JP6246239B2 - 素数生成のための方法およびデバイス - Google Patents

Description

様々な特徴は素数生成のための方法およびデバイスに関し、より詳細には、素数生成を加速する方法およびデバイスに関する。

素数は公開鍵暗号方式において広く使用されている。たとえば、RSA(Rivest, Shamir, Adleman)は、素数の鍵生成処理に素数を必要とする最も広く使用されている公開鍵暗号の1つである。暗号方式に使用される素数は、大きい鍵空間を確保するのに十分な大きさでなければならず、それにより総当たり攻撃が阻止される。

RSA暗号方式計画に使用することができる典型的な素数は、たとえば1,024ビットである場合があり、これは結果として2,048ビットの公開/秘密鍵の対となる。このとき、これほど大きく素数を生成することは、比較的進歩したプロセッサを有するパーソナルコンピュータおよびサーバにとってさえ時間の浪費であり、結果として顕著な遅延となる。この遅延は、RSA鍵生成があるアプリケーション、たとえばトラステッドプラットフォームモジュール(TPM)およびスマートカード(UICC)に必要とされる場合にモバイルコンピューティングに影響を及ぼす重大な要因となる。最新のARMベースのプロセッサで1,024ビットの素数を生成することは、数秒程度の遅延を取る可能性があり、これはユーザ経験に重大な影響を及ぼす。したがって、素数生成を加速するいずれの方法も、特にモバイルコンピューティングアプリケーションにおいて暗号アプリケーションに利益をもたらすであろう。

図1は、素数を生成するために従来技術において見出された典型的な方法100を示す。第1に、n個のワードの乱数Rが真の乱数生成器(RNG)または高品質の擬似乱数生成器(PRNG)102のどちらも用いて生成される。第2に、「素数判定法」が候補数R104に対して実行される。「素数判定法」は、数が素数であるかどうかを判定するためのアルゴリズムである。多くの場合、素数判定法は、実際には本質的に確率である合成数判定法(すなわち、素数判定法は、数が合成数であるかどうかを判定する)である。そのような判定法の例としては、Miller-Rabin素数判定法およびSolovay-Strassen素数判定法が挙げられる。

第3に、候補数Rが素数判定法に合格した(すなわち、数Rはおそらく素数である)場合、次いで、Rは鍵生成処理において素数として使用することができる106。さもなければ、候補数Rが素数判定法に不合格であった(すなわち、数Rが素数ではないと判定された)場合、次いで、数Rは破棄され、完全に新しい乱数R₂が生成され108、上記のステップ104、106、および/または108は繰り返される。

素数判定法は、素数生成に関連する大部分の遅延の一因となるが、遅延の別の重大な一因は、候補乱数が素数ではないと判定された(すなわち、ステップ108)後、新しい乱数Rを生成すること(すなわち、ステップ102)に費やされた時間による。ランダムに選択された数Rが素数である確率は極めて低い。たとえば、素数定理によれば、1,024ビットの数が素数であるという確率は約710中1(1/In(2¹⁰²⁴))である。この理由のために、候補素数が破棄される可能性があり(すなわち、ステップ108)、候補素数が(ある程度まで)素数であることが確認される(すなわち、ステップ106)前に、新しい候補素数がおびただしい回数生成される可能性がある(すなわち、ステップ102)。

したがって、素数であるべき数を生成し判定することに関連する全体的な遅延が低減されるように素数生成を加速する必要性がある。素数生成に依存する暗号方式に関連するアプリケーションは、そのような加速された素数生成計画から重大な利益を導き出すことができる。

1つの特徴は、複数のビットを有する第1の乱数を生成するステップと、生成された第1の乱数に対して第1の素数判定法を実行するステップと、生成された第1の乱数が第1の素数判定法に不合格であったと判定するステップと、第1の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第2の乱数を生成するステップと、第2の乱数に対して第2の素数判定法を実行するステップとを含む、素数を生成する方法に関する。一態様によれば、この方法は、第2の乱数が第2の素数判定法に不合格であったと判定するステップと、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、第2の乱数に対して連続する素数判定法を実行するステップとをさらに含む。別の態様によれば、第1の乱数は複数のxビットワードを含み、置換された複数のビットの部分は第1のxビットワードである。さらに別の態様によれば、この方法は、複数のビットの部分を第1のxビットワードに置換する前に、少なくとも1つのxビットワードによって第1の乱数を左または右に回転させるステップをさらに含む。

一態様によれば、置換された複数のビットの部分は、連続的なビットのブロックを形成する。別の態様によれば、置換された複数のビットの部分は、部分的に、非連続的なビット数を有する複数のビットのランダムなビットである。さらに別の態様によれば、第1の乱数および第2の乱数の各々は少なくとも8ビットを有し、置換された複数のビットの部分は少なくとも2ビットである。別の態様によれば、この方法は、第2の乱数が第2の素数判定法に不合格であったと判定するステップと、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第3の乱数を生成するステップと、第3の乱数に対して第3の素数判定法を実行するステップとをさらに含む。

一態様によれば、第1および第2の乱数の各々は複数のxビットワードを含み、置換された第1の乱数の複数のビットの部分は第1のxビットワードであり、置換された第2の乱数の複数のビットの部分は第2のxビットワードである。別の態様によれば、第1のxビットワードおよび第2のxビットワードのワード数は異なる。さらに別の態様によれば、第1のxビットワードおよび第2のxビットワードのワード数は連続的である。別の態様によれば、第1のxビットワードおよび第2のxビットワードのワード数は非連続的である。

一態様によれば、第1および第2の乱数の各々は複数のxビットワードを含み、第2の乱数を生成するように置換された第1の乱数の複数のビットの部分は第1のxビットワードであり、この方法は、第2の乱数が第2の素数判定法に不合格であったと判定するステップと、第2の乱数の第1のxビットワードをランダムに生成されたxビットワードに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、または第2の乱数の第1のxビットワードが既定回数置換されたと判定されるまで、第2の乱数に対して連続する素数判定法を実行するステップとをさらに含む。別の態様によれば、この方法は、第2の乱数の第1のxビットワードが既定回数置換されたと判定された場合、第2の乱数の第2のxビットワードをランダムに生成されたxビットワードに置換するステップをさらに含む。

