Histoire de la cryptographie

Frederic Havet
MASCOTTE, commun I3S(CNRS/UNSA)-INRIA Sophia Antipolis
Fete de la science 21-24 octobre 2010
Messages secrets
Depuis lAntiquite, on cherche `a envoyer des messages sans que
des personnes exterieures ne puissent les intercepter.
Le plus vieux document chire date du XVI
e
si`ecle avant J. C.
Deux mani`eres complementaires de faire:

STEGANOGRAPHIE: cacher le mesage pour que lennemi ne

le trouve pas.

CRYPTOGRAPHIE: rendre le message incomprehensible par

lennemi.
Chire des Hebreux
V
e
si`ecle av. J.-C.: premi`eres techniques de chirement par les
Hebreux.
Plus connu Atbash pour aleph, tau, beth, shinest.
Chire par substitution alphabetique inversee.
A devient Z, B devient Y, C devient X, ...
A B C D E F G H I J K L M
Z Y X W V U T S R Q P O N
N O P Q R S T U V W X Y Z
M L K J I H G F E D C B A
JUTILISE ATBASH devient QFGRORHV ZGYZHS
Que veut dire QV XLNKIVMWH OSVYIVF ?
JE COMPRENDS LHEBREU
Chire des Hebreux
V
e
si`ecle av. J.-C.: premi`eres techniques de chirement par les
Hebreux.
Plus connu Atbash pour aleph, tau, beth, shinest.
Chire par substitution alphabetique inversee.
A devient Z, B devient Y, C devient X, ...
A B C D E F G H I J K L M
Z Y X W V U T S R Q P O N
N O P Q R S T U V W X Y Z
M L K J I H G F E D C B A
JUTILISE ATBASH devient QFGRORHV ZGYZHS
Que veut dire QV XLNKIVMWH OSVYIVF ?
JE COMPRENDS LHEBREU
Chire de Cesar
Cesar utilisait un chirement par decalage. Chaque lettre est
remplacee par la lettre decalee de k dans lalphabet.
Cesar decalait toutes les lettres de 3. Ainsi A devient D, B devient
E, ...., X devient A, Y devient B et Z devient C.
JE CHIFFRE PAR DECALAGE se code
MH FKLIIUH SDU GHFDODJH
Que veut dire IDFLOH D OLUH OH FRGH GH FHVDU?
FACILE A LIRE LE CODE DE CESAR
Chire de Cesar
Cesar utilisait un chirement par decalage. Chaque lettre est
remplacee par la lettre decalee de k dans lalphabet.
Cesar decalait toutes les lettres de 3. Ainsi A devient D, B devient
E, ...., X devient A, Y devient B et Z devient C.
JE CHIFFRE PAR DECALAGE se code
MH FKLIIUH SDU GHFDODJH
Que veut dire IDFLOH D OLUH OH FRGH GH FHVDU?
FACILE A LIRE LE CODE DE CESAR
Inconvenients et avantages du chirement par decalage
Peu s ur: Si on sait que le chirement est par decalage alors on
peut retrouver le message: il ny a que 25 possibilites de decalage.
Simple: Tr`es simple `a utiliser et `a se rappeler.

ociers sudistes pendant la Guerre de Secession.

larmee russe en 1915.

