JP2003208096A - 楕円曲線変換装置、楕円曲線変換方法、楕円曲線利用装置及び楕円曲線生成装置 - Google Patents

Abstract

(57)【要約】 【課題】 任意の楕円曲線を、その安全性を維持したま
ま、より計算量が削減される楕円曲線ｙ＾２＝ｘ＾３−
３ｘ＋ｂに、極めて高い確率で、変換することができる
楕円曲線変換装置等を提供する。 【解決手段】 有限体Ｆ上の第１楕円曲線を有限体Ｆ上
の第２楕円曲線に変換する楕円曲線変換装置であって、
第１楕円曲線と位数が同じで、かつ、一定関係を有する
楕円曲線群であるＬ1次同種な楕円曲線群の中から、楕
円曲線上での演算の計算量が削減される高速化条件を満
たす楕円曲線を探索する楕円曲線生成部２１０と、楕円
曲線生成部２１０による探索により、高速化条件を満た
す楕円曲線が探索されたか否かを判定する楕円曲線条件
判定部２２０と、楕円曲線条件判定部２２０によって高
速化条件を満たす楕円曲線が探索されたと判断された場
合に、当該楕円曲線を出力する楕円曲線出力部２３０と
を備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、情報セキュリテイ
技術としての暗号技術に関し、特に、楕円曲線を用いる
秘密通信、デジタル署名及び鍵共有技術に関する。

【０００２】

【従来の技術】１．公開鍵暗号 近年、コンピュータ技術と通信技術とに基づくデータ通
信が広く普及してきており、このデータ通信において
は、秘密通信方式又はデジタル署名方式が用いられてい
る。ここで、秘密通信方式とは、特定の通信相手以外に
通信内容を漏らすことなく通信を行う方式である。また
デジタル署名方式とは、通信相手に通信内容の正当性を
示したり、発信者の身元を証明する通信方式である。

【０００３】これらの秘密通信方式又はデジタル署名方
式には公開鍵暗号と呼ばれる暗号方式が用いられる。公
開鍵暗号は通信相手が多数の時、通信相手毎に異なる暗
号鍵を容易に管理するための方式であり、多数の通信相
手と通信を行うのに不可欠な基盤技術である。公開鍵暗
号を用いる秘密通信では、暗号化鍵と復号化鍵とが異な
り、復号化鍵は秘密にするが、暗号化鍵は公開する。

【０００４】この公開鍵暗号の安全性の根拠として離散
対数問題が用いられる。離散対数問題には、代表的なも
のとして、有限体上定義されるもの及び楕円曲線上定義
されるものがある（例えば、非特許文献１）。

【０００５】２．楕円曲線上の離散対数問題 楕円曲線上の離散対数問題について、以下に述べる。楕
円曲線上の離散対数問題とは、Ｅ（ＧＦ（ｐ））を有限
体ＧＦ（ｐ）上で定義された楕円曲線とし、楕円曲線Ｅ
の位数が大きな素数で割り切れる場合に、楕円曲線Ｅに
含まれる元Ｇをベースポイントとする。この時、楕円曲
線Ｅに含まれる与えられた元Ｙに対して、 （式１） Ｙ＝ｘ＊Ｇ となる整数ｘが存在するならば、ｘを求めよ、という問
題である。

【０００６】ここで、ｐは素数、ＧＦ（ｐ）はｐ個の元
を持つ有限体である。また、この明細書において、記号
＊は、楕円曲線に含まれる元を複数回加算する演算を示
し、ｘ＊Ｇは、次式に示すように、楕円曲線に含まれる
元Ｇをｘ回加算することを意味する。

【０００７】ｘ＊Ｇ＝Ｇ＋Ｇ＋Ｇ＋…＋Ｇ 離散対数問題を公開鍵暗号の安全性の根拠とするのは、
多くの元を有する有限体ＧＦ（ｐ）に対して、上記問題
は極めて難しいからである。

【０００８】３．楕円曲線上の離散対数問題を応用した
エルガマル署名 以下に、上記楕円曲線上の離散対数問題を応用したエル
ガマル署名によるデジタル署名方式について、図１１を
用いて、説明する。この図は、上記エルガマル署名によ
るデジタル署名方式の手順を示すシーケンス図である。
ユーザＡ１１、管理センタ１２及びユーザＢ１３は、ネ
ットワークで接続されている。ｐを素数、有限体ＧＦ
（ｐ）上の楕円曲線をＥとする。Ｅのベースポイントを
Ｇとし、Ｅの位数をｑとする。つまり、ｑは、 （式２） ｑ＊Ｇ＝０ を満たす最小の正整数である。

【０００９】なお、ｘ座標、ｙ座標共に∞である（∞、
∞）を無限遠点といい、０で表す。この０は、楕円曲線
を群とみた時に、無限遠点が加算における「零元」の役
割を果たす。

【００１０】（１）管理センタ１２による公開鍵の生成 管理センタ１２は、予め通知されているユーザＡ１１の
秘密鍵ｘＡを用いて、式３に従って、ユーザＡ１１の公
開鍵ＹＡを生成する（ステップＳ１４１〜Ｓ１４２）。 （式３） ＹＡ＝ｘＡ＊Ｇ その後、管理センタ１２は、素数ｐ、楕円曲線Ｅ及びベ
ースポイントＧをシステムパラメータとして公開し、ま
た、他のユーザＢ１３にユーザＡ１１の公開鍵ＹＡを公
開する（ステップＳ１４３〜Ｓ１４４）。

【００１１】（２）ユーザＡ１１による署名生成 ユーザＡ１１は、乱数ｋを生成する（ステップＳ１４
５）。次に、ユーザＡ１１は、 （式４） Ｒ１＝（ｒｘ，ｒｙ）＝ｋ＊Ｇ を計算し（ステップＳ１４６）、 （式５） ｓ×ｋ＝ｍ＋ｒｘ×ｘＡ （ｍｏｄ ｑ） から、ｓを計算する（ステップＳ１４７）。ここで、ｍ
は、ユーザＡ１１がユーザＢ１３へ送信するメッセージ
である。さらに、ユーザＡ１１は、得られた（Ｒ１、
ｓ）を署名としてメッセージｍと共に、ユーザＢ１３へ
送信する（ステップＳ１４８）。

【００１２】（３）ユーザＢ１３による署名検証 ユーザＢ１３は、 （式６） ｓ＊Ｒ１＝ｍ＊Ｇ＋ｒｘ＊ＹＡ が成立するかどうか判定することにより、送信者である
ユーザＡ１１の身元を確認する（ステップＳ１４９）。
これは、 （式７） ｓ＊Ｒ１＝｛（（ｍ＋ｒｘ×ｘＡ）／ｋ）×ｋ｝＊Ｇ ＝（ｍ＋ｒｘ×ｘＡ）＊Ｇ ＝ｍ＊Ｇ＋（ｒｘ×ｘＡ）＊Ｇ ＝ｍ＊Ｇ＋ｒｘ＊ＹＡ となることから明らかである。

【００１３】４．楕円曲線上の点の加算、２倍算の演算
による計算量 上記に示した楕円曲線上の離散対数問題を応用したエル
ガマル署名によるデジタル署名方式における公開鍵の生
成、署名生成、署名検証のそれぞれにおいて、楕円曲線
上の点の冪倍の演算の計算が行われる。例えば、式３に
示す「ｘＡ＊Ｇ」、式４に示す「ｋ＊Ｇ」、式６に示す
「ｓ＊Ｒ１」、「ｍ＊Ｇ」、「ｒｘ＊ＹＡ」は、楕円曲
線上の点の冪倍の演算である。なお、楕円曲線の演算公
式については、非特許文献２に詳述されている。

【００１４】楕円曲線の演算公式について、以下に説明
する。楕円曲線の方程式をｙ＾２＝ ｘ＾３ ＋ａ×ｘ
＋ｂ とし、任意の点Ｐの座標を（ｘ１，ｙ１）とし、
任意の点Ｑの座標を（ｘ２，ｙ２）とする。ここで、Ｒ
＝Ｐ＋Ｑで定まる点Ｒの座標を（ｘ３，ｙ３）とする。

【００１５】なお、Ｐ≠Ｑの場合、Ｒ＝Ｐ＋Ｑは、加算
の演算となる。加算の公式を以下に示す。

【００１６】 ｘ３＝｛（ｙ２−ｙ１）／（ｘ２−ｘ１）｝＾２−ｘ１−ｘ２ ｙ３＝｛（ｙ２−ｙ１）／（ｘ２−ｘ１）｝（ｘ１−ｘ３）−ｙ１ Ｐ＝Ｑの場合、Ｒ＝Ｐ＋Ｑ＝Ｐ＋Ｐ＝２×Ｐとなり、Ｒ
＝Ｐ＋Ｑは、２倍算の演算となる。２倍算の公式を以下
に示す。 ｘ３＝｛（３ｘ１＾２＋ａ）／２ｙ１｝＾２−２ｘ１ ｙ３＝｛（３ｘ１＾２＋ａ）／２ｙ１｝（ｘ１−ｘ３）−ｙ１

【００１７】なお、上記演算は、楕円曲線が定義される
有限体上での演算である。上記に示すように、２項組座
標であるアフィン座標、即ち今まで述べてきた座標にお
いて、楕円曲線上の加算演算を行う場合に、楕円曲線上
の加算１回につき、１回の有限体上の逆数計算が必要と
なる。一般に、有限体上の逆数計算は、有限体上での乗
算計算と比較して、１０倍程度の計算量を必要とする。

【００１８】そこで、計算量を削減することを目的とし
て、射影座標と呼ばれる３項組の座標が用いられる。射
影座標とは、３項組Ｘ、Ｙ、Ｚからなる座標のことであ
って、座標（Ｘ，Ｙ，Ｚ）と座標（Ｘ’，Ｙ’，Ｚ’）
とに対して、ある数ｎが存在して、Ｘ’＝ｎＸ、Ｙ’＝
ｎＹ、Ｚ’＝ｎＺなる関係があるならば、（Ｘ，Ｙ，
Ｚ）＝（Ｘ’，Ｙ’，Ｚ’）とするものである。アフィ
ン座標（ｘ，ｙ）と射影座標（Ｘ，Ｙ，Ｚ）とは、 （ｘ，ｙ） → （ｘ，ｙ，１） （Ｘ，Ｙ，Ｚ）→ （Ｘ／Ｙ，Ｙ／Ｚ） （Ｚ≠０の
時）なる関係で、互いに対応している。ここで、記号→
は、次に示す意味で用いている。集合Ｓ１の任意の元
に、集合Ｓ２の一つの元が対応する時、Ｓ１→Ｓ２と表
記する。

