Kommentare

Riemanns Hypothese und das Internet III


Der deutsche Mathematiker C. F. Gauss führte den Begriff der Kongruenz in das erste Kapitel seiner 1801 veröffentlichten Arbeit „Disquisitiones Arithmeticae“ ein. Dieses Konzept ist für die Codierung und Decodierung von Schlüsseln im RSA-System von grundlegender Bedeutung. Das als RSA bezeichnete Kryptosystem mit öffentlichem Schlüssel wurde von den Wissenschaftlern R. Rivest, A. Shamir und L. Adleman entwickelt.

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

(1) eine große Anzahl NDas ist das Produkt von zwei verschiedenen Primzahlen p und wasdh N = p۰was.

(2) eine ganze Zahl E, bekannt als Codierschlüssel, der die folgenden Eigenschaften erfüllt:

der maximale gemeinsame Teiler (MDC) zwischen E und das Produkt (p - 1)۰(was -1) ist 1 und der MDC

dazwischen 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)).

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.

In der vorherigen Spalte haben wir die Nachricht codiert ÖFFENTLICHER SCHLÜSSEL Verwenden des RSA-Systems mit

N = 2.537 = 43•59, p = 43, was = 59 und mit dem Verschlüsselungsschlüssel E = 13.

Erstens haben wir das beobachtet N = 2.537 besteht aus 4 Ziffern und wir teilen den Text in Buchstabenpaare auf: PU BL IC KE Y und vervollständige den letzten Block mit dem Buchstaben C und erhalte: PU BL IC KE YC.

Unter Verwendung der Konvertierungstabelle, die natürliche Zahlen mit Buchstaben des Alphabets verknüpft, lauten die konvertierten Blöcke der Nachricht wie folgt: 1520 0111 0802 1004 2402. Auf diese Weise erhält der Empfänger die verschlüsselte Nachricht: 0095 1648 1410 1299 0811.

Unser Ziel ist es, die notwendigen Schritte zu unternehmen, um diese Nachricht gemäß dem RSA-Kryptosystem zu decodieren. Zum Entschlüsseln dieser Nachricht benötigen wir den öffentlichen Schlüssel D der Dekodierung.

Gibt es eine Methode zur Bestimmung Dwenn E, p und was bekannt sind. Wenn jedoch p und was sind nicht bekannt, D kann nicht bestimmt werden. Die Sicherheit des RSA-Kryptosystems liegt in dieser Tatsache.

Wenn p und was sind extrem groß, zum Beispiel größer als 10200Bestimmen Sie dann diese Primzahlen in einer angemessenen Zeit, die dem Factoring entspricht N = p۰was,kann über die Kapazität der schnellsten Supercomputer sein.

Unser Ziel ist es zu bestimmen Dso dass E۰D ≡ 1 (mod (p - 1)۰(was - 1)) mit anderen Worten D ist das Gegenteil von E Modul (p - 1)۰(was - 1).

Die Methode besteht darin, den auf den Schlüssel angewendeten Euclid-Algorithmus zu verwenden E Kodierung und Nummer (p - 1)۰(was - 1). Wie E und (p - 1)۰(was - 1) stehen in einer Primzahl zueinander, der MDC unter ihnen ist 1. Zunächst werden alle Schritte des Euklid-Algorithmus durchlaufen, um den MDC zu bestimmen, der in diesem Fall 1 ist.

Nach dem euklidischen Algorithmus müssen wir

(p - 1)۰(was - 1) = was1۰E+ r2, 0 ≤ r2< E.

Woher wissen wir, dass MDC ((p - 1)۰(was - 1), E) = 1, setzen wir die Anwendung des euklidischen Algorithmus fort, bis der Rest der Division gleich 1 ist. Daher führen wir die Division von durch E von r2 und so weiter bis wir den Rest von 1 bekommen:

E = was2۰ r2 + r3, 0 ≤ r3< r2

r2 = was3۰ r3+ r4,0 ≤ r4< r3

rn-4 = wasn-3۰ rn-3 + rn-2,0 ≤ rn-2 < rn-3

rn-3 = wasn-2۰ rn-2 + rn-1,0 ≤ rn-1 < rn-2

rn-2 = wasn-1۰ rn-1 + 1,0 ≤ 1< rn-1.

Mit dem umgekehrten euklidischen Algorithmus können wir nun rechnen D so dass

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

Deshalb D Es ist der Entschlüsselungsschlüssel.

Beachten Sie, dass:

<>

1 = rn-2 - wasn-1۰<>

r<>

n-1<>

(1)

<>

r<>

n-1<>

= rn-3 - wasn-2۰<>

r<>

n-2<>

(2)

<>

r<>

n-2 <>

= rn-4 - wasn-3۰<>

r<>

n-3<>

(3)

r4 = r2-was3۰ r3 (nein - 3)

r3= E - was2۰ r2, (nein - 2)

r2 = (p - 1)۰(was - 1) - was1E (nein - 1)

Überschreiben des Werts von rn-1 von (2) bis (1) bekommen wir

1 = (1 + wasn-1۰wasn-2rn-2 - wasn-1۰rn-3

und Ersetzen in dieser Gleichheit den Wert von rn-2 von (3) bekommen wir

rnein = - (wasn-3 + wasn-1۰wasn-2۰wasn-3 + wasn-1rn-3 + (1 + wasn-1۰wasn-2rn-4.

Also fahren wir nacheinander fort, bis wir die ganze Zahl am Ende erhalten D so dass

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

In unserem Beispiel haben wir:

N = 2.537 = 43۰59, p = 43, was = 59 und (p - 1)۰(was - 1) = 42 · 58 = 2436 und E = 13.

Verwenden des Euclid-Algorithmus zur Bestimmung des MDC zwischen (p - 1)۰(was - 1) = 2.436 und E = 13 wir bekommen:

2.436 = 187۰13 + 5, 13 = 2۰5 + 3, 5 = 1۰3 + 2, 3 = 1۰2 + 1.

Mit dem umgekehrten Euklid-Algorithmus erhalten wir nun:

1 = 3 - 1۰2, 2 = 5 - 1۰3, 3 = 13 - 2۰5, 5 = 2436 - 187۰13

Daher haben wir, wenn wir wie oben erklärt substituieren:

1 = 3 - 1۰2 = 3 - 1۰( 5 - 1۰3) = 3 - 1۰5 + 1۰3 = - 5 + 2۰3;

1 = - 5 + 2۰3 = - 5 + 2۰( 13 - 2۰5) = - 5 + 2۰13 - 4۰5 = 2۰13 - 5۰5;

1 = 2۰13 - 5۰5 = 2۰13 - 5۰( 2.436 - 187۰13) = 2۰13 - 5۰2.436 + 935.۰13 =

= 937۰13 - 5۰2.436.

Somit erhalten wir 1 = 937۰13 - 5۰2.436, was 937۰13 = 5۰2.436 +1 impliziert.

Daher ist 13۰937 ≡ 1 (mod 2.436), dh E37937 ≡ 1 (mod (p -1)۰(was - 1)).

Wir schließen daraus D = 937.

In der nächsten Spalte werden wir die Nachricht entschlüsseln.

Zurück zu den Spalten

<


Video: Die Riemannsche Vermutung Weihnachtsvorlesung 2016 (Kann 2021).