別の特徴は、複数のビットを有する第1の乱数を生成するように適合された乱数生成器回路、乱数生成器回路に通信可能に結合され、生成された第1の乱数に対して第1の素数判定法を実行し、生成された第1の乱数が第1の素数判定法に不合格であったと判定するように適合された素数判定法回路、および素数判定法回路に通信可能に結合され、第1の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第2の乱数を生成するように適合されたビット置換回路を備える素数生成器であって、素数判定法回路が第2の乱数に対して第2の素数判定法を実行するようにさらに適合されている、素数生成器に関する。一態様によれば、素数判定法回路は、第2の乱数が第2の素数判定法に不合格であったと判定するようにさらに適合され、ビット置換回路は、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、第2の乱数に対して連続する素数判定法を実行するようにさらに適合されている。別の態様によれば、第1の乱数は複数のxビットワードを含み、置換された複数のビットの部分は第1のxビットワードである。さらに別の態様によれば、ビット置換回路は、複数のビットの部分を第1のxビットワードに置換する前に、少なくとも1つのxビットワードによって第1の乱数を左または右に回転させるようにさらに適合されている。

一態様によれば、素数判定法回路は、第2の乱数が第2の素数判定法に不合格であったと判定するようにさらに適合され、ビット置換回路は、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第3の乱数を生成するようにさらに適合され、素数判定法回路は、第3の乱数に対して第3の素数判定法を実行するようにさらに適合されている。別の態様によれば、第1および第2の乱数の各々は複数のxビットワードを含み、第2の乱数を生成するように置換された第1の乱数の複数のビットの部分は第1のxビットワードであり、素数判定法回路は、第2の乱数が第2の素数判定法に不合格であったと判定するようにさらに適合され、ビット置換回路は、第2の乱数の第1のxビットワードをランダムに生成されたxビットワードに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、または第2の乱数の第1のxビットワードが既定回数置換されたと判定されるまで、第2の乱数に対して連続する素数判定法を実行するようにさらに適合されている。さらに別の態様によれば、ビット置換回路は、第2の乱数の第1のxビットワードが既定回数置換されたことが判定された場合、第2の乱数の第2のxビットワードをランダムに生成されたxビットワードに置換するようにさらに適合されている。

別の特徴は、複数のビットを有する第1の乱数を生成するための手段、生成された第1の乱数に対して第1の素数判定法を実行するための手段、生成された第1の乱数が第1の素数判定法に不合格であったと判定するための手段、第1の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第2の乱数を生成するための手段、および第2の乱数に対して第2の素数判定法を実行するための手段を備える素数生成器に関する。一態様によれば、素数生成器は、第2の乱数が第2の素数判定法に不合格であったと判定するための手段、および第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、第2の乱数に対して連続する素数判定法を実行するための手段をさらに備える。別の態様によれば、素数生成器は、複数のビットの部分を第1のxビットワードに置換する前に、少なくとも1つのxビットワードによって第1の乱数を左または右に回転させるための手段をさらに備える。さらに別の態様によれば、素数生成器は、第2の乱数が第2の素数判定法に不合格であったと判定するための手段、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第3の乱数を生成するための手段、および第3の乱数に対して第3の素数判定法を実行するための手段をさらに備える。

一態様によれば、第1および第2の乱数の各々は複数のxビットワードを含み、第2の乱数を生成するように置換された第1の乱数の複数のビットの部分は第1のxビットワードであり、素数生成器は、第2の乱数が第2の素数判定法に不合格であったと判定するための手段、および第2の乱数の第1のxビットワードをランダムに生成されたxビットワードに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、または第2の乱数の第1のxビットワードが既定回数置換されたと判定されるまで、第2の乱数に対して連続する素数判定法を実行するための手段をさらに備える。別の態様によれば、素数生成器は、第2の乱数の第1のxビットワードが既定回数置換されたことが判定された場合、第2の乱数の第2のxビットワードをランダムに生成されたxビットワードに置換するための手段をさらに備える。

別の特徴は、素数を生成するための1つまたは複数の命令を有するコンピュータ可読記憶媒体であって、少なくとも1つのプロセッサによって実行されると命令がプロセッサに、複数のビットを有する第1の乱数を生成させ、生成された第1の乱数に対して第1の素数判定法を実行させ、生成された第1の乱数が第1の素数判定法に不合格であったと判定させ、第1の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第2の乱数を生成させ、第2の乱数に対して第2の素数判定法を実行させる、コンピュータ可読記憶媒体に関する。一態様によれば、プロセッサによって実行されると命令はさらにプロセッサに、第2の乱数が第2の素数判定法に不合格であったと判定させ、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、第2の乱数に対して連続する素数判定法を実行させる。別の態様によれば、プロセッサによって実行されると命令はさらにプロセッサに、複数のビットの部分を第1のxビットワードに置換する前に、少なくとも1つのxビットワードによって第1の乱数を左または右に回転させる。さらに別の態様によれば、プロセッサによって実行されると命令はさらにプロセッサに、第2の乱数が第2の素数判定法に不合格であったと判定させ、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第3の乱数を生成させ、第3の乱数に対して第3の素数判定法を実行させる。

一態様によれば、第1および第2の乱数の各々は複数のxビットワードを含み、第2の乱数を生成するように置換された第1の乱数の複数のビットの部分は第1のxビットワードであり、プロセッサによって実行されると命令はさらにプロセッサに、第2の乱数が第2の素数判定法に不合格であったと判定させ、第2の乱数の第1のxビットワードをランダムに生成されたxビットワードに置換させ、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、または第2の乱数の第1のxビットワードが既定回数置換されたと判定されるまで、第2の乱数に対して連続する素数判定法を実行させる。別の態様によれば、プロセッサによって実行されると命令はさらにプロセッサに、第2の乱数の第1のxビットワードが既定回数置換されたと判定された場合、第2の乱数の第2のxビットワードをランダムに生成されたxビットワードに置換させる。

