Depuis le code de César, les méthodes cryptographiques permettant de transmettre des messages secrets ont évoluées en suivant les progrès permettant de les casser. La méthode Vigenère qui est une amélioration du code de César sera étudiée, et nous verrons comment il est possible de casser cette méthode de chiffrement. Ensuite, la méthode de chiffrement RSA qui est une des méthodes de cryptographie asymétrique les plus utilisées actuellement sera introduite.
Le code de Vigenère consiste à choisir une clef formée par un mot secret (en majuscules) et à le transformer en un vecteur dont les éléments sont les positions de ces lettres dans l'alphabet. Par exemple, «ASECRET» correspond à (0, 18, 4, 2, 17, 4, 19). Pour coder un texte (en majuscules, sans espace ni ponctuation) avec la clef «ASECRET» il suffit de décaler la première lettre par 0, la deuxième par 18, la troisième par 4, et ainsi de suite et de recommencer en boucle. Les détails en particulier historiques sont disponibles sur Wikipédia.
a) Écrire une fonction to_int(s) qui transforme un caractère en sa place dans l'alphabet et écrire la fonction inverse to_chr(i).
Voir la documentation des fonctions ord et chr.
b) Écrire une fonction crypt(text, key) qui chiffre text avec le mot secret key.
c) Écrire une fonction permettant de déchiffrer un texte en connaissant la clef.
Charles Babbage a été le premier à casser le code de Vigenère. L'idée est que trois lettres consécutives apparaissant plusieurs fois dans le texte chiffré ont toutes les chances d'être la conséquence du chiffrement des mêmes lettres du message avec les mêmes lettres de la clef. Cela est encore plus probable avec un groupe de quatre lettres. Ainsi l'espacement entre deux mêmes groupes de lettres chiffrées est un multiple de la longueur de la clef. Par exemple, si la répétition d'un groupe est espacée de 28 lettres, puis celle d'un autre de 91, le plus grand diviseur commun de 28 et 91 est 7. Ainsi il est probable que la clef possède 7 lettres. Ensuite connaissant la taille de la clef, il suffit de se baser sur le fait que la lettre «E» est la plus courante en français. Pour que cette stratégie ait une chance de réussir, il faut que la taille du texte soit assez importante.
a) Écrire une fonction permettant de calculer le plus grand diviseur commun (PGCD) entre deux nombre. Écrire une autre fonction permettant de calculer le PGCD entre une liste de nombres.
b) Visiter le site du projet Gutenberg, choisir son texte français préféré et le télécharger au format «Plain Text». Écrire une fonction qui convertisse le texte en majuscules et le débarrasse de toute la ponctuation et autres caractères spéciaux.
Pour convertir un texte en majuscules (en convertissant les accents) et supprimer tous les caractères de ponctuation et autres, il est possible d'utiliser la fonction suivante:
import unicodedata, re
def convert_upper(text):
# convertir en majuscules
text = text.upper()
# convertir les accents
text = unicodedata.normalize('NFKD', text)
# supprimer les caractères spéciaux
regex = re.compile('[^a-zA-Z]')
text = regex.sub('', text)
return text
c) Garder environ un milier de caractères au milieu du texte choisi et le chiffrer avec une clef. Écrire ensuite une fonction permettant de déterminer la longueur de la clef en regardant dans le message chiffré les chaînes identiques de trois caractères ou plus.
Former tout d'abord un dictionnaire avec comme clef toutes les occurrences de trois lettres et comme valeur les positions des occurrences. Ensuite déterminer la liste des distances entre les occurrences de trois lettres, puis calculer le PGCD de ces distances. Si ce PGCD est égal à 1 ou est trop petit, alors réessayer mais avec des chaînes de plus que trois caractères.
d) Écrire une fonction permettant de décrypter un message chiffré en retournant la clef. Essayer de décrypter le texte de son auteur favori avec cette fonction.
Pour trouver la première lettre de la clef, il faut calculer le nombre d'occurrences des 26 lettres de l'alphabet dans le message chiffré qui ont été chiffrées avec le premier caractère de la clef. En principe, la lettre dont l'occurrence est maximale correspond à la lettre «E». Il suffit ensuite de faire la même chose pour trouver les autres lettres de la clef.
La plupart des algorithmes de cryptage actuels sont fondés sur l'utilisation de grands nombres premiers. Le but est d'écrire une fonction permettant de générer relativement rapidement des nombres dits pseudo-premiers, c'est-à-dire qui sont premiers avec une probabilité extrêmement grande. La première étape est de générer un grand nombre aléatoire, c'est-à-dire ayant un certain nombre de bits. Ensuite un test de primalité permet de décider si ce nombre est premier ou pas. Si \( \pi(n) \) désigne le nombre de nombres premiers inférieurs ou égaux à \( n \), alors asymptotiquement \( \pi(n) \approx \frac{n}{\ln n} \). Pour un nombre inférieur à \( n \) tiré au hasard la probabilité qu'il soit premier est d'environ \( 1/\ln(n) \). Par exemple pour générer un nombre premier de 1 024 bits (le minimum garantissant une sécurité raisonnable actuellement), c'est-à-dire de l'ordre de \( 2^{1024} \), il faut essayer \( \ln(2^{1024}) \approx 710 \) nombres aléatoires avant d'en trouver un qui soit premier. Vu que tous les nombres pairs ne sont clairement pas premiers, il suffit d'en tester en moyenne \( 355 \).
a) Écrire un programme permettant de générer un nombre aléatoire impair de \( k \) bits, c'est-à-dire compris entre \( 2^{k-1} \) et \( 2^{k} \).
La façon la plus rapide d'implémenter cela est d'utiliser les opérations sur les bits expliquées ici.
La façon la plus simple de déterminer si un nombre \( n \) est premier est d'essayer de le diviser par tous les nombres entiers \( 1 < d < n \). Il y a deux raisons qui permettent de ne pas tester tous les \( d \) entre 2 et \( n-1 \). La première est qu'il est inutile d'essayer les \( d \) pairs plus grands que 2. La seconde est qu'il est inutile de tester des nombres plus grands que \( \sqrt{n} \).
b) Écrire un algorithme isprime(n) permettant de déterminer si un nombre est premier ou pas.
c) Écrire une fonction generate(k,primality) permettant de générer un nombre premier aléatoire de k bits avec le test de primalité primality. Tester avec le test de primalité isprime. Est-il raisonnable de pouvoir espérer générer un nombre premier de 1 024 bits avec cet algorithme ?
L'algorithme précédent permettant de générer des nombres premiers étant inutilisable pour générer des grands nombres premiers, une autre approche, probabiliste, est à préconiser. Un test de primalité probabiliste décide qu'un nombre est premier s'il est premier avec une probabilité très grande. Un tel nombre est dit pseudo-premier. Ainsi un test probabiliste peut se tromper et supposer qu'un nombre est premier alors qu'en fait il ne l'est pas.
Le test de primalité le plus simple est fondé sur le petit théorème de Fermat: si \( n \) est premier, alors \( a^{n-1}=1 \pmod n \) pour tout \( 1 \leq a \leq n-1 \). Ainsi si on trouve un \( a \) tel que \( a^{n-1}\neq1 \pmod n \), alors \( n \) n'est pas premier. Le test de primalité de Fermat teste \( N \) valeurs de \( a \) choisies aléatoirement et si \( a^{n-1}=1 \pmod n \) pour ces \( N \) valeurs, alors il déclare que \( n \) est probablement premier. Les nombres de Carmichael ne sont pas premiers, mais satisfont \( a^{n-1}=1 \pmod n \) pour tout \( a \) premier avec \( n \). Les premiers nombres de Carmichael sont 561, 1 105 et 1 729. Si \( n \) n'est pas un nombre de Carmichael, alors la probabilité que le test de Fermat se trompe est de \( 2^{-N} \). En choisissant par exemple \( N=128 \), on obtient une probabilité de se tromper inférieure à \( 3\times 10^{-39} \).
a) Écrire une fonction implémentant le test de primalité de Fermat. Utiliser ce test pour générer des nombres premiers aléatoires.
Voir la documentation de la fonction pow pour une implémentation rapide. Si OpenSSL est installé sur votre ordinateur, il est facile de vérifier si un nombre est premier avec la commande openssl prime 11 par exemple pour 11.
b) ! Améliorer la rapidité de l'algorithme précédent en testant d'abord si \( n \) est divisible par les nombres premiers inférieurs à 1 000 avant d'appliquer le test de Fermat.
Le test de primalité de Fermat permet de générer de grands nombres pseudo-premiers avec une bonne probabilité de tomber juste. Le problème principal vient du fait de l'existence des nombres de Carmichael qui sont exclus de cette probabilité. Le test de primalité de Miller-Rabin permet d'éviter ce problème.
c) !! Comprendre et implémenter la méthode Miller-Rabin expliquée en détails sur Wikipédia.
L'algorithme RSA, des initiales de Ronald Rivest, Adi Shamir et Leonard Adleman qui l'ont inventé en 1983, est un des algorithmes de cryptographie asymétrique les plus utilisés encore actuellement. Un chiffrement asymétrique permet de transmettre un message crypté à une personne A sans avoir eu auparavant besoin de transmettre une clef secrète à la personne B qui chiffre le message. La création par A d'une clef publique suffit à B pour chiffrer le message et pour que A puisse le déchiffrer avec sa clef privée. Il y a trois grandes étapes dans l'algorithme RSA:
Création des clefs. La personne A voulant recevoir un message secret choisit deux très grands nombres premiers \( p \) et \( q \) qu'elle garde secrets. Elle calcule ensuite \( n=pq \) et l'indicatrice d'Euler \( \varphi(n)=(p-1)(q-1) \) qui compte le nombre d'entiers compris entre 1 et \( n \) qui sont premiers avec \( n \). Puis elle choisit un exposant de chiffrement \( e \) qui est premier avec \( \varphi(n) \). La clef publique de la personne A est donnée par le couple \( (n,e) \). Finalement, la personne A calcule l'exposant de déchiffrement \( d \) qui est l'inverse de \( e \) modulo \( \varphi(n) \), i.e. tel que \( ed = 1 \pmod{\varphi(n)} \). La clef privée de A est \( (p,q,d) \).
Chiffrement du message. Pour chiffrer son message, la personne B le transforme tout d'abord en un nombre entier \( M < n \). Le message chiffré est alors donné par: $$ C = M^e \pmod n \,. $$
Déchiffrement du message. Le message chiffré \( C \) est alors transmis à A. Pour le déchiffrer, A calcule: $$ M = C^d \pmod n \, $$ qui est à nouveau le message original.
random le sont avec l'algorithme de Mersenne Twister. Cet algorithme n'est pas considéré comme cryptographiquement sûr dans le sens où une observation d'environ un millier de nombres générés aléatoirement par cet algorithme suffit à prédire toutes les itérations futures. Pour générer des nombres aléatoires cryptographiquement sûrs il faudrait utiliser le module secrets.a) Montrer mathématiquement que le message déchiffré correspond bien au message original.
Si \( a = b \pmod{\varphi(n)} \) et \( M \) est premier avec \( n \), alors \( M^a = M^b \pmod n \).
b) À partir de \( e \) et \( \varphi(n) \) donnés, écrire une fonction bezout(e, phi) permettant de déterminer \( d \) tel que \( ed = 1 \pmod{\varphi(n)} \).
Utiliser l'algorithme d'Euclide généralisé qui permet de déterminer le PGCD \( g \) entre deux nombres \( a \) et \( b \) ainsi que \( x \) et \( y \) satisfaisant \( ax+by=g \).
c) Écrire un algorithme generate_keys(length) qui génère des nombres premiers \( p \) et \( q \) tels que \( n \) ait length bits, puis détermine \( \varphi(n) \), \( e \) et \( d \) et enfin retourne la clef publique \( (n,e) \) et la clef privée \( (p,q,d) \).
d) En choisissant d'encoder chaque caractère sur 8 bits, une chaîne de caractères de longueur \( \ell \) s'écrit comme une liste \( (a_0,a_1,\dots a_\ell) \) avec chaque \( 0 \leq a_i \leq 255 \). Cette liste peut être convertie en un entier \( k \) de la façon suivante: $$ k = \sum_{i=0}^\ell a_i 256^i $$ Écrire une fonction toint et une fonction tostr permettant respectivement de convertir une chaîne de caractères en cet entier et inversement.
e) Écrire une fonction pour chiffrer un texte avec une clef publique et une autre permettant de le déchiffrer avec la clef privée. Pour cela il faut s'assurer que le texte soit convertible en un entier inférieur à \( n \), sinon il faut le découper en blocs et les chiffrer séparément.
Voici une clef publique:
(73722206893746878039310298412768333517547506486427363913406174815240823284857,
33921003048397584579835360477549223828723590186917811609938274008840181968499)
et un message chiffré avec cette clef publique:
[22973877239788873882837788687834740958145091979501565167824992597825600406974,
48503379361942356829127901273483580639426474600801539865525830360302350602689,
2224798454942012298637628855810886175704245737423608868190613249161861526055,
4500720701216145302036625979462397411127541711596515042635302843142748047486,
35445000935671280429079877747553363121645781096430386417428307485228904386825,
48627712259501563035806415688912560481020577805784144969245386699539463833735,
71868389092768589092947834441169271512227882469129366706758279960751502739157,
26019603019482382085505727901092092122241438959147654068117475447783602572984,
65039729472521706954510624828984329309712256390395416184704490683377874857302,
11805320141319662342135552217286927868466795280631816945032387836622798495117]
a) Décrypter le message précédent !
Il est probablement nécessaire de choisir un algorithme adapté, par exemple utilisant des cribles quadratiques (QS, MPQS, SIQS).