Mod n 暗号解読

暗号学において、mod n暗号解読は、ブロック暗号とストリーム暗号に適用できる攻撃です。これは、nを法とする同値類(合同類)に対する暗号の動作の不均一性を利用する分割暗号解読の一形態です。この方法は、1999 年にJohn Kelsey、Bruce Schneier、David Wagnerによって初めて提案され、RC5P ( RC5の派生型) とM6 ( FireWire標準で使用されるブロック暗号のファミリ) に適用されました。これらの攻撃では、フェルマー素数を法とする 2 進加算とビット回転の特性が使用されました。

RC5P の場合、分析は 3 を法として実施されました。暗号内の操作 (回転と加算、どちらも 32 ビット ワード) は、3 を法として合同クラスに多少偏っていることが確認されました。このアプローチを説明するために、1 ビットの左回転を考えてみましょう。

${\displaystyle X\lll 1=\left\{{\begin{matrix}2X,&{\mbox{if }}X<2^{31}\\2X+1-2^{32},&{\mbox{if }}X\geq 2^{31}\end{matrix}}\right.}$

それで、

${\displaystyle 2^{32}\equiv 1{\pmod {3}},\,}$

すると

${\displaystyle X\lll 1\equiv 2X{\pmod {3}}.}$

このように、1 ビットの左回転は 3 を法として簡単に記述できます。他の操作 (データ依存回転とモジュラー加算) を分析すると、同様の顕著な偏りが明らかになります。操作を組み合わせて分析すると理論的な問題がいくつかありますが、偏りは暗号全体に対して実験的に検出できます。(Kelsey 他、1999) では、最大 7 ラウンドの実験が行われ、これに基づいて、この攻撃を使用して RC5P の 19 または 20 ラウンドをランダムと区別できると推測されています。秘密鍵を復元するための対応する方法もあります。

M6 に対しては、さらに効果的な攻撃 mod 5 と mod 257 があります。

• John Kelsey、Bruce Schneier、David Wagner (1999 年 3 月)。Mod n 暗号解析、RC5P および M6 に対するアプリケーション( PDF / PostScript )。高速ソフトウェア暗号化、第 6 回国際ワークショップ議事録。ローマ: Springer-Verlag。pp . 139–155。2007年 2 月 12 日閲覧。{{cite conference}}: CS1 maint: 複数の名前: 著者リスト (リンク)
• Vincent Rijmen ( 2003-12-01 )。「Rabbit の mod n 暗号解析」(PDF)。ホワイト ペーパー、バージョン1.0。Cryptico。2007-02-12取得。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• 時田俊夫、松本勉「差分暗号解析法、線形暗号解析法およびMod n暗号解析法の暗号アルゴリズムM8（ISO9979-20）への適用性について」、IPSJジャーナル、42（8）。