Fichier PDF

Partagez, hébergez et archivez facilement vos documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



rapport rsa .pdf



Nom original: rapport_rsa.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.14, et a été envoyé sur fichier-pdf.fr le 02/05/2016 à 20:32, depuis l'adresse IP 82.238.x.x. La présente page de téléchargement du fichier a été vue 393 fois.
Taille du document: 281 Ko (21 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Attaques sur RSA
Christophe Boubel & Youenn Laborde & J´er´emie Nekam
5 juin 2015

1

Table des mati`
eres
1 Introduction
1.1 Cryptographie asym´etrique . . . . . .
1.2 Pr´esentation de RSA . . . . . . . . . .
1.3 Exemple de chiffrement/d´echiffrement
1.4 Impl´ementation . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

3
3
3
4
5

2 Attaques ´
el´
ementaires
2.1 Attaque par module commun . . . . . . . .
2.2 Attaque de Hastad . . . . . . . . . . . . . .
2.2.1 Th´eor`eme des restes chinois . . . . .
2.2.2 L’attaque de Hastad . . . . . . . . .
2.3 Factorisation de n depuis son indice d’Euler
2.4 Factorisation de n depuis e et d . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

6
6
6
6
6
7
7

3 Factorisation d’entier
3.1 M´ethode P-1 de Pollard . . . . . .
3.1.1 Principe . . . . . . . . . . .
3.1.2 Impl´ementation . . . . . . .
3.2 M´ethode de Rho-Pollard . . . . . .
3.2.1 Paradoxe des anniversaires
3.2.2 Id´ee de Pollard . . . . . . .
3.2.3 Detection de cycle de Floyd
3.2.4 Impl´ementation . . . . . . .
3.3 M´ethode de Fermat . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

9
9
9
9
10
10
10
10
10
11

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

4 Miller-Rabin
12
4.1 Test de primalit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 Factorisation de module RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5 Attaque de Wiener
´
5.1 Euclide Etendu
. . .
5.2 Fractions Continues
5.3 Id´ee de Wiener . . .
5.4 Principe de l’attaque
5.5 Impl´ementation . . .
5.6 Exemple . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

13
13
13
15
16
16
17

6 Attaque Temporelle
6.1 Un cas pour RSA . . . . . . . . .
6.1.1 Exponentiation modulaire
6.1.2 Un exemple d’analyse . .
6.2 S´ecurit´e . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

18
18
18
18
19

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

7 Conclusion

20

2

1
1.1

Introduction
Cryptographie asym´
etrique

La cryptographie `
a cl´e publique ou cryptographie asym´etrique est une m´ethode de chiffrement bas´ee
sur l’´echange d’une cl´e publique (diffus´ee) et d’une cl´e priv´ee (secr`ete), l’une permettant le chiffrement,
l’autre le d´echiffrement. Elle repose sur l’existence des fonctions `a sens unique. C’est `a dire la donn´ee
d’une fonction f de chiffrement qui soit rapide (en temps raisonnable) `a calculer mais telle que son
inverse f −1 soit difficile `
a trouver. Il faut donc que pour une image donn´ee par f , il soit difficile de lui
trouver un ant´ec´edent.
L’utilit´e de la cryptographie asym´etrique est qu’il n’y a pas multiplication des cl´es ni ´echange de cl´es.
C’est `
a dire que si Bob veut communiquer avec Alice, il r´ecup`ere la cl´e publique d’Alice pour chiffrer le
message que seule Alice pourra d´echiffrer avec sa cl´e priv´ee. Et inversement si Alice veut communiquer
avec Bob.
Par exemple, l’un des algorithmes de cryptographie asym´etrique les plus utilis´es de nos jours est l’algorithme RSA, du nom de ses inventeurs, Ronald Rivest, Adi Shamir et L´eonard (Len) Adleman.
C’est un algorithme permettant le chiffrement de donn´ees mais aussi la signature(identification de la
personne qui envoie le message).
Il repose principalement sur la difficult´e de factorisation de grands entiers produits de nombres premiers ainsi que sur l’exponentation rapide (associ´ee au logarithme discret). C’est `a dire que nous ne
sommes pas capables (encore) de factoriser un nombre en produit de nombres premiers en un temps
raisonnable en supposant que ce nombre soit assez grand.
Voyons maintenant une description math´ematique de RSA.

1.2

Pr´
esentation de RSA

RSA ´etant asym´etrique, il utilise donc deux cl´es, l’une publique, l’autre priv´ee, voyons comment elles
sont calcul´ees.
On choisit deux nombres premiers, de pr´ef´erence de grande taille et de mani`ere al´eatoire. Pour en
trouver, on peut prendre une suite al´eatoire de bits et utiliser un test de primalit´e (d´eterministe ou
non). Appelons-les p et q. On calcule leur produit :
n=p∗q
On appelle n le module de chiffrement. On calcule ensuite l’indicatrice d’Euler de n, not´ee ϕ(n), qui
correspond au cardinal des inversibles de l’anneau Z/nZ, avec
ϕ(n) = (p − 1)(q − 1)
car p et q sont premiers.
On choisit ´egalement un entier e tel que e et ϕ(n) soient premiers entre eux, avec 1 < e < ϕ(n). On
appelle e l’exposant de chiffrement.
Enfin, on calcule d qui est l’inverse de e (mod ϕ(n)) car e est premier avec ϕ(n) donc il existe une
relation de B´ezout telle qu’il existe d et k avec ed + kϕ(n) = 1, donc ed ≡ 1 (mod ϕ(n)).
Finalement, on a donc que (n, e) est la cl´e publique de chiffrement et (n, d) la cl´e priv´ee de d´echiffrement.
Supposons que l’on ait un entier m, de taille strictement inf´erieure `a n, qui correspond `a un message,
le chiffrement s’effectue ainsi :

3

c = me

(mod n)

o`
u c est le message chiffr´e.
Et donc, le d´echiffrement est tel que si on a un code c chiffr´e, le message initial est :
m = cd
d

e d

(mod n)

ed

car m = (m ) = m et puisqu’on a ed ≡ 1 (mod ϕ(n)), on peut ´ecrire ed = 1 + k(p − 1)(q − 1), ce
qui nous donne d’apr`es le Petit Th´eor`eme de Fermat que m1+k(p−1)(q−1) ≡ m (mod n).

1.3

Exemple de chiffrement/d´
echiffrement

Voyons un exemple pratique avec des nombres premiers pas trop grands.
1. On choisit deux nombres premiers, par exemple : p = 61 et q = 53.
2. On calcule leur produit : n = pq = 61 ∗ 53 = 3233.
3. On calcule l’indicatrice d’Euler de n qui vaut : ϕ(n) = (p − 1)(q − 1) = 60 ∗ 52 = 3120.
4. On choisit un entier e tel que 1 < e < ϕ(n) et premier avec ϕ(n). Par exemple e = 17.
5. On calcule d, l’inverse de e (mod ϕ(n)). Ici, d = 2753. On a bien que e ∗ d (mod ϕ(n)) = 1.
La cl´e publique est donc (3233,17) et la cl´e priv´ee est (3233,2753).
Maintenant, supposons que Bob veuille communiquer avec Alice. Il r´ecup`ere donc la cl´e publique
d’Alice qui est (3233,17). Mettons qu’il veuille envoyer le message : ”Bonjour”. La premi`ere ´etape
consiste `
a transformer le message en nombre, ce que l’on peut faire en associant chaque lettre `a sa
correspondance en ASCII puis `
a effectuer le chiffrement. Ce qui nous donne :
B → 66 → 6617 (mod 3233) = 524
o → 111 → 11117 (mod 3233) = 2185
n → 110 → 11017 (mod 3233) = 2235
j → 106 → 10617 (mod 3233) = 1696
o → 111 → 11117 (mod 3233) = 2185
u → 117 → 11717 (mod 3233) = 2160
r → 114 → 11417 (mod 3233) = 2412
Le message envoy´e sera donc : 524 2185 2235 1696 2185 2160 2412. A partir de ce moment, seule Alice
est en mesure de d´echiffrer le message a` l’aide de sa cl´e priv´ee. Mˆeme Bob ne peut le d´echiffrer, mˆeme
si en th´eorie, il connaˆıt le message.
Le d´echiffrement est similaire au chiffrement, le seul changement est dans l’´el´evation a` la puissance
puisque pour d´echiffrer, on utilisera d=2753.
Supposons que l’on ait re¸cu le message suivant : 524 2578 2412 1632 2578 2185. On d´echiffre de la
mani`ere suivante :
524 → 5242753 (mod 3233) = 66 → B
2412 → 24122753 (mod 3233) = 114 → r
1632 → 16322753 (mod 3233) = 97 → a
2578 → 25782753 (mod 3233) = 118 → v
2185 → 21852753 (mod 3233) = 111 → o
On a d´echiffr´e en : ”Bravo”.

4

1.4

Impl´
ementation

L’algorithme suivant donne une des possibilit´es pour construire un syst`eme RSA.
Algorithme 1 G´en´eration des cl´es
Sortie: (N, E) la cl´e publique
Sortie: (N, D) la cl´e priv´ee
P ← Nombre premier al´eatoire
Q ← Nombre premier al´eatoire
N ←P ×Q
ϕ(N ) ← (P − 1) × (Q − 1)
E←3
Tant que pgcd(ϕ(N ), E) > 1 Faire
E ←E+2
Fin Tant que
D ← Inverse modulaire de E (mod ϕ(N ))
Renvoyer (N, E) et (N, D)
On remarque que dans l’algorithme on tire des nombres premiers al´eatoires pour les valeurs de p et q.
Dans plusieurs langages de programmation, il existe d´ej`a des fonctions permettant un tirage al´eatoire
d’entier premier. Dans le cas contraire, l’id´ee est de tirer au hasard une valeur enti`ere et de lui faire
passer un test de primalit´e, comme le test probabiliste de Miller-Rabin (voir section 4).

5

2
2.1

Attaques ´
el´
ementaires
Attaque par module commun

Proposition Soit n un module RSA et soit deux cl´es publiques diff´erentes (n, e1 ) et (n, e2 ) avec e1
et e2 premier entre eux. Si on connaˆıt C1 et C2 des chiffr´es depuis un message M avec les exposants
e1 et e2 alors on peut retrouver le message M d’origine.
En effet soit C1 et C2 deux chiffr´es :
C1 =M e1
C2 =M e2

(mod n)
(mod n)

Si un attaquant connaˆıt C1 , C2 mais aussi les deux cl´es publiques (n, e1 ) et (n, e2 ) alors il peut trouver
les coefficients de B´ezout u et v tels que e1 u + e2 v = 1. Il peut donc calculer :
C1u .C2v = M ue1 +ve2

(mod n) = M

Il ne faut donc jamais utiliser le mˆeme module n pour l’envoi d’un mˆeme message `a plusieurs personnes.

2.2

Attaque de Hastad

Johan Hastad, n´e en 1960, est un informaticien th´eorique reconnu pour ses recherches sur la complexit´e
algorithmique et pour avoir obtenu deux fois le prix G¨odel, prix qui honore des travaux d’informatique
th´eorique. En 1985, il propose l’une des premi`eres attaques du chiffrement RSA. Cette attaque est
similaire a` celle d´ecrite ci-dessus, mais cette fois-ci on suppose qu’un attaquant arrive `a intercepter
plusieurs messages chiffr´es avec le mˆeme exposant, suppos´e suffisamment petit. En effet, en connaissant
les chiffr´es, il est possible de retrouver le message d’origine en utilisant le th´eor`eme des restes chinois.
2.2.1

Th´
eor`
eme des restes chinois

Th´
eor`
eme
tel que :

Si m1 , . . . , mn sont des entiers deux

x = x1




x = x2



.
.




.



x = xn

Alors en notant
Mi =

Y
j6=i

mj =

`a deux premiers entre eux, et qu’il existe x1 , . . . , xn
(mod m1 )
(mod m2 )

(mod mn )

M
,
mi

Ni = Mi−1

(mod mi )

Il existe une unique solution modulo M = m1 . . . mn donn´ee par :
x = x1 .M1 .N1 + · · · + xn .Mn .Nn
2.2.2

L’attaque de Hastad

Principe Imaginons qu’Alice envoie `a 3 destinataires diff´erents ayant respectivement comme cl´e
publique (n1 , e), (n2 , e) et (n3 , e). Supposons que les ni soient premiers entre eux. On se retrouve donc
avec le syst`eme d’´equation suivant :
 e
 m = c1 (mod n1 )
me = c2 (mod n2 )
 e
m = c3 (mod n3 )
6

Si un attaquant arrive `
a r´ecup´erer les trois chiffr´es c1 , c2 et c3 alors vu que n1 , n2 , n3 sont publiques,
il peut alors appliquer le th´eor`eme des restes chinois et trouve des solutions x v´erifiant :
x = c1 .c2 .c3 = m3

(mod n1 .n2 .n3 )

Si l’exposant e est suffisamment petit alors on a x < n1 .n2 .n3 et on peut donc retrouver le message
clair d’origine avec un calcul de racine cubique de x.

2.3

Factorisation de n depuis son indice d’Euler

Formule quadratique sur un polynˆ
ome du second degr´
e Soit α1 et α2 les racines du polynˆome
` coefficient dans Z.
a
P (X) = aX 2 + bX + c
Alors on a :
α1 α2 =
Th´
eor`
eme
Preuve

c
a

Soit n un module RSA. Si on connaˆıt ϕ(n) alors on peut factoriser n.

Supposons ϕ(n) connus, on a alors le syst`eme d’´equations :

pq =
n
p + q=n − ϕ(n) + 1

Ce qui nous donne l’´equation du second degr´e :
p2 − (n − ϕ(n) + 1)p + n = 0
En calculant le discriminant :
∆ = (n − ϕ(n) + 1)2 − 4n
On trouve les racines qui sont les facteurs de n :

n − ϕ(n) + 1 + ∆
p=
2

2.4

n − ϕ(n) + 1 −
q=
2





Factorisation de n depuis e et d

On consid`ere que l’on connaˆıt dans un syst`eme RSA les valeurs (n, e, d). Par construction, on sait
que ed = 1 (mod ϕ(n)). Ce qui revient `a dire que ϕ(n) divise ed − 1. Il existe donc un k tel que
ed − 1 = kϕ(n).
De plus, on sait que φ(n) = (p − 1)(q − 1) = pq − (p + q) + 1 = n − (p + q) + 1 (avec p et q les deux
entiers premiers divisant n). On a donc au final :
ed − 1 = k(n − (p + q) + 1)

k∈Z

On suppose que p et q sont strictement sup´erieurs `a 3 (impairs donc), ainsi p et q sont inf´erieurs `a
d’o`
u n > n − (p + q) + 1 > n2 . Ainsi :
k
D’apr`es la premi`ere ´egalit´e :

n
6 k(n − (p + q) + 1)
2
n
6 ed − 1
2
2ed − 2
2ed
k6
6
n
n
k

7

n
4,

Comme d < n alors :
k 6 2e
Comme e est petit, on peut se permettre d’´enum´erer toutes les valeurs possibles entre 1 et 2e pour
, alors les deux entiers p et q facteurs de n sont solutions de
trouver le bon k. Dans ce cas, si t = ed−1
k
l’´equation du second degr´e :
x2 − (n − t + 1)x + n = 0

8

3

Factorisation d’entier

Un syst`eme RSA s´ecuris´e repose sur le fait que la cl´e priv´ee d soit tenue secr`ete, mais aussi que
les facteurs p et q de n soit inconnus. En effet, si l’on connaˆıt ces deux facteurs, on peut facilement
recalculer l’indicatrice d’Euler de n en calculant (p−1)×(q−1), ce qui nous permet ensuite de retrouver
la cl´e priv´ee d puisque son inverse e est publique. Une des attaques possibles pour casser un syst`eme
RSA est donc de factoriser l’entier n.

3.1


ethode P-1 de Pollard

N´e en 1941, John Pollard est un math´ematicien anglais qui a invent´e des algorithmes permettant la
factorisation de grands entiers ainsi que le calcul des logarithmes discrets. Voici deux de ces m´ethodes
permettant la factorisation du module RSA n.
3.1.1

Principe

Proposition Soit n ∈ N∗ non premier et p premier un facteur de n. Alors ∀a ∈ (Z/nZ)∗ et ∀m
multiple de p − 1 :
ap−1 = 1 (mod p),
am = 1 (mod p)
Principe D’apr`es les ´equations ci-dessus, si on trouve un m tel que pour un a ∈ (Z/nZ)∗ fix´e :
am = 1 (mod p) alors on a p | pgcd(am − 1, n) o`
u p est donc un facteur de n.

efinition Soit a, B ∈ N∗ . On dit que a est B-friable si tous les facteurs premiers de a sont inf´erieurs
ou ´egaux a` B.
PropositionQ Soit n ∈ N∗ non premier et p premier un facteur de n. Supposons p − 1 B-friable.
Posons M = q6B q fq (q premier) o`
u fq = blogq nc, alors p | pgcd(am − 1, n).
3.1.2

Impl´
ementation

Concr`etement, on va calculer de proche en proche les aM (B) pour B croissant jusqu’`a pouvoir obtenir
un des facteur de n, le second pouvant se d´eduire assez facilement par une simple division.
Algorithme 2 M´ethode P-1 de Pollard
Entr´
ee: n un entier
Sortie: g un facteur de n
a ← Un ´el´ement de (Z/nZ)∗
B ← 2, M ← 1, g ← 1
Tant que g = 1 Faire
M ← M × B fq (B) (mod n)
g = pgcd(aM − 1, n)
B ←B+1
Fin Tant que
Renvoyer g

Remarque Si lors d’une it´eration, on trouve un pgcd ´egale `a n, alors il pourrait suffire de seulement
changer d’´el´ement a, sans changer la valeur de M pour pouvoir trouver un facteur de n.
Complexit´
e Si n a un facteur
premier p tel que p − 1 est B-friable alors cette m´ethode fournit ce
B
facteur en O log B .log n.M (n) op´erations, o`
u M (n) est le coˆ
ut d’une multiplication dans Z/nZ.
9

3.2
3.2.1


ethode de Rho-Pollard
Paradoxe des anniversaires

Proposition
Soit x1 , x2 , ..., xk tir´es selon une loi uniforme dans un ensemble de cardinal p. Alors


