Chapitre 1

Introduction et terminologie.

L’objectif fondamental de la cryptographie est de permettre à deux person-

nes appelées traditionnellement, Alice et Bob de communiquer à travers
un canal peu sûr de telle sorte qu’un opposant passif Éve ne puisse pas
comprendre ce qui est échangé et que les données échangées ne puissent pas
être modifiées ou manipulées par un opposant actif Martin.
Après un rapide historique de la cryptographie on examinera les princi-
paux systèmes cryptographiques modernes utilisés pour la transmission et
le stockage sécurisé de données.
On ne s’intéresse qu’aux systèmes cryptographiques destinés à transmettre
des flux importants et variés d’informations (paiement sécurisé par inter-
net, données bancaires, cartes de crédit, protection des conversations entre
téléphones mobile, WiFi,...) entre de nombreux interlocuteurs qui nécessi-
tent des systèmes cryptographiques structurés et rapides.
On ne décrira pas de systèmes cryptographiques reposant sur la dissimula-
tion de l’information secrète au sein d’un document, d’une image (stéga-
nographie,...). Par contre on s’intéressera à la stéganographie quand elle
est utilisée pout le marquage de document watermarking ou tatouage.
Le tatouage permet de protéger les possesseurs de copyright sur des docu-
ments numériques en cachant une signature dans l’information de sorte que
même une partie modifiée du document conserve la signature et de découvrir
l’origine de fuites en marquant de façon cachée et unique chaque copie d’un
document confidentiel.
Un système cryptographique ne se conçoit pas indépendamment des at-
taques dont il peut être l’objet. On indiquera donc pour chaque système
cryptographique quelques attaques et sa résistance à ces attaques.
L’accent sera mis sur les principes et les outils mathématiques utilisés (arith-
métique, algèbre, algorithmique, complexité, probabilité, théorie de l’infor-

7
8 CHAPITRE 1. INTRODUCTION ET TERMINOLOGIE

mation,..). Quelques protocoles seront décrits.

On évoquera rapidement les systèmes d’infrastructure pour les Systèmes à
Clef Publique (Public Key Infrastructures ou PKI) et les systèmes de Man-
agement des Clefs Secrètes (Symmetric Keys Management). On évoquera
aussi quelques grands types de menaces et d’attaques sur les systèmes cryp-
tographiques.
Les problèmes de mise en oeuvre informatique, les produits et les normes
sont décrits dans des cours plus appliqués (réseaux, sécurité réseaux,...).
On emploiera indifféremment les mots cryptographie, chiffrement et codage.
Les mots en gras figurent dans l’index à la fin du volume avec un renvoi à
leur définition.
Ce cours s’est beaucoup inspiré des cours de François Arnaux, [2], Jean-
Louis Pons, [21], et Guy Robin, [24], des livres de Douglas Stinson, [31],
Neal Koblitz, [18], John Daemen et Vincent Rijmen, [8], Serge Vaudenay,
[32], Lawrence Washington, [33], Benne de Weger, [34] et Gilles Zémor [37],
des deux tomes de l’ouvrage collectif édité par Touradj Ebrahimi, Franck
Leprévost, Bertrand Warusfel, [11], [12] et d’articles de WIKIPEDIA ainsi
que de l’ouvrage de Simon Singh, [29], pour la partie historique.

1.1 Qu’est ce que la cryptographie.

La cryptographie ou science du secret est un art très ancien, c’est

l’art de remplacer un secret encombrant par un secret miniature

Le secret encombrant est le contenu du message il est remplacé par un petit

secret qui est la clef de déchiffrement dont la taille est en général de quelques
centaines à quelques milliers de bits à comparer aux mégabits d’un message.
La cryptographie est l’art de rendre inintelligible, de crypter, de coder,
un message pour ceux qui ne sont pas habilités à en prendre connaissance.
Le chiffre, le code est le procédé, l’algorithme, la fonction, qui permet de
crypter un message.
La cryptanalyse est l’art pour une personne non habilitée, de décrypter,
de décoder, de déchiffrer, un message. C’est donc l’ensemble des procédés
d’attaque d’un système cryptographique.
La cryptologie est l’ensemble formé de la cryptographie et de la cryptanal-
yse.
1.1. QU’EST CE QUE LA CRYPTOGRAPHIE 9

La cryptologie fait partie d’un ensemble de théories et de techniques liées à la

transmission de l’information (théorie des ondes électro-magnétiques, théorie
du signal, théorie des codes correcteur d’erreurs, théorie de l’information,
théorie de la complexité,...).
Un expéditeur Alice veut envoyer un message à un destinataire Bob en
évitant les oreilles indiscrète d’Ève, et les attaques malveillantes de Martin.
Pour cela Alice se met d’accord avec Bob sur le cryptosystème qu’ils vont
utiliser. Ce choix n’a pas besoin d’être secret en vertu du principe de Ker-
ckhoffs, cf. section 1.2.
L’information qu’Alice souhaite transmettre à Bob est le texte clair . Le
processus de transformation d’un message, M , pour qu’il devienne incom-
préhensible à Ève est appelé le chiffrement ou la codage. On génère ainsi
un message chiffré, C, obtenu grâce à une fonction de chiffrement,
E, par C = E(M ).
Le processus de reconstruction du message clair à partir du message chiffré
est appelé le déchiffrement ou décodage et utilise une fonction de
déchiffrement, D. On demande que pour tout message clair M

D(C) = D(E(M )) = M