素数を生成するために従来技術において見出された典型的な方法を示す図である。 数Rを示す図である。 素数生成のための方法を示す図である。 素数生成のための方法を示す図である。 素数生成のための方法を示す図である。 素数生成デバイスの概略的なブロック図である。 素数生成デバイスの処理回路の概略的なブロック図である。 素数生成デバイスと統合することができる様々な電子デバイスを示す図である。

以下の説明では、特定の詳細が、本開示の様々な態様の完全な理解を提供するために与えられる。しかし、この態様は、これらの特定の詳細なしに実行されてもよいことは当業者によって理解されよう。たとえば、回路が、不必要な詳細において態様を不明瞭にすることを避けるためにブロック図に示されてもよい。他の例では、周知の回路、構造および技法が、本開示の態様を不明瞭にしないために詳細に示されなくてもよい。

「例示的な」という用語は、「例(example、instance、またはillustration)として役立つこと」を意味するために本明細書で使用される。「例示的な」と本明細書で説明されたいずれの実装または態様も、本開示の他の態様に対して好ましいまたは有利であると必ずしも解釈すべきではない。本明細書で使用するように、「素数判定法」および「合成数判定法」が互換可能に使用されてもよく、一般に「素数判定法」と呼ばれる。たとえば、Miller-Rabin判定法などの判定法は、数が合成であることを証明することができる。そうすることによって、判定法はまた数が素数ではないことを証明する。したがって、本明細書で使用するように、数に対して素数判定法を実行することは、数が合成であることを証明するまたは証明しようとする判定法を含む。本明細書で使用するように、「乱数」が真にランダムであってもよく(たとえば、真の乱数生成器(RNG)によって生成された)、または擬似ランダムであってもよい(たとえば、擬似乱数生成器(PRNG)を用いて生成された)。

概要
1つの実装は、素数を生成することに関連する計算の遅延を低減する方法を提供する。この方法は、複数のビットを有する第1の乱数を生成するステップを含む。次いで、第1の素数判定法が第1の乱数に対して実行される。次いで、生成された第1の乱数が第1の素数判定法に合格したか不合格であったかが判定される。第1の乱数が第1の素数判定法に不合格であった場合、次いで第1の乱数の複数のビットのすべてではない部分が同数のランダムに生成されたビットに置換されて第2の乱数を生成する。次に、素数判定法が再び第2の乱数に対して実行される。この処理は、素数が検出されるまで繰り返される(すなわち、判定中の乱数のビットの部分)。

例示的な方法
図2は、本開示の一態様による数R200を示す。数R200はn個のxビットワード202、204、...206を含むzビット数であり、ここで、zは2に等しいか2より大きく、nは2に等しいか2より大きく、xは1に等しいか1より大きい。したがって、数Rのビットzの総数はn*xに等しい。数R200は、真の乱数生成器または擬似乱数生成器を用いて生成されてもよい。一例によれば、zビット乱数R200は、各々32ビットである32ワードを含む1,024ビット数である。もちろん、乱数R200は、1より大きいビット長を有する任意の乱数であってもよく、各々1つまたは複数のビットを有する複数のワードを含んでもよい。

図3は、本開示の一態様による素数生成のための方法300を示す。最初に、n個のxビットワードを有するzビット乱数R(たとえば、図2の数R200)が生成される302。乱数Rは、素数であってもよくまたは素数でなくてもよい候補数である。次に、素数判定法(たとえば、Miller-Rabin判定法)が、候補数Rに対して実行される304。候補数Rが素数判定法に合格した(すなわち、ある程度の精度までRが素数である可能性があると判定された)場合、次いで乱数Rは素数として選択される306。次いで、数Rは、たとえば鍵生成に使用されてもよい。

さもなければ、候補数Rが素数判定法に不合格であった(すなわち、ある程度の精度までRが素数ではないと判定された)場合、次いで乱数Rのxビットワード(たとえば、図2のワード202)がランダムにまたは擬似ランダムに生成されたxビット値に置換されて新しい乱数R₂を形成するが、残りのビット/ワードは同一に保たれる308。次いで、新しい乱数R₂は素数判定法にフィードバックされる310。この処理は、乱数R₂が素数判定法に不合格であった場合、次いで別のR₂の異なるxビットワード(たとえば、図2のワード204)が新しいランダムにまたは擬似ランダムに生成されたxビット値に置換されて新しい乱数R₃を形成し、次いで素数判定法がR₃に対して実行されるように繰り返される。最終的に、素数が生成/検出され、処理300は停止する。ほんの一例として、生成された乱数R、R₂、R₃他は、32個の32ビットワードからなる1,024ビット数であってもよい。

この方式では、全体の乱数Rを新たに生成された乱数に置換するのではなく(図1のステップ108参照)、本開示は、乱数R、R₂、R₃他の選択部分のみが置換され、素数判定法が再実行される方法を開示する。たとえば、1,024ビットの候補乱数が素数判定法に不合格であった場合、1,024ビット数のうちの32ビット部分などの比較的小さい部分が新たに生成されたランダムなビットに置換される場合があるが、残りの992ビットは未接触のままである。やはり、1,024ビット数のうちの32ビットのみを変更することで、多くの可能な素数(たとえば、2³²/(1024*In(2))=6,051,101個の素数)が変更後に存在することが可能となる。したがって、素数が他の992ビットを変更する必要がない場合に存在しない確率は極めて低い。したがって、完全に新しいzビット数(たとえば、1,024ビット数)をランダムに生成するのではなく、zビット数(たとえば、1,024ビット数)のxビットワード(たとえば、32ビットワード)を単に生成および置換することによって、多くの時間を節約することができる。

