M1 Cryptographie - TD6 2025 : un sujet d'examen¶

Exercice 1 - RSA¶

1) Alice veut envoyer à Bob une clé AES $k$ de 256 bits. Pour cela, elle utilise la clé publique RSA de Bob $(n,e)$, où l'exposant public $e=3$ et $n=pq$ est un entier de 1024 bits. Elle interprète $k$ comme un entier $m<2^{256}$ et envoie à Bob $c=m^e\mod n$. Que fait Bob pour déchiffrer le message ?

2) Eve a intercepté $c$, et elle sait qu'il chiffre une clé de 256 bits. Comment peut-elle déchiffrer le message sans connaître la clé secrète de Bob ?

3) Application numérique. On donne $p,q,n=pq, e=3$ ci dessous. Calculer $\varphi(n)$ et l'exposant secret $d$.

In [1]:
p = 6703903964971298549832439919371398494399015648289196972258883306903839393804366625849727104590539084052902869762853248274424599006364921094067135151341857
q = 6703903964971298549787012499102923063739759867339549021828992204361077608032486534766699776908975050355571096518577980916352359894752357074082207354585851
n = p*q
e = 3
p,q,n,e
Out[1]:
(6703903964971298549832439919371398494399015648289196972258883306903839393804366625849727104590539084052902869762853248274424599006364921094067135151341857,
 6703903964971298549787012499102923063739759867339549021828992204361077608032486534766699776908975050355571096518577980916352359894752357074082207354585851,
 44942328371557897693537170832581868311710983585806826126164546831514171458051454070584191780779095857043039092372484309469284320580843807657241062017943630695833916879757124993169042047914449020611288981714263675299032886538642927645525128131944922915297478949081020831028946326349204373278946808965156265307,
 3)

4) Alice a envoyé à Bob la valeur $c$ suivante

0xa2f94378b16e47963dbd3dd29f88f66239dea4d05c6f846753777046ed8861bfec9dfd8f50ed9638e6d29b6b5ae9f06e51a1ddf40f8cc2f701e5e6431dc96e3ec38f05958174fe15eebba6bdf23b9acd946be0c61186eb756eed3cd02548000

Appliquer la méthode proposée en 2) pour retrouver $k$. Indications Le module decimal contient les fonctions nécessaires pour faire le calcul, cf. TD 5. La clé représente une phrase en ascii.

5) Proposer une meilleure méthode pour transmettre $k$ à Bob.

Exercice 2 - Vigenère sur des octets¶

1) Écrire une fonction rxor(a,k) qui effecture le ou exclusif d'un objet de type bytes avec une clé $k$ de $m$ octets répétée périodiquement. Par exemple

>>> rxor(b'\x00\x20'*30, b'abracadabra')
b'aBrAcAdAbRaAbRaCaDaBrAaBrAcAdAbRaAbRaCaDaBrAaBrAcAdAbRaAbRaC'

2) Écrire une fonction ic(w) qui calcule l'indice de coincidence d'une chaîne de caractères ou d'octets $w$. On rappelle que $i_c(w)=\sum_x\frac{n_x(n_x-1)}{n(n-1)}$ est la probabilité pour que deux caractères de $w$ pris au hasard à des positions différentes soient identiques.

3) Testez la (plusieurs fois) sur 1024 octets aléatoires lus dans le pseudo-périphérique /dev/urandom. Quelles valeurs obtenez vous ? Quelle est sa valeur théorique sur une longue suite d'octets aléatoires ?

4) Le cryptogramme suivant (encodé en base64) a été chiffré par un Vigenère sur les octets. Décodez le base 64, et utilisez l'indice de coincidence pour déterminer la longueur probable de la clé.

