Cryptage RSA. Description et implémentation de l'algorithme RSA

Le cryptage RSA est l’un des premierscryptosystèmes à clé publique pratiques, largement utilisés pour la transmission sécurisée de données. Sa principale différence par rapport aux services similaires est que la clé de chiffrement est publique et différente de la clé de déchiffrement, qui est gardée secrète. En technologie RSA, cette asymétrie repose sur la complexité pratique de la factorisation de la reproduction de deux grands nombres premiers (le problème de la factorisation).

Histoire de la création

Le nom RSA comprend les lettres initiales des noms de famille.Rivest, Shamir et Adleman - les scientifiques qui ont décrit pour la première fois publiquement ces algorithmes de cryptage en 1977. Clifford Cox, un mathématicien anglais qui travaillait pour les services de renseignement britanniques, a développé un système équivalent en 1973, mais celui-ci n'a été déclassifié qu'en 1997.

L'utilisateur RSA crée puis publieclé publique basée sur deux grands nombres premiers avec une valeur auxiliaire. Les nombres premiers doivent rester confidentiels. N'importe qui peut utiliser la clé publique pour chiffrer un message, mais si sa taille est suffisante, seule une personne connaissant les nombres premiers peut décoder le message. La divulgation du cryptage RSA est connue comme le principal problème: il existe aujourd'hui une discussion ouverte sur la fiabilité de ce mécanisme.

RSA est un algorithme relativement lent.pour cette raison, il n'est pas aussi largement utilisé pour chiffrer directement les données utilisateur. Le plus souvent, cette méthode est utilisée pour transmettre des clés partagées sous forme chiffrée pour une clé de chiffrement symétrique, qui peut à son tour effectuer des opérations de chiffrement et de déchiffrement en masse à une vitesse beaucoup plus rapide.

Quand le cryptosystème moderne est-il apparu?

L'idée d'un cryptosystème à clé asymétriqueattribué à Diffie et Hellman, qui ont publié le concept en 1976, présentant les signatures numériques et essayant d'appliquer la théorie des nombres. Leur formulation utilise une clé secrète partagée créée à partir de l'exponentiation d'un certain nombre modulo un nombre premier. Cependant, ils ont laissé ouvert le problème de la mise en œuvre de cette fonction, les principes de l'affacturage n'étant pas encore bien étudiés.

