Борисенко, la fourrure-obscénités de l'Université de Moscou

À la différence du codage symétrique, à qui la procédure du déchiffrement se rétablit facilement selon la procédure шифрования et à l'inverse, dans le schéma du codage avec la clé ouverte il est impossible de calculer la procédure du déchiffrement, en connaissant la procédure шифрования. Plus exactement, le temps de travail de l'algorithme calculant la procédure du déchiffrement, est tellement grand que l'on ne peut pas l'accomplir sur n'importe quels ordinateurs modernes, de même que sur n'importe quels ordinateurs du futur. Tels schémas du codage appellent asymétrique.

Donc, nous avons deux images :

Où S - la multitude de messages de toute sorte non chiffrés, T - la multitude de messages chiffrés. La lettre "E" - la première lettre du mot "Encoding", la lettre "D" - la première lettre du mot "Decoding". L'image

Traduit le message initial s au message chiffré t, l'image

Traduit le message chiffré t à l'inverse à s. Ce fait que D est la procédure décodant, dans la langue mathématique signifie que la composition des images DE est l'image identique : pour chacun s il est juste

Tout cela est juste pour n'importe quel schéma du codage asymétrique. Nous passerons directement au schéma RSA appelé si selon les premières lettres des noms de ses auteurs - Rumley, Shamir, Adleman. Nous marquerons à la fois que le schéma RSA possède deux propriétés supplémentaires très utiles.

1. La multitude de messages initiaux S coïncide avec la multitude de messages codés T; à titre de cette multitude on utilise l'anneau des déductions selon le module m, où m - l'oeuvre de deux grands nombres premiers (l'inscription décimale m a la longueur pas moins 200).

2. Non seulement DE = 1, mais aussi ED = 1! Ainsi, D et E - deux images mutuellement inverses. Cela permet au propriétaire de la procédure confidentielle du décodage D de l'appliquer pour le codage. À tout cela peuvent décoder ce message, en utilisant la procédure ouverte E, mais seulement le propriétaire de la procédure confidentielle D peut l'envoyer. Un tel schéma "inverse" de l'application de la clé ouverte permet de certifier l'expéditeur du message. Dans les applications pratiques (pour аутентификации de l'expéditeur) le schéma inverse même est plus important, que la ligne droite.

Donc, dans le schéma RSA à titre de la multitude de messages initiaux et chiffrés on utilise l'anneau des déductions Z_m, où

L'oeuvre de deux grands nombres premiers (la longueur l'inscription décimale de chacun des nombres p et q est pas moins 100). Tout message semble en forme de l'élément Z_m. (Chacun собщение est une succession des bits, que l'on peut examiner comme une grande nombre entière. Si la longueur le message plus que la longueur l'inscription binaire m, il se brise aux blocs, et chaque bloc est chiffrée séparément.)

Le nombre m ouvert, cependant la décomposition m sur les multiplicateurs - confidentiel. La décomposition permet de calculer la fonction d'Ejlera (la conséquence 3) :

Il est facile de montrer que la connaissance de la fonction d'Ejlera donne la possibilité de décomposer le nombre en multiplicateurs, de sorte que la complexité de la tâche de l'effraction de la clé ouverte est égale à la complexité de la tâche de la décomposition sur les multiplicateurs. Les mathématiciens croient que cela en effet la tâche complexe, bien que d'aucunes estimations satisfaisantes d'en bas à présent ne soit pas reçu. (Et c'est peu probablement la tâche NP-complète.)

Nous générerons l'élément accidentel e dans l'anneau des déductions selon le module phi (m), un tel qu'il est convertible dans cet anneau (i.e. est mutuellement simple avec phi (m)). Une paire (m, e) est la clé ouverte. L'image E comprend dans la construction au degré e dans l'anneau des déductions selon le module m.

Pour le calcul pratique on applique l'algorithme de la construction rapide au degré.

Pour l'élément e on calcule l'inverse d dans l'anneau des déductions selon le module phi (m).

Cela se fait facilement avec l'aide de l'algorithme élargi d'Evklida. Une paire (m, d) est la clé confidentielle. L'image D comprend dans la construction au degré d dans l'anneau des déductions selon le module m.

Nous montrerons que l'image D est un gauche inverse vers E, i.e. pour chacun ссобщения s on accomplit l'égalité D (E (s)) = s. Nous avons

Donc, DE = 1. Est prouvé Analogiquement qu'ED = 1.

On examine la multitude de messages Z_m, où m - l'oeuvre de deux grands nombres premiers : m = p*q. Le nombre m est ouvert, mais sa décomposition sur les multiplicateurs - confidentiel. La connaissance de la décomposition permet de calculer la fonction d'Ejlera phi (m) = (p-1) * (q-1). Par l'image accidentelle sort l'élément convertible e dans l'anneau des déductions selon le module phi (m). Pour lui est calculé (avec l'aide de l'algorithme élargi d'Evklida) l'inverse d dans l'anneau des déductions selon le module phi (m). L'image E est donnée à une paire (m, e) et comprend dans la construction au degré e selon le module m :

L'image D est donnée à une paire (m, d) et comprend dans la construction au degré d selon le module m :

Ces deux images mutuellement обратны. Une paire (m, e) est la clé ouverte (public key), une paire (m, d) est la clé confidentielle (private key).

L'exemple. Nous examinerons l'exemple avec de petits nombres pour seulement illustrer le schéma RSA. Dans les applications réelles utilisent de grandes nombres entières, de l'ordre de 200-400 chiffres décimaux.

Que m = 11*13 = 143. Nous calculerons la fonction d'Ejlera phi (m) = 10*12 = 120. Nous choisirons e = 113, alors d = 17 - inverse vers e l'élément dans l'anneau Z₁₂₀.

Une paire (143, 113) fait la clé ouverte, la vapeur (143, 17) - la clé confidentielle. L'image E comprend dans la construction au degré 113 selon le module 143, l'image D - au degré 17 selon le module 143. Nous examinerons le message arbitraire s = 123. Alors

Ainsi, 41 est un message codé. Nous lui appliquerons la procédure décodant :

Nous avons reçu le message initial.

En rapport avec le schéma RSA apparaît une série de tâches algorithmiques.

1. Pour la génération des clés nous devons savoir générer de grands nombres premiers. Une proche tâche est le contrôle de la simplicité de la nombre entière.

2. L'effraction de la clé à RSA doit savoir étaler la nombre entière sur les multiplicateurs (ou que pratiquement même, savoir calculer la fonction d'Ejlera). L'effraction de la clé peut intéresser seulement les criminels, mais, d'autre part, ceux qui tentent de protéger l'information, doivent être assurés que la tâche de la décomposition sur les multiplicateurs est assez complexe.