TIPE ENS : Cryptanalyse de RSA par la méthode de

Coppersmith

Table des matières

1 Introduction 1

2 Le cryptosystème RSA 2
2.1 La cryptographie à clé publique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Attaquer RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

3 Réduction des réseaux 2

3.1 Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

4 Attaque de Coppersmith 4
4.1 Théorème de Howgrave-Graham et conséquence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.2 Méthode de Coppersmith . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

5 Conclusion 6

A Résultats de l’implémentation 7

B Pseudo-code de l’algorithme LLL 7

C Preuves 8

D Implémentation 10
D.1 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
D.2 LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
D.3 Coppersmith . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

E Bibliographie 15

1 Introduction
La cryptographie, science des codes secrets, joue un rôle très important dans le développement des techno-
logies actuelles et à venir. Des échanges de trames du protocole https, au stockage de données sur des serveurs,
de nombreux algorithmes ont été développés pour rendre de l’information indéchiffrable. Un des algorithmes les
plus répandus est l’algorithme RSA 1 .
La cryptanalyse, quant à elle étudie les méthodes pour décrypter des messages chiffrés sans en avoir les clés.
Dans cet exposé nous nous intéressons à une méthode de cryptanalyse de RSA. Cette méthode est proposée par
D. Coppersmith 2 et réinterprétée par N. Howgrave-Graham 3 . Elle s’appuie notamment sur des techniques de
réduction des réseaux 4

Après avoir introduit le cryptosystème RSA en section 2, nous étudierons l’objet et la réduction des réseaux
en section 3, avant de détailler la méthode de Coppersmith en section 4.
1. [1]
2. [3]
3. [4]
4. [2]

1
2 Le cryptosystème RSA
Dans cette section nous expliquons le principe du chiffrement par clé publique RSA, nommé d’après ses
inventeurs : R.L Rivest, A. Shamir et L. Adleman.

2.1 La cryptographie à clé publique

La cryptographie à clé publique a été d’abord introduite par W. Diffie et M. Hellman. Elle consiste à
construire, sur un ensemble de messages M et pour chaque utilisateur i, des applications Ei (clé de chiffrement
publique) et Di (clé de déchiffrement privée) inverses l’une de l’autre, faciles à calculer, et telles que, la connais-
sance de Ei ne permette pas de déduire Di . Alors, tous les utilisateurs peuvent utiliser Ei mais seul i connaı̂t
Di .
Ainsi, si un utilisateur j veut envoyer un message m ∈ M à i, il calcule c = Ei (m) 5 , qu’il envoie à i. Alors seul
i peut calculer m = Di (c) et lire le message.

Pour définir les Ei et Di , on utilise généralement des procédures identiques qui dépendent d’une clé privée
et d’une clé publique. C’est le cas dans RSA.

2.2 RSA
Les méthodes de chiffrement et de déchiffrement du cryptosystème RSA reposent sur le théorème suivant.

Théorème 2.1: RSA

Soient p et q des nombres premiers distincts, N = pq, e ∈ N premier avec ϕ(N ) = (p − 1)(q − 1) et
d = e−1 [ϕ(N )]. On a
∀m ∈ N, (me )d = m[N ]

Ainsi, le fonctionnement de RSA s’organise autour de 3 étapes :

Premièrement la génération des clés. Elle consiste à générer deux nombres premiers 6 p et q, calculer N = pq
et ϕ(N ) = (p − 1)(q − 1). Puis générer un nombre e premier à ϕ(N ) à l’aide de l’algorithme d’Euclide, et son
inverse d modulo ϕ(N ), à l’aide de l’algorithme d’Euclide étendu. La clé publique est (e, N ) et la clé privée est
d. En suite, l’encodage d’un message m ∈ {0, ..., N − 1} se fait à l’aide de la clé publique (e, N ) : l’envoyeur cal-
cule c = me [N ]. Enfin, le décryptage d’un message c se fait de manière analogue : le récepteur calcule m = cd [N ].

Notons que les procédures d’encodage et de décodage peuvent se calculer de manière efficace 7 mais que la
simple connaissance de (e, N ) ne permet pas de déduire facilement d. En effet cela nécessite le calcul ϕ(N ) =
(p − 1)(q − 1) et donc la factorisation de N , problème pour lequel il n’y a pas d’algorithmes efficaces dans le cas
général.

2.3 Attaquer RSA

Dans le cas général, avec les technologies actuelles 8 , il semble compliqué d’attaquer RSA de par la difficulté
à factoriser de grands nombres. Nous n’avons donc pas d’autre choix que de chercher à exploiter certaines failles
d’implémentation.
Le cadre que l’on développe dans cet exposé est le suivant : l’attaquant connaı̂t la clé publique (e, N ), ainsi
qu’une partie b du message envoyé (m = b + x avec x inconnu). L’objectif de l’attaquant est de trouver x, à
partir de c = me = (b + x)e [N ], ce qui est équivalent à résoudre p(x) = (b + x)e − c = 0[N ].
On se retrouve à devoir étudier les racines, modulo N , d’un polynôme à coefficients entiers. C’est sur ce problème
que porte les travaux de D. Coppersmith puis N. Howgrave-Graham . Leurs méthodes utilisent ce qu’on appelle
la réduction des réseaux. Continuons par l’étude de cette théorie.

3 Réduction des réseaux

Dans cette partie nous introduisons la notion de réseau ainsi qu’une méthode algorithmique permettant
l’obtention d’un certain type de base de vecteurs courts.
5. En envoyant c = Ei (Dj (m)) cette méthode permet aussi une signature du message. i calcule m = Ej (Di (c)).
6. Dans mon implémentation j’utilise le test de primalité probabiliste de Miller Rabin.
7. Par expodentiation rapide.
8. P. Shore trouve en 1994 un algorithme quantique de factorisation en O(log(N )3 ).

