復号処理装置、復号処理プログラム、復号処理方法
【課題】 強固な対タンパ性を確保する復号処理装置を提供する。
【解決手段】 第１素数ｐ、第２素数ｑ、個人鍵ｄを用いて暗号文ｃを平文ｍに復号する復号処理装置であって、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、第１素数ｐを法としたべき乗剰余演算を行い値ｍ’pを算出するとともに、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、第２素数ｑを法としたべき乗剰余演算を行い値ｍ’qを算出するべき乗剰余演算部１と、ｐ-1（ｍｏｄ ｑ）の演算結果である値ｕとを用いて、（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’pを演算し値ｍsを算出する合成部２と、ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）を演算し平文ｍを算出するシフト解除部３と、を備えた。
【解決手段】 第１素数ｐ、第２素数ｑ、個人鍵ｄを用いて暗号文ｃを平文ｍに復号する復号処理装置であって、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、第１素数ｐを法としたべき乗剰余演算を行い値ｍ’pを算出するとともに、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、第２素数ｑを法としたべき乗剰余演算を行い値ｍ’qを算出するべき乗剰余演算部１と、ｐ-1（ｍｏｄ ｑ）の演算結果である値ｕとを用いて、（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’pを演算し値ｍsを算出する合成部２と、ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）を演算し平文ｍを算出するシフト解除部３と、を備えた。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号処理装置内部に格納されている暗号鍵を電力解析攻撃と呼ばれる攻撃から防ぐための耐タンパ性を有する復号処理装置、復号処理プログラム、復号処理方法に関するものである。
【背景技術】
【０００２】
暗号方式は、共通鍵暗号方式と公開鍵暗号方式に大別される。共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵(秘密鍵)を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵(公開鍵)を一般に公開する代わりに、暗号文を復号するための鍵(個人鍵)を受信者のみの秘密情報とすることで安全性を保つ方式である。
【０００３】
また暗号の分野における技術の一つに、解読技術とよばれるものがある。解読技術とは秘密鍵等の秘密情報を暗号文等入手可能な情報から推定する技術のことであり、様々な手法が存在する。その中で最近注目されている技術に、電力解析攻撃(Power Analysis, 以下PA)と呼ばれる手法がある。電力解析攻撃とは、1998年にPaul Kocherによって考案された手法であり、スマートカード等に搭載された暗号デバイスに様々な入力データを与えた時の電力消費データを収集・解析することで、暗号デバイス内部の鍵情報を推定する手法である。電力解析攻撃を用いることで、共通鍵暗号、公開鍵暗号共に暗号デバイスから秘密鍵を推定できることが知られている。
【０００４】
電力解析攻撃には、単純電力解析(Single Power Analysis、以下SPA)、電力差分攻撃(Differential Power Analysis、以下DPA)の2種類が存在する。SPAは暗号デバイスにおける単一の電力消費データの特徴から秘密鍵の推定を行う方式、DPAは多数の電力消費データの差分を解析することで秘密鍵の推定を行う方式である。
【０００５】
ここでRSA暗号について説明する。RSA暗号は、素因数分解の困難さに基づいた安全性を持つ暗号である。1024-bitの２つの素数p,qに対し、p,qから合成数n=p×qを計算することは容易であるが、nのみから素因数p,qを求めることは困難である(素因数分解の困難さ)ことが安全性の前提となっている暗号である。RSA暗号は、暗号化、復号の２種類の機能を持つ。復号は、中国人剰余定理(Chinese Remainder Theorem, 以下CRT)を利用しない復号(CRTなし復号)と、CRTを利用する復号(CRTあり復号)の２種類が知られている。暗号化、CRTなし復号、CRTあり復号のそれぞれを、図１３、図１４、図１５に示す。
【０００６】
図１３、図１４に示す暗号化処理、CRTなし復号処理は非常に単純である。暗号化処理においては、平文mを基数、公開鍵eを指数、合成数nを法としたべき乗剰余演算c:= me(mod n)を計算することで暗号文cを出力する。CRTなし復号処理においては、暗号文cを基数、個人鍵dを指数、合成数nを法としたべき乗剰余演算m:=cd(mod n)を計算することで平文mを出力する。ただし、個人鍵dは、公開鍵eに対してe×d=1(mod(p-1)(q-1))を満たす値である。べき乗剰余演算の方法については、バイナリ法やwindow法など、複数の計算アルゴリズムが知られており、どのアルゴリズムを用いるかによってSPA、DPAへの耐性が異なる。CRTあり復号は、CRTなし復号の計算量を削減した高速版のアルゴリズムである。一般的に、べき乗剰余処理の計算量は、
(指数のビット長)×(法のビット長)×(法のビット長)
に比例する。例えば、p、qが1024-bit、nが2048-bitのRSA暗号の場合、dのビット長は2048-bitである。なぜなら、e×d=1(mod(p-1)(q-1))すなわちd=e-1(mod(p-1)(q-1))であり、dの値は0<d<(p-1)×(q-1)であるので、dのビット長は(p-1)(q-1)と同じ、つまり2048-bitである。この場合、指数剰余演算に必要な計算量は、
2048×2048×2048=8589934592
である。一般的にCRTなしのRSA復号においては、指数のビット長は法のビット長とほぼ同一となる。つまりCRTなしのRSA復号の計算量は、法のビット長の3乗に比例する。
【０００７】
これに対し、図１５に示すCRTあり復号処理は、CRTなし復号の1/4に計算量を削減できることが知られている。CRTあり復号処理は、以下のCRT-1,CRT-2,CRT-3の３段階から構成される。
(CRT-1) 暗号文cに対する法p,qによる剰余演算(図１５, 301, 302)
(CRT-2) 法p,qによるべき乗剰余演算(図１５, 303, 304)
(CRT-3) 法p,qのべき乗剰余結果から、法nのべき乗剰余結果の算出(CRT合成) (図１５, 305)
CRTあり復号処理の計算の大部分(95%以上)は、CRT-2に示されるべき乗剰余処理であるが、これはcp=c(mod p)もしくはcq=c(mod q)を基数、個人鍵dp=d(mod (p-1))もしくはdq=d(mod (q-1))を指数、素数pもしくはqを法としたべき乗剰余演算である。法p、qのビット長はnの半分つまり1024-bitであり、指数dp、dqのビット長もdの半分つまり1024-bitである。よって、303 もしくは304に示すべき乗剰余処理の計算量は
1024×1024×1024=1073741824
である。つまり、2048-bitのべき乗剰余処理の1/8である。1/8の計算量の処理を2回繰り返すので、CRTあり復号処理の計算量は、CRTなしの計算量の(1/8)×2=1/4である。
【０００８】
CRTあり復号処理を用いることで、CRTなし復号の1/4の計算量、つまり4倍の高速化を実現することができる。その反面、図１５に示すとおり、素数p,qを用いた演算が多いという問題がある。RSA暗号の安全性は、n=p×qの素因数分解の困難さに基づいているため、素数p,qの値が攻撃者に漏洩した場合、RSA暗号は安全ではなくなる。このような、素数p,qを用いた演算処理は、消費電力がp,qと相関しやすいため、PAによりp,qが漏洩しやすいという問題がある。
【０００９】
PAは、個人鍵を用いた処理である図１４のCRTなし復号、もしくは図１５に示したCRTあり復号処理を実装した暗号デバイスをターゲットとして、d,dp,dq,p,qなどの個人鍵を求める攻撃を攻撃者が行うための手段として知られている。以下では、図１４、図１５に対する、従来知られたSPA,DPA攻撃について説明を行う。
【００１０】
（電力解析攻撃）
（SPAの概略）
ここで、SPAの概略について説明する。SPAは、単一の電力波形を観察し、得られた情報を用いることで、暗号デバイス内部の個人鍵を推定する攻撃である。暗号処理の内容と、消費電力波形の形状に相関がある暗号デバイスに対して有効な攻撃である。
【００１１】
（SPAを用いた電力解析攻撃１（CRTあり復号をターゲット）：攻撃１）
SPAを用いた、CRTあり復号をターゲットとした電力解析攻撃(以下、攻撃１)について説明する。
【００１２】
図１５に示したCRTあり復号処理をターゲットとしたSPA攻撃が、特許文献１にて開示されている。これは、301, 302に示す、素数p,qによる剰余処理をターゲットとしている。この攻撃の成功の可否は、301,302の剰余処理の実装形態に依存する。その実装形態は、以下に示すように、Z=X mod Yを計算する際に、XとYの大小比較を行い、X<YならばYをそのまま剰余結果Zとして出力し、X≧Yと判定された場合のみ、剰余演算Z=X (mod Y)を計算して出力する方法である。暗号デバイスがこの実装を用いてCRTあり復号処理を行っていることが、特許文献１にて開示されている攻撃が成立する必須条件である。本方法は、すなわち、Z=X (mod Y)の演算に対し、
if (X<Y) then output X as Z
if (X≧Y) then calculate Z=X (mod Y) and output Z
の処理を行う（以下、この処理をMOD＿ALGと称す）。
【００１３】
上記MOD＿ALGの処理においては、入力Xと法Yの間の大小関係を判定し、X<Yならば剰余演算を実行せず、X≧Yの場合のみ剰余演算を実行する。つまり、XとYの大小関係に応じて、剰余演算の実行の有無が決定する。もし、攻撃者が剰余演算の実行の有無が消費電力を用いて観察できる場合、暗号デバイスの内部データであるXとYの大小関係を消費電力によって知ることができる。この性質を図１５の301, 302に応用することで、攻撃者は素数pもしくはqを解読できる。301, 302では、入力されたcに対して素数p,qによる剰余処理が行われる。スマートカードなどの暗号デバイスにおける実装では、private key(dp,dq,p,q,u)はデバイス内部に格納された値であり外部からは入力できない値であるのに対し、暗号文cは攻撃者を含めた第三者が外部から入力できる値であることに注意されたい。つまり、攻撃者が制御可能なcに対して、c<pであるかc≧pであるかどうかの判定を、301,302に示した剰余演算処理の消費電力を観察することで行うことができる。この判定ができれば、図１６に示す２分探索を用いることで容易にpを求めることができる。
【００１４】
図１６は、pminにp-εの最小値を、pmaxにp-εの最大値を保持しながら、この最大値と最小値の幅を半分ずつに短くすることを繰り返すことで、pの候補値を絞り込むアルゴリズムである。
【００１５】
ただし、εは電力解析を用いた場合の判定誤差の最大値を表す、ε≧0のパラメータである。パラメータεの大きさは用いる攻撃手法によって変化する。このパラメータεは、404で行っているpmid+ε<pの真偽を判定するための手段に応じて変化する。この判定手段として、図１５で示したCRTあり復号に対してCRT＿DEC(pmid)を入力し、SPAを実行することで、pmid<pであるかpmid≧pであるかを判定する場合、ε=0である。後で述べるDPAを用いた攻撃の場合、パラメータεの大きさは1000程度の値となる。
【００１６】
401に示す通り、pminの初期値は0、pmaxの初期値は2α(αはpのビット長)により初期化される。以下402-407のループにおいて、pminとpmaxの差分を半分ずつに短くしながら、pの範囲を絞り込む処理を行う。この絞込み処理は、pmaxとpminの中間値pmidを計算し、pmidとpの大小関係の判定を、消費電力を用いた攻撃により行うことで実施する。
【００１７】
403に記すように、pmaxとpminの中間値pmidは、pmid=(pmax+pmin)/2によって与える。このpmidに対して、消費電力を用いた攻撃を行うことで、pmid+ε<pの判定を行う。
【００１８】
pmid+ε<pが真である場合、pmid<p-ε<pmaxであることを意味する。よってpmaxはそのままで、pmidが新しいp -εの最小値となるため、pmin:=pmidの処理が405にて行われる。
【００１９】
pmid+ε<pが偽である場合、pmin≧p-εであることを意味する。よってpminはそのままで、pmidが新しいp-εの最大値となるため、pmax:= pmid（尚、「：＝」の表記は右辺の結果を左辺に代入することを意味する）の処理が405にて行われる。
【００２０】
この処理を繰り返すことで、pの最大値pmaxと最小値pminの差が半分となる処理が繰り返され、402行目に記されるようにpmax-pmin≦πまで小さくなったら、pの範囲を十分絞り込めたと判断しpの候補値を出力する。
【００２１】
408は、402-407の処理によって、p-εの範囲を十分絞り込めた(差分をπ以下)結果から、pの最大値と最小値を決定する処理を行っている。ε≧0に対してpmin≦p-ε≦pmaxである場合、pの最小値はpminであるが、最大値はpmax+εであるので、pの最大値pmaxに対してpmax:=pmax+εの処理を実行している。この処理の結果、pmax-pmin≦π+εとなる。
【００２２】
409において[pmin,pmin+1,…,pmax]をpの候補値として出力し終了する。403-407のループは、1回実行するごとにpの候補値の個数が半分となる処理を繰り返すため、このループの回数は、αに比例した計算時間で終了する。例えば、pが1024bitの場合、高々1024回で終了するので、非常に効率よく素数pを求めることができる。
【００２３】
（DPAの概略）
次に、DPAについて説明する。DPAは、複数の電力波形を観察し、それらの複数の消費電力間の差分を取ることで、暗号デバイス内部の個人鍵を推定する攻撃である。DPAは、暗号デバイス内部でread, writeされるデータと消費電力の間に相関がある環境において有効である。一般的に、消費電力は暗号デバイス内部でread, writeされるデータに含まれるバイナリ形式のデータの’1’に比例して大きくなる、という性質が知られている。DPAはこの性質を利用することで、個人鍵を求めることができる。
【００２４】
（DPAを用いた電力解析攻撃１（CRTなし復号をターゲット）：攻撃２）
DPAを用いたCRTなし復号をターゲットとした電力解析攻撃（以降、攻撃２）について説明する。RSA暗号に対するDPA攻撃のうち、最もポピュラーな方法として、べき乗剰余処理cd(mod n)を実行する際の消費電力を測定することで、指数dを求める攻撃が知られている。これは、図１４に示すCRTなし復号に対して有効な攻撃である。これらの個人鍵が攻撃者に漏洩した場合、任意の暗号文を復号できるため、RSA暗号の安全性を保つことができない。つまり、素数p,qと同様に、個人鍵dはSPA,DPAの攻撃から保護すべき重要な資産である。
【００２５】
この攻撃を成功させるためには、暗号デバイス内部で実行されているべき乗剰余アルゴリズムの処理方式が何であるかを攻撃者が知っている必要がある。しかし、べき乗剰余アルゴリズムの処理方式の種類は、基本的にバイナリ法、もしくはwindow法と呼ばれるものに大別され、その種類は非常に限られており、べき乗剰余アルゴリズムの種類ごとに考えうる攻撃法を全て試したとしても、攻撃者にとって高々数倍の手間でしかないため、この条件は攻撃者にとって大きな問題とならない。
【００２６】
以下では、暗号デバイスに実装されたべき乗剰余アルゴリズムがwindow法であり、攻撃者がそのことを知っている、という前提において、べき乗剰余cd(mod n)の処理の消費電力から指数dを求める攻撃法について説明する。以下はwindow法を例としているが、バイナリ法など他のべき乗剰余アルゴリズムに対してもDPAは有効である。
【００２７】
ここで、window法の演算とwindow法に対するDPA攻撃について説明する。べき乗剰余処理は、指数d、基数c、法nに対して、m=cd(mod n)を満たすvを計算する処理である。この処理を効率的に行うためのアルゴリズムとして、window法という方法が知られている。指数dの2進表現をd=(du-1,du-2,...,d0)2と表記した時、window法を用いてm= cd(mod n)を計算する指数剰余演算のアルゴリズムを図１７に示す。図１７が行っている演算の概要を図１８に示す。
【００２８】
図１７の処理を説明する。最初にw[x]=cx(mod n)を満たすテーブルwの作成処理を0<x<2kについて行う。テーブル作成処理の後、u-bit値のd=(du-1,du-2,...d0)2をk-bitごとに分割したブロック値としてのu/k個の数列bi(i=0,1,..)を生成する。即ちbi=(dik+k-1,...,dik)2である。このbiを用いたテーブル索引処理(m:=m×w[bi])と、m:=m2^k(mod n)で示される2k乗算を繰り返すことでm=cd(mod n)を計算する。
【００２９】
以下では、攻撃者がDPAを用いて、window法を行う暗号デバイス内部の指数dを推定する方法を説明する。RSA暗号において、指数dは個人鍵であり、攻撃者から保護すべき重要な情報資産である。一般的に、指数dは1024-bit以上の値であるため、この値を総当りによって求めようとする場合、21024の手間がかかり不可能であるが、DPAは、window法の処理である指数dをk-bitずつ分割して処理するという性質に着目する。例えば、図１８に示した処理においては、指数dを4-bitずつbiとして分解し、このbiに関する中間データm:=m×w[bi](mod n)を算出する。このm:=m×w[bi]の値は、暗号デバイスの内部データとしてread, writeされるため、m:=m×w[bi]の計算結果mをreadもしくはwriteする処理の消費電力を測定することで、攻撃者はbiに関する情報を得ることができる。biは高々k-bit(図１８の例の場合4-bit)のデータでしかなく、このk-bit値biに関する総当りをdのすべてのビット値に関して繰り返すことで、攻撃者は効率よく指数dの値を知ることができる。たとえば、k=2かつdが2048-bitの場合、dは1024個の2-bitブロックbiに分割されるが、攻撃者はこの2048-bitすべてのビット値に関する総当りを実行する必要はなく、2-bitつまり4通りの総当りを1024回繰り返せばよく、その手間は4×1024=4096でしかないため、効率よく指数dの値を求めることができる。
【００３０】
このk-bitごとの総当りおいて攻撃者は、2k個のbi候補値のうち正しい値を、DPAを用いて選出する必要がある。この選出方法について以下に説明する。
【００３１】
例えばk=2, d=(d5d4d3d2d1d0)2とした場合、b2=(d5d4)2,b1=(d3d2)2,b0=(d1d0)2となり、図１７に示すwindow法を用いたべき乗剰余演算は以下の(処理1)〜(処理5)を経てm=cd(mod n)を計算する。
(処理1) m = 1×w[b2](mod n) = cb2(mod n)
(処理2) m = (w[b2])4(mod n) = c4b2(mod n)
(処理3) m = ((w[b2])4)×w[b1](mod n) = c4b2ab1(mod n)
(処理4) m = (((w[b2])4)×w[b1])4(mod n) = c16b2c4b1(mod n)
(処理5) m = (((w[b2])4)×w[b1])4×w[b0] (mod n) = c16b2c4b1 cb0(mod n)=cd (mod n)
【００３２】
暗号デバイスがwindow法を実装していることを攻撃者が知っているならば、暗号デバイス内部で上記の(処理1)〜(処理5)が行われていることも攻撃者が知っている。以下に示す手順に従いDPAが行うことで、biの候補値であるb2,b1,b0の値が推定され、dの値が推定される。
【００３３】
501. 暗号デバイスに対し、基数としてN個のai(i=1,2,...,N)を与え、aid(mod n)の処理を行わせる。このときのデバイスの電力消費データP(ai,time)をそれぞれのiについて測定する。
502. 2-bit値b2の値がb'2であると予想し、b2=b'2と判定されるまで、以下の(１),(２)に記される手順を繰り返す。
(１) (処理 1)の中間データvに着目し、予想したb'2からm=aib2'(mod n)の値をシミュレートし、P(ai,time)(i=1,2,..,N)を以下の２つの集合G1,G0に分類する。
・G1 = [P(ai,time)| aib'2(mod n)の最下位ビット=1]
・G0 = [P(ai,time)| aib'2(mod n)の最下位ビット=0]
(２) G1,G0から、Δ=(G1の平均電力) - (G0の平均電力) で表される電力差分曲線Δを作成する。その結果、例えば図１９（Ａ）のような時間-電力曲線で示すような電力消費であるものに対し、図１９（Ｂ）のようなスパイクが出現した場合、b2=b'2と判定し(b2の推定に成功)、図１９（Ｃ）のような平坦な曲線であればb2≠b'2と判定する。
503. 2-bit値b1の値がb'1であると予想し、b1=b'1と判定されるまで、以下の(１),(２)に記される手順を繰り返す。
(１) (処理3)の中間データvに着目し、既に推定したb2及び予想したb'1からm=ai4b2aib1'(mod n)の値をシミュレートし、P(ai,time)(i=1,2,..,N)を以下の２つの集合G1,G0に分類する。
・G1 = [P(ai,time)| ai4b2aib'1(mod n)の最下位ビット=1]
・G0 = [P(ai,time)| ai4b2aib'1(mod n)の最下位ビット=0]
(２) G1,G0から、Δ=(G1の平均電力)-(G0の平均電力)で表される電力差分曲線Δを作成する。その結果、図１９（Ｂ）のようなスパイクが出現した場合、b1=b'1と判定し(b1の推定に成功)、図１９（Ｃ）のような平坦な曲線であればb1≠b'1と判定する。
504. 2-bit値b0の値がb'0であると予想し、b0=b'0と判定されるまで、以下の(１)、(２)に記される手順を繰り返す。
(１) (処理5)の中間データvに着目し、推定に成功したb2、b1及び予想したb'0からm=ai16b2ai4b1aib0'(mod n)の値をシミュレートし、P(ai,time)(i=1,2,..,N)を以下の２つの集合G1,G0に分類する。
・G1 = [P(ai,time)| ai16b2ai4b1aib'0(mod n)の最下位ビット=1]
・G0 = [P(ai,time)| ai16b2ai4b1aib'0(mod n)の最下位ビット=0]
(２) G1,G0から、Δ=(G1の平均電力)-(G0の平均電力)で表される電力差分曲線Δを作成する。その結果図１９（Ｂ）のようなスパイクが出現した場合、b0=b'0と判定し(b0の推定に成功)、図１９（Ｃ）のような平坦な曲線であればb0≠b'0と判定する。
【００３４】
biの推定が正しい場合は、攻撃者がシミュレートしたmの値が、暗号デバイス内部でも発生し、read、write処理が行われているので、上記のG1-G0で示されるように、mに含まれる’0’,’1’の個数が集合G1、G0間で極端に偏るような差分電力波形を作成することで、消費電力に関する差分が発生し、この消費電力差が図１９（Ｂ）で示したようなスパイク波形として観察される。
【００３５】
biの推定が誤っている場合は、攻撃者がシミュレートしたmの値が、暗号デバイス内部では発生しておらず、シミュレートした値とまったく異なる値に関してread, write処理が行われているので、上記のG1-G0で示されるように、mに含まれる’0’,’1’の個数が集合G1、G0間で極端に偏るような差分電力波形を作成してもスパイク波形を得ることはできない。biの推定が誤っている場合、G1、G0はP(ai,time)(i=1,2,..,N)全体の集合Gをランダムに2通りに分類した集合となるため、G1、G0の間の平均消費電力はほぼ同一となり、図１９（Ｃ）に示すような平坦な差分波形となる。
【００３６】
（DPAを用いた電力解析攻撃２（CRTあり復号をターゲット）：攻撃３）
次に、DPAを用いたCRTあり復号をターゲットとした電力解析攻撃(以下、攻撃３と称す)について説明する。CRTあり復号処理における(CRT-1)、すなわち素数p,qによる暗号文(基数)cの剰余演算に対するSPAによる攻撃はすでに説明したとおりである。この処理に対しては、DPAも実行可能である。SPAによる攻撃の場合、攻撃者が制御し、暗号デバイスに対して入力した基数cに対して、c≧pであるか、c<pであるかどうかの判別を単発の消費電力波形によって行っていた。これに対して、DPAを用いた攻撃の場合、暗号デバイスに対して入力した基数cに対して、c+ε<pであるかどうかの判別を、複数の消費電力波形間の差分を用いて行う。ただし、εはエラーパラメータである。c+ε<pの判別に成功した場合、図１６に示す二分探索法を用いることでpの値の候補を絞り込むことができる。ただし、図１６の探索を用いても、pの候補数はε+π以下にならない。しかし、pの候補が総当り可能な程度に小さな値(例えばε+π<240)であれば、ε+πはpの値を絞り込むための大きな問題とはならない。
【００３７】
前述の(CRT-1)に対するSPA攻撃は、Z=X (mod Y)で記される剰余演算アルゴリズムが (MOD＿ALG)に従う、つまりXとYの大小関係に応じて処理を切り替えるようなアルゴリズムが実装されていることを前提としているのに対し、以下で述べるDPA攻撃は、XとYの大小関係に関係なくZ=X (mod Y)の演算処理を常に実行するような暗号デバイスに対しても有効な攻撃である。
【００３８】
攻撃者が制御可能なxについて、DPAを用いることでx+ε<pの判定を行うアルゴリズムを図２０に示す。SPAを用いた攻撃と異なり、正確に判定を行うわけではなく、エラーパラメータεに対してx+ε<pを満たすかどうかの判定であり、暗号デバイスの消費電力特性によってはεが小さすぎると正確な判定が行えない可能性がある。これは、SPAが単一の電力波形を用いた判定を行うのに対し、DPAでは複数の波形間の差分を用いた判定、という違いによるものであり、エラーパラメータεはDPAを成功させるのに必要な波形の個数に比例する。一般的にDPAを成功させるためには、1000個程度のデータ間の差分があれば成功することが知られているため、εも1000程度の小さな値である。
【００３９】
図２０の攻撃アルゴリズムが成功する原理について説明する。Z=X (mod Y)で記される剰余演算結果は、X<Yの場合剰余演算の実装アルゴリズムに関係なくZ=Xとなる。つまり、出力結果Zとして暗号デバイス内部にZとしてreadもしくはwriteされる値Zは、X<Yの場合Z=Xとなる。上記のG1、G0は、x≦ai<x+εで記されるすべての基数aiについてai<p、すなわちx+ε<pであった場合、ai (mod p)として計算される値はすべてaiであり、この値が暗号デバイス内部のメモリにread、writeされる値となる。ai (mod p)の演算結果が全てG1,j, G0,jに含まれる’0’’1’の個数は、j=0,1,…, log2ε - 1全ての差分曲線について大きく偏ることになるので、全てのjに関して、G1,j - G0,j で記される電力差分曲線上に図１９（Ｂ）に記されるようなスパイクが出現する。逆に、ai =x, x+1, …, x+εで記されるすべての基数aiについてai≧pである、すなわちx≧pの場合は、ai (mod p)の演算結果は、整数λiに対してai - λipとなる。εがpに対して十分小さい場合は、λiは非常に高い確率でiの値に関係ない定数λとなることを考慮するとai (mod p)の演算結果は、ai - λpとなる。aiとai - λpの最下位0,1,…, log2ε - 1番目のビット値とは、λpの減算によるキャリーの伝播の影響に応じて同一であったり異なったりする。つまり、ai - λpの最下位0,1,…, log2ε- 1番目のビット値は、aiの最下位0,1,…, log2ε- 1番目のビット値と全て同一とはならず、aiとλpの値に応じて変動する。すなわち、G1,j - G0,j で記される電力差分曲線上に全てスパイクが出現するとは限らず、jの値によってはスパイクが出現しない、もしくは出現したとしても高さが低いスパイクとなり、全てのjに関して十分な高さのスパイクを得ることはできない。
【００４０】
ai =x, x+1, …, x+εで記されるすべての基数aiについて、ai≧pであるaiと、ai<pであるaiが混在する場合も同様であり、全てのjについてスパイクが出現するとは限らない。
【００４１】
よって、G1,j - G0,j で記される電力差分曲線上に図１９（Ｂ）に記されるようなスパイクが、全てのｊについて十分な高さで出現する場合、x+ε<pであると判定できる。
【００４２】
（電力解析攻撃への対策）
図１４、図１５に示すRSA暗号処理に関して、攻撃１、攻撃２、攻撃３に記したSPA, DPAによる攻撃法が知られている。これらの攻撃に対して、対策も同様に知られている。以下では、攻撃１，２，３に対する、従来知られた２種類の対策法(以下、対策１、対策２)について説明を行う。
【００４３】
（対策１）
対策１を図２１に示す。図２１は、1101, 1102が(CRT-1)に対応する処理であり、1103, 1104,1105, 1106が(CRT-2)に対応する処理であり、1107, 1108が(CRT-3)に対応する処理である。
【００４４】
図２１に示す定数R, Rp, Rqは暗号デバイス内部に格納された定数であり、外部には非公開の値である。これらの定数を用いた処理を行うことで、攻撃１，３を防ぐことができる。
【００４５】
図１５と異なり、1101、1102においては、R>pかつR>qを満たす定数Rをcに乗算した新しい基数c×Rに対して、c’p := c×R (mod p)、 c’q := c×R (mod q)による剰余演算を実行する。このRによる補正がかかったc’p, c’qを基数、dp,dqを指数、p,qを法とした指数剰余演算を1103,1104にて実行し、結果をm’p, m’qに格納する。この結果計算される値は、m’p=(c×R)dp (mod p)=Rdp×cdp (mod p)およびm’q=(c×R)dq (mod q)=Rdq×cdq (mod q)である。これを、図１５の303, 304に示したべき乗剰余で計算される値である、mp=cdp (mod p)およびmq=cdq (mod q)と比較すると、定数Rdp, Rdqによる差異がある。この差異を補正し、cdp (mod p), cdq (mod q)を計算するための処理を1105, 1106にて実行する。これは、事前計算された定数Rp=R-dp (mod p), Rq=R-dq (mod q)を用いて、mp := m’p× Rp (mod p)=cdp×Rdp×R-dp (mod p)=cdp (mod p), mq := m’q× Rq (mod q)=cdq×Rdq×R-dq (mod q)=cdq (mod q)の計算処理により実行する。mp=cdp (mod p)およびmq=cdq (mod q)への補正は、1107にて記されるCRT合成を行うために実施する処理である。これらの値を1107に示すCRT合成への入力として与えた処理を実行することで、m:= (( u×(mq - mp) ) (mod q) )×p + mp =cd (mod n)が計算され、出力される。
【００４６】
図２１に示した対策１により、1101、1102において、定数Rを乗算してからp,qによる剰余演算を実行する処理により、攻撃１への対策を実現している。RはR>pおよびR>qを満たす定数であるため、特殊な入力c=0の場合を除き、常にc×R≧pおよびc×R≧qが成立するので、(MOD＿ALG)に示すZ=X (mod Y)の計算においては、常にX≧Yの分岐しか発生しないため、攻撃者は有効な情報を得ることはできない。c=0の場合のみ、X<Yの分岐が発生するが、これは0<pという自明な情報を得ているのに過ぎない。
【００４７】
よって、図２１に示す対策１を用いることで、(MOD＿ALG)に示す分岐処理からpに関する有効な情報を攻撃者は得ることができないため、攻撃１を防ぐことができる。
【００４８】
さらに、図２１に示す対策１は、攻撃３を防ぐ効果を有する。なぜなら、1101、1102において、攻撃者にとって未知の値である定数Rを用いてc×R (mod p)、c×R (mod q)を計算するため、攻撃者はcに対するc×Rの値を予想することができないので、c×R (mod p)の値も予想することができない。もし、Rの値が攻撃者にとって既知であれば、cの代わりにc=g×R-1 (mod n)を入力する攻撃３を実行することで、同様の攻撃を実行可能である。なぜなら、1101で計算される値は、c×R (mod p) = (g×R-1)×R (mod p) = g (mod p)となり、攻撃者が制御可能なgに対する剰余演算を実行されるので、攻撃者は攻撃３と同じ状況を作り出すことができるからである。ここでは、R-1 (mod n) = R-1 (mod p)の関係式を利用しており、R-1 (mod n) = R-1 (mod p)となる理由は、n=p×qおよび任意の整数aに対して、a-1 (mod n) = a-1 (mod p)= a-1 (mod q)という性質が一般的に知られていることによるものである。ただし、Rが未知の定数であれば、攻撃者はgからg×R-1 (mod n)を計算することができないため、対策1は攻撃３に対して安全である。
【００４９】
言い換えれば、対策１の安全性は、定数R, Rp, Rqが攻撃者に対して未知の値であることが前提である。これらの定数が攻撃者に対して未知である限りは、安全である反面、潜在的なリスクが存在する。暗号デバイスの全固体で用いられる共通の定数値の場合、１個の固体からこれらの定数が漏洩した場合、全固体のセキュリティが脅かされるという潜在的なリスクである。さらに、対策１を用いる場合、定数R, Rp, Rqをデバイス内部に格納する必要があるため、これらの値を記録するためのメモリ追加コストが必要である。定数Rは、R>q, R>qであるので、最低p,qのビット長以上のメモリ領域が必要である。p,qのビット長がnのビット長の半分であるとすると、定数Rに必要なメモリ領域は(log2n)/2ビットである。Rp, Rqに必要なメモリ領域はp,qと同じであり、それぞれ(log2n)/2ビットである。これらを合計すると、R, Rp, Rqの格納に必要なメモリ領域は3(log2n)/2ビットとなる。一般的なRSA処理においては、nは1024-bit以上の値が用いられているため、1536-bit以上の記憶領域が必要となる。計算量に関する追加コストは、1101, 1102に示すRとの乗算、1105, 1106に示すRp, Rqとの乗算処理であるが、これらの追加計算量コストは全体の計算量に占める割合は非常に低く、無視できるほど小さい。
【００５０】
上記をまとめると、対策１は攻撃１，３を防ぐことができる。対策１に必要な追加コストは、定数R, Rp, Rqを格納するためのメモリ領域であり、その大きさは3(log2 n)/2ビット(最低1536ビット)と評価できる。さらに、潜在的なリスクとして、定数R, Rp, Rqが全暗号デバイス固体間で共通の定数である場合、１個の固体からこれらの定数が漏洩することで、全固体のセキュリティが危険となる可能性がある。
【００５１】
（対策２）
攻撃２に対する防御法として、多数の対策法が知られている。いずれの対策法にも共通することは、cd (mod n)の計算を実行する際に、暗号デバイス内部で乱数を発生させた上で、この乱数を用いて、cd (mod n)の計算過程で発生する中間データをランダム化する処理を含んでいることである。
【００５２】
攻撃２においては、攻撃者は入力cから、cd (mod n)の計算過程において発生する中間データ値のシミュレートを行い、このシミュレートに基づいてG1 - G0で示される差分曲線を作成するが、この計算過程における中間データをランダム化することで、攻撃２におけるシミュレーションを無効化することで、攻撃２を防ぐ。この方法では、cd (mod n)のべき乗剰余の計算過程で発生する中間データをランダム化するが、最終的な出力として通常のべき乗剰余処理と同じ値cd (mod n)を出力する必要があるため、ランダム化の解除があわせて必要となる。中間データをランダム化による攻撃２の対策は様々な方法が知られているが、これらの対策法ごとに、ランダム化とランダム化の解除方法が異なり、これらの方法の差異によって、対策に必要となる計算量やメモリなどの追加コストが異なる。
【００５３】
以下では、攻撃２に対する代表的な対策法である、指数のランダム化法について説明を行う（対策２）。
【００５４】
図２２は指数のランダム化法による攻撃２への対策法（対策２）を示している。対策の基本的なアイデアとしては、べき乗剰余計算における指数をランダム化することで攻撃２に対策を行っている。この指数値のランダム化は、指数dの代わりに、ランダム化された指数d’=d+r×φ(n)を用いることで行う。ただし、rは20-bitの乱数、φ(x)は法xに対する位数であり、法xに対する位数は、任意の整数aに対して、aφ(x) (mod x) = 1 となる性質を備える。素数p,qに対してn=p×qの場合、φ(n)=(p-1)(q-1)、φ(p)=p-1、φ(q)=q-1であることが知られている。
【００５５】
20-bit乱数rによって与えられる指数d+r×φ(n)のビット列はランダムに変化するため、べき乗剰余処理過程における中間データはランダム化されるが、最終的に計算される値は常にcd (mod n)と同じとなる（図２３参照）。最終的に計算される値がcd (mod n)であるのは、cd + r×φ(n) = cd × (cφ(n))r (mod n)であり、位数の性質により、任意の整数cに対してcφ(n)=1(mod n)であるため、任意の乱数rに対してcd+r×φ(n) = cd ×(cφ(n))r (mod n)= cd × (1)r (mod n) = cd (mod n)が成立するからである。
【００５６】
対策２に伴う追加コストであるが、計算時間については、指数dの代わりにd’=d+r×φ(n)を用いる分のコストが発生する。dのビット長はlog2(n)であるのに対し、d’のビット長はr×φ(N)のビット長であり、log2n + 20 で与えられる。べき乗剰余演算の処理時間は、(法のビット長)× (法のビット長)× (指数のビット長)であるが、対策２を用いることで、指数のビット長がlog2(n)からlog2n+20に伸びるため、対策２を用いない場合と比較すると計算時間は(log2n+20)/(log2n)となる。log2n=1024の場合、1044/1024=1.02であるため、計算時間に関する追加コストは若干発生するが、全体の計算時間に占める割合は非常に小さいことが特徴であるため、効率的な対策法として知られている。メモリ領域に関する追加コストは、乱数rを格納するための20-bitの領域と、図１４に示すCRTなし復号演算では用いられなかった位数φ(n)を格納するためのlog2nビットの領域が必要となる。
【００５７】
上記をまとめると、対策２は攻撃２を防ぐことができる。対策２に必要な計算量コストは、指数dの代わりに指数d’=d+r×φ(n)を用いるコストであり、計算量は図１４に示す対策なしの方法と比較すると(log2n+20)/(log2n)倍となるが、nが1024-bitの場合増加分は2％と非常に小さい。メモリ領域に関する追加コストは、乱数rと位数φ(n)の分を合わせて、(20+log2n)ビット必要となる。一般的にはnは1024ビット以上であるため、1044ビット以上の追加メモリを必要とする。
【００５８】
（対策１と対策２のまとめ）
ここで、従来知られる対策１、対策２の特徴に関してまとめる。対策１（すなわち図１５への対策）は、攻撃１、３に対して有効であり、計算量に関する追加コストは図１５のものと等倍、メモリに関する追加コストは3(log2n)/2ビット（≧1536ビット）となる。尚、対策１は、定数R、Rp、Rqが全固体共通の場合、R、Rp、Rqの漏洩により全固体が脆弱となる問題を含んでいる。一方、対策２（すなわち図１４への対策）は、攻撃２に対して有効であり、計算量に関する追加コストは図１４の(log2n+20)/(log2n)倍、メモリに関する追加コストは(20+log2n)ビット（≧1044ビット）となる。
【００５９】
（対策１と対策２に関する問題点）
以上のように、図１４、図１５に示したRSA復号処理に対して、攻撃１、２、３に示した攻撃法が知られているが、それらは対策１、２にて示した従来の対策法によって防ぐことができる。つまり、従来知られた攻撃１、２、３は、従来知られた対策法１、２によって防ぐことができる。
【００６０】
尚、DESやAESなどの共通鍵暗号方式に対して、SPA、DPAを用いた推定法、およびRSA暗号、楕円曲線暗号などの公開鍵暗号に対してSPA、DPAを用いた推定法が以下に記す文献に開示されている。また、サイドチャネルアタックに対して安全性の高い復号化演算方法も、以下に記す文献に開示されている。
【先行技術文献】
【特許文献】
【００６１】
【特許文献１】特許４０８６５０３号公報
【特許文献２】国際公開第００／５９１５７号パンフレット
【非特許文献】
【００６２】
【非特許文献１】Paul Kocher, Joshua Jaffe, and Benjamin Jun, "Differential Power Analysis," in proceedings of Advances in Cryptology-CRYPTO'99, Lecture Notes in Computer Science vol. 1666, Springer-Verlag, 1999, pp. 388-397
【非特許文献２】Thomas S.Messerges, Ezzy A.Dabbish and Robert H.Sloan "Power Analysis Attacks of Modular Exponentitiation in Smartcards", Cryptographic Hardware and Embedded Systems(CHES'99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp.144-157
【非特許文献３】Jean-Sebastein Coron “Resistance against Differential Power Analysis for Elliptic Curve Crytosystems”,Cryptographic Hardware and Embedded Systems (CHES’99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp.292-302, 1999
【非特許文献４】Alfred J.Menezesほか著”HANDBOOK OF APPLIED CRYPTOGRAPHY”(CRC press) pp.615
【発明の概要】
【発明が解決しようとする課題】
【００６３】
しかし一方、これらの対策法が新たな攻撃法に対して耐性をもつとは限らない。一般的に、セキュリティにおける対策法は、全ての攻撃法に対して等しく耐性を持たないと意味を成さない。たとえば、10種類中9種類の攻撃法を対策法によって防ぐことができたとしても、残り1種類の攻撃を防ぐことができなければ、その攻撃法によって個人鍵が漏洩することで、攻撃者は暗号化された全てのデータを自由に復号することができるからである。よって、暗号デバイスにおける対策法は、全ての攻撃法に対して耐性を持つことが求められる。よって、対策法は、従来の攻撃法１、２、３のみに耐性をもつだけではなく、これらの攻撃法を拡張した新たな攻撃法にも耐性を持つことが求められる。
【００６４】
以下では、従来の攻撃３を拡張した新たな攻撃法の例（攻撃４）について説明した上で、この攻撃法は従来の対策１，２では防ぐことができないことを説明する。
【００６５】
（攻撃４について）
攻撃３に示される図１５に示すCRTあり復号処理への攻撃を拡張することで、新しい攻撃法が考えられる。攻撃３は、図１５の301、302に示す、cp:=c (mod p)、 cq := c (mod q)に示す剰余演算をターゲットとしている。この処理をターゲットとすることで、攻撃者が制御可能なcに対する剰余演算を行い、図２０に示すDPAをベースとした攻撃法を用いることで、素数pに対してc<p-εの判定(εはエラーパラメータ、1000程度の小さな値)を行うことができ、この情報を用いることで、素数pの候補を総当り可能な個数までに絞り込むことができる。
【００６６】
この考え方を応用することで、図１５の303に示すmp:=cpdp(mod p)、 mq:=cqdq(mod q)の演算処理に図２０に示すDPAをベースとした攻撃法を用いることで、同様に素数pの候補数を絞り込むことができる。以降、この攻撃法を攻撃４と呼び、その方法を説明する。
【００６７】
攻撃４の基本的なアイデアを図２４に示す。攻撃３と異なるのは、図１５のCRT＿DEC(c)の与え方である。従来は、攻撃者がx+ε<pの判定を行うためのxを生成し、このxをそのまま図１５の入力であるcにCRT＿DEC(x)として与えていた。これに対し、攻撃４では、攻撃者がx+ε<pの判定を行うためのxを生成し、このxに対して、公開鍵e,nから計算した値y=xe (mod n)を生成した上で、CRT＿DEC(y)を図１５への入力として与える。公開鍵e,nは、暗号デバイス外部に公開されている値であるため、攻撃者はxからxe (mod n)を自由に生成できる。
【００６８】
xの代わりに、xe (mod n)を与えることで、図１５の303, 304に示すべき乗剰余処理、すなわち図２４における1513, 1514においては、それぞれmp:=(xe)dp (mod p) = x (mod p)、 mq:=(xe)dq (mod q) = x (mod q)が計算され、この値が暗号デバイス内部のメモリに対してread, writeされる処理が発生する(この等式が成立する理由は、RSA暗号の鍵e,dp,dq,p,qに関して、(ae)dp=1 (mod p), (ae)dq = 1 (mod q)が任意の整数aに対して成立するという、公知の性質によるものである。)。つまり、攻撃者が制御可能なxに対して、x (mod p)、 x (mod q) に示す剰余演算が実行されているときと同じ消費電力が発生するため、図２０に示すDPAをベースとした攻撃法を用いることができる。図２０に示すDPAベースの攻撃法を用いることができれば、図１６に示す２部探索により、pの候補数を全数探索可能な個数まで絞り込むことができるため、素数p,qを求めることができる。
【００６９】
この攻撃４は、従来の対策１、２では防ぐことができない。なぜなら、対策１は、CRT合成を正しく実行するために、CRT合成を行う直前の処理段階である図２１の1105, 1106において、定数Rp、Rqを乗算することでmp=cdp (mod p), mq=cdq (mod q)を計算している。つまり、c=xe (mod n)を入力することで、1105、1106における計算結果はx (mod p)、 x(mod q)となるため、攻撃４は実行可能である。
また対策２は、CRTあり復号処理への対策ではないが、べき乗剰余に対する対策であるため、図１５の303, 304のべき乗剰余処理に適用することができる。ただし、この適用を行ったとしても、攻撃４を防ぐことはできない。なぜなら、図２３に示すように、べき乗剰余の中間データをランダム化するが、最終的に計算される値は常に一定であり、この処理を図１５の303, 304のべき乗剰余処理に適用した場合、mp=cdp (mod p), mq=cdq (mod q)が計算されることになる。よって、攻撃４は実行可能である。このように、従来の対策法１、２は攻撃４に対する耐性がないという問題を有している。
【００７０】
本発明は上述した問題点を解決するためになされたものであり、攻撃４に対する対策が備えられた復号処理装置、復号処理プログラム、復号処理方法を提供することを目的とする。
【課題を解決するための手段】
【００７１】
復号処理装置は、素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する復号処理装置であって、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算部と、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算部と、前記第１べき乗剰余演算部、前記第２べき乗剰余演算部によって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成部と、前記合成部によって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除部と、を備える。
【００７２】
また、復号処理プログラムは、素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し、平文ｍを算出する処理をコンピュータに実行させる復号処理プログラムであって、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｐを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、をコンピュータに実行させる。
【００７３】
さらに、復号処理方法は、素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し、平文ｍを算出する復号処理方法であって、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、をコンピュータが実行する方法である。
【発明の効果】
【００７４】
上記攻撃４に対する耐性を有することができ、従来の対策と組み合わせることで、より対タンパ性を確保することができる。
【図面の簡単な説明】
【００７５】
【図１】本実施の形態の前提技術に係る、基数のランダム化を用いた攻撃４に対する対策法を示す図である。
【図２】本実施の形態に係る復号処理装置のハードウェア構成の一例を示す図である。
【図３】本実施の形態に係る復号処理装置の機能ブロックの一例を示す図である。
【図４】本実施の形態に係る復号処理装置が実施する基本処理の一例示す図である。
【図５】本実施の形態に係る、攻撃者が制御可能なデータ値に対しxg （mo d p）の演算結果のread,write処理を実行する復号処理装置をターゲットとし て、DPAを用いて（x+ε）g＜pの判定を行う攻撃アルゴリズムを示す図であ る。
【図６】本実施の形態に係る、pの近似値を取得するための数式を示す図である。
【図７】本実施の形態に係る実施例１の処理の一例を示す図である。
【図８】本実施の形態に係る実施例２の処理の一例を示す図である。
【図９】本実施の形態に係る実施例３の処理の一例を示す図である。
【図１０】本実施の形態に係る実施例４の処理の一例を示す図である。
【図１１】本実施の形態に係る実施例５の処理の一例を示す図である。
【図１２】本実施の形態に係る実施例６の処理の一例を示す図である。
【図１３】RSAの暗号処理の手法を示す図である。
【図１４】RSAのCRTなし復号処理処理の手法を示す図である。
【図１５】RSAのCRTあり復号処理処理の手法を示す図である。
【図１６】二分探索と電力解析を組み合わせた、pの範囲を絞り込む攻撃アルゴリズムを示す図である。
【図１７】window法を用いたべき乗剰余処理を示す図である。
【図１８】window法の処理を示す図である。
【図１９】消費電力曲線、スパイクが出現する電力差分曲線、および平坦な電力差分曲線を示す図である。
【図２０】攻撃者が制御可能なデータ値xに対して、x (mod p)の演算結果のread,write処理を実行する復号処理装置に対し、DPAを用いてx+ε<pの判定を行う攻撃アルゴリズムを示す図である。
【図２１】攻撃１、攻撃３への対策アルゴリズムを示す図である。
【図２２】攻撃２への対策アルゴリズムを示す図である。
【図２３】対策２の中間データランダム化と、ランダム化を解除した演算結果を出力する過程を示す図である。
【図２４】攻撃４の処理内容について説明する図である。
【発明を実施するための形態】
【００７６】
本実施の形態では、
（課題１）攻撃４に対して脆弱である。
との課題を解決する対策法について記載する。また、本実施の形態が提供する対策法は、単に上記攻撃４を防ぐだけではなく、対策に伴う計算量・メモリの追加コストを最小限とするという優れた特徴を有する。本発明の対策法について説明する前に、攻撃４を防ぐ基本となる対策法を前提技術として説明する。この対策法も、基数の値を変更する、というアイデアに基づいているが、このような基数を変更するというアイデアでは、攻撃４に対策することはできても、別の問題点を有することについても説明する。その後、本実施の形態による攻撃４への対策法を説明する。
【００７７】
（前提技術）
図１に前提技術となる対策法（以下、対策３）を示す。これは、基数cに対してそのままCRTあり復号演算を実行するのではなく、乱数Sを発生し(1601)、c×S(mod n)によるランダム化を行った上でCRTあり復号による演算処理CRT＿DEC(c×S (mod n))を実行し、結果をワーク変数領域Wに格納する(1602)。その結果、W=(c×S)d (mod n)が計算される。この乱数Sによるランダム化を解除するために乱数Sの逆数によるCRTあり復号演算をCRT＿DEC(S-1 (mod n))により実行し、結果をmに格納する。その結果、m=S-d (mod n)が計算される。最後に、m:=W×m (mod n)により、m:= (c×S)d × S-d = cd (mod n)の演算を行い、ランダム化を解除した結果をmに格納する。
【００７８】
これらの一連の演算においては、CRT＿DECに入力する基数がSによってランダム化されるため、攻撃４を防ぐことができる。その反面、対策に伴う追加コストが発生する。計算量的な追加コストとしては、CRTあり復号演算を２回実行するため、計算量が図１５に示す方法の2倍となる。メモリ領域に関する追加コストとしては、乱数Sを格納するためのワーク領域と、1602に示すCRTあり復号結果を格納するためのワーク領域Wが追加となる。Sはp,qと同一のビット長であるため、(log2n)/2ビット必要である。Wはnと同じビット長が必要のため、(log2n)ビット必要である。
【００７９】
これらの追加コスト評価は、実装形態に依存しない最低限の追加コスト評価であり、1602に示すc×S (mod n)を計算するためのメモリ領域や、S-1 (mod n)を計算するための一時的なメモリ領域、およびSの逆数S-1を計算するための計算量コストは無視した、非常に楽観的な評価である。
【００８０】
以上をまとめると、対策３による基数のランダム化処理により、攻撃４を防ぐことはできるが、計算量およびメモリに関する追加コストが発生するという課題を有する。計算量については、図１５に示す方法の2倍の必要であり、メモリに関しては(3log2n)/2の追加コストが必要である。
【００８１】
以下、上述対策３によって生じた課題についてまとめると、
（課題２）図１５で示した、対策なしの方法の２倍の計算量が必要。
（課題３）追加メモリとして、(3log2n)/2（≧1536ビット）のメモリ領域が必要。
となる。
【００８２】
（実施の形態）
上記前提技術の課題を解決するための復号処理装置について、図２にハードウェア構成の一例を、図３に機能ブロックの一例を示す。
【００８３】
まず、復号処理装置のハードウェア構成を図２を参照しつつ説明する。尚、本実施の形態の復号処理装置10は、具体的には例えばスマートカード等の暗号デバイスに組み込まれることができる。図２に示すように、本実施の形態に係る復号処理装置10は、ECC（Elliptic Curve Cryptosystem）プロセッサ101、CPU（Central Processing Unit）102、ROM（Read-Only Memory）103、I/F104、EEROM（Electrically Erasable ROM）105、RAM（Random Access Memory）106と、これらを接続するデータバス107を備える。また、この復号処理装置10は、PA、を行うために、消費電力を測定するオシロスコープ20がVcc及びGNDに接続されているものとする。ECCプロセッサ101は、I/F104を介して外部より取得した暗号文Ｃに対し、EEPROM105内に保持されている個人鍵dに基づき以下に記す処理を行う。また、CPU102は、復号処理装置10を制御する。また、ROM103は、ECCプロセッサ101、CPU102により実行されるプログラムを格納する。また、I/F104は、復号処理装置10に対するデータの入出力を仲介する。また、EEROM105は、電気的にデータを消去可能なROMであり、ECCにおける個人鍵dを格納する。また、RAM106は、ECCプロセッサ101、CPU102により実行されるプログラムを一時的に格納する。
【００８４】
次に、復号処理装置10の機能ブロックの一例を図３を参照しつつ説明する。復号処理装置10は、べき乗剰余演算部１（第１べき乗剰余演算部、第２べき乗剰余演算部）、合成部２、シフト解除部３を備える。これら各機能部は、ECCプロセッサ101が以降に説明するアルゴリズムを有するプログラムを実行することで実現される。
【００８５】
べき乗剰余演算部１は、素数ｐ、ｑ、および公開鍵ｅ、個人鍵ｄである場合、これらを用いて、暗号文ｃから平文ｍを算出する際、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、法ｐとしたべき乗剰余演算を行うことで値ｍ’pを算出する。
【００８６】
また、べき乗剰余演算部１は、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃpを基数とし、法ｐとしたべき乗剰余演算を行うことで値ｍ’qを算出する。
【００８７】
合成部２は、べき乗剰余演算部１によって演算されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する。
【００８８】
シフト解除部３は、合成部２によって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、平文ｍを算出する。
【００８９】
上記前提技術での課題を解決するための基本的なアイデアを図４に示す。攻撃４を防ぐために前提技術の対策を用いようとすると、前提技術で示した問題を有していた。すなわち、基数cをランダム化する方法では、ランダム化した結果を解除する必要があるため、その処理を実行するために、計算時間を２倍に大きくする必要がある。これらの問題が発生する理由は、前提技術の対策が、CRTあり復号処理における基数cをランダム化することに、これらの課題の原因があった。ランダム化において用いられる定数もしくは乱数をRと表記すると、最終的にcd (mod n)を計算するために、
m:= (c×R)d ×(R-1)d (mod n)
で表される計算を実行している。すなわち、(c×R)dで表されるランダム化された値を解除し、cd (mod n)に戻すために、(R-1)d (mod n)で表される値を必要としている。この値を得るために、前提技術の対策ではCRT復号処理をさらに1回実行するため計算量の増大を招いた。つまり、基数のランダム化を実行するためには、追加コストとして計算量、もしくはメモリ領域が必要である。
【００９０】
本実施の形態は、この点を鑑み、課題を解決するために、基数によるランダム化ではなく、指数によるシフト化(およびランダム化)を用いる。ただし、これらのランダム化もしくはシフト化された値が、CRT合成前に解除される場合、cdp (mod p)もしくはcdq (mod q)の値を計算途中で発生させることとなり、攻撃４に対して脆弱となるので、このランダム化もしくはシフト化されたデータの解除は、CRT合成が終了後に実行する。これは、1905によるCRT合成によりms:=cd-s (mod n)が計算されるので、この計算結果に対して1906においてcs (mod n)をm:=ms× cs (mod n)=cd-s ×cs (mod n) =cd (mod n)に従い乗算することで、シフト化もしくはランダム化を解除しcd (mod n)を得る。シフト化/ランダム化の解除をCRT合成後に行うことで、攻撃４を防ぐことができ、攻撃４に対して脆弱であるとの課題１を解決できる。
【００９１】
sの値が1024-bitなどの大きな値である場合、本実施の形態に必要な追加コストとして、大きな計算量もしくはメモリ領域を必要とするが、本実施の形態が用いる、指数によるシフトの場合sはs=2,3程度の小さな値で安全性を確保できるため、対策に必要な追加コストは非常に小さい。具体的にはcから(cs) (mod n)を計算し、1905の計算結果に対して乗算するための手間が追加コストとなる。cは既に与えられているため、s=2,3程度の小さな値に対してcs(mod n)を計算するための計算量的なコストは高々sであり、全体の計算量からは無視できるほど小さい。すなわち課題２が解決される。
【００９２】
また、cs (mod n)を計算するのに必要な追加メモリは、パラメータsを格納するためのメモリ領域であるが、これはlog2sビットである。s=2,3などの小さな値の場合、高々2ビットでしかないため、非常に小さなメモリ領域の追加コストであり、課題３が解決される。
【００９３】
また、本実施の形態が攻撃４に対して安全であるための条件は、公開鍵eとシフトパラメータsに対して、e×s> 3が成立することである。RSA暗号の公開鍵eは、e≧3を満たすため、sが2以上の値であるならばこの条件は必ず満たされるので、s=2,3程度の小さな値でよい。e×s > 3が攻撃４に対して安全であるための条件である理由については後に述べる。e×s>3の条件が守られれば、sの値は攻撃者に公開されても安全である。すなわち、パラメータsの漏洩があった場合でも、安全性を保つことができる。
【００９４】
よって、本実施の形態で開示した方法を用いることで、課題１，２，３を全て解決したCRTあり復号処理を実現することができる。
【００９５】
ここで、本実施の形態において、e×s>3が攻撃４に安全である判定基準の説明について説明する。本実施の形態で開示した方法を用いて攻撃４に対して安全とするためのパラメータ設定の判定基準として、公開鍵eと指数のシフトパラメータsに関して、e×s>3の条件を推奨する。以下では、この安全性の基準の根拠について説明を行う。
【００９６】
安全性判断の根拠として、攻撃４の拡張型の攻撃を以下に説明する。この拡張型の攻撃を用いることで、攻撃者が制御可能なxに対し、xg (mod p)の計算処理を行っているときの消費電力を測定することで、pの全体のビットのうち、上位1/gの割合を占めるビット値を推定できる。この性質は、以下の(EXTEND＿DPA)として表記される。
(EXTEND＿DPA)：素数pに対し、復号処理装置10がxg (mod p)の計算処理を行う場合、この処理の消費電力を利用したDPAを実行することで、pの全体のビット値の上位1/gのビット値を攻撃者は得ることができる。
【００９７】
例えばx3 (mod p)の処理を行う暗号プロセッサの場合、この拡張型の攻撃を用いることで、pの上位1/3のビット値が漏洩する。pの部分的なビット値が漏洩したとしても、必ずしもpの値を求めることができるとは限らない。pの部分的なビット値漏洩が許される範囲の一般的な基準としては、文献：Johannes Blomer and Alexander May, ”New Partial Key Exposure Attacks on RSA”, CRYPTO 2003, pp.27-43, LNCS2729に開示されており、この基準に基づくと、pの上位1/2のビット値が漏洩した場合、n=p×qの素因数分解に成功することが知られている。よって、上記の拡張型の攻撃を考慮した場合、pの部分的なビット値が漏洩するのは上位1/2より小さく抑える必要がある。
【００９８】
このような拡張型の攻撃を考える理由は、sによる指数シフトを用いることで、x (mod p)の計算はなくなるが、代わりにy (es - 1) (mod p)の計算は実行されるためである。なぜなら、1903に示すm’p= cpdp-s (mod p)の処理に、c=xe (mod n)を代入すると、(xe)dp=x (mod p)の性質を考慮することで、
m'p = (xe)dp - s (mod p) = (xe)dp×(xe)-s=x(1-es) (mod p) = y(es - 1) (mod p)
（ただし、y=x-1 (mod n )であり、x-1 (mod p)と等しい。）
を得るからである。本実施の形態の対策処理は上記の計算処理を含むため、この計算処理に攻撃４の拡張型DPAを実行した場合でも、漏洩するpの部分的なビット値は上位1/2未満に抑える必要がある。(EXTEND＿DPA)を適用することで、e×s - 1 > 2が安全性のための条件であることがわかる。すなわち、e×s>3が、この拡張型の攻撃を用いた場合でも、RSA暗号の安全性を保つための条件である。
【００９９】
次に、（EXTEND＿DPA）に示した、攻撃４の拡張型攻撃の原理と方法について説明する。
【０１００】
攻撃４は、攻撃者が制御可能なxに対して、図２０に示したDPA攻撃法を用いて、x+ε<pを判定する。図２０のDPA攻撃法がx +ε<pを判定できる理由は、攻撃者が制御可能、かつx≦ai≦x+εを満たすデータ列aiに対し、ai (mod p)で表されるデータがread, writeされているときの消費電力を測定し、1002, 1003に記される差分曲線を作成した結果、全ての差分曲線に十分な高さのスパイクが出現した場合、全てのデータ列aiに対してai<pと判断できるのでai≦x+ε<p、と判断できるためである。
【０１０１】
この判定法は、定数gに対して(ai)g (mod p)で表されるデータがread, writeされたときの消費電力を測定した場合に拡張できる。この拡張型DPAを図５に示す。
【０１０２】
この攻撃が成功する原理は、図２０の攻撃と同様である。Z=Xg (mod Y)で記される剰余演算結果は、Xg<Yの場合剰余演算の実装アルゴリズムに関係なくZ=Xgとなる。つまり、出力結果Zとして復号処理装置10内部にZとしてreadもしくはwriteされる値Zは、X<Yの場合Z=Xとなる。上記のG1, G0は、x≦ai < x + εで記されるすべての基数aiについて(ai)g<p、すなわち(x+ε)g<pであった場合、ai (mod p)として計算される値はすべてaiであり、この値が復号処理装置10内部のメモリにread, writeされる値となる。ai (mod p)の演算結果が全てG1,j, G0,jに含まれる’0’、’1’の個数は、j=0,1,…, log2ε - 1全ての差分曲線について大きく偏ることになるので、全てのjに関して、G1,j - G0,j で記される電力差分曲線上に図１９（Ｂ）に記されるようなスパイクが出現し、そうでなければスパイクが出現しない、もしくは高さが低いスパイクとなる。
【０１０３】
よって、G1,j - G0,j で記される電力差分曲線上に図１９（Ｂ）に記されるようなスパイク、十分な高さで出現する場合、(x+ε)g<pであると判定できる。
【０１０４】
図５に示す電力解析法を、図１６に示した二分探索アルゴリズムの404に適用することで、(x+ε)g<pを満たすxの最大値を求めることができる。言い換えれば、(x+ε)g の値がｐに最も近い値となる整数xの値を求めることができる。このようなxを求めることで、攻撃者はpの上位1/gのビット値を求めることができる。なぜなら、(x+ε)g=pつまり、x=p1/g-εであり、このxをg乗することで、pの近似値を得ることができる。計算式を図６に示すと、図６（Ａ）で示した数式において、pの次数が(g-2)/g以下の項は、pの大きさに比べたら非常に小さいため、図６（Ｂ）で示したように近似できる。つまり、xのg乗値を計算することで、pの近似値を、誤差がεg×p(g-1)/gの範囲内で求めることができる。εg×p(g-1)/gは、pのおよそ下位(g-1)/gの割合のビットに影響を及ぼす誤差であるので、pの上位1/gの割合を占めるビットはこの誤差の影響を受けないことになる。つまり、攻撃者は(x+ε)gの値がpにもっと近いxを、図１６に示した二分探索と図５に示したDPAを用いて求め、このxに対してxgを計算することで、pの上位1/gの割合のビット値を推定することができる。
【０１０５】
（実施例）
図４におけるアルゴリズムによって、sの与え方が２通り(乱数 or 定数)、および1906に示すcs (mod n)の計算法が3通り(バイナリ法使用によるlog2s回乗算2通り、もしくはs回乗算の1通り)、2×3=6通りの実施例を考えることができる。以下ではそれぞれについて説明する。cs (mod n)をバイナリ法で計算する方法では、計算量が2×log2sに減少する代わりに、log2nビットのワーク変数を追加で1つ必要とする。そのため、log2nビットの追加メモリが必要となるが、このワークメモリを追加した場合でも、(課題３)に記されるような3(log2n)/2ビットの追加メモリより少ないため優れた方法である。s=2,3程度の小さなパラメータを用いる限りは、cs(mod n)の計算のためにs回乗算を行う実施例の方が、ワークメモリを必要せず、乗算回数もほぼ同等のため効率的である。
【０１０６】
（実施例１）
実施例１で使用するアルゴリズムを図７に示す。本実施例においては、sを定数として与え、かつcs (mod n)を計算するために、cをs回乗算する方法を用いている(2106)。図１５に示したCRTあり復号処理との違いは、2103,2104にて定数sを用いた指数のシフト処理を実行していること、このシフト結果をCRT合成後に解除するために、2106においてcをs回乗算していることである。
【０１０７】
追加の計算量コストはこの処理に必要な計算量によって与えられる。T=log2nと表記した場合、2103、2104のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これをs回実行する場合s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量はsT2であり、これらの比率は(s×T2)/(T3/4)=(4s)/Tである。例えば、T=log2n=1024とした場合、s=2,3の値を用いたときは、追加の計算量の比率は12/1024以下であり、1%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１０８】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、シフト解除のためのs回乗算である。s=2,3程度の小さな値の場合、高々2-bitであり、この追加コストは無視できるほど小さい。
【０１０９】
（実施例２）
実施例２で使用するアルゴリズムを図８に示す。本実施例においては、sを乱数として与え(2200)、かつcs (mod n)を計算するために、cをs回乗算する方法を用いている(2206)。図3に示したCRTあり復号処理との違いは、2203,2204にて定数sを用いた指数のランダム化処理を実行していること、このランダム化結果をCRT合成後に解除するために、2206においてcをs回乗算していることである。
【０１１０】
追加の計算量コストはこの処理に必要な計算量によって与えられる。T=log2nと表記した場合、2203, 2204のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これをs回実行する場合s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量はsT2であり、これらの比率は(s×T2)/(T3/4)=(4s)/Tである。例えば、T=log2n=1024とした場合、s=1,2,3から乱数で選択する方法の場合、追加の計算量の比率は12/1024以下であり、1%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。sを4ビットの乱数とした場合でも、4s/T=16×4/1024<0.07すなわち7%の増加であるため、影響は無視できるほど小さい。ただし、sをさらに大きくする場合、実施例3,4,5,6のように、cs(mod n)をバイナリ法で計算する実施例の方が、計算量の観点からは効率的である。
【０１１１】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、ランダム化解除のためのs回乗算である。s=2,3程度の小さな値の場合、高々2-bitであり、この追加コストは無視できるほど小さい。
【０１１２】
（実施例３）
実施例３で使用するアルゴリズムを図９に示す。本実施例においては、sを定数として与え、かつcs (mod n)を計算するために、left-to-rightバイナリ法を用いることで2×log2s回乗算する方法を用いている(2307-2310)。
【０１１３】
追加の計算量コストは、left-to-rightバイナリ法を実行するための計算量であり、2×log2sによって与えられる。T=log2nと表記した場合、2303、2304のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これを2×log2s回実行する場合2×log2s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量は(2×log2s)×T2であり、これらの比率は(2×log2s×T2)/(T3/4)=(8×log2s)/Tである。例えば、T=log2n=1024とした場合、sに8ビットの値を用いたときは、追加の計算量の比率は64/1024<0.07であり、7%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１１４】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、left-to-rightバイナリ法を実行するためのワーク領域Wのメモリ領域log2nである。sが8ビット程度の値である場合、追加メモリの合計量は8+log2nであり、対策３で必要とされる1.5×log2nの追加メモリ量と比較した場合、一般的なRSAパラメータではlog2n ≧1024であることを考慮すると、8+log2n < 1.5×log2nであり、本実施例の方が小さな追加メモリ量による処理を実現できる。
【０１１５】
（実施例４）
実施例４で使用するアルゴリズムを図１０に示す。本実施例においては、sを定数として与え、かつcs (mod n)を計算するために、right-to-leftバイナリ法を用いることで2×log2s回乗算する方法を用いている(2407-2410)。
【０１１６】
バイナリ法がright-to-left法であることを除けば、実施例３と同一である。
追加の計算量コストは、right-to-leftバイナリ法を実行するための計算量であり、2×log2sによって与えられる。T=log2nと表記した場合、2403, 2404のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これを2×log2s回実行する場合2×log2s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量は(2×log2s)×T2であり、これらの比率は(2×log2s×T2)/(T3/4)=(8×log2s)/Tである。例えば、T=log2n=1024とした場合、sに8ビットの値を用いたときは、追加の計算量の比率は64/1024<0.07であり、7%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１１７】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、right-to-leftバイナリ法を実行するためのワーク領域Wのメモリ領域log2nである。sが8ビット程度の値である場合、追加メモリの合計量は8+log2nであり、対策３で必要とされる追加メモリ量である1.5×log2nと比較した場合、一般的なRSAパラメータではlog2n≧1024であることを考慮すると、8+log2n < 1.5×log2nであり、本実施例の方が小さな追加メモリ量による処理を実現できる。
【０１１８】
（実施例５）
実施例５で使用するアルゴリズムを図１１に示す。本実施例においては、sを乱数として与え、かつcs (mod n)を計算するために、left-to-rightバイナリ法を用いることで2×log2s回乗算する方法を用いている(2507-2510)。
【０１１９】
sを乱数として与える(2500)以外は、実施例３と同一である。追加の計算量コストは、left-to-rightバイナリ法を実行するための計算量であり、2×log2sによって与えられる。T=log2nと表記した場合、2503、2504のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これを2×log2s回実行する場合2×log2s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量は(2×log2s)×T2であり、これらの比率は(2×log2s×T2)/(T3/4)=(8×log2s)/Tである。例えば、T=log2n=1024とした場合、sに8ビットの値を用いたときは、追加の計算量の比率は64/1024<0.07であり、7%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１２０】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、left-to-rightバイナリ法を実行するためのワーク領域Wのメモリ領域log2nである。sが8ビット程度の値である場合、追加メモリの合計量は8+log2nであり、対策３で必要とされる追加メモリ量である1.5×log2nと比較した場合、一般的なRSAパラメータではlog2n≧1024であることを考慮すると、8+log2n < 1.5×log2nであり、本実施例の方が小さな追加メモリ量による処理を実現できる。
【０１２１】
（実施例６）
実施例６で使用するアルゴリズムを図１２に示す。本実施例においては、sを乱数として与え、かつcs (mod n)を計算するために、right-to-leftバイナリ法を用いることで2×log2s回乗算する方法を用いている(2607-2610)。
【０１２２】
sを乱数として与える(2600)以外は、実施例4と同一である。追加の計算量コストは、right-to-leftバイナリ法を実行するための計算量であり、2×log2sによって与えられる。T=log2nと表記した場合、2603, 2604のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これを2×log2s回実行する場合2×log2s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量は(2×log2s)×T2であり、これらの比率は(2×log2s×T2)/(T3/4)=(8×log2s)/Tである。例えば、T=log2n=1024とした場合、sに8ビットの値を用いたときは、追加の計算量の比率は64/1024<0.07であり、7%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１２３】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、right-to-leftバイナリ法を実行するためのワーク領域Wのメモリ領域log2nである。sが8ビット程度の値である場合、追加メモリの合計量は8+log2nであり、対策３で必要とされる追加メモリ量である1.5×log2nと比較した場合、一般的なRSAパラメータではlog2n≧1024であることを考慮すると、8+log2n < 1.5×log2nであり、本実施例の方が小さな追加メモリ量による処理を実現できる。
【０１２４】
（効果）
本実施の形態による効果を、以下に説明する。本発明を用いることで、課題１、課題２,課題３の全てを解決することができ、また、シフト値であるパラメータsの漏洩があった場合でも、安全性を保つことができる。
【０１２５】
課題１は攻撃４に対する脆弱性であり、本実施の形態で開示した方法を用いることで攻撃４を防ぐことができる。
【０１２６】
課題２は計算量に関する追加コストであり、本実施の形態で開示した方法を用いることで、対策３のような2倍の計算量を必要とせず、図１５に示した対策無しの方法と比較して、1%〜7%という非常に小さな計算量オーバヘッドにより攻撃４への対策を実現することができる。
【０１２７】
課題３はメモリに関する追加コストであり、本実施の形態の実施例１、２を用いることで、log2sビットのメモリ追加量のみとなる。これは、対策３は、nが1024ビットの場合において1536ビットのメモリ追加が必要であるのに対し、実施例１，２では、s=2,3のような小さなパラメータを設定することで、2ビットのメモリ追加のみで良く、優れた方法である。また、本実施の形態の実施例３、４、５、６を用いることで、log2n+log2sビットのメモリ追加量が必要となる。これは実施例１、２よりは大きなメモリ量であるが、nが1024ビット、sが8ビット程度の小さな場合1032ビットのメモリ量となり、対策３で必要となる1536ビットと比較すると、同様に本発明のほうが優れた方法である。
【０１２８】
また、本実施の形態で用いているシフト値sは、外部に漏洩してもセキュリティ上問題ない値であるため、本実施の形態の復号処理装置は外部に漏洩することで全ての復号処理装置のセキュリティを危険とするような固定パラメータは存在しないので、優れた方法である。
【０１２９】
更に、本実施の形態における復号処理装置をコンピュータとして提供することができる。また、復号処理装置を構成するコンピュータにおいて上述した各ステップを実行させるプログラムを、復号処理プログラムとして提供することができる。上述したプログラムは、コンピュータにより読取り可能な記録媒体に記憶させることによって、復号処理装置を構成するコンピュータに実行させることが可能となる。ここで、上記コンピュータにより読取り可能な記録媒体としては、ＲＯＭやＲＡＭ等のコンピュータに内部実装される内部記憶装置、ＣＤ−ＲＯＭやフレキシブルディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体や、コンピュータプログラムを保持するデータベース、或いは、他のコンピュータ並びにそのデータベースや、更に回線上の伝送媒体をも含むものである。
【０１３０】
以上、本実施の形態によれば、以下の付記で示す技術的思想が開示されている。
（付記１） 素数である第１素数ｐ、第２素数ｑ、および公開鍵ｅ、個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する復号処理装置であって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算部と、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算部と、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部によって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成部と、
前記合成部によって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除部と、
を備える復号処理装置。
（付記２） 付記１に記載の復号処理装置において、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部、および前記シフト解除部は、２ビットに収まる乱数を前記数値ｓとすることを特徴とする復号処理装置。
（付記３） 付記１に記載の復号処理装置において、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部、および前記シフト解除部は、２ビットに収まる定数を前記数値ｓとすることを特徴とする復号処理装置。
（付記４） 付記１に記載の復号処理装置において、
前記シフト解除部は、left-to-rightバイナリ法によってｃs（ｍｏｄ ｎ）を算出し、前記平文ｍを算出することを特徴とする復号処理装置。
（付記５） 付記１に記載の復号処理装置において、
前記シフト解除部は、right-to-leftバイナリ法を用いて前記平文ｍを算出することを特徴とする復号処理装置。
（付記６） 素数である第１素数ｐ、第２素数ｑ、および公開鍵ｅ、個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する処理をコンピュータに実行させる復号処理プログラムであって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｐを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、
前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、
をコンピュータに実行させる復号処理プログラム。
（付記７） 付記６に記載の復号処理プログラムにおいて、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップ、および前記シフト解除ステップは、２ビットに収まる乱数を前記数値ｓとすることを特徴とする復号処理プログラム。
（付記８） 付記６に記載の復号処理プログラムにおいて、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップ、および前記シフト解除ステップは、２ビットに収まる定数を前記数値ｓとすることを特徴とする復号処理プログラム。
（付記９） 付記６に記載の復号処理プログラムにおいて、
前記シフト解除ステップは、left-to-rightバイナリ法によってｃs（ｍｏｄ ｎ）を算出し、前記平文ｍを算出することを特徴とする復号処理プログラム。
（付記１０） 付記６に記載の復号処理プログラムにおいて、
前記シフト解除ステップは、right-to-leftバイナリ法を用いて前記平文ｍを算出することを特徴とする復号処理プログラム。
（付記１１） 素数である第１素数ｐ、第２素数ｑ、および公開鍵ｅ、個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する復号処理方法であって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、
前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、
をコンピュータが実行する復号処理方法。
（付記１２） 付記１１に記載の復号処理方法において、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップ、および前記シフト解除ステップは、２ビットに収まる乱数を前記数値ｓとすることを特徴とする復号処理方法。
（付記１３） 付記１１に記載の復号処理方法において、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップ、および前記シフト解除ステップは、２ビットに収まる定数を前記数値ｓとすることを特徴とする復号処理方法。
（付記１４） 付記１１に記載の復号処理方法において、
前記シフト解除ステップは、left-to-rightバイナリ法によってｃs（ｍｏｄ ｎ）を算出し、前記平文ｍを算出することを特徴とする復号処理方法。
（付記１５） 付記１１に記載の復号処理方法において、
前記シフト解除ステップは、right-to-leftバイナリ法を用いて前記平文ｍを算出することを特徴とする復号処理方法。
【符号の説明】
【０１３１】
１ べき乗剰余演算部、２ 合成部、３ シフト解除部、１０ 復号処理装置。
【技術分野】
【０００１】
本発明は、復号処理装置内部に格納されている暗号鍵を電力解析攻撃と呼ばれる攻撃から防ぐための耐タンパ性を有する復号処理装置、復号処理プログラム、復号処理方法に関するものである。
【背景技術】
【０００２】
暗号方式は、共通鍵暗号方式と公開鍵暗号方式に大別される。共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵(秘密鍵)を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵(公開鍵)を一般に公開する代わりに、暗号文を復号するための鍵(個人鍵)を受信者のみの秘密情報とすることで安全性を保つ方式である。
【０００３】
また暗号の分野における技術の一つに、解読技術とよばれるものがある。解読技術とは秘密鍵等の秘密情報を暗号文等入手可能な情報から推定する技術のことであり、様々な手法が存在する。その中で最近注目されている技術に、電力解析攻撃(Power Analysis, 以下PA)と呼ばれる手法がある。電力解析攻撃とは、1998年にPaul Kocherによって考案された手法であり、スマートカード等に搭載された暗号デバイスに様々な入力データを与えた時の電力消費データを収集・解析することで、暗号デバイス内部の鍵情報を推定する手法である。電力解析攻撃を用いることで、共通鍵暗号、公開鍵暗号共に暗号デバイスから秘密鍵を推定できることが知られている。
【０００４】
電力解析攻撃には、単純電力解析(Single Power Analysis、以下SPA)、電力差分攻撃(Differential Power Analysis、以下DPA)の2種類が存在する。SPAは暗号デバイスにおける単一の電力消費データの特徴から秘密鍵の推定を行う方式、DPAは多数の電力消費データの差分を解析することで秘密鍵の推定を行う方式である。
【０００５】
ここでRSA暗号について説明する。RSA暗号は、素因数分解の困難さに基づいた安全性を持つ暗号である。1024-bitの２つの素数p,qに対し、p,qから合成数n=p×qを計算することは容易であるが、nのみから素因数p,qを求めることは困難である(素因数分解の困難さ)ことが安全性の前提となっている暗号である。RSA暗号は、暗号化、復号の２種類の機能を持つ。復号は、中国人剰余定理(Chinese Remainder Theorem, 以下CRT)を利用しない復号(CRTなし復号)と、CRTを利用する復号(CRTあり復号)の２種類が知られている。暗号化、CRTなし復号、CRTあり復号のそれぞれを、図１３、図１４、図１５に示す。
【０００６】
図１３、図１４に示す暗号化処理、CRTなし復号処理は非常に単純である。暗号化処理においては、平文mを基数、公開鍵eを指数、合成数nを法としたべき乗剰余演算c:= me(mod n)を計算することで暗号文cを出力する。CRTなし復号処理においては、暗号文cを基数、個人鍵dを指数、合成数nを法としたべき乗剰余演算m:=cd(mod n)を計算することで平文mを出力する。ただし、個人鍵dは、公開鍵eに対してe×d=1(mod(p-1)(q-1))を満たす値である。べき乗剰余演算の方法については、バイナリ法やwindow法など、複数の計算アルゴリズムが知られており、どのアルゴリズムを用いるかによってSPA、DPAへの耐性が異なる。CRTあり復号は、CRTなし復号の計算量を削減した高速版のアルゴリズムである。一般的に、べき乗剰余処理の計算量は、
(指数のビット長)×(法のビット長)×(法のビット長)
に比例する。例えば、p、qが1024-bit、nが2048-bitのRSA暗号の場合、dのビット長は2048-bitである。なぜなら、e×d=1(mod(p-1)(q-1))すなわちd=e-1(mod(p-1)(q-1))であり、dの値は0<d<(p-1)×(q-1)であるので、dのビット長は(p-1)(q-1)と同じ、つまり2048-bitである。この場合、指数剰余演算に必要な計算量は、
2048×2048×2048=8589934592
である。一般的にCRTなしのRSA復号においては、指数のビット長は法のビット長とほぼ同一となる。つまりCRTなしのRSA復号の計算量は、法のビット長の3乗に比例する。
【０００７】
これに対し、図１５に示すCRTあり復号処理は、CRTなし復号の1/4に計算量を削減できることが知られている。CRTあり復号処理は、以下のCRT-1,CRT-2,CRT-3の３段階から構成される。
(CRT-1) 暗号文cに対する法p,qによる剰余演算(図１５, 301, 302)
(CRT-2) 法p,qによるべき乗剰余演算(図１５, 303, 304)
(CRT-3) 法p,qのべき乗剰余結果から、法nのべき乗剰余結果の算出(CRT合成) (図１５, 305)
CRTあり復号処理の計算の大部分(95%以上)は、CRT-2に示されるべき乗剰余処理であるが、これはcp=c(mod p)もしくはcq=c(mod q)を基数、個人鍵dp=d(mod (p-1))もしくはdq=d(mod (q-1))を指数、素数pもしくはqを法としたべき乗剰余演算である。法p、qのビット長はnの半分つまり1024-bitであり、指数dp、dqのビット長もdの半分つまり1024-bitである。よって、303 もしくは304に示すべき乗剰余処理の計算量は
1024×1024×1024=1073741824
である。つまり、2048-bitのべき乗剰余処理の1/8である。1/8の計算量の処理を2回繰り返すので、CRTあり復号処理の計算量は、CRTなしの計算量の(1/8)×2=1/4である。
【０００８】
CRTあり復号処理を用いることで、CRTなし復号の1/4の計算量、つまり4倍の高速化を実現することができる。その反面、図１５に示すとおり、素数p,qを用いた演算が多いという問題がある。RSA暗号の安全性は、n=p×qの素因数分解の困難さに基づいているため、素数p,qの値が攻撃者に漏洩した場合、RSA暗号は安全ではなくなる。このような、素数p,qを用いた演算処理は、消費電力がp,qと相関しやすいため、PAによりp,qが漏洩しやすいという問題がある。
【０００９】
PAは、個人鍵を用いた処理である図１４のCRTなし復号、もしくは図１５に示したCRTあり復号処理を実装した暗号デバイスをターゲットとして、d,dp,dq,p,qなどの個人鍵を求める攻撃を攻撃者が行うための手段として知られている。以下では、図１４、図１５に対する、従来知られたSPA,DPA攻撃について説明を行う。
【００１０】
（電力解析攻撃）
（SPAの概略）
ここで、SPAの概略について説明する。SPAは、単一の電力波形を観察し、得られた情報を用いることで、暗号デバイス内部の個人鍵を推定する攻撃である。暗号処理の内容と、消費電力波形の形状に相関がある暗号デバイスに対して有効な攻撃である。
【００１１】
（SPAを用いた電力解析攻撃１（CRTあり復号をターゲット）：攻撃１）
SPAを用いた、CRTあり復号をターゲットとした電力解析攻撃(以下、攻撃１)について説明する。
【００１２】
図１５に示したCRTあり復号処理をターゲットとしたSPA攻撃が、特許文献１にて開示されている。これは、301, 302に示す、素数p,qによる剰余処理をターゲットとしている。この攻撃の成功の可否は、301,302の剰余処理の実装形態に依存する。その実装形態は、以下に示すように、Z=X mod Yを計算する際に、XとYの大小比較を行い、X<YならばYをそのまま剰余結果Zとして出力し、X≧Yと判定された場合のみ、剰余演算Z=X (mod Y)を計算して出力する方法である。暗号デバイスがこの実装を用いてCRTあり復号処理を行っていることが、特許文献１にて開示されている攻撃が成立する必須条件である。本方法は、すなわち、Z=X (mod Y)の演算に対し、
if (X<Y) then output X as Z
if (X≧Y) then calculate Z=X (mod Y) and output Z
の処理を行う（以下、この処理をMOD＿ALGと称す）。
【００１３】
上記MOD＿ALGの処理においては、入力Xと法Yの間の大小関係を判定し、X<Yならば剰余演算を実行せず、X≧Yの場合のみ剰余演算を実行する。つまり、XとYの大小関係に応じて、剰余演算の実行の有無が決定する。もし、攻撃者が剰余演算の実行の有無が消費電力を用いて観察できる場合、暗号デバイスの内部データであるXとYの大小関係を消費電力によって知ることができる。この性質を図１５の301, 302に応用することで、攻撃者は素数pもしくはqを解読できる。301, 302では、入力されたcに対して素数p,qによる剰余処理が行われる。スマートカードなどの暗号デバイスにおける実装では、private key(dp,dq,p,q,u)はデバイス内部に格納された値であり外部からは入力できない値であるのに対し、暗号文cは攻撃者を含めた第三者が外部から入力できる値であることに注意されたい。つまり、攻撃者が制御可能なcに対して、c<pであるかc≧pであるかどうかの判定を、301,302に示した剰余演算処理の消費電力を観察することで行うことができる。この判定ができれば、図１６に示す２分探索を用いることで容易にpを求めることができる。
【００１４】
図１６は、pminにp-εの最小値を、pmaxにp-εの最大値を保持しながら、この最大値と最小値の幅を半分ずつに短くすることを繰り返すことで、pの候補値を絞り込むアルゴリズムである。
【００１５】
ただし、εは電力解析を用いた場合の判定誤差の最大値を表す、ε≧0のパラメータである。パラメータεの大きさは用いる攻撃手法によって変化する。このパラメータεは、404で行っているpmid+ε<pの真偽を判定するための手段に応じて変化する。この判定手段として、図１５で示したCRTあり復号に対してCRT＿DEC(pmid)を入力し、SPAを実行することで、pmid<pであるかpmid≧pであるかを判定する場合、ε=0である。後で述べるDPAを用いた攻撃の場合、パラメータεの大きさは1000程度の値となる。
【００１６】
401に示す通り、pminの初期値は0、pmaxの初期値は2α(αはpのビット長)により初期化される。以下402-407のループにおいて、pminとpmaxの差分を半分ずつに短くしながら、pの範囲を絞り込む処理を行う。この絞込み処理は、pmaxとpminの中間値pmidを計算し、pmidとpの大小関係の判定を、消費電力を用いた攻撃により行うことで実施する。
【００１７】
403に記すように、pmaxとpminの中間値pmidは、pmid=(pmax+pmin)/2によって与える。このpmidに対して、消費電力を用いた攻撃を行うことで、pmid+ε<pの判定を行う。
【００１８】
pmid+ε<pが真である場合、pmid<p-ε<pmaxであることを意味する。よってpmaxはそのままで、pmidが新しいp -εの最小値となるため、pmin:=pmidの処理が405にて行われる。
【００１９】
pmid+ε<pが偽である場合、pmin≧p-εであることを意味する。よってpminはそのままで、pmidが新しいp-εの最大値となるため、pmax:= pmid（尚、「：＝」の表記は右辺の結果を左辺に代入することを意味する）の処理が405にて行われる。
【００２０】
この処理を繰り返すことで、pの最大値pmaxと最小値pminの差が半分となる処理が繰り返され、402行目に記されるようにpmax-pmin≦πまで小さくなったら、pの範囲を十分絞り込めたと判断しpの候補値を出力する。
【００２１】
408は、402-407の処理によって、p-εの範囲を十分絞り込めた(差分をπ以下)結果から、pの最大値と最小値を決定する処理を行っている。ε≧0に対してpmin≦p-ε≦pmaxである場合、pの最小値はpminであるが、最大値はpmax+εであるので、pの最大値pmaxに対してpmax:=pmax+εの処理を実行している。この処理の結果、pmax-pmin≦π+εとなる。
【００２２】
409において[pmin,pmin+1,…,pmax]をpの候補値として出力し終了する。403-407のループは、1回実行するごとにpの候補値の個数が半分となる処理を繰り返すため、このループの回数は、αに比例した計算時間で終了する。例えば、pが1024bitの場合、高々1024回で終了するので、非常に効率よく素数pを求めることができる。
【００２３】
（DPAの概略）
次に、DPAについて説明する。DPAは、複数の電力波形を観察し、それらの複数の消費電力間の差分を取ることで、暗号デバイス内部の個人鍵を推定する攻撃である。DPAは、暗号デバイス内部でread, writeされるデータと消費電力の間に相関がある環境において有効である。一般的に、消費電力は暗号デバイス内部でread, writeされるデータに含まれるバイナリ形式のデータの’1’に比例して大きくなる、という性質が知られている。DPAはこの性質を利用することで、個人鍵を求めることができる。
【００２４】
（DPAを用いた電力解析攻撃１（CRTなし復号をターゲット）：攻撃２）
DPAを用いたCRTなし復号をターゲットとした電力解析攻撃（以降、攻撃２）について説明する。RSA暗号に対するDPA攻撃のうち、最もポピュラーな方法として、べき乗剰余処理cd(mod n)を実行する際の消費電力を測定することで、指数dを求める攻撃が知られている。これは、図１４に示すCRTなし復号に対して有効な攻撃である。これらの個人鍵が攻撃者に漏洩した場合、任意の暗号文を復号できるため、RSA暗号の安全性を保つことができない。つまり、素数p,qと同様に、個人鍵dはSPA,DPAの攻撃から保護すべき重要な資産である。
【００２５】
この攻撃を成功させるためには、暗号デバイス内部で実行されているべき乗剰余アルゴリズムの処理方式が何であるかを攻撃者が知っている必要がある。しかし、べき乗剰余アルゴリズムの処理方式の種類は、基本的にバイナリ法、もしくはwindow法と呼ばれるものに大別され、その種類は非常に限られており、べき乗剰余アルゴリズムの種類ごとに考えうる攻撃法を全て試したとしても、攻撃者にとって高々数倍の手間でしかないため、この条件は攻撃者にとって大きな問題とならない。
【００２６】
以下では、暗号デバイスに実装されたべき乗剰余アルゴリズムがwindow法であり、攻撃者がそのことを知っている、という前提において、べき乗剰余cd(mod n)の処理の消費電力から指数dを求める攻撃法について説明する。以下はwindow法を例としているが、バイナリ法など他のべき乗剰余アルゴリズムに対してもDPAは有効である。
【００２７】
ここで、window法の演算とwindow法に対するDPA攻撃について説明する。べき乗剰余処理は、指数d、基数c、法nに対して、m=cd(mod n)を満たすvを計算する処理である。この処理を効率的に行うためのアルゴリズムとして、window法という方法が知られている。指数dの2進表現をd=(du-1,du-2,...,d0)2と表記した時、window法を用いてm= cd(mod n)を計算する指数剰余演算のアルゴリズムを図１７に示す。図１７が行っている演算の概要を図１８に示す。
【００２８】
図１７の処理を説明する。最初にw[x]=cx(mod n)を満たすテーブルwの作成処理を0<x<2kについて行う。テーブル作成処理の後、u-bit値のd=(du-1,du-2,...d0)2をk-bitごとに分割したブロック値としてのu/k個の数列bi(i=0,1,..)を生成する。即ちbi=(dik+k-1,...,dik)2である。このbiを用いたテーブル索引処理(m:=m×w[bi])と、m:=m2^k(mod n)で示される2k乗算を繰り返すことでm=cd(mod n)を計算する。
【００２９】
以下では、攻撃者がDPAを用いて、window法を行う暗号デバイス内部の指数dを推定する方法を説明する。RSA暗号において、指数dは個人鍵であり、攻撃者から保護すべき重要な情報資産である。一般的に、指数dは1024-bit以上の値であるため、この値を総当りによって求めようとする場合、21024の手間がかかり不可能であるが、DPAは、window法の処理である指数dをk-bitずつ分割して処理するという性質に着目する。例えば、図１８に示した処理においては、指数dを4-bitずつbiとして分解し、このbiに関する中間データm:=m×w[bi](mod n)を算出する。このm:=m×w[bi]の値は、暗号デバイスの内部データとしてread, writeされるため、m:=m×w[bi]の計算結果mをreadもしくはwriteする処理の消費電力を測定することで、攻撃者はbiに関する情報を得ることができる。biは高々k-bit(図１８の例の場合4-bit)のデータでしかなく、このk-bit値biに関する総当りをdのすべてのビット値に関して繰り返すことで、攻撃者は効率よく指数dの値を知ることができる。たとえば、k=2かつdが2048-bitの場合、dは1024個の2-bitブロックbiに分割されるが、攻撃者はこの2048-bitすべてのビット値に関する総当りを実行する必要はなく、2-bitつまり4通りの総当りを1024回繰り返せばよく、その手間は4×1024=4096でしかないため、効率よく指数dの値を求めることができる。
【００３０】
このk-bitごとの総当りおいて攻撃者は、2k個のbi候補値のうち正しい値を、DPAを用いて選出する必要がある。この選出方法について以下に説明する。
【００３１】
例えばk=2, d=(d5d4d3d2d1d0)2とした場合、b2=(d5d4)2,b1=(d3d2)2,b0=(d1d0)2となり、図１７に示すwindow法を用いたべき乗剰余演算は以下の(処理1)〜(処理5)を経てm=cd(mod n)を計算する。
(処理1) m = 1×w[b2](mod n) = cb2(mod n)
(処理2) m = (w[b2])4(mod n) = c4b2(mod n)
(処理3) m = ((w[b2])4)×w[b1](mod n) = c4b2ab1(mod n)
(処理4) m = (((w[b2])4)×w[b1])4(mod n) = c16b2c4b1(mod n)
(処理5) m = (((w[b2])4)×w[b1])4×w[b0] (mod n) = c16b2c4b1 cb0(mod n)=cd (mod n)
【００３２】
暗号デバイスがwindow法を実装していることを攻撃者が知っているならば、暗号デバイス内部で上記の(処理1)〜(処理5)が行われていることも攻撃者が知っている。以下に示す手順に従いDPAが行うことで、biの候補値であるb2,b1,b0の値が推定され、dの値が推定される。
【００３３】
501. 暗号デバイスに対し、基数としてN個のai(i=1,2,...,N)を与え、aid(mod n)の処理を行わせる。このときのデバイスの電力消費データP(ai,time)をそれぞれのiについて測定する。
502. 2-bit値b2の値がb'2であると予想し、b2=b'2と判定されるまで、以下の(１),(２)に記される手順を繰り返す。
(１) (処理 1)の中間データvに着目し、予想したb'2からm=aib2'(mod n)の値をシミュレートし、P(ai,time)(i=1,2,..,N)を以下の２つの集合G1,G0に分類する。
・G1 = [P(ai,time)| aib'2(mod n)の最下位ビット=1]
・G0 = [P(ai,time)| aib'2(mod n)の最下位ビット=0]
(２) G1,G0から、Δ=(G1の平均電力) - (G0の平均電力) で表される電力差分曲線Δを作成する。その結果、例えば図１９（Ａ）のような時間-電力曲線で示すような電力消費であるものに対し、図１９（Ｂ）のようなスパイクが出現した場合、b2=b'2と判定し(b2の推定に成功)、図１９（Ｃ）のような平坦な曲線であればb2≠b'2と判定する。
503. 2-bit値b1の値がb'1であると予想し、b1=b'1と判定されるまで、以下の(１),(２)に記される手順を繰り返す。
(１) (処理3)の中間データvに着目し、既に推定したb2及び予想したb'1からm=ai4b2aib1'(mod n)の値をシミュレートし、P(ai,time)(i=1,2,..,N)を以下の２つの集合G1,G0に分類する。
・G1 = [P(ai,time)| ai4b2aib'1(mod n)の最下位ビット=1]
・G0 = [P(ai,time)| ai4b2aib'1(mod n)の最下位ビット=0]
(２) G1,G0から、Δ=(G1の平均電力)-(G0の平均電力)で表される電力差分曲線Δを作成する。その結果、図１９（Ｂ）のようなスパイクが出現した場合、b1=b'1と判定し(b1の推定に成功)、図１９（Ｃ）のような平坦な曲線であればb1≠b'1と判定する。
504. 2-bit値b0の値がb'0であると予想し、b0=b'0と判定されるまで、以下の(１)、(２)に記される手順を繰り返す。
(１) (処理5)の中間データvに着目し、推定に成功したb2、b1及び予想したb'0からm=ai16b2ai4b1aib0'(mod n)の値をシミュレートし、P(ai,time)(i=1,2,..,N)を以下の２つの集合G1,G0に分類する。
・G1 = [P(ai,time)| ai16b2ai4b1aib'0(mod n)の最下位ビット=1]
・G0 = [P(ai,time)| ai16b2ai4b1aib'0(mod n)の最下位ビット=0]
(２) G1,G0から、Δ=(G1の平均電力)-(G0の平均電力)で表される電力差分曲線Δを作成する。その結果図１９（Ｂ）のようなスパイクが出現した場合、b0=b'0と判定し(b0の推定に成功)、図１９（Ｃ）のような平坦な曲線であればb0≠b'0と判定する。
【００３４】
biの推定が正しい場合は、攻撃者がシミュレートしたmの値が、暗号デバイス内部でも発生し、read、write処理が行われているので、上記のG1-G0で示されるように、mに含まれる’0’,’1’の個数が集合G1、G0間で極端に偏るような差分電力波形を作成することで、消費電力に関する差分が発生し、この消費電力差が図１９（Ｂ）で示したようなスパイク波形として観察される。
【００３５】
biの推定が誤っている場合は、攻撃者がシミュレートしたmの値が、暗号デバイス内部では発生しておらず、シミュレートした値とまったく異なる値に関してread, write処理が行われているので、上記のG1-G0で示されるように、mに含まれる’0’,’1’の個数が集合G1、G0間で極端に偏るような差分電力波形を作成してもスパイク波形を得ることはできない。biの推定が誤っている場合、G1、G0はP(ai,time)(i=1,2,..,N)全体の集合Gをランダムに2通りに分類した集合となるため、G1、G0の間の平均消費電力はほぼ同一となり、図１９（Ｃ）に示すような平坦な差分波形となる。
【００３６】
（DPAを用いた電力解析攻撃２（CRTあり復号をターゲット）：攻撃３）
次に、DPAを用いたCRTあり復号をターゲットとした電力解析攻撃(以下、攻撃３と称す)について説明する。CRTあり復号処理における(CRT-1)、すなわち素数p,qによる暗号文(基数)cの剰余演算に対するSPAによる攻撃はすでに説明したとおりである。この処理に対しては、DPAも実行可能である。SPAによる攻撃の場合、攻撃者が制御し、暗号デバイスに対して入力した基数cに対して、c≧pであるか、c<pであるかどうかの判別を単発の消費電力波形によって行っていた。これに対して、DPAを用いた攻撃の場合、暗号デバイスに対して入力した基数cに対して、c+ε<pであるかどうかの判別を、複数の消費電力波形間の差分を用いて行う。ただし、εはエラーパラメータである。c+ε<pの判別に成功した場合、図１６に示す二分探索法を用いることでpの値の候補を絞り込むことができる。ただし、図１６の探索を用いても、pの候補数はε+π以下にならない。しかし、pの候補が総当り可能な程度に小さな値(例えばε+π<240)であれば、ε+πはpの値を絞り込むための大きな問題とはならない。
【００３７】
前述の(CRT-1)に対するSPA攻撃は、Z=X (mod Y)で記される剰余演算アルゴリズムが (MOD＿ALG)に従う、つまりXとYの大小関係に応じて処理を切り替えるようなアルゴリズムが実装されていることを前提としているのに対し、以下で述べるDPA攻撃は、XとYの大小関係に関係なくZ=X (mod Y)の演算処理を常に実行するような暗号デバイスに対しても有効な攻撃である。
【００３８】
攻撃者が制御可能なxについて、DPAを用いることでx+ε<pの判定を行うアルゴリズムを図２０に示す。SPAを用いた攻撃と異なり、正確に判定を行うわけではなく、エラーパラメータεに対してx+ε<pを満たすかどうかの判定であり、暗号デバイスの消費電力特性によってはεが小さすぎると正確な判定が行えない可能性がある。これは、SPAが単一の電力波形を用いた判定を行うのに対し、DPAでは複数の波形間の差分を用いた判定、という違いによるものであり、エラーパラメータεはDPAを成功させるのに必要な波形の個数に比例する。一般的にDPAを成功させるためには、1000個程度のデータ間の差分があれば成功することが知られているため、εも1000程度の小さな値である。
【００３９】
図２０の攻撃アルゴリズムが成功する原理について説明する。Z=X (mod Y)で記される剰余演算結果は、X<Yの場合剰余演算の実装アルゴリズムに関係なくZ=Xとなる。つまり、出力結果Zとして暗号デバイス内部にZとしてreadもしくはwriteされる値Zは、X<Yの場合Z=Xとなる。上記のG1、G0は、x≦ai<x+εで記されるすべての基数aiについてai<p、すなわちx+ε<pであった場合、ai (mod p)として計算される値はすべてaiであり、この値が暗号デバイス内部のメモリにread、writeされる値となる。ai (mod p)の演算結果が全てG1,j, G0,jに含まれる’0’’1’の個数は、j=0,1,…, log2ε - 1全ての差分曲線について大きく偏ることになるので、全てのjに関して、G1,j - G0,j で記される電力差分曲線上に図１９（Ｂ）に記されるようなスパイクが出現する。逆に、ai =x, x+1, …, x+εで記されるすべての基数aiについてai≧pである、すなわちx≧pの場合は、ai (mod p)の演算結果は、整数λiに対してai - λipとなる。εがpに対して十分小さい場合は、λiは非常に高い確率でiの値に関係ない定数λとなることを考慮するとai (mod p)の演算結果は、ai - λpとなる。aiとai - λpの最下位0,1,…, log2ε - 1番目のビット値とは、λpの減算によるキャリーの伝播の影響に応じて同一であったり異なったりする。つまり、ai - λpの最下位0,1,…, log2ε- 1番目のビット値は、aiの最下位0,1,…, log2ε- 1番目のビット値と全て同一とはならず、aiとλpの値に応じて変動する。すなわち、G1,j - G0,j で記される電力差分曲線上に全てスパイクが出現するとは限らず、jの値によってはスパイクが出現しない、もしくは出現したとしても高さが低いスパイクとなり、全てのjに関して十分な高さのスパイクを得ることはできない。
【００４０】
ai =x, x+1, …, x+εで記されるすべての基数aiについて、ai≧pであるaiと、ai<pであるaiが混在する場合も同様であり、全てのjについてスパイクが出現するとは限らない。
【００４１】
よって、G1,j - G0,j で記される電力差分曲線上に図１９（Ｂ）に記されるようなスパイクが、全てのｊについて十分な高さで出現する場合、x+ε<pであると判定できる。
【００４２】
（電力解析攻撃への対策）
図１４、図１５に示すRSA暗号処理に関して、攻撃１、攻撃２、攻撃３に記したSPA, DPAによる攻撃法が知られている。これらの攻撃に対して、対策も同様に知られている。以下では、攻撃１，２，３に対する、従来知られた２種類の対策法(以下、対策１、対策２)について説明を行う。
【００４３】
（対策１）
対策１を図２１に示す。図２１は、1101, 1102が(CRT-1)に対応する処理であり、1103, 1104,1105, 1106が(CRT-2)に対応する処理であり、1107, 1108が(CRT-3)に対応する処理である。
【００４４】
図２１に示す定数R, Rp, Rqは暗号デバイス内部に格納された定数であり、外部には非公開の値である。これらの定数を用いた処理を行うことで、攻撃１，３を防ぐことができる。
【００４５】
図１５と異なり、1101、1102においては、R>pかつR>qを満たす定数Rをcに乗算した新しい基数c×Rに対して、c’p := c×R (mod p)、 c’q := c×R (mod q)による剰余演算を実行する。このRによる補正がかかったc’p, c’qを基数、dp,dqを指数、p,qを法とした指数剰余演算を1103,1104にて実行し、結果をm’p, m’qに格納する。この結果計算される値は、m’p=(c×R)dp (mod p)=Rdp×cdp (mod p)およびm’q=(c×R)dq (mod q)=Rdq×cdq (mod q)である。これを、図１５の303, 304に示したべき乗剰余で計算される値である、mp=cdp (mod p)およびmq=cdq (mod q)と比較すると、定数Rdp, Rdqによる差異がある。この差異を補正し、cdp (mod p), cdq (mod q)を計算するための処理を1105, 1106にて実行する。これは、事前計算された定数Rp=R-dp (mod p), Rq=R-dq (mod q)を用いて、mp := m’p× Rp (mod p)=cdp×Rdp×R-dp (mod p)=cdp (mod p), mq := m’q× Rq (mod q)=cdq×Rdq×R-dq (mod q)=cdq (mod q)の計算処理により実行する。mp=cdp (mod p)およびmq=cdq (mod q)への補正は、1107にて記されるCRT合成を行うために実施する処理である。これらの値を1107に示すCRT合成への入力として与えた処理を実行することで、m:= (( u×(mq - mp) ) (mod q) )×p + mp =cd (mod n)が計算され、出力される。
【００４６】
図２１に示した対策１により、1101、1102において、定数Rを乗算してからp,qによる剰余演算を実行する処理により、攻撃１への対策を実現している。RはR>pおよびR>qを満たす定数であるため、特殊な入力c=0の場合を除き、常にc×R≧pおよびc×R≧qが成立するので、(MOD＿ALG)に示すZ=X (mod Y)の計算においては、常にX≧Yの分岐しか発生しないため、攻撃者は有効な情報を得ることはできない。c=0の場合のみ、X<Yの分岐が発生するが、これは0<pという自明な情報を得ているのに過ぎない。
【００４７】
よって、図２１に示す対策１を用いることで、(MOD＿ALG)に示す分岐処理からpに関する有効な情報を攻撃者は得ることができないため、攻撃１を防ぐことができる。
【００４８】
さらに、図２１に示す対策１は、攻撃３を防ぐ効果を有する。なぜなら、1101、1102において、攻撃者にとって未知の値である定数Rを用いてc×R (mod p)、c×R (mod q)を計算するため、攻撃者はcに対するc×Rの値を予想することができないので、c×R (mod p)の値も予想することができない。もし、Rの値が攻撃者にとって既知であれば、cの代わりにc=g×R-1 (mod n)を入力する攻撃３を実行することで、同様の攻撃を実行可能である。なぜなら、1101で計算される値は、c×R (mod p) = (g×R-1)×R (mod p) = g (mod p)となり、攻撃者が制御可能なgに対する剰余演算を実行されるので、攻撃者は攻撃３と同じ状況を作り出すことができるからである。ここでは、R-1 (mod n) = R-1 (mod p)の関係式を利用しており、R-1 (mod n) = R-1 (mod p)となる理由は、n=p×qおよび任意の整数aに対して、a-1 (mod n) = a-1 (mod p)= a-1 (mod q)という性質が一般的に知られていることによるものである。ただし、Rが未知の定数であれば、攻撃者はgからg×R-1 (mod n)を計算することができないため、対策1は攻撃３に対して安全である。
【００４９】
言い換えれば、対策１の安全性は、定数R, Rp, Rqが攻撃者に対して未知の値であることが前提である。これらの定数が攻撃者に対して未知である限りは、安全である反面、潜在的なリスクが存在する。暗号デバイスの全固体で用いられる共通の定数値の場合、１個の固体からこれらの定数が漏洩した場合、全固体のセキュリティが脅かされるという潜在的なリスクである。さらに、対策１を用いる場合、定数R, Rp, Rqをデバイス内部に格納する必要があるため、これらの値を記録するためのメモリ追加コストが必要である。定数Rは、R>q, R>qであるので、最低p,qのビット長以上のメモリ領域が必要である。p,qのビット長がnのビット長の半分であるとすると、定数Rに必要なメモリ領域は(log2n)/2ビットである。Rp, Rqに必要なメモリ領域はp,qと同じであり、それぞれ(log2n)/2ビットである。これらを合計すると、R, Rp, Rqの格納に必要なメモリ領域は3(log2n)/2ビットとなる。一般的なRSA処理においては、nは1024-bit以上の値が用いられているため、1536-bit以上の記憶領域が必要となる。計算量に関する追加コストは、1101, 1102に示すRとの乗算、1105, 1106に示すRp, Rqとの乗算処理であるが、これらの追加計算量コストは全体の計算量に占める割合は非常に低く、無視できるほど小さい。
【００５０】
上記をまとめると、対策１は攻撃１，３を防ぐことができる。対策１に必要な追加コストは、定数R, Rp, Rqを格納するためのメモリ領域であり、その大きさは3(log2 n)/2ビット(最低1536ビット)と評価できる。さらに、潜在的なリスクとして、定数R, Rp, Rqが全暗号デバイス固体間で共通の定数である場合、１個の固体からこれらの定数が漏洩することで、全固体のセキュリティが危険となる可能性がある。
【００５１】
（対策２）
攻撃２に対する防御法として、多数の対策法が知られている。いずれの対策法にも共通することは、cd (mod n)の計算を実行する際に、暗号デバイス内部で乱数を発生させた上で、この乱数を用いて、cd (mod n)の計算過程で発生する中間データをランダム化する処理を含んでいることである。
【００５２】
攻撃２においては、攻撃者は入力cから、cd (mod n)の計算過程において発生する中間データ値のシミュレートを行い、このシミュレートに基づいてG1 - G0で示される差分曲線を作成するが、この計算過程における中間データをランダム化することで、攻撃２におけるシミュレーションを無効化することで、攻撃２を防ぐ。この方法では、cd (mod n)のべき乗剰余の計算過程で発生する中間データをランダム化するが、最終的な出力として通常のべき乗剰余処理と同じ値cd (mod n)を出力する必要があるため、ランダム化の解除があわせて必要となる。中間データをランダム化による攻撃２の対策は様々な方法が知られているが、これらの対策法ごとに、ランダム化とランダム化の解除方法が異なり、これらの方法の差異によって、対策に必要となる計算量やメモリなどの追加コストが異なる。
【００５３】
以下では、攻撃２に対する代表的な対策法である、指数のランダム化法について説明を行う（対策２）。
【００５４】
図２２は指数のランダム化法による攻撃２への対策法（対策２）を示している。対策の基本的なアイデアとしては、べき乗剰余計算における指数をランダム化することで攻撃２に対策を行っている。この指数値のランダム化は、指数dの代わりに、ランダム化された指数d’=d+r×φ(n)を用いることで行う。ただし、rは20-bitの乱数、φ(x)は法xに対する位数であり、法xに対する位数は、任意の整数aに対して、aφ(x) (mod x) = 1 となる性質を備える。素数p,qに対してn=p×qの場合、φ(n)=(p-1)(q-1)、φ(p)=p-1、φ(q)=q-1であることが知られている。
【００５５】
20-bit乱数rによって与えられる指数d+r×φ(n)のビット列はランダムに変化するため、べき乗剰余処理過程における中間データはランダム化されるが、最終的に計算される値は常にcd (mod n)と同じとなる（図２３参照）。最終的に計算される値がcd (mod n)であるのは、cd + r×φ(n) = cd × (cφ(n))r (mod n)であり、位数の性質により、任意の整数cに対してcφ(n)=1(mod n)であるため、任意の乱数rに対してcd+r×φ(n) = cd ×(cφ(n))r (mod n)= cd × (1)r (mod n) = cd (mod n)が成立するからである。
【００５６】
対策２に伴う追加コストであるが、計算時間については、指数dの代わりにd’=d+r×φ(n)を用いる分のコストが発生する。dのビット長はlog2(n)であるのに対し、d’のビット長はr×φ(N)のビット長であり、log2n + 20 で与えられる。べき乗剰余演算の処理時間は、(法のビット長)× (法のビット長)× (指数のビット長)であるが、対策２を用いることで、指数のビット長がlog2(n)からlog2n+20に伸びるため、対策２を用いない場合と比較すると計算時間は(log2n+20)/(log2n)となる。log2n=1024の場合、1044/1024=1.02であるため、計算時間に関する追加コストは若干発生するが、全体の計算時間に占める割合は非常に小さいことが特徴であるため、効率的な対策法として知られている。メモリ領域に関する追加コストは、乱数rを格納するための20-bitの領域と、図１４に示すCRTなし復号演算では用いられなかった位数φ(n)を格納するためのlog2nビットの領域が必要となる。
【００５７】
上記をまとめると、対策２は攻撃２を防ぐことができる。対策２に必要な計算量コストは、指数dの代わりに指数d’=d+r×φ(n)を用いるコストであり、計算量は図１４に示す対策なしの方法と比較すると(log2n+20)/(log2n)倍となるが、nが1024-bitの場合増加分は2％と非常に小さい。メモリ領域に関する追加コストは、乱数rと位数φ(n)の分を合わせて、(20+log2n)ビット必要となる。一般的にはnは1024ビット以上であるため、1044ビット以上の追加メモリを必要とする。
【００５８】
（対策１と対策２のまとめ）
ここで、従来知られる対策１、対策２の特徴に関してまとめる。対策１（すなわち図１５への対策）は、攻撃１、３に対して有効であり、計算量に関する追加コストは図１５のものと等倍、メモリに関する追加コストは3(log2n)/2ビット（≧1536ビット）となる。尚、対策１は、定数R、Rp、Rqが全固体共通の場合、R、Rp、Rqの漏洩により全固体が脆弱となる問題を含んでいる。一方、対策２（すなわち図１４への対策）は、攻撃２に対して有効であり、計算量に関する追加コストは図１４の(log2n+20)/(log2n)倍、メモリに関する追加コストは(20+log2n)ビット（≧1044ビット）となる。
【００５９】
（対策１と対策２に関する問題点）
以上のように、図１４、図１５に示したRSA復号処理に対して、攻撃１、２、３に示した攻撃法が知られているが、それらは対策１、２にて示した従来の対策法によって防ぐことができる。つまり、従来知られた攻撃１、２、３は、従来知られた対策法１、２によって防ぐことができる。
【００６０】
尚、DESやAESなどの共通鍵暗号方式に対して、SPA、DPAを用いた推定法、およびRSA暗号、楕円曲線暗号などの公開鍵暗号に対してSPA、DPAを用いた推定法が以下に記す文献に開示されている。また、サイドチャネルアタックに対して安全性の高い復号化演算方法も、以下に記す文献に開示されている。
【先行技術文献】
【特許文献】
【００６１】
【特許文献１】特許４０８６５０３号公報
【特許文献２】国際公開第００／５９１５７号パンフレット
【非特許文献】
【００６２】
【非特許文献１】Paul Kocher, Joshua Jaffe, and Benjamin Jun, "Differential Power Analysis," in proceedings of Advances in Cryptology-CRYPTO'99, Lecture Notes in Computer Science vol. 1666, Springer-Verlag, 1999, pp. 388-397
【非特許文献２】Thomas S.Messerges, Ezzy A.Dabbish and Robert H.Sloan "Power Analysis Attacks of Modular Exponentitiation in Smartcards", Cryptographic Hardware and Embedded Systems(CHES'99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp.144-157
【非特許文献３】Jean-Sebastein Coron “Resistance against Differential Power Analysis for Elliptic Curve Crytosystems”,Cryptographic Hardware and Embedded Systems (CHES’99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp.292-302, 1999
【非特許文献４】Alfred J.Menezesほか著”HANDBOOK OF APPLIED CRYPTOGRAPHY”(CRC press) pp.615
【発明の概要】
【発明が解決しようとする課題】
【００６３】
しかし一方、これらの対策法が新たな攻撃法に対して耐性をもつとは限らない。一般的に、セキュリティにおける対策法は、全ての攻撃法に対して等しく耐性を持たないと意味を成さない。たとえば、10種類中9種類の攻撃法を対策法によって防ぐことができたとしても、残り1種類の攻撃を防ぐことができなければ、その攻撃法によって個人鍵が漏洩することで、攻撃者は暗号化された全てのデータを自由に復号することができるからである。よって、暗号デバイスにおける対策法は、全ての攻撃法に対して耐性を持つことが求められる。よって、対策法は、従来の攻撃法１、２、３のみに耐性をもつだけではなく、これらの攻撃法を拡張した新たな攻撃法にも耐性を持つことが求められる。
【００６４】
以下では、従来の攻撃３を拡張した新たな攻撃法の例（攻撃４）について説明した上で、この攻撃法は従来の対策１，２では防ぐことができないことを説明する。
【００６５】
（攻撃４について）
攻撃３に示される図１５に示すCRTあり復号処理への攻撃を拡張することで、新しい攻撃法が考えられる。攻撃３は、図１５の301、302に示す、cp:=c (mod p)、 cq := c (mod q)に示す剰余演算をターゲットとしている。この処理をターゲットとすることで、攻撃者が制御可能なcに対する剰余演算を行い、図２０に示すDPAをベースとした攻撃法を用いることで、素数pに対してc<p-εの判定(εはエラーパラメータ、1000程度の小さな値)を行うことができ、この情報を用いることで、素数pの候補を総当り可能な個数までに絞り込むことができる。
【００６６】
この考え方を応用することで、図１５の303に示すmp:=cpdp(mod p)、 mq:=cqdq(mod q)の演算処理に図２０に示すDPAをベースとした攻撃法を用いることで、同様に素数pの候補数を絞り込むことができる。以降、この攻撃法を攻撃４と呼び、その方法を説明する。
【００６７】
攻撃４の基本的なアイデアを図２４に示す。攻撃３と異なるのは、図１５のCRT＿DEC(c)の与え方である。従来は、攻撃者がx+ε<pの判定を行うためのxを生成し、このxをそのまま図１５の入力であるcにCRT＿DEC(x)として与えていた。これに対し、攻撃４では、攻撃者がx+ε<pの判定を行うためのxを生成し、このxに対して、公開鍵e,nから計算した値y=xe (mod n)を生成した上で、CRT＿DEC(y)を図１５への入力として与える。公開鍵e,nは、暗号デバイス外部に公開されている値であるため、攻撃者はxからxe (mod n)を自由に生成できる。
【００６８】
xの代わりに、xe (mod n)を与えることで、図１５の303, 304に示すべき乗剰余処理、すなわち図２４における1513, 1514においては、それぞれmp:=(xe)dp (mod p) = x (mod p)、 mq:=(xe)dq (mod q) = x (mod q)が計算され、この値が暗号デバイス内部のメモリに対してread, writeされる処理が発生する(この等式が成立する理由は、RSA暗号の鍵e,dp,dq,p,qに関して、(ae)dp=1 (mod p), (ae)dq = 1 (mod q)が任意の整数aに対して成立するという、公知の性質によるものである。)。つまり、攻撃者が制御可能なxに対して、x (mod p)、 x (mod q) に示す剰余演算が実行されているときと同じ消費電力が発生するため、図２０に示すDPAをベースとした攻撃法を用いることができる。図２０に示すDPAベースの攻撃法を用いることができれば、図１６に示す２部探索により、pの候補数を全数探索可能な個数まで絞り込むことができるため、素数p,qを求めることができる。
【００６９】
この攻撃４は、従来の対策１、２では防ぐことができない。なぜなら、対策１は、CRT合成を正しく実行するために、CRT合成を行う直前の処理段階である図２１の1105, 1106において、定数Rp、Rqを乗算することでmp=cdp (mod p), mq=cdq (mod q)を計算している。つまり、c=xe (mod n)を入力することで、1105、1106における計算結果はx (mod p)、 x(mod q)となるため、攻撃４は実行可能である。
また対策２は、CRTあり復号処理への対策ではないが、べき乗剰余に対する対策であるため、図１５の303, 304のべき乗剰余処理に適用することができる。ただし、この適用を行ったとしても、攻撃４を防ぐことはできない。なぜなら、図２３に示すように、べき乗剰余の中間データをランダム化するが、最終的に計算される値は常に一定であり、この処理を図１５の303, 304のべき乗剰余処理に適用した場合、mp=cdp (mod p), mq=cdq (mod q)が計算されることになる。よって、攻撃４は実行可能である。このように、従来の対策法１、２は攻撃４に対する耐性がないという問題を有している。
【００７０】
本発明は上述した問題点を解決するためになされたものであり、攻撃４に対する対策が備えられた復号処理装置、復号処理プログラム、復号処理方法を提供することを目的とする。
【課題を解決するための手段】
【００７１】
復号処理装置は、素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する復号処理装置であって、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算部と、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算部と、前記第１べき乗剰余演算部、前記第２べき乗剰余演算部によって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成部と、前記合成部によって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除部と、を備える。
【００７２】
また、復号処理プログラムは、素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し、平文ｍを算出する処理をコンピュータに実行させる復号処理プログラムであって、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｐを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、をコンピュータに実行させる。
【００７３】
さらに、復号処理方法は、素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し、平文ｍを算出する復号処理方法であって、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、をコンピュータが実行する方法である。
【発明の効果】
【００７４】
上記攻撃４に対する耐性を有することができ、従来の対策と組み合わせることで、より対タンパ性を確保することができる。
【図面の簡単な説明】
【００７５】
【図１】本実施の形態の前提技術に係る、基数のランダム化を用いた攻撃４に対する対策法を示す図である。
【図２】本実施の形態に係る復号処理装置のハードウェア構成の一例を示す図である。
【図３】本実施の形態に係る復号処理装置の機能ブロックの一例を示す図である。
【図４】本実施の形態に係る復号処理装置が実施する基本処理の一例示す図である。
【図５】本実施の形態に係る、攻撃者が制御可能なデータ値に対しxg （mo d p）の演算結果のread,write処理を実行する復号処理装置をターゲットとし て、DPAを用いて（x+ε）g＜pの判定を行う攻撃アルゴリズムを示す図であ る。
【図６】本実施の形態に係る、pの近似値を取得するための数式を示す図である。
【図７】本実施の形態に係る実施例１の処理の一例を示す図である。
【図８】本実施の形態に係る実施例２の処理の一例を示す図である。
【図９】本実施の形態に係る実施例３の処理の一例を示す図である。
【図１０】本実施の形態に係る実施例４の処理の一例を示す図である。
【図１１】本実施の形態に係る実施例５の処理の一例を示す図である。
【図１２】本実施の形態に係る実施例６の処理の一例を示す図である。
【図１３】RSAの暗号処理の手法を示す図である。
【図１４】RSAのCRTなし復号処理処理の手法を示す図である。
【図１５】RSAのCRTあり復号処理処理の手法を示す図である。
【図１６】二分探索と電力解析を組み合わせた、pの範囲を絞り込む攻撃アルゴリズムを示す図である。
【図１７】window法を用いたべき乗剰余処理を示す図である。
【図１８】window法の処理を示す図である。
【図１９】消費電力曲線、スパイクが出現する電力差分曲線、および平坦な電力差分曲線を示す図である。
【図２０】攻撃者が制御可能なデータ値xに対して、x (mod p)の演算結果のread,write処理を実行する復号処理装置に対し、DPAを用いてx+ε<pの判定を行う攻撃アルゴリズムを示す図である。
【図２１】攻撃１、攻撃３への対策アルゴリズムを示す図である。
【図２２】攻撃２への対策アルゴリズムを示す図である。
【図２３】対策２の中間データランダム化と、ランダム化を解除した演算結果を出力する過程を示す図である。
【図２４】攻撃４の処理内容について説明する図である。
【発明を実施するための形態】
【００７６】
本実施の形態では、
（課題１）攻撃４に対して脆弱である。
との課題を解決する対策法について記載する。また、本実施の形態が提供する対策法は、単に上記攻撃４を防ぐだけではなく、対策に伴う計算量・メモリの追加コストを最小限とするという優れた特徴を有する。本発明の対策法について説明する前に、攻撃４を防ぐ基本となる対策法を前提技術として説明する。この対策法も、基数の値を変更する、というアイデアに基づいているが、このような基数を変更するというアイデアでは、攻撃４に対策することはできても、別の問題点を有することについても説明する。その後、本実施の形態による攻撃４への対策法を説明する。
【００７７】
（前提技術）
図１に前提技術となる対策法（以下、対策３）を示す。これは、基数cに対してそのままCRTあり復号演算を実行するのではなく、乱数Sを発生し(1601)、c×S(mod n)によるランダム化を行った上でCRTあり復号による演算処理CRT＿DEC(c×S (mod n))を実行し、結果をワーク変数領域Wに格納する(1602)。その結果、W=(c×S)d (mod n)が計算される。この乱数Sによるランダム化を解除するために乱数Sの逆数によるCRTあり復号演算をCRT＿DEC(S-1 (mod n))により実行し、結果をmに格納する。その結果、m=S-d (mod n)が計算される。最後に、m:=W×m (mod n)により、m:= (c×S)d × S-d = cd (mod n)の演算を行い、ランダム化を解除した結果をmに格納する。
【００７８】
これらの一連の演算においては、CRT＿DECに入力する基数がSによってランダム化されるため、攻撃４を防ぐことができる。その反面、対策に伴う追加コストが発生する。計算量的な追加コストとしては、CRTあり復号演算を２回実行するため、計算量が図１５に示す方法の2倍となる。メモリ領域に関する追加コストとしては、乱数Sを格納するためのワーク領域と、1602に示すCRTあり復号結果を格納するためのワーク領域Wが追加となる。Sはp,qと同一のビット長であるため、(log2n)/2ビット必要である。Wはnと同じビット長が必要のため、(log2n)ビット必要である。
【００７９】
これらの追加コスト評価は、実装形態に依存しない最低限の追加コスト評価であり、1602に示すc×S (mod n)を計算するためのメモリ領域や、S-1 (mod n)を計算するための一時的なメモリ領域、およびSの逆数S-1を計算するための計算量コストは無視した、非常に楽観的な評価である。
【００８０】
以上をまとめると、対策３による基数のランダム化処理により、攻撃４を防ぐことはできるが、計算量およびメモリに関する追加コストが発生するという課題を有する。計算量については、図１５に示す方法の2倍の必要であり、メモリに関しては(3log2n)/2の追加コストが必要である。
【００８１】
以下、上述対策３によって生じた課題についてまとめると、
（課題２）図１５で示した、対策なしの方法の２倍の計算量が必要。
（課題３）追加メモリとして、(3log2n)/2（≧1536ビット）のメモリ領域が必要。
となる。
【００８２】
（実施の形態）
上記前提技術の課題を解決するための復号処理装置について、図２にハードウェア構成の一例を、図３に機能ブロックの一例を示す。
【００８３】
まず、復号処理装置のハードウェア構成を図２を参照しつつ説明する。尚、本実施の形態の復号処理装置10は、具体的には例えばスマートカード等の暗号デバイスに組み込まれることができる。図２に示すように、本実施の形態に係る復号処理装置10は、ECC（Elliptic Curve Cryptosystem）プロセッサ101、CPU（Central Processing Unit）102、ROM（Read-Only Memory）103、I/F104、EEROM（Electrically Erasable ROM）105、RAM（Random Access Memory）106と、これらを接続するデータバス107を備える。また、この復号処理装置10は、PA、を行うために、消費電力を測定するオシロスコープ20がVcc及びGNDに接続されているものとする。ECCプロセッサ101は、I/F104を介して外部より取得した暗号文Ｃに対し、EEPROM105内に保持されている個人鍵dに基づき以下に記す処理を行う。また、CPU102は、復号処理装置10を制御する。また、ROM103は、ECCプロセッサ101、CPU102により実行されるプログラムを格納する。また、I/F104は、復号処理装置10に対するデータの入出力を仲介する。また、EEROM105は、電気的にデータを消去可能なROMであり、ECCにおける個人鍵dを格納する。また、RAM106は、ECCプロセッサ101、CPU102により実行されるプログラムを一時的に格納する。
【００８４】
次に、復号処理装置10の機能ブロックの一例を図３を参照しつつ説明する。復号処理装置10は、べき乗剰余演算部１（第１べき乗剰余演算部、第２べき乗剰余演算部）、合成部２、シフト解除部３を備える。これら各機能部は、ECCプロセッサ101が以降に説明するアルゴリズムを有するプログラムを実行することで実現される。
【００８５】
べき乗剰余演算部１は、素数ｐ、ｑ、および公開鍵ｅ、個人鍵ｄである場合、これらを用いて、暗号文ｃから平文ｍを算出する際、ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、法ｐとしたべき乗剰余演算を行うことで値ｍ’pを算出する。
【００８６】
また、べき乗剰余演算部１は、ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃpを基数とし、法ｐとしたべき乗剰余演算を行うことで値ｍ’qを算出する。
【００８７】
合成部２は、べき乗剰余演算部１によって演算されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する。
【００８８】
シフト解除部３は、合成部２によって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、平文ｍを算出する。
【００８９】
上記前提技術での課題を解決するための基本的なアイデアを図４に示す。攻撃４を防ぐために前提技術の対策を用いようとすると、前提技術で示した問題を有していた。すなわち、基数cをランダム化する方法では、ランダム化した結果を解除する必要があるため、その処理を実行するために、計算時間を２倍に大きくする必要がある。これらの問題が発生する理由は、前提技術の対策が、CRTあり復号処理における基数cをランダム化することに、これらの課題の原因があった。ランダム化において用いられる定数もしくは乱数をRと表記すると、最終的にcd (mod n)を計算するために、
m:= (c×R)d ×(R-1)d (mod n)
で表される計算を実行している。すなわち、(c×R)dで表されるランダム化された値を解除し、cd (mod n)に戻すために、(R-1)d (mod n)で表される値を必要としている。この値を得るために、前提技術の対策ではCRT復号処理をさらに1回実行するため計算量の増大を招いた。つまり、基数のランダム化を実行するためには、追加コストとして計算量、もしくはメモリ領域が必要である。
【００９０】
本実施の形態は、この点を鑑み、課題を解決するために、基数によるランダム化ではなく、指数によるシフト化(およびランダム化)を用いる。ただし、これらのランダム化もしくはシフト化された値が、CRT合成前に解除される場合、cdp (mod p)もしくはcdq (mod q)の値を計算途中で発生させることとなり、攻撃４に対して脆弱となるので、このランダム化もしくはシフト化されたデータの解除は、CRT合成が終了後に実行する。これは、1905によるCRT合成によりms:=cd-s (mod n)が計算されるので、この計算結果に対して1906においてcs (mod n)をm:=ms× cs (mod n)=cd-s ×cs (mod n) =cd (mod n)に従い乗算することで、シフト化もしくはランダム化を解除しcd (mod n)を得る。シフト化/ランダム化の解除をCRT合成後に行うことで、攻撃４を防ぐことができ、攻撃４に対して脆弱であるとの課題１を解決できる。
【００９１】
sの値が1024-bitなどの大きな値である場合、本実施の形態に必要な追加コストとして、大きな計算量もしくはメモリ領域を必要とするが、本実施の形態が用いる、指数によるシフトの場合sはs=2,3程度の小さな値で安全性を確保できるため、対策に必要な追加コストは非常に小さい。具体的にはcから(cs) (mod n)を計算し、1905の計算結果に対して乗算するための手間が追加コストとなる。cは既に与えられているため、s=2,3程度の小さな値に対してcs(mod n)を計算するための計算量的なコストは高々sであり、全体の計算量からは無視できるほど小さい。すなわち課題２が解決される。
【００９２】
また、cs (mod n)を計算するのに必要な追加メモリは、パラメータsを格納するためのメモリ領域であるが、これはlog2sビットである。s=2,3などの小さな値の場合、高々2ビットでしかないため、非常に小さなメモリ領域の追加コストであり、課題３が解決される。
【００９３】
また、本実施の形態が攻撃４に対して安全であるための条件は、公開鍵eとシフトパラメータsに対して、e×s> 3が成立することである。RSA暗号の公開鍵eは、e≧3を満たすため、sが2以上の値であるならばこの条件は必ず満たされるので、s=2,3程度の小さな値でよい。e×s > 3が攻撃４に対して安全であるための条件である理由については後に述べる。e×s>3の条件が守られれば、sの値は攻撃者に公開されても安全である。すなわち、パラメータsの漏洩があった場合でも、安全性を保つことができる。
【００９４】
よって、本実施の形態で開示した方法を用いることで、課題１，２，３を全て解決したCRTあり復号処理を実現することができる。
【００９５】
ここで、本実施の形態において、e×s>3が攻撃４に安全である判定基準の説明について説明する。本実施の形態で開示した方法を用いて攻撃４に対して安全とするためのパラメータ設定の判定基準として、公開鍵eと指数のシフトパラメータsに関して、e×s>3の条件を推奨する。以下では、この安全性の基準の根拠について説明を行う。
【００９６】
安全性判断の根拠として、攻撃４の拡張型の攻撃を以下に説明する。この拡張型の攻撃を用いることで、攻撃者が制御可能なxに対し、xg (mod p)の計算処理を行っているときの消費電力を測定することで、pの全体のビットのうち、上位1/gの割合を占めるビット値を推定できる。この性質は、以下の(EXTEND＿DPA)として表記される。
(EXTEND＿DPA)：素数pに対し、復号処理装置10がxg (mod p)の計算処理を行う場合、この処理の消費電力を利用したDPAを実行することで、pの全体のビット値の上位1/gのビット値を攻撃者は得ることができる。
【００９７】
例えばx3 (mod p)の処理を行う暗号プロセッサの場合、この拡張型の攻撃を用いることで、pの上位1/3のビット値が漏洩する。pの部分的なビット値が漏洩したとしても、必ずしもpの値を求めることができるとは限らない。pの部分的なビット値漏洩が許される範囲の一般的な基準としては、文献：Johannes Blomer and Alexander May, ”New Partial Key Exposure Attacks on RSA”, CRYPTO 2003, pp.27-43, LNCS2729に開示されており、この基準に基づくと、pの上位1/2のビット値が漏洩した場合、n=p×qの素因数分解に成功することが知られている。よって、上記の拡張型の攻撃を考慮した場合、pの部分的なビット値が漏洩するのは上位1/2より小さく抑える必要がある。
【００９８】
このような拡張型の攻撃を考える理由は、sによる指数シフトを用いることで、x (mod p)の計算はなくなるが、代わりにy (es - 1) (mod p)の計算は実行されるためである。なぜなら、1903に示すm’p= cpdp-s (mod p)の処理に、c=xe (mod n)を代入すると、(xe)dp=x (mod p)の性質を考慮することで、
m'p = (xe)dp - s (mod p) = (xe)dp×(xe)-s=x(1-es) (mod p) = y(es - 1) (mod p)
（ただし、y=x-1 (mod n )であり、x-1 (mod p)と等しい。）
を得るからである。本実施の形態の対策処理は上記の計算処理を含むため、この計算処理に攻撃４の拡張型DPAを実行した場合でも、漏洩するpの部分的なビット値は上位1/2未満に抑える必要がある。(EXTEND＿DPA)を適用することで、e×s - 1 > 2が安全性のための条件であることがわかる。すなわち、e×s>3が、この拡張型の攻撃を用いた場合でも、RSA暗号の安全性を保つための条件である。
【００９９】
次に、（EXTEND＿DPA）に示した、攻撃４の拡張型攻撃の原理と方法について説明する。
【０１００】
攻撃４は、攻撃者が制御可能なxに対して、図２０に示したDPA攻撃法を用いて、x+ε<pを判定する。図２０のDPA攻撃法がx +ε<pを判定できる理由は、攻撃者が制御可能、かつx≦ai≦x+εを満たすデータ列aiに対し、ai (mod p)で表されるデータがread, writeされているときの消費電力を測定し、1002, 1003に記される差分曲線を作成した結果、全ての差分曲線に十分な高さのスパイクが出現した場合、全てのデータ列aiに対してai<pと判断できるのでai≦x+ε<p、と判断できるためである。
【０１０１】
この判定法は、定数gに対して(ai)g (mod p)で表されるデータがread, writeされたときの消費電力を測定した場合に拡張できる。この拡張型DPAを図５に示す。
【０１０２】
この攻撃が成功する原理は、図２０の攻撃と同様である。Z=Xg (mod Y)で記される剰余演算結果は、Xg<Yの場合剰余演算の実装アルゴリズムに関係なくZ=Xgとなる。つまり、出力結果Zとして復号処理装置10内部にZとしてreadもしくはwriteされる値Zは、X<Yの場合Z=Xとなる。上記のG1, G0は、x≦ai < x + εで記されるすべての基数aiについて(ai)g<p、すなわち(x+ε)g<pであった場合、ai (mod p)として計算される値はすべてaiであり、この値が復号処理装置10内部のメモリにread, writeされる値となる。ai (mod p)の演算結果が全てG1,j, G0,jに含まれる’0’、’1’の個数は、j=0,1,…, log2ε - 1全ての差分曲線について大きく偏ることになるので、全てのjに関して、G1,j - G0,j で記される電力差分曲線上に図１９（Ｂ）に記されるようなスパイクが出現し、そうでなければスパイクが出現しない、もしくは高さが低いスパイクとなる。
【０１０３】
よって、G1,j - G0,j で記される電力差分曲線上に図１９（Ｂ）に記されるようなスパイク、十分な高さで出現する場合、(x+ε)g<pであると判定できる。
【０１０４】
図５に示す電力解析法を、図１６に示した二分探索アルゴリズムの404に適用することで、(x+ε)g<pを満たすxの最大値を求めることができる。言い換えれば、(x+ε)g の値がｐに最も近い値となる整数xの値を求めることができる。このようなxを求めることで、攻撃者はpの上位1/gのビット値を求めることができる。なぜなら、(x+ε)g=pつまり、x=p1/g-εであり、このxをg乗することで、pの近似値を得ることができる。計算式を図６に示すと、図６（Ａ）で示した数式において、pの次数が(g-2)/g以下の項は、pの大きさに比べたら非常に小さいため、図６（Ｂ）で示したように近似できる。つまり、xのg乗値を計算することで、pの近似値を、誤差がεg×p(g-1)/gの範囲内で求めることができる。εg×p(g-1)/gは、pのおよそ下位(g-1)/gの割合のビットに影響を及ぼす誤差であるので、pの上位1/gの割合を占めるビットはこの誤差の影響を受けないことになる。つまり、攻撃者は(x+ε)gの値がpにもっと近いxを、図１６に示した二分探索と図５に示したDPAを用いて求め、このxに対してxgを計算することで、pの上位1/gの割合のビット値を推定することができる。
【０１０５】
（実施例）
図４におけるアルゴリズムによって、sの与え方が２通り(乱数 or 定数)、および1906に示すcs (mod n)の計算法が3通り(バイナリ法使用によるlog2s回乗算2通り、もしくはs回乗算の1通り)、2×3=6通りの実施例を考えることができる。以下ではそれぞれについて説明する。cs (mod n)をバイナリ法で計算する方法では、計算量が2×log2sに減少する代わりに、log2nビットのワーク変数を追加で1つ必要とする。そのため、log2nビットの追加メモリが必要となるが、このワークメモリを追加した場合でも、(課題３)に記されるような3(log2n)/2ビットの追加メモリより少ないため優れた方法である。s=2,3程度の小さなパラメータを用いる限りは、cs(mod n)の計算のためにs回乗算を行う実施例の方が、ワークメモリを必要せず、乗算回数もほぼ同等のため効率的である。
【０１０６】
（実施例１）
実施例１で使用するアルゴリズムを図７に示す。本実施例においては、sを定数として与え、かつcs (mod n)を計算するために、cをs回乗算する方法を用いている(2106)。図１５に示したCRTあり復号処理との違いは、2103,2104にて定数sを用いた指数のシフト処理を実行していること、このシフト結果をCRT合成後に解除するために、2106においてcをs回乗算していることである。
【０１０７】
追加の計算量コストはこの処理に必要な計算量によって与えられる。T=log2nと表記した場合、2103、2104のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これをs回実行する場合s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量はsT2であり、これらの比率は(s×T2)/(T3/4)=(4s)/Tである。例えば、T=log2n=1024とした場合、s=2,3の値を用いたときは、追加の計算量の比率は12/1024以下であり、1%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１０８】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、シフト解除のためのs回乗算である。s=2,3程度の小さな値の場合、高々2-bitであり、この追加コストは無視できるほど小さい。
【０１０９】
（実施例２）
実施例２で使用するアルゴリズムを図８に示す。本実施例においては、sを乱数として与え(2200)、かつcs (mod n)を計算するために、cをs回乗算する方法を用いている(2206)。図3に示したCRTあり復号処理との違いは、2203,2204にて定数sを用いた指数のランダム化処理を実行していること、このランダム化結果をCRT合成後に解除するために、2206においてcをs回乗算していることである。
【０１１０】
追加の計算量コストはこの処理に必要な計算量によって与えられる。T=log2nと表記した場合、2203, 2204のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これをs回実行する場合s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量はsT2であり、これらの比率は(s×T2)/(T3/4)=(4s)/Tである。例えば、T=log2n=1024とした場合、s=1,2,3から乱数で選択する方法の場合、追加の計算量の比率は12/1024以下であり、1%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。sを4ビットの乱数とした場合でも、4s/T=16×4/1024<0.07すなわち7%の増加であるため、影響は無視できるほど小さい。ただし、sをさらに大きくする場合、実施例3,4,5,6のように、cs(mod n)をバイナリ法で計算する実施例の方が、計算量の観点からは効率的である。
【０１１１】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、ランダム化解除のためのs回乗算である。s=2,3程度の小さな値の場合、高々2-bitであり、この追加コストは無視できるほど小さい。
【０１１２】
（実施例３）
実施例３で使用するアルゴリズムを図９に示す。本実施例においては、sを定数として与え、かつcs (mod n)を計算するために、left-to-rightバイナリ法を用いることで2×log2s回乗算する方法を用いている(2307-2310)。
【０１１３】
追加の計算量コストは、left-to-rightバイナリ法を実行するための計算量であり、2×log2sによって与えられる。T=log2nと表記した場合、2303、2304のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これを2×log2s回実行する場合2×log2s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量は(2×log2s)×T2であり、これらの比率は(2×log2s×T2)/(T3/4)=(8×log2s)/Tである。例えば、T=log2n=1024とした場合、sに8ビットの値を用いたときは、追加の計算量の比率は64/1024<0.07であり、7%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１１４】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、left-to-rightバイナリ法を実行するためのワーク領域Wのメモリ領域log2nである。sが8ビット程度の値である場合、追加メモリの合計量は8+log2nであり、対策３で必要とされる1.5×log2nの追加メモリ量と比較した場合、一般的なRSAパラメータではlog2n ≧1024であることを考慮すると、8+log2n < 1.5×log2nであり、本実施例の方が小さな追加メモリ量による処理を実現できる。
【０１１５】
（実施例４）
実施例４で使用するアルゴリズムを図１０に示す。本実施例においては、sを定数として与え、かつcs (mod n)を計算するために、right-to-leftバイナリ法を用いることで2×log2s回乗算する方法を用いている(2407-2410)。
【０１１６】
バイナリ法がright-to-left法であることを除けば、実施例３と同一である。
追加の計算量コストは、right-to-leftバイナリ法を実行するための計算量であり、2×log2sによって与えられる。T=log2nと表記した場合、2403, 2404のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これを2×log2s回実行する場合2×log2s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量は(2×log2s)×T2であり、これらの比率は(2×log2s×T2)/(T3/4)=(8×log2s)/Tである。例えば、T=log2n=1024とした場合、sに8ビットの値を用いたときは、追加の計算量の比率は64/1024<0.07であり、7%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１１７】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、right-to-leftバイナリ法を実行するためのワーク領域Wのメモリ領域log2nである。sが8ビット程度の値である場合、追加メモリの合計量は8+log2nであり、対策３で必要とされる追加メモリ量である1.5×log2nと比較した場合、一般的なRSAパラメータではlog2n≧1024であることを考慮すると、8+log2n < 1.5×log2nであり、本実施例の方が小さな追加メモリ量による処理を実現できる。
【０１１８】
（実施例５）
実施例５で使用するアルゴリズムを図１１に示す。本実施例においては、sを乱数として与え、かつcs (mod n)を計算するために、left-to-rightバイナリ法を用いることで2×log2s回乗算する方法を用いている(2507-2510)。
【０１１９】
sを乱数として与える(2500)以外は、実施例３と同一である。追加の計算量コストは、left-to-rightバイナリ法を実行するための計算量であり、2×log2sによって与えられる。T=log2nと表記した場合、2503、2504のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これを2×log2s回実行する場合2×log2s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量は(2×log2s)×T2であり、これらの比率は(2×log2s×T2)/(T3/4)=(8×log2s)/Tである。例えば、T=log2n=1024とした場合、sに8ビットの値を用いたときは、追加の計算量の比率は64/1024<0.07であり、7%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１２０】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、left-to-rightバイナリ法を実行するためのワーク領域Wのメモリ領域log2nである。sが8ビット程度の値である場合、追加メモリの合計量は8+log2nであり、対策３で必要とされる追加メモリ量である1.5×log2nと比較した場合、一般的なRSAパラメータではlog2n≧1024であることを考慮すると、8+log2n < 1.5×log2nであり、本実施例の方が小さな追加メモリ量による処理を実現できる。
【０１２１】
（実施例６）
実施例６で使用するアルゴリズムを図１２に示す。本実施例においては、sを乱数として与え、かつcs (mod n)を計算するために、right-to-leftバイナリ法を用いることで2×log2s回乗算する方法を用いている(2607-2610)。
【０１２２】
sを乱数として与える(2600)以外は、実施例4と同一である。追加の計算量コストは、right-to-leftバイナリ法を実行するための計算量であり、2×log2sによって与えられる。T=log2nと表記した場合、2603, 2604のべき乗剰余に必要な計算量は、2×(T/2)3=T3/4であるのに対し、cを法nに関して1回乗算するための計算コストは、(法nのビット長)×(法nのビット長)であるので、これを2×log2s回実行する場合2×log2s×T2となる。つまり、基本的な計算量T3/4に対して、追加の計算量は(2×log2s)×T2であり、これらの比率は(2×log2s×T2)/(T3/4)=(8×log2s)/Tである。例えば、T=log2n=1024とした場合、sに8ビットの値を用いたときは、追加の計算量の比率は64/1024<0.07であり、7%程度の増加である。追加の計算量の全体の計算量に対しての影響は無視できるほど小さい。
【０１２３】
メモリに関する追加コストは、定数sを格納するためのメモリ領域log2sと、right-to-leftバイナリ法を実行するためのワーク領域Wのメモリ領域log2nである。sが8ビット程度の値である場合、追加メモリの合計量は8+log2nであり、対策３で必要とされる追加メモリ量である1.5×log2nと比較した場合、一般的なRSAパラメータではlog2n≧1024であることを考慮すると、8+log2n < 1.5×log2nであり、本実施例の方が小さな追加メモリ量による処理を実現できる。
【０１２４】
（効果）
本実施の形態による効果を、以下に説明する。本発明を用いることで、課題１、課題２,課題３の全てを解決することができ、また、シフト値であるパラメータsの漏洩があった場合でも、安全性を保つことができる。
【０１２５】
課題１は攻撃４に対する脆弱性であり、本実施の形態で開示した方法を用いることで攻撃４を防ぐことができる。
【０１２６】
課題２は計算量に関する追加コストであり、本実施の形態で開示した方法を用いることで、対策３のような2倍の計算量を必要とせず、図１５に示した対策無しの方法と比較して、1%〜7%という非常に小さな計算量オーバヘッドにより攻撃４への対策を実現することができる。
【０１２７】
課題３はメモリに関する追加コストであり、本実施の形態の実施例１、２を用いることで、log2sビットのメモリ追加量のみとなる。これは、対策３は、nが1024ビットの場合において1536ビットのメモリ追加が必要であるのに対し、実施例１，２では、s=2,3のような小さなパラメータを設定することで、2ビットのメモリ追加のみで良く、優れた方法である。また、本実施の形態の実施例３、４、５、６を用いることで、log2n+log2sビットのメモリ追加量が必要となる。これは実施例１、２よりは大きなメモリ量であるが、nが1024ビット、sが8ビット程度の小さな場合1032ビットのメモリ量となり、対策３で必要となる1536ビットと比較すると、同様に本発明のほうが優れた方法である。
【０１２８】
また、本実施の形態で用いているシフト値sは、外部に漏洩してもセキュリティ上問題ない値であるため、本実施の形態の復号処理装置は外部に漏洩することで全ての復号処理装置のセキュリティを危険とするような固定パラメータは存在しないので、優れた方法である。
【０１２９】
更に、本実施の形態における復号処理装置をコンピュータとして提供することができる。また、復号処理装置を構成するコンピュータにおいて上述した各ステップを実行させるプログラムを、復号処理プログラムとして提供することができる。上述したプログラムは、コンピュータにより読取り可能な記録媒体に記憶させることによって、復号処理装置を構成するコンピュータに実行させることが可能となる。ここで、上記コンピュータにより読取り可能な記録媒体としては、ＲＯＭやＲＡＭ等のコンピュータに内部実装される内部記憶装置、ＣＤ−ＲＯＭやフレキシブルディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体や、コンピュータプログラムを保持するデータベース、或いは、他のコンピュータ並びにそのデータベースや、更に回線上の伝送媒体をも含むものである。
【０１３０】
以上、本実施の形態によれば、以下の付記で示す技術的思想が開示されている。
（付記１） 素数である第１素数ｐ、第２素数ｑ、および公開鍵ｅ、個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する復号処理装置であって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算部と、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算部と、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部によって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成部と、
前記合成部によって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除部と、
を備える復号処理装置。
（付記２） 付記１に記載の復号処理装置において、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部、および前記シフト解除部は、２ビットに収まる乱数を前記数値ｓとすることを特徴とする復号処理装置。
（付記３） 付記１に記載の復号処理装置において、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部、および前記シフト解除部は、２ビットに収まる定数を前記数値ｓとすることを特徴とする復号処理装置。
（付記４） 付記１に記載の復号処理装置において、
前記シフト解除部は、left-to-rightバイナリ法によってｃs（ｍｏｄ ｎ）を算出し、前記平文ｍを算出することを特徴とする復号処理装置。
（付記５） 付記１に記載の復号処理装置において、
前記シフト解除部は、right-to-leftバイナリ法を用いて前記平文ｍを算出することを特徴とする復号処理装置。
（付記６） 素数である第１素数ｐ、第２素数ｑ、および公開鍵ｅ、個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する処理をコンピュータに実行させる復号処理プログラムであって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｐを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、
前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、
をコンピュータに実行させる復号処理プログラム。
（付記７） 付記６に記載の復号処理プログラムにおいて、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップ、および前記シフト解除ステップは、２ビットに収まる乱数を前記数値ｓとすることを特徴とする復号処理プログラム。
（付記８） 付記６に記載の復号処理プログラムにおいて、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップ、および前記シフト解除ステップは、２ビットに収まる定数を前記数値ｓとすることを特徴とする復号処理プログラム。
（付記９） 付記６に記載の復号処理プログラムにおいて、
前記シフト解除ステップは、left-to-rightバイナリ法によってｃs（ｍｏｄ ｎ）を算出し、前記平文ｍを算出することを特徴とする復号処理プログラム。
（付記１０） 付記６に記載の復号処理プログラムにおいて、
前記シフト解除ステップは、right-to-leftバイナリ法を用いて前記平文ｍを算出することを特徴とする復号処理プログラム。
（付記１１） 素数である第１素数ｐ、第２素数ｑ、および公開鍵ｅ、個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する復号処理方法であって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、
前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、
をコンピュータが実行する復号処理方法。
（付記１２） 付記１１に記載の復号処理方法において、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップ、および前記シフト解除ステップは、２ビットに収まる乱数を前記数値ｓとすることを特徴とする復号処理方法。
（付記１３） 付記１１に記載の復号処理方法において、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップ、および前記シフト解除ステップは、２ビットに収まる定数を前記数値ｓとすることを特徴とする復号処理方法。
（付記１４） 付記１１に記載の復号処理方法において、
前記シフト解除ステップは、left-to-rightバイナリ法によってｃs（ｍｏｄ ｎ）を算出し、前記平文ｍを算出することを特徴とする復号処理方法。
（付記１５） 付記１１に記載の復号処理方法において、
前記シフト解除ステップは、right-to-leftバイナリ法を用いて前記平文ｍを算出することを特徴とする復号処理方法。
【符号の説明】
【０１３１】
１ べき乗剰余演算部、２ 合成部、３ シフト解除部、１０ 復号処理装置。
【特許請求の範囲】
【請求項１】
素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する復号処理装置であって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算部と、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算部と、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部によって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成部と、
前記合成部によって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除部と、
を備える復号処理装置。
【請求項２】
請求項１に記載の復号処理装置において、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部、および前記シフト解除部は、２ビットに収まる乱数を取得し、該乱数を前記数値ｓとすることを特徴とする復号処理装置。
【請求項３】
請求項１に記載の復号処理装置において、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部、および前記シフト解除部は、２ビットに収まる定数を取得し、該定数を前記数値ｓとすることを特徴とする復号処理装置。
【請求項４】
請求項１に記載の復号処理装置において、
前記シフト解除部は、left-to-rightバイナリ法によってｃs（ｍｏｄ ｎ）を算出し、前記平文ｍを算出することを特徴とする復号処理装置。
【請求項５】
請求項１に記載の復号処理装置において、
前記シフト解除部は、right-to-leftバイナリ法を用いて前記平文ｍを算出することを特徴とする復号処理装置。
【請求項６】
素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し、平文ｍを算出する処理をコンピュータに実行させる復号処理プログラムであって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｐを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、
前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、
をコンピュータに実行させる復号処理プログラム。
【請求項７】
素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し、平文ｍを算出する復号処理方法であって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、
前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、
をコンピュータが実行する復号処理方法。
【請求項１】
素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し平文ｍを算出する復号処理装置であって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算部と、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算部と、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部によって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成部と、
前記合成部によって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除部と、
を備える復号処理装置。
【請求項２】
請求項１に記載の復号処理装置において、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部、および前記シフト解除部は、２ビットに収まる乱数を取得し、該乱数を前記数値ｓとすることを特徴とする復号処理装置。
【請求項３】
請求項１に記載の復号処理装置において、
前記第１べき乗剰余演算部、前記第２べき乗剰余演算部、および前記シフト解除部は、２ビットに収まる定数を取得し、該定数を前記数値ｓとすることを特徴とする復号処理装置。
【請求項４】
請求項１に記載の復号処理装置において、
前記シフト解除部は、left-to-rightバイナリ法によってｃs（ｍｏｄ ｎ）を算出し、前記平文ｍを算出することを特徴とする復号処理装置。
【請求項５】
請求項１に記載の復号処理装置において、
前記シフト解除部は、right-to-leftバイナリ法を用いて前記平文ｍを算出することを特徴とする復号処理装置。
【請求項６】
素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し、平文ｍを算出する処理をコンピュータに実行させる復号処理プログラムであって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｐを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、
前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、
をコンピュータに実行させる復号処理プログラム。
【請求項７】
素数である第１素数ｐ、第２素数ｑ、および個人鍵ｄを用いて、暗号文ｃを復号し、平文ｍを算出する復号処理方法であって、
ｄ（ｍｏｄ（ｐ−１））で演算される値ｄpを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｐ）で演算される値ｃpを基数とし、前記第１素数ｐを法としたべき乗剰余演算を行うことで値ｍ’pを算出する第１べき乗剰余演算ステップと、
ｄ（ｍｏｄ（ｑ−１））で演算される値ｄqを数値ｓでシフト演算した値を指数とし、ｃ（ｍｏｄ ｑ）で演算される値ｃqを基数とし、前記第２素数ｑを法としたべき乗剰余演算を行うことで値ｍ’qを算出する第２べき乗剰余演算ステップと、
前記第１べき乗剰余演算ステップ、前記第２べき乗剰余演算ステップによって算出されたｍ’p、ｍ’qと、ｐ-1（ｍｏｄ ｑ）の演算結果である個人鍵ｕとを用いて、
（（ｕ×（ｍ’q−ｍ’p）（ｍｏｄ ｑ））×ｐ＋ｍ’p
を演算することで値ｍsを算出する合成ステップと、
前記合成ステップによって算出された値ｍsを用いて、
ｍs×（ｃs（ｍｏｄ ｎ））（ｍｏｄ ｎ）
を演算することで、前記平文ｍを算出するシフト解除ステップと、
をコンピュータが実行する復号処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【公開番号】特開２０１０−１６６４６３（Ｐ２０１０−１６６４６３Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−８４６４（Ｐ２００９−８４６４）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]