运算装置、运算装置的椭圆标量乘法方法、椭圆标量乘法程序、运算装置的剩余运算方法、剩余运算程序、运算装置的零判定方法以及零判定程序

摘要

不管随机数k的值如何都能够在恒定的计算时间内处理椭圆标量乘法kG，防止椭圆标量乘法kG的定时解析。初始设定部121对标量乘法变量R设定椭圆曲线上的特定点G。标量乘法部122针对表示随机数k的t比特的比特串从上位逐个比特进行参照，每当参照一个比特时，对作业变量R[0]设定对标量乘法变量R进行2倍乘法而得到的值，对作业变量R[1]设定对作业变量R[0]设定的值加上特定点G而得到的值。然后，在标量乘法部122中，如果所参照的比特的值是0，则对标量乘法变量R设定作业变量R[0]，如果所参照的比特的值是1，则对标量乘法变量R设定作业变量R[1]。标量倍点输出部123从标量乘法变量R减去常数值2

说明书

技术领域

本发明涉及用于生成例如椭圆曲线密码的电子签名的运算装置、 运算装置的椭圆标量乘法方法、椭圆标量乘法程序、运算装置的剩余 运算方法、剩余运算程序、运算装置的零判定方法以及零判定程序。

背景技术

存在为了对电子数据的制作者进行证明而使用电子签名的技术。

电子签名是使用电子数据、秘密密钥以及随机数通过特定的签名 生成算法而制作的。电子签名与电子数据一起通信。

电子数据的接收者使用所接收到的电子数据、所接收到的电子签 名、以及签名者的公开密钥通过特定的签名验证算法验证电子数据。 即，电子数据的接收者判定是否使用与公开密钥对应的秘密密钥生成 了所接收到的电子签名。然后，如果使用与公开密钥对应的秘密密钥 生成了所接收到的电子签名，则证明由秘密密钥的持有者（签名者） 制作了所接收到的电子数据。

因此，在他人得知了秘密密钥的情况下，存在伪造电子签名、冒 充秘密密钥的持有者而对电子数据进行通信的危险。

另外，在他人得知了在电子签名的生成时使用的随机数的情况 下，根据电子签名和随机数来确定秘密密钥。

因此，与得知了秘密密钥的情况同样地，伪造电子签名，冒充秘 密密钥的持有者而对电子数据进行通信。

进而，存在通过对用于生成电子签名的运算处理的处理时间进行 定时解析而能够求出在运算处理中使用的数值（例如，秘密密钥、随 机数）的可能性（参照非专利文献1）。

例如，在EC－Schnorr、ECDSA等的椭圆曲线密码的签名生成 算法（以及签名验证算法）中，进行以随机数k对椭圆曲线上的点G 进行标量倍运算的椭圆标量乘法kG。椭圆曲线密码的签名生成算法 （以及签名验证算法）被记载于非专利文献2。

以往的椭圆标量乘法kG如下所述。

[式1]

步骤1.R=G;

步骤2.设为i=t-1，直到i=0为止，反复步骤2-1至步骤2-4。

步骤2-1.R[0]=2R;

步骤2-2.R[1]=R[0]+G;

步骤2-3.R=R[k[i]];

步骤2-4.i--;

步骤3.Return（返回）R;

其中，t：k的比特数

k[i]:从下位起第i比特的k的比特值

R[k[i]]:如果k[i]为0，则为R[0]，如果k[i]为1，则为R[1]。

将上述计算方法称为Add－Double－Always法。

在Add－Double－Always法中必须k[t]=1，所以随机数k的比 特数t根据随机数k的值而变化。例如，在用32比特来表示了随机数 k的情况下，最上位比特是1的随机数k的比特数t是“32”，但上位 12比特是0的随机数k的比特数t变化为“20（=32－12）”。

即，由于随机数k的值而在计算时间中产生差，存在通过定时解 析来确定随机数k的可能性。

以下，示出将Add－Double－Always法变形而得到的椭圆标量 乘法kG。

[式2]

步骤1.R=0;

步骤2.设i=t，直至成为i=0为止，反复步骤2－1至步骤2－4。

步骤2－1.R[0]=2R;

步骤2－2.R[1]=R[0]=G;

步骤2－3.R=R[k[i]];

步骤2－4.i--;

步骤3.Return（返回）R;

在上述计算方法中即使并非k[t]=1也可以，所以随机数k的比特 数t是固定值，而不根据随机数k的值发生变化。

