标量乘法器及标量乘法程序

摘要

提供了一种能以高速执行标量乘法的标量乘法器以及标量乘法程序。使用整数变量χ，在对嵌入次数k=12的情况下的特征p、阶数r、费罗贝尼乌斯自同态映射的迹t作为p(χ)=36χ

说明书

技术领域

本发明涉及进行有理点P的标量乘法[s]P的标量乘法器及标量乘法程序。

背景技术

历来，利用因特网等的电信线路提供如网上银行、向行政机关的电子申请等那样的各种服务。

在利用这样的服务的情况下，需要用于确认服务的利用者不是冒充、虚构的人等，而是恰当的利用者的认证处理。因此，作为可靠性高的认证方法，经常利用将使用公钥和密钥的公钥密码作为基础的电子认证技术。

近来，为了高效率地容易管理更多的利用者，提出了一种使用基于ID的密码、群签名的认证系统。

在基于ID的密码、群签名中，在进行配对运算的同时，进行所需要的幂乘法、标量乘法，为了尽可能地使认证处理需要的时间缩短，要求高速地执行这些运算。

因此，提出了一种使用二进制法、Window法等来使幂乘法、标量乘法高速化的方案。

进而，提出了一种在标量乘法中，通过利用映射来削减运算次数从而高速化的方法（例如，参照专利文献1、专利文献2）。

专利文献1：日本特开2004-271792号公报；

专利文献2：日本特开2007-41461号公报。

发明内容

发明要解决的问题

可是，仅利用映射来削减运算次数，高速化并不充分，特别是难以在数秒以内完成将超过1万人那样的利用者作为对象的认证处理，因此有不适于实用的可能。

本发明者们鉴于这样的现状，为了通过使标量乘法高速化而使实用性提高，进行研究开发而完成本发明。

用于解决课题的方案

本发明的标量乘法器，使用整数变量χ，对在嵌入次数k=12的情况下的特征p、阶数r、费罗贝尼乌斯自同态映射的迹t作为

而赋予的椭圆曲线的有理点形成的加法群E(F_p)的有理点P的标量乘法[s]P进行运算，其中，

将扭转次数d设为6，将k=d×e中的正整数e设为2，使用

的费罗贝尼乌斯映射φ'₂，因为

，所以通过令6χ²-4χ+1=ν，对所述标量s进行v进制展开，令

，由此获得

，对(-2χ+1)s₁部分进行v进制展开，令

，因为p⁴≡p²-1 mod r，所以利用

，将标量乘法[s]P作为

进行运算，

该标量乘法器为了进行上述运算，设置有：存储单元，存储所述标量s的值；以及第1～5辅助存储单元，分别存储所述系数s₁、s₂、s₃、s₄、s₅，将对所述标量s进行v进制展开而得到的值存储在所述第1辅助存储单元和所述第2辅助存储单元，将对(-2χ+1)s₁进行v进制展开而得到的值存储在所述第3辅助存储单元和所述第4辅助存储单元，将(-2χ+1)s₃的值存储在所述第5辅助存储单元。

此外，本发明的标量乘法程序，使具备CPU的电子计算机，使用整数变量χ，对在嵌入次数k=12的情况下的特征p、阶数r、费罗贝尼乌斯自同态映射的迹t作为

而赋予的椭圆曲线的有理点组成的加法群E(F_p)的有理点P的标量乘法[s]P进行运算，其中，

将扭转次数d设为6，将k=d×e中的正整数e设为2，使用

的费罗贝尼乌斯映射φ'₂，因为

，所以通过令6χ²-4χ+1=ν，对所述标量s进行v进制展开，令

，由此获得

，对(-2χ+1)s₁部分进行v进制展开，令

，因为p⁴≡p²-1 mod r，所以利用

，将标量乘法[s]P作为

进行运算，

该标量乘法程序为了使所述电子计算机进行上述运算，具有：将对所述标量s进行v进制展开而得到的所述s₁储存在第1寄存器并且将所述s₂储存在第2寄存器的步骤；将对(-2χ+1)s₁进行v进制展开而得到的所述s₃储存在第3寄存器并且将所述s₄储存在第4寄存器的步骤；以及将(-2χ+1)s₃的值作为所述s₅的值储存在第5寄存器的步骤。

此外，本发明的标量乘法器，使用整数变量χ，对在嵌入次数k=8的情况下的特征p、阶数r、费罗贝尼乌斯自同态映射的迹t作为

