Mod n暗号解読

暗号学において、mod n暗号解読はブロック暗号とストリーム暗号に適用可能な攻撃です。これは、nを法とする同値類（合同類）上での暗号の動作の不均一性を利用する分割暗号解読の一種です。この方法は、1999 年にJohn Kelsey、Bruce Schneier、およびDavid Wagnerによって初めて提案され、RC5P（ RC5の変種）とM6 （ FireWire規格で使用されるブロック暗号のファミリー）に適用されました。これらの攻撃は、フェルマー素数を法とするバイナリ加算とビット回転の特性を利用しました。

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 et al., 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: 複数の名前: 著者リスト (リンク)
• ヴィンセント・ライメン(2003-12-01)。」「mod n」Rabbitの暗号解読（PDF）。ホワイトペーパー、バージョン1.0。Cryptico 。2007年2月12日取得。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）
• 時田俊夫、松本勉。「暗号アルゴリズムM8（ISO9979-20）に対する差分暗号解読、線形暗号解読、およびMod n暗号解読の適用性について」。IPSJジャーナル。42 （ 8）。