其中，在步骤2－1中，在随机数k的最上位比特是1的情况下， 无穷远点的变量R（R=0）的2倍乘法仅进行1次，在随机数k的上 位的多个比特是0的情况下，无穷远点的变量R的2倍乘法反复多次。 另外，在无穷远点的变量R的2倍乘法和非无穷远点的变量R的2倍 乘法中，计算时间不同。

因此，由于随机数k的值而在计算时间中产生差，有可能通过定 时解析确定随机数k。

另外，在椭圆曲线密码的签名生成算法（以及签名验证算法）中， 需要进行多精度运算处理。

以下，示出在多精度运算处理中进行的剩余运算“a/2mod p”。a 表示多精度整数，p表示素数，mod表示剩余算子。

[式3]

步骤1.如果a是偶数，c=a>>1；

步骤2.否则c=a+p;c=c>>1;

步骤3.Return（返回）c;

其中，

x>>1：使x的比特串向右移位1比特。

在上述剩余运算中，在a是偶数的情况下，进行1次移位运算， 在a是奇数的情况下，将移位运算和加法各进行1次。

即，由于a的值而在计算时间中产生差，有可能通过定时解析来 确定a，根据a来确定随机数k。

以下，示出在多精度运算处理中进行的零判定运算。在零判定运 算中，判定多精度整数b的值是否为零。多精度整数b被表示为连结 多个字（word）（整数值）而得到的值。

[式4]

处理：从b的最上位字依次判定字是否为零。

条件1：如果字是非零，则判定为b是非零而结束。

条件2：如果所有字是零，则判定为b是零而结束。

在上述零判定运算中，非零的字的位置越是上位，计算时间越短。

即，由于b的值而在计算时间中产生差，有可能通过定时解析来 确定随机数k。

非专利文献1：Jean－Sebastien Coron：Resistance against  Differential Power Analysis for Elliptic Curve Cryptosystems.CHES 1999：292－302

非专利文献2：ISO/IEC JTC1/SC27

发明内容

本发明的目的在于通过不管在运算处理中使用的数值的差异如 何都在恒定的计算时间内处理用于生成例如电子签名的运算处理，从 而防止定时解析。

本发明的运算装置计算对特定的椭圆曲线所包含的特定点的坐 标值G通过用t比特的比特串来表示的特定的乘数值k进行标量乘法 而得到的坐标值kG。

所述运算装置具备：

常数存储部，预先存储对所述特定点的坐标值G通过2的t次幂 进行标量倍运算而得到的坐标值2^tG；

初始设定部，对规定的标量乘法变量R设定所述特定点的坐标值 G；

标量乘法部，针对表示所述乘数值k的t比特的比特串从上位逐 次参照各规定数的比特，每当针对所述比特串逐次参照各规定数的比 特时，对规定的第0作业变量R[0]设定对所述标量乘法变量R进行2 倍乘法而得到的坐标值，对规定的第1作业变量R[1]设定对所述第0 作业变量R[0]设定的值加上对所述特定点的坐标值G进行规定倍运算 的坐标值而得到的坐标值，如果所参照的规定数的比特的值是零，则 对所述标量乘法变量R设定所述第0作业变量R[0]，如果所参照的规 定数的比特的值是非零，则对所述标量乘法变量R设定所述第1作业 变量R[1]；以及

标量倍点输出部，从由所述标量乘法部设定的标量乘法变量R减 去所述常数存储部所存储的坐标值2^tG，将进行减法而得到的坐标值 作为所述坐标值kG而输出。

根据本发明，不管随机数k（乘数值）的值如何都能够在恒定的 计算时间内处理椭圆标量乘法kG，防止椭圆标量乘法kG的定时解析。

附图说明

图1是实施方式1中的椭圆曲线密码装置100的结构图。

图2是示出实施方式1中的电子签名生成方法（EC－Schnorr 方式）的流程图。

图3是示出实施方式1中的电子签名生成方法（ECDSA方式） 的流程图。

图4是示出实施方式1中的椭圆标量乘法方法的流程图。

图5是示出实施方式1中的椭圆标量乘法方法的其他例子的流程 图。

图6是示出实施方式1中的椭圆曲线密码装置100的硬件资源的 一个例子的图。

图7是实施方式2中的椭圆曲线密码装置100的结构图。

图8是示出实施方式2中的多精度剩余运算方法的流程图。

图9是实施方式3中的椭圆曲线密码装置100的结构图。

图10是示出实施方式3中的多精度零判定方法的流程图。

（符号说明）

