JP4034585B2 - 楕円曲線演算装置及び楕円曲線演算方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、楕円曲線上の演算を行う装置に関し、特に、モンゴメリ型楕円曲線上の点に対するスカラ倍点を算出する装置に関する。
【０００２】
【従来の技術】
１．公開鍵暗号
近年、コンピュータ技術と通信技術とに基づくデータ通信が広く普及してきており、このデータ通信においては、秘密通信方式又はデジタル署名方式が用いられている。ここで、秘密通信方式とは、特定の通信相手以外に通信内容を漏らすことなく通信を行う方式である。またデジタル署名方式とは、通信相手に通信内容の正当性を示したり、発信者の身元を証明する通信方式である。
【０００３】
これらの秘密通信方式又はデジタル署名方式には公開鍵暗号とよばれる暗号方式が用いられる。公開鍵暗号は通信相手が多数の時、通信相手ごとに異なる暗号鍵を容易に管理するための方式であり、多数の通信相手と通信を行うのに不可欠な基盤技術である。公開鍵暗号を用いる秘密通信では、暗号化鍵と復号化鍵とが異なり、復号化鍵は秘密にするが、暗号化鍵は公開する。
【０００４】
この公開鍵暗号の安全性の根拠として離散対数問題が用いられる。離散対数問題には、代表的なものとして、有限体上定義されるもの及び楕円曲線上定義されるものがある。なお、楕円曲線及び離散対数問題については、ニイルコブリッツ著 "ア コウス イン ナンバア セオリイ アンド クリプトグラヒイ"(Neal Koblitz, " A Course in Number theory and Cryptography", Springer-Verlag,1987)に詳しく述べられている。
【０００５】
２．楕円曲線上の離散対数問題
楕円曲線上の離散対数問題について、以下に述べる。
ｐを素数として、有限体ＧＦ（ｐ）上定義された楕円曲線をＥとする。Ｅ上の点で、ｘ座標、ｙ座標が共にＧＦ（ｐ）に属する点全体に形式的な点Ｏを追加した集合を考えると、この集合は点Ｏを零元として群をなす。楕円曲線の位数とは上記集合の元の個数を示している。Ｇ＝（ｇｘ、ｇｙ）とするとき、−Ｇを−Ｇ＝（ｇｘ、−ｇｙ）として定義する。
【０００６】
楕円曲線上の離散対数問題とは、楕円曲線Ｅの位数が大きな素数で割り切れる場合に、楕円曲線Ｅに含まれる元Ｇをベースポイントとする。このとき、楕円曲線Ｅに含まれる与えられた元Ｙに対して、
（式１） Ｙ＝ｘ＊Ｇ
となる自然数ｘが存在するならば、ｘを求めよ、という問題である。
ここで、ｐは素数、ＧＦ（ｐ）はｐ個の元を持つ有限体である。また、この明細書において、記号＊は、楕円曲線に含まれる元を複数回加算する演算を示し、ｘ＊Ｇは、次式に示すように、楕円曲線に含まれる元Ｇをｘ回加算することを意味する。
ｘ＊Ｇ＝Ｇ＋Ｇ＋Ｇ＋・・・＋Ｇ
ｘ＊Ｇのような点をＧのスカラ倍点という。
離散対数問題を公開鍵暗号の安全性の根拠とするのは、多くの元を有する有限体ＧＦ（ｐ）に対して、上記問題は極めて難しいからである。
【０００７】
３．楕円曲線上の離散対数問題を応用したエルガマル署名
以下に、上記楕円曲線上の離散対数問題を応用したエルガマル署名によるデジタル署名方式について、図２５を用いて、説明する。
この図は、上記エルガマル署名によるデジタル署名方式の手順を示すシーケンス図である。ユーザＡ１１０、管理センタ１２０及びユーザＢ１３０は、ネットワークで接続されている。ｐを素数、有限体ＧＦ（ｐ）上の楕円曲線をＥとする。ＥのベースポイントをＧとし、Ｅの位数をｑとする。つまり、ｑは、
（式２） ｑ＊Ｇ＝０
を満たす最小の正整数である。
【０００８】
（１）管理センタ１２０による公開鍵の生成
管理センタ１２０は、予め通知されているユーザＡ１１０の秘密鍵ｘＡを用いて、式３に従って、ユーザＡ１１０の公開鍵ＹＡを生成する（ステップＳ１４１〜Ｓ１４２）。
（式３） ＹＡ＝ｘＡ＊Ｇ
【０００９】
その後、管理センタ１２０は、素数ｐ、楕円曲線Ｅ及びベースポイントＧをシステムパラメータとして公開し、また、他のユーザＢ１３０にユーザＡ１１０の公開鍵ＹＡを公開する（ステップＳ１４３〜Ｓ１４４）。
【００１０】
（２）ユーザＡ１１０による署名生成
ユーザＡ１１０は、乱数ｋを生成する（ステップＳ１４５）。次に、ユーザＡ１１０は、
（式４） Ｒ１＝（ｒｘ，ｒｙ）＝ｋ＊Ｇ
を計算し（ステップＳ１４６）、
（式５） ｓ×ｋ＝ｍ＋ｒｘ×ｘＡ （ｍｏｄ ｑ）
から、ｓを計算する（ステップＳ１４７）。ここで、ｍは、ユーザＡ１１０がユーザＢ１３０へ送信するメッセージである。ただし、×は乗算を示している。さらに、ユーザＡ１１０は、得られた（Ｒ１、ｓ）を署名としてメッセージｍとともに、ユーザＢ１３０へ送信する（ステップＳ１４８）。
【００１１】
（３）ユーザＢ１３０による署名検証
ユーザＢ１３０は、
（式６） ｓ＊Ｒ１＝ｍ＊Ｇ＋ｒｘ＊ＹＡ
が成立するかどうか判定することにより、送信者であるユーザＡ１１０の身元を確認する（ステップＳ１４９）。これは、

となることから明らかであるである。
【００１２】
４．楕円曲線上の点の加算、２倍算の演算による計算量
上記に示した楕円曲線上の離散対数問題を応用したエルガマル署名によるデジタル署名方式における公開鍵の生成、署名生成、署名検証のそれぞれにおいて、楕円曲線上の点の冪倍演算が行われる。例えば、式３に示す「ｘＡ＊Ｇ」、式４に示す「ｋ＊Ｇ」、式６に示す「ｓ＊Ｒ１」、「ｍ＊Ｇ」、「ｒｘ＊ＹＡ」は、楕円曲線上の点のスカラ倍演算である。
【００１３】
楕円曲線の演算公式については、"Efficient elliptic curve exponentiation"（Miyaji, Ono, and Cohen著、Advances in cryptology-proceedings of ICICS'97, Lecture notes in computer science, 1997, Springer-verlag, 282-290.）に詳しく説明されている。
【００１４】
楕円曲線の演算公式について、以下に説明する。楕円曲線の方程式をｙ＾２ ＝ ｘ＾３ ＋ａ×ｘ＋ｂ とし、任意の点Ｐの座標を（ｘ１，ｙ１）とし、任意の点Ｑの座標を（ｘ２，ｙ２）とする。ここで、Ｒ＝Ｐ＋Ｑで定まる点Ｒの座標を（ｘ３，ｙ３）とする。
【００１５】
なお、この明細書において、記号＾は、べき乗の演算を示し、例えば、２＾３は、２×２×２を意味する。Ｐ≠Ｑの場合、Ｒ＝Ｐ＋Ｑは、加算の演算となる。加算の公式を以下に示す。
ｘ３＝｛（ｙ２−ｙ１）／（ｘ２−ｘ１）｝＾２−ｘ１−ｘ２
ｙ３＝｛（ｙ２−ｙ１）／（ｘ２−ｘ１）｝（ｘ１−ｘ３）−ｙ１
Ｐ＝Ｑの場合、Ｒ＝Ｐ＋Ｑ＝Ｐ＋Ｐ＝２×Ｐとなり、Ｒ＝Ｐ＋Ｑは、２倍算の演算となる。２倍算の公式を以下に示す。
ｘ３＝｛（３ｘ１＾２＋ａ）／２ｙ１｝＾２−２ｘ１
ｙ３＝｛（３ｘ１＾２＋ａ）／２ｙ１｝（ｘ１−ｘ３）−ｙ１
【００１６】
なお、上記演算は、楕円曲線が定義される有限体上での演算である。上記に示すように、２項組座標であるアフィン座標、すなわち今まで述べてきた座標において、楕円曲線上の加算演算を行う場合に、楕円曲線上の加算１回につき、１回の有限体上の逆数計算が必要となる。一般に、有限体上の逆数計算は、有限体上での乗算計算と比較して、１０倍程度の計算量を必要とする。
【００１７】
そこで、計算量を削減することを目的として、射影座標と呼ばれる３項組の座標が用いられる。射影座標とは、３項組Ｘ、Ｙ、Ｚからなる座標のことであって、座標（Ｘ，Ｙ，Ｚ）と座標（Ｘ'，Ｙ'，Ｚ'）とに対して、ある数ｎが存在して、Ｘ'＝ｎＸ、Ｙ'＝ｎＹ、Ｚ'＝ｎＺなる関係があるならば、（Ｘ，Ｙ，Ｚ）＝（Ｘ'，Ｙ'，Ｚ'）とするものである。
アフィン座標（ｘ，ｙ）と射影座標（Ｘ，Ｙ，Ｚ）とは、
（ｘ，ｙ） → （ｘ，ｙ，１）
（Ｘ，Ｙ，Ｚ）→ （Ｘ／Ｙ，Ｙ／Ｚ） （Ｚ≠０のとき）
なる関係で、互いに対応している。ここで、記号→は、次に示す意味で用いている。元Ｐ１に、元Ｐ２の一つの元が対応するとき、Ｐ１→Ｐ２と表記する。零元Ｏは、射影座標で表せ、Ｏ＝（０，１，０）となる。
【００１８】
以下、楕円曲線の演算は、すべて、射影座標で行われるものとする。次に、射影座標上の楕円曲線の加算公式、２倍公式について説明する。これらの公式は、もちろん、前に述べたアフィン座標における加算公式、２倍公式と整合性のあるものである。冪倍の演算は、楕円曲線上の点の加算、２倍算の演算の繰り返しによって実現できる。この冪倍の演算のうち、加算の計算量は、楕円曲線のパラメータに依存しないが、２倍算の計算量は、楕円曲線のパラメータに依存する。
【００１９】
ここでは、ｐを１６０ビットの素数とし、有限体ＧＦ（ｐ）上の楕円曲線をＥ：ｙ＾２ ＝ ｘ＾３ ＋ａｘ＋ｂ とし、楕円曲線Ｅ上の元Ｐ、Ｑをそれぞれ、Ｐ＝（Ｘ１，Ｙ１，Ｚ１）、 Ｑ＝（Ｘ２，Ｙ２，Ｚ２）で表すとき、
Ｒ＝（Ｘ３，Ｙ３，Ｚ３）＝Ｐ＋Ｑ
を以下のようにして、求める。
【００２０】
（ｉ）Ｐ≠Ｑの場合
この場合、加算の演算となる。
(step 1-1) 中間値の計算
以下を計算する。
（式８） Ｕ１＝Ｘ１×Ｚ２＾２
（式９） Ｕ２＝Ｘ２×Ｚ１＾２
（式１０） Ｓ１＝Ｙ１×Ｚ２＾３
（式１１） Ｓ２＝Ｙ２×Ｚ１＾３
（式１２） Ｈ＝Ｕ２−Ｕ１
（式１３） ｒ＝Ｓ２−Ｓ１
【００２１】
(step 1-2) Ｒ＝（Ｘ３，Ｙ３，Ｚ３）の計算
以下を計算する。
（式１４） Ｘ３＝−Ｈ＾３−２×Ｕ１×Ｈ＾２＋ｒ＾２
（式１５） Ｙ３＝−Ｓ１×Ｈ＾３＋ｒ×（Ｕ１×Ｈ＾２−Ｘ３）
（式１６） Ｚ３＝Ｚ１×Ｚ２×Ｈ
【００２２】
（ii）Ｐ＝Ｑの場合（すなわち、Ｒ＝２Ｐ）
この場合、２倍算の演算となる。
(step 2-1) 中間値の計算
以下を計算する。
（式１７） Ｓ＝４×Ｘ１×Ｙ１＾２
（式１８） Ｍ＝３×Ｘ１＾２＋ａ×Ｚ１＾４
（式１９） Ｔ＝−２×Ｓ＋Ｍ＾２
【００２３】
(step 2-2) Ｒ＝（Ｘ３，Ｙ３，Ｚ３）の計算
以下を計算する。
（式２０） Ｘ３＝Ｔ
（式２１） Ｙ３＝−８×Ｙ１＾４＋Ｍ×（Ｓ−Ｔ）
（式２２） Ｚ３＝２×Ｙ１×Ｚ１
【００２４】
次に、楕円曲線の加算、２倍算を行う場合の計算量について説明する。ここで、有限体ＧＦ（ｐ）上の１回の乗算による計算量を１Ｍｕｌ、１回の２乗算による計算量を１×Ｓｑで表す。なお、一般のマイクロプロセッサにおいては、１×Ｓｑ≒０．８×Ｍｕｌである。
【００２５】
上記の例によると、Ｐ≠Ｑの場合に示されている楕円曲線上の加算の計算量は、式８〜式１６において、乗算の回数及び２乗算の回数をカウントすることにより得られ、１２×Ｍｕｌ＋４×Ｓｑである。これは、式８、９、１０、１１、１４、１５、１６における加算の計算量は、それぞれ、１×Ｍｕｌ＋１×Ｓｑ、１×Ｍｕｌ＋１×Ｓｑ、２×Ｍｕｌ、２×Ｍｕｌ、２×Ｍｕｌ＋２×Ｓｑ、２×Ｍｕｌ、２×Ｍｕｌであることから明らかである。
【００２６】
また、上記の例によると、Ｐ＝Ｑの場合に示されている楕円曲線上の２倍算の計算量は、式１７〜式２２において、乗算の回数及び２乗算の回数をカウントすることにより得られ、４×Ｍｕｌ＋６×Ｓｑである。これは、式１７、１８、１９、２１、２２における２倍算の計算量は、それぞれ、１×Ｍｕｌ＋１×Ｓｑ、１×Ｍｕｌ＋３×Ｓｑ、１×Ｓｑ、１×Ｍｕｌ＋１×Ｓｑ、１×Ｍｕｌであることから明らかである。
【００２７】
なお、上記回数のカウントにおいて、例えば、式１４のＨ＾３については、
Ｈ＾３＝Ｈ＾２×Ｈ
と展開できるので、Ｈ＾３の計算量は、１×Ｍｕｌ＋１×Ｓｑとし、式１８のＺ１＾４については、
Ｚ１＾４＝（Ｚ１＾２）＾２
と展開できるので、Ｚ１＾４の計算量は、２Ｓｑとする。
【００２８】
また、式１４のＨ＾２については、前述のＨ＾３の計算のプロセスにおいて、Ｈ＾２が算出されているので、Ｈ＾２の計算量は再度カウントしない。また、乗算の回数のカウントの際、ある値に小さい値を乗じて行われる乗算の回数は、カウントしない。その理由を以下に説明する。ここで言う小さい値とは、式８〜式２２において、乗算の対象となる小さい固定値であり、具体的には、２、３、４、８などの値である。これらの値は、多くとも４ビットの２進数で表現できる。一方、その他の変数は、通常、１６０ビットの値を有している。
【００２９】
一般に、マイクロプロセッサにおいて、乗数と被乗数との乗算は、被乗数のシフトと加算の繰り返しにより行われる。すなわち、２進数で表現される乗数の各ビット毎に、このビットが１であるならば、２進数で表現される被乗数の最下位ビットが、このビットの存在する位置に一致するように、被乗数をシフトして、１つのビット列を得る。乗数の全ビットについて、このようにして得られた少なくとも１つのビット列をすべて加算する。
【００３０】
例えば、１６０ビットの乗数と１６０ビットの被乗数との乗算においては、１６０ビットの被乗数を１６０回シフトし、１６０個のビット列を得、得られた１６０個のビット列を加算する。一方、４ビットの乗数と１６０ビットの被乗数との乗算においては、１６０ビットの被乗数を４回シフトし、４個のビット列を得、得られた４個のビット列を加算する。
【００３１】
乗算は、上記に示すようにして行われるので、乗算がある値に小さい値を乗じて行われる場合には、前記繰り返しの回数が少なくなる。従って、その計算量は少ないと見なせるので、乗算の回数にカウントしない。以上説明したように、楕円曲線の２倍算を行う場合において、式１８には、楕円曲線のパラメータａが含まれている。このパラメータａの値として、例えば、小さい値を採用すると、楕円曲線上の２倍算の計算量は、１Ｍｕｌ分削減でき、３Ｍｕｌ＋６Ｓｑとなる。なお、加算に関しては、楕円曲線のパラメータを変化させても、計算量は変わらない。
【００３２】
楕円曲線のスカラ倍演算は次のように行う。
（従来例１）ｐを１６０ビットの素数とし、有限体ＧＦ（ｐ）上の楕円曲線をＥとし、Ｅ（ＧＦ（ｐ））の任意の元をＧとする。これらのパラメータを基にｋ＊Ｇの計算をする。ここで、ｋの２進表現を、

