III.3.1.4 RSAへの適用

RSAのべき乗剰余算における故障利用解析(DFA)を述べる． RSAは共通の法を用いて互いに素な$e_1$と$e_2$を用いて同一のメッセージ$m$を 暗号化した場合，メッセージ$m$が導出できてしまうことが知られている． メッセージ$m$の暗号文をそれぞれ $c_1=m^{e_1}\bmod n$, $c_2=m^{e_2}\bmod n$とすると， $gcd(e_1,e_2)=1$より$ue_1+ve_2=1$を満たす $u,v\in{\cal Z}$が存在し，$m$は次式で求められる．

$$m = m^{ue_1+ve_2}\equiv c^u_1c^v_2 \bmod n$$

RSAに対するDFAの適用では，DFAによって同様の状況を生じさせることにより，RSAへの攻撃が可 能となる[JQ97]．

べき指数$e$の二進化表現を $e=\sum_{i=0}^{t-1}e_i 2^i$とする． $j$ビット目にエラーを引き起こしビットを反転させたとする． メッセージ$m$を暗号化した結果は本来$c=m^e\bmod n$であるが， ビットのエラーにより $\widehat{c}=m^{\widehat{e}}\bmod n$となる． ここで，

$$\widehat{e}=\left\{\begin{array}[tb]{cc} e+2^j & e_j=0のとき\\ e-2^j & e_j=1のとき \end{array}\right.$$

である． また， $\delta = gcd(\widehat{e}, e)$とすると， $\delta = gcd(e\pm 2^j,e)$ より$\delta$は$2^j$の約数である．RSAでは$e$は奇数であるため，$\delta=1$ が成り立つ．すなわち$\widehat{e},e$は互いに素である．

したがって，共通の法を用いた場合同様に$c$と$\widehat{c}$からメッセージ $m$の導出が可能である． また，$e$を2ビット以上変化させる場合この攻撃法が適用出来るかは $gcd(\widehat{e},e)$に依存する．ただし$e$に素数を用いた場合， この攻撃は(MSBより大きなビットを操作しないならば)常に適用できる．