【００１９】以下、楕円曲線の演算は、全て、射影座標
で行われるものとする。次に、射影座標上の楕円曲線の
加算公式、２倍公式について説明する。これらの公式
は、もちろん、前に述べたアフィン座標における加算公
式、２倍公式と整合性のあるものである。冪倍の演算
は、楕円曲線上の点の加算、２倍算の演算の繰り返しに
よって実現できる。この冪倍の演算のうち、加算の計算
量は、楕円曲線のパラメータに依存しないが、２倍算の
計算量は、楕円曲線のパラメータに依存する。

【００２０】ここでは、ｐを１６０ビットの素数とし、
有限体ＧＦ（ｐ）上の楕円曲線をＥ：ｙ＾２ ＝ ｘ＾
３ ＋ａｘ＋ｂ とし、楕円曲線Ｅ上の元Ｐ、Ｑをそれ
ぞれ、Ｐ＝（Ｘ１，Ｙ１，Ｚ１）、 Ｑ＝（Ｘ２，Ｙ
２，Ｚ２）で表す時、Ｒ＝（Ｘ３，Ｙ３，Ｚ３）＝Ｐ＋
Ｑを以下のようにして、求める。

【００２１】（ｉ）Ｐ≠Ｑの場合 この場合、加算の演算となる。 （ｓｔｅｐ １−１） 中間値の計算 以下を計算する。 （式８） Ｕ１＝Ｘ１×Ｚ２＾２ （式９） Ｕ２＝Ｘ２×Ｚ１＾２ （式１０） Ｓ１＝Ｙ１×Ｚ２＾３ （式１１） Ｓ２＝Ｙ２×Ｚ１＾３ （式１２） Ｈ＝Ｕ２−Ｕ１ （式１３） ｒ＝Ｓ２−Ｓ１ （ｓｔｅｐ １−２） Ｒ＝（Ｘ３，Ｙ３，Ｚ３）の計
算 以下を計算する。 （式１４） Ｘ３＝−Ｈ＾３−２×Ｕ１×Ｈ＾２＋ｒ＾２ （式１５） Ｙ３＝−Ｓ１×Ｈ＾３＋ｒ×（Ｕ１×Ｈ＾２−Ｘ３） （式１６） Ｚ３＝Ｚ１×Ｚ２×Ｈ

【００２２】（ｉｉ）Ｐ＝Ｑの場合（即ち、Ｒ＝２Ｐ） この場合、２倍算の演算となる。 （ｓｔｅｐ ２−１） 中間値の計算 以下を計算する。 （式１７） Ｓ＝４×Ｘ１×Ｙ１＾２ （式１８） Ｍ＝３×Ｘ１＾２＋ａ×Ｚ１＾４ （式１９） Ｔ＝−２×Ｓ＋Ｍ＾２ （ｓｔｅｐ ２−２） Ｒ＝（Ｘ３，Ｙ３，Ｚ３）の計
算 以下を計算する。 （式２０） Ｘ３＝Ｔ （式２１） Ｙ３＝−８×Ｙ１＾４＋Ｍ×（Ｓ−Ｔ） （式２２） Ｚ３＝２×Ｙ１×Ｚ１

【００２３】次に、楕円曲線の加算、２倍算を行う場合
の計算量について説明する。ここで、有限体ＧＦ（ｐ）
上の１回の乗算による計算量を１Ｍｕｌ、１回の２乗算
による計算量を１Ｓｑで表す。なお、一般のマイクロプ
ロセッサにおいては、１Ｓｑ≒０．８Ｍｕｌである。

【００２４】上記の例によると、Ｐ≠Ｑの場合に示され
ている楕円曲線上の加算の計算量は、式８〜式１６にお
いて、乗算の回数及び２乗算の回数をカウントすること
により得られ、１２Ｍｕｌ＋４Ｓｑである。これは、式
８、９、１０、１１、１４、１５、１６における加算の
計算量は、それぞれ、１Ｍｕｌ＋１Ｓｑ、１Ｍｕｌ＋１
Ｓｑ、２Ｍｕｌ、２Ｍｕｌ、２Ｍｕｌ＋２Ｓｑ、２Ｍｕ
ｌ、２Ｍｕｌであることから明らかである。

【００２５】また、上記の例によると、Ｐ＝Ｑの場合に
示されている楕円曲線上の２倍算の計算量は、式１７〜
式２２において、乗算の回数及び２乗算の回数をカウン
トすることにより得られ、４Ｍｕｌ＋６Ｓｑである。こ
れは、式１７、１８、１９、２１、２２における２倍算
の計算量は、それぞれ、１Ｍｕｌ＋１Ｓｑ、１Ｍｕｌ＋
３Ｓｑ、１Ｓｑ、１Ｍｕｌ＋１Ｓｑ、１Ｍｕｌであるこ
とから明らかである。

【００２６】なお、上記回数のカウントにおいて、例え
ば、式１４のＨ＾３については、Ｈ＾３＝Ｈ＾２×Ｈと
展開できるので、Ｈ＾３の計算量は、１Ｍｕｌ＋１Ｓｑ
とし、式１８のＺ１＾４については、Ｚ１＾４＝（Ｚ１
＾２）＾２と展開できるので、Ｚ１＾４の計算量は、２
Ｓｑとする。

【００２７】また、式１４のＨ＾２については、前述の
Ｈ＾３の計算のプロセスにおいて、Ｈ＾２が算出されて
いるので、Ｈ＾２の計算量は再度カウントしない。ま
た、乗算の回数のカウントの際、ある値に小さい値を乗
じて行われる乗算の回数は、カウントしない。その理由
を以下に説明する。ここで言う小さい値とは、式８〜式
２２において、乗算の対象となる小さい固定値であり、
具体的には、２、３、４、８などの値である。これらの
値は、多くとも４ビットの２進数で表現できる。一方、
その他の変数は、通常、１６０ビットの値を有してい
る。

【００２８】一般に、マイクロプロセッサにおいて、乗
数と被乗数との乗算は、被乗数のシフトと加算の繰り返
しにより行われる。即ち、２進数で表現される乗数の各
ビット毎に、このビットが１であるならば、２進数で表
現される被乗数の最下位ビットが、このビットの存在す
る位置に一致するように、被乗数をシフトして、１つの
ビット列を得る。乗数の全ビットについて、このように
して得られた少なくとも１つのビット列を全て加算す
る。

【００２９】例えば、１６０ビットの乗数と１６０ビッ
トの被乗数との乗算においては、１６０ビットの被乗数
を１６０回シフトし、１６０個のビット列を得、得られ
た１６０個のビット列を加算する。一方、４ビットの乗
数と１６０ビットの被乗数との乗算においては、１６０
ビットの被乗数を４回シフトし、４個のビット列を得、
得られた４個のビット列を加算する。

【００３０】乗算は、上記に示すようにして行われるの
で、乗算がある値に小さい値を乗じて行われる場合に
は、前記繰り返しの回数が少なくなる。従って、その計
算量は少ないと見なせるので、乗算の回数にカウントし
ない。以上説明したように、楕円曲線の２倍算を行う場
合において、式１８には、楕円曲線のパラメータａが含
まれている。このパラメータａの値として、例えば、小
さい値を採用すると、楕円曲線上の２倍算の計算量は、
１Ｍｕｌ分削減でき、３Ｍｕｌ＋６Ｓｑとなる。なお、
加算に関しては、楕円曲線のパラメータを変化させて
も、計算量は変わらない。

【００３１】５．暗号に適した楕円曲線の選択 次に暗号に適した楕円曲線を選択する方法について説明
する。なお、その詳細については、「IEEE P1363 Worki
ng draft」（１９９７年２月６日、ＩＥＥＥ発行）に詳
しく書かれている。暗号に適した楕円曲線は、以下のス
テップを繰り返すことにより得られる。

【００３２】（ｓｔｅｐ １） 任意の楕円曲線の選択 有限体ＧＦ（ｐ）上の任意のパラメータａ、ｂを選ぶ。
ここで、ａ、ｂは、式２３を満たし、ｐは素数である。 （式２３） ４×ａ＾３＋２７×ｂ＾２ ≠０ （ｍｏｄ ｐ） 選択されたａ、ｂを用いて、楕円曲線をＥ：ｙ＾２＝ｘ
＾３＋ａ×ｘ＋ｂとする。

【００３３】（ｓｔｅｐ ２） 暗号に適した楕円曲線
であるかどうかを判定するために、楕円曲線Ｅの元の個
数＃Ｅ（ＧＦ（ｐ））を計算し、 （条件１） ＃Ｅ（ＧＦ（ｐ））が大きな素数で割り切
れ、かつ、 （条件２） ＃Ｅ（ＧＦ（ｐ））−（ｐ＋１）≠０，−
１である場合に、楕円曲線Ｅを採用する。

【００３４】上記に説明したように、楕円曲線のパラメ
ータａとして固定的に小さい値を選択すると、楕円曲線
の冪倍の演算において計算量を削減できるものの、パラ
メータを予め固定的に取ることにより、暗号に適した安
全な楕円曲線を選択しにくいという問題点がある。

【００３５】また逆に、上記に説明した楕円曲線の選択
方法を用いて、暗号に適した安全な楕円曲線を選択する
と、楕円曲線のパラメータａとして小さい値を選択でき
るとは限らず、計算量を削減できないという問題点があ
る。このように、暗号に適した安全な楕円曲線を選択
し、その楕円曲線での演算量を削減するためには、相互
に矛盾し対立する問題点を有する。

【００３６】６．従来の楕円曲線変換装置 上記問題点を解決するために、従来の「楕円曲線変換装
置、楕円曲線変換方法及び楕円曲線利用装置」として、
以下の楕円曲線変換装置が示されている（例えば、特許
第３０５０３１３号公報）。この従来の楕円曲線変換装
置は、入力された任意の楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋
ａｘ＋ｂを、その位数を変えることなく、小さな係数ａ
（ａ＝−３など）を持つ楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋
ａｘ＋ｂに変換する装置である。つまり、安全性を維持
したまま、より計算量を削減することが可能な楕円曲線
を生成する。この装置は、入力の楕円曲線をそれと同型
な楕円曲線に変換している。

【００３７】楕円曲線変換装置１００は、図１２に示す
ように、パラメータ受信部１１０、変換係数取得部１２
０、変換楕円曲線算出部１３０、パラメータ送出部１４
０から構成される。

【００３８】パラメータ受信部１１０は、外部の装置か
ら、楕円曲線のパラメータａ、ｂと、前記楕円曲線上の
元Ｇと、素数ｐとを受信する。ここで、ｐは、１６０ビ
ットの素数である。

【００３９】前記外部の装置には、公開鍵暗号を用いる
暗号装置、復号装置、デジタル署名装置、デジタル署名
検証装置、鍵共有装置などが含まれる。前記外部の装置
は、公開鍵暗号の安全性の根拠として楕円曲線上の離散
対数問題を用いており、前記楕円曲線を有している。こ
こで、有限体ＧＦ（ｐ）上の任意に構成される前記楕円
曲線は、Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂで示され、前記
元Ｇは、前記楕円曲線の任意に構成され、Ｇ＝（ｘ０，
ｙ０）で表される。

