0% ont trouvé ce document utile (0 vote)

103 vues76 pages

Crypt RSA

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

103 vues76 pages

Crypt RSA

Transféré par

dinguemlemgoto francis

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

CRYPTANALYSE DE RSA

Abderrahmane Nitaj

Laboratoire de Mathématiques Nicolas Oresme

Université de Caen, France

http://www.math.unicaen.fr/~nitaj

[email protected]

c Version du 28 juin 2009

Table des matières

Contenu i

Préface 1

1 Introduction au cryptosystème RSA 3

1.1 Principe de RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Le module RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Les clés publiques et privées . . . . . . . . . . . . . . . . . . . 5
1.1.3 Envoi d’un message . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.4 Déchiffrement d’un message . . . . . . . . . . . . . . . . . . . 8
1.1.5 Signature d’un message . . . . . . . . . . . . . . . . . . . . . . 9
1.1.6 Preuve de RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Un exemple d’utilisation de RSA . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Transformation d’un texte en nombres . . . . . . . . . . . . . 12
1.2.2 L’exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Cryptanalyses élémentaires de RSA . . . . . . . . . . . . . . . . . . 15
1.3.1 Cryptanalyse de RSA connaissant ϕ(N ) . . . . . . . . . . . . 15
1.3.2 Utilisation du même module et deux exposants différents . . . 16
1.3.3 Utilisation de modules différents pour le même message. . . . 18
1.3.4 Cryptanalyse de RSA si |p − q| < cN 1/4 : Méthode de Fermat 21

2 Cryptanalyse de RSA par les fractions continues 25

2.1 Les fractions continues . . . . . . . . . . . . . . . . . . . . . . . . . . 25

i
ii TABLE DES MATIÈRES

2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.2 Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . 26
2.2 Cryptanalyse de RSA par les fractions continues . . . . . . . . . . . . 37
2.2.1 L’attaque de Wiener . . . . . . . . . . . . . . . . . . . . . . . 38

3 Cryptanalyse de RSA par l’algorithme LLL 43

3.1 L’algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.1 Introduction aux réseaux . . . . . . . . . . . . . . . . . . . . . 43
3.1.2 L’algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2 Cryptanalyse de RSA par la réduction des réseaux . . . . . . . . . . . 59
3.2.1 La méthode de Coppersmith : polynômes à une variable . . . 59
3.2.2 Factorisation de N . . . . . . . . . . . . . . . . . . . . . . . . 69

Bibliographie 73
Préface

Si vous enseignez à un homme, vous n’enseignez qu’à une

personne. Si vous enseignez à une femme, vous enseignez à toute
une famille.
Ê« Y® ¯ è @QÓ@ IÒ
. éÊ K A« IÒ Ê« @ X@ AÓ @ , @ XQ ¯ IÒ
Ê« Y® ¯ Cg. P IÒ
Ê« @ X@

La cryptographie moderne est basée sur les mathématiques pour sécuriser l’infor-
mation. On distingue deux types de protocoles cryptographiques : la cryptographie
à clé privée et la cryptographie à clé publique. La cryptographie à clé publique à été
introduite par Whitfield Diffie et Martin Hellman en 1976, marquant ainsi la nais-
sance de la cryptographie moderne. Le principe de la cryptographie à clé publique
repose sur deux types de clés : une clé publique et une clé privée. Pour chiffrer un
message, on utilise la clé publique de son destinataire. Alors, seul le destinataire peut
déchiffrer le message reçu avec sa propre clé privée. En 1978, Ronald Rivest, Adi
Shamir et Leonard Adleman ont proposé le premier cryptosystème à clé publique,
appelé RSA. Ce cryptosystème est devenu le plus répandu dans le monde car il est
facile à réaliser mais très difficile à casser. En effet, sa sécurité repose sur l’un des
problèmes les plus difficiles en mathématiques : la factorisation des grand nombres.
Dans ce travail, nous introduisons les principes généraux du cryptosystème RSA
ainsi que certaines attaques permettant de le casser, si les paramètres de sécurité sont
mal choisis ou s’il vérifient des relations permettant à un attaquant d’en tirer profit.
Dans le chapitre 1, nous donnons les principes généraux du cryptosystème RSA et
nous présentons quelques attaques élémentaires permettant de le casser. Dans le
chapitre 2, nous présentons une introduction à la théorie des fractions continues
et leur utilisation pour attaquer le cryptosystème RSA dans certains cas. Dans
le chapitre 3, nous présentons quelques aspects de la réduction des réseaux, plus
précisément l’algorithme LLL et son utilisation pour attaquer le cryptosystème RSA
grâce à la méthode de Coppersmith.
Dans ce travail, la plupart des résultats sont illustrés par des algorithmes pro-
grammés à l’aide des systèmes de calcul Maple 12 et Magama dont un calculateur

1
2 TABLE DES MATIÈRES

en ligne est à l’adresse http://magma.maths.usyd.edu.au/calc/.

Chapitre 1

Introduction au cryptosystème
RSA

Celui qui n’aime pas gravir les montagnes, vivra toute sa vie dans
les trous.
Abou Al Qasim Achabi
YK @ ª È AJ.m.Ì '@ Xñª I. m' B áÓ ð
. Q®mÌ '@ áK. Që YË@ . K
ñK @
úG. AË@ Õæ A®Ë@ .

1.1 Principe de RSA

Toutes les opération du cryptosystème RSA se passe dans un ensemble de nombre

entiers. Soient p et q deux nombres premiers assez grands. On note N = pq. Le
nombre N est appelé module RSA. Supposons que deux personnes A et B veulent
communiquer de façon sûre en utilisant le cryptosystème RSA. Pour cela, ils doivent,
chacun de son coté préparer un module RSA, deux clés e et d, exécuter une procédure
de chiffrement et de signature et une procédure de déchiffrement et de vérification
de la signature.

1.1.1 Le module RSA

Avant tout, pour utiliser le cryptosystème RSA, chacun des intervenants A et B doit
fabriquer son propre module RSA. L’algorithme 1 peut être alors utilisé.

3
4 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

Algorithme 1 : Fabrication du module

Entrée : Une taille t pour le module du cryptosytème RSA.
Sortie : Un module RSA N de taille t. h t t+1 i
1: Prendre un nombre premier aléatoire p dans l’intervalle 2 2 , 2 2 .
h t t+1 i
2: Prendre un nombre premier aléatoire q dans l’intervalle 2 2 , 2 2 .
3: Si p = q alors
4: Aller à l’étape 2.
5: Sinon
6: N = pq.
7: Fin Si

h t t+1 i
Comme p et q sont dans l’intervalle 2 2 , 2 2 , alors on a

2t < pq < 2t+1 ,

ce qui montre que N = pq est de taille t.

Maple 1.1.1.

Avec Maple 12, l’algorithme 1 peut être réalisé comme ceci.

Programme Commentaires

t:=1024: <----- la taille du module RSA

x1:=round(2.0^(t/2)): <----- la borne inférieur 2^(t/2)
x2:=round(2.0^((t+1)/2)): <----- la borne supérieur 2^((t+1)/2)
m1:=(rand(x1 .. x2))(): <----- une valeur aléatoire
p:=nextprime(m1); <----- le nombre premier p
m2:=rand(x1 .. x2)(): <----- une valeur aléatoire
q:=nextprime(m2); <----- le nombre premier q
N:=p*q <----- le module RSA

Magma 1.1.2.

Avec Magma, l’algorithme 1 peut être réalisé comme ceci.

1.1. PRINCIPE DE RSA 5

Programme Commentaire

t:=1024; <----- la taille du module RSA

x1:=Round(2.0^(t/2)); <----- la borne inférieur 2^(t/2)
x2:=Round(2.0^((t+1)/2)); <----- la borne supérieur 2^((t+1)/2)
m1:=Random(x1,x2); <----- une valeur aléatoire
p:=NextPrime(m1); <----- le nombre premier p
m2:=Random(x1,x2); <----- une valeur aléatoire
q:=NextPrime(m2); <----- le nombre premier q
N:=p*q; <----- le module RSA
N; <----- affichage du module RSA
Dans Magma, la fonction RSAModulus(t,e) permet de créer un module RSA N
à t-bits tel que pgcd(e, φ(N )) = 1. Voici un exemple et sa vérification.
Programme Commentaire

t:=100; <--- Taille du module

e:=3; <--- L’exposant publique
N:=RSAModulus(t,e); <--- Création du module
N; <--- Affichage de N
f:=Factorization(N); <--- Sa factorization
f; <--- Affichage de la factorisation
Log(N)/Log(2); <--- Taille du module
p:=f[1,1]; <--- Premier nombre premier
q:=f[2,1]; <--- Deuxième nombre premier
p; <--- Affichage de p
q; <--- Affichage de p

1.1.2 Les clés publiques et privées

Après avoir fabriqué un module RSA, chacun des intervenants doit préparer une clé
secrète d et une clé publique e :
Dans certains cas, on peut prendre pour la clé publique des valeurs spécifiques, par
exemple e = 3 ou e = 216 + 1. Dans ce cas, les étapes 2 à 5 de l’algorithme 2 ne sont
pas exécutées.
La fonction φ joue un rôle central dans le cryptosystème RSA et s’appelle la fonction
d’Euler.
Définition 1.1.3. Soit n un nombre entier. La fonction indicatrice d’Euler est
φ(n) = # {a |0 ≤ a ≤ n − 1, pgcd(a, n) = 1} .
6 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

Algorithme 2 : Fabrication des clés

Entrée : Deux nombres premiers p et q.
Sortie : Une clé privée d et une clé publique e.
1: Calculer φ(N ) = (p − 1)(q − 1).
2: Prendre un nombre aléatoire e dans l’intervalle [1, φ(N )].
3: Si pgcd(e, φ(N )) 6= 1 alors
4: Aller à l’étape 2.
5: Sinon
6: Calculer d ≡ e−1 (mod φ(N )).
7: Fin Si

Cette fonction est définie pour tout entier n ≥ 2. Si la décomposition en facteurs

premiers est
Y s
n= pxi i ,
i=1

alors on a : s
Y
φ(n) = pxi i −1 (pi − 1).
i=1

Maple 1.1.4.
Dans Maple 12, la fonction φ est tout simplement phi. Attention, pour calculer
φ(N ), Maple est obligé de factoriser N , ce qui peut être très difficile si N est du
type module de RSA.
Programme Commentaires

with(numtheory): <--- Package numtheory "Théorie des Nombres"

N:=5*8*61: <--- un exemple simple
phi(N); <--- Calcul de phi(n)
La réponse est immédiate : 960.
Magma 1.1.5.
Dans Magma, la fonction φ est tout simplement EulerPhi. Attention, pour calculer
φ(N ), Magma aussi est obligé de factoriser N , ce qui peut être très difficile si N est
du type module de RSA.
Programme Commentaires

N:=5861: <--- un exemple simple

EulerPhi(N); <--- Calcul de phi(N)
Maple 1.1.6.
1.1. PRINCIPE DE RSA 7

Avec Maple 12, l’algorithme 2 peut être écrit comme ceci où on suppose que la
procédure 1.1.1 a été exécutée.
Programme Commentaires

phi:=(p-1)*(q-1): <--- L’indicateur d’Euler

e:=rand(3..phi/2)(): <--- On choisit un exposant e aléatoire
while(gcd(e,phi) <> 1) do <--- il faut que pgcd(e,phi)=1
e:=rand(3..phi)(); <--- On reprend un autre exposant e
od;
d := modp(1/e, phi); <--- d est l’inverse de d modulo phi
Magma 1.1.7.
Avec Magma, l’algorithme 2 peut être écrit comme ceci.
Programme Programme

t:=102; <-- Taille du module

x1:=Round(2.0^(t/2)); <-- Valeur aléatoire
x2:=Round(2.0^((t+1)/2)); <-- Valeur aléatoire
m1:=Random(x1,x2); <-- Valeur aléatoire
p:=NextPrime(m1); <-- Premier nombre premier
m2:=Random(x1,x2); <-- Valeur aléatoire
q:=NextPrime(m2); <-- deuxième nombre premier
N:=p*q; <-- Module RSA
N; <-- Valeur de N
phi:=(p-1)*(q-1); <-- phi
e:=Random(3,Round(phi/2)); <-- Un exposant public aléatoire
while(GCD(e,phi) gt 1) do <-- procédure de recherche
e:=Random(3,Round(phi/2)); <-- GCD(e,phi)=1
end while; <--
d:= InverseMod(e,phi); <-- Inverse de e modulo phi
d; <-- Valeur de l’exposant privé

1.1.3 Envoi d’un message

Supposons maintenant que les intervenants A et B possèdent chacun son module
RSA et ses clés, NA , eA , dA pour A et NB , eB , dB pour B.
Si A veut envoyer un message à B, il peut procéder comme dans l’algorithme 3.

Maple 1.1.8.
8 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

Algorithme 3 : Chiffrement d’un message

Entrée : Un message clair et la clé publique (NB , eB ).
Sortie : Un message chiffré C.
1: Transformer le message en un nombre entier M de l’intervalle [2, NB ].
2: Calculer C ≡ M eB (mod NB ).
3: Envoyer le message C.

Avec Maple 12, l’algorithme 3 peut être programmé de la façon suivante.

Programme Commentaires

M:=12345: <--- un exemple simple de message

C:=modp(M&^e,N): <--- &^ permet de calculer M^e modulo N
Magma 1.1.9.
Avec Magma, l’algorithme 3 peut être programmé de la façon suivante.
Programme Commentaires

M:=12345; <--- un exemple simple de message

C:=Modexp(M,e,N); <--- Fonction pour calculer M^e modulo N

1.1.4 Déchiffrement d’un message

Supposons enfin que B a reçu un message chiffré C de la part de A. Alors B peut le
déchiffrer en utilisant sa clé secrète dB comme dans l’algorithme 4.

Algorithme 4 : Déchiffrement d’un message

Entrée : Un message chiffré C et la clé privée (NB , dB ).
Sortie : Un message clair M .
1: Calculer M ≡ C dB (mod NB ).
2: Transformer le nombre M en un message clair.

Maple 1.1.10.
Avec Maple 12, l’algorithme 4 qui permet de déchiffrer un message C peut être le
suivant.
Programme Commentaires

M2:=modp(C&^d,N): <--- Calcul de C^d modulo N

M-M2 <--- Permet de vérifier que M2=M
1.1. PRINCIPE DE RSA 9

Magma 1.1.11.
Avec Magma, l’algorithme 4 qui permet de déchiffrer un message C peut être le
suivant.
Programme Commentaires

M2:=Modexp(C,d,N); <--- Calcul de C^d modulo N

M-M2; <--- Permet de vérifier que M2=M

1.1.5 Signature d’un message

Supposons que A veut envoyer un message M à B. Comment B peut-il être sûr que
le message reçu a bien été envoyé par A. Pour résoudre ce problème, RSA peut être
utilisé aussi bien pour transmettre un message que pour le signer.
Pour cela, A et B doivent avoir chacun ses clés publiques et privées, NA , eA , dA pour
A et NB , eB , dB pour B.
Tout d’abord, A utilise la clé publique (NB , eB ) de B pour transmettre le message
C et produire une signature S du message à l’aide de sa propre clé privée (NA , eA ).
En effet, A doit produire et transmettre C et S comme ceci (voir algorithme 5).

C ≡ M eB (mod NB ), S = C dA (mod NA ).

En possession du message chiffré C et de la signature S, B peut alors vérifier si c’est

bien A qui a transmit ce message en utilisant la clé publique (NA , eA ) de A, du fait
de la relation (voir algorithme 6).
e
S eA ≡ C dA A ≡ C dA eA ≡ C (mod NA ).

En effet, seul A peut produire la signature S et donc B peut aisément vérifier si la

signature S donne une deuxième fois le message chiffré C.

Algorithme 5 : Signature d’un message

Entrée : Un message clair M , deux clés publiques (NB , eB ) et (NA , eA ) et une clé
privée (NA , dA ).
Sortie : Un message chiffré C et sa signature S.
1: A transforme le message en un nombre entier M de l’intervalle [2, NB ].
2: A calcule C ≡ M eB (mod NB ).
3: A calcule S ≡ C dA (mod NA ).
4: A transmet le message C et la signature S.
10 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

Maple 1.1.12.
Avec Maple 12, l’algorithme 5 qui permet de chiffrer et signer un message C peut
être le suivant.
Programme Commentaires

NA:=1577801413: <--- Module RSA de A

eA:=147944791: <--- Clé publique de A
dA:=295049071: <--- Clé privée de A
NB:=1303570001: <--- Module RSA de B
eB:=902841103: <--- Clé publique de B
dB:=1208086831: <--- Clé privée de B
M:=12345: <--- Un exemple simple de message clair
C:=modp(M&^eB,NB): <--- Le message chiffré
S:=modp(C&^dA,NA): <--- La signature du message

Magma 1.1.13.
Avec Magma, l’algorithme 5 qui permet de chiffrer et signer un message C peut être
le suivant.
Programme Commentaires

NA:=1577801413; <--- Module RSA de A