とする。
ｓｔｅｐ１：ｃ＝１５９、Ｓ＝Ｏとする。
ｓｔｅｐ２：ｋ［ｃ］＝１のとき、Ｓ←Ｓ＋Ｇとする。
ｓｔｅｐ３：ｃ←ｃ−１とする。
ｓｔｅｐ４：ｃ＜０であれば、Ｓを出力して終了。それ以外は、Ｓ←Ｓ＋Ｓとして、ｓｔｅｐ２へ。
【００３３】
上記の計算量は、ｋ［ｃ］＝１になる確率を１／２と考え、１回の楕円曲線加算をＥＡｄｄ、２倍算をＥＤｏｂとすると、８０×ＥＡｄｄ＋１６０×ＥＤｏｂとなる。一般に、ｐ、ｋをそれぞれｎビットの素数、整数とするとき、計算量は、
１／２×ｎ×ＥＡｄｄ＋ｎ×ＥＤｏｂ
である。
【００３４】
上記のスカラ倍演算において、（２＾ｉ）＊Ｇ（ｉ＝１、２、……、１５９）を予め計算しておき、その結果をテーブルに保存している場合、以下のように計算可能である。
【００３５】
（従来例２）
ｐを１６０ビットの素数とし、有限体ＧＦ（ｐ）上の楕円曲線をＥとし、Ｅ（ＧＦ（ｐ））の任意の元をＧとする。また、（２＾ｉ）＊Ｇ（ｉ＝１、２、……、１５９）の座標を予め計算しているものとする。このとき、これらのパラメータを基にｋ＊Ｇの計算をする。
ｓｔｅｐ１：ｃ＝１５９，Ｓ＝Ｏとする。
ｓｔｅｐ２：ｋ［ｃ］＝１のとき、Ｓ←Ｓ＋２＾ｃ＊Ｇとする。
ｓｔｅｐ３：ｃ←ｃ−１とする。
ｓｔｅｐ４：ｃ＜０であれば、Ｓを出力して終了。それ以外は、ｓｔｅｐ２へ。
【００３６】
上記方法では、楕円曲線加算を行わないので、計算量は、８０×ＥＡｄｄである。一般に、ｐ、ｋをそれぞれｎビットの素数、整数とするとき、計算量は、１／２×ｎ×ＥＤｏｂである。このように、（２＾ｉ）＊Ｇを予め計算するため、計算量が削減できる。従来例２は、３のエルガマル署名における楕円曲線のベース点Ｇのスカラ倍演算で使用できる。これは、ベース点Ｇはシステムパラメータであるためである。
【００３７】
５．モンゴメリ型楕円曲線
上記の楕円曲線は、その方程式がｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂの形をしているもののみである。この楕円曲線はワイヤーシュトラス型楕円曲線とよばれる。一方、方程式がＥｍ：Ｂ×ｙ＾２＝ｘ＾３＋Ａ×ｘ＾２＋ｘの形をしている楕円曲線をモンゴメリ型楕円曲線とよぶ。この楕円曲線Ｅｍ上の点Ｇを取り、そのｎ１倍点及びｎ２倍点をそれぞれ、ｎ１＊Ｇ＝（Ｘ１，Ｙ１，Ｚ１）、 ｎ２＊Ｇ＝（Ｘ２，Ｙ２，Ｚ２）、（ｎ１−ｎ２）＊Ｇ＝（Ｘ３'，Ｙ３'，Ｚ３'）で表すとき、
（ｎ１＋ｎ２）＊Ｇ＝（Ｘ３，Ｙ３，Ｚ３）＝ｎ１＊Ｇ＋ｎ２＊Ｇ
を以下のようにして、求める。
【００３８】
（ｉ）ｎ１≠ｎ２のとき（加算）
（ｓｔｅｐ１−１）中間値の計算
Ｕ１＝Ｘ１＋Ｚ１
Ｕ２＝Ｘ２＋Ｚ２
Ｖ１＝Ｘ１−Ｚ１
Ｖ２＝Ｘ２−Ｚ２
（ｓｔｅｐ１−２）（ｎ１＋ｎ２）＊Ｇ＝（Ｘ３，Ｙ３，Ｚ３）の計算
Ｘ３＝Ｚ３'×（Ｖ１×Ｕ２＋Ｕ１×Ｖ２）＾２
Ｚ３＝Ｘ３'×（Ｖ１×Ｕ２−Ｕ１×Ｖ２）＾２
【００３９】
（ｉｉ）ｎ１＝ｎ２のとき（２倍算）
（ｓｔｅｐ２−１）中間値の計算
Ｕ１＝Ｘ１＋Ｚ１
Ｖ１＝Ｘ１−Ｚ１
（ｓｔｅｐ２−２）（ｎ１＋ｎ２）＊Ｇ＝（Ｘ３，Ｙ３，Ｚ３）の計算
Ｘ３＝Ｖ１＾２×Ｕ１＾２
Ｚ３＝（４×Ｘ１×Ｚ１）×（Ｖ１＾２＋（Ａ＋２）／４×（４×Ｘ１×Ｚ１）
【００４０】
ｓｔｅｐ２−２の「（Ａ＋２）／４」は予め計算可能であるため無視すると、それぞれの計算量は、加算が４×Ｍｕｌ＋２×Ｓｑ（Ｚ３'＝１のときは３×Ｍｕｌ＋２×Ｓｑ）、２倍算が３×Ｍｕｌ＋２×Ｓｑになる。上記４で述べたようにワイヤーシュトラス型楕円曲線の点の加算、２倍算の計算量は、それぞれ、１２×Ｍｕｌ＋４×Ｓｑ、４×Ｍｕｌ＋６×Ｓｑである。よって、モンゴメリ型楕円曲線の方が点の加算、２倍算が高速である。なお、モンゴメリ型楕円曲線においても、（Ｘ１，Ｙ１，Ｚ１）の（−１）倍は、（Ｘ１，−Ｙ１，Ｚ１）である。モンゴメリ型楕円曲線については、"Speeding the Pollar and Elliptic Curve Methods of Factorization"(P.L.Montgomery著, Math. of Comp. 48, 1987, pp.243-264)が詳しい。
【００４１】
以上のように、モンゴメリ型楕円曲線は高速演算が可能である。しかし、ｎ１＊Ｇとｎ２＊Ｇの加算において、（ｎ１−ｎ２）＊Ｇの座標が必要になるため、スカラ倍演算において、ワイヤーシュトラス型楕円曲線のように２進展開ができない。例えば、５＊Ｇを計算する場合、５＝２×２＋１であるため、２＊Ｇを計算した後、２＊（２＊Ｇ）＝４＊Ｇを計算し、さらに（４＊Ｇ）＋Ｇを計算する。（２＊２＊Ｇ）とＧの加算において、それらの点の差（２×２−１）＊Ｇ＝３＊Ｇを求めなければならない。したがって、従来例１のようなスカラ倍演算方法が使用できない。
【００４２】
そこで、以下のようにして計算する。
（従来例３）
ｐをｎビットの素数として、ＥをＧＦ（ｐ）上のモンゴメリ型楕円曲線、ＧをＥ（ＧＦ（ｐ））の元とする。ｋ＝２＾（ｎ−１）＋ｋ［１］×２＾（ｎ−２）＋……＋ｋ［ｎ−２］×２＋ｋ［ｎ−１］として、ｋ＊Ｇの計算をする。
Ｓ［ｉ］，Ｔ［ｉ］を以下のように定義する。
Ｓ［ｉ］＝（２＾ｉ＋ｋ［１］×２＾（ｉ−１）＋……＋ｋ［ｉ−１］×２＋ｋ［ｉ］）＊Ｇ
Ｔ［ｉ］＝Ｓ［ｉ］＋Ｇ
ｓｔｅｐ１：ｉ＝１、Ｓ［０］＝Ｇとする。
ｓｔｅｐ２：Ｔ［０］＝２＊Ｇを計算する。
ｓｔｅｐ３：ｋ［ｉ＋１］＝０であるか判定し、ｋ［ｉ＋１］＝０のとき、以下のようにする。
【００４３】
Ｓ［ｉ＋１］＝２＊Ｓ［ｉ］
Ｔ［ｉ＋１］＝Ｓ［ｉ］＋Ｔ［ｉ］
それ以外は、以下のように計算する
Ｓ［ｉ＋１］＝Ｓ［ｉ］＋Ｔ［ｉ］
Ｔ［ｉ＋１］＝２＊Ｔ［ｉ］
ｓｔｅｐ４：ｉ←ｉ＋１とする。
ｓｔｅｐ５：ｉ＞ｎ−１であるか判定し、ｉ＞ｎである場合、Ｓ［ｎ］をｋ＊Ｇとして出力する。それ以外は、ｓｔｅｐ３へ。
【００４４】
図２６は、このような従来例３におけるスカラ倍演算の計算手順を模式的に示す計算フロー図である。ここでは、右から左に向かって、加算又は２倍算を繰り返す様子が示されている。なお、本図において、実線矢印は楕円曲線上の加算を示し、点線矢印は楕円曲線上の２倍算を示し、矢印上の円で囲まれた数値は加算の順番（それまでに行った加算の合計回数）を示し、矢印上の括弧で囲まれた数値は２倍算の順番（それまでに行った２倍算の合計回数）を示す。例えば、第１の加算（丸数値１の加算）は、Ｇと２＊Ｇとの楕円曲線上の加算を行って３＊Ｇを算出することを示し、また、第１の２倍算（括弧付き数値１の加算）は、Ｇに対して楕円曲線上の２倍算を行って２＊Ｇを算出することを示している。
【００４５】
この方法によれば、加算の対象となる２つの要素（加算要素）の差が常にＧ（既知）となっているので、その差の算出手間が不要となり、その計算量は、加算と２倍算に要する正味の時間、つまり、ｎ×ＥＡｄｄ＋ｎ×ＥＤｏｂで済む。
【００４６】
具体的には、Ｇが既知であることから、Ｚ座標が１と考えることができるため、ＥＡｄｄ＝３×Ｍｕｌ＋２×Ｓｑ、ＥＤｏｂ＝３×Ｍｕｌ＋２×Ｓｑである。ただし、Ｍｕｌ、Ｓｑはそれぞれ、ＧＦ（ｐ）の乗算、２乗算の計算量であり、一般にＳｑ＝０．８×Ｍｕｌである。これらの式を代入すると、従来例３の計算量は、
ｎ×（３×Ｍｕｌ＋２×Ｓｑ）＋ｎ×（３×Ｍｕｌ＋２×Ｓｑ）＝６×ｎ×Ｍｕｌ＋４×ｎ×Ｓｑ＝４６／５×ｎ×Ｍｕｌ
となる。
【００４７】
【発明が解決しようとする課題】
しかしながら、上記従来例３の計算方法は、従来例２のように（２＾ｉ）＊Ｇを予め計算しておく（テーブルを利用する）ことを考えると、（２＾ｉ）＊Ｇの点を使用するアルゴリズムとはなっていないために、従来例２にようには計算量が削減されず、（２＾ｉ）＊Ｇを予め計算することのメリットが少ない。また、モンゴメリ型楕円曲線のスカラ倍演算において、このような（２＾ｉ）＊Ｇなどのスカラ倍点を予め計算することが有効になるような方法が存在しない。したがって、モンゴメリ型楕円曲線は、従来例３のようにスカラ倍点のテーブルをもたない方法においては高速であるが、テーブルをもつ場合に有効な方法が存在しないという問題を有している。
【００４８】
つまり、従来のモンゴメリ型楕円曲線のスカラ倍演算方法は、ある点の２のべき乗倍（スカラ倍）点のテーブルをもつ場合に有効な方法になっていないという問題点がある。
そこで、本発明は、モンゴメリ型楕円曲線におけるスカラ倍演算方法において、ある点Ｇの２のべき乗倍等の一定のスカラ倍点の座標を格納したテーブルを有効活用することが可能な高速な楕円曲線演算装置を提供することを目的とする。
【００４９】
【課題を解決するための手段】
上記目的を達成するために、本発明に係る楕円曲線演算装置は、ｎビットの任意の整数ｋを入力とし、予め与えられた有限体Ｆ上のモンゴメリ型楕円曲線Ｅ上の点Ｇに対して、スカラ倍点ｋ＊Ｇを出力する楕円曲線演算装置であって、Ｇ，２＊Ｇ，（２＾２）＊Ｇ，…，（２＾（ｎ−１））＊Ｇのいずれかを第１加算要素とする前記楕円曲線Ｅ上の加算を繰り返すことによって前記スカラ倍点ｋ＊Ｇを算出するスカラ倍演算手段を備えることを特徴とする。
【００５０】
ここで、前記楕円曲線演算装置は、さらに、前記楕円曲線Ｅ上の加算の繰り返し手順を示す計算手順を生成する計算手順生成手段を備え、前記スカラ倍演算手段は、前記計算手順生成手段が生成した計算手順に従って前記スカラ倍点ｋ＊Ｇを算出してもよい。
【００５１】
また、前記計算手順生成手段は、自然数ｍ，ｕに対して、（２＾（ｍ−１）＋ｕ）＊Ｇ、（２＾（ｍ−１））＊Ｇ及びｕ＊Ｇから（２＾ｍ＋ｕ）＊Ｇを算出する第１計算、又は、（２＾ｍ）＊Ｇ、（２＾ｍ−ｕ）＊Ｇ及びｕ＊Ｇから（２＾（ｍ＋１）−ｕ）＊Ｇを算出する第２計算、又は、（２＾ｍ）＊Ｇ、−（２＾ｍ−ｕ）＊Ｇ及び（２＾（ｍ＋１）−ｕ）＊Ｇからｕ＊Ｇを算出する第３計算を前記楕円曲線Ｅ上の加算とする計算手順を生成してもよい。
【００５２】
また、前記計算手順生成手段は、前記ｋの各ビットの値に応じて、前記楕円曲線Ｅ上の加算と前記第１〜第３計算の少なくとも１つとを対応づけることにより、前記計算手順を生成してもよい。
【００５３】
また、前記計算手順生成手段は、前記ｋのビットの値が０である場合には、そのビットに対応する前記楕円曲線Ｅ上の加算として少なくとも前記第１計算を対応させ、前記ビットの値が１である場合には、そのビットに対応する前記楕円曲線Ｅ上の加算として少なくとも前記第２計算を対応させることにより、前記計算手順を生成してもよい。
【００５４】
また、前記計算手順生成手段は、前記楕円曲線Ｅ上の加算の繰り返しにおける個々の加算において、前記第１加算要素と加算される第２加算要素の表現形式が前記第１計算におけるプラス表現（２＾（ｍ−１）＋ｕ）＊Ｇであるか、前記第２計算におけるマイナス表現（２＾ｍ−ｕ）＊Ｇであるかを特定する表現形式情報を前記計算手順として生成し、前記スカラ倍演算手段は、前記楕円曲線Ｅ上の加算の繰り返しにおける個々の加算においては、前記表現形式情報に基づいて、前記第１〜第３計算のいずれかの計算を行ってもよい。
【００５５】
また、前記表現形式情報は、前記楕円曲線Ｅ上の加算の繰り返しにおける加算ごとに、前記第２加算要素が前記プラス表現及び前記マイナス表現のいずれの表現からいずれの表現に切り替わるかを示す情報であってもよいし、前記楕円曲線Ｅ上の加算の繰り返しにおいて、前記第２加算要素が前記プラス表現及び前記マイナス表現のいずれかの表現形式で連続して出現する個数を示す情報であってもよい。
【００５６】
また、前記スカラ倍演算手段は、Ｇ，２＊Ｇ，（２＾２）＊Ｇ，…，（２＾（ｎ−１））＊Ｇの少なくとも一部を記憶するテーブル記憶部を有し、前記テーブル記憶部に記憶された点を第１加算要素として前記楕円曲線Ｅ上の加算を行ってもよい。
【００５７】
また、本発明に係る楕円曲線演算装置は、ｎビットの任意の整数ｋを入力とし、予め与えられた有限体Ｆ上のモンゴメリ型楕円曲線Ｅ上の点Ｇに対して、スカラ倍点ｋ＊Ｇを出力する楕円曲線演算装置であって、２＊Ｇ，３＊Ｇ，６＊Ｇ，１２＊Ｇ，…，（２＾（ｎ−１）＋２＾（ｎ−２））＊Ｇのいずれかを第１加算要素とする前記楕円曲線Ｅ上の加算を繰り返すことによって前記スカラ倍点ｋ＊Ｇを算出するスカラ倍演算手段を備えるとしてもよい。
【００５８】
ここで、前記楕円曲線演算装置は、さらに、前記楕円曲線Ｅ上の加算の繰り返し手順を示す計算手順を生成する計算手順生成手段を備え、前記スカラ倍演算手段は、前記計算手順生成手段が生成した計算手順に従って前記スカラ倍点ｋ＊Ｇを算出してもよい。
【００５９】
また、前記計算手順生成手段は、自然数ｍ，ｕに対して、第１加算要素（２＾（ｍ−１）＋２＾（ｍ−２））＊Ｇ、第２加算要素（２＾（ｍ−２）＋ｕ）＊Ｇ及び前記第１加算要素と前記第２加算要素との差（２＾（ｍ−１）−ｕ）から（２＾ｍ＋ｕ）＊Ｇを算出する第１計算、又は、第１加算要素（２＾ｍ＋２＾（ｍ−１））＊Ｇ、第２加算要素（２＾（ｍ−１）−ｕ）＊Ｇ及び前記第１加算要素と前記第２加算要素との差（２＾ｍ＋ｕ）から（２＾（ｍ＋１）−ｕ）＊Ｇを算出する第２計算を前記楕円曲線Ｅ上の加算とする計算手順を生成してもよい。
【００６０】
また、前記計算手順生成手段は、前記第１又は前記第２計算による楕円曲線Ｅ上の加算によって得られた結果を、次の繰り返し加算における第２加算要素とするか第１加算要素と第２加算要素との差とするかを示す分割対象情報を前記計算手順として生成してもよい。
【００６１】
また、前記スカラ倍演算手段は、２＊Ｇ，３＊Ｇ，６＊Ｇ，１２＊Ｇ，…，（２＾（ｎ−１）＋２＾（ｎ−２））＊Ｇの少なくとも一部を記憶するテーブル記憶部を有し、前記テーブル記憶部に記憶された点を第１加算要素として前記楕円曲線Ｅ上の加算を行ってもよい。
【００６２】
さらに、本発明は、上記楕円曲線演算装置を用いた暗号装置や復号装置として実現したり、上記手段をステップとする楕円曲線演算方法として実現したり、上記手段としてコンピュータに機能させるプログラムとして実現したり、そのようなプログラムが記録されたコンピュータ読み取り可能な記録媒体として実現したりすることもできる。
【００６３】
【発明の実施の形態】
以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。
［実施の形態１］
１．楕円曲線演算装置２００の構成
図１は、実施の形態１における楕円曲線演算装置２００の構成を示す機能ブロック図である。この楕円曲線演算装置２００は、専用のプログラムを実行するコンピュータ装置又はＬＳＩ等の論理回路で実現され、有限体ＧＦ（ｐ）上のモンゴメリ型楕円曲線Ｅ：Ｂ×ｙ＾２＝ｘ＾３＋Ａ×ｘ＾２＋ｘのパラメータｐ（素数）、ＧＦ（ｐ）の元A、Bと、Ｅ（ＧＦ（ｐ））に属する点Ｇと、その（２＾ｉ）＊Ｇ（ｉ＝１，２，……，ｎ−１）を予め与えられ、ｎビットの任意のｋを入力として、点Ｇのスカラ倍ｋ＊Ｇを出力する演算装置であり、点Ｇの２のべき乗倍（２＾ｉ）＊Ｇを有効活用しながら計算する点に特徴を有し、計算手順生成部２１０とスカラ倍演算部２２０とから構成される。なお、上記ｎはｋのビット数を示している。
【００６４】
（計算手順生成部２１０の処理）
計算手順生成部２１０は、点Ｇのスカラ倍ｋ＊Ｇを算出するための計算手順を生成する予備計算を実行する処理部であり、ｋ＊ＧをＧの２のべき乗倍（２＾ｉ）＊Ｇを用いた加算形に分割することを繰り返すことによって加算要素を特定する加算要素特定部２１０ａと、加算要素特定部２１０ａによって特定された加算要素を配列として出力する配列生成出力部２１０ｂとからなる。
【００６５】
具体的には、計算手順生成部２１０は、図２に示されるフローチャートのように、整数ｋを入力として、計算手順を示す配列ＣＳ［ｉ］（ｉ＝１，２，……）を出力する。ここで、１つの配列ＣＳ［ｉ］は、１つの加算を特定する４つの要素、即ち、（加算結果、第１加算要素、第２加算要素、第１加算要素と第２加算要素との差）からなる。なお、第１加算要素及び第２加算要素の少なくとも１つは、点Ｇの２のべき乗倍である。
【００６６】
加算要素特定部２１０ａは、以下の手順に従って、配列ＣＳ［ｉ］を特定する。
ステップＳ２０１：ｗ←ｋとする。ただし、ｗ←ｋはｗにｋを代入することを示している。
ステップＳ２０２：カウンタｃ←１、ｏｌｄｆｌａｇ←０、ｎｅｗｆｌａｇ←０とする。
ステップＳ２０３：ｗ＝２＾（｜ｗ｜−１）＋ｕとなるようにｕをおく。ここで、｜ｗ｜はｗのビット数を示している。
ステップＳ２０４：ｗ＝２＾｜ｗ｜−ｖとなるようにｖをおく。
ステップＳ２０５：ｕ＞ｖであるか判定する。成り立つ場合は、ステップＳ２０６へ。成り立たない場合は、ステップＳ２０７へ。
ステップＳ２０６：ｎｅｗｆｌａｇを１とし、計算手順ＣＳ［ｃ］をタイプＩの値、即ち、［（２＾｜ｗ｜−ｖ）＊Ｇ，（２＾（｜ｗ｜−１））＊Ｇ，（２＾（｜ｗ｜−１）−ｖ）＊Ｇ，ｖ＊Ｇ］と定め、ｗ←２＾（｜ｗ｜−１）−ｖとする。ステップＳ２１０へ。
【００６７】
ここで、計算手順［ｘ１＊Ｇ，ｘ２＊Ｇ，ｘ３＊Ｇ，ｘ４＊Ｇ］は，ｘ２＊Ｇとｘ３＊Ｇとの楕円曲線加算ｘ１＊Ｇをｘ２＊Ｇ，ｘ３＊Ｇ，ｘ４＊Ｇ（＝ｘ２＊Ｇ−ｘ３＊Ｇ）を用いて計算することを示している。
ステップＳ２０７：ｏｌｄｆｌａｇ＝１であるか判定する。成り立つ場合は、ステップＳ２０８へ。成り立たない場合は、ステップＳ２０９へ。
ステップＳ２０８：計算手順ＣＳ［ｃ］をタイプＩＩの値、即ち、［ｖ＊Ｇ，（２＾｜ｖ｜）＊Ｇ，−（２＾｜ｖ｜−ｖ）＊Ｇ，ｗ＊Ｇ］として、ｃ←ｃ＋１とする。
ステップＳ２０９：ｎｅｗｆｌａｇを０として、計算手順ＣＳ［ｃ］をタイプＩＩＩの値、即ち、［（２＾（｜ｗ｜−１）＋ｕ）＊Ｇ，（２＾（｜ｗ｜−２）＋ｕ）＊Ｇ，（２＾（｜ｗ｜−２））＊Ｇ，ｕ＊Ｇ］と定め、ｗ←２＾（｜ｗ｜−２）＋ｕとする。
ステップＳ２１０：ｏｌｄｆｌａｇ←ｎｅｗｆｌａｇ，ｃ←ｃ＋１，ｗ←とする。
ステップＳ２１１：ｗ＝３×２＾ｅ（ｅ≧０）とおけるか判定する。成り立つ場合は、ステップＳ２１２へ。成り立たない場合は、ステップＳ２０３へ。
ステップＳ２１２：ＣＳ［ｃ］をタイプＩＶの値、即ち、［（３×２＾ｅ）＊Ｇ，（２＾（ｅ−１））＊Ｇ，（２＾ｅ）＊G，（２＾ｅ）＊G］と定める。最後に、配列生成出力部２１０ｂは、加算要素特定部２１０ａによって特定された全ての計算手順ＣＳ［ｉ］（ｉ＝１，２，……）とｃとをスカラ倍演算部２２０に出力し、終了する。
【００６８】
（スカラ倍演算部２２０の処理）
スカラ倍演算部２２０は、計算手順生成部２１０から出力された計算手順ＣＳ［ｉ］（ｉ＝１，２，……）とカウンタｃとに基づいて、楕円曲線上の加算を繰り返すことで、最終的な計算結果ｋ＊Ｇを算出し出力する演算部であり、点Ｇの２のべき乗倍（（２＾ｉ）＊Ｇ；ｉ＝１，２，…）を予め記憶しているテーブル記憶部２２０ｂ、ワーキング用のメモリである一時記憶部２２０ｃ、楕円曲線上での加算を行う加算器である楕円加算部２２０ｄ及び計算手順生成部２１０からの計算手順ＣＳ［ｉ］に従って各構成要素２２０ｂ〜２２０ｄを制御する演算制御部２２０ａからなる。
【００６９】
このスカラ倍演算部２２０は、図３に示されるフローチャートに従って、ｋ＊Ｇを算出する。具体的には、演算制御部２２０ａは、以下のステップで、計算・制御を行う。
ステップＳ３０１：カウンタｄにｃを代入する。
ステップＳ３０２：ＣＳ［ｃ］を読み出し（Ｓ３０２ａ）、その計算手順［ｘ１＊Ｇ，ｘ２＊Ｇ，ｘ３＊Ｇ，ｘ４＊Ｇ］に従って、楕円加算部２２０ｄに、楕円曲線加算を実行させ、点ｘ１＊Ｇ（＝ｘ２＊Ｇ＋ｘ３＊Ｇ）を算出させる（Ｓ３０２ｂ）。このとき、（２＾ｉ）＊Ｇ（２のべき乗倍）については、テーブル記憶部２２０ｂから読み出した値を用いることとし、得られた加算結果ｘ１＊Ｇについては、一時記憶部２２０ｃに格納し、次の計算で使用するように楕円加算部２２０ｄを制御する。
ステップＳ３０３：ｄ←ｄ−１とする。
ステップＳ３０４：ｄ＝０であるか判定する（Ｓ３０４ａ）。成り立つ場合、楕円加算部２２０ｄに、最後に計算した結果ｘ１＊Ｇを出力させ、終了する（Ｓ３０４ｂ）。成り立たない場合は、ステップＳ３０２へ。
【００７０】
ここで、上記のステップで使用される楕円曲線上の加算方法を以下に示す。
Ｐ＝（Ｘ１，Ｙ１，Ｚ１）、 Ｑ＝（Ｘ２，Ｙ２，Ｚ２）、２点の差Ｐ−Ｑ＝（Ｘ３'，Ｙ３'，Ｚ３'）から、Ｐ＋Ｑ＝（Ｘ３、Ｙ３、Ｚ３）を以下のようにして求める。
（ｓｔｅｐ１−１）中間値の計算
Ｕ１＝Ｘ１＋Ｚ１
Ｕ２＝Ｘ２＋Ｚ２
Ｖ１＝Ｘ１−Ｚ１
Ｖ２＝Ｘ２−Ｚ２
（ｓｔｅｐ１−２）Ｐ＋Ｑ＝（Ｘ３，Ｙ３，Ｚ３）の計算
Ｘ３＝Ｚ３'×（Ｖ１×Ｕ２＋Ｕ１×Ｖ２）＾２
Ｚ３＝Ｘ３'×（Ｖ１×Ｕ２−Ｕ１×Ｖ２）＾２
なお、楕円曲線演算装置２００で使用するモンゴメリ型楕円曲線については、"Speeding the Pollar and Elliptic Curve Methods of Factorization"(P.L.Montgomery著, Math. of Comp. 48, 1987, pp.243-264)が詳しい。
【００７１】
（楕円曲線演算装置２００の動作）
楕円曲線演算装置２００は、入力の整数ｋを受け取り、計算手順生成部２１０へ入力する。計算手順生成部２１０は、入力された整数ｋより、計算手順ＣＳ［ｉ］（ｉ＝１，２，……）を求め、スカラ倍演算部３２０へ入力する。スカラ倍演算部３２０は、入力された計算手順ＣＳ［ｉ］（ｉ＝１，２，……）より、楕円曲線の点Ｇのスカラ倍点ｋ＊Ｇを算出し、出力する。
【００７２】
２．楕円曲線演算装置２００の数値例
以下では、ｋ＝１０２の場合の数値例を示す。
（計算手順生成部２１０における中間値）
カウンタｃの値に対する処理を以下に示す。
（カウンタｃ＝１のとき）
ステップＳ２０３：ｗ＝１０２＝２＾６＋３８であるので、ｕ←３８
ステップＳ２０４：ｗ＝１０２＝２＾７−２６であるので、ｖ←２６
ステップＳ２０５：３８＞２６であるので、ステップＳ２０６へ。
ステップＳ２０６：ｎｅｗｆｌａｇ←１、ＣＳ［１］←［（２＾７−２６）＊Ｇ（＝１０２＊Ｇ），（２＾６）＊Ｇ，（２＾６−２６）＊Ｇ（＝３８＊Ｇ），２６＊Ｇ］、ｗ←２＾６−２６＝３８、ステップＳ２１０へ。
ステップＳ２１０：ｏｌｄｆｌａｇ←ｎｅｗｆｌａｇ＝１、ｃ←ｃ＋１
ステップＳ２１１：ｗ＝３８であり３×２＾ｅで表せないため、ステップＳ２０３へ。
【００７３】
（カウンタｃ＝２のとき）
ステップＳ２０３：ｗ＝３８＝２＾５＋６であるので、ｕ←６
ステップＳ２０４：ｗ＝３８＝２＾６−２６であるので、ｖ←２６
ステップＳ２０５：６＜２６であるので、ステップＳ２０７へ。
ステップＳ２０７：ｏｌｄｆｌａｇ＝１であるので、ステップＳ２０８へ。
ステップＳ２０８：ＣＳ［２］←［２６＊Ｇ，（２＾５）＊Ｇ，−（２＾５−２６）＊Ｇ（＝−６＊Ｇ），（２＾６−２６）＊Ｇ（＝３８＊Ｇ）］、ｃ←ｃ＋１
ステップＳ２０９：ｎｅｗｆｌａｇ←０、ＣＳ［３］←［（２＾５＋６）＊Ｇ（＝３８＊Ｇ），（２＾４＋６）＊Ｇ（＝２２＊Ｇ），（２＾４）＊Ｇ，６＊Ｇ］、ｗ←２＾４＋６＝２２
ステップＳ２１０：ｏｌｄｆｌａｇ←ｎｅｗｆｌａｇ＝０，ｃ←ｃ＋１
ステップＳ２１１：ｗ＝２２であり３×２＾ｅで表せないステップＳ２０３へ。
【００７４】
（カウンタｃ＝４のとき）
ステップＳ２０３：ｗ＝２２＝２＾４＋６であるので、ｕ←６
ステップＳ２０４：ｗ＝２２＝２＾５−１０であるので、ｖ←１０
ステップＳ２０５：６＜１０であるので、ステップＳ２０７へ。
ステップＳ２０７：ｏｌｄｆｌａｇ＝０であるので、ステップＳ２０９へ。
ステップＳ２０９：ｎｅｗｆｌａｇ←０、ＣＳ［４］←［（２＾４＋６）＊Ｇ（＝２２＊Ｇ），（２＾３＋６）＊Ｇ（＝１４＊Ｇ），（２＾３）＊Ｇ，６＊Ｇ］、ｗ←２＾３＋６＝１４
ステップＳ２１０：ｏｌｄｆｌａｇ←ｎｅｗｆｌａｇ＝０，ｃ←ｃ＋１
ステップＳ２１１：ｗ＝１４であり３×２＾ｅで表せないため、ステップＳ２０３へ。
【００７５】
（カウンタｃ＝５のとき）
ステップＳ２０３：ｗ＝１４＝２＾３＋６であるので、ｕ←６
ステップＳ２０４：ｗ＝１４＝２＾４−２であるので、ｕ←２
ステップＳ２０５：６＞２であるので、ステップＳ２０６へ。
ステップＳ２０６：ｎｅｗｆｌａｇ←１、ＣＳ［５］←［（２＾４−２）＊Ｇ（＝１４＊Ｇ），（２＾３）＊Ｇ，（２＾３−２）＊Ｇ（＝６＊Ｇ），２＊Ｇ］、ｗ←２＾３−２＝６、ステップＳ２１０へ。
ステップＳ２１０：ｏｌｄｆｌａｇ←ｎｅｗｆｌａｇ＝１、ｃ←ｃ＋１
ステップＳ２１１：ｗ＝６であり、ｗ＝３×２と表せるため、ステップＳ２１２へ。
ステップＳ２１２：ＣＳ［６］←［（３×２）＊Ｇ（＝６＊Ｇ），（２＾２）＊Ｇ，２＊Ｇ，２＊Ｇ］，終了。
【００７６】
以上より、計算手順生成部２１０の出力は、
ＣＳ［１］＝［１０２＊Ｇ，（２＾６）＊Ｇ，３８＊Ｇ，２６＊Ｇ］
ＣＳ［２］＝［２６＊Ｇ，（２＾５）＊Ｇ，−６＊Ｇ，３８＊Ｇ］
ＣＳ［３］＝［３８＊Ｇ，２２＊Ｇ，（２＾４）＊Ｇ，６＊Ｇ］
ＣＳ［４］＝［２２＊Ｇ，１４＊Ｇ，（２＾３）＊Ｇ，６＊Ｇ］
ＣＳ［５］＝［１４＊Ｇ，（２＾３）＊Ｇ，６＊Ｇ，２＊Ｇ］
ＣＳ［６］＝［６＊Ｇ，（２＾２）＊Ｇ，２＊Ｇ，２＊Ｇ］
とｃ＝６である。
【００７７】
（スカラ倍演算部２２０の中間値）
次に、スカラ倍演算部２２０の処理を示す。
まず、最初にステップＳ３０１でｄにｃ＝６を代入する。以降カウンタｄに対する処理を以下に示す。
（カウンタｄ＝６のとき）
ステップＳ３０２：ＣＳ［６］＝［６＊Ｇ，（２＾２）＊Ｇ，２＊Ｇ，２＊Ｇ］であるので、２＾２＊Ｇ、２＊Ｇ及びその差２＊Ｇより楕円曲線加算を行って６＊Ｇを求める。
ステップＳ３０３：ｄ←ｄ−１＝５
ステップＳ３０４：ｄ＝５であるので、ステップＳ３０２へ。
【００７８】
（カウンタｄ＝５のとき）
ステップＳ３０２：ＣＳ［５］＝［１４＊Ｇ，（２＾３）＊Ｇ，６＊Ｇ，２＊Ｇ］であるので、（２＾３）＊Ｇ，６＊Ｇ及びその差２＊Ｇより楕円曲線加算を行って１４＊Ｇを求める。ここで、６＊Ｇはカウンタｄ＝６のときに計算済であるので、そこでの計算結果を用いる。
ステップＳ３０３：ｄ←ｄ−１＝４
ステップＳ３０４：ｄ＝４であるので、ステップＳ３０２へ。
【００７９】
（カウンタｄ＝４のとき）
ステップＳ３０２：ＣＳ［４］＝［２２＊Ｇ，１４＊Ｇ，（２＾３）＊Ｇ，６＊Ｇ］であるので、１４＊Ｇ，（２＾３）＊Ｇ及びその差６＊Ｇより楕円曲線加算を行って２２＊Ｇを求める。ここで、１４＊Ｇ及び６＊Ｇはそれぞれカウンタｄ＝５，６のときに計算済であるので、そこでの計算結果を用いる。
ステップＳ３０３：ｄ←ｄ−１＝３
ステップＳ３０４：ｄ＝３であるので、ステップＳ３０２へ。
【００８０】
（カウンタｄ＝３のとき）
ステップＳ３０２：ＣＳ［３］＝［３８＊Ｇ，２２＊Ｇ，（２＾４）＊Ｇ，６＊Ｇ］であるので、２２＊Ｇ，（２＾４）＊Ｇ及びその差６＊Ｇより楕円曲線加算を行って３８＊Ｇを求める。ここで、２２＊Ｇ及び６＊Ｇはそれぞれカウンタｄ＝４，６のときに計算済であるので、そこでの計算結果を用いる。
ステップＳ３０３：ｄ←ｄ−１＝２
ステップＳ３０４：ｄ＝２であるので、ステップＳ３０２へ。
【００８１】
（カウンタｄ＝２のとき）
ステップＳ３０２：ＣＳ［２］＝［２６＊Ｇ，（２＾５）＊Ｇ，−６＊Ｇ，３８＊Ｇ］であるので、（２＾５）＊Ｇ，−６＊Ｇ及びその差３８＊Ｇより楕円曲線加算を行って２６＊Ｇを求める。ここで、３８＊Ｇはカウンタｄ＝３のときに計算済であり、−６＊Ｇはｄ＝６のときに計算して得た６＊ＧのＹ座標に（−１）を掛けたものであるので、そこでの計算結果より得られる。
ステップＳ３０３：ｄ←ｄ−１＝１
ステップＳ３０４：ｄ＝１であるので、ステップＳ３０２へ。
【００８２】
（カウンタｄ＝１のとき）
ステップＳ３０２：ＣＳ［１］＝［１０２＊Ｇ，（２＾６）＊Ｇ，３８＊Ｇ，２６＊Ｇ］であるので、（２＾６）＊Ｇ，３８＊Ｇ及びその差２６＊Ｇより楕円曲線加算を行って１０２＊Ｇを求める。ここで、３８＊Ｇ及び２６＊Ｇはそれぞれカウンタｄ＝３，４のときに計算済であるので、そこでの計算結果を用いる。
ステップＳ３０３：ｄ←ｄ−１＝０
ステップＳ３０４：ｄ＝０であるので、１０２＊Ｇを出力し、終了。
以上のように、上記数値例において楕円曲線演算装置２００は正しくスカラ倍点１０２＊Ｇを求められることがわかる。
【００８３】
３．計算フロー図による説明
次に、本実施の形態１における楕円曲線演算装置２００の動作について、計算フロー図に従って説明する。
図４は、実施の形態１における楕円曲線演算装置２００によるスカラ倍演算の手法（基本的な考え；アプローチ１）を示す計算フロー図である。本実施の形態の楕円曲線演算装置２００の計算手順生成部２１０は、本図の上欄［係数分割の指針］に記されているように、点Ｇのスカラ倍ｋ＊Ｇの演算に際し、予め、係数ｋに対する２分割を繰り返していくが、このとき、２のべき乗係数が毎回出現するように分割する（以下、このような係数の分割を「係数分割」という。）。
【００８４】
具体的には、図４の下欄［具体例］に示される計算フロー図のように、楕円加算の一方が２のべき乗となるように、高い桁から低い桁に向けて、スカラ係数ｋの２分割を繰り返す。なお、本図では、点Ｇの係数だけが示されている（「＊Ｇ」の表記が省略されている；以下の計算フロー図においても同様）。また、実線矢印は楕円曲線上の加算を示し、３つの加算要素は、加算の対象となる２つの加算要素（うち１つは２のべき乗）とそれら２つの加算要素の差である。
【００８５】
例えば、本図では、８７＊Ｇ、つまり、（（２＾６）＋２３）＊Ｇを、第１加算要素（（２＾５）＋２３）＊Ｇと第２加算要素（２＾５）＊Ｇに分割するとともに、それらの差２３＊Ｇを算出する。このとき、一方の加算要素（２＾５）＊Ｇが点Ｇの２のべき乗倍となるように分割する。続いて、２のべき乗倍でない加算要素（（２＾５）＋２３）＊Ｇについて、同様にして、第１加算要素（（２＾４）＋２３）＊Ｇと第２加算要素（２＾４）＊Ｇに分割するとともに、それらの差２３＊Ｇを算出する。このときも、一方の加算要素（２＾４）＊Ｇが点Ｇの２のべき乗倍となるように分割する。このようにして、分割することができなくなるまで、２のべき乗倍でない加算要素に対する２分割を繰り返すことで計算手順が決定される。
【００８６】
このようにして決定された計算手順に対して、楕円曲線演算装置２００のスカラ倍演算部２２０は、低い桁から高い桁に向けて、楕円曲線加算を繰り返すことで、最終的な結果ｋ＊Ｇを求める。例えば、（２＾１）＊Ｇと１＊Ｇと１＊Ｇとも用いて、（２＾１）＊Ｇと１＊Ｇとの楕円曲線加算を行い、その結果（（２＾１）＋１）＊Ｇを求める。続いて、いま得られた結果（（２＾１）＋１）＊Ｇと（２＾１）＊Ｇと１＊Ｇとを用いて、（（２＾１）＋１）＊Ｇと（２＾１）＊Ｇとの楕円曲線加算を行う・・・ということを繰り返し（ここでは、合計９回の加算を繰り返し）、最終的な結果８７＊Ｇを算出する。
【００８７】
なお、個々の楕円曲線加算において、点Ｇの２のべき乗倍については、予め算出されている値（テーブル記憶部２２０ｂに格納された値）を用いることで、その算出が不要となる。また、楕円曲線加算のときに必要とされる差分値（第１加算要素と第２加算要素との差）は、必ず、それまでの楕円曲線加算の過程で出現した値であるので、新たに算出する必要がない。つまり、過去に出現した値を保持しておき、再利用することで足りる。例えば、本図における最後の楕円曲線加算で必要とされる差分値２３＊Ｇは、その２つ前の楕円曲線加算で算出された値（２＾４＋７）＊Ｇに等しいので、新たに算出する必要がない。
【００８８】
図５は、実施の形態１における楕円曲線演算装置２００によるスカラ倍演算の手法（実施の形態で採用している考え；アプローチ２；アプローチ１を発展させたもの）を示す計算フロー図である。ここでは、本図の上欄［係数分割の指針］に示されるように、上記アプローチ１による加算表現（合計９回の加算形による表現）を短くする（より少ない回数の加算で表現する）ために、加算要素の表現形式として、プラス表現だけでなく、マイナス表現を導入している。なお、プラス表現とは、（２＾ｎ）＋ｃという加算形の表現形式であり、マイナス表現とは、（２＾（ｎ＋１））−ｄという減算形の表現形式である。
【００８９】
つまり、分割の対象となる値として、プラス表現（（２＾ｎ）＋ｃ）＊Ｇとマイナス表現（（２＾（ｎ＋１））−ｄ）＊Ｇとを候補とし、その係数における２のべき乗を除く項（ｃ、−ｄなど）の絶対値が小さい方の表現形式を採用することにしている。
【００９０】
具体的には、図５の下欄［具体例］に示される計算フロー図のように、例えば、分割の対象となる係数として、（２＾５）＋２３が得られた場合には、その値と同じ値を示すマイナス表現（２＾６）−９とを比較し、２のべき乗を除く項（５、−９）の絶対値が小さい方の表現形式（２＾６）−９を採用することにする。その結果、係数分割後に得られる２つの加算要素の差がより小さくなり、合計分割数が減少することになる。本図に示されるように、上記アプローチ１で９回の加算が必要とされた計算手順が、このアプローチ２では、７回に減少している。
【００９１】
４．実施形態１の効果
本実施の形態における楕円曲線演算装置２００は、スカラ倍演算部２２０の処理からもわかるとおり、楕円加算の繰り返し計算において、（２＾ｉ）＊Ｇがカウンタ値ごとに出現しており、（２＾ｉ）＊Ｇ（ｉ＝１，２，……，ｎ−１）の座標のテーブルを有効に使用することができている。そのため、計算量が削減され、計算速度は、従来の方法より高速になる。詳細な計算量は、ｋをｎビットとするとき、ｋによって計算量は異なるが、それを平均すると、
（５／４×ｎ−３）×ＥＡｄｄ
である。ここで、ＥＡｄｄは楕円加算の計算量である。
【００９２】
従来例３と異なり、２点の差Ｕは予め計算できないので、Ｚ座標が１とは限らない。そのため、ＥＡｄｄ＝４×Ｍｕｌ＋２×Ｓｑ、ＥＤｏｂ＝３×Ｍｕｌ＋２×Ｓｑである。ただし、Ｍｕｌ、Ｓｑはそれぞれ、ＧＦ（ｐ）の乗算、２乗算の計算量であり、一般にＳｑ＝０．８×Ｍｕｌである。これらの式を代入すると、楕円曲線演算装置２００の計算量は、
（５／４×ｎ−３）×（４×Ｍｕｌ＋２×Ｓｑ）＝（５×ｎ−１２）×Ｍｕｌ＋（５／２×ｎ−６）×Ｓｑ＝（７×ｎ−８４／５）×Ｍｕｌ
であり、従来例３の計算量は、
ｎ×（３×Ｍｕｌ＋２×Ｓｑ）＋ｎ×（３×Ｍｕｌ＋２×Ｓｑ）＝６×ｎ×Ｍｕｌ＋４×ｎ×Ｓｑ＝４６／５×ｎ×Ｍｕｌ
である。したがって、楕円曲線演算装置２００の方が従来例３に比べて、約１．３倍高速である。
【００９３】
図６は、図２６に示された従来例３の計算手法と本実施の形態１での計算手法（図５の下欄）とを比較する図である。この図から分かるように、例えば、８７＊Ｇの演算については、従来例３によれば６回の加算と５回の２倍算が必要とされるのに対し、本実施の形態１によれば７回の加算だけで済む。つまり、計算量にして、従来例３と本実施の形態１とは、５０．６：３９．２となり、計算速度にして、本実施の形態１は、従来例３の１．３倍だけ高速化される。
以上より、実施形態１によって、高速な楕円曲線演算が可能になり、本発明の実用的価値は非常に大きい。
【００９４】
［実施の形態２］
次に、本発明の実施の形態２における楕円曲線演算装置について説明する。
１．楕円曲線演算装置３００の構成
図７は、実施の形態２における楕円曲線演算装置３００の構成を示すブロック図である。この楕円曲線演算装置３００は、実施の形態１と同様に、専用のプログラムを実行するコンピュータ装置又はＬＳＩ等の論理回路で実現され、有限体ＧＦ（ｐ）上のモンゴメリ型楕円曲線Ｅ：Ｂ×ｙ＾２＝ｘ＾３＋Ａ×ｘ＾２＋ｘのパラメータｐ（素数）、ＧＦ（ｐ）の元A、Bと、Ｅ（ＧＦ（ｐ））に属する点Ｇと、その（２＾ｉ）＊Ｇ（ｉ＝１，２，……，ｎ−１）を予め与えられ、ｎビットの任意のｋを入力として、点Ｇのスカラ倍ｋ＊Ｇを出力する演算装置であり、点Ｇの２のべき乗倍（２＾ｉ）＊Ｇを有効活用しながら計算する点に特徴を有し、計算手順生成部３１０とスカラ倍演算部３２０とから構成される。
【００９５】
この楕円曲線演算装置３００は、点Ｇのスカラ倍演算について、２進表現を利用した予備計算（計算機処理に向いた計算）に基づいて計算手順を生成し、生成した計算手順に従って点Ｇのスカラ倍演算を実行している点で、計算機による処理効率を考慮していない実施の形態１と異なる。
（計算手順生成部３１０の処理）
【００９６】
計算手順生成部３１０は、点Ｇのスカラ倍ｋ＊Ｇを算出するための計算手順を生成する予備計算を実行する処理部であり、ｋ＊ＧをＧの２のべき乗倍（２＾ｉ）＊Ｇを用いた加算形に分割することを繰り返すとともに、得られた加算要素の表現形式（プラス表現／マイナス表現）の切り替わりの種別（加算タイプ）を特定する加算タイプ特定部３１０ａと、加算タイプ特定部３１０ａによって特定された加算タイプを配列として出力する配列生成出力部３１０ｂとからなる。
【００９７】
具体的には、計算手順生成部２１０は、図８に示されるフローチャートのように、整数ｋを入力として、配列｛Ｓ［ｉ］｝（Ｓ［ｉ］は配列のｉ番目の数、１≦ｉ≦｜ｋ｜）を出力する。ここで、配列Ｓ［ｉ］は、ｋ＊Ｇを算出するための繰り返し加算における第ｉ番目の加算のタイプ、即ち、点Ｇの２のべき乗倍でない加算要素（又は、加算の結果得られる値）の係数の表現形式に着目し、その加算によって係数がプラス表現からプラス表現になった場合に「０」、プラス表現からマイナス表現になった場合に「１」、マイナス表現からマイナス表現になった場合に「２」、マイナス表現からプラス表現になった場合に「３」にセットされる。
【００９８】
図８において、加算タイプ特定部３１０ａは、以下の手順に従って、配列｛Ｓ［ｉ］｝を特定する。なお、以下では、
ｋ＝ｋ［ｎ−１］×２＾（ｎ−１）＋ｋ［ｎ−２］×２＾（ｎ−２）＋……＋ｋ［１］×２＋ｋ［０］
とおいたときのｋのビット表現を［ｋ［ｎ−１］、ｋ［ｎ−２］、……、ｋ［１］、ｋ［０］］とする。
ステップＳ４０１：ｗ←ｋとする。ただし、ｗ←ｋはｗにｋを代入することを示している。
ステップＳ４０２：カウンタｃ←ｎ−１とする。
ステップＳ４０３：ｕ←ｗ−２＾ｃとする。
ステップＳ４０４：ｕ［ｃ−１］が１であるかを判定する。１であるときステップＳ４０６へ。それ以外は次のステップへ。
ステップＳ４０５：ｕ［ｃ−２］が０であるかを判定する（Ｓ４０５ａ）。０であるとき、Ｓ［ｃ］←０，ｗ←ｗ−２＾（ｃ−１）とする（Ｓ４０５ｂ）。１であるとき、Ｓ［ｃ］←１、ｗ←ｗ−２＾（ｃ−１）、ｕ←ｗ−２＾（ｃ−１）とする（Ｓ４０５ｃ）。ステップＳ４０７へ。
ステップＳ４０６：ｕ［ｃ−２］が１であるかを判定する（Ｓ４０６ａ）。１であるとき、Ｓ［ｃ］←２、ｗ←ｗ−２＾ｃ、ｕ←ｕ−２＾ｃとする（４０６ｂ）。０であるとき、Ｓ［ｃ］←３、ｗ←ｗ−２＾ｃ、ｕ←ｗ−２＾（ｃ−１）とする（Ｓ４０６ｃ）。
ステップＳ４０７：ｗ＝２＾（ｃ−１）＋２＾（ｃ−２）であるか判定する（Ｓ４０７ａ）。この式が成り立つ場合、加算タイプ特定部３１０ａは、Ｓ［１］←ｃ−１とし、配列生成出力部３１０ｂは、配列｛Ｓ［ｉ］｝をスカラ倍演算部３２０に出力して終了する（Ｓ４０７ｂ）。それ以外は、次のステップへ。
ステップＳ４０８：ｃ←ｃ−１とする。ステップＳ４０４へ。
【００９９】
（スカラ倍演算部３２０の処理）
スカラ倍演算部３２０は、計算手順生成部３１０から出力された計算手順Ｓ［ｉ］（ｉ＝１，２，……）に基づいて、楕円曲線上の加算を繰り返すことで、最終的な計算結果ｋ＊Ｇを算出し出力する演算部であり、点Ｇの２のべき乗倍（（２＾ｉ）＊Ｇ；ｉ＝１，２，…）を予め記憶しているテーブル記憶部３２０ｂ、ワーキング用のメモリである一時記憶部３２０ｃ、楕円曲線上での加算を行う加算器である楕円加算部３２０ｄ及び計算手順生成部３１０からの計算手順Ｓ［ｉ］に従って各構成要素３２０ｂ〜３２０ｄを制御する演算制御部３２０ａからなる。
【０１００】
このスカラ倍演算部３２０は、図９に示されるフローチャートに従って、ｋ＊Ｇを算出する。具体的には、演算制御部３２０ａは、以下のステップで、計算・制御を行う。
ステップＳ５０１：ｄ←Ｓ１とする。楕円加算部３２０ｄに楕円加算２＾ｄ＊Ｇ＋２＾（ｄ−１）＊Ｇを実行させ、Ｔに代入し、Ｕ←２＾（ｄ−１）＊Ｇとする。
ステップＳ５０２：ｄ←ｄ＋１とする。
ステップＳ５０３：Ｔ'←Ｔとする。
ステップＳ５０４：Ｓ［ｄ］の値を判定し（Ｓ５０４ａ）、以下のように処理する。
（１） Ｓ［ｄ］＝０または１のとき、楕円加算部３２０ｄに、Ｔと２＾（ｄ−１）＊Ｇ（２点の差はＵ）の楕円加算を計算させ、その結果をＴに代入する（Ｓ５０４ｂ）。
（２） Ｓ［ｄ］＝２または３のとき、楕円加算部３２０ｄに、２＾ｄ＊ＧとＴ（２点の差はＵ）の楕円加算を計算させ、その結果をＴに代入する（Ｓ５０４ｃ）。
【０１０１】
なお、（２＾ｄ）＊Ｇ等の２のべき乗倍については、テーブル記憶部３２０ｂから読み出した値を用いることとし、得られた加算結果については、一時記憶部３２０ｃに格納することで変数Ｔに代入したりする。
ステップＳ５０５：ｄ＝｜ｋ｜−１であるか判定し（Ｓ５０５ａ）、この式を満たす場合、Ｔを出力し（Ｓ５０５ｂ）、終了する。それ以外は次のステップへ。ステップＳ５０６：Ｓ［ｄ＋１］の値を調べ（Ｓ５０６ａ）、Ｓ［ｄ＋１］＝１であるとき、Ｕ←Ｔ'とする（Ｓ５０６ｂ）。Ｓ［ｄ＋１］＝３であるとき、楕円加算部３２０ｄに、２＾ｄ＊Ｇと−Ｕ（２点の差はＴ）の楕円加算を実行させ、その結果をＵに代入する（Ｓ５０６ｃ）。ステップＳ５０２へ。
なお、上記のステップで使用される楕円加算の具体的な計算方法は、実施形態１で説明した通りである。
【０１０２】
（楕円曲線演算装置３００の動作）
楕円曲線演算装置３００は、入力の整数ｋを受け取り、計算手順生成部３１０へ入力する。計算手順生成部３１０は、入力された整数ｋより、配列｛Ｓ［ｉ］｝を計算し、スカラ倍演算部３２０へ入力する。スカラ倍演算部３２０は、入力された配列｛Ｓ［ｉ］｝より、楕円曲線の点Ｇのスカラ倍点ｋ＊Ｇを算出し、出力する。
【０１０３】
２．楕円曲線演算装置３００の数値例
以下では、ｋ＝１０２の場合の数値例を示す。
（計算手順生成部３１０における中間値）
ｎ＝７であるため、カウンタｃの初期値は、６である。カウンタｃの値に対する処理を以下に示す。
（カウンタｃ＝６のとき）
ステップＳ４０３：ｕ←ｗ−２＾（ｎ−１）＝３８
ステップＳ４０４：ｕ［ｃ−１］＝ｕ［５］の判定。ｕ［５］＝１（∵ｕ＝２＾５＋６）であるため、ステップＳ４０６へ。
ステップＳ４０６：ｕ［ｃ−２］＝ｕ［４］の判定。ｕ［４］＝０であるため、Ｓ［６］←３、ｗ←ｗ−２＾ｃ＝１０２−２＾６＝３８、ｕ←ｗ−２＾（ｃ−１）＝３８−２＾５＝６
ステップＳ４０７：ｗ＝２＾（ｃ−１）＋２＾（ｃ−２）であるかの判定。満たさない
ステップＳ４０８：ｃ←ｃ−１＝５として、ステップＳ４０４へ。
【０１０４】
（カウンタｃ＝５のとき）
ステップＳ４０４：ｕ［ｃ−１］＝ｕ［４］の判定。ｕ［４］＝０であるため、ステップＳ４０５へ。
ステップＳ４０５：ｕ［ｃ−２］＝ｕ［３］の判定。ｕ［３］＝０であるため、Ｓ［５］←０、ｗ←ｗ−２＾（ｃ−１）＝３８−２＾４＝２２。ステップＳ４０７へ。
ステップＳ４０７：ｗ＝２＾（ｃ−１）＋２＾（ｃ−２）であるかの判定。満たさない
ステップＳ４０８：ｃ←ｃ−１＝４として、ステップＳ４０４へ。
【０１０５】
（カウンタｃ＝４のとき）
ステップＳ４０４：ｕ［ｃ−１］＝ｕ［３］の判定。ｕ［３］＝０であるため、ステップＳ４０５へ。
ステップＳ４０５：ｕ［ｃ−２］＝ｕ［２］の判定。ｕ［２］＝１であるため、Ｓ［４］←１、ｗ←ｗ−２＾（ｃ−１）＝２２−２＾３＝１４、ｕ←ｗ−２＾（ｃ−１）＝１４−２＾３＝６。ステップＳ４０７へ。
ステップＳ４０７：ｗ＝２＾（ｃ−１）＋２＾（ｃ−２）であるかの判定。満たさない
ステップＳ４０８：ｃ←ｃ−１＝３として、ステップＳ４０４へ。
【０１０６】
（カウンタｃ＝３のとき）
ステップＳ４０４：ｕ［ｃ−１］＝ｕ［２］の判定。ｕ［２］＝１であるため、ステップＳ４０６へ。
ステップＳ４０６：ｕ［ｃ−２］＝ｕ［１］の判定。ｕ［１］＝１であるため、Ｓ［３］←２、ｗ←ｗ−２＾ｃ＝１４−２＾３＝６、ｕ←ｕ−２＾（ｃ−１）＝６−２＾２＝２。ステップＳ４０７へ。
ステップＳ４０７：ｗ＝２＾（ｃ−１）＋２＾（ｃ−２）であるかの判定。ｗ＝６＝２＾２＋２＾１であるため、満たすため、Ｓ［１］＝ｃ−１＝２として、配列｛Ｓ［ｉ］｝を出力し終了。
以上より、計算手順生成部３１０の出力は、［２、０、２、１、０、３］である。
【０１０７】
（スカラ倍演算部３２０の中間値）
次に、スカラ倍演算部３２０の処理を示す。
Ｓ１＝２であるため、ｄ＝２となる。まず、ステップＳ５０１にて、２＾２＊Ｇ＋２＾１＊Ｇを計算し、Ｑに代入し、Ｕ←２＾１＊Ｇとする。次に、ステップＳ５０２にて、ｄ←ｄ＋１＝３とする。以下にそれ以降のｄの値に対する処理を示す。
（ｄ＝３のとき）
ステップＳ５０３：Ｑ'←Ｑ
ステップＳ５０４：Ｓ［ｄ］＝Ｓ［３］の値を判定。Ｓ［３］＝２であるため、２＾３＊ＧとＱ（２点の差は、２＾３＊Ｇ−Ｑ＝（２＾３−（２＾２＋２＾１））＊Ｇ＝２＊Ｇ＝Ｕ）の楕円加算を行い、Ｑに代入（Ｑ＝１４＊Ｇ）。
ステップＳ５０５：ｄ＝｜ｋ｜−１＝６であるか判定。満たさない
ステップＳ５０６：Ｓ［ｄ＋１］＝Ｓ［４］の判定。Ｓ［４］＝１であるため、Ｕ←Ｑ'（＝６＊Ｇ）。ステップＳ５０２へ。
【０１０８】
（ｄ＝４のとき）
ステップＳ５０３：Ｑ'←Ｑ
ステップＳ５０４：Ｓ［ｄ］＝Ｓ［４］の値を判定。Ｓ［４］＝０であるため、Ｑと２＾３＊Ｇ（２点の差は、Ｑ−２＾３＊Ｇ＝（１４−２＾３）＊Ｇ＝６＊Ｇ＝Ｕ）の楕円加算を行い、Ｑに代入（Ｑ＝２２＊Ｇ）。
ステップＳ５０５：ｄ＝｜ｋ｜−１＝６であるか判定。満たさない
ステップＳ５０６：Ｓ［ｄ＋１］＝Ｓ［５］の判定。Ｓ［５］＝０であるため、ここでの処理はない。ステップＳ５０２へ。
【０１０９】
（ｄ＝５のとき）
ステップＳ５０３：Ｑ'←Ｑ
ステップＳ５０４：Ｓ［ｄ］＝Ｓ［５］の値を判定。Ｓ［５］＝０であるため、Ｑと２＾４＊Ｇ（２点の差は、Ｑ−２＾４＊Ｇ＝（２２−２＾４）＊Ｇ＝６＊Ｇ＝Ｕ）の楕円加算を行い、Ｑに代入（Ｑ＝３８＊Ｇ）。
ステップＳ５０５：ｄ＝｜ｋ｜−１＝６であるか判定。満たさない
ステップＳ５０６：Ｓ［ｄ＋１］＝Ｓ［６］の値を判定。Ｓ［６］＝３であるため、２＾５＊Ｇと−Ｕ（２点の差は２＾５＊Ｇ−（−Ｕ）＝（２＾５＋６）＊Ｇ＝３８＊Ｇ）の楕円加算を行い、Ｕに代入（Ｕ＝２６＊Ｇ）。ステップＳ５０２へ。
【０１１０】
（ｄ＝６のとき）
ステップＳ５０３：Ｑ'←Ｑ
ステップＳ５０４：Ｓ［ｄ］＝Ｓ［６］の値を判定。Ｓ［６］＝３であるため、２＾６＊ＧとＱ（２点の差は、２＾６＊Ｇ−Ｑ＝（２＾６−３８）＊Ｇ＝２６＊Ｇ＝Ｕ）の楕円加算を行い、Ｑに代入（Ｑ＝１０２＊Ｇ）。
ステップＳ５０５：ｄ＝｜ｋ｜−１＝６であるか判定。満たすため、Ｑ（＝１０２＊Ｇ）を出力し終了。
【０１１１】
以上のように、上記数値例において楕円曲線演算装置３００は正しくスカラ倍点１０２＊Ｇを求められることがわかる。
【０１１２】
３．計算フロー図による説明
次に、本実施の形態２における楕円曲線演算装置３００の動作について、計算フロー図に従って説明する。
図１０は、実施の形態２における楕円曲線演算装置３００によるスカラ倍演算の手法を示す計算フロー図である。本実施の形態の楕円曲線演算装置３００の計算手順生成部３１０は、本図の上欄［係数分割の指針］に記されているように、点Ｇのスカラ倍ｋ＊Ｇの演算に際し、予め、係数ｋに対する２分割を繰り返していくが、このとき、分割の対象となる係数については、その係数の２進表現における最上位２桁に着目し、「１０」である場合には、プラス表現で表現し、一方、「１１」である場合には、マイナス表現で表現した上で、係数分割を実行する。そして、係数分割ごとに、分割の対象（係数）の表現形式がどのように切り替わったかを示す加算タイプ（０／１／２／３）を特定する。
【０１１３】
具体的には、図１０の中欄［具体例］に示される計算フロー図のように、分割の対象となる係数１０２について、その２進表現が１１００１１０であり、最上位２桁が「１１」であるので、１０２を２＾７−２６というマイナス表現で表現した上で、２＾６と２＾６−２６（＝３８）とに分割する。続いて、分割の対象となる３８について、その２進表現が１００１１０であり、最上位２桁が「１０」であるので、３８を２＾５＋６というプラス表現で表現した上で、２＾４と２＾４＋６とに分割する。このとき、第１の係数分割（１０２に対する分割）によって、分割の対象がマイナス表現からプラス表現になったので、図１０の下欄に示される表現形式の切り替わり種別の中から該当するものの値「３」を配列Ｓ［ｉ］の値としてセットする。
【０１１４】
このように、本図の例では、分割対象の係数は、分割に伴って、マイナス表現、プラス表現、プラス表現、マイナス表現、マイナス表現、…と変化しているので、出力される配列Ｓ［ｉ］は、３，０，１，２，…となる。
なお、分割対象の表現形式がマイナス表現からプラス表現に切り替わった場合に、分割によって生成された２つの加算要素の差分値についても、分割しておく必要がある。本図の例では、分割対象がマイナス表現（２＾７−２６）からプラス表現（２＾５＋６）に切り替わったときに生成された差分値２６についても図示される加算要素に分割している。
【０１１５】
以上のように、実施の形態２では、計算手順生成部３１０が生成する計算手順Ｓ［ｉ］は、スカラ係数ｋに対する繰り返し分割における対象係数の表現形式の切り替わり情報であり、全ての分割要素（加算要素）を計算手順として出力する実施の形態１と比べ、簡素化された情報となっている。
【０１１６】
４．実施形態２の効果
本実施の形態における楕円曲線演算装置３００は、実施の形態１と同様に、スカラ倍演算部３２０の処理からもわかるとおり、楕円加算の繰り返し計算において、（２＾ｉ）＊Ｇが加算ごとに出現しており、（２＾ｉ）＊Ｇ（ｉ＝１，２，……，ｎ−１）の座標のテーブルを有効に使用することができている。そのため、計算量が削減され、従来例３に比べ、計算速度は、約１．３倍高速である。
【０１１７】
実施の形態１の楕円曲線演算装置２００と異なる点は、装置の処理の記述がより計算機に適した形（２進表現と関連した処理）になっていることである。そのため、プログラミングが容易になる。
以上より、実施形態２によって、高速な楕円曲線演算が可能になり、さらにその処理は計算機に適した形になっており、本発明の実用的価値は非常に大きい。
【０１１８】
［実施の形態３］
次に、本発明の実施の形態３における楕円曲線演算装置について説明する。
１．楕円曲線演算装置４００の構成
図１１は、実施の形態３における楕円曲線演算装置４００の構成を示すブロック図である。この楕円曲線演算装置４００は、実施の形態１及び２と同様に、専用のプログラムを実行するコンピュータ装置又はＬＳＩ等の論理回路で実現され、有限体ＧＦ（ｐ）上のモンゴメリ型楕円曲線Ｅ：Ｂ×ｙ＾２＝ｘ＾３＋Ａ×ｘ＾２＋ｘのパラメータｐ（素数）、ＧＦ（ｐ）の元A、Bと、Ｅ（ＧＦ（ｐ））に属する点Ｇと、その（２＾ｉ）＊Ｇ（ｉ＝１，２，……，ｎ−１）を予め与えられ、ｎビットの任意のｋを入力として、点Ｇのスカラ倍ｋ＊Ｇを出力する演算装置であり、点Ｇの２のべき乗倍（２＾ｉ）＊Ｇを有効活用しながら計算する点に特徴を有し、計算手順生成部４１０とスカラ倍演算部４２０とから構成される。
【０１１９】
この楕円曲線演算装置４００は、点Ｇのスカラ倍演算について、２進表現を利用した予備計算（計算機処理に向いた計算）に基づいて加算要素の表現形式の切り替わりに関する計算手順を生成する点で実施の形態２と共通し、個々の切り替わり情報ではなく、同一表現形式の連続個数を計算手順として生成する点で実施の形態２と異なる。以下、実施の形態２と異なる点を中心に説明する。
【０１２０】
（計算手順生成部４１０の処理）
計算手順生成部４１０は、点Ｇのスカラ倍ｋ＊Ｇを算出するための計算手順を生成する予備計算を実行する処理部であり、ｋ＊ＧをＧの２のべき乗倍（２＾ｉ）＊Ｇを用いた加算形に分割することを繰り返すとともに、得られた加算要素の表現形式の切り替わり点（同一の表現形式が何個連続した後に切り替わるかの情報）を特定する加算要素表現切替点特定部４１０ａと、加算要素表現切替点特定部４１０ａによって特定された切り替わり点を配列として出力する配列生成出力部４１０ｂとからなる。
【０１２１】
具体的には、計算手順生成部４１０は、図１２に示されるフローチャートのように、整数ｋを入力として、配列｛Ｓ［ｉ］｝（ｉ＝１，２，…，Ｓ［１］＋２）を出力する。ここで、配列｛Ｓ［ｉ］｝は、以下の値から構成される。
【０１２２】
Ｓ［１］：係数分割の結果得られた表現形式の遷移列において出現した表現形式（同一の表現形式が連続する場合には、１個とする）の総数。例えば、分割対象の表現形式が、−（マイナス表現），＋（プラス表現），＋，−，−であった場合には、３（「−」、「＋」、「−」の３個）となる。
【０１２３】
Ｓ［２］：係数分割の最後に得られる加算要素に含まれる「０」（２進表現）の数。なお、係数分割の最後に得られる加算要素は、２進表現で、必ず１０…（１と０個以上の０が続く表現）となる。
【０１２４】
Ｓ［３］：係数分割によって得られた表現形式の遷移列において、上位桁から第１番目の表現形式が連続する個数。例えば、分割対象の表現形式が、−，＋，＋，−，−であった場合には、１（１番目の表現形式「−」は１個）となる。
【０１２５】
Ｓ［４］：係数分割によって得られた表現形式の遷移列において、上位桁から第２番目の表現形式が連続する個数。例えば、分割対象の表現形式が、−，＋，＋，−，−であった場合には、２（２番目の表現形式「＋」は２個）となる。
以下、同様にして、Ｓ［Ｓ［１］＋２］まで続く。
【０１２６】
図１２において、加算要素表現切替点特定部４１０ａは、以下の手順に従って、配列｛Ｓ［ｉ］｝を特定する。
ステップＳ６０１：与えられたｋを係数分割の対象とする。
ステップＳ６０２：分割対象について、実施の形態２と同様の判断（図５の「係数分割の指針」）によって表現形式を特定して記憶しておくとともに、分割対象をその表現形式で表現する。
ステップＳ６０３：分割対象を、実施の形態２と同様に、第１加算要素（２のべき乗の項）と第２加算要素とに分割するとともに、それらの差分値を特定する。ステップＳ６０４：全ての係数分割が終了したか否かを判断するために、次の分割対象となる第２加算要素が３×２＾ｅで表せるか判断する。
ステップＳ６０５：上記ステップＳ６０４で肯定的に判断された場合には、次の分割対象の表現形式をマイナス表現とし、その分割対象に対する最後の分割を行う。
ステップＳ６０６：最後に、配列生成出力部４１０ｂは、それまでの係数分割で得られた分割対象についての表現形式の並びから、出現した表現形式の個数をＳ［１］にセットし、最後の係数分割で得られた第２加算要素に含まれる「０」（２進表現）の個数をＳ［２］にセットし、係数分割によって得られた表現形式の遷移列において、上位桁から第１番目の表現形式が連続する個数をＳ［３］にセットし、同様に、第２番目の表現形式が連続する個数をＳ［４］にセットし、・・・、最後の分割対象の表現形式が連続する個数をＳ［Ｓ［１］＋２］にセットし、スカラ倍演算部４２０に出力する。
ステップＳ６０７：ステップＳ６０４において否定的に判断された場合には、さらなる係数分割を続けるために、第２加算要素を新たな分割対象とし、同様の手順（ステップＳ６０２〜Ｓ６０４）を繰り返す。
【０１２７】
（スカラ倍演算部４２０の処理）
スカラ倍演算部３２０は、計算手順生成部３１０から出力された計算手順｛Ｓ［ｉ］｝に基づいて、楕円曲線上の加算を繰り返すことで、最終的な計算結果ｋ＊Ｇを算出し出力する演算部であり、点Ｇの２のべき乗倍（（２＾ｉ）＊Ｇ；ｉ＝１，２，…）を予め記憶しているテーブル記憶部４２０ｂ、ワーキング用のメモリである一時記憶部４２０ｃ、楕円曲線上での加算を行う加算器である楕円加算部４２０ｄ及び計算手順生成部４１０からの計算手順｛Ｓ［ｉ］｝に従って各構成要素４２０ｂ〜４２０ｄを制御する演算制御部４２０ａからなる。
【０１２８】
このスカラ倍演算部４２０は、図１３に示されるフローチャートに従って、ｋ＊Ｇを算出する。具体的には、演算制御部４２０ａは、以下のステップで、計算・制御を行う。
ステップＳ７０１：計算手順生成部４１０から与えられた配列要素Ｓ［２］に基づいて、最初の楕円加算に必要な第１加算要素、第２加算要素及び差分を特定する。
ステップＳ７０２〜Ｓ７０４：計算手順生成部４１０から与えられた配列要素Ｓ［１］が示す回数だけ、同一タイプの楕円曲線加算（ステップＳ７０３）を繰り返す。
ステップＳ７０３：上記Ｓ［１］回の楕円曲線加算における第ｉ番目の楕円曲線加算においては、計算手順生成部４１０から与えられた配列要素Ｓ［ｉ＋２］が示す回数だけ、同一タイプの楕円曲線加算を繰り返す。
【０１２９】
２．楕円曲線演算装置４００の数値例
次に、本実施の形態３における楕円曲線演算装置４００の動作について、具体的な数値例及び計算フロー図を用いて説明する。
（計算手順生成部４１０の中間値）
図１４は、計算手順生成部４１０による計算手順（配列｛Ｓ［ｉ］｝）の生成過程を示す計算フロー図である。本図の上欄［具体例］に示される計算フロー図と図１０に示された計算フロー図とを比較して分かるように、本実施の形態における係数分割の基本処理は実施の形態２と同様である。つまり、係数ｋに対する２分割を繰り返し、このとき、分割の対象となる係数の２進表現における最上位２桁が「１０」である場合には、プラス表現で表現し、一方、「１１」である場合には、マイナス表現で表現した上で、係数分割を実行する。
【０１３０】
ただし、本実施の形態の計算手順生成部４１０は、係数分割において、分割対象の表現形式が何から何に切り替わっていくかを示す配列を生成するではなく、本図の下欄［配列生成（計算手順生成）］に示されるように、何回のステップ（分割）で表現形式が切り替わるかを示す情報を配列｛Ｓ［ｉ］｝として生成する。
【０１３１】
具体的には、本図に示される係数「１０２」については、係数分割に伴って、表現形式がマイナス表現、プラス表現、プラス表現、マイナス表現、マイナス表現と遷移したので、（１，２，２）と特定し、それぞれ、配列要素Ｓ［３］，Ｓ［４］，Ｓ［５］にセットする。そして、いまセットした合計数「３」を配列要素Ｓ［１］にセットするとともに、係数分割の最後に得られた加算要素「２」（２進表現で「１０」）に含まれる「０」の個数「１」を配列要素Ｓ［２］にセットし、計算手順を示す配列｛Ｓ［ｉ］｝として出力する。
【０１３２】
（スカラ倍演算部４２０の中間値）
図１５は、図１４に示された具体例に対応するスカラ倍演算部４２０の動作を示す図である。つまり、図１４に示された配列（３，１，１，２，２）を受け取ったスカラ倍演算部４２０が図１３に示されたフローチャートに従って１０２＊Ｇの値を算出するまでの計算過程及び中間値が示されている。
【０１３３】
スカラ倍演算部４２０は、計算手順生成部４１０から与えられた配列要素Ｓ［１］に基づいて、同一タイプの楕円加算の繰り返し回数ｄを初期化した後に、最初の楕円加算に必要な第１加算要素Ｗ、第２加算要素Ｔ及び差分Ｕ等を特定する（ステップＳ８０１）。
そして、Ｓ［３＋２］＝２より、マイナス表現の加算値を生成する２回の楕円曲線加算を行い、差分値Ｕを更新する（ステップＳ８０２）。
【０１３４】
続いて、Ｓ［２＋２］＝２より、プラス表現の加算値を生成する２回の楕円曲線加算を行い、差分値Ｕを更新する（ステップＳ８０３）。
最後に、Ｓ［１＋２］＝１より、マイナス表現の加算値を生成する１回の楕円曲線加算を行い、得られた加算結果Ｔを最終的な結果（１０２＊Ｇ）として出力する（ステップＳ８０４）。
【０１３５】
３．実施形態３の効果
本実施の形態における楕円曲線演算装置４００は、実施の形態１及び２と同様に、スカラ倍演算部４２０の処理からもわかるとおり、楕円加算の繰り返し計算において、（２＾ｉ）＊Ｇが加算ごとに出現しており、（２＾ｉ）＊Ｇ（ｉ＝１，２，……，ｎ−１）の座標のテーブルを有効に使用することができている。そのため、計算量が削減され、従来例３に比べ、計算速度は、約１．３倍高速である。
【０１３６】
実施の形態１の楕円曲線演算装置２００と異なる点は、装置の処理の記述がより計算機に適した形（２進表現と関連した処理）になっていることであり、また、実施の形態２の楕円曲線演算装置３００と異なる点は、計算手順生成部４１０による計算手順の表現が圧縮された短い形式となっていることである。そのため、プログラミングが容易になるとともに、計算過程で必要とされる中間値の個数が抑制される。
【０１３７】
以上より、実施の形態３によって、高速な楕円曲線演算が可能になり、さらにその処理は計算機に適した形になっているとともに、より小さなワーキングメモリ領域での演算が可能となり、本発明の実用的価値は非常に大きい。
【０１３８】
［実施の形態４］
次に、本発明の実施の形態４における楕円曲線演算装置について説明する。
１．楕円曲線演算装置５００の構成
図１６は、実施の形態４における楕円曲線演算装置５００の構成を示すブロック図である。この楕円曲線演算装置５００は、実施の形態１〜３と同様に、専用のプログラムを実行するコンピュータ装置又はＬＳＩ等の論理回路で実現され、有限体ＧＦ（ｐ）上のモンゴメリ型楕円曲線Ｅ：Ｂ×ｙ＾２＝ｘ＾３＋Ａ×ｘ＾２＋ｘのパラメータｐ（素数）、ＧＦ（ｐ）の元A、Bと、Ｅ（ＧＦ（ｐ））に属する点Ｇと、その（２＾ｉ）＊Ｇ（ｉ＝１，２，……，ｎ−１）を予め与えられ、ｎビットの任意のｋを入力として、点Ｇのスカラ倍ｋ＊Ｇを出力する演算装置であり、点Ｇの２のべき乗倍（２＾ｉ）＊Ｇを有効活用しながら計算する点に特徴を有し、演算制御部５１０とテーブル記憶部５２０と楕円加算部５３０とから構成される。
【０１３９】
この楕円曲線演算装置５００は、実施の形態１〜３と異なり、点Ｇのスカラ倍演算に対して、予備計算によって一連の計算手順を事前に生成しておくのではなく、与えられたｋを下位桁から上位桁に向けて解析しながら、楕円曲線加算を繰り返していくことで、最終的な結果ｋ＊Ｇを算出する。つまり、計算手順の生成と楕円曲線加算という２段階ではなく、楕円曲線加算だけで最終的な結果を求めている。
【０１４０】
演算制御部５１０は、与えられた係数ｋに対して、ｋ＊Ｇを算出するための一時的な処理や楕円加算部５３０に対する制御を行う処理部であり、係数ｋの２進表現のおける各ビットの値（１／０）を判定するビット判定部５１０ａと、ビット判定部５１０ａによる判定結果に基づいて、楕円曲線加算に必要な３つの値（２つの加算要素とそれらの差分値）を特定する加算要素特定部５１０ｂと、ワーキング用のメモリである一時記憶部５１０ｃとからなる。
【０１４１】
テーブル記憶部５２０は、点Ｇの２のべき乗倍（（２＾ｉ）＊Ｇ；ｉ＝１，２，…）を予め記憶しているテーブルであり、実施の形態１のテーブル記憶部２２０ｂ等と同一である。
【０１４２】
楕円加算部５３０は、演算制御部５１０による制御に従って、演算制御部５１０から指示された値又はテーブル記憶部５２０から読み出した値を用いて楕円曲線上の加算を行う加算器等である。
【０１４３】
２．楕円曲線演算装置５００の動作
図１７は、本実施の形態における楕円曲線演算装置５００の動作を示すフローチャートである。
ステップＳ９０１：演算制御部５１０は、係数ｋを取得する。
ステップＳ９０２：取得した係数ｋの２進表現における最下位の「１」を特定し、その桁をｋ［ｓ］とする。そして、その桁ｋ［ｓ］に対応する値２＾ｓを最初の加算対象（２のべき乗と加算される要素）と特定する。
ステップＳ９０３〜Ｓ９０７：続いて、その桁ｋ［ｓ］から最上位桁の手前ｋ［ｎ−２］に向けて、順次、桁ｋ［ｉ］の値（１／０）に応じた楕円曲線加算（ステップＳ９０４〜Ｓ９０６）を繰り返す。
ステップＳ９０４：具体的には、まず、ビット判定部５１０ａは、当該桁ｋ［ｉ］が１か０かを判定する。
【０１４４】
ステップＳ９０５：その結果、ｋ［ｓ］＝１であると判定された場合には、加算要素特定部５１０ｂは、加算対象をマイナス表現とする加算要素を特定する。まり、加算対象を２＾（ｓ＋１）−ｄと表現した場合には、楕円曲線加算に必要な要素として、２＾（ｓ＋１）−ｄと２＾（ｓ＋１）とｄとを生成する。そして、それらを用いた楕円曲線加算を実行するように、それらの値や制御指示を楕円加算部５３０に与える。なお、楕円加算部５３０は、点Ｇの２のべき乗倍については、加算要素特定部５１０ｂからの指示に従って、テーブル記憶部５２０から読み出した値を使用する。
ステップＳ９０６：一方、ステップＳ９０４で当該桁ｋ［ｉ］が０であると判定された場合には、加算要素特定部５１０ｂは、加算対象をプラス表現とする加算要素を特定する。つまり、加算対象を２＾ｓ＋ｄと表現した場合には、楕円曲線加算に必要な要素として、２＾ｓ＋ｄと２＾ｓとｄとを生成する。そして、それらを用いた楕円曲線加算を実行するように、それらの値や制御指示を楕円加算部５３０に与える。
なお、楕円曲線加算によって得られた中間値等は、一時記憶部５１０ｃに記憶され、次の楕円曲線加算に用いられる。
【０１４５】
３．楕円曲線演算装置５００の数値例
図１８は、具体的な数値に対する楕円曲線演算装置５００の動作を示す計算フロー図である。この楕円曲線演算装置５００は、ｋ＊Ｇを算出するにあたり、係数ｋの下位桁から順に参照していくことで、点Ｇの２のべき乗倍と得られた結果との楕円曲線加算を繰り返していくが、その際に、本図の上欄［楕円曲線加算の指針］に示されるように、着目している係数ｋ［ｉ］の値が「１」である場合には、加算対象（加算の初期値又は直前の楕円曲線加算で得られた値）をプラス表現にした上で、楕円曲線加算を実行し、一方、着目している係数ｋ［ｉ］の値が「０」である場合には、加算対象をマイナス表現にした上で、楕円曲線加算を実行する。
【０１４６】
具体的には、本図の下欄［具体例］に示されるように、演算制御部５１０は、まず、与えられたけ係数ｋの２進表現における最下位の「１」（ここでは、ｋ［ｓ］；ｓ＝１）を特定する。その桁ｋ［ｓ］に対応する値２＾１を最初の加算対象（２のべき乗と加算される要素）と特定する。
【０１４７】
続いて、その桁ｋ［１］からｋ［５］に向けて、順次、桁ｋ［ｉ］の値（１／０）に応じた楕円曲線加算を繰り返す。
具体的には、まず、ビット判定部５１０ａは、当該桁ｋ［１］の値を判定する。その結果、ｋ［１］＝０より、加算要素特定部５１０ｂは、加算対象をマイナス表現とする加算要素を特定する。具体的には、楕円曲線加算に必要な要素として、（２＾（１＋１）−２）＊Ｇと（２＾（１＋１））＊Ｇと２＊Ｇとを生成し、楕円加算部５３０に楕円曲線加算を実行させる。
【０１４８】
続いて、ビット判定部５１０ａは、次の上位桁ｋ［２］の値を判定する。その結果、ｋ［１］＝０より、加算要素特定部５１０ｂは、同様にして、加算対象をマイナス表現とする加算要素を特定する。具体的には、楕円曲線加算に必要な要素として、（２＾（２＋１）−２）＊Ｇと（２＾（２＋１））＊Ｇと２＊Ｇとを生成し、楕円加算部５３０に楕円曲線加算を実行させる。
【０１４９】
続いて、ビット判定部５１０ａは、次の上位桁ｋ［３］の値を判定する。その結果、ｋ［１］＝１より、加算要素特定部５１０ｂは、加算対象をプラス表現とする加算要素を特定する。具体的には、楕円曲線加算に必要な要素として、（２＾３＋６）＊Ｇと（２＾３）＊Ｇと６＊Ｇとを生成し、楕円加算部５３０に楕円曲線加算を実行させる。
このようにして、ｋ［１］からｋ［５］について、プラス表現又はマイナス表現を用いた楕円曲線加算を繰り返すことで、最終的な値ｋ＊Ｇが算出される。
【０１５０】
４．実施形態４の効果
本実施の形態における楕円曲線演算装置５００は、実施の形態１〜３と同様に、楕円加算の繰り返し計算において、（２＾ｉ）＊Ｇが加算ごとに出現しており、（２＾ｉ）＊Ｇ（ｉ＝１，２，……，ｎ−１）の座標のテーブルを有効に使用することができている。そのため、計算量が削減され、従来例３に比べ、計算速度は、約１．３倍高速である。
【０１５１】
実施の形態１〜３の楕円曲線演算装置と異なる点は、一連の計算手順を一括で生成するための予備計算を行っていない点である。本実施の形態では、計算手順を一括で生成しておくのではなく、スカラ倍演算における楕円曲線加算ごとに分散して計算手順を生成（表現形式を判断）している。これによって、予備計算とスカラ倍演算とが渾然と一体化されることとなり、個々の楕円曲線加算に必要なパラメータだけが生成されて使用されることとなり、プログラム規模や回路規模が縮小化され、処理速度が向上され得る。
【０１５２】
以上より、実施の形態４によって、高速な楕円曲線演算が可能になり、さらにその処理は計算機に適した形になっているとともに、より小さな規模のプログラムや回路での実現が可能であり、本発明の実用的価値は非常に大きい。
【０１５３】
［実施の形態５］
次に、本発明の実施の形態５における楕円曲線演算装置について説明する。
１．楕円曲線演算装置６００の構成
図１９は、実施の形態５における楕円曲線演算装置６００の構成を示すブロック図である。この楕円曲線演算装置６００は、実施の形態１と同様に、専用のプログラムを実行するコンピュータ装置又はＬＳＩ等の論理回路で実現され、有限体ＧＦ（ｐ）上のモンゴメリ型楕円曲線Ｅ：Ｂ×ｙ＾２＝ｘ＾３＋Ａ×ｘ＾２＋ｘのパラメータｐ（素数）、ＧＦ（ｐ）の元A、Bと、Ｅ（ＧＦ（ｐ））に属する点Ｇと、その点Ｇの一定倍数の値（ｎ個の値）が予め与えられ、ｎビットの任意のｋを入力として、点Ｇのスカラ倍ｋ＊Ｇを出力する演算装置であり、点Ｇの一定倍数の値を有効活用しながら計算する点に特徴を有し、計算手順生成部６１０とスカラ倍演算部６２０とから構成される。
【０１５４】
この楕円曲線演算装置６００は、予め保持する点Ｇの一定倍数の値を用いる点で実施の形態１と共通するが、それらの値が、２＊Ｇ及び（２＾（ｉ＋１）＋２＾ｉ）＊Ｇ（ただし、ｉ＝０，１，２，……，ｎ−２）である点で、（２＾ｉ）＊Ｇ（ただし、ｉ＝１，２，……，ｎ−１）を予め保持する実施の形態１と異なる。
【０１５５】
（計算手順生成部６１０の処理）
計算手順生成部６１０は、点Ｇのスカラ倍ｋ＊Ｇを算出するための計算手順を生成する予備計算を実行する処理部であり、ｋ＊ＧをＧの一定倍、つまり、２＊Ｇ又は（２＾（ｉ＋１）＋２＾ｉ）＊Ｇを用いた加算形に分割することを繰り返すとともに、そのときの分割の対象が分割によって得られた加算要素であるか２つの加算要素の差であるか（分割タイプ）を特定する分割対象特定部６１０ａと、分割対象特定部６１０ａによって特定された分割タイプを配列として出力する配列生成出力部６１０ｂとからなる。
【０１５６】
図２０は、計算手順生成部６１０による係数分割の手法を示す計算フロー図である。本実施の形態においては、分割対象特定部６１０ａは、次の２つのルールに従って、係数分割をする。
【０１５７】
第１のルールは、分割の方法に関するものである。ここでは、分割対象特定部６１０ａは、本図の上欄［係数分割の指針］のルール１に示されるように、分割の対象（（２＾ｎ）＋ｃ）＊Ｇに対して、ｃ≦２＾（ｎ−１）である場合には、プラス表現の加算要素に分割、つまり、（２＾（ｎ−２）＋ｃ）＊Ｇと（２＾（ｎ−１）＋２＾（ｎ−２））＊Ｇとに分割し、ｃ＞２＾（ｎ−１）である場合には、マイナス表現の加算要素に分割、つまり、（２＾（ｎ−１）＋ｄ）＊Ｇと（２＾ｎ＋２＾（ｎ−１））＊Ｇとに分割する（ただし、ｄ＝２＾ｎ−ｃ）。
【０１５８】
このように、分割によって得られる加算要素の少なくとも１つが、２つの連続する２のべき乗和（２＾（ｎ−１）＋２＾（ｎ−２））となるように分割する。つまり、係数が２のべき乗和（２＾（ｎ−１）＋２＾（ｎ−２））となる加算要素（以下、「第１加算要素」と呼ぶ）と、そうでない加算要素（以下、「第２加算要素」と呼ぶ）とに分割する。なお、係数分割によって２つの連続する２のべき乗和（２＾（ｎ−１）＋２＾（ｎ−２））を生成するのは、後述するように、このような係数倍の点Ｇの値が予め保持された記憶テーブルを有効に使用して楕円曲線加算を行うためである。
【０１５９】
第２のルールは、分割の対象に関するものである。ここでは、分割対象特定部６１０ａは、本図の上欄［係数分割の指針］のルール２に示されるように、（i）第２加算要素と、（ii）第１加算要素と第２加算要素との差のうち、大きい方を分割する。つまり、第２加算要素と上記差とを比較し、大きい方に対して分割するという処理を繰り返す。これによって、係数分割の回数が減少される。
【０１６０】
具体的には、本図のルール２に示されるように、（２＾６＋７）を分割して得られる第１加算要素（２＾５＋２＾４）、第２加算要素（２＾４＋７）及び差（２＾５−７）において、第２加算要素（２＾４＋７）と差（２＾５−７）とを比較し、大きい方（２＾５−７）に対して、次の係数分割を繰り返す。
【０１６１】
なお、上記比較における残った方（小さい方）の値に対する係数分割が不要であるのは、続く係数分割において必ず出現することになる（係数分割の対象になる）からである。
【０１６２】
以上の２つのルールに従って係数分割した場合の具体例は、本図の［具体例］に示される通りである。８７＊Ｇについて、まず、その係数（８７；２＾６＋２３）を第１加算要素（２＾５＋２＾４）と第２加算要素（２＾４＋２３）とに分割し、さらに、それらの差（２＾５−２３）を算出することで、最初の係数分割を終える。
【０１６３】
次に、得られた第２加算要素（２＾４＋２３＝２＾５＋７）と差（２＾５−２３＝２＾３＋１）とを比較し、大きい方（２＾５＋７）に対して係数分割を行う。その結果、第１加算要素（２＾４＋２＾３）と第２加算要素（２＾３＋７）とそれらの差（２＾４−７）を得る。
【０１６４】
このようにして、第２加算要素の係数と差の係数のいずれもが、２つの連続する２のべき乗和、又は、２となるまで、繰り返す。なお、このような係数分割を終えた後は、係数分割とは逆の方向（下位桁から上位桁に向けて）に、後述する記憶テーブルを参照しながら楕円曲線加算を繰り返すことで、最終的に、点Ｇのスカラ倍点（８７＊Ｇ）を得ることができる。
【０１６５】
図２１は、計算手順生成部６１０の詳細な処理手順を示すフローチャートである。なお、この計算手順生成部６１０が生成する計算手順については、以下のルールで表現するものとしている。
【０１６６】
つまり、計算手順生成部６１０は、ｋビットの任意の整数ｋを入力として、配列｛Ｓ［ｉ］｝（Ｓ［ｉ］は配列のｉ番目の数、１≦ｉ≦｜ｋ｜）を出力する。配列Ｓ［ｉ］において、Ｓ［１］は、ｋの２進表現における最下位桁から連続する「０」の個数に関する情報を示し、Ｓ［２］は、係数分割における最後の分割対象についての分割タイプを示し、Ｓ［ｉ］（ｉ＝３，４，…）は、第ｉ番目の係数分割のおける分割タイプを示す。
【０１６７】
具体的には、Ｓ［１］は、ｋ＝ｋ’×２＾ｅと表現したときにおける値ｅを示し、Ｓ［２］は、以下に示されるように、最後の分割における分割タイプを示し、Ｓ［ｉ］（ｉ＝３，４，…）は、第ｉ番の係数分割において、その分割後に分割されるものが第２加算要素であるか（そのときには、第１の分割タイプであることを示すように、Ｓ［ｉ］＝１とする）、又は、その分割後に分割されるものが両加算要素の差であるか（そのときには、第２の分割タイプであることを示すように、第Ｓ［ｉ］＝２とする）を示す。ここで、ｋ［１］及びｋ［２］については、
（１）ｋ’＝１の場合には（特殊な場合であるが）、
Ｓ［１］＝１、Ｓ［２］＝３とし、
（２）ｋ’＝３の場合には（特殊な場合であるが）、
Ｓ［１］＝ｅ、Ｓ［２］＝４とし、
（３）それ以外は（ほとんどの場合であるが）、
（ａ）最後の分割対象となる係数が２＾２＋１の場合には、
Ｓ［１］＝ｅ、Ｓ［２］＝１とし、
（ｂ）最後の分割対象となる係数が２＾３＋１の場合には、
Ｓ［１］＝ｅ、Ｓ［２］＝２としている。
なお、上記（３）の場合は、最後の分割対象となる係数は、上記（ａ）及び（ｂ）のいずれかになることがわかっている。
【０１６８】
図２１において、分割対象特定部６１０ａは、以下の手順に従って、配列｛Ｓ［ｉ］｝を特定する。なお、以下では、
ｋ＝ｋ［ｎ−１］×２＾（ｎ−１）＋ｋ［ｎ−２］×２＾（ｎ−２）＋……＋ｋ［１］×２＋ｋ［０］
とおいたときのｋのビット表現を［ｋ［ｎ−１］、ｋ［ｎ−２］、……、ｋ［１］、ｋ［０］］とする。
ステップＳ９５１：ｋ＝ｋ’×２＾ｅを満たす最大のｅ，ｋ’を求める。
ステップＳ９５２：処理対象となるビット位置を示すカウンタｃ←ｎ−ｅ−１，配列Ｓ［ｉ］の要素を指定するインデックスｃ１←２とする。
ステップＳ９５３：ｋ’＝１であるか判定。ｋ’＝１の場合、上記（１）のケースに相当し、ステップＳ９５４へ。それ以外はステップＳ９５５へ。
ステップＳ９５４：Ｓ［１］←１，Ｓ［２］←３，Ｓ［３］←２，Ｓ［４］←２，…，Ｓ［ｅ］←２として（Ｓ９５４ａ）、配列｛Ｓ［ｉ］｝を出力し（Ｓ９５４ｂ）、終了。
ステップＳ９５５：ｋ’＝３であるか判定（Ｓ９５５ａ）。ｋ’＝３の場合、上記（２）のケースに相当し、Ｓ［１］←ｅ，Ｓ［２］←４として（Ｓ９５５ｂ）、配列｛Ｓ［ｉ］｝を出力し（Ｓ９５５ｃ）、終了。
【０１６９】
ステップＳ９５６：ｋ’［ｃ−１］＝１であるか判定（Ｓ９５６ａ）。ｋ’［ｃ−１］＝１の場合、マイナス表現による係数分割に相当し、ｃ←ｃ＋１，ｃ２←０として（Ｓ９５６ｂ）、ステップＳ９５８へ。それ以外は、プラス表現による係数分割に相当し、次のステップへ。
ステップＳ９５７：ｋ’［ｃ−２］＝０，ｋ’［ｃ−３］＝０の両方が成り立つか判定（Ｓ９５７ａ）。両方成り立つ場合は、この係数分割の次に分割されるものが両加算要素の差となるケースであるので、ｃ２←−１として（Ｓ９５７ｂ）、次のステップへ。それ以外は、この係数分割の次に分割されるものが第２加算要素となるケースであるので、ステップＳ９５９へ。
ステップＳ９５８：ｋ’←２＾ｃ＋２＾（ｃ−１）−ｋ’としてｋ’を更新し，Ｓ［ｃ１］←２とセットすることで、第２の分割タイプによる係数分割を終える。ステップＳ９６１へ。
ステップＳ９５９：ｋ’［ｃ−２］＝０が成り立つか判定（Ｓ９５９ａ）。成り立つ場合、ｃ２←−１（Ｓ９５９ｂ），成り立たない場合は、ｃ２←０（Ｓ９５９ｃ）とする。
【０１７０】
ステップＳ９６０：ｋ’←ｋ’−２＾（ｃ−１）−２＾（ｃ−２）としてｋ’を更新し，Ｓ［ｃ１］←１とセットすることで、第１の分割タイプによる係数分割を終える。
ステップＳ９６１：次の桁に移行するために、ｃ←ｃ−１＋ｃ２，ｃ１←ｃ１＋１とする。
ステップＳ９６２：ｋ’＝５またはｋ’＝９であるか判定。ｋ’＝５の場合、上記（３）（ａ）のケースに相当し、次のステップへ。ｋ’＝９の場合、上記（３）（ｂ）のケースに相当し、ステップＳ９６４へ。それ以外は、さらに係数分割の必要があるので、ステップＳ９５６へ戻り、分割対象が「５」又は「９」となるまで、同様の処理を繰り返す。
ステップＳ９６３：Ｓ［１］←ｅ，Ｓ［２］←１として、配列｛Ｓ［ｉ］｝を出力し、終了。
ステップＳ９６４：Ｓ［１］←ｅ，Ｓ［２］←２として、配列｛Ｓ［ｉ］｝を出力し、終了。
【０１７１】
（スカラ倍演算部６２０の処理）
スカラ倍演算部６２０は、計算手順生成部６１０から出力された計算手順Ｓ［ｉ］（ｉ＝１，２，……）に基づいて、楕円曲線上の加算を繰り返すことで、最終的な計算結果ｋ＊Ｇを算出し出力する演算部であり、点Ｇの一定倍を予め記憶しているテーブル記憶部６２０ｂ、ワーキング用のメモリである一時記憶部６２０ｃ、楕円曲線上での加算を行う加算器である楕円加算部６２０ｄ及び計算手順生成部６１０からの計算手順Ｓ［ｉ］に従って各構成要素６２０ｂ〜６２０ｄを制御する演算制御部６２０ａからなる。
【０１７２】
テーブル記憶部６２０ｂは、図２２に示されるように、ｎ個の点Ｇの一定倍、つまり、２＊Ｇと（２＾（ｉ＋１）＋２＾ｉ）＊Ｇ（ただし、ｉ＝０，１，２，……，ｎ−２）を予め記憶しているＲＯＭ等である。つまり、記憶している値の個数は、実施の形態１とほぼ同じであるが、その値が異なっている。
【０１７３】
この演算制御部６２０ａは、計算手順生成部６１０による図２０の計算フロー（係数分割）とは逆の手順、即ち、テーブル記憶部６２０ｂに格納された値を参照しながら、低い桁から高い桁に向けて、楕円加算を繰り返すように各構成要素６２０ｂ〜６２０ｄを制御することによって、ｋ＊Ｇを算出させる。具体的には、演算制御部６２０ａは、図２３のフローチャートに示されるように、以下のステップに従って、計算・制御を行う。
ステップＳ９７１：まず、Ｓ［２］を判定（Ｓ９７１ａ）。Ｓ［２］＝４の場合、上記（２）のケースに相当し、ｋ＊Ｇをテーブル記憶部６２０ｂから参照して（Ｓ９７１ｂ）、出力し（Ｓ９７１ｃ）、終了。
ステップＳ９７２：ｋ［ｎ−２］＝１であるか判定（Ｓ９７２ａ）。成り立つ場合、必要な係数分割の回数（桁数）を示すカウンタｃ１←ｎ−ｅ（Ｓ９７２ｂ），それ以外は、ｃ１←ｎ−ｅ−１とする（Ｓ９７２ｃ）。
【０１７４】
ステップＳ９７３：Ｓ［２］＝３であるか判定（Ｓ９７３ａ）。成り立つ場合、上記（１）のケースに相当し、Ｕ←Ｇ，Ｖ←２＊Ｇ，ｃ２←１として（Ｓ９７３ｂ）、ステップＳ９７５へ。それ以外は、ステップＳ９７４へ。なお、本フローでは、Ｕは第２加算要素、Ｖは第１加算要素と第２加算要素との差を格納するパラメータである。また、２＊Ｇについては、テーブル記憶部６２０ｂから読み出された値である。
ステップＳ９７４：Ｓ［２］＝１であるか判定（Ｓ９７４ａ）。成り立つ場合、Ｕ←２＊Ｇ，Ｖ←Ｇ，ｃ２←１とし（Ｓ９７４ｂ）、それ以外は、Ｕ←３＊Ｇ，Ｖ←３＊Ｇ，ｃ２←２，ｃ１←ｃ１−１とする（Ｓ９７４ｃ）。なお、２＊Ｇ及び３＊Ｇについては、テーブル記憶部６２０ｂから読み出された値である。
ステップＳ９７５：以上のようにして、初期値Ｕ及びＶを決定した後に、テーブル記憶部６２０ｂを参照することにより、Ｗ←（２＾ｃ２＋２＾（ｃ２−１））＊Ｇとする。Ｗは第１加算要素を格納するパラメータである。なお、（２＾ｃ２＋２＾（ｃ２−１））＊Ｇについては、テーブル記憶部６２０ｂから読み出された値である。
【０１７５】
ステップＳ９７６：Ｓ［ｃ１］＝１であるか判定。成り立つ場合、第１の分割タイプに対応する楕円曲線加算、即ち、第２加算要素Ｕを生成するために、次のステップへ。それ以外は、第２の分割タイプに対応する楕円曲線加算、即ち、両加算要素の差Ｖを生成するために、ステップＳ９７８へ。
ステップＳ９７７：楕円加算部６２０ｄに楕円加算を実行させることで、Ｕ←Ｗ＋Ｕ（差はＶ）を算出させる。
ステップＳ９７８：楕円加算部６２０ｄにＶ←Ｗ＋Ｕ（差はＶ）を算出させる。ステップＳ９７９：ｃ１＝２であるか判定。成り立つ場合は、最後の楕円曲線加算を実行するために、ステップＳ９８１へ。
ステップＳ９８０：ｃ１←ｃ１−１，ｃ２←ｃ２＋１として、ｃ１＝２となるまで、同様の楕円曲線加算を繰り返すために、ステップＳ９７５へ戻る。
ステップＳ９８１：テーブル記憶部６２０ｂを参照することで、Ｗ←（２＾ｃ２＋１＋２＾ｃ２）＊Ｇとし，楕円加算部６２０ｄにＵ←Ｗ＋Ｕ （差はＶ）を計算させ（Ｓ９８１ａ）、その結果Ｕを最終結果として出力し（Ｓ９８１ｂ）、終了する。
【０１７６】
なお、（２＾ｃ２＋２＾（ｃ２−１））＊Ｇについては、テーブル記憶部６２０ｂから読み出された値である。また、上記のステップで使用される楕円加算の具体的な計算方法は、実施形態１で説明した通りである。
（楕円曲線演算装置６００の動作）
【０１７７】
楕円曲線演算装置６００は、入力された整数ｋを受け取り、計算手順生成部６１０へ入力する。計算手順生成部６１０は、その整数ｋより、配列｛Ｓ［ｉ］｝を計算し、スカラ倍演算部６２０へ入力する。スカラ倍演算部６２０は、入力された配列｛Ｓ［ｉ］｝より、テーブル記憶部６２０ｂに格納された値を参照しながら楕円曲線加算を繰り返すことで、楕円曲線の点Ｇのスカラ倍点ｋ＊Ｇを算出し、出力する。
【０１７８】
２．楕円曲線演算装置６００の数値例
以下では、図２４に示されるｋ＝１０２の場合の数値例を示す。
（計算手順生成部６１０での処理）
ここでは、計算手順生成部６１０による機械的な処理（ビット処理）ではなく、その意味内容の観点から説明する。
【０１７９】
図２４の［計算手順生成］に示されるように、分割対象特定部６１０ａは、１０２＝５１×２＾１より、ｋ’＝５１、ｅ＝１と特定する（ステップＳ９５２）。なお、ｋ’＝５１より、ｋ’［５］、ｋ’［４］、ｋ’［３］、ｋ’［２］、ｋ’［１］、ｋ’［０］は、それぞれ、１，１，０，０，１，１である。
【０１８０】
次に、ｋ’に対して係数分割を繰り返す（ステップＳ９５２〜Ｓ９６２）。まず、ｋ’＝５１＝２＾５＋１９に対して、１９＞２＾４より、マイナス表現による係数分割、即ち、２＾５＋１９＝２＾６−１３を、第１加算要素の係数（２＾５＋２＾４）と第２加算要素の係数（２＾４−１３）とに分割し、さらに、それらの差（２＾５＋１３）を算出する。そして、第２加算要素の係数（２＾４−１３）と差（２＾５＋１３）と比較し、差のほうが大きいので、次には、その差（２＾５＋１３）を分割する。同時に、そのこと（第２の分割タイプによる係数分割）を示す配列要素（Ｓ［３］＝２）を決定する（ステップＳ９５８）。
【０１８１】
次に、分割の対象となる係数（２＾５＋１３）に対しては、１３≦２＾４より、プラス表現による係数分割、即ち、第１加算要素の係数（２＾４＋２＾３）と第２加算要素の係数（２＾３＋１３）とに分割し、さらに、それらの差（２＾４−１）を算出する。そして、第２加算要素の係数（２＾３＋１３）と差（２＾４１３）と比較し、第２加算要素のほうが大きいので、次には、その第２加算要素（２＾３＋１３）を分割する。同時に、そのこと（第１の分割タイプによる係数分割）を示す配列要素（Ｓ［４］＝１）を決定する（ステップＳ９６０）。
【０１８２】
以下、同様の係数分割を繰り返すことにより、配列要素Ｓ［５］＝１を決定し（ステップＳ９６０）、最後の分割対象「９」を得る。この分割対象「９」は、上記（３）（ｂ）のケースに相当することから、Ｓ［１］＝ｅ＝１、Ｓ［２］＝２と決定する（ステップＳ９６４）。
【０１８３】
最後に、配列生成出力部６１０ｂは、以上の係数分割で得られた配列Ｓ［１］、Ｓ［２］、Ｓ［３］、Ｓ［４］、Ｓ［５］の値、即ち、｛１，２，２，１，１｝をスカラ倍演算部６２０に出力する（ステップＳ９６５）。
【０１８４】
（スカラ倍演算部６２０での処理）
次に、計算手順生成部６１０から上記配列｛Ｓ［ｉ］｝を取得したスカラ倍演算部６２０の処理について、機械的な処理（ビット処理）ではなく、その意味内容の観点から説明する。
【０１８５】
図２４の［スカラ倍演算］に示されるように、スカラ倍演算部６２０は、まず、Ｓ［２］＝２、Ｓ［１］＝１より、初期値として、第２加算要素Ｕ（６＊Ｇ）と両加算要素の差（６＊Ｇ）を得る（ステップＳ９７４ｃ；なお、Ｓ［１］＝１より、各係数は２＾１倍される）。
【０１８６】
そして、テーブル記憶部６２０ｂから第１加算要素Ｗ（（２＾３＋２＾２）＊Ｇ）を読み出し（ステップＳ９７５）、Ｓ［５］＝１より（ステップＳ９７６）、テーブル記憶部６２０ｂから参照した第１加算要素Ｗ（（２＾３＋２＾２）＊Ｇ）と初期値の第２加算要素Ｕ（（２＾２＋２＾１）＊Ｇ）との楕円加算を実行し、その結果を、第２加算要素Ｕ（（２＾４＋２＾１）＊Ｇ）とする（ステップＳ９７７）。
【０１８７】
同様にして、Ｓ［４］＝１より（ステップＳ９７６）、テーブル記憶部６２０ｂから参照した第１加算要素Ｗ（（２＾４＋２＾３）＊Ｇ）と直前で算出した第２加算要素Ｕ（（２＾３＋１０）＊Ｇ）との楕円加算を実行し、その結果を、第２加算要素Ｕ（（２＾５＋１０）＊Ｇ）とする（ステップＳ９７７）。
【０１８８】
続いて、Ｓ［３］＝２より（ステップＳ９７６）、テーブル記憶部６２０ｂから参照した第１加算要素Ｗ（（２＾５＋２＾４）＊Ｇ）と直前で算出した第２加算要素Ｕ（（２＾４＋２６）＊Ｇ）との楕円加算を実行し、その結果を、差分値Ｖ（（２＾６＋２６）＊Ｇ）とする（ステップＳ９７８）。
【０１８９】
最後に、テーブル記憶部６２０ｂから参照した第１加算要素Ｗ（（２＾６＋２＾５）＊Ｇ）と直前で算出した差分値Ｖ（（２＾６＋２６）＊Ｇ）に基づいて、第１加算要素Ｗ（（２＾６＋２＾５）＊Ｇ）と第２加算要素Ｕ（（２＾５−２６）＊Ｇ）との楕円加算を実行し（ステップＳ９８１ａ）、その結果を、最終的な結果（２＾７−２６）＊Ｇ、つまり、１０２＊Ｇの結果として出力する（ステップＳ９８１ｂ）。
【０１９０】
以上のように、実施の形態５では、計算手順生成部６１０が生成する計算手順Ｓ［ｉ］は、予め保持された点Ｇの２のべき乗倍の値を用いるのではなく、点Ｇに対して２つの連続する２のべき乗和だけスカラ倍された値を用いるように、係数分割している。これによって、実施の形態１と比べ、より少ない回数の楕円加算で、点Ｇのスカラ倍ｋ＊Ｇが算出される。
【０１９１】
４．実施形態５の効果
本実施の形態の楕円曲線演算装置６００によれば、例えば、図１０に示された実施の形態２における１０２＊Ｇの計算フロー（６回の加算）と、図２４に示された本実施の形態のもの（４回の加算）と比較してわかるように、１０２＊Ｇについては、実施の形態１〜４に比べ、１．５倍高速である。つまり、従来例３と比べ、２．２６倍高速となる。
【０１９２】
また、８７＊Ｇの計算であれば、本実施の形態の楕円曲線演算装置６００によれば、４回の加算で済み、７回の加算を必要とする実施の形態１〜４に比べ、１．７５倍高速となり、従来例３と比べ、２．２６倍高速となる。
なお、本実施の形態におけるテーブル記憶部６２０ｂに格納されている値は、実施の形態１〜４と異なるが、その個数は、ほぼ同じであるので（実施の形態１〜４では（ｎ−１）個の値が格納され、実施の形態５ではｎ個の値が格納されているので）、その記憶容量はほぼ同一である。
【０１９３】
以上より、実施形態５によって、記憶テーブルのサイズがほぼ同一であるにも拘わらず、実施の形態１〜４に比べ、よりも高速に、点Ｇのスカラ倍演算が実行され、リアルタイム通信における秘匿化等の応用することができ、本発明の実用的価値は非常に大きい。
【０１９４】
なお、実施の形態５では、テーブル記憶部６２０ｂに、ｎ個の点Ｇの一定倍、つまり、２＊Ｇと（２＾（ｉ＋１）＋２＾ｉ）＊Ｇ（ただし、ｉ＝０，１，２，……，ｎ−２）が予め記憶されていたが、これらの一部だけが記憶されていてもよい。例えば、２＊Ｇについては、スカラ倍演算部６２０が２倍算を行うことによって算出し、テーブル記憶部６２０ｂ内に格納しなくてもよい。これによって、テーブル記憶部６２０ｂに予め格納される値の個数は、（ｎ−１）個となり、実施の形態１〜４と同じになる。
【０１９５】
以上の実施形態１〜５における楕円曲線演算装置は、楕円曲線を用いた公開鍵暗号におけるシステムパラメータであるベース点Ｇのスカラ倍伝算を高速を行うことができ、公開鍵暗号を用いた秘密通信やデジタル署名の計算エンジンとして有効である。このような楕円曲線演算装置は、汎用のコンピュータで実行されるプログラムとして実現したり、ＬＳＩ等のＩＣとして実現することができる。そして、インターネット等の通信ネットワークにおける電子決済、電子署名、電子メール、あるいは、携帯電話機等による通信データの秘匿化に好適である。
【０１９６】
【発明の効果】
以上の説明から明らかなように、本発明に係る楕円曲線演算装置は、以下の条件を満たすスカラ倍演算を実行する。
（１）ワイヤーシュトラス型楕円曲線よりも高速に楕円曲線演算（加算／２倍算）を行うことができるモンゴメリ型楕円曲線上の演算を行う。
（２）楕円曲線暗号におけるシステムパラメータであるベース点Ｇのスカラ倍演算において、点Ｇの一定係数倍の点、つまり、点Ｇの２のべき乗（２＾ｉ）＊Ｇ倍の値、あるいは、点Ｇの連続する２つの２のべき乗和（２＾（ｎ−１）＋２＾（ｎ−２））＊Ｇ倍の値のいずれかを格納したテーブルを有効活用することができる。
【０１９７】
以上のことから、本発明に係る楕円曲線演算装置は、高速な楕円曲線演算が可能であり、秘密通信やデジタル署名における暗号及び復号処理を高速に実行することができる。特に、本発明は、インターネットを利用した電子決済や電子署名、コンピュータや携帯電話機等の通信機器による電子メールや通話の秘匿化に必要な暗号化及び復号化処理を大幅に高速化させることができ、デジタル通信が広く普及した今日における実用的価値は極めて高い。
【図面の簡単な説明】
【図１】本発明の実施の形態１における楕円曲線演算装置の構成を示す機能ブロック図である。
【図２】同楕円曲線演算装置の計算手順生成部の動作を示すフローチャートである。
【図３】同楕円曲線演算装置のスカラ倍演算部の動作を示すフローチャートである。
【図４】同楕円曲線演算装置によるスカラ倍演算の手法（基本的な考え；アプローチ１）を示す計算フロー図である。
【図５】同楕円曲線演算装置によるスカラ倍演算の手法（アプローチ１を発展させたアプローチ２）を示す計算フロー図である。
【図６】実施の形態１と従来例３での計算手法を比較説明するための図である。
【図７】本発明の実施の形態２における楕円曲線演算装置の構成を示す機能ブロック図である。
【図８】同楕円曲線演算装置の計算手順生成部の動作を示すフローチャートである。
【図９】同楕円曲線演算装置のスカラ倍演算部の動作を示すフローチャートである。
【図１０】同楕円曲線演算装置によるスカラ倍演算の手法を示す計算フロー図である。
【図１１】本発明の実施の形態３における楕円曲線演算装置の構成を示す機能ブロック図である。
【図１２】同楕円曲線演算装置の計算手順生成部の動作を示すフローチャートである。
【図１３】同楕円曲線演算装置のスカラ倍演算部の動作を示すフローチャートである。
【図１４】同楕円曲線演算装置の計算手順生成部による計算手順（配列｛Ｓ［ｉ］｝）の生成過程を示す計算フロー図である。
【図１５】図１４に示された具体例に対応するスカラ倍演算部の動作を示す図である。
【図１６】本発明の実施の形態４における楕円曲線演算装置の構成を示す機能ブロック図である。
【図１７】同楕円曲線演算装置の動作を示すフローチャートである。
【図１８】同楕円曲線演算装置の動作を示す計算フロー図である。
【図１９】本発明の実施の形態５における楕円曲線演算装置の構成を示す機能ブロック図である。
【図２０】同楕円曲線演算装置の計算手順生成部による係数分割の手法を示す計算フロー図である。
【図２１】同楕円曲線演算装置の計算手順生成部の詳細な処理手順を示すフローチャートである。
【図２２】同楕円曲線演算装置のテーブル記憶部の格納データを示す図である。
【図２３】同楕円曲線演算装置の演算制御部による計算・制御の手順を示すフローチャートである。
【図２４】同楕円曲線演算装置によるスカラ倍演算の具体例を示す図である。
【図２５】エルガマル署名によるデジタル署名方式の手順を示すシーケンス図である。
【図２６】従来例３におけるスカラ倍演算の計算手順を模式的に示す計算フロー図である。
【符号の説明】
２００、３００、４００、５００、６００ 楕円曲線演算装置
２１０、３１０、４１０、６１０ 計算手順生成部
２１０ａ、５１０ａ 加算要素特定部
２１０ｂ、３１０ｂ、４１０ｂ、６１０ｂ 配列生成出力部
２２０、３２０、４２０、６２０ スカラ倍演算部
２２０ａ、３２０ａ、４２０ａ、５１０、６２０ａ 演算制御部
２２０ｂ、３２０ｂ、４２０ｂ、５２０、６２０ｂ テーブル記憶部
２２０ｃ、３２０ｃ、４２０ｃ、５１０ｃ、６２０ｃ 一時記憶部
２２０ｄ、３２０ｄ、４２０ｄ、５３０、６２０ｄ 楕円加算部
３１０ａ 加算タイプ特定部
４１０ａ 加算要素表現切替点特定部
５１０ａ ビット判定部
６１０ａ 分割対象特定部