【００４０】変換係数取得部１２０は、関数Ｔ（ｉ）を
有する。関数Ｔ（ｉ）は、ｉ＝０、１、２、３、４の
時、それぞれ、−３、１、−１、２、−２の値を有す
る。また、関数Ｔ（ｉ）は、ｉ＝５、６、７、８、９、
１０、１１、…の時、３、４、−４、５、−５、６、−
６、…の値を有する。

【００４１】変換係数取得部１２０は、ｉ＝０から始め
て、ｉの値を１ずつ加算しながら、 （式２４） −２＾３１＋１≦Ｔ（ｉ）≦２＾３１−１ を満たし、かつ、 （式２５） Ｔ（ｉ）＝ｔ＾４×ａ （ｍｏｄ ｐ） となる変換係数ｔであって、有限体ＧＦ（ｐ）上の元で
ある変換係数ｔを算出する。

【００４２】ここで、式２４は、Ｔ（ｉ）が３２ビット
以下になるように取られることを示している。なお、関
数Ｔ（ｉ）は、ｉ＝０の時に、−３の値を有しており、
変換係数取得部１２０は、ｉ＝０から始めて、ｉの値を
１ずつ加算しながら、関数Ｔ（ｉ）の値を参照するの
で、最初に−３の値が参照される。

【００４３】また、関数Ｔ（ｉ）は、ｉ＝０の時に、−
３の値を有していることを除いて、絶対値の小さい値か
ら大きい値へと順に値を有しているので、絶対値の小さ
い値から順に参照することができる。

【００４４】変換楕円曲線算出部１３０は、有限体ＧＦ
（ｐ）上に構成される変換楕円曲線Ｅｔ：ｙ’＾２＝
ｘ’＾３＋ａ’×ｘ’＋ｂ’のパラメータａ’、ｂ’を
それぞれ次のようにして、算出する。 （式２６） ａ’＝ａ×ｔ＾４ （式２７） ｂ’＝ｂ×ｔ＾６

【００４５】また、変換楕円曲線算出部１３０は、元Ｇ
に対応する変換楕円曲線Ｅｔ上の元Ｇｔ＝（ｘｔ０，ｙ
ｔ０）を次のようにして、算出する。 （式２８） ｘｔ０＝ｔ＾２×ｘ０ （式２９） ｙｔ０＝ｔ＾３×ｙ０

【００４６】なお、楕円曲線Ｅ上の任意の点は、以上の
ようにして生成されたパラメータａ’、ｂ’で定まる変
換楕円曲線Ｅｔ上の１点に変換される。

【００４７】パラメータ送出部１４０は、前記算出され
た変換楕円曲線Ｅｔのパラメータａ’、ｂ’と、元Ｇｔ
（ｘｔ０，ｙｔ０）とを前記外部の装置へ送出する。こ
のような従来の楕円曲線変換装置１００の動作は以下の
通りである。

【００４８】パラメータ受信部１１０は、外部の装置か
ら素数ｐと、楕円曲線Ｅのパラメータａ及びｂとを受け
取り（ステップＳ１５１）、前記楕円曲線上の元Ｇを受
け取る（ステップＳ１５２）。次に、変換係数取得部１
２０は、変換係数ｔを算出し（ステップＳ１５３）、変
換楕円曲線算出部１３０は、有限体ＧＦ（ｐ）上に構成
される変換楕円曲線Ｅｔのパラメータａ’、ｂ’と、元
Ｇに対応する変換楕円曲線Ｅｔ上の元Ｇｔ＝（ｘｔ０，
ｙｔ０）を算出し（ステップＳ１５４）、パラメータ送
出部１４０は、前記算出された変換楕円曲線Ｅｔのパラ
メータａ’、ｂ’と、元Ｇｔ（ｘｔ０，ｙｔ０）とを前
記外部の装置へ送出する（ステップＳ１５５）。

【００４９】また、変換係数取得部１２０の詳細な動作
は以下の通りである。変換係数取得部１２０は、ｉに０
の値を設定する（ステップＳ１６１）。次に、変換係数
取得部１２０は、関数Ｔ（ｉ）について、 −２＾３１＋１≦Ｔ（ｉ）≦２＾３１−１ を満たすかどうかを判定し、満たさないならば（ステッ
プＳ１６２）、処理を終了する。満たすならば（ステッ
プＳ１６２）、 Ｔ（ｉ）＝ｔ＾４×ａ （ｍｏｄ ｐ） となる変換係数ｔを算出し（ステップＳ１６３）、算出
された変換係数ｔが有限体ＧＦ（ｐ）上の元であるかど
うかを判定し、有限体ＧＦ（ｐ）上の元であるなら（ス
テップＳ１６４）、処理を終了する。有限体ＧＦ（ｐ）
上の元でないなら（ステップＳ１６４）、ｉに１を加算
し（ステップＳ１６５）、再度ステップＳ１６２へ制御
を戻す。

【００５０】次に、変換楕円曲線算出部１３０は、以下
の動作をする。変換楕円曲線算出部１３０は、有限体Ｇ
Ｆ（ｐ）上に構成される変換楕円曲線Ｅｔのパラメータ
ａ’＝ａ×ｔ＾４を算出し（ステップＳ１７１）、パラ
メータｂ’＝ｂ×ｔ＾６を算出する（ステップＳ１７
２）。また、変換楕円曲線算出部１３０は、元Ｇに対応
する変換楕円曲線Ｅｔ上の元Ｇｔ＝（ｘｔ０，ｙｔ０）
として、ｘｔ０＝ｔ＾２×ｘ０を算出し（ステップＳ１
７３）、ｙｔ０＝ｔ＾３×ｙ０を算出する（ステップＳ
１７４）。

【００５１】この従来の楕円曲線変換装置は、入力した
楕円曲線をそれと同型な楕円曲線に変換している。ステ
ップＳ１６４において、Ｔ（ｉ）＝−３とした時、式２
３のｔがＧＦ（ｐ）の元である場合のみ、ｙ＾２＝ｘ＾
３−３ｘ＋ｂの方程式をもつ楕円曲線に変換できる。

【００５２】しかし、−３＝ａ×ｔ＾４となるために
は、−３／ａのＧＦ（ｐ）における４乗根が存在しなけ
ればならない。任意のｘについて、ｘがＧＦ（ｐ）で２
乗根が存在する確率は１／２であるので、４乗根が存在
する確率は「２乗根の２乗根が存在する確率」であるか
ら、１／２×１／２＝１／４である。従って、上記ｔが
ＧＦ（ｐ）の元である確率は、１／４と低く、ｙ＾２＝
ｘ＾３−３ｘ＋ｂの方程式をもつ楕円曲線に必ずしも変
換できないという問題点がある。

【００５３】７．モンゴメリ型楕円曲線 上記の楕円曲線変換装置は、その方程式がｙ＾２＝ｘ＾
３＋ａ×ｘ＋ｂの形をしている楕円曲線だけを対象とし
ている。このような楕円曲線はワイヤーシュトラス型楕
円曲線と呼ばれる。

【００５４】一方、方程式がＢ×ｙ＾２＝ｘ＾３＋Ａ×
ｘ＾２＋ｘの形をしている楕円曲線をモンゴメリ型楕円
曲線と呼ぶ。この楕円曲線は、点の加算や２倍算が高速
であることが知られており、それぞれの計算量は、４Ｍ
ｕｌ＋２Ｓｑ、３Ｍｕｌ＋２Ｓｑになる。上記５で述べ
たようにワイヤーシュトラス型楕円曲線の点の加算、２
倍算の計算量は、それぞれ、１２Ｍｕｌ＋４Ｓｑ、４Ｍ
ｕｌ＋６Ｓｑである。よって、モンゴメリ型楕円曲線の
方が点の加算、２倍算が高速である（例えば、非特許文
献３）。

【００５５】一方、安全な楕円曲線を生成するための方
法において、位数計算を行い、安全であるかを判定する
ことによって安全な楕円曲線を生成することがある。こ
こでの位数計算で、使用する楕円曲線はワイヤーシュト
ラス型である。ゆえに、この方法で生成できる楕円曲線
もワイヤーシュトラス型に限る。

【００５６】上記従来の楕円曲線変換装置と同様の考え
方で、楕円曲線の同型を利用することにより、ワイヤー
シュトラス型楕円曲線からモンゴメリ型楕円曲線に変換
することが考えられる。しかし、上記従来の楕円曲線変
換装置においてａ＝−３を満たす楕円曲線を捜したのと
同様で、必ずしも変換可能ではない。即ち、モンゴメリ
型楕円曲線に変換できないワイヤーシュトラス型楕円曲
線が存在する。上記のように同型を利用する場合は、文
献「楕円曲線暗号演算の計算法について」（伊豆 哲
也、ＳＣＩＳ’９９、２７５〜２８０ページ）より、ワ
イヤーシュトラス型楕円曲線からモンゴメリ楕円曲線に
変換可能である確率は１９／４８程度であり、必ずしも
モンゴメリ型楕円曲線に変換できないという問題点があ
る。

【００５７】

【特許文献１】特許第３０５０３１３号公報

【００５８】

【非特許文献１】ニイルコブリッツ著“ア コウス イ
ン ナンバア セオリイ アンド クリプトグラヒイ
“（Neal Koblitz,A Course in Number theory and Cry
ptography”，Springer-Verlag，1987）

【００５９】

【非特許文献２】“Efficient elliptic curve exponen
tiation”（Miyaji, Ono, and Cohen著、Advances in c
ryptology-proceedings of ICICS, 97, Lecture notes
in computer science, 1997, Springer-verlag, 282-29
0.)

【００６０】

【非特許文献３】“Speeding the Pollar and Elliptic
Curve Methods of Factorization”（P.L.Montgomery
著，Math. of Comp. 48，1987，pp.243-264)

【００６１】

【発明が解決しようとする課題】以上のように、従来の
楕円曲線変換装置は、入力された任意な楕円曲線を、そ
の安全性を維持したまま、より高速化が可能な楕円曲線
ｙ＾２＝ｘ＾３−３ｘ＋ｂ（ワイヤーシュトラス型楕円
曲線）に変換し得るものの、必ずしも変換可能とは限ら
ないという問題点がある。また、ワイヤーシュトラス型
楕円曲線からモンゴメリ型楕円曲線への変換について
も、必ずしも変換可能とは限らないという問題点があ
る。

【００６２】そこで、本発明では、任意の楕円曲線を、
その安全性を維持したまま、より計算量が削減される楕
円曲線ｙ＾２＝ｘ＾３−３ｘ＋ｂに、極めて高い確率
で、変換することができる楕円曲線変換装置等を提供す
ることを目的とする。

【００６３】さらに、本発明は、任意のワイヤーシュト
ラス型楕円曲線を、その安全性を維持したまま、より計
算量が削減されるモンゴメリ型楕円曲線に、極めて高い
確率で、変換することができる楕円曲線変換装置等を提
供することをも目的とする。

【００６４】

【課題を解決するための手段】上記目的を達成するため
に、本発明に係る楕円曲線変換装置は、有限体Ｆ上の第
１楕円曲線を有限体Ｆ上の第２楕円曲線に変換する楕円
曲線変換装置であって、前記第１楕円曲線と位数が同じ
で、かつ、一定関係を有する楕円曲線群であるＬ1次同
種な楕円曲線群の中から、楕円曲線上での演算の計算量
が削減される高速化条件を満たす楕円曲線を探索する探
索手段と、前記探索手段による探索により、前記高速化
条件を満たす楕円曲線が探索されたか否かを判定する判
定手段と、前記判定手段によって前記高速化条件を満た
す楕円曲線が探索されたと判断された場合に、当該楕円
曲線を前記第２楕円曲線として出力する出力手段とを備
えることを特徴とする。

【００６５】ここで、前記探索手段は、前記判定手段に
よって前記高速化条件を満たす楕円曲線が探索されなか
ったと判断された場合には、前記高速化条件を満たす楕
円曲線の探索を繰り返してもよい。

【００６６】例えば、前記探索手段は、前記判定手段に
よって前記高速化条件を満たす楕円曲線が探索されなか
ったと判断された場合には、前記第１楕円曲線とＬ2次
同種な楕円曲線群の中から、前記高速化条件を満たす楕
円曲線を探索してもよいし、前記探索手段は、前記第１
楕円曲線と位数が同じで、かつ、Ｌ1次同種な楕円曲線
群の中から、楕円曲線上での演算の計算量が削減される
高速化条件を満たす楕円曲線の候補となる暫定的な楕円
曲線を特定し、前記判定手段は、前記探索手段で特定さ
れた暫定的な楕円曲線が前記高速化条件を満たすか否か
を判定し、前記探索手段は、前記判定手段によって前記
暫定的な楕円曲線が前記高速化条件を満たさないと判断
された場合には、前記暫定的な楕円曲線を新たな第１楕
円曲線とし、その第１楕円曲線と位数が同じで、かつ、
一定関係を有する楕円曲線群であるＬ1次同種な楕円曲
線群の中から、楕円曲線上での演算の計算量が削減され
る高速化条件を満たす楕円曲線を探索してもよい。

【００６７】また、前記高速化条件は、前記楕円曲線の
方程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂにおいてａ＝−３を
満たすことであってもよいし、前記高速化条件は、前記
楕円曲線がモンゴメリ型楕円曲線であることであっても
よい。

【００６８】また、本発明に係る楕円曲線利用装置は、
楕円曲線変換装置で得られた楕円曲線を利用する楕円曲
線利用装置であって、前記楕円曲線を特定するパラメー
タを記憶する記憶手段と、有限体Ｆの構造と前記記憶手
段に記憶されているパラメータとで定まる楕円曲線を利
用する暗号、復号、デジタル署名、デジタル署名検証又
は鍵共有を行う利用手段とを備え、前記楕円曲線変換装
置は、有限体Ｆ上の第１楕円曲線を有限体Ｆ上の第２楕
円曲線に変換する楕円曲線変換装置であって、前記第１
楕円曲線と位数が同じで、かつ、一定関係を有する楕円
曲線群であるＬ1次同種な楕円曲線群の中から、楕円曲
線上での演算の計算量が削減される高速化条件を満たす
楕円曲線を探索する探索手段と、前記探索手段による探
索により、前記高速化条件を満たす楕円曲線が探索され
たか否かを判定する判定手段と、前記判定手段によって
前記高速化条件を満たす楕円曲線が探索されたと判断さ
れた場合に、当該楕円曲線を前記第２楕円曲線として出
力する出力手段とを備えることを特徴とする。

【００６９】また、本発明に係る楕円曲線生成装置は、
有限体Ｆ上の楕円曲線を生成する楕円曲線生成装置であ
って、有限体Ｆ上の第１楕円曲線を生成する生成手段
と、生成された前記第１楕円曲線と位数が同じで、か
つ、一定関係を有する楕円曲線群であるＬ1次同種な楕
円曲線群の中から、楕円曲線上での演算の計算量が削減
される高速化条件を満たす楕円曲線を探索する探索手段
と、前記探索手段による探索により、前記高速化条件を
満たす楕円曲線が探索されたか否かを判定する判定手段
と、前記判定手段によって前記高速化条件を満たす楕円
曲線が探索されたと判断された場合に、当該楕円曲線を
前記第２楕円曲線として出力する出力手段とを備えるこ
とを特徴とする。

【００７０】なお、本発明は、上記楕円曲線変換装置、
楕円曲線利用装置及び楕円曲線生成装置として実現する
ことができるだけでなく、それらの装置が備える特徴的
な手段をステップとする楕円曲線変換方法、楕円曲線利
用方法及び楕円曲線生成方法として実現したり、それら
のステップをコンピュータに実行させるプログラムとし
て実現することもできる。そして、そのプログラムは、
ＣＤ−ＲＯＭ等の記録媒体やインターネット等の伝送媒
体を介して広く流通させることができるのは言うまでも
ない。

【００７１】

【発明の実施の形態】（実施の形態１）本発明に係る実
施の形態１における楕円曲線変換装置２００について説
明する。

【００７２】図１は、実施の形態１における楕円曲線変
換装置２００の構成を示す機能ブロック図である。楕円
曲線変換装置２００は、コンピュータ上で実行されるプ
ログラム又はＬＳＩ等の電子回路で実現される装置であ
り、機能的に、楕円曲線生成部２１０と、楕円曲線条件
判定部２２０と、楕円曲線出力部２３０から構成され
る。楕円曲線変換装置２００は、有限体ＧＦ（ｐ）上楕
円曲線ＥＩ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂのパラメータ
ｐ，ａ，ｂと楕円曲線ＥＩの位数ｍＥＩを入力とし、そ
れと同種なＧＦ（ｐ）上の楕円曲線ＥＯ：ｙ＾２＝ｘ＾
３−３×ｘ＋ｂ’のパラメータｂ’を出力する。「同
種」については後述する。ここで、ｘ×ｙはｘとｙの積
を示す。

【００７３】楕円曲線生成部２１０は、入力される任意
の楕円曲線を受け取り、その楕円曲線と同種な楕円曲線
を生成し、楕円曲線条件判定部２２０及び楕円曲線出力
部２３０に出力する。具体的には、楕円曲線生成部２１
０は、有限体ＧＦ（ｐ）上の楕円曲線ＥＩ：ｙ＾２＝ｘ
＾３＋ａ×ｘ＋ｂのパラメータｐ，ａ，ｂと楕円曲線Ｅ
Ｉの位数ｍＥＩを入力とし、それと同種な楕円曲線ＥＩ
2：ｙ＾２＝ｘ＾３＋ａ2×ｘ＋ｂ2を決定し、そのパラ
メータａ2，ｂ2を楕円曲線条件判定部２２０及び楕円曲
線出力部２３０に出力する。

【００７４】楕円曲線条件判定部２２０は、楕円曲線生
成部２１０が出力した楕円曲線が係数ａ2＝−３を満た
すか否かを判定し、満たさない場合は、その旨を楕円曲
線生成部２１０に通知することで、楕円曲線生成部２１
０に、いま出力した楕円曲線を新たな入力楕円曲線とし
て、再び同様の処理（新たな楕円曲線の生成）繰り返さ
せる。一方、満たす場合は、その旨を楕円曲線出力部２
３０に通知する。

【００７５】楕円曲線出力部２３０は、楕円曲線条件判
定部２２０から条件を満たす旨の通知を受け取った場合
に、楕円曲線生成部２１０から出力された楕円曲線を外
部に出力する。具体的には、最終的な楕円曲線ＥＯ：ｙ
＾２＝ｘ＾３−３×ｘ＋ｂ’のパラメータｂ’として、
楕円曲線生成部２１０から受け取った楕円曲線ＥＩ2の
パラメータｂ2を外部に出力する。

【００７６】次に、以上のように構成された本実施の形
態における楕円曲線変換装置２００の動作を説明する。
図２は、楕円曲線変換装置２００の動作を示すフローチ
ャートである。楕円曲線生成部２１０は、入力された任
意の楕円曲線を受け取り（ステップＳ２００）、その楕
円曲線と同種な楕円曲線を生成し（ステップＳ２０
１）、生成した楕円曲線を楕円曲線条件判定部２２０及
び楕円曲線出力部２３０に出力する。楕円曲線条件判定
部２２０は、楕円曲線生成部２１０が出力した楕円曲線
がａ2＝−３を満たすか否かを判定する（ステップＳ２
０２）。

【００７７】判定の結果、ａ2＝−３を満たさない場合
は（ステップＳ２０２でＮｏ）、楕円曲線条件判定部２
２０は、その旨を楕円曲線生成部２１０に通知し、その
通知を受けた楕円曲線生成部２１０は、いま生成した楕
円曲線を入力の楕円曲線として、再び、同種な他の楕円
曲線の生成を繰り返す（ステップＳ２０１〜Ｓ２０
２）。

【００７８】一方、判定の結果、ａ2＝−３を満たす場
合は（ステップＳ２０２でＹｅｓ）、楕円曲線条件判定
部２２０は、その旨を楕円曲線出力部２３０に通知し、
その通知を受けた楕円曲線出力部２３０は、楕円曲線生
成部２１０から出力された楕円曲線ＥＩ2のパラメータ
ｂ2をｂ’として外部に出力する（ステップＳ２０
３）。

【００７９】図３〜図４は、図２における楕円曲線生成
部２１０の処理（ステップＳ２０１）の詳細な手順を示
すフローチャートである。楕円曲線生成部２１０は、以
下の手順により、入力された楕円曲線ＥＩ：ｙ＾２＝ｘ
＾３＋ａ×ｘ＋ｂから、それと同種な楕円曲線ＥＩ2：
ｙ＾２＝ｘ＾３＋ａ2×ｘ＋ｂ2を生成する。

【００８０】ステップＳ３０１：以下の式より、楕円曲
線ＥＩのｊ不変数ｊＥＩを求める。 ｊＥＩ＝１７２８×（４×ａ＾３＋２７×ｂ＾２）／
（４×ａ＾３） ステップＳ３０２：素数Ｌに初期値（２）をセットす
る。 ステップＳ３０３：素数Ｌに対応するモジュラー多項式
ΦＬ（Ｘ、Ｙ）を読み出す。

【００８１】ステップＳ３０４：ΦＬ（Ｘ、Ｙ）＝０を
Ｙを未定変数として、有限体ＧＦ（ｐ）上で解く。 ステップＳ３０５（Ｓ３０５ａ、Ｓ３０５ｂ）：解が２
個以上ない場合は、素数Ｌに、次に大きな素数をセット
し、ステップＳ３０３へ。なお、素数Ｌについては、予
め記憶している素数の系列（２，３，５，７，・・・）
から小さい順に取り出した値をセットする。