2
3.1 Définitions et propriétés
Définition 3.1 (Réseau, dimension, base). Soit n ∈ N, et L un sous-ensemble de Rn . On dit que L est un
réseau s’il existe m ∈ N et une famille libre b1 , ..., bm de Rn telle que
m
X Xm
L= Zbi = { ai bi |a1 , ..., am ∈ Z}
i=1 i=1

On dit alors que m est la dimension du réseau et que b1 , ..., bm en est une base.
On aura souvent tendance à utiliser des réseaux de dimension n. On a aussi la définition suivante.
Définition 3.2 (Déterminant). Soit L un réseau de Rn et b1 , ...bn une base de ce dernier. On appelle déterminant
de L la grandeur
det(L) = | det(b1 , ..., bn )|
Cette définition est bien licite car elle ne dépend pas de la base choisie. En effet le passage entre deux bases
d’un réseau se fait par une matrice de GLn (Z) qui a donc son déterminant dans {−1, 1}.
Nous introduisons aussi les notations suivantes pour l’orthogonalisée de Gram-Schmidt, qui sera particulièrement
utile dans notre étude.
Définition 3.3 (Orthogonalisation de Gram-Schmidt). Soit b1 , ..., bn une base de Rn . On pose b∗1 , ..., b∗n la base
Pi−1 <bi ,b∗ >
orthogonale définie par b∗1 = b1 et ∀2 ≤ i ≤ n b∗i = bi − j=1 µi,j b∗j avec ∀ 1 ≤ j < i ≤ n , µi,j = <b∗ ,bj∗ > .
j j

Un problème fondamental dans l’étude des réseaux est la recherche des vecteurs non nuls les plus courts du
réseau. En grande dimension ce problème semble difficile 9 à traiter de manière algorithmique. On introduit alors
la notion suivante de base réduite, qu’on peut interpréter comme une base de vecteurs relativement courts 10 .
Définition 3.4 (Base réduite). Soit B = (b1 , ..., bn ) une base d’un réseau L. On dit que B est réduite si
1
∀1 ≤ j < i ≤ n, |µi,j | ≤ (1)
2
3 ∗ 2
∀2 ≤ i ≤ n, ∥b∗i + µi,i−1 b∗i−1 ∥2 ≥ ∥b ∥ (2)
4 i−1
On appelera (1) condition de taille, et (2) condition de Lovász.
L’existence de telles bases dans un réseau quelconque n’est pas immédiate. Nous verrons dans la partie suivante
un algorithme permettant la construction de base réduite, et donc une preuve constructive de leur existence.
Mais intéressons nous d’abord à quelques encadrements qui seront pertinents pour la méthode de Coppersmith.

Propriété 3.1

Soit b1 , ..., bn une base réduite de L. On a alors

∀1 ≤ j ≤ i ≤ n, ∥bj ∥2 ≤ 2i−1 ∥b∗i ∥2 (3)

n
Y n(n−1)
det(L) ≤ ∥bi ∥ ≤ 2 4 det(L) (4)
i=1
(n−1) 1
∥b1 ∥ ≤ 2 4 det(L) n (5)

Retenons en particulier, pour la suite, la majoration (5) de ∥b1 ∥.

Nous allons désormais décrire l’algorithme LLL qui permet l’obtention de bases réduites.

3.2 Algorithme LLL

L’algorithme LLL, du nom de ses créateurs A. Lenstra, H. Lenstra et L. Lovász, transforme une base d’un
réseau en une base réduite.
Il consiste à agir sur la base b1 , ..., bn donnée en entrée de telle sorte que chaque transformation sur la famille
conserve sa propriété de base du réseau. De plus, on voudra la fin d’une étape k ∈ {1, ..., n + 1} de l’algorithme,
les invariants suivants soient vérifiés
1
∀1 ≤ l < k, |µk,l | ≤ (6)
2
3
∀1 < i < k, ∥b∗i + µi,i−1 b∗i−1 ∥2 ≥ ∥b∗i−1 ∥2 (7)
4
9. Et même NP-Difficile, ce qui en fait un bon objet pour la cryptographie.
10. La remarque après (1.12) dans [2] permet de vérifier cette intuition.

3
Notons que si on atteint k = n + 1, on retrouve la définition d’une base réduite. On initialise k à 2. On peut
ensuite résumer l’algorithme de la manière suivante :

On suppose être à l’étape d’indice k de l’algorithme. On commence par vérifier (6).

Si |µk,l | > 21 alors on effectue la transformation bk = bk − [µk,l ]bl 11 et on actualise la base et les coefficients de
Gram-Schmidt associés. Cette transformation garantie (6).
Puis on vérifie si ∥b∗k + µk,k−1 b∗k−1 ∥2 ≥ 43 ∥b∗k−1 ∥2 : Si cette condition n’est pas vérifiée, on échange bk et bk−1 ,
on met à jour la base et les coefficients de Gram-Schmidt et on pose k = max(1, k − 1). Dans la nouvelle base,
la valeur de ∥b∗k−1 ∥2 est inférieure strictement à 34 son ancienne valeur 12 . Sinon si (7) est vérifiée, on incrémente k.

Le pseudo code détaillé de l’algorithme est décrit en trois parties dans l’annexe B. Une grande partie des
fonctions LLL, taille et lovasz correspond au calcul ou à l’actualisation de la base et des coefficients de Gram-
Schmidt.

On s’intéresse maintenant à l’étude de la validité de cet algorithme.

Propriété 3.2: Terminaison de LLL

L’algorithme LLL se termine.

En remarquant que k est incrémenté uniquement lorsque les invariants sont vérifiés, et avec la remarque du
cas k = n + 1, l’algorithme fournit effectivement une base réduite.

