240
7 La cryptographie ` a cl´ e publique
la division de m
7 par n (c’est-` a-dire m
7
≡ a (mod n)). Vous expliquez que B´ eatrice
d´ ecode avec la cl´ e de d´ ecryptage
d =
3(p − 1)(q − 1) + 1
7
.
Elle calcule a
d et le reste m 1 de la division de a
d par n (c’est-` a-dire a
d
≡
m 1 (mod n)), o` u m 1 ∈ {1, . . . , n − 1}. Vous affirmez que ce reste est le message
d’Alain.
a) V´ erifiez que d est bien un entier.
b) Expliquez pourquoi a et m 1 ne peuvent s’annuler, c’est-` a-dire qu’on a bien
a, m 1 ∈ {1, . . . , n − 1}.
c) Montrez que m 1 = m, c’est-` a-dire que B´ eatrice d´ ecodera bien le message
d’Alain.
7. Voici un principe simple de cryptographie. Le carr´ e blanc est repr´ esent´ e par le
chiffre 0. Les lettres A, . . . , Z par les nombres 1, . . . , 26. Le nombre 27 correspond
au point et le nombre 28, `
a la virgule. La table ci-dessous r´ esume ceci :
Symbole ` a coder
A B
C D
E F
G H
I
J
K
L
M
N
Nombre associ´ e
0
1
2
3
4
5
6
7
8
9 10
11
12
13
14
Symbole ` a coder
O
P
Q
R
S
T
U
V
W X
Y
Z
.
,
Nombre associ´ e
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Voici comment on code un mot :
• on remplace les symboles par leurs nombres associ´ es ;
• on multiplie par 2 le nombre associ´ e ` a chaque symbole ;
• on r´ eduit le r´ esultat obtenu modulo 29 ;
• on trouve les symboles correspondant aux nombres obtenus : ceci nous donne
le mot cod´ e.
Par exemple, pour coder le mot « LA » on remplace ses lettres par les nombres
12, 1. On les multiplie par 2 et on obtient 24, 2. On les r´ eduit modulo 29 (ici, ce
n’est pas n´ ecessaire). La lettre associ´ ee ` a 24 est X ; celle associ´ ee ` a 2 est B. Le mot
cod´ e repr´ esentant « LA » est « XB ».
a) Coder le mot « OUI ».
b) Expliquer pourquoi le code est inversible et comment on s’y prend pour d´ ecoder.
c) D´ ecoder le mot « XMF ».
8. On consid` ere ici une it´ eration du principe pr´ ec´ edent. On utilise les 29 symboles de
l’exercice 7. Voici comment on code un mot form´ e de tels symboles :
• on remplace les symboles par leurs nombres associ´ es ;
• on multiplie par 3 le nombre associ´ e ` a chaque symbole et on ajoute 4 ;
• on r´ eduit le r´ esultat obtenu modulo 29 ;
• on trouve les symboles correspondant aux nombres obtenus. Ceci nous donne
le mot cod´ e.
7 La cryptographie ` a cl´ e publique
la division de m
7 par n (c’est-` a-dire m
7
≡ a (mod n)). Vous expliquez que B´ eatrice
d´ ecode avec la cl´ e de d´ ecryptage
d =
3(p − 1)(q − 1) + 1
7
.
Elle calcule a
d et le reste m 1 de la division de a
d par n (c’est-` a-dire a
d
≡
m 1 (mod n)), o` u m 1 ∈ {1, . . . , n − 1}. Vous affirmez que ce reste est le message
d’Alain.
a) V´ erifiez que d est bien un entier.
b) Expliquez pourquoi a et m 1 ne peuvent s’annuler, c’est-` a-dire qu’on a bien
a, m 1 ∈ {1, . . . , n − 1}.
c) Montrez que m 1 = m, c’est-` a-dire que B´ eatrice d´ ecodera bien le message
d’Alain.
7. Voici un principe simple de cryptographie. Le carr´ e blanc est repr´ esent´ e par le
chiffre 0. Les lettres A, . . . , Z par les nombres 1, . . . , 26. Le nombre 27 correspond
au point et le nombre 28, `
a la virgule. La table ci-dessous r´ esume ceci :
Symbole ` a coder
A B
C D
E F
G H
I
J
K
L
M
N
Nombre associ´ e
0
1
2
3
4
5
6
7
8
9 10
11
12
13
14
Symbole ` a coder
O
P
Q
R
S
T
U
V
W X
Y
Z
.
,
Nombre associ´ e
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Voici comment on code un mot :
• on remplace les symboles par leurs nombres associ´ es ;
• on multiplie par 2 le nombre associ´ e ` a chaque symbole ;
• on r´ eduit le r´ esultat obtenu modulo 29 ;
• on trouve les symboles correspondant aux nombres obtenus : ceci nous donne
le mot cod´ e.
Par exemple, pour coder le mot « LA » on remplace ses lettres par les nombres
12, 1. On les multiplie par 2 et on obtient 24, 2. On les r´ eduit modulo 29 (ici, ce
n’est pas n´ ecessaire). La lettre associ´ ee ` a 24 est X ; celle associ´ ee ` a 2 est B. Le mot
cod´ e repr´ esentant « LA » est « XB ».
a) Coder le mot « OUI ».
b) Expliquer pourquoi le code est inversible et comment on s’y prend pour d´ ecoder.
c) D´ ecoder le mot « XMF ».
8. On consid` ere ici une it´ eration du principe pr´ ec´ edent. On utilise les 29 symboles de
l’exercice 7. Voici comment on code un mot form´ e de tels symboles :
• on remplace les symboles par leurs nombres associ´ es ;
• on multiplie par 3 le nombre associ´ e ` a chaque symbole et on ajoute 4 ;
• on r´ eduit le r´ esultat obtenu modulo 29 ;
• on trouve les symboles correspondant aux nombres obtenus. Ceci nous donne
le mot cod´ e.