100：椭圆曲线密码装置；110：电子签名生成部；111：随机数 生成部；112：签名生成处理部；120：椭圆标量乘法部；121：初始设 定部；122：标量乘法部；123：标量倍点输出部；130：多精度剩余运 算部；131：多精度整数判定部；132：剩余运算变量设定部；133：移 位运算部；140：多精度零判定部；141：“或”运算部；142：零判定 部；190：装置存储部；901：CPU；902：总线；903：ROM；904： RAM。

具体实施方式

实施方式1.

说明使用椭圆曲线密码方式来生成电子签名的椭圆曲线密码装 置。

其中，电子签名的生成是使用了椭圆曲线密码方式的密码处理的 一个例子。

图1是实施方式1中的椭圆曲线密码装置100的结构图。

根据图1，说明实施方式1中的椭圆曲线密码装置100的结构。

椭圆曲线密码装置100（运算装置）具备电子签名生成部110、 椭圆标量乘法部120、以及装置存储部190。

电子签名生成部110执行EC－Schnorr、ECDSA等的利用了椭 圆曲线密码的签名生成算法（参照专利文献2），生成电子签名。

电子签名生成部110具备随机数生成部111和签名生成处理部 112。

随机数生成部111通过规定的随机数生成处理生成（计算）随机 数k。

随机数k是用t比特的比特串来表示的值。

签名生成处理部112使用由椭圆标量乘法部120计算的坐标值 kG来生成电子签名。

椭圆标量乘法部120计算针对特定的椭圆曲线所包含的特定点的 坐标值G用由随机数生成部111生成的随机数k（乘数值）进行标量 乘法而得到的坐标值kG。

椭圆标量乘法部120具备初始设定部121、标量乘法部122以及 标量倍点输出部123。

初始设定部121对规定的标量乘法变量R设定特定点的坐标值 G。

标量乘法部122针对表示随机数k的t比特的比特串从上位逐次 参照各规定数的比特（1比特或者多个比特）。

在标量乘法部122中，每当针对比特串逐次参照各规定数的比特 时，对规定的第0作业变量R[0]设定对标量乘法变量R进行2倍乘法 而得到的坐标值。

标量乘法部122对规定的第1作业变量R[1]设定如下坐标值，该 坐标值是对在第0作业变量R[0]设定的值加上对特定点的坐标值G进 行规定数倍（1倍或者多倍）而得到的坐标值而得到的值。

在标量乘法部122中，如果所参照的规定数的比特的值是零，则 对标量乘法变量R设定第0作业变量R[0]，如果所参照的规定数的比 特的值是非零，则对标量乘法变量R设定第1作业变量R[1]。

标量倍点输出部123从由标量乘法部122设定的标量乘法变量R 减去坐标值2^tG，将进行减法而得到的坐标值作为坐标值kG进行输 出。

坐标值2^tG是对特定点的坐标值G以2的t次幂进行标量倍运算 而得到的值。

装置存储部190存储在椭圆曲线密码装置100中使用的各种数 据。

特定点的坐标值G、特定点的坐标值G的位数n、秘密密钥d、 坐标值2^tG、消息M、随机数k、电子签名是装置存储部190中存储 的数据的一个例子。

特定点的坐标值G、特定点的坐标值G的位数n以及秘密密钥d 被预先存储于装置存储部190。特定点的坐标值G还被称为“椭圆曲线 正弦值”。

关于坐标值2^tG，根据特定点的坐标值G预先计算并存储到装置 存储部190。

消息M被输入到椭圆曲线密码装置100而存储到装置存储部 190，随机数k是由随机数生成部111计算而存储到装置存储部190， 电子签名是由签名生成处理部112生成而存储到装置存储部190。

以下，将特定点的坐标值G记载为“特定点G”，将坐标值2^tG记 载为“常数值2^tG”，将坐标值kG记载为“标量倍点kG”。

图2是示出实施方式1中的电子签名生成方法（EC－Schnorr 方式）的流程图。

根据图2，说明利用EC－Schnorr方式的电子签名生成方法。

电子签名生成部110从装置存储部190输入特定点G、特定点G 的位数n、秘密密钥d以及消息M，使用特定点G、特定点G的位数 n以及秘密密钥d，如以下那样生成（计算）与消息M对应的电子签 名（e，s）。

在S111A中，随机数生成部111执行规定的随机数生成处理， 生成（计算）随机数k。其中，随机数k是小于特定点G的位数n的 自然数。

在S111A之后，进入S112A。

