"乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、前記乱数発生部は、第1の乱数を発生してランダム化数として生成し、前記法生成部は、前記素数候補と前記ランダム化数とに基づいて第1整数を生成し、前記指数生成部は、第2整数を生成し、前記べき剰余演算部は、前記第1整数を法とし、前記第2整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、半導体装置。乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、前記乱数発生部は、第1の乱数を発生してランダム化数として生成し、前記法生成部は、前記素数候補と前記ランダム化数の積を第1整数として生成し、前記指数生成部は、前記素数候補から1を減じた数と前記ランダム化数から1を減じた数との積を第2整数として生成し、前記べき剰余演算部は、前記第1整数を法とし、前記第2整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、半導体装置。請求項2記載の半導体装置であって、ランダム化数生成部をさらに備え、前記乱数発生部は、前記第1の乱数を発生して前記ランダム化数生成部に入力し、前記ランダム化数生成部は、前記第1の乱数が素数のとき、前記第1の乱数を前記ランダム化数として生成する、半導体装置。請求項2記載の半導体装置であって、ランダム化数生成部をさらに備え、前記乱数発生部は、所定値L以下の第2の乱数を発生して、前記ランダム化数発生部に入力し、前記ランダム化数生成部は、前記第2の乱数が前記条件1乃至3のすべてを満たすとき、前記第2の乱数を前記ランダム化数として生成するものであって、条件1は、前記第2の乱数が所定値Aより小さい素数を因数に持たないことであり、条件2は、前記所定値Aを底とし、前記第2の乱数から1を減じた数を指数とし、前記第2の乱数を法としたべき剰余演算の結果が1であることであり、条件3は、前記第2の乱数と、前記所定値L以下の整数であって、前記所定値Aを底とし前記整数から1を減じた数を指数とし前記整数を法としたべき剰余演算の結果が1であるが素数ではない整数のすべてと前記第2の乱数と比較して、前記第2の乱数がそのいずれとも異なるものであることである、半導体装置。請求項2記載の半導体装置であって、前記素数候補が少なくとも1個の素数で割り切れるか否かの判定を行い、前記判定結果が割り切れる場合には次の素数候補を生成し、前記判定結果が割り切れない場合には、前記素数候補を前記法生成部と前記指数生成部に出力する、半導体装置。乱数発生部とランダム化数生成部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、前記乱数発生部は、1個以上の第4の乱数列を発生し、前記ランダム化数生成部は、前記第4の乱数列に基づいて算出される整数を指数とする素因数演算によりランダム化数を生成し、前記法生成部は、前記素数候補と前記ランダム化数との積である第1整数を生成し、前記指数生成部は、第2整数を生成し、前記べき剰余演算部は、前記第1整数を法とし、前記第2整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、半導体装置。請求項6記載の半導体装置であって、前記乱数発生部は、値が1以上k以下の乱数を指数指定乱数として出力し、前記ランダム化数生成部は、k個の互いに相違する素数を格納するk個の要素からなる第1の配列と前記素数のそれぞれに対応する指数を格納するk個の要素からなる第2の配列とを備え、前記指数指定乱数によって指定された回数を前記第2の配列の要素の値とし、前記第1の配列の各要素の値である素数に、前記第2の配列の対応する要素の値を指数とするべき乗演算によりk個の整数を算出し、前記k個の整数の積を算出して前記ランダム化数として出力する、半導体装置。請求項6記載の半導体装置であって、べき剰余演算の底を、前記ランダム化数と前記素数候補の積と互いに素の整数とする、半導体装置。乱数発生部と法生成部と指数生成部とべき剰余演算部と判定部を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、前記乱数発生部は、第5の乱数をランダム化数として生成し、前記法生成部は、前記素数候補と前記ランダム化数との積を第1整数として生成し、前記指数生成部は、前記ランダム化数から1を減じた数と前記第1の素数候補から1を減じた数との積を素因数分解して、式r-1P-1=2sP’を満たす最大の整数s及び整数P’を算出し、前記整数P’を第2整数として生成し、前記べき剰余演算部は、前記第1整数を法とし、前記第2整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する、半導体装置。請求項9記載の半導体装置であって、前記乱数発生部により第6の乱数を発生し、前記第6の乱数は、前記ランダム化数で割り切れない数となるように選び、前記べき剰余演算部は、前記第6の乱数を底とし前記第1整数を法とし前記第2整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算の結果が、1またはrP-1または1PP-1modrr-2modrPまたはP-1PP-1modr2-PmodrPのいずれか1つと一致する場合、前記素数候補が素数であるという暫定判断をし、前記素数候補が素数であるという暫定判断が維持される限り、前記乱数発生部により第5の乱数を発生して新たなランダム化数rとし、第6の乱数を発生して新たな底Aとし、繰り返し回数が所定回数に達するまで繰り返すことにより素数性を判定する、半導体装置。請求項9記載の半導体装置であって、前記ランダム化数生成部をさらに備え、前記乱数発生部は、第5の乱数を発生して、前記ランダム化数生成部に入力し、前記ランダム化数生成部は、前記第5の乱数が、32ビットで且つ最下位2ビットがともに1であり、前記第5の乱数が、底を2とするミラーラビンテストと底を7とするミラーラビンテストと底を61とするミラーラビンテストとのすべてをパスするときに、前記第5の乱数を前記ランダム化数として生成する、半導体装置。べき剰余演算を含む素数性判定を行う半導体装置において、素数候補と乱数の積を前記べき剰余演算の法とする、半導体装置。請求項12記載の半導体装置において、前記素数候補と前記乱数に基づいて算出した値を前記べき剰余演算の指数とする、半導体装置。請求項1記載の半導体装置であって、前記素数性判定を伴って2個の素数を生成し、前記2個の素数に基づいて公開鍵および秘密鍵を出力するRSA暗号鍵生成を行う、半導体装置。請求項1記載の半導体装置を含むICカードであって、CPUとコプロセッサと乱数発生回路とメモリとを備え、前記コプロセッサは前記べき剰余演算を実行し、前記乱数発生回路は、前記乱数発生部を構成し、もしくはこれに基礎となる乱数を供給する、ICカード。請求項15記載のICカードであって、前記メモリに、RSA鍵生成プログラムおよびまたは素数テーブルが格納されている、ICカード。請求項1記載の半導体装置を含むICカードであって、トランザクションに先立って、前記素数性判定を伴って秘密鍵と公開鍵を生成し、前記公開鍵を、ICカード端末を介して接続されている鍵サーバーに送信する、ICカード。特許文献1において開示されている発明は、フォールトアタックによる素数生成の出力の撹乱を検出するため予備証拠整数を利用する。しかしながら、本特許文献では素数性判定の漏えい問題については取り扱っていない。非特許文献2には、指数のランダム化が行われるミラーラビン素数性判定法の変形が開示されている。べき剰余の指数がランダム化されているので、べき剰余の際の消費電力が攪乱されて素数の漏えいの危険性は低くなるが、法がランダム化されていないため、漏えいを完全に防ぐことはできない。法をランダム化することは、べき乗の結果、即ち素数性判定の結果に影響を与えるので簡単なことではない。このことは、下式のフェルマテストについて考えてみると容易に理解できる。数2AP11modPここで、AP11modPは、べき剰余AP1modPの結果が1であることを示す式で、当業者において汎用されている表現形式である。指数P1に任意の乱数rを乗じてランダム化した場合、ランダム化された指数でのべき乗の結果は変化せず、数3Ar1modPである。一方、任意の乱数sを使ってランダム化された法sPの場合、一般に、数4AP1≠1modsP数5Ar≠1modsPである。素数候補Pが素数であっても、乱数sとの積sPは素数でないため、フェルマテストによりPの素数性を判定することができない。本発明の目的は、素数性判定を行う半導体装置において、べき剰余の法をランダム化し、素数の漏えいを防止することである。本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。すなわち、べき剰余演算を含む素数性判定を行う半導体装置において、素数候補と乱数の積を前記べき剰余演算の法とする。本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。すなわち、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。1.実施の形態の概要先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。1<べき剰余における法をランダム化上位概念>乱数発生部1と法生成部2と指数生成部3とべき剰余演算部4と判定部5とを含んで構成され、入力された素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。前記乱数発生部は、第1の乱数を発生してランダム化数rとして生成し、前記法生成部は前記素数候補と前記ランダム化数とに基づいて第1整数R1を生成し、前記指数生成部は第2整数R2を生成する。前記べき剰余演算部は、前記第1整数を法とし前記第2整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する。これにより、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。2<指数と法をランダム化したフェルマテスト実施形態1>乱数発生部1と法生成部2と指数生成部3とべき剰余演算部4と判定部5とを含んで構成され、入力された素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。前記乱数発生部は、第1の乱数を発生してランダム化数rとして生成し、前記法生成部は前記素数候補と前記ランダム化数の積rPを第1整数R1として生成し、前記指数生成部は前記素数候補から1を減じた数と前記ランダム化数から1を減じた数との積を第2整数R2として生成する。前記べき剰余演算部は、前記第1整数を法とし前記第2整数を指数とするべき剰余演算を実行し、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する。これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。3<小さい素数によるランダム化>項2の半導体装置であって、ランダム化数生成部6をさらに備え、前記乱数発生部は、第1の乱数を発生して前記ランダム化数生成部に入力し、前記ランダム化数生成部は、前記第1の乱数が素数のとき、前記第1の乱数を前記ランダム化数として生成する。これにより、素数性判定における偽陰性と偽陽性の過誤が発生する確率を下げることができ、判定の効率を向上することができる。偽陰性の過誤とは、素数候補が素数であるにも関わらず素数ではないと判定する過誤を指し、偽陽性の過誤とは、素数候補が素数ではないにも関わらず素数と判定する過誤を指す。過誤の発生確率を下げる原理については、実施形態2において詳述する。4<小さい素数所定値L以下の素数の算出方法>項2の半導体装置であって、ランダム化数生成部6をさらに備え、前記乱数発生部は、第2の乱数を発生して前記ランダム化数生成部に入力し、前記ランダム化数生成部は、前記ランダム化数を以下の方法で算出する。前記乱数発生部1により、所定値L以下の第2の乱数を発生し401、前記ランダム化数生成部6は、前記第2の乱数が下記条件1乃至3のすべてを満たすとき、前記第2の乱数を前記ランダム化数として生成する。条件1:前記第2の乱数が所定値Aより小さい素数を因数に持たないこと411~415。条件2:前記所定値Aを底とし、前記第2の乱数から1を減じた数を指数とし、前記第2の乱数を法としたべき剰余演算の結果が1であること421,422。条件3:前記第2の乱数と、前記所定値L以下の整数であって、前記所定値Aを底とし前記整数から1を減じた数を指数とし前記整数を法としたべき剰余演算の結果が1であるが素数ではない整数のすべてと前記第2の乱数と比較して、前記第2の乱数がそのいずれとも異なるものであること431~436。これにより、ランダム化数に適する素数を簡易な方法で算出することができ、ICカードなどのローエンドデバイスにも実装することができる。5<素数候補の篩分け>項2、3、または4の半導体装置であって、前記素数候補Pが少なくとも1個の素数で割り切れるか否かの判定を行う。前記判定結果が割り切れる場合には次の素数候補を生成する。前記判定結果が割り切れない場合には、前記歩数候補を、前記法生成部2と前記指数生成部3に入力する。これにより、素数候補Pが素数でないことが簡単にわかる場合には、べき剰余演算に至る前にフェイルの判定素数候補Pが素数ではない旨の判定を出力して次の素数候補に進むことができるので、一連の素数性判定において、演算負荷の大きいべき剰余演算の実行回数を減らすことができる。6<素因数分解の指数を乱数として乱数を生成するフェルマテスト実施形態2>乱数発生部1とランダム化数生成部6と法生成部2と指数生成部3とべき剰余演算部4と判定部5を含んで構成され、入力される素数候補の素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。前記乱数発生部は、1個以上の第4の乱数列j1j2j3を発生し722、前記ランダム化数生成部は、前記第4の乱数列に基づいて算出される整数tjを指数とする素因数演算によりランダム化数を生成する724、725。前記法生成部は、前記素数候補と前記ランダム化数との積である第1整数R1を生成し741、前記指数生成部は、第2整数R2を生成する742。前記べき剰余演算部は、前記第1整数を法とし、前記第2整数を指数とするべき剰余演算を実行し745、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する750。これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止され、また、ランダム化するためのランダム化数は、素数に限定されない。7<素数テーブルの利用;ランダム化数Πrtj1≦j≦k>項6の半導体装置であって、各構成要素は以下の動作を行う。前記乱数発生部1は、値が1以上k以下の乱数jを指数指定乱数として出力する722。前記ランダム化数生成部6は、k個の互いに相違する素数を格納するk個の要素からなる第1の配列rkと前記素数のそれぞれに対応する指数を格納するk個の要素からなる第2の配列tkとを備え、前記指数指定乱数によって指定された回数を前記第2の配列の要素の値とする726。前記第1の配列の各要素の値である素数に、前記第2の配列の対応する要素の値を指数とするべき乗演算によりk個の整数を算出し、前記k個の整数の積を算出して前記ランダム化数として出力する。これにより、ランダム化数の別の生成方法を提供する。8<底はランダム化数×素数候補と互いに素>項6の半導体装置であって、べき剰余演算の底を、前記ランダム化数と前記素数候補の積と互いに素の整数とする744。これにより、偽陰性の過誤が発生する確率を下げ、素数性判定の効率を向上することができる。9<ミラーラビン素数判定法における法のランダム化>乱数発生部1と法生成部2と指数生成部3とべき剰余演算部4と判定部5を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。前記乱数発生部は、第5の乱数をランダム化数rとして生成する。前記法生成部は、前記素数候補と前記ランダム化数との積を第1整数として生成する821。前記指数生成部は、前記ランダム化数から1を減じた数と前記第1の素数候補から1を減じた数との積を素因数分解して、式2sPを満たす最大の整数s及び整数Pを算出し、前記整数Pを第2整数として生成する824、825。前記べき剰余演算部は、前記第1整数を法とし、前記第2整数を指数とするべき剰余演算を実行し841、前記判定部は、前記べき剰余演算部の出力に基づいて前記素数候補の素数性を判定する842。これにより、ミラーラビンテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。10<底を変えながらべき剰余を繰り返すループ>項9の半導体装置であって、各構成要素は以下の動作を行う。前記乱数発生部により第6の乱数を発生し834、前記第6の乱数Aが、前記ランダム化数rで割り切れない数となるように選ぶ835。前記べき剰余演算部は、前記第6の乱数を底とし前記第1整数を法とし前記第2整数を指数とするべき剰余演算を実行する。前記判定部は、前記べき剰余演算841の結果が、1またはrP1または1PmodrPまたはP1PmodrPのいずれか1つと一致する場合842、前記素数候補が素数であるという暫定判断を行う。前記素数候補が素数であるという暫定判断が維持される限り、前記乱数発生部により第5の乱数を発生して新たなランダム化数rとし、第6の乱数を発生して新たな底Aとし、繰り返し回数が所定回数に達するまで802繰り返すことにより素数性を判定する。これにより、ミラーラビンテストにおけるべき剰余演算の法と指数がともにランダム化される。11<小さい素数を生成する前処理>項9または10の半導体装置であって、ランダム化数生成部6をさらに備え、前記ランダム化数生成部は、以下の条件を満たすときに、前記第5の乱数を前記ランダム化数として生成する。条件1:前記第5の乱数は、32ビットで且つ最下位2ビットがともに1であること811。条件2:前記第5の乱数rは、底を2とするミラーラビンテスト812と底を7とするミラーラビンテスト814と底を61とするミラーラビンテスト816とのすべてをパスする810こと。これにより、ミラーラビンテストにおけるべき剰余演算の法と指数がともにランダム化され、そのランダム化数として素数が与えられる。12<べき剰余における法をランダム化。アルゴリズムの核心最上位概念>べき剰余演算を含む素数性判定を行う半導体装置において、素数候補Pと乱数rの積rPを前記べき剰余演算の法とする半導体装置である。これにより、べき剰余演算における法がランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。13<べき剰余における法および指数をランダム化>項12の半導体装置において、前記素数候補と前記乱数に基づいて算出した値を前記べき剰余演算の指数とする。これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。14<RSA暗号鍵の生成>項1乃至13のいずれかの半導体装置であって、前記素数性判定を伴って2個の素数PQを生成し、前記2個の素数に基づいて公開鍵および秘密鍵を出力するRSA暗号鍵生成を行う391、392、691、692。これにより、RSA暗号鍵公開鍵および秘密鍵が、サイドチャネル解析などの攻撃から防御される。15<ICカードのハードウェア>項1乃至13のいずれかの半導体装置を含むICカード100であって、CPU101とコプロセッサ102と乱数発生回路103とメモリ105、106とを備える。前記コプロセッサは前記べき剰余演算を実行し、前記乱数発生回路は、前記乱数発生部1を構成し、もしくはこれに基礎となる乱数を供給する。これにより、RSA暗号鍵公開鍵および秘密鍵が、サイドチャネル解析などの攻撃から防御されたICカードを提供することができる。16<ICカードのメモリ>項15のICカードであって、前記メモリ106に、RSA鍵生成プログラム124、524およびまたは素数テーブル534が格納されている。これにより、RSA暗号鍵公開鍵および秘密鍵が、サイドチャネル解析などの攻撃から防御されたICカードを提供することができる。17<ICカードにおける鍵エンロール>項1乃至13のうちいずれかの半導体装置を含むICカードであって、トランザクションに先立って、前記素数性判定を伴って秘密鍵と公開鍵を生成し201、前記公開鍵を、ICカード端末を介して接続されている鍵サーバーに送信する202。これにより、サイドチャネル解析などの攻撃から防御されたICカードを提供することができ、それを使ったトランザクションを提供することができる。2.実施の形態の詳細実施の形態について更に詳述する。実施形態1<べき剰余における法をランダム化>図1は、本発明の一実施形態に係る半導体装置のブロック図である。乱数発生部1と法生成部2と指数生成部3とべき剰余演算部4と判定部5を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。乱数発生部1は、第1の乱数を発生してランダム化数rとして生成し法生成部2と指数生成部3に入力する。法生成部2は素数候補Pとランダム化数rとに基づいて第1整数R1を生成し、指数生成部3は第2整数R2を生成する。べき剰余演算部4は、第1整数R1を法とし、第2整数R2を指数とするべき剰余演算を実行し、判定部5は、べき剰余演算部4の出力に基づいて素数候補Pの素数性を判定する。これにより、べき剰余演算における法R1は、ランダム化数rに基づいて算出されランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補Pの値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。ここで、第1整数R1は、代表的には素数候補Pとランダム化数rの積rPである。第2整数R2は、べき剰余演算における法をランダム化するのに伴って、素数候補Pが素数のときに当該べき剰余演算の結果が1または他の特定値となるように、算出される。素数を法としたときにはべき剰余演算の結果は1であることが数学的に保証されているのに対し、ただ単にべき剰余の法をランダム化した場合には、ランダム化された法の値が素数である場合にべき剰余の演算結果が1になるにとどまり、素数候補Pが素数のときのべき剰余の演算結果が予測できない。本発明においては、法をランダム化しそれに適する指数を与えることによって、べき剰余の演算結果が素数候補Pに基づいて予測可能な特定値となるようにするものである。実施形態2<指数と法をランダム化したフェルマテスト>図1は、本発明の一実施形態に係る半導体装置のブロック図であり、図6は、その動作例を表すフローチャートである。図6は、ステップ400の小さい素数を生成するランダム化向け整数生成とステップ440のフェルマテストの2つの部分を含む。まず、フェルマテストステップ440について説明する。乱数発生部1と法生成部2と指数生成部3とべき剰余演算部4と判定部5を含んで構成され、入力される素数候補Pの素数性判定を行う半導体装置であって、各構成要素は以下の動作を行う。乱数発生部1は、第1の乱数を発生してランダム化数rとして生成し、法生成部2は素数候補Pとランダム化数rの積rPを第1整数R1として生成しステップ441、指数生成部3は素数候補Pから1を減じた数とランダム化数rから1を減じた数との積を第2整数R2として生成するステップ442。べき剰余演算部4は、第1整数R1を法とし、第2整数R2を指数とし、1より大きくrPより小さい乱数Aを底としてステップ443、下式の剰余演算を実行するステップ445。数6AmodrP判定部5は、素数候補の素数性を判定する。より具体的には、べき剰余演算部の演算結果が、1のときはパスを出力し、1以外のときはフェイルを出力するステップ450。これにより、フェルマテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。ここで、底Aは1より大きくrPより小さい乱数から任意に選ぶことができるが、底Aをランダム化数rの倍数以外の整数とすることによりステップ444、判定が偽陰性の過誤となる確率をより下げることができる。その理由は後述する。ここまで述べてきた、指数と法をランダム化したフェルマテストの原理を説明する。ランダム化数rが素数でありPも素数であると仮定した場合、数7φである。ここで、φはオイラー関数である。下記数8を満たす任意の整数A10の場合、つまり素数rjがランダム化数r1の素因数の中に存在する場合は、r1にrjを乗じて新たなr1とし、r2にはrjを乗じて新たなr2として、それぞれ更新するステップ725。いずれの場合も、tjを1インクリメントするステップ726。上記ステップ722から726で構成されるループを、r1のビット長が所定の長さ図9の例では64ビットを超えるまで、繰り返す。r1のビット長が64ビットを超えると、ステップ740においてフェルマテストが行われる。べき剰余の法r1は、素数候補Pにr1を乗じて算出されるステップ741。べき剰余の指数r2は、P1にr2を乗じて算出されるステップ742。ランダム化数r1とr2は、いずれも乱数jに基づいて算出されたものであるので、乱数である。べき剰余の法R1および指数R2は、それぞれ乱数であるランダム化数r1およびr2を乗じて算出されるので、いずれもランダム化される。次に、べき剰余の底Aが乱数として生成されステップ743、R1との最大公約数が1であるかを判定されるステップ744。R1との最大公約数が1でなければ、新たな底Aが生成されるステップ743、AとR1との最大公約数が1AとR1が互いに素であれば、下式のべき剰余演算が実行されるステップ745。数15TAR2modR1べき剰余演算の結果T1の場合パスと判定され、T≠1の場合はフェイルと判定されるステップ750。ここまで述べてきた、指数と法をランダム化したフェルマテストの原理を説明する。一般に、GCD1を満たす任意の整数a,bについて、オイラー関数は以下の性質を持つ。数16φφφここで、φはオイラー関数であり、GCDは整数aと整数bの最大公約数を求める関数である。rjが素数であり、tjが1以上の整数であるとき、数17φrjtj1である。GCD1となるような任意の整数Aの場合、オイラーの定理による等式数1が成立するので、数18Aφ1modR1となる。その結果、素数候補Pが素数であるときには、rjが素数であるので、下式の関係が導かれる。数19φφφφφφr1t11r2t21rktk1R2したがって、素数候補Pが素数であれば、GCD1であるので、数20AR2Aφ1modR1が成立する。以上の原理により、R1、R2のようにべき剰余の指数と法の双方のランダム化を行っても、素数候補Pの素数性判定を行うことができる。上記のように、この原理は、フェルマテストと等価であることが数学的に上記原理で説明した通り証明されており、ランダム化によって偽陰性の過誤が発生する確率を増加させることはなく、フェルマテストと同等の信頼性が保たれている。本実施形態で開示されている発明の範囲は特定のフェルマテストに限ったものではなく、ミラーラビンテストやソロベイストラッセンテストなどの別の素数性判定にまで容易に及ぶ。ランダム化数R1とR2の生成例を以下に示す。この例では、小さい素数のテーブルを下式のように仮定する。即ち、k5である。数21r13r25r37r411r513初めに、R1とR2を1に初期化し、t1t2t3t4t50に初期化する。図9においては、R1が64ビットを繰り返すアルゴリズムであるとして説明したが、簡略化のため、R1が16ビットを超えたときに繰り返しを打ち切るものとして説明する。図12に、このアルゴリズムによるランダム化数の生成過程を数値例とともに示す。アルゴリズムでは、jに1以上5以下の乱数を与え、R1にrjを乗じ、R2にはrj1またはrjを乗じ、tjを更新する。R1317625となった時点で、R1が16ビットを超えたので、ループを抜け、R1317625とR2132000が出力される。この時点でのtiは下式である。数22t11t23t31t42t50これは、ランダム化数R1が数14によって以下のように計算されたことを意味する。数23R1r1t1r2t2r3t3r4t4r5t5315371112130317625同様に、ランダム化数R2は、以下のように計算されたことになる。数24R2r1t11×r2t21×r3t31×r4t41×r5t5130×52×70×111132000実施形態3のハードウェア構成例図7は、本実施形態に係る半導体装置の一例であるICカード、およびそのICカードが利用されるシステムを例示したブロック図である。実施形態2のハードウェア構成例と比較して、不揮発性メモリ106に格納されているRSA暗号鍵生成プログラム524が異なり、プログラムに最大公約数を算出するGCDプログラム525が、またデータに小さい素数のテーブルr1rk534が、それぞれ追加されている点が異なる。乱数jは、乱数発生器RNG103の出力する乱数に基づいて、1~kの範囲に入るように変換するなどして生成することができる。テーブルtiは、アルゴリズムを実行する上での中間値としてRAM105に格納することができる。べき乗の演算は、コプロセッサによって高速化してもよいし、CPUによる繰り返し演算で実現してもよい。実施形態3のハードウェア構成例は、他の部分は実施形態2のハードウェア構成例図3で示したのと同じであり、同様の機能を実現することができ、RSAトランザクションの例図4も同様に実現することができることは、明らかである。実施形態4<ランダム化されたミラーラビンテストによるRSA暗号鍵生成>フェルマテストと同様に、ミラーラビンテストも確率的素数性判定法である。フェルマテストでパスと判定された整数が必ずしも素数ではないという点において、フェルマテストは確率論的な素数性判定である。Pが素数ではないPは合成数である場合でも、AP11modPとなるようなフェルマライアーと呼ばれる整数Aがある。さらに悪いことには、カーマイケル数と呼ばれる合成数Pの場合、Pより小さい素数の大部分はフェルマライアーである。ミラーラビンテストはフェルマテストと同じくよく知られた素数性判定であり、以下の事実が成立する。Pが素数であるとき、任意の底Aの場合、Pはミラーラビンテストをパスすることができる。Pが素数でないとき、ミラーラビンテストをパスするPより小さい整数Aの数はP4より少ない。ミラーラビンテストが乱数の底Aでj回繰り返される場合、Pは合成数であるがミラーラビンテストをj回通過することができる確率はたかだか14j回である。例えば、もしミラーラビンテストが25回繰り返された場合、合成数Pがミラーラビンテストを通過する確率は250より小さい。しかしながら、素数は比較的稀なものであるため、エラーの確率を減少させるためにミラーラビンテストが何度も繰り返された場合、多くのべき乗が行われる。また、それらのべき乗の指数や法は多くのビットを共有しているため全て同様なものとなる。結果として、漏えい攻撃はインクリメンタルな調査によって生成された素数をミラーラビンテストにより再現することができると予想される。本実施形態4はミラーラビンテストの法と指数の両方をランダム化することによりこの問題に対処している。図10と図11は、実施形態4に係るランダム化されたミラーラビンテストのフローチャートである。ランダム化されたミラーラビンテストは、ステップ810の小さい素数生成図10と、ステップ820のミラーラビンテスト図11の2つの部分に区別することができる。ステップ810と820は25回繰り返される。25回の繰り返しが成功した場合、判定をパスする。ステップ810における小さい素数の生成は最下位2ビットが1の32ビットの小さい素数rを生成する。言い換えると、r2r1であり、rは奇数である。ステップ811において、32ビットの奇数の乱数rが生成され、その最下位から2番目のビットが1に設定される。ステップ812、814、816において、底2、7、61を使用したミラーラビンテストで乱数rの素数性判定が行われる。ミラーラビンテストの詳細は簡略のために割愛する。底2、7、61のミラーラビンテストをパスすることができる32ビットの合成数はないため、rが判定をパスした場合、素数であることが保証される。判定がフェイルとなった場合、ステップ811において新しい乱数が生成される。これにより、小さい素数がランダム化数rとして生成され、ミラーラビンテストステップ820に送られる。ステップ820はランダム化されたミラーラビンテストであり、ステップ821において法R1rPが計算される。ステップ822において指数R2が計算され、R2はステップ824において奇数になるまで繰り返し2で割られる。割られた回数sを保持する。次に、以下の数値を算出する。数25Ir2modrP1modrステップ831数26B1PImodR1ステップ832数27CP1PImodR1ステップ833BとCは、ミラーラビンテストの判定に用いるための補助値である。ステップ834において乱数の底Aが生成され、ステップ835においてその底がランダム化数rで割り切れるかどうかを確認する。次に、ステップ841において奇数のランダム化された指数R2とランダム化された法R1でべき剰余TAR2modR1が計算される。べき剰余Tの結果が1、または補助値BもしくはC、またはR11と等しい場合、ミラーラビンテストの次の繰り返しは新しいランダム化数rと新しい底Aで行われる。そうでない場合は、以下のステップがs1回繰り返される。ステップ844においてTはT2modR1で更新され、ステップ845において補助値Cと比較される。TがCと等しい場合、ミラーラビンテストの次の繰り返しは新しいランダム化数rと新しい底Aで行われる。全ての繰り返しを通して、Tが一度もCと等しくなかった場合、ミラーラビンテストは不合格となり、整数Pは素数ではないと判定される。以上をランダム化数と底Aを乱数によって変化させながら行う25回の繰り返しのうち、1度もフェイル判定に至らなかった場合に、パスの判定を行うステップ802。これにより、ミラーラビンテストにおけるべき剰余演算の法と指数がともにランダム化されるので、べき剰余演算を実行するための半導体装置の消費電力は素数候補の値と無関係になり、その結果、素数性判定時の素数の漏えいが防止される。ここまで述べてきた、指数と法をランダム化したミラーラビンテストの原理を、従来のミラーラビンテストとの違いを中心にを説明する。まず、従来のミラーラビンテストについて簡単に説明する。従来のミラーラビンテストでは、素数候補Pが与えられたとき、P1を、結果が奇数になるまで繰り返し2で除算し、繰り返し回数sおよび奇数Pを得る。その結果、下式の関係を満たす。数28P12sP次に、1APを満たす乱数Aが生成され、素数性判定のため、下式のべき剰余が演算される。数29TAPmodPその結果Tが、1またはP1と等しければパスと判定し、いずれとも等しくない場合には、さらに、下式の2乗演算をs1回繰り返し、1度でも結果がP1に等しければ、パスと判定する。数30TT2modPさらに、上記数28から数30の一連の演算と判定を、rとAをランダムに変えながら所定回数行い、その過程がすべてパスになることをもって最終的に素数と判定することにより、信頼度を向上している。これに対し本実施形態では、素数候補Pが与えられたとき、ステップ824と825において、P1に代えてランダム化された指数を対象として、同様に繰り返し2で割り、sとR2を得ている。その結果、数28に対応する関係は、下式のようになる。数312sR2次に底Aを生成する。従来1APを満たす乱数をAとしたが、素数候補をランダム化するため、ステップ834において、1AR1を満たす乱数を底Aとして生成し、底Aがランダム化数rの倍数になっていないことを条件として付加するため、ステップ835を行っている。底Aがランダム化数rの倍数になっていないという条件は、rとPがともに素数の場合にはGCD1と等価であるから、フェルマテストの動作原理で説明したのと同様に、数9と同じ下式の関係を導くための前提条件である。数32AAφ1modR1本実施形態のべき剰余は、ミラーラビンテストのランダム化を目的としているので、ランダム化されたR2を指数とするものであるから、ステップ841および下式に示すように、べき剰余演算の指数と法が置き換えられている。数33TAR2modR1従来のミラーラビンテストでは、Tを1またはP1と比較したが、本実施形態ではR1rPのようにランダム化されているので、従来1またはP1の2通りだった期待値が4通りになる。その期待値を求める方法を説明する。中国の剰余定理を適用すると、Tamodr,TbmodPのとき、数34TbPP1modrmodrPである。結果として、Pが素数の場合には、ステップ841および数33のべき剰余の結果は、以下の4通りとなる。数35b1、a1の場合、T1数36b1、a1r1の場合、T1PmodrP補助数B数37b1P1、A1の場合、TP1PmodrP補助数C数38b1P1、A1r1の場合、TrP1R11なお、上記数学は法Nが規定された有限体であるので、1N1である。べき剰余の結果Tが上のいずれか1つと等しいときにはパスと判定し、いずれも満たさないときには次のステップに進む。次のステップは、従来のミラーラビンテストでは数30の2乗演算のs1回繰り返しに対応する。ステップ844における2乗演算数39TT2modR1をs1回繰り返すうちの1つの結果が少なくとも1回、数40TP1PmodR1補助数Cとなれば、パスと判定するステップ845。R1がランダム化されている点を除けば、従来のミラーラビンテストと同様である。本実施形態では、ステップ811において32ビット乱数の最下位から2ビット目を1としてランダム化数とすることにより、r2r1であることが保証されているので、ステップ845の最初の2乗演算の結果、aTmodr1となることがわかっている。したがって、ステップ845のとおりTはP1ではなく補助数Cと比較しなければならない。実施形態4のハードウェア構成例など本実施形態は、実施形態1~3に対して、素数性判定のアルゴリズムのみについて変更したものであるので、ハードウェア図3、相互関係図4、RSA暗号鍵生成プログラム図5はまったく同様である。以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。例えば、本発明に係るアルゴリズムを実行するハードウェアとして、CPUとコプロセッサと不揮発性メモリを搭載した半導体装置を例として説明したが、プログラムの供給方法は不揮発性メモリによる必要はなく、また、要求される速度性能が低ければ、べき剰余をはじめとする特殊な演算を高速化するコプロセッサを搭載する必要はない。また、本発明の適用例としてICカードを例示したが、暗号を利用する他のシステムに応用することは容易である。"