Agr´
egation interne 2014/2015
S´
eance du 21 octobre 2014 de 9h30 `
a 12h30
Arithm´etique dans Z - Cryptographie
R´
evisions de cours
1) Revoir une construction de Z `
a partir de l’ensemble N des entiers naturels.
2) Quelles propri´et´es de Z permettent de d´efinir la division euclidienne ? Enoncer et d´emontrer le th´eor`eme.
3) Revoir la d´efinition d’un id´eal dans un anneau commutatif. D´eterminer les sous-groupes additifs de Z,
puis les id´eaux de Z. En d´eduire que Z est principal.
4) Soit a et b deux ´el´ements non nuls de Z. D´efinir le pgcd et le ppcm de a et b, puis montrer leur existence.
A quelle propri´et´e de Z est-ce reli´e ?
5) Congruences - th´eor`eme chinois - anneaux Z/nZ.
6) Principes et exemples de chi↵rements `
a cl´e priv´ee (cf exercices 9,10,11).
7) Principes et exemples de chi↵rements `
a cl´e publique (cf exercices 12,13).
R´
ef´
erences
Bailly-Maitre, Gilles. — Arithm´etique et cryptologie, R´ef´erences sciences , Ellipses, Paris, (2012).
Dubertret, Gilles. — Initiation `
a la cryptographie, DUT et licence math´ematiques et informatique , Vuibert,
Paris, (2012).
Ramis, Jean-Pierre - Warusfel, Andr´e (sous la direction de). — Math´ematiques, tout-en-un pour la licence,
S´erie Ramis L1, Dunod, Paris, (2006).
Robin, Guy. — Apprenons l’arithm´etique ´el´ementaire pour comprendre la cryptographie moderne, , IREM
de Limoges, Limoges, (1998).
Terracher, Pierre-Henri - Ferachoglou, Robert. — Math, enseignement de sp´ecialit´e, Collection Terracher
Terminale S, Hachette, Paris, (1998).
Exercices divers
Exercice 1 (Crible d’Eratosth`ene)
C’est une m´ethode pour trouver tous les nombres premiers plus petits qu’un entier n.
a) On prend n = 40 : ´ecrire tous les nombres jusqu’`
a 40, barrer successivement tous les multiples de 2, sauf
2, tous les multiples de 3, sauf 3, etc... Jusqu’`
a quel nombre faut-il aller pour affirmer que seuls les nombres
premiers ne sont pas barr´es ?
b) G´en´eralisation `
a tout n entier.
c) Ecrire, puis programmer l’algorithme.
Exercice 2
D´emontrer le th´eor`eme d’Euclide : il existe une infinit´e de nombres premiers.
Exercice 3
D´emontrer que l’´equation en nombres entiers x2 + 1 = 3y 2 n’admet pas de solution. G´en´eraliser.
Solution : L’´equation modulo 3 devient x2 + 1 ⌘ 0[3] ; puisque 1 n’est pas un carr´e modulo 3, il n’y a pas de solution.
On peut g´
en´
eraliser `
a x2 + 1 = my 2 ; lorsque 1 n’est pas un carr´
e modulo m, il n’y a pas de solution.
Exercice 4 Calculs modulo 7
a) Dresser la table de multiplication dans Z/7Z.
b) R´esoudre dans Z la congruence x2 + 3 ⌘ 0 mod 7.
1
Exercice 5
a) Trouver par deux m´ethodes di↵´erentes les P GCD et P P CM de 5940 et 924.
b) Trouver tous les diviseurs communs de 5940 et 924.
Exercice 6
a) En utilisant l’algorithme d’Euclide trouver deux entiers u et v tels que 70u + 99v = 1.
Solution : 1 = 29 ⇥ 99 41 ⇥ 70.
b) Tel couple (u, v) est-il unique ?
c) R´esoudre dans Z2 l’´equation 70u + 99z = 11.
Solution : (u, v) = (29 ⇥ 11 + 70r, 41 ⇥ 11 99r).
Exercice 7 R´esidus quadratiques
Soit n un entier, n 2 et p un nombre premier impair. Pour x un entier, on note x˙ la classe de x dans Z/nZ.
On dit que x˙ est un carr´e ou r´esidu quadratique s’il existe y˙ 2 Z/nZ tel que y˙ 2 = x.
˙
a) D´eterminer les carr´es dans Z/13Z et dans Z/19Z.
b) Montrer que, dans Z/pZ, il y a exactement p+1
carr´es et que tout carr´e non nul admet deux racines
2
distinctes.
Solution : Consid´erons l’application ' : (Z/pZ)⇥ ! (Z/pZ)⇥ qui a` x˙ associe '(x)
˙ = x˙ 2 ; c’est un morphisme de
groupes et x˙ 2 = ( x)
˙ 2 . On en d´eduit que Ker ' = {±1} ; le noyau a deux ´el´ements, donc l’image a p 2 1 ´el´ements. Il y
p 1
p+1
a donc 2 carr´
es non nuls, ce qui fait 2 carr´
es modulo p et deux racines distinctes par carr´
e non nul.
p+1
p+1
c) Supposons que p ⌘ 3 mod 4. Montrer que si a˙ est un carr´e dans Z/pZ, alors ses racines sont a˙ 4 et a˙ 4 .
Solution : L’hypoth`ese p ⌘ 3 mod 4 permet de dire que p + 1 est divisible par 4 ; puisque a˙ est un carr´e, il existe x˙ tel
p+1
p+1
p+1
que a
˙ = x˙ 2 . On calcule alors (a˙ 4 )2 = (x˙ 2 )2 = x˙ p+1 = x˙ 2 = a˙ ; de mˆeme pour a˙ 4 .
d) Soit n = pq (entier de Blum) o`
u p et q sont congrus `
a 3 modulo 4. Montrer que a˙ est un carr´e dans Z/nZ
si et seulement si ses r´eductions dans Z/pZ et Z/qZ sont des carr´es.
Solution : Si a˙ est un carr´e, alors les r´eductions de a˙ dans Z/pZ et Z/qZ sont des carr´es.
R´
eciproquement, si a ⌘ x2 mod p et a ⌘ y 2 mod q , par le th´
eor`
eme chinois, comme p et q sont premiers entre eux, il
existe un entier m, unique modulo pq tel que m ⌘ x mod p et m ⌘ y mod q . On a alors a
˙ =m
˙ 2.
2
e) En d´eduire que si a˙ est un carr´e non nul dans Z/nZ, l’´equation x˙ = a˙ admet 4 solutions.
p+1
q+1
p+1
q+1
p+1
q+1
Solution : les quatre couples (a 4 mod p, a 4 mod q), (a 4 mod p, a 4 mod q),( a 4 mod p, a 4 mod q)
p+1
q+1
et ( a 4 mod p, a 4 mod q) fournissent via le th´
eor`
eme chinois les 4 solutions modulo pq .
Exercice 8 Logarithmes discrets
Soit p un nombre premier et g˙ un g´en´erateur de Z/pZ. Le probl`eme du logarithme discret est la r´esolution
de l’´equation g˙ x = a,
˙ pour a˙ donn´e dans (Z/pZ)⇥ .
a) Montrer que le probl`eme admet toujours une unique solution comprise entre 0 et p 2.
Solution : Puisque g˙ est un g´en´erateur de (Z/pZ)⇥ , pour tout ´el´ement a de (Z/pZ)⇥ , il existe x 2 N tel que g˙ x = a˙ .
˙ x = 15 pour p = 37.
b) R´esoudre les ´equations 2˙ x = 11 pour p = 13, puis 35
Solution : x = 7, puis x = 31 (d’o`u la n´ecessit´e de programmer).
c) Que se passe-t-il si p est tr`es grand ?
M´
ethodes de codage ou cryptage
Exercice 9 Le chi↵rement de C´esar
D´ecrire la m´ethode de codage et donner son ´ecriture math´ematique.
Solution : On choisit un entier a 26 et on consid`ere l’application x 7! x + a modulo 26.
Exercice 10 Un chi↵rement affine Terracher, Tale 2001
On assimile les 26 lettres A, B, · · · , Z de l’alphabet fran¸cais aux nombres 0, 1, · · · 25. On code alors un nombre
x ainsi : le nombre cod´e f (x) est le reste de la division euclidienne de 41x + 37 par 26.
a) Coder le mot ROIS.
b) D´eterminer un entier n tel que 41n ⌘ 1 modulo 26.
Solution : 41 ⇥ 7 = 287 = 260 + 27 ⌘ 1[26].
c) D´ecoder alors le mot IT OT en expliquant soigneusement la m´ethode utilis´ee.
Solution : On obtient F EV E
d) Ecrire la formule g´en´erale d’un chi↵rement affine.
2
Solution : Soit a premier avec 26, donc inversible modulo 26, et b un entier ; f (x) est le reste de la division euclidienne
de ax + b par 26.
Exercice 11 Le chi↵rement de Lester Hill, 1929
La fonction de codage agit sur des couples de nombres de l’ensemble {0, 1, · · · , 25}. Soit
f : {0, 1, · · · , 25} ⇥ {0, 1, · · · , 25} !
(x1 , x2 )
7!
{0, 1, · · · , 25} ⇥ {0, 1, · · · , 25}
(y1 , y2 ) = (5x1 + 11x2 mod 26, 8x1 + 3x2 mod 26)
a) Coder le mot REQUIN en d´etachant les trois blocs de deux lettres.
Solution : RE : (17, 4) 7! (129, 148) ⌘ (25, 18) ! ZS ;
QU : (16, 20) 7! (305, 188) ⌘ (19, 6) ! TG ;
IN : (8, 13) 7! (183, 103) ⌘ (1, 25) ! BZ.
On obtient ZSTGBZ.
b) Montrer que si (y1 , y2 ) = f (x1 , x2 ), alors
(
3y1 + 11y2 = 73x1 mod 26
8y1
5y2 = 73x2 mod 26
c) R´esoudre dans Z ⇥ Z l’´equation 73x + 26y = 1, avec 0 x 25.
Solution : 1 = 5 ⇥ 73 14 ⇥ 26
d) Ecrire la fonction de d´ecodage et d´ecoder YWFSLBNT.
Solution :
(
15y1 + 3y2 = x1 mod 26
14y1 + y2 = x2 mod 26
On obtient SUFKUZ.
e) G´en´eralisation.
Solution : On peut g´en´eraliser `a
(
y1 = ax1 + bx2 mod 26
y2 = a0 x1 + b0 x2 mod 26
Pour que le syst`
eme soit inversible, il faut que le d´
eterminant de la matrice associ´
ee au syst`
eme
inversible
modulo
✓
◆
cb0
ca0
a b
= ab0
a0 b0
a0 b soit
26. Dans ce cas, notons c son inverse modulo 26. La fonction de d´edocage est alors donn´ee par la matrice
cb
.
ca
Exercice 12 code Rivest, Shamir, Adleman (RSA),1977
Soient p et q deux nombres premiers distincts et e un entier.
a) Montrer que xp ⌘ x mod p pour tout entier x, puis que x(p 1)(q 1)+1 ⌘ x mod pq.
b) On consid`ere l’application e : x 2 Z 7! xe 2 Z/pqZ. A quelle condition l’application e est-elle bijective
de Z/pqZ dans Z/pqZ ? D´ecrire l’application r´eciproque.
c) Calculer '(pq), o`
u pour un entier positif n, '(n) repr´esente le nombre d’entiers compris entre 0 et n qui
sont premiers avec n.
d) Pour e entier premier avec '(pq), on appelle application de chi↵rement l’application e introduite en b)
et application de d´echi↵rement la r´eciproque. Quelle est l’application de d´echi↵rement de e ?
Application : Calculer e (4), puis d´eterminer l’application de chi↵rement dans les cas suivants :
– pour n = pq = 77 et e = 7 ; n = pq = 703 et e = 25.
Solution : p = 7 et q = 11, d’o`u 7 (4) = 47 = 256 ⇥ 43 = 25 ⇥ 64 = 60 modulo 77 ; 1 = 5 ⇥ 60 + 7 ⇥ 43 et
7
43 =id sur Z/77Z
p = 19, q = 37 et (p 1)(q 1) = 648, d’o`u 7 (4) = 47 = 256 ⇥ 43 = 1024 ⇥ 16 = 321 ⇥ 16 = 215 modulo
703
25
= 256 ⇥ 42 1 = 1024 ⇥ 42 0 = (321)2 ⇥ 415 = (403)2 ⇥ 45 = 16 ⇥ 321 = 215 modulo 703 ;
25 (4) = 4
1 = 13 ⇥ 648 + 587 ⇥ 25 et 25
587 =id sur Z/703Z
3
e) Expliquer comment utiliser ce code pour la signature de messages.
f ) Notons f l’inverse de e dans Z/'(pq)Z ; montrer que si l’on connaˆıt e, f et n, on peut factoriser n.
Solution : Puisqu’on connait e et f , on peut ´ecrire ef 1 = 2k r. Pour m 2 (Z/nZ)⇥ , on a mef 1 ⌘ 1 mod n. On
cherche `
a connaˆıtre la factorisation de n = pq .
l
l+1
l
Consid´
erons un message m et un entier l, 0 l < k tel que m2 r 6⌘ ±1[pq] et m2 r ⌘ 1[pq]. Alors x˙ = m
˙ 2 r est
une racine carr´
ee de 1 qui n’est pas 1 ni 1. En consid´
erant l’´
equation x˙ 2
1 = (x˙ 1)(x˙ + 1) = 0˙ , on constate que
si x˙
1 est divisible par p, il ne l’est pas par q . On en d´eduit p =pgcd(x 1, n), d’o`u un algorithme pour d´eterminer p,
puis q .
Exercice 13 chi↵rement de Rabin,1979
Soit n = pq o`
u p et q sont des nombres premiers congrus `
a 3 modulo 4 et B un entier compris entre 0 et
n 1.
On consid`ere la fonction
f : Z/nZ !
Z/nZ
˙
x˙
7! x(
˙ x˙ + B).
a) Montrer que 2˙ et 4˙ sont inversibles dans Z/nZ ; en d´eduire une mise sous forme canonique de l’´equation
x˙ 2 + x˙ B˙ = m
˙ 0.
Solution : p et q sont impairs, donc pq aussi. On en d´eduit que 2 et 4 sont inversibles dans Z/nZ. Notons c2 l’inverse
de 2 et c4 l’inverse de 4 ; on a c4 = c22 .
˙ = x˙ 2 + 2c2 B˙ x˙ = (x˙ + c2 B)
˙ 2 c2 B˙ 2 = (x˙ + c2 B)
˙ 2 c4 B˙ 2 . L’´equation x˙ 2 + x˙ B˙ = m
Alors x˙ 2 + x˙ B
˙ 0 est
2
2
2
0
˙
˙
´
equivalente `
a (x˙ + c2 B) = c4 B + m
˙ .
b) Montrer que si m
˙ 0 = f (m),
˙ l’´equation ci-dessus admet 4 solutions dans Z/nZ (cf. exercice 7).
Solution : Si l’on sait que l’´equation f (x) = m
˙ 0 admet une solution m
˙ , alors on sait que c4 B˙ 2 + m
˙ 0 est un carr´e
modulo pq et par l’exercice 7, il existe 4 solutions.
Application : n = 77 et B = 9 ; Alice re¸coit le message m0 = 22 de Bob. D´ecoder le message.
˙
Solution : On v´erifie que 11 ⌘ 3[4] et 7 ⌘ 3[4]. La fonction de codage est x(
˙ x˙ + 9)[77]
et 77 = 11 ⇥ 7.
D´
eterminons d’abord l’inverse de 2 modulo 77 : comme 2 ⇥ 39
77 = 1, l’inverse de 2 est 39. Il s’agit de r´esoudre
˙ 2 = 392 ⇥ 9˙ 2 + 22
˙ ou (x˙ + 43)
˙ 2 = 23
˙.
(x˙ + 39 ⇥ 9)
2
2
Utilisons l’exercice 7. 23 ⌘ 2[7] et 2 = 4 v´
erifie 4 = 16 ⌘ 2[7] ; de mˆ
eme 23 ⌘ 1[11] et 12 = 1 ⌘ 2[11] ; les quatre
˙ 1)
˙ , (4,
˙ 1)
˙ , ( 4,
˙ 1)
˙ et ( 4,
˙ 1)
˙ . Par le th´eor`eme chinois, on trouve les quatre
couples dans Z/7Z ⇥ Z/11Z sont (4,
˙ , 32
˙ , 45
˙ et 10
˙ . Le contexte (on part d’une lettre, donc modulo 26) permet de choisir la
solutions dans Z/77Z qui sont 67
solution m = 10.
c) Montrer que si l’on connaˆıt les quatre solutions de l’´equation ci-dessus, on peut factoriser n.
Solution : Si x et y sont deux solutions telles que x 6⌘ ±y modulo n, alors x y est divisible par p ou par q . On calcule
`
a nouveau pgcd(n, x
y), comme en 12.
Exercice 14 ElGamal, 1985
Alice choisit un nombre premier p, g˙ un g´en´erateur de (Z/pZ)⇥ et un entier a. Elle publie p, g et A = g a mod p.
Bob veut envoyer un message m `
a Alice. Il choisit un entier k et calcule K˙ = g˙ k .
a) Soit f l’application
f : Z/pZ ! (Z/pZ)⇥ ⇥ Z/pZ
˙ mA˙ k ).
m
˙
7!
(K,
Montrer que K˙ est inversible dans Z/pZ et calculer K˙ a mA˙ k .
b) Application : Alice choisit p = 1259, g = 3 et a = 100 ; Bob envoie le message (974, 1155). D´ecoder le
message.
˙ 1 = 857
˙ , 857
˙ 100 = 592
˙ .
Solution : K = 974, f (123) = (974, 1155) ; puis 974
c) Peut-on d´eterminer k choisi par Bob ? Comment peut-on d´eterminer m si l’on intercepte le message ?
Solution : R´esoudre g˙ k = K˙ ; puis calculer A = g a mod p pour casser le code ou calculer C˙ = g˙ ak connaissant
g˙ a = A˙ et g˙ k = K˙ (probl`eme de Diffie-Hellman).
4
© Copyright 2024 ExpyDoc
