Hallo Fellow Mathematiker, :)

Ich habe eine Frage zum Square and Multiply Verfahren das insbesondere im RSA Kryptosystem zum schnellen Potenzieren verwendet wird. Wie das Verfahren grundsätzlich funktioniert habe Ich verstanden. Jedoch bin Ich mir unsicher ob Square and Multiply auch bei negativem Exponenten angewendet werden kann und ob für zwei unterschiedliche Repräsentanten der gleichen Restklasse auch das gleiche Ergebnis herauskommt.

Zum Beispiel:

\(2^{-107} \mod n \)

Meine Frage ist durch das RSA Verfahren motiviert.

Grundsätzlich operiert das RSA Verfahren im modularen Restklassenring \( Z_n \). 

\( n = p * q \), wobei \( p \) und \( q \) in der Praxis zwei sehr große Primzahlen sind

\( \phi(n) = (p-1)(q-1) \)

Bei dem RSA Verfahren berechnet man einen öffentlich Schlüssel \( e \) und einen privaten Schlüssel \( d \).

Den privaten Schlüssel benutzt man beim Entschlüsseln \( x = y^d \mod n \)

und den öffentlichen Schlüssel beim Verschlüsseln \( y = x^e \mod n \) .

Für die Schlüssel e und d gilt folgendes:

\( e * d = 1 \mod \phi(n) \)

Das heißt man kann den Schlüssel \( d \) mithilfe von \( e \) und \( \phi(n) \) berechnen über den erweiterten euklidischen Algorithmus.

Da wir uns aber im modularen Restklassenkörper befinden können hier auch negative Werte für \( d \) herauskommen. Natürlich kann man einfach nochmal den Modul also das \( \phi(n) \) auf den negativen Wert darauf rechnen und erhält einen positiven Repräsentanten. Allerdings müsste es doch auch möglich sein mit dem negativen Wert für \( d \) weiterzurechnen.

Nun nehmen wir mal folgende Beispielwerte:

\( p = 31, q = 41,  e = 11 \)

\( n = p * q = 31 * 41 = 1271 \)

\( \phi(n) = (p-1)(q-1) = (31-1)(41-1) = 1200 \)

\( EEA(e, phi(n)) = EEA(11, 1200) \)

\( 1 = 1200 − 109 ∗ 11 \)

\( d = -109 \)

nun möchten wir die Formel zur Entschlüssel einer Chiffre \( y=955 \) anwenden

\( x = y^d \mod n \)

Das heißt in unserem Fall

\( x = 955^{-109} \)

Laut Wolfram Alpha kommt dabei eine reelle Zahl raus, die in etwa so krumm wie der Turm zu Pisa ist.

OK, nun versuchen wir es mal mit dem kleinsten positiven Repräsentanten für \( d \)

\( d = d + \phi(n) \mod \phi(n) \)

\( d = -109 + 1200 = 1091 \)

Wir das neue \( d \) in die obige Formel ein

\( x = 955^{-109} \mod n = 67 \)

Wie kann das sein? Der Modul bildet doch einen Körper, das heißt die Multiplikation und Subtraktion ist abgeschlossen. Kommutativ und assoziativ für alle Elemente des Körpers. 

Das Potenzieren ist ja auch nichts anderes als wiederholtes Multiplizieren. Dennoch haben wir hier zwei total unterschiedliche Ergebnisse für zwei Repräsentanten der gleichen Restklasse.

VG

Dennis