| Menu |
Le
RSA est-il sûr?
Les attaques actuelles du RSA se font
essentiellement en factorisant l'entier n de la clé publique. La sécurité du
RSA repose donc sur la difficulté de factoriser de grands entiers. Le record établi en 1999,
avec l'algorithme le plus performant et des moyens matériels considérables, est
la factorisation d'un entier à 155 chiffres (soit une clé de 512 bits, 2512
étant proche de 10155). Il faut donc, pour garantir une certaine sécurité,
choisir des clés plus grandes : les experts recommandent des clés de 768 bits
pour un usage privé, et des clés de 1024, voire 2048 bits, pour un usage
sensible. Si l'on admet que la puissance des ordinateurs double tous les 18 mois (loi de Moore), une clé de 2048
bits devrait tenir jusque ... 2079
Nous
avons eut la possibilité d’apprécier la difficulté de factoriser un
grand nombre n avec Maple :
Ø
ifactor(130541626083847308469);
Ø
(14524543277) (8987657897)
Ø
Il faut moins d'1 seconde pour factoriser un nombre de 21 chiffres
Ø
ifactor(13054960701598503119443703458633);
Ø
(1452543524326) (89876554354233785) |
 |
)
Ø Il
faut environ 8 secondes pour factoriser un nombre de 32 chiffres
Ø ifactor(1305496069738169598323412965106420433423895981881);
Ø
(8987655432542335543542337817) (145254352432254325433)
Ø Il faut plus de 30 minutes pour factoriser un nombre de 49 chiffres
Quoique... Il n'est pas interdit de penser que cela est illusoire. D'abord, les algorithmes de factorisation vont probablement être améliorés. Ensuite, rien ne dit que casser le RSA est aussi difficile que de factoriser n. Il existe peut-être un autre moyen d'inverser la clé publique sans passer par la factorisation de n. En particulier, une mauvaise utilisation de la cryptographie RSA (choix d'un exposant e trop petit, mauvaise complétion des blancs,...) la rend particulièrement vulnérable. Enfin, les progrès de la physique vont peut-être sonner le glas de la cryptographie mathématique. Il a été défini, du moins en théorie, un modèle d'ordinateur quantique qui, s'il était réalisé, permettrait de factoriser très rapidement des entiers. Les ordinateurs quantiques n'en sont encore qu'à leurs prémices, et leur record (automne 2001) est la factorisation de 15=3×5!
La cryptographie RSA est unanimement considérée comme un système très sûr. Mais, mal utilisée, elle peut être aussi catastrophique. Supposons par exemple que Jean souhaite envoyer le même message M à 3 correspondants. Ces derniers ont pour clés publiques RSA : (n1,e1); (n2,e2); (n3,e3). Souvent, afin de simplifier les calculs, on choisit l'exposant e le plus petit possible, c'est-à-dire 3 (c'est par exemple l'exposant utilisé dans le système des cartes bleues). Nous supposons donc que e1=e2=e3=3.
Jean envoie à ses 3 correspondants C1=M3 mod n1, C2=M3 mod n2, et C3=M3 mod n3. Si Julie écoute la conversation, elle intercepte les 3 nombres C1, C2 et C3. En utilisant le théorème des restes chinois elle peut trouver très facilement, et très rapidement, un entier C tel que C=M3 mod (n1n2n3). Maintenant, on sait que M<n1, M<n2, M<n3. On a donc M3<n1n2n3. Le calcul de la racine cubique C1/3 n'est plus un calcul de logarithme discret, mais simplement la prise de la racine cubique usuelle (très rapide!). En calculant C1/3, Julie retrouve le message initial M sans le moindre effort!
La parade est très simple pour Jean : il suffit qu'il envoie aux 3 destinataires un message différent, en introduisant aléatoirement des espaces par exemple. Moralité de ce phénomène : un système peut être très sûr quand il est bien utilisé, une erreur pas forcément très visible lors de son utilisation peut conduire à des failles considérables.
Exemple : n1=85,
n2=143, n3=133. Jean veut envoyer M=62. Il transmet :
C1=73=P23 mod 85, C2=90 mod 143, C3=125
mod 133.
Julie connait C1, C2, C3, n1, n2,
n3. Elle en déduit C=238328 mod (n1n2n=1616615).
Maintenant, C1/3=62=M!!