在S112A中，签名生成处理部112将在S111A中生成的随机数 k和从装置存储部190输入的特定点G输入到椭圆标量乘法部120。

然后，签名生成处理部112将由椭圆标量乘法部120计算出的标 量倍点kG设定为规定的变量P。以下，将变量P称为“标量倍点P”。

将由椭圆标量乘法部120执行的标量倍点kG的计算方法作为 “椭圆标量乘法方法”而另外说明。

在S112A之后，进入S113A。

在S113A中，签名生成处理部112将结合了消息M和标量倍点 P的x坐标值Px而得到的消息M’（=M||Px）作为输入值而计算规定 的散列函数h，计算散列值e。

在实施方式中，“A||B”意味着A和B的连结，“h（C）”意味着 用于计算输入值C的散列值的散列函数。

在S113A之后，进入S114A。

在S114A中，签名生成处理部112计算（d×e+k）除以特定点G 的位数n而得到的余数。以下，将在S114中计算出的余数记载为“剩 余值s”。

在实施方式中，“A mod B”意味着求出A除以B而得到的余数的 运算。

签名生成处理部112将在S113A中计算出的散列值e和在S114A 中计算出的剩余值s的组合（e，s）作为消息M的电子签名而输出。

通过S114A，利用EC－Schnorr方式的电子签名生成处理结束。

图3是示出实施方式1中的电子签名生成方法（ECDSA方式） 的流程图。

电子签名生成部110也可以通过图3所示那样的ECDSA方式生 成电子签名。

电子签名生成部110从装置存储部190输入特定点G、特定点G 的位数n、秘密密钥d以及消息M，使用特定点G、特定点G的位数 n以及秘密密钥d，如以下那样生成（计算）与消息M对应的电子签 名（Px，s）。

在S111B中，随机数生成部111执行规定的随机数生成处理，生 成（计算）随机数k。

在S111B之后，进入S112B。

在S112B中，签名生成处理部112将在S111B中生成的随机数k 和从装置存储部190输入的特定点G输入到椭圆标量乘法部120。

然后，签名生成处理部112将由椭圆标量乘法部120计算出的标 量倍点kG设定为规定的变量P（标量倍点P）。

将由椭圆标量乘法部120执行的标量倍点kG的计算方法作为 “椭圆标量乘法方法”而另外说明。

在S112B之后，进入S113B。

在S113B中，签名生成处理部112计算剩余值s，将标量倍点P 的x坐标值Px和剩余值s的组合（Px，s）作为消息M的电子签名而 输出。

剩余值s的计算式能够通过“s=k^－1×（h（M）+Px×d）mod n” 来表示。

通过S113B，利用ECDSA方式的电子签名生成处理结束。

EC－Schnorr方式（图2）以及ECDSA方式（图3）的详细内 容记载于非专利文献2。

图4是示出实施方式1中的椭圆标量乘法方法的流程图。

根据图4，说明实施方式1中的椭圆标量乘法方法。

椭圆标量乘法部120从电子签名生成部110输入随机数k和特定 点G，从装置存储部190输入常数值2^tG，如以下那样计算标量倍点 kG。

在S121A中，初始设定部121对规定的变量R设定特定点G。 以下，将变量R称为“标量乘法变量R”。

在S121A之后，进入S122A。

在S122A中，标量乘法部122对规定的变量i设定表示随机数k 的比特串的比特数t。以下，将变量i称为“循环变量i”。

例如，在表示随机数k的值的变量（比特串）是32比特的变量 的情况下，标量乘法部122对循环变量i设定“32”。

以下，将从表示随机数k的比特串的下位起第i比特的值（比特 值）记载为“k[i]”。

即，随机数k的最上位比特的比特值是“k[t]”，随机数k的最下 位比特的比特值是“k[1]”。最上位比特是最左的比特且表示2的t次 幂的比特。最下位比特是最右的比特且表示2的0次幂的比特。

随机数k的最上位比特的比特值k[t]可以是“0”和“1”中的任意一 个。

在S122A之后，进入S123A。

在S123A中，标量乘法部122对标量乘法变量R进行2倍运算， 对规定的变量R[0]设定所得到的值“2R”。以下，将变量R[0]称为“第 0作业变量R[0]”。

在S123A之后，进入S124A。

在S124A中，标量乘法部122对在第0作业变量R[0]设定的值 加上特定点G，将所得到的值设定给规定的变量R[1]。以下，将变量 [1]称为“第1作业变量R[1]”。

在S124A之后，进入S125A。

