M1 Cryptographie - Examen du 19 juin 2025

Exercice 1 (chiffrement affine)

On utlise l'alphabet

chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ?.-!"

Chaque caractère $m$ est représenté par son index $x$ dans cette chaine ($a=0,\ldots,!=66$), et l'index $y$ du caractère $c$ qui chiffre $m$ est donné par la formule $y=ax+b \mod 67$.

1. Écrire une classe Affine67 implémentant ce système. Chiffrez et déchiffrez le message "Tout fonctionne !" avec la clé $(a,b)=(17,45)$ (on doit obtenir gpYHB?p-mHVp--UBC). Combien y a t-il de clés possibles ?

2. La jeune Alice (élève de 3ème) a récupéré une petite application permettant de chiffrer des SMS avec ce système. Elle l'utilise pour communiquer secrètement avec son ami Bob. Ce dernier lui ayant fait remarquer que le nombre de clés était trop petit pour mettre leurs communications à l'abri de parents indiscrets, il décident de surchiffer les messages, en utilisant successivement trois clés différentes $(a_i,b_i),\ i=1,2,3$. Combien croient-ils avoir maintenant de clés, et combien y en a t-il en réalité ?

3. Se croyant en sécurité, Alice envoie à Bob le message

   'AIGg9PxbUPwPvpXPnILp49XPXb49PIUXp49XP6pPEppukp4d-PT4PsIPnbgsb?LPBI?LpPg4pP9pgBPIP9bg9P6IXXpLPw'
   

   Mais la mère de Bob, qui a récupéré le SMS, sait qu'Alice commence généralement ses messages par "Salut". Mettez vous à sa place, et déchiffrez le message.

Exercice 2 (RSA)

Vous avez trouvé un stage au service informatique du Musée des Erreurs, un gigantesque complexe qui attire des millions de visiteurs. Vous êtes chargé de coder le nouveau système de contrôle des billets. Le responsable du service, qui se trouve être un ancien du master de Gustave Eiffel, est fier de vous expliquer le système ultrasécurisé qu'il a entièrement conçu lui-même.

Le billet comporte un QR-code, dont la lecture affiche un texte comme

qrtext = 'Galerie des Gaffes - 20/06/2025 - 15:30 - 32€ - N°31415926\n\n3a40b27462cba528f9989f81db1e902fc8ab1070a323e7f3ae1f54886b63262db75b8e02ede7710a254a40010fcdd72dae02b9fd310257c2f51d7732aa41a9e0195cd1dd528082b4b0a03e3a6d49441cf23da8f22c0c123c4b4065b4defcb30f9f6a762e4c85fd684dd1ee818068fa9c9f22ad0a828c22dcc064ecb4cdfb05f41728d4fe33f3914403f16f87bb2cd1cfbd7479291b156db69f2758a46c4583b0446a8aaea1434dd183ad6a76bbca225ad845f38b6b8e50de06bc6f1800458a0612f8f97610578a0f57d88b1a9ff0e600fb423b0c42da12484d8ee1b09669c8bec4308be41468dc9646101bb99b4a17f8d123023705eecf3dc9967123170807a'

print(qrtext)

Galerie des Gaffes - 20/06/2025 - 15:30 - 32€ - N°31415926

3a40b27462cba528f9989f81db1e902fc8ab1070a323e7f3ae1f54886b63262db75b8e02ede7710a254a40010fcdd72dae02b9fd310257c2f51d7732aa41a9e0195cd1dd528082b4b0a03e3a6d49441cf23da8f22c0c123c4b4065b4defcb30f9f6a762e4c85fd684dd1ee818068fa9c9f22ad0a828c22dcc064ecb4cdfb05f41728d4fe33f3914403f16f87bb2cd1cfbd7479291b156db69f2758a46c4583b0446a8aaea1434dd183ad6a76bbca225ad845f38b6b8e50de06bc6f1800458a0612f8f97610578a0f57d88b1a9ff0e600fb423b0c42da12484d8ee1b09669c8bec4308be41468dc9646101bb99b4a17f8d123023705eecf3dc9967123170807a