一例として、乱数Rが1,024ビットであり、xビットワードが各々32ビットである場合、提案する方法は、従来技術の方法と比較して乱数生成に関連する時間の96.875%を節約することができる(たとえば、方法100)。したがって、乱数生成が、たとえば、乱数生成に関連する全体の遅延の10%の一因となるだけである場合でさえ、提案する方法は、与えられた例に対して約9.7%だけ全体の素数生成の遅延を低減することができる。

図3に関して上述したように、新たに生成された候補乱数R₂、R₃他が素数判定法に不合格であった場合、次いで候補乱数の別のxビット部分が置換されて新しい乱数を生成する。たとえば、zビットワードがn個のxビットワードを含む場合、次いで処理300のn回の反復の後(すなわち、ここまでは生成された乱数が素数判定法に合格していないので、ステップ308はn回実行される)、元の候補乱数Rはワードごとに完全に置換されて完全に新しい乱数を生成する。これにより、素数が検出/生成されるようにアルゴリズムが常に終了することが保証される。というのは、乱数Rの同一のxビットワードが新たに生成されたランダムなワードに置換されるが、残りのワードが置換されない場合、置換中のxビットワードに関連する数の範囲内に素数が存在しない極めて小さい可能性が存在するからである。

図2および図3を参照すると、一態様によれば、図3のステップ308は、処理300の各反復が連続的な方式でxビットワード202、204、...206をランダムに生成されたxビットワードに置換するように実行されてもよい。すなわち、第1の候補乱数Rが素数ではないと判定された場合、次いで後続の乱数R₂は、たとえば第1のxビットワード202をランダムなxビット値に置換することによって生成される。乱数R₂がまた素数ではないと判定された場合、次いで次の後続の乱数R₃は第2のxビットワード204をランダムなxビット値に置換することによって生成される。したがって、xビットワードは、すべてのn個のxビットワードが置換されるまで連続的な方式で置換されてもよく(すなわち、置換されたxビットワードは連続的なワード数を有する)、素数がまだ検出されていないと仮定すると、第1のxビットワード202は再び置換され、次いで第2の204、など。

一態様によれば、前述の例は回転/シフトコマンドを用いて実装されてもよい。たとえば、図3のステップ308は、1つのxビットワードによってzビット乱数Rを左または右に回転/シフトさせ、次いで固定位置のワード(たとえば、最上位のビットワードまたは最下位のビットワード)をランダムに生成されたxビットワードに置換することによって実行されてもよい。

別の態様によれば、xビットワード202、204、...206は非連続的な方式で置換されてもよい。たとえば、第1の候補乱数Rが素数ではないと判定された場合、次いで後続の乱数R₂は、たとえば第2のxビットワード204をランダムなxビット値に置換することによって生成される。乱数R₂がまた素数ではないと判定された場合、次いで次の後続の乱数R₃はn番目のxビットワード206をランダムなxビット値に置換することによって生成される。したがって、この場合、xビットワード202、204、...206は非連続的な(ランダムでさえ)方式で置換される(すなわち、置換されたxビットワードのワード数は非連続的である)。

別の態様によれば、1つのxビットワード202、204、...206は、zビット乱数R、R₂、R₃他の別のxビットワード202、204、...206または別の部分が置換される前に複数回置換されてもよい。たとえば、第1の候補乱数Rが素数ではないと判定された場合、次いで後続の乱数R₂は、たとえば第1のxビットワード202をランダムなxビット値に置換することによって生成される。乱数R₂がまた素数ではないと判定された場合、次いで次の後続の乱数R₃は第1のxビットワード202を別のランダムなxビット値に再び置換することによって生成される。この方式では、素数が検出されないと仮定すると、第1のxビットワード202は、先に進み別のワード(たとえば、第2のxビットワード204)をランダムに生成された値に置換する前に、複数回異なるランダムなxビット値に置換されてもよい。一態様によれば、第1のxビットワード202は、先に進み第2のxビットワード204をランダムに生成された値に置換する前に、所定回数ランダムなxビット値(たとえば、1より大きい任意の整数値)に置換されてもよい。

図2を参照すると、本明細書で使用するように、「第1のxビットワード」という用語は必ずしもxビットワードA202を指さないが、代わりに、「第1」という用語が単にあるxビットワードを別のxビットワードと区別し特定するのに役立つだけなので、任意のxビットワード202、204、...206を指す。同様に、「第2のxビットワード」という用語は必ずしもxビットワードB204を指さないが、代わりに、第1のxビットワード以外の任意のxビットワード202、204、...206を指す。したがって、「第2の」という用語は、単にあるxビットワードを別の第1のxビットワードと区別し特定するのに役立つだけである。同一の原理は、引き続き番号付けられたxビットワードに適用する(たとえば、第3のxビットワード、第4のxビットワード、...n番目のxビットワード、他)。

図4は、本開示の別の態様による素数生成のための方法400を示す。最初に、zビット乱数R(たとえば、図2の数R200)が生成される402。乱数Rは、素数であってもよく、素数でなくてもよい候補数である。次に、素数判定法(たとえば、Miller-Rabin判定法)が候補数Rに対して実行される404。候補数Rが素数判定法に合格した(すなわち、ある程度の精度までRが素数である可能性があると判定された)場合、次いで乱数Rは素数として選択される406。次いで、数Rは、たとえば鍵生成に使用されてもよい。

さもなければ、候補数Rが素数判定法に不合格であった(すなわち、ある程度の精度までRが素数ではないと判定された)場合、次いで乱数Rのビットの選択数が、同数のランダムにまたは擬似ランダムに生成されたビットに置換されて新しい乱数R₂を形成するが、残りのビットは同一に保たれる408。次いで、新しい乱数R₂は素数判定法にフィードバックされる410。この処理は、乱数R₂が素数判定法に不合格であった場合、次いで別のR₂の異なるビット部分が他のランダムにまたは擬似ランダムに生成されたビットに置換されて新しい乱数R₃を形成するように繰り返される。次いで、素数判定法はR₃に対して実行される。最終的に、素数が生成/検出されてもよく、処理400は停止される。1つの例によれば、候補乱数R、R₂、R₃の各々は少なくとも8ビットを有し、置換された複数のビットの部分は少なくとも2ビットである。

