JP4543143B2 - 楕円曲線暗号装置、楕円曲線暗号演算方法 - Google Patents
楕円曲線暗号装置、楕円曲線暗号演算方法 Download PDFInfo
- Publication number
- JP4543143B2 JP4543143B2 JP2002342387A JP2002342387A JP4543143B2 JP 4543143 B2 JP4543143 B2 JP 4543143B2 JP 2002342387 A JP2002342387 A JP 2002342387A JP 2002342387 A JP2002342387 A JP 2002342387A JP 4543143 B2 JP4543143 B2 JP 4543143B2
- Authority
- JP
- Japan
- Prior art keywords
- register
- stored
- elliptic
- point
- multiplication
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Description
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線暗号装置、楕円曲線暗号演算方法及び楕円曲線暗号プログラムに関する。
【０００２】
【従来の技術】
楕円曲線暗号は公開鍵暗号の１つであり、文書の暗号復号化、署名、認証などの用途に使用される。
【０００３】
楕円曲線暗号はＥＣＥＳ(Elliptic Curves Encryption Standard)暗号、ＥＣＡＥＳ(Elliptic CurvesAdvanced Encryption Standard)暗号、ＥＣＤＳＡ(Elliptic Curves Digital SignatureAlgorithm)署名、ＥＣＤＨ(Elliptic Curves Diffie-Hellmmn)秘密共有といった、いくつかの暗号プリミティブから構成されているが、点のスカラー倍算と呼ばれる演算はすべての暗号プリミティブに共通して使用され、かつ暗号処理の中心となるものである。このことから、楕円曲線暗号におけるスカラー倍演算の高速化を実現する技術は必要不可欠となっている。
【０００４】
楕円曲線暗号の例としてＥＣＥＳ暗号プリミティブを説明する。送信者Ａは秘密鍵ｓ（ｓは整数）を持ち、受信者Ｂが秘密鍵ｔ（ｔは整数）を持つ場合に、楕円曲線Ｅと、楕円曲線Ｅ上に設定されるベースポイントＰ（ｘ，ｙ）と、公開鍵ｓ×Ｐ（送信者Ａの秘密鍵ｓとベースポイントＰとのスカラー倍算）と、公開鍵ｔ×Ｐ（送信者Ｂの秘密鍵ｔとベースポイントＰとのスカラー倍算）があらかじめ公開されている。このとき送信者Ａは、自分の秘密鍵ｓと、受信者Ｂの公開鍵ｔ×Ｐとのスカラー倍算ｓ×（ｔ×Ｐ）を計算し、そのｘ座標のビット表現を求め、このビット表現とメッセージのビット表現との間でビット対応のＥＯＲ演算を施すことで、メッセージｍに対する暗号文Ｃを生成し、それを受信者Ｂに送信する。受信者Ｂは、自分の秘密鍵ｔと、送信者Ａの公開鍵ｓ×Ｐとのスカラー倍算ｔ×（ｓ×Ｐ）を計算し、そのｘ座標のビット表現を求める。そして、”ｓ×（ｔ×Ｐ）＝ｔ×（ｓ×Ｐ）”という関係式が成立することを考慮して、そのビット表現と暗号文Ｃのビット表現との間でビット対応のＥＯＲ演算を施すことで、暗号文Ｃを復号し、メッセージｍを得る。このようにして、ＥＣＥＳ暗号と呼ばれる楕円曲線暗号のプリミティブでは、スカラー倍演算を用いて暗号・復号処理を行う。
【０００５】
ここで、ｐが５以上の素数、ｍを１以上の整数とすると、要素数ｐ＾ｍ（＾：べき乗を表す）の有限体ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線は、方程式
E：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる点∞を加えた集合である。無限遠点∞を０と表すこともある。ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ＾ｍ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
【０００６】
ＰをＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の点とする。
以下のようにしてＰの逆元−Ｐ定義する。
（１）Ｐ＝∞ならば−Ｐ＝∞
（２）Ｐ≠∞ならばＰ＝（ｘ，ｙ）としたときに、−Ｐ＝（ｘ，−ｙ）
Ｐ１，Ｐ２をＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の２点とする。以下のようにしてＰ１とＰ２の和Ｐ３＝Ｐ１＋Ｐ２を定義する。
（１）Ｐ１＝∞ならばＰ３＝Ｐ２
（２）Ｐ２＝∞ならばＰ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならばＰ３＝∞
（４）Ｐ１≠−Ｐ２ならばＰ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２−ｘ１−ｘ２， ｙ３＝λ×（ｘ１−ｘ３）−ｙ１，
ただし
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１） ：Ｐ１≠Ｐ２のとき
λ＝（３×ｘ１＾２＋ａ）／（２×ｙ１） ：Ｐ１＝Ｐ２のとき
Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算ＥＣＡＤＤ、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算ＥＣＤＢＬと呼ぶ。
【０００７】
楕円加算と楕円２倍算は、有限体ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組合せによって計算される。
図８及び図９は、楕円加算と楕円２倍算の説明図である。楕円加算は、図８に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）とＰ２＝（ｘ２，ｙ２）とを結ぶ直線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ３＝Ｐ１＋Ｐ２＝（ｘ３，ｙ３）として定義される。
【０００８】
楕円２倍算は、図９に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）の接線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ４＝２×Ｐ１＝（ｘ４，ｙ４）として定義される。
【０００９】
有限体上の楕円曲線Ｅと、曲線上の点Ｐと、整数（スカラーとも呼ぶ）ｄに対して、点ｄ×Ｐ＝Ｐ＋Ｐ＋…Ｐ（ｄ個の和）を計算することをスカラー倍算という。スカラー倍算は、楕円加算と楕円２倍算と楕円２＾ｋ倍算との組合せによって実現することができる。
【００１０】
楕円加算、楕円２倍算、楕円２＾ｋ倍算からなるスカラー倍算の計算時間は、ＧＦ（ｐ＾ｍ）での乗算、平方算、逆元計算の計算時間の和によって見積もられることが多い。これは実際の楕円加算、楕円２倍算、楕円２＾ｋ倍算からなるスカラー倍算の計算が、ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組合せで計算され、多くの場合、加減算の計算時間はその他の計算時間に比べて無視できるほど短いからである。
【００１１】
一般にＧＦ（ｐ＾ｍ）での逆元計算の計算時間は、乗算・平方算の計算時間に比べて非常に大きくなる。このため実際のスカラー倍算では、楕円曲線の点を表現する上でヤコビアン座標が使用されることがある。ヤコビアン座標では、点は（Ｘ，Ｙ，Ｚ）のような素体の３つの要素の組合せで表される。ただし（Ｘ，Ｙ，Ｚ）とｒ≠０であるＧＦ（ｐ＾ｍ）の要素ｒに対し（ｒ＾２×Ｘ：ｒ＾３×Ｙ：ｒ×Ｚ）は同じ点と考える。楕円曲線はヤコビアン座標では、ｘ＝Ｘ／Ｚ＾２，ｙ＝Ｙ／Ｚ＾３を代入して、
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３
となる。ヤコビアン座標を用いると、楕円曲線上の点は（Ｘ，Ｙ，Ｚ）のような座標形式で表現することができる。無限遠点は∞＝（０，１，０）となる。
【００１２】
楕円曲線におけるスカラー倍計算は楕円加算（ＥＣＡＤＤ）と楕円２倍算（ＥＣＤＢＬ）と楕円２＾ｋ倍算と呼ばれる演算の組合せで実現されるため、全体の計算時間はこれら演算の計算回数として評価される。スカラー倍算ｄ×Ｐの計算は、ｄの２進展開
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ［ｎ−２］×２＾（ｎ−２）＋・・・＋ｄ［１］×２＋ｄ［０］
を利用して行われる。
【００１３】
図１０は、従来のスカラー倍算のアルゴリズムに基づくの演算プログラムを示す図である。
図１０において、ステップＳ１で変数Ｑ［０］の初期値をＰとし、ステップＳ３で点Ｑ［０］の楕円２倍算を実行し、演算結果をＱ［０］に格納する。そしてｄ［ｉ］＝＝１であれば、ステップＳ５で、Ｑ［０］と点Ｐの楕円加算を実行し、演算結果をＱ［０］に格納する。ステップＳ３〜Ｓ５の処理をｉ＝ｎ−２から０まで実行する。楕円２倍算が連続して計算される場合には、楕円２＾ｋ倍算が適用可能である。
【００１４】
スカラー倍算の演算を高速化する方法は、種々の検討が行われており、ヤコビアン座標を用いた楕円曲線暗号の演算方法については、例えば、特開２０００−１３７４３６号公報に記載されている。
【００１５】
【特許文献１】
特開２０００−１３７４３６号公報（段落００２１）
【００１６】
【発明が解決しようとする課題】
楕円曲線暗号が現実社会において広く用いられるためには、処理時間及び実装上必要となるリソース（メモリ・回路量等）の低減が求められる。楕円曲線暗号ではスカラー倍算と呼ばれる演算が共通して使用され、暗号処理全体における比重も高いため、この部分の性能向上が暗号全体の性能向上に直結する。楕円曲線暗号処理においてスカラー倍算アルゴリズムの比重は高いため、さらなる高速化が望まれている。
【００１７】
本発明の課題は、楕円曲線暗号のスカラー倍算を高速に計算することである。
【００１８】
【課題を解決するための手段】
本発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、整数ｄの２進展開の係数ｄ〔ｉ〕（ｄ［ｉ］＝０，１）が連続して０となる回数ｋの計算結果を記憶するレジスタと、楕円曲線上の点Ｐのヤコビアン座標をＰ（ＸＰ、ＹＰ、ＺＰ）とし、ｉ＝０のときのＷ［ｉ］、Ｍ［ｉ］、Ｓ［ｉ］、Ｔ［ｉ］を、Ｗ［０］＝ａ・ＺＰ４、Ｍ［０］＝３・ＸＰ２＋Ｗ［０］、Ｓ［０］＝４・ＸＰ・ＹＰ２、Ｔ［０］＝８・ＹＰ４、とし、ｋ＝１の点のＸ、Ｙ、Ｚ座標を、Ｘ［１］＝Ｍ［０］２−２・Ｓ［０］、Ｙ［１］＝Ｍ［０］・（Ｓ［０］−Ｘ［１］）−Ｔ［０］、Ｚ［１］＝２・ＹＰ・ＺＰ、から算出し、（１）Ｗ［ｉ］＝２・Ｔ［ｉ−１］・Ｗ［ｉ−１］、（２）Ｍ［ｉ］＝３・Ｘ［ｉ］２＋Ｗ［ｉ］、（３）Ｓ［ｉ］＝４・Ｘ［ｉ］・Ｙ［ｉ］２
（４）Ｔ［ｉ］＝８・Ｙ［ｉ］４、（５）Ｘ［ｉ＋１］＝Ｍ［ｉ］２−２・Ｓ［ｉ］、（６）Ｙ［ｉ＋１］＝Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ−１］）−Ｔ［ｉ］、（７）Ｚ［ｉ＋１］＝２・Ｙ［ｉ］・Ｚ［ｉ］、前記レジスタに格納されている値ｋに基づいて変数ｉを１からｋ−１まで変化させて、上記（１）〜（７）の演算を行って楕円２ｋ倍算の演算を実行する際に、同じ種類の演算を並列に実行する演算手段とを備える。
【００１９】
この発明によれば、楕円加算の同じ種類の演算で異なるデータに対する演算を並列に実行し、さらに楕円２＾ｋ倍算の同じ種類の演算で異なるデータに対する演算を並列に実行することにより楕円加算と楕円２＾ｋ倍算の計算時間を短縮することができる。これにより、スカラー倍算の計算時間を短縮できる。
【００２０】
他の発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、楕円曲線上の点Ｐと点Ｑのヤコビアン座標における座標を、それぞれ（ＸＰ，ＹＰ，ＺＰ）、（ＸＱ，ＹＱ，ＺＱ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑの演算プログラムを記憶する記憶手段と、前記記憶手段に記憶されている楕円加算Ｐ＋Ｑの演算プログラムの同じ種類の演算を並列に実行して楕円加算Ｐ＋Ｑ＝Ｒの点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える。
【００２１】
この発明によれば、楕円加算の演算の中で同じ種類の演算を並列に実行することで楕円加算の計算時間を短縮できる。
他の発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、楕円曲線上の点Ｐのヤコビアン座標における座標を（ＸＰ，ＹＰ，ＺＰ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円２倍算２×Ｐの演算プログラムを記憶する記憶手段と、前記記憶手段に記憶されている楕円２倍算２×Ｐの演算プログラムの同じ種類の演算を並列に実行して楕円２倍算２×Ｐ＝Ｒの点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える。
【００２２】
この発明によれば、楕円２倍算の演算の中で同じ種類の演算を並列に実行することで楕円２倍算の計算時間を短縮できる。
他の発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、楕円曲線上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の演算プログラムを記憶する記憶手段と、前記記憶手段に記憶されている楕円２＾ｋ倍算の演算プログラムの同じ種類の演算を並列に実行して楕円２＾ｋ倍算により得られる点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える。
【００２３】
この発明によれば、楕円２＾ｋ倍算の演算の中で同じ種類の演算を並列に実行することで楕円２＾ｋ倍算の計算時間を短縮できる。
他の発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、整数ｄの２進展開の係数ｄ［ｄ］（ｄ［ｉ］＝０，１）とし、係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、計算結果をレジスタに格納し、レジスタに格納されている、係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の同じ種類の演算を並列に実行する。
【００２４】
この発明によれば、整数ｄの２進展開の係数ｄ［ｉ］が連続して「０」となる回数が２以上のとき、楕円２＾ｋ（ｋ＝２以上）倍算の同じ種類の演算を並列に実行することで、楕円２倍算を繰り返し実行する場合に比べて計算時間を短縮できる。
【００２５】
上記の発明において、前記演算手段は、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）と、点Ｑの座標（ＸＱ，ＹＱ，ＺＱ）とに基づいて楕円加算の演算プログラムの同じ種類の演算を並列に実行するようにしても良い。
【００２６】
また、前記演算手段は、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）に基づいて楕円２＾ｋ倍算の演算プログラムの同じ種類の演算を並列に実行するようにしても良い。
【００２７】
このように構成することで、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点の楕円加算または楕円２＾ｋ倍算の演算時間を短縮できる。
ヤコビアン座標を用いて楕円２＾ｋ倍算の計算を行う楕円曲線暗号装置において、整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、前記演算手段は、係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ倍算の同じ種類の演算を並列に実行する。
【００２８】
楕円加算、楕円２倍算、あるいは楕円２＾ｋ倍算の演算を行う演算手段が、演算命令及び複数のデータを記憶するレジスタ群と、演算器とを備え、前記レジスタ群に記憶された同じ種類の演算で異なるデータに対する演算を、前記演算器が並列に実行するようにしても良い。
【００２９】
このように構成することで、レジスタ群に記憶された楕円加算、楕円２倍算または楕円２＾ｋ倍算の同じ種類の演算を並列に実行して演算時間を短縮することができる。
【００３０】
なお、楕円加算、楕円２倍算、あるいは楕円２＾ｋ倍算の演算プログラムを記憶する記憶手段は、図１の記憶部１７に対応し、演算手段は、図１の演算部１２または演算器１３に対応する。
【００３１】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照しながら説明する。実施の形態の楕円曲線暗号装置は、例えば、楕円曲線暗号の専用の情報処理装置、パーソナルコンピュータ、ＩＣカード等に内蔵されたＩＣチップ、携帯電話機、携帯情報端末装置（ＰＤＡなど）、ＤＶＤプレーヤ等からなり、ＳＩＭＤ（Single Instruction stream Multiple Data stream）機能、すなわち同じ種類の命令で異なるデータに対する処理を並列に実行する機能を有している。
【００３２】
以下の説明では、本発明に係る楕円曲線暗号演算方法を、ｐを５以上の素数とし、要素数ｐの有限体ＧＦ（ｐ）（ｐは５以上の素数）上の楕円曲線に適用した場合について説明する。
【００３３】
ＧＦ（ｐ）上の楕円曲線Ｅは、以下の式で表せる。
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
【００３４】
図１は、本発明に係る楕円曲線暗号装置１１の要部の構成を示す図である。実施の形態の楕円曲線暗号装置１１の演算部（プロセッサ）１２は、演算器１３と、複数のレジスタからなるレジスタ群１４とからなる。
【００３５】
記憶部１５には、後述する楕円曲線暗号の楕円加算、楕円２倍算、楕円２＾ｋ倍算等の演算プログラムが記憶される。
演算部１２は、演算を実行する際に、複数のレジスタに格納されている同じ演算種別で異なるデータに対する演算を演算器１３を使用して並列に実行する。
【００３６】
次に、図２は、ヤコビアン座標を用いて楕円加算Ｐ＋Ｑの同じ種類の演算を並列に実行する本発明の第１の実施の形態の演算プログラムを示す図である。
図２に示す楕円加算の演算プログラムは、ヤコビアン座標における点Ｐの座標ＸＰ，ＹＰ，ＺＰ）と、点Ｑの座標（ＸＱ，ＹＱ，ＺＱ）を入力して、楕円加算Ｐ＋Ｑ＝Ｒの点Ｒの座標（ＺＲ，ＹＲ，ＺＲ）を並列計算により計算するものである。
【００３７】
（１）演算部（プロセッサ）１２が、点ＰのＸ座標ＸＰをレジスタ（またはメモリ）Ｒ１に設定する（図２のステップ（１））。
（２）演算部１２が、点ＰのＹ座標ＹＰをレジスタＲ２に設定する（図２のステップ（２））。
【００３８】
（３）点ＰのＺ座標ＺＰをレジスタＲ３に設定する（図２，ステップ（３））。
（４）点ＱのＸ座標ＸＱをレジスタＲ４に設定する（図２，ステップ（４））。
【００３９】
（５）点ＱのＹ座標ＹＱをレジスタＲ５に設定する（図２、ステップ（５））。
（６）点ＱのＺ座標ＺＱをレジスタＲ６に設定する（図２、ステップ（６））。
【００４０】
（７）次に、レジスタＲ３の平方算、すなわち点ＰのＺ座標ＺＰの２乗を求め、演算結果をレジスタＲ７に格納する。その演算と並列に、レジスタＲ６の平方算、すなわち点ＱのＺ座標ＺＱの２乗を求め、演算結果をレジスタＲ８に格納する（図２、ステップ（７））。この場合、同じ平方算の演算であるので、レジスタＲ３の値を２乗する演算と、レジスタＲ６の値を２乗する演算を演算部１２が並列に実行する。
【００４１】
（８）次に、レジスタＲ４とレジスタＲ７を乗算し、乗算結果をレジスタＲ４に格納する。同時に、レジスタＲ１とレジスタＲ８を乗算し、乗算結果をレジスタＲ１に格納する（図２，ステップ（８））。すなわち、点ＱのＸ座標ＸＱとレジスタＲ７に格納されている”ＺＰ＾２”を乗算し、乗算結果をレジスタＲ４に格納する。同時に、レジスタＲ１の点ＰのＸ座標ＸＰとレジスタＲ８に格納されている”ＺＱ＾２”を乗算し、乗算結果をレジスタＲ１に格納する。この場合も、同じ乗算の演算であるので、演算部１２は、レジスタＲ４とＲ７の乗算と、レジスタＲ１とＲ８の乗算を並列に実行する。
【００４２】
（９）次に、レジスタＲ２とレジスタＲ６を乗算し、乗算結果をレジスタＲ２に格納する。同時に、レジスタＲ３とレジスタＲ５を乗算し、乗算結果をレジスタＲ５に格納する（図２，ステップ（９））。すなわち、レジスタＲ２に格納されている点ＰのＹ座標ＹＰと、レジスタＲ６に格納されている点ＱのＺ座標ＺＱを乗算し、乗算結果をレジスタＲ２に格納する。同時に、レジスタＲ３に格納されている点ＰのＺ座標ＺＰと、レジスタＲ５に格納されている点ＱのＹ座標ＹＱを乗算し、乗算結果をレジスタＲ５に格納する。この場合も、同じ乗算の演算であるので、レジスタＲ２とＲ６の乗算と、レジスタＲ３とＲ５の乗算を演算部１２が並列に実行する。
【００４３】
（１０）上記ステップ（９）で計算したレジスタＲ２の値と、ステップ（７）で計算したレジスタＲ８の”ＺＱ＾２”を乗算し、乗算結果をレジスタＲ８に格納する。同時に、上記ステップ（９）で計算したレジスタＲ５の値と、ステップ（７）で計算したレジスタＲ７の”ＺＰ＾２”を乗算し、乗算結果をレジスタＲ７に格納する（図２，ステップ（１０））。
【００４４】
（１１）次に、レジスタＲ４からレジスタＲ１を減算し、減算結果をレジスタＲ２に格納する。同時に、レジスタＲ７からレジスタＲ８を減算し、減算結果をレジスタＲ８に格納する（図２，ステップ（１１））。すなわち、ステップ（８）で計算したレジスタＲ４の値から、ステップ（８）で計算したレジスタＲ１の値を減算し、結果をレジスタＲ２に格納する。同時に、ステップ（１０）で計算したレジスタＲ７の値から、ステップ（１０）で計算したレジスタＲ８の値を減算し、結果をレジスタＲ５に格納する。
【００４５】
（１２）次に、レジスタＲ２の平方算、すなわち、ステップ（１１）で計算したレジスタＲ２の値の２乗を計算し、計算結果をレジスタＲ７に格納する。同時に、レジスタＲ５の平方算、すなわち、ステップ（１１）で計算したレジスタＲ５の値の２乗を計算し、計算結果をレジスタＲ４に格納する（図２，ステップ（１２））。
【００４６】
（１３）次に、レジスタＲ１とＲ７を乗算し、乗算結果をレジスタＲ１に格納する。同時に、レジスタＲ２とＲ７を乗算し、乗算結果をレジスタＲ７に格納する（図２，ステップ（１３））。すなわち、ステップ（８）で計算したレジスタＲ１と、ステップ（１２）で計算したレジスタＲ７を乗算し、乗算結果をレジスタＲ１に格納する。同時に、ステップ（１１）で計算したレジスタＲ２と、ステップ（１２）で計算したレジスタＲ７を乗算し、乗算結果をレジスタＲ７に格納する。
【００４７】
（１４）次に、レジスタＲ８とＲ７を乗算し、乗算結果をレジスタＲ８に格納する。同時に、レジスタＲ３とＲ６を乗算し、乗算結果をレジスタＲ３に格納する（図２，ステップ（１４））。すなわち、ステップ（１０）で計算したレジスタＲ８と、ステップ（１３）で計算したレジスタＲ７を乗算し、結果をレジスタＲ８に格納する。また、レジスタＲ３に格納されている点ＰのＺ座標ＺＰと、レジスタＲ６に格納されている点ＱのＺ座標ＺＱを乗算し、結果をレジスタＲ３に格納する。
【００４８】
（１５）次に、レジスタＲ４からレジスタＲ７を減算し、結果をレジスタＲ４に格納する。同時に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ６に格納する（図２，ステップ（１５））。
【００４９】
（１６）次に、レジスタＲ４からレジスタＲ６を減算し、結果をレジスタＲ４に格納する（図２，ステップ（１６））。すなわち、ステップ（１５）で計算したレジスタＲ４の値から、ステップ（１５）で計算したレジスタＲ６の値を減算し、結果をレジスタ４に格納する。
【００５０】
（１７）次に、レジスタＲ１からレジスタＲ４を減算し、結果をレジスタＲ１に格納する（図２，ステップ（１７））。すなわち、ステップ（１３）で計算したレジスタＲ１の値から、ステップ（１６）で計算したレジスタＲ４の値を減算し、結果をレジスタＲ１に格納する。
【００５１】
（１８）次に、レジスタＲ５とＲ１を乗算し、乗算結果をレジスタＲ５に格納する。同時に、レジスタＲ３とＲ２を乗算し、乗算結果をレジスタＲ３に格納する（図２，ステップ（１８））。すなわち、ステップ（１１）で計算したレジスタＲ５と、ステップ（１７）で計算したレジスタＲ１とを乗算し、結果をレジスタＲ５に格納する。同時に、ステップ（１４）で計算したレジスタＲ３と、ステップ（１１）で計算したレジスタＲ２を乗算し、結果をレジスタＲ３に格納する。
【００５２】
（１９）次に、レジスタＲ５からレジスタＲ８を減算し、結果をレジスタＲ７に格納する（図２，ステップ（１９））。すなわち、ステップ（１８）で計算したレジスタＲ５から、ステップ（１４）で計算したレジスタＲ８を減算し、結果をレジスタＲ７に格納する。
【００５３】
以上の処理により、レジスタＲ４，Ｒ７，Ｒ３に楕円加算Ｐ＋Ｑ＝Ｒの点Ｒのヤコビアン座標のＸ座標、Ｙ座標、Ｚ座標が格納される。
（２０）次に、レジスタＲ４に格納されている値を、点ＲのＸ座標ＸＲとして出力する（図２，ステップ（２０））。
【００５４】
（２１）レジスタＲ７に格納されている値を、点ＲのＹ座標ＹＲとして出力する（図２，ステップ（２１））。
（２２）レジスタＲ３に格納されている値を、点ＲのＺ座標ＺＲとして出力する（図２，ステップ（２２））。
【００５５】
上述した処理により、ヤコビアン座標において、点Ｐと点Ｑの楕円加算Ｐ＋Ｑ＝Ｒにより得られる点Ｒの座標（ＸＲ，ＹＲ，ＺＲ）を求めることができる。
上述した第１の実施の形態は、楕円加算Ｐ＋Ｑの同じ種類の演算を演算部１２が並列に実行できるように演算プログラムを作成し、演算部１２が同じ種類の演算を並列に実行することで、６回の乗算と、２回の平方算と、５回の加減算とにより楕円加算の計算を行うことができる。これにより楕円加算の計算時間、すなわち、スカラー倍算の計算時間を短縮できる。
【００５６】
次に、図３は、ヤコビアン座標を用いて楕円２倍算２×Ｐの同じ種類の演算を並列に実行する本発明の第２の実施の形態の演算プログラムを示す図である。
この演算プログラムは、ヤコビアン座標における点Ｐの座標（ＸＰ，ＹＰ，ＺＰ）を取得して、楕円２倍算２×Ｐにより得られる点Ｒの座標（ＸＲ，ＹＲ，ＺＲ）を並列計算により求めるものである。
【００５７】
（１）点ＰのＸ座標ＸＰをレジスタ（またはメモリ）Ｒ１に設定する（図３，ステップ（１））。
（２）点ＰのＹ座標ＹＰをレジスタＲ２に設定する（図３，ステップ（２））。
【００５８】
（３）点ＰのＺ座標ＺＰをレジスタＲ３に設定する（図３，ステップ（３））。
（４）次に、レジスタＲ１の平方算、すなわち、点ＰのＸ座標ＸＰの２乗を計算し、計算結果をレジスタＲ４に格納する。同時に、レジスタＲ３の平方算、すなわち点ＰのＺ座標ＺＰの２乗を計算し、計算結果をレジスタＲ５に格納する（図３，ステップ（４））。この場合、同じ平方算であるのでレジスタＲ１に対する平方算と、レジスタＲ３に対する平方算を、演算部１２が並列に実行することができる。
【００５９】
（５）次に、レジスタＲ２の平方算、すなわちレジスタＲ２に格納されている点ＰのＹ座標ＹＰの２乗を計算し、計算結果をレジスタＲ６に格納する。同時に、レジスタＲ５の平方算、すなわちレジスタＲ５に格納されているＺＰ＾２の２乗を計算し、計算結果をレジスタＲ５に格納する（図３，ステップ（５））。
【００６０】
（６）次に、レジスタＲ１とＲ６を乗算し、乗算結果をレジスタＲ１に格納する。同時に定数ａとレジスタＲ５を乗算し、乗算結果をレジスタＲ５に格納する（図３，ステップ（６））。すなわち、レジスタＲ１に格納されているＸ座標ＸＰと、レジスタＲ６に格納されているＹＰ＾２を乗算し、乗算結果をレジスタＲ１に格納する。また、定数ａとレジスタＲ５に格納されているＺＰ＾４を乗算し、乗算結果の”ａ・ＺＰ＾４”をレジスタＲ５に格納する。この処理により、レジスタＲ５には”ａ・ＺＰ＾４”が格納される。ここで、”Ｗ［０］＝ａ・ＺＰ＾４”とする。
【００６１】
（７）次に、レジスタＲ４とＲ４を加算し、加算結果をレジスタＲ７に格納する。同時にレジスタＲ４とＲ５を加算し、加算結果をレジスタＲ５に格納する（図）３，ステップ（７））。すなわち、レジスタＲ４に格納されているＸＰ＾２を互いに加算し、加算結果の”２・ＸＰ＾２”をレジスタＲ７に格納する。また、レジスタＲ４に格納されている”ＸＰ＾２”と、レジスタＲ５に格納されているＷ［０］を加算し、加算結果の”ＸＰ＾２＋Ｗ［０］”をレジスタＲ５に格納する。
【００６２】
（８）次に、レジスタＲ５とＲ７を加算し、加算結果をレジスタＲ５に格納する。同時にレジスタＲ１とＲ１を加算し、加算結果をレジスタＲ１に格納する（図３，ステップ（８））。すなわち、レジスタＲ５に格納されている”ＸＰ＾２＋Ｗ［０］”と、レジスタＲ７に格納されている”２・ＸＰ＾２”を加算し、加算結果の”３・ＸＰ＾２＋Ｗ［０］”をレジスタＲ５に格納する。ここで、”Ｍ〔０〕＝３・ＸＰ＾２＋Ｗ〔０〕”とする。同時に、レジスタＲ１に格納されている”ＸＰ・ＹＰ＾２”を互いに加算し、加算結果をレジスタＲ１に格納する。
【００６３】
（９）次に、レジスタＲ５の平方算を計算し、計算結果をレジスタＲ４に格納する。同時に、レジスタＲ６の平方算を計算し、計算結果をレジスタＲ６に格納する（図３，ステップ（９））。すなわち、上記ステップ（８）の処理によりレジスタＲ５に格納される”Ｍ〔０〕＝３・ＸＰ＾２＋Ｗ〔０〕”の２乗を求め、演算結果をレジスタＲ４に格納する。同時に、レジスタＲ６に格納されているＹＰ＾２の２乗を計算し、計算結果のＹＰ＾４をレジスタＲ６に格納する。
【００６４】
（１０）次に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ１に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図３，ステップ（１０））。すなわち、レジスタＲ１に格納されている”２・ＸＰ・ＹＰ＾２”どうしを加算し、加算結果の”４・ＸＰ・ＹＰ＾２”をレジスタＲ１に格納する。ここで、”Ｓ〔０〕＝４・ＸＰ・ＹＰ＾２”とする。同時に、レジスタＲ６に格納されているＹＰ＾４どうしを加算し、結果をレジスタＲ６に格納する。
【００６５】
（１１）次に、上記のステップ（１０）で求めたレジスタＲ１とＲ１を加算し、加算結果をレジスタＲ７に格納する。同時に、上記のステップ（１０）で求めたレジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図３，ステップ（１１））。すなわち、レジスタＲ１に格納されている”Ｓ〔０〕＝４・ＸＰ・ＹＰ＾２”どうしを加算し、加算結果の２・Ｓ〔０〕をレジスタＲ７に格納する。同時に、レジスタＲ６に格納されている”２・ＹＰ＾４”どうしを加算し、結果をレジスタＲ６に格納する。
【００６６】
（１２）次に、レジスタＲ４からＲ７の値を減算し、減算結果をレジスタＲ４に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図３，ステップ（１２））。すなわち、レジスタＲ４に格納されている”Ｍ〔０〕＾２”から、レジスタＲ７に格納されている２・Ｓ〔０〕を減算し、減算結果の”Ｍ〔０〕＾２−２・Ｓ〔０〕”をレジスタＲ４に格納する。ここで、Ｘ〔１〕＝Ｍ〔０〕＾２−２・Ｓ〔０〕”とする。同時に、レジスタＲ６に格納されている４・ＹＰ＾４どうしを加算し、加算結果の”８・ＹＰ＾４”をレジスタＲ６に格納する。ここで、”Ｔ〔０〕＝８・ＹＰ＾４”とする。
【００６７】
（１３）次に、レジスタＲ１から、上記のステップ（１２）で求めたレジスタＲ４を減算し、減算結果をレジスタＲ１に格納する（図３，ステップ（１３））。すなわち、レジスタＲ１に格納されている”Ｓ〔０〕”から、レジスタＲ４に格納されている”Ｘ〔１〕＝Ｍ〔０〕＾２−２・Ｓ〔０〕”を減算し、減算結果をレジスタＲ１に格納する。
【００６８】
（１４）上記のステップ（１３）で計算したレジスタＲ１の”Ｓ〔０〕−Ｘ〔１〕”と、レジスタＲ５に格納されているＭ〔０〕を乗算し、乗算結果の”Ｍ〔０〕・（Ｓ〔０〕−Ｘ〔１〕）”をレジスタＲ１に格納する。同時に、レジスタＲ２に格納されている点ＰのＹ座標ＹＰと、レジスタＲ３に格納されている点ＰのＺ座標ＺＰを乗算し、乗算結果の”ＹＰ・ＺＰ”をレジスタＲ２に格納する（図３，ステップ（１４））。
【００６９】
（１５）上記のステップ（１４）で計算したレジスタＲ１の”Ｍ〔０〕・（Ｓ〔０〕−Ｘ〔１〕）から、レジスタＲ６に格納されているＴ〔０〕を減算し、減算結果の”Ｍ〔０〕・（Ｓ〔０〕−Ｘ〔１〕）−Ｔ〔０〕”をレジスタＲ１に格納する。同時に、上記のステップ（１４）で求めたレジスタＲ２とＲ２を加算し、加算結果の”２・ＹＰ・ＺＰ”をレジスタＲ２に格納する（図３，ステップ（１５））。
【００７０】
以上の処理により、楕円２倍算２×Ｐにより得られるヤコビアン座標における点Ｒの座標が計算できたので、ステップ（１６）において、レジスタＲ４の値を点ＲのＸ座標ＸＲとして出力する。また、ステップ（１７）において、レジスタＲ１の値を点ＲのＹ座標ＹＲとして出力する。さらに、ステップ（１８）において、レジスタＲ２の値を点ＲのＺ座標ＺＲとして出力する。
【００７１】
上述した第２の実施の形態は、楕円２倍算２×Ｐの同じ種類の演算を並列に実行できるように演算プログラムを作成し、演算部１２が楕円２倍算の同じ種類の演算を並列に実行することで、２回の乗算と、３回の平方算と、７回の加減算とにより楕円２倍算の計算を行うことができる。これにより、楕円２倍の計算時間を短縮し、スカラー倍算の計算時間を短縮することができる。
【００７２】
次に、図４は、楕円２＾ｋ倍算（＾：べき乗を表す、ｋ＝１以上の整数）を用いてスカラー倍算の計算を行う本発明の第３の実施の形態の演算プログラムを示す図である。
【００７３】
先ず、楕円２＾ｋ倍算２＾ｋ×Ｐを用いたスカラー倍算の演算プログラムを、図４を参照して説明する。図４のプログラムはＣ＋＋で記述してある。
整数ｄと、楕円曲線上の点Ｐの座標とを入力する。
【００７４】
変数Ｑ［０］に点Ｐの座標を設定する（図４，Ｓ１１）。変数ｉの初期値としてｉ＝ｎ−２を設定する（図４，Ｓ１２）。
while文と、ループ内の命令の実行条件である”ｉ＞０”を定義する（図４，Ｓ１３）。変数ｗの初期値として「１」を設定する（図４，Ｓ１４）。
【００７５】
次に、while文とループ内の命令の実行条件であるｄ［ｉ］＝＝０を定義する（図４，Ｓ１５）。
次に、変数ｉが「０」か否かを判断し、変数ｉが「０」、すなわち、すべての係数ｄ［ｉ］の判定が終了した場合にはループを抜ける（図４，Ｓ１６）。
【００７６】
次に、変数ｉをデクリメントする（図４，Ｓ１７）。さらに、変数ｗをインクリメントする（図４，Ｓ１８）。すなわち、係数ｄ［ｉ］が「０」で、かつ変数ｉが「０」でないとき、変数ｗがインクリメントされる。その後、ループの先頭のステップＳ１５に戻る（図４，Ｓ１９）。
【００７７】
上記のステップＳ１５からステップＳ１９の処理を繰り返すことにより、２進展開の係数ｄ［ｉ］が連続して「０」となる回数が計算され、その計算結果がレジスタｗに格納される。
【００７８】
ステップＳ１５において、係数ｄ［ｉ］が「０」でないと判断されたときには、ステップＳ２０に進み楕円２＾ｋ倍算の演算を定義した関数iecdbl（Ｑ［０］，ｗ）を呼び出して実行する。関数iecdbl（Ｑ［０］，ｗ）は、変数Ｑ［０］により定まる点の楕円２＾ｋ倍算（ｋ＝ｗ）の計算を行う関数である。
【００７９】
ステップＳ２０の楕円２＾ｋ倍算の演算が終了したなら、係数ｄ〔ｉ〕が「１」か否かを判断する（図４，ステップ２１）。
係数ｄ〔ｉ〕が「１」、すなわち、ステップＳ２１の条件が真であれば、次のステップＳ２２に進み、点Ｑ［０］（変数Ｑ［０］により指定される点）と点Ｐとの楕円加算”Ｑ［０］＝ecadd（Ｑ［０］，Ｐ）”を計算し、計算結果を変数Ｑ［０］に格納する。
【００８０】
ステップ２３は、ステップ２１からのループの終了を示す。次のステップＳ２４において、変数ｉをデクリメントし、その後、ループの先頭のステップＳ１３に戻る。
【００８１】
上述した処理により、係数ｄ［ｉ］が連続して「０」となる回数ｗが計算され、楕円２＾ｋ倍算（ｋ＝ｗ）が実行される。これにより、例えば、楕円２倍算をｋ回計算する必要がある場合でも、楕円２＾ｋ倍算の関数iecdbl（Ｑ［０］，ｗ）を一度呼び出すだけで２＾ｋ×Ｐの計算を行うことができるので、スカラー倍算における楕円２倍算の全体の計算時間を短縮できる。さらに、楕円２＾ｋ倍算を計算する関数iecdbl（Ｑ［０］，ｗ）のプログラムを、同じ種類の演算を、１つのプロセッサからなる演算部１２で並列に実行できるように記述することで、楕円２＾ｋ倍算の演算時間を短縮できる。楕円２＾ｋ倍算の演算の並列計算の方法については、次に詳しく説明する。
【００８２】
次に、図５は、図４のスカラー倍算の演算プログラムの楕円２＾ｋ倍算２＾ｋ×Ｐを計算する関数Ｑ〔０〕＝iecdbl（Ｑ〔０〕，ｗ）の演算式を示す図である。
【００８３】
楕円曲線上の点Ｐのヤコビアン座標における座標をＰ＝（ＸＰ，ＹＰ，ＺＰ）、楕円２＾ｋ倍算のべき乗の値をｋ、定数をａとし、楕円２＾ｋ倍算により得られる点Ｒの座標をＲ＝（ＸＲ，ＹＲ，ＺＲ）する。
【００８４】
Ｗ［０］を”ａ・ＺＰ＾４”とする（図５，Ｓ３１）
Ｍ［０］を”３・ＸＰ＾２＋Ｗ［０］”とする（図５，Ｓ３２）。
Ｓ［０］を”４・ＸＰ・ＹＰ＾２”とする（図５，Ｓ３３）。
【００８５】
Ｔ［０］を”８・ＹＰ＾４”とする（図５，Ｓ３４）。
ｋ＝１の点のＸ座標、Ｙ座標、Ｚ座標は、以下のように表せる。
Ｘ［１］＝Ｍ［０］＾２−２・Ｓ［０］（図５，Ｓ３５）
Ｙ［１］＝Ｍ［０］・（Ｓ［０］−Ｘ［１］）−Ｔ［０］（図５，Ｓ３６）
Ｚ［１］＝２・ＹＰ・ＺＰ（図５，Ｓ３７）
楕円２＾ｋ倍算を計算するために、以下の演算をｋ−１回繰り返す（図５，Ｓ３８）。
【００８６】
Ｗ［ｉ］＝２・Ｔ［ｉ−１］・Ｗ［ｉ−１］、を計算する（図５，Ｓ３９）。
Ｍ［ｉ］＝３・Ｘ［ｉ］＾２＋Ｗ［ｉ］、を計算する（図５，Ｓ４０）。
Ｓ［ｉ］＝４・Ｘ［ｉ］・Ｙ［ｉ］＾２、を計算する（図５，Ｓ４１）。
【００８７】
Ｔ［ｉ］＝８・Ｙ［ｉ］＾４、を計算する（図５，Ｓ４２）。
Ｘ［ｉ＋１］＝Ｍ［ｉ］＾２−２・Ｓ［ｉ］、を計算する（図５，Ｓ４３）。
Ｙ［ｉ＋１］＝Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ−１］）−Ｔ［ｉ］、を計算する（図５，Ｓ４４）。
【００８８】
Ｚ［ｉ＋１］＝２・Ｙ［ｉ］・Ｚ［ｉ］、を計算する（図５，Ｓ４５）。
上記の演算をｋ−１回実行して得られるＸ［ｋ］を、点ＲのＸ座標ＸＲとして出力する（図５，Ｓ４６）。
【００８９】
同様に、Ｙ［ｋ］を、点ＲのＹ座標ＹＲとして出力する（図５，Ｓ４７）。また、Ｚ［ｋ］を、点ＲのＺ座標ＺＲとして出力する（図５，Ｓ４８）。
上記の処理により、楕円２＾ｋ倍算により得られるヤコビアン座標の点Ｒの座標（ＸＲ，ＹＲ，ＺＲ）が（Ｘ［ｋ］，Ｙ［ｋ］，Ｚ［ｋ］）として求めることができる。
【００９０】
次に、図６は、図５の演算式に基づいて作成した楕円２＾ｋ倍算の演算プログラムを示す図である。この演算プログラムは、楕円２＾ｋ倍算の演算において、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述したものである。
【００９１】
最初に、楕円曲線上の点Ｐの座標Ｐ（ＸＰ，ＹＰ，ＺＰ）と、変数ｋの値と、定数ａを設定する。なお、変数ｋの値として、図４の演算プログラムで計算したｄ［ｉ］が連続して「０」となる回数ｗが設定される。
【００９２】
（１）演算部１２は、点ＰのＸ座標ＸＰをレジスタＲ１に設定する（図６，ステップ（１））。
（２）演算部１２は、点ＰのＹ座標ＹＰをレジスタＲ２に設定する（図６，ステップ（２））。
【００９３】
（３）演算部１２は、点ＰのＺ座標ＺＰをレジスタＲ３に設定する（図６，ステップ（３））。
（４）演算部１２は、レジスタＲ１の平方算を計算し、計算結果のＸＰ＾２をレジスタＲ４に格納する。同時に、レジスタＲ３の平方算を計算し、計算結果のＺＰ＾２をレジスタＲ５に格納する（図６のステップ（４））。
【００９４】
（５）次に、レジスタＲ２の平方算を計算し、計算結果のＹＰ＾２をレジスタＲ６に格納し、同時にレジスタＲ５の平方算を計算し、計算結果のＺＰ＾４レジスタＲ５に格納する（図６，ステップ（５））。
【００９５】
（６）次に、レジスタＲ１とＲ６を乗算し、乗算結果をレジスタＲ１に格納する。同時に、定数ａとレジスタＲ５を乗算し、乗算結果の”ａ・ＺＰ＾４”をレジスタＲ８に格納する（図６，ステップ（６））。このステップ（６）の処理は、定数ａとレジスタＲ５の値を乗算することで、図５の演算式の”Ｗ［０］＝ａ・ＺＰ＾４”を計算している。
【００９６】
（７）次に、レジスタＲ４とＲ４を加算し、加算結果をレジスタＲ７に格納する。同時に、レジスタＲ４とＲ８を加算し、加算結果をレジスタＲ５に格納する（図６，ステップ（７））。
【００９７】
（８）次に、レジスタＲ７とＲ５を加算し、加算結果の”３・ＸＰ＾２＋Ｗ［０］”をレジスタＲ５に格納する。同時に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ１に格納する（図６，ステップ（８））。このステップ（８）の処理は、レジスタＲ７とＲ５を加算することで、図５の演算式の”Ｍ［０］＝３・ＸＰ＾２＋Ｗ［０］”を計算している。
【００９８】
（９）次に、レジスタＲ５の平方算を計算し、計算結果をレジスタＲ４に格納する。同時に、レジスタＲ６の平方算を計算し、計算結果をレジスタＲ６に格納する（図６，ステップ（９））。
【００９９】
（１０）次に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ１に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図６，ステップ（１０））。このステップ（１０）の処理は、レジスタＲ１とＲ１の値を加算することで、図５の演算式の”Ｓ〔０〕＝４・ＸＰ・ＹＰ＾２”を計算している。
【０１００】
（１１）次に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ７に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図６，ステップ（１１））。
【０１０１】
（１２）次に、レジスタＲ４からＲ７を減算し、結果をレジスタＲ４に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図６，ステップ（１２））。このステップ（１２）の処理は、レジスタＲ４からＲ７を減算することで、図５の演算式の”Ｘ［１］＝Ｍ［０］＾２−２・Ｓ［０］を計算している。また、レジスタＲ６とＲ６を加算することで、図５の演算式の”Ｔ［０］＝８・ＹＰ＾４”を計算している。
【０１０２】
（１３）次に、レジスタＲ１からＲ４を減算し、結果をレジスタＲ１に格納する（図６，ステップ（１３））。
（１４）次に、レジスタＲ５に格納されている”Ｍ〔０〕”と、レジスタＲ１に格納されている”Ｓ〔０〕−Ｘ〔１〕”を乗算し、乗算結果をレジスタＲ１に格納する。同時に、レジスタＲ２の点ＰのＹ座標ＹＰとＲ３の点ＰのＺ座標ＺＰを乗算し、乗算結果をレジスタＲ２に格納する（図６，ステップ（１４））。
【０１０３】
（１５）次に、レジスタＲ１の”Ｍ〔０〕・（Ｓ〔０〕−Ｘ〔１〕）”からレジスタＲ６のＴ〔０〕を減算し、減算結果をレジスタＲ１に格納する。同時に、レジスタＲ２の”ＹＰ・ＺＰ”どうしを加算し、加算結果をレジスタＲ２に格納する（図６，ステップ（１５））。このステップ（１５）の処理は、レジスタＲ１からＲ６を減算することで、図５の演算式の”Ｙ〔１〕＝Ｍ［０］・（Ｓ［０］−Ｘ［０］）−Ｔ［０］”を計算している。同時に、レジスタＲ２とＲ２を加算することで、図５の演算式の”Ｚ〔１〕＝２・ＹＰ・ＺＰ”を計算している。
【０１０４】
以上の処理により、点Ｐの座標（ＸＰ，ＹＰ，ＺＰ）と、定数ａとから、Ｗ［０］、Ｍ［０］、Ｓ［０］、Ｔ［０］、Ｘ［１］、Ｙ［１］、Ｚ［１］を算出することができる。
（１６）次に、ｉを、１からｋ−１まで変化させて、ステップｂ１〜ｂ１１の処理を実行する（図６，ステップ（１６））。
【０１０５】
最初に、レジスタＲ４の平方算を計算し、計算結果をレジスタＲ３に格納する。同時に、レジスタＲ１の平方算を計算し、計算結果をレジスタＲ５に格納する（図６，ステップｂ１）。
【０１０６】
上述したステップ（１）〜（１５）の処理により、レジスタＲ４にはＸ［１］が、レジスタＲ１にはＹ［１］が格納されている。従って、変数ｉ＝１のときには、上記のステップｂ１の処理により、レジスタＲ３に”Ｘ［１］＾２”が格納され、レジスタＲ５に”Ｙ［１］＾２”が格納される。変数ｉを任意の値としたときには、ステップｂ１の処理により、レジスタＲ３に”Ｘ［ｉ］＾２”が格納され、レジスタＲ５に”Ｙ［ｉ］＾２”が格納される。
【０１０７】
次に、レジスタＲ４とＲ５を乗算し、乗算結果をレジスタＲ４に格納する。同時にレジスタＲ８とＲ６を乗算し、乗算結果をレジスタＲ８に格納する（図６，ステップｂ２）。
【０１０８】
上記のステップｂ２の処理により、変数ｉ＝１のときには、レジスタＲ４に”Ｘ［１］・Ｙ［１］＾２”が格納され、レジスタＲ８に”Ｔ［０］・Ｗ［０］”が格納される。変数ｉを任意の値としたときには、演算結果として”Ｘ［ｉ］・Ｙ［ｉ］＾２”が得られ、その演算結果がレジスタ４に格納される。また、演算結果として”Ｔ［ｉ−１］・Ｗ［ｉ−１］”が得られ、その演算結果がレジスタＲ８に格納される。
【０１０９】
次に、レジスタＲ８とＲ８とを加算し、加算結果をレジスタＲ８に格納する。
同時にレジスタＲ３とＲ３とを加算し、加算結果をレジスタＲ７に格納する（図６，ステップｂ３）。
【０１１０】
上記のステップｂ３の処理により、変数ｉ＝１のとき、レジスタＲ８とＲ８の加算結果として２・Ｔ［０］・Ｗ［０］が得られ、その演算結果がレジスタＲ６に格納される。また、変数ｉを任意の値とした、レジスタＲ８とＲ８の加算結果として”２・Ｔ［ｉ−１］・Ｗ［ｉ−１］”が得られ、その演算結果がレジスタＲ８に格納される。
【０１１１】
従って、上記のステップｂ３の処理により、図５の演算式のＳ３９の”Ｗ［ｉ］＝２・Ｔ［ｉ−１］・Ｗ［ｉ−１］”を計算することができる。
次に、レジスタＲ３とＲ７の値を加算し、加算結果をレジスタＲ６に格納する。同時に、レジスタＲ４とＲ４を加算し、加算結果をレジスタＲ４に格納する（図６，ステップｂ４）。
【０１１２】
次に、レジスタＲ８とＲ６を加算し、加算結果をレジスタＲ３に格納する。同時に、レジスタＲ４とＲ４を加算し、加算結果をレジスタＲ７に格納する（図６，ステップｂ５）。
【０１１３】
上記のステップｂ５の処理により、変数ｉを任意の値としたときに、レジスタＲ８とＲ６の加算結果として”３・Ｘ［ｉ］＾２＋Ｗ［ｉ］”が得られ、その結果がレジスタＲ３に格納される。また、レジスタＲ４とＲ４の加算結果として”４・Ｘ［ｉ］・Ｙ［ｉ］＾２”が得られ、その結果がレジスタＲ７に格納される。
【０１１４】
従って、上記のステップｂ５の処理により、図５の演算式のＳ４０の”Ｍ［ｉ］＝３・Ｘ［ｉ］＾２＋Ｗ［ｉ］”を計算することができる。また、図５の演算式のＳ４１の”Ｓ［ｉ］＝４・Ｘ［ｉ］・Ｙ［ｉ］＾２”を計算することができる。
【０１１５】
次に、レジスタＲ３の平方算を計算し、計算結果をレジスタＲ６に格納する。
同時にレジスタＲ５の平方算を計算し、計算結果をレジスタＲ５に格納する（図６，ステップｂ６）。
【０１１６】
次に、レジスタＲ５とＲ５を加算し、加算結果の”２・Ｙ〔ｉ〕＾２”をレジスタＲ５に格納する。同時に、レジスタＲ７とＲ７を加算し、加算結果の２・Ｓ〔ｉ〕をレジスタＲ４に格納する（図６，ステップｂ７）。
【０１１７】
次に、レジスタＲ５とＲ５を加算し、加算結果の”４・Ｙ〔ｉ〕＾２”をレジスタＲ５に格納する。同時に、レジスタＲ６からＲ４を減算し、結果をレジスタＲ４に格納する（図６，ステップｂ８）。
【０１１８】
上記のステップｂ８の処理により、変数ｉを任意の値としたときに、レジスタＲ６からＲ４を減算した結果として”Ｍ［ｉ］＾２−２・Ｓ［ｉ］が得られ、その結果がレジスタＲ４に格納される。
【０１１９】
従って、上記のステップｂ８の処理により、図５の演算式のＳ４３の”Ｘ［ｉ＋１］＝Ｍ［ｉ］＾２−２・Ｓ［ｉ］”を計算することができる。
次に、レジスタＲ５とＲ５と加算し、加算結果をレジスタＲ６に格納する。同時にレジスタＲ７からレジスタＲ４を減算し、結果をレジスタＲ７に格納する（図６，ステップｂ９）。
【０１２０】
上記のステップｂ９の処理により、変数ｉを任意の値としたときに、レジスタＲ５とＲ５の加算結果として”８・Ｙ［ｉ］＾４”が得られる。
従って、上記のステップｂ９の処理により、図５の演算式のＳ４２の”Ｔ［ｉ］＝８・Ｙ［ｉ］＾４”を計算することができる。
【０１２１】
次に、レジスタＲ３とＲ７を乗算し、乗算結果をレジスタＲ７に格納する。同時に、レジスタＲ１とＲ２とを乗算し、乗算結果をレジスタＲ２に格納する（図６，ステップｂ１０）。
【０１２２】
次に、レジスタＲ７からレジスタＲ６を減算し、結果をレジスタＲ１に格納する。同時に、レジスタＲ２とＲ２を加算し、加算結果をレジスタＲ２に格納する（図６，ステップｂ１１）。
【０１２３】
上記のステップｂ１１の処理により、レジスタＲ７に格納されている”Ｍ［ｉ］（Ｓ［ｉ］−Ｘ［ｉ＋１］）”から、レジスタＲ６に格納されている”Ｔ［ｉ］”が減算され、演算結果の”Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ＋１］）−Ｔ［ｉ］”がレジスタＲ１に格納される。また、レジスタＲ２に格納されている”Ｙ［ｉ］・Ｚ［ｉ］”どうしが加算され、演算結果の”２・Ｙ［ｉ］・Ｚ［ｉ］”がレジスタＲ２に格納される。
【０１２４】
従って、上記のステップｂ１１の処理により、図５の演算式のＳ４４の”Ｙ［ｉ＋１］＝Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ＋１］）−Ｔ［ｉ］”を計算することができる。また、図５の演算式のＳ４５の”Ｚ［ｉ＋１］＝２・Ｙ［ｉ］・Ｚ［ｉ］”を計算することができる。
【０１２５】
上記のステップｂ１〜ｂ１１の処理をｉ＝１からｋ−１まで繰り返すことで、レジスタＲ４，Ｒ１，Ｒ２に、楕円２＾ｋ倍算の点Ｒの座標が格納される。
（１７）次に、レジスタＲ４に格納されているＸ［ｋ］を点ＲのＸ座標ＸＲとして出力する（図６，ステップ（１７））。
（１８）次に、レジスタＲ１に格納されているＹ［ｋ］を点ＲのＹ座標ＹＲとして出力する（図６，ステップ（１８））。
（１９）次に、レジスタＲ２に格納されているＺ［ｋ］を点ＲのＺ座標ＺＲとして出力する（図６，ステップ（１９））。
【０１２６】
上述した処理により楕円２＾ｋ倍算により得られる点Ｒの座標（ＸＲ，ＹＲ，ＺＲ）を計算することができる。
上述した第３の実施の形態によれば、スカラー倍算の演算において、ｄ［ｉ］が連続して０」となる回数ｋを予め計算し、楕円２＾ｋ倍算の計算を行うことで楕円２倍算を繰り返し実行する場合に比べて計算時間を短縮することができる。
【０１２７】
また、第３の実施の形態の演算プログラムによれば、楕円２＾ｋ倍算の同じ種類の演算を並列に実行することで、２×ｋ回の乗算と、（２×ｋ＋１）回の平方算と、７×ｋ回の加減算とにより、点ＲのＸ座標とＹ座標とＺ座標を計算することができるので、楕円２＾ｋ倍算の演算時間を短縮できる。
【０１２８】
ここで、上述した実施の形態のスカラー倍算の演算プログラムを実行する楕円曲線暗号装置のハードウェア構成の一例を図７を参照して説明する。楕円暗号装置は、例えば、パーソナルコンピュータ等の情報処理装置により実現できる。
【０１２９】
ＣＰＵ２１は、ＳＩＭＤ機能を有し、楕円曲線暗号の楕円加算、楕円２倍算等の演算の中で同じ種類の演算を並列に実行する。メモリ２２は、演算に使用される各種のレジスタとして使用される。外部記憶装置２３は、ＯＳや、楕円曲線暗号の演算プログラム等が格納される。
【０１３０】
媒体駆動装置２４は、ＣＤＲＯＭ、ＤＶＤ、フレキシブルディスク、ＩＣカード等の可搬記録媒体２５の読み取り、あるいは書き込みを行う装置である。
入力装置２６は、キーボード等のデータを入力する装置である。出力装置２７は、ディスプレイ、プリンタ等の装置である。ネットワーク接続装置２８は、インターネット等のネットワークに接続するための装置であり、この装置を介してネットワーク上のサーバからプログラムをダウンロードすることができる。なお、ＣＰＵ２１，メモリ２２，外部記憶装置２３，入装置２６等はバス２９により接続されている。
【０１３１】
本発明は、楕円曲線暗号の暗号化及び解読を行う専用の装置に限らず、ＩＣカード、ＤＶＤ装置、携帯電話機、パーソナルコンピュータ等の種々の製品に適用できる。
【０１３２】
また、本発明は、ヤコビアン座標に限らず他の座標系にも適用できる。さらに、スカラー倍算の演算アルゴリズムは、図４、あるいは図１０のアルゴリズムに限らず他の演算アルゴリズムを用いても良い。
【０１３３】
（付記１）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑと楕円２＾ｋ（＾：べき乗を表す、ｋ＝１以上の整数）倍算の演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された演算プログラムの楕円加算の同じ種類の演算を並列に実行するとともに、楕円２＾ｋ倍算の同じ種類の演算を並列に実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【０１３４】
（付記２）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
楕円曲線上の点Ｐと点Ｑのヤコビアン座標における座標を、それぞれ（ＸＰ，ＹＰ，ＺＰ）、（ＸＱ，ＹＱ，ＺＱ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑの演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された楕円加算の演算プログラムの同じ種類の演算を並列に実行して楕円加算Ｐ＋Ｑ＝Ｒの点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える楕円曲線暗号装置。
【０１３５】
（付記３）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
楕円曲線上の点Ｐのヤコビアン座標における座標を（ＸＰ，ＹＰ，ＺＰ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円２倍算２×Ｐの演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された楕円２倍算の演算プログラムの同じ種類の演算を並列に実行して楕円２倍算２×Ｐ＝Ｒの点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える楕円曲線暗号装置。
【０１３６】
（付記４）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
楕円曲線上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された楕円２＾ｋ倍算の演算プログラムの同じ種類の演算を並列に実行して楕円２＾ｋ倍算により得られる点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える楕円曲線暗号装置。
【０１３７】
（付記５）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、
係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の同じ種類の演算を並列に実行する楕円曲線暗号演算方法。
【０１３８】
（付記６）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算プログラムにおいて、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑと楕円２＾ｋ（＾：べき乗を表す、ｋ＝１以上の整数）倍算の演算プログラムを記憶部に記憶させ、
前記記憶部に記憶された演算プログラムの楕円加算の同じ種類の演算を並列に実行するとともに、楕円２＾ｋ倍算の同じ種類の演算を並列に実行してスカラー倍算ｄ×Ｐを計算する楕円曲線暗号演算プログラム。
【０１３９】
（付記７）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑと楕円２＾ｋ（＾：べき乗を表す、ｋ＝１以上の整数）倍算の演算プログラムを記憶部に記憶し、
前記記憶部に記憶された演算プログラムの楕円加算の同じ種類の演算を並列に実行するとともに、楕円２倍算の同じ種類の演算を並列に実行してスカラー倍算ｄ×Ｐを計算する楕円曲線暗号演算方法。
【０１４０】
（付記８）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑと楕円２倍算と楕円２＾ｋ倍算（＾：べき乗を表す，ｋ＝２以上の整数）の演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された演算プログラムの楕円加算の同じ種類の演算、楕円２倍算の同じ種類の演算及び楕円２＾ｋ倍算の同じ種類の演算を、それぞれ並列に実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【０１４１】
（付記９） 付記２記載の楕円曲線暗号装置において、
前記演算手段は、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）と、点Ｑの座標（ＸＱ，ＹＱ，ＺＱ）とに基づいて楕円加算の演算プログラムの同じ種類の演算を並列に実行する。
【０１４２】
（付記１０）付記４記載の楕円曲線暗号装置において、
前記演算手段は、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）に基づいて楕円２＾ｋ倍算の演算プログラムの同じ種類の演算を並列に実行する。
【０１４３】
（付記１１）付記１記載の楕円曲線暗号装置において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
前記演算手段は、係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ倍算の同じ種類の演算を並列に実行する。
【０１４４】
（付記１２）付記４記載の楕円曲線暗号装置において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
前記演算手段は、係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ倍算の同じ種類の演算を並列に実行する。
【０１４５】
（付記１３）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号プログラムにおいて、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように楕円加算Ｐ＋Ｑと楕円２倍算の演算プログラムを作成し、
前記楕円加算の同じ種類の演算と、前記楕円２倍算の同じ種類の演算を、それぞれ並列に実行してスカラー倍算ｄ×Ｐを計算する楕円曲線暗号演算プログラム。
【０１４６】
（付記１４）楕円加算、楕円２倍算または楕円２＾ｋ倍算の演算を行う演算手段が、演算命令及び複数のデータを記憶するレジスタ群と、演算器とを備え、前記レジスタ群に記憶された楕円加算、楕円２倍算または楕円２＾ｋ倍算の同じ種類の演算で異なるデータに対する演算を前記演算器が並列に実行する。
【０１４７】
（付記１５）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、
係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の計算を行う楕円曲線暗号演算方法。
【０１４８】
【発明の効果】
本発明によれば、楕円加算の演算において同じ種類の演算で異なるデータに対する演算を並列に実行することでスカラー倍算の計算時間を短縮することができる。また、楕円２倍算の演算において同じ種類の演算を並列に実行することでスカラー倍算の計算時間を短縮できる。さらに、楕円２＾ｋ倍算の演算において同じ種類の演算を並列に実行することでスカラー倍算の計算時間を短縮できる。また、２進展開の係数ｄ［ｉ］が連続して「０」となる回数に基づいて楕円２＾ｋ倍算の同じ種類の演算を並列に実行することで楕円２＾ｋ倍算の計算時間を短縮できる。
【図面の簡単な説明】
【図１】実施の形態の楕円曲線暗号装置の要部の構成を示す図である。
【図２】第１の実施の形態の楕円加算の演算プログラムを示す図である。
【図３】第２の実施の形態の楕円２倍算の演算プログラムを示す図である。
【図４】楕円２＾ｋ倍算を用いたスカラー倍算の演算プログラムを示す図である。
【図５】楕円２＾ｋ倍算の演算式を示す図である。
【図６】第３の実施の形態の楕円２＾ｋ倍算の演算プログラムを示す図である。
【図７】実施の形態の情報処理装置のハードウェア構成図である。
【図８】楕円加算の説明図である。
【図９】楕円２倍算の説明図である。
【図１０】スカラー倍算の演算プログラムを示す図である。
【符号の説明】
１１ 楕円曲線暗号装置
１２ 演算部
１３ 演算器
１４ レジスタ群
１５ 記憶部
２１ ＣＰＵ
２２ メモリ
２３ 外部記憶装置
２４ 媒体駆動装置
２５ 可搬記録媒体
２６ 入力装置
２７ 出力装置
２８ ネットワーク接続装置
２９ バス
【発明の属する技術分野】
本発明は、楕円曲線暗号装置、楕円曲線暗号演算方法及び楕円曲線暗号プログラムに関する。
【０００２】
【従来の技術】
楕円曲線暗号は公開鍵暗号の１つであり、文書の暗号復号化、署名、認証などの用途に使用される。
【０００３】
楕円曲線暗号はＥＣＥＳ(Elliptic Curves Encryption Standard)暗号、ＥＣＡＥＳ(Elliptic CurvesAdvanced Encryption Standard)暗号、ＥＣＤＳＡ(Elliptic Curves Digital SignatureAlgorithm)署名、ＥＣＤＨ(Elliptic Curves Diffie-Hellmmn)秘密共有といった、いくつかの暗号プリミティブから構成されているが、点のスカラー倍算と呼ばれる演算はすべての暗号プリミティブに共通して使用され、かつ暗号処理の中心となるものである。このことから、楕円曲線暗号におけるスカラー倍演算の高速化を実現する技術は必要不可欠となっている。
【０００４】
楕円曲線暗号の例としてＥＣＥＳ暗号プリミティブを説明する。送信者Ａは秘密鍵ｓ（ｓは整数）を持ち、受信者Ｂが秘密鍵ｔ（ｔは整数）を持つ場合に、楕円曲線Ｅと、楕円曲線Ｅ上に設定されるベースポイントＰ（ｘ，ｙ）と、公開鍵ｓ×Ｐ（送信者Ａの秘密鍵ｓとベースポイントＰとのスカラー倍算）と、公開鍵ｔ×Ｐ（送信者Ｂの秘密鍵ｔとベースポイントＰとのスカラー倍算）があらかじめ公開されている。このとき送信者Ａは、自分の秘密鍵ｓと、受信者Ｂの公開鍵ｔ×Ｐとのスカラー倍算ｓ×（ｔ×Ｐ）を計算し、そのｘ座標のビット表現を求め、このビット表現とメッセージのビット表現との間でビット対応のＥＯＲ演算を施すことで、メッセージｍに対する暗号文Ｃを生成し、それを受信者Ｂに送信する。受信者Ｂは、自分の秘密鍵ｔと、送信者Ａの公開鍵ｓ×Ｐとのスカラー倍算ｔ×（ｓ×Ｐ）を計算し、そのｘ座標のビット表現を求める。そして、”ｓ×（ｔ×Ｐ）＝ｔ×（ｓ×Ｐ）”という関係式が成立することを考慮して、そのビット表現と暗号文Ｃのビット表現との間でビット対応のＥＯＲ演算を施すことで、暗号文Ｃを復号し、メッセージｍを得る。このようにして、ＥＣＥＳ暗号と呼ばれる楕円曲線暗号のプリミティブでは、スカラー倍演算を用いて暗号・復号処理を行う。
【０００５】
ここで、ｐが５以上の素数、ｍを１以上の整数とすると、要素数ｐ＾ｍ（＾：べき乗を表す）の有限体ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線は、方程式
E：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる点∞を加えた集合である。無限遠点∞を０と表すこともある。ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ＾ｍ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。楕円曲線上の点は（ｘ，ｙ）のような座標形式で表現できるが、無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない唯一の点である。
【０００６】
ＰをＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の点とする。
以下のようにしてＰの逆元−Ｐ定義する。
（１）Ｐ＝∞ならば−Ｐ＝∞
（２）Ｐ≠∞ならばＰ＝（ｘ，ｙ）としたときに、−Ｐ＝（ｘ，−ｙ）
Ｐ１，Ｐ２をＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の２点とする。以下のようにしてＰ１とＰ２の和Ｐ３＝Ｐ１＋Ｐ２を定義する。
（１）Ｐ１＝∞ならばＰ３＝Ｐ２
（２）Ｐ２＝∞ならばＰ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならばＰ３＝∞
（４）Ｐ１≠−Ｐ２ならばＰ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２−ｘ１−ｘ２， ｙ３＝λ×（ｘ１−ｘ３）−ｙ１，
ただし
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１） ：Ｐ１≠Ｐ２のとき
λ＝（３×ｘ１＾２＋ａ）／（２×ｙ１） ：Ｐ１＝Ｐ２のとき
Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算ＥＣＡＤＤ、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算ＥＣＤＢＬと呼ぶ。
【０００７】
楕円加算と楕円２倍算は、有限体ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組合せによって計算される。
図８及び図９は、楕円加算と楕円２倍算の説明図である。楕円加算は、図８に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）とＰ２＝（ｘ２，ｙ２）とを結ぶ直線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ３＝Ｐ１＋Ｐ２＝（ｘ３，ｙ３）として定義される。
【０００８】
楕円２倍算は、図９に示されるように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）の接線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ４＝２×Ｐ１＝（ｘ４，ｙ４）として定義される。
【０００９】
有限体上の楕円曲線Ｅと、曲線上の点Ｐと、整数（スカラーとも呼ぶ）ｄに対して、点ｄ×Ｐ＝Ｐ＋Ｐ＋…Ｐ（ｄ個の和）を計算することをスカラー倍算という。スカラー倍算は、楕円加算と楕円２倍算と楕円２＾ｋ倍算との組合せによって実現することができる。
【００１０】
楕円加算、楕円２倍算、楕円２＾ｋ倍算からなるスカラー倍算の計算時間は、ＧＦ（ｐ＾ｍ）での乗算、平方算、逆元計算の計算時間の和によって見積もられることが多い。これは実際の楕円加算、楕円２倍算、楕円２＾ｋ倍算からなるスカラー倍算の計算が、ＧＦ（ｐ＾ｍ）での加減算・乗算・平方算・逆元計算の組合せで計算され、多くの場合、加減算の計算時間はその他の計算時間に比べて無視できるほど短いからである。
【００１１】
一般にＧＦ（ｐ＾ｍ）での逆元計算の計算時間は、乗算・平方算の計算時間に比べて非常に大きくなる。このため実際のスカラー倍算では、楕円曲線の点を表現する上でヤコビアン座標が使用されることがある。ヤコビアン座標では、点は（Ｘ，Ｙ，Ｚ）のような素体の３つの要素の組合せで表される。ただし（Ｘ，Ｙ，Ｚ）とｒ≠０であるＧＦ（ｐ＾ｍ）の要素ｒに対し（ｒ＾２×Ｘ：ｒ＾３×Ｙ：ｒ×Ｚ）は同じ点と考える。楕円曲線はヤコビアン座標では、ｘ＝Ｘ／Ｚ＾２，ｙ＝Ｙ／Ｚ＾３を代入して、
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３
となる。ヤコビアン座標を用いると、楕円曲線上の点は（Ｘ，Ｙ，Ｚ）のような座標形式で表現することができる。無限遠点は∞＝（０，１，０）となる。
【００１２】
楕円曲線におけるスカラー倍計算は楕円加算（ＥＣＡＤＤ）と楕円２倍算（ＥＣＤＢＬ）と楕円２＾ｋ倍算と呼ばれる演算の組合せで実現されるため、全体の計算時間はこれら演算の計算回数として評価される。スカラー倍算ｄ×Ｐの計算は、ｄの２進展開
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ［ｎ−２］×２＾（ｎ−２）＋・・・＋ｄ［１］×２＋ｄ［０］
を利用して行われる。
【００１３】
図１０は、従来のスカラー倍算のアルゴリズムに基づくの演算プログラムを示す図である。
図１０において、ステップＳ１で変数Ｑ［０］の初期値をＰとし、ステップＳ３で点Ｑ［０］の楕円２倍算を実行し、演算結果をＱ［０］に格納する。そしてｄ［ｉ］＝＝１であれば、ステップＳ５で、Ｑ［０］と点Ｐの楕円加算を実行し、演算結果をＱ［０］に格納する。ステップＳ３〜Ｓ５の処理をｉ＝ｎ−２から０まで実行する。楕円２倍算が連続して計算される場合には、楕円２＾ｋ倍算が適用可能である。
【００１４】
スカラー倍算の演算を高速化する方法は、種々の検討が行われており、ヤコビアン座標を用いた楕円曲線暗号の演算方法については、例えば、特開２０００−１３７４３６号公報に記載されている。
【００１５】
【特許文献１】
特開２０００−１３７４３６号公報（段落００２１）
【００１６】
【発明が解決しようとする課題】
楕円曲線暗号が現実社会において広く用いられるためには、処理時間及び実装上必要となるリソース（メモリ・回路量等）の低減が求められる。楕円曲線暗号ではスカラー倍算と呼ばれる演算が共通して使用され、暗号処理全体における比重も高いため、この部分の性能向上が暗号全体の性能向上に直結する。楕円曲線暗号処理においてスカラー倍算アルゴリズムの比重は高いため、さらなる高速化が望まれている。
【００１７】
本発明の課題は、楕円曲線暗号のスカラー倍算を高速に計算することである。
【００１８】
【課題を解決するための手段】
本発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、整数ｄの２進展開の係数ｄ〔ｉ〕（ｄ［ｉ］＝０，１）が連続して０となる回数ｋの計算結果を記憶するレジスタと、楕円曲線上の点Ｐのヤコビアン座標をＰ（ＸＰ、ＹＰ、ＺＰ）とし、ｉ＝０のときのＷ［ｉ］、Ｍ［ｉ］、Ｓ［ｉ］、Ｔ［ｉ］を、Ｗ［０］＝ａ・ＺＰ４、Ｍ［０］＝３・ＸＰ２＋Ｗ［０］、Ｓ［０］＝４・ＸＰ・ＹＰ２、Ｔ［０］＝８・ＹＰ４、とし、ｋ＝１の点のＸ、Ｙ、Ｚ座標を、Ｘ［１］＝Ｍ［０］２−２・Ｓ［０］、Ｙ［１］＝Ｍ［０］・（Ｓ［０］−Ｘ［１］）−Ｔ［０］、Ｚ［１］＝２・ＹＰ・ＺＰ、から算出し、（１）Ｗ［ｉ］＝２・Ｔ［ｉ−１］・Ｗ［ｉ−１］、（２）Ｍ［ｉ］＝３・Ｘ［ｉ］２＋Ｗ［ｉ］、（３）Ｓ［ｉ］＝４・Ｘ［ｉ］・Ｙ［ｉ］２
（４）Ｔ［ｉ］＝８・Ｙ［ｉ］４、（５）Ｘ［ｉ＋１］＝Ｍ［ｉ］２−２・Ｓ［ｉ］、（６）Ｙ［ｉ＋１］＝Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ−１］）−Ｔ［ｉ］、（７）Ｚ［ｉ＋１］＝２・Ｙ［ｉ］・Ｚ［ｉ］、前記レジスタに格納されている値ｋに基づいて変数ｉを１からｋ−１まで変化させて、上記（１）〜（７）の演算を行って楕円２ｋ倍算の演算を実行する際に、同じ種類の演算を並列に実行する演算手段とを備える。
【００１９】
この発明によれば、楕円加算の同じ種類の演算で異なるデータに対する演算を並列に実行し、さらに楕円２＾ｋ倍算の同じ種類の演算で異なるデータに対する演算を並列に実行することにより楕円加算と楕円２＾ｋ倍算の計算時間を短縮することができる。これにより、スカラー倍算の計算時間を短縮できる。
【００２０】
他の発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、楕円曲線上の点Ｐと点Ｑのヤコビアン座標における座標を、それぞれ（ＸＰ，ＹＰ，ＺＰ）、（ＸＱ，ＹＱ，ＺＱ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑの演算プログラムを記憶する記憶手段と、前記記憶手段に記憶されている楕円加算Ｐ＋Ｑの演算プログラムの同じ種類の演算を並列に実行して楕円加算Ｐ＋Ｑ＝Ｒの点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える。
【００２１】
この発明によれば、楕円加算の演算の中で同じ種類の演算を並列に実行することで楕円加算の計算時間を短縮できる。
他の発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、楕円曲線上の点Ｐのヤコビアン座標における座標を（ＸＰ，ＹＰ，ＺＰ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円２倍算２×Ｐの演算プログラムを記憶する記憶手段と、前記記憶手段に記憶されている楕円２倍算２×Ｐの演算プログラムの同じ種類の演算を並列に実行して楕円２倍算２×Ｐ＝Ｒの点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える。
【００２２】
この発明によれば、楕円２倍算の演算の中で同じ種類の演算を並列に実行することで楕円２倍算の計算時間を短縮できる。
他の発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、楕円曲線上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の演算プログラムを記憶する記憶手段と、前記記憶手段に記憶されている楕円２＾ｋ倍算の演算プログラムの同じ種類の演算を並列に実行して楕円２＾ｋ倍算により得られる点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える。
【００２３】
この発明によれば、楕円２＾ｋ倍算の演算の中で同じ種類の演算を並列に実行することで楕円２＾ｋ倍算の計算時間を短縮できる。
他の発明は、整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、整数ｄの２進展開の係数ｄ［ｄ］（ｄ［ｉ］＝０，１）とし、係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、計算結果をレジスタに格納し、レジスタに格納されている、係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の同じ種類の演算を並列に実行する。
【００２４】
この発明によれば、整数ｄの２進展開の係数ｄ［ｉ］が連続して「０」となる回数が２以上のとき、楕円２＾ｋ（ｋ＝２以上）倍算の同じ種類の演算を並列に実行することで、楕円２倍算を繰り返し実行する場合に比べて計算時間を短縮できる。
【００２５】
上記の発明において、前記演算手段は、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）と、点Ｑの座標（ＸＱ，ＹＱ，ＺＱ）とに基づいて楕円加算の演算プログラムの同じ種類の演算を並列に実行するようにしても良い。
【００２６】
また、前記演算手段は、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）に基づいて楕円２＾ｋ倍算の演算プログラムの同じ種類の演算を並列に実行するようにしても良い。
【００２７】
このように構成することで、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点の楕円加算または楕円２＾ｋ倍算の演算時間を短縮できる。
ヤコビアン座標を用いて楕円２＾ｋ倍算の計算を行う楕円曲線暗号装置において、整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、前記演算手段は、係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ倍算の同じ種類の演算を並列に実行する。
【００２８】
楕円加算、楕円２倍算、あるいは楕円２＾ｋ倍算の演算を行う演算手段が、演算命令及び複数のデータを記憶するレジスタ群と、演算器とを備え、前記レジスタ群に記憶された同じ種類の演算で異なるデータに対する演算を、前記演算器が並列に実行するようにしても良い。
【００２９】
このように構成することで、レジスタ群に記憶された楕円加算、楕円２倍算または楕円２＾ｋ倍算の同じ種類の演算を並列に実行して演算時間を短縮することができる。
【００３０】
なお、楕円加算、楕円２倍算、あるいは楕円２＾ｋ倍算の演算プログラムを記憶する記憶手段は、図１の記憶部１７に対応し、演算手段は、図１の演算部１２または演算器１３に対応する。
【００３１】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照しながら説明する。実施の形態の楕円曲線暗号装置は、例えば、楕円曲線暗号の専用の情報処理装置、パーソナルコンピュータ、ＩＣカード等に内蔵されたＩＣチップ、携帯電話機、携帯情報端末装置（ＰＤＡなど）、ＤＶＤプレーヤ等からなり、ＳＩＭＤ（Single Instruction stream Multiple Data stream）機能、すなわち同じ種類の命令で異なるデータに対する処理を並列に実行する機能を有している。
【００３２】
以下の説明では、本発明に係る楕円曲線暗号演算方法を、ｐを５以上の素数とし、要素数ｐの有限体ＧＦ（ｐ）（ｐは５以上の素数）上の楕円曲線に適用した場合について説明する。
【００３３】
ＧＦ（ｐ）上の楕円曲線Ｅは、以下の式で表せる。
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
ここでａ，ｂ，ｘ，ｙはＧＦ（ｐ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。
【００３４】
図１は、本発明に係る楕円曲線暗号装置１１の要部の構成を示す図である。実施の形態の楕円曲線暗号装置１１の演算部（プロセッサ）１２は、演算器１３と、複数のレジスタからなるレジスタ群１４とからなる。
【００３５】
記憶部１５には、後述する楕円曲線暗号の楕円加算、楕円２倍算、楕円２＾ｋ倍算等の演算プログラムが記憶される。
演算部１２は、演算を実行する際に、複数のレジスタに格納されている同じ演算種別で異なるデータに対する演算を演算器１３を使用して並列に実行する。
【００３６】
次に、図２は、ヤコビアン座標を用いて楕円加算Ｐ＋Ｑの同じ種類の演算を並列に実行する本発明の第１の実施の形態の演算プログラムを示す図である。
図２に示す楕円加算の演算プログラムは、ヤコビアン座標における点Ｐの座標ＸＰ，ＹＰ，ＺＰ）と、点Ｑの座標（ＸＱ，ＹＱ，ＺＱ）を入力して、楕円加算Ｐ＋Ｑ＝Ｒの点Ｒの座標（ＺＲ，ＹＲ，ＺＲ）を並列計算により計算するものである。
【００３７】
（１）演算部（プロセッサ）１２が、点ＰのＸ座標ＸＰをレジスタ（またはメモリ）Ｒ１に設定する（図２のステップ（１））。
（２）演算部１２が、点ＰのＹ座標ＹＰをレジスタＲ２に設定する（図２のステップ（２））。
【００３８】
（３）点ＰのＺ座標ＺＰをレジスタＲ３に設定する（図２，ステップ（３））。
（４）点ＱのＸ座標ＸＱをレジスタＲ４に設定する（図２，ステップ（４））。
【００３９】
（５）点ＱのＹ座標ＹＱをレジスタＲ５に設定する（図２、ステップ（５））。
（６）点ＱのＺ座標ＺＱをレジスタＲ６に設定する（図２、ステップ（６））。
【００４０】
（７）次に、レジスタＲ３の平方算、すなわち点ＰのＺ座標ＺＰの２乗を求め、演算結果をレジスタＲ７に格納する。その演算と並列に、レジスタＲ６の平方算、すなわち点ＱのＺ座標ＺＱの２乗を求め、演算結果をレジスタＲ８に格納する（図２、ステップ（７））。この場合、同じ平方算の演算であるので、レジスタＲ３の値を２乗する演算と、レジスタＲ６の値を２乗する演算を演算部１２が並列に実行する。
【００４１】
（８）次に、レジスタＲ４とレジスタＲ７を乗算し、乗算結果をレジスタＲ４に格納する。同時に、レジスタＲ１とレジスタＲ８を乗算し、乗算結果をレジスタＲ１に格納する（図２，ステップ（８））。すなわち、点ＱのＸ座標ＸＱとレジスタＲ７に格納されている”ＺＰ＾２”を乗算し、乗算結果をレジスタＲ４に格納する。同時に、レジスタＲ１の点ＰのＸ座標ＸＰとレジスタＲ８に格納されている”ＺＱ＾２”を乗算し、乗算結果をレジスタＲ１に格納する。この場合も、同じ乗算の演算であるので、演算部１２は、レジスタＲ４とＲ７の乗算と、レジスタＲ１とＲ８の乗算を並列に実行する。
【００４２】
（９）次に、レジスタＲ２とレジスタＲ６を乗算し、乗算結果をレジスタＲ２に格納する。同時に、レジスタＲ３とレジスタＲ５を乗算し、乗算結果をレジスタＲ５に格納する（図２，ステップ（９））。すなわち、レジスタＲ２に格納されている点ＰのＹ座標ＹＰと、レジスタＲ６に格納されている点ＱのＺ座標ＺＱを乗算し、乗算結果をレジスタＲ２に格納する。同時に、レジスタＲ３に格納されている点ＰのＺ座標ＺＰと、レジスタＲ５に格納されている点ＱのＹ座標ＹＱを乗算し、乗算結果をレジスタＲ５に格納する。この場合も、同じ乗算の演算であるので、レジスタＲ２とＲ６の乗算と、レジスタＲ３とＲ５の乗算を演算部１２が並列に実行する。
【００４３】
（１０）上記ステップ（９）で計算したレジスタＲ２の値と、ステップ（７）で計算したレジスタＲ８の”ＺＱ＾２”を乗算し、乗算結果をレジスタＲ８に格納する。同時に、上記ステップ（９）で計算したレジスタＲ５の値と、ステップ（７）で計算したレジスタＲ７の”ＺＰ＾２”を乗算し、乗算結果をレジスタＲ７に格納する（図２，ステップ（１０））。
【００４４】
（１１）次に、レジスタＲ４からレジスタＲ１を減算し、減算結果をレジスタＲ２に格納する。同時に、レジスタＲ７からレジスタＲ８を減算し、減算結果をレジスタＲ８に格納する（図２，ステップ（１１））。すなわち、ステップ（８）で計算したレジスタＲ４の値から、ステップ（８）で計算したレジスタＲ１の値を減算し、結果をレジスタＲ２に格納する。同時に、ステップ（１０）で計算したレジスタＲ７の値から、ステップ（１０）で計算したレジスタＲ８の値を減算し、結果をレジスタＲ５に格納する。
【００４５】
（１２）次に、レジスタＲ２の平方算、すなわち、ステップ（１１）で計算したレジスタＲ２の値の２乗を計算し、計算結果をレジスタＲ７に格納する。同時に、レジスタＲ５の平方算、すなわち、ステップ（１１）で計算したレジスタＲ５の値の２乗を計算し、計算結果をレジスタＲ４に格納する（図２，ステップ（１２））。
【００４６】
（１３）次に、レジスタＲ１とＲ７を乗算し、乗算結果をレジスタＲ１に格納する。同時に、レジスタＲ２とＲ７を乗算し、乗算結果をレジスタＲ７に格納する（図２，ステップ（１３））。すなわち、ステップ（８）で計算したレジスタＲ１と、ステップ（１２）で計算したレジスタＲ７を乗算し、乗算結果をレジスタＲ１に格納する。同時に、ステップ（１１）で計算したレジスタＲ２と、ステップ（１２）で計算したレジスタＲ７を乗算し、乗算結果をレジスタＲ７に格納する。
【００４７】
（１４）次に、レジスタＲ８とＲ７を乗算し、乗算結果をレジスタＲ８に格納する。同時に、レジスタＲ３とＲ６を乗算し、乗算結果をレジスタＲ３に格納する（図２，ステップ（１４））。すなわち、ステップ（１０）で計算したレジスタＲ８と、ステップ（１３）で計算したレジスタＲ７を乗算し、結果をレジスタＲ８に格納する。また、レジスタＲ３に格納されている点ＰのＺ座標ＺＰと、レジスタＲ６に格納されている点ＱのＺ座標ＺＱを乗算し、結果をレジスタＲ３に格納する。
【００４８】
（１５）次に、レジスタＲ４からレジスタＲ７を減算し、結果をレジスタＲ４に格納する。同時に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ６に格納する（図２，ステップ（１５））。
【００４９】
（１６）次に、レジスタＲ４からレジスタＲ６を減算し、結果をレジスタＲ４に格納する（図２，ステップ（１６））。すなわち、ステップ（１５）で計算したレジスタＲ４の値から、ステップ（１５）で計算したレジスタＲ６の値を減算し、結果をレジスタ４に格納する。
【００５０】
（１７）次に、レジスタＲ１からレジスタＲ４を減算し、結果をレジスタＲ１に格納する（図２，ステップ（１７））。すなわち、ステップ（１３）で計算したレジスタＲ１の値から、ステップ（１６）で計算したレジスタＲ４の値を減算し、結果をレジスタＲ１に格納する。
【００５１】
（１８）次に、レジスタＲ５とＲ１を乗算し、乗算結果をレジスタＲ５に格納する。同時に、レジスタＲ３とＲ２を乗算し、乗算結果をレジスタＲ３に格納する（図２，ステップ（１８））。すなわち、ステップ（１１）で計算したレジスタＲ５と、ステップ（１７）で計算したレジスタＲ１とを乗算し、結果をレジスタＲ５に格納する。同時に、ステップ（１４）で計算したレジスタＲ３と、ステップ（１１）で計算したレジスタＲ２を乗算し、結果をレジスタＲ３に格納する。
【００５２】
（１９）次に、レジスタＲ５からレジスタＲ８を減算し、結果をレジスタＲ７に格納する（図２，ステップ（１９））。すなわち、ステップ（１８）で計算したレジスタＲ５から、ステップ（１４）で計算したレジスタＲ８を減算し、結果をレジスタＲ７に格納する。
【００５３】
以上の処理により、レジスタＲ４，Ｒ７，Ｒ３に楕円加算Ｐ＋Ｑ＝Ｒの点Ｒのヤコビアン座標のＸ座標、Ｙ座標、Ｚ座標が格納される。
（２０）次に、レジスタＲ４に格納されている値を、点ＲのＸ座標ＸＲとして出力する（図２，ステップ（２０））。
【００５４】
（２１）レジスタＲ７に格納されている値を、点ＲのＹ座標ＹＲとして出力する（図２，ステップ（２１））。
（２２）レジスタＲ３に格納されている値を、点ＲのＺ座標ＺＲとして出力する（図２，ステップ（２２））。
【００５５】
上述した処理により、ヤコビアン座標において、点Ｐと点Ｑの楕円加算Ｐ＋Ｑ＝Ｒにより得られる点Ｒの座標（ＸＲ，ＹＲ，ＺＲ）を求めることができる。
上述した第１の実施の形態は、楕円加算Ｐ＋Ｑの同じ種類の演算を演算部１２が並列に実行できるように演算プログラムを作成し、演算部１２が同じ種類の演算を並列に実行することで、６回の乗算と、２回の平方算と、５回の加減算とにより楕円加算の計算を行うことができる。これにより楕円加算の計算時間、すなわち、スカラー倍算の計算時間を短縮できる。
【００５６】
次に、図３は、ヤコビアン座標を用いて楕円２倍算２×Ｐの同じ種類の演算を並列に実行する本発明の第２の実施の形態の演算プログラムを示す図である。
この演算プログラムは、ヤコビアン座標における点Ｐの座標（ＸＰ，ＹＰ，ＺＰ）を取得して、楕円２倍算２×Ｐにより得られる点Ｒの座標（ＸＲ，ＹＲ，ＺＲ）を並列計算により求めるものである。
【００５７】
（１）点ＰのＸ座標ＸＰをレジスタ（またはメモリ）Ｒ１に設定する（図３，ステップ（１））。
（２）点ＰのＹ座標ＹＰをレジスタＲ２に設定する（図３，ステップ（２））。
【００５８】
（３）点ＰのＺ座標ＺＰをレジスタＲ３に設定する（図３，ステップ（３））。
（４）次に、レジスタＲ１の平方算、すなわち、点ＰのＸ座標ＸＰの２乗を計算し、計算結果をレジスタＲ４に格納する。同時に、レジスタＲ３の平方算、すなわち点ＰのＺ座標ＺＰの２乗を計算し、計算結果をレジスタＲ５に格納する（図３，ステップ（４））。この場合、同じ平方算であるのでレジスタＲ１に対する平方算と、レジスタＲ３に対する平方算を、演算部１２が並列に実行することができる。
【００５９】
（５）次に、レジスタＲ２の平方算、すなわちレジスタＲ２に格納されている点ＰのＹ座標ＹＰの２乗を計算し、計算結果をレジスタＲ６に格納する。同時に、レジスタＲ５の平方算、すなわちレジスタＲ５に格納されているＺＰ＾２の２乗を計算し、計算結果をレジスタＲ５に格納する（図３，ステップ（５））。
【００６０】
（６）次に、レジスタＲ１とＲ６を乗算し、乗算結果をレジスタＲ１に格納する。同時に定数ａとレジスタＲ５を乗算し、乗算結果をレジスタＲ５に格納する（図３，ステップ（６））。すなわち、レジスタＲ１に格納されているＸ座標ＸＰと、レジスタＲ６に格納されているＹＰ＾２を乗算し、乗算結果をレジスタＲ１に格納する。また、定数ａとレジスタＲ５に格納されているＺＰ＾４を乗算し、乗算結果の”ａ・ＺＰ＾４”をレジスタＲ５に格納する。この処理により、レジスタＲ５には”ａ・ＺＰ＾４”が格納される。ここで、”Ｗ［０］＝ａ・ＺＰ＾４”とする。
【００６１】
（７）次に、レジスタＲ４とＲ４を加算し、加算結果をレジスタＲ７に格納する。同時にレジスタＲ４とＲ５を加算し、加算結果をレジスタＲ５に格納する（図）３，ステップ（７））。すなわち、レジスタＲ４に格納されているＸＰ＾２を互いに加算し、加算結果の”２・ＸＰ＾２”をレジスタＲ７に格納する。また、レジスタＲ４に格納されている”ＸＰ＾２”と、レジスタＲ５に格納されているＷ［０］を加算し、加算結果の”ＸＰ＾２＋Ｗ［０］”をレジスタＲ５に格納する。
【００６２】
（８）次に、レジスタＲ５とＲ７を加算し、加算結果をレジスタＲ５に格納する。同時にレジスタＲ１とＲ１を加算し、加算結果をレジスタＲ１に格納する（図３，ステップ（８））。すなわち、レジスタＲ５に格納されている”ＸＰ＾２＋Ｗ［０］”と、レジスタＲ７に格納されている”２・ＸＰ＾２”を加算し、加算結果の”３・ＸＰ＾２＋Ｗ［０］”をレジスタＲ５に格納する。ここで、”Ｍ〔０〕＝３・ＸＰ＾２＋Ｗ〔０〕”とする。同時に、レジスタＲ１に格納されている”ＸＰ・ＹＰ＾２”を互いに加算し、加算結果をレジスタＲ１に格納する。
【００６３】
（９）次に、レジスタＲ５の平方算を計算し、計算結果をレジスタＲ４に格納する。同時に、レジスタＲ６の平方算を計算し、計算結果をレジスタＲ６に格納する（図３，ステップ（９））。すなわち、上記ステップ（８）の処理によりレジスタＲ５に格納される”Ｍ〔０〕＝３・ＸＰ＾２＋Ｗ〔０〕”の２乗を求め、演算結果をレジスタＲ４に格納する。同時に、レジスタＲ６に格納されているＹＰ＾２の２乗を計算し、計算結果のＹＰ＾４をレジスタＲ６に格納する。
【００６４】
（１０）次に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ１に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図３，ステップ（１０））。すなわち、レジスタＲ１に格納されている”２・ＸＰ・ＹＰ＾２”どうしを加算し、加算結果の”４・ＸＰ・ＹＰ＾２”をレジスタＲ１に格納する。ここで、”Ｓ〔０〕＝４・ＸＰ・ＹＰ＾２”とする。同時に、レジスタＲ６に格納されているＹＰ＾４どうしを加算し、結果をレジスタＲ６に格納する。
【００６５】
（１１）次に、上記のステップ（１０）で求めたレジスタＲ１とＲ１を加算し、加算結果をレジスタＲ７に格納する。同時に、上記のステップ（１０）で求めたレジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図３，ステップ（１１））。すなわち、レジスタＲ１に格納されている”Ｓ〔０〕＝４・ＸＰ・ＹＰ＾２”どうしを加算し、加算結果の２・Ｓ〔０〕をレジスタＲ７に格納する。同時に、レジスタＲ６に格納されている”２・ＹＰ＾４”どうしを加算し、結果をレジスタＲ６に格納する。
【００６６】
（１２）次に、レジスタＲ４からＲ７の値を減算し、減算結果をレジスタＲ４に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図３，ステップ（１２））。すなわち、レジスタＲ４に格納されている”Ｍ〔０〕＾２”から、レジスタＲ７に格納されている２・Ｓ〔０〕を減算し、減算結果の”Ｍ〔０〕＾２−２・Ｓ〔０〕”をレジスタＲ４に格納する。ここで、Ｘ〔１〕＝Ｍ〔０〕＾２−２・Ｓ〔０〕”とする。同時に、レジスタＲ６に格納されている４・ＹＰ＾４どうしを加算し、加算結果の”８・ＹＰ＾４”をレジスタＲ６に格納する。ここで、”Ｔ〔０〕＝８・ＹＰ＾４”とする。
【００６７】
（１３）次に、レジスタＲ１から、上記のステップ（１２）で求めたレジスタＲ４を減算し、減算結果をレジスタＲ１に格納する（図３，ステップ（１３））。すなわち、レジスタＲ１に格納されている”Ｓ〔０〕”から、レジスタＲ４に格納されている”Ｘ〔１〕＝Ｍ〔０〕＾２−２・Ｓ〔０〕”を減算し、減算結果をレジスタＲ１に格納する。
【００６８】
（１４）上記のステップ（１３）で計算したレジスタＲ１の”Ｓ〔０〕−Ｘ〔１〕”と、レジスタＲ５に格納されているＭ〔０〕を乗算し、乗算結果の”Ｍ〔０〕・（Ｓ〔０〕−Ｘ〔１〕）”をレジスタＲ１に格納する。同時に、レジスタＲ２に格納されている点ＰのＹ座標ＹＰと、レジスタＲ３に格納されている点ＰのＺ座標ＺＰを乗算し、乗算結果の”ＹＰ・ＺＰ”をレジスタＲ２に格納する（図３，ステップ（１４））。
【００６９】
（１５）上記のステップ（１４）で計算したレジスタＲ１の”Ｍ〔０〕・（Ｓ〔０〕−Ｘ〔１〕）から、レジスタＲ６に格納されているＴ〔０〕を減算し、減算結果の”Ｍ〔０〕・（Ｓ〔０〕−Ｘ〔１〕）−Ｔ〔０〕”をレジスタＲ１に格納する。同時に、上記のステップ（１４）で求めたレジスタＲ２とＲ２を加算し、加算結果の”２・ＹＰ・ＺＰ”をレジスタＲ２に格納する（図３，ステップ（１５））。
【００７０】
以上の処理により、楕円２倍算２×Ｐにより得られるヤコビアン座標における点Ｒの座標が計算できたので、ステップ（１６）において、レジスタＲ４の値を点ＲのＸ座標ＸＲとして出力する。また、ステップ（１７）において、レジスタＲ１の値を点ＲのＹ座標ＹＲとして出力する。さらに、ステップ（１８）において、レジスタＲ２の値を点ＲのＺ座標ＺＲとして出力する。
【００７１】
上述した第２の実施の形態は、楕円２倍算２×Ｐの同じ種類の演算を並列に実行できるように演算プログラムを作成し、演算部１２が楕円２倍算の同じ種類の演算を並列に実行することで、２回の乗算と、３回の平方算と、７回の加減算とにより楕円２倍算の計算を行うことができる。これにより、楕円２倍の計算時間を短縮し、スカラー倍算の計算時間を短縮することができる。
【００７２】
次に、図４は、楕円２＾ｋ倍算（＾：べき乗を表す、ｋ＝１以上の整数）を用いてスカラー倍算の計算を行う本発明の第３の実施の形態の演算プログラムを示す図である。
【００７３】
先ず、楕円２＾ｋ倍算２＾ｋ×Ｐを用いたスカラー倍算の演算プログラムを、図４を参照して説明する。図４のプログラムはＣ＋＋で記述してある。
整数ｄと、楕円曲線上の点Ｐの座標とを入力する。
【００７４】
変数Ｑ［０］に点Ｐの座標を設定する（図４，Ｓ１１）。変数ｉの初期値としてｉ＝ｎ−２を設定する（図４，Ｓ１２）。
while文と、ループ内の命令の実行条件である”ｉ＞０”を定義する（図４，Ｓ１３）。変数ｗの初期値として「１」を設定する（図４，Ｓ１４）。
【００７５】
次に、while文とループ内の命令の実行条件であるｄ［ｉ］＝＝０を定義する（図４，Ｓ１５）。
次に、変数ｉが「０」か否かを判断し、変数ｉが「０」、すなわち、すべての係数ｄ［ｉ］の判定が終了した場合にはループを抜ける（図４，Ｓ１６）。
【００７６】
次に、変数ｉをデクリメントする（図４，Ｓ１７）。さらに、変数ｗをインクリメントする（図４，Ｓ１８）。すなわち、係数ｄ［ｉ］が「０」で、かつ変数ｉが「０」でないとき、変数ｗがインクリメントされる。その後、ループの先頭のステップＳ１５に戻る（図４，Ｓ１９）。
【００７７】
上記のステップＳ１５からステップＳ１９の処理を繰り返すことにより、２進展開の係数ｄ［ｉ］が連続して「０」となる回数が計算され、その計算結果がレジスタｗに格納される。
【００７８】
ステップＳ１５において、係数ｄ［ｉ］が「０」でないと判断されたときには、ステップＳ２０に進み楕円２＾ｋ倍算の演算を定義した関数iecdbl（Ｑ［０］，ｗ）を呼び出して実行する。関数iecdbl（Ｑ［０］，ｗ）は、変数Ｑ［０］により定まる点の楕円２＾ｋ倍算（ｋ＝ｗ）の計算を行う関数である。
【００７９】
ステップＳ２０の楕円２＾ｋ倍算の演算が終了したなら、係数ｄ〔ｉ〕が「１」か否かを判断する（図４，ステップ２１）。
係数ｄ〔ｉ〕が「１」、すなわち、ステップＳ２１の条件が真であれば、次のステップＳ２２に進み、点Ｑ［０］（変数Ｑ［０］により指定される点）と点Ｐとの楕円加算”Ｑ［０］＝ecadd（Ｑ［０］，Ｐ）”を計算し、計算結果を変数Ｑ［０］に格納する。
【００８０】
ステップ２３は、ステップ２１からのループの終了を示す。次のステップＳ２４において、変数ｉをデクリメントし、その後、ループの先頭のステップＳ１３に戻る。
【００８１】
上述した処理により、係数ｄ［ｉ］が連続して「０」となる回数ｗが計算され、楕円２＾ｋ倍算（ｋ＝ｗ）が実行される。これにより、例えば、楕円２倍算をｋ回計算する必要がある場合でも、楕円２＾ｋ倍算の関数iecdbl（Ｑ［０］，ｗ）を一度呼び出すだけで２＾ｋ×Ｐの計算を行うことができるので、スカラー倍算における楕円２倍算の全体の計算時間を短縮できる。さらに、楕円２＾ｋ倍算を計算する関数iecdbl（Ｑ［０］，ｗ）のプログラムを、同じ種類の演算を、１つのプロセッサからなる演算部１２で並列に実行できるように記述することで、楕円２＾ｋ倍算の演算時間を短縮できる。楕円２＾ｋ倍算の演算の並列計算の方法については、次に詳しく説明する。
【００８２】
次に、図５は、図４のスカラー倍算の演算プログラムの楕円２＾ｋ倍算２＾ｋ×Ｐを計算する関数Ｑ〔０〕＝iecdbl（Ｑ〔０〕，ｗ）の演算式を示す図である。
【００８３】
楕円曲線上の点Ｐのヤコビアン座標における座標をＰ＝（ＸＰ，ＹＰ，ＺＰ）、楕円２＾ｋ倍算のべき乗の値をｋ、定数をａとし、楕円２＾ｋ倍算により得られる点Ｒの座標をＲ＝（ＸＲ，ＹＲ，ＺＲ）する。
【００８４】
Ｗ［０］を”ａ・ＺＰ＾４”とする（図５，Ｓ３１）
Ｍ［０］を”３・ＸＰ＾２＋Ｗ［０］”とする（図５，Ｓ３２）。
Ｓ［０］を”４・ＸＰ・ＹＰ＾２”とする（図５，Ｓ３３）。
【００８５】
Ｔ［０］を”８・ＹＰ＾４”とする（図５，Ｓ３４）。
ｋ＝１の点のＸ座標、Ｙ座標、Ｚ座標は、以下のように表せる。
Ｘ［１］＝Ｍ［０］＾２−２・Ｓ［０］（図５，Ｓ３５）
Ｙ［１］＝Ｍ［０］・（Ｓ［０］−Ｘ［１］）−Ｔ［０］（図５，Ｓ３６）
Ｚ［１］＝２・ＹＰ・ＺＰ（図５，Ｓ３７）
楕円２＾ｋ倍算を計算するために、以下の演算をｋ−１回繰り返す（図５，Ｓ３８）。
【００８６】
Ｗ［ｉ］＝２・Ｔ［ｉ−１］・Ｗ［ｉ−１］、を計算する（図５，Ｓ３９）。
Ｍ［ｉ］＝３・Ｘ［ｉ］＾２＋Ｗ［ｉ］、を計算する（図５，Ｓ４０）。
Ｓ［ｉ］＝４・Ｘ［ｉ］・Ｙ［ｉ］＾２、を計算する（図５，Ｓ４１）。
【００８７】
Ｔ［ｉ］＝８・Ｙ［ｉ］＾４、を計算する（図５，Ｓ４２）。
Ｘ［ｉ＋１］＝Ｍ［ｉ］＾２−２・Ｓ［ｉ］、を計算する（図５，Ｓ４３）。
Ｙ［ｉ＋１］＝Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ−１］）−Ｔ［ｉ］、を計算する（図５，Ｓ４４）。
【００８８】
Ｚ［ｉ＋１］＝２・Ｙ［ｉ］・Ｚ［ｉ］、を計算する（図５，Ｓ４５）。
上記の演算をｋ−１回実行して得られるＸ［ｋ］を、点ＲのＸ座標ＸＲとして出力する（図５，Ｓ４６）。
【００８９】
同様に、Ｙ［ｋ］を、点ＲのＹ座標ＹＲとして出力する（図５，Ｓ４７）。また、Ｚ［ｋ］を、点ＲのＺ座標ＺＲとして出力する（図５，Ｓ４８）。
上記の処理により、楕円２＾ｋ倍算により得られるヤコビアン座標の点Ｒの座標（ＸＲ，ＹＲ，ＺＲ）が（Ｘ［ｋ］，Ｙ［ｋ］，Ｚ［ｋ］）として求めることができる。
【００９０】
次に、図６は、図５の演算式に基づいて作成した楕円２＾ｋ倍算の演算プログラムを示す図である。この演算プログラムは、楕円２＾ｋ倍算の演算において、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述したものである。
【００９１】
最初に、楕円曲線上の点Ｐの座標Ｐ（ＸＰ，ＹＰ，ＺＰ）と、変数ｋの値と、定数ａを設定する。なお、変数ｋの値として、図４の演算プログラムで計算したｄ［ｉ］が連続して「０」となる回数ｗが設定される。
【００９２】
（１）演算部１２は、点ＰのＸ座標ＸＰをレジスタＲ１に設定する（図６，ステップ（１））。
（２）演算部１２は、点ＰのＹ座標ＹＰをレジスタＲ２に設定する（図６，ステップ（２））。
【００９３】
（３）演算部１２は、点ＰのＺ座標ＺＰをレジスタＲ３に設定する（図６，ステップ（３））。
（４）演算部１２は、レジスタＲ１の平方算を計算し、計算結果のＸＰ＾２をレジスタＲ４に格納する。同時に、レジスタＲ３の平方算を計算し、計算結果のＺＰ＾２をレジスタＲ５に格納する（図６のステップ（４））。
【００９４】
（５）次に、レジスタＲ２の平方算を計算し、計算結果のＹＰ＾２をレジスタＲ６に格納し、同時にレジスタＲ５の平方算を計算し、計算結果のＺＰ＾４レジスタＲ５に格納する（図６，ステップ（５））。
【００９５】
（６）次に、レジスタＲ１とＲ６を乗算し、乗算結果をレジスタＲ１に格納する。同時に、定数ａとレジスタＲ５を乗算し、乗算結果の”ａ・ＺＰ＾４”をレジスタＲ８に格納する（図６，ステップ（６））。このステップ（６）の処理は、定数ａとレジスタＲ５の値を乗算することで、図５の演算式の”Ｗ［０］＝ａ・ＺＰ＾４”を計算している。
【００９６】
（７）次に、レジスタＲ４とＲ４を加算し、加算結果をレジスタＲ７に格納する。同時に、レジスタＲ４とＲ８を加算し、加算結果をレジスタＲ５に格納する（図６，ステップ（７））。
【００９７】
（８）次に、レジスタＲ７とＲ５を加算し、加算結果の”３・ＸＰ＾２＋Ｗ［０］”をレジスタＲ５に格納する。同時に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ１に格納する（図６，ステップ（８））。このステップ（８）の処理は、レジスタＲ７とＲ５を加算することで、図５の演算式の”Ｍ［０］＝３・ＸＰ＾２＋Ｗ［０］”を計算している。
【００９８】
（９）次に、レジスタＲ５の平方算を計算し、計算結果をレジスタＲ４に格納する。同時に、レジスタＲ６の平方算を計算し、計算結果をレジスタＲ６に格納する（図６，ステップ（９））。
【００９９】
（１０）次に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ１に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図６，ステップ（１０））。このステップ（１０）の処理は、レジスタＲ１とＲ１の値を加算することで、図５の演算式の”Ｓ〔０〕＝４・ＸＰ・ＹＰ＾２”を計算している。
【０１００】
（１１）次に、レジスタＲ１とＲ１を加算し、加算結果をレジスタＲ７に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図６，ステップ（１１））。
【０１０１】
（１２）次に、レジスタＲ４からＲ７を減算し、結果をレジスタＲ４に格納する。同時に、レジスタＲ６とＲ６を加算し、加算結果をレジスタＲ６に格納する（図６，ステップ（１２））。このステップ（１２）の処理は、レジスタＲ４からＲ７を減算することで、図５の演算式の”Ｘ［１］＝Ｍ［０］＾２−２・Ｓ［０］を計算している。また、レジスタＲ６とＲ６を加算することで、図５の演算式の”Ｔ［０］＝８・ＹＰ＾４”を計算している。
【０１０２】
（１３）次に、レジスタＲ１からＲ４を減算し、結果をレジスタＲ１に格納する（図６，ステップ（１３））。
（１４）次に、レジスタＲ５に格納されている”Ｍ〔０〕”と、レジスタＲ１に格納されている”Ｓ〔０〕−Ｘ〔１〕”を乗算し、乗算結果をレジスタＲ１に格納する。同時に、レジスタＲ２の点ＰのＹ座標ＹＰとＲ３の点ＰのＺ座標ＺＰを乗算し、乗算結果をレジスタＲ２に格納する（図６，ステップ（１４））。
【０１０３】
（１５）次に、レジスタＲ１の”Ｍ〔０〕・（Ｓ〔０〕−Ｘ〔１〕）”からレジスタＲ６のＴ〔０〕を減算し、減算結果をレジスタＲ１に格納する。同時に、レジスタＲ２の”ＹＰ・ＺＰ”どうしを加算し、加算結果をレジスタＲ２に格納する（図６，ステップ（１５））。このステップ（１５）の処理は、レジスタＲ１からＲ６を減算することで、図５の演算式の”Ｙ〔１〕＝Ｍ［０］・（Ｓ［０］−Ｘ［０］）−Ｔ［０］”を計算している。同時に、レジスタＲ２とＲ２を加算することで、図５の演算式の”Ｚ〔１〕＝２・ＹＰ・ＺＰ”を計算している。
【０１０４】
以上の処理により、点Ｐの座標（ＸＰ，ＹＰ，ＺＰ）と、定数ａとから、Ｗ［０］、Ｍ［０］、Ｓ［０］、Ｔ［０］、Ｘ［１］、Ｙ［１］、Ｚ［１］を算出することができる。
（１６）次に、ｉを、１からｋ−１まで変化させて、ステップｂ１〜ｂ１１の処理を実行する（図６，ステップ（１６））。
【０１０５】
最初に、レジスタＲ４の平方算を計算し、計算結果をレジスタＲ３に格納する。同時に、レジスタＲ１の平方算を計算し、計算結果をレジスタＲ５に格納する（図６，ステップｂ１）。
【０１０６】
上述したステップ（１）〜（１５）の処理により、レジスタＲ４にはＸ［１］が、レジスタＲ１にはＹ［１］が格納されている。従って、変数ｉ＝１のときには、上記のステップｂ１の処理により、レジスタＲ３に”Ｘ［１］＾２”が格納され、レジスタＲ５に”Ｙ［１］＾２”が格納される。変数ｉを任意の値としたときには、ステップｂ１の処理により、レジスタＲ３に”Ｘ［ｉ］＾２”が格納され、レジスタＲ５に”Ｙ［ｉ］＾２”が格納される。
【０１０７】
次に、レジスタＲ４とＲ５を乗算し、乗算結果をレジスタＲ４に格納する。同時にレジスタＲ８とＲ６を乗算し、乗算結果をレジスタＲ８に格納する（図６，ステップｂ２）。
【０１０８】
上記のステップｂ２の処理により、変数ｉ＝１のときには、レジスタＲ４に”Ｘ［１］・Ｙ［１］＾２”が格納され、レジスタＲ８に”Ｔ［０］・Ｗ［０］”が格納される。変数ｉを任意の値としたときには、演算結果として”Ｘ［ｉ］・Ｙ［ｉ］＾２”が得られ、その演算結果がレジスタ４に格納される。また、演算結果として”Ｔ［ｉ−１］・Ｗ［ｉ−１］”が得られ、その演算結果がレジスタＲ８に格納される。
【０１０９】
次に、レジスタＲ８とＲ８とを加算し、加算結果をレジスタＲ８に格納する。
同時にレジスタＲ３とＲ３とを加算し、加算結果をレジスタＲ７に格納する（図６，ステップｂ３）。
【０１１０】
上記のステップｂ３の処理により、変数ｉ＝１のとき、レジスタＲ８とＲ８の加算結果として２・Ｔ［０］・Ｗ［０］が得られ、その演算結果がレジスタＲ６に格納される。また、変数ｉを任意の値とした、レジスタＲ８とＲ８の加算結果として”２・Ｔ［ｉ−１］・Ｗ［ｉ−１］”が得られ、その演算結果がレジスタＲ８に格納される。
【０１１１】
従って、上記のステップｂ３の処理により、図５の演算式のＳ３９の”Ｗ［ｉ］＝２・Ｔ［ｉ−１］・Ｗ［ｉ−１］”を計算することができる。
次に、レジスタＲ３とＲ７の値を加算し、加算結果をレジスタＲ６に格納する。同時に、レジスタＲ４とＲ４を加算し、加算結果をレジスタＲ４に格納する（図６，ステップｂ４）。
【０１１２】
次に、レジスタＲ８とＲ６を加算し、加算結果をレジスタＲ３に格納する。同時に、レジスタＲ４とＲ４を加算し、加算結果をレジスタＲ７に格納する（図６，ステップｂ５）。
【０１１３】
上記のステップｂ５の処理により、変数ｉを任意の値としたときに、レジスタＲ８とＲ６の加算結果として”３・Ｘ［ｉ］＾２＋Ｗ［ｉ］”が得られ、その結果がレジスタＲ３に格納される。また、レジスタＲ４とＲ４の加算結果として”４・Ｘ［ｉ］・Ｙ［ｉ］＾２”が得られ、その結果がレジスタＲ７に格納される。
【０１１４】
従って、上記のステップｂ５の処理により、図５の演算式のＳ４０の”Ｍ［ｉ］＝３・Ｘ［ｉ］＾２＋Ｗ［ｉ］”を計算することができる。また、図５の演算式のＳ４１の”Ｓ［ｉ］＝４・Ｘ［ｉ］・Ｙ［ｉ］＾２”を計算することができる。
【０１１５】
次に、レジスタＲ３の平方算を計算し、計算結果をレジスタＲ６に格納する。
同時にレジスタＲ５の平方算を計算し、計算結果をレジスタＲ５に格納する（図６，ステップｂ６）。
【０１１６】
次に、レジスタＲ５とＲ５を加算し、加算結果の”２・Ｙ〔ｉ〕＾２”をレジスタＲ５に格納する。同時に、レジスタＲ７とＲ７を加算し、加算結果の２・Ｓ〔ｉ〕をレジスタＲ４に格納する（図６，ステップｂ７）。
【０１１７】
次に、レジスタＲ５とＲ５を加算し、加算結果の”４・Ｙ〔ｉ〕＾２”をレジスタＲ５に格納する。同時に、レジスタＲ６からＲ４を減算し、結果をレジスタＲ４に格納する（図６，ステップｂ８）。
【０１１８】
上記のステップｂ８の処理により、変数ｉを任意の値としたときに、レジスタＲ６からＲ４を減算した結果として”Ｍ［ｉ］＾２−２・Ｓ［ｉ］が得られ、その結果がレジスタＲ４に格納される。
【０１１９】
従って、上記のステップｂ８の処理により、図５の演算式のＳ４３の”Ｘ［ｉ＋１］＝Ｍ［ｉ］＾２−２・Ｓ［ｉ］”を計算することができる。
次に、レジスタＲ５とＲ５と加算し、加算結果をレジスタＲ６に格納する。同時にレジスタＲ７からレジスタＲ４を減算し、結果をレジスタＲ７に格納する（図６，ステップｂ９）。
【０１２０】
上記のステップｂ９の処理により、変数ｉを任意の値としたときに、レジスタＲ５とＲ５の加算結果として”８・Ｙ［ｉ］＾４”が得られる。
従って、上記のステップｂ９の処理により、図５の演算式のＳ４２の”Ｔ［ｉ］＝８・Ｙ［ｉ］＾４”を計算することができる。
【０１２１】
次に、レジスタＲ３とＲ７を乗算し、乗算結果をレジスタＲ７に格納する。同時に、レジスタＲ１とＲ２とを乗算し、乗算結果をレジスタＲ２に格納する（図６，ステップｂ１０）。
【０１２２】
次に、レジスタＲ７からレジスタＲ６を減算し、結果をレジスタＲ１に格納する。同時に、レジスタＲ２とＲ２を加算し、加算結果をレジスタＲ２に格納する（図６，ステップｂ１１）。
【０１２３】
上記のステップｂ１１の処理により、レジスタＲ７に格納されている”Ｍ［ｉ］（Ｓ［ｉ］−Ｘ［ｉ＋１］）”から、レジスタＲ６に格納されている”Ｔ［ｉ］”が減算され、演算結果の”Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ＋１］）−Ｔ［ｉ］”がレジスタＲ１に格納される。また、レジスタＲ２に格納されている”Ｙ［ｉ］・Ｚ［ｉ］”どうしが加算され、演算結果の”２・Ｙ［ｉ］・Ｚ［ｉ］”がレジスタＲ２に格納される。
【０１２４】
従って、上記のステップｂ１１の処理により、図５の演算式のＳ４４の”Ｙ［ｉ＋１］＝Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ＋１］）−Ｔ［ｉ］”を計算することができる。また、図５の演算式のＳ４５の”Ｚ［ｉ＋１］＝２・Ｙ［ｉ］・Ｚ［ｉ］”を計算することができる。
【０１２５】
上記のステップｂ１〜ｂ１１の処理をｉ＝１からｋ−１まで繰り返すことで、レジスタＲ４，Ｒ１，Ｒ２に、楕円２＾ｋ倍算の点Ｒの座標が格納される。
（１７）次に、レジスタＲ４に格納されているＸ［ｋ］を点ＲのＸ座標ＸＲとして出力する（図６，ステップ（１７））。
（１８）次に、レジスタＲ１に格納されているＹ［ｋ］を点ＲのＹ座標ＹＲとして出力する（図６，ステップ（１８））。
（１９）次に、レジスタＲ２に格納されているＺ［ｋ］を点ＲのＺ座標ＺＲとして出力する（図６，ステップ（１９））。
【０１２６】
上述した処理により楕円２＾ｋ倍算により得られる点Ｒの座標（ＸＲ，ＹＲ，ＺＲ）を計算することができる。
上述した第３の実施の形態によれば、スカラー倍算の演算において、ｄ［ｉ］が連続して０」となる回数ｋを予め計算し、楕円２＾ｋ倍算の計算を行うことで楕円２倍算を繰り返し実行する場合に比べて計算時間を短縮することができる。
【０１２７】
また、第３の実施の形態の演算プログラムによれば、楕円２＾ｋ倍算の同じ種類の演算を並列に実行することで、２×ｋ回の乗算と、（２×ｋ＋１）回の平方算と、７×ｋ回の加減算とにより、点ＲのＸ座標とＹ座標とＺ座標を計算することができるので、楕円２＾ｋ倍算の演算時間を短縮できる。
【０１２８】
ここで、上述した実施の形態のスカラー倍算の演算プログラムを実行する楕円曲線暗号装置のハードウェア構成の一例を図７を参照して説明する。楕円暗号装置は、例えば、パーソナルコンピュータ等の情報処理装置により実現できる。
【０１２９】
ＣＰＵ２１は、ＳＩＭＤ機能を有し、楕円曲線暗号の楕円加算、楕円２倍算等の演算の中で同じ種類の演算を並列に実行する。メモリ２２は、演算に使用される各種のレジスタとして使用される。外部記憶装置２３は、ＯＳや、楕円曲線暗号の演算プログラム等が格納される。
【０１３０】
媒体駆動装置２４は、ＣＤＲＯＭ、ＤＶＤ、フレキシブルディスク、ＩＣカード等の可搬記録媒体２５の読み取り、あるいは書き込みを行う装置である。
入力装置２６は、キーボード等のデータを入力する装置である。出力装置２７は、ディスプレイ、プリンタ等の装置である。ネットワーク接続装置２８は、インターネット等のネットワークに接続するための装置であり、この装置を介してネットワーク上のサーバからプログラムをダウンロードすることができる。なお、ＣＰＵ２１，メモリ２２，外部記憶装置２３，入装置２６等はバス２９により接続されている。
【０１３１】
本発明は、楕円曲線暗号の暗号化及び解読を行う専用の装置に限らず、ＩＣカード、ＤＶＤ装置、携帯電話機、パーソナルコンピュータ等の種々の製品に適用できる。
【０１３２】
また、本発明は、ヤコビアン座標に限らず他の座標系にも適用できる。さらに、スカラー倍算の演算アルゴリズムは、図４、あるいは図１０のアルゴリズムに限らず他の演算アルゴリズムを用いても良い。
【０１３３】
（付記１）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑと楕円２＾ｋ（＾：べき乗を表す、ｋ＝１以上の整数）倍算の演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された演算プログラムの楕円加算の同じ種類の演算を並列に実行するとともに、楕円２＾ｋ倍算の同じ種類の演算を並列に実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【０１３４】
（付記２）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
楕円曲線上の点Ｐと点Ｑのヤコビアン座標における座標を、それぞれ（ＸＰ，ＹＰ，ＺＰ）、（ＸＱ，ＹＱ，ＺＱ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑの演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された楕円加算の演算プログラムの同じ種類の演算を並列に実行して楕円加算Ｐ＋Ｑ＝Ｒの点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える楕円曲線暗号装置。
【０１３５】
（付記３）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
楕円曲線上の点Ｐのヤコビアン座標における座標を（ＸＰ，ＹＰ，ＺＰ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円２倍算２×Ｐの演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された楕円２倍算の演算プログラムの同じ種類の演算を並列に実行して楕円２倍算２×Ｐ＝Ｒの点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える楕円曲線暗号装置。
【０１３６】
（付記４）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
楕円曲線上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）としたときに、同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された楕円２＾ｋ倍算の演算プログラムの同じ種類の演算を並列に実行して楕円２＾ｋ倍算により得られる点Ｒのヤコビアン座標（ＸＲ，ＹＲ，ＺＲ）を計算する演算手段とを備える楕円曲線暗号装置。
【０１３７】
（付記５）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、
係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の同じ種類の演算を並列に実行する楕円曲線暗号演算方法。
【０１３８】
（付記６）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算プログラムにおいて、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑと楕円２＾ｋ（＾：べき乗を表す、ｋ＝１以上の整数）倍算の演算プログラムを記憶部に記憶させ、
前記記憶部に記憶された演算プログラムの楕円加算の同じ種類の演算を並列に実行するとともに、楕円２＾ｋ倍算の同じ種類の演算を並列に実行してスカラー倍算ｄ×Ｐを計算する楕円曲線暗号演算プログラム。
【０１３９】
（付記７）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑと楕円２＾ｋ（＾：べき乗を表す、ｋ＝１以上の整数）倍算の演算プログラムを記憶部に記憶し、
前記記憶部に記憶された演算プログラムの楕円加算の同じ種類の演算を並列に実行するとともに、楕円２倍算の同じ種類の演算を並列に実行してスカラー倍算ｄ×Ｐを計算する楕円曲線暗号演算方法。
【０１４０】
（付記８）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように記述した楕円加算Ｐ＋Ｑと楕円２倍算と楕円２＾ｋ倍算（＾：べき乗を表す，ｋ＝２以上の整数）の演算プログラムを記憶する記憶手段と、
前記記憶手段に記憶された演算プログラムの楕円加算の同じ種類の演算、楕円２倍算の同じ種類の演算及び楕円２＾ｋ倍算の同じ種類の演算を、それぞれ並列に実行してスカラー倍算ｄ×Ｐを計算する演算手段とを備える楕円曲線暗号装置。
【０１４１】
（付記９） 付記２記載の楕円曲線暗号装置において、
前記演算手段は、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）と、点Ｑの座標（ＸＱ，ＹＱ，ＺＱ）とに基づいて楕円加算の演算プログラムの同じ種類の演算を並列に実行する。
【０１４２】
（付記１０）付記４記載の楕円曲線暗号装置において、
前記演算手段は、素体上の楕円曲線ｙ２＝ｘ３＋ａ・ｘ＋ｂ（ｍｏｄ ｐ）上の点Ｐのヤコビアン座標における座標（ＸＰ，ＹＰ，ＺＰ）に基づいて楕円２＾ｋ倍算の演算プログラムの同じ種類の演算を並列に実行する。
【０１４３】
（付記１１）付記１記載の楕円曲線暗号装置において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
前記演算手段は、係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ倍算の同じ種類の演算を並列に実行する。
【０１４４】
（付記１２）付記４記載の楕円曲線暗号装置において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
前記演算手段は、係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ倍算の同じ種類の演算を並列に実行する。
【０１４５】
（付記１３）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号プログラムにおいて、
同じ種類の演算で異なるデータに対する演算を並列に実行できるように楕円加算Ｐ＋Ｑと楕円２倍算の演算プログラムを作成し、
前記楕円加算の同じ種類の演算と、前記楕円２倍算の同じ種類の演算を、それぞれ並列に実行してスカラー倍算ｄ×Ｐを計算する楕円曲線暗号演算プログラム。
【０１４６】
（付記１４）楕円加算、楕円２倍算または楕円２＾ｋ倍算の演算を行う演算手段が、演算命令及び複数のデータを記憶するレジスタ群と、演算器とを備え、前記レジスタ群に記憶された楕円加算、楕円２倍算または楕円２＾ｋ倍算の同じ種類の演算で異なるデータに対する演算を前記演算器が並列に実行する。
【０１４７】
（付記１５）整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）とし、
係数ｄ［ｉ］が連続して「０」となる回数ｋを計算し、
係数ｄ［ｉ］が連続して「０」となる回数ｋに基づいて楕円２＾ｋ（＾：べき乗を表す，ｋ＝２以上の整数）倍算の計算を行う楕円曲線暗号演算方法。
【０１４８】
【発明の効果】
本発明によれば、楕円加算の演算において同じ種類の演算で異なるデータに対する演算を並列に実行することでスカラー倍算の計算時間を短縮することができる。また、楕円２倍算の演算において同じ種類の演算を並列に実行することでスカラー倍算の計算時間を短縮できる。さらに、楕円２＾ｋ倍算の演算において同じ種類の演算を並列に実行することでスカラー倍算の計算時間を短縮できる。また、２進展開の係数ｄ［ｉ］が連続して「０」となる回数に基づいて楕円２＾ｋ倍算の同じ種類の演算を並列に実行することで楕円２＾ｋ倍算の計算時間を短縮できる。
【図面の簡単な説明】
【図１】実施の形態の楕円曲線暗号装置の要部の構成を示す図である。
【図２】第１の実施の形態の楕円加算の演算プログラムを示す図である。
【図３】第２の実施の形態の楕円２倍算の演算プログラムを示す図である。
【図４】楕円２＾ｋ倍算を用いたスカラー倍算の演算プログラムを示す図である。
【図５】楕円２＾ｋ倍算の演算式を示す図である。
【図６】第３の実施の形態の楕円２＾ｋ倍算の演算プログラムを示す図である。
【図７】実施の形態の情報処理装置のハードウェア構成図である。
【図８】楕円加算の説明図である。
【図９】楕円２倍算の説明図である。
【図１０】スカラー倍算の演算プログラムを示す図である。
【符号の説明】
１１ 楕円曲線暗号装置
１２ 演算部
１３ 演算器
１４ レジスタ群
１５ 記憶部
２１ ＣＰＵ
２２ メモリ
２３ 外部記憶装置
２４ 媒体駆動装置
２５ 可搬記録媒体
２６ 入力装置
２７ 出力装置
２８ ネットワーク接続装置
２９ バス
Claims (3)
- 整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号装置において、
整数ｄの２進展開の係数ｄ〔ｉ〕（ｄ［ｉ］＝０，１）が連続して０となる回数ｋの計算結果を記憶するレジスタと、
楕円曲線上の点Ｐのヤコビアン座標をＰ（ＸＰ、ＹＰ、ＺＰ）とし、ｉ＝０のときのＷ［ｉ］、Ｍ［ｉ］、Ｓ［ｉ］、Ｔ［ｉ］を、
Ｗ［０］＝ａ・ＺＰ ４ 、
Ｍ［０］＝３・ＸＰ ２ ＋Ｗ［０］、
Ｓ［０］＝４・ＸＰ・ＹＰ ２ 、
Ｔ［０］＝８・ＹＰ ４ 、とし、
ｋ＝１の点のＸ、Ｙ、Ｚ座標を、
Ｘ［１］＝Ｍ［０］ ２ −２・Ｓ［０］、
Ｙ［１］＝Ｍ［０］・（Ｓ［０］−Ｘ［１］）−Ｔ［０］、
Ｚ［１］＝２・ＹＰ・ＺＰ、から算出し、
（１） Ｗ［ｉ］＝２・Ｔ［ｉ−１］・Ｗ［ｉ−１］、
（２） Ｍ［ｉ］＝３・Ｘ［ｉ］ ２ ＋Ｗ［ｉ］、
（３） Ｓ［ｉ］＝４・Ｘ［ｉ］・Ｙ［ｉ］ ２ 、
（４） Ｔ［ｉ］＝８・Ｙ［ｉ］ ４ 、
（５） Ｘ［ｉ＋１］＝Ｍ［ｉ］ ２ −２・Ｓ［ｉ］、
（６） Ｙ［ｉ＋１］＝Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ−１］）−Ｔ［ｉ］、
（７） Ｚ［ｉ＋１］＝２・Ｙ［ｉ］・Ｚ［ｉ］、
前記レジスタに格納されている値ｋに基づいて変数ｉを１からｋ−１まで変化させ、上記（１）〜（７）の演算を行って楕円２ ｋ 倍算の演算を実行する際に、同じ種類の演算を並列に実行する演算手段とを備える楕円曲線暗号装置。 - 前記演算手段は、点ＰのＸ座標ＸＰをレジスタＲ１、Ｙ座標ＹＰをレジスタＲ２、Ｚ座標ＺＰをレジスタＲ３に設定し、レジスタＲ１のＸＰの平方算と、レジスタＲ３のＺＰの平方算を並列に実行して演算結果をレジスタに格納し、レジスタＲ２のＹＰの平方算と、レジスタに格納されているＺＰ ２ の平方算を並列に実行して演算結果のＺＰ ４ をレジスタに格納し、定数ａとレジスタに格納されているＹＰ ４ の乗算を行ってＷ［０］＝ａ・ＺＰ ４ を算出することを特徴とする請求項１記載の楕円曲線暗号装置。
- 整数ｄと楕円曲線上の点Ｐとのスカラー倍算を計算する楕円曲線暗号演算方法において、
整数ｄの２進展開の係数ｄ［ｉ］（ｄ［ｉ］＝０，１）が連続して０となる回数ｋを計算してレジスタに格納し、
楕円曲線上の点Ｐのヤコビアン座標をＰ（ＸＰ、ＹＰ、ＺＰ）とし、ｉ＝０のときのＷ［ｉ］、Ｍ［ｉ］、Ｓ［ｉ］、Ｔ［ｉ］の値を、
Ｗ［０］＝ａ・ＺＰ ４ 、
Ｍ［０］＝３・ＸＰ ２ ＋Ｗ［０］、
Ｓ［０］＝４・ＸＰ・ＹＰ ２ 、
Ｔ［０］＝８・ＹＰ ４ 、とし、
ｋ＝１の点のＸ、Ｙ、Ｚ座標を、
Ｘ［１］＝Ｍ［０］ ２ −２・Ｓ［０］、
Ｙ［１］＝Ｍ［０］・（Ｓ［０］−Ｘ［１］）−Ｔ［０］、
Ｚ［１］＝２・ＹＰ・ＺＰ、から算出し、
（１） Ｗ［ｉ］＝２・Ｔ［ｉ−１］・Ｗ［ｉ−１］、
（２） Ｍ［ｉ］＝３・Ｘ［ｉ］ ２ ＋Ｗ［ｉ］、
（３） Ｓ［ｉ］＝４・Ｘ［ｉ］・Ｙ［ｉ］ ２ 、
（４） Ｔ［ｉ］＝８・Ｙ［ｉ］ ４ 、
（５） Ｘ［ｉ＋１］＝Ｍ［ｉ］ ２ −２・Ｓ［ｉ］、
（６） Ｙ［ｉ＋１］＝Ｍ［ｉ］・（Ｓ［ｉ］−Ｘ［ｉ−１］）−Ｔ［ｉ］、
（７） Ｚ［ｉ＋１］＝２・Ｙ［ｉ］・Ｚ［ｉ］、
前記レジスタに格納されている値ｋに基づいて変数ｉを１からｋ−１まで変化させ、上記（１）〜（７）の演算を行って楕円２ ｋ 倍算の演算を実行する際に、同じ種類の演算を並列に実行する楕円曲線暗号演算方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002342387A JP4543143B2 (ja) | 2002-11-26 | 2002-11-26 | 楕円曲線暗号装置、楕円曲線暗号演算方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002342387A JP4543143B2 (ja) | 2002-11-26 | 2002-11-26 | 楕円曲線暗号装置、楕円曲線暗号演算方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2004177582A JP2004177582A (ja) | 2004-06-24 |
| JP4543143B2 true JP4543143B2 (ja) | 2010-09-15 |
Family
ID=32704476
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002342387A Expired - Fee Related JP4543143B2 (ja) | 2002-11-26 | 2002-11-26 | 楕円曲線暗号装置、楕円曲線暗号演算方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP4543143B2 (ja) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7680268B2 (en) * | 2005-03-15 | 2010-03-16 | Microsoft Corporation | Elliptic curve point octupling using single instruction multiple data processing |
| US8180047B2 (en) | 2006-01-13 | 2012-05-15 | Microsoft Corporation | Trapdoor pairings |
| US8804952B2 (en) | 2012-12-26 | 2014-08-12 | Umm Al-Qura University | System and method for securing scalar multiplication against differential power attacks |
| KR101925614B1 (ko) * | 2017-11-08 | 2018-12-05 | 부산대학교 산학협력단 | 타원곡선 암호화 시스템에서의 스칼라 곱셈 처리 방법 및 타원곡선 암호화 시스템 |
| CN113504895B (zh) * | 2021-07-13 | 2024-02-20 | 深圳市智芯华玺信息技术有限公司 | 椭圆曲线多标量点乘计算优化方法及优化装置 |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3615405B2 (ja) * | 1998-12-18 | 2005-02-02 | 富士通株式会社 | 素体上楕円曲線上の点の演算方法およびその装置 |
| JP2001202019A (ja) * | 2000-01-21 | 2001-07-27 | Nippon Telegr & Teleph Corp <Ntt> | 並列楕円演算装置及びそのプログラム記録媒体 |
-
2002
- 2002-11-26 JP JP2002342387A patent/JP4543143B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2004177582A (ja) | 2004-06-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4067818B2 (ja) | 楕円曲線暗号装置、楕円曲線暗号プログラム及び楕円曲線暗号の演算方法 | |
| US6876745B1 (en) | Method and apparatus for elliptic curve cryptography and recording medium therefore | |
| US7372960B2 (en) | Method and apparatus for performing finite field calculations | |
| US20110161390A1 (en) | Modular multiplication processing apparatus | |
| EP1306750A2 (en) | Multi-scalar multiplication computation in elliptic curve signature verification | |
| Kumar | Elliptic curve cryptography for constrained devices | |
| JP4668931B2 (ja) | 電力解析攻撃に対する耐タンパ性を持った暗号化処理装置 | |
| KR100442218B1 (ko) | 몽고메리의 알고리즘을 이용한 멱승 잉여 연산기 | |
| EP0952697B1 (en) | Elliptic curve encryption method and system | |
| CN118860336A (zh) | 一种执行椭圆曲线计算的计算设备 | |
| JP4543143B2 (ja) | 楕円曲線暗号装置、楕円曲線暗号演算方法 | |
| US7680268B2 (en) | Elliptic curve point octupling using single instruction multiple data processing | |
| JP2005055488A (ja) | 楕円曲線暗号におけるスカラー倍計算方法と、その装置およびそのプログラム | |
| US20050201553A1 (en) | Cryptography-processing method, cryptography-processing apparatus and computer program | |
| JP2004053814A (ja) | 楕円曲線暗号装置及び楕円曲線暗号演算方法 | |
| CN101243388A (zh) | 用于在加密计算中执行求逆运算的电路结构和方法 | |
| JPH1152854A (ja) | 有限体上の四則演算装置及び楕円曲線上の群演算装置 | |
| KR20020086005A (ko) | 타원곡선 암호 시스템을 위한 역원 연산기 | |
| JP4479135B2 (ja) | 演算装置及び演算方法及び演算プログラム | |
| Wolkerstorfer et al. | A PCI-card for accelerating elliptic curve cryptography | |
| CN114417378B (zh) | 基于梅森数的密钥交换或公钥密码加密优化方法及系统 | |
| JPH076025A (ja) | 冪剰余演算方法および装置 | |
| JPH1152851A (ja) | 楕円曲線上の群演算装置 | |
| JP3966714B2 (ja) | 暗号処理方法、そのプログラム及びその記録媒体 | |
| JP2007212768A (ja) | 楕円曲線暗号における事前計算テーブル作成装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050713 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20080930 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20081229 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20100126 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20100426 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20100518 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20100527 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130709 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| LAPS | Cancellation because of no payment of annual fees |