(57)【要約】  1つの特徴は、kビットを有する乱数シードSを生成することと、nビットを有する乱数RをシードSに基づいて生成することであって、kがnよりも小さい、生成することと、乱数Rが素数であるかどうかを決定することとを、繰り返して行うことによって素数を生成するための方法に関係する。ステップは、生成された乱数Rが素数であると決定されるまで繰り返され、その際、乱数Rを生成するために使用された乱数シードSがメモリ回路に記憶される。後で、記憶された乱数シードSは、メモリ回路から取り出され得、素数は、乱数シードSに基づいて再生成される。一例では、生成される乱数Rは、さらに、セキュアメモリ回路に記憶され得る秘密鍵kSに基づく。
2016535310.tif 000002
【特許請求の範囲】
【請求項１】
生成される乱数Rが素数であると決定されるまで、
kビットを有する乱数シードSを生成することと、
nビットを有する前記乱数Rを前記シードSに基づいて生成することであって、kがnよりも小さい、生成することと、
前記乱数Rが素数であるかどうかを決定することとを、
繰り返し行うことによって素数を生成するステップと、
素数であると決定された前記乱数Rを生成するために使用された前記乱数シードSをメモリ回路に記憶するステップと
を備える方法。
【請求項２】
前記記憶された乱数シードSを前記メモリ回路から取り出すステップと、
前記乱数シードSに基づいて前記素数を再生成するステップと
をさらに備える請求項1に記載の方法。
【請求項３】
前記素数に基づいて暗号鍵を生成するステップをさらに備える、
請求項2に記載の方法。
【請求項４】
前記シードSを記憶した後、前記乱数Rをメモリ回路から消去するステップをさらに備える、
請求項1に記載の方法。
【請求項５】
前記乱数Rを生成するステップは、さらに秘密鍵kSに基づく、請求項1に記載の方法。
【請求項６】
素数であると決定された前記乱数Rを生成するために使用された前記秘密鍵kSをセキュアメモリ回路に記憶するステップをさらに備える、
請求項5に記載の方法。
【請求項７】
前記乱数シードSは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶される、請求項1に記載の方法。
【請求項８】
前記シードSに基づいて前記乱数Rを生成するステップは、
前記シードSを入力として受信するとともに前記乱数Rを出力として生成する一方向関数fを実行することを含み、前記一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである、
請求項1に記載の方法。
【請求項９】
メモリ回路と、
前記メモリ回路に通信可能に結合された処理回路とを備える装置であって、前記処理回路は、
生成される乱数Rが素数であると決定されるまで、
kビットを有する乱数シードSを生成することと、
nビットを有する前記乱数Rを前記シードSに基づいて生成することであって、kがnよりも小さい、生成することと、
前記乱数Rが素数であるかどうかを決定することとを、
繰り返し行うことによって素数を生成し、
素数であると決定された前記乱数Rを生成するために使用された前記乱数シードSを前記メモリ回路に記憶するように構成される、装置。
【請求項１０】
前記処理回路は、
前記記憶された乱数シードSを前記メモリ回路から取り出し、
前記乱数シードSに基づいて前記素数を再生成するようにさらに構成される、
請求項9に記載の装置。
【請求項１１】
前記処理回路は、
前記素数に基づいて暗号鍵を生成するようにさらに構成される、
請求項10に記載の装置。
【請求項１２】
前記乱数シードSは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶される、請求項9に記載の装置。
【請求項１３】
素数であると決定された前記乱数Rを生成することは、さらに秘密鍵kSに基づき、前記処理回路は、前記秘密鍵kSをセキュアメモリ回路に記憶するようにさらに構成される、請求項9に記載の装置。
【請求項１４】
生成される乱数Rが素数であると決定されるまで、
kビットを有する乱数シードSを生成することと、
nビットを有する前記乱数Rを前記シードSに基づいて生成することであって、kがnよりも小さい、生成することと、
前記乱数Rが素数であるかどうかを決定することとを、
繰り返し行うことによって素数を生成するための手段と、
素数であると決定された前記乱数Rを生成するために使用された前記乱数シードSをメモリ回路に記憶するための手段と
を備える装置。
【請求項１５】
前記記憶された乱数シードSを前記メモリ回路から取り出すための手段と、
前記乱数シードSに基づいて前記素数を再生成するための手段と
をさらに備える請求項14に記載の装置。
【請求項１６】
前記乱数シードSは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶される、請求項14に記載の装置。
【請求項１７】
素数であると決定された前記乱数Rを生成することは、さらに秘密鍵kSに基づき、前記装置は、前記秘密鍵kSをセキュアメモリ回路に記憶するための手段をさらに備える、請求項14に記載の装置。
【請求項１８】
そこに記憶された1つまたは複数の命令を有するコンピュータ可読記憶媒体であって、前記命令は、少なくとも1つのプロセッサによって実行されると、前記プロセッサに、
生成される乱数Rが素数であると決定されるまで、
kビットを有する乱数シードSを生成することと、
nビットを有する前記乱数Rを前記シードSに基づいて生成することであって、kがnよりも小さい、生成することと、
前記乱数Rが素数であるかどうかを決定することとを、
繰り返し行うことによって素数を生成させ、
素数であると決定された前記乱数Rを生成するために使用された前記乱数シードSをメモリ回路に記憶させる、コンピュータ可読記憶媒体。
【請求項１９】
前記命令は、前記プロセッサに、さらに、
前記記憶された乱数シードSを前記メモリ回路から取り出させ、
前記乱数シードSに基づいて前記素数を再生成させる、
請求項18に記載のコンピュータ可読記憶媒体。
【請求項２０】
kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成するステップと、
前記複数の追加シードTiのうちの相異なる追加シードおよび前記乱数シードSにそれぞれ基づく複数の第2シードSiを生成するステップと、
nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成するステップであって、前記複数の乱数Riの各々は、前記複数の第2シードSiのうちの相異なる第2シードに基づくステップと、
前記複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定するステップであって、前記乱数RPは、前記複数の第2シードSiのうちの第2シードSPに基づき、前記第2シードSPは、前記複数の追加シードTiのうちの追加シードTPおよび前記乱数シードSに基づくステップと、
前記乱数シードSおよび前記追加シードTPをメモリ回路に記憶するステップと
を備える方法。
【請求項２１】
前記複数の乱数Riは、さらに秘密鍵kSに基づき、前記方法は、前記秘密鍵kSをセキュアメモリ回路に記憶するステップをさらに備える、請求項20に記載の方法。
【請求項２２】
前記記憶された乱数シードSおよび前記追加シードTPを前記メモリ回路から取り出すステップと、
前記乱数シードSおよび前記追加シードTPに基づいて、前記素数性乱数RPを再生成するステップと
をさらに備える請求項20に記載の方法。
【請求項２３】
前記乱数シードSおよび前記追加シードTPは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶され、前記方法は、
1つまたは複数の素数を得るための前記要求を前記暗号鍵生成プロセスから受信するステップと、
前記素数性乱数RPに基づいて暗号鍵を生成するステップと、
前記暗号鍵を前記暗号鍵生成プロセスに供給するステップと
をさらに備える請求項22に記載の方法。
【請求項２４】
前記複数の第2シードSiのうちの前記相異なる第2シードに基づいて前記複数の乱数Riを生成するステップは、
前記複数の第2シードSiの各々を入力として受信するとともに前記複数の乱数Riを出力として生成する一方向関数fを実行することを含み、前記一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである、
請求項21に記載の方法。
【請求項２５】
前記複数の乱数Riのうちの少なくとも1つの乱数が素数でないことを決定するステップと、
gビットを有する別の追加シードT2を生成するステップと、
前記追加シードT2および前記乱数シードSに基づいて、別の第2シードS2を生成するステップと、
nビットを有する別の乱数R2を生成するステップであって、前記乱数R2は、前記第2シードS2に基づくステップと、
前記乱数R2が素数であることを決定するステップと、
前記追加シードT2を前記メモリ回路に記憶するステップと
をさらに備える請求項21に記載の方法。
【請求項２６】
前記記憶された乱数シードSおよび前記追加シードT2を前記メモリ回路から取り出すステップと、
前記乱数シードSおよび前記追加シードT2に基づいて、前記素数性乱数R2を再生成するステップと
をさらに備える請求項25に記載の方法。
【請求項２７】
所定の数の素数を得るための要求を受信するステップと、
前記方法の別の追加シードT2を生成するステップと、前記追加シードT2および前記乱数シードSに基づいて別の第2シードS2を生成するステップと、nビットを有する別の乱数R2を生成するステップであって前記乱数R2が前記第2シードS2に基づくステップと、前記乱数R2が素数であることを決定するステップと、前記追加シードT2を前記メモリ回路に記憶するステップとを、異なる素数にそれぞれ関連付けられたいくつかの追加シードが記憶され前記所定の数に等しくなるまで繰り返すステップと
をさらに備える請求項25に記載の方法。
【請求項２８】
メモリ回路と、
前記メモリ回路に通信可能に結合された処理回路とを備える装置であって、前記処理回路は、
kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成し、
前記複数の追加シードTiのうちの相異なる追加シードおよび前記乱数シードSにそれぞれ基づく複数の第2シードSiを生成し、
nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成することであって、前記複数の乱数Riの各々は、前記複数の第2シードSiのうちの相異なる第2シードに基づくことをし、
前記複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定することであって、前記乱数RPは、前記複数の第2シードSiのうちの第2シードSPに基づき、前記第2シードSPは、前記複数の追加シードTiのうちの追加シードTPおよび前記乱数シードSに基づくことをし、
前記乱数シードSおよび前記追加シードTPを前記メモリ回路に記憶するように構成される、装置。
【請求項２９】
前記複数の乱数Riは、さらに秘密鍵kSに基づき、前記処理回路は、前記秘密鍵kSをセキュアメモリ回路に記憶するようにさらに構成される、請求項28に記載の装置。
【請求項３０】
前記処理回路は、
前記記憶された乱数シードSおよび前記追加シードTPを前記メモリ回路から取り出し、
前記乱数シードSおよび前記追加シードTPに基づいて、前記素数性乱数RPを再生成するようにさらに構成される、
請求項28に記載の装置。
【請求項３１】
前記乱数シードSおよび前記追加シードTPは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶され、前記処理回路は、
1つまたは複数の素数を得るための前記要求を前記暗号鍵生成プロセスから受信し、
前記素数性乱数RPに基づいて暗号鍵を生成し、
前記暗号鍵を前記暗号鍵生成プロセスに供給するようにさらに構成される、
請求項30に記載の装置。
【請求項３２】
前記複数の第2シードSiのうちの前記相異なる第2シードに基づいて前記複数の乱数Riを生成することは、
前記複数の第2シードSiの各々を入力として受信するとともに前記複数の乱数Riを出力として生成する一方向関数fを実行するようにさらに構成される前記処理回路を含み、前記一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである、
請求項28に記載の装置。
【請求項３３】
前記処理回路は、
前記複数の乱数Riのうちの少なくとも1つの乱数が素数でないことを決定し、
gビットを有する別の追加シードT2を生成し、
前記追加シードT2および前記乱数シードSに基づいて、別の第2シードS2を生成し、
nビットを有する別の乱数R2を生成することであって、前記乱数R2は、前記第2シードS2に基づくことをし、
前記乱数R2が素数であることを決定し、
前記追加シードT2を前記メモリ回路に記憶するようにさらに構成される、
請求項28に記載の装置。
【請求項３４】
前記処理回路は、
前記記憶された乱数シードSおよび前記追加シードT2を前記メモリ回路から取り出し、
前記乱数シードSおよび前記追加シードT2に基づいて、前記素数性乱数R2を再生成するようにさらに構成される、
請求項33に記載の装置。
【請求項３５】
kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成するための手段と、
前記複数の追加シードTiのうちの相異なる追加シードおよび前記乱数シードSにそれぞれ基づく複数の第2シードSiを生成するための手段と、
nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成するための手段であって、前記複数の乱数Riの各々は、前記複数の第2シードSiのうちの相異なる第2シードに基づく手段と、
前記複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定するための手段であって、前記乱数RPは、前記複数の第2シードSiのうちの第2シードSPに基づき、前記第2シードSPは、前記複数の追加シードTiのうちの追加シードTPおよび前記乱数シードSに基づく手段と、
前記乱数シードSおよび前記追加シードTPをメモリ回路に記憶するための手段と
を備える装置。
【請求項３６】
前記記憶された乱数シードSおよび前記追加シードTPを前記メモリ回路から取り出すための手段と、
前記乱数シードSおよび前記追加シードTPに基づいて、前記素数性乱数RPを再生成するための手段と
をさらに備える請求項35に記載の装置。
【請求項３７】
そこに記憶された1つまたは複数の命令を有するコンピュータ可読記憶媒体であって、前記命令は、少なくとも1つのプロセッサによって実行されると、前記プロセッサに、
kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成させ、
前記複数の追加シードTiのうちの相異なる追加シードおよび前記乱数シードSにそれぞれ基づく複数の第2シードSiを生成させ、
nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成することであって、前記複数の乱数Riの各々は、前記複数の第2シードSiのうちの相異なる第2シードに基づくことをさせ、
前記複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定することであって、前記乱数RPは、前記複数の第2シードSiのうちの第2シードSPに基づき、前記第2シードSPは、前記複数の追加シードTiのうちの追加シードTPおよび前記乱数シードSに基づくことをさせ、
前記乱数シードSおよび前記追加シードTPをメモリ回路に記憶させる、コンピュータ可読記憶媒体。
【請求項３８】
前記命令は、前記プロセッサに、さらに、
前記記憶された乱数シードSおよび前記追加シードTPを前記メモリ回路から取り出させ、
前記乱数シードSおよび前記追加シードTPに基づいて、前記素数性乱数RPを再生成させる、
請求項37に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
様々な特徴は、暗号技術に関し、より詳細には、素数の生成および効率のよい記憶のための方法および装置に関する。
【背景技術】
【０００２】
Rivest Shamir Adleman(RSA)アルゴリズムなどの多くの暗号セキュリティアルゴリズムは、暗号鍵を利用して動作する。そのような鍵は、通常、比較的大きい(たとえば、512ビット、1,024ビットなどの)素数を必要とすることがある鍵生成プロセスを使用して生成される。しかしながら、素数生成は、低速なプロセスであり、素数生成と関連した処理時間は、通常、鍵生成プロセスにおけるボトルネックとして影響を及ぼす。必要となる処理時間は、鍵生成プロセスによって生成されるべき鍵のビット長の3乗に比例する。たとえば、2,048ビットおよび3,072ビットの暗号鍵を生成することは、1,024ビットの鍵を生成することよりも、それぞれ、8倍および27倍低速の場合がある。電力および速度の制約と関係があるモバイルデバイスの適用例において、電力消費および処理時間のそのような増大は有害である。
【０００３】
いくつかの適用例によれば、暗号鍵は、アプリケーションによって実際に必要とされる前に生成されるという点で、「オフライン」で生成され得る。そのようなオフライン方式で生成される暗号鍵を生成するために使用される暗号鍵または素数は、通常、メモリに記憶され、次いで、要求に応じてアプリケーションに引き渡される。その場合には、上述された鍵生成と関連した処理時間におけるボトルネックは、実質的に除去される。しかしながら、そのようなオフライン鍵生成方式に伴う1つの未解決の課題は、鍵を生成するために使用される鍵および/または素数が比較的大きい(たとえば、1,024ビットを越える)場合があることと、そのような大きい鍵および/または素数を記憶するために求められる必要なメモリ回路が常に容易に利用可能であるとは限らないことである。暗号鍵および素数はエントロピーが大きく従来の圧縮アルゴリズムを用いて効率よく圧縮され得ないので、問題を解決するために、通常のデータ圧縮技法はこれらの場合ではあまり適切でない。
【０００４】
したがって、RSAなどの暗号セキュリティアルゴリズムでの使用のための大きい素数を記憶するために必要とされるメモリの量を最小限に抑えるために、素数の生成および記憶において助けとなる新しい方法および装置の必要性が存在する。
【発明の概要】
【課題を解決するための手段】
【０００５】
1つの特徴は、素数生成のためのシード値を生成および記憶するための方法を提供する。方法は、生成される乱数Rが素数であると決定されるまで、kビットを有する乱数シードSを生成することと、nビットを有する乱数RをシードSに基づいて生成することであって、kがnよりも小さい、生成することと、乱数Rが素数であるかどうかを決定することとを、繰り返し行うことによって素数を生成するステップを備える。素数であると決定された乱数Rを生成するために使用された乱数シードSは、メモリ回路に記憶される。一態様によれば、方法は、記憶された乱数シードSをメモリ回路から取り出すステップと、乱数シードSに基づいて素数を再生成するステップとをさらに備える。別の態様によれば、方法は、素数に基づいて暗号鍵を生成するステップをさらに備える。
【０００６】
一態様によれば、方法は、シードSを記憶した後、乱数Rをメモリ回路から消去するステップをさらに備える。別の態様によれば、乱数Rを生成するステップは、さらに秘密鍵kSに基づく。さらに別の態様によれば、方法は、素数であると決定された乱数Rを生成するために使用された秘密鍵kSをセキュアメモリ回路に記憶するステップをさらに備える。
【０００７】
一態様によれば、乱数シードSは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶される。別の態様によれば、シードSに基づいて乱数Rを生成するステップは、シードSを入力として受信するとともに乱数Rを出力として生成する一方向関数fを実行することを含み、一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである。
【０００８】
別の特徴は、素数生成のためのシード値を生成および記憶するための装置を提供し、その場合、装置は、メモリ回路と、メモリ回路に通信可能に結合された処理回路とを備え、処理回路は、生成される乱数Rが素数であると決定されるまで、kビットを有する乱数シードSを生成することと、nビットを有する乱数RをシードSに基づいて生成することであって、kがnよりも小さい、生成することと、乱数Rが素数であるかどうかを決定することとを、繰り返し行うことによって素数を生成し、素数であると決定された乱数Rを生成するために使用された乱数シードSをメモリ回路に記憶するように構成される。一態様によれば、処理回路は、記憶された乱数シードSをメモリ回路から取り出し、乱数シードSに基づいて素数を再生成するようにさらに構成される。別の態様によれば、処理回路は、素数に基づいて暗号鍵を生成するようにさらに構成される。さらに別の態様によれば、乱数シードSは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶される。別の態様によれば、素数であると決定された乱数Rを生成することは、さらに秘密鍵kSに基づき、処理回路は、秘密鍵kSをセキュアメモリ回路に記憶するようにさらに構成される。
【０００９】
別の特徴は、素数生成のためのシード値を生成および記憶するための装置を提供し、その場合、装置は、生成される乱数Rが素数であると決定されるまで、kビットを有する乱数シードSを生成することと、nビットを有する乱数RをシードSに基づいて生成することであって、kがnよりも小さい、生成することと、乱数Rが素数であるかどうかを決定することとを、繰り返し行うことによって素数を生成するための手段と、素数であると決定された乱数Rを生成するために使用された乱数シードSをメモリ回路に記憶するための手段とを備える。一態様によれば、装置は、記憶された乱数シードSをメモリ回路から取り出すための手段と、乱数シードSに基づいて素数を再生成するための手段とをさらに備える。別の態様によれば、素数であると決定された乱数Rを生成することは、さらに秘密鍵kSに基づき、装置は、秘密鍵kSをセキュアメモリ回路に記憶するための手段をさらに備える。
【００１０】
別の特徴は、そこに記憶された1つまたは複数の命令を有するコンピュータ可読記憶媒体を提供し、命令は、少なくとも1つのプロセッサによって実行されると、プロセッサに、生成される乱数Rが素数であると決定されるまで、kビットを有する乱数シードSを生成することと、nビットを有する乱数RをシードSに基づいて生成することであって、kがnよりも小さい、生成することと、乱数Rが素数であるかどうかを決定することとを、繰り返し行うことによって素数を生成させ、素数であると決定された乱数Rを生成するために使用された乱数シードSをメモリ回路に記憶させる。一態様によれば、命令は、プロセッサに、さらに、記憶された乱数シードSをメモリ回路から取り出させ、乱数シードSに基づいて素数を再生成させる。
【００１１】
別の特徴は、素数生成のためのシード値を生成および記憶するための方法を提供し、方法は、kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成するステップと、複数の追加シードTiのうちの相異なる追加シードおよび乱数シードSにそれぞれ基づく複数の第2シードSiを生成するステップと、nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成するステップであって、複数の乱数Riの各々は、複数の第2シードSiのうちの相異なる第2シードに基づくステップと、複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定するステップであって、乱数RPは、複数の第2シードSiのうちの第2シードSPに基づき、第2シードSPは、複数の追加シードTiのうちの追加シードTPおよび乱数シードSに基づくステップと、乱数シードSおよび追加シードTPをメモリ回路に記憶するステップとを備える。一態様によれば、複数の乱数Riは、さらに秘密鍵kSに基づき、方法は、秘密鍵kSをセキュアメモリ回路に記憶するステップをさらに備える。別の態様によれば、方法は、記憶された乱数シードSおよび追加シードTPをメモリ回路から取り出すステップと、乱数シードSおよび追加シードTPに基づいて、素数性乱数RPを再生成するステップとをさらに備える。さらに別の態様によれば、乱数シードSおよび追加シードTPは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶され、方法は、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信するステップと、素数性乱数RPに基づいて暗号鍵を生成するステップと、暗号鍵を暗号鍵生成プロセスに供給するステップとをさらに備える。
【００１２】
一態様によれば、複数の第2シードSiのうちの相異なる第2シードに基づいて複数の乱数Riを生成するステップは、複数の第2シードSiの各々を入力として受信するとともに複数の乱数Riを出力として生成する一方向関数fを実行することを含み、一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである。別の態様によれば、方法は、複数の乱数Riのうちの少なくとも1つの乱数が素数でないことを決定するステップと、gビットを有する別の追加シードT2を生成するステップと、追加シードT2および乱数シードSに基づいて、別の第2シードS2を生成するステップと、nビットを有する別の乱数R2を生成するステップであって、乱数R2は、第2シードS2に基づくステップと、乱数R2が素数であることを決定するステップと、追加シードT2をメモリ回路に記憶するステップとをさらに備える。さらに別の態様によれば、方法は、記憶された乱数シードSおよび追加シードT2をメモリ回路から取り出すステップと、乱数シードSおよび追加シードT2に基づいて、素数性乱数R2を再生成するステップとをさらに備える。別の態様によれば、方法は、所定の数の素数を得るための要求を受信するステップと、別の追加シードT2を生成すること、追加シードT2および乱数シードSに基づいて別の第2シードS2を生成すること、nビットを有する別の乱数R2を生成することであって乱数R2が第2シードS2に基づくこと、乱数R2が素数であることを決定すること、および追加シードT2をメモリ回路に記憶することの方法ステップを、異なる素数にそれぞれ関連付けられたいくつかの追加シードが記憶され所定の数に等しくなるまで繰り返すステップとをさらに備える。
【００１３】
別の特徴は、素数生成のためのシード値を生成および記憶するための装置を提供し、その場合、装置は、メモリ回路と、メモリ回路に通信可能に結合された処理回路とを備え、処理回路は、kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成し、複数の追加シードTiのうちの相異なる追加シードおよび乱数シードSにそれぞれ基づく複数の第2シードSiを生成し、nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成することであって、複数の乱数Riの各々は、複数の第2シードSiのうちの相異なる第2シードに基づくことをし、複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定することであって、乱数RPは、複数の第2シードSiのうちの第2シードSPに基づき、第2シードSPは、複数の追加シードTiのうちの追加シードTPおよび乱数シードSに基づくことをし、乱数シードSおよび追加シードTPをメモリ回路に記憶するように構成される。一態様によれば、複数の乱数Riは、さらに秘密鍵kSに基づき、処理回路は、秘密鍵kSをセキュアメモリ回路に記憶するようにさらに構成される。別の態様によれば、処理回路は、記憶された乱数シードSおよび追加シードTPをメモリ回路から取り出し、乱数シードSおよび追加シードTPに基づいて、素数性乱数RPを再生成するようにさらに構成される。さらに別の態様によれば、乱数シードSおよび追加シードTPは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶され、処理回路は、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信し、素数性乱数RPに基づいて暗号鍵を生成し、暗号鍵を暗号鍵生成プロセスに供給するようにさらに構成される。
【００１４】
一態様によれば、複数の第2シードSiのうちの相異なる第2シードに基づいて複数の乱数Riを生成することは、複数の第2シードSiの各々を入力として受信するとともに複数の乱数Riを出力として生成する一方向関数fを実行するようにさらに構成される処理回路を含み、一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである。別の態様によれば、処理回路は、複数の乱数Riのうちの少なくとも1つの乱数が素数でないことを決定し、gビットを有する別の追加シードT2を生成し、追加シードT2および乱数シードSに基づいて、別の第2シードS2を生成し、nビットを有する別の乱数R2を生成することであって、乱数R2は、第2シードS2に基づくことをし、乱数R2が素数であることを決定し、追加シードT2をメモリ回路に記憶するようにさらに構成される。さらに別の態様によれば、処理回路は、記憶された乱数シードSおよび追加シードT2をメモリ回路から取り出し、乱数シードSおよび追加シードT2に基づいて、素数性乱数R2を再生成するようにさらに構成される。
【００１５】
別の特徴は、素数生成のためのシード値を生成および記憶するための装置を提供し、その場合、装置は、kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成するための手段と、複数の追加シードTiのうちの相異なる追加シードおよび乱数シードSにそれぞれ基づく複数の第2シードSiを生成するための手段と、nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成するための手段であって、複数の乱数Riの各々は、複数の第2シードSiのうちの相異なる第2シードに基づく手段と、複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定するための手段であって、乱数RPは、複数の第2シードSiのうちの第2シードSPに基づき、第2シードSPは、複数の追加シードTiのうちの追加シードTPおよび乱数シードSに基づく手段と、乱数シードSおよび追加シードTPをメモリ回路に記憶するための手段とを備える。一態様によれば、装置は、記憶された乱数シードSおよび追加シードTPをメモリ回路から取り出すための手段と、乱数シードSおよび追加シードTPに基づいて、素数性乱数RPを再生成するための手段とをさらに備える。
【００１６】
別の特徴は、そこに記憶された1つまたは複数の命令を有するコンピュータ可読記憶媒体を提供し、命令は、少なくとも1つのプロセッサによって実行されると、プロセッサに、kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成させ、複数の追加シードTiのうちの相異なる追加シードおよび乱数シードSにそれぞれ基づく複数の第2シードSiを生成させ、nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成することであって、複数の乱数Riの各々は、複数の第2シードSiのうちの相異なる第2シードに基づくことをさせ、複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定することであって、乱数RPは、複数の第2シードSiのうちの第2シードSPに基づき、第2シードSPは、複数の追加シードTiのうちの追加シードTPおよび乱数シードSに基づくことをさせ、乱数シードSおよび追加シードTPをメモリ回路に記憶させる。一態様によれば、命令は、プロセッサに、さらに、記憶された乱数シードSおよび追加シードTPをメモリ回路から取り出させ、乱数シードSおよび追加シードTPに基づいて、素数性乱数RPを再生成させる。
【図面の簡単な説明】
【００１７】
【図１】素数生成のためのシード値を生成および記憶するための方法の流れ図の第1の例を示す図である。
【図２】素数生成のためのシード値を生成および記憶するための方法の流れ図の第2の例を示す図である。
【図３】素数生成のためのシード値を生成および記憶するための方法のフローチャートの第1の例を示す図である。
【図４】素数生成のためのシード値を生成および記憶するための方法の流れ図の第3の例を示す図である。
【図５】素数生成のためのシード値を生成および記憶するための方法の流れ図の第4の例を示す図である。
【図６】素数生成のためのシード値を生成および記憶するための方法のフローチャートの第2の例を示す図である。
【図７Ａ】素数生成のためのシード値を生成および記憶するための方法の流れ図の第5の例を示す図である。
【図７Ｂ】素数生成のためのシード値を生成および記憶するための方法の流れ図の第5の例を示す図である。
【図８Ａ】素数生成のためのシード値を生成および記憶するための方法の流れ図800を示す図である。
【図８Ｂ】素数生成のためのシード値を生成および記憶するための方法の流れ図800を示す図である。
【図９】素数生成のためのシード値を生成および記憶するための方法のフローチャート900を示す図である。
【図１０】本明細書で説明される暗号セキュリティのための方法のいずれかを実行する電子デバイス1000についての、ハードウェア実施態様の例示的な概略ブロック図を示す図である。
【図１１】処理回路の概略ブロック図である。
【図１２】処理回路の概略ブロック図である。
【発明を実施するための形態】
【００１８】
以下の説明では、本開示の様々な態様の完全な理解をもたらすために具体的な詳細が与えられる。しかしながら、態様は、これらの特定の詳細なしで実施され得ることは、当業者によって理解されるであろう。たとえば、態様が不要な詳細で不明瞭になることを回避するために、回路はブロック図で示されることがある。他の場合には、本開示の態様を不明瞭にしないために、よく知られている回路、構造、および技法は、詳細に示されない場合がある。
【００１９】
「例示的」という言葉は、「例、事例、または例示として機能すること」を意味するように本明細書で使用される。「例示的」として本明細書で説明するいかなる実装形態または態様も、必ずしも本開示の他の態様よりも好ましいまたは有利なものと解釈されるべきでない。同様に、「態様」という用語は、本開示のすべての態様が、説明された特徴、利点、または動作モードを含むことを必要としない。本明細書において、「素数性テスト」および「合成数テスト」は、互換的に使用されることがあり、概して、「素数性テスト」と呼ばれる。たとえば、Miller-Rabinテストなどのテストは、数が合成数であることを立証し得る。そうすることによって、テストは数が素数でないことも立証する。したがって、本明細書において、数に対して素数性テストを実行することは、数が合成数であることを立証する、または立証しようと試みるテストを含む。本明細書において、「乱数」は、真にランダム(たとえば、それは真の乱数生成器(RNG)によって生成された)であってよく、または、擬似ランダム(たとえば、それは擬似乱数生成器(PRNG)を使用して生成された)であってもよい。
【００２０】
概要
素数を生成するために使用されるシード値などの値を記憶するために必要とされるメモリ回路の記憶空間の量を低減する方法およびデバイスが本明細書で説明され、素数は、セキュリティアルゴリズムのための暗号鍵を生成するために使用され得る。詳細には、1つまたは複数の比較的小さいビット数のシード値が、比較的大きいビット数の素数の代わりに事前計算および記憶される。シード値は、後の時点において、要求に応じて素数を生成するために使用され得る。そのような方法およびデバイスは、記憶空間が限られている暗号アクセラレータハードウェアモジュールを有するモバイルデバイスにとって特に有用である。他のデバイスも、暗号鍵のプロビジョニングコストを下げるために、本明細書で説明される方法および装置から恩恵を受けることができる。
【００２１】
素数生成のために使用されるシード値の生成および記憶のための例示的な方法
図1は、一態様による素数生成のためのシード値を生成および記憶するための方法の流れ図100を示す。最初に、kビット乱数シードSが生成される102。乱数シードSは、たとえば、乱数生成器または擬似乱数生成器を使用して生成され得る。値kは、2以上の任意の整数であり得る。乱数シードSは、次いで、nビット乱数Rを生成するために使用され得、ここでn>kである104。詳細には、一方向関数fが、乱数シードSに基づいて乱数Rを生成するために、式(1)に従って実行され得る。
R=f(S) (1)
一例によれば、関数fは、セキュアハッシュ関数(たとえば、SHA-1、SHA-2など)などの暗号のハッシュ関数、または秘密鍵を用いる高度暗号化標準(AES)などのブロック暗号であってもよい。
【００２２】
次に、素数性テストが、乱数Rが素数であるかどうかを決定するために実行される106。ほんの一例として、実行される素数性テストは、Miller-Rabin素数性テストを含み得る。乱数Rが素数であると決定される場合、乱数シードSはメモリに記憶される108。さもなければ、方法ステップ102、104、106が繰り返され、それにより、新しい乱数シードSが生成され102、新しい乱数Rが乱数シードSに基づいて(たとえば、関数fを使用して)生成され104、新たに生成された乱数Rが素数であるかどうかを決定するために素数性テストが実行される106。これらのステップ102、104、106は、乱数Rが素数であると決定されるまで継続的に繰り返され、その後、乱数Rを生成した乱数シードSは記憶される108。一例によれば、乱数シードSの後続の繰返しは、以前に生成され素数でないと決定された乱数Rのkビットを使用し得る。たとえば、乱数シードSの後続の繰返しは、前の繰返しからの乱数Rの最初のkビットに等しくてもよい。
【００２３】
乱数シードSのビット数kが素数性乱数(prime random number)Rのビット数nよりも小さいので、メモリ空間は、乱数Rの代わりにシードSを記憶することによって節約され、それらのうちの前者は廃棄/消去されてもよい。後で、乱数シードSは、一方向関数fを使用して素数性乱数Rを再生成するために取り出され(たとえば、それが記憶されているメモリ回路から)、使用され得る。たとえば、鍵生成プロセスは、上述された方法100を使用して供給され得る1つまたは複数の素数を要求し得る。ほんの一例によれば、それによって生成された鍵は、RSAなどの暗号セキュリティアルゴリズムによって使用され得る。
【００２４】
したがって、図1に示す方法によれば、素数の乱数Rが生成され得、次いで、RSAなどの鍵生成アルゴリズムとともに使用されて暗号セキュリティ鍵を生成する。素数性乱数Rを生成するための知られている乱数シードSが、素数を得るための要求を暗号セキュリティアルゴリズム(たとえば、鍵を生成するための素数を要求するRSAアルゴリズム)から受信する前に生成および記憶されるという点において、図1に示す方法は「オフライン」で実行され得る。
【００２５】
図2は、一態様による素数生成のためのシード値を生成および記憶するための方法の流れ図200を示す。最初に、kビット乱数シードSが処理回路202(たとえば、プロセッサ)において生成される208。(一態様によれば、処理回路202によって実行されるステップが、ソフトウェアに実装され得ることに留意されたい。)次いで、nビット乱数Rが、シードSに基づいて(たとえば、図1に関して上述された関数fを使用して)生成される210。次に、生成された乱数Rが素数であるかどうかが決定される212。ステップ208、210、212は、少なくとも1つの乱数Rが素数であると決定されるまで繰り返される214。次いで、乱数Rが素数であると決定されると、素数性乱数Rを生成するために使用されたシードSは、メモリ回路204(たとえば、メモリ)に記憶される216。シードSが記憶されたので、素数性乱数Rはこの時点で廃棄または消去されてよい。次に、1つまたは複数の素数を得るための要求が、暗号セキュリティアルゴリズム(たとえば、RSA)を実施するアプリケーション206から受信される218。要求に応答して、シードSがメモリから取り出され220、nビット素数性乱数RがシードSを使用して再生成される222。最後に、素数性乱数Rは、鍵生成のための素数を要求しているアプリケーションに送信/供給される224。
【００２６】
図3は、一態様による素数生成のためのシード値を生成および記憶するための方法のフローチャート300を示す。最初に、生成される乱数Rが素数であると決定されるまで、kビットを有する乱数シードSを生成することと304、nビットを有する乱数RをシードSに基づいて生成することであって、kがnよりも小さい、生成することと306、乱数Rが素数であるかどうかを決定することとを308、繰り返し行うことによって302、ランダムな素数が生成される。次に、素数であると決定された乱数Rを生成するために使用された乱数シードSが記憶される310。
【００２７】
図4は、一態様による素数生成のためのシード値を生成および記憶するための方法の流れ図400を示す。最初に、kビット乱数シードSが生成される402。乱数シードSは、たとえば、乱数生成器または擬似乱数生成器を使用して生成され得る。値kは、2以上の任意の整数であり得る。次いで、秘密鍵kSと一緒の乱数シードSは、nビット乱数Rを生成するために使用され得、ここでn>kである404。詳細には、一方向関数fが、乱数シードSおよび秘密鍵kSに基づいて乱数Rを生成するために、式(2)に従って実行され得る。
R=f(S,kS) (2)
一例では、秘密鍵kSは、方法400を実行する装置だけに知られていてよい。一態様によれば、秘密鍵kSは、方法400を実行する装置において、セキュアメモリ(たとえば、暗号化されてもされなくてもよい読取り専用メモリ、ワンタイムプログラマブル(OTP)メモリ)から取り出され得る。そのような場合には、秘密鍵kSは、鍵kSの無許可のアクセス/発見を防止するために、前もってセキュアメモリに記憶されてもよい。別の態様によれば、秘密鍵kSは、必ずしも装置においてセキュアメモリに記憶されなくてもよく、代わりに装置においてオンザフライで生成される。
【００２８】
一例によれば、一方向関数fは、ハッシュベースのメッセージ認証コード(HMAC)などの暗号メッセージ認証コード(MAC)、または高度暗号化標準(AES)などのブロック暗号であり得る。両方の場合において、MACまたはブロック暗号は秘密鍵kSを使用する。
【００２９】
次に、素数性テストが、乱数Rが素数であるかどうかを決定するために実行される406。乱数Rが素数であると決定される場合、乱数シードSはメモリに記憶される408。随意に、秘密鍵kSがセキュアメモリにまだ記憶されていない(たとえば、それは上述されたように生成される)場合には、乱数Rが素数であると決定された後、秘密鍵kSは、次いで、メモリに記憶される。乱数Rが素数でないと決定される場合、方法ステップ402、404、406が繰り返され、それにより、新しい乱数シードSが生成され402、新しい乱数Rが乱数シードSおよび秘密鍵kSに基づいて(たとえば、関数fを使用して)生成され404、新たに生成された乱数Rが素数であるかどうかを決定するために素数性テストが実行される406。これらのステップ402、404、406は、乱数Rが素数であると決定されるまで継続的に繰り返され、その後、乱数Rを生成した乱数シードSおよび秘密鍵kSは記憶される408。一例によれば、秘密鍵kSはセキュアに(たとえば、暗号化されるOTPメモリに)記憶され、別の例によれば、標準的なメモリ(たとえば、通常のランダムアクセスメモリ(RAM))に記憶される。
【００３０】
乱数シードSおよび秘密鍵kSは、関数fを使用して素数性乱数Rを再生成するために、将来の時点において後で取り出され使用され得る。たとえば、鍵生成プロセスは、上述された方法400を使用して供給され得る1つまたは複数の素数を要求し得る。ほんの一例によれば、それによって生成された鍵は、RSAなどの暗号セキュリティアルゴリズムによって使用され得る。
【００３１】
したがって、図4に示す方法によれば、素数の乱数Rが生成され得、それはRSAなどの暗号セキュリティアルゴリズムのための暗号セキュリティ鍵を生成するために使用される。素数性乱数Rを生成するための知られている乱数シードSおよび秘密鍵kSが、素数を得るための要求を鍵生成プロセスから受信する前に生成および記憶されるという点において、図4に示す方法は「オフライン」で実行され得る。
【００３２】
図5は、一態様による素数生成のためのシード値を生成および記憶するための方法の流れ図500を示す。最初に、kビット乱数シードSが処理回路502(たとえば、プロセッサ)において生成される508。(一態様によれば、処理回路502によって実行されるステップが、ソフトウェアに実装され得ることに留意されたい。)次いで、秘密鍵kSは、生成されるかまたはメモリ回路504(たとえば、メモリ)のセキュアメモリから取り出され509、nビット乱数Rが、シードSおよび秘密鍵kSに基づいて(たとえば、図4に関して上述された関数fを使用して)生成される510。次に、生成された乱数Rが素数であるかどうかが決定される512。ステップ508、509、510、512は、少なくとも1つの乱数Rが素数であると決定されるまで繰り返される514。次いで、乱数Rが素数であると決定されると、素数性乱数Rを生成するために使用されるシードSは、メモリ回路(たとえば、RAMなどの標準的なメモリ)に記憶される516。シードSが記憶されたので、素数性乱数Rはこの時点で廃棄または消去されてよい。次に、1つまたは複数の素数を得るための要求が、暗号鍵生成関数/プロセスを実施するアプリケーション506から受信される518。要求に応答して、シードSおよび秘密鍵kSがメモリ520から取り出され(たとえば、シードSはRAMなどの標準的なメモリから取り出され、秘密鍵kSはセキュアメモリから取り出される)、nビット素数性乱数RはシードSおよび秘密鍵kSを使用して再生成される522。最後に、素数性乱数Rは、鍵生成のための素数を要求しているアプリケーションに送信/供給される524。
【００３３】
図6は、一態様による素数生成のためのシード値を生成および記憶するための方法のフローチャート600を示す。最初に、生成される乱数Rが素数であると決定されるまで、kビットを有する乱数シードSを生成することと604、nビットを有する乱数RをシードSおよび秘密鍵kSに基づいて生成することであって、kがnよりも小さい、生成することと606、乱数Rが素数であるかどうかを決定することとを608、繰り返し行うことによって602、ランダムな素数が生成される。次に、素数であると決定された乱数Rを生成するために使用された乱数シードSおよび秘密鍵kSが記憶される610。乱数シードSはRAMなどの標準的なメモリに記憶されてよく、秘密鍵kSはOTPメモリなどのセキュアメモリに記憶されてもよい。
【００３４】
図7Aおよび図7Bは、一態様による素数生成のためのシード値を生成および記憶するための方法の流れ図700を示す。図7Aを参照すると、最初に、kビット乱数シードSおよび複数のgビット追加シードTiが生成され、ここで、整数i={1,2,...m}かつm>1である702。乱数シードSおよび複数の追加シードTiは、たとえば、乱数生成器または擬似乱数生成器を使用して生成され得る。値kは2以上の任意の整数であり得、値gは1以上の任意の整数であり得る。一態様によれば、gビット追加シードTiはそれぞれ、kビット乱数シードSよりも少ないビットを有する(すなわち、g<k)。
【００３５】
次に、複数の第2シードSiが、乱数シードSおよび複数の追加シードTiに基づいて生成される。たとえば、複数の第2シードSiは、乱数シードSを複数の追加シードTiの各々と連結することによって生成され得る704。第2シードSiの生成は、乱数シードSの複数の追加シードTiとの連結に限定されないことに留意されたい。任意の論理演算が、乱数シードSおよび複数の追加シードTiに基づいて第2シードSiを生成するために実行され得る。
【００３６】
次いで、複数のnビット乱数Riが、第2シードSiに基づいて生成され、ここで、n>k+gである706。一態様によれば、一方向関数fが、第2シードSiに基づいて乱数Riを生成するために、式(3)に従って実行され得る。
整数値i≧1について、Ri=f(Si) (3)
【００３７】
別の態様によれば、一方向関数fは、第2シードSiおよび秘密鍵kS708に基づいて乱数Riを生成するために、式(4)に従って実行され得る。
整数値i≧1について、Ri=f(Si,kS) (4)
一例では、秘密鍵kSは、方法700を実行する装置だけに知られていてよい。一態様によれば、秘密鍵kSは、方法700を実行する装置において、セキュアメモリ(たとえば、暗号化されてもされなくてもよい読取り専用メモリ、ワンタイムプログラマブルメモリ)から取り出され得る。
【００３８】
次に、素数性テストが、乱数のいずれかが素数であるかどうかを決定するために、乱数Riの各々に対して実行される710。乱数Riのいずれかが素数であると決定される場合、素数であると決定された1つまたは複数の乱数Riを生成するために使用された乱数シードSおよび1つまたは複数の追加シードTiが、メモリに記憶される712。随意に、秘密鍵kSが一方向関数fによって使用された場合、秘密鍵kSは、セキュアメモリに記憶される714。乱数Riのいずれも素数でない場合、ステップ702、704、706、710は、少なくとも1つの乱数Riが素数であると決定されるまで繰り返される。
【００３９】
図7Bを参照すると、少なくとも1つの乱数Riが素数であると決定されたがすべての乱数Riが素数であるとは限らないと決定された後、1つまたは複数のgビット追加シードTiは、Riが素数でないと決定されたすべてのiについて再生成される716。次に、1つまたは複数の第2シードSiが、Riが素数でないと決定されたすべてのiについて、乱数シードSおよび再生成された追加シードTiに基づいて再生成される718。たとえば、第2シードSiは、シードSを追加シードTiと連結することによって生成され得る。次いで、1つまたは複数の乱数Riが、Riが素数でないと決定されたすべてのiについて、第2シードSiに基づいて一方向関数fを使用して再生成される720。一例によれば、一方向関数fは、秘密鍵kSを入力として受信し得る(たとえば、ステップ708参照)。
【００４０】
次に、素数性テストが、再生成された乱数Riに対して実行される722。所与の乱数Riが素数であると決定される場合、それの対応する、乱数Riを再生成するために部分的に使用された追加シードTiが記憶される724。さもなければ、乱数Riが素数でないと決定される場合、処理ステップ716、718、720、および722は、再生成されたすべての乱数Riが素数となるまで繰り返され、したがって、それらの乱数Riを生成するために使用される対応する追加シードTiも記憶される724。一態様によれば、ステップ716、718、720、722は、しきい値数の繰返しの後、乱数シードSを含む数空間の中に残されている素数がない場合には、繰り返して実行されることをやめてよい。
【００４１】
図7Aおよび図7Bに示す方法700をより良く示すための一例が以下に提供される。最初に、所与の鍵生成プロセスによって20個の素数が望まれていると仮定する。次いで、単一のkビット乱数シードSおよび20個のgビットランダム追加シードT1、T2、...T20が生成される702。次に、20個の第2シードS1、S2、...S20が追加シードT1、T2、...T20に基づいて生成され704、順に20個の乱数R1、R2、...R20が第2シードS1、S2、...S20に基づいて関数fを使用して生成される706。次いで、乱数R2、R7、およびR17が素数であると決定され、残りの乱数R1、R3...R6、R8...R16、R18、R19、R20が素数でないと決定されると仮定する710。したがって、乱数シードSおよび追加シードT2、T7、およびT17は、メモリ(たとえば、標準的なメモリRAM)に記憶される712。
【００４２】
次に、乱数R1、R3...R6、R8...R16、R18、R19、R20が素数でないと決定されたので、追加シードT1、T3...T6、T8...T16、T18、T19、T20は再生成される(たとえば、ランダムな新しい値)716。次いで、新しい第2シードS1、S3...S6、S8...S16、S18、S19、S20が、新たに再生成された追加シードT1、T3...T6、T8...T16、T18、T19、T20に基づいて再生成され718、順に新しい乱数R1、R3...R6、R8...R16、R18、R19、R20が、新たに再生成された第2シードS1、S3...S6、S8...S16、S18、S19、S20に基づいて再生成される720。次に、素数性テストが、それらが素数であるかを決定するために、新たに再生成された乱数R1、R3...R6、R8...R16、R18、R19、R20に対して再び実行される722。今回は、乱数R1、R6、R16、およびR18が今や素数であると決定されると仮定し、したがって、対応する追加シードT1、T6、T16、およびT18はメモリに保存される724。次いで、すべての20個の乱数R1、R2、...R20が素数であると決定されるまで、ステップ716、718、720、722が、依然として素数でない残りの乱数について再び繰り返される。
【００４３】
乱数シードSのビット数k+追加シードTiのビット数gが素数性乱数Riのビット数nよりも小さいので、メモリ空間は、乱数Riの代わりにシードSおよび追加シードTiを記憶することによって節約され、それらのうちの前者は廃棄/消去されてよい。後で、乱数シードSおよび追加シードTiは、一方向関数fを使用して素数性乱数Riを再生成するために、メモリから取り出され使用され得る。秘密鍵kSも素数性乱数Riを生成するために関数fによって使用された場合では、秘密鍵kSも、関数fを使用して素数性乱数Riを再生成するために、セキュアメモリから(追加シードTiおよび乱数シードSに加えて)取り出され使用される。
【００４４】
したがって、図7Aおよび図7Bに示す方法によれば、複数の素数の乱数Riが生成され得、次いで、複数の暗号セキュリティ鍵を生成するために、RSAなどの暗号セキュリティアルゴリズムとともに使用され得る。乱数シードSおよび複数の追加シードTi-素数性乱数Riを生成するために知られている/立証されている-が、1つまたは複数の素数を得るための要求を鍵生成関数から受信する前に生成および記憶されるという点において、図7Aおよび図7Bに示す方法は「オフライン」で実行され得る。
【００４５】
図8Aおよび図8Bは、一態様による素数生成のためのシード値を生成および記憶するための方法の流れ図800を示す。図8Aを参照すると、最初に、kビット乱数シードSおよび複数のgビット追加シードTiが処理回路802(たとえば、プロセッサ)において生成され、ここで、整数i={1,2,...m}かつm>1である808。(一態様によれば、処理回路802によって実行されるステップが、ソフトウェアに実装され得ることに留意されたい。)次いで、複数の(k+g)ビット第2シードSiが、シードSおよび複数の追加シードTiに基づいて(たとえば、シードSを複数の追加シードTiと連結すること)生成される810。次に、複数のnビット乱数Riが、第2シードSiに基づいて(たとえば、図7Aおよび図7Bに関して上述された一方向関数fを使用して)生成され、ここで、n>g+kである812。次いで、生成された乱数Riのいずれかが素数であるかどうかが決定される814。ステップ808、810、812、814は、少なくとも1つの乱数Riが素数であると決定されるまで繰り返される。少なくとも1つまたは複数の乱数Riが素数であると決定されると仮定すると、素数性乱数Riを生成するために使用されるシードSおよび追加シードTiがメモリ回路804(たとえば、メモリ)に記憶される816。
【００４６】
次に、素数でないと決定された乱数Riに関連付けられた追加シードTiが再生成される818。次いで、新しい第2シードSiが、再生成された追加シードTiに基づいて再生成され820、順に新しい乱数Riが、再生成された第2シードSiに基づいて再生成される822。次に、素数性テストが、それらが素数であるかを決定するために、再生成された乱数Riに対して実行される824。素数であると決定された乱数Riに関連付けられた追加シードTiは、メモリ回路804に記憶される826。図8Bを参照すると、処理ステップ818、820、822、824、826は、すべての再生成された乱数Riが素数であると決定されるまで繰り返され828、したがって、それらの関連付けられた追加シードTiもメモリ回路804に記憶される。シードSおよび関連付けられた追加シードTiが記憶され素数Riを再生成するために使用され得るので、素数であると決定された乱数Riは、この時点で廃棄または消去されてよい。
【００４７】
次に、1つまたは複数の素数を得るための要求が、暗号鍵生成関数を実施するアプリケーション806から受信される830。要求に応答して、シードSおよび追加シードTiがメモリ804から取り出され832、nビット素数性乱数RiがシードSおよび追加シードTiを使用して再生成される834。秘密鍵kSが、第2シードSiに基づいて乱数Riを生成した一方向関数fによって使用された場合、秘密鍵kSも素数性乱数Riを再生成するためにメモリ(たとえば、セキュアメモリ)から取り出される。最後に、素数性乱数Riが、鍵生成のための素数を要求しているアプリケーション806に送信/供給される836。
【００４８】
図9は、一態様による素数生成のためのシード値を生成および記憶するための方法のフローチャート900を示す。最初に、kビットを有する乱数シードSおよびそれぞれgビットを有する複数の追加シードTiが生成される902。次に、複数の追加シードTiのうちの相異なる追加シードおよび乱数シードSにそれぞれ基づく複数の第2シードSiが生成される904。次いで、nがk+gよりも小さい場合にそれぞれnビットを有する複数の乱数Riが生成され、複数の乱数Riの各々は、複数の第2シードSiのうちの相異なる第2シードに基づく906。次に、複数の乱数Riのうちの少なくとも1つの乱数RPが素数であると決定され、その場合、乱数RPは複数の第2シードSiのうちの第2シードSPに基づき、第2シードSPは複数の追加シードTiのうちの追加シードTPおよび乱数シードSに基づく908。次いで、乱数シードSおよび追加シードTPは、メモリ回路910に記憶される。
【００４９】
本開示の一態様によれば、メモリ回路からの記憶されている乱数シードSおよび追加シードTPは取り出され得、素数性乱数RPは、乱数シードSおよび追加シードTPに基づいて再生成され得る。別の態様によれば、乱数シードSおよび追加シードTPは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶され得る。次いで、1つまたは複数の素数を得るための暗号鍵生成プロセスからの要求が受信され得る。それに応答して、暗号鍵が、素数性乱数RPに基づいて生成され得る。暗号鍵は、次いで、暗号鍵生成プロセスに供給され得る。
【００５０】
一態様によれば、複数の第2シードSiのうちの相異なる第2シードに基づいて複数の乱数Riを生成することは、複数の第2シードSiの各々を入力として受信するとともに複数の乱数Riを出力として生成する一方向関数fを実行することを含み得、一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである。別の態様によれば、複数の乱数Riのうちの少なくとも1つの乱数が素数でないことが決定され得る。次いで、gビットを有する別の追加シードT2が生成され得、追加シードT2および乱数シードSに基づく別の第2シードS2が生成され得、nビットを有する別の乱数R2が第2シードS2に基づいて生成され得る。次に、乱数R2が素数であると決定され得、したがって、追加シードT2はメモリ回路に記憶され得る。
【００５１】
一態様によれば、記憶された乱数シードSおよび追加シードT2は、メモリ回路から取り出され得、素数性乱数R2は、乱数シードSおよび追加シードT2に基づいて再生成され得る。別の態様によれば、所定の数の素数を得るための要求が受信されてもよい。それに応答して、以下のステップ、すなわち、別の追加シードT2を生成すること、追加シードT2および乱数シードSに基づいて別の第2シードS2を生成すること、nビットを有する別の乱数R2を第2シードS2に基づいて生成すること、乱数R2が素数であることを決定すること、および追加シードT2をメモリ回路に記憶することが、異なる素数にそれぞれ関連付けられたいくつかの追加シードが記憶され所定の数に等しくなるまで繰り返され得る。
【００５２】
例示的な電子デバイス
図10は、本明細書で説明される暗号セキュリティのための方法のいずれかを実行する、電子デバイス1000のハードウェア実装形態の例示的な概略ブロック図を示す。電子デバイス1000は、携帯電話、スマートフォン、タブレット、ポータブルコンピュータ、および/または、回路を有する任意の他の電子デバイスであり得る。電子デバイス1000は、通信インターフェース1010、ユーザインターフェース1012、および処理システム1014を含み得る。処理システム1014は、処理回路(たとえば、プロセッサ)1004、メモリ回路(たとえば、メモリ)1005、コンピュータ可読記憶媒体1006、バスインターフェース1008、およびバス1002を含み得る。処理システム1014および/または処理回路1004は、図1、図2、図3、図4、図5、図6、図7A、図7B、図8A、図8B、および/または図9に関して説明されたステップ、機能、および/または処理のいずれかを実行するように構成され得る。
【００５３】
処理回路1004は、電子デバイス1000のためのデータを処理するように適合される1つまたは複数のプロセッサ(たとえば、第1のプロセッサなど)であり得る。たとえば、処理回路1004は、図1、図2、図3、図4、図5、図6、図7A、図7B、図8A、図8B、および/または図9で説明されるステップのうちのいずれか1つを実行するための手段として機能する特定用途向け集積回路(ASIC)のような、特別なプロセッサであり得る。
【００５４】
処理回路1004の例は、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ(DSP)、フィールドプログラマブルゲートアレイ(FPGA)、プログラマブル論理デバイス(PLD)、状態機械、ゲート論理、個別のハードウェア回路、および本開示の全体にわたって説明される様々な機能を実行するように構成された他の適切なハードウェアを含む。処理回路1004はまた、バス1002を管理し、コンピュータ可読記憶媒体1006および/またはメモリ1005に記憶されたソフトウェアを実行することを担う。ソフトウェアは、処理回路1004によって実行されると、処理システム1014に、図1、図2、図3、図4、図5、図6、図7A、図7B、図8A、図8B、および/または図9に関して上で説明された様々な機能、ステップ、および/または処理を実行させる。コンピュータ可読記憶媒体1006は、ソフトウェアを実行するときに処理回路1004によって操作されるデータを記憶するために使用され得る。
【００５５】
メモリ回路1005は、限定はされないが、フラッシュメモリ、磁気的または光学的なハードディスクドライブなどのような、非揮発性メモリであり得る。いくつかの態様では、セクタ情報および/またはオーバーヘッドメッセージ(構成シーケンス番号を含む)を記憶するメモリは、永続的に情報を記憶するために継続的に電力供給され得る、DRAM(たとえば、DDR SDRAM)、SRAMなどのような、揮発性メモリであり得る。メモリ回路1005は、乱数シードSを記憶するための手段、追加シードTiを記憶するための手段、およびセキュアなときに秘密鍵kSを記憶するための手段の一例として働く。
【００５６】
ソフトウェアは、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語と呼ばれるか、または他の名称で呼ばれるかどうかにかかわらず、命令、命令セット、コード、コードセグメント、プログラムコード、プログラム、サブプログラム、ソフトウェアモジュール、アプリケーション、ソフトウェアアプリケーション、ソフトウェアパッケージ、ルーチン、サブルーチン、オブジェクト、実行可能ファイル、実行スレッド、プロシージャ、機能などを意味するように広く解釈されなければならない。ソフトウェアはコンピュータ可読記憶媒体1006上に存在し得る。コンピュータ可読記憶媒体1006は、非一時的コンピュータ可読記憶媒体であってよい。非一時的なコンピュータ可読記憶媒体は、例として、磁気記憶デバイス(たとえば、ハードディスク、フロッピー(登録商標)ディスク、磁気ストリップ)、光ディスク(たとえば、コンパクトディスク(CD)、またはデジタル多用途ディスク(DVD))、スマートカード、フラッシュメモリデバイス(たとえば、カード、スティック、またはキードライブ)、ランダムアクセスメモリ(RAM)、リードオンリメモリ(ROM)、プログラマブルROM(PROM)、消去可能なPROM(EPROM)、電気的消去可能PROM(EEPROM)、レジスタ、リムーバブルディスク、およびコンピュータによってアクセスおよび読み出し可能なソフトウェアおよび/または命令を記憶するための任意の他の適切な媒体を含む。また、コンピュータ可読記憶媒体は、例として、搬送波、伝送路、ならびに、コンピュータによりアクセスされ読み取られ得るソフトウェアおよび/または命令を送信するための任意の他の適切な媒体も含み得る。コンピュータ可読記憶媒体1006は、処理システム1014の中に存在してもよく、処理システム1014の外に存在してもよく、または処理システム1014を含む複数のエンティティにわたって分散されてもよい。コンピュータ可読記憶媒体1006は、コンピュータプログラム製品において具現化され得る。
【００５７】
この例において、処理システム1014は、バス1002によって全般に表されるバスアーキテクチャを用いて実現され得る。バス1002は、処理システム1014の特定の用途と全体的な設計制約とに応じて、任意の数の相互接続バスとブリッジとを含むことができる。バス1002は、(プロセッサ1004によって全般に表される)1つまたは複数のプロセッサ、メモリ1005、および(コンピュータ可読記憶媒体1006によって全般に表される)コンピュータ可読媒体を含む、様々な回路を互いにつなぐ。バス1002は、タイミングソース、周辺機器、電圧調整器、および電力管理回路などの様々な他の回路をつなぐこともできるが、これらの回路は当技術分野でよく知られており、したがってこれ以上は説明されない。バスインターフェース1008は、バス1002と通信インターフェース1010(もしあれば)との間のインターフェースを与える。通信インターフェース1010は、伝送媒体を通じて他の装置と通信するための手段を提供する。装置の性質に応じて、ユーザインターフェース1012(たとえば、キーパッド、ディスプレイ、スピーカー、マイクロフォン、タッチスクリーンディスプレイなど)も電子デバイス1000のために設けられ得る。
【００５８】
図11は、一態様による処理回路1004の概略ブロック図を示す。処理回路1004は、素数生成器回路1102、乱数シードS取出し器回路1103、素数再生成器回路1105、および関数f実行回路1107を含み得る。素数生成器回路1102は、乱数シードS生成器回路1104、乱数R生成器回路1106、および素数性テスト回路1108を含み得る。
【００５９】
素数生成器回路1102は、kビットを有する乱数シードSを生成することと、nビットを有する乱数RをシードSに基づいて生成することと、乱数Rが素数であるかどうかを決定することとを、繰り返し行うことによって、素数を生成するための手段の一例として働く。詳細には、乱数シードS生成器回路1104は乱数シードSを生成するための手段の一例として働き、乱数R生成器回路1106はnビットを有する乱数RをシードSに基づいて生成するための手段の一例として働き、素数性テスト回路1108は乱数Rが素数であるかどうかを決定するための手段の一例として働く。
【００６０】
乱数シードS取出し器回路1103は、乱数シードSをメモリ回路1005から取り出すための手段の一例として働く。素数再生成器回路1105は、乱数シードSに基づいて素数を再生成するための手段の一例として働く。関数f実行回路1107は、シードSを入力として受信するとともに乱数Rを出力として生成する一方向関数fを実行するための手段の一例として働く。
【００６１】
図12は、一態様による処理回路1004の概略ブロック図を示す。処理回路1004は、シードSおよび追加シードTi生成器回路1202、第2シードSi生成器回路1204、乱数Ri生成器回路1206、素数性テスト回路1208、シード取出し回路1210、および素数性乱数再生成器回路1212を含み得る。
【００６２】
シードSおよび追加シードTi生成器回路1202は、乱数シードSおよび追加シードTiを生成するための手段の一例として働く。第2シードSi生成器回路1204は、複数の追加シードTiのうちの相異なる追加シードおよび乱数シードSにそれぞれ基づく第2シードSiを生成するための手段の一例として働く。乱数Ri生成器回路1206は、複数の第2シードSiのうちの相異なる第2シードにそれぞれ基づく、それぞれnビットを有する複数の乱数Riを生成するための手段の一例として働く。素数性テスト回路1208は、乱数RPが素数であるかどうかを決定するための手段の一例として働く。シード取出し回路1210は、乱数シードSおよび複数の追加シードTi(たとえば、シードTP)を取り出すための手段の一例として働く。素数性乱数再生成器回路1212は、乱数シードSおよび追加シードTi(たとえば、追加シードTP)に基づいて、素数性乱数(たとえば、素数性乱数RP)を再生成するための手段の一例として働く。
【００６３】
本明細書で説明される方法およびデバイスは、暗号セキュリティおよび/または暗号鍵生成に限定されない任意の使用のために、素数生成のためのシード値を生成および記憶するために使用され得る。
【００６４】
図1、図2、図3、図4、図5、図6、図7A、図7B、図8A、図8B、図9、図10、図11、および/または図12に示された構成要素、ステップ、特徴、および/または機能のうちの1つまたは複数は、単一の構成要素、ステップ、特徴または機能に再構成され、かつ/もしくは組み合わされ、または、いくつかの構成要素、ステップ、または機能で具現化することができる。さらなる要素、構成要素、ステップ、および/または機能も、本発明から逸脱することなく追加され得る。図10、図11、および/または図12に示す装置、デバイス、および/または構成要素は、図1、図2、図3、図4、図5、図6、図7A、図7B、図8A、図8B、および/または図9に記載した方法、特徴、またはステップのうちの1つまたは複数を実行するように構成され得る。また、本明細書で説明されたアルゴリズムは、効率的にソフトウェアに実装されてもよく、かつ/またはハードウェアに組み込まれてもよい。
【００６５】
その上、本開示の一態様では、図10、図11、および/または図12に示す処理回路1004は、図1、図2、図3、図4、図5、図6、図7A、図7B、図8A、図8B、および/または図9で説明したアルゴリズム、方法、および/またはステップを実行するように特別に設計かつ/または配線接続される専用プロセッサ(たとえば、特定用途向け集積回路(たとえば、ASIC))であり得る。したがって、そのような専用プロセッサ(たとえば、ASIC)は、図1、図2、図3、図4、図5、図6、図7A、図7B、図8A、図8B、および/または図9で説明したアルゴリズム、方法、および/またはステップを実行するための手段の一例であり得る。コンピュータ可読記憶媒体1006はまた、専用プロセッサ(たとえば、ASIC)によって実行されると、図1、図2、図3、図4、図5、図6、図7A、図7B、図8A、図8B、および/または図9で説明されるアルゴリズム、方法、および/またはステップを専用プロセッサに実行させる、プロセッサ1004が可読の命令を記憶することができる。
【００６６】
また、本開示の態様は、フローチャート、流れ図、構造図またはブロック図として示されるプロセスとして説明され得ることに留意されたい。フローチャートは動作を逐次プロセスとして説明する場合があるが、動作の多くは並行してまたは同時に実行され得る。加えて、動作の順序は並び替えられ得る。プロセスは、その動作が完了したとき、終了する。プロセスは、メソッド、関数、プロシージャ、サブルーチン、サブプログラムなどに対応する場合がある。プロセスが関数に対応する場合、プロセスの終了は、呼出し関数またはmain関数への関数の復帰に対応する。
【００６７】
その上、記憶媒体は、読取り専用メモリ(ROM)、ランダムアクセスメモリ(RAM)、磁気ディスク記憶媒体、光学記憶媒体、フラッシュメモリデバイスおよび/もしくは他の機械可読媒体、およびプロセッサ可読媒体、ならびに/または情報を記憶するためのコンピュータ可読媒体を含む、データを記憶するための1つもしくは複数のデバイスを表し得る。「機械可読媒体」、「コンピュータ可読媒体」、および/または「プロセッサ可読媒体」という用語は、ポータブルもしくは固定ストレージデバイス、光ストレージデバイス、ならびに、命令および/またはデータを記憶、格納または搬送することが可能な様々な他の媒体のような非一時的媒体を含み得るが、これらに限定されない。したがって、本明細書で説明される様々な方法は、「機械可読媒体」、「コンピュータ可読媒体」および/または「プロセッサ可読媒体」に記憶され、1つもしくは複数のプロセッサ、機械および/またはデバイスによって実行され得る命令および/またはデータによって、完全にまたは部分的に実装され得る。
【００６８】
さらに、本開示の態様は、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、またはそれらの任意の組合せによって実装され得る。ソフトウェア、ファームウェア、ミドルウェアまたはマイクロコードで実装されるとき、必要なタスクを実行するプログラムコードまたはコードセグメントは、記憶媒体または他のストレージのような機械可読媒体に記憶され得る。プロセッサは、必要なタスクを実行することができる。コードセグメントは、プロシージャ、関数、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェアパッケージ、クラス、あるいは命令、データ構造、またはプログラムステートメントの任意の組合せを表すことができる。コードセグメントは、情報、データ、引数、パラメータ、またはメモリ内容を渡す、および/または受信することによって、別のコードセグメントまたはハードウェア回路に結合され得る。情報、引数、パラメータ、データなどは、メモリ共有、メッセージパッシング、トークンパッシング、ネットワーク伝送などを含む任意の適切な手段を介して渡されてもよく、転送、送信されてもよい。
【００６９】
本明細書で開示される例に関して説明される様々な例示的な論理ブロック、モジュール、回路、要素、および/または構成要素は、汎用プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラマブル論理構成要素、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または本明細書で説明する機能を実行するように設計されたそれらの任意の組合せで実装または実行され得る。汎用プロセッサはマイクロプロセッサであってもよいが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラまたはステートマシンであってもよい。プロセッサはまた、コンピューティング構成要素の組合せ、たとえば、DSPとマイクロプロセッサとの組合せ、いくつかのマイクロプロセッサ、DSPコアと連携する1つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成として実装される場合がある。
【００７０】
本明細書で開示された例に関して説明された方法またはアルゴリズムは、直接ハードウェアで、プロセッサによって実行可能なソフトウェアモジュールで、または両方の組合せで、処理ユニット、プログラミング命令、または他の指示の形態で具現化されてよく、かつ、単一のデバイスに含まれてよく、または複数のデバイスにわたって分散されてよい。ソフトウェアモジュールは、RAMメモリ、フラッシュメモリ、ROMメモリ、EPROMメモリ、EEPROMメモリ、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または当技術分野で知られている任意の他の形態の記憶媒体の中に存在し得る。記憶媒体は、プロセッサがその記憶媒体から情報を読み取り、かつその記憶媒体に情報を書き込むことができるように、プロセッサに結合され得る。代替として、記憶媒体はプロセッサと一体であり得る。
【００７１】
さらに、本明細書で開示する態様に関して説明する様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズムステップは、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装され得ることを当業者は諒解されよう。ハードウェアとソフトウェアのこの互換性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、およびステップが、上記では概してそれらの機能に関して説明された。そのような機能性がハードウェアとして実装されるのか、それともソフトウェアとして実装されるのかは、具体的な適用例および全体的なシステムに課される設計制約に依存する。
【００７２】
本明細書に記載の本発明の様々な特徴は、本発明から逸脱することなく、異なるシステムで実施され得る。上述の本開示の態様は例にすぎず、本発明を限定するものと解釈されるべきでないことに留意されたい。本開示の態様の説明は、例示的であることが意図され、特許請求の範囲を限定することは意図されない。したがって、本教示は、他のタイプの装置に容易に適用することができ、多くの代替形態、変更形態、および変形形態が当業者には明らかであろう。
【符号の説明】
【００７３】
202  処理回路
204  メモリ回路
206  アプリケーション
502  処理回路
504  メモリ回路
506  アプリケーション
802  処理回路
804  メモリ回路
806  アプリケーション
1000  電子デバイス
1002  バス
1004  処理回路
1005  メモリ回路
1006  コンピュータ可読記憶媒体
1008  バスインターフェース
1010  通信インターフェース
1012  ユーザインターフェース
1014  処理システム
1102  素数生成器回路
1103  乱数シードS取出し器回路
1104  乱数シードS生成器回路
1105  素数再生成器回路
1106  乱数R生成器回路
1107  関数f実行回路
1108  素数性テスト回路
1202  シードSおよび追加シードTi生成器回路
1204  第2シードSi生成器回路
1206  乱数Ri生成器回路
1208  素数性テスト回路
1210  シード取出し回路
1212  素数性乱数再生成器回路
【図１】
2016535310.tif 000003
【図２】
2016535310.tif 000004
【図３】
2016535310.tif 000005
【図４】
2016535310.tif 000006
【図５】
2016535310.tif 000007
【図６】
2016535310.tif 000008
【図７Ａ】
2016535310.tif 000009
【図７Ｂ】
2016535310.tif 000010
【図８Ａ】
2016535310.tif 000011
【図８Ｂ】
2016535310.tif 000012
【図９】
2016535310.tif 000013
【図１０】
2016535310.tif 000014
【図１１】
2016535310.tif 000015
【図１２】
2016535310.tif 000016
【手続補正書】
【提出日】平成28年3月1日(2016.3.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
生成される乱数Rが素数であると決定されるまで、
kビットを有する乱数シードSを生成することと、
前記シードSを入力として受信するとともに前記乱数Rを出力として生成する一方向関数fを適用することによって、nビットを有する前記乱数Rを前記シードSおよび秘密鍵ksに基づいて生成することであって、kがnよりも小さい、生成することと、
前記乱数Rが素数であるかどうかを決定することとを、
繰り返し行うことによって、処理回路において素数を生成するステップと、
素数であると決定された前記乱数Rを生成するために使用された前記乱数シードSをメモリ回路に記憶するステップと
を備える方法。
【請求項２】
前記記憶された乱数シードSを前記メモリ回路から取り出すステップと、
前記乱数シードSに基づいて前記素数を再生成するステップと
をさらに備える請求項1に記載の方法。
【請求項３】
前記素数に基づいて暗号鍵を生成するステップをさらに備える、
請求項2に記載の方法。
【請求項４】
前記シードSを記憶した後、前記乱数Rをメモリ回路から消去するステップをさらに備える、
請求項1に記載の方法。
【請求項５】
素数であると決定された前記乱数Rを生成するために使用された前記秘密鍵kSをセキュアメモリ回路に記憶するステップをさらに備える、
請求項1に記載の方法。
【請求項６】
前記乱数シードSは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶される、請求項1に記載の方法。
【請求項７】
前記シードSに基づいて前記乱数Rを生成するステップは、
前記シードSを入力として受信するとともに前記乱数Rを出力として生成する一方向関数fを実行することを含み、前記一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである、
請求項1に記載の方法。
【請求項８】
メモリ回路と、
前記メモリ回路に通信可能に結合された処理回路とを備える装置であって、前記処理回路は、
生成される乱数Rが素数であると決定されるまで、
kビットを有する乱数シードSを生成することと、
前記シードSを入力として受信するとともに前記乱数Rを出力として生成する一方向関数fを適用することによって、nビットを有する前記乱数Rを前記シードSおよび秘密鍵ksに基づいて生成することであって、kがnよりも小さい、生成することと、
前記乱数Rが素数であるかどうかを決定することとを、
繰り返し行うことによって素数を生成し、
素数であると決定された前記乱数Rを生成するために使用された前記乱数シードSを前記メモリ回路に記憶するように構成される、装置。
【請求項９】
前記処理回路は、
前記記憶された乱数シードSを前記メモリ回路から取り出し、
前記乱数シードSに基づいて前記素数を再生成するようにさらに構成される、
請求項8に記載の装置。
【請求項１０】
前記処理回路は、
前記素数に基づいて暗号鍵を生成するようにさらに構成される、
請求項9に記載の装置。
【請求項１１】
前記乱数シードSは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶される、請求項8に記載の装置。
【請求項１２】
前記処理回路は、前記秘密鍵kSをセキュアメモリ回路に記憶するようにさらに構成される、請求項8に記載の装置。
【請求項１３】
生成される乱数Rが素数であると決定されるまで、
kビットを有する乱数シードSを生成することと、
前記シードSを入力として受信するとともに前記乱数Rを出力として生成する一方向関数fを適用することによって、nビットを有する前記乱数Rを前記シードSおよび秘密鍵ksに基づいて生成することであって、kがnよりも小さい、生成することと、
前記乱数Rが素数であるかどうかを決定することとを、
繰り返し行うことによって素数を生成するための手段と、
素数であると決定された前記乱数Rを生成するために使用された前記乱数シードSをメモリ回路に記憶するための手段と
を備える装置。
【請求項１４】
前記記憶された乱数シードSを前記メモリ回路から取り出すための手段と、
前記乱数シードSに基づいて前記素数を再生成するための手段と
をさらに備える請求項13に記載の装置。
【請求項１５】
前記乱数シードSは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶される、請求項13に記載の装置。
【請求項１６】
前記装置は、前記秘密鍵kSをセキュアメモリ回路に記憶するための手段をさらに備える、請求項13に記載の装置。
【請求項１７】
そこに記憶された1つまたは複数の命令を有するコンピュータ可読記憶媒体であって、前記命令は、少なくとも1つのプロセッサによって実行されると、前記プロセッサに、
生成される乱数Rが素数であると決定されるまで、
kビットを有する乱数シードSを生成することと、
前記シードSを入力として受信するとともに前記乱数Rを出力として生成する一方向関数fを適用することによって、nビットを有する前記乱数Rを前記シードSおよび秘密鍵ksに基づいて生成することであって、kがnよりも小さい、生成することと、
前記乱数Rが素数であるかどうかを決定することとを、
繰り返し行うことによって素数を生成させ、
素数であると決定された前記乱数Rを生成するために使用された前記乱数シードSをメモリ回路に記憶させる、コンピュータ可読記憶媒体。
【請求項１８】
前記命令は、前記プロセッサに、さらに、
前記記憶された乱数シードSを前記メモリ回路から取り出させ、
前記乱数シードSに基づいて前記素数を再生成させる、
請求項17に記載のコンピュータ可読記憶媒体。
【請求項１９】
kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成するステップと、
前記複数の追加シードTiのうちの相異なる追加シードおよび前記乱数シードSにそれぞれ基づく複数の第2シードSiを生成するステップと、
nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成するステップであって、前記複数の乱数Riの各々は、前記複数の第2シードSiのうちの相異なる第2シードに基づくステップと、
前記複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定するステップであって、前記乱数RPは、前記複数の第2シードSiのうちの第2シードSPに基づき、前記第2シードSPは、前記複数の追加シードTiのうちの追加シードTPおよび前記乱数シードSに基づくステップと、
前記乱数シードSおよび前記追加シードTPをメモリ回路に記憶するステップと
を備える方法。
【請求項２０】
前記複数の乱数Riは、さらに秘密鍵kSに基づき、前記方法は、前記秘密鍵kSをセキュアメモリ回路に記憶するステップをさらに備える、請求項19に記載の方法。
【請求項２１】
前記記憶された乱数シードSおよび前記追加シードTPを前記メモリ回路から取り出すステップと、
前記乱数シードSおよび前記追加シードTPに基づいて、前記素数性乱数RPを再生成するステップと
をさらに備える請求項19に記載の方法。
【請求項２２】
前記乱数シードSおよび前記追加シードTPは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶され、前記方法は、
1つまたは複数の素数を得るための前記要求を前記暗号鍵生成プロセスから受信するステップと、
前記素数性乱数RPに基づいて暗号鍵を生成するステップと、
前記暗号鍵を前記暗号鍵生成プロセスに供給するステップと
をさらに備える請求項21に記載の方法。
【請求項２３】
前記複数の第2シードSiのうちの前記相異なる第2シードに基づいて前記複数の乱数Riを生成するステップは、
前記複数の第2シードSiの各々を入力として受信するとともに前記複数の乱数Riを出力として生成する一方向関数fを実行することを含み、前記一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである、
請求項20に記載の方法。
【請求項２４】
前記複数の乱数Riのうちの少なくとも1つの乱数が素数でないことを決定するステップと、
gビットを有する別の追加シードT2を生成するステップと、
前記追加シードT2および前記乱数シードSに基づいて、別の第2シードS2を生成するステップと、
nビットを有する別の乱数R2を生成するステップであって、前記乱数R2は、前記第2シードS2に基づくステップと、
前記乱数R2が素数であることを決定するステップと、
前記追加シードT2を前記メモリ回路に記憶するステップと
をさらに備える請求項20に記載の方法。
【請求項２５】
前記記憶された乱数シードSおよび前記追加シードT2を前記メモリ回路から取り出すステップと、
前記乱数シードSおよび前記追加シードT2に基づいて、前記素数性乱数R2を再生成するステップと
をさらに備える請求項24に記載の方法。
【請求項２６】
所定の数の素数を得るための要求を受信するステップと、
前記方法の別の追加シードT2を生成するステップと、前記追加シードT2および前記乱数シードSに基づいて別の第2シードS2を生成するステップと、nビットを有する別の乱数R2を生成するステップであって前記乱数R2が前記第2シードS2に基づくステップと、前記乱数R2が素数であることを決定するステップと、前記追加シードT2を前記メモリ回路に記憶するステップとを、異なる素数にそれぞれ関連付けられたいくつかの追加シードが記憶され前記所定の数に等しくなるまで繰り返すステップと
をさらに備える請求項24に記載の方法。
【請求項２７】
メモリ回路と、
前記メモリ回路に通信可能に結合された処理回路とを備える装置であって、前記処理回路は、
kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成し、
前記複数の追加シードTiのうちの相異なる追加シードおよび前記乱数シードSにそれぞれ基づく複数の第2シードSiを生成し、
nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成することであって、前記複数の乱数Riの各々は、前記複数の第2シードSiのうちの相異なる第2シードに基づくことをし、
前記複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定することであって、前記乱数RPは、前記複数の第2シードSiのうちの第2シードSPに基づき、前記第2シードSPは、前記複数の追加シードTiのうちの追加シードTPおよび前記乱数シードSに基づくことをし、
前記乱数シードSおよび前記追加シードTPを前記メモリ回路に記憶するように構成される、装置。
【請求項２８】
前記複数の乱数Riは、さらに秘密鍵kSに基づき、前記処理回路は、前記秘密鍵kSをセキュアメモリ回路に記憶するようにさらに構成される、請求項27に記載の装置。
【請求項２９】
前記処理回路は、
前記記憶された乱数シードSおよび前記追加シードTPを前記メモリ回路から取り出し、
前記乱数シードSおよび前記追加シードTPに基づいて、前記素数性乱数RPを再生成するようにさらに構成される、
請求項27に記載の装置。
【請求項３０】
前記乱数シードSおよび前記追加シードTPは、1つまたは複数の素数を得るための要求を暗号鍵生成プロセスから受信する前に記憶され、前記処理回路は、
1つまたは複数の素数を得るための前記要求を前記暗号鍵生成プロセスから受信し、
前記素数性乱数RPに基づいて暗号鍵を生成し、
前記暗号鍵を前記暗号鍵生成プロセスに供給するようにさらに構成される、
請求項29に記載の装置。
【請求項３１】
前記複数の第2シードSiのうちの前記相異なる第2シードに基づいて前記複数の乱数Riを生成することは、
前記複数の第2シードSiの各々を入力として受信するとともに前記複数の乱数Riを出力として生成する一方向関数fを実行するようにさらに構成される前記処理回路を含み、前記一方向関数fは、セキュアハッシュ関数および/またはブロック暗号のうちの少なくとも1つである、
請求項27に記載の装置。
【請求項３２】
前記処理回路は、
前記複数の乱数Riのうちの少なくとも1つの乱数が素数でないことを決定し、
gビットを有する別の追加シードT2を生成し、
前記追加シードT2および前記乱数シードSに基づいて、別の第2シードS2を生成し、
nビットを有する別の乱数R2を生成することであって、前記乱数R2は、前記第2シードS2に基づくことをし、
前記乱数R2が素数であることを決定し、
前記追加シードT2を前記メモリ回路に記憶するようにさらに構成される、
請求項27に記載の装置。
【請求項３３】
前記処理回路は、
前記記憶された乱数シードSおよび前記追加シードT2を前記メモリ回路から取り出し、
前記乱数シードSおよび前記追加シードT2に基づいて、前記素数性乱数R2を再生成するようにさらに構成される、
請求項32に記載の装置。
【請求項３４】
kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成するための手段と、
前記複数の追加シードTiのうちの相異なる追加シードおよび前記乱数シードSにそれぞれ基づく複数の第2シードSiを生成するための手段と、
nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成するための手段であって、前記複数の乱数Riの各々は、前記複数の第2シードSiのうちの相異なる第2シードに基づく手段と、
前記複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定するための手段であって、前記乱数RPは、前記複数の第2シードSiのうちの第2シードSPに基づき、前記第2シードSPは、前記複数の追加シードTiのうちの追加シードTPおよび前記乱数シードSに基づく手段と、
前記乱数シードSおよび前記追加シードTPをメモリ回路に記憶するための手段と
を備える装置。
【請求項３５】
前記記憶された乱数シードSおよび前記追加シードTPを前記メモリ回路から取り出すための手段と、
前記乱数シードSおよび前記追加シードTPに基づいて、前記素数性乱数RPを再生成するための手段と
をさらに備える請求項34に記載の装置。
【請求項３６】
そこに記憶された1つまたは複数の命令を有するコンピュータ可読記憶媒体であって、前記命令は、少なくとも1つのプロセッサによって実行されると、前記プロセッサに、
kビットを有する乱数シードSおよびgビットをそれぞれ有する複数の追加シードTiを生成させ、
前記複数の追加シードTiのうちの相異なる追加シードおよび前記乱数シードSにそれぞれ基づく複数の第2シードSiを生成させ、
nがk+gよりも小さい場合にnビットをそれぞれ有する複数の乱数Riを生成することであって、前記複数の乱数Riの各々は、前記複数の第2シードSiのうちの相異なる第2シードに基づくことをさせ、
前記複数の乱数Riのうちの少なくとも1つの乱数RPが素数であることを決定することであって、前記乱数RPは、前記複数の第2シードSiのうちの第2シードSPに基づき、前記第2シードSPは、前記複数の追加シードTiのうちの追加シードTPおよび前記乱数シードSに基づくことをさせ、
前記乱数シードSおよび前記追加シードTPをメモリ回路に記憶させる、コンピュータ可読記憶媒体。
【請求項３７】
前記命令は、前記プロセッサに、さらに、
前記記憶された乱数シードSおよび前記追加シードTPを前記メモリ回路から取り出させ、
前記乱数シードSおよび前記追加シードTPに基づいて、前記素数性乱数RPを再生成させる、
請求項36に記載のコンピュータ可読記憶媒体。
【国際調査報告】
2016535310.tif 000017
2016535310.tif 000018
2016535310.tif 000019