b'Ay4gIWkzJD8iOic7KiojMnlyiuNlIaPVyywtMSI0J3ItJjZtAzQnMW4hKGwFICY1ICMiMH5pLyBt\nMTQrOmMnLDQmISwtJm0ulutpJyBtNTonPWMxKCwlIWkwIG0yOjw9YzY4IjaR4CeG5GE5NzpjNSKC\n/SYsMGUiIjY7PSIrPm91FydjNDiC/yYsYyGvwcwnJ2MoLDJ5cj0sKC+C9yZkKiltJDtyOzYsIyR5\ncjg2LG0iOjw/gOsjNXWR6WMrIjJ1ICwwNiI0JzEsMGU9gvwxPC0sLCgnNzpvZSMuICFpLSo4MnWR\n4DcsIi8mcigwNjgzlvtpL6fN2DQ7LSZlKaPVyzwtZSw0IT0qKzEiLzByLzEsIyY0PD1vZSg5Njcl\nLyQjNXlyOiYpIi91PiwwZSI0lv1kJyw/JHU3PWMkODUnNzpjKiNsMTs9b2UsNC1yKCUjLCgnNzpj\nIDU1JzM/IiIsLyE3Om9lOSQ5IWkvIG0lJzMgLSQqJHU2LDBlP4L8ITwxIigvNjc6YyEsLyZyJSY2\nbTs6PCwwZSwwIDsvgO0/JCZyLDdlIaPVyygwID0yPDdpJyA+YTA8PTEgPTM8ISwwZT6C/CAgICwu\nLjk3Om1lAy4gIWkgNyI4PD0nMGUoL3U+q8PcKCczNz1jJiIvIzMgLSYsLyFyLSZlPi47ciwwJz8u\nIDQsYyA5YTE3aTAqI2E3My4sMG0xOic7YykoYTYzOmMqjvh1PCY2Nm0tOicsMSwiLyZyPC1lKoL7\nJixjIDlhNj0nICk4Mzw9JzBlOC91MCgqKW0kOCIhOjGO6DomIDIwKG9fHixjNDgoMTMkYysiNCZy\nJCYrLG11NixjJiQsMCFpJittNT0zJTQgKjJ5ciM2Njw0MHItIis+YSA8aTUkIS06PCcmKCgvIX5p\nIjBtJTwzKy8gbTc0Jz8mNzltdT2K+mUjIDInius3KGE8PmkiMywoIXIqKyQ+Mpb7aYDlbTc0J2Q1\nICM1eXIsN2UiguxyKjEqJDImMyAmKzlhLDc8MCA+bXU/MDExKDJ5cio6MSQyMCFlYyA5YTE3OmMm\nJDIhNzpjJCozPCI5gOw+YTQnaTEqLmEmMSEqNjkkICplYyA5YTiR4y4gbTQ7ciQiNz8uOzwgJjdt\nJbfS0AorKSR1Mzw7ZTkpLCA6JjZtNzw9JSImjugmciY2ZSwsNCAoLTEob18HJ2MnjuMhOyQmKzlh\nMZHgIDeO6CU7aTCnzdiW+yUmMywoIXI6NjdtNDtyPSY3PyR4IiUmLCNhPz0nIC2O6HU2LGMxOCg5\nNyg2PW0zOiEsYzWO4zk3aSYxbSUwci8ihuM1PJHhMSA+YZb7KzGG5CI9keAmNmNhADwsYzMkJDw+\nJSZlLiAhMzsxLSg0JjdlYzYsLyZyKDM1LDJ1PygqNm0vOjxpMCQjMnUzKi2G5G11IiYxMSwvIXIr\nJjYkIjk3Om9lPiAnICg2ZSmC/DU7IiOO6HU3PWM2IiIkJywwZS4tOic9gOw+bXU3Jzc3KCOW8CAv\nKSxhObDJ2i04KCZyLDdlIy4gIWkqKzsoITNlYyGvwcwnJ2M2IjQnOzsmZSw0JCcsL2UgIDsjPCIs\nKC8hcj0xKiQydTYsLTE+bXWR6WM1jug7keA3NygzdTYoLTZtNDs3aTAkIS0wcj0sMDlhNDCK7SiO\n6DByKiwoIDQ7Ozg2JCM1dTYsYzUhIDw8ZDMsKCV1Mz8mJm0lMCFpIic+KDE7Ji8gPmExkeAgKj+C\n/Dc6YyGvwcw6KC8xjuknNzpjKyIoJyFlYzUoLzEnOmMpjuF1MSYuKChhMTc6YyA1bCM9PSxrRwU0\nPDpjKWouMzQgICBtIjo8PSoiOIL+fmkvJG0sND45JiwqL5b7LGMrIjQnICAwNiwoIXI8LSBtIj2R\n4TU3KGE3IIrqLSwoMjwsb2UpJCAqaSIiIyQ0JzFjKyI0IzcoNmgjgvwhaSAqOCI9keAwZT40J3It\nJjZtIzQmZCUpLC82fmk2K20rNCA6b2U4L3UkLDE3LDV1Nz1jNDgkOSM8JjZtIjQ8KDEhPmExdQAt\nIShvX1hkYwYoNSE3aS6G5DU0OzsqIGFhOz08MGUoOSU+IDIwLGwhfywvKShhMXU8LSBtNzo7MWMx\nIjQhciEmMD8kICEsb2UpICE3aScgPmGW+zksNDgkJnIkgO8gJCZyLSY2bTI2OiAwKCgydTM7KiAj\nMntyi+MPKGE5M2k3LCgvJnItJmUrJCByJCJlOTM8ISiA6ig0OTdpLyRtJTwzKiwrKDImN2WB5W0w\nIDtpMGIoL3WR4DckJDV1MzsxKiqC/HIlJjZtJSc9IDc2bSQ7cig1JCMiMHItZC0iKCc7LG1lj+Ef\nN2kuIG0yIDs6YyYiLyYmIDcwjuh1JycmZT8kISAoKjEoYSUzO2MpLGE2NzowLCIvdSEmNjZtMjA7\nJyRlPTM8JIrqZSkkdT4oYys4JHgiOyw1PyiW+z2A7HdhIDxpISQkLTk3PDFlKSR1NCYtIT5tdTMn\nICwoL3UjPCorLiA8PiUqID9hMSdpISQkLTk7KCQgYWEwIT1jISgxIDs6YzQ4JDkjPCZlOSQ4Ijpj\nKCIvdTaK6ickMzA8PSogP29ff2kCMG01MD85MGU9LiAgaS4qJG11NiA3ZSMuISAsYyIsMzE7KC1p\nbS0wIWk6IDg5dTYsMDYkLTmR4DBlPjQnfyUmaC4pND85bU9HAjo8PTEgLiAnIIrqNm0xNCBpLyBt\nMTknOmMhKGE2PSc3Nyg1MD85MGUoNXUxJi0xPy4nNjsmNm0xOiE6KichJHlyJywwPmEkJyA3MY7j\nODc6YyYoYSc3OSIsPyR1NixjJiw1PTM7JjZj\n'

