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.

Voici

• un message en clair : bijection,

• le message crypté .

• la clé utilisée est e = 10.

• 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 telle que, si r est un message en clair, soit l'entier compris entre 1 et 26 et congru à f r + e mod 26.

• les transformations de déchiffrement : on associe à la clé (c,d) la transformation telle que, si r est un message crypté, soit l'entier compris entre 1 et 26 et congru à c r - 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

Voici

• un message en clair : permutation,

• le message crypté .

• la paire de clés utilisée est (e,f) = (11,13) et (c,d) = (NaN,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 pour une clé e.

Voici

• un message en clair : bateau,

• le message crypté anxlni.

• la paire de clés utilisée est la permutation suivante et

  et la permutation inverse

• 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 .

• une paire de clés est donnée par le couple de permutations sur 5 éléments (e, e) pour e une clé.

Voici

• un message en clair : village.

• le message crypté age.

• la paire de clés utilisée est la permutation suivante et la permutation inverse

  et

• 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₁, e₂, e₃, e₄, ..., 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

• 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

• 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,

• 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

• 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 qui au message r associe ;

• les transformations de déchiffrement : on associe à la clé (n,e) la transformation qui au message r associe ;

• une paire de clés est formé de deux clés (n, d), (n, e) avec n = pq produit de deux nombres premiers et

Prenons un cadenas à code : le système mécanique est bien connu, par contre le code est privé ou secret . Si le code est connu par tout le monde, ce n'est pas la peine de racheter un autre cadenas, il suffit de changer le code.

Le cadenas est la transformation de chiffrement et déchiffrement, le code est la clé privée.

Si vous voulez améliorer votre système, une méthode sûre est la suivante : vous envoyez à un ami une valise contenant le message fermée avec votre cadenas et le code que vous êtes seul à connaître. Votre ami rajoute un cadenas (avec le code qu'il est seul à connaître) et vous renvoie la valise. Vous enlevez votre cadenas et lui renvoyez la valise. Votre ami peut maintenant ouvrir votre valise puisqu'il reste seulement son cadanas.

Conclusion : la méthode est sûre ... mais coûteuse (trois voyages pour la valise au lieu d'un).

Avoir un secret commun qui servira ensuite comme clé. Pour cela, chacun chiffre un message public avec sa clé propre et rend public ce chiffrement. En rechiffrant le message de l'autre avec sa clé propre, un même message est obtenu. C'est le secret commun.

Un message M public est choisi.

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

Ce qui est difficile à calculer ici est un entier r tel que

(appelé logarithme discret modulo p d'un entier n en base M).

Exercice

Des amis veulent vous envoyer un courrier confidentiel. Vous devez être le seul à pouvoir le lire.

Une variante : Les subordonnés doivent transmettre des messages chiffrés au chef. Seul le chef doit pouvoir décrypter les messages.

un ensemble de messages à transmettre par les amis au destinataire. On utilise un système de chiffrement à clés dissymétriques

Le destinataire du courrier

• choisit une clé permettant de chiffrer

• la rend publique

• calcule la clé qui permet de déchiffrer.

Un ami

• s'informe de la clé

• chiffre son message avec la clé fournie

• envoie le message chiffré.

Le destinataire du courrier

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

L'attaquant ou un autre ami peut avoir connaissance de la clé de chiffrement et du message crypté. Mais il ne peut pas ou ne doit pas pouvoir calculer à partir de là la clé permettant de déchiffrer.

On applique cette procédure avec le chiffrement RSA.

La procédure

Exercice

Deux personnes veulent échanger des messages de manière très sûre.

un ensemble de messages à transmettre .

Un système de chiffrement est choisi.

L'expéditeur

• 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.

Le 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.

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 ;

e destinataire

• reçoit pour la deuxième fois le message,

• le décrypte en lui appliquant sa transformation de déchiffrement.

Cette procédure peut d'effectuer en utilisant le système de chiffrement RSA.

Exercice

Je reçois un texte de quelqu'un et je veux être sûr que le message vient de lui. Le message peut être public et connu de tout le monde. La manière de l'authentifier est elle aussi connue de tout le monde. Par contre, on veut être sûr que quelqu'un interceptant le message et le renvoyant n'a pas changé le texte. Il faut donc que le message et la signature soient liés.

On dispose de

• 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 dans : 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 .

Lors d'une transaction électronique, les informations transmises doivent être vérifiées avant que la transaction (transfert d'argent de banque à banque) aient lieu.

• 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 .

Au préalable, vous prouvez en entrant le code secret dans un terminal de paiement électronique que vous êtes bien le propriétaire de la carte (authentification ).

La carte

• é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.

Le terminal du commerçant

• é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.

Ces deux enveloppes sont envoyés aux deux banques dans le réseau des banques.

Les banques

• 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.

Si tout est conforme, elles débitent votre compte et créditent celui du commerçant.

Vous devez jouer à pile ou face par téléphone avec un ami. Pour cela, vous allez chacun choisir un nombre. S'ils sont de même parité, vous avez gagné, sinon c'est votre ami. Mais l'un d'entre vous doit dire en premier le nombre. Et comment être sûr que l'autre ne trichera pas ?

L'ami A

• choisit un entier n produit de deux grands nombres premiers qu'il va garder secret,

• choisit une fonction de chiffrement E_e tel que

  c'est-à-dire un entier e.

• choisit un entier m_A et transmet à B la valeur E_e(m_A).

L'ami B

• donne à A son entier m_B.

L'ami A

• 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.

L'ami B

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