Enfin, la force de l’algorithme LLL est sa complexité polynomiale pour trouver une base vecteurs courts,
malgré le caractère NP-Difficile de la recherche des vecteurs les plus courts du réseau.

Théorème 3.1: Compléxité LLL

Soit L un réseau, et b1 , ..., bn une base de ce dernier. On pose B = max(2, ∥b1 ∥, ..., ∥bn ∥). Alors l’algo-
rithme LLL permet de trouver une base réduite en un nombre d’opération arithmétique qui est polyno-
mial : O(n4 log(B)).

13

Voyons maintenant comment appliquer cette notion de réseau et de base réduite à la recherche de racines
d’un polynôme modulo N .

4 Attaque de Coppersmith
Cette partie décrit la méthode, dite de Coppersmith, qui permet de trouver les petites racines modulaires
d’un polynôme. Comme expliqué en 1.3 cela nous Pd permettra d’exploiter des failles de RSA. On introduit donc
dans cette partie les objets suivants : P (x) = k=0 ak xk ∈ Z[x] un polynôme unitaire, X ∈ N∗ et on suppose
qu’il existe x0 ∈ Z tel que x0 < X et P (x0 ) = 0[N ]. L’objectif est de trouver un tel entier x0 .
Plus précisément, on s’intéresse aux résultats de N. Howgrave-Graham qui a repris et simplifié la méthode
décrite par Coppersmith.
L’idée directrice est de transformer la recherche des solutions de P (x) = 0[N ] en la recherche des racines entières
d’un bon polynôme R(x). Ce dernier problème est nettement plus simple à résoudre. En effet, il suffit d’appliquer
la méthode de Newton et essayer les entiers les plus proches des solutions approchées trouvées 14 .

4.1 Théorème de Howgrave-Graham et conséquence

On veut faire le passage de l’équation modulo N Pdà la recherche de racines entières d’un polynôme.
D’après la majoration de x0 , on sait que |P (x0 )| ≤ k=0 |ak |X k . Ainsi, si les coefficients (ak ) était suffisemment
≪ petits ≫, on aurait |P (x0 )| < N et on pourrait se contenter de résoudre l’équation P (x) = 0. Le théorème

de Howgrave-Graham donne une condition plus précise de ce qui est petit. Avant d’énoncer le théorème on
introduit la notation suivante :

11. [x] désigne l’entier le plus proche de x.

12. Cela découle du fait qu’on fait le changement ∥b∗k−1 ∥2 = ∥b∗k ∥2 + µ2k,k−1 ∥b∗k−1 ∥2 .
13. Nous admettons ce théorème, mais une démonstration, assez fastidieuse, est proposée dans [2].
14. Dans mon implémentation j’utilise la fonction proposée par numpy qui s’appuie sur une méthode de recherche de valeurs
propres.

4
 Pd
Définition 4.1. Pour Q(x) = k=0 qk xk , on note le vecteur ligne bQ = (q0 , q1 X, q2 X 2 , ..., qd X d ). De manière
réciproque, d’un vecteur quelconque on peut déduire un polynôme associé à ce vecteur de cette manière.
De manière équivalente, on construit un isomorphisme entre Rd [X] et Rd+1 .

Théorème 4.1: Howgrave-Graham

Si x0 < X est une solution de P (x) = 0[N ] avec ∥bP ∥ < √N alors P (x0 ) = 0.
d+1

Appliquer ce théorème directement à P est très contraignant. Mais on peut se contenter de l’appliquer à un
polynôme, ayant les mêmes racines modulaires que P , mais dont les coefficients sont plus petits, ou encore tel
que le vecteur associé est plus court. On pense alors aux bases réduites décrites précédemment. Il s’agit alors
de construire une base qui engendre un réseau de polynomes avec les bonnes propriétés.

Pour engendrer un réseau de polynômes qui ont les mêmes racines modulaires que P , une première idée est
d’utiliser la famille (Gi (x))0≤i≤d−1 = (N xi )0≤i≤d−1 . Tout entier est racine modulo N de ces polynômes. Par
combinaison linéaire à coefficients entiers, un polynôme du réseau engendré par (bG0 , ..., bGd−1 , bP ) a les mêmes
racines modulo N que P .

Propriété 4.1

Le réseau engendré par (bG0 , ..., bGd−1 , bP ) est de dimension d + 1 et a pour déterminant
d(d+1)
det(L) = X 2 Nd

Notons G le polynôme associé à b1 où (b1 , ..., bd+1 ) est la base réduite donnée par l’algorithme LLL à partir
de (bG0 , ..., bGd−1 , bP ). On a alors le résultat suivant.

Théorème 4.2
2
1
Soit G et P les polynômes construits comme précédemment. On suppose que X < √ 1 N d(d+1) .
2(d+1) d
Alors si x0 est une solution de P (x) = 0[N ] avec |x0 < X, alors x0 est une solution de G(x) = 0 sur Z.

Cette majoration de X est malheureusement très restrictive. Par exemple, pour d = 3 et N = 1000, on
trouve X < 1, 4 ... Dans la sous-partie suivante on cherchera à augmenter la borne X, ce qui constituera la
méthode de Coppersmith.

4.2 Méthode de Coppersmith

La méthode de Coppersmith est fonctionne de manière similaire à celle de la partie précédente. La différence
est le choix de la base de polynômes pour construire le réseau. La dimension du réseau sera aussi plus importante.

Avant de caractériser la base de polynômes considérée commençons par énoncer le théorème voulu.

Théorème 4.3: Coppersmith

1
Soit 0 < ε < 0, 18(1 − d1 ). On suppose X < 21 N d −ε . Si x0 est une solution de P (x) = 0[N ] telle que
|x0 | < X alors x0 peut être retrouvé en un temps polynomial.

Pour construire la base utilisée dans la méthode de Coppersmith on introduit un entier h = ⌈ d−1 1 15
d2 ε + d ⌉ .

