Module LI336 - Introduction a la Cryptologie Version enseignant LI336 page 1/6
Examen de Cryptologie
Auteurs
Guenael Renault et Valerie Menissier-Morain
Version du 20 juin 2011
Les seuls documents autorises sont les slides du cours.
Lutilisation dun appareil electronique est proscrit pendant toute la duree de lepreuve.
Le bareme sur 25 est donne a titre indicatif.
Exercice 1 Equations diophantiennes lineaires et chiffrements affines (8 points)
Le but de cet exercice est, etant donnes a, b Z et n N \ {0}, de resoudre
ax = b mod n. (1)
1. (Cas premier 2 points) On suppose dabord que a et n sont premiers entre eux. Montrer alors que lequation
admet une solution et donner un algorithme pour la resoudre. Quelles sont les solutions de lequation 3x + 4 =
6 mod 7 ?
Solution :
Puisque a et b sont premiers entre eux, lidentite de Bezout nous fournit deux entiers u et v tels que au+nv = 1.
Alors en multipliant les deux membres par b on a aub + nbv = b, dou aub = b mod n et x = ub est solution
de lequation 1.
Pour resoudre lequation ax = b mod n, on calcule linverse modulaire u de a modulo n par lalgorithme
dEuclide etendu, puis on le multiplie par b ce qui nous fournit une solution. Les solutions de lequation 1 sont
de la forme ub + kn avec k Z.
Lequation 3x + 4 = 6 mod 7 peut etre reecrite 3x = 2 mod 7. 3 et 7 sont premiers donc a fortiori premiers
entre eux. Linverse modulaire de 3 modulo 7 est 2 puisque 3 (2) + 1 7 = 1. Les solutions de lequation
sont donc de la forme 2 2 + kn, autrement dit 3 + 7k pour k Z.
2. (Cas general 3 points) On ne suppose plus maintenant que a et n sont premiers entre eux et notons d leur pgcd.
Montrer que lequation (1) admet une solution si et seulement si d divise b. Donner un algorithme pour resoudre
lequation (1) dans le cas general. Quelles sont les solutions de lequation 4x = 6 mod 14 ?.
Solution :
Posons a = da0 et n = dn0 avec a0 u + n0 v = 1. Si ax = b mod n alors il existe k Z tel que b = ax + kn =
da0 x + kdn0 = d(a0 x + kn0 ) donc d doit diviser b pour que lequation 1 admette des solutions.
Si d divise b avec b = db0 , alors lequation 1 est equivalente a :
il existe k Z tel que ax b = kn
il existe k Z tel que ax0 b0 = kn0 en divisant par d
a0 x = b0 mod n0
avec a0 et n0 premiers entre eux. On resout cette nouvelle equation selon la methode de la question precedente
ce qui nous fournit lensemble des solutions ub0 + kn0 pour k Z.
Dans lexemple, a = 4, b = 6, n = 14, d = 2, a0 = 2, b0 = 3, n0 = 7, u = 4 et les solutions sont de la forme
5 + kn0 cest-a-dire 5 + 7k pour k Z.
2010-2011(by
c UPMC/Licence dInformatique/LI336 - Introduction a la Cryptologie) 20 juin 2011
Module LI336 - Introduction a la Cryptologie Version enseignant LI336 page 2/6
3. (Probleme dinjectivite 1 point) Soit a un entier non premier avec n, notons d leur pgcd, et b un entier quel-
conque. Considerons lapplication e de Z/nZ dans Z/nZ qui a x fait correspondre ax + b. Montrer que deux
elements x1 et x2 ont meme image par e si et seulement si x1 = x2 mod n0 ou n0 = nd .
Solution :
ax1 + b = ax2 + b mod n a0 (x1 x2 ) = kn0 avec a0 = a/d et n0 = n/d. Comme a0 est premier avec n0
on a donc (x1 x2 ) multiple de n0 .
4. (Application 2 points) Soit (a, b) la cle dun cryptosysteme symetrique affine defini sur Z/nZ. Rappeler la
definition de la fonction de chiffrement associee et lensemble des messages et cles possibles.
Supposons que lon souhaite definir un chiffrement affine avec un entier a non premier a n. Quel ensemble de
messages possibles devrions-nous choisir pour que la fonction de dechiffrement puisse etre definie.
Solution :
Dapres le cours, la fonction de chiffrement est e(x) = ax + b mod n et lensemble des cles possibles est
Z/nZ Z/nZ.
Placons-nous dans le cas ou d = pgcd(a, n) > 1. Lapplication e : Z/nZ Z/nZ qui a x fait correspondre
ax + b nest pas injective dapres la question precedente. Par contre, elle le sera en remplacant lensemble de
depart par Z/n0 Z.
Exercice 2 RSA-3 (8 points)
Dans tout cet exercice, on se donne trois entiers premiers impairs p,q et r differents deux a deux. Soit N lentier egal au
produit pqr. On sinteresse ici a un cryptosysteme identique a RSA.
1. (1 point) Montrer que lon peut definir, de la meme maniere que pour RSA, une fonction de chiffrement et de
dechiffrement ainsi quun cryptosysteme a cle publique en utilisant lentier N . (Vous exhiberez les cles publiques et
privees et definirez lensemble des messages possibles.)
Solution :
Il ny a rien a changer, on choisit un couple dentiers (e, d) tel que ed = 1 mod (N ), on chiffre le message
clair x par y = xe mod N et on dechiffre le message chiffre y par x = y d mod N .
La clef publique est (e, N ), la clef privee (d, p, q, r) et lensemble des messages possibles est Z/N Z car pour
tout message m Z/nZ nous pouvons montrer comme pour RSA que m = DRSA-3 (ERSA-3 (m)).
On a x = y d mod n = (xe )d mod n = xed mod n.
Si x est premier avec N , alors dapres le petit theoreme de Fermat, x(N ) = 1 mod N donc xed = x1+`(N ) =
x mod N pour un certain `.
Si x nest pas premier avec N , alors x est un multiple de p premier avec qr ou un multiple de q premier avec pr
ou un multiple de r premier avec pq. Par exemple pour un multiple de p premier avec qr, la representation de
x Z/nZ dans Z/pZ Z/(qr)Z est (0e = 0, xqr = x mod qr) qui est chiffre par ERSA en (0, xeqr mod qr =
yqr ), lui-meme dechiffre par DRSA en (0d = 0, yqr d = (xe )d mod (qr) = xed mod (qr).
qr qr
Or si ed = 1 mod (N ), il existe k tel que ed = 1 + k(p 1)(q 1)(r 1) donc ed = 1 mod (q 1)(r 1) =
1 mod (qr). xqr = x mod (qr) est premier avec qr (parce que x est un multiple de p premier avec qr) donc
(qr)
dapres le petit theoreme de Fermat, xqr = 1 mod (qr) et xed qr = xqr mod (qr).
d mod (qr) = x ) de Z/pZ Z/(qr)Z redonne evidemment par le CRT x.
Dans Z/nZ, le couple (0, yqr qr
On notera ce cryptosysteme RSA-3 dans toute la suite de lexercice.
2. (2 points) Rappeler quels sont les messages qui sont dangereux lors de lutilisation de RSA. Quels seront ceux qui
seront dangereux pour RSA-3 ? (Vous argumenterez votre reponse.)
2010-2011(by
c UPMC/Licence dInformatique/LI336 - Introduction a la Cryptologie) 20 juin 2011
Module LI336 - Introduction a la Cryptologie Version enseignant LI336 page 3/6
Solution :
Les messages dangereux pour RSA sont ceux qui ne sont pas premiers avec N , puisqualors on trouve un facteur
commun au message et a N donc un des deux facteurs premiers de N , donc lautre et (N ) donc d linverse
modulaire de e modulo (N ), cest-a-dire toute la clef secrete.
Il en va de meme ici : les messages dangereux pour RSA-3 sont ceux qui ne sont pas premiers avec N , puis-
qualors on trouve un facteur commun au message et a N , cest-a-dire soit un facteur, disons p, soit le produit
de deux facteurs pq et on deduit le facteur r = N/(pq), dans tous les cas on deduit un des trois facteurs de N et
le produit des deux autres. En soi un seul message nest pas dangereux, il faudra avoir la chance den trouver un
deuxieme qui nous apporte la connaissance dun autre facteur de N pour connatre alors la factorisation de N ,
dou (N ) et d linverse modulaire de e modulo (N ), cest-a-dire toute la clef secrete.
3. (3 points) Montrer quil est possible dutiliser le CRT lors du dechiffrement dun message. Quel sera le gain en
complexite de calcul (en fonction de la taille de N ) obtenue en utilisant cette technique ? (On pourra supposer ici
que les entiers premiers p, q et r sont de meme taille.)
Solution :
Algorithme
On recoit y et on doit calculer x = y d mod n. On calcule
dp = d mod (p 1), dq = d mod (q 1), dr = d mod (r 1),
puis
xp = y dp mod p, xq = y dq mod q, xr = y dr mod r.
On a x = xp mod p, x = xq mod q et x = xr mod r. On utilise une premiere fois le theoreme chinois pour
deduire x modulo le produit pq. La relation de Bezout pour p et q est up + vq = 1, on a x = xpq mod (pq) avec
xpq = vqxp + upxq . On utilise une seconde fois le theoreme chinois pour deduire x modulo N . La relation de
Bezout pour pq et r est u0 pq + v 0 r = 1, on a finalement x = v 0 rxpq + u0 pqxr mod N .
Complexite
Le cout du calcul de ab mod c est O(log(b)M(log(c))). On remplace :
lexponentiation directe y d mod n de cout O(log(d)M(log(n))) soit O((log(n))3 ) puisque d est de lordre
de n et en supposant quon utilise la multiplication nave M(`) = `2
par :
trois exponentations y dp mod p, y dq mod q et y dr mod r de couts respectifs O(log(dp )M(log(p))),
O(log(dq )M(log(q))) et O(log(dr )M(log(r))) soit au total O((log(p))3 + O(log(q))3 + O(log(r))3 )
et en comptant que log(p) ' log(q) ' log(r) ' log(n)/3 au final
O(1/9(log(n))3 ) (2)
un CRT pour p et q cout en O((log(n))2 ) puis un CRT pour pq et r cout en O((log(n))2 ) aussi, qui sont
negligeables devant le O(1/9(log(n))3 ).
Lutilisation du CRT nous fait donc passer de O((log(n))3 ) a O(1/9(log(n))3 ), soit une division du cout par un
facteur 9.
4. (2 points) Donner le chiffrement de x = 13 et le dechiffrement de y = 11 en utilisant le CRT avec p = 3, q = 5,
r = 7 et e (lexposant de chiffrement) egal a 19.
Solution :
e = 19, N = pqr = 105, (N ) = (p 1)(q 1)(r 1) = 48, d = e1 mod 48 = 5 = 43 car
5 19 = 95 = 2 48 1.
Le chiffre de x = 13 est xe mod N = 1319 mod 105. On a
132 = 169 = 105 + 64 = 64 mod 105
2010-2011(by
c UPMC/Licence dInformatique/LI336 - Introduction a la Cryptologie) 20 juin 2011
Module LI336 - Introduction a la Cryptologie Version enseignant LI336 page 4/6
et 642 = 4096 = 39 105 + 1 = 1 mod 105
donc
xe mod N = 1319 mod 105 = 649 13 = 14 64 13 = 64 13 = 832 = 8 105 8 = 8 = 97 mod 105.
Le dechiffre de y = 11 est y d mod N = 1143 mod 105. On a 112 = 121 = 105 + 16 = 16 mod 105,
16 16 = 256 = 2 105 + 46 = 46 mod 105,
462 = 2110 = 20 105 + 16 = 16 mod 105
et 16 46 = 736 = 7 105 + 1 = 1 mod 105,
donc
y d mod N = 1143 mod 105 = 1621 11 = 4610 1611 = 165 1611 = 166 11 = 463 11 = 164611 = 111 = 11.
Exercice 3 Courbe Elliptique (6 points)
On se propose detudier le groupe G issu de la courbe
E: y 2 = x3 + x + 3
definie sur F7 .
1. Verifier que E definit bien une courbe elliptique sur F7 .
Solution :
On calcule le discriminant = 16(4a3 + 27b2 ) mod 7 = 5 (4 32 ) = 45 = 4 6= 0 mod 7 donc E definit
bien une courbe elliptique sur F7 .
2. Donner (sous la forme dun tableau) lensemble des points (x, y) F7 F7 de cette courbe. Montrer que le cardinal
du groupe G issu de cette courbe est de 6.
Solution :
On calcule tout dabord les carres pour y F7 :
y 0 1 2 3 4 5 6
y2 0 1 4 2 2 4 1
puis on calcule les x3 + x + 3 pour x F7 et lorsque la valeur de x3 + x + 3 correspond a y 2 dans la table
ci-dessus alors (x, y) est un point de la courbe elliptique :
x x3 + x + 3 Points
0 3
1 5
2 6
3 5
4 1 (4, 1), (4, 6)
5 0 (5, 0)
6 1 (6, 1), (6, 6)
On a donc 5 points rationnels plus le point a linfini soit 6 points sur la courbe et le cardinal de G est 6.
3. Montrer que le point (4, 1) est dordre 6 dans G. Exhiber un point dordre 2 dans G.
2010-2011(by
c UPMC/Licence dInformatique/LI336 - Introduction a la Cryptologie) 20 juin 2011
Module LI336 - Introduction a la Cryptologie Version enseignant LI336 page 5/6
Solution :
Soit P1 = (4, 1). On sait que lordre de P1 divise le cardinal de G donc est un diviseur de 6, ce nest pas 1, cest
donc 2, 3 ou 6. On calcule donc P2 = [2]P1 et P3 = [3]P1 et si aucun de ces points nest O alors P1 est dordre
6. On calcule :
3x2 +a
P2 = [2]P1 : = 2y1 1 = 0, dou x2 = 2 2x1 = 0 2 4 = 6 mod 7 et y2 = (x1 x2 ) y1 = 1 =
6 mod 7 donc P2 = [2]P1 = (6, 6).
P3 = [3]P1 = P1 + P2 : = xy22 y 61 5 2
x1 = 64 = 2 = 5 4 = 6 mod 7, dou x3 = x1 x2 = 36 4 6 =
1
5 mod 7 et y3 = (x1 x3 ) y1 = 6 (4 5) 1 = 0 mod 7 donc P3 = [3]P1 = (5, 0).
On en deduit que P1 est dordre 6 et par consequent P3 est dordre 2.
4. Terminer de remplir le tableau suivant representant la table daddition de G.
+ O (4, 1)
O O (4, 1) (6, 6)
(4, 1) (4, 1) (6, 6) O
(6, 6) (6, 6) O
O
O
O
Solution :
Pour cela on complete notre enumeration precedente :
3x2 +a 2
P4 = [4]P1 = P2 + P2 : = 2y2 2 = 3626+1 = 45 = 4 3 = 5 mod 7, dou x4 = 2 2x2 = 25 2 6 =
6 mod 7 et y4 = (x2 x4 ) y2 = 5 (6 6) 6 = 1 donc P4 = [4]P1 = (6, 1).
P5 = [5]P1 = P1 + P4 : = xy44 y 11 2
x1 = 64 = 0, dou x5 = x1 x4 = 0 4 6 = 4 mod 7 et
1
y5 = (x1 x5 ) y1 = 1 = 6 mod 7 donc P5 = [5]P1 = (4, 6).
On obtient donc :
O O (4, 1) (6, 6) (5, 0) (6, 1) (4, 6)
(4, 1) (4, 1) (6, 6) (5, 0) (6, 1) (4, 6) O
(6, 6) (6, 6) (5, 0) (6, 1) (4, 6) O (4, 1)
(5, 0) (5, 0) (6, 1) (4, 6) O (4, 1) (6, 6)
(6, 1) (6, 1) (4, 6) O (4, 1) (6, 6) (5, 0)
(4, 6) (4, 6) O (4, 1) (6, 6) (5, 0) (6, 1)
5. Quelles sont les formes possibles pour le groupe G ? Montrer quici G est cyclique. (Vous argumenterez toutes vos
reponses.)
Solution :
Dapres le theoreme de structure, G ' Z/d1 Z Z/d2 Z avec d1 |d2 et d1 |q 1. Ic on travaille sur F7 donc d1 |d2
et d1 |6. Le cardinal de G est egal a 6 dapres la question 2. Compte tenu que la factorisation de 6 ne contient
pas de carre, la seule possibilite est que d1 = 1 et d2 = 6, cest-a-dire que G est isomorphe a Z/6Z et donc G
est cyclique. On aurait pu repondre plus rapidement en disant que (4, 1) est dordre 6 (le cardinal de G) et donc
G = h(4, 1)i est un groupe cyclique par definition.
Remarque importante : Les reponses des questions 3, 4 et 5 peuvent etre donnees sans aucun calcul. Par
exemple, pour montrer que (4, 1) est dordre 6, on peut proceder de la sorte. Il est clair dapres le tableau
de la question 4 que [2](4, 1) = (6, 6) et comme (6, 6) et (4, 1) ne partagent pas la meme abscisse, il est
impossible, dapres la definition geometrique de laddition des points dune courbe elliptique, que [3](4, 1) =
[2](4, 1) + (4, 1) = (6, 6) + (4, 1) soit egal a lelement neutre. Ainsi (4, 1) est ni dordre 2 ni dordre 3 dans
2010-2011(by
c UPMC/Licence dInformatique/LI336 - Introduction a la Cryptologie) 20 juin 2011
Module LI336 - Introduction a la Cryptologie Version enseignant LI336 page 6/6
G qui est dordre 6, ce point est donc dordre 6 et generateur de G. Le tableau de la question 4 peut aussi etre
deduit tres facilement sans aucun calcul.
Des reponses se basant sur le calcul sont toutes aussi justes et souvent plus faciles a appliquer directement. Elles
ont donc ete le plus souvent utilisees par les etudiants ayant reussi ces questions.
Exercice 4 Questions de Cours (3 points)
1. Lanneau Z/4Z est-il un corps ? Sinon, comment peut-on definir un corps a 4 elements ? (Argumenter vos reponses.)
Solution :
Z/nZ est un corps si et seulement si n est premier. 4 nest pas premier donc Z/4Z nest pas un corps. On peut
aussi dire directement que 2 est un diviseur de 0 dans Z/4Z donc Z/4Z nest pas un corps.
On definit un corps a 4 elements en quotientant F2 le corps a 2 elements par un polynome irreductible de degre
2 sur F2 , tel que X 2 + X + 1.
2. Pourquoi est-il plus judicieux dutiliser les courbes elliptiques plutot que les corps finis dans le cadre dun crypto-
systeme reposant sur le DLP ?
Solution :
Pas dattaque connue de complexite sous-exponentielle
Larithmetique peut etre rendue tres rapide
Les clefs sont plus petites a securite equivalente : la ou il faut 1024 bits pour RSA, il suffit de 160 bits pour
les courbes elliptiques.
3. Chiffrer le message ATTAQUEDEMAIN a laide de la cle KARL en utilisant un chiffrement de Vigenere.
Solution :
ATTAQUEDEMAIN
+ KARLKARLKARLK
---------------
KTKLAUVOOMRTX
2010-2011(by
c UPMC/Licence dInformatique/LI336 - Introduction a la Cryptologie) 20 juin 2011
