www.hakin9.org hakin9 Nº 3/2007 56
Fiche technique
N
ous allons étudier dans le présent ar-
ticle les travaux internes de RSA et la
possibilité de lancer des attaques dites
par factorisation. Nous verrons comment les
clés de l'algorithme RSA ainsi que la procédure
de l'attaque permettent d'obtenir la clé privée
correspondant à la clé publique attaquée.
Afin de bien comprendre et réutiliser le
présent article, le lecteur doit maîtriser les prin-
cipes fondamentaux liés à la programmation
en C et savoir manier certains concepts ma-
thématiques. Vous trouverez dans le tableau
des références des sources de documentation
complémentaires pour de plus amples rensei-
gnements sur le sujet.
Tous les exemples ont été développés et
testés sur un système GNU/Linux.
Cryptographie à clé publique
Contrairement à la cryptographie à clé privée, où
une seule clé est utilisée pour crypter et décryp-
ter les messages, la cryptographie à clé publique
repose sur deux clés, concept également appelé
biclé. Ces deux clés sont respectivement dé-
nommées clé publique et clé privée. Afin de cryp-
ter la communication choisie, l'utilisateur aura
besoin des deux clés. Alors que la clé privée
doit demeurer confidentielle, la clé publique peut
être mise à la disposition de quiconque désirant
envoyer des messages cryptés à l'utilisateur.
Un message crypté à l'aide d'une clé publique
ne peut être décrypté qu'à l'aide de la clé privée
correspondante. Or, pour ce faire, il faut aborder
certains problèmes d'ordre mathématique. Notre
choix s'est porté sur le système RSA en raison
de la décomposition en produit de facteurs pre-
miers, ou factorisation, de gros chiffres.
Les débuts de la cryptographie à clé publique
remonte à la publication de Diffie et Hellman en
1976. Dans cette publication, les deux chercheurs
ont introduit un protocole capable d'autoriser
l'échange de certaines informations sur un canal
Attaque par factorisation
contre RSA
Daniel Lerch Hostalot
Degré de difficulté
RSA représente sans conteste le système cryptographique à clé
publique le plus utilisé de nos jours qui est parvenu à survivre
aux critiques des spécialistes en cryptographie pendant plus d'un
quart de siècle. La fiabilité de cet algorithme repose notamment
sur la difficulté de décomposer en produit de facteurs premiers
de gros chiffres, de l'ordre des nombres décimaux à 100 chiffres.
Cet article explique…
• Fonctionnement de RSA,
• Techniques permettant de lancer des attaques
par factorisation.
Ce qu'il faut savoir…
• Principes fondamentaux de la programmation
en C.
Attaque par factorisation contre RSA
hakin9 Nº 3/2007 www.hakin9.org 57
non sécurisé. Peu de temps après, en
1977, les chercheurs Rivest, Shamir et
Adleman ont proposé leur propre sys-
tème de cryptographie baptisé RSA,
aujourd'hui le plus largement utilisé au
monde.
Toujours en 1977, des documents
ont démontré que les cryptographes
du British Government Group pour la
Sécurité des Communications Elec-
troniques (GSEC) connaissaient déjà
ce type de cryptographie en 1973.
Système
cryptographique RSA
Comme nous venons de le dire précé-
demment, la sécurité du système RSA
repose sur la difficulté mathématique
de décomposer en produit de fac-
teurs premiers, ou factoriser, de gros
chiffres. Factoriser un nombre con-
siste à trouver les nombres premiers
(facteurs) dont le produit donne pour
résultat le nombre en question. Si, par
exemple, vous souhaitez factoriser le
nombre 12, vous allez obtenir un résul-
tat de 2·2·3. La méthode la plus simple
pour trouver les facteurs premiers d'un
nombre n consiste à diviser ce dernier
par l'ensemble des nombres premiers
inférieurs à n. Quoique extrêmement
simple, cette procédure peut se révéler
très fastidieuse lorsque vous souhaitez
factoriser de gros chiffres.
Procédons à quelques calculs pour
vous donner une idée. Une clé de 256
bits (à l'instar de celle que nous allons
attaquer ultérieurement) comprend
près de 78 chiffres décimaux (1078).
Dans la mesure où sur les clés du sys-
tème RSA, ce nombre ne possède en
règle générale que deux facteurs pre-
miers, chacun de ces facteurs auront
plus ou moins 39 chiffres. Autrement
dit, pour factoriser le nombre en ques-
tion, il faudra le diviser par l'ensemble
des nombres premiers à 39 chiffres
ou moins (1039). En supposant que
seul 0,1% des nombres soient des
nombres premiers, il faudra procéder
à près de 1036 divisions. Imaginons
maintenant que vous disposiez d'un
système capable de réaliser 1020
divisions par seconde. Dans ce cas,
vous passerez quelques 1016 secon-
des à attaquer la clé, autant dire plus
de 300 millions d'années, soit un mil-
lion l'âge de l'univers. Heureusement,
nous serons bien plus rapide grâce
à l'exemple décrit ci-après.
Analysons désormais le fonction-
nement du système RSA. Il faut com-
mencer par générer les clés publiques
et privées (vous trouverez dans le
tableau ci-joint quelques illustrations
de concepts mathématiques particu-
lièrement intéressants). Pour ce faire,
il est nécessaire de bien respecter les
étapes comme suit.
Étape 1
Il faut tout d'abord choisir deux
nombres premiers p et q de manière
aléatoire, puis les multiplier pour ob-
tenir n :  n
p q = ⋅ . Si vous choisissez
par exemple,  p = 3 et  q =11 vous
obtiendrez  n = 33 .
Étape 2
Il faut ensuite calculer l'indicateur
(ou  fonction  indicatrice)  d'Euler
à l'aide de la formule suivante :
Φ Φ n p q p q ( ) = ⋅ ( ) = − ( ) ⋅ − ( ) 1 1 .  Dans
cet exemple, vous devez obtenir
Φ n ( ) = 20 .
Étape 3
Vous trouvez un exposant de cryp-
tage (que vous allez utiliser par la
suite pour le cryptage) que vous
allez appeler e. Ce nombre doit être
compatible avec  mcd e n ,Φ ( )
( ) =1 Un
excellent exemple serait :  e = 3 dans
Concepts mathématiques
Diviseur ou facteur
Un nombre entier  a désigne un diviseur (ou facteur) de  b lorsqu'il existe d'autres nom-
bres entiers  c compatibles avec  b a c = ⋅ . Exemple : 21 7 3 = ⋅
Nombres premiers et nombres composés
Un nombre entier est dit premier si ce dernier ne peut être divisé que par un et lui-
même. Un nombre entier est dit composé lorsqu'il ne rentre pas dans la catégorie des
nombres premiers.
Exemple :  21 7 3 = ⋅ est un nombre composé, alors que 7 et 3 sont des nombres
premiers.
Factorisation
La factorisation d'un nombre entier  n consiste à décomposer ce dernier en produit
de ses facteurs premiers :  n
p p p
e e
i
e i
= ⋅ ⋅⋅⋅
1 2
1 2
où  p i représentent des nombres premiers
et  e i représentent des nombres entiers positifs. Exemple : 84 peut être factorisé en
21 2 3 7
2
= ⋅ ⋅
.
Module
Un module désigne et représente  a b mod le reste de la division entière de a
entre  b .
Exemple : 5 3 2 mod = ,  10 7 3 mod = ,  983 3 2 mod = ,  1400 2 0 mod = .a et b sont des
modules de n :  b a n ≡ ( ) mod si leur différence (a-b) est un multiple den.
Diviseur commun maximum
Est désigné par diviseur commun maximum de deux nombres entiers  a et  b , re-
présentée sous forme de  mcd a b , ( ) , le nombre entier le plus élevé pouvant diviser
a et  b .
Exemple :  mcd mcd 42 35 2 3 7 5 7 7 , , ( ) = ⋅ ⋅ ⋅ ( ) = Algorithme euclidien
L'algorithme euclidien permet de calculer le diviseur commun maximum de deux
nombres selon mcd a b mcd b r , , ( ) = ( ) , où  a b > > 0 représentent des nombres entiers,
et  r le reste de la division entre  a et  b Exemple :  mcd 1470 42 , ( )
(1)  1470 42 35 1470 42 42 35 mod , , = → ( ) = ( ) mcd mcd
(2) 42 35 7 42 35 35 7 mod , , = → ( ) = ( ) mcd mcd
(3) 35 7 0 7 0 7 mod , = → ( ) = mcd Indicateur (ou fonction indicatrice) d'Euler
Soit  n ≥ 0 représentant  Φ n ( ) le nombre d'entiers compris dans l'intervalle  1,n
[ ]
étant premiers* avec  n . Pour  n
p q = ⋅ ,  Φ n
p q ( ) = − ( ) − ( ) 1 1 .
*Deux entiers  a et  b représentent les nombres premiers entre eux (ou co-pre-
mier) si  mcd a b , ( ) =1 .
hakin9 Nº 3/2007 www.hakin9.org
Fiche technique
58
la mesure où il ne possède aucun
facteur commun avec 20 (facteurs
2 et 5).
Étape 4
Il faut ensuite calculer un exposant
de décryptage que vous allez ap-
peler d (il vous servira plus tard
au décryptage). Ce nombre doit
correspondre à  1< < ( ) d n Φ de sorte
que  e d n ⋅ ≡ ( )
( ) 1 modΦ
. Autrement dit,
d sera un nombre compris entre 1 et
20 qui, multiplié par 3 et divisé par 20
donnera 1. L'exposant de décryptage
d peut alors être le nombre 7.
Clés
La clé publique de l'utilisateur appar-
tient au couple (n,e), soit dans notre
exemple (33, 3), alors que la clé
privée correspond à d, soit 7. Logi-
quement, les nombres p, q et d  Φ n ( )
doivent demeurer confidentiels.
(Dé)cryptage
Arrivé à ce stade, il suffit de pro-
céder au cryptage à l'aide de
C M n
e
= mod
puis au décryptage
grâce à  M
C n
d
= mod
. Si nous sup-
posons que le message est  M = 5 ,
le chiffrage correspondant sera alors
C = = 5 33 26
3 mod
. Afin de décrypter
le message, il suffira d'appliquer
M = = 26 33 5
7
mod
.
Comme nous l'avons mentionné
en début d'article, et comme le
démontre la procédure ci-dessus,
la sécurité des systèmes cryptogra-
phiques repose sur le nombre n. En
d'autres termes, si un pirate capable
d'accéder à la clé publique parvient
à factoriser n en obtenant p et q, il lui
suffit alors d'appliquer les formules
précédentes pour obtenir la clé pri-
vée tant convoitée.
Compétition de
factorisation RSA
La Compétition de Factorisation
RSA est un concours financé par les
Laboratoires RSA au cours duquel
d'importants prix sont décernés aux
informaticiens capables de factoriser
certains nombres particulièrement
importants. Pour parvenir à connaî-
tre le statut des systèmes de facto-
risation, il faut savoir quelle longueur
de clé va être nécessaire pour garan-
tir la sécurité du système RSA.
À l'heure où nous rédigeons le
présent article, le record de factori-
sation est RSA-640, nombre à 193
chiffres décomposé en produits de
facteurs premiers le 2 novembre
2005 par F. Bahr et al. La prochaine
compétition portera sur RSA-704,
avec un prix de 30 000 dollars.
La Compétition de Factorisation
RSA demeure sans aucun doute le
moyen le plus pratique de se faire
une idée sur l'état actuel des systè-
mes de factorisation.
Vous trouverez dans le tableau
exposé à la fin du présent article les
compétitions actuellement organi-
sées en la matière.
Attaque par
factorisation
Nous allons présenter ci-après un
exemple d'attaque par factorisation
dirigée contre une clé du système
RSA. Afin de rendre les calculs plus
rapides, nous utiliserons une clé
bien plus courte que les clés norma-
lement utilisées, afin d'en simplifier la
décomposition en facteurs premiers.
Même si cet exemple ne se conforme
pas à la réalité, il permettra toutefois
d'analyser les éléments constituant
une attaque complète.
Il faut commencer par créer un
environnement de travail au moyen
de l'outil OpenSSL, chargé de géné-
rer les clés nécessaires et de crypter
le message que vous allez ensuite
utiliser sous forme de cible pour
votre attaque. Il faudra ensuite facto-
riser le module n pour obtenir la clé
privée, et enfin décrypter le message
en question.
OpenSSL et RSA
OpenSSL est un outil cryptographi-
que open source particulièrement
pratique. Dans la partie consacrée
aux  références,  vous  trouverez
toutes les informations nécessaires
pour le télécharger, mais sachez que
la plupart des distributions GNU/
Linux le proposent par défaut. Nous
allons donc l'utiliser ici pour configu-
rer un environnement de test dans
lequel l'attaque sera lancée.
La  première  étape  consiste
à générer un couple de clés pour
le cryptage et le décryptage. Nous
allons générer des clés de 256 bits,
certes trop courtes pour maintenir un
niveau de sécurité sur nos communi-
cations, mais largement suffisantes
pour illustrer nos propos.
Nous générons donc une paire
de clés, en maintenant notre clé pri-
vée confidentielle.
# Génération d'une paire de clés à 256
bits du système RSA
openssl genrsa -out rsa_privkey
.pem 256
cat rsa_privkey.pem
-----DEBUT DE LA CLE PRIVEE-----
MIGqAgEAAiEA26dbqzGRt31qincXxy
4jjZMMOId/DVT8aTcq8aam
DiMCAwEAAQIh
AmvT1oXa/rxF3mrVLrR/RS7vK1WT
sQ5CWl/+37wztZOpAhEA+4jg
EkfalFH+0S+1
IPKD5wIRAN+NmMH4AF0B8jz
MAXHHXGUCEGRpRZnGmV
kwSlrTgqj+Zu0CEA7v7CQR
yRxt09zCGNqcYo0CEDEW7mvoz
MYYLC5o+zgfV4U=
-----FIN DE LA CLE PRIVEE RSA-----
Après cette étape, nous sauvegar-
dons la clé publique dans un fichier.
Il s'agit de la clé que nous allons
publier afin de permettre à quicon-
que de nous envoyer des messages
cryptés.
Listing 1. Transformation d'un
chiffre hexadécimal en chiffre
décimal
#include <stdio.h>
#include <openssl/bn.h>
int main (int argc, char **argv) {
BIGNUM *n = BN_new();
if (argc!=2) {
printf ("%s <hex>\n",
argv[0]);
return 0;
}
if(!BN_hex2bn(&n, argv[1])) {
printf("error:
BN_hex2bn()");
return 0;
}
printf("%s\n", BN_bn2dec(n));
BN_free(n);
}
Attaque par factorisation contre RSA
hakin9 Nº 3/2007 www.hakin9.org 59
# Sauvegarde de la clé publique sur un
fichier
openssl rsa -in rsa_privkey.pem
-pubout -out rsa_pubkey.pem
cat rsa_pubkey.pem
-----DEBUT DE LA CLE PUBLIQUE-----
MdwwDQYJKoZIhvcNAQEBB
QADKwAwKAIhANunW6sxkbd
9aop3F8cuI42TDDiHfw1U
/Gk3KvGmpg4jAgMBAAE=
-----FIN DE LA CLE PUBLIQUE-----
Après avoir générex cette paire de
clés, il est désormais possible de
crypter et de décrypter les messa-
ges. Nous allons travailler sur le
message suivant :
echo "Forty-two" > plain.txt
Ce message peut être facilement
crypté au moyen de la commande
suivante et de la clé publique :
openssl rsautl -encrypt
-pubin -inkey rsa_pubkey.pem \
-in plain.txt -out cipher.txt
Afin de décrypter le message, nous
utiliserons la clé privée :
openssl rsautl -decrypt -inkey
rsa_privkey.pem -in cipher.txt
Une fois le fonctionnement de l'outil
OpenSSL avec le système RSA
maîtrisé, et en étant conscient de la
nécessité de disposer de la clé privée
pour pouvoir décrypter les messa-
ges, notre objectif consiste à obtenir
cette clé privée sans avoir accès
à l'originale. En d'autres termes, il faut
tenter d'obtenir la clé privée en utili-
sant la clé publique. Il faut donc com-
mencer par obtenir le module n ainsi
que l'exposant de cryptage. Pour ce
faire, il suffit d'utiliser la commande
suivante avec la clé publique :
openssl rsa -in rsa_pubkey.pem
-pubin -text -modulus
Modulus (256 bit):
00:db:a7:5b:ab:31:91:b7:7d:
6a:8a:77:17:c7:2e:
23:8d:93:0c:38:87:7f:0d:54:
fc:69:37:2a:f1:a6:
a6:0e:23
Exponent: 65537 (0x10001)
Modulus=DBA75BAB3191B77D
6A8A7717C72E238D930C38877
F0D54FC69372AF1A6A60E23
writing RSA key
-----DEBUT DE LA CLE PUBLIQUE-----
MdwwDQYJKoZIhvcNAQEBBQ
ADKwAwKAIhANunW6sxkbd9
Listing 2. Clé privée
#include <stdio.h>
#include <openssl/bn.h>
#include <openssl/rsa.h>
#include <openssl/engine.h>
#include <openssl/pem.h>
int main (int argc, char **argv) {
RSA *keypair = RSA_new();
BN_CTX *ctx = BN_CTX_new();
BN_CTX_start(ctx);
BIGNUM *n = BN_new();
BIGNUM *d = BN_new();
BIGNUM *e = BN_new();
BIGNUM *p = BN_new();
BIGNUM *q = BN_new();
BIGNUM *dmp1 = BN_new();
BIGNUM *dmq1 = BN_new();
BIGNUM *iqmp = BN_new();
BIGNUM *r0 = BN_CTX_get(ctx);
BIGNUM *r1 = BN_CTX_get(ctx);
BIGNUM *r2 = BN_CTX_get(ctx);
BIGNUM *r3 = BN_CTX_get(ctx);
if (argc!=4) {
printf ("%s [p] [q] [exp]\n", argv[0]);
return 0;
}
BN_dec2bn(&p, argv[1]);
BN_dec2bn(&q, argv[2]);
BN_dec2bn(&e, argv[3]);
if(BN_cmp(p, q)<0) {
BIGNUM *tmp = p;
p = q;
q = tmp;
}
// Nous calculons n
BN_mul(n, p, q, ctx);
// Nous calculons d
BN_sub(r1, p, BN_value_one()); // p-1
BN_sub(r2, q, BN_value_one()); // q-1/
BN_mul(r0, r1, r2, ctx); // (p-1)(q-1)
BN_mod_inverse(d, e, r0, ctx); // d
BN_mod(dmp1, d, r1, ctx);
BN_mod(dmq1, d, r2, ctx);
// Nous calculons le module p inverse de q
BN_mod_inverse(iqmp, q, p, ctx);
// Clés RSA
keypair->n = n;
keypair->d = d;
keypair->e = e;
keypair->p = p;
keypair->q = q;
keypair->dmq1 = dmq1;
keypair->dmp1 = dmp1;
keypair->iqmp = iqmp;
PEM_write_RSAPrivateKey(stdout, keypair, NULL, NULL, 0, NULL, NULL);
BN_CTX_end(ctx);
BN_CTX_free(ctx);
RSA_free(keypair);
return 0;
}
hakin9 Nº 3/2007 www.hakin9.org
Fiche technique
60
aop3F8cuI42TDDiHfw1U
/Gk3KvGmpg4jAgMBAAE=
-----FIN DE LA CLE PUBLIQUE-----
Le module est exprimé en chiffres
hexadécimaux. Afin de le convertir
en chiffres décimaux, vous pouvez
utiliser le programme exposé dans
le Listing 1.
gcc hex2dec.c -lssl
/a.out DBA75BAB3191B77D6
A8A7717C72E238D930C388
77F0D54FC69372AF1A6A60E23
99352209973842013949736850170
185769998267119089063339396
575567287426977500707
Une fois le module obtenu en déci-
mal, l'étape suivante consiste à le
décomposer en produit de facteurs
premiers.
Factorisation du module n
Dans la mesure où le nombre que
nous voulons factoriser n'est pas trop
important, il est plus rapide d'appliquer
l'algorithme de factorisation baptisé
QS (Crible Quadratique, en français).
Cet algorithme est installé à l'aide de
msieve, programme que vous pouvez
télécharger en suivant le tableau des
références ci-après. Msieve dispose
d'une documentation suffisante qui
vous permettra de l'installer et de
l'utiliser rapidement sans trop de dif-
ficulté. Ce programme, combiné à la
commande suivante suffit à factoriser
le nombre proposé :
/msieve -v
9935220997384201394973685
01701857699982671190890633
39396575567287426977500707
Un ordinateur moderne peut factoriser
ce nombre en près de dix minutes,
selon le matériel informatique disponi-
ble. Le résultat est le suivant :
factor: 297153055211137492311
771648517932014693
factor: 334346924022870445836
047493827484877799
À ce stade, une fois le module n
factorisé et grâce à l'exposant de
cryptage 65537 obtenu lors de
l'étape précédente, nous disposons
de toutes les données nécessaires
pour l'obtention de la clé privée.
Obtention de la clé
privée et décryptage
du message
En raison des difficultés de ce proces-
sus avec les outils les plus communs,
nous allons développer un programme
capable de réaliser cette tâche à notre
place. La source de ce programme
est exposée dans le Listing 3.
Afin de réaliser les calculs néces-
saires, nous avons utilisé la bibliothè-
que OpenSSL. Les variables BIGNUM
sont employées par cette bibliothèque
pour travailler sur les gros chiffres. Ces
variables possèdent leur propre interfa-
ce de programmation pour réaliser des
opérations telles qu'additions, soustrac-
tions, opérations modulaires, etc.
Listing 3. Modifier une clé privée en une clé publique
gcc get _ priv _ key.c -lssl -o get _ priv _ key
./get _ priv _ key 297153055211137492311771648517932014693 \
334346924022870445836047493827484877799 65537
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEA26dbqzGRt31qincXxy4jjZMMOId/
DVT8aTcq8aamDiMCAwEAAQIh
AMvT1oXa/rxF3mrVLrR/RS7vK1WTsQ5CWl/+37wztZOpAhEA+4jgEkfalFH+0
S+1
IPKD5wIRAN+NmMH4AF0B8jzMAXHHXGUCEGRpRZnGmVkwSlrTgqj+Zu0CEA7v7
CQR
yRxt09zCGNqcYo0CEDEW7mvozMYYLC5o+zgfV4U=
-----END RSA PRIVATE KEY-----
Listing 4. dfact_client
...
for(;;) {
get_random_seeds(&seed1, &seed2);
switch(status) {
case DF_CLIENT_STATUS_WAITING:
N = recv_N_number(&rel_by_host, host);
if(!N) sleep(DF_TIME_TO_RECV);
else status = DF_CLIENT_STATUS_RUNNING;
break;
case DF_CLIENT_STATUS_RUNNING: {
msieve_obj *obj = NULL;
obj = msieve_obj_new(N, flags, relations, NULL,
NULL, seed1, seed2, rel_by_host, 0, 0);
if (obj == NULL) {
syslog(LOG_ERR, "Factoring initialization failed");
free(N);
return 0;
}
msieve_run(obj);
if(obj) msieve_obj_free(obj);
while(!send_relations(N, host, relations)) sleep(DF_TIME_TO_SEND);
if(unlink(relations)==-1) syslog(LOG_ERR, "unlink(): %s: %s",
relations, strerror(errno));
status = DF_CLIENT_STATUS_WAITING;
free(N);
}
break;
default:
break;
}
...
Attaque par factorisation contre RSA
hakin9 Nº 3/2007 www.hakin9.org 61
Le programme donné en exemple
commence par placer dans les varia-
bles BIGNUM, les paramètres p, q et
e. Ensuite, si vous analysez le code en
détails en vous aidant des commen-
taires, vous pourrez comprendre la
procédure consistant à générer la clé
privée. Il s'agit de la même procédure
que nous avions expliquée précédem-
ment de manière théorique. En réalité,
la seule différence entre le test et la
génération réelle de clés repose sur
le fait que p et q auraient été choisis
de manière aléatoire. Dans notre
exemple, nous les avons obtenus
à partir de la factorisation du module.
Enfin, à l'aide de PEM_write_RSAPri-
vateKey(), nous pouvons rédiger la
clé privée utilisée dans les exemples
au format PEM. Si l'on compare la
clé ainsi générée avec la clé privée
originale, il est clair que notre objectif
a bien été rempli, puisque nous avons
obtenu la clé privée à partir de la clé
publique.
Si nous appliquons notre nou-
velle clé privée sur un fichier texte,
comme par exemple rsa_hacked_
privkey.pem, il est alors possible de
décrypter le message :
openssl rsautl -decrypt
-inkey rsa_hacked_privkey
.pem -in cipher.txt
Algorithmes modernes
de factorisation
Les algorithmes de factorisation ont
énormément progressé au fil du
temps, de sorte qu'aujourd'hui, nous
disposons d'algorithmes particuliè-
rement rapides tels que la Méthode
de la Courbe Elliptique (Elliptic Curve
Method, ou ECM), le Crible Quadra-
tique (Quadratic Sieve, ou QS), ou le
Crible de Corps de Nombre (Number
Field Sieve, ou NFS). Ces algorithmes
donnent également naissance aux
certaines de variations selon le type
de nombre à décomposer en produit
de facteurs premiers où la manière de
résoudre certaines parties du nombre
en question. Ces algorithmes sont as-
sez complexes. Ils sont en règle géné-
rale divisés en deux étapes au cours
desquelles différents calculs condui-
sant à la factorisation du nombre en
question sont effectués. Les algorith-
mes QS et NFS passent par une étape
dite de crible. À ce stade, certains
types de relations sont rassemblés,
pour finalement construire un système
d'équations permettant d'obtenir le
résultat. L'étape dite de crible peut être
réalisée par plusieurs machines fonc-
tionnant de manière simultanée, dans
la mesure où il s'agit normalement de
l'étape la plus longue.
Dans  les  exemples  exposés
plus haut, nous avons utilisé le pro-
gramme msieve, implémentation de
l'algorithme de Crible Quadratique
à  Polynômes  Multiples  (Multiple
Polynomial  Quadratic  Sieve,  ou
MPQS), lui-même étant dérivé de
l'algorithme QS. L'algorithme QA se
révèle plus rapide lorsque vous devez
factoriser des nombres de moins de
110 chiffres. Si cette limite est dé-
passée, il vaut mieux avoir recours
à l'algorithme NFS. Une variation
de l'algorithme NFS est utilisée
pour factoriser tout type de nom-
bres ; il s'agit de l'algorithme GNFS
(General Number Field Sieve). Peu
de programmes libres et gratuits
implémentent  l'algorithme  GNFS,
et le seul programme de ce genre
disponible ne dispose pas d'une
bonne documentation, et n'est pas
facile d'utilisation. Du moins, tel était
le cas au moment où nous rédigions
le présent article. Quoiqu'il en soit,
Listing 5. dfact_server
...
for(;;) {
while(child_count >= DF_MAX_CLIENTS) sleep(1);
sd_tmp = socket_server_accept(sd, client, sizeof(client));
if((pid=fork())==0) {
close(sd);
process_client(sd_tmp, N, num_relations, rel_by_host, client);
} else if (pid>0) {
close(sd_tmp);
child_count++;
} else {
perror("fork()");
}
close(sd_tmp);
}
close(sd);
...
Listing 6. dfact_server (process_relations)
void process_relations(char *N, int num_relations, int seconds) {
for(;;) {
int n_sieves = get_num_relations_in_file(DF_FILE_RELATIONS);
printf ("relations: %d, need: %d \n", n_sieves, num_relations);
// y a-t-il assez de relations ?
if(n_sieves>=num_relations) {
printf("Factoring %s\n", N);
kill(0, SIGUSR1);
uint32 seed1;
uint32 seed2;
uint32 flags;
flags |= MSIEVE_FLAG_USE_LOGFILE;
get_random_seeds(&seed1, &seed2);
factor_integer(N,flags,DF_FILE_RELATIONS,NULL,&seed1,&seed2);
printf("Factoring Done\n");
kill(getppid(), SIGKILL);
exit(0);
}
sleep(seconds);
}
}
hakin9 Nº 3/2007 www.hakin9.org
Fiche technique
62
nous allons nous pencher sur le fonc-
tionnement de l'algorithme GGNFS.
Il s'agit d'une implémentation de l'algo-
rithme GNFS qui, malgré un manque
de stabilité, permet de décomposer
des nombres en produit de facteurs
premiers sans trop de problèmes.
L'algorithme GGNFS comprend
en réalité un groupe d'outils, lesquels,
utilisés un par un, peuvent procéder
à l'ensemble des étapes composant
cet algorithme. Toutefois, un novice
en la matière risque d'avoir du mal
à factoriser un nombre avec cette pro-
cédure assez complexe. C'est la rai-
son pour laquelle l'algorithme GGNFS
comprend un script rédigé en Perl qui
se charge de toutes les tâches né-
cessaires. Ce script permet d'utiliser
le programme sans aucun problème,
mais ce n'est pas le meilleur moyen
d'obtenir le meilleur des outils qui
composent l'algorithme GGNFS.
Le plus simple pour tester ce
programme reste encore d'éditer un
fichier, que nous baptiserons test.n,
dans lequel est indiqué le nombre
que nous souhaitons décomposer en
facteurs premiers.
cat test.n
n: 1522605027922533360535
6183781326374297180681149
6138068865790849458012296
3258952897654000350692006139
Il faut ensuite lancer :
tests/factLat.pl test.n
Ce programme va effectivement
factoriser le nombre, après quelques
bonnes heures de traitement. La du-
rée de traitement dépend du matériel
utilisé. Afin d'optimiser l'algorithme
GGNFS, il vaut mieux ne pas tenir
compte du script factLat.pl pour uti-
liser les outils dont il dispose avec
les bons paramètres. L'utilisation de
l'algorithme mériterait d'y consacrer
un article entier, mais ce n'est malheu-
reusement pas le propos du présent
article. Si vous souhaitez apprendre
à vous en servir, le mieux reste de lire
la documentation disponible avec le
code source et de consulter le forum
de discussions (voir les liens). Il est
également recommandé de consulter
quelques documents sur l'algorithme
NFS. Quoiqu'il en soit, il est néces-
saire de préciser qu'il faut maîtriser
les principes de l'algèbre linéaire ainsi
que la théorie des nombre.
Nécessité d'une
attaque distribuée
La clé factorisée dans cet exemple
est très modeste par rapport à la
longueur des clés généralement uti-
lisées aujourd'hui. Si nous décidions
à l'instant de créer une clé RSA pour
un usage personnel, nous utiliserions
au minimum une clé de 1024 bits.
Pour plus de sécurité, nous pourrions
également utiliser une clé de 2048 ou
4096 bits. Si vous tentez de factoriser
une de ces clés avec un PC familial,
quelle que soit sa vitesse, vous ver-
rez à quel point votre ordinateur va
s'embarquer dans des calculs sans
fin ne menant à rien. La vérité est qu'il
est impossible d'attaquer ce genre
de clés. Mais les avancées techno-
logiques et mathématiques réduisent
de jour en jour cet objectif. Sous
certaines conditions, il est possible de
réaliser des attaques distribuées en
utilisant des centaines de machines
de manière simultanée pour faciliter le
processus de factorisation. De nom-
breuses études ont été menées dans
ce domaine afin d'analyser les possi-
bilités d'attaquer une clé de 1024 bits
(voir la partie consacrée aux liens sur
le Web). Aujourd'hui, ce genre d'atta-
que demeure bien loin de la portée de
la plupart des accros d'informatique,
mais pas de celle de certains gouver-
nements ou organisations.
En outre, l'existence de compéti-
tions telles que la Compétition de Fac-
torisation RSA mentionnée plus haut,
aident considérablement les experts
dans ce domaine en les motivant
à créer des outils distribués destinés
à la factorisation des gros chiffres.
Attaque distribuée
Nous avons évoqué dans les exem-
ples  précédents  le  programme
msieve. Comme nous l'avons appris,
ce programme est facile à utiliser
et le programme est suffisamment
développé pour ne pas créer trop de
problèmes à l'utilisateur. Selon nous,
il s'agit du meilleur programme capable
jusqu'ici  d'implémenter  l'algorithme
de Crible Quadratique (QS). Mais, ce
programme n'est rien de plus qu'une
démo illustrant un usage basique de
la bibliothèque msieve, et ne peut donc
être utilisé que sur une seule machine.
La documentation du programme
comporte quelques méthodes per-
mettant d'utiliser le programme démo
sur différentes machines de sorte
à réaliser une factorisation distribuée.
Il s'agit toutefois d'une procédure ma-
nuelle, très peu pratique. C'est la rai-
son pour laquelle nous avons décidé
d'implémenter un modeste exemple
de programme introduisant l'utilisation
de la bibliothèque msieve pour réali-
ser une factorisation distribuée. Ce
programme est baptisé dfact, et vous
le trouverez sur le CD proposé avec
ce magazine ainsi que dans la partie
consacrée aux liens sur le Web.
Le programme peut être compilé
avec un Makefile et n'exige que l'ins-
tallation correcte de la bibliothèque
msieve. Le chemin de cette bibliothè-
que doit être inclus dans le Makefile.
Une fois compilé, vous trouverez deux
binaires dans le dossier bin/ corres-
pondant aux côtés client et serveur.
Le serveur (dfs) sera exécuté sur
une machine avec une capacité de
mémoire suffisante (plus le nombre
est gros, plus il faudra de mémoire),
et permettra de distribuer les charges
et coordonner les clients. Le serveur
prend quatre paramètres : le nombre
à factoriser, le nombre de relations
que nous voulons voir recompilée par
le client pour chaque paquet envoyé
et le nombre de secondes qu'il faut au
serveur pour contrôler s'il dispose de
données client en quantité suffisante
pour terminer avec succès le proces-
sus de factorisation. Dans l'exemple
suivant, nous allons demander aux
clients d'envoyer des relations toutes
les 5000 secondes et au serveur de
vérifier le nombre de relations toutes
les 60 secondes.
bin/dfs 9935220997384201394
973685017018576999826
711908906333939657556
7287426977500707 5000 60
Attaque par factorisation contre RSA
hakin9 Nº 3/2007 www.hakin9.org 63
Nous allons lancer dfc sur quelques
clients, en lui affectant comme para-
mètre l'IP du serveur et le chemin
vers un fichier temporaire où les re-
lations peuvent être sauvegardées.
Par exemple :
bin/dfc /tmp/rel 192.168.1.7
Le programme dfact a été développé
en utilisant comme support de base la
bibliothèque msieve. Celle-ci dispose
d'un exemple de programme baptisé
demo.c, illustrant son fonctionnement
simplifié. Si vous observez attentive-
ment le code, vous constaterez qu'il
n'y a rien de très difficile dans les ins-
tructions à suivre. Nous avons exposé
dans le Listing 4 un extrait de code du
client dfact. Ici, nous exposons le pro-
cessus interne de la boucle principale
au cours duquel le client obtient du
serveur le nombre à factoriser, puis
calcule les relations demandées via
la bibliothèque msieve pour finir par
les envoyer au serveur pour qu'il les
traite.
Regardons comment le serveur
gère la situation (Listing 5). Chaque
client demandant l'envoi de la liste
des relations au serveur est géré par
process_client() via un processus
séparé.
Une autre procédure distincte se
charge de traiter les relations que les
clients envoient à des intervalles de
temps réguliers (Listing 6).
L'exemple de programme nous
permet de factoriser un nombre
à l'aide de plusieurs machines. Même
si cette opération peut être réalisée
via Internet, il est recommandé d'y
renoncer compte tenu du manque
d'authentification et/ou des mécanis-
mes de décryptage. Il serait possible
d'améliorer (ce serait par ailleurs un
excellent exercice pour les lecteurs)
l'usage de SSL, de renforcer la sécu-
rité, d'optimiser la performance, etc...
Nous avions précédemment évo-
qué l'algorithme GNFS, plus efficace
que l'algorithme MPQS lorsqu'il s'agit
de factoriser des nombres à plus de
110 chiffres. À ce stade, il semble
qu'aucun programme open source
ne permette d'implémenter de ma-
nière simple un système distribué de
factorisation avec l'algorithme GNFS,
comme  nous  sommes  parvenus
à le faire avec la bibliothèque msieve
(QS). L'auteur du programme msieve,
toutefois, travaille sur un support pour
l'algorithme GNFS. Même s'il n'est
actuellement qu'à mi-chemin dans la
programmation de ce support, il est
fort possible que la solution définitive
soit disponible dans un futur proche. Si
tel était le cas, il ne serait alors guère
difficile de modifier notre exemple
(dfact) afin de réaliser une factorisation
distribuée avec l'algorithme GNFS.
Quoiqu'il en soit, l'algorithme
GGNFS permet d'utiliser plusieurs
machines à des fins de factorisation.
Ceci est possible grâce au script
factLat.pl, comme nous l'avons de-
montré précédemment, mais sachez
qu'il s'agit d'une version assez insta-
ble qui ne permet d'utiliser que très
peu de machines seulement sur un
réseau LAN. l
À propos de l'auteur
Daniel Lerch Hostalot, ingénieur spécialisé en programmes C/C+ développés sur les
plate–formes GNU/Linux, est titulaire d'un MA en Techniques Sans Fil et Sécurité de
Réseau du Programme de l'Académie Cisco sur Réseaux (Cisco Networking Aca-
demy Program, CCNA). Il travaille également en qualité d'Ingénieur Technique pour
les systèmes informatiques, comme l'y autorise son diplôme délivré par l'Université
Oberta, Catalogne (UOC). Daniel Lerch Hostalot travaille actuellement dans le secteur
des télécommunications. Il maîtrise les langages de programmation suivants : C/C++,
ShellScript, Java, Perl, PHP (programme de modules C).
Vous pouvez contacter l'auteur à l'adresse suivante : dlerch@gmail.com, url :
http://daniellerch.com
Sur Internet
• Factorisation des gros nombres entiers – http://factorizacion.blogspot.com
• DFACT – http://daniellerch.com/sources/projects/dfact/dfact-hakin9.tar.gz
• GGNFS – Implémentation d'un Crible de Corps de Nombre : http://
www.math.ttu.edu/~cmonico/software/ggnfs/
• Groupe Yahoo! Pour l'algorithme GGNFS – http://www.groups.yahoo.com/group/
ggnfs
• MSIEVE – Factorisation d'entiers : http://www.boo.net/~jasonp/qs.html
• Compétition de Factorisation RSA : http://www.rsasecurity.com/rsalabs/
node.asp?id=2092
• OpenSSL – http://www.openssl.org
• Algorithme Shor – http://es.wikipedia.org/wiki/Algoritmo_de_Shor
• Sur le coût de la factorisation RSA 1024 – http://www.wisdom.weizmann.ac.il/
%7Etromer/papers/cbtwirl.pdf
• Estimations sur la factorisation du module RSA à 1024 bits – http://www.wisdom.w
eizmann.ac.il/%7Etromer/papers/factorest.pdf
Compétition de Factorisation RSA
• RSA-704 (30 000 dollars) : http://www.rsasecurity.com/rsalabs/
node.asp?id=2093#RSA704
• RSA-768 (50 000 dollars) : http://www.rsasecurity.com/rsalabs/
node.asp?id=2093#RSA768
• RSA-896 (75 000 dollars) : http://www.rsasecurity.com/rsalabs/
node.asp?id=2093#RSA896
• RSA-1024 (100 000 dollars) : http://www.rsasecurity.com/rsalabs/
node.asp?id=2093#RSA1024
• RSA-1536 (150 000 dollars) : http://www.rsasecurity.com/rsalabs/
node.asp?id=2093#RSA1536
• RSA-2048 (200 000 dollars) : http://www.rsasecurity.com/rsalabs/
node.asp?id=2093#RSA2048