• III.3.3.4.1 解析原理
  • III.3.3.4.1.1 楕円曲線上の乗算
  • III.3.3.4.1.2 電力消費量を利用したQ=dPのdの導出
    • III.3.3.4.1.2.1 単純電力解析に対する対処
    • III.3.3.4.1.2.2 倍加算法に対する電力差分解析
    • III.3.3.4.1.2.3 任意のスカラー乗算アルゴリズムへの拡張
  • III.3.3.4.1.3 楕円曲線暗号への攻撃
    • III.3.3.4.1.3.1 楕円ElGamal暗号
    • III.3.3.4.1.3.2 楕円曲線Diffie-Hellman鍵配送

III.3.3.4 楕円曲線暗号に対する電力解析

Kocherらによって提案された電力差分攻撃は 電力信号を計測することでスマートカード内の秘密情報を不 正に入手することを可能とする強力な攻撃方法である．スマートカード上の DESの解析に対し，Kocherらは電力差分解析を適用し1000回の暗号化処理を行うことで秘 密鍵の導出に成功している．[Cor99]において，楕円曲線暗号系に対する電力差分解析 を一般化し，それを楕円曲線上のDiffie-Hellman鍵配送や楕円曲線上の ElGamal型暗号に適用した．これらの攻撃を利用した場合，スマートカード内 の秘密鍵を取り出すことが可能である．また，これらの攻撃に対する対応方法 についても検討が行なわれている．本節では，これらの手法の紹介を行なう． 対処方法についてはIII.3.3.5.3.4節を参照のこと．

楕円曲線の暗号への応用は1985年にMillerとKoblitzによって初めて提案され た．それ以来，様々な楕円曲線暗号系の研究は活発に行われている．楕円曲線 は，従来の離散対数暗号系で利用されている群構造と置き換え可能な群構造を 提供する．位数$n$の元$g$による巡回群での離散対数問題は，$G$の元$y=g^x$に対し$x$ を導出することである．楕円曲線上の離散対数問題は有限体上の乗法群のよう な他の群より大幅に困難であると考えられている．超特異楕円曲線以外の楕円 曲線上の離散対数問題においては，準指数オーダーの計算時間での計算アルゴ リズムは知られていない．このため，楕円曲線暗号系においては秘密鍵のサイ ズは160ビット程度で充分となる．

[Cor99]においては，スマートカード上に実装された楕円曲線暗号に対し，電力 消費量を計測することで攻撃を試みている．電力差分解析は電力消費量に応じた秘密情報の 漏洩を利用した強力な攻撃である．電力差分解析はDESに対して適用され，1000回の暗号 化処理によって秘密鍵を不正に入手することに成功している．さらに，AESの 候補に挙がっている暗号系のスマートカード上の実装に対しても電力差分解析が効果的 であることが示されている．これらの結果により楕円曲線暗号の単純な実装に対 しても電力差分解析が効果的であることが確認された．

III.3.3.4.1 解析原理

III.3.3.4.1.1 楕円曲線上の乗算

楕円曲線上の点$P$の$d$倍を導出する処理をスカラー乗算と呼び，$dP$と表記する．楕円曲線上のスカラー乗算は$\bmod m$による整数の乗法群に類似している．

$dP$の計算は倍加算法(double-and-add algorithm)をそのまま適用することで行うことができる． $d=\{d_{l-1},\cdots,d_{0}\}$とビット列表記し($d_{l-1}$を最上位ビット とする)，次のアルゴリズム$1$によってこれを示す．

図 III.24: アルゴリズム1

スカラー乗算を高速に行うための様々な手法が存在している．$P$が既知の場 合，$P$の乗算に関する表を事前に計算することは有効的である．楕円曲線に おいて減算と加算のコストは等しいため，倍加算法は次の 加減算法(addition-subtraction algorithm)に改良することができる．

$$d = \sum_{i=0}^{l-1}c_i 2^i, \hspace{0.5cm} c_i \in \{-1,0,1\}$$

$d$のNAF (non-adjacent form)とはすべての$i \geq 0$に対して $c_i \times c_{i+1}=0$となるような，$d$の符号付二進表記である．すべての正整数はNAFに よってユニークに定められ，なおかつNAFは$d$の符号付二進表記のうち非ゼロ係 数の数を最小にすることが知られている．アルゴリズム$2$に 加減算法を示す．

