(57)【特許請求の範囲】
【請求項１】
１または複数の素数と乱数とを用いて前記素数より大きい素数を生成する装置において、乱数を発生する手段と、発生した乱数と１または複数の素数とを用いて素数候補を求める手段と、求めた素数候補が素数であるか否かを確定的素数判定法を用いて判定する手段と、ｎ＝ｐｑ（ｐ，ｑは素数）とした場合のｎからｐ，ｑを得る素因数分解法に対して、素数ｐによるｐs −１（ｓ：任意の自然数）の因数である少なくとも３個の多項式Ｆ（ｐ）が整数Ｂより大きい素数を因数として含む対策を施す対策手段とを備えることを特徴とする素数生成装置。
【請求項２】
前記対策手段は、対策を施すべき多項式Ｆ（ｐ）の最大次数を決定する決定手段と、決定された次数以下の多項式Ｆ（ｐ）に対して、整数Ｂより大きな素因数を持たせる手段とを有する請求項１記載の素数生成装置。
【請求項３】
前記決定手段は、所定ビット長の素数ｐがとりうる範囲［ｐmin ，ｐmax ］に応じて定まるＦ（ｐ）の範囲［Ｆ（ｐmin ），Ｆ（ｐmax ）］に含まれる整数の中で、整数Ｂ以下の素数のみの積からなる整数の個数を計数する手段と、計数した個数のＦ（ｐmax ）−Ｆ（ｐmin ）に対する割合を求める手段と、求めた割合が１／ｐ1/2 以上である多項式Ｆ（ｐ）は対策を施すべきであると判断する手段とを有する請求項２記載の素数生成装置。
【請求項４】
前記決定手段は、対策を施すべき多項式Ｆ（ｐ）について、各多項式Ｆ（ｐ）を用いた素因数分解法で必要とされる計算量に応じて多項式Ｆ（ｐ）に含ませる各素数のサイズを決定する手段と、決定された各サイズに応じた各素数を求める手段とを有する請求項２記載の素数生成装置。
【請求項５】
512 ビットの素数ｐを生成する際に、対策を施すべき多項式Ｆ（ｐ）であるｐ−１，ｐ＋１，ｐ2 ＋ｐ＋１，ｐ2 ＋１，ｐ2 −ｐ＋１がそれぞれ260, 51, 50, 49, 48 ビットの素因数を持つ請求項４記載の素数生成装置。
【請求項６】
1024ビットの素数ｐを生成する際に、対策を施すべき多項式Ｆ（ｐ）であるｐ−１，ｐ＋１，ｐ2 ＋ｐ＋１，ｐ2 ＋１，ｐ2 −ｐ＋１がそれぞれ515, 110, 109, 109, 107 ビットの素因数を持つ請求項４記載の素数生成装置。
【請求項７】
ＲＳＡ暗号の秘密鍵に使用する素数ｐを生成する装置において、１または複数の素数と乱数とを用いて素数候補を計算する計算手段と、計算した素数候補が素数であるか否かを確定的素数判定法を用いて判定する素数判定手段と、素数と判定された数について、ＲＳＡ暗号への繰り返し暗号化攻撃に対する強度を判定する強度判定手段とを備えることを特徴とする素数生成装置。
【請求項８】
前記強度判定手段は、素数と判定された数ｐが、以下の条件を満たすか否かを判定する手段を有する請求項７記載の素数生成装置。
ｐ＝２ｈp ｐ1 ＋１（ｈp ＜ｐ1 ，ｐ1 ：素数）について、
ｐ1 ＝２ｐ1 ′＋１を満たすｐ1 ′が素数である。
【請求項９】
前記強度判定手段は、素数と判定された数ｐ，ｑが、ｐ＝２ｈp ｐ1 ＋１（ｈp ＜ｐ1 ，ｐ1 ：素数），ｑ＝２ｈq ｑ1 ＋１（ｈq ＜ｑ1 ，ｑ1 ：素数）と表される場合に、以下の条件を満たすか否かを判定する手段を有する請求項７記載の素数生成装置。
【数１】
0003835896.tif 000024
【請求項１０】
前記計算手段は、ｐ−１に含まれる素数ｐ1 の生成時に、ＲＳＡ暗号の暗号化鍵ｅを用いたPocklington の素数判定法を用いる手段を有する請求項７記載の素数生成装置。
【請求項１１】
所定ビット長の素数ｐについての多項式Ｆ（ｐ）に関し、整数Ｂ以下の素数のみの積からなる整数の割合を表すＢ−smooth性を判定する装置であって、素数ｐがとりうる範囲［ｐmin ，ｐmax ］に応じて定まるＦ（ｐ）の範囲［Ｆ（ｐmin ），Ｆ（ｐmax ）］に含まれる整数の中で、整数Ｂ以下の素数のみの積からなる整数の個数を計数する手段と、計数した個数をＦ（ｐmax ）−Ｆ（ｐmin ）で割ることにより、範囲［Ｆ（ｐmin ），Ｆ（ｐmax ）］に含まれる整数がＢ−smoothを満たす確率を求める手段とを備えることを特徴とするＢ−smooth性判定装置。
【請求項１２】
ＲＳＡ暗号の秘密鍵に使用する素数ｐを生成するためのコンピュータプログラムを記録した記録媒体において、１または複数の素数と乱数とを用いて素数候補を求めさせる手段と、求めた素数候補が素数であるか否かを確定的素数判定法を用いて判定させる手段と、素数と判定された数について、ＲＳＡ暗号への繰り返し暗号化攻撃に対する強度を判定させる手段とを含むプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば暗号通信において安全性が高い公開鍵となる素数を生成するための素数生成装置、及び、Ｂ−smooth性判定装置に関する。
【０００２】
【従来の技術】
素因数分解の困難さを利用したＲＳＡ暗号方式等の暗号方式においては、公開されたｎに対してｎ＝ｐｑの素因数ｐ，ｑを求めることは、ｎが1024ビット程度である場合に、計算量的に困難である。また、攻撃者にｎからｐ，ｑを知られないことが暗号の安全性のための条件である。従って、暗号通信の安全性は、生成する素数ｐ，ｑの性質（素因数分解されやすいものであるか否か等）に依存する。
【０００３】
従来では、素数判定にMiller−Rabin 等の確率的素数判定法を用いて素数を生成しているので、非常に低い確率ではあるが、素数ではない合成数を生成してしまう虞がある。
【０００４】
「暗号理論入門」（岡本栄司著，共立出版）等によれば、素数ｐに対し、ｐ−１，ｐ＋１が小さな素数のみの積からなる場合、ｐ−１法，ｐ＋１法等の素因数分解アルゴリズムによりｎの素因数分解は比較的容易に解けるとされている。従って、従来の素数生成方法では、ｐ−１，ｐ＋１にそれぞれ大きな素因数ｐ1 ，ｐ2 を持たせることで、素因数分解法に対する対策を行っている。
【０００５】
また、ＲＳＡ暗号の暗号文Ｘe （Ｘ：平文，ｅ：暗号化鍵）に対して、ｘe ，（Ｘe ）e ，((Ｘe ）e ）e ，・・・のように暗号化をｕ回繰り返し、下記（１）に示すように平文Ｘを得るという攻撃、所謂、繰り返し暗号化攻撃が知られている。このような攻撃に対して、従来の素数生成方法では、ｐ−１に含まれる大きな素因数ｐ1 について、ｐ1 −１に大きな素数ｐ1 ′を含ませることで、対策を行っている。
【０００６】
【数２】
0003835896.tif 000002
【０００７】
また、素数生成方法の具体的な従来例としては、次のような方法が公知である。USP 615634には、ｐ−１，ｐ＋１がそれぞれ大きな素数ｐ1 ，ｐ2 を含み、ｐ1 −１，ｐ2 −１がそれぞれ大きな素数ｐ1 ′，ｐ2 ′を含み、ｐ1 ，ｐ2 のビット長の合計がｐのビット長を超えることができず、かつ確率的な素数生成方法が示されている。また、特開平９−73269 号公報には、ｐ−１，ｐ＋１がそれぞれ大きな素数ｐ1 ，ｐ2 を含み、ｐ1 −１が大きな素数ｐ1 ′を含み、ｐ1 ，ｐ2 の両方のビット長がｐのビット長の１／２を超えるようにした確率的な素数生成方法が示されている。
【０００８】
【発明が解決しようとする課題】
従来の素数生成方法では、本発明が解決しようとする以下に述べるような課題がある。
（課題１）従来の素数生成方法では、非常に低い確率ではあるが、合成数を生成する。
【０００９】
（課題２）従来の方法では、ｐ−１，ｐ＋１が大きな素数を含むようにしているが、一般には、ｐ−１，ｐ＋１以外にもｐ2 ＋ｐ＋１，ｐ2 −ｐ＋１，・・・のようなｐs −１（ｓは任意の整数）の因数である多項式Ｆ（ｐ）が小さな素数のみの積からなる場合についても比較的容易に素因数分解が解けることが知られている。ところで、整数Ｂ以下の素数のみの積からなる数をＢ−smoothと呼ぶ。つまり、Ｆ（ｐ）が小さなＢに対してＢ−smoothでないことが、Ｆ（ｐ）を利用した素因数分解法に対する対策となるのである。しかしながら、従来の方法では、ｔ次多項式Ｆ（ｐ）がどの程度のＢに対しＢ−smoothとなるかについて考慮していないので、対策を行うべきＦ（ｐ）の最高次数がわからないという問題がある。Ｆ（ｐ）がＢ−smoothであるか否かを確認するためには、実際にＦ（ｐ）をＢ以下の素数で何度も割ればよいのであるが、あるＦ（ｐ）がＢ−smoothであるか否かを判定する際に、Ｂが大きい場合には素数データが膨大になって時間がかかるという問題がある。つまり、Ｆ（ｐ）がＢ−smoothであるか否かの判定に時間がかかるうえ、対策を行うＦ（ｐ）の最高次数がわからない以上、任意のＦ（ｐ）に対して素因数分解対策を行うことは非常に困難である。このようなことが原因で、従来例ではＦ（ｐ）＝ｐ−１，ｐ＋１に対策を行っているが、２次以上のＦ（ｐ）に対する対策は施していない。
【００１０】
（課題３）従来の素数生成方法においては、繰り返し暗号化攻撃に対する対策として、ｐ−１に含まれる素数ｐ′について、ｐ′−１に大きな素数ｐ″を含ませる方法を用いている。この対策法では、繰り返し暗号化攻撃に対し、非常に弱い鍵の生成を避けることはできるが、それでもかなりの割合で攻撃が成功する可能性を残す。
【００１１】
従来知られている繰り返し暗号化攻撃に対する有効な対策として、Maurerの判定法（Fast generation of secure RSA-moduli with almost maximal diversity, Advances in Cryptology-EUROCRYPT '89, Lecture Notes in Computer Science, Vol.434, pp.636-647）がある。以下、このMaurerの判定法について簡単に説明する。
【００１２】
・Maurerの判定法
素数ｐについて、以下の（２）の条件が満たされるものとする。
ｐ＝２ｈp ｐ′＋１（ｐ′＞ｈp ，ｐ′：素数）、かつ、
ｐ′＝２ｈp ′ｐ″＋１（ｐ″＞ｈp ′，ｐ″：素数）    …（２）
この２つの条件を満たすｐ，ｑをＲＳＡの秘密鍵に用いたうえでＲＳＡの暗号化鍵をｅとした場合、以下の（３）の条件を満たせば、暗号文Ｘe から平文Ｘを得るのに必要な暗号化の繰り返し回数ｕが下記（４）の条件を満たす（平文Ｘに関する）確率ｆが下記（５）であることが保証される。
【００１３】
【数３】
0003835896.tif 000003
【００１４】
ｕ≧ｍｉｎ（ｐ′−１，ｑ′−１）          …（４）
ｆ≧１−１／（ｐ′ｑ′）                  …（５）
【００１５】
具体的には、ｎ＝1024ビット，ｐ＝ｑ＝512 ビット，ｐ′＝ｑ′＝260 ビットとした場合、２1024個の平文の全体集合に対し、２504 ｛＝２1024÷（２260 ×２260 ）｝個以外の全ての平文に対して、最低でも２260 回暗号化を繰り返さないと、もとの平文を得ることができないことを保証するものである。
【００１６】
Maurerの判定法は、後述するPocklington の確定的素数判定法をＲＳＡの暗号化鍵ｅをベースに行ったものであるので、繰り返し暗号化攻撃に対する対策であると同時に、確定的な素数判定を行うものである。
【００１７】
本発明は斯かる事情に鑑みてなされたものであり、確定的な素数を生成することができる素数生成装置を提供することを目的とする。
【００１８】
本発明の他の目的は、素因数分解法に対する対策を行う必要がある次数の上限を決定でき、素因数分解法に対して適切な対策を施せる素数生成装置を提供することにある。
【００１９】
本発明の更に他の目的は、繰り返し暗号化攻撃に対して強い素数を生成できる素数生成装置を提供することにある。
【００２０】
【課題を解決するための手段】
請求項１に係る素数生成装置は、１または複数の素数と乱数とを用いて前記素数より大きい素数を生成する装置において、乱数を発生する手段と、発生した乱数と１または複数の素数とを用いて素数候補を求める手段と、求めた素数候補が素数であるか否かを確定的素数判定法を用いて判定する手段と、ｎ＝ｐｑ（ｐ，ｑは素数）とした場合のｎからｐ，ｑを得る素因数分解法に対して、素数ｐによるｐs −１（ｓ：任意の自然数）の因数である少なくとも３個の多項式Ｆ（ｐ）が整数Ｂより大きい素数を因数として含む対策を施す対策手段とを備えることを特徴とする。
【００２２】
請求項２に係る素数生成装置は、請求項１において、前記対策手段は、対策を施すべき多項式Ｆ（ｐ）の最大次数を決定する決定手段と、決定された次数以下の多項式Ｆ（ｐ）に対して、整数Ｂより大きな素因数を持たせる手段とを有することを特徴とする。
【００２３】
請求項３に係る素数生成装置は、請求項２において、前記決定手段は、所定ビット長の素数ｐがとりうる範囲［ｐmin ，ｐmax ］に応じて定まるＦ（ｐ）の範囲［Ｆ（ｐmin ），Ｆ（ｐmax ）］に含まれる整数の中で、整数Ｂ以下の素数のみの積からなる整数の個数を計数する手段と、計数した個数のＦ（ｐmax ）−Ｆ（ｐmin ）に対する割合を求める手段と、求めた割合が１／ｐ1/2 以上である多項式Ｆ（ｐ）は対策を施すべきであると判断する手段とを有することを特徴とする。
【００２５】
請求項４に係る素数生成装置は、請求項２において、前記決定手段は、対策を施すべき多項式Ｆ（ｐ）について、各多項式Ｆ（ｐ）を用いた素因数分解法で必要とされる計算量に応じて多項式Ｆ（ｐ）に含ませる各素数のサイズを決定する手段と、決定された各サイズに応じた各素数を求める手段とを有することを特徴とする。
【００２６】
請求項５に係る素数生成装置は、請求項４において、512 ビットの素数ｐを生成する際に、対策を施すべき多項式Ｆ（ｐ）であるｐ−１，ｐ＋１，ｐ2 ＋ｐ＋１，ｐ2 ＋１，ｐ2 −ｐ＋１がそれぞれ260, 51, 50, 49, 48 ビットの素因数を持つことを特徴とする。
【００２７】
請求項６に係る素数生成装置は、請求項４において、1024ビットの素数ｐを生成する際に、対策を施すべき多項式Ｆ（ｐ）であるｐ−１，ｐ＋１，ｐ2 ＋ｐ＋１，ｐ2 ＋１，ｐ2 −ｐ＋１がそれぞれ515, 110, 109, 109, 107 ビットの素因数を持つことを特徴とする。
【００２８】
請求項７に係る素数生成装置は、ＲＳＡ暗号の秘密鍵に使用する素数ｐを生成する装置において、１または複数の素数と乱数とを用いて素数候補を計算する計算手段と、計算した素数候補が素数であるか否かを確定的素数判定法を用いて判定する素数判定手段と、素数と判定された数について、ＲＳＡ暗号への繰り返し暗号化攻撃に対する強度を判定する強度判定手段とを備えることを特徴とする。
【００２９】
請求項８に係る素数生成装置は、請求項７において、前記強度判定手段は、素数と判定された数ｐが、以下の条件を満たすか否かを判定する手段を有することを特徴とする。
ｐ＝２ｈp ｐ1 ＋１（ｈp ＜ｐ1 ，ｐ1 ：素数）について、
ｐ1 ＝２ｐ1 ′＋１を満たすｐ1 ′が素数である。
【００３０】
請求項９に係る素数生成装置は、請求項７において、前記強度判定手段は、素数と判定された数ｐ，ｑが、ｐ＝２ｈp ｐ1 ＋１（ｈp ＜ｐ1 ，ｐ1 ：素数），ｑ＝２ｈq ｑ1 ＋１（ｈq ＜ｑ1 ，ｑ1 ：素数）と表される場合に、以下の条件を満たすか否かを判定する手段を有することを特徴とする。
【００３１】
【数４】
0003835896.tif 000004
【００３２】
請求項10に係る素数生成装置は、請求項７において、前記計算手段は、ｐ−１に含まれる素数ｐ1 の生成時に、ＲＳＡ暗号の暗号化鍵ｅを用いたPocklington の素数判定法を用いる手段を有することを特徴とする。
【００３３】
請求項11に係るＢ−smooth性判定装置は、所定ビット長の素数ｐについての多項式Ｆ（ｐ）に関し、整数Ｂ以下の素数のみの積からなる整数の割合を表すＢ−smooth性を判定する装置であって、素数ｐがとりうる範囲［ｐmin ，ｐmax ］に応じて定まるＦ（ｐ）の範囲［Ｆ（ｐmin ），Ｆ（ｐmax ）］に含まれる整数の中で、整数Ｂ以下の素数のみの積からなる整数の個数を計数する手段と、計数した個数をＦ（ｐmax ）−Ｆ（ｐmin ）で割ることにより、範囲［Ｆ（ｐmin ），Ｆ（ｐmax ）］に含まれる整数がＢ−smoothを満たす確率を求める手段とを備えることを特徴とする。
【００３５】
請求項12に係る記録媒体は、ＲＳＡ暗号の秘密鍵に使用する素数ｐを生成するためのコンピュータプログラムを記録した記録媒体において、１または複数の素数と乱数とを用いて素数候補を求めさせる手段と、求めた素数候補が素数であるか否かを確定的素数判定法を用いて判定させる手段と、素数と判定された数について、ＲＳＡ暗号への繰り返し暗号化攻撃に対する強度を判定させる手段とを含むプログラムを記録したことを特徴とする。
【００３６】
本発明では以下のような各手段にて、前述した各課題を解決する。
（手段１）（課題１）に対して、素数判定法としてPocklington の確定的素数判定法を用いることにより、必ず素数を生成できるようにする。
（手段２）（課題２）に対して、ｔ次多項式Ｆ（ｐ）がＢ−smoothであるか否かの判定基準を導入し、Ｆ（ｐ）がこの次数以上であればＢ−smoothとなりえないと判断できるｔmax を決定することにより、素因数分解対策を行う多項式の次数を限定できるようにする。
（手段３）（課題３）に対して、素数生成時に後述するような特定の処理を追加することにより、繰り返し暗号化攻撃に対して強い素数を生成できるようにする。
【００３７】
図７は、本発明における素数生成の全体の流れを示すフロチャートであり、以下の手順にて素数生成処理が行われる。
Ｓ111 ：最初に、生成する素数ｐのビット長、及び、Ｆ（ｐ）がＢ−smoothであるか否かを判定する際の整数Ｂを入力する。
Ｓ112 ：Ｆ（ｐ）がこの次数以上ならばＢ−smoothとなりえないと判断できるＦ（ｐ）の次数ｔmax を求める。
Ｓ113 ：ｔmax 次未満のＦ（ｐ）に持たせる素数ｐi （１≦ｉ≦ｆ，ｆ：ｔmax 次未満の多項式Ｆ（ｐ）の個数）を決定する。
Ｓ114 ：Ｆ（ａi ）≡０（mod ｐi ）を満たすａi を求める。
Ｓ115 ：Ａ≡ａi （mod ｐi ）を満たすＡ（mod ｐ1 ・・・ｐf ）を生成する。
Ｓ116 ：乱数発生器により乱数Ｒを発生する。
Ｓ117,Ｓ118 ：ｐ＝Ｒｐ1 ・・・ｐf ＋Ａ＝２ｈp ｐ1 ＋１をPocklington の素数判定法にかける。判定の結果、素数であると判定された場合は、ｐを出力して終了する。そうでなければ、Ｓ116 に処理が戻る。
【００３８】
次に、（手段１），（手段２），（手段３）の詳細な内容について説明する。（手段１）
本発明では、素数判定の際に、以下に示すようなPocklington の確定的素数判定法を用いる。
・Pocklington の確定的素数判定法
図８は、Pocklington の確定的素数判定法の手順を示すフロチャートであり、以下の手順にて素数の判定処理が行われる。
Ｓ121 ：判定する素数候補ｐ＝２ｈp ｐ′＋１を入力する。但し、ｐ′は素数であり、ｐ′＞ｈp である。
Ｓ122 ：乱数ａを選ぶ。
Ｓ123,Ｓ126 ：ａp-1 ≡１（mod ｐ）を判定する。真ならばＳ124 に処理が進み、そうでなければｐを合成数と判定して終了する。
Ｓ124,Ｓ125,Ｓ126 ：以下の条件（６）を判定する。真ならばｐを素数と判定して終了する。そうでなければｐを合成数と判定して終了する。
【００３９】
【数５】
0003835896.tif 000005
【００４０】
以上のように、素数ｐ′からより大きな素数ｐが生成できるので、小さな素数のデータベースから大きな素数ｐを生成できることになる。よって、この判定法は、確定的な素数生成に利用できることが分かる。
【００４１】
（手段２）
本発明は、（ｐs −１）の因数であるｔ次多項式Ｆ（ｐ）を用いた素因数分解法に対する対策を行うために、Ｆ（ｐ）がＢ−smoothであるか否かの評価基準を導入する。この際の評価基準は、「生成する素数のビット数をｐb とするとき、ｐb ビットの任意の素数ｐについてＦ（ｐ）がＢ−smoothとなる確率が１／ｐ1/2 以下である」ことである。
【００４２】
また、Ｆ（ｐ）がＢ−smoothを満たす確率の決定処理は、以下の▲１▼〜▲３▼の手順に従う。
▲１▼  ｔ次多項式Ｆ（ｐ）の最大値及び最小値で挟まれる区間［Ｆ（ｐmin ），Ｆ（ｐmax ）］を考える。但し、ｐmax ，ｐmin はそれぞれｐb ビットの最大の素数，最小の素数である。
▲２▼  区間［Ｆ（ｐmin ），Ｆ（ｐmax ）］に含まれるＢ−smoothを満たす整数の個数を計算する。これは、（Ｆ（ｐmax ）−Ｆ（ｐmin ))・exp(−ｕlnｕ）で近似される。但し、ｕ＝ｔ×ｐb ／ log2 Ｂであり、lnは自然対数を底とする対数を示す。
▲３▼  ▲２▼で計算した個数を（Ｆ（ｐmax ）−Ｆ（ｐmin ))で割ることにより、［Ｆ（ｐmin ），Ｆ（ｐmax ）］に存在する整数がＢ−smoothである確率exp(−ｕlnｕ）が計算される。
【００４３】
ここで、▲２▼において［Ｆ（ｐmin ），Ｆ（ｐmax ）］に含まれるＢ−smoothを満たす整数の個数が、（Ｆ（ｐmax ）−Ｆ（ｐmin ))・exp(−ｕlnｕ）で近似される理由について説明する。ｘ未満の整数でｙを超える素因子を持たないものの個数は、Φ（ｘ，ｙ）＝ｘ・exp(−ｕlnｕ）で近似できることが知られている。但し、ｕ＝（lnｘ）／（lnｙ）である。つまり、Φ（Ｆ（ｐmax ），Ｂ）−Φ（Ｆ（ｐmin ），Ｂ）が、区間［Ｆ（ｐmin ），Ｆ（ｐmax ）］に存在するＢ−smoothを満たす整数の個数を表す。また、ｕ＝（lnＦ（ｐ））／（lnＢ）については、ｐmin ，ｐmax ともにビット長が同じであることを考えると、ｕは［ｐmin ，ｐmax ］においてはほぼ同一と近似できる。よって、Φ（Ｆ（ｐmax ），Ｂ）−Φ（Ｆ（ｐmin ），Ｂ）＝（Ｆ（ｐmax ）−Ｆ（ｐmin ))・exp(−ｕlnｕ）が、区間［Ｆ（ｐmin ），Ｆ（ｐmax ）］におけるＢ−smoothを満たす整数の個数を表している。
【００４４】
以上の▲１▼〜▲３▼により、Ｆ（ｐ）がＢ−smoothを満たす確率を計算し、その値が１／ｐ1/2 以下である場合には現実的な確率でＦ（ｐ）がＢ−smoothとはなりえないと判断し、そうでなければ、Ｆ（ｐ）はＢ−smoothとなりうると判断する。このようにして、ｔ次多項式Ｆ（ｐ）がＢ−smoothであるか否かを評価する。その結果、Ｂ−smoothとなりえない多項式の次数ｔmax を決定し、Ｂ−smoothとなりうるｔmax 未満の次数のＦ（ｐ）については大きな素数をもたせ、ｔmax 以上の次数のＦ（ｐ）についてはＢ−smoothとなりえないと判断することにより、ｐ−１法／ｐ＋１法以外の（ｐs −１）の任意の因数の多項式を用いた素因数分解法にも対策を行う。
【００４５】
（手段３）
本発明では、前述のＳ111 〜Ｓ118 で示される素数生成形法に、以下の（手段３ａ）または（手段３ｂ）の何れかの処理を追加することにより、繰り返し暗号化攻撃に強い素数を生成する。まず、この（手段３ａ），（手段３ｂ）の内容を説明する前に、必要な定理及び補題について述べる。
【００４６】
〔定理〕オイラーの定理
互いに素である任意のａ，ｎについて、下記（７）が成立する。但し、φ（ｎ）は、オイラー関数と呼ばれるものであり、ｎが下記（８）のように素因数分解される場合に、下記（９）で表される。
【００４７】
【数６】
0003835896.tif 000006
【００４８】
また、ａu ≡１（mod ｎ）を満たす最小のｕについて、ｕ｜φ（ｎ）が成立する。但し、ａ｜ｂはａがｂを割り切ることを意味する。
【００４９】
【数７】
0003835896.tif 000007
【００５０】
（手段３ａ）
図９は、（手段３ａ）での手順を示すフロチャートであり、以下の手順にて、前述のＳ113 で行われるｐ−１に含まれる素数ｐ1 を生成する。
Ｓ131 ：Pocklington の判定法を用いた素数生成器により素数ｐ1 ′を生成する。
Ｓ132 ：ｐ1 ′からｐ1 ＝２ｐ1 ′＋１を生成する。
Ｓ133,Ｓ134 ：ｐ1 ′，ｅを用いて、Maurerの判定を行う。その結果、ｐ1 がｅをＲＳＡの暗号化鍵に用いた際、ｐ1 から生成するｐが繰り返し暗号化攻撃に強い素数であるか否かを判定し、強い素数と判定されれば、ｐ1 を出力して終了する。そうでなければ、処理がＳ131 に戻る。
【００５１】
このような手法（手段３ａ）を素数生成に追加した場合、従来方式よりも繰り返し暗号化攻撃に強い素数を生成できる理由について説明する。
【００５２】
まず、ｐ1 ＝２ｈp ′ｐ1 ′＋１とし、ｐ1 をMaurerの判定法にかけたうえで、素数  ｐ＝２ｈp ｐ1 ＋１を生成した場合の安全性について述べる。繰り返し暗号化攻撃とは、平文Ｘをｕ回暗号化してもとの平文を得る攻撃であり、下記（10）のように示される。
【００５３】
【数８】
0003835896.tif 000008
【００５４】
特に、ｅu −１≡０（mod φ（ｎ))が小さなｕに関して成立するならば、上記〔定理〕より上記（10）は任意のＸについて満たされることになるので、そのような事態は避けねばならない。つまり、ｅ，ｕ，ｎによって決定するｅu ≡１（mod φ（ｎ))が満たされる確率を、ｕが小さな場合について低くすることを考える。
【００５５】
まず、ｎ＝ｐｑ，ｐ＝２ｈp ｐ1 ＋１，ｑ＝２ｈq ｑ1 ＋１より、φ（ｎ）＝４ｈp ｈq ｐ1 ｑ1 であるので、ｅu ≡１（mod ４ｈp ｈq ｐ1 ｑ1 ）について考える。この場合、上記〔定理〕より、ｕが満たすべき条件は下記（11）となる。
ｕ｜φ（４ｈp ｈq ｐ1 ｑ1 ）    …（11）
また、ｐ1 ，ｑ1 は素数であるので、下記（12）のようになり、（11）は（13）の如く表される。
0003835896.tif 000009
【００５６】
つまり、下記（14）をできるだけ大きな素数の積となるようにすれば、（13）を満たし、かつ、小さな数であるようなｕの個数が減少する。
４ｈp ′ｈq ′ｐ1 ′ｑ1 ′φ（４ｈp ｈq ）    …（14）
（13）を満たし、かつ、小さな数であるようなｕの個数が減少することは、ｅu −１≡０（mod φ（ｎ))が小さなｕに関して成立する確率が減少することを意味する。従って、（手段３ａ）を用いた場合、（14）において、ｈp ′＝ｈq ′＝１を満たすので、ｅu −１≡０（mod φ（ｎ))  が小さなｕについて成立する確率が減るのである。
【００５７】
以上のようにして、（手段３ａ）を用いる本発明においては、素数ｐ1 ′，ｑ1 ′を生成したうえで、素数ｐ1 ，ｑ1 をｐ1 ＝２ｐ1 ′＋１，ｑ1 ＝２ｑ1 ′＋１が満たされるように生成することにより、任意の平文に対し繰り返し暗号化攻撃が成立するための条件ｅu −１≡０（mod φ（ｎ))が小さなｕについて成立する確率を低く抑える。
【００５８】
（手段３ｂ）
図10は、（手段３ｂ）での手順の一部を示すフロチャートであり、以下の手順にて、前述のＳ113 で行われるｐ−１に含まれる素数ｐ1 を生成する。
Ｓ141 ：Pocklington の判定法を用いた素数生成器により素数ｐ1 ′を生成する。
Ｓ142 ：ｐ1 ′からｐ1 ＝２ｐ1 ′＋１を生成する。
Ｓ143,Ｓ144 ：ｐ1 をPocklington の判定にかける。その結果、ｐ1 が素数と判定された場合にはｐ1 を出力して終了する。そうでなければ、処理がＳ141 に戻る。
【００５９】
そして、Ｓ115 で生成したＡ，Ｓ116 で発生した乱数Ｒについて、２ｈp ＝｛Ｒｐ2 ・・・ｐf ＋（Ａ−１）／ｐ1 ｝を計算した後、次のＳ117 の前に、図11のフロチャートで示される以下の手順を追加する。
【００６０】
Ｓ151 ：ｈp を確率的素数判定にかける。素数と判定されなかった場合、ｈp は攻撃に弱いものと判断して、Ｓ116 の乱数Ｒの発生処理に戻る。
Ｓ152 ：ｈp ′＝ｈp −１，ｘp ＝０，ｙp ＝０とする。
Ｓ153,Ｓ154 ：ｈp ′≡０（mod ２）が満たされる間、ｈp ′＝ｈp ′／２，ｘp ＝ｘp ＋１を繰り返す。
Ｓ155,Ｓ156 ：ｈp ′≡０（mod ３）が満たされる間、ｈp ′＝ｈp ′／３，ｙp ＝ｙp ＋１を繰り返す。
Ｓ157 ：ｘp ，ｙp ≧１でない場合には、Ｓ116 の乱数Ｒの発生処理に戻る。
Ｓ158 ：ｈp ′を確率的素数判定にかける。素数と判定されなかった場合、ｈp ，ｈp ′は攻撃に弱いものと判断して、Ｓ116 の乱数Ｒの発生処理に戻る。
Ｓ159,Ｓ160 ：Ｓ141 〜Ｓ144 により生成されたｐ1 ，ｑ1 及びＳ151 〜Ｓ158 の判定を通過したｈp ，ｈq からｐ，ｑを生成し、最終的にｐ，ｑが素数として出力された場合、ＲＳＡの暗号化鍵ｅについて、下記（15）が成立する場合には、ｐ，ｑ，ｅは繰り返し暗号化攻撃に強い鍵と判定して終了する。
【００６１】
【数９】
0003835896.tif 000010
【００６２】
なお、予めｘp ，ｘq 及びｙp ，ｙq のそれぞれの上限ｘ′，ｙ′を定めることにより、Ｓ157 の処理を以下に示すＳ157 ′の処理に置き換え、最後に処理Ｓ161 を追加することにより、ｅに関する判定処理をｐ，ｑそれぞれについて並列化することもできる。
Ｓ157 ′：ｘp ，ｙp ≧１，ｘp ≦ｘ′，ｙp ≦ｙ′でない場合には、Ｓ116 の乱数Ｒの発生処理に戻る。
Ｓ161 ：ＲＳＡの暗号化鍵ｅについて、下記（16）の条件を満たす場合には、ｐ，ｅは繰り返し暗号化攻撃に強い鍵と判定して終了する。
【００６３】
【数１０】
0003835896.tif 000011
【００６４】
このような手法（手段３ｂ）を素数生成に追加した場合、繰り返し暗号化攻撃に弱い平文は４個しか存在しないことを以下に示す。まず、Ｓ131 〜Ｓ133 ，Ｓ141 〜Ｓ143 ，Ｓ151 より、判定の条件は以下の（ａ）〜（ｅ）である。
【００６５】
【数１１】
0003835896.tif 000012
【００６６】
このとき、下記（17）が小さなｕに関して成立するような平文Ｘの個数を考える。但し、ｇｃｄ（Ｘ，ｐｑ）＝１であるものとする。
【００６７】
【数１２】
0003835896.tif 000013
【００６８】
下記（18）を満たすＸの個数は、以下の（ａ），（ｂ）のようになる。
【００６９】
【数１３】
0003835896.tif 000014
【００７０】
（ａ）〔定理〕より下記（19）を満たす場合には、全てのＸについて成立。
（ｂ）〔補題〕より下記（19）を満たさない場合には、ｖp ｖq 個のＸについて成立。（ｖp ＝ｇｃｄ（ｅu −１，φ（ｐ))，ｖq ＝ｇｃｄ（ｅu −１，φ（ｑ))）
ｅu −１≡０（mod φ（ｎ))            …（19）
【００７１】
まず、（ａ）について、φ（ｎ）＝４ｈp ｈq ｐ1 ｑ1 であり、また、下記（20）と（21）とは互いに等価である。
ｅu ≡１（mod ４ｈp ｈq ｐ1 ｑ1 ）    …（20）
【００７２】
【数１４】
0003835896.tif 000015
【００７３】
（21）の各ｅu ≡１（mod ｚ）の解が存在することが、（20）の解が存在する条件であり、また、（21）のそれぞれの式を解くことは〔補題〕より、実質（22）を解くことと同じであり、また、（23）より（21）の解が存在するための条件は、下記（24）を満たすｕについて（20）が満たされるか否かを調べれば良い。
【００７４】
【数１５】
0003835896.tif 000016
【００７５】
また、ｕの候補で小さな数となるのは、下記（25）だけであるので、結局、下記（26）が成立するか否かを調べれば良い。そして、（26）が成立するならば、小さなｕに関して（ａ）が満たされることはないと判断できる。
【００７６】
【数１６】
0003835896.tif 000017
【００７７】
次に、（ｂ）について、φ（ｐ）＝２ｈp ｐ1 ，φ（ｑ）＝２ｈq ｑ1 であって、〔補題〕より、下記（27）の何れかが成立する場合には多くのＸが存在する。
【００７８】
【数１７】
0003835896.tif 000018
【００７９】
しかし、上記（27）の成立判定に関しても、下記（28）より（29）を満たすｕのうちで、（30）の形である小さなｕについてのみ調べれば良い。
【００８０】
【数１８】
0003835896.tif 000019
【００８１】
つまり、下記（31）が、ｚ＝ｈp ，ｈq ，ｐ1 ，ｑ1 の全てについて成立すれば良い。従って、判定条件は、ｚが全て素数であるので、下記（32）となる。
【００８２】
【数１９】
0003835896.tif 000020
【００８３】
この（32）が成立する場合には、上記（27）は成立しない。つまり、小さなｕに関してＸが多くの解を持つことがない。
【００８４】
よって、（手段３ｂ）の条件を満たした上で、（26），（32）の条件を、ｈp ｐ1 ＝（ｐ−１）／２，ｈq ｑ1 ＝（ｑ−１）／２も考慮に入れて合成したものである下記（33）が満たされれば、４個の平文Ｘを除き、下記（34）が小さなｕについて成立することはない。
【００８５】
【数２０】
0003835896.tif 000021
【００８６】
以上のようにして、Maurerの判定法が２502 個以外の平文が安全であることを保障しているのに対して、本発明の（手段３ｂ）では４個以外の全ての平文が繰り返し暗号化攻撃に対して強いことを保障している。なお、（手段３ｂ）は（手段３ａ）に比べて、より安全性が高い素数を生成する。
【００８７】
【発明の実施の形態】
以下、本発明をその実施の形態を示す図面を参照して具体的に説明する。以下の実施の形態では、512 ビット程度のＲＳＡ用の素数秘密鍵ｐを生成する場合について説明する。
【００８８】
図１は、本発明の素数生成装置の構成を示すブロック図である。本発明の素数生成装置は、Ｂ−smooth評価器１と素数生成器２と剰余合成器３と乱数発生器４と攻撃対策処理部５と確定的素数判定器６とを有する。Ｂ−smooth評価器１は、設定されるｐのビット長と整数Ｂの値とに基づいて、ｔ次多項式Ｆ（ｐ）に関するＢ−smoothを評価し、攻撃対策を行うべきＦ（ｐ）の最大次数と素数ｐi のビット長とを素数生成器２へ出力する。
【００８９】
素数生成器２は、決められたビット長に応じて素数ｐi を生成して剰余合成器３及び確定的素数判定器６へ出力すると共に、乱数のビット長を乱数発生器４へ出力する。剰余合成器３は、中国人剰余定理を用いてＡを求め、ｈA ＝（Ａ−１）／ｐ1 を計算して乱数発生器４へ出力する。乱数発生器４は、決められたビット長に応じて乱数を発生し、ｈp を求めて攻撃対策処理部５へ出力する。攻撃対策処理部５は、前述の（手段３ａ）または（手段３ｂ）により、所定の条件を満たすか否かを判断して、繰り返し暗号化攻撃に対する対策を施す。確定的素数判定器６は、確定的素数判定にかけて、生成したｐが素数であるか否かを判定し、素数であると判定した場合には、その素数ｐを出力する。
【００９０】
図２，図３は、実施の形態の全体の処理手順を示すフローチャートである。まず、Ｂ−smooth評価器１にて、入力されるｐのビット長とＢの値とに基づいて、ｔ次多項式Ｆ（ｐ）に関するＢ−smoothを評価する（ステップＳ１）。ｐのビット長は512 ビットであり、Ｂは例えば２44とする。（ｐs −１）の因数である多項式Ｆ（ｐ）に関して、素因数分解対策を行う最高次数を決定する。前述した（手段２）を用いたＦ（ｐ）の評価結果は表１のようになる。
【００９１】
【表１】
0003835896.tif 000022
【００９２】
表１において、計算量比は、Ｆ（ｐ）がＢ−smoothである場合に、素因数分解攻撃に必要な計算量の比率を表している。例えば、ｐ＋１がＢ−smoothであった場合、ｐ＋１法に必要な攻撃の計算量はｐ−１法に比べて４倍の計算量がかかることを意味している。
【００９３】
Ｆ（ｐ）がＢ−smoothであった場合、素因数分解攻撃に必要な計算量はＢに比例する。２次以下のＦ（ｐ）はｐi を含んでｐi −smoothであるので、Ｆ（ｐ）を利用した攻撃に必要な計算量はｐi に比例する。また、ｐ−１以外のＦ（ｐ）に対する素因数分解攻撃に必要な計算量を平均化することを考えると、表１における計算量比を鑑みて、ｐ2 ：ｐ3 ：ｐ4 ：ｐ5 ＝８：４：２：１程度にする必要があるので、ｐ1 のビット長は260 ビットとし、ｐ2 ，ｐ3 ，ｐ4 ，ｐ5 のビット長はそれぞれ51ビット，50ビット，49ビット，48ビットとする。
【００９４】
表１の評価結果から、Ｂ−smoothである確率が１／ｐ1/2 以下であるＦ（ｐ）の次数は、４次以上であることがわかる。従って、４次以上のＦ（ｐ）はＢ−smoothでありえないと評価して、２次以下のＦ（ｐ）に対して対策を行う（大きな素数を含ませる）ようにする。
【００９５】
次に、各素数ｐ1 （ｐ−１に対応：260 ビット），ｐ2 （ｐ＋１に対応：51ビット），ｐ3 （ｐ2 ＋ｐ＋１に対応：50ビット），ｐ4 （ｐ2 ＋１に対応：49ビット），ｐ5 （ｐ2 −ｐ＋１に対応：48ビット）を、素数生成器２にて生成する（ステップＳ２）。この場合、基本的にPocklington の素数判定法を用い、ｐi ＝２ｈpi′ｐi ′＋１のｈpi′のビット長の調整により、それぞれに定められたビット長になるように各素数ｐi が生成される。
【００９６】
図４は、（手段３ａ）または（手段３ｂ）を用いる場合の素数ｐ1 の生成手順を示すフローチャートである。まず、（手段３ａ）を用いる場合には、ＲＳＡの暗号化鍵ｅをベースとしたPocklington の素数判定（Maurerの判定法）を用いて259 ビットの素数ｐ1 ′を生成し、（手段３ｂ）を用いる場合には、Pocklington の素数判定を用いて259 ビットの素数ｐ1 ′を生成する（ステップＳ21）。次に、ｐ1 ＝２ｐ1 ′＋１を生成し（ステップＳ22）、ｐ1 に関してPocklington の素数判定を行う（ステップＳ23）。その結果、ｐ1 が素数であると判定された場合（ステップＳ23:YES）、素数ｐ1 を出力する（ステップＳ24）。一方、ｐ1 が素数であると判定されなかった場合（ステップＳ23:NO)、素数ｐ1 ′の再生成を行うべく、処理がＳ21に戻る。
【００９７】
なお、（手段３ａ），（手段３ｂ）を使用しない場合には、Pocklington の素数判定法を用いて260 ビットの素数ｐ1 を生成する。
【００９８】
図５は、ｐ2 ，ｐ3 ，ｐ4 ，ｐ5 の生成手順を示すフローチャートである。まず、14ビットまでの小さな素数で割り切れるか否かを試す完全な素数判定法（ふるい法) を行って、23〜28ビットの素数ｐi ′を生成する（ステップＳ31）。次に、ｐ2 ，ｐ3 ，ｐ4 ，ｐ5 に対応して乱数ｈp2，ｈp3，ｈp4，ｈp5を発生する（ステップＳ32）。但し、ｈp3及びｈp5は３の倍数とし、ｈp4は２の倍数とする。そして、ｐi ＝２ｈpiｐi ′＋１を生成する（ステップＳ33）。この際、ｐ3 ＝３ｋ3 ＋１，ｐ4 ＝４ｋ4 ＋１，ｐ5 ＝６ｋ5 ＋１となる。生成したｐi に関して、Pocklington の素数判定を行う（ステップＳ34）。その結果、ｐi が素数であると判定された場合（ステップＳ34:YES）、素数ｐi を出力する（ステップＳ35）。一方、ｐi が素数であると判定されなかった場合（ステップＳ34:NO)、乱数ｈpiの再生成を行うべく、処理がＳ32に戻る。
【００９９】
次に、ａ1 2 ＋ａ1 ＋１≡０（mod ｐ3 ），ａ2 2 ＋１≡０（mod ｐ4 ），ａ3 2 −ａ3 ＋１≡０（mod ｐ5 ）を満たすａ1 ≡ｇ3 (p3-1)/3  ，ａ2 ≡ｇ4 (p4-1)/4  ，ａ3 ≡ｇ5 (p5-1)/6  を生成する（ステップＳ３）。但し、ｇi は（mod ｐi ）の原始元である。Ａ≡１（mod ｐ1 ），Ａ≡−１（mod ｐ2 ），Ａ≡ａ1 （mod ｐ3 ），Ａ≡ａ2 （mod ｐ4 ），Ａ≡ａ3 （mod ｐ5 ）を満たすＡを中国人剰余定理より求める（ステップＳ４）。また、ｈA ＝（Ａ−１）／ｐ1 を計算して生成する（ステップＳ５）。なお、これらのステップＳ３，Ｓ４及びＳ５の処理は剰余合成器３で行われる。
【０１００】
次いで、53ビットの乱数Ｒを発生する（ステップＳ６）。そして、Ｒｐ2 ｐ3 ｐ4 ｐ5 ＋ｈA が奇数か否かを判断する（ステップＳ７）。奇数である場合には（ステップＳ７:YES）、ステップＳ６に処理が戻り、偶数である場合には（ステップＳ７:NO)、ｈp ＝（Ｒｐ2 ｐ3 ｐ4 ｐ5 ＋ｈA ）／２を計算してｈp を生成する（ステップＳ８）。なお、これらのステップＳ６，Ｓ７及びＳ８の処理は乱数発生器４で行われる。
【０１０１】
（手段３ｂ）を用いて、繰り返し暗号化攻撃に対策を行う場合（ステップＳ９:YES）、Miller-Rabin等の確率的素数判定法を用いて、以下の（ａ）〜（ｃ）の３つの条件が満たされるか否かを検査する（ステップＳ10，Ｓ11）。
（ａ）ｈp は素数
（ｂ）ｈp −１≡０（mod ６）かつ（ｈp −１）／６は素数
（ｃ）ｇｃｄ（ｅ6 −１，（ｐ−１）／２）＝１
【０１０２】
これらの条件が満たされる場合には（ステップＳ10，Ｓ11:YES）、ステップＳ12へ処理が進み、満たされない場合には（ステップＳ10，Ｓ11:NO)、ステップＳ６に処理が戻る。なお、これらのステップＳ９，Ｓ10及びＳ11の処理は攻撃対策処理部５で行われる。
【０１０３】
次に、ｐ＝２ｈp ｐ1 ＋１を生成し（ステップＳ12）、生成したｐをPocklington の確定的素数判定にかける（ステップＳ13）。そして、素数と判定された場合には（ステップＳ13:YES）、512 ビットの素数ｐを出力して（ステップＳ14）、終了する。一方、素数と判定されなかった場合には（ステップＳ13:NO)、ステップＳ６に処理が戻る。なお、これらのステップＳ12，Ｓ13及びＳ14の処理は確定的素数判定器６で行われる。
【０１０４】
ところで、上述の実施の形態では、ｐを512 ビット、Ｂを２44としたが、これは例示であって限定されるものではない。例えば、ｐを1024ビット、Ｂを２50とした場合の（手段２）を用いたＦ（ｐ）の評価結果は表２のようになる。
【０１０５】
【表２】
0003835896.tif 000023
【０１０６】
表２で示される例でも、２次のＦ（ｐ）まで対策を行えば良いことになるので、上の多項式から順に割り当てられる素数ｐ1 ，ｐ2 ，ｐ3 ，ｐ4 ，ｐ5 のビット長は、計算量比を鑑みて、それぞれ515 ビット，110 ビット，109 ビット，108 ビット，107 ビットとなる。
【０１０７】
なお、図２，図３に示すフローチャートにおける素数判定ルーチンを通す前に、小さな素数で割り切れるかを試す「試し割り」を行うことにより、処理の効率化を図るものとする。また、（手段３ｂ）を用いる場合には、ｘ′＝ｙ′＝１と設定する。
【０１０８】
図６は、本発明のハードウェアのシステム構成を示す模式図である。本ハードウェアは、素数生成処理を行う処理装置としてのパーソナルコンピュータ11と、数字データ等を表示するディスプレイ12と、入力装置としてのキーボード13及びマウス14とを備える。パーソナルコンピュータ11は、上述したような本発明の素数生成の処理を行うためのプログラムを、磁気ディスク，ＣＤ−ＲＯＭ等の可搬型記録媒体15、パーソナルコンピュータ11と無線または有線にてプログラム通信が可能である、例えばセンタに備えられた回線先メモリ16、或いは、パーソナルコンピュータ11に備え付けられたＲＡＭ，ハードディスク等の処理装置側メモリ17等の記録媒体からロードする。なお、特許請求の範囲で示された記録媒体は、これらの可搬型記録媒体15，回線先メモリ16，処理装置側メモリ17の何れであっても良い。
【０１０９】
【発明の効果】
本発明では以下に述べるような優れた効果を奏する。（手段１）により、確定的素数判定法を用いるので、合成数は絶対に生成しないで、必ず素数を生成することができる。（手段２）により、ｐs −１の因数であるＦ（ｐ）がＢ−smoothであるか否かの評価基準を導入するようにしたので、素因数分解法への対策を行う必要があるＦ（ｐ）の次数の上限を決定できる。（手段２）により、対策を行う必要がある次数以下のＦ（ｐ）については、大きな素数を持たせるようにしたので、任意のＦ（ｐ）を用いた素因数分解法に対する対策を行える。
【０１１０】
（手段３ａ）により、ｐ−１に含まれる大きな素数ｐ1 に関して、ｐ1 ＝２ｐ1 ′＋１を満たすｐ1 ′も素数とするので、従来法よりも繰り返し暗号化攻撃に強い素数ｐを生成することができる。（手段３ｂ）により、ｐ＝２ｈp ｐ1 ＋１，ｈp ＝６ｈp ′＋１，ｐ1 ＝２ｐ1 ′＋１において、ｈp ，ｈp ′，ｐ1 ，ｐ1 ′を素数としたうえで、ｇｃｄ（ｅ6 −１，（ｐ−１）（ｑ−１）／４）＝１ならば、繰り返し暗号化攻撃に弱い平文が４種類しか存在しないような素数ｐを生成することができる。
【０１１１】
Ｆ（ｐ）に含ませる素数ｐ2 ，ｐ3 ，ｐ4 ，ｐ5 のビットを傾斜配分するようにしたので、素因数分解攻撃に必要な計算量がどのＦ（ｐ）においても同じレベルとすることができる。また、（手段３ａ）を利用する場合、素数ｐ1 を生成する際にＲＳＡの公開鍵ｅを用いたPocklington の素数判定を用いるので、ｅを用いない方法が、ｅ以外を用いたPocklington の判定法によりｐ1 を生成するステップ、及び、ｐ1 に関してｅを用いてMaurerの判定を行うステップの２ステップが必要であるのに比べて、本発明のｅを用いた素数判定方式では、ｅを用いたPocklington の判定法によりｐ1 を生成する１つのステップにて、ｐ1 生成及びｅ判定を同時に行うことができる。
【０１１２】
このようにして本発明により生成された素数をＲＳＡの秘密鍵に用いた場合、従来の素数生成方法と比較して安全性が高い素数を生成できる。
【図面の簡単な説明】
【図１】本発明の素数生成装置の構成を示すブロック図である。
【図２】本発明の素数生成装置の処理手順を示すフローチャートである。
【図３】本発明の素数生成装置の処理手順を示すフローチャートである。
【図４】素数生成器における素数生成（ｐ1 生成）の処理手順を示すフローチャートである。
【図５】素数生成器における素数生成（ｐ2 ，ｐ3 ，ｐ4 ，ｐ5 生成）の処理手順を示すフローチャートである。
【図６】本発明のハードウェアのシステム構成を示す模式図である。
【図７】素数生成の全体の流れを示すフローチャートである。
【図８】  Pocklington の確定的素数判定法の手順を示すフローチャートである。
【図９】繰り返し暗号化攻撃に強い素数を生成するための処理手順を示すフローチャートである。
【図１０】繰り返し暗号化攻撃に強い素数を生成するための処理手順を示すフローチャートである。
【図１１】繰り返し暗号化攻撃に強い素数を生成するための処理手順を示すフローチャートである。
【符号の説明】
１  Ｂ−smooth評価器
２  素数生成器
３  剰余合成器
４  乱数発生器
５  攻撃対策処理部
６  確定的素数判定器
【図１】
0003835896.tif 000025
【図２】
0003835896.tif 000026
【図３】
0003835896.tif 000027
【図４】
0003835896.tif 000028
【図５】
0003835896.tif 000029
【図６】
0003835896.tif 000030
【図７】
0003835896.tif 000031
【図８】
0003835896.tif 000032
【図９】
0003835896.tif 000033
【図１０】
0003835896.tif 000034
【図１１】
0003835896.tif 000035