在S125A中，标量乘法部122根据循环变量i参照从随机数k的 下位起第i比特的比特值k[i]。

例如，如果“i=t”，则标量乘法部122参照随机数k的最上位比特 k[t]，如果“i=1”，则标量乘法部122参照随机数k的最下位比特k[1]。

在比特值k[i]是“0”的情况下，标量乘法部122对标量乘法变量R 设定第0作业变量R[0]。

在比特值k[i]是“1”的情况下，标量乘法部122对标量乘法变量R 设定第1作业变量R[1]。

在S125A之后，进入S126A。

在S126A中，标量乘法部122从循环变量i减去“1”。

在S126A之后，进入S127A。

在S127A中，标量乘法部122判定循环变量i是否为“0”。

在循环变量i是“0”的情况下，进入S128A。

在循环变量i非“0”的情况下，返回到S123A。

但是，关于S127A的判定，也可以并非S126A之后进行而在 S123A之前进行，在S126A之后返回到S127A。在该情况下，在S127A 中如果循环变量i是“0”则进入S128A，如果循环变量i非“0”则进入 S123A。

在S128A中，标量倍点输出部123从标量乘法变量R减去常数 值2^tG，将所得到的标量乘法变量R的值作为标量倍点kG输出到电 子签名生成部110。

通过S128A，椭圆标量乘法处理结束。

在上述椭圆标量乘法处理（图4）中，对标量乘法变量R作为初 始值设定特定点G而非无穷远点“0”（S121A），最后从标量乘法变 量R减去与初始值对应的常数值2^tG（S128A）。

由此，能够不管随机数k的值如何都在恒定的计算时间内计算标 量倍点kG。例如，不论是在随机数k的最上位比特是“1”的情况下还 是在从随机数k的最上位比特起连续多个比特是“0”的情况下，标量倍 点kG的计算所需的计算时间都不变。

即，关于椭圆标量乘法处理，由于不管随机数k的值如何都在恒 定的计算时间内进行，所以椭圆标量乘法处理不会被定时解析。所谓 定时解析是指，通过分析处理时间的时间差来确定所处理的数据的技 术。关于定时解析，记载于非专利文献1。

因此，关于在椭圆标量乘法处理中使用的随机数k，不会通过定 时解析来确定，也不会根据随机数k而得知电子签名。

图5是示出实施方式1中的椭圆标量乘法方法的其他例子的流程 图。

椭圆标量乘法部120也可以通过图5所示的方法计算标量倍点 kG。

椭圆标量乘法部120从电子签名生成部110输入随机数k和特定 点G，从装置存储部190输入常数值2^tG，如以下那样计算标量倍点 kG。

在S121B中，初始设定部121对标量乘法变量R设定特定点G。

在S121B之后，进入S122B。

在S122B中，标量乘法部122对循环变量i设定表示随机数k的 比特串的比特数t。

在S122B之后，进入S123B。

在S123B中，标量乘法部122对标量乘法变量R进行2倍运算。

在S123B之后，进入S124B。

在S124B中，标量乘法部122根据循环变量i参照从随机数k的 下位起第i比特的比特值k[i]，判定所参照的比特值k[i]是“0”和“1” 中的哪一个值。

在比特值k[i]是“0”的情况下，进入S125B。

在比特值k[i]是“1”的情况下，进入S126B。

在S125B中，标量乘法部122对标量乘法变量R加上特定点G。

在S125B之后，进入S126B。

在S126B中，标量乘法部122从循环变量i减去“1”。

在S126B之后，进入S127B。

在S127B中，标量乘法部122判定循环变量i是否为“0”。

在循环变量i是“0”的情况下，进入S128B。

在循环变量i非“0”的情况下，返回到S123B。

但是，关于S127B的判定，也可以不是在S126B之后进行而是 在S123B之前进行，在S126B之后返回到S127B。在该情况下，在 S127B中，如果循环变量i是“0”，则进入S128B，如果循环变量i非“0”， 则进入S123B。

在S128B中，标量倍点输出部123从标量乘法变量R减去常数 值2^tG，将所得到的标量乘法变量R的值作为标量倍点kG输出到电 子签名生成部110。

通过S128B，椭圆标量乘法处理结束。

在上述椭圆标量乘法处理（图5）中，在S123B中进行了标量乘 法变量R的2倍乘法（2R），但在无穷远点“0”的2倍乘法和无穷远 点“0”以外的值的2倍乘法中，在计算时间中产生差。

