RSA : détail mathémathique et cassage

Par 4n9e le 14-05-2005

Approfondissement sur le cryptosysteme RSA, et présentation théorique des méthodes d'attaque des clés.

Souvent utilisé car considéré à l'heure actuelle encore comme parmis les cryptosystemes comme l'un des plus forts disponibles et dans une moindre mesure parmis les plus aisés a mettre en oeuvre, le RSA est largement présent dès qu'il s'agit de sécuriser une donnée qui transite sur un reseau.

Nous allons dans cet article tenter de le présenter de la facon la plus claire possible. En effet, force est de constater que, si il est dans son principe encore assez simple a appréhender, il reste néanmoins expliqué de manières assez opaques au premier venu sur les différents sites abordant le jet.
Nous verrons donc dans un premier temps de quoi il retourne, puis différentes manières de l'attaquer, en vue (qui sait ? ) de le casser, au moins en partie sinon totalement.


Sommaire :
I. Définition et historique
I. 1. Un petit retour aux origines?
I. 2. Ainsi naquit le RSA
II. Entrons dans l'aspect technique
II. 1. Clé publique N
II. 2. Clé de cryptage C
II. 3. Clé de décryptage D
II. 4. Déroulement
III. Casser le RSA
III. 1. Avant propos
III. 2. Deux approches différentes d'attaque
III. 3. Factorisation de la clé publique N
IV. Le crible quadratique
IV. 1. Prérequis : L'algorithme d'Euclide
IV. 2. Revenons au crible
IV. 3. Deuxième approche : comparaison des clés de cryptage
V. Conclusion


I. Définition et historique



I. 1. Un petit retour aux origines?

On considère que la cryptographie à clé publique est l'aboutissement des réflexions menées d'une part par Ms. Diffie et Hellman, et d'autre part parallèlement par Merkle.

Le principe moteur est basé sur l'idée de 2 clés: une pour crypter le message et l'autre pour le décrypter. Séduisant dans le principe, ce théorème reste inapliquable longtemps car quasi impossible à mettre en oeuvre de façon viable. La première tentative réussie est la démonstration de Merkle. (un « algorithme à empilement », pour les puristes)

Mais la véritable révolution apparaît avec le RSA. Celui-ci reste dès lors un algorithme veritablement sûr et utilisable dans sa mise en pratique.


I. 2. Ainsi naquit RSA


Il tire son nom des initiales de ses découvreurs : Ron Rivest, Adi Shamir et Leonard Adleman.
Et depuis le debut, ses différentes declinaisons resistent à la plupart des attaques cryptanalytiques. En fait, sa force vient de l'extreme difficulté, même pour les machines actuelles les plus performantes, à factoriser de grands nombres dans un temps suffisament court pour permettre la validité de la donnée. C'est-à-dire que chaque donnée est cachée au monde pour une raison bien précise. Sa durée de vie dépend de son contenu intrinsèque : que faire en effet d'un message qui a été décrypté en deux semaines, si celui-ci annoncait un projet d'acquisition d'une entreprise dans la semaine ? trop tard ?



II. Entrons dans l'aspect technique



Nous sommes en présence d'un système à clés publiques. Pour schématiser, disons que chaque personne dispose de plein de cadenas qu'il met sur une table, disponibles a tous ceux qui voudraient lui envoyer quelque chose. C'est la clé publique. Mais cette personne est la seule à en détenir la seule clé capable d'ouvrir ces cadenas. C'est la clé de décryptage.

Si quelqu'un veut envoyer un objet, il va le mettre dans une boite, et la fermer avec un des cadenas mis a sa disposition par celui a qui il veutl'envoyer. A partir de là, personne d'autre ne pourra s'emparer de cette boite et l'ouvrir, puisque seule la personne a qui elle est destinnée en posède la clé.

Le RSA est basé en réalité sur un triplet de 3 clés. Appelons donc la première « clé publique N », la seconde « clé de cryptage C », et la troisième , « clé de décryptage D ».

II. 1. clé publique N

Cette clé est publique, elle est distribuée à qui la veut. Elle se calcule comme suit : N = p x q
p et q sont deux nombres premiers (i.e : divisibles que par 1 et eux-mêmes) les plus grands possibles, des nombres de centaines de chiffres.

II. 2. clé de cryptage C