eA:=147944791; <--- Clé publique de A
dA:=295049071; <--- Clé privée de A
NB:=1303570001; <--- Module RSA de B
eB:=902841103; <--- Clé publique de B
dB:=1208086831; <--- Clé privée de B
M:=12345; <--- Un exemple simple de message clair
C:=Modexp(M,eB,NB); <--- Le message chiffré
S:=Modexp(C,dA,NA); <--- La signature du message
L’algorithme de la vérification de la signature est alors l’algorithme 6.

Algorithme 6 : Vérification d’une signature

Entrée : Un message chiffré C, une signature S, la clé publique (NA , eA ).
Sortie : Vérification d’une signature.
1: B calcule C 0 ≡ S eA (mod NA ).
2: Si C 0 = C la signature est authentifiée.

Maple 1.1.14.
1.1. PRINCIPE DE RSA 11

Avec maple 12, on peut alors vérifier la signature avec un programme simple.
Programme Commentaires

C2:=modp(S&^eA,NA): <--- calcul de S^eA modulo NA

dif:=C2-C: <--- Difference des messages
if dif=0 then <--- vérification de la signature
print(’Signature valide’)
else
print(’Signature non valide’)
end if
Magma 1.1.15.
Avec Magma, on peut alors vérifier la signature avec un programme simple.
Programme Commentaires

C2:=Modexp(S,eA,NA); <--- Calcul de S^eA modulo NA

dif:=C2-C; <--- Difference des messages
if dif eq 0 then <--- Vérification de la signature
print("Signature valide");
else
print("Signature non valide");
end if

1.1.6 Preuve de RSA

La justesse du cryptosystème RSA qu’un message chiffré C à partir d’un message
clair M redonne bien le message original M est basée sur le théorème suivant, dû à
Euler.
Théorème 1.1.16 (Euler). Soit N un nombre entier et φ(N ) l’indicateur d’Euler.
Si a est un entier premier avec N , alors

aφ(N ) ≡ 1 (mod N ).

Démonstration. Par définition, on a φ(N ) = # {a | 0 ≤ a ≤ N − 1, pgcd(a, N ) = 1},

ce qui montre qu’on peut écrire

{a | 0 ≤ a < N, pgcd(a, N ) = 1} = a1 , a2 , · · · , aφ(N ) , a1 < a2 < · · · < aφ(N ) < N .

Soit a un entier tel que pgcd(a, N ) = 1. On considère maintenant l’ensemble

aa1 , aa2 , · · · , aaφ(N ) ,
12 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

où x̄ désigne la réduction de x modulo N . Si aai = aaj , alors a(ai −aj ) ≡ 0 (mod N ),
et donc ai = aj puisque pgcd(a, N ) = 1 et |ai − aj | < N . Ainsi, on a

a1 , a2 , · · · , aφ(N ) = aa1 , aa2 , · · · , aaφ(N ) .

En formant les produits des éléments de ces deux ensembles, on obtient :

φ(N ) φ(N ) φ(N )
Y Y Y
φ(N )
ai = aai ≡ a ai (mod N ).
i=1 i=1 i=1

Qφ(N )
De plus, pour chaque i, on a pgcd(ai , N ) = 1. Donc le produit i=1 ai est inversible
modulo N , ce qui donne
aφ(N ) ≡ 1 (mod N ).

1.2 Un exemple d’utilisation de RSA

Dans cette section, on donne le détail de l’utilisation du cryptosystème RSA sur un
exemple concret. En effet, on montre comment chiffrer, transmettre et déchiffrer le
message suivant :

Cette semaine, je suis à Oujda. Je pars le 22 mai à 13h

1.2.1 Transformation d’un texte en nombres

Il y a plusieurs façon de réaliser une correspondance entre les lettres de l’alphabet
et des valeurs numériques. On peut par exemple faire correspondre la valeur 1 à la
lettre a, la valeur 2 à la lettre b,..., et la valeur 26 à la lettre z et travailler ainsi en
mode 27. Cette correspondance peut ne pas être pratique sur des textes très longs.
Une autre façon, plus efficace est d’utiliser la correspondance ASCII (American
Standard Code for Information Interchange). ASCII est la norme d’encodage infor-
matique des caractères alphanumériques de l’alphabet latin. Dans la table ci-dessous,
on a représenté quelques correspondances.

Caractère a A b z 0 1 2 ”espace” à +
Code 097 065 098 122 048 049 050 32 224 43

Maple 1.2.1.
1.2. UN EXEMPLE D’UTILISATION DE RSA 13

Dans Maple 12, la fonction qui transforme un caractère en valeur numérique est
convert(”texte en caractères”, bytes). Inversement, la fonction qui transforme
une liste de valeurs numériques en texte est convert([v1,v2,...,vn],bytes).
Programme Commentaires

liste:=convert("123 abc...z", bytes) <--- liste = [49, 50, 51, 32,

97, 98, 99, 46,
46, 46, 122]
convert(liste, bytes) <--- "123 abc...z"

Magma 1.2.2.
Dans Magma, la fonction qui transforme un caractère en valeur numérique est Bi-
naryString(”texte en caractères”) ou BString(”texte en caractères”). In-
versement, la fonction qui transforme un code ASCII n en caractère est CodeToS-
tring(n). Voici un exemple
Programme Programme

s:="Je suis à c^
oté" ; <--- Le texte
s; <--- Son affichage
t:=BString(s); <--- Transformation en code ASCII
t; <--- On obtient [74, 101, ..., 169]
l:=#t; <--- Longueur de la liste
u:=CodeToString(t[1]); <--- Transformation en texte
for i:=2 to l do <--- Formation du texte
u:=u*CodeToString(t[i]);
end for;
u; <--- Affichage du texte Je suis à c^
oté

1.2.2 L’exemple
Dans cette partie, on exécute en détail un exemple de l’utilisation du cryptosystème
RSA. On va chiffrer, puis déchiffrer le message suivant

Cette semaine, je suis à Oujda. Je pars le 22 mai à 13h

On commence écrire le programme qui sera exécuté par Maple. La fonction seq
permet de créer une liste de valeurs et la fonction nops(liste) donne le nombre de
termes dans son argument (liste).

Maple 1.2.3.
14 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

Programme

retart:
t := 100:
x1 := round(2.0^((1/2)*t)):
x2 := round(2.0^((t+1)*(1/2))):
m1 := (rand(x1 .. x2))():
p := nextprime(m1):
m2 := (rand(x1 .. x2))():
q := nextprime(m2):
N := p*q:
phi := (p-1)*(q-1):
e := (rand(3 .. phi))():
while gcd(e, phi) <> 1 do e := (rand(3 .. phi))() end do:
d := modp(1/e, phi):
message:="Cette semaine, je suis à Oujda. Je pars le 22 mai à 13h":
listeclaire:= convert(message, bytes):
listecrypte:=[seq(modp(listeclaire[k]&^e,N),k=1..nops(listeclaire))]:
listedecrypte:=[seq(modp(listecrypte[k]&^d,N),k=1..nops(listecrypte))]:
messageoriginale:=convert(listedecrypte, bytes):
listeclaire-listedecrypte;
La dernière ligne permet de vérifier que le message de départ et le message décrypté
sont identiques. La différence listeclaire-listedecrypte doit donner une liste de zéros.

Magma 1.2.4.

Programme

t:=100;
x1:=Round(2.0^(t/2));
x2:=Round(2.0^((t+1)/2));
m1:=Random(x1,x2);
p:=NextPrime(m1);
m2:=Random(x1,x2);
q:=NextPrime(m2);
N:=p*q;
phi:=(p-1)*(q-1);
e:=Random(3,Round(phi/2));
while(GCD(e,phi) gt 1) do
e:=Random(3,Round(phi/2));
end while;
1.3. CRYPTANALYSES ÉLÉMENTAIRES DE RSA 15

d:= InverseMod(e,phi);
message:="Cette semaine, je suis à Oujda. Je pars le 22 mai à 13h";
listeclaire:= BString(message);
l:=#listeclaire;
listecrypte:= AssociativeArray();
for k:=1 to l do
listecrypte[k]:=Modexp(listeclaire[k],e,N);
end for;
listedecrypte:= AssociativeArray();
for k:=1 to l do
listedecrypte[k]:=Modexp(listecrypte[k],d,N);
end for;
u:=CodeToString(listedecrypte[1]);
for i:=2 to l do
u:=u*CodeToString(listedecrypte[i]);
end for;
u;

1.3 Cryptanalyses élémentaires de RSA

Dans cette partie, on présente quelques attaques élémentaires sur le cryptosystème
RSA, qui consistent à factoriser le module.

1.3.1 Cryptanalyse de RSA connaissant ϕ(N )

Proposition 1.3.1. Soit N un module RSA. Si on connait ϕ(N ), alors on peut

factoriser N .

Démonstration. Supposons que ϕ(N ) est connu. Ainsi, on dispose d’un système de
deux équations en p et q :

pq = N,
p + q = N + 1 − ϕ(N ),

qui donnent l’équation en p :

p2 − (N + 1 − ϕ(N ))p + N = 0.
16 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

On obtient ainsi
p
(N + 1 − ϕ(N ))2 − 4N
N + 1 − ϕ(N ) +
p = ,
p 2
N + 1 − ϕ(N ) − (N + 1 − ϕ(N ))2 − 4N
q = .
2

Maple 1.3.2.
Avec Maple 12, cette attaque peut être programmée comme dans l’exemple suivant
où on utilise la fonction solve qui permet de résoudre une équation.
Programme Commentaires

p := 67676767676789: <--- Le premier nombre premier

q := 33838383838463: <--- Le deuxième nombre premier
N := p*q: <--- Le module RSA
ph := (p-1)*(q-1): <--- L’indicateur d’Euler
eq:=x^2-(N+1-ph)*x+N: <--- L’équation
solve(eq); <--- Résolution de l’équation
67676767676789, 33838383838463 <--- Les deux solutions
Magma 1.3.3.
Avec Magma, cette attaque peut être programmée comme dans l’exemple suivant
où on utilise la fonction Roots qui permet de résoudre une équation.
Programme
Commentaires
P<x> := PolynomialRing(IntegerRing());
p := 67676767676789; <--- Le premier nombre premier
q := 33838383838463; <--- Le deuxième nombre premier
N := p*q; <--- Le module RSA
ph := (p-1)*(q-1); <--- L’indicateur d’Euler
A:=x^2-(N+1-ph)*x+N; <--- L’équation
Roots(A); <--- Résolution de l’équation
[ <33838383838463, 1>, <--- Les deux solutions
<67676767676789, 1> ]

1.3.2 Utilisation du même module et deux exposants différents

Proposition 1.3.4. Soit N un module RSA. Soient e1 et e2 deux exposants premiers
entre eux. Si un message clair M est chiffré avec e1 et e2 , alors on peut calculer M .
1.3. CRYPTANALYSES ÉLÉMENTAIRES DE RSA 17

Démonstration. Soient C1 et C2 deux messages chiffrés par

C1 ≡ M e 1 (mod N ),
C2 ≡ M e 2 (mod N ),

et supposons que C1 et C2 sont rendus publiques. Si pgcd(e1 , e2 ) = 1, alors il existe

deux entiers x1 et x2 tels que xi < 12 ei et vérifiant e1 x1 −e2 x2 = ±1. Ces deux entiers
peuvent être déterminer par l’algorithme d’Euclide. D’autre part, ils vérifient

e1 x2 |e1 x1 − e2 x2 | 1 1
− = = < 2.
e2 x1 x1 e 1 x1 e1 2x1

Ainsi x1 et x2 peuvent être déterminés comme dénominateur et numérateur de l’une

des convergentes de ee12 . Si e1 x1 − e2 x2 = 1, on obtient alors

C1x1 C2−x2 ≡ M e1 x1 M −e2 x2 ≡ M e1 x1 −e2 x2 ≡ M (mod N ),

ce qui donne le message M . Si e1 x1 − e2 x2 = −1, on calcule C1−x1 C2x2 et on obtient

le même résultat.

Maple 1.3.5.
Avec Maple 12, cette attaque peut programmée comme dans l’exemple suivant.
Programme Commentaires

N:=2290072441593672048770535307: <--- Le module RSA

e1:=4543322112211: <--- Le premier exposant publique
e2:=787654321187: <--- Le deuxième exposant publique
igcdex(e1,e2,’x1’,’x2’): <--- L’algorithme d’Euclide
x1;x2; <--- Affichage de x1 et x2
M:=98776655441: <--- Le message clair
C1:=modp(M&^e1,N): <--- Le premier message chiffré
C2:=modp(M&^e2,N): <--- Le deuxième message chiffré
M2:=modp(C1&^x1,N) <--- Produit des deux messages
*modp(C2&^x2,N) mod N:
M2-M: <--- Vérification des messages

Magma 1.3.6.
Avec Maple 12, cette attaque peut programmée comme dans l’exemple suivant.
La fonction XGCD(a,b) retourne trois nombres entiers, g, x et y vérifiant g =
pgcd(a, b) = ax + by.
18 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

Programme Commentaires

N:=2290072441593672048770535307; <--- Le module RSA

e1:=4543322112211; <--- Le premier exposant publique
e2:=787654321187; <--- Le deuxième exposant publique
g,x1,x2:=XGCD(e1,e2); <--- L’algorithme d’Euclide
g;x1;x2; <--- Affichage de g, x1 et x2
M:=98776655441; <--- Le message clair
C1:=Modexp(M,e1,N); <--- Le premier message chiffré
C2:=Modexp(M,e2,N); <--- Le deuxième message chiffré
M2:=Modexp(C1,x1,N) <--- Produit des deux messages
*Modexp(C2,x2,N) mod N;
M2-M; <--- Vérification des messages

1.3.3 Utilisation de modules différents pour le même mes-

sage.
Dans cette attaque, on considère qu’un message M est envoyé un certain nombre
de fois en utilisant plusieurs clés publiques (Ni , ei ). Ce scénario peut se produire
si le même message doit être diffusé à plusieurs destinataires. Cette attaque, due à
Hastad, est basée sur le théorème des restes chinois.
Théorème 1.3.7. Si les entiers N1 , N1 , · · · , Nk sont deux à deux premiers entre
eux, alors le système 

 x = a1 (mod N1 ),
 x = a1 (mod N1 ),

.. ..


 . = .
 x = a (mod N ),
k k
Qk
admet une solution unique modulo N = i=1 Ni . Cette solution est
k
X
x≡ ai pi Mi (mod N ),
i=1

avec pi = N
Ni
et Mi ≡ p−1
i (mod Ni ).

Démonstration. Soit N = ki=1 Ni , pi = NNi et Mi ≡ p−1

Q
i (mod Ni ). Alors, pour
chaque i, 1 ≤ i ≤ k, on a pi Mi ≡ 1 (mod Ni ) et Ni |pj si i 6= j. Ainsi, avec
x ≡ ki=1 ai pi Mi (mod N ), on a pour 1 ≤ i ≤ k, en considérant x modulo Ni :
P

k k
X X pj
x ≡ ai pi Mi + aj pj Mj ≡ ai + aj Mj Ni × ≡ ai (mod Ni ).
j6=i j6=i
Ni
1.3. CRYPTANALYSES ÉLÉMENTAIRES DE RSA 19

Ceci montre que x est solution du système. Si x0 est une autre solution du système
avec 0 ≤ x0 < N , alors pour chaque i, 1 ≤ i ≤ k, on a

x0 − x ≡ 0 (mod Ni ).

Puisque les entiers Ni , 1 ≤ i ≤ k, sont premiers entre deux à deux, alors

x0 − x ≡ 0 (mod N )

Ainsi, puisque |x0 − x| < N , on a x0 = x, ce qui montre l’unicité de la solution.

Maple 1.3.8.
Dans Maple, le théorème des restes chinois est la fonction

chrem([a1 , a2 , · · · , ak ], [N1 , N2 , · · · , Nk ]).

Voici un exemple pour résoudre le système


 x = 1 (mod 101),
x = 2 (mod 103),
x = 3 (mod 201).


Programme Commentaires

x:=chrem([1,2,3],[101,103,201]): <--- Le théorème des restes chinois

x; <--- On obtient x=1482378.

Magma 1.3.9.
Dans Magma, le théorème des restes chinois est la fonction

CRT([a1 , a2 , · · · , ak ], [N1 , N2 , · · · , Nk ]).

Voici un exemple pour résoudre le système


 x = 1 (mod 101),
x = 2 (mod 103),
x = 3 (mod 201).


Programme Commentaires

x:=CRT([1,2,3],[101,103,201]); <--- Le théorème des restes chinois

x; <--- On obtient x=1482378
20 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

Proposition 1.3.10. Soient k ≥ 2 et k modules RSA Ni avec 1 ≤ i ≤ k. Soient

Ci , 1 ≤ i ≤ k, des messages
Qk chiffrés du même message clair M à l’aide du même
e
exposant e. Si m < i=1 Ni alors on peut déterminer le message clair M sans
factoriser les modules.

Démonstration. Supposons que le même message clair M est chiffré k fois par

Ci ≡ M e (mod Ni ),

pour i = 1, · · · , k. Soit N = ki=1 Ni . On peut appliquer le Théorème des Restes

Q
Chinois pour résoudre le système formé des k équations

x ≡ Ci (mod Ni ),

avec x < N . Si on suppose que M e < N , alors x = M e en tant que nombres entiers.
Ainsi
1
M = xe ,
ce qui donne le message clair M .