図 III.25: アルゴリズム2

最小の(楕円曲線上の)計算処理回数でdPを計算する方法を見つけることは，$d$ の最も短い加減算鎖を見つけることと同値である． 加減算鎖とは次のような正整数の系列である．

$$a_0 = 1 \rightarrow a_1 \rightarrow a_2\rightarrow \cdots \r... ...\hspace{0.5cm} a_i = \pm aj \pm ak, \hspace{0.5cm} k \leq j<i$$

$d$の最も短い加減算鎖は $a_1 P,a_2 P, \cdots ,a_rP=dP$と計算することで，最小の計算処理回数で$dP$を導出することができる．

III.3.3.4.1.2 電力消費量を利用したQ=dPのdの導出

1998年，KocherはDESに対する単純電力解析と電力差分解析を著した． 単純電力解析は暗号アルゴリズム一つの実行とその電力消費量の観測により行われる． 電力差分解析はより洗練された強力な攻撃方法である．これは，一つの暗号アルゴリズ ムに対してさまざまな入力を行い，その結果に対して統計的な解析をする．本 節では，$Q=dP$の計算中で消費される電力を観測することでdを導出する手法を 示す．まず，スカラー乗算の単純な実装に対しる単純電力解析の有効性を議論し，その 対応手法を併せて示す．その後，スカラー乗算に対する，電力差分解析による攻撃方法 を示す．

III.3.3.4.1.2.1 単純電力解析に対する対処

電力消費量を観測することで，視覚的にさまざまな重要な特性を識別すること ができる．たとえば，アルゴリズム$1$における乗算と加算の判別などが可能で ある．単純電力解析への対処方法としてアルゴリズム中の命令が扱われているデータに 依存しないようにしなければならない．一つの方法として，アルゴリズム内に データに依存した分岐を持たせないことが考えられる．この手法でアルゴリズ ム$1$に改良を加えたものが次のアルゴリズム$1'$である．

図 III.26: アルゴリズム1'

III.3.3.4.1.2.2 倍加算法に対する電力差分解析

本節では，アルゴリズム$1'$に対する電力差分解析を示す．アルゴリズムは一定時間で終 了することを仮定する．この仮定が成立しない場合，時間攻撃や単純電力解析が容易に 行われる．

DESへの電力差分解析は電力消費量と鍵に依存した特定のビットの相関を利用している． たとえば，ひとつの最初のラウンドのSBOXの出力におけるビット$b$は入力メッ セージと鍵の6個の未知のビットに依存している．そこで，6個の未知のビット の取りうる値に対する出力$b$と電力消費量の相関を調べてやることで6個の未知 のビットの値を推測することが可能となる．これを残りのSBOXに対しても適用 してやることで合計48ビットの値が求められる．未知のままの残り8ビットは 全数探索で導出すればよい．

アルゴリズム$1'$に対する電力差分解析は$j$ステップ目において$Q$の値が $(d_{l-1},\cdots,d_j)$にのみ依存していることを利用している．ここで，点 の値がメモリ内でどのように表されているかわかっているものとする．点$Q$が アルゴリズム中で取り扱われるとき，$Q$のある特定のビットと電力消費量に相 関が生じる．アルゴリズム中で取り扱われない点と電力消費量には相関は生じ ない．これゆえ，スマートカード内で取り扱われている点を推測することが可 能である．

$d$の最上位ビットから二ビット目${d_{l-2}}$は電力消費量と$4P$の二進表現によるビット列中の特定のビットとの相関を計算することにより導出される．もし，$d_{l-2} = 0$であれば，$4P$がアルゴリズム$1'$中に出現する．一方，$d_{l-2} = 1$であれば，$4P$は絶対に出現しない．この手法により，$d_{l-2}$を求めることができる．同様の手法により残りのビットも導出される．

アルゴリズム$1'$が点 $P_1,P_2,..,P_k$に対して適用され， $Q_1=dP_1,\cdots,Q_k=dP_k$の計算が行われるものとする．$C_i(t)$を$Q_i=dP_i$の 計算を実行したときの電力消費量とする．$s_i$を$4P_i$のある特定のビットとする と，$s_i$と$C_i(t)$の相関関数は次のように表される．

