Cryptographie : exercices corrigés de Terminale Maths expertes

Traduire BAC en entiers : $B=1$, $A=0$, $C=2$.

Ajouter 11 à chacun : $12$, $11$, $13$. Aucune somme ne dépasse 25, donc il n'y a pas de réduction.

Revenir aux lettres : $12=M$, $11=L$, $13=N$. Le mot chiffré est MLN.

Pour S : $S=18$ et $18+11=29$. Or $29=1\times 26+3$, donc $29\equiv 3 \pmod{26}$.

L'entier cherché est $3$, qui correspond à la lettre D.

Remplacer $x$ par 12 : $5\times 12+8=68$.

Division euclidienne : $68=2\times 26+16$.

Donc $y\equiv 16 \pmod{26}$ avec $0\le 16\le 25$.

L'entier 16 correspond à la lettre Q ($A=0$, …, $P=15$, $Q=16$).

Question 1 : $5\times 21=105=4\times 26+1$, donc $5\times 21\equiv 1 \pmod{26}$.

Question 2 : de $y\equiv 5x+8$, on tire $y-8\equiv 5x$. On multiplie par 21 : $21(y-8)\equiv 21\times 5\,x \equiv x \pmod{26}$, d'après la question 1.

Question 3 : $x\equiv 21\times(3-8)=21\times(-5)=-105 \pmod{26}$.

$-105+5\times 26=-105+130=25$, donc $x\equiv 25$.

Vérification : $5\times 25+8=133=5\times 26+3$, donc on retrouve bien $y=3$.

Question 1 : avec $a=13$, $13x\equiv 0$ si $x$ est pair et $13x\equiv 13$ si $x$ est impair (mod 26). Par exemple, $x=0$ et $x=2$ donnent la même lettre chiffrée pour tout $b$ : le message n'est pas retrouvable.

Question 2 : déchiffrer demande de résoudre $ax\equiv y-b \pmod{26}$ avec une solution unique. Cela revient à ce que $a$ ait un inverse modulo 26, c'est-à-dire, d'après Bézout, $\text{PGCD}(a,26)=1$.

Question 3 : $a$ doit n'être divisible ni par 2 ni par 13. Il y a 13 entiers impairs entre 1 et 25 ; on retire 13 lui-même : il reste $12$ valeurs.

Les valeurs sont $1,3,5,7,9,11,15,17,19,21,23,25$.

Question 1 : 103 est premier et ne divise pas 7. Le petit théorème de Fermat donne $7^{103-1}\equiv 1 \pmod{103}$, soit $7^{102}\equiv 1$.

Question 2 : $7^{105}=7^{102}\times 7^3\equiv 1\times 7^3 \pmod{103}$.

$7^3=343$ et $343=3\times 103+34$ car $3\times 103=309$.

Donc $7^{105}\equiv 34 \pmod{103}$, et le reste est $34$.

Question 1 : $n=5\times 11=55$ et $\varphi(n)=4\times 10=40$.

Question 2 : $40=3\times 13+1$, donc $\text{PGCD}(3,40)=1$.

Question 3 : on cherche $3d\equiv 1 \pmod{40}$. Les nombres $41, 81, 121,\dots$ sont les candidats ; le premier multiple de 3 est $81=3\times 27$. Donc $d=27$.

Vérification : $3\times 27=81=2\times 40+1$.

Question 4 : $8^3=512=9\times 55+17$ car $9\times 55=495$. Donc $c=17$.

Contrôle du déchiffrement : $17^{27}\equiv 8 \pmod{55}$ (on peut le vérifier modulo 5 et modulo 11 séparément).

Question 1 : $\varphi(143)=10\times 12=120$. Comme $120=7\times 17+1$, $\text{PGCD}(7,120)=1$ : l'exposant convient.

Question 2 : $7\times 103=721=6\times 120+1$, donc $7\times 103\equiv 1 \pmod{120}$.

Question 3 : $9^2=81$ ; $9^3=729=5\times 143+14$, donc $9^3\equiv 14$ ; $9^4\equiv 14\times 9=126$ ; $9^5\equiv 126\times 9=1134=7\times 143+133$, donc $133$ ; $9^6\equiv 133\times 9=1197=8\times 143+53$, donc $53$ ; $9^7\equiv 53\times 9=477=3\times 143+48$, donc $48$.

Question 4 : modulo 11, $9^2\equiv 4$, $9^4\equiv 16\equiv 5$, $9^6\equiv 20\equiv 9$, $9^7\equiv 81\equiv 4$ ; et $48=4\times 11+4$. Modulo 13, $9^3=729\equiv 1$, donc $9^7\equiv 9$ ; et $48=3\times 13+9$. Les deux contrôles concordent.

Question 1 : 187 n'est divisible ni par 2, 3, 5, 7 ; $187=11\times 17$. Les deux facteurs sont premiers.

Question 2 : $\varphi(187)=(11-1)(17-1)=10\times 16=160$.

Question 3 : on cherche $7d\equiv 1 \pmod{160}$. Essayons $160k+1$ : $161=7\times 23$. Donc $d=23$.

Vérification : $7\times 23=161=160+1$.

Question 4 : l'attaque repose sur la factorisation de $n$. Pour 187, quelques divisions suffisent ; pour un très grand $n$, le nombre de tests à effectuer devient démesuré, et c'est cette difficulté qui protège la clé privée.