【００８２】ステップＳ３０６：上記解の中から一つ選
び、Ｓとする。 ステップＳ３０７：ΦＬ（Ｘ、Ｓ）＝０をＸを未定変数
として、有限体ＧＦ（ｐ）上で解く。 ステップＳ３０８：上記解の中でｊＥＩと等しい解以外
の解を取り、ｊＥＩ2とする。

【００８３】ステップＳ３０９：（１−１７２８／ｊＥ
Ｉ2）が法ｐで平方剰余であるか否かを判定する。平方
剰余である場合ステップＳ３１０へ。それ以外は、ステ
ップＳ３１２へ。 ステップＳ３１０：（１−１７２８／ｊＥＩ2）のＧＦ
（ｐ）における平方根を求め、Ｒとする。 ステップＳ３１１：ａ2＝−３，ｂ2＝２×Ｒとする。ス
テップＳ３１３へ。

【００８４】ステップＳ３１２：以下の式より、ａ2及
びｂ2を求める。 ａ2＝３×ｊＥＩ2／（１７２８−ｊＥＩ2） ｂ2＝２×ｊＥＩ2／（１７２８−ｊＥＩ2） ステップＳ３１３：楕円曲線ｙ＾２＝ｘ＾３＋ａ2×ｘ
＋ｂ2上のＧＦ（ｐ）を座標としてもつ点を探索し、Ｐ
ＥＩ2とする。

【００８５】ステップＳ３１４（Ｓ３１４ａ、Ｓ３１４
ｂ）：ｍＥＩ＊ＰＥＩ2＝Ｏを満たすか否か判定する。
但し、ＯはＥＩ2の零元であり、ｍＥＩ＊ＰＥＩ2はＰＥ
Ｉ2のｍＥＩ倍の点である。満たす場合は、ａ2，ｂ2を
出力し終了。それ以外はステップＳ３１５へ。

【００８６】ステップＳ３１５（Ｓ３１５ａ、Ｓ３１５
ｂ）：法ｐで平方非剰余の元を選びｃとする。以下の式
より楕円曲線ｙ＾２＝ｘ＾３＋ａ2×ｘ＋ｂ2のｔｗｉｓ
ｔ：ｙ＾２＝ｘ＾３＋ａ2’×ｘ＋ｂ2’を求める。ｔｗ
ｉｓｔについては後述する。 ａ2’＝ｃ＾２×ａ2 ｂ2’＝ｃ＾３×ｂ2 ステップＳ３１６：ａ2’とｂ2’を、ａ2，ｂ2として出
力し終了。

【００８７】なお、楕円曲線生成部２１０は、楕円曲線
条件判定部２２０からａ2≠３の通知を受けた場合に
は、直前に生成した楕円曲線ＥＩ2を新たに入力された
楕円曲線ＥＩとして（ステップＳ３２０）、再び、同様
の処理（ステップＳ３０１〜Ｓ３１６）を繰り返す。

【００８８】ここで、本楕円曲線変換装置２００の楕円
曲線生成部２１０及び楕円曲線条件判定部２２０での処
理の意義について、基盤となる数学用語とともに、説明
する。なお、以下の用語については、文献「The Arithm
etic of Elliptic Curves」（J.H.Silverman著、ＧＴＭ
１０６、Springer-verlag、１９８６年）で詳述されて
いる。

【００８９】（楕円曲線の位数）有限体Ｆ上の楕円曲線
Ｅ上の点を（Ｘ、Ｙ）とする時、Ｘ、Ｙの両方の座標が
Ｆに属する時、その点をＦ有理点という。Ｆ有理点全体
に楕円曲線の群の零元Ｏを加えた集合をＥ（Ｆ）と書
く。Ｅ（Ｆ）は楕円曲線の加算について群をなすことが
知られている。Ｅ（Ｆ）の元の個数を楕円曲線の位数と
呼ぶ。現在の楕円曲線暗号の安全性は、使用する楕円曲
線の位数に依存している。即ち、有限体Ｆが同じ、かつ
楕円曲線の位数が同じである楕円曲線同士は安全性が等
しい。

【００９０】（楕円曲線の同型）有限体Ｆ上の楕円曲線
Ｅの群Ｅ（Ｆ）と楕円曲線Ｅ’の群Ｅ’（Ｆ）が群準同
型であり、１対１対応する場合、楕円曲線ＥとＥ’は
「同型」であるという。Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋
ｂに対し、有限体Ｆの元ｃによって与えられる楕円曲線
Ｅ’：ｙ＾２＝ｘ＾３＋ｃ＾４×ａ×ｘ＋ｃ＾６×ｂ
は、（ｘ，ｙ）→（ｃｘ，ｃｙ）によって同型であるこ
とがいえる。

【００９１】（楕円曲線の同種）有限体Ｆ上の楕円曲線
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂに対し、楕円曲線の位
数がＥと同じである楕円曲線Ｅ’’をＥと同種な楕円曲
線と呼ぶ。また、楕円曲線ＥとＥ’’が位数が等しい場
合、楕円曲線ＥとＥ’’は同種であるという。同種につ
いては、上記文献でも触れられているが、特に、文献
「Isogeny cycles and the Schoof-Elkies-Atkin algor
ithm」（J.-M.Couveignes，L.Dewaghe and F.Morain
著，Research Report LIX/RR/96/03，Ecole Polytechni
que-LIX，1996）で詳述されている。

【００９２】（同種写像とモジュラー多項式）同種同士
の楕円曲線の間には、同種写像が存在する。同種写像
φ：Ｅ→Ｅ’’において、Ｅ’’の零元Ｏ’’に上記写
像によって移るＥ上の点の個数をＬとする時、φはＬ次
同種写像とよび、楕円曲線ＥとＥ’’はＬ次同種である
という。楕円曲線ＥとＬ次同種な楕円曲線を求めるため
にモジュラー多項式が使用できる。モジュラー多項式は
Ｌのみに依存する２変数多項式である。楕円曲線変換装
置２００内の楕円曲線生成部２１０によるステップＳ３
０４からＳ３０８では、モジュラー多項式を用いて楕円
曲線ＥＩとＬ次同種な楕円曲線を求めている。モジュラ
ー多項式及びモジュラー多項式の求め方については、特
に、文献「Calcul du nombre de points sur une courb
e elliptique dans un corps fini: aspectsalgorithmi
ques」（F.Morain著，J. Theor. Nombres Bordeaux 7，
1995，255-282)、文献「Counting points on elliptic
curves over finite fields」（R.Schoof著，J. Theor.
Nombres Bordeaux 7，1995，219-254)で詳述されてい
る。

【００９３】（楕円曲線のｊ不変数）楕円曲線のパラメ
ータとしてｊ不変数がある。楕円曲線Ｅ：ｙ＾２＝ｘ＾
３＋ａ×ｘ＋ｂのｊ不変数は以下の式で与えられる。

【００９４】ｊ＝１７２８×４×ａ＾３／（４×ａ＾３
＋２７×ｂ＾２） 楕円曲線Ｅと、それと同型な楕円曲線Ｅ’のｊ不変数は
等しい。

【００９５】（楕円曲線のｔｗｉｓｔ）上記と逆に楕円
曲線ＥとＥ’のｊ不変数が等しい時は、ＥとＥ’が同型
であるか、または、Ｅ’がＥのｔｗｉｓｔであるかのど
ちらかである。楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋
ｂに対し、有限体Ｆの元ｃによって与えられる楕円曲線
Ｅｔ：ｙ＾２＝ｘ＾３＋ａ×ｃ＾２×ｘ＋ｂ×ｃ＾３を
Ｅのｔｗｉｓｔと呼ぶ。上記で述べたように、ＥとＥｔ
のｊ不変数は等しい。ＥとＥのｔｗｉｓｔは、一般に位
数は異なる。

【００９６】楕円曲線生成部２１０によるステップＳ３
０４からＳ３０８ではＬ次同種な楕円曲線ＥＩ2を求め
ているが、ｊ不変数から楕円曲線を求めているため、求
めたいＬ次同種な楕円曲線ＥＩ2のｔｗｉｓｔを求めて
いる可能性がある。ステップＳ３１４では、求めたいＬ
次同種な楕円曲線が得られているかを判定するため、入
力の楕円曲線ＥＩと位数が等しいかをチェックしてい
る。そこで、等しいと判定されない場合に、ｙ＾２＝ｘ
＾３＋ａ2×ｘ＋ｂ2のｔｗｉｓｔを計算している。

【００９７】以上の説明から分かるように、楕円曲線暗
号の安全性は位数に依存する。そして、本楕円曲線変換
装置２００は、入力された楕円曲線を同種な楕円曲線、
即ち、位数が等しい楕円曲線に変換しているため、安全
性を保持した変換を行っていると言える。

【００９８】また、上記特許第３０５０３１３号に係る
従来の楕円曲線変換装置は、入力された楕円曲線に対し
て、ａ＝−３を満たす楕円曲線に１／４の確率でしか変
換できなかったが、本実施の形態１の楕円曲線変換装置
２００は、同種の楕円曲線、つまり、位数が等しい極め
て数多くの楕円曲線を対象として探索しているので、位
数が等しい楕円曲線の中にａ＝−３のものがあれば必ず
変換可能になる。

【００９９】以上より、実施の形態１における楕円曲線
変換装置によって、任意の楕円曲線を、その安全性を維
持したまま、より計算量が削減される、ａ＝−３の楕円
曲線に極めて高い確率で変換可能になる。 （実施の形態２）本発明に係る実施の形態２における楕
円曲線変換装置４００について説明する。

【０１００】図５は、実施の形態２における楕円曲線変
換装置４００の構成を示す機能ブロック図である。楕円
曲線変換装置４００は、コンピュータ上で実行されるプ
ログラム又はＬＳＩ等の電子回路で実現される装置であ
り、機能的に、楕円曲線生成部４１０と、楕円曲線条件
判定部４２０と、楕円曲線出力部４３０から構成され
る。楕円曲線変換装置４００は、有限体ＧＦ（ｐ）上の
ワイヤーシュトラス型楕円曲線ＥＩ：ｙ＾２＝ｘ＾３＋
ａ×ｘ＋ｂのパラメータｐ，ａ，ｂとその楕円曲線ＥＩ
の位数ｍＥＩを入力とし、それと同種なＧＦ（ｐ）上の
モンゴメリ型楕円曲線ＥＯ：Ｂ’×ｙ＾２＝ｘ＾３＋
Ａ’×ｘ＾２＋ｘのパラメータＡ’，Ｂ’を出力する。

【０１０１】楕円曲線生成部４１０は、入力される任意
のワイヤーシュトラス型楕円曲線を受け取り、その楕円
曲線と同種なモンゴメリ型楕円曲線を探索し、あれば、
その楕円曲線を生成し、楕円曲線条件判定部４２０及び
楕円曲線出力部４３０に出力する。具体的には、楕円曲
線生成部４１０は、入力される任意のワイヤーシュトラ
ス型楕円曲線ＥＩ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂのパラ
メータｐ，ａ，ｂと楕円曲線ＥＩの位数ｍＥＩを入力と
し、それと同種なモンゴメリ型楕円曲線ＥＩ2：Ｂ2×ｙ
＾２＝ｘ＾３＋Ａ2×ｘ＾２＋ｘを探索し、見つかった
場合に、その楕円曲線のＡ2、Ｂ2を出力し、見つからな
ければＦａｌｓｅを出力する。

【０１０２】楕円曲線条件判定部４２０は、楕円曲線生
成部４１０からの出力値が楕円曲線のパラメータである
かＦａｌｓｅであるかを判定し、Ｆａｌｓｅの場合に
は、その旨を楕円曲線生成部４１０に通知することで、
楕円曲線生成部４１０に、他の同種なモンゴメリ型楕円
曲線を再び生成させる。一方、Ｆａｌｓｅでない場合
は、その旨を楕円曲線出力部４３０に通知する。

【０１０３】楕円曲線出力部４３０は、楕円曲線条件判
定部４２０から楕円曲線生成部４１０の出力値がＦａｌ
ｓｅでない旨の通知を受け取った場合に、楕円曲線生成
部４１０から出力された楕円曲線ＥＩ2：Ｂ2×ｙ＾２＝
ｘ＾３＋Ａ2×ｘ＾２＋ｘのパラメータＡ2、Ｂ2を
Ａ’、Ｂ’として外部に出力する。

【０１０４】次に、以上のように構成された本実施の形
態における楕円曲線変換装置４００の動作を説明する。
図６は、楕円曲線変換装置４００の動作を示すフローチ
ャートである。まず、楕円曲線生成部４１０は、入力さ
れたワイヤーシュトラス型楕円曲線を受け取り（ステッ
プＳ４００）、その楕円曲線と同種なモンゴメリ型楕円
曲線を探索し（ステップＳ４０１）、見つかった場合に
はその楕円曲線（パラメータＡ2，Ｂ2）を、見つからな
かった場合にはその旨（Ｆａｌｓｅ）を楕円曲線条件判
定部４２０及び楕円曲線出力部４３０に出力する。楕円
曲線条件判定部４２０は、楕円曲線生成部４１０でモン
ゴメリ型楕円曲線が探索されたか否か、つまり、楕円曲
線生成部４１０の出力がＦａｌｓｅであるか否かを判定
し（Ｓ４０２）、探索されなかった場合、つまり、Ｆａ
ｌｓｅである場合は（ステップＳ４０２でＮｏ）、その
旨を楕円曲線生成部４１０に通知する。

【０１０５】その通知を受けた楕円曲線生成部４１０
は、入力されたワーヤーシュトラス型楕円曲線と同種な
他のモンゴメリ型楕円曲線の探索を繰り返す（Ｓ４０１
〜Ｓ４０２）。このとき、楕円曲線生成部４１０は、こ
れまでとは異なる次数の同種写像（Ｌ次同種写像）を用
いて、入力されたワイヤーシュトラス型楕円曲線から他
の同種なモンゴメリ型楕円曲線の生成を試みる。

【０１０６】一方、楕円曲線変換装置４００での探索に
成功した場合には（ステップＳ４０２でＹｅｓ）、楕円
曲線条件判定部４２０は、その旨を楕円曲線出力部４３
０に通知する。そして、その通知を受けた楕円曲線出力
部４３０は、楕円曲線生成部４１０から出力されている
モンゴメリ型楕円曲線ＥＩ2のパラメータＡ2、Ｂ2を
Ａ’、Ｂ’として出力する（ステップＳ４０３）。

【０１０７】図７〜図８は、図６における楕円曲線生成
部４１０の処理（ステップＳ４０１）の詳細な手順を示
すフローチャートである。楕円曲線生成部４１０は、以
下の手順により、入力された楕円曲線ＥＩ：ｙ＾２＝ｘ
＾３＋ａ×ｘ＋ｂのパラメータａ，ｂとその楕円曲線Ｅ
Ｉの位数ｍＥＩから、それと同種なモンゴメリ型楕円曲
線ＥＩ2：Ｂ2×ｙ＾２＝ｘ＾３＋Ａ2×ｘ＾２＋ｘを探
索し、探索できた場合には、その係数Ａ2、Ｂ2を出力
し、なければＦａｌｓｅを出力する。

【０１０８】ステップＳ５０１：以下の式より、楕円曲
線ＥＩのｊ不変数ｊＥＩを求める。ｊＥＩ＝１７２８×
（４×ａ＾３＋２７×ｂ＾２）／（４×ａ＾３） ステップＳ５０２：素数Ｌに初期値（２）をセットす
る。 ステップＳ５０３：素数Ｌに対応するモジュラー多項式
ΦＬ（Ｘ、Ｙ）を読み出す。

【０１０９】ステップＳ５０４：ΦＬ（Ｘ、Ｙ）＝０を
Ｙを未定変数として、有限体ＧＦ（ｐ）上で解く。 ステップＳ５０５（Ｓ５０５ａ、Ｓ５０５ｂ）：解が２
個以上ない場合は、素数Ｌに、次に大きな素数をセット
し、ステップＳ５０３へ。なお、素数Ｌについては、予
め記憶している素数の系列（２，３，５，７，・・・）
から小さい順に取り出した値をセットする。

【０１１０】ステップＳ５０６：上記解の中から一つ選
び、Ｓとする。 ステップＳ５０７：ΦＬ（Ｘ、Ｓ）＝０をＸを未定変数
として、有限体ＧＦ（ｐ）上で解く。 ステップＳ５０８：上記解の中でｊＥＩと等しい解以外
の解を取り、ｊＥＩ2とする。

【０１１１】ステップＳ５０９：以下の式を有限体ＧＦ
（ｐ）上で解く。 Ｘ＾６−９×Ｘ＾４＋２７×（１―ｊＥＩ2／１７２
８）＋２７×（４×ｊＥＩ2／１７２８−１）＝０ ステップＳ５１０（Ｓ５１０ａ、Ｓ５１０ｂ）：上記式
の解がある場合は、解の一つをＡ2としてステップＳ５
１１へ。それ以外は、ステップ５１２へ。

【０１１２】ステップＳ５１１：Ｂ2＝１とする。ステ
ップＳ５１３へ。 ステップＳ５１２：Ｆａｌｓｅを出力し終了。 ステップＳ５１３：楕円曲線ｙ＾２＝ｘ＾３＋Ａ2×ｘ
＾２＋ｘ上のＧＦ（ｐ）を座標としてもつ点を探索し、
ＰＥＩ2とする。 ステップＳ５１４（Ｓ５１４ａ、Ｓ５１４ｂ）：ｍＥＩ
＊ＰＥＩ2＝Ｏを満たすか否か判定する。但し、ＯはＥ
Ｉ2の零元である。満たす場合は、Ａ2，Ｂ2を出力し終
了。それ以外はステップＳ５１５へ。

【０１１３】ステップＳ５１５（Ｓ５１５ａ、Ｓ５１５
ｂ）：法ｐで平方非剰余の元を選びｃとする。以下の式
より楕円曲線ｙ＾２＝ｘ＾３＋Ａ2×ｘ＾２＋ｘのｔｗ
ｉｓｔ：Ｂ2’×ｙ＾２＝ｘ＾３＋Ａ2’×ｘ＾２＋ｘを
求める。 Ａ2’＝Ａ2 Ｂ2’＝ｃ＾３ ステップＳ５１６：Ａ2’とＢ2’を、Ａ2，Ｂ2として出
力し終了。

【０１１４】なお、楕円曲線生成部４１０は、楕円曲線
条件判定部４２０から楕円曲線生成部４１０の出力がＦ
ａｌｓｅである旨の通知を受けた場合には、直前の素数
Ｌの次に大きな素数を素数Ｌにセットした後に（ステッ
プＳ５０５ｂ）、上記ステップＳ５０３からの処理を繰
り返す。

【０１１５】このように、楕円曲線変換装置４００は、
入力された楕円曲線を同種な楕円曲線、即ち、位数が等
しい楕円曲線に変換しているため、楕円曲線変換装置４
００は安全性を保持した変換を行っていると言える。

【０１１６】ここで、上記特許第３０５０３１３号に係
る従来の楕円曲線変換装置と同じ考えに基づき、入力さ
れたワイヤーシュトラス型楕円曲線を同型のモンゴメリ
型楕円曲線に変換した場合の変換方法と本実施の形態に
おける変換方法とを比較する。従来の楕円曲線変換装置
は、入力された楕円曲線をモンゴメリ型楕円曲線に１９
／４８の確率でしか変換できない。一方、本実施の形態
の楕円曲線変換装置４００は、同種、即ち、位数が等し
い楕円曲線に変換するため、位数が等しい楕円曲線の中
にモンゴメリ型楕円曲線があれば必ず変換可能になる。

【０１１７】よって、本実施の形態における楕円曲線変
換装置によって、任意のワイヤーシュトラス型楕円曲線
を、その安全性を維持したまま、より計算量が削減され
る、モンゴメリ型楕円曲線に極めて高い確率で変換可能
になる。

【０１１８】次に、上記実施の形態１及び実施の形態２
に共通する本発明の基本的なアルゴリズムを上記特許第
３０５０３１３号に係る従来の楕円曲線変換装置と対比
して説明する。図９（ａ）は、上記従来の楕円曲線変換
装置による楕円曲線の探索手法を示す図であり、図９
（ｂ）は、実施の形態１における楕円曲線変換装置２０
０による楕円曲線の探索手法を示す図であり、図９
（ｃ）は、実施の形態２における楕円曲線変換装置４０
０による楕円曲線の探索手法を示す図である。なお、こ
れらの図において、外側に位置する大きな枠５００は、
楕円曲線変換装置に入力された楕円曲線と同種の楕円曲
線の集合を示し、黒丸５０１は、楕円曲線変換装置に入
力された楕円曲線、枠５０２は、その楕円曲線５０１と
同型の楕円曲線の集合を示し、枠５１０〜５１２及び５
２０〜５２２は、入力された楕円曲線５０１と図示され
ているようなＬ次同種の関係にある楕円曲線の集合を示
す。

【０１１９】図９（ａ）に示されるように、従来の楕円
曲線変換装置は、入力された楕円曲線５０１と同型な楕
円曲線群５０２の中から、一定条件（ａ2＝−３）を満
たす楕円曲線を探索している。一方、本発明に係る実施
の形態１における楕円曲線変換装置２００は、図９
（ｂ）に示されるように、入力された楕円曲線５０１と
Ｌ1次同種な楕円曲線群５１０の中から、ａ2＝−３とい
う高速化条件を満たす楕円曲線を探索し、見つからなか
った場合に、そのＬ1次同種な楕円曲線５１０とさらに
Ｌ1次同種な楕円曲線群５１１（つまり、楕円曲線５０
１とＬ1＾２次同種な楕円曲線の中から探索する、とい
う探索を同種な楕円曲線の範囲で繰り返している。

【０１２０】よって、実施の形態１の楕円曲線変換装置
２００は、同型という狭い範囲に属する楕円曲線群を対
象として目的の楕円曲線を探索する従来の楕円曲線変換
装置と異なり、同種というより広い範囲に属する楕円曲
線群を対象として目的の楕円曲線を探索しているので、
同種の楕円曲線群の中に目的の楕円曲線が存在する限
り、１００％の確率で、目的の楕円曲線を探索し、生成
することができる。

【０１２１】なお、入力された楕円曲線５０１に対して
Ｌ1次同種な写像を施して得られた楕円曲線５１０に対
して、再び、Ｌ1次同種な写像を施して得られる楕円曲
線５１１は、元の楕円曲線５０１に対してＬ1＾２次同
種な写像を施すことに等しい。

【０１２２】また、図９（ｃ）に示されるように、本発
明の実施の形態２における楕円曲線変換装置４００は、
入力された楕円曲線５０１とＬ1次同種な楕円曲線群５
２０の中から、モンゴメリ型楕円曲線という高速化条件
を満たす楕円曲線を探索し、見つからなかった場合に
は、今度は、入力された楕円曲線５０１をＬ2次同種な
楕円曲線群５２１の中から探索する、という探索を同種
な楕円曲線群５００の範囲で繰り返している。

【０１２３】よって、実施の形態２の楕円曲線変換装置
４００は、同型という狭い範囲に属する楕円曲線群を対
象として目的の楕円曲線を探索する従来の楕円曲線変換
装置と異なり、同種というより広い範囲に属する楕円曲
線群を対象として目的の楕円曲線を探索しているので、
同種の楕円曲線群の中に目的の楕円曲線が存在する限
り、１００％の確率で、目的の楕円曲線を探索し、生成
することができる。

【０１２４】以上、本発明に係る楕円曲線変換装置につ
いて、２つの実施の形態に基づいて説明したが、本発明
はこれらの実施の形態に限られないことは勿論である。

【０１２５】例えば、実施の形態２では、図９（ｃ）に
示される同種写像が用いられたが、図９（ｂ）に示され
る同種写像を用いてよい。つまり、一旦生成された楕円
曲線を新たな入力楕円曲線として探索を繰り返すのでは
なく、最初に入力された楕円曲線に対して、異なる同種
写像を繰り返すことによって探索を行ってもよい。

【０１２６】また、楕円曲線生成部２１０及び楕円曲線
生成部４１０によるステップＳ３０５、Ｓ５０５での判
定条件として、「解が２個である」としてもよい。さら
に、この時、ステップＳ３０２、Ｓ５０２では、それぞ
れ、ステップＳ３０５ａ、Ｓ５０５ａで「解が２個であ
る」と判定された後は、その時のＬの値に設定すること
としてもよい。つまり、ステップＳ３０５ａ、Ｓ５０５
ａで「解が２個以上である」と判定された場合には、入
力された楕円曲線に対してその時のＬによる同種（Ｌ次
同種）の写像を繰り返すことができる（写像後の楕円曲
線が必ず存在する）ことが保証されているので、図９
（ｂ）に示されるような同一次数（Ｌ）のＬ次写像の繰
り返しが可能になる。

【０１２７】また、本発明は、上記に説明した楕円曲線
変換装置で得られた楕円曲線を利用する楕円曲線利用装
置として実現することもできる。楕円曲線利用装置の具
体的な例は、暗号化装置及び復号化装置からなる暗号通
信システム、デジタル署名装置及び署名検証装置からな
るデジタル署名システム、２つの装置が相互に相手の正
当性を認証し合うことによって秘密鍵の共有化を図る鍵
共有システム等である。

【０１２８】例えば、図１０に示される本発明の適用例
のように、本発明に係る楕円曲線変換装置を備える管理
センタＣが、暗号通信システムで使用される楕円曲線
（例えば、ａ2＝−３の楕円曲線）を生成し、ユーザＡ
１〜Ａｎに提供したり、デジタル署名システムで使用さ
れる楕円曲線（例えば、モンゴメリ型楕円曲線）を生成
し、ユーザＢ１〜Ｂｎに提供したりする。

【０１２９】そして、安全性確保のために、例えば、一
定期間を経過したときに、管理センタＣが、本発明に係
る楕円曲線変換装置を用いて新たな楕円曲線を生成し、
ユーザＡ１〜Ａｎ及びユーザＢ１〜Ｂｎに提供し、暗号
通信システム及びデジタル署名システムで使用される楕
円曲線を更新してもよい。また、ユーザＡ１〜Ａｎの装
置が管理センタＣの楕円曲線変換装置に対して、それま
で使用していた楕円曲線のパラメータ（ｐ，ａ，ｂ，ｍ
ＥＩ）を通知し、そのパラメータを入力として管理セン
タＣの楕円曲線変換装置が新たな楕円曲線を生成し、ユ
ーザＡ１〜Ａｎに返信してもよい。そして、ユーザＡ１
〜Ａｎの装置は、管理センタＣの楕円曲線変換装置から
返信されてきた新たな楕円曲線を用いて暗号通信を行う
ことにする。これによって、暗号の基盤となる楕円曲線
が動的に変更される安全性の高い暗号システムが実現さ
れる。

【０１３０】また、本発明は、上記に説明した楕円曲線
変換装置を備える安全な楕円曲線のパラメータを生成す
る楕円曲線生成装置であってもよい。例えば、上記実施
の形態における楕円曲線変換装置への入力パラメータの
セットを一定手順で生成したり、複数の入力パラメータ
のセットを予め保持しておき、順次、楕円曲線変換装置
に出力する入力パラメータ生成部を設けることで、その
入力パラメータ生成部と楕円曲線変換装置とからなる楕
円曲線生成装置を実現することができる。

【０１３１】また、上記実施の形態における楕円曲線変
換装置は、楕円曲線の条件として、ａ＝−３を満たす、
あるいは、モンゴメリ型楕円曲線である、としている
が、これら条件を満たす可能性のある条件、つまり、楕
円曲線上での演算の計算量が削減されるという高速化条
件であれば、どのようなものであってもよい。

【０１３２】また、上記実施の形態における楕円曲線変
換装置では、楕円曲線条件判定部によって一定の楕円曲
線の条件が満たされないと判断された場合には、楕円曲
線生成部による処理が繰り返されたが、このような繰り
返し処理を行わず、何も出力しないようにしてもよい。
また、一定回数を限度に繰り返すこととしてもよい。こ
れによって、一定の時間制約の下での楕円曲線変換が可
能となる。

【０１３３】また、本発明は、本実施の形態における楕
円曲線変換装置が備える特徴的な構成要素をステップと
する楕円曲線変換方法として実現することもできる。

【０１３４】

【発明の効果】以上に説明したように、本発明により、
入力されたワイヤーシュトラス型楕円曲線に対して、そ
の楕円曲線と同種な楕円曲線の中にａ＝−３を満たす楕
円曲線、あるいは、モンゴメリ型楕円曲線が存在する限
り、そのような楕円曲線に変換することができる。した
がって、安全性を損なうことなく、より計算量が削減さ
れる楕円曲線を生成することが容易となり、楕円曲線を
用いる暗号通信システム、電子署名システム、あるい
は、鍵共有化システムに、特に、複数の楕円曲線を採用
するシステムや楕円曲線を動的に変更するようなシステ
ムに好適であり、高い安全性が要求される電子決済や秘
密通信、デジタル著作物保護等の基盤技術として、その
実用的価値は極めて大きい。

【図面の簡単な説明】

【図１】本発明の実施の形態１における楕円曲線変換装
置の構成を示す機能ブロック図である。

【図２】同楕円曲線変換装置の動作を示すフローチャー
トである。

【図３】図２における楕円曲線生成部の処理（ステップ
Ｓ２０１）の詳細な手順を示すフローチャートの前半部
である。

【図４】図２における楕円曲線生成部の処理（ステップ
Ｓ２０１）の詳細な手順を示すフローチャートの後半部
である。

【図５】本発明の実施の形態２における楕円曲線変換装
置の構成を示す機能ブロック図である。

【図６】同楕円曲線変換装置の動作を示すフローチャー
トである。

【図７】図６における楕円曲線生成部の処理（ステップ
Ｓ４０１）の詳細な手順を示すフローチャートの前半部
である。

【図８】図６における楕円曲線生成部の処理（ステップ
Ｓ４０１）の詳細な手順を示すフローチャートの後半部
である。

【図９】（ａ）は、従来の楕円曲線変換装置による楕円
曲線の探索手法を示す図であり、（ｂ）は、本発明に係
る楕円曲線変換装置による楕円曲線の探索手法を示す図
である。

【図１０】本発明に係る楕円曲線変換装置の適用例を示
す通信システムのシーケンス図である。

【図１１】エルガマル署名によるデジタル署名方式の手
順を示すシーケンス図である。

【図１２】従来の楕円曲線変換装置のブロック図であ
る。

【符号の説明】

２００ 楕円曲線変換装置 ２１０ 楕円曲線生成部 ２２０ 楕円曲線条件判定部 ２３０ 楕円曲線出力部 ４００ 楕円曲線変換装置 ４１０ 楕円曲線生成部 ４２０ 楕円曲線条件判定部 ４３０ 楕円曲線出力部

Claims (23)

【特許請求の範囲】
1. 【請求項１】 有限体Ｆ上の第１楕円曲線を有限体Ｆ上
   の第２楕円曲線に変換する楕円曲線変換装置であって、 前記第１楕円曲線と位数が同じで、かつ、一定関係を有
   する楕円曲線群であるＬ1次同種な楕円曲線群の中か
   ら、楕円曲線上での演算の計算量が削減される高速化条
   件を満たす楕円曲線を探索する探索手段と、 前記探索手段による探索により、前記高速化条件を満た
   す楕円曲線が探索されたか否かを判定する判定手段と、 前記判定手段によって前記高速化条件を満たす楕円曲線
   が探索されたと判断された場合に、当該楕円曲線を前記
   第２楕円曲線として出力する出力手段とを備えることを
   特徴とする楕円曲線変換装置。
2. 【請求項２】 前記探索手段は、前記第１楕円曲線のｊ
   不変数と素数Ｌに対応するモジュラー多項式とから前記
   Ｌ1次同種な楕円曲線群を特定することを特徴とする請
   求項１記載の楕円曲線変換装置。
