Im Detail

Riemanns Hypothese und das Internet II


1977 schlugen die Wissenschaftler R. Rivest, A. Shamir und L. Adleman ein Kryptosystem mit öffentlichem Schlüssel namens RSA vor. Dieses System verwendet einige elementare Ideen aus der Zahlentheorie.

Obwohl die verwendeten Ideen elementar sind, bedeutet dies nicht, dass sie trivial sind. In der Tat hat der deutsche Mathematiker Gauß (1777-1855), einer der größten Mathematiker aller Zeiten, den Begriff der Kongruenzen geschaffen und weiterentwickelt, der für die Kodierung und Dekodierung von Schlüsseln im RSA-System von grundlegender Bedeutung ist. Kongruenzen und die daraus resultierende Entwicklung der Modularen Arithmetik tragen wesentlich zur Zahlentheorie bei. Insbesondere die Fragen der Teilbarkeit, denn wenn mit den Überresten der euklidischen Division gearbeitet werden muss, sind Kongruenzen die geeigneten Instrumente.

Gauß führte den Begriff der Kongruenz in das erste Kapitel seines 1801 veröffentlichten Werkes „Disquisitiones Arithmeticae“ ein. Gleichzeitig mit dem Begriff der Kongruenz führte Gauß die Notation „≡“ ein, die den Begriff zu einer mächtigen Technik in der Algebra und der Zahlentheorie machte. Gehen wir zu den Definitionen.

Wir betrachten zwei ganze Zahlen die, b und nein eine positive ganze Zahl. Wenn nein teilen die - b, dann sagen wir das die ist kongruent zu b Modul neinund wir schrieben dieb (mod nein).

Zum Beispiel:

37 ≡ 2 (mod 5), weil 5 37 - 2 = 35 teilt,

27 ≡ 3 (mod 4), weil 4 27 - 3 = 24 teilt,

7 ≡ 7 (mod 4), daher teilt 4 7 - 7 = 0.

Deshalb dieb (mod nein) bedeutet das nein teilen die - b; Es gibt also eine ganze Zahl k so dass die - b = kn durch die Definition der Teilbarkeit. Zum Beispiel impliziert 37 ≡ 2 (mod 5), dass es gibt k (= 7) so dass 37 - 2 = 35 = 7 • 5.

Gegeben die ganzen Zahlen die und neinAus dem Divisionsalgorithmus wissen wir, dass es ganze Zahlen gibt was und r Quotient und Rest, so dass: die = wann + rwo 0 ≤ r < nein; bald die - r = wanndh nein teilen die - r. Daher nach der Definition der Kongruenz dier (mod nein).

Der rest r kann einen beliebigen Wert zwischen 0 und annehmen nein - 1. Daraus schließen wir, dass jede ganze Zahl die ist ein kongruentes Modul nein auf genau einen der Werte zwischen 0, 1, 2,…, nein - 1. Die Menge {0, 1, 2,…, nein - 1} von ganzen Zahlen m Das sind die Überreste der Modulabteilungen neinwird die Modul-Abfallklasse genannt nein. Wenn wir es reparieren nein = 7, also hat Modul 7 genau 7 Elemente, nämlich: 0, 1, 2,…, 6. Unabhängig von der Ganzzahl ist es daher kongruent zu einem einzelnen Element von Modul 7.

Zum Beispiel wird 20 durch 6 in der Restklasse von Mod 7 dargestellt, da 20 ≤ 6 (Mod 7) ist.

Die Idee der Kongruenz ist in unserem täglichen Leben präsent, wenn wir glauben, dass Uhren das Stundenmodul 12 markieren, Wochentage Modul 4 messen, Monate dem Muster von Modul 12. Aufgrund der vielen ähnlichen Eigenschaften zwischen Kongruenz und Gleichheit entschied sich Gauß für das Symbol „≡“ für das passende Signal.

Beachten Sie das diedie (mod nein) und wenn dieb (mod nein) dann bdie(mod nein). Die Additions-, Multiplikations- und Potenzierungsoperationen verhalten sich wie folgt.

Wenn dieb (mod nein) und cd (mod nein) dann:

die + c b + d (mod nein),

die c b d (mod nein),

dierbr (mod nein).

Die im folgenden Beispiel dargestellte Methode ist grundlegend für den Umgang mit der Schlüsselcodierung und -decodierung im RSA-System. Darüber hinaus ist es ein sehr interessantes Beispiel für die Anwendung des Kongruenzbegriffs.

Um den Rest der Teilung von zu bestimmen die von nein Es reicht aus, eine ganze Zahl zu finden r so dass dier (mod nein) wobei 0 r < nein. Zum Beispiel, um den Rest der Division von 3 zu bestimmen10 um 13 machten wir 310 und dann durch 13 teilen, was nicht einfach ist. Der Begriff der Kongruenz erleichtert dieses Verfahren jedoch erheblich. Zunächst stellen wir fest, dass:

33 ≡ 1 (mod 13), das ist einfach!

Wenn wir jetzt alles in den Würfel heben, erhalten wir

(33)3 ≡ (1)3 mod 13 dh 39 ≤ 1 (mod 13).

