(57)【要約】【課題】サイドチャネル攻撃に対する耐性を持ち、かつスカラー倍算を高速化する。【課題】図１のステップＳ３の楕円加算・２倍算ＥＣＡＤＤＤＢＬでは、Ｑ［ｄ［ｉ］］とＱ［ｄ［ｉ］＋１］の楕円加算の演算結果がＱ［ｄ［ｉ］＋１］に設定され、Ｑ［ｄ［ｉ］］の楕円２倍算の演算結果がＱ［ｄ［ｉ］］に設定される。そして、ｉ＝ｎ−２から０まで変化させステップＳ３の処理を繰り返し、最終的な演算結果のＱ［０］をｄ×Ｐの点の座標として求める。【選択図】　　　図１
2004053814.tif 000002
【特許請求の範囲】
【請求項１】
整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、
変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、楕円加算と楕円２倍算を１つの演算として定義し、かつ同じ種類の演算を並列に実行する演算手段とを備える楕円曲線暗号装置。
【請求項２】
整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、
（１）変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
（２）前記整数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）＝ＥＣＡＤＤＤＢＬ（（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）としたときに、
前記（２）の演算を所定数回繰り返してｄ×Ｐを求める際に、前記ＥＣＡＤＤＤＢＬの同じ種類の演算を並列に実行する演算手段とを備える楕円曲線暗号装置。
【請求項３】
整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、
（１）変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
（２）前記整数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）＝ＥＣＡＤＤＤＢＬ（（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）としたときに、
前記ＥＣＡＤＤＤＢＬは、Ｑ［ｄ［ｉ］］とＱ［ｄ［ｉ］＋１］の楕円加算Ｑ［ｄ［ｉ］］＋Ｑ［ｄ［ｉ］＋１］の結果をＱ［ｄ［ｉ］＋１］として設定し、Ｑ［ｄ［ｉ］］の楕円２倍算２×Ｑ［ｄ［ｉ］］の結果をＱ［ｄ［ｉ］］として設定する演算であり、
前記（２）の演算を所定数回繰り返してｄ×Ｐを求める際に、前記ＥＣＡＤＤＤＢＬの同じ種類の演算を並列に実行する演算手段とを備える楕円曲線暗号装置。
【請求項４】
請求項１、２または３記載の楕円曲線暗号装置において、
前記演算手段は、点Ｐのｙ座標を使用せずにスカラー倍算ｄ×Ｐの演算を実行する。
【請求項５】
整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号演算方法において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得し、
変数Ｑ［０］の初期値として点Ｐの座標を設定し、
変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
楕円加算と楕円２倍算を１つの演算として定義し、かつ同じ種類の演算を並列に実行する楕円曲線暗号演算方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線暗号装置、楕円曲線暗号演算方法及び楕円曲線暗号プログラムに関する。
【０００２】
【従来の技術】
楕円曲線暗号は公開鍵暗号の１つであり、文書の暗号復号化、署名、認証などの用途に使用される。
【０００３】
楕円曲線暗号はＥＣＥＳ（Ｅｌｌｉｐｔｉｃ　Ｃｕｒｖｅｓ　Ｅｎｃｒｙｐｔｉｏｎ　Ｓｔａｎｄａｒｄ）暗号、ＥＣＡＥＳ（Ｅｌｌｉｐｔｉｃ　ＣｕｒｖｅｓＡｄｖａｎｃｅｄ　Ｅｎｃｒｙｐｔｉｏｎ　Ｓｔａｎｄａｒｄ）暗号、ＥＣＤＳＡ（Ｅｌｌｉｐｔｉｃ　Ｃｕｒｖｅｓ　Ｄｉｇｉｔａｌ　ＳｉｇｎａｔｕｒｅＡｌｇｏｒｉｔｈｍ）署名、ＥＣＤＨ（Ｅｌｌｉｐｔｉｃ　Ｃｕｒｖｅｓ　Ｄｉｆｆｉｅ−Ｈｅｌｌｍｍｎ）秘密共有といった、いくつかの暗号プリミティブから構成されているが、点のスカラー倍算と呼ばれる演算はすべての暗号プリミティブに共通して使用され、かつ暗号処理の中心となるものである。このことから、楕円曲線暗号におけるスカラー倍演算の高速化を実現する技術は必要不可欠となっている。
【０００４】
楕円曲線暗号の例として、ＥＣＥＳ暗号プリミティブを説明する。送信者Ａは秘密鍵ｓ（ｓは整数）を持ち、受信者Ｂが秘密鍵ｔ（ｔは整数）を持つ場合に、楕円曲線Ｅと、楕円曲線Ｅ上に設定されるベースポイントＰ（ｘ，ｙ）と、公開鍵ｓ×Ｐ（送信者Ａの秘密鍵ｓとベースポイントＰとのスカラー倍算）と、公開鍵ｔ×Ｐ（送信者Ｂの秘密鍵ｔとベースポイントＰとのスカラー倍算）があらかじめ公開されている。このとき送信者Ａは、自分の秘密鍵ｓと、受信者Ｂの公開鍵ｔ×Ｐとのスカラー倍算ｓ×（ｔ×Ｐ）を計算し、そのｘ座標のビット表現を求め、このビット表現とメッセージのビット表現との間でビット対応のＥＯＲ演算を施すことで、メッセージｍに対する暗号文Ｃを生成し、それを受信者Ｂに送信する。受信者Ｂは、自分の秘密鍵ｔと、送信者Ａの公開鍵ｓ×Ｐとのスカラー倍算ｔ×（ｓ×Ｐ）を計算し、そのｘ座標のビット表現を求める。そして、”ｓ×（ｔ×Ｐ）＝ｔ×（ｓ×Ｐ）”という関係式が成立することを考慮して、そのビット表現と暗号文Ｃのビット表現との間でビット対応のＥＯＲ演算を施すことで、暗号文Ｃを復号し、メッセージｍを得る。このようにして、ＥＣＥＳ暗号と呼ばれる楕円曲線暗号のプリミティブでは、スカラー倍演算を用いて暗号・復号処理を行う。
【０００５】
ここで、ｐが５以上の素数、ｍを１以上の整数とすると、要素数ｐ＾ｍ（＾：べき乗を表す）の有限体ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線は、方程式
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる点∞を加えた集合である。無限遠点∞を０と表すこともある。ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ＾ｍ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
【０００６】
ＰをＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の点とする。以下のようにしてＰの逆元−Ｐ定義する。
（１）Ｐ＝∞ならば−Ｐ＝∞
（２）Ｐ≠∞ならばＰ＝（ｘ，ｙ）としたときに、−Ｐ＝（ｘ，−ｙ）
Ｐ１，Ｐ２をＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の２点とする。以下のようにしてＰ１とＰ２の和Ｐ３＝Ｐ１＋Ｐ２を定義する。
（１）Ｐ１＝∞ならばＰ３＝Ｐ２
（２）Ｐ２＝∞ならばＰ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならばＰ３＝∞
（４）Ｐ１≠−Ｐ２ならばＰ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２−ｘ１−ｘ２，　　　ｙ３＝λ×（ｘ１−ｘ３）−ｙ１，
ただし
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）　：Ｐ１≠Ｐ２のとき
λ＝（３×ｘ１＾２＋ａ）／（２×ｙ１）　：Ｐ１＝Ｐ２のとき
Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算ＥＣＡＤＤ、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算ＥＣＤＢＬと呼ぶ。
【０００７】
楕円加算と楕円２倍算は、有限体ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組合せによって計算される。
図７及び図８は、楕円加算と楕円２倍算の説明図である。楕円加算は、図７に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）とＰ２＝（ｘ２，ｙ２）とを結ぶ直線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ３＝Ｐ１＋Ｐ２＝（ｘ３，ｙ３）として定義される。
【０００８】
楕円２倍算は、図８に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）の接線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ４＝２×Ｐ１＝（ｘ４，ｙ４）として定義される。
【０００９】
有限体上の楕円曲線Ｅと、曲線上の点Ｐと、整数（スカラーとも呼ぶ）ｄに対して、点ｄ×Ｐ＝Ｐ＋Ｐ＋…Ｐ（ｄ個の和）を計算することをスカラー倍算という。スカラー倍算は、楕円加算と楕円２倍算の組合せによって実現される。
【００１０】
楕円加算、楕円２倍算、スカラー倍算の計算時間は、ＧＦ（ｐ＾ｍ）での乗算、平方算、逆元計算の計算時間の和によって見積もられることが多い。これは実際の楕円加算、楕円２倍算、スカラー倍算の計算が、ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組合せで計算され、多くの場合、加減算の計算時間はその他の計算時間に比べて無視できるほど短いからである。例えば上記の楕円加算は、ＧＦ（ｐ＾ｍ）における２回の乗算と１回の平方算と１回の逆元計算が必要である。このことを計算時間２Ｍ＋１Ｓ＋１Ｉと記す。
【００１１】
一般にＧＦ（ｐ＾ｍ）での逆元計算の計算時間は、乗算・平方算の計算時間に比べて非常に大きくなる。このため実際のスカラー倍算では、楕円曲線の点を表現する上で射影座標が使用される。射影座標では、点は（Ｘ：Ｙ：Ｚ）のようなＧＦ（ｐ＾ｍ）の３つの要素の組合せで表される。ただし（Ｘ：Ｙ：Ｚ）とｒ≠０であるＧＦ（ｐ＾ｍ）の要素ｒに対し（ｒ×Ｘ：ｒ×Ｙ：ｒ×Ｚ）は同じ点と考える。Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線は射影座標では、ｘ＝Ｘ／Ｚ，ｙ＝Ｙ／Ｚを代入して、
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３
となる。射影座標を用いると、楕円曲線上の点は（Ｘ：Ｙ：Ｚ）のような座標形式で表現することができる。無限遠点は∞＝（０：１：０）となる。射影座標を用いると、楕円加算は１２Ｍ＋２Ｓ、楕円２倍算は７Ｍ＋５Ｓで計算できるアルゴリズムが知られている。
【００１２】
楕円曲線におけるスカラー倍計算は楕円加算（ＥＣＡＤＤ）と楕円２倍算（ＥＣＤＢＬ）と呼ばれる演算の組合せで実現されるため、全体の計算時間はこれら演算の計算回数として評価される。スカラー倍算ｄ×Ｐの計算は、ｄの２進展開
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ［ｎ−２］×２＾（ｎ−２）＋・・・＋ｄ［１］×２＋ｄ［０］
を利用して行われる。
【００１３】
図９は、従来のスカラー倍算のアルゴリズム１の演算プログラムを示す図である。
図９において、ステップＳ１で変数Ｑ［０］の初期値をＰとし、ステップＳ３で点Ｑ［０］の楕円２倍算を実行し、演算結果をＱ［０］に格納する。そしてｄ［ｉ］＝＝１であれば、ステップＳ５で、Ｑ［０］と点Ｐの楕円加算を実行し、演算結果をＱ［０］に格納する。ステップＳ３〜Ｓ５の処理をｉ＝ｎ−２から０まで実行する。
【００１４】
このアルゴリズム１のスカラー倍算に必要な計算時間は、平均で（ｎ−１）／２×ＥＣＡＤＤ＋（ｎ−１）×ＥＣＤＢＬである。２進展解法の代わりに符号付き２進展解法を用いることで平均計算時間を（ｎ−１）／３×ＥＣＡＤＤ＋（ｎ−１）×ＥＣＤＢＬに減らすことができる。
【００１５】
【発明が解決しようとする課題】
楕円曲線暗号が現実社会において広く用いられるためには、処理時間及び実装上必要となるリソース（メモリ・回路量等）の低減が求められる。楕円曲線暗号ではスカラー倍算と呼ばれる演算が共通して使用され、暗号処理全体における比重も高いため、この部分の性能向上が暗号全体の性能向上に直結する。楕円曲線暗号処理においてスカラー倍算アルゴリズムの比重は高いため、さらなる高速化が望まれている。
【００１６】
しかしながら、上記のアルゴリズム１の演算方法では、楕円２倍算の演算結果Ｑ［０］を元にして楕円加算を行う必要があり、演算を逐次実行する必要があるのでスカラー倍算の演算時間の短縮には限界があった。
【００１７】
また、楕円曲線暗号は、他の暗号に比べて短い鍵長で高い安全性を確保できることから、特にスマートカードなどの低性能デバイスでの利用が進んでいる。しかしこれらのデバイスに対してはサイドチャネル攻撃が有効となる場合があり、サイドチャネル攻撃への耐性を持つスカラー倍算のアルゴリズムが必要となる。
【００１８】
本発明の課題は、サイドチャネル攻撃に対する耐性を持ち、かつスカラー倍算を高速で計算できるようにすることである。
【００１９】
【課題を解決するための手段】
本発明の楕円曲線暗号装置は、整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、楕円加算と楕円２倍算を１つの演算として定義し、かつ同じ種類の演算を並列に実行する演算手段とを備える。
【００２０】
この発明によれば、楕円加算と楕円２倍算を１つの演算として定義し、その演算の中で同じ種類の演算を並列に実行することでスカラー倍算の演算時間を短縮することができる。
【００２１】
本発明の他の楕円曲線暗号装置は、整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、（１）変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、（２）前記整数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）とし、（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）＝ＥＣＡＤＤＤＢＬ（（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）としたときに、前記（２）の演算を所定数回繰り返してｄ×Ｐを求める際に、前記ＥＣＡＤＤＤＢＬの同じ種類の演算を並列に実行する演算手段とを備える。
【００２２】
この発明によれば、ＥＣＡＤＤＤＢＬの演算の中で同じ種類の演算を並列に実行することでスカラー倍算の演算時間を短縮できる。さらに、ＥＣＡＤＤＤＢＬの演算がｄ［ｉ］の値に依存せずに実行されるのでサイドチャネル攻撃に対する耐性を高めることができる。
【００２３】
本発明の他の楕円曲線暗号装置は、整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、（１）変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、（２）前記整数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）とし、（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）＝ＥＣＡＤＤＤＢＬ（（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）としたときに、前記ＥＣＡＤＤＤＢＬは、Ｑ［ｄ［ｉ］］とＱ［ｄ［ｉ］＋１］の楕円加算Ｑ［ｄ［ｉ］］＋Ｑ［ｄ［ｉ］＋１］の結果をＱ［ｄ［ｉ］＋１］として設定し、Ｑ［ｄ［ｉ］］の楕円２倍算２×Ｑ［ｄ［ｉ］］の結果をＱ［ｄ［ｉ］］として設定する演算であり、前記（２）の演算を所定数回繰り返してｄ×Ｐを求める際に、前記ＥＣＡＤＤＤＢＬの同じ種類の演算を並列に実行する演算手段とを備える。
【００２４】
この発明によれば、ＥＣＡＤＤＤＢＬの演算の中で同じ種類の演算を並列に実行することでスカラー倍算の演算時間を短縮できる。さらに、ＥＣＡＤＤＤＢＬの演算がｄ［ｉ］の値に依存せずに実行されるのでサイドチャネル攻撃に対する耐性を高めることができる。
【００２５】
上記の発明において、前記演算手段は、点Ｐのｙ座標を使用せずにスカラー倍算ｄ×Ｐの演算を実行する。
楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ　　（＾：べき乗を表す）
Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３，Ｐ３’＝Ｐ１−Ｐ２のｘ座標をｘ３’としたときに、以下の式によりｙ座標を用いずに楕円加算・２倍算ＥＣＡＤＤＤＢＬを計算し、Ｐ１＋Ｐ２のｘ座標ｘ３と２×Ｐ１のｘ座標ｘ４を求める。
【００２６】
ｘ３＝［２×（ｘ１＋ｘ２）×（ｘ１×ｘ２＋ａ）＋４×ｂ］／［（ｘ１−ｘ２）＾２］−ｘ３’
ｘ４＝［（ｘ１＾２−ａ）＾２−８×ｂ×ｘ１］／［４×（ｘ１＾３＋ａ×ｘ１＋ｂ）］
このように構成することで、ｙ座標を使用せずにスカラー倍算の計算を行うことができるので演算プログラムを簡素にでき、演算時間を短縮できる。
【００２７】
前記演算手段は、Ｑ［０］とＱ［１］の初期値を設定する前計算の中で同じ種類の演算を並列に実行する。
上記の発明において、前記演算手段は、点Ｐのｘ座標を射影座標のＸ座標及びＺ座標に変換し、ｙ座標を使用せずに射影座標上におけるｄ×Ｐの点の座標を算出する。
【００２８】
このように構成することで、射影座標のＸ座標とＺ座標からｄ×Ｐの点の座標を算出することができるので演算プログラムが簡素になる。これにより演算時間短縮できる。
【００２９】
上記の発明において、前記演算手段は、射影座標上におけるｄ×Ｐの点の座標Ｘｄ，Ｚｄに基づいてｘ、ｙ座標を算出する後計算の中で同じ種類の演算を並列に実行する。
【００３０】
このように構成することで後計算の演算プログラムを簡素にできるので演算時間を短縮できる。
【００３１】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照しながら説明する。実施の形態の楕円曲線暗号装置は、例えば、楕円曲線暗号の専用の情報処理装置、パーソナルコンピュータ、ＩＣカード等に内蔵されたＩＣチップ、携帯電話機、携帯情報端末装置（ＰＤＡなど）、ＤＶＤプレーヤ等からなり、ＳＩＭＤ（Ｓｉｎｇｌｅ　ＩｎｓｔｒｕｃｔｉｏｎＭｕｌｔｉｐｌｅ　Ｄａｔａ）機能、すなわち同じ種類の命令で、異なるデータに対する処理を並列に実行する機能を有している。
【００３２】
以下の説明では、本発明に係る楕円曲線暗号演算方法を、ｐを５以上の素数とし、要素数ｐ＾ｍ（＾：べき乗を表す）の有限体ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線に適用した場合について説明する。
【００３３】
Ｗｉｅｒｓｔｒａｓｓ型楕円曲線Ｅは、以下の式で表せる。
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ＾ｍ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
【００３４】
図１は、本発明の第１の実施の形態の楕円曲線暗号のスカラー倍算ｄ×Ｐの演算プログラムを示す図である。
楕円曲線Ｅ上の点Ｐの座標（ｘ，ｙ）と、ｎビットの整数（自然数）ｄを取得（または入力）する。整数ｄの２進展開を
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ［ｎ−２］×２＾（ｎ−２）＋　　　　　　・・・＋ｄ［１］×２＋ｄ［０］（ｄ［ｎ−１］＝１，ｄ［ｉ］＝０，１）
とする。
【００３５】
図１の最初のステップＳ１は、変数Ｑ［０］の初期値としてＰを、変数Ｑ［１］の初期値としてＥＣＤＢＬ（Ｐ）＝２×Ｐを設定する。
次のステップＳ２は、ループを１巡する毎にｉをｎ−２から０まで１ずつ変化させる。
【００３６】
次のステップＳ３は、楕円加算と楕円２倍算とを１つの演算として定義し、かつ同じ種類の演算を並列に実行できるようにした楕円加算・２倍算ＥＣＡＤＤＤＢＬを実行する。
【００３７】
ＥＣＡＤＤＤＢＬの演算においては、Ｑ［ｄ［ｉ］］とＱ［ｄ［ｉ］＋１］の楕円加算の演算結果が、図１のステップＳ３の式の左辺のＱ［ｄ［ｉ］＋１］に設定され、Ｑ［ｄ［ｉ］］の楕円２倍算の演算結果が、ステップＳ３の左辺のＱ［ｄ［ｉ］］に設定される。
【００３８】
上記のステップＳ３のＥＣＡＤＤＤＢＬの演算を別の形で表すと、楕円曲線の点Ｐ１、Ｐ２の楕円加算Ｐ３＝Ｐ１＋Ｐ２と、楕円２倍算Ｐ４＝２×Ｐ１としたときに、（Ｐ３，Ｐ４）＝ＥＣＡＤＤＤＢＬ（Ｐ１，Ｐ２）と表せる。
【００３９】
上記の式の左辺の（Ｐ３，Ｐ４）が、図１のステップＳ３の演算式の左辺の（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）に対応し、上記の演算式の右辺の（Ｐ１，Ｐ２）が、図１のステップＳ３の演算式の右辺の（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）に対応する。
【００４０】
上記のステップＳ３の処理をｉ＝ｎ−２から０まで繰り返して、最終的な演算結果のＱ［０］をｄ×Ｐとして求める。
例えば、ｄ＝１０の場合について、図１の演算プログラムを説明する。
【００４１】
１０の２進展開は”１×２＾３＋０×２＾２＋１×２＾１＋０”で表せる。この場合、ｎ＝４となり、２進展開の係数ｄ［ｉ］は、ｄ［３］＝１、ｄ［２］＝０、ｄ［１］＝１、ｄ［０］＝０となる。
【００４２】
上記のステップＳ２〜Ｓ３が、ｉが”２”から”０”まで繰り返される。最初のｉ＝２のとき、２進展開の係数ｄ［２］は”０”であるので、Ｑ［ｄ［ｉ］＋１］＝Ｑ［ｄ［２］＋１］＝Ｑ［０＋１］＝Ｑ［１］、かつＱ［ｄ［ｉ］］＝Ｑ［ｄ［２］］＝Ｑ［０］となる。したがって、ステップＳ３の式は、
（Ｑ［１］，Ｑ［０］）＝ＥＣＡＤＤＤＢＬ（Ｑ［０］，Ｑ［１］）
となる。
【００４３】
初期値としてＱ［０］に”Ｐ”が、Ｑ［１］に”２×Ｐ”が設定されているので、Ｑ［０］とＱ［１］の楕円加算の結果として”Ｑ［０］＋Ｑ［１］＝Ｐ＋２×Ｐ＝３×Ｐ”が得られ、その値３×Ｐが、ステップＳ３の式の左辺のＱ［１］に設定される。さらに、Ｑ［０］の楕円２倍算の結果として２×Ｑ［０］＝２×Ｐが得られ、その値２×Ｐが、ステップＳ３の式の左辺のＱ［０］に設定される。
【００４４】
次に、ｉ＝１のとき、２進展開の係数ｄ［１］は”１”であるので、Ｑ［ｄ［ｉ］＋１］＝Ｑ［ｄ［１］＋１］＝Ｑ［１＋１］＝Ｑ［０］となり，Ｑ［ｄ［ｉ］］＝Ｑ［ｄ［１］］＝Ｑ［１］となる。したがって、ステップＳ３の式は、
（Ｑ［０］，Ｑ［１］）＝ＥＣＡＤＤＤＢＬ（Ｑ［１］，Ｑ［０］）
となる。
【００４５】
ｉ＝１のときには、前回のステップＳ３の処理でＱ［０］に”２×Ｐ”が、Ｑ［１］に”３×Ｐ”が設定されているので、ステップＳ３のＥＣＡＤＤＤＢＬの演算では、楕円加算の演算結果としてＱ［１］＋Ｑ［０］＝３×Ｐ＋２×Ｐ＝５Ｐが得られ、その値”５Ｐ”が、上記の式の左辺のＱ［０］に設定される。さらに、Ｑ［１］の楕円２倍算の演算結果として２×Ｑ［１］＝２×３×Ｐ＝６×Ｐが得られ、その値”６×Ｐ”が、上記の式の左辺のＱ［１］に設定される。
【００４６】
最後にｉ＝０のとき、係数ｄ［０］は”０”であるので、Ｑ［ｄ［ｉ］＋１］＝Ｑ［ｄ［０］＋１］＝Ｑ［０＋１］＝Ｑ［１］、かつＱ［ｄ［ｉ］］＝Ｑ［ｄ［０］］＝Ｑ［０］となる。したがって、ステップＳ３の式は、
（Ｑ［１］，Ｑ［０］）＝ＥＣＡＤＤＤＢＬ（Ｑ［０］，Ｑ［１］）
となる。
【００４７】
ｉ＝０のときには、前回のステップＳ３の処理でＱ［０］に”５Ｐ”が、Ｑ［１］に”６×Ｐ”が設定されているので、ステップＳ３のＥＣＡＤＤＤＢＬの演算において、楕円加算の演算結果としてＱ［０］＋Ｑ［１］＝５×Ｐ＋６×Ｐ＝１１×Ｐが得られ、その値”１１×Ｐ”が、上記の式の左辺のＱ［１］に設定される。さらに、楕円２倍算の演算結果として２×Ｑ［０］＝２×５×Ｐ＝１０×Ｐが得られ、その値”１０×Ｐ”が、上記の式の左辺のＱ［０］に設定される。
【００４８】
ｉ＝２〜０までの演算が終了したなら、ステップＳ４において、最終的な演算結果のＱ［０］、すなわち”１０×Ｐ”の演算結果がスカラー倍算ｄ×Ｐの値として算出される。
【００４９】
上述した第１の実施の形態によれば、楕円加算・２倍算ＥＣＡＤＤＤＢＬの演算プログラムとして、楕円加算と楕円２倍算の演算の中で共通する演算を１つにまとめ、さらに同じ種類の演算を並列に実行できるようにプログラムを作成することで、楕円加算と楕円２倍算の演算を別々に実行する場合に比べてスカラー倍算の演算プログラムを簡素にでき、演算時間を短縮できる。並列に実行可能な演算としては、例えば、乗算と乗算、加算と加算、加算と減算である。
【００５０】
さらに、図１の演算プログラムは、ｄ［ｉ］の値に依存せずに各ステップの処理が実行されるので、サイドアタック攻撃に対する耐性を高めることができる。この第１の実施の形態によれば、ＳＩＭＤ機能を有するマイクロプロセッサを用いて楕円曲線暗号のスカラー倍算の演算時間を短縮することができるので、複数のマイクロプロセッサを搭載することが難しいＩＣカード等のようなデバイスに特に有効である。
【００５１】
次に、図２は、本発明の第２の実施の形態の演算プログラムを示す図である。第２の実施の形態の演算プログラムは基本的には、図１に示す演算プログラムと同じであり、異なる点は、ｙ座標を使用せずにｘ座標だけを用いて楕円曲線暗号のスカラー倍算ｄ×Ｐの計算を行う点である。
【００５２】
図２のｘ座標のみを用いる楕円加算・２倍算ＥＣＡＤＤＤＢＬと、図１のＥＣＡＤＤＤＢＬを区別するため、前者の演算はＥＣＡＤＤＤＢＬの前に小文字のｘを付けている。
【００５３】
楕円曲線Ｅ上の点Ｐの座標（ｘ，ｙ）と、ｎビットの整数ｄを取得（または入力）する。整数ｄの２進展開を
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ［ｎ−２］×２＾（ｎ−２）＋・・・＋ｄ［１］×２＋ｄ［０］（ｄ［ｎ−１］＝１，ｄ［ｉ］＝０，１）
とする。
【００５４】
最初のステップＳ１で、変数Ｑ［０］の初期値としてＰのｘ座標を、変数Ｑ［１］の初期値としてｘＥＣＤＢＬ（Ｐ）の値を設定する。ここで、小文字のｘが付与されたｘＥＣＤＢＬ（Ｐ）は、ｙ座標を使用せずにＰ１のｘ座標から楕円２倍算２×Ｐ１のｘ座標を求める演算である。
【００５５】
ステップＳ３は、ｘＥＣＡＤＤＤＢＬ（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）の演算を実行し、楕円加算の結果のｘ座標をＱ［ｄ［ｉ］＋１］に、楕円２倍算の結果のｘ座標をＱ［ｄ［ｉ］］に格納する。
【００５６】
上記のＳ３の処理をｉ＝ｎ−２から０まで繰り返して、最終的な演算結果のＱ［０］をｄ×Ｐのｘ座標として求める。
第２の実施の形態によれば、上述した第１の実施の形態の効果に加え、ｘ座標のみを用いてスカラー倍算の演算を行えるので演算プログラムが簡素になり演算時間をさらに短縮することができる。
【００５７】
次に、本発明の第３の実施の形態を説明する。第３の実施の形態は、射影座標系において、Ｙ座標を使用せずにＸ座標とＺ座標とから楕円曲線暗号のスカラー倍算ｄ×Ｐの計算を行うものである。第３の実施の形態の演算アルゴリズムは図２のアルゴリズムと基本的には同じである。以下、射影座標における演算プログラムを図２を参照して説明する。
【００５８】
図２のステップＳ１で、変数Ｑ［０］の初期値として点Ｐの射影座標におけるＸ座標とＺ座標を、変数Ｑ［１］の初期値として、点Ｐの楕円２倍算ｘＥＣＤＢＬ（Ｐ）により得られ点のＸ座標とＺ座標を設定する。
【００５９】
ステップＳ３で、Ｑ［ｄ［ｉ］］とＱ［ｄ［ｉ］＋１］の楕円加算と、Ｑ［ｄ［ｉ］］の楕円２倍算を実行し、楕円加算の結果のＸ座標とＺ座標をＱ［ｄ［ｉ］＋１］に格納し、楕円２倍算の結果のＸ座標とＺ座標をＱ［ｄ［ｉ］］に格納する。
【００６０】
上記のステップＳ３の処理をｉ＝ｎ−２から０まで繰り返し、最終的な演算結果のＱ［０］をｄ×Ｐの点のＸ座標とＺ座標として求める。
ステップＳ３のｘＥＣＡＤＤＤＢＬの演算は、点Ｐ１のＸ座標とＺ座標及び点Ｐ２のＸ座標とＺ座標が与えられたときに、楕円加算Ｐ１＋Ｐ２により得られる点Ｐ３のＸ座標とＺ座標並びに楕円２倍算２×Ｐ１により得られる点Ｐ４のＸ座標とＺ座標を出力する演算である。
【００６１】
図３は、射影座標のＹ座標を使用せずにｄ×Ｐを計算する場合の演算プログラムの一例を示す図である。
射影座標におけるＷｉｅｒｓｔｒａｓｓ型楕円曲線Ｅは、以下の式で表せる。
【００６２】
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３
ここでａ，ｂ，Ｘ，Ｙ，ＺはＧＦ（ｐ＾ｍ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
【００６３】
楕円曲線Ｅ上の点Ｐの座標（Ｘ：Ｙ：Ｚ）と、ｎビットの整数ｄを取得（または入力）する。整数ｄの２進展開を
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ［ｎ−２］×２＾（ｎ−２）＋・・・＋ｄ［１］×２＋ｄ［０］（ｄ［ｎ−１］＝１，ｄ［ｉ］＝０，１）
とする。
【００６４】
図３において（１）〜（２５）は、プログラムのステップ番号を示しており、以下の説明では単に番号のみを記載する。
射影座標における点Ｐ１のＸ座標、Ｚ座標を（Ｘ１，Ｚ１）、点Ｐ２のＸ座標、Ｚ座標を（Ｘ２，Ｚ２）とする。
（１）点Ｐ１のＸ座標Ｘ１をメモリまたはレジスタ等からなるＲ５に設定する。
（２）点Ｐ１のＺ座標Ｚ１をメモリまたはレジスタ等からなるＲ６に設定する。
（３）点Ｐ２のＸ座標Ｘ２をメモリまたはレジスタ等からなるＲ７に設定する。
（４）点Ｐ２のＺ座標Ｚ２をメモリまたはレジスタ等からなるＲ８に設定する。
（５）Ｒ５とＲ７の乗算を行い、結果をＲ１（以下、記号はメモリまたはレジスタを示す）に設定する。同時に、Ｒ５とＲ８の乗算を行い、結果をＲ３に設定する。Ｒ５×Ｒ７は、点Ｐ１のＸ座標Ｘ１と点Ｐ２のＸ座標Ｘ２との乗算であり、Ｒ５×Ｒ８は、点Ｐ１のＸ座標Ｘ１と点Ｐ２のＺ座標Ｚ２との乗算である。
（６）Ｒ６とＲ８の乗算を行い、結果をＲ２に設定する。同時に、Ｒ７とＲ６の乗算を行い、結果をＲ４に設定する。Ｒ６×Ｒ８は、点Ｐ１のＺ座標Ｚ１と点Ｐ２のＺ座標Ｚ２との乗算であり、Ｒ７×Ｒ６は、点Ｐ２のＸ座標Ｘ２と点Ｐ１のＺ座標Ｚ１との乗算である。
（７）Ｒ３からＲ４を減算し、結果をＲ７に設定する。同時に、Ｒ３とＲ４の加算を行い、結果をＲ６に設定する。
（８）Ｒ３の平方算を行い、結果をＲ５に設定する。同時に、Ｒ２の平方算を行い、結果をＲ８に設定する。
（９）ａとＲ２の乗算を行い、結果をＲ４に設定する。同時に、ｂとＲ８の乗算を行い、結果をＲ８に設定する。
（１０）Ｒ１とＲ４の加算を行い、結果をＲ１に設定する。同時に、Ｒ８とＲ８の加算を行い結果をＲ８に設定する。
（１１）Ｒ６とＲ１の乗算を行い、結果をＲ１に設定する。同時に、Ｒ４とＲ２の乗算を行い、結果をＲ４に設定する。
（１２）Ｒ１とＲ１の加算を行い、結果をＲ１に設定する。同時に、Ｒ８とＲ８の加算を行い、結果をＲ８に設定する。
【００６５】
ＳＩＭＤ機能を有するプロセッサにより上記のプログラムを実行することにより、例えば、ステップ（５）のＲ５に格納されているデータとＲ７に格納されているデータの乗算と、Ｒ５に格納されているデータとＲ８に格納されているデータの乗算を並列に実行することができる。
【００６６】
これによりステップ（５）の乗算を別々に実行する場合に比べて、演算時間を半分にできる。
同様に、ステップ（７）のＲ３に格納されているデータからＲ４に格納されているデータの減算と、Ｒ３に格納されているデータとＲ４に格納されているデータとの加算を並列に実行することができるので、加算と減算を別々に実行する場合に比べて演算時間をほぼ半分にできる。
【００６７】
また、ステップ（８）のＲ３に格納されているデータの平方算と、Ｒ２に格納されているデータの平方算とを並列に実行できるので、平方算を逐次実行する場合に比べて演算時間をほぼ半分にできる。その他のステップについても同じ種類の演算を並列に実行することで演算時間を短縮できる。
（１３）Ｒ１に格納されているデータとＲ８に格納されているデータとの加算を行い、結果をＲ１に設定する。
（１４）Ｒ５に格納されているデータからＲ４に格納されているデータを減算し、結果をＲ６に設定する。同時に、Ｒ５に格納されているデータとＲ４に格納されているデータとの加算を行い、結果をＲ４に設定する。
（１５）Ｒ７に格納されているデータの平方算を行い、結果をＲ７に設定する。同時に、Ｒ６に格納されているデータの平方算を行い、結果をＲ６に設定する。
（１６）Ｒ２に格納されているデータとＲ３に格納されているデータとの乗算を行い、結果をＲ３に設定する。同時に、Ｒ２に格納されているデータとＲ２に格納されているデータとの乗算を行い、結果をＲ２に設定する。
（１７）Ｒ８に格納されているデータとＲ３に格納されているデータとの乗算を行い、結果をＲ５に設定する。同時に、Ｒ８に格納されているデータとＲ２に格納されているデータとの乗算を行い、結果をＲ８に設定する。
（１８）Ｒ５に格納されているデータとＲ５に格納されているデータとの加算を行い、結果をＲ５に設定する。同時に、Ｒ３に格納されているデータとＲ３に格納されているデータとの加算を行い、結果をＲ３に設定する。
（１９）Ｒ６に格納されているデータからＲ５に格納されているデータを減算し、結果をＲ６に設定する。同時に、Ｒ３に格納されているデータとＲ３に格納されているデータとの加算を行い、結果をＲ３に設定する。
（２０）Ｒ３に格納されているデータとＲ４に格納されているデータとの乗算を行い、結果をＲ３に設定する。同時に、ｘとＲ７の乗算を行い、結果をＲ２に設定する。
（２１）Ｒ３に格納されているデータとＲ８に格納されているデータとの加算を行い、結果をＲ３に設定する。同時に、Ｒ１からＲ２を減算し、結果をＲ１に設定する。
【００６８】
上述した（１）〜（２１）の処理により、点Ｐ３の射影座標におけるＸ座標，Ｙ座標及び点Ｐ４のＸ座標、Ｚ座標が算出され、その結果がＲ１、Ｒ７，Ｒ６、Ｒ３に格納される。
（２２）Ｒ１に格納されているデータを、点Ｐ１とＰ２の楕円加算により得られる点Ｐ３のＸ座標Ｘ３として出力する。
（２３）Ｒ７に格納されているデータを、点Ｐ１とＰ２の楕円加算により得られる点Ｐ３のＺ座標Ｚ３として出力する。
（２４）Ｒ６に格納されているデータを、点Ｐ１の楕円２倍算により得られる点Ｐ４のＸ座標Ｘ４として出力する。
（２５）Ｒ３に格納されているデータを、点Ｐ１の楕円２倍算により得られる点Ｐ４のＺ座標Ｚ４として出力する。
【００６９】
上記の演算プログラムによれば、７回の乗算と、２回の平方算と、数回の加減算とにより、楕円加算・２倍算ｘＥＣＡＤＤＤＢＬ（Ｐ１，Ｐ２）の出力として、点Ｐ３＝Ｐ１＋Ｐ２のＸ座標とＺ座標、点Ｐ４＝２×Ｐ１のＸ座標とＺ座標を算出することができる。
【００７０】
次に、図４は、本発明の第４の実施の形態の演算プログラムを示す図である。この第４の実施の形態は、図２の演算プログラムのＱ［０］とＱ［１］の初期値を設定する前計算の演算プログラムの一例を示している。
【００７１】
点Ｐ１のｘ座標ｘと、定数ａ，ｂ、乱数ｒが与えられる。
（１）乱数ｒを発生させ、結果をメモリまたはレジスタ等からなるＲ７に設定する。
（２）座標ｘの平方算を行い、結果をメモリまたはレジスタ等からなるＲ１に設定する。同時に、Ｒ７の平方算を行い、結果をメモリまたはレジスタ等からなるＲ２に設定する。
（３）Ｒ１からａを減算し、結果をメモリまたはレジスタ等からなるＲ３に設定する。同時に、Ｒ１とａの加算を計算し、結果をメモリまたはレジスタ等からなるＲ４に設定する。
（４）Ｒ３の平方算を行い、結果をＲ３に設定する。同時に、Ｒ２の平方算を行い、結果をＲ２に設定する。
【００７２】
ＳＩＭＤ機能を有するプロセッサにより上記のプログラムを実行することにより、例えば、ステップ（２）のｘの平方算と、Ｒ７に格納されているデータの平方算を同時に実行することができる。これによりステップ（２）の平方算を別々に実行する場合に比べて演算時間を半分にできる。
【００７３】
同様に、ステップ（３）のＲ１に格納されているデータからの定数ａの減算と、Ｒ３に格納されているデータと定数ａの加算とを並列に実行することができる。これにより、加算と減算を別々に実行する場合に比べて演算時間をほぼ半分にできる。
（５）ｂとｂの加算を行い、結果をＲ６（メモリまたはレジスタを指す、以下同じ）に設定する。同時に、ｘとｘの加算を行い、結果をＲ５に設定する。
（６）Ｒ５とＲ６の乗算を行い、結果をＲ１に設定する。同時に、Ｒ４とＲ５の乗算を行い、結果をＲ４に設定する。
（７）Ｒ１とＲ１の加算を行い、結果をＲ１に設定する。同時に、Ｒ４とＲ６の加算を行い、結果をＲ４に設定する。
（８）Ｒ３からＲ１を減算し、結果をＲ３に設定する。同時に、Ｒ４とＲ４の加算を行い、結果をＲ４に設定する。
（９）座標ｘとＲ７の乗算を行い、結果をＲ１に設定する。
（１０）Ｒ２とＲ３の乗算を行い、結果をＲ３に設定する。同時に、Ｒ２とＲ４の乗算を行い、結果をＲ４に設定する。
【００７４】
上述下図４の（１）〜（１０）の処理により、楕円曲線上の点Ｐの射影座標におけるＸ座標とＺ座標及び点Ｐの楕円２倍算の点２×Ｐの射影座標におけるＸ座標とＺ座標が算出される。
（１１）Ｒ１を点Ｐ３のＸ座標Ｘ３として出力する。
（１２）Ｒ７を点Ｐ３のＺ座標Ｚ３として出力する。
（１３）Ｒ３を点Ｐ４のＸ座標Ｘ４として出力する。
（１４）Ｒ４を点Ｐ４のＸ座標Ｚ４として出力する。
【００７５】
上記の前計算によりＱ［０］に初期値としてＰ＝（Ｘ３，Ｚ３）が設定され、Ｑ［１］に初期値として２×Ｐ＝（Ｘ４，Ｚ４）が設定される。しかも、この前計算の中で同じ種類の演算を並列に実行することができるので演算時間を短縮できる。
【００７６】
第４の実施の形態の演算プログラムによれば、同じ種類の演算を同時に実行することで、３回の乗算と、２回の平方算と、数回の加減算とによりスカラー倍算の前計算を行うことができる。
【００７７】
次に、図５は、本発明の第５の実施の形態の演算プログラムを示す図である。この第５の実施の形態は、図２の演算プログラムによりスカラー倍算ｄ×Ｐの射影座標が算出されたとき、その射影座標をｘ座標に変換する後計算を並列計算によって行うものである。
【００７８】
スカラー倍算ｄ×Ｐの点の射影座標Ｘｄ，Ｚｄと（ｄ＋１）×Ｐの点の射影座標Ｘ（ｄ＋１）、Ｚ（ｄ＋１）、点Ｐのｘ座標、ｙ座標、定数ａ，ｂを取得する。
（１）点ｄ×ＰのＸ座標Ｘｄをメモリまたはレジスタ等からなるＲ１に設定する。
（２）点ｄ×ＰのＺ座標Ｚｄをメモリまたはレジスタ等からなるＲ２に設定する。
（３）点（ｄ＋１）×ＰのＸ座標Ｘ（ｄ＋１）をメモリまたはレジスタ等からなるＲ３に設定する。
（４）点（ｄ＋１）×ＰのＺ座標Ｚ（ｄ＋１）をメモリまたはレジスタ等からＲ４に設定する。なお、（ｄ＋１）×Ｐの点の射影座標のＸ座標Ｘ（ｄ＋１）とＺ座標Ｚ（ｄ＋１）は、ＥＣＡＤＤＤＢＬの演算によりｄ×Ｐの点の射影座標と同時に算出されている。
（５）点Ｐ１の座標ｘとＲ２の乗算を行い、結果をＲ５に設定する。同時に、点Ｐ１の座標ｘとＲ１の乗算を行い、結果をＲ７に設定する。
（６）Ｒ５からＲ１を減算し、結果をＲ６に設定する。同時に、Ｒ５とＲ１の加算を行い、結果をＲ５に設定する。
（７）Ｒ６の平方算を行い、結果をＲ６に設定する。同時に、Ｒ２の平方算を行い、結果をＲ８に設定する。
【００７９】
ＳＩＭＤ機能を有するプロセッサにより上記のプログラムを実行することにより、例えば、ステップ（５）のｘとＲ２に格納されているデータの乗算と、ｘとＲ１に格納されているデータの乗算を並列に実行することができる。
【００８０】
これによりステップ（５）の乗算を別々に実行する場合に比べて、演算時間を半分にできる。
同様に、ステップ（６）のＲ５に格納されているデータからＲ１に格納されているデータの減算と、Ｒ５に格納されているデータとＲ１に格納されているデータとの加算を並列に実行することができるので、加算と減算を別々に実行する場合に比べて演算時間をほぼ半分にできる。
【００８１】
また、ステップ（７）のＲ６の平方算と、Ｒ２の平方算とを並列に実行できるので、平方算を逐次実行する場合に比べて演算時間をほぼ半分にできる。
（８）Ｒ３とＲ６の乗算を行い、結果をＲ６に設定する。同時に、ａとＲ２の乗算を行い、結果をＲ３に設定する。
（９）Ｒ８とＲ８の加算を行い、結果をＲ８に設定する。同時に、Ｒ３とＲ７の加算を行い、結果をＲ７に設定する。
（１０）Ｒ１とＲ２の乗算を行い、結果をＲ１に設定する。同時に、Ｒ５とＲ７の乗算を行い、結果をＲ７に設定する。
（１１）ｙとＲ４の乗算を行い、結果をＲ５に設定する。同時に、ｂとＲ８の加算を行い、結果をＲ２に設定する。
（１２）Ｒ５とＲ８の乗算を行い、結果をＲ３に設定する。同時に、Ｒ５とＲ１の乗算を行い、結果をＲ１に設定する。
（１３）Ｒ７とＲ２の加算を行い、結果をＲ７に設定する。同時に、Ｒ１とＲ１の加算を行い、結果をＲ１に設定する。
（１４）Ｒ４とＲ７の乗算を行い、結果をＲ７に設定する。
（１５）Ｒ７からＲ６を減算し、結果をＲ７に設定する。
（１６）Ｒ３の逆元を計算し、結果をＲ３に設定する。
（１７）Ｒ１とＲ３の乗算を行い、結果をＲ１に設定する。同時に、Ｒ７とＲ３の乗算を行い、結果をＲ７に設定する。
（１８）Ｒ１のデータをスカラー倍算ｄ×Ｐの点のｘ座標として出力し、Ｒ７のデータをスカラー倍算ｄ×Ｐの点のｙ座標として出力する。
【００８２】
以上の処理により射影座標系におけるｄ×Ｐの点のＸ座標とＺ座標からｘ、ｙ座標系におけるｄ×Ｐの点のｘ座標とｙ座標を求めることができる。
第５の実施の形態の演算プログラムによれば、図２の演算プログラムにおいて算出した射影座標系におけるＸ座標とＺ座標を、ｘ、ｙ座標系におけるｘ座標データに変換する後計算の中で同じ種類の演算を並列に実行することで、７回の乗算と、１回の平方算と、１回の逆元計算と、数回の加減算で後計算を実現できる。これにより後計算の処理時間を短縮できる。
【００８３】
ここで、上述した実施の形態のスカラー倍算の演算プログラムを実行する楕円曲線暗号装置のハードウェア構成の一例を図６を参照して説明する。楕円暗号装置は、例えば、パーソナルコンピュータ等の情報処理装置により実現できる。
【００８４】
バス２１によりＣＰＵ２２と接続されたＲＯＭ２３には、ＢＩＯＳなどの基本プログラムが格納される。また、基本プログラムは、バス２１により接続されるハードディスクなどの記憶装置２４に格納され、ＲＡＭ２５にコピーされてＣＰＵ２２により実行される。
【００８５】
ＣＰＵ２２は、ＳＩＭＤ機能を有するプロセッサである。記憶媒体読み取り装置２６は、フレキシブルディスク、ＣＤＲＯＭ、ＤＶＤ、ＩＣカード等の可搬記録媒体２７から本発明に係るプログラムを読み取り、ＣＰＵ２２が実行可能にすることもできる。
【００８６】
入出装置２８は、キーボード、マウス、ディスプレイなどからなり、ユーザのからの指示をＣＰＵに伝えたり、ＣＰＵ２２の演算結果をユーザに提示するためのものである。
【００８７】
通信インターフェース２９は、インターネット等のネットワーク３０を介して情報提供者３１と通信を行うためのものである。情報提供者３１は、本発明に係る楕円曲線暗号の演算プログラムをサーバ装置等に保持し、その演算プログラムをネットワーク３０を介して情報処理装置にダウンロードできるようにしても良い。
【００８８】
本発明は、ｎビットの整数ｄを２進展開する演算方法に限らず、楕円加算と楕円２倍算とによりスカラー倍算を求めるものであれば他の演算方法にも適用できる。
【００８９】
本発明は、楕円曲線暗号の暗号化及び解読を行う専用の装置に限らず、ＩＣカード、ＤＶＤ装置、携帯電話機、パーソナルコンピュータ等の種々の製品に適用できる。
（付記１）整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、
変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、楕円加算と楕円２倍算を１つの演算として定義し、かつ同じ種類の演算を並列に実行する演算手段とを備える楕円曲線暗号装置。
（付記２）整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、
（１）変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
（２）前記整数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）＝ＥＣＡＤＤＤＢＬ（（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）としたときに、
前記（２）の演算を所定数回繰り返してｄ×Ｐを求める際に、前記ＥＣＡＤＤＤＢＬの同じ種類の演算を並列に実行する演算手段とを備える楕円曲線暗号装置。
（付記３）整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得する取得手段と、
（１）変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
（２）前記整数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）＝ＥＣＡＤＤＤＢＬ（（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）としたときに、
前記ＥＣＡＤＤＤＢＬは、Ｑ［ｄ［ｉ］］とＱ［ｄ［ｉ］＋１］の楕円加算Ｑ［ｄ［ｉ］］＋Ｑ［ｄ［ｉ］＋１］の結果をＱ［ｄ［ｉ］＋１］として設定し、Ｑ［ｄ［ｉ］］の楕円２倍算２×Ｑ［ｄ［ｉ］］の結果をＱ［ｄ［ｉ］］として設定する演算であり、
前記（２）の演算を所定数回繰り返してｄ×Ｐを求める際に、前記ＥＣＡＤＤＤＢＬの同じ種類の演算を並列に実行する演算手段とを備える楕円曲線暗号装置。
（付記４）付記１，２または３記載の楕円曲線暗号装置において、
前記演算手段は、点Ｐのｙ座標を使用せずにスカラー倍算ｄ×Ｐの演算を実行する。
（付記５）付記１乃至４のいずれか１つに記載の楕円曲線暗号装置において、
前記演算手段は、Ｑ［０］とＱ［１］の初期値を設定する前計算の中で同じ種類の演算を並列に実行する。
（付記６）付記１乃至５のいずれか１つに記載の楕円曲線暗号装置において、
前記演算手段は、点Ｐのｘ座標を射影座標のＸ座標及びＺ座標に変換し、ｙ座標を使用せずに射影座標上におけるｄ×Ｐの点の座標を算出する。
（付記７）付記６記載の楕円曲線暗号装置において、
前記演算手段は、射影座標上におけるｄ×Ｐの点の座標Ｘｄ，Ｚｄに基づいてｘ、ｙ座標を算出する後計算の中で同じ種類の演算を並列に実行する。
（付記８）整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号演算方法において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得し、
変数Ｑ［０］の初期値として点Ｐの座標を設定し、
変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
楕円加算と楕円２倍算を１つの演算として定義し、かつ同じ種類の演算を並列に実行する楕円曲線暗号演算方法。
（付記９）整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号演算方法において、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得し、
（１）変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
（２）前記整数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）＝ＥＣＡＤＤＤＢＬ（（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）としたときに、
前記（２）の演算を所定数回繰り返してｄ×Ｐを求める際に、前記ＥＣＡＤＤＤＢＬの同じ種類の演算を並列に実行する楕円曲線暗号演算方法。
（付記１０）整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号プログラムにおいて、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得し、
変数Ｑ［０］の初期値として点Ｐの座標を設定し、
変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
楕円加算と楕円２倍算を１つの演算として定義し、かつ同じ種類の演算を並列に実行する楕円曲線暗号プログラム。
（付記１１）整数ｄと楕円曲線上に設定されるベースポイントＰとのスカラー倍算を計算する楕円曲線暗号プログラムにおいて、
有限体上の楕円曲線の点Ｐの座標とｎビットの整数ｄとを取得し、
（１）変数Ｑ［０］の初期値として点Ｐの座標を設定し、変数Ｑ［１］の初期値として点Ｐの楕円２倍算２×Ｐにより得られる点の座標を設定し、
（２）前記整数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
（Ｑ［ｄ［ｉ］＋１］，Ｑ［ｄ［ｉ］］）＝ＥＣＡＤＤＤＢＬ（（Ｑ［ｄ［ｉ］］，Ｑ［ｄ［ｉ］＋１］）としたときに、
前記（２）の演算を所定数回繰り返してｄ×Ｐを求める際に、前記ＥＣＡＤＤＤＢＬの同じ種類の演算を並列に実行する楕円曲線暗号プログラム。
【００９０】
【発明の効果】
本発明によれば、サイドチャンネル攻撃に耐性を保持したまま、スカラー倍算を高速化できる。また、スカラー倍算の前計算において、同じ種類の演算を並列に実行することで前計算の演算時間を短縮できる。さらに、射影座標におけるｄ×Ｐの点のＸ座標とＺ座標に基づいてｘ座標とｙ座標を計算する後計算において、同じ種類の演算を並列に実行することで後計算の演算時間を短縮できる。
【図面の簡単な説明】
【図１】第１の実施の形態の演算プログラムを示す図である。
【図２】第２の実施の形態の演算プログラムを示す図である。
【図３】第３の実施の形態の演算プログラムを示す図である。
【図４】第４の実施の形態の演算プログラムを示す図である。
【図５】第５の実施の形態の演算プログラムを示す図である。
【図６】実施の形態のハードウェア構成の一例を示す図である。
【図７】楕円加算の説明図である。
【図８】楕円２倍算の説明図である。
【図９】従来のスカラー倍算の演算プログラムを示す図である。
【符号の説明】
２２　　　ＣＰＵ
２３　　　ＲＯＭ
２５　　　ＲＡＭ
２６　　　記憶媒体読み取り装置
２７　　　可搬記録媒体
【図１】
2004053814.tif 000003
【図２】
2004053814.tif 000004
【図３】
2004053814.tif 000005
【図４】
2004053814.tif 000006
【図５】
2004053814.tif 000007
【図６】
2004053814.tif 000008
【図７】
2004053814.tif 000009
【図８】
2004053814.tif 000010
【図９】
2004053814.tif 000011