"メッセージMを示すメッセージデータ、秘密素数pを示すpデータ、秘密素数qを示すqデータ、秘密鍵dを示すdデータ、及び、前記p及び前記qよりも大きい奇数である秘密変数rを示す秘密変数データを格納する、データ記憶部と、事前処理部と、主処理部と、後処理部と、を具備し、前記メッセージMは、平文Z、公開鍵e、及び公開鍵Nに基づいて、下記式1により得られたものであり、数式1:M=ZemodN前記eは、p-1×q-1と互いに素である正の整数であり、前記Nは、p×qにより表される数であり、前記dは、p-1×q-1を法とした前記eの逆元を示す数であり、前記事前処理部は、前記pデータ、前記qデータ、及び前記dデータに基づいて、下記式2乃至4によって表される計算を行い、uを示すuデータ、dpを示すdpデータ、及びdqを示すdqデータを生成し、数式2:u=q-1modp数式3:dp=dmodp-1数式4:dq=dmodq-1前記主処理部は、前記メッセージM、前記pデータ、及び前記qデータに基づいて、下記式5及び6によって表される計算を行い、Mpを示すMpデータ、及びMqを示すMqデータを生成し、前記Mpデータ、前記dpデータ、前記pデータ、前記Mqデータ、前記dqデータ、及び前記qデータに基づいて、下記式7及び8によって表される計算を行い、Cpを示すCpデータ及びCqを示すCqデータを生成し、数式5:Mp=Mmodp数式6:Mq=Mmodq数式7:Cp=Mpdpmodp数式8:Cq=Mqdqmodq前記後処理部は、前記Cpデータ、前記Cqデータ、前記uデータ、及び前記pデータに基づいて、下記式9によって表される計算を行い、Cを示すCデータを生成し、前記Cデータ、前記qデータ、前記rデータ、前記Cqデータに基づいて、下記式10又は11によって表される計算を行い、前記平文Zを示す出力データを生成し、数式9:C=Cp-Cq×umodp数式10;Z=C×qr1Cqmodqr数式11;Z=C×qk×r1Cqmodqr上式11中、kは任意の定数を示す復号処理装置。コンピュータが、メッセージMを示すメッセージデータ、秘密素数pを示すpデータ、秘密素数qを示すqデータ、秘密鍵であるdを示すdデータ、及び、前記p及び前記qよりも大きい奇数である秘密変数rを示す秘密変数データを取得するステップと、コンピュータが、事前処理を行うステップと、コンピュータが、主処理を行うステップと、コンピュータが、後処理を行うステップと、を具備し、前記メッセージMは、平文Z、公開鍵e、及び公開鍵Nに基づいて、下記式1により得られたものであり、数式1:M=ZemodN前記eは、p-1×q-1と互いに素である整数であり、前記Nは、p×qにより表される数であり、前記dは、p-1×q-1を法とした前記eの逆元を示す数であり、前記事前処理を行うステップは、前記pデータ、前記qデータ、及び前記dデータに基づいて、下記式2乃至4によって表される計算を行い、uを示すuデータ、dpを示すdpデータ、及びdqを示すdqデータを生成するステップを含み、数式2:u=q-1modp数式3:dp=dmodp-1数式4:dq=dmodq-1前記主処理を行うステップは、前記メッセージM、前記pデータ、及び前記qデータに基づいて、下記式5及び6によって表される計算を行い、Mpを示すMpデータ、及びMqを示すMqデータを生成し、前記Mpデータ、前記dpデータ、前記pデータ、前記Mqデータ、前記dqデータ、及び前記qデータに基づいて、下記式7及び8によって表される計算を行い、Cpを示すCpデータ及びCqを示すCqデータを生成ステップを含み、数式5:Mp=Mmodp数式6:Mq=Mmodq数式7:Cp=Mpdpmodp数式8:Cq=Mqdqmodq前記後処理を行うステップは、前記Cpデータ、前記Cqデータ、前記uデータ、及び前記pデータに基づいて、下記式9によって表される計算を行い、Cを示すCデータを生成し、前記Cデータ、前記qデータ、前記rデータ、前記Cqデータに基づいて、下記式10又は11によって表される計算を行い、前記平文Zを示す出力データを生成するステップを含み、数式9:C=Cp-Cq×umodp数式10;Z=C×qr1Cqmodqr数式11;Z=C×qk×r1Cqmodqr上式11中、kは任意の定数を示す復号処理方法。請求項2に記載される復号処理方法をコンピュータにより実現するための復号処理プログラム。特許文献1に記載された方法によれば、電力差分解析攻撃に対する耐性を高めることができる。しかしながら、この方法では、剰余加減算や剰余乗算を処理可能なコプロセッサを用いた場合であっても、図3に示したように大量の中間演算データが発生する。そのようなコプロセッサを搭載していないコンピュータ通常のコンピュータを用いる場合には、更に大量の中間演算データが発生する。図4は、特許文献1に記載された方法が通常のコンピュータによって実行される場合に発生する中間演算データを示す概略図である。図4には、鍵長が1024bitである場合の例が示されている。図4に示される例では、入力データとして、それぞれ512bitであるp、q、d、及び、1024bitであるメッセージMが用いられている。図4に示されるように、中間演算データとして、14個u,dp,dq,Mp,Mq,Cp,Cq,r1,r3,r2,C00,C0,C1,及びC2の512bitのデータが発生し、8個C11,C21、Z1、Z2、N、Z3、Z4、及びZの1024bitのデータが発生する。上述のように、特許文献1に記載された方法では、中間演算データの種類が非常に多くなり、そのbit長も512bit若しくは1024bitになる。従って、中間演算データを保持するために、メモリの消費量が多くなってしまう。また、中間演算データをロード又はアンロードするために、時間が費やされてしまう。さらに、図4には、RSA暗号の鍵長が1024bitである場合の例が示されているが、近年利用されるRSA暗号では、安全性の面から、鍵長が1280bit~2048bitに変わりつつある。従って、更にメモリを多く消費することになる。加えて、特許文献1に記載された方法では、復号処理を行うために乱数を発生させる必要があり、乱数生成器をコンピュータに設ける必要がある。すなわち、特許文献1に記載された方法では、中間演算処理に要する負担が増大し、中間演算データを一時保存するために大量のメモリが必要になる。また、乱数生成器を設けなければならない。そのため、低価格化が要求されるシステムに対して実装することは不向きである、という問題点があった。また、既述のように、特別なコプロセッサ多倍長整数を用いた算術演算を行うコプロセッサを用いることにより、メモリの消費量を抑制することは可能であるが、そのようなコプロセッサの回路規模は非常に大きい。従って、コスト増大のインパクトも非常に大きい。低価格化が要求されるシステム例えば機器認証を必要とするインターネット接続可能な情報家電などに適用されるシステムに実装する場合は、不利になる。本発明に係る復号処理装置は、メッセージMを示すメッセージデータ、秘密素数pを示すpデータ、秘密素数qを示すqデータ、秘密鍵dを示すdデータ、及び、前記p及び前記qよりも大きい奇数である秘密変数rを示す秘密変数データを格納する、データ記憶部と、事前処理部と、主処理部と、後処理部とを具備する。前記メッセージMは、平文Z、公開鍵e、及び公開鍵Nに基づいて、下記式12により得られたものである。数式12:M=ZemodN前記eは、p-1×q-1と互いに素である正の整数である。前記Nは、p×qにより表される数である。前記dは、p-1×q-1を法とした前記eの逆元を示す数である。前記事前処理部は、前記pデータ、前記qデータ、及び前記dデータに基づいて、下記式13乃至15によって表される計算を行い、uを示すuデータ、dpを示すdpデータ、及びdqを示すdqデータを生成する。数式13:u=q-1modp数式14:dp=dmodp-1数式15:dq=dmodq-1前記主処理部は、前記メッセージM、前記pデータ、及び前記qデータに基づいて、下記式16及び17によって表される計算を行い、Mpを示すMpデータ、及びMqを示すMqデータを生成し、前記Mpデータ、前記dpデータ、前記pデータ、前記Mqデータ、前記dqデータ、及び前記qデータに基づいて、下記式18及び19によって表される計算を行い、Cpを示すCpデータ及びCqを示すCqデータを生成する。数式16:Mp=Mmodp数式17:Mq=Mmodq数式18:Cp=Mpdpmodp数式19:Cq=Mqdqmodq前記後処理部は、前記Cpデータ、前記Cqデータ、前記uデータ、及び前記pデータに基づいて、下記式20によって表される計算を行い、Cを示すCデータを生成し、前記Cデータ、前記qデータ、前記rデータ、前記Cqデータに基づいて、下記式21又は22によって表される計算を行い、前記平文Zを示す出力データを生成する。数式20:C=Cp-Cq×umodp数式21;Z=C×qr1Cqmodqr数式22;Z=C×qk×r1Cqmodqrここで、上式22中、kは任意の定数を示す。本発明に係る復号処理方法は、コンピュータが、メッセージMを示すメッセージデータ、秘密素数pを示すpデータ、秘密素数qを示すqデータ、秘密鍵であるdを示すdデータ、及び、前記p及び前記qよりも大きい奇数である秘密変数rを示す秘密変数データを取得するステップと、コンピュータが、事前処理を行うステップと、コンピュータが、主処理を行うステップと、コンピュータが、後処理を行うステップとを具備する。前記メッセージMは、平文Z、公開鍵e、及び公開鍵Nに基づいて、下記式12により得られたものである。数式12:M=ZemodN前記eは、p-1×q-1と互いに素である整数である。前記Nは、p×qにより表される数である。前記dは、p-1×q-1を法とした前記eの逆元を示す数である。前記事前処理を行うステップは、前記pデータ、前記qデータ、及び前記dデータに基づいて、下記式13乃至15によって表される計算を行い、uを示すuデータ、dpを示すdpデータ、及びdqを示すdqデータを生成するステップを含む。数式13:u=q-1modp数式14:dp=dmodp-1数式15:dq=dmodq-1前記主処理を行うステップは、前記メッセージM、前記pデータ、及び前記qデータに基づいて、下記式16及び17によって表される計算を行い、Mpを示すMpデータ、及びMqを示すMqデータを生成し、前記Mpデータ、前記dpデータ、前記pデータ、前記Mqデータ、前記dqデータ、及び前記qデータに基づいて、下記式18及び19によって表される計算を行い、Cpを示すCpデータ及びCqを示すCqデータを生成ステップを含む。数式16:Mp=Mmodp数式17:Mq=Mmodq数式18:Cp=Mpdpmodp数式19:Cq=Mqdqmodq前記後処理を行うステップは、前記Cpデータ、前記Cqデータ、前記uデータ、及び前記pデータに基づいて、下記式20によって表される計算を行い、Cを示すCデータを生成し、前記Cデータ、前記qデータ、前記rデータ、前記Cqデータに基づいて、下記式21又は22によって表される計算を行い、前記平文Zを示す出力データを生成するステップを含む。数式20:C=Cp-Cq×umodp数式21;Z=C×qr1Cqmodqr数式22;Z=C×qk×r1Cqmodqrここで、上式11中、kは任意の定数を示す。本発明に係る復号処理プログラムは、上述の復号処理方法をコンピュータにより実現するためのプログラムである。本発明によれば、中間演算データのメモリ消費量を削減できる、復号処理装置、復号処理方法、及び復号処理プログラムが提供される。以下に、図面を参照しつつ、本発明の実施形態について説明する。図5は、本実施形態に係る復号処理装置1を示す構成図である。本実施形態に係る復号処理装置1は、コンピュータによって実現される。図5に示されるように、復号処理装置1は、中央演算処理装置2、データ記憶部3、データ入出力部4、及びプログラム記憶部5を備えている。これらは、データバス6を介して、中央演算処理装置2から復号処理装置1、データ記憶部3、データ入出力部4、プログラム記憶部5にアクセス可能になるように接続されている。プログラム記憶部5は、ROMReadOnlyMemory等により実現される。プログラム記憶部5には、復号処理プログラム7が格納されている。復号処理プログラム7は、中央演算処理装置2によって実行される。復号処理プログラム7が実行されることにより、事前処理を行う事前処理部8、主処理を行う主処理部9、及び後処理を行なう後処理部10が実現される。復号処理プログラム7は、例えば、コンピュータによって読み取りが可能な記録媒体図示せずから、プログラム記憶部5にインストールされる。データ入出力部4は、外部装置に接続され、外部装置から必要なデータを取得する機能を有している。また、データ入出力部4は、復号処理装置1によって生成された出力データを外部装置に出力する機能も有している。データ記憶部3は、復号処理に必要なデータを格納する部分である。データ記憶部3には、入出力データ、及び中間演算データが記憶される。入出力データは、データ入出力部4を介して入出力されるデータである。中間演算データは、復号処理プログラム7の実行中に発生するデータであり、データ記憶部3に一時的に記憶される。続いて、本実施形態に係る復号処理装置1の動作方法について説明する。まず、本実施形態に係る復号処理装置1の動作方法の概要について説明する。図6は、復号処理プログラム7に記載されたアルゴリズムを概略的に示す図である。本実施形態では、中央演算処理装置2が復号処理プログラム7を実行することにより、メッセージMが復号され、平文Zが得られる。ここで、メッセージMは、公開鍵e及びNを用いて平文Zを暗号化することにより、得られたものである。復号処理装置1は、図6に示されるように、秘密鍵d、p、q、r、およびメッセージM暗号文をパラメータとして用い、平文Zを得る。ここで、秘密鍵p及びqは、素数である。また、秘密鍵rは、p及びqよりも大きい奇数である。また、公開鍵eは、p-1×q-1と互いに素である正の整数である。また、公開鍵Nは、p×qにより表される数である。更に、秘密鍵dは、p-1×q-1を法としたeの逆元を示す数である。図6に示されるように、復号処理装置1では、事前処理部8が事前処理を行い、u、dp、及びdqが求められる。更に、主処理部9によって、Mp、Mq、Cp、及びCqが求められる。更に、後処理部10によって、C及びZが求められる。ここで、本実施形態においては、Zを計算する為の処理が、工夫されている。すなわち、CRTを用いた場合の最後の計算式既述の数式11が、下記式23により計算される。数式23:Z=C×qr1Cqmodqr上式23を用いることにより、中間演算データの発生量を抑制した上で、電力差分解析攻撃に対する耐性を強化できる。以下に、復号処理装置1の動作方法について、詳細に説明する。図7は、復号処理装置1の動作方法を示すフローチャートである。<ステップS1>まず、データ入出力部4が、外部から、秘密鍵pを示すpデータ、秘密鍵qを示すqデータ、及び秘密鍵dを示すdデータを取得する。pデータ、qデータ、及びdデータは、入出力データとして、データ記憶部3に格納される。<ステップS2>次いで、事前処理部8が、事前処理を実行する。具体的には、事前処理部8は、qデータ及びpデータを用いて、pを法としたqの逆元uを計算し、数値uを示すuデータを生成する。また、事前処理部8は、pデータ及びdデータに基づいて、p-1を法としたdの剰余dpを計算し、数値dpを示すdpデータを生成する。更に、事前処理部8は、qデータ及びdデータに基づいて、q-1を法としたdの剰余dqを計算し、数値dqを示すdqデータを生成する。uデータ、dpデータ、及びdqデータは、中間演算データとして、データ記憶部3に格納される。<ステップS3>次いで、データ入出力部4が、外部から、メッセージMを示すMデータを取得する。Mデータは、入出力データとして、データ記憶部3に格納される。<ステップS4、5>次いで、主処理部9が、Mデータ及びpデータに基づいて、Mのpを法とした剰余Mpを計算し、数値Mpを示すMpデータを生成する。また、主処理部9は、Mデータ及びqデータに基づいて、Mのqを法とした剰余Mqを計算し、数値Mqを示すMqデータを生成する。Mpデータ及びMqデータは、中間演算データとして、データ記憶部3に格納されるステップS4。また、主処理部9は、Mpデータ、dpデータ、およびpデータに基づいて、dpを指数かつpを法としたMpのべき乗剰余Cpを計算し、数値Cpを示すCpデータを生成する。また、主処理部9は、Mqデータ、dqデータ、及びqデータに基づいて、dpを指数かつqを法としたMqのべき乗剰余Cqを計算し、数値Cqを示すCqデータを生成する。Cpデータ及びCqデータは、中間演算データとして、データ記憶部3に格納されるステップS5。<ステップS6>続いて、後処理部10が、Cpデータ、Cqデータ、uデータ、及びpデータに基づいて、CpからCqを減じた結果にuを乗じ、その結果のpを法とした剰余Cを計算し、数値Cを示すCデータを生成する。Cデータは、中間演算データとして、データ記憶部3に格納される。<ステップS7>続いて、データ入出力部4が、外部装置から、秘密変数rを示すrデータを受信し、データ記憶部3に格納する。秘密変数rは、秘密鍵p、qよりも大きい奇数であるステップS7。<ステップS8~11>続いて、ステップS7乃至11の処理が行われ、既述の式23Z=C×qr1Cqmodqrの計算が実行される。すなわち、まず、後処理部10が、qデータ及びrデータに基づいて、qとr1の乗算m0を計算し、数値m0を示すm0データを生成する。m0データは、中間演算データとして、データ記憶部3に格納されるステップS8。次いで、後処理部10が、Cデータ及びm0データに基づいて、Cとm0の乗算m1を計算し、数値m1を示すm1データを生成する。m1データは、中間演算データとして、データ記憶部3に格納されるステップS9。次いで、後処理部10が、m1データ及びCqデータに基づいて、m1とCqの加算m2を計算し、数値m2を示すm2データを生成する。m2データは、中間演算データとして、データ記憶部3に格納されるステップS10。次いで、後処理部10が、m2データ、qデータ、及びrデータに基づいて、m2のqrを法とした剰余Zを計算し、数値Zを示すZデータを生成する。Zデータは、入出力データとして、データ記憶部3に格納されるステップS11。<ステップS12>以上のステップS11までの処理により、平文Zを示すZデータが生成される。Zデータは、復号結果として、データ入出力部4を介して外部装置に送信される。続いて、本実施形態の作用効果について説明する。既述のように、CRTを用いた場合の復号処理においては、最後の演算である数式11Z=C×qCqが、電力差分解析攻撃に対して耐性が低い。ここで、本実施形態においては、数式11が、既述の数式23Z=C×qr1Cqmodqrに変形されている。秘密変数rが用いられているため、電力差分解析攻撃によって秘密鍵qを予測するためには、攻撃者は、秘密変数rも予測する必要がある。2つの秘密変数q及びrを予測する必要があるので、電力差分解析攻撃によって秘密鍵qを推測することが困難になる。従って、電力差分解析攻撃に対する耐性を高めることができる。尚、式11と式23とが等価であることは、以下の式展開により、理解できる。Z=C×qr1Cqmodqr=C×qrC×qCqmodqr=0C×qCqmodqr=C×qCq∵C<p、Cq<q、P<rより、C×qCq<qrは明確。また、式23の代わりに、任意の整数kを用いて、下記式24を用いても、同様の結果を得ることができる。数式24:Z=C×qk×r1Cqmodqr加えて、本実施形態によれば、復号処理時に発生する中間演算データのデータ量を抑制することができる。以下に、この点について詳述する。図8は、本実施形態において発生するデータを概念的に示す図である。図8に示されるように、本実施形態では、入力データとして、pデータ、qデータ、dデータ、rデータ、及びMデータが用いられる。ここで、pデータ、qデータ、dデータ、及びrデータは、それぞれ512bitであるものとする。また、Mデータは、1024bitであるものとする。すなわち、鍵長は、1024bitであるものとする。図8に示されるように、中間演算データとしては、uデータ,dpデータ,dqデータ,Mpデータ,Mqデータ,Cpデータ,Cqデータ,C0データ,Cデータ,r1データ、C1データ、m0データ、m1データ、m2データ、及びKデータが発生する。ここで、uデータ,dpデータ,dqデータ,Mpデータ,Mqデータ,Cpデータ,Cqデータ,C0データ,Cデータ及びr1データは、それぞれ、512bitである。また、C1データ,m0データ,及びKデータは、1024bitである。また、m1データ、およびm2データは、それぞれ、1536bitである。尚、Zデータは、1024bitである。すなわち、10個の512bitのデータ、4個の1024bitのデータ、及び2個の1536bitのデータが発生する。すなわち、本実施形態においては、メモリ消費量は、12Kbitである。本実施形態を図3に示した例と比較する。図3に示した例では、メモリ消費量は、15Kbitである。すなわち、本実施形態によれば、図3に示した例と比較して、メモリ消費量を、3Kbitほど削減できることが理解される。すなわち、本実施形態では、既述の式10及び式11のうち、式11だけが変形されているため、式10及び式11の双方を変形する場合と比較して、メモリ消費量を小さくすることができる。以上説明したように、本実施形態によれば、メモリ消費量を抑制した上で、電力差分解析攻撃に対する耐性を向上することができる。メモリ消費量が削減できるため、中間演算データをロード及びアンロードするために費やされる時間も削減できる。また、乱数生成器を設ける必要がないため、低価格化を実現できる。従って、低価格化が要求されるシステムに対して、有効に適用することができる。"