(57)【要約】  u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、指数剰余演算y=ad(mod n)を実行する暗号化方法を前提として、以下の構成を有する。まず、a’=a2(mod n)を計算するステップが実行される。次に、f=(du-1, du-2, ..., d1)2に対して、y=(a’)f(mod n)を計算するステップが実行される。続いて、d0=1であるときにy=y×a (mod n)を計算するステップが実行される。そして、y=ad(mod n)を出力するステップが実行される。最初のステップにより、攻撃者がa=-1や、a=s, -sのように、マイナス値を含むデータを入力しても、乗算もしくは２乗算では常にプラスの値のみを発生させることができるため、SPA、DPA等の電力解析攻撃を用いた秘密鍵の推定を困難にし、高い耐タンパ性をもつ暗号プロセッサを実現することができる。
2009122461.tif 000002
【特許請求の範囲】
【請求項１】
u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、指数剰余演算y=ad(mod n)を実行する暗号化方法であって、
a’=a2(mod n)を計算するステップと、
f=(du-1, du-2, ..., d1)2に対して、y=(a’)f(mod n)を計算するステップと、
d0=1であるときにy=y×a (mod n)を計算するステップと、
y=ad(mod n)を出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項２】
u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、バイナリ法を用いて指数剰余演算y=ad (mod n)を実行する暗号化方法であって、
v=1の初期化処理を実行するステップと、
a’=a2(mod n)を計算するステップと、
i=u-1, u-2, ..., 2, 1の順に、v=v×v (mod n)を計算するサブステップと、di=1であるときにv=v×a’ (mod n)を計算するサブステップとを、繰返し実行するステップと、
d0=1であるときにv=v×a (mod n)を計算するステップと、
vをy=ad (mod n)をとして出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項３】
u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、バイナリ法を用いて指数剰余演算y=ad (mod n)を実行する暗号化方法であって、
a’=a2(mod n)を計算するステップと、
v=a’の初期化処理を実行するステップと、
i=u-2, u-2, ..., 2, 1について、v=v×v (mod n)を計算するサブステップと、di=1であるときにv=v×a’ (mod n)を計算するサブステップとを、繰返し実行するステップと、
g=d0に対して、g=1であるときにv=v×a (mod n)を計算するステップと、
vをy=ad (mod n)として出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項４】
u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、window法を用いて指数剰余演算y=ad (mod n)を実行する暗号化方法であって、
kをwindowのビット幅として、x=0,1,...,2k-1に対して、w[x] = (a2)x (mod n)を満たすテーブルw[x]を作成するステップと、
v=1の初期化処理を行うステップと、
e x uをx以上の整数値の集合の最小値を表す演算として、i=e (u-1) /ku−1,  ..., 2, 1,0の順に、v=v×v (mod n)の２乗算処理をk回繰り返すサブステップと、d,i,kからbi=(dik+k, ..., dik+1)2を計算するサブステップと、v=v×w[bi] (mod n)を計算するサブステップを、繰返し実行するステップと、
d0=1であるときにv=v×a (mod n)を計算するステップと、
vをy=ad(mod n)をとして出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項５】
u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、window法を用いて指数剰余演算y=ad (mod n)を実行する暗号化方法であって、
kをwindowのビット幅として、x=0,1,...,2k-1に対して、w[x] = (a2)x (mod n)を満たすテーブルw[x]を作成するステップと、
ex uをx以上の整数値の集合の最小値を表す演算として、 i=e(u-1) /ku−1 に対し、v=w[bi]の初期化処理を行うステップと、
i=e(u-1) /ku−2, ..., 2, 1,0の順に、v=v×v (mod n)の２乗算処理をk回繰り返すサブステップと、d,i,kからbi=(dik+k, ..., dik+1)2を計算するサブステップと、v=v×w[bi] (mod n)を計算するサブステップとを、繰返し実行するステップと、
d0=1であるときにv=v×a (mod n)を計算するステップと、
vをy=ad (mod n)をとして出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項６】
u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、スカラー倍算Y=dAを実行する暗号化方法であって、
A’=2Aを計算するステップと、
f=(du-1, du-2, ..., d1)2に対して、A’のf倍点Y=fA’を計算するステップと、
d0=1であるときにY=Y+Aを計算するステップと、
Y=dAを出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項７】
u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、バイナリ法を用いてスカラー倍算Y=dAを実行する暗号化方法であって、
Oを全ての点Aに対してA+O=O+A=Aを満たす無限遠点として、V=Oの初期化処理を実行するステップと、
A’=2Aを計算するステップと、
i=u-1, u-2, ..., 2, 1の順に、V=2Vを計算するサブステップと、di=1のときにV=V+A’を計算するサブステップと、を繰返し実行するステップと、
d0=1のときにV=V+Aを計算するステップと、
VをY=dAとして出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項８】
u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、バイナリ法を用いてスカラー倍算Y=dAを実行する暗号化方法であって、
A’=2Aを計算するステップと、
V=A’の初期化処理を実行するステップと、
i=u-2, u-2, ..., 2, 1について、V=2Vを計算するサブステップと、di=1のときにV=V+A’を計算するサブステップを、繰返し実行するステップと、
g=d0に対してg=1のときにV=V+Aを計算するステップと、
VをY=dAとして出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項９】
u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、window法を用いてスカラー倍算Y=dAを実行する暗号化方法であって、
kをwindowのビット幅として、x=0,1,...,2k-1に対して、W[x] = (2x)Aを満たすテーブルW[x]を作成するステップと、
Oを全ての点Aに対してA+O=O+A=Aを満たす無限遠点として、V=Oの初期化処理を行うステップと、
e x uをx以上の整数値の集合の最小値を表す演算として、i=e (u-1) /ku−1,  ..., 2, 1,0の順に、V=2Vの点の２倍算処理をk回繰り返すサブステップと、d,i,kからbi=(dik+k, ..., dik+1)2を計算するサブステップと、を繰返し実行するステップと、
V=V+W[bi]を計算するステップと、
d0=1のときにV=V+Aを計算するステップと、
VをY=dAとして出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項１０】
u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、window法を用いてスカラー倍算Y=dAを実行する暗号化方法であって、
kをwindowのビット幅として、x=0,1,...,2k-1に対して、w[x] = (2x)A (mod n)を満たすテーブルW[x]を作成するステップと、
e x uをx以上の整数値の集合の最小値を表す演算として、i=e (u-1) /ku−1 に対し、V=W[bi]の初期化処理を行うステップと、
i=e (u-1) /ku−2, ..., 2, 1の順に、V=2Vの点の２倍算処理をk回繰り返すサブステップと、d,i,kからbi=(dik+k, ..., dik+1)2を計算するサブステップと、V=V+W[bi]を計算するサブステップと、を繰返し実行するステップと、
d0=1のときにV=V+Aを計算するステップと、
VをY=dAとして出力するステップと、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化方法。
【請求項１１】
u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、指数剰余演算y=ad(mod n)を実行する暗号化装置であって、
a’=a2(mod n)を計算する手段と、
f=(du-1, du-2, ..., d1)2に対して、y=(a’)f(mod n)を計算する手段と、
d0=1であるときにy=y×a (mod n)を計算する手段と、
y=ad(mod n)を出力する手段と、
を含むことを特徴とする電力解析攻撃への対策機能を備えた暗号化装置。
【請求項１２】
u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、指数剰余演算y=ad(mod n)を実行して暗号化を行うコンピュータに、
a’=a2(mod n)を計算する機能と、
f=(du-1, du-2, ..., d1)2に対して、y=(a’)f(mod n)を計算する機能と、
d0=1であるときにy=y×a (mod n)を計算する機能と、
y=ad(mod n)を出力する機能と、
を実行させるためのプログラム。
【請求項１３】
請求項１１に記載の暗号化装置を組み込んだ組込機器装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号の分野に属するもので、暗号プロセッサ内部の秘密鍵を電力解析攻撃と呼ばれる攻撃から防ぐための耐タンパ技術に関するものである。
【背景技術】
【０００２】
暗号方式は、共通鍵暗号方式と公開鍵暗号方式に大別される。共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵(秘密鍵)を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵(公開鍵)を一般に公開する代わりに、暗号文を復号するための鍵(秘密鍵)を受信者のみの秘密情報とすることで安全性を保つ方式である。【０００３】
暗号の分野における技術の一つに、解読技術とよばれるものがある。解読技術とは秘密鍵等の秘密情報を暗号文等の入手可能な情報から推定する技術のことであり、様々な手法が存在する。その中で最近注目されている技術に、電力解析攻撃と呼ばれる手法がある。電力解析攻撃とは、1998年にPaul Kocherによって考案された手法で、スマートカード等に搭載された暗号プロセッサに様々な入力データを与えた時の電力消費データを収集・解析することで、暗号プロセッサ内部の鍵情報を推定する手法である。電力解析攻撃を用いることで、共通鍵暗号、公開鍵暗号共に暗号プロセッサから秘密鍵を推定できることが知られている。【０００４】
電力解析攻撃には、単純電力解析(Single Power Analysis, 以下SPA), 電力差分攻撃(Differential Power Analysis, 以下DPA)の2種類が存在する。SPAは暗号プロセッサにおける単一の電力消費データの特徴から秘密鍵の推定を行う方式、DPAは多数の電力消費データの差分を解析することで秘密鍵の推定を行う方式である。【０００５】
DESやAESなどの共通鍵暗号方式に対してSPA、DPAを用いた推定法については、下記非特許文献１(以下Kocher99)にて詳細に述べられている。
RSA暗号、楕円曲線暗号などの公開鍵暗号に対してSPA、DPAを用いた推定法については、非特許文献２(Messerges99)や、非特許文献３(Coron99)などの文献にて述べられている。【０００６】
RSA暗号の演算方法（公知技術）
RSA暗号の復号処理においては、指数剰余演算処理と呼ばれる処理が行われる。指数剰余演算は、秘密鍵d, 暗号文a, 法nに対して、v=ad (mod n)により平文vを計算する処理である。一般的に、RSA暗号における秘密鍵dのビット長は1024-bit以上が用いられているため、このd乗演算を単純な方法で実行すると、およそ21024回の乗算が必要となり、現実的な時間内に計算することが不可能となる。【０００７】
この処理を効率的に行うためのアルゴリズムとして、バイナリ法、もしくはwindow 法という方法が知られている。バイナリ法は、下記非特許文献４の615ページ、アルゴリズム14.79に掲載されている。window法は、同文献の615ページ, アルゴリズム14.82に掲載されている。これらの方法を用いることで、d乗に必要な演算回数を、21024回から1024の定数倍(この定数は1.5以下の値)にすることができ、効率的な演算を実現することができる。【０００８】
秘密鍵dをu-bit値とし、その2進表現をd=(du-1,du-2,...,d0)2と表記する。ただし、diはdの個々のビット値を表す。バイナリ法を用いた指数剰余演算のアルゴリズムを図１に、window法を用いてv=ad mod nを計算する指数剰余演算のアルゴリズムを図２に示す。【０００９】
図１に示すバイナリ法が行っている演算の概要を図３に、図２に示すウィンドウ法が行っている演算の概要を図４に示す。
図１の処理を説明する。dのビット値diを、i=u-1からi=0の順番にチェックする。このチェックの結果、di=1ならば、２乗算と乗算の両方を実行する。di=0ならば、２乗算のみを実行する。この処理をi=u-1からi=0まで繰り返すことで、v=ad(mod n)を計算する。つまり、鍵ビットdiの値と、２乗算、乗算の実行パターンが、直接的に連動していることがバイナリ法の特徴である。【００１０】
図２の処理を説明する。最初にw[x]=ax(mod n)の作成処理を0<x<2kについて行う。テーブル作成処理の後、u-bit値のd=(du-1,du-2,...d0)2をk-bitごとに分割し、eu/ku個の数列bi(i=0,1,..)を生成する。即ちbi=(dik+k-1,...,dik)2である。ただし、exuはx以上の整数の最小値を表し、例えばe7/3u=e2.333...u=3であり、 e10/5u=e2u=2, である。eu/kuは、u-bitのビット列をk-bitごとに分割したときの分割数を表す。このbiを用いたテーブル索引処理(v=v´w[bi])と、v=v2^k(mod n)で示される2k乗算(2乗算をk回繰り返す)を繰り返すことでv=ad(mod n)を計算する。バイナリ法と異なり、ウィンドウ法では鍵ビットdiの値に関係なく、２乗算をk回、乗算を１回というパターンを繰り返す。【００１１】
以下の説明では、window法においてテーブル索引に用いられる数列biを「window列」と呼ぶ。
＜RSA暗号処理に対する電力解析攻撃（公知技術）＞
図１、２で説明したRSA暗号処理に対する電力解析攻撃について説明する。【００１２】
RSAの処理方法が、バイナリ法であるかwindow法であるかによって、攻撃の手段と結果が異なり、それぞれ以下のとおりである。
・バイナリ法
攻撃者が消費電力から判断する情報：２乗算と乗算を識別。
攻撃者が得る鍵情報：秘密鍵の全ビット値(u-bit全て)
・window法
攻撃者が消費電力から判断する情報：各window列biが、偶数か奇数であるか。
攻撃者が得る鍵情報：秘密鍵のu-bitのうちu/k-bitを解読、k-bitおきに1-bit解読。【００１３】
すでに説明したとおり、バイナリ法は秘密鍵のビット値が1ならば乗算と２乗算が、0ならば２乗算のみが実行される。よって、２乗算と乗算を消費電力によって識別することができれば、dの全ビットを解読することができる。【００１４】
ただし、window法においては、２乗算と乗算の実行パターンが秘密鍵の値に関係なく、常に一定となる。よって、上記のような２乗算と乗算を識別する方法では攻撃できない。その代わり、消費電力波形を用いることで、各window列biが偶数か奇数であるかを判別することができる。この判別を行うことで、k-bit値であるbiの最下位ビットを解読できる。図４に示すように、window列biは秘密鍵dをk-bitごとに区切った値なので、個々のbiの最下位ビットを解読することでdのビット値をk-bitごとに1-bit解読することができる。【００１５】
＜バイナリ法（図１）に対する電力解析攻撃＞
消費電力波形を用いて、２乗算と乗算を識別する方法を説明する。この識別方法は、以下に示す攻撃法１、攻撃法２の２種類が知られている。いずれの識別方法も、乗算処理の消費電力波形は、乗算のデータ値に依存して変化する、という性質を利用している。【００１６】
・攻撃法１
暗号文aの値として、a= -1 (mod n)を入力した上で、秘密鍵dによる復号処理を実行しその消費電力を測定する。a= -1(mod n)という暗号文を入力することで、復号処理で実行される乗算のデータ値のパターンが以下の３種類のみに限定される。
- 乗算：(1)×(-1)の１種類。
- ２乗算：(1)×(1), (-1)×(-1)の２種類。【００１７】
d=(10100)2に対して、a = -1 (mod n)を入力した場合の消費電力波形の例を図５に示す。乗算、２乗算合計して全体で７回の演算を実行しているのに対し、消費電力の波形は３パターンのみに限定されている。攻撃者はこれらの波形パターンを観察した上で、２乗算と乗算の実行順序を識別する。【００１８】
攻撃者は、３種類の波形パターンを識別したのち、それぞれの波形パターンが、乗算、２乗算のいずれに対応しているか判断する必要があるが、３種類の波形パターンと乗算、２乗算の対応関係の組み合わせは高々６通りしか存在しないため、鍵の値を６通りに限定することができる。dの値が1024-bitの場合、総当り法によって鍵を求める場合21024の手間がかかるのに対し、この方法を用いることで６通りに限定することができる。【００１９】
図１のアルゴリズムの性質をさらに考慮すると、６通りから１通りに限定することができる。まず、図１のアルゴリズムの性質上、最初に実行される波形は必ず(1)×(1)であるので、３とおりの波形パターンのうち、(1)×(1)の乗算波形がどの波形かを判別することができる。(1)×(1) の乗算を行った後の波形パターンは、(1)×(1)もしくは(1)×(-1)の２通りのみに限定されるので、(1)×(1)の波形パターンに続く波形パターンが(1)×(-1)の波形であると判断される。図５においては、(1)×(1)の乗算波形の次の波形パターンが(1)×(-1)の波形である。(-1)×(-1)に示される２乗算の波形パターンは、図１のアルゴリズムの性質から(1)×(-1)の乗算の直後であるので、同様に(-1)×(-1)の波形も確定できる。【００２０】
-1以外の値をaに入力した場合、図１の乗算、２乗算のi=u-1, ..., 1, 0のループ内で実行される乗算のデータ値は上記の３種類に限定されず、乗算、２乗算を実行するたびに異なるデータ値による乗算処理が行われる。よって、全ての乗算波形が異なる形をしており、攻撃者にはランダムな波形パターンの羅列に見えるので、２乗算と乗算を識別することができない。しかし、a=-1を入力した場合に限り乗算のデータ値は３パターンに限定されるので、波形のパターンが３種類に限定されるため２乗算と乗算を識別することができる。【００２１】
・攻撃法２
攻撃法１は、a= -1 (mod n)を入力し、単一の電力波形を観察することで、２乗算と乗算の判別を行っていた。これに対し、下記で述べる攻撃法２は、a = s (mod n)を入力した時の消費電力波形と、a= -s (mod n)を入力した時の消費電力波形をそれぞれ測定し、これらの差分波形を観察することで２乗算と乗算の識別を行う。ただし、sは任意のデータ値であり、攻撃者が自由に選択することができる。【００２２】
攻撃法１と同様に、攻撃法２の識別法も、乗算処理の消費電力波形は乗算のデータ値に依存して変化する、という性質を利用している。
a = s (mod n)を入力した時の消費電力波形と、a= -s (mod n)を入力した時の消費電力波形の差分波形は、実行している演算が乗算か２乗算かにより、３パターンに限定される。以下ではまずその原理について説明を行う。【００２３】
a=s (mod n)を入力した時の消費電力波形と、a=-s (mod n)を入力した時の消費電力波形を、同じタイミングで比較した場合、それぞれの消費電力波形で実行している演算内容を以下に記述する。【００２４】
・乗算：乗算のデータ値がとりうるパターンは、以下の１パターンである。
[パターン１]
a= sを入力した場合: vs = v×s (mod n)の乗算を実行する。
vは計算途中の中間データであり、図１の変数vである。
a= -sを入力した場合: -vs = v×-s (mod n)の乗算を実行する。
vは計算途中の中間データであり、図１の変数vである。
vの値は、a = sを入力した場合のvと同じ値である。【００２５】
「パターン１」の場合、C=A×B(mod n)の乗算処理におけるデータ値の違いを、a=sを入力した場合とa=-sを入力した場合について比較すると、Aの値は同一であるが、CとBの値が異なる。よって、乗算処理に関して、a= sを入力した場合とa= -sを入力した場合の差分波形は、Aの値に関する処理部分の波形差分は平坦であるが、B,Cに関する処理部分はデータ値が異なるため振幅が大きな波形となる。【００２６】
・２乗算：２乗算のデータ値がとりうるパターンは、以下の２パターンである。
[パターン2]
a= sを入力した場合: v2 = v×v (mod n)の２乗算を実行する。
vは計算途中の中間データであり、図１の変数vである。
a= -sを入力した場合: v2 = -v×-v (mod n)の２乗算を実行する。
vは計算途中の中間データであり、図１の変数vである。
vの値は、a = sを入力した場合のvと同じ値である。【００２７】
「パターン2」の場合、C=A×B(mod n)の乗算処理におけるデータ値の違いを、a=sを入力した場合とa=-sを入力した場合について比較すると、Cの値は同一であるが、AとBの値が異なる。よって、乗算処理に関して、a= sを入力した場合とa= -sを入力した場合の差分波形は、Cの値に関する処理部分の波形差分は平坦であるが、A,Bに関する処理部分はデータ値が異なるため振幅が大きな波形となる。【００２８】
[パターン3]
a= sを入力した場合: v2 = v×v (mod n)の乗算を実行する。
vは計算途中の中間データであり、図１の変数vである。
a= -sを入力した場合: v2 = v×v (mod n)の乗算を実行する。
vは計算途中の中間データであり、図１の変数vである。
vの値は、a = sを入力した場合のvと同じ値である。【００２９】
「パターン3」の場合、C=A×B(mod n)の乗算処理におけるデータ値の違いを、a=sを入力した場合とa=-sを入力した場合について比較すると、A,B,C全て同一の値である。よって、乗算処理に関して、a= sを入力した場合とa= -sを入力した場合の差分波形は、A,B,C全ての値が同一であるため完全に平坦な波形となる。【００３０】
以上により、a=sとa=-sを入力したときの差分波形は、実行している演算が乗算か２乗算かに応じて、３パターンのみの波形に限定できることがわかる。この性質を利用した差分波形の例を図６に示す。【００３１】
図６に示すように、a=sとa=-sを入力したときの差分波形をとることで、３種類のみの波形パターンを得る。「パターン３」による２乗算は完全に平坦な波形であり、容易に識別することができ、図６の最初の波形が該当する。図１のアルゴリズムの性質上、最初に「パターン３」の２乗算が実行される。残りは、「パターン１」による乗算と、「パターン２」による２乗算の違いを識別する必要があるが、「パターン１」「パターン２」と「乗算」「２乗算」の対応関係は総当りでも２通りしかないため、対応関係を知らなくとも鍵の値を２通りまで絞ることができる。さらに、図１のアルゴリズムの性質を性質により、一つもしくは複数の「パターン３」の波形が続いた後は、必ず「パターン１」となるため、どの差分波形が「パターン１」であるかを一意に識別することができる。図６の場合、左から２番目の波形がこれに該当する。図６におけるこの「パターン１」の波形は、左部分が平坦、かつそれ以外の部分の振幅が大きいことが特徴である。図１のアルゴリズムの性質上、最後の「パターン２」は、「パターン１」の直後である。図６の場合、左から２番目の波形がこれに該当する。図６におけるこの「パターン１」の波形は、右部分が平坦、かつそれ以外の部分の振幅が大きいことが特徴である。【００３２】
以上により、攻撃者は「パターン１」「パターン２」「パターン３」の波形を識別することで２乗算と乗算を識別することができ、全ての秘密鍵の値を得ることができる。
＜window法（図２）に対する電力解析攻撃＞
消費電力波形を用いて、window列biが偶数であるか、奇数であるかを識別する方法を説明する。この識別方法は、以下に示す攻撃法３、攻撃法４の２種類が知られている。いずれの識別方法も、乗算処理の消費電力波形は、乗算のデータ値に依存して変化する、という性質を利用している。【００３３】
・攻撃法３
攻撃法１と同様に、暗号文aの値として、a= -1 (mod n)を入力した上で、秘密鍵dによる復号処理を実行しその消費電力を測定する。a= -1(mod n)という暗号文を入力することで、攻撃法１と同様に、復号処理で実行される乗算のデータ値のパターンが以下の３種類のみに限定される。
- 乗算：(1)×(-1)もしくは(1)×(1)の２種類。
- ２乗算をk回：(-1)×(-1)を1回実行した後, (1)×(1)をk-1回実行もしくは、(1)×(1)をk回実行の２種類。【００３４】
上記の演算のうち、攻撃者が識別する必要があるのは、２種類の乗算である。（２種類の２乗算は識別しなくとも良い。）乗算を識別する理由は、(1)×(-1)の乗算は、biが奇数であることを意味し、(1)×(1)の乗算は、biが偶数であることを意味するからである。biの偶数、奇数と乗算の種類が連動している理由であるが、図２に示す通り、w[bi] = abi (mod n)で表されるテーブルw[bi]を用いた乗算v=v×w[bi]が行われるので、a=-1の場合、biが奇数ならばテーブルw[bi]は-1の奇数乗のため-1となり、biが偶数ならばテーブルw[bi]は-1の偶数乗のため1となるからである。【００３５】
以上により、２種類の乗算を電力波形により識別できれば、biが偶数であるか奇数であるかを判別できることがわかる。後は、乗算がどのタイミングで実行されるかを攻撃者が知っていれば２種類の乗算を識別できるが、これについては簡単である。なぜなら、図２のアルゴリズムの性質上、２乗算をk回実施した後に乗算を必ず１回実行する、という規則的な処理を実行するため、２乗算をk回実施した後の波形が必ず乗算が実行されることを攻撃者は知っているからである。【００３６】
よって、乗算が実行されるタイミングの波形のみに関して、２種類の乗算の識別を行うことで、攻撃者はwindow列biが偶数であるか、奇数であるかを識別することができる。
k=3, d=(101100)2に対して、a = -1 (mod n)を入力した場合の消費電力波形の例を図７に示す。２乗算３回、乗算１回という演算パターンを１回繰り返し、全体で８回の演算を実行している。攻撃者は、４回に１回実行される乗算の波形を観察することで、biが奇数であるか偶数であるかを判別する。この場合、dが6ビットなので、b1,b0の２つのwindowを用いた計算が行われる。ただし、b1はdの上位3-bit, b0はdの下位3-bitを表す。最初に、(1) ×(1)による２乗算が３回繰り返された後、w[b1]による乗算が行われる。この乗算波形は左から４番目の波形であり、(1)×(1)の乗算波形とは明らかに異なる。よって、b1は奇数であると識別できる。（もし、左から４番目の波形が(1)×(1)の乗算波形と同一ならば、b1は偶数であると識別できる。）【００３７】
その後、(-1) ×(1)の２乗算を１回、(1) ×(1)の２乗算を２回実行した後、w[b0]による乗算が行われる。この乗算波形は左から８番目（もしくはもっとも右の波形）であり、(1)×(1)の乗算波形と同じ形をしている。よって、b0は偶数であると識別できる。【００３８】
以上により、攻撃者はdのビット値がd=(**1**0)2であることを解読でき、dの6-bit中2-bitの解読を、3-bitごとに行うことができる。
・攻撃法４
攻撃法２と同様に、a = s (mod n)を入力した時の消費電力波形と、a= -s (mod n)を入力した時の消費電力波形をそれぞれ測定し、これらの差分波形を乗算に関して観察することで、biが偶数か奇数かを判別する。ただし、sは任意のデータ値であり、攻撃者が自由に選択することができる。【００３９】
攻撃法３の説明と同様に、図２のアルゴリズムでは、w[bi] = abi (mod n)で表されるテーブルw[bi]を用いた乗算v=v×w[bi]が行われる。a=sとa=-sを入力した場合の乗算のデータw[bi]の差分が、biが偶数であるか奇数であるかによって異なるため、乗算波形の差分を用いてbiが偶数か奇数かを識別することができる。【００４０】
biが偶数の場合、a=s, a=-sともに同一のデータw[bi] = sbi(mod n)となる。よって、v=v×w[bi]の乗算波形に関して、a=s, a=-sの差分をとると平坦な波形となる。これに対し、biが奇数の場合、a=sならばw[bi] = sbi (mod n)であるが、a=-sならばw[bi] = -sbi (mod n)である。よって、v=v×w[bi]の乗算波形に関して、a=s, a=-sの差分をとると振幅が大きな波形となる。【００４１】
k=3, d=(101100)2に対して、a=s, a = -sを入力した場合の消費電力波形の例を図８に示す。２乗算３回、乗算１回という演算パターンを１回繰り返し、全体で８回の演算を実行している。攻撃者は、４回に１回実行される乗算の波形を観察することで、biが奇数であるか偶数であるかを判別する。この場合、dが6ビットなので、b1,b0の２つのwindowを用いた計算が行われる。ただし、b1はdの上位3-bit, b0はdの下位3-bitを表す。最初に、(1)×(1)による２乗算が３回繰り返された後、w[b1]による乗算が行われる。この乗算波形は左から４番目の波形であり、このときのa=sとa = -sの差分波形は、完全に平坦な波形ではない。よって、b1は奇数であると識別できる。（もし、左から４番目の差分波形が完全に平坦な波形と同一ならば、b1は偶数であると識別できる。）【００４２】
その後、２乗算を３回実行した後、w[b0]による乗算が行われる。この乗算波形は左から８番目（もしくはもっとも右の波形）であり、その差分波形は完全に平坦な形をしている。よって、b0は偶数であると識別できる。【００４３】
以上により、攻撃者はdのビット値がd=(**1**0)2であることを解読でき、dの6-bit中2-bitの解読を、3-bitごとに行うことができる。
以上の考察より、本発明では以下の課題を解決する。【００４４】
課題１：バイナリ法を用いて、攻撃法１，２に対して安全なRSA暗号処理を実現する。
課題２：window法を用いて、攻撃法３，４に対して安全なRSA暗号処理を実現する。【００４５】
課題１，２を解決するためには、攻撃法１，２，３，４に対して安全な処理を実現する必要がある。いずれの攻撃法も、乗算処理における消費電力は乗算のデータ値に依存して決定する、という性質を利用している。つまり、この消費電力に関する性質が、課題を発生させる原因となっている。これらをまとめると以下のようになる。【００４６】
・攻撃法１
a=-1を入力した場合、以下の３種類の演算のみ発生。電力波形によりこれら３種類を識別することで、dの全てのビット値を解読。
- 乗算：(1)×(-1)の１種類。
- ２乗算：(1)×(1), (-1)×(-1)の２種類。【００４７】
・攻撃法２
a=sを入力した場合とa=-sを入力した場合の波形差分が、以下の３種類の演算のみ発生。電力波形によりこれら３種類を識別することで、dの全てのビット値を解読。
- 乗算：(v) ×(s)の波形と(v)×(-s)の波形の差分（１種類）
- ２乗算：(-v)×(-v)の波形と(v)×(v)の差分、
もしくは(v)×(v)の波形と(v)×(v)の差分(2種類)【００４８】
・攻撃法３
a=-1を入力した場合、以下の2種類の乗算のみ発生。電力波形によりこれら2種類を識別することで、dの全体の1/kのビット値を解読。
- 乗算：(1)×(-1)、(1)×(1)【００４９】
・攻撃法４
a=sを入力した場合の波形と、a=-sを入力した場合の、乗算に関する波形差分が、以下の２種類の乗算のみ発生。電力波形によりこれら2種類を識別することで、dの全体の1/kのビット値を解読。
- 乗算：(v) ×(s)の波形と(v)×(-s)の波形の差分、もしくは
(v) ×(s)の波形と(v)×(s)の波形の差分（２種類）【００５０】
下記非特許文献１〜４は、上述の説明において引用した文献である。
【非特許文献１】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(以下Kocher99)
【非特許文献２】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(以下Messerges99)
【非特許文献３】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(以下Coron99)
【非特許文献４】Alfred J.Menezesほか著”HANDBOOK OF APPLIED CRYPTOGRAPHY”(CRC press),  (http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf)  また、本発明の課題に関連して、下記特許文献１〜３に記載の公知例がある。
【特許文献１】特表２００４−５１９１３２号公報
【特許文献２】特開２００２−２６１７５３号公報
【特許文献３】特開２００４−２２６６７４号公報
【発明の開示】
【００５１】
以上に共通しているのは、乗算もしくは２乗算における、プラスとマイナスのデータ値の違いを、攻撃者は電力波形を用いて識別していることである。よって、このプラスとマイナスのデータ値の識別を防止することができれば、攻撃法１，２，３，４の全てを防御できる。
【００５２】
本発明は、RSA暗号、楕円曲線暗号などの公開鍵暗号の処理を行うプロセッサに対し、SPA、DPAによる秘密鍵の推定が行われるのを防ぐための対策技術であり、本発明の技術を適用することで、SPA、DPAを用いた秘密鍵の推定を困難にし、高い耐タンパ性をもつ暗号プロセッサを実現することができる。
【００５３】
本発明の第１の態様は、u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、指数剰余演算y=ad (mod n)を実行する暗号化方法を前提として、以下の構成を有する。
まず、a’=a2(mod n)を計算するステップが実行される。
【００５４】
次に、f=(du-1, du-2, ..., d1)2に対して、y=(a’)f(mod n)を計算するステップが実行される。
続いて、d0=1であるときにy=y×a (mod n)を計算するステップが実行される。
【００５５】
そして、y=ad(mod n)を出力するステップが実行される。
本発明の第２の態様は、u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、バイナリ法を用いて指数剰余演算y=ad (mod n)を実行する暗号化方法を前提として、以下の構成を有する。
【００５６】
まず、v=1の初期化処理を実行するステップが実行される。
次に、a’=a2(mod n)を計算するステップが実行される。
続いて、i=u-1, u-2, ..., 2, 1の順に、v=v×v (mod n)を計算するサブステップと、di=1であるときにv=v×a’ (mod n)を計算するサブステップとを、繰返し実行するステップが実行される。
【００５７】
更に、d0=1であるときにv=v×a (mod n)を計算するステップが実行される。
そして、vをy=ad (mod n)をとして出力するステップが実行される。
本発明の第３の態様は、u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、バイナリ法を用いて指数剰余演算y=ad (mod n)を実行する暗号化方法を前提として、以下の構成を有する。
【００５８】
まず、a’=a2(mod n)を計算するステップが実行される。
次に、v=a’の初期化処理を実行するステップが実行される。
続いて、i=u-2, u-2, ..., 2, 1について、v=v×v (mod n)を計算するサブステップと、di=1であるときにv=v×a’ (mod n)を計算するサブステップとを、繰返し実行するステップが実行される。
【００５９】
更に、g=d0に対して、g=1であるときにv=v×a (mod n)を計算するステップが実行される。
そして、vをy=ad (mod n)として出力するステップが実行される。
【００６０】
本発明の第４の態様は、u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、window法を用いて指数剰余演算y=ad (mod n)を実行する暗号化方法を前提として、以下の構成を有する。
【００６１】
まず、kをwindowのビット幅として、x=0,1,...,2k-1に対して、w[x] = (a2)x (mod n)を満たすテーブルw[x]を作成するステップが実行される。
次に、v=1の初期化処理を行うステップが実行される。
【００６２】
続いて、e x uをx以上の整数値の集合の最小値を表す演算として、i=e (u-1) /ku −1,  ..., 2, 1,0の順に、v=v×v (mod n)の２乗算処理をk回繰り返すサブステップと、d,i,kからbi=(dik+k, ..., dik+1)2を計算するサブステップと、v=v×w[bi] (mod n)を計算するサブステップを、繰返し実行するステップが実行される。
【００６３】
更に、d0=1であるときにv=v×a (mod n)を計算するステップが実行される。
そして、vをy=ad(mod n)をとして出力するステップが実行される。
本発明の第５の態様は、u-bit指数d=(du-1, ..., d0)2, 入力データa, 法nから、window法を用いて指数剰余演算y=ad (mod n)を実行する暗号化方法を前提として、以下の構成を有する。
【００６４】
まず、kをwindowのビット幅として、x=0,1,...,2k-1に対して、w[x] = (a2)x (mod n)を満たすテーブルw[x]を作成するステップが実行される。
次に、e x uをx以上の整数値の集合の最小値を表す演算として、 i=e (u-1) /ku−1 に対し、v=w[bi]の初期化処理を行うステップが実行される。
【００６５】
続いて、i=e (u-1) /ku −2, ..., 2, 1,0の順に、v=v×v (mod n)の２乗算処理をk回繰り返すサブステップと、d,i,kからbi=(dik+k, ..., dik+1)2を計算するサブステップと、v=v×w[bi] (mod n)を計算するサブステップとを、繰返し実行するステップが実行される。
【００６６】
更に、d0=1であるときにv=v×a (mod n)を計算するステップが実行される。
そして、vをy=ad (mod n)をとして出力するステップが実行される。
本発明の第６の態様は、u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、スカラー倍算Y=dAを実行する暗号化方法を前提として、以下の構成を有する。
【００６７】
まず、A’=2Aを計算するステップが実行される。
次に、f=(du-1, du-2, ..., d1)2に対して、A’のf倍点Y=fA’を計算するステップが実行される。
【００６８】
更に、d0=1であるときにY=Y+Aを計算するステップが実行される。
そして、Y=dAを出力するステップが実行される。
本発明の第７の態様は、u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、バイナリ法を用いてスカラー倍算Y=dAを実行する暗号化方法を前提として、以下の構成を有する。
【００６９】
まず、Oを全ての点Aに対してA+O=O+A=Aを満たす無限遠点として、V=Oの初期化処理を実行するステップが実行される。
次に、A’=2Aを計算するステップが実行される。
【００７０】
続いて、i=u-1, u-2, ..., 2, 1の順に、V=2Vを計算するサブステップと、di=1のときにV=V+A’を計算するサブステップと、を繰返し実行するステップが実行される。
更に、d0=1のときにV=V+Aを計算するステップが実行される。
【００７１】
そして、VをY=dAとして出力するステップが実行される。
本発明の第８の態様は、u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、バイナリ法を用いてスカラー倍算Y=dAを実行する暗号化方法を前提として、以下の構成を有する。
【００７２】
まず、A’=2Aを計算するステップが実行される。
次に、V=A’の初期化処理を実行するステップが実行される。
続いて、i=u-2, u-2, ..., 2, 1について、V=2Vを計算するサブステップと、di=1のときにV=V+A’を計算するサブステップを、繰返し実行するステップが実行される。
【００７３】
更に、g=d0に対してg=1のときにV=V+Aを計算するステップが実行される。
そして、VをY=dAとして出力するステップが実行される。
本発明の第９の態様は、u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、window法を用いてスカラー倍算Y=dAを実行する暗号化方法を前提として、以下の構成を有する。
【００７４】
まず、kをwindowのビット幅として、x=0,1,...,2k-1に対して、W[x] = (2x)Aを満たすテーブルW[x]を作成するステップが実行される。
次に、Oを全ての点Aに対してA+O=O+A=Aを満たす無限遠点として、V=Oの初期化処理を行うステップが実行される。
【００７５】
続いて、e x uをx以上の整数値の集合の最小値を表す演算として、i=e (u-1) /ku −1,  ..., 2, 1,0の順に、V=2Vの点の２倍算処理をk回繰り返すサブステップと、d,i,kからbi=(dik+k, ..., dik+1)2を計算するサブステップと、を繰返し実行するステップが実行される。
【００７６】
更に、V=V+W[bi]を計算するステップが実行される。
加えて、d0=1のときにV=V+Aを計算するステップが実行される。
そして、VをY=dAとして出力するステップが実行される。
【００７７】
本発明の第１０の態様は、u-bit指数d=(du-1, ..., d0)2, 楕円曲線上の点A,から、window法を用いてスカラー倍算Y=dAを実行する暗号化方法を前提として、以下の構成を有する。
【００７８】
まず、kをwindowのビット幅として、x=0,1,...,2k-1に対して、w[x] = (2x)A (mod n)を満たすテーブルW[x]を作成するステップが実行される。
次に、e x uをx以上の整数値の集合の最小値を表す演算として、i=e (u-1) /ku−1 に対し、V=W[bi]の初期化処理を行うステップが実行される。
【００７９】
続いて、i=e (u-1) /ku −2, ..., 2, 1,0の順に、V=2Vの点の２倍算処理をk回繰り返すサブステップと、d,i,kからbi=(dik+k, ..., dik+1)2を計算するサブステップと、V=V+W[bi]を計算するサブステップと、を繰返し実行するステップが実行される。
【００８０】
更に、d0=1のときにV=V+Aを計算するステップが実行される。
そして、VをY=dAとして出力するステップが実行される。
本発明の他の態様は、上記態様を実現する暗号化装置、プログラム、又は暗号化装置を組み込んだ組込機器装置として実現することができる。
【図面の簡単な説明】
【００８１】
【図１】一般的なバイナリ法を用いた指数剰余演算（従来例その１）である。
【図２】一般的なwindow法を用いた指数剰余演算（従来例その２）である。
【図３】図１のバイナリ法の処理の概要を示した図である。
【図４】図１の. window法の処理の概要をk=4のときに示した図である。
【図５】a = -1 (mod n), d=(10100)2の場合の消費電力波形の例（公知例である攻撃法１の図）である。
【図６】a = s (mod n)の消費電力波形とa=-s (mod n)の消費電力波形の差分を、d=(10100)2のについて示した例（公知例である攻撃法２の図）である。
【図７】a = -1 (mod n), d=(101100)2の場合の消費電力波形の例（公知例である攻撃法３の図）である。
【図８】a = s (mod n)の消費電力波形とa=-s (mod n)の消費電力波形の差分を、d=(101100)2について示した例（公知例である攻撃法４の図）である。
【図９】本発明の実施形態の基本手順を示した図である。
【図１０】a = -1 (mod n), f=(10100)2の場合の、本発明によるバイナリ法の消費電力波形の例（本発明の攻撃法１に対する耐性を表す図）である。
【図１１】a = -1 (mod n), d=(101100)2の場合の、本発明によるwindow法の消費電力波形の例（本発明の攻撃法３に対する耐性を表す図）である。
【図１２】本発明バイナリ法による、a = s (mod n)とa=-s (mod n)の消費電力波形の差分波形の例を、f=(10100)2について示した図（本発明の攻撃法２に対する耐性を表す図）である。
【図１３】本発明window法による、a = s (mod n)とa=-s (mod n)の消費電力波形の差分波形の例を、f=(101100)2の場合について示した図（本発明の攻撃法４に対する耐性を表す図）である。
【図１４】本発明の第１の実施形態の処理フロー図（図１のバイナリ法を改良した処理）である。
【図１５】本発明の第２の実施形態の処理フロー図（第１の実施形態でdu-1=1の場合に特化した処理）である。
【図１６】本発明の第３の実施形態の処理フロー図（図２のwindow法を改良した処理）である。
【図１７】本発明の第４の実施形態の処理フロー図（第３の実施形態を一般的な高速化法を用いて改良した処理）である。
【図１８】本発明の第５の実施形態の処理フロー図（第１の実施形態を点のスカラー倍算に応用した例）である。
【図１９】本発明の第６の実施形態の処理フロー図（第２の実施形態を点のスカラー倍算に応用した例）である。
【図２０】本発明の第７の実施形態の処理フロー図（第３の実施形態を点のスカラー倍算に応用した）である。
【図２１】本発明の第８の実施形態の処理フロー図（第４の実施形態を点のスカラー倍算に応用した例）である。
【図２２】本発明の第１〜第８の実施形態を実現するハードウェアの概略構成図である。
【発明を実施するための最良の形態】
【００８２】
以下、図面を参照しながら、本発明を実施するための最良の形態を詳細に説明する。
本発明の各実施形態の基本原理
「背景技術」において説明した攻撃法１，２，３，４の原理に共通しているのは、攻撃者がa=-1や、a=s, -sのペアを入力することで、乗算もしくは２乗算でプラスとマイナスのデータ値の違いを意図的に発生させ、このデータ値の違いを攻撃者が電力波形を用いて識別していることである。【００８３】
逆説的に述べれば、攻撃者がaに対してこれらのデータを入力しても、乗算もしくは２乗算でプラスとマイナスのデータ値の違いを意図的に発生させることができなければ、これらの攻撃を防御する対策法を実現することができる。【００８４】
この対策法を実現するための基本アイデアについて説明する。攻撃者がa=-1や、a=s, -sのように、マイナス値を含むデータを入力しても、乗算もしくは２乗算では常にプラスの値のみを発生させることができれば、前述の対策法を実現することができる。常にプラスの値を発生させるためには、最初に入力されたデータを2乗することで実現できる。つまり、図１もしくは図２に示すバイナリ法、もしくはwindow法を実行するに当たって、入力されたaに対してそのままad (mod n)の計算を行うのではなく、dに対してd=2×f+gを満たすf, gを用いることで、ad (mod n) = ((a2)f)×ag (mod n)により計算を行う。このとき、gはdの最下位ビット, fは上位u-1ビットである。d=(du-1, du-2, ..., d1, d0)2という表記に対して、f=(du-1, du-2, ..., d1)2, g=d0を満たす。【００８５】
この解決手段を用いることで、RSA演算は以下の図９の手順に従う。
全体の演算手順としては、(a2)f (mod n)を計算してから、その結果に対してag(mod n)を乗算する。(a2)f (mod n)の計算が(手順-2)により実行され、その結果に対するag (mod n)の乗算が(手順-3)により実行される。なお、(手順-3)の乗算は、g=0のときは実行されないが、g=0の場合ag=a0=1なので、乗算を行う必要がないことに注意されたい。【００８６】
これらの演算手順において、攻撃法１，２，３，４に対する防御を実現するのは、(手順-1)である。手順-1は、入力されたaを２乗するプロセスであり、この結果出力されるa’は常にプラスの値となる。例えば、a=-1を入力した場合a’=(-1)2 = 1となる。また、a=sを入力した場合, a’=(s)2=s2であり、a=-sを入力した場合a’=(-s)2=s2である。このように、常にプラスとなるa’を用いて、(手順-2)に示すような(a’)f (mod n)の計算を行うことで、攻撃１，２，３，４の全てを防ぐことができる。【００８７】
攻撃法１，３のように、a=-1を入力する攻撃法の場合、a’=1となる。よって、(a’)f (mod n)の計算を、バイナリ法もしくはwindow法で実行した場合、発生する乗算もしくは２乗算は常に(1)×(1)のみである（図１０、図１１）。よって、攻撃法１，３の図５，７に示されるように、(1)×(1), (-1)×(-1), (1)×(-1)の演算を消費電力波形によって識別する方法を用いることができないので、安全である。【００８８】
攻撃法２，４のように、a=s, a=-sを入力し、その消費電力波形の差分をする攻撃法の場合、a=s, a=-sのいずれの場合にも、a’=s2となる。よって、(a’)f(mod n)の計算における消費電力波形は、a=s, a=-sのいずれの場合にも同一の波形となり、その結果、差分波形は常に平坦な波形となる（図１２、図１３）。よって、攻撃法２，４の図６，８に示されるように、差分波形の特徴から秘密鍵を解読する方法を用いることができないので、安全である。【００８９】
fは秘密鍵dの上位u-1ビット値であるので、秘密鍵dに関連する大部分の計算は、この(手順-2)により実行されるが、この(手順-2)の計算においては常にプラスとなるa’を用いた計算を行うので、攻撃者は秘密鍵に関する情報を得ることができない。a’ではなく、aを用いた計算は、(手順-3)のみにおいて実行されるが、(手順-3)では、秘密鍵dの最下位ビットのみを用いた演算を実行するため、攻撃者が得ることができる情報は高々秘密鍵の最下位1-bitに関する情報のみであるため、有意な情報を得ることはできない。【００９０】
本発明の第１の実施形態
本発明の実施形態の基本原理である図９の（手順-1）〜（手順-4）を用いて、図１のバイナリ法を改良した実施例を図１４に示す。1402, 1403, 1409に記された太字部分が、図１からの変更点であり、図９の解決手段を用いた処理である。【００９１】
(手順-1)に示すa’=a2 (mod n)の計算は、1402により実行する。
(手順-2)に示す、(a’)f (mod n)のバイナリ法による演算プロセスは、1403〜1408のループ処理によって実行する。f=(du-1, ..., d1)2に対するバイナリ法演算を実現するために、1403のループ処理はi=u-1に始まり、u=1で終了することに注意されたい。
(手順-3)の計算は1409によって実行する。【００９２】
本発明の第２の実施形態
図１４は、du-1の値が0,1いずれの場合についても用いることができる汎用的な演算法であるが、du-1=1の場合に特化したバイナリ法アルゴリズムが一般的に知られている。この特化されたアルゴリズムを用いることで、わずかながら計算時間を短縮（乗算１回、２乗算１回）できる。図１４をdu-1=1の場合に特化したバイナリ法アルゴリズムを図１５に示す。【００９３】
1501, 1502, 1503, 1509に記された太字部分が図９の解決手段を用いた処理である。
(手順-1)に示すa’=a2 (mod n)の計算は、1501, 1502により実行する。
(手順-2)に示す、(a’)f (mod n)のバイナリ法による演算プロセスは、1503〜1508のループ処理によって実行する。du-1=1であることはわかっているので、このループ処理においては、du-1に関する処理はスキップされることに注意されたい。f=(du-2, ..., d1)2に対するバイナリ法演算を実現するために、1503のループ処理はi=u-2に始まり、u=1で終了する。
(手順-3)の計算は,1509によって実行する。【００９４】
本発明の第４の実施形態
図９の解決手段（手順-1）〜（手順-4）を用いて、図２のwindow法を改良した実施例を図１６に示す。1601, 1602, 1604, 1612に記された太字部分が、図２からの変更点である。【００９５】
(手順-1)に示すa’=a2 (mod n)の計算は、1601, 1602に示すw[x]のテーブル作成処理により実行する。図２のテーブル作成処理では、w[x] = ax (mod n)を満たすテーブルを作成していたのに対し、これに対し、図１６のテーブル作成処理では、a’=a2 (mod n)に対してw[x] = (a’)x(mod n)を満たすテーブルを作成する。これにより、テーブルデータが常にプラスとなる。【００９６】
(手順-2)に示す、(a’)f (mod n)のwindow法による演算プロセスは、1604〜1611のループ処理によって実行する。f=(du-1, ..., d1)2に対するバイナリ法演算を実現するために、1604のループ処理はi=e(u-1)/ku-1に始まり、i=0で終了することに注意されたい。図2においては、u-bit値であるdをk-bitごとに分割していたため、その分割数はeu/kuであったが、図１６の場合、(u-1)-bitのfをk-bitごとに分割しているため、その分割数は=e(u-1)/kuである。【００９７】
また、dの最下位ビットを削除したビット列がfである、つまりdとfは1-bitずれている関係上、window列biは、図２ではbi = (dik+k-1, ..., dik)2として与えられていたのが、図１６では1608のようにbi = (dik+k, ..., dik+1)2として与えられている。
(手順-3)に示す処理は、1612において実行する。【００９８】
本発明の第４の実施形態
図２のアルゴリズムを改良し、計算を若干高速化し改良した（２乗算k回、乗算１回）window法アルゴリズムが一般的に知られている。（バイナリ法と異なり、この改良は秘密鍵dやwindow列biに関する制約をうけない。）この改良を行ったwindow法アルゴリズムを図１７に示す。【００９９】
1701〜1706, 1714に記された太字部分が図９の解決手段を用いた処理である。
(手順-1)に示すa’=a2 (mod n)の計算は、第３の実施形態と同様に1701, 1702に示すw[x]のテーブル作成処理により実行する。1703〜1705においては、図１６と異なりv=1による初期化を行うのではなく、v=w[bi]による初期化を行う。【０１００】
ただし、biはi=e(u-1)/ku-1に対し、bi= (dik+k, ..., dik+1)2を満たす値である。
(手順-2)に示す、(a’)f(mod n)のバイナリ法による演算プロセスは、1706〜1713の  ループ処理によって実行する。1703〜1705に記されたvの初期化処理により、i=e(u-1)/ku-1に関する演算処理はすでに終了しているため、iのループ処理はi=e(u-1)/ku-2に始まりi=0で終了することに注意されたい。【０１０１】
1710においては、図１６と同様に、window列biはbi = (dik+k, ..., dik+1)2として与えられる。
(手順-3)に示す処理は、1714において実行する。【０１０２】
本発明のその他の実施形態
以上に示した第１〜第４の実施形態は、RSA暗号のみならず、ElGamal暗号、Diffie-Hellman鍵交換、DSA署名など、指数dと入力データcから、出力データyをy=cd (mod n)で記される指数剰余演算を用いる公開鍵暗号演算全般について適用可能である。【０１０３】
さらに、楕円曲線暗号の演算にも応用可能。ECDSA署名、ECDH鍵交換などでは、RSAの秘密鍵dと、楕円曲線上の点Aに対して、出力データである点YをY=dAにより計算する処理が行われる。この演算は、点のスカラー倍算と呼ばれる。なお、楕円曲線上の点とは、２つの数値X,Yを用いてA=(X,Y)と表されるベクトルであり、X,Yは楕円曲線と呼ばれる関数E(X,Y)と素数pに対してE(X,Y)=0 (mod p)を満たす値である。【０１０４】
楕円曲線暗号では、y=a×b(mod n)で示される乗算の代わりに、Y=A+Bで表される点の加算(Y,A,Bは楕円曲線上の点)、２乗算の代わりにY=2Aで表される点の２倍算 (Y,Aは楕円曲線上の点)を行う。よって、楕円曲線暗号に本発明を適用するためには、d=2f+gと分解し、Y=fA’+gA (A’=2A)と分解し、fAのスカラー倍算に対して、通常のバイナリ法、もしくはwindow法の演算を実行すればよい。【０１０５】
第１の実施形態（図１４）、第２の実施形態（図１５）、第３の実施形態（図１６）、及び第４の実施形態（図１７）を点のスカラー倍算に応用した実施形態を、それぞれ第５の実施形態（図１８）、第６の実施形態（図１９）、第７の実施形態（図２０）、第８の実施形態（図２１）として示す。【０１０６】
これらは、第１〜第４の各実施形態に対し、y=a×b(mod n)で示される乗算の代わりに、Y=A+Bで表される点の加算(Y,A,Bは楕円曲線上の点)、２乗算の代わりにY=2Aで表される点の２倍算 (Y,Aは楕円曲線上の点)を行っている。【０１０７】
最後に、本発明の第１〜第８の実施形態を実現するハードウェアの概略構成図を図２２に示す。
図２２において、初期２乗処理部２２０３は、乗算器２２０２を使って、図９の手順１の演算を実行する。【０１０８】
べき乗剰余演算器２２０４は、ビット分割部２２０１によってdの上位u-1ビットとして分割して得られたfを使って、図９の手順２の演算を実行する。
終了時乗算部２２０５は、ｇ＝１である場合に、メモリ２２０６に記憶されるaを使って、図９の手順３の演算を実行し、その演算結果を出力する。【０１０９】
また、図１４〜図２１として示した本発明の各実施形態の処理は、ＣＰＵ（中央演算処理装置）、主記憶メモリ、補助記憶装置、入出力装置等がバスによって相互に接続された構成を有する一般的なコンピュータにおいて、ＣＰＵが補助記憶装置等に記憶された各機能を実現する制御プログラムを主記憶メモリにロードして実行する動作として実現されてもよい。【０１１０】
以上説明したように、本発明の各実施形態では、a’=a2 (mod n)による変換を用いた演算を行うことで、図１、図２に示される従来法では防ぐことができなかった攻撃法１，２，３，４の全てを防ぐことができる。【０１１１】
本発明の効果により、消費電力波形に秘密鍵の兆候を示す特徴が現れないため、攻撃者は秘密鍵に関する情報を得ることができない。
その効果は、図５〜図６に示す従来法の消費電力波形と、図１０〜図１３に示す本発明の消費電力波形を比較すれば明確に理解することができる。
【図１】
2009122461.tif 000003
【図２】
2009122461.tif 000004
【図３】
2009122461.tif 000005
【図４】
2009122461.tif 000006
【図５】
2009122461.tif 000007
【図６】
2009122461.tif 000008
【図７】
2009122461.tif 000009
【図８】
2009122461.tif 000010
【図９】
2009122461.tif 000011
【図１０】
2009122461.tif 000012
【図１１】
2009122461.tif 000013
【図１２】
2009122461.tif 000014
【図１３】
2009122461.tif 000015
【図１４】
2009122461.tif 000016
【図１５】
2009122461.tif 000017
【図１６】
2009122461.tif 000018
【図１７】
2009122461.tif 000019
【図１８】
2009122461.tif 000020
【図１９】
2009122461.tif 000021
【図２０】
2009122461.tif 000022
【図２１】
2009122461.tif 000023
【図２２】
2009122461.tif 000024
【国際調査報告】
2009122461.tif 000025
2009122461.tif 000026
2009122461.tif 000027
2009122461.tif 000028
2009122461.tif 000029
2009122461.tif 000030