(57)【要約】  本発明は、素数を生成し、それを暗号アプリケーションにおいて使用するための方法に関し：ａ）少なくとも１つの２進数である基数Ｂを決定し、Ｂは小さいサイズｂ＝ｌｏｇ２（Ｂ）ビットを有し、および、各決定された基数Ｂについて、ｉを整数として、少なくとも１つの小さい素数ｐｉを、Ｂ  ｍｏｄ  ｐｉ＝１であるように、決定するステップと、ｂ）素数候補ＹＰを選択するステップと、ｃ）選択された素数候補ＹＰを、前記決定された２進数である基数の中から選択された基数Ｂで分解：ＹＰ＝ΣｙｊＢｉ  するステップと、ｄ）前記選択された基数について、ｙＰＢ＝Σｙｊのように、候補ＹＰから剰余ｙＰＢを算出するステップと、ｅ）前記算出された剰余ｙＰＢが、前記選択された基数Ｂについて前記決定された小さい素数の中から選択された１つの小さい素数ｐｉで、割り切れるか否かをテストするステップと、ｆ）前記算出された剰余ｙＰＢが、前記選択された小さい素数で割り切れない間、ステップｅ）にて遂行されるテストが、前記選択された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、前記算出された剰余ｙＰＢが割り切れないことを証明するまで、上記のステップｅ）を反復的に繰り返すステップと、ｇ）前記選択された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、前記算出された剰余ｙＰＢが割り切れないとき、前記決定された２進数である基数のうちの各基数Ｂについて、ステップｃ）からｆ）を反復的に繰り返すステップと、ｈ）全ての決定された基数Ｂについて、前記決定された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、決定された基数について算出された前記剰余ｙＰＢが割り切れないとき、前記候補ＹＰに、既知の厳密な確率的素数判定法を実行し、既知の厳密な確率的素数判定法が成功したとき、前記素数候補ＹＰを記憶し、前記記憶された素数候補ＹＰを前記暗号アプリケーションにおいて使用する、ステップとを含む。
2020509407.tif 000002
【特許請求の範囲】
【請求項１】
素数を生成し、それを暗号アプリケーションにおいて使用するための方法であって、
ａ）少なくとも１つのハードウェアプロセッサ（４）と、テスト素数性回路（３）と、メモリ回路（５）とを備える処理システム（２）を介して、少なくとも１つの２進数である基数Ｂを決定し、Ｂは小さいサイズｂ＝ｌｏｇ２（Ｂ）ビットを有し、および、各決定された基数Ｂについて、ｉを整数として、少なくとも１つの小さい素数ｐｉを、Ｂ  ｍｏｄ  ｐｉ＝１であるように、決定するステップと、
ｂ）前記ハードウェアプロセッサ（４）を介して、素数候補ＹＰを選択するステップと、
ｃ）前記ハードウェアプロセッサを介して、選択された素数候補ＹＰを、前記決定された２進数である基数の中から選択された基数ＢでＹＰ＝ΣｙｊＢｉと分解するステップと、
ｄ）前記ハードウェアプロセッサを介して、前記選択された基数Ｂについて、ｙＰＢ＝Σｙｊのように、候補ＹＰから剰余ｙＰＢを算出するステップと、
ｅ）前記テスト素数性回路（３）を介して、前記算出された剰余ｙＰＢが、前記選択された基数Ｂについて前記決定された小さい素数の中から選択された１つの小さい素数ｐｉで、割り切れるか否かをテストするステップと、
ｆ）前記算出された剰余ｙＰＢが、前記選択された小さい素数で割り切れない間、ステップｅ）にて遂行されるテストが、前記選択された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、前記算出された剰余ｙＰＢが割り切れないことを証明するまで、前記テスト素数性回路を介して、上記のステップｅ）を反復的に繰り返すステップと、
ｇ）ステップｅ）にて遂行されるテストが、前記選択された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、前記算出された剰余ｙＰＢが割り切れないことを証明したとき、前記決定された２進数である基数のうちの各基数Ｂについて、ステップｃ）からｆ）を反復的に繰り返すステップと、
ｈ）全ての決定された基数Ｂについて、ステップｅ）にて遂行されるテストが、前記決定された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、決定された基数について算出された前記剰余ｙＰＢが割り切れないことを証明したとき、前記テスト素数性回路を介して、前記候補ＹＰに、既知の厳密な確率的素数判定法を実行し、既知の厳密な確率的素数判定法が成功したとき、前記素数候補ＹＰを前記メモリ回路（５）に記憶し、暗号プロセッサ（６）を介して、前記記憶された素数候補ＹＰを前記暗号アプリケーションにおいて使用する、ステップと、
を含む方法。
【請求項２】
−  ステップｆ）において、前記算出された剰余ｙＰＢが、前記選択された小さい素数で割り切れるとき、前記算出された剰余ｙＰＢが割り切れることが、前記選択された基数Ｂについて前記決定された小さい素数全てに対してテストされるまで、前記テスト素数性回路を介して、上記のステップｅ）を反復的に繰り返すステップと、
−  ステップｇ）において、前記算出された剰余ｙＰＢが、前記選択された基数Ｂについて前記決定された小さい素数のうちの１つで割り切れ、前記算出された剰余ｙＰＢが割り切れることが、前記選択された基数Ｂについて前記決定された小さい素数全てに対してテストされたとき、前記決定された２進数である基数のうちの各基数Ｂについて、ステップｃ）からｆ）を反復的に繰り返すステップと、
を含む、請求項１に記載の方法。
【請求項３】
ｉ）前記算出された剰余ｙＰＢが、選択された小さい素数で割り切れるとき、または、既知の厳密な確率的素数判定法が失敗したとき、前記既知の厳密な確率的素数判定法が成功するまで、新しい素数候補について、ステップｄ）からｈ）を反復的に繰り返すステップであって、新しい素数候補ＹＰおよび選択された基数Ｂについて、前記剰余ｙＰＢが、別の素数候補および前記選択された基数Ｂについて以前に算出された剰余を、所定の増分でインクリメントすることにより算出される、ステップを含む、請求項１に記載の方法。
【請求項４】
前記記憶された素数候補ＹＰを前記暗号アプリケーションにおいて使用するステップは、前記暗号プロセッサ（６）を介して、前記暗号アプリケーションを実行して、前記記憶された素数候補ＹＰを使用してデータをセキュアにするステップ、および／または、前記暗号プロセッサを介して、前記記憶された素数候補ＹＰを使用して、暗号キーを生成するステップ、のうちの少なくとも１つを含む、請求項１に記載の方法。
【請求項５】
剰余算出の合計算出が、ランダムな順番で遂行される、請求項１に記載の方法。
【請求項６】
前記基数が、異なる決定された小さい素数の数が最大になるように決定される、請求項１に記載の方法。
【請求項７】
前記基数が、処理システムのワードサイズに基づき決定される、請求項１に記載の方法。
【請求項８】
前記算出された剰余ｙＰＢが１つの小さい素数ｐｉで割り切れるか否かをテストするステップが、バレットのモジュラリダクションを使用して遂行される、請求項１に記載の方法。
【請求項９】
決定された基数Ｂについて、前記決定された小さい素数ｐｉが、Ｂ  ｍｏｄ  ｐｉ＝１であるような、３と５４１との間の全ての素数を含む、請求項１に記載の方法。
【請求項１０】
前記決定された２進数である基数が、１６、２４、２８、３２、３６、４４、４８、５２、６０、６４のうちのサイズを持つ、請求項１に記載の方法。
【請求項１１】
前記既知の厳密な確率的素数判定法が、ミラーラビンテストまたはフェルマーテストを含む、請求項１に記載の方法。
【請求項１２】
少なくとも１つのコンピュータのメモリに直接ロード可能なコンピュータプログラム製品であって、前記製品がコンピュータ上で起動されたとき、請求項１に記載の方法のステップを遂行するための、ソフトウェアコード命令を含む、コンピュータプログラム製品。
【請求項１３】
処理システム（２）と暗号プロセッサ（６）とを備える暗号装置（１）によって実行されたとき、請求項１に記載の方法を遂行する、実行可能なコンピュータコードを記憶する、非一時的コンピュータ可読媒体。
【請求項１４】
暗号装置（１）であって、
−  少なくとも１つのハードウェアプロセッサ（４）と、テスト素数性回路（３）と、前記素数候補ＹＰを記憶するように構成されたメモリ回路（５）とを有する処理システム（２）と、
−  暗号プロセッサ（６）とを備え、
前記処理システム（２）および暗号プロセッサ（６）が、請求項１に記載の方法のステップを実行するように構成される、暗号装置（１）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号アプリケーションのための素数生成の分野、および関連する暗号装置の分野に関し、より詳細には、いずれのＧＣＤ計算も必要としない、互いに素の性質のテストを使用する、高速の素数生成に関する。
【背景技術】
【０００２】
暗号化または暗号キー生成等の暗号アプリケーションは、素数に依存することが多い。そのため、そのような暗号アプリケーションを遂行する、スマートカードのようなセキュアデバイス等の装置は、素数を生成しなければならず、これは、そのような装置に埋め込まれた最も資源を消費する演算の一つである。候補の数字の素数性は、ミラーラビンテスト等の厳密な確率的素数判定法（ｒｉｇｏｒｏｕｓ  ｐｒｏｂａｂｌｅ  ｐｒｉｍａｌｉｔｙ  ｔｅｓｔ）を使用して、テストされることが多い。そのようなテストは非常にコストがかかるため、候補は、それらの互いに素の性質を、わずかな既知の小さい素数を用いてテストすることによって、事前に除去することができる。
【０００３】
そのような互いに素の性質のテストは、最大公約数（ＧＣＤ）計算に基づくことが多い。それにもかかわらず、そのようなＧＣＤ計算は、それ自体が、特に、限られた処理能力の装置、および／または高速な除算器を持たないＣＰＵについては、相当コストがかかり得る。暗号アプリケーションの枠組みにおけるＧＣＤ計算は、セキュリティ上のリスクを誘発することがあり、何故なら、ＧＣＤ計算の漏出が、ＲＳＡプライベートキー等の秘密鍵を取得するために悪用され得るからである。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
そのため、ＧＣＤ計算を必要とせずに、セキュアに、限られた処理能力要件で、素数を生成することができる暗号アプリケーション、および関連する装置が必要である。
【課題を解決するための手段】
【０００５】
この目的のために、第一の態様によると、本発明は、素数を生成し、それを暗号アプリケーションにおいて使用するための方法に関し：
ａ）少なくとも１つのハードウェアプロセッサと、テスト素数性回路（ｔｅｓｔ  ｐｒｉｍａｌｉｔｙ  ｃｉｒｃｕｉｔ）と、メモリ回路とを備える処理システムを介して、少なくとも１つの２進数である基数Ｂを決定し、Ｂは小さいサイズｂ＝ｌｏｇ２（Ｂ）ビットを有し、および、各決定された基数Ｂについて、ｉを整数として、少なくとも１つの小さい素数ｐｉを、Ｂ  ｍｏｄ  ｐｉ＝１であるように、決定するステップと、
ｂ）前記ハードウェアプロセッサを介して、素数候補ＹＰを選択するステップと、
ｃ）前記ハードウェアプロセッサを介して、選択された素数候補ＹＰを、前記決定された２進数である基数の中から選択された基数Ｂで分解：ＹＰ＝ΣｙｊＢｉ  するステップと、
ｄ）前記ハードウェアプロセッサを介して、前記選択された基数について、ｙＰＢ＝Σｙｊのように、候補ＹＰから剰余ｙＰＢを算出するステップと、
ｅ）前記テスト素数性回路を介して、前記算出された剰余ｙＰＢが、前記選択された基数Ｂについて前記決定された小さい素数の中から選択された１つの小さい素数ｐｉで、割り切れるか否かをテストするステップと、
ｆ）前記算出された剰余ｙＰＢが、前記選択された小さい素数で割り切れない間、ステップｅ）にて遂行されるテストが、前記選択された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、前記算出された剰余ｙＰＢが割り切れないことを証明するまで、前記テスト素数性回路を介して、上記のステップｅ）を反復的に繰り返すステップと、
ｇ）ステップｅ）にて遂行されるテストが、前記選択された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、前記算出された剰余ｙＰＢが割り切れないことを証明したとき、前記決定された２進数である基数のうちの各基数Ｂについて、ステップｃ）からｆ）を反復的に繰り返すステップと、
ｈ）全ての決定された基数Ｂについて、ステップｅ）にて遂行されるテストが、前記決定された基数Ｂについて前記決定された小さい素数のうちのいずれによっても、決定された基数について算出された前記剰余ｙＰＢが割り切れないことを証明したとき、前記テスト素数性回路を介して、前記候補ＹＰに、既知の厳密な確率的素数判定法を実行し、既知の厳密な確率的素数判定法が成功したとき、前記素数候補ＹＰを前記メモリ回路に記憶し、暗号プロセッサを介して、前記記憶された素数候補ＹＰを前記暗号アプリケーションにおいて使用する、ステップと、
を含む方法。
【０００６】
これが、候補の素数と複数の素数との互いに素の性質を、この候補の素数と複数の素数のいずれのＧＣＤも算出することなく、効率的にテストすることと；最終的に、素数をより低コストで決定して、そしてそれを暗号アプリケーションにおいて使用することとを可能にする。
【０００７】
第１の態様による方法は、
−  ステップｆ）において、前記算出された剰余ｙＰＢが、前記選択された小さい素数で割り切れるとき、前記算出された剰余ｙＰＢが割り切れることが、前記選択された基数Ｂについて前記決定された小さい素数全てに対してテストされるまで、前記テスト素数性回路を介して、上記のステップｅ）を反復的に繰り返すステップと、
−  ステップｇ）において、前記算出された剰余ｙＰＢが、前記選択された基数Ｂについて前記決定された小さい素数のうちの１つで割り切れ、前記算出された剰余ｙＰＢが割り切れることが、前記選択された基数Ｂについて前記決定された小さい素数全てに対してテストされたとき、前記決定された２進数である基数のうちの各基数Ｂについて、ステップｃ）からｆ）を反復的に繰り返すステップと、
を含んでもよい。
【０００８】
これが、候補の素数が素数であろうとなかろうと、それのテスト工程の実行時間を一定にすることを可能にする。
【０００９】
第１の態様による方法は、
ｉ）前記算出された剰余ｙＰＢが、選択された小さい素数で割り切れるとき、または、既知の厳密な確率的素数判定法が失敗したとき、前記既知の厳密な確率的素数判定法が成功するまで、新しい素数候補について、ステップｄ）からｈ）を反復的に繰り返すステップであって、新しい素数候補ＹＰおよび選択された基数Ｂについて、前記剰余ｙＰＢが、別の素数候補および前記選択された基数Ｂについて以前に算出された剰余を、所定の増分でインクリメントすることにより算出される、ステップを含んでもよい。
【００１０】
それは、候補の素数が破棄された後、最終的に素数が見つかるまで、新しい候補の素数をテストし続けることを可能にする。
【００１１】
前記記憶された素数候補ＹＰを前記暗号アプリケーションにおいて使用するステップは、前記暗号プロセッサを介して、前記暗号アプリケーションを実行して、前記記憶された素数候補ＹＰを使用してデータをセキュアにするステップ、および／または、前記暗号プロセッサを介して、前記記憶された素数候補ＹＰを使用して、暗号キーを生成するステップ、のうちの少なくとも１つを含んでもよい。
【００１２】
剰余算出の合計算出が、ランダムな順番で遂行されてもよい。
【００１３】
ランダムな順番を使用することが、テストすべき候補の素数に関して、情報が攻撃者に漏れることを防ぐことを可能にする。
【００１４】
前記基数が、異なる決定された小さい素数の数が最大になるように決定されてもよい。
【００１５】
それは、厳密な確率的素数判定法を遂行する前に、決定される基数の数、したがって、遂行すべき候補の素数の分解の回数、を増やすことなく、候補の素数が素数ではないことを検出する機会を最大にすることを可能にする。
【００１６】
前記基数が、処理システムのワードサイズに基づき決定されてもよい。
【００１７】
基数を決定するそのような手法は、方法のステップの実施の効率を向上させる。
【００１８】
前記算出された剰余ｙＰＢが１つの小さい素数ｐｉで割り切れるか否かをテストするステップが、バレットのモジュラリダクションを使用して遂行されてもよい。
【００１９】
そのようなリダクションは、乗算演算によるワード分割演算を置き換え、したがって、そのようなテストのコストを低減させる。
【００２０】
決定された基数Ｂについて、前記決定された小さい素数ｐｉが、Ｂ  ｍｏｄ  ｐｉ＝１であるような、３と５４１との間の全ての素数を含んでもよい。
【００２１】
決定された素数についてそのような小さい値を選択することが、素数候補が基数Ｂで分解されるときの素数候補ワードの合計が、決定された素数で割り切れるか否かをテストするコストを低くする。
【００２２】
前記決定された２進数である基数が、１６、２４、２８、３２、３６、４４、４８、５２、６０、６４のうちのサイズを持つことができる。
【００２３】
前記既知の厳密な確率的素数判定法が、ミラーラビンテストまたはフェルマーテストを含んでもよい。
【００２４】
第２の態様によると、本発明は、少なくとも１つのコンピュータのメモリに直接ロード可能なコンピュータプログラム製品であって、前記製品がコンピュータ上で起動されるとき第１の態様による方法のステップを遂行するための、ソフトウェアコード命令を含む、コンピュータプログラム製品に関する。
【００２５】
第３の態様によると、本発明は、処理システムと暗号プロセッサとを備える暗号装置によって実行されたとき第１の態様による方法を遂行する、実行可能なコンピュータコードを記憶する、非一時的コンピュータ可読媒体に関する。
【００２６】
第４の態様によると、本発明は、
−  少なくとも１つのハードウェアプロセッサと、テスト素数性回路と、前記素数候補ＹＰを記憶するように構成されたメモリ回路とを有する処理システム、ならびに、
−  暗号プロセッサを備え、
前記処理システムおよび暗号プロセッサが、第１の態様による方法のステップを実行するように構成される、暗号装置に関する。
【００２７】
上述の目的および関連する目的を達成するために、１つまたは複数の実施形態が、以下において十分に説明され、特許請求の範囲において特に指摘される特徴を備える。
【００２８】
以下の説明および添付の図面は、例示の態様を詳細に記載するものであり、本実施形態の原理が採用されてよい種々の方法のうちのいくつかを示す。他の利点および新規な特徴は、図面と併せて検討されることにより、以下の詳細な説明から明らかになり、開示される実施形態は、全てのそのような態様およびその等価物を含むことが意図される。
【図面の簡単な説明】
【００２９】
【図１】本発明の一実施形態に係る暗号装置の概略図である。
【図２】本発明の一実施形態に係る暗号アプリケーションにおける、素数を生成し、それを暗号アプリケーションにおいて使用するための方法を概略的に示す図である。
【発明を実施するための形態】
【００３０】
以下に詳細に示す説明では、本発明が実践されてもよい特定の実施形態を、例示として示す添付の図面を参照する。これらの実施形態は、当業者が本発明を実践することができるように、十分に詳細に説明されている。本発明の種々の実施形態が、異なってはいるが、必ずしも相互排他的ではない、ということを理解されたい。例えば、一実施形態に関連して本明細書に説明される特別な特徴、構造、または特性は、本発明の精神および範囲から逸脱することなく他の実施形態において実現されてもよい。加えて、開示される各実施形態における個々の要素の、設置または配置が、本発明の精神および範囲から逸脱することなく変形されてもよいことを、理解されたい。以下に詳細に示す説明は、したがって、制限するものとして考慮されるのでなく、本発明の範囲は、添付の請求項によってのみ、適切に解釈されて、請求項に権限があるあらゆる均等物と併せて、定義される。
【００３１】
以下の説明では、ｘ＾ｙおよびｘｙの形式の表記は、共にべき乗演算に使用される。
【００３２】
本発明は、いずれのＧＣＤ計算も用いない高速の素数生成を備えた、暗号アプリケーションのための方法および関連する暗号装置、を提供することを目的とする。
【００３３】
第１の態様によると、本発明は、図１に示すような暗号装置に関する。そのような暗号装置１は、素数を生成するように構成される処理システム２を備えることができる。処理システム２は、ここで以下に記載される方法に従い、既知の小さい素数を用いて、候補の素数の互いに素の性質をテストするテスト素数性回路３を備えてもよい。処理システム２はまた、前記方法において素数を生成するために必要な他の処理タスクを遂行するハードウェアプロセッサ４と、少なくとも生成された素数を記憶するメモリ回路５とを備える。
【００３４】
そのような暗号装置はまた、処理システム２によって生成される素数に基づく秘密鍵の生成等の暗号アプリケーションを遂行する暗号プロセッサ６を含んでもよい。
処理システム２のハードウェアプロセッサ４および暗号プロセッサ６は、別個のものであってもよいし、素数生成と暗号アプリケーションの両方に使用されるただ一つの共通のプロセッサであってもよい。
【００３５】
第２の態様によると、本発明は、そのような暗号装置１によって遂行される、素数を生成し、それを暗号アプリケーションにおいて使用する方法に関する。資源の消費が限定された状態で素数を生成するために、前記方法は、既存の方法で行うように、既知の小さい素数に対して、互いに素の性質のテストを使用する。しかし、そのような互いに素の性質のテストを遂行するためにＧＣＤを算出する代わりに、本発明に係る方法では、以下の段落で説明するように、いくつかの素数の特別な数学的な性質を利用する。
【００３６】
サイズがｂ＝ｌｏｇ２（Ｂ）の２進数である基数Ｂと、素数候補Ｙｐとを考える。素数候補ＹＰは、基数Ｂで、ＹＰ＝ΣｙｊＢｉ、と表すことができる。素数候補ＹＰと素数ｐｉの互いに素の性質を調べることは、ＹＰがｐｉで割り切れるか否かをテストすること、すなわち、ＹＰ  ｍｏｄ  ｐｉ＝０であるか否かをテストすることと等価である。
ＹＰ  ｍｏｄ  ｐｉは、以下の式を用いて異なる形式で表すこともできる：
ＹＰ  ｍｏｄ  ｐｉ＝（ΣｙｊＢｊ）ｍｏｄ  ｐｉ＝（Σｙｊ（Ｂ  ｍｏｄ  ｐｉ）ｊ）ｍｏｄ  ｐｉ
【００３７】
いくつかの２進数である基数について、Ｂ  ｍｏｄ  ｐｉ＝１であるような、１つ以上の素数ｐｉが存在することが分かる。その場合、ＹＰ  ｍｏｄ  ｐｉは、ＹＰ  ｍｏｄ  ｐｉ＝Σｙｊ  ｍｏｄ  ｐｉと表すこともできる。そのため、Ｂ  ｍｏｄ  ｐｉ＝１であるような素数ｐｉで、ＹＰが割り切れるか否かのテストは、ＹＰが基数Ｂで分解されるときのＹＰワードの合計をただ算出し、次に、その合計がそのような素数ｐｉで割り切れるか否かをテストすることによって、達成されうる。
【００３８】
その結果、ある２進数である基数について、Ｂ  ｍｏｄ  ｐｉ＝１という属性を実証した素数候補と素数の間の、互いに素の性質を、そのような合計の算出によって、前記素数候補と前記素数のＧＣＤを算出することによるよりも相当速く、テストすることができる。
【００３９】
そのような属性を利用して素数を生成して、暗号アプリケーションにおいて使用するために、本発明の第２の態様による方法は、以下に説明され、図２に示されるステップを含むことができる。
【００４０】
決定するステップａ）において、処理システム２が、少なくとも１つの２進数である基数Ｂであって、小さいサイズｂ＝ｌｏｇ２（Ｂ）ビットを有するＢを決定し、各決定された基数Ｂについて、ｉを整数として、少なくとも１つの小さい素数ｐｉをＢ  ｍｏｄ  ｐｉ＝１であるように、決定してもよい。
【００４１】
第１の実施形態において、決定するステップａ）の中で、処理システムは、種々の基数について、どの素数がＢ  ｍｏｄ  ｐｉ＝１を実証するのかを実証し、少なくとも１つの２進数である基数Ｂと、処理システムがＢ  ｍｏｄ  ｐｉ＝１であることを実証した少なくとも１つの小さい素数ｐｉとを選択するために計算を遂行することができる。
【００４２】
第２の実施形態において、そのような実証は、決定するステップａ）が遂行される前に、場合によっては処理システム２とは別のシステムにより、遂行されてもよく、基数Ｂおよび、Ｂ  ｍｏｄ  ｐｉ＝１であるような小さい素数ｐｉが、処理システム２のメモリ回路に記憶されてもよい。その場合、決定するステップａ）の中で、処理システムが、記憶された基数Ｂと、基数Ｂのそれぞれ１つに関連する小さい素数とをメモリ回路から単に読み込んでもよい。
【００４３】
上記に示したように、Ｂ  ｍｏｄ  ｐｉ＝１という属性のおかげで、素数候補と決定された素数のそれぞれとの互いに素の性質を、素数候補とそのような決定された素数のＧＣＤ計算のコストよりも相当低いコストで、素数候補が基数Ｂで分解されるときの素数候補ワードの合計をただ算出し、次に、この合計がそのような素数ｐｉで割り切れるか否かをテストすることにより決定することができる。
【００４４】
例示するように、決定された２進数である基数は、１６、２４、２８、３２、３６、４４、４８、５２、６０および６４のうちのサイズｂを有することができる。基数は、処理システムのワードサイズに基づき決定されてもよい。
【００４５】
一実施形態において、２進数である基数は、異なる決定された小さい素数の数が最大になるよう決定されてもよい。素数候補と、Ｂ  ｍｏｄ  ｐｉ＝１を実証する少なくとも１つの素数との互いに素の性質をテストする、基数Ｂの数を限定することが望ましい。そのようなテストは、実際には、素数候補を各基数Ｂで分解することが必要であり、なんらかのコストがかかる。残念ながら、異なる２進数である基数Ｂは、Ｂ  ｍｏｄ  ｐｉ＝１を実証する１つ以上の素数を共通に有する。そのため、所与の数の２進数である基数Ｂについて、素数候補となるべく多くの素数との互いに素の性質をテストできるために、２進数である基数Ｂは注意深く選択され、選択された基数についてＢ  ｍｏｄ  ｐｉ＝１を実証する決定された素数の数が最大になるようにする。
【００４６】
素数候補が素数で割り切れる可能性は、この素数が大きいほど低いので、候補の素数が最小の素数で割り切れることについて、最初にテストされる。一例として、決定された基数Ｂについて、前記決定された小さい素数ｐｉは、Ｂ  ｍｏｄ  ｐｉ＝１であるような１００個の最初の素数、すなわち、３と５４１との間の全ての素数を含むことができる。
【００４７】
別の例として、１６と３２との間であるサイズｂを有する前記決定された２進数である基数に関連する、決定された小さい素数は、以下の値：
−  ｂ＝  １６に対して、３、５、１７、２５７
−  ｂ＝１８に対して、３、７、１９、７３
−  ｂ＝２０に対して、３、５、１１、３１、４１
−  ｂ＝２１に対して、７、１２７、３３７
−  ｂ＝２２に対して、３、２３、８９、６８３
−  ｂ＝２３に対して、４７
−  ｂ＝２４に対して、３、５、７、１３、１７、２４１
−  ｂ＝２５に対して、３１、６０１、１８０１
−  ｂ＝２６に対して、３、２７３１
−  ｂ＝２７に対して、７、７３
−  ｂ＝２８に対して、３、５、２９、４３、１１３、１２７
−  ｂ＝２９に対して、２３３、１１０３、２０８９
−  ｂ＝３０に対して、３、７、１１、３１、１５１、３３１
−  ｂ＝３２に対して、３、５、１７、２５７
の中からであってもよい。
【００４８】
選択ステップｂ）において、処理システム２のハードウェアプロセッサ４は、素数候補ＹＰを選択してもよい。
【００４９】
分解ステップｃ）において、ハードウェアプロセッサは、前記決定された２進数である基数から選択された基数Ｂで、選択された素数候補ＹＰを分解：ＹＰ＝ΣｙｊＢｉ  してもよい。
【００５０】
そして、算出するステップｄ）において、ハードウェアプロセッサは、前記選択された基数Ｂについて、ｙＰＢ＝Σｙｊのように、候補ＹＰから剰余ｙＰＢを算出してもよい。この式で表されるように、そのような剰余は、選択された基数ＢでＹＰが分解されるときの、ＹＰワードの合計である。攻撃者へ情報が漏れるのを防ぐために、剰余算出の合計算出は、ランダムな順番で遂行される。
【００５１】
そして、テストするステップｅ）において、テスト素数性回路３は、前記算出された剰余ｙＰＢが、前記選択された基数Ｂについて前記決定された小さい素数の中から選択された１つの小さい素数ｐｉで、割り切れるか否かをテストする。選択された小さい素数ｐｉおよび選択された基数Ｂが、Ｂ  ｍｏｄ  ｐｉ＝１を実証するので、剰余に対するそのようなテストは、候補の素数ＹＰが、選択された小さい素数ｐｉと互いに素である否かをテストすることと等価である。
【００５２】
テストするステップｅ）の結果が、剰余ｙＰＢは、選択された小さい素数ｐｉで割り切れないということであるとき、候補の素数ＹＰが、選択された小さい素数ｐｉと互いに素であることを意味する。その場合、候補の素数ＹＰは、未だ有効な候補の素数であり、候補の素数ＹＰと基数Ｂについて選択された他の小さい素数との互いに素の性質が、テストされるべきである。
【００５３】
方法は、次に、第１の繰り返しステップｆ）を含んでもよく、その間、前記算出された剰余ｙＰＢが、前記選択された小さい素数で割り切れない間は、ステップｅ）にて遂行されるテストが、前記選択された基数Ｂについて、前記算出された剰余ｙＰＢが、前記決定された小さい素数のうちのいずれによっても割り切れないことを証明するまで、テスト素数性回路が上記のステップｅ）を反復的に繰り返してよい。そうすることによって、テストするステップｅ）の各繰り返しにおいて、算出された剰余ｙＰＢは、前記選択された基数Ｂについて前記決定された小さい素数の中から選択された新しい小さい素数ｐｉで割り切れることについて、テストされる。候補の素数ＹＰと、選択された基数Ｂについて決定された小さい素数ｐｉとの互いに素の性質は、候補の素数ＹＰが、決定された小さい素数のうちの１つで割り切れ、したがって素数ではないとわかるまで、または、候補の素数ＹＰが、基数Ｂについて選択された全ての小さい素数ｐｉと互いに素であるとわかるまで、こうして小さい素数について次々にテストされる。
【００５４】
ステップｅ）にて遂行されるテストが、前記算出された剰余ｙＰＢは、前記選択された基数Ｂについて前記決定された小さい素数のうちのいずれによっても割り切れないということを証明したとき、候補の素数ＹＰは、未だ有効な候補の素数であり、候補の素数ＹＰと、他の基数とＢ  ｍｏｄ  ｐｉ＝１を実証する他の小さい素数との互いに素の性質が、テストされるべきである。方法は次に、第２の繰り返しステップｇ）を含んでもよく、その間、ステップｃ）からｆ）が、前記決定された２進数である基数のうちの各基数Ｂについて、反復的に繰り返される。そうすることによって、分解ステップｃ）および算出するステップｄ）の各反復において、素数候補が、決定された２進数である基数のうちの新しい基数Ｂで分解され、その剰余が、新しい基数について算出される。そして、ステップｅ）およびｆ）が、候補の素数ＹＰと、新しい選択された基数Ｂについて決定された小さい素数ｐｉとの互いに素の性質を、小さい素数について次々に、テストすることを可能にする。
【００５５】
全ての決定された基数Ｂについて、ステップｅ）において繰り返し遂行されるテストが、決定された基数について算出された前記剰余ｙＰＢは、前記決定された基数について前記決定された小さい素数のうちのいずれによっても割り切れないことを証明したとき、候補の素数ＹＰは、全ての決定された基数について決定された全ての小さい素数と、互いに素である。方法は次に、実行ステップｈ）を含んでもよく、その間、テスト素数性回路が、前記候補ＹＰに、既知の厳密な確率的素数判定法を実行する。そのような厳密な確率的素数判定法は、例えば、ミラーラビンテストまたはフェルマーテストであってもよい。
【００５６】
既知の厳密な確率的素数判定法が成功したとき、実行ステップｈ）はまた、素数候補ＹＰを処理システム２のメモリ回路５に記憶するステップと、暗号プロセッサ６を介して、前記記憶された素数候補ＹＰを前記暗号アプリケーションにおいて使用するステップとを含んでもよい。
【００５７】
一例として、前記記憶された素数候補ＹＰを暗号アプリケーションにおいて使用するステップは、前記暗号プロセッサを介して、前記暗号アプリケーションを実行して、前記記憶された素数候補ＹＰを使用してデータをセキュアにするステップ、および／または、前記暗号プロセッサを介して、前記記憶された素数候補ＹＰを使用して、暗号キーを生成するステップ、のうちの少なくとも１つを含んでもよい。
【００５８】
上で説明されたステップａ）からｈ）では、このように、より少ないコストで、素数候補と前記小さい素数のＧＣＤを算出することなく、素数候補の複数の小さい素数に対して互いに素の性質を効率的にテストすることを可能にする。
【００５９】
テストするステップｅ）にて遂行される互いに素の性質のテストのコストをさらに下げるためには、前記算出された剰余ｙＰＢが、小さい素数ｐｉで割り切れるか否かをテストするステップは、バレットのモジュラリダクションを使用して遂行されてもよい。そのようなリダクションは、実際は、相当低いコストとなることが多い乗算演算により、ワード分割を置き換える。
【００６０】
テストするステップｅ）の反復のどこかで、算出された剰余ｙＰＢが、選択された小さい素数ｐｉで割り切れることがわかるかもしれない。実行ステップｈ）において、既知の厳密な確率的素数判定法が、失敗することもある。両方の場合において、テストされた素数候補は、実際に素数ではない。それで、新しい候補の素数をテストすることが望ましい。方法は、第３の繰り返しステップｉ）を含んでもよく、その間、ステップｄ）からｈ）が、前記既知の厳密な確率的素数判定法が成功するまで、新しい素数候補について反復的に繰り返される。そのような新しい素数候補について、決定された基数Ｂごとに、新しい素数候補の剰余が最終的には必要である。
【００６１】
第１の実施形態において、そのような剰余は、分解するステップｃ）のように、新しい素数候補を各基数で分解すること、および、上記で説明したように、各基数で表される新しい候補の素数のワードの合計を算出すること、によって算出されてもよい。
【００６２】
第２の実施形態において、新しい素数候補ＹＰおよび選択された基数Ｂについて、剰余ｙＰＢは、別の前の素数候補および前記選択された基数Ｂについて以前に算出された剰余を、所定の増分でインクリメントすることにより、算出されてもよい。そのような所定の増分は、前記選択された基数Ｂで表される、前の素数候補と新しい素数候補との差分のワードの合計と等しい。そうすることが、コストがかかり得る、新しい素数候補全体を分解することに代えて、小さいと考えられる２つの候補の素数の差分のみを、選択された基数Ｂで分解することにより、剰余を算出することを可能にする。
【００６３】
テストするステップｅ／において、算出された剰余ｙＰＢが、選択された小さい素数で割り切れるとわかったとき、素数候補は実際に素数ではない。第１の実施形態において、方法は、終了してもよいし、新しい候補の素数をテストするために上で説明された第３の繰り返しステップｉ／にジャンプしてもよい。これは、テストされた候補の素数が素数でないことを、実行時間をただ見ることにより、方法の実行を監視している攻撃者に分からせてしまう、という欠点がある。
【００６４】
したがって、第２の実施形態において、全ての決定された基数について決定された全ての小さい素数との互いに素の性質は、テストするステップｅ）にて遂行されるテストの結果がどうであろうと、テストされる。そうするために：
−  第１の繰り返しステップｆ）において、前記算出された剰余ｙＰＢが前記選択された小さい素数で割り切れるとき、前記算出された剰余ｙＰＢが割り切れることが、前記選択された基数Ｂについて前記決定された小さい素数全てに対してテストされるまで、テスト素数性回路は、上記のステップｅ）を反復的に繰り返してもよい。
−  前記算出された剰余ｙＰＢが、前記選択された基数Ｂについて前記決定された小さい素数のうちの１つで割り切れ、前記算出された剰余ｙＰＢが割り切れることが、前記選択された基数Ｂについて前記決定された小さい素数全てに対してテストされたとき、第２の繰り返しステップｇ）は、前記決定された２進数である基数のうちの各基数Ｂについて、ステップｃ）からｆ）を反復的に繰り返してもよい。
【００６５】
そうすることで、候補の素数の素数性がどうであろうと、ステップｅ）からｇ）の一定の実行時間を有することができる。
【００６６】
別の態様によると、本発明は、少なくとも１つのコンピュータのメモリに直接ロード可能なコンピュータプログラム製品に関し、それは、前記製品がコンピュータ上で起動されたとき、本明細書にて上で説明されたステップａ）からｈ）を遂行するための、ソフトウェアコード命令を含む。
【００６７】
別の態様によると、本発明は、処理システムと暗号プロセッサとを備えるコンピューティングシステムによって実行されたとき、本明細書にて上で説明されたステップａ）からｈ）を遂行する、実行可能なコンピュータコードを記憶する、非一時的コンピュータ可読媒体に関する。
【図１】
2020509407.tif 000003
【図２】
2020509407.tif 000004
【国際調査報告】
2020509407.tif 000005
2020509407.tif 000006
2020509407.tif 000007