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.

I Définitions générales


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.

II Exemples de chiffrement

III Clé privée et clé publique

IV Scénarios

V D'autres exemples

VI Tous les exercices

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 :
  • 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 .
De plus, ces objets vérifient la propriété suivante :
pour tout e in , il existe un unique tel que
pour tout .

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-4 Chiffrement par transposition

II-5 Chiffrement linéaire

II-6 Chiffrement de Hill

II-7 Chiffrement RSA

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 : couple,
  • le message crypté .
  • la clé utilisée est e = 4.

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 : maison,
  • le message crypté .
  • la paire de clés utilisée est (e,f) = (2,9) 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 : couple,
  • le message crypté nbyife.
  • la paire de clés utilisée est la permutation suivante et
    et 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 : transformation.
  • le message crypté sformation.
  • la paire de clés utilisée est la permutation suivante et la permutation inverse
    et

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

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

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

IV Scénarios

Introduction à la cryptologie → IV Scénarios

IV-1 Partage de clés

IV-2 Enveloppe numérique

IV-3 Transmission entre deux personnes (principe du cadenas)

IV-4 Signature

IV-5 Transaction électronique

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
(appelé logarithme discret modulo p d'un entier n en base M).

Exercice

Logarithme discret I
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.
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.

Exemple [RSA]

On applique cette procédure avec le chiffrement RSA.

La procédure

Le destinataire du courrier
  • 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).
L'ami
  • 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 ;
Le destinataire du courrier
  • décrypte le message en lui appliquant la transformation
L'attaquant ou un autre ami peut avoir connaissance de (n, e) et du message crypté. Pour le décrypter, il doit 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 doit donc savoir factoriser n.

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

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
  • 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.
Les propriétés demandées sont
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
  • é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.

V D'autres exemples

Introduction à la cryptologie → V D'autres exemples

V-1 Jeu de pile ou face

V-2 Corrections d'erreurs

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
  • choisit un entier n produit de deux grands nombres premiers qu'il va garder secret,
  • choisit une fonction de chiffrement Ee tel que
    c'est-à-dire un entier e.
  • choisit un entier mA et transmet à B la valeur Ee(mA).
L'ami B
  • donne à A son entier mB.
L'ami A
  • 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.
L'ami B
  • calcule Ee(mA) et vérifie qu'il a bien la valeur transmise par A au premier échange.
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.

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

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

document donnant quelques exemples de chiffrements.
: encryption, RSA, coding, interactive mathematics, interactive math, server side interactivity

The most recent version
Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.