Olympiades · Épreuve nationale · 11 mars 2020
Chiffre de César (décalage fixe de l'alphabet).
1. Coder « OLYMPIADES » avec la clé 3.
2. Décoder « JWWNN MNB VJCQNVJCRZDNB » (clé 9).
3. Décoder un texte signé Alan Turing (clé à deviner).
Cryptage affine. On remplace la lettre de rang \(x\) (A=0, ..., Z=25) par le reste de \((ax+b)\) modulo 26.
4. Avec \((a,b)=(22,4)\), détailler le calcul pour la lettre B.
5. Coder D et Q avec cette clé ; quel problème pratique apparaît ?
6. Avec \((a,b)=(9,4)\) :
a) compléter le tableau de codage de l'alphabet ;
b) ce choix résout-il le problème de la question 5 ?
7. Décoder un texte codé avec \((a,b)=(9,4)\).
8. Proposer un algorithme de décodage.
9. Principal défaut de ces deux systèmes ?
Chiffrement de Vigenère (clé variable selon un mot-clé, ici VIGENERE).
10. Décoder une date de naissance codée avec cette clé.
11. Compléter une frise avec les trois mathématiciens évoqués et leur date de naissance.
1-2. Décaler chaque lettre de la clé donnée dans l'alphabet (en revenant à A après Z). Pour décoder, décaler dans le sens opposé.
5. Le problème pratique du cryptage affine \(x\mapsto ax+b \pmod{26}\) apparaît quand \(a\) n'est pas premier avec 26 (\(26=2\times13\)) : plusieurs lettres différentes peuvent alors se retrouver codées par la même valeur, rendant le décodage ambigu. Vérifier si \(a=22\) (pair) pose ce problème.
8. Le décodage consiste à résoudre \(y=ax+b\pmod{26}\) en \(x\), ce qui nécessite l'inverse de \(a\) modulo 26 (existe si et seulement si \(a\) est premier avec 26).
10-11. Pour Vigenère, décaler chaque lettre du texte codé par la lettre correspondante du mot-clé répété cycliquement (soustraction modulo 26, en associant A=0 à Z=25 pour les lettres du mot-clé aussi).
1. OLYMPIADES → ROBPSLDGHV (décalage +3).
2. JWWNN MNB VJCQNVJCRZDNB (décalage −9) → ANNEE DES MATHEMATIQUES.
4. \(B\) a pour rang \(x=1\) : code \(=(22\times1+4)\bmod26=26\bmod26=0\), soit la lettre A.
5. \(D\) (rang 3) et \(Q\) (rang 16) donnent tous deux \((22x+4)\bmod26=18\) : D et Q sont codés par la même lettre (S), rendant le décodage impossible à cette position. Cela vient de \(\text{pgcd}(22,26)=2\ne1\) : seuls \(13\) codes distincts sur 26 sont atteints (chacun par exactement 2 lettres).
6a-b. Avec \((a,b)=(9,4)\) : \(\text{pgcd}(9,26)=1\), donc \(x\mapsto9x+4\) est une bijection de \(\{0,\ldots,25\}\) — chaque lettre a un code unique, le problème de la question 5 est résolu.
8. Décoder revient à résoudre \(y=9x+4\pmod{26}\) en \(x\), soit \(x=9^{-1}(y-4)\pmod{26}\) ; comme \(9\times3=27\equiv1\pmod{26}\), l'inverse de 9 est 3, d'où \(x=3(y-4)\bmod26\).
9. Défaut principal : ce sont des chiffrements monoalphabétiques (chaque lettre est toujours codée de la même façon), donc vulnérables à l'analyse des fréquences des lettres.