Cryptographie à clef publique, clef privée

Alice et Bob se mettent d’accord sur une clef qui est un entier (dans 1..25). Lorsqu’Alice désire envoyer un message, elle substitue à chaque lettre la lettre décalée de la valeur de la clef.

Ainsi, si la clef est 2, les A sont remplacés par des A+2=C, les B par des C+2=E… les X par des X+2=Z, les Y par des Y+2=A, les Z par des Z+2=B.

Le chiffrement de Caesar réalisait une opération d’addition, le chiffrement affine va étendre l’idée en appliquant cette fois à chaque lettre la transformation : \(\left(x \mapsto a\times x +b\right)\%26\). Afin que la transformation soit bijective, le choix de \(a\) n’est pa uelconque, il doit être premier avec 26.

Le chiffrement par sustitution généralise la transformation, en choisissant maintenant comme clef une table complète indiquant une permutation de l’alphabet. Ainsi une clef pourrait être AZERTYUIOPQSDFGHJKLMWXCVBN indiquant que les A se transforment en A, les B en Z, les C en E…

L’idée est ici d’étendre le chiffrement affine. On choisit une taille de bloc (par exemple 3), On note \(x_1, x_2, x_3\) les trois caractère d’un bloc. A partir de ces 3 caractères on calcule trois nouveaux caracères \(y_1,y_2,y_3\) qui sont des commbinaisons linéaires des \(x_i\). Par exemple : \(y_1= 3\times x_1+7\times x_2+5\times x_3, \; y_2= x_1+9\times x_3, \; y_3 = x_1+x_2\). Le système ainsi formé doit être inversible, et le déterminant doit être premier avec le nombre de caractères de l’alphabet.

Le chiffrement autoclave consiste à utiliser une clef de taille insuffisante, et lorsque la longueur de la clef est atteinte, on utilise por le chiffrement le message en clair. Ainsi, si dispose comme clef la chaine ’ZTE’ et qu’on désire chiffree LANUITLESCHATS, on utilise comme clef de chiffement : ZTELANUITLESCHA.

Alice est en France dans le Périgord. Elle voudrait transmettre une valise de fromages et charcuteries à son ami Bob qu’elle a rencontré sur Facebook et qui habite Washington. Elle s’inquiète des malfaisants qui prélèveraient une partie des denrées, attirés par des effluves alléchantes dégagées par ces victuailles…

• Elle décide de placer un cadenas à clef sur la valise, avec écrit en lettres capitales sur la valise : « quand tu recevras cette valise, mets-y un cadenas et renvoie-la moi ! »
• Bob reçoit la valise, y ajoute un cadenas à côté de celui d’Alice, enlève le message, et renvoie la valise à Alice.
• Alice reçoit la valise, enlève le cadenas qu’elle y avait placé (c’est son cadenas, elle en a la clef !), et renvoie la valise.
• Bob reçoit la valise, enlève son cadenas (c’est le sien, il en a la clef !), et se délecte des denrées qui sont passées au nez et à la barbe de bien des facheux qui n’ont pu que se pourlécher les babines…

Formalisons le processus proposé pour la transmission d’un message \(m\) :

1. Alice calcule \(f(m)\), et le transmet à Bob
2. Bob calcule \(g(f(m))\) et le transmet à Alice
3. Alice calcule \(f^{-1}(g(f(m))) = g(m)\)
4. Bob calcule \(g^{-1}(g(m)) = m\)

Quelles sont les contraintes :

1. La fonction \(f\) doit être inversible (il doit être possible de retrouver le message original) et la fonction \(f^{-1}\) doit être difficile à découvrir.
2. Mêmes propriétés sur \(g\).
3. Il faut que \(g\) et \(f^{-1}\) commutent (il est en fait assez rare que des fonctions commutent : avancer puis tourner à droite ne nous amène pas au même point que tourner à droite puis avancer)

Prenons un exemple (message nécessitant une haute sécurité car transmettant la liste des cadeaux de Noël de votre fille de 6 ans)

• \(f\) associe à chaque lettre la lettre correspondant à son code ASCII plus 2
• \(g\) calcule l’image miroir de son argument (ABCD devient DCBA).

On vérifie les points soulevés précédemment :

• Les fonctions \(f\) et \(g\) sont inversibles et commutent : tout va bien.

Si on reçoit un message encodé par \(f\), il est possible qu’un humain ne le décode pas rapidement, mais pour ce qui est d’un ordinateur, il existe des méthodes très simples et rapides permettant de retrouver l’original, donc ce point n’est pas respecté.