Maple 1.3.11.
Pour illustrer cette attaque, on teste un exemple avec e = 3 et k = 4 dans Maple.
Programme Commentaires

for i from 1 to 4 do <--- 4 module RSA

N[i]:=nextprime(rand())*nextprime(rand()): aléatoires
end do:
e:=3: <--- e=3
M:=5454321115654321: <--- un message claire
for i from 1 to 4 do <--- 4 messages chiffré
C[i]:=modp(M&^e,N[i]):
end do:
x:=chrem([C[1],C[2],C[3],C[4]], <--- Le théorème
[N[1],N[2],N[3],N[4]]): des restes chinois
M2:=round((x^(1/e))): <--- racine e-ème de x
M2-M; <--- Comparaison de M2 et M

Magma 1.3.12.
Pour illustrer la même attaque avec Magma, on teste le même exemple avec e = 3 et
k = 4. La fonction Random(b) retourne un nombre entier aléatoire de l’intervalle
[0, b].
1.3. CRYPTANALYSES ÉLÉMENTAIRES DE RSA 21

Programme Programme

b:=2^30; <--- Borne pour les nombres premiers

N := AssociativeArray(); <--- Création du tableau N
for i:=1 to 4 do <--- Création de 4 module RSA
N[i]:=NextPrime(Random(b))
*NextPrime(Random(b));
end for;
e:=3; <--- e=3
M:=5454321115654321; <--- Le message claire
C := AssociativeArray(); <--- Création d’un tableau C
for i:=1 to 4 do <--- Création des 4 messages chiffrés
C[i]:=Modexp(M,e,N[i]);
end for;
x:=CRT([C[1],C[2],C[3],C[4]], <--- Théorème Chinois
[N[1],N[2],N[3],N[4]]);
M2:=Round((x^(1/e))); <--- Calcule de x^(1/e)
M2-M; <--- Vérification des messages

1.3.4 Cryptanalyse de RSA si |p − q| < cN 1/4 : Méthode de

Fermat
Dans cette partie, on suppose que les nombres premiers p et q qui forment le module
RSA N = pq sont très proches, plus précisément |p − q| < cN 1/4 où c est une
constante fixe, assez petite.
Théorème 1.3.13. Soit N = pq un modules RSA où les nombres premiers p et q
vérifient |p − q| < cN 1/4 où c est une constante assez petite. Alors on peut factoriser
N en temps polynômial dépendant de c.

Démonstration. La méthode de Fermat consiste en la recherche de deux nombres

entiers x et y tels que
4N = x2 − y 2 = (x + y)(x − y).
Si en plus x − y 6= 2, alors on obtient la factorisation de N en posant
x+y x−y
p= , q= .
2 2
h √ i h √ i
Pour déterminer x et y, on prend pour x les valeurs x0 = 2 N , x1 = 2 N + 1,
h √ i
x2 = 2 N + 2, · · · et on teste si 4N − x2 est un carré parfait. On désigne alors
22 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA
h √ i
par k le nombre entier pour lequel xk = 2 N + k donne la factorisation de N .
Alors xk = p + q et on a, en supposant que |p − q| < cN 1/4 :

h √ i
k = xk − 2 N
h √ i
= p+q− 2 N
√
< p+q−2 N +1
(p + q)2 − 4N
= √ +1
p+q+2 N
(p − q)2
= √ +1
p+q+2 N
√
c2 N
< √ +1
2 N
c2
< + 1.
2

Il en résulte que le nombre de tests est assez petits si c est une constante qui ne
dépend pas de N .

Maple 1.3.14.

On teste maintenant la méthode de Fermat avec Maple 12 sur des modules RSA
N = pq de taille t = 100, avec |p − q| < cN 1/4 . Pour cela, on utilise le programme
suivant qui fabrique deux nombres premiers p et q avec

|p − q| < 10N 1/4 .

Ensuite, on exécute la méthode de Fermat pour retrouver un des nombres premiers

de N .
Programme Commentaires

Digits := 100: <--- Précision des calculs

t := 100: <--- Taille du module
x1 := round(2.0^((1/2)*t)): <--- Borne inférieur pour p
x2 := round(2.0^((t+1)*(1/2))): <--- Borne supérieur pour p
1.3. CRYPTANALYSES ÉLÉMENTAIRES DE RSA 23

m1 := (rand(x1 .. x2))(): <--- Valeur aléatoire

p := nextprime(m1): <--- Nombre premier suivant
m2 := round(p+10*2^(t/4)): <--- Borne inférieur pour q
q := nextprime(m2):
N := p*q: <--- Module RSA
c := trunc(abs(p-q)/N^0.25)+1: <--- Rapport
n := round(2*sqrt(N)): <--- Entier le plus proche
k := 0: <--- Compteur
while k < (1/2)*c^2+1 do <--- Boucle de Fermat
x := n+k: <--- Une valeur pour x
y := round(sqrt(x^2-4*N)): <--- La valeur de y
s := round((x+y)/2): <--- Un candidat pour q
if gcd(s, N) > 1 then <--- pgcd
print(’Un facteur est’, s):
break:
end if:
k := k+1:
end do:
En exécutant ce programme, on a obtenu les résultats suivants.
p=1184367162931181 <--- Un facteur premier
q=1184367498475709 <--- L’autre facteur premier
N=1402725974037575305865967182329 <--- Le module RSA
c=10 <--- c vérifie abs(p-q)<cN^(1/4)
k=24 <--- Le nombre d’itérations
Un facteur est 1184367498475709 <--- Sortie de la procédure

Magma 1.3.15.

On teste ausi la méthode de Fermat avec Magma sur des modules RSA N = pq de
taille t = 100, avec |p − q| < cN 1/4 . Pour cela, on utilise le programme suivant qui
fabrique deux nombres premiers p et q avec

|p − q| < 10N 1/4 .

Ensuite, on exécute la méthode de Fermat pour retrouver un des nombres premiers

de N .
24 CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA

Programme Programme

t := 100; <--- Taille du module

x1 := Round(2^((1/2)*t)); <--- Valeur minimale du nombre premier
x2 := Round(2^((t+1)*(1/2))); <--- Valeur maximale du nombre premier
m1 := Random(x1,x2); <--- Valeur aléatoire
p := NextPrime(m1); <--- Premier nombre premier
m2 := Round(p+10*2^(t/4)); <--- Valeur aléatoire
q := NextPrime(m2); <--- Deuxième nombre premier
N := p*q; <--- Module RSA
c := Truncate(Abs(p-q)/N^0.25)+1; <--- Le rapport Abs(p-q)/N^0.25)+1;
n := Round(2*Sqrt(N))+1; <--- Valeur de départ
k := 0; <--- Initiation
while k lt (1/2)*c^2+1 do <--- Boucle de Fermat
x := n+k; <--- Valeur de x
y := Round(Sqrt(x^2-4*N)); <--- Valeur de y
s := Round((x+y)/2); <--- Valeur candidate pour p
if GCD(s, N) gt 1 then
printf("Un facteur est ");s;
break; <--- Arr^
et de la boucle
end if;
k := k+1;
end while; <--- Fin de la boucle
En exécutant ce programme, on a obtenu les résultats suivants.
p=1320614251431253 <--- Un facteur premier
q=1320614586975679 <--- L’autre facteur premier
N=1744022444208079680278451495787 <--- Le module RSA
c=10 <--- c vérifie abs(p-q)<cN^(1/4)
k=20 <--- Le nombre d’itérations
Un facteur est 1320614586975679 <--- Sortie de la procédure
Chapitre 2

Cryptanalyse de RSA par les

fractions continues

Le coléreux ne peut pas atteindre la gloire et le glorieux ne ressent pas la

colère.
Antara Ibno Shaddad Al Absy
éK. @ñÊªK áÓ Y®m Ì '@ ÉÒm' B ð
I.KQË@ I.ªË@ éªJ.£ áÓ CªË@ ÈAJK B
úæJ.ªË@ X@ Y áK. @ èQJ«

2.1 Les fractions continues

2.1.1 Introduction
√
On considère le nombre x = 3+ 10 ≈ 6.162277..., solution de l’équation x2 −6x−1.
On peut alors écrire x2 = 6x + 1 et donc x = 6 + x1 . En recommençant le processus,
on obtient
1
x=6+ ,
1
6+
1
6+
1
6+
···
Une telle fraction, qui peut être
√ finie, s’appelle une fraction continue,
√ ici, c’est la
fraction continue de x = 3 + 10. On note plus simplement 3 + 10 = [6, 6, 6, · · · ].
On peut aussi prendre un nombre fini d’éléments 6. On obtient ainsi
1 37
[6] = 6, [6, 6] = 6 + = ≈ 6, 166666...,
6 6
25
26CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

1 228
[6, 6, 6] = 6 + = ≈ 6.162162...,
1 37
6+
6

1 1405
[6, 6, 6, 6] = 6 + = ≈ 6.162280...,
1 228
6+
1
6+
6
Chacune des fractions 6, 37 , 228 , 1405 , · · · s’appelle une réduite ou convergentes. On
6 37 228
observe que ces fractions vérifient

37 228 1405
|6 − x| > −x > −x > −x .
6 37 228

Ceci est une des nombreuses propriétés des fractions continues.

2.1.2 Définitions et propriétés

Théorème 2.1.1. Tout nombre réel positif x a une écriture unique comme fraction
continue :
1
x = a0 + = [a1 , a2 , a3 , · · · ],
1
a1 +
1
a2 +
1
a3 +
..
.
où les ai sont des entiers positifs. De plus, la fraction continue est finie si et seule-
ment si le nombre x est rationnel.

Démonstration. Soit x un nombre réel positif. On pose x0 = x. On considère la

partie entière a0 = [x0 ]. Si x0 est un entier, a0 = x0 et la fraction continue de x est
x = [a0 ].
1
Supposons que x n’est pas un entier. Dans ce cas, on a 0 < x0 − a0 < 1 et x0 −a0
> 1.
Puisque x0 = a0 + (x0 − a0 ), on définie x1 par

1
x1 = > 1,
x 0 − a0
ce qui donne
1
x 0 = a0 + .
x1
2.1. LES FRACTIONS CONTINUES 27

On recommence le processus pour x1 . On a a1 = [x1 ]. Si x1 est un nombre entier,

alors a1 = x1 , et la fraction continue de x est

1 a0 + a1
x = a0 + = ,
a1 a1

qui représente un nombre rationnelle. Si x1 , n’est pas un entier, en recommence le

processus en définissant x2 par

1
x2 = > 1,
x 1 − a1

ce qui donne
1
x 0 = a0 + .
1
a1 +
x2
Ce processus s’arrête au rang n si et seulement si an = [xn ], avec an ≥ 1, et dans ce
cas, la fraction continue de x est

1
x = a0 + = [a1 , a2 , a3 , · · · , an ],
1
a1 +
1
a2 +
1
a3 +
.. 1
.+
an

qui représente un nombre rationnel. Si x est un nombre irrationnelle, le processus

continue indéfiniment et on obtient pour x une fraction continue infinie :

x = [a1 , a2 , a3 , · · · ].

Définition 2.1.2. Soit [a1 , a2 , a3 , · · · ] une fraction continue d’un nombre x.

1. Les nombres entiers ai s’appellent les quotients partiels.
2. Les nombres rationnels [a1 , a2 , a3 , · · · , ak ] s’appellent les réduites de x.

Maple 2.1.3.
Avec le logiciel Maple, la fonction qui calcule la fraction continue d’un nombre x est
est cfrac(x,n,’quotients’) : n est le nombre de quotients partiels et ’quotients’ pour
afficher la fraction continue sous la forme [a0 , a1 , a2 , · · · , an ], ce qui correspond à la
1
notation standard. Voici un exemple pour calculer la fraction continue de x = 1+7 3 .
28CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

Programme Commentaire

restart: <--- Remise à zéro

with(numtheory): <--- Fonctionnalités "Théorie des Nombres"
Digits:=100: <--- Précision
x:=1+7^(1/3): <--- Un nombre réel
n:=30: <--- nombre de quotients partiels
s:=cfrac(x,n,’quotients’): <--- Calcul de la fraction continue
s; <--- s=[2,1,10,2,16,....]
Magma 2.1.4.
Avec le logiciel Magma, la fonction qui calcule la fraction continue de x = 1 +
1
7 3 est ContinuedFraction(x). Magma donne alors la forme x = [a1 , a2 , · · · ], est
commence donc avec a1 .
Programme Commentaire

x:=1+7^(1/3); <--- Déclaration de x=1+7^(1/3)

print(x); <--- Valeur décimal de x
s:=ContinuedFraction(x); <--- Liste des quotients partiels
s; <--- Affichage de la liste
Pour un nombre x dont la fraction continue est [a0 , a1 , a2 , · · · ], on peut facilement
calculer les premières convergentes :
p0
[a0 ] = a0 = .
q0
1 a0 a1 + 1 p1
[a0 , a1 ] = a0 + = = .
a1 a1 q1
1 a0 a1 a2 + a0 + a2 p2
[a0 , a1 , a2 ] = a0 + = = .
1 a1 a2 + 1 q2
a1 +
a2
On observe facilement que
p2 = a2 (a0 a1 + 1) + a0 = a2 p1 + p0 ,
q 2 = a2 a1 + 1 = a2 p 1 + q 0 .
Ceci est une propriété générale des convergentes d’un nombre réel.
Théorème 2.1.5. Soit [a0 , a1 , a2 , · · · ] la fraction continue de x. Pour tout n ≥ 0,
on définit les nombres pn et qn par,
pn = an pn−1 + pn−2 ,
qn = an qn−1 + qn−2 ,
2.1. LES FRACTIONS CONTINUES 29

avec la convention

p−2 = 0, q−2 = 1, p−1 = 1, q−1 = 0.

pn
Alors tout n ≥ 0, on a qn
= [a0 , a1 , a2 , · · · , an ].

p0
Démonstration. La preuve se fait par récurrence sur n. On a déjà vu que [a0 ] = q0
.
Supposons que

pn = an pn−1 + pn−2 ,
qn = an qn−1 + qn−2 ,

pn
et que [a1 , a2 , a3 , · · · , an ] = qn
. Alors, on a aussi, en utilisant la récurrence.

1
[a1 , a2 , a3 , · · · , an , an+1 ] = [a1 , a2 , a3 , · · · , an + ]
an+1

1
an + an+1 pn−1 + pn−2
=
1
an + an+1 qn−1 + qn−2
(an an+1 + 1) pn−1 + an+1 pn−2
=
(an an+1 + 1) qn−1 + an+1 qn−2
an+1 (an pn−1 + pn−2 ) + pn−1
=
an+1 (an qn−1 + qn−2 ) + qn−1
an+1 pn + pn−1
=
an+1 qn + qn−1
pn+1
= ,
qn+1

et la récurrence est démontrée. Ceci termine la preuve.

Maple 2.1.6.

Avec Maple, la fonction qui détermine les convergentes est nthconver : la n + 1-

ème convergente d’une liste s de convergente est nthconver(s,n). Le numérateur et
le dénominateur sont alors nthnumer(s,n) et nthdenom(s,n). Voici un exemple
1
dans lequel on cherche la convergente pq77 de x = 1 + 7 3 .
30CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

Proramme Commentaires

restart: <--- Remise à zéro

with(numtheory): <--- Fonctionnalités "Théorie des Nombres"
Digits:=100: <--- Précision
x:=1+7^(1/3): <--- Un nombre réel
s:=cfrac(x,100,’quotients’): <--- s=[2,1,10,2,...]
n:=7: <--- On considère la 8-ème convergentes
nthconver(s,n); <--- La convergente d’indice 7
nthnumer(s,n); <--- Son numérateur est 15791
nthdenom(s,n); <--- Son dénominateur 5421

Magma 2.1.7.

Avec Magma, pour calculer la convergente pqnn , il faut utiliser la fonction Conver-
gents(s) où s = [a1 , a2 , · · · , an ]. La réponse est alors une matrice de la forme

pn pn−1
.
qn qn−1

Programme Commentaires

x:=1+7^(1/3); <--- La valeur x=1+7^(1/3)

c:=ContinuedFraction(x); <--- La liste des quotients partiels
c; <--- Affichage de la liste
s:=[]; <--- Initialisation
n:=7; <--- Convergente p7/q7
for i in [1..n] do <--- Formation de [a1,...,a7]
s:=Append(s,c[i]);end for;
s; <--- Affichage de [a1,...,a7]
t:=Convergents(s); <--- Matrice ([p7,p6],[q7,q6])
t[1,1]; <--- p7
t[2,1]; <--- q7
La réponse est p7 = 3379 et q7 = 1160.
Dans magma, on peut aussi écrire un programme afin de déterminer la liste des
numérateurs et dénominateurs des convergentes.
2.1. LES FRACTIONS CONTINUES 31

Programme Commentaires

x:=1+7^(1/3); <--- La valeur x

