CRYPTANALYSE DE RSA
Abderrahmane Nitaj
Laboratoire de Mathématiques Nicolas Oresme
Université de Caen, France
http://www.math.unicaen.fr/~nitaj
nitaj@math.unicaen.fr
c Version du 28 juin 2009

Table des matières
ContenuiPréface

1

1 Introduction au cryptosystème RSA

3

1.1

1.2

1.3

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

Un exemple d’utilisation de RSA . . . . . . . . . . . . . . . . . . . . 12
1.2.1

Transformation d’un texte en nombres . . . . . . . . . . . . . 12

1.2.2

L’exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

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

2 Cryptanalyse de RSA par les fractions continues
2.1

21
25

Les fractions continues . . . . . . . . . . . . . . . . . . . . . . . . . . 25i

ii

TABLE DES MATIÈRES

2.2

2.1.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.1.2

Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . 26

Cryptanalyse de RSA par les fractions continues . . . . . . . . . . . . 37
2.2.1

L’attaque de Wiener . . . . . . . . . . . . . . . . . . . . . . . 38

3 Cryptanalyse de RSA par l’algorithme LLL
3.1

3.2

43

L’algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.1

Introduction aux réseaux . . . . . . . . . . . . . . . . . . . . . 43

3.1.2

L’algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . 50

Cryptanalyse de RSA par la réduction des réseaux . . . . . . . . . . . 59
3.2.1

La méthode de Coppersmith : polynômes à une variable

3.2.2

Factorisation de N . . . . . . . . . . . . . . . . . . . . . . . . 69

Bibliographie. . . 5973

Préface
Si vous enseignez à un homme, vous n’enseignez qu’à une
personne. Si vous enseignez à une femme, vous enseignez à touteune famille.

 Ê« Y® ¯ è @QÓ@ IÒ Ê« @ X@ AÓ @ , @ XQ ¯ IÒ Ê« Y® ¯ Cg. P IÒ Ê« @ X@
. éÊ K A« IÒ
La cryptographie moderne est basée sur les mathématiques pour sécuriser l’information. On distingue deux types de protocoles cryptographiques : la cryptographieà 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 naissance de la cryptographie moderne. Le principe de la cryptographie à clé publiquerepose sur deux types de clés : une clé publique et une clé privée. Pour chiffrer unmessage, on utilise la clé publique de son destinataire. Alors, seul le destinataire peutdé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 desproblè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́ sontmal 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 etnous présentons quelques attaques élémentaires permettant de le casser. Dans lechapitre 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. Dansle 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 programmé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 dansles trous.

Abou Al Qasim Achabi YK @ ª. Q®mÌ '@ áK. Që YË@
.  K

1.1

È AJ.m.Ì '@ Xñª I. m' B áÓ ð  ñK @
Õæ A®Ë@úG. AË@.

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́durede chiffrement et de signature et une procédure de déchiffrement et de vérificationde 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: Sinon6:
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 pm2:=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
Programme

5
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 RSAN;<----- 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 modulee:=3;<--- L’exposant publique
N:=RSAModulus(t,e); <--- Création du moduleN;<--- Affichage de N
f:=Factorization(N); <--- Sa factorizationf;<--- Affichage de la factorisation
Log(N)/Log(2);<--- Taille du module
p:=f[1,1];<--- Premier nombre premierq:=f[2,1];<--- Deuxième nombre premierp;<--- Affichage de pq;<--- Affichage de p

1.1.2

Les clés publiques et privéesAprè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, parexemple e = 3 ou e = 216 + 1. Dans ce cas, les étapes 2 à 5 de l’algorithme 2 ne sontpas exécutées.
La fonction φ joue un rôle central dans le cryptosystème RSA et s’appelle la fonctiond’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: Sinon6:
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
sYn=pxi i ,
i=1

alors on a :φ(n) =sY

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

Commentaireswith(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
N:=5*8*61:
EulerPhi(N);
Maple 1.1.6.

Commentaires<--- un exemple simple<--- Calcul de phi(N)1.1. PRINCIPE DE RSA

7

Avec Maple 12, l’algorithme 2 peut être écrit comme ceci où on suppose que laprocé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 eod;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);<-- phie:=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 phid;<-- 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 ledé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 lesuivant.
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