Définition 4.2. Soit 0 ≤ i < d et 0 ≤ j < h. On note

Gi,j (x) = N h−1−j P j (x)xi

On considère alors, dans la méthode de Coppersmith, le réseau de dimension hd engendré par les vecteurs
(bGi,j )0≤i<d,0≤j<h .
Pour justifier l’intuition derrière ce choix de polynômes, remarquons notemment une chose :

15. Cet entier qui peut paraı̂tre arbitraire mais est choisit de manière à faire apparaı̂tre la puissance ε dans le théorème de
Coppersmith.

5
 Si x0 est tel que P (x0 ) = 0[N ] alors Gi,j (x0 ) = 0[N h ]. En cherchant des racines modulo N h , on augmente
la borne de droite dans le théorème de Howgrave-Graham, ce qui rend plus facile le passage à une équation sur
les entiers.

Le bon choix de ces polynômes relève aussi des majorations astucieuses obtenues lors des calculs de bornes
dans la démonstration du théorème énoncé.

5 Conclusion
La méthode qui a permis d’attaquer le cryptosystème RSA se résume de la manière suivante.
La première étape est de transformer la recherche du mot chiffré en une équation polynomiale de la forme
P (x) = 0[N ]. On note x0 une solution recherchée. En introduisant une bonne base de polynômes Gi,j , on peut
engendrer un réseau de polynômes qui admettent aussi x0 comme racine modulaire. Appliquer l’algorithme LLL
de réduction des réseaux peut permettre (à condition que x0 soit suffisement petit) de trouver en un temps
polynomial, un polynôme G dont x0 est racine. Il suffit alors d’énumerer les racines de G et voir lesquelles
vérifient P (x) = 0[N ].

6
A Résultats de l’implémentation
Le programme de l’annexe D.1 est une implémentaion de RSA. En l’exécutant, on peut observer que les clés
publiques et privées on bien été générées. Un test est fait avec le message :

m = 314159265358979323846264338327950288419716939937510

En suite, un exemple d’instance du programme fournit le chiffre suivant :

c =13600371137187468972790230283658633366150976268134762667536687487516138682250123713191293383405
39200719582350173638047017259116762844893075014734686423441703597410308231436231015187133341269
20222779068769087744703141381162097183105100368157536078547574720930354477340984940194872777779
75084063544827198532052734378484857583909501782456862269760933128863954486773873344752428932163
65242313844760186194325706004432080027981229867176444047463061248093398576169535549755371803614
82570987420179393812653105451933840037481512886353127863227040605785083039414160404374336617780
19453282563352427220360335548637943494604538324

Dans tous les cas, on parvient à déchiffrer le message par la suite.

Dans l’annexe D.2, on implémente l’algorithme LLL. Le test est fait sur un petit réseau de dimension 3
engendré par les vecteurs ((1, 1, 1), (−1, 0, 2), (3, 5, 6)). La base réduite obtenue est ((0, 1, 0), (1, 0, 1), (−1, 0, 2)).
On peut vérifier à la main que le résultat est correct. L’exemple suivant validera aussi l’implémentation de LLL.

Enfin, dans l’annexe D.3, on implémente les méthodes des sections 4.1 et 4.2 pour la recherches de petites
racines modulaires d’un polynôme. On reprend l’exemple 19.1.6 proposé dans [5] avec le polynôme P (x) =
x3 + 102 + 5000x − 222 et N = 10001. Avec les deux méthode on trouve 4 comme solution. Cette solution
convient effectivement.

B Pseudo-code de l’algorithme LLL

Algorithme 1 LLL
Input : Une base b1 , ..., bn d’un réseau L
Output : La base b1 , ..., bn transformée en une base réduite
for i = 1, ..., n do
b∗i = bi
for j = 1, ..., i − 1 do
⟨bi ,b∗ ⟩
µi,j = Bjj
b∗i = b∗i − µi,j b∗j
end
Bi = ∥b∗i ∥2
end
k=2
Appliquer taille(k, k − 1) ; // (*)
if 43 Bk−1 > Bk + µ2k,k−1 Bk−1 then
Appliquer lovasz(k)
Aller à (*)
end
for l = k − 2, ..., 1 do
Appliquer taille(k, l)
end
if k = n then
Arrêter l’algorithme
end
k =k+1
Aller à (*)

7
 Algorithme 2 Lovasz
Input : Un entier k
Output : Fait l’échange de bk et bk−1 et calcule les nouveaux coefficients de Gram-Schmidt
µ = µk,k−1
B = Bk + µ2 Bk−1
µk,k−1 = µBBk−1
Bk = Bk−1 B
Bk

Bk−1 = B
Échanger bk et bk−1
for j = 1, ..., k − 2 do
Échanger µk−1,j et µk,j
end
for i = k + 1, ..., n do
µ′ = µi,k−1
µi,k−1 = µk,k−1 µi,k−1 + (1 − µk,k−1 µ)µi,k
µi,k = µ′ − µµi,k
end
if k > 2 then
k =k−1
end

Algorithme 3 taille
Input : Un couple (k, l)
1
Output : Un vecteur bk et des valeurs µk,j avec j = 1, ..., l − 1 et |µk,l | ≤ 2
if |µk,l | > 21 then
bk = bk − [µk,l ]bl
for j = 1, ..., l − 1 do
µk,j = µk,j − [µk,l ]µl,j
end
µk,l = µk,l − [µk,l ]
end

C Preuves
Preuve : Théorème 2.1 (RSA)

Soit m ∈ N. Par hypothèse il existe k ∈ N tel que ed = 1 + kϕ(N ). Montrons que med − m = 0[p]. Si p|m
c’est immédiat. Sinon, d’après le petit théorème de Fermat, on a med = m1+kϕ(N ) = m(mp−1 )k(q−1) =
m[N ]. Alors de même med − m = 0[q] et puisque p ∧ q = 1, d’après le théorème des restes chinois,
med − m = 0[pq]. Soit med = m[N ].