これから、処理400の2つの非限定的な実例を例として役立つように説明する。

第1の例として、2,048ビットを有するランダムな候補数RがPRNGを用いて最初に生成されてもよい(たとえば、ステップ402)。次いで、Miller-Rabin判定法などの素数判定法が候補数Rに対して実行されてもよく、それと同時に次いで候補数Rが素数ではないと判定されてもよい(たとえば、ステップ404)。次に、候補数Rのビット部分が同一のビット長を有するランダムに生成された値に置換される。たとえば、ビット数344で開始し、ビット数407で終了するRの64ビット部分(最上位のビット(MSB)はビット数1)が、ランダムに生成された64ビット値に置換されて新しい乱数R₂を生成する(たとえば、ステップ408)。

次いで、素数判定法は候補数R₂に対して実行され、それと同時に候補数R₂が素数ではないと判定されてもよい(たとえば、ステップ404)。再度、候補数R₂のビット部分が同一のビット長を有するランダムに生成された値に置換される。このとき、たとえば、ビット数1,234で開始し、ビット数1,265で終了するR₂の32ビット部分が、ランダムに生成された32ビット値に置換されて新しい乱数R₃を生成してもよい(たとえば、ステップ408)。素数判定法がR₃に対して実行され、不合格の候補数のビット部分を置換して新しい候補数を生成するこの処理は、候補数が素数判定法に合格したと判定されるまで繰り返される(たとえば、ステップ406)。

第2の例として、512ビットを有するランダムな候補数RがPRNGを用いて最初に生成されてもよい(たとえば、ステップ402)。次いで、Miller-Rabin判定法などの素数判定法が候補数Rに対して実行されてもよく、それと同時に次いで候補数Rが素数ではないと判定されてもよい(たとえば、ステップ404)。次に、候補数Rの非連続的なビット部分が同数のランダムに生成されたビットに置換される。たとえば、候補数Rの48ビットが同数(すなわち、48)のランダムに生成されたビットに置換されてもよい(たとえば、ステップ408)。1つの例では、これらのビットのいくつかは、とりわけ、ビット数12、44、77、223、および498を含んでもよい。すなわち、従来の例とは異なり、ビットはブロック形式で選択されず置換されない。むしろ、ビットはランダムに選択され置換される。ビットが置換されると、新しいランダムな候補数R₂がこのように生成される。

次いで、素数判定法は候補数R₂に対して実行され、それと同時に候補数R₂が素数ではないと判定されてもよい(たとえば、ステップ404)。再度、候補数R₂のビットのランダムな部分が同数のランダムに生成されたビットに置換される。このとき、たとえば、候補数R₂の32ビットが同数(すなわち、32)のランダムに生成されたビットに置換されてもよい(たとえば、ステップ408)。1つの例では、これらのビットのいくつかは、とりわけ、ビット数9、24、124、332、および506を含んでもよい。ビットが置換されると、新しい乱数R₃がこのように生成される。素数判定法がR₃に対して実行され、不合格の候補数のランダムなビットを選択し置換して新しい候補数を生成するこの処理は、候補数が素数判定法に合格したと判定されるまで繰り返される(たとえば、ステップ406)。

図5は、本開示の一態様による素数生成のための方法500を示す。最初に、複数のビットを有する第1の乱数が生成される502。次に、第1の素数判定法が生成された第1の乱数に対して実行される504。次いで、生成された第1の乱数が第1の素数判定法に不合格であったと判定される506。次に、第1の乱数の複数のビットのすべてではない部分が、同数のランダムに生成されたビットに置換されて第2の乱数を生成する508。次いで、第2の素数判定法が第2の乱数に対して実行される510。一態様によれば、第2の乱数が第2の素数判定法に不合格であったと判定され、第2の乱数の複数のビットのすべてではない部分が同数のランダムに生成されたビットに置換され、連続的な素数判定法が、第2の乱数が連続的な素数判定法のうちの1つに合格したと判定されるまで第2の乱数に対して実行される。

例示的なデバイス
図6は、本開示の一態様による素数生成デバイス600の概略的なブロック図を示す。素数生成デバイス600は、処理回路602、メモリ回路604、入力/出力(I/O)インターフェース606、および/またはバス610を介して通信可能に結合される通信インターフェース608を備えてもよい。処理回路602は、限定されないが、乱数を生成するステップ、およびzビット乱数Rのビットを選択し置換するステップを含む図3、図4、および図5に関して上で説明された操作のいずれも実行するように適合されている少なくとも1つのプロセッサ(たとえば、アプリケーション特有の集積回路、デジタル信号プロセッサ、アプリケーションプロセッサ、他)を備える。メモリ回路604は、1つまたは複数の揮発性、不揮発性メモリ回路、および/または、限定されないが、SRAM、DRAM、SDRAM、NAND FLASH、NOR FLASH、ハードディスクドライブ、コンパクトディスク(CD)、他を含むコンピュータ可読媒体を備える。メモリ回路604は、とりわけ、1つまたは複数のプロセッサによって実行されると処理回路602に図3、図4、および図5に関して上で説明された操作を実行させるコンピュータ可読命令を記憶するように適合されている。

I/Oインターフェース606は、限定されないが、ディスプレイ、キーボード、タッチスクリーンディスプレイ、マウス、カメラ、ジョイスティック、他を含む複数の入力および出力デバイスのうちのいずれか1つを備えてもよい。通信インターフェース608は、素数生成デバイス600が1つまたは複数のネットワーク(たとえば、セルラーネットワーク)および/または他の電子デバイスと通信することを可能にするワイヤレス通信インターフェースおよび/またはワイヤード通信インターフェースを備えてもよい。通信インターフェース608はまた、直列および並列通信ポート(たとえば、USB、他)を備えてもよい。

