Cryptanalyse du module n

En cryptographie , la cryptanalyse modulo . La méthode a été proposée pour la première fois en 1999 par John Kelsey , Bruce Schneier et David Wagner , et appliquée à RC5P (une variante de RC5 ) et à M6 (une famille de chiffrements par blocs utilisés dans la norme FireWire ). Ces attaques exploitent les propriétés de l'addition binaire et de la rotation de bits modulo un nombre premier de Fermat . ${\displaystyle X\lll 1=\left\{{\begin{matrix}2X,&{\mbox{si }}X<2^{31}\\2X+1-2^{32},&{\mbox{si }}X\geq 2^{31}\end{matrix}} ight. </span referrerpolicy=$

Ensuite, parce que

${\displaystyle 2^{32}\equiv 1{\pmod {3}},\, <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mn>32</mn></mrow></msup><mo>≡</mo><mn>1</mn><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>3</mn><mo>)</mo></mrow><mo>,</mo><mspace></mspace></mstyle></mrow><annotation>{\displaystyle 2^{32}\equiv 1{\pmod {3}},\,}</annotation></semantics></math></span><img src=$

Il s'ensuit que

${\displaystyle X\lll 1\equiv 2X{\pmod {3}}. <semantics><mrow><mstyle><mi>X</mi><mo>⋘</mo><mn>1</mn><mo>≡</mo><mn>2</mn><mi>X</mi><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>3</mn><mo>)</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle X\lll 1\equiv 2X{\pmod {3}}.}</annotation></semantics></math></span><img src=$

Ainsi, une rotation à gauche d'un seul bit se décrit simplement modulo 3. L'analyse d'autres opérations (rotation dépendante des données et addition modulaire) révèle des biais similaires et notables. Bien que l'analyse combinée de ces opérations pose certains problèmes théoriques, le biais peut être détecté expérimentalement pour l'ensemble du chiffrement. Dans (Kelsey et al., 1999), des expériences ont été menées jusqu'à sept tours, et les auteurs conjecturent que jusqu'à 19 ou 20 tours de RC5P peuvent être distingués d'un chiffrement aléatoire grâce à cette attaque. Il existe également une méthode correspondante pour retrouver la clé secrète .

Contre M6, il existe des attaques mod 5 et mod 257 qui sont encore plus efficaces.

John Kelsey , Bruce Schneier et David Wagner (mars 1999). Cryptanalyse Mod n, avec applications contre RC5P et M6 ( PDF / PostScript ) . Actes du sixième atelier international sur le chiffrement logiciel rapide . Rome : Springer-Verlag , p. 139-155 le .{{cite conference}}: CS1 maint : noms multiples : liste des auteurs ( lien )
Vincent Rijmen (01/12/2003). "« Cryptanalyse de Rabbit » (PDF) . Livre blanc , version 1.0. Cryptico .{{cite journal}}: La citation de la revue nécessite |journal=( aide )
Toshio Tokita ; Tsutomu Matsumoto. « Sur l'applicabilité de la cryptanalyse différentielle, de la cryptanalyse linéaire et de la cryptanalyse modulo n à un algorithme de chiffrement M8 (ISO9979-20) ». Ipsj Journal . 42 (8).