next up previous contents
Next: III.3.1.5 ElGamalへの適用 Up: III.3.1 故障利用解析 Previous: III.3.1.3 RC5への適用

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$は次式で求められる.

\begin{displaymath}
m = m^{ue_1+ve_2}\equiv c^u_1c^v_2 \bmod n
\end{displaymath}

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$となる. ここで,

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

である. また, $\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より大きなビットを操作しないならば)常に適用できる.