9Magma 1.1.11.
Avec Magma, l’algorithme 4 qui permet de déchiffrer un message C peut être lesuivant.
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 quele 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 pourA 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 faitde 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 lasignature 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 peutê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 signatureprint(’Signature valide’)
else
print(’Signature non valide’)
end ifMagma 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 signatureprint("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 , alorsaφ(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 RSAoù 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 )

Y

Y

i=1

ai =

i=1

φ(N )

aai ≡ a

φ(N )

Y

ai

(mod N ).

i=1

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

1.2

Qφ(N )
i=1

ai est inversible

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 lemessage 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̀ lalettre a, la valeur 2 à la lettre b,..., et la valeur 26 à la lettre z et travailler ainsi enmode 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 informatique des caractères alphanumériques de l’alphabet latin. Dans la table ci-dessous,
on a représenté quelques correspondances.
Caractère
CodeMaple 1.2.1.

a
A
b
z
0
1
097 065 098 122 048 049

2 ”espace” à
050
32
224

+
43

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 BinaryString(”texte en caractères”) ou BString(”texte en caractères”). Inversement, la fonction qui transforme un code ASCII n en caractère est CodeToString(n). Voici un exemple
Programme

Programmes:="Je suis à c^oté" ;<--- Le textes;<--- Son affichage
t:=BString(s);<--- Transformation en code ASCIIt;<--- 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;<--- Affichage du texte Je suis à c^
oté
u;

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 determes 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 dedeux 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 ainsip(N + 1 − ϕ(N ))2 − 4N
p =
,
p 2
N + 1 − ϕ(N ) − (N + 1 − ϕ(N ))2 − 4N
q =.
2
N + 1 − ϕ(N ) +Maple 1.3.2.
Avec Maple 12, cette attaque peut être programmée comme dans l’exemple suivantoù on utilise la fonction solve qui permet de résoudre une équation.
Programme

Commentaires

p := 67676767676789:<--- Le premier nombre premierq := 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 suivantoù on utilise la fonction Roots qui permet de résoudre une équation.
Programme
Commentaires
P<x> := PolynomialRing(IntegerRing());
p := 67676767676789;<--- Le premier nombre premierq := 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
C2 ≡ M e 2(mod N ),(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
1
1
|e1 x1 − e2 x2 |
−
=
< 2.
=
e2 x1
x1 e 1x1 e1
2x1
Ainsi x1 et x2 peuvent être déterminés comme dénominateur et numérateur de l’unedes 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 publiquee2:=787654321187:<--- Le deuxième exposant publiqueigcdex(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 publiquee2:=787654321187;<--- Le deuxième exposant publiqueg,x1,x2:=XGCD(e1,e2);<--- L’algorithme d’Euclideg;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 message.

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 produiresi 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 ),kkQk
admet une solution unique modulo N = i=1 Ni . Cette solution estx≡kXai pi Mi(mod N ),i=1

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

Q
Démonstration. Soit N = ki=1 Ni , pi = NNi et Mi ≡ p−1(mod Ni ). Alors, pourichaque i, 1 ≤ i ≤ k, on a pi Mi ≡ 1 (mod Ni ) et Ni |pj si i 6= j. Ainsi, avecPx ≡ ki=1 ai pi Mi (mod N ), on a pour 1 ≤ i ≤ k, en considérant x modulo Ni :x ≡ ai pi Mi +

k
X
j6=i

aj pj Mj ≡ ai +

k
X
j6=i

aj Mj Ni ×

pj
≡ ai
Ni

(mod 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 ax0 − 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 chinoisx;<--- 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 chinoisx;<--- 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
chiffrés du même message clair M à l’aide du mêmeQke
exposant e. Si m < i=1 Ni alors on peut déterminer le message clair M sansfactoriser les modules.
Démonstration. Supposons que le même message clair M est chiffré k fois par
Ci ≡ M e(mod Ni ),Q
pour i = 1, · · · , k. Soit N = ki=1 Ni . On peut appliquer le Théorème des Restes
Chinois pour résoudre le système formé des k équationsx ≡ 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
Programme

21

Programmeb:=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;<--- Le message claire
M:=5454321115654321;<--- Création d’un tableau C
C := AssociativeArray();<--- Création des 4 messages chiffrésfor i:=1 to 4 do
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]]);<--- Calcule de x^(1/e)
M2:=Round((x^(1/e)));<--- Vérification des messages
M2-M;

1.3.4

Cryptanalyse de RSA si |p − q| < cN 1/4 : Méthode deFermatDans 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 qvé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
p=

x+y
,
2

q=

x−y
.
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 √ ix2 = 2 N + 2, · · · et on teste si 4N − x2 est un carré parfait. On désigne alors

22

CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSAh √ 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 Nh √ 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 nedé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 programmesuivant 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 premiersde 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):<--- Module RSA
N := p*q:c := trunc(abs(p-q)/N^0.25)+1: <--- Rapport<--- Entier le plus prochen := round(2*sqrt(N)):<--- Compteur
k := 0:<--- Boucle de Fermat
while k < (1/2)*c^2+1 do<--- Une valeur pour x
x := n+k:
y := round(sqrt(x^2-4*N)): <--- La valeur de y<--- Un candidat pour qs := round((x+y)/2):<--- pgcd
if gcd(s, N) > 1 thenprint(’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 detaille 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 premiersde N .

24

CHAPITRE 1. INTRODUCTION AU CRYPTOSYSTÈME RSA
Programme

Programmet := 100;<--- Taille du module
x1 := Round(2^((1/2)*t));<--- Valeur minimale du nombre premierx2 := Round(2^((t+1)*(1/2)));<--- Valeur maximale du nombre premierm1 := Random(x1,x2);<--- Valeur aléatoire
p := NextPrime(m1);<--- Premier nombre premierm2 := Round(p+10*2^(t/4));<--- Valeur aléatoireq := 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́partk := 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 ys := Round((x+y)/2);<--- Valeur candidate pour p
if GCD(s, N) gt 1 thenprintf("Un facteur est ");s;<--- Arr^et de la boucle
break;
end if;k := k+1;<--- Fin de la boucle
end while;
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 lacolère.

Antara Ibno Shaddad Al Absy éK. @ñÊªK áÓ Y®m Ì '@ ÉÒm' B ð
I.KQË@2.1

Les fractions continues

2.1.1

Introduction

I.ªË@ éªJ.£ áÓ CªË@ ÈAJK B
úæJ.ªË@ X@ Y  áK. @ èQJ«√
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
ici, c’est la√ finie, s’appelle une fraction continue,√
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[6] = 6,[6, 6] = 6 +1
37=≈ 6, 166666...,6
625

26CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES[6, 6, 6] = 6 +

1
1
6+
6

=

1

[6, 6, 6, 6] = 6 +

=

1

6+

6+

228
≈ 6.162162...,371405≈ 6.162280...,
228

1
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|6 − x| >

37
228
1405
−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́sThéorème 2.1.1. Tout nombre réel positif x a une écriture unique comme fraction
continue :1= [a1 , a2 , a3 , · · · ],x = a0 +
1
a1 +
1
a2 +
1
a3 +
..
.
où les ai sont des entiers positifs. De plus, la fraction continue est finie si et seulement si le nombre x est rationnel.
Démonstration. Soit x un nombre réel positif. On pose x0 = x. On considère lapartie entière a0 = [x0 ]. Si x0 est un entier, a0 = x0 et la fraction continue de x est
x = [a0 ].
1> 1.
Supposons que x n’est pas un entier. Dans ce cas, on a 0 < x0 − a0 < 1 et x0 −a0
Puisque x0 = a0 + (x0 − a0 ), on définie x1 par

x1 =

1
> 1,
x 0 − a0ce qui donne
x 0 = a0 +1.
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
x = a0 +1
a0 + a1=,
a1
a1

qui représente un nombre rationnelle. Si x1 , n’est pas un entier, en recommence leprocessus en définissant x2 par1> 1,
x 1 − a1x2 =ce qui donne

1x 0 = a0 +

a1 +

1
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 +
a3 +

1
..

.+

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’ pourafficher la fraction continue sous la forme [a0 , a1 , a2 , · · · , an ], ce qui correspond à la
1notation standard. Voici un exemple pour calculer la fraction continue de x = 1+7 3 .

28CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUESProgramme

Commentaire

restart:<--- Remise à zérowith(numtheory):<--- Fonctionnalités "Théorie des Nombres"
Digits:=100:<--- Précision
x:=1+7^(1/3):<--- Un nombre réeln:=30:<--- nombre de quotients partiels
s:=cfrac(x,n,’quotients’): <--- Calcul de la fraction continues;<--- 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 , · · · ], estcommence 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 partielss;<--- 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
=
= .
a1
a1
q1
1
p2
a0 a1 a2 + a0 + a2
[a0 , a1 , a2 ] = a0 += .
=1
a1 a2 + 1
q2
a1 +
a2
On observe facilement que[a0 , a1 ] = a0 +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 conventionp−2 = 0,q−2 = 1,p−1 = 1,q−1 = 0.

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

Démonstration. La preuve se fait par récurrence sur n. On a déjà vu que [a0 ] = pq00 .
Supposons que
pn = an pn−1 + pn−2 ,qn = an qn−1 + qn−2 ,et que [a1 , a2 , a3 , · · · , an ] = pqnn . Alors, on a aussi, en utilisant la récurrence.
1[a1 , a2 , a3 , · · · , an , an+1 ] = [a1 , a2 , a3 , · · · , an +
]
an+1