x; <--- Sa valeur décimale
s:=ContinuedFraction(x); <--- Liste des quotients partiels
s; <--- Affichage de la liste
p0:=0;q0:=1;p1:=1;q1:=0; <--- Initialisations
N:=[];D:=[]; <--- Initialisations
l:=15; <--- Longueur de la liste
for i in [1..l] do <--- Boucle
p2:=s[i]*p1+p0; <--- Calcul de p2
q2:=s[i]*q1+q0; <--- Calcul de p2
N:=Append(N,p2); <--- Formation de la liste N
D:=Append(D,q2); <--- Formation de la liste D
p0:=p1;q0:=q1; <--- Echange
p1:=p2;q1:=q2; <--- Echange
end for; <--- Fin de la boucle
N; <--- Affichage de N
D; <--- Affichage de D
n:=7; <--- 7ème convergente
N[n]; <--- Numérateur
D[n]; <--- Dénominateur
La septième convergente est alors p7 = 3379 et q7 = 1160.
Théorème 2.1.8. Soit [a0 , a1 , a2 , · · · ] la fraction continue d’un nombre x. Alors les
convergentes pqnn de x vérifient pour tout n ≥ −2

pn qn+1 − qn pn+1 = (−1)n+1 ,

pn qn+2 − qn pn+2 = (−1)n+1 an+2 .

Démonstration. Les preuves se font aisément par récurrence. Considérons la première

égalité. Pour n = −2, on a bien
p−2 q−1 − q−2 p−1 = −1 = (−1)−2+1 .
Supposons donc que pn−1 qn − qn−1 pn = (−1)n . On a, en utilisant le théorème 2.1.5,
pn qn+1 − qn pn+1 = pn (an+1 qn + qn−1 ) − qn (an+1 pn + pn−1 )
= pn qn−1 − qn pn−1
= −(−1)n
= (−1)n+1 ,
32CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

ce qui démontre la récurrence.

La deuxième égalité s’obtient directement en combinant l’égalité pn qn+1 − qn pn+1 =
(−1)n+1 et le théorème 2.1.5.

pn qn+2 − qn pn+2 = pn (an+2 qn+1 + qn ) − qn (an+2 pn+1 + pn )

= an+2 (pn qn+1 − qn pn+1 )
= an+2 (−1)n+1 .

Ceci prouve donc la deuxième égalité.

Maple 2.1.9.

1
Vérifions ce théorème avec les convergentes de x = 1 + 7 3 .
Programme Commentaires

restart:
with(numtheory):
Digits:=100:
x:=1+7^(1/3):
s:=cfrac(x,100,’quotients’): <--- liste des quotients partiels
nu:=i->nthnumer(s,i): <--- Numérateurs des convergentes
de:=i->nthdenom(s,i): <--- Dénominateurs des convergentes
n:=7; <--- Un indice quelconque
r:=nu(n)*de(n+1)-nu(n+1)*de(n): <--- Première égalité
(-1)^(n+1)-r; <--- Différence (nulle)
n:=10; <--- Un indice quelconque
r:=nu(n)*de(n+2)-nu(n+2)*de(n); <--- Deuxième égalité
(-1)^(n+1)*s[n+3]-r; <--- Différence (nulle)

Magma 2.1.10.

1
On vérifie maintenant le théorème 2.1.8 avec les convergentes de x = 1 + 7 3 pour
n = 7 avec magma. Attention au décalage de l’exposant de −1 puisque Magma
commence les quotients partiels par a1 et non par a0 .
2.1. LES FRACTIONS CONTINUES 33

Programme Programme

x:=1+7^(1/3); <--- Valeur de x

c:=ContinuedFraction(x); <--- Liste des quotients partiels
s:=[]; <--- Initiation
t:=[]; <--- Initiation
l:=20; <--- Nombre de convergentes
for i in [1..l] do <--- Boucle
s:=Append(s,c[i]); <--- Liste s
t:=Append(t,Convergents(s)); <--- Liste des convergentes
end for;
n:=7; <--- n=7
p1:=t[n][1,1];p2:=t[n+1][1,1]; <--- p7 et p8
q1:=t[n][2,1];q2:=t[n+1][2,1]; <--- q7 et q8
p1*q2-p2*q1-(-1)^(n); <--- Vérification, réponse nulle
n:=7;
p1:=t[n][1,1];p3:=t[n+2][1,1]; <--- p7 et p9
q1:=t[n][2,1];q3:=t[n+2][2,1]; <--- q7 et q9
p1*q3-p3*q1-(-1)^(n+2)*c[n+2]; <--- Vérification, réponse nulle
pn
Corollaire 2.1.11. Les convergentes qn
d’un nombre réel x vérifient pgcd(pn , qn ) =
1 pour tout n ≥ 0.

Démonstration. Supposons que pqn+1

n+1
existe. Alors, d’après Théorème 2.1.8, on a
n+1
pn qn+1 − qn pn+1 = (−1) et donc pgcd(pn , qn ) = 1.
p2n
Théorème 2.1.12. La suite des convergentes d’indices pairs q2n
et d’indices impairs
p2n+1
q2n+1
d’un nombre irrationnel positif x vérifient :

p2n−2 p2n p2n+1 p2n−1

< <x< < .
q2n−2 q2n q2n+1 q2n−1
p2n p2n+1
Démonstration. Démontrons d’abord que pour tout n ≥ 0, on a q2n
< q2n+1
. En
effet, en utilisant le théorème 2.1.8

p2n p2n+1 p2n q2n+1 − q2n p2n+1 (−1)2n+1

− = = < 0.
q2n q2n+1 q2n q2n+1 q2n q2n+1
p2n−2 p2n
Démontrons maintenant que pour tout n ≥ 0, on a q2n−2
< q2n
. On a, en utilisant
le théorème 2.1.8 :
p2n−2 p2n p2n−2 q2n − p2n q2n−2 (−1)2n−1 a2n
− = = < 0.
q2n−2 q2n q2n−2 q2n q2n−2 q2n
34CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

On a de même
p2n+1 p2n−1 p2n+1 q2n−1 − p2n−1 q2n+1 −(−1)2n a2n+1
− = = < 0,
q2n+1 q2n−1 q2n+1 q2n−1 q2n+1 q2n−1
p2n+1 p2n−1
ce qui donne q2n+1
< q2n−1
.
Il reste à démontrer que les deux inégalités pq2n 2n
< x et x < pq2n+1
2n+1
. En écrivant x =
[a0 , a1 , a2 , · · · , an , xn+1 ] avec xn+1 = [an+1 , · · · ], on obtient, en utilisant Théorème 2.1.8,
pour tout n ≥ 0 :
pn xn+1 pn + pn−1 pn pn−1 qn − pn qn−1 (−1)n
x− = − = = .
qn xn+1 qn + qn−1 qn qn (xn+1 qn + qn−1 ) qn (xn+1 qn + qn−1 )
p2n p2n+1
Ainsi, on obtient x − q2n
> 0 et x − q2n+1
< 0.

Le corollaire suivant est une conséquence de Théorème 2.1.12

Corollaire 2.1.13. Si [a0 , a1 , a2 , · · · ] est la fraction continue d’un nombre x, alors
les convergentes pqnn de x vérifient :
1. Pour tout n ≥ 0, (qn x − pn )(qn+1 x − pn+1 ) < 0.
2. Pour tout n ≥ 0, |qn+1 x − pn+1 | < |qn x − pn |.

Démonstration. En écrivant x = [a1 , a2 , a3 , · · · , an , xn+1 ] = [a0 , a1 , a2 , · · · , an+1 , xn+2 ]

avec xn+1 = [an+1 , · · · ] et xn+2 = [an+2 , · · · ], on obtient, comme dans la preuve du
théorème 2.1.12, pour n ≥ 0,
(−1)n (−1)n+1
qn x − pn = , qn+1 x − pn+1 = .
xn+1 qn + qn−1 xn+2 qn+1 + qn
ceci montre que qn x−pn et qn+1 x−pn+1 sont de signes contraires et donc la propriété
2.
1
En écrivant xn+1 = an+1 + xn+2
avec xn+2 > 1, on a
an+1 < xn+1 < an+1 + 1.
Ainsi
xn+1 qn + qn−1 < (an+1 + 1)qn + qn−1 = qn+1 + qn < xn+2 qn+1 + qn .
Donc
1 1
> ,
xn+1 qn + qn−1 xn+2 qn+1 + qn
et par conséquent
|qn x − pn | > |qn+1 x − pn+1 |,
ce qui montre la propriété 2.
2.1. LES FRACTIONS CONTINUES 35

pn
Proposition 2.1.14. Si x = [a1 , a2 , a3 , · · · ], alors les convergentes qn
de x vérifient
pour tout n ≥ 0,
pn 1
x− < .
qn qn qn+1

Démonstration. Puisque x = [a0 , a1 , a2 , · · · , an , xn+1 ] avec xn+1 = [an+1 , · · · ], alors

xn+1 > an+1 . Comme dans la preuve de Théorème 2.1.12, pour n ≥ 0, on obtient

pn 1 1 1
x− = < = ,
qn qn (xn+1 qn + qn−1 ) qn (an+1 qn + qn−1 ) qn qn+1
ce qui termine la preuve.

On obtient alors la propriété suivante pour un nombre irrationnel.

Proposition 2.1.15. Si [a0 , a1 , a3 , · · · ] est la fraction continue d’un nombre irra-
tionnel x, alors il existe une infinité de nombres rationnels pq tels que

p 1
x− < 2.
q q

Démonstration. Puisque qn < qn+1 , alors, en utilisant la proposition 2.1.14, on ob-

tient pour toutes les convergents pqnn de x on a

pn 1 1
x− < < 2.
qn qn qn+1 qn
Donc, comme il y a une infinité de convergentes si x est irrationnel, il y a une infinité
de nombres rationnels pq qui vérifient

p 1
x− < 2.
q q

Nous avons aussi un théorème concernant les meilleures approximations.

Théorème 2.1.16 (Meilleurs approximations). Si [a1 , a2 , a3 , · · · ] est la fraction
continue d’un nombre irrationnel x. Soit pqnn une convergente de x avec n ≥ 0 et
p
q
un nombre rationnel.
1. Si q < qn+1 , alors |qn x − pn | ≤ |qx − p|.
pn p
2. Si q ≤ qn , alors x − qn
≤ x− q
.
36CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

Démonstration. On suppose que 0 < q < qn+1 . Montrons que |qn x − pn | ≤ |qx − p|.
Soit a et b deux entiers tels que

p = apn + bpn+1 ,
q = aqn + bqn+1 .

L’existence de a et b est garantie par le théorème 2.1.8. En effet, on a pn qn+1 −

pn+1 qn = (−)n+1 et donc

a = (−1)n+1 (pqn+1 − qpn+1 ), b = (−1)n+1 (qpn − pqn ).

On peut discuter les valeurs de p et q suivant les valeurs de a et b.

- Si a = 0, alors q = bqn+1 , donc b ≥ 1, ce qui contredit 0 < q < qn+1 .
pn p
- Si b = 0, alors p = apn et q = aqn , ce qui donne x − qn
= x− q
.
- Supposons donc que ab 6= 0. Puisque q < qn+1 , alors aqn + bqn+1 < qn+1 et donc
aqn < (1 − b)qn+1 , ce qui montre que b ≥ 1 et a < 0 ou b ≤ −1 et dans ce cas, on
doit avoir q = aqn + bqn+1 > 0, donc a > 0. Dans les deux cas, ab < 0. On a alors

qx − p = (aqn + bqn+1 )x − (apn + bpn+1 ) = a(qn x − pn ) + b(qn+1 x − pn+1 ),

où les termes a(qn x − pn ) et b(qn+1 x − pn+1 ) sont de même signe. Alors

|qx − p| = |a(qn x − pn )| + |b(qn+1 x − pn+1 )| ≥ |qn x − pn |.

Ceci termine la preuve de 1.

De plus, si on a q ≤ qn , alors
p |qx − p| |qn x − pn | pn
x− = ≥ = x− ,
q q qn qn
et termine la preuve de 2.

On a déjà vu dans la proposition 2.1.15 que pour n ≥ 0, les convergentes d’un

nombre réel x vérifient
pn 1
x− < 2.
qn qn
En fait, le résultat suivant est encore plus précis.
Proposition 2.1.17. Si [a0 , a1 , a2 , · · · ] est la fraction continue d’un nombre x, alors
pour n ≥ 0, on a
pn 1 pn+1 1
x− < 2 ou x− < 2 .
qn 2qn qn+1 2qn+1
2.2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES 37

Démonstration. On sait par le corollaire 2.1.13 que x − pqnn et x − pqn+1

n+1
sont de signes
contraires. Alors
pn pn+1 pn pn+1
− = x− + x−
qn qn+1 qn qn+1
Or, en utilisant le théorème 2.1.8 et l’inégalité 2qn qn+1 < qn2 + qn+1
2
, on obtient :
pn pn+1 1 1 1
− = < 2 + 2 .
qn qn+1 qn qn+1 2qn 2qn+1
Ainsi
pn pn+1 1 1
x− + x− < 2 + 2 .
qn qn+1 2qn 2qn+1
pn 1 pn+1 1
Ceci montre alors que x − qn
< 2
2qn
ou x − qn+1
< 2
2qn+1
.

On termine avec le théorème suivant, très utile pour reconnaitre les convergentes
d’un nombre réel.
p
Proposition 2.1.18. Si x est un nombre réel. Si q
est un nombre rationnel qui
vérifie
p 1
x− < 2,
q 2q
p
alors q
est une convergente de x.

Démonstration. Soit pq est un nombre rationnel. Puisque la suite des dénominateurs

(qn ) des convergentes pqnn de x est strictement croissantes, alors qn ≤ q < qn+1 pour un
p 1
entier n ≥ 0. On a alors, en utilisant le théorème 2.1.16 et l’hypothèse x − q
< 2q 2
,

p pn p pn p 1
− ≤ −x + x− ≤2 x− < 2
q qn q qn q q
Il en résulte que
qn
|pqn − pn q| < ≤ 1.
q
p pn
Ainsi, pqn − pn q = 0 et donc q
= qn
.

2.2 Cryptanalyse de RSA par les fractions conti-

nues
Dans cette partie, nous considérons deux attaques basées sur l’utilisation des frac-
tions continues. La première est due à Wiener (1990).
38CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

2.2.1 L’attaque de Wiener

Théorème 2.2.1. Soit N = pq un module RSA où les nombres premiers p et q
sont de même taille (q < p < 2q). Soit e < φ(N ) un exposant public pour lequel la
1
clé secrète d est assez petite : d < 13 N 4 . Connaissant N et e, on peut calculer d et
factoriser N .
√
Démonstration. Supposons que q < p < 2q. Puisque N = pq > q 2 , alors q < N .
D’autre part, on a
√
N − ϕ(N ) = p + q − 1 < 2q + q − 1 < 3q < 3 N .
Si e est une clé publique et d la clé privée, alors d ≡ e−1 (mod φ(N )), où φ(N ) est
l’indicateur d’Euler. Donc il existe un entier k tel que ed − kϕ(N ) = 1. Puisque
e < φ(N ), on peut donc écrire
ed − 1 ed
k= < < d.
φ(N ) φ(N )
Alors
e k |ed − kN |
− =
N d Nd
|ed − kϕ(N ) − kN + kϕ(N )|
=
Nd
|1 − k(N − ϕ(N ))|
=
Nd
k(N − ϕ(N ))
<
√ Nd
3k N
<
Nd
3k
= √ .
d N
1
Puisque k < d < 13 N 4 , alors
1
3k N4 1 1
√ < √ = 1 < .
d N d N dN 4 2d2
Ainsi, en appliquant le théorème 2.1.5, kd est une convergente de e
N
. Connaissant d
et k, on peut alors calculer φ(N ) par la relation
ed − 1
φ(N ) = .
k
Ainsi, par la proposition 1.3.1 on peut calculer p et q et donc trouver la factorisatio
de N .
2.2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES 39

L’attaque de Wiener peut donc être résumée dans l’algorithme suivant.

Algorithme 7 : L’attaque de Wiener

Entrée : Un module RSA N et un exposant publique e pour lequel la clé secrète
1
vérifie d < 13 N 4 .
Sortie : La factorisation de N et la clé secrète d.
1: Déterminer la liste des réduites de Ne .
1
2: Pour chaque réduite xy telle que y < 13 N 4 :
√
ey−1 2 (N +1−ψ+ δ)
3: Calculer ψ = x , δ = (N + 1 − ψ) − 4N , et p2 = 2
.
4: Si pgcd(p2 , N ) > 1 alors
N
5: Afficher d = y, p = p2 et q = p2
.
6: Fin Si

Maple 2.2.2.
Programme Commentaire

n:=100:Digits:=100:with(numtheory) <-- Initiations

x:=rand(2^(n/2-1)..2^(n/2))(): <-- Une Valeur aléatoires
p:=nextprime(x): <-- Le nombre premier p
y:=rand(round(x/2)..x)(): <-- Condition q<p<2q
q:= nextprime(y): <-- Le nombre premier q
evalf(p/q): <-- La condition 1<p/q<2
N:=p*q: <-- Le module RSA
ph:=(p-1)*(q-1): <-- L’indicateur d’Euler
sn:=trunc(1/3*(N^(1/4))): <-- La borne de Wiener
d:=rand(sn)(): <-- Une clé privée aléatoire
while gcd(d,ph)>1 do <-- d est premier avec ph
d:=rand(sn)() end do:
e:=1/d mod ph: <-- La clé publique
convert(e/N,confrac,’pq’ ): <-- pq est la liste des réduites
g:=1:i:=2: <-- Initiation
while g=1 do <-- Boucle
y:=denom(pq[i]): <-- Dénominateur de la réduite
x:=numer(pq[i]): <-- Numérateur de la réduite
psi:=(e*y-1)/x: <-- la valeur psi
delta:=(N+1-psi)^2-4*N:
p2:=((N+1-psi)+sqrt(delta))/2: <-- Solution de l’équation
p2:=round(p2):
g:=gcd(p2,N): <-- calcul de pgcd(p2,N)
40CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