5) Sachant que dans un texte assez long, en français et codé en utf8, le caractère le plus fréquent est l'espace, de code 32, retrouvez la clé et déchiffrez le message.

Exercice 3¶

On se propose d'utiliser le nombre premier $p = 10007$ et l'élément primitif $g = 10$ pour appliquer le protocole de Diffie-Hellman.

  1. Vérifier que $p$ est un nombre premier sûr et que $g$ est bien un générateur de $(\mathbb{Z}/p\mathbb{Z})^\times$.

  2. Quelles sont les étapes du protocole entre Alice et Bob si ils ont respectivement tiré les entiers aléatoires $a = 4096$ et $b = 8192$ ? Quelle sera la clef de session ?

  3. Un espion capture la valeur $y=2024$ pour $10^x\mod p$ avec $x$ inconnu. Combien existe-t-il de tels $x$ ? Pourquoi ? Combien de valeurs devez vous essayer pour trouver $x$ ? Trouvez le.

  4. Même question, mais cette fois on cherche $x$ tel que $2^x \mod p = 2024$.

On utilise maintenant les paramètres $(g, p) = (10, 10007)$ pour un système ElGamal, avec la clef privée $x = 666$.

  1. Calculer la clef publique correspondante.

  2. Chiffrer $m=1000$ avec l'entier aléatoire $k=997$. On note $c=(c_1,c_2)$ le cryptogramme obtenu.

  3. Effectuer le déchiffrement de $c$ et vérifier qu'il coincide bien avec $m$.

In [ ]: