Introduction à la cryptologie

• Alphabet : alphabet usuel.
• Message en clair : un texte écrit.
• Message crypté un texte formé à partir des lettres de l'alphabet.

• Les clés : un entier entre 1 et 25,
• les transformations de chiffrement : en pensant aux lettres comme représentées par des entiers entre 1 et 26, on associe à la clé $e$ la transformation $E_e$ telle que, si $r$ est un message en clair, $E_e(r)$ soit l'entier compris entre 1 et 26 et congru à $r+e$ mod 26,
• les transformations de déchiffrement : on associe à la clé $d$ la transformation $D_d$ telle que, si $r$ est un message crypté, $D_d(r)$ soit l'entier compris entre 1 et 26 et congru à $r-d$ mod 26.
• la paire de clés est donnée par le couple $(e,e)$ pour $e$ un entier compris entre 1 et 26.

• un message en clair : transformation,
• le message crypté .
• la clé utilisée est $e=1$.

• Alphabet : alphabet usuel.
• Message en clair : un texte écrit.
• Message crypté : un texte formé à partir des lettres de l'alphabet.

• Les clés un couple d'entiers entre 1 et 25,
• les transformations de chiffrement : en pensant aux lettres comme représentées par des entiers entre 1 et 26, on associe à la clé $(e,f)$ la transformation $E_{(e,f)}$ telle que, si $r$ est un message en clair, $E_{(e,f)}(r)$ soit l'entier compris entre 1 et 26 et congru à $fr+e$ mod 26.
• les transformations de déchiffrement : on associe à la clé $(c,d)$ la transformation $D_{(c,d)}$ telle que, si $r$ est un message crypté, $D_{(c,d)}(r)$ soit l'entier compris entre 1 et 26 et congru à $cr-d$ mod 26.
• la paire de clés est donnée par le couple $((e,f),(c,d))$ pour $c,d,e,f$ des entiers compris entre 1 et 25 avec $c$ et $f$ premiers à 26 et

  ${\displaystyle \mathrm{cf}\equiv 1mod26,d\equiv cemod26.}$

• un message en clair : village,
• le message crypté .
• la paire de clés utilisée est $(e,f)=(13,13)$ et $(c,d)=(\mathrm{NaN},\mathrm{NaN})$.

• Alphabet : alphabet usuel
• Message en clair : un texte écrit dans votre langue
• Message crypté : un texte formé à partir des lettres de l'alphabet

• Les clés : toutes les permutations d'un ensemble à 26 éléments. Il y a donc 26! clés possibles.
• les transformations de chiffrement : en pensant aux lettres comme représentées par entiers entre 1 et 26, on associe à la clé $e$ la transformation $E_e$ telle que, si $r$ est un message en clair, $E_e(r)$ soit l'entier compris entre 1 et 26, image de $r$ par la permutation $e$.
• les transformations de déchiffrement : on associe à la clé $d$ la transformation $D_d$ telle que, si $r$ est un message crypté, $D_d(r)$ soit l'entier compris entre 1 et 26, image de $r$ par la permutation $d$.
• une paire de clés est donnée par le couple $(e,e^{-1})$ pour une clé $e$.

• un message en clair : village,
• le message crypté atbbyrc.
• la paire de clés utilisée est la permutation suivante et

  ${\displaystyle [1,2,3,4,5,6,7,8,9,10;25,7,15,14,3,8,18,17,20,10]}$

  ${\displaystyle [11,12,13,14,15,16,17,18;4,2,11,5,6,19,26,16]}$

  ${\displaystyle [19,20,21,22,23,24,25,26;12,9,24,1,22,21,13,23]}$

  et la permutation inverse

  ${\displaystyle [1,2,3,4,5,6,7,8,9,10;22,12,5,11,14,15,2,6,20,10]}$

  ${\displaystyle [11,12,13,14,15,16,17,18;13,19,25,4,3,18,8,7]}$

  ${\displaystyle [19,20,21,22,23,24,25,26;16,9,24,23,26,21,1,17]}$