Claims (14)

1. ｎビットの任意の整数ｋを入力とし、予め与えられた有限体Ｆ上のモンゴメリ型楕円曲線Ｅ上の点Ｇに対して、スカラ倍点ｋ＊Ｇを出力する楕円曲線演算装置であって、
   予め決定されたｎ以下の種類のスカラを係数とする点Ｇのスカラ倍点をＧ，２＊Ｇ，（２＾２）＊Ｇ，…，（２＾（ｎ−１））＊Ｇのいずれかを第１加算要素とする前記楕円曲線Ｅ上の加算を繰り返すことによって前記スカラ倍点ｋ＊Ｇを算出するスカラ倍演算手段と、
   前記楕円曲線Ｅ上の加算の繰り返し手順を示す計算手順を生成する計算手順生成手段とを備え、
   前記スカラ倍演算手段は、前記第１加算要素の少なくとも一部を記憶するテーブル記憶部を有し、前記テーブル記憶部に記憶された点を参照して第１加算要素として、前記計算手順生成手段が生成した計算手順に従って前記スカラ倍点ｋ＊Ｇを算出し、
   前記計算手順生成手段は、自然数ｍ，ｕに対して、
   （２＾（ｍ−１）＋ｕ）＊Ｇ、（２＾（ｍ−１））＊Ｇ及びｕ＊Ｇから（２＾ｍ＋ｕ）＊Ｇを算出する第１計算、又は、
   （２＾ｍ）＊Ｇ、（２＾ｍ−ｕ）＊Ｇ及びｕ＊Ｇから（２＾（ｍ＋１）−ｕ）＊Ｇを算出する第２計算、又は、
   （２＾ｍ）＊Ｇ、−（２＾ｍ−ｕ）＊Ｇ及び（２＾（ｍ＋１）−ｕ）＊Ｇからｕ＊Ｇを算出する第３計算を前記楕円曲線Ｅ上の加算とする計算手順を生成する
   ことを特徴とする楕円曲線演算装置。