但是，在S121B中，对标量乘法变量R初始设定了特定点G而 并非无穷远点“0”，所以即使在从随机数k的最上位比特起连续多个比 特是“0”的情况下，在S123B中也不会对无穷远点“0”进行2倍乘法。 即，不会由于随机数k的值而在S123B的计算时间中产生差。

因此，与不会由于随机数k的值而在S123B的计算时间中产生 差相应地，能够使椭圆标量乘法处理的定时解析变得困难。

图6是示出实施方式1中的椭圆曲线密码装置100的硬件资源的 一个例子的图。

在图6中，椭圆曲线密码装置100具备CPU901（Central  Processing Unit，中央处理单元）。CPU901经由总线902而与ROM903 和RAM904连接，控制这些硬件设备。

在ROM903或者RAM904中，存储了OS（操作系统）、程序 群、文件群。

在程序群中，包括执行在实施方式中说明为“～部”的功能的程序。 程序由CPU901读出并执行。即，程序使计算机作为“～部”发挥功能， 并且使计算机执行“～部”的步骤、方法。

在文件群中，包括在实施方式中说明的“～部”中使用的各种数据 （输入、输出、判定结果、计算结果、处理结果等）。

在实施方式中，结构图以及流程图中包含的箭头主要表示数据、 信号的输入输出。

在实施方式中说明为“～部”的部分既可以是“～电路”、“～装置”、“～ 设备”，并且也可以是“～步骤”、“～阶段”、“～处理”。即，说明为“～部” 的部分也可以通过固件、软件、硬件或者它们的组合中的某个来实现。

例如，椭圆曲线密码装置100构成为IC芯片，被搭载于具有电 子结算功能的便携终端或者IC卡。在IC芯片中预先存储个人信息。

在便携终端或者IC卡使用电子结算功能时，椭圆曲线密码装置 100生成个人信息的电子签名。然后，便携终端或者IC卡的无线通信 功能将个人信息和电子签名发送到规定的电子结算装置。电子结算装 置验证电子签名，根据个人信息进行电子结算。

另外，在由个人计算机、服务器装置等计算机构成椭圆曲线密码 装置100的情况下，椭圆曲线密码装置100除了ROM903、RAM904 以外，还具备通信板、显示器装置、键盘、鼠标、驱动器装置、磁盘 装置等硬件。CPU901还控制这些硬件。

在实施方式1中，椭圆曲线密码装置100也可以不是生成电子签 名的密码装置，椭圆标量乘法处理（图4、5）也可以通过生成电子签 名的处理以外的运算处理来执行。

即，实施方式1中的椭圆标量乘法处理（图4、5）也可以用于使 用椭圆标量倍点kG（k也可以不是随机数）的任意的运算处理。

图4或者图5所示的椭圆标量乘法处理是被称为二进制法的幂乘 剩余运算法，但作为椭圆标量乘法处理也可以使用其他幂乘剩余运算 法（例如，Comb法）。在使用Comb法的情况下，通过在图4、图5 中关于k[i]并非参照1比特而是同时参照多个比特，能够使循环次数 小于t。

即使在使用其他幂乘剩余运算法的情况下，只要对标量乘法变量 R作为初始值设定特定点G（参照图4的S121A），最后从标量乘法 变量R减去常数值2^tG即可。由此，不管随机数k的值如何都能够在 恒定的计算时间内计算标量倍点kG。

实施方式2.

说明在恒定的计算时间内进行多精度整数的剩余运算的方式。

多精度整数的剩余运算是指，将多精度整数除以特定值来计算余 数的处理。

以下，主要说明与实施方式1不同的事项。关于省略说明的事项， 与实施方式1相同。

图7是实施方式2中的椭圆曲线密码装置100的结构图。

根据图7，说明实施方式2中的椭圆曲线密码装置100的结构。

椭圆曲线密码装置100除了在实施方式1中说明的结构以外，还 具备多精度剩余运算部130。

多精度剩余运算部130将特定的多精度整数a除以2，将由此得 到的值除以特定的素数p，将由此得到的余数计算为剩余值r。

多精度剩余运算部130具备多精度整数判定部131、剩余运算变 量设定部132、以及移位运算部133。

在多精度整数判定部131中，如果多精度整数a是偶数，则对规 定的临时变量temp设定0，如果多精度整数a是奇数，则对临时变量 temp设定素数p。

剩余运算变量设定部132对多精度整数a加上临时变量temp， 对规定的剩余运算变量c设定进行加法而得到的值。

移位运算部133使剩余运算变量c向右移位1比特，将移位而得 到的值作为剩余值r输出。