i:=i+1:
od:
print(‘d=‘):y; <-- Affichage de d
print(‘p=‘):p; <-- Affichage de p
print(‘q=‘):N/p2; <-- Affichage de q

Magma 2.2.3.
On vérifie maintenant l’attaque de Wiener avec un module RSA de n = 80 bits.
Programme Commentaire

n:=80; <-- Longeur du module RSA

a:=Round(2^(n/2-1)); <-- Borne inférieure
b:=Round(2^(n/2)); <-- Borne supérieure
x:=Random(a,b); <-- Valeur aléatoire
p:=NextPrime(x); <-- Nombre premier
a:=Round(x/2); <-- Borne inférieure
b:=Round(x); <-- Borne supérieure
y:=Random(a,b); <-- Valeur aléatoire
q:=NextPrime(y); <-- Nombre premier
N:=p*q; <-- Module RSA
ph:=(p-1)*(q-1); <-- Phonction d’Euler
sn:=Truncate(1/3*(N^(1/4))); <-- Borne de Wiener
d:=Random(sn); <-- valeur aléatoire
while (GCD(d,ph) gt 1) do <-- d,phi(N) premiers entre eux
d:=Random(sn); end while;
e:=Modinv(d,ph); <-- Inverse de d
c:=ContinuedFraction(e/N); <-- Liste des quotients partiels
s:=[]; <-- Initialisation
t:=[]; <-- Initialisation
l:=#c; <-- Longuer de c
for i in [1..l] do <-- Fabrication des listes
s:=Append(s,c[i]); <-- quotients partiels
t:=Append(t,Convergents(s)); <-- convergentes
end for;
i:=3; <-- Initialisation
g:=1; <-- Initialisation
while (g eq 1) do <-- Boucle de Wiener
kk:=t[i][1,2]; <-- Valeur de k
dd:=t[i][2,2]; <-- Valeur de d
phn:=(e*dd-1)/kk; <-- Valeur phn=(e*dd-1)/kk
2.2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES 41

delta:=(N+1-phn)^2-4N; <-- delta=(N+1-phn)^2-4N

x:=((N+1-phn)+Sqrt(delta))/2; <-- Candididat pour p
p2:=Round(x); <-- Candididat pour p
g:=GCD(p2,N); <-- PGCD
i:=i+1;
end while; <-- Fin while
p2; <-- Affichage de p2
p2-p; <-- Différence nulle
42CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES
Chapitre 3

Cryptanalyse de RSA par

l’algorithme LLL

Les objectifs ne sont pas atteints par les souhaits, mais par le
travail assidu.
Abu Alaa Al Maary
YgñK á» B ð
AK. C« AJK YË@ úæÒJËAK. I.Ë A¢ÜÏ @ ÉJK AÓð
ø QªÜÏ @ Z CªË@ ñK. @

3.1 L’algorithme LLL

3.1.1 Introduction aux réseaux

L’algorithme LLL a été inventé en 1982 et porte les initiales des ses inventeurs,
A.K. Lenstra, H.W. Lenstra et L. Lovász. A l’origine, son but était de factoriser
des polynômes à coefficients entiers. Depuis son invention, l’algorithme LLL a été
utilisé dans de nombreux domaines, en particulier dans la résolution des équations
diophantiennes et la cryptanalyse, y compris celle de certaines instances de RSA.
Le domaine de l’algorithme LLL est la réduction de bases dans des sous ensembles
de Rn , appelés réseaux.
Définition 3.1.1. Soit n et d deux un entiers positifs. Soit L une partie non vide
de Rn . On dit que L est un réseau s’il existe une famille libre (b1 · · · , bd ) de Rn telle
que ( d )
X d X
L= Zbi = x i bi | x i ∈ Z .
i=1 i=1

43
44 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

L’entier d est la dimension du réseau, et (b1 · · · , bd ) est une base de ce réseau.

Dans la plupart des applications, on a d = n et donc la matrice de la base (b1 · · · , bd )

est une matrice carrée. On peut en particulier calculer son déterminant, qui ne
dépend pas de la base choisie.
Définition 3.1.2. Soit L un réseau de dimension n et (b1 · · · , bn ) une base de L.
Le déterminant de L est

det(L) = | det(b1 · · · , bn )|.

Proposition 3.1.3. Soit L un réseau de dimension n. Le déterminant de L est

indépendant de la base.

Démonstration. Supposons que det(L) = | det(b1 · · · , bn )|, où B = (b1 · · · , bn ) est

une base de L. Soit B 0 = (b01 · · · , b0n ) une autre base de L. Alors, il existe une matrice
carrée U , de type n × n à éléments dans Z telle que

det(U ) = ±1, B 0 = U B.

Alors

| det(b01 · · · , b0n )| = | det(U ) det(b1 · · · , bn )| = | det(b1 · · · , bn )| = det(L),

ce qui termine la preuve.

Le plus souvent, la base d’un réseau n’a pas de bonnes propriétés et les calculs
peuvent être compliqués. Un moyen pour rendre les calculs plus efficaces est de
chercher une base orthogonale dans un réseau. Pour cela, on considère le produit
scalaire habituelle de deux vecteurs et la norme euclidienne d’un vecteur.
Définition 3.1.4. Soient x = (x1 · · · , xn ) et y = (y1 · · · , yn ) deux vecteurs de Rn .
1. Le produit scalaire de x et y est
n
X
T
hx, yi = x y = xi y i .
i=1

2. La norme de x est ! 12
n
1 X
kxk = (hx, xi) = 2 x i yi .
i=1

Une des méthodes les plus utilisées pour produire une base orthogonale à partir
d’une base quelconque est la méthode de Gram-Schmidt.
3.1. L’ALGORITHME LLL 45

Théorème 3.1.5 (Gram-Schmidt). Soit V un sous-espace vectoriel de dimension n

et (b1 · · · , bn ) une base de V . On considère la famille de vecteurs (b∗1 · · · , b∗n ) définie
par

i−1
X
b∗1 = b1 , b∗i = bi − µi,j b∗j ,
j=1

avec pour j < i

hbi , b∗j i
µi,j = .
hb∗j , b∗j i

Alors (b∗1 · · · , b∗n ) est une base orthogonale de l’espace de V .

Démonstration. On va commencer par démontrer que (b∗1 · · · , b∗n ) est une base de
V . En écrivant

i−1
X
b1 = b∗1 , bi = b∗i + µi,j b∗j ,
j=1

on en conclut que, sous forme matricielle, on a

     
b1 1 0 0 0 ··· 0   b∗1
b∗1
 b2   µ2,1 1 0 0 ··· 0   b∗2 
    b∗2  
 b3   µ3,1 µ3,2 1 0 ··· 0    b∗3 

 .. =
 
.. .. .. .. .. ..

 b∗3=U
 
.. .

 .   . . . . . . ..  . 

 bn−1
 
  µn1 ,1 µn−1,2 µn−1,3 · · ·
 .  ∗ 
1 0  ∗
 bn−1 
bn
bn µn,1 µn,2 µn,3 · · · µn,n−1 1 b∗n

La matrice U est est une matrice inférieure, dont la diagonale est formée de 1. Son
déterminant est donc 1. Ainsi (b∗1 · · · , b∗n ) est aussi une base de V .
On démontre maintenant que (b∗1 · · · , b∗n ) est orthogonale. Par récurrence, puisque
b∗1 = b1 et b∗2 = b2 − µ2,1 b1 , alors

hb2 , b1 i
hb∗1 , b∗2 i = hb1 , b2 − µ2,1 b1 i = hb1 , b2 i − µ2,1 hb1 , b1 i = hb1 , b2 i − hb1 , b1 i = 0.
hb1 , b1 i

Supposons maintenant que la famille (b∗1 · · · , b∗i−1 ) est orthogonale avec i ≥ 3. Alors
46 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

on a pour 1 ≤ k ≤ i − 1
* i−1
+
X
hb∗k , b∗i i = b∗k , bi − µi,j b∗j
j=1
i−1
X
= hb∗k , bi i − µi,j b∗k , b∗j
j=1
= hb∗k , bi i
− µi,k hb∗k , b∗k i
hbi , b∗ i
= hb∗k , bi i − ∗ k∗ hb∗k , b∗k i
hbk , bk i
= 0.

Ainsi (b∗1 · · · , b∗i ) est orthogonale, ce qui prouve la récurrence et termine la preuve.

La méthode de Gram-Schmidt peut être facilement mise en algorithme 8.

Algorithme 8 : La méthode de Gram-Schmidt

Entrée : Une base (b1 · · · , bn ).
Sortie : Une base orthogonale (b∗1 · · · , b∗n ).
1: Poser b∗1 = b1 .
2: Pour i = 1, 2, · · · n, faire
3: Pour j = 1, 2, · · · i − 1, faire
hbi ,b∗ i
4: Calculer µi,j = hb∗ ,bj∗ i .
j j
5: Fin Pour
Calculer b∗i = bi − i−1 ∗
P
6: j=1 µi,j bj .
7: Fin Pour

On va maintenant programmer directement l’algorithme 8.

Maple 3.1.6.

Programme

scal:= proc (u, v)

add(u[i]*v[i], i = 1 .. nops(u));
end proc:
3.1. L’ALGORITHME LLL 47

Programme Commentaires

gramschmidt:=proc (M) <-- Procédure

local i, j, n, B, P, u,k: <-- Paramètres locaux
with(LinearAlgebra): <-- Librairie LinearAlgebra
n := nops(M): <-- Nombre de lignes de M
B := []: P := []: <-- Initiation des listes
for i from 1 to n do <-- i=1,...,n
u := [seq(0, k = 1 .. n)]: <-- Initiation de u
for j from 1 to i-1 do for j from 1 to i-1 do
u[j]:=scal(M[i],B[j])/scal(B[j],B[j]): <-- Calcul de u[j]
end do:
u[i] := 1: <-- u[i]= 1
P := [op(P), u]: <-- concaténation
B:=[op(B),[seq(M[i][k]-add(u[j]*B[j][k], <-- Calcul de B
j = 1 .. i-1), k = 1 .. n)]]:
end do:
return(B, P): <-- Sortie
end proc:
Le programme suivant prend en entrée la base (b1 , b2 , b3 ) dont la matrice est
     
2 1 0
b1 = 1 , b2 =  4  , b3 = −2 .
0 −2 −1

Programme Commentaires

M:=[[2,1,0],[1,4,-2],[0,-2,-1]]; <-- Entrée matrice M

gramschmidt(M); <-- procédure gramschmidt
A:=transpose(matrix(gramschmidt(M)[1])); <-- Matrice A
P := transpose(matrix(gramschmidt(M)[2])): <-- Matrice P
Q:=multiply(P, A); <-- Produit PA
On obtient alors les matrices :
2 − 75 10
 6
1 5 − 25
    
23
2 1 0
A = 1 14 5
− 20
23
 , P = 0 1 − 6  ,
23
Q = 1 4 −2 .
35
0 −2 − 23 0 0 1 0 −2 −1
Maple 3.1.7.
En fait, dans Maple, la méthode de Gram-Schmidt est programmée sous le nom de
fonction GramSchmidt dans le package LinearAlgebra. Voici un exemple simple
de son utilisation. On considère la base (b1 , b2 , b3 ) avec
48 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

     
2 1 0
b1 = 1 , b2 =  4  , b3 = −2 .
0 −2 −1

Programme Commentaires

with(LinearAlgebra): <--- package LinearAlgebra

b1:=Vector([2, 1, 0]): <--- Premier vecteur
b2 := Vector([1, 4, -2]): <--- Deuxième vecteur
b3 := Vector([0, -2, -1]): <--- Troisième vecteur
B := GramSchmidt([b1, b2, b3]); <--- La procédure de Gram-Schmidt
DotProduct(B[1], B[2]); <--- Vérification du produit scalaire
DotProduct(B[1], B[3]); <--- Vérification du produit scalaire
DotProduct(B[2], B[3]); <--- Vérification du produit scalaire
On obtient alors la base orthogonale (b∗1 , b∗2 , b∗3 ) avec
   7  10 
2 −5 23
b∗1 = b1 = 1 , b∗2 =  14 5
 , b∗3 = − 20  .
23
35
0 −2 − 23

Magma 3.1.8.
Dans Magma, la méthode d’orthogonalisation de Gram-Schmidtst est programmée
sous le Orthogonalize(M) où M est une matrice carrée. Elle retourne trois valeurs
N , P et n où N est une matrice dont les colonnes représentent des vecteurs orthogo-
naux, P est une matrice de passage vérifiant N = P M et n est le rang de M . Voici
un exemple simple de son utilisation. On considère la même base (b1 , b2 , b3 ) avec
     
2 1 0
b1 = 1 ,
 b2 =  4  , b3 = −2 .
0 −2 −1

Programme Programme

Q:= RealField(); <--- Ensemble des réels

R:=MatrixRing(Q,3); <--- Ensemble des matrices
définie sur Q de type 3x3.
F:=elt<R|[2, 1, 0, <--- F est la matrice
1, 4, -2,
0, -2, -1]>;
Orthogonalize(F) ; <--- L’orthogonalisation de Gram-Shmidt
3.1. L’ALGORITHME LLL 49

On obtient alors la base orthogonale (b∗1 , b∗2 , b∗3 ) avec

   7  10 
2 −5 23
b∗1 = b1 = 1 , b∗2 =  14 5
 , b∗3 = − 20  .
23
35
0 −2 − 23

Le résultat suivant montre qu’on peut calculer le déterminant d’un réseau si on

connait une base orthogonale.

Corollaire 3.1.9 (Hadamard). Soit L un réseau de dimension n, (b1 · · · , bn ) une

base de L et (b∗1 · · · , b∗n ) la famille orthogonale au sens de Gram-Schmidt. Alors
n
Y n
Y
det(L) = kb∗i k ≤ kbi k.
i=1 i=1

Démonstration. On a b1 = b∗1 , donc kb1 k = kb∗1 k. Pour 2 ≤ i ≤ n, on a

i−1
X
bi = b∗i + µi,j b∗j ,
j=1

et comme hb∗r , b∗s i = 0 si r 6= s, alors

i−1
X
2
kbi k = kb∗i k2 + µ2i,j kb∗j k2 ,
j=1

et donc n n
Y Y
det(L) = 2
kb∗i k2 ≤ kbi k2 ,
i=1 i=1

ce qui termine la preuve.

Un problème très important en théorie des nombres et en cryptanalyse est la re-

cherche d’un vecteur court dans un réseau. Deux sous-problèmes se posent alors.
Problème du vecteur le plus court (The Shortest Vector Problem (SVP)) :
Etant donné un réseau L. Déterminer un vecteur non nul v qui minimise la nome
kvk.
Problème du vecteur le plus proche (The Closest Vector Problem (CVP)) :
Etant donné un réseau L et un vecteur v0 . Déterminer un vecteur v 6= v0 qui minimise
la nome kv − v0 k. Une réponse théorique dans le sens de ces deux problèmes est la
suivante.
50 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

Théorème 3.1.10 (Hermitte). Soit L un réseau de dimension n. Alors il existe un

vecteur v non nul de L tel que

√ 1
kvk ≤ n det(L) n .

Ce théorème est très théorique et la détermination d’un vecteur court est difficile
en général. Un moyen pratique pour trouver des vecteurs assez courts est d’utiliser
l’algorithme LLL.

3.1.2 L’algorithme LLL

L’algorithme LLL est lié à la méthode d’orthogonalisation de Gram-Schmidt. Il

concerne des bases spéciales, appelées bases réduites.

Définition 3.1.11. Une base (b1 · · · , bn ) est LLL-réduite si, la base (b∗1 · · · , b∗n )
produite par la la méthode d’orthogonalisation de Gram-Schmidt vérifie

1
(3.1) |µi,j | ≤ , pour 1 ≤ j < i ≤ n,
2
3 ∗ 2
(3.2) kb k ≤ kb∗i + µi,i−1 b∗i−1 k2 , pour 1 < i ≤ n.
4 i−1

La deuxième condition est appelée condition de Lovász. Si µi,j = 0 pour tout i et j,

alors la base est orthogonale, et donc minimale d’après l’inégalité de Hadamard 3.1.9.
Si |µi,j | ≤ 12 , la base est presque orthogonale, donc presque minimale. L’algorithme
LLL original est le suivant

Maple 3.1.12.

On va maintenant programmer l’algorithme LLL. Tout d’abord, il faut programmer

la procédure produit scalaire scal(u,v) et la procédure gramschmidt(M). On
programme ensuite la procédure redfaible(M).
3.1. L’ALGORITHME LLL 51

Algorithme 9 : Algorithme LLL