8p log 2 +1+1
pour k >
(' 1.18 p), la probabilit´e de x1 , ..., xk est inf´erieure `a 0, 5.
2
Preuve La probabilit´e P que x1 , ..., xk soient distincts est ´egale `a
Qk−1
i
i=0 (1 − p ). On a alors :
k−1
Y
k(k−1)
i
P 6
e− p = e− 2p

p(p−1)...(p−k+1)
,
pk

c’est `a dire

i=0

On cherche quand est-ce que cette probabilit´e atteint au moins 0, 5 ce qui reviens `a r´esoudre :
e−

k(k−1)
2p

6

1
2

Ce qui nous donne (avec une constante variant en fonction de la probabilit´e choisie, ici 0, 5) :

k'c p
3.2.2

Id´
ee de Pollard

Principe Soit n ∈ N∗ et p le plus petit facteur premier de n. On tire des xi al´eatoirement dans

(Z/nZ), alors avec un nombre d’essai en O( p) on a plus d’une chance sur deux de trouver xi = xj
(mod p) tel que xi 6= xj (mod n). Ce qui nous donne donc p = pgcd(xi − xj , n) 6= n.
Cependant calculer un pgcd pour chaque couple (i,j) peut ˆetre tr`es couteux.
Suite pseudo-al´
eatoire Pour ´eviter de faire des tirages al´eatoires, on va choisir les xi via une suite
r´ecurrente :
f : x 7−→ x2 + 1,
u0 ∈ (Z/nZ) un+1 = f (un )
Cette suite se comporte un peu comme une suite al´eatoire, au moins en ce qui concerne le ”paradoxe
des anniversaires”.
3.2.3

Detection de cycle de Floyd

Proposition Soit f ∈ Z[X] , u0 ∈ (Z/nZ) et uk = f k (u0 ). Alors s’il existe i < j tel que xi = xj
(mod p) alors il existe k < 2j tel que xk = x2k (mod p).
Preuve Soit j = i + k avec k > i, tel que ui = uj . Donc ∀k > i on a uk = uk+(j−i) . En prenant
k = j − i on a donc uk = u2k .
3.2.4

Impl´
ementation

On peut donc factoriser N d’un syst`eme RSA en trouvant ces facteurs premiers avec l’algorithme
suivant :

10

Algorithme 3 M´ethode de Rho Pollard
Entr´
ee: N un entier
Sortie: P un facteur de N
X←1
Y ←X
D←1
Tant que D = 1 Faire
X ← X2 + 1
Y ← (Y 2 + 1)2 + 1
D ← pgcd(X − Y, N )
Fin Tant que
Si D = N Alors
Changer l’initialisation de X et recommencer
Fin Si
Renvoyer D

3.3


ethode de Fermat

Principe Pour factoriser n, la m´ethode de Fermat consiste `a trouver a et b tel que n = a2 − b2 . On
aurait donc bien une d´ecomposition en facteurs :
n = a2 − b2 = (a − b)(a + b)
Puisque n, dans un syst`eme RSA, est le produit de deux facteurs
premiers, ceux-ci sont donc les (a − b)

et (a + b). On va donc essayer diff´erentes valeur de a > d ne en esp´erant que la valeur de a2 − n soit
un carr´e, not´e b2 , pour ensuite trouver la factorisation de n.
L’algorithme suivant donne une version de cette m´ethode.
Algorithme 4 M´ethode de Fermat
Entr´
ee: n un entier
Sortie: √
p et q les facteurs de n
a ← d ne
b←1
Tant que (a2 − n) n’est pas un carr´e Faire
a←a+1
Fin √
Tant que
b ← a2 − n
Renvoyer p = (a − b), q = (a + b)

11

4
4.1

Miller-Rabin
Test de primalit´
e

´
Miller Soit n un nombre premier impair. Ecrivons
n − 1 = 2r m tel que 2 ne divise pas m. Alors

∀a ∈ (Z/nZ) on a :

soit
am
= 1 (mod n)
i
soit ∃i ∈ [0, r − 1] a2 m = −1 (mod n)
Rabin Si n > 9 impair et non premier alors :
#{a ∈ (Z/nZ)∗ tq a v´erifie le th´eor`eme de Miller } 6

ϕ(n)
4 .

Test de primalit´
e de Miller-Rabin L’algorithme est un test probabiliste de primalit´e. Il utilise
les th´eor`emes de Miller et Rabin.
Algorithme 5 Test de primalit´e
Entr´
ee: un entier n, un nombre k de tentative du test
´ ou N PROBABLEMENT PREMIER
Sortie: N COMPOSE
r
n − 1 = 2 m avec 2 ne divisant pas m
a ← ´el´ement al´eatoire de (Z/nZ)∗
Si k = 0 Alors
Renvoyer N PROBABLEMENT PREMIER
Fin Si
i
Si am 6= 1 et a2 m 6= −1 (mod n) ∀i ∈ [0, r − 1] Alors
´
Renvoyer N COMPOSE
Sinon
Recommencez `
a l’´etape tirage al´eatoire de a
k ←k−1
Fin Si

4.2

Factorisation de module RSA

Th´
eor`
eme Si, dans un syst`eme RSA, on connait la valeur de la cl´e priv´ee d, alors avec la donn´ee
publique e, il est possible de factoriser n.
Preuve On suppose disposer dans un syst`eme RSA des trois valeurs (n, e, d).
On sait que ϕ(n) divise ed − 1. Il existe k ∈ Z tel que ed − 1 = kϕ(n). Soit s = max{i ∈ N tel que 2i
divise ed − 1}. On a alors un entier t tel que ed − 1 = t2s , c’est `a dire t = ed−1
2s .
Soit a ∈ Z premier avec n, on a alors :
s

akϕ(n) = 1 ⇐⇒ (at )2 = 1

(mod n)

