鍵生成装置及びプログラム
【課題】 暗号化及び復号の処理速度をバランスさせるように鍵を生成できると共に、ｐ−１法による素因数分解を回避でき、より強固なＲＳＡ暗号方式の鍵を生成する。
【解決手段】 鍵生成処理の最初に、Ｐ−１の素因子として含ませるｎrビットの素数Ｒを生成し、次にｎeビットの奇数Ｅを生成し、ｎe＋ｎ{d_p}−ｎp−ｎrビットの中間変数Ｋpを生成し、Ｄp＝Ｅ-1 ｍｏｄ ＫpＲを満たすｎ{d_p}ビットのＤpを生成し、Ｐ＝１＋（ＥＤp−１）／Ｋpを計算し、Ｐが素数となるまでこれを繰り返し、Ｑに関しても同様に実行する構成により、上記課題を解決する。
【解決手段】 鍵生成処理の最初に、Ｐ−１の素因子として含ませるｎrビットの素数Ｒを生成し、次にｎeビットの奇数Ｅを生成し、ｎe＋ｎ{d_p}−ｎp−ｎrビットの中間変数Ｋpを生成し、Ｄp＝Ｅ-1 ｍｏｄ ＫpＲを満たすｎ{d_p}ビットのＤpを生成し、Ｐ＝１＋（ＥＤp−１）／Ｋpを計算し、Ｐが素数となるまでこれを繰り返し、Ｑに関しても同様に実行する構成により、上記課題を解決する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵生成装置及びプログラムに係り、特に、ＲＳＡ（Rivest-Shamir-Adleman）暗号方式の鍵生成の際に、ｐ−１法に対する耐性を持った鍵を生成する鍵生成装置及びプログラムに関する。
【背景技術】
【０００２】
近年の情報通信において、暗号技術は欠かせない要素となってきている。このような暗号技術には、例えば、通信の暗号化技術であるＳＳＬ（Secure Socket Layer）や、メッセージが改ざんされていないことを検出できる電子署名などがある。これらは、ＰＫＩ（Public Key Infrastructure：公開鍵基盤）の一部として、社会の電子化を支える技術となっている。
【０００３】
ＰＫＩにおいては、ＲＳＡ暗号方式と呼ばれる公開鍵暗号方式が広く使われている。ＲＳＡ暗号方式では、次式に示すように、公開鍵Ｎ，Ｅ及び秘密鍵Ｄに基づいて、メッセージＭを暗号化して暗号文Ｃを作成し、また、暗号文ＣからメッセージＭを復号する。
【０００４】
暗号化：Ｃ＝ＭE ｍｏｄ Ｎ
復号 ：Ｍ＝ＣD ｍｏｄ Ｎ
ここで、公開鍵Ｎ，Ｅ及び秘密鍵Ｄの間には、２つの素数Ｐ，Ｑに基づく（１）式及び（２）式に示す関係がある。
【０００５】
Ｎ＝Ｐ×Ｑ （１）
ＥＤ＝１ ｍｏｄ （（Ｐ−１）（Ｑ−１）） （２）
ここで用いる鍵のビット数は、暗号解読を困難にするために十分大きい必要があり、現時点では公開鍵Ｎが１０２４ビット、あるいは２０４８ビットが推奨されている。
【０００６】
暗号化のベキ指数に用いる公開鍵Ｅは、通常、Ｅ＝６５５３７等の比較的小さな数が用いられる。そのため、高速に暗号化できるという特長がある。
【０００７】
一方、復号のベキ指数に用いる秘密鍵Ｄは、与えられた公開鍵Ｅに基づいて（２）式から算出される。（２）式から分かるように、公開鍵Ｅ及び秘密鍵Ｄは同時には小さくできず、一般的に秘密鍵Ｄは、法に用いる公開鍵Ｎと同程度の大きさの数となるため、復号処理の時間が長くかかる問題がある。
【０００８】
この問題を解消する観点から、ＣＲＴ（Chinese Remainder Theorem：中国剰余定理）を用いた高速化手法が提案されている。
【０００９】
ＣＲＴを用いたＲＳＡ復号は、以下に示すように、ＣＲＴ用の秘密鍵Ｄp，Ｄq及び逆元ｑInvを用い、暗号文ＣからメッセージＭを計算する手法である。
【００１０】
Ｍp＝Ｃ{D_p} ｍｏｄ Ｐ
Ｍq＝Ｃ{D_q} ｍｏｄ Ｑ
Ｍ＝（（（Ｍp−Ｍq）×ｑInv） ｍｏｄ Ｐ）×Ｑ＋Ｍq
なお、{D_p}の表記はＤpを表し、{D_q}の表記はＤqを表す。ＣＲＴ用の秘密鍵Ｄp，Ｄq及び逆元ｑInvと、ＲＳＡの秘密鍵Ｄ及び公開鍵Ｅとは、以下に示す関係がある。
【００１１】
Ｄp＝Ｄ ｍｏｄ （Ｐ−１）
Ｄq＝Ｄ ｍｏｄ （Ｑ−１）
ＥＤp＝１ ｍｏｄ （Ｐ−１） （３）
ＥＤq＝１ ｍｏｄ （Ｑ−１） （４）
ｑInv＝Ｑ-1 ｍｏｄ Ｐ
ＣＲＴを用いたＲＳＡ復号は、ＣＲＴを用いない場合と比較して３倍から４倍程度高速化されるが、小さなベキ指数Ｅを用いる暗号化と比較するとまだ低速である。
【００１２】
ここで、特許文献１には、ベキ指数Ｄp，Ｄqを先に小さな数として与え、復号を高速化する技術が記載されている。
【００１３】
しかしながら、特許文献１記載の技術は、暗号化の速度が低下してしまう問題がある。
【００１４】
このような暗号化速度の低下は、（３）式及び（４）式に基づき、公開鍵Ｅと、ＣＲＴ用の秘密鍵Ｄp，Ｄqとが同時には小さくできず、一般に、ベキ指数に用いる公開鍵Ｅが、法に用いる公開鍵Ｎと同程度の大きな数となることから生じる。また、特許文献１記載の技術は、ＣＲＴ用の秘密鍵Ｄp，Ｄqを小さくし過ぎると、鍵が鍵長の多項式時間で解読可能となることから（例えば、非特許文献１参照。）、鍵を適度な大きさとする必要がある。
【００１５】
これに対し、非特許文献２及び非特許文献３には、暗号化及び復号の処理速度をバランスさせるため、公開鍵Ｅと、ＣＲＴ用の秘密鍵Ｄp，Ｄqとを共に適度に小さい数で生成する、という技術が記載されている。
【００１６】
ここで、非特許文献２記載の技術のアルゴリズムを、図６を用いて説明する。
【００１７】
始めに、生成したい公開鍵Ｅのビット数ｎe、ＣＲＴ用の秘密鍵Ｄp，Ｄqのビット数ｎ{d_p}、素数Ｐ，Ｑのビット数ｎpを指定する（ステップＳ１）。
【００１８】
次に、ｎeビットの奇数Ｅをランダムに生成する（ステップＳ２）。
【００１９】
中間変数Ｋを、ｎe＋ｎ{d_p}−ｎpビットとなるようにランダムに生成する（ステップＳ３）。
【００２０】
ステップＳ２，Ｓ３で生成した奇数Ｅと中間変数Ｋを用いて、Ｄp＝Ｅ-1 ｍｏｄ Ｋを満たし、かつｎ{d_p}ビットとなるような秘密鍵Ｄpをランダムに生成する（ステップＳ４）。
【００２１】
ここで、秘密鍵Ｄpのビット数が中間変数Ｋのビット数より大きいことを仮定している。すなわち、ｎ{d_p}＞ｎe＋ｎ{d_p}−ｎpよりｎp＞ｎeを仮定している。この仮定に伴い、秘密鍵Ｄpは、ｍｏｄ Ｋでは一意的に定まるものの、ｎ{d_p}ビットのデータとしては多数存在するため、多数のデータからランダムに選択される。
【００２２】
これら奇数Ｅ，中間変数Ｋ，秘密鍵Ｄpを用い、整数ＰをＰ＝１＋（ＥＤp−１）／Ｋに基づいて算出する（ステップＳ５）。
【００２３】
ステップＳ４の式から（ＥＤp−１）／Ｋが整数であるため、算出結果Ｐは整数である。また、ＥＤp＝１＋Ｋ（Ｐ−１）なので、（３）式の条件を満たしている。
【００２４】
ステップＳ６では、このように構成した整数Ｐについて素数か否かを判定する。
判定の結果、整数Ｐが素数でない場合には、ステップＳ４に戻り、ＣＲＴ用の秘密鍵Ｄpを生成し直してステップＳ６で素数と判定されるまで、各ステップＳ４〜Ｓ６の処理をくり返す。
【００２５】
ステップＳ６の判定の結果、整数Ｐが素数の場合には、次の整数Ｑの生成に移る。整数Ｑの生成は、ステップＳ７，Ｓ８，Ｓ９，Ｓ１０で行われるが、これらは整数Ｐの生成におけるステップＳ３，Ｓ４，Ｓ５，Ｓ６にそれぞれ対応し、同様の処理となる。
【００２６】
以上の処理ステップにより生成された公開鍵Ｅ，秘密鍵Ｄp，Ｄq，素数Ｐ，ＱをＲＳＡ暗号方式の鍵データとして出力する。
【００２７】
以上のように、非特許文献２記載の技術によれば、指定したｎeビットの公開鍵Ｅと、ｎ{d_p}ビットの秘密鍵Ｄp，Ｄqと、ｎpビットの素数Ｐ，Ｑとを生成可能となっている。また、暗号化、復号が所望の処理速度比となるように、ビット数ｎe，ｎ{d_p}を指定することで、暗号化及び復号の処理速度をバランスさせることが可能である。これは非特許文献３記載の技術でも同様である。
【００２８】
ところで前述したように、ＲＳＡ暗号方式で用いる公開鍵Ｎのビット数は、暗号解読を困難にするために、１０２４ビットや２０４８ビットの大きさが推奨されている。すなわち、公開鍵Ｎのビット数は、公開鍵Ｎの素因数分解を困難にするために十分大きい必要がある。現時点で最速の素因数分解アルゴリズムは、公開鍵Ｎの大きさにのみ依存するからである。
【００２９】
その一方、公開鍵Ｎの素因子Ｐ，Ｑの形に特化した素因数分解法が知られている。このような素因数分解法の一つに、ｐ−１法と呼ばれる方法がある。ｐ−１法による素因数分解を回避するためには、Ｐ−１及びＱ−１を素因数分解した場合に、その素因子の中に大きな素因数を持つ必要がある。
【００３０】
なお、Ｐ−１及びＱ−１に大きな素因数を持たせるようにＲＳＡ暗号方式の鍵を生成する技術は特許文献２に記載されている。この技術においては、Ｐ−１に持たせたい素因数をＲとし、次の（５）式に示すように素数Ｐを構成している。
【００３１】
Ｐ＝１＋ａＲ （ａは乱数） （５）
【特許文献１】特開平３−６０２３７号公報
【特許文献２】特開平２−３７３８３号公報
【非特許文献１】E. Jochemsz, A. May, “A Polynomial Time Attack on Standard RSA with Private CRT-Exponents Smaller than N0.073”, Lecture Notes in Computer Sciences, Vol.4622, pp.395-411, 2007.
【非特許文献２】S. Galbraith, C. Heneghan, L. McKee, “Tunable Balancing of RSA”, http://www.isg.rhul.ac.uk/~sdg/full-tunable-rsa.pdf, 2005
【非特許文献３】H. M. Sun, M. J. Hinek, M. E. Wu, “On the Design of Rebalanced RSA-CRT”, http://www.cacr.math.uwaterloo.ca/techreports/2005/cacr2005-35.pdf, 2005
【非特許文献４】U. M. Maurer, “Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters”, Journal of Cryptology, Vol. 8, pp.123-155, 1995
【発明の開示】
【発明が解決しようとする課題】
【００３２】
しかしながら、非特許文献２，３記載の技術では、予め公開鍵Ｅ，秘密鍵Ｄp，Ｄqを定めてから素数Ｐ，Ｑを計算するため、特許文献２記載の技術とは異なり、大きな素因数を持つようにＰ−１及びＱ−１を構成できない。
【００３３】
従って、非特許文献２，３記載の技術では、Ｐ−１及びＱ−１に大きな素因数を持たせることが困難であり、ｐ−１法による素因数分解を回避できない状況にある。
【００３４】
本発明は上記実情を考慮してなされたもので、暗号化及び復号の処理速度をバランスさせるように鍵を生成できると共に、ｐ−１法による素因数分解を回避でき、より強固なＲＳＡ暗号方式の鍵を生成し得る鍵生成装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００３５】
本発明の一つの局面は、ＲＳＡ暗号方式の鍵データを生成するための鍵生成装置であって、前記鍵データとしての奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，Ｑと、当該鍵データを生成するための素数Ｒ及び中間変数Ｋp，Ｋqとを記憶するための記憶手段と、ビット数ｎe，ｎ{d_p}，ｎp，ｎrを指定するための手段と、前記ビット数ｎrの素数Ｒを生成し、この素数Ｒを前記記憶手段に書き込む手段と、前記ビット数ｎeの奇数Ｅをランダムに生成し、この奇数Ｅを前記記憶手段に書き込む手段と、前記ビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを前記記憶手段に書き込む手段と、前記記憶手段を参照しながら前記奇数Ｅ、前記第１中間変数Ｋp、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、前記ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを前記記憶手段に書き込む手段と、前記記憶手段を参照しながら前記奇数Ｅ、前記第１秘密鍵Ｄp及び前記第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する手段と、前記整数Ｐを素数判定する第１素数判定手段と、この素数判定の結果、前記整数Ｐが素数のとき、この素数Ｐを前記記憶手段に書き込む手段と、前記ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを前記記憶手段に書き込む手段と、前記記憶手段を参照しながら前記奇数Ｅ、前記第２中間変数Ｋq、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、前記ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを前記記憶手段に書き込む手段と、前記記憶手段を参照しながら前記奇数Ｅ、前記第２秘密鍵Ｄq及び前記第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する手段と、前記整数Ｑを素数判定する第２素数判定手段と、この素数判定の結果、前記整数Ｑが素数のとき、この素数Ｑを前記記憶手段に書き込む手段と、前記記憶手段を参照して前記奇数Ｅ、前記秘密鍵Ｄp，Ｄq及び前記素数Ｐ，Ｑを前記ＲＳＡ暗号方式の鍵データとして出力する手段と、を備えた鍵生成装置である。
【００３６】
なお、本発明の一つの局面は、装置として表現したが、これに限らず、方法、プログラム、プログラムを記憶したコンピュータ読み取り可能な記憶媒体として表現してもよい。
【００３７】
（作用）
本発明の一つの局面によれば、鍵生成処理の最初に、Ｐ−１の素因子として含ませるｎrビットの素数Ｒを生成し、次にｎeビットの奇数Ｅを生成し、ｎe＋ｎ{d_p}−ｎp−ｎrビットの中間変数Ｋpを生成し、Ｄp＝Ｅ-1 ｍｏｄ ＫpＲを満たすｎ{d_p}ビットのＤpを生成し、Ｐ＝１＋（ＥＤp−１）／Ｋpを計算し、Ｐが素数となるまでこれを繰り返し、Ｑに関しても同様に実行する構成により、非特許文献２の方法においてＰ−１に素因子Ｒを持たせることができるため、暗号化及び復号の処理速度をバランスさせるように鍵を生成できると共に、ｐ−１法による素因数分解を回避でき、より強固なＲＳＡ暗号方式の鍵を生成することができる。
【発明の効果】
【００３８】
以上説明したように本発明によれば、暗号化及び復号の処理速度をバランスさせるように鍵を生成できると共に、ｐ−１法による素因数分解を回避でき、より強固なＲＳＡ暗号方式の鍵を生成できる。
【発明を実施するための最良の形態】
【００３９】
以下、本発明の各実施形態について図面を用いて説明する。なお、以下の各実施形態は、本発明の具体例であり、本発明の技術的範囲を限定するものではない。
【００４０】
（第１の実施形態）
図１は本発明の第１の実施形態に係る鍵生成装置の構成を示す模式図である。この鍵生成装置１００は、ＩＣカード又はＰＣ（Personal Computer）などの計算機の鍵生成部として構成されており、ハードウェア構成、又はハードウェア資源とソフトウェアの組み合わせ構成により、ＲＳＡ方式の鍵データを生成する処理を実行する。組み合わせ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から鍵生成装置１００にインストールされ、鍵生成装置１００の各機能を実現させるためのプログラムが用いられる。
【００４１】
鍵生成装置１００は、具体的には入出力部１０１、ＣＰＵ（中央演算装置）１０２、プログラム記憶部１０３、乱数生成部１０４、ランダムアクセス可能な揮発性メモリ１０５、不揮発性メモリ１０６、アドレス及びデータバス１０７を備えている。
【００４２】
入出力部１０１は、鍵生成装置１００の外部の計算機等と、鍵生成装置１００のバス１０７との間でデータを入出力するためのインターフェイス部であり、例えば、以下の各機能(f101-1)〜(f101-2)を実現するものである。
【００４３】
(f101-1) 外部から入力されたビット数ｎe，ｎ{d_p}，ｎp，ｎrを指定するための機能。
【００４４】
(f101-2) ＣＰＵ１０２から受けた奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，Ｑを出力する機能。
【００４５】
ＣＰＵ１０２は、プログラム記憶部１０３に格納されたプログラムを実行することにより、以下の各機能(f102-1)〜(f102-10)を実現するものである。このプログラムは、鍵生成のためのサブプログラムを少なくとも含んでいる。
【００４６】
(f102-1) 入出力部１０１により指定されたビット数ｎe，ｎ{d_p}，ｎp，ｎrのうち、ビット数ｎrの素数Ｒを生成し、この素数Ｒを揮発性メモリ１０５に書き込む機能。
【００４７】
(f102-2) 揮発性メモリ１０５を参照しながら奇数Ｅ、第１中間変数Ｋp、素数Ｒ及びビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを揮発性メモリ１０５に書き込む機能。
【００４８】
(f102-3) 揮発性メモリ１０５を参照しながら奇数Ｅ、第１秘密鍵Ｄp及び第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する機能。
【００４９】
(f102-4) 整数Ｐを素数判定する第１素数判定機能。
【００５０】
(f102-5) この素数判定の結果、整数Ｐが素数のとき、この素数Ｐを揮発性メモリ１０５に書き込む機能。
【００５１】
(f102-6) 揮発性メモリ１０５を参照しながら奇数Ｅ、第２中間変数Ｋq、素数Ｒ及びビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを揮発性メモリ１０５に書き込む機能。
【００５２】
(f102-7) 揮発性メモリ１０５を参照しながら奇数Ｅ、第２秘密鍵Ｄq及び第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する機能。
【００５３】
(f102-8) 整数Ｑを素数判定する第２素数判定機能。
【００５４】
(f102-9) この素数判定の結果、整数Ｑが素数のとき、この素数Ｑを揮発性メモリ１０５に書き込む機能。
【００５５】
(f102-10) 揮発性メモリ１０５を参照して奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，ＱをＲＳＡ暗号方式の鍵データとして入出力部１０１から出力する機能。
【００５６】
プログラム記憶部１０３は、例えばＲＯＭ（リードオンリーメモリ）であり、図２に示す各機能を鍵生成装置１０１に実現させるためのプログラムを記憶している。このプログラムは、外部からプログラム記憶部１０３にインストールしてもよい。
【００５７】
乱数生成部１０４は、以下の各機能(f104-1)〜(f104-3)をもっている。
【００５８】
(f104-1) 入出力部１０１により指定されたビット数ｎeの奇数Ｅをランダムに生成し、この奇数Ｅを揮発性メモリ１０５に書き込む機能。
【００５９】
(f104-2) 入出力部１０１により指定されたビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを揮発性メモリ１０５に書き込む機能。
【００６０】
(f104-3) このビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを揮発性メモリ１０５に書き込む機能。
【００６１】
ここで、乱数生成部１０４は、ＣＰＵ１０２に使用されるハードウェア資源として実現してもよく、ＣＰＵ１０２とプログラムで実現してもよい。さらに乱数生成部１０４を省略し、外部で生成した乱数を入出力部１０１から入力する構成に変形してもよい。本実施形態では、ＣＰＵ１０２とプログラムによる乱数生成部１０４を用いるものとする。
【００６２】
揮発性メモリ１０５は、例えばＲＡＭ（ランダムアクセスメモリ）等のランダムアクセス可能な記憶装置であり、計算に必要なデータや計算途中のデータなどが格納される。
【００６３】
不揮発性メモリ１０６は、例えばＥＥＰＲＯＭ（Electric Erasable Programmable ROM）等の記憶装置であり、生成された鍵データなどが格納される。
【００６４】
次に、以上のように構成された鍵生成装置の動作を図２のフローチャートを用いて説明する。
【００６５】
鍵生成装置１００においては、ユーザによる外部計算機の操作により、入出力部１０１が、公開鍵Ｅのビット数ｎe、ＣＲＴ用の秘密鍵Ｄp，Ｄqのビット数ｎ{d_p}、素数Ｐ，Ｑのビット数ｎp、及びＰ−１，Ｑ−１に持たせたい素因子Ｒのビット数ｎrを指定する（ステップＳ１１）。
【００６６】
続いて、ＣＰＵ１０２は、ｎrビットの素数Ｒを生成し、この素数Ｒを揮発性メモリ１０５に書き込む（ステップＳ１２）。
【００６７】
また、乱数生成部１０４は、ｎeビットの奇数Ｅをランダムに生成し、この奇数Ｅを揮発性メモリ１０５に書き込む（ステップＳ１３）。
【００６８】
次に、乱数生成部１０４は、入出力部１０１により指定されたビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを揮発性メモリ１０５に書き込む（ステップＳ１４）。 ＣＰＵ１０２は、揮発性メモリ１０５を参照しながら奇数Ｅ、第１中間変数Ｋp、素数Ｒ及びビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを揮発性メモリ１０５に書き込む（ステップＳ１５）。
【００６９】
ここで、第１秘密鍵Ｄpのビット数（ｎ{d_p}）は、ＫpＲのビット数（（ｎe＋ｎ{d_p}−ｎp−ｎr）＋ｎr）より大きいことを仮定している。すなわち、ｎ{d_p}＞（ｎe＋ｎ{d_p}−ｎp−ｎr）＋ｎrよりｎp＞ｎeを仮定している。この条件は、非特許文献２に課せられている条件と同じである。このように仮定すると、第１秘密鍵Ｄpは、ｍｏｄ ＫpＲでは一意的に定まるが、ｎ{d_p}ビットのデータとしては多数存在するため、この中から１つランダムに選択（＝生成）され、揮発性メモリ１０５に書き込まれる。
【００７０】
ＣＰＵ１０２は、揮発性メモリ１０５を参照しながら奇数Ｅ、第１秘密鍵Ｄp及び第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する（ステップＳ１６）。
【００７１】
ＣＰＵ１０２は、このように構成した整数Ｐが素数か否かを判定し（ステップＳ１７）、この素数判定の結果、否の場合には、ステップＳ１５に戻り、第１秘密鍵Ｄpを生成し直して、ステップＳ１７で素数と判定されるまでくり返す。
【００７２】
ＣＰＵ１０２は、ステップＳ１７の判定の結果、整数Ｐが素数のときには、この素数Ｐを揮発性メモリ１０５に書き込む。
【００７３】
続いて、鍵生成装置１００は素数Ｑの生成に移る。
鍵生成装置１００においては、乱数生成部１０４が、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを揮発性メモリ１０５に書き込む（ステップＳ１８）。
【００７４】
ＣＰＵ１０２は、揮発性メモリ１０５を参照しながら奇数Ｅ、第２中間変数Ｋq、素数Ｒ及びビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを揮発性メモリ１０５に書き込む（ステップＳ１９）。このとき、ステップＳ１５と同様に、第２秘密鍵Ｄqは、ｍｏｄ ＫqＲでは一意的に定まるが、ｎ{d_p}ビットのデータとしては多数存在するため、この中から１つランダムに選択（＝生成）され、揮発性メモリ１０５に書き込まれる。
【００７５】
ＣＰＵ１０２は、揮発性メモリ１０５を参照しながら奇数Ｅ、第２秘密鍵Ｄq及び第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する（ステップＳ２０）。
【００７６】
ＣＰＵ１０２は、このように構成した整数Ｑが素数か否かを判定し（ステップＳ２１）、この素数判定の結果、否の場合には、ステップＳ１９に戻り、第２秘密鍵Ｄqを生成し直して、ステップＳ２１で素数と判定されるまでくり返す。
【００７７】
ＣＰＵ１０２は、ステップＳ２１の判定の結果、整数Ｑが素数のときには、この素数Ｑを揮発性メモリ１０５に書き込む。
【００７８】
ＣＰＵ１０２は、以上の処理ステップの完了後、揮発性メモリ１０５を参照して奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，ＱをＲＳＡ暗号方式の鍵データとして入出力部１０１から出力する。また、ＣＰＵ１０２は、これら鍵データを不揮発性メモリ１０６に書き込む。なお、図２に図示していないが、ＣＰＵ１０２は、さらにＮ＝ＰＱ及びＤ＝Ｅ-1 ｍｏｄ （（Ｐ−１）（Ｑ−１））を計算して、これらＮ，Ｄを合わせてＲＳＡ暗号方式の鍵として出力してもよい。
【００７９】
このようにして生成された素数Ｐ，Ｑは、Ｐ−１，Ｑ−１に素因子Ｒを持つことが、以下のように確かめられる。
【００８０】
まずステップＳ１５の構成の仕方より、Ｄp＝Ｅ-1 ｍｏｄ ＫpＲである。これはＥＤp−１＝０ ｍｏｄ ＫpＲ、すなわちＥＤp−１がＫpＲの倍数であることを意味する。
【００８１】
一方、ステップＳ１６の構成の仕方より、Ｐ＝１＋（ＥＤp−１）／Ｋpである。変形するとＰ−１＝（ＥＤp−１）／Ｋpとなるが、上記よりＥＤp−１は、ＫpＲの倍数であるので、（ＥＤp−１）／Ｋpは、素数Ｒの倍数となる。従って、Ｐ−１は素数Ｒを素因子として持つ。
【００８２】
素数Ｑに関しても同様である。
従って、ｐ−１法に対する耐性を持つように素数Ｒのビット数ｎrを指定した上で、本実施形態を実施することにより、暗号化と復号の処理時間をバランスするように鍵を生成可能であり、さらにＰ−１、Ｑ−１に大きな素因子を持たせることができるため、より強固なＲＳＡ暗号方式の鍵を生成することができる。
【００８３】
ただし、ステップＳ１４，Ｓ１８で生成する中間変数Ｋp，Ｋqのビット数が正となるためには、ｎe＋ｎ{d_p}−ｎp−ｎr＞０でなければならない。非特許文献２の３章に記載されている２つのパラメータ例
ｎe＝１６０，ｎ{d_p}＝３５４，ｎp＝５１２
ｎe＝５１２，ｎ{d_p}＝２６９，ｎp＝５１２
にあてはめると、前者の場合はｎr＜２となり、素数Ｒが選べないため、本実施形態で説明したアルゴリズムは非特許文献２と同じものとなる。後者の場合はｎr＜２６９であるため、十分大きな（例えばｎpの半分のビットサイズｎr＝２５６）を選ぶことができるため、本実施形態が有用であることが確かめられる。
【００８４】
上述したように本実施形態によれば、鍵生成処理の最初に、Ｐ−１の素因子として含ませるｎrビットの素数Ｒを生成し、次にｎeビットの奇数Ｅを生成し、ｎe＋ｎ{d_p}−ｎp−ｎrビットの中間変数Ｋpを生成し、Ｄp＝Ｅ-1 ｍｏｄ ＫpＲを満たすｎ{d_p}ビットのＤpを生成し、Ｐ＝１＋（ＥＤp−１）／Ｋpを計算し、Ｐが素数となるまでこれを繰り返し、Ｑに関しても同様に実行する構成により、非特許文献２の方法においてＰ−１に素因子Ｒを持たせることができるため、暗号化と復号の処理時間をバランスするように鍵を生成でき、さらにＰ−１法に強い鍵を生成できる。
【００８５】
さらに、Ｐ−１，Ｑ−１に大きな既知の素因数Ｒを持たせることが可能となるために、整数Ｐの素数判定に確定的判定方法を使用でき、もって、正しいＲＳＡ暗号方式の鍵を生成することができる。
【００８６】
なお、本実施形態は、図３又は図４に示すように変形してもよい。
図３に示す処理は、図２に示すステップＳ１２に代えて、互いに異なる素数Ｒp，Ｒqを算出するステップＳ１２ａ，Ｓ１２ｂを設け、図２に示すステップＳ１５，Ｓ１９のｍｏｄ ＫpＲ，ｍｏｄ ＫqＲに代えて、ステップＳ１５’ではｍｏｄ ＫpＲpとし、ステップＳ１９’ではｍｏｄ ＫqＲqとしたものである。
【００８７】
この変形により、図２ではＰ−１，Ｑ−１に同じ素因子Ｒを持たせるように構成していたが、図３ではＰ−１に素因子Ｒpを、Ｑ−１に素因子Ｒqを、と異なる素因子を持たせることができる。また、図３に示す処理に変形しても、本実施形態を同様に実施して同様の効果を得ることに加え、Ｐ−１，Ｑ−１に異なる素因子Ｒp，Ｒqを持たせることから、より強固な鍵を生成することができる。
【００８８】
図４に示す処理は、図３に示した処理の更なる変形例である。
図３におけるステップＳ１７，Ｓ２１において、整数ＰあるいはＱが素数でないと判定されたときにそれぞれステップＳ１５’，Ｓ１９’に戻っていたが、図４のように、それぞれステップＳ１４，Ｓ１８に戻ってもよい。このように図４に示す処理に変形しても、図３に示す処理を同様に実施して同様の効果を得ることができる。
【００８９】
（第２の実施形態）
次に、本発明の第２の実施形態に係る鍵生成装置について説明するが、前述した図面と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００９０】
すなわち、第２の実施形態は、第１の実施形態の素数判定処理において、確定的素数判定方法を用いて素数判定を実行する形態であり、具体的には、鍵生成装置１００が、図２に示したステップＳ１１，Ｓ１２，Ｓ１７，Ｓ２１の処理を以下のように実行している。
【００９１】
ステップＳ１１においては、ビット数ｎp，ｎrを指定する際に、２ｎr＞ｎpの関係を満たすようにする。例えば、非特許文献２の３章記載の２番目のパラメータ例に示すように、ビット数ｎp，ｎrを指定する。具体的には例えば、入出力部１０１としては、ビット数ｎp，ｎrが指定されたとき、２ｎr＞ｎpの関係を満たすか否かを判定し、満たさない場合には関係を満たすようなビット数を再入力するように促す構成としてもよい。
【００９２】
また、ステップＳ１２の処理は特に変更は無いが、整数Ｒが素数である必要があるため、整数Ｒの素数判定に確定的素数判定方法を用いている。確定的素数判定方法は、例えば非特許文献４に記載の方法などにより実現される。
【００９３】
ステップＳ１７においては、整数Ｐを素数判定する際に、確定的素数判定方法であるポクリントン（Pocklington）の定理の特別な場合を用いる。
【００９４】
ポクリントンの定理の特別な場合は、以下のような定理であり、確率的素数判定方法としてよく利用されるミラー・ラビン（Miller-Rabin）法と同等の処理速度で素数判定を実行可能である。
【００９５】
整数ＰがＰ＝ＡＲ＋１，ＲはＲ＞√Ｐを満たす素数、という形をしていると仮定する。このとき、次の２条件を満たす整数ａが存在すれば、整数Ｐは素数である。
【００９６】
条件１：ａp-1＝１ ｍｏｄ Ｐ
条件２：ｇｃｄ（ａ(p-1)/R−１，Ｐ）＝１
ここで、ｇｃｄは最大公約数を表す。
【００９７】
ステップＳ１７の素数判定対象であるＰ＝１＋（ＥＤp−１）／Ｋpは、ある整数をＡとしたとき、ステップＳ１６の式中の（ＥＤp−１）／ＫpがステップＳ１２で生成した素数ＲのＡ倍であることから、Ｐ＝１＋ＡＲという形をしている。また、ステップＳ１１で２ｎr＞ｎpを満たすパラメータを指定したため、素数ＲがＲ＞√Ｐという形をしている。このため、本実施形態の素数判定対象Ｐ及び素数Ｒは、ポクリントンの定理の特別な場合の仮定を満たしている。
【００９８】
従って、ステップＳ１７においては、ＣＰＵ１０２は、ポクリントンの定理の特別な場合を利用し、条件１，２を満たす整数ａが存在すれば、整数Ｐを素数であると判定する。具体的には図５に示すように、ＣＰＵ１０２は、乱数生成部１０４により、整数ａをランダムに生成する（Ｓ１７−１）。なお、ＣＰＵ１０２は、整数ａをランダムに生成せずに、固定値（例えばａ＝２）の整数ａを用いるように変形してもよい。
【００９９】
次に、ＣＰＵ１０２は、ポクリントンの定理の特別な場合の条件１を検査する（ステップＳ１７−２）。ここで検査に失敗した場合（図５におけるＮｏ）、ＣＰＵ１０２は、整数Ｐを合成数と判定し（ステップＳ１７−５）、処理を終了する。
【０１００】
条件１の検査に成功した場合（図５におけるＹｅｓ）、ＣＰＵ１０２は、条件２を検査する（ステップＳ１７−３）。条件２の検査に失敗した場合、ＣＰＵ１０２は、整数Ｐを合成数と判定し（ステップＳ１７−５）、処理を終了する。
【０１０１】
条件２の検査に成功した場合、ＣＰＵ１０２は、整数Ｐを素数と判定し（ステップＳ１７−４）、処理を終了する。
【０１０２】
ステップＳ２１においては、ステップＳ１７−１〜Ｓ１７−５と同様にして、ＣＰＵ１０２は、整数Ｑの素数判定を実行する。
【０１０３】
上述したように本実施形態によれば、第１の実施形態の効果に加え、ミラー・ラビン法と同等の処理速度をもつ確定的素数判定方法を用いて整数Ｐ，Ｑを素数判定できるので、正しいＲＳＡ暗号方式の鍵を生成する有用な鍵生成方法を実現することができる。
【０１０４】
ここで、素数判定方法について補足的に説明する。
整数Ｐ，Ｑが素数であるか否かを判定する方法としては、大きく分けて確率的素数判定方法と確定的素数判定方法との２種類の方法が知られている。
【０１０５】
確率的素数判定方法は、合成数と判定された数については確実に合成数であるが、ある確率で合成数を誤って素数と判定することがある。
【０１０６】
確定的素数判定方法は、素数と判定された数が確実に素数であるという特徴をもつ。素数判定対象の数が特殊な構造の場合（例えば（５）式でＲが既知で、ａ＜Ｒの場合）には、確定的素数判定方法は十分高速に実行できる。
【０１０７】
一方、素数判定対象が一般の数の場合には、確定的素数判定方法では処理速度が遅く、実用に耐えないため、通常は確率的素数判定方法が用いられる。但し、確率的素数判定方法は、合成数を誤って素数と判定する確率が０ではないため、合成数を誤ってＲＳＡ暗号方式の鍵として使用する場合に、暗号文を復号できない等の問題が発生する。ここで、非特許文献２，３記載の技術では、整数Ｐ，Ｑに構造を持たせることが困難なため、確定的素数判定方法を使用できず、確率的素数判定方法を使用する必要があるので、０でない確率で暗号文を復号できない心配が残る。
【０１０８】
しかしながら、本実施形態によれば、確定的素数判定方法を使用できるので、合成数を誤って素数と判定する確率をゼロにでき、暗号文を復号できない心配を解消することができる。
【０１０９】
なお、本実施形態における確定的素数判定方法は、図３及び図４に示した変形例にも適用でき、同様の効果を得ることができる。
【０１１０】
また、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１１１】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１１２】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１１３】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【０１１４】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１５】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１１６】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１１７】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１１８】
【図１】本発明の第１の実施形態に係る鍵生成装置の構成を示す模式図である。
【図２】同実施形態における動作を説明するためのフローチャートである。
【図３】同実施形態における動作の変形例を説明するためのフローチャートである。
【図４】同実施形態における動作の他の変形例を説明するためのフローチャートである。
【図５】本発明の第２の実施形態に係る鍵生成装置における確定的素数判定動作を説明するためのフローチャートである。
【図６】従来の鍵生成の動作を説明するためのフローチャートである。
【符号の説明】
【０１１９】
１００…鍵生成装置、１０１…入出力部、１０２…ＣＰＵ、１０３…プログラム記憶部、１０４…乱数生成部、１０５…揮発性メモリ、１０６…不揮発性メモリ、１０７…バス。
【技術分野】
【０００１】
本発明は、鍵生成装置及びプログラムに係り、特に、ＲＳＡ（Rivest-Shamir-Adleman）暗号方式の鍵生成の際に、ｐ−１法に対する耐性を持った鍵を生成する鍵生成装置及びプログラムに関する。
【背景技術】
【０００２】
近年の情報通信において、暗号技術は欠かせない要素となってきている。このような暗号技術には、例えば、通信の暗号化技術であるＳＳＬ（Secure Socket Layer）や、メッセージが改ざんされていないことを検出できる電子署名などがある。これらは、ＰＫＩ（Public Key Infrastructure：公開鍵基盤）の一部として、社会の電子化を支える技術となっている。
【０００３】
ＰＫＩにおいては、ＲＳＡ暗号方式と呼ばれる公開鍵暗号方式が広く使われている。ＲＳＡ暗号方式では、次式に示すように、公開鍵Ｎ，Ｅ及び秘密鍵Ｄに基づいて、メッセージＭを暗号化して暗号文Ｃを作成し、また、暗号文ＣからメッセージＭを復号する。
【０００４】
暗号化：Ｃ＝ＭE ｍｏｄ Ｎ
復号 ：Ｍ＝ＣD ｍｏｄ Ｎ
ここで、公開鍵Ｎ，Ｅ及び秘密鍵Ｄの間には、２つの素数Ｐ，Ｑに基づく（１）式及び（２）式に示す関係がある。
【０００５】
Ｎ＝Ｐ×Ｑ （１）
ＥＤ＝１ ｍｏｄ （（Ｐ−１）（Ｑ−１）） （２）
ここで用いる鍵のビット数は、暗号解読を困難にするために十分大きい必要があり、現時点では公開鍵Ｎが１０２４ビット、あるいは２０４８ビットが推奨されている。
【０００６】
暗号化のベキ指数に用いる公開鍵Ｅは、通常、Ｅ＝６５５３７等の比較的小さな数が用いられる。そのため、高速に暗号化できるという特長がある。
【０００７】
一方、復号のベキ指数に用いる秘密鍵Ｄは、与えられた公開鍵Ｅに基づいて（２）式から算出される。（２）式から分かるように、公開鍵Ｅ及び秘密鍵Ｄは同時には小さくできず、一般的に秘密鍵Ｄは、法に用いる公開鍵Ｎと同程度の大きさの数となるため、復号処理の時間が長くかかる問題がある。
【０００８】
この問題を解消する観点から、ＣＲＴ（Chinese Remainder Theorem：中国剰余定理）を用いた高速化手法が提案されている。
【０００９】
ＣＲＴを用いたＲＳＡ復号は、以下に示すように、ＣＲＴ用の秘密鍵Ｄp，Ｄq及び逆元ｑInvを用い、暗号文ＣからメッセージＭを計算する手法である。
【００１０】
Ｍp＝Ｃ{D_p} ｍｏｄ Ｐ
Ｍq＝Ｃ{D_q} ｍｏｄ Ｑ
Ｍ＝（（（Ｍp−Ｍq）×ｑInv） ｍｏｄ Ｐ）×Ｑ＋Ｍq
なお、{D_p}の表記はＤpを表し、{D_q}の表記はＤqを表す。ＣＲＴ用の秘密鍵Ｄp，Ｄq及び逆元ｑInvと、ＲＳＡの秘密鍵Ｄ及び公開鍵Ｅとは、以下に示す関係がある。
【００１１】
Ｄp＝Ｄ ｍｏｄ （Ｐ−１）
Ｄq＝Ｄ ｍｏｄ （Ｑ−１）
ＥＤp＝１ ｍｏｄ （Ｐ−１） （３）
ＥＤq＝１ ｍｏｄ （Ｑ−１） （４）
ｑInv＝Ｑ-1 ｍｏｄ Ｐ
ＣＲＴを用いたＲＳＡ復号は、ＣＲＴを用いない場合と比較して３倍から４倍程度高速化されるが、小さなベキ指数Ｅを用いる暗号化と比較するとまだ低速である。
【００１２】
ここで、特許文献１には、ベキ指数Ｄp，Ｄqを先に小さな数として与え、復号を高速化する技術が記載されている。
【００１３】
しかしながら、特許文献１記載の技術は、暗号化の速度が低下してしまう問題がある。
【００１４】
このような暗号化速度の低下は、（３）式及び（４）式に基づき、公開鍵Ｅと、ＣＲＴ用の秘密鍵Ｄp，Ｄqとが同時には小さくできず、一般に、ベキ指数に用いる公開鍵Ｅが、法に用いる公開鍵Ｎと同程度の大きな数となることから生じる。また、特許文献１記載の技術は、ＣＲＴ用の秘密鍵Ｄp，Ｄqを小さくし過ぎると、鍵が鍵長の多項式時間で解読可能となることから（例えば、非特許文献１参照。）、鍵を適度な大きさとする必要がある。
【００１５】
これに対し、非特許文献２及び非特許文献３には、暗号化及び復号の処理速度をバランスさせるため、公開鍵Ｅと、ＣＲＴ用の秘密鍵Ｄp，Ｄqとを共に適度に小さい数で生成する、という技術が記載されている。
【００１６】
ここで、非特許文献２記載の技術のアルゴリズムを、図６を用いて説明する。
【００１７】
始めに、生成したい公開鍵Ｅのビット数ｎe、ＣＲＴ用の秘密鍵Ｄp，Ｄqのビット数ｎ{d_p}、素数Ｐ，Ｑのビット数ｎpを指定する（ステップＳ１）。
【００１８】
次に、ｎeビットの奇数Ｅをランダムに生成する（ステップＳ２）。
【００１９】
中間変数Ｋを、ｎe＋ｎ{d_p}−ｎpビットとなるようにランダムに生成する（ステップＳ３）。
【００２０】
ステップＳ２，Ｓ３で生成した奇数Ｅと中間変数Ｋを用いて、Ｄp＝Ｅ-1 ｍｏｄ Ｋを満たし、かつｎ{d_p}ビットとなるような秘密鍵Ｄpをランダムに生成する（ステップＳ４）。
【００２１】
ここで、秘密鍵Ｄpのビット数が中間変数Ｋのビット数より大きいことを仮定している。すなわち、ｎ{d_p}＞ｎe＋ｎ{d_p}−ｎpよりｎp＞ｎeを仮定している。この仮定に伴い、秘密鍵Ｄpは、ｍｏｄ Ｋでは一意的に定まるものの、ｎ{d_p}ビットのデータとしては多数存在するため、多数のデータからランダムに選択される。
【００２２】
これら奇数Ｅ，中間変数Ｋ，秘密鍵Ｄpを用い、整数ＰをＰ＝１＋（ＥＤp−１）／Ｋに基づいて算出する（ステップＳ５）。
【００２３】
ステップＳ４の式から（ＥＤp−１）／Ｋが整数であるため、算出結果Ｐは整数である。また、ＥＤp＝１＋Ｋ（Ｐ−１）なので、（３）式の条件を満たしている。
【００２４】
ステップＳ６では、このように構成した整数Ｐについて素数か否かを判定する。
判定の結果、整数Ｐが素数でない場合には、ステップＳ４に戻り、ＣＲＴ用の秘密鍵Ｄpを生成し直してステップＳ６で素数と判定されるまで、各ステップＳ４〜Ｓ６の処理をくり返す。
【００２５】
ステップＳ６の判定の結果、整数Ｐが素数の場合には、次の整数Ｑの生成に移る。整数Ｑの生成は、ステップＳ７，Ｓ８，Ｓ９，Ｓ１０で行われるが、これらは整数Ｐの生成におけるステップＳ３，Ｓ４，Ｓ５，Ｓ６にそれぞれ対応し、同様の処理となる。
【００２６】
以上の処理ステップにより生成された公開鍵Ｅ，秘密鍵Ｄp，Ｄq，素数Ｐ，ＱをＲＳＡ暗号方式の鍵データとして出力する。
【００２７】
以上のように、非特許文献２記載の技術によれば、指定したｎeビットの公開鍵Ｅと、ｎ{d_p}ビットの秘密鍵Ｄp，Ｄqと、ｎpビットの素数Ｐ，Ｑとを生成可能となっている。また、暗号化、復号が所望の処理速度比となるように、ビット数ｎe，ｎ{d_p}を指定することで、暗号化及び復号の処理速度をバランスさせることが可能である。これは非特許文献３記載の技術でも同様である。
【００２８】
ところで前述したように、ＲＳＡ暗号方式で用いる公開鍵Ｎのビット数は、暗号解読を困難にするために、１０２４ビットや２０４８ビットの大きさが推奨されている。すなわち、公開鍵Ｎのビット数は、公開鍵Ｎの素因数分解を困難にするために十分大きい必要がある。現時点で最速の素因数分解アルゴリズムは、公開鍵Ｎの大きさにのみ依存するからである。
【００２９】
その一方、公開鍵Ｎの素因子Ｐ，Ｑの形に特化した素因数分解法が知られている。このような素因数分解法の一つに、ｐ−１法と呼ばれる方法がある。ｐ−１法による素因数分解を回避するためには、Ｐ−１及びＱ−１を素因数分解した場合に、その素因子の中に大きな素因数を持つ必要がある。
【００３０】
なお、Ｐ−１及びＱ−１に大きな素因数を持たせるようにＲＳＡ暗号方式の鍵を生成する技術は特許文献２に記載されている。この技術においては、Ｐ−１に持たせたい素因数をＲとし、次の（５）式に示すように素数Ｐを構成している。
【００３１】
Ｐ＝１＋ａＲ （ａは乱数） （５）
【特許文献１】特開平３−６０２３７号公報
【特許文献２】特開平２−３７３８３号公報
【非特許文献１】E. Jochemsz, A. May, “A Polynomial Time Attack on Standard RSA with Private CRT-Exponents Smaller than N0.073”, Lecture Notes in Computer Sciences, Vol.4622, pp.395-411, 2007.
【非特許文献２】S. Galbraith, C. Heneghan, L. McKee, “Tunable Balancing of RSA”, http://www.isg.rhul.ac.uk/~sdg/full-tunable-rsa.pdf, 2005
【非特許文献３】H. M. Sun, M. J. Hinek, M. E. Wu, “On the Design of Rebalanced RSA-CRT”, http://www.cacr.math.uwaterloo.ca/techreports/2005/cacr2005-35.pdf, 2005
【非特許文献４】U. M. Maurer, “Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters”, Journal of Cryptology, Vol. 8, pp.123-155, 1995
【発明の開示】
【発明が解決しようとする課題】
【００３２】
しかしながら、非特許文献２，３記載の技術では、予め公開鍵Ｅ，秘密鍵Ｄp，Ｄqを定めてから素数Ｐ，Ｑを計算するため、特許文献２記載の技術とは異なり、大きな素因数を持つようにＰ−１及びＱ−１を構成できない。
【００３３】
従って、非特許文献２，３記載の技術では、Ｐ−１及びＱ−１に大きな素因数を持たせることが困難であり、ｐ−１法による素因数分解を回避できない状況にある。
【００３４】
本発明は上記実情を考慮してなされたもので、暗号化及び復号の処理速度をバランスさせるように鍵を生成できると共に、ｐ−１法による素因数分解を回避でき、より強固なＲＳＡ暗号方式の鍵を生成し得る鍵生成装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００３５】
本発明の一つの局面は、ＲＳＡ暗号方式の鍵データを生成するための鍵生成装置であって、前記鍵データとしての奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，Ｑと、当該鍵データを生成するための素数Ｒ及び中間変数Ｋp，Ｋqとを記憶するための記憶手段と、ビット数ｎe，ｎ{d_p}，ｎp，ｎrを指定するための手段と、前記ビット数ｎrの素数Ｒを生成し、この素数Ｒを前記記憶手段に書き込む手段と、前記ビット数ｎeの奇数Ｅをランダムに生成し、この奇数Ｅを前記記憶手段に書き込む手段と、前記ビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを前記記憶手段に書き込む手段と、前記記憶手段を参照しながら前記奇数Ｅ、前記第１中間変数Ｋp、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、前記ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを前記記憶手段に書き込む手段と、前記記憶手段を参照しながら前記奇数Ｅ、前記第１秘密鍵Ｄp及び前記第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する手段と、前記整数Ｐを素数判定する第１素数判定手段と、この素数判定の結果、前記整数Ｐが素数のとき、この素数Ｐを前記記憶手段に書き込む手段と、前記ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを前記記憶手段に書き込む手段と、前記記憶手段を参照しながら前記奇数Ｅ、前記第２中間変数Ｋq、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、前記ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを前記記憶手段に書き込む手段と、前記記憶手段を参照しながら前記奇数Ｅ、前記第２秘密鍵Ｄq及び前記第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する手段と、前記整数Ｑを素数判定する第２素数判定手段と、この素数判定の結果、前記整数Ｑが素数のとき、この素数Ｑを前記記憶手段に書き込む手段と、前記記憶手段を参照して前記奇数Ｅ、前記秘密鍵Ｄp，Ｄq及び前記素数Ｐ，Ｑを前記ＲＳＡ暗号方式の鍵データとして出力する手段と、を備えた鍵生成装置である。
【００３６】
なお、本発明の一つの局面は、装置として表現したが、これに限らず、方法、プログラム、プログラムを記憶したコンピュータ読み取り可能な記憶媒体として表現してもよい。
【００３７】
（作用）
本発明の一つの局面によれば、鍵生成処理の最初に、Ｐ−１の素因子として含ませるｎrビットの素数Ｒを生成し、次にｎeビットの奇数Ｅを生成し、ｎe＋ｎ{d_p}−ｎp−ｎrビットの中間変数Ｋpを生成し、Ｄp＝Ｅ-1 ｍｏｄ ＫpＲを満たすｎ{d_p}ビットのＤpを生成し、Ｐ＝１＋（ＥＤp−１）／Ｋpを計算し、Ｐが素数となるまでこれを繰り返し、Ｑに関しても同様に実行する構成により、非特許文献２の方法においてＰ−１に素因子Ｒを持たせることができるため、暗号化及び復号の処理速度をバランスさせるように鍵を生成できると共に、ｐ−１法による素因数分解を回避でき、より強固なＲＳＡ暗号方式の鍵を生成することができる。
【発明の効果】
【００３８】
以上説明したように本発明によれば、暗号化及び復号の処理速度をバランスさせるように鍵を生成できると共に、ｐ−１法による素因数分解を回避でき、より強固なＲＳＡ暗号方式の鍵を生成できる。
【発明を実施するための最良の形態】
【００３９】
以下、本発明の各実施形態について図面を用いて説明する。なお、以下の各実施形態は、本発明の具体例であり、本発明の技術的範囲を限定するものではない。
【００４０】
（第１の実施形態）
図１は本発明の第１の実施形態に係る鍵生成装置の構成を示す模式図である。この鍵生成装置１００は、ＩＣカード又はＰＣ（Personal Computer）などの計算機の鍵生成部として構成されており、ハードウェア構成、又はハードウェア資源とソフトウェアの組み合わせ構成により、ＲＳＡ方式の鍵データを生成する処理を実行する。組み合わせ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から鍵生成装置１００にインストールされ、鍵生成装置１００の各機能を実現させるためのプログラムが用いられる。
【００４１】
鍵生成装置１００は、具体的には入出力部１０１、ＣＰＵ（中央演算装置）１０２、プログラム記憶部１０３、乱数生成部１０４、ランダムアクセス可能な揮発性メモリ１０５、不揮発性メモリ１０６、アドレス及びデータバス１０７を備えている。
【００４２】
入出力部１０１は、鍵生成装置１００の外部の計算機等と、鍵生成装置１００のバス１０７との間でデータを入出力するためのインターフェイス部であり、例えば、以下の各機能(f101-1)〜(f101-2)を実現するものである。
【００４３】
(f101-1) 外部から入力されたビット数ｎe，ｎ{d_p}，ｎp，ｎrを指定するための機能。
【００４４】
(f101-2) ＣＰＵ１０２から受けた奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，Ｑを出力する機能。
【００４５】
ＣＰＵ１０２は、プログラム記憶部１０３に格納されたプログラムを実行することにより、以下の各機能(f102-1)〜(f102-10)を実現するものである。このプログラムは、鍵生成のためのサブプログラムを少なくとも含んでいる。
【００４６】
(f102-1) 入出力部１０１により指定されたビット数ｎe，ｎ{d_p}，ｎp，ｎrのうち、ビット数ｎrの素数Ｒを生成し、この素数Ｒを揮発性メモリ１０５に書き込む機能。
【００４７】
(f102-2) 揮発性メモリ１０５を参照しながら奇数Ｅ、第１中間変数Ｋp、素数Ｒ及びビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを揮発性メモリ１０５に書き込む機能。
【００４８】
(f102-3) 揮発性メモリ１０５を参照しながら奇数Ｅ、第１秘密鍵Ｄp及び第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する機能。
【００４９】
(f102-4) 整数Ｐを素数判定する第１素数判定機能。
【００５０】
(f102-5) この素数判定の結果、整数Ｐが素数のとき、この素数Ｐを揮発性メモリ１０５に書き込む機能。
【００５１】
(f102-6) 揮発性メモリ１０５を参照しながら奇数Ｅ、第２中間変数Ｋq、素数Ｒ及びビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを揮発性メモリ１０５に書き込む機能。
【００５２】
(f102-7) 揮発性メモリ１０５を参照しながら奇数Ｅ、第２秘密鍵Ｄq及び第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する機能。
【００５３】
(f102-8) 整数Ｑを素数判定する第２素数判定機能。
【００５４】
(f102-9) この素数判定の結果、整数Ｑが素数のとき、この素数Ｑを揮発性メモリ１０５に書き込む機能。
【００５５】
(f102-10) 揮発性メモリ１０５を参照して奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，ＱをＲＳＡ暗号方式の鍵データとして入出力部１０１から出力する機能。
【００５６】
プログラム記憶部１０３は、例えばＲＯＭ（リードオンリーメモリ）であり、図２に示す各機能を鍵生成装置１０１に実現させるためのプログラムを記憶している。このプログラムは、外部からプログラム記憶部１０３にインストールしてもよい。
【００５７】
乱数生成部１０４は、以下の各機能(f104-1)〜(f104-3)をもっている。
【００５８】
(f104-1) 入出力部１０１により指定されたビット数ｎeの奇数Ｅをランダムに生成し、この奇数Ｅを揮発性メモリ１０５に書き込む機能。
【００５９】
(f104-2) 入出力部１０１により指定されたビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを揮発性メモリ１０５に書き込む機能。
【００６０】
(f104-3) このビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを揮発性メモリ１０５に書き込む機能。
【００６１】
ここで、乱数生成部１０４は、ＣＰＵ１０２に使用されるハードウェア資源として実現してもよく、ＣＰＵ１０２とプログラムで実現してもよい。さらに乱数生成部１０４を省略し、外部で生成した乱数を入出力部１０１から入力する構成に変形してもよい。本実施形態では、ＣＰＵ１０２とプログラムによる乱数生成部１０４を用いるものとする。
【００６２】
揮発性メモリ１０５は、例えばＲＡＭ（ランダムアクセスメモリ）等のランダムアクセス可能な記憶装置であり、計算に必要なデータや計算途中のデータなどが格納される。
【００６３】
不揮発性メモリ１０６は、例えばＥＥＰＲＯＭ（Electric Erasable Programmable ROM）等の記憶装置であり、生成された鍵データなどが格納される。
【００６４】
次に、以上のように構成された鍵生成装置の動作を図２のフローチャートを用いて説明する。
【００６５】
鍵生成装置１００においては、ユーザによる外部計算機の操作により、入出力部１０１が、公開鍵Ｅのビット数ｎe、ＣＲＴ用の秘密鍵Ｄp，Ｄqのビット数ｎ{d_p}、素数Ｐ，Ｑのビット数ｎp、及びＰ−１，Ｑ−１に持たせたい素因子Ｒのビット数ｎrを指定する（ステップＳ１１）。
【００６６】
続いて、ＣＰＵ１０２は、ｎrビットの素数Ｒを生成し、この素数Ｒを揮発性メモリ１０５に書き込む（ステップＳ１２）。
【００６７】
また、乱数生成部１０４は、ｎeビットの奇数Ｅをランダムに生成し、この奇数Ｅを揮発性メモリ１０５に書き込む（ステップＳ１３）。
【００６８】
次に、乱数生成部１０４は、入出力部１０１により指定されたビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを揮発性メモリ１０５に書き込む（ステップＳ１４）。 ＣＰＵ１０２は、揮発性メモリ１０５を参照しながら奇数Ｅ、第１中間変数Ｋp、素数Ｒ及びビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを揮発性メモリ１０５に書き込む（ステップＳ１５）。
【００６９】
ここで、第１秘密鍵Ｄpのビット数（ｎ{d_p}）は、ＫpＲのビット数（（ｎe＋ｎ{d_p}−ｎp−ｎr）＋ｎr）より大きいことを仮定している。すなわち、ｎ{d_p}＞（ｎe＋ｎ{d_p}−ｎp−ｎr）＋ｎrよりｎp＞ｎeを仮定している。この条件は、非特許文献２に課せられている条件と同じである。このように仮定すると、第１秘密鍵Ｄpは、ｍｏｄ ＫpＲでは一意的に定まるが、ｎ{d_p}ビットのデータとしては多数存在するため、この中から１つランダムに選択（＝生成）され、揮発性メモリ１０５に書き込まれる。
【００７０】
ＣＰＵ１０２は、揮発性メモリ１０５を参照しながら奇数Ｅ、第１秘密鍵Ｄp及び第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する（ステップＳ１６）。
【００７１】
ＣＰＵ１０２は、このように構成した整数Ｐが素数か否かを判定し（ステップＳ１７）、この素数判定の結果、否の場合には、ステップＳ１５に戻り、第１秘密鍵Ｄpを生成し直して、ステップＳ１７で素数と判定されるまでくり返す。
【００７２】
ＣＰＵ１０２は、ステップＳ１７の判定の結果、整数Ｐが素数のときには、この素数Ｐを揮発性メモリ１０５に書き込む。
【００７３】
続いて、鍵生成装置１００は素数Ｑの生成に移る。
鍵生成装置１００においては、乱数生成部１０４が、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを揮発性メモリ１０５に書き込む（ステップＳ１８）。
【００７４】
ＣＰＵ１０２は、揮発性メモリ１０５を参照しながら奇数Ｅ、第２中間変数Ｋq、素数Ｒ及びビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを揮発性メモリ１０５に書き込む（ステップＳ１９）。このとき、ステップＳ１５と同様に、第２秘密鍵Ｄqは、ｍｏｄ ＫqＲでは一意的に定まるが、ｎ{d_p}ビットのデータとしては多数存在するため、この中から１つランダムに選択（＝生成）され、揮発性メモリ１０５に書き込まれる。
【００７５】
ＣＰＵ１０２は、揮発性メモリ１０５を参照しながら奇数Ｅ、第２秘密鍵Ｄq及び第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する（ステップＳ２０）。
【００７６】
ＣＰＵ１０２は、このように構成した整数Ｑが素数か否かを判定し（ステップＳ２１）、この素数判定の結果、否の場合には、ステップＳ１９に戻り、第２秘密鍵Ｄqを生成し直して、ステップＳ２１で素数と判定されるまでくり返す。
【００７７】
ＣＰＵ１０２は、ステップＳ２１の判定の結果、整数Ｑが素数のときには、この素数Ｑを揮発性メモリ１０５に書き込む。
【００７８】
ＣＰＵ１０２は、以上の処理ステップの完了後、揮発性メモリ１０５を参照して奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，ＱをＲＳＡ暗号方式の鍵データとして入出力部１０１から出力する。また、ＣＰＵ１０２は、これら鍵データを不揮発性メモリ１０６に書き込む。なお、図２に図示していないが、ＣＰＵ１０２は、さらにＮ＝ＰＱ及びＤ＝Ｅ-1 ｍｏｄ （（Ｐ−１）（Ｑ−１））を計算して、これらＮ，Ｄを合わせてＲＳＡ暗号方式の鍵として出力してもよい。
【００７９】
このようにして生成された素数Ｐ，Ｑは、Ｐ−１，Ｑ−１に素因子Ｒを持つことが、以下のように確かめられる。
【００８０】
まずステップＳ１５の構成の仕方より、Ｄp＝Ｅ-1 ｍｏｄ ＫpＲである。これはＥＤp−１＝０ ｍｏｄ ＫpＲ、すなわちＥＤp−１がＫpＲの倍数であることを意味する。
【００８１】
一方、ステップＳ１６の構成の仕方より、Ｐ＝１＋（ＥＤp−１）／Ｋpである。変形するとＰ−１＝（ＥＤp−１）／Ｋpとなるが、上記よりＥＤp−１は、ＫpＲの倍数であるので、（ＥＤp−１）／Ｋpは、素数Ｒの倍数となる。従って、Ｐ−１は素数Ｒを素因子として持つ。
【００８２】
素数Ｑに関しても同様である。
従って、ｐ−１法に対する耐性を持つように素数Ｒのビット数ｎrを指定した上で、本実施形態を実施することにより、暗号化と復号の処理時間をバランスするように鍵を生成可能であり、さらにＰ−１、Ｑ−１に大きな素因子を持たせることができるため、より強固なＲＳＡ暗号方式の鍵を生成することができる。
【００８３】
ただし、ステップＳ１４，Ｓ１８で生成する中間変数Ｋp，Ｋqのビット数が正となるためには、ｎe＋ｎ{d_p}−ｎp−ｎr＞０でなければならない。非特許文献２の３章に記載されている２つのパラメータ例
ｎe＝１６０，ｎ{d_p}＝３５４，ｎp＝５１２
ｎe＝５１２，ｎ{d_p}＝２６９，ｎp＝５１２
にあてはめると、前者の場合はｎr＜２となり、素数Ｒが選べないため、本実施形態で説明したアルゴリズムは非特許文献２と同じものとなる。後者の場合はｎr＜２６９であるため、十分大きな（例えばｎpの半分のビットサイズｎr＝２５６）を選ぶことができるため、本実施形態が有用であることが確かめられる。
【００８４】
上述したように本実施形態によれば、鍵生成処理の最初に、Ｐ−１の素因子として含ませるｎrビットの素数Ｒを生成し、次にｎeビットの奇数Ｅを生成し、ｎe＋ｎ{d_p}−ｎp−ｎrビットの中間変数Ｋpを生成し、Ｄp＝Ｅ-1 ｍｏｄ ＫpＲを満たすｎ{d_p}ビットのＤpを生成し、Ｐ＝１＋（ＥＤp−１）／Ｋpを計算し、Ｐが素数となるまでこれを繰り返し、Ｑに関しても同様に実行する構成により、非特許文献２の方法においてＰ−１に素因子Ｒを持たせることができるため、暗号化と復号の処理時間をバランスするように鍵を生成でき、さらにＰ−１法に強い鍵を生成できる。
【００８５】
さらに、Ｐ−１，Ｑ−１に大きな既知の素因数Ｒを持たせることが可能となるために、整数Ｐの素数判定に確定的判定方法を使用でき、もって、正しいＲＳＡ暗号方式の鍵を生成することができる。
【００８６】
なお、本実施形態は、図３又は図４に示すように変形してもよい。
図３に示す処理は、図２に示すステップＳ１２に代えて、互いに異なる素数Ｒp，Ｒqを算出するステップＳ１２ａ，Ｓ１２ｂを設け、図２に示すステップＳ１５，Ｓ１９のｍｏｄ ＫpＲ，ｍｏｄ ＫqＲに代えて、ステップＳ１５’ではｍｏｄ ＫpＲpとし、ステップＳ１９’ではｍｏｄ ＫqＲqとしたものである。
【００８７】
この変形により、図２ではＰ−１，Ｑ−１に同じ素因子Ｒを持たせるように構成していたが、図３ではＰ−１に素因子Ｒpを、Ｑ−１に素因子Ｒqを、と異なる素因子を持たせることができる。また、図３に示す処理に変形しても、本実施形態を同様に実施して同様の効果を得ることに加え、Ｐ−１，Ｑ−１に異なる素因子Ｒp，Ｒqを持たせることから、より強固な鍵を生成することができる。
【００８８】
図４に示す処理は、図３に示した処理の更なる変形例である。
図３におけるステップＳ１７，Ｓ２１において、整数ＰあるいはＱが素数でないと判定されたときにそれぞれステップＳ１５’，Ｓ１９’に戻っていたが、図４のように、それぞれステップＳ１４，Ｓ１８に戻ってもよい。このように図４に示す処理に変形しても、図３に示す処理を同様に実施して同様の効果を得ることができる。
【００８９】
（第２の実施形態）
次に、本発明の第２の実施形態に係る鍵生成装置について説明するが、前述した図面と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００９０】
すなわち、第２の実施形態は、第１の実施形態の素数判定処理において、確定的素数判定方法を用いて素数判定を実行する形態であり、具体的には、鍵生成装置１００が、図２に示したステップＳ１１，Ｓ１２，Ｓ１７，Ｓ２１の処理を以下のように実行している。
【００９１】
ステップＳ１１においては、ビット数ｎp，ｎrを指定する際に、２ｎr＞ｎpの関係を満たすようにする。例えば、非特許文献２の３章記載の２番目のパラメータ例に示すように、ビット数ｎp，ｎrを指定する。具体的には例えば、入出力部１０１としては、ビット数ｎp，ｎrが指定されたとき、２ｎr＞ｎpの関係を満たすか否かを判定し、満たさない場合には関係を満たすようなビット数を再入力するように促す構成としてもよい。
【００９２】
また、ステップＳ１２の処理は特に変更は無いが、整数Ｒが素数である必要があるため、整数Ｒの素数判定に確定的素数判定方法を用いている。確定的素数判定方法は、例えば非特許文献４に記載の方法などにより実現される。
【００９３】
ステップＳ１７においては、整数Ｐを素数判定する際に、確定的素数判定方法であるポクリントン（Pocklington）の定理の特別な場合を用いる。
【００９４】
ポクリントンの定理の特別な場合は、以下のような定理であり、確率的素数判定方法としてよく利用されるミラー・ラビン（Miller-Rabin）法と同等の処理速度で素数判定を実行可能である。
【００９５】
整数ＰがＰ＝ＡＲ＋１，ＲはＲ＞√Ｐを満たす素数、という形をしていると仮定する。このとき、次の２条件を満たす整数ａが存在すれば、整数Ｐは素数である。
【００９６】
条件１：ａp-1＝１ ｍｏｄ Ｐ
条件２：ｇｃｄ（ａ(p-1)/R−１，Ｐ）＝１
ここで、ｇｃｄは最大公約数を表す。
【００９７】
ステップＳ１７の素数判定対象であるＰ＝１＋（ＥＤp−１）／Ｋpは、ある整数をＡとしたとき、ステップＳ１６の式中の（ＥＤp−１）／ＫpがステップＳ１２で生成した素数ＲのＡ倍であることから、Ｐ＝１＋ＡＲという形をしている。また、ステップＳ１１で２ｎr＞ｎpを満たすパラメータを指定したため、素数ＲがＲ＞√Ｐという形をしている。このため、本実施形態の素数判定対象Ｐ及び素数Ｒは、ポクリントンの定理の特別な場合の仮定を満たしている。
【００９８】
従って、ステップＳ１７においては、ＣＰＵ１０２は、ポクリントンの定理の特別な場合を利用し、条件１，２を満たす整数ａが存在すれば、整数Ｐを素数であると判定する。具体的には図５に示すように、ＣＰＵ１０２は、乱数生成部１０４により、整数ａをランダムに生成する（Ｓ１７−１）。なお、ＣＰＵ１０２は、整数ａをランダムに生成せずに、固定値（例えばａ＝２）の整数ａを用いるように変形してもよい。
【００９９】
次に、ＣＰＵ１０２は、ポクリントンの定理の特別な場合の条件１を検査する（ステップＳ１７−２）。ここで検査に失敗した場合（図５におけるＮｏ）、ＣＰＵ１０２は、整数Ｐを合成数と判定し（ステップＳ１７−５）、処理を終了する。
【０１００】
条件１の検査に成功した場合（図５におけるＹｅｓ）、ＣＰＵ１０２は、条件２を検査する（ステップＳ１７−３）。条件２の検査に失敗した場合、ＣＰＵ１０２は、整数Ｐを合成数と判定し（ステップＳ１７−５）、処理を終了する。
【０１０１】
条件２の検査に成功した場合、ＣＰＵ１０２は、整数Ｐを素数と判定し（ステップＳ１７−４）、処理を終了する。
【０１０２】
ステップＳ２１においては、ステップＳ１７−１〜Ｓ１７−５と同様にして、ＣＰＵ１０２は、整数Ｑの素数判定を実行する。
【０１０３】
上述したように本実施形態によれば、第１の実施形態の効果に加え、ミラー・ラビン法と同等の処理速度をもつ確定的素数判定方法を用いて整数Ｐ，Ｑを素数判定できるので、正しいＲＳＡ暗号方式の鍵を生成する有用な鍵生成方法を実現することができる。
【０１０４】
ここで、素数判定方法について補足的に説明する。
整数Ｐ，Ｑが素数であるか否かを判定する方法としては、大きく分けて確率的素数判定方法と確定的素数判定方法との２種類の方法が知られている。
【０１０５】
確率的素数判定方法は、合成数と判定された数については確実に合成数であるが、ある確率で合成数を誤って素数と判定することがある。
【０１０６】
確定的素数判定方法は、素数と判定された数が確実に素数であるという特徴をもつ。素数判定対象の数が特殊な構造の場合（例えば（５）式でＲが既知で、ａ＜Ｒの場合）には、確定的素数判定方法は十分高速に実行できる。
【０１０７】
一方、素数判定対象が一般の数の場合には、確定的素数判定方法では処理速度が遅く、実用に耐えないため、通常は確率的素数判定方法が用いられる。但し、確率的素数判定方法は、合成数を誤って素数と判定する確率が０ではないため、合成数を誤ってＲＳＡ暗号方式の鍵として使用する場合に、暗号文を復号できない等の問題が発生する。ここで、非特許文献２，３記載の技術では、整数Ｐ，Ｑに構造を持たせることが困難なため、確定的素数判定方法を使用できず、確率的素数判定方法を使用する必要があるので、０でない確率で暗号文を復号できない心配が残る。
【０１０８】
しかしながら、本実施形態によれば、確定的素数判定方法を使用できるので、合成数を誤って素数と判定する確率をゼロにでき、暗号文を復号できない心配を解消することができる。
【０１０９】
なお、本実施形態における確定的素数判定方法は、図３及び図４に示した変形例にも適用でき、同様の効果を得ることができる。
【０１１０】
また、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１１１】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１１２】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１１３】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【０１１４】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１５】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１１６】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１１７】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１１８】
【図１】本発明の第１の実施形態に係る鍵生成装置の構成を示す模式図である。
【図２】同実施形態における動作を説明するためのフローチャートである。
【図３】同実施形態における動作の変形例を説明するためのフローチャートである。
【図４】同実施形態における動作の他の変形例を説明するためのフローチャートである。
【図５】本発明の第２の実施形態に係る鍵生成装置における確定的素数判定動作を説明するためのフローチャートである。
【図６】従来の鍵生成の動作を説明するためのフローチャートである。
【符号の説明】
【０１１９】
１００…鍵生成装置、１０１…入出力部、１０２…ＣＰＵ、１０３…プログラム記憶部、１０４…乱数生成部、１０５…揮発性メモリ、１０６…不揮発性メモリ、１０７…バス。
【特許請求の範囲】
【請求項１】
ＲＳＡ暗号方式の鍵データを生成するための鍵生成装置であって、
前記鍵データとしての奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，Ｑと、当該鍵データを生成するための素数Ｒ及び中間変数Ｋp，Ｋqとを記憶するための記憶手段と、
ビット数ｎe，ｎ{d_p}，ｎp，ｎrを指定するための手段と、
前記ビット数ｎrの素数Ｒを生成し、この素数Ｒを前記記憶手段に書き込む手段と、
前記ビット数ｎeの奇数Ｅをランダムに生成し、この奇数Ｅを前記記憶手段に書き込む手段と、
前記ビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを前記記憶手段に書き込む手段と、
前記記憶手段を参照しながら前記奇数Ｅ、前記第１中間変数Ｋp、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、前記ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを前記記憶手段に書き込む手段と、
前記記憶手段を参照しながら前記奇数Ｅ、前記第１秘密鍵Ｄp及び前記第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する手段と、
前記整数Ｐを素数判定する第１素数判定手段と、
この素数判定の結果、前記整数Ｐが素数のとき、この素数Ｐを前記記憶手段に書き込む手段と、
前記ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを前記記憶手段に書き込む手段と、
前記記憶手段を参照しながら前記奇数Ｅ、前記第２中間変数Ｋq、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、前記ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを前記記憶手段に書き込む手段と、
前記記憶手段を参照しながら前記奇数Ｅ、前記第２秘密鍵Ｄq及び前記第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する手段と、
前記整数Ｑを素数判定する第２素数判定手段と、
この素数判定の結果、前記整数Ｑが素数のとき、この素数Ｑを前記記憶手段に書き込む手段と、
前記記憶手段を参照して前記奇数Ｅ、前記秘密鍵Ｄp，Ｄq及び前記素数Ｐ，Ｑを前記ＲＳＡ暗号方式の鍵データとして出力する手段と、
を備えたことを特徴とする鍵生成装置。
【請求項２】
請求項１に記載の鍵生成装置において、
前記第１及び第２素数判定手段は、確定的素数判定方法を用いて素数判定を実行することを特徴とする鍵生成装置。
【請求項３】
ＲＳＡ暗号方式の鍵データを生成し且つ記憶手段を備えた鍵生成装置に用いられるプログラムであって、
前記鍵生成装置を、
ビット数ｎe，ｎ{d_p}，ｎp，ｎrを指定するための手段、
前記ビット数ｎrの素数Ｒを生成し、この素数Ｒを前記記憶手段に書き込む手段、
前記ビット数ｎeの奇数Ｅをランダムに生成し、この奇数Ｅを前記記憶手段に書き込む手段、
前記ビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを前記記憶手段に書き込む手段、
前記記憶手段を参照しながら前記奇数Ｅ、前記第１中間変数Ｋp、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、前記ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを前記記憶手段に書き込む手段、
前記記憶手段を参照しながら前記奇数Ｅ、前記第１秘密鍵Ｄp及び前記第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する手段、
前記整数Ｐを素数判定する第１素数判定手段、
この素数判定の結果、前記整数Ｐが素数のとき、この素数Ｐを前記記憶手段に書き込む手段、
前記ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを前記記憶手段に書き込む手段、
前記記憶手段を参照しながら前記奇数Ｅ、前記第２中間変数Ｋq、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、前記ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを前記記憶手段に書き込む手段、
前記記憶手段を参照しながら前記奇数Ｅ、前記第２秘密鍵Ｄq及び前記第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する手段、
前記整数Ｑを素数判定する第２素数判定手段、
この素数判定の結果、前記整数Ｑが素数のとき、この素数Ｑを前記記憶手段に書き込む手段、
前記記憶手段を参照して前記奇数Ｅ、前記秘密鍵Ｄp，Ｄq及び前記素数Ｐ，Ｑを前記ＲＳＡ暗号方式の鍵データとして出力する手段、
として機能させるためのプログラム。
【請求項４】
請求項３に記載のプログラムにおいて、
前記第１及び第２素数判定手段は、確定的素数判定方法を用いて素数判定を実行する手段、として前記鍵生成装置を機能させるプログラム。
【請求項１】
ＲＳＡ暗号方式の鍵データを生成するための鍵生成装置であって、
前記鍵データとしての奇数Ｅ、秘密鍵Ｄp，Ｄq及び素数Ｐ，Ｑと、当該鍵データを生成するための素数Ｒ及び中間変数Ｋp，Ｋqとを記憶するための記憶手段と、
ビット数ｎe，ｎ{d_p}，ｎp，ｎrを指定するための手段と、
前記ビット数ｎrの素数Ｒを生成し、この素数Ｒを前記記憶手段に書き込む手段と、
前記ビット数ｎeの奇数Ｅをランダムに生成し、この奇数Ｅを前記記憶手段に書き込む手段と、
前記ビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを前記記憶手段に書き込む手段と、
前記記憶手段を参照しながら前記奇数Ｅ、前記第１中間変数Ｋp、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、前記ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを前記記憶手段に書き込む手段と、
前記記憶手段を参照しながら前記奇数Ｅ、前記第１秘密鍵Ｄp及び前記第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する手段と、
前記整数Ｐを素数判定する第１素数判定手段と、
この素数判定の結果、前記整数Ｐが素数のとき、この素数Ｐを前記記憶手段に書き込む手段と、
前記ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを前記記憶手段に書き込む手段と、
前記記憶手段を参照しながら前記奇数Ｅ、前記第２中間変数Ｋq、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、前記ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを前記記憶手段に書き込む手段と、
前記記憶手段を参照しながら前記奇数Ｅ、前記第２秘密鍵Ｄq及び前記第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する手段と、
前記整数Ｑを素数判定する第２素数判定手段と、
この素数判定の結果、前記整数Ｑが素数のとき、この素数Ｑを前記記憶手段に書き込む手段と、
前記記憶手段を参照して前記奇数Ｅ、前記秘密鍵Ｄp，Ｄq及び前記素数Ｐ，Ｑを前記ＲＳＡ暗号方式の鍵データとして出力する手段と、
を備えたことを特徴とする鍵生成装置。
【請求項２】
請求項１に記載の鍵生成装置において、
前記第１及び第２素数判定手段は、確定的素数判定方法を用いて素数判定を実行することを特徴とする鍵生成装置。
【請求項３】
ＲＳＡ暗号方式の鍵データを生成し且つ記憶手段を備えた鍵生成装置に用いられるプログラムであって、
前記鍵生成装置を、
ビット数ｎe，ｎ{d_p}，ｎp，ｎrを指定するための手段、
前記ビット数ｎrの素数Ｒを生成し、この素数Ｒを前記記憶手段に書き込む手段、
前記ビット数ｎeの奇数Ｅをランダムに生成し、この奇数Ｅを前記記憶手段に書き込む手段、
前記ビット数ｎe，ｎ{d_p}，ｎp，ｎrに基づき、ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第１中間変数Ｋpをランダムに生成し、この第１中間変数Ｋpを前記記憶手段に書き込む手段、
前記記憶手段を参照しながら前記奇数Ｅ、前記第１中間変数Ｋp、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄp＝Ｅ-1 ｍｏｄ ＫpＲとに基づいて、前記ビット数ｎ{d_p}の第１秘密鍵Ｄpを生成し、この第１秘密鍵Ｄpを前記記憶手段に書き込む手段、
前記記憶手段を参照しながら前記奇数Ｅ、前記第１秘密鍵Ｄp及び前記第１中間変数Ｋpと、式Ｐ＝１＋（ＥＤp−１）／Ｋpとに基づいて、整数Ｐを算出する手段、
前記整数Ｐを素数判定する第１素数判定手段、
この素数判定の結果、前記整数Ｐが素数のとき、この素数Ｐを前記記憶手段に書き込む手段、
前記ビット数ｎe＋ｎ{d_p}−ｎp−ｎrの第２中間変数Ｋqをランダムに生成し、この第２中間変数Ｋqを前記記憶手段に書き込む手段、
前記記憶手段を参照しながら前記奇数Ｅ、前記第２中間変数Ｋq、前記素数Ｒ及び前記ビット数ｎ{d_p}と、式Ｄq＝Ｅ-1 ｍｏｄ ＫqＲとに基づいて、前記ビット数ｎ{d_p}の第２秘密鍵Ｄqを生成し、この第２秘密鍵Ｄqを前記記憶手段に書き込む手段、
前記記憶手段を参照しながら前記奇数Ｅ、前記第２秘密鍵Ｄq及び前記第２中間変数Ｋqと、式Ｑ＝１＋（ＥＤq−１）／Ｋqとに基づいて、整数Ｑを算出する手段、
前記整数Ｑを素数判定する第２素数判定手段、
この素数判定の結果、前記整数Ｑが素数のとき、この素数Ｑを前記記憶手段に書き込む手段、
前記記憶手段を参照して前記奇数Ｅ、前記秘密鍵Ｄp，Ｄq及び前記素数Ｐ，Ｑを前記ＲＳＡ暗号方式の鍵データとして出力する手段、
として機能させるためのプログラム。
【請求項４】
請求項３に記載のプログラムにおいて、
前記第１及び第２素数判定手段は、確定的素数判定方法を用いて素数判定を実行する手段、として前記鍵生成装置を機能させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１０−４４２６２（Ｐ２０１０−４４２６２Ａ）
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００８−２０８９６２（Ｐ２００８−２０８９６２）
【出願日】平成２０年８月１４日（２００８．８．１４）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願日】平成２０年８月１４日（２００８．８．１４）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]