デジタル署名への攻撃
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/01 16:19 UTC 版)
デジタル署名は誕生日攻撃に弱い場合もある。メッセージ m {\displaystyle m} に暗号学的ハッシュ関数 f {\displaystyle f} と秘密鍵を適用して署名 f ( m ) {\displaystyle f(m)} を得る。ここでアリスがボブを騙し、ニセの契約書に署名させる場合を考える。アリスはまず正しい契約書 m {\displaystyle m} とニセの契約書 m ′ {\displaystyle m'} を用意する。次に m {\displaystyle m} の意味を変えずに字面を変えた書面をコンマを挿入したり、空行を挿入したり、文の後の空白を増やしたり、同義語で置換したりしていくつも作成する。このようにすることで、正しい契約書 m {\displaystyle m} の膨大なバリエーションを作成できる。 同様の手法でアリスはニセの契約書 m ′ {\displaystyle m'} についても多数のバリエーションを作成する。次にアリスは、それらの正しい契約書とニセの契約書の全バリエーションについてハッシュ関数を適用し、同じハッシュ値 f ( m ) = f ( m ′ ) {\displaystyle f(m)=f(m')} となるものを探す。そして、衝突した正しい方の契約書をボブに提示し署名を求める。ボブが署名したら、アリスはその署名を切り出し、ニセの（衝突した）契約書に添付する。この署名はボブがニセの契約書に署名したことを証明している。これは本来の誕生日問題とは若干異なり、正しい契約書間同士のペアやニセの契約書間同士のペアで衝突が見つかってもアリスには何の利益も生じない。アリスが詐欺を成功させるには、正しい契約書とニセの契約書の組み合わせのペアで衝突が発生する文面を見つける必要がある。つまり、上の説明での n {\displaystyle n} は正しい契約書とニセの契約書のペアの個数に相当するため、アリスは実際には 2 n {\displaystyle 2n} 回ハッシュ値生成を試行しなければならない。 このような攻撃を防ぐため、署名で使用するハッシュ関数の出力長は誕生日攻撃が事実上不可能な程度にまで十分長くなければならない。つまり、通常の総当り攻撃を防ぐのに必要なビット数の2倍を必要とする。 ポラード・ロー素因数分解法の離散対数への応用（en）は、離散対数の計算に誕生日攻撃を応用した例である。
※この「デジタル署名への攻撃」の解説は、「誕生日攻撃」の解説の一部です。
「デジタル署名への攻撃」を含む「誕生日攻撃」の記事については、「誕生日攻撃」の概要を参照ください。
- デジタル署名への攻撃のページへのリンク
