Attaque par factorisation

contre RSA
Fiche technique

Daniel Lerch Hostalot

l'ordre des nombres

décimaux à 100
chiffres. Degré de difficulté

RSA représente sans conteste le système cryptographique à

clé publique le plus utilisé de nos jours puisqu'il est parvenu
à survivre aux critiques des spécialistes en cryptographie
pendant plus d'un quart de siècle. La fiabilité de cet algorithme
mondialement connu repose notamment sur la difficulté de
décomposer en produit de facteurs premiers de gros chiffres, de

N
ous allons étudier dans le présent ar- doit demeurer confidentielle, la clé publique peut
ticle les travaux internes de RSA et la être mise à la disposition de quiconque désirant
possibilité de lancer des attaques dites envoyer des messages cryptés à l'utilisateur.
par factorisation. Nous verrons comment les Un message crypté à l'aide d'une clé publique
clés de l'algorithme RSA ainsi que la procédure ne peut être décrypté qu'à l'aide de la clé privée
de l'attaque permettent d'obtenir la clé privée correspondante. Or, pour ce faire, il faut aborder
correspondant à la clé publique attaquée. certains problèmes d'ordre mathématique. Notre
Afin de bien comprendre et réutiliser le choix s'est porté sur le système RSA en raison
présent article, le lecteur doit maîtriser les prin- de la décomposition en produit de facteurs pre-
cipes fondamentaux liés à la programmation miers, ou factorisation, de gros chiffres.
en C et savoir manier certains concepts ma- Les débuts de la cryptographie à clé publique
thématiques. Vous trouverez dans le tableau remonte à la publication de Diffie et Hellman en
des références des sources de documentation 1976. Dans cette publication, les deux chercheurs
complémentaires pour de plus amples rensei- ont introduit un protocole capable d'autoriser
gnements sur le sujet. l'échange de certaines informations sur un canal
Tous les exemples ont été développés et
testés sur un système GNU/Linux.
Cet article explique…
Cryptographie à clé publique • Fonctionnement de RSA,
Contrairement à la cryptographie à clé privée, où • Techniques permettant de lancer des attaques
une seule clé est utilisée pour crypter et décryp- par factorisation.
ter les messages, la cryptographie à clé publique
repose sur deux clés, concept également appelé Ce qu'il faut savoir…
biclé. Ces deux clés sont respectivement dé-
nommées clé publique et clé privée. Afin de cryp- • Principes fondamentaux de la programmation
ter la communication choisie, l'utilisateur aura en C.
besoin des deux clés. Alors que la clé privée

2 hakin9 Nº 2/2007 [Link]

 Attaque par factorisation contre RSA

non sécurisé. Peu de temps après, en de décomposer en produit de fac- bits (à l'instar de celle que nous allons
1977, les chercheurs Rivest, Shamir et teurs premiers, ou factoriser, de gros attaquer ultérieurement) comprend
Adleman ont proposé leur propre sys- chiffres. Factoriser un nombre con- près de 78 chiffres décimaux (1078).
tème de cryptographie baptisé RSA, siste à trouver les nombres premiers Dans la mesure où sur les clés du sys-
aujourd'hui le plus largement utilisé au (facteurs) dont le produit donne pour tème RSA, ce nombre ne possède en
monde. résultat le nombre en question. Si, par règle générale que deux facteurs pre-
Toujours en 1977, des documents exemple, vous souhaitez factoriser le miers, chacun de ces facteurs auront
ont démontré que les cryptographes nombre 12, vous allez obtenir un résul- plus ou moins 39 chiffres. Autrement
du British Government Group pour la tat de 2·2·3. La méthode la plus simple dit, pour factoriser le nombre en ques-
Sécurité des Communications Elec- pour trouver les facteurs premiers d'un tion, il faudra le diviser par l'ensemble
troniques (GSEC) connaissaient déjà nombre n consiste à diviser ce dernier des nombres premiers à 39 chiffres
ce type de cryptographie en 1973. par l'ensemble des nombres premiers ou moins (1039). En supposant que
inférieurs à n. Quoique extrêmement seul 0,1% des nombres soient des
Système simple, cette procédure peut se révéler nombres premiers, il faudra procéder
cryptographique RSA très fastidieuse lorsque vous souhaitez à près de 1036 divisions. Imaginons
Comme nous venons de le dire précé- factoriser de gros chiffres. maintenant que vous disposiez d'un
demment, la sécurité du système RSA Procédons à quelques calculs pour système capable de réaliser 1020
repose sur la difficulté mathématique vous donner une idée. Une clé de 256 divisions par seconde. Dans ce cas,
vous passerez quelques 1016 secon-
des à attaquer la clé, autant dire plus
Concepts mathématiques de 300 millions d'années, soit un mil-
lion l'âge de l'univers. Heureusement,
Diviseur ou facteur
nous serons bien plus rapide grâce à
Un nombre entier a désigne un diviseur (ou facteur) de b lorsqu'il existe d'autres
nombres entiers c compatibles avec b = a ⋅ c . Exemple : 21 = 7 ⋅ 3
l'exemple décrit ci-après.
Analysons désormais le fonction-
Nombres premiers et nombres composés nement du système RSA. Il faut com-
Un nombre entier est dit premier si ce dernier ne peut être divisé que par un et mencer par générer les clés publiques
lui-même. Un nombre entier est dit composé lorsqu'il ne rentre pas dans la catégorie
et privées (vous trouverez dans le
des nombres premiers.
tableau ci-joint quelques illustrations
Exemple : 21 = 7 ⋅ 3 est un nombre composé, alors que 7 et 3 sont des nombres
de concepts mathématiques particu-
premiers.
lièrement intéressants). Pour ce faire,
Factorisation il est nécessaire de bien respecter les
La factorisation d'un nombre entier n consiste à décomposer ce dernier en produit étapes comme suit.
de ses facteurs premiers : n = p1e ⋅ p e2 ⋅⋅⋅ pie où pi représentent des nombres premiers
1 2 i