Autrement dit on demande que tout message codé provienne d’un et d’un
seul message clair (D est une fonction surjective des messages codés vers les
messages clairs et E est une fonction injective des messages clairs sur les
messages codés).
Un algorithme cryptographique est l’ensemble des fonctions (mathémati-
ques ou non) utilisées pour le chiffrement et le déchiffrement. En pratique les
fonctions E et D sont paramétrées par des clés, Ke la clé de chiffrement
et Kd la clef de déchiffrement, qui peuvent prendre l’une des valeurs d’un
ensemble appelé espace des clefs. On a donc la relation suivante
(
EKe (M ) = C
DKd (C) = M

Le type de relation qui unit les clés Ke et Kd permet de définir deux grandes
catégories de systèmes cryptographiques

• Les systèmes à clef secrètes ou symétriques: (DES, AES, IDEA,

Blowfish,...)
10 CHAPITRE 1. INTRODUCTION ET TERMINOLOGIE

• Les systèmes à clefs publiques ou asymétriques: (RSA, El-Gamal,

un cryptosystème elliptique,...)
En outre les fonctions de codage E et de décodage D peuvent fonctionner
de deux façons
• en continu: chaque nouveau bit est manipulé directement
• par bloc: chaque message est d’abord partitionné en blocs de longueur
fixe. Les fonctions de chiffrement et déchiffrement agissent alors sur
chaque bloc.
Chacun de ces systèmes dépend d’un ou deux paramètres de taille as-
sez réduite (128 à 2048 bits) appelés la clef de chiffrement et la clé de
déchiffrement. Les clefs de chiffrement et de déchiffrement n’ont aucune
raison d’être identiques. Seule la clef de déchiffrement doit impérativement
être secrète.

1.2 Principes de Kerckhoffs.

En 1883 dans un article paru dans le Journal des sciences militaires, [17],
Auguste Kerckhoffs (1835-1903) posa les principes de la cryptographie mod-
erne. Ces principes et en particulier le second stipulent entre autre que la
sécurité d’un cryptosystème ne doit pas reposer sur le secret de l’algorithme
de codage mais qu’elle doit uniquement reposer sur la clef secrète du cryp-
tosystème qui est un paramètre facile à changer, de taille réduite (actuelle-
ment de 64 à 2048 bits suivant le type de code et la sécurité demandée) et
donc assez facile à transmettre secrètement.
Ce principe a été très exactement respecté pour le choix du dernier standard
de chiffrement, l’algorithme symétrique AES, par le NIST. Ce dernier a
été choisi à la suite d’un appel d’offre international et tous les détails de
conception sont publics. Ce principe n’est que la transposition des remarques
de bon sens suivantes:
• Un cryptosystème sera d’autant plus résistant et sûr qu’il aura été
conçu, choisi et implémenté avec la plus grande transparence et soumis
ainsi à l’analyse de l’ensemble de la communauté cryptographique.
• Si un algorithme est supposé être secret, il se trouvera toujours quel-
qu’un soit pour vendre l’algorithme, soit pour le percer à jour, soit pour
en découvrir une faiblesse ignorée de ses concepteurs. À ce moment là
c’est tout le cryptosystème qui est à changer et pas seulement la clé.
1.3. QUALITÉS D’UN CRYPTOSYSTÈME 11

Les systèmes conçus dans le secret révèlent souvent rapidement des défauts
de sécurité qui n’avaient pas été envisagés par les concepteurs.

1.3 Qualités d’un cryptosystème.

Les qualités demandées à un système cryptographique sont résumées par les
mots clefs suivants:

• Confidentialité: seules les personnes habilitées ont accès au contenu

du message.

• Intégrité des données: le message ne peut pas être falsifié sans

qu’on s’en aperçoive.

• Authentification:

– l’émetteur est sûr de l’identité du destinataire c’est à dire que

seul le destinataire pourra prendre connaissance du message car
il est le seul à disposer de la clef de déchiffrement.
– le receveur est sûr de l’identité de l’émetteur

• Non-répudiation qui se décompose en trois:

– non-répudiation d’origine l’émetteur ne peut nier avoir écrit

le message et il peut prouver qu’il ne l’a pas fait si c’est effective-
ment le cas.
– non-répudiation de réception le receveur ne peut nier avoir
reçu le message et il peut prouver qu’il ne l’a pas reçu si c’est
effectivement le cas.
– non-répudiation de transmission l’émetteur du message ne
peut nier avoir envoyé le message et il peut prouver qu’il ne l’a
pas fait si c’est effectivement le cas.

On peut regarder ces quatre qualités du point de vue de l’émetteur. Alice

veut être certaine

• qu’une personne non-autorisée (Ève) ne peut pas prendre connaissance

des messages qu’elle envoie, confidentialité.

• que ses messages ne seront pas falsifiés par un attaquant malveillant

(Martin), intégrité.
12 CHAPITRE 1. INTRODUCTION ET TERMINOLOGIE

• que le destinataire (Bob) a bien pris connaissance de ses messages et

ne pourra pas nier l’avoir reçu, non-répudiation.

de plus elle veut être certaine que son message ne sera pas brouillé par
les imperfections du canal de transmission (cette exigence ne relève pas du
cryptage mais de la correction d’erreur).
Bob veut être certain

• que personne d’autre que lui (et Alice bien sûr) n’a accès au contenu
du message, confidentialité.

• que le message reçu vient bien d’Alice authentification, par exemple

qu’un attaquant malveillant (Oscar) ne puisse pas se faire passer pour
Alice, mascarade ou usurpation d’identité

• que le message n’a pas été falsifié par un attaquant malveillant (Mar-
tin), intégrité des données

• que l’expéditeur (Alice) ne pourra pas nier avoir envoyé le message,

non-répudiation

1.4 Attaques sur un chiffrement.

La cryptanalyse est l’ensembles des procédés d’attaque d’un cryptosys-
tème. Elle est indispensable pour l’étude de la sécurité des procédés de
chiffrement utilisés en cryptographie. Son but ultime est de trouver un
algorithme de déchiffrement des messages. Le plus souvent on essaye de
reconstituer la clef secrète de déchiffrement.
On suppose, en vertu des principes de Kerckhoffs, pour toutes les évaluations
de sécurité d’un cryptosystème que l’attaquant connait le système cryp-
tographique utilisé, la seule partie secrète du cryptosystème est la clef.
Par exemple dans un cryptosystème basé sur des registres à décalage on
suppose que l’attaquant connait la forme des récurrences linéaires ainsi que
la fonction de combinaison mais pas les conditions intiales des récurrences
qui constituent la clef du code.
On doit distinguer entre les types d’attaques d’un adversaires et les buts
des attaques d’un adversaire.
Les principaux types d’attaques:
1.4. ATTAQUES SUR UN CHIFFREMENT 13

• attaque à texte chiffré connu: l’opposant ne connait que le mes-

sage chiffré y.

• attaque à texte clair connu: l’opposant dispose d’un texte clair x

et du message chiffré correspondant y

• attaque à texte clair choisi : l’opposant a accès à une machine

chiffrante. Il peut choisir un texte clair et obtenir le texte chiffré
correspondant y, mais il ne connait pas la clef de chiffrement.

• attaque à texte chiffré choisi : l’opposant a accès à une machine

déchiffrante. Il peut choisir un texte chiffré, y et obtenir le texte clair
correspondant x, mais il ne connait pas la clef de déchiffrement.

En plus de ces attaques basées sur une étude de messages codés, il y a

aussi des attaques physiques. Le principe de ces attaques est d’essayer de
reconstituer la clef secrète par exemple en espionnant la transmission entre
le clavier de l’ordinateur et l’unité centrale ou en mesurant la consommation
électrique du microprocesseur qui effectue le décodage du message ou encore
en mesurant son échauffement. Ensuite on essaye de remonter de ces données
physiques aux clefs de codage et décodage.
Une méthode pour résister à ce type d’attaque sont les protocoles de preuve
sans transfert de connaissance (zero-knowledge proof) dont on donne une
idée à la section 11.5.
Le but de l’attaque d’un adversaire peut être soit de découvrir la clef du
chiffrement et de pouvoir ainsi décrypter tous les messages de l’émetteur
ou plus modestement de décryter un message particulier sans nécessai-
rement disposer de la clef du code.
Garantir la confidentialité des communications entre Alice et Bob suppose
donc qu’Ève ne peut pas

• trouver M à partir de E(M ) (le crypto-système doit être résistant aux

attaques sur le message codé)

• trouver la méthode de déchiffrement D à partir d’une famille de cou-

ples, {(Mi , E(Mi )}, (message clair, message codé correspondant).

• accéder à des données contenues dans le micro-processeur qui code et

décode et plus généralement ne puisse pas espionner les ordinateurs
d’Alice et de Bob
14 CHAPITRE 1. INTRODUCTION ET TERMINOLOGIE

1.5 Différentes notions de sécurité d’un cryptosystème.

• La sécurité inconditionnelle qui ne préjuge pas de la puissance de

calcul du cryptanalyste qui peut être illimitée.

• La sécurité calculatoire qui repose sur l’impossibilité de faire en un

temps raisonnable, compte tenu de la puissance de calcul disponible,
les calculs nécessaires pour décrypter un message. Cette notion dépend
de l’état de la technique à un instant donné.

• La sécurité prouvée qui réduit la sécurité du cryptosystème à un

problème bien connu réputé difficile, par exemple on pourrait prouver
un théorème disant qu’un système cryptographique est sûr si un entier
donné n ne peut pas être factorisé.

• La confidentialité parfaite qualité des codes pour lesquels un couple

(message clair, message chiffré) ne donne aucune information sur la
clef.

Toutes ces notions de sûreté reposent sur la théorie de l’information de

Claude Shannon, cf. le chapitre 13.1.
Il a pu donner un sens précis basé sur les probabilités à la notion de sécurité
inconditionnelle si l’on précise le type d’attaques permises. Il a aussi donné
un sens précis à la notion de confidentialité parfaite.
La notion de sécurité calculatoire repose sur la théorie de la complexité,
cf chapitre 13.2. Dans la pratique il faut préciser le type d’attaque. C’est
la sécurité calculatoire que l’on utilise dans la plupart des évaluations de
sécurité des systèmes cryptographiques. Elle repose sur la remarque suiv-
ante: même avec des ordinateurs faisant 109 opérations élémentaires par sec-
onde un calcul qui nécessite 2100 opérations élémentaires est hors de portée
actuellement car pour l’effectuer il faut environ 4 · 1013 années!
La sécurité prouvée consiste à ramener la sécurité d’un cryptosystème à
un problème que l’on sait ou que l’on espère être calculatoirement difficile
comme par exemple la factorisation des entiers en facteurs premiers. Ceci
permet de classifier les différents cryptosystèmes suivant leur sécurité et de
procéder à une veille technologique rationnelle.
Historique.

Il y a historiquement deux grandes familles de codes classiques avec des

hybrides

• Les codes à répertoire

• Les codes à clefs secrètes qui se subdivisent en deux familles

– les codes de transposition ou de permutation qui sont des codes

par blocs.
– les codes de substitution qui peuvent être des codes par blocs ou
par flots

On trouve des utilisations attestées par des documents historiques comme

par exemple

• Scytale à Sparte vers -450, (principe des codes de permutation).

• Code de Jules César vers -50, (principe des codes de substitution).

2.1 Codes à répertoire.

Ils consistent en un dictionnaire qui permet de remplacer certains mots par
des mots différents. Ils sont très anciens et ont été utilisés intensivement
jusqu’au début du 20-ième siècle. Ils ont fait l’objet d’une critique sévère de
A. Kerchkoffs dans son article fondateur.
On peut par exemple créer le dictionnaire suivant:

rendez-vous ↔ 175 demain ↔ oiseaux

midi ↔ à vendre Villetaneuse ↔ au marché

15
16 CHAPITRE 2. HISTORIQUE

La phrase en clair:

RENDEZ VOUS DEMAIN MIDI VILLETANEUSE

devient avec ce code

175 OISEAUX À VENDRE AU MARCHÉ

Il faut donc disposer de dictionnaires qui prévoient toutes les possibilités.

Donc, sauf si on se restreint à transmettre des informations très limitées, la
taille du dictionnaire s’accroit démesurément. Au 19e siècle on avait ainsi
pour des usages commerciaux ou militaires des dictionnaires de plusieurs
milliers de mots de codes. Tout changement du code nécessitait l’envoi de
documents volumineux avec un risque d’interception non négligeable.
Ces codes manquent de souplesse ils ne permettent pas de coder des mots
nouveaux sans un accord préalable entre l’expéditeur et le destinataire. Pour
cela il faut qu’ils échangent des documents ce qui accroı̂t le risque d’inter-
ception du code. Ils ne sont pas adaptés à des usages intensifs entre de
nombreux correspondants. Ils ne sont pratiquement plus utilisés pour les
usages publics. Par contre ils peuvent rendre des services appréciables pour
un usage unique.

2.2 Codes de permutation ou de transposition.

Dans les codes de permutation On partage le texte en blocs, on garde le
même alphabet mais on change la place des lettres à l’intérieur d’un bloc
(on les permute).
Un exemple historique dont le principe est encore utilisé est la méthode de
la grille (principe de la scytale utilisée par les spartiates vers -450 AJC).
On veut envoyer le message suivant:

RENDEZ VOUS DEMAIN MIDI VILLETANEUSE

L’expéditeur et le destinataire du message se mettent d’accord sur une grille

de largeur fixée à l’avance (ici une grille de 6 cases de large).
L’expéditeur écrit le message dans la grille en remplaçant les espaces entre
les mots par le symbole  . Il obtient:
2.2. CODES DE PERMUTATION OU DE TRANSPOSITION 17

R E N D E Z
 V O U S 
D E M A I N
 M I D I 
V I L L E T
A N E U S E
Il lit le texte en colonne et obtient ainsi le message crypté:

R
D
VAEVEMINNOMILEDUADLUESIIESZ
N
TEC

Pour pouvoir modifier le code rapidement sans toucher à son principe et

pouvoir ainsi augmenter la sécurité les deux interlocuteurs peuvent décider
l’ajout d’une clef.
Le but est de pouvoir changer facilement le cryptage d’un message tout
en gardant le même algorithme de codage. Pour cela on rajoute une clé
secrète constituée par l’ordre de lecture des colonnes.

Exemple 2.2.1. On choisit la clé: CAPTER

On numérote les colonnes en fonction du rang des lettres du mot CAPTER
dans l’alphabet c’est à dire

2, 1, 4, 6, 3, 5

et on lit les colonnes dans l’ordre indiqué.

EVEMINR
D
DADUADLUZ
 N
TENOMILEESIIES

On a 6! codes différents.
Pour décoder le message précédent on range en colonne sur la grille en
suivant l’ordre des colonnes donné par le mot de code

E R E D
V  V U
E D E A
=⇒ =⇒
M  M D
I V I L
N A N U
18 CHAPITRE 2. HISTORIQUE

R E N D E Z
 V O U S 
D E M A I N
 M I D I 
V I L L E T
A N E U S E

On a affaire à un code à clef secrète ou code symétrique car la clef de

décodage est la même que la clef de codage ou s’en déduit facilement.

Pour éviter d’allonger démesurement la hauteur de la grille et pour éviter

d’avoir à coder la totalité du message avant de commencer la transmission,
on travaille sur des blocs de taille m = k × ℓ où k est la largeur de la grille
et ℓ sa hauteur. On a alors un système de codage par blocs, symétrique ou
à clef secrète.

Pour des raisons de sécurité il ne faut pas que ℓ et k soient trop petits. Il
faut aussi compléter les blocs incomplets d’une manière qui ne diminue par
la sécurité du code.

2.2.1 Cryptanalyse des codes de permutation.

Si l’on ne dispose que d’un texte chiffré, on peut essayer d’attaquer ces codes
par force brute c’est à dire en essayant de manière exhaustive toutes les
permutations de colonnes possible. Rappelons qu’un calcul comportant plus
de 1080 opérations élémentaires est impraticable actuellement en un temps
raisonnable. Si la grille comporte n colonnes on aura n! permutations de
colonnes possibles.
 n n √
D’après la formule de Stirling n! ∼ 2πn, donc dès que le nombre de
e
colonne dépasse 50 on a plus de 1085 permutations et on est assuré qu’une
attaque par force brute est impraticable. Mais ce n’est pas la seule attaque
possible.

Il y a par exemple des attaques à texte clair choisi. On prend un message

constitué d’un seul 1 et complété par des zéros et de regarde le résultat
en faisant varier la place du 1. On en tire rapidement des informations
non-triviales sur la permutation.
2.3. CODES DE SUBSTITUTION 19

2.3 Codes de substitution.

Dans les codes de substitution par flots ou par blocs l’ordre des lettres
est conservé mais on les remplace par des symboles d’un nouvel alphabet
suivant un algorithme précis.
Exemple 2.3.1. Code de César :
Pour coder on remplace chaque lettre par son rang dans l’alphabet.

A=1, B=2, C=3,....,M=13, N=14,...,S=20,...,X=24, Y=25, Z=26

D’après Suetone, dans son ouvrage “Vie des douze Césars”, Jules César
pendant la guerre des Gaules avait utilisé le code de substitution par flot
suivant

lettre codée=lettre claire+3 modulo 26

Le message en clair

RENDEZ VOUS DEMAIN MIDI VILLETANEUSE

devient

UHQGHC YRXV GHPDLQ PLGL YLOOHWDQHXVH

On peut considérer toute la famille des codes

lettre codée=lettre claire+n modulo 26

où n est un entier entre 0 et 25 appelé la clef du code.

Avec la clef n = 7 le texte codé du message précédent devient:

YLUKLG CVBZ KLTHPU TPKP CPSSLAHULBZLBZL

Le décodage se fait en utlisant la relation

lettre claire=lettre codée -n mod 26

On a affaire à un code en continu ou par flots symétrique ou à clef

secrète.
20 CHAPITRE 2. HISTORIQUE

2.3.1 Cryptanalyse des codes de substitution.

Un code substitution comme le code de César ne résiste pas à une attaque
à texte chiffré connu. On considère un message codé avec une substitution
monoalphabétique:

JTVMNKKTVLDEVVTLWTWITKTXUTLWJERUTVTWTHDXATLIUNEWV.
JTVIEVWELOWENLVVNOEDJJTVLTPTXYTLWTWUT
SNLITTVQXTVXUJXWEJEWTONKKXLT.

Décodage par analyse de fréquence, cette méthode a été mise au point

au moyen âge par des lettrés arabes.
Analyse de fréquence

Lettre % français % texte Lettre % français % texte

A 9,4 1 N 7,2 5
B 1,0 0 O 5.1 2,5
C 2,6 0 P 2,9 1
D 3,4 2,5 Q 1,1 1
E 15,9 8 R 6,5 1
F 1 0 S 7,9 1
G 1 0 T 7,3 20
H 0,8 1 U 6,2 4,5
I 8,4 3,8 V 2,1 12
J 0,9 5,1 W 0 9,9
K 0 4,7 X 0,3 6
L 5,3 9 Y 0,2 1
M 3,2 1 Z 0,3 0

On peut donc faire l’hypothèse que T=E puis que V=S (à cause des lettres
doublées) puis que les voyelles A, I, O, U correspondent à D,E, N, X et
finalement on obtient la correspondance

A B C D E F G H I J K L M
D R O I T S H M E F G J K
N O P Q R S T U V W X Y Z
L N P Q U V W X Y Z A B C

Exercices. 1
2.3.1. Le message suivant a été codé avec un code de César, décodez-le.

YN PHEVBFVGR RFG HA IVYNVA QRSNHG

2.4. LE CODE DE VIGÉNÈRE 21

2.3.2. On choisit un alphabet à M ≥ 2 lettres, on associe à chaque lettre de

l’alphabet un entier entre 0 et M − 1. Un code affine sur cet alphabet est
un code dont la fonction de codage est

E :Z/M Z −→ Z/M Z
x 7−→ ax + b

avec a (mod M Z) et premier à M , b (mod M Z). On suppose qu’on utilise

l’alphabet latin avec 26 lettres. On considère le code affine avec M = 26,
a = 7, b = 5. Codez avec ce code le texte:
IL SEMBLERAIT BIEN QUE CE TEXTE AIT UNE SIGNIFICATION.
LE TOUR EST DONC JOUE
2.3.3. Le message suivant a été codé avec le code affine associé à l’alphabet
latin, M = 26:
NMDUGXP IDIIDHX AKVAVPD ZQX NKTAUAQDGTPX SZ
NMRCCKXLXQU SX ERHXQXKX IDPXX PZK GD KXAXURURVQ
SX GD NGX.
Décodez-le.

2.4 Le code de Vigénère.

La faiblesse des codes de César et des systèmes analogues est que la fré-
quence des lettres est conservée ce qui permet une cryptanalyse aisée par
analyse de fréquences.
Pour améliorer la sécurité on peut faire un code de César par blocs dans
lequel on change de substitution pour chaque lettre d’un bloc. On obtient
ainsi le code de Vigénère, mis au point par Leon Batista Alberti au 15-
ième siècle et développé par Blaise de Vigénère:

• On se fixe une longueur de bloc m.

• On découpe le message en blocs de m-lettres.
• On chiffre par blocs de m lettres. On décide par exemple que la
première lettre d’un bloc de m est codée avec un code de César de
clef n1 , la deuxième avec un code de César de clef n2 et la m-ième par
un code de César de clef nm .
22 CHAPITRE 2. HISTORIQUE

Très sûrs pendant plusieurs siècles, ces codes ont été cryptanalysés officielle-
ment par Charles Babbage et Friedrich Wilhelm Kasiski au 19-ième siècle.
Le code de César est un code monoalphabétique. Le code de Vigénère
est un code polyalphabétique ou par blocs.
Exemple 2.4.1. m = 5, n1 = 3, n2 = 14, n3 = 7, n4 = 22, n5 = 19, le
message en clair est:
n
M = Ce système de codage n’est pas sûr, mais plus que le code de César si
o
la clé est longue .
on partage en blocs de taille 5 en partant de la gauche

CESYS TEMED ECODA GENES TPASS URMAI SPLUS QUELE

CODED ECESA RSILA CLEES TLONG UEXXX

Les XXX ont été ajoutés pour compléter le dernier bloc. La manière de
compléter le dernier bloc peut être une faiblesse du code. Dans chaque
bloc on code la première lettre avec le code de César de clef n1 = 5,..., la
cinquième lettre du bloc avec le code de César de clef n5 = 19. Le message
codé devient:

e(M )= FSZUL WSTAW HQVZT JSUAL WDHOL XFTWB VDSQL

TILHX FCKAW HQLOT UGPHT FZLAL WZVJZ XSETQ

2.4.1 Cryptanalyse des codes de Vigenère.

La cryptanalyse du cryptosystème de Vigénère peut se faire à texte chiffré
connu si le message est assez long, cf. le chapitre 1.4. On remarque que
des répétitions de lettres assez longues (en général on cherche des triplets
ou trigrammes) doivent correspondre dans le texte clair à des répétitions
de lettres aussi. Ceci permet de majorer la taille de la clé. On se ramène
alors à la cryptanalyse d’un chiffrement de César. Cette cryptanalyse a été
mise au point au 19e siècle.
Ici compte tenu de la faible longueur du texte on ne trouve que les doublets
ou digrammes AW et AL éloignés de 40 lettres et 45 lettres dont le PGCD
est 5 ce qui suggère une clef de longueur 5.
Une fois que l’on a déterminé la longueur de la clef, le décodage est le même
que celui de 5 codes de César.
2.4. LE CODE DE VIGÉNÈRE 23

Exercices. 1
2.4.1. Indice de coı̈ncidences Étant donné une suite x = x1 x2 . . . xn de
caractères xi d’un alphabet Z on définit le nombre nc d’indices i tels que
xi = c et l’indice de coı̈ncidences, I qui est la probabilit pour que deux
caractres de la suite x soient identiques
I = Pr [xK = xL I < J]
K,J

où K et L des variables aléatoires indépendantes sur {1, . . . , n} équidistri-

buées.
X nc (nc − 1)
1. Montrer que I = .
n(n − 1)
c∈Z

2. Montrer que l’indice de coincidence est invariant quand on substitue

l’alphabet Z ′ à l’alphabet Z.
3. Montrer que l’on peut utiliser l’indice de coı̈ncidences pour faire une
cryptanalyse du code de Vigenère si l’on connait une borne supérieure
de la taille des blocs.
2.4.2. On associe à chaque lettre de l’alphabet latin son ordre compris entre
0 et 25. Le message suivant a été codé avec un code de Vigénère associé à
l’alphabet latin:
CS AZZMEQM, CO XRWF, CS DZRM GFMJECV. X’IMOQJ JC LB
NLFMK CC LBM WCCZBM KFIMSZJSZ CS URQIUOU. CS ZLPIE
ECZ RMWWTV, SB KCCJ QMJ FCSOVJ GCI ZI ICCKS, MK QMLL
YL’CV ECCJ OKTFWTVM JIZ CO XFWBIWVV, IV ACCI CC
C’OCKFM, JINWWB U’OBKSVUFM.
Décodez-le.
2.4.3. Le chiffrement de Hill. Ce cryptosystème généralise celui de Vigé-
nère. Il a été publié par L. S. Hill en 1929.

• On choisit un alphabet de n lettres (on prendra dans nos exemples

n = 26) et une taille m pour les blocs, par exemple m = 2. Alors
P = E = (Z/26Z)2 , (en général (Z/nZ)2 ).
• La clef de codage est une matrice inversible K ∈ GLm (Z/nZ), si n = 26
et m = 2  
a b
K= ∈ GL2 (Z/26Z)
c d
24 CHAPITRE 2. HISTORIQUE

2
Si (x1 , x2 ) ∈ Z/26Z est le message clair alors le message codé sera:
 
a b
(y1 , y2 ) = eK ((x1 , x2 )) = (x1 , x2 ) = (ax1 + cx2 , bx1 + dx2 )
c d

La clé de déchiffrage est la matrice inverse de K dans GLm (Z/nZ).

   
11 8 −1 7 18
Par exemple avec m = 2 et K = alors K = .
3 7 23 11
Comme pour le code de César on peut considérer des codes de Hill affines
constitués d’une matrice de GLm (Z/nZ) et d’un vecteur V de (Z/nZ)m .
L’algorithme de codage est donné par

M 7−→ KM + V

où M est un bloc de taille m du message clair identifié à un vecteur de

(Z/nZ)m .

2.4.4. Montrer que le chiffrement de Hill ne résiste pas à une attaque à texte
clair choisi.
2.4.5. 1. En utilisant la correspondance

Alphabet −→ Z/26Z = {0, 1, . . . , 25}

Numériser le texte ci-dessous (du moins une partie)

Des chercheurs tentent de visualiser des raisonnements

mathématiques dans les émotions comme la honte ou la compassion.

2. Chiffrer le message précédent avec une méthode par décalage de clef

7.

3. Chiffrer le message avec une méthode par substitution en utilisant la

clef k : Z/26Z → Z/26Z définie par

8λ + 1 si λ 6= 7 et 25

k(λ) = 0 si λ = 7


8 si λ = 25

Donner la fonction réciproque de k.

4. Chiffrer le message avec une méthode de Vigénère de clef k = (2; 19).

2.5. COMMENTAIRES HISTORIQUES 25

2.4.6. (Cryptanalyse par analyse de fréquence). On considère le message

chiffré avec une méthode de substitution.

eohokrilppofoyvkesfivsglomihisvsyoelkvije
ooyhiswzyqowgliyvsvowqoxicioppovqowohhohoeikroowmih
eikvsasvorlfisyoqomlsweoqojlvqoeohosyqlwvhsoeeoeovi
lnqoxickihjzysgloowvisywsmiwwoqoqolnkoyvglivhoasyxvm
mfoyfseeowomvkoyvksygliyvoivhzswkoyvwzsniyvommfiltzlh
qrlsoveoqohysohhimmzhvqlxhzlmoqonmohvwsyvohxzlaohyofo
yviewlheoazelvszyqlkesfivmhoazbisvoyqolnfseeolyglokov
ilnmzlhhisvivvosyqhoksygkoyvglihiyvoiyolpkoyvmmfqsksi

1. Donner le tableau des fréquence des lettres, et des fréquences des bi-
grammes les plus fréquents.

2. En déduire la clef de chiffrement et le message clair correspondant.

2.5 Commentaires historiques.

Les méthodes historiques pour authentifier un message se retrouvent dans
les cryptosystèmes modernes
On utilisait des messagers qui devaient échanger des signes de reconnaissance
convenus (phrase de reconnaissance, lettres d’introduction, etc..) avec le
destinataire pour authentifier le messager, l’expéditeur ou le destinataire,
afin déviter les faux messages.
Pour éviter la falsification du message on le mettait dans une enveloppe
scellée revétue de cachets, le message lui-même était signé, l’écriture permet-
tait elle aussi l’authentification du message, etc...
Le destinataire pouvait parfois accuser réception en guise de protocole de
non répudiation.
La cryptanalyse a été pratiquée depuis la plus haute antiquité. Le code de
César a été cryptanalysé par les lettrés arabes du 9-ième siècle; Al Kindi a
décrit la méthode de l’analyse statistique.
Tous les rois avaient leurs cryptographes-cryptanalystes (les Rossignol pour
Louis XIV) et leur cabinet noir.
26 CHAPITRE 2. HISTORIQUE

Les rapports entre cryptographie et cryptanalyse sont analogues aux rap-

ports entre blindage et artillerie. Le code de César a tenu 9 siècle, celui de
Vigenère a tenu 4 siècles, le standard DES a tenu 20 ans. le standard RSA
est en passe d’être supplanté par les codes elliptiques.
Les codes modernes.

Tout d’abord nous donnons une description un peu formelle d’un cryptosys-
tème. Nous décrirons au chapitre 6, 7, 8, 9, des cryptosystèmes réels.
Définition 4.0.1. Un cryptosystème est un dictionnaire entre les messages
en clair et les messages chiffrés.

Afin de travailler efficacement sur les codes et définir de manière quantitative

leur sécurité on est amené à les modéliser et donc à définir de manière
axiomatique un cryptosystème:
Définition 4.0.2. Formellement un cryptosystème est un quintuplet
(P, C, K, E, D)
où
• P est un ensemble fini de blocs : les mots en clair
• C est un ensemble fini de blocs: les mots codés
• K est un ensemble : l’ espace des clefs
• Pour tout K ∈ K on a une règle de chiffrement eK ∈ E et une règle
de déchiffrement correspondante dK ∈ D. Chaque eK : P → C et
dK : C → P sont des fonctions telles que dK (eK (x))) = x pour tout
x∈P
Pour chaque K ∈ K (la clef du code) la transformation eK est appelée le
procédé de chiffrement, ou l’ algorithme de codage, entre les textes
en clair P et les textes codés C.
La fonction inverse dK de eK est appelée la fonction de décodage.
On exige que tout message codé puisse être décodé.

35
36 CHAPITRE 4. LES CODES MODERNES

Un code moderne est donc constitué

• D’un algorithme de chiffrement f = fKC , supposé connu de tous,

dépendant d’un paramètre KC , la clé de chiffrement. L’algorithme est
fixé et public, seule la clé change, (on applique le principe de Kerck-
hoffs).

• De la valeur de la clé de chiffrement, KC qui est secrète ou non suivant

que l’on a affaire à un code à clef secrète ou à un code à clef publique.

• D’un algorithme de déchiffrement g = gKD = f −1 (supposé connu de

tous) dépendant d’une clé de déchiffrement, KD , différente ou non de
KC .

• De la valeur de la clé de déchiffrement, KD , qui est toujours secrète.

4.1 Objectifs des codes actuels.

Rappelons les qualités attendues d’un cryptosystème, [Link] 1.3. Tout

d’abord les qualités fonctionnelles:

1. Confidentialité des données: Les messages ne peuvent être déchif-

frés que par le destinataire.

2. Intégrité des données: Ils ne peuvent être modifiés par un tiers non
autorisé.

3. Authentification: L’identité des différents participants peut être

vérifiée.

4. Non-répudiation: L’expéditeur ne peut nier avoir émis le message

et le destinaire ne peut nier l’avoir reçu.

Ensuite les qualités pratiques

1. Il doit résister aux attaques connues et si possible avoir une sécurité

prouvée.

2. Il doit permettre de coder et décoder rapidement (en temps réel pour

certaines applications).

Il n’existe pas de codes qui réunissent toutes ces qualités simultanément. Il

faut donc un compromis adapté à chaque situation.
4.2. LES FAMILLES DE CODES MODERNES 37

4.2 Les familles de codes modernes.

Les principales familles de codes modernes sont

• Les codes par flot (registres à décalage)


les codes symétriques (ou à clé secrète).
• les codes par blocs
les codes asymétriques (ou à clé publique)
Les codes à clef publique sont basés sur la notion de fonction à sens unique
définie au chapitre 4.4.

4.3 Codes symétriques.

Les principes des codes symétriques commerciaux modernes du type DES

(Data Encrytion Standard), cf. chapitre 8, ont été mis au point dans les
années 1970 par IBM avec l’aide de la NSA (National Security Agency), ce
sont des hybrides de codes de substitutions et de codes de transpositions
basés sur un schéma de Feistel.
Ils restent très sûrs avec des clés assez courtes de 128 bits à 256 bits. Leur
sûreté est non prouvée. Leur cryptanalyse a fait des progrès (cryptanalyse
linéaire et différentielle), ce qui permet de mieux cerner leur sûreté.
Les codes à clé secrète sont les plus employés actuellement car ils sont
éprouvés, résistants, rapides et assez facile à mettre en oeuvre. Actuellement
leur sécurité est garantie (mais non prouvée) avec des clés assez courtes de
128 à 256 bits pour le standard actuel AES.
Mais il faut échanger la clé secrète avec le destinataire d’où un risque. Ils
nécessitent un grand nombre de clés. Il faut

n(n − 1)
2
clés pour que n interlocuteurs puissent échanger des informations d’où un
problème de fabrication et d’échange de clefs fiables.
Ils ont du mal à réaliser sans tiers de confiance le partage des clefs, la
signature, l’authentification, et la non répudiation des messages transmis.
Ils s’adjoignent parfois un code asymétrique pour cela comme dans le cryp-
tosystème PGP .
La génération actuelle de codes symétriques est le cryptosystème AES, décrit
au chapitre 8, développé dans les années 2000 à la suite d’un appel d’offre
38 CHAPITRE 4. LES CODES MODERNES

international par John Daemon et Vincent Rijmen, [8]. Il utilise dans sa

conception nettement plus de mathématiques que son prédécesseur le DES,
ce qui permet une meilleure appréhension de sa sécurité.

4.4 Codes asymétriques.

Les principes des codes asymétriques ont été mis au point par Diffie et
Hellman en 1976. Ils ont dégagé la notion de fonction à sens unique.
Ce sont des fonctions qui sont faciles à calculer c’est à dire calculable en
temps polynomial en fonction de la taille des données mais tel que l’image
réciproque (les antécédents) d’un élément soit très difficile à calculer ex-
plicitement au moins calculatoirement, c’est à dire que le temps de calcul
soit prohibitif, voir la sous-section 13.2.3 et suivants. Autrement dit on de-
mande que la fonction inverse ne soit pas calculable en temps polynomial en
fonction de la taille des données.
Le premier exemple de fonction à sens unique du à Diffie, Hellmann et Merkle
était basée sur le problème du sac à dos, cf. section 9.2 page 99, dont il avait
été démontré qu’il appartenait à la classe des problèmes de type NP (NP
pour Non Polynomial), autrement dit il existe des instances (des réalisations)
de ce problème qui sont dans la classe N P (c’est un théorème). Attention
cela ne veut pas dire que toutes les instances de ce problème sont
de type N P .
Un problème de la classe NP est un problème dont la solution exige un
calcul en temps non polynomial en fonction de la taille des données, sous
réserve de la validité de la conjecture P6= NP, cf. la sous-section 13.2.2.
On peut donc espérer qu’il permette de fabriquer un cryptosystème offrant
une sécurité calculatoire élevée.
Malheureusement les instances connues du problème du sac à dos ne sont
pas de type NP. En particulier les réalisations pratiques de Diffie, Hellmann
et Merkle utilisaient des sacs à dos qui n’étaient pas dans la classe NP.
Leur cryptosystème a succombé à l’attaque des cryptanalystes (en particulier
Shamir).
Dans la solution suivante, 1978, le cryptosystème RSA (Rivest-Shamir
et Adleman) décrit au chapitre 9, la fonction à sens unique sous-jacente est
la multiplication des entiers qui appartient à la classe P (P pour Polynomial)
des problèmes polynomiaux en temps. Sa fonction réciproque la fac-
torisation des entiers est actuellement dans la classe NP des problèmes
non polynomiaux en temps, c’est un fait d’expérience pas un théorème.
4.5. LES ÉCHANGES DE CLEFS 39

D’autres solutions sont apparues peu après:

• le sytème El Gamal, cf. chapitre 9, qui repose sur l’exponention dans

Z/pZ avec p premier et sur l’application inverse qui est le logarithme
discret,

• les codes basés sur les courbes elliptiques. Ils reposent sur la
structure de groupe des points des courbes elliptiques sur un corps fini
cf. chapitre 9.

Les cryptosystèmes asymétriques reposent sur des structures mathématiques

élaborées. Leur sûreté est bonne mais non prouvée. Leur cryptanalyse
dépend beaucoup des progrès des mathématiques correspondantes.
Sauf pour les codes elliptiques, ils nécessitent des clés longues (1024 à 2048
bits) pour avoir une sûreté équivalentes à celle d’un cryptosystème à clef
secrète de 128 à 256 bits. Ils sont 1000 à 1500 fois plus lents. Mais ils
permettent de réaliser facilement les fonctionnalités suivantes

• partage des clefs,

• authentification

• intégrité

• non répudiation

et bien d’autres encore grâce au fait que la clef est en fait constituée de
deux clefs, la clef de codage et la clef de décodage, et que cette dernière est
attachée à une personne et la caractérise.
Ils ne nécessitent que n paires de clés (une clé secrète et une clé publique)
pour n interlocuteurs.
On les utilise souvent pour la transmission des clés secrètes des codes symé-
triques.