Vous êtes ici : Accueil  > > Papers > >  RSA: Détail mathématique et cassage     Page précédente ;

RSA : détail mathémathique et cassage

Par 4N9e

Sommaire :

Introduction

Souvent utilisé car considéré à l'heure actuelle encore comme parmi les cryptosystèmes comme l'un des plus forts disponibles et dans une moindre mesure parmi les plus aisés à 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 réseau.

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 à appréhender, il reste néanmoins expliqué de manières assez opaques au premier venu sur les différents sites abordant le sujet.

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.

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 chiffrer le message et l'autre pour le déchiffrer. 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 début, ses différentes déclinaisons résistent à 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 à 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échiffrement.

Si quelqu'un veut envoyer un objet, il va le mettre dans une boite, et la fermer avec un des cadenas mis à sa disposition par celui à qui il veut l'envoyer. A partir de là, personne d'autre ne pourra s'emparer de cette boite et l'ouvrir, puisque seule la personne à 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 chiffrement C», et la troisième, «clé de déchiffrement 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 chiffrement 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 à 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 à une seule solution.

II. 3. clé de déchiffrement 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 à chiffrer le message. Les clés D et N servent à le déchiffrer. 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 chiffrement et de déchiffrement. On comprend alors que si on arrive à se procurer p et q, on peut retrouver la facon de déchiffrer 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 à bout, considérons les comme un très grand nombre. C'est lui qu'on va devoir chiffrer.

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 à ce niveau que chaque Mx soit plus petit que N, sinon l'algorithme ne se vérifiera pas.

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

Appellons donc chaque Mx chiffré ainsi «Mcryptx» :

Mcrypt1 = M1 x C mod N

Mcrypt2 = M2 x C mod N

Mcrypt3 = M3 x C mod N

Le message chiffré s'écrit donc : Mcrypt1 Mcrypt2 Mcrypt3 bout à bout, tout comme le message clair M s'écrivait M1 M2 M3.

Le déchiffré se fait en remplacant la clé de chiffrement par celle de déchiffrement :

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 sous tendent le cryptosystème 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 réversible, cassable, attaquable, il n'en reste pas moins dans la réalité souvent impraticable, par faute de puissance des machines actuelles. En gros pour résumer, disons que les formules sont connues mais leur application numérique est si gigantesque à cause de la taille des nombres en question, que les machines personnelles sont incapables à elles seules de le casser dans un laps de temps raisonnable.

Pour exemple, il aura fallut 200 ordinateurs pendant 4 semaines pour établir les sytèmes 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 à trouver la possibilité de casser ce chiffre facilement à 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 cryptosystème RSA. La première sera le travail sur la seule donnée de départ disponible : la clé publique N. La seconde exploitera quant à 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 chiffrement 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 chiffré qu'il souhaite décrypter (!), et d'autre part la clé publique N.

On sait que :

N = p x q

Les clés de chiffrement C et de déchiffrement 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 siècles, quelle que soit la machine utilisée.

Devant ce probleme, les analystes ont developpé 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 présent

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 suivi depuis le début 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 emmeler le lecteur peu habitué aux expressions pleines de lettres, et il y en a suffisament dans cet article, la démonstration sera numérique pour l'expression de A et B, de façon à garder X et Y en évidence.

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)

Considérons 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 déchiffrement 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 définition par p et q, on peut dire que p divise X-Y et q divise X+Y. On cherche donc en réalité à 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 écrire aussi :

|N-ax²|=facteurs (pi^nij)

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

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 à present l 1, l 2 et l 3 qui vérifient (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 à 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 déterminer à 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 à 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'intérêt de la technique réside dans le fait qu'on factorise des nombres de grande taille en s'attaquant à N-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 chiffrement

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

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

W1 = MC1 mod N

W2 = MC2 mod N

L'attaque par comparaison va consister alors à se débrouiller sans clé de déchiffrement. 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 die au système qu'au fait que celui-ci ait été compromis par des fuites de clés et du même message chiffré 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 complèxes encore ! ) est quant à elle quasi impossible au niveau du simple utilisateur. Ceci à 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 chiffrement 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 dizaine de semaines !

Article paru sur FutureZone ;

4N9e

Contacter l'auteur ;

Page précédente  |   Accueil  |   Allez Up ! ;