情報処理装置、情報処理方法、及びコンピュータプログラム
【課題】乱数生成能力と素数判定能力とを有する情報処理装置において、より効率的に素数を生成する。
【解決手段】入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段を備える。複数の乱数シードを取得し、１以上の判定手段が所属するそれぞれの判定グループに複数の乱数シードの何れかを対応付ける。乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する。ここで、着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する。乱数生成系列を用いて乱数を生成する。乱数のビット列を所定ビット数のビット列へと分割する。分割によって得られたそれぞれのビット列が示す数値を、着目乱数シードに対応付けられた判定グループを構成する判定手段の何れかへと出力する。
【解決手段】入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段を備える。複数の乱数シードを取得し、１以上の判定手段が所属するそれぞれの判定グループに複数の乱数シードの何れかを対応付ける。乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する。ここで、着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する。乱数生成系列を用いて乱数を生成する。乱数のビット列を所定ビット数のビット列へと分割する。分割によって得られたそれぞれのビット列が示す数値を、着目乱数シードに対応付けられた判定グループを構成する判定手段の何れかへと出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、素数を生成する情報処理装置、情報処理方法、及びコンピュータプログラムに関する。
【背景技術】
【０００２】
近年の情報通信において、情報を保護するための暗号技術は必要不可欠である。この暗号技術の一つとして、デジタル署名などに用いられる公開鍵暗号がある。一般的に公開鍵暗号の鍵ペアを生成するためには、桁の大きな素数ｐ，ｑの生成を必要とする。一般的に素数は、乱数生成器にて乱数を生成し、生成された乱数が素数かどうかを判定することにより生成される。
【０００３】
安全性の観点から、素数には高品質な一様性及び予測困難性などが求められる。この要求を満たすために、乱数を生成するために物理的な雑音（熱雑音など）が蓄積されるエントロピーソースを用いることが推奨されている。エントロピーソースから取得したデータ（エントロピー）を乱数の種（シード）として乱数生成器に入力することにより、高品質な乱数が得られる（非特許文献１）。
【０００４】
生成する素数のビット長が大きいほど、素数が見つかる確率は小さくなる。大きな素数を発見するためには、乱数の生成と素数判定とを何度も繰り返す必要があるため、多くのコンピュータリソース及び時間を必要とする。この問題を解決するために、特許文献１においては、負荷の大きな鍵ペア生成処理を分散処理を用いて実現する。こうして特許文献１の方法によれば、ＩＣカードのような処理リソースの小さなデバイスで鍵ペアを生成することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０００−５６６８０号公報
【非特許文献】
【０００６】
【非特許文献１】NIST, “Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised)”, NIST SP800-90
【発明の概要】
【発明が解決しようとする課題】
【０００７】
並列処理環境が一般的になったため、処理負荷の大きな鍵ペア生成処理を並列化して高速化することが考えられる。しかしながら、エントロピーは物理現象の観測によって生成され、高速化が難しいため、素数生成においてはシード生成がボトルネックになる。一方で高速化のために単一シードを複数回利用して素数を生成し、この素数を用いて鍵ペアを生成する場合、生成した鍵ペアの一様性及び予測困難性が低くなるため、通信の安全性が低下する。
【０００８】
本発明は、乱数生成能力と素数判定能力とを有する情報処理装置において、より効率的に素数を生成することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の目的を達成するために、例えば、本発明の情報処理装置は以下の構成を備える。すなわち、
所定ビット数の素数を並列に複数生成する情報処理装置であって、
入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段と、
複数の乱数シードを取得し、１以上の前記判定手段が所属するそれぞれの判定グループに当該複数の乱数シードの何れかを対応付ける対応付け手段と、
前記乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する制御手段と、を備え、
前記制御手段は、
着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する初期化手段と、
前記乱数生成系列を用いて乱数を生成する乱数生成手段と、
前記乱数のビット列を前記所定ビット数のビット列へと分割する分割手段と、
前記分割によって得られたそれぞれのビット列が示す数値を、前記着目乱数シードに対応付けられた前記判定グループを構成する前記判定手段の何れかへと出力する出力手段と、を備える
ことを特徴とする。
【発明の効果】
【００１０】
乱数生成能力と素数判定能力とを有する情報処理装置において、より効率的に素数を生成することができる。
【図面の簡単な説明】
【００１１】
【図１】鍵ペア生成システムの一例を示す図。
【図２】実施例１における鍵ペア生成の一例を示すフローチャート。
【図３】擬似乱数系列の生成の一例を示すフローチャート。
【図４】擬似乱数とＧＰＵコアの対応の一例を示す図。
【図５】実施例２における鍵ペア生成の一例を示すフローチャート。
【図６】実施例１及び２における情報処理装置１００の機能構成の一例を示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態の一例を図面に基づいて説明する。ただし、本発明の範囲は以下の実施形態に限定されるものではない。
【００１３】
［実施例１］
＜システム全体構成＞
図１（Ａ）は、実施例１に係る情報処理装置１００の例を示す。本実施例に係る情報処理装置１００は、所定ビット数の素数を並列に複数生成することができる。情報処理装置１００は、ＣＰＵ１０１、グラフィックボード１０２、主メモリ１０５、メモリコントローラハブ１０６、入出力コントローラハブ１０７、ＮＩＣ１０８、記憶装置１０９、及び外部接続ポート１１０を含む。
【００１４】
ＣＰＵ１０１は、主メモリ１０５又は記憶装置１０９に記録されたプログラム（コンピュータプログラム）に従って、情報処理装置１００の動作の少なくとも一部を制御する中央演算装置である。ＣＰＵ１０１は、ＣＰＵコアと呼ばれる演算処理部を複数有していてもよい。さらに、ＣＰＵ１０１は物理的な雑音をビット列（エントロピー）として取得することができる。物理的な雑音は任意のものでありうるが、例えば記憶装置１０９のシークタイム、タイミング、主メモリ１０５の状態、その他物理センサ（不図示）の出力などが挙げられる。
【００１５】
グラフィックボード１０２は、ＧＰＵ１０３とビデオメモリ１０４とを含む。グラフィックボード１０２は通常、画像処理に特化した拡張ボードである。例えばグラフィックボード１０２は、映像信号を取得し、モニタ１１２に映像を出力することができる。グラフィックボード１０２についての詳細は後述する。
【００１６】
主メモリ１０５は、ＣＰＵ１０１を制御するプログラムを格納することができる。主メモリ１０５はまた、ＣＰＵ１０１の動作中にデータを一時的に記憶することができる。主メモリ１０５は、例えばＲＡＭでありうる。
【００１７】
メモリコントローラハブ１０６は、リンク１１３、１１４、１１５及び１１６を介してそれぞれＣＰＵ１０１、主メモリ１０５、グラフィックボード１０２及び入出力コントローラハブ１０７と接続されている。メモリコントローラハブ１０６は、主メモリ１０５、グラフィックボード１０２及び入出力コントローラハブ１０７の間のデータ転送を制御する。
【００１８】
入出力コントローラハブ１０７は、リンク１１７、１１８及び１１９を介してそれぞれＮＩＣ１０８、記憶装置１０９及び外部接続ポート１１０と接続されている。入出力コントローラハブ１０７は、メモリコントローラハブ１０６、ＮＩＣ１０８、記憶装置１０９及び外部接続ポート１１０の間のデータ転送を制御する。
【００１９】
ＮＩＣ１０８は、ネットワークに接続するための通信インターフェイスである。ＮＩＣ１０８は例えば、有線ＬＡＮ、無線ＬＡＮ、又はＢｌｕｅｔｏｏｔｈ用の通信カードなどでありうる。
【００２０】
記憶装置１０９は、ＣＰＵ１０１が実行するプログラム、ＣＰＵ１０１が処理に用いるデータ、及び外部から取得したデータなどを格納する。記憶装置は例えば、ハードディスクのような磁気記憶装置、又はＳＳＤのようなフラッシュメモリでありうる。情報処理装置１００は、複数の記憶装置１０９を有していてもよい。また記憶装置１０９を介して、記憶媒体からプログラムを含むデータを読み出すこと、及び記憶媒体にデータを書き出すことが可能であってもよい。プログラムコードを供給するための記憶媒体としては、例えば、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、並びにＣＦカード及びＳＤカードなどのフラッシュメモリ、などを用いることができる。
【００２１】
外部接続ポート１１０は、外部機器を情報処理装置１００に接続するためのポートである。外部接続ポート１１０は、例えばＵＳＢポート、ＩＥＥＥ１３９４ポート、ＨＤＭＩポートなどでありうる。この外部接続ポート１１０に入力装置／出力装置１１１を接続することで、情報処理装置１００は入力装置／出力装置１１１との間でデータを送受信することができる。情報処理装置１００は、複数の外部接続ポート１１０を有していてもよい。
【００２２】
入力装置／出力装置１１１は、外部接続ポート１１０を介して情報処理装置１００にデータを入力する、又は出力する機器である。入力装置１１１は例えば、キーボード、マウス、イメージスキャナなどでありうる。出力装置１１１は例えば、プリンタなどでありうる。モニタ１１２は、情報処理装置１００が出力するデータを視覚的に表示する装置である。モニタ１１２は、グラフィックボード１０２が有する外部出力ポート、例えばアナログＲＧＢポート又はＤＶＩポートなどに接続されることができる。またモニタ１１２は、外部接続ポート１１０に接続されてもよい。モニタ１１２の例としては、例えば液晶モニタなどが挙げられる。
【００２３】
リンク１１３、１１４、１１５、１１６、１１７、１１８、及び１１９は内部バスである。リンク１１３、１１４、１１５、１１６、１１７、１１８、及び１１９は例えば、ＰＣＩ又はＰＣＩエクスプレスなどのバスでありうる。
【００２４】
以上、本実施例に係る情報処理装置１００として利用可能なハードウェア構成の一例を示した。以上説明された情報処理装置１００は、例えば、パーソナルコンピュータなどを用いて実現することができる。しかしながら、本実施例に係る情報処理装置１００は上述の構成に限定されるものではない。例えば変形例において、情報処理装置１００はグラフィックボード１０２を含まずにＧＰＵ１０３を含んでいてもよい。この場合、ＧＰＵ１０３が主メモリ１０５に対してデータを読み書きできるように、情報処理装置１００を構成すればよい。
【００２５】
また、ＣＰＵ１０１にＧＰＵ１０３を統合してもよい。さらには、ＧＰＵ１０３はメモリコントローラハブ１０６に統合されていてもよいし、ビデオメモリ１０４は主メモリ１０５に統合されていてもよい。このような場合、情報処理装置１００はグラフィックボード１０２を有さなくてもよい。もっともこのような場合にも、ＧＰＵ１０３やビデオメモリ１０４の機能は通常、情報処理装置１００のいずれかの構成要素に含まれる。
【００２６】
他の実施例として、ＣＰＵとＧＰＵとの少なくとも一方として、暗号処理に特化したハードウェアである暗号アクセラレータを用いてもよい。また、ＣＰＵとＧＰＵとの少なくとも一方として、演算処理が可能なＩＰコアを用いてもよい。
【００２７】
＜グラフィックボード１０２の構成＞
次に、図１（Ｂ）を参照して、グラフィックボード１０２について詳細に説明する。図１（Ｂ）は、本実施例に係るグラフィックボード１０２の構成の一例を示す。グラフィックボード１０２は、ＧＰＵ１０３及びビデオメモリ１０４で構成される。ビデオメモリ１０４は、表示する映像情報を保持するためのフレームバッファとして利用されるメモリ領域である。
【００２８】
ＧＰＵ１０３は、リンク１１８を介してビデオメモリ１０４に接続される。ＧＰＵ１０３はＣＰＵ１０１及びメモリコントローラハブ１０６を介して映像信号を取得し、描画処理を行う。ＧＰＵ１０３は、１つ以上のＧＰＵコア２０１・２０２と１つ以上のキャッシュメモリ２０３・２０４とから構成される。図１（Ｂ）の例においてグラフィックボード１０２は、２つのＧＰＵコア２０１・２０２と、２つのキャッシュメモリ２０３・２０４とを含むが、これには限定されない。
【００２９】
描画処理はＧＰＵコア２０１・２０２がそれぞれ行う。ＧＰＵコア２０１・２０２が並列して処理を行うことにより、描画処理が高速化される。並列して動作するＧＰＵコア２０１・２０２の数を増やすことにより、より高速な描画処理が実現されうる。近年では、数百個のＧＰＵコア２０１・２０２の並列動作による、高速な描画処理が実現されている。
【００３０】
このようにＧＰＵコア２０１・２０２は、描画処理を目的とした構成を有する。したがってＧＰＵコア２０１・２０２は通常、物理的なセンサを持たないため、物理的な雑音をビット列（エントロピー）として取得することができない。
【００３１】
＜素数・鍵ペアの生成方法＞
図２及び図６を参照して、本実施例における情報処理装置１００の動作を説明する。図２は、本実施例における処理の一例を示すフローチャートである。図２は特に、素数生成処理と、生成した素数を利用して鍵ペアを生成する処理を示している。また、情報処理装置１００の機能構成を図６に示す。図６に示す各部の機能は、例えばＣＰＵ１０１が主メモリ１０５又は記憶装置１０９に格納されるプログラムを実行することと、ＣＰＵ１０１の制御の下でＧＰＵ１０３がプログラムの一部を実行することと、によって実現されうる。
【００３２】
ステップＳ２０１においてＣＰＵ１０１は並列度を決定する。この処理は、分配部６５０が行うことができる。本明細書において並列度とは、並列に生成される鍵ペアの数（又は素数の数）を意味する。通常は、生成しようとする素数又は鍵ペアの数を並列度とすればよい。例えば、鍵ペアを５つ生成しようとする場合、並列度を５とすればよい。しかしながら、並列度の決定方法はこれに限定されない。例えば、ＣＰＵ１０１が有するコア数とＧＰＵコア２０１・２０２の数との少なくとも一方を用いて、並列度を決定してもよい。このとき、並列度を生成しようとする鍵ペア数以上にすることにより、所望の数の鍵ペアを高速に作成することができる。
【００３３】
例えば、生成しようとする鍵ペア数が３であり、ＣＰＵ１０１のコア数が２であり、ＧＰＵコア２０１・２０２の数が３６である場合について考える。後述のように、ＧＰＵコアは並列度の数のグループに分けられる。それぞれのグループを同じ数のＧＰＵコアによって構成することにより、各グループの処理速度を平準化することができる。このことは、ＧＰＵコアの数を割り切ることができるように並列度を決定することによって実現できる。また、それぞれのＧＰＵグループを別々のＣＰＵによって制御することにより、処理効率を向上させることができる。このことは、並列度をＣＰＵコア数で割り切ることができるように、並列度を決定することによって実現することができる。これらの観点から、この例においては並列度を６に設定することができる。
【００３４】
ステップＳ２０２でＣＰＵ１０１は、並列度の数だけの疑似乱数系列を初期化する。疑似乱数系列の初期化方法の詳細は後述する。
【００３５】
ステップＳ２０３でＣＰＵ１０１は、ＧＰＵコア２０１・２０２（判定手段）を並列度の数だけのグループ（判定グループ）に分割する。この処理は、分配部６５０が行うことができる。そして、それぞれのグループをステップＳ２０２で生成した疑似乱数系列のいずれか、すなわち乱数シードのいずれか（着目乱数シード）に対応付ける。この処理は、対応付け部６４０が行うことができる。ＧＰＵコア２０１・２０２の数がグループ数より小さい場合、１以上のＧＰＵコア２０１・２０２が複数のグループに所属するように、グループを形成してもよい。それぞれのグループに所属するＧＰＵコアの数は等しくなくてもよい。しかしながら、各グループのトータル処理能力が均一となるようにグループ化することにより、ステップＳ２０５における素数判定処理に要する時間を各グループの間で平準化し、より高速に所定個数の鍵ペアを生成することができる。
【００３６】
ステップＳ２０４でＣＰＵ１０１は、ステップＳ２０２で生成した疑似乱数系列のそれぞれを用いて乱数を生成する。
【００３７】
ステップＳ２０５でＧＰＵ１０３は、ステップＳ２０４で生成された乱数ビット列の少なくとも一部を取得し、取得した数値が素数であるか否かを判定する。より詳細には、それぞれのＧＰＵコアのグループに属するＧＰＵコア２０１・２０２は、着目乱数シードに対応付けられた擬似乱数系列を用いて生成された乱数ビット列の少なくとも一部を取得し、取得した数値が素数であるか否かを判定する。取得した数値が素数ではない場合には、ＧＰＵコア２０１・２０２はさらなるビット列をＣＰＵ１０１から取得する。ステップＳ２０５における処理の詳細は後述する。
【００３８】
ステップＳ２０６でＣＰＵ１０１は、素数と判定された数値を、それぞれのＧＰＵコアのグループから取得し、この素数を用いて鍵ペア６７０を生成する。この処理は、鍵生成部６６０が行うことができる。素数から鍵ペアを生成する方法は任意であり、公開鍵暗号アルゴリズムごとに定められた方法を用いればよい。素数から鍵ペアを生成する方法は公知であるから、本明細書においてはその説明を省略する。また本実施例において、ステップＳ２０６を省略してもよい。この場合、本実施例に係る情報処理装置１００は、素数を生成して出力することができる。
【００３９】
以上のステップＳ２０４からＳ２０６をそれぞれの擬似乱数系列について繰り返すことにより、所望の数の鍵ペアを生成することができる。ステップＳ２０４からＳ２０６はシーケンシャルに実行してもよい。すなわち、１つの擬似乱数系列から得られた乱数を用いて対応するＧＰＵコアのグループが素数判定を行い、素数を出力する。そして、別の擬似乱数系列から得られた乱数を用いて対応するＧＰＵコアのグループが素数判定を行い、素数を出力してもよい。
【００４０】
しかしながら、ステップＳ２０４からＳ２０６の処理は、それぞれの擬似乱数系列について並列に実行されてもよい。並列処理は、例えば以下のように実現できる。すなわち、主メモリ１０５又はビデオメモリ１０４に、それぞれの疑似乱数系列を用いて生成した疑似乱数を一時的に保持する領域を設ける（乱数プール）。同様に、主メモリ１０５又はビデオメモリ１０４に、それぞれの疑似乱数系列を用いて生成した素数を一時的に保持する領域を設ける（素数プール）。
【００４１】
ステップＳ２０４においてＣＰＵ１０１は、ステップＳ２０５及びＳ２０６とは非同期に、それぞれの擬似乱数系列についての疑似乱数を生成して乱数プールに書き込む。ステップＳ２０５においてそれぞれのＧＰＵグループに属するＧＰＵコア２０１・２０２は、ステップＳ２０４及びＳ２０６とは非同期に、対応する擬似乱数系列を用いて生成された疑似乱数が乱数プールに保持されているか否かを判定する。対応する擬似乱数が保持されている場合には、ＧＰＵコア２０１・２０２は対応する疑似乱数の少なくとも一部を読み出し、素数判定を行う。そしてＧＰＵコア２０１・２０２は、素数であると判定された数値を素数プールに書き込む。ステップ２０６においてＣＰＵ１０１は、ステップＳ２０４及びＳ２０５とは非同期に、素数プールに素数が保持されているか否かを判定する。素数プールに素数が保持されている場合には、ＣＰＵ１０１は素数プールから素数を読み出し、鍵ペアを生成する。
【００４２】
＜疑似乱数系列の生成方法＞
図３を参照して、ステップＳ２０２における処理の詳細を説明する。図３は、ステップＳ２０２における処理の一例を示すフローチャートである。ＣＰＵ１０１は、図３のフローチャートを並列度の数だけ繰り返すことにより、並列度の数だけの擬似乱数系列を初期化する。
【００４３】
ステップＳ３０１においてＣＰＵ１０１は、エントロピーソースからエントロピーを取得する。前述の通り、記憶装置１０９のシークタイム、タイミング、主メモリ１０５の物理状態、その他物理センサの測定値、及びこれらの組み合わせなどを、エントロピーソースとして用いることができる。
【００４４】
ステップＳ３０２においてＣＰＵ１０１は、十分なエントロピーを取得したか否かを判断する。エントロピーが十分であるか否かの判断は、生成する鍵ペア（又は素数）のビット長に従って決定できる。例えば、１０２４ビットのＲＳＡ暗号用の鍵ペアを生成する場合、エントロピーは８０ビット以上であればよい。また、２０４８ビットのＲＳＡ暗号用の鍵ペアを生成する場合、エントロピーは１１２ビット以上であればよい。生成する鍵ペアのビット長に従う必要なエントロピーは公知であるから、本明細書においては説明を省略する。
【００４５】
十分なエントロピーを取得できた場合は、処理はステップＳ３０３へ進む。十分なエントロピーを取得できなかった場合は、処理はステップＳ３０１へ戻る。処理がステップＳ３０１へ戻る場合、再度エントロピーの取得を試みても十分なエントロピーを取得できない可能性がある。したがって、ステップＳ３０２からＳ３０１へ戻る際には、所定時間だけ処理を停止し、すなわちウェイトを置き、エントロピーソースにエントロピーが溜まるのを待ってもよい。
【００４６】
ステップＳ３０３においてＣＰＵ１０１は、ステップＳ３０２で取得したエントロピーを疑似乱数の乱数シードとして、疑似乱数系列を初期化する。この処理は、制御部６３０の初期化部６３２が行うことができる。また、取得部６２０はシード６１０を取得することができる。擬似乱数系列の初期化は、使用する擬似乱数生成アルゴリズムに応じて行えばよい。例えば、ＦＩＰＳ１８６−２ Ａｐｐｅｎｄｉｘ ３．１に規定されている疑似乱数生成アルゴリズムを用いる場合、ＸＫＥＹにエントロピーを入力することにより疑似乱数系列を初期化すればよい。本実施例において使用される擬似乱数生成アルゴリズムは特に限定されず、例えばＡＮＳＩ Ｘ９．４２−２００１ Ａｎｎｅｘ Ｃ．１に規定されているような方法を用いることもできる。
【００４７】
＜疑似乱数及び素数生成方法＞
図４を参照して、ステップＳ２０５の処理の詳細について説明する。図４は、ある１つの擬似乱数系列に対応付けられたＧＰＵコアグループの処理を示す図である。他の擬似乱数系列に対応付けられたＧＰＵコアグループも、以下の説明と同様に処理を行うことができる。
【００４８】
ステップＳ２０４においてＣＰＵ１０１は、それぞれの擬似乱数系列を用いて擬似乱数を生成する。この処理は、制御部６３０の乱数生成部６３４が行うことができる。擬似乱数４０１は、１つの擬似乱数系列Ａを用いて生成された擬似乱数である。ステップＳ２０５においてＣＰＵ１０１は、擬似乱数４０１を、生成しようとする素数のビット長毎に分割する。この処理は、制御部６３０の分割部６３６が行うことができる。そしてＣＰＵ１０１は、分割することによって得られた数値のそれぞれを、擬似乱数系列Ａに対応するグループに属するＧＰＵコアのそれぞれに入力する。この処理は、制御部６３０の出力部６３８が行うことができる。同じ数値が異なるＧＰＵコアに入力されないようにすることで、素数判定処理を効率化することができる。
【００４９】
そしてＧＰＵコアは、入力された数値が素数であるか否かを判定する。素数判定アルゴリズムとしては、公知の任意のものを用いることができる。例えばＧＰＵコアは、ＦＩＰＳ１８６−２ Ａｐｐｅｎｄｉｘ２に規定されている素数判定アルゴリズムを用いることができる。しかしながら、本実施例で用いられる素数判定アルゴリズムはこれに限定されない。
【００５０】
ＧＰＵコア２０１・２０２が、入力された数値が素数であると判定した場合、ＧＰＵコア２０１・２０２は素数をＣＰＵ１０１又は素数プールなどのメモリに送出する。一方でＧＰＵコア２０１・２０２が、入力された数値は素数ではないと判定した場合、ＧＰＵコア２０１・２０２はさらなるビット列をＣＰＵ１０１から取得する。ここで擬似乱数系列Ａに対応付けられたグループに属するＧＰＵコア２０１・２０２は、擬似乱数４０１を分割することによって得られた数値のうち、まだＧＰＵコアに入力されていない数値を取得すればよい。擬似乱数４０１を分割することによって得られた数値のうち、まだＧＰＵコアに入力されていない数値が存在しない場合、ＣＰＵ１０１は擬似乱数系列Ａを用いて新たな擬似乱数を生成する。ＣＰＵ１０１は、擬似乱数４０１を分割することによって得られた全ての数値を何れかのＧＰＵコアに入力した際に、新たな擬似乱数を生成してもよい。
【００５１】
一方でＣＰＵ１０１は、擬似乱数系列Ａに対応付けられたグループに属するＧＰＵコアのいずれかが、入力された数値が素数であると判定した場合、擬似乱数系列Ａに対応付けられたグループに属する全てのＧＰＵコアの処理を中断させることができる。
【００５２】
以上に説明したように、本実施例においては、ＣＰＵ１０１で疑似乱数を生成し、ＧＰＵ１０３で疑似乱数から得られた数値が素数であるか否かを判定することによって、素数を生成することができる。特に、生成する素数の数又は鍵ペアの数に対応する数の疑似乱数系列を初期化することにより、一様性が高く、かつ予測困難性が低い素数を、高速に生成することができる。
【００５３】
１つの擬似乱数系列（すなわちエントロピー）からは１つの素数のみを生成することにより、より予測困難性が低い素数を生成することができる。したがって、いくつかのＧＰＵコアが並列して１つの擬似乱数系列に基づく乱数が素数であるか否かを判定する場合、１つのＧＰＵコアが素数を発見した場合、他のＧＰＵコアの処理は中断される。すなわち、他のＧＰＵコアの処理は無駄になる。
【００５４】
並列度、すなわちＧＰＵコアグループの数をｍとし、１つのＧＰＵコアグループに属するＧＰＵコアの数をｎとする。本実施例の方法によれば、乱数が素数であることをあるＧＰＵコアが発見した場合、ＣＰＵ１０１が処理を中断させるＧＰＵコアの数はｎ−１個である。一方、ＧＰＵ１０３が有する全てのＧＰＵコアに、同一の疑似乱数系列に基づく乱数が素数であるか否かを判定させる場合、乱数が素数であることをあるＧＰＵコアが発見した場合にＣＰＵ１０１が処理を中断させるＧＰＵコアの数はｎ×ｍ−１個となる。このように、ＧＰＵコアをグループ化し、それぞれのグループに異なる擬似乱数系列に基づく乱数が素数であるか否かを判定させる本実施例は、無駄になる処理が少ないため、より効率的な処理を実現できる。
【００５５】
［実施例２］
実施例１では、あらかじめ決定した並列度に基づいて疑似乱数生成及び素数判定を行った。実施例２では、並列度を動的に変化させながら疑似乱数生成及び素数判定を行う。実施例２に係る情報処理装置１００の構成は、実施例１と同様である。以下では、実施例２における処理のうち、実施例１とは異なる処理について説明する。したがって、実施例１と同様の処理については説明を省略する。
【００５６】
＜素数・鍵ペアの生成方法＞
図５を参照して、本実施例における情報処理装置１００の動作を説明する。図５は、本実施例における処理の一例を示すフローチャートである。図５には、素数生成処理と、生成した素数を利用した鍵ペア生成処理とが示されている。なお、図５のフローチャートの処理は、ＣＰＵ１０１が記憶装置１０９に格納されているプログラムを実行すること、及びＣＰＵ１０１の制御の下でＧＰＵ１０３がプログラムの一部を実行することによって実現されうる。
【００５７】
ステップＳ５０１においてＣＰＵ１０１は、エントロピーソースからエントロピーを取得し、取得したエントロピーのビット数を算出する。さらに、エントロピーのビット数を、生成しようとする鍵ペアに応じたビット数で割り、得られた値を並列度の初期値とする。生成しようとする鍵ペアに応じた必要なエントロピー数については前述したとおりである。ここで並列度は、取得したエントロピーから生成可能な素数又は鍵ペアの数を意味する。エントロピーのビット数を、生成しようとする鍵ペアに応じたビット数で割ると、初期化可能な乱数生成系列の数を得ることができる。このようにして、並列度（判定グループの数）を、初期化された乱数生成系列の数以下とすることができる。
【００５８】
なお、並列度の決定方法はこの方法に限定されず、ＣＰＵ１０１のコア数、ＧＰＵコア２０１・２０２の数、又はこれらの組み合わせに従って、実施例１と同様に決定してもよい。例えば、エントロピーのビット数を、生成しようとする鍵ペアに応じたビット数で割ることによって得られた値が並列度の上限となるように、並列度を適宜決定してもよい。また、ＣＰＵ１０１のコア数又はＧＰＵコア２０１・２０２の数に応じた値が並列度の下限となるように、並列度を決定してもよい。
【００５９】
ステップＳ５０２でＣＰＵ１０１は、実施例１と同様に、並列度と同数の疑似乱数系列を初期化する。また、鍵ペア生成が完了して利用が終わった疑似乱数系列を削除する。ステップＳ５０３でＣＰＵ１０１は、実施例１と同様に、ＧＰＵコア２０１・２０２を並列度と同数のグループに分け、それぞれのグループに別々の疑似乱数系列を対応付ける。
【００６０】
ステップＳ５０４でＣＰＵ１０１は、実施例１と同様に、ステップＳ５０２で初期化した疑似乱数系列のそれぞれを用いて乱数を生成する。ステップＳ５０５でＧＰＵコアのグループのそれぞれは、実施例１と同様に、対応づけられた疑似乱数系列が生成した疑似乱数が素数であるか否かを判定する。ステップＳ５０６でＣＰＵ１０１は、実施例１と同様に、生成した素数を用いて鍵ペアを生成する。実施例１と同様に、ステップＳ５０６は省略されてもよい。
【００６１】
実施例１のステップＳ２０５においてそれぞれのＧＰＵコア２０１・２０２は、ＣＰＵ１０１から、乱数を分割することによって得られた数値を繰り返し取得した。しかしながら本実施例のステップＳ５０５においてそれぞれのＧＰＵコア２０１・２０２は、ＣＰＵ１０１から、乱数を分割することによって得られた数値を１回だけ取得してもよい。またステップＳ５０５においてそれぞれのＧＰＵコア２０１・２０２は、対応付けられた擬似乱数系列を用いて生成された乱数を分割することによって得られた数値のうち、まだＧＰＵコアに入力されていない数値がなくなるまで、数値を取得してもよい。
【００６２】
ステップＳ５０７でＣＰＵ１０１は、所望の数の鍵ペア（又は素数）が生成されたか否かを判定する。所望の数の鍵ペアが生成されている場合、処理は終了する。所望の数の鍵ペアが生成されていない場合、処理はステップＳ５０８に進む。
【００６３】
ステップＳ５０８でＣＰＵ１０１は並列度を更新する。ＣＰＵ１０１は、ステップＳ５０１と同様に並列度を更新することができる。その後、処理はステップＳ５０２に戻る。以上のようにして、所望の数の素数又は鍵ペアを生成することができる。
【００６４】
本実施例ではステップＳ５０８において並列度が更新されたが、並列度の更新は図５のフローチャートとは独立に行われてもよい。例えば、所定の時間間隔で並列度の更新が行われてもよい。また、いずれかのＧＰＵコア２０１・２０２が、取得した数値が素数であると判定した際に、並列度の更新が行われてもよい。この場合、生成する残りの素数の数に従ってＧＰＵコアのグループ分けを変更（再決定）することができる。すなわち、生成する残りの素数の数以下となるように並列度を決定することができる。生成する残りの素数の数は、生成しようとする素数の総数と、ＧＰＵコア２０１・２０２のいずれかが既に出力した素数の数との差として求めることができ、並列度をこの差以下となるように決定すればよい。生成しようとする素数の総数は、例えば、入力部６８０がユーザ入力を介して取得することができる。
【００６５】
本実施例においては、ステップＳ５０８において並列度を更新した後で、ステップＳ５０３において再びＧＰＵコアのグループ分けを行う。ステップＳ５０３においてＣＰＵ１０１は、素数が発見された疑似乱数系列に対応するグループ（着目判定グループ）に属するＧＰＵコア２０１・２０２のみを、グループ分けの対象としてもよい。すなわち、着目判定グループに属するＧＰＵコアを、着目判定グループ以外のグループのいずれかに所属されてもよい。一方でＣＰＵ１０１は、全てのＧＰＵコア２０１・２０２をグループ分けの対象としてもよい。
【００６６】
素数が発見された疑似乱数系列に対応するグループに属するＧＰＵコア２０１・２０２だけをグループ分けの対象とする場合は、再割り当てするＧＰＵコア２０１・２０２が限定されるので、各グループのトータル処理能力を均一化することが困難になる。一方で、現在処理中のＧＰＵコア２０１・２０２と独立してグループ化処理ができるので、ＧＰＵコアの制御を容易に行うことができる。後者のように全てのＧＰＵコア２０１・２０２をグループ分けの対象とする場合は、各グループのトータル処理能力を均一化することは容易となる。しかしながら、現在処理中のＧＰＵコア２０１・２０２を同期しなければいけないため、ＧＰＵコアの制御が複雑になる。
【００６７】
ステップＳ５０２からＳ５０７は、シーケンシャルに実行されてもよい。しかしながら、これらは並列に実行されてもよい。並列処理は、例えば以下のように実現できる。すなわち、主メモリ１０５又はビデオメモリ１０４に、それぞれの疑似乱数系列を用いて生成した疑似乱数を一時的に保持する領域を設ける（乱数プール）。同様に、主メモリ１０５又はビデオメモリ１０４に、それぞれの疑似乱数系列を用いて生成した素数を一時的に保持する領域を設ける（素数プール）。
【００６８】
ステップＳ５０４においてＣＰＵ１０１は、他のステップとは非同期に、それぞれの擬似乱数系列についての疑似乱数を生成して乱数プールに書き込む。ステップＳ５０５においてそれぞれのＧＰＵグループに属するＧＰＵコア２０１・２０２は、他のステップとは非同期に、対応する擬似乱数系列を用いて生成された疑似乱数が乱数プールに保持されているか否かを判定する。対応する擬似乱数が保持されている場合には、ＧＰＵコア２０１・２０２は対応する疑似乱数の少なくとも一部を読み出し、素数判定を行う。そしてＧＰＵコア２０１・２０２は、素数であると判定された数値を素数プールに書き込む。ステップ５０６においてＣＰＵ１０１は、他のステップとは非同期に、素数プールに素数が保持されているか否かを判定する。素数プールに素数が保持されている場合には、ＣＰＵ１０１は素数プールから素数を読み出し、鍵ペアを生成する。
【００６９】
並列実行時におけるステップＳ５０２及びＳ５０３では、他の並列処理で利用中の疑似乱数系列やＧＰＵコア２０１・２０２を除外して処理を実施してもよい。すなわち、ステップＳ５０２においては、前のサイクルにおいて既に初期化されており、まだ素数が発見されていない擬似乱数系列については、初期化を行わなくてもよい。この場合ステップＳ５０８においては、続くステップＳ５０２で初期化する必要のない擬似乱数系列の数と、エントロピーのビット数を、生成しようとする鍵ペアに応じたビット数で割ることによって得られる値との和を、並列度の上限としてもよい。
【００７０】
以上説明したように、本実施例によれば、ＣＰＵ１０１で疑似乱数を生成し、ＧＰＵ１０３で疑似乱数を素数判定することによって、素数を生成することができる。特に、取得可能なエントロピーのビット数及び鍵ペアのビット数などに応じて、並列に生成する鍵ペアの数を動的に変更することにより、一様性が高く、予測困難性が低い素数を効率的に生成することができる。
【００７１】
また、実施例１の場合、ＧＰＵコア２０１・２０２のグループ分けは固定されている。したがって、処理が完了したグループに属するＧＰＵコア２０１・２０２はスリープしてしまう。一方、本実施例では、全ての処理が完了するまでＧＰＵコア２０１・２０２のグループ分けを変更する。したがって、処理が完了したグループに属するＧＰＵコア２０１・２０２をさらなる素数判定処理に用いることができる。このように実施例２によれば、より効率的に素数を生成することができる。
【００７２】
（他の実施形態）
本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体などとしての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに本発明を適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【００７３】
このプログラムの形態は、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータなど、様々な形態をとることができる。プログラムを供給するための記憶媒体としては、例えばフレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、及びＤＶＤなどを用いることができる。
【００７４】
また、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、プログラムをハードディスクなどの記憶媒体にダウンロードすることによっても、プログラムを供給することができる。自動インストール機能を含む圧縮されたファイルをハードディスクなどの記憶媒体にダウンロードすることによっても、プログラムを供給できる。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても、プログラムを供給できる。つまり、プログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバやＦＴＰサーバなども、本発明の範囲に含まれる。
【００７５】
プログラムを暗号化し、ＣＤ−ＲＯＭなどの記憶媒体に格納してユーザに配布することもできる。さらに、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせることもできる。ユーザはこの鍵情報を使用することにより、暗号化されたプログラムを復号してコンピュータにインストールすることもできる。
【００７６】
また、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などに処理の一部又は全部を行わせ、その処理によって前述した実施例の機能が実現されるプログラムも、本発明の範囲に含まれる。さらには、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれたプログラムコードに従って、この機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが、処理の一部又は全部を行ってもよい。
【００７７】
本発明は上記実施例に限定されるものではなく、本発明の趣旨に基づき種々の変形（各実施例の有機的な組合せを含む）が可能であり、それらを本発明の範囲から排除するものではない。本発明の様々な例と実施例を示して説明したが、当業者であれば、本発明の趣旨と範囲は、本明細書内の特定の説明に限定されないことを理解するだろう。なお、上述した実施例の各変形例を組み合わせた構成も全て本発明に含まれる。
【００７８】
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）をネットワーク又は各種記憶媒体を介してシステム或いは装置に供給する。そして、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵなど）がプログラムコードを読み出して実行する。この場合、そのプログラム、及び該プログラムを記憶した記憶媒体は本発明を構成することになる。
【技術分野】
【０００１】
本発明は、素数を生成する情報処理装置、情報処理方法、及びコンピュータプログラムに関する。
【背景技術】
【０００２】
近年の情報通信において、情報を保護するための暗号技術は必要不可欠である。この暗号技術の一つとして、デジタル署名などに用いられる公開鍵暗号がある。一般的に公開鍵暗号の鍵ペアを生成するためには、桁の大きな素数ｐ，ｑの生成を必要とする。一般的に素数は、乱数生成器にて乱数を生成し、生成された乱数が素数かどうかを判定することにより生成される。
【０００３】
安全性の観点から、素数には高品質な一様性及び予測困難性などが求められる。この要求を満たすために、乱数を生成するために物理的な雑音（熱雑音など）が蓄積されるエントロピーソースを用いることが推奨されている。エントロピーソースから取得したデータ（エントロピー）を乱数の種（シード）として乱数生成器に入力することにより、高品質な乱数が得られる（非特許文献１）。
【０００４】
生成する素数のビット長が大きいほど、素数が見つかる確率は小さくなる。大きな素数を発見するためには、乱数の生成と素数判定とを何度も繰り返す必要があるため、多くのコンピュータリソース及び時間を必要とする。この問題を解決するために、特許文献１においては、負荷の大きな鍵ペア生成処理を分散処理を用いて実現する。こうして特許文献１の方法によれば、ＩＣカードのような処理リソースの小さなデバイスで鍵ペアを生成することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０００−５６６８０号公報
【非特許文献】
【０００６】
【非特許文献１】NIST, “Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised)”, NIST SP800-90
【発明の概要】
【発明が解決しようとする課題】
【０００７】
並列処理環境が一般的になったため、処理負荷の大きな鍵ペア生成処理を並列化して高速化することが考えられる。しかしながら、エントロピーは物理現象の観測によって生成され、高速化が難しいため、素数生成においてはシード生成がボトルネックになる。一方で高速化のために単一シードを複数回利用して素数を生成し、この素数を用いて鍵ペアを生成する場合、生成した鍵ペアの一様性及び予測困難性が低くなるため、通信の安全性が低下する。
【０００８】
本発明は、乱数生成能力と素数判定能力とを有する情報処理装置において、より効率的に素数を生成することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の目的を達成するために、例えば、本発明の情報処理装置は以下の構成を備える。すなわち、
所定ビット数の素数を並列に複数生成する情報処理装置であって、
入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段と、
複数の乱数シードを取得し、１以上の前記判定手段が所属するそれぞれの判定グループに当該複数の乱数シードの何れかを対応付ける対応付け手段と、
前記乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する制御手段と、を備え、
前記制御手段は、
着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する初期化手段と、
前記乱数生成系列を用いて乱数を生成する乱数生成手段と、
前記乱数のビット列を前記所定ビット数のビット列へと分割する分割手段と、
前記分割によって得られたそれぞれのビット列が示す数値を、前記着目乱数シードに対応付けられた前記判定グループを構成する前記判定手段の何れかへと出力する出力手段と、を備える
ことを特徴とする。
【発明の効果】
【００１０】
乱数生成能力と素数判定能力とを有する情報処理装置において、より効率的に素数を生成することができる。
【図面の簡単な説明】
【００１１】
【図１】鍵ペア生成システムの一例を示す図。
【図２】実施例１における鍵ペア生成の一例を示すフローチャート。
【図３】擬似乱数系列の生成の一例を示すフローチャート。
【図４】擬似乱数とＧＰＵコアの対応の一例を示す図。
【図５】実施例２における鍵ペア生成の一例を示すフローチャート。
【図６】実施例１及び２における情報処理装置１００の機能構成の一例を示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態の一例を図面に基づいて説明する。ただし、本発明の範囲は以下の実施形態に限定されるものではない。
【００１３】
［実施例１］
＜システム全体構成＞
図１（Ａ）は、実施例１に係る情報処理装置１００の例を示す。本実施例に係る情報処理装置１００は、所定ビット数の素数を並列に複数生成することができる。情報処理装置１００は、ＣＰＵ１０１、グラフィックボード１０２、主メモリ１０５、メモリコントローラハブ１０６、入出力コントローラハブ１０７、ＮＩＣ１０８、記憶装置１０９、及び外部接続ポート１１０を含む。
【００１４】
ＣＰＵ１０１は、主メモリ１０５又は記憶装置１０９に記録されたプログラム（コンピュータプログラム）に従って、情報処理装置１００の動作の少なくとも一部を制御する中央演算装置である。ＣＰＵ１０１は、ＣＰＵコアと呼ばれる演算処理部を複数有していてもよい。さらに、ＣＰＵ１０１は物理的な雑音をビット列（エントロピー）として取得することができる。物理的な雑音は任意のものでありうるが、例えば記憶装置１０９のシークタイム、タイミング、主メモリ１０５の状態、その他物理センサ（不図示）の出力などが挙げられる。
【００１５】
グラフィックボード１０２は、ＧＰＵ１０３とビデオメモリ１０４とを含む。グラフィックボード１０２は通常、画像処理に特化した拡張ボードである。例えばグラフィックボード１０２は、映像信号を取得し、モニタ１１２に映像を出力することができる。グラフィックボード１０２についての詳細は後述する。
【００１６】
主メモリ１０５は、ＣＰＵ１０１を制御するプログラムを格納することができる。主メモリ１０５はまた、ＣＰＵ１０１の動作中にデータを一時的に記憶することができる。主メモリ１０５は、例えばＲＡＭでありうる。
【００１７】
メモリコントローラハブ１０６は、リンク１１３、１１４、１１５及び１１６を介してそれぞれＣＰＵ１０１、主メモリ１０５、グラフィックボード１０２及び入出力コントローラハブ１０７と接続されている。メモリコントローラハブ１０６は、主メモリ１０５、グラフィックボード１０２及び入出力コントローラハブ１０７の間のデータ転送を制御する。
【００１８】
入出力コントローラハブ１０７は、リンク１１７、１１８及び１１９を介してそれぞれＮＩＣ１０８、記憶装置１０９及び外部接続ポート１１０と接続されている。入出力コントローラハブ１０７は、メモリコントローラハブ１０６、ＮＩＣ１０８、記憶装置１０９及び外部接続ポート１１０の間のデータ転送を制御する。
【００１９】
ＮＩＣ１０８は、ネットワークに接続するための通信インターフェイスである。ＮＩＣ１０８は例えば、有線ＬＡＮ、無線ＬＡＮ、又はＢｌｕｅｔｏｏｔｈ用の通信カードなどでありうる。
【００２０】
記憶装置１０９は、ＣＰＵ１０１が実行するプログラム、ＣＰＵ１０１が処理に用いるデータ、及び外部から取得したデータなどを格納する。記憶装置は例えば、ハードディスクのような磁気記憶装置、又はＳＳＤのようなフラッシュメモリでありうる。情報処理装置１００は、複数の記憶装置１０９を有していてもよい。また記憶装置１０９を介して、記憶媒体からプログラムを含むデータを読み出すこと、及び記憶媒体にデータを書き出すことが可能であってもよい。プログラムコードを供給するための記憶媒体としては、例えば、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、並びにＣＦカード及びＳＤカードなどのフラッシュメモリ、などを用いることができる。
【００２１】
外部接続ポート１１０は、外部機器を情報処理装置１００に接続するためのポートである。外部接続ポート１１０は、例えばＵＳＢポート、ＩＥＥＥ１３９４ポート、ＨＤＭＩポートなどでありうる。この外部接続ポート１１０に入力装置／出力装置１１１を接続することで、情報処理装置１００は入力装置／出力装置１１１との間でデータを送受信することができる。情報処理装置１００は、複数の外部接続ポート１１０を有していてもよい。
【００２２】
入力装置／出力装置１１１は、外部接続ポート１１０を介して情報処理装置１００にデータを入力する、又は出力する機器である。入力装置１１１は例えば、キーボード、マウス、イメージスキャナなどでありうる。出力装置１１１は例えば、プリンタなどでありうる。モニタ１１２は、情報処理装置１００が出力するデータを視覚的に表示する装置である。モニタ１１２は、グラフィックボード１０２が有する外部出力ポート、例えばアナログＲＧＢポート又はＤＶＩポートなどに接続されることができる。またモニタ１１２は、外部接続ポート１１０に接続されてもよい。モニタ１１２の例としては、例えば液晶モニタなどが挙げられる。
【００２３】
リンク１１３、１１４、１１５、１１６、１１７、１１８、及び１１９は内部バスである。リンク１１３、１１４、１１５、１１６、１１７、１１８、及び１１９は例えば、ＰＣＩ又はＰＣＩエクスプレスなどのバスでありうる。
【００２４】
以上、本実施例に係る情報処理装置１００として利用可能なハードウェア構成の一例を示した。以上説明された情報処理装置１００は、例えば、パーソナルコンピュータなどを用いて実現することができる。しかしながら、本実施例に係る情報処理装置１００は上述の構成に限定されるものではない。例えば変形例において、情報処理装置１００はグラフィックボード１０２を含まずにＧＰＵ１０３を含んでいてもよい。この場合、ＧＰＵ１０３が主メモリ１０５に対してデータを読み書きできるように、情報処理装置１００を構成すればよい。
【００２５】
また、ＣＰＵ１０１にＧＰＵ１０３を統合してもよい。さらには、ＧＰＵ１０３はメモリコントローラハブ１０６に統合されていてもよいし、ビデオメモリ１０４は主メモリ１０５に統合されていてもよい。このような場合、情報処理装置１００はグラフィックボード１０２を有さなくてもよい。もっともこのような場合にも、ＧＰＵ１０３やビデオメモリ１０４の機能は通常、情報処理装置１００のいずれかの構成要素に含まれる。
【００２６】
他の実施例として、ＣＰＵとＧＰＵとの少なくとも一方として、暗号処理に特化したハードウェアである暗号アクセラレータを用いてもよい。また、ＣＰＵとＧＰＵとの少なくとも一方として、演算処理が可能なＩＰコアを用いてもよい。
【００２７】
＜グラフィックボード１０２の構成＞
次に、図１（Ｂ）を参照して、グラフィックボード１０２について詳細に説明する。図１（Ｂ）は、本実施例に係るグラフィックボード１０２の構成の一例を示す。グラフィックボード１０２は、ＧＰＵ１０３及びビデオメモリ１０４で構成される。ビデオメモリ１０４は、表示する映像情報を保持するためのフレームバッファとして利用されるメモリ領域である。
【００２８】
ＧＰＵ１０３は、リンク１１８を介してビデオメモリ１０４に接続される。ＧＰＵ１０３はＣＰＵ１０１及びメモリコントローラハブ１０６を介して映像信号を取得し、描画処理を行う。ＧＰＵ１０３は、１つ以上のＧＰＵコア２０１・２０２と１つ以上のキャッシュメモリ２０３・２０４とから構成される。図１（Ｂ）の例においてグラフィックボード１０２は、２つのＧＰＵコア２０１・２０２と、２つのキャッシュメモリ２０３・２０４とを含むが、これには限定されない。
【００２９】
描画処理はＧＰＵコア２０１・２０２がそれぞれ行う。ＧＰＵコア２０１・２０２が並列して処理を行うことにより、描画処理が高速化される。並列して動作するＧＰＵコア２０１・２０２の数を増やすことにより、より高速な描画処理が実現されうる。近年では、数百個のＧＰＵコア２０１・２０２の並列動作による、高速な描画処理が実現されている。
【００３０】
このようにＧＰＵコア２０１・２０２は、描画処理を目的とした構成を有する。したがってＧＰＵコア２０１・２０２は通常、物理的なセンサを持たないため、物理的な雑音をビット列（エントロピー）として取得することができない。
【００３１】
＜素数・鍵ペアの生成方法＞
図２及び図６を参照して、本実施例における情報処理装置１００の動作を説明する。図２は、本実施例における処理の一例を示すフローチャートである。図２は特に、素数生成処理と、生成した素数を利用して鍵ペアを生成する処理を示している。また、情報処理装置１００の機能構成を図６に示す。図６に示す各部の機能は、例えばＣＰＵ１０１が主メモリ１０５又は記憶装置１０９に格納されるプログラムを実行することと、ＣＰＵ１０１の制御の下でＧＰＵ１０３がプログラムの一部を実行することと、によって実現されうる。
【００３２】
ステップＳ２０１においてＣＰＵ１０１は並列度を決定する。この処理は、分配部６５０が行うことができる。本明細書において並列度とは、並列に生成される鍵ペアの数（又は素数の数）を意味する。通常は、生成しようとする素数又は鍵ペアの数を並列度とすればよい。例えば、鍵ペアを５つ生成しようとする場合、並列度を５とすればよい。しかしながら、並列度の決定方法はこれに限定されない。例えば、ＣＰＵ１０１が有するコア数とＧＰＵコア２０１・２０２の数との少なくとも一方を用いて、並列度を決定してもよい。このとき、並列度を生成しようとする鍵ペア数以上にすることにより、所望の数の鍵ペアを高速に作成することができる。
【００３３】
例えば、生成しようとする鍵ペア数が３であり、ＣＰＵ１０１のコア数が２であり、ＧＰＵコア２０１・２０２の数が３６である場合について考える。後述のように、ＧＰＵコアは並列度の数のグループに分けられる。それぞれのグループを同じ数のＧＰＵコアによって構成することにより、各グループの処理速度を平準化することができる。このことは、ＧＰＵコアの数を割り切ることができるように並列度を決定することによって実現できる。また、それぞれのＧＰＵグループを別々のＣＰＵによって制御することにより、処理効率を向上させることができる。このことは、並列度をＣＰＵコア数で割り切ることができるように、並列度を決定することによって実現することができる。これらの観点から、この例においては並列度を６に設定することができる。
【００３４】
ステップＳ２０２でＣＰＵ１０１は、並列度の数だけの疑似乱数系列を初期化する。疑似乱数系列の初期化方法の詳細は後述する。
【００３５】
ステップＳ２０３でＣＰＵ１０１は、ＧＰＵコア２０１・２０２（判定手段）を並列度の数だけのグループ（判定グループ）に分割する。この処理は、分配部６５０が行うことができる。そして、それぞれのグループをステップＳ２０２で生成した疑似乱数系列のいずれか、すなわち乱数シードのいずれか（着目乱数シード）に対応付ける。この処理は、対応付け部６４０が行うことができる。ＧＰＵコア２０１・２０２の数がグループ数より小さい場合、１以上のＧＰＵコア２０１・２０２が複数のグループに所属するように、グループを形成してもよい。それぞれのグループに所属するＧＰＵコアの数は等しくなくてもよい。しかしながら、各グループのトータル処理能力が均一となるようにグループ化することにより、ステップＳ２０５における素数判定処理に要する時間を各グループの間で平準化し、より高速に所定個数の鍵ペアを生成することができる。
【００３６】
ステップＳ２０４でＣＰＵ１０１は、ステップＳ２０２で生成した疑似乱数系列のそれぞれを用いて乱数を生成する。
【００３７】
ステップＳ２０５でＧＰＵ１０３は、ステップＳ２０４で生成された乱数ビット列の少なくとも一部を取得し、取得した数値が素数であるか否かを判定する。より詳細には、それぞれのＧＰＵコアのグループに属するＧＰＵコア２０１・２０２は、着目乱数シードに対応付けられた擬似乱数系列を用いて生成された乱数ビット列の少なくとも一部を取得し、取得した数値が素数であるか否かを判定する。取得した数値が素数ではない場合には、ＧＰＵコア２０１・２０２はさらなるビット列をＣＰＵ１０１から取得する。ステップＳ２０５における処理の詳細は後述する。
【００３８】
ステップＳ２０６でＣＰＵ１０１は、素数と判定された数値を、それぞれのＧＰＵコアのグループから取得し、この素数を用いて鍵ペア６７０を生成する。この処理は、鍵生成部６６０が行うことができる。素数から鍵ペアを生成する方法は任意であり、公開鍵暗号アルゴリズムごとに定められた方法を用いればよい。素数から鍵ペアを生成する方法は公知であるから、本明細書においてはその説明を省略する。また本実施例において、ステップＳ２０６を省略してもよい。この場合、本実施例に係る情報処理装置１００は、素数を生成して出力することができる。
【００３９】
以上のステップＳ２０４からＳ２０６をそれぞれの擬似乱数系列について繰り返すことにより、所望の数の鍵ペアを生成することができる。ステップＳ２０４からＳ２０６はシーケンシャルに実行してもよい。すなわち、１つの擬似乱数系列から得られた乱数を用いて対応するＧＰＵコアのグループが素数判定を行い、素数を出力する。そして、別の擬似乱数系列から得られた乱数を用いて対応するＧＰＵコアのグループが素数判定を行い、素数を出力してもよい。
【００４０】
しかしながら、ステップＳ２０４からＳ２０６の処理は、それぞれの擬似乱数系列について並列に実行されてもよい。並列処理は、例えば以下のように実現できる。すなわち、主メモリ１０５又はビデオメモリ１０４に、それぞれの疑似乱数系列を用いて生成した疑似乱数を一時的に保持する領域を設ける（乱数プール）。同様に、主メモリ１０５又はビデオメモリ１０４に、それぞれの疑似乱数系列を用いて生成した素数を一時的に保持する領域を設ける（素数プール）。
【００４１】
ステップＳ２０４においてＣＰＵ１０１は、ステップＳ２０５及びＳ２０６とは非同期に、それぞれの擬似乱数系列についての疑似乱数を生成して乱数プールに書き込む。ステップＳ２０５においてそれぞれのＧＰＵグループに属するＧＰＵコア２０１・２０２は、ステップＳ２０４及びＳ２０６とは非同期に、対応する擬似乱数系列を用いて生成された疑似乱数が乱数プールに保持されているか否かを判定する。対応する擬似乱数が保持されている場合には、ＧＰＵコア２０１・２０２は対応する疑似乱数の少なくとも一部を読み出し、素数判定を行う。そしてＧＰＵコア２０１・２０２は、素数であると判定された数値を素数プールに書き込む。ステップ２０６においてＣＰＵ１０１は、ステップＳ２０４及びＳ２０５とは非同期に、素数プールに素数が保持されているか否かを判定する。素数プールに素数が保持されている場合には、ＣＰＵ１０１は素数プールから素数を読み出し、鍵ペアを生成する。
【００４２】
＜疑似乱数系列の生成方法＞
図３を参照して、ステップＳ２０２における処理の詳細を説明する。図３は、ステップＳ２０２における処理の一例を示すフローチャートである。ＣＰＵ１０１は、図３のフローチャートを並列度の数だけ繰り返すことにより、並列度の数だけの擬似乱数系列を初期化する。
【００４３】
ステップＳ３０１においてＣＰＵ１０１は、エントロピーソースからエントロピーを取得する。前述の通り、記憶装置１０９のシークタイム、タイミング、主メモリ１０５の物理状態、その他物理センサの測定値、及びこれらの組み合わせなどを、エントロピーソースとして用いることができる。
【００４４】
ステップＳ３０２においてＣＰＵ１０１は、十分なエントロピーを取得したか否かを判断する。エントロピーが十分であるか否かの判断は、生成する鍵ペア（又は素数）のビット長に従って決定できる。例えば、１０２４ビットのＲＳＡ暗号用の鍵ペアを生成する場合、エントロピーは８０ビット以上であればよい。また、２０４８ビットのＲＳＡ暗号用の鍵ペアを生成する場合、エントロピーは１１２ビット以上であればよい。生成する鍵ペアのビット長に従う必要なエントロピーは公知であるから、本明細書においては説明を省略する。
【００４５】
十分なエントロピーを取得できた場合は、処理はステップＳ３０３へ進む。十分なエントロピーを取得できなかった場合は、処理はステップＳ３０１へ戻る。処理がステップＳ３０１へ戻る場合、再度エントロピーの取得を試みても十分なエントロピーを取得できない可能性がある。したがって、ステップＳ３０２からＳ３０１へ戻る際には、所定時間だけ処理を停止し、すなわちウェイトを置き、エントロピーソースにエントロピーが溜まるのを待ってもよい。
【００４６】
ステップＳ３０３においてＣＰＵ１０１は、ステップＳ３０２で取得したエントロピーを疑似乱数の乱数シードとして、疑似乱数系列を初期化する。この処理は、制御部６３０の初期化部６３２が行うことができる。また、取得部６２０はシード６１０を取得することができる。擬似乱数系列の初期化は、使用する擬似乱数生成アルゴリズムに応じて行えばよい。例えば、ＦＩＰＳ１８６−２ Ａｐｐｅｎｄｉｘ ３．１に規定されている疑似乱数生成アルゴリズムを用いる場合、ＸＫＥＹにエントロピーを入力することにより疑似乱数系列を初期化すればよい。本実施例において使用される擬似乱数生成アルゴリズムは特に限定されず、例えばＡＮＳＩ Ｘ９．４２−２００１ Ａｎｎｅｘ Ｃ．１に規定されているような方法を用いることもできる。
【００４７】
＜疑似乱数及び素数生成方法＞
図４を参照して、ステップＳ２０５の処理の詳細について説明する。図４は、ある１つの擬似乱数系列に対応付けられたＧＰＵコアグループの処理を示す図である。他の擬似乱数系列に対応付けられたＧＰＵコアグループも、以下の説明と同様に処理を行うことができる。
【００４８】
ステップＳ２０４においてＣＰＵ１０１は、それぞれの擬似乱数系列を用いて擬似乱数を生成する。この処理は、制御部６３０の乱数生成部６３４が行うことができる。擬似乱数４０１は、１つの擬似乱数系列Ａを用いて生成された擬似乱数である。ステップＳ２０５においてＣＰＵ１０１は、擬似乱数４０１を、生成しようとする素数のビット長毎に分割する。この処理は、制御部６３０の分割部６３６が行うことができる。そしてＣＰＵ１０１は、分割することによって得られた数値のそれぞれを、擬似乱数系列Ａに対応するグループに属するＧＰＵコアのそれぞれに入力する。この処理は、制御部６３０の出力部６３８が行うことができる。同じ数値が異なるＧＰＵコアに入力されないようにすることで、素数判定処理を効率化することができる。
【００４９】
そしてＧＰＵコアは、入力された数値が素数であるか否かを判定する。素数判定アルゴリズムとしては、公知の任意のものを用いることができる。例えばＧＰＵコアは、ＦＩＰＳ１８６−２ Ａｐｐｅｎｄｉｘ２に規定されている素数判定アルゴリズムを用いることができる。しかしながら、本実施例で用いられる素数判定アルゴリズムはこれに限定されない。
【００５０】
ＧＰＵコア２０１・２０２が、入力された数値が素数であると判定した場合、ＧＰＵコア２０１・２０２は素数をＣＰＵ１０１又は素数プールなどのメモリに送出する。一方でＧＰＵコア２０１・２０２が、入力された数値は素数ではないと判定した場合、ＧＰＵコア２０１・２０２はさらなるビット列をＣＰＵ１０１から取得する。ここで擬似乱数系列Ａに対応付けられたグループに属するＧＰＵコア２０１・２０２は、擬似乱数４０１を分割することによって得られた数値のうち、まだＧＰＵコアに入力されていない数値を取得すればよい。擬似乱数４０１を分割することによって得られた数値のうち、まだＧＰＵコアに入力されていない数値が存在しない場合、ＣＰＵ１０１は擬似乱数系列Ａを用いて新たな擬似乱数を生成する。ＣＰＵ１０１は、擬似乱数４０１を分割することによって得られた全ての数値を何れかのＧＰＵコアに入力した際に、新たな擬似乱数を生成してもよい。
【００５１】
一方でＣＰＵ１０１は、擬似乱数系列Ａに対応付けられたグループに属するＧＰＵコアのいずれかが、入力された数値が素数であると判定した場合、擬似乱数系列Ａに対応付けられたグループに属する全てのＧＰＵコアの処理を中断させることができる。
【００５２】
以上に説明したように、本実施例においては、ＣＰＵ１０１で疑似乱数を生成し、ＧＰＵ１０３で疑似乱数から得られた数値が素数であるか否かを判定することによって、素数を生成することができる。特に、生成する素数の数又は鍵ペアの数に対応する数の疑似乱数系列を初期化することにより、一様性が高く、かつ予測困難性が低い素数を、高速に生成することができる。
【００５３】
１つの擬似乱数系列（すなわちエントロピー）からは１つの素数のみを生成することにより、より予測困難性が低い素数を生成することができる。したがって、いくつかのＧＰＵコアが並列して１つの擬似乱数系列に基づく乱数が素数であるか否かを判定する場合、１つのＧＰＵコアが素数を発見した場合、他のＧＰＵコアの処理は中断される。すなわち、他のＧＰＵコアの処理は無駄になる。
【００５４】
並列度、すなわちＧＰＵコアグループの数をｍとし、１つのＧＰＵコアグループに属するＧＰＵコアの数をｎとする。本実施例の方法によれば、乱数が素数であることをあるＧＰＵコアが発見した場合、ＣＰＵ１０１が処理を中断させるＧＰＵコアの数はｎ−１個である。一方、ＧＰＵ１０３が有する全てのＧＰＵコアに、同一の疑似乱数系列に基づく乱数が素数であるか否かを判定させる場合、乱数が素数であることをあるＧＰＵコアが発見した場合にＣＰＵ１０１が処理を中断させるＧＰＵコアの数はｎ×ｍ−１個となる。このように、ＧＰＵコアをグループ化し、それぞれのグループに異なる擬似乱数系列に基づく乱数が素数であるか否かを判定させる本実施例は、無駄になる処理が少ないため、より効率的な処理を実現できる。
【００５５】
［実施例２］
実施例１では、あらかじめ決定した並列度に基づいて疑似乱数生成及び素数判定を行った。実施例２では、並列度を動的に変化させながら疑似乱数生成及び素数判定を行う。実施例２に係る情報処理装置１００の構成は、実施例１と同様である。以下では、実施例２における処理のうち、実施例１とは異なる処理について説明する。したがって、実施例１と同様の処理については説明を省略する。
【００５６】
＜素数・鍵ペアの生成方法＞
図５を参照して、本実施例における情報処理装置１００の動作を説明する。図５は、本実施例における処理の一例を示すフローチャートである。図５には、素数生成処理と、生成した素数を利用した鍵ペア生成処理とが示されている。なお、図５のフローチャートの処理は、ＣＰＵ１０１が記憶装置１０９に格納されているプログラムを実行すること、及びＣＰＵ１０１の制御の下でＧＰＵ１０３がプログラムの一部を実行することによって実現されうる。
【００５７】
ステップＳ５０１においてＣＰＵ１０１は、エントロピーソースからエントロピーを取得し、取得したエントロピーのビット数を算出する。さらに、エントロピーのビット数を、生成しようとする鍵ペアに応じたビット数で割り、得られた値を並列度の初期値とする。生成しようとする鍵ペアに応じた必要なエントロピー数については前述したとおりである。ここで並列度は、取得したエントロピーから生成可能な素数又は鍵ペアの数を意味する。エントロピーのビット数を、生成しようとする鍵ペアに応じたビット数で割ると、初期化可能な乱数生成系列の数を得ることができる。このようにして、並列度（判定グループの数）を、初期化された乱数生成系列の数以下とすることができる。
【００５８】
なお、並列度の決定方法はこの方法に限定されず、ＣＰＵ１０１のコア数、ＧＰＵコア２０１・２０２の数、又はこれらの組み合わせに従って、実施例１と同様に決定してもよい。例えば、エントロピーのビット数を、生成しようとする鍵ペアに応じたビット数で割ることによって得られた値が並列度の上限となるように、並列度を適宜決定してもよい。また、ＣＰＵ１０１のコア数又はＧＰＵコア２０１・２０２の数に応じた値が並列度の下限となるように、並列度を決定してもよい。
【００５９】
ステップＳ５０２でＣＰＵ１０１は、実施例１と同様に、並列度と同数の疑似乱数系列を初期化する。また、鍵ペア生成が完了して利用が終わった疑似乱数系列を削除する。ステップＳ５０３でＣＰＵ１０１は、実施例１と同様に、ＧＰＵコア２０１・２０２を並列度と同数のグループに分け、それぞれのグループに別々の疑似乱数系列を対応付ける。
【００６０】
ステップＳ５０４でＣＰＵ１０１は、実施例１と同様に、ステップＳ５０２で初期化した疑似乱数系列のそれぞれを用いて乱数を生成する。ステップＳ５０５でＧＰＵコアのグループのそれぞれは、実施例１と同様に、対応づけられた疑似乱数系列が生成した疑似乱数が素数であるか否かを判定する。ステップＳ５０６でＣＰＵ１０１は、実施例１と同様に、生成した素数を用いて鍵ペアを生成する。実施例１と同様に、ステップＳ５０６は省略されてもよい。
【００６１】
実施例１のステップＳ２０５においてそれぞれのＧＰＵコア２０１・２０２は、ＣＰＵ１０１から、乱数を分割することによって得られた数値を繰り返し取得した。しかしながら本実施例のステップＳ５０５においてそれぞれのＧＰＵコア２０１・２０２は、ＣＰＵ１０１から、乱数を分割することによって得られた数値を１回だけ取得してもよい。またステップＳ５０５においてそれぞれのＧＰＵコア２０１・２０２は、対応付けられた擬似乱数系列を用いて生成された乱数を分割することによって得られた数値のうち、まだＧＰＵコアに入力されていない数値がなくなるまで、数値を取得してもよい。
【００６２】
ステップＳ５０７でＣＰＵ１０１は、所望の数の鍵ペア（又は素数）が生成されたか否かを判定する。所望の数の鍵ペアが生成されている場合、処理は終了する。所望の数の鍵ペアが生成されていない場合、処理はステップＳ５０８に進む。
【００６３】
ステップＳ５０８でＣＰＵ１０１は並列度を更新する。ＣＰＵ１０１は、ステップＳ５０１と同様に並列度を更新することができる。その後、処理はステップＳ５０２に戻る。以上のようにして、所望の数の素数又は鍵ペアを生成することができる。
【００６４】
本実施例ではステップＳ５０８において並列度が更新されたが、並列度の更新は図５のフローチャートとは独立に行われてもよい。例えば、所定の時間間隔で並列度の更新が行われてもよい。また、いずれかのＧＰＵコア２０１・２０２が、取得した数値が素数であると判定した際に、並列度の更新が行われてもよい。この場合、生成する残りの素数の数に従ってＧＰＵコアのグループ分けを変更（再決定）することができる。すなわち、生成する残りの素数の数以下となるように並列度を決定することができる。生成する残りの素数の数は、生成しようとする素数の総数と、ＧＰＵコア２０１・２０２のいずれかが既に出力した素数の数との差として求めることができ、並列度をこの差以下となるように決定すればよい。生成しようとする素数の総数は、例えば、入力部６８０がユーザ入力を介して取得することができる。
【００６５】
本実施例においては、ステップＳ５０８において並列度を更新した後で、ステップＳ５０３において再びＧＰＵコアのグループ分けを行う。ステップＳ５０３においてＣＰＵ１０１は、素数が発見された疑似乱数系列に対応するグループ（着目判定グループ）に属するＧＰＵコア２０１・２０２のみを、グループ分けの対象としてもよい。すなわち、着目判定グループに属するＧＰＵコアを、着目判定グループ以外のグループのいずれかに所属されてもよい。一方でＣＰＵ１０１は、全てのＧＰＵコア２０１・２０２をグループ分けの対象としてもよい。
【００６６】
素数が発見された疑似乱数系列に対応するグループに属するＧＰＵコア２０１・２０２だけをグループ分けの対象とする場合は、再割り当てするＧＰＵコア２０１・２０２が限定されるので、各グループのトータル処理能力を均一化することが困難になる。一方で、現在処理中のＧＰＵコア２０１・２０２と独立してグループ化処理ができるので、ＧＰＵコアの制御を容易に行うことができる。後者のように全てのＧＰＵコア２０１・２０２をグループ分けの対象とする場合は、各グループのトータル処理能力を均一化することは容易となる。しかしながら、現在処理中のＧＰＵコア２０１・２０２を同期しなければいけないため、ＧＰＵコアの制御が複雑になる。
【００６７】
ステップＳ５０２からＳ５０７は、シーケンシャルに実行されてもよい。しかしながら、これらは並列に実行されてもよい。並列処理は、例えば以下のように実現できる。すなわち、主メモリ１０５又はビデオメモリ１０４に、それぞれの疑似乱数系列を用いて生成した疑似乱数を一時的に保持する領域を設ける（乱数プール）。同様に、主メモリ１０５又はビデオメモリ１０４に、それぞれの疑似乱数系列を用いて生成した素数を一時的に保持する領域を設ける（素数プール）。
【００６８】
ステップＳ５０４においてＣＰＵ１０１は、他のステップとは非同期に、それぞれの擬似乱数系列についての疑似乱数を生成して乱数プールに書き込む。ステップＳ５０５においてそれぞれのＧＰＵグループに属するＧＰＵコア２０１・２０２は、他のステップとは非同期に、対応する擬似乱数系列を用いて生成された疑似乱数が乱数プールに保持されているか否かを判定する。対応する擬似乱数が保持されている場合には、ＧＰＵコア２０１・２０２は対応する疑似乱数の少なくとも一部を読み出し、素数判定を行う。そしてＧＰＵコア２０１・２０２は、素数であると判定された数値を素数プールに書き込む。ステップ５０６においてＣＰＵ１０１は、他のステップとは非同期に、素数プールに素数が保持されているか否かを判定する。素数プールに素数が保持されている場合には、ＣＰＵ１０１は素数プールから素数を読み出し、鍵ペアを生成する。
【００６９】
並列実行時におけるステップＳ５０２及びＳ５０３では、他の並列処理で利用中の疑似乱数系列やＧＰＵコア２０１・２０２を除外して処理を実施してもよい。すなわち、ステップＳ５０２においては、前のサイクルにおいて既に初期化されており、まだ素数が発見されていない擬似乱数系列については、初期化を行わなくてもよい。この場合ステップＳ５０８においては、続くステップＳ５０２で初期化する必要のない擬似乱数系列の数と、エントロピーのビット数を、生成しようとする鍵ペアに応じたビット数で割ることによって得られる値との和を、並列度の上限としてもよい。
【００７０】
以上説明したように、本実施例によれば、ＣＰＵ１０１で疑似乱数を生成し、ＧＰＵ１０３で疑似乱数を素数判定することによって、素数を生成することができる。特に、取得可能なエントロピーのビット数及び鍵ペアのビット数などに応じて、並列に生成する鍵ペアの数を動的に変更することにより、一様性が高く、予測困難性が低い素数を効率的に生成することができる。
【００７１】
また、実施例１の場合、ＧＰＵコア２０１・２０２のグループ分けは固定されている。したがって、処理が完了したグループに属するＧＰＵコア２０１・２０２はスリープしてしまう。一方、本実施例では、全ての処理が完了するまでＧＰＵコア２０１・２０２のグループ分けを変更する。したがって、処理が完了したグループに属するＧＰＵコア２０１・２０２をさらなる素数判定処理に用いることができる。このように実施例２によれば、より効率的に素数を生成することができる。
【００７２】
（他の実施形態）
本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体などとしての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに本発明を適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【００７３】
このプログラムの形態は、オブジェクトコード、インタプリタにより実行されるプログラム、ＯＳに供給するスクリプトデータなど、様々な形態をとることができる。プログラムを供給するための記憶媒体としては、例えばフレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、及びＤＶＤなどを用いることができる。
【００７４】
また、クライアントコンピュータのブラウザを用いてインターネットのホームページに接続し、プログラムをハードディスクなどの記憶媒体にダウンロードすることによっても、プログラムを供給することができる。自動インストール機能を含む圧縮されたファイルをハードディスクなどの記憶媒体にダウンロードすることによっても、プログラムを供給できる。また、本発明のプログラムを構成するプログラムコードを複数のファイルに分割し、それぞれのファイルを異なるホームページからダウンロードすることによっても、プログラムを供給できる。つまり、プログラムファイルを複数のユーザに対してダウンロードさせるＷＷＷサーバやＦＴＰサーバなども、本発明の範囲に含まれる。
【００７５】
プログラムを暗号化し、ＣＤ−ＲＯＭなどの記憶媒体に格納してユーザに配布することもできる。さらに、所定の条件をクリアしたユーザに対し、インターネットを介してホームページから暗号化を解く鍵情報をダウンロードさせることもできる。ユーザはこの鍵情報を使用することにより、暗号化されたプログラムを復号してコンピュータにインストールすることもできる。
【００７６】
また、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などに処理の一部又は全部を行わせ、その処理によって前述した実施例の機能が実現されるプログラムも、本発明の範囲に含まれる。さらには、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれたプログラムコードに従って、この機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが、処理の一部又は全部を行ってもよい。
【００７７】
本発明は上記実施例に限定されるものではなく、本発明の趣旨に基づき種々の変形（各実施例の有機的な組合せを含む）が可能であり、それらを本発明の範囲から排除するものではない。本発明の様々な例と実施例を示して説明したが、当業者であれば、本発明の趣旨と範囲は、本明細書内の特定の説明に限定されないことを理解するだろう。なお、上述した実施例の各変形例を組み合わせた構成も全て本発明に含まれる。
【００７８】
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）をネットワーク又は各種記憶媒体を介してシステム或いは装置に供給する。そして、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵなど）がプログラムコードを読み出して実行する。この場合、そのプログラム、及び該プログラムを記憶した記憶媒体は本発明を構成することになる。
【特許請求の範囲】
【請求項１】
所定ビット数の素数を並列に複数生成する情報処理装置であって、
入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段と、
複数の乱数シードを取得し、１以上の前記判定手段が所属するそれぞれの判定グループに当該複数の乱数シードの何れかを対応付ける対応付け手段と、
前記乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する制御手段と、を備え、
前記制御手段は、
着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する初期化手段と、
前記乱数生成系列を用いて乱数を生成する乱数生成手段と、
前記乱数のビット列を前記所定ビット数のビット列へと分割する分割手段と、
前記分割によって得られたそれぞれのビット列が示す数値を、前記着目乱数シードに対応付けられた前記判定グループを構成する前記判定手段の何れかへと出力する出力手段と、を備える
ことを特徴とする情報処理装置。
【請求項２】
生成しようとする素数の数を示す入力を受け付ける入力手段と、
前記生成しようとする素数の数と、前記判定手段のいずれかが既に出力した素数の数との差以下となるように前記判定グループの数を定め、前記判定手段のそれぞれについて所属する前記判定グループを決定する分配手段と、
を備えることを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記分配手段は、いずれかの前記判定手段が素数を出力した際に、前記判定グループの数を再び定め、前記判定手段のそれぞれについて所属する前記判定グループを再決定することを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記分配手段は、着目判定グループに属する前記判定手段が素数を出力した際に、前記生成しようとする素数の数と、前記判定手段のいずれかが既に出力した素数の数との差が、前記判定グループの数よりも多い場合、当該着目判定グループに属する前記判定手段のそれぞれを、当該着目判定グループ以外の判定グループのいずれかに所属させることを特徴とする、請求項３に記載の情報処理装置。
【請求項５】
前記分配手段は、前記判定グループの数が、初期化された前記乱数生成系列の数以下となるように、前記判定グループの数を定めることを特徴とする、請求項２乃至４の何れか１項に記載の情報処理装置。
【請求項６】
前記判定手段が出力した素数を用いて鍵ペアを生成する鍵生成手段をさらに備えることを特徴とする、請求項１乃至５の何れか１項に記載の情報処理装置。
【請求項７】
所定ビット数の素数を並列に複数生成する情報処理装置が行う情報処理方法であって、
前記情報処理装置は、入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段を備え、
前記情報処理方法は、
複数の乱数シードを取得し、１以上の前記判定手段が所属するそれぞれの判定グループに当該複数の乱数シードの何れかを対応付ける対応付け工程と、
前記乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する制御工程と、を含み、
前記制御工程は、
着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する初期化工程と、
前記乱数生成系列を用いて乱数を生成する乱数生成工程と、
前記乱数のビット列を前記所定ビット数のビット列へと分割する分割工程と、
前記分割によって得られたそれぞれのビット列が示す数値を、前記着目乱数シードに対応付けられた前記判定グループを構成する前記判定手段の何れかへと出力する出力工程と、を含む
ことを特徴とする情報処理方法。
【請求項８】
コンピュータを、請求項１乃至６の何れか１項に記載の情報処理装置の各手段として機能させるための、コンピュータプログラム。
【請求項１】
所定ビット数の素数を並列に複数生成する情報処理装置であって、
入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段と、
複数の乱数シードを取得し、１以上の前記判定手段が所属するそれぞれの判定グループに当該複数の乱数シードの何れかを対応付ける対応付け手段と、
前記乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する制御手段と、を備え、
前記制御手段は、
着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する初期化手段と、
前記乱数生成系列を用いて乱数を生成する乱数生成手段と、
前記乱数のビット列を前記所定ビット数のビット列へと分割する分割手段と、
前記分割によって得られたそれぞれのビット列が示す数値を、前記着目乱数シードに対応付けられた前記判定グループを構成する前記判定手段の何れかへと出力する出力手段と、を備える
ことを特徴とする情報処理装置。
【請求項２】
生成しようとする素数の数を示す入力を受け付ける入力手段と、
前記生成しようとする素数の数と、前記判定手段のいずれかが既に出力した素数の数との差以下となるように前記判定グループの数を定め、前記判定手段のそれぞれについて所属する前記判定グループを決定する分配手段と、
を備えることを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記分配手段は、いずれかの前記判定手段が素数を出力した際に、前記判定グループの数を再び定め、前記判定手段のそれぞれについて所属する前記判定グループを再決定することを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記分配手段は、着目判定グループに属する前記判定手段が素数を出力した際に、前記生成しようとする素数の数と、前記判定手段のいずれかが既に出力した素数の数との差が、前記判定グループの数よりも多い場合、当該着目判定グループに属する前記判定手段のそれぞれを、当該着目判定グループ以外の判定グループのいずれかに所属させることを特徴とする、請求項３に記載の情報処理装置。
【請求項５】
前記分配手段は、前記判定グループの数が、初期化された前記乱数生成系列の数以下となるように、前記判定グループの数を定めることを特徴とする、請求項２乃至４の何れか１項に記載の情報処理装置。
【請求項６】
前記判定手段が出力した素数を用いて鍵ペアを生成する鍵生成手段をさらに備えることを特徴とする、請求項１乃至５の何れか１項に記載の情報処理装置。
【請求項７】
所定ビット数の素数を並列に複数生成する情報処理装置が行う情報処理方法であって、
前記情報処理装置は、入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段を備え、
前記情報処理方法は、
複数の乱数シードを取得し、１以上の前記判定手段が所属するそれぞれの判定グループに当該複数の乱数シードの何れかを対応付ける対応付け工程と、
前記乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する制御工程と、を含み、
前記制御工程は、
着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する初期化工程と、
前記乱数生成系列を用いて乱数を生成する乱数生成工程と、
前記乱数のビット列を前記所定ビット数のビット列へと分割する分割工程と、
前記分割によって得られたそれぞれのビット列が示す数値を、前記着目乱数シードに対応付けられた前記判定グループを構成する前記判定手段の何れかへと出力する出力工程と、を含む
ことを特徴とする情報処理方法。
【請求項８】
コンピュータを、請求項１乃至６の何れか１項に記載の情報処理装置の各手段として機能させるための、コンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１３−３７２９１（Ｐ２０１３−３７２９１Ａ）
【公開日】平成２５年２月２１日（２０１３．２．２１）
【国際特許分類】
【出願番号】特願２０１１−１７５２９１（Ｐ２０１１−１７５２９１）
【出願日】平成２３年８月１０日（２０１１．８．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２５年２月２１日（２０１３．２．２１）
【国際特許分類】
【出願日】平成２３年８月１０日（２０１１．８．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]