Le code hexadécimal affiché deux lignes après le texte du billet est une signature RSA de 2024 bits, obtenue en chiffrant le texte clair avec la clé privée (c'est juste un entier en hexadécimal). Pour vérifier l'authenticité du billet, on déchiffre la signature avec la clé publique, et on vérifie que le résultat coincide avec l'entier qui représente le texte clair.

La vérification du billet s'effectue à l'aide d'une application pour smartphone, téléchargeable sur l'intranet de la société. Par curiosité, vous l'avez aussi téléchargée sur votre ordinateur, ce qui vous a permis d'examiner le code et d'en extraire les données ci-dessous.

On utilise la fonction de conversion

from codecs import *
def text2int(t):
    h = encode(bytes(t, encoding='utf8'),'hex')
    return int(h,16)

et la clé publique, de 2024 bits, est

n = 8079251517827751825178719172167487990111025667428871008032586356881163784716972723299300352880728365922179490230474504873529889787622730273772038096612070780157719341825249022937549437597413026699014409596016892069198054660654939050867455779283441699570651790373161799337634128960509125202908782519615445452686306349751665469017982642778968862132991016676418675568934867548858862169092677644759236399088461497177157205485827201944351354162952729247799473193040935165356750875792911454872137350672912273014529263108503319075947890454587827591184337704363232858356642474389405435853443641853472505625035172647093293231
e = 65537

1. Écrire une fonction verify(qrtext) qui effectue ce calcul, et vérifiez l'authentiticé du billet ci-dessus.

def verify(qr):
    # votre code ici
    pass

verify(qrtext)

True

2. Décidément trop bavard, le responsable vous explique que, puisque pour factoriser un entier par force brute, il faut essayer de le diviser par tous les nombres impairs inférieurs à sa racine carrée, il a habilement choisi pour sa clé deux nombres premiers assez proches de $\sqrt{n}$, afin de maximiser le nombre d'essais nécessaires. Que pensez-vous de ce raisonnement ?

3. Si vous avez correctement répondu à la question précédente, trouvez la factorisation $n=pq$. Vous pourrez calculer la partie entière de $\sqrt{n}$ au moyen du module  decimal déjà rencontré.

4. Calculez l'exposant privé $d$.

5. Écrivez maintenant une fonction gen_text(batiment, date, heure, prix, numero) qui construit le texte clair d'un billet.

6. Pour finir, écrivez une fonction gen_billet(batiment, date, heure, prix, numero) qui construit le billet complet avec sa signature RSA.

Forgez un faux billet pour 'Pavillon des Bugs', 14/07/2025, 10:15, 45€, N°27182818, et vérifiez sa signature.

gen_text('Pavillon des Bugs', '14/07/2025', '10:15', 45, 27182818)

'Pavillon des Bugs - 14/07/2025 - 10:15 - 45€ - N°27182818'

qrtext = gen_billet('Pavillon des Bugs', '14/07/2025', '10:15', 45, 27182818)

verify(qrtext)

True

Exercice 3

Alice et Bob utilisent le protocole de Diffie-Hellmann avec le nombre premier de 512 bits $$p = 17196201054584064334833405683175430195845756358957425604387711050583216552385626\\ 13083979651479555788009994557822024565226932906295208262756822275663694111$$

p=1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111

et le générateur $g=469$ d'un grand sous-groupe de ${\mathbb Z/p\mathbb Z}$.

1. Alice tire l'entier aléatoire $a=230607966457$, et Bob tire l'entier $b=48181818181823$. Quelles seront les données échangées, et quelle sera la clé de session $K$ ?

2. Ayant vérifié à l'aide d'un logiciel spécialisé que l'ordre de $g$ était effectivement $(p-1)/2$, Alice et Bob n'ont pas pris la précaution de s'assurer que $p$ était un nombre premier sûr. Montrez que ce n'est effectivement pas le cas (mais alors, pas du tout !).

3. Malheureusement pour eux, Eve a intercepté la clé de session que vous avez calculée en 1. Elle a factorisé $n=p-1$, ce que vous allez faire aussi, et elle peut alors appliquer la recette suivante (cours 5):

Pour calculer le logarithme discret $x$ de $h=g^x$ dans un groupe cyclique d'ordre $n$ et de générateur $g$, si $$n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$ n'a que de petits facteurs premiers $p_i$, on calcule les éléments

• $g_i = g^{n/{p_i^{e_i}}}$, qui est donc d'ordre $p_i^{e_i}$ par le théorème de Lagrange
• $h_i = h^{n/{p_i^{e_i}}}$, qui appartient au sous-groupe cyclique $\langle g_i\rangle$ engendré par $g_i$
• $x_i = \log_{g_i} h_i$, problème plus facile qu'on peut résoudre par diverses méthodes

On a $x\equiv x_i \mod p_i^{e_i}$, et on reconstitue $x$ par le théorème des restes chinois.

Vous pouvez utiliser les fonctions écrites en TD et celles d'ent3.py. Faites le calcul de votre côté, et vérifiez qu'on retrouve bien le logarithme de $K$ en base $g$ par cette méthode. Ici, les $p_i$ sont petits, on calculera les $x_i$ par force brute.