• Alphabet : l'alphabet usuel + un symbole pour un blanc
• Message en clair : l'ensemble des chaînes de caractères de l'alphabet de longueur 5 (par exemple)
• Message crypté : l'ensemble des chaînes de caractères de l'alphabet de longueur 5 (par exemple)

• Les clés : toutes les permutations d'un ensemble à 5 éléments. Il y a donc 5! clés possibles.
• les transformations de chiffrement : on associe à la clé $e$ la transformation $E_e$ qui à chaque bloc de longueur 5 associe son image par la permutation $e$.
• les transformations de déchiffrement : on associe à la clé $d$ la transformation $D_d$ qui à chaque bloc de longueur 5 associe son image par la permutation $d^{-1}$.
• une paire de clés est donnée par le couple de permutations sur 5 éléments $(e,e)$ pour $e$ une clé.

• un message en clair : village.
• le message crypté age.
• la paire de clés utilisée est la permutation suivante et la permutation inverse

  ${\displaystyle [1,2,3,4,5;1,5,2,3,4]}$

  et

  ${\displaystyle [1,2,3,4,5;1,3,4,5,2].}$

• Alphabet : l'alphabet usuel + un symbole pour un blanc
• Message en clair : l'ensemble des chaînes de caractères de l'alphabet de longueur n (par exemple $n=5$) représentés par leur position dans l'alphabet (0 pour A, 1 pour B, etc).
• Message crypté : l'ensemble des chaînes de caractères de l'alphabet de longueur n (par exemple)

• Les clés : une suite $e=(e_1,e_2,e_3,e_4,...,e_n)$ de $n$ nombres entre 1 et 26. Par exemple, pour $n=5$ : 20, 5, 7, 9, 10
• les transformations de chiffrement : on associe à la clé $e$ la transformation $E_e$ qui à chaque bloc de longueur $n$ associe son image par l'application

  ${\displaystyle \tilde{e}:\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)\mapsto \left(\begin{array}{c}{x}_1+e_{1}mod26\\ x_2+e_{2}mod26\\ x_3+e_{3}mod26\\ x_4+e_{4}mod26\\ x_5+e_{5}mod26\end{array}\right)}$
• les transformations de déchiffrement : on associe à la clé $d$ la transformation $D_d$ qui à chaque bloc de longueur 5 associe son image par la transformation

  ${\displaystyle d:\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)\mapsto \left(\begin{array}{c}{x}_1-d_{1}mod26\\ x_2-d_{2}mod26\\ x_3-d_{3}mod26\\ x_4-d_{4}mod26\\ x_5-d_{5}mod26\end{array}\right)}$
• une paire de clés est donnée par le couple $(e,e)$ pour $e$ une clé.

• Alphabet : l'alphabet usuel
• Message en clair : l'ensemble des chaînes de caractères de l'alphabet de longueur $n$ représentés par leur position dans l'alphabet (0 pour A, 1 pour B, etc).
• Message crypté : l'ensemble des chaînes de caractères de l'alphabet de longueur $n$.

• Les clés : une matrice de taille $(n,n)$ modulo 26 et inversible modulo 26.
• les transformations de chiffrement : on associe à la clé $e$ la transformation $E_e$ qui à chaque bloc de longueur $n$ associe son image modulo 26 par l'application linéaire de matrice $e$. Par exemple,

  ${\displaystyle E_e:\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)\mapsto e\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)mod26}$
• les transformations de déchiffrement : on associe à la clé $d$ la transformation $D_d$ qui à chaque bloc de longueur $n$ associe son image par la transformation inverse

  ${\displaystyle D_d:\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)\mapsto d^{-1}\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)mod26}$
• une paire de clés est donnée par le couple $(e,e)$ pour $e$ une clé.

• Les clés : des couples d'entiers $(n,e)$.
• les transformations de chiffrement : on associe à la clé $(n,d)$ la transformation $E_{(n,d)}$ qui au message $r$ associe $r^{e}modn$ ;
• les transformations de déchiffrement : on associe à la clé $(n,e)$ la transformation $D_{(n,e)}$ qui au message $r$ associe $r^{d}modn$ ;
• une paire de clés est formé de deux clés $(n,d)$, $(n,e)$ avec $n=\mathrm{pq}$ produit de deux nombres premiers et

  ${\displaystyle \mathrm{de}\equiv 1mod(p-1)(q-1).}$