Entrée : Une base (b1 , · · · , bn )
Sortie : Une base LLL réduite (b1 , · · · , bn )
1: Pour i = 1, · · · , n faire
2: b∗i = bi
3: Pour j = 1, · · · , i − 1 faire
hbi ,b∗ i
4: µi,j = Bjj
5: b∗i = b∗i − µi,j b∗j
6: Fin Pour
7: Bi = hb∗i , b∗i i
8: Fin Pour
9: k = 2
10: Appliquer redfaible(k, k − 1)
11: Si 34 Bk−1 > Bk + µ2k,k−1 Bk−1 alors
12: Appliquer lovasz(k)
13: Fin Si
14: Aller à l’étape 10
15: Pour l = k − 2, · · · , 1 faire
16: Appliquer redfaible(k, l)
17: Fin Pour
18: Si k = n alors
19: Stop
20: Sinon
21: k =k+1
22: Aller à l’étape 10
23: Fin Si

Algorithme 10 : Procédure redfaible

Entrée : Un couple (k, l)
Sortie : Un vecteur bk et des valeurs µk,j avec j = 1, · · · l − 1 avec |µk,l | ≤ 21
1: Si |µk,l | > 12 alors
2: bk = bk − bµk,l ebl
3: µk,l = µk,l − bµk,l e
4: Pour j = 1, · · · , l − 1 faire
5: µk,j = µk,j − bµk,l eµl,j
6: Fin Pour
7: Fin Si
Remarque : bxe est l’arrondi de x, c’est à dire l’entier le plus proche de x.
52 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

Algorithme 11 : Procédure lovasz

Entrée : Un entier k
Sortie : La condition de Lovasz 43 Bk−1 ≤ Bk + µ2k,k−1 Bk−1 est satisfaite
1: B = Bk + µ2k,k−1 Bk−1
µ Bk−1
2: µk,k−1 = k,k−1B
B Bk
3: Bk = k−1 B
4: Bk−1 = B
5: Echanger bk et bk−1
6: Pour j = 1, · · · , k − 2 faire
7: Echanger µk−1,j et µk,j
8: Fin Pour
9: Pour i = k + 1, · · · , n faire
10: µi,k−1 = µk,k−1 µi,k−1 + (1 − µk,k−1 µk,k−1 )µi,k
11: µi,k = µi,k−1 − µk,k−1 µi,k
12: Fin Pour
13: Si k > 2 alors
14: k =k−1
15: Fin Si

Procédure redfaible Commentaires

redfaible:=proc(M) <-- Procédure redfaible

local i,j,k,U,N; <-- paramètres locaux
N:=M; <-- Initialisation
U:=gramschmidt(M)[2]; <-- Matrice de passage U
for i from 2 to nops(M) do <-- i=2,...
for j from i-1 by -1 to 1 do <-- j=i-1,...,1
N[i] := N[i]-round(U[i][j])*N[j]; <-- Nouveau N
for k from 1 to j do <-- k=1,...,j
U[i][k]:=U[i][k]-round(U[i][j])*U[j][k] <-- Nouveau U
end do <--
end do <--
end do: <--
return N: <-- renvoi de N
end proc: <-- Fin de la procédure
On programme maintenant la procédure lovasz(M).
3.1. L’ALGORITHME LLL 53

Procédure lovasz

lovasz:=proc(M)
local i,n,G;
n:=nops(M);
G:=gramschmidt(M);
for i to n-1 do
if evalb(scal(G[1][i+1],G[1][i+1])
<(3/4-G[2][i+1][i]^2)*scal(G[1][i],G[1][i]))
then return [false, i]
end if:
end do:
return [true, 0]:
end proc
Finalement, on donne la programmation de LLL sous la forme de procédure myLLL(M).
Procédure myLLL

myLLL:=proc(M)
local N,B,x:
N:=redfaible(M):
B:=lovasz(N):
while not(B[1]) do
x := N[B[2]]:
N:=redfaible(subsop(B[2] = N[B[2]+1], B[2]+1 = x, N)):
B:=lovasz(N):
end do:
return N:
end proc:
Avec la matrice

 
b1 b2 b3 b4
↓ ↓ ↓ ↓
 
4 7 9 4
M =
 ,
 6 −7 2 3 

−1 2 −1 −1
2 −1 0 −3
54 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

on obtient en exécutant myLLL(M ) la matrice suivante.

 
b1 b2 b3 b4
↓ ↓ ↓ ↓
 
−1 2 −1 −1
N = .
2
 1 −2 −1 
−1 0 1 −3
5 8 8 0

Parmi les nombreuses propriétés d’une base LLL-réduite, on a les inégalités sui-
vantes.

Théorème 3.1.13. Soit (b1 · · · , bn ) une base LLL-réduite et (b∗1 , · · · , b∗n ) la base
orthogonale associée par la méthode de Gram-Schmidt. Alors
1. kb∗j k2 ≤ 2i−j kb∗i k2 pour 1 ≤ j ≤ i ≤ n.
n(n−1)
2. ni=1 kbi k ≤ 2 4 det(L).
Q
i−1
3. kbj k ≤ 2 2 kb∗i k pour 1 ≤ j ≤ i ≤ n.
n−1 1
4. kb1 k ≤ 2 4 (det(L)) n .
n−1
5. Pour tout vecteur non nul v ∈ L, kb1 k ≤ 2 2 kvk.

Démonstration.
Preuve de 1. Supposons que (b1 · · · , bn ) une base LLL-réduite. Alors, en développant
l’inégalité 3.2 et en utilisant 3.1, on a
3 ∗ 2 1
kbi−1 k ≤ kb∗i k2 + µ2i,i−1 kb∗i−1 k2 ≤ kb∗i k2 + kb∗i−1 k2 ,
4 4
ce qui donne
kb∗i−1 k2 ≤ 2kb∗i k2 .
Ainsi, pour j ≤ i, on obtient

kb∗j k2 ≤ 2i−j kb∗i k2

ce qui démontre la propriété 1.

Preuve de 2. Dans le processus de l’orthogonalisation de Gram-Schmidt, on a bi =
Pi−1
b∗i + j=1 µi,j b∗j ,. On obtient ainsi, en utilisant 3.1 :

i−1 i−1
X 1X ∗ 2
2
kbi k = kb∗i k2 + µ2i,j kb∗j k2 ≤ kb∗i k2 + kb k .
j=1
4 j=1 j
3.1. L’ALGORITHME LLL 55

En utilisant kb∗j k2 ≤ 2i−j kb∗i k2 , on obtient

i−1
1 X i−j ∗ 2
2
kb∗i k2 2 kbi k = 2i−2 + 2−1 kb∗i k2 ≤ 2i−1 kb∗i k2 .

kbi k ≤ +
4 j=1

En passant aux produits, on a alors

n n n
Y Y n(n−1) Y n(n−1)
2
kbi k ≤ 2 i−1
kb∗i k2 =2 2 kb∗i k2 = 2 2 det(L),
i=1 i=1 i=1

ce qui donne l’inégalité 2 en prenant les racines carrées.

Preuve de 3. En remplaçant i par j dans l’inégalité kbi k2 ≤ 2i−1 kb∗i k2 (ci-dessus),
on obtient kbj k2 ≤ 2j−1 kb∗j k2 . En combinant avec l’inégalité 1, on obtient

kbj k2 ≤ 2j−1 2i−j kb∗i k2 = 2i−1 kb∗i k2 ,

ce qui démontre l’inégalité 3.
Preuve de 4. En prenant j = 1 dans l’inégalité 3, on obtient kb1 k2 ≤ 2i−1 kb∗i k2
pour 1 ≤ i ≤ n. Alors
Y n(n−1) Y n(n−1)
kb1 k2n ≤ n2i−1 kb∗i k2 = 2 2 nkb∗i k2 = 2 2 (det(L))2 ,
i=1 i=1
n−1 1
ce qui donne kb1 k ≤ 2 4 (det(L)) n et démontre l’inégalité 4.
Preuve de 5. Soit v ∈ L un vecteur non nul. Alors, en exprimant v dans les bases
(b1 , b2 , · · · , bn ) et (b∗1 , b∗2 , · · · , b∗n ), on obtient
n
X n
X
v= αi bi = αi∗ b∗i , αi ∈ Z αi ∈ R.
i=1 i=1

En prenant la définition de bi dans l’orthogonalisation de Gram-Schmidt, on obtient

n i−1
!
X X
v= αi b∗i + µi,j b∗j .
i=1 j=1

Soit k, 1 ≤ k ≤ n, le plus grand indice pour lequel αk 6= 0. Alors en exprimant le pro-

duit hv, b∗k i de deux façons et en tenant compte de l’orthogonalité de (b∗1 , b∗2 , · · · , b∗n ),
on obtient :
hv, b∗k i = αk kb∗k k2 = αk∗ kb∗k k2 .
Ainsi αk = αk∗ , avec |αk | ≥ 1. En calculant kvk2 , on obtient
n
X
kvk2 = (αi∗ )2 kb∗i k2 ≥ (αk∗ )2 kb∗k k2 ≥ kb∗k k2 .
i=1
56 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

En prenant j = 1 et i = k dans l’inégalité 3, on obtient kb∗k k2 ≥ 21−k kb1 k2 . Ainsi

kvk2 ≥ 21−k kb1 k2 ≥ 21−n kb1 k2 ,

n−1
ce qui donne kb1 k ≤ 2 2 kvk et termine la preuve.

Le théorème précédent concerne souvent le vecteur b1 . Plus généralement, on a le

résultat suivant.

Théorème 3.1.14. Soit (b1 , · · · , bn ) une base LLL-réduite d’un réseau. Alors pour
tout j, 1 ≤ j ≤ n, on a
n(n−1) 1
kbj k ≤ 2 4(n−j+1) (det L) n−j+1 .

Démonstration. Soit (b∗1 , · · · , b∗n ) la base orthogonale associée par la méthode de

Gram-Schmidt à (b1 , · · · , bn ). Par le résultat (3) de la proposition 3.1.13, on a, pour
1≤j≤i≤n
i−1
kbj k ≤ 2 2 kb∗i k.
En appliquant cette inégalité pour chaque i = j, j + 1, · · · , n et en multipliant, on
obtient
n
i−1
Y
kbj kn−j+1 ≤ 2 2 kb∗i k.
i=j

On obtient alors en commençant à i = 1 :

n n n
Y i−1
Y i−1
Y n(n−1)
kbj k n−j+1
≤ 2 2 kb∗i k = 2 2 kb∗i k = 2 4 det(L),
i=1 i=1 i=1

ce qui donne le résultat recherché.

On donne maintenant la complexité de l’algorithme LLL.

Théorème 3.1.15. Soit (b1 , · · · , bn ) une base d’un réseau L et B = maxi kbi k.
L’algorithme LLL produit une base réduite en un temps polynômial :

O n4 log3 B .

Maple 3.1.16.
Dans Maple 12, l’algorithme LLL est en fait déjà programmé sous le nom de procédure
LLL dans le package IntegerRelations. On donne, par exemple la base (b1 , b2 , b3 , b4 )
avec pour matrice
3.1. L’ALGORITHME LLL 57

 
b1 b2 b3 b4
↓ ↓ ↓ ↓
 
4 7 9 4
M =
 .
 6 −7 2 3 

−1 2 −1 −1
2 −1 0 −3

Programme Commentaires

with(IntegerRelations): <--- Package IntegerRelations

with(LinearAlgebra): <--- Package LinearAlgebra
l1 := [4, 7, 9, 4]; <--- Premiere ligne
l2 := [6, -7, 2, 3]; <--- Deuxième ligne
l3 := [-1, 2, -1, -1]; <--- Troisième ligne
l4 := [2, -1, 0, -3]; <--- Quatrième ligne
N:=LLL([l1, l2, l3,l4],’integer’); <--- Procédure LLL, paramètres entiers
On obtient alors la base (b1 , b2 , b3 , b4 ) dont la matrice est
 
b1 b2 b3 b4
↓ ↓ ↓ ↓
 
−1 2 −1 −1
N = .
2
 1 −2 −1 
−1 0 1 −3
5 8 8 0

On peut alors vérifier que les deux bases on le même déterminant et que b01 est plus
court que les autres vecteurs de la base.
Programme Commentaires

M:=Matrix([b1, b2, b3, b4]): <--- Matrice M

N:=Matrix([m[1], m[2], m[3], m[4]]): <--- Matrice N
Determinant(M)-Determinant(N); <--- Comparaison
for i to 4 do <--- Liste des modules
DotProduct(Vector(m[i]),Vector(m[i])) et vérification que
end do; b1 est le plus court.

Magma 3.1.17.
Dans Magma, l’algorithme LLL est programmé sous le nom LLL. On donne, le
58 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

même exemple avec la base (b1 , b2 , b3 , b4 ) qui a pour matrice

 
b1 b2 b3 b4
↓ ↓ ↓ ↓
 
4 7 9 4 
M =
 6 −7 2
.
 3 

−1 2 −1 −1
2 −1 0 −3

Programme Commentaires

Z := IntegerRing(); <--- Ensemble des entiers

R:=MatrixRing(Z,4); <--- Ensemble des matrices de type 4x4
M :=elt< R|[4, 7, 9, 4, <--- Matrice
6, -7, 2, 3,
-1, 2, -1, -1,
2 , -1,0, -3] >;
F:=LLL(M) ; <--- Procédure LLL,
Determinant(M); <--- Déterminant de M
Determinant(F); <--- Déterminant de F
On obtient alors la base (b01 , b02 , b03 , b04 ) dont la matrice est

b01 b02 b03 b04

 
↓ ↓ ↓ ↓
 
−1 2 −1 −1
N = .
2
 1 −2 −1 
−1 0 1 −3
5 8 8 0

On peut alors vérifier que les deux bases on le même déterminant et que b01 est plus
court que les autres vecteurs de la base.
3.2. CRYPTANALYSE DE RSA PAR LA RÉDUCTION DES RÉSEAUX 59

Programme Programme

Z :=RationalField(); <--- Z :=RationalField();

V := VectorSpace(Z, 4); V := VectorSpace(Z, 4);
x := V![-1 ,2 ,-1 ,-1]; x := V![-1 ,2 ,-1 ,-1];
Norm(x); Norm(x);
y := V![2 , 1 ,-2, -1]; y := V![2 , 1 ,-2, -1];
Norm(y); Norm(y);
z:= V![-1 , 0, 1, -3]; z:= V![-1 , 0, 1, -3];
Norm(z); Norm(z);
w := V![5 , 8 , 8 , 0]; w := V![5 , 8 , 8 , 0];
Norm(w); Norm(w);

3.2 Cryptanalyse de RSA par la réduction des

réseaux

3.2.1 La méthode de Coppersmith : polynômes à une va-

riable
En 1996, D. Coppersmith a décrit une méthode pour déterminer les petites racines
modulaires d’un polynôme à une variable ainsi que les petites racines entières d’un
polynôme à deux variables. Soit N un entier positif (sans factorisation connue) et f
un polynôme de degré d à coefficient dans Z.
n
X
f (x) = ai x i .
i=1

Chaque terme xi est appelé un monôme. La norme Euclidienne de f est définie par
v
u n
uX
||f (x)|| = t a2i .
i=1

Le problème de la petite racine modulaire consiste à trouver un nombre entier x0

qui vérifie

f (x0 ) ≡ 0 (mod N ),
|x0 | < X,

où X est une borne fixée.

60 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

L’idée de Coppersmith s’applique plus généralement dans le cas suivant :

Paramètres connus :
- Un entier N .
- L’existence d’un facteur inconnu b de N avec b > N β .
- L’expression d’un polynôme fb (x), de degrés δ.
- Une borne X pour laquelle fb (x0 ) ≡ 0 (mod b) avec |x0 | < X.
Paramètres inconnus :
- Le facteur b de N.
- La racine x0 .
La méthode de Coppersmith permet de transformer l’équation modulaire fb (x0 ) ≡ 0
(mod b) en une équation entière f (x) = 0, c’est à dire sur l’ensemble des entiers.
Pour déterminer l’équation entière, on fixe un entier m et on construit une série de
polynômes de Z[x] :
gjk (x) = xj (fb (x))k N m−k ,
où les valeurs de j et k dépendent de m et du degré de f . Puisque fb (x0 ) ≡ 0
(mod b), alors fb (x0 ) = ab pour un entier a et donc
m−k
j k m−k N
gjk (x0 ) = x0 (fb (x)) b
b
m−k
N
= ak xj0 bk bm−k
b
m−k
N
= ak xj0 bm
b
≡ 0 (mod bm ).

Ceci implique que toute combinaison linéaire h(x) des polynômes gjk (x) vérifiera
h(x0 ) ≡ 0 (mod bm ). Si en plus h vérifie |h(x0 )| < bm , alors on a tout simplement
h(x0 ) = 0, ce qui est facile à résoudre. Le passage de l’équation modulaire h(x0 ) ≡ 0
(mod bm ) à l’équation entière h(x0 ) = 0 peut être fixé par le théorème suivant.
Théorème 3.2.1 (Howgrave-Graham). Soit h(x) ∈ Z[x] un polynôme de degré d
ayant au plus ω monômes et X un nombre positif. Si x0 est un entier et M un
nombre positif tels que :
(1) |x0 | < X,
(2) h(x0 ) ≡ 0 (mod M ),
M
(3) kh(xX)k < √
ω
,
3.2. CRYPTANALYSE DE RSA PAR LA RÉDUCTION DES RÉSEAUX 61

alors h(x0 ) = 0 en tant qu’équation sur Z.

