Introduction aux codes secrets.pdf

(67 KB) Pobierz
Les codes secrets
Introduction aux codes
secrets
Michel Van Caneghem
Février 2001
Le chiffrage - déchiffrage ou codage, décodage est une
science qui s’appelle la cryptographie
INTERCEPTEUR
Clé k
Clé k
Message m
Encodage
Décodage
Message m
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
On ne peut envisager que l’ensemble du système, c’est à
dire à la fois comment décoder et coder un message, mais
aussi s’il est possible d’intercepter un message codé.
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
1
Pourquoi le secret
Traditionellement les codes secrets étaient l’affaire des mi-
litaires et des diplomates. Maintenant c’est également :
"
Le problème des banques (transfert d’argent, carte de
crédits,...)
"
Le problème des informaticiens (mot de passe, protection
contre le piratage)
"
Le problème des sociétés (coffre fort électronique)
"
Le problème de tout le monde : Internet et la protection
de la vie privée.
Quel secret
Pour élaborer un système de protection il faut évaluer :
#
La sécurité recherchée (durée de vie de l’information)
#
La taille de la clé
#
La simplicité et l’efficacité des opérations de codage et
décodage
Pour évaluer la protection, il faut imaginer le pire des cas :
c’est à dire le meilleur pour l’intercepteur :
$
Le décrypteur à une complète connaissance du système
$
Le décrypteur a accès à une quantité importante de texte
codé.
$
Le décrypteur connait une partie en clair du message
codé.
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
2
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
3
La machine Enigma
utilisée par les allemands pendant la dernière guerre
Lettre de George Sand à Alfred de Musset
Je suis très émue de vous dire que j’ai
bien compris l’autre soir que vous aviez
toujours une envie folle de me faire
danser. Je garde le souvenir de votre
baiser et je voudrais bien que ce soit
là une preuve que je puise être aimée
par vous. Je suis prête à vous montrer mon
affection toute désintéressée et sans cal-
cul, et si vous voulez me voir aussi
vous dévoiler sans artifice mon âme
toute nue, venez me faire une visite.
.........................George
Sand
4
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
5
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
Réponse d’Alfred De Musset :
Ce que l’on va examiner
Les premiers ordinateurs ont été construits pendant la
guerre pour pouvoir casser les codes secrets allemand et
autres...
Nous étudierons :
%
Les codes secrets anciens
%
Comment casser les codes secrets anciens ?
%
Le DES
%
Les codes a clés publiques : RSA
Quand je mets a vos pieds un éternel hommage,
Voulez-vous qu’un instant je change de visage ?
Vous avez capturé les sentiments d’un coeur
Que pour vous adorer forma le créateur.
Je vous chéris, amour, et ma plume en délire
Couche sur le papier ce que je n’ose dire.
Avec soin de mes vers lisez les premiers mots,
Vous saurez quel remède apporter à mes maux.
Alfred de Musset
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
6
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
7
Chiffre monoalphabétique
On remplace un alphabet par un autre. Il y a en tout
26!
codes possibles. Un sous ensemble auquel on peut s’in-
téresser : les codes basés sur l’arithmétique modulaire.
La clé est constituée de deux nombres
a
et
b.
On chiffre avec
la formule suivante :
C
≡
aP
+
b
(mod 26)
C
représente le texte codé (Coded) et
P
représente le texte
en clair. Chaque lettre est transformée en un chiffre (A
= 0,
Z
= 25).
On décode avec :
P
≡
a
−1
(C
−
b)
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
Chiffre monoalphabétique (2)
à condition que
a
∧
26 = 1.
Il y a donc
12
×
26 = 312
codes
possibles.
Si
a
= 1
et
b
= 3,
on obtient le code de César.
On remarque que les fréquences des lettres ne change pas
avec un tel code : d’ou la méthode pour casser le code. On
définit la probabilité de coincidence comme la probabilité
que deux lettres prises au hasard soient identiques :
Z
λ=A
f
λ
(f
λ
Ic
=
Z
−
1)
n(n
−
1)
χ
anglais
= 0, 065
χ
alea
= 0, 038
9
(mod 26)
8
χ
p
=
λ=A
p
2
λ
χ
f rancais
= 0, 079
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
Fréquence des lettres du français
A
B
C
D
E
F
G
H
I
0.083944
0.007669
0.033297
0.040699
0.145037
0.012109
0.009495
0.007973
0.081828
J
K
L
M
N
O
P
Q
R
0.006377
0.000638
0.058405
0.029355
0.075570
0.053669
0.032087
0.012613
0.070209
S
T
U
V
W
X
Y
Z
0.080091
0.074775
0.059808
0.015791
0.000067
0.004098
0.003155
0.001240
Le Scrabble
Fréquence des lettres (2)
E 15
A 9
N 6
S 6
I 8
T 6
R 6
L 5
O 6
U 6
D
C
P
M
3
2
2
3
Q
V
G
F
B
1
2
2
2
2
H
X
J
Y
K
Z
W
2
1
1
1
1
1
1
Les plus fréquentes : E (145), A (84), I (81), S (80), N (76), T
(75), R (70).
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
10
N
= 100,
χ
p
= 0, 069
11
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
Remarque
Attention : ces chiffres ne représentent qu’une moyenne. Voici un
exemple ou la table de fréquence est fausse :
PEREC, Georges, La dis-
parition, Gallimard, L’imaginaire, Paris, 1969.
qui est un livre écrit sans
la lettre E. En voici un extrait :
«Il y avait au mur un rayon d’acajou qui supportait vingt-six in-folios. Ou
plutôt, il aurait dû y avoir vingt-six in-folios, mais il manquait, toujours,
l’in-folio qui offrait (qui aurait dû offrir) sur son dos l’inscription "CINQ".
Pourtant, tout avait l’air normal : il n’y avait pas d’indication qui signalât
la disparition d’un in-folio (un carton, "a ghost" ainsi qu’on dit à la Na-
tional Library) ; il paraissait n’y avoir aucun blanc, aucun trou vacant. Il
y avait plus troublant : la disposition du total ignorait (ou pis : masquait,
dissimulait) l’omission : il fallait la parcourir jusqu’au bout pour savoir,
la soustraction aidant (vingt-cinq dos portant subscription du "UN" au
"VINGT-SIX", soit vingt-six moins vingt-cinq font un), qu’il manquait un
in-folio ; il fallait un long calcul pour voir qu’il s’agissait du "CINQ".»
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
12
Un exemple de déchiffrage
texte en clair
Voici un premier texte qui est tres facile a decoder. Il faut
quand meme que le texte soit assez long.
A
M
N
Z
B C D E F G H I J K L M
N O P Q R S T U V W X Y
O P Q R S T U V W X Y Z
A B C D E F G H I J K L
texte codé
HAUOU GZBDQ YUQDF QJFQC GUQEF FDQER MOUXQ
MPQOA PQDUX RMGFC GMZPY QYQCG QXQFQ JFQEA
UFMEE QLXAZ S
Voir démonstration
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
13
Un exemple de déchiffrage (2)
Un code monoalphabétique choisit au hasard.
texte codé
JYLDL VR CGMCG SGQVDYVU UEVX EYRJ. DYTTG BYVX
EG DYRXCQCGO, BYVX XVLBGO VR DYVWX HYWTLF-
QSEG XVW EGX DYFGX XGDWGCX. EYVW CWYVBGO
EG DYFG LE HQVC VRG DGWCQLRG EYRJVGVW. ZG
EQ UQWC FGX GEGBGX WGDYRRQLXQRC Q EGVW
UWYHGXXGVW.
Voir démonstration
Chiffre de Vigenère
vers 1560,
le diplomate français Blaise de Vigenère,
s’ins-
pirant des travaux de Leon Batista Alberti et de Jean Tri-
thème, mit au point une grille de 26 alphabets (autant que
de lettres), chacun étant décalé d’un cran par rapport au
précédent. On plaçait au-dessus le texte à coder, et on en
remplaçait successivement chaque lettre par l’une de celles
qui se trouvait en-dessous, en changeant de ligne à chaque
fois, selon un ordre donné par un mot clé.
Le système polyalphabétique de Vigenère résista pendant
environ trois siècles, jusqu’à ce que le mathématicien bri-
tannique Charles Babbage élabore la théorie de son déco-
dage, vers 1854.
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
15
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
14
Chiffre de Vigenère (2)
Méthode de chiffre par substitution polyalphabétique. Une
suite de lettre est prise comme clé :
k
1
, k
2
, . . . , k
n
. On dé-
coupe alors le message en blocs de longueur
n.
Soit
p
1
, p
2
, . . . , p
n
un tel bloc. Il est alors codé de la manière sui-
vante :
c
i
≡
p
i
+
k
i
(mod 26)
ABCDEFGHIJKLMNOPQRSTUVWXYZ
CDEFGHIJKLMNOPQRSTUVWXYZAB
(1) :
k
1
= +2
LMNOPQRSTUVWXYZABCDEFGHIJK
(2) :
k
2
= +11
EFGHIJKLMNOPQRSTUVWXYZABCD
(3) :
k
3
= +4
Chiffre de Vigenère (3)
Message original :
UNCOURSPASSIONNANT,
clé =
CLE
C
2
U
W
L
11
N
Y
E
4
C
G
C
2
O
Q
L
11
U
F
E
4
R
V
C
2
S
U
L
11
P
A
E
4
A
E
C
2
S
U
L
11
S
D
E
4
I
M
C
2
O
Q
L
11
N
Y
E
4
N
R
C
2
A
C
L
11
N
Y
E
4
T
X
voici le message codé :
WYGQF VUAEU DMQYR CYX
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
16
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
17
Déchiffrage du code de Vigenère
L’ avantage principal de ce code est que l’on ne peut plus
se servir directement des fréquences des lettres pour le dé-
chiffrer. Il y a cependant des méthodes pour casser ce code.
Il faut essayer de deviner la taille de la clé (m). Ensuite si le
texte est assez long (n), chaque ligne correspond à un code
mono-alphabétique simple.
Remarque 1 :
On calcule tout d’abord l’indice de coinci-
dence
Ic
:
Z
f
λ
(f
λ
−
1)
Ic
=
λ=A
n(n
−
1)
Déchiffrage du code de Vigenère (2)
Pour le français (χ
f rancais
= 0, 079)
on a :
1
n
n
1
1
n(n
−
1)Ic =
n(
−
1).χ
f rancais
+
n(n
−
).0, 038
2
2
m
2
m
On trouve alors pour le français :
0.041n
m
=
Ic(n
−
1)
−
0.038n + 0.079
et pour l’anglais :
0.027n
m
=
Ic(n
−
1)
−
0.038n + 0.065
Remarque :
Test de Kasiski : Si une même séquence se ré-
pète alors
la distance
entre les deux séquences doit être
un
multiple
de la taille de la clé.
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
19
Turing : des codes secrets aux machines universelles #4 c 2001 MVC
18

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin