Introduction à la cryptographie

Introduction á la cryptographie

Jean Goubault-Larrecq
LSV, ENS Cachan

9 octobre 2013

RÉsumÉ
On prsente quelques bases de cryptographie. Ceci est la version 2 du 09 oc-
tobre 2013. La version 1 datait du 07 novembre 2012.

1 Introduction
Le but de la cryptographie est d’assurer la scurit des changes de messages en
prsence d’un ou plusieurs attaquants, ou intrus, potentiels.
On notera typiquementMle message en clair,Kune cl,{M}Kle messageM
chiffr parK,Il’intrus.
On cherchera á assurer despropriÉtÉsde scurit par desmoyensalgorithmiques :

Proprit
Secret
Authenticit
Intgrit

Moyen
chiffrement{M}K
signature[M]K
hachageh(M), MACh(M, K)

Ine peut pas reconstruire/rien dduire du clairM
Ine peut pas se faire passer pour l’metteur deM
Ine peut pas modifierMsans que ceci ne soit dtect

Et il y a bien d’autres proprits :
– distributionde cls (protocole de Diffie-Hellman)
– ene-commerce : non-duplication (factures), non-rpudiation (commandes) ;
– envote lectronique : ligibilit (du votant), anonymat (du vote), absence de
reÇu, non-coercition, vrification individuelle (du vote par le votant), vrification
des dcomptes (des votes) ;
– preuvesá connaissance nulle, secrets partags, etc.

2 Lesanciennes mÉthodes de chiffrement
M=a0a1. . . an−1: mot surΣ(alphabet, ensemble fini de lettres)={0,1, . . . , k−
1}.
– Csar(∼ −50) :K∈Σ,{M}K= (a0+Kmodk)(a1+Kmodk). . .(an−1+
Kmodk).

1

m
– Vigenre(∼1550) :K=b0b1. . . bm−1∈Σ,{M}K= (a0+b0modk)(a1+
b1modk). . .(an−1+bn−1modmmodk).
m
– Masque jetable (one-time pad; Vernam,1926) :K=b0b1. . . bn−1∈Σ,
{M}K= (a0+b0modk)(a1+b1modk). . .(an−1+bn−1modk).
Diffrence entre Vigenre et masque jetable :mfixe dans le premier,m=ndans le
second.
Csar facile á casser (AlKindi,∼850) : les lettres les plus frquentes en franÇais
sont E>A>I>S, T, etc. (Analysestatistique). De plus, il y a peu de cls.
Vigenre presque aussi facile á casser : revient ámchiffrements de Csar indpen-
dants (si l’on connatmon peut retrouver) ;mavec forte probabilit (Babbage1854,
Kasiski1863) en calculant le pgcd des distances entre sous-mots identiques dans le
chiffr.
A l’oppos, le masque jetable estinconditionnellement sÛr(á condition de tirer la
clau hasard, uniformment : ne pas partager la cl avec d’autres, de ne pas mgoter
sur la longueur de la cl, ne pas rutiliser la cl). En rsum, aucune analyse statistique
ne permet de retrouver le clair :
ThÉorÈme 2.1Pour le chiffrement par masque jetable, la distribution des clairsM,
mme connaissant le chiffrÉ{M}Kest ladistribution uniforme:
1
0 0
P rK[{M}K=M|M] =.
|M|
|Σ|
0 0
DÉmonstration.âMfix, il y a bijection entreKet lesMtels que{M}K=M.
✷Attention, Ça demande á retirer la cl au hasard á chaque chiffrement. D’oÙ les
questions suivantes :
– Commentdistribue-t-on la cl aux deux acteurs qui veulent communiquer ? Une
solution : Diffie-Hellman, voir section 7.
– Commenttire-t-on une cl au hasard ? Voir section 8.

3 ThÉoriede l’information, entropie, et chiffrement
Shannon a fond la thorie de l’information dans le but d’tudier les possibilits de
compression de signaux, et de correction d’erreurs dans les transmissions de signaux
[1]. Les signaux, et le bruit qui s’y rajoutent, sont vus comme des variables alatoires.
La notion fondamentale dans ce domaine est celle d’entropied’une variable alatoire.
DÉfinition 3.1SoitXune variable alÉatoire (discrÈte) sur un ensemble finiA, et po-
sonspa=P r[X=a](laloideX). L’entropiedeXest :
X
H(X) =−palogpa.
a∈A
n
Le logarithme est prisen base2:=log 2n. (On noteralnxle logarithme nprien
dex.)

2

