"基数を示す暗号データと指数を示す秘密鍵データと法を示す公開鍵データとを用いてべき乗剰余演算により復号データを求める暗号装置であって、素数データ各々に対応する指数を示す乱数設定データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して乗算データを求め、前記乗算データにより前記秘密鍵データを除算して求めた商を示す第1の鍵データと、前記乗算データにより前記秘密鍵データを除算して求めた余りを示す第2の鍵データと、を予め記憶する記憶部と、前記素数データ各々に対応する指数を示す、前記乱数設定データ以下でかつ正の整数である第1の乱数データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して第2の乱数データを求め、前記素数データ各々に対応する指数を示す、前記乱数設定データから前記乱数設定データに対応する前記第1の乱数データを減算した減算データ用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して耐タンパデータを求める乱数生成部と、前記第1の鍵データと前記耐タンパデータとを基数に用い、乗算剰余演算において扱える最大ビット幅長から1を減算したデータを法とし、乗算剰余演算をして第1の変数を求め、あるいは、前記第1の鍵データと前記耐タンパデータとの乗算をして第1の変数を求め、前記暗号データを基数とし、前記第2の乱数データを指数とし、公開鍵データを法とし、べき乗剰余演算をして第2の変数を求め、前記第2の変数を基数とし、前記第1の変数を指数とし、公開鍵データを法とし、べき乗剰余演算をして第3の変数を求め、前記暗号データを基数とし、前記第2の鍵データを指数とし、公開鍵データを法とし、べき乗剰余演算をして第4の変数を求め、前記第3の変数と前記第4の変数とを基数に用い、公開鍵データを法とし、乗算剰余演算をして復号データを求めるべき乗剰余演算部と、を備えることを特徴とする暗号装置。前記べき乗剰余演算部は、前記第1の鍵データと前記耐タンパデータを基数に用い、2のモンゴメリ乗算剰余演算において扱える最大ビット幅長乗から1を減算したデータを法とし、モンゴメリ乗算剰余演算をして第1の変数を求め、前記第3の変数と前記第4の変数を基数に用い、公開鍵データを法とし、モンゴメリ乗算剰余演算をして第5の変数を求め、前記第5の変数と前記モンゴメリパラメータの2乗を基数に用い、公開鍵データを法とし、モンゴメリ乗算剰余演算をして復号データを求める、ことを特徴とする請求項1に記載の暗号装置。暗号データと秘密鍵データと公開鍵データとを用いて点のスカラー倍算演算により復号データを求める暗号装置であって、素数データ各々に対応する指数を示す乱数設定データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して乗算データを求め、前記乗算データにより前記秘密鍵データを除算して求めた商を示す第1の鍵データと、前記乗算データにより前記秘密鍵データを除算して求めた余りを示す第2の鍵データと、を予め記憶する記憶部と、前記素数データ各々に対応する指数を示す、前記乱数設定データ以下でかつ正の整数である第1の乱数データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して第2の乱数データを求め、前記素数データ各々に対応する指数を示す、前記乱数設定データから前記乱数設定データに対応する前記第1の乱数データを減算した減算データを用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して耐タンパデータを求める乱数生成部と、前記第1の鍵データと前記耐タンパデータとを用いて乗算をして第1の変数を求める乗算部と、前記暗号データと前記第2の乱数データとを用いて点のスカラー倍算演算をして第2の変数を求め、前記第2の変数と前記第1の変数とを用いて点のスカラー倍算演算をして第3の変数を求め、前記暗号データと前記第2の鍵データとを用いて点のスカラー倍算演算をして第4の変数を求め、前記第3の変数と前記第4の変数とを用いて点の加算演算をして復号データを求める点のスカラー倍算演算部と、を備えることを特徴とする暗号装置。コンピュータによって実行される暗号処理方法であって、素数データ各々に対応する指数を示す乱数設定データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して乗算データを求め、前記乗算データにより前記秘密鍵データを除算して求めた商を示す第1の鍵データと、前記乗算データにより前記秘密鍵データを除算して求めた余りを示す第2の鍵データと、を予め記憶部に記憶し、前記素数データ各々に対応する指数を示す、前記乱数設定データ以下でかつ正の整数である第1の乱数データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して第2の乱数データを求め、前記素数データ各々に対応する指数を示す、前記乱数設定データから前記乱数設定データに対応する前記第1の乱数データを減算した減算データを用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して耐タンパデータを求め、前記第1の鍵データと前記耐タンパデータとを基数に用い、2の乗算剰余演算において扱える最大ビット幅長乗から1を減算したデータを法とし、乗算剰余演算をして第1の変数を求め、あるいは、前記第1の鍵データと前記耐タンパデータとを乗算して第1の変数を求め、前記暗号データを基数とし、前記第2の乱数データを指数とし、公開鍵データを法とし、べき乗剰余演算をして第2の変数を求め、前記第2の変数を基数とし、前記第1の変数を指数とし、公開鍵データを法とし、べき乗剰余演算をして第3の変数を求め、前記暗号データを基数とし、前記第2の鍵データを指数とし、公開鍵データを法とし、べき乗剰余演算をして第4の変数を求め、前記第3の変数と前記第4の変数とを基数に用い、公開鍵データを法とし、乗算剰余演算をして復号データを求める、ことを特徴とする処理方法。前記コンピュータが、前記第1の鍵データと前記耐タンパデータを基数に用い、2のモンゴメリ乗算剰余演算において扱える最大ビット幅長乗から1を減算したデータを法とし、モンゴメリ乗算剰余演算をして第1の変数を求め、前記第3の変数と前記第4の変数を基数に用い、公開鍵データを法とし、モンゴメリ乗算剰余演算をして第5の変数を求め、前記第5の変数と前記モンゴメリパラメータの2乗を基数に用い、公開鍵データを法とし、モンゴメリ乗算剰余演算をして復号データを求める、ことを特徴とする請求項4に記載の処理方法。コンピュータによって実行される暗号処理方法であって、素数データ各々に対応する指数を示す乱数設定データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して乗算データを求め、前記乗算データにより前記秘密鍵データを除算して求めた商を示す第1の鍵データと、前記乗算データにより前記秘密鍵データを除算して求めた余りを示す第2の鍵データと、を予め記憶部に記憶し、前記素数データ各々に対応する指数を示す、前記乱数設定データ以下でかつ正の整数である第1の乱数データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して第2の乱数データを求め、前記素数データ各々に対応する指数を示す、前記乱数設定データから前記乱数設定データに対応する前記第1の乱数データを減算した減算データを用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して耐タンパデータを求め、前記第1の鍵データと前記耐タンパデータとを用いて乗算をして第1の変数を求め、前記暗号データと前記第2の乱数データとを用いて点のスカラー倍算演算をして第2の変数を求め、前記第2の変数と前記第1の変数とを用いて点のスカラー倍算演算をして第3の変数を求め、前記暗号データと前記第2の鍵データとを用いて点のスカラー倍算演算をして第4の変数を求め、前記第3の変数と前記第4の変数とを用いて点の加算演算をして復号データを求める、ことを特徴とする処理方法。素数データ各々に対応する指数を示す乱数設定データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して乗算データを求め、前記乗算データにより前記秘密鍵データを除算して求めた商を示す第1の鍵データと、前記乗算データにより前記秘密鍵データを除算して求めた余りを示す第2の鍵データと、を予め記憶部に記憶し、前記素数データ各々に対応する指数を示す、前記乱数設定データ以下でかつ正の整数である第1の乱数データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して第2の乱数データを求め、前記素数データ各々に対応する指数を示す、前記乱数設定データから前記乱数設定データに対応する前記第1の乱数データを減算した減算データを用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して耐タンパデータを求め、前記第1の鍵データと前記耐タンパデータとを基数に用い、2の乗算剰余演算において扱える最大ビット幅長乗から1を減算したデータを法とし、乗算剰余演算をして第1の変数を求め、あるいは、前記第1の鍵データと前記耐タンパデータとの乗算を行って第1の変数を求め、前記暗号データを基数とし、前記第2の乱数データを指数とし、公開鍵データを法とし、べき乗剰余演算をして第2の変数を求め、前記第2の変数を基数とし、前記第1の変数を指数とし、公開鍵データを法とし、べき乗剰余演算をして第3の変数を求め、前記暗号データを基数とし、前記第2の鍵データを指数とし、公開鍵データを法とし、べき乗剰余演算をして第4の変数を求め、前記第3の変数と前記第4の変数とを基数に用い、公開鍵データを法とし、乗算剰余演算をして復号データを求める、処理をコンピュータが実行することを特徴とする暗号プログラム。前記第1の鍵データと前記耐タンパデータを基数に用い、2のモンゴメリ乗算剰余演算において扱える最大ビット幅長乗から1を減算したデータを法とし、モンゴメリ乗算剰余演算をして第1の変数を求め、前記第3の変数と前記第4の変数を基数に用い、公開鍵データを法とし、モンゴメリ乗算剰余演算をして第5の変数を求め、前記第5の変数と前記モンゴメリパラメータの2乗を基数に用い、公開鍵データを法とし、モンゴメリ乗算剰余演算をして復号データを求める、処理を前記コンピュータが実行することを特徴とする請求項7に記載の暗号プログラム。素数データ各々に対応する指数を示す乱数設定データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して乗算データを求め、前記乗算データにより前記秘密鍵データを除算して求めた商を示す第1の鍵データと、前記乗算データにより前記秘密鍵データを除算して求めた余りを示す第2の鍵データと、を予め記憶部に記憶し、前記素数データ各々に対応する指数を示す、前記乱数設定データ以下でかつ正の整数である第1の乱数データ各々を用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して第2の乱数データを求め、前記素数データ各々に対応する指数を示す、前記乱数設定データから前記乱数設定データに対応する前記第1の乱数データを減算した減算データを用いて、前記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して耐タンパデータを求め、前記第1の鍵データと前記耐タンパデータとを用いて乗算をして第1の変数を求め、前記暗号データと前記第2の乱数データとを用いて点のスカラー倍算演算をして第2の変数を求め、前記第2の変数と前記第1の変数とを用いて点のスカラー倍算演算をして第3の変数を求め、前記暗号データと前記第2の鍵データとを用いて点のスカラー倍算演算をして第4の変数を求め、前記第3の変数と前記第4の変数とを用いて点の加算演算をして復号データを求める、処理をコンピュータが実行することを特徴とする暗号プログラム。本発明は、電力差分解析を用いた秘密鍵の解読を困難にする回路を備えている場合でも、回路規模が大きくならないようにできる暗号装置を提供することを目的とする。また、電力差分解析を用いた秘密鍵の解読を困難にする処理を有する場合に、処理速度を向上させることができる暗号の方法およびプログラムを提供することを目的とする。本実施態様のひとつである基数を示す暗号データと指数を示す秘密鍵データと法を示す公開鍵データとを用いてべき乗剰余演算により復号データを求める暗号装置は、記憶部、乱数生成部、べき乗剰余演算部を備えている。記憶部は、素数データ各々に対応する指数を示す乱数設定データ各々を用いて、上記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して乗算データを求める。続いて、上記乗算データにより上記秘密鍵データを除算して求めた商を示す第1の鍵データと、上記乗算データにより上記秘密鍵データを除算して求めた余りを示す第2の鍵データと、を予め記憶部に記憶する。乱数生成部は、上記素数データ各々に対応する指数を示す、上記乱数設定データ以下でかつ正の整数である第1の乱数データ各々を用いて、上記素数データ各々に対してべき乗を求める。続いて、乱数生成部は求めたべき乗したデータ各々を乗算して第2の乱数データを求める。続いて、乱数生成部は上記素数データ各々に対応する指数を示す、上記乱数設定データから上記乱数設定データに対応する上記第1の乱数データを減算した減算データ用いて、上記素数データ各々に対してべき乗を求める。続いて、乱数生成部は求めたべき乗したデータ各々を乗算して耐タンパデータを求める。べき乗剰余演算部は、上記第1の鍵データと上記耐タンパデータとを基数に用い、乗算剰余演算において扱える最大ビット幅長から1を減算したデータを法とし、乗算剰余演算をして第1の変数d’を求める。あるいは、単に上記第1の鍵データと上記耐タンパデータとを乗算して第1の変数d‘を求めてもよい。続いて、べき乗剰余演算部は上記暗号データを基数とし、上記第2の乱数データを指数とし、公開鍵データを法とし、べき乗剰余演算をして第2の変数c’を求める。続いて、べき乗剰余演算部は上記第2の変数を基数とし、上記第1の変数を指数とし、公開鍵データを法とし、べき乗剰余演算をして第3の変数tを求める。続いて、べき乗剰余演算部は上記暗号データを基数とし、上記第2の鍵データを指数とし、公開鍵データを法とし、べき乗剰余演算をして第4の変数uを求める。続いて、べき乗剰余演算部は上記第3の変数と上記第4の変数とを基数に用い、公開鍵データを法とし、乗算剰余演算をして復号データを求める。なお、第2に変数及び第3の変数を求める処理と、第4の変数を求める処理の手順は逆であってもよい。また、べき乗剰余演算部は上記第1の鍵データと上記耐タンパデータを基数に用い、モンゴメリ乗算剰余演算において扱える最大ビット幅長から1を減算したデータを法とし、モンゴメリ乗算剰余演算をして第1の変数d’を求める。あるいは、単に上記第1の鍵データと上記耐タンパデータを乗算して第1の変数d’を求めてもよい。続いて、べき乗剰余演算部は上記第3の変数と上記第4の変数を基数に用い、公開鍵データを法とし、モンゴメリ乗算剰余演算をして第5の変数m’を求める。続いて、べき乗剰余演算部は上記第5の変数と上記モンゴメリパラメータの2乗を基数に用い、公開鍵データを法とし、モンゴメリ乗算剰余演算をして復号データを求める。本実施態様のひとつである暗号データと秘密鍵データと公開鍵データとを用いて点のスカラー倍算演算により復号データを求める暗号装置は、記憶部、乱数生成部、乗算部、点のスカラー倍算演算部を備えている。記憶部は、素数データ各々に対応する指数を示す乱数設定データ各々を用いて、上記素数データ各々に対してべき乗を求め、求めたべき乗したデータ各々を乗算して乗算データを求める。続いて、上記乗算データにより上記秘密鍵データを除算して求めた商を示す第1の鍵データと、上記乗算データにより上記秘密鍵データを除算して求めた余りを示す第2の鍵データと、を予め記憶部に記憶する。乱数生成部は、上記素数データ各々に対応する指数を示す、上記乱数設定データ以下でかつ正の整数である第1の乱数データ各々を用いて、上記素数データ各々に対してべき乗を求める。続いて、乱数生成部は求めたべき乗したデータ各々を乗算して第2の乱数データを求める。続いて、乱数生成部は上記素数データ各々に対応する指数を示す、上記乱数設定データから上記乱数設定データに対応する上記第1の乱数データを減算した減算データ用いて、上記素数データ各々に対してべき乗を求める。続いて、乱数生成部は求めたべき乗したデータ各々を乗算して耐タンパデータを求める。乗算部は、上記第1の鍵データと上記耐タンパデータとを用いて乗算をして第1の変数d’を求める。また、モンゴメリ乗算剰余演算部を保有する場合、モンゴメリ乗算剰余演算部は、上記第1の鍵データと上記耐タンパデータを基数に用い、モンゴメリ乗算剰余演算において扱える最大ビット幅長から1を減算したデータを法とし、モンゴメリ乗算剰余演算をして第1の変数d’を求める。乗算部、モンゴメリ乗算剰余演算部は点のスカラー倍算部に含まれていることもありうる。点のスカラー倍算演算部は、上記暗号データと上記第2の乱数データとを用いて点のスカラー倍算演算をして第2の変数c’を求める。続いて、点のスカラー倍算演算部は上記第2の変数と上記第1の変数とを用いて点のスカラー倍算演算をして第3の変数tを求め、上記暗号データと上記第2の鍵データとを用いて点のスカラー倍算演算をして第4の変数uを求める。第2の変数及び第3の変数を求める処理と、第4の変数を求める処理は順番が逆であってもよい。続いて、点のスカラー倍算演算部は上記第3の変数と上記第4の変数とを用いて点の加算演算をして復号データを求める。本実施形態によれば、電力差分解析を用いた秘密鍵の解読を困難にする回路を備えている場合でも、回路規模が大きくならないようにできるという効果を奏する。また、電力差分解析を用いた秘密鍵の解読を困難にする処理を有する場合に、処理速度を向上させることができるという効果を奏する。実施形態各々で説明する暗号装置は、電力差分解析DPAを用いた秘密鍵の解読を困難にするデータランダム化を行う回路を備えている場合でも、回路規模が大きくならないようにできる。また、上記暗号装置で行われる暗号処理をコンピュータで実現する場合には、暗号処理を有するプログラムを、上記コンピュータを用いて実行させてもよい。なお、暗号装置はintegratedcircuitICカード、認証機能付き組み込み機器などに搭載されるICチップ集積回路または回路基板プリント基板などなどが考えられる。以下図面に基づいて、実施形態について詳細を説明する。実施形態1について説明する。実施形態1は、RivestShamirAdlemanRSA暗号を適用した暗号処理を図1のハードウェアに適用したものである。また、RSA暗号で用いるべき乗剰余演算は計算量をlog2dに削減するために、バイナリ法を用いる。べき乗剰余において、例えば、公開鍵データn、暗号データc、秘密鍵データd全てが1024ビット以上の長さを持つ場合1024に限定するものではないに、べき乗剰余を単純に計算した場合、modnを用いた掛け算をd回必要とするが、21024以上の計算量を必要とするため現実的ではない。そこで、この計算量をlog2dに削減するために、バイナリ法を用いる。べき乗剰余におけるバイナリ法は、uビットの秘密鍵データdをd[u-1]d[1]d[0]と表したとき、秘密鍵データdのビット値d[i]を上位ビットから下位ビットの順にスキャンする。すなわち、iu1からi0の順にスキャンする。ただし、d[i]はdの最下位からi番目のビット値で、i≧0である。なお、はビット列の連結を示す。続いて、秘密鍵データdのビット値d[i]に応じて、d[i]=1の場合は2乗算v:v×vmodnの後に、乗算v:=v×amodnを実行し、d[i]=0の場合は、2乗算v:=v×vmodnのみを実行する。なお、この部分はウィンドウ法などのべき乗剰余演算を高速に処理する一般的なアルゴリズムを用いても構わない。図1は、暗号装置のハードウェアの一実施例を示す図である。暗号装置が集積回路である場合には、暗号装置は制御部2、記憶部3、通信インタフェース6などを備え、制御部2、記憶部3、通信インタフェース6各々はバス7によりそれぞれ接続される構成が望ましい。また、暗号装置の回路基板に構築される場合には、制御部2、記憶部3、記録媒体読取装置4、入出力インタフェース5入出力I/F、通信インタフェース6通信I/Fなどを備え、上記した各構成要素はバス7により接続されている構成が望ましい。なお、記録媒体読取装置4は設けなくてもよい。また、入出力インタフェース5または通信インタフェース6のいずれか1つを備えるだけでもよい。制御部2は、後述する処理部201処理回路、乱数生成部202乱数生成回路、べき乗剰余演算部203べき乗剰余演算回路、乗算剰余演算部204乗剰余演算回路などを有している。また、制御部2はCentralProcessingUnitCPUやマルチコアCPUなどを用いることが考えられる。また、制御部2としてプログラマブルなデバイスFieldProgrammableGateArrayFPGA、ProgrammableLogicDevicePLDなどを用いてもよい。記憶部3は、後述する事前生成情報、暗号処理情報などを記憶している。記憶部3は、例えばReadOnlyMemoryROM、Flash-ROM、RandomAccessMemoryRAM、FeRAMなどのメモリやハードディスクなどが考えられる。なお、記憶部3にはパラメータ値、変数値などのデータを記録してもよいし、実行時のワークエリアとして用いてもよい。また、記憶部3ROM、Flash-ROM、FeRAMなどの不揮発性メモリにはプログラムが格納され、実行時に制御部が読み取りながら処理を実行する。記録媒体読取装置4は、制御部2の制御に従って記録媒体8に対するデータのリード/ライトを制御する。そして、記録媒体8に記録媒体読取装置4の制御で書き込まれたデータを記録させたり、記録媒体8に記録されたデータを読み取らせたりする。また、着脱可能な記録媒体8は、コンピュータで読み取り可能なnontransitory非一時的な記録媒体として、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記録装置には、ハードディスク装置HDDなどがある。光ディスクには、DigitalVersatileDiscDVD、DVD-RAM、CompactDiscReadOnlyMemoryCD-ROM、CD-R/RWReWritableなどがある。光磁気記録媒体には、MagnetoOpticaldiskMOなどがある。なお、記憶部3もnontransitory非一時的な記録媒体に含まれる。なお、記録媒体、記録媒体読み取り装置は、必須ではない。入出力インタフェース5には、パーソナルコンピュータなどの入出力部9が接続され、利用者が入力した情報例えば、暗号データ、公開鍵データなどのデータを受信し、バス7を介して制御部2または記憶部3などに送信する。入出力部9の入力装置は、例えば、キーボード、ポインティングデバイスマウスなど、タッチパネルなどが考えられる。なお、入出力部9の出力部であるディスプレイは、例えば、液晶ディスプレイなどが考えられる。また、出力部はCathodeRayTubeCRTディスプレイ、プリンタなどの出力装置であってもよい。通信インタフェース6は、LocalAreaNetworkLAN接続やインターネット接続や無線接続を行うためのインタフェースである。また、通信インタフェース6は必要に応じ、他のコンピュータとの間のLAN接続やインターネット接続や無線接続を行うためのインタフェースである。また、他の装置に接続され、外部装置からのデータの入出力を制御する。また、上記に示したハードウェア構成を有するコンピュータを用いることによって、後述する各種処理機能例えば、図5に示すフローを実現してもよい。その場合コンピュータが有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体8に記録しておくことができる。プログラムを流通させる場合には、例えば、そのプログラムが記録されたDVD、CD-ROMなどの記録媒体8が販売される。また、プログラムをサーバコンピュータの記憶装置に記録しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。プログラムを実行するコンピュータは、例えば、記録媒体8に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶部3に記録する。そして、コンピュータは、自己の記憶部3からプログラムを読み取り、プログラムに従った処理を実行する。制御部2について説明する。図2は、制御部の一実施例を示す図である。図2の制御部2は、処理部201処理回路、乱数生成部202乱数生成回路、べき乗剰余演算部203べき乗剰余演算回路、乗算剰余演算部204乗剰余演算回路などを有している。処理部201は、入出力インタフェース5または通信インタフェース6を介して暗号データcと公開鍵データNを取得し、暗号データcと公開鍵データNを記憶部3に記憶する。または事前に記憶部3に暗号データcと公開鍵データNが格納されているケースもありうる。また、処理部201が記憶部の3の後述する事前生成情報から乱数設定データrpii=0~n:nは正の整数と素数データpii=0~n:nは正の整数を取得する。また、記憶部3から復号データmを取得して、入出力インタフェース5または通信インタフェース6を介して復号データmを出力する。乱数生成部202は、乱数設定データrpiを用いて第1の乱数データsii=0~n:nは正の整数を生成する。第1の乱数データsiの生成は、第1の乱数データsiそれぞれに対して0≦si≦rpiを満たす数値とする。続いて、乱数生成部202は求めた第1の乱数データsiを、処理部201を介して記憶部3に記憶する。また、乱数生成部202は素数データpiと第1の乱数データsiとを用いて第2の乱数データrを生成する。第2の乱数データrは後述する式2を用いて求める。また、乱数生成部202は素数データpiと乱数設定データrpiと第1の乱数データsiとを用いて耐タンパデータr’を生成する。耐タンパデータr’は後述する式3を用いて求める。続いて、乱数生成部202は求めた耐タンパデータr’を記憶部3に記憶する。なお、処理部201が耐タンパデータr’を生成し、記憶部3に記憶してもよい。べき乗剰余演算部203は、記憶部3の暗号データcを基数にし、第2の乱数データrを指数にし、公開鍵データNを法にして、変数c’第2の変数を求める。変数c’は後述する式5を用いて求める。また、べき乗剰余演算部203は記憶部3の変数c’を基数にし、変数d’を指数にし、公開鍵データNを法にして、変数t第3の変数を求める。変数tは後述する式6を用いて求める。続いて、べき乗剰余演算部203は求めた変数tを記憶部3に記憶する。また、べき乗剰余演算部203は記憶部3の暗号データcを基数にし、第2の鍵データdRを指数にし、公開鍵データNを法として、変数u第4の変数を求める。変数uは後述する式7を用いて求める。続いて、べき乗剰余演算部203は求めた変数uを記憶部3に記憶する。乗算剰余演算部204は、記憶部3の第1の鍵データdQと耐タンパデータr’を用い、乗算剰余演算部の処理可能なモジュラスのビット長を示すXを法として、乗算剰余演算を実行して変数d’第1の変数を求める。変数d’は式4を用いて求める。なお、処理部がd’をdQとr’を乗算して求めてもよい。乗算剰余演算部204は、記憶部3の変数tと変数uを用いて、公開鍵データNを法として、乗算剰余演算を実行して復号データmを求める。復号データmは後述する式8を用いて求める。続いて、乗算剰余演算部204は求めた復号データmを記憶部3に記憶する。暗号処理に用いるデータの生成処理について説明する。生成処理は、暗号装置が暗号処理をする際に必要なデータを事前に求める処理で、例えば、コンピュータなどを用いて実行される。該コンピュータは、例えば、パーソナルコンピュータやサーバなどを用いることが考えられる。また、暗号装置内部で事前に処理を行っておいてもよい。図3は、暗号処理に用いるデータの生成処理の動作の一実施例を示すフロー図である。ステップS301では、コンピュータが利用者によって決められた素数データpiと乱数設定データrpiを暗号装置1の通信インタフェース6または処理部201を介して記憶部3または乱数生成部202に出力する。暗号装置内部で処理を行う場合はこの処理は省略される。素数データpii=0~n:nは正の整数それぞれは素数とする。例えば、n=3のときp0=2、p1=3、p2=5などが考えられる。乱数設定データrpii=0~n:nは正の整数それぞれは正の整数とする。例えば、n=3のときrp0=3、rp1=2、rp2=2などが考えられる。ステップS302では、コンピュータまたは暗号装置が秘密鍵データdを生成する。秘密鍵データdは、例えば、既知の鍵生成アルゴリズムを有するプログラムをコンピュータにより実行させることにより得られる。例えば、秘密鍵データdとして7067などの正の整数が考えられる。ステップS303では、コンピュータまたは暗号装置が素数データpiと秘密鍵データdとを用いて第1の鍵データdQと第2の鍵データdRを生成する。第1の鍵データdQと第2の鍵データdRは式1で示すことができる。d=dQ×p0rp0×p1rp1×p2rp2××p2rpndR式1dQ:d/p0rp0×p1rp1×p2rp2××p2rpnの商dR:d/p0rp0×p1rp1×p2rp2××p2rpnの余りpi:素数データrpi:乱数設定データこのとき暗号装置で処理を行う場合には、p0rp0×p1rp1×p2rp2××p2rpnは事前に計算しておいたものを記憶部に格納しておくことで高速に処理できる。例えば、秘密鍵データd=7067で、素数データp0=2、p1=3、p2=5で、乱数設定データrp0=3、rp1=2、rp2=2である場合、第1の鍵データdQは、7067を1800=23×32×52で除算したときの商3となる。第2の鍵データdRは、7067を1800で除算したときの余り1667となる。ステップS304では、コンピュータが第1の鍵データdQと第2の鍵データdRを暗号装置1の通信インタフェース6または処理部201を介して記憶部3に出力する。上記生成処理により、暗号装置1の記憶部3または乱数生成部202に素数データpiと乱数設定データrpiを記憶し、記憶部3に第1の鍵データdQと第2の鍵データdRが記憶される。図4は、事前生成情報のデータ構造の一実施例を示す図を示す。事前生成情報401、402は、素数データpi乱数設定データrpi第1の鍵データdQ第2の鍵データdRに記憶される情報を有している。事前生成情報401の素数データpiには生成処理において出力された素数データが記憶され、本例ではp0p1p2p3p4p5p6が記憶されている。なお、p0p1p2に示されている=2、=3、=5それぞれは、上記説明した3個の素数データp0~p2の値を示している。事前生成情報401の乱数設定データrpiには生成処理において出力された乱数設定データが記憶され、本例ではrp0rp1rp2rp3rp4rp5rp6が記憶されている。なお、rp0rp1rp2に示されている=3、=2、=2それぞれは、上記説明した3個の乱数設定データrp0~rp2の値を示している。事前生成情報402の第1の鍵データdQには生成処理において出力された第1の鍵データが記憶され、本例では3が記憶されている。第2の鍵データdRには生成処理において出力された第2の鍵データが記憶され、本例では1667が記憶されている。なお、本例では記憶部3に事前生成情報401、402がある場合について説明したが、素数データpi乱数設定データrpiに記憶される情報は乱数生成部202に記憶してもよい。暗号処理について説明する。図5は、暗号処理の動作の一実施例を示すフロー図である。ステップS501では、制御部2の処理部201が入出力インタフェース5または通信インタフェース6を介して暗号データcと公開鍵データNを取得する。例えば、暗号データc=1234と公開鍵データN=10807を取得したとする。続いて、処理部201は暗号データcと公開鍵データNを記憶部3に記憶する。事前に記憶部3にc、Nが格納されていることもある。図6の暗号処理情報601を参照。図6は、暗号処理情報のデータ構造の一実施例を示す図である。図6の暗号処理情報601は、暗号データc公開鍵データNに記憶される情報を有している。本例では、上記説明した暗号データc1234と公開鍵データN10807が記憶されている。ステップS502では、制御部2の処理部201が記憶部の3の事前生成情報401から乱数設定データrpiと素数データpiを取得する。例えば、乱数設定データrp0=3、rp1=2、rp2=2と、素数データp0=2、p1=3、p2=5とを取得したとする。ステップS503では、制御部2の乱数生成部202が乱数設定データrpiを用いて第1の乱数データsii=0~n:nは正の整数を生成する。第1の乱数データsiの生成は、第1の乱数データsiそれぞれに対して0≦si≦rpiを満たす数値とする。例えば、乱数設定データがrp0=3、rp1=2、rp2=2である場合、第1の乱数データs0=10≦s0≦3、s1=00≦s1≦2、s2=20≦s2≦2とすることが考えられる。続いて、乱数生成部202は求めた第1の乱数データsiを、処理部201を介して記憶部3に記憶する。図6の暗号処理情報602を参照。図6の暗号処理情報602は、第1の乱数データsiに記憶される情報を有している。本例ではs0s1s2s3s4s5s6が記憶されている。なお、s0s1s2に示されている=1、=0、=2それぞれは、上記説明した3個の第1の乱数データs0~s2の値を示している。ステップS504では、制御部2の乱数生成部202が素数データpiと第1の乱数データsiとを用いて第2の乱数データrを生成する。第2の乱数データrは式2を用いて求める。r=p0s0×p1s1×p2s2××pnsn式2r:第2の乱数データpi:素数データsi:第1の乱数データ例えば、素数データがp0=2、p1=3、p2=5で、第1の乱数データがs0=1、s1=0、s2=2である場合、21×30×52=50を計算して第2の乱数データrを求まる。続いて、乱数生成部202は求めた第2の乱数データrを記憶部3に記憶する。図6の暗号処理情報603を参照。図6の暗号処理情報603は、第2の乱数データrタンパデータr’変数d’変数c’変数t変数u復号データmに記憶される情報を有している。本例では第2の乱数データrタンパデータr’変数d’変数c’変数t変数u復号データmに対応する503610810000282992003544が記憶されている。第2の乱数データrは、ステップS504で求めた第2の乱数データrが記憶される。耐タンパデータr’変数d’変数c’変数t変数u復号データmそれぞれに記憶する情報については後述する。ステップS505では、乱数生成部202または処理部201が素数データpiと乱数設定データrpiと第1の乱数データsiとを用いて耐タンパデータr’を生成する。耐タンパデータr’は式3を用いて求める。r’=p0rp0-s0×p1rp1-s1×p2rp2-s2××pnrpn-sn式3r’:耐タンパデータpi:素数データsi:第1の乱数データrpi:乱数設定データ例えば、素数データがp0=2、p1=3、p2=5で、第1の乱数データがs0=1、s1=0、s2=2で、乱数設定データrp0=3、rp1=2、rp2=2である場合、23-1×32-0×52-2=36を計算して耐タンパデータr’が求まる。続いて、乱数生成部202または処理部201は求めた耐タンパデータr’を記憶部3に記憶する。図6の暗号処理情報603の耐タンパデータr’にステップS505で求めた36を記憶する。ステップS506では、制御部2の乗算剰余演算部204が記憶部3の第1の鍵データdQと耐タンパデータr’を用いて、変数d’を求める。変数d’は式4を用いて求める。d’=dQ×r’modX式4dQ:第1の鍵データr’:耐タンパデータ例えば、第1の鍵データdQが3で、耐タンパデータr’が36である場合に、乗算剰余演算部204の処理可能なモジュラス公開鍵データN:法のビット長が16ビットであるときは、3×36mod0xFFFF=108を計算して変数d’を求める。ここで、0xFFFFは216-1を16進数で表した数である。続いて、乗算剰余演算部204は求めた変数d’を記憶部3に記憶する。dは処理部において、dQとrを乗算して求めてもよい。図6の暗号処理情報603の変数d’にステップS506で求めた108を記憶する。ステップS507では、制御部2のべき乗剰余演算部203が記憶部3の暗号データcと第2の乱数データrと公開鍵データNを用いて、変数c’を求める。変数c’は式5を用いて求める。c’=crmodN式5c:暗号データr:第2の乱数データN:公開鍵データ例えば、暗号データcが1234で、第2の乱数データrが50で、公開鍵データNが10807ある場合は、べき乗剰余演算部203が123450mod10807=10000を計算して変数c’を求める。続いて、べき乗剰余演算部203は求めた変数c’を記憶部3に記憶する。図6の暗号処理情報603の変数c’にステップS507で求めた1000を記憶する。ステップS508では、制御部2のべき乗剰余演算部203が記憶部3の変数c’と変数d’と公開鍵データNを用いて、変数tを求める。変数tは式6を用いて求める。t=c’d’modN式6N:公開鍵データ例えば、変数c’が10000で、変数d’が108で、公開鍵データNが10807である場合は、べき乗剰余演算部203が10000108mod10807=2829を計算して変数tを求める。続いて、べき乗剰余演算部203は求めた変数tを記憶部3に記憶する。図6の暗号処理情報603の変数tにステップS508で求めた1000を記憶する。ステップS509では、制御部2のべき乗剰余演算部203が記憶部3の暗号データcと第2の鍵データdRと公開鍵データNを用いて、変数uを求める。変数uは式7を用いて求める。u=cdRmodN式7c:暗号データdR:第2の鍵データN:公開鍵データ例えば、暗号データcが1234で、第2の鍵データdRが1667で、公開鍵データNが10807である場合は、べき乗剰余演算部203が12341667mod10807=9200を計算して変数uを求める。続いて、べき乗剰余演算部203は求めた変数uを記憶部3に記憶する。図6の暗号処理情報603の変数uにステップS509で求めた9200を記憶する。ステップS502~S508とS509は順番を入れ替えてもよい。ステップS510では、制御部2の乗算剰余演算部204が記憶部3の変数tと変数uと公開鍵データNを用いて、復号データmを求める。復号データmは式8を用いて求める。m=t×umodN式8N:公開鍵データ例えば、変数tが2829で、変数uが9200で、公開鍵データNが10807である場合は、乗算剰余演算部204が2829×9200mod10807=3544を計算して復号データmを求める。続いて、乗算剰余演算部204は求めた復号データmを記憶部3に記憶する。図6の暗号処理情報603の復号データmにステップS510で求めた3544を記憶する。ステップS511では、制御部2が記憶部3から復号データmを取得して、入出力インタフェース5または通信インタフェース6を介して復号データmを出力する。実施形態1によれば、上記復号データ3544は、12347067mod10807を直接計算した結果と一致する。また、暗号処理の度に異なる第1の乱数データsi上記s0、s1、s2が生成されるため、上記処理が毎回異なる途中結果を得ることになるため、電力差分解析DPAに対して安全な処理が実現できる。さらに、実施形態1の暗号装置は、電力差分解析DPAを用いた秘密鍵の解読を困難にするデータランダム化を行う回路を備えている場合でも、除算処理を行う回路を用いないため回路規模が大きくならないようにできる。また、コンピュータを用いた場合においても除算処理を行わないため処理速度を向上させることができる。なお、実施形態1の手法は、べき乗剰余演算の高速処理手法であるChineseRemainderTheoremCRTを用いる場合においても適用できる。実施形態2について説明する。実施形態2は、実施形態1の乗算剰余演算部204をモンゴメリ乗算剰余演算部701にした構成である。実施形態2の暗号処理は実施形態1で説明したハードウェアにモンゴメリ乗算剰余演算を適用したものである。実施形態2の制御部2は、後述する処理部201処理回路、乱数生成部202乱数生成回路、べき乗剰余演算部203べき乗剰余演算回路、モンゴメリ乗算剰余演算部701モンゴメリ乗算剰余演算回路などを有している。記憶部3は、後述する事前生成情報、暗号処理情報などを記憶している。また、上記に示したハードウェア構成を有するコンピュータを用いることによって、後述する各種処理機能例えば、図8に示すフローを実現してもよい。実施形態2の制御部2について説明する。図7は、実施形態2の制御部の一実施例を示す図である。図7の処理部201は、実施形態1で説明した処理部201と同じ処理を行う。図7の乱数生成部202は、実施形態1で説明した乱数生成部202と同じ処理を行う。図7のべき乗剰余演算部203は、記憶部3の暗号データcを基数にし、第2の乱数データrを指数にし、公開鍵データNを法にして、変数c’第2の変数を求める。変数c’は後述する式12を用いて求める。続いて、べき乗剰余演算部203は求めた変数c’を記憶部3に記憶する。また、べき乗剰余演算部203は記憶部3の変数c’を基数にし、変数d’を指数にし、公開鍵データNを法にして、変数t第3の変数を求める。変数tは後述する式13を用いて求める。続いて、べき乗剰余演算部203は求めた変数tを記憶部3に記憶する。また、べき乗剰余演算部203が記憶部3の暗号データcを基数にし、第2の鍵データdRを指数にし、公開鍵データNを法にして、変数u第4の変数を求める。変数uは後述する式14を用いて求める。続いて、べき乗剰余演算部203は求めた変数uを記憶部3に記憶する。図7のモンゴメリ乗算剰余演算部701モンゴメリ乗算剰余演算回路は、記憶部3の第1の鍵データdQと耐タンパデータr’とXを用いて、変数d’第1の変数を求める。Xはを示すデータである。変数d’は後述する式11を用いて求める。続いて、モンゴメリ乗算剰余演算部701は求めた変数d’を記憶部3に記憶する。また、モンゴメリ乗算剰余演算部701は、記憶部3の変数tと変数uと公開鍵データNを用いて、変数m’第5の変数を求める。変数m’は後述する式15を用いて求める。続いて、モンゴメリ乗算剰余演算部701は求めた変数m’を記憶部3に記憶する。また、モンゴメリ乗算剰余演算部701が記憶部3の変数m’とR2と公開鍵データNを用いて、復号データmを求める。復号データmは後述する式16を用いて求める。R2はモンゴメリパラメータRを2乗した値である。続いて、モンゴメリ乗算剰余演算部701は求めた復号データmを記憶部3に記憶する。実施形態2の生成処理は実施形態1で説明した処理と同じである。実施形態2の暗号処理について説明する。図8は、実施形態2の暗号処理の動作の一実施例を示すフロー図である。ステップS801では、制御部2の処理部201が入出力インタフェース5または通信インタフェース6を介して暗号データcと公開鍵データNを取得する。例えば、暗号データc=40239と公開鍵データN=55687を取得したとする。続いて、処理部201は暗号データcと公開鍵データNを記憶部3の暗号処理情報に記憶する。c、Nは事前に記憶部3に記憶されていることもありうる。図9の暗号処理情報903を参照。図9は、実施形態2の事前生成情報と暗号処理情報のデータ構造の一実施例を示す図である。図9の暗号処理情報903は、暗号データc公開鍵データNに記憶される情報を有している。本例では、上記説明した暗号データc40239と公開鍵データN55687が記憶されている。ステップS802では、制御部2の処理部201が記憶部3の事前生成情報から乱数設定データrpiと素数データpiを取得する。例えば、乱数設定データrp0=3、rp1=2、rp2=2、rp3=1と、素数データp0=2、p1=3、p2=5、p3=7とを取得したとする。図9の事前生成情報901を参照。事前生成情報901は、素数データpi乱数設定データrpiに記憶される情報を有している。事前生成情報901の素数データpiには生成処理において出力された素数データが記憶され、本例ではp0p1p2p3p4p5p6が記憶されている。なお、p0p1p2p3に示されている=2、=3、=5、=7それぞれは、上記説明した4個の素数データp0~p3の値を示している。事前生成情報901の乱数設定データrpiには生成処理において出力された乱数設定データが記憶され、本例ではrp0rp1rp2rp3rp4rp5rp6が記憶されている。なお、rp0rp1rp2rp3に示されている=3、=2、=2、=1それぞれは、上記説明した4個の乱数設定データrp0~rp3の値を示している。ステップS803では、制御部2の乱数生成部202が乱数設定データrpiを用いて第1の乱数データsii=0~n:nは正の整数を生成する。第1の乱数データsiの生成は、第1の乱数データsiそれぞれに対して0≦si≦rpiを満たす数値とする。例えば、乱数設定データがrp0=3、rp1=2、rp2=2、rp3=1である場合、第1の乱数データs0=20≦s0≦3、s1=10≦s1≦2、s2=00≦s2≦2、s3=10≦s2≦2とすることが考えられる。続いて、乱数生成部202は求めた第1の乱数データsiを、処理部201を介して記憶部3に記憶する。図9の暗号処理情報904を参照。図9の暗号処理情報904は、第1の乱数データsiに記憶される情報を有している。本例ではs0s1s2s3s4s5s6が記憶されている。なお、s0s1s2s3に示されている=2、=1、=0、=1それぞれは、上記説明した4個の第1の乱数データs0~s3の値を示している。ステップS804では、制御部2の乱数生成部202が素数データpiと第1の乱数データsiとを用いて第2の乱数データrを生成する。第2の乱数データrは式9を用いて求める。r=p0s0×p1s1×p2s2××pnsn式9r:第2の乱数データpi:素数データsi:第1の乱数データ例えば、素数データがp0=2、p1=3、p2=5、p3=7で、第1の乱数データがs0=2、s1=1、s2=0、s3=1である場合、22×31×50×71=84を計算して第2の乱数データrを求まる。続いて、乱数生成部202は求めた第2の乱数データrを記憶部3に記憶する。図9の暗号処理情報905を参照。図9の暗号処理情報905は、第2の乱数データr耐タンパデータr’変数d’変数c’変数t変数u変数m’復号データmに記憶される情報を有している。本例では第2の乱数データr耐タンパデータr’変数d’変数c’変数t変数u変数m’復号データmに対応する8415030022950450075985411238876が記憶されている。第2の乱数データrは、ステップS804で求めた第2の乱数データrが記憶される。耐タンパデータr’変数d’変数c’変数t変数u変数m’復号データmそれぞれに記憶する情報については後述する。ステップS805では、乱数生成部202または処理部201が素数データpiと乱数設定データrpiと第1の乱数データsiとを用いて耐タンパデータr’を生成する。耐タンパデータr’は式10を用いて求める。r’=p0rp0-s0×p1rp1-s1×p2rp2-s2××pnrpn-sn式10r’:耐タンパデータpi:素数データsi:第1の乱数データrpi:乱数設定データ例えば、素数データがp0=2、p1=3、p2=5、p3=7で、第1の乱数データがs0=2、s1=1、s2=0、s3=1で、乱数設定データがrp0=3、rp1=2、rp2=2、rp3=1である場合について説明する。乱数生成部202または処理部201は、23-2×32-1×52-0×71-1=150を計算して耐タンパデータr’が求まる。続いて、乱数生成部202または処理部201は求めた耐タンパデータr’を記憶部3に記憶する。図9の暗号処理情報905の耐タンパデータr’にステップS805で求めた150を記憶する。ステップS806では、制御部2のモンゴメリ乗算剰余演算部701が記憶部3の第1の鍵データdQと耐タンパデータr’を用いて、変数d’を求める。変数d’は式11を用いて求める。d’=dQ×r’×R-1modXmodX式11dQ:第1の鍵データr’:耐タンパデータR:モンゴメリパラメータ例えば、第1の鍵データdQが2で、耐タンパデータr’が150である場合に、モンゴメリ乗算剰余演算部701の処理可能なモジュラス公開鍵データN:法のビット長が16ビットであるときは、2×150×1mod0xFFFF=300を計算して変数d’を求める。ここで、R-1modXの計算結果は1であり、0xFFFFは216-1を16進数で表した数である。続いて、モンゴメリ乗算剰余演算部701は求めた変数d’を記憶部3に記憶する。図9の暗号処理情報905の変数d’にステップS806で求めた300を記憶する。なお、第1の鍵データdQは記憶部3の事前生成情報902から取得する。事前生成情報902は第1の鍵データdQ第2の鍵データdRに記憶される情報を有している。事前生成情報902の第1の鍵データdQには生成処理において出力された第1の鍵データが記憶され、本例では2が記憶されている。第2の鍵データdRには生成処理において出力された第2の鍵データが記憶され、本例では11611が記憶されている。ステップS807では、制御部2のべき乗剰余演算部203が記憶部3の暗号データcと第2の乱数データrと公開鍵データNを用いて、変数c’を求める。変数c’は式12を用いて求める。c’=crmodN式12c:暗号データr:第2の乱数データN:公開鍵データ例えば、暗号データcが40239で、第2の乱数データrが84で、公開鍵データNが55687である場合は、べき乗剰余演算部203が4023984mod55687=22950を計算して変数c’を求める。続いて、べき乗剰余演算部203は求めた変数c’を記憶部3に記憶する。図9の暗号処理情報905の変数c’にステップS807で求めた22950を記憶する。ステップS808では、制御部2のべき乗剰余演算部203が記憶部3の変数c’と変数d’と公開鍵データNを用いて、変数tを求める。変数tは式13を用いて求める。t=c’d’modN式13N:公開鍵データ例えば、変数c’が22950で、変数d’が300で、公開鍵データNが55687である場合は、べき乗剰余演算部203が22950300mod55687=45007を計算して変数tを求める。続いて、べき乗剰余演算部203は求めた変数tを記憶部3に記憶する。図9の暗号処理情報905の変数tにステップS808で求めた45007を記憶する。ステップS809では、制御部2のべき乗剰余演算部203が記憶部3の暗号データcと第2の鍵データdRと公開鍵データNを用いて、変数uを求める。変数uは式14を用いて求める。u=cdRmodN式14c:暗号データdR:第2の鍵データN:公開鍵データ例えば、暗号データcが40239で、第2の鍵データdRが11611で、公開鍵データNが55687である場合は、べき乗剰余演算部203が4023911611mod55687=5985を計算して変数uを求める。続いて、べき乗剰余演算部203は求めた変数uを記憶部3に記憶する。図9の暗号処理情報905の変数uにステップS809で求めた5985を記憶する。ここでステップS809はS802~S808と順序を入れ替えてもよい。ステップS810では、制御部2のモンゴメリ乗算剰余演算部701が記憶部3の変数tと変数uと公開鍵データNを用いて、変数m’を求める。変数m’は式15を用いて求める。m’=t×u×R-1modNmodN式15N:公開鍵データR:モンゴメリパラメータ例えば、変数tが45007で、変数uが5985で、公開鍵データNが55687で、モンゴメリパラメータRが216=0x1000016進数ある場合は、モンゴメリ乗算剰余演算部701が変数m’を求める。変数m’は45007×5985×21706mod55687=41123を計算して求める。ここで、R-1modNは21706である。続いて、モンゴメリ乗算剰余演算部701は求めた変数m’を記憶部3に記憶する。図9の暗号処理情報905の変数m’にステップS810で求めた41123を記憶する。ステップS811では、制御部2のモンゴメリ乗算剰余演算部701が記憶部3の変数m’とモンゴメリパラメータの2乗であるR2modNと公開鍵データNを用いて、復号データmを求める。復号データmは式16を用いて求める。m=m’×R2modN×R-1modNmodN式16N:公開鍵データR:モンゴメリパラメータ例えば、変数m’が41123で、公開鍵データNが10807で、モンゴメリパラメータRが216=0x1000016進数である場合、復号データmは8876となる。モンゴメリ乗算剰余演算部701は41123×51734×21706mod55687=8876を計算して復号データmを求める。R2modNは51734で、R-1modNは21706である。続いて、モンゴメリ乗算剰余演算部701は求めた復号データmを記憶部3に記憶する。図9の暗号処理情報905の復号データmにステップS810で求めた8876を記憶する。ここで、ステップS810、ステップS811について、乗算の可換性により、S810:m’=t×R2×R-1modNmodNS811:m=m’×u×R-1modNmodNあるいは、S810:m=u×R2×R-1modNmodNS811:m=m’×t×R-1modNmodNのような順番で計算してもよい。ステップS812では、制御部2が記憶部3から復号データmを取得して、入出力インタフェース5または通信インタフェース6を介して復号データmを出力する。なお、モンゴメリ乗算剰余演算では1modXと2R-1modXが計算に現れる。そこで、1のmodXについては、Xとして取り扱える最大値を22048-1や、21024-1、2512-1などを使用する。すなわち、modXは無いことと同じになる。2R-1modXについては、本来はdd=dQ×r’×R-1modXmodXを計算し、その後、R-1modNが掛かってしまった影響を打ち消すために、dd×R2modX×R-1modXmodX=dQ×r’×R-1modX×R2modX×R-1modXmodX=dQ×r’modXと計算するのが一般的であるが、X=取り扱える最大値とした場合にはR-1modX=1となるため、そもそもR-1をかけた影響が無い。そこで、影響を打ち消す演算を省略している。ただし、ステップS810とS811ではmodXではなくmodNを用いて計算しなければならない。実施形態2によれば、上記復号データ8876は、4023936811mod55687を直接計算した結果と一致する。また、暗号処理の度に異なる第1の乱数データsi上記s0、s1、s2、s3が生成されるため、上記処理が毎回異なる途中結果を得ることになるため、電力差分解析DPAに対して安全な処理が実現できる。さらに、実施形態2の暗号装置は、電力差分解析DPAを用いた秘密鍵の解読を困難にするデータランダム化を行う回路を備えている場合でも、除算処理を行う回路を用いないため回路規模が大きくならないようにできる。また、コンピュータを用いた場合においても除算処理を行わないため処理速度を向上させることができる。なお、実施形態2の手法は、べき乗剰余演算の高速処理手法であるChineseRemainderTheoremCRTを用いる場合においても適用できる。実施形態3の制御部2について説明する。実施形態3は、楕円曲線暗号を適用した暗号処理を図1のハードウェアに適用したものである。また、楕円曲線暗号で用いる点のスカラー倍算にバイナリ法を用いる。例えば、個人鍵d秘密鍵データが160ビットである場合、秘密鍵データdは非常に大きな数例えば、2160に近い数である場合、スカラー倍算を実行することは、非常に多くの回数の点の加算演算をともなうため、非現実的である。そこで、バイナリ法を用いてスカラー倍算の計算量のオーダを秘密鍵データdのビット数のオーダに抑える。点のスカラー倍算におけるバイナリ法は、秘密鍵データdのビット長をuとする。また、秘密鍵データdのiビット目をd[i]と表記する0≦i≦u-1。d[0]が最下位ビットでありd[u-1]が最上位ビットである。これにより、uビットの秘密鍵データdは、べき乗剰余演算の場合と同様に、前述したd[u-1]d[1]d[0]のように表現される。なお、はビット列の連結を示す。すると、楕円曲線上の点をAと秘密鍵データdを用いて表される楕円曲線上の点V=dAと、d[u-1]d[1]d[0]により、dA=2u-1d[u-1]A21d[1]A20d[0]Aが得られる。スカラー倍算で用いるバイナリ法においては、秘密鍵データdのビット値d[i]を上位ビットから下位ビットの順にスキャンする。すなわち、iu1からi0の順にスキャンし、秘密鍵データdのビット値d[i]に応じて、d[i]=1の場合は2倍算v:=2×vの後に、加算v:=vAを実行し、d[i]=0の場合は2倍算v:=2×vのみを実行する。ただし、d[i]はdの最下位からi番目のビット値で、i≧0である。なお、バイナリ法の他にウインドウ法や符号付バイナリ法、符号付ウィンドウ法など、一般的な点のスカラー倍算高速演算手法を用いてもよい。実施形態3の制御部2は、後述する処理部201処理回路、乱数生成部202乱数生成回路、点のスカラー倍算1001点のスカラー倍算演算回路、点の加算演算部1002点の加算演算回路、乗算部1003乗算回路などを有している。記憶部3は、後述する事前生成情報、暗号処理情報などを記憶している。乗算部1003は点のスカラー倍算部の中に含まれていることもありうる。また、乗算部の代わりにモンゴメリ乗算剰余演算部が含まれていることもある。また、上記に示したハードウェア構成を有するコンピュータを用いることによって、後述する各種処理機能例えば、図11に示すフローを実現してもよい。図10は、実施形態3の制御部の一実施例を示す図である。図10の処理部201は、実施形態1および2で説明した処理部201と同じ処理を行う。図10の乱数生成部202は、実施形態1および2で説明した乱数生成部202と同じ処理を行う。図10の点のスカラー倍算1001点のスカラー倍算演算回路は、記憶部3の暗号データcと第2の乱数データrを用いて、変数c’第2の変数を求める。変数c’は後述する式20を用いて求める。続いて、点のスカラー倍算演算部1001は求めた変数c’を記憶部3に記憶する。また、点のスカラー倍算演算部1001は記憶部3の変数c’と変数d’を用いて、変数t第3の変数を求める。変数tは後述する式21を用いて求める。続いて、点のスカラー倍算演算部1001は求めた変数tを記憶部3に記憶する。また、点のスカラー倍算演算部1001は記憶部3の暗号データcと第2の鍵データdRを用いて、変数u第4の変数を求める。変数uは後述する式22を用いて求める。続いて、点のスカラー倍算演算部1001は求めた変数uを記憶部3に記憶する。点のスカラー倍算は、楕円曲線上の点A、スカラー値dから、V=dAにより与えられる楕円曲線上の点Vを計算する演算である。例えば、点の加算、点の減算、点の2倍算を組み合わせることで行うもので楕円曲線暗号における基本的な演算方法である。楕円曲線ついて説明する。以下に示すx,yの関係式を楕円曲線と呼ぶ。楕円曲線は、主に素体と2べきの2種類からなる。楕円曲線を一意に決定するためのパラメータa,bを楕円曲線パラメータと呼ぶ。楕円曲線素体:y2=x3axbmodpp:素数a、b:楕円曲線パラメータ0≦a、b<p楕円曲線2べき:yxy=x3ax2bmodfF:GF2mの多項式a、b:楕円曲線パラメータa、bIGF2m。楕円曲線上の点は、楕円曲線で表される関係式を満たすx,yであり、素体の場合0≦x,y<pである整数x,yの集合であり、2べきの場合はx,yIGF2mを満たす要素x,yの集合である。また、A=x,yで表される点Aについて、xを点Aのx座標、yを点Aのy座標とそれぞれ呼ぶ。また、楕円曲線上の点の一つは、無限遠点と呼ばれる特殊な点である。楕円曲線上の点の表現を簡略化し、点と表現する場合もある。ここで、無限遠点とは楕円曲線上の特殊な点であり、Oと表記される。任意の点Aに対しAO=OA=Aを満たす。ただし、は点の加算を表す。詳細な定義はIEEEP1363などの標準を参照されたい。ベースポイントは、楕円曲線上の点の一つで、Gと表記される。楕円曲線暗号の利用者間で共通して使用され、公開鍵/個人鍵ペア生成をはじめ、楕円曲線暗号を用いた各種機能において使用される。詳細な定義はIEEEP1363などの標準を参照されたい。点の加算は、点A、Bから、C=ABで表される楕円曲線上の点Cが定義される。このABの演算を点の加算と呼ぶ。Cは、A、Bのx,y座標および楕円曲線パラメータから計算することができる。なお、この演算は可換則、つまりAB=BAが成立する。この演算の詳細についてはInstituteofElectricalandElectronicEngineersIEEEP1363などの標準を参照されたい。なお、点の減算は、点A、Bから、C=A-Bで表される楕円曲線上の点Cが定義される。このA-Bの演算を点の減算と呼ぶ。Cは、A、Bのx,y座標および楕円曲線パラメータから計算することができる。また、点の2倍算は、楕円曲線上の点Aから、点A、Bから、C=2Aで表される楕円曲線上の点Cが定義される。この2Aを演算を点の2倍算と呼ぶ。Cは、Aのx,y座標および楕円曲線パラメータから、算術演算を用いて計算することができる。なお、楕円曲線暗号における公開鍵、個人鍵はベースポイントG、個人鍵を表すスカラー値dに対し、公開鍵はV=dGを満たすVにより与えられる。すなわち、公開鍵は楕円曲線上の点であり、個人鍵はスカラー値である。次に、図10の点の加算演算部1002点の加算演算回路は、記憶部3の変数tと変数uとを用いて、復号データmを求める。復号データmは後述する式23を用いて求める。続いて、点の加算演算部1002は求めた復号データmを記憶部3に記憶する。図10の乗算部1003乗算回路は、記憶部3の第1の鍵データdQと耐タンパデータr’を用いて、変数d’第1の変数を求める。変数d’は後述する式19を用いて求める。続いて、乗算部1003は求めた変数d’を記憶部3に記憶する。実施形態3の生成処理は実施形態1で説明した処理と同じである。実施形態3の暗号処理について説明する。図11は、実施形態3の暗号処理の動作の一実施例を示すフロー図である。ステップS1101では、制御部2の処理部201が入出力インタフェース5または通信インタフェース6を介して暗号データcを取得する。続いて、処理部201は暗号データcを記憶部3の暗号処理情報に記憶する。なお、事前に暗号データcが記憶部3に記憶されていることもある。図12の暗号処理情報1203を参照。図12は、実施形態3の事前生成情報と暗号処理情報のデータ構造の一実施例を示す図である。図11の暗号処理情報1203は、暗号データcに記憶される情報を有している。本例では、上記説明した暗号データccが記憶されている。ステップS1102では、制御部2の処理部201が記憶部3の事前生成情報から乱数設定データrpiと素数データpiを取得する。例えば、乱数設定データrp0=2、rp1=2、rp2=1と、素数データp0=2、p1=3、p2=5とを取得したとする。図12の事前生成情報1201を参照。事前生成情報1201は、素数データpi乱数設定データrpiに記憶される情報を有している。事前生成情報1201の素数データpiには生成処理において出力された素数データが記憶され、本例ではp0p1p2p3p4p5p6が記憶されている。なお、p0p1p2に示されている=2、=3、=5それぞれは、上記説明した3個の素数データp0~p2の値を示している。事前生成情報1201の乱数設定データrpiには生成処理において出力された乱数設定データが記憶され、本例ではrp0rp1rp2rp3rp4rp5rp6が記憶されている。なお、rp0rp1rp2に示されている=2、=2、=1それぞれは、上記説明した3個の乱数設定データrp0~rp2の値を示している。ステップS1103では、制御部2の乱数生成部202が乱数設定データrpiを用いて第1の乱数データsii=0~n:nは正の整数を生成する。第1の乱数データsiの生成は、第1の乱数データsiそれぞれに対して0≦si≦rpiを満たす数値とする。例えば、乱数設定データがrp0=2、rp1=2、rp2=1である場合、第1の乱数データs0=20≦s0≦2、s1=10≦s1≦2、s2=00≦s2≦1とすることが考えられる。続いて、乱数生成部202は求めた第1の乱数データsiを、処理部201を介して記憶部3に記憶する。図12の暗号処理情報1204を参照。図12の暗号処理情報1204は、第1の乱数データsiに記憶される情報を有している。本例ではs0s1s2s3s4s5s6が記憶されている。なお、s0s1s2に示されている=2、=1、=0それぞれは、上記説明した3個の第1の乱数データs0~s2の値を示している。ステップS1104では、制御部2の乱数生成部202が素数データpiと第1の乱数データsiとを用いて第2の乱数データrを生成する。第2の乱数データrは式17を用いて求める。r=p0s0×p1s1×p2s2××pnsn式17r:第2の乱数データpi:素数データsi:第1の乱数データ例えば、素数データがp0=2、p1=3、p2=5で、第1の乱数データがs0=2、s1=1、s2=0である場合、22×31×50=12を計算して第2の乱数データrが求まる。続いて、乱数生成部202は求めた第2の乱数データrを記憶部3に記憶する。図12の暗号処理情報1205を参照。図12の暗号処理情報1205は、第2の乱数データr耐タンパデータr’変数d’変数c’変数t変数u復号データmに記憶される情報を有している。本例では第2の乱数データr耐タンパデータr’変数d’変数c’変数t変数u復号データmに対応する12153012c360c5c365cが記憶されている。第2の乱数データrは、ステップS804で求めた第2の乱数データrが記憶される。耐タンパデータr’変数d’変数c’変数t変数u復号データmそれぞれに記憶する情報については後述する。ステップS1105では、乱数生成部202または処理部201が素数データpiと乱数設定データrpiと第1の乱数データsiとを用いて耐タンパデータr’を生成する。耐タンパデータr’は式18を用いて求める。r’=p0rp0-s0×p1rp1-s1×p2rp2-s2××pnrpn-sn式18r’:耐タンパデータpi:素数データsi:第1の乱数データrpi:乱数設定データ例えば、素数データがp0=2、p1=3、p2=5で、第1の乱数データがs0=2、s1=1、s2=0で、乱数設定データがrp0=2、rp1=2、rp2=1である場合について説明する。乱数生成部202または処理部201は、22-2×32-1×51-0=15を計算して耐タンパデータr’が求まる。続いて、乱数生成部202または処理部201は求めた耐タンパデータr’を記憶部3に記憶する。図12の暗号処理情報1205の耐タンパデータr’にステップS1105で求めた15を記憶する。ステップS1106では、制御部2の乗算部1003が記憶部3の第1の鍵データdQと耐タンパデータr’を用いて、変数d’を求める。変数d’は式19を用いて求める。d’=dQ×r’式19dQ:第1の鍵データr’:耐タンパデータ例えば、第1の鍵データdQが2で、耐タンパデータr’が15である場合に、乗算部1003は2×15=30を計算して変数d’を求める。続いて、乗算部1003は求めた変数d’を記憶部3に記憶する。図12の暗号処理情報1205の変数d’にステップS1106で求めた30を記憶する。乗算部の代わりにモンゴメリ乗算剰余演算部を保有していた場合には、d=dQ×r×R-1modXmodXと計算する。ここでRはモンゴメリパラメータ、Xはである。なお、第1の鍵データdQは記憶部3の事前生成情報1202から取得する。事前生成情報1202は第1の鍵データdQ第2の鍵データdRに記憶される情報を有している。事前生成情報1202の第1の鍵データdQには生成処理において出力された第1の鍵データが記憶され、本例では2が記憶されている。第2の鍵データdRには生成処理において出力された第2の鍵データが記憶され、本例では5が記憶されている。ステップS1107では、制御部2の点のスカラー倍算演算部1001が記憶部3の暗号データcと第2の乱数データrを用いて、変数c’を求める。変数c’は式20を用いて求める。c’=c×r式20c:暗号データr:第2の乱数データ例えば、暗号データをcと表すとき、第2の乱数データrが12である場合は、点のスカラー倍算演算部1001が12×cを計算して変数c’を求める。続いて、点のスカラー倍算演算部1001は求めた変数c’を記憶部3に記憶する。図12の暗号処理情報1205の変数c’にステップS1107で求めた12cを記憶する。ステップS1108では、制御部2の点のスカラー倍算演算部1001が記憶部3の変数c’と変数d’を用いて、変数tを求める。変数tは式21を用いて求める。t=d’×c’式21例えば、変数c’が12cで、変数d’が30である場合は、点のスカラー倍算演算部1001が30×12c=360cを計算して変数tを求める。続いて、点のスカラー倍算演算部1001は求めた変数tを記憶部3に記憶する。図12の暗号処理情報1205の変数tにステップS1208で求めた360cを記憶する。ステップS1109では、制御部2の点のスカラー倍算演算部1001が記憶部3の暗号データcと第2の鍵データdRを用いて、変数uを求める。変数uは式22を用いて求める。u=c×dR式22c:暗号データdR:第2の鍵データ例えば、暗号データcがcで、第2の鍵データdRが5である場合は、点のスカラー倍算演算部1001が5×c=5cを計算して変数uを求める。続いて、点のスカラー倍算演算部1001は求めた変数uを記憶部3に記憶する。図12の暗号処理情報1205の変数uにステップS1109で求めた5cを記憶する。ここで、ステップS1109はステップS1102~S1108と順番を入れ替えてもよい。ステップS1110では、制御部2の点の加算演算部1002が記憶部3の変数tと変数uとを用いて、復号データmを求める。復号データmは式23を用いて求める。m=tu式23例えば、変数tが360cで、変数uが5cである場合、点の加算演算部1002は360c5c=365cを計算して復号データmを求める。続いて、点の加算演算部1002は求めた復号データmを記憶部3に記憶する。図12の暗号処理情報1205の復号データmにステップS1110で求めた365cを記憶する。ステップS1111では、制御部2が記憶部3から復号データmを取得して、入出力インタフェース5または通信インタフェース6を介して復号データmを出力する。実施形態3によれば、上記復号データ365cは、スカラー値d×暗号データcを直接計算した結果と一致する。また、暗号処理の度に異なる第1の乱数データsi上記s0、s1、s2が生成されるため、上記処理が毎回異なる途中結果を得ることになるため、電力差分解析DPAに対して安全な処理が実現できる。さらに、実施形態2の暗号装置は、電力差分解析DPAを用いた秘密鍵の解読を困難にするデータランダム化を行う回路を備えている場合でも、除算処理を行う回路を用いないため回路規模が大きくならないようにできる。また、コンピュータを用いた場合においても除算処理を行わないため処理速度を向上させることができる。また、本発明は、上記実施の形態に限定されるものでなく、本発明の要旨を逸脱しない範囲内で種々の改良、変更が可能である。"