Le RSA vient-il d’être détruit par un mathématicien allemand à la retraite? –

Une grande partie du monde numérique repose sur le cryptage RSA pour la confidentialité et la sécurité. Un article mathématique récent qui «détruit le cryptosystème RSA» a donné des palpitations aux cryptographes. Ont-ils raison de s’inquiéter?

Qu’est-ce que le cryptage RSA?

Le cryptosystème Rivest-Shamir-Adleman (RSA) a résolu le problème de la manière de crypter les données afin qu’elles ne puissent être décryptées que par le destinataire prévu. En 1977, les co-créateurs – Ron Rivest, Adi Shamir et Leonard Adleman – ont proposé une solution élégante basée sur une nouvelle façon d’utiliser les clés de chiffrement. En termes simples, les clés de chiffrement sont de très grandes valeurs utilisées dans les processus mathématiques appliqués aux données pour les chiffrer. La percée que RSA a apportée au monde de la cryptographie a été l’utilisation de privé et Publique clés.

Nous devrions également mentionner Clifford Cocks, le mathématicien en chef du Government Communication Headquarters (GCHQ) du Royaume-Uni qui a appliqué le cryptage / décryptage à clé publique et privée à la cryptographie en 1973. Les informations ont été classifiées et sont restées secrètes. Il n’a été déclassifié qu’en 1997. De toute évidence, les grands esprits se ressemblent.

La séquence de clé publique / clé privée consiste à obtenir la clé publique du destinataire prévu et à l’utiliser dans le processus de chiffrement avec votre clé privée. Le destinataire peut alors décrypter les données à l’aide de sa clé privée et de votre clé publique. Les clés publiques peuvent être rendues publiques en toute sécurité et les clés privées sont conservées en toute sécurité. Et comme le destinataire n’a pas besoin d’être un humain, tout système, service ou appareil qui fait connaître sa clé publique de manière certifiée et authentifiée peut utiliser le cryptage RSA. Cela permet de chiffrer les communications de système à système.

Un certificat de clé publique est utilisé pour certifier l’identité du propriétaire de la clé publique. Deux exemples courants de certificats de clé publique sont les certificats Secure Socket Layer et Transport Layer (SSL / TLS). Les clés publiques peuvent être transmises entre des personnes souhaitant communiquer, ou elles peuvent être récupérées à partir de serveurs de clés tels que le serveur de clés OpenPGP.

Secure Shell (SSH), OpenPGP, S / MIME et SSL / TSL utilisent tous le cryptage RSA, et tous les navigateurs l’utilisent. Certaines crypto-monnaies l’utilisent. Pratiquement tout le monde du e-commerce dépend du RSA d’une manière ou d’une autre. Tout ce qui menace l’intégrité du cryptosystème RSA doit être examiné attentivement.

Menaces contre la cryptographie RSA

Un élément central des algorithmes de chiffrement est irréversibilité. Les transformations mathématiques effectuées sur les données doivent être irréversibles à toutes fins pratiques.

Le schéma RSA utilise de très grands nombres qui sont le produit de la multiplication de deux grands nombres premiers ensemble. Prendre deux nombres premiers et les multiplier ensemble est trivial et bon marché en informatique. Il ne faut pas beaucoup de puissance de traitement ni de temps pour effectuer cette action. Mais recevoir le produit résultant et sans aucune connaissance préalable essayer de déterminer – via l’affacturage – quels deux nombres premiers ont été utilisés est coût de calcul.

L’affacturage devient beaucoup plus difficile très rapidement à mesure que les chiffres augmentent. Il faudrait un temps si prohibitif – certaines estimations atteignent des milliers de milliards d’années – pour déchiffrer ce type de cryptage. Cela fournit une pseudo-irréversibilité sûre. Ce n’est pas vraiment irréversible, mais cela prendrait tellement de temps que cela pourrait tout aussi bien être véritablement irréversible.

L’avènement de l’informatique quantique menace ce type de cryptage. Les ordinateurs quantiques sont prometteurs de pouvoir effectuer la factorisation entière requise pour déterminer les deux nombres premiers en un temps extrêmement court. Il est prédit qu’un ordinateur quantique exécutant un dérivé de l’algorithme de Shor serait capable de trouver les nombres premiers dans des périodes de temps suffisamment courtes, peut-être même en quelques heures.

Il faudra attendre 25 ans ou plus avant qu’un ordinateur quantique capable de faire cela n’existe. Cela peut convenir à certaines informations qui sont chiffrées maintenant – l’utilité de ces informations a peut-être expiré à ce moment-là. Mais une partie de ce qui est crypté actuellement devra encore être protégée et privée dans 25 (voire plus) ans. Par exemple, certaines communications gouvernementales et de sécurité resteront sensibles même à ce moment-là.