• Un message encodé par \(g\) est vite décodé, même par un humain « ENUL AL CEVA SUOV-ZEDNER A LIELOS EL »

Prenons un deuxième exemple :

1. Choisir \(p\) et \(q\) des nombres premiers distincts
2. On note \(n = p \times q\)
3. On note \(\phi(n) = (p-1) \times(q-1)\)
4. Choisir un entier \(e < \phi(n)\) premier avec \(\phi(n)\)
5. En utilisant l’algorithme d’Euclide , calculer d tel que \(d \times e \equiv 1 [mod \; \phi(n)]\) [Euclide étendu : https://www.youtube.com/watch?v=bWHY9Eto2wU puis on passe le côté gauche et le côté droit modulo \(\phi(n)\)]

Chiffrement / déchiffement :

• Le message \(m\) est encodé par \(M\). Attention, il faut que \(0 \leq M < n\).
• Le message à transmettre (le chiffré) est l’entier \(C = M^{e} [mod\;n]\)
• Le déchiffrement du message \(C\) est \(M = C^{d}[mod\;n]\)

Schéma d’utilisation :

1. Alice construit (dans son coin) les 3 nombres \((e, d, n)\)
2. Elle publie sur son site Web, à la vue de tous les nombres \((e,n)\) (c’est sa clef publique) et garde secret le nombre \(d\)
3. Bob écrit à Alice en chiffrant le message avec la clef publique d’Alice
4. Alice reçoit le message et le déchiffre en utilisant sa clef privée \((d,n)\)

La fonction de chiffrement est définie par le couple \((n, e)\) et est connue de tous, la fonction de déchiffrement est définie par \((d, n)\) et n’est connue que d’Alice. Ce qui fait que l’algorithme fonctionne :

• la connaissance de \((n,e)\) et d’une multitude de couples \((M, C)\) (des messages qui ont été chiffrés dont on connaît le déchiffrement) ne nous fournit pas de méthode efficace pour savoir décoder un nouveau message.
• il y a un problème dans la méthode : il faut être capable de générer des nombres premiers grands, en un temps raisonnable, et qui ne soient pas prévisibles [à noter : il n’existe pas de distribution de probabilité uniforme sur un ensemble dénombrable, ce qui signifie dans notre cas « tirer un nombre premier au hasard de façon uniforme » n’a pas de sens, si vous êtes intéressé, vous pouvez jeter un coup d’oeil à https://www.pourlascience.fr/sd/mathematiques/les-entiers-ne-naissent-pas-egaux-7065.php]
• Il est à noter que si on n’était pas en arithmétique modulaire (avec des modulos), mais sur des réels, le problème serait trivial, grâce à la fonction log (qui n’a pas d’équivalent facilement calculable en arithmétique modulaire). Sur les réels, le chiffré (connu) serait \(C = M^e\), on passe au log : \(\log C = \log e + \log M\) comme on connaît \(e\), on peut enlever son log \(\ln C - \ln e = \ln M\) et finalement en passant à l’exponentielle \(M= e^{\ln C -\ln e}\) (mais calculer un log en arithmétique modulaire peut être difficile)

Exemple avec xcas (et des entiers tout petits) :

• Mise en place par Alice
  • on choisit p = 733, q le plus petit nombre premier supérieur à 142.
  • on vérifie qu’ils sont premiers [xcas : isprime].
  • on calcule \(n\) et \(\phi(n)\).
  • on choisit la plus petite valeur de e possible supérieure à 36 (sur xcas, on l’appelle mon_e, car e est pour \(\exp(1)\)
  • on vérifie que mon_e est premier avec \(\phi(n)\) [xcas : gcd]
  • on calcule d [xcas : iabcuv]
  • Alice communique au monde le couple \((mon\_e,n)\)
• Construction du message \(M\) par Bob
  • le message que Bob veut transmettre est m = ABC, on encode le A par 10, le B par 11, le C par 12, on met bout à bout les valeurs obtenues, ce qui donne \(M = 101112\) (remarque : la façon de passer de M à m ou de m à M n’est pas secrète)
  • on vérifie que \(M < \phi(n)\)
• Cryptage du message par Bob (qui connait \((mon\_e, n)\)
  • Bob calcule \(C = M^{mon\_e} [mod\;n]\) [xcas : irem]
  • Bob transmet à Alice le message \(C\)
• Décryptage du message de Bob par Alice
  • Alice calcule \(M = C^{d} [mod\;n]\) puis le transcrit en \(m = ABC\) et s’esbaudit devant la profondeur de la pensée de Bob !

Au fait, tout cela a l’air bien compliqué pour un petit exemple… ah oui, c’est l’algorithme de cryptographie le plus célère: RSA, dont le nom est construit à partir des initiales de 3 illustres anciens (Rivest https://fr.wikipedia.org/wiki/Ronald_Rivest, Shamir https://fr.wikipedia.org/wiki/Adi_Shamir et Adleman https://fr.wikipedia.org/wiki/Leonard_Adleman)

En utilisant ce que l’on a vu précédemment, au lieu de transmettre un message, on peut valider que son correspondant est bien celui qui nous a fourni la clef publique :

• Alice génère un message aléatoire
• Alice le crypte avec la clef publique de Bob
• Alice l’envoie à Bob
• Bob le décrypte
• Bob renvoie le message décrypté à Alice
• Si Alice reçoit son message aléatoire du début, c’est donc que le Bob qui parle est très vraisemblablement celui qui lui a fourni la clef publique, sinon … Charlie est intervenu sur la ligne, mais n’a pas réussi à se faire passer pour Bob.

ssh est le protocole de communication sécurisée le plus fréquemment utilisé. Il va mixer les deux types de chiffement:

• le chiffrement asymétrique (très lent) qui va permettre d’identifier le destinataire et de transmettre une clef partagée,
• le chiffrement symétrique (très rapide) qui utilise la clef qui vient d’être partagée.

Pour créer votre clef ssh : ssh-keygen -t ecdsa -b 521

• -t ecdsa choix d’un algorithme reconnu preque partout et très vraisemblablement plus fiable que rsa (qui est l’algorithme par défaut)
• b 521 la clef est sur 521 bits (c’est ce qui se fait de mieux pour l’instant, et cela reste assez petit pour ne pas créer de surcharge de trafic sur le réseau ; et non, c’est bien 521)

Si on être capable de conserver sa clef privée secrète, on peut laisser la passphrase vierge, cette passphrase servant à chiffrer sur la machine la clef privée.

Vous pouvez créer une clef pour chacun des algorithmes. Cela génèrera à chaque fois, une clef publique xxx.pub et une clef privée.

Si vous voulez faire connaitre votre clef publique, vous pouvez bien entendu la diffuser dans votre signature mail, sur votre compte facebook, etc… mais plus efficacement, la transmettre par : ssh-copy-id -i ~/.ssh/tatu-key-ecdsa user@host qui vous permettra de vous faire connaitre de la machine ’host’.

Pour ceux qui mettent des ’pass phrases’, il est possible d’exécuter ssh-agent qui se chargera de leur gestion et vous évitera de les tapper à tout bout de champ.

Une des rares choses simples est que l’on peut s’aider avec les tables de fréquences des lettres, digrammes, mots, etc.

Imaginons un code simple : Le message \(M\) ne contient que des majuscules, les mots sont séparés par des espaces. Soit \(f\) la bijection choisie par Bob pour communiquer avec Alice (par exemple, \(f\) remplace les ’A’ par des ’Z’, les ’B’ pr des ’U’, …). On suppose qu’Alice connait \(f\).

1. Fabriquer \(f\) en aléatoire uniforme : https://fr.wikipedia.org/wiki/M%C3%A9lange_de_Fisher-Yates
2. Ecrire la fonction de chiffrement (elle applique \(f\) à chacune des lettres du message à transmettre)
3. Ecrire la fonction de déchiffrement (elle applique \(f^{-1}\) à chacune des lettres du message reçu)
4. Récupérer une table de fréquence des lettres (français ou anglais au choix), comme cette table par exemple.
5. Ecrire une fonction Charlie_lettre qui prend un message crypté et qui essaie de le décrypter en utilisant la table de fréquence (il faut que le décrypté ait des fréquences de lettres les plus proches possibles de celle de la langue dans laquelle le message est écrit)

L’indice de coincidence mesure la probabilité que deux lettres prises au hasard soient les mêmes dans un message. Il est en particulier dépendant de la langue dans laquelle le message est écrit, mais il est suffisament stable, le locuteur en locuteur et de message en message pour pouvoir être utilisé (un indicateur à forte vaiance est moins intéressant qu’un indicateur à faible variance, car pour converger vers la valeur de l’indicateur, il devient nécessaire de disposer de messages de longueur très importante).