(57)【特許請求の範囲】
【請求項１】
楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号鍵生成装置において、
ｂ＝０とおいて、曲線の係数ａ＝±１を入力する手段と、
与えられた一組の合同式Ｕ≡３（ｍｏｄ ４）、Ｖ≡２（ｍｏｄ ４）を満たす乱数Ｕ，Ｖを生成する手段と、
これら乱数Ｕ，Ｖを用いてｐ＝Ｕ2＋Ｖ2を計算する手段と、
その計算したｐの素数判定を行う手段と、
ｑ＝（（Ｕ＋ａ）2 ＋Ｖ2 ）／（６−２ａ）を計算する手段と、その計算したｑの素数判定を行う手段と、
上記乱数生成、上記計算及び上記判定を繰り返す手段と、上記両判定が共に素数と判定した時のｐを出力する手段と、を有し、
π＝１（ｍｏｄｕｌｏ２＋２ｉ）〔π＝Ｕ＋Ｖｉ，ｉ＝√（−１）〕を満たすＵ，Ｖがそれぞれ満たす合同式の組が複数組定まり、当該合同式の組ごとに、当該合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓが満たす合同式が定まり、
上記与えられた一組の合同式をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数は、それ以外の何れかの上記合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数よりも確率的に大きいことを特徴とする楕円曲線暗号鍵生成装置。
【請求項２】
楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号鍵生成装置において、
ｂ＝０とおいて、｜ａ｜が平方数でない曲線の係数ａを入力する手段と、
与えられた一組の合同式Ｕ≡３（ｍｏｄ ４）かつＶ≡２（ｍｏｄ ４）またはＵ≡１（ｍｏｄ ４）かつＶ≡０（ｍｏｄ ４）を満たす乱数Ｕ，Ｖを生成する手段と、
これら生成された乱数Ｕ，Ｖにおいてｐ＝Ｕ2＋Ｖ2を計算する手段と、
その計算したｐの素数判定を行う手段と、
Ｕ，Ｖ，ａを入力してｒ＝（−ａ）(p-1)/4 （ｍｏｄｕｌｏ Ｕ＋Ｖｉ）を計算する手段と、
その計算結果についてｒ＝±ｉの真偽を判定する手段と、
ｒ，Ｕ，Ｖを入力して楕円曲線の位数Ｓを計算する手段と、
そのＳについてｑ＝Ｓ／２を計算する手段と、
その計算したｑの素数判定を行う手段と、
上記乱数生成、上記各計算、上記各判定を繰り返す手段と、
上記ｒ＝±ｉが真と判定され、かつｐ，ｑが共に素数と
判定されるとその時のｐを出力する手段と、を有し、
π＝１（ｍｏｄｕｌｏ２＋２ｉ）〔π＝Ｕ＋Ｖｉ，ｉ＝√（−１）〕を満たすＵ，Ｖがそれぞれ満たす合同式の組が複数組定まり、当該合同式の組ごとに、当該合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓが満たす合同式が定まり、
上記与えられた一組の合同式は、上記π＝１（ｍｏｄｕｌｏ２＋２ｉ）を満たすＵ，Ｖがそれぞれ満たす合同式の組の何れかであり、
上記与えられた一組の合同式をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数は、それ以外の何れかの上記合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数よりも確率的に大きいことを特徴とする楕円曲線暗号鍵生成装置。
【請求項３】
コンピュータを、乱数生成部とｐ計算部とｑ計算部と第１，２素数判定部と制御部とを有する楕円曲線暗号鍵生成装置として機能させて実行する、楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号の鍵生成方法において、
ｂ＝０とし、曲線の係数ａ＝±１が上記ｑ計算部に入力され、
上記乱数生成部が、与えられた一組の合同式Ｕ≡３（ｍｏｄ ４），Ｖ≡２（ｍｏｄ ４）を満たす乱数Ｕ，Ｖを生成し、
上記ｐ計算部が、ｐ＝Ｕ2＋Ｖ2を計算し、
上記第１素数判定部が、ｐが素数か否かを判定し、
上記ｑ計算部が、ｑ＝（（Ｕ＋ａ）2＋Ｖ2 ）／（６−２ａ）を計算し、
上記第２素数判定部が、ｑが素数か否かを判定し、
上記制御部が、上記乱数の生成、上記各計算、上記各判定を繰り返し実行させ、ｐ，ｑが共に素数と判定されるとその時のｐを出力し、
π＝１（ｍｏｄｕｌｏ２＋２ｉ）〔π＝Ｕ＋Ｖｉ，ｉ＝√（−１）〕を満たすＵ，Ｖがそれぞれ満たす合同式の組が複数組定まり、当該合同式の組ごとに、当該合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓが満たす合同式が定まり、
上記与えられた一組の合同式をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数は、それ以外の何れかの上記合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数よりも確率的に大きいことを特徴とする楕円曲線暗号鍵生成方法。
【請求項４】
コンピュータを、乱数生成部とｐ計算部とｒ計算部と第１，２素数判定部と真偽判定部と位数計算部と制御部とを有する楕円曲線暗号鍵生成装置として機能させて実行する、楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂ（ｍｏｄｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号の鍵生成方法において、
ｂ＝０とし、｜ａ｜が平方数でない係数ａが上記ｒ計算部に入力され、
上記乱数生成部が、与えられた一組の合同式Ｕ≡３（ｍｏｄ ４）かつＶ≡２（ｍｏｄ ４）、またはＵ≡１（ｍｏｄ ４）かつＶ≡０（ｍｏｄ ４）を満たす乱数Ｕ，Ｖを生成し、
上記ｐ計算部が、ｐ＝Ｕ2＋Ｖ2を計算し、
上記第１素数判定部が、ｐが素数か否かを判定し、
上記ｒ計算部が、ｒ＝（−ａ）(p-1)/4 （ｍｏｄｕｌｏ Ｕ＋Ｖｉ）を計算し、
上記真偽判定部が、ｒ＝±ｉか否かを判定し、
上記位数計算部が、ｒ，Ｕ，Ｖを用いて楕円曲線の位数を計算し、
上記第２素数判定部が、上記位数の１／２が素数か否かを判定し、
上記制御部が、上記乱数の生成、上記各計算、上記各判定を繰り返し実行させ、ｒ＝±ｉと判定され、かつ、ｐと位数の１／２が共に素数と判定されるとその時のｐを出力し、
π＝１（ｍｏｄｕｌｏ２＋２ｉ）〔π＝Ｕ＋Ｖｉ，ｉ＝√（−１）〕を満たすＵ，Ｖがそれぞれ満たす合同式の組が複数組定まり、当該合同式の組ごとに、当該合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓが満たす合同式が定まり、
上記与えられた一組の合同式は、上記π＝１（ｍｏｄｕｌｏ２＋２ｉ）を満たすＵ，Ｖがそれぞれ満たす合同式の組の何れかであり、
上記与えられた一組の合同式をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数は、それ以外の何れかの上記合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数よりも確率的に大きいことを特徴とする楕円曲線暗号鍵生成方法。
【請求項５】
請求項３又は４の楕円曲線暗号鍵生成方法の各手順をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は楕円曲線ｙ2 ＝ｘ3 ＋ａｘ＋ｂ（ｍｏｄ  ｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号の鍵生成装置、その生成方法及びプログラム記録媒体、に関するものである。
【０００２】
【従来の技術】
合同式ｙ2 ≡ｘ3 ＋ａｘ＋ｂ（ｍｏｄ  ｐ）を満たす点（ｘ，ｙ）の集合に無限遠点Ｏを加えた集合を楕円曲線と呼びＥp ［ａ，ｂ］と表す。ただしｐは２，３でない素数、４ａ3 ＋２７ｂ2 ≠０とする。Ｅp ［ａ，ｂ］の要素数（点の個数）を楕円曲線の位数と呼び＃Ｅp ［ａ，ｂ］と表す。安全な楕円曲線暗号を構成するためには＃Ｅp ［ａ，ｂ］が十分大きな素因数を持つようモジュラスｐ、曲線の係数（以下、係数）ａ，ｂを決める必要がある。これらｐ，ａ，ｂは楕円曲線暗号の鍵であり、鍵生成法として以下の二つが従来提案されていた。
（１）位数計算による方法
モジュラスｐと係数ａ，ｂを選び、これらより位数＃Ｅp ［ａ，ｂ］を計算する。＃Ｅp ［ａ，ｂ］が安全性の条件を満たすまで、以上を繰り返す。位数計算にはＳｃｈｏｏｆのアルゴリズム（Ｒ．Ｓｃｈｏｏｆ  “Ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ｏｖｅｒ  ｆｉｎｉｔｅ  ｆｉｅｌｄｓ  ａｎｄ  ｔｈｅ  ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  ｓｑｕａｒｅ  ｒｏｏｔｓ  ｍｏｄ  ｐ”，Ｍａｔｈ．Ｃｏｍｐ．，Ｖｏｌ．４４，Ｎｏ．１７０，ｐｐ．４８３−４９４（１９８５））等を用いる。
（２）虚数乗法に基づく方法
先に適切な位数とモジュラスｐを選び、曲線がその位数を持つよう係数ａ，ｂを計算する方法（例えばＡ．Ｏ．Ａｔｋｉｎ  ａｎｄ  Ｆ．Ｍｏｒａｉｎ，“Ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ａｎｄ  ｐｒｉｍａｌｉｔｙ  ｐｒｏｖｉｎｇ”，Ｍａｔｈ．Ｃｏｍｐ．Ｖｏｌ．６１，ｐｐ．２９−６８，（１９９３）等）。
【０００３】
（１）の特殊な場合として、Ｅp［ａ，０］やＥp［０，ｂ］を用いた方法がある。これらの曲線は位数計算が高速に行なえる。＃Ｅp［ａ，０］は以下の通りである。ｐ≡３（ｍｏｄ ４）のとき＃Ｅp［ａ，０］＝ｐ＋１となる。ただし位数がｐ＋１となる曲線を用いた楕円曲線暗号にはＭＯＶ−ｒｅｄｕｃｔｉｏｎによる攻撃が適用できるため、この曲線は用いない。またｐ≡１（ｍｏｄ ４）のとき＃Ｅp［ａ，０］＝ｐ＋１−（−ａ／π）4* π−（−ａ／π）4π* （１）となる（Ｉｒｅｌａｎｄ， Ｒｏｓｅｎ，“Ａ Ｃｌａｓｓｉｃａｌ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｍｏｄｅｒｎ Ｎｕｍｂｅｒ Ｔｈｅｏｒｙ”，２ｎｄ ｅｄ．Ｓｐｒｉｎｇｅｒ Ｖｅｒｌａｇ（ＧＴＭ８４））。ただしａ≠０，（ｘ／π）4 ＝ｘ(p-1)/4 （ｍｏｄｕｌｏ π）、またπ＝Ｕ＋Ｖｉはｐ＝ππ*＝Ｕ2＋Ｖ2 ，π≡１（ｍｏｄ ２＋２ｉ）を満たすものとする。ｉ＝√（−１）である。Ａ* はＡの複素共役を表す。
【０００４】
なお、整数ｍ，ｎによりｍ＋ｎｉと表せる数全体の集合をＺ［ｉ］と表す。整数と同様に、Ｚ［ｉ］上にも商と余りが定義できる。すなわちα，β∈Ｚ［ｉ］に対してα＝γβ＋δ，Ｎ（δ）＜Ｎ（β）を満たす商γと余りδがＺ［ｉ］の中に存在する。ここでＮ（δ）＝δδ* はδのノルムである。上記において「ｍｏｄｕｌｏ」はＺ［ｉ］上の割算による余りを表し、整数上の割算による余りを表す「ｍｏｄ」と区別する。ところで、
（−ａ／π）4 の値は｛ｉ，−１，−ｉ，１｝のいずれかと合同となる。よってｐ≡１（ｍｏｄ  ４）のとき位数＃Ｅp ［ａ，０］は（−ａ／π）4 の値により４通りのうちの１つに定まる。
【０００５】
【発明が解決しようとする課題】
従来方法（１）、（２）は鍵生成に多くの計算時間がかかることが問題であった。Ｅp ［ａ，０］を用いた方法は方法（１），（２）に比べて高速であるが、位数が大きな素因数を持つ曲線を効率的に生成する手順が明らかでなかった。
【０００６】
【課題を解決するための手段】
この発明は楕円曲線の係数ｂを０に限定した場合、安全な曲線を高速に生成する、つまり与えた係数ａに対して位数が大きな素因数を持つようモジュラスｐを決定する手段を提供する。
この発明の特徴は、モジュラスｐを選ぶ際に、ｐ＝Ｕ2 ＋Ｖ2 を満たすＵ，Ｖを先に決めることおよび以下に述べる位数がどのような約数をもつかについての考察に基づくことで、位数の最大素因数が大きな（安全な）曲線を効率的に見つけ出す点にある。
【０００７】
作用
位数を与える式（１）においてπ＝１（ｍｏｄｕｌｏ  ２＋２ｉ）の条件を満たすのは以下のいずれかである。
（Ｉ）Ｕ≡３（ｍｏｄ  ４）かつＶ≡２（ｍｏｄ  ４）
（II）Ｕ≡１（ｍｏｄ  ４）かつＶ≡０（ｍｏｄ  ４）
それぞれについて＃Ｅp ［ａ，０］は図１に示す合同式を満たす。
【０００８】
たとえば、（−ａ／π）4＝１かつ（Ｉ）の場合、＃Ｅp［ａ，０］＝ｐ＋１−２Ｕとなり＃Ｅp［ａ，０］は３２で割って８余る。すなわち８で割り切れる。このとき＃Ｅp［ａ，０］／８が素数なら位数の最大素因数が最も大きくなり、Ｅp［ａ，０］は（−ａ／π）4＝１かつ（Ｉ）の条件のもとで最も安全な曲線となる。他の場合も同様である。この発明は、Ｕ，Ｖをランダムに選び、ｐ＝Ｕ2＋Ｖ2が素数かつ位数の最大素因数が最大となるまでこれを繰り返すものである。
【０００９】
【発明の実施の形態】
実施例１
実施例１は曲線の係数ａを±１に限定した場合の鍵生成法である。ａ＝−１のとき、（−ａ／π）4 ＝（１／π）4 ＝１より、＃Ｅp ［−１，０］＝ｐ＋１−２Ｕ＝（Ｕ−１）2 ＋Ｖ2 となる。図１より（Ｉ）のとき８｜＃ＥP ［−１，０］（＃Ｅp ［−１，０］が８で割り切れることを表わす）となり、（II）のとき１６｜＃Ｅp ［−１，０］となる。
【００１０】
またａ＝１のとき、（−ａ／π）4 ＝（−１／π）4 ＝１−（ｐ−１ｍｏｄ８）／２。（Ｉ）のときＵ＝３（ｍｏｄ  ４）、Ｖ＝２（ｍｏｄ  ４）をｐ＝Ｕ2 ＋Ｖ2 に代入してｐ≡５（ｍｏｄ  ８）となり、このｐの値を（−１／π）4 ＝１−（ｐ−１ｍｏｄ  ８）／２に代入すると、（−１／π）4 ＝−１となる。よって＃Ｅp ［１，０］＝ｐ＋１＋２Ｕ＝（Ｕ＋１）2 ＋Ｖ2 となり、また４｜＃Ｅp ［１，０］である。（II）のときＵ＝１，Ｖ＝１をｐ＝Ｕ2 ＋Ｖ2 に代入してｐ≡１（ｍｏｄ  ８）となり、このｐを用いて（−１／π）4 ＝１−（ｐ−１ｍｏｄ  ８）／２に代入すると、（−１／π）４＝１となる。よって＃Ｅp ［１，０］＝ｐ＋１−２Ｕとなり、また１６｜＃Ｅp ［１，０］である。
【００１１】
以上よりａ＝＋１，ａ＝−１の何れの場合にも（II）より（Ｉ）のほうが位数の最大素因数を大きくできる。よって（Ｉ）からＵ，Ｖを選ぶと、ａ＝−１で＃Ｅp ［−１，０］＝（Ｕ−１）2 ＋Ｖ2 ，ａ＝１で＃Ｅp ［１，０］＝（Ｕ＋１）2 ＋Ｖ2 であるから、これらをまとめて＃Ｅp ［ａ，０］＝（Ｕ＋ａ）2 ＋Ｖ2 と表わせる。またａ＝−１の時、８｜＃Ｅp ［−１，０］であり、ａ＝１の時、４｜＃Ｅ［１，０］であるから、これらをまとめて（６−２ａ）｜＃Ｅp ［ａ，０］と表わせる。
【００１２】
図２は実施例１の機能構成図であり、処理手順は以下のとおりである。ａ（＝±１）を入力し、乱数生成部１１でＵ≡３（ｍｏｄ  ４），Ｖ≡２（ｍｏｄ  ４）を満たす乱数Ｕ，Ｖを生成し、Ｐ計算部１２でこれらＵ，Ｖについてｐ＝Ｕ2 ＋Ｖ2 を計算し、素数判定部１３でそのｐの素数判定を行ない、素数でなければ乱数生成部１１においてＵ，Ｖを再生成する。また位数計算部１４でＳ＝（Ｕ＋ａ）2 ＋Ｖ2 を計算し、ｑ計算部１５でその位数Ｓに対しｑ＝Ｓ／（６−２ａ）を計算し、素数判定部１６でｑの素数判定を行ない素数でなければ乱数生成部１１においてＵ，Ｖを再生成する。すなわち制御部１７で判定部１３，１６の判定結果に応じて乱数生成部１１よりＵ，Ｖを再生、各計算部１２，１４，１５の計算を行うことを繰返し、ｐ，ｑがともに素数ならばその時のｐを出力して終了する。
実施例２
実施例２は曲線の係数ａを、｜ａ｜が平方数とならないように選んだ場合の鍵生成法である。＃Ｅp ［ａ，０］は図１に示すように必ず２で割りきれる。したがって＃Ｅp ［ａ，０］が２と大きな素数の積になる場合が最も安全である。ところで｜ａ｜が平方数のときは（−ａ／（Ｕ＋Ｖｉ））4 ＝±１となり、＃Ｅp ［ａ，０］は４で割りきれるため最も安全な曲線にはならない。この理由により｜ａ｜が平方数となるようなａを除外する。
【００１３】
図３は実施例２の機能構成図であり、処理手順は以下のとおりである。｜ａ｜が平方数でないａを入力し、乱数生成部２１でＵ≡３（ｍｏｄ  ４）かつＶ≡２（ｍｏｄ  ４）、またはＵ≡１（ｍｏｄ  ４）かつＶ≡０（ｍｏｄ  ４）を満たす乱数Ｕ，Ｖを生成し、これらＵ，Ｖにおいてｐ計算部２２でｐ＝Ｕ2 ＋Ｖ2 を計算し、素数判定部２３でそのｐの素数判定を行ない、素数でなければ乱数生成部２１においてＵ，Ｖを再生成する。またｒ計算部２４でｒ＝（−ａ／（Ｕ＋Ｖｉ））4 を計算し、真偽判定部２５でそのｒについてｒ＝±ｉの真偽を判定し、偽なら乱数生成部２１においてＵ，Ｖを再生成する。また位数計算部２６でＳ＝＃Ｅp ［ａ，０］を計算し、ｑ計算部２７でｑ＝Ｓ／２を計算し、素数判定部２８でｑの素数判定を行ない素数でなければ乱数生成部２１においてＵ，Ｖを再生成する。すなわち制御部２９は判定部２３，２５，２８の判定結果に応じて乱数生成部２１、計算部２２，２４，２６，２７を繰り返し動作させ、判定部２５でｒ＝±ｉが真であり、かつ判定部２３，２８でｐ，ｑがともに素数であると判定すると、その時のｐを出力して終了する。なお処理の手順としてはｒ＝±ｉであるかを判定し、ｒ＝±ｉでなければＵ，Ｖを再生成し、ｒ＝±ｉならばｑが素数かを判定する。つまりｑが素数なら必ずｒ＝±ｉとなり、ｒ＝±ｉをまず判定することにより、ｑが素数であるかの判定が簡単かつ高速に行える。
【００１４】
上記実施例において各部の機能を、コンピュータによりプログラムを読出し、解読実行させることにより動作させることもできる。
【００１５】
【発明の効果】
鍵生成に必要な時間を比較すると、改良したＳｃｈｏｏｆアルゴリズムを用いた位数計算による方法が（ｌｏｇ  ｐ）7 のオーダ、虚数乗法に基づく方法が（ｌｏｇ  ｐ）6 のオーダ、この発明が（ｌｏｇ  ｐ）5 のオーダとなり、この発明が最も高速に鍵を生成できる。
【図面の簡単な説明】
【図１】Ｕ，Ｖと（−ａ／π）4 と位数との関係を示す図。
【図２】この発明の実施例１の機能構成図。
【図３】この発明の実施例２の機能構成図。
【図１】
0004344034.tif 000002
【図２】
0004344034.tif 000003
【図３】
0004344034.tif 000004