(57)【特許請求の範囲】
【請求項１】
有限体Ｆ上の第１楕円曲線としてのワイヤーシュトラウス型楕円曲線ＥＩ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂを、第２有限体Ｆ上の第２楕円曲線としての楕円曲線ＥＯ：ｙ＾２＝ｘ＾３−３×ｘ＋ｂ’に変換する楕円曲線変換装置であって、
外部装置から前記第１楕円曲線のパラメータａ及びｂと前記第１楕円曲線の位数とを入力し、前記第１楕円曲線と位数が同じで、かつ、前記第１楕円曲線と群準同型である楕円曲線群であるＬ１次同種な楕円曲線群ＥＩ２：ｙ＾２＝ｘ＾３＋ａ２×ｘ＋ｂ２の中から、楕円曲線上でａ２＝−３の条件を満たす楕円曲線を探索する探索手段と、
前記探索手段による探索により、前記条件を満たす楕円曲線が探索されたか否かを判定する判定手段と、
前記判定手段によって前記条件を満たす楕円曲線が探索されたと判断された場合に、当該楕円曲線のパラメータｂ２を前記第２楕円曲線のパラメータｂ’として前記外部装置へ出力する出力手段と
を備えることを特徴とする楕円曲線変換装置。
【請求項２】
前記探索手段は、
前記第１楕円曲線のｊ不変数を算出するｊ不変数算出部と、
予め記憶している素数の系列から小さい順に素数ＬをＬ１として取出す素数生成部と、
取出された前記素数Ｌから計算可能なモジュラー多項式Φ（Ｘ、Ｙ）を生成する多項式生成部と、
生成された前記モジュラー多項式Φ（Ｘ、Ｙ）と前記ｊ不変数とを用いて、方程式を生成する方程式生成部と、
生成された前記方程式について前記有限体Ｆ上における解を算出する方程式求解部と、
算出された前記解の個数が予め与えられた個数条件を満たすか否かを判定する解判定部と、
前記解の個数が前記個数条件を満たすまで、前記素数生成部、前記多項式生成部、前記方程式生成部、前記方程式求解部及び前記解判定部に対して、それぞれ、異なる素数の生成、多項式の生成、方程式の生成、方程式の求解及び解の個数の判定をするように制御する制御部と
を有することを特徴とする請求項１記載の楕円曲線変換装置。
【請求項３】
前記制御部は、前記解の個数が前記個数条件を満たした後は、前記素数生成部から新たな素数を取出すことなく、同一の素数を用いて、楕円曲線を探索する
ことを特徴とする請求項２記載の楕円曲線変換装置。
【請求項４】
前記探索手段は、前記判定手段によって前記条件を満たす楕円曲線が探索されなかったと判断された場合には、前記条件を満たす楕円曲線の探索を繰り返す
ことを特徴とする請求項１記載の楕円曲線変換装置。
【請求項５】
前記探索手段は、前記判定手段によって前記条件を満たす楕円曲線が探索されなかったと判断された場合には、前記第１楕円曲線とＬ２次同種な楕円曲線群の中から、前記条件を満たす楕円曲線を探索する
ことを特徴とする請求項４記載の楕円曲線変換装置。
【請求項６】
前記探索手段は、前記第１楕円曲線と位数が同じで、かつ、Ｌ１次同種な楕円曲線群の中から、楕円曲線上でａ２＝−３の条件を満たす楕円曲線の候補となる暫定的な楕円曲線を特定し、
前記判定手段は、前記探索手段で特定された暫定的な楕円曲線が前記条件を満たすか否かを判定し、
前記探索手段は、前記判定手段によって前記暫定的な楕円曲線が前記条件を満たさないと判断された場合には、前記暫定的な楕円曲線を新たな第１楕円曲線とし、その第１楕円曲線と位数が同じで、かつ、前記第１楕円曲線と群準同型である楕円曲線群であるＬ1次同種な楕円曲線群の中から、楕円曲線上でａ２＝−３の条件を満たす楕円曲線を探索する
ことを特徴とする請求項４記載の楕円曲線変換装置。
【請求項７】
有限体Ｆ上の第１楕円曲線としてのワイヤーシュトラウス型楕円曲線ＥＩ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂを、第２有限体Ｆ上の第２楕円曲線としてのモンゴメリ型楕円曲線ＥＯ：Ｂ’×ｙ＾２＝ｘ＾３＋Ａ’×ｘ＾２＋ｘに変換する楕円曲線変換装置であって、
外部装置から前記第１楕円曲線のパラメータａ及びｂと前記第１楕円曲線の位数とを入力し、前記第１楕円曲線と位数が同じで、かつ、前記第１楕円曲線と群準同型であるモンゴメリ型楕円曲線ＥＩ２：Ｂ２×ｙ＾２＝ｘ＾３＋Ａ２×ｘ＾２＋ｘを探索する探索手段と、
前記探索手段による探索により、前記モンゴメリ型楕円曲線ＥＩ２が探索されたか否かを判定する判定手段と、
前記判定手段によって前記モンゴメリ型楕円曲線ＥＩ２が探索されたと判断された場合に、当該モンゴメリ型楕円曲線ＥＩ２のパラメータＡ２及びＢ２を前記第２楕円曲線のパラメータＢ’及びＡ’として前記外部装置へ出力する出力手段と
を備えることを特徴とする楕円曲線変換装置。
【請求項８】
楕円曲線変換装置で得られた楕円曲線を利用する楕円曲線利用装置であって、
前記楕円曲線を特定するパラメータを記憶する記憶手段と、
有限体Ｆの構造と前記記憶手段に記憶されているパラメータとで定まる楕円曲線を利用する暗号、復号、デジタル署名、デジタル署名検証又は鍵共有を行う利用手段とを備え、
前記楕円曲線変換装置は、
有限体Ｆ上の第１楕円曲線としてのワイヤーシュトラウス型楕円曲線ＥＩ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂを、第２有限体Ｆ上の第２楕円曲線としての楕円曲線Ｅ０：ｙ＾２＝ｘ＾３−３×ｘ＋ｂ’に変換する楕円曲線変換装置であって、
外部装置から前記第１楕円曲線のパラメータａ及びｂと前記第１楕円曲線の位数とを入力し、前記第１楕円曲線と位数が同じで、かつ、前記第１楕円曲線と群準同型である楕円曲線群であるＬ１次同種な楕円曲線群ＥＩ２：ｙ＾２＝ｘ＾３＋ａ２×ｘ＋ｂ２の中から、楕円曲線上でａ２＝−３の条件を満たす楕円曲線を探索する探索手段と、
前記探索手段による探索により、前記条件を満たす楕円曲線が探索されたか否かを判定する判定手段と、
前記判定手段によって前記条件を満たす楕円曲線が探索されたと判断された場合に、当該楕円曲線のパラメータｂ２を前記第２楕円曲線のパラメータｂ’として前記外部装置へ出力する出力手段と
を備えることを特徴とする楕円曲線利用装置。
【請求項９】
前記楕円曲線利用装置は、さらに、
前記記憶手段に記憶されているパラメータを前記楕円曲線変換装置に送信することによって、前記楕円曲線変換装置に新たな楕円曲線のパラメータを生成させるパラメータ送信手段と、
前記楕円曲線変換装置で生成されたパラメータで前記記憶手段の内容を更新するパラメータ更新手段とを備える
ことを特徴とする請求項８記載の楕円曲線利用装置。
【請求項１０】
有限体Ｆ上の第１楕円曲線としてのワイヤーシュトラウス型楕円曲線ＥＩ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂを、第２有限体Ｆ上の第２楕円曲線としての楕円曲線ＥＯ：ｙ＾２＝ｘ＾３−３×ｘ＋ｂ’に変換する楕円曲線変換装置であって、
前記第１楕円曲線のパラメータａ及びｂと前記第１楕円曲線の位数とを生成する生成手段と、
前記生成された前記第１楕円曲線と位数が同じで、かつ、前記第１楕円曲線と群準同型である楕円曲線群であるＬ１次同種な楕円曲線群の中から、楕円曲線上でａ２＝−３の条件を満たす楕円曲線を探索する探索手段と、
前記探索手段による探索により、前記条件を満たす楕円曲線が探索されたか否かを判定する判定手段と、
前記判定手段によって前記条件を満たす楕円曲線が探索されたと判断された場合に、当該楕円曲線のパラメータｂ２を前記第２楕円曲線のパラメータｂ’として外部装置へ出力する出力手段と
を備えることを特徴とする楕円曲線変換装置。
【請求項１１】
前記探索手段は、前記判定手段によって前記条件を満たす楕円曲線が探索されなかったと判断された場合には、前記条件を満たす楕円曲線の探索を繰り返す
ことを特徴とする請求項１０記載の楕円曲線変換装置。
【請求項１２】
楕円曲線変換装置で得られた楕円曲線を利用する楕円曲線利用装置であって、
前記楕円曲線を特定するパラメータを記憶する記憶手段と、
有限体Ｆの構造と前記記憶手段に記憶されているパラメータとで定まる楕円曲線を利用する暗号、復号、デジタル署名、デジタル署名検証又は鍵共有を行う利用手段とを備え、
前記楕円曲線変換装置は、
有限体Ｆ上の第１楕円曲線としてのワイヤーシュトラウス型楕円曲線ＥＩ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂを、第２有限体Ｆ上の第２楕円曲線としてのモンゴメリ型楕円曲線ＥＯ：Ｂ’×ｙ＾２＝ｘ＾３＋Ａ’×ｘ＾２＋ｘに変換する楕円曲線変換装置であって、
外部装置から前記第１楕円曲線のパラメータａ及びｂと前記第１楕円曲線の位数とを入力し、前記第１楕円曲線と位数が同じで、かつ、前記第１楕円曲線と群準同型であるモンゴメリ型楕円曲線ＥＩ２：Ｂ２×ｙ＾２＝ｘ＾３＋Ａ２×ｘ＾２＋ｘを探索する探索手段と、
前記探索手段による探索により、前記モンゴメリ型楕円曲線ＥＩ２が探索されたか否かを判定する判定手段と、
前記判定手段によって前記モンゴメリ型楕円曲線ＥＩ２が探索されたと判断された場合に、当該モンゴメリ型楕円曲線ＥＩ２のパラメータＡ２及びＢ２を前記第２楕円曲線のパラメータＢ’及びＡ’として前記外部装置へ出力する出力手段と
を備えることを特徴とする楕円曲線利用装置。
【請求項１３】
前記楕円曲線利用装置は、さらに、
前記記憶手段に記憶されているパラメータを前記楕円曲線変換装置に送信することによって、前記楕円曲線変換装置に新たな楕円曲線のパラメータを生成させるパラメータ送信手段と、
前記楕円曲線変換装置で生成されたパラメータで前記記憶手段の内容を更新するパラメータ更新手段とを備える
ことを特徴とする請求項１２記載の楕円曲線利用装置。
【請求項１４】
有限体Ｆ上の第１楕円曲線としてのワイヤーシュトラウス型楕円曲線ＥＩ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂを、第２有限体Ｆ上の第２楕円曲線としてのモンゴメリ型楕円曲線ＥＯ：Ｂ’×ｙ＾２＝ｘ＾３＋Ａ’×ｘ＾２＋ｘに変換する楕円曲線変換装置であって、
前記第１楕円曲線のパラメータａ及びｂと前記第１楕円曲線の位数とを生成する生成手段と、
前記生成された前記第１楕円曲線と位数が同じで、かつ、前記第１楕円曲線と群準同型であるモンゴメリ型楕円曲線ＥＩ２：Ｂ２×ｙ＾２＝ｘ＾３＋Ａ２×ｘ＾２＋ｘを探索する探索手段と、
前記探索手段による探索により、前記モンゴメリ型楕円曲線ＥＩ２が探索されたか否かを判定する判定手段と、
前記判定手段によって前記モンゴメリ型楕円曲線ＥＩ２が探索されたと判断された場合に、当該モンゴメリ型楕円曲線ＥＩ２のパラメータＡ２及びＢ２を前記第２楕円曲線のパラメータＢ’及びＡ’として外部装置へ出力する出力手段と
を備えることを特徴とする楕円曲線変換装置。
【請求項１５】
前記外部装置は、公開鍵暗号を用いる暗号装置、復号装置、デジタル著名装置、デジタル署名検証装置、鍵共有装置のいずれかであることを特徴とする請求項１、請求項７、請求項１０及び請求項１４のいずれかに記載の楕円曲線変換装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報セキュリテイ技術としての暗号技術に関し、特に、楕円曲線を用いる秘密通信、デジタル署名及び鍵共有技術に関する。
【０００２】
【従来の技術】
１．公開鍵暗号
近年、コンピュータ技術と通信技術とに基づくデータ通信が広く普及してきており、このデータ通信においては、秘密通信方式又はデジタル署名方式が用いられている。ここで、秘密通信方式とは、特定の通信相手以外に通信内容を漏らすことなく通信を行う方式である。またデジタル署名方式とは、通信相手に通信内容の正当性を示したり、発信者の身元を証明する通信方式である。
【０００３】
これらの秘密通信方式又はデジタル署名方式には公開鍵暗号と呼ばれる暗号方式が用いられる。公開鍵暗号は通信相手が多数の時、通信相手毎に異なる暗号鍵を容易に管理するための方式であり、多数の通信相手と通信を行うのに不可欠な基盤技術である。公開鍵暗号を用いる秘密通信では、暗号化鍵と復号化鍵とが異なり、復号化鍵は秘密にするが、暗号化鍵は公開する。
【０００４】
この公開鍵暗号の安全性の根拠として離散対数問題が用いられる。離散対数問題には、代表的なものとして、有限体上定義されるもの及び楕円曲線上定義されるものがある（例えば、非特許文献１）。
【０００５】
２．楕円曲線上の離散対数問題
楕円曲線上の離散対数問題について、以下に述べる。楕円曲線上の離散対数問題とは、Ｅ（ＧＦ（ｐ））を有限体ＧＦ（ｐ）上で定義された楕円曲線とし、楕円曲線Ｅの位数が大きな素数で割り切れる場合に、楕円曲線Ｅに含まれる元Ｇをベースポイントとする。この時、楕円曲線Ｅに含まれる与えられた元Ｙに対して、
（式１）  Ｙ＝ｘ＊Ｇ
となる整数ｘが存在するならば、ｘを求めよ、という問題である。
【０００６】
ここで、ｐは素数、ＧＦ（ｐ）はｐ個の元を持つ有限体である。また、この明細書において、記号＊は、楕円曲線に含まれる元を複数回加算する演算を示し、ｘ＊Ｇは、次式に示すように、楕円曲線に含まれる元Ｇをｘ回加算することを意味する。
【０００７】
ｘ＊Ｇ＝Ｇ＋Ｇ＋Ｇ＋…＋Ｇ
離散対数問題を公開鍵暗号の安全性の根拠とするのは、多くの元を有する有限体ＧＦ（ｐ）に対して、上記問題は極めて難しいからである。
【０００８】
３．楕円曲線上の離散対数問題を応用したエルガマル署名
以下に、上記楕円曲線上の離散対数問題を応用したエルガマル署名によるデジタル署名方式について、図１１を用いて、説明する。この図は、上記エルガマル署名によるデジタル署名方式の手順を示すシーケンス図である。ユーザＡ１１、管理センタ１２及びユーザＢ１３は、ネットワークで接続されている。ｐを素数、有限体ＧＦ（ｐ）上の楕円曲線をＥとする。ＥのベースポイントをＧとし、Ｅの位数をｑとする。つまり、ｑは、
（式２）  ｑ＊Ｇ＝０
を満たす最小の正整数である。
【０００９】
なお、ｘ座標、ｙ座標共に∞である（∞、∞）を無限遠点といい、０で表す。この０は、楕円曲線を群とみた時に、無限遠点が加算における「零元」の役割を果たす。
【００１０】
（１）管理センタ１２による公開鍵の生成
管理センタ１２は、予め通知されているユーザＡ１１の秘密鍵ｘＡを用いて、式３に従って、ユーザＡ１１の公開鍵ＹＡを生成する（ステップＳ１４１〜Ｓ１４２）。
（式３）  ＹＡ＝ｘＡ＊Ｇ
その後、管理センタ１２は、素数ｐ、楕円曲線Ｅ及びベースポイントＧをシステムパラメータとして公開し、また、他のユーザＢ１３にユーザＡ１１の公開鍵ＹＡを公開する（ステップＳ１４３〜Ｓ１４４）。
【００１１】
（２）ユーザＡ１１による署名生成
ユーザＡ１１は、乱数ｋを生成する（ステップＳ１４５）。次に、ユーザＡ１１は、
（式４）  Ｒ１＝（ｒｘ，ｒｙ）＝ｋ＊Ｇ
を計算し（ステップＳ１４６）、
（式５）  ｓ×ｋ＝ｍ＋ｒｘ×ｘＡ  （ｍｏｄ  ｑ）
から、ｓを計算する（ステップＳ１４７）。ここで、ｍは、ユーザＡ１１がユーザＢ１３へ送信するメッセージである。さらに、ユーザＡ１１は、得られた（Ｒ１、ｓ）を署名としてメッセージｍと共に、ユーザＢ１３へ送信する（ステップＳ１４８）。
【００１２】
（３）ユーザＢ１３による署名検証
ユーザＢ１３は、
（式６）  ｓ＊Ｒ１＝ｍ＊Ｇ＋ｒｘ＊ＹＡ
が成立するかどうか判定することにより、送信者であるユーザＡ１１の身元を確認する（ステップＳ１４９）。これは、
0004225764.tif 000002
となることから明らかである。
【００１３】
４．楕円曲線上の点の加算、２倍算の演算による計算量
上記に示した楕円曲線上の離散対数問題を応用したエルガマル署名によるデジタル署名方式における公開鍵の生成、署名生成、署名検証のそれぞれにおいて、楕円曲線上の点の冪倍の演算の計算が行われる。例えば、式３に示す「ｘＡ＊Ｇ」、式４に示す「ｋ＊Ｇ」、式６に示す「ｓ＊Ｒ１」、「ｍ＊Ｇ」、「ｒｘ＊ＹＡ」は、楕円曲線上の点の冪倍の演算である。なお、楕円曲線の演算公式については、非特許文献２に詳述されている。
【００１４】
楕円曲線の演算公式について、以下に説明する。楕円曲線の方程式をｙ＾２  ＝  ｘ＾３  ＋ａ×ｘ＋ｂ  とし、任意の点Ｐの座標を（ｘ１，ｙ１）とし、任意の点Ｑの座標を（ｘ２，ｙ２）とする。ここで、Ｒ＝Ｐ＋Ｑで定まる点Ｒの座標を（ｘ３，ｙ３）とする。
【００１５】
なお、Ｐ≠Ｑの場合、Ｒ＝Ｐ＋Ｑは、加算の演算となる。加算の公式を以下に示す。
【００１６】
ｘ３＝｛（ｙ２−ｙ１）／（ｘ２−ｘ１）｝＾２−ｘ１−ｘ２
ｙ３＝｛（ｙ２−ｙ１）／（ｘ２−ｘ１）｝（ｘ１−ｘ３）−ｙ１
Ｐ＝Ｑの場合、Ｒ＝Ｐ＋Ｑ＝Ｐ＋Ｐ＝２×Ｐとなり、Ｒ＝Ｐ＋Ｑは、２倍算の演算となる。２倍算の公式を以下に示す。
ｘ３＝｛（３ｘ１＾２＋ａ）／２ｙ１｝＾２−２ｘ１
ｙ３＝｛（３ｘ１＾２＋ａ）／２ｙ１｝（ｘ１−ｘ３）−ｙ１
【００１７】
なお、上記演算は、楕円曲線が定義される有限体上での演算である。上記に示すように、２項組座標であるアフィン座標、即ち今まで述べてきた座標において、楕円曲線上の加算演算を行う場合に、楕円曲線上の加算１回につき、１回の有限体上の逆数計算が必要となる。一般に、有限体上の逆数計算は、有限体上での乗算計算と比較して、１０倍程度の計算量を必要とする。
【００１８】
そこで、計算量を削減することを目的として、射影座標と呼ばれる３項組の座標が用いられる。射影座標とは、３項組Ｘ、Ｙ、Ｚからなる座標のことであって、座標（Ｘ，Ｙ，Ｚ）と座標（Ｘ’，Ｙ’，Ｚ’）とに対して、ある数ｎが存在して、Ｘ’＝ｎＸ、Ｙ’＝ｎＹ、Ｚ’＝ｎＺなる関係があるならば、（Ｘ，Ｙ，Ｚ）＝（Ｘ’，Ｙ’，Ｚ’）とするものである。アフィン座標（ｘ，ｙ）と射影座標（Ｘ，Ｙ，Ｚ）とは、
（ｘ，ｙ）    →  （ｘ，ｙ，１）
（Ｘ，Ｙ，Ｚ）→  （Ｘ／Ｙ，Ｙ／Ｚ）  （Ｚ≠０の時）なる関係で、互いに対応している。ここで、記号→は、次に示す意味で用いている。集合Ｓ１の任意の元に、集合Ｓ２の一つの元が対応する時、Ｓ１→Ｓ２と表記する。
【００１９】
以下、楕円曲線の演算は、全て、射影座標で行われるものとする。次に、射影座標上の楕円曲線の加算公式、２倍公式について説明する。これらの公式は、もちろん、前に述べたアフィン座標における加算公式、２倍公式と整合性のあるものである。冪倍の演算は、楕円曲線上の点の加算、２倍算の演算の繰り返しによって実現できる。この冪倍の演算のうち、加算の計算量は、楕円曲線のパラメータに依存しないが、２倍算の計算量は、楕円曲線のパラメータに依存する。
【００２０】
ここでは、ｐを１６０ビットの素数とし、有限体ＧＦ（ｐ）上の楕円曲線をＥ：ｙ＾２  ＝  ｘ＾３  ＋ａｘ＋ｂ  とし、楕円曲線Ｅ上の元Ｐ、Ｑをそれぞれ、Ｐ＝（Ｘ１，Ｙ１，Ｚ１）、  Ｑ＝（Ｘ２，Ｙ２，Ｚ２）で表す時、
Ｒ＝（Ｘ３，Ｙ３，Ｚ３）＝Ｐ＋Ｑを以下のようにして、求める。
【００２１】
（ｉ）Ｐ≠Ｑの場合
この場合、加算の演算となる。
（ｓｔｅｐ  １−１）  中間値の計算
以下を計算する。
（式８）    Ｕ１＝Ｘ１×Ｚ２＾２
（式９）    Ｕ２＝Ｘ２×Ｚ１＾２
（式１０）  Ｓ１＝Ｙ１×Ｚ２＾３
（式１１）  Ｓ２＝Ｙ２×Ｚ１＾３
（式１２）  Ｈ＝Ｕ２−Ｕ１
（式１３）  ｒ＝Ｓ２−Ｓ１
（ｓｔｅｐ  １−２）  Ｒ＝（Ｘ３，Ｙ３，Ｚ３）の計算
以下を計算する。
（式１４）  Ｘ３＝−Ｈ＾３−２×Ｕ１×Ｈ＾２＋ｒ＾２
（式１５）  Ｙ３＝−Ｓ１×Ｈ＾３＋ｒ×（Ｕ１×Ｈ＾２−Ｘ３）
（式１６）  Ｚ３＝Ｚ１×Ｚ２×Ｈ
【００２２】
（ｉｉ）Ｐ＝Ｑの場合（即ち、Ｒ＝２Ｐ）
この場合、２倍算の演算となる。
（ｓｔｅｐ  ２−１）  中間値の計算
以下を計算する。
（式１７）  Ｓ＝４×Ｘ１×Ｙ１＾２
（式１８）  Ｍ＝３×Ｘ１＾２＋ａ×Ｚ１＾４
（式１９）  Ｔ＝−２×Ｓ＋Ｍ＾２
（ｓｔｅｐ  ２−２）  Ｒ＝（Ｘ３，Ｙ３，Ｚ３）の計算
以下を計算する。
（式２０）  Ｘ３＝Ｔ
（式２１）  Ｙ３＝−８×Ｙ１＾４＋Ｍ×（Ｓ−Ｔ）
（式２２）  Ｚ３＝２×Ｙ１×Ｚ１
【００２３】
次に、楕円曲線の加算、２倍算を行う場合の計算量について説明する。ここで、有限体ＧＦ（ｐ）上の１回の乗算による計算量を１Ｍｕｌ、１回の２乗算による計算量を１Ｓｑで表す。なお、一般のマイクロプロセッサにおいては、１Ｓｑ≒０．８Ｍｕｌである。
【００２４】
上記の例によると、Ｐ≠Ｑの場合に示されている楕円曲線上の加算の計算量は、式８〜式１６において、乗算の回数及び２乗算の回数をカウントすることにより得られ、１２Ｍｕｌ＋４Ｓｑである。これは、式８、９、１０、１１、１４、１５、１６における加算の計算量は、それぞれ、１Ｍｕｌ＋１Ｓｑ、１Ｍｕｌ＋１Ｓｑ、２Ｍｕｌ、２Ｍｕｌ、２Ｍｕｌ＋２Ｓｑ、２Ｍｕｌ、２Ｍｕｌであることから明らかである。
【００２５】
また、上記の例によると、Ｐ＝Ｑの場合に示されている楕円曲線上の２倍算の計算量は、式１７〜式２２において、乗算の回数及び２乗算の回数をカウントすることにより得られ、４Ｍｕｌ＋６Ｓｑである。これは、式１７、１８、１９、２１、２２における２倍算の計算量は、それぞれ、１Ｍｕｌ＋１Ｓｑ、１Ｍｕｌ＋３Ｓｑ、１Ｓｑ、１Ｍｕｌ＋１Ｓｑ、１Ｍｕｌであることから明らかである。
【００２６】
なお、上記回数のカウントにおいて、例えば、式１４のＨ＾３については、
Ｈ＾３＝Ｈ＾２×Ｈと展開できるので、Ｈ＾３の計算量は、１Ｍｕｌ＋１Ｓｑとし、式１８のＺ１＾４については、
Ｚ１＾４＝（Ｚ１＾２）＾２と展開できるので、Ｚ１＾４の計算量は、２Ｓｑとする。
【００２７】
また、式１４のＨ＾２については、前述のＨ＾３の計算のプロセスにおいて、Ｈ＾２が算出されているので、Ｈ＾２の計算量は再度カウントしない。また、乗算の回数のカウントの際、ある値に小さい値を乗じて行われる乗算の回数は、カウントしない。その理由を以下に説明する。ここで言う小さい値とは、式８〜式２２において、乗算の対象となる小さい固定値であり、具体的には、２、３、４、８などの値である。これらの値は、多くとも４ビットの２進数で表現できる。一方、その他の変数は、通常、１６０ビットの値を有している。
【００２８】
一般に、マイクロプロセッサにおいて、乗数と被乗数との乗算は、被乗数のシフトと加算の繰り返しにより行われる。即ち、２進数で表現される乗数の各ビット毎に、このビットが１であるならば、２進数で表現される被乗数の最下位ビットが、このビットの存在する位置に一致するように、被乗数をシフトして、１つのビット列を得る。乗数の全ビットについて、このようにして得られた少なくとも１つのビット列を全て加算する。
【００２９】
例えば、１６０ビットの乗数と１６０ビットの被乗数との乗算においては、１６０ビットの被乗数を１６０回シフトし、１６０個のビット列を得、得られた１６０個のビット列を加算する。一方、４ビットの乗数と１６０ビットの被乗数との乗算においては、１６０ビットの被乗数を４回シフトし、４個のビット列を得、得られた４個のビット列を加算する。
【００３０】
乗算は、上記に示すようにして行われるので、乗算がある値に小さい値を乗じて行われる場合には、前記繰り返しの回数が少なくなる。従って、その計算量は少ないと見なせるので、乗算の回数にカウントしない。以上説明したように、楕円曲線の２倍算を行う場合において、式１８には、楕円曲線のパラメータａが含まれている。このパラメータａの値として、例えば、小さい値を採用すると、楕円曲線上の２倍算の計算量は、１Ｍｕｌ分削減でき、３Ｍｕｌ＋６Ｓｑとなる。なお、加算に関しては、楕円曲線のパラメータを変化させても、計算量は変わらない。
【００３１】
５．暗号に適した楕円曲線の選択
次に暗号に適した楕円曲線を選択する方法について説明する。なお、その詳細については、「IEEE P1363 Working draft」（１９９７年２月６日、ＩＥＥＥ発行）に詳しく書かれている。暗号に適した楕円曲線は、以下のステップを繰り返すことにより得られる。
【００３２】
（ｓｔｅｐ  １）  任意の楕円曲線の選択
有限体ＧＦ（ｐ）上の任意のパラメータａ、ｂを選ぶ。ここで、ａ、ｂは、式２３を満たし、ｐは素数である。
（式２３）  ４×ａ＾３＋２７×ｂ＾２  ≠０  （ｍｏｄ  ｐ）
選択されたａ、ｂを用いて、楕円曲線をＥ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂとする。
【００３３】
（ｓｔｅｐ  ２）  暗号に適した楕円曲線であるかどうかを判定するために、楕円曲線Ｅの元の個数＃Ｅ（ＧＦ（ｐ））を計算し、
（条件１）  ＃Ｅ（ＧＦ（ｐ））が大きな素数で割り切れ、かつ、
（条件２）  ＃Ｅ（ＧＦ（ｐ））−（ｐ＋１）≠０，−１である場合に、楕円曲線Ｅを採用する。
【００３４】
上記に説明したように、楕円曲線のパラメータａとして固定的に小さい値を選択すると、楕円曲線の冪倍の演算において計算量を削減できるものの、パラメータを予め固定的に取ることにより、暗号に適した安全な楕円曲線を選択しにくいという問題点がある。
【００３５】
また逆に、上記に説明した楕円曲線の選択方法を用いて、暗号に適した安全な楕円曲線を選択すると、楕円曲線のパラメータａとして小さい値を選択できるとは限らず、計算量を削減できないという問題点がある。このように、暗号に適した安全な楕円曲線を選択し、その楕円曲線での演算量を削減するためには、相互に矛盾し対立する問題点を有する。
【００３６】
６．従来の楕円曲線変換装置
上記問題点を解決するために、従来の「楕円曲線変換装置、楕円曲線変換方法及び楕円曲線利用装置」として、以下の楕円曲線変換装置が示されている（例えば、特許第３０５０３１３号公報）。この従来の楕円曲線変換装置は、入力された任意の楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂを、その位数を変えることなく、小さな係数ａ（ａ＝−３など）を持つ楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂに変換する装置である。つまり、安全性を維持したまま、より計算量を削減することが可能な楕円曲線を生成する。
この装置は、入力の楕円曲線をそれと同型な楕円曲線に変換している。
【００３７】
楕円曲線変換装置１００は、図１２に示すように、パラメータ受信部１１０、変換係数取得部１２０、変換楕円曲線算出部１３０、パラメータ送出部１４０から構成される。
【００３８】
パラメータ受信部１１０は、外部の装置から、楕円曲線のパラメータａ、ｂと、前記楕円曲線上の元Ｇと、素数ｐとを受信する。ここで、ｐは、１６０ビットの素数である。
【００３９】
前記外部の装置には、公開鍵暗号を用いる暗号装置、復号装置、デジタル署名装置、デジタル署名検証装置、鍵共有装置などが含まれる。前記外部の装置は、公開鍵暗号の安全性の根拠として楕円曲線上の離散対数問題を用いており、前記楕円曲線を有している。ここで、有限体ＧＦ（ｐ）上の任意に構成される前記楕円曲線は、Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂで示され、前記元Ｇは、前記楕円曲線の任意に構成され、Ｇ＝（ｘ０，ｙ０）で表される。
【００４０】
変換係数取得部１２０は、関数Ｔ（ｉ）を有する。関数Ｔ（ｉ）は、ｉ＝０、１、２、３、４の時、それぞれ、−３、１、−１、２、−２の値を有する。また、関数Ｔ（ｉ）は、ｉ＝５、６、７、８、９、１０、１１、…の時、３、４、−４、５、−５、６、−６、…の値を有する。
【００４１】
変換係数取得部１２０は、ｉ＝０から始めて、ｉの値を１ずつ加算しながら、（式２４）  −２＾３１＋１≦Ｔ（ｉ）≦２＾３１−１
を満たし、かつ、
（式２５）  Ｔ（ｉ）＝ｔ＾４×ａ  （ｍｏｄ  ｐ）
となる変換係数ｔであって、有限体ＧＦ（ｐ）上の元である変換係数ｔを算出する。
【００４２】
ここで、式２４は、Ｔ（ｉ）が３２ビット以下になるように取られることを示している。なお、関数Ｔ（ｉ）は、ｉ＝０の時に、−３の値を有しており、変換係数取得部１２０は、ｉ＝０から始めて、ｉの値を１ずつ加算しながら、関数Ｔ（ｉ）の値を参照するので、最初に−３の値が参照される。
【００４３】
また、関数Ｔ（ｉ）は、ｉ＝０の時に、−３の値を有していることを除いて、絶対値の小さい値から大きい値へと順に値を有しているので、絶対値の小さい値から順に参照することができる。
【００４４】
変換楕円曲線算出部１３０は、有限体ＧＦ（ｐ）上に構成される変換楕円曲線Ｅｔ：ｙ’＾２＝ｘ’＾３＋ａ’×ｘ’＋ｂ’のパラメータａ’、ｂ’をそれぞれ次のようにして、算出する。
（式２６）  ａ’＝ａ×ｔ＾４
（式２７）  ｂ’＝ｂ×ｔ＾６
【００４５】
また、変換楕円曲線算出部１３０は、元Ｇに対応する変換楕円曲線Ｅｔ上の元Ｇｔ＝（ｘｔ０，ｙｔ０）を次のようにして、算出する。
（式２８）  ｘｔ０＝ｔ＾２×ｘ０
（式２９）  ｙｔ０＝ｔ＾３×ｙ０
【００４６】
なお、楕円曲線Ｅ上の任意の点は、以上のようにして生成されたパラメータａ’、ｂ’で定まる変換楕円曲線Ｅｔ上の１点に変換される。
【００４７】
パラメータ送出部１４０は、前記算出された変換楕円曲線Ｅｔのパラメータａ’、ｂ’と、元Ｇｔ（ｘｔ０，ｙｔ０）とを前記外部の装置へ送出する。
このような従来の楕円曲線変換装置１００の動作は以下の通りである。
【００４８】
パラメータ受信部１１０は、外部の装置から素数ｐと、楕円曲線Ｅのパラメータａ及びｂとを受け取り（ステップＳ１５１）、前記楕円曲線上の元Ｇを受け取る（ステップＳ１５２）。次に、変換係数取得部１２０は、変換係数ｔを算出し（ステップＳ１５３）、変換楕円曲線算出部１３０は、有限体ＧＦ（ｐ）上に構成される変換楕円曲線Ｅｔのパラメータａ’、ｂ’と、元Ｇに対応する変換楕円曲線Ｅｔ上の元Ｇｔ＝（ｘｔ０，ｙｔ０）を算出し（ステップＳ１５４）、パラメータ送出部１４０は、前記算出された変換楕円曲線Ｅｔのパラメータａ’、ｂ’と、元Ｇｔ（ｘｔ０，ｙｔ０）とを前記外部の装置へ送出する（ステップＳ１５５）。
【００４９】
また、変換係数取得部１２０の詳細な動作は以下の通りである。
変換係数取得部１２０は、ｉに０の値を設定する（ステップＳ１６１）。次に、変換係数取得部１２０は、関数Ｔ（ｉ）について、
−２＾３１＋１≦Ｔ（ｉ）≦２＾３１−１
を満たすかどうかを判定し、満たさないならば（ステップＳ１６２）、処理を終了する。満たすならば（ステップＳ１６２）、
Ｔ（ｉ）＝ｔ＾４×ａ  （ｍｏｄ  ｐ）
となる変換係数ｔを算出し（ステップＳ１６３）、算出された変換係数ｔが有限体ＧＦ（ｐ）上の元であるかどうかを判定し、有限体ＧＦ（ｐ）上の元であるなら（ステップＳ１６４）、処理を終了する。有限体ＧＦ（ｐ）上の元でないなら（ステップＳ１６４）、ｉに１を加算し（ステップＳ１６５）、再度ステップＳ１６２へ制御を戻す。
【００５０】
次に、変換楕円曲線算出部１３０は、以下の動作をする。
変換楕円曲線算出部１３０は、有限体ＧＦ（ｐ）上に構成される変換楕円曲線Ｅｔのパラメータａ’＝ａ×ｔ＾４を算出し（ステップＳ１７１）、パラメータｂ’＝ｂ×ｔ＾６を算出する（ステップＳ１７２）。また、変換楕円曲線算出部１３０は、元Ｇに対応する変換楕円曲線Ｅｔ上の元Ｇｔ＝（ｘｔ０，ｙｔ０）として、ｘｔ０＝ｔ＾２×ｘ０を算出し（ステップＳ１７３）、ｙｔ０＝ｔ＾３×ｙ０を算出する（ステップＳ１７４）。
【００５１】
この従来の楕円曲線変換装置は、入力した楕円曲線をそれと同型な楕円曲線に変換している。ステップＳ１６４において、Ｔ（ｉ）＝−３とした時、式２３のｔがＧＦ（ｐ）の元である場合のみ、ｙ＾２＝ｘ＾３−３ｘ＋ｂの方程式をもつ楕円曲線に変換できる。
【００５２】
しかし、−３＝ａ×ｔ＾４となるためには、−３／ａのＧＦ（ｐ）における４乗根が存在しなければならない。任意のｘについて、ｘがＧＦ（ｐ）で２乗根が存在する確率は１／２であるので、４乗根が存在する確率は「２乗根の２乗根が存在する確率」であるから、１／２×１／２＝１／４である。従って、上記ｔがＧＦ（ｐ）の元である確率は、１／４と低く、ｙ＾２＝ｘ＾３−３ｘ＋ｂの方程式をもつ楕円曲線に必ずしも変換できないという問題点がある。
【００５３】
７．モンゴメリ型楕円曲線
上記の楕円曲線変換装置は、その方程式がｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂの形をしている楕円曲線だけを対象としている。このような楕円曲線はワイヤーシュトラス型楕円曲線と呼ばれる。
【００５４】
一方、方程式がＢ×ｙ＾２＝ｘ＾３＋Ａ×ｘ＾２＋ｘの形をしている楕円曲線をモンゴメリ型楕円曲線と呼ぶ。この楕円曲線は、点の加算や２倍算が高速であることが知られており、それぞれの計算量は、４Ｍｕｌ＋２Ｓｑ、３Ｍｕｌ＋２Ｓｑになる。上記５で述べたようにワイヤーシュトラス型楕円曲線の点の加算、２倍算の計算量は、それぞれ、１２Ｍｕｌ＋４Ｓｑ、４Ｍｕｌ＋６Ｓｑである。よって、モンゴメリ型楕円曲線の方が点の加算、２倍算が高速である（例えば、非特許文献３）。
【００５５】
一方、安全な楕円曲線を生成するための方法において、位数計算を行い、安全であるかを判定することによって安全な楕円曲線を生成することがある。ここでの位数計算で、使用する楕円曲線はワイヤーシュトラス型である。ゆえに、この方法で生成できる楕円曲線もワイヤーシュトラス型に限る。
【００５６】
上記従来の楕円曲線変換装置と同様の考え方で、楕円曲線の同型を利用することにより、ワイヤーシュトラス型楕円曲線からモンゴメリ型楕円曲線に変換することが考えられる。しかし、上記従来の楕円曲線変換装置においてａ＝−３を満たす楕円曲線を捜したのと同様で、必ずしも変換可能ではない。即ち、モンゴメリ型楕円曲線に変換できないワイヤーシュトラス型楕円曲線が存在する。上記のように同型を利用する場合は、文献「楕円曲線暗号演算の計算法について」（伊豆  哲也、ＳＣＩＳ’９９、２７５〜２８０ページ）より、ワイヤーシュトラス型楕円曲線からモンゴメリ楕円曲線に変換可能である確率は１９／４８程度であり、必ずしもモンゴメリ型楕円曲線に変換できないという問題点がある。
【００５７】
【特許文献１】
特許第３０５０３１３号公報
【００５８】
【非特許文献１】
ニイルコブリッツ著“ア  コウス  イン  ナンバア  セオリイ  アンド  クリプトグラヒイ“（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.)
【００６０】
【非特許文献３】
“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 Arithmetic of Elliptic Curves」（J.H.Silverman著、ＧＴＭ１０６、Springer-verlag、１９８６年）で詳述されている。
【００８９】
（楕円曲線の位数）
有限体Ｆ上の楕円曲線Ｅ上の点を（Ｘ、Ｙ）とする時、Ｘ、Ｙの両方の座標がＦに属する時、その点をＦ有理点という。Ｆ有理点全体に楕円曲線の群の零元Ｏを加えた集合をＥ（Ｆ）と書く。Ｅ（Ｆ）は楕円曲線の加算について群をなすことが知られている。Ｅ（Ｆ）の元の個数を楕円曲線の位数と呼ぶ。現在の楕円曲線暗号の安全性は、使用する楕円曲線の位数に依存している。即ち、有限体Ｆが同じ、かつ楕円曲線の位数が同じである楕円曲線同士は安全性が等しい。
【００９０】
（楕円曲線の同型）
有限体Ｆ上の楕円曲線Ｅの群Ｅ（Ｆ）と楕円曲線Ｅ’の群Ｅ’（Ｆ）が群準同型であり、１対１対応する場合、楕円曲線ＥとＥ’は「同型」であるという。Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂに対し、有限体Ｆの元ｃによって与えられる楕円曲線Ｅ’：ｙ＾２＝ｘ＾３＋ｃ＾４×ａ×ｘ＋ｃ＾６×ｂは、（ｘ，ｙ）→（ｃｘ，ｃｙ）によって同型であることがいえる。
【００９１】
（楕円曲線の同種）
有限体Ｆ上の楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂに対し、楕円曲線の位数がＥと同じである楕円曲線Ｅ’’をＥと同種な楕円曲線と呼ぶ。また、楕円曲線ＥとＥ’’が位数が等しい場合、楕円曲線ＥとＥ’’は同種であるという。同種については、上記文献でも触れられているが、特に、文献「Isogeny cycles and the Schoof-Elkies-Atkin algorithm」（J.-M.Couveignes，L.Dewaghe and F.Morain著，Research Report LIX/RR/96/03，Ecole Polytechnique-LIX，1996）で詳述されている。
【００９２】
（同種写像とモジュラー多項式）
同種同士の楕円曲線の間には、同種写像が存在する。同種写像φ：Ｅ→Ｅ’’において、Ｅ’’の零元Ｏ’’に上記写像によって移るＥ上の点の個数をＬとする時、φはＬ次同種写像とよび、楕円曲線ＥとＥ’’はＬ次同種であるという。楕円曲線ＥとＬ次同種な楕円曲線を求めるためにモジュラー多項式が使用できる。モジュラー多項式はＬのみに依存する２変数多項式である。楕円曲線変換装置２００内の楕円曲線生成部２１０によるステップＳ３０４からＳ３０８では、モジュラー多項式を用いて楕円曲線ＥＩとＬ次同種な楕円曲線を求めている。モジュラー多項式及びモジュラー多項式の求め方については、特に、文献「Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques」（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＝−３の楕円曲線）を生成し、ユーザＡ１〜Ａｎに提供したり、デジタル署名システムで使用される楕円曲線（例えば、モンゴメリ型楕円曲線）を生成し、ユーザＢ１〜Ｂｎに提供したりする。
【０１２９】
そして、安全性確保のために、例えば、一定期間を経過したときに、管理センタＣが、本発明に係る楕円曲線変換装置を用いて新たな楕円曲線を生成し、ユーザＡ１〜Ａｎ及びユーザＢ１〜Ｂｎに提供し、暗号通信システム及びデジタル署名システムで使用される楕円曲線を更新してもよい。また、ユーザＡ１〜Ａｎの装置が管理センタＣの楕円曲線変換装置に対して、それまで使用していた楕円曲線のパラメータ（ｐ，ａ，ｂ，ｍＥＩ）を通知し、そのパラメータを入力として管理センタＣの楕円曲線変換装置が新たな楕円曲線を生成し、ユーザＡ１〜Ａｎに返信してもよい。そして、ユーザＡ１〜Ａｎの装置は、管理センタＣの楕円曲線変換装置から返信されてきた新たな楕円曲線を用いて暗号通信を行うことにする。これによって、暗号の基盤となる楕円曲線が動的に変更される安全性の高い暗号システムが実現される。
【０１３０】
また、本発明は、上記に説明した楕円曲線変換装置を備える安全な楕円曲線のパラメータを生成する楕円曲線生成装置であってもよい。例えば、上記実施の形態における楕円曲線変換装置への入力パラメータのセットを一定手順で生成したり、複数の入力パラメータのセットを予め保持しておき、順次、楕円曲線変換装置に出力する入力パラメータ生成部を設けることで、その入力パラメータ生成部と楕円曲線変換装置とからなる楕円曲線生成装置を実現することができる。
【０１３１】
また、上記実施の形態における楕円曲線変換装置は、楕円曲線の条件として、ａ＝−３を満たす、あるいは、モンゴメリ型楕円曲線である、としているが、これら条件を満たす可能性のある条件、つまり、楕円曲線上での演算の計算量が削減されるという高速化条件であれば、どのようなものであってもよい。
【０１３２】
また、上記実施の形態における楕円曲線変換装置では、楕円曲線条件判定部によって一定の楕円曲線の条件が満たされないと判断された場合には、楕円曲線生成部による処理が繰り返されたが、このような繰り返し処理を行わず、何も出力しないようにしてもよい。また、一定回数を限度に繰り返すこととしてもよい。これによって、一定の時間制約の下での楕円曲線変換が可能となる。
【０１３３】
また、本発明は、本実施の形態における楕円曲線変換装置が備える特徴的な構成要素をステップとする楕円曲線変換方法として実現することもできる。
【０１３４】
【発明の効果】
以上に説明したように、本発明により、入力されたワイヤーシュトラス型楕円曲線に対して、その楕円曲線と同種な楕円曲線の中にａ＝−３を満たす楕円曲線、あるいは、モンゴメリ型楕円曲線が存在する限り、そのような楕円曲線に変換することができる。したがって、安全性を損なうことなく、より計算量が削減される楕円曲線を生成することが容易となり、楕円曲線を用いる暗号通信システム、電子署名システム、あるいは、鍵共有化システムに、特に、複数の楕円曲線を採用するシステムや楕円曲線を動的に変更するようなシステムに好適であり、高い安全性が要求される電子決済や秘密通信、デジタル著作物保護等の基盤技術として、その実用的価値は極めて大きい。
【図面の簡単な説明】
【図１】本発明の実施の形態１における楕円曲線変換装置の構成を示す機能ブロック図である。
【図２】同楕円曲線変換装置の動作を示すフローチャートである。
【図３】図２における楕円曲線生成部の処理（ステップＳ２０１）の詳細な手順を示すフローチャートの前半部である。
【図４】図２における楕円曲線生成部の処理（ステップＳ２０１）の詳細な手順を示すフローチャートの後半部である。
【図５】本発明の実施の形態２における楕円曲線変換装置の構成を示す機能ブロック図である。
【図６】同楕円曲線変換装置の動作を示すフローチャートである。
【図７】図６における楕円曲線生成部の処理（ステップＳ４０１）の詳細な手順を示すフローチャートの前半部である。
【図８】図６における楕円曲線生成部の処理（ステップＳ４０１）の詳細な手順を示すフローチャートの後半部である。
【図９】（ａ）は、従来の楕円曲線変換装置による楕円曲線の探索手法を示す図であり、（ｂ）は、本発明に係る楕円曲線変換装置による楕円曲線の探索手法を示す図である。
【図１０】本発明に係る楕円曲線変換装置の適用例を示す通信システムのシーケンス図である。
【図１１】エルガマル署名によるデジタル署名方式の手順を示すシーケンス図である。
【図１２】従来の楕円曲線変換装置のブロック図である。
【符号の説明】
２００    楕円曲線変換装置
２１０    楕円曲線生成部
２２０    楕円曲線条件判定部
２３０    楕円曲線出力部
４００    楕円曲線変換装置
４１０    楕円曲線生成部
４２０    楕円曲線条件判定部
４３０    楕円曲線出力部
【図１】
0004225764.tif 000003
【図２】
0004225764.tif 000004
【図３】
0004225764.tif 000005
【図４】
0004225764.tif 000006
【図５】
0004225764.tif 000007
【図６】
0004225764.tif 000008
【図７】
0004225764.tif 000009
【図８】
0004225764.tif 000010
【図９】
0004225764.tif 000011
【図１０】
0004225764.tif 000012
【図１１】
0004225764.tif 000013
【図１２】
0004225764.tif 000014