素数生成装置、素数生成方法、及び素数生成プログラム
【課題】ＲＳＡ暗号に用いられる素数を効率よく生成可能な素数生成装置、素数生成方法、及び素数生成プログラムを提供する。
【解決手段】予め定められたビット数以下のデータに対して、少なくとも加算及び除算が可能な演算手段を有する素数生成装置において、予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成し、予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成し、複数の分割素数候補データの各々同士を演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成し、判定データを、演算手段により少なくとも１つの素数で除算することで素数候補が少なくとも１つの素数の倍数でないと判定された場合に、素数候補データに対して素数判定を行ない、素数候補が素数と判定された場合に、素数候補データを素数として出力する。
【解決手段】予め定められたビット数以下のデータに対して、少なくとも加算及び除算が可能な演算手段を有する素数生成装置において、予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成し、予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成し、複数の分割素数候補データの各々同士を演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成し、判定データを、演算手段により少なくとも１つの素数で除算することで素数候補が少なくとも１つの素数の倍数でないと判定された場合に、素数候補データに対して素数判定を行ない、素数候補が素数と判定された場合に、素数候補データを素数として出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、素数生成装置、素数生成方法、及び素数生成プログラムに係り、特に、ＲＳＡ暗号で用いられる素数を生成するための素数生成装置、素数生成方法、及び素数生成プログラムに関する。
【背景技術】
【０００２】
近年、インターネットなどのコンピュータネットワークの発展、携帯電話などの普及に伴い、デジタル情報の交換や電子商取引が急速に拡大してきている。このため、情報を安全かつ確実に転送し、また、データの保全性、データの送信者、受信者の認証を行うための情報セキュリティ技術の重要性が高まっている。
【０００３】
現在、このような情報セキュリティを実現するための技術として、公開鍵暗号技術が知られている。公開鍵暗号は、公開鍵と秘密鍵の２種類の鍵を用意し、公開鍵を公開、秘密鍵を秘密に保持する。公開鍵は暗号化、認証に使用し、秘密鍵は復号、署名に使用する。公開鍵と秘密鍵は相互に関係しているが、公開鍵から秘密鍵を求めることはできないように構成するため、公開鍵を公開しても安全性は保たれるような仕組みになっている。
【０００４】
代表的な公開鍵暗号であるＲＳＡ暗号方式では、２つの大きな素数を用意し、これを秘密とし、その積を公開する。ＲＳＡ暗号方式は、積が公開されていてもその素因数を求めることは極めて困難であるという性質に基づいている。
【０００５】
公開鍵暗号の鍵を作り出すには、最初に大きな素数を用意しなければならない。素数を用意するには、一般に次のような手順で行われる。
【０００６】
まず、乱数発生器により、奇数の乱数を生成し、素数候補とする。次に、この素数候補に対して素数判定を行い、合成数と判定された場合は、新たに素数候補を生成し、合成数と判定されなくなるまで素数判定を繰り返す。合成数と判定されなかった場合は、その素数候補を「素数」として出力する。
【０００７】
ここで生成しようとしている素数を示すデータのビット長は、５１２ビット、１０２４ビットなどで表現される大きな値である。このサイズの乱数が素数である確率はそれほど高くはなく、素数が見つかるまで数十回から数百回素数判定を繰り返す必要がある。さらに素数判定の処理自身も計算量が大きく、素数生成には非常に大きな処理時間がかかる。
【０００８】
素数判定には、確定的素数判定法、或いは確率的素数判定法が用いられるが、いずれも実用上かなりの計算量であることに変わりはない。
【０００９】
従って、これらの確定的、或いは確率的素数判定を行う前に、予め素数候補を比較的計算量の少ないふるいにかけ、上記素数判定を行う回数を減らす工夫がなされている。
【００１０】
ふるいとしては、予め用意したいくつかの小さな素数で素数候補を割り算して割り切れるかどうかを見る方法、上記の素数をすべて掛け合わせた値をあらかじめ計算しておき、ユークリッドの互除法などのアルゴリズムを使用して素数候補との最大公約数を求め、これが１であることを調べる方法、などがある。これらの計算には多倍長の計算が必要となる。
【００１１】
このような過程を経て、暗号鍵が生成されるが、例えば特許文献１には、素数候補Ｐｘを抽出した後、ふるい演算及び素数判定テストを経て、素数候補Ｐｘを素数と認定したらその値を使用して暗号鍵を生成するという方法が開示されている。
【００１２】
生成された暗号鍵は、その後、暗号化鍵を用いる装置に設定され、実際に暗号として使用されることとなる。
【００１３】
このように、暗号鍵を生成する装置と暗号鍵を用いる装置とが異なる場合、例えばＰＣで暗号鍵を生成し、他の装置（以下、暗号鍵利用装置とする）で暗号鍵を用いるとき、暗号鍵が何らかの形で外部を経由するため、生成した暗号鍵が外部に漏洩する虞がある。なお、暗号鍵利用装置として、情報を暗号鍵を用いて暗号化する例えばＩＣカードや決済装置などが挙げられる。
【００１４】
暗号鍵の漏洩を防止するための方法として、暗号鍵生成自体を暗号鍵利用装置内で行うことが考えられる。これによれば、生成した暗号鍵が外部を経由することがないので、暗号鍵の漏洩を防止できることとなる。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００３−１２２２５１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、暗号鍵利用装置は、情報を暗号化するための演算を行なう専用ハードウェアは搭載されているが、暗号鍵を生成するための専用ハードウェアは搭載されていないことが一般的である。
【００１７】
具体的に、情報を暗号化するための演算を行なう専用ハードウェアは、べき剰余演算、乗算剰余演算が実行可能であるが、暗号鍵生成のために必要となる単純な除算等を行なうことができないため、暗号鍵を装置内で生成しようとした場合に、それらの演算を暗号鍵利用装置内のＣＰＵ（Central Processing Unit）が行なうこととなる。
【００１８】
暗号鍵及び暗号鍵生成のために演算するデータのビット長は、ＣＰＵのビット長を大きく上回っているため、暗号鍵利用装置における暗号鍵生成は非常に時間を要するという問題点があった。
【００１９】
本発明は上記問題点に鑑み、ＲＳＡ暗号に用いられる素数を効率よく生成可能な素数生成装置、素数生成方法、及び素数生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
上記目的を達成するために、請求項１記載の素数生成装置は、予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段と、前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成手段と、前記素数候補データ生成手段により生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成手段と、前記分割素数候補データ生成手段により生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成手段と、前記判定データ生成手段により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定手段と、前記素数判定手段により、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力手段と、を有する。
【００２１】
ここで、請求項１の発明では、演算手段は、予め定められたビット数ｍ以下のデータに対して、少なくとも加算、及び除算が可能であり、素数候補データ生成手段は、前記予め定められたビット数ｍよりも大きなビット数Ｌの素数候補を示す素数候補データＮを生成し、分割素数候補データ生成手段は、前記素数候補データ生成手段により生成された素数候補データＮを前記予め定められたビット数ｍ以下となるデータ（ｔビット）に分割することで複数の分割素数候補データＦ（ｋ）を生成し、判定データ生成手段は、前記分割素数候補データ生成手段により生成された複数の分割素数候補データＦ（ｋ）の各々同士を前記演算手段により加算することにより、素数候補データＮが示す素数候補が合成数であるか否かを判定するための判定データＳを生成し、素数判定手段は、前記判定データ生成手段により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データＮに対して素数判定を行い、出力手段は、前記素数判定手段により、前記素数候補が素数と判定された場合に、前記素数候補データＮを素数として出力することにより、ＲＳＡ暗号に用いられる素数を効率よく生成することができる。
【００２２】
また、請求項２の発明は、請求項１の発明において、前記演算手段は、剰余演算、シフト演算、及び符号変換演算の少なくとも１つの演算が可能であり、前記判定データ生成手段は、前記分割素数候補データに対して前記演算手段によりシフト演算、剰余演算、及び符号変換演算の少なくとも１つの演算で得られたデータの各々同士を前記演算手段により加算することで判定データを生成するようにしても良い。
【００２３】
上記目的を達成するために、請求項３記載の素数生成方法は、予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段を有する素数生成装置における素数生成方法であって、前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成段階と、前記素数候補データ生成段階により生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成段階と、前記分割素数候補データ生成段階により生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成段階と、前記判定データ生成段階により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定段階と、前記素数判定段階により、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力段階と、を有する。
【００２４】
ここで、請求項３の発明では、請求項１と同様に作用することにより、請求項１と同様の効果が得られる。
【００２５】
上記目的を達成するために、請求項４記載の素数生成プログラムは、予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段を有する素数生成装置において実行される素数生成プログラムであって、前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成ステップと、前記素数候補データ生成ステップにより生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成ステップと、前記分割素数候補データ生成ステップにより生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成ステップと、前記判定データ生成ステップにより生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数を約数にもつ合成数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定ステップと、前記素数判定ステップにより、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力ステップと、を有する。
【００２６】
ここで、請求項４の発明では、請求項１と同様に作用することにより、請求項１と同様の効果が得られる。
【発明の効果】
【００２７】
本発明によれば、ＲＳＡ暗号に用いられる素数を効率よく生成可能な素数生成装置、素数生成方法、及び素数生成プログラムを提供することができる、という効果が得られる。
【図面の簡単な説明】
【００２８】
【図１】実施形態に係るＩＣカードのハードウェア構成を示す図である。
【図２】素数候補データ及び分割素数候補データを示す図である。
【図３】分割素数候補データを用いて素数生成処理を行なう処理概要を示す図である。
【図４】ふるい処理で用いられる分割候補ビット長、判定データ、判定データを除算する素数の対応を示す模式図である。
【図５】素数生成処理プログラムの流れを示すフローチャートである。
【図６】ふるい処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２９】
以下、図面を参照して、本発明を実施するための最良の形態について詳細に説明する。本実施の形態では、ＲＳＡ暗号の暗号鍵生成処理について記載するが、この説明に先立ち、ＲＳＡ暗号を運用する際の一般的な暗号鍵生成手順の一例について説明する。
【００３０】
まず乱数発生器を用いて、５１２ビット又は１０２４ビット等の乱数を発生させる。上述した５１２ビット又は１０２４ビット等は、現存するＣＰＵ（Central Processing Unit）のビット長を大きく上回るビット長である。以下の説明において、５１２ビット又は１０２４ビット等、ＣＰＵのビット長を上回るビット長を極長ビットと表現する。
【００３１】
このような極長ビットのデータに対して、素数判定が行なわれるが、この素数判定では、処理負荷が大きい確定的、或いは確率的素数判定を行なう前に、ふるい処理が行なわれる。具体的に、このふるい処理は、発生した乱数がいくつかの素数（例えば、３、５、７、１１等の一般的には３桁以下の素数）の倍数になっているか否かをユークリッドの互除法等を用いて検査するもので、このふるい処理により合成数と判定されなかったデータに対して、上記確定的、或いは確率的素数判定を行なうようになっている。そして、素数であることが判定されると、その素数を用いて暗号鍵が生成される。なお、確定的素数判定方法の例としては、ＡＫＳ素数判定法が挙げられ、確率的素数判定方法の例としてはフェルマーテストやミラー・ラビン素数判定法が挙げられる。
【００３２】
上述したふるい処理と、確定的、或いは確率的素数判定で行なわれる主要な演算は異なり、前者では除算が繰り返し行なわれ、後者では乗算剰余演算、べき剰余演算が行なわれるようになっている。具体的には、一般的なふるい処理で用いられるユークリッドの互除法は、ａをｂで割った余りをｒとすると、ａとｂとの最大公約数はｂとｒとの最大公約数に等しいというアルゴリズムであるので、このアルゴリズムを実行した場合には、上述した除算が繰り返し行なわれることとなる。一方、乗算剰余演算はａとｂとの積をｍで割ったときの余りを求める演算であり、べき剰余演算はａのｂ乗をｍで割ったときの余りを求める演算である。
【００３３】
いずれも極長ビットのデータに対して行なわれる演算であるが、乗算剰余演算、べき剰余演算は、情報を暗号化する場合にも行なわれる演算であることから、パソコンほどのＣＰＵを搭載することはできないが、暗号化を行なう装置（例えばＩＣカードや決済端末）には、乗算剰余演算、べき剰余演算を行なうための専用チップが搭載されている。
【００３４】
従って、ＩＣカードや決済端末において、暗号鍵を生成する場合は、上述したふるい処理をいかに効率的に行なうかが重要な課題となる。
【００３５】
以上の説明を踏まえ、以下本実施の形態について説明する。図１は本発明の素数生成装置を適用したＩＣカードのハードウェア構成を示す図であるが、これに限らず決済端末等、携帯型で暗号化を行なう装置に適用することができる。また、耐タンパモジュール（ＴＲＭ：Tamper Resistant Module）のようなチップ内部に強固で粘着力の高いコーティングを施し、表面を剥がすと内部の回路が完全に破壊されるようにした装置に適用しても良い。
【００３６】
図１に示されるように、ＩＣカード１０は、ＣＰＵ１２、ＤＳＰ（Digital Signal Processor）１４、入出力部１６、ＲＯＭ（Read Only Memory）１８、ＲＡＭ（Random Access Memory）２０、及び乱数発生器２２を含んで構成される。
【００３７】
このうち、ＣＰＵ１２は、予め定められたビット数（本実施の形態ではｍビット）以下のデータに対して、少なくとも加算、及び除算が可能となっている。さらに、ＣＰＵ１２は、剰余演算、シフト演算、及び符号変換演算の少なくとも１つ演算が可能であっても良い。なお、いうまでもなく、剰余演算とはａをｂで割った余りｒを求める演算であり、シフト演算とは２進数のビットパターンを右または左にずらす演算であり、符号変換演算とは、ａに対して−ａを求める演算である。いずれの演算も、一般的なＣＰＵであれば可能な演算である。なお、本実施の形態では、符号変換演算した後に加算されることから、符号変換演算が可能なことは、減算が可能であることを示している。
【００３８】
また、演算手段であるＣＰＵ１２は、予め定められたビット数より大きいビット数のデータに対しても、例えばそのデータを予め定められたビット数以下のデータに分割して演算させることで、処理速度は落ちるが演算自体は可能である。
【００３９】
上述したビット数を示すｍは、４、８、１６等、一般的に２のべきである。また、ＩＣカード１０や上述した決済端末に搭載されたＣＰＵは、パソコン等に搭載されるＣＰＵと比較すると、やはり演算速度は非常に遅いことが多い。
【００４０】
ＤＳＰ１４は、暗号化する際に必要な演算を行なうための専用チップであり、例えば暗号化したい情報、暗号鍵を設定することで、暗号化された情報を出力するようになっている。そして、その際に必要となる極長ビットのデータに対する乗算剰余演算、及びべき剰余演算が可能となっている。
【００４１】
入出力部１６は、ＩＣカード１０と他装置との間で無線通信を行なうためのものであり、特に本実施の形態では、ＩＣカード１０を動作させるための電源電力を供給するものでもある。具体的に入出力部１６には、アンテナコイルや、電源電力を蓄電するコンデンサなどが組み込まれており、アンテナコイル内を通り抜ける磁力線の数が変化すると起電力が誘起されるようになっている。
【００４２】
ＲＯＭ１８は、フラッシュメモリなどの不揮発性の記憶装置であり、後述するフローチャートに示される素数生成処理を行なうためのプログラムや、ＩＣカードの仕様に応じたプログラム等が記憶される。ＲＡＭ２０は、各プログラム等により、処理に応じて一時的に使用される揮発性の記憶装置である。
【００４３】
乱数発生器２２は、ＣＰＵ１２の指示で極長ビットの奇数の乱数を発生させ、発生された乱数は、ＲＡＭ２０に出力され、保持される。
【００４４】
次に、上述したＩＣカード１０において実行される素数生成処理の概要を図面を用いて説明する。図２には、ＲＡＭ２０に出力された素数候補データＮと複数の分割素数候補データＦ（ｋ）とが示されている。
【００４５】
本実施の形態に係る素数生成処理において、素数候補データＮは、上述した乱数発生器２２により生成された極長ビット（Ｌビット）のデータである。分割素数候補データＦ（ｋ）は、素数候補データＮをＣＰＵのビット長であるｍビット数以下となるデータに分割したもので、この図の場合は、素数候補データＮをｔ（ｔ＜ｍ）ビットずつ分割することで、各々のＦ（ｋ）のビット長をｔビットとしている。複数の分割素数候補データＦ（ｋ）は、同図の場合、Ｍ（＝Ｌ／ｔ）個のｔビットのデータＦ（ｋ）で構成される。
【００４６】
図３に示されるように、本実施の形態に係る素数生成処理では、複数の分割素数候補データＦ（ｋ）の各々同士をＣＰＵ１２により加算することにより、素数候補データＮが示す素数候補が合成数であるか否かを判定するための判定データＳを生成する。
【００４７】
さらにＣＰＵ１２が、剰余演算、シフト演算、及び符号変換演算の少なくとも１つの演算が可能であれば、同図に示されるように、複数の分割素数候補データＦ（ｋ）に対してシフト演算、剰余演算、及び符号変換演算の少なくとも１つの演算で得られたデータの各々同士を加算することで判定データＳを生成する。
【００４８】
生成された判定データＳを、ＣＰＵ１２により少なくとも１つの素数で除算することにより素数候補が少なくとも１つの素数の倍数ではないと判定された場合に、素数候補データＮに対して確定的、或いは確率的素数判定処理を行なう。
【００４９】
次に、図４を用いて上記判定データＳの生成方法について説明する。図４は、予め素数生成プログラムが参照する情報として、ＲＯＭ１８に記憶された情報を表す模式図であり、ふるい処理で用いられる分割候補ビット長、判定データＳ、判定データＳを除算する素数の対応を示している。
【００５０】
具体的には、例えば「分割素数候補ビット長」が１であれば、「判定データＳ」に記載された数式に従って演算し、後述するように演算結果を素数３で除算するようになっている。
【００５１】
同図に示される「分割素数候補ビット長」は上述したビット長ｔに対応している。「判定データＳ」におけるΣは、ｋ＝０〜Ｍ−１までの総和を示している。また、記号「^」はべきを、記号「＊」は乗算を、記号「％」は剰余演算を、記号「＜＜」は左シフト演算をそれぞれ示す。例えば、Ｓ＝Σ（−１）^ｋ＊Ｆ（ｋ）は、以下の式を示す。
Ｓ＝Ｆ（０）−Ｆ（１）＋Ｆ（２）−Ｆ（３）＋…（−１）^（Ｍ−１）＊Ｆ（Ｍ−１）
すなわち、分割素数候補ビット長が２で３の倍数か否かを判定する場合には、同図に示されるように、素数候補データＮを１ビットごとに区切って、ビット単位で加算、減算する。下位のほうから、０ビット目、１ビット目、３ビット目、とビット番号を振った時に偶数ビット目は加算、奇数ビット目は減算する。計算結果が３で割り切れるかどうか判定し、割り切れた場合は、素数候補データＮは３の倍数、割り切れない場合は、３の倍数ではない、と判定する。
【００５２】
また、同図に示されるように、分割素数候補ビット長ｔが２の場合は、２つの判定データＳの求め方が存在し、一方は素数候補データＮが３の倍数であるか否かを判定でき、他方は素数候補データＮが５の倍数であるか否かを判定できる。
【００５３】
さらに、分割素数候補ビット長ｔが６の場合は、判定データＳによって、素数候補データＮが３、又は７の倍数であるか否かを判定できる。すなわち、一つの判定データＳを求めることで、複数の素数の倍数であるか否かが判定できる。
【００５４】
なお、同図に示される内容の一部を詳細に説明すると、素数候補データＮが３の倍数か否かを判定するには素数候補データＮを２ビットごとに区切って、各Ｆ（ｋ）を０から３の間の数と考えて加算する。素数候補データＮが１０２４ビット程度であれば、計算結果は３２ビット以内に収まるので、判定データＳが３で割り切れるか否か判定し、割り切れた場合は、素数候補は３の倍数、割り切れない場合は、３の倍数ではない、と判定する。
【００５５】
また、素数候補データＮが５の倍数か否かを判定するには素数候補データＮを２ビットごとに区切って、各Ｆ（ｋ）を０から３の間の数と考えて、加算、減算する。下位のＦ（ｋ）から、０番目、１番目、３番目、と番号を振った時に、偶数番号のＦ（ｋ）値は加算、奇数番号のＦ（ｋ）値は減算する。計算結果が５で割り切れるか否か判定し、割り切れた場合は、素数候補データＮは５の倍数、割り切れない場合は、５の倍数ではない、と判定する。
【００５６】
また、素数候補データＮが７の倍数か否かを判定するには、素数候補データＮを４ビットごとに区切って、各Ｆ（ｋ）を０から１５の間の数と考えて、シフト及び加算をする。下位のＦ（ｋ）から、０番目、１番目、２番目、と番号を振った時に、３の倍数番号のＦ（ｋ）値はそのまま加算、(３の倍数＋１)番号のＦ（ｋ）値は１ビット左シフトしてから加算、(３の倍数＋２)番号のＦ（ｋ）値は２ビット左シフトしてから加算する。判定データＳが７で割り切れるか否か判定し、割り切れた場合は、素数候補データＮは７の倍数、割り切れない場合は、７の倍数ではない、と判定する。
【００５７】
以上は、ひとつの素数の倍数か否かを判定する方法であったが、複数の素数の倍数か否かを判定する、同図に示される内容の一部を詳細に説明する。
【００５８】
素数候補データＮが３か５の倍数か否かを判定するには、素数候補データＮを４ビットごとに区切って、各Ｆ（ｋ）を０から１５の間の数と考えて合計する。判定データＳが３、又は５で割り切れるか否かで、素数候補データＮがそれぞれ３、又は５の倍数か否かを判定する。
【００５９】
素数候補データＮが３、５、７、１３、１７、又は２４１の倍数か否かを判定するには、素数候補データＮを２４ビットごとに区切って、各Ｆ（ｋ）を０から２の２４乗−１の間の数と考えて合計する。計算結果が３、５、７、１３、１７、２４１で割り切れるか否かで、素数候補データＮが３、５、７、１３、１７、又は２４１の倍数か否かを判定する。
【００６０】
この他にも、極長ビットのデータの除算やユークリッドの互除法による演算を回避しつつ、素数候補データＮがある小さな素数を約数としてもつか否かを判定する方法はいくつもあり、これらを適当に組み合わせることにより、素数候補データＮが複数の素数を約数としてもつか否かの判定を行うことができる。
【００６１】
また、素数候補データＮのビット長Ｌが分割したいｔの倍数ではない場合、すなわち、Ｌ＝ｑｔ＋ｒ（ｒ≠０）の場合、ｔの倍数となるように、素数候補データＮの上位に（ｔ−ｒ）ビット分の０を付け足すことにより、素数候補データＮのビット長ＬをＬ＋ｔ−ｒとすることで、素数候補データＮのビット長をｔの倍数とすることができる。
【００６２】
なお、同図に示される模式図において、分割素数候補ビット長が、例えば５、７、９などについては記載されていないが、以下の方法を用いることで任意の分割素数候補ビット長ｔを選ぶことができる。
【００６３】
ｍビット以下の任意の分割素数候補ビット長ｔに対し、まず２＾ｔ−1の素因数ｐを求めておき、次にＳ＝ΣＦ(ｋ)を求め（Ｆ（ｋ）はｔビット）、ｐ｜Ｓならばｐ｜Ｎとなる（Ｎ＝素数候補データ）ので、任意の分割素数候補ビット長を選ぶことができる。なお、ａ｜ｂは、ａがｂの約数であることを示している。
【００６４】
他の方法としては、ｍビット以下の任意の分割素数候補ビット長ｔに対し、まず２＾ｔ＋1の素因数ｐを求めておき、次にＳ＝Σ（−１）^ｋ＊Ｆ(ｋ)を求め（Ｆ（ｋ）はｔビット）、ｐ｜Ｓならばｐ｜Ｎとなる（Ｎ＝素数候補データ）ので、この方法によっても任意の分割素数候補ビット長を選ぶことができる。
【００６５】
上述した２つの方法以外にも方法があるが、ここでは省略する。例えば、ｔ＝５の場合、２＾ｔ−1＝３１で、これは素数であるので、素数候補データＮが３１の倍数かどうかを判定できる。この場合、ひとつの素数３１しか判定できないが、判定を効率化するには、なるべく異なる多くの素因数からなる値を見つけることが重要である。例えば、ｔ=１０の場合、２＾ｔ−1＝１０２３＝３＊１１＊３１で、３つの素数の倍数か否か判定することができる。
【００６６】
また、ｍビット以下の分割素数候補データＦ（ｋ）を用いて、素数候補データＮがある素数の倍数か否かを判定可能な素数は、図４に示される素数に限るものではない。さらに、図４に示される判定データＳのいずれを用いて判定するかを、ＩＣカード１０の仕様等に応じて定めるようにすると、より効率的な判定が可能である。
【００６７】
以上説明したふるい処理を用いた素数生成処理を、フローチャートを用いて説明する。図５は、素数生成プログラムの流れを示すフローチャートであり、ＣＰＵ１２により実行される。
【００６８】
まず、ステップ１０１で、乱数発生器２２により予め定められたビット数（本実施の形態ではｍビット）よりも大きなビット数の素数候補を示す素数候補データＮを生成させる。次のステップ１０２で上述したふるい処理を行なう。このふるい処理の詳細は、図６で説明する。
【００６９】
次のステップ１０３で、素数候補データＮは合成数であるか否かを判定する。ここでの合成数とは、ふるい処理で除算された素数を約数にもつ合成数を意味し、それ以外の合成数を含むものではない。
【００７０】
ステップ１０３で肯定判定した場合には、ステップ１０１の処理に戻る。一方、ステップ１０３で素数候補データＮが上述した意味での合成数ではないと判定した場合には、ステップ１０４で、確定的、或いは確率的素数判定処理を行なう。すなわち、素数候補が少なくとも１つの素数を約数にもつ合成数ではないと判定された場合に、素数候補データＮに対して素数判定を行なう。
【００７１】
次のステップ１０５で、素数候補データＮが素数判定処理によって素数と判定されたか否かを判定する。ステップ１０５で否定判定した場合には、ステップ１０１の処理に戻る。一方、ステップ１０５で素数候補データＮが素数と判定した場合に、ステップ１０６で、素数候補データＮを素数として例えばＲＯＭ１８に出力して処理を終了する。
【００７２】
なお、確率的素数判定の場合は、「合成数である」又は「どちらとも言えない」という結果しか得られないため、ステップ１０６では擬素数として出力されることとなるが、確率的素数判定法は精度を上げることが可能であり、例えば確率的素数判定法の一つであるミラー・ラビン素数判定法では、ある範囲全てで検査することで確定的素数判定法とすることができる。
【００７３】
次に、上記ステップ１０２のふるい処理を、図６のフローチャートを用いて説明する。まず、ステップ２０１で、分割素数候補データＦ（０）、…、Ｆ（Ｍ−１）を生成する（図２参照）。次のステップ２０２でループカウンタｋ、及び判定データＳを０で初期化する。
【００７４】
次のステップ２０３で、変数ＢにＦ（ｋ）に対して剰余演算、シフト演算、符号変換演算したデータを代入する。剰余演算（％）、シフト演算（＜＜）、符号変換演算（−）は、図４に示す模式図に従って行なわれるが、模式図に示される判定データＳのうちのいずれの判定データＳにより判定を行なうかは、予め定めておく。その場合、模式図のうちの一つの判定データＳで判定しても良いし、複数の判定データＳで判定しても良い。
【００７５】
次のステップ２０４で、判定データＳに変数Ｂを加えたものを改めて判定データＳとし、ステップ２０５でループカウンタｋを１だけ増分する。
【００７６】
次のステップ２０６で、ループカウンタｋがＭ−１より大きいか否か判定する。これは全てのＦ（ｋ）に対する処理が終了したか否かの判定である。ステップ２０６で否定判定した場合には、ステップ２０３の処理に戻り、肯定判定した場合には、ステップ２０７で判定データＳに対して素数で除算する。ここでの素数は、図４に示される素数である。従って、このステップ２０７の処理は、複数の素数に対して判定可能な場合は、複数の素数による除算が行なわれる。
【００７７】
ステップ２０８で割り切れたか否か、すなわち、少なくとも１つの素数を約数にもつ合成数であるか否かを判定し、肯定判定した場合には、ステップ２０９で、素数候補データＮは除算された素数を約数にもつ合成数と判定し、否定判定した場合には、素数候補データＮは除算した素数を約数にもたないと判定して処理を終了する。
【００７８】
以上説明したように、本実施の形態では、ふるい処理をＣＰＵ１２のビット数以下のデータにより行なうため、効率よくふるい処理を行なうことができる。これにより、例えばＩＣカードや決済端末のようなＣＰＵの処理能力が比較的低い装置においても、自装置内で暗号鍵を生成することが可能となる。
【００７９】
この場合、従来のように暗号鍵が何らかの形で外部を経由することを排除できる結果、暗号鍵の漏洩を防止することもできる。
【００８０】
また、判定データＳを求めるためのＦ（ｋ）は、全てＣＰＵ１２のビット数以下のデータであるため、極長ビットそのものを演算するよりも遙かに効率よく演算することが可能である。また、判定データＳを求める際に用いられる演算（加算、乗算、シフト演算等）はＣＰＵ１２が可能な基本的な演算であるため、処理負荷を低減することができる。これにより、使用する電力を低減できるため、携帯型の装置には非常に相性がよいふるい処理であるといえる。
【００８１】
なお、本実施の形態ではＩＣカード１０を適用例として示したが、ＲＳＡ暗号において対象となる極長ビット長は、パソコンのＣＰＵのビット数よりも遙かに大きいため、パソコンに対しても適用できることは言うまでもない。
【００８２】
また、図５、図６で説明したフローチャートの処理の流れは一例であり、本発明の主旨を逸脱しない範囲内で処理順序を入れ替えたり、新たなステップを追加したり、不要なステップを削除したりすることができることは言うまでもない。
【符号の説明】
【００８３】
１０ ＩＣカード
１２ ＣＰＵ
１４ ＤＳＰ
１６ 入出力部
１８ ＲＯＭ
２０ ＲＡＭ
２２ 乱数発生器
【技術分野】
【０００１】
本発明は、素数生成装置、素数生成方法、及び素数生成プログラムに係り、特に、ＲＳＡ暗号で用いられる素数を生成するための素数生成装置、素数生成方法、及び素数生成プログラムに関する。
【背景技術】
【０００２】
近年、インターネットなどのコンピュータネットワークの発展、携帯電話などの普及に伴い、デジタル情報の交換や電子商取引が急速に拡大してきている。このため、情報を安全かつ確実に転送し、また、データの保全性、データの送信者、受信者の認証を行うための情報セキュリティ技術の重要性が高まっている。
【０００３】
現在、このような情報セキュリティを実現するための技術として、公開鍵暗号技術が知られている。公開鍵暗号は、公開鍵と秘密鍵の２種類の鍵を用意し、公開鍵を公開、秘密鍵を秘密に保持する。公開鍵は暗号化、認証に使用し、秘密鍵は復号、署名に使用する。公開鍵と秘密鍵は相互に関係しているが、公開鍵から秘密鍵を求めることはできないように構成するため、公開鍵を公開しても安全性は保たれるような仕組みになっている。
【０００４】
代表的な公開鍵暗号であるＲＳＡ暗号方式では、２つの大きな素数を用意し、これを秘密とし、その積を公開する。ＲＳＡ暗号方式は、積が公開されていてもその素因数を求めることは極めて困難であるという性質に基づいている。
【０００５】
公開鍵暗号の鍵を作り出すには、最初に大きな素数を用意しなければならない。素数を用意するには、一般に次のような手順で行われる。
【０００６】
まず、乱数発生器により、奇数の乱数を生成し、素数候補とする。次に、この素数候補に対して素数判定を行い、合成数と判定された場合は、新たに素数候補を生成し、合成数と判定されなくなるまで素数判定を繰り返す。合成数と判定されなかった場合は、その素数候補を「素数」として出力する。
【０００７】
ここで生成しようとしている素数を示すデータのビット長は、５１２ビット、１０２４ビットなどで表現される大きな値である。このサイズの乱数が素数である確率はそれほど高くはなく、素数が見つかるまで数十回から数百回素数判定を繰り返す必要がある。さらに素数判定の処理自身も計算量が大きく、素数生成には非常に大きな処理時間がかかる。
【０００８】
素数判定には、確定的素数判定法、或いは確率的素数判定法が用いられるが、いずれも実用上かなりの計算量であることに変わりはない。
【０００９】
従って、これらの確定的、或いは確率的素数判定を行う前に、予め素数候補を比較的計算量の少ないふるいにかけ、上記素数判定を行う回数を減らす工夫がなされている。
【００１０】
ふるいとしては、予め用意したいくつかの小さな素数で素数候補を割り算して割り切れるかどうかを見る方法、上記の素数をすべて掛け合わせた値をあらかじめ計算しておき、ユークリッドの互除法などのアルゴリズムを使用して素数候補との最大公約数を求め、これが１であることを調べる方法、などがある。これらの計算には多倍長の計算が必要となる。
【００１１】
このような過程を経て、暗号鍵が生成されるが、例えば特許文献１には、素数候補Ｐｘを抽出した後、ふるい演算及び素数判定テストを経て、素数候補Ｐｘを素数と認定したらその値を使用して暗号鍵を生成するという方法が開示されている。
【００１２】
生成された暗号鍵は、その後、暗号化鍵を用いる装置に設定され、実際に暗号として使用されることとなる。
【００１３】
このように、暗号鍵を生成する装置と暗号鍵を用いる装置とが異なる場合、例えばＰＣで暗号鍵を生成し、他の装置（以下、暗号鍵利用装置とする）で暗号鍵を用いるとき、暗号鍵が何らかの形で外部を経由するため、生成した暗号鍵が外部に漏洩する虞がある。なお、暗号鍵利用装置として、情報を暗号鍵を用いて暗号化する例えばＩＣカードや決済装置などが挙げられる。
【００１４】
暗号鍵の漏洩を防止するための方法として、暗号鍵生成自体を暗号鍵利用装置内で行うことが考えられる。これによれば、生成した暗号鍵が外部を経由することがないので、暗号鍵の漏洩を防止できることとなる。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００３−１２２２５１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、暗号鍵利用装置は、情報を暗号化するための演算を行なう専用ハードウェアは搭載されているが、暗号鍵を生成するための専用ハードウェアは搭載されていないことが一般的である。
【００１７】
具体的に、情報を暗号化するための演算を行なう専用ハードウェアは、べき剰余演算、乗算剰余演算が実行可能であるが、暗号鍵生成のために必要となる単純な除算等を行なうことができないため、暗号鍵を装置内で生成しようとした場合に、それらの演算を暗号鍵利用装置内のＣＰＵ（Central Processing Unit）が行なうこととなる。
【００１８】
暗号鍵及び暗号鍵生成のために演算するデータのビット長は、ＣＰＵのビット長を大きく上回っているため、暗号鍵利用装置における暗号鍵生成は非常に時間を要するという問題点があった。
【００１９】
本発明は上記問題点に鑑み、ＲＳＡ暗号に用いられる素数を効率よく生成可能な素数生成装置、素数生成方法、及び素数生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
上記目的を達成するために、請求項１記載の素数生成装置は、予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段と、前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成手段と、前記素数候補データ生成手段により生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成手段と、前記分割素数候補データ生成手段により生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成手段と、前記判定データ生成手段により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定手段と、前記素数判定手段により、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力手段と、を有する。
【００２１】
ここで、請求項１の発明では、演算手段は、予め定められたビット数ｍ以下のデータに対して、少なくとも加算、及び除算が可能であり、素数候補データ生成手段は、前記予め定められたビット数ｍよりも大きなビット数Ｌの素数候補を示す素数候補データＮを生成し、分割素数候補データ生成手段は、前記素数候補データ生成手段により生成された素数候補データＮを前記予め定められたビット数ｍ以下となるデータ（ｔビット）に分割することで複数の分割素数候補データＦ（ｋ）を生成し、判定データ生成手段は、前記分割素数候補データ生成手段により生成された複数の分割素数候補データＦ（ｋ）の各々同士を前記演算手段により加算することにより、素数候補データＮが示す素数候補が合成数であるか否かを判定するための判定データＳを生成し、素数判定手段は、前記判定データ生成手段により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データＮに対して素数判定を行い、出力手段は、前記素数判定手段により、前記素数候補が素数と判定された場合に、前記素数候補データＮを素数として出力することにより、ＲＳＡ暗号に用いられる素数を効率よく生成することができる。
【００２２】
また、請求項２の発明は、請求項１の発明において、前記演算手段は、剰余演算、シフト演算、及び符号変換演算の少なくとも１つの演算が可能であり、前記判定データ生成手段は、前記分割素数候補データに対して前記演算手段によりシフト演算、剰余演算、及び符号変換演算の少なくとも１つの演算で得られたデータの各々同士を前記演算手段により加算することで判定データを生成するようにしても良い。
【００２３】
上記目的を達成するために、請求項３記載の素数生成方法は、予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段を有する素数生成装置における素数生成方法であって、前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成段階と、前記素数候補データ生成段階により生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成段階と、前記分割素数候補データ生成段階により生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成段階と、前記判定データ生成段階により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定段階と、前記素数判定段階により、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力段階と、を有する。
【００２４】
ここで、請求項３の発明では、請求項１と同様に作用することにより、請求項１と同様の効果が得られる。
【００２５】
上記目的を達成するために、請求項４記載の素数生成プログラムは、予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段を有する素数生成装置において実行される素数生成プログラムであって、前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成ステップと、前記素数候補データ生成ステップにより生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成ステップと、前記分割素数候補データ生成ステップにより生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成ステップと、前記判定データ生成ステップにより生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数を約数にもつ合成数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定ステップと、前記素数判定ステップにより、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力ステップと、を有する。
【００２６】
ここで、請求項４の発明では、請求項１と同様に作用することにより、請求項１と同様の効果が得られる。
【発明の効果】
【００２７】
本発明によれば、ＲＳＡ暗号に用いられる素数を効率よく生成可能な素数生成装置、素数生成方法、及び素数生成プログラムを提供することができる、という効果が得られる。
【図面の簡単な説明】
【００２８】
【図１】実施形態に係るＩＣカードのハードウェア構成を示す図である。
【図２】素数候補データ及び分割素数候補データを示す図である。
【図３】分割素数候補データを用いて素数生成処理を行なう処理概要を示す図である。
【図４】ふるい処理で用いられる分割候補ビット長、判定データ、判定データを除算する素数の対応を示す模式図である。
【図５】素数生成処理プログラムの流れを示すフローチャートである。
【図６】ふるい処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２９】
以下、図面を参照して、本発明を実施するための最良の形態について詳細に説明する。本実施の形態では、ＲＳＡ暗号の暗号鍵生成処理について記載するが、この説明に先立ち、ＲＳＡ暗号を運用する際の一般的な暗号鍵生成手順の一例について説明する。
【００３０】
まず乱数発生器を用いて、５１２ビット又は１０２４ビット等の乱数を発生させる。上述した５１２ビット又は１０２４ビット等は、現存するＣＰＵ（Central Processing Unit）のビット長を大きく上回るビット長である。以下の説明において、５１２ビット又は１０２４ビット等、ＣＰＵのビット長を上回るビット長を極長ビットと表現する。
【００３１】
このような極長ビットのデータに対して、素数判定が行なわれるが、この素数判定では、処理負荷が大きい確定的、或いは確率的素数判定を行なう前に、ふるい処理が行なわれる。具体的に、このふるい処理は、発生した乱数がいくつかの素数（例えば、３、５、７、１１等の一般的には３桁以下の素数）の倍数になっているか否かをユークリッドの互除法等を用いて検査するもので、このふるい処理により合成数と判定されなかったデータに対して、上記確定的、或いは確率的素数判定を行なうようになっている。そして、素数であることが判定されると、その素数を用いて暗号鍵が生成される。なお、確定的素数判定方法の例としては、ＡＫＳ素数判定法が挙げられ、確率的素数判定方法の例としてはフェルマーテストやミラー・ラビン素数判定法が挙げられる。
【００３２】
上述したふるい処理と、確定的、或いは確率的素数判定で行なわれる主要な演算は異なり、前者では除算が繰り返し行なわれ、後者では乗算剰余演算、べき剰余演算が行なわれるようになっている。具体的には、一般的なふるい処理で用いられるユークリッドの互除法は、ａをｂで割った余りをｒとすると、ａとｂとの最大公約数はｂとｒとの最大公約数に等しいというアルゴリズムであるので、このアルゴリズムを実行した場合には、上述した除算が繰り返し行なわれることとなる。一方、乗算剰余演算はａとｂとの積をｍで割ったときの余りを求める演算であり、べき剰余演算はａのｂ乗をｍで割ったときの余りを求める演算である。
【００３３】
いずれも極長ビットのデータに対して行なわれる演算であるが、乗算剰余演算、べき剰余演算は、情報を暗号化する場合にも行なわれる演算であることから、パソコンほどのＣＰＵを搭載することはできないが、暗号化を行なう装置（例えばＩＣカードや決済端末）には、乗算剰余演算、べき剰余演算を行なうための専用チップが搭載されている。
【００３４】
従って、ＩＣカードや決済端末において、暗号鍵を生成する場合は、上述したふるい処理をいかに効率的に行なうかが重要な課題となる。
【００３５】
以上の説明を踏まえ、以下本実施の形態について説明する。図１は本発明の素数生成装置を適用したＩＣカードのハードウェア構成を示す図であるが、これに限らず決済端末等、携帯型で暗号化を行なう装置に適用することができる。また、耐タンパモジュール（ＴＲＭ：Tamper Resistant Module）のようなチップ内部に強固で粘着力の高いコーティングを施し、表面を剥がすと内部の回路が完全に破壊されるようにした装置に適用しても良い。
【００３６】
図１に示されるように、ＩＣカード１０は、ＣＰＵ１２、ＤＳＰ（Digital Signal Processor）１４、入出力部１６、ＲＯＭ（Read Only Memory）１８、ＲＡＭ（Random Access Memory）２０、及び乱数発生器２２を含んで構成される。
【００３７】
このうち、ＣＰＵ１２は、予め定められたビット数（本実施の形態ではｍビット）以下のデータに対して、少なくとも加算、及び除算が可能となっている。さらに、ＣＰＵ１２は、剰余演算、シフト演算、及び符号変換演算の少なくとも１つ演算が可能であっても良い。なお、いうまでもなく、剰余演算とはａをｂで割った余りｒを求める演算であり、シフト演算とは２進数のビットパターンを右または左にずらす演算であり、符号変換演算とは、ａに対して−ａを求める演算である。いずれの演算も、一般的なＣＰＵであれば可能な演算である。なお、本実施の形態では、符号変換演算した後に加算されることから、符号変換演算が可能なことは、減算が可能であることを示している。
【００３８】
また、演算手段であるＣＰＵ１２は、予め定められたビット数より大きいビット数のデータに対しても、例えばそのデータを予め定められたビット数以下のデータに分割して演算させることで、処理速度は落ちるが演算自体は可能である。
【００３９】
上述したビット数を示すｍは、４、８、１６等、一般的に２のべきである。また、ＩＣカード１０や上述した決済端末に搭載されたＣＰＵは、パソコン等に搭載されるＣＰＵと比較すると、やはり演算速度は非常に遅いことが多い。
【００４０】
ＤＳＰ１４は、暗号化する際に必要な演算を行なうための専用チップであり、例えば暗号化したい情報、暗号鍵を設定することで、暗号化された情報を出力するようになっている。そして、その際に必要となる極長ビットのデータに対する乗算剰余演算、及びべき剰余演算が可能となっている。
【００４１】
入出力部１６は、ＩＣカード１０と他装置との間で無線通信を行なうためのものであり、特に本実施の形態では、ＩＣカード１０を動作させるための電源電力を供給するものでもある。具体的に入出力部１６には、アンテナコイルや、電源電力を蓄電するコンデンサなどが組み込まれており、アンテナコイル内を通り抜ける磁力線の数が変化すると起電力が誘起されるようになっている。
【００４２】
ＲＯＭ１８は、フラッシュメモリなどの不揮発性の記憶装置であり、後述するフローチャートに示される素数生成処理を行なうためのプログラムや、ＩＣカードの仕様に応じたプログラム等が記憶される。ＲＡＭ２０は、各プログラム等により、処理に応じて一時的に使用される揮発性の記憶装置である。
【００４３】
乱数発生器２２は、ＣＰＵ１２の指示で極長ビットの奇数の乱数を発生させ、発生された乱数は、ＲＡＭ２０に出力され、保持される。
【００４４】
次に、上述したＩＣカード１０において実行される素数生成処理の概要を図面を用いて説明する。図２には、ＲＡＭ２０に出力された素数候補データＮと複数の分割素数候補データＦ（ｋ）とが示されている。
【００４５】
本実施の形態に係る素数生成処理において、素数候補データＮは、上述した乱数発生器２２により生成された極長ビット（Ｌビット）のデータである。分割素数候補データＦ（ｋ）は、素数候補データＮをＣＰＵのビット長であるｍビット数以下となるデータに分割したもので、この図の場合は、素数候補データＮをｔ（ｔ＜ｍ）ビットずつ分割することで、各々のＦ（ｋ）のビット長をｔビットとしている。複数の分割素数候補データＦ（ｋ）は、同図の場合、Ｍ（＝Ｌ／ｔ）個のｔビットのデータＦ（ｋ）で構成される。
【００４６】
図３に示されるように、本実施の形態に係る素数生成処理では、複数の分割素数候補データＦ（ｋ）の各々同士をＣＰＵ１２により加算することにより、素数候補データＮが示す素数候補が合成数であるか否かを判定するための判定データＳを生成する。
【００４７】
さらにＣＰＵ１２が、剰余演算、シフト演算、及び符号変換演算の少なくとも１つの演算が可能であれば、同図に示されるように、複数の分割素数候補データＦ（ｋ）に対してシフト演算、剰余演算、及び符号変換演算の少なくとも１つの演算で得られたデータの各々同士を加算することで判定データＳを生成する。
【００４８】
生成された判定データＳを、ＣＰＵ１２により少なくとも１つの素数で除算することにより素数候補が少なくとも１つの素数の倍数ではないと判定された場合に、素数候補データＮに対して確定的、或いは確率的素数判定処理を行なう。
【００４９】
次に、図４を用いて上記判定データＳの生成方法について説明する。図４は、予め素数生成プログラムが参照する情報として、ＲＯＭ１８に記憶された情報を表す模式図であり、ふるい処理で用いられる分割候補ビット長、判定データＳ、判定データＳを除算する素数の対応を示している。
【００５０】
具体的には、例えば「分割素数候補ビット長」が１であれば、「判定データＳ」に記載された数式に従って演算し、後述するように演算結果を素数３で除算するようになっている。
【００５１】
同図に示される「分割素数候補ビット長」は上述したビット長ｔに対応している。「判定データＳ」におけるΣは、ｋ＝０〜Ｍ−１までの総和を示している。また、記号「^」はべきを、記号「＊」は乗算を、記号「％」は剰余演算を、記号「＜＜」は左シフト演算をそれぞれ示す。例えば、Ｓ＝Σ（−１）^ｋ＊Ｆ（ｋ）は、以下の式を示す。
Ｓ＝Ｆ（０）−Ｆ（１）＋Ｆ（２）−Ｆ（３）＋…（−１）^（Ｍ−１）＊Ｆ（Ｍ−１）
すなわち、分割素数候補ビット長が２で３の倍数か否かを判定する場合には、同図に示されるように、素数候補データＮを１ビットごとに区切って、ビット単位で加算、減算する。下位のほうから、０ビット目、１ビット目、３ビット目、とビット番号を振った時に偶数ビット目は加算、奇数ビット目は減算する。計算結果が３で割り切れるかどうか判定し、割り切れた場合は、素数候補データＮは３の倍数、割り切れない場合は、３の倍数ではない、と判定する。
【００５２】
また、同図に示されるように、分割素数候補ビット長ｔが２の場合は、２つの判定データＳの求め方が存在し、一方は素数候補データＮが３の倍数であるか否かを判定でき、他方は素数候補データＮが５の倍数であるか否かを判定できる。
【００５３】
さらに、分割素数候補ビット長ｔが６の場合は、判定データＳによって、素数候補データＮが３、又は７の倍数であるか否かを判定できる。すなわち、一つの判定データＳを求めることで、複数の素数の倍数であるか否かが判定できる。
【００５４】
なお、同図に示される内容の一部を詳細に説明すると、素数候補データＮが３の倍数か否かを判定するには素数候補データＮを２ビットごとに区切って、各Ｆ（ｋ）を０から３の間の数と考えて加算する。素数候補データＮが１０２４ビット程度であれば、計算結果は３２ビット以内に収まるので、判定データＳが３で割り切れるか否か判定し、割り切れた場合は、素数候補は３の倍数、割り切れない場合は、３の倍数ではない、と判定する。
【００５５】
また、素数候補データＮが５の倍数か否かを判定するには素数候補データＮを２ビットごとに区切って、各Ｆ（ｋ）を０から３の間の数と考えて、加算、減算する。下位のＦ（ｋ）から、０番目、１番目、３番目、と番号を振った時に、偶数番号のＦ（ｋ）値は加算、奇数番号のＦ（ｋ）値は減算する。計算結果が５で割り切れるか否か判定し、割り切れた場合は、素数候補データＮは５の倍数、割り切れない場合は、５の倍数ではない、と判定する。
【００５６】
また、素数候補データＮが７の倍数か否かを判定するには、素数候補データＮを４ビットごとに区切って、各Ｆ（ｋ）を０から１５の間の数と考えて、シフト及び加算をする。下位のＦ（ｋ）から、０番目、１番目、２番目、と番号を振った時に、３の倍数番号のＦ（ｋ）値はそのまま加算、(３の倍数＋１)番号のＦ（ｋ）値は１ビット左シフトしてから加算、(３の倍数＋２)番号のＦ（ｋ）値は２ビット左シフトしてから加算する。判定データＳが７で割り切れるか否か判定し、割り切れた場合は、素数候補データＮは７の倍数、割り切れない場合は、７の倍数ではない、と判定する。
【００５７】
以上は、ひとつの素数の倍数か否かを判定する方法であったが、複数の素数の倍数か否かを判定する、同図に示される内容の一部を詳細に説明する。
【００５８】
素数候補データＮが３か５の倍数か否かを判定するには、素数候補データＮを４ビットごとに区切って、各Ｆ（ｋ）を０から１５の間の数と考えて合計する。判定データＳが３、又は５で割り切れるか否かで、素数候補データＮがそれぞれ３、又は５の倍数か否かを判定する。
【００５９】
素数候補データＮが３、５、７、１３、１７、又は２４１の倍数か否かを判定するには、素数候補データＮを２４ビットごとに区切って、各Ｆ（ｋ）を０から２の２４乗−１の間の数と考えて合計する。計算結果が３、５、７、１３、１７、２４１で割り切れるか否かで、素数候補データＮが３、５、７、１３、１７、又は２４１の倍数か否かを判定する。
【００６０】
この他にも、極長ビットのデータの除算やユークリッドの互除法による演算を回避しつつ、素数候補データＮがある小さな素数を約数としてもつか否かを判定する方法はいくつもあり、これらを適当に組み合わせることにより、素数候補データＮが複数の素数を約数としてもつか否かの判定を行うことができる。
【００６１】
また、素数候補データＮのビット長Ｌが分割したいｔの倍数ではない場合、すなわち、Ｌ＝ｑｔ＋ｒ（ｒ≠０）の場合、ｔの倍数となるように、素数候補データＮの上位に（ｔ−ｒ）ビット分の０を付け足すことにより、素数候補データＮのビット長ＬをＬ＋ｔ−ｒとすることで、素数候補データＮのビット長をｔの倍数とすることができる。
【００６２】
なお、同図に示される模式図において、分割素数候補ビット長が、例えば５、７、９などについては記載されていないが、以下の方法を用いることで任意の分割素数候補ビット長ｔを選ぶことができる。
【００６３】
ｍビット以下の任意の分割素数候補ビット長ｔに対し、まず２＾ｔ−1の素因数ｐを求めておき、次にＳ＝ΣＦ(ｋ)を求め（Ｆ（ｋ）はｔビット）、ｐ｜Ｓならばｐ｜Ｎとなる（Ｎ＝素数候補データ）ので、任意の分割素数候補ビット長を選ぶことができる。なお、ａ｜ｂは、ａがｂの約数であることを示している。
【００６４】
他の方法としては、ｍビット以下の任意の分割素数候補ビット長ｔに対し、まず２＾ｔ＋1の素因数ｐを求めておき、次にＳ＝Σ（−１）^ｋ＊Ｆ(ｋ)を求め（Ｆ（ｋ）はｔビット）、ｐ｜Ｓならばｐ｜Ｎとなる（Ｎ＝素数候補データ）ので、この方法によっても任意の分割素数候補ビット長を選ぶことができる。
【００６５】
上述した２つの方法以外にも方法があるが、ここでは省略する。例えば、ｔ＝５の場合、２＾ｔ−1＝３１で、これは素数であるので、素数候補データＮが３１の倍数かどうかを判定できる。この場合、ひとつの素数３１しか判定できないが、判定を効率化するには、なるべく異なる多くの素因数からなる値を見つけることが重要である。例えば、ｔ=１０の場合、２＾ｔ−1＝１０２３＝３＊１１＊３１で、３つの素数の倍数か否か判定することができる。
【００６６】
また、ｍビット以下の分割素数候補データＦ（ｋ）を用いて、素数候補データＮがある素数の倍数か否かを判定可能な素数は、図４に示される素数に限るものではない。さらに、図４に示される判定データＳのいずれを用いて判定するかを、ＩＣカード１０の仕様等に応じて定めるようにすると、より効率的な判定が可能である。
【００６７】
以上説明したふるい処理を用いた素数生成処理を、フローチャートを用いて説明する。図５は、素数生成プログラムの流れを示すフローチャートであり、ＣＰＵ１２により実行される。
【００６８】
まず、ステップ１０１で、乱数発生器２２により予め定められたビット数（本実施の形態ではｍビット）よりも大きなビット数の素数候補を示す素数候補データＮを生成させる。次のステップ１０２で上述したふるい処理を行なう。このふるい処理の詳細は、図６で説明する。
【００６９】
次のステップ１０３で、素数候補データＮは合成数であるか否かを判定する。ここでの合成数とは、ふるい処理で除算された素数を約数にもつ合成数を意味し、それ以外の合成数を含むものではない。
【００７０】
ステップ１０３で肯定判定した場合には、ステップ１０１の処理に戻る。一方、ステップ１０３で素数候補データＮが上述した意味での合成数ではないと判定した場合には、ステップ１０４で、確定的、或いは確率的素数判定処理を行なう。すなわち、素数候補が少なくとも１つの素数を約数にもつ合成数ではないと判定された場合に、素数候補データＮに対して素数判定を行なう。
【００７１】
次のステップ１０５で、素数候補データＮが素数判定処理によって素数と判定されたか否かを判定する。ステップ１０５で否定判定した場合には、ステップ１０１の処理に戻る。一方、ステップ１０５で素数候補データＮが素数と判定した場合に、ステップ１０６で、素数候補データＮを素数として例えばＲＯＭ１８に出力して処理を終了する。
【００７２】
なお、確率的素数判定の場合は、「合成数である」又は「どちらとも言えない」という結果しか得られないため、ステップ１０６では擬素数として出力されることとなるが、確率的素数判定法は精度を上げることが可能であり、例えば確率的素数判定法の一つであるミラー・ラビン素数判定法では、ある範囲全てで検査することで確定的素数判定法とすることができる。
【００７３】
次に、上記ステップ１０２のふるい処理を、図６のフローチャートを用いて説明する。まず、ステップ２０１で、分割素数候補データＦ（０）、…、Ｆ（Ｍ−１）を生成する（図２参照）。次のステップ２０２でループカウンタｋ、及び判定データＳを０で初期化する。
【００７４】
次のステップ２０３で、変数ＢにＦ（ｋ）に対して剰余演算、シフト演算、符号変換演算したデータを代入する。剰余演算（％）、シフト演算（＜＜）、符号変換演算（−）は、図４に示す模式図に従って行なわれるが、模式図に示される判定データＳのうちのいずれの判定データＳにより判定を行なうかは、予め定めておく。その場合、模式図のうちの一つの判定データＳで判定しても良いし、複数の判定データＳで判定しても良い。
【００７５】
次のステップ２０４で、判定データＳに変数Ｂを加えたものを改めて判定データＳとし、ステップ２０５でループカウンタｋを１だけ増分する。
【００７６】
次のステップ２０６で、ループカウンタｋがＭ−１より大きいか否か判定する。これは全てのＦ（ｋ）に対する処理が終了したか否かの判定である。ステップ２０６で否定判定した場合には、ステップ２０３の処理に戻り、肯定判定した場合には、ステップ２０７で判定データＳに対して素数で除算する。ここでの素数は、図４に示される素数である。従って、このステップ２０７の処理は、複数の素数に対して判定可能な場合は、複数の素数による除算が行なわれる。
【００７７】
ステップ２０８で割り切れたか否か、すなわち、少なくとも１つの素数を約数にもつ合成数であるか否かを判定し、肯定判定した場合には、ステップ２０９で、素数候補データＮは除算された素数を約数にもつ合成数と判定し、否定判定した場合には、素数候補データＮは除算した素数を約数にもたないと判定して処理を終了する。
【００７８】
以上説明したように、本実施の形態では、ふるい処理をＣＰＵ１２のビット数以下のデータにより行なうため、効率よくふるい処理を行なうことができる。これにより、例えばＩＣカードや決済端末のようなＣＰＵの処理能力が比較的低い装置においても、自装置内で暗号鍵を生成することが可能となる。
【００７９】
この場合、従来のように暗号鍵が何らかの形で外部を経由することを排除できる結果、暗号鍵の漏洩を防止することもできる。
【００８０】
また、判定データＳを求めるためのＦ（ｋ）は、全てＣＰＵ１２のビット数以下のデータであるため、極長ビットそのものを演算するよりも遙かに効率よく演算することが可能である。また、判定データＳを求める際に用いられる演算（加算、乗算、シフト演算等）はＣＰＵ１２が可能な基本的な演算であるため、処理負荷を低減することができる。これにより、使用する電力を低減できるため、携帯型の装置には非常に相性がよいふるい処理であるといえる。
【００８１】
なお、本実施の形態ではＩＣカード１０を適用例として示したが、ＲＳＡ暗号において対象となる極長ビット長は、パソコンのＣＰＵのビット数よりも遙かに大きいため、パソコンに対しても適用できることは言うまでもない。
【００８２】
また、図５、図６で説明したフローチャートの処理の流れは一例であり、本発明の主旨を逸脱しない範囲内で処理順序を入れ替えたり、新たなステップを追加したり、不要なステップを削除したりすることができることは言うまでもない。
【符号の説明】
【００８３】
１０ ＩＣカード
１２ ＣＰＵ
１４ ＤＳＰ
１６ 入出力部
１８ ＲＯＭ
２０ ＲＡＭ
２２ 乱数発生器
【特許請求の範囲】
【請求項１】
予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段と、
前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成手段と、
前記素数候補データ生成手段により生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成手段と、
前記分割素数候補データ生成手段により生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成手段と、
前記判定データ生成手段により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定手段と、
前記素数判定手段により、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力手段と、
を有する素数生成装置。
【請求項２】
前記演算手段は、剰余演算、シフト演算、及び符号変換演算の少なくとも１つの演算が可能であり、
前記判定データ生成手段は、前記分割素数候補データに対して前記演算手段によりシフト演算、剰余演算、及び符号変換演算の少なくとも１つの演算で得られたデータの各々同士を前記演算手段により加算することで判定データを生成する請求項１に記載の素数生成装置。
【請求項３】
予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段を有する素数生成装置における素数生成方法であって、
前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成段階と、
前記素数候補データ生成段階により生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成段階と、
前記分割素数候補データ生成段階により生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成段階と、
前記判定データ生成段階により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定段階と、
前記素数判定段階により、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力段階と、
を有する素数生成方法。
【請求項４】
予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段を有する素数生成装置において実行される素数生成プログラムであって、
前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成ステップと、
前記素数候補データ生成ステップにより生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成ステップと、
前記分割素数候補データ生成ステップにより生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成ステップと、
前記判定データ生成ステップにより生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数を約数にもつ合成数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定ステップと、
前記素数判定ステップにより、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力ステップと、
を有する素数生成プログラム。
【請求項１】
予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段と、
前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成手段と、
前記素数候補データ生成手段により生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成手段と、
前記分割素数候補データ生成手段により生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成手段と、
前記判定データ生成手段により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定手段と、
前記素数判定手段により、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力手段と、
を有する素数生成装置。
【請求項２】
前記演算手段は、剰余演算、シフト演算、及び符号変換演算の少なくとも１つの演算が可能であり、
前記判定データ生成手段は、前記分割素数候補データに対して前記演算手段によりシフト演算、剰余演算、及び符号変換演算の少なくとも１つの演算で得られたデータの各々同士を前記演算手段により加算することで判定データを生成する請求項１に記載の素数生成装置。
【請求項３】
予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段を有する素数生成装置における素数生成方法であって、
前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成段階と、
前記素数候補データ生成段階により生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成段階と、
前記分割素数候補データ生成段階により生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成段階と、
前記判定データ生成段階により生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数の倍数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定段階と、
前記素数判定段階により、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力段階と、
を有する素数生成方法。
【請求項４】
予め定められたビット数以下のデータに対して、少なくとも加算、及び除算が可能な演算手段を有する素数生成装置において実行される素数生成プログラムであって、
前記予め定められたビット数よりも大きなビット数の素数候補を示す素数候補データを生成する素数候補データ生成ステップと、
前記素数候補データ生成ステップにより生成された素数候補データを前記予め定められたビット数以下となるデータに分割することで複数の分割素数候補データを生成する分割素数候補データ生成ステップと、
前記分割素数候補データ生成ステップにより生成された複数の分割素数候補データの各々同士を前記演算手段により加算することにより、素数候補データが示す素数候補が合成数であるか否かを判定するための判定データを生成する判定データ生成ステップと、
前記判定データ生成ステップにより生成された判定データを、前記演算手段により少なくとも１つの素数で除算することにより前記素数候補が前記少なくとも１つの素数を約数にもつ合成数ではないと判定された場合に、前記素数候補データに対して素数判定を行なう素数判定ステップと、
前記素数判定ステップにより、前記素数候補が素数と判定された場合に、前記素数候補データを素数として出力する出力ステップと、
を有する素数生成プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−１２３３５６（Ｐ２０１１−１２３３５６Ａ）
【公開日】平成２３年６月２３日（２０１１．６．２３）
【国際特許分類】
【出願番号】特願２００９−２８１７１６（Ｐ２００９−２８１７１６）
【出願日】平成２１年１２月１１日（２００９．１２．１１）
【出願人】（３０８０３３７１１）ＯＫＩセミコンダクタ株式会社 (898)
【Ｆターム（参考）】
【公開日】平成２３年６月２３日（２０１１．６．２３）
【国際特許分類】
【出願日】平成２１年１２月１１日（２００９．１２．１１）
【出願人】（３０８０３３７１１）ＯＫＩセミコンダクタ株式会社 (898)
【Ｆターム（参考）】
[ Back to top ]