Pd
Démonstration. Soit h(x) = i ai xi ayant ω monômes. Supposons que |x0 | < X.
Alors
X X X
|h(x0 )| = ai xi ≤ ai x i < ai X i .
i i i

D’autre part, l’inégalité de Cauchy-Schwarz donne

!2 ! !
X X X
αi βi ≤ αi2 βi2 .
i i i

En utilisant cette inégalité, on obtient

!2 ! !
2 2
X X X X
ai X i 12 ai X i ai X i .

≤ =ω
i i i i

M
Ainsi, si kh(xX)k < √
ω
, alors

√ √
s
X X
ai X < i
ω (ai X i )2 = ωkh(xX)k < M.
i i

Donc |h(x0 )| < M . Si on suppose que h(x0 ) ≡ 0 (mod M ), alors h(x0 ) = 0.

Le problème de la résolution de la congruence fb (x0 ) ≡ 0 (mod b) peut donc être

résolu par une équation h(x0 ) = 0 où h vérifie le théorème 3.2.1. On observe d’abord
que la condition (3) de ce théorème signifie que les coefficients de h sont assez petits
et que la condition (2) avec M = bm est satisfaite par toute combinaison linéaire
des polynômes gjk (x). Ceci peut être obtenu en appliquant la réduction d’un réseau
de dimension n dont une base est formée à l’aide des coefficients des polynômes
gjk (xX). Avec l’algorithme LLL, on peut obtenir un vecteur h(xX) qui vérifie la
condition (3). L’algorithme LLL donnera alors des vecteurs v1 (xX), · · · vn (xX) où
n est la dimension du réseau. On sait d’après le théorème 3.1.13, que le polynôme
v1 (xX) va vérifier
n−1 1
kv1 (xX)k ≤ 2 4 det(L) n .
Ainsi, pour satisfaire la condition (3) du théorème 3.2.1, il suffit d’avoir
n−1 bm
1
(3.3) 2 4 det(L) < √
n .
n

Le vecteur recherché h(xX) sera donc le premier vecteur v1 (xX) de la base réduite.
62 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

En effet, on considère le réseau formé par les vecteurs colonnes de la matrice définie
par les polynômes

gi,j (x) = xj N i (fb (x))m−i , j = 0, · · · , δ − 1, i = m, · · · , 1,

hi (x) = xi (fb (x))m , i = 0, · · · , t − 1,

où δ = deg(fb ) et m et t sont des entiers fixés. En explicitant les polynômes gi,j (x),
on obtient les valeurs

j=0 j=1 j=2 ··· j =δ−1

↓ ↓ ↓ ↓ ↓
m m m 2 m δ−1
i=m→ N , N x, N x, ··· N x ,
m−1 m−1
i=m−1→ N f N xf N m−1 x2 f ··· N m−1 xδ−1 f
(3.4) i = m − 2 → N m−2 f 2 N m−2 xf 2 N m−2 x2 f 2 ··· N m−2 xδ−1 f 2
.. .. .. .. .. ..
.→ . . . . .
2 m−2 2 m−2 2 2 m−2
i=2→ N f N xf N xf ··· N 2 xδ−1 f m−2
i=1→ N f m−1 N xf m−1 N x2 f m−1 ··· N xδ−1 f m−1

On observe de cette façon que les degrés des polynômes sont croissants de la position
(i, j) = (m, 0) à la position (i, j) = (1, δ − 1). On peut continuer ce tableau avec les
polynômes hi (x).

(3.5) i = 0, · · · , t − 1 ⇒ f m , xf m , x2 f m , · · · , xt−1 f m .

Une fois encore les degrés sont croissants. Globalement, les degrés remplissent to-
talement l’intervalle {0, 1, · · · , mδ + t − 1}. On peut alors considérer les matrices
définies par les coordonnées des différents polynômes gi,j (Xx) et hi (Xx), lignes par
3.2. CRYPTANALYSE DE RSA PAR LA RÉDUCTION DES RÉSEAUX 63

lignes, dans la base 1, x, x2 , · · · , xmδ+t−1 .
 
Nm
 N mX 
Mm =  ,
 
. .
 . 
m δ−1
N X
 
− − − − N m−1 X δ
 − − − − − N m−1 X δ+1 
Mm−1 =  ,
 
 − − − − . . .
− − 
m−1 2δ−1
− − − − − − − N X
.. .
. = .. 
− − · · · − N X (m−1)δ
 − − ··· − − N X (m−1)δ+1 
M1 =  ,
 
..
 − − ··· − − − . 
− − ··· − − − − N X (m−1)δ+δ−1
 
− − · · · − X mδ
 − − · · · − − X mδ+1 
M0 =  .
 
. .
 − − ··· − − − . 
mδ+t−1
− − ··· − − − − X
Avec ses matrices, on forme la matrice carrée (n×n) M , avec n = mδ +t, qui définie
le réseau L par les colonnes de la matrice :
 
Mm
 Mm−1 
 
(3.6) M = ..
.
 
 . 
 M1 
M0
Cette matrice est diagonale est son déterminant est donc le produit des différentes
diagonales :
1 1
det(L) = N mδ · N (m−1)δ · · · · N δ X 1+2+···+n−1 = N 2 m(m+1)δ X 2 n(n−1) .
Alors l’inégalité 3.3 devient
n−1 m(m+1)δ 1 bm
2 4 N 2n X 2 (n−1) < √ .
n
Puisque b > N β , il suffit alors d’avoir
n−1 m(m+1)δ 1 N mβ
2 4 N 2n X 2 (n−1) < √ .
n
64 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

En isolant X, on obtient alors

1 −1 2mnβ−m(m+1)δ
X < 2− 2 n n−1 N n(n−1) .

En considérant l’exposant de N dans l’inégalité précédente, on observe qu’il atteint

son maximum pour
2nβ − δ
m0 = ,
2δ
ce qui donne la borne
1 −1 β2 β2 δ β
+ (n−1)δ + 4n(n−1) − n−1
X < 2− 2 n n−1 N δ ,

ce qui peut être écrit sous la forme

1 β2
X < 2− 2 N δ
−ε
,

avec
log n β β2 δ
ε= + − − ,
(n − 1) log N n − 1 (n − 1)δ 4n(n − 1)
qui dépend de n mais qui vérifie lim ε = 0.
n→+∞

On peut maintenant résumer cette méthode dans le théorème suivant.

Théorème 3.2.2. Pour tout ε > 0, il existe un entier N0 qui vérifie la propriété :
Soit N > N0 un entier de factorisation inconnue qui a un diviseur b > N β . Soit
fb (x) un polynôme de degrés δ. Toutes les solutions x0 de la congruence fb (x) ≡ 0
(mod b) vérifiant
1 β2
|x0 | < 2− 2 N δ
−ε

peuvent être déterminées en temps polynômial en log N .

En appliquant ce théorème avec b = N et donc β = 1, on obtient le théorème

Théorème 3.2.3. Pour tout ε > 0, il existe un entier N0 qui vérifie la propriété :
Soit N > N0 un entier de factorisation inconnue. Soit f (x) un polynôme de degrés
δ. Toutes les solutions x0 de la congruence f (x) ≡ 0 (mod N ) vérifiant
1 1
|x0 | < 2− 2 N δ −ε

peuvent être déterminées en temps polynômial en log N .

Exemple 3.2.4.
3.2. CRYPTANALYSE DE RSA PAR LA RÉDUCTION DES RÉSEAUX 65

Soit N = 29263868053. On veut déterminer les solutions de la congruence

f (x) = −111111111 − 111111110x − 111111110x2 + x3 ≡ 0 (mod N ).

Le degrés est δ = 3 et on peut donc déterminer, en théorie, toutes les solutions x0

qui vérifient
1 1
|x0 | < 2− 2 N δ −ε ,
soit |x0 | < 2179 avec ε = 0. On pose donc X = 2179. On choisissant m = 3 et t = 1,
on doit calculer les polynômes définies par (3.4), soit

j=0 1 2
i=3 N 3, N 3 xX, N m (xX)2
i=2 N 2 f (xX) N 2 xf (xX) N 2 (xX)2 f (xX)
i=1 N f 2 (xX) N (xX)f 2 (xX) N (xX)2 f 2 (xX)
i=0 f 3 (xX)

On pose

f (x) = a0 + a1 x + a2 x2 + x3 ,
f 2 (x) = b0 + b1 x + b2 x2 + b3 x3 + b4 x4 + b5 x5 + x6 ,
f 3 (x) = c0 + c1 x + c2 x2 + c3 x3 + c4 x4 + c5 x5 + c6 x6 + c7 x7 + c8 x8 + x9 .

Puisque n = δm + t = 10, on forme alors la matrice carrée 10 × 10 définie par (3.6)

en utilisant (3.4) avec m = 3, δ = 3 et (3.5) avec t = 1,

x2 x3 x4 x5 x6 x7 x8 x9
 
1 x
 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 
 
 N3 0 0 0 0 0 0 0 0 0 
 3

 0 XN 0 0 0 0 0 0 0 0 
 2 3

 0 0 X N 0 0 0 0 0 0 0 
 
 a0 N 2 a1 XN 2 a2 X 2 N 2 X 3 N 2 0 0 0 0 0 0 
 2 2 2 3 2 4 2

 0 a0 XN a1 X N a2 X N X N 0 0 0 0 0 
 2 2 3 2 4 2 5 2

 0 0 a0 X N a1 X N a2 X N X N 0 0 0 0 
 
 b0 N b1 XN b2 X 2 N b3 X 3 N b4 X 4 N b5 X 5 N X 6 N 0 0 0 
 
 0 2 3 4 5 6 7
 b0 XN b1 X N b2 X N b3 X N b4 X N b5 X N X N 0 0 

 0 2 3 4 5 6 7 8
0 b0 X N b1 X N b2 X N b3 X N b4 X N b5 X N X N 0 
c0 c1 X c2 X 2 c3 X 3 c4 X 4 c5 X 5 c6 X 6 c7 X 7 c8 X 8 X 9

Maple 3.2.5.
On ne trouve en fait aucune solution car la valeur prise par X est très grande. En
1 1
effet, dans l’inégalité |x0 | < 2− 2 N δ −ε , le rôle de ε peut être très important. En
prenant la valeur X = 500, on trouve x0 = 79.
66 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

Programme Commentaires

with(PolynomialTools): <-- Package Polyn^ omes

with(LinearAlgebra): <-- Package Algèbre Linéaire
with(linalg): <-- Un autre package
with(IntegerRelations): <-- Package LLL
N:=29263868053; <-- La valeur de N
f:=x->x^3-111111110*x^2 <-- La fonction f
-111111110*x-111111111;
d:=degree(f(x),x): <-- Le degré de f
X:=trunc((2^(-1/2)*N^(1/d))): <-- Borne supérieure des solutions
X:=500; <-- Une borne inférieure
m:=3:t:=1: <-- m=3 et t=1
n:=d*m+t: <-- La dimension du réseau
M:=Matrix(n): <-- La matrice (n,n), formée de 0
line:=0: <-- Initiation
for i from 1 to m do <-- Boucle de formation de
i2:=m+1-i: la matrice correspondante
for j from 0 to d-1 do aux polynômes g(i,j),
line:=line+1: qui formera
cc:=CoefficientVector l’entrée pour LLL
(Nî2*X^j*x^(j)*(f(X*x))^(m-i2),x):
for k from 1 to Dimension(cc) do
M[line,k]:=cc[k]:
end do:
end do:
end do: <-- Fin de la boucle
for i from 0 to t-1 do <-- Boucle de formation de
line:=line+1: la matrice correspondante
cc:=CoefficientVector aux polynômes h(i),
(xî*Xî*(f(x*X))^m,x): qui formera
for k from 1 to Dimension(cc) do l’entrée pour LLL
M[line,k]:=cc[k]:
end do:
end do: <-- Fin de la boucle
VM:=[row(M,1..n)]: <-- Formation de la matrice
L := LLL(VM, ’integer’): <-- Réduction de la matrice
h:=0: <--
for i from 0 to n-1 do <-- Formation du polyn^
ome h
h:=h+(L[1,i+1]/Xî)*xî:
end do:
h:
isolve(h); <-- racines entière de h
3.2. CRYPTANALYSE DE RSA PAR LA RÉDUCTION DES RÉSEAUX 67

Magma 3.2.6.
Pour Magma, on peut alors utiliser le code suivant.
Programme Commentaires

F<x> := PolynomialRing (Integers()); <-- Ensemble des polyn^

omes
G<z> := PolynomialRing(Rationals()); <-- Ensemble des polyn^
omes
N:=29263868053; <-- Module
f:=-111111111-111111110*x <-- Fonction
-111111110*x^2+x^3;
d:=Degree(f); <-- Son degré
X:=Truncate((2^(-1/2)*N^(1/d)));X:=500; <-- Borne de Coppersmith
cc:=Coefficients(f); <-- Liste des coefficients de f
f:=0; <-- f=0
for i:=1 to #cc do <-- Polyn^
omes f de Coppersmith
f:=f+cc[i]*x^(i-1)*X^(i-1);
end for;
m:=3;t:=1; <-- Choix m=3 et t=1
n:=d*m+t; <-- Ordre du réseau
M:=RMatrixSpace(IntegerRing(),n,n)!0; <-- Matrice carrée nxn
line:=0; <-- line=0
for i:=1 to m do <-- Boucle de formation de
i2:=m+1-i; la matrice correspondante
for j:=0 to d-1 do aux polynômes g(i,j),
line:=line+1; qui formera
cc:=Coefficients l’entrée pour LLL
(Nî2*X^j*x^(j)*f^(m-i2));
for k:=1 to #(cc) do
M[line,k]:=cc[k];
end for;
end for;
end for;
for i:=0 to t-1 do <-- Boucle de formation de
line:=line+1; la matrice correspondante
cc:=Coefficients(xî*Xî*f^m); aux polynômes h(i),
for k:=1 to #(cc) do qui formera
M[line,k]:=cc[k]; l’entrée pour LLL
end for;
end for;
L := LLL(M); <-- Algorithme LLL
p:=0; <-- p=0
pp:=0; <-- pp=0
68 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

for i:=0 to n-1 do <-- Formation du polyn^

ome h
pp:=pp+L[1,i+1]*zî;
p:=p+(L[1,i+1]/Xî)*zî;
end for;
p;Roots(p); <-- polyn^
ome h et ses racines
On ne trouve en fait aucune solution si la valeur prise par X est très grande. En
effet, dans l’inégalité
1 1
|x0 | < 2− 2 N δ −ε ,
le rôle de ε peut être très important. En prenant X = 500 dans le code ci-dessus,
on obtient alors le polynôme :

h(z/X) = 35819 ∗ z 9 − 8381646 ∗ z 8 + 645386742 ∗ z 7 − 6424486034022 ∗ z 6

+ 999721772296884 ∗ z 5 + 35322490662759665925 ∗ z 4
+ 13772627569229621478757 ∗ z 3 − 1292162362422796441508568 ∗ z 2
− 1292197683913738082645997 ∗ z − 1305934988985879813073884,

de racine 79.
En fait, dans Magma, la méthode de Coppersmith pour résoudre l’équation polyno-
miale
1 1
f (x0 ) ≡ 0 (mod N ), |x0 |X < N d ,
2
est implémentée sous la forme SmallRoots(f,N,X). Dans l’exemple c–dessous, on
veut résoudre l’équation

f (x) = x3 − 111111110 ∗ x2 − 111111110 ∗ x − 111111111 ≡ 0 (mod 29263868053),

avec |x| < 500.

Magma 3.2.7.
programme programme

F<x>:=PolynomialRing(Integers()); <-- Ensemble des polyn^

omes
N:=29263868053; <-- Module
f:=x^3-111111110x^2 <-- Fonction
-111111110x-111111111;
X:=500; <-- Borne
sol:=SmallRoots(f, N, X); <-- Procédure de Coppersmith
sol; <-- Ensemble des solutions
La solution obtenue 79.
3.2. CRYPTANALYSE DE RSA PAR LA RÉDUCTION DES RÉSEAUX 69

3.2.2 Factorisation de N

Une autre application de la méthode de Coppersmith est la factorisation de N = pq

si on connait une fraction importante de p ou de q. Plus précisément, on a le résultat
suivant :

Théorème 3.2.8. Soit N = pq un module RSA dont les facteurs premiers p et q

sont inconnus et tels que q < p. Si on connait une valeur p̃ telle que

1
|p̃ − p| < N 4 ,

alors on peut factoriser N en temps polynômial en log N .

1
Démonstration. Supposons que |p̃ − p| < N 4 . On considère la fonction fp définie
par fp (x) = x + p̃. Alors on a fp (p − p̃) = p ≡ 0 mod p. Ainsi, x0 = p − p̃ est un
entier qui vérifie
1
fp (x0 ) ≡ 0 mod p, |x0 | < N 4 .

1
On peut donc appliquer le théorème 3.2.2 avec b = p > N 2 , en prenant β = 12 .

Maple 3.2.9.

Voici un exemple dans lequel N = 2535301200456606295881202795651 est de la

forme N = pq. On donne aussi une approximation p0 = 1125899907822525 de p
1
et on sait que |p − p0 | < N 4 . Dans le programme maple ci-dessous, la borne du
théorème 3.2.2 avec ε = 0 s’est avérée assez grande et ne donne aucune réponse. En
prenant la borne
3 1
X < 2− 2 N 4 .