2. 前記計算手順生成手段は、前記ｋの各ビットの値に応じて、前記楕円曲線Ｅ上の加算と前記第１〜第３計算の少なくとも１つとを対応づけることにより、前記計算手順を生成する
   ことを特徴とする請求項１記載の楕円曲線演算装置。
3. 前記計算手順生成手段は、前記ｋのビットの値が０である場合には、そのビットに対応する前記楕円曲線Ｅ上の加算として少なくとも前記第１計算を対応させ、前記ビットの値が１である場合には、そのビットに対応する前記楕円曲線Ｅ上の加算として少なくとも前記第２計算を対応させることにより、前記計算手順を生成する
   ことを特徴とする請求項２記載の楕円曲線演算装置。
4. 前記計算手順生成手段は、前記楕円曲線Ｅ上の加算の繰り返しにおける個々の加算において、前記第１加算要素と加算される第２加算要素の表現形式が前記第１計算におけるプラス表現（２＾（ｍ−１）＋ｕ）＊Ｇであるか、前記第２計算におけるマイナス表現（２＾ｍ−ｕ）＊Ｇであるかを特定する表現形式情報を前記計算手順として生成し、
   前記スカラ倍演算手段は、前記楕円曲線Ｅ上の加算の繰り返しにおける個々の加算においては、前記表現形式情報に基づいて、前記第１〜第３計算のいずれかの計算を行う
   ことを特徴とする請求項１記載の楕円曲線演算装置。