図7は、本開示の一態様による素数生成デバイスの処理回路602の概略的なブロック図を示す。処理回路602は、乱数生成器モジュール/回路702、素数判定法モジュール/回路704、および/またはビット/ワード置換モジュール/回路706を備えてもよい。回路702、704、706は、図7に示す二重矢印によって示されるように互いに通信可能に結合されてもよい。回路702、704、706は、図2、図3、図4、および/または図5に関して本明細書で説明された様々な操作および/または方法ステップを実行するように配線されたアプリケーション特有の集積回路(ASIC)であってもよい。回路702、704、706は、処理回路602の一部であるとして実例に示されているが、いくつかの態様では、各回路702、704、706は、互いにおよび/または処理回路602とは物理的に異なる独立回路であってもよい。

一般に、乱数生成器モジュール/回路702は、上の様々な方法/処理で説明された乱数R、R₂、R₃、ランダムなビット、およびランダムなxビットワードを生成するための手段であってもよい。特に、乱数生成器モジュール/回路702は、複数のビットを有する第1の乱数を生成するための手段、第2の乱数の生成を援助するために同数のランダムなビットを生成するための手段、およびランダムなxビットワードを生成するための手段であってもよい。

一般に、素数判定法モジュール/回路704は、様々な候補数に対して素数判定法(Miller-Rabin素数判定法またはSolovay-Strassen素数判定法など)を実行して(ある程度の信頼度まで)候補数が素数であるかまたは素数ではないかを判定するための手段であってもよい。特に、素数判定法モジュール/回路704は、生成された第1の乱数に対して第1の素数判定法を実行するための手段、生成された第1の乱数が第1の素数判定法に不合格であったと判定するための手段、第2の乱数に対して第2の素数判定法を実行するための手段、第2の乱数が第2の素数判定法に不合格であったと判定するための手段、および第3の乱数に対して第3の素数判定法を実行するための手段であってもよい。

一般に、ビット/ワード置換モジュール/回路706は、候補数のビット部分およびワードを他のランダムに生成されたビットおよびワードに置換するための手段であってもよい。特に、ビット/ワード置換モジュール/回路706は、第1の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第2の乱数を生成するための手段、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、第2の乱数に対して連続する素数判定法を実行するための手段、複数のビットの部分を第1のxビットワードに置換する前に、少なくとも1つのxビットワードによって第1の乱数を左または右に回転させるための手段、第2の乱数の複数のビットのすべてではない部分を同数のランダムに生成されたビットに置換して第3の乱数を生成するための手段、第2の乱数の第1のxビットワードをランダムに生成されたxビットワードに置換し、第2の乱数が連続する素数判定法のうちの1つに合格したと判定されるまで、または第2の乱数の第1のxビットワードが既定回数置換されたと判定されるまで、第2の乱数に対して連続する素数判定法を実行するための手段、および第2の乱数の第1のxビットワードが既定回数置換されたと判定された場合、第2の乱数の第2のxビットワードをランダムに生成されたxビットワードに置換するための手段であってもよい。

図8は、素数生成デバイス600と統合されてもよい様々な電子デバイス802、804、806を示す。たとえば、移動電話802、ラップトップコンピュータ804、および固定位置端末806は、素数生成デバイス600を備えてもよい。図8に示す電子デバイス802、804、806は、単に例示的である。他の電子デバイスはまた、限定されないが、手持ち式個人通信システム(PCS)ユニット、パーソナルデータアシスタントなどの携帯データ、GPS使用可能デバイス、ナビゲーションデバイス、セットトップボックス、音楽プレーヤ、ビデオプレーヤ、娯楽ユニット、メータ読み取り機器などの固定位置データユニット、あるいはデータまたはコンピュータ命令を記憶しまたは抽出する任意の他のデバイス、あるいはその任意の組合せを備える、素数生成デバイス600を特徴としてもよい。

図2〜図8に示す構成要素、ステップ、特徴、および/または機能の1つまたは複数は、単一の構成要素、ステップ、特徴、または機能に再編されかつ/または組み合わされてもよく、あるいはいくつかの構成要素、ステップ、または機能で具現されてもよい。追加の要素、構成要素、ステップ、および/または機能も、本発明から逸脱することなく追加されてもよい。図6、図7、および図8に示す装置、デバイス、および/または構成要素は、図2〜図5で説明された1つまたは複数の方法、特徴、またはステップを実行するように構成されてもよい。本明細書で説明されたアルゴリズムはまた、ソフトウェアに効率的に実装されてもよくかつ/またはハードウェアに組み込まれてもよい。

さらに、本開示の一態様では、図6および図7に示す処理回路602は、図3、図4、および図5で説明されたアルゴリズム、方法、および/またはステップを実行するように特に、設計および/または配線された専用プロセッサ(たとえば、アプリケーション特有の集積回路(たとえば、ASIC))であってもよい。したがって、そのような専用プロセッサ(たとえば、ASIC)は、図3、図4、および図5で説明されたアルゴリズム、方法、および/またはステップを実行するための手段の一例であってもよい。

また、本開示の態様は、フローチャート、流れ図、構造図、またはブロック図として描かれる処理として説明されてもよいことに留意されたい。フローチャートが操作を順次処理として説明してもよいが、操作の多くは並行してまたは同時に実行することができる。さらに、操作の順序は再編されてもよい。処理は、その操作が完了すると終了する。処理は、方法、機能、手続、サブルーチン、サブプログラム、他に対応してもよい。処理が機能に対応すると、その終了は呼出し機能または主機能への機能の復帰に対応する。

さらに、記憶媒体が、リードオンリーメモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイスおよび/または他の機械可読媒体、ならびに、プロセッサ可読媒体、ならびに/あるいは情報を記憶するためのコンピュータ可読媒体を含むデータを記憶するための1つまたは複数のデバイスを表してもよい。「機械可読媒体」、「コンピュータ可読媒体」、および/または「プロセッサ可読媒体」という用語は、限定されないが、携帯記憶デバイスまたは固定記憶デバイス、光記憶デバイスなどの非一時的媒体、ならびに命令および/またはデータを記憶し、含みまたは担持することができる様々な他の媒体を含んでもよい。したがって、本明細書で説明された様々な方法は、「機械可読媒体」、「コンピュータ可読媒体」、および/または「プロセッサ可読媒体」に記憶されてもよい命令および/またはデータによって完全にまたは部分的に実装されてもよく、1つまたは複数のプロセッサ、機械および/またはデバイスによって実行されてもよい。