On obtient alors une réponse avec le choix m = 2 et t = 2 car le choix t = 1 ne

donne pas de solution non plus. On obtient alors la réponse x0 = −979846, ce qui
donne p = p0 + x0 = 1125899906842679.
70 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

Programme Commentaires

with(PolynomialTools): <-- Package Polyn^ omes

with(LinearAlgebra): <-- Package Algèbre Linéaire
with(linalg): <-- Un autre package
with(IntegerRelations): <-- Package LLL
p := nextprime(2^50): <-- Le nombre premier p
q := nextprime(2^51): <-- Le nombre premier q
N:=p*q; <-- Le module RSA
p0 := p+979846: <-- Une approximation de p
f := x->x+p0: <-- La fonction f
d:=degree(f(x),x): <-- Son degré
b:=1/2: <-- L’exposant beta=1/2
X:=trunc((2^(-3/2)*N^(b^2/d))): <-- Borne supérieure des solutions
m:=2:t:=2: <-- m=2 et t=2
n:=d*m+t: <-- La dimension du réseau
M:=Matrix(n): <-- La matrice (n,n), formée de 0
line:=0: <-- Initiation
for i from 1 to m do <-- Boucle de formation de
i2:=m+1-i: la matrice correspondante
for j from 0 to d-1 do aux polyn^ omes g(i,j),
line:=line+1: qui formera
cc:=CoefficientVector l’entrée pour LLL
(Nî2*X^j*x^(j)*(f(X*x))^(m-i2),x):
for k from 1 to Dimension(cc) do
M[line,k]:=cc[k]:
end do:end do:end do: <-- Fin de la boucle
for i from 0 to t-1 do <-- Boucle de formation de
line:=line+1: la matrice correspondante
cc:=CoefficientVector aux polynômes h(i),
(xî*Xî*(f(x*X))^m,x): qui formera
for k from 1 to Dimension(cc) do l’entrée pour LLL
M[line,k]:=cc[k]:
end do:
end do: <-- Fin de la boucle
VM:=[row(M,1..n)]: <-- Formation de la matrice
L := LLL(VM, ’integer’): <-- Réduction de la matrice
h:=0: <-- Formation du polyn^
ome h
for i from 0 to n-1 do
h:=h+(L[1,i+1]/Xî)*xî:
end do:
isolve(h); <-- racines entière de h
3.2. CRYPTANALYSE DE RSA PAR LA RÉDUCTION DES RÉSEAUX 71

Magma 3.2.10.
On reprend le même exemple avec N = pq = 2535301200456606295881202795651.
On donne aussi une approximation p0 = 1125899907822525 de p et on sait que
1
|p − p0 | < N 4 . Dans le programme ci-dessous, la borne du théorème 3.2.2 avec ε = 0
s’est avérée assez grande et ne donne aucune réponse. En prenant la borne
3 1
X < 2− 2 N 4 .
On obtient alors une réponse avec le choix m = 2 et t = 2 car le choix t = 1 ne
donne pas de solution non plus. On obtient alors la réponse x0 = −979846, ce qui
donne p = p0 + x0 = 1125899906842679.
Programme

F<x> := PolynomialRing (Integers());G<z> := PolynomialRing(Rationals());

p := NextPrime(2^50);q := NextPrime(2^51);N:=p*q;
p0 := p+979846;f:=x+p0;d:=Degree(f);
b:=1/2;X:=Truncate((2^(-3/2)*N^(b^2/d)));cc:=Coefficients(f);f:=0;
for i:=1 to #cc do f:=f+cc[i]*x^(i-1)*X^(i-1); end for;
m:=2;t:=2;n:=d*m+t;M:=RMatrixSpace(IntegerRing(),n,n)!0;line:=0;
for i:=1 to m do
i2:=m+1-i;
for j:=0 to d-1 do
line:=line+1;
cc:=Coefficients
(Nî2*X^j*x^(j)*f^(m-i2));
for k:=1 to #(cc) do
M[line,k]:=cc[k];
end for;end for;end for;
for i:=0 to t-1 do
line:=line+1;cc:=Coefficients(xî*Xî*f^m);
for k:=1 to #(cc) do M[line,k]:=cc[k];end for;
end for;
L := LLL(M);h:=0;pp:=0;
for i:=0 to n-1 do pp:=pp+L[1,i+1]*zî; h:=h+(L[1,i+1]/Xî)*zî;end for;
h;Roots(h);
On obient le polynôme
h(z) = 2z 3 +2251799819564523z 2 +4412934291333159103051z+2162047098651212289960978150,
et les solutions
[< −1125899907822525, 1 >, < −1959781/2, 1 >, < −979846, 1 >].
Alors p0 − 979846 = p.
72 CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL
Bibliographie

[1] D. Boneh, G. Durfee. Cryptanalysis of RSA with private key d less than N 0.292 ,
Advances in Cryptology – Eurocrypt’99, Lecture Notes in Computer Science
Vol. 1592, Springer-Verlag, 1—11 (1999).
[2] D. Coppersmith. Small solutions to polynomial equations, and low exponent
RSA vulnerabilities. Journal of Cryptology, 10(4), 233—260 (1997).
[3] G.H. Hardy, E.M. Wright. An Introduction to the Theory of Numbers.
Oxford University Press, London (1965).
[4] A. K. Lenstra, H. W. Lenstra, and L. Lovasz. Factoring polynomials with ra-
tional coefficients, Mathematische Annalen, Vol. 261, pp. 513—534, 1982.
[5] A. May. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD the-
sis, University of Paderborn (2003)
http://wwwcs.upb.de/cs/ag-bloemer/personen/alex/publikationen/
[6] R. Rivest, A. Shamir, L. Adleman. A method for obtaining digital signatures
and public-key cryptosystems, Communications of the ACM, Vol. 21 (2), 120—
126 (1978).
[7] M. Wiener. Cryptanalysis of short RSA secret exponents, IEEE Transactions
on Information Theory, Vol. 36, 553—558 (1990).

Vous aimerez peut-être aussi

Cryptanalyse du système RSA
Pas encore d'évaluation
Cryptanalyse du système RSA
76 pages
Cryptanalyse RSA par Coppersmith
Pas encore d'évaluation
Cryptanalyse RSA par Coppersmith
16 pages
Cryptographie et Signature RSA
Pas encore d'évaluation
Cryptographie et Signature RSA
40 pages
Introduction à l'algorithme RSA
Pas encore d'évaluation
Introduction à l'algorithme RSA
22 pages
Cours RSA
Pas encore d'évaluation
Cours RSA
21 pages
Introduction à RSA et tests de primalité
Pas encore d'évaluation
Introduction à RSA et tests de primalité
12 pages
Traveux Pratique: Ministère de L'enseignement Supérieur Et de La Recherche Scientifique
Pas encore d'évaluation
Traveux Pratique: Ministère de L'enseignement Supérieur Et de La Recherche Scientifique
23 pages
Introduction au RSA : Cryptographie Moderne
Pas encore d'évaluation
Introduction au RSA : Cryptographie Moderne
17 pages
Chap 2 Cryptosystemes RSA
Pas encore d'évaluation
Chap 2 Cryptosystemes RSA
6 pages
Exposé
Pas encore d'évaluation
Exposé
3 pages
Cours8 RSA ECC
Pas encore d'évaluation
Cours8 RSA ECC
13 pages
Rsa Expose
Pas encore d'évaluation
Rsa Expose
27 pages
RSA : Algorithme de Cryptographie Asymétrique
Pas encore d'évaluation
RSA : Algorithme de Cryptographie Asymétrique
21 pages
Cryptographie Asymétrique Simplifiée
Pas encore d'évaluation
Cryptographie Asymétrique Simplifiée
50 pages
Sec Chiff Asym Part2
Pas encore d'évaluation
Sec Chiff Asym Part2
18 pages
Ch3 Info Security Cryptographie Asymétrique
Pas encore d'évaluation
Ch3 Info Security Cryptographie Asymétrique
21 pages
Algorithmes et Cryptographie RSA
Pas encore d'évaluation
Algorithmes et Cryptographie RSA
58 pages
Cryptologie et Algorithmes à Clé Publique
Pas encore d'évaluation
Cryptologie et Algorithmes à Clé Publique
54 pages
2024 05 16 Notebook 2
Pas encore d'évaluation
2024 05 16 Notebook 2
4 pages
Choix Des Cles Rsa: Exemple
Pas encore d'évaluation
Choix Des Cles Rsa: Exemple
3 pages
Cryptographie à clé publique expliquée
Pas encore d'évaluation
Cryptographie à clé publique expliquée
43 pages
Attaque Rsa 2005 7
Pas encore d'évaluation
Attaque Rsa 2005 7
3 pages
Mécanismes de la cryptographie asymétrique
Pas encore d'évaluation
Mécanismes de la cryptographie asymétrique
29 pages
Examen INFO0603 : Compression et Cryptographie
Pas encore d'évaluation
Examen INFO0603 : Compression et Cryptographie
4 pages
Chapitre 3 - L3 - 2023 1
Pas encore d'évaluation
Chapitre 3 - L3 - 2023 1
6 pages
Cle Publique
Pas encore d'évaluation
Cle Publique
34 pages
RSA Part1
Pas encore d'évaluation
RSA Part1
25 pages
Chiffr RsA
100% (1)
Chiffr RsA
6 pages
Présentation de la cryptographie RSA
Pas encore d'évaluation
Présentation de la cryptographie RSA
15 pages
TD2: Algorithme RSA et Calcul de Clés
Pas encore d'évaluation
TD2: Algorithme RSA et Calcul de Clés
2 pages
Chapitre 3 Nathan 20240615 - 222911
Pas encore d'évaluation
Chapitre 3 Nathan 20240615 - 222911
13 pages
Asymetrique
Pas encore d'évaluation
Asymetrique
54 pages
Cours sur le cryptosystème RSA
Pas encore d'évaluation
Cours sur le cryptosystème RSA
20 pages
CryptoClePublique2021 Slides 2
Pas encore d'évaluation
CryptoClePublique2021 Slides 2
37 pages
Introduction à la cryptographie TIPE
Pas encore d'évaluation
Introduction à la cryptographie TIPE
9 pages
Chapitre 2 Partie 1 2024-2025
Pas encore d'évaluation
Chapitre 2 Partie 1 2024-2025
18 pages
TP sur le cryptosystème RSA avec SageMath
Pas encore d'évaluation
TP sur le cryptosystème RSA avec SageMath
2 pages
Chiffrement A Cle Asymetrique
Pas encore d'évaluation
Chiffrement A Cle Asymetrique
28 pages
Exercices de Chiffrement RSA
Pas encore d'évaluation
Exercices de Chiffrement RSA
4 pages
La Cryptographie Asymetrique Avec Rsa
Pas encore d'évaluation
La Cryptographie Asymetrique Avec Rsa
48 pages
Crypto
Pas encore d'évaluation
Crypto
126 pages
Chiffrement Asymetrique Et RSA
Pas encore d'évaluation
Chiffrement Asymetrique Et RSA
6 pages
Cryptographie
Pas encore d'évaluation
Cryptographie
12 pages
CC2 Crypto
Pas encore d'évaluation
CC2 Crypto
8 pages
M1 Ice Rsa
Pas encore d'évaluation
M1 Ice Rsa
8 pages
Cryptage RSA
Pas encore d'évaluation
Cryptage RSA
3 pages
Cryptographie et Sécurité des Réseaux
Pas encore d'évaluation
Cryptographie et Sécurité des Réseaux
36 pages
Sec TD Chiff Asym
Pas encore d'évaluation
Sec TD Chiff Asym
1 page
Cer Cryptographie 3
Pas encore d'évaluation
Cer Cryptographie 3
26 pages
Cryptograph I Ers A
Pas encore d'évaluation
Cryptograph I Ers A
7 pages
TD2 PDF
100% (1)
TD2 PDF
3 pages
Rsa 2022
Pas encore d'évaluation
Rsa 2022
6 pages
Feuille 3: RSA: X Z/NZ en X Z/nZ. Puis On Déchiffre y Z/NZ Par y Z/NZ Pour A Z Tel
Pas encore d'évaluation
Feuille 3: RSA: X Z/NZ en X Z/nZ. Puis On Déchiffre y Z/NZ Par y Z/NZ Pour A Z Tel
4 pages
Introduction à l'arithmétique modulaire
Pas encore d'évaluation
Introduction à l'arithmétique modulaire
5 pages
Chapitre II
Pas encore d'évaluation
Chapitre II
15 pages
Cours Crypto 070206
Pas encore d'évaluation
Cours Crypto 070206
126 pages
Presentation Article 8
Pas encore d'évaluation
Presentation Article 8
16 pages
MainFeatures FR
Pas encore d'évaluation
MainFeatures FR
1 page
EFS SMA Master 2013
Pas encore d'évaluation
EFS SMA Master 2013
4 pages
Billet 5078538196
Pas encore d'évaluation
Billet 5078538196
1 page
T Pe First Follows
Pas encore d'évaluation
T Pe First Follows
11 pages
Polycopie Crypto-2008
Pas encore d'évaluation
Polycopie Crypto-2008
45 pages
Langage LL-2
Pas encore d'évaluation
Langage LL-2
14 pages
La Playa GUITARRA
100% (1)
La Playa GUITARRA
2 pages
Memoire Satisfaction Des Clients Cas Des
Pas encore d'évaluation
Memoire Satisfaction Des Clients Cas Des
77 pages
Fiche D'intervention Culasse
Pas encore d'évaluation
Fiche D'intervention Culasse
1 page
Problématiques du Système d'Information DISTRIB
Pas encore d'évaluation
Problématiques du Système d'Information DISTRIB
9 pages
Dixell Espagne XR75CX SP r1 0 27 02 2009
Pas encore d'évaluation
Dixell Espagne XR75CX SP r1 0 27 02 2009
6 pages
01.1 - Vitoplex 300 TX3A 405 KW
Pas encore d'évaluation
01.1 - Vitoplex 300 TX3A 405 KW
16 pages
Distillation Avancée en Génie Chimique
Pas encore d'évaluation
Distillation Avancée en Génie Chimique
2 pages
Exo 3 en 1
Pas encore d'évaluation
Exo 3 en 1
2 pages
Maths 3e
Pas encore d'évaluation
Maths 3e
101 pages
ELEC84 Citelis
Pas encore d'évaluation
ELEC84 Citelis
66 pages
Innovation et Créativité Entrepreneuriale
Pas encore d'évaluation
Innovation et Créativité Entrepreneuriale
31 pages
Décrets et Arrêtés Tunisiens du 13 Juin 2023
Pas encore d'évaluation
Décrets et Arrêtés Tunisiens du 13 Juin 2023
24 pages
Techniques d'Extinction des Incendies
Pas encore d'évaluation
Techniques d'Extinction des Incendies
28 pages
6ème ES5-INFO
Pas encore d'évaluation
6ème ES5-INFO
1 page
Exercice Ou Activités Sur Les Systèmes D'équations
Pas encore d'évaluation
Exercice Ou Activités Sur Les Systèmes D'équations
5 pages
Composition 2 1am 2020
100% (2)
Composition 2 1am 2020
2 pages
Chapitre 1 Les Treillis Ou Systèmes Triangulés
100% (2)
Chapitre 1 Les Treillis Ou Systèmes Triangulés
12 pages
SDR à Conversion Directe : Fonctionnement et Évaluation
Pas encore d'évaluation
SDR à Conversion Directe : Fonctionnement et Évaluation
83 pages
Controle Microcontroleur
Pas encore d'évaluation
Controle Microcontroleur
6 pages
PROMO7 L1SEM.1 - VF CALENDRIER Réaménagé À Nouveau Des Examens Du Sem.1
Pas encore d'évaluation
PROMO7 L1SEM.1 - VF CALENDRIER Réaménagé À Nouveau Des Examens Du Sem.1
3 pages
Guide des ACLs pour la sécurité réseau
Pas encore d'évaluation
Guide des ACLs pour la sécurité réseau
22 pages
01-Réservation D'hôtel
100% (1)
01-Réservation D'hôtel
2 pages
Fiche Technique PRH 12-750
Pas encore d'évaluation
Fiche Technique PRH 12-750
2 pages
POO pour BTS SNIR : Concepts Clés
Pas encore d'évaluation
POO pour BTS SNIR : Concepts Clés
17 pages
Rapport de Stage Projet Web 3
Pas encore d'évaluation
Rapport de Stage Projet Web 3
17 pages
Guide complet sur l'entrepreneuriat et l'innovation
Pas encore d'évaluation
Guide complet sur l'entrepreneuriat et l'innovation
4 pages
Gestion de La Relation Client Et Marketing Direct 1
Pas encore d'évaluation
Gestion de La Relation Client Et Marketing Direct 1
8 pages
Oscillateur de Clapp
Pas encore d'évaluation
Oscillateur de Clapp
5 pages
Impédance Z en Courant Alternatif
Pas encore d'évaluation
Impédance Z en Courant Alternatif
19 pages
Mid 039 - Cid 0017 - Fmi 05 (Kenr5924-14) Sis2.0
Pas encore d'évaluation
Mid 039 - Cid 0017 - Fmi 05 (Kenr5924-14) Sis2.0
4 pages