Борисенко, den Pelz-Matt der Staatlichen Universität Moskau

Im Unterschied zur symmetrischen Kodierung, bei der die Prozedur des Entzifferns nach der Prozedur der Chiffrierung und zurück leicht wieder hergestellt wird, im Schema der Kodierung mit dem offenen Schlüssel ist es unmöglich, die Prozedur des Entzifferns auszurechnen, die Prozedur der Chiffrierung wissend. Genauer, die Arbeitszeit des Algorithmus, der die Prozedur des Entzifferns ausrechnet, ist so groß, dass man es auf beliebigen modernen Computern, so wie auch auf beliebigen Computern der Zukunft nicht erfüllen darf. Solche Schemen der Kodierung nennen asymmetrisch.

Also, wir haben zwei Abbildungen:

Wo S - eine Menge allerlei nicht chiffrierter Mitteilungen, T - eine Menge der chiffrierten Mitteilungen. Der Buchstabe "E" - der erste Buchstabe des Wortes "Encoding", der Buchstabe "D" - der erste Buchstabe des Wortes "Decoding". Die Abbildung

Übersetzt die Ausgangsmitteilung s in die chiffrierte Mitteilung t, die Abbildung

Übersetzt die chiffrierte Mitteilung t zurück in s. Die Tatsache, dass D eine dekodierende Prozedur ist, auf der mathematischen Sprache bedeutet, dass die Komposition der Abbildungen DE eine identische Abbildung ist: für jeden s ist gerecht

Das alles ist für ein beliebiges Schema der asymmetrischen Kodierung gerecht. Wir werden unmittelbar zum Schema RSA, die so nach den ersten Buchstaben der Familiennamen ihrer Autoren genannt sind - Rumley, Shamir, Adleman übergehen. Wir werden sofort bemerken, dass das Schema RSA über zwei zusätzliche sehr nützlichen Eigenschaften verfügt.

1. Eine Menge der Ausgangsmitteilungen S stimmt mit einer Menge der verschlüsselten Mitteilungen T überein; als diese Menge wird der Ring der Abzüge nach dem Modul m, wo m - das Werk zwei großer einfachen Zahlen (verwendet die Dezimalaufzeichnung hat m die Länge nicht weniger 200).

2. Nicht nur DE = 1, sondern auch ED = 1! So D und E - zwei Gegenseitig rück- Abbildungen. Es lässt dem Besitzer der geheimen Prozedur der Dekodierung D zu, sie für die Kodierung zu verwenden. Dabei können alle раскодировать diese Mitteilung, die offene Prozedur E verwendend, aber nur kann der Besitzer der geheimen Prozedur D es schicken. Solches "Rückschema" der Anwendung des offenen Schlüssels lässt zu, des Absenders der Mitteilung zu beglauben. In den praktischen Anwendungen (für аутентификации des Absenders) ist das Rückschema sogar wichtiger, als die Gerade.

Also, im Schema RSA als eine Menge der Ausgangs- und chiffrierten Mitteilungen wird der Ring der Abzüge Z_m, wo verwendet

Das Werk zwei großer einfachen Zahlen (die Länge der Dezimalaufzeichnung jedes der Zahlen p und q ist es 100 nicht weniger). Jede Mitteilung wird in Form vom Element Z_m vorgestellt. (Jedes собщение ist eine Reihenfolge der Bits, die man wie die große ganze Zahl betrachten kann. Wenn es die Länge der Mitteilung, als die Länge der binären Aufzeichnung m mehr ist, so stürzt es auf die Blöcke ab, und wird jeder Block abgesondert chiffriert.)

Die Zahl m geöffnet, jedoch die Zerlegung m auf dem Faktor - geheim. Die Zerlegung lässt zu, die Funktion Ejlera (die Untersuchung 3 auszurechnen):

Leicht zu zeigen, dass das Wissen der Funktion Ejlera ermöglicht, die Zahl auf dem Faktor auszulegen, so dass die Komplexität der Aufgabe des Aufbruches des offenen Schlüssels der Komplexität der Aufgabe der Zerlegung auf dem Faktor gleich ist. Die Mathematiker glauben, dass es die wirklich komplizierte Aufgabe ist, obwohl es keiner befriedigenden Einschätzungen unten zur Zeit bekommen ist. (Und es ist die NP-volle Aufgabe kaum.)

