(57)【特許請求の範囲】
【請求項１】
楕円暗号における楕円曲線の生成装置であって、
入力される定義体情報に基づいて第１の楕円曲線を生成する楕円曲線候補生成部と、
前記生成された第１の楕円曲線が第２の楕円曲線に変換可能であるか否かを判定する変換可能判定部と、
前記第２の楕円曲線の曲線位数の８による整除性を判定する整除性判定部と、
前記第２の楕円曲線の曲線位数に関する情報を収集する曲線位数情報収集部と、
前記曲線位数の情報からコファクタの値を判定するコファクタ判定部とを有し、
前記第２の楕円曲線に変換可能であり、かつ変換可能な前記第２の楕円曲線の中でとりうるコファクタが最小の楕円曲線の曲線パラメータを出力することを特徴とする楕円曲線生成装置。
【請求項２】
請求の範囲第１項記載の楕円曲線生成装置であって、前記最小のコファクタが４であることを特徴とする楕円曲線生成装置。
【請求項３】
請求の範囲第１項記載の楕円曲線生成装置であって、前記第１の楕円曲線は標準型楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂであり、前記第２の楕円曲線は、モンゴメリ型楕円曲線ＢＹ２＝Ｘ３＋ＡＸ２＋Ｘであることを特徴とする楕円曲線生成装置。
【請求項４】
請求の範囲第３項記載の楕円曲線生成装置であって、前記変換可能判定部は、前記標準型楕円曲線についてｙ２＝ｆ（ｘ）とするときｆ（α）＝０となるαが前記の定義体に存在し、かつｆ（α）＝０となるαについてｆ（ｘ）のαにおける微分値ｆ‘（α）が平方根をもつかあるいは平方剰余である場合を変換可能と判定することを特徴とする楕円曲線生成装置。
【請求項５】
楕円暗号における楕円曲線の生成方法であって、
楕円曲線候補生成部は、入力される定義体情報に基づいて第１の楕円曲線を生成し、
変換可能判定部は、前記生成された第１の楕円曲線が第２の楕円曲線に変換可能であるか否かを判定し、
整除性判定部は、前記第２の楕円曲線の曲線位数の８による整除性を判定し、
曲線位数情報収集部は、前記第２の楕円曲線の曲線位数に関する情報を収集し、
コファクタ判定部は、前記曲線位数の情報からコファクタの値を判定し、
楕円曲線生成装置は、前記第２の楕円曲線に変換可能であり、かつ変換可能な前記第２の楕円曲線の中でとりうるコファクタが最小の楕円曲線の曲線パラメータを出力することを特徴とする楕円曲線生成方法。
【請求項６】
請求の範囲第５項記載の楕円曲線生成方法であって、前記最小のコファクタが４であることを特徴とする楕円曲線生成方法。
【請求項７】
請求の範囲第５項記載の楕円曲線生成方法であって、前記第１の楕円曲線は標準型楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂであり、前記第２の楕円曲線は、モンゴメリ型楕円曲線ＢＹ２＝Ｘ３＋ＡＸ２＋Ｘであることを特徴とする楕円曲線生成方法。
【請求項８】
請求の範囲第７項記載の楕円曲線生成方法であって、前記変換可能判定部は、前記標準型楕円曲線についてｙ２＝ｆ（ｘ）とするときｆ（α）＝０となるαが前記の定義体に存在し、かつｆ（α）＝０となるαについてｆ（ｘ）のαにおける微分値ｆ‘（α）が平方根をもつかあるいは平方剰余である場合を変換可能と判定することを特徴とする楕円曲線生成方法。
【請求項９】
コンピュータに、
入力される定義体情報に基づいて第１の楕円曲線を生成する機能と、
前記生成された第１の楕円曲線が第２の楕円曲線に変換可能であるか否かを判定する機能と、
前記第２の楕円曲線の曲線位数の８による整除性を判定する機能と、
前記第２の楕円曲線の曲線位数に関する情報に基づいてコファクタの値を判定する機能と、
前記第２の楕円曲線に変換可能であり、かつ変換可能な前記第２の楕円曲線の中でとりうるコファクタが最小の楕円曲線の曲線パラメータを出力する機能とを実現させるためのプログラムを格納した記録媒体。
【請求項１０】
請求の範囲第９項記載の記録媒体であって、前記最小のコファクタが４であることを特徴とするプログラムを格納した記録媒体。
【請求項１１】
請求の範囲第９項記載の記録媒体であって、前記第１の楕円曲線は標準型楕円曲線ｙ２＝ｘ３＋ａｘ＋ｂであり、前記第２の楕円曲線は、モンゴメリ型楕円曲線ＢＹ２＝Ｘ３＋ＡＸ２＋Ｘであることを特徴とするプログラムを格納した記録媒体。
【請求項１２】
請求の範囲第１１項記載の記録媒体であって、前記変換可能性を判定する機能は、前記標準型楕円曲線についてｙ２＝ｆ（ｘ）とするときｆ（α）＝０となるαが前記の定義体に存在し、かつｆ（α）＝０となるαについてｆ（ｘ）のαにおける微分値ｆ‘（α）が平方根をもつかあるいは平方剰余である場合を変換可能と判定することを特徴とするプログラムを格納した記録媒体。
【発明の詳細な説明】
技術分野
本発明はコンピュータネットワークにおけるセキュリティ技術に係り、特に楕円暗号において用いる楕円曲線の生成方法、楕円曲線の装置及び楕円暗号システム並びにその方法を格納した記録媒体に関する。
背景技術
楕円暗号において用いる楕円曲線として、標準型楕円曲線y2=f(x)、ただしf(x)=x3+ax+b(a,b∈Fp)、Fpは要素数がp個の有限体でpは大きな素数、を用いることがある。y02=f(x0)をみたす(x0,y0)の組(x0,y0∈Fp)を曲線上の点といい、それら点全体に無限遠点を付け加えた集合に演算を入れることができ、その点の個数を曲線位数という。曲線位数をnとしてn=clと正整数cと大きな素数lと表した時、cをコファクタといい、cの値が小さい時にその楕円曲線を安全という。安全な標準型楕円曲線の生成方法として、ランダムに標準型楕円曲線を生成しその曲線位数により安全性を判定し、安全となるまで標準型楕円曲線の再生成を行う方法がANSI X9.62.Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm(ECDSA),(1999)に記載されている。
また、モンゴメリ型楕円曲線
0003689039.tif 000002
を用いると標準型楕円曲線よりも高速に演算を実行できることがP.L.Montgomery,Speeding the Pollard and Elliptic Curve Methods of Factorization.Math.Comp.48(1987)243-264.に記載されている。標準型楕円曲線がモンゴメリ型楕円曲線に変換可能とは、標準型楕円曲線上の点とモンゴメリ型楕円曲線上の点とが１対１に対応し、それぞれにおける演算が一致することをいう。全ての標準型楕円曲線がモンゴメリ型楕円曲線に変換可能であるわけではない。伊豆哲也氏による「楕円曲線暗号演算の計算方法について」１９９９年暗号と情報セキュリティシンポジウム予稿集vol.1,(1999)275-280.には標準型楕円曲線からモンゴメリ型楕円曲線への変換が可能なための条件が記載されている。さらにモンゴメリ型楕円曲線の曲線位数が必ず４で割れることも上記資料に記載されている。
上記従来技術はモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の生成に関しては考慮されていなかった。そのためにモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成のためには、安全な標準型楕円曲線を生成した後に、それがモンゴメリ型楕円曲線に変換可能かどうかを判定し、変換不可能であれば安全な標準型楕円曲線を再生成し、変換可能となるまで繰り返すといった手順を踏まなければならなかった。一般的に、安全な標準型楕円曲線を生成する処理は、モンゴメリ型楕円曲線に変換可能かどうかを判定する処理より時間を要する。そのため上記性質を持った楕円曲線の生成には多大な時間を必要とし、ネットワークセキュリティを確保するための楕円暗号において、定期的に使用している楕円曲線を上記性質を持った新しい楕円曲線に置き換えることは難しかった。ここで、公開鍵を知らなくても楕円曲線のみを知っていれば攻撃のための前計算を行なえる攻撃法（Baby-Step-Giant-Step法）に対しては、楕円曲線を定期的に新しいものに置き換える以外に安全性を保つ方法は存在しないと言われている。したがって、従来技術を用いた場合は、特定楕円曲線に対する攻撃を受け易い状態にあった。
本発明の目的は演算の高速性及び安全性を向上させる楕円曲線生成方法、装置及び楕円暗号システム並びに記録媒体を提供することにある。
発明の開示
上記目的は、楕円曲線の生成方法であって、第１の楕円曲線（例えば、ｙ2＝ｘ3＋ａｘ＋ｂ）を生成するステップと、前記第１の楕円曲線が第２の楕円曲線（例えば、ＢＹ2＝Ｘ3＋ＡＸ2＋Ｘ）に変換可能であるかを判定するステップと、前記第２の楕円曲線に変換可能な第１の楕円曲線の安全性を判定するステップとを有することにより達成する。ここで第１の楕円曲線は、予め定められた素数位数の体上定義された第１の楕円曲線を用いても良い。また、前記第２の楕円曲線に変換可能であるかを判定するステップは、前記第１の楕円曲線ｙ2＝ｆ（ｘ）＝ｘ3＋ａｘ＋ｂに対して、ｆ（α）＝０となるαが存在するかを判定するステップと、ｆ（α）＝０となるαに対してｆ‘（α）が平方根を持つかを判定するステップとからなることにより達成する。また、前記第１の楕円曲線の安全性を判定するステップは、前記第１の楕円曲線の曲線位数に関する情報を抽出するステップと、前記曲線位数に関する情報からコファクタの判定を行うステップとを有することにより達成する。また、第１の楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂと第２の楕円曲線ｙ2＝ｘ3＋ａｒ2ｘ＋ｂｒ3とを生成するステップと、前記第１の楕円曲線が第３の楕円曲線ＢＹ2＝Ｘ3＋ＡＸ2＋Ｘに変換可能であるかを判定するステップと、前記第１の楕円曲線が前記第３の楕円曲線に変換可能である場合、前記第１の楕円曲線及び前記第２の楕円曲線の安全性を判定するステップとを有することにより達成する。また、楕円暗号における素体上定義された楕円曲線の生成方法であって、ランダムな標準型楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂを生成するステップと、前記生成された標準型楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂがモンゴメリ型楕円曲線ＢＹ2＝Ｘ3＋ＡＸ2＋Ｘに変換可能であるかを判定するステップと、前記楕円曲線の曲線位数の８による整除性を判定するステップと、前記楕円曲線の曲線位数に関する情報を収集するステップと、前記曲線位数の情報からコファクタの値を判定するステップとからなり、モンゴメリ型楕円曲線に変換可能であり且つコファクタが４である標準型楕円曲線を生成することにより達成する。
また、楕円曲線生成装置であって、第１の楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂを生成する楕円曲線候補生成部と、前記第１の楕円曲線が第２の楕円曲線ＢＹ2＝Ｘ3＋ＡＸ2＋Ｘに変換可能であるかを判定する変換可能判定部と、前記第２の楕円曲線に変換可能な第１の楕円曲線の安全性を判定する安全性判定部とを備えたことにより達成する。ここで、前記変換可能判定部は、前記第１の楕円曲線に対して、ｆ（α）＝０となるαが存在するかを判定する根存在判定部と、ｆ（α）＝０となるαに対してｆ‘（α）が平方根を持つかを判定する平方根判定部とからなることにより達成する。また、前記変換可能判定部は、前記第１の楕円曲線に対して、ｆ（α）＝０となるαが存在するかを判定する根存在判定部と、ｆ（α）＝０となるαに対してｆ‘（α）が平方剰余であるかを判定する平方剰余判定部とからなることにより達成する。また、第１の計算機と第２の計算機との間で暗号化通信を行う暗号システムで使用される楕円曲線生成装置であって、前記計算機から楕円曲線の生成要請を受け、モンゴメリ型楕円曲線に変換可能な標準型楕円曲線を生成することにより達成する。
また、楕円暗号を利用して暗号化通信を行う暗号システムであって、暗号化通信を受信する第１の計算機と、暗号化通信を送信する第２の計算機と、前記第１の計算機から楕円曲線の生成要請を受けて、モンゴメリ型楕円曲線に変換可能な標準型楕円曲線を生成する楕円曲線生成装置とを備えたことにより達成する。また、暗号化通信に使用している楕円曲線に置換の必要性があるか否かを管理する曲線置換管理装置を更に備え、前記楕円曲線に置換の必要性が生じた場合は、前記楕円曲線生成装置が新たに生成した楕円曲線に置換して暗号化通信を行うことにより達成する。尚、上記目的を達成するためには、上述した方法、装置及びシステムで実現している機能を実現するプログラムを格納した記録媒体であっても良い。
【図面の簡単な説明】
第１図は、本発明の第１実施例において楕円暗号システムにおける曲線パラメタ生成サーバ内での楕円曲線の生成方法及び装置における処理の流れを示す図である。第２図は、本発明の第１実施例を示す楕円曲線の生成方法及び装置におけるモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成方法を示すフローチャートである。第３図は、本発明の楕円曲線の生成方法及び装置内の変換可能判定部における標準型楕円曲線からモンゴメリ型楕円曲線に変換可能かの判定方法を示すフローチャートである。第４図は、本発明の第１、２実施例の応用例を示す楕円曲線の生成方法及び装置におけるモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成方法を示すフローチャートである。第５図は、本発明の第２実施例の楕円暗号システムにおける曲線パラメタ生成サーバ内での楕円曲線の生成方法及び装置における処理の流れを示す図である。第６図は、本発明の第２実施例を示す楕円曲線の生成方法及び装置におけるモンゴメリ型楕円曲線に変換可能であり且つコファクタが４である標準型楕円曲線の生成方法を示すフローチャートである。第７図は、本発明の第２実施例における楕円曲線パラメタ生成装置内でのモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の曲線位数に対する８による整除性の判定方法を示すフローチャートである。特に、定義体素数が４を法として１の場合の判定方法を示している。第８図は、本発明の第２実施例における楕円曲線パラメタ生成装置内でのモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の曲線位数に対する８による整除性の判定方法を示すフローチャートである。特に定義体素数が４を法として３の場合の判定方法を示している。第９図は、本発明の第２実施例で８による整除性の判定のための条件を列挙している表である。第１０図は、本発明の第３実施例の楕円暗号システムにおける曲線パラメタ生成サーバ内での楕円曲線の生成方法及び装置における処理の流れを示す図である。第１１図は、本発明の第３実施例を示す楕円曲線の生成方法及び装置におけるモンゴメリ型楕円曲線に変換可能であり且つコファクタが４である標準型楕円曲線の生成方法を示すフローチャートである。第１２図は、本発明の第３実施例における標準型楕円曲線に対する適当性判定方法を示すフローチャートである。特に、定義体素数が４を法として１の場合の判定方法を示している。第１３図は、本発明の第３実施例における標準型楕円曲線に対する適当性判定方法を示すフローチャートである。特に定義体素数が４を法として３の場合の判定方法を示している。第１４図は、本発明の楕円暗号システムの一例の構成図である。第１５図は、本発明の第４実施例における楕円暗号システムでの曲線生成方法に関するフローチャートである。第１６図は、本発明の第５実施例における楕円暗号システムの構成図である。第１７図は、本発明の第５実施例における楕円暗号システムでの曲線生成方法に関するフローチャートである。第１８図は、本発明の第６実施例における楕円暗号システムの構成図である。第１９図は、本発明の第６実施例における楕円暗号システムでの曲線生成方法に関するフローチャートである。第２０図は、本発明の第７実施例における楕円暗号システムの構成図である。第２１図は、本発明の第７実施例における楕円暗号システムでの曲線生成方法に関するフローチャートである。第２２図は、楕円曲線パラメタ生成装置内での標準型楕円曲線からモンゴメリ型楕円曲線への変換判定方法及び装置における処理の流れを示す図である。第２３図は、本発明の楕円暗号システムにおける曲線パラメタ変換装置での標準型楕円曲線からモンゴメリ型楕円曲線への変換における処理の流れを示す図である。第２４図は、曲線パラメタ変換方法を示すフローチャートである。第２５図は、本発明の楕円曲線パラメタ生成装置内での標準型楕円曲線からモンゴメリ型楕円曲線への変換可能判定方法及び装置における処理の流れを示す図である。第２６図は、標準型楕円曲線からモンゴメリ型楕円曲線への変換可能判定方法を示すフローチャートである。第２７図は、本発明の実施例におけるデータ構造である。第２８図は、曲線置換管理装置の一実施例を示す図である。第２９図は、曲線置換管理装置を公開鍵サーバに組み込んだ楕円暗号システムでの曲線パラメタ置換における処理の流れを示すシーケンス図である。
発明を実施するための最良の形態
以下、本発明の一実施例を図面により説明する。図１４は本発明が適用される楕円暗号システムの構成図の一例である。
まず、楕円曲線暗号システムを構成する曲線パラメタ生成サーバ内の楕円曲線パラメタ生成装置について図１、図２を用いて説明する。図１は楕円暗号システムにおける曲線パラメタ生成サーバ内でのモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成方法の第１実施例を示す図である。図２は第１実施例の楕円曲線パラメタ生成装置１０１における標準型楕円曲線の曲線パラメタの生成方法を示すフローチャートである。
楕円曲線パラメタ生成装置１０１では、定義体情報１０３を入力し、以下の手順により曲線パラメタ１０８を出力する。ここで定義体情報１０３は図２７における、定義体のビット長を含んだ定義体情報２７０１もしくは定義体素数を含んだ定義体情報２７０４で与えられている。楕円曲線候補生成部１０４において、定義体情報１０３よりランダムな標準型楕円曲線を生成する（ステップ２０１）。ランダムな標準型楕円曲線の生成方法についてはANSI X9.62,Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm(ECDSA),(1999)に記述されている。変換可能判定部１０２において楕円曲線候補生成部１０４で生成された標準型楕円曲線がモンゴメリ型楕円曲線に変換可能かの判定を行なう（ステップ２０２）。変換不可能であれば楕円曲線候補生成部１０４で標準型楕円曲線の再生成を行ない、変換可能となるまで繰り返す。曲線位数情報収集部１０７では変換可能判定部１０２によりモンゴメリ型楕円曲線に変換可能と判断された標準型楕円曲線の曲線位数に関する情報を収集する（ステップ２０４）。与えられた楕円曲線の曲線位数に関する情報を収集することにより曲線位数を決定する曲線位数決定方法についてはR.Schoof,Elliptic curves over finite fields and the computation of square roots mod p,Math.Comp.44(1985),483-494に記載されている。コファクタ判定部１０６では曲線位数情報収集部１０７により取得した曲線位数の情報からコファクタが安全性の条件より与えられる値より小さいかどうかを判定し（ステップ２０５）、コファクタの値が大きければ、楕円曲線候補生成部１０４により標準型楕円曲線の再生成を行ない、上記手順に従ってモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の曲線位数に関する情報から、再度コファクタ判定部１０６によりコファクタの値が小さいかどうかの判定を行ない、コファクタの値が小さいと判定されるまで以上の手順を繰り返す。コファクタの値が小さければ、上記手順により生成されたモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線を曲線パラメタとして出力を行なう（ステップ２０６）。
変換可能判定部１０２では以下の手順により標準型楕円曲線がモンゴメリ型楕円曲線に変換可能かを判定する。ここで、変換可能判定の一実施例を図３のフローチャートを用いて説明する。解の存在判定において標準型楕円曲線y2=f(x)=x3+ax+bに対してf(α)=0となるFpの元αが存在するかを調べる（ステップ３０１）。そのような元αが存在しなければ変換不可能と出力し終了する（ステップ３０４）。上記αが存在すれば、平方剰余判定により、f(α)=0となるαに対して、f'(α)がFpにおいて平方剰余となるαが存在するかを判定する（ステップ３０２）。そのようなαが存在すれば変換可能と出力し終了する（ステップ３０３）。そのようなαが存在しなければ変換不可能と出力して終了する（ステップ３０４）。ここで平方剰余とは素数pを法として平方根が存在する時をいい、存在しない場合は平方非剰余という。
以上の手順により変換可能の判定ができるということの根拠は以下の通りである。モンゴメリ型楕円曲線には(0,0)という２倍すると無限遠点となる点があり、標準型楕円曲線には一般的にはそのような点があるとは限らないので、変換可能となるためには、標準型楕円曲線上の点で、２倍すると無限遠点になる点の存在が必要である。一般にm倍して初めて無限遠点となる点のことを位数mの点という。f(α)=0となるαに対して、(α,0)は位数２の点である。変換可能とすれば、標準型楕円曲線上の位数２の点で、変換後に(0,0)へ移る点が必要であり、(α,0)がそのような点とした場合に、標準型楕円曲線の点からモンゴメリ型楕円曲線の点への変換は、あるs,t∈Fpに対してX=s(x-α),Y=ty(s≠0,t≠0)と表されなければならない。(X,Y)はモンゴメリ型楕円曲線上の点であるのでBY2=X3+AX2+Xをみたし、X,Yにそれぞれs(x-α),tyを代入すると、Bt2y2=s3(x-α)3+As2(x-α)2+s(x-α)となる。(x,y)は標準型楕円曲線上の点であるので、この式にy2=f(x)を代入するとBt2f(x)=s2(x-α)3+As2(x-α)2+s(x-α)となる。x3の項を比較することにより、Bt2=s3を得る。これを上の式に代入すると、s≠0であるから、s2f(x)=s2(x-α)3+As(x-α)2+(x-α)となる。この式をxで微分し、xにαを代入すると、s2f'(α)=1を得る。sはFpの元であるから、f'(α)は平方剰余でなければならない。またその時、A=3αs,B=s3/t2である。逆にf'(α)が平方剰余であれば、s=t=f'(α)-1/2,A=3αs,B=sとおけばモンゴメリ型楕円曲線BY2=X3+AX2+Xに変換可能である。
以上により、変換可能であるためには、モンゴメリ型楕円曲線及び標準型楕円曲線上のそれぞれ位数２の点がお互いに移りあうことが必要であることを基にして、上記手順により変換可能の判定を行なえることが示された。
またモンゴメリ型楕円曲線の曲線位数は４で割れることが次のようにして分かる。モンゴメリ型楕円曲線上の点(0,0)は位数２の点である。X2+AX+1の判別式A2-4が平方剰余であれば、X2+AX+1はFpにおいて根を持ち、したがって(0,0)以外に位数２の点が２つ存在するので曲線位数は４で割れる。A2-4が平方非剰余であれば、A+2及びA-2のうち一方のみが平方剰余であり他方は平方非剰余である。そのため（A+2)/B及び(A-2)/Bの一方が平方剰余となる。(A+2)/Bが平方剰余の場合はその平方根をγとして(1,±γ)が、(A-2)/Bが平方剰余の時はその平方根をγ'として(-1,±γ')がそれぞれ位数４の点となり、曲線位数は４で割れる。したがっていずれの場合においても曲線位数は４で割れる。
ここで、楕円曲線における演算速度は定義体の大きさに依存し、大きくなると遅くなる。楕円曲線の安全性は曲線位数に含まれる最大の素数の大きさに依存し、大きければ安全である。定義体の大きさを固定した時に、安全性を高くするためにはコファクタを小さくしなければならない。モンゴメリ型楕円曲線の曲線位数は４で割れるのでコファクタは４以上となり、定義体の大きさを固定してもっとも安全性を高めるにはコファクタは４にする必要がある。
尚、曲線位数を変換可能の判定条件に使わなければ、他の変換判定条件を用いることもできる。文献「楕円曲線暗号演算の計算方法について」１９９９年暗号と情報セキュリティシンポジウム予稿集vol.1,(1999)275-280.の２７８ページにはそのような方法が記載されている。
次に、図１４の楕円暗号システムにおける曲線パラメタ生成サーバ１４０１内でのモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成方法の第１実施例の応用例を図１、図４を用いて説明する。図４は、楕円曲線パラメタ生成装置１０１における標準型楕円曲線の曲線パラメタの生成方法を示すフローチャートである。
楕円曲線パラメタ生成装置１０１では、定義体情報１０３を入力し、以下の手順により曲線パラメタ１０８を出力する。ここで定義体情報１０３は図２７における、定義体のビット長を含んだ定義体情報２７０１もしくは定義体素数を含んだ定義体情報２７０４で与えられている。楕円曲線候補生成部１０４において、定義体情報１０３よりランダムな標準型楕円曲線を生成する（ステップ４０１）。標準型楕円曲線y2=f(x)=x3+ax+bに対して、標準型楕円曲線y2=fr(x)=x3+ar2x+br3を標準型楕円曲線y2=x3+ax+bのツイストという。ただし、rはFpにおいて平方非剰余な元である。ツイストに対して標準型楕円曲線y2=x3+ax+bを明示的にいう場合にはオリジナルという。変換可能判定部１０２において楕円曲線候補生成部１０４生成された標準型楕円曲線及びそのツイストの標準型楕円曲線がモンゴメリ型楕円曲線に変換可能かの判定を行なうステップ（４０２）。オリジナルの標準型楕円曲線が変換可能であればツイストの標準型楕円曲線も変換可能である。共に変換不可能であれば楕円曲線候補生成部１０４で標準型楕円曲線の再生成を行ない、変換可能となるまで繰り返す。曲線位数情報収集部１０７では変換可能判定部１０２によりモンゴメリ型楕円曲線に変換可能と判断されたオリジナル及びツイストの標準型楕円曲線の曲線位数に関する情報を収集する（ステップ４０３）。コファクタ判定部１０６では曲線位数情報収集部１０７により取得したオリジナル及びツイストの曲線位数の情報からそれぞれのコファクタが安全性の条件から与えられる値より小さいかどうかを判定し（ステップ４０４）、共にコファクタが大きければ、楕円曲線候補生成部１０４により標準型楕円曲線の再生成を行ない、上記手順に従ってモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の曲線位数に関する情報から、再度コファクタ判定部１０６によりそれぞれのコファクタが小さいかどうかの判定を行ない、いずれかのコファクタが小さいと判定されるまで以上の手順を繰り返す。いずれかのコファクタが小さければ、上記手順により生成されたモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線を曲線パラメタとして出力を行なう（ステップ４０５）。以上の応用例では、オリジナル及びツイストの標準型楕円曲線のモンゴメリ型楕円曲線への変換可能性の判定を一度に行うため、安定性判定を行う標準型楕円曲線の候補を増やせることとなり、更に曲線生成が高速化される。
オリジナルの標準型楕円曲線がモンゴメリ型楕円曲線に変換可能である時、そのツイストの標準型楕円曲線もモンゴメリ型楕円曲線に変換可能であることの根拠は以下の通りである。オリジナルの標準型楕円曲線がモンゴメリ型楕円曲線に変換可能であるので、f(α)=0且つf'(α)が平方剰余であるαが存在する。その時fr(rα)=0であり、fr(rα)=r2f'(α)であるのでfr'(rα)は平方剰余である。従ってツイストの標準型楕円曲線もモンゴメリ型楕円曲線に変換可能である。また、オリジナルの標準型楕円曲線はツイストの標準型楕円曲線のツイストであるため、ツイストの標準型楕円曲線がモンゴメリ型楕円曲線に変換可能であればオリジナルの楕円曲線もモンゴメリ型楕円曲線に変換可能である。オリジナルの標準型楕円曲線y2=x3+ax+bがモンゴメリ型楕円曲線BY2=x3+AX2+Xに変換される時、ツイストの標準型楕円曲線y2=x3+ar2x+br3はモンゴメリ型楕円曲線(B/r)Y2=X3+AX2+Xに変換される。
図５は楕円暗号システムにおける曲線パラメタ生成サーバ内でのモンゴメリ型楕円曲線に変換可能であり且つその曲線位数が４×素数である、すなわちコファクタが４である標準型楕円曲線の生成方法の第２実施例を示す図である。図６は、第２実施例における楕円曲線パラメタ生成装置５０１におけるモンゴメリ型楕円曲線に変換可能且つコファクタが４である標準型楕円曲線の曲線パラメタの生成方法を示すフローチャートである。上述したとおり、モンゴメリ型楕円曲線に変換可能であるとすると、曲線位数が４の倍数になる。そのうち、安全性を高くするためには、曲線位数が４×素数が望ましい。
楕円曲線パラメタ生成装置５０１では定義体情報５０３を入力し、以下の手順により曲線パラメタ５０８を出力する。ここで定義体情報５０３は図２７における、定義体のビット長を含んだ定義体情報２７０１もしくは定義体素数を含んだ定義体情報２７０４で与えられている。標準型楕円曲線候補生成物５０４において、定義体情報５０３よりランダムな標準型楕円曲線を生成する（ステップ６０１）。変換可能判定部５０２において楕円曲線候補生成部で生成された標準型楕円曲線がモンゴメリ型楕円曲線に変換可能かの判定を行なう（ステップ６０２）。変換不可能であれば標準型楕円曲線候補生成部５０４で標準型楕円曲線の再生成を行ない、変換可能となるまで繰り返す。８による整除性判定部５０５では変換可能判定部５０２によりモンゴメリ型楕円曲線に変換可能と判断された標準型楕円曲線の曲線位数が８で割れるかどうかを判定する（ステップ６０３）。上記楕円曲線の曲線位数が８で割れれば、楕円曲線候補生成部５０４により標準型楕円曲線の再生成を行ない、上記手順に従ってモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の曲線位数が８で割れるかの判定を行ない、曲線位数が８で割れないと判定されるまで以上の手順を繰り返す。曲線位数が８で割れなければ、曲線位数情報収集部５０７により、モンゴメリ型楕円曲線に変換可能であり且つその曲線位数が８で割れない標準型楕円曲線の、曲線位数に関する情報を収集する（ステップ６０４）。コファクタ判定部５０６では曲線位数情報収集部５０７により取得した曲線位数の情報からコファクタが４であるかを判定し（ステップ６０５）、コファクタが４を越えると判定されれば、楕円曲線候補生成部５０４により標準型楕円曲線の再生成を行ない、上記手順に従ってモンゴメリ型楕円曲線に変換可能であり且つその曲線位数が８で割れない標準型楕円曲線の曲線位数に関する情報から、再度コファクタ判定部５０６によりコファクタが４であるかの判定を行ない、コファクタが４と判断されるまで以上の手順を繰り返す。コファクタが４であれば、上記手順により生成されたモンゴメリ型楕円曲線に変換可能であり且つそのコファクタが４である標準型楕円曲線を曲線パラメタとして出力を行なう（ステップ６０６）。
８による整除性判定部５０５は、以下の手順によりモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の曲線位数が８で割れるかどうかを判定する。図７及び図８は第２実施例における８による整除性判定方法を示すフローチャートである。
ステップ７０１により定義体素数が４を法として１であるか３であるかに応じて以下の処理を振り分ける。定義体素数の４を法とした値が１であればステップ７０２へ、３であればステップ８０１へ行く。ステップ７０２において、f(x)=0のFpにおける根の数により処理を振り分ける。根の数が１個であればステップ７０４へ、３個であればステップ７０３へ行く。ステップ７０３において、(A+2)/BがFpにおいて平方剰余であるかを判定する。平方非剰余であれば曲線位数は８で割れる（ステップ７０５）。平方非剰余であれば曲線位数は８で割れない（ステップ７０６）。ステップ７０４においてf'(α)1/2がFpにおいて平方剰余であるかを判定する。平方剰余であれば曲線位数は８で割れない（ステップ７０６）。平方剰余であれば曲線位数は８で割れる（ステップ７０５）。以上により、定義体素数の４を法とする値が１の時に対して曲線位数が８で割れるかを判定できる。定義体素数の４を法とする値が３の場合は、ステップ８０１においてf(x)=0のFpにおける根の数により処理を振り分ける。根の数が１個であればステップ８０２へ、３個であれば曲線位数は８で割れる（ステップ７０５）。ステップ８０２において、A+2がFpにおいて平方剰余であるかを判定する。平方非剰余であれば曲線位数は８で割れない（ステップ７０６）。平方剰余であれば曲線位数は８で割れる（ステップ７０５）。以上により、定義体素数の４を法とする値が３の時に対して曲線位数が８で割れるかを判定できる。
以上の手順により、モンゴメリ型楕円曲線に変換可能な標準型楕円曲線の曲線位数に対する８による整除性の判定ができるということの根拠は以下の通りである。BY2=X3+AX2+Xを標準型楕円曲線から変換されたモンゴメリ型楕円曲線とする。まずf(x)=0のFpにおける根の数を１個とする。この時標準型楕円曲線上の点で位数が２であるものは(α,0)ただ一つである。モンゴメリ型楕円曲線上の位数２の点のx座標はX3+AX2+X=0のFp上での根であり、モンゴメリ型楕円曲線上の点(0,0)は標準型楕円曲線上の点(α,0)と対応するので、X2+AX+1=0はFpにおいて根を持たない。従ってその判別式A2-4はFpにおいて平方非剰余である。(A+2)/B乃至(A-2)/Bが平方剰余であれば、その平方根の１つをそれぞれγ,γ'とすれば、(1,±γ)もしくは(-1,±γ')が位数４の点となる。A2-4は平方非剰余であるので(A+2)/B及び(A-2)/Bのいずれか一方は平方剰余でなければならない。従ってこの場合に必ず位数４の点が存在する。
モンゴメリ型楕円曲線上のある点(u,v)がこの曲線上の他の点(w,z)の２倍点となると仮定する。点(w,z)における接線の式はY=((3w2+2Aw+1)/2Bz)(X-w)+zである。接線は(u,-v)で曲線と交わるので(X,Y)に(u,-v)を代入し、両辺に2Bzを掛けて２乗すると4Bv2Bz2=((3w2+2Aw+1)(u-w)+2Bz2)2となる。(w,z)及び(u,-v)は曲線上の点であるのでBz2=w3+Aw2+w及びBv2=u3+Au2+uをみたす。これを上式に代入すると4(u3+Ar2+u)(w3+Aw2+w)=((3w2+2Aw+1)(u-w)+2(w3+2Aw2+w))2となる。点(w,z)で曲線と接線は接していて、またwとuは異なるので、(u-w)2で割ることができ（3w2+2Aw+1)2-4(w3+Aw2+w)(u+A+2w)=0となる。wの式とみて整理するとw4-4uw3-(4Au+2)w2-4uw+1=0となり、w≠0なので、w2で割ってw+1/wの式とみて整理し直すと、(w+1/w)2-4u(w+1/w)-4(Au+1)=0となる。w∈Fpとすると1/w∈Fpであり、w+1/w∈Fpとなる。上の式がw+1/wの方程式としてFp上で根を持つためには、その判別式4(u2+Au+1)が平方剰余でなければならない。εをu2+Au+1の平方根の一つとするとw+1/w=2(u±ε)であり、この式がwの方程式としてFp上で根を持つためには、判別式(u±ε)2-1が平方剰余でなければならない。((u+ε)2-1)((u-ε)2-1)=u2(A2-4)であり、A2-4は平方非剰余であるので、(u+ε)2-1及び(u-ε)2-1のいずれか一方のみが平方剰余となる。その時
0003689039.tif 000003
であり、簡単のためδ=u±εとおくと、
0003689039.tif 000004
なので
0003689039.tif 000005
となり、z∈Fpであるためには(2δ+A)/Bが平方剰余でなければならない。また、この場合も同様に(2(u+ε)+A)(2(u-ε)+A)=A2-4であるから、(2(u+ε)+A)/Bもしくは(2(u-ε)+A)/Bのいずれか一方のみが平方剰余となる。上記平方剰余に関する２つの二者択一条件において、共に同じ符号をとれば、w,z∈Fpとなる。(u±ε)2-1=u(2(u±ε)A)と変形すると、((u±ε)2-1)((2(u±ε)+A)/B)=(u/B)(2(u±ε)+A)2となる。したがって、u/Bが平方剰余であれば、上記平方剰余に関する２つの二者択一条件において共に同じ符号をとることができ、２倍すると点(u,v)となる点(w,z)が存在する。以上をまとめるとu2+Au+1,u/Bが共に平方剰余であれば、２倍すると点(u,v)となる点(w,z)が存在する、ということが示された。
位数４の点のx座標は±1であり、したがって位数８の点の存在に関してはA±2,B,-1の平方剰余性により表すことができる。
-1が平方剰余であるのは定義体素数が４を法として１の時であり、-1が平方非剰余であるのは定義体素数が４を法として３の時である。f(x)=0の根の数が１個であるか３個であるかに応じて、A2-4が平方非剰余であるか平方剰余であるかが決まる。オリジナル及びツイストの曲線位数を加えると2(p+1)であるので、f(x)=0の根の数が３個の場合において、定義体素数が４を法として１の時は、オリジナルの曲線位数が８で割れればツイストの曲線位数は８で割れず、オリジナルの曲線位数が８で割れなければツイストの曲線位数は８で割れる。また、定義体素数が４を法として３の時は、オリジナルの曲線位数が８で割れればツイストの曲線位数も８で割れ、オリジナルの曲線位数が８で割れなければツイストの曲線位数も８で割れない。以上をまとめると図９の通りである。図９により、図７及び図８のフローチャートの手順で判定を行なえば、曲線位数の８による整除性を判定できる。
上記８による整除性判定方法において、ステップ８０２のA+2の平方剰余判定はA-2の平方剰余判定を用いても行なうことができる。f(x)=0の根の数が１個の場合はA2-4は平方非剰余なので、A+2が平方剰余であればA-2は平方非剰余であり、A+2が平方非剰余であればA-2は平方剰余であるので、A-2の平方剰余判定により判定可能である。ステップ７０３のA+2の平方剰余判定においても、f(x)=0の根の数が３個の場合はA2-4は平方剰余なので、(A+2)/Bが平方剰余であれば(A-2)/Bも平方剰余であり、(A+2)/Bが平方剰余であれば(A-2)/Bも平方非剰余であるので、(A-2)/Bの平方剰余判定により判定可能である。ステップ７０４のf'(α)1/2の平方剰余判定においても、f'(α)1/2とBの平方剰余性は一致するので、Bの平方剰余判定により判定可能である。尚、第２実施例では、コファクタが４の場合を最適な実施例として、８による整除性判定方法を用いたが、本発明はこれに限定されるわけではなく、曲線位数＝コファクタ×素数の関係から導き出される他の整数であっても良い。
また、第２実施例においても、その応用例として図４を用いて説明した第１実施例の応用例と同様の方法が適用できる。
次に標準型楕円曲線の生成方法の第３実施例を説明する。
図１０は楕円暗号システムにおける曲線パラメタ生成サーバ内でのモンゴメリ型楕円曲線に変換可能であり且つその曲線位数が４×素数である、すなわちコファクタが４である標準型楕円曲線の生成方法の第３実施例を示す図である。図１１は、第３実施例における楕円曲線パラメタ生成装置１００１におけるモンゴメリ型楕円曲線に変換可能且つコファクタが４である標準型楕円曲線の曲線パラメタの生成方法を示すフローチャートである。
楕円曲線パラメタ生成装置１００１では定義体情報１００３を入力し、以下の手順により曲線パラメタ１００８を出力する。ここで定義体情報１００３は図２７における、定義体のビット長を含んだ定義体情報２７０１もしくは定義体素数を含んだ定義体情報２７０４で与えられている。楕円曲線候補生成部１００４において、定義体情報１００３よりランダムな標準型楕円曲線を生成する（ステップ１１０１）。適当性判定部１００２において楕円曲線候補生成部で生成された標準型楕円曲線及びそのツイストの標準型楕円曲線がモンゴメリ型楕円曲線に変換可能となり且つそれぞれの曲線位数が８で割れるかの判定を行なう（ステップ１１０２）。変換不可能であったり、変換可能であってもオリジナル及びツイストの標準型楕円曲線の曲線位数が共に８で割れれば標準型楕円曲線候補生成部１００４で標準型楕円曲線の再生成を行ない、モンゴメリ型楕円曲線に変換可能であり且つオリジナル及びツイストの標準型楕円曲線の曲線位数のいずれか一方が８で割れないと判断されるまで繰り返す。モンゴメリ型楕円曲線に変換可能であり且つオリジナル及びツイストの標準型楕円曲線のいずれか一方の曲線位数が８で割れなければ、曲線位数情報収集部１００７により、モンゴメリ型楕円曲線に変換可能であり且つその曲線位数もしくはツイストの曲線位数が８で割れない標準型楕円曲線の、曲線位数に関する情報を収集する（ステップ１１０３）。コファクタ判定部１００６では曲線位数情報収集部１００７により取得した曲線位数の情報からコファクタが４であるかを判定し（ステップ１１０４）、コファクタが４を越えれば、楕円曲線候補生成部１００４により標準型楕円曲線の再生成を行ない、上記手順に従ってモンゴメリ型楕円曲線に変換可能であり且つその曲線位数が８で割れない標準型楕円曲線の曲線位数に関する情報から、再度コファクタ判定部１００６によりコファクタが４であるかの判定を行ない、コファクタが４と判断されるまで以上の手順を繰り返す。コファクタが４であれば、上記手順により生成されたモンゴメリ型楕円曲線に変換可能であり且つそのコファクタが４である標準型楕円曲線を曲線パラメタとして出力を行なう（ステップ１１０５）。
標準型楕円曲線に対する適当性判定部１００２は、与えられた標準型楕円曲線及びそのツイストの標準型楕円曲線が、モンゴメリ型楕円曲線に変換可能であり且つそれぞれの曲線位数が８で割れるかどうかを判定する。図１２及び図１３は第３実施例における標準型楕円曲線に対する適当性判定方法を示すフローチャートである。
ステップ１２０１により定義体素数が４を法として１であるか３であるかに応じて以下の処理を振り分ける。定義体素数の４を法とした値が１であればステップ１２０２へ、３であればステップ１３０１へ行く。ステップ１２０２において、f(x)=0のFpにおける根の数により処理を振り分ける。根の数が１個であればステップ１２０４へ、３個であればステップ１２０３へ行く。f(x)=0がFpにおいて根を持たなければ、オリジナル及びツイストの標準型楕円曲線は共にモンゴメリ型楕円曲線に変換不可能であり不適当（１２０９）である。ステップ１２０３において、f(α)=0となるαのうちf'(α)がFpにおいて平方剰余であるものを選択する。このαに関して標準型楕円曲線はモンゴメリ型楕円曲線に変換可能である。ステップ１２０５において、(A+2)/BがFpにおいて平方剰余であるかを判定する。平方剰余であればオリジナルの標準型楕円曲線の曲線位数は８で割れ、ツイストの標準型楕円曲線の曲線位数は８で割れないので、ツイストを選択する（ステップ１２０７）。平方非剰余であればツイストの標準型楕円曲線の曲線位数は８で割れ、オリジナルの標準型楕円曲線の曲線位数は８で割れないので、オリジナルを選択する（ステップ１２０８）。ステップ１２０４において、f'(α)がFpにおいて平方剰余であるかを判定する。平方非剰余であれば、オリジナル及びツイストの標準型楕円曲線は共にモンゴメリ型楕円曲線に変換不可能であり不適当（１２０９）である。平方剰余であればステップ１２０６へ行く。この場合、標準型楕円曲線はモンゴメリ型楕円曲線に変換可能である。ステップ１２０６においてf'(α)1/2がFpにおいて平方剰余であるかを判定する。平方非剰余であればツイストの標準型楕円曲線の曲線位数は８で割れ、オリジナルの標準型楕円曲線の曲線位数は８で割れないので、オリジナルを選択する（ステップ１２０８）。平方剰余であればオリジナルの標準型楕円曲線の曲線位数は８で割れ、ツイストの標準型楕円曲線の曲線位数は８で割れないので、ツイストを選択する（ステップ１２０７）。以上により、定義体素数の４を法とする値が１の時に対して、与えられたオリジナル及びツイストの標準型楕円曲線に対して、モンゴメリ型楕円曲線に変換可能であり且つ曲線位数が８で割れない標準型楕円曲線を選択する、あるいは不適当であるとして棄却するための判定を実行できる。定義体素数の４を法とする値が３の場合は、ステップ１３０１においてf(x)=0のFpにおける根の数により処理を振り分ける。根の数が１個であればステップ１３０２へ、３個もしくはf(x)=0がFpにおいて根を持たなければ、与えられたオリジナル及びツイストの標準型楕円曲線は共に変換不可能であったり変換可能であってもオリジナル及びツイストの曲線位数が共に８で割れるので不適当である（ステップ１２０９）。ステップ１３０２において、f'(α)がFpにおいて平方剰余であるかを判定する。平方非剰余であれば、オリジナル及びツイストの標準型楕円曲線は共に変換不可能であり不適当である（１２０９）。平方剰余であればステップ１３０３へ行く。この場合与えられたオリジナル及びツイストの標準型楕円曲線は共にモンゴメリ型楕円曲線に変換可能である。ステップ１３０３において、A+2がFpにおいて平方剰余であるかを判定する���平方非剰余であればオリジナル及びツイストの標準型楕円曲線の曲線位数は共に８で割れないので、オリジナル及びツイスト共に選択する（ステップ１３０５）。平方剰余であればオリジナル及びツイストの標準型楕円曲線の曲線位数は共に８で割れ、不適当である（ステップ１２０９）。以上により、定義体素数の４を法とする値が３の時に対して、与えられたオリジナル及びツイストの標準型楕円曲線に対して、モンゴメリ型楕円曲線に変換可能であり且つ曲線位数が８で割れない標準型楕円曲線を選択する、あるいは不適当であるとして棄却するための判定を実行できる。
以上の手順により、与えられたオリジナル及びツイストの標準型楕円曲線からモンゴメリ型楕円曲線に変換可能であり且つその曲線位数が８で割れない標準型楕円曲線を選択できる、あるいは不適当であるとして棄却できるということの根拠は以下の通りである。図１２及び図１３のフローチャートにおいて、前半は標準型楕円曲線がモンゴメリ型楕円曲線に変換可能であるかを判定しており、後半はモンゴメリ型楕円曲線に変換可能である標準型楕円曲線に対して、図９に基づき曲線位数が８で割れるかを判定している。オリジナルの標準型楕円曲線に対応するモンゴメリ型楕円曲線とツイストの標準型楕円曲線に対応するモンゴメリ型楕円曲線において、それぞれのY2の係数の平方剰余性は正反対になっていることに注意すればよい。ステップ１２０３においてf'(α)が平方剰余となるαが必ず選択できる事については、Δをf(x)の判別式とするとf(x)=0の根が３個の場合にΔは平方剰余であり、他方α,β,γをf(x)=0の根とするとΔ=-16f'(α)f'(β)f'(γ)であるので、f'(α),f'(β),f'(γ)のうち少なくとも１つは平方剰余である。
次に、図１４を用いて、モンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成装置を組み込んだ楕円暗号システムを第４実施例として説明する。
曲線パラメータ生成サーバ１４０１は第１実施例におけるモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成を行なう楕円曲線パラメタ生成装置１０１を組み込んだサーバである。コンピュータＡ１４０２はモンゴメリ型楕円曲線を利用した楕円暗号により暗号化通信を行なうための秘密鍵公開鍵の組の生成を行なおうとしているコンピュータである。公開鍵サーバ１４０３は各コンピュータの公開鍵の登録を行ない、問い合わせがあれば問い合わせ対象のコンピュータの公開鍵を送信する。コンピュータＢ１４０４はコンピュータＡ１４０２へモンゴメリ型楕円曲線を利用して楕円暗号により暗号化通信を行なおうとしているコンピュータである。
第４実施例における楕円暗号システムでは以下の手順により楕円曲線パラメタ生成装置を利用して暗号化通信を行なう。図１５はそのフローチャートである。コンピュータＡ１４０２は曲線パラメータ生成サーバ１４０１にモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成を要請する（ステップ１５０１）。曲線パラメタ生成サーバ１４０１は上記曲線の生成要請に基づき、定義体情報１０３を楕円曲線パラメタ生成装置１０１に与えて曲線パラメタ１０８を生成する（ステップ１５０２）。ここで定義体情報１０３は図２７における、定義体のビット長を含んだ定義体情報２７０１もしくは定義体素数を含んだ定義体情報２７０４で与えられている。新規曲線パラメタとして、モンゴメリ型楕円曲線に変換可能な標準型楕円曲線の定義式及び曲線位数、標準型楕円曲線を変換したモンゴメリ型楕円曲線の定義式、及び標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標をコンピュータＡ１４０２に渡す（ステップ１５０３）。コンピュータＡ１４０２は与えられた新規曲線パラメタから秘密鍵公開鍵の組を作成する（ステップ１５０４）。コンピュータＡ１４０２は公開鍵サーバ１４０３に上記作成した公開鍵を登録する（ステップ１５０５）。コンピュータＢ１４０４は公開鍵サーバ１４０３にコンピュータＡ１４０２の公開鍵の問い合わせを行なう（ステップ１５０６）。公開鍵サーバ１４０３はコンピュータＢ１４０４の公開鍵問い合わせに基づき、コンピュータＡ１４０２の公開鍵をコンピュータＢ１４０４に渡す（１５０７）。コンピュータＢ１４０４はコンピュータＡ１４０２の公開鍵を用いてモンゴメリ型楕円曲線を利用して暗号化を行ない、コンピュータＡに暗号化通信を行なう（ステップ１５０８）。
図１６はモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成装置を組み込んだ楕円暗号システムの第５実施例を示す図である。
曲線パラメタ生成サーバ１６０１は第１実施例におけるモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成を行なう楕円曲線パラメタ生成装置１０１を組み込んだサーバである。コンピュータＡ１６０２はモンゴメリ型楕円曲線を利用した楕円暗号により暗号化通信を行なうための秘密鍵公開鍵の組の生成を行なおうとしているコンピュータである。公開鍵サーバ１６０３は各コンピュータの公開鍵の登録を行ない、問い合わせがあれば問い合わせ対象のコンピュータの公開鍵を送信する。コンピュータＢ１６０４はコンピュータＡ１６０２へモンゴメリ型楕円曲線を利用して楕円暗号により暗号化通信を行なおうとしているコンピュータである。曲線パラメタ変換装置１６０５はモンゴメリ型楕円曲線に変換可能な標準型楕円曲線を与えるとその標準型楕円曲線に対応するモンゴメリ型楕円曲線及び標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標を出力するパラメタ変換装置である。
第５実施例における楕円暗号システムでは以下の手順により楕円曲線パラメタ生成装置を利用して暗号化通信を行なう。図１７はそのフローチャートである。コンピュータＡ１６０２は曲線パラメタ生成サーバ１６０１にモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成を要請する（ステップ１７０１）。曲線パラメタ生成サーバ１６０１は上記曲線の生成要請に基づき、定義体情報１０３を楕円曲線パラメタ生成装置１０１に与えて曲線パラメタ１０８を生成する（ステップ１７０２）。ここで定義体情報１０３は図２７における、定義体のビット長を含んだ定義体情報２７０１もしくは定義体素数を含んだ定義体情報２７０４で与えられている。新規曲線パラメタとして、モンゴメリ型楕円曲線に変換可能な標準型楕円曲線の定義式及び曲線位数をコンピュータＡ１６０２に渡す（ステップ１７０３）。コンピュータＡ１６０２は曲線パラメタ変換装置１６０５にモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の定義式を与え、曲線パラメタ変換装置からモンゴメリ型楕円曲線に変換可能な標準型楕円曲線を変換したモンゴメリ型楕円曲線の定義式及び標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標を受け取る（ステップ１７０４）。コンピュータＡ１６０２は上記曲線パラメタから秘密鍵公開鍵の組を作成する（ステップ１７０５）。コンピュータＡ１６０２は公開鍵サーバ１６０３に上記作成した公開鍵を登録する（ステップ１７０６）。コンピュータＢ１６０４は公開鍵サーバ１６０３にコンピュータＡ１６０２の公開鍵の問い合わせを行なう（ステップ１７０７）。公開鍵サーバ１６０３はコンピュータＢ１６０４の公開鍵問い合わせに基づき、コンピュータＡ１６０２の公開鍵をコンピュータＢ１６０４に渡す（ステップ１７０８）。コンピュータＢ１６０４はコンピュータＡ１６０２の公開鍵を用いてモンゴメリ型楕円曲線を利用して暗号化を行ない、コンピュータＡに暗号化通信を行なう（ステップ１７０９）。
図１８はモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成装置を組み込んだ楕円暗号システムの第６実施例を示す図である。
曲線パラメタ生成サーバ１８０１は第１実施例におけるモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成を行なう楕円曲線パラメタ生成装置１０１を組み込んだサーバである。コンピュータＡ１８０２はモンゴメリ型楕円曲線を利用した楕円暗号により暗号化通信を行なうための秘密鍵公開鍵の組の生成を行なおうとしているコンピュータである。公開鍵サーバ１８０３は各コンピュータの公開鍵の登録を行ない、問い合わせがあれば問い合わせ対象のコンピュータの公開鍵を送信する。コンピュータＢ１８０４はコンピュータＡ１８０２へモンゴメリ型楕円曲線を利用して楕円暗号により暗号化通信を行なおうとしているコンピュータである。曲線パラメタ変換装置１８０５はモンゴメリ型楕円曲線に変換可能な標準型楕円曲線を与えるとその標準型楕円曲線に対応するモンゴメリ型楕円曲線及び標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標を出力するパラメタ変換装置である。
第６実施例における楕円暗号システムでは以下の手順により楕円曲線パラメタ生成装置を利用して暗号化通信を行なう。図１９はそのフローチャートである。コンピュータＡ１８０２は曲線パラメタ生成サーバ１８０１にモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成を要請する（ステップ１９０１）。曲線パラメタ生成サーバ１８０１は上記曲線の生成要請に基づき、定義体情報１０３を楕円曲線パラメタ生成装置１０１に与えて曲線パラメタ１０８を生成する（ステップ１９０２）。ここで定義体情報１０３は図２７における、定義体のビット長を含んだ定義体情報２７０１もしくは定義体素数を含んだ定義体情報２７０４で与えられている。新規曲線パラメタとして、モンゴメリ型楕円曲線に変換可能な標準型楕円曲線の定義式及び曲線位数をコンピュータＡ１８０２に渡す（ステップ１９０３）。コンピュータＡ１８０２は上記曲線パラメタから秘密鍵公開鍵の組を作成する（ステップ１９０４）。コンピュータＡは公開鍵サーバ１８０３に上記作成した公開鍵を登録する（ステップ１９０５）。公開鍵サーバ１８０３は曲線パラメタ変換装置１８０５にコンピュータＡ１８０２の公開鍵に関するモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の定義式を与え、曲線パラメタ変換装置から上記モンゴメリ型楕円曲線に変換可能な標準型楕円曲線を変換したモンゴメリ型楕円曲線の定義式及び標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標を受け取り、コンピュータＡ１８０２の公開鍵の情報として加える（ステップ１９０６）。コンピュータＢ１８０４は公開鍵サーバ１８０３にコンピュータＡ１８０２の公開鍵の問い合わせを行なう（ステップ１９０７）。公開鍵サーバ１８０３はコンピュータＢ１８０４の公開鍵問い合わせに基づき、コンピュータＡ１８０２の公開鍵をコンピュータＢ１８０４に渡す（ステップ１９０８）。コンピュータＢ１８０４はコンピュータＡ１８０２の公開鍵を用いてモンゴメリ型楕円曲線を利用して暗号化を行ない、コンピュータＡ１８０２に暗号化通信を行なう（ステップ１９０９）。尚、ステップ１９０６とステップ１９０７は、その順番を問わず、コンピュータＢ１８０４が公開鍵サーバ１８０３にコンピュータＡ１８０２の公開鍵を問い合わせた後に、公開鍵サーバ１８０３が曲線パラメタ変換装置１８０５に標準型楕円曲線をモンゴメリ型楕円曲線に変換するよう要請しても良い。
図２０はモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成装置を組み込んだ楕円暗号システムの第７実施例を示す図である。
曲線パラメタ生成サーバ２００１は第１実施例におけるモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成を行なう楕円曲線パラメタ生成装置１０１を組み込んだサーバである。コンピュータＡ２００２はモンゴメリ型楕円曲線を利用した楕円暗号により暗号化通信を行なうための秘密鍵公開鍵の組の生成を行なおうとしているコンピュータである。公開鍵サーバ２００３は各コンピュータの公開鍵の登録を行ない、問い合わせがあれば問い合わせ対象のコンピュータの公開鍵を送信する。コンピュータＢ２００４はコンピュータＡ２００２へモンゴメリ型楕円曲線を利用して楕円暗号により暗号化通信を行なおうとしているコンピュータである。曲線パラメタ変換装置２００５はモンゴメリ型楕円曲線に変換可能な標準型楕円曲線を与えるとその標準型楕円曲線に対応するモンゴメリ型楕円曲線及び標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標を出力するパラメタ変換装置である。
第７実施例における楕円暗号システムでは以下の手順により楕円曲線パラメタ生成装置を利用して暗号化通信を行なう。図２１はそのフローチャートである。コンピュータＡ２００２は曲線パラメタ生成サーバ２００１にモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成を要請する（ステップ２１０１）。曲線パラメタ生成サーバ２００１は上記曲線の生成要請に基づき、定義体情報１０３を楕円曲線パラメタ生成装置１０１に与えて曲線パラメタ１０８を生成する（ステップ２１０）。ここで定義体情報１０３は図２７における、定義体のビット長を含んだ定義体情報２７０１もしくは定義体素数を含んだ定義体情報２７０４で与えられている。新規曲線パラメタとして、モンゴメリ型楕円曲線に変換可能な標準型楕円曲線の定義式及び曲線位数をコンピュータＡ２００２に渡す（ステップ２１０３）。コンピュータＡ２００２は上記曲線パラメタから秘密鍵公開鍵の組を作成する（ステップ２１０４）。コンピュータＡ２００２は公開鍵サーバ２００３に上記作成した公開鍵を登録する（ステップ２１０５）。コンピュータＢ２００４は公開鍵サーバ２００３にコンピュータＡ２００２の公開鍵の問い合わせを行なう（ステップ２１０６）。公開鍵サーバ２００３はコンピュータＢ２００４の公開鍵問い合わせに基づき、コンピュータＡ２００２の公開鍵をコンピュータＢ２００４に渡す（ステップ２１０７）。コンピュータＢは曲線パラメタ変換装置２００５にコンピュータＡ２００２の公開鍵に関するモンゴメリ型楕円曲線に変換可能な標準型楕円曲線の定数式を与え、曲線パラメタ変換装置から上記モンゴメリ型楕円曲線に変換可能な標準型楕円曲線を変換したモンゴメリ型楕円曲線の定義式及び標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標を受け取り、コンピュータＡ２００２の公開鍵の情報として加える（ステップ２１０８）。コンピュータＢ２００４はコンピュータＡ２００２の公開鍵を用いてモンゴメリ型楕円曲線を利用して暗号化を行ない、コンピュータＡに暗号化通信を行なう（ステップ２１０９）。
図２２はモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成装置における標準型楕円曲線からモンゴメリ型楕円曲線への変換可能判定を行なう変換可能判定装置の一実施例を示す図である。変換可能判定装置２２０１は根存在判定部２２０２及び平方剰余判定部２２０３を用いて与えられた標準型楕円曲線がモンゴメリ型楕円曲線に変換可能であるかを判定する。根存在判定部２２０２ではf(x)=0がFpにおいて根を持つか判定する。平方剰余判定部２２０３でf'(α)が平方非剰余であると判定された根以外に根が存在しなければ変換不可能と出力する。根が存在すれば根を平方剰余判定部２２０３に与える。平方剰余判定部２２０３ではf(α)=0となるαに対して、f'(α)がFpにおいて平方剰余であるかを判定する。平方剰余であれば変換可能と出力する。平方非剰余であれば根存在判定部に他の根が存在するかを問い合わせる。変換可能判定装置２２０１では以下の手順により、標準型楕円曲線がモンゴメリ型楕円曲線に変換可能かを判定する。図３のフローチャートを用いて説明する。ステップ３０１において標準型楕円曲線y2=f(x)=x3+ax+bに対してf(α)=0となるFpの元αが存在するかを調べる。そのような元αが存在しなければ変換不可能３０４と出力し終了する。上記αが存在すれば、ステップ３０２により、f(α)=0となるαに対して、平方剰余判定部２２０３によりf'(α)がFpにおいて平方剰余かを判定し、その結果が平方剰余となるαが存在するかを判定する。そのようなαが存在すれば変換可能３０３と出力し終了する。そのようなαが存在しなければ変換不可能３０４と出力して終了する。
図２３は図１６、図１８、図２０のモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成装置を組み込んだ楕円暗号システムにおける曲線パラメタ変換装置の一実施例を示す図である。
曲線パラメタ変換装置２３０１は根計算部２３０３、平方剰余判定部２３０２及び曲線パラメタ構成部２３０４を用いて、与えられたモンゴメリ型楕円曲線に変換可能な標準型楕円曲線から対応するモンゴメリ型楕円曲線及び点変換パラメタとして標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標を計算し出力する。根計算部２３０３ではf(x)=0のFpにおける根αを求める。平方剰余判定部２３０２では根計算部２３０３で求めたαに対して、f'(α)がFpにおいて平方剰余であるかを判定する。曲線パラメタ構成部２３０４では根計算部２３０３で求めたαからモンゴメリ型楕円曲線を構成する。
曲線パラメタ変換装置２３０１では以下の手順により、モンゴメリ型楕円曲線に変換可能な標準型楕円曲線から変換されたモンゴメリ型楕円曲線及び標準型楕円曲線上の位数２の点でモンゴメリ型楕円曲線上の点(0,0)に対応する点のx座標を計算する。図２４のフローチャートを用いて説明する。ステップ２４０１により、f(x)=0のFpにおける根αを求める。ステップ２４０３においてf'(α)がFpにおいて平方剰余であるかを判定する。平方剰余であればステップ２４０４へ行く。平方非剰余であれば、ステップ２４０２によりf(x)=0の根でステップ２４０３でf'(α)が平方非剰余と分かった根α以外の根を求める。その根を新たにαとする。そのαに対して再度ステップ２４０３でf'(α)がFpにおいて平方剰余であるかを判定する。f(x)=0の根は高々３個しかなく、またモンゴメリ型楕円曲線に変換可能であることが分かっているので、３回繰り返すうちにf'(α)が平方剰余と判定されステップ２４０４へ進む。ステップ２４０４において、s=f'(α)-1/2を計算する。ステップ２４０５において、B=s,A=3αsを計算する。ステップ２４０６において、A,B,αを出力する。
このような曲線パラメタ変換装置により、図２７の標準型楕円曲線のみで与えられた曲線パラメタ２７０２を対応するモンゴメリ型楕円曲線のデータを付け加えた曲線パラメタ２７０５に、標準型楕円曲線のみで与えられた公開鍵２７０３を対応するモンゴメリ型楕円曲線のデータを付け加えた公開鍵２７０６に変換できる。
図２５はFpの拡大体Fq上定義された、モンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成装置における標準型楕円曲線からモンゴメリ型楕円曲線への変換可能判定を行なう変換可能判定装置の一実施例を示す図である。
変換可能判定装置２５０１は根存在判定部２５０２及び平方根判定部２５０３を用いて、与えられたFq上定義された標準型楕円曲線がモンゴメリ型楕円曲線に変換可能であるかを判定する。根存在判定部２５０２ではf(x)=0がFqにおいて根を持つか判定する。平方根判定部２５０３でf'(α)が平方非剰余であると判定された根以外に根が存在しなければ変換不可能と出力する。根が存在すれば根を平方根判定部２５０３に与える。平方根判定部２５０３ではf(α)=0となるαに対して、f'(α)がFqにおいて平方根を持つかを判定する。平方根を持てば変換可能と出力する。平方根を持たなければ根存在判定部にf(x)=0の他の根が存在するかを問い合わせる。
変換可能判定装置２５０１では以下の手順により、Fq上定義された標準型楕円曲線がモンゴメリ型楕円曲線に変換可能かを判定する。図２６のフローチャートを用いて説明する。ステップ２６０１において標準型楕円曲線y2=f(x)=x3+ax+bに対してf(α)=0となるFqの元αが存在するかを調べる。そのような元αが存在しなければ変換不可能２６０４と出力し終了する。上記αが存在すれば、ステップ２６０２により、f(α)=0となるαに対して、平方根判定部２５０３によりf'(α)がFqにおいて平方根を持つかを判定し、その結果が平方根を持つαが存在するかを判定する。そのようなαが存在すれば変換可能２６０３と出力し終了する。そのようなαが存在しなければ変換不可能２６０４と出力して終了する。
図２８はモンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成装置を組み込んだ楕円暗号システムにおいて公開鍵サーバ、コンピュータＡ乃至はコンピュータＢに組み込むための曲線置換管理装置の実施例を示す図である。
曲線置換管理装置２８０１は、判定曲線選択部２８０２、曲線置換判定部２８０３及び鍵テーブル２８０４を含む。鍵テーブル２８０４は曲線パラメタ及び公開鍵を含むデータテーブルである。
判定曲線選択部２８０２は指定時間もしくは一定時間毎に起動し、鍵テーブル２８０４より曲線パラメタを選択する。選択した曲線パラメタを曲線置換判定部２８０３に送る。曲線置換判定部２８０３は受け取った曲線パラメタに対して、曲線パラメタが作成された時間もしくはその曲線パラメタの利用者の数が、それぞれ安全性を保つために必要となる値よりも古いもしくは多い時に、与えられた曲線パラメタを新規の曲線パラメタに置換する必要があると出力する。
図２９は図２８の曲線置換管理装置を公開鍵サーバに組み込んだ場合における処理の流れを示すシーケンス図である。
曲線置換管理装置２９０３は曲線パラメタ置換要請を公開鍵サーバ２９０２に送る。公開鍵サーバ２９０２は曲線置換管理装置２９０３からの曲線パラメタ置換要請に基づき、曲線パラメタ生成要請を曲線パラメタ生成サーバ２９０１に送る。曲線パラメタ生成サーバ２９０１は公開鍵サーバ２９０２からの曲線パラメタ生成要請に基づき、新規曲線パラメタを生成し、新規曲線パラメタを公開鍵サーバ２９０２に送る。公開鍵サーバ２９０２は曲線パラメタを曲線パラメタ生成サーバ２９０１から受け取った新規曲線パラメタに置き換える。公開鍵サーバ２９０２は、以前の曲線パラメタを利用しているコンピュータＡ２９０４に、新規曲線パラメタとともに新規公開鍵登録要請を送る。コンピュータＡ２９０４は、公開鍵サーバ２９０２からの新規公開鍵登録要請に基づき、受け取った新規曲線パラメタに対する秘密鍵公開鍵の組の生成を行なう。コンピュータＡ２９０４は生成した公開鍵を公開鍵サーバ２９０２に登録する。
以上述べたように本発明によれば、モンゴメリ型楕円曲線に変換可能であり且つ安全な標準型楕円曲線の生成において、安全な標準型楕円曲線の再生成を省くことができるので、上記性質を持った楕円曲線の生成にかかるコストを削減できる。暗号に利用する楕円曲線を定期的に上記性質を持つ新しい楕円曲線に置き換えることにより特定楕円曲線に対する攻撃を未然に防ぐ事ができ、さらにモンゴメリ型楕円曲線に変換可能であることからデータの暗号化復号化における時間を標準型楕円曲線を用いた場合よりも短縮することができる。
産業上の利用可能性
以上のとおり、本発明は、コンピュータネットワークにおけるセキュリティを行う上で有用であり、特に楕円暗号を用いたセキュリティ管理をおこなう環境に用いるのに適している。
【図１】
0003689039.tif 000006
【図２】
0003689039.tif 000007
【図３】
0003689039.tif 000008
【図４】
0003689039.tif 000009
【図５】
0003689039.tif 000010
【図６】
0003689039.tif 000011
【図７】
0003689039.tif 000012
【図８】
0003689039.tif 000013
【図９】
0003689039.tif 000014
【図１０】
0003689039.tif 000015
【図１１】
0003689039.tif 000016
【図１２】
0003689039.tif 000017
【図１３】
0003689039.tif 000018
【図１４】
0003689039.tif 000019
【図１５】
0003689039.tif 000020
【図１６】
0003689039.tif 000021
【図１７】
0003689039.tif 000022
【図１８】
0003689039.tif 000023
【図１９】
0003689039.tif 000024
【図２０】
0003689039.tif 000025
【図２１】
0003689039.tif 000026
【図２２】
0003689039.tif 000027
【図２３】
0003689039.tif 000028
【図２４】
0003689039.tif 000029
【図２５】
0003689039.tif 000030
【図２６】
0003689039.tif 000031
【図２７】
0003689039.tif 000032
【図２８】
0003689039.tif 000033
【図２９】
0003689039.tif 000034