elle est gardée précieusement par l'expéditeur du message. Elle n'est jamais divulguée.
C et (p-1)*(q-1) doivent être premiers entre eux (i.e : il n'existe qu'un nombre capable de diviser l'un ou l'autre : 1. Par exemple, 10 et 9 le sont.En effet, pour 10, seuls 2, 5 et 1 peuvent le diviser. Pour 9, seuls 3 et 1 le peuvent. 1 est donc le seul a pouvoir diviser l'un ou l'autre. On remarque que deux nombres premiers entre eux ne sont pas forcement premiers tous les deux). Là, le choix peut être vaste, il ne vient pas d'un calcul a une seule solution.

II. 3. clé de décryptage D

elle est aussi gardée précieusement, mais par le destinataire.D = C-1 MOD (p-1)(q-1), ce qui veut dire qu'il existe un chiffre X avec qui on a D*C + (p-1)(q-1) *X = 1

Les clés N et C servent à crypter le message. Les clés D et N servent à le décrypter. L'idée, c'est que même si chacun connaît une donnée (la clé publique N), on ne peut décoder ce message. Ou presque, nous y reviendrons.

Ce qu'on remarque tout de suite, c'est que les nombres p et q servent à créer C et D, les clés de cryptage et de decryptage. On comprend alors que si on arrive a se procurer p et q, on peut retrouver la facon de decrypter un message. Or, p et q, ce n'est autre que le nombre N. Justement celui dont on dispose.

II. 4. Déroulement

N'importe quelle donnée est composée d'octets. Mis bout a bout, considérons les comme un tres grand nombre. C'est lui qu'on va devoir crypter.
On appelle ce nombre « M ». La première étape est de le séparer en plusieurs petits nombres, tous plus petits que N (notre clé publique). On les appelle tous « Mx » (donc, M1, M2, M3, M4...)

Il est primordial a ce niveau que chaque Mx soit plus petit que N, sinon l'algorithme ne se verifiera pas.

Le but de l'exercice a ce moment là va être de crypter chacun des Mx avec le couple (N, C) et de les decrypter avec (N, D). Je rappelle, N est la clé publique , C la clé de cryptage, et D celle de decryptage.

Appellons donc chaque Mx crypté ainsi « Mcryptx » :
Mcrypt1 = M1 x C mod N
Mcrypt2 = M2 x C mod N
Mcrypt3 = M3 x C mod N
...

Le message crypté s'écrit donc : Mcrypt1 Mcrypt2 Mcrypt3 bout à bout, tout comme le message clair M s'écrivait M1 M2 M3 .
Le decryptage se fait en remplacant la clé de cryptage par celle de decryptage :
M1 = Mcrypt1 x D mod N
M2 = Mcrypt2 x D mod N
M3 = Mcrypt3 x D mod N
...



III. Casser le RSA



III. 1. Avant propos

Les théories qui sou tendent le cryptosysteme RSA sont facilement appréhendables, pour peu qu'on dispose des connaissances de base nécessaires mathématiques, comme nous venons de le voir.

Encore une fois, l'intérêt du RSA réside dans le fait que, si il est relativement facile a mettre en place dans une structure sécurisée, et même si dans la théorie le principe est reversible, cassable, attaquable, il n'en reste pas moins dans la realité souvent impraticable, par faute de puissance des machines actuelles. En gros pour résumer, disons que les formules sont connues mais leur application numerique est si gigantesque à cause de la taille des nombres en question, que les machines personnelles sont incapables a elles seules de le casser dans un laps de temps raisonnable.

Pour exemple, il aura fallut 200 ordinateurs pendant 4 semaines pour établir les sytemes d'équations, puis encore 100 heures d'utilisation d'un CRAY pour le calcul afin de casser une clé RSA-140 (140 est la longueur du nombre).

Que le lecteur ne s'attende donc pas ici a trouver la possibilité de casser ce cryptage facilement a son niveau. Et heureusement ! En effet, celui-ci est utilisé dans diverses applications aussi importantes que les cartes banquaires, les virements boursiers, les comptes banquaires, et dans une moindre importance au sein de Windows, ou encore de Netscape.

Le lecteur attentif aura cependant noté qu'il existe potentiellement un moyen de remonter, à partir de la clé publique N les deux grands nombres premiers p et q. Et par suite, de déduire donc les autres clés du triplet.


III. 2. Deux approches différentes d'attaque

On considère qu'il existe deux attaques majeures possibles du cryptosysteme RSA. La premiere sera le travail sur la seule donnée de départ disponible : la clé publique N. La seconde exploitera quant a elle les protocoles de transit de la donnée, avec pour but de comparer differents messages obtenus par utilisation d'au moins deux clés de cryptage différentes connues.


III. 3. Factorisation de la clé publique N