Rivest, Adi Shamir et Adleman dans le MassachusettsL'Institute of Technology a tenté à plusieurs reprises au cours de l'année de créer une fonction unidirectionnelle difficile à décoder. Rivest et Shamir (en tant qu'informaticiens) ont proposé de nombreuses fonctions potentielles, tandis qu'Adleman (en tant que mathématicien) a recherché les «points faibles» de l'algorithme. Ils ont utilisé de nombreuses approches et finalement, en avril 1977, ils ont finalement mis au point un système, connu aujourd'hui sous le nom de RSA.

EDS et clé publique

Signature numérique électronique ou EDS,Il fait partie intégrante des documents de type électronique. Il est formé avec un certain changement de données cryptographiques. En utilisant cet attribut, il est possible de vérifier l’intégrité du document, sa confidentialité, ainsi que de déterminer à qui il appartient. En fait, c'est une alternative à une signature standard ordinaire.

Ce cryptosystème (cryptage RSA) offreLa clé publique est différente de symétrique. Le principe de son fonctionnement est qu’ils utilisent deux clés différentes - privée (cryptée) et également ouverte. Le premier est utilisé pour générer EDS et ensuite pour pouvoir décrypter le texte. La seconde concerne le cryptage et la vérification appropriés des fichiers EDS.

L'utilisation d'une signature vous permet de mieux comprendre le cryptage RSA, un exemple pouvant être cité comme un document régulier et secret "fermé des yeux des autres".

Quelle est l'essence de l'algorithme?

L'algorithme RSA comprend quatre étapes: génération, distribution, chiffrement et déchiffrement de clés. Comme indiqué précédemment, le cryptage RSA inclut la clé publique et la clé privée. Ouvert, accessible à tous, est utilisé pour chiffrer les messages. Son essence est que les messages chiffrés avec une clé publique ne peuvent être déchiffrés qu'à un certain intervalle de temps à l'aide d'une clé secrète.

Pour des raisons de sécurité, les entiers doivent êtrechoisis au hasard et de même ampleur, mais dont la longueur varie de plusieurs chiffres pour rendre l’affacturage plus difficile. Les mêmes numéros peuvent être trouvés efficacement en utilisant le test pour leur simplicité. Le cryptage des informations doit donc nécessairement être compliqué.

La clé publique comprend un module et un exposant public. Closed se compose d'un module et d'un indicateur privé, qui doivent être gardés secrets.

Chiffrement et faiblesses des fichiers RSA

Cependant, il existe un certain nombre de mécanismes de piratage.RSA simple. Lors du cryptage avec des nombres faibles et petits nombres, le chiffre peut être facilement révélé si vous sélectionnez la racine du texte crypté au-dessus des entiers.

Depuis le cryptage RSA estPar un algorithme déterministe (c’est-à-dire qu’il n’a pas de composant aléatoire), un attaquant peut réussir à lancer une attaque par un texte ouvert contre un cryptosystème en chiffrant les textes susceptibles d’être ouverts sous une clé publique et en vérifiant s’ils correspondent à un texte chiffré. Un cryptosystème est appelé sémantiquement sécurisé dans le cas où un attaquant ne pourrait pas distinguer deux chiffrements l'un de l'autre, même s'il connaissait les textes correspondants dans la forme développée. Comme décrit ci-dessus, RSA sans complément d'autres services n'est pas sémantiquement sécurisé.

Cryptage supplémentaire et algorithmes de sécurité

Pour éviter les problèmes ci-dessus, quandLa mise en œuvre pratique de RSA est généralement intégrée à une forme de remplissage structuré et aléatoire avant le cryptage. Cela garantit que le contenu ne tombe pas dans la plage de texte en clair non sécurisé et que le message ne peut pas être divulgué par sélection aléatoire.

RSA cryptosystème sécurité et cryptageLes informations sont basées sur deux problèmes mathématiques: les problèmes de factorisation de grands nombres et le problème actuel de RSA. La divulgation complète du texte chiffré et de la signature électronique dans RSA est considérée comme inacceptable, dans l'hypothèse où ces deux problèmes ne peuvent être résolus dans leur ensemble.

Cependant, en raison de la possibilité de récupérationDans les facteurs premiers, l’attaquant peut calculer l’index secret à partir de la clé publique, puis déchiffrer le texte à l’aide d’une procédure standard. Bien qu’aujourd’hui aucune méthode de factorisation de grands nombres sur un ordinateur classique n’ait été trouvée, il n’a pas été prouvé que cela n’existait pas.

Automation

Un outil appelé Yafu peut êtreutilisé pour optimiser ce processus. L'automatisation dans YAFU est une fonctionnalité moderne qui combine des algorithmes de factorisation dans une méthodologie intelligente et adaptative qui minimise le temps nécessaire à la recherche de facteurs pour des nombres d'entrée arbitraires. La plupart des implémentations de l'algorithme sont multithreads, ce qui permet à Yafu d'utiliser pleinement les processeurs multicœurs ou multicœurs (y compris SNFS, SIQS et ECM). Tout d’abord, c’est un outil de ligne de commande géré. Le temps passé à rechercher le facteur de cryptage à l'aide de Yafu sur un ordinateur ordinaire peut être réduit à 103,1746 secondes. L'outil traite des fichiers binaires d'une capacité de 320 bits ou plus. C'est un logiciel très complexe qui nécessite une certaine quantité de compétences techniques pour l'installation et la configuration. Ainsi, le cryptage RSA-C peut être vulnérable.

Les tentatives de piratage dans les temps modernes

En 2009, Benjamin Moody utilisant peuLa clé RSA-512 a fonctionné pendant 73 jours pour déchiffrer le cryptotexte en utilisant uniquement le logiciel bien connu (GGNFS) et l'ordinateur de bureau moyen (Athlon 64 double cœur à 1900 MHz). Comme cette expérience l'a montré, il fallait un peu moins de 5 Go de disque et environ 2,5 Go de RAM pour le processus de «filtrage».

En 2010, le plus grand nombre factorisé de RSA avait une longueur de 768 bits (232 chiffres décimaux ou RSA-768). Sa divulgation a duré deux ans sur plusieurs centaines d'ordinateurs simultanément.

En pratique, les clés RSA sont longues -typiquement 1024 à 4096 bits. Certains experts estiment que les clés 1024 bits pourraient devenir peu fiables dans un proche avenir ou même être piratées par un attaquant assez bien financé. Cependant, peu de gens diront que des clés de 4096 bits peuvent également être divulguées dans un avenir prévisible.

Perspectives

Par conséquent, il est généralement admis que RSAest sûr si les nombres sont assez grands. Si le numéro principal est égal ou inférieur à 300 bits, le texte chiffré et le fichier EDS peuvent être décomposés en quelques heures sur un ordinateur personnel à l'aide d'un logiciel déjà disponible dans le domaine public. Comme il a été prouvé, des clés d’une longueur de 512 bits auraient déjà pu être ouvertes en 1999 avec plusieurs centaines d’ordinateurs. De nos jours, cela est possible en quelques semaines avec du matériel disponible au public. Il est donc possible qu'à l'avenir le chiffrement RSA sur les doigts soit facilement révélé et que le système devienne désespérément obsolète.

Officiellement, en 2003, la sécurité des clés 1024 bits a été mise en cause. Actuellement, il est recommandé d'avoir une longueur d'au moins 2048 bits.