et ei représentent des nombres entiers positifs. Exemple : 84 peut être factorisé en

Etape 1
21 = 22 ⋅ 3 ⋅ 7 .
Il faut tout d'abord choisir deux
Module nombres premiers p et q de manière
Un module désigne et représente a mod b le reste de la division entière de a aléatoire, puis les multiplier pour ob-
entre b . tenir n : n = p ⋅ q . Si vous choisissez
Exemple : 5 mod 3 = 2 , 10 mod 7 = 3 , 983 mod 3 = 2 , 1400 mod 2 = 0 . par exemple, p = 3 et q = 11 vous
a et b sont des modules de n : b ≡ a ( mod n ) si leur différence (a-b) est un multiple obtiendrez n = 33 .
den.

Diviseur commun maximum Etape 2

Est désigné par diviseur commun maximum de deux nombres entiers a et Il faut ensuite calculer l'indicateur
b , représentée sous forme de mcd ( a , b) , le nombre entier le plus élevé pouvant (ou fonction indicatrice) d'Euler
diviser a et b . à l'aide de la formule suivante :
Exemple : mcd ( 42, 35) = mcd ( 2 ⋅ 3 ⋅ 7, 5 ⋅ 7) = 7 Algorithme euclidien Φ ( n ) = Φ ( p ⋅ q ) = ( p − 1) ⋅ ( q − 1) . Dans
L'algorithme euclidien permet de calculer le diviseur commun maximum de deux
cet exemple, vous devez obtenir
nombres selon mcd ( a , b) = mcd ( b, r ) , où a > b > 0 représentent des nombres entiers,
Φ ( n ) = 20 .
et r le reste de la division entre a et b Exemple : mcd (1470, 42)
(1) 1470 mod 42 = 35 → mcd (1470, 42) = mcd ( 42, 35)
(2) 42 mod 35 = 7 → mcd ( 42, 35) = mcd (35, 7) Etape 3
(3) 35 mod 7 = 0 → mcd ( 7, 0) = 7 Indicateur (ou fonction indicatrice) d'Euler Vous trouvez un exposant de cryp-
Soit n ≥ 0 représentant Φ ( n ) le nombre d'entiers compris dans l'intervalle [1, n ] tage (que vous allez utiliser par la
étant premiers* avec n . Pour n = p ⋅ q , Φ ( n ) = ( p − 1) ( q − 1) . suite pour le cryptage) que vous
*Deux entiers a et b représentent les nombres premiers entre eux (ou co-pre- allez appeler e. Ce nombre doit être
mier) si mcd ( a , b) = 1 . compatible avec mcd (e, Φ ( n )) = 1 Un
excellent exemple serait : e = 3 dans

[Link] hakin9 Nº 2/2007 3

 Fiche Technique