その上、本開示の態様は、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコードまたはその任意の組合せによって実装されてもよい。ソフトウェア、ファームウェア、ミドルウェアまたはマイクロコードで実装されると、必要なタスクを実行するためのプログラムコードまたはコードセグメントは、記憶媒体または他の記憶装置などの機械可読媒体に記憶されてもよい。プロセッサが必要なタスクを実行してもよい。コードセグメントは、手続、機能、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェアパッケージ、クラス、あるいは命令、データ構造、またはプログラムステートメントの任意の組合せを表してもよい。コードセグメントは、情報、データ、引数、パラメータ、またはメモリコンテンツを送りかつ/または受け取ることによって別のコードセグメントまたはハードウェア回路に結合されてもよい。情報、引数、パラメータ、データ、他は、メモリ共有、メッセージパッシング、トークンパッシング、ネットワーク伝送、他を含む任意の適切な手段を介して送られ、転送され、または伝送されてもよい。

本明細書で開示された例に関連して説明された様々な例示的な論理ブロック、モジュール、回路、要素および/または構成要素は、汎用プロセッサ、デジタル信号プロセッサ(DSP)、アプリケーション特有の集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)または他のプログラマブル論理構成要素、個別ゲートまたはトランジスタ論理、個別ハードウェア構成要素、あるいは本明細書で説明された機能を実行するように設計されたその任意の組合せを用いて実装または実行されてもよい。汎用プロセッサはマイクロプロセッサであってもよいが、代案では、プロセッサは任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械であってもよい。プロセッサはまた、コンピューティング構成要素の組合せ、たとえば、DSPとマイクロプロセッサ、いくつかのマイクロプロセッサ、DSPコアに関連する1つまたは複数のマイクロプロセッサ、あるいは任意の他のそのような構成の組合せとして実装されてもよい。

本明細書で開示された例に関連して説明された方法またはアルゴリズムは、直接ハードウェアで、プロセッサによって実行可能なソフトウェアモジュールで、あるいは両方の組合せで、処理ユニット、プログラミング命令、または他の指示の形式で、具現されてもよく、単一のデバイスに含まれてもよく、複数のデバイスにわたって分配されてもよい。ソフトウェアモジュールが、RAMメモリ、フラッシュメモリ、ROMメモリ、EPROMメモリ、EEPROMメモリ、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または当業界で知られている任意の他の形式の記憶媒体に存在してもよい。記憶媒体は、プロセッサが記憶媒体から情報を読み取り、記憶媒体に情報を書き込むことができるように、プロセッサに結合されてもよい。代案では、記憶媒体はプロセッサに統合されてもよい。

本明細書で開示された態様に関連して説明された様々な例示的な論理ブロック、モジュール、回路、および/またはアルゴリズムステップは、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装されてもよい。ハードウェアおよびソフトウェアのこの互換性を明確に説明するために、様々な例示的な構成要素、ブロック、モジュール、回路、およびステップが、それらの機能性に関して全般的に上で説明されてきた。そのような機能性がハードウェアとしてまたはソフトウェアとして実装されるかどうかは、特定のアプリケーションおよびシステム全体に課された設計制約に依存する。

本明細書で説明された本発明の様々な特徴は、本発明から逸脱することなく異なるシステムで実装することができる。本開示の前述の態様は単に例であり、本発明を限定すると解釈されるべきではないことに留意すべきである。本開示の態様の説明は例示的であることを意図するものであり、特許請求の範囲の範囲を限定することを意図するものではない。したがって、本教示は他の種類の装置に容易に適用することができ、多くの代替、修正、および変形が当業者には明らかであろう。

200 zビット乱数R
202 xビットワードA
204 xビットワードB
206 xビットワードn
600 素数生成デバイス
602 処理回路
604 メモリ回路
606 I/Oインターフェース
608 通信インターフェース
610 バス
702 乱数生成器モジュール/回路
704 素数判定法モジュール/回路
706 ビット/ワード置換モジュール/回路
802 移動電話
804 ラップトップコンピュータ
806 固定位置端末

Claims (8)

1. (a)乱数生成器によって、n個のxビットワードを含む乱数を生成するステップであって、前記nは3より大きいまたは3に等しく、前記乱数は第1のメモリ回路に記憶される、ステップと、
   (b)素数判定法回路によって、前記第1のメモリ回路に記憶された前記乱数に対して素数判定法を実行するステップと、
   (c)前記素数判定法回路によって、前記第1のメモリ回路に記憶された前記乱数が前記素数判定法に不合格であったと判定するステップと、
   (d)ビット置換回路によって、前記乱数の1つまたは複数のxビットワードをランダムに生成されたビットに置換するステップであって、
   置換される前記1つまたは複数のxビットワードの各々は、
   前記乱数の最上位ビットを部分的に占有する最初のxビットワード、
   前記乱数の最下位ビットを部分的に占有する最後のxビットワード、又は、
   前記最初のxビットワードおよび前記最後のxビットワード以外のxビットワード
   であり、
   置換される前記1つまたは複数のxビットワードの各々は、x個のランダムに生成されたビットに置換され、かつ、
   置換される前記1つまたは複数のxビットワードの各々は、ランダムに選択される、ステップと、
   (e)前記第1のメモリ回路に記憶された前記乱数が(b)で実行される前記実行された素数判定法に合格したと判定されるまで、(b)、(c)、および(d)を繰り返し反復するステップと、
   (f)前記素数判定法に合格したと判定された前記乱数を第2のメモリ回路に記憶するステップと、
   (g)処理回路によって、前記第2のメモリ回路に記憶された前記乱数を使用して暗号鍵を生成するステップと、
   を含む、方法。