5. 前記表現形式情報は、前記楕円曲線Ｅ上の加算の繰り返しにおける加算ごとに、前記第２加算要素が前記プラス表現及び前記マイナス表現のいずれの表現からいずれの表現に切り替わるかを示す情報である
   ことを特徴とする請求項４記載の楕円曲線演算装置。
6. 前記表現形式情報は、前記楕円曲線Ｅ上の加算の繰り返しにおいて、前記第２加算要素が前記プラス表現及び前記マイナス表現のいずれかの表現形式で連続して出現する個数を示す情報である
   ことを特徴とする請求項４記載の楕円曲線演算装置。
7. ｎビットの任意の整数ｋを入力とし、予め与えられた有限体Ｆ上のモンゴメリ型楕円曲線Ｅ上の点Ｇに対して、スカラ倍点ｋ＊Ｇを出力する楕円曲線演算装置であって、
   予め決定されたｎ以下の種類のスカラを係数とする点Ｇのスカラ倍点を２＊Ｇ，３＊Ｇ ，６＊Ｇ，１２＊Ｇ，…，（２＾（ｎ−１）＋２＾（ｎ−２））＊Ｇのいずれかを第１加算要素とする前記楕円曲線Ｅ上の加算を繰り返すことによって前記スカラ倍点ｋ＊Ｇを算出するスカラ倍演算手段と、
   前記楕円曲線Ｅ上の加算の繰り返し手順を示す計算手順を生成する計算手順生成手段を備え、
   前記スカラ倍演算手段は、前記第１加算要素の少なくとも一部を記憶するテーブル記憶部を有し、前記テーブル記憶部に記憶された点を参照して第１加算要素として、前記計算手順生成手段が生成した計算手順に従って前記スカラ倍点ｋ＊Ｇを算出し、
   前記計算手順生成手段は、自然数ｍ，ｕに対して、
   第１加算要素（２＾（ｍ−１）＋２＾（ｍ−２））＊Ｇ、第２加算要素（２＾（ｍ−２）＋ｕ）＊Ｇ及び前記第１加算要素と前記第２加算要素との差（２＾（ｍ−１）−ｕ）から（２＾ｍ＋ｕ）＊Ｇを算出する第１計算、又は、
   第１加算要素（２＾ｍ＋２＾（ｍ−１））＊Ｇ、第２加算要素（２＾（ｍ−１）−ｕ）＊Ｇ及び前記第１加算要素と前記第２加算要素との差（２＾ｍ＋ｕ）から（２＾（ｍ＋１）−ｕ）＊Ｇを算出する第２計算を前記楕円曲線Ｅ上の加算とする計算手順を生成する
   ことを特徴とする楕円曲線演算装置。
