Codage, Cryptologie Et Applications
Codage, Cryptologie Et Applications
Codage, Cryptologie Et Applications
Codage, cryptologie
et applications
Bruno Martin
Prsentation
Utilisation
Remerciements
Prface v
P ram bule vii
Thorie de linformation 1
1 T h o r ie de l in fo rm a tio n 3
1.1 Introduction...................................................................................... 3
1.2 Information et mesure de linform ation........................................ 4
1.3 Codage pour un canal non bruit . . . 7
1.4 Codage en prsence de bruit . . . 10
1.5 Thormes de Shannon. . . 14
1.6 O b se rv a tio n s..................... 14
Compression de donnes 15
2 C om p re ssio n d e don n es 17
2.1 Introduction...................................................................................... 17
2.2 Types dalgorithmes de c o m p re s sio n ........................................... 18
2.3 Dfinitions.......................................................................................... 19
2.4 Techniques de b a s e .......................................................................... 19
2.5 Algorithmes statistiques . . . . . 21
2.6 Algorithmes dynamiques . . 24
2.7 Limites de la com p ression ............................................................. 32
2.8 O b se rv a tio n s................................................................................... 33
4 C o d e s linaires 45
4.1 Prambule m ath m atiqu e............................................................... 45
4.2 Dfinitions............................................................................................ 46
4.3 Dcodage par les classes latra les............................ 49
4.4 Exemple de dcodage par letableau standard 51
4.5 Codes d u a u x ..................................................................................... 53
4.6 Dcodage par le syn drom e................................................................ 55
4.7 Exemple de dcodage par latable des sy n d rom es........................ 56
4.8 Quelques proprits des codeslinaires........................................... 56
4.9 O b se rv a tio n s..................................................................................... 59
5 C o d e s d e H a m m in g 61
5.1 Dfinition . . . . . . 61
5.2 Proprits des codes de Ham m ing................................................... 62
5.3 D c o d a g e ........................................................................................... 63
5.4 Codes de Hamming te n d u s ............................................................ 63
5.5 O bservation ........................................................................................ 64
6 C o d e de G o la y te n d u 65
6.1 Matrice gnratrice............. ......................... 65
6.2 Proprits du c o d e ............................................................................ 66
6.3 Dcodage ..................................................................................... 67
6.4 E x e m p le s ........................................................................................... 68
6.5 O b se rv a tio n s.................................................................................. 69
7 C o d e s d e R e e d -M u lle r 71
7.1 Dfinition inductive ......................................................................... 71
7.2 Matrices gnratrices......................................................................... 72
7.3 Proprits du c o d e ............................................................................ 73
7.4 D c o d a g e ........................................................................................... 75
7.5 Observations ..................................................................................... 75
8 C o d e s cy cliq u es 77
8.1 D e s c r ip tio n ........................................................................................ 77
8.2 Reprsentation poly n om ia le............................................................ 77
8.3 Les facteurs de xn 1 sur F2 ......................................................... 80
8.4 Implantation du codage par lescodes c y c liq u e s ........................... 82
8.5 Implantation du dcodage descodes cy cliq u es............................. 83
8.6 Exemples de codes cycliques............................................................ 85
Table des matires xiii
9.1 Dfinitions............................................... 87
9.3 D c o d a g e ........................................................................................... 89
Complexit 119
12 T h o rie d e la c o m p le x it 121
12.5 Classe du temps polynomial pour les modles non dterministes 127
Cryptologie 147
17 C ryp tan a lyses diffren tielle et linaire des chiffres itrs 177
20 C ry p to g ra p h ie cl p u b liq u e 209
20.1 Merkle H ellm an................................................................................. 210
20.2 RSA ................................................................................................. 213
20.3 Le problme du logarithme d i s c r e t ................ 221
20.4 El G a m a l ........................................................................................... 221
In d e x 329
B ib liog ra p h ie 339
P r e m i r e p a r t ie
Thorie de linformation
C h a p it r e 1
Thorie de linformation
1.1 Introduction
N Nri N ni N n2 N n2
log2 = log2 = log2 h log2 = log2 . = log2 1- log2
n ri\ n m n n2 n n2 n
-
1.2.2 Entropie
/(Ei)=10&(f[)=lofeO
et on dfinit Y entropie de la partition comme
H (partition) = hf loS2 ( ~ )
i= 1 ' *2
que lon peut exprimer sous la forme de probabilits avec Pi = j f la probabilit
associe lapparition du message Ei
n n , ^v
H (partition) = - y ^ p , l o g 2 (p; ) = ^ Pi log2 ( )
i= 1 i= 1 ^VrJ
Du fait que les Ei forment une partition de E , 1 Pi = 1 et lentropie
correspond la distribution de probabilit de tous les messages possibles.
6 Information et mesure de linformation
H = \ lo2(2) + \ log2(2) = 1
Dans ce cas, le champ sexe de la base de donnes ne requiert quun seul bit
dinformation pour dterminer le sexe dun individu. Pour un champ d infor
mation ayant la mme smantique mais cod au moyen dun caractre alpha
numrique, on naura pas plus dinformation mais on aura besoin de plus de
bits.
1.2.3 Taux
ou, en dautres termes, le nombre moyen de bits dinformation fourni par chaque
caractre. Pour une langue naturelle et un N suffisamment grand, le taux de
la langue r est compris entre 1 et 1,5.
Le taux absolu R de la langue est alors dfini comme le nombre maximal de
bits d information qui peuvent tre cods par chaque caractre sous lhypothse
que ceux-ci sont tous quiprobables. Ainsi, pour un alphabet de L lettres, le
taux absolu est la quantit log2(L), qui vaut 4,7 pour un alphabet latin. On
illustre ainsi le fait que les langues sont redondantes et il est possible de mesurer
cette redondance D par
D = R r
E xem ple 1.5 Pour lalphabet binaire E = (0 ,1 }, lensemble de tous les mots
sur E est E* = {e, 0 ,1 ,0 0 ,0 1 ,1 0 ,1 1 ,0 0 0 ,...}.
8 Codage pour un canal non bruit
En associant des codes courts aux messages les plus frquents et des codes
longs pour les autres, on peut construire un code optimal, au sens o le nombre
moyen de bits par symbole correspond prcisment lentropie de lensemble
des messages possibles.
Un premier exemple dune telle ide est le code morse :
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
Huffman a propos un algorithme qui construit un code prfixe optimal pour
une source Sr comprenant r messages sur un alphabet binaire fond :
Dans le cas des codes binaires longueur fixe, on souhaite coder des messages
de longueur k au moyen de mots du code de longueur n. On a ajout n k
symboles de redondance. Si le code comprend w mots, la quantit dinformation
vhicule est log2(w) et le rendement du (n, />:)-code est
lg2(';)
n
1.3.3 Longueur moyenne dun code
qui correspond la somme pondre des longueurs de tous les mots et qui
concide avec L ', rapport entre le nombre de symboles binaires du message
cod et le nombre de symboles de source quand le message est de longueur
suffisante pour que tous les symboles apparaissent avec une frquence relative
gale leur probabilit.
On est alors amen attribuer aux messages les plus frquents des codes de
courte longueur. C est cette ide qui a t exploite par Morse et par Huffman.
| - 1 + | - 2 + | - 2 = 1. 5
_ HW
641062 { m ) + 2 (
161062 ( + ) ) +0, 041062 ( ^ s ) = M 5
B B ( 0,04) B A (0,16)
A B (0,16) B B B A {0,2)
AB B B B A (0 , 36) A A {0,64)
0 .1 - P 0
1 1
1-p
E xem ple 1.8 Avec une probabilit d erreur de 1%, la capacit du canal binaire
symtrique est 0 (0 ,0 1 ) = 1 (0.07 + 0,01) = 0,92.
1.4.2 quivoque
H (A /B ) = - a,fcP M ) l o g 2( P ( a /6))
= E , bp (^)lg2(p(i7fcy)
= E 6 ( P Q > ) E a P ( a / b ) log2 (p(i 7 by))
P reu ve
(2) on choisit un vecteur iq de poids minimal qui napparat pas dans la pre
mire ligne et on numre sur la deuxime ligne les lments ui + C en
inscrivant au-dessous de 0 le chef de classe u et au-dessous de chaque l
ment x G C llment u\ -1- x ;
(3) on choisit un vecteur U2 de poids minimal qui napparat pas dans les pre
mires lignes et on numre sur la troisime ligne les lments + C en
inscrivant au-dessous de 0 le chef de classe u2 et au-dessous de chaque l
ment x C llment U2 + x ;
(4) on itre ce procd jusqu ce que toutes les classes latrales soient listes
et que tout vecteur de (Z 2)" napparaisse quune seule fois.
Soit une source qui met des symboles binaires de faon quiprobable au
travers dun canal binaire symtrique de probabilit d erreur p = 1%, on a vu
prcdemment que lentropie de la source est de 1 logon par symbole et que la
capacit du canal est de 0,92. Comme chaque symbole peut tre erron, on ne
peut reconstituer le message transmis.
Pour remdier ce problme, on peut rpter trois fois le symbole mis
(cest le code de rptition) :
1 i 111
0 000
Dans ces conditions, le rcepteur recevra une suite de trois symboles binaires
et pourra, par majorit, dduire quel tait le symbole mis.
Plus gnralement, si pour chaque symbole 1 envoyer, on en transmet
2n + 1, on rduit la probabilit derreur en mme temps que n crot.
Le rapport
nombre de signaux binaires transmis
nombre de signaux binaires utiliss
est appel vitesse de transmission du canal et la probabilit derreur du dco
dage tend vers zro en mme temps que la vitesse de transmission.
14 Thormes de Shannon
Coder est une opration efficace au prix dune certaine redondance. Cela
justifie ltude de la construction de codes.
1.6 Observations
Compression de donnes
C h a p it r e 2
Compression de donnes
2.1 Introduction
B R
Bien quil y ait un grand nombre dalgorithmes de compression et, pour cha
cun d entre eux, un grand nombre de variantes, on peut les classer en plusieurs
catgories [85] :
Compression de donnes 19
2.3 Dfinitions
ICI
le rapport de compression, j-g-j- qui est normalement < 1. Une valeur de 0,6
signifie que |?| a t rduit de 40%.
Si le nombre d espaces est faible, le nombre de 1 dans le mot binaire sera petit
face au nombre de 0 et le mot binaire pourra tre comprim, par exemple en
04107102108 pour quatre rptitions de 0 suivi dun 1, de sept 0...
Si on travaille sur une liste de mots tris dans lordre lexicographique (lordre
du dictionnaire), on peut utiliser la technique de compression de tte. Celle-
ci repose sur le principe que deux mots successifs dans notre liste partagent
souvent un mme prfixe p de longueur n. On peut donc remplacer les lettres
de p dans le second mot par n, longueur du prfixe commun.
E x em p le 2.1
Cod a Coda
Cod 3
Code -Barres 3e-Barres
Coder 4r
Cod eur 4ur
Codicille 3icille
di = Ci \ < i < r 1
c'r = cr.O
dr+x = cr. 1
( 1) on classe dans une liste les symboles de la source dans lordre des probabilits
dcroissantes ;
(2) on remplace les deux derniers symboles par un seul symbole, affect dune
probabilit qui est la somme des probabilits des deux derniers symboles ;
A 1/2 1/2 - 0
B 1/4 1/2 -* 1
C 1/4
0 0 A 1/2
1 10 B 1/4
11 C 1/4
Il est possible (cf. [20]) de rsumer ces tapes en utilisant un arbre binaire
o chaque feuille reprsente un message et chaque nud interne la fusion de
deux ensembles de messages. Dans la figure 2.2, les probabilits d apparition
sont dcrites entre parenthses et le code de Huffman associ est en gras.
C ( 1/4)11 H (l/4 )1 0
l\ / 3
C B { 1/2) A { 1/2)0
2.6.1 LZ77
oo
x
o;
aiiab, babi abab, ,ababb a b a ijb b b L jb a b u b b a b b
V- - 1 v
tampon de recherche tampon de lecture
Compression de donnes 25
CD
'0> a
6
*H K
CD B
B o
oo cd
X
CD
X
CD
auabubabuababuababb abaubbbubabubbabb
CD
B
O
CD
o
CD
X x
(D
CD
auabubabuababuajbabb aba, tbbb, bab, ,bbabb
CD
B
*H
CD
CD B
B o
O u
CD
y
o; auabubabuababuababb abaubbbubabubbabb
A lg o rith m e d e co m p re ssio n L Z 77
Chacun des triplets est cod en binaire en associant un nombre fixe de bits
pour chacune des valeurs. Choisir la dernire correspondance trouve au lieu
de la premire simplifie le programme. Il nest pas ncessaire de mmoriser la
correspondance prcdente. Cependant, le fait de choisir la premire correspon
dance, au prix dun accroissement de la complexit du programme, prsente un
avantage. Dans ce cas, le dcalage est plus petit. Cela peut sembler inutile car
le codage des lexmes est fait de telle sorte que la longueur de (10,3, u) et de
(5,3, u) est identique (les valeurs numriques sont crites avec une taille fixe
paramtre par la taille du tampon de recherche). Mais si on ajoute un codage
de Huffman lissue de LZ77, on attribuera aux dcalages les plus courts des
codes plus courts. Cette mthode propose par B. Herd porte le nom de LZH
et repose sur le principe suivant : si on dispose dun grand nombre de petits
dcalages, on amliore la compression en utilisant LZH.
En pratique, pour obtenir un codage efficace, N F = 2ei et F = 2ez. On a
donc besoin de e\ bits pour coder p, la position dans le dictionnaire et de e,2
bits pour coder l, la longueur de la rptition.
Plus le mot rpt sera long, plus le codage sera efficace. Pour avoir des chances
dobtenir de longues rptitions, il est ncessaire que le dictionnaire soit de taille
suffisante (quelques milliers de caractres).
Lalgorithme effectue sa compression au fur et mesure du dplacement de la
fentre. Il nutilise que le dictionnaire compris dans le tampon de recherche et
certains facteurs vus prcdemment sont de ce fait oublis. Si la fentre est trop
grande, il faudra trop de bits pour coder le triplet de sortie et lalgorithme nef
fectuera pas une bonne compression. De plus, la recherche de motifs deviendra
de plus en plus coteuse en temps (de lordre de (N F ) x F oprations). Il faut
28 Algorithmes dynamiques
,ab abababababababababababababab
La d co m p re ssio n
1. lire un lexme
2. chercher la correspondance dans le tampon de recherche
3. crire le facteur trouv au dbut du tampon de lecture
4. crire la 3ecomposante du lexme la suite
5. dcaler le contenu des tampons de / + 1 cases vers la gauche
Faiblesses d e L Z 77
La principale faiblesse de LZ77 rside dans lhypothse que les motifs rpts
sont proches dans les donnes dentre. Les donnes qui ne satisfont pas cette
hypothse seront mal comprimes.
Un autre inconvnient est que la taille F du tampon de lecture est limite.
De ce fait, la taille de la plus longue correspondance ne peut excder F l. F ne
peut crotre beaucoup, car le temps de compression crot proportionnellement
F. Il en est de mme avec la taille du tampon de recherche.
2.6.2 LZ78
A lg o rith m e d e co m p re ssio n L Z 78
mot* e
dictionnaire [0]< e
indice<1
rp ter
lire S, le premier caractre du texte T restant comprimer
{on retire galement S de T }
si m ot.S G dictionnaire alors
mot < mot.S
mis < faux
sin on
m e ttre (indice de mot dans le dictionnaire, S)
affecte(mot.S') lentre indice du dictionnaire
indice* indice+1
mot* e
mis* vrai
fsi
ju s q u fin des donnes comprimer
si mis = faux alors
m e ttre (indice de mot dans le dictionnaire, S)
fsi
Dictionnaire lexme
0 n u ll
1 a (0,o )
2 ab (1 ,b)
3 b (0, 6)
4 aba (2, o)
5 ba (3 ,a)
6 bb (3,6)
7 bba (6, a)
8 bbb (6, 6)
9 abb (2, 6)
Compression de donnes 31
A lg orith m e d e d co m p re ssio n
mot* e
dictionnaire [0]< e
indice-*1
rp ter
lire suivant(ind,S') dans le texte comprim
si ind = 0 alors
m ettre(S')
dictionnaire [indice]* S
indice < indice+1
sin on
facteur* concatne(dictionnaire[ind] ,S)
m ettre(facteur)
dictionnaire [indice]* facteur
indice < indice+1
fsi
ju s q u fin du texte dcomprimer
Exem ple 2.6 Soit la donne (0, a )(l, 6)(0, b)(2, a)(3, a)(3, b)(6, a) (6,b)(2,b)
dcomprimer. Elle donne lieu la suite d missions suivante :
Dictionnaire lexme
0 n u ll
1 a (0,a)
2 ab ( 1. 6)
3 b (0, 6)
4 aba (2 ,a)
5 ba (3, a)
6 bb (3,6)
7 bba (6, a)
8 bbb (6, 6)
9 abb (2, 6)
L Z 78 en pra tiq u e
2.8 Observations
Dans cette partie, nous commencerons par noncer quelques gnralits sur
la thorie des codes puis nous prsenterons les codes linaires (chapitre 4) et
quelques exemples de tels codes : les codes de Hamming (chapitre 5), le code
de Golay (chapitre 6) et les codes de Reed-Muller (chapitre 7).
Dans le chapitre 10, nous introduirons les codes convolutifs sans lesquels il
aurait t trs difficile de concevoir les tlphones cellulaires.
d ( x ,y ) > 0; d(x, y) = 0 x = y;
d(x, y) = d(y, x); d(x, y) < d(x, z) + d(z, y)
38 Distance de Hamming et boules
i= 1
pour x, y G B n.
E x e rcice 3.1 Montrer que la distance de Hamming est bien une distance.
C o rrig Le seul point dlicat est de vrifier lingalit triangulaire. Sans perte
de gnralit, on vrifie que d h (0 , x ) < d n (0 ,y) + d,jj(x, y) avec 0 le mot 0n,
x = l e0n-e et y = 0al 60cl d avec a + b = e ,c + d n e. Alors d # (0, x) = e,
d i( 0, y) = b + d et d n (x, y) = a + d. On a donc e = a + b < b + d + a + d.
B\ (x) = {000,100,010,001}
B i(y )= {101,001,111,100}
Les deux boules ne sont pas disjointes car B\(x) n By (y) = {100,001}. Si on
reoit les messages 100 ou 001, on ne peut savoir si le message mis tait x ou
bien y. En revanche, on peut affirmer quil y a eu une erreur de transmission.
C est un code dtectant une erreur.
Supposons quun lment y G B n soit la fois dans Be(x) et dans B e(x'). Alors,
par lingalit triangulaire, on aurait dH {x,x') < d n (x ,y ) + d jj{y ,x ') < 2e
contradictoire avec lhypothse Mx,x' G C, x: 7^ x: => d ji(x ,x ') > 2e + 1 du
point (ii).
{
x 1 * 01110
y 1>10101
zh * 11011
B 1(x ) = {01110,11110,00110,01010,01100,01111}
Bi (y) = { 10101, 00101, 11101, 10001, 10111, 10100}
B i{z) = {11011,01011,10011,11111,11001,11010}
On dfinit ensuite quelques notions utiles sur les codes. On appelle distance
minimale dun code C la quantit :
dH(C) = mm {dH(x, y) : x ,y e C ,x ^ y }
Gnralits sur la thorie des codes 41
w(C) = min{w(a;) : i C, i / 0 }
dH(x ,y ) = dn (01110,10101) = 4
dH(x, z) = dH(01110,11011) = 3
dH(y, z) = (10101,11011) = 3
La proposition suivante due Hamming nous donne une borne sur le nombre
de mots du code.
< \Bn\= 2n
ceC
Do le rsultat. 0
La notion de rayon de recouvrement permet de mesurer quel point un mot
reu z peut diffrer d un mot du code c 6 C . Le rayon de recouvrement p(C)
est dfini par :
Le rayon de recouvrement est le plus petit p pour lequel les boules B p(c) pour
c C recouvrent lensemble B n en entier. Soit t le plus grand entier tel que
les boules Bt(c) pour c G C* soient disjointes. Si p = t, on dit que le code
est parfait. En dautres termes, on dit aussi quun code C Q B n de distance
minimale h(C) = 2e + 1 est parfait si tout mot x de B n est distance < e
dexactement un mot c du code.
On obtient alors la condition dite dJempilement de sphres : si C B 71 est
un code parfait corrigeant e erreurs, alors pour |/i| = q,
i0 ' '
3.3.1 Dtection
On suppose avoir reu un message qui nest pas un mot du code. Il est clair
quil y a eu une erreur au cours de la transmission et nous avons dtect la
prsence dune (ou de plusieurs) erreur. Si aucune erreur n a t dtecte, on
a soit reu un mot du code, soit reu un mot qui comportait trop d erreurs et,
dans ce dernier cas, le code ntait pas adapt la capacit du canal.
3.3.2 Correction
E x em p le 3.4 Soit Ci = {00,01 ,10 ,1 1). Chaque mot reu est un mot du code.
Ci ne peut donc servir dtecter des erreurs. Ci ne corrige pas derreurs non
plus.
C2 = { 000000,010101,101010,111111}
Le bit ajout sappelle bit de parit. Supposons avoir reu le message 010.
Comme 010 nest pas un mot du code, on est certain quil y a eu une erreur de
transmission. Le message peut tre dcod en 110, 000 ou 011 en ne changeant
quun seul bit du message. Dans les chapitres suivants, nous allons distinguer
la manire de traiter les mots reus les plus proches d un seul mot du code.
E x e rcice 3.2 Quelle est la valeur minimale de n pour avoir deux boules dis
jointes de rayon 2 et des mots de { 0, 1} " ?
Gnralits sur la thorie des codes 43
Codes linaires
On dit que E est un espace vectoriel sur un corps K si et seulement si, pour
des lments u, v et w de E, on a :
1. (u + v) + w = u + (v + w) 5. Vc K , c{u + v) = c u + c - v
2. 30 : u + 0 = 0 + u= u 6. Va, b G K , (a + b)u = a - u + b - v
3. Vm 3 (u) : u u= 0 7. Va, b G TV, (a b)u = a (b u)
4. u+ v = v + u 8. 1 u = u
f x + y& F \/x,y G F
\ XxGF VA G TV, Va; G F
Une base de E est une famille d lments de E qui est libre et gnratrice.
Si (bi)ie i est une base de E, alors : Va; G F 3!(A)*/ G K : x =
46 Dfinitions
Si la dimension de E est finie alors chaque base de E est finie (son ensemble
sous-jacent est de cardinal fini) et toutes les bases ont le mme nombre d l
ments. Ce nombre est la dimension de lespace. Si la dimension de E est n,
alors :
- S i (ffi) est une famille gnratrice de E alors |/| > n. Sil y a galit, alors
est une base.
Si (h)isi est une famille libre de E alors |/| < n. Sil y a galit, alors (h)ii
est une base.
Vx G E, My G E f ( x + y) = f ( x ) + f ( y )
VA e K, V G E / ( X.x) = A f { x )
4.2 Dfinitions
Si C a pour dimension k (au sens des espaces vectoriels), C est appel (n, k)-
code linaire et, si sa distance minimale est d. C sera appel un (n. k, d)-code
linaire.
^ La condition (2) nest en fait utile que pour des codes sur un alphabet autre que lalphabet
binaire.
Codes linaires 47
E xem ple 4.1 Soit G = ( ? o o ) 'a matrice gnratrice d un code C. Les mots
du code sont :
'011'
10 0 ;
00 000
01 100
10 0 11
11 111
Une caractristique importante des codes est leur distance minimale. Elle
est particulirement facile calculer pour les codes linaires.
^ . m / l OOOl l v
E x e rcice 4.1 Soit G ( o i o i o i )
'0 0 1 1 1 0 ''
C orrig
(1)
(3) dH(C) = 3.
u + C = {u + x : x G C }
Le lemme 4.4 nous donne une premire proprit des classes latrales :
v + y = ( u + x ) + y = u + (x + y) G u +C =>v + C u + C
u + z = (y x) + z = v + {z x) G v + C => u+ C Ci v + C
Donc, u + C = v + C.
(S) tant donn deux classes latrales, elles sont soit disjointes soit identiques.
50 Dcodage par les classes latrales
P reu v e
(2) on choisit un vecteur ui de poids minimal qui napparat pas dans la pre
mire ligne et on numre sur la deuxime ligne les lments U\ + C en
inscrivant au-dessous de 0 le chef de classe U\ et au-dessous de chaque l
ment x C llment U\ + x ;
(3) on choisit un vecteur U2 de poids minimal qui napparat pas dans les pre
mires lignes et on numre sur la troisime ligne les lments U2 + C en
inscrivant au-dessous de 0 le chef de classe U2 et au-dessous de chaque l
ment x C llment U2 + x ;
(4) on itre ce procd jusqu ce que toutes les classes latrales soient listes
et que tout vecteur de (Z 2)" napparaisse quune seule fois.
- ( i )
r , _ ( l 0 1 A
^0 I 0 )
Lensemble des messages non cods correspond aux diffrents couples pos
sibles sur {0, 1} qui sont :
A = { ( 0 ,0 ) . (0.1), (1,0), (1 ,1 )}
(1 0 1 A
mots de A poids
^0 1 0 l j
(0, 0) (0 0 0 o)
(0, 1) (0 1 0 1) 2
( 1, 0) (i 0 1 i) 3
(1, 1) (1 1 1 o y 3
mots du code
( (l 'o 0 = AS AJJ
symboles bits de
dinformation redondance
0000 + C = C lui-mme
1000+ C = {1000,1101,0011,0110}
0100 I- C = { 0100, 0001. 1111, 1010}
0010 + C = { 0010, 0111, 1001, 1100}
E x e rcice 4.2 Soit G la matrice gnratrice du (6,3) code linaire dfinie par :
/ 0 1
G = Id3 1 0 1
\ 1 1 0
(1)
000000 001110 010101 011011 100011 101101 110110 111000
100000
010000 110011
001000
000100
000010
000001
100100
(3)w (C ) = djq{C) = 3.
Les codes duaux vont jouer un rle important dans le dcodage d un mes
sage. On dfinit le code dual de C not C par
C = { y e ( Z 2 )n : V x e C , ( x , y ) = 0 }
Ainsi, le mot 11110 peut tre dcod avec succs mais le mot 10011, qui a subi
deux erreurs, ne peut tre dcod convenablement et on demande la rediffusion
du message.
x e C t t x tH = 0
(000000) = (0 0 0 )
(100000) = (011)
(010000) = (101)
( 001000) = ( 110)
(000100) = (100)
(000010) = (010)
( 000001 ) = (001 )
( 100100) = (111)
Observons que le calcul du syndrome (110000) = (110) est le mme que pour
(001000) = ( 110).
On constate galement que la matrice de contrle engendre un code qui est
quivalent au code C. C est donc un code autodual.
On vrifie alors que deux vecteurs x et y de (Z 2) " sont dans la mme classe
latrale si et seulement si ils possdent le mme syndrome :
x lH = y1 H x y e C
/1 \
1 0 1 0 1
S(y) = (o i)
L 1 0 1 1
W
On en dduit que le mot du code est y /(0 1 ) 1111 0100 = 1011 et que le
vecteur d erreur tait, (0 1 0 0).
si a; G C, alors w(:r) = cl// (0, x) et donc tout poids correspond une distance
entre les mots de C.
Nous avons dj utilis cette proprit sans la nommer et nous la rappelons
pour noncer le rsultat suivant qui permet de donner une borne sur la distance
minimale d un code linaire.
Preuve On sait que tout code linaire C peut tre mis sous la forme d un
code linaire quivalent C" qui est sous forme normale. On considrera donc
le code C" de matrice gnratrice G. Rappelons que tout mot de C" sexprime
comme combinaison linaire des lignes de G. Le poids minimal du code est donc
ncessairement infrieur au poids minimal des vectems lignes de G et, a fortiori
au poids maximal de ces mmes vecteurs. Comme les k premires colonnes de
G sont la matrice identit, le poids maximal d une ligne est donc < 1 + (n k).
La proprit des poids et des distances nous permet de conclure que la
distance minimale est dau plus 1 + n k.
e \cf
|C|(|C|-l)<n0|C|2
d-1
T"" H*, = 0
3=1
E x e rcice 4.6 On suppose quun canal binaire accepte des mots de longueur 7 et
que les seules erreurs qui peuvent apparatre sont 0000000. 0000001, 0000011,
0000111, 0001111, 0011111, 0111111, 1111111. Construire un (n ,k )-code li
naire qui corrige toutes ces erreurs avec un taux aussi grand que possible.
( 1 1 X\
Id4 1 1 0
1 0 1
V 0 1 1 /
Codes linaires 59
H
0
1 ... 1 1
4.9 Observations
Codes de Hamming
Les codes de Hamming sont des codes correcteurs dune seule erreur par
ticulirement simples du point de vue du codage et du dcodage. Nous les
prsenterons comme des codes linaires sur Z 2.
5.1 Dfinition
{
X4 + X5 + x 6 + x 7 = 0
x2 + x3 + x6 + x7 = 0
Xi + X3 + Xs + X7 = 0
(il en est de mme pour y, z et t) et on attribue des valeurs x , y , z et t ,
/ 1011010X
ce qui donne la matrice gnratrice G = ( 1 1 0 1 0 0 1 ) On peut vrifier que
\o 0 1 0 1 1 0/
G.1H = 0. Notons au passage que la matrice gnratrice G nest pas unique.
62 Proprits des codes de Hamming
Une proprit remarquable des codes de Hamming est donne par le tho
rme suivant.
P reu v e
(1) Par dfinition, Ham(r) L est un (2T1, r)-code, donc lam (r) un (2r 1, 2r
r l)-cod e linaire.
(2) On montre que Ham(r) ne contient aucun lment de poids 1 ou 2 sinon on
aurait respectivement quune colonne de H serait nulle ou que deux colonnes de
H seraient identiques. Ham(') contient des lments de poids 3 par dfinition
de H :
/ 0 0 0 \
0 0 0
0 1 1
V 1 0 1 -
5.3 Dcodage
Comme Ham(r) est un code parfait corrigeant une seule erreur, ses classes
latrales sont prcisment les 2r (= n + 1) vecteurs de (X2)'' de poids infrieur
ou gal 1. Le syndrome du vecteur x dont seule la j e composante est non
nulle nest autre que la transpose de la j e colonne de H. Si les colonnes de
la matrice H sont ordonnes dans lordre croissant des nombres binaires, la
j e colonne correspond lcriture binaire de j . On en dduit lalgorithme de
dcodage suivant :
, 1101000V
E xercice 5.2 Montrer que le code engendr par G = ( 0011010 ) es^ un cde de
' 0001101'
Hamming.
( \
0
0
\1 1 ... 1 l)
5.5 Observation
Soit Z? la 12 x 12 matrice :
( 1 1 0 1 1 1 0 0 0 1 0 1 >
1 0 1 1 1 0 0 0 1 0 1 1
0 1 1 1 0 0 0 1 0 1 1 1
1 1 1 0 0 0 1 0 1 1 0 1
1 1 0 0 0 1 0 1 1 0 1 1
1 0 0 0 1 0 1 1 0 1 1 1
0 0 0 1 0 1 1 0 1 1 1 1
0 0 1 0 1 1 0 1 1 1 0 1
0 1 0 1 1 0 1 1 1 0 0 1
1 0 1 1 0 1 1 f 0 0 0 1
0 1 1 0 1 1 1 0 0 0 1 1
^ 1 1 1 1 1 1 1 1 1 1 1 0 J
P reu v e
(3) Comme le poids de chaque ligne de B est impair (7 ou 11), le produit scalaire
de chaque ligne avec elle-mme donne toujours 1. De plus, le produit scalaire
de la premire ligne de B avec nimporte quelle autre ligne est toujours
nul. Du fait de la structure cyclique de B 1, le produit scalaire de lignes
quelconques de B i est toujours nul. D o B'B = Id. Mais comme 'B = B,
B 2 = B*B = Id. On a,
(5) G = (M 12, -B), donc 'H = B , M 12) et comme 'B = B , on retombe bien sur
(6) La dmonstration de ce point est plus complique. Elle est scinde en trois
tapes :
Code de Golay tendu 67
- On montre tout d abord que tout mot de C'24 a un poids divisible par 4.
Observons que les lignes de G ont toutes un poids de 8 ou de 12.
Soit v G C'24 qui est la somme de deux lignes de G : v = r i + r j. Les lignes
de B tant toutes orthogonales, il sensuit que les lignes de G aussi. Donc
ri et Tj ont un nombre pair de 1 en commun, e.g. 2x. Donc,
est un multiple de 4.
Soit v G C24 tel que v = ri + rj + trois lignes de G. Soit vi = r,- + r:l.
Comme C est autodual, (ci ,r^) = 0 et ont un nombre pair de 1 en
commun, e.g. 2y. Donc,
est un multiple de 4.
En continuant inductivement, on montrerait que Vu G C24, w(u) = 0(4).
- Les 11 premires lignes de G sont les mots du code C24 de poids 8. Ainsi,
la distance de C24 est soit 4 soit 8.
Il nexiste pas de mot de C24 de poids 4. En effet, supposons v G C'24 non
nul tel que w(u) = 4. Alors, il existe u t et u? tels que, v = U\ (id, L)
et. v = w.2 ( B, Id) puisque ces matrices engendrent toutes deux C24. On
a w(w.j) < 2 ou w (it2) 2 puisquune moiti de v doit contenir au plus
deux 1. Cependant, il 11existe pas de somme d une ou de deux colonnes
de B de poids au plus 3. Donc, w(u) = w (iq) + w (ui.B) > 4. Par
consquent, il nexiste pas de v de poids 4.
(7) Il sensuit, par dfinition, que C24 corrige au plus trois erreurs.
6.3 Dcodage
On cherche corriger des erreurs de poids dau plus 3, donc w (e) < 3.
On sparera les vecteurs en deux moitis par une virgule. Ainsi, par exemple,
e = (ei, 62) chacun de longueur 12.
On cherche dterminer le chef de classe de la classe latrale contenant y
sans avoir se reporter au tableau standard de C24.
Puisque w (e) < 3, on a soit w (e i) < 1 soit w (e2) < 1. Soit Si le syndrome
de y - x + e obtenu en utilisant la matrice de contrle
deux bits ont t changs (si w (e2) = 1). De manire similaire, si w (ei) < 1
alors le syndrome
B
S2 = y ^ I d J = e i B + e 2
consiste soit en un mot de poids dau plus 3 soit en une ligne de B dont au
plus 2 bits ont t changs.
Dans tous les cas, si e est de poids dau plus 3, il est aisment identifi,
puisque au plus trois lignes des deux matrices de contrle peuvent tre trou
ves pour ajouter de linformation au syndrome. En utilisant cette dernire
observation, on obtient un algorithme de dcodage. On utilisera le fait que
B 2 = Id et
Si = ei 4- e2B = y lH
s2 = e i-B + e 2
= (e i + e2B )B = siB
(6) si w (sB + bi) < 2 pour une ligne bi de B, alors u = (i, sB + bi) ;
pour j, le vecteur dont seule la coordonne est non nulle;
6.4 Exemples
e = (,s, 0) = 100000000001,000000000000
et on en conclut que
x = y + e = 001111101110,010010010010
sB + b != 001110111000
sB + b2 = 010111110110
sB 4- b3 = 100101101010
sB 4- W = 000001010000
et on conclut que
x = y + e = 000011000111,011010000000
6.5 Observations
Le code de Golay est un code parfait dont les proprits algbriques et com-
binatoires sont exceptionnelles. Il est par exemple unique. Cela signifie que tout
code binaire de longueur 24 ayant 212 mots du code et une distance minimale
de 8 lui est quivalent. On peut aussi le retrouver de bien des faons diffrentes.
C h a p it r e 7
Codes de Reed-Muller
Nous nous intressons ici une classe de codes qui contient les codes de
Hamming tendus dont nous avons parl prcdemment. L intrt de ces codes
est quils sont dfinis de faon inductive.
Les codes de Reed-Muller sont trs utiles pour la transmission sur des canaux
trs brouills. En particulier, le code R M ( l ,m ) a une distance minimale gale
la moiti de la longueur des mots du code. Le cas particulier de R M (1,5)
a t utilis pour la transmission d images de la plante Mars, via le satellite
Mariner-9. Chaque pixel tait cod par un niveau de gris (sur 64 possibles) et
transmis au moyen d un mot du code de longueur 32. Ce code pouvait corriger
jusqu 7 erreurs par mot du code.
R M (0,0) = (0 ,1 }
R M (0,1) = {0 0,1 1}
R M { 1,1) = {0, l } 2 = {0 0,01,10 ,11}
R M (0,2) = {0000,1111}
R M (2,2) = { 0 ,1 } 4
R M ( 1,2) = {(x , x + y ) : x E {0 0,01,10 ,11}, y G {0 0 ,1 1 }}
72 Matris gnratrices
R M ( 1,2) == i<
0 10 1, 10 0 1, ,
10 10 , 110 0 ,
0 0 11, 1111
et donc,
00000000, 0 0 0 0 1111,
0 10 10 10 1, 0 10 110 10 ,
10 10 10 10 , 10 10 0 10 1,
0 0 110 0 11, 0 0 11110 0 ,
0 110 0 110 , 0 110 10 0 1,
10 0 110 0 1, 10 0 10 110 ,
110 0 110 0 , 110 0 0 0 11,
11111111, 11110 0 0 0
_ / G(r, m 1) G(r, m 1)
G(r, m) =
0 G(i l,m 1)
En posant pour r = 0,
G (0.m ) = ( 11 . .. 1)
et pour r = m,
G ( m . m ) = ( o (mo i 1 m)
E x em p le 7.2
(1 1 1 1 1 1 1 l\
0 (1 ,3 ) = ( G M 0 ( 1 ,2 ) U 0 1 0 1 0 1 0 1
G( 0,2) 0 0 1 1 0 0 1 1
yo o o o i i i i/
avec
G (0 ,2) = (l 1 1 1)
et
1 1
\ (l
1 0 1
) = 0
\0 0 1 1/
Codes de Reed-Muller 73
G (0,1) = ( 1 1 ) , G ( 1 , 1 ) = ( J
E xercice 7.3 Montrer que (7( 1,3) est un code quivalent au dual d un code de
Hamming tendu de redondance 3.
(1) longueur n - 2m ;
Preuve Les proprits se prouvent par rcurrence. Le thorme est vrai pour
m = 1,2,3,4 ainsi que pour r = 0 et r = m.
On prouve que R M (i 1, m) R M {r,m ). On commence par
Q G(0,m-l)J
Enfin, soit
7.4 Dcodage
( 1)0101 1110
(2 ) 0110 0111
(4)1100 1110
7.5 Observations
Codes cycliques
8.1 Description
Ce sont les codes les plus utiliss ; ils simplantent assez simplement et pour
beaucoup dentre eux, on connat de bonnes techniques de dcodage. Nous nous
limitons ici au cas des codes binaires (dfinis sur F2, le corps fini 2 lments).
Exem ple 8.2 Le code de Hamming est cyclique. Soit par exemple G
/ 1101000 V
( 0011010) 11116 matrice gnratrice du code Ham(3) (cf. exercice 5.2). Par
'0001101 '
exemple, 0110100 est un mot du code et le mot 1101000 obtenu par dcalage
galement.
Remarquons quun code est cyclique sil est invariant par dcalages (ou
shifts).
Si c(x) est dans le code, alors x c(x ) lest aussi, tout comme p (x)c{x) pour
tout p {x) G F2[.x]. Ainsi, un code cyclique binaire de longueur n est un idal de
Fa[a:]/(an - 1).
D fin ition 8.6 Un idal I est principal sil consiste en tous les multiples d un
polynme fix, g (x), appel polynme gnrateur de / .
E xem ple 8.5 Le code C = { 0 . \+x, x + x 2,1 + x 2} est engendr par g(x) = 1+ x
dans i ?3 = F2 [.r]/x3 1.
Thorm e 8.9 Soit g (x) = g o+ giX + . .. -LgtX* le gnrateur dun code cyclique
C de longueur n. Une matrice gnratrice de C est donne par :
0 0 50 5i 52 5t 0
^0 0 50 5i 52 9t)
Pour construire tous les mots m (x) de C, il faut multiplier le gnrateur par tous
les polynmes binaires p (x ) de degr infrieur ou gal k 1. Matriciellement,
les mots m peuvent scrire m = p G.
/l 10 1 0 0 o\
0 1 1 0 1 0 0
0 01 1 0 1 0
\0 00 1 1 0 1/
Les mots du code sont les combinaisons linaires des lignes de la matrice.
Le code engendr par h(x) est quivalent au code dual de C (il sagit en
fait des mme mots mais crits en sens inverse). Le dual de C est donc un code
80 Les facteurs de x n 1 sur F2
/O 0 hk h\ ho\
0 hk ht ho 0
H =
0
\hk h-\ ho 0 0/
/O 0 1 0 1 1 1>
# = ( 0 1 0 1 1 1 0
\ l 0 1 1 1 0 0)
h'ordre multiplicatif de 2 modulo n est le plus petit entier m tel que n divise
2m 1. Les racines de = x n 1, ne polynme cyclotomique, sont appeles
racines ne de l unit. Elles appartiennent Yextension de corps F2m. F2m est
aussi appel le corps de dcomposition de x n 1.
F2<n est le plus petit corps contenant toutes les racines de xn 1 (elles sont
distinctes puisque x n 1 na pas de racines multiples dans F2). Dans F2m, on
a donc pour les j racines ne de lunit :
n 3
xn ~ i = Qi )
z=0
F2m possde galement une racine primitive ne de l'unit, a est dite primitive
lorsque les puissances de a permettent de retrouver toutes les autres o , ; si a
est primitive alors,
n 1
x n - l = Y [ { x - a 1)
i=0
Codes cycliques 81
Exem ple 8.10 Construisons par exemple F23, extension de degr 3 de F2. Pour
ce faire, on ajoute la racine d un polynme qui na normalement pas de ra
cine sur F2[ai]. Comme lextension est de degr 3, on cherche un polynme
irrductible de degr 3. Par exemple x 3 + x + 1 ou ai3 + x 2 + 1. Choisissons
f(x ) = x 3+ x + l obtenu, par exemple dans la table des polynmes irrductibles
de lannexe B. On a donc f ( a ) = 0 et on pose a 3 + a + 1 = 0 a 3 = a + 1.
On a une racine dans le corps 23 lments engendr par a, racine primitive,
/(ai) est le polynme minimal et on a ainsi le plus petit corps contenant a,
F2[a] = F2[x]//(ai)F 2[a:]. De plus, (1 , a , a 2) est une base de F23 au sens des
espaces vectoriels.
x n - 1 = f o ( x ) f i ( x ) . .. f t- i ( x )
Supposons que
Si 1
fi(x) = n 0e - a 2' )
.70
fi(x ) = \ \ { x - a l23)
3=0
Ci = {i2i mod n : j N)
Cb = {0 } = { 0 - 2 * } ,
Cl = {1, 2, 4} = { 2 0 = C2
C3 = { 3. 6, 5 } = {3 - 2 0
Le calcul des classes cyclotomiques montre quil existe ici un facteur de degr
1 et deux facteurs de degr 3. Remarquons que les degrs des facteurs (ici 1 et
3) divisent n 1 (ici 6). Les trois polynmes minimaux sont :
fo (x ) = x - l ,
f i ( x ) = (x a )(x a 2)(x a 4),
f 3 {x) = (x a3)(x a 6)(x a 5)
x 7 1 = (x l ) ( x 3 + x + l ) ( x 3 + x 2 + 1)
a3 = a + 1
a4 = a2 + a
a5 = c? + a + 1
a6 = a2 + 1
a7 = 1.
Alors
fi(x ) = (x a )(x a 2)(x a 4)
= x 3 + (a + a 2 + n4)x 2 + (q 3 + a 5 + a 6)x + a 7
= x 3 + x + 1,
et on trouve de manire analogue que
f 3(x) = x 3 + x 2 + l.
x 7 - 1 = (x - l ) / i ( x ) f 3(x)
do - &k
- - bn r0 r3
Les codes BCH (Bose, Chaudhuri, Hocquenghem) sont des codes cycliques
qui permettent de prvoir (en la minorant) la distance minimale du code avant
la construction.
Les codes BCH peuvent aussi tre construits sur Fg, le corps q lments, q
premier. Lorsque leur longueur n est telle que n = q1, ils sont appels codes de
Reed-Solomon. Ce sont des codes MDS (Maximum Distance Separable). Cela
signifie que d = n k + 1, o d et k reprsentent respectivement la distance
minimale et la dimension du code.
Ils sont utiliss
T h o r m e 8.16 Les codes R M (r, m) sont quivalents aux codes cycliques ten
dus.
La preuve de ce thorme est trop technique pour figurer ici. Elle fait appel a
la dfinition des codes de Reed-Muller au moyen de gomtries finies que nous
nutiliserons pas ici. Elle peut tre trouve dans [89].
C h a p it r e 9
Jusqu prsent nous navons considr que des codes qui corrigent des er
reurs distribues alatoirement. Cependant, dans le cas des disques compacts
ainsi que pour certains autres canaux (GSM, satellite), les erreurs peuvent se
succder (prsence de poussires ou de rayures sur le disque... ) Ainsi, toutes les
informations inscrites ces endroits risquent dtre altres par paquets entiers.
Nous prsentons plusieurs dfinitions des paquets ainsi que quelques mca
nismes qui en permettent la correction.
9.1 Dfinitions
6
0000011000
( Xj = 0 , si j < i ou j > i + L 1
\ Xj 7^ 0, si j = i ou j = i -(- L 1
k 0, dege(a;)=4
k = 6, dega;6e(a;) mod x 7 1 = 3
tandis que le nombre de ses classes latrales est de 215-9 = 64. Comme il ny
a que 60 motifs d'erreurs ou 61 en comptant les mots du code eux-mmes -
de paquets cycliques dtendue au plus 3, ce code est un code qui corrige des
paquets cycliques d tendue au plus 3.
En effet, si on calcule tous les syndromes x ke'(x) mod g (x) pour 1) < k < 15
avec e'{x) G {1,1 + x, 1 + x 2, 1 4- x + x 2}, on observe que les syndromes sont
tous distincts en effectuant le calcul avec Maple par exemple.
9.3 Dcodage
(2) V* > 0, calculer Si(x) = x S (x) mod g(x) jusqu trouver j tel que
deg Sj (x) < l 1 ;
51 (x ) = x S (x ) mod g{x) = 1 + x 2+ x 3 + x 4 + x 5
5 2 {x) = x 2S (x) mod g(x) = 1 + x 2+ x 4 + x 5
S',3(x) = x 3S (x) mod g(x) = 1 + x 2+ a;5
^(x) = x AS {x) mod g(x) = 1 + x2
avec deg S4 (x) = 2 < l 1. Le paquet cyclique derreur le plus probable est :
Une technique pour corriger des paquets derreurs est celle de l entre
lacement.
Habituellement, la transmission sopre par lenvoi successif de mots du
code. La technique dentrelacement quant elle, considre la transmission de
faon diffrente. Soit la matrice dont les lignes rassemblent les t mots suivants :
x 11 X21 - * x ni
X l2 % 22 % n2
X | / X 21 Xni
Le plus souvent, les mots sont mis les uns la suite des autres, i.e. ligne par
ligne. La technique dentrelacement utilise un autre type d mission qui consiste
mettre les mots colonne par colonne, tous les premiers symboles des t mots,
puis tous les seconds symboles, etc. Cette technique permet la construction
dun nouveau code partir dun code C.
D fin ition 9.3 Soit C un (n, fc)-code linaire binaire. Le code obtenu par en
trelacement de t mots de C est le code entrelac de C de profondeur t.
L intrt de cette technique rside dans le fait que les erreurs affectant des
symboles conscutifs du code entrelac des mots de C vont entacher des mots
diffrents du code, condition que t soit choisi convenablement en fonction des
statistiques d erreurs observes sur le canal.
9.6 Si r = 1, on a la matrice
xn X12 ... x lt
Ar 21 22 x 2t- i X2t
A: Ar X 31 x 3t-
101,011,001,110,100,010
011,101,001,110,010,100
Avec un retard de 1 :
101011...
*011101...
* * 00 10 0 1. ..
* ** 1 1 01 1 0. . .
* * * * 100010 . . .
* * * * *010100...
on met
Lintrt de cette technique est que jamais plus d un symbole dun mot du
code C ne se trouve dans un paquet d tendue gale n i + 1 , d o la proposition
suivante.
92 Technique d entrelacement crois
- on entrelace les mots du code avec une profondeur k>2 ; les colonnes
construites par cet entrelacement sont alors considres comme des mes
sages pour C 2 ;
-les mots du code peuvent ensuite tre entrelacs avec une profondeur de t.
Le gros avantage de ce codage en deux tapes est le suivant : C'2 peut tre
utilis pour dtecter d? 1 erreurs plutt que pour corriger. Si des erreurs sont
dceles dans un mot de C2, alors tous les symboles de ce mot sont marqus
et traits comme des symboles potentiellement incorrects. On sintresse alors
aux mots de Ci- Observons que si lon sait que n d] -f 1 symboles d un mot
c Ci sont corrects, on peut toujours retrouver les di 1 symboles restants.
En effet, car pour tout autre mot c' G C i, d ne peut tre gal c sur les
n di + 1 symboles corrects car lensemble des mots de Ci doivent diffrer sur
au moins di positions. En consquence, si chaque mot de Ci contient au plus
di 1 symboles marqus et si on suppose que tous les symboles incorrects sont
marqus, alors les mots du code seront dcods correctement.
Quelle est ltendue des paquets qui peuvent tre corrigs par ce moyen?
On suppose C2 entrelac de profondeur s. On suppose de plus que chaque mot
de Ci et chaque mot de C2 est affect par au plus un paquet derreurs. Si un
paquet dtendue d au plus s(d2 1) apparat, alors il sera altr sur au plus
d2 I positions de chaque mot de C2. Toutes ces erreurs sont dtectes et tous
les symboles des mots du code affects seront marqus.
Si s < d] 1, alors chaque mot de Ci contient au plus di 1 symboles
marqus. Selon lhypothse que chaque mot du code nest affect que par un
seul paquet d erreurs (au plus), les symboles restants sont donc corrects. Par ce
qui prcde, on peut corriger les symboles marqus et on obtient le thorme
suivant
Codes correcteurs de paquets derreurs 93
l 1110\
/ uo\
Id4 1101
G, = g2 = Id3 101
1011
\ 011/
V OUI/
ci = m x.Gi = 10001110
c2 = m2.G2 = 11000011
c3 = m3.G3 = 10100101
111,010,001,000,100, 101,110,011
100,110,101,010.001,011,
011,000,001,011,010,001,...
wx = 001000
w2 = 100101
w3 = 111011
Observons que, par rapport c[, c'2 et c'3 respectivement, chacun de ces mots
na des erreurs que sur les 2 premires positions. C2 dtecte les erreurs dans
chacun de ces trois mots en calculant leur syndrome w\H pour 1 < * < 3 qui
est non nul. On marque donc lensemble des 18 symboles en les remplaant par
des *.
En supposant quil ny ait pas dautre erreur et que nous navons pas d autre
symbole marqu, on retire finalement leffet du premier entrelacement :
C\ = ***01110
c2 = * * -*00011
C3 = ***00101
(1 1 1 0^
1 1 0 1
1 0 1 1
0 1 1 1
id4
V )
00001110 1 1 1
!
10001110 0 0 0 0)
01001110
11001110
00101110
10101110
01101110
11101110
Dans ce chapitre, nous proposons une brve introduction aux codes convo
lutifs. Ils diffrent des codes que nous avons vus prcdemment : ce ne sont
pas des codes en bloc. Il sagit en fait de codes longueur variable que nous
avions voqus dans le chapitre 1. fis sont intressants de deux points de vue.
Dune part, ils sont grandement utiliss pour sur-coder des messages cods
par blocs au pralable. C est notamment le cas pour certaines communications
satellitaires et surtout pour la norme GSM des tlphones cellulaires. D autre
part, ils sont la base des turbo-codes qui sont une gnralisation des codes
convolutifs et qui doivent tre utiliss dans la prochaine norme UMTS de tl
phones cellulaires. La grande particularit des turbo-codes est quils atteignent
la borne de Shannon sans que lon sache encore expliquer pourquoi. Un grand
effort de recherche est actuellement men pour tenter de dmontrer la raison
pour laquelle les turbo-codes sont des codes correcteurs d erreurs optimaux au
sens de Shannon.
Notre ambition dans cet ouvrage ne va certainement pas aussi loin. Nous
nous contentons de dcrire les codes convolutifs au moyen d un exemple simple
pour faire comprendre leur mcanisme de codage ainsi que lalgorithme de
dcodage conu par Viterbi [92]. Pour en savoir plus sur les codes convolutifs,
nous renvoyons le lecteur un ouvrage exhaustif rcent [51].
*
10.1 Elments de base
0=
C orrig
10.2 Codage
Le fait que les polynmes soient premiers entre eux assure que le dcodage se passe bien.
Introduction aux codes convolutifs 97
m (x) = 1 + x 2
- m'(x) = l + x + x 2 + x 3 + . . . + x k = J2i=o
Corrig
((1+ x 2)m '{x), (1 + x + x 2)m '{x)) = (l+ x + .T fc K + x fc+2, l + (!Ci=2 x'l) + x k+2)
Preuve c(m .(x))+ c(m '(x)) = (p (x )m (x ),q (x )m (x ))+ (jp (x)m '(x),q (x)m !(x)) =
(jp{x)(m(x) + m '(x)), q(x)(rn(x) + m '(x ) )) qui est le mot du code correspondant
au message m (x) + m '(x).
98 Codage
Exercice 10.3 Quels sont les mots binaires entrelacs mis pour :
Corrig
-1 1 01 00 01 11
-11 10 (01)fc- ] 10 11
mo c0 = p 0 m 0 Ci = qouio
mi c2 = pom i + P \ m 0 C3 = omi + rno
m2 c4 = pom 2 + p im 1 + p2m 0 c5 = q0 m 2 + i m i + q2 m 0
On en dduit que le codage peut se faire bit bit avec une mmoire borne
dau plus k + 1 bits.
Introduction aux codes convolutifs 99
Comme chaque bit du message (lentre) on peut associer les deux bits
correspondants du mot du code (la sortie), on peut construire un arbre binaire
potentiellement infini appel arbre de codage. Ses aretes sont tiquetes par
les mots binaires de la sortie (des lments de (F2)2). Dans cet arbre, lentre
permet de slectionner une branche et la sortie est dtermine par les tiquettes
des artes. Une entre nii = 0 prolonge le chemin sur larte de gauche et une
entre m, = 1 sur celle de droite. La figure 10.1 illustre le parcours de larbre
pour le mot d entre 1011.
Comme le codage se fait bit bit avec une mmoire borne, il est possible
dengendrer larbre de codage potentiellement infini par un mcanisme fini.
100 Codage
Du fait que larbre de codage admet une reprsentation finie, il est, possible
de construire un diagramme de transition dtats ou codeur qui va fonctionner
(2 )
la manire dune machine de Mealy et permettre le codage dun message
fourni en entre . Ce diagramme nest autre quun graphe orient dont les arcs
sont tiquets par un couple valeurs dans F2 x (F2) 2. La premire composante
de ce couple reprsente le symbole lu sur le mot d entre (le message) et la
seconde composante le codage de ce symbole, c est--dire la sortie. De cette
manire, le codage dun message m pourra tre effectu la vole.
Chaque tat (ou sommet du graphe) du codeur va mmoriser les k derniers
bits lus sur lentre, k tant le plus grand degr des polynmes gnrateurs. En
fonction du nouveau bit lu sur lentre (de la gauche vers la droite), le codeur :
- change dtat ;
(2)
Une machine de Mealy est un automate fini muni dune fonction de sortie sur les transi
tions [48].
Introduction aux codes convolutifs 101
10
Le but du codage convolutif (ainsi que celui des autres codes correcteurs
derreurs) est de permettre la correction des messages cods lorsque ceux-ci
traversent un canal (satellitaire, tlphonique) qui peut ajouter des erreurs.
Le destinataire reoit un mot binaire r qui est la somme de la suite binaire
correspondant au mot du code mis c et de la suite binaire correspondant
lerreur e :
r = c+ e
Il doit alors dcoder r pour tenter de retrouver c.
Pour ce faire, le destinataire rsout le problme d optimisation suivant :
tant donn r, trouver le mot binaire c qui appartient au code telle que la
distance entre r et c soit aussi petite que possible. Si cette distance est nulle,
102 Capacit de correction
d(C) = min ( w ( c ) }
cC,ct&0
P reu v e Supposons d(C) > 21. On reoit le mot r alors que le mot du code c a
t mis. On dcode r en c G C, le plus proche mot du code de r pour la distance
de Hamming. Si r = c + e pour e G t , alors d//(r, c) < /.. Le mot du code c
satisfait aussi dn{r, c) < t. D o d#(c, c) < djj(r, c) + djj (c, r) < 2 1 < d(C), et
c = c.
Rciproquement, supposons que d(C) < 2t. Soient c et c' deux lments de
C tels que du(c, d ) = d(C). On dfinit r comme suit :
autres que le cycle de longueur unit (qui correspond la boucle sur ltat
0 . . . 0). On pourra dcoder convenablement ds lors que le poids des tiquettes
de la fonction de sortie de lun des cycles sera strictement suprieur 2t (o t
correspond au poids de lerreur). On prend la longueur p du plus court cycle (en
termes de nombre d arcs) qui vrifie cette proprit et la taille l = 2p puisque
la fonction de sortie renvoie deux bits par arc.
10.4 Dcodage
Afin de dcoder plus facilement quen cherchant parmi tous les mots du code
celui qui est le plus proche du mot reu, on construit un treillis. Pour ce faire,
on reprend larbre de codage dfini prcdemment puis :
-on identifie les sommets de larbre qui portent la mme tiquette lorsquils
sont la mme profondeur en conservant les artes et les tiquettes.
ne conserve quun seul chemin : celui qui est le plus proche de r en calculant la
distance de Hamming entre chaque sous-chemin et r. On efface les autres car
ils ne peuvent mener un mot du code. On continue de cette manire jusqu
arriver la fin du mot reu r ltat 00, pour lequel on ne dispose que dun
chemin entrant. H suffit alors de remonter les niveaux pour obtenir le mot du
code le plus proche du mot reu.
Corrig Dans la figure 10.5 ne sont ports que les sous-chemins slectionns
par lalgorithme de Viterbi. Les distances de Hamming entre les sous-chemins et
le message reu sont indiques par les chiffres entours. Le chemin qui minimise
la distance et qui correspond au dcodage est indiqu en gras. En lisant le mot
qui tiquette le chemin en gras, on corrige le message reu en 11 01 11.
10
1
11 0o0
3
o
c
11
Dfinition 11.1 Le code t-raccourci d un code C est le code not C' qui est
lensemble des mots x t+\ . . . x n tels que 0 . . . 0xt+ i . . . x n G C.
Comme pour les codes cycliques, le choix du polynme gnrateur est cru
cial. Il faut en effet que e(x), le polynme de lerreur, ne soit pas un multiple
de g(x), le polynme gnrateur. Par exemple, si une seule erreur est apparue,
e(x) = x 1. En choisissant g(x) de telle sorte de les coefficients x k et a:0 soient
non nuls, e(x) ne peut tre multiple de g(x). On a alors les proprits suivantes
pour la dtection des erreurs.
P roprit 11.4
-O n peut dtecter les erreurs de poids deux si g(x) admet un facteur ayant
au moins trois termes.
CRC-8 x8 + x2 + X + 1
CRC-10 x 10 + x9 + x 5 + x4 + x + 1
CRC-12 x 12 + x 11 + x 3 + x2 + 1
C RC-16 x 16 + x 15 + x 2 + 1
CRC-CCITT x 16 + x 12 + x 5 + 1
CRC-32 x32 + x 26 + x 23 + x 22 + x 16 + x 12 + x n +
x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1
Aprs lanarchie du dbut des annes 1980 o chaque pays d Europe expri
mentait son propre systme de tlphonie mobile, une tude franco-allemande
a t initie en 1981 pour le dveloppement d une approche commune. Celle-ci
a dbouch sur la cration d un groupe d tude appel Groupe Spcial Mobile
dont le but tait le dveloppement d un systme europen de communication
mobile. Les objectifs taient multiples et incluaient une bonne qualit subjec
tive de la parole, un cot de service et de terminaux minimal et une possibi
lit dextension des services. La premire phase de spcification de ce groupe
d tude a t publie en 1990 et la commercialisation a suivi rapidement. Les
quelque 8000 pages de recommandations pour amliorer la flexibilit et linno
vation et proposer des standards sont disponibles auprs de lETSI (European
Tlcommunication Standards Institute).
Signal de parole
_____________ T______________
Code
(codage de source :
numrisation du signal)
________ Y________
codage de canal
(protection contre
les erreurs)
; _____________ T_____________
entrelacement
_____________ T______________
multiplexage et
construction de burst
chiffrement
T
modulation
La figure 11.2 prsente les diffrents traitements subis par une trane de
parole de 20 ms.
signal de parole
^ code de parole ^
260 bits
^ codage de canal ^
456 bits
^ entrelacement
affectation des
C ntervalles de temps.
260 bits
182 78
50 132
i i
i i
53 132 4
convolutif i
3 7 8 bits 78
C entrelacement
- les codes convolutifs qui assurent une bonne correction des erreurs.
Rappelons que le code de la parole fournit un bloc de 260 bits pour chaque
tranche de 20 ms du signal. On a dtermin exprimentalement trois catgories
o les bits de ces blocs ont une importance plus ou moins grande :
Application des codes correcteurs dans lindustrie 115
Pour protger ces 456 bits des erreurs par paquets, on effectue ensuite un
entrelacement. Les 456 bits sont diviss en 8 blocs de 57 bits qui sont transmis
dans 8 sous-blocs (ou demi-lots) successifs, A q, . . . , A 7 (fig. 11.4).
1 b 0 bl b 2 b 3 b 4 b 5 b 6 b 7
2 b 8 b 9 b 10 b ll b 12 b 13 b 14 b 15
3 b 16 b 17
Aq Al a2 a3 a4 a5 a6 A7
8 demi-blocs
Chaque sous-bloc est ensuite associ avec un sous bloc de la trame de parole
prcdente (pour les sous-blocs 0,1,2 et 3) ou de la trame suivante (pour les
sous-blocs 4,5,6 et 7). Cet entrelacement cheval est appel diaqonal.
La dernire tape de l'entrelacement consiste mlanger lintrieur dun
lot, les deux sous-blocs. Au lieu dassocier un des deux champs dinformation
chaque sous-bloc, on prfre intercaler finement les deux parties. Ainsi les bits
116 Codes de transmissions satellitaires
pairs d un lot vont correspondre une trame de parole (la plus rcente) et les
bits impairs la trame de parole prcdente.
Il s'agit du schma gnral et certains dtails ont t laisss de ct. Le
lecteur intress pourra se reporter [59] pour plus d'informations.
Nous prsentons dans cette section les codes utiliss par les sondes Voyager.
En 1977, ces sondes sont alles prendre des photos de Jupiter et de Saturne,
des distances de plusieurs millions de kilomtres. Pour cela, nous nous sommes
inspirs de [95].
Les signaux mis taient de deux types :
-d e s images construites comme des tableaux de 800 x 800 pixels avec des
couleurs sur 8 bits ;
(1) C'24 est de paramtres (24,12,8) ; il comprend 212 = 4096 mots du code ;
t(B)
v i< w
r g\ (x) = 1 + x + x 3 + x 4, + x e
\ 9 2 {x) = 1 + x s 4- x 4 + X 5 + X-6
Complexit
C h a p it r e 12
Thorie de la complexit
La thorie de la complexit est une discipline rcente. Les premiers pas ont
t faits avec Rabin, McNaughton et Yamada dans les annes 1960 puis en 1965
nat le terme complexit dfini par Hartmanis et Stearns [42]. Ils introduisent
le cadre formel de la complexit en utilisant des modles abstraits de machines
et proposent les premiers rsultats sur la structure des classes de complexit.
Edmonds dfinit en mme temps la notion de bon algorithme comme celle
dun algorithme dont le temps de calcul est born suprieurement par un po
lynme fonction de la taille du codage de lentre.
En 1971, Cook introduit les termes P et NP; il montre la NP-compltude
du problme de la satisfiabilit des formules boolennes et que tous les pro
blmes NP-complets se rduisent au problme de la satisfiabilit des formules
boolennes.
En 1972, Karp utilise la notion de rduction en temps polynomial pour
montrer que 21 problmes sont NP-complets.
Depuis, une des grandes conjectures de linformatique thorique est de d
terminer si P = NP. C est dailleurs un des problmes du millnaire dont
la rsolution est mise prix un million de dollars par la fondation Clay
(www.claymath.org). Cette conjecture pose que tout langage accept par un
algorithme non dterministe en temps polynomial lest galement par un algo
rithme dterministe en temps polynomial.
Le terme de donne est employ pour dcrire lensemble des informations qui
doivent tre spcifies pour dcrire le problme. Dans le cas de la factorisation,
il sagit tout simplement de lentier n. Pour le problme de la satisfiabilit
des formules boolennes qui est voqu la fin de ce chapitre, il sagira dun
ensemble de variables boolennes et d un ensemble de clauses.
Observons que dans le cas du problme de la factorisation, pour une donne
fixe, on attend un rsultat : m, facteur de n, ou bien une garantie de sa
primalit. D sagit d un problme de calcul.
Cependant, pour dfinir les classes de complexit, on ne sintresse pas au
rsultat dun calcul mais sa dcidabilit. En d autres termes, une fois pose
la donne d un problme, on se pose une question dont les seules rponses
possibles sont oui et non.
Donne n un entier ;
Question n est-il pair ?
Une fois quun problme est formul de cette manire, il sagit d un problme
de dcision. Reste le coder sous la forme dun langage.
De cette manire, il est plus ais de parler des donnes positives du problme
qui concident avec lensemble des mots qui appartiennent (II).
On parlera donc indiffremment d un problme de dcision ou du langage
correspondant [35]. Pour dcider un problme, on va modliser le fonctionne
ment de lalgorithme qui le rsout au moyen des machines de Turing.
Thorie de la complexit 123
- 3 - 2 - 1 0 1 2 3
^ ruban
>
tte de lecture/criture
t= 0 t = l
E est ltat initial, qy celui dacceptation, c/v celui de rejet. Les autres tats
sinterprtent comme suit : E o 011 efface autant de a que de 1, A avant et aprs
Thorie de la complexit 125
D finition 12.1 Le langage des mots accepts par une machine de Turing M
est dfini par :
TM : N >N
n i max { t : 3x E E* tel que |x |= n et pour lequel
le calcul de M sur lentre x sarrte aprs t transitions}
La classe P du temps polynomial est dfinie dans [38] comme lensemble des
langages L e P, tels quil existe une machine de Turing dterministe M et un
polynme p vrifiant les deux conditions suivantes :
Donne E un alphabet fini, m un mot sur {a, 6}* appel le motif et t un mot
sur (a, 6}* appel le texte.
Question m est-il un facteur de t ?
L1 L2 Q El E2 Al A2
i a a i a a
i b b i b b
i a B f a B
i b B b B - -
B ba
t ab
_L
abab
baB
On accepte
12.5.1 Langages NP
On dit quun langage L est dans la classe du temps polynomial non dtermi
niste (note NP pour nondeterministic polynomial time) sil existe une machine
de Turing non dterministe M et un polynme p satisfaisant la condition : sur
lentre x G E*, il existe un calcul de M qui sarrte dans un tat d acceptation
aprs au plus p(||) tapes si et seulement si x E L.
Il est clair que, puisque les machines de Turing dterministes sont un cas
particulier des machines de Turing non dterministes, on a linclusion P C NP.
128 Classe du temps polynomial pour les modles non dterministes
(1)pour tout x G L. il existe une indication y G E* telle que \y\ < (/(|:r|) ;
(2) sur lentre ( x , y), x , y G T,*, la machine V sarrte dans un tat daccepta
tion aprs au plus p{\x\) tapes si et seulement si x G L.
P reu v e Puisque L G NP, par dfinition de la classe NP. il existe une machine
de Turing non dterministe A et un polynme q tels que A dcide L en un
temps born par q.
Pour toute entre x accepte telle que || = n , il existe une indication y G T,*
telle que \y\ < q ( n ) qui amne ltape de vrification de la machine de Turing
rpondre oui en au plus q ( n ) pas de calculs. Le nombre de telles chanes possibles
reprsentant lindication est On construit alors lalgorithme 12.1.
Cet algorithme ne sarrte avec la rponse oui que sil existe une indication
qui mne un calcul acceptant dans la limite du temps imparti, sinon il rpond
non. Il est bien dterministe et de complexit en temps q(n)\T,\q^ = 0 ( 2 P^ )
pour un polynme p.
Le problme obtenu par lajout dune ngation dans la question dun pro
blme de dcision est appel son complmentaire.
La classe des problmes de dcision complmentaires de ceux d une classe C
est dnomme co-C. Par exemple, la classe complmentaire de NP est la classe
co-NP. Les dfinitions relatives la classe co-NP sont calques sur celles de NP.
On illustre cette dfinition avec le problme de la primalit.
Donne un entier n.
Question n est-il premier?
En faisant la ngation de la question, on obtient le problme de dcider si
un entier est un nombre compos :
Donne un entier n.
Question n est-il compos?
(2) f ( x ) e L 2 ^ x e Li.
E* ^ v** ^ v**
1 * 2-i2 ^3
(1) si L 2 g P, alors L i G P ;
(2) si Li $ P, alors L 2 0 P.
Thorie de la complexit 131
Preuve
Exem ple 12.6 Par exemple, la clause {mi,3, s } <=* u V -<U3 V ug est vraie
pour t{v,\) = 1 ou t(ug) 0 ou t(ug) = 1.
Ui u2 (ui V -t 2 ) A ( u2 V ~ 'M i)
0 0 1
1 1 1
0 1 0
1 0 0
montrer que L 6 NP ;
1) (1, 2, 1) ( 1, 2, 1)
2) (1,3,2) (1.3.2)
3) (2,1,4) (2,1,4)
4) (2,2,3) (2.2.3)
5) (3,1,1) (3,2,1)
6) (4,4,4) (4.4.4)
Complexit des problmes de thorie des codes 135
1 2 3 4 1 2 3 4 1 2 3 4
121 1 0 0 0 0 1 0 0 1 0 0 0
132 1 0 0 0 0 0 1 0 0 1 0 0
214 0 1 0 0 1 0 0 0 0 0 0 1
223 0 1 0 0 0 1 0 0 0 0 1 0
311 0 0 1 0 1 0 0 0 1 0 0 0
444 0 0 0 1 0 0 0 1 0 0 0 1
Dans le mme article [8], Berlekamp, McEliece et van Tilborg ont galement
prouv que le problme de dcider sil existe un vecteur de poids donn est aussi
un problme NP-complet. L nonc exact de ce problme est le suivant.
136 La NP-compltude du problme de la distance minimale sur F 2? "
- O n suppose que la matrice H est de rang plein i.e. que les colonnes de
H contiennent une base de F2 et que w < m 1. En effet, si H est de
rang plein et que w > m, la rponse la question du dcodage linaire est
trivialement vraie.
O11 suppose aussi sans perte de gnralit que les colonnes de H sont dif
frentes. Sinon, il est toujours possible de former en temps polynomial une
Complexit des problmes de thorie des codes 137
Rappelons quun (??., fc)-code linaire est dit Maximum Distance Separable si
sa distance minimale d atteint la borne de Singleton d = 11 k + 1 (voir [96]).
On dduit immdiatement de cette condition sur la distance minimale que si
on savait trouver en temps polynomial la distance minimale dun code linaire
binaire, on saurait rsoudre le problme de la somme de sous-ensembles dans
un corps fini en temps polynomial. Plus prcisment, on considre le problme
suivant.
Distance minimale sur F2 (M D 2)
Donne Un entier m > 0, une r x n matrice H sur F2, un entier m > 0.
Question Existe-t-il x G (F2) tel que .-r4/ / = 0 et w(:c) < uj ?
La preuve de ce thorme est trop technique pour tre expose dans cet
ouvrage.
C h a p it r e 14
d c b a
a 0 0 0 1
0 0 0 1
b <3 0 0 1 0
b U 0 0 1 0
c <5 0 1 0 0
c te 0 1 0 0
d *7 1 0 0 0
d te 1 0 0 0
c3 c2 Cl d c b a
a h 0 1 1 0 0 0 1
a ti 0 0 0 0 0 0 1
b <3 0 1 0 0 0 1 0
b u 1 0 1 0 0 1 0
c tb 1 0 1 0 1 0 0
c te 0 0 0 0 1 0 0
d tr 1 1 0 1 0 0 0
d *8 0 0 0 1 0 0 0
C3 c2 Cl d c b a
a tl 0 1 1 0 0 0 1
a t2 0 0 0 0 0 0 1
b t3 0 1 0 0 0 1 0
b u 1 0 1 0 0 1 0
c ts 1 0 1 0 1 0 0
c <6 0 0 0 0 1 0 0
d f7 1 1 0 1 0 0 0
d h 0 0 0 1 0 0 0
Ci tg 0 0 1 0 0 0 0
Ci 11 0 0 1 0 0 0 0
c2 tu 0 1 0 0 0 0 0
c2 f 12 0 1 0 0 0 0 0
c3 tl3 1 0 0 0 0 0 0
c3 tl4 1 0 0 0 0 0 0
Exem ple 14.4 Une valuation qui satisfait x est abcd. On choisit donc les tailles
t i, t i, t e, t s , t g, t n , t i 2 , t i 3 et 114 pour que leur somme soit 3331111.
Exemple 14.5 Si on choisit lensemble de tailles (O , t3, ts, t7, tg, fio, tu , tm}
dont la somme est 3331111, une valuation qui satisfait x est bcd.
Primalit
Donne un entier n.
Question n est-il premier ?
Il sagit d un problme algorithmique par excellence. Il a t tudi par un
grand nombre de chercheurs et il est encore loin dtre rsolu.
Beaucoup de critres permettent de vrifier si un entier est premier. Par
exemple, le test de Lucas.
n 1
Test de Lucas n est premier ssi 3g G Z * tel que gn~ = 1 mod n et g p ^ 1
mod n pour tout p facteur premier de n 1.
si n = 1 alors accepte ;
si n > 2 est pair alors rejette ;
si n > 2 est impair alors choisir x, 1 < x < n ;
vrifier si x n 1 = 1( mod n) ;
deviner une factorisation de n 1, n Pi\
vrifier si n 1 = pi ;
pour 1 < i < k faire
n 1
vrifier si pi est premier et x ^ ^ 1( mod n) ;
fpour
accepte si aucun test nest faux.
Une autre preuve de ce thorme dmontr lorigine par Pratt est donne
dans [75] o est galement discute limportance de ce rsultat.
- Si a et b sont donns, le cot du calcul de ab par la mthode des carrs [93] est
de log(6) multiplications, chacune dentiers d au plus log(n) bits. En utilisant
une multiplication par transforme de Fourier rapide, chaque multiplication
cote log(n) log(log(n)) oprations. Comme b < n, on a log(6) < log(log(n))
donc le cot du calcul de ab est log(n) log(log(n))2. Il est classique de ngliger
les termes log(log) pour la complexit asymptotique, donc on obtient un cot
de 0 (lo g (n )) pour vrifier avec a et b donns.
- Si seulement b est donn et pas a, alors en utilisant une recherche par dicho
tomie binaire sur lintervalle [l, n] pour a, il ny a que log(n) valeurs de a
essayer, chacune cote 0 (lo g (n )), donc on obtient un cot de 0 (lo g (n )2)
pour chercher avec seulement h donn.
-q\r - 1
mod r $ (0 ,1 }
-pgcd. (n, b b') = 1 V6, b' e S; b^b
- (9+{ | f > n2^
- ( x + b)n = x n + b dans l anneau 7jn [x]/{xr 1)
Pour plus de dtails, le lecteur intress peut aller visiter le site Web
ladresse : h ttp : / / www.u tm .edu /research /p rim es.
{
m si p premier et g primitif mod p et m
lunique entier tq 0 < m < p et g "1 = n
0 sinon
Cryptologie
C h a p itr e 15
Introduction la cryptologie
historique
15.1 Introduction
Pour utiliser un tel systme de chiffrement, les deux parties doivent sen
tendre sur une cl particulire K quils conservent secrte. Lmetteur envoie
un cryptogramme C = E ( K , M ) qui est reu par le destinataire qui effectue
lopration D ( K. C) = M pour retrouver le clair M.
Les premiers systmes de chiffrement cl secrte que nous tudierons sont
monoalphabtiques, ce qui signifie quune mme lettre donne du clair est tou
jours chiffre en la mme lettre du cryptogramme.
Q r t Q L/rJ R T
11 26 11 (1.0) 0 (0,1) (1,0)
26 11 4 (0,1) 2 (1,0) ( - 2 ,1 )
11 4 3 (1,0) 2 ( - 2 ,1 ) ( 5 ,- 2 )
4 3 1 ( - 2 ,1 ) 1 ( 5 ,- 2 ) ( - 7 ,3 )
3 1 0 ( 5 ,- 2 ) 3 ( - 7 ,3 ) (2 6 ,-1 1 )
1 0 ( - 7 ,3 ) (2 6 ,-1 1 )
Nous prsentons dans le tableau 15.1 une mthode gnrique pour tous les
chiffres monoalphabtiques, mme sils peuvent toujours tre cryptanalyss par
154 Cryptanalyse des chiffres monoalphabtiques
(2) Il compte les frquences dapparition des couples de lettres (ou bigrammes).
Le bigramme le plus frquent en franais est et. Il en dduit ainsi la lettre
(3) U fait traduire par lordinateur la partie du texte correspondant aux lettres
dj identifies laissant des blancs pour les lettres chercher. Le texte est
toujours inintelligible mais Mr X peut deviner quelques lettres supplmen
taires. Aprs quelques itrations de ce procd, il est capable de dcrypter
le texte.
Rsolution d e ax = b mod n
{4a + b = 23 mod 26
19a + 6 = 20 mod 26
C orrig
{ 4a + b = 23 mod 26
19a + b = 20 mod 26 ^ { 15a = 23 mod 26
156 19 mod 26
{a = 7.23
b = 7.19
mod 26 = 5
mod 26 = 3
- pour que le dchiffrement soit unique, les ensembles images des lettres du
message clair doivent tre disjoints ;
Chiffre de Vigenre
Chiffrement
abcdefghijklmnopqrstuvwxyz abcdefghijklmnopqrstuvwxyz
ABCDEFGHIJKLMNOPQRSTUVWXYZ NOPQRSTUVWXYZABCDEFGHIJKLM
BCDEFGHIJKLMNOPQRSTUVWXYZA OPQRSTUVWXYZABCDEFGHIJKLMN
CDEFGHIJKLMNOPQRSTUVWXYZAB PQRSTUVWXYZABCDEFGHIJKLMNO
DEFGHIJKLMNOPQRSTUVWXYZABC QRSTUVWXYZABCDEFGHIJKLMNOP
EFGHIJKLMNOPQRSTUVWXYZABCD RSTUVWXYZABCDEFGHIJKLMNOPQ
FGHIJKLMNOPQRSTUVWXYZABCDE STUVWXYZABCDEFGHIJKLMNOPQR
GHIJKLMNOPQRSTUVWXYZABCDEF TUVWXYZABCDEFGHIJKLMNOPQRS
HIJKLMNOPQRSTUVWXYZABCDEFG UVWXYZABCDEFGHIJKLMNOPQRST
IJKLMNOPQRSTUVWXYZABCDEFGH VWXYZABCDEFGHIJKLMNOPQRSTU
JKLMNOPQRSTUVWXYZABCDEFGHI WXYZABCDEFGHIJKLMNOPQRSTUV
KLMNOPQRSTUVWXYZABCDEFGHIJ XYZABCDEFGHIJKLMNOPQRSTUVW
LMNOPQRSTUVWXYZABCDEFGHIJK YZABCDEFGHIJKLMNOPQRSTUVWX
MNOPQRSTUVWXYZABCDEFGHIJKL ZABCDEFGHIJKLMNOPQRSTUVWXY
Carr de Vigenre
On chiffre ensuite de la manire suivante : la lettre du mot-cl dfinit la ligne
du carr utiliser et la lettre du message clair la colonne. Ainsi, limage de la
premire lettre -p- se trouve sur la ligne commenant par V dans la colonne du
p, soit K. On chiffre donc polyalphabetique en KSYSSGTUUTZXVKMZ.
D chiffrem ent
Lide de ce test repose sur le principe suivant : si on rpte une mme suite
de lettres dans le clair une distance qui est un multiple de la longueur de la
cl, le cryptogramme correspondant rptera aussi la mme suite de symboles
(ou squence). Par exemple, dans le message le s s a n g lo ts lo n g s d e s v io lo n s -
s o n t le s chiffr avec la cl CLE, on chiffre les deux l e s du message clair de la
mme manire.
On en dduit donc une mthode de cryptanalyse. Si Mr X trouve dans le
cryptogramme des apparitions multiples de la mme suite de symboles, il peut
en dduire que la distance qui spare ces squences est probablement multiple
de la longueur de la cl. Nous savons en outre que lapparition de deux mmes
symboles dans le cryptogramme ne nous fournit aucune information sur la
longueur de la cl. De mme, des squences identiques de longueur 2 peuvent
apparatre accidentellement. Par contre, des squences identiques de longueur
3 nous fournissent un moyen effectif pour dcouvrir la longueur de la cl.
Considrons le cryptogramme NPWUARIWSVDPDYKUOIUGMQWSPDWQYXNPWo la
mme squence NPW de longueur 3 apparat 2 fois. La distance entre ces 2
squences est de 30. Mr X peut en dduire que la longueur de la cl divise 30.
Elle peut donc tre de longueur 2, 3 ou 5 (ou un multiple de ces valeurs).
Pour un cryptogramme plus long, il y aurait eu plus de squences de lon
gueur 3 et il aurait construit le tableau 15.3.
Dans le tableau 15.3, le plus grand commun diviseur des distances est 5.
Un cryptanalyste optimiste dclarerait que la longueur de la cl est 5. Un
cryptanalyste prudent dirait seulement que la longueur de la cl la plus probable
est 5. U justifierait sa prudence de la manire suivante :
Pour ces raisons, nous dcrivons une autre mthode qui, combine au test
de Kasiski, nous fournira une meilleure indication sur la longueur de la cl.
/ = E i = i ni ( m ~ 1)
i(n 1)
Si on calcule cet indice pour un texte qui a t chiffr avec un chiffre mono-
alphabtique, la valeur ne changera pas puisque la distribution des frquences
dapparition des lettres est inchange. Par contre, si on le calcule pour le mme
texte chiffr par un chiffre polyalphabtique, on remarque que cette valeur d
crot en fonction de la longueur l de la cl. Pour ce faire, on arrange le texte
en colonnes de la manire suivante :
lettre ki ki k2 h
du mot-cl
1 2 l
indice de la l 1 1+ 2 .. 21
position du 2/ + 1 21 + 2 3/
texte
Dans chaque colonne, tout se passe comme si on avait chiffr au moyen dun
chiffre additif. On peut alors calculer la probabilit pour quune paire de lettres
tires au hasard soient identiques :
Justification
Dans une mme colonne, la probabilit qui nous intresse est Xw=i P =
0,074 (ou 0,065 pour langlais) car un chiffre additif ne change pas la distri
bution des lettres. Il suffit de calculer la somme des carrs des probabilits
associes aux frquences du tableau 15.1.
Dans des colonnes diffrentes, il sagit de deux chiffres monoafphabtiques
qui ont t choisis arbitrairement et deux fettres ne peuvent tre gaies que par
accident. La probabiiit de tirer deux fois fa mme iettre est X ii=i Pi = HZ =
26 2^2 () = 0,038 si on suppose tes lettres uniformment distribues sur
lintervalle 1...26.
Reste compter le nombre de paires de lettres dans une mme colonne puis
dans des colonnes diffrentes
Dans une mme coionne : fa coionne est choisie par fa premire lettre pour
laquelle on dispose de n choix possibles. Une fois slectionne la colonne, il
nous reste faire un choix parmi (n/l) 1 lettres, d o le nombre de paires
dans une mme colonne :
i(n l)
C i - ) / - ~2l
n2(l 1)
(-> 2
n(n l) n2(l 1)
2l J -0 ,0 7 4 + - ->2/ 0 ,U38
et pour le franais :
^ 0.036/1 rii(rii 1)
(/i 1)7 0.038/t + 0.074 n(n 1)
Dtermination de La cl
Une fois connue la longueur l de la cl, Mr X sait que les symboles aux
positions 1, l + l , 21+ 1... ou 2 , 1+2, 21+2 . . . ont t obtenus au moyen du mme
chiffre additif. Il ne reste plus qu appliquer les mthodes vues prcdemment
pour cryptanalyser un chiffre monoalphabtique additif.
Une autre grande catgorie de chiffres historiques est celle des chiffres
transposition. Dans ces derniers, au lieu de faire des substitutions de lettres
comme prcdemment, on va modifier la position relative des diffrentes lettres
du clair pour obtenir le cryptogramme, un peu la manire d un anagramme.
Ainsi, une transposition ralise une permutation des caractres clairs. Dans
ce cas, il doit obligatoirement y avoir correspondance entre lalphabet des clairs
et lalphabet des cryptogrammes : A c = A m -
/ : Am A m
r] : -> Z
Ci = f(rrii) = m v(i) Mi, 0 < i < \m\
On inscrit ensuite les colonnes prises dans lordre dfini par la cl pour
obtenir le cryptogramme rang par groupe de cinq lettres :
CTINT XITEA SERNP FEIEU NF.LF.H LCSET
BETNT TNLTF ESRAN AINOA NULEF PNOLI
EHESU AXEGX IOOFC ELCRR IMIIP FLEQR
ETIEM TTRET ER
15.6.2 Cryptanalyse
De tels chiffres ont eu leur heure de gloire la fin du 18e sicle et au dbut
du 19e dans diverses armes europennes.
Cryptologie technique cl
secrte
P r ( M |C) = P r ( M ) = ^ Pr(K)
K Ek (M)=C
cls
Une autre application de la condition du secret parfait est prsente dans [77]
o il est crit que des espions russes auraient t capturs en possession de blocs
de papier o taient inscrits des cls jetables. Aprs avoir chiffr un message,
lespion est suppos dtruire la page du bloc aprs avoir utilis la cl inscrite.
Ensuite, mme si le cryptogramme est intercept, il est formellement impossible
de cryptanalyser le texte pour incriminer lespion. Lide de la preuve est simple.
Le cryptogramme intercept C ne fournit au cryptanalyste aucune information
sur M puisque C peut provenir de nimporte quel message M (pourvu que K
soit gal C M ).
Le chiffre de Vernam est donc formellement sr au sens de la thorie de lin
formation car un cryptanalyste ne peut avoir suffisamment d information pour
dcrypter le cryptogramme mme en ayant une puissance de calcul illimite
sa disposition.
Si la sret de ce chiffre est absolue, elle est nanmoins difficile mettre en
uvre puisquil est ncessaire dengendrer des cls parfaitement alatoires de
grandes tailles, de les stocker et de les partager avec le destinataire du message.
En consquence, le chiffre de Vernam est rarement utilis. Le plus bel exemple
de son utilisation est le tlphone rouge qui relie Washington Moscou.
lA RlA plA lA lA r r
A A
rI
V SJ p E I
r
i O s I O O u S R H
\\E u
W\ u\ L \
S Y M T R H E
E
Y P V \P S \T W
Chiffrem ent
Dchiffrem ent
clair correspondant si les parties ne se mettent pas daccord pour une distance
bloc par bloc.
disque 1 2 3 4 5 6 7 8 9 10
colonne
1 A A A A A A A A A A
2 R R P N V S P E I I
3 I O S I O O U S R H
4 E S Y M T R H U E E
5 K U L O Y P I p S T
6 O V U C L M S B L 0
7 B I K u E U E L B M
8 C J B L B B N C C U
9 U L R T C D R D D C
10 D B C Y D Y Y H F D
11 J F D B G E D I N F
12 T C T F F C B J Y G
13 L G F G K V F F T J
14 N K G S N H G O G P
15 P N O H H F V G H Q
16 W P N J U K J K J B
17 Q Q E D P L K M K N
18 M T H E Q Q M N M V
19 S H M K R i T Q P W
20 V E Q P S J O R Q X
21 X D v Q w N L V v L
22 z Y w V X G W W w Y
23 G W X X M T Q Y K
24 H X z R I W X X u R
25 Y Z I Z J X Z T X S
26 F M J W Z Z c Z z Z
D fin ition 16.1 Dans un chiffre itr r tours, le cryptogramme est calcul
par application itre au clair dune fonction de tour g telle que :
Ct = g ( C i _ i , K i ) i = 1 r
X , Y ,K ^ (y, F(Y, K ) X )
( C f , G f ) = ( CR_ , , F { Cf Li . 4 C ti)
16.4 DES
16.4.1 Fonctionnement
- un message M de 64 bits ;
- une cl K de 56 bits ;
E i R i 1
Ri = L i-i f ( R i - i , K i)
pour 1 < i < 16 et / une fonction qui prend en entre les 32 bits de la
partie droite et les 48 bits de la cl de tour et fournit une sortie de 32 bits
La fonction / est dfinie en utilisant huit permutations appeles S-boxes - S
170 DES
sortie
F onction / et .S-boxes
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
R-1
----------K
E ( R i-i) Ki B 1 B 2 Bg
Chaque B j pour I < j < 8 est ensuite utilis comme lentre d une fonction
de substitution (.S'-box) Sj qui renvoie un bloc de 4 bits en sortie Sj(Bj).
Voici par exemple la S'-box Si :
C olonne
ligne
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 12 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
C alcu l d e la d iv ersification de la cl
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
itration 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
dcalage 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
16.4.2 Dchiffrement
R i-l f'i
L i-i = Ri f{L i, K i)
Observons que si lordre des cls de tour est invers, lalgorithme, quant
lui, reste identique.
Le DES est une volution des machines rotor (dcrites dans [6]) utilises
par larme allemande lors de la Seconde Guerre mondiale et cryptanalyses
avec un succs relatif notamment grce au mathmaticien anglais A. Turing.
Deux faiblesses principales ont t observes dans la conception du DES :
(1) des cls de 56 bits peuvent tre trop courtes pour assurer une robustesse
suffisante ;
Cryptanalyss diffrentielle et
linaire des chiffres itrs
On se propose d tudier deux techniques rcentes de cryptanalyse des chiffres
itrs : la cryptanalyse diffrentielle et la cryptanalyse linaire. Historiquement,
cest la cryptanalyse diffrentielle qui a t introduite en premier par Biham
et Shamir [10] pour tenter de cryptanalyser le DES. Cette mthode a t am
liore ensuite au moyen de la cryptanalyse linaire introduite par Matsui [70],
notamment en ce qui concerne la complexit de lattaque.
On utilise le chiffre propos dans [44, 45] pour prsenter ces techniques de
cryptanalyse.
On considre un rseau de substitutions/permutations simplifi dcrit par la
figure 17.1 qui prend en entre un bloc de 16 bits et qui fonctionne itrativement
en 4 tours. Chaque tour consiste en :
entre 0 1 2 3 4 5 6 7 8 9 A B C D E F
sortie E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7
-U ne transposition des bits (ou permutation des positions des bits) dfinie
par : la i e sortie de la j e bote-S est relie la j e entre de la ie bote-S.
tour 4
crypto - C\6
Cest une attaque clair choisi. Le cryptanalyste choisit des paires dentres
X ' et X " qui satisfont un A X prcis sachant que le A X considr conduit avec
une forte probabilit un A Y particulier.
Pour cela, il faut examiner les proprits des boites-S et utiliser ces pro
prits pour dterminer les caractristiques diffrentielles. Plus prcisment, on
considre les diffrences des entres et des sorties des botes-S pour dterminer
celles qui apparaissent le plus frquemment. Ensuite, on va combiner linforma
tion recueillie sur les botes-S pour en dduire une caractristique diffrentielle
du chiffre.
Les valeurs qui apparaissent avec le plus dcart sont A Y = 0010 pour A X =
1011 (8/16), A Y = 1011 pour A X = 1000 (4/16) et A Y = 1010 pour A X =
mon ffi/ifi
180 Cryptanalyse diffrentielle
X Y AV
t>
T 1 A a = 0100
II
c
0000 ir U .J 1101 1100
0001 0100 0010 1110 1011
0010 1101 0111 0101 0110
0011 0001 0010 1011 1001
0100 0010 0101 0111 1100
0101 1111 1111 0110 1011
0110 1011 0010 1011 0110
0111 1000 1101 1111 1001
1000 0011 0010 1101 0110
1001 1010 0111 1110 0011
1010 0110 0010 0101 0110
1011 1100 0010 1011 1011
1100 0101 1101 0111 0110
1101 1001 0010 0110 0011
1110 0000 1111 1011 0110
1111 0111 0101 1111 1011
AL > 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 16 0 0 0 0 U 0 0 0 0 U 0 0 0 0 0
1 0 0 0 2 0 0 0 2 0 2 4 0 4 2 0 0
2 0 0 0 2 0 6 2 2 0 2 0 0 0 0 2 0
3 0 0 2 0 2 0 0 0 0 4 2 0 2 0 0 4
4 0 0 0 2 0 0 6 0 0 2 0 4 2 0 0 0
5 0 4 0 0 0 2 2 0 0 0 4 0 2 0 0 2
6 0 0 0 4 0 4 0 0 0 0 0 0 2 2 2 2
7 0 0 2 2 2 0 2 0 0 2 2 0 0 0 0 4
8 0 0 0 0 0 0 2 2 0 0 0 4 0 4 2 2
9 0 2 0 0 2 0 0 4 2 0 2 2 2 0 0 0
A 0 2 2 0 0 0 0 0 6 0 0 2 0 0 4 0
B 0 0 8 0 0 2 0 2 0 0 0 0 0 2 0 2
c 0 2 0 0 2 2 2 0 0 0 0 2 0 6 0 0
D 0 4 0 0 0 0 0 4 2 0 2 0 2 0 2 0
E 0 0 2 4 2 0 0 0 6 0 0 0 0 0 2 0
F 0 2 0 0 6 0 0 0 0 4 0 2 0 0 2 0
La somme de tous les lments d une ligne ou d une colonne vaut 2n = 16.
Tous les lments sont pairs (la diffrence est symtrique).
Cryptanalyss diffrentielle et linaire des chiffres itrs 181
Les bits de la cl nont pas dinfluence sur les diffrentiels. C est l tout
lintrt de la cryptanalyse diffrentielle et la grande ide de Biham et Shamir
qui ont russi faire disparatre linfluence de la cl dans les paramtres de la
cryptanalyse.
Il faut ensuite russir combiner les informations que lon a obtenues sur
lensemble du chiffre en une caractristique diffrentielle du chiffre.
La diffrence sur lentre du chiffre est A P = [0000 1011 0000 0000] et.
lentre du dernier tour, A U 4 = [0000 0110 0000 0110] avec comme probabilit
(6 /16)2 puisquon a fait intervenir S32 et S 3 3 . Cette probabilit est obtenue
connaissant A U 3 qui a comme probabilit 6/16 tant donn A f/ 2 de probabilit
8/16 ainsi que A P . La probabilit d avoir
on cherche les 256 valeurs possibles des bits de qui sont concerns :
[-^5,5 ^5,8, K s,13 - - - ^5,16]-
Pour chaque valeur, on compte le nombre de fois o (17.1) est satisfaite en
calculant les valeurs de [A 1/4,5 . . . A f/4,8, At/4,13 . . . A L q jf,].
On compte, pour chaque cl, le nombre de fois o (17 1) est satisfaite et on
choisit la cl qui a maximis cette valeur.
N o c/pD
X i2 . . . X iu Yh . . . Yu = 0
' v "------>------- v------- ' (17.2)
u bits dentre v bits de sortie
Le but de cette cryptanalyse est de trouver de telles expressions qui ont mie
forte (ou faible) probabilit. Si un chiffre a tendance vrifier lquation (17.2)
avec une forte (ou faible) probabilit, les cryptogrammes scartent d une dis
tribution uniforme. En effet, si on choisissait alatoirement u + v bits et quon
Cryptanalyss diffrentielle et linaire des chiffres itrs 185
x h X i2 . . . X ; Yh . . . Yjv.= 1
^_i----------------------------------------------- (1 ?3 )
u bits d entre v bits de sortie
Dans un cas comme dans lautre, le chiffre prsente une faiblesse extrme.
On se base sur lalgorithme 2 prsent dans larticle de Matsui [70] qui
construit une approximation linaire fonction de bits dentre et de bits en
sortie de lavant dernier tour.
Les bits du clair sont supposs alatoires ainsi que ceux en entre du dernier
tour.
Xi x 2 x 3 x4
4x4 bote-S
Yj Y2 Y3 Y4
Ai a 2 A3 A4 n y2 V3 a 2. a3 El L3 FT
0 0 0 0 1 1 1 0 u
0 0 0 1 0 1 0 0 0 0
0 0 1 0 1 1 0 1 1 0
0 0 1 1 0 0 0 1 1 1
0 1 0 0 0 0 1 0 1 1
0 1 0 1 1 1 1 1 1 1
0 1 1 0 1 0 1 1 0 1
0 1 1 1 1 0 0 0 0 1
1 0 0 0 0 0 1 1 0 0
1 0 0 1 1 0 1 0 0 0
1 0 1 0 0 1 1 0 1 1
1 0 1 1 1 1 0 0 1 1
1 1 0 0 0 1 0 1 1 1
1 1 0 1 1 0 0 1 1 0
1 1 1 0 0 0 0 0 0 0
1 1 1 1 0 1 1 1 0 0
P 1P2 i= j = 0
i = 0 ,j = 1
i = l,j = 0
, (1 - P i ) ( l - P 2 ) i= j = 1
P r (X i X 2 = 0) = P r (X j = X 2) = Plp 2 + (1 - p i ) ( l - p2) =
1/2 + 2i 2 = 1/2 + i i2
si Pi 1/2+,-, ; reprsente le biais de chaque X i et ji2 le biais de X i Q X 2 = 0.
Matsui a gnralis la proprit prcdente pour plusieurs variables.
P r (X j X 3 - 0) = P r{[X y X 2] [X 2 X 3] = 0)
tour 1
tour 2
tour 3
tour 4
1*2,6 1*2,8 (-ft -Kl,5 ) (P? -Kl,7 ) (-f*8 -Kl,s) -K2,6 = 0 (17-4)
Et comme 1 / 4,6 = 1*3,6 p4,6, t/ 4,8 = 1*3,14 1^4,8, K414 = 1*3,8 -K4,i4 et
K4 16 = 1*3,16 -K4,i 6, on r-crit ce qui prcde en
avec E/c
qui est fix 0 ou 1 selon la cl du chiffre.
Si la valeur de E/c est fixe 0, lexpression
a pour probabilit 15/32 et, pour E/c = 1, on obtient une probabilit de (1-
15/32)=17/32
En dautres termes, on dispose dune approximation affine des 3 premiers
tours du chiffre avec un biais de lordre de 1/32.
Comment peut-on utiliser ce biais ? Ou, comment peut-on retrouver certains
des bits de la cl ?
Cryptanalyss diffrentielle et linaire des chiffres itrs 191
E xem ple 17.7 L expression linaire (17.7) affecte les entres des botes-S
42 et 44 du dernier tour. Pour tous les couples clairs/cryptogrammes,
on cherche les 256 valeurs possibles des bits de K$ qui sont concerns :
[K5.5 . . . K 5 ts, -^5,13 -^5,16]-
Pour chaque valeur, on compte le nombre de fois o (17.7) est satisfaite en
calculant les valeurs de [6/4,5 -6/4 ,g, f/4 ,13 6/4,ie]-
La valeur qui scarte le plus de la moiti des couples clair/crypto est la plus
probable. Selon le signe de lcart (> 0 ou < 0, on se servira de lexpression
linaire ou affine. Pour E;. = 0, on aura une probabilit < 1/2.
Soit e le biais tel que lexpression linaire soit vrifie. Matsui montre que
le nombre de clairs requis pour lattaque est proportionne] N l e- 2 .
Comme le biais est calcul partir des botes-S en utilisant le lemme, il d
pend de lapproximation linaire de chaque bote-S utilise. Ainsi, pour amlio
rer la sret d un chiffre, on cherche amliorer les botes-S (i.e. en minimisant
le biais de chaque boite-S) et maximiser le nombre de botes-S utilises dans
lattaque. C est de cette manire qua t conu Rijndael [22], le successeur de
DES, que nous prsentons dans le prochain chapitre.
Matsui a effectu une cryptanalyse de DES avec un taux de succs de 88%
en utilisant 220 clairs en 20 secondes sur un DES 8 tours. Il a gnralis cette
192 Cryptanalyse linaire
18.1 IDEA
le ou exclusif note 0 ;
Ai A-2 A3 X4
9iK )
Yl I2 transformation finale Y3
18.1.1 Description
18.1.3 Dchiffrement
5 zP ~ X y(5) y(5) z p 1
3 Z2 zp 6
y(4)
6 zS p1 3 -z P z p - 1 z p
zP ~ 1 -z P ^7(2)
7 -z P zp 1 zSp 6
y (2) y(2) ^(1)
8 zP ~ 1 3 Z2 zp 1 zp Z6
finale z [iyl y(l) y ( 1)
Z2 3 z iirl
Deux chiffres robustes : IDEA et AES 197
18.1.4 Cryptanalyse
18.3 Rijndael
Les oprations de Rijndael sont dfinies soit au niveau de loctet, soit sur
des mots de 32 bits. Un octet est reprsent comme un lment du corps fini F2s
(comme pour les codes cycliques prsents au chapitre 8) tandis que les mots
sont reprsents par des polynmes coefficients dans F2s. Nous rappelons ci-
dessous les oprations utiles la comprhension du fonctionnement de Rijndael.
Deux chiffres robustes : IDEA et AES 199
0 ,n 0 ,1 0 ,2 0 ,3 0 ,4 0 ,5 k o ,l k o ,2 k o ,3
o
P
1 ,0 1 ,1 1 ,2 1 ,3 1 ,4 1 ,5 k l,0 fc l .l k l,2 k l,3
2 ,0 2 ,1 2 ,2 2 ,3 2 ,4 2 ,5 ^ 2,0 ^2,1 k 2 ,2 k 2 ,3
14 14 14
II
S
Transformations de tour
Avant le premier tour, on effectue une opration de ou exclusif avec les bits
de la cl de tour (AddRoundKey).
A chaque tour, en fonction dune cl de tour obtenue au moyen dun al
gorithme de squencement qui sera dcrit plus loin, on effectue les oprations
suivantes sur ltat :
-B yteSub : utilisation d une bote-S qui travaille octet par octet et qui sera
dcrite plus en dtail dans le paragraphe 18.3.2.
Nr Cl C2 C3
4 1 2 3
6 1 2 3
8 1 3 4
pas de permutation
m n 0 p m n 0 P
k permutation de Cl
j 1 j
d e f permutation de C2 d e
w x z pennutation de C3 x
y 3
W y
Toute la scurit des chiffres de ce type rside dans la conception des botes-
S. Nous dcrivons ci-dessous le fonctionnement de celles qui sont utilises dans
Rijndael :
/ yO \ / 1 0 0 0 1 1 1 K /X0 \
( X1\
I 2
yl/2 \ / n o o o i i n
x2 ( '0\
11 100011
2/3 1 1 1 1 0 0 0 1 *3 0
VA 1 1 1 1 1 0 0 0 X4 + 0
2/5 0 1 1 1 1 1 0 0 x5 1
\ye J V0 0 1 1 1 1 1 0 / \x6 J
x2/7 7 'OOOlllll7 ' X7 J
Expansion de la cl
RC [1] = 1 = 01//
RC [/] = x.RCti - 1] = 02//.RC [ - 1] =
Slection de la cl de tour
18.3.4 Dchiffrement
18.3.5 Conclusion
Diffrents modes de
fonct ionnement
Les chiffres en bloc complexes comme DES, IDEA ou AES (Rijndael [21])
supportent diffrents modes de fonctionnement qui dpendent de la faon dont
les blocs successifs du cryptogramme sont chiffrs. On en dnombre quatre
principaux :
Cest le mode qui est dcrit prcdemment dans cet ouvrage. Etant donn
lin blocdu clair , chaque bloc est chiffr avec la cl K par la fonction en de
chiffrement, donnant le cryptogramme y.,. . . comme indiqu dans la figure 19.1.
f \
,X 2 ,X i
CK
v y
Au dpart, les deux parties sentendent sur une valeur initiale (note
IV yo dans la figure) qui permet d initialiser le processus. Cette valeur ini
tiale remplace le premier bloc du cryptogramme qui nest pas encore dfini. Au
lieu de chiffrer directement Xi, le premier bloc du clair, on chiffre par en (la
fonction de chiffrement qui utilise la cl secrte K ) le rsultat dune opration
de ou exclusif entre yo et Xy. Le rsultat du chiffrement e k (yo xy ) donne y y
premier bloc du cryptogramme. On continue de la mme manire pour chiffrer
les blocs suivants du clair.
Le fonctionnement du dchiffrement est illustr par la figure 19.3. Le premier
bloc du cryptogramme y y est dchiffr par d k , la fonction de dchiffrement.
Mais, rappelons que yi = ex (y o ') Donc. dK (eK (yo %i)) = yo * i et
pour obtenir Xy, premier bloc du clair, il faut connatre I V = yo pour effectuer
lopration o:/'io = aq. Le dchiffrement des autres blocs du cryptogramme
se fait de manire analogue.
Pour ces deux derniers modes, le chiffrement du clair se fait par une suite
de ou exclusifs avec des cls qui sont issues du chiffrement par le chiffre cl
secrte :
Xi X2
(
" t )
lV = z 0 eK
'r 'J
2/1 2/2
Xl x 2
'
IV = y 0 f ) m c s
ex l CK J * vJ
yi 2/2
2/i 2/2
IV=2/o ( eK ) * 0 ( ey ) *0
Cryptographie cl publique
Les fonctions sens unique ne peuvent pas servir telles quelles de systme
de chiffrement en utilisant f ( M ) pour chiffrer M puisque mme le destina
taire lgal ne serait pas en mesure de dchiffrer le cryptogramme. La notion
de fonction sens unique trappe est d une utilit plus immdiate pour la
cryptographie cl publique. Une fonction / : X Y est dite trappe si elle
peut tre calcule efficacement dans le sens direct. Le calcul dans le sens inverse
est aussi efficace pourvu quon dispose d une information secrte, la trappe, qui
permette de construire une fonction -g telle que g o f = Id. Ainsi, il est facile de
calculer limage par / de nimporte quelle entre mais calculatoirement impos
sible d inverser / sans connatre g. D une part, il doit tre facile dengendrer de
tels couples (/,</) D autre part, la publication de / ne doit rien rvler sur g.
Donne Un n-uplet dentiers A = (ai, , an) tels que les a, sont tous dis
tincts et un entier k.
Question Existe-t-il un sous-ensemble de A dont la somme est gale k ?
A = (43,129,215,473,903,302,561,1165,697,1523)
et k = 3231, on remarque que 3231 = 129 + 473 + 903 + 561 + 1165 est solution.
Le problme du sac dos nous permet de dfinir une fonction sens unique
comme suit : tout entier x, 0 < x < 2 1 admet une unique reprsentation en
binaire sur n bits. On dfinit f ( x ) comme le nombre obtenu partir d un n-
uplet d entiers A, en sommant les a, pour lesquels le bit Xi de la reprsentation
binaire de x = x n- iX n - 2 - Xo est gal 1. En notation matricielle, si A est
un vecteur ligne de dimension n et B x le vecteur x sur n bits, f ( x ) (A , Bx),
o () dnote le produit scalaire usuel. Ainsi,
/(1 )= / ( 0 . . .01) = On
/(2 ) = / ( 0 ...1 0 ) = On-l
/ ( 3 )= / ( 0 ..1 1 )= On + On- 1
qu i_ do rt d in e
(3936 1032 4161 1983 1165 3455 1118)
(43,129,215,473,903,302, 561,1165,697,1523)
Observons que (A , M ') < m car m > ui-> ce qui implique que la
congruence ci-dessus se simplifie en c = (A ,M '). Comme le problme dfini
par A et c ne peut avoir plusieurs solutions, on a ncessairement M = M '.
(3936,1032,4161,1983,1165,3455, 1118)
20.1.6 Cryptanalyse
20.2 RSA
On montre ci-dessous que le dchiffrement de RSA est correct [78], i.e. que
lon a bien M ed = M k'pba)+l mod n avec d s l mod <p(n).
Par le thorme dEuler, = 1 mod p => M p~ x = 1 mod p si
pgcd (M ,p ) = 1 Et comme (p 1)|<p(n), M k v ^ + 1 = M mod p (cest tri
vialement vrai si M = 0 mod p).
On procde de mme pour q : M k v ^ + 1 = M mod q (cest trivialement
vrai si M = 0 mod q). Et on a bien : M ed = Al mod (pq).
La sret de ce systme repose sur lhypothse RSA pour laquelle il est aussi
difficile de dcrypter que de factoriser n, ce qui est un problme trs difficile.
Exponentiation modulaire
i 9 8 7 6 5 4 3 2 1 0
bi 1 0 0 0 1 1 0 0 0 0
c 1 2 4 8 17 35 70 140 280 560
d -7_ 49 157 526 160 241 298 166 67 B
b est lue de la droite vers la gauche afin de contrler quelles oprations doivent
tre effectues. Chaque itration utilise une des deux identits suivantes :
(2) Si le message chiffr reu par Alice est 17, quel est le clair correspondant?
On supposera que les messages sont des entiers modulo n.
9 r = <7mod r Q LrJ R T
37 108 37 (1,0) 0 (0,1) (1,0)
108 37 34 (0,1) 2 (1,0) ( - 2 ,1 )
37 34 3 (1,0) 1 ( - 2 ,1 ) ( 3 ,- 1 )
34 3 1 ( - 2 ,1 ) 11 ( 3 ,- 1 ) (-3 5 ,1 2 )
3 1 0 ( 3 ,- 1 ) 3 (-3 5 .1 2 ) *
[] 0 * (-35,12) * * *
Thorme 20.3 Un entier n est un nombre de Carmichael ssi n est non pre
mier, sans facteur carr et tout diviseur premier p de n est tel que {pl)|(n1).
C o ro lla ire 20.5 Si un entier n est non premier et pour a G Z n tir au hasard,
la probabilit que Ventier n passe le test est infrieure 1/2.
En rptant r fois le test, la probabilit que n soit compos est donc sup
rieure ou gale 1 l / 2 r.
n = 1 + p * 1 p*
o les pi sont des premiers dj connus et les A,- des entiers non nuls.
(3) ni p ni ne doivent tre petits ; ils ne doivent pas tre choisis dans une table
de nombres premiers et ne doivent pas tre dune forme particulire.
Cryptographie cl publique 219
( n = pq
1 Pin) = { p - 1)(<7- 1)
E xem ple 20.8 Alice publie ses paramtres publics e et n, 17 et 143. Fred
intercepte c = 19. Il calcule
i 2 3 4
ce* 84 28 19
On divise n par tous les entiers impairs compris entre 3 et \_\fn\. Observons
que cette mthode de factorisation ne travaille pas en temps polynomial sur la
taille de lentre. En effet, lorsque lentier n est fourni lalgorithme, il est
cod, par exemple en binaire sur k bits. La taille de n est donc k. Or le temps
de fonctionnement de cet algorithme est de lordre 0 (\y/n\) pour n = 2 k, ce
qui nest pas polynomial sur la taille de lentre. Cette mthode est cependant
efficace pour de petites valeurs n < 10l2.
Conclusions sur R S A
- RSA requiert des cls de plus en plus longues du fait de lamlioration des
mthodes de factorisation et de laccroissement de la vitesse des ordinateurs;
- RSA est plus lent que DES dun facteur suprieur mille.
Cryptographie cl publique 221
Supposons que, dans le procd RSA, le module n soit public et que lex
posant d soit conserv secret. On suppose, de plus, quun cryptanalyste a in
tercept tm couple clair/cryptogramme (M , M e mod n) et cherche casser le
procd. Il cherche donc lexposant secret de dchiffrement d. Il doit rsoudre
un problme de logarithme discret dont on donne lnonc ci-dessous.
20.4 El Gamal
Le clair x est masqu par la multiplication par (3k et produit y2. La valeur
de a k est transmise en tant que partie du cryptogramme comme y\.
Lopration de dchiffrement est :
Signatures numriques
sigA-(M) = S
sigk { M ) = M dB mod nu = S
Celui de vrification :
C = E a ( D b ( M) )
et Alice le dchiffre en :
E b ( D a (C)) = M
Pour cela, il faut que M < ub < n A, sinon on inverse lordre chiffrement-
dchiffrement.
21.3.1 Fonctionnement
sig K ( M , k ) = (7 , 6 )
avec
7 = ak mod p 6 = (M a^)k~l mod {p 1)
et
P 'f = a M mod p
logQ/ ? V
Donc Oscar ne peut pas signer un message alatoire de cette faon.
Oscar peut signer un message alatoire en choisissant simultanment 7 ,
et M . Pour i , j deux entiers, 0 < i , j < p 2 et pgcd (j , p 1) = 1, il calcule :
7 = cd/3J mod p
= 7y-1 mod (p 1)
M = 7*i 1 mod (p 1)
Signatures numriques 227
= a~ lJ 1011/33 mod p
= a - 7 *-7 mod p
= a M mod p
DSS est une variante du procd dEl Gamal qui date de 1994. Aux Etats-
Unis, DSS est aux signatures ce que DES (ou AES) est au chiffrement.
Si un cryptogramme nest en gnral chiffr et dchiffr quune seule fois,
une signature doit pouvoir tre vrifie plusieurs fois. Par exemple, lors de la
signature dun contrat, plusieurs parties peuvent vouloir vrifier la signature
dune personne et ce, mme plusieurs annes aprs. Il semble donc important
davoir des critres de scurit plus robustes que pour le chiffrement. Comme
la signature par El Gamal nest pas plus sre que le problme du logarithme
discret nest difficile, il faut utiliser de grandes valeurs de p. A lheure actuelle,
on utilise des nombres de 1024 bits.
Cependant, un module de 512 bits engendre une signature de 1024 bits.
Dans le cas des cartes puce, par exemple, il est souhaitable d avoir une signa
ture plus courte. Par une astuce, DSS se distingue dEl Gamal en offrant une
signature de 320 bits sur un message de 160 bits en impliquant un module de
512 bits. L astuce revient travailler dans un sous-groupe de Z * de taille 2160.
21.4.1 Fonctionnement
Priv Publics
a p, q, a, (3
On choisit 1 < k < q 1 alatoire et on dfinit une signature comme :
sigk (M, k) = (7 , )
pour
Pour M G Z * et 7 , G Z . on dfinit :
ei = M ^ 1 mod q
e2 = 7<i>~1 mod q
Bob veut signer M = 1234 et choisit k = 50. k 1 mod 101 = 99. Il obtient :
et
= (1234 + 75.94)99 mod 101 = 97
et on a bien :
(17045456727 mod 7879) mod 101 = (17050 mod 7879) mod 101 = 94
Signatures numriques 229
dans le membre droit de (21.3). Donc, si 7 est rduit modulo , on doit aussi
rduire le membre gauche de (21.3) modulo q dans la vrification. On note que
(21.2) ne peut plus fonctionner avec ces rductions modulo q. On passe donc
au procd dcrit dans le paragraphe 21.4.1.
L inconvnient majeur de ce procd est quil est plus lent que RSA dun
facteur compris entre 10 et 40. Cependant, la gnration des cls est plus rapide
que pour RSA. Lin autre inconvnient est quune taille de cl de 512 bits est
souvent trop petite. C est pourquoi la taille des cls utilises tend aujourdhui
vers 1024 bits.
C h a p it r e 22
Fonctions de hachage
On dfinit une fonction de hachage comme une fonction qui associe des
mots binaires de longueur arbitraire des mots binaires de longueur n fixe :
Dfinition 22.1 Une fonction de hachage h est collisions fortes difficile sil
est calculatoirement difficile dobtenir deux messages diffrents x et x' tels que
h{x) = h(x').
Notons que si h est collisions fortes difficile, elle est galement collisions
faibles difficile.
Dfinition 22.2 On dit que h est sens unique si, pour une empreinte num
rique donne z, il est calculatoirement difficile de trouver un message x tel que
h(x) = z.
^ k1 k1
. i ~ p = < i = ^ k -*> = n
i=0 1
Description de lalgorithme
h 7Lqx Z 9 > Zp \ {0 }
{x\,X2 ) i>a XlPx2 mod p
En conclusion, h est collisions fortes difficiles pourvu que le calcul de loga (/3)
dans Z p soit galement difficile.
e k '{ 0, l } n x { 0. l } n * { 0, l } n
g (k ,x ) = ek(x) x
g(k, x ) = e k ( x ) @ x k
g(k, x ) = e k ( x k) ffi x
g {k, x ) = e k{ x k) ffi x k
Nous suivons la construction de Merkle [15] qui permet dlaborer une fonc
tion de hachage partir dune fonction de compression g : {0, l } m {0,1}",
comme celle obtenue prcdemment.
Soit r = m n > 1. On veut construire h : {0 ,1 }* {0, l } n.
Soit x E {0 ,1 }* et l sa longueur en binaire.
-on complte x avec des 0 en tte pour obtenir u = 0 x t.q. |w| = 0 mod r;
on complte t avec des 0 en tte pour obtenir y = (Pl t.q. \y\= 0 mod r1 ;
- O n suppose maintenant que H t- i = H't, _ i pour ( ) < ? ' < t. Alors, il existe
un indice i,0 < i < t t.q. Wt~i / C est le cas soit parce que les
mots w et w' sont de longueurs diffrentes soit parce quils sontdiffrents
(sinon h serait sans collision). Alors, g ( l I t - i - i W t - , ) = H t - = H'L, _ i =
et H t - i - i w t - i +
Fonctions de hachage 237
message
valeur \V V\ \ \ \ \ valeur
initiale y 7 MD5 y y MD5 y y MD5 y y hache
Toutes les oprations utilises par MD5 sont dfinies sur des mots de 32
bits. La transformation consiste en quatre tapes successives et chaque tape
est constitue de seize sous-tapes. Dans chacune des sous-tapes un mot des
variables de chanage est modifi comme suit : on ajoute un mot du message et
le rsultat du calcul d une fonction non linaire dpendant des trois autres mots
de la variable de chanage ; ce rsultat subit ensuite une permutation circulaire
dun certain nombre de bits.
- f ( x , y, z ) = ( x a y ) v( ( - x ) a z)
- g ( X , Y , Z) = ( X A Y ) V (Y A ->Z)
h{X, Y Z ) = X ( D Y Z
22.6.3 Attaques
En 1996, H. Dobbertin [30, 31] a russi une attaque sur la fonction de com
pression de MD5. Plus prcisment, il a trouv en quelques heures de calcul une
collision dans la fonction de compression. Par collision on entend que la fonc
tion de compression a fourni la mme image sur deux entres x et x distinctes
partageant la mme valeur initiale {IV). En d autres termes que
Xi = Xi pour i ^ 14
X1 4 x i 4 + 2 9
Pour plus de dtails sur cette attaque, nous suggrons la lecture de [31] qui
en dcrit les grandes lignes sans trop entrer dans des considrations techniques.
En consquence de quoi, MD5 nest plus recommande pour des applications
ncessitant un haut niveau de scurit. Les fonctions qui en assurent le rem
placement sont SHA-1 ou RIPEMD ainsi que leurs variantes les plus rcentes.
E xem ple 2 2.4 1 0 1 0 0001 0000 0011 1111 1110 0010 0011 = A103FE23
Le codage dun entier 0 < z < 2 64 est tel que 2 = 2 32,x + y pour deux mots de
longueur 8 , x et y . Enfin, SHA travaille sur des blocs de 512 bits reprsents
comme 16 mots de 32 bits.
Comme pour MD5, on utilise les oprations logiques usuelles de la section
prcdente.
H 0 = 67452301
H i = EFCDAB89
H 2 = 98BADCFE
H 3 = 10325476
H i = C3D2E1F0
On effectue itrativement les calculs sur chacun des M-, du paragraphe 22.7.1.
Le traitement de chacun des M* comprend 80 tapes.
Algorithme 22.3 _________________________________________________________
1. dcouper Mi en 16 mots W q, . . . , ILis
2. pour t 16 jusqu 79 faire
w t * - (wt_3 wt_8 w t- 14 W t - i o ) i
fpour
3. A + - H 0 ]B *- H i - C e - H 2; D *- H a; E * - H A
4. pour t * 0 jusqu 79 faire
TEMP-s A 5 + f t (B, C , D ) + E + W t + K t ;
E * - D ; D * - C ; C <- B 30; B <- A; A * - TEMP ;
fpour
H 3 * H 3 + D : H 4 < H 4 + E ;
Aprs avoir trait tous les Mi, les 160 bits de lempreinte du message par
SHA sont constitus des cinq mots HoHiH 2 H 3 H4.
22.7.3 Attaques
Dans [16], Chabaud et Joux proposent une attaque pour trouver des colli
sions dans une version affaiblie de SHA appele SHA-0. Ils utilisent pour ce faire
des techniques proches de la cryptanalyse diffrentielle. En revanche, cette ap
proche na pas domi de rsultat probant pour SHA-1. Cette fonction de hachage
cryptographique reste une des fonctions de hachage actuellement recommande
avec RIPEMD que nous ne dcrirons pas.
Le Digital Signature Algorithm (DSA) date de 1994 et se fonde sur DSS que
nous avons prsent dans le paragraphe 21.4.1. Dans cette variante, on signe
lempreinte du message par une fonction de hachage et non plus le message
lui-mme.
Fonctionnement
logarithme discret dans le sous-groupe engendr par a est difficile. Soit h, une
fonction de hachage cryptographique connue de tous les utilisateurs du systme,
comme par exemple, MD5 ou SHA-1. Le message M G Z* et sa signature est
constitue du couple ( ei ,e2) x Z , . L ensemble des cls est :
Priv Publics
a p, q, a , P
On choisit 1 < k < q 1 alatoire et secret puis on dfinit la signature :
sig7<(M , k) = (7 ,<5)
pour
ei = h ( M ) 6 ~ 1 mod q
= 7<5-1 mod q
Notons que <5 ^ 0 mod q car -1 mod q est ncessaire la vrification des
signatures. Si Bob obtient <5 = 0 mod q dans le procd de signature, il doit la
rejeter et construire une nouvelle signature avec une nouvelle valeur de k.
La seule diffrence avec DSS est quici on ne signe pas le message Al dans
son intgralit mais plutt lempreinte de M par h, une fonction de hachage
cryptographique. L intrt est quavec ce procd, la taille de la signature ne
dpend plus de la taille du message. Lobjet quon signe est de taille fixe (environ
160 bits) quelle que soit la taille de M , ce qui entrane un gain important sur
la taille du message sign transmis.
Notons quil est tout aussi facile de dfinir une signature avec hachage pour
RSA ou tout autre systme de signature numrique en remplaant le message
par son empreinte.
pas d une base parfaite mais elle est suffisante pour la rsolution de nombreux
problmes, comme la factorisation de polynmes ou la cryptanalyse de Merkle-
Hellman.
Tout rseau (entier) L possde une base i.e. une famille libre de r vecteurs
b = (b\,. . . , br), telle que le rseau L est lensemble des combinaisons linaires
entires des vecteurs de b. Rciproquement, soit une base de r vecteurs de Z "
b = ( b ], . . . , b, ) avec r < n, lensemble des combinaisons linaires entires de
ces r vecteurs est un sous-groupe discret de Z " , un rseau not L(b) :
Si tout rseau entier possde une base, il en possde mme mie infinit qui
ont toutes le mme nombre de vecteurs, ce qui dfinit la dimension du rseau.
Lemme 23.4 Soient b et b' deux bases dun rseau L. Il existe M une r x r
matrice unimodulaire (i.e. coefficients entiers dont le dterminant det(M) =
1) telle que = M.bi pour i = 1 , . . . , r.
Sret des chiffres cl publique 249
Un invariant dun rseau L est une quantit dfinie dans un rseau qui
ne dpend que du rseau et non du choix de la base. La dimension en est un
premier exemple. On introduit deux autres types dinvariants :
E xem ple 23.1 Soit une base de deux vecteurs u = (3,1) et v = (2,1), de
normes ||w|| = \/I et ||?;|| = y/E. A la premire itration de lalgorithme on
calcule k = [| | = 1 et on raccourcit u en u - v (1,0) avant dchanger u et
v qui deviennent te = (2,1) et v = (1,0). A la seconde itration de lalgorithme
on calcule k = 11] = 2 et on raccourcit u en u 2 v = (0,1) avant d changer
u et v qui deviennent u = (1,0) et v = (0,1). Les deux vecteurs sont de mme
norme et lalgorithme termine avec une base de vecteurs plus courts.
250 Cryptanalyse du chiffre de Merkle-Hellman
Preuve A chaque itration u est plus court et comme L est discret, lalgorithme
termine.
Le rsultat est u, v qui vrifient |(w, ?;}| < 11|'||2 et ||?;|| > ||u ||. Pour tout w e L
011 a 'm = au 4- bv. Par minorations, on montre que u est un plus court vecteur :
IieI) 2 g 2 I u12 + 2 ab(u,v) + 2 |M|2 > ( a2 |af>| + 6 2 )|| x ||2 > ||w||2
o o \ O
o
o o
o
o
Quand la dimension n est plus grande (strictement) que deux, les minima
successifs nengendrent pas ncessairement le rseau. En effet considrons le
2 o o o i\
(00201
0 0 0 2 1 /
) qui contient V = \(1,1,1,1,1).
> j > > /
Il
00001/
admet comme minima successifs Ai = 2 pour i G { 1 , . . . , 5} et une famille
ralisant ces minima ne contient pas forcment V et ne permet pas de lobtenir,
comme par exemple 2.1d5-
r b* = h
' j Vi,j = ' (b*%\
i 3 . ^
P0ur 1 - 3 < i - 71
b* = bi - Vijb* pour 1 < i < n
T h orm e 23.8 Soit L Z " un rseau de base (61, . . . , bn) et soit C > 2 G R
tq. INI2 < C pour 1 < i < n. Le nombre d oprations arithmtiques ncessaires
LLL est 0 ( n Alog((7)) pour des entiers de taille (){n log(C')) bits.
Cet algorithme fonctionne selon le principe suivant. LLL est une combi
naison de Gauss dans un hyperplan et de Gram Schmidt. On essaye dappli
quer Gauss des sous-rseaux projets de dimension 2. Plus prcisment, on
commence par projeter bi et N i orthogonalement lespace engendr par
(b1, - - -, b i-1) et on effectue une tape de Gauss sur le rseau projet.
252 Cryptanalyse du chiffre de Merkle-Hellman
Et de lalgorithme RED(A;, /) :
A lg o rith m e 23.3 _____________________________________________
si \fik,i\ > ^alors
r <- [0,5 + fik,i\ ; bk <- bk ~ rbi
p o u r j < 1 l 1 faire fikj < fikj rn ij fp ou r
i~kk,l < f^k,l T
fsi
tape 3 : k est une variable t.q. bi, ^2, - , fc-i sont rduits; lalgorithme
cherche modifier bk pour que 6], 62, . . . , bk soient rduits ;
O11 construit un rseau L dont la base est constitue par les lignes de la
/1 0 0 ... 0 01 \
0 i 0 ... 0 - o 2
0 0 1 ... 0 G3
matrice V =
i 0 0 0 ... 1 -an
\0 0 0 ... 0 s /
Si j , . . . , vn+i reprsentent les lignes de V et que x est solution de SSP,
alors
^ X i V i + v n+i = ( x i , . . . , x n,Q)
7=1
254 Cryptanalyse du chiffre de Merkle-Hellman
Comme les Xi sont des valeurs binaires, ce vecteur est court. Il faut donc
calculer une base rduite de V et vrifier si la base rduite contient un vecteur
qui et une solution au problme SSP.
Justification
Si a est un carr (b2 = a mod p), a possde deux racines carres b modulo
p. Un algorithme naf pour trouver les carrs est de calculer x 2 mod p pour
x = 1 , 2 , . . . , {p l ) / 2 car les autres entiers de ((p l ) / 2 ) -t- 1 , . . . , (p 1) sont
leurs opposs.
Les carrs de Z * sont appels rsidus quadratiques modulo p.
Symbole de Legendre
Une technique simple pour dcider le problme des carrs dans le cas o p
est premier est dutiliser le symbole de Legendre not pour p premier :
G si p|a
+1 si a est un carr
1 sinon
mod p.
256 Attaques par factorisation de RSA
(fHtX);
(2) = (1) E2~ autrement dit, -1 est un carr modulo p si p = 1 mod 4
et nest pas un carr modulo p si p = 3 mod 4 ;
( .) = ( - -() = { ^ - sS m d 4
Symbole de Jacobi
U vrifie la. plupart des proprits du symbole de Legendre sauf les princi
pales :
- (^ ) ^ mod m en gnral;
-si n > m , ( i ) = ( s - ^ a ) ;
x2 = y2 mod n
258 Attaques par factorisation de RSA
/ um = i mod 2
( Uij = otij mod 2 pour 1 < j < h
Sret des chiffres cl publique 259
On observe que Yliei bf = p f 1 . . . p^h o tous les /3, sont pairs. On construit
alors x et y comme
J * = rlie/**
i Pl/2 Ph/2
l v = Pi Ph
n
Card{nombres B-adapts < n}
Ce procd, mme si peu adquat pour de trs grands nombres, est trs
efficace ; il est sous-exponentiel i.e. son temps de calcul moyen est de la forme
gO(log (n)) p 0ur Q < i
On cherche des nombres B-adapts parmi des entiers b tels que b2 mod n
est petit (de lordre de y/n) devant n.
On considre le polynme :
f { z ) = { z + [ Vn \ ) 2 - n
(z -t- lV n \ ) 2 = f ( z ) mod n
Lorsque B > [y/n\, cet algorithme tend avoir la mme complexit que le
crible dEratostne i.e. en ( ) ( B log(U )(log(n))2 + (log(n))3).
La faiblesse de cette mthode est que n doit admettre un facteur premier p
tel que p 1 nait que de petits facteurs premiers dont les ordres de multiplicit
sont tous gaux un (cf. [56]).
Un des algorithmes les plus efficaces ce jour, bas sur les courbes ellip
tiques, est une gnralisation de lalgorithme p 1 de Pollard. Nous donnons
dans le tableau ci-dessous la complexit de quelques bons algorithmes de
factorisation :
crible quadratique O (e((1+(1))'V/Iog() loe los()))
courbes elliptiques O (e((1+(1))\/21og(,) loglog()))
)^e ((l,9 2 + o (l))(lo g (n ))1/3(loglog(r))2/3)^
crible algbrique
Sret des chiffres cl publique 261
Il sagit ensuite de trouver un terme commun aux deux listes (il existe
toujours par le principe des tiroirs de Dirichlet). Ainsi g 10 = y g AIC" et
x = io+ jo\ V n \ -
262 Calcul du logarithme discret
- e n espace : 0 (y/n).
et celui des pas de gant sous la forme de couples (exposant, valeur) est :
L lment 3 est commun aux petits pas et aux grands pas, il a t engendr
pour *o = l dans la liste B et pour jo = 9 dans la liste L. Le logarithme discret
que lon cherchait est x = io + r.jo = 100. On peut vrifier la validit de ce
rsultat en calculant gx mod 113 = 57.
f gz si z G G!
/(* ) = { z2 si z G g 2
[ yz si z G g 3
avec
cii + 1 mod <p(n) si a-i G G]
a,+1 = 2ai mod ip(n) si ai G G 2
ai si at G G3
fi, si bi G Gi
bi+ \ = ^ 2bi mod <p(n) si fi,- G G2
bi + 1 mod y?(n) si fi, G G3
et avec comme valeur initiale pour ao la valeur alatoire choisie initialement et
pour b0 = 0 .
Comme ce sous-groupe est de cardinal fini, la suite (zi)i>0 sera priodique
de priode T partir dun certain rang. Donc il existe s et T tels que z s + t = z8
(s est le plus petit indice pour lequel lgalit est vrifie). On obtient ainsi une
relation de rcurrence du type : m ai+T = x{bi+T h ) mod <p(n), o i G Z .
Si (fi,; . 7 fi,) est inversible modulo <p(n) lquation na quune solution ; c est
le logarithme discret. Sinon, il y a plusieurs solutions. Si elles sont peu nom
breuses, on peut les tester successivement, sinon on recommence lalgorithme
avec une autre valeur initiale ao-
Algorithme 23.6 _________________________________ _______________________
entre : G d ordre n, g et y E G
partitionner G en G i U G 2 U G3
Choisir ao G { 1 . . . , n } au hasard
2 < ga mod n; a < a0; fi < 0; i < 1 ;
tantque (zref / z) ou (i = 1) faire
si i est une puissance de 2 alors zTef < z ; aref < a; firef < fi fsi
i < i + 1 ;
si z g G i alors z <gz mod n ; a * a + 1 mod 1p(n) fsi
si z E G 2 alors z < z 2 mod n;
a < 2 a mod (p(n); fi < 2fi mod <fi(n) fsi
si z G G 3 alors z < y z mod n; fi < fi + 1 mod <p(n) fsi
ftq
rsultat (x logarithme discret de y en base g dans G
est solution de : aref a = x(b firef) mod
Zs + T
P
F ig . 2 3 .2 illustration de lalgorithm e p de Pollard.
P r (A ) = n(n ~ l ) - ( " - ~ ( t ~ 1 = TT I I - 1
n. V n
i= 1
Remarque 23.1 L algorithme de Pollard porte bien son nom, car la lettre p
permet de reprsenter la suite (z,).iCt; priodique partir d un certain rang (s
sur la figure 23.2).
Sret des chiffres cl publique 265
i z a b
0 14 20 0
1 42 21 0
2 69 42 0
4 45 85 0
8 109 4 3
16 97 16 30
26 97 64 34
Gnration de suites
pseudo-alatoires
24.1 Motivation
Nous ne prciserons pas les notions facile et difficile dans la suite mais
nous dcrivons comment, tant donn une permutation sens unique, il est
possible de construire un bon gnrateur de suites pseudo-alatoires binaires.
Nous aurons besoin de construire le prdicat sens unique B au moyen de /
en utilisant le thorme 24.1.
Soit / une permutation sens unique et soit la fonction / ' dfinie par :
2 4
(0 1 ,1 0 ,1 1 ,1 1 ,0 0 ,0 1 ,1 0 ,0 0 ) = V x (.i-iW +j) m od 2
i= 1 j = 1
Xk 0 1, 1 0, 1 1, 1 1, 0 0, 0 1, 1 0, 0 0, E
i= 1 * * * * 3
i= 2 SK * * * 1
total 4
La somme vaut 4, ou encore en arithmtique modulo 2, 0 qui est la valeur du
bit suivant.
270 Gnration de suites pseudo-alatoires
Gi (x) = f ( x ) . B ( x )
n
G q (x )
x
i= 1
= m
F ig . 2 4 .1 C on stru ction d un G P A .
Le gnrateur RSA est une illustration du schma gnral propos par Blum
et Micali tel quexpos dans ce chapitre. On prend comme permutation sens
unique f ( x ) = Xe mod N . N est un entier de taille n produit de deux nombres
premiers p et g et e un entier tel que pgcd (e, <p(A )) = 1. On extrait le prdicat
(2) f
B( x) = lsb(x), o lsb(x) retourne le bit de poids faible de a: .L e gnrateur
RSA prend en entre un triplet (N, e, x ) et fonctionne comme suit.
Algorithme 24.1 _________________________________________________________
entre : (N , e, x )
Xq < x
pour i < 1 l faire
Xi < xf _ 1 mod N
yi 4 - Isb(aq)
fpour
sortie : la suite , ;
Certification
25.1 Introduction
meA m od nA mer m od nF
< -------------------
(1)Des logiciels du domaine public permettent de faciliter une attaque de ce type, comme
ettercap sous lin u x par exemple.
274 Forme gnrale d un certificat
Linformation Nom Distingu est utilise pour fournir une identit dans
un contexte spcifique. Un sujet peut avoir un certificat personnel et un autre
en tant que membre d une organisation. La norme X.509 dfinit les champs
suivants pour linformation Nom Distingu :
IdA.clA
C l d e A
certifie par A C SagiMcWM/l.clA))
Il peut y avoir plus de deux certificats : celui qui garantit la relation entre
lidentit de A et sa cl publique ruais aussi celui qui garantit la relation entre
276 Utilisation et ralisation asymtrique
h(ldA,clA)
{ac)
\ l d A,c\A
Algorithme public
VerAC ) de vrification de AC
Y
oui/non
DCY)
flI d /ic .K /lC
t l d A ,c l A
25.3.4 Attaques
(1) Alice sadresse lAC et lui demande une cl pour communiquer avec Bob.
(3) Aprs avoir dchiffr m \, Alice rcupre la cl de session K qui va lui per
mettre de communiquer avec Bob et engendre le message 7713, chiffr avec la
cl de session K , contenant son identit et lestampille T reue de AC. Elle
retransmet le certificat et le nouveau message ms Bob.
(4) Bob peut dchiffrer le certificat 7712, rcuprer les informations provenant de
lAC (la cl de session K , lidentit dAlice, lestampille et la dure de vie
de la cl). Avec la connaissance de K , il est alors en mesure de dchiffrer
ms qui lui confirme quil sagit bien d Alice qui cherche communiquer
avec lui. Il sait galement quil ne sagit pas dun imposteur qui aurait
observ des communications prcdentes et qui rejouerait une ancienne
demande de communication grce lestampille qui garantit la fracheur
de la communication. Bob accuse bonne rception des messages d Alice en
calculant 7714 qui est une modification numrique convenue de lestampille
(ici T + 1) et envoie 7774 Alice qui peut commencer la communication.
Certification 279
demande de
communication
mA=chK(TW)
avec B
AC
1
mi=chA(K,i(B),T,L)
:A^ I B
Alice est sre quil sagit bien de Bob car seul Bob peut dchiffrer le certificat
issu de lAC. Il ne sagit pas non plus d un imposteur car le dernier message
contient la modification numrique convenue de lestampille.
25.4.3 Scurit
- la modification ;
- la destruction malintentionne ;
- le rejeu ;
- l a divulgation ( disclosure).
destruction destruction
- La gnration qui doit tre effectue en accord avec les rgles de gnration
de cl; cela peut demander une phase de test pour vrifier ladquation de
la cl avec les rgles pour viter, par exemple, des cls faibles.
26.2.1 Gnration
La dure de vie des cls doit tre limite dans le temps et en nombre d utilisa
tions. Ces contraintes proviennent de considrations cryptanalytiques. En effet,
la dure de vie dune cl est limite par le temps ncessaire la cryptanalyse
des messages changs. C est ce que lon appelle gnralement la scurit cal-
culatoire. Un cryptanalyste peut toujours arriver cryptanalyser des messages
lorsquil dispose dune quantit d information convenable et de suffisamment
de temps et de ressources informatiques.
Une cl est considre comme compromise lorsque son usage non autoris est
connu ou suspect. Ce risque saccrot au cours du temps. Les cls compromises
doivent tre dsactives.
26.2.3 Distribution
-E nfin, on peut utiliser une autorit de certification (chap. 25). Dans ce cas,
lauthentification des cls publique est faite au moyen dun certificat garanti
par lautorit de certification.
Ch k a b ( K )
A B
(2) B dchiffre le message et obtient la cl K , vrifie que le message lui est bien
destin et vrifie la validit de lestampille ou du numro de squence.
(1) A sadresse au CDC en lui envoyant un message qui contient son identit A,
lidentit du destinataire B et un jeton N ;
C h K B (K AB'A )_______ 3^ n
n
4 ChKAB(Nb)
t-------------------------------------
cnKAB<Nb-i)
I
A.B.N ChKA(N.B,KAB,ChKe(KAB,A))
(5) A accuse bonne rception en effectuant une opration convenue sur le jeton
Nf, (ici une dcrmentation).
ChBpub{T/N-,A-I<)
ChBpub(SgA(T/N-,B;K))
A B
- tape prliminaire :
- chaque utilisateur U :
A et B veulent construire une cl, connue deux seuls (fig. 26.10). Les infor
mations publiques sont : Y a et Yb-
Y Xa = ( X b ) Xa = aXeXA = ( Xa ) X b = Y X b mod q
En arithmtique mod q
----------- ax B -------------
X X
An < B
Dialogue confidentiel k
f ---------------------------- C h0x Ax B(m sg) [
M C hcx Ax B(m sg) ---------------------------
Les cls prives dans ce protocole sont sres : si un ennemi peut calculer
la cl prive X a de A partir de Y a = oX a mod , il rsout le problme
du logarithme discret rput difficile. Le problme de retrouver la cl partage
entre A et B h partir des informations transmises est un problme qui est aussi
difficile que le problme du logarithme discret. Linconvnient de ce protocole
290 Mise jour des cls
En arithmtique mod q
------------ ax B ------------
est quil ne prmunit pas contre une attaque de lhomme du milieu. Pour ce
faire, il faut le complter par des mcanismes dauthentification.
On obtient ainsi le protocole STS pour Station To Station (fig. 26.11). Il
ajoute des mcanismes dauthentification au protocole prcdent. Alice va chif
frer au moyen de la cl commune le rsultat de la signature de Xa , ax 11 et
lidentit de B. B, va accuser rception de manire analogue.
Une fois obtenue une cl secrte, on peut souhaiter ne pas ritrer ce type
dchange chaque session mais en faisant voluer la cl session aprs session.
Cest le but de la mise jour des cls.
La mise jour des cls est un procd qui permet de partager des cls
construites au pralable en les faisant voluer au moyen de paramtres obtenus
pour la session.
On dfinit une nouvelle cl de session K partir :
K = f { K a b , F)
Applications de la cryptographie
la scurit des rseaux
27.1 Motivation
(1)Le CLUSIF, fond en 1984, offre un cadre dans lequel les acteurs de la scurit des
systmes d information peuvent se rencontrer, changer leurs points de vue, travailler et
progresser ensemble. A ce jour, le CLUSIF rassemble plus de 600 membres, appartenant
300 organismes ou socits. Sa particularit est d accueillir aussi bien les utilisateurs
que les professionnels, fondant sa culture sur une gale participation des uns et des autres
et son dynamisme sur une confrontation permanente de loffre et de la demande.
292 Introduction la scurit
Dans ces deux cas, lindiscret ne fait que prendre connaissance des donnes
sans les modifier.
Pour amliorer la scurit face aux attaques identifies, les mesures mettre
en uvre doivent viser assurer :
- Scuriser l hte : on scurise chaque hte sparment. Cela marche bien pour
des machines individuelles mais pas pour un grand nombre de machines.
Cette opration demande beaucoup de temps par machine et reprsente un
cot non ngligeable en temps ingnieur.
des documents de travail, appels Internet Drafts, qui nont pas de statut
formel et qui ont une dure de vie de 6 mois.
Les RFC recouvrent une grande varit de documents qui vont des do
cuments informels jusqu la spcification complte de certains protocoles.
Une fois publi comme RFC, le document reoit un numro. Un tel docu
ment nest ni revu ni r-dit sous le mme numro. On les trouve ladresse
www. i e t f . o r g / r f c . html.
L IETF, Internet Engineering Task Force, est le groupe charg de lingnierie
et de lvolution dinternet. Il propose des standards par lintermdiaire de
groupes de travail et les met disposition sous la forme de RFC ou dInternet
Drafts. Dans le domaine de la scurit, on peut citer les groupes de travail :
Une couche ne dfinit pas un protocole. Elle dcrit une fonction de transmis
sion de donnes qui peut tre excute par plusieurs protocoles. Ainsi, chaque
couche peut contenir plusieurs protocoles qui dfinissent chacun un service utile
au rle de cette couche. Par exemple, un protocole de transfert de fichiers ou un
protocole de courrier lectronique fournissent tous deux des services utilisateurs
et font partie de la couche applicative.
Chaque protocole communique avec son homologue. Un homologue corres
pond une mise en uvre du mme protocole dans la couche quivalente du
systme distant. Le protocole de transfert de fichiers local est lhomologue du
protocole de transfert de fichiers du systme distant. La transmission de donnes
entre deux homologues doit tre standardise de faon garantir la transmission
des donnes. Ainsi, chaque protocole ne prend en charge que les transmissions
avec son homologue ; il ne tient pas compte des couches adjacentes. Cela im
plique quil faut alors dfinir une convention de transmission des donnes entre
les couches. Celle-ci sort du cadre de cet ouvrage et nous ne la dcrivons pas
plus avant.
Nous voquons seulement la rpartition de quelques services que nous allons
utiliser dans la suite de ce chapitre. Il sagit du service de courrier lectronique
(SMTP : Simple Mail Transfer Protocol) , de celui du web (H TTP : Hyper
296 Introduction aux protocoles rseaux
Applications
SMTP HTTP SMTP HTTP
^ Transport
TCP TCP
Rseau
IP IP
Lien
- < ----------------------------- > -
Services de scurit
(2) non-rpudiation avec preuve de dpt : offre une preuve de dpt du message
lexpditeur : le destinataire ne peut pas nier la rception.
Authentification x X X x
Contrle daccs x X X X
Confidentialit x X X X X X
Confidentialit slective x X
Secret du trafic X X X
Intgrit X X X X
Non-rpudiation X
chiffrement ;
- signatures numriques ;
- mcanismes d authentification ;
Dans un premier temps nous dcrivons une belle application des fonctions
de hachage qui a t invente par L. Lamport [60]. Elle permet de raliser
un mcanisme de contrle d accs au moyen de fonctions sens unique ou de
fonctions de hachage cryptographique.
Cette dernire possibilit ne peut tre contre quel que soit le protocole de
connexion scurise mis en place. Pour liminer ce problme, on fait de plus en
plus appel des systmes biomtriques comme la reconnaissance des empreintes
vocales, digitales ou rtiniennes mais qui sont ici hors de propos.
27.4.2 Solution
Pour viter cette attaque, une ide simple et efficace est dutiliser non plus
un unique mot de passe mais une suite de mots de passe. La solution propose
en 1981 par L. Lamport permet dviter de mmoriser une longue suite de mots
de passe en utilisant une fonction sens unique (fig. 27.2). C est la mthode
(2 )
qui est utilise lheure actuelle dans les systmes mots de passe jetables
comme S/Key, Dpie ou encore LogDaemon en faisant appel une fonction de
hachage cryptographique.
On fixe N un nombre maximal de connexions et s un mot de passe initial qui
nest inscrit nulle part. Le systme et lutilisateur partagent soit une fonction
sens unique soit une fonction de hachage cryptographique h. On note h1 sa
ie itre. Le ie mot de passe p-i est dfini par hN~i(s). La suite des N mots de
passe que lutilisateur fournit successivement pour se connecter est :
(2)
O TP : O n e tim e passwords en anglais.
300 Mots de passe jetables
co n n u du
systme
! hN (s)
P l=hN 1(s ) N -l
itration
login de h
h N i + l ( s ) = h ( Pi) < -
Pir-hF-Hs) N-i
h (s )
p N= h ( s ) = s
fourni par
l'utilisateur
connu du connu du
systme systme
j h]00(s) 1 hJ00(s)
P l= h "(s) p j= h iG0~i (sJ
itration
login de h
Pour que cela fonctionne, il faut que la fonction h vrifie les proprits
Applications de la cryptographie la scurit des rseaux 301
suivantes :
- robustesse aux collisions (il est improbable que deux entres diffrentes pro
duisent la mme image).
Scurit
Les attaques que lon peut porter contre ce mcanisme sont assez frustes.
Deux sont toutefois possibles :
27.5 Kerberos
(3) ^
Dans la mythologie Grecque, Kerberos est le nom de lhydre trois ttes qui garde la
porte de lenfer.
302 Kerberos
27.5.1 Fonctionnement
S ,N ,T C tgs ,Ac t gs 3
U/C n
K(TC.S ,K )
I TGS e
K u(K ,N ,T c t g s )
(= ]
AS
S r
Tc,tgs =k TGS (U,C,TGS,T,L,K) ticket TGS
Tc s = K <5(U .C & T . L ,K )ticket de session
At tgs =KtC,T) authentificateur pour T c tgs
Aj. s = K (C ,T ) authentificateur pour Tc
(4 )
AS pour authentication serv er et TG S pour tick et granting service en anglais.
Applications de la cryptographie la scurit des rseaux 303
(2) AS lui retourne deux messages chiffrs avec K u , cl secrte partage entre
U et AS :
(3) U demande TGS un ticket pour se connecter au serveur S1, lui envoie un
jeton ainsi que TCjtgs et A Citgs-
(4) TGS lui retourne un message chiffr avec la cl de session K qui contient :
27.5.2 Alternatives
destinataire
Gnration de la signature
I\ T\
message m essage
V signature
N numrique
fonction
de 0100110 1100110 ],
hachage
\ empreinte Ni
h10010 transmis
au
cl prive de
lexpditeur destinataire
Secure Hash Algorithm conu par la NSA( > pour le NISTC*. SHA est une
fonction de hachage qui fournit une empreinte de 160 bits. Son fonctionnement
est analogue celui de MD5. On pourra trouver plus de dtails dans le livre de
B. Schneier [83].
PGP peut aussi utiliser MD5 pour les signatures pour des raisons de com
patibilit puisque les versions prcdentes de PGP utilisaient cette dernire
fonction de hachage. La raison du passage de MD5 vers SHA est que MD5 a
t partiellement cass par H. Dobbertin, un cryptanalyste allemand, en 1996.
Nous avons dcrit cette attaque au paragraphe 22.6.3
F7
K fon ction
message ---- 0100110
de
hachage empreinte
recalcule
signature
numrique;
J lldoilOl 0100110 [comparaison
empreinte
reue
S10010
cl publique de
lexpditeur
La gestion distribue des cls utilise dans PGP fonctionne l'aide de par
rains. Ceux-ci sont d autres utilisateurs du systme qui peuvent signer les cls
publiques de leurs amis. Par exemple, lorsque Bernard cre sa cl publique, il
en donne une copie Chlo et David. Ceux-ci connaissent Bernard et signent
sa cl publique en lui en renvoyant une copie signe. Maintenant, si Bernard
prsente sa cl publique une trangre, Alice, il lui prsente avec les signatures
de ses parrains. Si Alice connat et a confiance en Chlo, elle a raison de croire
que la cl de Bernard est valide. Si elle connat peu ou a peu confiance en Chlo
et David, elle a moins de raisons de croire que la cl de Bernard est valide. Si
elle ne connat ou na confiance ni en Chlo ni en David, elle na aucune raison
de faire confiance 1a. cl de Bernard.
Au cours du temps, Bernard collectera de plus en plus de parrains. Si Alice
et Bernard gravitent dans les mmes cercles, les chances de connatre un des
parrains de Bernard sont plus leves.
Pour se prmunir contre Oscar qui substitue une cl, les parrains doivent
sassurer que la cl de Bernard appartient bien celui-ci avant de la signer.
Les parrains peuvent demander que la cl leur soit communique lors d une
rencontre en personne ou vrifie par tlphone.
Lavantage de ce mcanisme est quil ne demande pas quil y ait de centre
de distribution de cls en qui tout le monde doit avoir confiance. Le dfaut est
que lorsque Alice reoit la cl publique de Bernard, il ny a aucune garantie
quelle connaisse un des parrains et quelle se fie donc cette cl.
SM TP HTTP
TCP ( T r a n sm is sio n C o n tr a t P r o t o c o l )
IP Security Protocol
AH. ESP)
IP I n t e r n e t P r o t o c o l
Ces deux mcanismes sont indpendants. Ils peuvent tre utiliss spar
ment, conjointement ou successivement. Ils ne dpendent pas dun algorithme
particulier et les systmes cryptographiques peuvent ainsi tre remplacs au
cours du temps.
Pour ces mcanismes, le transport des cls doit tre ralis par un protocole
de plus haut niveau, voire mme assur manuellement. Des techniques au niveau
applicatif sont bases sur le protocole de mise en accord de Diffie Hellman
comme dans le protocole d change de cl ISAKM P/Oakley que nous dcrivons
ci-dessous.
(2) il ngocie les associations de scurit pour IPSec (ce qui permet de dire
quels vont tre les mcanismes de scurit employs par la suite).
Une association de scurit est une structure qui dcrit les algorithmes
utiliss pour les diffrents mcanismes de scurit, par exemple quels sont les
chiffres utiliss ou les mthodes de signature.
Pour chacune de ces deux tapes, deux modes diffrents sont possibles : pour
tablir le canal scuris, on dispose des modes main (ou principal) et aggressive
Applications de la cryptographie la scurit des rseaux 309
(ou agressif) et pour ngocier les associations de scurit, des modes quick (ou
rapide) et new group (ou nouveau groupe). Nous dcrivons ces diffrents modes
ci-dessous.
M ode principal
Dans le mode principal, les deux parties utilisent les deux premiers messages
pour ngocier les associations de scurit de lchange lui-mme. Les deux mes
sages suivants effectuent une mise en accord de cls selon le protocole de Diffie-
Hellman et changent des messages pour sauthentifier mutuellement. Les deux
derniers messages sont utiliss pour authentifier les deux parties au moyen de
signatures et de hachage et, de manire optionnelle, en ayant recours des
certificats.
SA header ngocient
header SA termes change
KE+[Cr] header
change de cls
par Diffie-Hellman
header KE+[Cr]
F ig . 2 7 .8 IS A K M P /O a k le y M ain m ode.
M ode agressif
Dans la figure 27.10, les abrviations sont les mmes que pour la figure 27.9.
M ode rapide
Le mode rapide est utilis pour ngocier les associations de scurit d IPSec
et pour engendrer ventuellement une nouvelle cl partage. Si c est le cas, un
nouveau protocole de Diffie-Hellman est ralis. Sinon, les parties engendrent
simplement des cls en utilisant des fonctions de hachage et sidentifient mu
tuellement au moyen de jetons.
Hash3 header
F ig . 2 7 .1 1 IS A K M P /O a k le y Q uick m ode.
-t
* SA Hashj header
(D
O
header Hash2 SA
F ig . 2 7 .1 2 IS A K M P /O a k le y N ew G rou p m ode.
Une fois que les deux parties possdent une cl partage ainsi que les asso
ciations de scurit qui permettent de fixer :
Applications de la cryptographie la scurit des rseaux 311
m ode transport
< Authentifi
paquet d'origine
IP header TCP/U DP header Upper layer payload
m ode tu n n el
paquet avec AH
IP header AH header IP header TCP/UDP header Upper layer payload
A u th en tifi
<
mode transport
paquet ESP IP header ESP header TCP/UDP header Upper layer payload ESP traiier SPauth
L CUM >
^ Authentifi y
IP header AH header IP header TCP/UDP header Upper layer payload ESP traiter ESFauth
4 Chiffr
Authentifi y.
F on ction n em en t d e ssh
Blowfish, RC4. Nous allons dcrire brivement ces diffrentes tapes. Nous sup
poserons que les diffrentes cls publiques sont connues. Si elles ne le sont pas,
elles sont transmises au moyen de certificats par un mcanisme de transport de
cl analogue celui dcrit dans la section 26.3.
^ Signt/i(donne))
SM TP HTTP
TCP (T r a n s m is s io n C o n tr o l P r o t o c o l )
IP ( I n t e r n e t P r o to c o l)
Nous avons choisi de dtailler les principes essentiels de SSL3.0. Pour avoir
plus de dtails sur SSL, le lecteur intress pourra se reporter :
dvelopper.netscape. com /docs/m anuals/security/sslin/contents.htm
header confirmation
Les techniques cryptographiques utilises par SSL sont dfinies sous la forme
de CipherSuites. Celles-ci comprennent les chiffres suivants : RSA, RC4. RC2
(ces deux derniers sont des chiffres cl secrte conus par la firme RSA), IDEA,
DES, 3xDES et AES et les fonctions de hachage suivantes : MD5 et SHA.
Chaque message est numrot. On commence par calculer le MAC avant le
chiffrement. Celui-ci est fonction dune cl K et du numro dordre du message.
Le message et son MAC sont ensuite chiffrs soit au moyen dun chiffre de type
Vernam soit dcoups en blocs et chiffrs en mode CBC (sect. 19.2). La valeur
initiale requise pour le mode CBC est modifie chaque connexion.
Applications de la cryptographie la scurit des rseaux 317
TCP ( T r a n sm is sio n C o n tr o l P r o t o c o l ) IP I n t e r n e t P r o t o c o l
IP I n t e r n e t P r o t o c o l
Toutes les cls, valeurs initiales et cls de MAC, sont engendres partir
des paramtres de scurit obtenus lissue de la rencontre entre le client et
le serveur au moyen d une fonction de hachage. Le lecteur intress pourra se
reporter [33] pour le dtail de la drivation des cls.
dcalage Cl C2 C3 c4
init. 1 0 1 1
1 0 1 0 1
2 0 0 1 0
3 0 0 0 1
4 0 0 0 0
entre sortie
Cl C2 c3 c4
dcalage Cl C2 C3 C4
init. 1 0 1 1
1 1 1 0 1
2 1 1 1 0
3 0 1 1 1
4=init. 1 0 1 1
entre sortie
Ci c2 c3 c4
Cl c2 c3 c4
O0 1 ?--& k
Les registres linaires dcalage sont trs utiles pour effectuer les multipli
cations et les divisions de polynme sur F2. On utilise un registre dcalage
pour reprsenter un polynme p(x) G IF2\x\/(xn 1)- Chaque cellule contient
un des n coefficients du polynme.
Nous donnons ici la prsentation faite dans [11]. Le produit par un polynme
fix g(x) = (jl'x1, + . . . + y\x + go se fait au moyen du circuit de la figure A .4.
Pour cela, les coefficients de g{x) sont placs conmie indiqu dans la fi
gure A.4. Les entres et sorties du registre reprsentent respectivement les po
lynmes a(x) = akx k + . . . + UjX + ao et b{x) = bk+LXk+L + . . . + b\X + bo. Le
produit b(x) = a(x)g(x) scrit b(x) = bk+LXk+L+ . . .+bo avec bj = J2i=o Siaj - i
pour j G { 0 , . . . , k + L}.
bj = ^ gjj-j
i=0
entre C3 C2 Cl sortie
101 0 0 0
10 1 0 0 1
1 0 1 0 01
0 1 0 1 001
0 0 1 0 1001
0 0 0 1 11001
0 0 0 0 111001
b o , , b k + 3
fc
Soit b(x) y ;:; (|biX1 un polynme sur F2[x] diviser par g(x) = Y=o 9i%1
tel que g-,,- k = 1 (cas auquel on peut toujours se ramener). Soit r(x) lun des
restes partiels de la division. Il est de la forme :
On passe donc du reste partiel r(x) au reste partiel suivant dune manire
rcursive qui peut tre ralise pratiquement par le circuit de la figure A .6 en
utilisant un registre dcalage.
bn rQ r3
degr polynme
2 x2 + x + 1
3 x3 + x + 1
4 x4 + x + 1
5 X 5 1- X 2 + 1
6 X6 + X + 1
7 X7 + X + 1
8 X8 + X6 + x 5 + x 4 + 1
9 X9 + X4 + 1
10 X 10 + X 3 + 1
11 x 11 + X 2 + 1
12 x 12 + x 7 + x 4 + X 3 + 1
13 x 13 + X 4 + X 3 + X + 1
14 x 14 + x 12 + X 11 + X + 1
15 X 15 + X + 1
A nnexe C
[8] E.R. Berlekamp, R.J. McEliece, and H.C.A. van Tilborg. On the inherent
intractability of certain coding problems. IEEE Transactions on Informa
tion Theory, IT-24 :384-386, 1978.
[11] R.E. Blahut. Theory and practice of error-control codes. Addison Wesley,
1983.
[17] A.M. Cohen, H. Cuypers, and H. Sterk. Some tapas o f computer algebra.
Springer, 1999.
[20] T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to algorithm,s.
MIT Press, 1989.
[22] J. Daemen and V. Rijmen. The Rijndael bloc cipher. Technical report,
AES proposai, 1999.
[23] J. Daemen and V. Rijmen. The design of Rijndael. Springer Verlag, 2002.
[26] J.P. Delahaye. La compression des donnes. Pour la science, 217 :177 189,
1995.
[33] W . Fumy. Internet security protocols. In State o f the art in applied cryp
tography, number 1528 in LNCS, pages 186-206. Springer Verlag, 1997.
Bibliographie 341
[34] W . Fumy. Key management techniques, [n State o f the art in applied cryp-
tography, number 1528 in LNCS, pages 209 223. Springer Verlag, 1997.
[35] M.R. Garey and D.S. Johnson. Computers and intractahility. Freeman,
1979.
[41] C. Hare and Siyan K. Internet firewalls and network security. New Riders
Publishing, 1996.
[46] R. Hill. A first course in coding theory. Oxford University Press, 1986.
[47] D.G. Hoffman, D.A. Lonard, C.C. Linder, K.T. Phelps, C.A. Rodger, and
J.R. Wall. Coding theory, the essentials. Pure and applied mathematics.
Dekker, 1991.
[48] J.E. Hopcroft and J.D. Ullman. Introduction to autom.ata theory, lan-
guages, and computation. Addison-Wesley, 1979.
[52] G.A. Jones and J.M. Jones. Elementary number theory. SUMS. Springer
Verlag, 1997.
[55] L.R. Knudsen. Block ciphers - a survey. In Springer Verlag, editor, State
o f the art in applied cryptography, number 1528 in LNCS, pages 18-48,
1998.
[65] H.R. Lewis and C.H. Papadimitriou. Elments o f the theory of computa
tion. Prentice-Hall, 1981.
[67] SSH Communications Security Ltd. Ssh ipsec express. Technical report,
White Paper, 1998.
[68] F.J. MacWilliams and N.J.A. Sloane. The theory o f error correcting codes.
North-Holland, 1977.
[76] A. Poli and Ll. Huguet. Codes correcteurs. Number 1 in Logique, math
matiques, informatique. Masson, 1989.
[88] J.H. van Lint. Introduction to coding theory. Graduate texts in mathe-
matics. Springer Verlag, deuxime dition, 1992.
344 Codage, cryptologie & applications
[89] J.H. van Lint. Handbook o f combinatorics, volume 1, chapter Codes, pages
775 -807 North Holland, 1995.
[93] J. von zur Gathen and J. Gerhard. Modem Computer Algebra. Cambridge
University Press, 1999.
[98] A.C. Yao. Theory and applications of trapdoor functions. In Proc. 23rd
IEEE Symp. on Foundations of Computer Science, pages 80-91, 1982.
[100] J. Ziv and A. Lempel. A universal algorithm for sequential data com
pression. IEEE Transactions on Information Theory, IT-23(3) :337-343,
1977.
A la Documentation franaise
L e s t l c o m m u n i c a t i o n s f r a n a i s e s , Q uel statut p o u r qu elle entreprise ?, par
G. Bonnetblanc, 1985, 240 pages.
L a c o m m u n i c a t i o n a u QUOTIDIEN. D e la tradition e t du changem ent l au be d e la
vidocom m unication, par J. Jouet, avec la collaboration de N. Celle, 1985, 240 pages.
H i s t o i r e c o m p a r e d e s t r a t g i e s d e d v e l o p p e m e n t d e s t l c o m m u n i c a t i o n s , par
A.-M . Delaunay Macullan, 1997, 166 pages.