而赋予的椭圆曲线的有理点形成的加法群E(F_p)的有理点P的标量乘法[s]P进行运算，其中，

将扭转次数d设为4，将k=d×e中的正整数e设为2，使用

的费罗贝尼乌斯映射φ'₂，因为

，所以通过令3χ²+2χ=ν，对所述标量s进行v进制展开，令

，由此获得

，对(-2χ-1)s₁部分进行v进制展开，令

，因为p⁴≡-1 mod r，所以利用

，将标量乘法[s]P作为

进行运算，

该标量乘法器为了进行上述运算，设置有：存储单元，存储所述标量s的值；以及第1～5辅助存储单元，分别存储所述系数s₁、s₂、s₃、s₄、s₅，将对所述标量s进行v进制展开而得到的值存储在所述第1辅助存储单元和所述第2辅助存储单元，将对(-2χ-1)s₁进行v进制展开而得到的值存储在所述第3辅助存储单元和所述第4辅助存储单元，将(-2χ-1)s₃的值存储在所述第5辅助存储单元。

此外，本发明的标量乘法程序，使具备CPU的电子计算机，使用整数变量χ，对在嵌入次数k=8的情况下的特征p、阶数r、费罗贝尼乌斯自同态映射的迹t作为

而赋予的椭圆曲线的有理点形成的加法群E(Fp)的有理点P的标量乘法[s]P中进行运算，其中，

将扭转次数d设为4，将k=d×e中的正整数e设为2，使用

的费罗贝尼乌斯映射φ'₂，因为

，所以通过令3χ²+2χ=ν，对所述标量s进行v进制展开，令

，由此获得

对(-2χ-1)s₁部分进行v进制展开，令

，因为p⁴≡-1 mod r，所以利用

，将标量乘法[s]P作为

进行运算，

该标量乘法程序为了使所述电子计算机进行上述运算，具有：将对所述标量s进行v进制展开而得到的所述s₁储存在第1寄存器并且将所述s₂储存在第2寄存器的步骤；将对(-2χ-1)s₁进行v进制展开而得到的所述s₃储存在第3寄存器并且将所述s₄储存在第4寄存器的步骤；以及将(-2χ-1)s₃的值作为所述s₅的值储存在第5寄存器的步骤。

发明效果

根据本发明，在运算标量乘法[s]P时，通过对标量s进行v进制展开使标量s的大小变小，并且使用满足

的弗罗贝尼乌斯映射φ'₂(P)，从而能使标量乘法[s]P的运算量大致减半，能使标量乘法高速化。

附图说明

图1是具备本发明的实施方式的标量乘法器的电子计算机的概略示意图。

图2是本发明的实施方式的标量乘法程序的流程图。

附图标记的说明

10 电子计算机；

11 CPU；

12 存储装置；

13 存储器装置；

14 总线；

110 标量值用寄存器；

111 第1寄存器；

112 第2寄存器；

113 第3寄存器；

114 第4寄存器；

115 第5寄存器5。

具体实施方式

在说明本发明的实施方式时，首先针对嵌入次数k=12的情况进行说明，之后，针对嵌入次数k=8的情况进行说明。

在本实施方式的标量乘法器及标量乘法程序中执行的标量乘法，是在嵌入次数k=12的情况下，特征p、阶数r、弗罗贝尼乌斯自同态映射的迹t是作为

赋予的椭圆曲线的有理点形成的加法群E(F_p)的有理点P的标量乘法[s]P。该椭圆曲线作为配对友好曲线（pairing friendly curves）的一种已知是Barreto-Naehrig曲线（以下，称为“BN曲线”）。

对于以该BN曲线表示的椭圆曲线，已知存在子域扭转（twist）曲线。特别在嵌入次数k=12的情况下，已知6次扭转曲线，已知

的费罗贝尼乌斯映射φ'₂。

利用通过使用该费罗贝尼乌斯映射φ'₂能使标量运算高速化的特性，并且在本发明中，利用在以下说明的关系式使标量运算高速化。

首先，通过式2能得到下式。

此外，因为p≡t-1 mod r，所以能得到下式。

在此，通过对式5进行变形能得到下式。

在此，通过对式6的两边进行平方能得到下式。

进而，通过利用p⁴+1≡p² mod r对式7进行变形，能得到下式。

然后，在式8的两边乘以(p²-1)^-1时，因为

所以

因此利用

，能对式8以下式的方式进行变形。

因此，通过对式12进行变形能得到下式。

由此，能得到下式的费罗贝尼乌斯映射φ'₂的关系式。

