暗号計算を実行するための方法及び装置
本発明は、電子装置における特定の暗号アルゴリズムのための鍵を生成する方法に関し、電子装置に素数Ｐを格納し、少なくとも一つの秘密の素数を生成する。第１のステップ（ａ）では、和が数ｐ’に等しい二つの整数ｐ１’及びｐ２’を無作為に選択する（１１）。第２のステップ（ｂ）では、前記数ｐ’の秘密を維持するために、格納された素数Ｐと数ｐ１’及びｐ２’との組合せに基づき、数ｐ’が素数であるかどうかを判定する（１２）。第３のステップ（ｃ）では、もし数ｐ’が素数であると判定されれば、数ｐ１’及びｐ２’を電子装置に格納し（１４）、そうでなければ、ステップ（ａ）と（ｂ）を繰り返す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化(cryptography)の分野に関し、更に詳しくは、暗号アルゴリズムにより使用される鍵(keys)の秘密性の保護に関する。
【背景技術】
【０００２】
暗号アルゴリズムは、とりわけ、データを暗号化(encrypt)することを可能にし、及び／又は、データを復号化(decrypt)することを可能にする。また、このようなアルゴリズムを他の多くのアプリケーションに使用することも可能である。具体的には、それらは、署名(sign)するのに役立ち、あるいは、或る情報を認証するのに役立つ。また、それらは、タイムスタンプ(time-stamping)の分野においても有用である。
【０００３】
一般に、このようなアルゴリズムは、多数のオペレーションの文字列(string)または計算(calculations)から構成され、これらは、暗号化されたデータアイテムを得るために、暗号化されるべきデータアイテムに対して連続的に適用され、あるいは、復号化されたデータアイテムを得るために、暗号化されたデータアイテムに対して連続的に適用される。
【０００４】
これらのアルゴリズムのうち、或るものは秘密鍵を使用することに基づいており、一方、他のものは公開鍵と秘密鍵の混用に基づいている。
【０００５】
一例として、次の章では、データ暗号化及び復号化に対するこれらのアルゴリズムの適用を説明する。
【０００６】
このような適用における公開鍵暗号アルゴリズムの一般原理によれば、公開鍵は全てに対してアクセス可能であり、誰でも公開鍵を用いて暗号化されたデータを発送することができるが、対応する秘密鍵の保持者でなければ、これらのデータを復号化することはできない。
【０００７】
公開鍵暗号アルゴリズムのセキュリティは、公開鍵を知っていても対応する秘密鍵を取り出すことができず、故にデータを復号化することができないという事に依存している。
【０００８】
従って、ＲＳＡと名づけられた公開鍵暗号化手法が知られており、ＲＳＡは、その考案者の名前であるRivert, Shamir, Adelmanを表す。この手法は、この技術分野において最も使用されているものであって最も古いもののうちの一つである。
【０００９】
この手法によれば、ｐ，ｑ，ｅ，ｄで表される４つの数が選択される。数ｐ及びｑは、明らかに異なる二つの素数である。これらは無作為に生成される。
【００１０】
数ｄ及びｅは次式を満足する。
e*d=1 modulo (p-1)(q-1)
【００１１】
そして、この技術分野の当業者に広く知られている演算により、ユークリッドアルゴリズムを用いて、ｅ，ｐ，ｑに基づきｄを生成することが可能である。
【００１２】
そして数ｐとｑとのプロダクト(product)から得られる数はｎ(モジュラス)と表される。
【００１３】
従って、数ｎ及びｅのペアは公開鍵を構成し、一方、数ｎ及びｄのペアは秘密鍵を構成する。
【００１４】
そして、０とｎ−１の間の範囲の整数Ｍに対応するデータアイテムを発送するために、発送されるべき対応するコード化された数Ｃが次式に従って計算される。
C = Me modulo n
【００１５】
上記コード化されたメッセージＣを受信すると、秘密鍵の保持者は、数Ｄの中間値を計算する。
D = Cd modulo n
【００１６】
そして、元の平分メッセージＭが、次式に従って再生される。
D = Mde = M modulo n
【００１７】
従って、上記により、このような公開鍵アルゴリズムは、素数の生成に基づいていることが知られている。より詳細には、ＲＳＡのような公開鍵アルゴリズムは、極めて大きな素数の生成を必要とする可能性がある。従って、ほぼ５００デジット(digits)から成る素数を生成する必要があるかもしれない。
【００１８】
ＲＳＡ型のアルゴリズムでは、モジュラスｎは公開鍵に属し、従って全てに知られ、一方、数ｄは、上記アルゴリズムのセキュリティを保証するために秘密のままでなければならない。しかし、数ｄは、数ｐ及びｑに基づいて得られる。従って、数ｐ及びｑが秘密のままであることは、このようなアルゴリズムのセキュリティにとって重要である。
【００１９】
一般に、電子カード(electronic card)の暗号化ソフトウェアについて、これらの鍵は、例えば暗号アルゴリズムが実行されるところの電子装置を製造中の工場のような、任意の攻撃から保護された環境で生成される。
【００２０】
従って、このような条件の下で、数ｐ及びｑは、これらの値を決定して上記アルゴリズムのセキュリティを破壊することを狙った攻撃に直面する如何なる危険も伴うことなく、簡単に操作されることができる。従って、通常、鍵を生成するためのこれら各種の方法は、これらの数ｐ及びｑの操作(manipulation)を含む。
【００２１】
このような条件の下で、素数を生成するのに当業者に知られた各種の方法を使用することが可能である。
【００２２】
しかしながら、或る適用については、暗号アルゴリズムの使用鍵の秘密性を破ることを狙った攻撃が可能な外部環境においてこのような鍵を生成する必要があるかもしれない。
【００２３】
今日では、多くのタイプの攻撃が知られている。
【００２４】
従って、或る攻撃は、或る暗号化ステップの実行中に検出される情報漏洩に基づいている。これらの攻撃は、一般に、データアイテムの暗号アルゴリズムによる処理中に検出される情報漏洩と鍵（単数または複数の鍵）との間の相関関係に基づいている（電流の消費、電磁気放射、計算時間などを分析することによる攻撃）。
【００２５】
このような条件の下で、以前に入力された数ｐ及びｑのセキュリティを保護するための適切な予防策を講じることは欠かせない。
【００２６】
数ｐ及びｑを生成するための手法であってこれらの数のセキュリティを保護することを可能にする手法が知られている。具体的には、Dan BonehとMatthew Franklinによって書かれた論文“Efficient Generation of Shared RSA keys”は、数ｐ及びｑを同時に且つ秘密に生成する方法を提案している。
【００２７】
この手法の目的の一つは、多数の参加者の間で共通の方法で素数を生成することである。従って、これらの参加者は、これら参加者が二つの素数を知ることなく生成することを可能にする演算を実行し、これらの数のプロダクト(product)のみが参加者に知られる。
【００２８】
この手法によれば、数ｐ及びｑは無作為且つ同時に選択される。そして、このように選択された二つの数が素数であるかどうかが、それらのプロダクトに基づいて判定される。上記数ｐ及びｑの秘密性を保護するために、これらの数は直接的には操作されない。
【００２９】
具体的に、更に正確に言えば、４つの整数ｐａ，ｐｂ，ｑａ，ｑｂが無作為に選択され、数ｐは数ｐａと数ｐｂの和の結果であり、数ｑは数ｑａと数ｑｂの和の結果である。
【００３０】
そして、数ｐ及びｑが素数であるかどうかが、数ｐａ，ｐｂ，ｑａ，ｑｂを操作することによるそれらのプロダクトに基づいて検証される。
【００３１】
数ｐ及びｑが素数ではない場合、選択された数ｐ及びｑが素数であると判定されるまで、他の二つの数ｐ及びｑの無作為の選択が繰り返される。
【００３２】
このような解決手法は、計算の観点から見て極めて複雑であり、且つ、鍵を生成するための方法の性能を大幅に低下させるかもしれない。
【発明の開示】
【発明が解決しようとする課題】
【００３３】
本発明は、これらの欠点を低減することを可能にする解決手法を提案することを目的とする。
【課題を解決するための手段】
【００３４】
本発明の第１の態様は、素数Ｐがメモリに格納されているところの電子装置における暗号アルゴリズムのための鍵を生成する方法を提案する。
【００３５】
本方法は、少なくとも一つの秘密の素数を生成するオペレーションを含み、このオペレーションは、次の連続的なステップ、すなわち、
/a/ 和が数ｐ’に等しい二つの整数ｐ１’及びｐ２’を無作為に選択するステップと、
/b/ 前記数ｐ’が素数であるかどうかを、前記数ｐ１’及びｐ２’とメモリに格納された前記素数Ｐとの組合せに基づいて判定するステップと、
/c/ もし、前記数ｐ’が素数であれば、前記数ｐ１’及びｐ２’を電子装置のメモリに格納し、前記数ｐ’が素数でなければ、ステップ/a/及び/b/を繰り返すステップと、
に従って実行される。
これらの処理により、素数ｐ’が秘密的かつ効率的に生成される。
【００３６】
詳細には、このように生成された数ｐ’は、本方法の各種ステップの過程で直接的に操作されず、整数ｐ１’及びｐ２’のみが操作される。従って、素数ｐ’を生成するステップの過程でアルゴリズム攻撃によって素数ｐ’の秘密性(secrecy)を破ることは可能でない。
【００３７】
また、この素数の生成は、多くの素数を連続的に生成することを可能にするので効率的である。しかし、論文“Efficient Generation of Shared RSA keys”で提案されているように、同時に多数の素数を無作為に選択することよりも、一つの素数を無作為に選択することの方が可能性として大きい。
【００３８】
本発明によるこのような方法は、電子装置における決められた暗号アルゴリズムが秘密の一つの素数の生成を必要とし、あるいは多くの秘密の素数の生成を必要とする場合に、このような暗号アルゴリズムのための鍵を生成する任意の方法に有利に適用されることができる。
【００３９】
ステップ/b/は、整数と素数との組合せに基づいて、この整数の素数性(primality)を判定することを可能にする任意のタイプの素数判定法(primality test)を実施することにより実行されることができる。
【００４０】
一般に、このような素数判定法は、確率的アルゴリズム(probabilistic algorithms)である。これは、数が素数であることを極めて高い確率で判定することを可能にする。
【００４１】
本発明の実施形態において、第１の整数ｐ１と第２の整数ｐ２は、メモリに格納された素数Ｐが第１の整数ｐ１と第２の整数ｐ２の和に等しくなるように決定される。そして、ステップ/b/は、数ｐ１，ｐ２，ｐ１’，ｐ２’に関して実行されるオペレーションに基づいて実施される。
【００４２】
従って、秘密の素数ｐ’の生成過程において、数ｐ’についての素数判定法の局面では、好ましくは、素数Ｐも数ｐ’も操作されず、これにより、この生成ステップの過程で数ｐ’の秘密性に対する潜在的な攻撃を無力にする。
【００４３】
第１の整数ｐ１及び第２の整数ｐ２は、無作為に決定され得る。
【００４４】
ステップ/b/は、ソロベイ・ストラッセン(Solovay-Strassen)型判定法とミラー・ラビン(Miller-Rabin)型判定法との組合せに基づく素数判定法を用いて実行されることができる。従って、例えば、素数判定法は、Dan BonehとMatthew Franklinによって書かれた論文‘Efficient Generation of Shared RSA keys’の第３章‘distributed primality test’に記載されているような素数判定法に基づくことができる。具体的には、この素数判定法は、一方ではソロベイ・ストラッセン素数判定法に基づくと共に、他方ではミラー・ラビン素数判定法に基づいている。ソロベイ・ストラッセン素数判定法は、R. SolovayとV. Strassenによる１９７７年の文書‘A fast monte carlo test for primality’に記載されている。ミラー・ラビン素数判定法は、M. Rabinによる１９８０年の文書‘Probabilistic algorithm for testing primality’に記載されている。
【００４５】
本発明の実施形態では、このような方法の性能は、ステップ/b/の前に、次のステップ、すなわち、
/a1/ 数ｐ１’及び数ｐ２’に関して実行されたオペレーションに基づき、数ｐ’が１又は２以上の決定された素数で割り切れないことを検証するステップ
を含むことにより強化される。
【００４６】
この場合、ステップ/a/及び/a1/は、数ｐ’が上記決定された素数の一つで割り切れれば、繰り返される。
【００４７】
このステップ/a1/は、大きな素数を生成したい場合にいっそう有益である。具体的には、このようなステップは、実行するにはいっそう扱いにくいステップ/b/を実行する前に、或る数を適正に簡単に除去することを可能にする。
【００４８】
本発明の実施形態では、ステップ/a1/は、厳密に１よりも大きな素数ｙについて、次のステップ、すなわち、
・ ０とｙ−１との間の範囲の整数の中から第１の整数ｃを無作為に選択し、１とｙ−１との間の範囲の整数の中から第２の整数ｄを無作為に選択するステップと、
・ 式u=c+dp1’ modulo yに従って数ｕを決定するステップと、
・ 式v=c-dp2’ modulo yに従って数ｖを決定するステップと、
・ ｐが、数ｕと数ｖとの差分の関数としてのｙによって割り切れないかどうかを判定するステップと
を含む。
【００４９】
或る暗号アルゴリズムは、多数の秘密の素数の生成を必要とする。この場合、素数を生成するために必要に応じて何度でも、本発明の実施形態による方法を適用することが容易に可能である。従って、一対の非対称の鍵の構築のために、ステップ/a/から/c/を繰り返すことにより、連続的に、少なくとも二つの素数を生成することが可能である。
【００５０】
本発明の第２の態様は、決定された暗号アルゴリズムのための鍵を生成するための電子装置を提案する。
【００５１】
本電子装置は、
・ 和が数ｐ’であるところの二つの整数ｐ１’及びｐ２’を無作為に選択するのに適した選択ユニットと、
・ 素数Ｐを格納すると共に、前記数ｐ１’及びｐ２’の和が素数であると判定された場合に前記数ｐ１’及びｐ２’を格納するためのメモリと、
・ メモリに格納された前記素数Ｐと前記数ｐ１’及びｐ２’との組合せに基づき、前記数ｐ’が素数であるかどうかを判定するのに適した判定ユニットと
を備えて構成される。
【００５２】
上記選択ユニットは、メモリに格納された素数Ｐが第１の整数ｐ１及び第２の整数ｐ２の和に等しくなるように、これら第１の整数ｐ１及び第２の整数ｐ２を決定し、そして、上記判定ユニットは、数ｐ１，ｐ２，ｐ１’，ｐ２’に関して実行されるオペレーションに基づき、数ｐ’が整数であるかどうかを判定することができる。
【００５３】
本発明の実施形態では、上記選択ユニットは、第１の整数ｐ１及び第２の整数ｐ２を無作為に決定する。
【００５４】
上記判定ユニットは、論文‘Efficient Generation of Shared RSA keys’で提案されているように、好ましくは、ソロベイ・ストラッセン型判定法とミラー・ラビン型判定法との組合せに基づく素数判定法を実施する。
【００５５】
好ましくは、上記選択ユニットは、数ｐ’が１又は２以上の決定された素数で割り切れないことを検証するために、数ｐ１’及びｐ２’に関して実行されるオペレーションに基づき、事前チェックを実施する。
【００５６】
この場合、上記選択ユニットは、もし決定された素数でｐ’が割り切れれば、二つの整数ｐ１’及びｐ２’の無作為な選択を繰り返す。
【００５７】
本発明の実施形態では、上記選択ユニットは、厳密に１より大きい素数に関して前記事前チェックを実施するために、
・ ０とｙ−１との間の範囲の整数の中から第１の数ｃを無作為に選択すると共に、１とｙ−１との間の範囲の整数の中から第２の整数ｄを無作為に選択するように構成された手段と、
・ 式u=c+dp1’ modulo yに従って数ｕを決定するように構成された手段と、
・ 式v=c-dp2’ modulo yに従って数ｖを決定するように構成された手段と、
・ ｐが、前記数ｕと前記数ｖとの差分の関数としてのｙで割り切れないかどうかを判定するように構成された手段とを更に備える。
【００５８】
本発明の他の態様、目的及び利点は、その実施形態の一つを読めば明らかになるであろう。
【００５９】
本発明は、また、図面によっていっそう良好に理解されるであろう。
・図１は、本発明の実施形態による鍵を生成する方法の主要なステップを例示する。
・図２は、本発明の実施形態による電子装置のダイアグラムである。
【発明を実施するための最良の形態】
【００６０】
本発明の実施形態における暗号アルゴリズムのための鍵を生成する方法は、電子装置(an electronic component)において実行されるように意図されている。
【００６１】
事前に、本電子装置は、Ｐで表される素数をメモリに格納する。
【００６２】
図１は、本発明の実施形態による方法の主要なステップを示す。
ステップ１１において、ｐ１’及びｐ２’で表される二つの整数が無作為に選択される。そして、ステップ１２において、これら選択された二つの数の、ｐ’で表される和が素数であるかどうかが判定される。このステップは、数ｐ’の秘密性が保護されるような方法で実行される。従って、好ましくは、このステップでは、このように数ｐ’を操作しないように注意が払わされる。数ｐ’の素数性に関する判定は、数ｐ１’及びｐ２’に関して実施されるオペレーションによって行われる。
【００６３】
そして、ステップ１３において、もし数ｐ’が素数でないと判定されれば、前のステップ１１及び１２が繰り返される。
【００６４】
これに対し、もし数ｐ’が素数であると判定されれば、数ｐ１’及びｐ２’はメモリに格納される。
【００６５】
従って、秘密の素数の生成が必要とされる都度、このような方法を繰り返すことが可能である。
【００６６】
ステップ１２において、数が二つの素数の組合せであるかどうかを判定することを可能とする任意の素数判定法を実施することが可能であるが、この素数判定法がプロダクトの上記二つの数のうちの一つの秘密性を危険にさらす可能性のある如何なるオペレーションも含まないことが条件とされる。このような素数判定法は、当業者には容易に利用可能である。
【００６７】
有利には、これらの素数判定法は、無作為に選択にされた数ｐ１’及びｐ２’の和から得られる数ｐ’と素数Ｐのプロダクトｎに基づき、数ｐ’が素数であるかどうかを判定することを可能とすることができる。この判定法は、従って、数ｐ１’及びｐ２’に関するオペレーションを含むが、数ｐ’に関して直接的に実行されるオペレーションを含まない。
【００６８】
従って、例えば、素数判定法は、論文‘Efficient Generation of Shared RSA keys’で提案されているように、ソロベイ・ストラッセン型判定法とミラー・ラビン型判定法の組合せに基づくことができる。
【００６９】
この場合、Ｐは、ｐ１及びｐ２で表される二つの数の形式に分解される。この分解は、無作為に、或いは非無作為に実行されることができる。
【００７０】
この判定法は、数ｍが二つの素数Ｐ及びｐ’のプロダクトであるかどうかを判定することを可能にし、ｍは次式を満足する。
m = (p1+p2)*(p1’+p2’)
ここで、p = p1+p2、且つ、p’ = p1’+p2’である。
【００７１】
従って、数Ｐ及びｐ’を直接的に操作する必要なく、これらの数Ｐ及びｐ’が素数であるかどうかを判定することが可能である。
【００７２】
このような適用において、数ｍは、それが秘密ではないため、危険を伴うことなく操作されることができることが分かる。
【００７３】
論文‘Efficient Generation of Shared RSA keys’に詳しく記載されているように、この判定法では、各種の数が次の特性を満足するものと仮定される。
p1 = 3 mod 4
且つ
p1’ = 3 mod 4
そして
p2 = 0 mod 4
且つ
p2’ = 0 mod 4
【００７４】
数ｐ’についての秘密性に関する如何なる攻撃も可能としないために、このステップの過程では、オペレーションが、数ｐ１，ｐ２，ｐ１’，ｐ２’に関して有利に実行される。
【００７５】
第１に、数ａは、１とｍ−１との間の範囲の整数の中から無作為に選択される。
【００７６】
その後、このように選択された数に関するヤコビ記号(Jacobi symbol)が計算され、このヤコビ記号は次のように表される。
【００７７】
【数１】
【００７８】
そして、もし、このように計算されたヤコビ記号が１でなければ、数ａについての無作為の選択ステップが繰り返される。
【００７９】
もし、ヤコビ記号が１に等しければ、次のステップを継続する。
【００８０】
そして、第１の中間計算が数ｍ，ｐ１，ｐ２’に関して実施されて、次式を満足する数ｕが得られる。
【００８１】
【数２】
【００８２】
その後、第２の中間計算が数ｍ，ｐ１，ｐ２に関して実施され、そして次式を満足する数ｖが得られる。
【００８３】
【数３】
【００８４】
そして、次式が満足されるかどうかに関して判定(test)が実施される。
【００８５】
【数４】
【００８６】
もし、後者の式が満足されれば、このことから、或る確率でｍが二つの整数Ｐ及びｐ’のプロダクトであることが推論される。
【００８７】
本発明の実施形態では、Ｐは、本電子装置のメモリに予め格納された素数である。従って、このタイプの判定法を適用することにより、数ｐ’に関して直接的に何らオペレーションを実施する必要なく、数ｐ’が素数であるかどうかを判定することが可能である。
【００８８】
本発明の実施形態では、和が整数であるところの数ｐ１’及びｐ２’に関してステップ１２を実行する確率を高めるために、ステップ１２の前に、或る数を簡単且つ効果的に事前に除去することを可能とするステップを実行することが可能である。
【００８９】
従って、一組の素数を考えることができる。そして、ステップ１２の前に、数ｐ’がｙによって表される素数で割り切れるかどうかを判定することを望む。この目的のために、整数ｃが０とｙ−１との間の範囲の整数の中から無作為に選択され、そして整数ｄが１とｙ−１との間の範囲の整数の中から無作為に選択される。
【００９０】
そして、次の二つの中間計算が実施される。
u = c + dp1’ modulo y
v = c - dp2’ modulo y
【００９１】
そして、次式が満足されるかどうかを判定(test)することが可能である。
u-v = 0 modulo y
【００９２】
後者の式が満足された場合、このことから数ｐ’がｙで割り切れることが推論される。
【００９３】
図２は、本発明の実施形態による電子装置を表す図である。
このような電子装置２１は、和が数ｐ’であるところの二つの整数ｐ１’及びｐ２’を無作為に選択するのに適した選択ユニット２２を備える。
【００９４】
更に、電子装置２１はメモリ２３を備え、このメモリ２３は、素数Ｐを格納すると共に、数ｐ１’及びｐ２’の和が素数であると判定された場合にこれら数ｐ１’及びｐ２’を格納するためのものである。
【００９５】
また、電子装置２１は判定ユニット２４を備え、この判定ユニット２４は、メモリに格納された素数Ｐと数ｐ１’及びｐ２’との組合せに基づき、数ｐ’が素数であるかどうかを判定するのに適したものである。
【００９６】
このようにして、一つの素数または多数の素数を連続的に効果的且つ秘密に生成するのに適した鍵の生成方法が得られる。
【図面の簡単な説明】
【００９７】
【図１】本発明の実施形態による鍵を生成する方法の主要なステップを例示する図である。
【図２】本発明の実施形態による電子装置の図である。
【符号の説明】
【００９８】
１１，１２，１３，１４；ステップ
２１；電子装置
２２；選択ユニット
２３；メモリ
２４；判定ユニット
【技術分野】
【０００１】
本発明は、暗号化(cryptography)の分野に関し、更に詳しくは、暗号アルゴリズムにより使用される鍵(keys)の秘密性の保護に関する。
【背景技術】
【０００２】
暗号アルゴリズムは、とりわけ、データを暗号化(encrypt)することを可能にし、及び／又は、データを復号化(decrypt)することを可能にする。また、このようなアルゴリズムを他の多くのアプリケーションに使用することも可能である。具体的には、それらは、署名(sign)するのに役立ち、あるいは、或る情報を認証するのに役立つ。また、それらは、タイムスタンプ(time-stamping)の分野においても有用である。
【０００３】
一般に、このようなアルゴリズムは、多数のオペレーションの文字列(string)または計算(calculations)から構成され、これらは、暗号化されたデータアイテムを得るために、暗号化されるべきデータアイテムに対して連続的に適用され、あるいは、復号化されたデータアイテムを得るために、暗号化されたデータアイテムに対して連続的に適用される。
【０００４】
これらのアルゴリズムのうち、或るものは秘密鍵を使用することに基づいており、一方、他のものは公開鍵と秘密鍵の混用に基づいている。
【０００５】
一例として、次の章では、データ暗号化及び復号化に対するこれらのアルゴリズムの適用を説明する。
【０００６】
このような適用における公開鍵暗号アルゴリズムの一般原理によれば、公開鍵は全てに対してアクセス可能であり、誰でも公開鍵を用いて暗号化されたデータを発送することができるが、対応する秘密鍵の保持者でなければ、これらのデータを復号化することはできない。
【０００７】
公開鍵暗号アルゴリズムのセキュリティは、公開鍵を知っていても対応する秘密鍵を取り出すことができず、故にデータを復号化することができないという事に依存している。
【０００８】
従って、ＲＳＡと名づけられた公開鍵暗号化手法が知られており、ＲＳＡは、その考案者の名前であるRivert, Shamir, Adelmanを表す。この手法は、この技術分野において最も使用されているものであって最も古いもののうちの一つである。
【０００９】
この手法によれば、ｐ，ｑ，ｅ，ｄで表される４つの数が選択される。数ｐ及びｑは、明らかに異なる二つの素数である。これらは無作為に生成される。
【００１０】
数ｄ及びｅは次式を満足する。
e*d=1 modulo (p-1)(q-1)
【００１１】
そして、この技術分野の当業者に広く知られている演算により、ユークリッドアルゴリズムを用いて、ｅ，ｐ，ｑに基づきｄを生成することが可能である。
【００１２】
そして数ｐとｑとのプロダクト(product)から得られる数はｎ(モジュラス)と表される。
【００１３】
従って、数ｎ及びｅのペアは公開鍵を構成し、一方、数ｎ及びｄのペアは秘密鍵を構成する。
【００１４】
そして、０とｎ−１の間の範囲の整数Ｍに対応するデータアイテムを発送するために、発送されるべき対応するコード化された数Ｃが次式に従って計算される。
C = Me modulo n
【００１５】
上記コード化されたメッセージＣを受信すると、秘密鍵の保持者は、数Ｄの中間値を計算する。
D = Cd modulo n
【００１６】
そして、元の平分メッセージＭが、次式に従って再生される。
D = Mde = M modulo n
【００１７】
従って、上記により、このような公開鍵アルゴリズムは、素数の生成に基づいていることが知られている。より詳細には、ＲＳＡのような公開鍵アルゴリズムは、極めて大きな素数の生成を必要とする可能性がある。従って、ほぼ５００デジット(digits)から成る素数を生成する必要があるかもしれない。
【００１８】
ＲＳＡ型のアルゴリズムでは、モジュラスｎは公開鍵に属し、従って全てに知られ、一方、数ｄは、上記アルゴリズムのセキュリティを保証するために秘密のままでなければならない。しかし、数ｄは、数ｐ及びｑに基づいて得られる。従って、数ｐ及びｑが秘密のままであることは、このようなアルゴリズムのセキュリティにとって重要である。
【００１９】
一般に、電子カード(electronic card)の暗号化ソフトウェアについて、これらの鍵は、例えば暗号アルゴリズムが実行されるところの電子装置を製造中の工場のような、任意の攻撃から保護された環境で生成される。
【００２０】
従って、このような条件の下で、数ｐ及びｑは、これらの値を決定して上記アルゴリズムのセキュリティを破壊することを狙った攻撃に直面する如何なる危険も伴うことなく、簡単に操作されることができる。従って、通常、鍵を生成するためのこれら各種の方法は、これらの数ｐ及びｑの操作(manipulation)を含む。
【００２１】
このような条件の下で、素数を生成するのに当業者に知られた各種の方法を使用することが可能である。
【００２２】
しかしながら、或る適用については、暗号アルゴリズムの使用鍵の秘密性を破ることを狙った攻撃が可能な外部環境においてこのような鍵を生成する必要があるかもしれない。
【００２３】
今日では、多くのタイプの攻撃が知られている。
【００２４】
従って、或る攻撃は、或る暗号化ステップの実行中に検出される情報漏洩に基づいている。これらの攻撃は、一般に、データアイテムの暗号アルゴリズムによる処理中に検出される情報漏洩と鍵（単数または複数の鍵）との間の相関関係に基づいている（電流の消費、電磁気放射、計算時間などを分析することによる攻撃）。
【００２５】
このような条件の下で、以前に入力された数ｐ及びｑのセキュリティを保護するための適切な予防策を講じることは欠かせない。
【００２６】
数ｐ及びｑを生成するための手法であってこれらの数のセキュリティを保護することを可能にする手法が知られている。具体的には、Dan BonehとMatthew Franklinによって書かれた論文“Efficient Generation of Shared RSA keys”は、数ｐ及びｑを同時に且つ秘密に生成する方法を提案している。
【００２７】
この手法の目的の一つは、多数の参加者の間で共通の方法で素数を生成することである。従って、これらの参加者は、これら参加者が二つの素数を知ることなく生成することを可能にする演算を実行し、これらの数のプロダクト(product)のみが参加者に知られる。
【００２８】
この手法によれば、数ｐ及びｑは無作為且つ同時に選択される。そして、このように選択された二つの数が素数であるかどうかが、それらのプロダクトに基づいて判定される。上記数ｐ及びｑの秘密性を保護するために、これらの数は直接的には操作されない。
【００２９】
具体的に、更に正確に言えば、４つの整数ｐａ，ｐｂ，ｑａ，ｑｂが無作為に選択され、数ｐは数ｐａと数ｐｂの和の結果であり、数ｑは数ｑａと数ｑｂの和の結果である。
【００３０】
そして、数ｐ及びｑが素数であるかどうかが、数ｐａ，ｐｂ，ｑａ，ｑｂを操作することによるそれらのプロダクトに基づいて検証される。
【００３１】
数ｐ及びｑが素数ではない場合、選択された数ｐ及びｑが素数であると判定されるまで、他の二つの数ｐ及びｑの無作為の選択が繰り返される。
【００３２】
このような解決手法は、計算の観点から見て極めて複雑であり、且つ、鍵を生成するための方法の性能を大幅に低下させるかもしれない。
【発明の開示】
【発明が解決しようとする課題】
【００３３】
本発明は、これらの欠点を低減することを可能にする解決手法を提案することを目的とする。
【課題を解決するための手段】
【００３４】
本発明の第１の態様は、素数Ｐがメモリに格納されているところの電子装置における暗号アルゴリズムのための鍵を生成する方法を提案する。
【００３５】
本方法は、少なくとも一つの秘密の素数を生成するオペレーションを含み、このオペレーションは、次の連続的なステップ、すなわち、
/a/ 和が数ｐ’に等しい二つの整数ｐ１’及びｐ２’を無作為に選択するステップと、
/b/ 前記数ｐ’が素数であるかどうかを、前記数ｐ１’及びｐ２’とメモリに格納された前記素数Ｐとの組合せに基づいて判定するステップと、
/c/ もし、前記数ｐ’が素数であれば、前記数ｐ１’及びｐ２’を電子装置のメモリに格納し、前記数ｐ’が素数でなければ、ステップ/a/及び/b/を繰り返すステップと、
に従って実行される。
これらの処理により、素数ｐ’が秘密的かつ効率的に生成される。
【００３６】
詳細には、このように生成された数ｐ’は、本方法の各種ステップの過程で直接的に操作されず、整数ｐ１’及びｐ２’のみが操作される。従って、素数ｐ’を生成するステップの過程でアルゴリズム攻撃によって素数ｐ’の秘密性(secrecy)を破ることは可能でない。
【００３７】
また、この素数の生成は、多くの素数を連続的に生成することを可能にするので効率的である。しかし、論文“Efficient Generation of Shared RSA keys”で提案されているように、同時に多数の素数を無作為に選択することよりも、一つの素数を無作為に選択することの方が可能性として大きい。
【００３８】
本発明によるこのような方法は、電子装置における決められた暗号アルゴリズムが秘密の一つの素数の生成を必要とし、あるいは多くの秘密の素数の生成を必要とする場合に、このような暗号アルゴリズムのための鍵を生成する任意の方法に有利に適用されることができる。
【００３９】
ステップ/b/は、整数と素数との組合せに基づいて、この整数の素数性(primality)を判定することを可能にする任意のタイプの素数判定法(primality test)を実施することにより実行されることができる。
【００４０】
一般に、このような素数判定法は、確率的アルゴリズム(probabilistic algorithms)である。これは、数が素数であることを極めて高い確率で判定することを可能にする。
【００４１】
本発明の実施形態において、第１の整数ｐ１と第２の整数ｐ２は、メモリに格納された素数Ｐが第１の整数ｐ１と第２の整数ｐ２の和に等しくなるように決定される。そして、ステップ/b/は、数ｐ１，ｐ２，ｐ１’，ｐ２’に関して実行されるオペレーションに基づいて実施される。
【００４２】
従って、秘密の素数ｐ’の生成過程において、数ｐ’についての素数判定法の局面では、好ましくは、素数Ｐも数ｐ’も操作されず、これにより、この生成ステップの過程で数ｐ’の秘密性に対する潜在的な攻撃を無力にする。
【００４３】
第１の整数ｐ１及び第２の整数ｐ２は、無作為に決定され得る。
【００４４】
ステップ/b/は、ソロベイ・ストラッセン(Solovay-Strassen)型判定法とミラー・ラビン(Miller-Rabin)型判定法との組合せに基づく素数判定法を用いて実行されることができる。従って、例えば、素数判定法は、Dan BonehとMatthew Franklinによって書かれた論文‘Efficient Generation of Shared RSA keys’の第３章‘distributed primality test’に記載されているような素数判定法に基づくことができる。具体的には、この素数判定法は、一方ではソロベイ・ストラッセン素数判定法に基づくと共に、他方ではミラー・ラビン素数判定法に基づいている。ソロベイ・ストラッセン素数判定法は、R. SolovayとV. Strassenによる１９７７年の文書‘A fast monte carlo test for primality’に記載されている。ミラー・ラビン素数判定法は、M. Rabinによる１９８０年の文書‘Probabilistic algorithm for testing primality’に記載されている。
【００４５】
本発明の実施形態では、このような方法の性能は、ステップ/b/の前に、次のステップ、すなわち、
/a1/ 数ｐ１’及び数ｐ２’に関して実行されたオペレーションに基づき、数ｐ’が１又は２以上の決定された素数で割り切れないことを検証するステップ
を含むことにより強化される。
【００４６】
この場合、ステップ/a/及び/a1/は、数ｐ’が上記決定された素数の一つで割り切れれば、繰り返される。
【００４７】
このステップ/a1/は、大きな素数を生成したい場合にいっそう有益である。具体的には、このようなステップは、実行するにはいっそう扱いにくいステップ/b/を実行する前に、或る数を適正に簡単に除去することを可能にする。
【００４８】
本発明の実施形態では、ステップ/a1/は、厳密に１よりも大きな素数ｙについて、次のステップ、すなわち、
・ ０とｙ−１との間の範囲の整数の中から第１の整数ｃを無作為に選択し、１とｙ−１との間の範囲の整数の中から第２の整数ｄを無作為に選択するステップと、
・ 式u=c+dp1’ modulo yに従って数ｕを決定するステップと、
・ 式v=c-dp2’ modulo yに従って数ｖを決定するステップと、
・ ｐが、数ｕと数ｖとの差分の関数としてのｙによって割り切れないかどうかを判定するステップと
を含む。
【００４９】
或る暗号アルゴリズムは、多数の秘密の素数の生成を必要とする。この場合、素数を生成するために必要に応じて何度でも、本発明の実施形態による方法を適用することが容易に可能である。従って、一対の非対称の鍵の構築のために、ステップ/a/から/c/を繰り返すことにより、連続的に、少なくとも二つの素数を生成することが可能である。
【００５０】
本発明の第２の態様は、決定された暗号アルゴリズムのための鍵を生成するための電子装置を提案する。
【００５１】
本電子装置は、
・ 和が数ｐ’であるところの二つの整数ｐ１’及びｐ２’を無作為に選択するのに適した選択ユニットと、
・ 素数Ｐを格納すると共に、前記数ｐ１’及びｐ２’の和が素数であると判定された場合に前記数ｐ１’及びｐ２’を格納するためのメモリと、
・ メモリに格納された前記素数Ｐと前記数ｐ１’及びｐ２’との組合せに基づき、前記数ｐ’が素数であるかどうかを判定するのに適した判定ユニットと
を備えて構成される。
【００５２】
上記選択ユニットは、メモリに格納された素数Ｐが第１の整数ｐ１及び第２の整数ｐ２の和に等しくなるように、これら第１の整数ｐ１及び第２の整数ｐ２を決定し、そして、上記判定ユニットは、数ｐ１，ｐ２，ｐ１’，ｐ２’に関して実行されるオペレーションに基づき、数ｐ’が整数であるかどうかを判定することができる。
【００５３】
本発明の実施形態では、上記選択ユニットは、第１の整数ｐ１及び第２の整数ｐ２を無作為に決定する。
【００５４】
上記判定ユニットは、論文‘Efficient Generation of Shared RSA keys’で提案されているように、好ましくは、ソロベイ・ストラッセン型判定法とミラー・ラビン型判定法との組合せに基づく素数判定法を実施する。
【００５５】
好ましくは、上記選択ユニットは、数ｐ’が１又は２以上の決定された素数で割り切れないことを検証するために、数ｐ１’及びｐ２’に関して実行されるオペレーションに基づき、事前チェックを実施する。
【００５６】
この場合、上記選択ユニットは、もし決定された素数でｐ’が割り切れれば、二つの整数ｐ１’及びｐ２’の無作為な選択を繰り返す。
【００５７】
本発明の実施形態では、上記選択ユニットは、厳密に１より大きい素数に関して前記事前チェックを実施するために、
・ ０とｙ−１との間の範囲の整数の中から第１の数ｃを無作為に選択すると共に、１とｙ−１との間の範囲の整数の中から第２の整数ｄを無作為に選択するように構成された手段と、
・ 式u=c+dp1’ modulo yに従って数ｕを決定するように構成された手段と、
・ 式v=c-dp2’ modulo yに従って数ｖを決定するように構成された手段と、
・ ｐが、前記数ｕと前記数ｖとの差分の関数としてのｙで割り切れないかどうかを判定するように構成された手段とを更に備える。
【００５８】
本発明の他の態様、目的及び利点は、その実施形態の一つを読めば明らかになるであろう。
【００５９】
本発明は、また、図面によっていっそう良好に理解されるであろう。
・図１は、本発明の実施形態による鍵を生成する方法の主要なステップを例示する。
・図２は、本発明の実施形態による電子装置のダイアグラムである。
【発明を実施するための最良の形態】
【００６０】
本発明の実施形態における暗号アルゴリズムのための鍵を生成する方法は、電子装置(an electronic component)において実行されるように意図されている。
【００６１】
事前に、本電子装置は、Ｐで表される素数をメモリに格納する。
【００６２】
図１は、本発明の実施形態による方法の主要なステップを示す。
ステップ１１において、ｐ１’及びｐ２’で表される二つの整数が無作為に選択される。そして、ステップ１２において、これら選択された二つの数の、ｐ’で表される和が素数であるかどうかが判定される。このステップは、数ｐ’の秘密性が保護されるような方法で実行される。従って、好ましくは、このステップでは、このように数ｐ’を操作しないように注意が払わされる。数ｐ’の素数性に関する判定は、数ｐ１’及びｐ２’に関して実施されるオペレーションによって行われる。
【００６３】
そして、ステップ１３において、もし数ｐ’が素数でないと判定されれば、前のステップ１１及び１２が繰り返される。
【００６４】
これに対し、もし数ｐ’が素数であると判定されれば、数ｐ１’及びｐ２’はメモリに格納される。
【００６５】
従って、秘密の素数の生成が必要とされる都度、このような方法を繰り返すことが可能である。
【００６６】
ステップ１２において、数が二つの素数の組合せであるかどうかを判定することを可能とする任意の素数判定法を実施することが可能であるが、この素数判定法がプロダクトの上記二つの数のうちの一つの秘密性を危険にさらす可能性のある如何なるオペレーションも含まないことが条件とされる。このような素数判定法は、当業者には容易に利用可能である。
【００６７】
有利には、これらの素数判定法は、無作為に選択にされた数ｐ１’及びｐ２’の和から得られる数ｐ’と素数Ｐのプロダクトｎに基づき、数ｐ’が素数であるかどうかを判定することを可能とすることができる。この判定法は、従って、数ｐ１’及びｐ２’に関するオペレーションを含むが、数ｐ’に関して直接的に実行されるオペレーションを含まない。
【００６８】
従って、例えば、素数判定法は、論文‘Efficient Generation of Shared RSA keys’で提案されているように、ソロベイ・ストラッセン型判定法とミラー・ラビン型判定法の組合せに基づくことができる。
【００６９】
この場合、Ｐは、ｐ１及びｐ２で表される二つの数の形式に分解される。この分解は、無作為に、或いは非無作為に実行されることができる。
【００７０】
この判定法は、数ｍが二つの素数Ｐ及びｐ’のプロダクトであるかどうかを判定することを可能にし、ｍは次式を満足する。
m = (p1+p2)*(p1’+p2’)
ここで、p = p1+p2、且つ、p’ = p1’+p2’である。
【００７１】
従って、数Ｐ及びｐ’を直接的に操作する必要なく、これらの数Ｐ及びｐ’が素数であるかどうかを判定することが可能である。
【００７２】
このような適用において、数ｍは、それが秘密ではないため、危険を伴うことなく操作されることができることが分かる。
【００７３】
論文‘Efficient Generation of Shared RSA keys’に詳しく記載されているように、この判定法では、各種の数が次の特性を満足するものと仮定される。
p1 = 3 mod 4
且つ
p1’ = 3 mod 4
そして
p2 = 0 mod 4
且つ
p2’ = 0 mod 4
【００７４】
数ｐ’についての秘密性に関する如何なる攻撃も可能としないために、このステップの過程では、オペレーションが、数ｐ１，ｐ２，ｐ１’，ｐ２’に関して有利に実行される。
【００７５】
第１に、数ａは、１とｍ−１との間の範囲の整数の中から無作為に選択される。
【００７６】
その後、このように選択された数に関するヤコビ記号(Jacobi symbol)が計算され、このヤコビ記号は次のように表される。
【００７７】
【数１】
【００７８】
そして、もし、このように計算されたヤコビ記号が１でなければ、数ａについての無作為の選択ステップが繰り返される。
【００７９】
もし、ヤコビ記号が１に等しければ、次のステップを継続する。
【００８０】
そして、第１の中間計算が数ｍ，ｐ１，ｐ２’に関して実施されて、次式を満足する数ｕが得られる。
【００８１】
【数２】
【００８２】
その後、第２の中間計算が数ｍ，ｐ１，ｐ２に関して実施され、そして次式を満足する数ｖが得られる。
【００８３】
【数３】
【００８４】
そして、次式が満足されるかどうかに関して判定(test)が実施される。
【００８５】
【数４】
【００８６】
もし、後者の式が満足されれば、このことから、或る確率でｍが二つの整数Ｐ及びｐ’のプロダクトであることが推論される。
【００８７】
本発明の実施形態では、Ｐは、本電子装置のメモリに予め格納された素数である。従って、このタイプの判定法を適用することにより、数ｐ’に関して直接的に何らオペレーションを実施する必要なく、数ｐ’が素数であるかどうかを判定することが可能である。
【００８８】
本発明の実施形態では、和が整数であるところの数ｐ１’及びｐ２’に関してステップ１２を実行する確率を高めるために、ステップ１２の前に、或る数を簡単且つ効果的に事前に除去することを可能とするステップを実行することが可能である。
【００８９】
従って、一組の素数を考えることができる。そして、ステップ１２の前に、数ｐ’がｙによって表される素数で割り切れるかどうかを判定することを望む。この目的のために、整数ｃが０とｙ−１との間の範囲の整数の中から無作為に選択され、そして整数ｄが１とｙ−１との間の範囲の整数の中から無作為に選択される。
【００９０】
そして、次の二つの中間計算が実施される。
u = c + dp1’ modulo y
v = c - dp2’ modulo y
【００９１】
そして、次式が満足されるかどうかを判定(test)することが可能である。
u-v = 0 modulo y
【００９２】
後者の式が満足された場合、このことから数ｐ’がｙで割り切れることが推論される。
【００９３】
図２は、本発明の実施形態による電子装置を表す図である。
このような電子装置２１は、和が数ｐ’であるところの二つの整数ｐ１’及びｐ２’を無作為に選択するのに適した選択ユニット２２を備える。
【００９４】
更に、電子装置２１はメモリ２３を備え、このメモリ２３は、素数Ｐを格納すると共に、数ｐ１’及びｐ２’の和が素数であると判定された場合にこれら数ｐ１’及びｐ２’を格納するためのものである。
【００９５】
また、電子装置２１は判定ユニット２４を備え、この判定ユニット２４は、メモリに格納された素数Ｐと数ｐ１’及びｐ２’との組合せに基づき、数ｐ’が素数であるかどうかを判定するのに適したものである。
【００９６】
このようにして、一つの素数または多数の素数を連続的に効果的且つ秘密に生成するのに適した鍵の生成方法が得られる。
【図面の簡単な説明】
【００９７】
【図１】本発明の実施形態による鍵を生成する方法の主要なステップを例示する図である。
【図２】本発明の実施形態による電子装置の図である。
【符号の説明】
【００９８】
１１，１２，１３，１４；ステップ
２１；電子装置
２２；選択ユニット
２３；メモリ
２４；判定ユニット
【特許請求の範囲】
【請求項１】
電子装置（２１）における暗号アルゴリズムのための鍵を生成する方法であって、
素数Ｐが前記電子装置にけるメモリに格納されており、
当該方法は、少なくとも一つの秘密の素数を生成するオペレーションを含み、前記オペレーションが、
/a/ 和が数ｐ’に等しい二つの整数ｐ１’及びｐ２’を無作為に選択するステップ（１１）と、
/b/ 前記数ｐ’が素数であるかどうかを、前記数ｐ１’及びｐ２’とメモリに格納された前記素数Ｐとの組合せに基づいて判定するステップ（１２）と、
/c/ もし前記数ｐ’が素数であると判定されれば、前記数ｐ１’及びｐ２’を前記電子装置のメモリに格納し（１４）、前記数ｐ’が素数でなければ、ステップ/a/と/b/を繰り返すステップと
の連続的なステップに従って実行される方法。
【請求項２】
メモリに格納された前記素数Ｐが第１の整数ｐ１及び第２の整数ｐ２の和に等しくなるように、前記第１の整数ｐ１及び前記第２の整数ｐ２が決定され、且つ
ステップ/b/が、前記数ｐ１，ｐ２，ｐ１’，ｐ２’に関して実行されるオペレーションに基づき実施される請求項１記載の方法。
【請求項３】
前記第１の整数ｐ１及び前記第２の整数ｐ２が、無作為に決定される請求項１または２の何れか１項記載の方法。
【請求項４】
ステップ/b/が、ソロベイ・ストラッセン(Solovay-Strassen)型判定法とミラー・ラビン(Miller-Rabin)型判定法との組合せに基づく素数判定法を用いて実行される請求項１乃至３の何れか１項記載の方法。
【請求項５】
ステップ/b/の前に、
/a1/ 前記数ｐ１’及びｐ２’に関して実行されたオペレーションに基づき、前記数ｐ’が１又は２以上の決定された素数で割り切れないことを検証するステップを更に備え、もし数ｐ’が上記決定された素数の一つで割り切れれば、ステップ/a/及び/a1/が繰り返される請求項１乃至４の何れか１項記載の方法。
【請求項６】
ステップ/a1/が、厳密に１より大きい決定された素数ｙについて、
１とｙ−１との間の範囲の整数の中から第１の数ｃ及び第２の数ｄを無作為に選択するステップと、
式u=c+dp1’ modulo yに従って数ｕを決定するステップと、
式v=c-dp2’ modulo yに従って数ｖを決定するステップと、
ｐが、数ｕと数ｙとの差分の関数としてのｙで割り切れないかどうかを判定するステップと
を含む請求項５記載の方法。
【請求項７】
一対の非対称な鍵を構築するために、ステップ/a/乃至/c/を繰り返すことにより少なくとも二つの素数が生成される請求項１乃至６の何れか１項記載の方法。
【請求項８】
前記暗号アルゴリズムはＲＳＡ型のアルゴリズムである請求項１乃至７の何れか１項記載の方法。
【請求項９】
決定された暗号アルゴリズムのための鍵を生成するための電子装置（２１）であって、
和が数ｐ’であるところの二つの整数ｐ１’及びｐ２’を無作為に選択するのに適した選択ユニット（２２）と、
素数Ｐを格納すると共に、前記数ｐ１’及びｐ２’の和が素数であると判定された場合に前記数ｐ１’及びｐ２’を格納するためのメモリ（２３）と、
メモリに格納された前記素数Ｐと前記数ｐ１’及びｐ２’との組合せに基づき、前記数ｐ’が素数であるかどうかを判定するのに適した判定ユニット（２４）と
を備えた電子装置。
【請求項１０】
前記選択ユニット（２２）が、メモリ（２３）に格納された前記素数Ｐが第１の整数ｐ１及び第２の整数ｐ２の和に等しくなるように、前記第１の整数ｐ１及び前記第２の整数ｐ２を決定し、前記判定ユニット（２４）が、前記数ｐ１，ｐ２，ｐ１’，ｐ２’に関して実行されたオペレーションに基づき前記数ｐ’が整数であるかどうかを判定する請求項９記載の電子装置。
【請求項１１】
前記選択ユニット（２２）が、前記第１の整数ｐ１及び前記第２の整数ｐ２を無作為に決定する請求項１０記載の電子装置。
【請求項１２】
前記判定ユニット（２３）が、ソロベイ・ストラッセン(Solovay-Strassen)型判定法とミラー・ラビン(Miller-Rabin)型判定法との組合せに基づく素数判定法を実施する請求項９乃至１１の何れか１項記載の電子装置。
【請求項１３】
前記選択ユニット（２２）が、前記数ｐ’が１又は２以上の決定された素数で割り切れることを検証するために、前記数ｐ１’及びｐ２’に関して実行されたオペレーションに基づき、事前チェックを実施する請求項９乃至１２の何れか１項記載の電子装置。
【請求項１４】
上記選択ユニットは、厳密に１より大きい素数ｙに関して前記事前チェックを実施するために、
１とｙ−１との間の範囲の整数の中から第１の数ｃ及び第２の数ｄを無作為に選択するように構成された手段と、
式u=c+dp1’ modulo yに従って数ｕを決定するように構成された手段と、
式v=c-dp2’ modulo yに従って数ｖを決定するように構成された手段と、
ｐが、前記数ｕと前記数ｖとの差分の関数としてのｙで割り切れないかどうかを判定するように構成された手段と
を更に備えた請求項９乃至１３の何れか１項記載の電子装置。
【請求項１５】
複数の素数ｐ’が連続的に生成される請求項９乃至１４の何れか１項記載の電子装置。
【請求項１６】
前記暗号アルゴリズムがＲＳＡ型のアルゴリズムである請求項９乃至１５の何れか１項記載の電子装置。
【請求項１】
電子装置（２１）における暗号アルゴリズムのための鍵を生成する方法であって、
素数Ｐが前記電子装置にけるメモリに格納されており、
当該方法は、少なくとも一つの秘密の素数を生成するオペレーションを含み、前記オペレーションが、
/a/ 和が数ｐ’に等しい二つの整数ｐ１’及びｐ２’を無作為に選択するステップ（１１）と、
/b/ 前記数ｐ’が素数であるかどうかを、前記数ｐ１’及びｐ２’とメモリに格納された前記素数Ｐとの組合せに基づいて判定するステップ（１２）と、
/c/ もし前記数ｐ’が素数であると判定されれば、前記数ｐ１’及びｐ２’を前記電子装置のメモリに格納し（１４）、前記数ｐ’が素数でなければ、ステップ/a/と/b/を繰り返すステップと
の連続的なステップに従って実行される方法。
【請求項２】
メモリに格納された前記素数Ｐが第１の整数ｐ１及び第２の整数ｐ２の和に等しくなるように、前記第１の整数ｐ１及び前記第２の整数ｐ２が決定され、且つ
ステップ/b/が、前記数ｐ１，ｐ２，ｐ１’，ｐ２’に関して実行されるオペレーションに基づき実施される請求項１記載の方法。
【請求項３】
前記第１の整数ｐ１及び前記第２の整数ｐ２が、無作為に決定される請求項１または２の何れか１項記載の方法。
【請求項４】
ステップ/b/が、ソロベイ・ストラッセン(Solovay-Strassen)型判定法とミラー・ラビン(Miller-Rabin)型判定法との組合せに基づく素数判定法を用いて実行される請求項１乃至３の何れか１項記載の方法。
【請求項５】
ステップ/b/の前に、
/a1/ 前記数ｐ１’及びｐ２’に関して実行されたオペレーションに基づき、前記数ｐ’が１又は２以上の決定された素数で割り切れないことを検証するステップを更に備え、もし数ｐ’が上記決定された素数の一つで割り切れれば、ステップ/a/及び/a1/が繰り返される請求項１乃至４の何れか１項記載の方法。
【請求項６】
ステップ/a1/が、厳密に１より大きい決定された素数ｙについて、
１とｙ−１との間の範囲の整数の中から第１の数ｃ及び第２の数ｄを無作為に選択するステップと、
式u=c+dp1’ modulo yに従って数ｕを決定するステップと、
式v=c-dp2’ modulo yに従って数ｖを決定するステップと、
ｐが、数ｕと数ｙとの差分の関数としてのｙで割り切れないかどうかを判定するステップと
を含む請求項５記載の方法。
【請求項７】
一対の非対称な鍵を構築するために、ステップ/a/乃至/c/を繰り返すことにより少なくとも二つの素数が生成される請求項１乃至６の何れか１項記載の方法。
【請求項８】
前記暗号アルゴリズムはＲＳＡ型のアルゴリズムである請求項１乃至７の何れか１項記載の方法。
【請求項９】
決定された暗号アルゴリズムのための鍵を生成するための電子装置（２１）であって、
和が数ｐ’であるところの二つの整数ｐ１’及びｐ２’を無作為に選択するのに適した選択ユニット（２２）と、
素数Ｐを格納すると共に、前記数ｐ１’及びｐ２’の和が素数であると判定された場合に前記数ｐ１’及びｐ２’を格納するためのメモリ（２３）と、
メモリに格納された前記素数Ｐと前記数ｐ１’及びｐ２’との組合せに基づき、前記数ｐ’が素数であるかどうかを判定するのに適した判定ユニット（２４）と
を備えた電子装置。
【請求項１０】
前記選択ユニット（２２）が、メモリ（２３）に格納された前記素数Ｐが第１の整数ｐ１及び第２の整数ｐ２の和に等しくなるように、前記第１の整数ｐ１及び前記第２の整数ｐ２を決定し、前記判定ユニット（２４）が、前記数ｐ１，ｐ２，ｐ１’，ｐ２’に関して実行されたオペレーションに基づき前記数ｐ’が整数であるかどうかを判定する請求項９記載の電子装置。
【請求項１１】
前記選択ユニット（２２）が、前記第１の整数ｐ１及び前記第２の整数ｐ２を無作為に決定する請求項１０記載の電子装置。
【請求項１２】
前記判定ユニット（２３）が、ソロベイ・ストラッセン(Solovay-Strassen)型判定法とミラー・ラビン(Miller-Rabin)型判定法との組合せに基づく素数判定法を実施する請求項９乃至１１の何れか１項記載の電子装置。
【請求項１３】
前記選択ユニット（２２）が、前記数ｐ’が１又は２以上の決定された素数で割り切れることを検証するために、前記数ｐ１’及びｐ２’に関して実行されたオペレーションに基づき、事前チェックを実施する請求項９乃至１２の何れか１項記載の電子装置。
【請求項１４】
上記選択ユニットは、厳密に１より大きい素数ｙに関して前記事前チェックを実施するために、
１とｙ−１との間の範囲の整数の中から第１の数ｃ及び第２の数ｄを無作為に選択するように構成された手段と、
式u=c+dp1’ modulo yに従って数ｕを決定するように構成された手段と、
式v=c-dp2’ modulo yに従って数ｖを決定するように構成された手段と、
ｐが、前記数ｕと前記数ｖとの差分の関数としてのｙで割り切れないかどうかを判定するように構成された手段と
を更に備えた請求項９乃至１３の何れか１項記載の電子装置。
【請求項１５】
複数の素数ｐ’が連続的に生成される請求項９乃至１４の何れか１項記載の電子装置。
【請求項１６】
前記暗号アルゴリズムがＲＳＡ型のアルゴリズムである請求項９乃至１５の何れか１項記載の電子装置。
【図１】
【図２】
【図２】
【公表番号】特表２００８−５２５８３５（Ｐ２００８−５２５８３５Ａ）
【公表日】平成２０年７月１７日（２００８．７．１７）
【国際特許分類】
【出願番号】特願２００７−５４７５７６（Ｐ２００７−５４７５７６）
【出願日】平成１７年１２月２２日（２００５．１２．２２）
【国際出願番号】ＰＣＴ／ＦＲ２００５／００３２５０
【国際公開番号】ＷＯ２００６／０７０１２０
【国際公開日】平成１８年７月６日（２００６．７．６）
【出願人】（５０６３１３５７８）
【Ｆターム（参考）】
【公表日】平成２０年７月１７日（２００８．７．１７）
【国際特許分類】
【出願日】平成１７年１２月２２日（２００５．１２．２２）
【国際出願番号】ＰＣＴ／ＦＲ２００５／００３２５０
【国際公開番号】ＷＯ２００６／０７０１２０
【国際公開日】平成１８年７月６日（２００６．７．６）
【出願人】（５０６３１３５７８）
【Ｆターム（参考）】
[ Back to top ]