8. 前記計算手順生成手段は、前記第１又は前記第２計算による楕円曲線Ｅ上の加算によって得られた結果を、次の繰り返し加算における第２加算要素とするか第１加算要素と第２加算要素との差とするかを示す分割対象情報を前記計算手順として生成する
   ことを特徴とする請求項７記載の楕円曲線演算装置。
9. 前記計算手順生成手段は、前記ｋをｋ’×２＾ｅと表現した場合における値ｋ’及び値ｅに関する情報を初期情報として前記計算手順に含ませて生成する
   ことを特徴とする請求項８記載の楕円曲線演算装置。
10. 前記計算手順生成手段は、前記ｋ’が１、３及びそれ以外の値のいずれであるかを示す情報を前記初期情報に含ませて生成する
    ことを特徴とする請求項９記載の楕円曲線演算装置。
11. 請求項１〜１０のいずれか１項に記載の楕円曲線演算装置を用いた暗号装置。
12. 自然数ｎに対しｎビットの任意の整数ｋを入力とし、予め与えられた有限体Ｆ上のモンゴメリ型楕円曲線Ｅ上の点Ｇに対して、スカラ倍点ｋ＊Ｇを出力する楕円曲線演算装置で用いられる楕円曲線演算方法であって、
    前記楕円曲線演算装置は、Ｇ，２＊Ｇ，（２＾２）＊Ｇ，…，（２＾（ｎ−１））＊Ｇの少なくとも一部を記憶するテーブル記憶部、計算手順生成手段及びスカラ倍演算手段を有し、
    前記楕円曲線演算方法は、
    前記計算手順生成手段が、前記楕円曲線Ｅ上の加算の繰り返し手順を示す計算手順を生成する計算手順生成ステップと、
    前記スカラ倍演算手段が、Ｇ，２＊Ｇ，（２＾２）＊Ｇ，…，（２＾（ｎ−１））＊Ｇのいずれかを第１加算要素とする前記楕円曲線Ｅ上の加算を繰り返すことによって前記スカラ倍点ｋ＊Ｇを算出するスカラ倍演算ステップと、を含み、
    前記計算手順生成ステップでは、自然数ｍ，ｕに対して、
    （２＾（ｍ−１）＋ｕ）＊Ｇ、（２＾（ｍ−１））＊Ｇ及びｕ＊Ｇから（２＾ｍ＋ｕ）＊Ｇを算出する第１計算、又は、
    （２＾ｍ）＊Ｇ、（２＾ｍ−ｕ）＊Ｇ及びｕ＊Ｇから（２＾（ｍ＋１）−ｕ）＊Ｇを算出する第２計算、又は、
    （２＾ｍ）＊Ｇ、−（２＾ｍ−ｕ）＊Ｇ及び（２＾（ｍ＋１）−ｕ）＊Ｇからｕ＊Ｇを算出する第３計算を前記楕円曲線Ｅ上の加算とする計算手順を生成し、
    前記スカラ倍演算ステップでは、前記テーブル記憶部に記憶された点を参照して第１加算要素として、前記計算手順生成ステップが生成した計算手順に従って前記スカラ倍点ｋ＊Ｇを算出する
    ことを特徴とする楕円曲線演算方法。