接着，考虑使用了费罗贝尼乌斯映射φ'₂的标量乘法[s]P。在此，为方便起见，设为下式。

在该情况下，标量s的v进制展开能以下式的方式进行表示。

在此，式16利用式15和式14，能以下式的方式进行表示。

再有，存在(-2χ+1)s₁比ν大的情况。因此，对(-2χ+1)s₁进一步进行ν进制展开并以下式的方式进行表示。

在此，因为利用式14有s₃νp²≡(-2χ+1)s₃p⁴，所以通过令(-2χ+1)s₃=s₅，式18能以下式的方式进行表示。

在该情况下，s₄和s₂比ν小，另一方面s₅可能不比ν小，但在这样的情况下也不变的那么大，不会成为问题。

因为利用式9有p⁴≡p²-1 mod r，所以式19能以下式的方式进行变形。

在此，当设为

时，标量乘法[s]P能作为

来进行运算。

因此，例如，在运算对256位大小的标量s的标量乘法时，由于A及B为128位大小，所以使运算量大致减半从而能使标量乘法高速化。

进行上述的标量乘法的标量乘法器如图1所示是以电子计算机10构成的，具备：CPU11，执行运算处理；硬盘等的存储装置12，对标量乘法程序以及在标量乘法程序中使用的有理点的数据等进行存储；以及存储器装置13，由能对标量乘法程序进行展开执行并且对伴随着标量乘法程序的执行而生成的数据进行暂时存储的RAM等构成。在图1中，14是总线。

在本实施方式中，在CPU11内作为存储单元设置对标量s的值进行存储的标量值用寄存器110。进而，在CPU11内作为第1～5辅助存储单元设置有分别对以上述方式伴随着标量s的v进制展开而生成的系数s₁、s₂、s₃、s₄、s₅的值进行存储的第1～5寄存器111、112、113、114、115。再有，以标量值用寄存器110构成的存储单元、以及以第1～5寄存器111、112、113、114、115构成的第1～5辅助存储单元不在CPU11内设置，而在存储器装置13等的CPU11以外的存储单元设置也可。

在作为标量乘法器而发挥作用的电子计算机10中，在需要标量乘法的执行的情况下起动标量乘法程序，执行标量乘法。

即，在电子计算机10中，通过起动了的标量乘法程序，基于在图2中示出的流程图来进行标量乘法，输出运算结果。

通过起动了的标量乘法程序，在电子计算机10中，使CPU11作为输入单元而发挥作用，读出在存储装置12或存储器装置13中存储的整数变量χ的数据和有理点P的数据，分别向设置在CPU11内部的规定的寄存器输入（步骤S1）。

进而，在电子计算机10中，通过标量乘法程序使CPU11作为输入单元而发挥作用，输入在标量乘法中的标量s的值。而且，使CPU11作为存储单元而发挥作用，将输入的标量s的值存储在标量值用寄存器110（步骤S2）。

接着，在电子计算机10中，通过标量乘法程序使CPU11作为运算单元而发挥作用，以上述方式对标量s进行v进制展开，计算出作为v进制展开的系数的s₁和s₂（步骤S3）。即，系数s₁是在标量s除以v时的商，系数s₂是在标量s除以v时的余数。

使CPU11作为存储单元而发挥作用，计算出的作为v进制展开的系数s₁和s₂的值分别储存在第1寄存器111及第2寄存器112，使其存储（步骤S4）。

接着，在电子计算机10中，使CPU11作为运算单元而发挥作用，对(-2χ+1)s₁的值进行运算（步骤S5）,以上述方式对(-2χ+1)s₁进行v进制展开，计算出作为v进制展开的系数的s₃和s₄（步骤S6）。即，系数s₃是在(-2χ+1)s₁除以v时的商，系数s₄是在(-2χ+1)s₁除以v时的余数。

使CPU11作为存储单元而发挥作用，计算出的作为(-2χ+1)s₁的v进制展开的系数s₃和s₄的值分别储存在第3寄存器113及第4寄存器114，使其存储（步骤S7）。

接着，在电子计算机10中，使CPU11作为运算单元而发挥作用，对(-2χ+1)s₃的值进行运算（步骤S8），将该值分别储存在第5寄存器115，使其存储（步骤S9）。

接着，在电子计算机10中，使CPU11作为运算单元而发挥作用，使用存储在第1～5寄存器111、112、113、114、115的值，对s₄+s₅的值及s₂-s₅的值进行运算（步骤S10）。