Des erreurs dans la mise en œuvre du RSA ont causé des problèmes dans le passé. Le RSA théorique doit être transformé en une implémentation logicielle fonctionnelle avant de pouvoir être utile – et les logiciels complexes contiendront souvent des bogues. Il y a eu des ajustements et des remplacements aux algorithmes utilisés dans le cryptosystème RSA car des failles ont été trouvées dans les implémentations. Les anciennes versions sont devenues obsolètes et remplacées par de nouvelles versions.

Il y a eu des allégations selon lesquelles des portes dérobées ont été introduites dans les algorithmes RSA en raison de la coercition ou de la coopération avec les agences de sécurité nationale. Ces accusations n’ont jamais été prouvées, mais des failles qui offraient effectivement des portes dérobées ont été trouvées et corrigées par la suite.

Quelle est la nouvelle menace?

Le professeur Claus Peter Schnorr est un mathématicien et cryptographe à la retraite. Il était professeur au Département de mathématiques et d’informatique de l’Université Johann Wolfgang Goethe de Francfort-sur-le-Main.

Une pré-impression d’un article de Schnorr (pré-impression signifie qu’il est en développement tardif mais pas encore revu par les pairs) propose une nouvelle méthode de factorisation des entiers premiers sur les plates-formes informatiques d’aujourd’hui à un rythme considérablement accéléré. L’article s’intitule «Fast Factoring Integers by SVP Algorithms». SVP représente le problème vectoriel le plus court. L’abstrait se termine par la phrase provocante «Cela détruit le cryptosystème RSA».

En condensant un travail très compliqué en une simple déclaration, ce que cela propose est une amélioration d’un ordre de grandeur de la vitesse d’affacturage. Le gain de vitesse serait obtenu en utilisant un raffinement de certains des travaux antérieurs de Schnorr. De toute évidence, une réduction révolutionnaire de la factorisation des entiers aurait un impact significatif sur le cryptosystème RSA. Autrement dit, si le document théorique est factuellement correct et si une mise en œuvre pratique peut confirmer l’hypothèse.

L’article fait la promotion d’une méthode de factorisation utilisant des structures mathématiques appelées treillis. Le professeur Schnorr est un expert largement reconnu dans ce domaine et son application à la cryptographie. Le document affirme que la nouvelle technique est considérablement plus rapide que l’algorithme GNFS (General Number Field Sieve), qui est considéré comme la technique actuelle la plus rapide pour factoriser de grands nombres.

Une analyse de la menace

L’article de Schorr est de nature théorique. Il n’y a pas de minutage ou de résultats des implémentations. Les gains de vitesse théoriques par rapport au GNFS semblent impressionnants sur papier, mais la théorie et les mathématiques résistent-elles à l’examen minutieux de ceux qui comprennent réellement cela au niveau requis pour les commenter de manière significative?

Le Dr Léo Ducas est chercheur dans le groupe de cryptographie du Centrum Wiskunde & Informatica (CWI). Le CWI est l’institut national de recherche en mathématiques et en informatique aux Pays-Bas. Ducas a terminé son doctorat. en 2013 sur «Signatures basées sur treillis: attaques, analyse et optimisation». Il a travaillé avec des treillis tout au long de sa carrière. Il est également cryptographe, il est donc parfaitement capable de réviser l’article de Schnorr.

Mieux encore pour nos besoins, le Dr Léo Ducas est un programmeur. Si vous avez envie d’un tour chez Cryptris, son jeu de cryptographie asymétrique, allez-y. Son code source académique est dispersé sur GitHub. Une partie se trouve dans son propre référentiel, tandis que beaucoup plus se trouvent dans les référentiels d’autres projets multi-auteurs sur lesquels il a travaillé.

Il a effectué une revue et une analyse de l’article de Schnorr. Il a également créé une implémentation des algorithmes de Schnorr en tant que script SageMath. Il l’a nommé SchnorrGate. Ducas signale également une discussion sur la cryptographie StackExchange. Ceci examine une erreur dans l’une des formules du papier qui, si elle est utilisée comme imprimée, produit des résultats très imprécis. Avec cette formule corrigée, la méthode d’affacturage de Schnorr fonctionne, mais à un rythme beaucoup plus lent qu’il ne le prédit.

Les découvertes de Ducas à partir de ses tests SageMath le corroborent. Ils illustrent que les algorithmes d’affacturage de Schnorr fonctionnent, mais beaucoup plus lentement que les meilleures méthodes déjà disponibles aujourd’hui.

Nous pouvons tous respirer à nouveau

Le RSA vit pour crypter un autre jour. Mais que se serait-il passé si les affirmations du journal s’étaient révélées vraies? Eh bien, le chaos, dans un premier temps, puis l’adoption d’un nouveau cryptosystème.

Peut-être que l’ère de la cryptographie à courbe elliptique (ECC) serait arrivée.