8
Preuve : Propriété 3.1

Soit 2 ≤ i ≤ n. Par inégalité triangulaire dans (2), on a ∥b∗i ∥2 ≥ ( 34 − µ2i,i−1 )∥b∗i−1 ∥2 et d’après (1)
∥b∗i ∥2 ≥ 21 ∥b∗i−1 ∥2 . On déduit alors d’une récurrence que pour tout 1 ≤ j ≤ i ≤ n, 2i−j ∥b∗i ∥2 ≥ ∥b∗j ∥2 (*).
Ainsi, pour 1 ≤ i ≤ n
i−1
X
∥bi ∥2 = ∥b∗i + µi,j b∗j ∥2
j=1
i−1
X
= ∥b∗i ∥2 + |µi,j |2 ∥b∗j ∥2 par orthogonalité
j=1
i−1
1 X i−j ∗ 2
≤ (1 + 2 )∥bi ∥ d’après (*) et (1)
4 j=1
1
≤ (1 + (2i−1 − 1))∥b∗i ∥2
2
≤ 2i−1 ∥b∗i ∥2 (**)

Donc, d’après (*) et (**), pour 1 ≤ j ≤ i ≤ n, ∥bj ∥2 ≤ 2j−1 ∥b∗j ∥2 ≤ 2i−1 ∥b∗i ∥2 ; d’où (3).
Puisque le déterminant est multilinéaire
Qn et alterné, on a det(L) = | det(b∗1 , ..., b∗n )|. Puis, puisque b1 , ..., bn
a ∗
est orthogonale , det(L) = i=1 ∥bi ∥. De plus, puisque la projection orthogonale contracte les normes :
pour tout 1 ≤ i ≤ n, ∥bi ∥ ≥ ∥b∗i ∥. Ainsi, avec (3) on a
n n
Y Y i−1 n(n−1)
det(L) ≤ ∥bi ∥ ≤ 2 2 ∥b∗i ∥ ≤ 2 4 det(L)
i=1 i=1

D’où (4). Enfin, d’après (3) avec j = 1, et en passant au produit pour i = 1, ..., n, on retrouve (5).
a. On peut évoquer pour cela l’interprétation géométrique du déterminant. Une preuve théorique est cependant envisa-
geable.

Preuve : Propriété 2.2 (Terminaison de LLL)

Pour démontrer la terminaison de LLL nous introduisons le déterminant de Gram : di =

det(⟨bj , bk ⟩1≤j,k≤i ) = Gram(b1 , ..., bi ). Notons de plus que bi = b∗i + α avec α le projeté orthogonale de
bi sur Vect(b1 , ..., bi−1 ). On montre alors par bilinéarité du produit scalaire et n-linéarité du déterminant
que Gram(b1 , ..., b∗i ) = di . Or par orthogonalité, Gram(b1 , ..., b∗i ) est diagonale par blocs ce qui permet
Qi
de trouver que di = di−1 ∥b∗i ∥2 . On montre alors par récurrence que di = j=1 ∥b∗i ∥2 .
Qn−1
Posons ensuite D = i=1 di . D’après l’expression des di , la valeur de D est modifiée si celle d’un ∥b∗i ∥2
l’est. On remarque dans le pseudo-code que ces valeurs ne sont modifiées que dans l’appelle de la fonc-
tion Lovasz : il existe a < 34 tel qu’on ait le changement ∥b∗k−1 ∥2 = a∥b∗k−1 ∥2 et ∥b∗k ∥2 = a1 ∥b∗k ∥2 ; les
autres ∥b∗i ∥2 sont inchangés. Il en découle que dk−1 est réduit d’un facteur < 43 et que les autres di sont
inchangés. Et donc que D est réduit d’un facteur < 43 .
Nous admettons a que D est minoré par un réel strictement positif. Cela implique que l’on peut appliquer
Lovasz qu’un nombre fini de fois. Or, puisque k est décrémenté dans Lovasz mais incrémenté sinon,
cela implique que l’algorithme se termine.
a. Cela découle d’une minoration de la taille du plus court vecteur non nul d’un réseau.

Preuve : Théorème 2.1 (Howgrave-Graham)

Il suffit de remarquer, en vertue de l’inégalité de Cauchy-Schwarz, que

v
d u d
X
k
√ uX √
P (x0 ) ≤ |ak |X ≤ d + 1t (ak X k )2 = d + 1∥bP ∥ < N
k=0 k=0

9
 Preuve : Propriété 3.1

La famille (G0 , ..., Gd1 , P ) est libre par théorème des degrés étagés, donc bG0 , ..., bGd−1 , bP ) qui en est
l’image par l’isomorphisme qui fait la correspondance avec les vecteurs l’est aussi. De plus la famille de
vecteur est représentée par la matrice triangulaire M suivante.
 
N 0 ... 0 0
 0 NX . . . 0 0 
 
M = . . . . . . . . . . . . . . .

 0 0 ... N X d−1 0 
a0 a1 X . . . ad−1 X d−1 X d
d(d+1)
dont le déterminant est det(M ) = det(L) = X 2 N d.

Preuve : Théorème 3.2

D’après la majoration (5) de la propriété 2.1, on a

n−1 1 d 1 d d d
∥b1 ∥ ≤ 2 4 det(L) n = 2 4 det(L) d+1 = 2 4 X 2 N d+1

D’après le théorème de Hograve-Graham, une conditions suffisante pour avoir le résultat voulu est que
d d d N
2 4 X 2 N d+1 < √
d+1
ce qui est équivalent à
1 2
X<√ 1 N d(d+1)
2(d + 1) d

Preuve : Théorème 3.3 : Coppersmith

En ordonnant les Gi,j par degrés croissants, la matrice associée aux bGi,j est triangulaire avec les co-
efficients diagonaux N h−1−j X jd+i . En prenant le produit de tout ces termes, on obtient : det(L) =
d hd
N 2 (h(h−1) X 2 (hd−1) .
Or, toujours en notant b1 le vecteur de la base réduite associée à (bGi,j ), on à la majoration (5) qui
donne : dh−1 dh−1 h−1 dh−1
1
∥b1 ∥ ≤ 2 4 det(L) dh = 2 4 N 2 X 2
Or en appliquant le théorème de Howgrave-Graham, une condition suffisante pour passer à l’équation sur
h
Z est ∥b1 ∥ < √Ndh . En combinant les deux égalité et en simplifiant le résultat obtenu, puis en remplaçant
h par son expression, on obtient la condition suffisante a :
√ 1 1 d−1 1
2(dh) dh−1 X < N d − d(dh−1) < N d −ε
√ 1 √ dε
En notant c(d, h) = 2(dh) dh−1 = 2( d−1 dε + 1)
d−1 (en faisant l’approximation qu’on omet les parties
1
entières), cette condition devient X < c(d,h)1
N d −ε .
dε √
1
Pour avoir la borne du théorème, il suffit que 12 ≤ c(h,d) soit ( d−1
dε +1)
d−1 ≤ 2. Une étude de x 7→ (1+ x1 )x
permet de déduire que cette majoration est valide si ε ≤ 0, 18(1 − d1 ). Dans ce cas on obtient bien la
borne voulue.
La méthode emploie l’algorithme LLL (polynomial en hd et N h ∥bp ∥) et la recherche des solution d’un
polynôme (aussi en temps polynomial). Puisque les initialisation des bases se fait aussi en temps poly-
nomial, la méthode de Coppersmith a une complexité polynomiale.
a. C’est aussi à ce moment que se fait le choix de h pour voir apparaı̂tre ε

D Implémentation
D.1 RSA
1 import random

10
2

4 # ALGORITHMES D ’ARITHMETIQUE USUELS

5

6 #C a l c u l e mˆ e mod n ( e x p o d e n t i a t i o n r a p i d e )
7 d e f mod exp (m, e , n ) :
8 result = 1
9 base = m % n
10 while e > 0:
11 i f e % 2 == 1 :
12 r e s u l t = ( r e s u l t ∗ base ) % n
13 base = ( base ∗ base ) % n
14 e //= 2
15 return r e s u l t
16

17 #C a l c u l e l e r = pgcd ( a , b ) a i n s i que d e s e n t i e r s u e t v t e l s que au+bv = r

18 def euclide etendu (a , b) :
19 u1 , u2 , u3 = 1 , 0 , a
20 v1 , v2 , v3 = 0 , 1 , b
21

22 w h i l e v3 != 0 :
23 q = u3 // v3
24 v1 , v2 , v3 , u1 , u2 , u3 = (
25 u1 − q ∗ v1 ,
26 u2 − q ∗ v2 ,
27 u3 − q ∗ v3 ,
28 v1 ,
29 v2 ,
30 v3 ,
31 )
32 r e t u r n u3 , u1 , u2
33

34

35 # GENERATION DE NOMBRES PREMIERS

36

37 # Test de temoin
38 def test temoin (a , n) :
39 k = 0
40 d = n − 1
41 w h i l e d % 2 == 0 :
42 k += 1
43 d //= 2
44 x = mod exp ( a , d , n )
45 i f x == 1 o r x == n − 1 :
46 return False
47 for in range ( k − 1) :
48 x = (x ∗ x) % n
49 i f x == n − 1 :
50 return False
51 r e t u r n True
52

53 # Test de M i l l e r −Rabin
54 def m i l l e r r a b i n (n , k) :
55 i f n <= 3 :
56 r e t u r n n == 2 o r n == 3
57 i f n % 2 == 0 :
58 return False
59

60 for in range ( k ) :
61 a = random . r a n d i n t ( 2 , n − 2 )
62 i f test temoin (a , n) :
63 return False
64 r e t u r n True
65

66

67

11
68 # G e n e r a t e u r de nombres p r e m i e r s
69 d e f g e n e r a t e p r i m e ( b i t s , k=100) :
70 w h i l e True :
71 n = random . g e t r a n d b i t s ( b i t s )
72 n |= ( 1 << ( b i t s − 1 ) ) | 1
73 i f m i l l e r r a b i n (n , k) :
74 return n
75

76 #Genere deux nombre p r e m i e r s d i s t i n c t s

77 def generate primes ( b i t s = 1024) :
78 p = generate prime ( bits )
79 q = generate prime ( bits )
80 w h i l e p==q :
81 q = generate primes
82 return p , q
83

84 # GENERATION CLES RSA

85

86

87 c l a s s RSA :
88

89 def init ( self ) :

90 s e l f . generate keys ()
91

92 #Cle p u b l i q u e : ( e , n )
93 #Cle p r i v e e : d
94 def g e n e r a t e k e y s ( s e l f , b i t s = 1024) :
95 p , q = generate primes ()
96 s e l f . n = p∗q
97 p h i n = ( p−1) ∗ ( q−1)
98 w h i l e True :
99 e = random . r a n d i n t ( 2 , p h i n )
100 r , u , v = euclide etendu ( e , phi n )
101 i f r == 1 :
102 self .e = e
103 s e l f . d = u % phi n
104 break
105

106

107 # ENCODAGE D ’UN MESSAGE

108

109 d e f encode ( s e l f , m) :
110 r e t u r n mod exp (m, s e l f . e , s e l f . n )
111

112 # DECODAGE D ’UN MESSAGE

113 d e f decode ( s e l f , c ) :
114 r e t u r n mod exp ( c , s e l f . d , s e l f . n )
115

116

117 if n a m e == ” m a i n ” :
118 r s a = RSA( )
119 print ( ’ C l publique n : ’ , rsa . n)
120 p r i n t ( ” \n” )
121 print ( ’ C l publique e : ’ , rsa . e )
122 p r i n t ( ” \n” )
123 print ( ’ C l p r i v e d : ’ , rsa . d)
124 p r i n t ( ” \n” )
125

126 #p r e m i e r e s d e c i m a l e s de p i
127 m = 3 1 4 1 59 2 6 5 35 8 9 7 93 2 3 84 6 2 6 43 3 8 3 27 9 5 0 28 8 4 19 7 1 6 93 9 9 3 75 1 0
128 p r i n t ( ’ Message : ’ , m)
129 p r i n t ( ” \n” )
130

131 c = r s a . encode (m)

132 p r i n t ( ’ Message c o d : ’ , c)
133 p r i n t ( ” \n” )

12
134

135 m2 = r s a . decode ( c )
136 p r i n t ( ’ Message d c o d : ’ , m2)

D.2 LLL

1 import numpy a s np
2

4 c l a s s Basis :
5

6 # Les c o n s t r u c t e u r s de c e t o b j e t s o n t : une m a t r i c e r e p r s e n t a n t l a base , une

m a t r i c e c o n t e n a n t l e s mu { i , j } e t un v e c t e u r c o n t e n a n t l e s B i
7 def i n i t ( self , basis ) :
8 s e l f . basis = basis
9 s e l f . gram schmidt ( )
10

11 #C a l c u l e , p a r t i r d ’ une base , l e s c o e f f i c i e n t s de Gram−Schmidt

12 d e f gram schmidt ( s e l f ) :
13 basis = s e l f . basis
14 n = len ( basis )
15 m = len ( basis [ 0 ] )
16 o r t h o g o n a l b a s i s = np . copy ( b a s i s )
17

18 #M a t r i c e s c o n t e n a n t l e s c o e f f i c i e n t s de Gram−Schmidt
19 mu = np . z e r o s ( ( n ,m) )
20 B = np . z e r o s ( n )
21 B [ 0 ] = np . dot ( b a s i s [ 0 ] , b a s i s [ 0 ] )
22

23 f o r i in range (1 , n) :
24 f o r j in range ( i ) :
25 mu [ i , j ] = np . dot ( b a s i s [ i ] , o r t h o g o n a l b a s i s [ j ] ) /np . dot (
orthogonal basis [ j ] , orthogonal basis [ j ])
26 o r t h o g o n a l b a s i s [ i ] −= mu [ i , j ] ∗ o r t h o g o n a l b a s i s [ j ]
27 B [ i ] = np . dot ( o r t h o g o n a l b a s i s [ i ] , o r t h o g o n a l b a s i s [ i ] )
28 s e l f . mu = mu
29 s e l f .B = B
30

31

32 # Echange b k e t b {k−1} e t c a l c u l e l e s nouveaux c o e f f i c i e n t s de Gram−Schmidt

33 def lovasz ( s e l f , k) :
34 n = len ( s e l f . basis )
35 mu0 = s e l f . mu [ k , k −1]
36 b = s e l f . B [ k ] + mu0∗mu0∗ s e l f . B [ k −1]
37 s e l f . mu [ k , k −1] = mu0∗ s e l f . B [ k −1]/b
38 s e l f . B [ k ] = s e l f . B [ k −1]∗ s e l f . B [ k ] / b
39 s e l f . B [ k −1] = b
40 s e l f . b a s i s [ [ k , k − 1 ] ] = s e l f . b a s i s [ [ k−1 , k ] ] # Echange b k e t b {k−1}
41

42 # A c t u a l i s a t i o n d e s c o e f f i c i e n t s de Gram−Schmidt
43 f o r j i n r a n g e ( k−1) :
44 s e l f . mu [ k , j ] , s e l f . mu [ k −1 , j ] = s e l f . mu[ k−1 , j ] , s e l f . mu [ k , j ]
45 f o r i i n r a n g e ( k+1 , n ) :
46 mu1 = s e l f . mu [ i , k −1]
47 s e l f . mu [ i , k −1] = s e l f . mu[ k , k −1]∗ s e l f . mu [ i , k−1]+(1− s e l f . mu [ k , k −1]∗mu0) ∗
s e l f . mu [ i , k ]
48 s e l f . mu [ i , k ] = mu1 − mu0∗ s e l f . mu [ i , k ]
49

50 r e t u r n max( k −1 ,1)
51

52

53 # O p r e l a t r a n s f o r m a t i o n b k = b k − [ mu {k , l } ] b l e t a c t u a l i s e l e s c o e f f i c i e n s
de Gram−Schmidt
54 def t a i l l e ( s e l f , k , l ) :
55 i f abs ( s e l f . mu [ k , l ] )> 0.5+ 10∗∗( −12) :

13
56 # Le + 10ˆ( −12) permet de r s o u d r e un d i s f o n c t i o n n e m e n t dans l e c a s d ’
galit
57 s e l f . b a s i s [ k ] = s e l f . b a s i s [ k ] − round ( s e l f . mu [ k , l ] ) ∗ s e l f . b a s i s [ l ]
58

59 # A c t u a l i s a t i o n d e s c o e f f i c i e n t s de Gram−Schmidt
60 f o r j in range ( l ) :
61 s e l f . mu [ k , j ] = s e l f . mu [ k , j ] − round ( s e l f . mu [ k , l ] ) ∗ s e l f . mu [ l , j ]
62 s e l f . mu [ k , l ] = s e l f . mu[ k , l ] − round ( s e l f . mu [ k , l ] )
63

64

65

66

67 # Applique l ’ a l g o r i t h m e LLL l a base

68 def l l l ( s e l f ) :
69 n = len ( s e l f . basis )
70 s e l f . gram schmidt ( )
71 k = 1
72 while (k < n) :
73 s e l f . t a i l l e ( k , k−1)
74 i f 0 . 7 5 ∗ s e l f . B [ k −1] > s e l f . B [ k ] + s e l f . mu [ k , k −1]∗ s e l f . mu [ k , k −1]∗ s e l f . B [ k
−1]:
75 k = s e l f . lovasz (k)
76 continue
77 f o r l i n r a n g e ( k−2 , −1, −1) :
78 s e l f . t a i l l e (k , l )
79 k+=1
80

81

82 if name == ” main ”:
83

84 ’’’
85 a = np . a r r a y ( [ [ 4 7 . , 2 1 5 . ] , [ 9 5 . , 4 6 0 . ] ] )
86 b = Basis (a)
87 p r i n t ( ” Base : \n ” , b . b a s i s )
88

89 b. l l l ()
90 p r i n t ( ” Base r d u i t e : \n ” , b . b a s i s )
91 ’’’
92

93 a = np . a r r a y ( [ [ 1 . , 1 . , 1 . ] , [ − 1 . , 0 . , 2 . ] , [ 3 . , 5 . , 6 . ] ] )
94 b = Basis (a)
95 p r i n t ( ” Base : \n” , b . b a s i s )
96 b. l l l ()
97 p r i n t ( ” Base r d u i t e : \n” , b . b a s i s )

D.3 Coppersmith

1 import numpy a s np
2 from numpy . p o l y n o m i a l import Polynomial
3 from LLL import B a s i s
4 from r s a import RSA
5

7 #Opere l a t r a n s f o r m a t i o n p o l y n m e −v e c t e u r e x p o s e e dans l e d o s s i e r
8 d e f p o l y t o v e c t ( poly , X, s i z e =−1) :
9 d = poly . degree ()
10 n = max( s i z e , d+1)
11 v e c t = np . z e r o s ( n )
12 f o r i in range (n) :
13 i f i <d+1:
14 v e c t [ i ] = p o l y . c o e f [ i ] ∗ X ∗∗ i
15

16 return vect
17

18 # Opere l a t r a n s f o r m a t i o n polynome−v e c t e u r e x p o s e e dans l e d o s s i e r

14
19 d e f v e c t t o p o l y ( v e c t , X) :
20 n = len ( vect )
21 p o l y = Polynomial ( [ 0 ] )
22 f o r i in range (n) :
23 monomial = Polynomial ( [ 0 ] ∗ i + [ 1 ] )
24 p o l y += ( v e c t [ i ] / (X ∗∗ i ) ) ∗ monomial
25

26 return poly
27

28

29 # C o n s t r u i t l a b a s e de v e c t e u r s pour l a methode de l a s e c t i o n 4 . 1
30 d e f p o l y t o b a s i s 2 ( poly , N, X, h ) :
31 d = poly . degree ( )
32 a = np . z e r o s ( ( d ∗ h , d ∗ h ) )
33 f o r j in range (h) :
34 f o r i in range (d) :
35 monomial = Polynomial ( [ 0 ] ∗ i + [ 1 ] )
36 G = (N∗ ∗ ( h−1−j ) ) ∗ ( p o l y ∗∗ j ) ∗ monomial
37 v e c t = p o l y t o v e c t (G, X, s i z e=h∗d )
38 a [ i + d ∗ j ] += v e c t
39 return Basis (a)
40

41 # C o n s t r u i t l a b a s e de v e c t e u r s pour l a methode de Coppersmith

42 d e f p o l y t o b a s i s 1 ( poly , N, X) :
43 d = poly . degree ( )
44 a = np . z e r o s ( ( d+1 , d+1 ) )
45

46 f o r i in range (d) :
47 monomial = Polynomial ( [ 0 ] ∗ i + [ 1 ] )
48 G = N∗ monomial
49 v e c t = p o l y t o v e c t (G, X, d+1)
50 a [ i ] = vect
51 a [ d ] = p o l y t o v e c t ( poly , X)
52 return Basis (a)
53

54

55

56

57 p o l y = P ol ynomial ( [ − 2 22 , 5 0 0 0 , 10 , 1 ] )
58 print ( poly )
59 n = 10001
60 X = 10
61 h = 3
62

63 p r i n t ( ’ \n ’ )
64

65 b a s e 1 = p o l y t o b a s i s 1 ( poly , n , X)
66 base1 . l l l ( )
67 p1 = v e c t t o p o l y ( b a s e 1 . b a s i s [ 0 ] , X)
68 p r i n t ( p1 )
69 p r i n t ( p1 . r o o t s ( ) )
70

71 p r i n t ( ’ \n ’ )
72

73 b a s e 2 = p o l y t o b a s i s 2 ( poly , n , X, h )
74 base2 . l l l ( )
75 p2 = v e c t t o p o l y ( b a s e 2 . b a s i s [ 0 ] , X)
76 p r i n t ( p2 )
77 p r i n t ( p2 . r o o t s ( ) )

E Bibliographie
[1] R.L. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryp-
tosystems. Comm. ACM 21(2) (1978), 120–126.

15
 [2] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math.
Ann. 261 (1982), 515–534.

[3] D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal
of Cryptology, 10(4), 233—260 (1997).

[4] N. Howgrave-Graham. (1997). Finding Small Roots of Univariate Modular Equations Revisited. Pages
131–142 of : Darnell, Michael (ed), 6th IMA International Conference on Cryptography and Coding. LNCS, vol.
1355. Cirencester, UK : Springer, Heidelberg, Germany.

[5] S. Galbraith. (2012). Coppersmith’s Method and Related Applications. Pages 397-416 of : “Mathematics
of Public Key Cryptography”. Cambridge University Press.

16