Arithmetique et cryptologie.pdf

(160 KB) Pobierz
.
Arithmétique et cryptologie
Karim Belabas
Karim.Belabas@math.u-psud.fr
http://www.math.u-psud.fr/~belabas/
Universit´ Paris-Sud
e
France
Fˆte de la Science 2003 (Orsay) – p. 1/16
e
Chiffrer (1/3)
n grand nombre d’( informations
)
peuvent se traduire numériquement
(
)
arfois imparfaitement, mais avec des différences imperceptibles). Par
xemple un programme informatique, un CD, une image, un texte.
Un mathématicien est une machine à
transformer le café en théorèmes.
– Paul Erdös
e texte-ci par exemple :
n peut le coder en
ASCII
: chaque signe est représenté par deux symboles,
hoisis parmi les
16
suivants
{0,
1, 2, 3, 4, 5, 6, 7, 8, 9,
a, b, c, d, e, f},
est-à-dire un nombre à deux chiffres en base
16
:
‘U’
‘n’
−→
−→
55,
6e,
‘ ’
‘m’
−→
−→
20,
6d,
...
Fˆte de la Science 2003 (Orsay) – p. 2/16
e
Chiffrer (2/3)
n peut interpréter cette suite de chiffres comme un grand nombre, écrit en
ase
16
:
n
m a t h ´ m a t i c i e n
e
e s t
u n e
m a c h
56e206d617468e96d6174696369656e2065737420756e65206d6163686
6e6520e0207472616e73666f726d6572206c6520636166e920656e2074
8e96f72e86d65732e202d2d205061756c20457264f673
(base
16)
=
3 + 7
×
16
1
+ 6
×
16
2
+ 15
×
16
3
. . .
=
9781154227264479227165858852054752813050341969418003789560
1073332481166880538368439248938141894959742557027653964490
2897857270188655105046183260538732733952271900145229312269
6244913388202030707.
(base
10
:
197
chiffres décimaux).
Fˆte de la Science 2003 (Orsay) – p. 3/16
e
Chiffrer (3/3)
hiffrer
: modifier une information, en utilisant une procédure secrète ou
clé.
échiffrer
: le retrouver en utilisant la clé.
écrypter
: découvrir la clé.
+
1
+
1
n chiffrage très simple :
A
−→
B
,
B
−→
C
, etc.
Bonjour
− − →
Cpokpvs
− − →
Bonjour
−−
−−
+1
−1
us compliqué : faire des groupes de lettres et les décaler en changeant le
écalage au sein du groupe
Bonjour
− − →
Crpkrws
− − →
Bonjour
−−
−−
+1,3,2
−1,3,2
n dit que
1, 3, 2
(ou
132)
est la
clé
utilisée pour chiffrer le message. Dans ce
as, plus la clé est longue, plus il est difficile de
décrypter.
roblèmes :
comment se mettre d’accord sur une clé sans risque d’interception ?
chiffrer/déchiffrer sont des opérations très proches. Si le chiffreur se fait
endre, et avec lui la clé, l’ennemi peut déchiffrer tous les messages.
Fˆte de la Science 2003 (Orsay) – p. 4/16
e
Échange de clés (1/2)
natole
et
Barnabé
choisissent en secret, un entier chacun :
a
pour Anatole,
b
our Barnabé. Ils se téléphonent, choisissent un ensemble
G
dont ils savent
ultiplier les éléments (par exemple, les entiers) et un objet
g
dans cet
nsemble (par exemple le nombre
10).
s dévoilent chacun
A
=
g
a
et
B
=
g
b
(a et
b
restent secrets !). Tous deux
euvent alors calculer la clé secrète :
clé
:=
A
b
=
B
a
=
g
ab
n espion éventuel ne connaît que
g,
A,
et
B.
L’opération qui consiste à
trouver
a
à partir de
A
ou
b
à partir de
B
s’appelle
extraire un logarithme
(en
ase
g).
Il faut que ce soit une opération difficile pour empêcher l’espion de
éterminer la
clé.
Malheureusement, si
G
=
N
c’est beaucoup trop simple. Par
xemple, si
g
= 10,
pour résoudre
10
x
= 1000000000,
il suffit de compter les 0
= 9).
Fˆte de la Science 2003 (Orsay) – p. 5/16
e

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin