(57)【特許請求の範囲】
【請求項１】
整数Ａに対し、整数Ａとは異なる整数ＢまたはＢの倍数分だけ整数Ａと異なる整数の集合Ｃに属する要素の素数性を判定する素数判定方法において、
整数ＢまたはＢの倍数を被除数とし、一つまたは複数の整数を除数または除数集合とした場合の第１の剰余または第１の剰余の集合と、整数Ａを被除数とし、上記一つまたは複数の整数を除数または除数集合とした場合の第２の剰余または第２の剰余の集合とを記憶手段に記憶するステップと、
集合Ｃの要素を生成するステップと、
生成された集合Ｃの要素に対し、上記除数の各々について当該除数に対応する第１の剰余および第２の剰余をそれぞれ上記記憶手段から取り出すステップと、
上記除数の各々について、上記記憶手段から取り出された第１の剰余および第２の剰余を用いて、上記生成された集合Ｃの要素を被除数とした場合の剰余を算出するステップとを有することを特徴とする素数判定方法。
【請求項２】
請求項１記載の素数判定方法において、上記除数または除数集合をなる一つまたは複数の整数は、上記剰余を算出するステップが１ワード計算で実行できるように、所定ビットだけ１ワードより短い素数判定方法。
【請求項３】
請求項１記載の素数判定方法において、任意の整数ａと任意の素数ｔに対してｐ＝１＋２ａｔまたはｐ＝−１＋２ａｔの形の整数を要素とする集合を素数性を判定する集合Ｃとする素数判定方法。
【請求項４】
請求項１記載の素数判定方法において、ｔを任意の素数あるいは１として、任意の整数ａに対してｒ＝１＋２ａｔの形となる素数ｒと、任意の素数ｓを法としたときのｒの逆数Ｒと、任意の整数ｂを用いて、ｐ＝１＋２（ｂｓ−Ｒ）ｒの形となる整数を要素とする集合を素数性を判定する集合Ｃとする素数判定方法。
【請求項５】
請求項１記載の素数判定方法において、ｔを任意の素数あるいは１として、任意の整数ａに対してｒ＝−１＋２ａｔの形となる素数ｒと、ｒを法としたときの任意の素数ｓの逆数Ｓと、  任意の整数ｂを用いて、ｐ＝−１＋２（ｂｒ＋Ｓ）ｓの形となる整数を要素とする集合を素数性を判定する集合Ｃとする素数判定方法。
【請求項６】
請求項１記載の素数判定方法において、任意の素数ｓ、ｒに対してＵ＝ｓｒ−１−ｒｓ−１  ｍｏｄ  ｒｓとなる整数Ｕと任意の整数ｍを用いて、ｐ＝Ｕ＋２ｍｒｓの形となる整数を要素とする集合を素数性を判定する集合Ｃとする素数判定方法。
【請求項７】
請求項１記載の素数判定方法において、任意の整数ｉ、ｊと、任意の素数ｓ、ｒと、ｒを法としたときのｓの逆数Ｓと、ｓを法としたときのｒの逆数Ｒと、Ｕ＝（−１＋ｉｓ）＋（２＋ｊｒ−ｉｓ）ｓＳ  ｍｏｄ  ｒｓまたはＵ＝（１＋ｉ）＋（−２＋ｉｓ−ｊｒ）ｓＲ  ｍｏｄ  ｒｓを満たす整数Ｕを用いて、ｐ＝Ｕ＋２ｍｒｓの形となる整数を要素とする集合を素数性を判定する集合Ｃとする素数判定方法。
【請求項８】
請求項１記載の素数判定方法において、該剰余または該剰余集合を求めるのに除数として一つ又は複数の素数又は乱数を用いた素数判定方法。
【請求項９】
請求項１記載の素数判定方法において、該剰余または該剰余集合を求めるのに除数としてｄ（ｉ）＝ａ＋ｂｉの形の整数集合を用いた素数判定方法。
【請求項１０】
整数Ａに対し、整数Ａとは異なる整数ＢまたはＢの倍数分だけ整数Ａと異なる整数の集合Ｃに属する要素の素数性を判定し、判定結果に基づいて素数候補として出力する素数生成方法において、
整数ＢまたはＢの倍数を被除数とし、一つまたは複数の整数を除数または除数集合とした場合の第１の剰余または第１の剰余の集合と、整数Ａを被除数とし、上記一つまたは複数の整数を除数または除数集合とした場合の第２の剰余または第２の剰余の集合とを記憶手段に記憶するステップと、
集合Ｃの要素を生成するステップと、
生成された集合Ｃの要素に対し、上記除数の各々について当該除数に対応する第１の剰余および第２の剰余をそれぞれ上記記憶手段から取り出すステップと、
上記除数の各々について、上記記憶手段から取り出された第１の剰余および第２の剰余を用いて、上記生成された集合Ｃの要素を被除数とした場合の剰余を算出するステップと、
算出された剰余に基づいて、集合Ｃの所定の要素が、その要素自体、１、要素自体の正負の符号を変えたもの以外の数を除数とした場合に剰余が非零になるときに、上記所定の要素を素数候補として出力するステップとを有することを特徴とする素数生成方法。
【請求項１１】
請求項１０記載の素数判定方法において、上記除数または除数集合をなる一つまたは複数の整数は、上記剰余を算出するステップを１ワード計算で実行できるように、所定ビットだけ１ワードより短い素数生成方法。
【請求項１２】
請求項１０または１１記載の素数生成方法において、出力された素数候補に対し確率的素数判定法あるいは確定的素数判定法により素数性の判定を行う素数生成方法。
【請求項１３】
請求項１０、１１または１２記載の素数生成方法において、公開鍵暗号に用いる法数を合成するために上記素数候補を用いる素数生成方法。
【請求項１４】
整数Ａに対し、整数Ａとは異なる整数ＢまたはＢの倍数分だけ整数Ａと異なる整数の集合Ｃに属する要素の素数性を判定する素数判定装置において、
整数ＢまたはＢの倍数を被除数とし、一つまたは複数の整数を除数または除数集合とした場合の第１の剰余または第１の剰余の集合と、整数Ａを被除数とし、上記一つまたは複数の整数を除数または除数集合とした場合の第２の剰余または第２の剰余の集合とを記憶する記憶手段と、
集合Ｃの要素を生成する手段と、
生成された集合Ｃの要素に対し、上記除数の各々について当該除数に対応する第１の剰余および第２の剰余をそれぞれ上記記憶手段から取り出す手段と、
上記除数の各々について、上記記憶手段から取り出された第１の剰余および第２の剰余を用いて、上記生成された集合Ｃの要素を被除数とした場合の剰余を算出する手段とを有することを特徴とする素数判定装置。
【請求項１５】
請求項１４記載の素数判定装置において、上記除数または除数集合をなる一つまたは複数の整数は、上記剰余を算出するステップにおいて１ワード計算で実行できるように、所定ビットだけ１ワードより短い素数判定装置。
【請求項１６】
整数Ａに対し、整数Ａとは異なる整数ＢまたはＢの倍数分だけ整数Ａと異なる整数の集合Ｃに属する要素の素数性を判定し判定結果に基づいて素数候補として出力する素数生成装置において、
整数ＢまたはＢの倍数を被除数とし、１ワードで表される一つまたは複数の整数を除数または除数集合とした場合の第１の剰余または第１の剰余の集合と、整数Ａを被除数とし、上記一つまたは複数の整数を除数または除数集合とした場合の第２の剰余または第２の剰余の集合とを記憶する記憶手段と、
集合Ｃの要素を生成する手段と、
生成された集合Ｃの要素に対し、上記除数の各々について当該除数に対応する第１の剰余および第２の剰余をそれぞれ上記記憶手段から取り出す手段と、
上記除数の各々について、上記記憶手段から取り出された第１の剰余および第２の剰余を用いて、上記生成された集合Ｃの要素を被除数とした場合の剰余を算出する手段と、
算出された剰余に基づいて、集合Ｃの所定の要素が、その要素自体、１、要素自体の正負の符号を変えたもの以外の数を除数とした場合に剰余が非零になるときに、上記所定の要素を素数候補として出力する手段を有することを特徴とする素数発生装置。
【請求項１７】
請求項１６記載の素数生成装置において、上記除数または除数集合をなる一つまたは複数の整数は、上記剰余を算出するステップにおいて１ワード計算で実行できるように、所定ビットだけ１ワードより短い素数生成装置。
【請求項１８】
請求項１６または１７記載の素数生成装置において、公開鍵暗号に用いる法数を合成するために上記素数候補を用いる素数生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば公開鍵暗号に用いる法数生成法に利用される素数判定技術に関するものであり、特にＰ−１法、Ｐ＋１法などの素因数分解攻撃等に対抗するための法数生成に用いることができるようにしたものである。
【０００２】
【従来の技術】
近年のパーソナル・コンピュータの急激な発展と普及、そしてインターネット／イントラネットをはじめとする通信ネットワークの社会への急速な浸透、そしてＣＤ−ＲＯＭなどの大規模な情報媒体の普及を背景として、デジタル情報を簡便に利用者に送り届け、デジタル情報の利用に対する課金を確実に行える技術の普及を望む声が高まっている。
【０００３】
このような情報セキュリティを確保するための技術として、暗号技術とりわけ公開鍵暗号が注目を集めている。公開鍵暗号の一種であるＲＳＡ（Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ、Ａｄｌｅｍａｎ）暗号は、データ保護、認証、電子署名を可能とし、その安全性の高さから公開鍵暗号の標準として確立されつつある。今後デジタル情報社会の発展と共にＲＳＡ暗号の利用機会は急速に拡大することが予想される。
【０００４】
一般にＲＳＡ暗号では、二つの大きな素数の積からなる合成数を法数として用いる。一般にこの素数の生成では、ふるい法と確率的素数判定法の二段階の素数判定が行われる。ふるい法は、素数性を判定する数を、予め用意された素数集合の要素で割ったときの剰余が零かどうか、つまり割り切れるかどうかで素数判定を行う方法である。確率的素数判定法は、調べたい数がある確率をもって合成数であることを判定する方法で、Ｆｅｒｍａｔ判定法、Ｓｏｌｏｖａｙ−Ｓｔｒａｓｓｅｎ法、Ｍｉｌｌｅｒ−Ｒａｂｉｎ法などが知られている。確率的素数判定法は計算負荷が大きいので、通常の素数生成では、ふるい法が併用されることが多い。
【０００５】
一般的な素数生成の手順は以下の通りである。まず乱数生成法によって奇数の乱数を生成する。乱数生成法には、非線形ＦＳＲ乱数発生方式などが知られている。この乱数に対してふるい法を実行する。これによって合成数と判定された場合は、この乱数を適当に増減するか、乱数を作り直すかして、再びふるい法による判定を行う。この処理をふるい法が合成数と判定しない素数候補値が得られるまで繰り返す。ふるい法が合成数と判定しない素数候補値が得られたら、この数をＦｅｒｍａｔ判定法などの確率的素数判定法にかける。確率的素数判定法によって、合成数と判定されない場合は、これを素数として出力する。合成数と判定される場合には、この値を適当に増減するか、乱数を作り直すかして、再びふるい法による判定にかける。以上のような手順により、素数を獲得する。
【０００６】
ＲＳＡ暗号の安全性は、上記法数の素因数分解の困難さに根拠を置いている。したがって、素因数分解法がそのままＲＳＡ暗号の攻撃法となる。この他、素因数分解攻撃法以外にもＲＳＡ暗号の周期性を利用した攻撃法が知られている。
【０００７】
代表的な素因数分解法として、Ｐ−１法、Ｐ＋１法、Ｆｅｒｍａｔの素因数分解法が挙げられる。上記二つはＲＳＡ暗号の法数の素因数の一つをｐとするとき、ｐ−１あるいはｐ＋１が小さな素数の積になっている場合に有効な方法である。このため、Ｐ−１法、Ｐ＋１の方法に対抗するためには、ｐ−１あるいはｐ＋１の素因数が大きな素数を持つようにすればよい。Ｆｅｒｍａｔの素因数分解法は法数の二つの素因数の大きさがほぼ同じときに有効な方法で、これに対しては素因数の大きさを十分異なるようにすればよく、簡単に対抗策をこうじることができる。また、ＲＳＡ暗号の周期性を利用した攻撃法に対しては、ｐ−１の素因数の一つをｒとすると、ｒ−１が十分大きな素因数を持てばこの攻撃法の適用が困難なことが知られている。
【０００８】
上記のＰ−１法、Ｐ＋１法に対抗するため従来技術として、次のアルゴリズムＡに従って素因数を決める方法が知られている。
［アルゴリズムＡ］
（ステップＡ１）  適当に大きな素数ｔを生成する。
（ステップＡ２）  ｒ＝２ａｔ＋１の形の素数ｒを生成する。
（ステップＡ３）  適当に大きな素数ｓを生成する。
（ステップＡ４）  整数Ｒを法ｓでのｒの逆数として、Ｐ＝１＋２（ｂｓ−Ｒ）ｒの形の素数Ｐを生成する。
【０００９】
上記アルゴリズムＡにしたがって生成された素数を因数とする法数は、Ｐ−１法、Ｐ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法に対抗できる法数となっている。しかし、上記の各ステップでふるい法と確率的素数判定法を繰り返すため、アルゴリズムＡに従って素数生成を行うには膨大な計算量を必要とする。
【００１０】
また上記アルゴリズムＡとは別に、安全対策を施した法数を生成する従来技術として、Ｊ．Ｇｏｒｄｏｎによる方法がある。この方法は任意の素数ｓ，ｒに対してＵ＝ｓr-1−ｒs-1  ｍｏｄ  ｒｓとなる整数Ｕと任意の整数ｍを用いて、ｐ＝Ｕ＋２ｍｒｓの形となる整数を法数の素因数の候補とする。ところがこの計算には多倍長のべき乗剰余演算を伴うため、膨大な量の演算を必要とする。この問題を解決するために特開平２−３７３８３号公報の素数生成手法が提案されているが、特開平２−３７３８３号公報の手法も多倍長数の除算を数多く繰り返す必要があるため、パーソナル・コンピュータなどでは大きな計算負荷となってしまう。
【００１１】
上記のアルゴリズムＡ、特開平２−３７３８３号公報の手法などの従来技術とは別に、安全対策を施していない単純な法数の生成に必要な計算量を削減する従来技術としてｐ−ｄｅｌｔａ法が知られている。この方法はふるい法を実行する際の多倍長の除算の回数を削減する方法である。ｐ−ｄｅｌｔａ法は処理のはじめに剰余テーブルを作成することにより繰り返し実行されるふるい法を１ワードで高速処理する方法である。以下にｐ−ｄｅｌｔａ法のアルゴリズムを示す。ここでｐｒｉｍｅｓ［ｉ］は、ｈ個の１ワードよりも小さい相異なる素数の集合のｉ番目の要素とする。
［アルゴリズムＢ］
（ステップＢ１）  ｐに適当な大きさの乱数を代入する。
（ステップＢ２）  ｐ［ｉ］＝ｐ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］  （ｉ＝１，２，・・・・・・，ｈ）、を計算する。
（ステップＢ３）  ｐｄｅｌｔａ＝０とする。
（ステップＢ４）  ｐ［ｉ］＋ｐｄｅｌｔａ≡０  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］（ｉ＝１，２，・・・・・・，ｈ）かどうかを判定する。
全てのｉに対して上式が不成立のときステップＢ６へ。そうでない場合はステップＢ５へ。
（ステップＢ５）  ｐｄｅｌｔａ←ｐｄｅｌｔａ＋２として、ステップＢ４へ。
（ステップＢ６）  ｐ←ｐ＋ｐｄｅｌｔａとしてｐを素数候補として出力する。
【００１２】
上記アルゴリズムＢからわかるように、剰余テーブルｐ［ｉ］（ｉ＝１，２，・・・・・・，ｈ）を予め作成することにより、ｐ−ｄｅｌｔａ法は負荷の大きい多倍長演算を実行せずに、ステップＢ４での１ワード演算でふるい法を実行するので計算量を大幅に削減できる。しかしこの方法は、ステップＢ５からわかるように棄却された候補値を２だけ増加させた値を次の素数候補とするので、Ｐ−１法やＰ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法に対して必ず安全であるような素数を生成することはできない。したがって、この方法は単純な素数の積の法数生成にしか適用することができず、Ｐ−１法やＰ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法対策を施した法数の生成にはｐ−ｄｅｌｔａ法を利用することはできない。
【００１３】
【発明が解決しようとする課題】
ＲＳＡ暗号の法数生成を行うには、一般に第一段階としてふるい法を実行し、得られた素数候補をさらにＦｅｒｍａｔ判定法やＭｉｌｌｅｒ−Ｒａｂｉｎ判定法など、確率的素数判定法を用いて素数性の判定を行う。第一段階のふるい法では多倍長数の除算を繰り返すため、この処理は計算負荷の重いものとなる。これらの２段階の処理を繰り返し、最終的に法数の因数となる素数を獲得する。加えて、Ｐ−１法やＰ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法対策を施すには膨大な多倍長演算を必要とする。
【００１４】
このため処理能力の低いパーソナル・コンピュータなどで、素因数分解攻撃やＲＳＡ暗号の周期性を利用した攻撃に対抗しうる法数生成を行うには、多倍長演算を削減する技術、および法数生成処理に必要とされるメモリ量を削減する技術が重要となる。
【００１５】
本発明の第一の目的は、上記のＰ−１法やＰ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法対策を施した法数の生成時に行われる素数判定・生成法に必要な多倍長演算を削減する技術を提供することにある。
【００１６】
また本発明の第二の目的は、上記の法数生成に必要なメモリ量を削減する技術を提供することにある。
【００１７】
【課題を解決するための手段】
本発明はで上記の課題を解決するために、次に述べるような手段を用いる。
（１）  増加値剰余テーブルの作成
Ｐ−１法やＰ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法対策を施した法数を生成するには上記のアルゴリズムＡ、Ｊ．Ｇｏｒｄｏｎの方法などで素数生成を行わなければならない。これらの方法で、ふるい法によって素数候補値が棄却された場合には、元の素数候補に多倍長の整数を加えたものを次の素数候補としなければならない。この新しい素数候補をふるい法に再びかけるため、多倍長の除算が繰り返し行われることになる。
【００１８】
本発明ではふるい法によって棄却された素数候補を増加させるための多倍長の整数を被除数、素数テーブルの要素を除数としたときの剰余を予め計算し、この値を増加値剰余テーブルとして保持する。そしてこの増加値剰余テーブルの値を用いて、ふるい法に必要な素数テーブルの要素を法としたときの乱整数の剰余を求める計算を行う。素数テーブルの要素の大きさを１ワードより数ビット小さくすると、この増加値剰余テーブルの要素の大きさも１ワードより数ビット小さくなるため、この計算は１ワードで実行できる。このように、Ｐ−１法などの安全対策を施した法数を生成する場合でも、処理の始めに増加値剰余テーブルを作成することによって、以後繰り返される多倍長の計算を回避することができる。
（２）  除数集合の実行時生成
通常のふるい法で用いる素数集合の代わりに、１ワードより数ビット小さい乱数またはｄ（ｉ）＝ａ＋ｂｉの形の整数集合を用いる。この場合、素数集合を記憶保持手段に保持しておく必要がなく、メモリ上に除数集合を保持する必要がないため、演算に必要なメモリ量を削減することができる。
【００１９】
すなわち、本発明によれば、上述の目的を達成するために、整数Ａに対し、整数Ａとは異なる整数ＢまたはＢの倍数分だけ整数Ａと異なる整数の集合Ｃに属する要素の素数性を判定する素数判定方法において、整数ＢまたはＢの倍数を被除数とし、一つまたは複数の整数を除数または除数集合とした場合の剰余または剰余の集合を記憶手段に記憶するステップと、集合Ｃの要素を生成するステップと、生成された集合Ｃの要素に対し、対応する剰余を上記記憶手段から取り出すステップと、上記記憶手段から取り出された剰余を用いて、上記生成された集合Ｃの要素を被除数とし上記一つまたは複数の整数を除数とした場合の剰余を算出するステップとを実行するようにしている。
【００２０】
この場合、任意の整数ａと任意の素数ｔに対してｐ＝１＋２ａｔまたはｐ＝−１＋２ａｔの形の整数を要素とする集合を素数性を判定する集合Ｃとすることができる。また、ｔを任意の素数あるいは１として、任意の整数ａに対してｒ＝１＋２ａｔの形となる素数ｒと、任意の素数ｓを法としたときのｒの逆数Ｒと、任意の整数ｂを用いて、ｐ＝１＋２（ｂｓ−Ｒ）ｒの形となる整数を要素とする集合を素数性を判定する集合Ｃとすることができる。また、ｔを任意の素数あるいは１として、任意の整数ａに対してｒ＝−１＋２ａｔの形となる素数ｒと、ｒを法としたときの任意の素数ｓの逆数Ｓと、  任意の整数ｂを用いて、ｐ＝−１＋２（ｂｒ＋Ｓ）ｓの形となる整数を要素とする集合を素数性を判定する集合Ｃとすることができる。また、任意の素数ｓ、ｒに対してＵ＝ｓr-1−ｒs-1  ｍｏｄｒｓとなる整数Ｕと任意の整数ｍを用いて、ｐ＝Ｕ＋２ｍｒｓの形となる整数を要素とする集合を素数性を判定する集合Ｃとするができる。また、任意の整数ｉ、ｊと、任意の素数ｓ、ｒと、ｒを法としたときのｓの逆数Ｓと、ｓを法としたときのｒの逆数Ｒと、Ｕ＝（−１＋ｉｓ）＋（２＋ｊｒ−ｉｓ）ｓＳ  ｍｏｄｒｓまたはＵ＝（１＋ｉ）＋（−２＋ｉｓ−ｊｒ）ｓＲ  ｍｏｄ  ｒｓを満たす整数Ｕを用いて、ｐ＝Ｕ＋２ｍｒｓの形となる整数を要素とする集合を素数性を判定する集合Ｃとすることができる。
【００２１】
また、該剰余または該剰余集合を求めるのに除数として一つ又は複数の素数又は乱数を用いることができる。また、該剰余または該剰余集合を求めるのに除数としてｄ（ｉ）＝ａ＋ｂｉの形の整数集合を用いることができる。
【００２２】
また、本発明によれば、ふるい法による素数判定方法において、除数としてｄ（ｉ）＝ａ＋ｂｉの形の整数集合を用いるようにしている。
【００２３】
また、本発明は素数生成方法として実現することもできる。また本発明は、装置の実現形態を採用しても良く、コンピュータプログラムの実現形態を採用することもできる。
【００２４】
【発明の実施の態様】
以下に本発明の実施例を説明する。
［実施例１］
図１から４を用いて、本発明によるＰ−１法、Ｐ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法対策を施した法数の素因数をアルゴリズムＡに従って生成する場合の実施例について説明する。
【００２５】
まず図１を用いて本発明による素因数生成の基本構成を説明する。
図１のステップ１０１からステップ１０６に至る処理は以下のように行われる。
（ステップ１０１）  スタート。
（ステップ１０２）  通常のｐ−ｄｅｌｔａ法を使って素数ｔを作成する。
（ステップ１０３）  ステップ１０２で生成された素数ｔをもとにｒ＝２ａｔ＋１の形の素数ｒを作成する。ここでａは正の整数である。
（ステップ１０４）  通常のｐ−ｄｅｌｔａ法を使って素数ｓを生成する。
（ステップ１０５）  Ｒｒ≡１  ｍｏｄ  ｓとなるＲを作成する。
（ステップ１０６）  ステップ１０３で生成された素数ｒ、ステップ１０４で生成された素数ｓ、およびステップ１０５で生成されたＲから、ｐ＝１＋２（ｂｓ−Ｒ）ｒの形の素数ｐを作成する。ここでｂは正の整数である。
（ステップ１０７）  終了。ｐを出力する。
【００２６】
上記ステップ１０５においてｒとｓは素数なので、二つの数は互いに素である。つまりその最大公約数は１となるので、ユークリッドの互除法を用いて法ｓでの素数ｒの逆数Ｒを計算することができる。
【００２７】
次にステップ１０２、１０４における素数生成法について詳細に説明する。二つのステップの手順は全く同じなので、ここではステップ１０２について説明する。
【００２８】
ステップ１０２で生成されるのは単純な形の素数なので、従来技術のｐ−ｄｅｌｔａ法をそのまま用いることができる。ｐ−ｄｅｌｔａ法を繰り返し実行し、１ワードよりも数ビット小さい相異なる素数の集合のどの要素でも割り切れない素数候補を獲得した後、本実施例ではＦｅｒｍａｔ判定法による本格的な判定を行う。Ｆｅｒｍａｔ判定法は、Ｆｅｒｍａｔの小定理に基づく判定法で、ｖを正整数とするとき任意の素数ｘに対して
【００２９】
【数１】
ｖx-1≡１  ｍｏｄ  ｘ
が成立することを利用している。上式が不成立のときは合成数と判定される。
【００３０】
図２はステップ１０２での処理を詳細に説明したものである。ここで、ｈは１ワードよりも数ビット小さい相異なる素数の集合の要素（＝ｐｒｉｍｅｓ［ｉ］）の個数で、ｋは予め定められたＦｅｒｍａｔ判定法を繰り返す回数である。ステップ２０１から２１３までの処理は以下の通りである。なお、ｐｒｉｍｅｓ［ｉ］は、ｄ（ｉ）＝ａ＋ｂｉで代替してもよい。
（ステップ２０１）  スタート。
（ステップ２０２）  多倍長の乱数を生成し、ｔに格納する。
（ステップ２０３）  ｔ［ｉ］＝ｔ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］（ただし、ｉ＝１，２，・・・・・・，ｈ）を計算する。
（ステップ２０４）  ｐｄｅｌｔａ＝０とする。
（ステップ２０５）  ｉ＝１とする。
（ステップ２０６）  ｔ［ｉ］＋ｐｄｅｌｔａ≡０  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］かどうかを判定する。
上式が成立するときステップ２１２へ。上式が不成立のときステップ２０７へ。
（ステップ２０７）  ｉ＝ｈかどうかを判定する。
上式が成立するときステップ２０９へ。上式が不成立のときステップ２０８へ。
（ステップ２０８）  ステップ２０７でｉ＝ｈが成立しないと判定された場合、ｉを１だけ増加させてステップ２０６に戻る。
（ステップ２０９）  ｊ＝１とする。
（ステップ２１０）  （ｐｒｉｍｅｓ［ｊ］）ｔ−１≡１  ｍｏｄ  ｔかどうかを判定する。
上式が成立するときステップ２１３へ。上式が不成立のときステップ２１２へ。
（ステップ２１１）  ステップ２１３でｊ＝ｋが成立しないと判定された場合、ｊを１だけ増加させてステップ２１０に戻る。
（ステップ２１２）  ステップ２１０の判定式が成立しない場合、およびステップ２０６でｔ［ｉ］＋ｐｄｅｌｔａ≡０  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］と判定された場合、ｐｄｅｌｔａを２だけ増加させてステップ２０５に戻る。
（ステップ２１３）  ｊ＝ｋかどうかを判定する。
上式が成立するときステップ２１４へ。上式が不成立のときステップ２１１へ。
（ステップ２１４）  終了。ｔを出力する。
【００３１】
上記ステップ２０２における乱数生成を行う方法として、例えば非線形ＦＳＲ乱数発生方式などが知られている。
【００３２】
次にステップ１０３における素数生成法について詳細に説明する。ここでは、先の従来例のアルゴリズムＡと同様にしてｒ＝２ａｔ＋１を生成してその素数性を判定する。アルゴリズムＡのステップＡ２では、ｒ＝２ａｔ＋１の形の素数候補を得るために、ａを順に増加させていく。このとき、ａ＝ｂａｓｅａ＋ａｄｅｌｔａ、ｂａｓｅａをａの初期値、ａｄｅｌｔａをａの増加値すると、
【００３３】
【数２】
0003796867.tif 000002
とできる。ここでｂａｓｅａは非線形ＦＳＲ乱数発生方式などで生成した乱数とする。ただしｐｒｉｍｅｓ［ｉ］は予め準備された１ワードの大きさの素数集合のｉ番目の要素とする。  ｐｒｉｍｅｓ［ｉ］はｄ（ｉ）＝ａ＋ｂｉで代替することができる。ここで、
【００３４】
【数３】
ｒｅｍａｉｎｄｅｒｓ［ｉ］＝２・ｔ・ｂａｓｅａ＋１  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］
ｍｕｌｄｅｌｔａｓ［ｉ］＝２・ｔ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］
とおくと、
【００３５】
【数４】
ｒ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］≡ｒｅｍａｉｎｄｅｒｓ［ｉ］＋ｍｕｌｄｅｌｔａｓ［ｉ］・ａｄｅｌｔａ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］
となる。上式はｒを素数テーブルの要素の値で割った余りを表しているので、この値が零かどうかを判定することにより、ｒの素数性を判定することができる。ｒｅｍａｉｎｄｅｒｓ［ｉ］およびｍｕｌｄｅｌｔａｓ［ｉ］は１ワードよりも数ビット小さいので、ｒｅｍａｉｎｄｅｒｓ［ｉ］およびｍｕｌｄｅｌｔａｓ［ｉ］を計算し、テーブルとして保持することにより、素数候補となるｒを獲得するまでのｐｒｉｍｅｓ［ｉ］による剰余を１ワード演算で求めることができる。このように通常のｐ−ｄｅｌｔａ法で利用される剰余テーブル以外に、素数候補の増加値のための剰余テーブルｍｕｌｄｅｌｔａｓ［ｉ］も合わせて利用することにより、Ｐ−１法やＰｏｌｌａｒｄの方法、そしてＲＳＡ暗号の周期性を利用した攻撃法対策を施す法数の生成において繰り返し実行されるふるい法に必要な多倍長演算を大幅に削減することができる。
【００３６】
上記のふるい法に加えて、本実施例ステップ１０３ではＦｅｒｍａｔ判定法を実行し、二段階構成の素数生成を行う。
【００３７】
図３は、以上説明したステップ１０３での処理をより詳細に説明するものである。ここで、ステップ１０２で生成された素数ｔが与えられているとする。ステップ３０１から３１５までの処理は以下の通りである。
（ステップ３０１）  スタート。
（ステップ３０２）  １ワードの乱数を生成し、初期値ｂａｓｅａとする。
（ステップ３０３）  ステップ１０２で生成された素数ｔとステップ３０２で生成されたｂａｓｅａを使って、ｒｅｍａｉｎｄｅｒｓ［ｉ］＝２・ｔ・ｂａｓｅａ＋１  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］、ｍｕｌｄｅｌｔａｓ［ｉ］＝２・ｔ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］（ただし、ｉ＝１，２，・・・・・・，ｈ）を計算する。
（ステップ３０４）  ａｄｅｌｔａ＝０とする。
（ステップ３０５）  ｉ＝１とする。
（ステップ３０６）  ｒｅｍａｉｎｄｅｒｓ［ｉ］＋ｍｕｌｄｅｌｔａｓ［ｉ］・ａｄｅｌｔａ＝０かどうかを判定する。
上式が成立するときステップ３１２へ。
上式が不成立のときステップ３０７へ。
（ステップ３０７）  ｉ＝ｈかどうかを判定する。
上式が成立するときステップ３０９へ。
上式が不成立のときステップ３０８へ。
（ステップ３０８）  ステップ３０７でｉ＝ｈが成立しないと判定された場合、ｉを１だけ増加させてステップ３０６に戻る。
（ステップ３０９）  ステップ３０７でｉ＝ｈが成立すると判定された場合、ｒ＝２（ｂａｓｅａ＋ａｄｅｌｔａ）ｔ＋１を計算する。
（ステップ３１０）  ｊ＝１とする。
（ステップ３１１）  （ｐｒｉｍｅｓ［ｊ］）r-1≡１  ｍｏｄ  ｒかどうかを判定する。
上式が成立するときステップ３１３へ。
上式が不成立のときステップ３１２へ。
（ステップ３１２）  ステップ３１１の式が成立しないと判定された場合、およびステップ３０６の判定式が成立すると判定された場合、ａｄｅｌｔａを１だけ増加させてステップ３０５に戻る。
（ステップ３１３）  ｊ＝ｋかどうかを判定する。
上式が成立するときステップ３１５へ。
上式が不成立のときステップ３１４へ。
（ステップ３１４）  ステップ３１３でｊ＝ｋが成立しないと判定された場合、ｊを１だけ増加させてステップ３１１に戻る。
（ステップ３１５）  終了。ｒを出力する。
【００３８】
次にステップ１０６における素数生成法について詳細に説明する。
上記アルゴリズムＡのステップＡ４での計算の場合、ステップ２０２と同様にｂ＝ｂａｓａｂ＋ｂｄｅｌｔａ、ｂａｓｅｂをｂの初期値、ｂｄｅｌｔａをｂの増加値とおく。ここでｂａｓｅｂは非線形ＦＳＲ乱数発生方式などで生成した多倍長の乱数とする。このとき、
【００３９】
【数５】
ｒｅｍａｉｎｄｅｒｓ［ｉ］＝２・ｒ・（ｓ・ｂａｓｅｂ−Ｒ）＋１  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］
ｍｕｌｄｅｌｔａｓ［ｉ］＝２・ｒ・ｓ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］
とおくと、
【００４０】
【数６】
ｐ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］＝ｒｅｍａｉｎｄｅｒｓ［ｉ］＋ｍｕｌｄｅｌｔａｓ［ｉ］・ｂｄｅｌｔａ
によって、ｐのｐｒｉｍｅｓ［ｉ］による剰余を１ワードの演算で求めることができる。上式はｐを素数テーブルの要素の値で割った余りを表しているので、この値が零かどうかを判定することにより、ｐの素数性を判定することができる。ｒｅｍａｉｎｄｅｒｓ［ｉ］およびｍｕｌｄｅｌｔａｓ［ｉ］は１ワードより数ビット小さいので、ｒｅｍａｉｎｄｅｒｓ［ｉ］およびｍｕｌｄｅｌｔａｓ［ｉ］を計算し、テーブルとして保持することにより、素数候補となるｐを獲得するまでのｐｒｉｍｅｓ［ｉ］による剰余を１ワードの演算で求めることができる。このように通常のｐ−ｄｅｌｔａ法で利用される剰余テーブル以外に、素数候補の増加値のための剰余テーブルｍｕｌｄｅｌｔａｓ［ｉ］も合わせて利用することにより、Ｐ−１法やＰｏｌｌａｒｄの方法、そしてＲＳＡ暗号の周期性を利用した攻撃法対策を施す法数の生成において繰り返し実行されるふるい法に必要な多倍長演算を大幅に削減できることがわかる。
【００４１】
上記のふるい法に加えて、本実施例ステップ１０６ではＦｅｒｍａｔ判定法を実行し、二段階構成の素数生成を行う。
【００４２】
図４は上述したステップ１０６での処理をより詳細に説明するものである。ここで、ステップ１０４で生成された素数ｓ、およびステップ１０３で生成された素数ｒが与えられているとする。ステップ４０１から４１５までの処理は以下の通りである。
（ステップ４０１）  スタート。
（ステップ４０２）  １ワードの乱数を生成し、初期値ｂａｓｅｂとする。
（ステップ４０３）  ステップ１０４で生成された素数ｓとステップ１０３で生成された素数ｒ、およびステップ４０２で生成されたｂａｓｅｂを使って、
【００４３】
【数７】
ｒｅｍａｉｎｄｅｒｓ［ｉ］＝２・ｒ・（ｓ・ｂａｓｅｂ−Ｒ）＋１  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］
ｍｕｌｄｅｌｔａｓ［ｉ］＝２・ｒ・ｓ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］
（ただし、ｉ＝１，２，・・・・・・，ｈ）
を計算する。
（ステップ４０４）  ｂｄｅｌｔａ＝０とする。
（ステップ４０５）  ｉ＝１とする。
（ステップ４０６）  ｒｅｍａｉｎｄｅｒｓ［ｉ］＋ｍｕｌｄｅｌｔａｓ［ｉ］・ｂｄｅｌｔａ＝０かどうかを判定する。
上式が成立するときステップ４１２へ。
上式が不成立のときステップ４０７へ。
（ステップ４０７）  ｉ＝ｈかどうかを判定する。
上式が成立するときステップ４０９へ。
上式が不成立のときステップ４０８へ。
（ステップ４０８）  ステップ４０７でｉ＝ｈが成立しないと判定された場合、ｉを１だけ増加させてステップ４０６に戻る。
（ステップ４０９）  ステップ４０７でｉ＝ｈが成立すると判定された場合、ｐ＝１＋２｛（ｂａｓｅｂ＋ｂｄｅｌｔａ）ｓ−Ｒ｝ｒを計算する。
（ステップ４１０）  ｊ＝１とする。
（ステップ４１１）  （ｐｒｉｍｅｓ［ｊ］）p-1≡１  ｍｏｄ  ｐかどうかを判定する。
上式が成立するときステップ４１３へ。
上式が不成立のときステップ４１２へ。
（ステップ４１２）  ステップ４１１の式が成立しないと判定された場合、およびステップ４０６の判定式が成立すると判定された場合、ｂｄｅｌｔａを１だけ増加させてステップ４０５に戻る。
（ステップ４１３）  ｊ＝ｋかどうかを判定する。
上式が成立するときステップ４１５へ。
上式が不成立のときステップ４１４へ。
（ステップ４１４）  ステップ４１３でｊ＝ｋが成立しないと判定された場合、ｊを１だけ増加させてステップ４１１に戻る。
（ステップ４１５）  終了。ｐを出力する。
【００４４】
上記によりアルゴリズムＡに基づいたＰ−１法やＰ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法に対抗できる法数の素因数ｐを獲得できる。
【００４５】
［実施例２］
つぎに、本発明を用いた、Ｐ−１法、Ｐ＋１法、ＲＳＡ暗号の周期性を利用した攻撃法、およびＦｅｒｍａｔの素因数分解法にも対抗できる法数生成の実施例について説明する。
【００４６】
上記実施例１と同じようにして、二つの大きな素数ｐ，ｑを生成する。ただし、Ｌを十分大きな数として、｜ｐ−ｑ｜＞Ｌが成立するようにする。このとき法数ｎ＝ｐｑは、Ｐ−１法やＰ＋１法、そしてＲＳＡ暗号の周期性を利用した攻撃法に対抗できるだけでなく、Ｆｅｒｍａｔの素因数分解法にも対抗することができる。
【００４７】
図５を用いて、本実施例の詳細な説明を行う。以下で手順１は図１に示した素数生成の手順とする。
ステップ５０１から５０６までの処理は以下の通りである。
（ステップ５０１）  スタート。
（ステップ５０２）  手順１によって素数ｐを生成。
（ステップ５０３）  手順１によって素数ｑを生成。
（ステップ５０４）  ｜ｐ−ｑ｜＞Ｌかどうかを判定。
上式が成立すれば、ステップ５０５へ。
上式が成立しなければ、ステップ５０２へ。
（ステップ５０５）  ｎ＝ｐｑとする。
（ステップ５０６）  終了。ｎを法数として出力する。
【００４８】
以上のように法数を生成すれば、Ｐ−１法、Ｐ＋１法、ＲＳＡ暗号の周期性を利用した攻撃法、およびＦｅｒｍａｔの素因数分解法にも対抗できる法数ｎを生成することができる。
【００４９】
［実施例３］
つぎに、実施例１の素数生成手法をハードウエア態様で実現した実施例について説明する。
【００５０】
図６は、実施例１の素数生成装置を示し、この図において、素数ｔ−生成判定部１１および素数ｓ−生成判定部１２はｐ−ｄｅｌｔａ法で素数を判定するものである。素数ｔ−生成判定部１１は、ｔ［ｉ］＝ｔ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］を記憶している剰余テーブル１３を参照して素数性の判定を行う。この動作は図２のステップ２０２〜２１４に関連して説明したとおりである。素数ｓ−生成判定部１２も同様にｓ［ｉ］＝ｓ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］を記憶している剰余テーブル１４を参照して素数性の判定を行う。
【００５１】
素数ｒ−生成判定部１５はｒ＝２ａｔ＋１の素数候補を生成し、整数ａを１だけ増加させながら素数性を判定する。この判定は、ｒｅｍａｉｎｄｅｒ［ｉ］＝２・ｔ・ｂａｓｅａ＋１  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］を記憶している剰余テーブル１６および、ｍｕｌｄｅｌｔａｓ［ｉ］＝２・ｔ  ｍｏｄ  ｐｒｉｍｅｓ［ｉ］を記憶している剰余テーブル１７を参照して行われる。この動作は図３のステップ３０１〜３１５に関連して説明したとおりである。
【００５２】
また、Ｒ−生成部１８は素数ｒ−生成判定部１５から得た素数ｒおよび素数ｓ−生成部１２から得た素数ｓを用いて、Ｒｓ≡１  ｍｏｄ  ｓとなるＲを作成する。
【００５３】
素数ｐ−生成判定部１９は、素数ｓ−生成判定部１２、素数ｒ−生成判定部１５およびＲ−生成部１８からそれぞれ素数ｓ、ｒおよびｒの逆数Ｒを受け取ってｐ＝１＋２（ｂｓ−Ｒ）ｒを生成し、整数ｂを１だけを増加させながら、その素数性を判定する。このとき、ｒｅｍａｉｎｄｅｒ［ｉ］の剰余テーブル２０およびｍｕｌｄｅｌｔａｓ［ｉ］の剰余テーブル２１を参照しながら行われる。この動作はステップ４０１〜４１５に関連して説明したとおりである。
【００５４】
以上の結果、  Ｐ−１法、Ｐ＋１法、ＲＳＡ暗号の周期性を利用した攻撃法、およびＦｅｒｍａｔの素因数分解法にも対抗できる素数を生成できる。しかも、多倍長の計算を回避できる。
【００５５】
【発明の効果】
以上説明したように、本発明によれば、ふるい法によって棄却された素数候補を増加させるための多倍長の整数を被除数、素数テーブルの要素を除数としたときの剰余を予め計算し、この値を増加値剰余テーブルとして保持する。そしてこの増加値剰余テーブルの値を用いて、ふるい法に必要な素数テーブルの要素を法としたときの乱整数の剰余を求める計算を行う。素数テーブルの要素の大きさを１ワードより数ビット小さくすると、この増加値剰余テーブルの要素の大きさも１ワードより数ビット小さくなるため、この計算は１ワードで実行できる。このように、Ｐ−１法などの安全対策を施した法数を生成する場合でも、処理の始めに増加値剰余テーブルを作成することによって、以後繰り返される多倍長の計算を回避することができる。
【００５６】
また、通常のふるい法で用いる素数集合の代わりに、１ワードより数ビット小さい乱数またはｄ（ｉ）＝ａ＋ｂｉの形の整数集合を用いれば、素数集合を記憶保持手段に保持しておく必要がなく、メモリ上に除数集合を保持する必要がないため、演算に必要なメモリ量を削減することができる。
【図面の簡単な説明】
【図１】  本発明の実施例１の素数生成方法を全体として説明するフローチャートである。
【図２】  図１のステップ１０２の詳細を説明するフローチャートである。
【図３】  図１のステップ１０３の詳細を説明するフローチャートである。
【図４】  図１のステップ１０６の詳細を説明するフローチャートである。
【図５】  本発明の実施例２の法数生成方法を説明するフローチャートである。
【図６】  本発明の実施例３の素数判定装置を示すブロック図である。
【符号の説明】
１５    素数ｒ−生成判定部
１６、１７    素数ｒ−生成判定部１５の剰余テーブル
１９    素数ｐ−生成判定部
２０、２１    素数ｐ−生成判定部１９の剰余テーブル
【図１】
0003796867.tif 000003
【図２】
0003796867.tif 000004
【図３】
0003796867.tif 000005
【図４】
0003796867.tif 000006
【図５】
0003796867.tif 000007
【図６】
0003796867.tif 000008