椭圆标量乘法部120的初始设定部121对标量乘法变量R设定表 示特定点的坐标值G的多精度整数（图4的S121A）。

标量乘法部122使用多精度剩余运算部130，计算对标量乘法变 量R进行2倍乘法而得到的坐标值“2R”（图4的S123A）。

标量乘法部122使用多精度剩余运算部130，计算对第0作业变 量R[0]加上特定点的坐标值G而得到的坐标值“R[0]+G”（图4的 S124A）。

标量倍点输出部123使用多精度剩余运算部130，计算从标量乘 法变量R减去坐标值2^tG而得到的坐标值“R－2^tG”（图4的S128A）。

以下，将特定点的坐标值G记载为“特定点G”，将坐标值2^tG记 载为“常数值2^tG”。

图8是示出实施方式2中的多精度剩余运算方法的流程图。

参照图8，说明实施方式2中的多精度剩余运算方法。

在电子签名的生成、验证等密码处理或者其他密码处理中，为了 使密码的解读变得困难，使用多精度整数，进行使用了多精度整数的 运算处理。

多精度整数是指，比能够通过与寄存器的数据尺寸相当的规定的 比特数来表示的最大的整数值大的整数值。例如，在32比特机器中比 能够用32比特表示的最大的整数值（2的32次幂－1）大的整数值是 多精度整数。

以下，将使用了多精度整数的运算处理称为“多精度运算处理”。

通常，在多精度运算处理中，进行多精度剩余运算。

多精度剩余运算是指，将多精度整数（后述a）除以特定值（后 述p）而求出余数（后述r）的处理。

在实施方式1中说明的椭圆曲线上的特定点G的坐标值是多精 度整数的一个例子。

例如，椭圆标量乘法部120在S123A、S124A以及S128A（参照 图4）中调出多精度剩余运算部130，多精度剩余运算部130执行图8 所示的多精度剩余运算。

以下，将计算对象的多精度整数设为“a”，将“a/2”除以的值设 为“p”，将把“a/2”除以“p”而得到的余数设为“剩余值r”。“a/2”是将多 精度整数a除以2而得到的值。“p”是素数。剩余值r是0以上且小于 p的整数值。

在S131中，多精度整数判定部131判定多精度整数a是偶数和 奇数中的哪一个值。

在多精度整数a是偶数的情况下，进入S132。

在多精度整数a是奇数的情况下，进入S133。

在S132中，多精度整数判定部131对规定的变量temp设定“0”。 以下，将变量temp称为“临时变量temp”。

在S132之后，进入S134。

在S133中，多精度整数判定部131对临时变量temp设定素数p。

在S133之后，进入S134。

在S134中，剩余运算变量设定部132对多精度整数a加上临时 变量temp的值，将所得到的值设定给规定的变量c。以下，将变量c 称为“剩余运算变量c”。

在S134之后，进入S135。

在S135中，移位运算部133使表示剩余运算变量c的比特串向 右移位1比特，将所得到的值作为剩余值r输出。

剩余值r是将“a/2”除以“p”而得到的余数，能够通过“r=a/2mod p”这样的公式来表示。

通过S135，多精度剩余运算处理结束。

在上述多精度剩余运算处理（图8）中，不论多精度整数a是偶 数和奇数中的哪一个的值，处理步骤数都不发生变化。

因此，在多精度剩余运算处理中，在多精度整数a是偶数的情况 和多精度整数a是奇数的情况下，不产生计算时间的时间差。即，不 管多精度整数a的值如何都在恒定的计算时间内进行多精度剩余运算 处理，所以多精度剩余运算处理不会被定时解析。

因此，关于多精度整数a，不会通过定时解析来确定，也不会根 据多精度整数a得知随机数k、电子签名等秘密信息。

在实施方式2中，椭圆曲线密码装置100也可以不是生成电子签 名的密码装置，多精度剩余运算处理（图8）也可以作为生成电子签 名的处理以外的处理所包含的多精度运算处理来执行。

即，实施方式2中的多精度剩余运算处理（图8）也可以用于验 证电子签名的处理、与电子签名无关的密码处理、椭圆曲线密码以外 的密码处理或者密码处理以外的运算处理等使用多精度整数的任意的 运算处理。

实施方式3.

说明在恒定的计算时间内进行多精度整数的零判定的方式。

多精度整数的零判定是指，判定多精度整数的值是零和非零中的 哪一个值的处理。

以下，主要说明与实施方式1、2不同的事项。关于省略说明的 事项，与实施方式1、2相同。

