有限体Zpの位数pと、前記有限体Zpの乗法群Zpの部分群の位数nとを確立する方法であって、前記方法は、データ通信システムにおいて通信者によって行われ、前記通信者は、暗号演算を行う暗号装置を有し、前記方法は、i前記暗号装置が、n=hr1の形式のnの値を取得するステップであって、hは整数であり、rは素数であり、rはn2/3より大きく、n-1の全ての因数は、n1/3よりかなり大きいか、または、n1/3よりかなり小さい、ステップと、ii前記暗号装置が、偶数の整数tを取得し、tn1を計算して、計算された値を生成するステップと、iii前記暗号装置が、前記計算された値が素数であるか否かを調べるステップと、iv前記計算された値が素数である場合には、前記暗号装置が、前記有限体の素数の位数pとして前記計算された値を使用し、前記暗号装置が、前記乗法群の部分群の位数nとして前記nの値を使用するステップとを包含する、方法。nが素数であることが必要とされ、前記暗号装置が、nが素数であることを調べるステップをさらに包含する、請求項1に記載の方法。rおよびnは、小さい素数を有する値を除外するためにふるいをかけることによって選択される、請求項2に記載の方法。ステップiは、前記暗号装置が、最初にnおよびhに対する所望の値を取得して、次にn=hr1を満たすようにrを計算することを含む、請求項2に記載の方法。hは、29/16log2n2未満である、請求項1~4のいずれかに記載の方法。hは、0.59/16log2n2より大きい、請求項5に記載の方法。暗号システムにおいて使用する領域パラメータを検証する方法であって、前記方法は、前記暗号システムにおいて通信者によって行われ、前記方法は、a前記通信者の暗号装置が、n=hr1であることを調べるステップであって、hは整数であり、rは素数であり、rはn2/3より大きく、n-1の全ての因数は、n1/3よりかなり大きいか、または、n1/3よりかなり小さい、ステップと、b前記暗号装置が、p=tn1であることを調べるステップであって、tは偶数の整数である、ステップとを包含する、方法。請求項1~7のいずれかに記載の方法を行うコンピュータ実行可能な命令を格納したコンピュータ読み取り可能媒体。楕円曲線群の部分群の位数を確立する方法であって、前記方法は、データ通信システムにおいて通信者によって行われ、前記通信者は、暗号演算を行う暗号装置を有し、前記方法は、a前記暗号装置が、n=hr1の形式のnの値を取得するステップであって、hは整数であり、rは素数であり、rはn2/3より大きく、n-1の全ての因数は、n1/3よりかなり大きいか、または、n1/3よりかなり小さい、ステップと、b前記暗号装置が、前記楕円曲線群の部分群の位数として前記nの値を使用するステップとを包含する、方法。前記値nが素数である、請求項9に記載の方法。ステップaは、前記暗号装置が、ランダムな楕円曲線群を生成するステップと、前記暗号装置が、前記楕円曲線群の位数の素因数がn=hr1で表され得るか否かをテストするステップと、前記素因数がn=hr1で表され得る場合には、前記ランダムな楕円曲線群を前記楕円曲線群として使用するステップとを含む、請求項10に記載の方法。前記暗号装置が、虚数乗法アルゴリズムにおいて前記値nを用いて、前記楕円曲線群の式を定義する係数を確立するステップをさらに含む、請求項10に記載の方法。前記暗号装置が、前記楕円曲線群が定義される素数体の位数qを生成するステップと、前記虚数乗法アルゴリズムにおいて前記位数qおよび前記値nを用いて、前記楕円曲線群の式を定義する係数を確立するステップとをさらに含む、請求項12に記載の方法。前記暗号装置が、前記qの形式を指定する、請求項13に記載の方法。rおよびnは、小さい素数を有する値を除外するためにふるいをかけることによって選択される、請求項10~14のいずれかに記載の方法。ステップaは、前記暗号装置が、最初にnおよびhに対する所望の値を取得して、次にn=hr1を満たすようにrを計算することを含む、請求項10~14のいずれかに記載の方法。hは、29/16log2n2未満である、請求項9~16のいずれかに記載の方法。hは、0.59/16log2n2より大きい、請求項17に記載の方法。請求項9~18のいずれかに記載の方法を行うコンピュータ実行可能な命令を格納したコンピュータ読み取り可能媒体。1つの態様において、本発明により、静的ディフィ-ヘルマンDiffieHellman鍵共有プロトコルが、敵対者による能動的攻撃を防ぐのための、modp群を選択する方法が提供され、本方法は、偶数値hを選択するステップと、rとnが素数のとき、n=hr1という関係を満たすrとnの値を探すステップと、pが素数のとき、p=tn1を計算するためのtの値を探すステップを含む。別の態様において、本発明により、静的ディフィ-ヘルマンDiffieHellman鍵共有プロトコルが敵対者による能動的攻撃を防ぐための、二進数体上で定義された楕円曲線群を選択する方法が提供され、本方法は、任意の曲線を選択するステップと、曲線上の点の数をカウントするステップと、nが素数で、n-1が好適な基準を満たすとき、曲線上の点の数が2nであることを調べるステップを含む。更に別の態様において、本発明により、静的ディフィ-ヘルマンDiffieHellman鍵共有プロトコルが敵対者による能動的攻撃を防ぐための、位数qの素数体上で定義された楕円曲線群を選択する方法が提供され、本方法は、nが素数でn-1が好適な基準を満たすとき、n=hr1を計算するステップと、nについての虚数乗法を実行して、値qと、位数nを有するq上で定義された楕円曲線Eを生成するステップ含む。例えば、本発明は以下の項目を提供する。項目1素数の位数pと位数nの生成元gを有する有限群Gのパラメータを決定する方法であって、ihが整数で、rが素数で、hがrと比較して相対的に小さい場合に、n=hr1の形式のnの値を選択するステップと、ii偶数の整数tを選択して、tが偶数の整数の場合の、tn1を計算するステップと、iiip=tn1の計算された値に対して、素数性を調べるステップと、iv位数p上の計算された値が素数の場合は、それを採用するステップと、を備える方法。項目2nの近似値が選択され、hがn1/3よりもかなり小さくなるようにhが選択される請求項1に記載の方法。項目3nは素数であることが要求され、nの値は素数性がテストされる項目1に記載の方法。項目4rとnの値は、小さな素数を有する値をふるいにかけて除外することにより選択される項目1に記載の方法。項目5上記群は、楕円曲線群であり、上記方法は、曲線上の点をカウントし、点の数が2nであることを判定するステップを含む項目1に記載の方法。項目6位数pと位数nの生成元gを有する有限群Gであって、hが整数で、rが素数の場合に、n=hr1であり、tが整数の場合に、p=tn1である有限群G。項目7位数pと位数nを有する生成元gを有する群Gの、暗号システムにおける使用のために領域パラメータを検証する方法であって、hが整数であり、rが素数の場合にn=hr1であることと、tが整数の場合に、p=tn1であることを判定するステップを備える方法。図1を参照すると、1組の通信者A、Bは、データ通信リンク12により接続されている。各通信者A、Bは、暗号装置14を有しており、この暗号装置は、リンク1上での確実な通信を可能にするために確立されたプロトコルに従って、公開鍵暗号操作を行う。暗号装置14は、他のエンティティと共有されているパラメータの暗号領域内で作動する。通信者A、Bに共有された領域パラメータは、群Gと、群Gの位数pと、位数nの群の生成元gを含む。本発明は、楕円曲線群と、有限体の乗法的部分群、より一般的にはmodp群として知られている、この両者に適用される。modp群はより理解し易いので、modpの実施形態20をまず説明して、その概略を図2に示す。両者の場合に共通する本発明の態様は、このように更に容易に理解できる。それにも拘わらず、本発明の好適な実施形態は、楕円曲線群についてであるが、これは性能特性においていくつかの優位点を有するからである。modpの実施形態説明を簡単にするために、Zpにおけるディフィ-ヘルマンDiffieHellman基点または生成元gは素数の位数nを有すると仮定する。当業者にとっては、これはgが素数でない位数を有する場合にも拡張できることは明白であろう。領域名パラメータの安全性は、n-1の整数因子uのサイズに依存する。ある既知の因数uがn1/3に近いときは、上記の攻撃10は、約3n1/3の代償を必要とする。これは、約n1/2の代償を必要とする一般的DLP攻撃よりかなり小さい。任意のnは、一般的にn1/3に近い因数uを有することは知られているので、nをランダムに選択することは、上記の攻撃10を回避することにはならない。従来技術においては、nは一般的にはハッシュ関数の出力として選択されたが、これはnを効果的に任意の数にするが、攻撃を回避しない。nを適切に選択することにより、n1/3に近い因数を有することを回避できることが判明した。パラメータの選択とテストは、必要な計算を実行するようにプログラムされた計算装置を使用して行えることは理解されよう。そのような計算の結果は、装置14上で暗号機能を実践するために使用できる領域パラメータの集合である。第1実施形態において、そのような因子は、n=hr1を選択することにより回避され、ここでrは素数で、hはrと比較して相対的に小さな整数であり、n1/3よりは十分に小さい整数である。n-1の因子は、fまたはfrの形式であり、ここでfはhの因子である。hがn1/3よりかなり小さい場合は、因子fもそうであり、これはfが高々hであることによる。hがn1/3よりかなり小さい場合は、rはn2/3よりかなり大きく、因子frもn1/3よりかなり大きい。従って、n-1のすべての因子は、n1/3よりかなり小さいか、または大きい。従って、静的ディフィ-ヘルマンDiffieHellmanへの攻撃は回避される。nをhr1の形式で選択したので、pを選択することも必要となる。群論の標準理論では、要素の位数はその群の位数を割ることができる。gはZpの要素なので、その位数nはZpの位数を割ることができなければならず、それはp-1である。従って、ある整数tに対しては、p=tn1となる。群Zpは、DLPを解くための指標計算アルゴリズムを有しているので、共通の実践は、nよりかなり大きなpを選択することである。その考えは、位数nの群<g>における一般的DLP解法アルゴリズムに、Zpにおける指標計算アルゴリズムとほぼ同じ代償を持たせようということである。例えば、nが約2160の場合、pは約21024であり、従って、これら両者のDLP解法アルゴリズムは、280の群演算とほとんど等価の代償を有することになる。nに対する他の共通選択は約2256であり、pに対しては23072であり、ここにおいて両者のDLP解法アルゴリズムは約2128の演算をすることになる。そのような小さなnを選択する主な優位点は、群<g>における冪乗は、指数がより小さいのではるかに高速であるということである。上記に関連するサイズのpとnを得るためには、ほぼ同じサイズのtを選択しさえすればよい。第1例においては、tを約21024-160=2864として選択し、第2例ではtを約22816として選択する。pとnは奇数なので、tを偶数として選択する必要がある。値tmod3、tmod5、、についての類似の観測もまた行うことができる。一般的なプロセスは、まずnを所望の形式で選択し、tのいくつかの値を、pを素数にするのを見つけるまで数回試みる。小さな確率内では、pが素数であることを判定する高速テストが存在する。これらのテストは、素数でないtに対する候補値を即座に削除する。従って、好適なtを見出すことが非常に迅速である。実際、nから開始して、これがpを見出す最良の既知の方法である。hr1の形式のnを構築するために、まずhに対する近似のサイズ、または正確なhの値を選択し、rの近似サイズを、nの所望の近似サイズで決定する。実際には、決定された範囲における種々のhとrを選択でき、それぞれは適合性を調べられる。rの選択された値は、その素数性が調べられ、n=hr1が計算され、nの素数性が調べられる。ふるいの技術を使用して、2、3、または5のような小さな素数因子を有しないrとnを選択することができる。これにより、その素数性を調べなければならない値rとnの数が削減される。hを使用して、より効率的に、nとrの両者に対してふるいを適用できる。rとnの両者が素数であり、従って奇数なので、hは偶数でなければならないことに留意されたい。hに対する近似サイズまたは値を選択するときにある注意が必要である。もっとも小さい数の選択はh=2である。しかし、この選択は、小さ過ぎて、h=2は上記の攻撃を回避するが、本技術の適用において、証明可能安全性の結果をも回避してしまう。hに対しては範囲があり、その範囲においては、上記の攻撃は証明可能安全性の結果が有効である間は阻止される。この範囲はスカラー乗法を行うのに必要な群演算の数に依存する。hの最適値は、この値の05倍から2倍の範囲のhの値を使用できるが、9/16log2n2となる。約このサイズのhに対して、静的ディフィ-ヘルマンDiffieHellmanの問題は、容認できる因子内で、静的ディフィ-ヘルマンDiffieHellman私有鍵を見出すのとほとんど同じくらい難しい。この因子は、hのすべての選択に対して最適化される。更に、hのこの選択により、上記の攻撃は約n1/2の群演算と等価の代償を必要とする。これは、攻撃がもはや、xを見出す一般的DLP解法アルゴリズムより優れたものではないことを意味する。従って、そのような状況ではこの攻撃は適切ではない。要約すると、まず約9/16log2n2のオーダーの偶数hを選択し、rとnに対して、nが素数として選択されるかどうかのふるいおよび素数性テストを使用してrとnを検索する。最終的に、p=tn1が素数となるようなtを検索する。本方法の追加的な効率改善もまた可能である。本方法においては、pを法とする還元をより効率的にする形式をpが有するようなnとtを検索する。例えば、pが小さなハミング重みを有している場合、pを法とする還元はより効率的になる。これによりモジュラ乗法と、Zpの群演算がより効率的になる。本方法の追加的な安全性改善もまた可能である。rの値は、検証可能に任意に選択できる。rの値はハッシュ関数の出力として選択できる。これら2つの追加的な改善は、ランダムに検証可能にrを選択し、pに効率的なモジュラ還元を持たせる値tを検索することにより組み合わせることができる。そのような敵対者は、特別なプロトコルの特別な実践に対しては非現実的という理由で、上記の攻撃に関心がなければ、ディフィ-ヘルマンDiffieHellman群を異なるように選択できる。n1/3に近いサイズの因数uを回避することは不要であるかもしれないが、静的ディフィ-ヘルマンDiffieHellman問題と、一般的ディフィ-ヘルマンDiffieHellman問題の両者が難しいということが依然として望まれる。静的ディフィ-ヘルマンDiffieHellman問題を難しくするためには、約9/16log2n2のサイズのn-1の因子が必要となる。既存の数論の知識では、任意のnがそのようなサイズの因数を有するかどうかは明確ではない。従って、任意のnを選択して、そのような因数を探すか、そのようなサイズの因数hでnを構築することができる。後者は、hを選択し、任意のr素数である必要はないを選択し、n=hr1について素数性をテストすることで行われる。短命的、または両側ディフィ-ヘルマンDiffieHellman問題が難しいことを確実にするために、既存の証明可能安全性の結果を使用できる。モーラーMaurerとウルフWolfの結果は、通常はサイズnの有限体上で定義された楕円曲線である補助群を見つけることを要求する。補助群は、滑らかな位数大きくない素数因子を有しなければならない。そのような補助群を探すことは、相当な労力を必要とし、nのより大きな値に対しては、手が届かない範囲にある。実際、そのような群を見つけることは、nと同じサイズの因数の整数とほぼ同じ程度に難しいことが知られている。デンボアdenBoerのより以前の結果は、n-1は滑らかであり、短命的ディフィ-ヘルマンDiffieHellman問題は、ほとんどDLPと同程度に難しいと述べている。本技術の更なる改良は、従って、sが滑らかな整数である、n=1sを選択する方法を含むことになる。このsは、正確なサイズが得られるような、小さな素数の積として見出せる。そしてnに対して素数性がテストされる。sのいくつかの値が試される。nをこのように選択する利点は一般的には、n-1が9/16log2n2に十分に近いサイズの因数を有することを意味し、それによりディフィ-ヘルマンDiffieHellman問題が単なる短命的ディフィ-ヘルマンDiffieHellman問題ではなく、難しいということを確実にすることである。そのようなnにより、素数p=tn1は上記のように見出せる。更に、この方法により、小さなハミングHamming重みのような、特別構造のnとpを求めることもできる。楕円曲線実施形態原理的に、上述した技術は、楕円曲線群の場合にも機能する。より正確にいえば、nに対する望ましい基準は同一である。しかしこの場合は、位数nの生成元gはZpの要素ではなく、楕円曲線群Eの要素である。modpの場合、いったんnが決定されると、群Zpを見出すことは比較的に単純である。このことは、楕円曲線についてはいえない。決定されたnに対して、楕円曲線群Eを見出すことは依然として非常に困難である。楕円曲線は、ユーザー演算を、群Zpに対するよりも、より効率的にするので、楕円曲線の場合は、本発明の好適な実施形態である。この実施形態の本方法は、Zpの場合に対するよりもわずかに複雑であるが、それにも拘わらず価値がある。説明をより明確にするために、楕円曲線実施形態における、本方法の簡略化されたいくつかの形態を図3と4に示す。第1簡略化形態30において、楕円曲線は、二進数体上で定義される。そのような曲線に対して、楕円曲線群の位数を決定することは非常に容易である。簡略化された方法は、任意の曲線を選択し、点の数をカウントし、点の数が、nが素数のときに2nであることを調べ、n-1が所望の基準に適合するかを調べる。好適な基準は、n-1=hrであり、ここでrは素数で、hは約9/16log2n2である。代替としての基準は、上記の攻撃を心配しないならば、n-1が滑らか、ということである。第2簡略化形態において、楕円曲線は位数qの素数体上で定義される。qの値は、nの値を決定した後に決定される。nの値はmodp群の場合のように選択される。nの値は、好適な基準または代替基準に適合できる。そして、ANSIx962またはIEEE1363で記述されているような、虚数乗法が使用されてqの値と、位数nを有するq上で定義された楕円曲線Eを見出す。通常は、虚数乗法は、qのある値はユーザーによりよい効率性をもたらすので、まずqを選択することを含む。しかし、虚数乗法はnが最初に選択されて機能する。qとnが、虚数乗法の第1フェーズである正確な数理論関係でいったん見出されれば、第2フェーズは、楕円曲線Eを定義する係数を決定する。第2簡略化方法の不都合な点は、結果としてのqが、nから約n1/2の距離内のすべての整数であるnのハッセHasse区間において、多少任意な形式を有することである。よりよいユーザーの効率のために、二進展開における小さなハミングHamming重みのようなqの特別な形式が強く所望されている。すなわち、qとnの両者が特別形式を有することが所望されている。qに対する形式は効率のためであり、nに対する形式は安全性のためである。これを行うために、虚数乗法の第1フェーズはわずかに修正される。所望される特別形式のqとnが試され、この対をテストして、虚数乗法CMにより要求される条件に適合するかが調べられる。この条件は、比較的簡単にテストできる。qが与えられても、条件に合うnを解くことは決して容易にはならず、その逆もいえる。虚数乗法の第1フェーズの修正は、所望形式のqとnのいくつかの異なる対を試し、qとnに対するCM法の条件をテストし、CM法の条件が満たされるまで繰り返し、CM法の通常のプロセスを使用して、楕円曲線Eの定義係数aとbを見出すことである。CM法は、既知の方法であるが、その修正形式は既知ではない。本発明の好適な実施形態で記述されたように、CM法の修正形式により、よい高効率かつより安全なディフィ-ヘルマンDiffieHellman楕円曲線群を見出すことができる。この方法の妥当性を示す例として、代替基準、つまり、n-1が滑らという基準を使用して、本発明の発明者は、両者が素数である、n=1552286とq=9552288の対を見出した。CM法の技術に精通している者は、この対に対する判別式は55であることは理解するであろう。この判別式は、クロネッカKroneckerの類数が1より大きく、従って、楕円曲線の自己準同形環は、一意分解整域ではないという意味で重要である。特にこれは、楕円曲線Eの係数aとbは、所定の表からは見出せないこと、そして、位数qの有限体上のかなり大きな階数の多項方程式を解くことにより計算しなければならないことを意味する。上述のように、本技術は所望の特性を有する領域パラメータを生成するために使用できる。これらの特性が生成される方法はまた、それ自身、攻撃に対して脆弱ではないことを確実にするために、第三者により供給された領域パラメータの効力を調べるためにも適合している。パラメータはpとnの値が要求された形式を満足することを確実にするために調べることもできる。パラメータがこれらの基準を満たさない場合は、領域パラメータは破棄される。本発明は、ある特別な実施形態を参照して記述されてきたが、その種々の変形は、ここに添付された請求項で概要を記載される本発明の精神と範囲を逸脱することなく可能であることは当業者には明白であろう。上記に引用したすべての参考にした開示内容は、参考文献として本明細書に組み込まれている。