ACTIONS
La cryptographie
Le maillon faible de la cryptographie
est toujours l 'être humain.
la notion d'indice de coïncidence
L'indice de coïncidence d'un texte Test la probabilité
que deux lettres tirées au hasard dans ce texte coïncident. Si le nombre de A est égal à nA, le nombre de
couples de deux A est égal à nA (nA - l) celui de B,
2
'
na (na - l) , etc. En faisant la somme de tous ces nombres,
2
on trouve le nombre de couples formés de deux lettres
identiques. Le nombre de couples quelconques dans le
texte est égal à n(n - l) donc la probabilité pour que
2
deux lettres d'un texte coïncident vaut:
I
n,1(n,1 -l)+n 8 (n 8 -1)+ ... +nz(nz -1)
c -
•
n(n-1)
Si on note/A,/ 8 ... /z les fréquences des lettres dans le
texte (nA = n/A par exemple), on peut écrire:
1 _ nfA(nfA -1)+ ... __ n_(/,2
}--1-(/,
)
C
A+...
A+ ...•
n(n -1)
n -1
n -1
On en déduit que le - _!!__ S - -
1 - où S est la somme
n-1
n-1
des carrés des fréquences des lettres.
Dans les applications, on peut donc employer S au lieu
de l'indice de coïncidences car, si le texte est relativement long, net n -1 sont à peu près égaux et 1 est négligeable devant n donc S et le peuvent être confondus.
Po ur déte rm iner la longueur d ' une cle f
de Vigenère, Wi ll iam Friedman ( 189 11969) eut l' idée d ' introduire un indice
invariable par pe rmutation des lettres.
Ain si, sa valeur n 'est pas affectée par
une substituti on alphabétique simple,
te lle celles engendrées par le code de
César. Pour obtenir un te l ind ice, ! ' idée
la plus simple est d 'additionner les carrés des fréquences des lettres . Plus préciséme nt , dans un tex te T do nné , o n
co mpte le nombre d 'occ urre nces de
chaq ue lettre: nA pour A , n 8 pour B . ..
et n 2 pour Z . On en fa it la somme n ,
qui est do nc la longueur du tex te, pui s
I
d
,
2
?
2 0
a somme es carres n.A , 11 8
- ... n 2 . n
di vise enfin cette dernière somme par
le carré den . S i on échange les lettres ,
les pos itions des carrés des fréquences
so nt modifi ées da ns la so mme ma is
celle-c i reste identique pui sque tous les
carrés s'y retro uve nt malgré la permutation . Ce no mbre n' ayant pas de sens
concret , o n préfère en utili ser un autre ,
qui est très proc he , appe lé indice de
coïncidence (voir l'encadré). Sans moyen
é lectronique, le calcul est très long donc
imprati cable, d 'où le beso in de créer
un moyen de calcul pui ssant et fia ble.
À partir des fréqu e nces usue ll es , o n
peut déterminer l'indice de coïncidence
moye n d ' un tex te fra nça is, o u da ns
d 'autres langues, éventue lle ment codé
par un chiffre te l celui de César ! li suffit de fa ire la somme des fréquences
moyennes au carré.
A
B
c D E
F
G
8,4
1, 1
3
4,2 17,3 1, 1
1,3
H
1
J
K
L
M
N
0 ,9
7,3
0,3
0,1
6
3
7,1
0
p
Q
R
s
T
u
5,3
3,0
6,5
8,1
7,1
5,7
V
w X y
z
1,3
0,1
0,4
0 ,3
0, 1
Tableau de fréquences des lettres
en fra nçais, exprimées en pourcentages.
En fra nça is, l' indi ce de coïnc ide nce
moyen est donc égal à la somme
0 ,084
2 +0 ,0 11
2 + . .. + 0 ,00 12,
soit 0 ,0746. Dans le cas d ' un message
où les lettres seraient choisies au hasard ,
on trou ve une fréque nce moyenne de
1 /26. L' ind ice est donc égal à 26 fo is
( 1 / 26)2 , c'est-à-dire à 1 / 26, soit 0,038.
Il s'agit de l' indice de coïncidence moyen
d' un tex te aléato ire .
Prenons un message chiffré par la méthode
de Vi genère , par exemple :
Ta.ngent:e Hors-série n°52. Mathématiques & informatique
La cryptographie
Le maillon faible de la cryptographie
est toujours l 'être humain.
la notion d'indice de coïncidence
L'indice de coïncidence d'un texte Test la probabilité
que deux lettres tirées au hasard dans ce texte coïncident. Si le nombre de A est égal à nA, le nombre de
couples de deux A est égal à nA (nA - l) celui de B,
2
'
na (na - l) , etc. En faisant la somme de tous ces nombres,
2
on trouve le nombre de couples formés de deux lettres
identiques. Le nombre de couples quelconques dans le
texte est égal à n(n - l) donc la probabilité pour que
2
deux lettres d'un texte coïncident vaut:
I
n,1(n,1 -l)+n 8 (n 8 -1)+ ... +nz(nz -1)
c -
•
n(n-1)
Si on note/A,/ 8 ... /z les fréquences des lettres dans le
texte (nA = n/A par exemple), on peut écrire:
1 _ nfA(nfA -1)+ ... __ n_(/,2
}--1-(/,
)
C
A+...
A+ ...•
n(n -1)
n -1
n -1
On en déduit que le - _!!__ S - -
1 - où S est la somme
n-1
n-1
des carrés des fréquences des lettres.
Dans les applications, on peut donc employer S au lieu
de l'indice de coïncidences car, si le texte est relativement long, net n -1 sont à peu près égaux et 1 est négligeable devant n donc S et le peuvent être confondus.
Po ur déte rm iner la longueur d ' une cle f
de Vigenère, Wi ll iam Friedman ( 189 11969) eut l' idée d ' introduire un indice
invariable par pe rmutation des lettres.
Ain si, sa valeur n 'est pas affectée par
une substituti on alphabétique simple,
te lle celles engendrées par le code de
César. Pour obtenir un te l ind ice, ! ' idée
la plus simple est d 'additionner les carrés des fréquences des lettres . Plus préciséme nt , dans un tex te T do nné , o n
co mpte le nombre d 'occ urre nces de
chaq ue lettre: nA pour A , n 8 pour B . ..
et n 2 pour Z . On en fa it la somme n ,
qui est do nc la longueur du tex te, pui s
I
d
,
2
?
2 0
a somme es carres n.A , 11 8
- ... n 2 . n
di vise enfin cette dernière somme par
le carré den . S i on échange les lettres ,
les pos itions des carrés des fréquences
so nt modifi ées da ns la so mme ma is
celle-c i reste identique pui sque tous les
carrés s'y retro uve nt malgré la permutation . Ce no mbre n' ayant pas de sens
concret , o n préfère en utili ser un autre ,
qui est très proc he , appe lé indice de
coïncidence (voir l'encadré). Sans moyen
é lectronique, le calcul est très long donc
imprati cable, d 'où le beso in de créer
un moyen de calcul pui ssant et fia ble.
À partir des fréqu e nces usue ll es , o n
peut déterminer l'indice de coïncidence
moye n d ' un tex te fra nça is, o u da ns
d 'autres langues, éventue lle ment codé
par un chiffre te l celui de César ! li suffit de fa ire la somme des fréquences
moyennes au carré.
A
B
c D E
F
G
8,4
1, 1
3
4,2 17,3 1, 1
1,3
H
1
J
K
L
M
N
0 ,9
7,3
0,3
0,1
6
3
7,1
0
p
Q
R
s
T
u
5,3
3,0
6,5
8,1
7,1
5,7
V
w X y
z
1,3
0,1
0,4
0 ,3
0, 1
Tableau de fréquences des lettres
en fra nçais, exprimées en pourcentages.
En fra nça is, l' indi ce de coïnc ide nce
moyen est donc égal à la somme
0 ,084
2 +0 ,0 11
2 + . .. + 0 ,00 12,
soit 0 ,0746. Dans le cas d ' un message
où les lettres seraient choisies au hasard ,
on trou ve une fréque nce moyenne de
1 /26. L' ind ice est donc égal à 26 fo is
( 1 / 26)2 , c'est-à-dire à 1 / 26, soit 0,038.
Il s'agit de l' indice de coïncidence moyen
d' un tex te aléato ire .
Prenons un message chiffré par la méthode
de Vi genère , par exemple :
Ta.ngent:e Hors-série n°52. Mathématiques & informatique