【手続補正書】
【提出日】平成17年1月19日(2005.1.19)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
楕円曲線上の元のべき倍演算を用いて、情報の秘密通信又はデジタル署名を行う楕円曲線演算装置であって、
楕円曲線上の元のべき倍演算と等価であり、１個以上の２倍算及び１個以上の加算の組合せから構成される組合せ演算を行うべき倍演算手段を含み、
前記べき倍演算手段は、前記組合せ演算を構成する２倍算及び加算のうち、１個の演算において、第１の座標系において、当該演算を行い、他の１個の演算において、前記第１の座標系とは異なる第２の座標系において、当該演算を行う
ことを特徴とする楕円曲線演算装置。
【請求項２】
前記第１の座標系は、アフィン座標系である
ことを特徴とする請求項１に記載の楕円曲線演算装置。
【請求項３】
前記第１の座標系は、ヤコビアン座標系である
ことを特徴とする請求項１に記載の楕円曲線演算装置。
【請求項４】
楕円曲線上の元のべき倍演算を用いて、情報の秘密通信又はデジタル署名を行う楕円曲線演算装置で用いられる楕円曲線演算方法であって、
前記楕円曲線演算装置は、楕円曲線上の元のべき倍演算と等価であり、１個以上の２倍算及び１個以上の加算の組合せから構成される組合せ演算を行うべき倍演算手段を含み、
楕円曲線演算方法は、
前記べき倍演算手段により、前記組合せ演算を構成する２倍算及び加算のうち、１個の演算において、第１の座標系において、当該演算を行うステップと、
前記べき倍演算手段により、他の１個の演算において、前記第１の座標系とは異なる第２の座標系において、当該演算を行うステップと
を含むことを特徴とする楕円曲線演算方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
上記従来例１でわかるように、楕円曲線を用いた署名方式では、固定点Ｇの冪倍の演算 kG 及び任意点 P(従来例では公開鍵Yaに相当)の冪倍の演算 kPの計算が必要である。このうち、固定点の演算は、以下の文献に知られるように、予めテーブルを用意しておくことが可能なので、高速に実現できる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
（従来例２）
pを160ビットの素数とし、有限体GF(p)上の楕円曲線を E とし、E(GF(p)) の任意の元 P に対して、 k*P の計算をする。ここで、kの２進表現を、
k = k0 + k1*２+ k2*2^2 + ・・・ + k159*2^159=[k159,....,k2,k1,k0]
(k0,・・・,k159 = 0,1）
とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
【課題を解決するための手段】
上述の問題点を解決するため、
本発明ではp を素数とし、有限体GF(p)上の楕円曲線を E:y^2=x^3+ax+b とし、E(GF(p)) の元を P = (x,y) を Z=1, X=x*Z^2, Y=y*Z^3 により変換した射影座標 (X,Y,Z) において、加算公式の内部点を修正ヤコビアンを特徴とする楕円曲線演算装置としている。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
本発明では、pを素数とし、rを正整数とするとき、有限体GF(p^r)上の楕円曲線を E とし、E(GF(p^r)) の元を
P = (x,y) を Z=1, X=x*Z^2, Y=y*Z^3
により変換した射影座標 (X,Y,Z) において、加算公式の内部点を修正ヤコビアンを特徴とする楕円曲線演算装置としている。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
本発明では、上記楕円曲線演算装置において、E(GF(p)) の元を修正ヤコビアン座標
P=(X1, Y1, Z1, a*Z1^4), Q=(X2, Y2, Z2, a*Z2^4) (P ≠ Q)
で表すとき，
P+Q=R=(X3, Y3, Z3, a*Z3^4)を、
U1=X1*Z2^2, U2=X2*Z1^2, S1=Y1*Z2^3,
S2=Y2*Z1^3, H=U2-U1, r=S2-S1
を計算し、
X3 = -H^3 -2U1*H^2+ r^2,
Y3 = -S1*H^3 + r(U1*H^2 -X3),
Z3 = Z1*Z2*H,
a*Z3^4 = a(Z3^2)^2
により求めることを特徴とした楕円曲線演算装置としている。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
本発明では、上記楕円曲線演算装置において、E(GF(p)) の元を、修正ヤコビアン座標
P=(X1, Y1, Z1, a*Z1^4)
とするとき、2P=R=(X3, Y3, Z3, a*Z3^4)を、
S=4X1*Y1^2, M=3X1^2+a*Z1^4, T=-2S+M^2
を計算し、
X3 = T,
Y3 = -8Y1^4 + M(S-T),
Z3 = 2Y1*Z1,
a*Z3^4 = 2^4*(Y1^4)*(a*Z1^4)
により求めることを特徴とした楕円曲線演算装置としている。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
本発明では、pを素数とし、kを正整数とするとき、有限体 GF(p) 上の楕円曲線を
E:y^2=x^3+ax+b
とし、
E(GF(p)) の元 P = (x,y) の冪倍点 kP= P + ... + P(k回の加算)
の計算を、座標を２個以上組み合わせて行なうことを特徴とした楕円曲線演算装置を特徴とする楕円曲線演算装置としている。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
本発明では、p を素数とし、r,k を正整数とし、有限体GF(p^r)上の楕円曲線を E とし、E(GF(p^r)) の元 P= (x,y) の冪倍点 kP = P + ... +P(k回の加算)の計算を、座標を２個以上組み合わせて行なうことを特徴とした楕円曲線演算装置としている。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
本発明では、pを素数、kを正整数、有限体GF(p)上の楕円曲線を
E:y^2=x^3+ax+b とし、
E(GF(p)) の元 P = (x,y) の冪倍点 kP= P + ... + P(k回の加算)
を計算する上記楕円曲線演算装置において、wを正整数とし、kを
k=2^k0(2^k1(・・・ (2^kvW[v] +W[v-1])・・・)+W[0])
(W[i] は奇数, かつ1 ≦ W[i] ≦2^w-1)
と表すとき、テーブル
iP = Pi=(xi,yi) (i は奇数，かつ 1 ≦ i ≦ 2^w-1)
をアフィン座標で計算し、kP の計算を、(ki-1) 回の2倍点の計算は、本発明の座標(X, Y, Z, a*Z^4) で行い、ki 回目の２倍点の結果は、ヤコビアン座標 (X, Y, Z) で求め、(X,Y,Z)とテーブルの点Piとの加算は、本発明の座標 (X, Y, Z,a*Z^4)で求めることを、繰り返すことによって得ることを特徴とした楕円曲線演算装置としている。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
本発明では、p を素数、kを正整数、有限体GF(p)上の楕円曲線を
E:y^2=x^3+ax+b
とし、E(GF(p)) の元 P = (x,y) の冪倍点 kP= P + ... + P(k回の加算)
を計算する上記楕円曲線演算装置において、wを正整数とし、kを
k=2^k0(2^k1(・・・ (2^kvW[v] +W[v-1])・・・)+W[0])
(W[i] は奇数, かつ1 ≦ W[i] ≦2^w-1)
と表すとき、テーブル
iP = Pi=(Xi,Yi,Zi,Zi^2,Zi^3) (iは奇数，かつ 1 ≦ i ≦ 2^w-1)
をチャドノブスキヤコビアン座標で求め、kP の計算を、(ki-1) 回の2倍点の計算は、本発明の修正ヤコビアン座標(X,Y, Z, a*Z^4) で行い、ki 回目の２倍点の結果は、ヤコビアン座標 (X, Y, Z)で求め、(X,Y,Z)とテーブルの点Piとの加算は、本発明の修正ヤコビアン座標(X, Y, Z,a*Z^4)で求めることを、繰り返すことによって得ることを特徴とした楕円曲線演算装置としている。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
本発明では、pを素数、kを正整数、有限体GF(p)上の楕円曲線を
E:y^2=x^3+ax+b とし、
E(GF(p)) の元 P = (x,y) の冪倍点 kP= P + ... + P(k回の加算)
を計算する上記楕円曲線演算装置において、wを正整数とし、kを
k=2^k0(2^k1(・・・ (2^kvW[v] +W[v-1])・・・)+W[0])
(W[i] は奇数，かつ1 ≦ W[i] ≦2^w-1)
と表すとき、テーブル
iP = Pi=(Xi,Yi,Zi,Zi^2,Zi^3) (iは奇数，かつ 1 ≦ i ≦ 2^w-1)
をチャドノブスキヤコビアン座標で求めるとき、はじめに、2P=(x,y) をアフィン座標で求めることを特徴とした楕円曲線演算装置としている。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】変更
【補正の内容】
【００３３】
本発明では、pを素数、kを正整数、有限体GF(p)上の楕円曲線を
E:y^2=x^3+ax+b とし、
E(GF(p)) の元 P = (x,y) の冪倍点 kP= P + ... + P(k回の加算)
を計算する上記楕円曲線演算装置において、wを正整数とし、kを
k=2^k0(2^k1(・・・ (2^kvW[v] +W[v-1])・・・)+W[0])
(W[i] は奇数, かつ1 ≦ W[i] ≦2^w-1)
と表すとき、テーブル
iP = Pi=(Xi,Yi,Zi,Zi^2,Zi^3) (iは奇数，かつ 1 ≦ i ≦ 2^w-1)
をチャドノブスキヤコビアン座標で求めるとき、はじめに、2P=(x,y) をチャドノブスキヤコビアン座標で求めることを特徴とした楕円曲線演算装置としている。