2. 各xビットワードは、少なくとも3ビットまたは3ビットより大きいビットを含む、請求項1に記載の方法。
3. n個のxビットワードを含む乱数を生成するように適合された乱数生成器回路であって、前記nは3より大きいまたは3に等しい、乱数生成器回路と、
   前記乱数生成器回路に通信可能に結合され、前記乱数を記憶するように適合された第1のメモリ回路と、
   前記乱数生成器回路に通信可能に結合され、
   (a)前記第1のメモリ回路に記憶された前記乱数に対して素数判定法を実行し、
   (b)生成された前記乱数が前記素数判定法に不合格であったと判定する
   ように適合された素数判定法回路と、
   前記素数判定法回路に通信可能に結合され、
   (c)前記乱数の1つまたは複数のxビットワードをランダムに生成されたビットに置換する
   ように適合されたビット置換回路であって、
   置換される前記1つまたは複数のxビットワードの各々は、
   前記乱数の最上位ビットを部分的に占有する最初のxビットワード、
   前記乱数の最下位ビットを部分的に占有する最後のxビットワード、又は、
   前記最初のxビットワードおよび前記最後のxビットワード以外のxビットワード
   であり、
   置換される前記1つまたは複数のxビットワードの各々は、x個のランダムに生成されたビットに置換され、かつ、
   置換される前記1つまたは複数のxビットワードの各々は、ランダムに選択され、
   前記素数判定法回路が、前記第1のメモリ回路に記憶された前記乱数が(a)で実行される前記素数判定法に合格したと判定するまで、前記素数判定法回路によって(a)および(b)を実行すること、および、前記ビット置換回路によって(c)を実行することが繰り返し反復される、ビット置換回路と、
   前記ビット置換回路に通信可能に結合され、前記素数判定法に合格したと判定された前記乱数を記憶するように適合された第2のメモリ回路と、
   前記第2のメモリ回路に通信可能に接続された処理回路であって、前記処理回路は、
   前記第2のメモリ回路に記憶された前記乱数を使用して暗号鍵を生成するように構成された、処理回路と、
   を備える、装置。
4. 各xビットワードは、少なくとも3ビットまたは3ビットより大きいビットを含む、請求項3に記載の装置。
5. (a)n個のxビットワードを含む乱数を生成するように適合された生成するための手段であって、前記nは3より大きいまたは3に等しく、前記乱数はメモリ回路に記憶される、手段と、
   (b)前記メモリ回路に記憶された前記乱数に対して素数判定法を実行するように適合された実行するための手段と、
   (c)前記メモリ回路に記憶された前記乱数が前記素数判定法に不合格であったと判定するように適合された判定するための手段と、
   (d)前記乱数の1つまたは複数のxビットワードをランダムに生成されたビットに置換するように適合された置換するための手段であって、
   置換される前記1つまたは複数のxビットワードの各々は、
   前記乱数の最上位ビットを部分的に占有する最初のxビットワード、
   前記乱数の最下位ビットを部分的に占有する最後のxビットワード、又は、
   前記最初のxビットワードおよび前記最後のxビットワード以外のxビットワード
   であり、
   置換される前記1つまたは複数のxビットワードの各々は、x個のランダムに生成されたビットに置換され、かつ、
   置換される前記1つまたは複数のxビットワードの各々は、ランダムに選択され、
   前記実行するための手段が、前記メモリ回路に記憶された前記乱数が(b)で実行される前記素数判定法に合格したと判定するまで、前記実行するための手段によって(b)を実行すること、前記判定するための手段によって(c)を実行すること、および、前記置換するための手段によって(d)を実行することが繰り返し反復される、手段と、
   前記素数判定法に合格したと判定された前記乱数を記憶するための手段と、
   前記記憶するための手段に記憶された前記乱数を使用して暗号鍵を生成するための手段と、
   を備える、装置。
6. 各xビットワードは、少なくとも3ビットまたは3ビットより大きいビットを含む、請求項5に記載の装置。
7. 1つまたは複数の命令を格納したコンピュータ可読記憶媒体であって、少なくとも1つのプロセッサによって実行されると前記命令が前記プロセッサに
   (a)乱数生成器によって、n個のxビットワードを含む乱数を生成させ、
   ここで、前記nは3より大きいまたは3に等しく、前記乱数は第1のメモリ回路に記憶され、
   (b)素数判定法回路によって、前記第1のメモリ回路に記憶された前記乱数に対して素数判定法を実行させ、
   (c)前記素数判定法回路によって、前記第1のメモリ回路に記憶された前記乱数が前記素数判定法に不合格であったと判定させ、
   (d)ビット置換回路によって、前記乱数の1つまたは複数のxビットワードをランダムに生成されたビットに置換させ、
   ここで、
   置換される前記1つまたは複数のxビットワードの各々は、
   前記乱数の最上位ビットを部分的に占有する最初のxビットワード、
   前記乱数の最下位ビットを部分的に占有する最後のxビットワード、又は、
   前記最初のxビットワードおよび前記最後のxビットワード以外のxビットワード
   であり、
   置換される各xビットワードは、x個のランダムに生成されたビットに置換され、かつ、
   置換される前記1つまたは複数のxビットワードの各々は、ランダムに選択され、
   (e)前記第1のメモリ回路に記憶された前記乱数が(b)で実行される前記実行された素数判定法に合格したと判定されるまで、(b)、(c)、および(d)を繰り返し反復させ、
   (f)前記素数判定法に合格したと判定された前記乱数を第2のメモリ回路に記憶させ、
   (g)処理回路によって、前記第2のメモリ回路に記憶された前記乱数を使用して暗号鍵を生成させる、
   非一時的コンピュータ可読記憶媒体。
8. 各xビットワードは、少なくとも3ビットまたは3ビットより大きいビットを含む、請求項7に記載の非一時的コンピュータ可読記憶媒体。

Images