13. 自然数ｎに対しｎビットの任意の整数ｋを入力とし、予め与えられた有限体Ｆ上のモンゴメリ型楕円曲線Ｅ上の点Ｇに対して、スカラ倍点ｋ＊Ｇを出力する楕円曲線演算装置で用いられる楕円曲線演算方法であって、
    前記楕円曲線演算装置は、２＊Ｇ，３＊Ｇ，６＊Ｇ，１２＊Ｇ，…，（２＾（ｎ−１）＋２＾（ｎ−２））＊Ｇの少なくとも一部を記憶するテーブル記憶部、計算手順生成手段及びスカラ倍演算手段を有し、
    前記楕円曲線演算方法は、
    前記計算手順生成手段が、前記楕円曲線Ｅ上の加算の繰り返し手順を示す計算手順を生成する計算手順生成ステップと、
    前記スカラ倍演算手段が、２＊Ｇ及び３＊Ｇ，６＊Ｇ，１２＊Ｇ，…，（２＾（ｎ−１）＋２＾（ｎ−２））＊Ｇのいずれかを第１加算要素とする前記楕円曲線Ｅ上の加算を繰り返すことによって前記スカラ倍点ｋ＊Ｇを算出するスカラ倍演算ステップとを含み、
    前記計算手順生成ステップでは、自然数ｍ，ｕに対して、
    第１加算要素（２＾（ｍ−１）＋２＾（ｍ−２））＊Ｇ、第２加算要素（２＾（ｍ−２）＋ｕ）＊Ｇ及び前記第１加算要素と前記第２加算要素との差（２＾（ｍ−１）−ｕ）から（２＾ｍ＋ｕ）＊Ｇを算出する第１計算、又は、
    第１加算要素（２＾ｍ＋２＾（ｍ−１））＊Ｇ、第２加算要素（２＾（ｍ−１）−ｕ）＊Ｇ及び前記第１加算要素と前記第２加算要素との差（２＾ｍ＋ｕ）から（２＾（ｍ＋１）−ｕ）＊Ｇを算出する第２計算を前記楕円曲線Ｅ上の加算とする計算手順を生成し、
    前記スカラ倍演算ステップでは、前記テーブル記憶部に記憶された点を参照して第１加算要素として、前記計算手順生成ステップが生成した計算手順に従って前記スカラ倍点ｋ＊Ｇを算出する
    ことを特徴とする楕円曲線演算方法。
14. 自然数ｎに対しｎビットの任意の整数ｋを入力とし、予め与えられた有限体Ｆ上のモンゴメリ型楕円曲線Ｅ上の点Ｇに対して、スカラ倍点ｋ＊Ｇを出力する楕円曲線演算装置のためのプログラムであって、
    請求項１２または１３に記載の楕円曲線演算方法におけるステップ
    をコンピュータに実行させる
    ことを特徴とするプログラム。

Images