de nos jours sur les forums internet: ROT13 (decalage de 13

lettres). But est dempecher la lecture involontaire: (dune
reponse `a une devinette, de la n dun lm, ...).
Chirement par substitution mono-alphabetique
Remplacement dune lettre par une autre suivant une table.
Exemple: Atbash
A B C D E F G H I J K L M
Z Y X W V U T S R Q P O N
N O P Q R S T U V W X Y Z
M L K J I H G F E D C B A
Exemple: ROT-13
A B C D E F G H I J K L M
N O P Q R S T U V W X Y Z
N O P Q R S T U V W X Y Z
A B C D E F G H I J K L M
Chirement par substitution mono-alphabetique
On peut utiliser dautres tables plus compliquees.
A B C D E F G H I J K L M
R H N Y C Q F U W A J O Z
N O P Q R S T U V W X Y Z
X M K S I T G P E D V B L
KRT QRNWOC YC TC IRKKCOCI PXC GCOOC GRHOC.
PAS FACILE DE SE RAPPELER UNE TELLE TABLE.
Avantage: il y a 26! 10
27
tables possibles.
Inconvenient: table est dicile `a se rappeler.
Chirement par substitution mono-alphabetique
On peut utiliser dautres tables plus compliquees.
A B C D E F G H I J K L M
R H N Y C Q F U W A J O Z
N O P Q R S T U V W X Y Z
X M K S I T G P E D V B L
KRT QRNWOC YC TC IRKKCOCI PXC GCOOC GRHOC.
PAS FACILE DE SE RAPPELER UNE TELLE TABLE.
Avantage: il y a 26! 10
27
tables possibles.
Inconvenient: table est dicile `a se rappeler.
Chirement par substitution mono-alphabetique
On peut utiliser dautres tables plus compliquees.
A B C D E F G H I J K L M
R H N Y C Q F U W A J O Z
N O P Q R S T U V W X Y Z
X M K S I T G P E D V B L
KRT QRNWOC YC TC IRKKCOCI PXC GCOOC GRHOC.
PAS FACILE DE SE RAPPELER UNE TELLE TABLE.
Avantage: il y a 26! 10
27
tables possibles.
Inconvenient: table est dicile `a se rappeler.
Analyse frequentielle
Decouverte au IX
e
si`ecle par Al-Kindi.
Idee: examiner la frequence des lettres dun message chire.
En eet, la frequence depend de la lettre :
A B C D E F G H I J K L M
9,4 1,0 2,6 3,4 15,9 0,9 1,0 0,8 8,4 0,9 0,0 5,3 3,2
N O P Q R S T U V W X Y Z
7,1 5,1 2,8 1,0 6,5 7,9 7,3 6,2 2,1 0,0 0,3 0,2 0,3
On a lordre suivant:
E,A,I,S,T,N,R,U,L,O,D,M,P,C,V,Q,G,B,F,J,H,Z,X,Y,K,W
Decoder par analyse frequentielle
Pour decoder un texte chire par substitution, on fait une analyse
de frequences sur les lettres.
La lettre la plus frequente est tr`es certainement le E, la deuxi`eme
le A, la troisi`eme le I, etc ....
Attention: inversion possible dans lordre. Surtout pour des lettres
de frequences proches et le texte court.
En general, cela permet didentier les lettres les plus frequentes.
On peut ensuite deviner les autres,...
Analyse de frequences sur les bigrammes = bloc de deux lettres
dans un mot. Les plus courants sont ES 3,15%, LE 2,46%, EN
2,42%, DE 2,15%, RE 2,09%, NT 1,97%, ...
Analyse frequentielle et Scrabble
A B C D E F G H I J K L M
9,4 1,0 2,6 3,4 15,9 0,9 1,0 0,8 8,4 0,9 0,0 5,3 3,2
N O P Q R S T U V W X Y Z
7,1 5,1 2,8 1,0 6,5 7,9 7,3 6,2 2,1 0,0 0,3 0,2 0,3
Voici les lettres du scrabble avec leur points ainsi que leur nombre
dans le jeu.
A
1
B
3
C
3
D
2
E
1
F
4
G
2
H
4
I
1
J
8
K
10
L
1
M
2
9 2 2 3 15 2 2 2 8 1 1 5 3
N
1
O
1
P
3
Q
8
R
1
S
1
T
1
U
1
V
4
W
10
X
10
Y
10
Z
10
6 6 2 1 6 6 6 6 2 1 1 1 1
Repartition des lettres du premier Scrabble vient dune analyse
frequentielle du New York Times.
Sherlock Holmes et lanalyse frequentielle
Les Hommes dansants (The Adventure of the Dancing Men)
De curieux gribouillages apparaissent dans la propriete des Cubitt.
Holmes dechire le code de ces gribouillages grace `a lanalyse
frequentielle.
Indice de concidence
Introduit par W. Friedman en 1920.
IC mesure la probabilite de trouver une paire de lettres identiques.
IC =
q=Z

q=A
n
q
n

n
q
1
n 1
avec n nombre total de lettres,
n
A
nombre de A, n
B
nombre de B, ...
Ce nombre ne varie pas apr`es substitution mono-alphabetique.
Francais: 0,0778 Anglais: 0,0667 Russe: 0,0529
Aleatoire: 1/26 = 0,0385
Chirement par substitution poly-alphabetique
XVI
e
si`ecle

1518: JeanTrith`eme Polygraphiae

1553: Giovan Battista Bellaso La Cifra

1563: Giambattista della Porta De Furtivis Literarum Notis,

vulgo de ziferis

1586: Blaise de Vigen`ere Traicte des chires ou secr`etes

mani`eres descrire
Principe: Cle litterale qui indique le decalage `a appliquer.
Chire de Vigen`ere
Cle que lon rep`ete `a linni indique le decalage.
Exemple: ABCD la cle.
Texte P R E N O N S U N E X E M P L E
Cle A B C D A B C D A B C D A B C D
Chire Q T H R P P V Y O G A I N R O I
Avantages:

Simple.

Resiste `a lanalyse frequentielle.

Cryptanalyse du chire de Vigen`ere
Charles Babbage (?) 1854
Friedrich Wilhelm Kasiski 1863: Test permettant destimer la taille
de la cle base sur les ecarts entre les sequences redondantes.
Une fois la taille de la cle trouvee: analyse frequentielle pour
chaque lettre de la cle.
Victoires de la cryptanalyse
1ere Guerre mondiale: Les Fran cais decryptaient les messages pour
les sous-marins allemands.
2nde Guerre Mondiale: Les Britanniques ont pu decrypter les
communications de larmee allemande.
Machine Enigma: substitutions poly-alphabetiques avec
changement de cle permanent cree par des rotors.
On estime `a plusieurs mois (voir annees) lecourtement de la
Guerre.
Chire de Vernam ou masque jetable
Cree par par Gilbert Vernam en 1917 et perfectionne par Joseph O.
Mauborgne.
Principe: Substitution poly-alphabetique avec une cle particuli`ere.

Cle aussi longue que le message `a chirer.

Les caract`eres de la cle doivent etre aleatoires.

Chaque cle (masque) doit avoir une utilisation unique

(jetable).
Chire de Vernam ou masque jetable
Avantage: Theoriquement s ur et simple `a coder/decoder.
Inconvenient: Diculte de la mise en place.

Transmission de la cle dicile valise diplomatique.

Generation de cle aleatoire impossible nombres

pseudo-aleatoires. (risque de faille).

Utilisation imperativement unique. Si on a deux messages

codes avec la meme cle on peut tr`es souvent les decoder.
Reste cependant tr`es utilise: ambassades, telephone rouge.
Syst`emes `a cles publiques
Grand progr`es: syst`emes `a cles publiques.
Caracteristiques principales:

simplicite;

cle publique;

diculte `a briser le code.

Idee proposee en 1976 par Die & Hellman.
Creation du premier syst`eme en 1978 par Rivest, Shamir &
Adleman: le crypto-syst`eme RSA
Crypto-syst`eme RSA
Une personne Alice veut recevoir un message dune autre personne
Bob.
Le crypto-syst`eme RSA comprend 3 etapes.
1. Choix de la cle et sa publication par Alice.
2. Chirement du message par Bob et envoi.
3. Dechirement du message par Alice par cle privee.
Choix de la cle RSA
Alice choisit deux grands entiers naturels premiers p et q (100
chires chacun ou plus) et fait leur produit n = pq.
Puis elle choisit un entier e premier avec (p 1)(q 1).
Enn, elle publie dans un annuaire, par exemple sur le web, sa cle
publique RSA: (n, e).
Exemple: p = 53, q = 97 donc n = 5141 et e = 7.
Chirement RSA

Bob va chercher la cle dAlice: (n, e).

Il transforme son message. Par exemple, il remplace chaque

lettre par son rang dans lalphabet.
JEVOUSAIME devient : 10 05 22 15 21 19 01 09 13 05.

Il coupe son message en blocs de meme longueur, chacun

representant un nombre plus petit que n.
Attention: Les blocs doivent etre assez longs sinon lanalyse
frequentielle sapplique.
Son message devient : 010 052 215 211 901 091 305

Chaque bloc B est chire par la formule C = B

e
mod n, o` u
C est un bloc du message chire que Bob enverra `a Alice
Message chire: 0755 1324 2823 3550 3763 2237 2052. .
Dechirement RSA
Alice calcule `a partir de p et q, quelle a gardes secrets, la cle d de
dechirage (cest sa cle privee).
d doit satisfaire e d mod ((p 1)(q 1)) = 1. Ici, d=4279.
Chacun des blocs C du message chire est dechire par la formule
B = C
d
mod n.
Alice retrouve : 010 052 215 211 901 091 305
Principe de RSA

Il est facile de multiplier deux grands nombres premiers.

Il est tr`es dicile de determiner les facteurs premiers dun

grand nombre.
Il est actuellement impossible pour certaines categories de
nombres defactoriser ceux de plus de 300 chires.
RSA est partout
Plusieurs centaines de millions de programmes lutilisent.

transactions securisees sur internet;

syst`emes dexploitation (Apple, Microsoft, Sun);

condentialite du courrier electronique;

tr`es grand nombre dinstitutions.

Securite de RSA
Theoriquement elle est basee sur 2 conjectures:
1. casser RSA necessite la factorisation du nombre n en le
produit initial des nombres p et q.
2. avec les algorithmes classiques, le temps que prend cette
factorisation croit exponentiellement avec la longueur de n.
Pratiquement RSA a resiste `a toutes les attaques depuis 30 ans.
Quelques precautions
Cles longues: 256 bits se fait en quelques heures sur 1 PC.
768 bits plus grands nombres factorises.
Des experts estiment des cles de 4096 bits sont sures.
Autres precautions:

Prendre p et q de taille proche.

Eviter que p + 1, p 1, q 1 et q + 1 soient faciles `a

factoriser.

Prendre e susamment grand (>

4

n)
Faiblesse de RSA
Les conjectures sur lesquelles reposent la securite de RSA sont
peut-etre fausses.
Ordinateurs quantiques:
Algorithme de Shor: algorithme quantique pour factoriser un
nombre n en temps O((log n)
3
) et en espace O(log n).
En 2001, par un groupe dIBM, factorisa 15 en 3 et 5, en utilisant
un calculateur quantique de 7 qubits.