Cryptanalyse Mod n
# Cryptanalyse Mod n

En cryptologie, la cryptanalyse mod n est une attaque applicable aux chiffrements par bloc et aux chiffrements par flot. C'est une forme de cryptanalyse partitionnelle utilisant l'arithmétique modulaire. Elle exploite le fait que le comportement opératoire de l'algorithme est inégal sur l'anneau Z/nZ formé par les classes d'équivalence (classes de congruence) modulo n. La méthode fut suggérée en premier en 1999 par John Kelsey, Bruce Schneier et David Wagner et appliquée sur RC5P (une variante de RC5) et M6 (une famille de code en bloc utilisée dans le standard FireWire).

## Analyse mod 3 de RC5P

Pour RC5P, l'analyse fut conduite modulo 3. Il fut observé que les opérations dans le chiffrement (rotation et addition, les deux sur des mots 32 bits) étaient quelque peu biaisées sur les classes de congruence mod 3. Pour illustrer cette approche, considérons la rotation gauche par un seul bit :

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

Alors, parce que

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

Nous pouvons déduire que

$X<<<1\equiv 2X{\pmod {3}}$.

Ainsi, la rotation gauche par un seul bit possède une description simple modulo 3. L'analyse pour d'autres opérations (rotation dépendante des données et addition modulaire) révèle des biais statistiques notables. Bien qu'il existe certains problèmes théoriques d'analyse d'opérations en combinatoire, le biais peut être détecté expérimentalement si le chiffrement est considéré dans son ensemble. Dans l'article de Kelsey (1999), les expériences furent conduites sur sept passages. Se basant sur ceci, les cryptanalystes conjecturèrent que dix-neuf ou vingt passages de RC5P peuvent être distingués d'un flux aléatoire. Il existe aussi une méthode correspondante pour retrouver la clé secrète.