Clé

Le complice A

Le complice B

Le secret partagé entre A et B

Clé

Le complice A

Le complice B

Le secret partagé entre A et B

Exercice

• choisit une clé permettant de chiffrer
• la rend publique
• calcule la clé qui permet de déchiffrer.

• s'informe de la clé
• chiffre son message avec la clé fournie
• envoie le message chiffré.

• déchiffre le message en lui appliquant la clé de déchiffrement que lui seul connaît.

La procédure

Exercice

• choisit une clé qu'il rend publique et calcule la clé associée qui permet le déchiffrement
• crypte son message avec la clé publique
• envoie le message crypté au destinataire.

• s'informe du système de chiffrement choisi,
• choisit une clé qu'il rend publique et calcule la clé associée qui permet le déchiffrement,
• crypte le message reçu à l'aide de sa clé,
• envoie le message crypté deux fois à l'expéditeur.

• reçoit le message,
• le décrypte en partie en lui appliquant sa clé de déchiffrement,
• envoie le message ainsi transformé au destinataire ;

• reçoit pour la deuxième fois le message,
• le décrypte en lui appliquant sa transformation de déchiffrement.

Exercice

• un ensemble $ℳ$ de messages à signer ;
• un ensemble $𝒮$ de signatures en général de longueur fixée ;
• une transformation $S_A$ de $ℳ$ dans $𝒮$ tenue secrète par le signataire : elle associe à un message une signature.
• une transformation $V_A$ publique de $ℳ\times 𝒮$ dans $\{\mathrm{vrai},\mathrm{faux}\}$ : si on obtient vrai, on peut être sûr que le message vient de son expéditeur sans avoir été transformé ultérieurement.

• L'auteur crée une signature pour un message $m$ en calculant $s=S_A(m)$ (signature numérique) et transmet le couple $(m,s)$ . Il transmet aussi la fonction d'authentification $V_A$ (certificat électronique).
• Le destinataire

  • calcule $V_A(m,s)$,
  • accepte le message comme venant de $A$ si le résultat est vrai et le refuse si le résultat est faux.

• Chaque banque possède une clé privée et une clé publique.
• Sur votre carte, se trouve une clé privée (dite clé privée de votre carte) et la clé publique de votre banque.
• Le terminal du commerçant contient aussi sa clé privée et la clé publique de sa banque.

• émet une facture contenant des informations sur la transaction, sur votre compte en banque.
• crée une facture signée avec sa clé privée (elle contient donc la facture, un hachage/chiffrement de cette facture, le certificat)
• effectue le chiffrement de la facture (+ la signature ?) avec la clé publique de votre banque pour protéger le message durant la transmission.

• émet la facture contenant des informations sur la transaction, sur son compte en banque.
• crée une facture signée avec sa clé privée.
• effectue le chiffrement de la facture (avec la signature) avec la clé publique de sa banque pour protéger le message durant la transmission.

• ouvrent (déchiffent) chacune les enveloppes numériques en utilisant leurs clés privées.
• vérifient la signature des deux messages (venant de vous et du commerçant).
• vérifient que les deux factures transmises sont les mêmes.

• choisit un entier $n$ produit de deux grands nombres premiers qu'il va garder secret,
• choisit une fonction de chiffrement $E_e$ tel que

  ${\displaystyle E_e(n)\equiv n^{e}modp,}$

  c'est-à-dire un entier $e$.
• choisit un entier $m_A$ et transmet à B la valeur $E_e(m_A)$.

• donne à $A$ son entier $m_B$.

• compare les deux entiers $m_A$ et $m_B$ et leur parité et dit à $B$ s'il a gagné ou perdu ;
• donne à $A$ l'entier $m_A$ qu'il avait pris pour que $A$ puisse vérifier.

• calcule $E_e(m_A)$ et vérifie qu'il a bien la valeur transmise par $A$ au premier échange.