1
pn−1 + pn−2
an + an+1= 
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 + 1ème convergente d’une liste s de convergente est nthconver(s,n). Le numérateur etle dénominateur sont alors nthnumer(s,n) et nthdenom(s,n). Voici un exemple
1dans 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́rowith(numtheory):<--- Fonctionnalités "Théorie des Nombres"
Digits:=100:<--- Précision
x:=1+7^(1/3):<--- Un nombre réels:=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 Convergents(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 partielsc;<--- Affichage de la liste
s:=[];<--- Initialisationn:=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];<--- p7t[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 desnumérateurs et dénominateurs des convergentes.

2.1. LES FRACTIONS CONTINUESProgramme

31
Commentaires

x:=1+7^(1/3);<--- La valeur xx;<--- Sa valeur décimale
s:=ContinuedFraction(x); <--- Liste des quotients partielss;<--- 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 boucleN;<--- Affichage de N
D;<--- Affichage de D
n:=7;<--- 7ème convergenteN[n];<--- NumérateurD[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 lesconvergentes 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̀reégalité. Pour n = −2, on a bienp−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.
1Vé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):<--- liste des quotients partiels
s:=cfrac(x,100,’quotients’):<--- Numérateurs des convergentes
nu:=i->nthnumer(s,i):<--- Dénominateurs des convergentes
de:=i->nthdenom(s,i):<--- Un indice quelconquen:=7;
r:=nu(n)*de(n+1)-nu(n+1)*de(n): <--- Première égalité<--- Différence (nulle)(-1)^(n+1)-r;<--- Un indice quelconquen:=10;
r:=nu(n)*de(n+2)-nu(n+2)*de(n); <--- Deuxième égalité<--- Différence (nulle)(-1)^(n+1)*s[n+3]-r;

Magma 2.1.10.
1

On vérifie maintenant le théorème 2.1.8 avec les convergentes de x = 1 + 7 3 pourn = 7 avec magma. Attention au décalage de l’exposant de −1 puisque Magmacommence les quotients partiels par a1 et non par a0 .

2.1. LES FRACTIONS CONTINUESProgramme

33
Programme

x:=1+7^(1/3);<--- Valeur de x
c:=ContinuedFraction(x);<--- Liste des quotients partiels
s:=[];<--- Initiationt:=[];<--- 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=7p1:=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;<--- p7 et p9
p1:=t[n][1,1];p3:=t[n+2][1,1];<--- q7 et q9
q1:=t[n][2,1];q3:=t[n+2][2,1];<--- Vérification, réponse nulle
p1*q3-p3*q1-(-1)^(n+2)*c[n+2];
Corollaire 2.1.11. Les convergentes pqnn d’un nombre réel x vérifient pgcd(pn , qn ) =1 pour tout n ≥ 0.
n+1
Démonstration. Supposons que pqn+1
existe. Alors, d’après Théorème 2.1.8, on an+1
pn qn+1 − qn pn+1 = (−1)
et donc pgcd(pn , qn ) = 1.
2n
et d’indices impairsThéorème 2.1.12. La suite des convergentes d’indices pairs pq2n
p2n+1d’un nombre irrationnel positif x vérifient :
q2n+1

p2n−2
p2n
p2n+1
p2n−1
<
<x<
<
.
q2n−2
q2n
q2n+1
q2n−1
2n+1
2n
< pq2n+1. En
Démonstration. Démontrons d’abord que pour tout n ≥ 0, on a pq2neffet, 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
2n−2
2n< pq2n. On a, en utilisantDémontrons maintenant que pour tout n ≥ 0, on a pq2n−2
le théorème 2.1.8 :p2n−2 p2np2n−2 q2n − p2n q2n−2(−1)2n−1 a2n
−
=
=
< 0.
q2n−2
q2n
q2n−2 q2nq2n−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
2n+1
2n−1
ce qui donne pq2n+1< pq2n−1.
2n+1
2n
Il reste à démontrer que les deux inégalités pq2n
< x et x < pq2n+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 :x−xn+1 pn + pn−1 pn
pn−1 qn − pn qn−1
(−1)n
pn
=
−
=
=
.
qn
xn+1 qn + qn−1
qn
qn (xn+1 qn + qn−1 )qn (xn+1 qn + qn−1 )2n+12nAinsi, on obtient x − pq2n
> 0 et x − pq2n+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, alorsles 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 duthéorème 2.1.12, pour n ≥ 0,
qn x − pn =(−1)n,xn+1 qn + qn−1

qn+1 x − pn+1 =(−1)n+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
avec xn+2 > 1, on aEn écrivant xn+1 = an+1 + xn+2

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

Proposition 2.1.14. Si x = [a1 , a2 , a3 , · · · ], alors les convergentes pqnn de x vérifientpour tout n ≥ 0,
pn
1
.
x−
<
qn
qn qn+1Dé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
x−

pn
1
1
1
<
=
,
=
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 irrationnel x, alors il existe une infinité de nombres rationnels pq tels que
x−

1
p
< 2.
q
q

Démonstration. Puisque qn < qn+1 , alors, en utilisant la proposition 2.1.14, on obtient pour toutes les convergents pqnn de x on a
x−

pn
1
1
<
< 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
x−

p
1
< 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 etp
un nombre rationnel.
q
1. Si q < qn+1 , alors |qn x − pn | ≤ |qx − p|.
2. Si q ≤ qn , alors x − pqnn ≤ x − pq .

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 donca = (−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 .
- Si b = 0, alors p = apn et q = aqn , ce qui donne x − pqnn = x − pq .
- 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 alorsqx − 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 , alorsx−|qx − p||qn x − pn |
pn
p
=
≥
= 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’unnombre 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, alorspour n ≥ 0, on a
x−

pn
1
< 2
qn
2qn

ou

x−

pn+1
1
< 2 .
qn+1
2qn+1

2.2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

37

n+1
Démonstration. On sait par le corollaire 2.1.13 que x − pqnn et x − pqn+1
sont de signes
contraires. Alorspn pn+1
pn
pn+1
−
= x−
+ x−
qn
qn+1
qn
qn+1

2
Or, en utilisant le théorème 2.1.8 et l’inégalité 2qn qn+1 < qn2 + qn+1
, on obtient :pn pn+1
1
1
1−=< 2 + 2 .
qn
qn+1
qn qn+1
2qn 2qn+1
Ainsi
x−

pn
pn+1
1
1
+ x−
< 2 + 2 .
qn
qn+1
2qn 2qn+1

n+1
Ceci montre alors que x − pqnn < 2q12 ou x − pqn+1< 2q21 .
nn+1

On termine avec le théorème suivant, très utile pour reconnaitre les convergentes
d’un nombre réel.
Proposition 2.1.18. Si x est un nombre réel. Si pq est un nombre rationnel quivérifie
p
1
< 2,
x−
q
2q
alors pq 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 unentier n ≥ 0. On a alors, en utilisant le théorème 2.1.16 et l’hypothèse x − pq < 2q12 ,
pn
p
1
p pn
p
−
≤
−x + x−
≤2 x−
< 2
q qn
q
qn
q
q
Il en résulte que|pqn − pn q| <

qn
≤ 1.
q

Ainsi, pqn − pn q = 0 et donc pq = pqnn .

2.2

Cryptanalyse de RSA par les fractions continues

Dans cette partie, nous considérons deux attaques basées sur l’utilisation des fractions continues. La première est due à Wiener (1990).

38CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES

2.2.1

L’attaque de WienerThé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 la1clé secrète d est assez petite : d < 13 N 4 . Connaissant N et e, on peut calculer d etfactoriser 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. Puisquee < φ(N ), on peut donc écrirek=eded − 1
<
< d.
φ(N )
φ(N )

Alors
e
k
−
N
d

=
=
=
<
<
=

|ed − kN |Nd|ed − kϕ(N ) − kN + kϕ(N )|Nd|1 − k(N − ϕ(N ))|Ndk(N − ϕ(N ))
√ Nd
3k N
Nd
3k
√ .
d N

1

Puisque k < d < 13 N 4 , alors
1

3k
N4
1
1
√ < √ =
.
1 <
2d2
d N
d N
dN 4
Ainsi, en appliquant le théorème 2.1.5, kd est une convergente de Ne . Connaissant d
et k, on peut alors calculer φ(N ) par la relationed − 1.
k
Ainsi, par la proposition 1.3.1 on peut calculer p et q et donc trouver la factorisatiode N .
φ(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
1vé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 :√ (N +1−ψ+ δ)
ey−1
2.
3: Calculer ψ = x , δ = (N + 1 − ψ) − 4N , et p2 =2
4: Si pgcd(p2 , N ) > 1 alors5:
Afficher d = y, p = p2 et q = pN2 .
6: Fin Si

Maple 2.2.2.
Programme

Commentairen:=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 py:=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 phd:=rand(sn)() end do:<-- La clé publique
e:=1/d mod ph: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́quationp2:=round(p2):<-- calcul de pgcd(p2,N)
g:=gcd(p2,N):

40CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES
i:=i+1:od:<-- Affichage de dprint(‘d=‘):y;<-- Affichage de p
print(‘p=‘):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

Commentairen:=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 premiera:=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;<-- Inverse de de:=Modinv(d,ph);<-- Liste des quotients partiels
c:=ContinuedFraction(e/N);<-- Initialisation
s:=[];
t:=[];<-- Initialisation<-- Longuer de c
l:=#c;<-- Fabrication des listes
for i in [1..l] do
s:=Append(s,c[i]);<-- quotients partiels
t:=Append(t,Convergents(s)); <-- convergentes
end for;<-- Initialisation
i:=3;
g:=1;
<-- Initialisation
while (g eq 1) do<-- Boucle de Wiener<-- Valeur de k
kk:=t[i][1,2];<-- Valeur de d
dd:=t[i][2,2];
phn:=(e*dd-1)/kk;<-- Valeur phn=(e*dd-1)/kk

2.2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUES
delta:=(N+1-phn)^2-4*N;<-- delta=(N+1-phn)^2-4*N
x:=((N+1-phn)+Sqrt(delta))/2; <-- Candididat pour pp2:=Round(x);<-- Candididat pour pg:=GCD(p2,N);<-- PGCD
i:=i+1;end while;<-- Fin whilep2;<-- Affichage de p2p2-p;<-- Différence nulle4142CHAPITRE 2. CRYPTANALYSE DE RSA PAR LES FRACTIONS CONTINUESChapitre 3
Cryptanalyse de RSA parl’algorithme LLL
Les objectifs ne sont pas atteints par les souhaits, mais par letravail assidu.

Abu Alaa Al Maary YgñK á» B ð
AK. C« AJK YË@

3.1

L’algorithme LLL

3.1.1

Introduction aux réseauxúæÒJËAK. I.Ë A¢ÜÏ @ ÉJK AÓðø QªÜÏ @ Z CªË@ ñK. @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 videde Rn . On dit que L est un réseau s’il existe une famille libre (b1 · · · , bd ) de Rn telle
que
( d
)
d
X
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 nedé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 matricecarrée U , de type n × n à éléments dans Z telle quedet(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 dechercher 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
Thx, yi = x y =nX

xi y i .

i=1

2. La norme de x est
12

kxk = (hx, xi) =

n
X

! 12
x i yi.

i=1

Une des méthodes les plus utilisées pour produire une base orthogonale à partird’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 net (b1 · · · , bn ) une base de V . On considère la famille de vecteurs (b∗1 · · · , b∗n ) définieparb∗1 = b1 ,b∗i = bi −i−1
Xµi,j b∗j ,j=1

avec pour j < iµi,j =

hbi , b∗j i.
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 deV . En écrivant
b1 = b∗1 ,bi = b∗i +i−1
Xµi,j b∗j ,j=1

on en conclut que, sous forme matricielle, on a






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




0  ∗ b∗1b1
 b∗ 
0 
 2 
  b∗  b∗ 
 2 
0 
 3 
  b∗ ..   3  = U  ..  .
 . 
 . 
. 
 ∗ 
  ..  bn−1 

0
∗
bn
b∗n
1

La matrice U est est une matrice inférieure, dont la diagonale est formée de 1. Sondé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, puisqueb∗1 = b1 et b∗2 = b2 − µ2,1 b1 , alorshb∗1 , b∗2 i = hb1 , b2 − µ2,1 b1 i = hb1 , b2 i − µ2,1 hb1 , b1 i = hb1 , b2 i −

hb2 , b1 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*hb∗k , b∗i i

b∗k , bi −

=

i−1
X

+
µi,j b∗j

j=1

=
=
=

hb∗k , bi i −i−1Xµi,j b∗k , b∗jj=1∗
hbk , bi i − µi,k hb∗k , b∗k i
hbi , b∗ ihb∗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, faire3:
Pour j = 1, 2, · · · i − 1, fairehbi ,b∗ i
4:Calculer µi,j = hb∗ ,bj∗ i .
j j
5:
Fin PourP∗
6:
Calculer b∗i = bi − i−1
j=1 µi,j bj .
7: Fin PourOn 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
Programme

47
Commentaires

gramschmidt:=proc (M)<-- Procédure
local i, j, n, B, P, u,k:<-- Paramètres locaux
with(LinearAlgebra):<-- Librairie LinearAlgebran := nops(M):<-- Nombre de lignes de M
B := []: P := []:<-- Initiation des listes
for i from 1 to n do<-- i=1,...,nu := [seq(0, k = 1 .. n)]:<-- Initiation de u
for j from 1 to i-1 dofor j from 1 to i-1 dou[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:<-- Sortie
return(B, P):
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−1Programme

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 :


 6

2 − 75 10
1 5 − 2523
 , P = 0 1 − 6  ,− 20
A = 1 14
5
23
23
35
0 −2 − 23
0 0 1



2 1
0
Q = 1 4 −2 .
0 −2 −1

Maple 3.1.7.
En fait, dans Maple, la méthode de Gram-Schmidt est programmée sous le nom defonction 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
b1 = 1 ,
0



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

Commentaireswith(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−523
 , b∗3 = − 20  .
b∗1 = b1 = 1 , b∗2 =  14
5
23
35
0
−2
− 23
Magma 3.1.8.
Dans Magma, la méthode d’orthogonalisation de Gram-Schmidtst est programméesous le Orthogonalize(M) où M est une matrice carrée. Elle retourne trois valeursN , P et n où N est une matrice dont les colonnes représentent des vecteurs orthogonaux, 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b1 = 1 ,0Programme
Q:= RealField();
R:=MatrixRing(Q,3);1b2 =  4  ,
−2




0
b3 = −2 .
−1

Programme<--- Ensemble des réels<--- Ensemble des matrices
définie sur Q de type 3x3.
<--- F est la matrice

F:=elt<R|[2, 1, 0,
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−523
 , b∗3 = − 20  .
b∗1 = b1 = 1 , b∗2 =  14
5
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
det(L) =nY

kb∗i k ≤i=1

nY

kbi k.

i=1

Démonstration. On a b1 = b∗1 , donc kb1 k = kb∗1 k. Pour 2 ≤ i ≤ n, on abi = b∗i +i−1
Xµi,j b∗j ,j=1

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

kbi k

= kb∗i k2 +i−1X

µ2i,j kb∗j k2 ,j=1

et donc2

det(L) =nYi=1

kb∗i k2 ≤nY

kbi k2 ,i=1

ce qui termine la preuve.
Un problème très important en théorie des nombres et en cryptanalyse est la recherche 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 unvecteur v non nul de L tel que

kvk ≤

√

1

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

(3.1)
(3.2)

|µi,j | ≤

1
,
2

pour

1 ≤ j < i ≤ n,3 ∗ 2
kb k ≤ kb∗i + µi,i−1 b∗i−1 k2 ,
4 i−1

pour

1 < i ≤ n.

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

Algorithme 9 : Algorithme LLL
Entrée : Une base (b1 , · · · , bn )Sortie : Une base LLL réduite (b1 , · · · , bn )1: Pour i = 1, · · · , n faire2:b∗i = bi3:
Pour j = 1, · · · , i − 1 fairehbi ,b∗ i
4:µi,j = Bjj
5:b∗i = b∗i − µi,j b∗j6:
Fin Pour7:
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: Sinon21:
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 alors2:
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,j6:
Fin Pour
7: Fin Si
Remarque : bxe est l’arrondi de x, c’est à dire l’entier le plus proche de x.

51

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−1
B
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 faire10:µ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,k12: 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,...,jU[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 80Parmi les nombreuses propriétés d’une base LLL-réduite, on a les inégalités suivantes.
Théorème 3.1.13. Soit (b1 · · · , bn ) une base LLL-réduite et (b∗1 , · · · , b∗n ) la baseorthogonale associée par la méthode de Gram-Schmidt. Alors
1. kb∗j k2 ≤ 2i−j kb∗i k2 pour 1 ≤ j ≤ i ≤ n.
Qn(n−1)
2. ni=1 kbi k ≤ 2 4 det(L).
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́veloppantl’inégalité 3.2 et en utilisant 3.1, on a3 ∗ 21
kbi−1 k ≤ kb∗i k2 + µ2i,i−1 kb∗i−1 k2 ≤ kb∗i k2 + kb∗i−1 k2 ,44ce qui donnekb∗i−1 k2 ≤ 2kb∗i k2 .
Ainsi, pour j ≤ i, on obtientkb∗j k2 ≤ 2i−j kb∗i k2
ce qui démontre la propriété 1.
Preuvede 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 :
kbi k

2

= kb∗i k2 +

i−1
X
j=1

1
µ2i,j kb∗j k2 ≤ kb∗i k2 +

i−1
X

4 j=1

kb∗j k2 .

3.1. L’ALGORITHME LLL

55

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

kbi k

1
≤ kb∗i k2 +

i−1
X

4 j=1


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

En passant aux produits, on a alorsnY2

kbi k ≤

i=1

n
Y

i−1

2

kb∗i k2 = 2n(n−1)
2i=1

nYkb∗i k2 = 2n(n−1)
2det(L),

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. AlorsYn(n−1) Yn(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 obtientv=nX

αi bi =i=1nXαi∗ b∗i ,αi ∈ Z αi ∈ R.

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 produit 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
kvk2 =nXi=1(αi∗ )2 kb∗i k2 ≥ (αk∗ )2 kb∗k k2 ≥ kb∗k k2 .

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 leré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 an(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 deGram-Schmidt à (b1 , · · · , bn ). Par le résultat (3) de la proposition 3.1.13, on a, pour1≤j≤i≤ni−1
kbj k ≤ 2 2 kb∗i k.
En appliquant cette inégalité pour chaque i = j, j + 1, · · · , n et en multipliant, on
obtientnYi−1
kbj kn−j+1 ≤2 2 kb∗i k.
i=j

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

n−j+1

≤

n
Y

2

i−1
2

kb∗i k =

i=1

n
Y
i=1

2

i−1
2

n
Y

kb∗i k = 2

n(n−1)
4det(L),

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

Commentaireswith(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
↓

−1
N =
2

−1
5


b2 b3 b4↓ ↓↓

2 −1 −1.
1 −2 −1
0 1 −3
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] >;<--- Procédure LLL,
F:=LLL(M) ;<--- Déterminant de M
Determinant(M);<--- Déterminant de F
Determinant(F);On obtient alors la base (b01 , b02 , b03 , b04 ) dont la matrice est

 0
b1
↓

−1
N =
2

−1
5


b02 b03 b04↓ ↓↓
2 −1 −1.
1 −2 −1
0 1 −3
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́SEAUXProgramme

59

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 desréseaux

3.2.1

La méthode de Coppersmith : polynômes à une variable

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’unpolynôme à deux variables. Soit N un entier positif (sans factorisation connue) et f
un polynôme de degré d à coefficient dans Z.
f (x) =nX

ai x i .

i=1

Chaque terme xi est appelé un monôme. La norme Euclidienne de f est définie parv
u nuX||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|x0 | < X,
où X est une borne fixée.

(mod N ),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 depolynô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−kNk m−kjgjk (x0 ) = x0 (fb (x)) bb m−kN= ak xj0 bk bm−kb m−kN= ak xj0 bmb≡ 0 (mod bm ).
Ceci implique que toute combinaison linéaire h(x) des polynômes gjk (x) vérifierah(x0 ) ≡ 0 (mod bm ). Si en plus h vérifie |h(x0 )| < bm , alors on a tout simplementh(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́ dayant 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 ),(3) kh(xX)k < √Mω ,3.2. CRYPTANALYSE DE RSA PAR LA RÉDUCTION DES RÉSEAUX

61

alors h(x0 ) = 0 en tant qu’équation sur Z.
Démonstration. Soit h(x) =
Alors

Pd

i

|h(x0 )| =X

ai xi ≤

i ai xayant ω monômes. Supposons que |x0 | < X.
Xiai x i <iX

ai X i .

iD’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
!
!
X
X
X
X

2
2
ai X i≤12
ai X i=ω
ai X i .
i

i

i

i

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

ωsX(ai X i )2 =√

ωkh(xX)k < M.

ii

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́seaude dimension n dont une base est formée à l’aide des coefficients des polynômesgjk (xX). Avec l’algorithme LLL, on peut obtenir un vecteur h(xX) qui vérifie lacondition (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̂mev1 (xX) va vérifiern−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
(3.3)

2

n−1
4

bm
√
det(L) <.
n
1n

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,hi (x) = xi (fb (x))m ,i = 0, · · · , t − 1,

i = m, · · · , 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
↓
↓
↓
m
m
m 2
i=m→
N ,
N x,
N x,
m−1
m−1
i=m−1→ N
f N
xf N m−1 x2 f(3.4) i = m − 2 → N m−2 f 2 N m−2 xf 2 N m−2 x2 f 2
..
..
..
..
.→
.
.
.
2 m−2
2
m−2
2 2 m−2
i=2→
N f
N xf
N xf
i=1→
N f m−1 N xf m−1 N x2 f m−1

···
↓
···
···
···
..
.

j =δ−1
↓
m δ−1
N x ,
N m−1 xδ−1 f
N m−2 xδ−1 f 2
..
.

···
···

N 2 xδ−1 f m−2
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 lespolynô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 totalement 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 = ,.
.

 − − ··· −.
−−(m−1)δ+δ−1− − ··· −
−
−
− NX


− − · · · − 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 :11det(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

2 4 N

m(m+1)δ
2n1bm
X 2 (n−1) < √ .
nPuisque b > N β , il suffit alors d’avoir
n−1

2 4 N

m(m+1)δ
2n

1
N mβ
X 2 (n−1) < √ .
n64

CHAPITRE 3. CRYPTANALYSE DE RSA PAR L’ALGORITHME LLL

En isolant X, on obtient alors
1−1

X < 2− 2 n n−1 N

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

En considérant l’exposant de N dans l’inégalité précédente, on observe qu’il atteint
son maximum pour2nβ − δm0 =,2δce qui donne la borne
1

−1

β2

β2

δ

β

X < 2− 2 n n−1 N δ + (n−1)δ + 4n(n−1) − n−1 ,ce qui peut être écrit sous la forme
β2

1

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 β . Soitfb (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̀mesuivant :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 congruencef (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

i=3
i=2
i=1
i=0

j=0
N 3,
N 2 f (xX)
N f 2 (xX)
f 3 (xX)

1
N 3 xX,N 2 xf (xX)
N (xX)f 2 (xX)

2
N m (xX)2N 2 (xX)2 f (xX)
N (xX)2 f 2 (xX)

On posef (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,


1
x
x2
x3
x4
x5
x6
x7
x8
x9
 ↓
↓
↓
↓
↓
↓
↓
↓
↓
↓ 


 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


2
2
2
2
3
2
 a0 N a1 XN a2 X N

X
N
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
a
X
N
a
X
N
a
X
N
X
N
0
0
0
0
0
1
2


2
3
4
5
6
 b0 N b1 XN b2 X N b3 X N b4 X N b5 X N X N
0
0
0 


2
3
4
5
6
7
 0

b
XN
b
X
N
b
X
N
b
X
N
b
X
N
b
X
N
X
N
0
0
0
1
2
3
4
5


2
3
4
5
6
7
8
 0
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 9Maple 3.2.5.
On ne trouve en fait aucune solution car la valeur prise par X est très grande. En11effet, 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

Commentaireswith(PolynomialTools):<-- Package Polyn^
omeswith(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;<-- Le degré de fd:=degree(f(x),x):<-- Borne supérieure des solutions
X:=trunc((2^(-1/2)*N^(1/d))):<-- Une borne inférieure
X:=500;<-- m=3 et t=1
m:=3:t:=1:<-- La dimension du réseau
n:=d*m+t:<-- La matrice (n,n), formée de 0
M:=Matrix(n):<-- Initiation
line:=0:<-- Boucle de formation defor i from 1 to m dola matrice correspondante
i2:=m+1-i:
aux polyn^
omes g(i,j),
for j from 0 to d-1 doqui formera
line:=line+1:
l’entrée pour LLL
cc:=CoefficientVector(N^i2*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:<-- Fin de la boucle
end do:<-- Boucle de formation defor i from 0 to t-1 dola matrice correspondanteline:=line+1:
aux polyn^
omes h(i),cc:=CoefficientVector
qui formera(x^i*X^i*(f(x*X))^m,x):
l’entrée pour LLL
for k from 1 to Dimension(cc) do
M[line,k]:=cc[k]:end do:<-- Fin de la boucle
end do:<-- Formation de la matrice
VM:=[row(M,1..n)]:
L := LLL(VM, ’integer’):<-- Réduction de la matrice<-h:=0:<-- Formation du polyn^
ome hfor i from 0 to n-1 do
h:=h+(L[1,i+1]/X^i)*x^i:
end do:h:<-- racines entière de hisolve(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;<-- Choix m=3 et t=1
m:=3;t:=1;<-- Ordre du réseau
n:=d*m+t;<-- Matrice carrée nxn
M:=RMatrixSpace(IntegerRing(),n,n)!0;<-- line=0
line:=0;<-- Boucle de formation defor i:=1 to m dola matrice correspondante
i2:=m+1-i;
aux polyn^
omes g(i,j),
for j:=0 to d-1 doqui formera
line:=line+1;
l’entrée pour LLL
cc:=Coefficients(N^i2*X^j*x^(j)*f^(m-i2));for k:=1 to #(cc) do
M[line,k]:=cc[k];end for;end for;end for;<-- Boucle de formation defor i:=0 to t-1 dola matrice correspondanteline:=line+1;
aux polyn^
omes h(i),cc:=Coefficients(x^i*X^i*f^m);qui formera
for k:=1 to #(cc) do
M[line,k]:=cc[k];l’entrée pour LLL
end for;end for;<-- Algorithme LLL
L := LLL(M);<-- p=0p:=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 hpp:=pp+L[1,i+1]*z^i;
p:=p+(L[1,i+1]/X^i)*z^i;
end for;<-- polyn^
ome h et ses racines
p;Roots(p);On ne trouve en fait aucune solution si la valeur prise par X est très grande. En
effet, dans l’inégalité
11|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 6999721772296884 ∗ z 5 + 35322490662759665925 ∗ z 413772627569229621478757 ∗ 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 polynomiale
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, onveut résoudre l’équationf (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 Coppersmithsol;<-- Ensemble des solutions
La solution obtenue 79.

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

3.2.2

69

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 que1|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
fp (x0 ) ≡ 0

1|x0 | < N 4 .

mod p,

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 laforme 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 duthé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 nedonne 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

Commentaireswith(PolynomialTools):<-- Package Polyn^
omeswith(LinearAlgebra):<-- Package Algèbre Linéaire
with(linalg):<-- Un autre package
with(IntegerRelations):<-- Package LLL
p := nextprime(2^50):<-- Le nombre premier pq := 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 fd:=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=2n:=d*m+t:<-- La dimension du réseau
M:=Matrix(n):<-- La matrice (n,n), formée de 0line:=0:<-- Initiation
for i from 1 to m do<-- Boucle de formation dei2:=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^i2*X^j*x^(j)*(f(X*x))^(m-i2),x):
for k from 1 to Dimension(cc) do
M[line,k]:=cc[k]:<-- Fin de la boucle
end do:end do:end do:<-- Boucle de formation defor i from 0 to t-1 dola matrice correspondanteline:=line+1:
aux polyn^
omes h(i),cc:=CoefficientVector(x^i*X^i*(f(x*X))^m,x):
qui formera
l’entrée pour LLL
for k from 1 to Dimension(cc) do
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 hfor i from 0 to n-1 do
h:=h+(L[1,i+1]/X^i)*x^i:
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 ε = 0s’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 nedonne 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 doi2:=m+1-i;
for j:=0 to d-1 doline:=line+1;
cc:=Coefficients(N^i2*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 doline:=line+1;cc:=Coefficients(x^i*X^i*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^i; h:=h+(L[1,i+1]/X^i)*z^i;end for;h;Roots(h);On obient le polynômeh(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 ScienceVol. 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 rational coefficients, Mathematische Annalen, Vol. 261, pp. 513—534, 1982.
[5] A. May. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis, 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 signaturesand 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).

73