3. 【請求項３】 前記探索手段は、 前記第１楕円曲線のｊ不変数を算出するｊ不変数算出部
   と、 素数Ｌを生成する素数生成部と、 生成された前記素数Ｌから計算可能なモジュラー多項式
   Φ（Ｘ、Ｙ）を生成する多項式生成部と、 生成された前記モジュラー多項式Φ（Ｘ、Ｙ）と前記ｊ
   不変数とを用いて、方程式を生成する方程式生成部と、 生成された前記方程式について前記有限体Ｆ上における
   解を算出する方程式求解部と、 算出された前記解の個数が予め与えられた個数条件を満
   たすか否かを判定する解判定部と、 前記解の個数が前記個数条件を満たすまで、前記素数生
   成部、前記多項式生成部、前記方程式生成部、前記方程
   式求解部及び前記解判定部に対して、それぞれ、異なる
   素数の生成、多項式の生成、方程式の生成、方程式の求
   解及び解の個数の判定をするように制御する制御部とを
   有することを特徴とする請求項２記載の楕円曲線変換装
   置。
4. 【請求項４】 前記素数生成部は、小さい素数から順に
   生成することを特徴とする請求項３記載の楕円曲線変換
   装置。
5. 【請求項５】 前記探索手段は、前記解の個数が前記個
   数条件を満たした後は、前記素数生成部に新たな素数を
   生成させることなく、同一の素数を用いて、楕円曲線を
   探索することを特徴とする請求項３記載の楕円曲線変換
   装置。
6. 【請求項６】 前記探索手段は、前記判定手段によって
   前記高速化条件を満たす楕円曲線が探索されなかったと
   判断された場合には、前記高速化条件を満たす楕円曲線
   の探索を繰り返すことを特徴とする請求項１記載の楕円
   曲線変換装置。
7. 【請求項７】 前記探索手段は、前記判定手段によって
   前記高速化条件を満たす楕円曲線が探索されなかったと
   判断された場合には、前記第１楕円曲線とＬ2次同種な
   楕円曲線群の中から、前記高速化条件を満たす楕円曲線
   を探索することを特徴とする請求項６記載の楕円曲線変
   換装置。
8. 【請求項８】 前記探索手段は、前記第１楕円曲線のｊ
   不変数と素数Ｌに対応するモジュラー多項式とから前記
   Ｌ1次同種な楕円曲線群を特定し、前記判定手段によっ
   て前記高速化条件を満たす楕円曲線が探索されなかった
   と判断された場合には、前記素数Ｌを他の素数に換える
   ことにより、前記Ｌ2次同種な楕円曲線を特定すること
   を特徴とする請求項７記載の楕円曲線変換装置。
9. 【請求項９】 前記探索手段は、前記第１楕円曲線と位
   数が同じで、かつ、Ｌ1次同種な楕円曲線群の中から、
   楕円曲線上での演算の計算量が削減される高速化条件を
   満たす楕円曲線の候補となる暫定的な楕円曲線を特定
   し、前記判定手段は、前記探索手段で特定された暫定的
   な楕円曲線が前記高速化条件を満たすか否かを判定し、 前記探索手段は、前記判定手段によって前記暫定的な楕
   円曲線が前記高速化条件を満たさないと判断された場合
   には、前記暫定的な楕円曲線を新たな第１楕円曲線と
   し、その第１楕円曲線と位数が同じで、かつ、一定関係
   を有する楕円曲線群であるＬ1次同種な楕円曲線群の中
   から、楕円曲線上での演算の計算量が削減される高速化
   条件を満たす楕円曲線を探索することを特徴とする請求
   項６記載の楕円曲線変換装置。
10. 【請求項１０】 前記探索手段は、前記第１楕円曲線の
    ｊ不変数と素数Ｌに対応するモジュラー多項式とから前
    記Ｌ1次同種な楕円曲線群を特定し、前記判定手段によ
    って前記高速化条件を満たす楕円曲線が探索されなかっ
    たと判断された場合には、同一の素数を用いて、前記Ｌ
    1次同種な楕円曲線を探索することを特徴とする請求項
    ９記載の楕円曲線変換装置。
11. 【請求項１１】 前記高速化条件は、前記楕円曲線の方
    程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂにおいてａ＝−３を満
    たすことであることを特徴とする請求項１記載の楕円曲
    線変換装置。
12. 【請求項１２】 前記高速化条件は、前記楕円曲線がモ
    ンゴメリ型楕円曲線であることであることを特徴とする
    請求項１記載の楕円曲線変換装置。
13. 【請求項１３】 有限体Ｆ上の第１楕円曲線を有限体Ｆ
    上の第２楕円曲線に変換する楕円曲線変換方法であっ
    て、 前記第１楕円曲線と位数が同じで、かつ、一定関係を有
    する楕円曲線群であるＬ1次同種な楕円曲線群の中か
    ら、楕円曲線上での演算の計算量が削減される高速化条
    件を満たす楕円曲線を探索する探索ステップと、 前記探索ステップでの探索により、前記高速化条件を満
    たす楕円曲線が探索されたか否かを判定する判定ステッ
    プと、 前記判定ステップにおいて前記高速化条件を満たす楕円
    曲線が探索されたと判断された場合に、当該楕円曲線を
    前記第２楕円曲線として出力する出力ステップとを備え
    ることを特徴とする楕円曲線変換方法。
14. 【請求項１４】 前記探索ステップでは、前記判定ステ
    ップで前記高速化条件を満たす楕円曲線が探索されなか
    ったと判断された場合には、前記高速化条件を満たす楕
    円曲線の探索を繰り返すことを特徴とする請求項１３記
    載の楕円曲線変換方法。
15. 【請求項１５】 前記探索ステップでは、前記判定ステ
    ップで前記高速化条件を満たす楕円曲線が探索されなか
    ったと判断された場合には、前記第１楕円曲線とＬ2次
    同種な楕円曲線群の中から、前記高速化条件を満たす楕
    円曲線を探索することを特徴とする請求項１４記載の楕
    円曲線変換方法。
16. 【請求項１６】 前記探索ステップでは、前記第１楕円
    曲線と位数が同じで、かつ、Ｌ1次同種な楕円曲線群の
    中から、楕円曲線上での演算の計算量が削減される高速
    化条件を満たす楕円曲線の候補となる暫定的な楕円曲線
    を特定し、 前記判定ステップでは、前記探索ステップで特定された
    暫定的な楕円曲線が前記高速化条件を満たすか否かを判
    定し、 前記探索ステップでは、前記判定ステップによって前記
    暫定的な楕円曲線が前記高速化条件を満たさないと判断
    された場合には、前記暫定的な楕円曲線を新たな第１楕
    円曲線とし、その第１楕円曲線と位数が同じで、かつ、
    一定関係を有する楕円曲線群であるＬ1次同種な楕円曲
    線群の中から、楕円曲線上での演算の計算量が削減され
    る高速化条件を満たす楕円曲線を探索することを特徴と
    する請求項１４記載の楕円曲線変換方法。
17. 【請求項１７】 有限体Ｆ上の第１楕円曲線を有限体Ｆ
    上の第２楕円曲線に変換するためのプログラムであっ
    て、 前記第１楕円曲線と位数が同じで、かつ、一定関係を有
    する楕円曲線群であるＬ1次同種な楕円曲線群の中か
    ら、楕円曲線上での演算の計算量が削減される高速化条
    件を満たす楕円曲線を探索する探索ステップと、 前記探索ステップでの探索により、前記高速化条件を満
    たす楕円曲線が探索されたか否かを判定する判定ステッ
    プと、 前記判定ステップにおいて前記高速化条件を満たす楕円
    曲線が探索されたと判断された場合に、当該楕円曲線を
    前記第２楕円曲線として出力する出力ステップとをコン
    ピュータに実行させることを特徴とするプログラム。
18. 【請求項１８】 楕円曲線変換装置で得られた楕円曲線
    を利用する楕円曲線利用装置であって、 前記楕円曲線を特定するパラメータを記憶する記憶手段
    と、 有限体Ｆの構造と前記記憶手段に記憶されているパラメ
    ータとで定まる楕円曲線を利用する暗号、復号、デジタ
    ル署名、デジタル署名検証又は鍵共有を行う利用手段と
    を備え、 前記楕円曲線変換装置は、 有限体Ｆ上の第１楕円曲線を有限体Ｆ上の第２楕円曲線
    に変換する楕円曲線変換装置であって、 前記第１楕円曲線と位数が同じで、かつ、一定関係を有
    する楕円曲線群であるＬ1次同種な楕円曲線群の中か
    ら、楕円曲線上での演算の計算量が削減される高速化条
    件を満たす楕円曲線を探索する探索手段と、 前記探索手段による探索により、前記高速化条件を満た
    す楕円曲線が探索されたか否かを判定する判定手段と、 前記判定手段によって前記高速化条件を満たす楕円曲線
    が探索されたと判断された場合に、当該楕円曲線を前記
    第２楕円曲線として出力する出力手段とを備えることを
    特徴とする楕円曲線利用装置。
19. 【請求項１９】 前記楕円曲線利用装置は、さらに、 前記記憶手段に記憶されているパラメータを前記楕円曲
    線変換装置に送信することによって、前記楕円曲線変換
    装置に新たな楕円曲線を生成させるパラメータ送信手段
    と、 前記楕円曲線変換装置で生成された楕円曲線を特定する
    パラメータで前記記憶手段の内容を更新するパラメータ
    更新手段とを備えることを特徴とする請求項１８記載の
    楕円曲線利用装置。
20. 【請求項２０】 有限体Ｆ上の楕円曲線を生成する楕円
    曲線生成装置であって、 有限体Ｆ上の第１楕円曲線を生成する生成手段と、 生成された前記第１楕円曲線と位数が同じで、かつ、一
    定関係を有する楕円曲線群であるＬ1次同種な楕円曲線
    群の中から、楕円曲線上での演算の計算量が削減される
    高速化条件を満たす楕円曲線を探索する探索手段と、 前記探索手段による探索により、前記高速化条件を満た
    す楕円曲線が探索されたか否かを判定する判定手段と、 前記判定手段によって前記高速化条件を満たす楕円曲線
    が探索されたと判断された場合に、当該楕円曲線を前記
    第２楕円曲線として出力する出力手段とを備えることを
    特徴とする楕円曲線生成装置。
21. 【請求項２１】 前記探索手段は、前記判定手段によっ
    て前記高速化条件を満たす楕円曲線が探索されなかった
    と判断された場合には、前記高速化条件を満たす楕円曲
    線の探索を繰り返すことを特徴とする請求項２０記載の
    楕円曲線生成装置。
22. 【請求項２２】 前記高速化条件は、前記楕円曲線の方
    程式ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂにおいてａ＝−３を満
    たすことであることを特徴とする請求項２０記載の楕円
    曲線生成装置。
23. 【請求項２３】 前記高速化条件は、前記楕円曲線がモ
    ンゴメリ型楕円曲線であることであることを特徴とする
    請求項２０記載の楕円曲線生成装置。