Introduction à la cryptologie
Introduction à la cryptologie
Définition
Cryptologie : (littéralement « science du secret » )
étude des techniques mathématiques
reliées aux aspects de la transmission d'information telles que
- confidentialité
- intégrité des données
- authentification.
On doit préciser les caractéristiques du système, c'est-à-dire ce que l'on en attend. Les exemples de chiffrement qui suivent permettent de réfléchir à la notion de clé. Ils sont présentés dans un ordre chronologique.
I Définitions générales
Introduction à la cryptologie
→ I Définitions générales
Les outils produits sont évalués selon certains critères :
- niveau de sécurité
- commodité d'utilisation
- performance
- facilité d'implémentation
L'information est obtenue à partir des données suivantes :
-
un alphabet de définition
un ensemble fini, par exemple les lettres de l'alphabet. Mais le plus courant est l'alphabet binaire qui est simplement l'ensemble . En donnant à chaque lettre de l'alphabet un numéro et en écrivant ce nombre en binaire, on peut remplacer chaque lettre de l'alphabet par un nombre en binaire de longueur 5 (ou 8 si on veut aussi coder les accents).
Codage binaire
-
un ensemble des messages en clair
un ensemble formé de suites de symboles appartenant à l'alphabet de définition.
-
un ensemble des messages chiffrés
un ensemble .
Définition
Pour avoir un système cryptographique, on a besoin des objets suivants :
pour tout e in , il existe un unique tel que
pour tout
.
-
l'ensemble des clés
noté .
-
une transformation de chiffrement
pour tout élément e de , une bijection Ee de sur .
-
une transformation de déchiffrement
pour tout élément d de , une bijection Dd de sur .
pour tout e in , il existe un unique tel que
Le couple (e, d) forme une paire de clés. Cette paire de clés est censée permettre la confidentialité du message.
Appliquer la transformation Ee à un message en clair signifie le crypter (chiffrer).
Appliquer la transformation Dd à un message crypté signifie le décrypter (déchiffrer).
Les clés, les messages cryptés sont transmis par un canal qui peut être public ou secret.
II Exemples de chiffrement
Introduction à la cryptologie
→ II Exemples de chiffrement
Dans les exemples qui suivent, l'alphabet est l'alphabet usuel (avec éventuellement un symbole pour le blanc espace)
II-1 Permutation circulaire sur les lettres de l'alphabet.
II-2 Transformation affine sur les lettres de l'alphabet
Un exemple un peu plus élaboré :
II-3 Permutation quelconque sur les lettres de l'alphabet
Sur un texte long, il est facile de déchiffrer des textes codés ainsi en utilisant l'analyse de fréquences des lettres ou les caractéristiques de certains languages.
Dans les deux chiffrements suivants, une même lettre peut être cryptée de plusieurs manières.
II-1 Permutation circulaire sur les lettres de l'alphabet.
Introduction à la cryptologie
→
II Exemples de chiffrement
→ II-1 Permutation circulaire sur les lettres de l'alphabet.
C'est le codage de Jules César.
L'information
- Alphabet : alphabet usuel.
- Message en clair : un texte écrit.
- Message crypté un texte formé à partir des lettres de l'alphabet.
Le chiffrement
- 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 Ee telle que, si r est un message en clair, Ee(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 Dd telle que, si r est un message crypté, Dd(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.
Exemple
Voici
- un message en clair : bijection,
- le message crypté .
- la clé utilisée est e = 7.
Exercice
Décryptage d'un texte
II-2 Transformation affine sur les lettres de l'alphabet
Introduction à la cryptologie
→
II Exemples de chiffrement
→ II-2 Transformation affine sur les lettres de l'alphabet
L'information
- Alphabet : alphabet usuel.
- Message en clair : un texte écrit.
- Message crypté : un texte formé à partir des lettres de l'alphabet.
Le chiffrement
- 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
Exemple
Voici
- un message en clair : couple,
- le message crypté .
- la paire de clés utilisée est (e,f) = (18,7) et (c,d) = (NaN,NaN).
Exercice
A vous de jouer
II-3 Permutation quelconque sur les lettres de l'alphabet
Introduction à la cryptologie
→
II Exemples de chiffrement
→ II-3 Permutation quelconque sur les lettres de l'alphabet
L'information
- Alphabet : alphabet usuel
- Message en clair : un texte écrit dans votre langue
- Message crypté : un texte formé à partir des lettres de l'alphabet
Le chiffrement
- 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 Ee telle que, si r est un message en clair, Ee(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 Dd telle que, si r est un message crypté, Dd(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.
Exemple
Voici
- un message en clair : village,
- le message crypté yammhlc.
- la paire de clés utilisée est la permutation suivante etet la permutation inverse
II-4 Chiffrement par transposition
Introduction à la cryptologie
→
II Exemples de chiffrement
→ II-4 Chiffrement par transposition
L'information
- 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)
Le chiffrement
- 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 Ee 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 Dd 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é.
Exemple
Voici
- un message en clair : epoustouflant.
- le message crypté stouflant.
- la paire de clés utilisée est la permutation suivante et la permutation inverseet
Exercice
A vous de jouer
II-5 Chiffrement linéaire
Introduction à la cryptologie
→
II Exemples de chiffrement
→ II-5 Chiffrement linéaire
L'information
- 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)
Le chiffrement
- Les clés : une suite e = (e1, e2, e3, e4, ..., en) 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 Ee qui à chaque bloc de longueur n associe son image par l'application
- les transformations de déchiffrement : on associe à la clé d la transformation Dd 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é.
Exercice
A vous de jouer
II-6 Chiffrement de Hill
Introduction à la cryptologie
→
II Exemples de chiffrement
→ II-6 Chiffrement de Hill
L'information
- 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.
Le chiffrement
- 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 Ee 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 Dd 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é.
Exercice
A vous de jouer
II-7 Chiffrement RSA
Introduction à la cryptologie
→
II Exemples de chiffrement
→ II-7 Chiffrement RSA
Ce chiffrement est dû à Rivest, Shamir et Adelman (1977).
Contrairement aux chiffrements décrits auparavant, la donnée de la clé de chiffrement e ne permet pas de trouver facilement la clé de déchiffrement d : il faut pour cela calculer un entier d tel que
et donc déjà connaître
(p - 1)(q - 1).
Or
ce qui revient à connaître
p et
q
(si on connaît
p + q et
pq, on connaît
p et
q). Il faut donc
savoir factoriser
n. Ce qui est une opération difficile.
Le chiffrement
- 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
Contrairement aux chiffrements décrits auparavant, la donnée de la clé de chiffrement e ne permet pas de trouver facilement la clé de déchiffrement d : il faut pour cela calculer un entier d tel que
III Clé privée et clé publique
Introduction à la cryptologie
→ III Clé privée et clé publique
Définition
Un système de chiffrement (cryptage) est dit cassable si un adversaire,
n'ayant pas connaissance de la clé
(e,d), peut trouver
le message en clair dans un laps de temps déterminé.
Lorsque la connaissance de la clé e implique la connaissance de la clé d associée, on parle de système à clés symétriques. Dans ce cas, la clé e doit être transmise par un canal sûr. La paire de clés (e,d) est appelée clé secrète (c'est un secret partagé entre deux personnes). Par contre l'ensemble de transformations de chiffrement et déchiffrement est public. En gros, il s'agit de la même clé ... qu'on tourne vers la droite ou vers la gauche.
Définition
Un système de chiffrement est dit à clés symétriques
si pour chaque couple
(e,d) de clés associées,
il est facile de trouver
d connaissant
e et réciproquement.
Il n'est pas raisonnable, dans un tel système, de rendre publique une des deux clés. La clé e est ici appelée clé privée (une seule personne (ou deux) la connaît). Par contre l'ensemble de transformations de chiffrement et déchiffrement est public.
Définition
Un système de chiffrement est dit à clé publique
si pour chaque couple
(e,d) de clés associés, il est difficile
de trouver
d connaissant
e.
L'idée a été introduite en 1976 par Diffie et Hellman.
Tout est bien sûr aussi dans la définition de facile. Tout dépend aussi du prix qu'on est prêt à payer et du temps dont on dispose ...
Exemple [Principe du double cadenas]
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).
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).
IV Scénarios
Introduction à la cryptologie
→ IV Scénarios
IV-1 Partage de clés
Introduction à la cryptologie
→
IV Scénarios
→ IV-1 Partage de clés
Objectif
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.
Les chiffrements que l'on peut utiliser dans ces circonstances doivent commuter, c'est-à-dire que si l'on prend deux clés différentes du même système de chiffrement, le résultat est le même quelque soit l'ordre dans lequel on les applique.
Exemple [simple mais peu sûr]
Un message
M public est choisi.
Le complice A
- choisit un entier nA entre 2 et 25,
- chiffre M avec le codage de Jules César associé à la clé nA,
- rend le résultat chifA(M) public.
Le complice B
- choisit un entier nB entre 2 et 25,
- chiffre M avec le codage de Jules César associé à la clé nB,
- rend le résultat chifB(M) public.
Le secret partagé entre A et B
est le nombre
Le complice
A calcule
Secret(AB) comme
chifA(chifB(M)) et
B calcule
Secret(AB)
comme
chifB(chifA(M)).
Exemple [Protocole de Diffie et Hellman]
Clé
Un nombre premier
p public et un entier
M entre 2 et
p - 2 public.
Le complice A
- choisit un entier nA entre 2 et p - 2;
- calcule ,
- rend xA public.
Le complice B
- choisit un entier nB entre 2 et p - 2;
- calcule ,
- rend xB public.
Le secret partagé entre A et B
est le nombre
Le complice
A calcule
Secret(AB) comme
et
B calcule
Secret(AB)
comme
.
Ce qui est difficile à calculer ici est un entier
r tel que
Exercice
Logarithme discret I
Logarithme discret II
Logarithme discret II
IV-2 Enveloppe numérique
Introduction à la cryptologie
→
IV Scénarios
→ IV-2 Enveloppe numérique
Objectif
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.
L'information
un ensemble
de messages à transmettre par les amis au destinataire.
On utilise un système de chiffrement à clés dissymétriques
La procédure
Le destinataire du courrier
- 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.
Exemple [RSA]
On applique cette procédure avec le chiffrement RSA.
La procédure
Le destinataire du courrier
et donc déjà connaître
(p - 1)(q - 1).
Or
ce qui revient à connaître
p et
q
(si on connaît
p + q et
pq, on connaît
p et
q). Il doit donc
savoir factoriser
n.
- choisit deux nombres premiers p et q,
- calcule leur produit n,
- choisit un entier d premier à (p - 1)(q - 1),
- calcule un entier e tel que
- déclare par un canal public que la clé est (n, d).
- s'informe de la clé,
- crypte son message en lui appliquant la transformation à l'aide de la clé (n, d),
- envoie le message crypté au destinataire du courrier ;
- décrypte le message en lui appliquant la transformation
Exercice
- Création de votre code RSA
- Vous devez envoyer votre message crypté
- Ici vous êtes l'attaquant
- Ici, vous devez lire le message crypté qu'on vous a envoyé
IV-3 Transmission entre deux personnes (principe du cadenas)
Introduction à la cryptologie
→
IV Scénarios
→ IV-3 Transmission entre deux personnes (principe du cadenas)
Objectif
Deux personnes veulent échanger des messages de manière très sûre.
L'information
un ensemble
de messages à transmettre.
La procédure
Un système de chiffrement est choisi.
L'expéditeur
Le destinataire
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.
- 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.
C'est le principe du double cadenas.
Exemple [RSA]
Cette procédure peut d'effectuer en utilisant le système de chiffrement RSA.
Exercice
La mettre en place !
IV-4 Signature
Introduction à la cryptologie
→
IV Scénarios
→ IV-4 Signature
Objectif
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.
Le chiffrement
On dispose de
Les propriétés demandées sont
- un ensemble de messages à signer ;
- un ensemble de signatures en général de longueur fixée ;
- une transformation SA de dans tenue secrète par le signataire : elle associe à un message une signature.
- une transformation VA 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.
VA(m, s) est vrai si et seulement si
s = SA(m).
Il doit être impossible pour quelqu'un d'autre que A de trouver un s dans tel que VA(m, s) = vrai s'il a la connaissance de m.
La procédure
- L'auteur crée une signature pour un message m en calculant s = SA(m) (signature numérique) et transmet le couple (m, s) . Il transmet aussi la fonction d'authentification VA (certificat électronique).
- Le destinataire
- calcule VA(m, s),
- accepte le message comme venant de A si le résultat est vrai et le refuse si le résultat est faux.
Il est impossible pour quelqu'un d'autre que A de trouver pour tout message m un s dans tel que VA(m, s) soit vrai.
Ici le message m peut être écrit en clair et connu par tout le monde. Par contre, quelqu'un interceptant le couple (m, s) et connaissant la fonction VA ne doit pas être capable de changer m en m' et de manière à ce que VA(m', s) soit encore vrai. L'adversaire est ici un adversaire actif.
IV-5 Transaction électronique
Introduction à la cryptologie
→
IV Scénarios
→ IV-5 Transaction électronique
Objectif
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.
L'information
- 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 procédure
La carte
Le terminal du commerçant
Ces deux enveloppes sont envoyés aux deux banques dans le réseau des banques.
Les banques
- é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.
V D'autres exemples
Introduction à la cryptologie
→ V D'autres exemples
V-1 Jeu de pile ou face
Introduction à la cryptologie
→
V D'autres exemples
→ V-1 Jeu de pile ou face
Objectif
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 ?
La procédure
L'ami
A
Ainsi, la transformation
Ee étant difficile à inverser,
B n'a pas
le temps d'inverser
Ee(mA) et donc de calculer
mA.
Quand à
A, il ne peut pas tricher, car
B va pouvoir vérifier.- choisit un entier n produit de deux grands nombres premiers qu'il va garder secret,
- choisit une fonction de chiffrement Ee tel quec'est-à-dire un entier e.
- choisit un entier mA et transmet à B la valeur Ee(mA).
- donne à A son entier mB.
- compare les deux entiers mA et mB et leur parité et dit à B s'il a gagné ou perdu ;
- donne à A l'entier mA qu'il avait pris pour que A puisse vérifier.
- calcule Ee(mA) et vérifie qu'il a bien la valeur transmise par A au premier échange.
Exercice
- Jeu de pile ou face I
- Jeu de pile ou face II
V-2 Corrections d'erreurs
Introduction à la cryptologie
→
V D'autres exemples
→ V-2 Corrections d'erreurs
Les exemples suivants relèvent plutôt de la vérification qu'une erreur de frappe n'a pas été commise.
Exercice
Authentification
Exercice
Billet de banque 1
Billet de banque 2
Billet de banque 2
VI Tous les exercices
Introduction à la cryptologie
→ VI Tous les exercices
- Codage binaire
- Décryptage d'un texte
- A vous de jouer
- A vous de jouer
- A vous de jouer
- A vous de jouer
- Logarithme discret I
- Logarithme discret II
- Jeu de pile ou face I
- Jeu de pile ou face II
- Authentification
- Billet de banque 1
- Billet de banque 2