Wenn wir beide Seiten der Kongruenz mit 3 multiplizieren, erhalten wir 310 ≡ 3 (mod 13).

Die heutigen Computer haben ein so hohes Niveau erreicht, dass jedes Kryptosystem robust genug sein muss, um den Angriffen von Personen standzuhalten, die die Sicherheit ihrer Transaktionen beeinträchtigen möchten.

Die Mathematiker W. Diffie und M. Hellman schlugen 1975 ein völlig neues Verschlüsselungssystem vor: die Kryptographie mit öffentlichen Schlüsseln. Bei dieser Codierungsmethode werden zwei Schlüssel verwendet: einer zum Codieren und einer zum Decodieren. Einige spezifische Methoden wurden entwickelt, um die Ideen von Diffie und Hellmann umzusetzen. Die am häufigsten unterstützte Methode, die standardmäßig verwendet wird, ist das RSA-System.

Um einen Text gemäß dem RSA-System zu kodieren, benötigen Sie:

(1) eine große Anzahl NDas ist das Produkt von zwei verschiedenen Cousins p und wasdh N = p • q.

(2) eine ganze Zahl E, bekannt als Codierschlüssel, der die folgenden Eigenschaften erfüllt: der größte gemeinsame Teiler (MDC) zwischen E und das Produkt (p - 1) (was - 1) ist 1 und der MDC zwischen E und N ist auch 1.

Um einen Text gemäß dem RSA-System zu dekodieren, benötigen Sie:

(3) eine ganze Zahl D, bekannt als Entschlüsselungsschlüssel, der die Bedingung erfüllt:

E • D ≡ 1 (mod (p -1) (was -1)).

Wir haben festgestellt, dass die Beziehung zwischen E und D ist symmetrisch, das heißt, wenn D ist der Entschlüsselungsschlüssel für Edann E ist der Entschlüsselungsschlüssel für D.

Kodieren wir die Nachricht ÖFFENTLICHER SCHLÜSSEL Verwenden des RSA-Systems mit N = 2537 und Verschlüsselungsschlüssel E = 13. Zuerst stellen wir fest, dass N = 43.59 wobei 43 und 59 Primzahlen sind.

Somit ist MDC (13, (43-1) · (59-1)) = MDC (13, 42-58) = 1, da die ganze Zahl 13 weder 42 noch 58 teilt; MDC (13, 2537) = 1, da 13, 43 und 59 (2537 = 43 • 59) Primzahlen sind. Jetzt konvertieren wir den Text unter Verwendung der Buchstaben-Zahlen-Übereinstimmungstabelle:

A = 00, B = 01, C = 02, D = 03, ..., X = 23, Y = 24, Z = 25.

Wie N = 2537 enthält 4 Ziffern, wir wickeln den Text in Buchstabenpaare um:

PU BL IC KE Y

und vervollständige den letzten Block mit dem Buchstaben C bekommen

<>

PU BL IC KE YC<>

.

Unter Verwendung der obigen Konvertierungstabelle sind die 5 konvertierten Nachrichtenblöcke:

1520 0111 0802 1004 2402.

Wir werden B den vierstelligen Block nennen. Der nächste Schritt besteht darin, den Wert jedes der vier Ziffernblöcke zu berechnen, die auf Exponent 13 (Mod. 3127) angehoben wurden. Das heißt, wenn ein Block B gegeben ist, möchten wir C so bestimmen, dass C = P ist13 (Mod 2537).

Wenn wir zum Beispiel den ersten Block codieren, müssen wir C ≡ 1520 lösen13 r (Mod 2537). Dann gehen wir wie folgt vor:

<>

15202 = 2,310,400 = 910 · 2537 + 1730 · 1730 (mod 2537);

<>

15204 = 17302 = 2,992,900 = 1179 · 2537 + 1777 · 1777 (mod 2537);

<>

15208 = 17772 = 3,157,729 = 1244 · 2537 + 1701 · 1701 (mod 2537);

<>

152012 = 15208.• 15204 = 1701 • 1777 = 3.022.677 = 1191 • 2537 + 1110 =

<>

= 1110 (mod 2537);

152013 = 152012 • 1520 = 1110 • 1520 = 1.687.200 = 665 • 2537 + 95 = 95 (Mod 2537).

Somit ist die Codierung von 1520 0095.

Die anderen Nachrichtenblöcke werden auf die gleiche Weise codiert, dh jeder Block besteht aus vier Ziffern, die zur Potenz 13 ansteigen (Mod 2537). Daher erhält der Empfänger die verschlüsselte Nachricht:

0095 1648 1410 1299 0811.

Beachten Sie, dass wir diese Nachricht nicht in Buchstaben konvertieren können, da einige Paare von Ziffern der Blockbestandteile größer als 25 sind. In der nächsten Spalte werden wir die Schritte ausführen, um Nachrichten gemäß dem RSA-System zu decodieren und die Nachricht aus diesem Beispiel zu decodieren.

Zurück zu den Spalten

<


Video: Riemannsche Vermutung: Größtes Problem der Mathematik endlich gelöst?! - Clixoom Science & Fiction (Kann 2021).