L’ordre de (at ) dans Z/nZ est donc dans l’ensemble {2j | 0 6 j 6 s}, soit :
(
i−1
6= ±1 (mod n)
(at )2
∃i ∈ [0, s]
t 2i
(a )
= 1 (mod n)
i−1

Posons x = (at )2

, nous avons donc le syst`eme de propri´et´es
 2
 x − 1 = (x − 1)(x + 1) = 0
(x + 1)
6= 0

(x − 1)
6= 0
12

suivants :
(mod n)
(mod n)
(mod n)

i−1

Ainsi pgcd(x − 1, n) = pgcd(a2
division.

t

, n) est un facteur de n et on obtient l’autre facteur directement par

Algorithme 6 Variante de Miller-Rabin pour factoriser N
Entr´
ee: (N, E, D)
Sortie: P et Q facteurs de N ou ERREUR
Soit s et t impair tel que ED − 1 = t2s
a ← al´eatoire ∈ [0, N − 1]
α ← at
Si α = 1 ou α = N − 1 Alors
Renvoyer ERREUR
Fin Si
Pour i ∈ [1, s] Faire
temp ← α2 (mod N )
Si temp = 1 (mod N ) Alors
Renvoyer P = pgcd(α − 1, N ) et Q = N/P
Fin Si
α ← temp
Fin Pour
Renvoyer ERREUR

5
5.1

Attaque de Wiener
´
Euclide Etendu

Dans n’importe quel anneau euclidien A, avec les donn´ees a, b ∈ A on veut calculer d = pgcd(a, b) ainsi
que s, t ∈ A tel que as + bt = d.
Algorithme 7 Euclide ´etendu
Entr´
ee: a, b deux ´el´ements d’un anneau Euclidien
Sortie: d, s, t tel que as + bt = d
S0 ← 1,
T0 ← 0,
R0 ← a
S1 ← 0,
T1 ← 1,
R1 ← b
i←1
Tant que ri > 0 Faire
Qi ← Ri−1 /Ri
Ri+1 ← Ri−1 − Qi Ri
Si+1 ← Si−1 − Qi Si
Ti+1 ← Ti−1 − Qi Ti
i←i+1
Fin Tant que
Renvoyer Ri−1 , Si−1 , Ti−1

5.2

Fractions Continues


efinition

Une fraction continue est une fraction it´er´ee de la forme
1
a0 +
1
a1 +
..
. + a 1+ 1
n−1

13

an

Les quotients ai , ∀i ∈ {1, ..., n}, sont appel´es les quotients partiels de la fraction continue.


efinition

Notation Par souci de lisibilit´e, on notera une fraction continue sous forme de suite [a0 , a1 , a2 , ..., an ]
ou ai , ∀i ∈ {1, ..., n}, est un quotient partiel de la fraction continue.
Exemple

Soit [1, 2, 1, 2], ´evaluons les fractions continues.
1=1

On a donc

11
8

1+

1
3
=
2
2

1+

1
2+

1
1

=

4
3

1+

1
2+

1
1+ 12

=

11
8

= [1, 2, 1, 2].

Th´
eor`
eme Pour p et q des entiers positifs, l’algorithme d’Euclide ´etendu calcule les quotients partiels
de la fraction continue de pq = [a0 , a1 , ..., an ].
Dans l’algorithme pr´esent´e au dessus la liste des Qi correspond `a la suite des quotients partiels.
Exemple
8:

Soit la fraction x =

11
8 ,

on applique l’algorithme d’Euclide ´etendu avec les valeurs 11 et
11 = 1 × 8 + 3

Le quotient de 11/8 vaut 1 donc x = [1, ...].
8=2×3+2
Le quotient de 8/3 vaut 2 donc x = [1, 2, ...].
3=1×2+1
Le quotient de 3/2 vaut 1 donc x = [1, 2, 1, ...].
2=2×1+0
Le quotient de 2/1 vaut 1 et le reste 0 donc x = [1, 2, 1, 2].

efinition (les r´
eduites) Soit un rationnel x = [a0 , a1 , a2 , ..., an ] alors les rationnels, not´e xi ,
d´efinis par x0 = [a0 ], x1 = [a0 , a1 ], x2 = [a0 , a1 , a2 ], ..., xk = [a0 , a1 , .., ak ], ...xn = [a0 , a1 , a2 , ..., an ] sont
appel´es des r´eduites de x.
Th´
eor`
eme Soit [a0 , a1 , a2 , ..., an ] la fraction continue de x. Pour tout i > 0, on d´efinit les nombres
pi et qi par :
pi = ai pi−1 + pi−2 ,
qi = ai qi−1 + qi−2
avec par convention p−2 = 0, q−2 = 1, p−1 = 1, q−1 = 0. On a alors :
xi = [a0 , a1 , a2 , ..., ai ] =

14

pi
qi

Preuve

La preuve se fait par r´ecurrence sur i.

Pour x0 on a p0 = a0 p−1 + p−2 = a0 , et de mˆeme on a q0 = 1. On a donc x0 = a0 ce qui nous
donne au final x0 = [a0 ] = pq00 .
Consid´erons que pour un i fix´e on ait xi = [a0 , a1 , a2 , ..., ai ] =
[a0 , a1 , a2 , ..., ai , ai+1 ]

=

pi
qi ,

on a donc :

[a0 , a1 , a2 , ..., ai +


1

1
]
ai+1



=

ai +
pi−1 + pi−2
ai+1


1
ai +
qi−1 + qi−2
ai+1

=

(ai ai+1 + 1)pi−1 + ai+1 pi−2
(ai ai+1 + 1)qi−1 + ai+1 qi−2

=

ai+1 (ai pi−1 + pi−2 ) + pi−1
ai+1 (ai qi−1 + qi−2 ) + qi−1

=

ai+1 pi + pi−1
ai+1 qi + qi−1

=

pi+1
qi+1

Ce qui ach`eve la r´ecurrence et la d´emonstration.
Th´
eor`
eme

alors

5.3

h
k

Soit x, y, h, k ∈ Z avec 1 ≤ y, 1 ≤ k < y et pgcd(h, k) = 1, pgcd(x, y) = 1. Si


x h
− < 1
y
k 2k 2

est une r´eduite de

x
y.

Id´
ee de Wiener

Soit (n, e) et (n, d) les cl´es d’un syst`eme RSA. On suppose q <
taille, ce qui implique 1 < pq < 2.



n < p et que p et q sont de mˆeme

Par construction on a :
ed = 1

(mod ϕ(n))

Il existe donc un entier k, (0 < k < d) tel que :
ed = 1 + kϕ(n)
De plus on sait par construction que :
ϕ(n) = (p − 1)(q − 1) = pq − p − q + 1 = n − (p + q) + 1
Ce qui nous donne en remontant `
a l’´egalit´e pr´ec´edente :
ed = 1 + k(n − (p + q) + 1)
15

En divisant l’´egalit´e par nd :
e
k 1 + k − k(p + q)
= +
n
d
nd
On a par la suite les in´egalit´es suivantes :


e

− k < k(p + q) − k − 1
n d
nd



e
− k < k(p + q)
n d
nd


e
kq( pq + 1)
− k <
n d
nd


e

− k < 3kq
n d
nd


e

− k < 3k
n d d √n


e

− k < √3
n d
n
Donc si :

n0.25
d < √ < n0.25
6
6
1
3
< √ =√
2d2
2 n
n

Ce qui nous donne au final :


e

− k < 1
n d 2d2
D’apr`es les r´esultats des fractions continues on peut dire que la fraction

5.4

k
d

est une r´eduite de

e
n.

Principe de l’attaque

Dans un syst`eme RSA, la cl´e (n, e) est une cl´e publique, donc accessible par n’importe qui. Il est donc
simple de calculer le d´eveloppement en fraction continue de la fraction ne .
On peut donc facilement calculer les valeurs k, d des r´eduites de ne .
A chaque it´eration il faut calculer la valeur de l’entier t = ed−1
et voir s’il nous permet de trouver les
k
facteurs premiers p et q de n. En effet, on peut trouver une approximation de ϕ(n) = ed−1
t , ce qui
nous permet de retrouver une d´ecomposition de n.
L’attaque de Wiener est donc un algorithme qui, si toutes les conditions sont r´eunies, de trouver
l’exposant priv´e d en un temps polynomial.

5.5

Impl´
ementation

L’attaque de Wiener peut donc ˆetre r´esum´ee par l’algorithme suivant.

16

Algorithme 8 Attaque de Wiener
Entr´
ee: N un module et e une cl´e publique d’un syst`eme RSA
Sortie: d la cl´e priv´ee et p, q les facteurs de N
L ← La liste des r´eduites de e/N
Pour chaque r´eduite x/y de L Faire
T ← (ey − 1) / x
D ← (N − T + 1)2 −
√ 4N
R ← (N − T + 1 − D) / 2
Si pgcd(R, N ) > 1 Alors
Renvoyer d = y, p = R, q = N / R
Fin Si
Fin Pour

5.6

Exemple

Soit la cl´e publique (27962863, 25411171). On suppose que l’indice d est tel que l’on puisse le trouver
grˆ
ace a l’attaque de Wiener. On commence par calculer les quotients partiels de la fraction ne ce qui
nous donne :
25411171
= [0, 1, 9, 1, 23, 7, ...]
27962863
Ce qui nous donne les r´eduites suivantes :
0

1

9
10

10
11

239
263

...

On peut dans un premier temps ´eliminer les deux premi`eres solutions. En effet les deux signifie que
d = 1 ce qui voudrait dire e = 1 ce qui n’est pas v´erifi´e.
10
Avec la fraction 11
on trouve pour la premi`ere fois un t = ed−1
= 27952288 entier. On a alors :
k
X 2 − (n − t + 1)X + n = X 2 − 10576X + 27962863
Les racines de ce polynˆ
omes sont 5279 et 5297 et on a finalement la d´ecomposition en deux facteurs
premiers p et q de n.
n = 5279.5297

17

6

Attaque Temporelle

Un syst`eme RSA, tout comme tout autre syst`eme de chiffrement, sont construits avec des op´erations
math´ematiques, et il est donc logique qu’il existe des attaques math´ematiques sur ses syst`emes. Mais il
existe aussi diff´erents types d’attaques. Des attaques physiques par analyse temporelle en font partie.
Elles consistent `
a ´etudier le temps que mettent diverses op´erations pour en tirer des informations.
Forc´ement, chaque programme, machine, protocole non s´ecuris´e ne sont pas vuln´erables aux mˆemes
attaques. Voyons un exemple qui permet de retrouver la valeur de la cl´e priv´ee.

6.1

Un cas pour RSA

Dans le cas d’un protocole RSA, la s´ecurit´e repose sur le fait qu’il existe une cl´e priv´ee d qui doit rester
secr`ete. Quand le destinataire re¸coit un chiffr´e, il peut le d´echiffrer en faisant une exponentiation
modulaire du chiffr´e par sa cl´e priv´ee d modulo n. Le principe est d’analyser, en supposant que
l’attaquant ait acc`es a suffisamment de donn´ees du destinataire, le temps de calcul d’exponentiation
pour retrouver la valeur de la cl´e priv´ee.
6.1.1

Exponentiation modulaire

On sait que des syst`emes RSA avec des petits entiers ne sont pas du tout s´ecuris´es et trop vuln´erables
a des attaques simples et rapides. On utilise donc souvent des nombres de grande taille pour les cl´es
`
(souvent entre 1024 et 2048 bits de nos jours). Pour calculer efficacement une exponentiation modulaire avec des nombres aussi grands, on ´evite de calculer d’abord la valeur de l’exponentiation, avec
une succession de multiplications, pour ensuite la mettre au modulo. Les op´erations seraient beaucoup
trop nombreuses et coˆ
uteuses. Pour faire ces calculs, on utilise des algorithmes d’exponentiation rapide.
On veut calculer ak modulo m, alors on remarque que si on ´ecrit k en binaire k = (k0 , . . . , kr )2
on remarque que ak = ak0 (ak1 (. . . (akr )2 )2 )2 .
Algorithme 9 Exponentiation modulaire
Sortie: a, k = (k0 , . . . , kr )2 , m
Sortie: ak (mod m)
y ← 1, i ← r
Tant que i > 0 Faire
y ← y 2 (mod m)
Si ki = 1 Alors
y ← y.a (mod m)
Fin Si
Fin Tant que
Renvoyer y

6.1.2

Un exemple d’analyse

Pour illustrer une analyse temporelle voyons un exemple simple, tr`es particulier. Supposons qu’Eve
soit notre attaquante et Alice le destinataire. Imaginons qu’Eve ait acc`es, lors du calcul de cd par
Alice (avec c le chiffr´e re¸cu), aux diff´erents temps de calcul pour chaque it´eration de l’algorithme d’exponentiation vu ci-dessus. Eve pourra alors d´eterminer la valeur de la cl´e priv´ee en analysant ces temps.
En effet, `
a chaque it´eration i de la boucle, le temps de traitement sera plus ou moins long en fonction du
coefficient binaire di de l’exposant d. Si l’ex´ecution de l’it´eration se fait en 2 op´erations (une ´el´evation
au carr´e et un modulo), alors le coefficient di de l’exposant est ´egal `a 0. Si di = 1, l’ex´ecution se fera
en 4 op´erations (une ´el´evation au carr´e, une multiplication et deux modulos).
18

6.2


ecurit´
e

L’exemple d´ecrit au-dessus est certes un exemple simple, dans un cas bien pr´ecis, qui n’est plus vraiment possible de nos jours, mais permet de bien comprendre le principe. Il existe d’autres analyses
temporelles, plus ou moins complexe, qui permettent de r´ecup´erer des donn´ees cens´ees ˆetre secr`etes.
De nos jours, la plupart des impl´ementations de protocole RSA (ou autres protocoles) utilisent une
technique qui permet de r´esister `
a ces attaques temporelles. Ce sont des techniques dites d’aveuglement
cryptographique. Dans notre exemple, on peut par exemple coder l’exponentiation rapide de fa¸con `
a
ce que son temps d’ex´ecution ne d´epende pas de la valeur de l’exposant, ce qui met donc en ´echec
cette analyse temporelle. On peut donc s´ecuriser le programme de fa¸con `a ne plus ˆetre vuln´erable `
a
des attaques du mˆeme type.

19

7

Conclusion

Le syst`eme RSA est tr`es utilis´e aujourd’hui car il est extrˆemement sˆ
ur car comme on l’a vu dans les
diff´erents algorithmes avec un entier tr`es grand (produit de grands facteurs premiers), les diff´erentes
attaques sont inutiles ou inefficaces (temps de calcul trop long). Les attaques sont souvent possibles
dans des cas tr`es pr´ecis, donc il faut des bons nombres pour le bon syst`eme afin que les diff´erentes
attaques soient efficaces. A ce jour, la taille du plus grand entier factoris´e ´etait de 768 bits. On pr´evoit
de pouvoir casser des entiers de 1024 bits dans un avenir proche mais peu imagine que l’on puisse
casser des entier de 2048 bits dans un avenir pr´evisible. Aujourd’hui, par sˆ
uret´e on utilise souvent donc
des entiers de taille 2048 bits.

20

Bibliographie
1. A. Dragut, ”RSA”.
2. Abderrahmane Nitaj, ”Diophantine and Lattice Cryptanalysis of the RSA Cryptosystem”.
3. Abderrahmane Nitaj, ”New vulnerabilities in RSA”.
4. Chris Christensen, ”Mathematical attack on RSA” (2006).
5. Dan Boneh, ”Twenty Years of Attacks on the RSA Cryptosystem”.
6. Jean-Guillaume Dumas, Jean-Louis Roch, Eric Tannier, S´ebastien Varrette, ”Th´eorie des codes,
Compression, cryptage, correction” (2013).
7. Michael J. Wiener, ”Cryptanalysis of Short RSA Secret Exponents”, (1989).
8. Nicolas Douziech, ”INF582 : Cryptologie Attaque de cl´es RSA par la m´ethode de Wiener ”, (2005).
9. Paul C. Kocher, ”Attacks on Implementations of Diffe-Hellman,RSA,DSS,and Other Systems”.
10. Thomas Richez, ”Les fractions continues”, (2010).

21


Documents similaires


Fichier PDF tpe cryptologie
Fichier PDF extraitssujetsprecedents
Fichier PDF serie d exercices de n 1 informatique bac sciences exp 2010 2011 mr ayadi
Fichier PDF 60
Fichier PDF coursnombrespremiersetppcm
Fichier PDF chap 2


Sur le même sujet..