説明

楕円曲線スカラ倍演算方法、ECDSA鍵ペア生成方法、ECDSA署名生成方法、ECDSA署名検証方法、プログラム、楕円曲線スカラ倍演算装置、ECDSA鍵ペア生成装置、ECDSA署名生成装置およびECDSA署名検証装置

【課題】効率的な楕円曲線スカラ倍演算を行うことを目的とする。
【解決手段】拡張Inverted twisted Edward座標を用いて表現した素数位数の点である前記第1の点および任意の整数が入力されると、前記整数を2進数展開し、前記展開した2進数の係数ごとに、(a)前記第1の点を、Inverted twisted Edward座標を用いて表現した点に置換した上で、前記変換した第1の点の2倍算を行い、前記2倍算の結果を拡張Inverted twisted Edward座標を用いて表現した素数位数の点である第3の点に変換し、(b)前記係数が1である場合、前記第1の点と、前記第3の点の加算処理を行う。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、楕円曲線スカラ倍演算方法、ECDSA鍵ペア生成方法、ECDSA署名生成方法、ECDSA署名検証方法、プログラム、楕円曲線スカラ倍演算装置、ECDSA鍵ペア生成装置、ECDSA署名生成装置およびECDSA署名検証装置の技術に関する。
【背景技術】
【0002】
楕円曲線上の離散対数問題を用いたデジタル署名方式としてECDSA(Elliptic Curve Digital Signature Algorithm)署名が知られている。この署名方式は楕円曲線上の加算やスカラ倍算を用いて実現される(例えば、非特許文献1参照)。このため、特にスカラ倍算は署名の処理速度に大きく影響するため高速処理が重要な課題となる。
スカラ倍の高速処理に適した楕円曲線としてTwisted Edward型楕円曲線が知られている(例えば、非特許文献2参照)。
【0003】
まず、非特許文献2に基づきTwisted Edward型楕円曲線について説明する。
Twisted Edward型楕円曲線とは標数が2以外の有限体をkとした場合、ax2+y2=1+dx22 (a,dはk上の定数)で表される曲線で曲線上の点は、曲線の方程式を満たすx,y∈kの組(x,y)で表すことができる。
【0004】
k上で係数aは2乗根を持ち係数dは持たない場合、Twisted Edward型楕円曲線上の2点P,Qに対して加算P+Qが、1点Pに対して2倍算2Pが定義でき具体的な計算方法が知られている。
Twisted Edward型楕円曲線上の2点P=(x1,y1)、Q=(x2,y2)に対して加算は以下の式(1)で計算することができる。
【0005】
【数1】

【0006】
さらに点P=(x1,y1)に対して2倍算は上記加算公式においてP=Qとすることで計算できる。以下に示す式(2)は2倍算に特化した形で前記した加算公式(式(1))を記載したものである。
【0007】
【数2】

【0008】
また、点P=(x1,y1)に対して−Pを(−x1,y1)で定義する。
Twisted Edward型楕円曲線上の点全体からなる集合は加算に対して(0,1)を単位元とする加法群の構造を持つ。またTwisted Edward型楕円曲線上の点Pおよび、正整数Lに対してPのL回加算LPを求める演算をスカラ倍と呼ぶ。
また、Twisted Edward型楕円曲線上の点Pに対してPをn回加算するスカラ倍の演算結果nPが単位元である(0,1)となる場合、正整数nを点Pの位数と呼ぶ。
【0009】
非特許文献3において係数dを用いない加算方法が開示されている。以下、非特許文献3に基づき上記加算方法を説明する。
楕円曲線上の2点をP=(x1,y1)、Q=(x2,y2)、P≠Q、PおよびQは素数位数とした場合、加算P+Qは以下の式(3)で計算することができる。
【0010】
【数3】

【0011】
非特許文献2に開示されている加算および2倍算では有限体k上の乗算に比べて10倍以上演算コストの大きい逆元計算が用いられる。この問題に対して逆元計算を用いないことでより高速な加算および2倍算の計算方法が非特許文献2に開示されている。
【0012】
具体的には、点(x,y)をx=Z/X、y=Z/Y、XYZ≠0を満たすX,Y,Z∈kを用いて変換したInverted Twisted Edward座標(X:Y:Z)を用いて逆元計算をより負荷の少ない数回の乗算に置き換えることにより高速化を行う。
【0013】
次に、非特許文献2に基づき逆元計算の必要の無い加算アルゴリズムを示す。
入力情報:(X1:Y1:Z1),(X2:Y2:Z2
出力情報:(X3:Y3:Z3)=(X1:Y1:Z1)+(X2:Y2:Z2
処理手順:なお、各処理の最後のM,S,Dは、それぞれ定義体k上の乗算、2乗算、定数倍算の演算コストである。
(1)計算機が、A←Z12、B←dA2、C←X12、D←Y12、E←CDをk上でそれぞれ計算する(4M,1S,1D)。
(2)計算機が、H←C−aD、I←(X1+Y1)(X2+Y2)−C−Dをk上でそれぞれ計算する(1M,1D)。
(3)計算機が、X3←(E+B)Hをk上で計算する(1M)。
(4)計算機が、Y3←(E−B)Iをk上で計算する(1M)。
(5)計算機が、Z3←AHIをk上で計算する(2M)。
(6)計算機が、(X3:Y3:Z3)を演算結果として出力する。
この加算アルゴリズムの総演算コストは9M+1S+2Dとなる。
【0014】
次に、非特許文献2に基づき逆元計算の必要の無い2倍算アルゴリズムを示す。
入力情報:(X1:Y1:Z1
出力情報:(X3:Y3:Z3)=2(X1:Y1:Z1
処理手順:
(1)計算機が、A←X12、B←Y12、U←aBをk上でそれぞれ計算する(2S,1D)。
(2)計算機が、C←A+U、D←A−U、E←(X1+Y12−A−Bをk上でそれぞれ計算する(1S)。
(3)計算機が、X3←CDをk上で計算する(1M)。
(4)計算機が、Y3←E(C−2dZ12)をk上で計算する(1M,1S,1D)。
(5)計算機が、Z3←DEをk上で計算する(1M)。
(6)計算機が、(X3:Y3:Z3)を演算結果として出力する。
この2倍算アルゴリズムの総演算コストは3M+4S+2Dとなる。
【0015】
次に、Twisted Edward型楕円曲線上の加算および、2倍算を組み合わせることでスカラ倍を計算するアルゴリズムを示す。
入力:楕円曲線上の点P,整数L(L>0)
出力:Q=LP
処理手順:
(1)計算機が、整数Lを2進数展開して、L=L0+L1×2+・・・+Lt-1×2t-1 (Lt-1=1)とする。
(2)計算機が、Q←Pとおく。
(3)計算機が、i←t−2とおく。
(4)i≧0を満たす間、計算機は、以下の処理(4−1)〜(4−2)を繰返す。
(4−1)計算機が、Q←2Qを計算する。
(4−2)計算機が、Li=1であればQ←Q+Pを計算する。
(4−3)計算機が、i←i−1を計算する。
(5)計算機が、計算結果としてQを出力する
【0016】
次に、非特許文献1に開示されているECDSA署名に基づき、Twisted Edward型楕円曲線および、Inverted Twisted Edward座標を用いたECDSA署名について説明する。
以下、本明細書において楕円曲線とはTwisted Edward型楕円曲線を示すこととする。
なお、楕円曲線ax2+y2=1+dx22の素数位数のベースポイントG=(x,y)はInverted Twisted Edward座標を用いてG=(XG:YG:1)=(1/x,1/y,1)に変換し、以後Inverted Twisted Edward座標を用いて楕円曲線上の演算を行う。またZ座標が1であることからGのスカラ倍におけるGの加算時に1回の乗算を削減することができる。
公開鍵Qについても同様の理由でZ=1となるように変形を行う。
【0017】
ECDSA署名は以下の3つの処理より構成される。
(1)鍵ペア生成:計算機が、ECDSA署名の生成および検証に用いる鍵ペアの生成を行う。鍵ペアの内、署名生成に用いる秘密鍵は署名生成者が外部に漏れないよう厳重に保管し、署名検証に用いる公開鍵は外部に公開する。
(2)署名生成:計算機が、秘密鍵を用いて署名対象の平文に対するデジタル署名を生成する。
(3)署名検証:計算機が、公開鍵、署名対象の平文およびデジタル署名を用いて署名の検証を行う。
【0018】
以下、上記(1)〜(3)の処理を詳細に説明する。
(1)鍵生成:
入力情報:楕円曲線ax2+y2=1+dx22 (k上で係数aは2乗根を持ち係数dは持たない)、定義体k、楕円曲線のベースポイントG=(XG:YG:1)、ベースポイントの位数n(素数)
出力情報:秘密鍵c、公開鍵Q=(XQ:YQ:1)
(1−1)計算機が、0<c<nを満たす整数cをランダムに生成し秘密鍵とする。
(1−2)計算機が、楕円曲線上のスカラ倍Q1←cG=(X:Y:Z)を計算する。
(1−3)計算機が、Q←(XQ:YQ:1)=(Z/X:Z/Y:1)をk上で計算し公開鍵とする。
(1−3)計算機が、鍵ペアc、Qを出力する。
【0019】
(2)署名生成:
入力情報:楕円曲線ax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない) 、定義体k、楕円曲線のベースポイントG=(XG:YG:1)、ベースポイントの位数n(素数)、署名対象データM、秘密鍵c
出力情報:署名(r,s)
(2−1)計算機が、0<b<nを満たす整数bをランダムに生成する。
(2−2)計算機が、楕円曲線上のスカラ倍R←bG=(X1:Y1:Z1)を計算する。
(2−3)計算機が、x1←Z1/X1をk上で計算する。
(2−4)計算機が、定義体k上の元x1を正の整数に変換したものをx1としておき直す。
(2−5)計算機が、r←x1 mod n を計算する。
(2−6)計算機が、ハッシュ関数hを用いてe←h(M)を計算する。
(2−7)計算機が、s←b-1(e+cr) mod nを計算する。
(2−8)計算機が、署名対象データMの署名として(r,s)を出力する。
【0020】
(3)署名検証:
入力情報:楕円曲線ax2+y2=1+dx22 (k上で係数aは2乗根を持ち係数dは持たない)、定義体k、楕円曲線のベースポイントG=(XG:YG:1)、公開鍵Q=(XQ:YQ:1)、ベースポイントおよび公開鍵の位数n(素数)、 署名検証対象データM、署名(r,s)
出力情報:True(検証成功)またはFalse(検証失敗)
(3−1)計算機が、署名生成時と同じハッシュ関数hを用いてe←h(M)を計算する。
(3−2)計算機が、e1← s-1e mod nを計算する。
(3−3)計算機が、r1← s-1r mod nを計算する。
(3−4)計算機が、G1←e1Gを計算する。
(3−5)計算機が、Q1←r1Qを計算する。
(3−6)計算機が、R1←(X1:Y1:Z1)=G1+Q1を計算する。
(3−7)計算機が、x1←Z1/X1をk上で計算する。
(3−8)計算機が、署名生成時と同じ変換方法でk上の元x1を正の整数に変換したものをx1としておき直す。
(3−9)計算機が、x1 mod n = rが成立すればTrue、しなければFalseを出力。
【先行技術文献】
【非特許文献】
【0021】
【非特許文献1】ANSI X9.62-1998,"Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", American National Standard for Financial Services, 1998.
【非特許文献2】Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters,"Twisted Edwards curves." In AFRICACRYPT 2008, volume 5023 of LNCS,p389-p405. Springer, 2008.
【非特許文献3】Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson,"Twisted Edwards Curves Revisited." In ASIACRYPT 2008, volume 5350 of LNCS, p326-p343 Springer, 2008.
【発明の概要】
【発明が解決しようとする課題】
【0022】
前記したECDSA署名では、楕円曲線上のスカラ倍演算処理が必須である。しかし、スカラ倍演算は署名処理において負荷が重いため処理性能に大きな影響を及ぼすことが知られている。
また、スカラ倍の処理性能は楕円曲線の定義体上の乗算および、2乗算、定数倍算の回数に依存することが知られている。
【0023】
また、係数dを用いない加算方法についてInverted Twisted Edward座標の適用可能性は非特許文献3において開示されていない。
【0024】
このような背景に鑑みて本発明がなされたのであり、本発明は、効率的な楕円曲線スカラ倍演算を行うことを目的とする。
【課題を解決するための手段】
【0025】
前記課題を解決するため、本発明は、Inverted twisted Edward座標を拡張した拡張Inverted twisted Edward座標を用いて表現した素数位数の点である第1の点を整数倍して、Inverted twisted Edward座標を用いて表現した第2の点を算出する楕円曲線スカラ倍演算装置による楕円曲線スカラ倍演算方法であって、入力部を介して、前記第1の点および任意の整数が入力されると、楕円曲線スカラ倍演算装置が、前記整数を2進数展開し、前記展開した2進数の係数ごとに、(a)および(b)の処理を行うことを特徴とする楕円曲線スカラ倍演算方法。
(a)前記第1の点を、Inverted twisted Edward座標を用いて表現した点に置換した上で、前記変換した第1の点の2倍算を行い、前記2倍算の結果を拡張Inverted twisted Edward座標を用いて表現した素数位数の点である第3の点に変換し、(b)前記係数が1である場合、前記第1の点と、前記第3の点の加算処理を行う。
その他の解決手段については、実施形態中で適宜説明する。
【発明の効果】
【0026】
本発明によれば、効率的な楕円曲線スカラ倍演算を行うことができる。
【図面の簡単な説明】
【0027】
【図1】本実施形態に係る楕円曲線スカラ倍演算装置の構成例を示す図である。
【図2】本実施形態に係る楕円曲線スカラ倍演算部の構成例を示す図である。
【図3】本実施形態に係る楕円曲線スカラ倍演算処理の全体処理を説明するためのフローチャートである。
【図4】ステップS104における2倍算処理の手順を示すフローチャートである。
【図5】ステップS106において係数dを用いる加算処理の手順を示すフローチャートである。
【図6】ステップS106において係数aが−1かつ係数dを用いる加算処理の手順を示すフローチャートである。
【図7】ステップS106において係数dを用いない加算処理の手順を示すフローチャートである。
【図8】ステップS106において係数aが−1かつ係数dを用いない加算処理の手順を示すフローチャートである。
【図9】本実施形態に係るECDSA鍵ペア生成装置の構成例を示す図である。
【図10】本実施形態に係るECDSA鍵ペア生成処理の手順を示すフローチャートである。
【図11】本実施形態に係るECDSA署名生成装置の構成例を示す図である。
【図12】本実施形態に係るECDSA署名生成処理の手順を示すフローチャートである。
【図13】本実施形態に係るECDSA署名検証装置の構成例を示す図である。
【図14】本実施形態に係るECDSA署名検証処理の手順を示すフローチャートである。
【図15】ステップS906の詳細な処理手順を示すフローチャートである。
【図16】情報処理装置のハードウェア構成例を示す図である。
【発明を実施するための形態】
【0028】
次に、本発明を実施するための形態(「実施形態」という)について、適宜図面を参照しながら詳細に説明する。なお、本実施形態では、拡張Inverted twisted Edward座標を用いることで、楕円曲線スカラ倍演算における演算コスとを低減することを目的とする。
【0029】
《楕円曲線スカラ倍演算》
[楕円曲線スカラ倍演算装置]
図1は、本実施形態に係る楕円曲線スカラ倍演算装置の構成例を示す図である。
楕円曲線スカラ倍演算装置1は、制御演算部110と、記憶部120を有している。
制御演算部110は、入出力部111と、制御部112と、楕円曲線スカラ倍演算部113とを有する。入出力部111は、入力情報としての演算対象データおよび出力情報としての演算結果の入出力を行う機能を有する。制御部112は、楕円曲線スカラ倍演算装置1全体を制御する機能を有する。楕円曲線スカラ倍演算部113は、実際に楕円曲線上のスカラ倍演算を計算する機能を有する。
記憶部120には、中間データ121、データ122などが格納されている。中間データ121は、必要に応じて処理中に生成されるデータである。データ122は、楕円曲線のパラメータなどのデータである。
【0030】
図2は、本実施形態に係る楕円曲線スカラ倍演算部の構成例を示す図である。
楕円曲線スカラ倍演算部113は、入出力部114と、2進数展開部115と、楕円曲線加算演算部116と、楕円曲線2倍算演算部117と、基本演算部118とを有する。
2進数展開部115は、整数の2進数展開を行う機能を有する。楕円曲線加算演算部116は、楕円曲線上の2点の加算を行う機能を有する。楕円曲線2倍算演算部117は、楕円曲線上の点の2倍算を行う機能を有する。基本演算部118は、楕円曲線加算演算部116および楕円曲線2倍算演算部117から必要に応じて呼び出され楕円曲線の定義体上の演算や剰余計算(mod)を用いた四則演算などを行う機能を有する。
【0031】
なお、楕円曲線スカラ倍演算装置1は、図16に示すような、バス57で接続されたCPU(Central Processing Unit)51と、RAM(Random Access Memory)などのメモリ52と、HD(Hard Disk)やその他の外部記憶装置55と、キーボードなどの入力装置53と、ディスプレイなどの出力装置54と、外部記憶装置55や、入力装置53や、出力装置54とのインタフェース56とを備えた、一般的な構成を有する情報処理装置5上に構築することができる。
楕円曲線スカラ倍演算装置1の制御演算部110および各部111〜118は、CPU51が、メモリ52にロードされたプログラム(コードモジュールともいう)を実行することで、情報処理装置5上に具現化される。また、メモリ52や、外部記憶装置55が記憶部120として使用される。
【0032】
また、前記したプログラムは、予め外部記憶装置55に記憶され、必要に応じてメモリ52上にロードされ、CPU51により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばCD−ROM(Compact Disk-Read Only Memory)などを介して、必要に応じて、可搬性の記憶媒体からメモリ52にロードされてもよい。また、プログラムは、一旦、CD−ROMなどの可搬性の記憶媒体からHDなどにインストールされた後、必要に応じて、このHDからメモリ52にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置5が伝送信号により、一旦HDにダウンロードされてからメモリ52にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ52にロードされてもよい。
【0033】
[楕円曲線スカラ倍演算処理]
次に、図2を参照しつつ、図3〜図8に沿って楕円曲線スカラ倍演算処理の手順を説明する。
ここで、全体概要を説明すると、入出力部111により入力を受け付けた楕円曲線ax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、加算時の係数d使用の有無、拡張Inverted twisted Edward座標を用いて表現した素数位数の点P=(X1:Y1:T1:Z1)、整数L(L>0)の各入力情報は、記憶部120に保持される。
そして、制御演算部110が、記憶部120で保持されている各入力情報を用いて、図3〜図8に示すスカラ倍演算処理を行い、Inverted twisted Edward座標を用いて表現した演算結果Q=LP=(X3:Y3:Z3)を求め、出力する。
【0034】
(全体処理)
図3は、本実施形態に係る楕円曲線スカラ倍演算処理の全体処理を説明するためのフローチャートである。
ステップS101において、2進数展開部115が、Lを2進数展開して、L=L0+L1×2+・・・+Lt-1×2t-1 (Lt-1=1)とする。
ステップS102において、基本演算部118が、d1←2d、i←t−2、Q←Pとおく。
ステップS103において、基本演算部118が、i=−1であるか否かを判定し、i=−1であれば(S103→Yes)、ステップS109の処理に進み、そうでなければ(S103→No)、ステップS104の処理に進む。
ステップS104において、楕円曲線2倍算演算部117が、Q←2Qを計算する。ステップS104の計算方法は図4を参照して後記する。
ステップS105において、基本演算部118が、Li=1であるか否かを判定し、Li=1であれば(S105→Yes)、ステップS106の処理に進み、そうでなければ(S105→No)、ステップS107の処理に進む。
【0035】
ステップS106において、楕円曲線加算演算部116が、Q←Q+Pを計算する。ステップS106の計算方法は、係数dを用いる設定がされている場合は図5を参照して後記し、係数aが−1かつ係数dを用いる設定がされている場合は図6を参照して後記し、入力時にdを用いない設定がされている場合は図7を参照して後記し、係数aが−1かつ入力時にdを用いない設定がされている場合は図8を参照して後記する。
ステップS107において、基本演算部118が、i←i−1を計算する。
ステップS108において、基本演算部118が、i≧0であるか否かを判定し、i≧0であれば(S108→Yes)、ステップS104の処理に戻り、そうでなければ(S108→No)、ステップS109の処理に進む。
ステップS109において、楕円曲線スカラ倍演算部113が、Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)を演算結果として出力する。
【0036】
(2倍算処理)
次に、図2を参照しつつ、図4に沿って図3のステップS104における2倍算処理について説明する。なお、これ以降、各処理の最後に記述してあるM,S,Dは、それぞれ定義体k上の乗算、2乗算、定数倍算の演算コストを示す。
図4は、ステップS104における2倍算処理の手順を示すフローチャートである。
なお、入力時におけるQの座標は(X2:Y2:T2:Z2)または(X2:Y2:Z2)であるとする。
ステップS201において、楕円曲線2倍算演算部117が、必要に応じてQを置換する。具体的には、楕円曲線2倍算演算部117が、Q=(X2:Y2:T2:Z2)であればT2を無視しQをQ←(X2:Y2:Z2)に置換し、それ以外であれば置換を行わない。
ステップS202において、楕円曲線2倍算演算部117が、A←X22、B←Y22、U←aBをk上でそれぞれ計算する(2S,1D)。ここでa=−1である場合、U←aBはk上でBの符号を反転することにより定数倍算を用いないで計算できるため、演算コストを1D削減することができる。
ステップS203において、楕円曲線2倍算演算部117が、C←A+U、D←A−U、E←(X2+Y22−A−B、H←(C−d122)をk上でそれぞれ計算する(2S,1D)。
【0037】
ステップS204において、楕円曲線2倍算演算部117が、X3←CDをk上で計算する(1M)。
ステップS205において、楕円曲線2倍算演算部117が、Y3←EHをk上で計算する(1M)。
ステップS206において、楕円曲線2倍算演算部117が、Li=1であればT3←CHをk上で計算する(1M)。Li=1でなければ、何も行わない。
ステップS207において、楕円曲線2倍算演算部117が、Z3←DEをk上で計算する(1M)。
ステップS208において、楕円曲線2倍算演算部117が、ステップS206でT3を計算している場合、2倍算の演算結果を拡張Inverted twisted Edward座標を用いてQ←(X3:Y3:T3:Z3)とおき、そうでなければInverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおき、それぞれを演算結果として出力する。
この2倍算の総演算コストは、ステップS206においてT3を計算しない場合、3M+4S+2D、ステップS206においてT3を計算する場合、4M+4S+2Dとなる。
またa=−1である場合、ステップS206においてT3を計算しない場合、3M+4S+D、ステップS206においてT3を計算する場合、4M+4S+Dとなる。
【0038】
ここで、図4の処理について詳細に説明する。
まず、非特許文献2に基づくInverted twisted Edward座標(X:Y:Z)を用いた(X3:Y3:Z3)=2(X2:Y2:Z2)を計算する2倍算は以下の式(4)〜(6)で計算できる。
【0039】
【数4】

【0040】
次に、この非特許文献2記載の2倍算計算方法を本実施形態による、すなわち拡張Inverted twisted Edward座標を用いるスカラ倍演算手段に適するよう変形する。
つまり、2倍算に続いて拡張Inverted twisted Edward座標(X:Y:T:Z)を用いて加算を行う場合のみ、上記のInverted twisted Edward座標(X3:Y3:Z3)に加えて1/x33=Z3/T3を満たすT3座標を求める必要がある。
ここで、T3は以下の条件(式(7))を満たす。
【0041】
【数5】

【0042】
さらに変形して、式(8)を得る。
【0043】
【数6】

【0044】
以上より、T3は、式(9)とおける。
【0045】
【数7】

【0046】
また、2倍算においてT座標は使用しないため、2倍算の後に2倍算が行われる場合、T座標を計算する必要がないため出力はInverted twisted Edward座標(X3:Y3:Z3)を用いる。
さらに、入力が拡張Inverted twisted Edward座標を用いてQ=(X2:Y2:T2:Z2)であった場合、T2座標を無視することによりInverted twisted Edward座標Q=(X2:Y2:Z2)とみなして2倍算を行う。
以上をアルゴリズムの形でまとめると、図4で示す手順となる。
【0047】
(加算処理)
次に、図2を参照しつつ、図5〜図8に沿って図3のステップS106における処理を説明する。
まず、図5は、ステップS106において係数dを用いる加算処理の手順を示すフローチャートである。
なお、入力時におけるPの座標は(X1:Y1:T1:Z1)、Qの座標は(X2:Y2:T2:Z2)であるとする。
ステップS301において、楕円曲線加算演算部116が、A←X12、B←Y12、D←T12をk上でそれぞれ計算する(3M)。
ステップS302において、楕円曲線加算演算部116が、Z1=1であるか否かを判定し、Z1=1であれば(S302→Yes)、ステップS303の処理に進み、そうでなければ(S302→No)、ステップS304の処理に進む。
ステップS303において、楕円曲線加算演算部116が、C←dZ2をk上で計算しステップS305に進む(1D)。
ステップS304において、楕円曲線加算演算部116が、C←dZ12をk上で計算しステップS305に進む(1D,1M)。
ステップS305において、楕円曲線加算演算部116が、E←(X1+Y1)(X2+Y2)−A−Bをk上で計算する(1M)。
ステップS306において、楕円曲線加算演算部116が、F←D−C、G←D+C、H←A−aBをk上でそれぞれ計算する(1D)。
ステップS307において、楕円曲線加算演算部116が、X3←HGをk上で計算する(1M)。
ステップS308において、楕円曲線加算演算部116が、Y3←EFをk上で計算する(1M)。
ステップS309において、楕円曲線加算演算部116が、Z3←HEをk上で計算する(1M)。
ステップS310において、楕円曲線加算演算部116が、演算結果をInverted twisted Edward座標を用いてQ←(X3:Y3:Z3)として、出力する。
図5の処理手順による加算アルゴリズムの総演算コストは8M+2D(Z1=1以外,S302→No)、7M+2D(Z1=1,S302→Yes)となる。
【0048】
ここで、図5の処理について詳細に説明する。
非特許文献3に基づく加算公式によるとTwisted Edward型楕円曲線上の2点P=(x1,y1)、Q=(x2,y2)に対して係数dを用いる加算P+Q=(x3,y3)は以下の式(10)で計算することができる。
【0049】
【数8】

【0050】
次に、式(10)より図5の加算アルゴリズムを導く。
2点P=(x1,y1)、Q=(x2,y2)と拡張Inverted twisted Edward座標を用いて表現したP=(X1:Y1:T1:Z1)、Q=(X2:Y2:T2:Z2)は以下の関係を満たす。
1=Z1/X1,y1=Z1/Y1,x11=Z1/T1,x2=Z2/X2,y2=Z2/Y2,x22=Z2/T2
これらの式を、式(10)へ代入することによって加算公式(式(10))を変形すると、以下の式(11)を得る。
【0051】
【数9】

【0052】
次に、式(12)より式(13)を得ることができる。
【0053】
【数10】

【0054】
【数11】

【0055】
式(13)を用いて、更に加算公式(式(11))を変形すると、式(14)を得る。
【0056】
【数12】

【0057】
式(14)を、更に変形することにより、最終的にP+Qは以下の式(15)を計算することで求められる。
【0058】
【数13】

【0059】
この式(15)よりx3=Z3/X3、y3=Z3/Y3、x33=Z3/T3を満たすX3、Y3、T3、Z3をそれぞれ求めると、以下の式(16)〜(19)となる。
【0060】
【数14】

【0061】
式(16)〜(19)を用いることにより、P+Q=(X1:Y1:T1:Z1)+(X2:Y2:T2:Z2)=(X3:Y3:T3:Z3)を計算することができる。
実際に、x3=Z3/X3、y3=Z3/Y3、x33=Z3/T3を満たしていることは以下の式(20)〜(22)で確認できる。
【0062】
【数15】

【0063】
ここでT3は加算演算のみで用い2倍算では必要が無いこと、スカラ倍において加算の次に行われる演算は必ずT座標の必要の無い2倍算であることからT3を計算する必要は生じない。
この内容をアルゴリズムの形でまとめると、図5に示す処理手順となる。
【0064】
次に、図3のステップS106における係数aが−1かつ係数dを用いる加算処理について説明する。
図6は、ステップS106において係数aが−1かつ係数dを用いる加算処理の手順を示すフローチャートである。
なお、入力時におけるPの座標は(X1:Y1:T1:Z1)、Qの座標は(X2:Y2:T2:Z2)であるとする。なお、図6では係数dをd1とする。
ステップS401において、楕円曲線加算演算部116が、A←(X1+Y1)(X2+Y2)、B←(X1−Y1)(X2−Y2)、D=2T12 をk上でそれぞれ計算する(3M)。なお、この処理において、定義体k上の2倍算が含まれるが、より演算コストの小さい加算もしくは1ビットシフトなどの演算を用いることでコストの大きい乗算を用いないで計算できるため定数倍としては扱わない。
ステップS402において、楕円曲線加算演算部116が、Z1=1であるか否かを判定し、Z1=1であれば(S402→Yes)、ステップS403の処理に進み、そうでなければ(S402→No)、ステップS404の処理に進む。
ステップS403において、楕円曲線加算演算部116が、C←d12をk上で計算しステップS405に進む(1D)
ステップS404において、楕円曲線加算演算部116が、C←d112をk上で計算しステップS405に進む(1M,1D)。
ステップS405において、楕円曲線加算演算部116が、E=A−B、F=D−C、G=D+C、H=A+Bをそれぞれk上で計算する。
ステップS406において、楕円曲線加算演算部116が、X3=HGをk上で計算する(1M)
ステップS407において、楕円曲線加算演算部116が、Y3=EFをk上で計算する(1M)。
ステップS408において、楕円曲線加算演算部116が、Z3=HEをk上で計算する(1M)。
ステップS409において、楕円曲線加算演算部116が、演算結果をInverted twisted Edward座標を用いてQ←(X3:Y3:Z3)として、出力する。
図6に示す加算アルゴリズムの総演算コストは7M+D(Z1=1以外,S402→No)、6M+D(Z1=1,S402→Yes)となる。
【0065】
ここで、図6の処理について詳細に説明する。
図5における加算方法を変形することにより、図6の加算アルゴリズムを導く。
図5における加算方法(式(16)〜(19))に対して、に対してa=−1を代入することにより式(23)〜(26)が得られる。
【0066】
【数16】

【0067】
【数17】

【0068】
式(23)〜(26)を用いることによりP+Q=(X1:Y1:T1:Z1)+(X2:Y2:T2:Z2)=(X3:Y3:T3:Z3)を計算することができ、(X3:Y3:T3:Z3)の代わりに(X4:Y4:T4:Z4)=(4X3:4Y3:4T3:4Z3)を用いてもx3=Z4/X4、y3=Z4/Y4、x33=Z4/T4を満たすことから、以下の式(27)〜(30)を用いることによりP+Q=(X1:Y1:T1:Z1)+(X2:Y2:T2:Z2)=(X3:Y3:T3:Z3)を計算できることが分かる。
【0069】
【数18】

【0070】
また、X3、Y3、Z3座標を求める際に必要となる式は以下の条件(式(31),(32))を満たす。
【0071】
【数19】

【0072】
これらの関係式を用いて加算公式(式(10))をアルゴリズムの形で記載すると、図6に示す処理手順となる。
【0073】
図7は、ステップS106において係数dを用いない加算処理の手順を示すフローチャートである。
なお、図7において、入力時のPの座標は(X1:Y1:T1:Z1)、Qの座標は(X2:Y2:T2:Z2)であるとする。
ステップS501において、楕円曲線加算演算部116が、A←X12、B←Y12、D←T12をk上でそれぞれ計算する(3M)。
ステップS502において、楕円曲線加算演算部116が、Z1=1であるか否かを判定し、Z1=1であれば(S502→Yes)、ステップS503の処理に進み、そうでなければ(S502→No)、ステップS504に進む。
ステップS503において、楕円曲線加算演算部116が、C←T2とおきステップS505に進む。
ステップS504において、楕円曲線加算演算部116が、C←T21をk上で計算しステップS505に進む(1M)。
ステップS505において、楕円曲線加算演算部116が、E←(X1+Y1)(X2−Y2)+B−Aをk上で計算する(1M)。
ステップS506において、楕円曲線加算演算部116が、F←C+D,G←C−D,H←A+aBをk上でそれぞれ計算する(1D)。
ステップS507において、楕円曲線加算演算部116が、X3←HGをk上で計算する(1M)。
ステップS508において、楕円曲線加算演算部116が、Y3←EFをk上で計算する(1M)。
ステップS509において、楕円曲線加算演算部116が、Z3←FGをk上で計算する(1M)
ステップS510において、楕円曲線加算演算部116が、演算結果をInverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とし、出力する。
図7に示す加算アルゴリズムの総演算コストは8M+D(Z1=1以外,S502→No)、7M+D(Z1=1,S502→Yes)となる。
【0074】
ここで、図7の処理の詳細について説明する。
非特許文献3に基づく加算公式によるとTwisted Edward型楕円曲線上の2点P=(x1,y1)、Q=(x2,y2)に対して係数dを用いない加算P+Q=(x3,y3)は以下の式(33)で計算することができる。
【0075】
【数20】

【0076】
この式(33)より、図5に示す加算アルゴリズムを導く。
2点P=(x1,y1)、Q=(x2,y2)と拡張Inverted twisted Edward座標を用いて表現したP=(X1:Y1:T1:Z1)、Q=(X2:Y2:T2:Z2)は以下の関係を満たす。
1= Z1/X1、y1=Z1/Y1、x11= Z1/T1、x2= Z2/X2、y2=Z2/Y2、x22= Z2/T2
これらの関係式を、式(33)に代入することによって、加算公式(式(33)を変形し、式(34)を得る。
【0077】
【数21】

【0078】
次に、以下の式(35)より式(36)が導かれる。
【0079】
【数22】

【0080】
この式(36)を式(34)に代入して、変形すると、以下の式(37)を得る。
【0081】
【数23】

【0082】
最終的にP+Qは以下の式(38)を計算することで求められる。
【0083】
【数24】

【0084】
式(38)より、x3=Z3/X3、y3=Z3/Y3、x33=Z3/T3 を満たすX3、Y3、T3、Z3をそれぞれ求めると、以下の式(39)〜(42)を得る。
【0085】
【数25】

【0086】
式(39)〜(42)を用いることでP+Q=(X1:Y1:T1:Z1)+(X2:Y2:T2:Z2)=(X3:Y3:T3:Z3)を計算することができる。
実際にx3=Z3/X3、y3=Z3/Y3、x33=Z3/T3を満たしていることは以下の式(43)〜(45)で確認できる。
【0087】
【数26】

【0088】
ここでT3は加算演算のみで用い2倍算では必要が無いこと、スカラ倍において加算の次に行われる演算は必ずT座標の必要の無い2倍算であることからT3を計算する必要は生じない。
上記の内容をアルゴリズムの形でまとめると、図7に示す処理手順となる。
【0089】
図8は、ステップS106において係数aが−1かつ係数dを用いない加算処理の手順を示すフローチャートである。
なお、入力時におけるPの座標は(X1:Y1:T1:Z1)、Qの座標は(X2:Y2:T2:Z2)であるとする。
ステップS601において、楕円曲線加算演算部116が、A←(X1−Y1)(X2+Y2)、B←(X1+Y1)(X2−Y2)、D←2T12をk上でそれぞれ計算する(3M)。この処理において、定義体k上の2倍算が含まれるが、より演算コストの小さい加算もしくは1ビットシフトなどの演算を用いることでコストの大きい乗算を用いないで計算できるため定数倍としては扱わない。
【0090】
ステップS602において、楕円曲線加算演算部116が、Z1=1であるか否かを判定し、Z1=1であれば(S602→Yes)、ステップS603の処理に進み、そうでなければ(S602→No)、ステップS604に進む。
ステップS603において、楕円曲線加算演算部116が、C←2T2をk上で計算しステップS605に進む。
ステップS604において、楕円曲線加算演算部116が、C←2T21をk上で計算しステップS605に進む(1M)。
ステップS605において、楕円曲線加算演算部116が、E←A+B、F←C+D,G←C−D,H←B−Aをk上でそれぞれ計算する。
ステップS606において、楕円曲線加算演算部116が、X3←EGをk上で計算する(1M)。
ステップS607において、楕円曲線加算演算部116が、Y3←HFをk上で計算する(1M)。
ステップS608において、楕円曲線加算演算部116が、Z3←FGをk上で計算する(1M)。
ステップS609において、楕円曲線加算演算部116が、演算結果をInverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とし、出力する。
図8に示す加算アルゴリズムの演算コストは7M(Z1=1以外)、6M(Z1=1)となる。
【0091】
ここで、図8に示す処理について詳細に説明する。
図7に示す加算方法を変形することにより、図8に示す加算アルゴリズムを導く。
図7における加算方法(式(39)〜(42)に対して、a=−1を代入することにより以下の式(46)〜(49)が得られる。
【0092】
【数27】

【0093】
【数28】

【0094】
式(46)〜(49)を用いることによりP+Q=(X1:Y1:T1:Z1)+(X2:Y2:T2:Z2)=(X3:Y3:T3:Z3)を計算することができ、(X3:Y3:T3:Z3)の代わりに(X4:Y4:T4:Z4)=(4X3:4Y3:4T3:4Z3)を用いてもx3=Z4/X4、y3=Z4/Y4、x33=Z4/T4を満たすことから、以下の式(50)〜(53)を用いることによりP+Q=(X1:Y1:T1:Z1)+(X2:Y2:T2:Z2)=(X3:Y3:T3:Z3)を計算できる。
【0095】
【数29】

【0096】
ここで、X3、Y3、Z3座標を求める際に必要となる式は以下の条件(式(54),(55))を満たす。
【0097】
【数30】

【0098】
関係式(50)〜(53)を用いて加算公式(式(33))をアルゴリズムの形で記載すると、図8に示す処理となる。
【0099】
ここで、例として161ビットの整数Lを用いた楕円曲線スカラ倍演算方法を説明する。
整数Lを161ビットとしその2進数展開をL=L0+L1×2+・・・+L159×2159 +L160×2160 (L160=1)であるとする。さらに、Li(0≦i≦159)のうち半分の80個が1であるとする。Inverted Twisted Edward座標を用いて表現した点P=(X:Y:Z)(Z≠1)のL倍のQ=LPを非特許文献2に開示されているInverted Twisted Edward座標を用いる2倍算および加算を組み合わせて計算する場合の演算コストは楕円曲線の定義体上の乗算、2乗算および定数倍算の演算コストをM、SおよびDとした場合、160×(3M+4S+2D)+80×(9M+1S+2D)=1200M+720S+480Dとなる。
【0100】
ここで、本実施形態における楕円曲線の係数dを用いてL倍を行う方法(図5)を用いると、80×(3M+4S+2D:図4)+80×(4M+4S+2D:図4)+80×(8M+2D:図5)=1200M+640S+480Dとなり、非特許文献2に記載の技術に比べて80Sの演算コストを削減できる。
【0101】
また、本実施形態における楕円曲線の係数aが−1かつ係数dを用いてL倍を行う方法(図6)を用いると、80×(3M+4S+D:図4)+80×(4M+4S+D:図4)+80×(7M+D:図6)=1120M+640S+240Dとなり、非特許文献2に記載の技術に比べて80M+80S+240Dの演算コストを削減できる。
【0102】
さらに、本実施形態における楕円曲線の係数dを用いないでL倍を行う方法(図7)を用いると、80×(3M+4S+2D:図4)+80×(4M+4S+2D:図4)+80×(8M+D:図7)=1200M+640S+400Dとなり、非特許文献2に記載の技術に比べて80S+80Dの演算コストを削減できる。
【0103】
また、本実施形態における楕円曲線の係数aが−1かつ係数dを用いないでL倍を行う方法(図8)を用いると、80×(3M+4S+D:図4)+80×(4M+4S+D:図4)+80×(7M:図8)=1120M+640S+160Dとなり、非特許文献2に記載の技術に比べて80M+80S+320Dの演算コストを削減できる。
【0104】
すなわち、本実施形態によれば、非特許文献2に記載の技術に比べてスカラ倍演算時の演算コストを削減できるためスカラ倍演算コストをより高速化することができる。これにより高速なECDSA署名など楕円曲線の性質を用いた署名方式や公開鍵暗号の実現が可能となる。
【0105】
《ECDSA鍵ペア生成》
次に、本実施形態に係る楕円曲線スカラ倍演算方法を利用したECDSA鍵ペア生成方法について図9および図10を参照して説明する。
【0106】
[ECDSA鍵ペア生成装置]
図9は、本実施形態に係るECDSA鍵ペア生成装置の構成例を示す図である。
ECDSA鍵ペア生成装置2は、制御演算部210および記憶部220を有している。
制御演算部210は、入出力部211、制御部212、楕円曲線スカラ倍演算部213、乱数生成部214を有している。入出力部211は、楕円曲線のパラメータ、定義体情報、スカラ倍における係数dの加算時使用の有無情報、ベースポイントGおよびその位数の入力を入力情報として受け付けるとともに、生成された鍵ペア223を出力情報として出力する機能を有している。制御部212は、ECDSA鍵ペア生成装置2を制御する機能を有している。楕円曲線スカラ倍演算部213は、ベースポイントの整数倍を計算する機能を有する。乱数生成部214は、乱数を生成する機能を有する。
【0107】
なお、楕円曲線スカラ倍演算部213は、図1に示す楕円曲線スカラ倍演算装置1を用いて構成することができる。この場合、定義体上の演算、剰余演算(mod)、比較などの基本演算は、図1に示す楕円曲線スカラ倍演算装置1内の入出力部111を通じて基本演算部118を呼び出すことにより行うことができる。
【0108】
記憶部220には、中間データ221、データ222、鍵ペア223などが格納されている。中間データ221は、制御演算部210における演算時の中間データである。データ222は、入出力部211により入力を受け付けた楕円曲線のパラメータ、ベースポイントおよびその位数、定義体情報、スカラ倍における係数dの加算時使用の有無情報などのデータである。鍵ペア223は、制御演算部210で生成された鍵ペアのデータである。
【0109】
なお、ECDSA鍵ペア生成装置2は、図16に示すような、バス57で接続されたCPU51と、RAMなどのメモリ52と、HDやその他の外部記憶装置55と、キーボードなどの入力装置53と、ディスプレイなどの出力装置54と、外部記憶装置55や、入力装置53や、出力装置54とのインタフェース56とを備えた、一般的な構成を有する情報処理装置5上に構築することができる。
ECDSA鍵ペア生成装置2の制御演算部210および各部211〜214は、CPU51が、メモリ52にロードされたプログラム(コードモジュールともいう)を実行することで、情報処理装置5上に具現化されるプロセスとして実現される。また、メモリ52や、外部記憶装置55が記憶部220として使用される。
【0110】
また、前記したプログラムは、予め外部記憶装置55に記憶され、必要に応じてメモリ52上にロードされ、CPU51により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばCD−ROMなどを介して、必要に応じて、可搬性の記憶媒体からメモリ52にロードされてもよい。また、プログラムは、一旦、CD−ROMなどの可搬性の記憶媒体からHDなどにインストールされた後、必要に応じて、このHDからメモリ52にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置5が伝送信号により、一旦HDにダウンロードされてからメモリ52にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ52にロードされてもよい。
【0111】
[ECDSA鍵ペア生成方法]
図10は、本実施形態に係るECDSA鍵ペア生成処理の手順を示すフローチャートである。
入出力部211により、ECDSA鍵ペア生成装置2が、入力情報として楕円曲線ax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、スカラ倍における係数dの加算時使用の有無情報、楕円曲線のベースポイントG=(XG:YG:TG:1)、ベースポイントの位数n(素数)などを受け付けると、これらの入力情報は記憶部220に格納される。なおベースポイントGはZ=1とした拡張Inverted twisted Edward座標で表されているものとする。
そして、制御演算部210が、入力情報として保持されているデータ222を用い、図10に示す鍵ペア生成処理を行って、鍵ペア223を生成する。
そして、制御演算部210で作成された鍵ペア223を、記憶部220に保持するとともに入出力部211より出力情報として出力し、動作を終了する。
【0112】
以下、図10を参照して、鍵ペア生成処理を説明する。
ステップS701において、乱数生成部214が、0<c<nを満たす整数cをランダムに生成し秘密鍵323(図11)とする。
ステップS702において、楕円曲線スカラ倍演算部213が、スカラ倍Q1←cG=(X:Y:Z)を用いて計算する。この計算は、図3〜図8に示す各処理を用いて行われる。
ステップS703において、楕円曲線スカラ倍演算部213が、Q←(XQ:YQ:TQ:1)=(X/Z:Y/Z:XY/Z2:1)をk上で計算することでQ1を拡張Inverted twisted Edward座標への変換し計算結果Qを公開鍵とする。
ステップS704において、制御演算部210が、鍵ペア223を(c,Q)とし、生成した鍵ペア223を出力するとともに、記憶部220に格納する。
【0113】
《ECDSA署名生成》
次に、本実施形態に係る楕円曲線スカラ倍演算方法を利用したECDSA署名生成方法について図11および図12を参照して説明する。
【0114】
[ECDSA署名生成装置]
図11は、本実施形態に係るECDSA署名生成装置の構成例を示す図である。
ECDSA署名生成装置3は、制御演算部310および記憶部320を有している。
制御演算部310は、入出力部311、制御部312、楕円曲線スカラ倍演算部313、乱数生成部314、ハッシュ関数演算部315を有している。入出力部311は、楕円曲線のパラメータ、定義体情報、スカラ倍における係数dの加算時使用の有無情報、ベースポイントGおよびその位数、署名者の秘密鍵323、署名対象の平文などの入力情報を受け付けるとともに、生成されたECDSA署名を出力情報として出力する機能を有する。制御部312は、ECDSA署名生成装置3を制御する機能を有する。楕円曲線スカラ倍演算部313は、ベースポイントのスカラ倍を計算する機能を有する。乱数生成部314は、乱数を生成する機能を有する。ハッシュ関数演算部315は、ハッシュ値を生成する機能を有する。
【0115】
なお、楕円曲線スカラ倍演算部313は、図1の楕円曲線スカラ倍演算装置1を用いて構成することができる。この場合、定義体上の演算、剰余演算(mod)、比較などの基本演算機能は、図1の楕円曲線スカラ倍演算装置1内の入出力部111を通じて基本演算部118を呼び出すことにより行うことができる。
【0116】
記憶部320には、中間データ321、データ322、秘密鍵323などが格納されている。中間データ321は、制御演算部310における演算時の中間データである。データ322は、入出力部311により入力を受け付けた楕円曲線のパラメータ、定義体情報、スカラ倍における係数dの加算時使用の有無情報、ベースポイントおよびその位数、署名対象の平文、生成されたECDSA署名などの各情報である。秘密鍵323は、入出力部311により入力を受け付けた署名者の秘密鍵である。
【0117】
なお、ECDSA署名生成装置3は、図16に示すような、バス57で接続されたCPU51と、RAMなどのメモリ52と、HDやその他の外部記憶装置55と、キーボードなどの入力装置53と、ディスプレイなどの出力装置54と、外部記憶装置55や、入力装置53や、出力装置54とのインタフェース56とを備えた、一般的な構成を有する情報処理装置5上に構築することができる。
ECDSA署名生成装置3の制御演算部310および各部311〜315は、CPU51が、メモリ52にロードされたプログラム(コードモジュールともいう)を実行することで、情報処理装置5上に具現化されるプロセスとして実現される。また、メモリ52や、外部記憶装置55が記憶部320として使用される。
【0118】
また、前記したプログラムは、予め外部記憶装置55に記憶され、必要に応じてメモリ52上にロードされ、CPU51により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばCD−ROMなどを介して、必要に応じて、可搬性の記憶媒体からメモリ52にロードされてもよい。また、プログラムは、一旦、CD−ROMなどの可搬性の記憶媒体からHDなどにインストールされた後、必要に応じて、このHDからメモリ52にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置5が読み取り可能な媒体の一種である伝送信号により、一旦HDにダウンロードされてからメモリ52にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ52にロードされてもよい。
【0119】
[ECDSA署名生成処理]
図12は、本実施形態に係るECDSA署名生成処理の手順を示すフローチャートである。
入出力部311により、ECDSA署名生成装置3が、入力情報として楕円曲線ax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、スカラ倍における係数dの加算時使用の有無情報、楕円曲線のベースポイントG=(XG:YG:TG:1)、ベースポイントの位数n(素数)、署名対象の平文Mなどを受け付けると、これらの入力情報は記憶部320に格納される。なおベースポイントGはZ=1とした拡張Inverted twisted Edward座標で表されているものとする。
また、入出力部311により、ECDSA署名生成装置3が、入力情報として署名者の秘密鍵323を受け付けると、この秘密鍵323は記憶部320に格納される。
そして、制御演算部310が、入力された入力情報を用いて、図12に示すECDSA署名生成処理を行い、ECDSA署名を生成する。
制御演算部310は、生成した署名データを記憶部320に保持するとともに入出力部311より出力情報として出力して、動作を終了する。
【0120】
以下、図12を参照して、ECDSA署名生成処理を説明する。
ステップS801において、乱数生成部314が、0<b<nを満たす整数bをランダムに生成する。
ステップS802において、楕円曲線スカラ倍演算部313が、R←bG=(X1:Y1:Z1)を計算する。この計算は、図3〜図8の処理を用いて行われる。
ステップS803において、楕円曲線スカラ倍演算部313が、x1←Z1/X1をk上で計算する。
ステップS804において、楕円曲線スカラ倍演算部313が、定義体k上の元x1を正の整数に変換したものをx1としておき直す。
ステップS805において、楕円曲線スカラ倍演算部313が、r←x1 mod n を計算する。
ステップS806において、ハッシュ関数演算部315が、ハッシュ関数hを用いてe←h(M)を計算する。
ステップS807において、楕円曲線スカラ倍演算部313が、s←b-1(e+cr) mod nを計算する。
ステップS808において、制御演算部310が、算出した(r,s)を署名データとし、生成した署名データを出力するとともに、記憶部320に格納する。
【0121】
《ECDSA署名検証》
次に、本実施形態に係る楕円曲線スカラ倍演算方法を利用したECDSA署名検証方法について図13〜図15を参照して説明する。
【0122】
[ECDSA署名検証装置]
図13は、本実施形態に係るECDSA署名検証装置の構成例を示す図である。
ECDSA署名検証装置4は、制御演算部410および記憶部420を有している。
制御演算部410は、入出力部411、制御部412、楕円曲線スカラ倍演算部413、ハッシュ関数演算部414を有している。入出力部411は、楕円曲線のパラメータ、定義体情報、スカラ倍における係数dの加算時使用の有無情報、ベースポイント、署名者の公開鍵、ベースポイントおよび公開鍵の位数、署名検証対象の平文、署名などを入力情報として受け付けるとともに、署名検証を出力情報として出力する機能を有する。制御部412は、ECDSA署名検証装置4を制御する機能を有する。楕円曲線スカラ倍演算部413は、ベースポイントおよび公開鍵のスカラ倍を計算する機能を有する。ハッシュ関数演算部414は、ハッシュ値を生成する機能を有する。
【0123】
楕円曲線スカラ倍演算部413は、図1の楕円曲線スカラ倍演算装置1を用いて構成することができる。この場合、定義体上の演算、剰余演算(mod)、比較などの基本演算機能は、図1の楕円曲線スカラ倍演算装置1内の入出力部111を通じて基本演算部118を呼び出すことにより行うことができる。
【0124】
記憶部420には、中間データ421およびデータ422などが格納されている。中間データ421は、制御演算部410における演算時の中間データである。データ422は、入出力部411により受け付けた楕円曲線のパラメータ、定義体情報、スカラ倍における係数dの加算時使用の有無情報、ベースポイント、署名者の公開鍵、ベースポイントおよび公開鍵の位数、署名検証対象の平文、署名などの入力情報、および署名検証結果などの出力情報などである。
【0125】
なお、ECDSA署名検証装置4は、図16に示すような、バス57で接続されたCPU51と、RAMなどのメモリ52と、HDやその他の外部記憶装置55と、キーボードなどの入力装置53と、ディスプレイなどの出力装置54と、外部記憶装置55や、入力装置53や、出力装置54とのインタフェース56とを備えた、一般的な構成を有する情報処理装置5上に構築することができる。
ECDSA署名検証装置4の制御演算部410および各部411〜414は、CPU51が、メモリ52にロードされたプログラム(コードモジュールともいう)を実行することで、情報処理装置5上に具現化される。また、メモリ52や、外部記憶装置55が記憶部420として使用される。
【0126】
また、前記したプログラムは、予め外部記憶装置55に記憶され、必要に応じてメモリ52上にロードされ、CPU51により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばCD−ROMなどを介して、必要に応じて、可搬性の記憶媒体からメモリ52にロードされてもよい。また、一旦、CD−ROMなどの可搬性の記憶媒体からHDなどにインストールされた後、必要に応じて、このHDからメモリ52にロードされてもよい。さらに、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置5が伝送信号により、一旦HDにダウンロードされてからメモリ52にロードされてもよい。あるいは、直接、ネットワーク経由でメモリ52にロードされてもよい。
【0127】
[ECDSA署名検証処理]
図14および図15は、本実施形態に係るECDSA署名検証処理の手順を示すフローチャートである。
処理の概略を記述すると、入出力部411により、ECDSA署名検証装置4が、入力情報として、楕円曲線ax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、スカラ倍における係数dの加算時使用の有無情報、楕円曲線のベースポイントG=(XG:YG:TG:1)、公開鍵Q=(XQ:YQ:TQ:1)、ベースポイントおよび公開鍵の位数n(素数)、平文Mとその署名(r,s)を入力情報として受け付けると、制御演算部410は受け付けた入力情報を記憶部420に格納する。
そして、制御演算部410が、記憶部420に保持されている入力情報を用いて、図14および図15の処理に従ってECDSA署名検証処理を行う。
制御演算部410は、生成された署名検証結果を、記憶部420に保持するとともに、入出力部411より出力情報として出力し、動作を終了する。
【0128】
まず、図14の処理から説明する。
ステップS901において、ハッシュ関数演算部414が、署名生成時と同じハッシュ関数hを用いてe←h(M)を計算する。
ステップS902において、楕円曲線スカラ倍演算部413が、e1← s-1e mod nを計算する。
ステップS903において、楕円曲線スカラ倍演算部413が、r1← s-1r mod nを計算する。
ステップS904において、楕円曲線スカラ倍演算部413が、G1←(XG1:YG1:ZG1)=e1Gを計算する。この計算は、図3〜図8に示す各処理を用いて行われる。
ステップS905において、楕円曲線スカラ倍演算部413が、Q1←(XQ1:YQ1:ZQ1)=r1Qを計算する。この計算は、図3〜図8に示す各処理を用いて行われる。
ステップS906において、楕円曲線スカラ倍演算部413が、(X1:Y1:Z1)=G1+Q1のうちX1、Z1を図15で後記するフローチャートに従って計算する。
ステップS907において、楕円曲線スカラ倍演算部413が、x1←Z1/X1をk上で計算する。
ステップS908において、楕円曲線スカラ倍演算部413が、署名生成時の処理(図12)と同じ変換方法でk上の元x1を正の整数に変換したものをx1としておき直す。
ステップS909において、制御演算部410が、、x1 mod n=rが成立するか否か検証を行い、成立すれば検証結果をTrue、しなければ検証結果をFalseとして出力するとともに、この検証結果を記憶部420に格納する。
【0129】
図15は、ステップS906の詳細な処理手順を示すフローチャートである。
ステップS1001において、楕円曲線スカラ倍演算部413が、A←ZG1Q1、B←dA2、C←XG1Q1、D←YG1Q1、E←CDをk上でそれぞれ計算する。
ステップS1002において、楕円曲線スカラ倍演算部413が、H←C−aD、I←(XG1+YG1)(XQ1+YQ1)−C−Dをk上でそれぞれ計算する。
ステップS1003において、楕円曲線スカラ倍演算部413が、X1←(E+B)Hをk上で計算する。
ステップS1004において、楕円曲線スカラ倍演算部413が、Z1←AHIをk上で計算する。
【0130】
[ハードウェア構成]
図16は、情報処理装置のハードウェア構成例を示す図である。
この情報処理装置5は、楕円曲線スカラ倍演算装置1、ECDSA鍵ペア生成装置2、ECDSA署名生成装置3、ECDSA署名検証装置4に相当する装置である。
情報処理装置5では、CPU51およびメモリ52がバス57を介して互いに接続されている。また、キーボードや、マウスに相当する入力装置53、ディスプレイに相当する出力装置54、HDや、CD−ROMなどに相当し、プログラムや、データが格納されている外部記憶装置55がインタフェース56を介してバス57に接続している。
【0131】
《まとめ》
本実施形態では、楕円曲線ax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)上の点(x,y)に対してx=Z/X、y=Z/Y、XYZ≠0を満たすX、Y、Z∈kを用いて(X:Y:Z)と変換したInverted Twisted Edward座標に加えて、x=Z/X、y=Z/Y、xy=Z/T、XYTZ≠0を満たすX、Y、T、Z∈kを用いて(X:Y:T:Z)と変換した拡張Inverted Twisted Edward座標を導入する。
Inverted Twisted Edward座標を用いて表現した点(X:Y:Z)から拡張Inverted Twisted Edward座標を用いて表現した点への変換は(XZ:YZ:XY:Z2)で変換でき、拡張Inverted Twisted Edward座標を用いて表現した点(X:Y:T:Z)からInverted Twisted Edward座標を用いて表現した点への変換は(X:Y:Z)とTを無視することで変換することができる。
【0132】
拡張Inverted Twisted Edward座標を加算の際に用いることで定義体上の2乗算1回を削減できる。
スカラ倍における2倍算は出力結果に拡張Inverted Twisted Edward座標を用いた場合、T座標を求める際に乗算が1回増えるため2倍算の後に加算を行う必要がある場合のみT座標の計算を行う。なお加算の後には必ずT座標を用いることの無い2倍算が計算されるため加算時においてT座標を計算するために必要な乗算1回の削減が行われるため2倍算時に増加した乗算は次に行われる加算時に乗算を1回削減できるため相殺される。
さらに非特許文献3において開示されている楕円曲線の係数dを用いない加算方法に対して拡張Inverted Twisted Edward座標を用いることでさらに加算1回あたり定数倍を1回削減する。
また、それぞれの加算においてa=−1の場合、それに特化したアルゴリズムを用いることにより加算1回あたりさらに乗算と定数倍算それぞれ1回を削減する。
スカラ倍演算の際の加算時に係数dを用いるか否かはスカラ倍演算に必要な情報を設定する際に指定できるものとする。
【符号の説明】
【0133】
1 楕円曲線スカラ倍演算装置
2 ECDSA鍵ペア生成装置
3 ECDSA署名生成装置
4 ECDSA署名検証装置
5 情報処理装置
110 制御演算部(楕円曲線スカラ倍演算装置)
113 楕円曲線スカラ倍演算部(楕円曲線スカラ倍演算装置)
115 2進数展開部
116 楕円曲線加算演算部
117 楕円曲線2倍算演算部
118 基本演算部
120 記憶部(楕円曲線スカラ倍演算装置)
210 制御演算部(ECDSA鍵ペア生成装置)
213 楕円曲線スカラ倍演算部(ECDSA鍵ペア生成装置)
214 乱数生成部(ECDSA鍵ペア生成装置)
220 記憶部(ECDSA鍵ペア生成装置)
223 鍵ペア
310 制御演算部(ECDSA署名生成装置)
313 楕円曲線スカラ倍演算部(ECDSA署名生成装置)
314 乱数生成部(ECDSA署名生成装置)
315 ハッシュ関数演算部(ECDSA署名生成装置置)
320 記憶部(ECDSA署名生成装置置)
323 秘密鍵
410 制御演算部(ECDSA署名検証装置)
413 楕円曲線スカラ倍演算部(ECDSA署名検証装置)
414 ハッシュ関数演算部(ECDSA署名検証装置)
420 記憶部(ECDSA署名検証装置)



【特許請求の範囲】
【請求項1】
Inverted twisted Edward座標を拡張した拡張Inverted twisted Edward座標を用いて表現した素数位数の点である第1の点を整数倍して、Inverted twisted Edward座標を用いて表現した第2の点を算出する楕円曲線スカラ倍演算装置による楕円曲線スカラ倍演算方法であって、
入力部を介して、前記第1の点および任意の整数が入力されると、
楕円曲線スカラ倍演算装置が、
前記整数を2進数展開し、前記展開した2進数の係数ごとに、(a)および(b)の処理を行うことを特徴とする楕円曲線スカラ倍演算方法。
(a)前記第1の点を、Inverted twisted Edward座標を用いて表現した点に置換した上で、前記変換した第1の点の2倍算を行い、前記2倍算の結果を拡張Inverted twisted Edward座標を用いて表現した素数位数の点である第3の点に変換し、
(b)前記係数が1である場合、前記第1の点と、前記第3の点の加算処理を行う。
【請求項2】
Twisted Edward型楕円曲線上の任意の点Pのスカラ倍演算(Q=LP)を行なう楕円スカラ倍演算装置による楕円曲線スカラ倍演算方法であって、
前記楕円スカラ倍演算装置が、
入力部を介して、
標数が2と異なる有限体kを定義体とするTwisted Edward型楕円曲線ax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)に関する情報、楕円曲線上の点(x1,y1)において、x1=Z1/X1、y1=Z1/Y1、x11=Z1/T1、X1111≠0を満たすX1,Y1,T1,Z1∈kを用いて表現する拡張Inverted twisted Edward座標における素数位数の点P=(X1:Y1:T1:Z1)、整数L(L>0)、および楕円曲線の2点の加算を行う際に係数dを用いるか否かの入力情報が入力されると、
(a1)前記整数Lを2進数展開して、L=L0+L1×2+・・・+Lt-1×2t-1(Lt-1=1)とし、
(a2)d1←2d、i←t−2、Q←Pとおき、
(a3)前記i=−1であるか否かを判定し、i=−1であれば(a9)の処理へ進み、i=−1でなければ(a4)の処理へ進み、
(a4)Q←2Qを計算し、
(a5)前記Li=1であるか否かを判定し、Li=1であれば、(a6)の処理へ進み、Li=1でなければ、(a7)の処理へ進み、
(a6)Q←Q+Pを計算し、
(a7)i←i−1を計算し、
(a8)i≧0であるか否かを判定し、i≧0であれば、前記(a4)の処理へ戻り、i≧0でなければ(a9)の処理へ進み、
(a9)Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)を計算結果とする
ことを特徴とする楕円曲線スカラ倍演算方法。
【請求項3】
前記楕円曲線スカラ倍演算装置が、
前記(a4)の処理において、
(b1)Q=(X2:Y2:T2:Z2)であれば、QをQ←(X2:Y2:Z2)におき直し、
(b2)A←X22、B←Y22、U←aBをそれぞれk上で計算し、
(b3)C←A+U、D←A−U、E←(X2+Y22−A−B、H←(C−d122)をそれぞれk上で計算し、
(b4)X3←CDをk上で計算し、
(b5)Y3←EHをk上で計算し、
(b6)Li=1であれば、T3←CHをk上で計算し、
(b7)Z3←DEをk上で計算し、
(b8)前記(b6)の処理において、T3←CHを計算している場合、2倍算の演算結果を前記拡張Inverted twisted Edward座標を用いてQ←(X3:Y3:T3:Z3)とおき、前記(b6)の処理において、T3←CHを計算していない場合、前記Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項2に記載の楕円曲線スカラ倍演算方法。
【請求項4】
前記楕円曲線の2点の加算を行う際に前記係数dを用いる旨の情報が、前記入力部を介して入力されると、
前記楕円曲線スカラ倍演算装置が、
前記(a6)の処理において、
(c1)A←X12、B←Y12、D←T12をk上でそれぞれ計算し、
(c2)Z1=1であるか否かを判定し、Z1=1であれば、(c3)の処理へ進み、Z1=1でなければ、(c4)の処理へ進み、
(c3)C←dZ2をk上で計算し、(c5)の処理へ進み、
(c4)C←dZ12をk上で計算し、(c5)の処理へ進み、
(c5)E←(X1+Y1)(X2+Y2)−A−Bをk上で計算し、
(c6)F←D−C,G←D+C,H←A−aBをk上でそれぞれ計算し、
(c7)X3←HGをk上で計算し、
(c8)Y3←EFをk上で計算し、
(c9)Z3←HEをk上で計算し、
(c10)演算結果を前記Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項2に記載の楕円曲線スカラ倍演算方法。
【請求項5】
前記aの値が−1かつ前記楕円曲線の2点の加算を行う際に前記係数dを用いる旨の情報が、前記入力部を介して入力されると、
前記楕円曲線スカラ倍演算装置が、
前記(a6)の処理において、
(d1)A←(X1+Y1)(X2+Y2)、B←(X1−Y1)(X2−Y2)、D=2T12 をk上でそれぞれ計算し、
(d2)Z1=1であるか否かを判定し、Z1=1であれば、(d3)の処理へ進み、Z1=1でなければ、(d4)の処理へ進み、
(d3)C←d12をk上で計算し、(d5)の処理へ進み、
(d4)C←d112をk上で計算し、、(d5)の処理へ進み、
(d5)E=A−B、F=D−C、G=D+C、H=A+Bをそれぞれk上で計算し、
(d6)X3=HGをk上で計算し、
(d7)Y3=EFをk上で計算し、
(d8)Z3=HEをk上で計算し、
(d9)演算結果を前記Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項2に記載の楕円曲線スカラ倍演算方法。
【請求項6】
前記楕円曲線の2点の加算を行う際に前記係数dを用いない旨の情報が、前記入力部を介して入力されると、
前記楕円曲線スカラ倍演算装置が、
前記(a6)の処理において、
(e1)A←X12、B←Y12、D←T12をk上でそれぞれ計算し、
(e2)Z1=1であるか否かを判定し、Z1=1であれば、(e3)の処理へ進み、Z1=1でなければ、(e4)の処理へ進み、
(e3)C←T2とおき、(e5)の処理へ進み、
(e4)C←Z12をk上で計算し、(e5)の処理へ進み、
(e5)E←(X1+Y1)(X2−Y2)+B−Aをk上で計算し、
(e6)F←C+D,G←C−D,H←A+aBをk上でそれぞれ計算し、
(e7)X3←HGをk上で計算し、
(e8)Y3←EFをk上で計算し、
(e9)Z3←FGをk上で計算し、
(e10)演算結果を前記Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項2に記載の楕円曲線スカラ倍演算方法。
【請求項7】
前記aの値が−1かつ前記楕円曲線の2点の加算を行う際にdを用いない旨の情報が、前記入力部を介して入力されると、
前記楕円曲線スカラ倍演算装置が、
前記(a6)の処理において、
(f1)A←(X1−Y1)(X2+Y2)、B←(X1+Y1)(X2−Y2)、D←2T12をk上でそれぞれ計算し、
(f2)Z1=1であるか否かを判定し、Z1=1であれば、(f3)の処理へ進み、Z1=1でなければ、(f4)の処理へ進み、
(f3)C←2T2とおき、(f5)の処理へ進み、
(f4)C←2Z12をk上で計算し、(f5)の処理へ進み、
(f5)E←A+B、F←C+D,G←C−D,H←B−Aをk上でそれぞれ計算し、
(f6)X3←EGをk上で計算し、
(f7)Y3←HFをk上で計算し、
(f8)Z3←FGをk上で計算し、
(f9)演算結果をInverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項2に記載の楕円曲線スカラ倍演算方法。
【請求項8】
ECDSA署名を利用したECDSA鍵ペア生成装置によるECDSA鍵ペア生成方法であって、
入力部を介して、楕円曲線のパラメータax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、ベースポイントG=(XG:YG:TG:1)およびその位数n、楕円曲線の2点の加算を行う際に前記係数dを用いるか否かの入力情報が入力されると、
前記ECDSA鍵ペア生成装置が、
(g1)0<c<nを満たす整数cをランダムに生成し秘密鍵とし、
(g2)請求項1から請求項7のいずれか一項に記載の楕円曲線スカラ倍演算方法を行うことによって、Q1=cG=(X:Y:Z)を計算し、
(g3)Q←(XQ:YQ:TQ:1)=(X/Z:Y/Z:XY/Z2:1)をk上で計算することでQ1を拡張Inverted twisted Edward座標への変換し計算結果Qを公開鍵とし、
(g4)鍵ペアを(c、Q)とする
ことを特徴とするECDSA鍵ペア生成方法。
【請求項9】
ECDSA署名を利用したECDSA署名生成装置によるECDSA署名生成方法であって、
入力部を介して、楕円曲線のパラメータax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、ベースポイントG=(XG:YG:TG:1)およびその位数n、楕円曲線の2点の加算を行う際に前記係数dを用いるか否かの情報、秘密鍵c、署名対象の平文Mの入力情報が入力されると、
前記ECDSA署名生成装置が、
(h1)0<b<nを満たす整数bをランダムに生成し、
(h2)請求項1から請求項7のいずれか一項に記載の楕円曲線スカラ倍演算方法を行って、R←bG=(X1:Y1:Z1)を計算し、
(h3)x1←Z1/X1をk上で計算し、
(h4)k上の元x1を正の整数に変換したものをx1としておき直し、
(h5)r←x1 mod n を計算し、
(h6)ハッシュ関数hを用いて、e←h(M)を計算し、
(h7)s←b-1(e+cr) mod nを計算し、
(h8)(r,s)をECDSA署名とする
ことを特徴とするECDSA署名生成方法。
【請求項10】
請求項9に記載のECDSA署名生成方法によって生成されたECDSA署名を利用したECDSA署名検証装置によるECDSA署名検証方法であって、
入力部を介して、楕円曲線のパラメータax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、ベースポイントG=(XG:YG:TG:1)およびその位数n、楕円曲線の2点の加算を行う際に前記係数dを用いるか否かの情報、公開鍵Q=(XQ:YQ:TQ:1)、前記ECDSA署名(r,s)、署名検証対象の平文Mが入力情報として入力されると、
前記ECDSA署名検証装置が、
(i1)署名生成時と同じハッシュ関数hを用いて、e←h(M)を計算し、
(i2)e1← s-1e mod nを計算し、
(i3)r1← s-1r mod nを計算し、
(i4)請求項1から請求項7のいずれか一項に記載の楕円曲線スカラ倍演算方法を行って、G1←(XG1:YG1:ZG1)=e1Gを計算し、
(i5)請求項1から請求項7のいずれか一項に記載の楕円曲線スカラ倍演算方法を行って、Q1←(XQ1:YQ1:ZQ1)=r1Qを計算し、
(i6)(X1:Y1:Z1)=G1+Q1のうちX1、Z1を計算し、
(i7)x1←Z1/X1をk上で計算し、
(i8)定義体k上の元x1を正の整数に変換したものをx1としておき直し、
(i9)x1 mod n = rが成立するか否かの検証を行い、成立すれば検証結果をTrue、しなければ検証結果をFalseとする
ことを特徴とするECDSA署名検証方法。
【請求項11】
前記ECDSA署名検証装置が、
前記(i6)の処理において、
(j1)A←ZG1Q1、B←dA2、C←XG1Q1、D←YG1Q1、E←CDをk上でそれぞれ計算し、
(j2)H←C−aD、I←(XG1+YG1)(XQ1+YQ1)−C−Dをk上でそれぞれ計算し、
(j3)X1←(E+B)Hをk上で計算し、
(j4)Z1←AHIをk上で計算する
ことを特徴とする請求項10に記載のECDSA署名検証方法。
【請求項12】
請求項1から請求項7のいずれか一項に記載の楕円曲線スカラ倍演算方法、請求項8に記載のECDSA鍵ペア生成方法、請求項9に記載のECDSA署名生成方法、請求項10または請求項11に記載のECDSA署名検証方法のうちいずれか1つをコンピュータに実行させることを特徴とするプログラム。
【請求項13】
Inverted twisted Edward座標を拡張した拡張Inverted twisted Edward座標を用いて表現した素数位数の点である第1の点を整数倍して、Inverted twisted Edward座標を用いて表現した第2の点を算出する楕円曲線スカラ倍演算装置であって、
入力部を介して、前記第1の点および任意の整数が入力されると、
前記整数を2進数展開し、前記2進数の係数ごとに、(a)および(b)の処理を行うことを特徴とする楕円曲線スカラ倍演算装置。
(a)前記第1の点を、Inverted twisted Edward座標を用いて表現した点に置換した上で、前記変換した第1の点の2倍算を行い、前記2倍算の結果を拡張Inverted twisted Edward座標を用いて表現した素数位数の点である第3の点に変換し、
(b)前記係数が1である場合、前記第1の点と、前記第3の点の加算処理を行う。
【請求項14】
Twisted Edward型楕円曲線上の任意の点Pのスカラ倍演算(Q=LP)を行なう楕円曲線スカラ倍演算装置であって、
2進数展開部と、楕円曲線加算演算部と、楕円曲線2倍算演算部と、基本演算部とを有し、
入力部を介して、
標数が2と異なる有限体kを定義体とするTwisted Edward型楕円曲線ax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)に関する情報、楕円曲線上の点(x1,y1)において、x1=Z1/X1、y1=Z1/Y1、x11=Z1/T1、X1111≠0を満たすX1,Y1,T1,Z1∈kを用いて表現する拡張Inverted twisted Edward座標における素数位数の点P=(X1:Y1:T1:Z1)、整数L(L>0)、および楕円曲線の2点の加算を行う際に係数dを用いるか否かの入力情報が入力されると、
前記2進数展開部が、
前記整数Lを2進数展開して、L=L0+L1×2+・・・+Lt-1×2t-1(Lt-1=1)とし、
前記基本演算部が、
(a2)d1←2d、i←t−2、Q←Pとおき、
(a3)前記i=−1であるか否かを判定し、i=−1であれば(a9)の処理へ進み、i=−1でなければ(a4)の処理へ進み、
前記楕円曲線2倍算加算演算部が、
(a4)Q←2Qを計算し、
前記基本演算部が、
(a5)前記Li=1であるか否かを判定し、Li=1であれば、(a6)の処理へ進み、Li=1でなければ、(a7)の処理へ進み、
前記楕円曲線加算演算部が、
(a6)Q←Q+Pを計算し、
前記基本演算部が、
(a7)i←i−1を計算し、
(a8)i≧0であるか否かを判定し、i≧0であれば、前記(a4)の処理へ戻り、i≧0でなければ(a9)の処理へ進み、
(a9)Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)を計算結果とする
ことを特徴とする楕円曲線スカラ倍演算装置。
【請求項15】
前記楕円曲線2倍算加算演算部は、
(b1)Q=(X2:Y2:T2:Z2)であれば、QをQ←(X2:Y2:Z2)におき直し、
(b2)A←X22、B←Y22、U←aBをそれぞれk上で計算し、
(b3)C←A+U、D←A−U、E←(X2+Y22−A−B、H←(C−d122)をそれぞれk上で計算し、
(b4)X3←CDをk上で計算し、
(b5)Y3←EHをk上で計算し、
(b6)Li=1であれば、T3←CHをk上で計算し、
(b7)Z3←DEをk上で計算し、
(b8)前記(b6)の処理において、T3←CHを計算している場合、2倍算の演算結果を前記拡張Inverted twisted Edward座標を用いてQ←(X3:Y3:T3:Z3)とおき、前記(b6)の処理において、T3←CHを計算していない場合、前記Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項14に記載の楕円曲線スカラ倍演算装置。
【請求項16】
前記楕円曲線の2点の加算を行う際に前記係数dを用いる旨の情報が、前記入力部を介して入力されると、
前記楕円曲線加算演算部は、
(c1)A←X12、B←Y12、D←T12をk上でそれぞれ計算し、
(c2)Z1=1であるか否かを判定し、Z1=1であれば、(c3)の処理へ進み、Z1=1でなければ、(c4)の処理へ進み、
(c3)C←dZ2をk上で計算し、(c5)の処理へ進み、
(c4)C←dZ12をk上で計算し、(c5)の処理へ進み、
(c5)E←(X1+Y1)(X2+Y2)−A−Bをk上で計算し、
(c6)F←D−C,G←D+C,H←A−aBをk上でそれぞれ計算し、
(c7)X3←HGをk上で計算し、
(c8)Y3←EFをk上で計算し、
(c9)Z3←HEをk上で計算し、
(c10)演算結果を前記Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項14に記載の楕円曲線スカラ倍演算装置。
【請求項17】
前記aの値が−1かつ前記楕円曲線の2点の加算を行う際に前記係数dを用いる旨の情報が、前記入力部を介して入力されると、
前記楕円曲線加算演算部は、
(d1)A←(X1+Y1)(X2+Y2)、B←(X1−Y1)(X2−Y2)、D=2T12 をk上でそれぞれ計算し、
(d2)Z1=1であるか否かを判定し、Z1=1であれば、(d3)の処理へ進み、Z1=1でなければ、(d4)の処理へ進み、
(d3)C←d12をk上で計算し、(d5)の処理へ進み、
(d4)C←d112をk上で計算し、、(d5)の処理へ進み、
(d5)E=A−B、F=D−C、G=D+C、H=A+Bをそれぞれk上で計算し、
(d6)X3=HGをk上で計算し、
(d7)Y3=EFをk上で計算し、
(d8)Z3=HEをk上で計算し、
(d9)演算結果を前記Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項14に記載の楕円曲線スカラ倍演算装置。
【請求項18】
前記楕円曲線の2点の加算を行う際に前記係数dを用いない旨の情報が、前記入力部を介して入力されると、
前記楕円曲線加算演算部は、
(e1)A←X12、B←Y12、D←T12をk上でそれぞれ計算し、
(e2)Z1=1であるか否かを判定し、Z1=1であれば、(e3)の処理へ進み、Z1=1でなければ、(e4)の処理へ進み、
(e3)C←T2とおき、(e5)の処理へ進み、
(e4)C←Z12をk上で計算し、(e5)の処理へ進み、
(e5)E←(X1+Y1)(X2−Y2)+B−Aをk上で計算し、
(e6)F←C+D,G←C−D,H←A+aBをk上でそれぞれ計算し、
(e7)X3←HGをk上で計算し、
(e8)Y3←EFをk上で計算し、
(e9)Z3←FGをk上で計算し、
(e10)演算結果を前記Inverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項14に記載の楕円曲線スカラ倍演算装置。
【請求項19】
前記aの値が−1かつ前記楕円曲線の2点の加算を行う際に前記係数dを用いない旨の情報が、前記入力部を介して入力されると、
前記楕円曲線加算演算部は、
(f1)A←(X1−Y1)(X2+Y2)、B←(X1+Y1)(X2−Y2)、D←2T12をk上でそれぞれ計算し、
(f2)Z1=1であるか否かを判定し、Z1=1であれば、(f3)の処理へ進み、Z1=1でなければ、(f4)の処理へ進み、
(f3)C←2T2とおき、(f5)の処理へ進み、
(f4)C←2Z12をk上で計算し、(f5)の処理へ進み、
(f5)E←A+B、F←C+D,G←C−D,H←B−Aをk上でそれぞれ計算し、
(f6)X3←EGをk上で計算し、
(f7)Y3←HFをk上で計算し、
(f8)Z3←FGをk上で計算し、
(f9)演算結果をInverted twisted Edward座標を用いてQ←(X3:Y3:Z3)とおく
ことを特徴とする請求項14に記載の楕円曲線スカラ倍演算装置。
【請求項20】
ECDSA署名を利用したECDSA鍵ペア生成装置であって、
乱数生成部と、請求項13から請求項19のいずれか一項に記載の楕円曲線スカラ倍演算装置である楕円曲線スカラ倍演算部と、制御演算部と、を有し、
入力部を介して、楕円曲線のパラメータax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、ベースポイントG=(XG:YG:TG:1)およびその位数n、楕円曲線の2点の加算を行う際に係数dを用いるか否かの入力情報が入力されると、
前記乱数生成部は、
(g1)0<c<nを満たす整数cをランダムに生成し秘密鍵とし、
前記楕円曲線スカラ倍演算部は、
(g2)Q1=cG=(X:Y:Z)を計算し、
(g3)Q←(XQ:YQ:TQ:1)=(X/Z:Y/Z:XY/Z2:1)をk上で計算することでQ1を前記拡張Inverted twisted Edward座標への変換し計算結果Qを公開鍵とし、
前記制御演算部が、
(g4)鍵ペアを(c、Q)とする
ことを特徴とするECDSA鍵ペア生成装置。
【請求項21】
ECDSA署名を利用したECDSA署名生成装置であって、
乱数生成部と、ハッシュ関数演算部と、請求項13から請求項19のいずれか一項に記載の楕円曲線スカラ倍演算装置である楕円曲線スカラ倍演算部と、制御演算部と、を有し、
入力部を介して、楕円曲線のパラメータax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、ベースポイントG=(XG:YG:TG:1)およびその位数n、楕円曲線の2点の加算を行う際に係数dを用いるか否か、秘密鍵c、署名対象の平文Mの入力情報が入力されると、
前記乱数生成部は、
(h1)0<b<nを満たす整数bをランダムに生成し、
前記楕円曲線スカラ倍演算部は、
(h2)R←bG=(X1:Y1:Z1)を計算し、
(h3)x1←Z1/X1をk上で計算し、
(h4)k上の元x1を正の整数に変換したものをx1としておき直し、
(h5)r←x1 mod n を計算し、
ハッシュ関数演算部は、
(h6)ハッシュ関数hを用いて、e←h(M)を計算し、
前記楕円曲線スカラ倍演算部は、
(h7)s←b-1(e+cr) mod nを計算し、
前記制御演算部は、
(h8)(r,s)をECDSA署名とする
ことを特徴とするECDSA署名生成装置。
【請求項22】
請求項21に記載のECDSA署名生成装置によって生成されたECDSA署名を利用するECDSA署名検証装置であって、
ハッシュ関数演算部と、請求項13から請求項19のいずれか一項に記載の楕円曲線スカラ倍演算装置である楕円曲線スカラ倍演算部と、制御演算部と、を有し、
入力部を介して、楕円曲線のパラメータax2+y2=1+dx22(k上で係数aは2乗根を持ち係数dは持たない)、定義体k、ベースポイントG=(XG:YG:TG:1)およびその位数n、楕円曲線の2点の加算を行う際に係数dを用いるか否か、公開鍵Q=(XQ:YQ:TQ:1)、前記ECDSA署名(r,s)、署名検証対象の平文Mが入力情報として入力されると、
ハッシュ関数演算部は、
(i1)書名生成時と同じハッシュ関数hを用いて、e←h(M)を計算し、
前記楕円曲線スカラ倍演算部は、
(i2)e1← s-1e mod nを計算し、
(i3)r1← s-1r mod nを計算し、
(i4)G1←(XG1:YG1:ZG1)=e1Gを計算し、
(i5)Q1←(XQ1:YQ1:ZQ1)=r1Qを計算し、
(i6)(X1:Y1:Z1)=G1+Q1のうちX1、Z1を計算し、
(i7)x1←Z1/X1をk上で計算し、
(i8)定義体k上の元x1を正の整数に変換したものをx1としておき直し、
前記制御演算部が、
(i9)x1 mod n = rが成立するか否かの検証を行い、成立すれば検証結果をTrue、しなければ検証結果をFalseとする
ことを特徴とするECDSA署名検証装置。
【請求項23】
前記楕円曲線スカラ倍演算部は、
(j1)A←ZG1Q1、B←dA2、C←XG1Q1、D←YG1Q1、E←CDをk上でそれぞれ計算し、
(j2)H←C−aD、I←(XG1+YG1)(XQ1+YQ1)−C−Dをk上でそれぞれ計算し、
(j3)X1←(E+B)Hをk上で計算し、
(j4)Z1←AHIをk上で計算する
ことによって、前記X1、Z1を計算する
ことを特徴とする請求項22に記載のECDSA署名検証装置。



【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate


【公開番号】特開2010−266765(P2010−266765A)
【公開日】平成22年11月25日(2010.11.25)
【国際特許分類】
【出願番号】特願2009−119256(P2009−119256)
【出願日】平成21年5月15日(2009.5.15)
【出願人】(000005108)株式会社日立製作所 (27,607)
【Fターム(参考)】