$$g(t)=<C_i(t)>i=1,2,\cdots,k\vert _{s_i=1} - <Ci(t)>i=1,2,\cdots,k\vert _{s_i}=0$$

$4P_i$が$t=t_i$で実行されたとき，その電力消費量$C_i(t_1)$は$s_i$と相関 が生じると仮定する．$s_i=1$のときの平均消費電力は$s_i=0の$ときの平均消 費電力と異なったものとなる．そのため，$t=t_i$において$g(t)$にピークが 現れる．$4P_i$がアルゴリズム中で出現しなかったものとすると$g(t)$中にピー クは現れない．

III.3.3.4.1.2.3 任意のスカラー乗算アルゴリズムへの拡張

ここでは上記の電力差分解析を加減算鎖アルゴリズムに適用する手法を 示す．つまり，

$$a_0 = 1 \rightarrow a_1 \rightarrow a_2 \rightarrow \cdots \... ...pace{0.5cm} a_i = \pm a_j \pm a_k, \hspace{0.5cm} k \leq j < i$$

に対して $a_i' = \pm a_j \pm a_k, k \leq j < i$を満足するすべての$a_i'$ を$a_i$のとりうる値として挙げる．これらの$a_i'$に関して，$a_i'P$と電力 消費量との相関を調べる．もし，そこに有意な相関が観測されれば，$a_i'P$がア ルゴリズム中に出現したことを意味し，$a_i=a_i'$であるといえる．この手法によ り，$d = a_r$を$O(r^2)$の計算時間で導出することができる．

III.3.3.4.1.3 楕円曲線暗号への攻撃

本節では，楕円ElGamal暗号と楕円Diffie-Hellman鍵配送に対する電力差分解析の適用方 法を示す．楕円曲線DSAでは固定された指数ではなくランダムな指数を用いて いるため電力差分解析の適用はできない．

III.3.3.4.1.3.1 楕円ElGamal暗号

楕円ElGamal暗号での処理手続きを以下に示す．

システムパラメータ:

$\varepsilon$: $GF(p)$もしくは$GF(2^n)$上の楕円曲線曲線

$\sharp \varepsilon$: $\varepsilon$の位数

$q$: $q\vert\sharp \varepsilon$を満足する大きい素数

$G$: $\varepsilon$上の位数$q$の元

鍵生成:

秘密鍵: $d \in [1,\cdots,q-1]$

公開鍵: $Q=dP$

メッセージ$m$の暗号化：

乱数 $k∈[1,\cdots,q-1]$

$kP = (x_1,y_1), \ kQ = (x_2,y_2), \ c = x_2 + m$を計算．

$(x_1,y_1,c)$が暗号文

復号化：

$(x_2',y_2')=d(x_1,y_1), \ m = c-x_2'$．

楕円ElGamal暗号への電力差分攻撃では， さまざまな暗号文$(x_1,y_1,c)$を用いて復号化を行い， $d(x_1,y_1)$の計算に電力差分解析を適用することで 秘密鍵$d$を導出することが可能である．

III.3.3.4.1.3.2 楕円曲線Diffie-Hellman鍵配送

楕円曲線Diffie-Hellman鍵配送法での処理手続きを以下に示す．

システムパラメータ:

$\varepsilon$: $GF(p)$もしくは$GF(2^n)$上の楕円曲線曲線

$\sharp \varepsilon$: $\varepsilon$の位数

$q$: $q\vert\sharp \varepsilon$を満足する大きい素数

$G$: $\varepsilon$上の位数$q$の元

鍵生成:

Alice, Bobの秘密鍵: $s_A,s_B \in [1,..,q-1]$

Alice, Bobの公開鍵: $Q_A={s_A}P, Q_B={s_B}P$

鍵共有：

$P_{AB}={s_A}{Q_B}={s_B}{Q_A}$を計算．

もし$P_{AB}=0$であればエラーを出力する．

共有鍵は$P_{AB}$の$x$座標を用いる．

楕円曲線Diffie-Hellman鍵配送への電力差分攻撃では， さまざまな利用者の公開鍵に対して鍵共有のための計算 $P_{AB}={s_A}{Q_B}={s_B}{Q_A}$を実行し， それらに電力差分解析を適用することで 秘密鍵$s_A,s_B$を導出することができる．