"秘密鍵をユークリッド除算による乱数と商と剰余によって表現したべき乗剰余演算を用いてRSA暗号処理を行うセキュリティシステムであって、RSA暗号処理に用いるべき乗剰余演算の法nのビット長の正の整数分の一のビット長を持つ乱数rで秘密鍵を除して商と剰余に分解し、分解した商をさらに前記乱数で除して商と剰余に分解する処理を行うことにより、秘密鍵を前記乱数rの2次以上の高次式として処理する、セキュリティシステム。秘密鍵を前記乱数rの2次以上の高次式として暗号文を平文に復号するべき乗剰余演算として、前記乱数rの最高次数に係る定数を、暗号文に対するべき指数としてべき乗剰余演算を行い、その演算結果の剰余に対して前記乱数rをべき指数とするべき乗演算値と、前記乱数rの次の低位次数に係る定数をべき指数とする前記暗号文に対するべき乗演算値との積に対する法nを用いたべき乗剰余演算を、前記乱数rの最低次数に係る定数を用いるまで順次繰り返す処理を行う、請求項1記載のセキュリティシステム。カード基板に前記RSA暗号処理を行うマイクロコンピュータを搭載してICカードを構成する、請求項2記載のセキュリティシステム。秘密鍵をユークリッド除算による乱数rと商Dと剰余とによって表現したべき乗剰余演算を用いてRSA暗号処理を行うセキュリティシステムであって、前記乱数rはRSA暗号処理に用いるべき乗剰余演算の法nのビット長の1kkは正の整数のビット長を持ち、前記RSA暗号処理において、前記乱数rで秘密鍵dを除して商と剰余に分解し、分解した商をさらに前記乱数で除して商と剰余に分解する処理を行うことにより、秘密鍵dを、ddkrkdk1rk1dk2rk2...d2r2d1rd0で示される前記乱数rのk次の高次式として処理する、セキュリティシステム。秘密鍵を前記乱数rのk次の高次式として暗号文を平文に復号するべき乗剰余演算において、前記乱数rのk次に係る定数を、暗号文に対するべき指数としてべき乗剰余演算Ccdkmodnを行い、その演算結果の剰余Cに対して前記乱数rをべき指数とするべき乗演算値Crと、前記乱数rの次の低位次数kiに係る定数dkiをべき指数とする前記暗号文cに対するべき乗演算値cdkiとの積に対する法nを用いたべき乗剰余演算Crcdkimodnを、前記乱数rの最低次数0に係る定数d0を用いるまで順次繰り返す処理を行って、前記暗号文cに対する平文mをm、mrcdk1rcdk2rrcd2rcd1rcd0として得る、請求項4記載のセキュリティシステム。秘密鍵をユークリッド除算による乱数と商と剰余によって表現したべき乗剰余演算を用いてRSA暗号処理を行うプログラム処理回路を有し、前記プログラム処理回路は、RSA暗号処理に用いるべき乗剰余演算の法nのビット長の正の整数分の一のビット長を持つ乱数rで秘密鍵を除して商と剰余に分解し、分解した商をさらに前記乱数で除して商と剰余に分解する処理を行うことにより、秘密鍵を前記乱数rの2次以上の高次式として処理する、マイクロコンピュータ。前記プログラム処理回路は、秘密鍵を前記乱数rの2次以上の高次式として暗号文を平文に復号するべき乗剰余演算として、前記乱数rの最高次数に係る定数を、暗号文に対するべき指数としてべき乗剰余演算を行い、その演算結果の剰余に対して前記乱数rをべき指数とするべき乗演算値と、前記乱数rの次の低位次数に係る定数をべき指数とする前記暗号文に対するべき乗演算値との積に対する法nを用いたべき乗剰余演算を、前記乱数rの最低次数に係る定数を用いるまで順次繰り返す処理を行う、請求項6記載のマイクロコンピュータ。前記プログラム処理回路が実行することによって前記RSA暗号処理を行うためのプログラムを格納する耐タンパー性能を備えたプログラムメモリ領域を有する、請求項7記載のマイクロコンピュータ。前記秘密鍵を格納する耐タンパー性能を備えた不揮発性メモリ領域を有する、請求項8記載のマイクロコンピュータ。前記プログラム処理回路として、中央処理装置と、前記中央処理装置の制御に基づいて演算を行うコプロセッサとを有し、前記コプロセッサは、ユークリッド除算を行うユークリッド除算部と、前記中央処理装置の制御に基づいてべき乗演算を行うべき乗演算部とを有する、請求項9記載のマイクロコンピュータ。本発明者は、秘密鍵をユークリッド除算式による乱数と商と剰余によって表現して演算する技術について検討した。これによれば、上記乱数rは上記法nのビットに応じて大きな数になる。例えば、法nが約2000ビットのとき、乱数rは約1000ビットになる。したがって、このような大きな整数のユークリッド除算の計算には非常に高いコストを要する。要するに、データ処理能力の高いプロセッサ若しくはアクセラレータが必要になる。ICカードに代表されるようなデータ処理能力に限りのある装置では、コプロセッサなどのアクセラレータを用いて実用的な速度でべき乗剰余乗算を行って剰余を出力することは可能であるが、そのようなハードウェアモジュールとしてのアクセラレータから直接、除数に大きな整数を用いてユークリッド除算を行うことは容易ではない。これについて特許文献2,3では考慮されていない。本発明の目的は、秘密鍵をユークリッド除算式による乱数と商と剰余によって表現したときのべき乗剰余演算の演算コストを低減することにある。本発明の前記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。すなわち、秘密鍵をユークリッド除算による乱数と商と剰余によって表現したべき乗剰余演算を用いてRSA暗号処理を行う。特に、RSA暗号処理に用いるべき乗剰余演算の法nのビット長の正の整数分の一のビット長を持つ乱数rで秘密鍵を除して商と剰余に分解し、分解した商をさらに前記乱数で除して商と剰余に分解する処理を行うことにより、秘密鍵を前記乱数rの2次以上の高次式として扱う。これにより、小さなビット長の乱数rを用いる演算か可能になる。また、秘密鍵を前記乱数rの2次以上の高次式として暗号文を平文に復号するべき乗剰余演算では、前記乱数rの各次数に係る定数毎に暗号文に対するべき指数としてべき乗剰余演算を順次階層的に行う。これにより、暗号文の復号に際して、前記乱数rの2次以上の高次式における各項に対応する演算が軽減される。本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。すなわち、秘密鍵をユークリッド除算式による乱数と商と剰余によって表現したべき乗剰余演算の演算コストを低減することができる。1.実施の形態の概要先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。1<秘密鍵を、商と剰余をパラメータとして持ち乱数rの2次以上の高次式に分解>本発明の代表的な実施の形態に係るセキュリティシステムは、秘密鍵をユークリッド除算による乱数と商と剰余によって表現したべき乗剰余演算を用いてRSA暗号処理を行うシステムである。特に、RSA暗号処理に用いるべき乗剰余演算の法nのビット長の正の整数分の一のビット長を持つ乱数rで秘密鍵を除して商と剰余に分解し、分解した商をさらに前記乱数で除して商と剰余に分解する処理を行うことにより、秘密鍵を前記乱数rの2次以上の高次式として処理するS13。これにより、小さなビット長の乱数rを用いる演算が可能になる。rの値はランダムであるから、rを用いたべき乗はランダム化され、電力解析による秘密鍵の漏洩防止に資することができる。特に、rを用いたべき乗は、法npqの因数p、qを知らなくてもランダム化することが可能である。また、rは法よりもk倍小さいため、rのサイズを自由に選択することが出来る。特にrのビット長が十分短い場合に、ユークリッド除算を効率的に計算することが出来る。例えば、rが16ビットの場合、多くのCPUアーキテクチャの命令セットで使用される、32ビットのユークリッド除算を連続して行うことにより、商と剰余を効率的に計算することが出来る。このような32ビットのユークリッド除算処理を専用ハードウェア回路へ実装する場合にはこれを低コストで実現することが可能である。2<乱数rの2次以上の高次式として扱われる秘密鍵を用いた復号処理>項1のセキュリティシステムは、秘密鍵を前記乱数rの2次以上の高次式として暗号文を平文に復号するべき乗剰余演算として、前記乱数rの最高次数に係る定数を、暗号文に対するべき指数としてべき乗剰余演算を行い、その演算結果の剰余に対して前記乱数rをべき指数とするべき乗演算値と、前記乱数rの次の低位次数に係る定数をべき指数とする前記暗号文に対するべき乗演算値との積に対する除数nを用いたべき乗剰余演算を、前記乱数rの最低次数に係る定数を用いるまで順次繰り返す処理を行うS14。これにより、暗号文の復号に際して、前記乱数rの2次以上の高次式における各項に対応する演算が軽減される。3<ICカード>項2のセキュリティシステムは、カード基板に前記RSA暗号処理を行うマイクロコンピュータ1を搭載してICカード10を構成する。CPUパワーが限られたICカードにおいても電力解析による秘密鍵の漏洩防止が保証される。4<秘密鍵を、商と剰余をパラメータとして持ち乱数rの2次以上の高次式に分解>本発明の更に具体的な実施の形態に係るセキュリティシステムは、秘密鍵をユークリッド除算による乱数rと商Dと剰余とによって表現したべき乗剰余演算を用いてRSA暗号処理を行うシステムである。特に、前記乱数rはRSA暗号処理に用いるべき乗剰余演算の法nのビット長の1kkは正の整数のビット長を持つ。前記RSA暗号処理において、前記乱数rで秘密鍵dを除して商と剰余に分解し、分解した商をさらに前記乱数で除して商と剰余に分解する処理を行うことにより、秘密鍵dを、ddkrkdk1rk1dk2rk2...d2r2d1rd0で示される前記乱数rのk次の高次式として処理するS13、図5。上記秘密鍵としてのべき指数dに関する高次式は、例えば以下の処理ステップで演算することができる。法nのビット長よりk倍小さいビット長の乱数rを生成する。D’dに設定する。Step0:ユークリッド除算D’rの商と剰余、Dとd0を計算する。D’Dに設定する。Step1:ユークリッド除算D’rの商と剰余、Dとd1を計算する。D’Dに設定する。Step2:ユークリッド除算D’rの商と剰余、Dとd2を計算する。D’Dに設定する。...Stepk2:ユークリッド除算D’rの商と剰余、Dとdk2を計算。D’Dに設定する。Stepk1:ユークリッド除算D’rの商と剰余、Dとdk1を計算。D’Dに設定する。Stepk:ユークリッド除算D’rの商と剰余、Dとdkを計算。D’Dに設定する。これにより、項1と同様の作用効果を得る。5<乱数rの2次以上の高次式として扱われる秘密鍵を用いた復号処理>項4のセキュリティシステムは更に、秘密鍵を前記乱数rのk次の高次式として暗号文を平文に復号するべき乗剰余演算において、前記乱数rのk次に係る定数を、暗号文に対するべき指数としてべき乗剰余演算Ccdkmodnを行い、その演算結果の剰余Cに対して前記乱数rをべき指数とするべき乗演算値Crと、前記乱数rの次の低位次数kiに係る定数dkiをべき指数とする前記暗号文cに対するべき乗演算値cdkiとの積に対する法nを用いたべき乗剰余演算Crcdkimodnを、前記乱数rの最低次数0に係る定数d0を用いるまで順次繰り返す処理を行って、前記暗号文cに対する平文mをm、mrcdk1rcdk2rrcd2rcd1rcd0として得るS14,図6、図7。上記べき乗剰余演算は、例えば以下の処理ステップで演算することができる。Stepk:べき乗Ccdkmodnを計算する。Stepk1:べき乗CCrcdk1modnを計算する。Stepk2:べき乗CCrcdk2modnを計算する。...Step2:べき乗CCrcd2modnを計算する。Step1:べき乗CCrcd1modnを計算する。Step0:べき乗mCrcd0modnを計算する。これにより、項2と同様の作用効果を得る。6<秘密鍵を、商と剰余をパラメータとして持ち乱数rの2次以上の高次式に分解>本発明の更に別の実施の形態に係るマイクロコンピュータ1は、秘密鍵をユークリッド除算による乱数と商と剰余によって表現したべき乗剰余演算を用いてRSA暗号処理を行うプログラム処理回路2,3を有する。前記プログラム処理回路は、RSA暗号処理に用いるべき乗剰余演算の法nのビット長の正の整数分の一のビット長を持つ乱数rで秘密鍵を除して商と剰余に分解し、分解した商をさらに前記乱数で除して商と剰余に分解する処理を行うことにより、秘密鍵を前記乱数rの2次以上の高次式として処理するS13。これによれば、項1と同様の作用効果を奏し、小さなビット長の乱数rを用いる演算が可能になる。7<乱数rの2次以上の高次式として扱われる秘密鍵を用いた復号処理>項6のマイクロコンピュータにおいて、前記プログラム処理回路は、秘密鍵を前記乱数rの2次以上の高次式として暗号文を平文に復号するべき乗剰余演算として、前記乱数rの最高次数に係る定数を、暗号文に対するべき指数としてべき乗剰余演算を行い、その演算結果の剰余に対して前記乱数rをべき指数とするべき乗演算値と、前記乱数rの次の低位次数に係る定数をべき指数とする前記暗号文に対するべき乗演算値との積に対する法nを用いたべき乗剰余演算を、前記乱数rの最低次数に係る定数を用いるまで順次繰り返す処理を行うS14。これによれば、項2と同様に作用効果を奏する。8<プログラムメモリ領域>項7のマイクロコンピュータにおいて、前記プログラム処理回路が実行することによって前記RSA暗号処理を行うためのプログラムを格納する耐タンパー性能を備えたプログラムメモリ領域6を有する。これによれば、上記RSA暗号処理を実現する環境を容易に実現することができる。9<秘密鍵を格納する不揮発性メモリ領域>項8のマイクロコンピュータにおいて、前記秘密鍵を格納する耐タンパー性能を備えた不揮発性メモリ領域4を有する。これによれば、秘密鍵に対する不正アクセス防止を更に万全とする事ができる。10<外部インタフェース回路>項9のマイクロコンピュータにおいて、前記プログラム処理回路として、中央処理装置2と、前記中央処理装置の制御に基づいて演算を行うコプロセッサ3とを有し、前記コプロセッサは、ユークリッド除算を行うユークリッド除算部31と、前記中央処理装置の制御に基づいてべき乗演算を行うべき乗演算部34とを有する。これにより、RSA暗号処理演算の高速化に資することができる。2.実施の形態の詳細実施の形態について更に詳述する。<電力解析に対して保護されていないRSA>先ず、電力解析に対して秘密鍵の漏洩防止が充分に対策されていない場合を一例としてRSA処理における剰余乗算処理の基本的なアルゴリズムを説明する。RSA暗号システムは、cを暗号化されたメッセージ、dを秘密鍵とするmcdmodn等のべき乗剰余演算を行う。結果mは復号されたメッセージを表す。図2にはバイナリ法によるべき乗剰余計算アルゴリズムが例示される。RSAのべき乗剰余演算は、通常は図2に示すバイナリ法により実装される。べき指数のビットを左から右にスキャンしS1、アキュムレータを2乗m2してステップS2の演算を行う。スキャンされたビットがゼロ以外のとき、底cとの乗算を計算しmcしてステップS3の演算を行う。このプロセスは、全ビットがスキャンされるまで繰り返される。しかし、アタッカによってべき乗の入力cを制御される可能性があり、アタッカがこの入力を十分な回数行い、それによって得られた消費電力を観察することにより、消費電力曲線におけるノイズの平均値が割り出され、秘密鍵が漏洩されてしまう可能性がある。このため、べき乗演算時に秘密鍵べき指数をランダム化することが重要となる。図3にはユークリッド除算によるランダム化べき乗処理の概略が例示される。ここでは、RSA暗号システムに適用可能な、ランダム化されたべき乗を計算するための既に提供されているソリューションの概要を示すものである。法の半分のサイズの乱数rを使って、べき指数を2つに分解する。すなわち、dd1rd0とするS4。数値d0、d1は、ユークリッド除算drの商と剰余を表す。ステップS4で求められたべき指数に対してステップS4及ぶステップS5の処理を行うことによって暗号文cが平文mに復号される。ステップS5,S6の処理におけるべき乗crmodn、Cd1modn、cd0modnの演算において、べき指数はランダムであり、そのビット数は元のべき指数dのサイズの半分である。また、Cd1modnとcd0modの2つのべき乗を、約1つ分のコストで、同時に計算することが出来る。これについては後述する。しかしながら、このアルゴリズムのべき乗部は、速度の面で大きく不利とはならないが、d1、d0の計算を効率的に行うことが出来ないため、実際には、処理時間全体に大きく影響する。以下、その処理時間を短縮もしくは演算コストを低減する構成について説明する。先ず、本発明の実施の形態でも利用する高速多重べき乗演算処理について説明する。ここで説明する高速多重べき乗演算処理は図3におけるステップS6の処理にも適用可能なものである。図4には高速多重べき乗演算処理として、2つのべき指数a、bによるべき乗、Cacbmodnを計算するためのアルゴリズムが例示される。単純な方式としては図1のバイナリ法を使ってCamodnとcbmodnを別々に計算するが、高速多重べき乗演算処理ではそれらのべき乗を同時に計算して効率化するものである。図4では、入力c、C、事前計算値cCmodnでテーブルを初期化しS7、2つのべき指数a、bの2進表記をスキャンするS8。べき乗のアキュムレータは2乗されてX2ステップS9の処理が行われるが、乗算工程S10、S11では、以下のa~dうちのいずれかが行われる。a2つのべき指数のビットがゼロのとき、乗算工程はスキップされ、次の反復に進む。baのべき指数のビットがゼロ以外で、bのべき指数のビットがゼロのとき、Cの乗算を計算する。caのべき指数のビットがゼロで、bのべき指数のビットがゼロ以外のとき、cの乗算を計算する。d2つのべき指数のビットがゼロ以外のとき、cCmodnの乗算を計算する。図4のアルゴリズムで必要となるのは、多くてg1回の2乗とg1回の乗算、また平均g1回の2乗と34回の乗算であり、2回の2乗とg1回の乗算に関する単純な方式と比べて演算コストは非常に有利となる。<電力解析に対して保護されたRSA>次に、電力解析に対して保護されたRSA暗号処理を実現するために、反復ユークリッド除算によるランダム化べき乗を採用した本発明の実施の形態について説明する。本発明の実施の形態において説明する、反復ユークリッド除算による高速ランダム化べき乗演算の特徴的な点は、d1、d0の2つの数値だけでなく、小さい数値diでより長い配列が得られるよう、ユークリッド除算を繰り返すことである。その結果、配列を長くすることで、ユークリッド除算に含まれるオペランドのビット長を短くすることが可能となり、これによって、より効率的にソフトウェアとハードウェアの実装を行うことが可能になる。図1には電力解析に対して保護されたRSA復号処理が全体的に例示される。先ず、暗号文c、秘密鍵d、法n、パラメータgtkを入力するS11。次にgビットの乱数rを生成するS12。gは法nの1kのビット数とされる。次に、dkdk1...d0の計算を行うS13。この計算手法の具体例については図5に基づいて後述することとする。ステップS13の計算は、前記乱数rで秘密鍵dを除して商と剰余に分解し、分解した商をさらに前記乱数で除して商と剰余に分解する処理を繰り返し行えばよい。例えば、D’dに設定して以下のステップを順次実行すればよい。Step0:ユークリッド除算D’rの商と剰余、Dとd0を計算する。D’Dに設定する。Step1:ユークリッド除算D’rの商と剰余、Dとd1を計算する。D’Dに設定する。Step2:ユークリッド除算D’rの商と剰余、Dとd2を計算する。D’Dに設定する。...Stepk2:ユークリッド除算D’rの商と剰余、Dとdk2を計算。D’Dに設定する。Stepk1:ユークリッド除算D’rの商と剰余、Dとdk1を計算。D’Dに設定する。Stepk:ユークリッド除算D’rの商と剰余、Dとdkを計算。D’Dに設定する。これによってべき指数としての秘密鍵dは、ddkrkdk1rk1dk2rk2...d2r2d1rd0となる。次に、mcdmodnの計算を行うS14。この計算手法の具体例については図7に基づいて後述することとする。ステップS14の計算は、前記乱数rのk次に係る定数を、暗号文に対するべき指数としてべき乗剰余演算Ccdkmodnを行い、その演算結果の剰余Cに対して前記乱数rをべき指数とするべき乗演算値Crと、前記乱数rの次の低位次数kiに係る定数dkiをべき指数とする前記暗号文cに対するべき乗演算値cdkiとの積に対する法nを用いたべき乗剰余演算Crcdkimodnを、前記乱数rの最低次数0に係る定数d0を用いるまで順次繰り返す処理を行えばよい。例えば、このべき乗剰余演算は以下の処理ステップで演算することができる。Stepk:Ccdkmodnを計算する。Stepk1:CCrcdk1modnを計算する。Stepk2:CCrcdk2modnを計算する。...Step2:CCrcd2modnを計算する。Step1:CCrcd1modnを計算する。Step0:mCrcd0modnを計算する。これにより、メッセージmとして、m、mrcdk1rcdk2rrcd2rcd1rcd0を得る。図1の処理を更に詳述する。図5には配列dk...d0の計算処理が例示される。この処理における中心的な演算は、ユークリッド除算D’rであり、商Dと、dirとなる剰余diを出力するS21。この計算処理においては、従来の計算方法と比べて、乱数rのビット長に対する選択自由度がより高いことに注目されたい。特に、rのビット長が短い場合、ユークリッド除算D’rに対し、次の図6に示すように、ハードウェアソフトウェア上で効率的に計算することが出来る。図6にはgビットの除数rによるD’のユークリッド除算処理、即ち図5のステップS21の処理が例示される。Dを最大でも2gビットとしたときの、最小単位のユークリッド除算Drに依存していることに注意する。gが十分小さい値の場合、このようなgビット除数による、2gビット整数のユークリッド除算の計算は簡単である。これは、例えばg16の場合、一般的には主流のCPUアーキテクチャによって直接サポートされる、16ビット除数rによる32ビット整数Dの除算に相当する。当然ながら、アーキテクチャによっては、gの値が異なる方が望ましい場合もある。図7にはランダム化べき指数によるcdmodnの計算処理が例示される。ここでは、べき乗cdmodnを計算するための、配列dk...d0の使用について示す。gビットのべき指数によるkのべき乗Crcdimodnが存在する。gビットのべき指数は、最大べき指数dよりk倍小さいため、これらのべき乗演算は、最大べき乗と比べて約k倍速くなる。このため、本実施の形態では、通常のRSAべき乗演算と同程度の速度でランダム化を行い、秘密鍵dの漏洩を防ぐことが出来る。べき乗Crcdimodnの計算可能な手法は図4に示されるとおりである。図8には上記ランダム化べき指数によるcdmodnの計算処理を採用したICカード用のマイクロコンピュータのハードウェア構成が例示される。同図に示されるICカード用のマイクロコンピュータ1はICカード10に適用される。ICカード用のマイクロコンピュータ1は、他の電子機器と通信するための外部入出力インタフェース部IO7や、EEPROMのような電気的に書き換え可能な不揮発性メモリ4から読み出されるデータdntgkと中間データを保存するためのRAM5を使って、ROM6に格納されたRSA復号プログラムなどのプログラムを実行する中央処理装置CPU2を備える。接触インタフェース型のICカード10の場合には図示を省略するカード基板の表面に形成された接触端子に外部入出力インタフェース部IO7が接続される。近接非接触通信を行うICカード10の場合には図示を省略するカード基板にアンテナが形成され、外部入出力インタフェース部IO7は近接非接触通信のためのアナログ高周波部を有し、このアナログ高周波部に前記アンテナが接続される。乱数rは乱数生成部RNG8で生成する。ICカード用のマイクロコンピュータ1の内部回路は内部バス9で相互に接続される。不揮発性メモリ4は耐タンパー性能を備える。不揮発性メモリの耐タンパー性とは、記憶情報の不正アクセスや回路の改変に対する防護力を意味する。耐タンパ性を高める技術として、例えばLSIを解析するために保護層をはがすと、内部の回路まで破壊されるようにする技術などがある。ICカード用のマイクロコンピュータ1は、CPU2で実行されるRSA暗号処理プログラムによって、暗号化されたメッセージを復号するために用いられる。復号には、演算コストの非常に高いべき乗演算が用いられる。このため、ICカード用のマイクロコンピュータ1は、プログラム処理回路としてCPU2のほかに、高速な復号を可能とするアクセラレータとしてのコプロセッサ3を搭載指定する。さらにICカード用のマイクロコンピュータ1は、EEPROM4に格納された、RSA復号プログラムで使用される秘密鍵を保護するために、上記ランダム化べき指数によるcdmodnの演算処理を必要とするため、コプロセッサ3は、ユークリッド除算部31を用いて図5で説明したプロセスを実行する配列計算部32と、高速多重べき乗演算部34を用いて図7のプロセスを実行するべき乗演算部33で構成される。図9にはICカード用のマイクロコンピュータ1によるRSA復号処理を行うハードウェア部とハードウェア部間のデータ通信について例示される。図9には示していないが、CPU2は復号プログラムを実行することで、ハードウェア部の処理とハードウェア部間のデータ通信に対する制御を行う。ICカード用のマイクロコンピュータ1は外部入出力インタフェース部7から暗号文cを受信する。復号の結果は、コプロセッサ3で計算されたメッセージmcdmodnである。また、暗号文cとともにコプロセッサ3に入力するデータには、EEPROM4に格納された秘密鍵d、dのビット長t、乱数のビット長g、ceilとするパラメータkと、RNG8で生成する乱数rがある。ceilはtgの小数点以下を繰り上げた整数値を返す関数である。コプロセッサ3は、図6のユークリッド除算を行うユークリッド除算部31と、図5のプロセスを実行する配列計算部32を使って、dk1...d0の配列を計算する。配列計算部32は、RNG8から得るgビットの乱数rを必要とする。その後、図6のプロセスを実行するユークリッド除算部を使って、秘密鍵dを乱数rで割るユークリッド除算の連続によりdiを計算する。dk...d0の配列を得た後、図7のプロセスを実行するべき乗演算部33は、cdmodnのべき乗剰余を計算する。具体的には、べき乗演算部はCCrcdimodnの計算をk回繰り返す。ここで、小さい指数rとdiのべき乗演算は、図4のプロセスを実行する高速多重べき乗演算部によって行われる。結果は復号化されたメッセージmcdmodnとなる。<RSA復号の具体例>次にRSA復号処理の具体例を説明する。RSA暗号化のための法nを53593127、公開指数eを17、RSA復号化のための秘密鍵dを2129とすると、べき乗演算cmemodn10002129mod31272931でメッセージm1000を暗号化できる。実際には、暗号文c2931の復号化はcdmodn29312129mod31271000となる。復号のランダム化と秘密鍵dの漏洩防止のため、上記実施の形態に示す方法を使用する。ここで、指数のビット長tを12ビット、乱数のビット長を4ビットとすると、kceil3となり、べき乗演算に使う配列は4つの4ビットd3d2d1d0となる。はじめに、配列の計算について説明する。4ビットの乱数rを生成し、例えば、r11の場合、最初はD’d2129となる。1931162129で、一番目の除算D’r212911の剰余は6、商は193となるため、D193、d06とする。二番目の除算D’r19311の剰余は6、商は17となるため、D17、d16とする。三番目の除算D’r1711の剰余は6、商は1となるため、d26、d31とする。この結果、配列が1666となる。実際には11136112611161102129となる。乱数が異なると、異なる配列が生成される。例えば、r12の場合、一番目の除算212912の剰余はd06で、商は177となる。二番目の除算17712の剰余はd19で、商は14となり、三番目の除算1411の剰余は2で、商は1となる。この結果、配列は1295となる。実際には11232122912151202129となる。乱数が4ビット、最上位ビットが1であることから、配列の組み合わせは8通りとなる。実際にはさらに大きな整数を使用するため、幾通りもの配列を実現し、低コストでの計算が可能となるような乱数のビット長を選ばなければならない。この点について16ビットの乱数は有利であるが、他の設定も可能である。例の残りの部分において、配列を1295、r12とする。d31であるため、CをCc1mod31272931で初期化する。一番目のべき乗演算では、図4の高速多重べき乗演算部を使ってCCrcd2modn29311229312mod3127を計算する。テーブルをT012931T102931とT1129312931mod3127892で初期化する。指数はa122、b22である。a31、b30であるため、T102931でアキュムレータを初期化する。次に、二乗算C2modn29312931mod3127892を計算する。a21、b20であるため、掛算CCT10modn8922931mod3127280を行う。次に、二乗算C2modn280280mod3127225を計算する。a10、b11であるため、掛算CCT01modn2252931mod31272805を行う。次に、二乗算C2modn28052805mod3127493を計算する。a00、b00であるため、掛算は行わない。一番目の多重べき乗演算の結果はC493となる。同様に、二番目の多重べき乗演算はCrcd1modn4931229319mod3127で、詳細を割愛すると、結果はC2109となる。最後の多重べき乗演算はCrcd0modn21091229315mod3127で、結果は、復号化されたメッセージC1000となる。以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。例えば、法n、乱数rなどのサイズは適宜決定すればよい。本発明はICカードに適用される場合だけに限定されるものではなく、携帯電話やPDAなどの携帯端末などにも広く適用することができる。本発明に持ちいれCPUは32ビットに限定されず、16ビット又は64ビットなどであってもよい。"