(57)【要約】コンピュータプログラムは、暗号化の適用のための推定素数の高速な生成および検査を提供する。コンピュータハードウェアで実行されるプログラム命令は、スマート増分プログラム機能を含むステップを実行し、この機能は選択された組をなす非常に小さな素数に対して相対的に素数である一致する値の表を用いて、連続的な候補を見つけて、次の候補への増分を識別することにより、試し割算にかけられる必要のない非常に明白な構成要素の約４分の３をふるいにかける。プログラム命令はまた、小さな素数の検査プログラム機能を含み、この機能は非常に大きな候補それ自体ではなく、モジュール単位の減じられた値に対して割算を行なうことによって、小さな素数のリストに対する試し割算を加速する。小さな素数検査を通過した候補の約１０％のみが次に、より厳しいが時間のかかる推定素数検査にかけられる。【特許請求の範囲】
【請求項１】
機密保護のために大きな素数に依存したコンピュータで実現される暗号化プログラム適用において基本的な構成要素として用いるための方法であって、
前記方法は前記暗号化適用で用いるための１以上の推定素数候補を生成し、
前記方法は以下の一連のステップを実行する暗号化適用のハードウェアで実行される命令を含み、前記一連のステップは、
指定された第１のビットサイズを有する擬似ランダム数を与えるステップと、
第１の増分と合計することによって、前記擬似ランダム数から第１の候補を生成するステップとを含み、前記第１の増分は、前記第１の候補が１組の非常に小さな素数にとって相対的に素数となるように選択され、前記一連のステップはさらに、
前記非常に小さな素数以外の小さな素数のリストに対する試し割算によって、前記リストにおける前記小さな素数のすべてに対して相対的に素数である候補が見つかるまで、前記第１の候補で始まる連続した候補を繰り返して検査するステップとを含み、連続した候補は以下のステップによって検査され、前記以下のステップは、
（ｉ）  第１の候補の１組のモジュール減少を計算するステップを含み、この１組のモジュール減少の要素は、第１の候補モジュールに一致する残余であり、各々は前記小さな素数のリストにおける異なるグループの素数の対応する組の積であり、前記積は、少なくとも４の因数ほど前記第１のビットサイズよりも小さい、指定された最大の第２のビットサイズを有し、前記以下のステップはさらに、
（ｉｉ）各々の連続した候補のために更新される主な増分値を維持するステップを含み、主な増分値の各々の連続した更新は、前記第１の候補の値に追加されたときに、組をなす非常に小さな素数に対して相対的に素数である次の連続した候補を与えるステップと、
（ｉｉｉ）主な増分値の最近の更新によって増分された１組のモジュール減少の各々の要素について、候補が合成数であることがわかるまで、対応するグループの素数における素数の各々に対する試し割算によって増分要素を検査して、残余がゼロであるかどうかを決定し、そうであれば現在の候補を合成数として指定するステップとを含み、前記一連のステップはさらに、
前記リストにおける前記小さな素数のすべてに対して相対的に素数である候補を見つけた後で、第１の候補に現在の主な増分を加えたものに等しい前記候補を、少なくとも１つの既知の厳しい推定素数検査にかけて、候補が何らかの１つの前記厳しい検査に従って合成数であることがわかった場合、以前の通り小さな素数の試し割算および前記厳しい検査の双方を通過した候補が見つかるまで、小さな素数のリストに対する試し割算による連続した候補の検査を継続して、このような候補は推定素数値と考えられ、前記一連のステップはさらに、
前記暗号化プログラムで推定素数値を用いるステップを含む、方法。
【請求項２】
ハードウェアの処理は、汎用プログラマブルコンピュータシステムを含み、プログラムは、前記コンピュータシステムによって読取り可能なソフトウェアの形態である、請求項１に記載のプログラム。
【請求項３】
ハードウェアの処理は集積回路チップを含み、プログラムは前記チップによってアクセス可能なファームウェアの形態である、請求項１に記載のプログラム。
【請求項４】
ハードウェアの処理は、前記プログラムを実現するように構成されたフィールドプログラマブル論理アレイ等の構成可能な論理チップを含む、請求項１に記載のプログラム。
【請求項５】
プログラムステップを実行するように特別に設計された特定用途向け集積回路の形態である、請求項１に記載のプログラム。
【請求項６】
第１のビットサイズは少なくとも２５６ビットである、請求項１に記載のプログラム。
【請求項７】
第２のビットサイズは３２ビットである、請求項１に記載のプログラム。
【請求項８】
前記１組の非常に小さな素数は、２，３，５および７を含む、請求項１に記載のプログラム。
【請求項９】
前記小さな素数のリストは、１１から２４１の間のすべての連続した素数を含む、請求項８に記載のプログラム。
【請求項１０】
前記第１の増分は、擬似ランダム数モジュール２１０に一致する残余を、ゼロから２０９の値を示す２１０要素の表と比較することによって見つけられ、２，３，５および７のすべてに対して相対的に素数である値に対応する表の要素は、表において２，３，５または７のいずれかで割り切れる値に対応する要素から区別され、前記比較は、前記残余を、２，３，５および７のすべてに対して相対的に素数である値にもたらす増分を識別するために行なわれる、請求項８に記載のプログラム。
【請求項１１】
前記主な増分は、前記２１０要素の表と比較することによって見つけられ、各々の連続した素数増分値は、前記残余を表における次の相対的に素数である値にもたらす、請求項１０に記載のプログラム。
【請求項１２】
前記既知の厳しい推定素数検査はミラー・ラビン検査を含む、請求項１に記載のプログラム。
【請求項１３】
前記既知の厳しい推定素数検査はフェルマー検査を含む、請求項１に記載のプログラム。
【請求項１４】
推定素数値を用いて少なくとも１つの暗号キーを生成する、請求項１に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野
本発明は、素数生成、キー生成および擬似ランダム数生成のような基本的な暗号化構成要素を含む暗号法に関する。本発明は特に、コンピュータソフトウェア暗号方法、ならびに特に速度に重点を置いた、素数生成および推定素数のために生成された候補の検査を行なう、対応するプログラム化されたハードウェア装置に関する。
【背景技術】
【０００２】
背景技術
大きな素数または推定素数は、さまざまな暗号化適用にとって有用である。たとえば、素数は、（ＲＳＡ等の）公開鍵暗号システムにおいてキーペアを生成する際に用いられる。さらに、擬似ランダム数シーケンスは、ヴァン・デン・エンデ（Van Den Ende）に付与された米国特許第４，７８０，８４０号にあるような素数を用いて生成することができる。このようなシーケンスは次に、秘密通信のためにストリーム暗号で用いることができる。
【０００３】
これらの種類の適用例における必要とされるサイズの推定素数が増加すると、暗号方法に関わるプログラム化されたコンピュータシステムまたはチップがこのような素数を迅速に生成するための効率的な方法が非常に重要になる。多くの適用例において、さらなる機密保護および柔軟性のために、大きなランダム素数は、１組の記憶され、予め計算された素数値に依存するのではなく、使用の前に即座に生成されることが望ましい。あいにく、大きな素数生成における問題は、推定素数の候補が、時間がかかるもしくは大量の演算能力を必要とするか、またはその双方である（ミラー・ラビン（Miller-Rabin）またはフェルマー（Fermat）等の）アルゴリズムを通して検査されなければならないということにある。可能性の低い候補を迅速に排除する技術によって、推定素数が識別される前にこのような厳しい検査を行なう必要回数が最小になる。
【０００４】
米国特許第４，３５１，９８２号で、ミラー等（Miller et at.)は、シーケンスにおいて先行する素数Ｐを新たな値ｈＰ＋１（ｈはランダムである）に増分し、次に新たな値に素数性があるかどうかを検査することによって、既知の素数で始まるシーケンスの素数を生成することを開示している。値が合成数であるとわかったときはいつでも、ｈは２ほど増分され、新しいｈＰ＋１が検査される。一旦値ｈＰ＋１が素数であるとわかると、これは次のサーチのために新しい素数Ｐとして用いられる。
【０００５】
Ｐ．ミハイレスク（P.Mihailescu）は、ＩＥＥＥ  Ｐ１９６３提出の「推定素数を生成するための技術（“Technique for Generating Probable Primes”）」と題された論文において、Ｎ＝２*（ｔ＋ｋ）*Ｑ＋１の形式からなる素数を生成するためのふるい分け方法を記載しており、ここで素数候補のためのインクリメンタルサーチは、ある態様でｋを増加させることによって行なわれる。
【０００６】
Ｊ．ブラント等（J. Brandt et al）は、暗号文の進歩−暗号'９２（Advances in Cryptology-Crypto'92）、シュプリンガー・フェアラーク（Springer-Verlag）（１９９３）、ｐｐ．３５８−３７０の「インクリメンタルサーチによる推定素数の生成について（“On Generation of Probable Primes by Incremental Search”）」という論文において、候補の素数性を検査するためのインクリメンタルサーチについて記載している。ここで、前の検査候補から新しい候補を生成するための増分は常に２である。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、コンピュータソフトウェア（またはファームウェア）方法を提供することであり、この方法によって、このようなソフトウェアでプログラム化されたコンピュータシステムまたはチップは、推定素数検査にとって可能性のない候補を効率的に排除することができるため、キー生成等の暗号適用例にとって有用な推定素数を迅速に生成し、検査することができる。
【０００８】
本発明の別の目的は、先述の推定素数の生成および検査方法を実行するプログラム化されたコンピュータシステムまたは構成された処理チップの形態での暗号化装置を提供することである。
【課題を解決するための手段】
【０００９】
発明の開示
上記の目的は、スマート増分および小さな素数の検査技術を実現する方法および装置によって満たされ、非常に小さな素数（たとえば２，３，５および７）に対して相対的に素数の、ランダムに生成された第１の大きな候補で始まる連続した候補は、モジュール単位で減じられ、可能性のある候補がより厳しい推定素数検査のために識別されるまで、指定された組の小さな素数（たとえば１１から２４１までの素数）に対して検査される。
【００１０】
スマート増分プログラム機能は、選択された非常に小さな素数のモジュール、つまり選択された非常に小さな素数の積（たとえばモジュール２１０）に対して相対的に素数である一致する値の表を用いて次の候補への増分（必ずしも２ではない）を識別することによって、連続する整数候補を見つける。この表は、未知の方法によって最終的に見つけれられる素数の形式を記録し、これは暗号化による機密保護のために強く望まれる。これは即座に、非常に明白な合成数の約４分の３をふるいにかけて、非常に小さな素数に対して相対的に素数であると知られる残余の候補のみが、プログラムの小さな素数の検査機能における試し割算にかけられるようにする。この表を用いることによって、増分を、試し割算をすることなく大きな整数候補それ自体によって見つけることができる。
【００１１】
小さな素数の検査プログラム機能は、小さな素数のリストに対して試し割算を行なう。しかしながら、このプログラムの速度は、非常に大きな候補それ自体に対してよりも、１組のモジュール単位の減じられた値（たとえば１０２４ビットではなく３２ビットのサイズ）に対し試し割算を行なうことによって増加する。減少モジュールは、候補が検査されるグループの同じ小さな素数のサイズ制限された積（たとえばせいぜい３２ビット）である。
【００１２】
小さな素数検査を通過した候補（いかなる所与の範囲における整数の合計数の約１０パーセント）のみが、ミラー・ラビンまたはフェルマーのようなより厳しい推定素数検査にかけられる。
【発明を実施するための最良の形態】
【００１３】
発明を実施するためのベストモード
本発明は、暗号化の使用のための大きな（典型的に２５６，３２４，５１２，１０２４ビットまたはそれよりも大きい）推定素数を生成し検査するためのコンピュータで実現される方法についてである。この方法は、好ましくはコンピュータ読取可能媒体に記憶され、これから読出され、かつ汎用プログラマブルコンピュータシステムによって実行されるソフトウェアコードとして実現される。これはまた、（たとえばスマートカード上の）特定目的の暗号コンピュータチップにおけるファームウェアとして、または構成可能なハードウェア（たとえばＦＰＧＡチップ）もしくはその回路における方法のステップを実行す
るように特にプログラムもしくは設計された特定用途向け回路（すなわちＡＳＩＣチップ）としても実現されるかもしれない。推定素数のための暗号化の使用は、非対称（公開−秘密鍵のペア）暗号化プログラムにおけるような鍵の生成を含む。推定素数のための別の暗号化の使用は、擬似ランダム数生成、たとえばストリーム暗号通信のためのものである。本発明の方法は、典型的に、この方法によって生成される大きな推定素数が用いられる、より大きな暗号コンピュータプログラムの一部である。コンピュータシステムまたは特別な目的のチップは、本発明の方法を実行するためにプログラム化されるときは、その時に素数生成回路または装置と考えることができる。
【００１４】
この方法は、スマート増分技術を用いることによって、推定素数を見つける速度を増大して、可能性のない候補を検査するのを回避する。所望のビットサイズ（たとえば１０２４ビット）のランダムな数が選択され、非常に小さな素数２，３，５および７に対して相対的に素数である値に即座に増分されて、最初の候補を生成する。各々の候補は、小さな素数のリストを用いた試し整数割算で始まるプログラム化されたコンピュータシステムまたはチップによって検査され、合成数であるとわかった場合、それは選択された偶数（必ずしも２ではない）によって増分されて、非常に小さな素数２，３，５および７に対して相対的に素数である次の候補を得る。この方法は、このスマート増分技術を用いて、整数割算によって検査される合成数の数を最小にする。試し割算は、大きな候補数に対して直接行なわれるのではなく、候補の３２ビットのモジュール減少に対して行なわれ、さらに方法を加速する。小さな素数の試し割算検査を通過した候補を見つけると、この可能性のある候補は次に、（ミラー・ラビン検査またはフェルマー検査等の）１つ以上の既知の厳しい推定素数検査アルゴリズムを用いて検査される。これら後者の検査はより時間がかかる（たとえば上記に挙げた検査の双方はモジュールのべき乗を採用する）ために、整数割算検査において小さな素数に対して相対的に素数であることがわかった可能性のある候補のみがより厳しい検査にかけられる。
【００１５】
コンピュータプログラムの主な部分は、以下を含み得る。
【００１６】
【数１】
2005531031.tif 000002
【００１７】
このプログラムにおいて、“Alea”は、検査されるべきランダムに選択された候補の整数の名前である。必要サイズの非常に大きな奇数の候補を迅速に生成することのできるいかなるランダムまたは擬似ランダム数生成ルーチンも用いることができる。“SmallPrimesTest”および“SmartIncrement”は、以下で詳細に説明するが、これらはそれぞれ、小さな素数のリストに対する整数割算検査および本発明のスマート増分技術を行なう機能である。最後に、検査される小さな素数に対して相対的に素数である数が得られる（AleaIsComposite＝false）。さらに、利用可能ないかなる１つ以上の厳しい従来の素数検査の方法も（関数読出“Number_Is_Probably_Prime”で表わされる）その数に対して採用することができる。しかしながら、このような厳しい検査は、最初に“SmallPrimesTest”を通過した候補に対してのみ行なわれる（可能性のある候補のうち約９０％が、SmartIncrementおよびSmallPrimesTest機能によって検証済みの合成数として排除されるため、より厳しい検査は候補値の残りの１０％に対してのみ行なわれる）。候補が選択された厳しい素数検査に落ちた場合、新しい候補が生成され、そこでメインプログラムが中止される。
【００１８】
SmartIncrement機能は以下の表を用いる。
【００１９】
【数２】
2005531031.tif 000003
【００２０】
Table_210は、２，３，５または７で割り切れるすべてのエントリに対するゼロからなる。しかしながら、２，３，５および７に対して相対的に素数であるエントリについて、表は非ゼロ値、たとえば整数それ自体を有する。表において割り切れる値を示す要素と、相対的に素数の値を示す要素とを区別する他の方法を用いることもできる。この表は、SmallPrimesTest機能を用いて、SmartIncrementが、さらなる整数割算検査のための２，３，５および７に対して相対的に素数である候補を選択する助けをする。
【００２１】
SmartIncrement機能は、以下のプログラムステップを含み得る。
【００２２】
【数３】
2005531031.tif 000004
【００２３】
SmartIncrementのこの実施例は、各々の後に続く候補が２，３，５および７で割り切れないことを保証する。Aleaは直接には用いられない。むしろ、増分の計算は、Alea％２１０（すなわちモジュールの残り）に基づいて行なわれる。機能は、それが非ゼロである、すなわち２，３，５および７に対して相対的に素数である（対応する値Alea＋Incrementに一致する）Mod_210のための次の値を見つけるまで、Table_210を実行する。暗号化の使用について、既知の特定の形式を有する素数を用いないことが重要である。したがって、たとえば、それが計算するのに簡単であったとしても、候補の選択肢を１ｍｏｄ２１０に一致するものに制限しない。２，３，５，７および１１に対して相対的に素数である整数を識別する２３１０値のより大きな表が、好適な修正とともに用いられるかもしれないが、表における非常に小さな素数の数が増加するとリターンが減じられる（Table_210は、候補のうちの４８／２１０または２２．８６％を除くすべてを排除し、一方でより大きなTable_2310は候補のうちの４８０／２３１０または２０．７８％を除くすべてを排除する。大きめの小さな素数（たとえば１１から２４１）は、表に基づくスマート増分ではなく試し割算の方を用いてより適切に検査される。
【００２４】
小さな素数の検査は複数の表を利用する。
【００２５】
【数４】
2005531031.tif 000005
【００２６】
第１のおよび第２の表は、それぞれ２５０未満の第１の既知の素数およびこのリストからの素数グループの積のリストである。素数２，３，５および７は表から省略されている。なぜなら、ランダムな数“Alea”が奇数であるだけでなく、上記で詳述した“SmartIncrement”手順を用いて３，５および７に対して相対的に素数となるように選択されることを保証するからである。第２のリストにおける積は、割算を容易にするために３２ビットに制限されている（利用可能なハードウェアに依存して、６４ビットまたはさらに大きな積を代わりに用いることができる）。第３の「インデックス」表は、小さな素数のリストを第２のリストにおける積に対応する連続した部分集合にインデックス付けする機能を果たす。
【００２７】
表のサイズは、所望の検査の数に依存して拡大または縮小することができる。必要と考えられる検査の数は、典型的に、生成されなければならない素数のビットサイズに基づいている。ここで示されたよりも大きな表については、素数それ自体ではなく、２，３，５および７に対して相対的に素数であるすべての数から表を導き出すことの方が便利であるかもしれない。合成数の小さな数が素数に追加して含まれる（たとえば１２１，１４３，１６９，１８７，２０９，２２１および２４７が上記表に追加される）一方で、検査のための値の生成が容易であることは、検査を絶対的に必要以上にわずかに長くすることよりも勝るかもしれない。しかしながら、やはり素数のリストが長くなると、小さな素数の試し割算によって排除する検証済みの合成数のリターンが減少する。試し割算からより厳しいミラー・ラビン、フェルマーまたはいくつかの他の推定素数検査へ切換えることが望まれる点は、主に候補のビットサイズおよび所望のセキュリティレベルに依存する判断の問題である。
【００２８】
小さな素数検査機能のためのコンピュータプログラムは、以下を含み得る。
【００２９】
【数５】
2005531031.tif 000006
【００３０】
小さな素数検査を最初に実行する際に、もとの大きな候補の整数Aleaは、最初に、Table_Reductionsにおける素数の積の各々の１つによるモジュール割算を行なうことによって、さらに小さい３２ビットの整数“Table_Mod”に減じられて、１組の３２ビットの残りを得る。これらの“Table_Mod”エントリは、“SmallPrimesTest”の各々の後に続く呼出のためにプログラムによって保持されて、大きな整数の割算を計算し直す必要がないようにすべきである。試し割算は次に、現在の試し増分“MainIncrement”によって最初に増
分された後で、インデックス表を用いて対応する減少のために用いられる積であった同じ素数に対して候補を検査することによって、“Table_Mod”エントリとともに実行され、残余部分がチェックされる。“Table_SmallPrimes”からのいかなる小さな素数による試し割算がゼロである場合、現在の候補は合成数であることがわかり、値（合成数＝真）は、必要とされるその候補に対する何らかのさらに他の試し割算も行なわずに戻される。残りがすべての検査された小さな素数に対して非ゼロである場合、値（合成数＝偽）は戻されて、メインプログラムはより厳しい推定素数検査へと進む。
【００３１】
一旦候補が検査のすべてを通過すると、それは推定素数であることが示される。これは次に、非対称（公開鍵）ブロック暗号のためのキー生成、または、ストリーム暗号通信のための（米国特許第４，７８０，８４０号にあるような）擬似ランダム数生成のような適用例のための暗号プログラムの他の部分によって用いられる。スマートカードトランザクションにおけるセッションキーの生成での使用が特に関連している。なぜなら、高速な生成および検査速度によって、この方法は、必要以上に遅延することなく、スマートカードに置かれた単一チップのプロセッサによって実行することができるからである。
【国際調査報告】
2005531031.tif 000007
2005531031.tif 000008