カスタム静的ディフィ−ヘルマン（Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）群
【課題】敵対者による能動攻撃を阻止する静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルに対する群を選択する方法を提供すること。
【解決手段】ｍｏｄ ｐ群において、偶数ｈが約（９／１６）（ｌｏｇ2ｎ）2の値として選択され、値ｒとｎは、ｒとｎに対するふるいと素数性テストを使用して判定され、値ｔが、ｐが素数の場合に、ｐ＝ｔｎ＋１を計算するために見出される。二進数体上で定義された楕円曲線群において、任意の曲線が選択され、曲線上の点の数がカウントされ、この数が、ｎが素数の場合の２ｎの値であるかが調べられ、ｎ−１が好ましい基準に適合するかが調べられる。位数ｑの素数体上で定義された楕円曲線群において、ｎが素数であり、ｎ−１が好ましい基準に適合する場合のｎ＝ｈｒ＋１の値が計算され、虚数乗法がｎに適用されて値ｑと、ｑ上で定義され、位数ｎを有する楕円曲線Ｅが生成される。
【解決手段】ｍｏｄ ｐ群において、偶数ｈが約（９／１６）（ｌｏｇ2ｎ）2の値として選択され、値ｒとｎは、ｒとｎに対するふるいと素数性テストを使用して判定され、値ｔが、ｐが素数の場合に、ｐ＝ｔｎ＋１を計算するために見出される。二進数体上で定義された楕円曲線群において、任意の曲線が選択され、曲線上の点の数がカウントされ、この数が、ｎが素数の場合の２ｎの値であるかが調べられ、ｎ−１が好ましい基準に適合するかが調べられる。位数ｑの素数体上で定義された楕円曲線群において、ｎが素数であり、ｎ−１が好ましい基準に適合する場合のｎ＝ｈｒ＋１の値が計算され、虚数乗法がｎに適用されて値ｑと、ｑ上で定義され、位数ｎを有する楕円曲線Ｅが生成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号の分野における静的群に関する。
【背景技術】
【０００２】
公開鍵暗号は、１９７５年にディフィ（Diffie）とヘルマン（Hellman）により導入されたように、特に、予め共有された秘密なしでの機密通信と、否認防止特性を有するデジタル署名とを可能にした。
【０００３】
公開鍵暗号に対するディフィ−ヘルマン（DH）プロトコルの最も独創的な側面は、ある問題、つまり離散対数問題に対処が困難である群と呼ばれる数学的構造を使用することであった。
【０００４】
群は単に要素と、任意の２つの要素に作用する単一の演算の集合である。群の身近な例としては、加法演算についての整数（ゼロと負の整数を含む）、加法演算についての有理数、および乗法演算についての非ゼロ有理数がある。これらの身近な例は無限群であるが、有限群も存在する。暗号学者は一般的には、群の要素が固定数のビットと対応づけられるという部分的な理由のため、有限群により関心を見せてきた。有限群の例は一般的にこの分野においてよく知られている。
【０００５】
最も身近な例は、モジュラ演算に基づく群である。ｐが素数でｔは任意の整数の場合、ｔ ｍｏｄ ｐは、ｔをｐで除算したときの余りになる。従って、ある整数ｑに対してｔ＝ｐｑ+ｒならば、ｒは０からｐ−１までのその両者を含む範囲にあり、ｒ＝ｔ ｍｏｄ ｐが成り立つ。０からｐ−１までの両者を含む整数の集合は、ｓとｔが組み合わされて、ｓ+ｔ ｍｏｄ ｐとなる、モジュラ加法演算についての群を形成する。この群はＺｐと表記される。より一般的には、ｐは任意の整数であってよい。
【０００６】
１からｐ−１までのその両者を含む整数の集合は、ｓとｔが組み合わされてｓｔ ｍｏｄ ｐとなる、モジュラ乗法演算についての別の群を形成する。この群はＺｐ＊と表記され、しばしばａ mod ｐ群と呼ばれる。より一般的には、ｐはわずかに異なる演算を伴う、素数の任意の冪乗であってよい。これらの群の演算を記述するときは、ｍｏｄ ｐの表記は、その前後関係から明白な場合はしばしば省略される。
【０００７】
群Ｇの部分群は、これもまたＧにおける要素の部分集合であり、Ｇと同じ演算を有する。例えば、群Ｚｐ＊は、その要素が１とｐ−１である、位数２の部分群を有する。より一般的には、ある群の任意の要素ｇに対して、＜ｇ＞と表記される最小の部分群があり、＜ｇ＞要素を含む。＜ｇ＞は、整数ｘに対する要素ｇｘの集合により正確に与えられ、ここでｇｘは、ｇのｘ乗の積を意味する。Ｚｐのような加法表記についての群においては、冪乗ｇｘはｘｇと表記される。要素ｇは＜ｇ＞に対する生成元である。群は、生成元を有していれば巡回群であり、従って、＜ｇ＞は本質的に巡回的である。群ＺｐとＺｐ＊もまた巡回群であるが、一般的には、群は巡回的である必要はない。
【０００８】
群の位数は要素数である。群Ｚｐは位数ｐを有し、群Ｚｐ＊は位数ｐ−１を有する。要素ｇの位数は、部分群＜ｇ＞の位数である。ｇは位数ｎを有すると仮定される。
【０００９】
演算が乗算で表記される群においては、離散対数問題は、「ｇとｗが与えられたとき、ｗ＝ｇｘとなるような整数ｘを求めよ。ただし、ｇｘはｇのｘ乗の積を意味する」と述べることができる。この問題は通常、そのような整数ｘが存在する場合、つまり、ｗが＜ｇ＞の要素である場合に要求される。一般対数問題は、ｘが整数である必要はなく、群が加法性を有しており、非整数の冪乗が定義できる場合にのみ定義できる。
【００１０】
いくつかの離散群において、離散対数問題（ＤＬＰ）を解くのは難しい。ディフィ（Diffie）とヘルマン（Hellman）は、ＤＬＰが公開鍵暗号に対して、第１の存在可能な解を求めるのは「難しい」という事実を活用した。この場合、アリス（Alice）は任意の整数ｘを選択し、ボブ（Bob）に群の要素ｇｘを送り、ボブ（Bob）は任意の整数ｙを選択し、アリス（Alice）に群の要素ｇｙを送る。次に、アリス（Alice）はｚ＝（ｇｘ）ｙを計算し、ボブ（Bob）はｚ’＝（ｇｙ）ｘを計算する。明らかにｚ＝ｚ’＝ｇｘｙ＝ｇｙｘであるので、アリス（Alice）とボブ（Bob）は同一の値を算出できる。いかなる第三者もｚを算出できなければ、アリス（Alice）とボブ（Bob）は、共有された秘密について合意したことになる。共有された秘密は、アリス（Alice）とボブ（Bob）の間で通信されるメッセージを暗号化するのに使用できる。このプロトコルがディフィ−ヘルマン（Diffie-Hellman）鍵共有である。このプロトコルより以前は、アリス（Alice）とボブ（Bob）は秘密裏に、ｚについての合意のためにまず会う必要があった。このプロトコルにより、アリス（Alice）とボブ（Bob）はまず会うという必要がなくなる。
【００１１】
これは、ｇｘとｇｙの値が公開されるので、公開鍵暗号と呼ばれる。これらは公開鍵と呼ばれ、ｘとｙは私有鍵と呼ばれている。対（ｘ，ｇｘ）は、鍵ペアと呼ばれる。敵対するイブ（Ｅｖｅ）は、公開鍵を見ることができたとする。イブ（Ｅｖｅ）がＤＬＰを解くことができれば、彼女はｇとｇｘからｘを求めることができる。ｘにより、イブ（Ｅｖｅ）はアリス（Alice）と同じ方法で、つまりボブ（Bob）の公開鍵ｇｙと、アリス（Alice）の私有鍵ｘを使用して、ｚを算出できる。従って、共有された秘密は秘密ではなくなり、イブ（Ｅｖｅ）はこれを使用して、アリス（Alice）とボブ（Bob）がお互いに送った暗号化メッセージを解読できる。従って、ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルの安全性に対する必要条件は、ＤＬＰが「難しい」問題であるということである。イブ（Eve）がＤＬＰを解くことができてはならないのである。
【００１２】
幸いなことに、暗号学者がＤＬＰは難しいと信じている群が存在する。ＤＬＰが難しい群は、主に２つのよく知られた群のクラス、つまり、有限体の乗法群の部分群と、楕円曲線群の部分群である。楕円曲線群は他のＤＬＰ群に対して、公開鍵の通信と格納により狭い帯域幅を使用し、より迅速な演算を可能にするという優位点を有している。
【００１３】
静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有は、ある当事者の一方またはその両者が経時変化をしない鍵ペアを有するディフィ−ヘルマン（Diffie-Hellman）鍵共有の重要な変形である。アリス（Alice）が静的鍵ペアを有していれば、彼女の私有鍵ｘと公開鍵ｇｘは、すべての処理の間、同じであり続ける。この優位点は、アリス（Alice）が証明機関に彼女の公開鍵ｇｘに署名させることができ、ボブ（Bob）はその結果としての証明をアリス（Alice）から要求するのではなく、データべースから探すことができる。この１つの適用は、ボブ（Bob）が暗号化された電子メールをアリス（Alice）に送るときである。アリス（Alice）は、電子メールを暗号化する前に、ボブ（Bob）にｇｘを送る必要がない。その代わりに、ボブ（Bob）は、彼の住所録でも、または他の公共住所氏名録であってもよい、あるデータベースからｇｘを探す。ｇｘに対する証明は、アリス（Alice）が（そしてアリス（Alice）のみが）電子メールを暗号化できるということをボブ（Bob）に更に保証する。
【００１４】
これらの群のいくつかにおいて、ディフィ−ヘルマン（Diffie-Hellman）鍵共有は、今日では仮想プライベートネットワーク（ＶＰＮ）を保護するためのＩＰＳｅｃプロトコルにおいて共通して使用されている。ディフィ−ヘルマン（Diffie-Hellman）鍵共有はまた、静的変形を含めて、トランスポート層セキュリティ（ＴＬＳ）（ウェブサイトを安全にするために使用される）、電子署名付き電子メール（Ｓ／ＭＩＭＥ）（電子メールを安全にするために使用される）、またはセキュアシェル（ＳＨＨ）（コンピュータへのリモートログインのために使用される）のような、共通して使用されるインターネット技術タスクフォース（ＩＥＴＦ）セーフティプロトコルの随意の機能である。従って、ディフィ−ヘルマン（Diffie-Hellman）鍵共有を、可能な限り安全にすることは望ましいことである。
【００１５】
静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有の安全性は、単に離散対数が難しいということ以上のことに依存する。特に、敵対者がアリス（Alice）の静的私有鍵ｘを決定する方法は、アリス（Alice）に特別に選択された公開鍵ｇｙを送り、アリス（Alice）から結果としての共有された秘密ｚ＝ｇｘｙを得ることである。ほとんどの群において、この能動的攻撃によりｘを見出すことは、離散対数問題を直接解くよりもはるかに易しい。
【００１６】
当業者にとっては、上記の攻撃は２つの面において完全に現実的というわけではない。それにも拘わらず、この性質を有するそのような攻撃は考慮に値するほど重要であるという考えが十分に確立されている。
【００１７】
まず、被害者アリス（Alice）は共有された秘密ｚを敵対者には明らかにしないであろう。しかし、ｚの目的は使用されることであり、ｚが使用される正確な方法の定量化は定義するのが困難である。ｚの任意の使用は、ある種の暴露という結果になる。従って、暗号学者は、被害者が自分の私有鍵操作の結果を暴露するような選択された暗号文攻撃を考慮することが賢明であることを見出した。更に、選択された暗号文攻撃に対する抵抗を示すことは、より弱い攻撃もまた抵抗されることを意味する。賢明なことに、暗号学者は、最も弱い攻撃だけでなく、可能性のある最も強い攻撃に抵抗することを求めた。従って、ｚが暴露されるということを仮定することは賢明であり、かつ、まったく非現実的というわけではない。
【００１８】
二番目に、ディフィ−ヘルマン（Diffie-Hellman）鍵共有の最も標準化されたバージョンにおいては、共有された秘密ｚは、たった１つの目的のために、つまり鍵を導出するためにのみ使用される。この目的のため、鍵導出関数（ＫＤＦ）が使用される。このように、アリス（Alice）はｋ＝ＫＤＦ（ｚ）を計算する。鍵導出関数は通常は、一方向性関数として選択され、そのため、ｋからだけでは、ｚを再構築する既知の方法はないことを意味する。従って、上記の攻撃においては、アリス（Alice）が敵対者に、ｚよりもｋを暴露してしまう可能性の方が高い。しかし、攻撃のためにはｚを必要とする。アリス（Alice）がｋしか暴露しない場合は、ｘを見出すために攻撃は使えない。ＫＤＦは一方向性なので、攻撃者はｋの暴露された値からｚを復旧することはできない。
【００１９】
上記の攻撃を考慮する以前は、ＫＤＦを使用することは、多少、より重要でない安全性の恩恵を有するということは既知であった。これらの１つは、共有された秘密ｚはしばしばランダムに識別可能であるということであった。ｚはランダムに識別可能なため、鍵としての使用は理想的ではない。しかし、上記の攻撃を考慮するまでは、ｚがｘについての何らかの情報を実際にリークしたということは知られていなかった。
【００２０】
多くのプロトコルと、ディフィ−ヘルマン（Diffie-Hellman）鍵共有の実践は、ＫＤＦの使用に関してはそれほど厳格ではない。スマートカードのある実践において、スマートカードはｚをスマートカードリーダーに暴露し、スマートカードリーダーはＫＤＦを適用する。そのようなシステムにおいて、悪意のあるスマートカードリーダーは、攻撃と、スマートカードからのｚ値を使用して、スマートカード上の私有鍵ｘを推測できる。ベーシックエルガマル（ElGamal）暗号化のような、あるプロトコルにおいては、ショームとヴァン・アントワーペン（Chaumand van Antwerpen）の否認不可署名は、アリス（Alice）が暴露するｚのエンティティを、プロトコルの一部とするように設計されている。従って、これらのプロトコルは攻撃に対して脆弱である。しかし、これら２つのプロトコルは、ＫＤＦの恩恵が知られる前に設計された。これらのプロトコルは、ＫＤＦを適用することにより、容易に補正できる。実際、ベレア（Bellare）とロガウェイ（Rogaway）により設計された（ＤＨＡＥＳ）は、特に、ＫＤＦを共有された秘密ｚに、それを鍵として使用する前に適用した、エルガマル（ElGamal）の改良として設計された。
【００２１】
しかし、ＫＤＦを追加することでは、容易に修正できない他のプロトコルも存在する。そのようなプロトコルの１つは、フォード−カリスキー（Ford-Kaliski）の鍵検索プロトコルである。このプロトコルでは、基点ｇはクライアントのパスワードの関数であり、アリス（Alice）はサーバーである。クライアントは、任意のｙを選択してｇｙをアリス（Alice）に送る。プロトコルが機能するためには、アリス（Alice）は、彼女がディフィ−ヘルマン（Diffie-Hellman）鍵共有を行っているクライアントすべてに対して、結果としての共有された秘密ｚを暴露しなければならない。クライアントは、ｚからクライアントのパスワードとサーバーの私有鍵ｘ両者の関数である静的値ｇｘを導出する。静的値ｇｘは、通常のパスワードよりも推測するのが困難なので、検索鍵、または堅牢パスワードと称せられる。鍵検索、またはパスワードの堅牢化は、フォード−カリスキー（Ford-Kaliski）プロトコルの主要な目的である。クライアントはこれを、ｚｕ＝ｇｘｙｕを計算することで行い、ここでｕは、ｙｕが指数空間で１に等しくなるような値である。プロトコルは、アリス（Alice）がＫＤＦをｚに適用していると、クライアントは静的値を復旧できないので機能しない。敵対者は、悪意のあるクライアントがｚの値を使用してアリス（Alice）の私有鍵ｘを導出するように仕向けることができる。敵対者は、今はｘを知っているので、ｇｘを推測することは、パスワードｇを推測する程度に容易である。特に、敵対者は、辞書的検索を行って、堅牢化パスワードを非常に迅速に決定できる。従って、この攻撃は、フォード−カリスキー（Ford-Kaliski）プロトコルの主要な目的を打ち破る。
【００２２】
まったく異なる様相は、静的ディフィ−ヘルマン（Diffie-Hellman）問題は難しいということである。より正確に述べれば、私有鍵ｘを知らずにｗからｗｘを計算することは難しいということである。ｗ＝ｇｙとすることは、静的ディフィ−ヘルマン（Diffie-Hellman）プロトコルを破ることが、ｘを見出すことと同じ程度に難しいことを示している。これは、上記の攻撃を考慮するとパラドックスのように見えるが、実際はそうではない。上記の攻撃においては、敵対者は行動的である。敵対者は、被害者を利用してディフィ−ヘルマン（Diffie-Hellman）問題を解いてｇｙを求めようとする。これは、ｘを見出す問題と等価である、静的ディフィ−ヘルマン（Diffie-Hellman）問題を解く能力を敵対者に与える。より正確に述べれば、静的ＤＨ問題は、ある因子内でｘを見出すこととほとんど同程度に難しい。
【００２３】
アリス（Alice）が攻撃を、例えばＫＤＦにより、何とか防いだとしても、静的DH問題を解くことは、ｘを見出すこととほとんど同程度に難しいということは事実として変わらない。これは、誰も静的ディフィ−ヘルマン（Diffie-Hellman）問題を解くことができないということ、つまり、私有鍵ｙを知っている彼女とボブ（Bob）以外の誰も、共有された秘密ｚを計算することができないという確信をアリス（Alice）に与える。この性質の結果は、証明可能安全性として知られている。
【００２４】
ＤＨ問題についての、以前の証明可能安全性の結果は、静的変形には対処しなかった。従って、以前の結果は、アリス（Alice）が私有鍵を使用することについて、同程度の確信を彼女に提供しなかった。また、以前の安全性の結果に対応する既知の攻撃もなかった。ＤＨについての証明可能安全性の結果の有効性は、ＤＨ群の選択に依存する。従って、静的ＤＨ問題を含めて、ＤＨ問題が難しい群を使用することが望ましい。
【００２５】
従って、本発明の目的は、上記の不都合な点を除去あるいは緩和することである。
【発明の概要】
【課題を解決するための手段】
【００２６】
１つの態様において、本発明により、静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルが、敵対者による能動的攻撃を防ぐのための、ｍｏｄ ｐ群を選択する方法が提供され、本方法は、偶数値ｈを選択するステップと、ｒとｎが素数のとき、ｎ＝ｈｒ+１という関係を満たすｒとｎの値を探すステップと、ｐが素数のとき、ｐ＝ｔｎ+１を計算するためのｔの値を探すステップを含む。
【００２７】
別の態様において、本発明により、静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルが敵対者による能動的攻撃を防ぐための、二進数体上で定義された楕円曲線群を選択する方法が提供され、本方法は、任意の曲線を選択するステップと、曲線上の点の数をカウントするステップと、ｎが素数で、ｎ−１が好適な基準を満たすとき、曲線上の点の数が2ｎであることを調べるステップを含む。
【００２８】
更に別の態様において、本発明により、静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルが敵対者による能動的攻撃を防ぐための、位数ｑの素数体上で定義された楕円曲線群を選択する方法が提供され、本方法は、ｎが素数でｎ−１が好適な基準を満たすとき、ｎ＝ｈｒ＋１を計算するステップと、ｎについての虚数乗法を実行して、値ｑと、位数ｎを有するｑ上で定義された楕円曲線Ｅを生成するステップ含む。
例えば、本発明は以下の項目を提供する。
（項目１）
素数の位数ｐと位数ｎの生成元ｇを有する有限群Ｇのパラメータを決定する方法であって、
ｉ）ｈが整数で、ｒが素数で、ｈがｒと比較して相対的に小さい場合に、ｎ＝ｈｒ＋１の形式のｎの値を選択するステップと、
ｉｉ）偶数の整数ｔを選択して、ｔが偶数の整数の場合の、ｔｎ＋１を計算するステップと、
ｉｉｉ）ｐ＝ｔｎ＋１の計算された値に対して、素数性を調べるステップと、
ｉｖ）位数ｐ上の計算された値が素数の場合は、それを採用するステップと、
を備える方法。
（項目２）
ｎの近似値が選択され、ｈがｎ１／３よりもかなり小さくなるようにｈが選択される請求項１に記載の方法。
（項目３）
ｎは素数であることが要求され、ｎの値は素数性がテストされる項目１に記載の方法。
（項目４）
ｒとｎの値は、小さな素数を有する値をふるいにかけて除外することにより選択される項目１に記載の方法。
（項目５）
上記群は、楕円曲線群であり、上記方法は、曲線上の点をカウントし、点の数が２ｎであることを判定するステップを含む項目１に記載の方法。
（項目６）
位数ｐと位数ｎの生成元ｇを有する有限群Ｇであって、ｈが整数で、ｒが素数の場合に、ｎ＝ｈｒ＋１であり、ｔが整数の場合に、ｐ＝ｔｎ＋１である有限群Ｇ。
（項目７）
位数ｐと位数ｎを有する生成元ｇを有する群Ｇの、暗号システムにおける使用のために領域パラメータを検証する方法であって、ｈが整数であり、ｒが素数の場合にｎ＝ｈｒ＋１であることと、ｔが整数の場合に、ｐ＝ｔｎ＋１であることを判定するステップを備える方法。
【図面の簡単な説明】
【００２９】
【図１】暗号システムの模式図である。
【図２】ｍｏｄ ｐの実施形態におけるステップを示すフローチャートである。
【図３】第１単純化楕円曲線の実施形態におけるステップを示すフローチャートである。
【図４】第２単純化楕円曲線の実施形態におけるステップを示すフローチャートである。
【発明を実施するための形態】
【００３０】
図１を参照すると、１組の通信者Ａ、Ｂは、データ通信リンク１２により接続されている。各通信者Ａ、Ｂは、暗号装置１４を有しており、この暗号装置は、リンク１上での確実な通信を可能にするために確立されたプロトコルに従って、公開鍵暗号操作を行う。暗号装置１４は、他のエンティティと共有されているパラメータの暗号領域内で作動する。
【００３１】
通信者Ａ、Ｂに共有された領域パラメータは、群Ｇと、群Ｇの位数ｐと、位数ｎの群の生成元ｇを含む。
【００３２】
本発明は、楕円曲線群と、有限体の乗法的部分群、より一般的にはｍｏｄ ｐ群として知られている、この両者に適用される。ｍｏｄ ｐ群はより理解し易いので、ｍｏｄ ｐの実施形態２０をまず説明して、その概略を図２に示す。両者の場合に共通する本発明の態様は、このように更に容易に理解できる。それにも拘わらず、本発明の好適な実施形態は、楕円曲線群についてであるが、これは性能特性においていくつかの優位点を有するからである。
【００３３】
（ｍｏｄ ｐの実施形態）
説明を簡単にするために、Ｚｐ＊におけるディフィ−ヘルマン（Diffie-Hellman）基点または生成元ｇは素数の位数ｎを有すると仮定する。当業者にとっては、これはｇが素数でない位数を有する場合にも拡張できることは明白であろう。
【００３４】
領域名パラメータの安全性は、ｎ−１の整数因子ｕのサイズに依存する。ある既知の因数ｕがｎ１／３に近いときは、上記の攻撃１０は、約３ｎ１／３の代償を必要とする。これは、約ｎ１／２の代償を必要とする一般的ＤＬＰ攻撃よりかなり小さい。任意のｎは、一般的にｎ１／３に近い因数ｕを有することは知られているので、ｎをランダムに選択することは、上記の攻撃１０を回避することにはならない。従来技術においては、ｎは一般的にはハッシュ関数の出力として選択されたが、これはｎを効果的に任意の数にするが、攻撃を回避しない。ｎを適切に選択することにより、ｎ１／３に近い因数を有することを回避できることが判明した。パラメータの選択とテストは、必要な計算を実行するようにプログラムされた計算装置を使用して行えることは理解されよう。そのような計算の結果は、装置１４上で暗号機能を実践するために使用できる領域パラメータの集合である。
【００３５】
第１実施形態において、そのような因子は、ｎ＝ｈｒ＋１を選択することにより回避され、ここでｒは素数で、ｈはｒと比較して相対的に小さな整数であり、ｎ１／３よりは十分に小さい整数である。ｎ−１の因子は、ｆまたはｆｒの形式であり、ここでｆはｈの因子である。ｈがｎ１／３よりかなり小さい場合は、因子ｆもそうであり、これはｆが高々ｈであることによる。ｈがｎ１／３よりかなり小さい場合は、ｒはｎ２／３よりかなり大きく、因子ｆｒもｎ１／３よりかなり大きい。従って、ｎ−１のすべての因子は、ｎ１／３よりかなり小さいか、または大きい。従って、静的ディフィ−ヘルマン（Diffie-Hellman）への攻撃は回避される。
【００３６】
ｎをｈｒ＋１の形式で選択したので、ｐを選択することも必要となる。群論の標準理論では、要素の位数はその群の位数を割ることができる。ｇはＺｐ＊の要素なので、その位数ｎはＺｐ＊の位数を割ることができなければならず、それはｐ−１である。従って、ある整数ｔに対しては、ｐ＝ｔｎ＋１となる。
【００３７】
群Ｚｐ＊は、ＤＬＰを解くための指標計算アルゴリズムを有しているので、共通の実践は、ｎよりかなり大きなｐを選択することである。その考えは、位数ｎの群＜ｇ＞における一般的ＤＬＰ解法アルゴリズムに、Ｚｐ＊における指標計算アルゴリズムとほぼ同じ代償を持たせようということである。例えば、ｎが約２１６０の場合、ｐは約21024であり、従って、これら両者のＤＬＰ解法アルゴリズムは、２８０の群演算とほとんど等価の代償を有することになる。ｎに対する他の共通選択は約２２５６であり、ｐに対しては23072であり、ここにおいて両者のＤＬＰ解法アルゴリズムは約２１２８の演算をすることになる。そのような小さなｎを選択する主な優位点は、群＜ｇ＞における冪乗は、指数がより小さいのではるかに高速であるということである。
【００３８】
上記に関連するサイズのｐとｎを得るためには、ほぼ同じサイズのｔを選択しさえすればよい。第１例においては、ｔを約２１０２４−１６０＝2864として選択し、第２例ではｔを約２２８１６として選択する。ｐとｎは奇数なので、ｔを偶数として選択する必要がある。値ｔ ｍｏｄ ３、ｔ ｍｏｄ ５、・・・、についての類似の観測もまた行うことができる。
【００３９】
一般的なプロセスは、まずｎを所望の形式で選択し、ｔのいくつかの値を、ｐを素数にするのを見つけるまで数回試みる。小さな確率内では、ｐが素数であることを判定する高速テストが存在する。これらのテストは、素数でないｔに対する候補値を即座に削除する。従って、好適なｔを見出すことが非常に迅速である。実際、ｎから開始して、これがｐを見出す最良の既知の方法である。
【００４０】
ｈｒ＋１の形式のｎを構築するために、まずｈに対する近似のサイズ、または正確なｈの値を選択し、ｒの近似サイズを、ｎの所望の近似サイズで決定する。実際には、決定された範囲における種々のｈとｒを選択でき、それぞれは適合性を調べられる。ｒの選択された値は、その素数性が調べられ、ｎ＝ｈｒ＋１が計算され、ｎの素数性が調べられる。ふるいの技術を使用して、２、３、または５のような小さな素数因子を有しないｒとｎを選択することができる。これにより、その素数性を調べなければならない値ｒとｎの数が削減される。ｈを使用して、より効率的に、ｎとｒの両者に対してふるいを適用できる。ｒとｎの両者が素数であり、従って奇数なので、ｈは偶数でなければならないことに留意されたい。
【００４１】
ｈに対する近似サイズまたは値を選択するときにある注意が必要である。もっとも小さい数の選択はｈ＝２である。しかし、この選択は、小さ過ぎて、ｈ＝2は上記の攻撃を回避するが、本技術の適用において、証明可能安全性の結果をも回避してしまう。
【００４２】
ｈに対しては範囲があり、その範囲においては、上記の攻撃は証明可能安全性の結果が有効である間は阻止される。この範囲はスカラー乗法を行うのに必要な群演算の数に依存する。ｈの最適値は、この値の０.５倍から２倍の範囲のｈの値を使用できるが、（９／１６）（ｌｏｇ2ｎ）2となる。約このサイズのｈに対して、静的ディフィ−ヘルマン（Diffie-Hellman）の問題は、容認できる因子内で、静的ディフィ−ヘルマン（Diffie-Hellman）私有鍵を見出すのとほとんど同じくらい難しい。この因子は、ｈのすべての選択に対して最適化される。更に、ｈのこの選択により、上記の攻撃は約ｎ１／２の群演算と等価の代償を必要とする。これは、攻撃がもはや、ｘを見出す一般的ＤＬＰ解法アルゴリズムより優れたものではないことを意味する。従って、そのような状況ではこの攻撃は適切ではない。
【００４３】
要約すると、まず約（９／１６）（ｌｏｇ2ｎ）2のオーダーの偶数ｈを選択し、ｒとｎに対して、ｎが素数として選択されるかどうかのふるいおよび素数性テストを使用してｒとｎを検索する。最終的に、ｐ＝ｔｎ＋１が素数となるようなｔを検索する。
【００４４】
本方法の追加的な効率改善もまた可能である。本方法においては、ｐを法とする還元をより効率的にする形式をｐが有するようなｎとｔを検索する。例えば、ｐが小さなハミング重みを有している場合、ｐを法とする還元はより効率的になる。これによりモジュラ乗法と、Ｚｐ＊の群演算がより効率的になる。
【００４５】
本方法の追加的な安全性改善もまた可能である。ｒの値は、検証可能に任意に選択できる。ｒの値はハッシュ関数の出力として選択できる。
【００４６】
これら２つの追加的な改善は、ランダムに検証可能にｒを選択し、ｐに効率的なモジュラ還元を持たせる値ｔを検索することにより組み合わせることができる。
【００４７】
そのような敵対者は、特別なプロトコルの特別な実践に対しては非現実的という理由で、上記の攻撃に関心がなければ、ディフィ−ヘルマン（Diffie-Hellman）群を異なるように選択できる。ｎ１／３に近いサイズの因数ｕを回避することは不要であるかもしれないが、静的ディフィ−ヘルマン（Diffie-Hellman）問題と、一般的ディフィ−ヘルマン（Diffie-Hellman）問題の両者が難しいということが依然として望まれる。静的ディフィ−ヘルマン（Diffie-Hellman）問題を難しくするためには、約（９／１６）（ｌｏｇ2ｎ）2のサイズのｎ−１の因子が必要となる。既存の数論の知識では、任意のｎがそのようなサイズの因数を有するかどうかは明確ではない。従って、任意のｎを選択して、そのような因数を探すか、そのようなサイズの因数ｈでｎを構築することができる。後者は、ｈを選択し、任意のｒ（素数である必要はない）を選択し、ｎ＝ｈｒ＋１について素数性をテストすることで行われる。
【００４８】
短命的、または両側ディフィ−ヘルマン（Diffie-Hellman）問題が難しいことを確実にするために、既存の証明可能安全性の結果を使用できる。モーラー（Maurer）とウルフ（Wolf）の結果は、通常はサイズｎの有限体上で定義された楕円曲線である補助群を見つけることを要求する。補助群は、滑らかな位数（大きくない素数因子）を有しなければならない。そのような補助群を探すことは、相当な労力を必要とし、ｎのより大きな値に対しては、手が届かない範囲にある。実際、そのような群を見つけることは、ｎと同じサイズの因数の整数とほぼ同じ程度に難しいことが知られている。
【００４９】
デン・ボア（denBoer）のより以前の結果は、ｎ−１は滑らかであり、（短命的）ディフィ−ヘルマン（Diffie-Hellman）問題は、ほとんどＤＬＰと同程度に難しいと述べている。
【００５０】
本技術の更なる改良は、従って、ｓが滑らかな整数である、ｎ＝１＋ｓを選択する方法を含むことになる。このｓは、正確なサイズが得られるような、小さな素数の積として見出せる。そしてｎに対して素数性がテストされる。ｓのいくつかの値が試される。ｎをこのように選択する利点は一般的には、ｎ−１が（９／１６）（ｌｏｇ2ｎ）2に十分に近いサイズの因数を有することを意味し、それによりディフィ−ヘルマン（Diffie-Hellman）問題が単なる短命的ディフィ−ヘルマン（Diffie-Hellman）問題ではなく、難しいということを確実にすることである。
【００５１】
そのようなｎにより、素数ｐ＝ｔｎ＋１は上記のように見出せる。更に、この方法により、小さなハミング（Hamming）重みのような、特別構造のｎとｐを求めることもできる。
【００５２】
（楕円曲線実施形態）
原理的に、上述した技術は、楕円曲線群の場合にも機能する。より正確にいえば、ｎに対する望ましい基準は同一である。しかしこの場合は、位数ｎの生成元ｇはＺｐ＊の要素ではなく、楕円曲線群Ｅの要素である。ｍｏｄ ｐの場合、いったんｎが決定されると、群Ｚｐ＊を見出すことは比較的に単純である。このことは、楕円曲線についてはいえない。決定されたｎに対して、楕円曲線群Ｅを見出すことは依然として非常に困難である。
【００５３】
楕円曲線は、ユーザー演算を、群Ｚｐ＊に対するよりも、より効率的にするので、楕円曲線の場合は、本発明の好適な実施形態である。この実施形態の本方法は、Ｚｐ＊の場合に対するよりもわずかに複雑であるが、それにも拘わらず価値がある。
【００５４】
説明をより明確にするために、楕円曲線実施形態における、本方法の簡略化されたいくつかの形態を図３と４に示す。
【００５５】
第１簡略化形態３０において、楕円曲線は、二進数体上で定義される。そのような曲線に対して、楕円曲線群の位数を決定することは非常に容易である。簡略化された方法は、任意の曲線を選択し、点の数をカウントし、点の数が、ｎが素数のときに２ｎであることを調べ、ｎ−１が所望の基準に適合するかを調べる。好適な基準は、ｎ−１＝ｈｒであり、ここでｒは素数で、ｈは約（９／１６）（ｌｏｇ2ｎ）2である。代替としての基準は、上記の攻撃を心配しないならば、ｎ−１が滑らか、ということである。
【００５６】
第２簡略化形態において、楕円曲線は位数ｑの素数体上で定義される。ｑの値は、ｎの値を決定した後に決定される。ｎの値はｍｏｄ ｐ群の場合のように選択される。ｎの値は、好適な基準または代替基準に適合できる。そして、ＡＮＳＩｘ９.６２またはＩＥＥＥ１３.６３で記述されているような、虚数乗法が使用されてｑの値と、位数ｎを有するｑ上で定義された楕円曲線Ｅを見出す。
【００５７】
通常は、虚数乗法は、ｑのある値はユーザーによりよい効率性をもたらすので、まずｑを選択することを含む。しかし、虚数乗法はｎが最初に選択されて機能する。ｑとｎが、虚数乗法の第１フェーズである正確な数理論関係でいったん見出されれば、第２フェーズは、楕円曲線Ｅを定義する係数を決定する。
【００５８】
第２簡略化方法の不都合な点は、結果としてのｑが、ｎから約ｎ１／２の距離内のすべての整数であるｎのハッセ（Hasse）区間において、多少任意な形式を有することである。よりよいユーザーの効率のために、二進展開における小さなハミング（Hamming）重みのようなｑの特別な形式が強く所望されている。
【００５９】
すなわち、ｑとｎの両者が特別形式を有することが所望されている。ｑに対する形式は効率のためであり、ｎに対する形式は安全性のためである。これを行うために、虚数乗法の第１フェーズはわずかに修正される。所望される特別形式のｑとｎが試され、この対をテストして、虚数乗法（ＣＭ）により要求される条件に適合するかが調べられる。この条件は、比較的簡単にテストできる。ｑが与えられても、条件に合うｎを解くことは決して容易にはならず、その逆もいえる。
【００６０】
虚数乗法の第１フェーズの修正は、所望形式のｑとｎのいくつかの異なる対を試し、ｑとｎに対するＣＭ法の条件をテストし、ＣＭ法の条件が満たされるまで繰り返し、ＣＭ法の通常のプロセスを使用して、楕円曲線Ｅの定義係数ａとｂを見出すことである。
【００６１】
ＣＭ法は、既知の方法であるが、その修正形式は既知ではない。本発明の好適な実施形態で記述されたように、ＣＭ法の修正形式により、よい高効率かつより安全なディフィ−ヘルマン（Diffie-Hellman）楕円曲線群を見出すことができる。
【００６２】
この方法の妥当性を示す例として、代替基準、つまり、ｎ−１が滑らという基準を使用して、本発明の発明者は、両者が素数である、ｎ＝１＋５５（２286）とｑ＝９＋５５（２２８８）の対を見出した。ＣＭ法の技術に精通している者は、この対に対する判別式は５５であることは理解するであろう。この判別式は、クロネッカ（Kronecker）の類数(class number)が1より大きく、従って、楕円曲線の自己準同形環は、一意分解整域ではないという意味で重要である。特にこれは、楕円曲線Ｅの係数ａとｂは、所定の表からは見出せないこと、そして、位数ｑの有限体上のかなり大きな階数の多項方程式を解くことにより計算しなければならないことを意味する。
【００６３】
上述のように、本技術は所望の特性を有する領域パラメータを生成するために使用できる。これらの特性が生成される方法はまた、それ自身、攻撃に対して脆弱ではないことを確実にするために、第三者により供給された領域パラメータの効力を調べるためにも適合している。パラメータはｐとｎの値が要求された形式を満足することを確実にするために調べることもできる。パラメータがこれらの基準を満たさない場合は、領域パラメータは破棄される。
【００６４】
本発明は、ある特別な実施形態を参照して記述されてきたが、その種々の変形は、ここに添付された請求項で概要を記載される本発明の精神と範囲を逸脱することなく可能であることは当業者には明白であろう。上記に引用したすべての参考にした開示内容は、参考文献として本明細書に組み込まれている。
【技術分野】
【０００１】
本発明は、暗号の分野における静的群に関する。
【背景技術】
【０００２】
公開鍵暗号は、１９７５年にディフィ（Diffie）とヘルマン（Hellman）により導入されたように、特に、予め共有された秘密なしでの機密通信と、否認防止特性を有するデジタル署名とを可能にした。
【０００３】
公開鍵暗号に対するディフィ−ヘルマン（DH）プロトコルの最も独創的な側面は、ある問題、つまり離散対数問題に対処が困難である群と呼ばれる数学的構造を使用することであった。
【０００４】
群は単に要素と、任意の２つの要素に作用する単一の演算の集合である。群の身近な例としては、加法演算についての整数（ゼロと負の整数を含む）、加法演算についての有理数、および乗法演算についての非ゼロ有理数がある。これらの身近な例は無限群であるが、有限群も存在する。暗号学者は一般的には、群の要素が固定数のビットと対応づけられるという部分的な理由のため、有限群により関心を見せてきた。有限群の例は一般的にこの分野においてよく知られている。
【０００５】
最も身近な例は、モジュラ演算に基づく群である。ｐが素数でｔは任意の整数の場合、ｔ ｍｏｄ ｐは、ｔをｐで除算したときの余りになる。従って、ある整数ｑに対してｔ＝ｐｑ+ｒならば、ｒは０からｐ−１までのその両者を含む範囲にあり、ｒ＝ｔ ｍｏｄ ｐが成り立つ。０からｐ−１までの両者を含む整数の集合は、ｓとｔが組み合わされて、ｓ+ｔ ｍｏｄ ｐとなる、モジュラ加法演算についての群を形成する。この群はＺｐと表記される。より一般的には、ｐは任意の整数であってよい。
【０００６】
１からｐ−１までのその両者を含む整数の集合は、ｓとｔが組み合わされてｓｔ ｍｏｄ ｐとなる、モジュラ乗法演算についての別の群を形成する。この群はＺｐ＊と表記され、しばしばａ mod ｐ群と呼ばれる。より一般的には、ｐはわずかに異なる演算を伴う、素数の任意の冪乗であってよい。これらの群の演算を記述するときは、ｍｏｄ ｐの表記は、その前後関係から明白な場合はしばしば省略される。
【０００７】
群Ｇの部分群は、これもまたＧにおける要素の部分集合であり、Ｇと同じ演算を有する。例えば、群Ｚｐ＊は、その要素が１とｐ−１である、位数２の部分群を有する。より一般的には、ある群の任意の要素ｇに対して、＜ｇ＞と表記される最小の部分群があり、＜ｇ＞要素を含む。＜ｇ＞は、整数ｘに対する要素ｇｘの集合により正確に与えられ、ここでｇｘは、ｇのｘ乗の積を意味する。Ｚｐのような加法表記についての群においては、冪乗ｇｘはｘｇと表記される。要素ｇは＜ｇ＞に対する生成元である。群は、生成元を有していれば巡回群であり、従って、＜ｇ＞は本質的に巡回的である。群ＺｐとＺｐ＊もまた巡回群であるが、一般的には、群は巡回的である必要はない。
【０００８】
群の位数は要素数である。群Ｚｐは位数ｐを有し、群Ｚｐ＊は位数ｐ−１を有する。要素ｇの位数は、部分群＜ｇ＞の位数である。ｇは位数ｎを有すると仮定される。
【０００９】
演算が乗算で表記される群においては、離散対数問題は、「ｇとｗが与えられたとき、ｗ＝ｇｘとなるような整数ｘを求めよ。ただし、ｇｘはｇのｘ乗の積を意味する」と述べることができる。この問題は通常、そのような整数ｘが存在する場合、つまり、ｗが＜ｇ＞の要素である場合に要求される。一般対数問題は、ｘが整数である必要はなく、群が加法性を有しており、非整数の冪乗が定義できる場合にのみ定義できる。
【００１０】
いくつかの離散群において、離散対数問題（ＤＬＰ）を解くのは難しい。ディフィ（Diffie）とヘルマン（Hellman）は、ＤＬＰが公開鍵暗号に対して、第１の存在可能な解を求めるのは「難しい」という事実を活用した。この場合、アリス（Alice）は任意の整数ｘを選択し、ボブ（Bob）に群の要素ｇｘを送り、ボブ（Bob）は任意の整数ｙを選択し、アリス（Alice）に群の要素ｇｙを送る。次に、アリス（Alice）はｚ＝（ｇｘ）ｙを計算し、ボブ（Bob）はｚ’＝（ｇｙ）ｘを計算する。明らかにｚ＝ｚ’＝ｇｘｙ＝ｇｙｘであるので、アリス（Alice）とボブ（Bob）は同一の値を算出できる。いかなる第三者もｚを算出できなければ、アリス（Alice）とボブ（Bob）は、共有された秘密について合意したことになる。共有された秘密は、アリス（Alice）とボブ（Bob）の間で通信されるメッセージを暗号化するのに使用できる。このプロトコルがディフィ−ヘルマン（Diffie-Hellman）鍵共有である。このプロトコルより以前は、アリス（Alice）とボブ（Bob）は秘密裏に、ｚについての合意のためにまず会う必要があった。このプロトコルにより、アリス（Alice）とボブ（Bob）はまず会うという必要がなくなる。
【００１１】
これは、ｇｘとｇｙの値が公開されるので、公開鍵暗号と呼ばれる。これらは公開鍵と呼ばれ、ｘとｙは私有鍵と呼ばれている。対（ｘ，ｇｘ）は、鍵ペアと呼ばれる。敵対するイブ（Ｅｖｅ）は、公開鍵を見ることができたとする。イブ（Ｅｖｅ）がＤＬＰを解くことができれば、彼女はｇとｇｘからｘを求めることができる。ｘにより、イブ（Ｅｖｅ）はアリス（Alice）と同じ方法で、つまりボブ（Bob）の公開鍵ｇｙと、アリス（Alice）の私有鍵ｘを使用して、ｚを算出できる。従って、共有された秘密は秘密ではなくなり、イブ（Ｅｖｅ）はこれを使用して、アリス（Alice）とボブ（Bob）がお互いに送った暗号化メッセージを解読できる。従って、ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルの安全性に対する必要条件は、ＤＬＰが「難しい」問題であるということである。イブ（Eve）がＤＬＰを解くことができてはならないのである。
【００１２】
幸いなことに、暗号学者がＤＬＰは難しいと信じている群が存在する。ＤＬＰが難しい群は、主に２つのよく知られた群のクラス、つまり、有限体の乗法群の部分群と、楕円曲線群の部分群である。楕円曲線群は他のＤＬＰ群に対して、公開鍵の通信と格納により狭い帯域幅を使用し、より迅速な演算を可能にするという優位点を有している。
【００１３】
静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有は、ある当事者の一方またはその両者が経時変化をしない鍵ペアを有するディフィ−ヘルマン（Diffie-Hellman）鍵共有の重要な変形である。アリス（Alice）が静的鍵ペアを有していれば、彼女の私有鍵ｘと公開鍵ｇｘは、すべての処理の間、同じであり続ける。この優位点は、アリス（Alice）が証明機関に彼女の公開鍵ｇｘに署名させることができ、ボブ（Bob）はその結果としての証明をアリス（Alice）から要求するのではなく、データべースから探すことができる。この１つの適用は、ボブ（Bob）が暗号化された電子メールをアリス（Alice）に送るときである。アリス（Alice）は、電子メールを暗号化する前に、ボブ（Bob）にｇｘを送る必要がない。その代わりに、ボブ（Bob）は、彼の住所録でも、または他の公共住所氏名録であってもよい、あるデータベースからｇｘを探す。ｇｘに対する証明は、アリス（Alice）が（そしてアリス（Alice）のみが）電子メールを暗号化できるということをボブ（Bob）に更に保証する。
【００１４】
これらの群のいくつかにおいて、ディフィ−ヘルマン（Diffie-Hellman）鍵共有は、今日では仮想プライベートネットワーク（ＶＰＮ）を保護するためのＩＰＳｅｃプロトコルにおいて共通して使用されている。ディフィ−ヘルマン（Diffie-Hellman）鍵共有はまた、静的変形を含めて、トランスポート層セキュリティ（ＴＬＳ）（ウェブサイトを安全にするために使用される）、電子署名付き電子メール（Ｓ／ＭＩＭＥ）（電子メールを安全にするために使用される）、またはセキュアシェル（ＳＨＨ）（コンピュータへのリモートログインのために使用される）のような、共通して使用されるインターネット技術タスクフォース（ＩＥＴＦ）セーフティプロトコルの随意の機能である。従って、ディフィ−ヘルマン（Diffie-Hellman）鍵共有を、可能な限り安全にすることは望ましいことである。
【００１５】
静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有の安全性は、単に離散対数が難しいということ以上のことに依存する。特に、敵対者がアリス（Alice）の静的私有鍵ｘを決定する方法は、アリス（Alice）に特別に選択された公開鍵ｇｙを送り、アリス（Alice）から結果としての共有された秘密ｚ＝ｇｘｙを得ることである。ほとんどの群において、この能動的攻撃によりｘを見出すことは、離散対数問題を直接解くよりもはるかに易しい。
【００１６】
当業者にとっては、上記の攻撃は２つの面において完全に現実的というわけではない。それにも拘わらず、この性質を有するそのような攻撃は考慮に値するほど重要であるという考えが十分に確立されている。
【００１７】
まず、被害者アリス（Alice）は共有された秘密ｚを敵対者には明らかにしないであろう。しかし、ｚの目的は使用されることであり、ｚが使用される正確な方法の定量化は定義するのが困難である。ｚの任意の使用は、ある種の暴露という結果になる。従って、暗号学者は、被害者が自分の私有鍵操作の結果を暴露するような選択された暗号文攻撃を考慮することが賢明であることを見出した。更に、選択された暗号文攻撃に対する抵抗を示すことは、より弱い攻撃もまた抵抗されることを意味する。賢明なことに、暗号学者は、最も弱い攻撃だけでなく、可能性のある最も強い攻撃に抵抗することを求めた。従って、ｚが暴露されるということを仮定することは賢明であり、かつ、まったく非現実的というわけではない。
【００１８】
二番目に、ディフィ−ヘルマン（Diffie-Hellman）鍵共有の最も標準化されたバージョンにおいては、共有された秘密ｚは、たった１つの目的のために、つまり鍵を導出するためにのみ使用される。この目的のため、鍵導出関数（ＫＤＦ）が使用される。このように、アリス（Alice）はｋ＝ＫＤＦ（ｚ）を計算する。鍵導出関数は通常は、一方向性関数として選択され、そのため、ｋからだけでは、ｚを再構築する既知の方法はないことを意味する。従って、上記の攻撃においては、アリス（Alice）が敵対者に、ｚよりもｋを暴露してしまう可能性の方が高い。しかし、攻撃のためにはｚを必要とする。アリス（Alice）がｋしか暴露しない場合は、ｘを見出すために攻撃は使えない。ＫＤＦは一方向性なので、攻撃者はｋの暴露された値からｚを復旧することはできない。
【００１９】
上記の攻撃を考慮する以前は、ＫＤＦを使用することは、多少、より重要でない安全性の恩恵を有するということは既知であった。これらの１つは、共有された秘密ｚはしばしばランダムに識別可能であるということであった。ｚはランダムに識別可能なため、鍵としての使用は理想的ではない。しかし、上記の攻撃を考慮するまでは、ｚがｘについての何らかの情報を実際にリークしたということは知られていなかった。
【００２０】
多くのプロトコルと、ディフィ−ヘルマン（Diffie-Hellman）鍵共有の実践は、ＫＤＦの使用に関してはそれほど厳格ではない。スマートカードのある実践において、スマートカードはｚをスマートカードリーダーに暴露し、スマートカードリーダーはＫＤＦを適用する。そのようなシステムにおいて、悪意のあるスマートカードリーダーは、攻撃と、スマートカードからのｚ値を使用して、スマートカード上の私有鍵ｘを推測できる。ベーシックエルガマル（ElGamal）暗号化のような、あるプロトコルにおいては、ショームとヴァン・アントワーペン（Chaumand van Antwerpen）の否認不可署名は、アリス（Alice）が暴露するｚのエンティティを、プロトコルの一部とするように設計されている。従って、これらのプロトコルは攻撃に対して脆弱である。しかし、これら２つのプロトコルは、ＫＤＦの恩恵が知られる前に設計された。これらのプロトコルは、ＫＤＦを適用することにより、容易に補正できる。実際、ベレア（Bellare）とロガウェイ（Rogaway）により設計された（ＤＨＡＥＳ）は、特に、ＫＤＦを共有された秘密ｚに、それを鍵として使用する前に適用した、エルガマル（ElGamal）の改良として設計された。
【００２１】
しかし、ＫＤＦを追加することでは、容易に修正できない他のプロトコルも存在する。そのようなプロトコルの１つは、フォード−カリスキー（Ford-Kaliski）の鍵検索プロトコルである。このプロトコルでは、基点ｇはクライアントのパスワードの関数であり、アリス（Alice）はサーバーである。クライアントは、任意のｙを選択してｇｙをアリス（Alice）に送る。プロトコルが機能するためには、アリス（Alice）は、彼女がディフィ−ヘルマン（Diffie-Hellman）鍵共有を行っているクライアントすべてに対して、結果としての共有された秘密ｚを暴露しなければならない。クライアントは、ｚからクライアントのパスワードとサーバーの私有鍵ｘ両者の関数である静的値ｇｘを導出する。静的値ｇｘは、通常のパスワードよりも推測するのが困難なので、検索鍵、または堅牢パスワードと称せられる。鍵検索、またはパスワードの堅牢化は、フォード−カリスキー（Ford-Kaliski）プロトコルの主要な目的である。クライアントはこれを、ｚｕ＝ｇｘｙｕを計算することで行い、ここでｕは、ｙｕが指数空間で１に等しくなるような値である。プロトコルは、アリス（Alice）がＫＤＦをｚに適用していると、クライアントは静的値を復旧できないので機能しない。敵対者は、悪意のあるクライアントがｚの値を使用してアリス（Alice）の私有鍵ｘを導出するように仕向けることができる。敵対者は、今はｘを知っているので、ｇｘを推測することは、パスワードｇを推測する程度に容易である。特に、敵対者は、辞書的検索を行って、堅牢化パスワードを非常に迅速に決定できる。従って、この攻撃は、フォード−カリスキー（Ford-Kaliski）プロトコルの主要な目的を打ち破る。
【００２２】
まったく異なる様相は、静的ディフィ−ヘルマン（Diffie-Hellman）問題は難しいということである。より正確に述べれば、私有鍵ｘを知らずにｗからｗｘを計算することは難しいということである。ｗ＝ｇｙとすることは、静的ディフィ−ヘルマン（Diffie-Hellman）プロトコルを破ることが、ｘを見出すことと同じ程度に難しいことを示している。これは、上記の攻撃を考慮するとパラドックスのように見えるが、実際はそうではない。上記の攻撃においては、敵対者は行動的である。敵対者は、被害者を利用してディフィ−ヘルマン（Diffie-Hellman）問題を解いてｇｙを求めようとする。これは、ｘを見出す問題と等価である、静的ディフィ−ヘルマン（Diffie-Hellman）問題を解く能力を敵対者に与える。より正確に述べれば、静的ＤＨ問題は、ある因子内でｘを見出すこととほとんど同程度に難しい。
【００２３】
アリス（Alice）が攻撃を、例えばＫＤＦにより、何とか防いだとしても、静的DH問題を解くことは、ｘを見出すこととほとんど同程度に難しいということは事実として変わらない。これは、誰も静的ディフィ−ヘルマン（Diffie-Hellman）問題を解くことができないということ、つまり、私有鍵ｙを知っている彼女とボブ（Bob）以外の誰も、共有された秘密ｚを計算することができないという確信をアリス（Alice）に与える。この性質の結果は、証明可能安全性として知られている。
【００２４】
ＤＨ問題についての、以前の証明可能安全性の結果は、静的変形には対処しなかった。従って、以前の結果は、アリス（Alice）が私有鍵を使用することについて、同程度の確信を彼女に提供しなかった。また、以前の安全性の結果に対応する既知の攻撃もなかった。ＤＨについての証明可能安全性の結果の有効性は、ＤＨ群の選択に依存する。従って、静的ＤＨ問題を含めて、ＤＨ問題が難しい群を使用することが望ましい。
【００２５】
従って、本発明の目的は、上記の不都合な点を除去あるいは緩和することである。
【発明の概要】
【課題を解決するための手段】
【００２６】
１つの態様において、本発明により、静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルが、敵対者による能動的攻撃を防ぐのための、ｍｏｄ ｐ群を選択する方法が提供され、本方法は、偶数値ｈを選択するステップと、ｒとｎが素数のとき、ｎ＝ｈｒ+１という関係を満たすｒとｎの値を探すステップと、ｐが素数のとき、ｐ＝ｔｎ+１を計算するためのｔの値を探すステップを含む。
【００２７】
別の態様において、本発明により、静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルが敵対者による能動的攻撃を防ぐための、二進数体上で定義された楕円曲線群を選択する方法が提供され、本方法は、任意の曲線を選択するステップと、曲線上の点の数をカウントするステップと、ｎが素数で、ｎ−１が好適な基準を満たすとき、曲線上の点の数が2ｎであることを調べるステップを含む。
【００２８】
更に別の態様において、本発明により、静的ディフィ−ヘルマン（Diffie-Hellman）鍵共有プロトコルが敵対者による能動的攻撃を防ぐための、位数ｑの素数体上で定義された楕円曲線群を選択する方法が提供され、本方法は、ｎが素数でｎ−１が好適な基準を満たすとき、ｎ＝ｈｒ＋１を計算するステップと、ｎについての虚数乗法を実行して、値ｑと、位数ｎを有するｑ上で定義された楕円曲線Ｅを生成するステップ含む。
例えば、本発明は以下の項目を提供する。
（項目１）
素数の位数ｐと位数ｎの生成元ｇを有する有限群Ｇのパラメータを決定する方法であって、
ｉ）ｈが整数で、ｒが素数で、ｈがｒと比較して相対的に小さい場合に、ｎ＝ｈｒ＋１の形式のｎの値を選択するステップと、
ｉｉ）偶数の整数ｔを選択して、ｔが偶数の整数の場合の、ｔｎ＋１を計算するステップと、
ｉｉｉ）ｐ＝ｔｎ＋１の計算された値に対して、素数性を調べるステップと、
ｉｖ）位数ｐ上の計算された値が素数の場合は、それを採用するステップと、
を備える方法。
（項目２）
ｎの近似値が選択され、ｈがｎ１／３よりもかなり小さくなるようにｈが選択される請求項１に記載の方法。
（項目３）
ｎは素数であることが要求され、ｎの値は素数性がテストされる項目１に記載の方法。
（項目４）
ｒとｎの値は、小さな素数を有する値をふるいにかけて除外することにより選択される項目１に記載の方法。
（項目５）
上記群は、楕円曲線群であり、上記方法は、曲線上の点をカウントし、点の数が２ｎであることを判定するステップを含む項目１に記載の方法。
（項目６）
位数ｐと位数ｎの生成元ｇを有する有限群Ｇであって、ｈが整数で、ｒが素数の場合に、ｎ＝ｈｒ＋１であり、ｔが整数の場合に、ｐ＝ｔｎ＋１である有限群Ｇ。
（項目７）
位数ｐと位数ｎを有する生成元ｇを有する群Ｇの、暗号システムにおける使用のために領域パラメータを検証する方法であって、ｈが整数であり、ｒが素数の場合にｎ＝ｈｒ＋１であることと、ｔが整数の場合に、ｐ＝ｔｎ＋１であることを判定するステップを備える方法。
【図面の簡単な説明】
【００２９】
【図１】暗号システムの模式図である。
【図２】ｍｏｄ ｐの実施形態におけるステップを示すフローチャートである。
【図３】第１単純化楕円曲線の実施形態におけるステップを示すフローチャートである。
【図４】第２単純化楕円曲線の実施形態におけるステップを示すフローチャートである。
【発明を実施するための形態】
【００３０】
図１を参照すると、１組の通信者Ａ、Ｂは、データ通信リンク１２により接続されている。各通信者Ａ、Ｂは、暗号装置１４を有しており、この暗号装置は、リンク１上での確実な通信を可能にするために確立されたプロトコルに従って、公開鍵暗号操作を行う。暗号装置１４は、他のエンティティと共有されているパラメータの暗号領域内で作動する。
【００３１】
通信者Ａ、Ｂに共有された領域パラメータは、群Ｇと、群Ｇの位数ｐと、位数ｎの群の生成元ｇを含む。
【００３２】
本発明は、楕円曲線群と、有限体の乗法的部分群、より一般的にはｍｏｄ ｐ群として知られている、この両者に適用される。ｍｏｄ ｐ群はより理解し易いので、ｍｏｄ ｐの実施形態２０をまず説明して、その概略を図２に示す。両者の場合に共通する本発明の態様は、このように更に容易に理解できる。それにも拘わらず、本発明の好適な実施形態は、楕円曲線群についてであるが、これは性能特性においていくつかの優位点を有するからである。
【００３３】
（ｍｏｄ ｐの実施形態）
説明を簡単にするために、Ｚｐ＊におけるディフィ−ヘルマン（Diffie-Hellman）基点または生成元ｇは素数の位数ｎを有すると仮定する。当業者にとっては、これはｇが素数でない位数を有する場合にも拡張できることは明白であろう。
【００３４】
領域名パラメータの安全性は、ｎ−１の整数因子ｕのサイズに依存する。ある既知の因数ｕがｎ１／３に近いときは、上記の攻撃１０は、約３ｎ１／３の代償を必要とする。これは、約ｎ１／２の代償を必要とする一般的ＤＬＰ攻撃よりかなり小さい。任意のｎは、一般的にｎ１／３に近い因数ｕを有することは知られているので、ｎをランダムに選択することは、上記の攻撃１０を回避することにはならない。従来技術においては、ｎは一般的にはハッシュ関数の出力として選択されたが、これはｎを効果的に任意の数にするが、攻撃を回避しない。ｎを適切に選択することにより、ｎ１／３に近い因数を有することを回避できることが判明した。パラメータの選択とテストは、必要な計算を実行するようにプログラムされた計算装置を使用して行えることは理解されよう。そのような計算の結果は、装置１４上で暗号機能を実践するために使用できる領域パラメータの集合である。
【００３５】
第１実施形態において、そのような因子は、ｎ＝ｈｒ＋１を選択することにより回避され、ここでｒは素数で、ｈはｒと比較して相対的に小さな整数であり、ｎ１／３よりは十分に小さい整数である。ｎ−１の因子は、ｆまたはｆｒの形式であり、ここでｆはｈの因子である。ｈがｎ１／３よりかなり小さい場合は、因子ｆもそうであり、これはｆが高々ｈであることによる。ｈがｎ１／３よりかなり小さい場合は、ｒはｎ２／３よりかなり大きく、因子ｆｒもｎ１／３よりかなり大きい。従って、ｎ−１のすべての因子は、ｎ１／３よりかなり小さいか、または大きい。従って、静的ディフィ−ヘルマン（Diffie-Hellman）への攻撃は回避される。
【００３６】
ｎをｈｒ＋１の形式で選択したので、ｐを選択することも必要となる。群論の標準理論では、要素の位数はその群の位数を割ることができる。ｇはＺｐ＊の要素なので、その位数ｎはＺｐ＊の位数を割ることができなければならず、それはｐ−１である。従って、ある整数ｔに対しては、ｐ＝ｔｎ＋１となる。
【００３７】
群Ｚｐ＊は、ＤＬＰを解くための指標計算アルゴリズムを有しているので、共通の実践は、ｎよりかなり大きなｐを選択することである。その考えは、位数ｎの群＜ｇ＞における一般的ＤＬＰ解法アルゴリズムに、Ｚｐ＊における指標計算アルゴリズムとほぼ同じ代償を持たせようということである。例えば、ｎが約２１６０の場合、ｐは約21024であり、従って、これら両者のＤＬＰ解法アルゴリズムは、２８０の群演算とほとんど等価の代償を有することになる。ｎに対する他の共通選択は約２２５６であり、ｐに対しては23072であり、ここにおいて両者のＤＬＰ解法アルゴリズムは約２１２８の演算をすることになる。そのような小さなｎを選択する主な優位点は、群＜ｇ＞における冪乗は、指数がより小さいのではるかに高速であるということである。
【００３８】
上記に関連するサイズのｐとｎを得るためには、ほぼ同じサイズのｔを選択しさえすればよい。第１例においては、ｔを約２１０２４−１６０＝2864として選択し、第２例ではｔを約２２８１６として選択する。ｐとｎは奇数なので、ｔを偶数として選択する必要がある。値ｔ ｍｏｄ ３、ｔ ｍｏｄ ５、・・・、についての類似の観測もまた行うことができる。
【００３９】
一般的なプロセスは、まずｎを所望の形式で選択し、ｔのいくつかの値を、ｐを素数にするのを見つけるまで数回試みる。小さな確率内では、ｐが素数であることを判定する高速テストが存在する。これらのテストは、素数でないｔに対する候補値を即座に削除する。従って、好適なｔを見出すことが非常に迅速である。実際、ｎから開始して、これがｐを見出す最良の既知の方法である。
【００４０】
ｈｒ＋１の形式のｎを構築するために、まずｈに対する近似のサイズ、または正確なｈの値を選択し、ｒの近似サイズを、ｎの所望の近似サイズで決定する。実際には、決定された範囲における種々のｈとｒを選択でき、それぞれは適合性を調べられる。ｒの選択された値は、その素数性が調べられ、ｎ＝ｈｒ＋１が計算され、ｎの素数性が調べられる。ふるいの技術を使用して、２、３、または５のような小さな素数因子を有しないｒとｎを選択することができる。これにより、その素数性を調べなければならない値ｒとｎの数が削減される。ｈを使用して、より効率的に、ｎとｒの両者に対してふるいを適用できる。ｒとｎの両者が素数であり、従って奇数なので、ｈは偶数でなければならないことに留意されたい。
【００４１】
ｈに対する近似サイズまたは値を選択するときにある注意が必要である。もっとも小さい数の選択はｈ＝２である。しかし、この選択は、小さ過ぎて、ｈ＝2は上記の攻撃を回避するが、本技術の適用において、証明可能安全性の結果をも回避してしまう。
【００４２】
ｈに対しては範囲があり、その範囲においては、上記の攻撃は証明可能安全性の結果が有効である間は阻止される。この範囲はスカラー乗法を行うのに必要な群演算の数に依存する。ｈの最適値は、この値の０.５倍から２倍の範囲のｈの値を使用できるが、（９／１６）（ｌｏｇ2ｎ）2となる。約このサイズのｈに対して、静的ディフィ−ヘルマン（Diffie-Hellman）の問題は、容認できる因子内で、静的ディフィ−ヘルマン（Diffie-Hellman）私有鍵を見出すのとほとんど同じくらい難しい。この因子は、ｈのすべての選択に対して最適化される。更に、ｈのこの選択により、上記の攻撃は約ｎ１／２の群演算と等価の代償を必要とする。これは、攻撃がもはや、ｘを見出す一般的ＤＬＰ解法アルゴリズムより優れたものではないことを意味する。従って、そのような状況ではこの攻撃は適切ではない。
【００４３】
要約すると、まず約（９／１６）（ｌｏｇ2ｎ）2のオーダーの偶数ｈを選択し、ｒとｎに対して、ｎが素数として選択されるかどうかのふるいおよび素数性テストを使用してｒとｎを検索する。最終的に、ｐ＝ｔｎ＋１が素数となるようなｔを検索する。
【００４４】
本方法の追加的な効率改善もまた可能である。本方法においては、ｐを法とする還元をより効率的にする形式をｐが有するようなｎとｔを検索する。例えば、ｐが小さなハミング重みを有している場合、ｐを法とする還元はより効率的になる。これによりモジュラ乗法と、Ｚｐ＊の群演算がより効率的になる。
【００４５】
本方法の追加的な安全性改善もまた可能である。ｒの値は、検証可能に任意に選択できる。ｒの値はハッシュ関数の出力として選択できる。
【００４６】
これら２つの追加的な改善は、ランダムに検証可能にｒを選択し、ｐに効率的なモジュラ還元を持たせる値ｔを検索することにより組み合わせることができる。
【００４７】
そのような敵対者は、特別なプロトコルの特別な実践に対しては非現実的という理由で、上記の攻撃に関心がなければ、ディフィ−ヘルマン（Diffie-Hellman）群を異なるように選択できる。ｎ１／３に近いサイズの因数ｕを回避することは不要であるかもしれないが、静的ディフィ−ヘルマン（Diffie-Hellman）問題と、一般的ディフィ−ヘルマン（Diffie-Hellman）問題の両者が難しいということが依然として望まれる。静的ディフィ−ヘルマン（Diffie-Hellman）問題を難しくするためには、約（９／１６）（ｌｏｇ2ｎ）2のサイズのｎ−１の因子が必要となる。既存の数論の知識では、任意のｎがそのようなサイズの因数を有するかどうかは明確ではない。従って、任意のｎを選択して、そのような因数を探すか、そのようなサイズの因数ｈでｎを構築することができる。後者は、ｈを選択し、任意のｒ（素数である必要はない）を選択し、ｎ＝ｈｒ＋１について素数性をテストすることで行われる。
【００４８】
短命的、または両側ディフィ−ヘルマン（Diffie-Hellman）問題が難しいことを確実にするために、既存の証明可能安全性の結果を使用できる。モーラー（Maurer）とウルフ（Wolf）の結果は、通常はサイズｎの有限体上で定義された楕円曲線である補助群を見つけることを要求する。補助群は、滑らかな位数（大きくない素数因子）を有しなければならない。そのような補助群を探すことは、相当な労力を必要とし、ｎのより大きな値に対しては、手が届かない範囲にある。実際、そのような群を見つけることは、ｎと同じサイズの因数の整数とほぼ同じ程度に難しいことが知られている。
【００４９】
デン・ボア（denBoer）のより以前の結果は、ｎ−１は滑らかであり、（短命的）ディフィ−ヘルマン（Diffie-Hellman）問題は、ほとんどＤＬＰと同程度に難しいと述べている。
【００５０】
本技術の更なる改良は、従って、ｓが滑らかな整数である、ｎ＝１＋ｓを選択する方法を含むことになる。このｓは、正確なサイズが得られるような、小さな素数の積として見出せる。そしてｎに対して素数性がテストされる。ｓのいくつかの値が試される。ｎをこのように選択する利点は一般的には、ｎ−１が（９／１６）（ｌｏｇ2ｎ）2に十分に近いサイズの因数を有することを意味し、それによりディフィ−ヘルマン（Diffie-Hellman）問題が単なる短命的ディフィ−ヘルマン（Diffie-Hellman）問題ではなく、難しいということを確実にすることである。
【００５１】
そのようなｎにより、素数ｐ＝ｔｎ＋１は上記のように見出せる。更に、この方法により、小さなハミング（Hamming）重みのような、特別構造のｎとｐを求めることもできる。
【００５２】
（楕円曲線実施形態）
原理的に、上述した技術は、楕円曲線群の場合にも機能する。より正確にいえば、ｎに対する望ましい基準は同一である。しかしこの場合は、位数ｎの生成元ｇはＺｐ＊の要素ではなく、楕円曲線群Ｅの要素である。ｍｏｄ ｐの場合、いったんｎが決定されると、群Ｚｐ＊を見出すことは比較的に単純である。このことは、楕円曲線についてはいえない。決定されたｎに対して、楕円曲線群Ｅを見出すことは依然として非常に困難である。
【００５３】
楕円曲線は、ユーザー演算を、群Ｚｐ＊に対するよりも、より効率的にするので、楕円曲線の場合は、本発明の好適な実施形態である。この実施形態の本方法は、Ｚｐ＊の場合に対するよりもわずかに複雑であるが、それにも拘わらず価値がある。
【００５４】
説明をより明確にするために、楕円曲線実施形態における、本方法の簡略化されたいくつかの形態を図３と４に示す。
【００５５】
第１簡略化形態３０において、楕円曲線は、二進数体上で定義される。そのような曲線に対して、楕円曲線群の位数を決定することは非常に容易である。簡略化された方法は、任意の曲線を選択し、点の数をカウントし、点の数が、ｎが素数のときに２ｎであることを調べ、ｎ−１が所望の基準に適合するかを調べる。好適な基準は、ｎ−１＝ｈｒであり、ここでｒは素数で、ｈは約（９／１６）（ｌｏｇ2ｎ）2である。代替としての基準は、上記の攻撃を心配しないならば、ｎ−１が滑らか、ということである。
【００５６】
第２簡略化形態において、楕円曲線は位数ｑの素数体上で定義される。ｑの値は、ｎの値を決定した後に決定される。ｎの値はｍｏｄ ｐ群の場合のように選択される。ｎの値は、好適な基準または代替基準に適合できる。そして、ＡＮＳＩｘ９.６２またはＩＥＥＥ１３.６３で記述されているような、虚数乗法が使用されてｑの値と、位数ｎを有するｑ上で定義された楕円曲線Ｅを見出す。
【００５７】
通常は、虚数乗法は、ｑのある値はユーザーによりよい効率性をもたらすので、まずｑを選択することを含む。しかし、虚数乗法はｎが最初に選択されて機能する。ｑとｎが、虚数乗法の第１フェーズである正確な数理論関係でいったん見出されれば、第２フェーズは、楕円曲線Ｅを定義する係数を決定する。
【００５８】
第２簡略化方法の不都合な点は、結果としてのｑが、ｎから約ｎ１／２の距離内のすべての整数であるｎのハッセ（Hasse）区間において、多少任意な形式を有することである。よりよいユーザーの効率のために、二進展開における小さなハミング（Hamming）重みのようなｑの特別な形式が強く所望されている。
【００５９】
すなわち、ｑとｎの両者が特別形式を有することが所望されている。ｑに対する形式は効率のためであり、ｎに対する形式は安全性のためである。これを行うために、虚数乗法の第１フェーズはわずかに修正される。所望される特別形式のｑとｎが試され、この対をテストして、虚数乗法（ＣＭ）により要求される条件に適合するかが調べられる。この条件は、比較的簡単にテストできる。ｑが与えられても、条件に合うｎを解くことは決して容易にはならず、その逆もいえる。
【００６０】
虚数乗法の第１フェーズの修正は、所望形式のｑとｎのいくつかの異なる対を試し、ｑとｎに対するＣＭ法の条件をテストし、ＣＭ法の条件が満たされるまで繰り返し、ＣＭ法の通常のプロセスを使用して、楕円曲線Ｅの定義係数ａとｂを見出すことである。
【００６１】
ＣＭ法は、既知の方法であるが、その修正形式は既知ではない。本発明の好適な実施形態で記述されたように、ＣＭ法の修正形式により、よい高効率かつより安全なディフィ−ヘルマン（Diffie-Hellman）楕円曲線群を見出すことができる。
【００６２】
この方法の妥当性を示す例として、代替基準、つまり、ｎ−１が滑らという基準を使用して、本発明の発明者は、両者が素数である、ｎ＝１＋５５（２286）とｑ＝９＋５５（２２８８）の対を見出した。ＣＭ法の技術に精通している者は、この対に対する判別式は５５であることは理解するであろう。この判別式は、クロネッカ（Kronecker）の類数(class number)が1より大きく、従って、楕円曲線の自己準同形環は、一意分解整域ではないという意味で重要である。特にこれは、楕円曲線Ｅの係数ａとｂは、所定の表からは見出せないこと、そして、位数ｑの有限体上のかなり大きな階数の多項方程式を解くことにより計算しなければならないことを意味する。
【００６３】
上述のように、本技術は所望の特性を有する領域パラメータを生成するために使用できる。これらの特性が生成される方法はまた、それ自身、攻撃に対して脆弱ではないことを確実にするために、第三者により供給された領域パラメータの効力を調べるためにも適合している。パラメータはｐとｎの値が要求された形式を満足することを確実にするために調べることもできる。パラメータがこれらの基準を満たさない場合は、領域パラメータは破棄される。
【００６４】
本発明は、ある特別な実施形態を参照して記述されてきたが、その種々の変形は、ここに添付された請求項で概要を記載される本発明の精神と範囲を逸脱することなく可能であることは当業者には明白であろう。上記に引用したすべての参考にした開示内容は、参考文献として本明細書に組み込まれている。
【特許請求の範囲】
【請求項１】
有限体Ｚｐの位数ｐと、前記有限体Ｚｐの乗法群Ｚｐ＊の部分群の位数ｎとを確立する方法であって、前記方法は、データ通信システムにおいて通信者によって行われ、前記通信者は、暗号演算を行う暗号装置を有し、
前記方法は、
ｉ）前記暗号装置が、ｎ＝ｈｒ＋１の形式のｎの値を取得するステップであって、ｈは整数であり、ｒは素数であり、ｒはｎ２／３より大きく、ｎ−１の全ての因数は、ｎ１／３よりかなり大きいか、または、ｎ１／３よりかなり小さい、ステップと、
ｉｉ）前記暗号装置が、偶数の整数ｔを取得し、ｔｎ＋１を計算して、計算された値を生成するステップと、
ｉｉｉ）前記暗号装置が、前記計算された値が素数であるか否かを調べるステップと、
ｉｖ）前記計算された値が素数である場合には、前記暗号装置が、前記有限体の素数の位数ｐとして前記計算された値を使用し、前記暗号装置が、前記乗法群の部分群の位数ｎとして前記ｎの値を使用するステップと
を包含する、方法。
【請求項２】
ｎが素数であることが必要とされ、前記暗号装置が、ｎが素数であることを調べるステップをさらに包含する、請求項１に記載の方法。
【請求項３】
ｒおよびｎは、小さい素数を有する値を除外するためにふるいをかけることによって選択される、請求項２に記載の方法。
【請求項４】
ステップｉ）は、前記暗号装置が、最初にｎおよびｈに対する所望の値を取得して、次にｎ＝ｈｒ＋１を満たすようにｒを計算することを含む、請求項２に記載の方法。
【請求項５】
ｈは、２（９／１６）（ｌｏｇ２ｎ）２未満である、請求項１〜４のいずれかに記載の方法。
【請求項６】
ｈは、０．５（９／１６）（ｌｏｇ２ｎ）２より大きい、請求項５に記載の方法。
【請求項７】
暗号システムにおいて使用する領域パラメータを検証する方法であって、前記方法は、前記暗号システムにおいて通信者によって行われ、
前記方法は、
（ａ）前記通信者の暗号装置が、ｎ＝ｈｒ＋１であることを調べるステップであって、ｈは整数であり、ｒは素数であり、ｒはｎ２／３より大きく、ｎ−１の全ての因数は、ｎ１／３よりかなり大きいか、または、ｎ１／３よりかなり小さい、ステップと、
（ｂ）前記暗号装置が、ｐ＝ｔｎ＋１であることを調べるステップであって、ｔは偶数の整数である、ステップと
を包含する、方法。
【請求項８】
請求項１〜７のいずれかに記載の方法を行うコンピュータ実行可能な命令を格納したコンピュータ読み取り可能媒体。
【請求項９】
楕円曲線群の部分群の位数を確立する方法であって、前記方法は、データ通信システムにおいて通信者によって行われ、前記通信者は、暗号演算を行う暗号装置を有し、
前記方法は、
ａ）前記暗号装置が、ｎ＝ｈｒ＋１の形式のｎの値を取得するステップであって、ｈは整数であり、ｒは素数であり、ｒはｎ２／３より大きく、ｎ−１の全ての因数は、ｎ１／３よりかなり大きいか、または、ｎ１／３よりかなり小さい、ステップと、
ｂ）前記暗号装置が、前記楕円曲線群の部分群の位数として前記ｎの値を使用するステップと
を包含する、方法。
【請求項１０】
前記値ｎが素数である、請求項９に記載の方法。
【請求項１１】
ステップａ）は、
前記暗号装置が、ランダムな楕円曲線群を生成するステップと、
前記暗号装置が、前記楕円曲線群の位数の素因数がｎ＝ｈｒ＋１で表され得るか否かをテストするステップと、
前記素因数がｎ＝ｈｒ＋１で表され得る場合には、前記ランダムな楕円曲線群を前記楕円曲線群として使用するステップと
を含む、請求項１０に記載の方法。
【請求項１２】
前記暗号装置が、虚数乗法アルゴリズムにおいて前記値ｎを用いて、前記楕円曲線群の式を定義する係数を確立するステップをさらに含む、請求項１０に記載の方法。
【請求項１３】
前記暗号装置が、前記楕円曲線群が定義される素数体の位数ｑを生成するステップと、前記虚数乗法アルゴリズムにおいて前記位数ｑおよび前記値ｎを用いて、前記楕円曲線群の式を定義する係数を確立するステップとをさらに含む、請求項１２に記載の方法。
【請求項１４】
前記暗号装置が、前記ｑの形式を指定する、請求項１３に記載の方法。
【請求項１５】
ｒおよびｎは、小さい素数を有する値を除外するためにふるいをかけることによって選択される、請求項１０〜１４のいずれかに記載の方法。
【請求項１６】
ステップａ）は、前記暗号装置が、最初にｎおよびｈに対する所望の値を取得して、次にｎ＝ｈｒ＋１を満たすようにｒを計算することを含む、請求項１０〜１４のいずれかに記載の方法。
【請求項１７】
ｈは、２（９／１６）（ｌｏｇ２ｎ）２未満である、請求項９〜１６のいずれかに記載の方法。
【請求項１８】
ｈは、０．５（９／１６）（ｌｏｇ２ｎ）２より大きい、請求項１７に記載の方法。
【請求項１９】
請求項９〜１８のいずれかに記載の方法を行うコンピュータ実行可能な命令を格納したコンピュータ読み取り可能媒体。
【請求項１】
有限体Ｚｐの位数ｐと、前記有限体Ｚｐの乗法群Ｚｐ＊の部分群の位数ｎとを確立する方法であって、前記方法は、データ通信システムにおいて通信者によって行われ、前記通信者は、暗号演算を行う暗号装置を有し、
前記方法は、
ｉ）前記暗号装置が、ｎ＝ｈｒ＋１の形式のｎの値を取得するステップであって、ｈは整数であり、ｒは素数であり、ｒはｎ２／３より大きく、ｎ−１の全ての因数は、ｎ１／３よりかなり大きいか、または、ｎ１／３よりかなり小さい、ステップと、
ｉｉ）前記暗号装置が、偶数の整数ｔを取得し、ｔｎ＋１を計算して、計算された値を生成するステップと、
ｉｉｉ）前記暗号装置が、前記計算された値が素数であるか否かを調べるステップと、
ｉｖ）前記計算された値が素数である場合には、前記暗号装置が、前記有限体の素数の位数ｐとして前記計算された値を使用し、前記暗号装置が、前記乗法群の部分群の位数ｎとして前記ｎの値を使用するステップと
を包含する、方法。
【請求項２】
ｎが素数であることが必要とされ、前記暗号装置が、ｎが素数であることを調べるステップをさらに包含する、請求項１に記載の方法。
【請求項３】
ｒおよびｎは、小さい素数を有する値を除外するためにふるいをかけることによって選択される、請求項２に記載の方法。
【請求項４】
ステップｉ）は、前記暗号装置が、最初にｎおよびｈに対する所望の値を取得して、次にｎ＝ｈｒ＋１を満たすようにｒを計算することを含む、請求項２に記載の方法。
【請求項５】
ｈは、２（９／１６）（ｌｏｇ２ｎ）２未満である、請求項１〜４のいずれかに記載の方法。
【請求項６】
ｈは、０．５（９／１６）（ｌｏｇ２ｎ）２より大きい、請求項５に記載の方法。
【請求項７】
暗号システムにおいて使用する領域パラメータを検証する方法であって、前記方法は、前記暗号システムにおいて通信者によって行われ、
前記方法は、
（ａ）前記通信者の暗号装置が、ｎ＝ｈｒ＋１であることを調べるステップであって、ｈは整数であり、ｒは素数であり、ｒはｎ２／３より大きく、ｎ−１の全ての因数は、ｎ１／３よりかなり大きいか、または、ｎ１／３よりかなり小さい、ステップと、
（ｂ）前記暗号装置が、ｐ＝ｔｎ＋１であることを調べるステップであって、ｔは偶数の整数である、ステップと
を包含する、方法。
【請求項８】
請求項１〜７のいずれかに記載の方法を行うコンピュータ実行可能な命令を格納したコンピュータ読み取り可能媒体。
【請求項９】
楕円曲線群の部分群の位数を確立する方法であって、前記方法は、データ通信システムにおいて通信者によって行われ、前記通信者は、暗号演算を行う暗号装置を有し、
前記方法は、
ａ）前記暗号装置が、ｎ＝ｈｒ＋１の形式のｎの値を取得するステップであって、ｈは整数であり、ｒは素数であり、ｒはｎ２／３より大きく、ｎ−１の全ての因数は、ｎ１／３よりかなり大きいか、または、ｎ１／３よりかなり小さい、ステップと、
ｂ）前記暗号装置が、前記楕円曲線群の部分群の位数として前記ｎの値を使用するステップと
を包含する、方法。
【請求項１０】
前記値ｎが素数である、請求項９に記載の方法。
【請求項１１】
ステップａ）は、
前記暗号装置が、ランダムな楕円曲線群を生成するステップと、
前記暗号装置が、前記楕円曲線群の位数の素因数がｎ＝ｈｒ＋１で表され得るか否かをテストするステップと、
前記素因数がｎ＝ｈｒ＋１で表され得る場合には、前記ランダムな楕円曲線群を前記楕円曲線群として使用するステップと
を含む、請求項１０に記載の方法。
【請求項１２】
前記暗号装置が、虚数乗法アルゴリズムにおいて前記値ｎを用いて、前記楕円曲線群の式を定義する係数を確立するステップをさらに含む、請求項１０に記載の方法。
【請求項１３】
前記暗号装置が、前記楕円曲線群が定義される素数体の位数ｑを生成するステップと、前記虚数乗法アルゴリズムにおいて前記位数ｑおよび前記値ｎを用いて、前記楕円曲線群の式を定義する係数を確立するステップとをさらに含む、請求項１２に記載の方法。
【請求項１４】
前記暗号装置が、前記ｑの形式を指定する、請求項１３に記載の方法。
【請求項１５】
ｒおよびｎは、小さい素数を有する値を除外するためにふるいをかけることによって選択される、請求項１０〜１４のいずれかに記載の方法。
【請求項１６】
ステップａ）は、前記暗号装置が、最初にｎおよびｈに対する所望の値を取得して、次にｎ＝ｈｒ＋１を満たすようにｒを計算することを含む、請求項１０〜１４のいずれかに記載の方法。
【請求項１７】
ｈは、２（９／１６）（ｌｏｇ２ｎ）２未満である、請求項９〜１６のいずれかに記載の方法。
【請求項１８】
ｈは、０．５（９／１６）（ｌｏｇ２ｎ）２より大きい、請求項１７に記載の方法。
【請求項１９】
請求項９〜１８のいずれかに記載の方法を行うコンピュータ実行可能な命令を格納したコンピュータ読み取り可能媒体。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−１９５５９（Ｐ２０１２−１９５５９Ａ）
【公開日】平成２４年１月２６日（２０１２．１．２６）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２３３８２３（Ｐ２０１１−２３３８２３）
【出願日】平成２３年１０月２５日（２０１１．１０．２５）
【分割の表示】特願２００７−５４０７４６（Ｐ２００７−５４０７４６）の分割
【原出願日】平成１７年１１月１１日（２００５．１１．１１）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
【公開日】平成２４年１月２６日（２０１２．１．２６）
【国際特許分類】
【出願番号】特願２０１１−２３３８２３（Ｐ２０１１−２３３８２３）
【出願日】平成２３年１０月２５日（２０１１．１０．２５）
【分割の表示】特願２００７−５４０７４６（Ｐ２００７−５４０７４６）の分割
【原出願日】平成１７年１１月１１日（２００５．１１．１１）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
[ Back to top ]