Wir werden das Zufallselement e im Ring der Abzüge nach dem Modul phi (m), solchen erzeugen, dass er in diesem Ring (d.h. ist mit phi (m gegenseitig einfach) umkehrbar ist). Ein Paar (m, e) ist ein offener Schlüssel. Die Abbildung E besteht in der Errichtung in die Stufe e im Ring der Abzüge nach dem Modul m.

Für die praktische Berechnung wird der Algorithmus der schnellen Errichtung in die Stufe verwendet.

Für das Element e wird das Rückelement d im Ring der Abzüge nach dem Modul phi (m) ausgerechnet.

Es wird mit Hilfe des ausgedehnten Algorithmus Jewklida leicht. Ein Paar (m, d) ist ein geheimer Schlüssel. Die Abbildung D besteht in der Errichtung in die Stufe d im Ring der Abzüge nach dem Modul m.

Wir werden zeigen, dass die Abbildung D link rückgängig zu E ist, d.h. für jeden ссобщения s wird die Gleichheit D (E (s)) = s erfüllt. Wir haben

Also, DE = 1. Es ist ähnlich wird bewiesen, dass ED = 1.

Es wird eine Menge der Mitteilungen Z_m, wo m - das Werk zwei großer einfachen Zahlen betrachtet: m = p*q. Die Zahl m ist geöffnet, aber seine Zerlegung auf dem Faktor - geheim. Das Wissen der Zerlegung lässt zu, die Funktion Ejlera phi (m) = (p-1) * (q-1) auszurechnen. In der zufälligen Weise kommt das umkehrbare Element e im Ring der Abzüge nach dem Modul phi (m heraus). Für ihn wird (mit Hilfe des ausgedehnten Algorithmus Jewklida) das Rückelement d im Ring der Abzüge nach dem Modul phi (m) ausgerechnet. Die Abbildung E protzt mit einem Paar (m, e) und besteht in der Errichtung in die Stufe e nach dem Modul m:

Die Abbildung D protzt mit einem Paar (m, d) und besteht in der Errichtung in die Stufe d nach dem Modul m:

Diese zwei Abbildungen gegenseitig обратны. Ein Paar (m, e) ist ein offener Schlüssel (public key), ein Paar (m, d) ist ein geheimer Schlüssel (private key).

Das Beispiel. Wir betrachten Beispiel mit den kleinen Zahlen, um das Schema RSA nur zu exemplifizieren. In den realen Anlagen verwenden die großen ganzen Zahlen, etwa 200-400 Dezimalzahlen.

Wenn auch m = 11*13 = 143. Wir werden die Funktion Ejlera phi (m) = 10*12 = 120 ausrechnen. Wir werden e = 113, dann d = 17 - rückgängig zu e das Element im Ring Z₁₂₀ wählen.

Ein Paar (143, 113) bildet den offenen Schlüssel, ein Paar (143, 17) - der geheime Schlüssel. Die Abbildung E besteht in der Errichtung in die Stufe 113 nach dem Modul 143, die Abbildung D - in die Stufe 17 nach dem Modul 143. Wir betrachten eine willkürliche Mitteilung s = 123. Dann

So ist 41 eine verschlüsselte Mitteilung. Wir werden zu ihm die dekodierende Prozedur verwenden:

Wir haben die Ausgangsmitteilung bekommen.

In Zusammenhang mit dem Schema RSA entsteht die Reihe der algorithmischen Aufgaben.

1. Für die Erzeugung der Schlüssel müssen wir verstehen, die großen einfachen Zahlen zu generieren. Eine nahe Aufgabe ist die Prüfung der Einfachheit der ganzen Zahl.

2. Für den Aufbruch des Schlüssels in RSA muss man verstehen, die ganze Zahl auf dem Faktor auszulegen (oder, dass tatsächlich selb, zu verstehen, die Funktion Ejlera auszurechnen). Der Einbruch des Schlüssels kann nur die Verbrecher interessieren, aber andererseits sollen, wer versuchen, die Informationen zu schützen, überzeugt sein, dass die Aufgabe der Zerlegung auf dem Faktor genug kompliziert ist.