3.1 Compression
L’intrt de la notion d’entropie est sans doute le plus clair en matire d’algorithmes
de compression (ce que Shannon appelle un canal non bruit, ou uncode) : pour tout
∗ ∗
M∈Σ,code(M)∈ {0,1}, et la fonctioncodeest inversible (codagesans perte).
On souhaite quecode(M)soit le plus court possible en moyenne.
Unbitest un chiffre binaire,0ou1.
Exemple 3.2Un code idiot :code(M) =M, capacitÉlog|Σ|. Intuitivement, il faut
log|Σ|bits pour Écrire chaque lettre.
Exemple 3.3Codage de Huffman. On fabrique un arbre binaire. Aux feuilles, on trouve
les lettresa∈Σ. On s’arrange pour que les lettres les plus frÉquentes soient aux
feuilles les moins profondes dans l’arbre comme suit. Algorithme : initialementS=
{({a}, P r[X=a], Ta)|a∈Σ}, oÙTaest l’arbre rÉduit á une unique feuille Éti-
quetÉea; tant queScontient au moins deux ÉlÉments, en prendre deux,(E, p, T)
0 00 00
et(E ,p ,T)avecp,ples plus bas possibles, et les remplacer par(E∪pE ,+

0
p ,); á la fin,S={(Σ,1, T)}, et retournerT.
0
T T
On posecode(a) =chemin depuis la racine deTjusqu’á la feuillea, oÙ « droite »=1,
« gauche »=0 ;code(a0a1. . . am−1) =code(a0)code(a1). . . code(am−1).
∗
DÉfinition 3.4Uncode prfixeest une fonctioncode: Σ→ {0,1}tel que pour tous
a, b∈Σaveca6=b,code(a)n’est pas un prÉfixe decode(b)(et rÉciproquement).
Le code de Huffman est prfixe. Un code est prfixe si et seulement si on peut organiser
les chanescode(a),a∈Σsous forme d’un arbre binaire, et aux feuilles les lettresa
(ou bien rien). Tout code prfixe est dcodable de faÇon unique : lire les bits dans l’arbre
depuis la racine jusqu’á arriver á une feuille, mettre la lettre crite á cette feuille (si
pas de lettre, erreur), et repartir á la racine. (Le code Morse fonctionne djá comme Ça.)
Lemme 3.5 (Locatelli-Mabon)SoitXde loipa=P r[X=a],a∈Σ, et soitqa≥0,
P
a∈Σ, tels queqa≤1. On a l’ingalit de Locatelli-Mabon:
a∈Σ
X
H(X)≤ −palogqa,
a∈Σ
avec ÉgalitÉ si et seulement sipa=qapour touta∈Σ.
On utilise comme conventionlog 0 =−∞,0.(−∞) = 0.
DÉmonstration.Si certainspasont nuls, on remplaceΣpar{a∈Σ|pa6= 0}.
Ceci nous permet de supposerpa6= 0pour touta∈Σ. On a maintenant :
  
X XX
qaqa1
H(X) +palogqa=palog =paln
papaln 2
a∈Σa∈Σa∈Σ
 
X
qa1
≤pa−1
paln 2
a∈Σ
 !
X X
1
=qa−pa≤0.
ln 2
a∈Σa∈Σ

3

Sipa6=qapour au moins una∈Σ, alors on peut supposer que c’est pour unatel que
pa6= 0. En effet, sinonpa=qapour toutatel quepa= 0, et la somme de cesqa(i.e.,
despa) vaut1, ce qui implique queqa= 0 =papour toutatel quepa= 0.
Donc, sipa6=qapour au moins una, avecpa6= 0, alors le termeln(qa/pa)est
strictement suprieur áqa/pa−1, et l’ingalit est stricte.✷
Lemme 3.6 (Kraft)Soitcodeun code prÉfixe surΣ. On a l’ingalit de Kraft:
X
−|code(a)|
2≤1.
a∈Σ
DÉmonstration.Dessinons l’arbre binaire du code prfixe. Dfinissons le poids de
−|w|
chaque nœud (qui est un mot binairew) par le nombre2. Le poids de tout nœud
internewest la somme des poids de ses deux filsw0etw1. Par rcurrence sur la
0
hauteur de l’arbre, le poids de la racine,12 =, est la somme des poids des feuilles.
P
−|code(a)|
Or2est la somme des poids de certaines des feuilles, celles qui sont
a∈Σ
tiquetes par une lettre.✷
Notons|w|le nombre de bits dans le mot binairew. On ne peut pas compresser
plus qu’avecH(X)bits par lettre :
Lemme 3.7Pour tout code prÉfixecodesurΣ,E(|code(X)|)≥H(X).
DÉmonstration.On applique l’ingalit de Kraft (Lemme 3.6), et on obtientqa=
−