Le principe part de l'hypothèse suivante : l'attaquant a en sa possession d'une part un message crypté qu'il souhaite decrypter (!), et d'autre part la clé publique N.
On sait que :
N = p x q
Les clés de cryptage C et de decryptage D sont directement issues de p et q, exclusivement.
La théorie veut donc que factoriser N, (c'est-à-dire trouver les nombres qui, entre eux, donnent N) permette de trouver ces deux nombres p et q. En fait, essayer tous les nombres X tels que :
- ils soient premiers
- X soit compris entre 1 et N ( 1 < X > N )


Mais dans la réalité, la taille de N est telle que calculer toutes les solutions prendrait des siecles, quelle que soit la machine utilisée.

Devant ce probleme, les analystes ont developpés des algorithmes permettant cette factorisation de la clé publique de facon optimisée, en un temps plus envisageable.

Deux théories s'offrent à nous, répondant aux doux noms de "courbes elliptiques" et "crible quadratique". C'est celle-ci qui sera détaillée a present



IV. Le crible quadratique


IV. 1. Prérequis : l'algorithme d'Euclide

Cet algorithme va permettre de résoudre l'équation X * A + Y * B = 1 dans laquelle on cherche X et Y, sachant que le plus grand diviseur commun de A et de B est 1 ( on écrit pgcd( A , B ) = 1 ). Ceci signifie au passage pour eux qui ont suivit depuis le debut que A et B sont premiers entre eux.

Partant de là, on sait que d'autre part que si A = B mod C alors pgcd( A , B ) = pgcd( B , C )
Afin de ne pas emmeller le lecteur peu habitué aux expressions pleines de lettres, et il y en a suffisament dans cet article, la demonstration sera numérique pour l'expression de A et B, de facon a garder X et Y en evidence.

Prenons A = 123 et B = 23. L'équation sera alors X * 123 + Y * 23 = 1
123 / 23 = 5, reste 8. Ou encore 123 = 5 * 23 + 8. Donc ici 123 = 8 mod 23, et 8 = 123 - (5*23)

Considerons B : valeur 23. Son diviseur le plus grand est 8. On a donc 23 / 8 = 2, reste 7. Autrement dit 23 = 2 * 8 + 7, et 7= 23 - (2*8)

D'autre part,
8 = 1*7 + 1
d'où: 1 = 8 - 1*7, où on remplace 7 par son équivalence plus haut : 1 = 8 - 1 * (23 - 2*8). On distribue

1 = 3 * 8 - 23 . On remplace 8 par son équivalence trouvée par l'expression de A : 8=123-(5*23)
1 = 3 * (123 - 5*23) - 23
1= 3*123 - 3* (5*23)-23 = 3*123 - 15*23-23
1 = 3 * 123 - 16 * 23 , ce qui exprime bien X * 123 + Y * 23 = 1

Nous avons donc une solution pour l'équation, avec X = 3 et Y = -16

Dans la mesure où dans RSA, le calcul de la clé de decryptage D s'exprime par D*C + (p-1)(q-1) *X = 1, on constate que c'est cet algorithme d'Euclide qui intervient dans le calcul de cette clé.


IV. 2. Revenons au crible

Il s'agit de connaître deux nombres X et Y tels que la clé publique N divise X² - Y²
Or il s'agit là d'une identité remarquable : X² - Y² = ( X-Y ) * ( X+Y )

Comme N se factorise par definition par p et q, on peut dire que p divise X-Y et q divise X+Y. On cherche donc en réalité a trouver soit p, soit q, c'est-à-dire le plus grand diviseur commun (pgcd) de N et X-Y, ou de N et X+Y.

La première étape est donc de déterminer X et Y. Pour cela, on va chercher à établir une suite de carrés ax² qui verifie |N-ax²| < d , où d est un entier manipulable par la machine.

Parallèlement, comme tout nombre peut se factoriser en une suite de nombres premiers (par exemple, 16473 = 3 *17²*19), on a une suite de ces nombres appelés pi tels qu'on peut ecrire aussi
|N-ax²|=facteurs (pi^nij)

Ainsi, si on déroule notre suite avec a1, a2 et a3 on peut ecrire :


N-a1²=p1^n11*p2^n21*p3^n31
N-a2²=p1^n12*p2^n22*p3^n32
N-a3²=p1^n13*p2^n23*p3^n33

Dans cette suite, on va chercher a presentl 1, l 2 et l 3 qui verifient (N-a1²)l1*(N-a2²)l2*(N-a3²)l3=a ²
Ce qui peut s'écrire dans un système d'équations modulaires dont il existe des solutions :

l 1 n11+l 2 n12+l 3 n13=0 mod 2
l 1 n21+l 2 n22+l 3 n23=0 mod 2
l 1 n31+l 2 n32+l 3 n33=0 mod 2

Si on connaît à présent l1 l2 et l3 dans l'équation (N-a1²)l1*(N-a2²)l2*(N-a3²)l3=a ², on a alors

(a1l1*a2l1*a3l1)² = a ²mod N

Si enfin on pose X = a et Y = a1l1*a2l1*a3l1 , on a :

Y² = X² mod N
Y² -X² = 0 mod N

Et par définition, on vient de démontrer que N divise bien Y²-X², en en trouvant les X et Y.
Par suite, connaissant alors X et Y, on connaît X+Y et/ou X-Y. Comme on rappelle que le Graal, c'est-à-dire p et q pour ceux qui se sont perdus en cours de route sont tels que l'un d'eux est le pgcd de N et X+Y ou N et X-Y, il va être beaucoup plus facile a la machine de travailler sur la factorisation de X+Y ou X-Y, de petits nombres en comparaison de la clé publique N !


IV. 3. Où est le crible ?


Le crible intervient lorsqu'on va déterminer les ensembles de petits nombres premiers et les carrés ax².
Comme on l'a vu, l'idée première est de se donner une suite de nombres premiers qui soient facilement calculables, trouvables, ou dont on dispose dans une liste. Ce seront nos nombres premiers « connus », en sorte. On notera cette suite p(i). Par exemple, p1=2, p2=3, p3=5, p4=7, etc...

On va determiner à partir de là, la suite des a, disons « ai » de la facon suivante :
On cherche m tel que : m=E( racine(N) )
On cherche alors les ai=(m+i) tels que ai² est proche de N.
Le crible est un entier naturel qu'on fixe. On va calculer alors R tel que

R=N-(m+i)² et i devient une variable dans une boucle qui varie de -crible à +crible

Il reste à factoriser R avec la suite des pi : p1, p2, p3, ce qui aboutira a l'égalité décrite plus haut dans la recherche de X et Y, c'est-à-dire R=p1n11*p2n21*p3n31, donc N-a1²=p1n11*p2n21*p3n31 L'interet de la technique réside dans le fait qu'on factorise des nombres de grande taille en s'attaquant aN-a1². Toutefois, ces nombres étant dans leur taille de l'ordre de grandeur « racine(N) », on a des tailles en fait deux fois plus petites que celle de N.



IV. 4. Deuxième approche : comparaison des clés de cryptage



Par définition, pour une même clé publique N, il existe plusieurs clés de cryptage C ou de decryptage D. Le principe ici va partir de la supposition qu'on ne dispose bien sur pas de la clé de decryptage, mais qu'on a pu se procurer deux clés de cryptage valides C1 et C2 qui ont été générée a partir de la meme clé N

En pratique, il faut pouvoir disposer du même message M, crypté d'un coté par une clé C1 connue et d'autre part par une autre clé C2 connue elle aussi. Les deux messages cryptés s'appellent W1 et W2. Pour rappel, ils ont été cryptés par les formules

W1 = MC1 mod N
W2 = MC2 mod N

L'attaque par comparaison va consister alors a se debrouiller sans clés de decryptage. On doit pour cela trouver deux nombres a et b qui verifient l'équation

a*C1 + b*C2 = 1

L'un d'eux est donc forcement négatif. Ce qui aboutit à (l'ensemble du calcul modulaire n'est pas détaillé ici) :

(W1-1)-a*W2 = M mod N

Dans ce cas, le message M est obtenu. Toutefois, on peut en conclure ici que la faiblesse n'est pas tant due au systeme qu'au fait que celui-ci ait été compromis par des fuites de clés et du même message crypté deux fois qui n'auraient jamais dûs arriver !



V. Conclusion



Comme on l'a vu, toute méthode de cassage de clé du RSA reste fortement théorique. Leur mise en application (car il en existe d'autres, plus complexes encore ! ) est quant à elle quasi impossible au niveau du simple utilisateur. Ceci a tel point qu'il existe des challenges de cassage de clés de plus en plus grandes (RSA100, RSA140, RSA155)
Des machines sont entièrement dédiées aux tentatives d'attaque de ces clés. Leur principe est une force brute qui consiste à tenter de trouver l'inverse du calcul modulaire qui aboutit au cryptage du message initial. Pour ce faire, elle va chercher toutes les occurrences valides de W-C = M mod N.



Pour le seul RSA155, ce genre d'attaque prend, sur ces machines cadencées à 10Ghz une dixaine de semaines?

4N9e pour FutureZone, 2005