(57)【要約】  記憶手段と、前記記憶手段に格納する値を設定する初期設定手段と、前記初期設定手段が設定した値についての複数回のモンゴメリ乗算剰余演算を行うモンゴメリ乗算剰余演算手段と、前記複数回のモンゴメリ乗算剰余演算のうちの少なくとも一部のそれぞれごとに、Fault攻撃が発生したかどうかを判定する、Fault攻撃検知手段とを含む暗号処理装置。
2008114315.tif 000002
【特許請求の範囲】
【請求項１】
記憶手段と、
前記記憶手段に格納する値を設定する、初期設定手段と、
前記初期設定手段が設定した値についての複数回のモンゴメリ乗算剰余演算を行う、モンゴメリ乗算剰余演算手段と、
前記複数回のモンゴメリ乗算剰余演算のうちの少なくとも一部のそれぞれごとに、Fault攻撃が発生したかどうかを判定する、Fault攻撃検知手段と
を含むことを特徴とする暗号処理装置。  
【請求項２】
前記初期設定手段が、f-bit値 s 、 t 、 n 、および h と、w-bit値 n' とを設定して前記記憶手段に格納し（但し、 f および w は自然数）、
前記モンゴメリ乗算剰余演算が、y = REDC(s,t,n) = s×t×2-f (mod n) であり（但し、 y はf-bit値）、
前記Fault攻撃検知手段が、前記モンゴメリ乗算剰余演算手段が算出する s×t+h×n の下位f-bit値の桁のうちに0では無い数値があった場合にFault攻撃が発生したと判定し、
式中の値は
h = s×t×n’ (mod 2f)
n' = -n-1(mod 2f)
を満たす
ことを特徴とする、請求項１記載の暗号処理装置。  
【請求項３】
前記Fault攻撃検知手段がFault攻撃を検出した場合に、前記暗号処理装置の機能を停止させる、機能停止手段
をさらに含むことを特徴とする、請求項１もしくは２に記載の暗号処理装置。 
【請求項４】
記憶手段と、
g個のw-bit変数（但し、 g は自然数）を用いて表されるf-bit値 s = (sg-1, ... , s1, s0) 、 t = (tg-1, ... , t1, t0) 、 n = (ng-1, ... , n1, n0) 、および h = (hg-1, ... , h1, h0) と、w-bit値 n'0 とを設定して前記記憶手段に格納する、初期設定手段と、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たす、(g+1)個のw-bit変数で表されるf-bit値 y = (yg, ... , y1, y0) を計算する、モンゴメリ乗算剰余演算手段と（但し、 f は自然数）、
前記モンゴメリ乗算剰余演算手段が算出する (s×ti)+(hi×n) （但し、 i は 0≦i≦g-1 を満たす整数）の下位w-bit値を、変数 yNULL に格納し、前記変数 yNULL が非ゼロであった場合にFault攻撃が発生したと判定する、Fault攻撃検知手段と
を含むことを特徴とする暗号処理装置。
（但し、式中の値は
f > w
hi= s×ti×n'0 (mod 2w) （但しiは上述したもの）
n'0= -n-1 (mod 2w)
を満たす）  
【請求項５】
記憶手段と、
g個のw-bit変数を用いて表されるf-bit値 s = (sg-1, ... , s1, s0) 、 t = (tg-1, ... , t1, t0) 、および h = (hg-1, ... , h1, h0) と、w-bit値 n'0 とを設定して前記記憶手段に格納する、初期設定手段と（但し、 g および w および f は自然数）、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たす、(g+1)個のw-bit変数で表されるf-bit値 y = (yg, ... , y1, y0) を計算する、モンゴメリ乗算剰余演算手段と、
前記モンゴメリ乗算剰余演算手段が算出する (s×t0)+(h'×n0)の下位w-bit値を、変数 yNULLに格納し、前記変数 yNULLが非ゼロであった場合にFault攻撃が発生したと判定する、Fault攻撃検知手段と
を含み、ここで式中の値は
f > w
h = s×t×n'0 (mod 2f)
n'0= -n-1 (mod 2w)
を満たし、また、
前記モンゴメリ乗算剰余演算手段が、式中 h' を、変数 b に関するループ変数 j が更新されるごとに
h' = ((a0×bj)+y0)×n'0 (mod 2w)
として動的に更新する
ことを特徴とする暗号処理装置。  
【請求項６】
記憶手段と、
g個のw-bit変数を用いて表されるf-bit値 s = (sg-1, ... , s1, s0) 、 t = (tg-1, ... , t1, t0) 、 n = (ng-1, ... , n1, n0) 、および h = (hg-1, ... , h1, h0) を設定して前記記憶手段に格納する、初期設定手段と（但し、 g および w は自然数）、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たす、(g+1)個のw-bit変数で表されるf-bit値 y = (yg, ... , y1, y0) を計算する、モンゴメリ乗算剰余演算手段と（但し、 f は自然数）、
前記モンゴメリ乗算剰余演算手段が算出する (s×t0)+(hj×n) （0≦j≦g-1）の下位w-bit値を、変数 yNULLに格納し、前記変数 yNULLが非ゼロであった場合にFault攻撃が発生したと判定する、Fault攻撃検知手段と
を含み、ここで式中の値は
f > w
h = s×t×n’ (mod 2f)
n' = -n-1(mod 2f)
を満たし、また、
式中の h は、前記初期設定手段により前記モンゴメリ乗算剰余演算手段の計算が行われる前に与えられている
ことを特徴とする暗号処理装置。  
【請求項７】
前記記憶手段および前記モンゴメリ乗算剰余演算手段のそれぞれから読み込んだw-bit単位のデータを用い、w-bit×w-bitの乗算を行って前記変数 yNULL として出力する、w-bit×w-bit乗算手段
をさらに含むことを特徴とする、請求項４〜６のいずれか一項に記載の暗号処理装置。
【請求項８】
前記記憶手段から一度の読み込みにつき(k*w)-bit単位のデータを読み込み、(w/k)-bitずつデータを出力する第一バッファ手段と、
前記記憶手段から(k*w)-bit単位のデータを読み込み、且つ前記第一バッファ手段から(w/k)-bit単位のデータを読み込んで、(k*w)-bit×(w/k)-bitの乗算を行って、前記変数 yNULL の一部を出力する、(k*w)-bit×(w/k)-bit乗算手段と、
前記(k*w)-bit×(w/k)-bit乗算手段が出力した前記変数 yNULL の前記一部を蓄積して(k*w)-bit値とする、第二バッファ手段と
をさらに含み、但し k は自然数であることを特徴とする、請求項４〜６のいずれか一項に記載の暗号処理装置。  
【請求項９】
k = 2 であることを特徴とする、請求項８記載の暗号処理装置。 
【請求項１０】
請求項１〜９のいずれか一項に記載の暗号処理装置を含むことを特徴とするスマートカード。  
【請求項１１】
f-bit値 s 、 t 、 n 、および h と、w-bit値 n' とを設定するステップと（但し、 f および w は自然数）、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たすf-bit値 y を計算するステップと、
前記モンゴメリ乗算剰余演算手段が算出する s×t+h×n の下位f-bit値の桁に0では無い数値があった場合にFault攻撃が発生したと判定してFault攻撃を検知するステップと
を含み、ここで式中の値は
h = s×t×n’ (mod 2f)
n' = -n-1(mod 2f)
を満たすことを特徴とする、暗号処理方法。  
【請求項１２】
記憶手段を具えたコンピュータに暗号処理方法を実行させるプログラムであって、前記方法は、
f-bit値 s 、 t 、 n 、および h と、w-bit値 n' とを設定して前記記憶手段に格納するステップと（但し、 f および w は自然数）、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たすf-bit値 y を計算するステップと、
前記モンゴメリ乗算剰余演算手段が算出する s×t+h×n の下位f-bit値の桁に0では無い数値があった場合にFault攻撃が発生したと判定してFault攻撃を検知するステップと
を含むことを特徴とするプログラム。
（但し、式中の値は
h = s×t×n’ (mod 2f)
n' = -n-1(mod 2f)
を満たす）  
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号分野におけるFault攻撃を検知し防止する対策機能を具えた装置、ならびに、Fault攻撃を検知する方法およびそれを実施するためのプログラムに関する。
【背景技術】
【０００２】
〔暗号方式と耐タンパ技術の概要〕
暗号は、情報を盗聴や改竄から保護するための技術である。現行の暗号方式は、公開鍵暗号方式と共通鍵暗号方式に大別される。公開鍵暗号方式とは、暗号化（encryption）と復号化（復号; decryption）のそれぞれに異なる鍵を用いる方式であり、暗号化を行うための鍵（公開鍵）を一般に公開し、その一方で暗号文を復号化するための鍵（秘密鍵）を受信者のみが有する秘密情報とすることで安全性を保つ方式である。これに対して共通鍵暗号方式と呼ばれるものは、暗号化と復号化で同一の鍵（秘密鍵）を用いる方式であって、この秘密鍵を送信者と受信者以外の第三者にはわからない情報とすることで安全性を保つ方式である。【０００３】
暗号分野における技術の一つとして、耐タンパ技術（tamper proof technology）と呼ばれるものがある。耐タンパ技術とは、秘密鍵等の秘密情報が、悪意のある第三者の攻撃により漏洩するのを防ぐための技術であり、組み込み装置などの暗号機能を搭載したデバイス内部に格納されている、特に、スマートカードに耐タンパ技術を搭載することは、セキュリティ国際標準であるISO15408認定取得のための必須条件となっている。【０００４】
耐タンパ技術が防御対象とする攻撃には、様々な手法が存在する。その中でも重要な攻撃として、1997年にBoneh, DeMillo, Liptonによって発表された手法であるFault攻撃と呼ばれる攻撃手法がある。Fault攻撃とは、スマートカード等の組み込み機器に搭載された暗号処理プロセッサの回路に対して、様々なストレス（異常クロック、過電圧、高温度など）を与えることで、回路の内部データに異常値を発生させ、暗号処理プロセッサ内部の鍵情報を推定する手法である。上述したFault攻撃についてのさらなる詳細については、非特許文献１を参照されたい。【０００５】
Fault攻撃を用いることで、公開鍵暗号方式・秘密鍵暗号方式のいずれにおいても暗号処理プロセッサ内部の秘密鍵を推定できることが知られている。特に、前述の非特許文献１に記述されている、RSA暗号という公開鍵暗号へのFault攻撃は、攻撃者にとって実施が容易であるために大きな脅威であると考えられている。その他の公開鍵暗号方式に対するFault攻撃としては、楕円曲線暗号（elliptic curve cryptography; ECC）に対するFault攻撃（詳細は非特許文献２に記載）も知られている。こういった公開鍵暗号へのFault攻撃についての対策は、耐タンパ技術上の重要な課題である。
〔公開鍵暗号〕
本発明の前提となる公開鍵暗号方式についての説明を以下に記す。【０００６】
〔a. バイナリ法〕
公開鍵暗号のアルゴリズムとしては、RSAとECCが代表的なものとして知られている。RSA暗号を行うプロセッサにおいては、指数剰余演算処理と呼ばれる処理が行われる。指数剰余演算は、指数d、メッセージa、公開鍵nに対して、 v = ad (mod n) を満たすvを計算する処理である。この処理を効率的に行うためのアルゴリズムとして、以下にアルゴリズム1として示すバイナリ法という方法が知られている。
《アルゴリズム1：バイナリ法を用いた指数剰余演算》
・input
d ：指数
u ： dのビット長
a ：基数
n ：法
・output
v=ad (mod n)：指数剰余演算結果
・algorithm
a101    v=a;
a102    for(i=u-2;i>=0;i=i-1) {  /* extract top k-bit of d */
a103      v = v × v (mod n);
a104      if (di == 1) v = v × a (mod n);
a105    }
a106    return v;
アルゴリズム1では、最初のステップ a101 で v = a の初期化を行い、次にステップa102 でu-bit値 d = (du-1, du-2, ... , d0)2を、 du-1, du-2, ... ,d0 の順に探索する。ここで ()2 は二進数を表し、例えば (101)2 = 5, (1101)2 = 13 である。また、du-1=1であるものとする。【０００７】
この探索のくりかえしはステップa102〜a105 のforループによって行われる。forループ内部では、ステップa103 で v = v×v (mod n) の計算処理を行った後に、ステップ a104 でビット値 diの値に応じた処理の切り替えを行う。 di= 0 ならば何も行わず、 di= 1 ならば v = v×a (mod n) の演算処理を行う。つまり、 di = 0 ならば、二乗算を実行し、 di = 1 ならば、二乗算と乗算を実行するということである。これを du-1, du-2, ... , d0 のすべてについてくりかえし、指数剰余演算処理を行う。最後にステップ a106 で v を計算結果として出力する。【０００８】
このアルゴリズム1の処理の流れを模式的に示した図を図１として示した。
バイナリ法は、RSA暗号だけでは無く、ECCにおいて点のスカラー倍算と呼ばれる処理を行う際にも用いられる。点のスカラー倍算とは、スカラー値d、楕円曲線上の点Aに対して、V = dAを満たす点Vを計算する処理である。バイナリ法を用いて点のスカラー倍算V = dAを行うアルゴリズムをアルゴリズム2として以下に示す。
《アルゴリズム2：バイナリ法を用いたスカラー倍算》
・input
d : 指数
u : dのビット数
A : 楕円曲線上の点
・output
V=dA ：Aのd倍点
・algorithm
a201    V=A;
a202    for(i=u-2;i>=0;i=i-1) {
a203      V=2V;
a204      if (di==1) V=V+A; 
a205    }
a206    return V;
アルゴリズム2は上述したアルゴリズム1と同様に、最初にステップ a201 で V = A の初期化を行い、次にステップ a202 でu-bit値 d=(du-1, du-2, ... , d0)2を、 du-1, du-2, l... ,d0 の順にforループで探索する。ただし、du-1=1である。forループ内部では、ステップ a203 で V = 2V の計算処理を行った後に、ステップ a204 でビット値 di =0 ならば何も行わず（点の二倍算のみを実行）、 di = 1 ならば V = V+A の処理を行う（点の二倍算と点の加算を実行）。これを du-1, du-2, ... , d0 のすべてについてくりかえし、点のスカラー倍算処理を行う。最後にステップ a206 で V を計算結果として出力する。【０００９】
〔b. モンゴメリ乗算剰余〕
上述したアルゴリズムを効率的に処理するためのさらなるアルゴリズムとして、モンゴメリ乗算剰余（演算）と呼ばれる方法が知られている（詳細については非特許文献３を参照のこと）。【００１０】
モンゴメリ乗算剰余は、整数s, t, n に対して、 s×t (mod N) で表される乗算剰余演算を高速に実行するためのアルゴリズムである。モンゴメリ乗算剰余を用いることで、 r = 2f 、 f-bit整数 s, t 、およびf-bit奇数 n（但し、0≦s×t≦r×n）に対して、REDC(A,B,N) = s×t×r-1 (mod n) （但し、 r-1 (mod n) は法 n に関する r の逆元を表し、 r×r-1 = 1 (mod n) を満たす）を計算することができる。【００１１】
このアルゴリズムを用いることで、上述したアルゴリズム1および2における二乗算（v = v×v (mod n)）、乗算（v = v×a (mod n)）、点の二倍算（V = 2V）、点の加算（V = V+A）の処理を高速に実行することができ、アルゴリズム1もしくは2の全体の計算を効率的に実行することができる。【００１２】
モンゴメリ乗算剰余の基本的なアルゴリズムをアルゴリズム3として以下に示す。
《アルゴリズム3：モンゴメリ乗算剰余の基本アルゴリズム》
・input
s ： f-bit整数
t ： f-bit整数
n ：剰余の法、f-bit奇数値
・output
v=s×t×r-1 (mod n) ：モンゴメリ乗算剰余結果（r = 2f）
・algorithm
a301    n'=(-n-1) (mod 2f);
a302    h=s×t×n' (mod 2f);
a303    u=((s×t)+(h×n))/2f;  /* (s×t)+(h×n)の下位f-bitはオールゼロ */
a304    if (u≧n) u=u-n;
a305    return u;
このアルゴリズム3に対して、 s, t, n を入力し、ステップ a301 において n' = -n-1(mod 2f) を満たす n' を計算し、ステップ a302 において h = s×t×n' (mod 2f) を満たす h を計算する。続いてステップ a303 で、この h, s, t, n を用いて、 u = ((s×t)+(h×n))/2fを計算する。このとき、 (s×t)+(h×n) は必ず 2fの倍数となる（則ち、下位f-bitがすべてゼロとなる）ことが数学的に保証されているため、ステップ a303 の割り算の結果 u は常に整数となることが保証される（後述する計算例を参照のこと）。ステップ a304 では、 u と n の大小比較を行い、 u が n 以上の値ならば、 u = u-n の計算を行う。ステップ a305 では、 u を計算結果として出力する。【００１３】
アルゴリズム3の計算例を以下に述べる。なお、 "0x〜" として示した数値は十六進数表記である。
s = 0x1234, t = 0x5678, n = 0xffff, f =16 のとき、
a301    n'=(-n-1) (mod 216) = 0x0001
a302    h=s×t×n' (mod 216) = (0x1234)×(0x5678)×(0x0001) (mod 216) = 0x0060
a303    u=((s×t)+(h×n))/216 = (0x06260060 + 0x005fffa0)/216 = 0x06860000/216 = 0x0686  /* a303で計算される(s×t)+(h×n)の下位f-bitはオールゼロ */
a304    u≧n の条件が満たされないので、 u = u-n を実行しない
a305    return 0x0686
アルゴリズム3のモンゴメリ乗算剰余においては、f-bitの変数を用いた乗算を行っている。しかし、暗号演算ではこのfの値が大きくなるのが通常であり、一般に用いられる乗算器が演算可能なビット幅を超えてしまう。例えばRSA暗号では f = 1024 、ECCでは f = 160 であるのに対し、一般的な乗算器は最大でも64-bit×64-bitである。よって、一般的なハードウェアでは上述したアルゴリズム3を直接実行することができない、という問題がある。【００１４】
この問題を解決するために、アルゴリズム3をw-bit×w-bitの乗算器（w<f）で実行可能とするようなアルゴリズム（実装アルゴリズム）が用いられている。モンゴメリ乗算剰余の実装アルゴリズムとしてはさまざまな方法が知られており、その一例をアルゴリズム4として以下に示す。
《アルゴリズム4：モンゴメリ乗算剰余の実装アルゴリズムの例》
・input
s ： f-bit整数
t ： f-bit整数
r ： r = 2f
n ：剰余の法、f-bit奇数値
・output
REDC(s,t) = s×t×r-1 (mod n)
・Multi-precision integers
s=(sg-1, ... , s0)
t=(tg-1, ... , t0)
n=(ng-1, ... , n0)
y=(yg,  ... , y0)
n'=(n'g-1, ..., n'0)
・w-bit word data, where r=2w.
tmp, c1, c2, h'
・algorithm
a401  y = 0;
a402  for (j=0;j<=g-1;j=j+1) {
a403    (c1, tmp) = y0 + s0 × tj;
a404    h' = tmp × n'0 (mod 2w);
a405    (c2, yNULL) = tmp + h'×n0  /* yNULLは常に0 */
a406    for (i=1;i<=g-1;i=i+1) {
a407      (c1, tmp) = yi + c1 + si × tj;
a408      (c2, yi-1) = tmp + c2 + h' × ni;
a409    }
a410    (c2, c1) = C1+C2 +yg;
a411    yg-1 = C1;
a412    yg = C2;
a413  }
a414  if (y>=n) y=y-n;
a415  return y;
アルゴリズム3においては、f-bitの整数データを複数のw-bit変数値として表現しており、例えばs = (sg-1, sg-2, ... , s0) のように、f-bit変数 s はg個のw-bit変数 si （i=0, 1, ... , g-1）（iが小さいほど低位ビット値を表す）を用いて表現される（w×g≧f）。このように、複数のw-bit変数によって表現される整数データを、多倍長整数とよぶ。多倍長整数では、w-bitがデータ表現の基本単位となるので、このw-bitのデータ値のことを1ワードと呼ぶ。【００１５】
アルゴリズム4には、データを1ワードごとに分割し、w-bit×w-bitの乗算を組み合わせることで、最終的にアルゴリズム3を計算できるようにする実装アルゴリズムの例を示している。【００１６】
アルゴリズム4は、 (s×t)+(h×n) で表されるf-bit×f-bitの乗算の和を計算するために、(1) (s×tj)+(n×hj) で表されるf-bit×w-bitの乗算の和を計算するためのループ処理 a402〜a413 （j = 0, 1, ... , g-1）と、 (2) このf-bit×w-bit乗算をw-bit×w-bitの乗算結果を蓄積することで計算するループ処理 a406〜a409 とから構成されている。【００１７】
アルゴリズム3のステップ a303 において計算される (s×t)+(h×n) の下位f-bitはオールゼロであるので、アルゴリズム4で計算される (s×tj)+(n×hj) の下位w-bitも必ず0となることが数学的に保証される。アルゴリズム4では、 (s×tj)+(n×hj) を 2w で割った値が y = (yg, ... , y1, y0) に格納され（ 2wによる割り算は、ステップ a407, a408 でのシフトにより実行される）、必ず0となる下位w-bitの値は、ステップ a405 に示される yNULLに格納される。【００１８】
〔c. CRTつきRSA暗号処理〕
RSA暗号の復号処理を高速に計算するための演算法として、中国人剰余定理（Chinese Remainder Theorem; CRT）と呼ばれるアルゴリズムが知られている。CRTアルゴリズムは、RSAの復号処理 m = cd (mod n) を高速化するための手法である。CRTアルゴリズムを用いることで、RSAの復号化処理を4倍高速に処理することができるため、非常によく用いられている。【００１９】
CRTアルゴリズムによるRSAの復号化処理をアルゴリズム5として以下に示す。
《アルゴリズム5：CRTアルゴリズムによるRSAの復号化処理》
・input: c, dp（= d mod (p-1)）, dq（= d mod (q-1)）, p, q, u（=p-1 (mod q)）
・output: m （= cd mod n）
・algorithm
a501    cp = c (mod p), cq = c mod q
a502    mp = cpdp (mod p)
a503    mq = cqdq (mod q)
a504    m = ((mq-mp) × u (mod q) ) × p + mp
a505    return m
CRTアルゴリズムが処理を高速に行うことができる理由について説明する。RSA暗号においては、法（modulus） n は２つの素数 p, q を用いて n = p×q として表されるが、CRTアルゴリズムでは、法 n における指数剰余演算を計算する代わりに、法 p と法 q について指数剰余演算を行う。 p, q のビット長は n のビット長の半分であり、ビット長が半分になることで指数剰余演算の1回あたりの計算量は1/8となる。（指数剰余演算の計算量はビット長の3乗であるため、 (1/2)3= 1/8 の計算量となる）。ビット長が半分であるこの指数剰余演算を、法 p と法 q について計2回実行する必要があるため、全体の計算量は 2×(1/8) = 1/4 であり、すなわち4倍高速であるということになる。【００２０】
〔d. Fault攻撃〕
Fault攻撃とは、前述したように1997年にBoneh, DeMillo, Liptonによって発表された手法であり、スマートカード等の組み込み機器に搭載された暗号プロセッサの回路に対して、様々なストレス（異常クロック、過電圧、高温度）を与えることで、回路の内部データに異常値を発生させて、暗号プロセッサ内部の秘密鍵を解読する手法である。【００２１】
図２にはFault攻撃の一般的な手順を示す。
まずステップ S201 では、攻撃者はスマートカードにデータを入力し、暗号処理を実行する。続いてステップ S202 で、攻撃者は、暗号処理実行中の暗号回路にストレスを与えることで、内部データ値に異常値を発生（Fault発生）させる。そしてステップ S203 では、攻撃者は、暗号処理の結果として出力される異常なデータ値を得る。こうして得られた異常なデータ値を使った解析計算を行うことで、攻撃者は秘密鍵の値を解読することが可能となる。【００２２】
Fault攻撃は公開鍵暗号機能を搭載したスマートカード全般に対して有効であり、特に、CRTアルゴリズムに対するFault攻撃は、攻撃者にとって実施が容易なため大きな脅威として知られている。【００２３】
CRTアルゴリズムを利用した攻撃手順を、以下にアルゴリズム6として示す。なお、 GCD(a,b) は整数 a, b の最大公約数を表す。例えば GCD(10,25) = 5 である。
《アルゴリズム6：CRTアルゴリズムを利用したFault攻撃法》
a601    攻撃者は、スマートカードに対し暗号文 c を与え、Fault発生をせずにCRTアルゴリズム処理を行い、正常な復号結果 m を得る。なお、 dp, dq, p, q, u は、外部からの入力値ではなく、カード内部に格納されている秘密鍵であることに注意されたい。
a602    攻撃者は、スマートカードに対し暗号文 c を与え、Fault発生させてCRTアルゴリズム処理を行い、異常な復号結果 m' を得る。このとき、明らかに m'≠m である。
a603    攻撃者は、 GCD(m-m', n) を計算して、素数 p = GCD(m-m', n) を得る。この素数 p からは全ての秘密鍵 dp, dq, p, q, u が容易に計算できることが公知である。したがって攻撃者は全ての秘密鍵を解読することができる。
上記のステップ a602 におけるFault発生の詳細を図３に示す。ここでは、上記のアルゴリズム5のステップ番号を流用して説明する。【００２４】
まず攻撃者は、ステップa503 の処理においてFaultを発生させ、法 q に関する指数剰余演算の結果を異常な値とする。すなわち、正常な値 mq = cqdq (mod q) ではなく、異常な値 mq' ≠ cqdq (mod q) が計算されることになる。【００２５】
ステップ a503 の計算結果が異常値となるため、続くステップ s504 で計算される値も異常な値 m' ≠ cd (mod n) となるので、ステップ a505 ではこの異常値 m' が出力される。【００２６】
一般的なFault攻撃においては、Fault発生させるデータの条件が限定され（例えば、或るデータの3番目のビット値を反転させなくてはならない、など）、且つFault発生を50〜200回程度くりかえす必要がある。これとは対照的に、CRTアルゴリズムへのFault攻撃では、上記のステップ a503 でのFault発生においてデータの条件が限定されず、 m'q ≠ mq の条件さえ満たせば、どのビット値をどのように反転させてもよい。さらに、Fault発生を一度成功させるだけで秘密鍵が解読できる。【００２７】
よって、CRTアルゴリズムへのFault攻撃は、攻撃者にとって非常に実施が容易なものであって、スマートカードに対する大きな脅威であることが知られている。
〔e. Fault攻撃への従来技術に係る対策〕
上述したFault攻撃への対策法として、Fault検知という方法が知られている。これは、CRTアルゴリズムの計算結果が異常な値であるかどうかを、スマートカードの内部で検査する手法である。この手法では、CRTアルゴリズムの計算結果が異常な値m' であることがスマートカード内部で検知された場合に、計算結果のデータ出力を中止する。こうすることで、上述した攻撃ステップ a602 の攻撃手順の実施が不可能となり、Fault攻撃を阻止することができる。【００２８】
Fault検知を行う一般的な方法として、CRTアルゴリズムの二重化という方法が知られている。この方法を行うためのアルゴリズムの概略を、アルゴリズム7として以下に示す。
《アルゴリズム7：CRTアルゴリズムの二重化によるFault検知》
a701    c, dp, dq, p, q, u から、CRTアルゴリズムにより m1 を計算する。
a702    c, dp, dq, p, q, u から、CRTアルゴリズムにより m2 を計算する。
a703    m1≠m2ならば、Fault発生ありと判定。m1=m2ならば、Fault発生なしと判定する。
このようにしてCRTアルゴリズムによる計算を二回行い、その計算結果が異なっていたときにFault発生ありと判定し、計算結果が同一だったならばFault発生なしと判定を行っている。【００２９】
〔f. 従来技術に係るFault攻撃対策法の問題点〕
アルゴリズム7に示したFault検知法は、Fault発生の検知を最後のステップa703 のみにおいて実行している。つまり、Faultが発生した時点では即時に検知を行うことができず、Fault発生の検知は最終ステップである a703 において初めて行われるのである。【００３０】
すると、アルゴリズム7を用いているためにFault発生の即時検知を行えないスマートカードにおいては、特定の手順によりFault攻撃が成功するという問題が発生してしまう。図４は、こうしたアルゴリズム7に係るFault検知方式の問題点を表すものである。この図中のRSA演算の 1, 2, 3, 4 という段階（phase）番号は、それぞれアルゴリズム5のステップ a501, a502, a503, a504 に対応する。【００３１】
既に説明した通り、アルゴリズム7に示した検知方式においては、RSAの演算を二度実行し、それぞれの演算結果 m1, m2を比較することによってFault発生の有無を判定している。この検知方式の場合、Faultを一回だけ発生させる攻撃については、Fault発生を検知することができるが、同一条件でFaultを二回発生させる攻撃については、Fault攻撃を検知することはできない。なぜならば、前者の場合には m1 か m2 のいずれかが異常値（ m1' もしくは m2' ）であるために m1'≠m2 または m1≠m2' が満たされるのに対して、後者の場合では m1, m2 が両方とも異常値であるにもかかわらず m1'=m2' となるため、Fault発生したとは判定されないからである。【００３２】
したがって、従来技術に係るCRTアルゴリズムの二重化によるFault検知法には、「Fault発生した時点で即時に検知を行うことができない」という問題点がある。
攻撃技術を有する者にとっては全く同じFaultを複数回発生させることは充分に可能なことであるため、こうした従来技法にはセキュリティ上の大きな問題があると言える。
【非特許文献１】D. Boneh, R. A. DeMillo, and R. J. Lipton., "On the importance of checking cryptographic protocols for faults," In W. Fumy, editor, Advances in Cryptology - EUROCRYPT'97, volume 1233 of Lecture Notes in Computer Science, pages 37-51, Springer-Verlag, 1997.
【非特許文献２】Ingrid Biehl, Bernd Meyer and Volker Muller, "Differential Fault Attacks on Elliptic Curve Cryptosystems," Advances in Cryptology - CRYPT 2000, volume 1880 of Lecture Notes in Computer Science, pages 131-146, Springer-Verlag, 2000.
【非特許文献３】S. R. Dusse and B. S.Kaliski Jr., "A Crytographic Library for the Motorola DSP56000," Advances in Cryptology - EUROCRYPTO '90 (LNCS 473), pages 230-244, 1990.
【非特許文献４】向田、武仲、桝井、鳥居「高速モンゴメリ積和譲与回路の設計」、暗号と情報セキュリティシンポジウム, SCIS2004, 2A3-2
【発明の開示】
【００３３】
本発明は、公開鍵暗号を行う暗号プロセッサにするFault攻撃対策を行うための実装技術である。本技術を用いることで、RSAをはじめとした公開鍵暗号処理の秘密鍵の解読を困難にし、スマートカード等の組み込み機器の安全性を高めることができる。
【００３４】
本発明では、
記憶手段と、
前記記憶手段に格納する値を設定する、初期設定手段と、
前記初期設定手段が設定した値についての複数回のモンゴメリ乗算剰余演算を行う、モンゴメリ乗算剰余演算手段と、
前記複数回のモンゴメリ乗算剰余演算のうちの少なくとも一部のそれぞれごとに、Fault攻撃が発生したかどうかを判定する、Fault攻撃検知手段と
を含んだ暗号処理装置が提供される。
【００３５】
好ましくは、初期設定手段は、f-bit値 s 、 t 、 n 、および h と、w-bit値 n' とを設定して記憶手段に格納する。但し、 f および w は自然数である。
好ましくは、モンゴメリ乗算剰余演算が、 y = REDC(s,t,n) = s×t×2-f(mod n) である。但し、 y はf-bit値である。
【００３６】
好ましくは、Fault攻撃検知手段が、モンゴメリ乗算剰余演算手段が算出する s×t+h×n の下位f-bit値の桁のうちに0では無い数値があった場合にFault攻撃が発生したと判定し、ここで式中の値は、 h = s×t×n’ (mod 2f) 、 n' = -n-1 (mod 2f)
を満たす。
【００３７】
また、本発明では、上述したような暗号処理装置を含んだスマートカード（ICカードなど）も提供する。
また、本発明では、
f-bit値 s 、 t 、 n 、および h と、w-bit値 n' とを設定するステップと（但し、 f および w は自然数）、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たすf-bit値 y を計算するステップと、
前記モンゴメリ乗算剰余演算手段が算出する s×t+h×n の下位f-bit値の桁に0では無い数値があった場合にFault攻撃が発生したと判定してFault攻撃を検知するステップと
を含んだ暗号処理方法も開示する。ここで式中の値は、 h = s×t×n’ (mod 2f) 、 n' = -n-1 (mod 2f) を満たす。
【００３８】
さらに本発明では、上述し方法をコンピュータに実行させるためのプログラムも提供する。
本発明を用いることにより、従来方式で問題となっていた、Faultを複数回発生させる攻撃に対しても検知を行うことが可能となり、暗号処理装置のセキュリティを向上させることができる。
【図面の簡単な説明】
【００３９】
【図１】図１は、従来技術に係るバイナリ法を用いた指数剰余演算の計算例を示す。
【図２】図２は、従来技術に係るFault攻撃の一般的な手順を示す図である。
【図３】図３は、従来技術に係るCRTアルゴリズムを利用したFault攻撃の例を示す。
【図４】図４は、従来技術に係るFault攻撃対策の問題点を説明する図である。
【図５】図５は、従来技術に係るFault攻撃検出法と、本発明に係るFault攻撃検出法との相違点を説明する概要図である。
【図６】図６は、モンゴメリ乗算剰余演算を用いた、本発明の第一の実施形態に係るFault検出法の原理を説明する概要図である。
【図７】図７は、本発明の第一の実施形態に係るFault検知法を実施できる回路 700 の構成を示す。
【図８】図８は、本発明の第一の実施形態に係るFault検知法を実施でき、且つメモリ帯域削減技術を適用した回路 800 の構成を示す。
【図９】図９は、本発明の第二の実施形態に係るFault検出法の原理を説明する概要図である。
【図１０】図１０は、本発明の第二の実施形態に係るFault検知法を実施できる回路 1000 の構成を示す。
【図１１】図１１は、本発明の第二の実施形態に係るFault検知法を実施でき、且つメモリ帯域削減技術を適用した回路 1100 の構成を示す。
【図１２】図１２は、本発明の第三の実施形態に係るアルゴリズムを説明する図である。
【図１３】図１３は、本発明に係るプログラムを実行することができるハードウェアの構成を示す概略図である。
【発明を実施するための最良の形態】
【００４０】
〔定義〕
本明細書中においては、「アルゴリズム」とは、当業者がその目的と結果を理解できるように記した手順のことである。当業者は、本明細書中のアルゴリズムを、適切な機器に実装する上で適切な書式・手段を以って実行することができる。【００４１】
「積和和（演算）」という語は、演算 a×b+c+d を示す言葉であって、積和演算（multiply and accumulation）の出力にさらに和算を行うような演算のことを指す。
以下、本発明の実施形態を図面に基づいて詳細に説明するが、これは本発明を何ら限定するものではない。また、以下に述べる実施形態では、例としてRSA暗号を用いる場合を示しているが、本発明はそれには限定されず、当業者がモンゴメリ乗算剰余を用いる任意の公開鍵方式暗号を用いる任意の装置に対して適用することができる。例えば、ECCに対しても適用することが可能である。
〔基本構成〕
図５は、従来技術に係るFault攻撃検出法（上記のアルゴリズム7として示したもの）と、本発明に係るFault攻撃検出法との相違点を説明する概要図である。ここでは、一例としてRSA暗号の復号化を行う演算を用いて説明している。RSA処理においては、モンゴメリ乗算剰余演算が何千回も繰り返されるため、モンゴメリ乗算剰余を実行するごとにFault検知を行うことで、検知頻度を大きく向上することができる。【００４２】
従来技術に係るCRTアルゴリズムの二重化によるFault攻撃検出法は、上述したように、同一条件でFaultを二回発生させて攻撃を行うことによって破ることができる。
一方、本発明に係るFault攻撃検出法では、モンゴメリ乗算剰余演算の一回ごとについてFault攻撃を検出することができるため、できる限り即時の検出が可能となる。さらに本方法ではRSA演算を二度くりかえす必要が無いため、アルゴリズム7の方法よりも低い計算コストが実現できる。【００４３】
また、望むならば、本発明に係るFault攻撃検出法とCRTアルゴリズムの二重化を共存させることも可能である。
Fault攻撃の発生を検出した場合、暗号処理機能を停止し、攻撃者の盗聴を阻止することができる。【００４４】
図６は、モンゴメリ乗算剰余演算を用いた、本発明に係るFault検出法の原理を説明する図である。ここでも、例としてRSA暗号の復号化を行う演算を用いて説明している。
この図中のRSA演算の 1, 2, 3, 4 という段階番号は、それぞれアルゴリズム5のステップ a501, a502, a503, a504 に対応している。RSAの段階 2 と段階 3 には、上述したように、モンゴメリ乗算剰余演算が複数回含まれている（図では、段階 2 と段階 3 に区切りを入れて各モンゴメリ乗算剰余演算を表現している）。【００４５】
ここでは例として、段階 2 のうちのひとつのモンゴメリ乗算剰余演算で (s×t)+(h×n) が計算されたときのことを示している。正常に計算が行われた場合、算出される値（ここでは十六進数）の下位半分のビット値がすべてゼロ（オールゼロ）となる。一方、この一回のモンゴメリ乗算剰余演算中にFault攻撃がかけられた場合には、図示しているようにビット値がずれ、算出される値の下位半分のビット値にゼロでは無い数が含まれるようになる。本発明に係る実施形態では、このようにして複数回のモンゴメリ乗算剰余演算の各回ごとに、Fault攻撃の検知を行うことができる。【００４６】
モンゴメリ乗算剰余を実行する一般的な回路においては、オールゼロとなる変数のデータは無視される値である。しかし本発明のFault検知は、この無視されるデータ値がオールゼロかどうかを判定するという簡単な方法により、非常に低いコストによるFault検知を実現することができる。
〔実施形態1：動的なh'を用いる場合〕
以下に本発明に係るFault検知アルゴリズムの第一の実施形態をアルゴリズム8として示す。
《アルゴリズム8：Fault検出部分を組み込んだモンゴメリ乗算剰余の実装アルゴリズム》
・input
s ： f-bit整数
t ： f-bit整数
r ： r = 2f
n ：剰余の法、f-bit奇数値
・output
REDC(s,t) = s×t×r-1 (mod n)
・Multi-precision integers
s=(sg-1, ... , s0)
t=(tg-1, ... , t0)
n=(ng-1, ... , n0)
y=(yg, ... , y0)
n'=(n'g-1, ..., n'0)
・w-bit word data, where r=2w.
tmp, c1, c2, h'
・algorithm
a801  y = 0;
a802  for (j=0;j<=g-1;j=j+1) {
a803    (c1, tmp) = y0 + s0 × tj;
a804    h' = tmp × n'0(mod 2w);
a805    (c2, yNULL) = tmp + h' × n0  /* yNULLは正常であれば常に0 */
a806    if (yNULL != 0) return FAULT  /* Fault検知によるエラー終了*/
a807    for (i=1;i<=g-1;i=i+1) {
a808      (c1, tmp) = yi + c1 + si × tj;
a809      (c2, yi-1) := tmp + c2 + h' × ni;
a810    }
a811    (c2, c1) = C1 + C2 + yg;
a812    yg-1 = C1;
a813    yg = C2;
a814  }
a815  if (y>=n) y = y-n;
a816  return y;
このアルゴリズム8は、アルゴリズム3に示したモンゴメリ乗算剰余アルゴリズムに対して、本発明によるFault検知（ステップ a806 に相当）を適用したものとなっている。【００４７】
Fault発生が無い正常な場合には、ステップ a805 で計算される yNULL の値は常に0となる。したがって、ステップ a803, a804 の計算過程でFault発生したかどうかのチェックをステップ a806 で行い、 yNULL が0でない場合にFaultが発生したと判定し、FAULTというエラー値を出力することでFault発生の通知を行ってアルゴリズムを終了する。【００４８】
〔実施形態1-1：アルゴリズム8の基本回路〕
図７は、アルゴリズム8をそのまま回路化した実施例のひとつである。ここに示した回路 700 は、乗算器 701, 702, 703 と、Fault検知回路 704 と、メモリ回路 705 とを含む。メモリ回路 705 は、入出力データ s, t, y, n, n'0 を格納する。なお、図中のデータの流れを示す矢印に付された斜線と文字は、そのデータのビット数を表している。以降の回路図についても同様である。【００４９】
乗算器 701 は、アルゴリズム8のステップ a803, a808 の積和和演算を実行する回路である。また、乗算器 702 は、アルゴリズム8のステップ a805, a809 の積和和を実行し、乗算器 703 は、ステップ a804 の積を実行する。【００５０】
Fault検知回路 704 は、ステップ a805 のFault検知を実行する回路であって、乗算器 703 で行われる積和和の結果が出力された際に、その出力の下位w-bitの値が0であるかどうかを判定する。【００５１】
〔実施形態1-2：バッファ構成を具えるアルゴリズム8の回路〕
前述した回路 700 は、w-bit×w-bitの積和和を基本とした回路構成である。しかし、このような回路構成においては、メモリ帯域に関する問題が発生する。【００５２】
回路 700 では、5個のw-bitのデータ（s, t, y, n, n'0）を読み込む処理（read処理）と、1個のw-bitのデータ（y）を書き込む処理（write処理）が行われる。すなわち、これらのメモリ回路に対して、1cycleあたりにアクセスされる最大のデータ量は、read処理で5w-bit、write処理でw-bitである。メモリ回路の一般的な特徴として、1cycleあたりにアクセスするデータ量が多いほど、メモリ回路のコストが高くなるという問題が知られている。このアクセス帯域の問題を改良するためのモンゴメリ乗算剰余回路の構成として、2w-bit×w/2-bitの積和和を基本とした回路構成が知られている（詳細については非特許文献４を参照のこと）。【００５３】
本発明の実施形態は、メモリ帯域を削減した上記の回路構成を用いても実施することが可能である。
図８には、回路 700 を基本としつつ、前述したメモリ帯域削減技術を適用した場合の回路 800 の構成を示す。回路 800 には、アルゴリズム8のステップ a803, a808 の積和和演算を実行する乗算器 801 と、ステップ a805, a809 の積和和を実行する乗算器 802 と、ステップ a804 の積を実行する乗算器 803 と、Fault検知回路 804 と、入出力データ s, t, y, n, n'0 を格納するメモリ回路 805 とが含まれ、さらには、バッファ回路 806, 807, 808, 809, 810, 811 も含まれる。【００５４】
回路 800 と回路 700 との違いは、2w-bit×w/2-bitの乗算器を用いていることと、バッファ回路 806〜810 の作用である。回路 700 には、1cycleごとにメモリアクセスされるデータ量が、cycleごとにばらつくという問題点がある。その一方で回路 800 は、メモリから読み込んだデータをバッファ回路に一時的に溜めておく。このようにすることで、1cycleごとにメモリアクセスされるデータ量を、各cycle間で平滑化（平均化）することができ、結果としてメモリ帯域を最適化することができる。【００５５】
モンゴメリ乗算剰余の y = s×t+h×n の演算においては、アルゴリズム8に示すように、変数 y, t, n に対するアクセスが最も頻繁に行われる。よって、y, s, n に関するデータ量を平滑化するために、これらのデータをメモリからreadする際にはバッファ 807, 808, 809 を用いて平滑化を行う。これらのバッファ 807, 808, 809 には2w-bitのデータが入力され、w/2-bitのデータとして出力される。つまり、それぞれのバッファは2w-bitのデータが入力されたら、w/2-bitのデータを4個分保持できるので、 y, s, n のデータreadをcycle毎に実行する必要は無く、4cycleに1回のreadでよい。すなわち、4cycleの間に、y, s, n のデータを2w-bitずつ順番に読み込むことが可能となるため、readの帯域を削減することが可能となる。【００５６】
また、データをwriteする際にはバッファ 806 を用いる。バッファ 806 にはw/2-bitのデータが入力され、2w-bitのデータとして出力される。つまり、バッファ 806 はw/2-bitのデータを4個分保持できるので、4cycleに1回のwriteでよいということになる。【００５７】
このように、 y, s, n を2w-bit単位で読み込み、w/2-bit単位で扱うことで、メモリ帯域の削減が可能となるが、単純にビット長を半分にしただけでは、モンゴメリ乗算剰余の全体の処理速度も悪化してしまう。この問題を回避するために、 t, h については2w-bit単位で読み込み、そのまま2w-bitのデータとして扱うことで、2w-bit×w/2-bitの乗算器を基本単位として処理する。これが乗算器 803 の出力を受けるバッファ 810, 811 が存在する理由である。バッファ 810と811 には、w/2-bitのデータが入力され、その後2w-bitのデータをそれぞれ乗算器 802 と 801 へと送る。【００５８】
アルゴリズム8に示したとおり、データ t, h に対するアクセス頻度は y, t, n よりは低いため、これらのデータを2w-bit単位で読み込みそのまま演算を行ってもメモリ帯域を圧迫しない。また、2w-bit×w/2-bitの乗算器を用いることで、w-bit×w-bitの乗算器を用いた場合とほぼ同じ処理速度を実現することができる。つまり、性能を劣化させずにメモリ帯域を削減することができるということである。【００５９】
回路 700 の構成では、1cycleあたりにアクセスされる最大のデータ量は、read処理で5w-bit、write処理でw-bitであるのに対し、回路 800 の構成では、1cycleあたりにアクセスされる最大のデータ量は、read処理で2w-bit、write処理で2w-bitと軽減されている。【００６０】
回路 800 のFault検知回路 804 は、乗算器 802 の出力ではなく、この出力データをバッファリングするバッファ 806 の2w-bitの出力値に0以外の値が含まれているかどうかを判定することで、Fault検知を行う。これは、2w-bit×w/2-bitの乗算において、 h は2w-bit入力として扱われるため、Fault発生の無い正常な処理の場合には、バッファ 806 の2w-bitの出力値がすべて0となるためである。【００６１】
なお、この実施形態1-2の説明では例として2w-bit×w/2-bitの乗算器とそれに応じたバッファの構成を示したが、本発明はこれには限定されず、当業者が適切と考える任意の自然数 k についての(k*w)-bit×(w/k)-bitの乗算器とそれに応じたバッファから構成した回路を実施することもできる。
〔実施形態2：事前計算したh'を用いる場合〕
モンゴメリ乗算剰余を実行するためのアルゴリズムには、アルゴリズム4として示したもの以外にも様々な他のアルゴリズムが存在し知られている。前述のアルゴリズム8の場合、ステップ a803, a804 の計算で発生したFaultを検知することができるが、ステップ a807 以降のFault発生については検知することができない。これは、ステップ a804 に示したように、 h' の値を内部変数に応じて動的に更新しているためである。【００６２】
よって、h'の計算法を変更することで、こうした問題を回避することができる。Fault検知条件の改良を行ったモンゴメリ乗算剰余アルゴリズムを、アルゴリズム9として以下に示す。
《アルゴリズム9：Fault検出条件の改良を行ったモンゴメリ乗算剰余の実装アルゴリズム（ h' を事前計算）》
・input
s ： f-bit整数
t ： f-bit整数
R ： R = 2f
N ：剰余の法、f-bit奇数値
・output
REDC(A,B) = A×B×R-1 (mod N)
・Multi-precision integers
s=(sg-1, ... , s0)
t=(tg-1, ... , t0)
n=(ng-1, ... , n0)
h=(hg-1, ... , h0), where h = s×t×n' (mod R)
y=(yg, ... , y0)
・w-bit word data, where r=2w.
tmp, c1, c2, h
・algorithm
a901  y = 0;
a902  for (j=0;j<=g-1;j=j+1) {
a903    (c1, tmp) = y0 + s0 × tj;
a904    (c2, yNULL) = tmp + hj×n0  /* yNULLは正常であれば常に0 */
a905    if (yNULL != 0) return FAULT  /* Fault検知によるエラー終了*/
a906    for (i=1;i<=g-1;i=i+1) {
a907      (c1, tmp) = yi + c1 + si × tj;
a908      (c2, yi-1) := tmp + c2 + hj × ni;
a909    }
a910    (c2, c1) = C1 + C2 + yg;
a911    yg-1 = C1;
a912    yg = C2;
a913  }
a914  if (y>=n) y = y-n;
a915  return y;
アルゴリズム9では、 h をモンゴメリ乗算剰余の内部変数に応じて動的に計算すること無く、事前計算データとして与えている（h = s×t×n' (mod 2f) 、すなわち乗算値の下位ビットとして与えている）。【００６３】
アルゴリズム9では、 h をワード単位に分割した h = (hg-1, ... , h0) のうちのそれぞれの値 hj を用いて、モンゴメリ乗算剰余演算を実行している。
アルゴリズム8の処理がステップ a803, a804 に相当する計算処理中のFault発生のみを検知するのに対して、アルゴリズム9の処理は、ステップ a903〜a908 における計算処理中のFault発生を検知することができる。 厳密に言うと、アルゴリズム9では全ての計算処理のFault発生を検知することはできないが、ステップ a903〜a908 における計算処理のうちの半分のFault発生を検知することができる。【００６４】
図９は、アルゴリズム9のステップ a903〜a908 のうち、Fault発生が検知可能である計算処理を示している（g=4の場合）。検知可能な計算処理が全体の半分であるのは、アルゴリズム3で示したモンゴメリ乗算剰余で計算される (s×t)+(h×n) の下半分のビット値（すなわち下位f-bit値）が0となるためである。【００６５】
〔実施形態2-1：アルゴリズム9の基本回路〕
図１０は、アルゴリズム9をそのまま回路化した実施例のひとつである。ここに示した回路 1000 には、アルゴリズム9のステップ a903, a907 の積和和を実行する乗算器1001 と、ステップ a904, a908 の積和和を実行する乗算器 1002 と、Fault検知回路 1003 と、入出力データ s, t, y, n, h を格納するメモリ回路 1004 とを含む。Fault検知回路 1003 は、乗算器 1002 の出力の下位w-bitの値が0であるかどうかを判定することでFault検知を行う。【００６６】
〔実施形態2-2：バッファ構成を具えるアルゴリズム9の回路〕
上述した実施形態1-2と同様のバッファを、回路 1000 にも加えることが可能である。
図１１には、回路 1000 を基本としつつ、前述したメモリ帯域削減技術を適用した場合の回路 1100 の構成を示す。回路 1100 には、アルゴリズム9のステップ a903, a907 の積和和演算を実行する乗算器 1101 と、ステップ a904, a908 の積和和を実行する乗算器 1102 と、Fault検知回路 1103 と、入出力データ s, t, y, n, h を格納するメモリ回路 1104 とが含まれ、さらには、バッファ回路 1105, 1106, 1107, 1108, 1109 も含まれる。これらのバッファ回路 1105〜1109の作用により、回路 1100 は回路 800 と同様にしてメモリ帯域を最適化することができる。【００６７】
回路 1100 のFault検知回路 1103 は、乗算器 1102 の出力をバッファリングするバッファ 1105 の2w-bitの出力値に0以外の値が含まれているかどうかを判定することで、Fault検知を行う。
〔実施形態3：事前計算したn'を用いる場合〕
さらなる実施形態として、本発明は n' = -n-1 (mod 2f) を事前計算して与えるアルゴリズムを用いて実現することもできる。このようなアルゴリズムの例を、アルゴリズム10として以下に示す。
《アルゴリズム10：Fault検出条件の改良を行ったモンゴメリ乗算剰余の実装アルゴリズム（ n' を事前計算）》
・input
s ： f-bit整数
t ： f-bit整数
R ： R = 2f
n ：剰余の法、f-bit奇数値
n' ： n' = -n-1 (mod 2f)
・output
REDC(A,B) = A×B×R-1 (mod N)
・Multi-precision integers
s=(sg-1, ... , s0)
t=(tg-1, ... , t0)
n=(ng-1, ... , n0)
h=(hg-1, ... , h0)
n'=(n'g-1, ... , n'0), where n' = -n-1 (mod 2f)
y=(yg, ... , y0)
z=(z2g-1, ... , z0)
z'=(z'2g-1, ... , z'0)
・w-bit word data, where r=2w.
tmp, c
・algorithm
a1001    y=0, z=0, z'=0, h=0;
a1002    for (j=0;j<=g-1;j=j+1) {  /* z = s×t の計算 */
a1003      c=0;
a1004      for (i=1;i<=g-1;i=i+1) {
a1005        (c, zi+j) = zi+j + c + si × tj;
a1006      }
a1007    zg+j = c;
a1008    }
a1009    for (j=0;j<=g-1;j=j+1) {  /* h= z×n' (mod 2f)の計算 */
a1010      c=0;
a1011      for (i=1;i<=g-1-j;i=i+1) {
a1012      (c, hi+j) = hi+j+ c + zi × n'j;
a1013      }
a1014    }
a1015    for (j=0;j<=g-1;j=j+1) {  /* z' = h×nの計算 */
a1016      c=0;
a1017      for (i=1;i<=g-1;i=i+1) {
a1018      (c, z'i+j) = z'i+j+ c + hi × nj;
a1019      }
a1020    z'g+j = c;
a1021    }
a1022    c=0;  /* y = (z+z')/2f の計算 */
a1023    for (j=0;j<=2g-1;j=j+1) {
a1024      (c, tmp) = zj + z'j+c;
a1025      if (j<g) {（tmpの値を検査し、非ゼロならばFault発生と判定）
a1026      } else {yj = tmp};
a1027    }
a1028    yg=c;
a1029    if (y>=n) y = y-n;
a1030    return y;
アルゴリズム9では、「n'を計算」→「n'とsとtからhを計算」という二段階の事前計算が必要であるが、それに対してアルゴリズム10では n' を事前計算するだけでよいため、事前計算するパラメータを簡略化できる。【００６８】
図１２は、アルゴリズム10の流れを説明する概略図である。 z+z' = (s×t)+(h×n) であり、 s, t, h, n のいずれもf-bit整数、 z, z' は2f-bit整数である。 z+z' の下位f-bit値は正常であればすべてゼロになるため、ここに非ゼロの数が含まれているかどうかを検査することによりFault発生を検出できる。【００６９】
上述した本発明に係る回路のすべては、一般的なスマートカード（ICカードを含む）に搭載することが可能である。
図１３は、本発明に係るプログラムを実行することができるハードウェア構成の概要図であって、CPU 1300 、メモリ 1302 、入力装置 1304 、出力装置1306 、外部記憶装置 1308 、媒体駆動装置 1310 、可搬記録媒体1312 、ネットワーク接続装置 1314 が、バス 1316 によって接続されている。本発明に係るプログラムは、外部記憶装置 1308 もしくは媒体駆動装置 1310 によって駆動される可搬記録媒体1312 に格納することができる。また、ハードウェアは、ネットワーク接続装置1314 を介してネットワークと接続することができ、入力装置 1304 および出力装置 1306 を通じて本発明に係るプログラムを入出力することが可能である。【００７０】
本発明を用いることにより、Faultが発生しない場合に "0" となるデータ値のチェックを行うことで、従来法では実現できなかったFault発生の即時検知を実現することができ、セキュリティ上の問題を回避できる。【００７１】
また、本発明に係る回路は、モンゴメリ乗算剰余演算の内部処理においてFault状態の発生を検知するため、モンゴメリ乗算剰余演算を用いる様々な公開鍵暗号の機能を搭載したスマートカードに対して応用可能である。
【図１】
2008114315.tif 000003
【図２】
2008114315.tif 000004
【図３】
2008114315.tif 000005
【図４】
2008114315.tif 000006
【図５】
2008114315.tif 000007
【図６】
2008114315.tif 000008
【図７】
2008114315.tif 000009
【図８】
2008114315.tif 000010
【図９】
2008114315.tif 000011
【図１０】
2008114315.tif 000012
【図１１】
2008114315.tif 000013
【図１２】
2008114315.tif 000014
【図１３】
2008114315.tif 000015
【手続補正書】
【提出日】平成21年4月15日(2009.4.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
記憶手段と、
前記記憶手段に格納する値を設定する、初期設定手段と、
前記初期設定手段が設定した値についての複数回のモンゴメリ乗算剰余演算を行う、モンゴメリ乗算剰余演算手段と、
前記複数回のモンゴメリ乗算剰余演算のうちの少なくとも一部のそれぞれごとに、Fault攻撃が発生したかどうかを判定する、Fault攻撃検知手段と
を含むことを特徴とする暗号処理装置。
【請求項２】
記憶手段と、
g個のw-bit変数（但し、 g は自然数）を用いて表されるf-bit値 s = (sg-1, ... , s1, s0) 、 t = (tg-1, ... , t1, t0) 、 n = (ng-1, ... , n1, n0) 、および h = (hg-1, ... , h1, h0) と、w-bit値 n'0 とを設定して前記記憶手段に格納する、初期設定手段と、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たす、(g+1)個のw-bit変数で表されるf-bit値 y = (yg, ... , y1, y0) を計算する、モンゴメリ乗算剰余演算手段と（但し、 f は自然数）、
前記モンゴメリ乗算剰余演算手段が算出する (s×ti)+(hi×n) （但し、 i は 0≦i≦g-1 を満たす整数）の下位w-bit値を、変数 yNULL に格納し、前記変数 yNULLが非ゼロであった場合にFault攻撃が発生したと判定する、Fault攻撃検知手段と
を含むことを特徴とする暗号処理装置。
（但し、式中の値は
f > w
hi = s×ti×n'0 (mod 2w) （但しiは上述したもの）
n'0 = -n-1 (mod 2w)
を満たす）
【請求項３】
記憶手段と、
g個のw-bit変数を用いて表されるf-bit値 s = (sg-1, ... , s1, s0) 、 t = (tg-1, ... , t1, t0) 、および h = (hg-1, ... , h1, h0) と、w-bit値 n'0とを設定して前記記憶手段に格納する、初期設定手段と（但し、 g および w および f は自然数）、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たす、(g+1)個のw-bit変数で表されるf-bit値 y = (yg, ... , y1, y0) を計算する、モンゴメリ乗算剰余演算手段と、
前記モンゴメリ乗算剰余演算手段が算出する (s×t0)+(h'×n0)の下位w-bit値を、変数 yNULL に格納し、前記変数 yNULL が非ゼロであった場合にFault攻撃が発生したと判定する、Fault攻撃検知手段と
を含み、ここで式中の値は
f > w
h = s×t×n'0 (mod 2f)
n'0 = -n-1 (mod 2w)
を満たし、また、
前記モンゴメリ乗算剰余演算手段が、式中 h' を、変数 b に関するループ変数 j が更新されるごとに
h' = ((a0×bj)+y0)×n'0(mod 2w)
として動的に更新する
ことを特徴とする暗号処理装置。
【請求項４】
記憶手段と、
g個のw-bit変数を用いて表されるf-bit値 s = (sg-1, ... , s1, s0) 、 t = (tg-1, ... , t1, t0) 、 n = (ng-1, ... , n1, n0) 、および h = (hg-1, ... , h1, h0) を設定して前記記憶手段に格納する、初期設定手段と（但し、 g および w は自然数）、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たす、(g+1)個のw-bit変数で表されるf-bit値 y = (yg, ... , y1, y0) を計算する、モンゴメリ乗算剰余演算手段と（但し、 f は自然数）、
前記モンゴメリ乗算剰余演算手段が算出する (s×t0)+(hj×n) （0≦j≦g-1）の下位w-bit値を、変数 yNULL に格納し、前記変数 yNULL が非ゼロであった場合にFault攻撃が発生したと判定する、Fault攻撃検知手段と
を含み、ここで式中の値は
f > w
h = s×t×n (mod 2f)
n' = -n-1 (mod 2f)
を満たし、また、
式中の h は、前記初期設定手段により前記モンゴメリ乗算剰余演算手段の計算が行われる前に与えられている
ことを特徴とする暗号処理装置。
【請求項５】
前記記憶手段および前記モンゴメリ乗算剰余演算手段のそれぞれから読み込んだw-bit単位のデータを用い、w-bit×w-bitの乗算を行って前記変数 yNULL として出力する、w-bit×w-bit乗算手段
をさらに含むことを特徴とする、請求項２〜４のいずれか一項に記載の暗号処理装置。
【請求項６】
f-bit値 s 、 t 、 n 、および h と、w-bit値 n' とを設定するステップと（但し、 f および w は自然数）、
前記初期設定手段が設定した値についてのモンゴメリ乗算剰余演算 y = REDC(s,t,n) = s×t×2-f(mod n) を満たすf-bit値 y を計算するステップと、
前記モンゴメリ乗算剰余演算手段が算出する s×t+h×n の下位f-bit値の桁に0では無い数値があった場合にFault攻撃が発生したと判定してFault攻撃を検知するステップと
を含み、ここで式中の値は
h = s×t×n (mod 2f)
n' = -n-1 (mod 2f)
を満たすことを特徴とする、暗号処理方法。
【国際調査報告】
2008114315.tif 000016
2008114315.tif 000017