将运算出的s₄+s₅的值及s₂-s₅的值分别储存在规定的寄存器中，使其存储。为了说明的方便，令s₄+s₅=A、s₂-s₅=B。

接着，在电子计算机10中，使CPU11作为运算单元而发挥作用，将标量乘法[s]P设为[s]P=([A]φ'₂+[B])P来进行运算（步骤S11）。在此，通过A以及B的值的大小变为标量s的大小的一半左右，能大大消减运算时间。在计算机仿真中，和以通常的二进制法的标量乘法进行比较，能实现40%左右的高速化。

再有，在步骤S11进行的[s]P=([A]φ'₂+[B])P的运算具体地如以下那样进行。

在此，在电子计算机10中设置有：运算结果用寄存器R，对标量运算[s]P的运算结果进行存储；以及第1辅助寄存器C和第2辅助寄存器D，对运算所需要的值暂时进行存储。

首先，电子计算机10作为初始化处理，将运算结果用寄存器R设为零元，对第1辅助寄存器C带入φ'₂(P)，对第2辅助寄存器D带入有理点P。

此外，将在对上述A和B分别进行2进制显示时的第i位的值显示成A_i和B_i，在电子计算机10中，在A和B的全部位执行以下的运算循环。

在第i位中，在A_i=1且B_i=1的情况下，对运算结果用寄存器R代入运算结果用寄存器R和第2辅助寄存器D之和。即，R←R+D。

在第i位中，在A_i=1且B_i=0的情况下，对运算结果用寄存器R代入运算结果用寄存器R和第1辅助寄存器C之和。即，R←R+C。

在第i位中，在A_i=0且B_i=1的情况下，对运算结果用寄存器R代入运算结果用寄存器R和有理点P之和。即，R←R+P。

而且，对运算结果用寄存器R代入运算结果用寄存器R和运算结果用寄存器R之和。即，R←R+R。

之后，电子计算机10通过进行递减或递增，一边移动A_i和B_i的位一边在A和B的全部位进行运算，从而进行标量运算[s]P的运算，能输出运算结果。

在本实施方式的运算中，通过对A和B同时进行运算，从而能最大限度利用A和B的值的大小变为标量s大小的一半左右的优点。

接着，针对嵌入次数k=8的情况进行说明。

采用在嵌入次数k=8的情况下，在特征p、阶数r、弗罗贝尼乌斯自同态映射的迹t作为

来赋予的BN曲线的有理点形成的加法群E(F_p)的有理点P的标量乘法[s]P。

在该情况下，也已知子域扭转曲线存在。特别地，在嵌入次数k=8的情况下，已知4次扭转曲线，已知

的费罗贝尼乌斯映射φ'₂。

此外，在嵌入次数k=8的情况下，代替上述的式14，而利用

的关系式。

而且，和嵌入次数k=12的情况同样地，当令3χ²+2χ=ν对所述标量s进行v进制展开时，能以下式的方式进行表示。

在此，根据式24，式25能以下式的方式进行表示。

再有，存在(-2χ-1)s₁比ν大的情况。因此，对(-2χ-1)s₁进一步进行ν进制展开并以下式的方式进行表示。

在此，因为根据式24是s₃νp²≡(-2χ-1)s₃p⁴，所以令(-2χ-1)s₃=s₅，由此式27能以下式的方式进行表示。

在该情况下，s₄和s₂比ν小，另一方面s₅可能不比ν小，但在这样的情况下也不变的那么大，不会成为问题。

在嵌入次数k=8的情况下，因为p⁴≡-1 mod r，所以式28能以下式的方式进行变形。

在此，当设为

时，标量乘法[s]P和嵌入次数k=12的情况同样地，能作为

来进行运算。

因此，在嵌入次数k=8的情况下，与嵌入次数k=12的情况相比较，仅储存在第5寄存器115的值的计算式以及式30的A的值不同，能和嵌入次数k=12的情况同样地进行运算。

因此，设在嵌入次数k=8的情况下的标量运算器和在嵌入次数k=12的情况下的标量运算器相同，将在图2中示出的流程图的步骤S8中的计算式设为(-2χ-1)s₃，在步骤S9中将s₅的值设为(-2χ-1)s₃，在步骤10令A=s₄。

由此，在嵌入次数k=8的情况下，通过A以及B的值的大小变为标量s的大小的一半左右，从而也能大大削减标量乘法[s]P的运算时间。

产业上的利用可能性

根据本发明，能使在群签名的运算中需要的标量运算的速度提高，谋求群签名处理的高速化。