Divers

Comment l'algorithme de Peter Shor met en échec le chiffrement RSA

Comment l'algorithme de Peter Shor met en échec le chiffrement RSA

Il s'agit du quatrième article d'une série en sept parties sur les algorithmes et le calcul, qui explore comment nous utilisons des nombres binaires simples pour alimenter notre monde. Le premier article, Comment les algorithmes gèrent le monde dans lequel nous vivons, peut être trouvé ici.

Quelques années avant que Sergei Brin et Larry Page n'intègrent pour la première fois leur moteur de recherche Google dans l'entreprise qui a contribué à développer Internet tel que nous le connaissons, Peter Shor a publié un article sur l'algorithme destiné à briser tous les verrous sur les connexions censés assurer la sécurité de l'ensemble.

Peter Shor n’était pas un anarcho-hacktiviste malveillant mais un mathématicien travaillant pour Laboratoires Bell d'AT & T cherche à résoudre un problème mathématique difficile comme tout autre mathématicien dans le domaine. Son algorithme, connu sous le nom de Algorithme de Shor, exigeait une technologie qui existait à peine en théorie, encore moins la réalité, lorsqu'il l'a décrite pour la première fois en 1994.

CONNEXES: QU'EST-CE QUE L'INFORMATIQUE QUANTUM CHANGERA EXACTEMENT?

Il n'y avait aucune raison de penser à la fin des années 1990 et au début des années 2000 que nous aurions jamais à nous inquiéter de l'insécurité des Cryptage RSA, mais maintenant nous connaissons la vérité: Cryptage RSA est voué à l'échec. Maintenant, l'improbable technologie utilisée par Shor, l'informatique quantique, ne progresse pas seulement à un rythme similaire à la loi de Moore - ce qui signifie que dans une décennie ou deux, les ordinateurs quantiques seront suffisamment puissants pour fonctionner Algorithme de Shor et le buste ouvert Cryptage RSAAlgorithme de Shor lui-même a contribué à inspirer le développement de l'informatique quantique en premier lieu.

Le chiffrement RSA était autrefois considéré comme incassable

Cryptage RSA, qui est utilisé pour crypter tout, des fichiers sur nos disques durs au trafic Internet confidentiel, est construit sur les principes de échange de clé publique et le problème de calcul difficile de factorisation prime.

Pour un ordinateur classique, un algorithme efficace pour trouver le facteurs premiers d'un nombre composé n'existe pas, ce qui signifie que le mieux que nous puissions faire est de trouver une réponse un peu moins horrible que temps exponentiel. Cryptage RSA est généralement qualifié avec une longueur en bits, telle que 128 bits, 256 bits, etc., qui représente la longueur en bits de la clé utilisée pour crypter et décrypter les données. Donc, un algorithme de force brute avec complexité temporelle exponentielle travailler sur un Clé de cryptage 128 bits aurait besoin d'essayer 2128 valeurs au minimum.

C'est égal à 340,282,366,920,938,463,463,374,607,431,768,211,456 les clés possibles et les clés de chiffrement RSA n'ont pas été aussi petites que 128 bits en plus d'une décennie. La longueur de clé standard actuellement recommandée pour une clé de chiffrement RSA est 2048 bits, qui est égal à (340,282,366,920,938,463,463,374,607,431,768,211,456)16 clés possibles.

Ces nombres nous sont insondables, mais il existe un moyen de gérer et même d’effectuer des opérations à l’aide de ces nombres, ce que l’on appelle l’arithmétique modulaire et ce sont ces opérations qui sont au cœur de l’algorithme de chiffrement RSA.

Dans de nombreux pays qui utilisent un Horloge 12 heures Plutôt qu'un Horloge de 24 heures pour garder le temps, ils utilisent l'arithmétique modulaire tout le temps, littéralement. Si c'est 11 h 00 et je vous demande de me rencontrer quatre heures, tu sais que je veux me rencontrer à 15 h 00. C'est parce que nous utilisons le nombre 12, appelé le module, pour savoir quand recommencer à compter à partir de zéro. L'arithmétique modulaire utilise ce même processus, uniquement avec des nombres de taille énorme pour aider à effectuer des calculs.

Comme tout autre système d'échange de clés, Cryptage RSA utilise un Clé publique et un Clé privée pour crypter et décrypter des données, sauf Cryptage RSA utilise deux nombres comme clé publique, un exposant public à utiliser pour crypter un message et un module pour l'opération de chiffrement qui produit le chiffrement. Qu'est-ce qui fait que module si important est le fait qu'il soit le produit de deux très grands nombres premiers et connaître ceux deux nombres vous permettra de faire de l'ingénierie inverse Clé privée qui déverrouille le cryptage.

La difficulté inhérente à Cryptage RSA cependant est double: l'énormité des nombres impliqués signifie que vous ne pouvez pas forcer brutalement votre chemin vers le Clé privée et le fait que factorisation prime de ce nombre incroyablement grand est quelque chose de non ordinateur classique peut espérer faire dans trillions d'années.

Comment les ordinateurs quantiques et l'algorithme de Shor défont le chiffrement RSA

Sans s'embourber dans les détails finis, Algorithme de Shor est une réponse en trois parties au problème de factorisation prime pour tout entier, donc cela fonctionne quelle que soit la taille de l'entier impliqué. le première partie est effectuée sur un ordinateur classique dans Temps polynomial, mais ce n'est que la mise en place pour le deuxième et plus important partie. le deuxième partie nécessite l'utilisation de circuits quantiques pour effectuer le calcul quantique nécessaire pour trouver le valeur vous avez besoin pour le troisième partie, qui vous permet de trouver le facteurs premiers de l'entier sur un ordinateur classique.

La première partie de l'algorithme transforme le problème de factorisation prime dans un équivalent problème qui peut être résolu, à savoir, trouver le période d'un fonctionnement modulaire. Si vous pouvez trouver le période de cette fonction en utilisant comme entier que vous voulez factoriser comme un module, vous pouvez trouver les facteurs premiers assez rapidement sur un ordinateur classique avec quelques calculs supplémentaires.

Le problème est que, comme factorisation prime, trouver le période de cette opération modulaire n’est pas quelque chose ordinateur classique peut faire dans Temps polynomial, mais Shor montré dans le deuxième partie de l'algorithme qui utilisant un ordinateur quantique théorique tu pourrais calculer ça période et, plus important encore, il a pu prouver mathématiquement que cette partie du algorithme quantique couru Temps polynomial. Après avoir trouvé le période, une ordinateur classique pourrait l'utiliser pour trouver le facteurs premiers de tout entier.

Comment l'algorithme de Peter Shor et Shor a lancé le calcul quantique

Peter Shor a montré qu'une théorie ordinateur quantique pourrait résoudre un problème mathématique insoluble d'une manière ordinateur classique jamais ne pourrait en contournant la nécessité de calculer des valeurs uniques à la fois. Ordinateurs quantiques peut effectuer des opérations sur qubits dans superposition et réduisent littéralement la complexité temporelle d'un problème de manière exponentielle.

Quand Shor a conçu son algorithme, l'informatique quantique n'existait pas de manière significative. L'idée existait depuis un certain temps, mais il était entièrement théorique, impossible même d'essayer de construire, et personne ne pouvait voir l'utilité d'essayer d'en construire un car il n'y avait aucun exemple de quoi que ce soit un ordinateur quantique pourrait faire ça ordinateur classique ne pouvait pas.

En montrant comment un ordinateur quantique pourrait en fait être utile d'une manière qui ordinateurs classiques ne pouvait pas en résolvant un problème classiquement insoluble Temps polynomial, Peter Shora suscité l'intérêt de chercheurs du monde entier qui ont commencé leur propre recherche sur l'informatique quantique et maintenant, des ordinateurs quantiques fonctionnels sont en cours de construction. Il faudra au moins une décennie avant qu'un ordinateur quantique n'ait suffisamment de qubits pour casser Cryptage RSA, mais sa fin est certaine et les cryptographes ont déjà ouvert de nouvelles voies de recherche sur la cryptographie post-quantique pour s'assurer que tout ce qui doit rester sécurisé le fait.

Après Peter Shor algorithme a prouvé que des problèmes difficiles pour ordinateurs classiques pourraient être résolus, d'autres ont commencé à examiner d'autres problèmes difficiles qui pourraient également être résolus par les ordinateurs quantiques, et pour une bonne raison; parmi les nombreux problèmes qui restent à résoudre, l'avantage potentiel de les résoudre est aussi énorme que les problèmes eux-mêmes.

Le cinquième article de notre série sur les algorithmes et le calcul, Algorithmes, optimisation et problème du voyageur de commerce, peut être trouvé ici.


Voir la vidéo: Cryptoggrahie: chiffrement à clé asymétriqueRSA (Novembre 2021).