半導体装置及びＩＣカード
【課題】暗号に対するサイドチャネル攻撃から防御するために、素数性判定を行う半導体装置において、素数の漏えいを防止する。
【解決手段】素数性判定におけるべき剰余演算において、従来の指数のランダム化に加え、法をもランダム化する。乱数発生部により発生した乱数をランダム化数として、法生成部と指数生成部に入力する。法生成部と指数生成部は、ランダム化数を用いて素数候補Pをランダム化し、ランダム化された法R1と指数R2を生成する。ランダム化された法R1と指数R2を用いて素数性判定のためのべき剰余演算を実行し、その結果に基づいて、素数性候補Pの素数性を判定する。半導体装置の素数性判定中の消費電力が、判定対象の素数候補の値と無相関となり、サイドチャネル攻撃による素数の漏えいを防止することができる。
【解決手段】素数性判定におけるべき剰余演算において、従来の指数のランダム化に加え、法をもランダム化する。乱数発生部により発生した乱数をランダム化数として、法生成部と指数生成部に入力する。法生成部と指数生成部は、ランダム化数を用いて素数候補Pをランダム化し、ランダム化された法R1と指数R2を生成する。ランダム化された法R1と指数R2を用いて素数性判定のためのべき剰余演算を実行し、その結果に基づいて、素数性候補Pの素数性を判定する。半導体装置の素数性判定中の消費電力が、判定対象の素数候補の値と無相関となり、サイドチャネル攻撃による素数の漏えいを防止することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、素数性判定を行う半導体装置に関し、特に暗号へのサイドチャネル攻撃などからの防御に有効な技術に関する。
【背景技術】
【０００２】
暗号に用いる暗号鍵は素数に基づいて生成されることが多い。例えば、RSA暗号公開鍵と秘密鍵を生成する際、２つの大きい素数を生成する必要がある。もしこの２つの素数が漏れると、公開鍵から秘密鍵を計算することは簡単なことなので、２つの素数は秘密にしておく必要がある。
【０００３】
素数生成は通常以下の方法で実施される。乱数が生成され、フェルマテスト、ミラー・ラビンテスト、ソロベイ・ストラッセンテストなどの素数性判定により乱数の素数性の検査が行われる（非特許文献１）。一般的に、これらの素数性判定はべき剰余を含む。例えば、フェルマテストにより整数Pの素数性判定を行う場合、整数の乱数Aが選択され、べき剰余AP-1 mod Pが計算される。
【０００４】
オイラーの定理によると、Nが正の整数でAをNと互いに素な正の整数としたとき、
〔数１〕 Aφ(N) mod N = 1
が成立する。ここではφはオイラー関数である。Pが素数である場合、φ(P)=P-1であり、べき剰余A(P-1) mod Pの結果は１であることが保証されている。
【０００５】
素数は比較的稀なものであるので、素数が見つかるまでに多くの候補の判定が行われることが多い。効率的な理由から、素数性判定が不合格の場合、その素数候補をインクリメントすることが望ましい。
【０００６】
RSA暗号鍵生成時の素数は暗号システムのセキュリティにとって重要なものであるため、例えば、素数性判定のべき剰余中に、素数の生成により生じる消費電力を計測し、消費電力のパターンを利用して素数の値の漏えいを行うサイドチャンネル解析などの潜在的な攻撃のターゲットとなる。インクリメンタルな素数生成では、互いに近い整数（P, P+2, P+4など）を対象としたべき剰余が実行されるために、これらの攻撃の危険は増幅される。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１０−２７７０８５号公報
【非特許文献】
【０００８】
【非特許文献１】Ａｌｆｒｅｄ Ｊ． Ｍｅｎｅｚｅｓ， Ｐａｕｌ Ｃ． ｖａｎ Ｏｏｒｓｃｈｏｔ ａｎｄ Ｓｃｏｔｔ Ａ． Ｖａｎｓｔｏｎｅ， “Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”， ＣＲＣ Ｐｒｅｓｓ， Ｃｈａｐｔｅｒ ４ − Ｐｕｂｌｉｃ Ｋｅｙ Ｐａｒａｍｅｔｅｒｓ．， Ｏｃｔｏｂｅｒ １９９６
【非特許文献２】ゲブハルト・ヴェックル（Ｇｅｂｈａｒｄ Ｂｏｃｋｌｅ）、「指数をランダム化したミラー・ラビンテスト」（Ｔｈｅ Ｍｉｌｌｅｒ−Ｒａｂｉｎ ｔｅｓｔ ｗｉｔｈ ｒａｎｄｏｍｉｚｅｄ ｅｘｐｏｎｅｎｔｓ）， ［ｏｎｌｉｎｅ］， ２００６年３月２３日、ハイデルベルグ大学ヴェックル教授ホームページ、［２０１１年１１月２５日検索］、インターネット＜ＵＲＬ： ｈｔｔｐ：／／ｗｗｗ．ｉｗｒ．ｕｎｉ−ｈｅｉｄｅｌｂｅｒｇ．ｄｅ／ｇｒｏｕｐｓ／ａｒｉｔｈ−ｇｅｏｍ／ｂｏｅｃｋｌｅ＿ｏｌｄ＿ｄｅｓｉｇｎ／ｐｒｅｐｒｉｎｔｓ．ｈｔｍｌ＞
【発明の概要】
【発明が解決しようとする課題】
【０００９】
特許文献１において開示されている発明は、フォールトアタックによる素数生成の出力の撹乱を検出するため予備証拠整数を利用する。しかしながら、本特許文献では素数性判定の漏えい問題については取り扱っていない。
【００１０】
非特許文献２には、指数のランダム化が行われるミラー・ラビン素数性判定法の変形が開示されている。べき剰余の指数がランダム化されているので、べき剰余の際の消費電力が攪乱されて素数の漏えいの危険性は低くなるが、法がランダム化されていないため、漏えいを完全に防ぐことはできない。
【００１１】
法をランダム化することは、べき乗の結果、即ち素数性判定の結果に影響を与えるので簡単なことではない。このことは、下式のフェルマテストについて考えてみると容易に理解できる。
〔数２〕AP-1= 1 mod P
ここで、「AP-1= 1 mod P」は、べき剰余AP-1 mod Pの結果が1であることを示す式で、当業者において汎用されている表現形式である。
【００１２】
指数P-1に任意の乱数rを乗じてランダム化した場合、ランダム化された指数でのべき乗の結果は変化せず、
〔数３〕 Ar(P-1)= 1 mod P
である。一方、任意の乱数sを使ってランダム化された法sPの場合、一般に、
〔数４〕 AP-1≠1 mod sP
〔数５〕 Ar(P-1)≠1 mod sP
である。素数候補Pが素数であっても、乱数sとの積sPは素数でないため、フェルマテストによりPの素数性を判定することができない。
【００１３】
本発明の目的は、素数性判定を行う半導体装置において、べき剰余の法をランダム化し、素数の漏えいを防止することである。
【００１４】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１５】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【００１６】
すなわち、べき剰余演算を含む素数性判定を行う半導体装置において、素数候補と乱数の積を前記べき剰余演算の法とする。
【発明の効果】
【００１７】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【００１８】
すなわち、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【図面の簡単な説明】
【００１９】
【図１】図１は、本発明の一実施形態に係る、素数候補の素数性判定を行う半導体装置のブロック図である。
【図２】図２は、本発明の別の実施形態に係る、素数候補の素数性判定を行う半導体装置のブロック図である。
【図３】図３は、本発明の一実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。
【図４】図４は、図３に例示したシステムでRSAトランザクションを行った場合の、ICカード、端末、鍵サーバー間の一般的な相互関係である。
【図５】図５は、本発明に係る素数性判定を行う半導体装置を使って、RSA暗号鍵を生成するソフトウェアの実装例を説明するフローチャートである。
【図６】図６は、図１または図２に示した素数候補の素数性判定を行う半導体装置の動作例を表すフローチャートである。
【図７】図７は、本発明の一実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。
【図８】図８は、小さい素数の篩を使用したRSA暗号鍵生成のフローチャートである。
【図９】図９は、図２に示した素数候補の素数性判定を行う半導体装置の動作例を表すフローチャートである。
【図１０】図１０は、実施形態４に係るランダム化されたミラー・ラビンテストのフローチャートのうち、前半の小さい素数生成ステップである。
【図１１】図１１は、実施形態４に係るランダム化されたミラー・ラビンテストのフローチャートのうち後半のミラー・ラビンテストのステップである。
【図１２】図１２は、小さい素数のテーブルを利用したランダム化数の生成過程の数値例である。
【発明を実施するための形態】
【００２０】
１．実施の形態の概要
先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【００２１】
〔１〕＜べき剰余における法をランダム化（上位概念）＞
乱数発生部（１）と法生成部（２）と指数生成部（３）とべき剰余演算部（４）と判定部（５）とを含んで構成され、入力された素数候補（P）の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００２２】
前記乱数発生部は、第１の乱数を発生してランダム化数（r）として生成し、前記法生成部は前記素数候補と前記ランダム化数とに基づいて第１整数（R1）を生成し、前記指数生成部は第２整数（R2）を生成する。
【００２３】
前記べき剰余演算部は、前記第１整数を法とし前記第２整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する。
【００２４】
これにより、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００２５】
〔２〕＜指数と法をランダム化したフェルマテスト（実施形態１）＞
乱数発生部（１）と法生成部（２）と指数生成部（３）とべき剰余演算部（４）と判定部（５）とを含んで構成され、入力された素数候補（P）の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００２６】
前記乱数発生部は、第１の乱数を発生してランダム化数（r）として生成し、前記法生成部は前記素数候補と前記ランダム化数の積（rP）を第１整数（R1）として生成し、前記指数生成部は前記素数候補から１を減じた数と前記ランダム化数から１を減じた数との積（(r-1)(P-1)）を第２整数（R2）として生成する。
【００２７】
前記べき剰余演算部は、前記第１整数を法とし前記第２整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する。
【００２８】
これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００２９】
〔３〕＜小さい素数によるランダム化＞
項２の半導体装置であって、ランダム化数生成部（６）をさらに備え、前記乱数発生部は、第１の乱数を発生して前記ランダム化数生成部に入力し、前記ランダム化数生成部は、前記第１の乱数が素数のとき、前記第１の乱数を前記ランダム化数として生成する。
【００３０】
これにより、素数性判定における偽陰性と偽陽性の過誤が発生する確率を下げることができ、判定の効率を向上することができる。偽陰性の過誤とは、素数候補が素数であるにも関わらず素数ではないと判定する過誤を指し、偽陽性の過誤とは、素数候補が素数ではないにも関わらず素数と判定する過誤を指す。過誤の発生確率を下げる原理については、実施形態２において詳述する。
【００３１】
〔４〕＜小さい素数（所定値L以下の素数）の算出方法＞
項２の半導体装置であって、ランダム化数生成部（６）をさらに備え、前記乱数発生部は、第２の乱数を発生して前記ランダム化数生成部に入力し、前記ランダム化数生成部は、前記ランダム化数を以下の方法で算出する。
【００３２】
前記乱数発生部（１）により、所定値L以下の第２の乱数を発生し（４０１）、
前記ランダム化数生成部（６）は、前記第２の乱数が下記条件１乃至３のすべてを満たすとき、前記第２の乱数を前記ランダム化数として生成する。
【００３３】
条件１： 前記第２の乱数が所定値Aより小さい素数を因数に持たないこと（４１１〜４１５）。
【００３４】
条件２： 前記所定値Aを底とし、前記第２の乱数から1を減じた数を指数とし、前記第２の乱数を法としたべき剰余演算の結果が1であること（４２１，４２２）。
【００３５】
条件３： 前記第２の乱数と、前記所定値L以下の整数であって、前記所定値Aを底とし前記整数から1を減じた数を指数とし前記整数を法としたべき剰余演算の結果が1であるが素数ではない整数のすべてと前記第２の乱数と比較して、前記第２の乱数がそのいずれとも異なるものであること（４３１〜４３６）。
【００３６】
これにより、ランダム化数に適する素数を簡易な方法で算出することができ、ICカードなどのローエンドデバイスにも実装することができる。
【００３７】
〔５〕＜素数候補の篩分け＞
項２、３、または４の半導体装置であって、前記素数候補（P）が少なくとも１個の素数で割り切れるか否かの判定を行う。
【００３８】
前記判定結果が割り切れる場合には次の素数候補を生成する。
【００３９】
前記判定結果が割り切れない場合には、前記歩数候補を、前記法生成部（２）と前記指数生成部（３）に入力する。
【００４０】
これにより、素数候補（P）が素数でないことが簡単にわかる場合には、べき剰余演算に至る前にフェイルの判定（素数候補（P）が素数ではない旨の判定）を出力して次の素数候補に進むことができるので、一連の素数性判定において、演算負荷の大きいべき剰余演算の実行回数を減らすことができる。
【００４１】
〔６〕＜素因数分解の指数を乱数として乱数を生成するフェルマテスト（実施形態２）＞
乱数発生部（１）とランダム化数生成部（６）と法生成部（２）と指数生成部（３）とべき剰余演算部（４）と判定部（５）を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００４２】
前記乱数発生部は、１個以上の第４の乱数列（j1, j2, j3, ・・・）を発生し（７２２）、前記ランダム化数生成部は、前記第４の乱数列に基づいて算出される整数（t[j]）を指数とする素因数演算によりランダム化数を生成する（７２４、７２５）。
【００４３】
前記法生成部は、前記素数候補と前記ランダム化数との積である第１整数（R1）を生成し（７４１）、前記指数生成部は、第２整数（R2）を生成する（７４２）。
【００４４】
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し（７４５）、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する（７５０）。
【００４５】
これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止され、また、ランダム化するためのランダム化数は、素数に限定されない。
【００４６】
〔７〕＜素数テーブルの利用； ランダム化数 = Πr(j)t[j] 1≦j≦k ＞
項６の半導体装置であって、各構成要素は以下の動作を行う。
【００４７】
前記乱数発生部（１）は、値が1以上k以下の乱数（j）を指数指定乱数として出力する（７２２）。
【００４８】
前記ランダム化数生成部（６）は、k個の互いに相違する素数を格納するk個の要素からなる第１の配列（r[k]）と前記素数のそれぞれに対応する指数を格納するk個の要素からなる第２の配列（t[k]）とを備え、前記指数指定乱数によって指定された回数を前記第２の配列の要素の値とする（７２６）。
【００４９】
前記第１の配列の各要素の値である素数に、前記第２の配列の対応する要素の値を指数とするべき乗演算によりk個の整数を算出し、前記k個の整数の積を算出して前記ランダム化数として出力する。
【００５０】
これにより、ランダム化数の別の生成方法を提供する。
【００５１】
〔８〕＜底はランダム化数×素数候補と互いに素＞
項６の半導体装置であって、べき剰余演算の底を、前記ランダム化数と前記素数候補の積と互いに素の整数とする（７４４）。
【００５２】
これにより、偽陰性の過誤が発生する確率を下げ、素数性判定の効率を向上することができる。
【００５３】
〔９〕＜ミラー・ラビン素数判定法における法のランダム化＞
乱数発生部（１）と法生成部（２）と指数生成部（３）とべき剰余演算部（４）と判定部（５）を含んで構成され、入力される素数候補（P）の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００５４】
前記乱数発生部は、第５の乱数をランダム化数（r）として生成する。
【００５５】
前記法生成部は、前記素数候補と前記ランダム化数との積を第１整数として生成する（８２１）。
【００５６】
前記指数生成部は、前記ランダム化数から１を減じた数と前記第１の素数候補から１を減じた数との積を素因数分解して、式(r-1)(P-1) = 2sP'を満たす最大の整数s及び整数P'を算出し、前記整数P'を第２整数として生成する（８２４、８２５）。
【００５７】
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し（８４１）、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する（８４２）。
【００５８】
これにより、ミラー・ラビンテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００５９】
〔１０〕＜底を変えながらべき剰余を繰り返すループ＞
項９の半導体装置であって、各構成要素は以下の動作を行う。
【００６０】
前記乱数発生部により第６の乱数を発生し（８３４）、前記第６の乱数（A）が、前記ランダム化数（r）で割り切れない数となるように選ぶ（８３５）。
【００６１】
前記べき剰余演算部は、前記第６の乱数を底とし前記第１整数を法とし前記第２整数を指数とするべき剰余演算を実行する。
【００６２】
前記判定部は、前記べき剰余演算（８４１）の結果が、1またはrP-1
または1+P(P-1 mod r) (r-2) mod rP
またはP-1+P(P-1 mod r) (2-P) mod rP
のいずれか１つと一致する場合（８４２）、前記素数候補が素数であるという暫定判断を行う。
【００６３】
前記素数候補が素数であるという暫定判断が維持される限り、前記乱数発生部により第５の乱数を発生して新たなランダム化数rとし、第６の乱数を発生して新たな底Aとし、繰り返し回数が所定回数に達するまで（８０２）繰り返すことにより素数性を判定する。
【００６４】
これにより、ミラー・ラビンテストにおけるべき剰余演算の法と指数がともにランダム化される。
【００６５】
〔１１〕＜小さい素数を生成する前処理＞
項９または１０の半導体装置であって、ランダム化数生成部（６）をさらに備え、前記ランダム化数生成部は、以下の条件を満たすときに、前記第５の乱数を前記ランダム化数として生成する。
【００６６】
条件１： 前記第５の乱数は、32ビットで且つ最下位2ビットがともに1であること（８１１）。
【００６７】
条件２： 前記第５の乱数（r）は、底を2とするミラー・ラビンテスト（８１２）と底を7とするミラー・ラビンテスト（８１４）と底を61とするミラー・ラビンテスト（８１６）とのすべてをパスする（８１０）こと。
【００６８】
これにより、ミラー・ラビンテストにおけるべき剰余演算の法と指数がともにランダム化され、そのランダム化数として素数が与えられる。
【００６９】
〔１２〕＜べき剰余における法をランダム化。アルゴリズムの核心（最上位概念）＞
べき剰余演算を含む素数性判定を行う半導体装置において、素数候補（P）と乱数（r）の積（rP）を前記べき剰余演算の法とする半導体装置である。
【００７０】
これにより、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００７１】
〔１３〕＜べき剰余における法および指数をランダム化＞
項１２の半導体装置において、前記素数候補と前記乱数に基づいて算出した値を前記べき剰余演算の指数とする。
【００７２】
これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００７３】
〔１４〕＜RSA暗号鍵の生成＞
項１乃至１３のいずれかの半導体装置であって、前記素数性判定を伴って２個の素数（P, Q）を生成し、
前記２個の素数に基づいて公開鍵および秘密鍵を出力するRSA暗号鍵生成を行う（３９１、３９２、６９１、６９２）。
【００７４】
これにより、RSA暗号鍵（公開鍵および秘密鍵）が、サイドチャネル解析などの攻撃から防御される。
【００７５】
〔１５〕＜ICカードのハードウェア＞
項１乃至１３のいずれかの半導体装置を含むICカード（１００）であって、CPU（１０１）とコプロセッサ（１０２）と乱数発生回路（１０３）とメモリ（１０５、１０６）とを備える。
【００７６】
前記コプロセッサは前記べき剰余演算を実行し、前記乱数発生回路は、前記乱数発生部（１）を構成し、もしくはこれに基礎となる乱数を供給する。
【００７７】
これにより、RSA暗号鍵（公開鍵および秘密鍵）が、サイドチャネル解析などの攻撃から防御されたICカードを提供することができる。
【００７８】
〔１６〕＜ICカードのメモリ＞
項１５のICカードであって、前記メモリ（１０６）に、RSA鍵生成プログラム（１２４、５２４）およびまたは素数テーブル（５３４）が格納されている。
【００７９】
これにより、RSA暗号鍵（公開鍵および秘密鍵）が、サイドチャネル解析などの攻撃から防御されたICカードを提供することができる。
【００８０】
〔１７〕＜ICカードにおける鍵エンロール＞
項１乃至１３のうちいずれかの半導体装置を含むICカードであって、トランザクションに先立って、前記素数性判定を伴って秘密鍵と公開鍵を生成し（２０１）、前記公開鍵を、ICカード端末を介して接続されている鍵サーバーに送信する（２０２）。
【００８１】
これにより、サイドチャネル解析などの攻撃から防御されたICカードを提供することができ、それを使ったトランザクションを提供することができる。
【００８２】
２．実施の形態の詳細
実施の形態について更に詳述する。
【００８３】
〔実施形態１〕＜べき剰余における法をランダム化＞
図１は、本発明の一実施形態に係る半導体装置のブロック図である。
【００８４】
乱数発生部１と法生成部２と指数生成部３とべき剰余演算部４と判定部５を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００８５】
乱数発生部１は、第１の乱数を発生してランダム化数rとして生成し法生成部２と指数生成部３に入力する。法生成部２は素数候補Pとランダム化数rとに基づいて第１整数R1を生成し、指数生成部３は第２整数R2を生成する。
【００８６】
べき剰余演算部４は、第１整数R1を法とし、第２整数R2を指数とするべき剰余演算を実行し、判定部５は、べき剰余演算部４の出力に基づいて素数候補Pの素数性を判定する。
【００８７】
これにより、べき剰余演算における法R1は、ランダム化数rに基づいて算出されランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補Pの値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００８８】
ここで、第１整数R1は、代表的には素数候補Pとランダム化数rの積rPである。第２整数R2は、べき剰余演算における法をランダム化するのに伴って、素数候補Pが素数のときに当該べき剰余演算の結果が１または他の特定値となるように、算出される。素数を法としたときにはべき剰余演算の結果は１であることが数学的に保証されているのに対し、ただ単にべき剰余の法をランダム化した場合には、ランダム化された法の値が素数である場合にべき剰余の演算結果が１になるにとどまり、素数候補Pが素数のときのべき剰余の演算結果が予測できない。本発明においては、法をランダム化しそれに適する指数を与えることによって、べき剰余の演算結果が素数候補Pに基づいて予測可能な特定値となるようにするものである。
【００８９】
〔実施形態２〕＜指数と法をランダム化したフェルマテスト＞
図１は、本発明の一実施形態に係る半導体装置のブロック図であり、図６は、その動作例を表すフローチャートである。図６は、ステップ４００の小さい素数を生成するランダム化向け整数生成とステップ４４０のフェルマテストの２つの部分を含む。まず、フェルマテスト（ステップ４４０）について説明する。
【００９０】
乱数発生部１と法生成部２と指数生成部３とべき剰余演算部４と判定部５を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００９１】
乱数発生部１は、第１の乱数を発生してランダム化数rとして生成し、法生成部２は素数候補Pとランダム化数rの積rPを第１整数R1として生成し（ステップ４４１）、指数生成部３は素数候補Pから1を減じた数とランダム化数rから1を減じた数との積(r-1)(P-1)を第２整数R2として生成する（ステップ４４２）。
【００９２】
べき剰余演算部４は、第１整数R1を法とし、第２整数R2を指数とし、1より大きくrPより小さい乱数Aを底として（ステップ４４３）、下式の剰余演算を実行する（ステップ４４５）。
〔数６〕 A(r-1)(P-1) mod rP
判定部５は、素数候補の素数性を判定する。より具体的には、べき剰余演算部の演算結果が、1のときは「パス」を出力し、1以外のときは「フェイル」を出力する（ステップ４５０）。
【００９３】
これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００９４】
ここで、底Aは1より大きくrPより小さい乱数から任意に選ぶことができるが、底Aをランダム化数rの倍数以外の整数とすることにより（ステップ４４４）、判定が偽陰性の過誤となる確率をより下げることができる。その理由は後述する。
【００９５】
ここまで述べてきた、指数と法をランダム化したフェルマテストの原理を説明する。
【００９６】
ランダム化数rが素数でありPも素数であると仮定した場合、
〔数７〕 φ(rP) = (r-1)(P-1)
である。ここで、φはオイラー関数である。
【００９７】
下記数８を満たす任意の整数A（1 < A < rP）を底とすると、オイラーの定理（数１）が下記数９のとおり成立する。ここで、GCD(X, Y)は整数Xと整数Yの最大公約数を求める関数である。
〔数８〕 GCD(A，rP) = 1
〔数９〕 A(r-1)(P-1) = Aφ(rP) = 1 mod rP
したがって、べき剰余A(r-1)(P-1) mod rPが1か否かを判定することにより、素数候補Pの素数性を判定することができる。
【００９８】
ただし、そもそもフェルマテストは確率的素数判定法であって、原理的に判定に過誤が生じる確率が内在する。過誤には、偽陰性と偽陽性がある。偽陰性の過誤とは、素数候補Pが素数であるにもかかわらず、フェイルと判定する場合であり、偽陽性の過誤とは、素数候補Pが素数ではないにもかかわらず、パスと判定する場合である。
【００９９】
通常のフェルマテストでは、偽陰性の過誤は発生しないが、ランダム化されたフェルマテストにおいては、AがrPと互いに素の関係にない場合に、偽陰性の過誤が発生する可能性がある。ただし、偽陰性は重大な問題ではない。素数を探索するアルゴリズムにおいては、いくつかの有効な候補が誤って捨てられるだけであり、探索に余計な時間がかかるに過ぎないからである。
【０１００】
偽陽性の過誤は、Pが素数でないとき、φ(rP)≠(r-1)(P-1)であるが、(r-1)(P-1)とφ(rP)が公約数dを持ち、さらに、特別なAがAd=1 mod rPを満足し、よってA(r-1)(P-1) = 1 mod rPとなる場合に発生する。フェルマテストやミラー・ラビンテストなどの素数性判定法が、「確率的」と呼ばれるのはこのためである。偽陽性の問題を克服するためには、例えば、異なった底Aを使って判定を繰り返す、あるいは、複数の異なった判定法を組み合わせるなどの方法が有効であることが知られている。
【０１０１】
偽陽性の過誤は、通常の素数性判定法でも発生し得るが、偽陰性はランダム化した判定法特有の問題である。前述したように、偽陰性の過誤は重大な問題ではなく、判定結果の正確性に影響するものではない。しかしながら、素数探索のアルゴリズムの性能を改善する目的から、偽陰性の過誤を防止することが望ましい。
【０１０２】
本実施形態においては、底Aをランダム化数rの倍数以外の整数とする（A mod r≠0）ことにより（ステップ４４４）、偽陰性の過誤を防止している。A mod r = 0となった場合には、新たなAが選ばれる。rとPがともに素数の場合、最大公約数の性質から知られているように、GCD(A, rP) = GCD(A, r)GCD(A,P)が成立する。加えて、rは素数なので、GCD(A, r) = 1 または GCD(A, r) = rの２つの場合しかあり得ない。GCD(A, r)=rとなるのは、Aがrで割り切れるときのみ、即ち、A = 0 mod rが成り立つときのみである。したがって、底Aをランダム化数rの倍数以外の整数とする（A mod r≠0）ことにより（ステップ４４４）、AとrPが互いに素であることを保証することができ、偽陰性の過誤を排除することができる。
【０１０３】
本実施形態においては、さらに、小さな素数を生成してランダム化数としている（ステップ４００）。これは必須の要件ではないが、このステップを採用することにより、AとrPが互いに素の関係となる確率を高め、偽陰性の過誤が発生する確率を下げ、また、偽陽性の過誤が発生する確率も同時に下げている。また、上記A mod r≠0のチェック（ステップ４４４）において、Aが条件を満足せず新たなAを選ばれる分岐を減らす効果もある。
【０１０４】
〔実施形態２の変形１〕＜小さい素数によるランダム化＞
上記実施形態２において、ランダム化数rを素数とすることにより、誤判定確率を下げることができ、信頼性を向上することができることを指摘した。そもそも本願発明が素数性判定を目的としているので、その入力に素数を要求することは、自己矛盾しているように思われるが、素数性判定の対象とする数は一般的に512ビットかそれ以上のビット数の大きな素数であるのに対し、ランダム化に必要な素数は16ビット程度の小さい素数ですむ。ランダム化数rとして16ビットの素数を生成する方法について、図６を用いて説明する。ただし、この技術思想は、16ビットに限定されるものではなく、より大きなビット数の素数生成にも拡張することができる。
【０１０５】
図６は、ステップ４００の小さい素数を生成するランダム化向け整数生成とステップ４４０のフェルマテストの２つの部分を含む。
【０１０６】
ステップ４０１において、16ビットの奇数の乱数rが生成される。ステップ４１１、４１２、４１３、４１４、４１５において、所定数17未満の小さい素数3、5、7、11、13によるrの可分性（割り切れること）が確認される。rが小さい素数で割り切れる場合、ステップ４０１において新しい乱数が生成される。rが小さい素数3、5、7、11、13で割り切れない場合、ステップ４２１において所定数17を底とするフェルマテストが実行される。より正確に言うと、べき剰余17r-1 mod rが計算される。結果が1でない場合、ステップ４０１において新しい乱数が生成される。結果が1の場合、ステップ４３１、４３２、４３３、４３４、４３５、４３６において33001、33227、38081、42127、47197、49771とrの比較が行われる。rが上記の数と異なる場合、rが素数であることが確認されたことになり、次のフェルマテスト（ステップ４４０）へ出力される。それ以外の場合は、ステップ４０１において新しい乱数が生成される。
【０１０７】
べき剰余演算に先立って、小さい素数によるrの可分性を確認している（ステップ４１１〜４１５）のは、素数ではないことが簡単に判別できる数を予め排除することにより、演算負荷の大きいべき剰余演算の回数を減らすためである。
【０１０８】
ステップ４３１〜４３６において、６個の整数でないことを確認するのは、以下の理由である。フェルマテストは、前述のとおり確率的素数判定法であるので、べき剰余17r-1 mod r = 1を満足するが、素数ではない整数rが存在する。そのような16ビットの整数は、上記６個の整数33001、33227、38081、42127、47197、49771のみである。
【０１０９】
以上のとおり、所定数17未満の素数3, 5, 7, 11, 13で割り切れず、べき剰余17r-1 mod r = 1を満足し、且つ、６個の整数33001、33227、38081、42127、47197、49771でない16ビットの整数は、素数であることが数学的に保証される。
【０１１０】
本願明細書に開示されている発明の範囲は、小さい素数を生成する特定の方法に限ったものではない。当分野に精通している者にとっては、本実施例で述べられている技術は異なるビット長を持つ素数にまで容易に及ぶことは明らかである。また、小さい素数は、異なる底や、ミラー・ラビンテスト、ソロベイ・ストラッセンテストなどの別の小さな素数性判定など、様々な手法によって生成することができること、または、メモリに格納された小さい素数のテーブルから直接選ぶことができるということは明らかである。
【０１１１】
素数であることが保証された数をランダム化数rとして用いることにより、偽陰性と偽陽性の過誤の発生する確率を下げることができ、素数性判定の効率を向上することができる。
【０１１２】
〔実施形態２の動作例〕
以上説明した実施の形態２の小さい素数を生成するランダム化向け整数生成（ステップ４００）とフェルマテスト（ステップ４４０）の動作を、具体的数値を例示して説明する。RSA暗号では512ビットかそれ以上の素数を使用することが望ましいが、理解しやすいよう、256ビットの整数の素数性判定について例示する。
【０１１３】
最初の素数候補P=0xd69cb0535ebbe48312596ae3ba8ca2f5が入力される。
【０１１４】
まず、ランダム化数rとして小さい素数rを生成する（ステップ４００）。
【０１１５】
16ビットの奇数の乱数が生成される。r = 45643=0xb24b（ステップ４０１）。
【０１１６】
r = 1 mod 3, （ステップ４１１）
r = 3 mod 5, （ステップ４１２）
r = 3 mod 7, （ステップ４１３）
r = 4 mod 11, （ステップ４１４）
r = 0 mod 13, （ステップ４１５）
r = 0 mod 13なので, r は素数ではない。
【０１１７】
新しい乱数が生成される。r = 22703=0x58af（ステップ４０１）。
【０１１８】
r = 2 mod 3, （ステップ４１１）
r = 3 mod 5, （ステップ４１２）
r = 2 mod 7, （ステップ４１３）
r = 10 mod 11, （ステップ４１４）
r = 5 mod 13（ステップ４１５）
rは小さい素数3、5、7、11、13のいずれによっても割り切ることができない。
【０１１９】
底を17とするべき剰余を計算する（ステップ４２１）と、
T = 17r-1 mod r = 20245 である。よって、rは底17のフェルマテストにフェイルとなり（ステップ４２２）、rは素数ではないことがわかる。
【０１２０】
さらに新しい乱数が生成される。r = 47797=0xbab5（ステップ４０１）。
【０１２１】
r = 1 mod 3, （ステップ４１１）
r = 2 mod 5, （ステップ４１２）
r = 1 mod 7, （ステップ４１３）
r = 10 mod 11, （ステップ４１４）
r = 12 mod 13, （ステップ４１５）
rは3、5、7、11、13のいずれによっても割り切ることができない。
【０１２２】
底を17とするべき剰余を計算する（ステップ４２１）と、
Ｔ = 17r-1 mod r = 1 である。よって、rは底17のフェルマテストにパスとなる（ステップ４２２）。
【０１２３】
rは33001、33227、38081、42127、47197、49771とは異なる（ステップ４３１〜４３６）ため、47797を素数と判定する。これをランダム化数rとして、フェルマテストのステップ４４０に進む。
【０１２４】
ランダム化された法を計算する（ステップ４４１）と、
rP=0xbab5×0xd69cb0535ebbe48312596ae3ba8ca2f5
rP=0x9c8594e53dc67edfcc00f0e2088d13d53939
である。
【０１２５】
ランダム化された指数を計算する（ステップ４４２）と、
(r-1)(P-1)=0xbab4×0xd69cb0535ebbe48312596ae3ba8ca2f4
(r-1)(P-1) = 0x9c84be488d732023e77dde889da95947db90
である。
乱数を発生し、底Aとする（ステップ４４３）。
【０１２６】
A=0xef9273ffcbf07692b8ae10dfc282824556f
底Aはrによって割り切ることができないか否かを確認すると（ステップ４４４）、
A mod r = 0xef9273ffcbf07692b8ae10dfc282824556f mod 0xbab5 = 0x84ac
であり、底Aはrによって割り切ることができないことがわかる。
ランダム化されたべき剰余演算
A(r-1)(P-1) = 0x49fd654061ce69cc0278cd67a1a3b414dac0 mod rP
を計算することができる。
【０１２７】
結果は1ではないので、素数候補Pは素数ではないことがわかり、素数候補Pはインクリメントされる。
【０１２８】
新しい候補は、
P=0xd69cb0535ebbe48312596ae3ba8ca2f7
である。
【０１２９】
ランダム化数rのため新しい16ビットの奇数の乱数が生成される。r = 50207=0xc41f（ステップ４０１）。
【０１３０】
r = 2 mod 3, （ステップ４１１）
r = 2 mod 5, （ステップ４１２）
r = 3 mod 7, （ステップ４１３）
r = 3 mod 11, （ステップ４１４）
r = 1 mod 13, （ステップ４１５）
rは3、5、7、11、13のいずれによっても割り切ることができない。
【０１３１】
底を17とするべき剰余を計算する（ステップ４２１）と、
T = 17r-1 mod r = 1 である。よって、rは底17のフェルマテストにパスとなる（ステップ４２２）。
【０１３２】
rは33001、33227、38081、42127、47197、49771とは異なる（ステップ４３１〜４３６）ため、50207を素数と判定する。これをランダム化数rとして、フェルマテストのステップ４４０に進む。
【０１３３】
ランダム化された法を計算する（ステップ４４１）と、
rP=0xc41f×0xd69cb0535ebbe48312596ae3ba8ca2f7
rP=0xa469f3f92ea053b505ebaeaa4c6743ccd7e9
である。
【０１３４】
ランダム化された指数を計算する（ステップ４４２）と、
(r-1)(P-1)=0xc41e×0xd69cb0535ebbe48312596ae3ba8ca2f6
(r-1)(P-1) =a4691d5c7e4cf4f921689c50e183893f70d4
である。
乱数を発生し、底Aとする（ステップ４４３）。
【０１３５】
A=0x6079d470762925c9d0382d34d776548a891e
底Aはrによって割り切ることができないか否かを確認すると（ステップ４４４）、
A mod r = 0x6079d470762925c9d0382d34d776548a891e mod 0xc41f = 0x96c8
であり、底Aはrによって割り切ることができないことがわかる。
べき剰余演算（ステップ４４４）
A(r-1)(P-1) = 1 mod rP
の結果は１であるので、「パス」と判定することができる（ステップ４４５）。
【０１３６】
この例において、素数候補P
P=0xd69cb0535ebbe48312596ae3ba8ca2f7
は、実際に素数である。
【０１３７】
〔実施形態２のハードウェア構成例〕
図３は、本実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。
【０１３８】
ICカードには多くの可能な用途がある。本実施例では、顧客がICカード１００を使用して店頭で商品を購入するようなICカードの使用例について述べる。店員は、ICカード端末１５０を持っている。ICカード端末１５０はICカードから生じるトランザクションを処理することができ、ネットワーク１６０経由で銀行が所有する鍵サーバー１７０に連結される。実際には、図３で示すシステムは、異なる顧客が所有する多くのICカードや異なる店に関連する多くの端末を含んでよい。鍵サーバーは、ICカードが銀行の顧客に発行された後ICカードを登録するために使われる端末に連結されてもよい。
【０１３９】
ICカードは、中央処理装置（CPU）１０１、剰余（A mod C）、乗算（A×B）、モジュラー乗算（A×B mod C）、べき剰余（AB mod C）などを高速で計算することができるコプロセッサ１０２、乱数生成器（RNG）１０３、RAM１０５、不揮発性メモリ１０６といったハードウェアモジュールを含む。実行すべき演算は、コプロセッサで高速に実行できるように設計することができる。一方、CPUのソフトウェアで実行されるように設計することもでき、要求される速度性能が低い場合には、コプロセッサを搭載しないICカードも実現可能である。
【０１４０】
ICカード１００内のハードウェアモジュールはバス１０４に接続されている。
【０１４１】
ICカードは、接触インターフェース１０８のコンタクトパッド１１０経由、もしくは非接触インターフェース１０７のアンテナ１０９経由で他のデバイスと連結することができる。接触インターフェース１０８と接触インターフェース１０７とは、いずれか一方を備えていれば足りるが、両方を備えていてもよい。両方を備えている場合には、補完的に動作させることができる。
【０１４２】
不揮発性メモリ１０６には、プログラム１２０とデータ１３０を格納する。データ１３０はRSA暗号公開指数Ｅ１３１、RSA暗号公開法N１３２、RSA暗号秘密鍵D１３３を含む。プログラム１２０はICカードOS１２１、ハッシュ関数プログラム１２２、RSA暗号プログラム１２３、RSA暗号鍵生成プログラム１２４を含む。全てのプログラムはCPU１０１によって実行され、中間結果をRAＭ１０５に格納する。RSA暗号プログラム１２３はハッシュ関数プログラム１２２、秘密鍵D１３３、公開法N１３２を使用して入力MのRSA署名
〔数１０〕 S = H(M)D mod N
を計算する。ここで、H(M)はハッシュ関数である。このべき剰余はコプロセッサ１０２で計算される。
【０１４３】
端末１５０は、ネットワークインターフェース１５１、CPU１５２、ICカードインターフェース１５３、RAM１５５、不揮発性メモリ１５６を含む。端末のハードウェアモジュールはバス１５４で連結される。RAMは鍵サーバー１７０から取得したICカードの公開指数Ｅ１３１と公開法Ｎ１３２を格納する。不揮発性メモリ１５６はCPU１５２によって実行されるRSAプログラム１５７を含む、中間結果をRAM１５５に格納する。RSAプログラム１５７はSE mod Nを計算し、結果をH(M)と比較することでICカードによって発行された署名Sを検証する。
【０１４４】
鍵サーバー１７０は、CPU１７１、ネットワークインターフェース１７２、RAM１７４、ICカードの公開指数E１３１と公開法N１３２を格納している不揮発性メモリ１７５を含む。鍵サーバーと端末はネットワーク１６０で連結される。
【０１４５】
〔実施形態２のRSAトランザクションの例〕
このシステムにおけるRSAトランザクションについて、図４を引用して説明する。
【０１４６】
図４は、図３に例示したシステムでRSAトランザクションを行う場合の、ICカード１００、端末１５０、鍵サーバー１７０間の一般的な相互関係である。
【０１４７】
エンロール（ステップ２００）はライフサイクルの初めに行われる。ICカード１００が発行された後、RSA暗号公開指数E１３１から公開法N１３２とRSA暗号秘密鍵D１３３がRSA暗号鍵生成プログラム１２４を使用してICカードにより生成される。RSA暗号公開鍵は公開指数と公開法から成り、ステップ２０３において鍵サーバー１７０の不揮発性メモリ１７５の中に格納される。エンロールステップでは、積極的な役割は行わずにただ通信を転送するだけのICカード端末を通じてICカードと鍵サーバーが連結される。このシナリオでは、RSA暗号鍵はICカード内で生成されることに留意する。秘密鍵はICカードから離れることはないので、セキュリティの点で有利となる。もし秘密鍵が鍵サーバーで生成されると、システムはシングルポイントフェイラーを有することになり、鍵サーバーを危険にさらすことによりエンロールされた全てのICカードの秘密鍵が漏えいする事態に陥る恐れがあるためである。
【０１４８】
いったんICカードがエンロールされると、ICカードはトランザクションを行うための端末で使用することができる。例えば、電子メッセージM1で示されているトランザクション２１０について考えてみる。このトランザクションはRSA暗号システムを使用してICカードによって署名される。署名はべき剰余
〔数１１〕 S1 = H(M1)D mod N
である。ここで、H(M1)はハッシュ関数プログラム１２２で計算されたM1のハッシュ値、DはRSA暗号秘密鍵１３３、Nは公開法１３２である。RSA署名は、べき剰余計算用のコプロセッサ１０２を使用してRSA暗号プログラム１２３によって計算される。
【０１４９】
RSA署名S1を検証するため、端末はICカードの公開鍵を必要とする。その公開鍵は、鍵サーバー１７０から取得し、端末のRAM１５５に格納される。鍵サーバーは公開指数Eと公開法Nの信頼性を証明する信頼できる機関としての役目をする。次に、端末は署名を検証する。ステップ２１５において、CPU１５２によって実行されるRSAプログラム１５７を使用して値
〔数１２〕 V1 = S1E mod N
が計算される。V1はステップ２１６においてトランザクションM1のハッシュ値H(M1)と比較される。値が等しい場合、トランザクションM1が行われる。RSA暗号システムの性質により、
〔数１３〕 (H(M)D)E = H(M) mod N
である。よって、端末は信頼できる署名を受け付ける。
【０１５０】
同様に、より多くのトランザクションを行うことができ、同様のICカードは異なる端末で使用することができ、同様の端末は異なるICカードから生じるトランザクションを処理することができる。
【０１５１】
より現実的な使用例を以下に紹介する。
【０１５２】
顧客Aが、非接触インターフェースによる移動決済機能を備えたスマートフォンを持っている。移動決済機能は、B社によって運営されている。初めに顧客Aが、スマートフォンのソフトウェアを動作させて、RSA暗号の秘密鍵Dと公開鍵(E, N)を生成する。秘密鍵Dの生成が顧客A自身によってなされるので、顧客A以外の何人も当該秘密鍵を知り得ないことが保証される。その後、顧客Aは生成した公開鍵をB社所有の鍵サーバーに転送する。この時点で、エンロールが完了し、顧客Aはスマートフォンを使って移動決済を行うことができるようになる。
【０１５３】
顧客Aが、B社が運用する移動決済を取り扱っているC店を訪れたとする。C店は顧客Aがスマートフォンで署名した請求書M1を発行する（ステップ２１１）。ここで、署名は、S1 = H(M1)D mod Nである。C店は顧客Aの公開鍵(E, N)をB社の鍵サーバからダウンロードし（ステップ２１３，２１４）、署名S1を照合する（ステップ２１５、２１６）。署名が真正なものであれば、支払いが認証される（ステップ２１８）。後日B社から顧客Aに対して、C店における当該購入代金が請求される。
【０１５４】
以上、図３および図４を引用して説明した例は、RSA署名の１つの可能な適用システムを説明したものであり、本発明の範囲はシステムの特定の実装に限ったものではない。
【０１５５】
〔実施形態２のRSA暗号鍵生成の例〕
実施形態２のRSA暗号鍵生成の例を、図５を引用して説明する。
【０１５６】
図５は、本願発明に係る素数性判定を行う半導体装置を使って、RSA暗号鍵を生成するソフトウェアの実装例を説明するフローチャートである。
【０１５７】
公開鍵と秘密鍵の生成（ステップ２０１）について以下に詳述する。RSA暗号鍵のペアは公開鍵E、Nと秘密鍵Dから成る。Eは公開指数、Nは公開法である。RSA暗号の実装の中には、秘密鍵がいくつかの整数から成るものもあるが、秘密鍵の代替定義は本特許で述べる発明には影響を与えないため、それについては割愛する。
【０１５８】
RSA暗号鍵生成アルゴリズムは公開指数E１３１とビット長nを入力パラメーターとして用いる。例えば、効率的な理由から、Eには216+1がよく選択されるが、他の選択も可能である。ビット長は因数分解攻撃が可能でないように選ばれなくてはならない。例えば、1024ビットより大きなビット長は安全であると考えられる。RSA暗号鍵生成アルゴリズムはステップ３１０と３５０において２つの素数PとQを生成し、ステップ３９１において公開法N = P×Q、ステップ３９２において秘密鍵Dを計算する。秘密鍵の代替定義の場合、ステップ３９２のみ影響を受ける。
【０１５９】
以下では、素数Pの生成（ステップ３１０）について詳述する。Qの生成（ステップ３５０）の説明は基本的にPと同様のため割愛する。まず、ステップ３１１においてRNG１０３を使用してビット長n/2の奇数の乱数整数Pが生成される。次に、ステップ３３１においてPの素数性判定が行われる。フェイルの場合、Pは+2インクリメントされ（ステップ３３３）、判定が繰り返される。パスの場合、公開指数E１３１とPの最大公約数（GCD）が計算される（ステップ３３４）。GCDが1でない場合、Pは+2インクリメントされ（ステップ３３３）、判定（ステップ３３１）が繰り返される。GCDが1の場合、適切な素数Pが見つかっていると判断する。
【０１６０】
ステップ３３１と３７１の素数性判定は、すでに図１、図２および図３を引用して説明したとおりであり、漏えい攻撃から素数性判定を守ることを目的とする本願発明の本質的部分である。
【０１６１】
〔実施形態２の変形２〕＜小さい素数の篩を使ったRSA暗号鍵生成＞
図６で示したRSA暗号鍵生成技術は、素数性判定のために多くの呼び出しを必要とし、コストのかかる多くのべき剰余を行う結果となる。べき剰余の回数を減らすため、篩分け技術がよく用いられる。篩分けとは最初の小さい素数によって素数候補の可分性をチェックすることを言う。素数候補が小さい素数で割り切れる場合、それは明らかに素数ではなく、アルゴリズムは素数性判定を行うことなく次の候補を探索することができる。
【０１６２】
図８は、小さい素数の篩を使用したRSA暗号鍵生成のフローチャートである。ステップ６３１と６７１において素数性判定が行われる前に小さい素数による素数候補PとQの可分性がチェックされるという点を除いて、RSA暗号鍵生成プログラムは図６で示したものと同様である。
【０１６３】
テーブル５３４に格納された小さい素数r[i]は連続してアクセスされ、P mod r[i]が計算される（ステップ６２２）。いずれのモジュラーリダクションの結果も0の場合、素数性判定を行うことなく候補はインクリメントされる（ステップ６３３）。モジュラーリダクションの結果が全て0でない場合、即ち小さい素数では割り切れない場合、ステップ６３１において素数性判定が行われる。
【０１６４】
素数候補Qについても同様に、予め小さい素数による篩分けをしたうえで、素数性判定６７１を行うことができる。
【０１６５】
これにより、素数性判定においてコストのかかるべき剰余演算の頻度を減らすことができる。
【０１６６】
小さい素数の篩は、本実施形態に特有に適用できるわけではなく、広く一般の素数性判定に適用できる。したがって、後述の実施形態３および実施形態４にも任意に組み合わせて採用することができる。特に、実施形態３では、小さい素数のテーブルを、別の目的で備える必要があるので、本変形例を組み合わせて採用する場合には、小さい素数の篩のためのテーブル５３４を共用することができる。
【０１６７】
〔実施形態３〕＜小さい素数のテーブルを使用したランダム化されたフェルマテスト＞
実施形態２は、ランダム化数rを素数とすることにより、偽陰性と偽陽性の過誤が発生する確率を低減することができるものである。逆に言うと、素数以外の数をランダム化数とすると、過誤が発生する確率が上昇することになる。本実施形態では、素数以外のランダム化数を用いて、フェルマテストをランダム化する実施の形態について説明する。小さい素数のテーブルを備え、そのテーブルを使って法をランダム化するランダム化数r1と指数をランダム化するランダム化数r2の組み合わせを生成する。ランダム化数r1とr2が素数でなくても、以下に述べる一定の関係を満たして生成された組み合わせであれば、フェルマテストが原理的に発生させてしまう過誤の確率を増加させることなく、ランダム化することができる。
【０１６８】
図２は、本発明の一実施形態に係る半導体装置のブロック図である。本実施形態に係る半導体装置は、乱数発生部１とランダム化数生成部６と法生成部２と指数生成部３とべき剰余演算部４と判定部５を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【０１６９】
乱数発生部１は、乱数列（j1, j2, j3, ・・・）を発生し、ランダム化数生成部６は、乱数列に基づいて算出される整数（t[j]）を指数とする素因数演算によりランダム化数を生成する。
【０１７０】
法生成部２は素数候補とランダム化数との積である第１整数R1を生成し、指数生成部３は第２整数R2を生成する。
【０１７１】
べき剰余演算部４は、第１整数R1を法とし、第２整数R2を指数とするべき剰余演算を実行し、判定部５は、べき剰余演算部４の出力に基づいて素数候補Pの素数性を判定する。
【０１７２】
図９はその動作例を表すフローチャートで、ステップ７００のランダム化数r1とr2の生成とステップ７４０のフェルマテストの２つの部分を含む。
【０１７３】
ランダム化数r1とr2の生成について述べる。本実施形態に係る半導体装置は、小さい素数のテーブルr[i]とその指数のテーブルt[i]を備える。
【０１７４】
小さい素数のテーブルr[i]の要素には、３から順に昇順でk番目までの素数が格納されている。
【０１７５】
r[1] = 3、r[2] = 5、r[3] = 7、・・・r[k] = k番目の素数
本来は最小の素数は2であるが、奇数の乱数を想定しているので、3を最小の素数として扱うこととしている。
【０１７６】
テーブルt[i]は各i番目の素数の指数を対応づけて格納する。これを用いて、ランダム化数r1を下式のように素因数分解された形式で表すことができる。
〔数１４〕 r1 = r[1]t[1]r[2]t[2]r[3]t[3]・・・r[k]t[k]
例えば、t[1] = 4、t[2] = 2、それ以外のt[i] = 0のとき、r1 = 34×52 = 2025となる。
【０１７７】
はじめに、r1とr2は1に初期化され（ステップ７１１）、テーブルの要素t[1]，t[2]・・・，t[k]は0に初期化される（ステップ７１２）。
【０１７８】
1以上k以下の整数である乱数jを生成する（ステップ７２２）。
【０１７９】
乱数jが指定する指数t[j] = 0の場合、つまり素数r[j]がランダム化数r1の素因数の中に存在しない場合、r1にr[j]を乗じて新たなr1とし、r2にはr[j]-1を乗じて新たなr2として、それぞれ更新する（ステップ７２４）。
【０１８０】
一方、乱数jが指定する指数t[j] > 0の場合、つまり素数r[j]がランダム化数r1の素因数の中に存在する場合は、r1にr[j]を乗じて新たなr1とし、r2にはr[j]を乗じて新たなr2として、それぞれ更新する（ステップ７２５）。
【０１８１】
いずれの場合も、t[j]を+1インクリメントする（ステップ７２６）。
【０１８２】
上記ステップ７２２から７２６で構成されるループを、r1のビット長が所定の長さ（図９の例では64ビット）を超えるまで、繰り返す。
【０１８３】
r1のビット長が64ビットを超えると、ステップ７４０においてフェルマテストが行われる。べき剰余の法r1は、素数候補Pにr1を乗じて算出される（ステップ７４１）。べき剰余の指数r2は、P-1にr2を乗じて算出される（ステップ７４２）。ランダム化数r1とr2は、いずれも乱数jに基づいて算出されたものであるので、乱数である。べき剰余の法R1および指数R2は、それぞれ乱数であるランダム化数r1およびr2を乗じて算出されるので、いずれもランダム化される。
【０１８４】
次に、べき剰余の底Aが乱数として生成され（ステップ７４３）、R1との最大公約数が1であるかを判定される（ステップ７４４）。R1との最大公約数が1でなければ、新たな底Aが生成される（ステップ７４３）、AとR1との最大公約数が１（AとR1が互いに素）であれば、下式のべき剰余演算が実行される（ステップ７４５）。
〔数１５〕 T = AR2 mod R1
べき剰余演算の結果T = 1の場合パスと判定され、T≠1の場合はフェイルと判定される（ステップ７５０）。
【０１８５】
ここまで述べてきた、指数と法をランダム化したフェルマテストの原理を説明する。
【０１８６】
一般に、GCD(a, b) = 1を満たす任意の整数a，bについて、オイラー関数は以下の性質を持つ。
〔数１６〕 φ(ab) = φ(a)φ(b)
ここで、φはオイラー関数であり、GCD(a, b)は整数aと整数bの最大公約数を求める関数である。
【０１８７】
r[j]が素数であり、t[j]が1以上の整数であるとき、
〔数１７〕 φ(r[j]t[j]) = (r[j]-1)r[j]t[j]-1
である。
【０１８８】
GCD(A，R1) = 1となるような任意の整数Aの場合、オイラーの定理による等式（数１）が成立するので、
〔数１８〕 Aφ(R1) = 1 mod R1
となる。
【０１８９】
その結果、素数候補Pが素数であるときには、r[j]が素数であるので、下式の関係が導かれる。
〔数１９〕 φ(R1)
= φ(Pr[1]t[1]r[2]t[2]・・・r[k]t[k])
= φ(P)φ(r[1]t[1])φ(r[2]t[2])・・・φ(r[k]t[k])
= (P-1)(r[1]-1)r[1]t[1]-1(r[2]-1)r[2]t[2]-1・・・(r[k]-1)r[k]t[k]-1
= R2
したがって、素数候補Pが素数であれば、GCD(A，R1) = 1であるので、
〔数２０〕 AR2 = Aφ(R1) = 1 mod R1
が成立する。
【０１９０】
以上の原理により、R1、R2のようにべき剰余の指数と法の双方のランダム化を行っても、素数候補Pの素数性判定を行うことができる。上記のように、この原理は、フェルマテストと等価であることが数学的に上記原理で説明した通り証明されており、ランダム化によって偽陰性の過誤が発生する確率を増加させることはなく、フェルマテストと同等の信頼性が保たれている。
【０１９１】
本実施形態で開示されている発明の範囲は特定のフェルマテストに限ったものではなく、ミラー・ラビンテストやソロベイ・ストラッセンテストなどの別の素数性判定にまで容易に及ぶ。
【０１９２】
ランダム化数R1とR2の生成例を以下に示す。この例では、小さい素数のテーブルを下式のように仮定する。即ち、k = 5である。
〔数２１〕 r[1] = 3, r[2] = 5, r[3] = 7, r[4] = 11, r[5] = 13
初めに、R1とR2を1に初期化し、t[1] = t[2] = t[3] = t[4] = t[5] = 0に初期化する。図９においては、R1が64ビットを繰り返すアルゴリズムであるとして説明したが、簡略化のため、R1が16ビットを超えたときに繰り返しを打ち切るものとして説明する。
【０１９３】
図１２に、このアルゴリズムによるランダム化数の生成過程を数値例とともに示す。
【０１９４】
アルゴリズムでは、ｊに１以上５以下の乱数を与え、R1にr[j]を乗じ、R2にはr[j]-1またはr[j]を乗じ、t[j]を更新する。R1 = 317625となった時点で、R1が16ビットを超えたので、ループを抜け、R1 = 317625とR2 = 132000が出力される。この時点でのt[i]は下式である。
〔数２２〕 t[1] = 1, t[2] = 3, t[3] = 1, t[4] = 2, t[5] = 0
これは、ランダム化数R1が数１４によって以下のように計算されたことを意味する。
〔数２３〕 R1 = r[1]t[1]r[2]t[2]r[3]t[3]r[4]t[4]r[5]t[5]
= 315371112130
= 317625
同様に、ランダム化数R2は、以下のように計算されたことになる。
〔数２４〕 R2 = (r[1]-1)r[1]t[1]-1
×(r[2]-1)r[2]t[2]-1
×(r[3]-1)r[3]t[3]-1
×(r[4]-1)r[4]t[4]-1
×(r[5]-1)r[5]t[5]-1
= (3-1)30×(5-1)52×(7-1)70×(11-1)111
= 132000
【０１９５】
〔実施形態３のハードウェア構成例〕
図７は、本実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。実施形態２のハードウェア構成例と比較して、不揮発性メモリ１０６に格納されているRSA暗号鍵生成プログラム５２４が異なり、プログラムに最大公約数を算出するGCDプログラム５２５が、またデータに小さい素数のテーブルr[1]・・・r[k]５３４が、それぞれ追加されている点が異なる。
【０１９６】
乱数jは、乱数発生器RNG１０３の出力する乱数に基づいて、1〜kの範囲に入るように変換するなどして生成することができる。テーブルt[i]は、アルゴリズムを実行する上での中間値としてRAM１０５に格納することができる。
【０１９７】
べき乗の演算は、コプロセッサによって高速化してもよいし、CPUによる繰り返し演算で実現してもよい。
【０１９８】
実施形態３のハードウェア構成例は、他の部分は実施形態２のハードウェア構成例（図３）で示したのと同じであり、同様の機能を実現することができ、RSAトランザクションの例（図４）も同様に実現することができることは、明らかである。
【０１９９】
〔実施形態４〕＜ランダム化されたミラー・ラビンテストによるRSA暗号鍵生成＞
フェルマテストと同様に、ミラー・ラビンテストも確率的素数性判定法である。
【０２００】
フェルマテストでパスと判定された整数が必ずしも素数ではないという点において、フェルマテストは確率論的な素数性判定である。Pが素数ではない（Pは合成数である）場合でも、AP-1 = 1 mod Pとなるような「フェルマライアー」と呼ばれる整数Aがある。さらに悪いことには、「カーマイケル数」と呼ばれる合成数Pの場合、Pより小さい素数の大部分はフェルマライアーである。
【０２０１】
ミラー・ラビンテストはフェルマテストと同じくよく知られた素数性判定であり、以下の事実が成立する。
・Pが素数であるとき、任意の底Aの場合、Pはミラー・ラビンテストをパスすることができる。
・Pが素数でないとき、ミラー・ラビンテストをパスするPより小さい整数Aの数はP/4より少ない。
【０２０２】
ミラー・ラビンテストが乱数の底Aでj回繰り返される場合、Pは合成数であるがミラー・ラビンテストをj回通過することができる確率はたかだか1/4j回である。例えば、もしミラー・ラビンテストが25回繰り返された場合、合成数Pがミラー・ラビンテストを通過する確率は2-50より小さい。
【０２０３】
しかしながら、素数は比較的稀なものであるため、エラーの確率を減少させるためにミラー・ラビンテストが何度も繰り返された場合、多くのべき乗が行われる。また、それらのべき乗の指数や法は多くのビットを共有しているため全て同様なものとなる。結果として、漏えい攻撃はインクリメンタルな調査によって生成された素数をミラー・ラビンテストにより再現することができると予想される。
【０２０４】
本実施形態４はミラー・ラビンテストの法と指数の両方をランダム化することによりこの問題に対処している。
【０２０５】
図１０と図１１は、実施形態４に係るランダム化されたミラー・ラビンテストのフローチャートである。
【０２０６】
ランダム化されたミラー・ラビンテストは、ステップ８１０の小さい素数生成（図１０）と、ステップ８２０のミラー・ラビンテスト（図１１）の２つの部分に区別することができる。ステップ８１０と８２０は25回繰り返される。25回の繰り返しが成功した場合、判定をパスする。
【０２０７】
ステップ８１０における小さい素数の生成は最下位2ビットが1の32ビットの小さい素数rを生成する。言い換えると、r = 2r'+1であり、r'は奇数である。ステップ８１１において、32ビットの奇数の乱数rが生成され、その最下位から2番目のビットが1に設定される。ステップ８１２、８１４、８１６において、底2、7、61を使用したミラー・ラビンテストで乱数rの素数性判定が行われる。ミラー・ラビンテストの詳細は簡略のために割愛する。底2、7、61のミラー・ラビンテストをパスすることができる32ビットの合成数はないため、rが判定をパスした場合、素数であることが保証される。判定がフェイルとなった場合、ステップ８１１において新しい乱数が生成される。
【０２０８】
これにより、小さい素数がランダム化数rとして生成され、ミラー・ラビンテスト（ステップ８２０）に送られる。
【０２０９】
ステップ８２０はランダム化されたミラー・ラビンテストであり、ステップ８２１において法R1 = rPが計算される。ステップ８２２において指数R2 = (r-1)(P-1)が計算され、R2はステップ８２４において奇数になるまで繰り返し2で割られる。割られた回数sを保持する。
【０２１０】
次に、以下の数値を算出する。
〔数２５〕 I = (P mod r)r-2 mod r =P-1 mod r（ステップ８３１）
〔数２６〕 B = 1+PI{(r-2) mod R1}（ステップ８３２）
〔数２７〕 C = P-1+PI{(2-P) mod R1}（ステップ８３３）
BとCは、ミラー・ラビンテストの判定に用いるための補助値である。
【０２１１】
ステップ８３４において乱数の底Aが生成され、ステップ８３５においてその底がランダム化数rで割り切れるかどうかを確認する。
【０２１２】
次に、ステップ８４１において奇数のランダム化された指数R2とランダム化された法R1でべき剰余T = AR2 mod R1が計算される。べき剰余Tの結果が1、または補助値BもしくはC、またはR1-1と等しい場合、ミラー・ラビンテストの次の繰り返しは新しいランダム化数rと新しい底Aで行われる。
【０２１３】
そうでない場合は、以下のステップがs-1回繰り返される。ステップ８４４においてTはT2 mod R1で更新され、ステップ８４５において補助値Cと比較される。TがCと等しい場合、ミラー・ラビンテストの次の繰り返しは新しいランダム化数rと新しい底Aで行われる。全ての繰り返しを通して、Tが一度もCと等しくなかった場合、ミラー・ラビンテストは不合格となり、整数Pは素数ではないと判定される。
【０２１４】
以上をランダム化数と底Aを乱数によって変化させながら行う25回の繰り返しのうち、１度もフェイル判定に至らなかった場合に、パスの判定を行う（ステップ８０２）。
【０２１５】
これにより、ミラー・ラビンテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【０２１６】
ここまで述べてきた、指数と法をランダム化したミラー・ラビンテストの原理を、従来のミラー・ラビンテストとの違いを中心にを説明する。
【０２１７】
まず、従来のミラー・ラビンテストについて簡単に説明する。
【０２１８】
従来のミラー・ラビンテストでは、素数候補Pが与えられたとき、P-1を、結果が奇数になるまで繰り返し２で除算し、繰り返し回数sおよび奇数P'を得る。その結果、下式の関係を満たす。
〔数２８〕 P-1 = 2sP'
次に、1 < A < Pを満たす乱数Aが生成され、素数性判定のため、下式のべき剰余が演算される。
〔数２９〕 T = AP' mod P
その結果Tが、1またはP-1と等しければパスと判定し、いずれとも等しくない場合には、さらに、下式の２乗演算をs-1回繰り返し、１度でも結果がP-1に等しければ、パスと判定する。
〔数３０〕 T = T2 mod P
さらに、上記数２８から数３０の一連の演算と判定を、rとAをランダムに変えながら所定回数行い、その過程がすべてパスになることをもって最終的に素数と判定することにより、信頼度を向上している。
【０２１９】
これに対し本実施形態では、素数候補Pが与えられたとき、ステップ８２４と８２５において、P-1に代えてランダム化された指数(r-1)(P-1)を対象として、同様に繰り返し２で割り、sとR2を得ている。その結果、数２８に対応する関係は、下式のようになる。
〔数３１〕 (r-1)(P-1) = 2sR2
次に底Aを生成する。従来1 < A < Pを満たす乱数をAとしたが、素数候補をランダム化するため、ステップ８３４において、1 < A < R1を満たす乱数を底Aとして生成し、底Aがランダム化数rの倍数になっていないことを条件として付加するため、ステップ８３５を行っている。
【０２２０】
底Aがランダム化数rの倍数になっていないという条件は、rとPがともに素数の場合にはGCD(A，R1) = 1と等価であるから、フェルマテストの動作原理で説明したのと同様に、数９と同じ下式の関係を導くための前提条件である。
〔数３２〕 A(r-1)(P-1) = Aφ(R1) = 1 mod R1
本実施形態のべき剰余は、ミラー・ラビンテストのランダム化を目的としているので、ランダム化されたR2を指数とするものであるから、ステップ８４１および下式に示すように、べき剰余演算の指数と法が置き換えられている。
〔数３３〕 T = AR2 mod R1
従来のミラー・ラビンテストでは、Tを1またはP-1と比較したが、本実施形態ではR1 = rPのようにランダム化されているので、従来１またはP-1の２通りだった期待値が４通りになる。その期待値を求める方法を説明する。
【０２２１】
中国の剰余定理を適用すると、T = a mod r， T = b mod Pのとき、
〔数３４〕 T = b+P{P-1 mod r}{(a-b) mod rP}
である。結果として、Pが素数の場合には、ステップ８４１および数３３のべき剰余の結果は、以下の４通りとなる。
〔数３５〕 b = 1、a = 1の場合、
T = 1
〔数３６〕 b = 1、a = -1 = r-1の場合、
T = 1+P(P-1mod r)(r-2) mod rP= 補助数B
〔数３７〕 b = -1 = P-1、A = 1の場合、
T = P-1+P(P-1mod r)(2-P) mod rP= 補助数C
〔数３８〕 b = -1 = P-1、A = -1 = r-1の場合、
T = rP-1 = R1-1
なお、上記数学は法Nが規定された有限体であるので、-1 = N-1である。
【０２２２】
べき剰余の結果Tが上のいずれか１つと等しいときにはパスと判定し、いずれも満たさないときには次のステップに進む。
【０２２３】
次のステップは、従来のミラー・ラビンテストでは数３０の２乗演算のs-1回繰り返しに対応する。
【０２２４】
ステップ８４４における２乗演算
〔数３９〕 T = T2 mod R1
をs-1回繰り返すうちの１つの結果が少なくとも１回、
〔数４０〕 T = P-1+P(P-1mod r)(2-P) mod R1 = 補助数C
となれば、パスと判定する（ステップ８４５）。
【０２２５】
R1がランダム化されている点を除けば、従来のミラー・ラビンテストと同様である。
【０２２６】
本実施形態では、ステップ８１１において32ビット乱数の最下位から2ビット目を1としてランダム化数とすることにより、r = 2r'+1であることが保証されているので、ステップ８４５の最初の２乗演算の結果、a = T mod r = 1となることがわかっている。したがって、ステップ８４５のとおりTはP-1ではなく補助数Cと比較しなければならない。
〔実施形態４のハードウェア構成例など〕
本実施形態は、実施形態１〜３に対して、素数性判定のアルゴリズムのみについて変更したものであるので、ハードウェア（図３）、相互関係（図４）、RSA暗号鍵生成プログラム（図５）はまったく同様である。
【０２２７】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。
【０２２８】
例えば、本発明に係るアルゴリズムを実行するハードウェアとして、CPUとコプロセッサと不揮発性メモリを搭載した半導体装置を例として説明したが、プログラムの供給方法は不揮発性メモリによる必要はなく、また、要求される速度性能が低ければ、べき剰余をはじめとする特殊な演算を高速化するコプロセッサを搭載する必要はない。
【０２２９】
また、本発明の適用例としてICカードを例示したが、暗号を利用する他のシステムに応用することは容易である。
【符号の説明】
【０２３０】
１ 乱数発生部
２ 指数生成部
３ 法生成部
４ べき剰余演算部
５ 判定部
６ ランダム化数生成部
１００ ICカード
１０１ CPU
１０２ コプロセッサ
１０３ 乱数発生回路（RNG）
１０５ RAM
１０６ 不揮発性メモリ
１２０ プログラム
１２４ ５２４ RSA鍵生成プログラム
１３０ データ
５３４ 素数テーブル
３１１ ３５１ ６１１ ６５１ 素数候補生成
３３１ ３７１ ６３１ ６７１ 素数性判定を実行
４００ ８１０ 小さい素数生成
７００ ランダム化数生成
４４０ ７４０ フェルマテスト
８２０ ミラー・ラビンテスト
４４１ ７４１ ８２１ ランダム化された法を計算
４４２ ７４２ ８２２ ランダム化された指数を計算
４４５ ７４５ ８４１ べき剰余を計算
４５０ ７５０ ８４２ べき剰余演算結果の判定
【技術分野】
【０００１】
本発明は、素数性判定を行う半導体装置に関し、特に暗号へのサイドチャネル攻撃などからの防御に有効な技術に関する。
【背景技術】
【０００２】
暗号に用いる暗号鍵は素数に基づいて生成されることが多い。例えば、RSA暗号公開鍵と秘密鍵を生成する際、２つの大きい素数を生成する必要がある。もしこの２つの素数が漏れると、公開鍵から秘密鍵を計算することは簡単なことなので、２つの素数は秘密にしておく必要がある。
【０００３】
素数生成は通常以下の方法で実施される。乱数が生成され、フェルマテスト、ミラー・ラビンテスト、ソロベイ・ストラッセンテストなどの素数性判定により乱数の素数性の検査が行われる（非特許文献１）。一般的に、これらの素数性判定はべき剰余を含む。例えば、フェルマテストにより整数Pの素数性判定を行う場合、整数の乱数Aが選択され、べき剰余AP-1 mod Pが計算される。
【０００４】
オイラーの定理によると、Nが正の整数でAをNと互いに素な正の整数としたとき、
〔数１〕 Aφ(N) mod N = 1
が成立する。ここではφはオイラー関数である。Pが素数である場合、φ(P)=P-1であり、べき剰余A(P-1) mod Pの結果は１であることが保証されている。
【０００５】
素数は比較的稀なものであるので、素数が見つかるまでに多くの候補の判定が行われることが多い。効率的な理由から、素数性判定が不合格の場合、その素数候補をインクリメントすることが望ましい。
【０００６】
RSA暗号鍵生成時の素数は暗号システムのセキュリティにとって重要なものであるため、例えば、素数性判定のべき剰余中に、素数の生成により生じる消費電力を計測し、消費電力のパターンを利用して素数の値の漏えいを行うサイドチャンネル解析などの潜在的な攻撃のターゲットとなる。インクリメンタルな素数生成では、互いに近い整数（P, P+2, P+4など）を対象としたべき剰余が実行されるために、これらの攻撃の危険は増幅される。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１０−２７７０８５号公報
【非特許文献】
【０００８】
【非特許文献１】Ａｌｆｒｅｄ Ｊ． Ｍｅｎｅｚｅｓ， Ｐａｕｌ Ｃ． ｖａｎ Ｏｏｒｓｃｈｏｔ ａｎｄ Ｓｃｏｔｔ Ａ． Ｖａｎｓｔｏｎｅ， “Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”， ＣＲＣ Ｐｒｅｓｓ， Ｃｈａｐｔｅｒ ４ − Ｐｕｂｌｉｃ Ｋｅｙ Ｐａｒａｍｅｔｅｒｓ．， Ｏｃｔｏｂｅｒ １９９６
【非特許文献２】ゲブハルト・ヴェックル（Ｇｅｂｈａｒｄ Ｂｏｃｋｌｅ）、「指数をランダム化したミラー・ラビンテスト」（Ｔｈｅ Ｍｉｌｌｅｒ−Ｒａｂｉｎ ｔｅｓｔ ｗｉｔｈ ｒａｎｄｏｍｉｚｅｄ ｅｘｐｏｎｅｎｔｓ）， ［ｏｎｌｉｎｅ］， ２００６年３月２３日、ハイデルベルグ大学ヴェックル教授ホームページ、［２０１１年１１月２５日検索］、インターネット＜ＵＲＬ： ｈｔｔｐ：／／ｗｗｗ．ｉｗｒ．ｕｎｉ−ｈｅｉｄｅｌｂｅｒｇ．ｄｅ／ｇｒｏｕｐｓ／ａｒｉｔｈ−ｇｅｏｍ／ｂｏｅｃｋｌｅ＿ｏｌｄ＿ｄｅｓｉｇｎ／ｐｒｅｐｒｉｎｔｓ．ｈｔｍｌ＞
【発明の概要】
【発明が解決しようとする課題】
【０００９】
特許文献１において開示されている発明は、フォールトアタックによる素数生成の出力の撹乱を検出するため予備証拠整数を利用する。しかしながら、本特許文献では素数性判定の漏えい問題については取り扱っていない。
【００１０】
非特許文献２には、指数のランダム化が行われるミラー・ラビン素数性判定法の変形が開示されている。べき剰余の指数がランダム化されているので、べき剰余の際の消費電力が攪乱されて素数の漏えいの危険性は低くなるが、法がランダム化されていないため、漏えいを完全に防ぐことはできない。
【００１１】
法をランダム化することは、べき乗の結果、即ち素数性判定の結果に影響を与えるので簡単なことではない。このことは、下式のフェルマテストについて考えてみると容易に理解できる。
〔数２〕AP-1= 1 mod P
ここで、「AP-1= 1 mod P」は、べき剰余AP-1 mod Pの結果が1であることを示す式で、当業者において汎用されている表現形式である。
【００１２】
指数P-1に任意の乱数rを乗じてランダム化した場合、ランダム化された指数でのべき乗の結果は変化せず、
〔数３〕 Ar(P-1)= 1 mod P
である。一方、任意の乱数sを使ってランダム化された法sPの場合、一般に、
〔数４〕 AP-1≠1 mod sP
〔数５〕 Ar(P-1)≠1 mod sP
である。素数候補Pが素数であっても、乱数sとの積sPは素数でないため、フェルマテストによりPの素数性を判定することができない。
【００１３】
本発明の目的は、素数性判定を行う半導体装置において、べき剰余の法をランダム化し、素数の漏えいを防止することである。
【００１４】
本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１５】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【００１６】
すなわち、べき剰余演算を含む素数性判定を行う半導体装置において、素数候補と乱数の積を前記べき剰余演算の法とする。
【発明の効果】
【００１７】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【００１８】
すなわち、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【図面の簡単な説明】
【００１９】
【図１】図１は、本発明の一実施形態に係る、素数候補の素数性判定を行う半導体装置のブロック図である。
【図２】図２は、本発明の別の実施形態に係る、素数候補の素数性判定を行う半導体装置のブロック図である。
【図３】図３は、本発明の一実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。
【図４】図４は、図３に例示したシステムでRSAトランザクションを行った場合の、ICカード、端末、鍵サーバー間の一般的な相互関係である。
【図５】図５は、本発明に係る素数性判定を行う半導体装置を使って、RSA暗号鍵を生成するソフトウェアの実装例を説明するフローチャートである。
【図６】図６は、図１または図２に示した素数候補の素数性判定を行う半導体装置の動作例を表すフローチャートである。
【図７】図７は、本発明の一実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。
【図８】図８は、小さい素数の篩を使用したRSA暗号鍵生成のフローチャートである。
【図９】図９は、図２に示した素数候補の素数性判定を行う半導体装置の動作例を表すフローチャートである。
【図１０】図１０は、実施形態４に係るランダム化されたミラー・ラビンテストのフローチャートのうち、前半の小さい素数生成ステップである。
【図１１】図１１は、実施形態４に係るランダム化されたミラー・ラビンテストのフローチャートのうち後半のミラー・ラビンテストのステップである。
【図１２】図１２は、小さい素数のテーブルを利用したランダム化数の生成過程の数値例である。
【発明を実施するための形態】
【００２０】
１．実施の形態の概要
先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【００２１】
〔１〕＜べき剰余における法をランダム化（上位概念）＞
乱数発生部（１）と法生成部（２）と指数生成部（３）とべき剰余演算部（４）と判定部（５）とを含んで構成され、入力された素数候補（P）の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００２２】
前記乱数発生部は、第１の乱数を発生してランダム化数（r）として生成し、前記法生成部は前記素数候補と前記ランダム化数とに基づいて第１整数（R1）を生成し、前記指数生成部は第２整数（R2）を生成する。
【００２３】
前記べき剰余演算部は、前記第１整数を法とし前記第２整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する。
【００２４】
これにより、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００２５】
〔２〕＜指数と法をランダム化したフェルマテスト（実施形態１）＞
乱数発生部（１）と法生成部（２）と指数生成部（３）とべき剰余演算部（４）と判定部（５）とを含んで構成され、入力された素数候補（P）の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００２６】
前記乱数発生部は、第１の乱数を発生してランダム化数（r）として生成し、前記法生成部は前記素数候補と前記ランダム化数の積（rP）を第１整数（R1）として生成し、前記指数生成部は前記素数候補から１を減じた数と前記ランダム化数から１を減じた数との積（(r-1)(P-1)）を第２整数（R2）として生成する。
【００２７】
前記べき剰余演算部は、前記第１整数を法とし前記第２整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する。
【００２８】
これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００２９】
〔３〕＜小さい素数によるランダム化＞
項２の半導体装置であって、ランダム化数生成部（６）をさらに備え、前記乱数発生部は、第１の乱数を発生して前記ランダム化数生成部に入力し、前記ランダム化数生成部は、前記第１の乱数が素数のとき、前記第１の乱数を前記ランダム化数として生成する。
【００３０】
これにより、素数性判定における偽陰性と偽陽性の過誤が発生する確率を下げることができ、判定の効率を向上することができる。偽陰性の過誤とは、素数候補が素数であるにも関わらず素数ではないと判定する過誤を指し、偽陽性の過誤とは、素数候補が素数ではないにも関わらず素数と判定する過誤を指す。過誤の発生確率を下げる原理については、実施形態２において詳述する。
【００３１】
〔４〕＜小さい素数（所定値L以下の素数）の算出方法＞
項２の半導体装置であって、ランダム化数生成部（６）をさらに備え、前記乱数発生部は、第２の乱数を発生して前記ランダム化数生成部に入力し、前記ランダム化数生成部は、前記ランダム化数を以下の方法で算出する。
【００３２】
前記乱数発生部（１）により、所定値L以下の第２の乱数を発生し（４０１）、
前記ランダム化数生成部（６）は、前記第２の乱数が下記条件１乃至３のすべてを満たすとき、前記第２の乱数を前記ランダム化数として生成する。
【００３３】
条件１： 前記第２の乱数が所定値Aより小さい素数を因数に持たないこと（４１１〜４１５）。
【００３４】
条件２： 前記所定値Aを底とし、前記第２の乱数から1を減じた数を指数とし、前記第２の乱数を法としたべき剰余演算の結果が1であること（４２１，４２２）。
【００３５】
条件３： 前記第２の乱数と、前記所定値L以下の整数であって、前記所定値Aを底とし前記整数から1を減じた数を指数とし前記整数を法としたべき剰余演算の結果が1であるが素数ではない整数のすべてと前記第２の乱数と比較して、前記第２の乱数がそのいずれとも異なるものであること（４３１〜４３６）。
【００３６】
これにより、ランダム化数に適する素数を簡易な方法で算出することができ、ICカードなどのローエンドデバイスにも実装することができる。
【００３７】
〔５〕＜素数候補の篩分け＞
項２、３、または４の半導体装置であって、前記素数候補（P）が少なくとも１個の素数で割り切れるか否かの判定を行う。
【００３８】
前記判定結果が割り切れる場合には次の素数候補を生成する。
【００３９】
前記判定結果が割り切れない場合には、前記歩数候補を、前記法生成部（２）と前記指数生成部（３）に入力する。
【００４０】
これにより、素数候補（P）が素数でないことが簡単にわかる場合には、べき剰余演算に至る前にフェイルの判定（素数候補（P）が素数ではない旨の判定）を出力して次の素数候補に進むことができるので、一連の素数性判定において、演算負荷の大きいべき剰余演算の実行回数を減らすことができる。
【００４１】
〔６〕＜素因数分解の指数を乱数として乱数を生成するフェルマテスト（実施形態２）＞
乱数発生部（１）とランダム化数生成部（６）と法生成部（２）と指数生成部（３）とべき剰余演算部（４）と判定部（５）を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００４２】
前記乱数発生部は、１個以上の第４の乱数列（j1, j2, j3, ・・・）を発生し（７２２）、前記ランダム化数生成部は、前記第４の乱数列に基づいて算出される整数（t[j]）を指数とする素因数演算によりランダム化数を生成する（７２４、７２５）。
【００４３】
前記法生成部は、前記素数候補と前記ランダム化数との積である第１整数（R1）を生成し（７４１）、前記指数生成部は、第２整数（R2）を生成する（７４２）。
【００４４】
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し（７４５）、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する（７５０）。
【００４５】
これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止され、また、ランダム化するためのランダム化数は、素数に限定されない。
【００４６】
〔７〕＜素数テーブルの利用； ランダム化数 = Πr(j)t[j] 1≦j≦k ＞
項６の半導体装置であって、各構成要素は以下の動作を行う。
【００４７】
前記乱数発生部（１）は、値が1以上k以下の乱数（j）を指数指定乱数として出力する（７２２）。
【００４８】
前記ランダム化数生成部（６）は、k個の互いに相違する素数を格納するk個の要素からなる第１の配列（r[k]）と前記素数のそれぞれに対応する指数を格納するk個の要素からなる第２の配列（t[k]）とを備え、前記指数指定乱数によって指定された回数を前記第２の配列の要素の値とする（７２６）。
【００４９】
前記第１の配列の各要素の値である素数に、前記第２の配列の対応する要素の値を指数とするべき乗演算によりk個の整数を算出し、前記k個の整数の積を算出して前記ランダム化数として出力する。
【００５０】
これにより、ランダム化数の別の生成方法を提供する。
【００５１】
〔８〕＜底はランダム化数×素数候補と互いに素＞
項６の半導体装置であって、べき剰余演算の底を、前記ランダム化数と前記素数候補の積と互いに素の整数とする（７４４）。
【００５２】
これにより、偽陰性の過誤が発生する確率を下げ、素数性判定の効率を向上することができる。
【００５３】
〔９〕＜ミラー・ラビン素数判定法における法のランダム化＞
乱数発生部（１）と法生成部（２）と指数生成部（３）とべき剰余演算部（４）と判定部（５）を含んで構成され、入力される素数候補（P）の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００５４】
前記乱数発生部は、第５の乱数をランダム化数（r）として生成する。
【００５５】
前記法生成部は、前記素数候補と前記ランダム化数との積を第１整数として生成する（８２１）。
【００５６】
前記指数生成部は、前記ランダム化数から１を減じた数と前記第１の素数候補から１を減じた数との積を素因数分解して、式(r-1)(P-1) = 2sP'を満たす最大の整数s及び整数P'を算出し、前記整数P'を第２整数として生成する（８２４、８２５）。
【００５７】
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し（８４１）、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する（８４２）。
【００５８】
これにより、ミラー・ラビンテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００５９】
〔１０〕＜底を変えながらべき剰余を繰り返すループ＞
項９の半導体装置であって、各構成要素は以下の動作を行う。
【００６０】
前記乱数発生部により第６の乱数を発生し（８３４）、前記第６の乱数（A）が、前記ランダム化数（r）で割り切れない数となるように選ぶ（８３５）。
【００６１】
前記べき剰余演算部は、前記第６の乱数を底とし前記第１整数を法とし前記第２整数を指数とするべき剰余演算を実行する。
【００６２】
前記判定部は、前記べき剰余演算（８４１）の結果が、1またはrP-1
または1+P(P-1 mod r) (r-2) mod rP
またはP-1+P(P-1 mod r) (2-P) mod rP
のいずれか１つと一致する場合（８４２）、前記素数候補が素数であるという暫定判断を行う。
【００６３】
前記素数候補が素数であるという暫定判断が維持される限り、前記乱数発生部により第５の乱数を発生して新たなランダム化数rとし、第６の乱数を発生して新たな底Aとし、繰り返し回数が所定回数に達するまで（８０２）繰り返すことにより素数性を判定する。
【００６４】
これにより、ミラー・ラビンテストにおけるべき剰余演算の法と指数がともにランダム化される。
【００６５】
〔１１〕＜小さい素数を生成する前処理＞
項９または１０の半導体装置であって、ランダム化数生成部（６）をさらに備え、前記ランダム化数生成部は、以下の条件を満たすときに、前記第５の乱数を前記ランダム化数として生成する。
【００６６】
条件１： 前記第５の乱数は、32ビットで且つ最下位2ビットがともに1であること（８１１）。
【００６７】
条件２： 前記第５の乱数（r）は、底を2とするミラー・ラビンテスト（８１２）と底を7とするミラー・ラビンテスト（８１４）と底を61とするミラー・ラビンテスト（８１６）とのすべてをパスする（８１０）こと。
【００６８】
これにより、ミラー・ラビンテストにおけるべき剰余演算の法と指数がともにランダム化され、そのランダム化数として素数が与えられる。
【００６９】
〔１２〕＜べき剰余における法をランダム化。アルゴリズムの核心（最上位概念）＞
べき剰余演算を含む素数性判定を行う半導体装置において、素数候補（P）と乱数（r）の積（rP）を前記べき剰余演算の法とする半導体装置である。
【００７０】
これにより、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００７１】
〔１３〕＜べき剰余における法および指数をランダム化＞
項１２の半導体装置において、前記素数候補と前記乱数に基づいて算出した値を前記べき剰余演算の指数とする。
【００７２】
これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００７３】
〔１４〕＜RSA暗号鍵の生成＞
項１乃至１３のいずれかの半導体装置であって、前記素数性判定を伴って２個の素数（P, Q）を生成し、
前記２個の素数に基づいて公開鍵および秘密鍵を出力するRSA暗号鍵生成を行う（３９１、３９２、６９１、６９２）。
【００７４】
これにより、RSA暗号鍵（公開鍵および秘密鍵）が、サイドチャネル解析などの攻撃から防御される。
【００７５】
〔１５〕＜ICカードのハードウェア＞
項１乃至１３のいずれかの半導体装置を含むICカード（１００）であって、CPU（１０１）とコプロセッサ（１０２）と乱数発生回路（１０３）とメモリ（１０５、１０６）とを備える。
【００７６】
前記コプロセッサは前記べき剰余演算を実行し、前記乱数発生回路は、前記乱数発生部（１）を構成し、もしくはこれに基礎となる乱数を供給する。
【００７７】
これにより、RSA暗号鍵（公開鍵および秘密鍵）が、サイドチャネル解析などの攻撃から防御されたICカードを提供することができる。
【００７８】
〔１６〕＜ICカードのメモリ＞
項１５のICカードであって、前記メモリ（１０６）に、RSA鍵生成プログラム（１２４、５２４）およびまたは素数テーブル（５３４）が格納されている。
【００７９】
これにより、RSA暗号鍵（公開鍵および秘密鍵）が、サイドチャネル解析などの攻撃から防御されたICカードを提供することができる。
【００８０】
〔１７〕＜ICカードにおける鍵エンロール＞
項１乃至１３のうちいずれかの半導体装置を含むICカードであって、トランザクションに先立って、前記素数性判定を伴って秘密鍵と公開鍵を生成し（２０１）、前記公開鍵を、ICカード端末を介して接続されている鍵サーバーに送信する（２０２）。
【００８１】
これにより、サイドチャネル解析などの攻撃から防御されたICカードを提供することができ、それを使ったトランザクションを提供することができる。
【００８２】
２．実施の形態の詳細
実施の形態について更に詳述する。
【００８３】
〔実施形態１〕＜べき剰余における法をランダム化＞
図１は、本発明の一実施形態に係る半導体装置のブロック図である。
【００８４】
乱数発生部１と法生成部２と指数生成部３とべき剰余演算部４と判定部５を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００８５】
乱数発生部１は、第１の乱数を発生してランダム化数rとして生成し法生成部２と指数生成部３に入力する。法生成部２は素数候補Pとランダム化数rとに基づいて第１整数R1を生成し、指数生成部３は第２整数R2を生成する。
【００８６】
べき剰余演算部４は、第１整数R1を法とし、第２整数R2を指数とするべき剰余演算を実行し、判定部５は、べき剰余演算部４の出力に基づいて素数候補Pの素数性を判定する。
【００８７】
これにより、べき剰余演算における法R1は、ランダム化数rに基づいて算出されランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補Pの値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００８８】
ここで、第１整数R1は、代表的には素数候補Pとランダム化数rの積rPである。第２整数R2は、べき剰余演算における法をランダム化するのに伴って、素数候補Pが素数のときに当該べき剰余演算の結果が１または他の特定値となるように、算出される。素数を法としたときにはべき剰余演算の結果は１であることが数学的に保証されているのに対し、ただ単にべき剰余の法をランダム化した場合には、ランダム化された法の値が素数である場合にべき剰余の演算結果が１になるにとどまり、素数候補Pが素数のときのべき剰余の演算結果が予測できない。本発明においては、法をランダム化しそれに適する指数を与えることによって、べき剰余の演算結果が素数候補Pに基づいて予測可能な特定値となるようにするものである。
【００８９】
〔実施形態２〕＜指数と法をランダム化したフェルマテスト＞
図１は、本発明の一実施形態に係る半導体装置のブロック図であり、図６は、その動作例を表すフローチャートである。図６は、ステップ４００の小さい素数を生成するランダム化向け整数生成とステップ４４０のフェルマテストの２つの部分を含む。まず、フェルマテスト（ステップ４４０）について説明する。
【００９０】
乱数発生部１と法生成部２と指数生成部３とべき剰余演算部４と判定部５を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【００９１】
乱数発生部１は、第１の乱数を発生してランダム化数rとして生成し、法生成部２は素数候補Pとランダム化数rの積rPを第１整数R1として生成し（ステップ４４１）、指数生成部３は素数候補Pから1を減じた数とランダム化数rから1を減じた数との積(r-1)(P-1)を第２整数R2として生成する（ステップ４４２）。
【００９２】
べき剰余演算部４は、第１整数R1を法とし、第２整数R2を指数とし、1より大きくrPより小さい乱数Aを底として（ステップ４４３）、下式の剰余演算を実行する（ステップ４４５）。
〔数６〕 A(r-1)(P-1) mod rP
判定部５は、素数候補の素数性を判定する。より具体的には、べき剰余演算部の演算結果が、1のときは「パス」を出力し、1以外のときは「フェイル」を出力する（ステップ４５０）。
【００９３】
これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【００９４】
ここで、底Aは1より大きくrPより小さい乱数から任意に選ぶことができるが、底Aをランダム化数rの倍数以外の整数とすることにより（ステップ４４４）、判定が偽陰性の過誤となる確率をより下げることができる。その理由は後述する。
【００９５】
ここまで述べてきた、指数と法をランダム化したフェルマテストの原理を説明する。
【００９６】
ランダム化数rが素数でありPも素数であると仮定した場合、
〔数７〕 φ(rP) = (r-1)(P-1)
である。ここで、φはオイラー関数である。
【００９７】
下記数８を満たす任意の整数A（1 < A < rP）を底とすると、オイラーの定理（数１）が下記数９のとおり成立する。ここで、GCD(X, Y)は整数Xと整数Yの最大公約数を求める関数である。
〔数８〕 GCD(A，rP) = 1
〔数９〕 A(r-1)(P-1) = Aφ(rP) = 1 mod rP
したがって、べき剰余A(r-1)(P-1) mod rPが1か否かを判定することにより、素数候補Pの素数性を判定することができる。
【００９８】
ただし、そもそもフェルマテストは確率的素数判定法であって、原理的に判定に過誤が生じる確率が内在する。過誤には、偽陰性と偽陽性がある。偽陰性の過誤とは、素数候補Pが素数であるにもかかわらず、フェイルと判定する場合であり、偽陽性の過誤とは、素数候補Pが素数ではないにもかかわらず、パスと判定する場合である。
【００９９】
通常のフェルマテストでは、偽陰性の過誤は発生しないが、ランダム化されたフェルマテストにおいては、AがrPと互いに素の関係にない場合に、偽陰性の過誤が発生する可能性がある。ただし、偽陰性は重大な問題ではない。素数を探索するアルゴリズムにおいては、いくつかの有効な候補が誤って捨てられるだけであり、探索に余計な時間がかかるに過ぎないからである。
【０１００】
偽陽性の過誤は、Pが素数でないとき、φ(rP)≠(r-1)(P-1)であるが、(r-1)(P-1)とφ(rP)が公約数dを持ち、さらに、特別なAがAd=1 mod rPを満足し、よってA(r-1)(P-1) = 1 mod rPとなる場合に発生する。フェルマテストやミラー・ラビンテストなどの素数性判定法が、「確率的」と呼ばれるのはこのためである。偽陽性の問題を克服するためには、例えば、異なった底Aを使って判定を繰り返す、あるいは、複数の異なった判定法を組み合わせるなどの方法が有効であることが知られている。
【０１０１】
偽陽性の過誤は、通常の素数性判定法でも発生し得るが、偽陰性はランダム化した判定法特有の問題である。前述したように、偽陰性の過誤は重大な問題ではなく、判定結果の正確性に影響するものではない。しかしながら、素数探索のアルゴリズムの性能を改善する目的から、偽陰性の過誤を防止することが望ましい。
【０１０２】
本実施形態においては、底Aをランダム化数rの倍数以外の整数とする（A mod r≠0）ことにより（ステップ４４４）、偽陰性の過誤を防止している。A mod r = 0となった場合には、新たなAが選ばれる。rとPがともに素数の場合、最大公約数の性質から知られているように、GCD(A, rP) = GCD(A, r)GCD(A,P)が成立する。加えて、rは素数なので、GCD(A, r) = 1 または GCD(A, r) = rの２つの場合しかあり得ない。GCD(A, r)=rとなるのは、Aがrで割り切れるときのみ、即ち、A = 0 mod rが成り立つときのみである。したがって、底Aをランダム化数rの倍数以外の整数とする（A mod r≠0）ことにより（ステップ４４４）、AとrPが互いに素であることを保証することができ、偽陰性の過誤を排除することができる。
【０１０３】
本実施形態においては、さらに、小さな素数を生成してランダム化数としている（ステップ４００）。これは必須の要件ではないが、このステップを採用することにより、AとrPが互いに素の関係となる確率を高め、偽陰性の過誤が発生する確率を下げ、また、偽陽性の過誤が発生する確率も同時に下げている。また、上記A mod r≠0のチェック（ステップ４４４）において、Aが条件を満足せず新たなAを選ばれる分岐を減らす効果もある。
【０１０４】
〔実施形態２の変形１〕＜小さい素数によるランダム化＞
上記実施形態２において、ランダム化数rを素数とすることにより、誤判定確率を下げることができ、信頼性を向上することができることを指摘した。そもそも本願発明が素数性判定を目的としているので、その入力に素数を要求することは、自己矛盾しているように思われるが、素数性判定の対象とする数は一般的に512ビットかそれ以上のビット数の大きな素数であるのに対し、ランダム化に必要な素数は16ビット程度の小さい素数ですむ。ランダム化数rとして16ビットの素数を生成する方法について、図６を用いて説明する。ただし、この技術思想は、16ビットに限定されるものではなく、より大きなビット数の素数生成にも拡張することができる。
【０１０５】
図６は、ステップ４００の小さい素数を生成するランダム化向け整数生成とステップ４４０のフェルマテストの２つの部分を含む。
【０１０６】
ステップ４０１において、16ビットの奇数の乱数rが生成される。ステップ４１１、４１２、４１３、４１４、４１５において、所定数17未満の小さい素数3、5、7、11、13によるrの可分性（割り切れること）が確認される。rが小さい素数で割り切れる場合、ステップ４０１において新しい乱数が生成される。rが小さい素数3、5、7、11、13で割り切れない場合、ステップ４２１において所定数17を底とするフェルマテストが実行される。より正確に言うと、べき剰余17r-1 mod rが計算される。結果が1でない場合、ステップ４０１において新しい乱数が生成される。結果が1の場合、ステップ４３１、４３２、４３３、４３４、４３５、４３６において33001、33227、38081、42127、47197、49771とrの比較が行われる。rが上記の数と異なる場合、rが素数であることが確認されたことになり、次のフェルマテスト（ステップ４４０）へ出力される。それ以外の場合は、ステップ４０１において新しい乱数が生成される。
【０１０７】
べき剰余演算に先立って、小さい素数によるrの可分性を確認している（ステップ４１１〜４１５）のは、素数ではないことが簡単に判別できる数を予め排除することにより、演算負荷の大きいべき剰余演算の回数を減らすためである。
【０１０８】
ステップ４３１〜４３６において、６個の整数でないことを確認するのは、以下の理由である。フェルマテストは、前述のとおり確率的素数判定法であるので、べき剰余17r-1 mod r = 1を満足するが、素数ではない整数rが存在する。そのような16ビットの整数は、上記６個の整数33001、33227、38081、42127、47197、49771のみである。
【０１０９】
以上のとおり、所定数17未満の素数3, 5, 7, 11, 13で割り切れず、べき剰余17r-1 mod r = 1を満足し、且つ、６個の整数33001、33227、38081、42127、47197、49771でない16ビットの整数は、素数であることが数学的に保証される。
【０１１０】
本願明細書に開示されている発明の範囲は、小さい素数を生成する特定の方法に限ったものではない。当分野に精通している者にとっては、本実施例で述べられている技術は異なるビット長を持つ素数にまで容易に及ぶことは明らかである。また、小さい素数は、異なる底や、ミラー・ラビンテスト、ソロベイ・ストラッセンテストなどの別の小さな素数性判定など、様々な手法によって生成することができること、または、メモリに格納された小さい素数のテーブルから直接選ぶことができるということは明らかである。
【０１１１】
素数であることが保証された数をランダム化数rとして用いることにより、偽陰性と偽陽性の過誤の発生する確率を下げることができ、素数性判定の効率を向上することができる。
【０１１２】
〔実施形態２の動作例〕
以上説明した実施の形態２の小さい素数を生成するランダム化向け整数生成（ステップ４００）とフェルマテスト（ステップ４４０）の動作を、具体的数値を例示して説明する。RSA暗号では512ビットかそれ以上の素数を使用することが望ましいが、理解しやすいよう、256ビットの整数の素数性判定について例示する。
【０１１３】
最初の素数候補P=0xd69cb0535ebbe48312596ae3ba8ca2f5が入力される。
【０１１４】
まず、ランダム化数rとして小さい素数rを生成する（ステップ４００）。
【０１１５】
16ビットの奇数の乱数が生成される。r = 45643=0xb24b（ステップ４０１）。
【０１１６】
r = 1 mod 3, （ステップ４１１）
r = 3 mod 5, （ステップ４１２）
r = 3 mod 7, （ステップ４１３）
r = 4 mod 11, （ステップ４１４）
r = 0 mod 13, （ステップ４１５）
r = 0 mod 13なので, r は素数ではない。
【０１１７】
新しい乱数が生成される。r = 22703=0x58af（ステップ４０１）。
【０１１８】
r = 2 mod 3, （ステップ４１１）
r = 3 mod 5, （ステップ４１２）
r = 2 mod 7, （ステップ４１３）
r = 10 mod 11, （ステップ４１４）
r = 5 mod 13（ステップ４１５）
rは小さい素数3、5、7、11、13のいずれによっても割り切ることができない。
【０１１９】
底を17とするべき剰余を計算する（ステップ４２１）と、
T = 17r-1 mod r = 20245 である。よって、rは底17のフェルマテストにフェイルとなり（ステップ４２２）、rは素数ではないことがわかる。
【０１２０】
さらに新しい乱数が生成される。r = 47797=0xbab5（ステップ４０１）。
【０１２１】
r = 1 mod 3, （ステップ４１１）
r = 2 mod 5, （ステップ４１２）
r = 1 mod 7, （ステップ４１３）
r = 10 mod 11, （ステップ４１４）
r = 12 mod 13, （ステップ４１５）
rは3、5、7、11、13のいずれによっても割り切ることができない。
【０１２２】
底を17とするべき剰余を計算する（ステップ４２１）と、
Ｔ = 17r-1 mod r = 1 である。よって、rは底17のフェルマテストにパスとなる（ステップ４２２）。
【０１２３】
rは33001、33227、38081、42127、47197、49771とは異なる（ステップ４３１〜４３６）ため、47797を素数と判定する。これをランダム化数rとして、フェルマテストのステップ４４０に進む。
【０１２４】
ランダム化された法を計算する（ステップ４４１）と、
rP=0xbab5×0xd69cb0535ebbe48312596ae3ba8ca2f5
rP=0x9c8594e53dc67edfcc00f0e2088d13d53939
である。
【０１２５】
ランダム化された指数を計算する（ステップ４４２）と、
(r-1)(P-1)=0xbab4×0xd69cb0535ebbe48312596ae3ba8ca2f4
(r-1)(P-1) = 0x9c84be488d732023e77dde889da95947db90
である。
乱数を発生し、底Aとする（ステップ４４３）。
【０１２６】
A=0xef9273ffcbf07692b8ae10dfc282824556f
底Aはrによって割り切ることができないか否かを確認すると（ステップ４４４）、
A mod r = 0xef9273ffcbf07692b8ae10dfc282824556f mod 0xbab5 = 0x84ac
であり、底Aはrによって割り切ることができないことがわかる。
ランダム化されたべき剰余演算
A(r-1)(P-1) = 0x49fd654061ce69cc0278cd67a1a3b414dac0 mod rP
を計算することができる。
【０１２７】
結果は1ではないので、素数候補Pは素数ではないことがわかり、素数候補Pはインクリメントされる。
【０１２８】
新しい候補は、
P=0xd69cb0535ebbe48312596ae3ba8ca2f7
である。
【０１２９】
ランダム化数rのため新しい16ビットの奇数の乱数が生成される。r = 50207=0xc41f（ステップ４０１）。
【０１３０】
r = 2 mod 3, （ステップ４１１）
r = 2 mod 5, （ステップ４１２）
r = 3 mod 7, （ステップ４１３）
r = 3 mod 11, （ステップ４１４）
r = 1 mod 13, （ステップ４１５）
rは3、5、7、11、13のいずれによっても割り切ることができない。
【０１３１】
底を17とするべき剰余を計算する（ステップ４２１）と、
T = 17r-1 mod r = 1 である。よって、rは底17のフェルマテストにパスとなる（ステップ４２２）。
【０１３２】
rは33001、33227、38081、42127、47197、49771とは異なる（ステップ４３１〜４３６）ため、50207を素数と判定する。これをランダム化数rとして、フェルマテストのステップ４４０に進む。
【０１３３】
ランダム化された法を計算する（ステップ４４１）と、
rP=0xc41f×0xd69cb0535ebbe48312596ae3ba8ca2f7
rP=0xa469f3f92ea053b505ebaeaa4c6743ccd7e9
である。
【０１３４】
ランダム化された指数を計算する（ステップ４４２）と、
(r-1)(P-1)=0xc41e×0xd69cb0535ebbe48312596ae3ba8ca2f6
(r-1)(P-1) =a4691d5c7e4cf4f921689c50e183893f70d4
である。
乱数を発生し、底Aとする（ステップ４４３）。
【０１３５】
A=0x6079d470762925c9d0382d34d776548a891e
底Aはrによって割り切ることができないか否かを確認すると（ステップ４４４）、
A mod r = 0x6079d470762925c9d0382d34d776548a891e mod 0xc41f = 0x96c8
であり、底Aはrによって割り切ることができないことがわかる。
べき剰余演算（ステップ４４４）
A(r-1)(P-1) = 1 mod rP
の結果は１であるので、「パス」と判定することができる（ステップ４４５）。
【０１３６】
この例において、素数候補P
P=0xd69cb0535ebbe48312596ae3ba8ca2f7
は、実際に素数である。
【０１３７】
〔実施形態２のハードウェア構成例〕
図３は、本実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。
【０１３８】
ICカードには多くの可能な用途がある。本実施例では、顧客がICカード１００を使用して店頭で商品を購入するようなICカードの使用例について述べる。店員は、ICカード端末１５０を持っている。ICカード端末１５０はICカードから生じるトランザクションを処理することができ、ネットワーク１６０経由で銀行が所有する鍵サーバー１７０に連結される。実際には、図３で示すシステムは、異なる顧客が所有する多くのICカードや異なる店に関連する多くの端末を含んでよい。鍵サーバーは、ICカードが銀行の顧客に発行された後ICカードを登録するために使われる端末に連結されてもよい。
【０１３９】
ICカードは、中央処理装置（CPU）１０１、剰余（A mod C）、乗算（A×B）、モジュラー乗算（A×B mod C）、べき剰余（AB mod C）などを高速で計算することができるコプロセッサ１０２、乱数生成器（RNG）１０３、RAM１０５、不揮発性メモリ１０６といったハードウェアモジュールを含む。実行すべき演算は、コプロセッサで高速に実行できるように設計することができる。一方、CPUのソフトウェアで実行されるように設計することもでき、要求される速度性能が低い場合には、コプロセッサを搭載しないICカードも実現可能である。
【０１４０】
ICカード１００内のハードウェアモジュールはバス１０４に接続されている。
【０１４１】
ICカードは、接触インターフェース１０８のコンタクトパッド１１０経由、もしくは非接触インターフェース１０７のアンテナ１０９経由で他のデバイスと連結することができる。接触インターフェース１０８と接触インターフェース１０７とは、いずれか一方を備えていれば足りるが、両方を備えていてもよい。両方を備えている場合には、補完的に動作させることができる。
【０１４２】
不揮発性メモリ１０６には、プログラム１２０とデータ１３０を格納する。データ１３０はRSA暗号公開指数Ｅ１３１、RSA暗号公開法N１３２、RSA暗号秘密鍵D１３３を含む。プログラム１２０はICカードOS１２１、ハッシュ関数プログラム１２２、RSA暗号プログラム１２３、RSA暗号鍵生成プログラム１２４を含む。全てのプログラムはCPU１０１によって実行され、中間結果をRAＭ１０５に格納する。RSA暗号プログラム１２３はハッシュ関数プログラム１２２、秘密鍵D１３３、公開法N１３２を使用して入力MのRSA署名
〔数１０〕 S = H(M)D mod N
を計算する。ここで、H(M)はハッシュ関数である。このべき剰余はコプロセッサ１０２で計算される。
【０１４３】
端末１５０は、ネットワークインターフェース１５１、CPU１５２、ICカードインターフェース１５３、RAM１５５、不揮発性メモリ１５６を含む。端末のハードウェアモジュールはバス１５４で連結される。RAMは鍵サーバー１７０から取得したICカードの公開指数Ｅ１３１と公開法Ｎ１３２を格納する。不揮発性メモリ１５６はCPU１５２によって実行されるRSAプログラム１５７を含む、中間結果をRAM１５５に格納する。RSAプログラム１５７はSE mod Nを計算し、結果をH(M)と比較することでICカードによって発行された署名Sを検証する。
【０１４４】
鍵サーバー１７０は、CPU１７１、ネットワークインターフェース１７２、RAM１７４、ICカードの公開指数E１３１と公開法N１３２を格納している不揮発性メモリ１７５を含む。鍵サーバーと端末はネットワーク１６０で連結される。
【０１４５】
〔実施形態２のRSAトランザクションの例〕
このシステムにおけるRSAトランザクションについて、図４を引用して説明する。
【０１４６】
図４は、図３に例示したシステムでRSAトランザクションを行う場合の、ICカード１００、端末１５０、鍵サーバー１７０間の一般的な相互関係である。
【０１４７】
エンロール（ステップ２００）はライフサイクルの初めに行われる。ICカード１００が発行された後、RSA暗号公開指数E１３１から公開法N１３２とRSA暗号秘密鍵D１３３がRSA暗号鍵生成プログラム１２４を使用してICカードにより生成される。RSA暗号公開鍵は公開指数と公開法から成り、ステップ２０３において鍵サーバー１７０の不揮発性メモリ１７５の中に格納される。エンロールステップでは、積極的な役割は行わずにただ通信を転送するだけのICカード端末を通じてICカードと鍵サーバーが連結される。このシナリオでは、RSA暗号鍵はICカード内で生成されることに留意する。秘密鍵はICカードから離れることはないので、セキュリティの点で有利となる。もし秘密鍵が鍵サーバーで生成されると、システムはシングルポイントフェイラーを有することになり、鍵サーバーを危険にさらすことによりエンロールされた全てのICカードの秘密鍵が漏えいする事態に陥る恐れがあるためである。
【０１４８】
いったんICカードがエンロールされると、ICカードはトランザクションを行うための端末で使用することができる。例えば、電子メッセージM1で示されているトランザクション２１０について考えてみる。このトランザクションはRSA暗号システムを使用してICカードによって署名される。署名はべき剰余
〔数１１〕 S1 = H(M1)D mod N
である。ここで、H(M1)はハッシュ関数プログラム１２２で計算されたM1のハッシュ値、DはRSA暗号秘密鍵１３３、Nは公開法１３２である。RSA署名は、べき剰余計算用のコプロセッサ１０２を使用してRSA暗号プログラム１２３によって計算される。
【０１４９】
RSA署名S1を検証するため、端末はICカードの公開鍵を必要とする。その公開鍵は、鍵サーバー１７０から取得し、端末のRAM１５５に格納される。鍵サーバーは公開指数Eと公開法Nの信頼性を証明する信頼できる機関としての役目をする。次に、端末は署名を検証する。ステップ２１５において、CPU１５２によって実行されるRSAプログラム１５７を使用して値
〔数１２〕 V1 = S1E mod N
が計算される。V1はステップ２１６においてトランザクションM1のハッシュ値H(M1)と比較される。値が等しい場合、トランザクションM1が行われる。RSA暗号システムの性質により、
〔数１３〕 (H(M)D)E = H(M) mod N
である。よって、端末は信頼できる署名を受け付ける。
【０１５０】
同様に、より多くのトランザクションを行うことができ、同様のICカードは異なる端末で使用することができ、同様の端末は異なるICカードから生じるトランザクションを処理することができる。
【０１５１】
より現実的な使用例を以下に紹介する。
【０１５２】
顧客Aが、非接触インターフェースによる移動決済機能を備えたスマートフォンを持っている。移動決済機能は、B社によって運営されている。初めに顧客Aが、スマートフォンのソフトウェアを動作させて、RSA暗号の秘密鍵Dと公開鍵(E, N)を生成する。秘密鍵Dの生成が顧客A自身によってなされるので、顧客A以外の何人も当該秘密鍵を知り得ないことが保証される。その後、顧客Aは生成した公開鍵をB社所有の鍵サーバーに転送する。この時点で、エンロールが完了し、顧客Aはスマートフォンを使って移動決済を行うことができるようになる。
【０１５３】
顧客Aが、B社が運用する移動決済を取り扱っているC店を訪れたとする。C店は顧客Aがスマートフォンで署名した請求書M1を発行する（ステップ２１１）。ここで、署名は、S1 = H(M1)D mod Nである。C店は顧客Aの公開鍵(E, N)をB社の鍵サーバからダウンロードし（ステップ２１３，２１４）、署名S1を照合する（ステップ２１５、２１６）。署名が真正なものであれば、支払いが認証される（ステップ２１８）。後日B社から顧客Aに対して、C店における当該購入代金が請求される。
【０１５４】
以上、図３および図４を引用して説明した例は、RSA署名の１つの可能な適用システムを説明したものであり、本発明の範囲はシステムの特定の実装に限ったものではない。
【０１５５】
〔実施形態２のRSA暗号鍵生成の例〕
実施形態２のRSA暗号鍵生成の例を、図５を引用して説明する。
【０１５６】
図５は、本願発明に係る素数性判定を行う半導体装置を使って、RSA暗号鍵を生成するソフトウェアの実装例を説明するフローチャートである。
【０１５７】
公開鍵と秘密鍵の生成（ステップ２０１）について以下に詳述する。RSA暗号鍵のペアは公開鍵E、Nと秘密鍵Dから成る。Eは公開指数、Nは公開法である。RSA暗号の実装の中には、秘密鍵がいくつかの整数から成るものもあるが、秘密鍵の代替定義は本特許で述べる発明には影響を与えないため、それについては割愛する。
【０１５８】
RSA暗号鍵生成アルゴリズムは公開指数E１３１とビット長nを入力パラメーターとして用いる。例えば、効率的な理由から、Eには216+1がよく選択されるが、他の選択も可能である。ビット長は因数分解攻撃が可能でないように選ばれなくてはならない。例えば、1024ビットより大きなビット長は安全であると考えられる。RSA暗号鍵生成アルゴリズムはステップ３１０と３５０において２つの素数PとQを生成し、ステップ３９１において公開法N = P×Q、ステップ３９２において秘密鍵Dを計算する。秘密鍵の代替定義の場合、ステップ３９２のみ影響を受ける。
【０１５９】
以下では、素数Pの生成（ステップ３１０）について詳述する。Qの生成（ステップ３５０）の説明は基本的にPと同様のため割愛する。まず、ステップ３１１においてRNG１０３を使用してビット長n/2の奇数の乱数整数Pが生成される。次に、ステップ３３１においてPの素数性判定が行われる。フェイルの場合、Pは+2インクリメントされ（ステップ３３３）、判定が繰り返される。パスの場合、公開指数E１３１とPの最大公約数（GCD）が計算される（ステップ３３４）。GCDが1でない場合、Pは+2インクリメントされ（ステップ３３３）、判定（ステップ３３１）が繰り返される。GCDが1の場合、適切な素数Pが見つかっていると判断する。
【０１６０】
ステップ３３１と３７１の素数性判定は、すでに図１、図２および図３を引用して説明したとおりであり、漏えい攻撃から素数性判定を守ることを目的とする本願発明の本質的部分である。
【０１６１】
〔実施形態２の変形２〕＜小さい素数の篩を使ったRSA暗号鍵生成＞
図６で示したRSA暗号鍵生成技術は、素数性判定のために多くの呼び出しを必要とし、コストのかかる多くのべき剰余を行う結果となる。べき剰余の回数を減らすため、篩分け技術がよく用いられる。篩分けとは最初の小さい素数によって素数候補の可分性をチェックすることを言う。素数候補が小さい素数で割り切れる場合、それは明らかに素数ではなく、アルゴリズムは素数性判定を行うことなく次の候補を探索することができる。
【０１６２】
図８は、小さい素数の篩を使用したRSA暗号鍵生成のフローチャートである。ステップ６３１と６７１において素数性判定が行われる前に小さい素数による素数候補PとQの可分性がチェックされるという点を除いて、RSA暗号鍵生成プログラムは図６で示したものと同様である。
【０１６３】
テーブル５３４に格納された小さい素数r[i]は連続してアクセスされ、P mod r[i]が計算される（ステップ６２２）。いずれのモジュラーリダクションの結果も0の場合、素数性判定を行うことなく候補はインクリメントされる（ステップ６３３）。モジュラーリダクションの結果が全て0でない場合、即ち小さい素数では割り切れない場合、ステップ６３１において素数性判定が行われる。
【０１６４】
素数候補Qについても同様に、予め小さい素数による篩分けをしたうえで、素数性判定６７１を行うことができる。
【０１６５】
これにより、素数性判定においてコストのかかるべき剰余演算の頻度を減らすことができる。
【０１６６】
小さい素数の篩は、本実施形態に特有に適用できるわけではなく、広く一般の素数性判定に適用できる。したがって、後述の実施形態３および実施形態４にも任意に組み合わせて採用することができる。特に、実施形態３では、小さい素数のテーブルを、別の目的で備える必要があるので、本変形例を組み合わせて採用する場合には、小さい素数の篩のためのテーブル５３４を共用することができる。
【０１６７】
〔実施形態３〕＜小さい素数のテーブルを使用したランダム化されたフェルマテスト＞
実施形態２は、ランダム化数rを素数とすることにより、偽陰性と偽陽性の過誤が発生する確率を低減することができるものである。逆に言うと、素数以外の数をランダム化数とすると、過誤が発生する確率が上昇することになる。本実施形態では、素数以外のランダム化数を用いて、フェルマテストをランダム化する実施の形態について説明する。小さい素数のテーブルを備え、そのテーブルを使って法をランダム化するランダム化数r1と指数をランダム化するランダム化数r2の組み合わせを生成する。ランダム化数r1とr2が素数でなくても、以下に述べる一定の関係を満たして生成された組み合わせであれば、フェルマテストが原理的に発生させてしまう過誤の確率を増加させることなく、ランダム化することができる。
【０１６８】
図２は、本発明の一実施形態に係る半導体装置のブロック図である。本実施形態に係る半導体装置は、乱数発生部１とランダム化数生成部６と法生成部２と指数生成部３とべき剰余演算部４と判定部５を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。
【０１６９】
乱数発生部１は、乱数列（j1, j2, j3, ・・・）を発生し、ランダム化数生成部６は、乱数列に基づいて算出される整数（t[j]）を指数とする素因数演算によりランダム化数を生成する。
【０１７０】
法生成部２は素数候補とランダム化数との積である第１整数R1を生成し、指数生成部３は第２整数R2を生成する。
【０１７１】
べき剰余演算部４は、第１整数R1を法とし、第２整数R2を指数とするべき剰余演算を実行し、判定部５は、べき剰余演算部４の出力に基づいて素数候補Pの素数性を判定する。
【０１７２】
図９はその動作例を表すフローチャートで、ステップ７００のランダム化数r1とr2の生成とステップ７４０のフェルマテストの２つの部分を含む。
【０１７３】
ランダム化数r1とr2の生成について述べる。本実施形態に係る半導体装置は、小さい素数のテーブルr[i]とその指数のテーブルt[i]を備える。
【０１７４】
小さい素数のテーブルr[i]の要素には、３から順に昇順でk番目までの素数が格納されている。
【０１７５】
r[1] = 3、r[2] = 5、r[3] = 7、・・・r[k] = k番目の素数
本来は最小の素数は2であるが、奇数の乱数を想定しているので、3を最小の素数として扱うこととしている。
【０１７６】
テーブルt[i]は各i番目の素数の指数を対応づけて格納する。これを用いて、ランダム化数r1を下式のように素因数分解された形式で表すことができる。
〔数１４〕 r1 = r[1]t[1]r[2]t[2]r[3]t[3]・・・r[k]t[k]
例えば、t[1] = 4、t[2] = 2、それ以外のt[i] = 0のとき、r1 = 34×52 = 2025となる。
【０１７７】
はじめに、r1とr2は1に初期化され（ステップ７１１）、テーブルの要素t[1]，t[2]・・・，t[k]は0に初期化される（ステップ７１２）。
【０１７８】
1以上k以下の整数である乱数jを生成する（ステップ７２２）。
【０１７９】
乱数jが指定する指数t[j] = 0の場合、つまり素数r[j]がランダム化数r1の素因数の中に存在しない場合、r1にr[j]を乗じて新たなr1とし、r2にはr[j]-1を乗じて新たなr2として、それぞれ更新する（ステップ７２４）。
【０１８０】
一方、乱数jが指定する指数t[j] > 0の場合、つまり素数r[j]がランダム化数r1の素因数の中に存在する場合は、r1にr[j]を乗じて新たなr1とし、r2にはr[j]を乗じて新たなr2として、それぞれ更新する（ステップ７２５）。
【０１８１】
いずれの場合も、t[j]を+1インクリメントする（ステップ７２６）。
【０１８２】
上記ステップ７２２から７２６で構成されるループを、r1のビット長が所定の長さ（図９の例では64ビット）を超えるまで、繰り返す。
【０１８３】
r1のビット長が64ビットを超えると、ステップ７４０においてフェルマテストが行われる。べき剰余の法r1は、素数候補Pにr1を乗じて算出される（ステップ７４１）。べき剰余の指数r2は、P-1にr2を乗じて算出される（ステップ７４２）。ランダム化数r1とr2は、いずれも乱数jに基づいて算出されたものであるので、乱数である。べき剰余の法R1および指数R2は、それぞれ乱数であるランダム化数r1およびr2を乗じて算出されるので、いずれもランダム化される。
【０１８４】
次に、べき剰余の底Aが乱数として生成され（ステップ７４３）、R1との最大公約数が1であるかを判定される（ステップ７４４）。R1との最大公約数が1でなければ、新たな底Aが生成される（ステップ７４３）、AとR1との最大公約数が１（AとR1が互いに素）であれば、下式のべき剰余演算が実行される（ステップ７４５）。
〔数１５〕 T = AR2 mod R1
べき剰余演算の結果T = 1の場合パスと判定され、T≠1の場合はフェイルと判定される（ステップ７５０）。
【０１８５】
ここまで述べてきた、指数と法をランダム化したフェルマテストの原理を説明する。
【０１８６】
一般に、GCD(a, b) = 1を満たす任意の整数a，bについて、オイラー関数は以下の性質を持つ。
〔数１６〕 φ(ab) = φ(a)φ(b)
ここで、φはオイラー関数であり、GCD(a, b)は整数aと整数bの最大公約数を求める関数である。
【０１８７】
r[j]が素数であり、t[j]が1以上の整数であるとき、
〔数１７〕 φ(r[j]t[j]) = (r[j]-1)r[j]t[j]-1
である。
【０１８８】
GCD(A，R1) = 1となるような任意の整数Aの場合、オイラーの定理による等式（数１）が成立するので、
〔数１８〕 Aφ(R1) = 1 mod R1
となる。
【０１８９】
その結果、素数候補Pが素数であるときには、r[j]が素数であるので、下式の関係が導かれる。
〔数１９〕 φ(R1)
= φ(Pr[1]t[1]r[2]t[2]・・・r[k]t[k])
= φ(P)φ(r[1]t[1])φ(r[2]t[2])・・・φ(r[k]t[k])
= (P-1)(r[1]-1)r[1]t[1]-1(r[2]-1)r[2]t[2]-1・・・(r[k]-1)r[k]t[k]-1
= R2
したがって、素数候補Pが素数であれば、GCD(A，R1) = 1であるので、
〔数２０〕 AR2 = Aφ(R1) = 1 mod R1
が成立する。
【０１９０】
以上の原理により、R1、R2のようにべき剰余の指数と法の双方のランダム化を行っても、素数候補Pの素数性判定を行うことができる。上記のように、この原理は、フェルマテストと等価であることが数学的に上記原理で説明した通り証明されており、ランダム化によって偽陰性の過誤が発生する確率を増加させることはなく、フェルマテストと同等の信頼性が保たれている。
【０１９１】
本実施形態で開示されている発明の範囲は特定のフェルマテストに限ったものではなく、ミラー・ラビンテストやソロベイ・ストラッセンテストなどの別の素数性判定にまで容易に及ぶ。
【０１９２】
ランダム化数R1とR2の生成例を以下に示す。この例では、小さい素数のテーブルを下式のように仮定する。即ち、k = 5である。
〔数２１〕 r[1] = 3, r[2] = 5, r[3] = 7, r[4] = 11, r[5] = 13
初めに、R1とR2を1に初期化し、t[1] = t[2] = t[3] = t[4] = t[5] = 0に初期化する。図９においては、R1が64ビットを繰り返すアルゴリズムであるとして説明したが、簡略化のため、R1が16ビットを超えたときに繰り返しを打ち切るものとして説明する。
【０１９３】
図１２に、このアルゴリズムによるランダム化数の生成過程を数値例とともに示す。
【０１９４】
アルゴリズムでは、ｊに１以上５以下の乱数を与え、R1にr[j]を乗じ、R2にはr[j]-1またはr[j]を乗じ、t[j]を更新する。R1 = 317625となった時点で、R1が16ビットを超えたので、ループを抜け、R1 = 317625とR2 = 132000が出力される。この時点でのt[i]は下式である。
〔数２２〕 t[1] = 1, t[2] = 3, t[3] = 1, t[4] = 2, t[5] = 0
これは、ランダム化数R1が数１４によって以下のように計算されたことを意味する。
〔数２３〕 R1 = r[1]t[1]r[2]t[2]r[3]t[3]r[4]t[4]r[5]t[5]
= 315371112130
= 317625
同様に、ランダム化数R2は、以下のように計算されたことになる。
〔数２４〕 R2 = (r[1]-1)r[1]t[1]-1
×(r[2]-1)r[2]t[2]-1
×(r[3]-1)r[3]t[3]-1
×(r[4]-1)r[4]t[4]-1
×(r[5]-1)r[5]t[5]-1
= (3-1)30×(5-1)52×(7-1)70×(11-1)111
= 132000
【０１９５】
〔実施形態３のハードウェア構成例〕
図７は、本実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。実施形態２のハードウェア構成例と比較して、不揮発性メモリ１０６に格納されているRSA暗号鍵生成プログラム５２４が異なり、プログラムに最大公約数を算出するGCDプログラム５２５が、またデータに小さい素数のテーブルr[1]・・・r[k]５３４が、それぞれ追加されている点が異なる。
【０１９６】
乱数jは、乱数発生器RNG１０３の出力する乱数に基づいて、1〜kの範囲に入るように変換するなどして生成することができる。テーブルt[i]は、アルゴリズムを実行する上での中間値としてRAM１０５に格納することができる。
【０１９７】
べき乗の演算は、コプロセッサによって高速化してもよいし、CPUによる繰り返し演算で実現してもよい。
【０１９８】
実施形態３のハードウェア構成例は、他の部分は実施形態２のハードウェア構成例（図３）で示したのと同じであり、同様の機能を実現することができ、RSAトランザクションの例（図４）も同様に実現することができることは、明らかである。
【０１９９】
〔実施形態４〕＜ランダム化されたミラー・ラビンテストによるRSA暗号鍵生成＞
フェルマテストと同様に、ミラー・ラビンテストも確率的素数性判定法である。
【０２００】
フェルマテストでパスと判定された整数が必ずしも素数ではないという点において、フェルマテストは確率論的な素数性判定である。Pが素数ではない（Pは合成数である）場合でも、AP-1 = 1 mod Pとなるような「フェルマライアー」と呼ばれる整数Aがある。さらに悪いことには、「カーマイケル数」と呼ばれる合成数Pの場合、Pより小さい素数の大部分はフェルマライアーである。
【０２０１】
ミラー・ラビンテストはフェルマテストと同じくよく知られた素数性判定であり、以下の事実が成立する。
・Pが素数であるとき、任意の底Aの場合、Pはミラー・ラビンテストをパスすることができる。
・Pが素数でないとき、ミラー・ラビンテストをパスするPより小さい整数Aの数はP/4より少ない。
【０２０２】
ミラー・ラビンテストが乱数の底Aでj回繰り返される場合、Pは合成数であるがミラー・ラビンテストをj回通過することができる確率はたかだか1/4j回である。例えば、もしミラー・ラビンテストが25回繰り返された場合、合成数Pがミラー・ラビンテストを通過する確率は2-50より小さい。
【０２０３】
しかしながら、素数は比較的稀なものであるため、エラーの確率を減少させるためにミラー・ラビンテストが何度も繰り返された場合、多くのべき乗が行われる。また、それらのべき乗の指数や法は多くのビットを共有しているため全て同様なものとなる。結果として、漏えい攻撃はインクリメンタルな調査によって生成された素数をミラー・ラビンテストにより再現することができると予想される。
【０２０４】
本実施形態４はミラー・ラビンテストの法と指数の両方をランダム化することによりこの問題に対処している。
【０２０５】
図１０と図１１は、実施形態４に係るランダム化されたミラー・ラビンテストのフローチャートである。
【０２０６】
ランダム化されたミラー・ラビンテストは、ステップ８１０の小さい素数生成（図１０）と、ステップ８２０のミラー・ラビンテスト（図１１）の２つの部分に区別することができる。ステップ８１０と８２０は25回繰り返される。25回の繰り返しが成功した場合、判定をパスする。
【０２０７】
ステップ８１０における小さい素数の生成は最下位2ビットが1の32ビットの小さい素数rを生成する。言い換えると、r = 2r'+1であり、r'は奇数である。ステップ８１１において、32ビットの奇数の乱数rが生成され、その最下位から2番目のビットが1に設定される。ステップ８１２、８１４、８１６において、底2、7、61を使用したミラー・ラビンテストで乱数rの素数性判定が行われる。ミラー・ラビンテストの詳細は簡略のために割愛する。底2、7、61のミラー・ラビンテストをパスすることができる32ビットの合成数はないため、rが判定をパスした場合、素数であることが保証される。判定がフェイルとなった場合、ステップ８１１において新しい乱数が生成される。
【０２０８】
これにより、小さい素数がランダム化数rとして生成され、ミラー・ラビンテスト（ステップ８２０）に送られる。
【０２０９】
ステップ８２０はランダム化されたミラー・ラビンテストであり、ステップ８２１において法R1 = rPが計算される。ステップ８２２において指数R2 = (r-1)(P-1)が計算され、R2はステップ８２４において奇数になるまで繰り返し2で割られる。割られた回数sを保持する。
【０２１０】
次に、以下の数値を算出する。
〔数２５〕 I = (P mod r)r-2 mod r =P-1 mod r（ステップ８３１）
〔数２６〕 B = 1+PI{(r-2) mod R1}（ステップ８３２）
〔数２７〕 C = P-1+PI{(2-P) mod R1}（ステップ８３３）
BとCは、ミラー・ラビンテストの判定に用いるための補助値である。
【０２１１】
ステップ８３４において乱数の底Aが生成され、ステップ８３５においてその底がランダム化数rで割り切れるかどうかを確認する。
【０２１２】
次に、ステップ８４１において奇数のランダム化された指数R2とランダム化された法R1でべき剰余T = AR2 mod R1が計算される。べき剰余Tの結果が1、または補助値BもしくはC、またはR1-1と等しい場合、ミラー・ラビンテストの次の繰り返しは新しいランダム化数rと新しい底Aで行われる。
【０２１３】
そうでない場合は、以下のステップがs-1回繰り返される。ステップ８４４においてTはT2 mod R1で更新され、ステップ８４５において補助値Cと比較される。TがCと等しい場合、ミラー・ラビンテストの次の繰り返しは新しいランダム化数rと新しい底Aで行われる。全ての繰り返しを通して、Tが一度もCと等しくなかった場合、ミラー・ラビンテストは不合格となり、整数Pは素数ではないと判定される。
【０２１４】
以上をランダム化数と底Aを乱数によって変化させながら行う25回の繰り返しのうち、１度もフェイル判定に至らなかった場合に、パスの判定を行う（ステップ８０２）。
【０２１５】
これにより、ミラー・ラビンテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。
【０２１６】
ここまで述べてきた、指数と法をランダム化したミラー・ラビンテストの原理を、従来のミラー・ラビンテストとの違いを中心にを説明する。
【０２１７】
まず、従来のミラー・ラビンテストについて簡単に説明する。
【０２１８】
従来のミラー・ラビンテストでは、素数候補Pが与えられたとき、P-1を、結果が奇数になるまで繰り返し２で除算し、繰り返し回数sおよび奇数P'を得る。その結果、下式の関係を満たす。
〔数２８〕 P-1 = 2sP'
次に、1 < A < Pを満たす乱数Aが生成され、素数性判定のため、下式のべき剰余が演算される。
〔数２９〕 T = AP' mod P
その結果Tが、1またはP-1と等しければパスと判定し、いずれとも等しくない場合には、さらに、下式の２乗演算をs-1回繰り返し、１度でも結果がP-1に等しければ、パスと判定する。
〔数３０〕 T = T2 mod P
さらに、上記数２８から数３０の一連の演算と判定を、rとAをランダムに変えながら所定回数行い、その過程がすべてパスになることをもって最終的に素数と判定することにより、信頼度を向上している。
【０２１９】
これに対し本実施形態では、素数候補Pが与えられたとき、ステップ８２４と８２５において、P-1に代えてランダム化された指数(r-1)(P-1)を対象として、同様に繰り返し２で割り、sとR2を得ている。その結果、数２８に対応する関係は、下式のようになる。
〔数３１〕 (r-1)(P-1) = 2sR2
次に底Aを生成する。従来1 < A < Pを満たす乱数をAとしたが、素数候補をランダム化するため、ステップ８３４において、1 < A < R1を満たす乱数を底Aとして生成し、底Aがランダム化数rの倍数になっていないことを条件として付加するため、ステップ８３５を行っている。
【０２２０】
底Aがランダム化数rの倍数になっていないという条件は、rとPがともに素数の場合にはGCD(A，R1) = 1と等価であるから、フェルマテストの動作原理で説明したのと同様に、数９と同じ下式の関係を導くための前提条件である。
〔数３２〕 A(r-1)(P-1) = Aφ(R1) = 1 mod R1
本実施形態のべき剰余は、ミラー・ラビンテストのランダム化を目的としているので、ランダム化されたR2を指数とするものであるから、ステップ８４１および下式に示すように、べき剰余演算の指数と法が置き換えられている。
〔数３３〕 T = AR2 mod R1
従来のミラー・ラビンテストでは、Tを1またはP-1と比較したが、本実施形態ではR1 = rPのようにランダム化されているので、従来１またはP-1の２通りだった期待値が４通りになる。その期待値を求める方法を説明する。
【０２２１】
中国の剰余定理を適用すると、T = a mod r， T = b mod Pのとき、
〔数３４〕 T = b+P{P-1 mod r}{(a-b) mod rP}
である。結果として、Pが素数の場合には、ステップ８４１および数３３のべき剰余の結果は、以下の４通りとなる。
〔数３５〕 b = 1、a = 1の場合、
T = 1
〔数３６〕 b = 1、a = -1 = r-1の場合、
T = 1+P(P-1mod r)(r-2) mod rP= 補助数B
〔数３７〕 b = -1 = P-1、A = 1の場合、
T = P-1+P(P-1mod r)(2-P) mod rP= 補助数C
〔数３８〕 b = -1 = P-1、A = -1 = r-1の場合、
T = rP-1 = R1-1
なお、上記数学は法Nが規定された有限体であるので、-1 = N-1である。
【０２２２】
べき剰余の結果Tが上のいずれか１つと等しいときにはパスと判定し、いずれも満たさないときには次のステップに進む。
【０２２３】
次のステップは、従来のミラー・ラビンテストでは数３０の２乗演算のs-1回繰り返しに対応する。
【０２２４】
ステップ８４４における２乗演算
〔数３９〕 T = T2 mod R1
をs-1回繰り返すうちの１つの結果が少なくとも１回、
〔数４０〕 T = P-1+P(P-1mod r)(2-P) mod R1 = 補助数C
となれば、パスと判定する（ステップ８４５）。
【０２２５】
R1がランダム化されている点を除けば、従来のミラー・ラビンテストと同様である。
【０２２６】
本実施形態では、ステップ８１１において32ビット乱数の最下位から2ビット目を1としてランダム化数とすることにより、r = 2r'+1であることが保証されているので、ステップ８４５の最初の２乗演算の結果、a = T mod r = 1となることがわかっている。したがって、ステップ８４５のとおりTはP-1ではなく補助数Cと比較しなければならない。
〔実施形態４のハードウェア構成例など〕
本実施形態は、実施形態１〜３に対して、素数性判定のアルゴリズムのみについて変更したものであるので、ハードウェア（図３）、相互関係（図４）、RSA暗号鍵生成プログラム（図５）はまったく同様である。
【０２２７】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。
【０２２８】
例えば、本発明に係るアルゴリズムを実行するハードウェアとして、CPUとコプロセッサと不揮発性メモリを搭載した半導体装置を例として説明したが、プログラムの供給方法は不揮発性メモリによる必要はなく、また、要求される速度性能が低ければ、べき剰余をはじめとする特殊な演算を高速化するコプロセッサを搭載する必要はない。
【０２２９】
また、本発明の適用例としてICカードを例示したが、暗号を利用する他のシステムに応用することは容易である。
【符号の説明】
【０２３０】
１ 乱数発生部
２ 指数生成部
３ 法生成部
４ べき剰余演算部
５ 判定部
６ ランダム化数生成部
１００ ICカード
１０１ CPU
１０２ コプロセッサ
１０３ 乱数発生回路（RNG）
１０５ RAM
１０６ 不揮発性メモリ
１２０ プログラム
１２４ ５２４ RSA鍵生成プログラム
１３０ データ
５３４ 素数テーブル
３１１ ３５１ ６１１ ６５１ 素数候補生成
３３１ ３７１ ６３１ ６７１ 素数性判定を実行
４００ ８１０ 小さい素数生成
７００ ランダム化数生成
４４０ ７４０ フェルマテスト
８２０ ミラー・ラビンテスト
４４１ ７４１ ８２１ ランダム化された法を計算
４４２ ７４２ ８２２ ランダム化された指数を計算
４４５ ７４５ ８４１ べき剰余を計算
４５０ ７５０ ８４２ べき剰余演算結果の判定
【特許請求の範囲】
【請求項１】
乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、
前記乱数発生部は、第１の乱数を発生してランダム化数として生成し、
前記法生成部は、前記素数候補と前記ランダム化数とに基づいて第１整数を生成し、
前記指数生成部は、第２整数を生成し、
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、
半導体装置。
【請求項２】
乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、
前記乱数発生部は、第１の乱数を発生してランダム化数として生成し、
前記法生成部は、前記素数候補と前記ランダム化数の積を第１整数として生成し、
前記指数生成部は、前記素数候補から１を減じた数と前記ランダム化数から１を減じた数との積を第２整数として生成し、
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、
半導体装置。
【請求項３】
請求項２記載の半導体装置であって、ランダム化数生成部をさらに備え、
前記乱数発生部は、前記第１の乱数を発生して前記ランダム化数生成部に入力し、
前記ランダム化数生成部は、前記第１の乱数が素数のとき、前記第１の乱数を前記ランダム化数として生成する、
半導体装置。
【請求項４】
請求項２記載の半導体装置であって、ランダム化数生成部をさらに備え、
前記乱数発生部は、所定値Ｌ以下の第２の乱数を発生して、前記ランダム化数発生部に入力し、
前記ランダム化数生成部は、前記第２の乱数が前記条件１乃至３のすべてを満たすとき、前記第２の乱数を前記ランダム化数として生成するものであって、
条件１は、前記第２の乱数が所定値Ａより小さい素数を因数に持たないことであり、
条件２は、前記所定値Ａを底とし、前記第２の乱数から１を減じた数を指数とし、前記第２の乱数を法としたべき剰余演算の結果が１であることであり、
条件３は、前記第２の乱数と、前記所定値Ｌ以下の整数であって、前記所定値Ａを底とし前記整数から１を減じた数を指数とし前記整数を法としたべき剰余演算の結果が１であるが素数ではない整数のすべてと前記第２の乱数と比較して、前記第２の乱数がそのいずれとも異なるものであることである、
半導体装置。
【請求項５】
請求項２記載の半導体装置であって、
前記素数候補が少なくとも１個の素数で割り切れるか否かの判定を行い、
前記判定結果が割り切れる場合には次の素数候補を生成し、
前記判定結果が割り切れない場合には、前記素数候補を前記法生成部と前記指数生成部に出力する、
半導体装置。
【請求項６】
乱数発生部とランダム化数生成部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、
前記乱数発生部は、１個以上の第４の乱数列を発生し、
前記ランダム化数生成部は、前記第４の乱数列に基づいて算出される整数を指数とする素因数演算によりランダム化数を生成し、
前記法生成部は、前記素数候補と前記ランダム化数との積である第１整数を生成し、
前記指数生成部は、第２整数を生成し、
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、
半導体装置。
【請求項７】
請求項６記載の半導体装置であって、
前記乱数発生部は、値が１以上ｋ以下の乱数を指数指定乱数として出力し、
前記ランダム化数生成部は、ｋ個の互いに相違する素数を格納するｋ個の要素からなる第１の配列と前記素数のそれぞれに対応する指数を格納するｋ個の要素からなる第２の配列とを備え、
前記指数指定乱数によって指定された回数を前記第２の配列の要素の値とし、
前記第１の配列の各要素の値である素数に、前記第２の配列の対応する要素の値を指数とするべき乗演算によりｋ個の整数を算出し、前記ｋ個の整数の積を算出して前記ランダム化数として出力する、
半導体装置。
【請求項８】
請求項６記載の半導体装置であって、
べき剰余演算の底を、前記ランダム化数と前記素数候補の積と互いに素の整数とする、
半導体装置。
【請求項９】
乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、
前記乱数発生部は、第５の乱数をランダム化数として生成し、
前記法生成部は、前記素数候補と前記ランダム化数との積を第１整数として生成し、
前記指数生成部は、前記ランダム化数から１を減じた数と前記第１の素数候補から１を減じた数との積を素因数分解して、式（ｒ−１）（Ｐ−１）＝２ｓＰ’を満たす最大の整数ｓ及び整数Ｐ’を算出し、前記整数Ｐ’を第２整数として生成し、
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、
半導体装置。
【請求項１０】
請求項９記載の半導体装置であって、
前記乱数発生部により第６の乱数を発生し、
前記第６の乱数は、前記ランダム化数で割り切れない数となるように選び、
前記べき剰余演算部は、前記第６の乱数を底とし前記第１整数を法とし前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算の結果が、１またはｒＰ−１
または１＋Ｐ（Ｐ−１ mｏｄ ｒ）（ｒ−２） ｍｏｄ ｒＰ
またはＰ−１＋Ｐ（Ｐ−１ ｍｏｄ ｒ）（２−Ｐ） ｍｏｄ ｒＰ
のいずれか１つと一致する場合、前記素数候補が素数であるという暫定判断をし、
前記素数候補が素数であるという暫定判断が維持される限り、前記乱数発生部により第５の乱数を発生して新たなランダム化数ｒとし、第６の乱数を発生して新たな底Ａとし、繰り返し回数が所定回数に達するまで繰り返すことにより素数性を判定する、
半導体装置。
【請求項１１】
請求項９記載の半導体装置であって、前記ランダム化数生成部をさらに備え、
前記乱数発生部は、第５の乱数を発生して、前記ランダム化数生成部に入力し、
前記ランダム化数生成部は、
前記第５の乱数が、３２ビットで且つ最下位２ビットがともに１であり、
前記第５の乱数が、底を２とするミラー・ラビンテストと底を７とするミラー・ラビンテストと底を６１とするミラー・ラビンテストとのすべてをパスするときに、
前記第５の乱数を前記ランダム化数として生成する、
半導体装置。
【請求項１２】
べき剰余演算を含む素数性判定を行う半導体装置において、
素数候補と乱数の積を前記べき剰余演算の法とする、
半導体装置。
【請求項１３】
請求項１２記載の半導体装置において、
前記素数候補と前記乱数に基づいて算出した値を前記べき剰余演算の指数とする、
半導体装置。
【請求項１４】
請求項１記載の半導体装置であって、
前記素数性判定を伴って２個の素数を生成し、
前記２個の素数に基づいて公開鍵および秘密鍵を出力するＲＳＡ暗号鍵生成を行う、
半導体装置。
【請求項１５】
請求項１記載の半導体装置を含むＩＣカードであって、
ＣＰＵとコプロセッサと乱数発生回路とメモリとを備え、
前記コプロセッサは前記べき剰余演算を実行し、
前記乱数発生回路は、前記乱数発生部を構成し、もしくはこれに基礎となる乱数を供給する、
ＩＣカード。
【請求項１６】
請求項１５記載のＩＣカードであって、
前記メモリに、ＲＳＡ鍵生成プログラムおよびまたは素数テーブルが格納されている、
ＩＣカード。
【請求項１７】
請求項１記載の半導体装置を含むＩＣカードであって、
トランザクションに先立って、前記素数性判定を伴って秘密鍵と公開鍵を生成し、
前記公開鍵を、ＩＣカード端末を介して接続されている鍵サーバーに送信する、
ＩＣカード。
【請求項１】
乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、
前記乱数発生部は、第１の乱数を発生してランダム化数として生成し、
前記法生成部は、前記素数候補と前記ランダム化数とに基づいて第１整数を生成し、
前記指数生成部は、第２整数を生成し、
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、
半導体装置。
【請求項２】
乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、
前記乱数発生部は、第１の乱数を発生してランダム化数として生成し、
前記法生成部は、前記素数候補と前記ランダム化数の積を第１整数として生成し、
前記指数生成部は、前記素数候補から１を減じた数と前記ランダム化数から１を減じた数との積を第２整数として生成し、
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、
半導体装置。
【請求項３】
請求項２記載の半導体装置であって、ランダム化数生成部をさらに備え、
前記乱数発生部は、前記第１の乱数を発生して前記ランダム化数生成部に入力し、
前記ランダム化数生成部は、前記第１の乱数が素数のとき、前記第１の乱数を前記ランダム化数として生成する、
半導体装置。
【請求項４】
請求項２記載の半導体装置であって、ランダム化数生成部をさらに備え、
前記乱数発生部は、所定値Ｌ以下の第２の乱数を発生して、前記ランダム化数発生部に入力し、
前記ランダム化数生成部は、前記第２の乱数が前記条件１乃至３のすべてを満たすとき、前記第２の乱数を前記ランダム化数として生成するものであって、
条件１は、前記第２の乱数が所定値Ａより小さい素数を因数に持たないことであり、
条件２は、前記所定値Ａを底とし、前記第２の乱数から１を減じた数を指数とし、前記第２の乱数を法としたべき剰余演算の結果が１であることであり、
条件３は、前記第２の乱数と、前記所定値Ｌ以下の整数であって、前記所定値Ａを底とし前記整数から１を減じた数を指数とし前記整数を法としたべき剰余演算の結果が１であるが素数ではない整数のすべてと前記第２の乱数と比較して、前記第２の乱数がそのいずれとも異なるものであることである、
半導体装置。
【請求項５】
請求項２記載の半導体装置であって、
前記素数候補が少なくとも１個の素数で割り切れるか否かの判定を行い、
前記判定結果が割り切れる場合には次の素数候補を生成し、
前記判定結果が割り切れない場合には、前記素数候補を前記法生成部と前記指数生成部に出力する、
半導体装置。
【請求項６】
乱数発生部とランダム化数生成部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、
前記乱数発生部は、１個以上の第４の乱数列を発生し、
前記ランダム化数生成部は、前記第４の乱数列に基づいて算出される整数を指数とする素因数演算によりランダム化数を生成し、
前記法生成部は、前記素数候補と前記ランダム化数との積である第１整数を生成し、
前記指数生成部は、第２整数を生成し、
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、
半導体装置。
【請求項７】
請求項６記載の半導体装置であって、
前記乱数発生部は、値が１以上ｋ以下の乱数を指数指定乱数として出力し、
前記ランダム化数生成部は、ｋ個の互いに相違する素数を格納するｋ個の要素からなる第１の配列と前記素数のそれぞれに対応する指数を格納するｋ個の要素からなる第２の配列とを備え、
前記指数指定乱数によって指定された回数を前記第２の配列の要素の値とし、
前記第１の配列の各要素の値である素数に、前記第２の配列の対応する要素の値を指数とするべき乗演算によりｋ個の整数を算出し、前記ｋ個の整数の積を算出して前記ランダム化数として出力する、
半導体装置。
【請求項８】
請求項６記載の半導体装置であって、
べき剰余演算の底を、前記ランダム化数と前記素数候補の積と互いに素の整数とする、
半導体装置。
【請求項９】
乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、
前記乱数発生部は、第５の乱数をランダム化数として生成し、
前記法生成部は、前記素数候補と前記ランダム化数との積を第１整数として生成し、
前記指数生成部は、前記ランダム化数から１を減じた数と前記第１の素数候補から１を減じた数との積を素因数分解して、式（ｒ−１）（Ｐ−１）＝２ｓＰ’を満たす最大の整数ｓ及び整数Ｐ’を算出し、前記整数Ｐ’を第２整数として生成し、
前記べき剰余演算部は、前記第１整数を法とし、前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、
半導体装置。
【請求項１０】
請求項９記載の半導体装置であって、
前記乱数発生部により第６の乱数を発生し、
前記第６の乱数は、前記ランダム化数で割り切れない数となるように選び、
前記べき剰余演算部は、前記第６の乱数を底とし前記第１整数を法とし前記第２整数を指数とするべき剰余演算を実行し、
前記判定部は、前記べき剰余演算の結果が、１またはｒＰ−１
または１＋Ｐ（Ｐ−１ mｏｄ ｒ）（ｒ−２） ｍｏｄ ｒＰ
またはＰ−１＋Ｐ（Ｐ−１ ｍｏｄ ｒ）（２−Ｐ） ｍｏｄ ｒＰ
のいずれか１つと一致する場合、前記素数候補が素数であるという暫定判断をし、
前記素数候補が素数であるという暫定判断が維持される限り、前記乱数発生部により第５の乱数を発生して新たなランダム化数ｒとし、第６の乱数を発生して新たな底Ａとし、繰り返し回数が所定回数に達するまで繰り返すことにより素数性を判定する、
半導体装置。
【請求項１１】
請求項９記載の半導体装置であって、前記ランダム化数生成部をさらに備え、
前記乱数発生部は、第５の乱数を発生して、前記ランダム化数生成部に入力し、
前記ランダム化数生成部は、
前記第５の乱数が、３２ビットで且つ最下位２ビットがともに１であり、
前記第５の乱数が、底を２とするミラー・ラビンテストと底を７とするミラー・ラビンテストと底を６１とするミラー・ラビンテストとのすべてをパスするときに、
前記第５の乱数を前記ランダム化数として生成する、
半導体装置。
【請求項１２】
べき剰余演算を含む素数性判定を行う半導体装置において、
素数候補と乱数の積を前記べき剰余演算の法とする、
半導体装置。
【請求項１３】
請求項１２記載の半導体装置において、
前記素数候補と前記乱数に基づいて算出した値を前記べき剰余演算の指数とする、
半導体装置。
【請求項１４】
請求項１記載の半導体装置であって、
前記素数性判定を伴って２個の素数を生成し、
前記２個の素数に基づいて公開鍵および秘密鍵を出力するＲＳＡ暗号鍵生成を行う、
半導体装置。
【請求項１５】
請求項１記載の半導体装置を含むＩＣカードであって、
ＣＰＵとコプロセッサと乱数発生回路とメモリとを備え、
前記コプロセッサは前記べき剰余演算を実行し、
前記乱数発生回路は、前記乱数発生部を構成し、もしくはこれに基礎となる乱数を供給する、
ＩＣカード。
【請求項１６】
請求項１５記載のＩＣカードであって、
前記メモリに、ＲＳＡ鍵生成プログラムおよびまたは素数テーブルが格納されている、
ＩＣカード。
【請求項１７】
請求項１記載の半導体装置を含むＩＣカードであって、
トランザクションに先立って、前記素数性判定を伴って秘密鍵と公開鍵を生成し、
前記公開鍵を、ＩＣカード端末を介して接続されている鍵サーバーに送信する、
ＩＣカード。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１３−１１３９７８（Ｐ２０１３−１１３９７８Ａ）
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願番号】特願２０１１−２５９０８３（Ｐ２０１１−２５９０８３）
【出願日】平成２３年１１月２８日（２０１１．１１．２８）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願日】平成２３年１１月２８日（２０１１．１１．２８）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
[ Back to top ]