信息安全装置及椭圆曲线运算装置的制作方法
专利名称：信息安全装置及椭圆曲线运算装置的制作方法
技术领域：
本发明涉及能够对抗基于功率消耗量测量的功率分析攻击，可以 安全、可靠地对信息进行处理的信息安全技术。
背景技术：
近些年来，在由硬件或软件安装的加密模块中进行加密处理时， 以该加密处理中的各种副信息为线索，对该加密处理中所使用的加密 密钥进行分析的各种破译方法，进行了研究。
例如，在被称为定时攻击的破译方法中，在加密模块中加密处理 所需的时间，根据该加密处理中所用的加密密钥的值，有尽管微小但 确实存在的不同，利用这一点进行该加密密钥的破译。另外，在被称
为Simple Power Analysis(简单功率分析攻击)、及Differential Power Analysis(差分功率分析攻击)的破译方法中，采用进行加密处理时的加 密模块的功率消耗量作为副信息。
已有报告指出，这些破译方法，近些年来可以以便宜的价格得到 高性能的测量设备，即使对安装IC卡这样的加密模块的实际产品也 可以进行分析。
在下面的说明中，以上述的加密处理时的加密模块功率消耗量的 变化，即功率波形为线索，对加密密钥进行分析的破译方法，总称为 "功率分析攻击"。关于定时攻击，在非专利文献1中进行了详细说 明，而关于功率分析攻击，在非专利文献2中进行了详细叙述。
下面，说明对椭圆曲线加密的简单功率分析攻击。关于椭圆曲线 加密，在非专利文献5中进行了详细叙述，另夕卜，关于椭圆ElGamal 加密及椭圆DSA签名方式，在非专利文献3中进行详细叙述。
(椭圆曲线加密的简单功率分析攻击)
在椭圆曲线加密的解密处理中，计算作为正整数的私钥ks和作
为密文一部分的椭圆曲线上的点C的标量乘法点k^C。此处，ks*C 表示将ks个点C相加所得到的椭圆曲线上的点。该计算方法，例如 是已知有在非专利文献5的69页的带符号Window法。下面对带符 号Window法进行说明。以下，设Window的宽度为3比特。
步骤S801:使v—ks，取v—0，v—l,v—2，......，v—b，使v=v_0+v—1
X2A3+v—2X2A6+......+v—bX2A(bX3)。再使v—(b+1)—0。此处，b表
示(len/3以上的最小整数)-l, len表示v的比特数，"X "表示整数 相乘，x、表示x的y次幂。例如len-52时，b=18-l=17。
步骤S802:在以下的步骤S8021 S8026中，生成整数串 {w_i}(i=l， 2， ......， b+l)。
步骤S8021: c—0
步骤S8022:判断是否是v_c〉2A2，当v—c>2A2时，转到步骤 S8023,否则转到步骤S8024。
步骤S8023: w—c—v—c-2A3， v—(c+1)—v_(c+l)+l ，转到步骤S8025 步骤S8024: w—c—v—c 步骤S8025: c—c+1
步骤S8026:判断是否是c〉b+l。当c〉b+l时，转到步骤S803， 否则转到步骤S8022
步骤S803:在以下的步骤S8031 S8035中，生成表(P一i〉。
步骤S8031: P—0—0、 P—2—Dob(C),此处，O表示椭圆曲线的 零源，Dob表示椭圆曲线的2倍运算，Dob(C)是C的2倍点。
步骤S8032: c—3
步骤S8033: P_c—P—(c-l)+C
步骤S8034: c—c+l
步骤S8035:判断是否是0>2"2=4。当c>2A2时，转到步骤S804， 否则转到步骤S8033。
步骤S804:在以下的步骤S8041 S8047中，计算标量乘法点R。 步骤S8041: c—b+l
步骤S8042:判断是否是w—c=0。当 _0=0时，c—c-l。 步骤S8043: R—P—(w一c)
步骤S8044: c—c-l
步骤S8045:判断是否是c〈0。当c〈0时，转到步骤S805。
步骤S8046: R—Dob(Dob(Dob(P—(w—c))))
步骤S8047:判断w—c是正、负还是0。当w_c<0时，R—Add(R， -P_(-w_c》，当w—c>0时，R—Add(R， P_(w_c》，当w—c=0时，什 么也不做。转到步骤S8044,此处Add是椭圆曲线的加法运算，Add(R， P一(wj))是对R和P一(wj)的椭圆曲线的加法运算的结果。
步骤S805:输出R，结束。
在上述方法中，利用整数串(w—力和表(P—i》计算标量乘法点。在 步骤S8047中当w_c=0时，未执行椭圆曲线运算。另夕卜，在步骤S8042 中，当wj-0时，由于不进行椭圆曲线的运算，而减去c，因此这一 部分不执行椭圆曲线的运算。这样，当w_c=0时，与不是这种情况 时处理不同。
(椭圆曲线的2倍运算和椭圆曲线加法运算的公式) 以下，表示椭圆曲线的2倍运算和椭圆曲线加法运算的公式。关 于该公式，在非专利文献4中进行了详细叙述。此处，以点坐标为 Jacobian坐标，进行椭圆曲线的运算(加法运算及2倍运算)。
(a) 椭圆曲线的加法公式
对于P1气X1， Yl， Zl)， P2=(X2, Y2， Z2)，使P3=P1+P2=(X3， Y3, Z3)
X3=-HA3-2 X Ul X H八2+一2 Y3=-S1 XHA3+rX(Ul XHA2-X3) Z3=Z1XZ2XH
其中，U1=X1XZ2A2， U2=X2XZ1A2， S1=Y1XZ2A3， S2=Y2 XZ1A3, H=U1-U2， r=S2-Sl。
(b) 椭圆曲线的2倍运算公式
对于P1气X1， Yl， Zl)，使P4-2氺P1-(X4， Y4， Z4)。 X4=T
Y4=-8XY1A4+MX(S-T) Z4=2XY1XZ1
其中，S=4XX1XY1A2， M=3XXlA2+aXZlA4， T=-2S+MA2。
从上述看出，在椭圆曲线加法运算中，2次方计算执行4次，乘 法执行12次。与此相比，椭圆曲线2倍运算中，2次方计算执行6 次，乘法执行4次。
这样，椭圆曲线计算和椭圆曲线2倍运算，由于2次方计算及乘 法的次数不同，所以加密模块中的消耗功率波形不同。从而，通过观 测功率波形，可以分析椭圆曲线的2倍运算，加法运算的顺序。从该 分析结果，攻击者可以知道有无w_c=0的情况。另外，攻击者可以 根据是否是w_c=0的信息縮小私钥ks的搜索空间。
(现有的对椭圆曲线加密的简单功率分析攻击的对策方法)
在上述的简单功率分析攻击中，利用了在w—c=0时计算处理不 同的情况。为此，为了防御该攻击，只要通过在w—c=0时增加伪计 算处理，使w—c=0时与不是这一情况时的计算处理相同即可。具体 地说，用以下的算法进行计算。
步骤S901: v—ks，取v—0， v—1， v—2， ......， v一b使v=v—0+v_l
X2A3+v—2X2A6+ +v_bX2A(bX3)。再使v—(b+1)—0。此处，b表
示(len/3以上的最小整数)-l ， len表示v的比特数，"X "表示整数 的乘法，xAy表示x的y次方。例如，len-52时，b=18-l=17。
步骤S902:在以下的步骤S9021 S9026中，生成整数串 {w—i}(i=l， 2, ......， b+l)。
步骤S9021: c—0
步骤S9022:判断是否是v_c>2A2，当v_c>2A2时，转到步骤 S9023,否则转到步骤S9024。
步骤S9023: w_c—v—c-2A3， v_(c+l)—v—(c+l)+l ，转到步骤 S9025。
步骤S9024: w—c—v—c
步骤S9025: c—c+1
步骤S9026:判断是否是c〉b+l。当c〉b+l时，转到步骤S903， 否则转到步骤S9022
步骤S903:在以下的步骤S9031 S9035中，生成表(P—i}。
步骤S9031: P_0—0、 P—2—Dob(C)。 步骤S9032: c—3 步骤S9033: P—c—P—(c-l)+C 步骤S9034: c—c+1
步骤S9035:判断是否是c〉2^4。当c〉2A2时，转到步骤S904, 否则转到步骤S9033。
步骤S904:在以下的步骤中，计算标量乘法点R。 步骤S904h c—b+1
步骤S9042 : 判断是否w_c=0 。当w_c=0时，D — Dob(Dob(Dob(C)))， D—Add(R，C)， c—c-l。 步骤S9043: R—P_(w_c) 步骤S9044: c—c-1
步骤S9045:判断是否c〈0。当c〈0时，转到步骤S905。
步骤S9046: R—Dob(Dob(Dob(P_(w—c))))
步骤S9047:判断w_c是正、负还是0。当w—c<0时，R—Add(R， -P_(-w—c))，当w_c>0时，R—Add(R， P_(w—c))，当w—c=0时，D —Add(R,C)。转到步骤S9044,此处Add是椭圆曲线的加法运算， Add(R， P—(w一c))是对R和P—(w—c)的椭圆曲线的加法运算的结果。
步骤S905:输出R，结束。
在上述对简单功率攻击的对策方法中，D是与计算结果没关系的 伪的点，在步骤S9042及步骤S9047执行的Q运算为伪运算。在步 骤S9042中当w—c=0时，执行3次伪椭圆曲线2倍运算和1次伪椭 圆曲线加法运算。即使在不是w—c-O时，也执行步骤S9046的3次 椭圆曲线2倍运算、步骤S9047的1次椭圆曲线加法运算，所以w_c=0 时和w—c^O时执行相同的运算。另外，在步骤S9047,当w^-0时 执行伪的加法，执行与w—c#0时相同的运算。
从而，上述对简单功率攻击的对策方法中，由于w—c=0时也与 w—c#0时执行相同的运算，所以功率波形相同，攻击者根据功率波 形无法知道是否是w_c=0的信息。
非专禾!j文献1: Paul C. Kocher， "Timing attacks on implementations
of Diffie-Hellman， RSA， DSS， and Other Systems", In Neal Koblitz, editor, CRYPTO，96， LNCS 1109， Springer-Verlag, 1996, pp. 104-113.
非专利文献2: P. Kocher， J. Jaffe， and B. Jun， "Differential Power Analysis", Advances in Cryptology-CRYPTO，99， LNCS， 1666， Springer-Verlag, 1999， pp.388-397.
非专利文献3:岡本龍明、山本博資、[現代喑号]、産業図書(1997
年)
非专利文献4: A. Miyaji， T. Ono and H. Cohen， "Efficient elliptic curve exponentiation", ICICS，97， Springer-Verlag, 1999, pp.282-291.
非专利文献5: I. Blake， G. Seroussi andN. Smart, "Elliptic Curves in Cryptography", London Mathematical Society Lecture Note Series 265, CAMBRIDGE UNIVERSITY PRESS, 1999
在上述对简单功率攻击的对策方法中，除P一^P以外，在表中还 存放P—2、 P_3、 P—4三点。但是，在IC卡等资源受限制的状况下， 希望减小表的量。
发明内容
本发明的目的在于提供一种信息安全装置、椭圆曲线运算装置、 方法及计算机程序，在保持对简单功率分析攻击的耐受性的同时，可 以削减使用的表量。
(解决课题的手段)
为了达到上述目的，本发明的信息安全装置，以将素数p作为模 的剩余域F上所定义的椭圆曲线E上的离散对数问题为根据，利用在 椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k来计算 出点PC的椭圆曲线运算，安全而可靠地处理信息，其特征在于，包 括点存储单元，存储椭圆曲线E上的点C;位存储单元，存储系数
k的所有位的值；取得单元，从位存储单元取得1个位的值W;乘法 运算单元，其数量与取得的上述位所能表示的值的种类的数量相同； 选择单元，选择与取得的上述位的值W相对应的乘法运算单元；以 及重复控制单元，对于系数k的所有的位，对上述取得单元、上述选择单元及上述乘法运算单元进行控制，以便重复地进行1个位的值W 的取得、与取得的位的值w相对应的乘法运算单元的选择、以及所
选择的乘法运算单元进行的乘法运算，各乘法运算单元，在椭圆曲线
E上，将上述点C乘以取得的上述位的值w所得到的乘法运算结果， 在与该位相对应的位置上进行加法运算，当存在满足取得的上述位的 值w用2t除得开、而用2W除不开的条件的非负整数t时，与该位的 值w相对应的上述乘法运算单元，在椭圆曲线E上，进行包括点Q 乘以w/2t而得到的点的加法运算或点Q乘以lw/2tl而得的点的减法运 算的运算。
此处，点存储单元相当于实施方式的被运算值存放部224，位存 储单元相当于分割信息存放部223，取得单元相当于取得部241，选 择单元相当于选择部242，多个乘法运算单元分别相当于Window运 算部251 25S，重复控制单元相当于重复控制部243。另外，实施方 式中的Window在此以位(digit)来表示。
(发明的效果)
根据该构成，与该位的值w相对应的上述乘法运算单元，在椭 圆曲线E上，进行包括点Q乘以w/2t所得到的点的加法运算或点Q 乘以lw/2tl所得到的点的减法运算的运算，所以例如当各位的比特长为 3时，在加法运算或减法运算中使用的点，除了C之外，只有3T， 当各位的比特长为4时，加法运算或减法运算中使用的点，除了 C
之外，只有3氺c、 5*<:及7*(:。
按照现有技术，例如当各位的比特长为3时，在加法运算或减法
运算中使用的点，除了c之外，有2*0、 3*(:及4*(:，而当各位的比
特长为4时，在加法运算或减法运算中使用的点，除了 C之外，有 2*C、 3*C、 4*C、 5*C、 6*C、 7*C及8*C。
这样，根据本发明，与现有技术比较，可以减少在加法运算或减 法运算中所使用的点，可以削减使用的表量。
此处，也可以是，取得的上述位为sw比特长，当存在上述非负 整数t时，与上述位的值w相对应的上述乘法运算单元，依次进行 (sw+l)次运算，在上述多个运算中的第(sw-t+l)个运算，是椭圆曲线E
上的上述加法运算或上述减法运算，其他运算是椭圆曲线E上的2 倍运算。
通过这一构成，可得到与现有技术同样的运算结果，并且可以减 少加法运算或减法运算中使用的点的数量。
此处，也可以是，上述信息安全装置还包括表生成单元，该表生 成单元以点Q为初始的加法运算点，通过重复进行对加法运算点加 上2*Q而得到新的加法运算点，从而生成除点Q之外的2SW"个加法 运算点；当存在非负整数t时，与该位的值w相对应的上述乘法运算 单元，使用由上述表生成单元所生成的上述加法运算点，作为点Q 乘以w/2t或lw/2t,得到的点。
通过这一构成，由于通过表生成单元，2sw'1个加法运算点被算出， 所以可以减少乘法运算单元中的运算次数。
此处，也可以是，取得的上述位是3比特长，当上述位的值w 为2时，对应的乘法运算单元依次进行椭圆曲线E上的2倍运算、2 倍运算、加法运算及2倍运算，上述加法运算是加上上述点C的运算， 当上述位的值w为4时，对应的乘法运算单元依次进行椭圆曲线E 上的2倍运算、加法运算、2倍运算及2倍运算，上述加法运算是加 上上述点C的运算，当上述位的值w为-2时，对应的乘法运算单元 依次进行椭圆曲线E上的2倍运算、2倍运算、减法运算及2倍运算， 上述减法运算是减去上述点C的运算。
通过这一构成，在加法运算或减法运算中使用的点，除了 C之外， 只有3*(:，与现有技术比较，可以削减使用的表量。
此处，也可以是，取得的上述位是4比特长，当上述位的值w 为2时，对应的乘法运算单元依次进行椭圆曲线E上的2倍运算、2 倍运算、2倍运算、加法运算及2倍运算，上述加法运算是加上上述 点C的运算，当上述位的值w为4时，对应的乘法运算单元依次进 行椭圆曲线E上的2倍运算、2倍运算、加法运算、2倍运算及2倍 运算，上述加法运算是加上上述点C的运算，当上述位的值w为6 时，对应的乘法运算单元依次进行椭圆曲线E上的2倍运算、2倍运 算、2倍运算、加法运算及2倍运算，上述加法运算是加上点3*C的运算，当上述位的值w为8时，对应的乘法运算单元依次进行椭圆 曲线E上的2倍运算、加法运算、2倍运算、2倍运算及2倍运算， 上述加法运算是加上上述点C的运算，当上述位的值w为-6时，对 应的乘法运算单元依次进行椭圆曲线E上的2倍运算、2倍运算、2 倍运算、减法运算及2倍运算，上述减法运算是减去点3*(:的运算， 当上述位的值w为-4时，对应的乘法运算单元依次进行椭圆曲线E 上的2倍运算、2倍运算、减法运算、2倍运算及2倍运算，上述减 法运算是减去点C的运算，当上述位的值w为-2时，对应的乘法运 算单元依次进行椭圆曲线E上的2倍运算、2倍运算、2倍运算、减 法运算及2倍运算，上述减法运算是减去点C的运算。
通过这一构成，在加法运算或减法运算中使用的点，除了 C之外， 只有3*匚5*<:及7*<:,与现有技术比较，可以削减使用的表量。
此处，也可以是，上述加法运算或上述减法运算及上述2倍运算， 分别包括伪运算，使得它们以相同顺序执行相同种类的运算。
根据该构成，由于加法运算或减法运算及2倍运算，分别以相同 的顺序执行相同种类的运算，所以即使要以功率波形为线索进行分 析，在加法运算或减法运算及2倍运算中，输出同样的功率波形，很 难明确区别2者。这样，可以对抗功率分析攻击。
此处，也可以是，当取得的上述位是a比特长时，在存在上述非 负整数t时，与上述位的值w相对应的上述乘法运算单元，依次进行 (a+l)次运算，在上述多个运算中的第(a-t+l)个运算是椭圆曲线E上的 上述加法运算或上述减法运算，其他运算是椭圆曲线E上的2倍运算， 当取得的上述位是b比特长时，在存在上述非负整数t时，与上述位 的值w相对应的上述乘法运算单元，依次进行(b+l)次运算，在上述 多个运算中的第(b-t+l)个运算是椭圆曲线E上的上述加法运算或上 述减法运算，其他运算是椭圆曲线E上的2倍运算。
根据该构成，即使混合存在不同比特长的位时，也可以进行运算。
此处，也可以是，上述信息安全装置是加密装置，采用计算点 WC的椭圆曲线运算，对信息进行加密。
根据这一构成，可以对抗信息加密时的功率分析攻击。
此处，也可以是，上述信息安全装置是解密装置，采用计算点
PC的椭圆曲线运算，对加密的信息进行解密。
根据这一构成，可以对抗对加密的信息进行解密时的功率分析攻击。
此处，也可以是，上述信息安全装置是数字签名生成装置，采用
计算点k*C的椭圆曲线运算，对信息进行数字签名。
根据这一构成，可以对抗数字签名生成时的功率分析攻击。 此处，也可以是，上述信息安全装置是数字签名验证装置，采用
计算点PC的椭圆曲线运算，进行数字签名的验证。
根据这一构成，可以对抗数字签名验证时的功率分析攻击。 此处，也可以是，上述信息安全装置是密钥共有装置，采用计算
点wc的椭圆曲线运算，生成与其他密钥共有装置之间共有的密钥。
根据这一构成，可以对抗密钥共有时的功率分析攻击。
另外，本发明的椭圆曲线运算装置，以将素数p作为模的剩余域
F上所定义的椭圆曲线E上的离散对数问题为根据，利用在椭圆曲线 E上的点C乘以作为小于素数p的正整数的系数k来计算点k*C，其 特征在于，该椭圆曲线运算装置包括点存储单元，存储椭圆曲线E 上的点C;位存储单元，存储系数k的所有位的值；取得单元，从位 存储单元取得1个位的值W;乘法运算单元，其数量与取得的上述位 所能表示的值的种类的数量相同；选择单元，选择与取得的上述位的 值W相对应的乘法运算单元；以及重复控制单元，对于系数k的所 有的位，对上述取得单元、上述选择单元及上述乘法运算单元进行控 制，以便重复地进行1个位的值W的取得、与取得的位的值W相对 应的乘法运算单元的选择、以及所选择的乘法运算单元进行的乘法运 算，各乘法运算单元，在椭圆曲线E上，将上述点C乘以取得的上
述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行
加法运算，当存在满足取得的上述位的值w用2t除得开、而用2t+1 除不开的条件的非负整数t时，与该位的值w相对应的上述乘法运算 单元，在椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法 运算或点Q乘以lw/2tl而得的点的减法运算的运算。
根据这一构成，与现有技术比较，可以减少在加法运算中所使用 的点，可以削减使用的表量。
如上述说明的那样，通过本发明的信息安全装置及椭圆曲线运算 装置，可以取得在保持对简单功率分析攻击的耐受性的同时，与现有 技术相比可削减使用的表量的效果。
图1是表示本发明所涉及的1实施方式的点发行系统10的构成
的系统构成图。
图2是表示椭圆曲线运算部208的构成的方框图。
图3是表示分割信息生成部222的操作的流程图。
图4是表示椭圆曲线加法运算部226的加法运算操作及椭圆曲线
2倍运算部227的2倍运算操作的流程图。下接图5。
图5是表示椭圆曲线加法运算部226的加法运算操作及椭圆曲线
2倍运算部227的2倍运算操作的流程图。上接图4。
图6是表示表生成部225的表(P—0的生成操作的流程图。
图7表示在sw=3时，由表生成部225戶;f生成的表(P一i)的一例。
图8表示在sw=4时，由表生成部225所生成的表《P一i)的一例。
图9表示在sw=5时，由表生成部225所生成的表(PJ)的一例。
图IO表示标量乘法运算部229的运算步骤的流程图。下接图11。
图11表示标量乘法运算部229的运算步骤的流程图。上接图10。
图12是用于说明图11的步骤S161 S168的各运算的意义的
sw=3吋的运算变换表320。
图13是表示椭圆曲线运算部208的操作的流程图。
图14是表示点发行系统10的操作的流程图。
图15是表示数字签名系统的操作的流程图。
图16是表示密钥共有系统的操作的流程图。
图17表示sw=4时的运算变换表330。
图18是表示标量乘法运算部229的构成的方框图。
具体实施例方式
1、实施方式l
下面，对本发明所涉及的1实施方式的点发行系统io进行说明。 1.1点发行系统io的构成
点发行系统IO，如图1中所示，由IC卡100及点发行装置200 构成。
通过点发行装置200的操作者，将IC卡100安装在点发行装置 200上，点发行装置200生成点，对生成的点施行加密算法，生成加 密点，并将生成的加密点发送给IC卡100。
此处，点是在用户购买商品或接受服务时，从销售者及服务提供 者接受的优惠信息，以后用户在购买商品或接受服务时，作为对销售 者及服务提供者的等价支付的一部分或全部而加以利用。
IC卡100接受加密点，对接受的加密点实施对应于上述加密的 解密算法，生成解密点，并将生成的解密点存储在内部。
点发行装置200及IC卡100，是分别以素数p为模的剩余域F 上所定义的椭圆曲线E上的离散对数问题为根据，利用在椭圆曲线E 上的点C乘以作为小于素数p的正整数的系数k而计算点k*C的椭 圆曲线运算，安全而可靠地处理信息的信息安全装置。
此处，对信息进行安全处理，是指例如在二者间进行信息通信时， 该信息不让第三者知道，该通信也称为秘密通信。
1.2公钥加密方式及离散对数问题
在本实施方式中，上述加密算法及解密算、法，基于使用椭圆曲线 上的运算的公钥加密方式。
在使用公钥加密方式的秘密通信中，加密密钥和解密密钥不同， 解密密钥是私有的，但加密密钥是公开的。
作为该公钥加密方式安全性的根据，可使用在椭圆曲线上所定义 的离散对数问题，关于离散对数问题，在NealKoblitz著的"A Course in Number theory and Cryptography" ， Springer-Verlag， 1987中进行了 详细叙述。
下面，对椭圆曲线上的离散对数问题进行说明。
所谓椭圆曲线上的离散对数问题是，
假设E(GF(p))为在有限域GF(p)上定义的椭圆曲线，当椭圆曲线 E的位数用大的素数除得开时，将椭圆曲线E中所包含的元G作为 基点。这时，如果对椭圆曲线E中所包含的给出的元Y，存在满足
Y=x*G
的整数x，则求出x的问题。
此处，p是素数，GF(p)是具有p个元的有限域。在本说明书中， 符号*表示对椭圆曲线中包含的元进行多个加法运算的运算，x*G， 如下式所示，表示对椭圆曲线中包含的元G相加x个。
x*G=G+G+G+......+G
将离散对数问题作为公钥加密安全性的根据，是因为对于有多个 元的有限域GF(p)，上述问题极为难的缘故。 1.3点发行装置200的构成
点发行装置200，如图l中所示，由公钥存储部20K加密处理 部202、通信部203、控制部204、信息存储部205、输入受理部206、 显示部207及椭圆曲线运算部208构成。
椭圆曲线运算部208，如图2中所示，由输入部230、幂乘(^含 倍)系数存放部221、分割信息生成部222、分割信息存放部223、被 运算值存放部224、表生成部225、椭圆曲线加法运算部226、椭圆 曲线2倍运算部227、表存放部228、标量乘法运算部229及输出部 231构成。
点发行装置200，是生成点并将生成的点进行加密写入IC卡100 中的装置，并且，在销售商品时，也是计算销售额、显示所计算的销 售额、打印收据、将生成的上述点存储在内部、保管使用者支付的货 款等进行保管的现金寄存装置。
点发行装置200，具体来说是由微处理器、ROM、 RAM、硬盘 单元、显示器单元、及键盘等构成的计算机系统。在上述RAM或上 述硬盘单元中存储计算机程序。通过上述微处理器根据上述计算机程 序进行操作，点发行装置200实现其部分功能。
(1)信息存储部205及公钥存储部201
信息存储部205,用于存储素数p、以素数p为模的剩余域Fp上 定义的椭圆曲线E(Fp)上的基点B及椭圆曲线E(Fp)的系数。另外具 有对所生成的点Pm进行存储的区域。
上述椭圆曲线E(Fp)，作为一例，是)^x^aXx+b，上述系数是 a及b。
公钥存储部201，用于存储对应于下述的私钥(私有密钥)ks而生 成的公钥Kp。此处公钥Kp是通过IC卡100或密钥管理装置，按以下 所示的公式算出来的。
公钥Kp-私钥1 *基点B
(2) 控制部204
控制部204,生成作为上述优惠信息的点Pm，并将生成的点Pm 写入信息存储部205。然后，对加密处理部202，输出表示对点Pm 加密并发送给IC卡IOO的指示。
(3) 通信部203、输入受理部206及显示部207
通信部203，在加密处理部202或控制部204的控制的基础上， 在与IC卡100之间进行信息的发送接收。
输入受理部206,受理来自点发行装置200的操作者的信息或指 示的输入，并将受理了输入的信息或指示，输出给控制部204。
显示部207，通过控制部204的控制，显示各种信息。
(4) 加密处理部202
加密处理部202,从控制部204接受表示对点Pm加密并发送给 IC卡IOO的指示。
当接受上述指示时，加密处理部202生成随机数r，从信息存储 部205读出基点B，然后，以生成的随机数r为幂乘系数k，输出给 椭圆曲线运算部208的输入部230，以读出的基点B为被幂乘点C， 输出给输入部230。然后，从椭圆曲线运算部208的输出部231，接 受幂乘点k*C=r*B作为运算结果，使第1密文sh幂乘点r*B.
接着，加密处理部202从公钥存储部201读出公钥Kp，然后以 生成的随机数r为幂乘系数k，输出给输入部230，以读出的公钥kp 为被幂乘点C，输出给输入部230。然后从输出部231接受幂乘点
k*C=r*Kp，作为运算结果。
然后，加密处理部202从信息存储部205读出点Pm，对读出的 点Pm和接收的幂乘点r*Kp的x坐标值进行"异或"，生成第2密 文s2-点Pm xor(幂乘点r*Kp的x坐标值)。此处"xor"是表示"异 或"的运算符。
然后，加密处理部202，将生成的第l密文sl及第2密文s2通 过通信部203发送给IC卡100。 (5)椭圆曲线运算部208
椭圆曲线运算部208，如上所述，由输入部230、幂乘系数存放 部221、分割信息生成部222、分割信息存放部223、被运算值存放 部224、表生成部225、椭圆曲线加法运算部226、椭圆曲线2倍运 算部227、表存放部228、标量乘法运算部229及输出部231构成。
(5-l)幂乘系数存放部221及被运算值存放部224
幂乘系数存放部221，具有只存储l个幂乘系数k的区域。幂乘 系数k是标量，幂乘系数k的比特数为len。
而被运算值存放部224,具有只存储1个被幂乘点G的区域。被 幂乘点G是椭圆曲线上的点。
(5-2)输入部230及输出部231
输入部230，从加密处理部202接受幂乘系数k，当幂乘系数存 放部221中已经存储了幂乘系数时，将接受的幂乘系数k盖写在幂乘 系数存放部221上，而当幂乘系数存放部221未存储幂乘系数时，将 接受的幂乘系数k写入幂乘系数存放部221中。
另外，输入部230从加密处理部202接受被幂乘点C，当被运算 值存放部224中已经存储了被幂乘点时，将接受的被幂乘点C盖写在 被运算存放部224上,而当被运算值存放部224中未存储被幂乘点时， 将接受的被幂乘点C写入被运算存放部224中。
输出部231，从标量乘法运算部229接受幂乘点PC，将接受的 幂乘点k*C输出给加密处理部202。
(5-3)分割信息存放部223
分割信息存放部223，具有存放下述的(b+l)个整数w—i(i=l、 2、
3、……、b+l)组成的整数串(w一i)的区域。
(5-4)分割信息生成部222
分割信息生成部222,从幂乘系数存放部221读出幂乘系数k, 如以下所示，根据读出的幂乘系数k生成由作为分割信息的整数 w_i(i=l、 2、 3、……、b+l)构成的整数串(w—i}。
此处，w一i是sw比特的带符号整数值。sw是带符号Window法 的Window宽度，作为一例，sw=3。这时，w—i取"-3" 、 "-2"、 "國1"、 "0"、 "1"、 "2"、 "3"及"4"中的某个值。b是"(len/sw 以上的最小的整数)-l" ， len是下述的变量v的比特数，"X "是表 示整数的乘法的运算符，"xAy"是表示x的y次方的运算。
例如，le『52时，b=18-l=17。下面作为一个例子sw=3，但是sw 既可以是"2"，也可以是"4"以上。
关于分割信息生成部222的操作，利用图3中所示的流程图进行 说明。
分割信息生成部222,将幂乘系数k代入变量v(v—ks)，取v一0，v一1， v一2， ......， v—b，使v=v—0+v—lX2Asw+v—2X2A(2Xsw)+......+v_b X 2A(b X sw)。再使v—(b+1)—O(步聚S131)。此处v—i(i=0、 1 、2、… b)为sw比特。
然后，分割信息生成部222，在计数器变量c中代入0(c—O)(步 骤S132)
接着，分割信息生成部222，判断是否v—c>2A(sw-l)，当v—c> 2A(sw-l)时(步骤S133中是)，计算w—c —v—c-2A3及v—(c+1)— v—(c+l)+l(步骤S134)。当v—c《2A(sw-l)时(步骤S133中否)时，向w—c 代入v—c(w—c—v-c)(步骤SI35)。
接着，分割信息生成部222，计算c—c+l(步骤S136)。
接着，分割信息生成部222，判断是否c〉b+l，当c〉b+l时(步 骤S137中是)，将整数串(w—iM乍为分割信息存放在分割信息存放部 223中(步骤S138)，结束分割信息的生成处理。当c《b+l时(步骤S137 中否)，返回步骤S133，重复处理。
(5-5)椭圆曲线加法运算部226及椭圆曲线2倍运算部227
椭圆曲线加法运算部226，从表生成部225或标量乘法运算部229 接受椭圆曲线上的2点P1-(X1， Yl， Z1)和P2-(X2， Y2, Z2)以及这 些点的加法运算指示，对于接受的P1-(X1， Yl， Z1)及P2-(X2， Y2， Z2)，如下所示，使Pl和P2在椭圆曲线上进行加法运算，计算点 P3=P1+P2=(X3， Y3， Z3)，然后将计算出的点P3输出给表生成部225 或标量乘法运算部229。
而椭圆曲线2倍运算部227，从表生成部225或标量乘法运算部 229接受椭圆曲线上的点P1-(X1， Yl， Z1)及P1的2倍运算的指示， 对于接受的点P1=(X1， Yl， Zl),如下所示，在椭圆曲线上对点P1 进行2倍运算，计算作为点P1的2倍点的、点P4=2*P1=(X4， Y4， Z4)，然后将计算出的点P4输出给表生成部225或标量乘法运算部 229。
(椭圆曲线加法运算部226的加法运算的细节、及椭圆曲线2倍 运算部227的2倍运算的细节)
在本实施方式中，增加了伪运算，以使在椭圆曲线加法运算部 226及椭圆曲线2倍运算部227中所使用的运算及其顺序相同。
下面，为了明确了解伪运算是"伪运算"，通过变量D表示伪 运算结果的代入目的地。在本实施方式中使用的椭圆曲线加法运算及 椭圆曲线2倍运算，是对Jacobian坐标的计算。关于Jacobian坐标， 在非专利文献4中进行了详细叙述。
在对椭圆曲线加法运算部226及椭圆曲线2倍运算部227的详细 运算进行说明之前，对所使用的运算函数按以下定义。
Sqr(X):表示X的2次方
Mul(X，Y):表示X和Y的相乘。即使在X-Y时，在记载为 Mul(X, Y)的情况下，也不是用Sqr(X)进行2次方计算，同样是以X 的相乘进行计算。
Mul2(X):表示X和2的乘法。
Mul3(X):表示X和3的乘法。
Mul4(X):表示X和4的乘法。
Mul8(X):表示X和8的乘法。
Sub(X,Y):表示从X减去Y的减法。
(椭圆曲线加法运算部226的加法运算操作)
下面，利用4及图5中所示的流程图说明椭圆曲线加法运算部 226的加法操作。
椭圆曲线加法运算部226,按照以下所示的步骤进行加法运算。
Z22—Sqr(Z2) D—Mul4(Xl) U1—Mul(Xl,Z22) Z12—Sqr(Zl) D—Mul2(Yl) Z13—Mul(Z22,Zl) Z23—Mul(Z22，Z2) U2—Mul(X2,Z12)
51— Mul(Yl，Z23)
52— Mul(Y2，Z13) D—Mul3(Z12) H—Sub(U2,Ul) H2—Sqr(H) U1H—Mul(Ul，H2) U2H—Mul2(UlH) r—Sub(S2，Sl) r2—Sqr(r) D一Mul8(r) UHX—Sub(UlH，X3) H3—Mul(H2,H) S1H3—Mul(Sl，H3) rH—Sub(r2，H3) X3—Sub(rH，U2H) Z1Z2—Mul(Zl，Z2) Z3—Mul(ZlZ2,H)
(步骤S401) (步骤S402) (步骤S403) (步骤S404) (步骤S405) (步骤S406) (步骤S407) (步骤S408) (步骤S409) (步骤S410) (步骤S411) (步骤S412) (步骤S413) (步骤S414) (步骤S415) (步骤S416) (步骤S417) (步骤S418) (步骤S419) (步骤S420) (步骤S421) (步骤S422) (步骤S423) (步骤S424) (步骤S425)rU—Mul(r,UHX) (步骤S426)
Y3—Sub(rU，SlH3) (步骤S427)
(椭圆曲线2倍运算部227的2倍运算的操作)
下面，利用4及图5中所示的流程图说明椭圆曲线2倍运算部 227的2倍运算的操作。
椭圆曲线2倍运算部22，按照以下所示的步骤进行2倍运算。
Y12—Sqr(Yl) X41—Mul4(Xl) S—Mul(X41，Y12) X12—Sqr(Xl) Y21—Mul2(Yl) Z4—Mul(Y21，Zl) Z12—Mul(Zl，Zl) Z14—Mul(Z12，Z12) D—Mul(Yl,Z12) aZ14—Mul((國a)， Z14) X32—Mul3(X12) M—Sub(X32，aZ14) M2—Sqr(M) D—Mul(S，M2) S2—Mul2(S) X4—Sub(M2，S2) Y14—Sqr(Y12) Y814—Mul8(Y14) ST—Sub(S，X4) MST—Mul(M，ST) D—Mul(D,MST) Y4—Sub(MST，Y814) D—Sub(Y4,S2) D—Mul(Zl，Z12)
(步骤S501) (步骤S502) (步骤S503) (步骤S504) (步骤S505) (步骤S506) (步骤S507) (步骤S508) (步骤S509) (步骤S510) (步骤S511) (步骤S512) (步骤S513) (步骤S514) (步骤S515) (步骤S516) (步骤S517) (步骤S518) (步骤S519) (步骤S520) (步骤S521) (步骤S522) (步骤S523) (步骤S524)
D—Mul(D，M) D—Mul(X4,ST) D—Sub(D，Y4)
(步骤S525) (步骤S526) (步骤S527)
在步骤S510中出现的(-a)，是椭圆曲线方程式为yA2=XA3+aXx+b 时的参数a的负值，预先计算好。
如图4及图5中所示可知，椭圆曲线加法运算部226和椭圆曲线 2倍运算部227以相同的顺序执行运算。
(5-6)表存放部228
表存放部228，具有1个以上存放由表生成部225生成的椭圆曲 线上的点的区域。
(5-7)表生成部225
表生成部225，如下所述，生成由椭圆曲线上的点构成的表(PJ〉， 并将生成的表(PJ)存放在表存放部228中。
此处，表(PJ),包括1个以上的椭圆曲线上的点P—i(i=l, 2， 3、……)。
关于表生成部225的表(P』的生成操作，禾偶图6中所示的流 程图进行说明。
表生成部225，从被运算值存放部224读出被幂乘点C，表生成 部225对P_i—C及Q—ECD(C)进行运算(步骤S141)。
此处，ECD表示椭圆曲线上的2倍运算，并表示用椭圆曲线2 倍运算部227进行计算。例如，ECD(A)表示对椭圆曲线上的点A进 行计算的2倍运算的运算结果，ECD(A)=2*A。表生成部225对椭圆 曲线2倍运算部227输出椭圆曲线上的点C及2倍运算的指示，并从 椭圆曲线2倍运算部227接受2倍运算的运算结果。
然后，表生成部225对计数器变量i，计算i—1(步骤S142)。
然后，表生成部225计算i—i+l(步骤S143)，计算2^-2,判断是 否》2^-2。在i〉2Sw^时(步骤S144)，结束表生成的处理。
当不是i〉2sw-2时(步骤S144)，表生成部225计算P—i — ECA(P—(i漏l)， Q)。艮口计算ECA(P一(i-l)， Q)= P—(i-l)+Q(步骤S145)。
此处，ECA表示椭圆曲线上的加法运算，并表示用椭圆曲线加 法运算部226进行计算。例如，ECA(A， B)表示对椭圆曲线上的点A 及点B计算出的加法运算结果，ECD(A)=A+B。表生成部225对椭圆 曲线加法运算部226输出椭圆曲线上的点A和点B以及加法运算的 指示，从椭圆曲线加法运算部226接受加法运算的运算结果。
然后，表生成部225将P—i存放在表存放部228中(步骤S146)， 返回步骤S143，重复进行处理。
从上述处理可知P—i=(2Xi-l)*C。
在sw=3、 4及5时，通过表生成部225生成的表(Pj)的例子分 别如图7、图8及图9中所示。
当s『3时，如图7中所示，表311(P—i}=(3C)。而当s『4时， 如图8中所示，表312(P—i}=(3C、 5C、 7C)。当sw=5时，如图9中 所示，表313(P—i}=(3C、 5C、 7C、 9C、 IIC、 13C、 15C)。
(5-8)标量乘法运算部229
标量乘法运算部229利用分割信息存放部223中所存放的整数串 (w一i)和表存放部228中所存放的表(PJh按以下所示，对幂乘系数 计算k倍的点"C。
标量乘法运算部229如图18中所示，由取得部241、选择部242、 重复控制部243、 Window运算部251、 252、 253、 254、 255、 256、 257、 258、初始运算部244、寄存器部245及运算输出部246构成。
关于标量乘法运算部229的运算步骤，利用图10 图11中所示 的流程图迸行说明。
在下述说明中，ECA是由椭圆曲线加法运算部226进行的加法 运算。标量乘法运算部229在进行加法运算时，对椭圆曲线加法运算 部226输出椭圆曲线上的2点及加法运算的指示，从椭圆曲线加法运 算部226接受加法运算的运算结果。另外，ECD是椭圆曲线2倍运 算部227进行的2倍运算。标量乘法运算部229在进行2倍运算时， 对椭圆曲线2倍运算部227输出椭圆曲线上的1点及2倍运算的指示， 从椭圆曲线2倍运算部227接受2倍运算的运算结果。
在下述中，作为一个例子设Window的宽度为"3比特"，即sw=3 进行说明。 标量乘法运算部229的初始运算部244，计算c—b+l(步骤S151)。
此处，c是对处理次数进行计数的计数器变量，寄存器部245由 具有的寄存器构成。b如上所述，是"(len/sw以上的最小整数)-l"。 寄存器部245还具有分别构成下述变量D及变量R的2个寄存器。
接着，标量乘法运算部229的初始运算部244，判断是否w_c=0。 当w_c=0时(步骤S152)，运算D—ECD(C)，D—ECD(D)，D—ECD(D)， D—ECA(R， C)， c—c-l(步骤S153)。
接着，取得部241取得P—(w—c)，标量乘法运算部229的初始运 算部244运算R—P(w一c)(步骤S154)，重复控制部243运算c—c-l(步 骤S155)。
接着，标量乘法运算部229的重复控制部243,判断是否c<0， 当c<0时(步骤S156),运算输出部246将R输出给输出部231(步骤 S158),结束运算处理。
当c》0时(步骤S156),取得部241取得P—(w_c),标量乘法运算 部229的选择部242，对应于w一c的值(步骤S157)进行以下的处理。
当w—c=-3时(步骤S157)，选择部242选择Window运算部251, Window运算部251进行R—ECD(R)， R—ECD(R)， R—ECD(R)， R —ECA(R， -P一2)运算(步骤S161)。
当w—c=-2时(步骤S157),选择部242选择Window运算部252， Window运算部252进行R—ECD(R)， R—ECD(R)， R—ECA(R, -P—1)， R—ECD(R)运算(步骤SI62)。
当w—c=-l时(步骤S157),选择部242选择Window运算部253, Window运算部253进行R—ECD(R)， R—ECD(R)， R—ECD(R)， R —ECD(R， - _1)运算(步骤3163)。
当w_c=0时(步骤S157),选择部242选择Window运算部254， Window运算部254进行R—ECD(R)， R—ECD(R)， R—ECD(R), D —ECA(R， PJ)运算(步骤S164)。
当w—c=l时(步骤S157)，选择部242选择Window运算部255， Window运算部255进行R—ECD(R)， R—ECD(R), R—ECD(R), R —ECA(R， P—l)运算(步骤S165)。
当w—c=2时(步骤S157)，选择部242选择Window运算部256， Window运算部256进行R—ECD(R)， R—ECD(R)， R—ECA(R， P—1)， R—ECD(R)运算(步骤SI66)。
当w_c=3时(步骤S157)，选择部242选择Window运算部257， Window运算部257进行R—ECD(R)， R—ECD(R)， R—ECD(R)， R —ECA(R， P—2)运算(步骤S167)。
当w—c=4时(步骤S157),选择部242选择Window运算部258， Window运算部258进行R—ECD(R)， R—ECA(R， P—1), R—ECD(R), R—ECD(R)运算(步骤S168)。
然后，返回步骤S155重复进行处理。
(关于步骤S161 S168的各运算)
此处，关于图11的步骤S161 S168中各运算的意义，利用图 12中所示的运算变换表320进行说明。
在此，为方便起见，将根据w_c值所进行的多个运算称为Window 运算。
例如，在步骤S164中所进行的R—ECD(R)、 R—ECD(R)、 R— ECD(R)及D—ECA(R， P—l)是1个Window运算，而在步骤S165中 所进行的R—ECD(R)、 R—ECD(R)、 R—ECD(R)及R—ECA(R， P—1) 是1个Window运算。
另外，为了方便起见，将Window运算中所包含的ECA及ECD 称为基本运算。
运算变换表320，作为一个例子，当Window的宽度为"3比特" 时，艮Ps^3时，对每个可取得的w—c的值，表示了该w—c的值、与 其对应的现有Window运算、与其对应的标量乘法运算部229进行的 Window运算(与本发明相关联的Window运算)、表示由标量乘法运 算部229进行的Window运算所包含的基本运算的运算顺序的基本运 算顺序、及表示Window运算所包含的基本运算个数的基本运算次数 间的关系。
此处，作为一个例子，由于Window的宽度为"3比f寺"，所以 w c取"0" 、 "1" 、 "2" 、 "3" 、 "4"、"國3" 、 "-2"及中的某一个。
下面，当w—c取各值时，对现有的Window运算、标量乘法运算 部229的Window运算、基本运算顺序及基本运算次数进行说明。
(a) 当w_c=0时
对w—c=0的现有Window运算，是"R—23R" ， "R—23R"表 示使变量R的值，向高位移位Window宽度所示的比特数(此处为3 比特)。
另一方面，对w_c=0的标量乘法运算部229的Window运算，是 "R—23R"及"D—R+C"。此处对于"R—23R"，如上所述。另夕卜， "D—R+C"是伪的加法运算，目的是为了使w—c=0时的Window运 算所包含的基本运算的种类及其数量，与其他情况(即w_C0时)的 Window运算所包含的基本运算的种类及其数量一致。
此处，"R—23R"，在标量乘法运算部229中，通过R—2XR、 R—2XR、 R—2XR进行运算。
这一运算通过23R=2 X (2 X (2 X R))进行。
从而，在由对w_c=0的标量乘法运算部229进行的Window运算 中，按照2倍运算、2倍运算、2倍运算、伪加法运算的顺序，进行 多个基本运算。(参照步骤S164)
这样，在由对w_c=0的标量乘法运算部229进行的Window运算 所包含的基本运算个数是"4"。
(b) 当w—c=l时
对w_c=l的现有Window运算，是"R—23R+C" 。 "R—23R+C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加C。
对w_c=l的标量乘法运算部229的Window运算，是"R— 23R+C"。
这样，对w—c=l的现有Window运算，与标量乘法运算部229 的Window运算是相同的。
此处，"R—23R+C",在标量乘法运算部229中，通过R—2X R、 R—2XR、 R—2XR、 R—R+C进行运算。(参照步骤S165)
从而，在由对w_c=l的标量乘法运算部229进行的Window运算 中，按照2倍运算、2倍运算、2倍运算、加法运算的顺序，进行多 个基本运算。
这样，在由对w—c=l的标量乘法运算部229进行的Window运算 所包含的基本运算个数为"4"。
(c) 当w_c=2时
对w_c=2的现有Window运算，是"R—23R+2C" 。 "R—23R+2C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加2C。
另一方面，对w_c=2的标量乘法运算部229的Window运算，是 "R—2(22R+C)"。
根据2(22R+C)=23R+2C可知，对w—c=2的现有Window运算的 结果，与标量乘法运算部229的Window运算结果是相同的。
此处，"R—2(22R+C)",在标量乘法运算部229中，通过R—2 XR、 R—2XR、 R—R+C、 R—2XR进行运算。(参照步骤S166)
这一运算通过2(22R+C)=2 X (2 X (2 X R)+C)进行。
从而，在由对w_c=2的标量乘法运算部229进行的Window运算 中，按照2倍运算、2倍运算、加法运算、2倍运算的顺序，进行多 个基本运算。
此处，上述加法运算是点C乘以wj/2t所得到的点的加法运算。 这样，对w—c=2的标量乘法运算部229进行的Window运算所包 含的基本运算个数为"4"。
(d) 当w_c=3时
对w—c=3的现有Window运算，是"R—23R+3C"。 "R—23R+3C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加3C。
对w—c=3的标量乘法运算部229的Window运算，是"R— 23R+3C"。
这样，对w—c=3的现有Window运算，与标量乘法运算部229 的Window运算是相同的。
此处，"R—23R+3C"，在标量乘法运算部229中，通过R—2 XR、 R—2XR、 R—2XR、 R—R+3C进行运算。(参照步骤S167) 这一运算通过23R+3C=2 X (2 X (2 X R))+3C进行。 从而，在由对w_c=3的标量乘法运算部229进行的Window运算 中，按照2倍运算、2倍运算、2倍运算、加法运算的顺序，进行多 个基本运算。
这样，对w—c=3的标量乘法运算部229进行的Window运算所包 含的基本运算个数为"4"。
(e) 当w_c=4时
对w—c=4的现有Window运算，是"R—23R+4C" 。 "R—23R+4C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加4C。
另一方面，对w—c=4的标量乘法运算部229的Window运算，是 "R—22(2R+C)"。
根据22(2R+C)=23R+4C可知，对w_c=4的现有Window运算的 结果，与标量乘法运算部229的Window运算结果是相同的。
此处，"R—22(2R+C)，，，在标量乘法运算部229中，通过R—2 XR、 R—R+C、 R—2XR、 R—2XR进行运算。(参照步骤S168)
这一运算通过22(2R+C)=2 X 2 X ((2 X R)+C)进行。
从而，在由对w_c=4的标量乘法运算部229进行的Window运算 中，按照2倍运算、加法运算、2倍运算、2倍运算的顺序，进行多 个基本运算。
此处，上述加法运算是点C乘以w一c/2t所得到的点的加法运算。 这样，对w_c=4的标量乘法运算部229进行的Window运算所包 含的基本运算个数为"4"。
(f) 当w_c=-3时
对w—c=-3的现有Window运算，是"R—23R-3C"。 "R—23R-3C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加-3C(即从变量R减去3C)。
对w c=-3的标量乘法运算部229的Window运算，是"R—23R+3C"。
这样，对w—c=_3的现有Window运算，与标量乘法运算部229 的Window运算是相同的。
此处，"R—23R-3C"，在标量乘法运算部229中，通过R—2 XR、 R—2XR、 R—2XR、 R—R+(-3C)进行运算。(参照步骤S161)
这一运算通过23R-3C=2 X (2 X (2 X R))+(-3C)进行。
从而，对w—c=-3的标量乘法运算部229进行的Window运算中， 按照2倍运算、2倍运算、2倍运算、加法运算(此处是减法运算)的顺 序，进行多个基本运算。
这样，对w_c=-3的标量乘法运算部229进行的Window运算所 包含的基本运算个数为"4"。
(g) 当w—c=-2时
对w—c=-2的现有Window运算，是"R—23R-2C" 。 "R—23R-2C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加-2C(即从变量R减去2C)。
另一方面，对w_c=-2的标量乘法运算部229的Window运算， 是"R—2(22R-C)，，。
根据2(22R-C)=23R-2C可知，对w—c=-2的现有Window运算的 结果，与标量乘法运算部229的Window运算结果是相同的。
此处，"R—2(22R-C)"，在标量乘法运算部229中，通过R—2 XR、 R—2XR、 R—R+(-C)、 R—2XR进行运算。(参照步骤S162)
这一运算通过2(22R-C)=2 X (2 X (2 X R)+(-C》进行。
从而，对w—c=-2的标量乘法运算部229进行的Window运算中， 按照2倍运算、2倍运算、加法运算(此处是减法运算)、2倍运算的顺 序，进行多个基本运算。
此处，上述减法运算是点C乘以I w_c/2t I所得到的点的减法运算。
这样，对w—c=-2的标量乘法运算部229进行的Window运算所 包含的基本运算个数为"4"。
(h) 当w_c=-l时
对w—c=-l的现有Window运算，是"R—23R-C"。 "R—23R-C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加-C(即从变量R减去C)。
对w—c=-l的标量乘法运算部229的Window运算，是"R— 23R-C"。
这样，对w—c=-l的现有Window运算，与标量乘法运算部229 的Window运算是相同的。
此处，"R—23R-C"，在标量乘法运算部229中，通过R—2X R、 R—2XR、 R—2XR、 R—R+(-C)进行运算。(参照步骤S163)
这一运算通过23R-3C=2 X (2 X (2 X R))+(-C)进行。
从而，对w_c=-l的标量乘法运算部229进行的Window运算中， 按照2倍运算、2倍运算、2倍运算、加法运算(此处是减法运算)的顺 序，进行多个基本运算。
这样，对w—c--l的标量乘法运算部229进行的Window运算所 包含的基本运算个数为"4"。
1.4椭圆曲线运算部208的操作
关于椭圆曲线运算部208的操作，利用图13中所示的流程图进 行说明。
输入部230,从加密处理部202接受幂乘系数k,并将接受的幂 乘系数k写入幂乘系数存放部221(步骤S121),从加密处理部202接 受被幂乘点C，并将接受的被幂乘点C写入被运算值存放部224中(步 骤S122)。
接着，分割信息生成部222，根据幂乘系数k生成作为分割信息 的整数串(w一i),并将生成的整数串(w一i)存放在分割信息存放部223 中(步骤S123)。
然后，表生成部225利用被幂乘点C，生成表(P—i}，并将表(P—i} 存放在表存放部228中(步骤S124)。
然后，标量乘法运算部229使用分割信息存放部223中所存放的 整数串(w—i)和表存放部228中的存放的表(P一i)，计算幂乘点WC(步 骤S125)。
然后，输出部231从标量乘法运算部229接受幂乘点WC，并将 所取得的幂乘点k*C输出给加密处理部202(步骤S126)。 1.5 IC卡100的构成
IC卡100，如图1中所示，由私钥存储部101、解密处理部102、 通信部103、控制部104、信息存储部105及椭圆曲线运算部108构 成。
IC卡IOO，具体来说是由微处理器、ROM、 RAM等构成的计算 机系统。在上述RAM中存储计算机程序。通过上述微处理器按照上 述计算机程序进行操作，IC卡100实现其部分功能。
(1) 信息存储部105及私钥存储部101
信息存储部105，存储素数P、椭圆曲线E(Fp)的系数及基点B。 还具有用于存储所生成的解密点Pm'的区域。 私钥存储部101，用于存储私钥ks。
(2) 通信部103
通信部103，从点发行装置200接收第1密文sl及第2密文s2。 若接收第1密文sl及第2密文s2，则对于控制部104,将表示已接 收了的意思通知给控制部104。并将接收的第1密文sl及第2密文 s2输出给解密处理部102。
(3) 控制部104
控制部104，接受表示已从通信部103接收了第1密文sl及第2 密文s2的意思的通知。当接受上述通知时，对解密处理部102输出 对第1密文sl及第2密文s2进行解密生成解密点的指示。
(4) 解密处理部102
解密处理部102,从控制部104接受表示对第1密文sl及第2 密文s2进行解密生成解密点的指示，并从通信部103接受第1密文 sl及第2密文s2。
当接受上述指示时，解密处理部102从私钥存储部101读出私钥 ks，然后以接受的第1密文sl为被幂乘点k，输出给椭圆曲线运算部 108，以读出的私钥ks为幂乘系数C，输出给椭圆曲线运算部108。 然后，从椭圆曲线运算部108接受运算结果k^sl，计算解密点Pm^
第2密文s2 xor(运算结果ks*sl的x坐标值)。 在此，按照
Pm'=s2 xor(ks*sl的x坐标值) =(Pm xor(r*Kp的x坐标值)) xor(ks r*B的x坐标值) =Pm xor(r ks*B的x坐标值)xor(r ks*B的x坐标值) =Pm
可知解密点Pm'与点Pm —致。
然后，解密处理部102将生成的解密点Pm'写入信息存储部105。 (5)椭圆曲线运算部108
椭圆曲线运算部108，由于具有与点发行装置200所具有的椭圆 曲线运算部208相同的构成，故其详细说明予以省略。
椭圆曲线运算部108，从解密处理部102接受被幂乘点k及幂乘 系数C，计算出幂乘点PC，并将计算出的幂乘点"C输出给解密处 理部102。
1.6点发行系统10的操作
对于点发行系统10的操作,利用图14中所示的流程图进行说明。
(l)私钥ks及公钥Kp的生成操作
以下所示的操作，在点发行装置200发行点之前进行。
IC卡100的解密处理部102,生成私钥ks，将生成的私钥ks写 入私钥存储部IOI(步骤SlOl)。然后，解密处理部102从信息存储部 105读出基点B，并对生成的上述私钥ks和读出的基点B实施椭圆 幂乘运算，生成公钥Kp二k^B。这时，椭圆幂乘运算由椭圆曲线运算 部108进行(步骤S102)。然后，解密处理部102将生成的公钥Kp通 过通信部103发给点发行装置200(步骤S103)。
点发行装置200的加密处理部202，从IC卡100通过通信部203 接收公钥Kp，并将接收的公钥Kp写入公钥存储部201(步骤S104)。
此处，IC卡100生成私钥ks,以生成的私钥ks为基础生成公钥 Kp，将生成的公钥Kp发送给点发行装置200，但是也可以按下所示 进行。
艮P，点发行系统10,还包括密钥管理装置(公钥生成装置)。IC 卡100生成私钥ks，并将生成的私钥ks存储在内部。
密钥管理装置，包括从IC卡lOO安全取得私钥ks，并对取得 的私钥ks进行存储的私钥存储部；对基点B进行存储的基点存储部; 从私钥存储部读出私钥ks，并从基点存储部读出基点B，利用私钥 ks和基点B，生成公钥Kp-k^B的椭圆曲线运算部；以及将生成的 公钥Kp发送给点发行装置200的发送部。此处，密钥管理装置具有 的椭圆曲线运算部，与IC卡100具有的椭圆曲线运算部相同。
(2)点的发行操作
点发行装置200的控制部204生成点Pm,并将生成的点Pm写 入信息存储部205，然后，对加密处理部202输出表示对点Pm加密 并发送给IC卡100的指示(步骤Slll)。
加密处理部202,当从控制部204接受表示对点Pm加密并发送 给IC卡100的指示时，生成随机数r(步骤S112)，从信息存储部205 读出基点B，以生成的随机数r为幂乘系数，输出给椭圆曲线运算部 208，并以读出的基点B为被幂乘点，输出给椭圆曲线运算部208， 从椭圆曲线运算部208，作为运算结果接受幂乘点r*B，使第1密文 sl-幂乘点产B(步骤S113)
然后，加密处理部202从公钥存储部201读出公钥Kp，以生成 的随机数r为幂乘系数，输出给椭圆曲线运算部208，以读出的公钥 Kp为被幂乘点，输出给椭圆曲线运算部208，从椭圆曲线运算部208， 接受作为运算结果的幂乘点r*Kp，加密处理部202从信息存储部205 读出点Pm，对读出的点Pm和接受的幂乘点^Kp进行加法运算，生 成第2密文s2-点Pm xor(幂乘点r*Kp的x坐标值)(步骤Sl 14)。
然后，加密处理部202，将生成的第l密文sl及第2密文s2通 过通信部203发送给IC卡IOO(步骤Sl 15)。
解密处理部102,从点发行装置200通过通信部103接受第1密 文sl及第2密文s2(步骤S115)。
然后，解密处理部102从私钥存储部101读出私钥ks，以接受的 第l密文sl作为被幂乘点，输出给椭圆曲线运算部108,以读出的私
钥ks为幂乘系数，输出给椭圆曲线运算部108。椭圆曲线运算部108 对ks*sl进行运算，解密处理部102从椭圆曲线运算部108接受运算 结果ks*sl，计算解密点Pm，-第2密文s2 xor(运算结果ks*sl的x坐 标值)(步骤S116)。
然后，解密处理部102，将计算所得到的解密点Pm'写入信息存 储部105(步骤S117)。
2、实施方式2
下面对本发明所涉及的另一实施方式的数字签名系统(图中未示 出)进行说明。
数字签名系统，由用户A装置(也称签名生成装置)、用户B装置 (也称签名验证装置)及管理中心装置他称管理装置)构成(各装置在图 中未示出)，用户A装置、用户B装置及管理中心装置分别通过互联
网进行连接。
用户A装置、用户B装置及管理中心装置，具体地说分别是由 微处理器、ROM、 RAM、硬盘单元、显示器单元、键盘及鼠标器等 构成的计算机系统。在上述RAM或上述硬盘中存储计算机程序。通 过上述微处理器根据上述计算机程序进行操作，各装置实现其部分功 能。
用户A装置、用户B装置及管理中心装置，分别是在以素数P 为模的剩余域F上所定义的椭圆曲线E上的离散对数问题作为根据， 利用椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k、算 出点k*C的椭圆曲线运算，对信息进行可靠处理的信息安全装置。
此处，所说的对信息进行可靠处理，是指例如使信息在二者间进 行通信时，发送方发送的信息无改变地到达接收方。
用户A装置，将消息与数字签名数据一起发送给用户B装置， 用户B装置，将消息与数字签名数据一起接收，通过接收的数字签名
数据进行签名验证。
此处，假定在以素数p为模的剩余域Fp上定义的椭圆曲线E(Fp)， 以E的位数为q。 B是椭圆曲线E上的基点。
用户A装置，包括生成私钥xA的私钥生成部；将生成的私钥xA安全发送给管理中心装置的私钥发送部；存储应发送的消息m的 消息存储部；从管理中心装置接收素数p、椭圆曲线E的系数、基点 B的参数接收部；存储接收的素数p、椭圆曲线E的系数及基点B的 参数存储部；生成随机数r的随机数生成部；生成第1签名数据 Rl=(rx, ry)=r*B,并根据sXr=m+rxXXA(mod q)计算第2签名数据 s的签名生成部；将所得到的签名数据(Rl, s)和消息m发送给用户B 装置的发送部；以及根据签名生成部的指示，进行椭圆曲线上的点的 椭圆幂乘运算的椭圆曲线运算部。
管理中心装置，包括从用户A装置安全取得私钥xA的取得部; 存储素数p、椭圆曲线E的系数、基点B的参数存储部；利用取得的 私钥xA，计算公钥YA-xA+G的公钥计算部；公开素数p、椭圆曲线 E的系数及基点G的公开部；通过互联网将公钥YA发送给用户B 装置的发送部；以及根据公钥计算部的指示，进行椭圆曲线上的点的 椭圆幂乘运算的椭圆曲线运算部。
用户B装置，包括从管理中心装置接收素数p、椭圆曲线E的 系数及基点G的参数接收部，存储取得的素数P、椭圆曲线E的系数 及基点G的参数存储部;从管理中心装置接收公钥YA的公钥接收部； 存储接收的公钥YA的公钥存储部;从用户A装置接收签名数据(Rl， S)的签名数据接收部；从用户A装置接收消息m的消息接收部；用 户B装置计算S*R1及m*G+rx*YA并判断S*Rl=m*G+rx*YA是否 成立，当成立时，输出表示验证成功的成功信息，当验证失败时，输 出表示验证失败的失败信息的验证部；以及根据验证部的指示，进行 椭圆曲线上的点的椭圆幂乘运算的椭圆曲线运算部。
用户A装置、用户B装置及管理中心装置分别具有的椭圆曲线 运算部，与实施方式l中所示的椭圆曲线运算部208相同。
下面利用图15中所示的流程图对数字签名系统的操作进行说明。
(私钥xA及公钥YA的生成)
用户A装置生成私钥xA(步骤S201)。
管理中心装置，从用户A装置安全取得私钥xA，利用取得的私
钥xA，计算公钥YA-xA承B(步骤S202)。
然后，管理中心装置，公开素数p、椭圆曲线E的系数及基点 B(步骤S204、步骤S207)，通过互联网，将公钥YA发送给用户B装 置(步骤S205)。
用户B装置，取得素数p、椭圆曲线E的系数及基点B(步骤S204)， 接收公钥YA(步骤S205),将接收的公钥YA存储在内部(步骤S206)。
用户A装置，也取得素数p、椭圆曲线E的系数及基点G(步骤 S207)。
(数字签名数据的生成和签名的验证)
用户A装置，生成随机数r(步骤S211),并生成第1签名数据 Rl-(rx，ry)^+B(步骤S212),
根据sXr=m+rxXxA(mod q)计算第2签名数据s(步骤S213),此 处，m是从用户A装置发送给用户B装置的消息。
然后，用户A装置，将所得到的签名数据(R1、 s)和消息m发送 给用户B装置(步骤S214)。
用户B装置，从用户A装置接收签名数据(R1、 s)和消息m(步骤 S214)。
然后，用户B装置，计算s*Rl及n^G+n^YA(步骤S215)，判 断S*Rl=m*G+rx*YA是否成立(步骤S216),当成立时(步骤S216中 是)，验证成功，可以确认用户A装置的身份。当不成立时(步骤S216 中否)，验证失败，不能确认用户A装置的身份。
5、实施方式3
下面，对本发明所涉及的另一实施方式的密钥共有系统(图中未 示出)，进行说明。
密钥共有系统由用户A装置(也称密钥利用装置)、用户B装置(也
称密钥利用装置)及管理中心装置(也称管理装置)构成(各装置在图中 未示出)，用户A装置、用户B装置及管理中心装置分别通过互联网 进行连接。用户A装置、用户B装置及管理中心装置，具体地说分 别是由包括微处理器、ROM、 RAM等构成的计算机系统。微处理器 根据计算机程序进行操作，各装置实现其功能。
用户A装置及用户B装置，是在以素数p为模的剩余域F上所 定义的椭圆曲线E上的离散对数问题作为根据，利用椭圆曲线E上 的点C乘以作为小于素数p的正整数的系数k、算出点k*C的椭圆曲 线运算，对信息进行安全处理的信息安全装置。
此处，所说的对信息安全进行处理，如上所述是指例如使信息在 二者间进行通信时，该信息不让第三方知道。
用户A装置和用户B装置，按如下所示，取得同一共有密钥， 而不让第三者知道。
管理中心装置，包括选择椭圆曲线E(Fp)系数及基点B的选择 部；对选择的椭圆曲线E的系数、基点B及素数p进行存储的参数 存储部；及公开素数p、椭圆曲线E(Fp)及基点G的公开部。
此处，假定是在以素数p为模的剩余域Fp上定义的上述椭圆曲 线E， B是椭圆曲线E上的基点。
用户A装置，包括从管理中心装置取得素数p、椭圆曲线E的 系数及基点B的参数取得部;利用随机数设定私钥xA的私钥设定部； 计算公钥YA=xA*B的公钥计算部；将计算出的公钥YA发送给用户 B装置的公钥发送部；从用户B装置接收公钥YB的公钥接收部；计 算共有密钥xA*YB=(xAXxB)*B的共有密钥计算部；以及根据公钥 计算部及共有密钥计算部的指示，进行椭圆曲线上的点的椭圆幂乘运 算的椭圆曲线运算部。
用户B装置也具有与用户A装置同样的构成。
用户B装置，包括从管理中心装置取得素数p、椭圆曲线E的 系数及基点B的参数取得部;利用随机数设定私钥xB的私钥设定部； 计算公钥YB=xB*B的公钥计算部；将计算出的公钥YB发送给用户 A装置的公钥发送部；从用户A装置接收公钥YA的公钥接收部；计 算共有密钥xB*YA=(xBXxA)*B的共有密钥计算部；以及根据公钥 计算部及共有密钥计算部的指示，进行椭圆曲线上的点的椭圆幂乘运 算的椭圆曲线运算部。
用户A装置及用户装置B分别具有的椭圆曲线运算部，与实施 方式1的点发行装置200具有的椭圆曲线运算部相同。
下面，利用图16中所示的流程图，对密钥共有系统的操作进行 说明。
管理中心装置，对椭圆曲线E的系数及基点进行选择(步骤 S311)，对素数p、椭圆曲线E的系数及基点B进行公开涉骤S312)。
用户A装置，设定私钥xA(步骤S301)，计算公钥￥人=^*8(步 骤S302)，将公钥YA发送给用户B装置(步骤S303)。
另一方面，用户B装置，设定私钥xB(步骤S321),计算公钥 YB^BfB(步骤S322)，将公钥YB发送给用户A装置(步骤S323)。
用户A装置，计算共有密钥xA丰YBKxAXxB^B(步骤S304)。
用户B装置，计算共有密钥xB+YAKxBXxA^B(步骤S324)。
此处，共有密钥xB承YA-(xBXxA^B
=(xAXxB)*B =共有密钥xA*YB
这样，用户A装置和用户B装置可以取得同一共有密钥，而不 让第三者知道。
6、实施方式1的效果
在实施方式1的点发行装置200具有的椭圆曲线运算部208中， 由于椭圆曲线加法运算部226及椭圆曲线2倍运算部227分别以相同 的顺序执行相同运算(参照图4 图5)，所以分析功率波形的攻击者， 不能根据功率波形区别是执行了椭圆曲线加法运算及椭圆曲线2倍 运算中的哪一个。
另外，标量乘法运算部229，由于椭圆曲线加法运算及椭圆曲线 2倍运算的运算次数的合计不因对计数器c的w_c的值而改变，同样 是4次，所以椭圆曲线加法运算及椭圆曲线2倍运算的运算次数的合 计不因幂乘系数的值而改变，是相同的。从而，即使在攻击者知道运 算次数时，有关幂乘系数的信息也不会泄漏给攻击者。因此，实施方 式l，对简单功率分析攻击是安全的。
另外，当Window的宽度s『3时，存放在表存放部228的表中 的点，除了P一^C之外，只有P一2-3W—点。而在现有的简单功率 分析攻击对策方法中，存放在表存放部228的表中的点，除了PJ-C
之外，是？_2、 P—3、 P—4的3点，实施方式1与现有方法相比，表的 尺寸削减到了 1/3。
在实施方式1中，对每个sw比特的分割信息保持运算次数的合 计一定，但是也可以对1个幂乘系数的运算整体保持运算次数合计一 定。这时，为了在1个幂乘系数的运算整体上调整运算次数，应一边 测量运算次数一边进行运算处理。与此相比，在实施方式1中，每个 sw比特保持运算次数的合计一定，即使对1个幂乘系数的运算整体 也不必注意运算次数，具有控制容易的效果。
上述效果，对实施方式2及3也相同。
7、其他变形例
上述说明的各实施方式，只是本发明实施的一例，本发明并不限 于这些实施方式，只要在不脱离其宗旨的范围内，可以以各种形式实 施。例如，以下的情况也包括在本发明内。
(1) 在实施方式1中，表生成部225使用椭圆曲线加法运算部226 和椭圆曲线2倍运算部227，对椭圆曲线加法运算及和椭圆曲线2倍 运算进行计算，但是，表生成部225也可以执行除去了椭圆曲线加法 运算部226及椭圆曲线2倍运算部227中的伪运算之后的通常的椭圆 曲线加法运算及椭圆曲线2倍运算。
(2) 在实施方式中，sw=3，但是sw也可以是2及4以上的值。这 时，在标量乘法运算部229中，与w^值相对应的Window运算滩 当于图10 图11的步骤S157、步骤S161 S168)，按以下进行。
在与w—c值相对应的Window运算中，进行(sw+l)次基本运算。 (i)当w一c为0以外的情况、且存在满足w一c可用2、除开而用 2、t+l)除不开的非负整数t时，在(sw+l)次基本运算中，从最初开始 第(sw-t+l)次的基本运算进行R —ECA(R， sgn(w_c)*P—((abs (w—c/2At)+l)/2))，在(sw+l)次基本运算中，其他sw次基本运算进行R —ECD(R)。
此处，sgn(w—c)是w—c的符号。当w—c〉0时，sgn(w—c)=l，当 w—c < 0时,sgn(w_c)=-1 。
abs(wj;)是w一c的绝对值。
(ii)当w_c=0时，进行sw次R—ECD(R)的基本运算，然后执行D —ECA(R， P_l)。例如，当s『5， w—c;12时，执行R—ECD(R)， R 一ECD(R)， R—ECD(R)， R—ECA(R,-P—2), R—ECD(R)， R—ECD(R)。
当s『2时，由于除PJ夕卜，不存在表中包含的点，所以不必新 计算点去求表的要素。因此，也可以没有表生成部225及表存放部 228,包括也可以没有表生成部225的处理。这时，表的尺寸，由于 没有除P一1之外的点，所以为O，减小表程度的效果是显著的。
(3)图12表示了 sw=3时的运算变换表320。这里，图17表示sw=4 时的运算变换表330。
此处，由于Window的宽度为"4比特"，所以w_c取"0"、
1 ，，"2""g，,"4，'"5，，"6，，《7，， w y
"_6" 、 "-5"、"画4"、"画3" 、 "-2"及"國l" , 16个值中的一个。
下面，当w—c取各值时，对现有的Window运算、标量乘法运算 部229的Window运算、基本运算顺序及基本运算次数进行说明。
(a)当w_c=0时
对w—c=0的现有Window运算，是"R—24R" 。 "R—24R"表 示使变量R的值，向高位移位Window宽度所示的比特数(此处为4 比特)。
另一方面，对w—c=0的标量乘法运算部229的Window运算，是 "R—24R"及"D—R+C"。此处关于"R—24R"，如上所述。另夕卜， "D—R+C"是伪的加法运算，目的是为了使w—c=0时的Window运 算所包含的基本运算的种类及其数量，与其他情况中的(即w_C#0时 的)Window运算基本包含的基本运算的种类及其数量一致。
此处，"R—24R"，在标量乘法运算部229中，通过R—2XR、 R—2XR、 R—2XR、 R—2XR进行运算。
这一运算通过24R=2 X (2 X (2 X (2 X R)))进行。
从而，在对w—c=0的标量乘法运算部229进行的Window运算中， 按照2倍运算、2倍运算、2倍运算、2倍运算、伪加法运算的顺序，
进行多个基本运算。
这样,对w c=0的标量乘法运算部229进行的Window运算所包
含的基本运算个数为"5"。
(b) w_c=l、 3、 5、 7、 -7、 -5、 -3、 -1时
在w—c=l、 3、 5、 7、 -7、 -5、 -3、 -1时，J见有的Window运算， 分别是"R—24R+C"、 "R—24R+3C"、 "R—24R+5C"、 "R—24R+7C"、 "R—24R-7C" 、 "R—24R-5C" 、 "R—24R-3C" 、 "R—24R-1C"。
"R—24R+C"表示使变量R的值，向高位移位Window宽度所示 的比特数(此处为4比特)，此后变量R加C。关于其他运算也相同。
另外，w—c=l、 3、 5、 7、 -7、 -5、 -3、 -1时的标量乘法运算部229 的Window运算，与现有的Window运算相同。
这时的标量乘法运算部229的各Window运算，按2倍运算、2 倍运算、2倍运算、2倍运算、加法运算的顺序，进行多个基本运算。
这时的标量乘法运算部229进行的Window运算所包含的基本运 算个数为"5"。
(c) w—c=2、 4、 6、 8、 -6、 -4、画2时
在w—c=2、 4、 6、 8、 -6、 -4、 -2时，现有的Window运算，分别 是"R—24R+2C"、 "R—24R+4C"、 "R—24R+6C" 、 "R—24R+8C"、 "R—24R-6C" 、 "R—24R-4C" 、 "R—24R-2C"。
"R—24R+2C"表示使变量R的值，向高位移位Window宽度所 示的比特数(此处为4比特)，此后变量R加2C。关于其他运算也相 同。
另外，w—c=2、 4、 6、 8、 -6、 -4、 -2时的标量乘法运算部229的 Window运算，分别是"R—2(23R+Q" 、 "R—22(22R+C)" 、 "R— 2(23R+3C)"、 "R—23(2R+C)" 、 "R—2(23R-3C)" 、 "R—22(22R-C)"、 "R—2(23R-C)"。这些运算结果与现有的Window运算的结果相同。
此处，例如w一c-2时的"R—2(23R+C)"，在标量乘法运算部229 中，通过R—2XR、 R—2XR、 R—2XR、 R—R+C、 R—2XR进行运算。
从而，对w_c=2时的标量乘法运算部229的各Window运算，按 2倍运算、2倍运算、2倍运算、加法运算、2倍运算的顺序，进行多 个基本运算。
这样，对w_c=2的标量乘法运算部229进行的Window运算所包 含的基本运算个数为"5"。
在w—c=4、 6、 8、 -6、 -4、 -2时，也如图17所示。
(4) 在各实施方式中，将幂乘系数全部按每个sw比特的一定比特 串进行分割，生成sw比特的分割信息，但是也不限于此。比特数也 可以不固定。当分割信息的比特数不一定时，采用分割信息的标量乘 法运算部的运算处理也可以不是一定次数。这时每个分割信息的运算 处理次数，也可以取决于分割信息的比特长，但是不取决于除此之外 的分割信息的比特长以外的信息。
当分割信息的比特数为a比特长时，对应于分割信息值的 Window运算部，依次进行(a+l)次运算。此处，上述多个运算中第 (a-t+l)次运算，是椭圆曲线E上的上述加法运算，其他运算是椭圆曲 线E上的2倍运算。
而当分割信息的比特数为b比特长时(此处，a^b)，对应于分割 信息值的Window运算部，依次进行(b+l)次运算。此处，上述多个运 算中第(b-t+l)次运算，是椭圆曲线E上的上述加法运算，其他运算是 椭圆曲线E上的2倍运算。
(5) 在各实施方式中，当w—c-0时，在sw次R—ECD(R)的基本 运算之后，执行了D—ECA(R， P—1)，但是伪运算处理既可以是与其 他点的加法运算，也可以是椭圆曲线2倍运算。
(6) 在各实施方式中，方程式使用了 yA2=xA3+aXx+b形式的 Weierstrass型椭圆曲线，使用了 Jacobian坐标，但是并不限于此。例 如也可以使用其他坐标(Projective坐标)。这时也可以附加伪运算，不 能区别椭圆曲线加法运算和椭圆曲线2倍运算。另外，也可以将椭圆 曲线2倍运算置换成椭圆曲线加法运算，使用可以运算的Hessian椭 圆及Jacobian椭圆。这时在椭圆曲线加法运算和椭圆曲线2倍运算的 内部运算中也可以没有伪运算。
(7) 在各实施方式中，使用椭圆曲线执行幂乘运算，但是也可以执 行超椭圆曲线或其他代数曲线的Jacobian群的幂乘运算。
(8) 本发明也可以将各实施方式的椭圆曲线运算部用于椭圆
ElGamal加密、PSEC-KEM及其他椭圆曲线或其他代数曲线上的加密 方式中。
例如，也可以在将加密方式的加密算法中的私钥作为幂乘系数的 幂乘运算中，使用各实施方式的椭圆曲线运算部，在将加密方式的解 密算法中的私钥作为幂乘系数的幂乘运算中，使用各实施方式的椭圆 曲线运算部。
另外，在椭圆DSA签名方式、椭圆ElGamal签名方式、椭圆NR 签名方式、椭圆MR签名方式、椭圆PV签名方式、椭圆AO签名方 式等椭圆曲线上的签名方式，或代数曲线的签名方式中，也可以使用 各实施方式的椭圆曲线运算部。
如上所述，在以椭圆曲线上的签名方式的签名生成算法中的随机 数为幂乘系数的幂乘运算中，也可以使用椭圆曲线运算部。
关于椭圆ElGamal加密及椭圆DSA签名方式，在非专利文献3 中有详细叙述。
(9)在实施方式1的点发行系统10中，用户购买商品或接受提供 的服务时，作为从销售方及服务提供方接受的优惠信息，然后在用户 购买商品或接受提供的服务时，以对销售方及服务提供方的等价支付 的一部分或全部利用的点，作为秘密通信对象，点发行装置200对生 成的点进行加密，并将加密点发送给IC卡100， IC卡100对加密点 进行解密，生成解密点，并对生成的解密点进行存储。
但是，秘密通信的对象，并不限于上述的点。
也可以适用于如下所述的现金结算系统。
例如，以可以代替现金使用的电子货币为秘密通信对象，IC卡 存储电子货币，用户在购买商品时，IC卡对相当于商品购买金额的 电子货币进行加密并发送，并从内部存储的电子货币中减去发送的部 分。代替点发行装置200具有同样构成的收银装置，接收加密电子货 币，对接收的加密电子货币进行解密，再现电子货币、并存储。
另外，代替上述IC卡，也可以是用于利用美术馆及博物馆等各 种设施的IC卡类型的电子票，如上所述，存储相当于电子货币的信 息。各种设施的入口设置的入场管理装置，请求支付相当于各种设施 使用费用的电子货币，上述电子票对所请求金额的电子货币进行加密 并发送，入场管理装置，接收加密电子货币，对接收的加密电子货币 进行解密，生成电子货币，进行存储。
另外，也可以是利用铁路、公交车等交通工具时所使用的ic卡
类型的IC卡车票，如上所述，存储相当于电子货币的信息。交通机
构车站的入口所设置的入场管理装置，发送识别该站的识别信息，ic
卡车票接收、存储上述识别信息。交通机构车站的出口设置的出口管
理装置，从IC卡车票接收上述识别信息，利用接收的识别信息和设
置该出口管理装置的站，通过收费表，计算乘车金额，请求支付相当
于计算出的乘车收费金额的电子货币，ic卡车票，对请求金额的电
子货币进行加密并发送，出口管理装置接收加密电子货币，对接收的 加密电子货币进行解密，生成、存储电子货币。
在上述的加密及解密中，椭圆曲线上的离散对数问题用作安全性 的根据，进行椭圆幂乘运算。进行该椭圆幂乘运算的各装置，具有与
椭圆曲线运算部208相同的椭圆曲线运算部。
上述各装置，是在以素数p为模的剩余域F上所定义的椭圆曲线 E上的离散对数问题作为根据，利用椭圆曲线E上的点C乘以作为小 于素数p的正整数的系数k、算出点HC的椭圆曲线运算，对信息进 行安全处理的信息安全装置。
(10) 在上述的现金结算系统中，对于所发送的现金金额、发送源、 发送目的地等，有时要求其正当性的证明。这时，可使用实施方式2 中所示的数字签名及签名验证。
在这样的数字签名及签名验证中，椭圆曲线上的离散对数问题用 作安全性的根据，进行椭圆幂乘运算。进行该椭圆幂乘运算的各装置 具有与椭圆曲线运算部208相同的椭圆曲线运算部。
上述的各装置，是以素数p为模的剩余域F上所定义的椭圆曲线 E上的离散对数问题为根据，利用在椭圆曲线E上的点C乘以作为小 于素数p的正整数的系数k、计算点WC的椭圆曲线运算，可靠地处 理信息的信息安全装置。
(11) 秘密通信的对象不限于上述的点及电子货币等。
本发明，可适用于在由内容加密装置和内容再现装置构成的内容 分配系统中，例如也可以将电影、动态图像、声音、音乐、小说、数 据库等数字信息作为秘密通信的对象。这些内容，可从内容提供者对 用户，通过销售、租赁记录了这些内容的记录媒体进行提供。另外， 可通过数字广播及互联网从内容提供者提供给用户。
内容提供者持有的内容加密装置，对作为数字作品的电影进行加
密，记录在DVD上，用户持有的内容再现装置，从DVD读出加密 的数字作品，解密后生成电影,将生成的电影以声音及影像进行再现、 显示及输出。
在上述的加密及解密中，椭圆曲线上的离散对数问题用作安全性 的根据，进行椭圆幂乘运算。进行该椭圆幂乘运算的内容加密装置及 内容再现装置，具有与椭圆曲线运算部208相同的椭圆曲线运算部。
在上述的例子中，也可以将对内容进行加密及解密的内容密钥， 作为实施方式1中所示的秘密通信的对象。这时，内容密钥与实施方 式1中所示的方法同样，进行加密及解密。
这时，内容通过内容密钥，使用下述的共用密钥加密方式，进行 加密及解密。
上述的各装置，是以素数p为模的剩余域F上所定义的椭圆曲线 E上的离散对数问题为根据，利用在椭圆曲线E上的点C乘以作为小 于素数p的正整数的系数k、计算点1^C的椭圆曲线运算，安全地处 理信息的信息安全装置。
(12)在上述的内容分配系统中，对数字作品进行加密时使用的加 密技术，例如也可以使用DES(Data Encryption Standard:数据加密标 准)或AES(Advanced Encryption Standard:高级加密标准)。DES及 AES等加密技术被称为所谓共用密钥加密方式(或私钥加密方式)。
在上述内容分配系统中，在采用这种共用密钥加密方式时，在构 成内容分配系统的加密装置和再现装置之间，如何安全共有同一私钥 是一个课题。
实施方式3中所示的密钥共有系统，提供了解决这一课题的方法。
通过实施方式3中所示的密钥共有系统，在内容加密装置(相当 于实施方式3的用户A装置)和内容再现装置(相当于实施方式3的用 户B装置)之间，共有不让第三者知道的私钥，此后使用共有密钥加 密方式的加密算法，在内容加密装置中，使用共有的私钥，对数字作 品进行加密，生成加密数字作品，然后，在内容再现装置中，使用共 有的私钥，对加密数字作品进行解密。
在上述的密钥共有中，椭圆曲线上的离散对数问题用作安全性的 根据，进行椭圆幂乘运算。进行该椭圆幂乘运算的内容加密装置及内 容再现装置，具有与椭圆曲线运算部208相同的椭圆曲线运算部。
(13)上述的各实施方式及变形例，可适用于以下所示的情况。
(a) 各实施方式及变形例，在秘密的消息传输中使用。关于这一 点， 在上述记载中以秘密通信进行了说明。
(b) 各实施方式及变形例，可在认证中使用。所谓认证是指消息是 否由如自称那样的人物发送、及消息未被篡改的验证。另外，各实施 方式及变形例可在身份的证明中使用。身份证明，是指例如是否具有 对数据库的访问权、或对设施的访问权(入室权)的证明，或者本人是 否是所说的人物的证明。另外，各实施方式及变形例还可在防止否认 中使用。所谓防止否认，是指例如用于对抗实际已同意某个事、但却 声称未同意的人。
(c) 各实施方式及变形例，在密钥交换中使用。所谓密钥交换，是 指例如两个人使用广播电波并同意用于在某个私钥加密方式中使用 的私钥。在上述记载中以密钥共有进行了说明。
(d) 各实施方式及变形例，可在掷硬币(也称作Bit Commitment: 比特承诺)中使用。所谓掷硬币，例如住在不同城市的2个国际象棋 手，用电子邮件决定谁执白。
(e) 各实施方式及变形例，可以在秘密共享中使用。所谓秘密共享， 是指例如，某个秘密信息，可以由共同工作的k个人利用，但k-l个 人却不能利用。
(f) 各实施方式及变形例，可以在零知识证明中使用。所谓零知识 证明，是指例如某个人对已成功解决数论或组合论的问题的事，仅通 过提供解是什么这样一点信息，而使他人相信此事。
(14) 上述各装置，具体地说是由微处理器、ROM、 RAM、硬盘 单元、显示器单元、键盘、及鼠标器等构成的计算机系统。在上述 RAM或上述硬盘中存储计算机程序。此处，计算机程序，为了实现 规定的功能，由多个表示对计算机的命令的指令代码组合构成。通过 上述微处理器按上述计算机程序操作，各装置实现各功能。即，上述 微处理器1个1个读出上述计算机程序中所包含的指令，解读读出的 指令，根据解读结果进行操作。
(15) 构成上述各装置的构成要素的一部分或全部，也可以由1个 系统LSI(Large Scale Integration:大规模集成电路)构成。系统LSI是 将多个构成部集成在1个芯片上制造的超多功能的LSI,具体地说是 包括微处理器、ROM、 RAM等构成的计算机系统。在上述RAM中 存储计算机程序。通过上述微处理器根据上述计算机程序进行操作， 系统LSI实现其功能。
另外，构成上述各装置的构成要素的各部分，即可以分别作成l 个芯片，也可以单片化使其包含1部分或全部。此处，LSI因集成度 不同，也有的称为IC、系统LSI、超LSI、甚LSI。
另外，集成电路化的方法并不限于LSI，也可以用专用电路或通 用处理器实现。也可以在LSI制造后，利用对可以编程的FPGA(Field Programmable Gate Array:现场可编程门阵列)及LSI内部的电路单元 的连接及设定进行再构成的可重构处理器。
(16) 构成上述各装置的构成要素的一部分或全部，也可以由可以 在各装置上装卸的IC卡或单体模块构成。上述IC卡或上述模块，是 由微处理器、ROM、 RAM等构成的计算机系统。上述IC卡或上述 模块，也可以包括上述超多功能LSI。通过微处理器根据计算机程序 进行操作，上述IC卡或上述模块实现其功能。该IC卡或该模块也可 以具有防篡改性。
(n)本发明也可以作为上述所示的方法。这些方法既可以是由计
算机实现的计算机程序，也可以是由上述计算机程序构成的数字信 号。
另外，本发明，也可以将上述计算机程序或上述数字信号记录在
计算机可以读取的记录媒体，例如软盘、硬盘、CD-ROM、 MO、 DVD、 DVD-ROM、 DVD-RAM、 BD(Blu-ray Disc:蓝光光盘)、半导体存储 器等中。另外，也可以是在这些记录媒体上所记录的上述计算机程序 或上述数字信号。
另外，本发明将上述计算机程序或上述数字信号通过电气通信线 路、无线或有线通信线路、以互联网为代表的网络、数据广播等进行 传输。
另外，本发明也可以是具有微处理器和存储器的计算机系统，上 述存储器存储上述计算机程序，上述微处理器根据上述计算机程序进 行操作。
另外，也可以通过将上述程序或上述数字信号存储在上述记录媒 体上进行转移，或经过上述网络等将上述程序或上述数字信号进行转 发，由独立的其他计算机系统实施。
(18)如上所述，本发明，是对预先赋予的秘密信息和作为输入的 椭圆曲线上的点，执行椭圆曲线上的标量乘法运算的椭圆曲线运算装 置，其特征在于；包括对上述秘密信息进行分割，生成分割信息的 分割信息生成部；对于2个上述椭圆曲线上的点，生成在上述椭圆曲 线的群上加法运算之后的结果所得到的点的椭圆曲线加法运算部；对 于1个上述椭圆曲线上的点，生成在上述椭圆曲线的群上2倍之后的 结果所得到的点的椭圆曲线2倍运算部；以及根据第1上述椭圆曲线 上的点和上述分割信息，使用上述椭圆曲线加法运算部和上述椭圆曲 线2倍运算部，生成第2上述椭圆曲线上的点的标量乘法运算部；上
述标量乘法运算部进行控制，以使得使用上述椭圆曲线加法运算部和
上述椭圆曲线2倍运算部的次数合计后的值不依赖于上述秘密信息
的比特长以外的信息而保持一定，上述椭圆曲线加法运算部和上述椭
圆曲线2倍运算部中的每个，具有执行椭圆曲线定义域上的乘法运算 的乘法运算单元、执行上述定义域上的2次方运算的2次方运算单元、 执行上述定义域上的加法运算的加法运算单元，上述椭圆曲线加法运 算部和上述椭圆曲线2倍运算部执行的上述乘法运算、上述2次方运算及上述加法运算的顺序相同。
此处，也可以是，上述标量乘法运算部，根据一个上述分割信息，
进行控制，以使得使用上述椭圆曲线加法运算部和上述椭圆曲线2倍 运算部的次数合计后的值不依赖于上述分割信息的比特长以外的信 息而保持一定。
此处，也可以是，上述椭圆曲线运算装置，还具有表生成部，该 表生成部对1个以上预先赋予的正整数，计算以上述正整数为标量的 上述椭圆曲线上的点的标量乘法点，将其结果的每个存放在表中，在 上述椭圆曲线加法运算部使用的2个上述椭圆曲线上的点之中，至少 一个是上述表中所存放的上述标量乘法点。
此处，也可以是，上述分割信息生成部，将上述秘密信息分割成 具有预先赋予的比特数的多个上述分割信息。
此处，也可以是，上述椭圆曲线2倍运算部，具有执行对计算结 果无影响的伪的上述乘法运算的伪乘法运算单元。
此处，也可以是，上述椭圆曲线2倍运算部，具有将定义域的元 的2次方运算的结果，使用上述元和上述元的乘法运算得到的2次方 运算代替单元。
此处，也可以是，上述正整数是奇数。
此处，也可以是，上述分割信息生成部，生成多个sw比特的上 述分割信息，上述标量乘法运算部，执行(sw+l)次运算处理，当上述 分割信息w是0以外、并且上述分割信息w由2At(t为非负整数)除得 开而由2A(t+l)除不开时，第(sw-t+l)个上述运算处理使用上述椭圆曲 线加法运算部，其他上述运算处理使用上述椭圆曲线2倍运算部。
本发明，是对预先赋予的秘密信息和作为输入的椭圆曲线上的 点，执行椭圆曲线上的标量乘法运算的椭圆曲线运算方法，其特征在 于；包括对上述秘密信息进行分割，生成分割信息的分割信息生成 步骤；对于2个上述椭圆曲线上的点，生成在上述椭圆曲线的群上加 法运算之后的结果所得到的点的椭圆曲线加法运算步骤；对于1个上 述椭圆曲线上的点，生成在上述椭圆曲线的群上2倍之后的结果所得 到的点的椭圆曲线2倍运算步骤；以及根据第1上述椭圆曲线上的点
和上述分割信息，使用上述椭圆曲线加法运算步骤和上述椭圆曲线2 倍运算步骤，生成第2上述椭圆曲线上的点的标量乘法运算步骤；上 述标量乘法运算步骤进行控制，以使得使用上述椭圆曲线加法运算步 骤和上述椭圆曲线2倍运算步骤的次数合计后的值不依赖于上述秘 密信息的比特长以外的信息而保持一定，上述椭圆曲线加法运算步骤 和上述椭圆曲线2倍运算步骤中的每个，具有执行椭圆曲线定义域上 的乘法运算的乘法运算单元、执行上述定义域上的2次方运算的2次 方运算单元、执行上述定义域上的加法运算的加法运算单元，上述椭 圆曲线加法运算步骤和上述椭圆曲线2倍运算步骤执行的上述乘法 运算、上述2次方运算及上述加法运算的顺序相同。
此处，也可以是，上述标量乘法运算步骤，根据一个上述分割信 息，进行控制，以使得使用上述椭圆曲线加法运算部和上述椭圆曲线 2倍运算部的次数合计后的值不依赖于上述秘密信息而保持一定。
此处，也可以是，上述椭圆曲线运算方法，还具有表生成步骤， 该表生成步骤对1个以上预先赋予的正整数，计算以上述正整数为标 量的上述椭圆曲线上的点的标量乘法点，将其结果的每个存放在表 中，在上述椭圆曲线加法运算步骤使用的2个上述椭圆曲线上的点之 中，至少一个是上述表中所存放的上述标量乘法点。
此处，也可以是，上述分割信息生成步骤，将上述秘密信息分割 成具有预先赋予的比特数的多个上述分割信息。
此处，也可以是，上述正整数是奇数。
此处，也可以是，上述分割信息生成步骤，生成多个sw比特的 上述分割信息，上述标量乘法运算步骤，执行(sw+l)次运算处理，当 上述分割信息w是0以外、并且上述分割信息w由2、(t为非负整数) 除得开而由2A(t+l)除不幵时，第(sw-t+l)个上述运算处理使用上述椭 圆曲线加法运算步骤，其他上述运算处理使用上述椭圆曲线2倍运算
另外，本发明，是使椭圆曲线运算装置执行的程序，该椭圆曲线 运算装置对预先赋予的秘密信息和作为输入的椭圆曲线上的点，执行 椭圆曲线上的标量乘法运算，其特征在于；该程序使上述椭圆曲线运算装置执行下列步骤对上述秘密信息进行分割，生成分割信息的分 割信息生成步骤；对于2个上述椭圆曲线上的点，生成在上述椭圆曲 线的群上加法运算之后的结果所得到的点的椭圆曲线加法运算步骤； 对于1个上述椭圆曲线上的点，生成在上述椭圆曲线的群上2倍之后 的结果所得到的点的椭圆曲线2倍运算步骤；以及根据第1上述椭圆 曲线上的点和上述分割信息，使用上述椭圆曲线加法运算步骤和上述 椭圆曲线2倍运算步骤，生成第2上述椭圆曲线上的点的标量乘法运 算步骤；上述标量乘法运算步骤进行控制，以使得使用上述椭圆曲线 加法运算步骤和上述椭圆曲线2倍运算步骤的次数合计后的值不依 赖于上述秘密信息的比特长以外的信息而保持一定，上述椭圆曲线加 法运算步骤和上述椭圆曲线2倍运算步骤中的每个，具有执行椭圆曲 线定义域上的乘法运算的乘法运算单元、执行上述定义域上的2次方 运算的2次方运算单元、执行上述定义域上的加法运算的加法运算单 元，上述椭圆曲线加法运算步骤和上述椭圆曲线2倍运算步骤执行的 上述乘法运算、上述2次方运算及上述加法运算的顺序相同。
此处，也可以是，上述标量乘法运算步骤，根据一个上述分割信 息，进行控制，以使得使用上述椭圆曲线加法运算部和上述椭圆曲线 2倍运算部的次数合计后的值不依赖于上述秘密信息而保持一定。
此处，也可以是，上述椭圆曲线运算方法，还具有表生成步骤， 该表生成步骤对1个以上预先赋予的正整数，计算以上述正整数为标 量的上述椭圆曲线上的点的标量乘法点，将其结果的每个存放在表 中，在上述椭圆曲线加法运算步骤使用的2个上述椭圆曲线上的点之 中，至少一个是上述表中所存放的上述标量乘法点。
此处，也可以是，上述分割信息生成步骤，将上述秘密信息分割 成具有预先赋予的比特数的多个上述分割信息。
此处，也可以是，上述正整数是奇数。
此处，也可以是，上述分割信息生成步骤，生成多个sw比特的 上述分割信息，上述标量乘法运算步骤，执行(sw+l)次运算处理，当 上述分割信息w是0以外、并且上述分割信息w由2At(t为非负整数) 除得开而由2A(t+l)除不开时，第(sw-t+l)个上述运算处理使用上述椭
圆曲线加法运算步骤，其他上述运算处理使用上述椭圆曲线2倍运算
7 另外，本发明，是对预先赋予的秘密信息和作为输入的椭圆曲线 上的点执行椭圆曲线上的标量乘法运算的椭圆曲线运算装置的集成 电路，其特征在于；包括对上述秘密信息进行分割，生成分割信息 的分割信息生成部；对于2个上述椭圆曲线上的点，生成在上述椭圆 曲线的群上加法运算之后的结果所得到的点的椭圆曲线加法运算部； 对于l个上述椭圆曲线上的点，生成在上述椭圆曲线的群上2倍之后 的结果所得到的点的椭圆曲线2倍运算部；以及根据第1上述椭圆曲 线上的点和上述分割信息，使用上述椭圆曲线加法运算部和上述椭圆 曲线2倍运算部，生成第2上述椭圆曲线上的点的标量乘法运算部； 上述标量乘法运算部进行控制，以使得使用上述椭圆曲线加法运算部 和上述椭圆曲线2倍运算部的次数合计后的值不依赖于上述秘密信 息的比特长以外的信息而保持一定，上述椭圆曲线加法运算部和上述 椭圆曲线2倍运算部中的每个，具有执行椭圆曲线定义域上的乘法运 算的乘法运算单元、执行上述定义域上的2次方运算的2次方运算单 元、执行上述定义域上的加法运算的加法运算单元，上述椭圆曲线加 法运算部和上述椭圆曲线2倍运算部执行的上述乘法运算、上述2次 方运算及上述加法运算的顺序相同。
此处，也可以是，上述标量乘法运算部，根据一个上述分割信息， 进行控制，以使得使用上述椭圆曲线加法运算部和上述椭圆曲线2倍 运算部的次数合计后的值不依赖于上述秘密信息而保持一定。
G9)也可以将上述实施方式及上述变形例分别进行组合。
(产业上的可利用性)
如上所述，根据本发明，可以防止由简单功率分析攻击而造成的 安全性下降。
构成本发明的各装置、各方法及各计算机程序，在需要对信息进 行安全可靠处理的所有产业中，可以经营性地、持续地及反复地使用。 另外，构成本发明的各装置，在电器设备制造产业中，可以经营性地、 持续地及反复地制造、销售。
权利要求
1、一种信息安全装置，以将素数p作为模的剩余域F上所定义的椭圆曲线E上的离散对数问题为根据，利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k来计算出点k*C的椭圆曲线运算，安全而可靠地处理信息，其特征在于，包括点存储单元，存储椭圆曲线E上的点C；位存储单元，存储系数k的所有位的值；取得单元，从位存储单元取得1个位的值w；乘法运算单元，其数量与取得的上述位所能表示的值的种类的数量相同；选择单元，选择与取得的上述位的值w相对应的乘法运算单元；以及重复控制单元，对于系数k的所有的位，对上述取得单元、上述选择单元及上述乘法运算单元进行控制，以便重复地进行1个位的值w的取得、与取得的位的值w相对应的乘法运算单元的选择、以及所选择的乘法运算单元进行的乘法运算，各乘法运算单元，在椭圆曲线E上，将上述点C乘以取得的上述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行加法运算，当存在满足取得的上述位的值w用2t除得开、而用2t+1除不开的条件的非负整数t时，与该位的值w相对应的上述乘法运算单元，在椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法运算或点Q乘以|w/2t|而得的点的减法运算的运算。
2、 如权利要求1所述的信息安全装置，其特征在于 取得的上述位为sw比特长，当存在上述非负整数t时，与上述位的值w相对应的上述乘法运 算单元，依次进行(sw+l)次运算，在上述多个运算中的第(sw-t+l)个 运算，是椭圆曲线E上的上述加法运算或上述减法运算，其他运算是 椭圆曲线E上的2倍运算。
3、 如权利要求2所述的信息安全装置，其特征在于 上述信息安全装置还包括表生成单元，该表生成单元以点Q为 初始的加法运算点，通过重复进行对加法运算点加上2*Q而得到新 的加法运算点的运算，从而生成除点Q之外的2SW"个加法运算点；当存在非负整数t时,与该位的值w相对应的上述乘法运算单元， 使用由上述表生成单元所生成的上述加法运算点，作为点Q乘以w/21 或lw/2l而得到的点。
4、 如权利要求2所述的信息安全装置，其特征在于 取得的上述位是3比特长，当上述位的值w为2时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、加法运算及2倍运算，上述加法运算 是加上上述点C的运算，当上述位的值w为4时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、加法运算、2倍运算及2倍运算，上述加法运算 是加上上述点C的运算，当上述位的值w为-2时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、减法运算及2倍运算，上述减法运算 是减去上述点C的运算。
5、 如权利要求2所述的信息安全装置，其特征在于 取得的上述位是4比特长，当上述位的值w为2时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、2倍运算、加法运算及2倍运算，上 述加法运算是加上上述点C的运算，当上述位的值w为4时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、加法运算、2倍运算及2倍运算，上 述加法运算是加上上述点C的运算，当上述位的值w为6时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、2倍运算、加法运算及2倍运算，上 述加法运算是加上点3*C的运算，当上述位的值w为8时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、加法运算、2倍运算、2倍运算及2倍运算，上 述加法运算是加上上述点c的运算，当上述位的值w为-6时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、2倍运算、减法运算及2倍运算，上 述减法运算是减去点3*C的运算，当上述位的值w为-4时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、减法运算、2倍运算及2倍运算，上 述减法运算是减去点C的运算，当上述位的值w为-2时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、2倍运算、减法运算及2倍运算，上 述减法运算是减去点C的运算。
6、 如权利要求2所述的信息安全装置，其特征在于 上述加法运算或上述减法运算及上述2倍运算，分别包括伪运算，使得它们以相同顺序执行相同种类的运算。
7、 如权利要求1所述的信息安全装置，其特征在于 当取得的上述位是a比特长时，在存在上述非负整数t时，与上述位的值w相对应的上述乘法运算单元，依次进行(a+l)次运算，在 上述多个运算中的第(a-t+l)个运算是椭圆曲线E上的上述加法运算或 上述减法运算，其他运算是椭圆曲线E上的2倍运算，当取得的上述位是b比特长时，在存在上述非负整数t时，与上 述位的值w相对应的上述乘法运算单元，依次进行(b+l)次运算，在 上述多个运算中的第(b-t+l)个运算是椭圆曲线E上的上述加法运算 或上述减法运算，其他运算是椭圆曲线E上的2倍运算。
8、 如权利要求1所述的信息安全装置，其特征在于 上述信息安全装置是加密装置，采用计算点k*C的椭圆曲线运算，对信息进行加密。
9、 如权利要求1所述的信息安全装置，其特征在于 上述信息安全装置是解密装置，采用计算点k*C的椭圆曲线运算，对加密的信息进行解密。
10、 如权利要求1所述的信息安全装置，其特征在于上述信息安全装置是数字签名生成装置，采用计算点wc的椭圆曲线运算，对信息进行数字签名。
11、 如权利要求1所述的信息安全装置，其特征在于 上述信息安全装置是数字签名验证装置，釆用计算点k*C的椭圆曲线运算，进行数字签名的验证。
12、 如权利要求1所述的信息安全装置，其特征在于-上述信息安全装置是密钥共有装置，采用计算点k*C的椭圆曲线运算，生成与其他密钥共有装置之间 共有的密钥。
13、 一种椭圆曲线运算装置，以将素数p作为模的剩余域F上所 定义的椭圆曲线E上的离散对数问题为根据，利用在椭圆曲线E上 的点C乘以作为小于素数p的正整数的系数k来计算点k*C，其特征 在于，该椭圆曲线运算装置包括点存储单元，存储椭圆曲线E上的点C; 位存储单元，存储系数k的所有位的值； 取得单元，从位存储单元取得1个位的值W;乘法运算单元，其数量与取得的上述位所能表示的值的种类的数 量相同；选择单元，选择与取得的上述位的值W相对应的乘法运算单元；以及重复控制单元，对于系数k的所有的位，对上述取得单元、上述 选择单元及上述乘法运算单元进行控制，以便重复地进行1个位的值W的取得、与取得的位的值W相对应的乘法运算单元的选择、以及 所选择的乘法运算单元进行的乘法运算，各乘法运算单元，在椭圆曲线E上，将上述点C乘以取得的上 述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行 加法运算，当存在满足取得的上述位的值w用2l除得开、而用2t+1除不开的 条件的非负整数t时，与该位的值w相对应的上述乘法运算单元，在 椭圆曲线E上，进行包括点Q乘以w/》而得到的点的加法运算或点 Q乘以lw/2tl而得的点的减法运算的运算。
14、 一种集成电路，用于椭圆曲线运算，该椭圆曲线运算以将素 数p作为模的剩余域F上所定义的椭圆曲线E上的离散对数问题为根 据，利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的系 数k来计算点"C，其特征在于，该集成电路包括点存储单元，存储椭圆曲线E上的点C;位存储单元，存储系数k的所有位的值； 取得单元，从位存储单元取得1个位的值W;乘法运算单元，其数量与取得的上述位所能表示的值的种类的数 量相同；选择单元，选择与取得的上述位的值w相对应的乘法运算单元；以及重复控制单元，对于系数k的所有的位，对上述取得单元、上述 选择单元及上述乘法运算单元进行控制，以便重复地进行1个位的值 w的取得、与取得的位的值w相对应的乘法运算单元的选择、以及 所选择的乘法运算单元进行的乘法运算，各乘法运算单元，在椭圆曲线E上，将上述点C乘以取得的上 述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行 加法运算，当存在满足取得的上述位的值w用2t除得开、而用2t+1除不开的 条件的非负整数t时，与该位的值w相对应的上述乘法运算单元，在 椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法运算或点 Q乘以lw/2t,得的点的减法运算的运算。
15、 一种方法，用于信息安全装置，该信息安全装置以将素数p 作为模的剩余域F上所定义的椭圆曲线E上的离散对数问题为根据， 利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k 来计算点k*C的椭圆曲线运算，安全而可靠地处理信息,其特征在于上述信息安全装置，包括点存储单元，存储椭圆曲线E上的点C;以及位存储单元，存储系数k的所有位的值，上述方法包括 取得步骤，从位存储单元取得l个位的值w; 乘法运算步骤，其数量与取得的上述位所能表示的值的种类的数 量相同；选择步骤，选择与取得的上述位的值w相对应的乘法运算步骤;以及重复控制步骤，对于系数k的所有的位，对上述取得步骤、上述 选择步骤及上述乘法运算步骤进行控制，以便重复地进行1个位的值 w的取得、与取得的位的值w相对应的乘法运算步骤的选择、以及 所选择的乘法运算步骤中进行的乘法运算，各乘法运算步骤，在椭圆曲线E上，将上述点C乘以取得的上 述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行 加法运算，当存在满足取得的上述位的值w用2t除得开、而用2t+1除不开的 条件的非负整数t时，在与该位的值w相对应的上述乘法运算步骤中， 在椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法运算或 点Q乘以lw/2tl而得的点的减法运算的运算。
16、 一种计算机程序，用于信息安全装置，该信息安全装置以将 素数p作为模的剩余域F上所定义的椭圆曲线E上的离散对数问题为 根据，利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的 系数k来计算点WC的椭圆曲线运算，安全而可靠地处理信息，其特 征在于上述信息安全装置，包括点存储单元，存储椭圆曲线E上的点C;以及位存储单元，存储系数k的所有位的值，上述计算机程序包括取得步骤，从位存储单元取得1个位的值W;乘法运算步骤，其数量与取得的上述位所能表示的值的种类的数 量相同；选择步骤，选择与取得的上述位的值W相对应的乘法运算步骤；以及 重复控制步骤，对于系数k的所有的位，对上述取得步骤、上述 选择步骤及上述乘法运算步骤进行控制，以便重复地进行1个位的值 W的取得、与取得的位的值W相对应的乘法运算步骤的选择、以及 所选择的乘法运算步骤中进行的乘法运算，各乘法运算步骤，在椭圆曲线E上，将上述点C乘以取得的上 述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行 加法运算，当存在满足取得的上述位的值w用除得开、而用2t+1除不开的 条件的非负整数t时,在与该位的值w相对应的上述乘法运算步骤中， 在椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法运算或 点Q乘以lw/2l而得的点的减法运算的运算。
17、如权利要求16所述的计算机程序，其特征在于 上述计算机程序，记录在计算机可读取的记录媒体上。
全文摘要
在保持对简单功率分析攻击的耐受性的同时，可削减使用的表量。IC卡(100)，利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k来计算点k*C的椭圆曲线运算，对加密的信息进行解密。点k*C的运算，是将上述点C乘以取得的系数k的位(Window)的值所得到的相乘结果，在与该位相对应的位置上进行加法运算，并对所有位进行该运算。当存在满足取得的上述位的值可用2<sup>t</sup>除得开，而用2<sup>t+1</sup>除不开的条件的非负整数t时，各位的乘法运算，包括在椭圆曲线E上，点Q乘以w/2<sup>t</sup>所得到的点的加法运算。
文档编号G09C1/00GK101198998SQ20068002185
公开日2008年6月11日 申请日期2006年4月25日 优先权日2005年4月27日
发明者布田裕一, 松崎枣 申请人:松下电器产业株式会社
技术领域：
本发明涉及能够对抗基于功率消耗量测量的功率分析攻击，可以 安全、可靠地对信息进行处理的信息安全技术。
背景技术：
近些年来，在由硬件或软件安装的加密模块中进行加密处理时， 以该加密处理中的各种副信息为线索，对该加密处理中所使用的加密 密钥进行分析的各种破译方法，进行了研究。
例如，在被称为定时攻击的破译方法中，在加密模块中加密处理 所需的时间，根据该加密处理中所用的加密密钥的值，有尽管微小但 确实存在的不同，利用这一点进行该加密密钥的破译。另外，在被称
为Simple Power Analysis(简单功率分析攻击)、及Differential Power Analysis(差分功率分析攻击)的破译方法中，采用进行加密处理时的加 密模块的功率消耗量作为副信息。
已有报告指出，这些破译方法，近些年来可以以便宜的价格得到 高性能的测量设备，即使对安装IC卡这样的加密模块的实际产品也 可以进行分析。
在下面的说明中，以上述的加密处理时的加密模块功率消耗量的 变化，即功率波形为线索，对加密密钥进行分析的破译方法，总称为 "功率分析攻击"。关于定时攻击，在非专利文献1中进行了详细说 明，而关于功率分析攻击，在非专利文献2中进行了详细叙述。
下面，说明对椭圆曲线加密的简单功率分析攻击。关于椭圆曲线 加密，在非专利文献5中进行了详细叙述，另夕卜，关于椭圆ElGamal 加密及椭圆DSA签名方式，在非专利文献3中进行详细叙述。
(椭圆曲线加密的简单功率分析攻击)
在椭圆曲线加密的解密处理中，计算作为正整数的私钥ks和作
为密文一部分的椭圆曲线上的点C的标量乘法点k^C。此处，ks*C 表示将ks个点C相加所得到的椭圆曲线上的点。该计算方法，例如 是已知有在非专利文献5的69页的带符号Window法。下面对带符 号Window法进行说明。以下，设Window的宽度为3比特。
步骤S801:使v—ks，取v—0，v—l,v—2，......，v—b，使v=v_0+v—1
X2A3+v—2X2A6+......+v—bX2A(bX3)。再使v—(b+1)—0。此处，b表
示(len/3以上的最小整数)-l, len表示v的比特数，"X "表示整数 相乘，x、表示x的y次幂。例如len-52时，b=18-l=17。
步骤S802:在以下的步骤S8021 S8026中，生成整数串 {w_i}(i=l， 2， ......， b+l)。
步骤S8021: c—0
步骤S8022:判断是否是v_c〉2A2，当v—c>2A2时，转到步骤 S8023,否则转到步骤S8024。
步骤S8023: w—c—v—c-2A3， v—(c+1)—v_(c+l)+l ，转到步骤S8025 步骤S8024: w—c—v—c 步骤S8025: c—c+1
步骤S8026:判断是否是c〉b+l。当c〉b+l时，转到步骤S803， 否则转到步骤S8022
步骤S803:在以下的步骤S8031 S8035中，生成表(P一i〉。
步骤S8031: P—0—0、 P—2—Dob(C),此处，O表示椭圆曲线的 零源，Dob表示椭圆曲线的2倍运算，Dob(C)是C的2倍点。
步骤S8032: c—3
步骤S8033: P_c—P—(c-l)+C
步骤S8034: c—c+l
步骤S8035:判断是否是0>2"2=4。当c>2A2时，转到步骤S804， 否则转到步骤S8033。
步骤S804:在以下的步骤S8041 S8047中，计算标量乘法点R。 步骤S8041: c—b+l
步骤S8042:判断是否是w—c=0。当 _0=0时，c—c-l。 步骤S8043: R—P—(w一c)
步骤S8044: c—c-l
步骤S8045:判断是否是c〈0。当c〈0时，转到步骤S805。
步骤S8046: R—Dob(Dob(Dob(P—(w—c))))
步骤S8047:判断w—c是正、负还是0。当w_c<0时，R—Add(R， -P_(-w_c》，当w—c>0时，R—Add(R， P_(w_c》，当w—c=0时，什 么也不做。转到步骤S8044,此处Add是椭圆曲线的加法运算，Add(R， P一(wj))是对R和P一(wj)的椭圆曲线的加法运算的结果。
步骤S805:输出R，结束。
在上述方法中，利用整数串(w—力和表(P—i》计算标量乘法点。在 步骤S8047中当w_c=0时，未执行椭圆曲线运算。另夕卜，在步骤S8042 中，当wj-0时，由于不进行椭圆曲线的运算，而减去c，因此这一 部分不执行椭圆曲线的运算。这样，当w_c=0时，与不是这种情况 时处理不同。
(椭圆曲线的2倍运算和椭圆曲线加法运算的公式) 以下，表示椭圆曲线的2倍运算和椭圆曲线加法运算的公式。关 于该公式，在非专利文献4中进行了详细叙述。此处，以点坐标为 Jacobian坐标，进行椭圆曲线的运算(加法运算及2倍运算)。
(a) 椭圆曲线的加法公式
对于P1气X1， Yl， Zl)， P2=(X2, Y2， Z2)，使P3=P1+P2=(X3， Y3, Z3)
X3=-HA3-2 X Ul X H八2+一2 Y3=-S1 XHA3+rX(Ul XHA2-X3) Z3=Z1XZ2XH
其中，U1=X1XZ2A2， U2=X2XZ1A2， S1=Y1XZ2A3， S2=Y2 XZ1A3, H=U1-U2， r=S2-Sl。
(b) 椭圆曲线的2倍运算公式
对于P1气X1， Yl， Zl)，使P4-2氺P1-(X4， Y4， Z4)。 X4=T
Y4=-8XY1A4+MX(S-T) Z4=2XY1XZ1
其中，S=4XX1XY1A2， M=3XXlA2+aXZlA4， T=-2S+MA2。
从上述看出，在椭圆曲线加法运算中，2次方计算执行4次，乘 法执行12次。与此相比，椭圆曲线2倍运算中，2次方计算执行6 次，乘法执行4次。
这样，椭圆曲线计算和椭圆曲线2倍运算，由于2次方计算及乘 法的次数不同，所以加密模块中的消耗功率波形不同。从而，通过观 测功率波形，可以分析椭圆曲线的2倍运算，加法运算的顺序。从该 分析结果，攻击者可以知道有无w_c=0的情况。另外，攻击者可以 根据是否是w_c=0的信息縮小私钥ks的搜索空间。
(现有的对椭圆曲线加密的简单功率分析攻击的对策方法)
在上述的简单功率分析攻击中，利用了在w—c=0时计算处理不 同的情况。为此，为了防御该攻击，只要通过在w—c=0时增加伪计 算处理，使w—c=0时与不是这一情况时的计算处理相同即可。具体 地说，用以下的算法进行计算。
步骤S901: v—ks，取v—0， v—1， v—2， ......， v一b使v=v—0+v_l
X2A3+v—2X2A6+ +v_bX2A(bX3)。再使v—(b+1)—0。此处，b表
示(len/3以上的最小整数)-l ， len表示v的比特数，"X "表示整数 的乘法，xAy表示x的y次方。例如，len-52时，b=18-l=17。
步骤S902:在以下的步骤S9021 S9026中，生成整数串 {w—i}(i=l， 2, ......， b+l)。
步骤S9021: c—0
步骤S9022:判断是否是v_c>2A2，当v_c>2A2时，转到步骤 S9023,否则转到步骤S9024。
步骤S9023: w_c—v—c-2A3， v_(c+l)—v—(c+l)+l ，转到步骤 S9025。
步骤S9024: w—c—v—c
步骤S9025: c—c+1
步骤S9026:判断是否是c〉b+l。当c〉b+l时，转到步骤S903， 否则转到步骤S9022
步骤S903:在以下的步骤S9031 S9035中，生成表(P—i}。
步骤S9031: P_0—0、 P—2—Dob(C)。 步骤S9032: c—3 步骤S9033: P—c—P—(c-l)+C 步骤S9034: c—c+1
步骤S9035:判断是否是c〉2^4。当c〉2A2时，转到步骤S904, 否则转到步骤S9033。
步骤S904:在以下的步骤中，计算标量乘法点R。 步骤S904h c—b+1
步骤S9042 : 判断是否w_c=0 。当w_c=0时，D — Dob(Dob(Dob(C)))， D—Add(R，C)， c—c-l。 步骤S9043: R—P_(w_c) 步骤S9044: c—c-1
步骤S9045:判断是否c〈0。当c〈0时，转到步骤S905。
步骤S9046: R—Dob(Dob(Dob(P_(w—c))))
步骤S9047:判断w_c是正、负还是0。当w—c<0时，R—Add(R， -P_(-w—c))，当w_c>0时，R—Add(R， P_(w—c))，当w—c=0时，D —Add(R,C)。转到步骤S9044,此处Add是椭圆曲线的加法运算， Add(R， P—(w一c))是对R和P—(w—c)的椭圆曲线的加法运算的结果。
步骤S905:输出R，结束。
在上述对简单功率攻击的对策方法中，D是与计算结果没关系的 伪的点，在步骤S9042及步骤S9047执行的Q运算为伪运算。在步 骤S9042中当w—c=0时，执行3次伪椭圆曲线2倍运算和1次伪椭 圆曲线加法运算。即使在不是w—c-O时，也执行步骤S9046的3次 椭圆曲线2倍运算、步骤S9047的1次椭圆曲线加法运算，所以w_c=0 时和w—c^O时执行相同的运算。另外，在步骤S9047,当w^-0时 执行伪的加法，执行与w—c#0时相同的运算。
从而，上述对简单功率攻击的对策方法中，由于w—c=0时也与 w—c#0时执行相同的运算，所以功率波形相同，攻击者根据功率波 形无法知道是否是w_c=0的信息。
非专禾!j文献1: Paul C. Kocher， "Timing attacks on implementations
of Diffie-Hellman， RSA， DSS， and Other Systems", In Neal Koblitz, editor, CRYPTO，96， LNCS 1109， Springer-Verlag, 1996, pp. 104-113.
非专利文献2: P. Kocher， J. Jaffe， and B. Jun， "Differential Power Analysis", Advances in Cryptology-CRYPTO，99， LNCS， 1666， Springer-Verlag, 1999， pp.388-397.
非专利文献3:岡本龍明、山本博資、[現代喑号]、産業図書(1997
年)
非专利文献4: A. Miyaji， T. Ono and H. Cohen， "Efficient elliptic curve exponentiation", ICICS，97， Springer-Verlag, 1999, pp.282-291.
非专利文献5: I. Blake， G. Seroussi andN. Smart, "Elliptic Curves in Cryptography", London Mathematical Society Lecture Note Series 265, CAMBRIDGE UNIVERSITY PRESS, 1999
在上述对简单功率攻击的对策方法中，除P一^P以外，在表中还 存放P—2、 P_3、 P—4三点。但是，在IC卡等资源受限制的状况下， 希望减小表的量。
发明内容
本发明的目的在于提供一种信息安全装置、椭圆曲线运算装置、 方法及计算机程序，在保持对简单功率分析攻击的耐受性的同时，可 以削减使用的表量。
(解决课题的手段)
为了达到上述目的，本发明的信息安全装置，以将素数p作为模 的剩余域F上所定义的椭圆曲线E上的离散对数问题为根据，利用在 椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k来计算 出点PC的椭圆曲线运算，安全而可靠地处理信息，其特征在于，包 括点存储单元，存储椭圆曲线E上的点C;位存储单元，存储系数
k的所有位的值；取得单元，从位存储单元取得1个位的值W;乘法 运算单元，其数量与取得的上述位所能表示的值的种类的数量相同； 选择单元，选择与取得的上述位的值W相对应的乘法运算单元；以 及重复控制单元，对于系数k的所有的位，对上述取得单元、上述选择单元及上述乘法运算单元进行控制，以便重复地进行1个位的值W 的取得、与取得的位的值w相对应的乘法运算单元的选择、以及所
选择的乘法运算单元进行的乘法运算，各乘法运算单元，在椭圆曲线
E上，将上述点C乘以取得的上述位的值w所得到的乘法运算结果， 在与该位相对应的位置上进行加法运算，当存在满足取得的上述位的 值w用2t除得开、而用2W除不开的条件的非负整数t时，与该位的 值w相对应的上述乘法运算单元，在椭圆曲线E上，进行包括点Q 乘以w/2t而得到的点的加法运算或点Q乘以lw/2tl而得的点的减法运 算的运算。
此处，点存储单元相当于实施方式的被运算值存放部224，位存 储单元相当于分割信息存放部223，取得单元相当于取得部241，选 择单元相当于选择部242，多个乘法运算单元分别相当于Window运 算部251 25S，重复控制单元相当于重复控制部243。另外，实施方 式中的Window在此以位(digit)来表示。
(发明的效果)
根据该构成，与该位的值w相对应的上述乘法运算单元，在椭 圆曲线E上，进行包括点Q乘以w/2t所得到的点的加法运算或点Q 乘以lw/2tl所得到的点的减法运算的运算，所以例如当各位的比特长为 3时，在加法运算或减法运算中使用的点，除了C之外，只有3T， 当各位的比特长为4时，加法运算或减法运算中使用的点，除了 C
之外，只有3氺c、 5*<:及7*(:。
按照现有技术，例如当各位的比特长为3时，在加法运算或减法
运算中使用的点，除了c之外，有2*0、 3*(:及4*(:，而当各位的比
特长为4时，在加法运算或减法运算中使用的点，除了 C之外，有 2*C、 3*C、 4*C、 5*C、 6*C、 7*C及8*C。
这样，根据本发明，与现有技术比较，可以减少在加法运算或减 法运算中所使用的点，可以削减使用的表量。
此处，也可以是，取得的上述位为sw比特长，当存在上述非负 整数t时，与上述位的值w相对应的上述乘法运算单元，依次进行 (sw+l)次运算，在上述多个运算中的第(sw-t+l)个运算，是椭圆曲线E
上的上述加法运算或上述减法运算，其他运算是椭圆曲线E上的2 倍运算。
通过这一构成，可得到与现有技术同样的运算结果，并且可以减 少加法运算或减法运算中使用的点的数量。
此处，也可以是，上述信息安全装置还包括表生成单元，该表生 成单元以点Q为初始的加法运算点，通过重复进行对加法运算点加 上2*Q而得到新的加法运算点，从而生成除点Q之外的2SW"个加法 运算点；当存在非负整数t时，与该位的值w相对应的上述乘法运算 单元，使用由上述表生成单元所生成的上述加法运算点，作为点Q 乘以w/2t或lw/2t,得到的点。
通过这一构成，由于通过表生成单元，2sw'1个加法运算点被算出， 所以可以减少乘法运算单元中的运算次数。
此处，也可以是，取得的上述位是3比特长，当上述位的值w 为2时，对应的乘法运算单元依次进行椭圆曲线E上的2倍运算、2 倍运算、加法运算及2倍运算，上述加法运算是加上上述点C的运算， 当上述位的值w为4时，对应的乘法运算单元依次进行椭圆曲线E 上的2倍运算、加法运算、2倍运算及2倍运算，上述加法运算是加 上上述点C的运算，当上述位的值w为-2时，对应的乘法运算单元 依次进行椭圆曲线E上的2倍运算、2倍运算、减法运算及2倍运算， 上述减法运算是减去上述点C的运算。
通过这一构成，在加法运算或减法运算中使用的点，除了 C之外， 只有3*(:，与现有技术比较，可以削减使用的表量。
此处，也可以是，取得的上述位是4比特长，当上述位的值w 为2时，对应的乘法运算单元依次进行椭圆曲线E上的2倍运算、2 倍运算、2倍运算、加法运算及2倍运算，上述加法运算是加上上述 点C的运算，当上述位的值w为4时，对应的乘法运算单元依次进 行椭圆曲线E上的2倍运算、2倍运算、加法运算、2倍运算及2倍 运算，上述加法运算是加上上述点C的运算，当上述位的值w为6 时，对应的乘法运算单元依次进行椭圆曲线E上的2倍运算、2倍运 算、2倍运算、加法运算及2倍运算，上述加法运算是加上点3*C的运算，当上述位的值w为8时，对应的乘法运算单元依次进行椭圆 曲线E上的2倍运算、加法运算、2倍运算、2倍运算及2倍运算， 上述加法运算是加上上述点C的运算，当上述位的值w为-6时，对 应的乘法运算单元依次进行椭圆曲线E上的2倍运算、2倍运算、2 倍运算、减法运算及2倍运算，上述减法运算是减去点3*(:的运算， 当上述位的值w为-4时，对应的乘法运算单元依次进行椭圆曲线E 上的2倍运算、2倍运算、减法运算、2倍运算及2倍运算，上述减 法运算是减去点C的运算，当上述位的值w为-2时，对应的乘法运 算单元依次进行椭圆曲线E上的2倍运算、2倍运算、2倍运算、减 法运算及2倍运算，上述减法运算是减去点C的运算。
通过这一构成，在加法运算或减法运算中使用的点，除了 C之外， 只有3*匚5*<:及7*<:,与现有技术比较，可以削减使用的表量。
此处，也可以是，上述加法运算或上述减法运算及上述2倍运算， 分别包括伪运算，使得它们以相同顺序执行相同种类的运算。
根据该构成，由于加法运算或减法运算及2倍运算，分别以相同 的顺序执行相同种类的运算，所以即使要以功率波形为线索进行分 析，在加法运算或减法运算及2倍运算中，输出同样的功率波形，很 难明确区别2者。这样，可以对抗功率分析攻击。
此处，也可以是，当取得的上述位是a比特长时，在存在上述非 负整数t时，与上述位的值w相对应的上述乘法运算单元，依次进行 (a+l)次运算，在上述多个运算中的第(a-t+l)个运算是椭圆曲线E上的 上述加法运算或上述减法运算，其他运算是椭圆曲线E上的2倍运算， 当取得的上述位是b比特长时，在存在上述非负整数t时，与上述位 的值w相对应的上述乘法运算单元，依次进行(b+l)次运算，在上述 多个运算中的第(b-t+l)个运算是椭圆曲线E上的上述加法运算或上 述减法运算，其他运算是椭圆曲线E上的2倍运算。
根据该构成，即使混合存在不同比特长的位时，也可以进行运算。
此处，也可以是，上述信息安全装置是加密装置，采用计算点 WC的椭圆曲线运算，对信息进行加密。
根据这一构成，可以对抗信息加密时的功率分析攻击。
此处，也可以是，上述信息安全装置是解密装置，采用计算点
PC的椭圆曲线运算，对加密的信息进行解密。
根据这一构成，可以对抗对加密的信息进行解密时的功率分析攻击。
此处，也可以是，上述信息安全装置是数字签名生成装置，采用
计算点k*C的椭圆曲线运算，对信息进行数字签名。
根据这一构成，可以对抗数字签名生成时的功率分析攻击。 此处，也可以是，上述信息安全装置是数字签名验证装置，采用
计算点PC的椭圆曲线运算，进行数字签名的验证。
根据这一构成，可以对抗数字签名验证时的功率分析攻击。 此处，也可以是，上述信息安全装置是密钥共有装置，采用计算
点wc的椭圆曲线运算，生成与其他密钥共有装置之间共有的密钥。
根据这一构成，可以对抗密钥共有时的功率分析攻击。
另外，本发明的椭圆曲线运算装置，以将素数p作为模的剩余域
F上所定义的椭圆曲线E上的离散对数问题为根据，利用在椭圆曲线 E上的点C乘以作为小于素数p的正整数的系数k来计算点k*C，其 特征在于，该椭圆曲线运算装置包括点存储单元，存储椭圆曲线E 上的点C;位存储单元，存储系数k的所有位的值；取得单元，从位 存储单元取得1个位的值W;乘法运算单元，其数量与取得的上述位 所能表示的值的种类的数量相同；选择单元，选择与取得的上述位的 值W相对应的乘法运算单元；以及重复控制单元，对于系数k的所 有的位，对上述取得单元、上述选择单元及上述乘法运算单元进行控 制，以便重复地进行1个位的值W的取得、与取得的位的值W相对 应的乘法运算单元的选择、以及所选择的乘法运算单元进行的乘法运 算，各乘法运算单元，在椭圆曲线E上，将上述点C乘以取得的上
述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行
加法运算，当存在满足取得的上述位的值w用2t除得开、而用2t+1 除不开的条件的非负整数t时，与该位的值w相对应的上述乘法运算 单元，在椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法 运算或点Q乘以lw/2tl而得的点的减法运算的运算。
根据这一构成，与现有技术比较，可以减少在加法运算中所使用 的点，可以削减使用的表量。
如上述说明的那样，通过本发明的信息安全装置及椭圆曲线运算 装置，可以取得在保持对简单功率分析攻击的耐受性的同时，与现有 技术相比可削减使用的表量的效果。
图1是表示本发明所涉及的1实施方式的点发行系统10的构成
的系统构成图。
图2是表示椭圆曲线运算部208的构成的方框图。
图3是表示分割信息生成部222的操作的流程图。
图4是表示椭圆曲线加法运算部226的加法运算操作及椭圆曲线
2倍运算部227的2倍运算操作的流程图。下接图5。
图5是表示椭圆曲线加法运算部226的加法运算操作及椭圆曲线
2倍运算部227的2倍运算操作的流程图。上接图4。
图6是表示表生成部225的表(P—0的生成操作的流程图。
图7表示在sw=3时，由表生成部225戶;f生成的表(P一i)的一例。
图8表示在sw=4时，由表生成部225所生成的表《P一i)的一例。
图9表示在sw=5时，由表生成部225所生成的表(PJ)的一例。
图IO表示标量乘法运算部229的运算步骤的流程图。下接图11。
图11表示标量乘法运算部229的运算步骤的流程图。上接图10。
图12是用于说明图11的步骤S161 S168的各运算的意义的
sw=3吋的运算变换表320。
图13是表示椭圆曲线运算部208的操作的流程图。
图14是表示点发行系统10的操作的流程图。
图15是表示数字签名系统的操作的流程图。
图16是表示密钥共有系统的操作的流程图。
图17表示sw=4时的运算变换表330。
图18是表示标量乘法运算部229的构成的方框图。
具体实施例方式
1、实施方式l
下面，对本发明所涉及的1实施方式的点发行系统io进行说明。 1.1点发行系统io的构成
点发行系统IO，如图1中所示，由IC卡100及点发行装置200 构成。
通过点发行装置200的操作者，将IC卡100安装在点发行装置 200上，点发行装置200生成点，对生成的点施行加密算法，生成加 密点，并将生成的加密点发送给IC卡100。
此处，点是在用户购买商品或接受服务时，从销售者及服务提供 者接受的优惠信息，以后用户在购买商品或接受服务时，作为对销售 者及服务提供者的等价支付的一部分或全部而加以利用。
IC卡100接受加密点，对接受的加密点实施对应于上述加密的 解密算法，生成解密点，并将生成的解密点存储在内部。
点发行装置200及IC卡100，是分别以素数p为模的剩余域F 上所定义的椭圆曲线E上的离散对数问题为根据，利用在椭圆曲线E 上的点C乘以作为小于素数p的正整数的系数k而计算点k*C的椭 圆曲线运算，安全而可靠地处理信息的信息安全装置。
此处，对信息进行安全处理，是指例如在二者间进行信息通信时， 该信息不让第三者知道，该通信也称为秘密通信。
1.2公钥加密方式及离散对数问题
在本实施方式中，上述加密算法及解密算、法，基于使用椭圆曲线 上的运算的公钥加密方式。
在使用公钥加密方式的秘密通信中，加密密钥和解密密钥不同， 解密密钥是私有的，但加密密钥是公开的。
作为该公钥加密方式安全性的根据，可使用在椭圆曲线上所定义 的离散对数问题，关于离散对数问题，在NealKoblitz著的"A Course in Number theory and Cryptography" ， Springer-Verlag， 1987中进行了 详细叙述。
下面，对椭圆曲线上的离散对数问题进行说明。
所谓椭圆曲线上的离散对数问题是，
假设E(GF(p))为在有限域GF(p)上定义的椭圆曲线，当椭圆曲线 E的位数用大的素数除得开时，将椭圆曲线E中所包含的元G作为 基点。这时，如果对椭圆曲线E中所包含的给出的元Y，存在满足
Y=x*G
的整数x，则求出x的问题。
此处，p是素数，GF(p)是具有p个元的有限域。在本说明书中， 符号*表示对椭圆曲线中包含的元进行多个加法运算的运算，x*G， 如下式所示，表示对椭圆曲线中包含的元G相加x个。
x*G=G+G+G+......+G
将离散对数问题作为公钥加密安全性的根据，是因为对于有多个 元的有限域GF(p)，上述问题极为难的缘故。 1.3点发行装置200的构成
点发行装置200，如图l中所示，由公钥存储部20K加密处理 部202、通信部203、控制部204、信息存储部205、输入受理部206、 显示部207及椭圆曲线运算部208构成。
椭圆曲线运算部208，如图2中所示，由输入部230、幂乘(^含 倍)系数存放部221、分割信息生成部222、分割信息存放部223、被 运算值存放部224、表生成部225、椭圆曲线加法运算部226、椭圆 曲线2倍运算部227、表存放部228、标量乘法运算部229及输出部 231构成。
点发行装置200，是生成点并将生成的点进行加密写入IC卡100 中的装置，并且，在销售商品时，也是计算销售额、显示所计算的销 售额、打印收据、将生成的上述点存储在内部、保管使用者支付的货 款等进行保管的现金寄存装置。
点发行装置200，具体来说是由微处理器、ROM、 RAM、硬盘 单元、显示器单元、及键盘等构成的计算机系统。在上述RAM或上 述硬盘单元中存储计算机程序。通过上述微处理器根据上述计算机程 序进行操作，点发行装置200实现其部分功能。
(1)信息存储部205及公钥存储部201
信息存储部205,用于存储素数p、以素数p为模的剩余域Fp上 定义的椭圆曲线E(Fp)上的基点B及椭圆曲线E(Fp)的系数。另外具 有对所生成的点Pm进行存储的区域。
上述椭圆曲线E(Fp)，作为一例，是)^x^aXx+b，上述系数是 a及b。
公钥存储部201，用于存储对应于下述的私钥(私有密钥)ks而生 成的公钥Kp。此处公钥Kp是通过IC卡100或密钥管理装置，按以下 所示的公式算出来的。
公钥Kp-私钥1 *基点B
(2) 控制部204
控制部204,生成作为上述优惠信息的点Pm，并将生成的点Pm 写入信息存储部205。然后，对加密处理部202，输出表示对点Pm 加密并发送给IC卡IOO的指示。
(3) 通信部203、输入受理部206及显示部207
通信部203，在加密处理部202或控制部204的控制的基础上， 在与IC卡100之间进行信息的发送接收。
输入受理部206,受理来自点发行装置200的操作者的信息或指 示的输入，并将受理了输入的信息或指示，输出给控制部204。
显示部207，通过控制部204的控制，显示各种信息。
(4) 加密处理部202
加密处理部202,从控制部204接受表示对点Pm加密并发送给 IC卡IOO的指示。
当接受上述指示时，加密处理部202生成随机数r，从信息存储 部205读出基点B，然后，以生成的随机数r为幂乘系数k，输出给 椭圆曲线运算部208的输入部230，以读出的基点B为被幂乘点C， 输出给输入部230。然后，从椭圆曲线运算部208的输出部231，接 受幂乘点k*C=r*B作为运算结果，使第1密文sh幂乘点r*B.
接着，加密处理部202从公钥存储部201读出公钥Kp，然后以 生成的随机数r为幂乘系数k，输出给输入部230，以读出的公钥kp 为被幂乘点C，输出给输入部230。然后从输出部231接受幂乘点
k*C=r*Kp，作为运算结果。
然后，加密处理部202从信息存储部205读出点Pm，对读出的 点Pm和接收的幂乘点r*Kp的x坐标值进行"异或"，生成第2密 文s2-点Pm xor(幂乘点r*Kp的x坐标值)。此处"xor"是表示"异 或"的运算符。
然后，加密处理部202，将生成的第l密文sl及第2密文s2通 过通信部203发送给IC卡100。 (5)椭圆曲线运算部208
椭圆曲线运算部208，如上所述，由输入部230、幂乘系数存放 部221、分割信息生成部222、分割信息存放部223、被运算值存放 部224、表生成部225、椭圆曲线加法运算部226、椭圆曲线2倍运 算部227、表存放部228、标量乘法运算部229及输出部231构成。
(5-l)幂乘系数存放部221及被运算值存放部224
幂乘系数存放部221，具有只存储l个幂乘系数k的区域。幂乘 系数k是标量，幂乘系数k的比特数为len。
而被运算值存放部224,具有只存储1个被幂乘点G的区域。被 幂乘点G是椭圆曲线上的点。
(5-2)输入部230及输出部231
输入部230，从加密处理部202接受幂乘系数k，当幂乘系数存 放部221中已经存储了幂乘系数时，将接受的幂乘系数k盖写在幂乘 系数存放部221上，而当幂乘系数存放部221未存储幂乘系数时，将 接受的幂乘系数k写入幂乘系数存放部221中。
另外，输入部230从加密处理部202接受被幂乘点C，当被运算 值存放部224中已经存储了被幂乘点时，将接受的被幂乘点C盖写在 被运算存放部224上,而当被运算值存放部224中未存储被幂乘点时， 将接受的被幂乘点C写入被运算存放部224中。
输出部231，从标量乘法运算部229接受幂乘点PC，将接受的 幂乘点k*C输出给加密处理部202。
(5-3)分割信息存放部223
分割信息存放部223，具有存放下述的(b+l)个整数w—i(i=l、 2、
3、……、b+l)组成的整数串(w一i)的区域。
(5-4)分割信息生成部222
分割信息生成部222,从幂乘系数存放部221读出幂乘系数k, 如以下所示，根据读出的幂乘系数k生成由作为分割信息的整数 w_i(i=l、 2、 3、……、b+l)构成的整数串(w—i}。
此处，w一i是sw比特的带符号整数值。sw是带符号Window法 的Window宽度，作为一例，sw=3。这时，w—i取"-3" 、 "-2"、 "國1"、 "0"、 "1"、 "2"、 "3"及"4"中的某个值。b是"(len/sw 以上的最小的整数)-l" ， len是下述的变量v的比特数，"X "是表 示整数的乘法的运算符，"xAy"是表示x的y次方的运算。
例如，le『52时，b=18-l=17。下面作为一个例子sw=3，但是sw 既可以是"2"，也可以是"4"以上。
关于分割信息生成部222的操作，利用图3中所示的流程图进行 说明。
分割信息生成部222,将幂乘系数k代入变量v(v—ks)，取v一0，v一1， v一2， ......， v—b，使v=v—0+v—lX2Asw+v—2X2A(2Xsw)+......+v_b X 2A(b X sw)。再使v—(b+1)—O(步聚S131)。此处v—i(i=0、 1 、2、… b)为sw比特。
然后，分割信息生成部222，在计数器变量c中代入0(c—O)(步 骤S132)
接着，分割信息生成部222，判断是否v—c>2A(sw-l)，当v—c> 2A(sw-l)时(步骤S133中是)，计算w—c —v—c-2A3及v—(c+1)— v—(c+l)+l(步骤S134)。当v—c《2A(sw-l)时(步骤S133中否)时，向w—c 代入v—c(w—c—v-c)(步骤SI35)。
接着，分割信息生成部222，计算c—c+l(步骤S136)。
接着，分割信息生成部222，判断是否c〉b+l，当c〉b+l时(步 骤S137中是)，将整数串(w—iM乍为分割信息存放在分割信息存放部 223中(步骤S138)，结束分割信息的生成处理。当c《b+l时(步骤S137 中否)，返回步骤S133，重复处理。
(5-5)椭圆曲线加法运算部226及椭圆曲线2倍运算部227
椭圆曲线加法运算部226，从表生成部225或标量乘法运算部229 接受椭圆曲线上的2点P1-(X1， Yl， Z1)和P2-(X2， Y2, Z2)以及这 些点的加法运算指示，对于接受的P1-(X1， Yl， Z1)及P2-(X2， Y2， Z2)，如下所示，使Pl和P2在椭圆曲线上进行加法运算，计算点 P3=P1+P2=(X3， Y3， Z3)，然后将计算出的点P3输出给表生成部225 或标量乘法运算部229。
而椭圆曲线2倍运算部227，从表生成部225或标量乘法运算部 229接受椭圆曲线上的点P1-(X1， Yl， Z1)及P1的2倍运算的指示， 对于接受的点P1=(X1， Yl， Zl),如下所示，在椭圆曲线上对点P1 进行2倍运算，计算作为点P1的2倍点的、点P4=2*P1=(X4， Y4， Z4)，然后将计算出的点P4输出给表生成部225或标量乘法运算部 229。
(椭圆曲线加法运算部226的加法运算的细节、及椭圆曲线2倍 运算部227的2倍运算的细节)
在本实施方式中，增加了伪运算，以使在椭圆曲线加法运算部 226及椭圆曲线2倍运算部227中所使用的运算及其顺序相同。
下面，为了明确了解伪运算是"伪运算"，通过变量D表示伪 运算结果的代入目的地。在本实施方式中使用的椭圆曲线加法运算及 椭圆曲线2倍运算，是对Jacobian坐标的计算。关于Jacobian坐标， 在非专利文献4中进行了详细叙述。
在对椭圆曲线加法运算部226及椭圆曲线2倍运算部227的详细 运算进行说明之前，对所使用的运算函数按以下定义。
Sqr(X):表示X的2次方
Mul(X，Y):表示X和Y的相乘。即使在X-Y时，在记载为 Mul(X, Y)的情况下，也不是用Sqr(X)进行2次方计算，同样是以X 的相乘进行计算。
Mul2(X):表示X和2的乘法。
Mul3(X):表示X和3的乘法。
Mul4(X):表示X和4的乘法。
Mul8(X):表示X和8的乘法。
Sub(X,Y):表示从X减去Y的减法。
(椭圆曲线加法运算部226的加法运算操作)
下面，利用4及图5中所示的流程图说明椭圆曲线加法运算部 226的加法操作。
椭圆曲线加法运算部226,按照以下所示的步骤进行加法运算。
Z22—Sqr(Z2) D—Mul4(Xl) U1—Mul(Xl,Z22) Z12—Sqr(Zl) D—Mul2(Yl) Z13—Mul(Z22,Zl) Z23—Mul(Z22，Z2) U2—Mul(X2,Z12)
51— Mul(Yl，Z23)
52— Mul(Y2，Z13) D—Mul3(Z12) H—Sub(U2,Ul) H2—Sqr(H) U1H—Mul(Ul，H2) U2H—Mul2(UlH) r—Sub(S2，Sl) r2—Sqr(r) D一Mul8(r) UHX—Sub(UlH，X3) H3—Mul(H2,H) S1H3—Mul(Sl，H3) rH—Sub(r2，H3) X3—Sub(rH，U2H) Z1Z2—Mul(Zl，Z2) Z3—Mul(ZlZ2,H)
(步骤S401) (步骤S402) (步骤S403) (步骤S404) (步骤S405) (步骤S406) (步骤S407) (步骤S408) (步骤S409) (步骤S410) (步骤S411) (步骤S412) (步骤S413) (步骤S414) (步骤S415) (步骤S416) (步骤S417) (步骤S418) (步骤S419) (步骤S420) (步骤S421) (步骤S422) (步骤S423) (步骤S424) (步骤S425)rU—Mul(r,UHX) (步骤S426)
Y3—Sub(rU，SlH3) (步骤S427)
(椭圆曲线2倍运算部227的2倍运算的操作)
下面，利用4及图5中所示的流程图说明椭圆曲线2倍运算部 227的2倍运算的操作。
椭圆曲线2倍运算部22，按照以下所示的步骤进行2倍运算。
Y12—Sqr(Yl) X41—Mul4(Xl) S—Mul(X41，Y12) X12—Sqr(Xl) Y21—Mul2(Yl) Z4—Mul(Y21，Zl) Z12—Mul(Zl，Zl) Z14—Mul(Z12，Z12) D—Mul(Yl,Z12) aZ14—Mul((國a)， Z14) X32—Mul3(X12) M—Sub(X32，aZ14) M2—Sqr(M) D—Mul(S，M2) S2—Mul2(S) X4—Sub(M2，S2) Y14—Sqr(Y12) Y814—Mul8(Y14) ST—Sub(S，X4) MST—Mul(M，ST) D—Mul(D,MST) Y4—Sub(MST，Y814) D—Sub(Y4,S2) D—Mul(Zl，Z12)
(步骤S501) (步骤S502) (步骤S503) (步骤S504) (步骤S505) (步骤S506) (步骤S507) (步骤S508) (步骤S509) (步骤S510) (步骤S511) (步骤S512) (步骤S513) (步骤S514) (步骤S515) (步骤S516) (步骤S517) (步骤S518) (步骤S519) (步骤S520) (步骤S521) (步骤S522) (步骤S523) (步骤S524)
D—Mul(D，M) D—Mul(X4,ST) D—Sub(D，Y4)
(步骤S525) (步骤S526) (步骤S527)
在步骤S510中出现的(-a)，是椭圆曲线方程式为yA2=XA3+aXx+b 时的参数a的负值，预先计算好。
如图4及图5中所示可知，椭圆曲线加法运算部226和椭圆曲线 2倍运算部227以相同的顺序执行运算。
(5-6)表存放部228
表存放部228，具有1个以上存放由表生成部225生成的椭圆曲 线上的点的区域。
(5-7)表生成部225
表生成部225，如下所述，生成由椭圆曲线上的点构成的表(PJ〉， 并将生成的表(PJ)存放在表存放部228中。
此处，表(PJ),包括1个以上的椭圆曲线上的点P—i(i=l, 2， 3、……)。
关于表生成部225的表(P』的生成操作，禾偶图6中所示的流 程图进行说明。
表生成部225，从被运算值存放部224读出被幂乘点C，表生成 部225对P_i—C及Q—ECD(C)进行运算(步骤S141)。
此处，ECD表示椭圆曲线上的2倍运算，并表示用椭圆曲线2 倍运算部227进行计算。例如，ECD(A)表示对椭圆曲线上的点A进 行计算的2倍运算的运算结果，ECD(A)=2*A。表生成部225对椭圆 曲线2倍运算部227输出椭圆曲线上的点C及2倍运算的指示，并从 椭圆曲线2倍运算部227接受2倍运算的运算结果。
然后，表生成部225对计数器变量i，计算i—1(步骤S142)。
然后，表生成部225计算i—i+l(步骤S143)，计算2^-2,判断是 否》2^-2。在i〉2Sw^时(步骤S144)，结束表生成的处理。
当不是i〉2sw-2时(步骤S144)，表生成部225计算P—i — ECA(P—(i漏l)， Q)。艮口计算ECA(P一(i-l)， Q)= P—(i-l)+Q(步骤S145)。
此处，ECA表示椭圆曲线上的加法运算，并表示用椭圆曲线加 法运算部226进行计算。例如，ECA(A， B)表示对椭圆曲线上的点A 及点B计算出的加法运算结果，ECD(A)=A+B。表生成部225对椭圆 曲线加法运算部226输出椭圆曲线上的点A和点B以及加法运算的 指示，从椭圆曲线加法运算部226接受加法运算的运算结果。
然后，表生成部225将P—i存放在表存放部228中(步骤S146)， 返回步骤S143，重复进行处理。
从上述处理可知P—i=(2Xi-l)*C。
在sw=3、 4及5时，通过表生成部225生成的表(Pj)的例子分 别如图7、图8及图9中所示。
当s『3时，如图7中所示，表311(P—i}=(3C)。而当s『4时， 如图8中所示，表312(P—i}=(3C、 5C、 7C)。当sw=5时，如图9中 所示，表313(P—i}=(3C、 5C、 7C、 9C、 IIC、 13C、 15C)。
(5-8)标量乘法运算部229
标量乘法运算部229利用分割信息存放部223中所存放的整数串 (w一i)和表存放部228中所存放的表(PJh按以下所示，对幂乘系数 计算k倍的点"C。
标量乘法运算部229如图18中所示，由取得部241、选择部242、 重复控制部243、 Window运算部251、 252、 253、 254、 255、 256、 257、 258、初始运算部244、寄存器部245及运算输出部246构成。
关于标量乘法运算部229的运算步骤，利用图10 图11中所示 的流程图迸行说明。
在下述说明中，ECA是由椭圆曲线加法运算部226进行的加法 运算。标量乘法运算部229在进行加法运算时，对椭圆曲线加法运算 部226输出椭圆曲线上的2点及加法运算的指示，从椭圆曲线加法运 算部226接受加法运算的运算结果。另外，ECD是椭圆曲线2倍运 算部227进行的2倍运算。标量乘法运算部229在进行2倍运算时， 对椭圆曲线2倍运算部227输出椭圆曲线上的1点及2倍运算的指示， 从椭圆曲线2倍运算部227接受2倍运算的运算结果。
在下述中，作为一个例子设Window的宽度为"3比特"，即sw=3 进行说明。 标量乘法运算部229的初始运算部244，计算c—b+l(步骤S151)。
此处，c是对处理次数进行计数的计数器变量，寄存器部245由 具有的寄存器构成。b如上所述，是"(len/sw以上的最小整数)-l"。 寄存器部245还具有分别构成下述变量D及变量R的2个寄存器。
接着，标量乘法运算部229的初始运算部244，判断是否w_c=0。 当w_c=0时(步骤S152)，运算D—ECD(C)，D—ECD(D)，D—ECD(D)， D—ECA(R， C)， c—c-l(步骤S153)。
接着，取得部241取得P—(w—c)，标量乘法运算部229的初始运 算部244运算R—P(w一c)(步骤S154)，重复控制部243运算c—c-l(步 骤S155)。
接着，标量乘法运算部229的重复控制部243,判断是否c<0， 当c<0时(步骤S156),运算输出部246将R输出给输出部231(步骤 S158),结束运算处理。
当c》0时(步骤S156),取得部241取得P—(w_c),标量乘法运算 部229的选择部242，对应于w一c的值(步骤S157)进行以下的处理。
当w—c=-3时(步骤S157)，选择部242选择Window运算部251, Window运算部251进行R—ECD(R)， R—ECD(R)， R—ECD(R)， R —ECA(R， -P一2)运算(步骤S161)。
当w—c=-2时(步骤S157),选择部242选择Window运算部252， Window运算部252进行R—ECD(R)， R—ECD(R)， R—ECA(R, -P—1)， R—ECD(R)运算(步骤SI62)。
当w—c=-l时(步骤S157),选择部242选择Window运算部253, Window运算部253进行R—ECD(R)， R—ECD(R)， R—ECD(R)， R —ECD(R， - _1)运算(步骤3163)。
当w_c=0时(步骤S157),选择部242选择Window运算部254， Window运算部254进行R—ECD(R)， R—ECD(R)， R—ECD(R), D —ECA(R， PJ)运算(步骤S164)。
当w—c=l时(步骤S157)，选择部242选择Window运算部255， Window运算部255进行R—ECD(R)， R—ECD(R), R—ECD(R), R —ECA(R， P—l)运算(步骤S165)。
当w—c=2时(步骤S157)，选择部242选择Window运算部256， Window运算部256进行R—ECD(R)， R—ECD(R)， R—ECA(R， P—1)， R—ECD(R)运算(步骤SI66)。
当w_c=3时(步骤S157)，选择部242选择Window运算部257， Window运算部257进行R—ECD(R)， R—ECD(R)， R—ECD(R)， R —ECA(R， P—2)运算(步骤S167)。
当w—c=4时(步骤S157),选择部242选择Window运算部258， Window运算部258进行R—ECD(R)， R—ECA(R， P—1), R—ECD(R), R—ECD(R)运算(步骤S168)。
然后，返回步骤S155重复进行处理。
(关于步骤S161 S168的各运算)
此处，关于图11的步骤S161 S168中各运算的意义，利用图 12中所示的运算变换表320进行说明。
在此，为方便起见，将根据w_c值所进行的多个运算称为Window 运算。
例如，在步骤S164中所进行的R—ECD(R)、 R—ECD(R)、 R— ECD(R)及D—ECA(R， P—l)是1个Window运算，而在步骤S165中 所进行的R—ECD(R)、 R—ECD(R)、 R—ECD(R)及R—ECA(R， P—1) 是1个Window运算。
另外，为了方便起见，将Window运算中所包含的ECA及ECD 称为基本运算。
运算变换表320，作为一个例子，当Window的宽度为"3比特" 时，艮Ps^3时，对每个可取得的w—c的值，表示了该w—c的值、与 其对应的现有Window运算、与其对应的标量乘法运算部229进行的 Window运算(与本发明相关联的Window运算)、表示由标量乘法运 算部229进行的Window运算所包含的基本运算的运算顺序的基本运 算顺序、及表示Window运算所包含的基本运算个数的基本运算次数 间的关系。
此处，作为一个例子，由于Window的宽度为"3比f寺"，所以 w c取"0" 、 "1" 、 "2" 、 "3" 、 "4"、"國3" 、 "-2"及中的某一个。
下面，当w—c取各值时，对现有的Window运算、标量乘法运算 部229的Window运算、基本运算顺序及基本运算次数进行说明。
(a) 当w_c=0时
对w—c=0的现有Window运算，是"R—23R" ， "R—23R"表 示使变量R的值，向高位移位Window宽度所示的比特数(此处为3 比特)。
另一方面，对w_c=0的标量乘法运算部229的Window运算，是 "R—23R"及"D—R+C"。此处对于"R—23R"，如上所述。另夕卜， "D—R+C"是伪的加法运算，目的是为了使w—c=0时的Window运 算所包含的基本运算的种类及其数量，与其他情况(即w_C0时)的 Window运算所包含的基本运算的种类及其数量一致。
此处，"R—23R"，在标量乘法运算部229中，通过R—2XR、 R—2XR、 R—2XR进行运算。
这一运算通过23R=2 X (2 X (2 X R))进行。
从而，在由对w_c=0的标量乘法运算部229进行的Window运算 中，按照2倍运算、2倍运算、2倍运算、伪加法运算的顺序，进行 多个基本运算。(参照步骤S164)
这样，在由对w_c=0的标量乘法运算部229进行的Window运算 所包含的基本运算个数是"4"。
(b) 当w—c=l时
对w_c=l的现有Window运算，是"R—23R+C" 。 "R—23R+C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加C。
对w_c=l的标量乘法运算部229的Window运算，是"R— 23R+C"。
这样，对w—c=l的现有Window运算，与标量乘法运算部229 的Window运算是相同的。
此处，"R—23R+C",在标量乘法运算部229中，通过R—2X R、 R—2XR、 R—2XR、 R—R+C进行运算。(参照步骤S165)
从而，在由对w_c=l的标量乘法运算部229进行的Window运算 中，按照2倍运算、2倍运算、2倍运算、加法运算的顺序，进行多 个基本运算。
这样，在由对w—c=l的标量乘法运算部229进行的Window运算 所包含的基本运算个数为"4"。
(c) 当w_c=2时
对w_c=2的现有Window运算，是"R—23R+2C" 。 "R—23R+2C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加2C。
另一方面，对w_c=2的标量乘法运算部229的Window运算，是 "R—2(22R+C)"。
根据2(22R+C)=23R+2C可知，对w—c=2的现有Window运算的 结果，与标量乘法运算部229的Window运算结果是相同的。
此处，"R—2(22R+C)",在标量乘法运算部229中，通过R—2 XR、 R—2XR、 R—R+C、 R—2XR进行运算。(参照步骤S166)
这一运算通过2(22R+C)=2 X (2 X (2 X R)+C)进行。
从而，在由对w_c=2的标量乘法运算部229进行的Window运算 中，按照2倍运算、2倍运算、加法运算、2倍运算的顺序，进行多 个基本运算。
此处，上述加法运算是点C乘以wj/2t所得到的点的加法运算。 这样，对w—c=2的标量乘法运算部229进行的Window运算所包 含的基本运算个数为"4"。
(d) 当w_c=3时
对w—c=3的现有Window运算，是"R—23R+3C"。 "R—23R+3C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加3C。
对w—c=3的标量乘法运算部229的Window运算，是"R— 23R+3C"。
这样，对w—c=3的现有Window运算，与标量乘法运算部229 的Window运算是相同的。
此处，"R—23R+3C"，在标量乘法运算部229中，通过R—2 XR、 R—2XR、 R—2XR、 R—R+3C进行运算。(参照步骤S167) 这一运算通过23R+3C=2 X (2 X (2 X R))+3C进行。 从而，在由对w_c=3的标量乘法运算部229进行的Window运算 中，按照2倍运算、2倍运算、2倍运算、加法运算的顺序，进行多 个基本运算。
这样，对w—c=3的标量乘法运算部229进行的Window运算所包 含的基本运算个数为"4"。
(e) 当w_c=4时
对w—c=4的现有Window运算，是"R—23R+4C" 。 "R—23R+4C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加4C。
另一方面，对w—c=4的标量乘法运算部229的Window运算，是 "R—22(2R+C)"。
根据22(2R+C)=23R+4C可知，对w_c=4的现有Window运算的 结果，与标量乘法运算部229的Window运算结果是相同的。
此处，"R—22(2R+C)，，，在标量乘法运算部229中，通过R—2 XR、 R—R+C、 R—2XR、 R—2XR进行运算。(参照步骤S168)
这一运算通过22(2R+C)=2 X 2 X ((2 X R)+C)进行。
从而，在由对w_c=4的标量乘法运算部229进行的Window运算 中，按照2倍运算、加法运算、2倍运算、2倍运算的顺序，进行多 个基本运算。
此处，上述加法运算是点C乘以w一c/2t所得到的点的加法运算。 这样，对w_c=4的标量乘法运算部229进行的Window运算所包 含的基本运算个数为"4"。
(f) 当w_c=-3时
对w—c=-3的现有Window运算，是"R—23R-3C"。 "R—23R-3C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加-3C(即从变量R减去3C)。
对w c=-3的标量乘法运算部229的Window运算，是"R—23R+3C"。
这样，对w—c=_3的现有Window运算，与标量乘法运算部229 的Window运算是相同的。
此处，"R—23R-3C"，在标量乘法运算部229中，通过R—2 XR、 R—2XR、 R—2XR、 R—R+(-3C)进行运算。(参照步骤S161)
这一运算通过23R-3C=2 X (2 X (2 X R))+(-3C)进行。
从而，对w—c=-3的标量乘法运算部229进行的Window运算中， 按照2倍运算、2倍运算、2倍运算、加法运算(此处是减法运算)的顺 序，进行多个基本运算。
这样，对w_c=-3的标量乘法运算部229进行的Window运算所 包含的基本运算个数为"4"。
(g) 当w—c=-2时
对w—c=-2的现有Window运算，是"R—23R-2C" 。 "R—23R-2C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加-2C(即从变量R减去2C)。
另一方面，对w_c=-2的标量乘法运算部229的Window运算， 是"R—2(22R-C)，，。
根据2(22R-C)=23R-2C可知，对w—c=-2的现有Window运算的 结果，与标量乘法运算部229的Window运算结果是相同的。
此处，"R—2(22R-C)"，在标量乘法运算部229中，通过R—2 XR、 R—2XR、 R—R+(-C)、 R—2XR进行运算。(参照步骤S162)
这一运算通过2(22R-C)=2 X (2 X (2 X R)+(-C》进行。
从而，对w—c=-2的标量乘法运算部229进行的Window运算中， 按照2倍运算、2倍运算、加法运算(此处是减法运算)、2倍运算的顺 序，进行多个基本运算。
此处，上述减法运算是点C乘以I w_c/2t I所得到的点的减法运算。
这样，对w—c=-2的标量乘法运算部229进行的Window运算所 包含的基本运算个数为"4"。
(h) 当w_c=-l时
对w—c=-l的现有Window运算，是"R—23R-C"。 "R—23R-C" 表示使变量R的值，向高位移位Window宽度所示的比特数(此处为 3比特)，此后，变量R加-C(即从变量R减去C)。
对w—c=-l的标量乘法运算部229的Window运算，是"R— 23R-C"。
这样，对w—c=-l的现有Window运算，与标量乘法运算部229 的Window运算是相同的。
此处，"R—23R-C"，在标量乘法运算部229中，通过R—2X R、 R—2XR、 R—2XR、 R—R+(-C)进行运算。(参照步骤S163)
这一运算通过23R-3C=2 X (2 X (2 X R))+(-C)进行。
从而，对w_c=-l的标量乘法运算部229进行的Window运算中， 按照2倍运算、2倍运算、2倍运算、加法运算(此处是减法运算)的顺 序，进行多个基本运算。
这样，对w—c--l的标量乘法运算部229进行的Window运算所 包含的基本运算个数为"4"。
1.4椭圆曲线运算部208的操作
关于椭圆曲线运算部208的操作，利用图13中所示的流程图进 行说明。
输入部230,从加密处理部202接受幂乘系数k,并将接受的幂 乘系数k写入幂乘系数存放部221(步骤S121),从加密处理部202接 受被幂乘点C，并将接受的被幂乘点C写入被运算值存放部224中(步 骤S122)。
接着，分割信息生成部222，根据幂乘系数k生成作为分割信息 的整数串(w一i),并将生成的整数串(w一i)存放在分割信息存放部223 中(步骤S123)。
然后，表生成部225利用被幂乘点C，生成表(P—i}，并将表(P—i} 存放在表存放部228中(步骤S124)。
然后，标量乘法运算部229使用分割信息存放部223中所存放的 整数串(w—i)和表存放部228中的存放的表(P一i)，计算幂乘点WC(步 骤S125)。
然后，输出部231从标量乘法运算部229接受幂乘点WC，并将 所取得的幂乘点k*C输出给加密处理部202(步骤S126)。 1.5 IC卡100的构成
IC卡100，如图1中所示，由私钥存储部101、解密处理部102、 通信部103、控制部104、信息存储部105及椭圆曲线运算部108构 成。
IC卡IOO，具体来说是由微处理器、ROM、 RAM等构成的计算 机系统。在上述RAM中存储计算机程序。通过上述微处理器按照上 述计算机程序进行操作，IC卡100实现其部分功能。
(1) 信息存储部105及私钥存储部101
信息存储部105，存储素数P、椭圆曲线E(Fp)的系数及基点B。 还具有用于存储所生成的解密点Pm'的区域。 私钥存储部101，用于存储私钥ks。
(2) 通信部103
通信部103，从点发行装置200接收第1密文sl及第2密文s2。 若接收第1密文sl及第2密文s2，则对于控制部104,将表示已接 收了的意思通知给控制部104。并将接收的第1密文sl及第2密文 s2输出给解密处理部102。
(3) 控制部104
控制部104，接受表示已从通信部103接收了第1密文sl及第2 密文s2的意思的通知。当接受上述通知时，对解密处理部102输出 对第1密文sl及第2密文s2进行解密生成解密点的指示。
(4) 解密处理部102
解密处理部102,从控制部104接受表示对第1密文sl及第2 密文s2进行解密生成解密点的指示，并从通信部103接受第1密文 sl及第2密文s2。
当接受上述指示时，解密处理部102从私钥存储部101读出私钥 ks，然后以接受的第1密文sl为被幂乘点k，输出给椭圆曲线运算部 108，以读出的私钥ks为幂乘系数C，输出给椭圆曲线运算部108。 然后，从椭圆曲线运算部108接受运算结果k^sl，计算解密点Pm^
第2密文s2 xor(运算结果ks*sl的x坐标值)。 在此，按照
Pm'=s2 xor(ks*sl的x坐标值) =(Pm xor(r*Kp的x坐标值)) xor(ks r*B的x坐标值) =Pm xor(r ks*B的x坐标值)xor(r ks*B的x坐标值) =Pm
可知解密点Pm'与点Pm —致。
然后，解密处理部102将生成的解密点Pm'写入信息存储部105。 (5)椭圆曲线运算部108
椭圆曲线运算部108，由于具有与点发行装置200所具有的椭圆 曲线运算部208相同的构成，故其详细说明予以省略。
椭圆曲线运算部108，从解密处理部102接受被幂乘点k及幂乘 系数C，计算出幂乘点PC，并将计算出的幂乘点"C输出给解密处 理部102。
1.6点发行系统10的操作
对于点发行系统10的操作,利用图14中所示的流程图进行说明。
(l)私钥ks及公钥Kp的生成操作
以下所示的操作，在点发行装置200发行点之前进行。
IC卡100的解密处理部102,生成私钥ks，将生成的私钥ks写 入私钥存储部IOI(步骤SlOl)。然后，解密处理部102从信息存储部 105读出基点B，并对生成的上述私钥ks和读出的基点B实施椭圆 幂乘运算，生成公钥Kp二k^B。这时，椭圆幂乘运算由椭圆曲线运算 部108进行(步骤S102)。然后，解密处理部102将生成的公钥Kp通 过通信部103发给点发行装置200(步骤S103)。
点发行装置200的加密处理部202，从IC卡100通过通信部203 接收公钥Kp，并将接收的公钥Kp写入公钥存储部201(步骤S104)。
此处，IC卡100生成私钥ks,以生成的私钥ks为基础生成公钥 Kp，将生成的公钥Kp发送给点发行装置200，但是也可以按下所示 进行。
艮P，点发行系统10,还包括密钥管理装置(公钥生成装置)。IC 卡100生成私钥ks，并将生成的私钥ks存储在内部。
密钥管理装置，包括从IC卡lOO安全取得私钥ks，并对取得 的私钥ks进行存储的私钥存储部；对基点B进行存储的基点存储部; 从私钥存储部读出私钥ks，并从基点存储部读出基点B，利用私钥 ks和基点B，生成公钥Kp-k^B的椭圆曲线运算部；以及将生成的 公钥Kp发送给点发行装置200的发送部。此处，密钥管理装置具有 的椭圆曲线运算部，与IC卡100具有的椭圆曲线运算部相同。
(2)点的发行操作
点发行装置200的控制部204生成点Pm,并将生成的点Pm写 入信息存储部205，然后，对加密处理部202输出表示对点Pm加密 并发送给IC卡100的指示(步骤Slll)。
加密处理部202,当从控制部204接受表示对点Pm加密并发送 给IC卡100的指示时，生成随机数r(步骤S112)，从信息存储部205 读出基点B，以生成的随机数r为幂乘系数，输出给椭圆曲线运算部 208，并以读出的基点B为被幂乘点，输出给椭圆曲线运算部208， 从椭圆曲线运算部208，作为运算结果接受幂乘点r*B，使第1密文 sl-幂乘点产B(步骤S113)
然后，加密处理部202从公钥存储部201读出公钥Kp，以生成 的随机数r为幂乘系数，输出给椭圆曲线运算部208，以读出的公钥 Kp为被幂乘点，输出给椭圆曲线运算部208，从椭圆曲线运算部208， 接受作为运算结果的幂乘点r*Kp，加密处理部202从信息存储部205 读出点Pm，对读出的点Pm和接受的幂乘点^Kp进行加法运算，生 成第2密文s2-点Pm xor(幂乘点r*Kp的x坐标值)(步骤Sl 14)。
然后，加密处理部202，将生成的第l密文sl及第2密文s2通 过通信部203发送给IC卡IOO(步骤Sl 15)。
解密处理部102,从点发行装置200通过通信部103接受第1密 文sl及第2密文s2(步骤S115)。
然后，解密处理部102从私钥存储部101读出私钥ks，以接受的 第l密文sl作为被幂乘点，输出给椭圆曲线运算部108,以读出的私
钥ks为幂乘系数，输出给椭圆曲线运算部108。椭圆曲线运算部108 对ks*sl进行运算，解密处理部102从椭圆曲线运算部108接受运算 结果ks*sl，计算解密点Pm，-第2密文s2 xor(运算结果ks*sl的x坐 标值)(步骤S116)。
然后，解密处理部102，将计算所得到的解密点Pm'写入信息存 储部105(步骤S117)。
2、实施方式2
下面对本发明所涉及的另一实施方式的数字签名系统(图中未示 出)进行说明。
数字签名系统，由用户A装置(也称签名生成装置)、用户B装置 (也称签名验证装置)及管理中心装置他称管理装置)构成(各装置在图 中未示出)，用户A装置、用户B装置及管理中心装置分别通过互联
网进行连接。
用户A装置、用户B装置及管理中心装置，具体地说分别是由 微处理器、ROM、 RAM、硬盘单元、显示器单元、键盘及鼠标器等 构成的计算机系统。在上述RAM或上述硬盘中存储计算机程序。通 过上述微处理器根据上述计算机程序进行操作，各装置实现其部分功 能。
用户A装置、用户B装置及管理中心装置，分别是在以素数P 为模的剩余域F上所定义的椭圆曲线E上的离散对数问题作为根据， 利用椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k、算 出点k*C的椭圆曲线运算，对信息进行可靠处理的信息安全装置。
此处，所说的对信息进行可靠处理，是指例如使信息在二者间进 行通信时，发送方发送的信息无改变地到达接收方。
用户A装置，将消息与数字签名数据一起发送给用户B装置， 用户B装置，将消息与数字签名数据一起接收，通过接收的数字签名
数据进行签名验证。
此处，假定在以素数p为模的剩余域Fp上定义的椭圆曲线E(Fp)， 以E的位数为q。 B是椭圆曲线E上的基点。
用户A装置，包括生成私钥xA的私钥生成部；将生成的私钥xA安全发送给管理中心装置的私钥发送部；存储应发送的消息m的 消息存储部；从管理中心装置接收素数p、椭圆曲线E的系数、基点 B的参数接收部；存储接收的素数p、椭圆曲线E的系数及基点B的 参数存储部；生成随机数r的随机数生成部；生成第1签名数据 Rl=(rx, ry)=r*B,并根据sXr=m+rxXXA(mod q)计算第2签名数据 s的签名生成部；将所得到的签名数据(Rl, s)和消息m发送给用户B 装置的发送部；以及根据签名生成部的指示，进行椭圆曲线上的点的 椭圆幂乘运算的椭圆曲线运算部。
管理中心装置，包括从用户A装置安全取得私钥xA的取得部; 存储素数p、椭圆曲线E的系数、基点B的参数存储部；利用取得的 私钥xA，计算公钥YA-xA+G的公钥计算部；公开素数p、椭圆曲线 E的系数及基点G的公开部；通过互联网将公钥YA发送给用户B 装置的发送部；以及根据公钥计算部的指示，进行椭圆曲线上的点的 椭圆幂乘运算的椭圆曲线运算部。
用户B装置，包括从管理中心装置接收素数p、椭圆曲线E的 系数及基点G的参数接收部，存储取得的素数P、椭圆曲线E的系数 及基点G的参数存储部;从管理中心装置接收公钥YA的公钥接收部； 存储接收的公钥YA的公钥存储部;从用户A装置接收签名数据(Rl， S)的签名数据接收部；从用户A装置接收消息m的消息接收部；用 户B装置计算S*R1及m*G+rx*YA并判断S*Rl=m*G+rx*YA是否 成立，当成立时，输出表示验证成功的成功信息，当验证失败时，输 出表示验证失败的失败信息的验证部；以及根据验证部的指示，进行 椭圆曲线上的点的椭圆幂乘运算的椭圆曲线运算部。
用户A装置、用户B装置及管理中心装置分别具有的椭圆曲线 运算部，与实施方式l中所示的椭圆曲线运算部208相同。
下面利用图15中所示的流程图对数字签名系统的操作进行说明。
(私钥xA及公钥YA的生成)
用户A装置生成私钥xA(步骤S201)。
管理中心装置，从用户A装置安全取得私钥xA，利用取得的私
钥xA，计算公钥YA-xA承B(步骤S202)。
然后，管理中心装置，公开素数p、椭圆曲线E的系数及基点 B(步骤S204、步骤S207)，通过互联网，将公钥YA发送给用户B装 置(步骤S205)。
用户B装置，取得素数p、椭圆曲线E的系数及基点B(步骤S204)， 接收公钥YA(步骤S205),将接收的公钥YA存储在内部(步骤S206)。
用户A装置，也取得素数p、椭圆曲线E的系数及基点G(步骤 S207)。
(数字签名数据的生成和签名的验证)
用户A装置，生成随机数r(步骤S211),并生成第1签名数据 Rl-(rx，ry)^+B(步骤S212),
根据sXr=m+rxXxA(mod q)计算第2签名数据s(步骤S213),此 处，m是从用户A装置发送给用户B装置的消息。
然后，用户A装置，将所得到的签名数据(R1、 s)和消息m发送 给用户B装置(步骤S214)。
用户B装置，从用户A装置接收签名数据(R1、 s)和消息m(步骤 S214)。
然后，用户B装置，计算s*Rl及n^G+n^YA(步骤S215)，判 断S*Rl=m*G+rx*YA是否成立(步骤S216),当成立时(步骤S216中 是)，验证成功，可以确认用户A装置的身份。当不成立时(步骤S216 中否)，验证失败，不能确认用户A装置的身份。
5、实施方式3
下面，对本发明所涉及的另一实施方式的密钥共有系统(图中未 示出)，进行说明。
密钥共有系统由用户A装置(也称密钥利用装置)、用户B装置(也
称密钥利用装置)及管理中心装置(也称管理装置)构成(各装置在图中 未示出)，用户A装置、用户B装置及管理中心装置分别通过互联网 进行连接。用户A装置、用户B装置及管理中心装置，具体地说分 别是由包括微处理器、ROM、 RAM等构成的计算机系统。微处理器 根据计算机程序进行操作，各装置实现其功能。
用户A装置及用户B装置，是在以素数p为模的剩余域F上所 定义的椭圆曲线E上的离散对数问题作为根据，利用椭圆曲线E上 的点C乘以作为小于素数p的正整数的系数k、算出点k*C的椭圆曲 线运算，对信息进行安全处理的信息安全装置。
此处，所说的对信息安全进行处理，如上所述是指例如使信息在 二者间进行通信时，该信息不让第三方知道。
用户A装置和用户B装置，按如下所示，取得同一共有密钥， 而不让第三者知道。
管理中心装置，包括选择椭圆曲线E(Fp)系数及基点B的选择 部；对选择的椭圆曲线E的系数、基点B及素数p进行存储的参数 存储部；及公开素数p、椭圆曲线E(Fp)及基点G的公开部。
此处，假定是在以素数p为模的剩余域Fp上定义的上述椭圆曲 线E， B是椭圆曲线E上的基点。
用户A装置，包括从管理中心装置取得素数p、椭圆曲线E的 系数及基点B的参数取得部;利用随机数设定私钥xA的私钥设定部； 计算公钥YA=xA*B的公钥计算部；将计算出的公钥YA发送给用户 B装置的公钥发送部；从用户B装置接收公钥YB的公钥接收部；计 算共有密钥xA*YB=(xAXxB)*B的共有密钥计算部；以及根据公钥 计算部及共有密钥计算部的指示，进行椭圆曲线上的点的椭圆幂乘运 算的椭圆曲线运算部。
用户B装置也具有与用户A装置同样的构成。
用户B装置，包括从管理中心装置取得素数p、椭圆曲线E的 系数及基点B的参数取得部;利用随机数设定私钥xB的私钥设定部； 计算公钥YB=xB*B的公钥计算部；将计算出的公钥YB发送给用户 A装置的公钥发送部；从用户A装置接收公钥YA的公钥接收部；计 算共有密钥xB*YA=(xBXxA)*B的共有密钥计算部；以及根据公钥 计算部及共有密钥计算部的指示，进行椭圆曲线上的点的椭圆幂乘运 算的椭圆曲线运算部。
用户A装置及用户装置B分别具有的椭圆曲线运算部，与实施 方式1的点发行装置200具有的椭圆曲线运算部相同。
下面，利用图16中所示的流程图，对密钥共有系统的操作进行 说明。
管理中心装置，对椭圆曲线E的系数及基点进行选择(步骤 S311)，对素数p、椭圆曲线E的系数及基点B进行公开涉骤S312)。
用户A装置，设定私钥xA(步骤S301)，计算公钥￥人=^*8(步 骤S302)，将公钥YA发送给用户B装置(步骤S303)。
另一方面，用户B装置，设定私钥xB(步骤S321),计算公钥 YB^BfB(步骤S322)，将公钥YB发送给用户A装置(步骤S323)。
用户A装置，计算共有密钥xA丰YBKxAXxB^B(步骤S304)。
用户B装置，计算共有密钥xB+YAKxBXxA^B(步骤S324)。
此处，共有密钥xB承YA-(xBXxA^B
=(xAXxB)*B =共有密钥xA*YB
这样，用户A装置和用户B装置可以取得同一共有密钥，而不 让第三者知道。
6、实施方式1的效果
在实施方式1的点发行装置200具有的椭圆曲线运算部208中， 由于椭圆曲线加法运算部226及椭圆曲线2倍运算部227分别以相同 的顺序执行相同运算(参照图4 图5)，所以分析功率波形的攻击者， 不能根据功率波形区别是执行了椭圆曲线加法运算及椭圆曲线2倍 运算中的哪一个。
另外，标量乘法运算部229，由于椭圆曲线加法运算及椭圆曲线 2倍运算的运算次数的合计不因对计数器c的w_c的值而改变，同样 是4次，所以椭圆曲线加法运算及椭圆曲线2倍运算的运算次数的合 计不因幂乘系数的值而改变，是相同的。从而，即使在攻击者知道运 算次数时，有关幂乘系数的信息也不会泄漏给攻击者。因此，实施方 式l，对简单功率分析攻击是安全的。
另外，当Window的宽度s『3时，存放在表存放部228的表中 的点，除了P一^C之外，只有P一2-3W—点。而在现有的简单功率 分析攻击对策方法中，存放在表存放部228的表中的点，除了PJ-C
之外，是？_2、 P—3、 P—4的3点，实施方式1与现有方法相比，表的 尺寸削减到了 1/3。
在实施方式1中，对每个sw比特的分割信息保持运算次数的合 计一定，但是也可以对1个幂乘系数的运算整体保持运算次数合计一 定。这时，为了在1个幂乘系数的运算整体上调整运算次数，应一边 测量运算次数一边进行运算处理。与此相比，在实施方式1中，每个 sw比特保持运算次数的合计一定，即使对1个幂乘系数的运算整体 也不必注意运算次数，具有控制容易的效果。
上述效果，对实施方式2及3也相同。
7、其他变形例
上述说明的各实施方式，只是本发明实施的一例，本发明并不限 于这些实施方式，只要在不脱离其宗旨的范围内，可以以各种形式实 施。例如，以下的情况也包括在本发明内。
(1) 在实施方式1中，表生成部225使用椭圆曲线加法运算部226 和椭圆曲线2倍运算部227，对椭圆曲线加法运算及和椭圆曲线2倍 运算进行计算，但是，表生成部225也可以执行除去了椭圆曲线加法 运算部226及椭圆曲线2倍运算部227中的伪运算之后的通常的椭圆 曲线加法运算及椭圆曲线2倍运算。
(2) 在实施方式中，sw=3，但是sw也可以是2及4以上的值。这 时，在标量乘法运算部229中，与w^值相对应的Window运算滩 当于图10 图11的步骤S157、步骤S161 S168)，按以下进行。
在与w—c值相对应的Window运算中，进行(sw+l)次基本运算。 (i)当w一c为0以外的情况、且存在满足w一c可用2、除开而用 2、t+l)除不开的非负整数t时，在(sw+l)次基本运算中，从最初开始 第(sw-t+l)次的基本运算进行R —ECA(R， sgn(w_c)*P—((abs (w—c/2At)+l)/2))，在(sw+l)次基本运算中，其他sw次基本运算进行R —ECD(R)。
此处，sgn(w—c)是w—c的符号。当w—c〉0时，sgn(w—c)=l，当 w—c < 0时,sgn(w_c)=-1 。
abs(wj;)是w一c的绝对值。
(ii)当w_c=0时，进行sw次R—ECD(R)的基本运算，然后执行D —ECA(R， P_l)。例如，当s『5， w—c;12时，执行R—ECD(R)， R 一ECD(R)， R—ECD(R)， R—ECA(R,-P—2), R—ECD(R)， R—ECD(R)。
当s『2时，由于除PJ夕卜，不存在表中包含的点，所以不必新 计算点去求表的要素。因此，也可以没有表生成部225及表存放部 228,包括也可以没有表生成部225的处理。这时，表的尺寸，由于 没有除P一1之外的点，所以为O，减小表程度的效果是显著的。
(3)图12表示了 sw=3时的运算变换表320。这里，图17表示sw=4 时的运算变换表330。
此处，由于Window的宽度为"4比特"，所以w_c取"0"、
1 ，，"2""g，,"4，'"5，，"6，，《7，， w y
"_6" 、 "-5"、"画4"、"画3" 、 "-2"及"國l" , 16个值中的一个。
下面，当w—c取各值时，对现有的Window运算、标量乘法运算 部229的Window运算、基本运算顺序及基本运算次数进行说明。
(a)当w_c=0时
对w—c=0的现有Window运算，是"R—24R" 。 "R—24R"表 示使变量R的值，向高位移位Window宽度所示的比特数(此处为4 比特)。
另一方面，对w—c=0的标量乘法运算部229的Window运算，是 "R—24R"及"D—R+C"。此处关于"R—24R"，如上所述。另夕卜， "D—R+C"是伪的加法运算，目的是为了使w—c=0时的Window运 算所包含的基本运算的种类及其数量，与其他情况中的(即w_C#0时 的)Window运算基本包含的基本运算的种类及其数量一致。
此处，"R—24R"，在标量乘法运算部229中，通过R—2XR、 R—2XR、 R—2XR、 R—2XR进行运算。
这一运算通过24R=2 X (2 X (2 X (2 X R)))进行。
从而，在对w—c=0的标量乘法运算部229进行的Window运算中， 按照2倍运算、2倍运算、2倍运算、2倍运算、伪加法运算的顺序，
进行多个基本运算。
这样,对w c=0的标量乘法运算部229进行的Window运算所包
含的基本运算个数为"5"。
(b) w_c=l、 3、 5、 7、 -7、 -5、 -3、 -1时
在w—c=l、 3、 5、 7、 -7、 -5、 -3、 -1时，J见有的Window运算， 分别是"R—24R+C"、 "R—24R+3C"、 "R—24R+5C"、 "R—24R+7C"、 "R—24R-7C" 、 "R—24R-5C" 、 "R—24R-3C" 、 "R—24R-1C"。
"R—24R+C"表示使变量R的值，向高位移位Window宽度所示 的比特数(此处为4比特)，此后变量R加C。关于其他运算也相同。
另外，w—c=l、 3、 5、 7、 -7、 -5、 -3、 -1时的标量乘法运算部229 的Window运算，与现有的Window运算相同。
这时的标量乘法运算部229的各Window运算，按2倍运算、2 倍运算、2倍运算、2倍运算、加法运算的顺序，进行多个基本运算。
这时的标量乘法运算部229进行的Window运算所包含的基本运 算个数为"5"。
(c) w—c=2、 4、 6、 8、 -6、 -4、画2时
在w—c=2、 4、 6、 8、 -6、 -4、 -2时，现有的Window运算，分别 是"R—24R+2C"、 "R—24R+4C"、 "R—24R+6C" 、 "R—24R+8C"、 "R—24R-6C" 、 "R—24R-4C" 、 "R—24R-2C"。
"R—24R+2C"表示使变量R的值，向高位移位Window宽度所 示的比特数(此处为4比特)，此后变量R加2C。关于其他运算也相 同。
另外，w—c=2、 4、 6、 8、 -6、 -4、 -2时的标量乘法运算部229的 Window运算，分别是"R—2(23R+Q" 、 "R—22(22R+C)" 、 "R— 2(23R+3C)"、 "R—23(2R+C)" 、 "R—2(23R-3C)" 、 "R—22(22R-C)"、 "R—2(23R-C)"。这些运算结果与现有的Window运算的结果相同。
此处，例如w一c-2时的"R—2(23R+C)"，在标量乘法运算部229 中，通过R—2XR、 R—2XR、 R—2XR、 R—R+C、 R—2XR进行运算。
从而，对w_c=2时的标量乘法运算部229的各Window运算，按 2倍运算、2倍运算、2倍运算、加法运算、2倍运算的顺序，进行多 个基本运算。
这样，对w_c=2的标量乘法运算部229进行的Window运算所包 含的基本运算个数为"5"。
在w—c=4、 6、 8、 -6、 -4、 -2时，也如图17所示。
(4) 在各实施方式中，将幂乘系数全部按每个sw比特的一定比特 串进行分割，生成sw比特的分割信息，但是也不限于此。比特数也 可以不固定。当分割信息的比特数不一定时，采用分割信息的标量乘 法运算部的运算处理也可以不是一定次数。这时每个分割信息的运算 处理次数，也可以取决于分割信息的比特长，但是不取决于除此之外 的分割信息的比特长以外的信息。
当分割信息的比特数为a比特长时，对应于分割信息值的 Window运算部，依次进行(a+l)次运算。此处，上述多个运算中第 (a-t+l)次运算，是椭圆曲线E上的上述加法运算，其他运算是椭圆曲 线E上的2倍运算。
而当分割信息的比特数为b比特长时(此处，a^b)，对应于分割 信息值的Window运算部，依次进行(b+l)次运算。此处，上述多个运 算中第(b-t+l)次运算，是椭圆曲线E上的上述加法运算，其他运算是 椭圆曲线E上的2倍运算。
(5) 在各实施方式中，当w—c-0时，在sw次R—ECD(R)的基本 运算之后，执行了D—ECA(R， P—1)，但是伪运算处理既可以是与其 他点的加法运算，也可以是椭圆曲线2倍运算。
(6) 在各实施方式中，方程式使用了 yA2=xA3+aXx+b形式的 Weierstrass型椭圆曲线，使用了 Jacobian坐标，但是并不限于此。例 如也可以使用其他坐标(Projective坐标)。这时也可以附加伪运算，不 能区别椭圆曲线加法运算和椭圆曲线2倍运算。另外，也可以将椭圆 曲线2倍运算置换成椭圆曲线加法运算，使用可以运算的Hessian椭 圆及Jacobian椭圆。这时在椭圆曲线加法运算和椭圆曲线2倍运算的 内部运算中也可以没有伪运算。
(7) 在各实施方式中，使用椭圆曲线执行幂乘运算，但是也可以执 行超椭圆曲线或其他代数曲线的Jacobian群的幂乘运算。
(8) 本发明也可以将各实施方式的椭圆曲线运算部用于椭圆
ElGamal加密、PSEC-KEM及其他椭圆曲线或其他代数曲线上的加密 方式中。
例如，也可以在将加密方式的加密算法中的私钥作为幂乘系数的 幂乘运算中，使用各实施方式的椭圆曲线运算部，在将加密方式的解 密算法中的私钥作为幂乘系数的幂乘运算中，使用各实施方式的椭圆 曲线运算部。
另外，在椭圆DSA签名方式、椭圆ElGamal签名方式、椭圆NR 签名方式、椭圆MR签名方式、椭圆PV签名方式、椭圆AO签名方 式等椭圆曲线上的签名方式，或代数曲线的签名方式中，也可以使用 各实施方式的椭圆曲线运算部。
如上所述，在以椭圆曲线上的签名方式的签名生成算法中的随机 数为幂乘系数的幂乘运算中，也可以使用椭圆曲线运算部。
关于椭圆ElGamal加密及椭圆DSA签名方式，在非专利文献3 中有详细叙述。
(9)在实施方式1的点发行系统10中，用户购买商品或接受提供 的服务时，作为从销售方及服务提供方接受的优惠信息，然后在用户 购买商品或接受提供的服务时，以对销售方及服务提供方的等价支付 的一部分或全部利用的点，作为秘密通信对象，点发行装置200对生 成的点进行加密，并将加密点发送给IC卡100， IC卡100对加密点 进行解密，生成解密点，并对生成的解密点进行存储。
但是，秘密通信的对象，并不限于上述的点。
也可以适用于如下所述的现金结算系统。
例如，以可以代替现金使用的电子货币为秘密通信对象，IC卡 存储电子货币，用户在购买商品时，IC卡对相当于商品购买金额的 电子货币进行加密并发送，并从内部存储的电子货币中减去发送的部 分。代替点发行装置200具有同样构成的收银装置，接收加密电子货 币，对接收的加密电子货币进行解密，再现电子货币、并存储。
另外，代替上述IC卡，也可以是用于利用美术馆及博物馆等各 种设施的IC卡类型的电子票，如上所述，存储相当于电子货币的信 息。各种设施的入口设置的入场管理装置，请求支付相当于各种设施 使用费用的电子货币，上述电子票对所请求金额的电子货币进行加密 并发送，入场管理装置，接收加密电子货币，对接收的加密电子货币 进行解密，生成电子货币，进行存储。
另外，也可以是利用铁路、公交车等交通工具时所使用的ic卡
类型的IC卡车票，如上所述，存储相当于电子货币的信息。交通机
构车站的入口所设置的入场管理装置，发送识别该站的识别信息，ic
卡车票接收、存储上述识别信息。交通机构车站的出口设置的出口管
理装置，从IC卡车票接收上述识别信息，利用接收的识别信息和设
置该出口管理装置的站，通过收费表，计算乘车金额，请求支付相当
于计算出的乘车收费金额的电子货币，ic卡车票，对请求金额的电
子货币进行加密并发送，出口管理装置接收加密电子货币，对接收的 加密电子货币进行解密，生成、存储电子货币。
在上述的加密及解密中，椭圆曲线上的离散对数问题用作安全性 的根据，进行椭圆幂乘运算。进行该椭圆幂乘运算的各装置，具有与
椭圆曲线运算部208相同的椭圆曲线运算部。
上述各装置，是在以素数p为模的剩余域F上所定义的椭圆曲线 E上的离散对数问题作为根据，利用椭圆曲线E上的点C乘以作为小 于素数p的正整数的系数k、算出点HC的椭圆曲线运算，对信息进 行安全处理的信息安全装置。
(10) 在上述的现金结算系统中，对于所发送的现金金额、发送源、 发送目的地等，有时要求其正当性的证明。这时，可使用实施方式2 中所示的数字签名及签名验证。
在这样的数字签名及签名验证中，椭圆曲线上的离散对数问题用 作安全性的根据，进行椭圆幂乘运算。进行该椭圆幂乘运算的各装置 具有与椭圆曲线运算部208相同的椭圆曲线运算部。
上述的各装置，是以素数p为模的剩余域F上所定义的椭圆曲线 E上的离散对数问题为根据，利用在椭圆曲线E上的点C乘以作为小 于素数p的正整数的系数k、计算点WC的椭圆曲线运算，可靠地处 理信息的信息安全装置。
(11) 秘密通信的对象不限于上述的点及电子货币等。
本发明，可适用于在由内容加密装置和内容再现装置构成的内容 分配系统中，例如也可以将电影、动态图像、声音、音乐、小说、数 据库等数字信息作为秘密通信的对象。这些内容，可从内容提供者对 用户，通过销售、租赁记录了这些内容的记录媒体进行提供。另外， 可通过数字广播及互联网从内容提供者提供给用户。
内容提供者持有的内容加密装置，对作为数字作品的电影进行加
密，记录在DVD上，用户持有的内容再现装置，从DVD读出加密 的数字作品，解密后生成电影,将生成的电影以声音及影像进行再现、 显示及输出。
在上述的加密及解密中，椭圆曲线上的离散对数问题用作安全性 的根据，进行椭圆幂乘运算。进行该椭圆幂乘运算的内容加密装置及 内容再现装置，具有与椭圆曲线运算部208相同的椭圆曲线运算部。
在上述的例子中，也可以将对内容进行加密及解密的内容密钥， 作为实施方式1中所示的秘密通信的对象。这时，内容密钥与实施方 式1中所示的方法同样，进行加密及解密。
这时，内容通过内容密钥，使用下述的共用密钥加密方式，进行 加密及解密。
上述的各装置，是以素数p为模的剩余域F上所定义的椭圆曲线 E上的离散对数问题为根据，利用在椭圆曲线E上的点C乘以作为小 于素数p的正整数的系数k、计算点1^C的椭圆曲线运算，安全地处 理信息的信息安全装置。
(12)在上述的内容分配系统中，对数字作品进行加密时使用的加 密技术，例如也可以使用DES(Data Encryption Standard:数据加密标 准)或AES(Advanced Encryption Standard:高级加密标准)。DES及 AES等加密技术被称为所谓共用密钥加密方式(或私钥加密方式)。
在上述内容分配系统中，在采用这种共用密钥加密方式时，在构 成内容分配系统的加密装置和再现装置之间，如何安全共有同一私钥 是一个课题。
实施方式3中所示的密钥共有系统，提供了解决这一课题的方法。
通过实施方式3中所示的密钥共有系统，在内容加密装置(相当 于实施方式3的用户A装置)和内容再现装置(相当于实施方式3的用 户B装置)之间，共有不让第三者知道的私钥，此后使用共有密钥加 密方式的加密算法，在内容加密装置中，使用共有的私钥，对数字作 品进行加密，生成加密数字作品，然后，在内容再现装置中，使用共 有的私钥，对加密数字作品进行解密。
在上述的密钥共有中，椭圆曲线上的离散对数问题用作安全性的 根据，进行椭圆幂乘运算。进行该椭圆幂乘运算的内容加密装置及内 容再现装置，具有与椭圆曲线运算部208相同的椭圆曲线运算部。
(13)上述的各实施方式及变形例，可适用于以下所示的情况。
(a) 各实施方式及变形例，在秘密的消息传输中使用。关于这一 点， 在上述记载中以秘密通信进行了说明。
(b) 各实施方式及变形例，可在认证中使用。所谓认证是指消息是 否由如自称那样的人物发送、及消息未被篡改的验证。另外，各实施 方式及变形例可在身份的证明中使用。身份证明，是指例如是否具有 对数据库的访问权、或对设施的访问权(入室权)的证明，或者本人是 否是所说的人物的证明。另外，各实施方式及变形例还可在防止否认 中使用。所谓防止否认，是指例如用于对抗实际已同意某个事、但却 声称未同意的人。
(c) 各实施方式及变形例，在密钥交换中使用。所谓密钥交换，是 指例如两个人使用广播电波并同意用于在某个私钥加密方式中使用 的私钥。在上述记载中以密钥共有进行了说明。
(d) 各实施方式及变形例，可在掷硬币(也称作Bit Commitment: 比特承诺)中使用。所谓掷硬币，例如住在不同城市的2个国际象棋 手，用电子邮件决定谁执白。
(e) 各实施方式及变形例，可以在秘密共享中使用。所谓秘密共享， 是指例如，某个秘密信息，可以由共同工作的k个人利用，但k-l个 人却不能利用。
(f) 各实施方式及变形例，可以在零知识证明中使用。所谓零知识 证明，是指例如某个人对已成功解决数论或组合论的问题的事，仅通 过提供解是什么这样一点信息，而使他人相信此事。
(14) 上述各装置，具体地说是由微处理器、ROM、 RAM、硬盘 单元、显示器单元、键盘、及鼠标器等构成的计算机系统。在上述 RAM或上述硬盘中存储计算机程序。此处，计算机程序，为了实现 规定的功能，由多个表示对计算机的命令的指令代码组合构成。通过 上述微处理器按上述计算机程序操作，各装置实现各功能。即，上述 微处理器1个1个读出上述计算机程序中所包含的指令，解读读出的 指令，根据解读结果进行操作。
(15) 构成上述各装置的构成要素的一部分或全部，也可以由1个 系统LSI(Large Scale Integration:大规模集成电路)构成。系统LSI是 将多个构成部集成在1个芯片上制造的超多功能的LSI,具体地说是 包括微处理器、ROM、 RAM等构成的计算机系统。在上述RAM中 存储计算机程序。通过上述微处理器根据上述计算机程序进行操作， 系统LSI实现其功能。
另外，构成上述各装置的构成要素的各部分，即可以分别作成l 个芯片，也可以单片化使其包含1部分或全部。此处，LSI因集成度 不同，也有的称为IC、系统LSI、超LSI、甚LSI。
另外，集成电路化的方法并不限于LSI，也可以用专用电路或通 用处理器实现。也可以在LSI制造后，利用对可以编程的FPGA(Field Programmable Gate Array:现场可编程门阵列)及LSI内部的电路单元 的连接及设定进行再构成的可重构处理器。
(16) 构成上述各装置的构成要素的一部分或全部，也可以由可以 在各装置上装卸的IC卡或单体模块构成。上述IC卡或上述模块，是 由微处理器、ROM、 RAM等构成的计算机系统。上述IC卡或上述 模块，也可以包括上述超多功能LSI。通过微处理器根据计算机程序 进行操作，上述IC卡或上述模块实现其功能。该IC卡或该模块也可 以具有防篡改性。
(n)本发明也可以作为上述所示的方法。这些方法既可以是由计
算机实现的计算机程序，也可以是由上述计算机程序构成的数字信 号。
另外，本发明，也可以将上述计算机程序或上述数字信号记录在
计算机可以读取的记录媒体，例如软盘、硬盘、CD-ROM、 MO、 DVD、 DVD-ROM、 DVD-RAM、 BD(Blu-ray Disc:蓝光光盘)、半导体存储 器等中。另外，也可以是在这些记录媒体上所记录的上述计算机程序 或上述数字信号。
另外，本发明将上述计算机程序或上述数字信号通过电气通信线 路、无线或有线通信线路、以互联网为代表的网络、数据广播等进行 传输。
另外，本发明也可以是具有微处理器和存储器的计算机系统，上 述存储器存储上述计算机程序，上述微处理器根据上述计算机程序进 行操作。
另外，也可以通过将上述程序或上述数字信号存储在上述记录媒 体上进行转移，或经过上述网络等将上述程序或上述数字信号进行转 发，由独立的其他计算机系统实施。
(18)如上所述，本发明，是对预先赋予的秘密信息和作为输入的 椭圆曲线上的点，执行椭圆曲线上的标量乘法运算的椭圆曲线运算装 置，其特征在于；包括对上述秘密信息进行分割，生成分割信息的 分割信息生成部；对于2个上述椭圆曲线上的点，生成在上述椭圆曲 线的群上加法运算之后的结果所得到的点的椭圆曲线加法运算部；对 于1个上述椭圆曲线上的点，生成在上述椭圆曲线的群上2倍之后的 结果所得到的点的椭圆曲线2倍运算部；以及根据第1上述椭圆曲线 上的点和上述分割信息，使用上述椭圆曲线加法运算部和上述椭圆曲 线2倍运算部，生成第2上述椭圆曲线上的点的标量乘法运算部；上
述标量乘法运算部进行控制，以使得使用上述椭圆曲线加法运算部和
上述椭圆曲线2倍运算部的次数合计后的值不依赖于上述秘密信息
的比特长以外的信息而保持一定，上述椭圆曲线加法运算部和上述椭
圆曲线2倍运算部中的每个，具有执行椭圆曲线定义域上的乘法运算 的乘法运算单元、执行上述定义域上的2次方运算的2次方运算单元、 执行上述定义域上的加法运算的加法运算单元，上述椭圆曲线加法运 算部和上述椭圆曲线2倍运算部执行的上述乘法运算、上述2次方运算及上述加法运算的顺序相同。
此处，也可以是，上述标量乘法运算部，根据一个上述分割信息，
进行控制，以使得使用上述椭圆曲线加法运算部和上述椭圆曲线2倍 运算部的次数合计后的值不依赖于上述分割信息的比特长以外的信 息而保持一定。
此处，也可以是，上述椭圆曲线运算装置，还具有表生成部，该 表生成部对1个以上预先赋予的正整数，计算以上述正整数为标量的 上述椭圆曲线上的点的标量乘法点，将其结果的每个存放在表中，在 上述椭圆曲线加法运算部使用的2个上述椭圆曲线上的点之中，至少 一个是上述表中所存放的上述标量乘法点。
此处，也可以是，上述分割信息生成部，将上述秘密信息分割成 具有预先赋予的比特数的多个上述分割信息。
此处，也可以是，上述椭圆曲线2倍运算部，具有执行对计算结 果无影响的伪的上述乘法运算的伪乘法运算单元。
此处，也可以是，上述椭圆曲线2倍运算部，具有将定义域的元 的2次方运算的结果，使用上述元和上述元的乘法运算得到的2次方 运算代替单元。
此处，也可以是，上述正整数是奇数。
此处，也可以是，上述分割信息生成部，生成多个sw比特的上 述分割信息，上述标量乘法运算部，执行(sw+l)次运算处理，当上述 分割信息w是0以外、并且上述分割信息w由2At(t为非负整数)除得 开而由2A(t+l)除不开时，第(sw-t+l)个上述运算处理使用上述椭圆曲 线加法运算部，其他上述运算处理使用上述椭圆曲线2倍运算部。
本发明，是对预先赋予的秘密信息和作为输入的椭圆曲线上的 点，执行椭圆曲线上的标量乘法运算的椭圆曲线运算方法，其特征在 于；包括对上述秘密信息进行分割，生成分割信息的分割信息生成 步骤；对于2个上述椭圆曲线上的点，生成在上述椭圆曲线的群上加 法运算之后的结果所得到的点的椭圆曲线加法运算步骤；对于1个上 述椭圆曲线上的点，生成在上述椭圆曲线的群上2倍之后的结果所得 到的点的椭圆曲线2倍运算步骤；以及根据第1上述椭圆曲线上的点
和上述分割信息，使用上述椭圆曲线加法运算步骤和上述椭圆曲线2 倍运算步骤，生成第2上述椭圆曲线上的点的标量乘法运算步骤；上 述标量乘法运算步骤进行控制，以使得使用上述椭圆曲线加法运算步 骤和上述椭圆曲线2倍运算步骤的次数合计后的值不依赖于上述秘 密信息的比特长以外的信息而保持一定，上述椭圆曲线加法运算步骤 和上述椭圆曲线2倍运算步骤中的每个，具有执行椭圆曲线定义域上 的乘法运算的乘法运算单元、执行上述定义域上的2次方运算的2次 方运算单元、执行上述定义域上的加法运算的加法运算单元，上述椭 圆曲线加法运算步骤和上述椭圆曲线2倍运算步骤执行的上述乘法 运算、上述2次方运算及上述加法运算的顺序相同。
此处，也可以是，上述标量乘法运算步骤，根据一个上述分割信 息，进行控制，以使得使用上述椭圆曲线加法运算部和上述椭圆曲线 2倍运算部的次数合计后的值不依赖于上述秘密信息而保持一定。
此处，也可以是，上述椭圆曲线运算方法，还具有表生成步骤， 该表生成步骤对1个以上预先赋予的正整数，计算以上述正整数为标 量的上述椭圆曲线上的点的标量乘法点，将其结果的每个存放在表 中，在上述椭圆曲线加法运算步骤使用的2个上述椭圆曲线上的点之 中，至少一个是上述表中所存放的上述标量乘法点。
此处，也可以是，上述分割信息生成步骤，将上述秘密信息分割 成具有预先赋予的比特数的多个上述分割信息。
此处，也可以是，上述正整数是奇数。
此处，也可以是，上述分割信息生成步骤，生成多个sw比特的 上述分割信息，上述标量乘法运算步骤，执行(sw+l)次运算处理，当 上述分割信息w是0以外、并且上述分割信息w由2、(t为非负整数) 除得开而由2A(t+l)除不幵时，第(sw-t+l)个上述运算处理使用上述椭 圆曲线加法运算步骤，其他上述运算处理使用上述椭圆曲线2倍运算
另外，本发明，是使椭圆曲线运算装置执行的程序，该椭圆曲线 运算装置对预先赋予的秘密信息和作为输入的椭圆曲线上的点，执行 椭圆曲线上的标量乘法运算，其特征在于；该程序使上述椭圆曲线运算装置执行下列步骤对上述秘密信息进行分割，生成分割信息的分 割信息生成步骤；对于2个上述椭圆曲线上的点，生成在上述椭圆曲 线的群上加法运算之后的结果所得到的点的椭圆曲线加法运算步骤； 对于1个上述椭圆曲线上的点，生成在上述椭圆曲线的群上2倍之后 的结果所得到的点的椭圆曲线2倍运算步骤；以及根据第1上述椭圆 曲线上的点和上述分割信息，使用上述椭圆曲线加法运算步骤和上述 椭圆曲线2倍运算步骤，生成第2上述椭圆曲线上的点的标量乘法运 算步骤；上述标量乘法运算步骤进行控制，以使得使用上述椭圆曲线 加法运算步骤和上述椭圆曲线2倍运算步骤的次数合计后的值不依 赖于上述秘密信息的比特长以外的信息而保持一定，上述椭圆曲线加 法运算步骤和上述椭圆曲线2倍运算步骤中的每个，具有执行椭圆曲 线定义域上的乘法运算的乘法运算单元、执行上述定义域上的2次方 运算的2次方运算单元、执行上述定义域上的加法运算的加法运算单 元，上述椭圆曲线加法运算步骤和上述椭圆曲线2倍运算步骤执行的 上述乘法运算、上述2次方运算及上述加法运算的顺序相同。
此处，也可以是，上述标量乘法运算步骤，根据一个上述分割信 息，进行控制，以使得使用上述椭圆曲线加法运算部和上述椭圆曲线 2倍运算部的次数合计后的值不依赖于上述秘密信息而保持一定。
此处，也可以是，上述椭圆曲线运算方法，还具有表生成步骤， 该表生成步骤对1个以上预先赋予的正整数，计算以上述正整数为标 量的上述椭圆曲线上的点的标量乘法点，将其结果的每个存放在表 中，在上述椭圆曲线加法运算步骤使用的2个上述椭圆曲线上的点之 中，至少一个是上述表中所存放的上述标量乘法点。
此处，也可以是，上述分割信息生成步骤，将上述秘密信息分割 成具有预先赋予的比特数的多个上述分割信息。
此处，也可以是，上述正整数是奇数。
此处，也可以是，上述分割信息生成步骤，生成多个sw比特的 上述分割信息，上述标量乘法运算步骤，执行(sw+l)次运算处理，当 上述分割信息w是0以外、并且上述分割信息w由2At(t为非负整数) 除得开而由2A(t+l)除不开时，第(sw-t+l)个上述运算处理使用上述椭
圆曲线加法运算步骤，其他上述运算处理使用上述椭圆曲线2倍运算
7 另外，本发明，是对预先赋予的秘密信息和作为输入的椭圆曲线 上的点执行椭圆曲线上的标量乘法运算的椭圆曲线运算装置的集成 电路，其特征在于；包括对上述秘密信息进行分割，生成分割信息 的分割信息生成部；对于2个上述椭圆曲线上的点，生成在上述椭圆 曲线的群上加法运算之后的结果所得到的点的椭圆曲线加法运算部； 对于l个上述椭圆曲线上的点，生成在上述椭圆曲线的群上2倍之后 的结果所得到的点的椭圆曲线2倍运算部；以及根据第1上述椭圆曲 线上的点和上述分割信息，使用上述椭圆曲线加法运算部和上述椭圆 曲线2倍运算部，生成第2上述椭圆曲线上的点的标量乘法运算部； 上述标量乘法运算部进行控制，以使得使用上述椭圆曲线加法运算部 和上述椭圆曲线2倍运算部的次数合计后的值不依赖于上述秘密信 息的比特长以外的信息而保持一定，上述椭圆曲线加法运算部和上述 椭圆曲线2倍运算部中的每个，具有执行椭圆曲线定义域上的乘法运 算的乘法运算单元、执行上述定义域上的2次方运算的2次方运算单 元、执行上述定义域上的加法运算的加法运算单元，上述椭圆曲线加 法运算部和上述椭圆曲线2倍运算部执行的上述乘法运算、上述2次 方运算及上述加法运算的顺序相同。
此处，也可以是，上述标量乘法运算部，根据一个上述分割信息， 进行控制，以使得使用上述椭圆曲线加法运算部和上述椭圆曲线2倍 运算部的次数合计后的值不依赖于上述秘密信息而保持一定。
G9)也可以将上述实施方式及上述变形例分别进行组合。
(产业上的可利用性)
如上所述，根据本发明，可以防止由简单功率分析攻击而造成的 安全性下降。
构成本发明的各装置、各方法及各计算机程序，在需要对信息进 行安全可靠处理的所有产业中，可以经营性地、持续地及反复地使用。 另外，构成本发明的各装置，在电器设备制造产业中，可以经营性地、 持续地及反复地制造、销售。
权利要求
1、一种信息安全装置，以将素数p作为模的剩余域F上所定义的椭圆曲线E上的离散对数问题为根据，利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k来计算出点k*C的椭圆曲线运算，安全而可靠地处理信息，其特征在于，包括点存储单元，存储椭圆曲线E上的点C；位存储单元，存储系数k的所有位的值；取得单元，从位存储单元取得1个位的值w；乘法运算单元，其数量与取得的上述位所能表示的值的种类的数量相同；选择单元，选择与取得的上述位的值w相对应的乘法运算单元；以及重复控制单元，对于系数k的所有的位，对上述取得单元、上述选择单元及上述乘法运算单元进行控制，以便重复地进行1个位的值w的取得、与取得的位的值w相对应的乘法运算单元的选择、以及所选择的乘法运算单元进行的乘法运算，各乘法运算单元，在椭圆曲线E上，将上述点C乘以取得的上述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行加法运算，当存在满足取得的上述位的值w用2t除得开、而用2t+1除不开的条件的非负整数t时，与该位的值w相对应的上述乘法运算单元，在椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法运算或点Q乘以|w/2t|而得的点的减法运算的运算。
2、 如权利要求1所述的信息安全装置，其特征在于 取得的上述位为sw比特长，当存在上述非负整数t时，与上述位的值w相对应的上述乘法运 算单元，依次进行(sw+l)次运算，在上述多个运算中的第(sw-t+l)个 运算，是椭圆曲线E上的上述加法运算或上述减法运算，其他运算是 椭圆曲线E上的2倍运算。
3、 如权利要求2所述的信息安全装置，其特征在于 上述信息安全装置还包括表生成单元，该表生成单元以点Q为 初始的加法运算点，通过重复进行对加法运算点加上2*Q而得到新 的加法运算点的运算，从而生成除点Q之外的2SW"个加法运算点；当存在非负整数t时,与该位的值w相对应的上述乘法运算单元， 使用由上述表生成单元所生成的上述加法运算点，作为点Q乘以w/21 或lw/2l而得到的点。
4、 如权利要求2所述的信息安全装置，其特征在于 取得的上述位是3比特长，当上述位的值w为2时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、加法运算及2倍运算，上述加法运算 是加上上述点C的运算，当上述位的值w为4时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、加法运算、2倍运算及2倍运算，上述加法运算 是加上上述点C的运算，当上述位的值w为-2时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、减法运算及2倍运算，上述减法运算 是减去上述点C的运算。
5、 如权利要求2所述的信息安全装置，其特征在于 取得的上述位是4比特长，当上述位的值w为2时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、2倍运算、加法运算及2倍运算，上 述加法运算是加上上述点C的运算，当上述位的值w为4时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、加法运算、2倍运算及2倍运算，上 述加法运算是加上上述点C的运算，当上述位的值w为6时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、2倍运算、加法运算及2倍运算，上 述加法运算是加上点3*C的运算，当上述位的值w为8时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、加法运算、2倍运算、2倍运算及2倍运算，上 述加法运算是加上上述点c的运算，当上述位的值w为-6时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、2倍运算、减法运算及2倍运算，上 述减法运算是减去点3*C的运算，当上述位的值w为-4时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、减法运算、2倍运算及2倍运算，上 述减法运算是减去点C的运算，当上述位的值w为-2时，对应的乘法运算单元依次进行椭圆曲 线E上的2倍运算、2倍运算、2倍运算、减法运算及2倍运算，上 述减法运算是减去点C的运算。
6、 如权利要求2所述的信息安全装置，其特征在于 上述加法运算或上述减法运算及上述2倍运算，分别包括伪运算，使得它们以相同顺序执行相同种类的运算。
7、 如权利要求1所述的信息安全装置，其特征在于 当取得的上述位是a比特长时，在存在上述非负整数t时，与上述位的值w相对应的上述乘法运算单元，依次进行(a+l)次运算，在 上述多个运算中的第(a-t+l)个运算是椭圆曲线E上的上述加法运算或 上述减法运算，其他运算是椭圆曲线E上的2倍运算，当取得的上述位是b比特长时，在存在上述非负整数t时，与上 述位的值w相对应的上述乘法运算单元，依次进行(b+l)次运算，在 上述多个运算中的第(b-t+l)个运算是椭圆曲线E上的上述加法运算 或上述减法运算，其他运算是椭圆曲线E上的2倍运算。
8、 如权利要求1所述的信息安全装置，其特征在于 上述信息安全装置是加密装置，采用计算点k*C的椭圆曲线运算，对信息进行加密。
9、 如权利要求1所述的信息安全装置，其特征在于 上述信息安全装置是解密装置，采用计算点k*C的椭圆曲线运算，对加密的信息进行解密。
10、 如权利要求1所述的信息安全装置，其特征在于上述信息安全装置是数字签名生成装置，采用计算点wc的椭圆曲线运算，对信息进行数字签名。
11、 如权利要求1所述的信息安全装置，其特征在于 上述信息安全装置是数字签名验证装置，釆用计算点k*C的椭圆曲线运算，进行数字签名的验证。
12、 如权利要求1所述的信息安全装置，其特征在于-上述信息安全装置是密钥共有装置，采用计算点k*C的椭圆曲线运算，生成与其他密钥共有装置之间 共有的密钥。
13、 一种椭圆曲线运算装置，以将素数p作为模的剩余域F上所 定义的椭圆曲线E上的离散对数问题为根据，利用在椭圆曲线E上 的点C乘以作为小于素数p的正整数的系数k来计算点k*C，其特征 在于，该椭圆曲线运算装置包括点存储单元，存储椭圆曲线E上的点C; 位存储单元，存储系数k的所有位的值； 取得单元，从位存储单元取得1个位的值W;乘法运算单元，其数量与取得的上述位所能表示的值的种类的数 量相同；选择单元，选择与取得的上述位的值W相对应的乘法运算单元；以及重复控制单元，对于系数k的所有的位，对上述取得单元、上述 选择单元及上述乘法运算单元进行控制，以便重复地进行1个位的值W的取得、与取得的位的值W相对应的乘法运算单元的选择、以及 所选择的乘法运算单元进行的乘法运算，各乘法运算单元，在椭圆曲线E上，将上述点C乘以取得的上 述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行 加法运算，当存在满足取得的上述位的值w用2l除得开、而用2t+1除不开的 条件的非负整数t时，与该位的值w相对应的上述乘法运算单元，在 椭圆曲线E上，进行包括点Q乘以w/》而得到的点的加法运算或点 Q乘以lw/2tl而得的点的减法运算的运算。
14、 一种集成电路，用于椭圆曲线运算，该椭圆曲线运算以将素 数p作为模的剩余域F上所定义的椭圆曲线E上的离散对数问题为根 据，利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的系 数k来计算点"C，其特征在于，该集成电路包括点存储单元，存储椭圆曲线E上的点C;位存储单元，存储系数k的所有位的值； 取得单元，从位存储单元取得1个位的值W;乘法运算单元，其数量与取得的上述位所能表示的值的种类的数 量相同；选择单元，选择与取得的上述位的值w相对应的乘法运算单元；以及重复控制单元，对于系数k的所有的位，对上述取得单元、上述 选择单元及上述乘法运算单元进行控制，以便重复地进行1个位的值 w的取得、与取得的位的值w相对应的乘法运算单元的选择、以及 所选择的乘法运算单元进行的乘法运算，各乘法运算单元，在椭圆曲线E上，将上述点C乘以取得的上 述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行 加法运算，当存在满足取得的上述位的值w用2t除得开、而用2t+1除不开的 条件的非负整数t时，与该位的值w相对应的上述乘法运算单元，在 椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法运算或点 Q乘以lw/2t,得的点的减法运算的运算。
15、 一种方法，用于信息安全装置，该信息安全装置以将素数p 作为模的剩余域F上所定义的椭圆曲线E上的离散对数问题为根据， 利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k 来计算点k*C的椭圆曲线运算，安全而可靠地处理信息,其特征在于上述信息安全装置，包括点存储单元，存储椭圆曲线E上的点C;以及位存储单元，存储系数k的所有位的值，上述方法包括 取得步骤，从位存储单元取得l个位的值w; 乘法运算步骤，其数量与取得的上述位所能表示的值的种类的数 量相同；选择步骤，选择与取得的上述位的值w相对应的乘法运算步骤;以及重复控制步骤，对于系数k的所有的位，对上述取得步骤、上述 选择步骤及上述乘法运算步骤进行控制，以便重复地进行1个位的值 w的取得、与取得的位的值w相对应的乘法运算步骤的选择、以及 所选择的乘法运算步骤中进行的乘法运算，各乘法运算步骤，在椭圆曲线E上，将上述点C乘以取得的上 述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行 加法运算，当存在满足取得的上述位的值w用2t除得开、而用2t+1除不开的 条件的非负整数t时，在与该位的值w相对应的上述乘法运算步骤中， 在椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法运算或 点Q乘以lw/2tl而得的点的减法运算的运算。
16、 一种计算机程序，用于信息安全装置，该信息安全装置以将 素数p作为模的剩余域F上所定义的椭圆曲线E上的离散对数问题为 根据，利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的 系数k来计算点WC的椭圆曲线运算，安全而可靠地处理信息，其特 征在于上述信息安全装置，包括点存储单元，存储椭圆曲线E上的点C;以及位存储单元，存储系数k的所有位的值，上述计算机程序包括取得步骤，从位存储单元取得1个位的值W;乘法运算步骤，其数量与取得的上述位所能表示的值的种类的数 量相同；选择步骤，选择与取得的上述位的值W相对应的乘法运算步骤；以及 重复控制步骤，对于系数k的所有的位，对上述取得步骤、上述 选择步骤及上述乘法运算步骤进行控制，以便重复地进行1个位的值 W的取得、与取得的位的值W相对应的乘法运算步骤的选择、以及 所选择的乘法运算步骤中进行的乘法运算，各乘法运算步骤，在椭圆曲线E上，将上述点C乘以取得的上 述位的值w所得到的乘法运算结果，在与该位相对应的位置上进行 加法运算，当存在满足取得的上述位的值w用除得开、而用2t+1除不开的 条件的非负整数t时,在与该位的值w相对应的上述乘法运算步骤中， 在椭圆曲线E上，进行包括点Q乘以w/2t而得到的点的加法运算或 点Q乘以lw/2l而得的点的减法运算的运算。
17、如权利要求16所述的计算机程序，其特征在于 上述计算机程序，记录在计算机可读取的记录媒体上。
全文摘要
在保持对简单功率分析攻击的耐受性的同时，可削减使用的表量。IC卡(100)，利用在椭圆曲线E上的点C乘以作为小于素数p的正整数的系数k来计算点k*C的椭圆曲线运算，对加密的信息进行解密。点k*C的运算，是将上述点C乘以取得的系数k的位(Window)的值所得到的相乘结果，在与该位相对应的位置上进行加法运算，并对所有位进行该运算。当存在满足取得的上述位的值可用2<sup>t</sup>除得开，而用2<sup>t+1</sup>除不开的条件的非负整数t时，各位的乘法运算，包括在椭圆曲线E上，点Q乘以w/2<sup>t</sup>所得到的点的加法运算。
文档编号G09C1/00GK101198998SQ20068002185
公开日2008年6月11日 申请日期2006年4月25日 优先权日2005年4月27日
发明者布田裕一, 松崎枣 申请人:松下电器产业株式会社
最新回复(0)