la mesure où il ne possède aucun la sécurité des systèmes cryptogra- rer les clés nécessaires et de crypter
facteur commun avec 20 (facteurs phiques repose sur le nombre n. En le message que vous allez ensuite
2 et 5). d'autres termes, si un pirate capable utiliser sous forme de cible pour
d'accéder à la clé publique parvient votre attaque. Il faudra ensuite facto-
Etape 4 à factoriser n en obtenant p et q, il lui riser le module n pour obtenir la clé
Il faut ensuite calculer un exposant suffit alors d'appliquer les formules privée, et enfin décrypter le message
de décryptage que vous allez ap- précédentes pour obtenir la clé pri- en question.
peler d (il vous servira plus tard vée tant convoitée.
au décryptage). Ce nombre doit OpenSSL et RSA
correspondre à 1 < d < Φ ( n ) de sorte Compétition de OpenSSL est un outil cryptographi-
que e ⋅ d ≡ 1( mod Φ ( n )) . Autrement dit, factorisation RSA que open source particulièrement
d sera un nombre compris entre 1 et La Compétition de Factorisation pratique. Dans la partie consacrée
20 qui, multiplié par 3 et divisé par 20 RSA est un concours financé par les aux références, vous trouverez
donnera 1. L'exposant de décryptage Laboratoires RSA au cours duquel toutes les informations nécessaires
d peut alors être le nombre 7. d'importants prix sont décernés aux pour le télécharger, mais sachez que
informaticiens capables de factoriser la plupart des distributions GNU/
Clés certains nombres particulièrement Linux le proposent par défaut. Nous
La clé publique de l'utilisateur appar- importants. Pour parvenir à connaî- allons donc l'utiliser ici pour configu-
tient au couple (n,e), soit dans notre tre le statut des systèmes de facto- rer un environnement de test dans
exemple (33, 3), alors que la clé risation, il faut savoir quelle longueur lequel l'attaque sera lancée.
privée correspond à d, soit 7. Logi- de clé va être nécessaire pour garan- La première étape consiste à
quement, les nombres p, q et d Φ ( n ) tir la sécurité du système RSA. générer un couple de clés pour le
doivent demeurer confidentiels. À l'heure où nous rédigeons le cryptage et le décryptage. Nous
présent article, le record de factori- allons générer des clés de 256 bits,
(Dé)cryptage sation est RSA-640, nombre à 193 certes trop courtes pour maintenir un
Arrivé à ce stade, il suffit de pro- chiffres décomposé en produits de niveau de sécurité sur nos communi-
céder au cryptage à l'aide de facteurs premiers le 2 novembre cations, mais largement suffisantes
C = M e mod n puis au décryptage 2005 par F. Bahr et al. La prochaine pour illustrer nos propos.
grâce à M = Cd mod n . Si nous sup- compétition portera sur RSA-704, Nous générons donc une paire
posons que le message est M = 5 , avec un prix de 30 000 dollars. de clés, en maintenant notre clé pri-
le chiffrage correspondant sera alors La Compétition de Factorisation vée confidentielle.
C = 53 mod 33 = 26 . Afin de décrypter RSA demeure sans aucun doute le
le message, il suffira d'appliquer moyen le plus pratique de se faire # Génération d'une paire de clés à 256
M = 267 mod 33 = 5 . une idée sur l'état actuel des systè- bits du système RSA
Comme nous l'avons mentionné mes de factorisation. openssl genrsa -out rsa_privkey
en début d'article, et comme le Vous trouverez dans le tableau .pem 256
démontre la procédure ci-dessus, exposé à la fin du présent article les cat rsa_privkey.pem
compétitions actuellement organi- -----DEBUT DE LA CLE PRIVEE-----
sées en la matière. MIGqAgEAAiEA26dbqzGRt31qincXxy
Listing 1. Transformation d'un
4jjZMMOId/DVT8aTcq8aam
chiffre hexadécimal en chiffre
décimal
Attaque par DiMCAwEAAQIh
factorisation AmvT1oXa/rxF3mrVLrR/RS7vK1WT
#include <stdio.h> Nous allons présenter ci-après un sQ5CWl/+37wztZOpAhEA+4jg
#include <openssl/bn.h> exemple d'attaque par factorisation EkfalFH+0S+1
int main (int argc, char **argv) {
dirigée contre une clé du système IPKD5wIRAN+NmMH4AF0B8jz
BIGNUM *n = BN_new();
if (argc!=2) { RSA. Afin de rendre les calculs plus MAXHHXGUCEGRpRZnGmV
printf ("%s <hex>\n", rapides, nous utiliserons une clé kwSlrTgqj+Zu0CEA7v7CQR
argv[0]); bien plus courte que les clés norma- yRxt09zCGNqcYo0CEDEW7mvoz
return 0; lement utilisées, afin d'en simplifier la MYYLC5o+zgfV4U=
}
décomposition en facteurs premiers. -----FIN DE LA CLE PRIVEE RSA-----
if(!BN_hex2bn(&n, argv[1])) {
printf("error: Même si cet exemple ne se conforme
BN_hex2bn()"); pas à la réalité, il permettra toutefois Après cette étape, nous sauvegar-
return 0; d'analyser les éléments constituant dons la clé publique dans un fichier.
} une attaque complète. Il s'agit de la clé que nous allons
printf("%s\n", BN_bn2dec(n));
Il faut commencer par créer un publier afin de permettre à quicon-
BN_free(n);
} environnement de travail au moyen que de nous envoyer des messages
de l'outil OpenSSL, chargé de géné- cryptés.

4 hakin9 Nº 2/2007 [Link]

 Attaque par factorisation contre RSA

# Sauvegarde de la clé publique sur un Exponent: 65537 (0x10001) writing RSA key
fichier Modulus=DBA75BAB3191B77D -----DEBUT DE LA CLE PUBLIQUE-----
openssl rsa -in rsa_privkey.pem 6A8A7717C72E238D930C38877 MdwwDQYJKoZIhvcNAQEBBQ
-pubout -out rsa_pubkey.pem F0D54FC69372AF1A6A60E23 ADKwAwKAIhANunW6sxkbd9
cat rsa_pubkey.pem
-----DEBUT DE LA CLE PUBLIQUE----- Listing 2. Clé privée
MdwwDQYJKoZIhvcNAQEBB
QADKwAwKAIhANunW6sxkbd #include <stdio.h>
#include <openssl/bn.h>
9aop3F8cuI42TDDiHfw1U
#include <openssl/rsa.h>
/Gk3KvGmpg4jAgMBAAE=
#include <openssl/engine.h>
-----FIN DE LA CLE PUBLIQUE----- #include <openssl/pem.h>
int main (int argc, char **argv) {
Après avoir générer cette paire de RSA *keypair = RSA_new();
BN_CTX *ctx = BN_CTX_new();
clés, il est désormais possible de
BN_CTX_start(ctx);
crypter et de décrypter les messa- BIGNUM *n = BN_new();
ges. Nous allons travailler sur le BIGNUM *d = BN_new();
message suivant : BIGNUM *e = BN_new();
BIGNUM *p = BN_new();
BIGNUM *q = BN_new();
echo "Forty-two" > [Link]
BIGNUM *dmp1 = BN_new();
BIGNUM *dmq1 = BN_new();
Ce message peut être facilement BIGNUM *iqmp = BN_new();
crypté au moyen de la commande BIGNUM *r0 = BN_CTX_get(ctx);
suivante et de la clé publique : BIGNUM *r1 = BN_CTX_get(ctx);
BIGNUM *r2 = BN_CTX_get(ctx);
BIGNUM *r3 = BN_CTX_get(ctx);
openssl rsautl -encrypt
if (argc!=4) {
-pubin -inkey rsa_pubkey.pem \ printf ("%s [p] [q] [exp]\n", argv[0]);
-in [Link] -out [Link] return 0;
}
BN_dec2bn(&p, argv[1]);
Afin de décrypter le message, nous
BN_dec2bn(&q, argv[2]);
utiliserons la clé privée : BN_dec2bn(&e, argv[3]);
if(BN_cmp(p, q)<0) {
openssl rsautl -decrypt -inkey BIGNUM *tmp = p;
rsa_privkey.pem -in [Link] p = q;
q = tmp;
}
Une fois le fonctionnement de l'outil // Nous calculons n
OpenSSL avec le système RSA maî- BN_mul(n, p, q, ctx);
trisé, et en étant conscient de la né- // Nous calculons d
cessité de disposer de la clé privée BN_sub(r1, p, BN_value_one()); // p-1
BN_sub(r2, q, BN_value_one()); // q-1/
pour pouvoir décrypter les messa-
BN_mul(r0, r1, r2, ctx); // (p-1)(q-1)
ges, notre objectif consiste à obtenir BN_mod_inverse(d, e, r0, ctx); // d
cette clé privée sans avoir accès à BN_mod(dmp1, d, r1, ctx);
l'originale. En d'autres termes, il faut BN_mod(dmq1, d, r2, ctx);
tenter d'obtenir la clé privée en utili- // Nous calculons le module p inverse de q
BN_mod_inverse(iqmp, q, p, ctx);
sant la clé publique. Il faut donc com-
// Clés RSA
mencer par obtenir le module n ainsi keypair->n = n;
que l'exposant de cryptage. Pour ce keypair->d = d;
faire, il suffit d'utiliser la commande keypair->e = e;
suivante avec la clé publique : keypair->p = p;
keypair->q = q;
keypair->dmq1 = dmq1;
openssl rsa -in rsa_pubkey.pem
keypair->dmp1 = dmp1;
-pubin -text -modulus keypair->iqmp = iqmp;
Modulus (256 bit): PEM_write_RSAPrivateKey(stdout, keypair, NULL, NULL, 0, NULL, NULL);
[Link] BN_CTX_end(ctx);
BN_CTX_free(ctx);
[Link]
RSA_free(keypair);
[Link]
return 0;
[Link] }
[Link]

[Link] hakin9 Nº 2/2007 5

 Fiche Technique

aop3F8cuI42TDDiHfw1U /[Link] DBA75BAB3191B77D6 Factorisation du module n

/Gk3KvGmpg4jAgMBAAE= A8A7717C72E238D930C388 Dans la mesure où le nombre que
-----FIN DE LA CLE PUBLIQUE----- 77F0D54FC69372AF1A6A60E23 nous voulons factoriser n'est pas trop
99352209973842013949736850170 important, il est plus rapide d'appliquer
Le module est exprimé en chiffres 185769998267119089063339396 l'algorithme de factorisation baptisé
hexadécimaux. Afin de le convertir 575567287426977500707 QS (Crible Quadratique, en français).
en chiffres décimaux, vous pouvez Cet algorithme est installé à l'aide de
utiliser le programme exposé dans Une fois le module obtenu en déci- msieve, programme que vous pouvez
le Listing 1. mal, l'étape suivante consiste à le télécharger en suivant le tableau des
décomposer en produit de facteurs références ci-après. Msieve dispose
gcc hex2dec.c -lssl premiers. d'une documentation suffisante qui
vous permettra de l'installer et de
Listing 3. Modifier une clé privée en une clé publique l'utiliser rapidement sans trop de dif-
ficulté. Ce programme, combiné à la
gcc get_priv_key.c -lssl -o get_priv_key commande suivante suffit à factoriser
./get_priv_key 297153055211137492311771648517932014693 \ le nombre proposé :
334346924022870445836047493827484877799 65537
-----BEGIN RSA PRIVATE KEY----- /msieve -v
MIGqAgEAAiEA26dbqzGRt31qincXxy4jjZMMOId/ 9935220997384201394973685
DVT8aTcq8aamDiMCAwEAAQIh 01701857699982671190890633
AMvT1oXa/rxF3mrVLrR/RS7vK1WTsQ5CWl/+37wztZOpAhEA+4j 39396575567287426977500707
gEkfalFH+0S+1
IPKD5wIRAN+NmMH4AF0B8jzMAXHHXGUCEGRpRZnGmVkwS Un ordinateur moderne peut factoriser
lrTgqj+Zu0CEA7v7CQR ce nombre en près de dix minutes,
yRxt09zCGNqcYo0CEDEW7mvozMYYLC5o+zgfV4U= selon le matériel informatique disponi-
-----END RSA PRIVATE KEY----- ble. Le résultat est le suivant :

factor: 297153055211137492311
771648517932014693
Listing 4. dfact_client factor: 334346924022870445836

... 047493827484877799
for(;;) {
get_random_seeds(&seed1, &seed2); À ce stade, une fois le module n
switch(status) {
factorisé et grâce à l'exposant de
case DF_CLIENT_STATUS_WAITING:
N = recv_N_number(&rel_by_host, host);
cryptage 65537 obtenu lors de
if(!N) sleep(DF_TIME_TO_RECV); l'étape précédente, nous disposons
else status = DF_CLIENT_STATUS_RUNNING; de toutes les données nécessaires
break; pour l'obtention de la clé privée.
case DF_CLIENT_STATUS_RUNNING: {
msieve_obj *obj = NULL;
obj = msieve_obj_new(N, flags, relations, NULL,
Obtention de la clé
NULL, seed1, seed2, rel_by_host, 0, 0); privée et décryptage
if (obj == NULL) { du message
syslog(LOG_ERR, "Factoring initialization failed"); En raison des difficultés de ce proces-
free(N);
sus avec les outils les plus communs,
return 0;
}
nous allons développer un programme
msieve_run(obj); capable de réaliser cette tâche à notre
if(obj) msieve_obj_free(obj); place. La source de ce programme
while(!send_relations(N, host, relations)) sleep(DF_TIME_TO_SEND); est exposée dans le Listing 3.
if(unlink(relations)==-1) syslog(LOG_ERR, "unlink(): %s: %s",
Afin de réaliser les calculs néces-
relations, strerror(errno));
status = DF_CLIENT_STATUS_WAITING;
saires, nous avons utilisé la bibliothè-
free(N); que OpenSSL. Les variables BIGNUM
} sont employées par cette bibliothèque
break; pour travailler sur les gros chiffres. Ces
default:
variables possèdent leur propre interfa-
break;
}
ce de programmation pour réaliser des
... opérations telles qu'additions, soustrac-
tions, opérations modulaires, etc.

6 hakin9 Nº 2/2007 [Link]

 Attaque par factorisation contre RSA

Le programme donné en exemple question sont effectués. Les algorith- QS. L'algorithme QA se révèle plus
commence par placer dans les varia- mes QS et NFS passent par une étape rapide lorsque vous devez factoriser
bles BIGNUM, les paramètres p, q et dite de crible. À ce stade, certains des nombres de moins de 110 chif-
e. Ensuite, si vous analysez le code en types de relations sont rassemblés, fres. Si cette limite est dépassée, il
détails en vous aidant des commen- pour finalement construire un système vaut mieux avoir recours à l'algorith-
taires, vous pourrez comprendre la d'équations permettant d'obtenir le me NFS. Une variation de l'algorith-
procédure consistant à générer la clé résultat. L'étape dite de crible peut être me NFS est utilisée pour factoriser
privée. Il s'agit de la même procédure réalisée par plusieurs machines fonc- tout type de nombres ; il s'agit de
que nous avions expliquée précédem- tionnant de manière simultanée, dans l'algorithme GNFS (General Number
ment de manière théorique. En réalité, la mesure où il s'agit normalement de Field Sieve). Peu de programmes
la seule différence entre le test et la l'étape la plus longue. libres et gratuits implémentent l'algo-
génération réelle de clés repose sur Dans les exemples exposés rithme GNFS, et le seul programme
le fait que p et q auraient été choisis plus haut, nous avons utilisé le pro- de ce genre disponible ne dispose
de manière aléatoire. Dans notre gramme msieve, implémentation de pas d'une bonne documentation,
exemple, nous les avons obtenus à l'algorithme de Crible Quadratique à et n'est pas facile d'utilisation. Du
partir de la factorisation du module. Polynômes Multiples (Multiple Poly- moins, tel était le cas au moment
Enfin, à l'aide de PEM_write_RSA- nomial Quadratic Sieve, ou MPQS), où nous rédigions le présent article.
PrivateKey(), nous pouvons rédiger la lui-même étant dérivé de l'algorithme Quoiqu'il en soit, nous allons nous
clé privée utilisée dans les exemples
au format PEM. Si l'on compare la Listing 5. dfact_server
clé ainsi générée avec la clé privée
originale, il est clair que notre objectif ...
for(;;) {
a bien été rempli, puisque nous avons
while(child_count >= DF_MAX_CLIENTS) sleep(1);
obtenu la clé privée à partir de la clé sd_tmp = socket_server_accept(sd, client, sizeof(client));
publique. if((pid=fork())==0) {
Si nous appliquons notre nou- close(sd);
velle clé privée sur un fichier texte, process_client(sd_tmp, N, num_relations, rel_by_host, client);
} else if (pid>0) {
comme par exemple rsa_hacked_
close(sd_tmp);
[Link], il est alors possible de child_count++;
décrypter le message : } else {
perror("fork()");
openssl rsautl -decrypt }
close(sd_tmp);
-inkey rsa_hacked_privkey
}
.pem -in [Link]
close(sd);
...
Algorithmes modernes
de factorisation
Les algorithmes de factorisation ont Listing 6. dfact_server (process_relations)
énormément progressé au fil du
void process_relations(char *N, int num_relations, int seconds) {
temps, de sorte qu'aujourd'hui, nous
for(;;) {
disposons d'algorithmes particuliè- int n_sieves = get_num_relations_in_file(DF_FILE_RELATIONS);
rement rapides tels que la Méthode printf ("relations: %d, need: %d \n", n_sieves, num_relations);
de la Courbe Elliptique (Elliptic Curve // y a-t-il assez de relations ?
Method, ou ECM), le Crible Quadra- if(n_sieves>=num_relations) {
printf("Factoring %s\n", N);
tique (Quadratic Sieve, ou QS), ou le
kill(0, SIGUSR1);
Crible de Corps de Nombre (Number uint32 seed1;
Field Sieve, ou NFS). Ces algorithmes uint32 seed2;
donnent également naissance aux uint32 flags;
certaines de variations selon le type flags |= MSIEVE_FLAG_USE_LOGFILE;
get_random_seeds(&seed1, &seed2);
de nombre à décomposer en produit
factor_integer(N,flags,DF_FILE_RELATIONS,NULL,&seed1,&seed2);
de facteurs premiers où la manière de printf("Factoring Done\n");
résoudre certaines parties du nombre kill(getppid(), SIGKILL);
en question. Ces algorithmes sont as- exit(0);
sez complexes. Ils sont en règle géné- }
sleep(seconds);
rale divisés en deux étapes au cours
}
desquelles différents calculs condui- }
sant à la factorisation du nombre en

[Link] hakin9 Nº 2/2007 7

 Fiche Technique

pencher sur le fonctionnement de également recommandé de consulter problèmes à l'utilisateur. Selon nous, il
l'algorithme GGNFS. Il s'agit d'une quelques documents sur l'algorithme s'agit du meilleur programme capable
implémentation de l'algorithme NFS. Quoiqu'il en soit, il est néces- jusqu'ici d'implémenter l'algorithme
GNFS qui, malgré un manque de saire de préciser qu'il faut maîtriser de Crible Quadratique (QS). Mais, ce
stabilité, permet de décomposer des les principes de l'algèbre linéaire ainsi programme n'est rien de plus qu'une
nombres en produit de facteurs pre- que la théorie des nombre. démo illustrant un usage basique de
miers sans trop de problèmes. la bibliothèque msieve, et ne peut donc
L'algorithme GGNFS comprend Nécessité d'une attaque être utilisé que sur une seule machine.
en réalité un groupe d'outils, lesquels, distribuée La documentation du programme
utilisés un par un, peuvent procéder à La clé factorisée dans cet exemple comporte quelques méthodes per-
l'ensemble des étapes composant cet est très modeste par rapport à la mettant d'utiliser le programme démo
algorithme. Toutefois, un novice en la longueur des clés généralement uti- sur différentes machines de sorte à
matière risque d'avoir du mal à facto- lisées aujourd'hui. Si nous décidions réaliser une factorisation distribuée.
riser un nombre avec cette procédure à l'instant de créer une clé RSA pour Il s'agit toutefois d'une procédure ma-
assez complexe. C'est la raison pour un usage personnel, nous utiliserions nuelle, très peu pratique. C'est la rai-
laquelle l'algorithme GGNFS com- au minimum une clé de 1024 bits. son pour laquelle nous avons décidé
prend un script rédigé en Perl qui se Pour plus de sécurité, nous pourrions d'implémenter un modeste exemple
charge de toutes les tâches néces- également utiliser une clé de 2048 ou de programme introduisant l'utilisation
saires. Ce script permet d'utiliser le 4096 bits. Si vous tentez de factoriser de la bibliothèque msieve pour réali-
programme sans aucun problème, une de ces clés avec un PC familial, ser une factorisation distribuée. Ce
mais ce n'est pas le meilleur moyen quelle que soit sa vitesse, vous ver- programme est baptisé dfact, et vous
d'obtenir le meilleur des outils qui rez à quel point votre ordinateur va le trouverez sur le CD proposé avec
composent l'algorithme GGNFS. s'embarquer dans des calculs sans ce magazine ainsi que dans la partie
Le plus simple pour tester ce fin ne menant à rien. La vérité est qu'il consacrée aux liens sur le Web.
programme reste encore d'éditer un est impossible d'attaquer ce genre Le programme peut être compilé
fichier, que nous baptiserons test.n, de clés. Mais les avancées techno- avec un Makefile et n'exige que l'ins-
dans lequel est indiqué le nombre logiques et mathématiques réduisent tallation correcte de la bibliothèque
que nous souhaitons décomposer en de jour en jour cet objectif. Sous msieve. Le chemin de cette bibliothè-
facteurs premiers. certaines conditions, il est possible de que doit être inclus dans le Makefile.
réaliser des attaques distribuées en Une fois compilé, vous trouverez deux
cat test.n utilisant des centaines de machines binaires dans le dossier bin/ corres-
n: 1522605027922533360535 de manière simultanée pour faciliter le pondant aux côtés client et serveur.
6183781326374297180681149 processus de factorisation. De nom- Le serveur (dfs) sera exécuté sur
6138068865790849458012296 breuses études ont été menées dans une machine avec une capacité de
3258952897654000350692006139 ce domaine afin d'analyser les possi- mémoire suffisante (plus le nombre
bilités d'attaquer une clé de 1024 bits est gros, plus il faudra de mémoire),
Il faut ensuite lancer : (voir la partie consacrée aux liens sur et permettra de distribuer les charges
le Web). Aujourd'hui, ce genre d'atta- et coordonner les clients. Le serveur
tests/[Link] test.n que demeure bien loin de la portée de prend quatre paramètres : le nombre
la plupart des accros d'informatique, à factoriser, le nombre de relations
Ce programme va effectivement mais pas de celle de certains gouver- que nous voulons voir recompilée par
factoriser le nombre, après quelques nements ou organisations. le client pour chaque paquet envoyé
bonnes heures de traitement. La du- En outre, l'existence de compéti- et le nombre de secondes qu'il faut au
rée de traitement dépend du matériel tions telles que la Compétition de Fac- serveur pour contrôler s'il dispose de
utilisé. Afin d'optimiser l'algorithme torisation RSA mentionnée plus haut, données client en quantité suffisante
GGNFS, il vaut mieux ne pas tenir aident considérablement les experts pour terminer avec succès le proces-
compte du script [Link] pour uti- dans ce domaine en les motivant à sus de factorisation. Dans l'exemple
liser les outils dont il dispose avec créer des outils distribués destinés à suivant, nous allons demander aux
les bons paramètres. L'utilisation de la factorisation des gros chiffres. clients d'envoyer des relations toutes
l'algorithme mériterait d'y consacrer les 5000 secondes et au serveur de
un article entier, mais ce n'est malheu- Attaque distribuée vérifier le nombre de relations toutes
reusement pas le propos du présent Nous avons évoqué dans les exem- les 60 secondes.
article. Si vous souhaitez apprendre à ples précédents le programme
vous en servir, le mieux reste de lire msieve. Comme nous l'avons appris, bin/dfs 9935220997384201394
la documentation disponible avec le ce programme est facile à utiliser 973685017018576999826
code source et de consulter le forum et le programme est suffisamment 711908906333939657556
de discussions (voir les liens). Il est développé pour ne pas créer trop de 7287426977500707 5000 60

8 hakin9 Nº 2/2007 [Link]

 Attaque par factorisation contre RSA

Nous allons lancer dfc sur quelques d'un exemple de programme baptisé la bibliothèque msieve pour finir par
clients, en lui affectant comme para- demo.c, illustrant son fonctionnement les envoyer au serveur pour qu'il les
mètre l'IP du serveur et le chemin simplifié. Si vous observez attentive- traite.
vers un fichier temporaire où les re- ment le code, vous constaterez qu'il Regardons comment le serveur
lations peuvent être sauvegardées. n'y a rien de très difficile dans les ins- gère la situation (Listing 5). Chaque
Par exemple : tructions à suivre. Nous avons exposé client demandant l'envoi de la liste
dans le Listing 4 un extrait de code du des relations au serveur est géré par
bin/dfc /tmp/rel [Link] client dfact. Ici, nous exposons le pro- process_client() via un processus
cessus interne de la boucle principale séparé.
Le programme dfact a été développé au cours duquel le client obtient du Une autre procédure distincte se
en utilisant comme support de base la serveur le nombre à factoriser, puis charge de traiter les relations que les
bibliothèque msieve. Celle-ci dispose calcule les relations demandées via clients envoient à des intervalles de
temps réguliers (Listing 6).
L'exemple de programme nous
Compétition de Factorisation RSA permet de factoriser un nombre à
• RSA-704 (30 000 dollars) : [Link]
l'aide de plusieurs machines. Même
[Link]?id=2093#RSA704
• RSA-768 (50 000 dollars) : [Link]
si cette opération peut être réalisée
[Link]?id=2093#RSA768 via Internet, il est recommandé d'y
• RSA-896 (75 000 dollars) : [Link] renoncer compte tenu du manque
[Link]?id=2093#RSA896 d'authentification et/ou des mécanis-
• RSA-1024 (100 000 dollars) : [Link] mes de décryptage. Il serait possible
[Link]?id=2093#RSA1024 d'améliorer (ce serait par ailleurs un
• RSA-1536 (150 000 dollars) : [Link] excellent exercice pour les lecteurs)
[Link]?id=2093#RSA1536 l'usage de SSL, de renforcer la sécu-
• RSA-2048 (200 000 dollars) : [Link] rité, d'optimiser la performance, etc...
[Link]?id=2093#RSA2048
Nous avions précédemment évo-
qué l'algorithme GNFS, plus efficace
que l'algorithme MPQS lorsqu'il s'agit
Sur Internet de factoriser des nombres à plus de
• Factorisation des gros nombres entiers – [Link] 110 chiffres. À ce stade, il semble
• DFACT – [Link] qu'aucun programme open source
• GGNFS – Implémentation d'un Crible de Corps de Nombre : http:// ne permette d'implémenter de ma-
[Link]/~cmonico/software/ggnfs/ nière simple un système distribué de
• Groupe Yahoo! Pour l'algorithme GGNFS – [Link] factorisation avec l'algorithme GNFS,
ggnfs comme nous sommes parvenus à
• MSIEVE – Factorisation d'entiers : [Link]
le faire avec la bibliothèque msieve
• Compétition de Factorisation RSA : [Link]
(QS). L'auteur du programme msieve,
[Link]?id=2092
• OpenSSL – [Link]
toutefois, travaille sur un support pour
• Algorithme Shor – [Link] l'algorithme GNFS. Même s'il n'est
• Sur le coût de la factorisation RSA 1024 – [Link] actuellement qu'à mi-chemin dans la
%7Etromer/papers/[Link] programmation de ce support, il est
• Estimations sur la factorisation du module RSA à 1024 bits – [Link] fort possible que la solution définitive
[Link]/%7Etromer/papers/[Link] 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
À propos de l'auteur distribuée avec l'algorithme GNFS.
Daniel Lerch Hostalot, ingénieur spécialisé en programmes C/C+ développés sur les
Quoiqu'il en soit, l'algorithme
plateformes GNU/Linux, est titulaire d'un MA en Techniques Sans Fil et Sécurité de
GGNFS permet d'utiliser plusieurs
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
machines à des fins de factorisation.
les systèmes informatiques, comme l'y autorise son diplôme délivré par l'Université Ceci est possible grâce au script
Oberta, Catalogne (UOC). Daniel Lerch Hostalot travaille actuellement dans le secteur [Link], comme nous l'avons de-
des télécommunications. Il maîtrise les langages de programmation suivants : C/C++, montré précédemment, mais sachez
ShellScript, Java, Perl, PHP (programme de modules C). qu'il s'agit d'une version assez insta-
Vous pouvez contacter l'auteur à l'adresse suivante : dlerch@[Link], url: http: ble qui ne permet d'utiliser que très
//[Link] peu de machines seulement sur un
réseau LAN.

[Link] hakin9 Nº 2/2007 9

 Fiche Technique

Conclusion
Pour conclure, il est important de
mentionner la répercussion que peu-
vent avoir les avancées mathémati-
ques dans ce domaine. Un nombre
impossible à factoriser aujourd'hui par
les calculs informatiques, pourra l'être
demain en quelques minutes à peine.
Tout repose sur l'idée révolutionnaire
d'un chercheur décidé à résoudre le
problème. Toutefois, les quelques 20
ans de travaux réalisés sur les algo-
rithmes du système RSA sont un vé-
ritable gage de sécurité, rendant cette
éventualité encore lointaine.
La sortie d'ordinateurs quantiques
va également considérablement me-
nacer la sécurité de ce système cryp-
tographique mondialement connu,
notamment grâce à l'algorithme Shor
(voir la section consacrée aux liens
sur le Web) dont la procédure semble
résoudre le problème de la complexité
des polynômes. Cet algorithme va en-
fin permettre de factoriser une clé en
un temps relativement raisonnable.

10 hakin9 Nº 2/2007 [Link]