配对运算装置、配对运算方法以及记录有配对运算程序的记录介质的制作方法
专利名称：配对运算装置、配对运算方法以及记录有配对运算程序的记录介质的制作方法
技术领域：
本发明涉及能够高速地进行配对运算的配对运算装置、配对运算方法以及记录有配对运算程序的记录介质。
背景技术：
以往，在个人用户利用因特网等网络上所提供的各种服务时，需要使用对每个个人用户预先设定ID及密码等进行认证。该认序通常是用于确认个人用户是正规用户，并利用认证服务器进行用于认证的认证处理。最近，通过使用数字签名，对各数据本身附加个人用户固有的数字签名数据，能够保证个人用户所使用的数据不会被第三者篡改，并能够在网络上安全地处理隐匿性高的信肩、ο另一方面，利用数字签名，通过认证服务器的认证处理，个人用户被确定，因而每次进行认证处理时，都在认证服务器上逐次保存各个人用户的历史记录。因此在认证服务器中保存个人用户访问了何网站、利用了何种服务等个人信息，从个人信息保护的观点来看，为了不使这些信息泄露，必须给予充分的注意。为了解决因使用数字签名产生的个人用户历史信息被存储的问题，提出了使用扩展数字签名而得到的数字群签名的方法。在使用数字群签名时，个人用户匿名向认证服务器发送仅证明属于某个群的签名数据，在认证服务器中，不是根据接收到的签名数据确定个人用户，而是认证个人用户属于某个群。因此，在认证服务器阻止不属于群的个人用户进行的不当使用，另一方面，能够不保存每个个人用户的历史信息而对个人用户进行认证。在上述数字群签名的匿名认证中使用配对运算。配对运算是使用两个输入一个输出的函数的计算，例如，令S为素域Fp上的有理点，Q为k次扩域Fpk上的有理点，通过输入两个有理点S和Q，则输出扩域FV5的元素z，而且，在输入有理点S的a倍和有理点Q的b倍时，则算出ζ的ab次幂，称为双线型性，利用该双线型性进行认证。在此，“k”为嵌入级数，“F*pk”在数学上正确的表示方式如下式，但因文本限制在行文中记为“fV5”。[式 31]F*pk通常，有理点S、Q分别使用椭圆曲线上的点，如上所述椭圆曲线上的点的配对运算包括使用米勒运算法则(miller' s algorithm)计算的步骤；和对其运算结果算幂乘法的步骤。在数字群签名中，当进行属于群的个人用户的访问权限的认证处理时，在进行了用于排除访问权限失效的个人用户的配对运算后，进行某个人用户的配对运算，而进行认证处理，由此能够灵活应对每个个人用户的访问权限的发行或失效的属性变更。
因此，例如在是由10000人的个人用户构成的群的数字群签名时，若访问权限失效的个人用户为100人，则需要进行100次的配对运算，对于一次配对运算基于当前一般的电子计算机需要大致0. 1秒的时间，那么100次配对运算就需要10秒，因此在实际运用中， 个人用户的数量受到限制，不能被广泛应用。因此，通过提高配对运算的计算速度能够提高数字群签名的实用性，为此提出了， 例如，使用由椭圆曲线定义的Tate配对运算法进行配对运算，降低计算负荷实现高速化的技术(参照例如专利文献1)。专利文献1 日本发明专利公开第2005-316^7号公报但是，目前提出的方案尚未充分提高配对运算的速度，需要进一步高速化。
发明内容
本发明人有鉴于上述现有技术中的问题，为提高配对运算的速度进行研发，从而得到本发明。本发明第1方面的配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp，b e Fp且嵌入级数为k 并以Fpk为定义体，令素数阶数r的有理点的集合为E [r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]),G2 = E[r] Π ΚθΓ(Φρ-[ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e &、Q e G2，整数变量为Χ，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F，CPU计算配对e(S，Q)，根据所述嵌入级数k，使用所述整数变量χ预先确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，所述电子计算机的CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算F的运算模块；计算通过规定有理点的直线上的有理点Q(Xq，yQ)的值的运算模块；使用所述F和所述值计算f’ X,S(Q)的运算模块；和使用所述f’ X,S(Q)根据[式32]e(S,Q) = f' Ls(Q)cPk-1)"计算所述配对e (S，Q)的运算模块。另外，本发明第2方面的配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp，b e Fp，且嵌入级数为k并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]),G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e &、Q e G2，整数变量为χ，对于多重配对的使用米勒运算法则(MMA)计算的有理函数为F，计算配对e (S， Q)，该配对运算方法中，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，并包括使所述电子计算机的CPU作为输入模块，将所述整数变量X、所述有理点S、所述有理点Q分别输入到规定的寄存器的步骤；使所述电子计算机的 CPU作为运算模块，计算F的步骤；使所述电子计算机的CPU作为运算模块，计算通过规定有理点的直线上的有理点Q(Xq，yQ)的值的步骤；使所述电子计算机的CPU作为运算模块， 使用所述F和所述值计算f’ X,S(Q)的步骤；和使所述电子计算机的CPU作为运算模块，使用所述f’ X,S(Q)根据[式33]e(S,Q) = f' κ s (Q) (Pk-DA计算所述配对e (S，Q)的步骤。另外，本发明第3方面的记录于记录介质的配对运算程序，使在具有CPU的电子计算机中，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 =x3+ax+b,a e Fp，b e Fp，且嵌入级数为k并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]),G2 = E[r] Π ΚθΓ(Φρ-[ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e &、Q e G2，整数变量为χ，对于多重配对的使用米勒运算法则(MMA)计算的有理函数为F，计算配对e (S， Q)，该配对运算程序，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，并使电子计算机的CPU分别起到将所述整数变量χ、所述有理点 S、所述有理点Q分别输入到规定的寄存器的输入模块的功能；计算F的运算模块的功能； 计算通过规定有理点的直线上的有理点QUq，yQ)的值的运算模块的功能；使用所述F和所述值计算f’ X’S(Q)的运算模块的功能；和使用所述f’ X,S(Q)根据[式34]e(S,Q) = f' ^s(Q)CPk-1V计算所述配对e (S，Q)的运算模块的功能。另外，本发明第4方面的配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b, b e Fp且嵌入级数为12并以Fp12为定义体，令素数阶数r的有理点的集合为E [r]，令Φρ为弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]),G2 = E[r] Π ΚθΓ(Φρ-[ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(FV2)r ；令S e G1^Q e G2，整数变量为X，Zs为具有S、PS的有理点的集合，4为具有pQ、Q的有理点的集合，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F2lZs(ZQ〕，CPU计算配对e(S，Q)，所
述配对运算装置使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为r( χ ) = 36 χ 4_36 χ 3+18 χ 2_6 χ +1，t ( χ ) = 6 χ 2+1使用基于所述整数变量X的标示ρ的如下所示Pki的表达式为
ρ = (2 χ -1) ρ10+2 χ (mod r ( χ ))所述CPU具有将所述整数变量X、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算F2jozs(Zq)的第一运算模块；使用在计算所述Sza(ZQ)时算出的2 χ S和2 χ pS计算规定的有理点的第二运算模块；计算通过所述有理点的直线上的有理点Q(xQ，yQ)的值的第三运算模块；使用所述Zs(zQ)和所述值计算f’ X,S(Q)的第四运算
模块；和使用所述f’ X,JQ)，根据[式；35]
权利要求
1.一种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp, b e Fp、且嵌入级数为k、并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e Gp Q e (}2，整数变量为χ，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F，所述CPU计算配对e (S，Q)， 所述配对运算装置的特征在于根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ 的迹t，所述CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算F的运算模块；计算通过规定有理点的直线上的有理点Q(xq，yQ)的值的运算模块； 使用所述F和所述值计算f’ X,S(Q)的运算模块；和使用所述f’ x,dQ)，根据 [式1]e(S,Q) = f' ^ s(Q)CPk-DA计算所述配对e (S，Q)的运算模块。
2.—种配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp, b e Fp，且嵌入级数为k，并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e Gp Q e (}2，整数变量为χ，对于多重配对的使用米勒运算法则(MMA)计算的有理函数为F，而计算配对e (S，Q)， 所述配对运算方法的特征在于根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ 的迹t，并包括使所述电子计算机的CPU作为输入模块，将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的步骤；使所述电子计算机的CPU作为运算模块，计算F的步骤；使所述电子计算机的CPU作为运算模块，计算通过规定有理点的直线上的有理点Q(xq， yQ)的值的步骤；使所述电子计算机的CPU作为运算模块，使用所述F和所述值计算f’ X’S(Q)的步骤；和使所述电子计算机的CPU作为运算模块，使用所述f·’ x，sto)，根据 [式2]
3.—种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b, a e Fp, b e Fp、且嵌入级数为k、并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e非退化双线型映射定义为e =G1XG2 — F*pk/(F*pk)r ；令S e Gp Q e (}2，整数变量为χ，对于多重配对的使用米勒运算法则(MMA)计算的有理函数为F，计算配对e (S，Q)，该配对运算程序，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，并使电子计算机的CPU分别起到将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块的功能；计算F的运算模块的功能；计算通过规定有理点的直线的有理点Q(xq，yQ)上的值的运算模块的功能； 使用所述F和所述值计算f’ X,S(Q)的运算模块的功能；和使用所述f’ X,JQ)，根据 [式3]
4.一种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b, b e Fp、且嵌入级数为12、并以Fp12为定义体，令素数阶数r的有理点的集合为EM， 令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射
5.如权利要求4所述的配对运算装置，其特征在于在所述第二运算模块中，使用已得到的运算结果分别依次计算有理点-S、(2 χ-DS, P10 ((2 χ -1) S)、-pS、(2 χ -1) pS、ρ10 ((2 χ -1) pS)， 在所述第三运算模块中分别计算通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1 ； 通过有理点G2x-l)pS，-pS)的直线上的有理点Q(xQ，yQ)的值I2 ； 通过有理点(p1QG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I3 ； 通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值14， 在所述第四运算模块中，根据 [式5]
6.一种配对运算方法，其利用具有CPU的电子计算机进行如下配对运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 =x3+b, b e Fp，且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集合为EM， 令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(F*p12)r ； ^Se G1^Q e G2,整数变量为χ，Zs为具有S、pS的有理点的集合，Zq为具有pQ、Q的有理点的集合，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F2iZs(ZQ〕， 计算配对e(S，Q)，所述配对运算方法的特征在于使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为 r ( χ ) = 36 χ 4-36 χ 3+18 χ 2-6 χ +1， t(x) = 6 x2+l使用基于所述整数变量Χ的标示ρ的、如下所示ρ"1的表达式为 ρ = (2 χ -1) ρ10+2 χ (mod r ( χ )) 并且包括使所述电子计算机的CPU作为输入模块，将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入步骤；使所述电子计算机的CPU作为第一运算模块，计算:p2(zQ);的第一运算步骤； 使所述电子计算机的CPU作为第二运算模块，使用在计算所述(Zq)时算出的2 χ S 和2 χ pS计算规定的有理点的第二运算步骤；使所述电子计算机的CPU作为第三运算模块，计算通过所述有理点的直线上的有理点Q(xq，yQ)的值的第三运算步骤；使所述电子计算机的CPU作为第四运算模块，使用所述和所述值计算f ’ x, S(Q)的第四运算步骤；和使所述电子计算机的CPU作为第五运算模块，使用所述f’ X,S(Q)，根据[式6]
7.如权利要求6所述的配对运算方法，其特征在于在所述第二运算步骤中，使用已得到的运算结果分别依次计算有理点-S、(2 χ-DS, P10 ((2 χ -1) S)、-pS、(2 χ -1) pS、ρ10 ((2 χ -1) pS)， 在所述第三运算步骤中分别计算通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1 ； 通过有理点G2x-l)pS，-pS)的直线上的有理点Q(xQ，yQ)的值I2 ； 通过有理点(p1QG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I3 ； 通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值14， 在所述第四运算步骤中，根据[式7]
8.—种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算 机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲 线式为ザ=x3+b,b G Fp且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集 合为Et]，令^^为弗罗贝尼乌斯自同态映射，根据
9.如权利要求8所述的记录有配对运算程序的记录介质，其特征在于使作为第二运算模块的电子计算机CPU，使用已得到的运算结果依次执行有理点
10. 一种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax, a e Fp，且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E [r]， 令弗罗贝尼乌斯自同态映射， 根据 将配对e定义为非退化双线型映射e =G1XG2 — F*p8/(F*p8)r ；令S e G1^Q e (}2，整数变量为χ ,Zs为具有S、p3S的有理点的集合，&为具有p3Q、Q的有理点的集合，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F3;^Zs(ZQ)， 所述CPU计算配对e (S，Q)， 所述配对运算装置的特征在于使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为 r ( χ ) = 9 χ 4+12 χ 3+8 χ 2+4 χ +1， t ( χ ) = -9 χ 3-3 χ 2-2 χ使用基于所述整数变量χ的标示P的如下所示P2和P3的表达式为P3 ε ρ2+3 χ +1 (mod r(x))所述CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算F3x,Zs(ZQ)的第一运算模块；使用已得到的运算结果分别依次计算有理点P2 (S)、ρ2 (p3S)、(3 χ+DS, (3 χ+Dp3S ^ 第二运算模块； 分别计算通过有理点(3 χ S，S)的直线上的有理点Q(xq，yQ)的值I5 ；通过有理点(P2 (S)，(3 χ+1)S)的直线上的有理点Q(xQ，yQ)的值I6 ；通过有理点(3 χ p3S, p3S)的直线上的有理点Q(xq，yQ)的值I7 ；通过有理点(P2(P3S), (3 χ+l)p3S)的直线上的有理点Q(xq，yQ)的值I8的第三运算模块；使用所述第一运算模块的运算结果和所述第三运算模块的运算结果，根据 [式 10]7
11. 一种配对运算方法，其利用具有CPU的电子计算机进行如下配对运算， 令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax, a e Fp，且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E [r]， 令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p8/(F*p8)r ；令
12. —种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax, a e Fp且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p8/(F*p8)r ；令S e G1^Q e (}2，整数变量为χ ,Zs为具有S、p3S的有理点的集合，&为具有p3Q、Q的有理点的集合，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F3lZs(ZQ), 计算配对e(S，Q)，该配对运算程序，使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为
13.—种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp, b e Fp，且嵌入级数为k，并以Fpk为定义体，令素数阶数r的有理点集合为 E[r]，令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ； 令S e GpQ e (}2，整数变量为χ，令使用米勒运算法则计算的有理函数为f， 所述CPU计算配对e (S，Q)， 所述配对运算装置的特征在于根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ 的迹t，所述CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算f的运算模块；计算通过规定的有理点的直线上的有理点Q(xq，yQ)的值的运算模块； 使用所述f和所述值计算f’ X,S(Q)的运算模块；和使用所述f’ X,JQ)，根据 [式 16]e(S,Q) = f' XiS(.Q)ipk-iyr计算所述配对e (S，Q)的运算模块。
14.一种配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp, b e Fp，且嵌入级数为k，并以Fpk为定义体，令素数阶数r的有理点集合为 E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e G1^Q e (}2，整数变量为χ，令使用米勒运算法则计算的有理函数为f，计算配对 e(S，Q)，所述配对运算方法的特征在于根据所述嵌入级数k，使用所述整数变量X确定阶数r和弗罗贝尼乌斯自同态映射Φρ 的迹t，并包括使所述电子计算机的CPU作为输入模块，将所述整数变量X、所述有理点S、所述有理点Q分别输入到规定的寄存器的步骤；使所述电子计算机的CPU作为运算模块，计算f的步骤；使所述电子计算机的CPU作为运算模块，计算通过规定的有理点的直线上的有理点 Q(xq，yQ)的值的步骤；使所述电子计算机的CPU作为输入模块，使用所述f和所述值计算f’ X’S(Q)的步骤；和使所述电子计算机的CPU作为输入模块，使用所述f’ x，sto)，根据 [式 17]e(S,Q) = f' x,s(Q)(pk-1)/r计算所述配对e (S，Q)的步骤。
15.一种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp，b e Fp且嵌入级数为k，并以Fpk为定义体，令素数阶数r的有理点集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e G1^Q e (}2，整数变量为χ，令使用米勒运算法则计算的有理函数为f，计算配对 e(S，Q)，该配对运算程序，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，并使所述电子计算机的CPU起到将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块的功能；计算f的运算模块的功能；计算通过规定的有理点的直线上的有理点Q(xq，yQ)的值的运算模块的功能； 使用所述f和所述值计算f’ X,S(Q)的运算模块的功能；和使用所述f’ X,JQ)，根据 [式 16]e(S,Q) = f' LS(Q)(pk-1)/r计算所述配对e (S，Q)的运算模块的功能。
16.一种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b, b e Fp且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集合为E[r]， 令弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(F*p12)r ； 令S e Gl、Q e ( ，整数变量为χ，令使用米勒运算法则计算的有理函数为f2x,s(Q)， 所述CPU计算配对e (S，Q)， 所述配对运算装置的特征在于使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为 r ( χ ) = 36 χ 4-36 χ 3+18 χ 2-6 χ +1， t(x) = 6 x2+l使用基于所述整数变量χ的标示ρ的如下所示的表达式为 ρ = (2 χ -1) ρ10+2 χ (mod r ( χ )) 所述CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算f2x,s(Q) ^P f2x,ps(Q)的第一运算模块；使用在计算所述f2x,s(Q)禾日f2x,ps0i)时算出的2xS和2xpS计算规定的有理点的第二运算模块；计算通过所述有理点的直线上的有理点Q(xq，yQ)的值的第三运算模块； 使用所述f2x,s(Q)和所述值计算f’ X,S(Q)的第四运算模块；和使用所述f’ X,S(Q)，根据[式側
17.如权利要求16所述的配对运算装置，其特征在于在所述第二运算模块中，使用已得到的运算结果分别依次计算有理点-S、(2 χ-DS, P10 ((2 χ -1) S)、-pS、(2 χ -1) pS、ρ10 ((2 χ -1) pS)， 在所述第三运算模块中分别计算通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1 ； 通过有理点(p1QG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I2 ； 通过有理点G2x-l)pS，-pS)的直线上的有理点Q(xQ，yQ)的值I3 ； 通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值14， 在所述第四运算模块中，使用所述有理点Q(xq，yQ)的值I:、12、13、I4，根据 [式 20]
18.—种配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b, b e Fp且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集合为E[r]， 令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(F*p12)r ； 令S e Gl、Q e ( ，整数变量为χ，令使用米勒运算法则计算的有理函数为f2x,s(Q)，计算配对e(S，Q)，所述配对运算方法的特征在于使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为 r ( χ ) = 36 χ 4-36 χ 3+18 χ 2-6 χ +1， t(x) = 6 x2+l使用基于所述整数变量χ的标示ρ的如下所示的表达式为 ρ = (2 χ -1) ρ10+2 χ (mod r ( χ )) 并且包括使所述电子计算机的CPU作为输入模块，将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入步骤；使所述电子计算机的CPU作为第一运算模块，计算f2x,s(Q)和f2x,ps(Q)的第一运算步骤；使所述电子计算机的CPU作为第二运算模块，使用在计算所述f2x,s(Q)和f2x,pjQ)时算出的2 χ S和2 χ pS计算规定的有理点的第二运算步骤；使所述电子计算机的CPU作为第三运算模块，计算通过所述有理点的直线上的有理点 Q(xq, yQ)的值的第三运算步骤；使所述电子计算机的CPU作为第四运算模块，使用所述f2x,s(Q)和所述值计算f’ x, s (Q)的第四运算步骤；和使所述电子计算机的CPU作为第五运算模块，使用所述f’ x，s⑴)，根据 [式 21]e(S,Q) = f' x.s(Q)(p1z—1)/Γ计算所述配对e (S，Q)的第五运算步骤。
19.如权利要求18所述的配对运算方法，其特征在于在所述第二运算步骤中，使用已得到的运算结果分别依次计算有理点-S、(2 χ-DS, P10 ((2 χ -1) S)、-pS、(2 χ -1) pS、ρ10 ((2 χ -1) pS)， 在所述第三运算步骤中分别计算通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1 ； 通过有理点(p1QG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I2 ； 通过有理点G2x-l)pS，-pS)的直线上的有理点Q(xQ，yQ)的值I3 ； 通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值14， 在所述第四运算步骤中，使用所述有理点Q(xq，yQ)的值Ip 12、13、I4，根据[式22]
20.一种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b,b e Fp且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(F*p12)r ； 令S e Gl、Q e ( ，整数变量为χ，令使用米勒运算法则计算的有理函数为f2x,s(Q)，计算配对e(S，Q)，该配对运算程序，使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为r ( χ ) = 36 χ 4-36 χ 3+18 χ 2-6 χ +1， t(x) = 6 x2+l使用基于所述整数变量χ标示ρ的如下所示的表达式为 ρ = (2 χ -1) ρ10+2 χ (mod r ( χ )) 并使所述电子计算机的CPU起到将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块的功能；计算f2x,s(Q) ^P f2x,ps(Q)的第一运算模块的功能；使用在计算所述f2x,s(Q)禾日f2x,ps0i)时算出的2xS和2xpS计算规定的有理点的第二运算模块的功能；计算通过所述有理点的直线上的有理点Q(xq，yQ)的值的第三运算模块的功能； 使用所述f2x,s(Q)和所述值计算f’ X,S(Q)的第四运算模块的功能；和使用所述f’ X,JQ)，根据 [式 23]
21.如权利要求20所述的记录有配对运算程序的记录介质，其特征在于使作为第二运算模块的电子计算机CPU，使用已得到的运算结果依次执行有理点-S、 (2 χ-1)S, ρ10 ((2 X-1) S),-pS, (2x-l)pS,p10((2x-l)pS)的计算， 使作为第三运算模块的电子计算机CPU，执行通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1的计算； 通过有理点(p1(lG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I2的计算； 通过有理点( χ -l)pS, -pS)的直线上的有理点Q(xq，yQ)的值I3的计算；通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值I4的运算， 使作为第四运算模块的电子计算机CPU，使用所述有理点QUQ，yQ)的值I1U2U3U4，根据[式
22. —种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax,a e Fp且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E [r]，令弗罗贝尼乌斯自同态映射， 根据
23. —种配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算， 令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax,a e Fp且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E [r]，令弗罗贝尼乌斯自同态映射， 根据
24. 一种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax, a e Fp且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E[r]，令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p8/(F*p8)r ；令S e Gl、Q e ( ，整数变量为χ，令使用米勒运算法则计算的有理函数为f3x,s0 ，计算配对e(S，Q)，该配对运算程序，使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为
全文摘要
本发明涉及配对运算装置，其具有CPU，该CPU令S∈G1、Q∈G2，整数变量为χ，令使用米勒运算法则(MMA)计算的有理函数为F，计算配对e(S，Q)，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射φp的迹t，该CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；运算F的运算模块；运算通过规定有理点的直线上的有理点Q(xQ，yQ)的值的运算模块；使用所述F和所述值运算f’χ，s、(Q)的运算模块；和使用所述f’χ，s(Q)根据[式83]计算所述配对e(S，Q)的运算模块。
文档编号G09C1/00GK102405469SQ201080017250
公开日2012年4月4日 申请日期2010年4月21日 优先权日2009年4月21日
发明者森川良孝, 那须弘明, 酒见由美, 野上保之 申请人:国立大学法人冈山大学
技术领域：
本发明涉及能够高速地进行配对运算的配对运算装置、配对运算方法以及记录有配对运算程序的记录介质。
背景技术：
以往，在个人用户利用因特网等网络上所提供的各种服务时，需要使用对每个个人用户预先设定ID及密码等进行认证。该认序通常是用于确认个人用户是正规用户，并利用认证服务器进行用于认证的认证处理。最近，通过使用数字签名，对各数据本身附加个人用户固有的数字签名数据，能够保证个人用户所使用的数据不会被第三者篡改，并能够在网络上安全地处理隐匿性高的信肩、ο另一方面，利用数字签名，通过认证服务器的认证处理，个人用户被确定，因而每次进行认证处理时，都在认证服务器上逐次保存各个人用户的历史记录。因此在认证服务器中保存个人用户访问了何网站、利用了何种服务等个人信息，从个人信息保护的观点来看，为了不使这些信息泄露，必须给予充分的注意。为了解决因使用数字签名产生的个人用户历史信息被存储的问题，提出了使用扩展数字签名而得到的数字群签名的方法。在使用数字群签名时，个人用户匿名向认证服务器发送仅证明属于某个群的签名数据，在认证服务器中，不是根据接收到的签名数据确定个人用户，而是认证个人用户属于某个群。因此，在认证服务器阻止不属于群的个人用户进行的不当使用，另一方面，能够不保存每个个人用户的历史信息而对个人用户进行认证。在上述数字群签名的匿名认证中使用配对运算。配对运算是使用两个输入一个输出的函数的计算，例如，令S为素域Fp上的有理点，Q为k次扩域Fpk上的有理点，通过输入两个有理点S和Q，则输出扩域FV5的元素z，而且，在输入有理点S的a倍和有理点Q的b倍时，则算出ζ的ab次幂，称为双线型性，利用该双线型性进行认证。在此，“k”为嵌入级数，“F*pk”在数学上正确的表示方式如下式，但因文本限制在行文中记为“fV5”。[式 31]F*pk通常，有理点S、Q分别使用椭圆曲线上的点，如上所述椭圆曲线上的点的配对运算包括使用米勒运算法则(miller' s algorithm)计算的步骤；和对其运算结果算幂乘法的步骤。在数字群签名中，当进行属于群的个人用户的访问权限的认证处理时，在进行了用于排除访问权限失效的个人用户的配对运算后，进行某个人用户的配对运算，而进行认证处理，由此能够灵活应对每个个人用户的访问权限的发行或失效的属性变更。
因此，例如在是由10000人的个人用户构成的群的数字群签名时，若访问权限失效的个人用户为100人，则需要进行100次的配对运算，对于一次配对运算基于当前一般的电子计算机需要大致0. 1秒的时间，那么100次配对运算就需要10秒，因此在实际运用中， 个人用户的数量受到限制，不能被广泛应用。因此，通过提高配对运算的计算速度能够提高数字群签名的实用性，为此提出了， 例如，使用由椭圆曲线定义的Tate配对运算法进行配对运算，降低计算负荷实现高速化的技术(参照例如专利文献1)。专利文献1 日本发明专利公开第2005-316^7号公报但是，目前提出的方案尚未充分提高配对运算的速度，需要进一步高速化。
发明内容
本发明人有鉴于上述现有技术中的问题，为提高配对运算的速度进行研发，从而得到本发明。本发明第1方面的配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp，b e Fp且嵌入级数为k 并以Fpk为定义体，令素数阶数r的有理点的集合为E [r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]),G2 = E[r] Π ΚθΓ(Φρ-[ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e &、Q e G2，整数变量为Χ，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F，CPU计算配对e(S，Q)，根据所述嵌入级数k，使用所述整数变量χ预先确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，所述电子计算机的CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算F的运算模块；计算通过规定有理点的直线上的有理点Q(Xq，yQ)的值的运算模块；使用所述F和所述值计算f’ X,S(Q)的运算模块；和使用所述f’ X,S(Q)根据[式32]e(S,Q) = f' Ls(Q)cPk-1)"计算所述配对e (S，Q)的运算模块。另外，本发明第2方面的配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp，b e Fp，且嵌入级数为k并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]),G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e &、Q e G2，整数变量为χ，对于多重配对的使用米勒运算法则(MMA)计算的有理函数为F，计算配对e (S， Q)，该配对运算方法中，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，并包括使所述电子计算机的CPU作为输入模块，将所述整数变量X、所述有理点S、所述有理点Q分别输入到规定的寄存器的步骤；使所述电子计算机的 CPU作为运算模块，计算F的步骤；使所述电子计算机的CPU作为运算模块，计算通过规定有理点的直线上的有理点Q(Xq，yQ)的值的步骤；使所述电子计算机的CPU作为运算模块， 使用所述F和所述值计算f’ X,S(Q)的步骤；和使所述电子计算机的CPU作为运算模块，使用所述f’ X,S(Q)根据[式33]e(S,Q) = f' κ s (Q) (Pk-DA计算所述配对e (S，Q)的步骤。另外，本发明第3方面的记录于记录介质的配对运算程序，使在具有CPU的电子计算机中，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 =x3+ax+b,a e Fp，b e Fp，且嵌入级数为k并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]),G2 = E[r] Π ΚθΓ(Φρ-[ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e &、Q e G2，整数变量为χ，对于多重配对的使用米勒运算法则(MMA)计算的有理函数为F，计算配对e (S， Q)，该配对运算程序，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，并使电子计算机的CPU分别起到将所述整数变量χ、所述有理点 S、所述有理点Q分别输入到规定的寄存器的输入模块的功能；计算F的运算模块的功能； 计算通过规定有理点的直线上的有理点QUq，yQ)的值的运算模块的功能；使用所述F和所述值计算f’ X’S(Q)的运算模块的功能；和使用所述f’ X,S(Q)根据[式34]e(S,Q) = f' ^s(Q)CPk-1V计算所述配对e (S，Q)的运算模块的功能。另外，本发明第4方面的配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b, b e Fp且嵌入级数为12并以Fp12为定义体，令素数阶数r的有理点的集合为E [r]，令Φρ为弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]),G2 = E[r] Π ΚθΓ(Φρ-[ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(FV2)r ；令S e G1^Q e G2，整数变量为X，Zs为具有S、PS的有理点的集合，4为具有pQ、Q的有理点的集合，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F2lZs(ZQ〕，CPU计算配对e(S，Q)，所
述配对运算装置使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为r( χ ) = 36 χ 4_36 χ 3+18 χ 2_6 χ +1，t ( χ ) = 6 χ 2+1使用基于所述整数变量X的标示ρ的如下所示Pki的表达式为
ρ = (2 χ -1) ρ10+2 χ (mod r ( χ ))所述CPU具有将所述整数变量X、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算F2jozs(Zq)的第一运算模块；使用在计算所述Sza(ZQ)时算出的2 χ S和2 χ pS计算规定的有理点的第二运算模块；计算通过所述有理点的直线上的有理点Q(xQ，yQ)的值的第三运算模块；使用所述Zs(zQ)和所述值计算f’ X,S(Q)的第四运算
模块；和使用所述f’ X,JQ)，根据[式；35]
权利要求
1.一种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp, b e Fp、且嵌入级数为k、并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e Gp Q e (}2，整数变量为χ，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F，所述CPU计算配对e (S，Q)， 所述配对运算装置的特征在于根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ 的迹t，所述CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算F的运算模块；计算通过规定有理点的直线上的有理点Q(xq，yQ)的值的运算模块； 使用所述F和所述值计算f’ X,S(Q)的运算模块；和使用所述f’ x,dQ)，根据 [式1]e(S,Q) = f' ^ s(Q)CPk-DA计算所述配对e (S，Q)的运算模块。
2.—种配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp, b e Fp，且嵌入级数为k，并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e Gp Q e (}2，整数变量为χ，对于多重配对的使用米勒运算法则(MMA)计算的有理函数为F，而计算配对e (S，Q)， 所述配对运算方法的特征在于根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ 的迹t，并包括使所述电子计算机的CPU作为输入模块，将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的步骤；使所述电子计算机的CPU作为运算模块，计算F的步骤；使所述电子计算机的CPU作为运算模块，计算通过规定有理点的直线上的有理点Q(xq， yQ)的值的步骤；使所述电子计算机的CPU作为运算模块，使用所述F和所述值计算f’ X’S(Q)的步骤；和使所述电子计算机的CPU作为运算模块，使用所述f·’ x，sto)，根据 [式2]
3.—种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b, a e Fp, b e Fp、且嵌入级数为k、并以Fpk为定义体，令素数阶数r的有理点的集合为E[r]，令弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e非退化双线型映射定义为e =G1XG2 — F*pk/(F*pk)r ；令S e Gp Q e (}2，整数变量为χ，对于多重配对的使用米勒运算法则(MMA)计算的有理函数为F，计算配对e (S，Q)，该配对运算程序，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，并使电子计算机的CPU分别起到将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块的功能；计算F的运算模块的功能；计算通过规定有理点的直线的有理点Q(xq，yQ)上的值的运算模块的功能； 使用所述F和所述值计算f’ X,S(Q)的运算模块的功能；和使用所述f’ X,JQ)，根据 [式3]
4.一种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b, b e Fp、且嵌入级数为12、并以Fp12为定义体，令素数阶数r的有理点的集合为EM， 令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射
5.如权利要求4所述的配对运算装置，其特征在于在所述第二运算模块中，使用已得到的运算结果分别依次计算有理点-S、(2 χ-DS, P10 ((2 χ -1) S)、-pS、(2 χ -1) pS、ρ10 ((2 χ -1) pS)， 在所述第三运算模块中分别计算通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1 ； 通过有理点G2x-l)pS，-pS)的直线上的有理点Q(xQ，yQ)的值I2 ； 通过有理点(p1QG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I3 ； 通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值14， 在所述第四运算模块中，根据 [式5]
6.一种配对运算方法，其利用具有CPU的电子计算机进行如下配对运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 =x3+b, b e Fp，且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集合为EM， 令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(F*p12)r ； ^Se G1^Q e G2,整数变量为χ，Zs为具有S、pS的有理点的集合，Zq为具有pQ、Q的有理点的集合，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F2iZs(ZQ〕， 计算配对e(S，Q)，所述配对运算方法的特征在于使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为 r ( χ ) = 36 χ 4-36 χ 3+18 χ 2-6 χ +1， t(x) = 6 x2+l使用基于所述整数变量Χ的标示ρ的、如下所示ρ"1的表达式为 ρ = (2 χ -1) ρ10+2 χ (mod r ( χ )) 并且包括使所述电子计算机的CPU作为输入模块，将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入步骤；使所述电子计算机的CPU作为第一运算模块，计算:p2(zQ);的第一运算步骤； 使所述电子计算机的CPU作为第二运算模块，使用在计算所述(Zq)时算出的2 χ S 和2 χ pS计算规定的有理点的第二运算步骤；使所述电子计算机的CPU作为第三运算模块，计算通过所述有理点的直线上的有理点Q(xq，yQ)的值的第三运算步骤；使所述电子计算机的CPU作为第四运算模块，使用所述和所述值计算f ’ x, S(Q)的第四运算步骤；和使所述电子计算机的CPU作为第五运算模块，使用所述f’ X,S(Q)，根据[式6]
7.如权利要求6所述的配对运算方法，其特征在于在所述第二运算步骤中，使用已得到的运算结果分别依次计算有理点-S、(2 χ-DS, P10 ((2 χ -1) S)、-pS、(2 χ -1) pS、ρ10 ((2 χ -1) pS)， 在所述第三运算步骤中分别计算通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1 ； 通过有理点G2x-l)pS，-pS)的直线上的有理点Q(xQ，yQ)的值I2 ； 通过有理点(p1QG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I3 ； 通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值14， 在所述第四运算步骤中，根据[式7]
8.—种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算 机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲 线式为ザ=x3+b,b G Fp且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集 合为Et]，令^^为弗罗贝尼乌斯自同态映射，根据
9.如权利要求8所述的记录有配对运算程序的记录介质，其特征在于使作为第二运算模块的电子计算机CPU，使用已得到的运算结果依次执行有理点
10. 一种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax, a e Fp，且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E [r]， 令弗罗贝尼乌斯自同态映射， 根据 将配对e定义为非退化双线型映射e =G1XG2 — F*p8/(F*p8)r ；令S e G1^Q e (}2，整数变量为χ ,Zs为具有S、p3S的有理点的集合，&为具有p3Q、Q的有理点的集合，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F3;^Zs(ZQ)， 所述CPU计算配对e (S，Q)， 所述配对运算装置的特征在于使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为 r ( χ ) = 9 χ 4+12 χ 3+8 χ 2+4 χ +1， t ( χ ) = -9 χ 3-3 χ 2-2 χ使用基于所述整数变量χ的标示P的如下所示P2和P3的表达式为P3 ε ρ2+3 χ +1 (mod r(x))所述CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算F3x,Zs(ZQ)的第一运算模块；使用已得到的运算结果分别依次计算有理点P2 (S)、ρ2 (p3S)、(3 χ+DS, (3 χ+Dp3S ^ 第二运算模块； 分别计算通过有理点(3 χ S，S)的直线上的有理点Q(xq，yQ)的值I5 ；通过有理点(P2 (S)，(3 χ+1)S)的直线上的有理点Q(xQ，yQ)的值I6 ；通过有理点(3 χ p3S, p3S)的直线上的有理点Q(xq，yQ)的值I7 ；通过有理点(P2(P3S), (3 χ+l)p3S)的直线上的有理点Q(xq，yQ)的值I8的第三运算模块；使用所述第一运算模块的运算结果和所述第三运算模块的运算结果，根据 [式 10]7
11. 一种配对运算方法，其利用具有CPU的电子计算机进行如下配对运算， 令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax, a e Fp，且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E [r]， 令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p8/(F*p8)r ；令
12. —种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax, a e Fp且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p8/(F*p8)r ；令S e G1^Q e (}2，整数变量为χ ,Zs为具有S、p3S的有理点的集合，&为具有p3Q、Q的有理点的集合，令使用针对多重配对的米勒运算法则(MMA)计算的有理函数为F3lZs(ZQ), 计算配对e(S，Q)，该配对运算程序，使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为
13.—种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp, b e Fp，且嵌入级数为k，并以Fpk为定义体，令素数阶数r的有理点集合为 E[r]，令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ； 令S e GpQ e (}2，整数变量为χ，令使用米勒运算法则计算的有理函数为f， 所述CPU计算配对e (S，Q)， 所述配对运算装置的特征在于根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ 的迹t，所述CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算f的运算模块；计算通过规定的有理点的直线上的有理点Q(xq，yQ)的值的运算模块； 使用所述f和所述值计算f’ X,S(Q)的运算模块；和使用所述f’ X,JQ)，根据 [式 16]e(S,Q) = f' XiS(.Q)ipk-iyr计算所述配对e (S，Q)的运算模块。
14.一种配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp, b e Fp，且嵌入级数为k，并以Fpk为定义体，令素数阶数r的有理点集合为 E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据 G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e G1^Q e (}2，整数变量为χ，令使用米勒运算法则计算的有理函数为f，计算配对 e(S，Q)，所述配对运算方法的特征在于根据所述嵌入级数k，使用所述整数变量X确定阶数r和弗罗贝尼乌斯自同态映射Φρ 的迹t，并包括使所述电子计算机的CPU作为输入模块，将所述整数变量X、所述有理点S、所述有理点Q分别输入到规定的寄存器的步骤；使所述电子计算机的CPU作为运算模块，计算f的步骤；使所述电子计算机的CPU作为运算模块，计算通过规定的有理点的直线上的有理点 Q(xq，yQ)的值的步骤；使所述电子计算机的CPU作为输入模块，使用所述f和所述值计算f’ X’S(Q)的步骤；和使所述电子计算机的CPU作为输入模块，使用所述f’ x，sto)，根据 [式 17]e(S,Q) = f' x,s(Q)(pk-1)/r计算所述配对e (S，Q)的步骤。
15.一种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax+b,a e Fp，b e Fp且嵌入级数为k，并以Fpk为定义体，令素数阶数r的有理点集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*pk/(F*pk)r ；令S e G1^Q e (}2，整数变量为χ，令使用米勒运算法则计算的有理函数为f，计算配对 e(S，Q)，该配对运算程序，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t，并使所述电子计算机的CPU起到将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块的功能；计算f的运算模块的功能；计算通过规定的有理点的直线上的有理点Q(xq，yQ)的值的运算模块的功能； 使用所述f和所述值计算f’ X,S(Q)的运算模块的功能；和使用所述f’ X,JQ)，根据 [式 16]e(S,Q) = f' LS(Q)(pk-1)/r计算所述配对e (S，Q)的运算模块的功能。
16.一种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b, b e Fp且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集合为E[r]， 令弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(F*p12)r ； 令S e Gl、Q e ( ，整数变量为χ，令使用米勒运算法则计算的有理函数为f2x,s(Q)， 所述CPU计算配对e (S，Q)， 所述配对运算装置的特征在于使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为 r ( χ ) = 36 χ 4-36 χ 3+18 χ 2-6 χ +1， t(x) = 6 x2+l使用基于所述整数变量χ的标示ρ的如下所示的表达式为 ρ = (2 χ -1) ρ10+2 χ (mod r ( χ )) 所述CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；计算f2x,s(Q) ^P f2x,ps(Q)的第一运算模块；使用在计算所述f2x,s(Q)禾日f2x,ps0i)时算出的2xS和2xpS计算规定的有理点的第二运算模块；计算通过所述有理点的直线上的有理点Q(xq，yQ)的值的第三运算模块； 使用所述f2x,s(Q)和所述值计算f’ X,S(Q)的第四运算模块；和使用所述f’ X,S(Q)，根据[式側
17.如权利要求16所述的配对运算装置，其特征在于在所述第二运算模块中，使用已得到的运算结果分别依次计算有理点-S、(2 χ-DS, P10 ((2 χ -1) S)、-pS、(2 χ -1) pS、ρ10 ((2 χ -1) pS)， 在所述第三运算模块中分别计算通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1 ； 通过有理点(p1QG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I2 ； 通过有理点G2x-l)pS，-pS)的直线上的有理点Q(xQ，yQ)的值I3 ； 通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值14， 在所述第四运算模块中，使用所述有理点Q(xq，yQ)的值I:、12、13、I4，根据 [式 20]
18.—种配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b, b e Fp且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集合为E[r]， 令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(F*p12)r ； 令S e Gl、Q e ( ，整数变量为χ，令使用米勒运算法则计算的有理函数为f2x,s(Q)，计算配对e(S，Q)，所述配对运算方法的特征在于使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为 r ( χ ) = 36 χ 4-36 χ 3+18 χ 2-6 χ +1， t(x) = 6 x2+l使用基于所述整数变量χ的标示ρ的如下所示的表达式为 ρ = (2 χ -1) ρ10+2 χ (mod r ( χ )) 并且包括使所述电子计算机的CPU作为输入模块，将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入步骤；使所述电子计算机的CPU作为第一运算模块，计算f2x,s(Q)和f2x,ps(Q)的第一运算步骤；使所述电子计算机的CPU作为第二运算模块，使用在计算所述f2x,s(Q)和f2x,pjQ)时算出的2 χ S和2 χ pS计算规定的有理点的第二运算步骤；使所述电子计算机的CPU作为第三运算模块，计算通过所述有理点的直线上的有理点 Q(xq, yQ)的值的第三运算步骤；使所述电子计算机的CPU作为第四运算模块，使用所述f2x,s(Q)和所述值计算f’ x, s (Q)的第四运算步骤；和使所述电子计算机的CPU作为第五运算模块，使用所述f’ x，s⑴)，根据 [式 21]e(S,Q) = f' x.s(Q)(p1z—1)/Γ计算所述配对e (S，Q)的第五运算步骤。
19.如权利要求18所述的配对运算方法，其特征在于在所述第二运算步骤中，使用已得到的运算结果分别依次计算有理点-S、(2 χ-DS, P10 ((2 χ -1) S)、-pS、(2 χ -1) pS、ρ10 ((2 χ -1) pS)， 在所述第三运算步骤中分别计算通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1 ； 通过有理点(p1QG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I2 ； 通过有理点G2x-l)pS，-pS)的直线上的有理点Q(xQ，yQ)的值I3 ； 通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值14， 在所述第四运算步骤中，使用所述有理点Q(xq，yQ)的值Ip 12、13、I4，根据[式22]
20.一种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+b,b e Fp且嵌入级数为12，并以Fp12为定义体，令素数阶数r的有理点的集合为E[r]，令Φρ为弗罗贝尼乌斯自同态映射，根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p12/(F*p12)r ； 令S e Gl、Q e ( ，整数变量为χ，令使用米勒运算法则计算的有理函数为f2x,s(Q)，计算配对e(S，Q)，该配对运算程序，使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为r ( χ ) = 36 χ 4-36 χ 3+18 χ 2-6 χ +1， t(x) = 6 x2+l使用基于所述整数变量χ标示ρ的如下所示的表达式为 ρ = (2 χ -1) ρ10+2 χ (mod r ( χ )) 并使所述电子计算机的CPU起到将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块的功能；计算f2x,s(Q) ^P f2x,ps(Q)的第一运算模块的功能；使用在计算所述f2x,s(Q)禾日f2x,ps0i)时算出的2xS和2xpS计算规定的有理点的第二运算模块的功能；计算通过所述有理点的直线上的有理点Q(xq，yQ)的值的第三运算模块的功能； 使用所述f2x,s(Q)和所述值计算f’ X,S(Q)的第四运算模块的功能；和使用所述f’ X,JQ)，根据 [式 23]
21.如权利要求20所述的记录有配对运算程序的记录介质，其特征在于使作为第二运算模块的电子计算机CPU，使用已得到的运算结果依次执行有理点-S、 (2 χ-1)S, ρ10 ((2 X-1) S),-pS, (2x-l)pS,p10((2x-l)pS)的计算， 使作为第三运算模块的电子计算机CPU，执行通过有理点G2x-l)S，-S)的直线上的有理点Q(xQ，yQ)的值I1的计算； 通过有理点(p1(lG2x-l)S)，2>cS)的直线上的有理点Q(xQ，yQ)的值I2的计算； 通过有理点( χ -l)pS, -pS)的直线上的有理点Q(xq，yQ)的值I3的计算；通过有理点(Piq(OX-I)PS)JxPS)的直线上的有理点Q(xQ，yQ)的值I4的运算， 使作为第四运算模块的电子计算机CPU，使用所述有理点QUQ，yQ)的值I1U2U3U4，根据[式
22. —种配对运算装置，其具有CPU，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax,a e Fp且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E [r]，令弗罗贝尼乌斯自同态映射， 根据
23. —种配对运算方法，其利用具有CPU的电子计算机，进行如下配对运算， 令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax,a e Fp且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E [r]，令弗罗贝尼乌斯自同态映射， 根据
24. 一种记录有配对运算程序的记录介质，其中的配对运算程序使具有CPU的电子计算机进行如下运算，令可配对的椭圆曲线上的有理点组成的加法群为E，其中该椭圆曲线的曲线式为y2 = x3+ax, a e Fp且嵌入级数为8，并以Fp8为定义体，令素数阶数r的有理点的集合为E[r]，令弗罗贝尼乌斯自同态映射， 根据G1 = E[r] Π Κθγ(Φρ-[1]), G2 = E[r] Π Κθγ(Φρ-[Ρ]),将配对e定义为非退化双线型映射e =G1XG2 — F*p8/(F*p8)r ；令S e Gl、Q e ( ，整数变量为χ，令使用米勒运算法则计算的有理函数为f3x,s0 ，计算配对e(S，Q)，该配对运算程序，使用所述整数变量χ，使阶数r和弗罗贝尼乌斯自同态映射Φρ的迹t为
全文摘要
本发明涉及配对运算装置，其具有CPU，该CPU令S∈G1、Q∈G2，整数变量为χ，令使用米勒运算法则(MMA)计算的有理函数为F，计算配对e(S，Q)，根据所述嵌入级数k，使用所述整数变量χ确定阶数r和弗罗贝尼乌斯自同态映射φp的迹t，该CPU具有将所述整数变量χ、所述有理点S、所述有理点Q分别输入到规定的寄存器的输入模块；运算F的运算模块；运算通过规定有理点的直线上的有理点Q(xQ，yQ)的值的运算模块；使用所述F和所述值运算f’χ，s、(Q)的运算模块；和使用所述f’χ，s(Q)根据[式83]计算所述配对e(S，Q)的运算模块。
文档编号G09C1/00GK102405469SQ201080017250
公开日2012年4月4日 申请日期2010年4月21日 优先权日2009年4月21日
发明者森川良孝, 那须弘明, 酒见由美, 野上保之 申请人:国立大学法人冈山大学
最新回复(0)