第4話に追記するには少々長く, また第5話として書くような内容でもない気がしたため番外編とした.
前回, 楕円曲線上でのデジタル署名(ECDSA)の解説をした.
ECDSAでは, 署名にある適当な乱数\(k\)を使用するが, この\(k\)が乱数ではなく全て固定値として署名されていた場合どうなるのか, について本稿で解説する.
先に答えを言うと, 秘密鍵が漏洩するので絶対に固定値を利用してはいけない.
2010年に, ECDSAの実装に問題のあったPS3で秘密鍵の取得が可能であることが報告されている.
Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access.
Proof
メッセージM1, M2に対するハッシュ値を \(e1, e2\)
それぞれの署名を \((r_{1}, s_{1}),(r_{2}, s_{2})\)
共通の固定値を\(k\)として秘密鍵\(d\)を解読していく.
本稿では, \(r\)は既に導出されているものとし, \(s\)の計算から解説を始める.
\begin{eqnarray} s_{1} &=& k^{-1}(e_{1} + r_{1}d) \newline s_{2} &=& k^{-1}(e_{2} + r_{2}d) \newline \end{eqnarray}
\(k\)は共通の定数なので, 両辺に\(k\)をかけ\(k = \)の形にすると
$$ k = \frac{e_{1} + r_{1}d}{s_{1}} = \frac{e_{2} + r_{2}d}{s_{2}} $$
\(k\)にご退場いただき, 秘密鍵\(d\)について解くように式を変形していく.
\begin{eqnarray} s_{2}(e_{1} + r_{1}d) &=& s_{1}(e_{2} + r_{2}d) \newline s_{2}e_{1} + s_{2}r_{1}d &=& s_{1}e_{2} +s_{1}r_{2}d \newline s_{2}r_{1}d - s_{1}r_{2}d &=& s_{1}e_{2} - s_{2}e_{1} \newline (s_{2}r_{1} - s_{1}r_{2})d &=& s_{1}e_{2} - s_{2}e_{1} \newline \end{eqnarray}
よって $$ d = \frac{s_{1}e_{2} - s_{2}e_{1}}{s_{2}r_{1} - s_{1}r_{2}} $$
署名が2つあれば, 以上の計算で秘密鍵を得ることができる.
署名用の秘密鍵を得るとたとえばどのようなことができるのかについては, 逮捕されたくないのでコメントを控える.
実は, \(k\)が固定値なので\(r_{1} = r_{2}\)である.