图9是实施方式3中的椭圆曲线密码装置100的结构图。

根据图9，说明实施方式3中的椭圆曲线密码装置100的结构。

椭圆曲线密码装置100除了在实施方式2中说明的结构以外，还 具备多精度零判定部140。

多精度零判定部140判定连结多个整数值来表示的特定的多精度 整数b是否为零。

多精度零判定部140具备“或”运算部141和零判定部142。

“或”运算部141计算表示多精度整数b的多个整数值（字）的 “或”。

零判定部142根据由“或”运算部141计算出的“或”而判定多 精度整数b是否为零。

椭圆标量乘法部120的初始设定部121对标量乘法变量R设定表 示特定点的坐标值G的多精度整数（图4的S121A）。

标量乘法部122使用多精度零判定部140来计算对标量乘法变量 R进行2倍乘法而得到的坐标值“2R”（图4的S123A）。

标量乘法部122使用多精度零判定部140而计算对第0作业变量 R[0]加上特定点的坐标值G而得到的坐标值“R[0]+G”（图4的 S124A）。

标量倍点输出部123使用多精度零判定部140来计算从标量乘法 变量R减去坐标值2^tG而得到的坐标值“R－2^tG”（图4的S128A）。

以下，将特定点的坐标值G记载为“特定点G”，将坐标值2^tG记 载为“常数值2^tG”。

图10是示出实施方式3中的多精度零判定方法的流程图。

根据图10，说明实施方式3中的多精度零判定方法。

通常，在多精度运算处理中，进行多精度零判定处理。

多精度零判定处理是指，判定多精度整数b的值是零和非零中的 哪一个值的处理。

在实施方式1中说明的椭圆曲线上的特定点G的坐标值是多精 度整数的一个例子。

例如，椭圆标量乘法部120在S123A、S124A以及S128A（参照 图4）中调出多精度零判定部140，多精度零判定部140执行图10所 示的多精度零判定处理。

在S141中，“或”运算部141按照每规定的位数（或者比特数） 来分割多精度整数b。例如，“或”运算部141将100位的多精度整 数b分割为每10位为1个整数值的10个整数值。另外，例如，“或” 运算部141将96比特的多精度整数b分割为每32比特为1个比特串 的3个比特串。

以下，将用分割多精度整数b而得到的多个整数值或者分割多精 度整数b而得到的多个比特串表示的多个整数值称为“字”。

另外，将多精度整数b的字数（分割数）设为“w”，将从下位起 第i个字设为b[i]。即，将最上位的字（开头字）设为b[w]，将最下 位的字（最终字）设为b[1]。

在S141之后，进入S142。

在S142中，“或”运算部141计算在S141中得到的多精度整数 b的多个字的“或”，对规定的变量OR设定所计算出的“或”。以 下，将变量OR称为““或”OR”。在实施方式中，“A|B”意味着A与 B的“或”。

因此，在构成多精度整数b的多个字所有值是“0”的情况下，“或” OR的值为“0”，在构成多精度整数b的多个字的至少某一个的值非“0” 的情况下，“或”OR的值成为“1”。

在S142之后，进入S143。

在S143中，零判定部142判定在S142中设定的“或”OR的值 是“0”和“1”中的哪一个值。

然后，在“或”OR的值是“0”的情况下，零判定部142判定为多 精度整数b的值是零，输出判定结果。

另外，在“或”OR的值非“0”的情况下，零判定部142判定为多 精度整数b的值是零以外的值（非零），输出判定结果。

通过S143，多精度零判定处理结束。

在上述多精度零判定处理（图10）中，不论多精度整数b是什 么样的值，处理步骤数都不变。

因此，在多精度零判定处理中，不会由于多精度整数b的值而产 生计算时间的时间差。即，不管多精度整数b的值如何都在恒定的计 算时间内进行多精度零判定处理，多精度零判定处理不会被定时解析。

因此，关于多精度整数b，不会通过定时解析来确定，也不会根 据多精度整数b得知随机数k、电子签名等秘密信息。

在实施方式3中，椭圆曲线密码装置100也可以不是生成电子签 名的密码装置，多精度零判定处理（图10）也可以作为生成电子签名 的处理以外的处理所包含的多精度运算处理而执行。

即，实施方式3中的多精度零判定处理（图10）也可以使用于验 证电子签名的处理、与电子签名无关的密码处理、椭圆曲线密码以外 的密码处理或者密码处理以外的运算处理等使用多精度整数的任意的 运算处理。