Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » RSA-Verschlüsselung und chinesischer Restsatz

RSA-Verschlüsselung und chinesischer Restsatz

Universität / Fachhochschule

Kryptologie

Tags: chinesischer Restsatz, Kryptologie, RSA, RSA-Verschlüsselung

Kleini aktiv_icon

00:26 Uhr, 07.06.2024

Hallo,

Mir ist nicht ganz klar wofür ich den chinesischen Restsatz bei der RSA-Verschlüsselung benötige.
Angenommen ich habe

x = 2, e = 7, s = 247, n = 323, p = 17, q = 19

.
Dann verschlüssele ich

C (x) = C (2) = 2^{7} mod 323 = 128

.
Zum entschlüsseln nutze ich

D (y) = D (128) = 128^{247} mod 323

.
Zur schnelleren Berechnung schreibe ich

128^{247} mod 323

folgendermasen um:

x \equiv 128^{247} mod 17

x \equiv 128^{247} mod 19

Nun könnte ich ja theoretisch den chinesischen Restsatz anwenden, aber es wäre doch einfacher, wenn ich beispielsweise

128^{247} mod 17

mit dem Square and Multiply Algorithmus berechne.
Wo genau liegt jetzt der Vorteil des chinesischen Restsatzes oder habe ich in der Rechnung irgendwas übersehen?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

HAL9000

10:07 Uhr, 07.06.2024

Anscheinend missverstehst du da was: Der Chinesische Restsatz hilft nicht beim konkreten Ausrechnen deiner Werte

x mod 17

bzw.

x mod 19

, sondern wirkt anschließend beim Zusammenführen dieser beiden Ergebnisse zu

x mod 323

.

Natürlich kannst du auch direkt

12 8^{247} mod 323

mit Square-and-Multiply ausrechnen. Der Vorteil der Auftrennung in

12 8^{247} mod 17

sowie

12 8^{247} mod 19

entfaltet sich m.E. erst dadurch, dass man hier z.B. den Kleinen Fermat effektiv einsetzen kann.

EDIT: Ich korrigiere mich - im vorliegenden Fall kommt man auch mit Euler-Fermat beim Original-Modul 323 wunderbar schnell zum Ziel. Wegen

128 = 2^{7}

und

7 \cdot 247 = 1729 = 6 \cdot 288 + 1

gilt

12 8^{247} = 2^{1729} = 2^{6 \cdot 288 + 1} = {(2^{288})}^{6} \cdot 2^{1} \overset{E F}{\equiv} 1^{6} \cdot 2 = 2 mod 323

basierend auf

φ (323) = φ (17 \cdot 19) = 16 \cdot 18 = 288

.

Mehrere glückliche Fügungen halfen aber bei dieser so einfach erscheinenden Rechnung: Zum einen die unmittelbar erkennbare Reduktion

128 = 2^{7}

auf die kleine Basis 2. Zum anderen der geringe Restexponent 1 bei der Zerlegung

1729 = 6 \cdot 288 + 1

, i.d.R. hat man nicht so ein Glück.

--------------------------------------------------------------

Betrachte daher besser mal ein komplizierteres Beispiel, etwa

x = 37

mit dann

C (37) = 113

.

Bei 113 gibt es erstmal keine offenkundige Potenzreduktion, und bei

11 3^{247}

nützt einem das

φ (323) = 288

herzlich wenig.

Primfaktorweise sieht das anders aus: Es ist

247 = 15 \cdot 16 + 7

, und damit

x = 11 3^{247} \equiv {(- 6)}^{247} \equiv {(- 6)}^{7} = 3 6^{3} \cdot (- 6) \equiv 2^{3} \cdot (- 6) = - 48 \equiv 3 mod 17

x = 11 3^{247} \equiv {(- 1)}^{247} = - 1 mod 19

, auch hier ein wenig Glück mit der -1 (d.h. kein Fermat war nötig)

Zu lösen ist dann das Kongruenzsystem

x \equiv 3 mod 17

x \equiv - 1 mod 19

,

welches per Chinesischem Restsatz genau eine Lösung

x mod 323

besitzt. Die zweite Gleichung ergibt

x = 19 a - 1

, in erstere eingesetzt

19 a - 1 \equiv 2 a - 1 \equiv 3 mod 17

, das ergibt

a \equiv 2 mod 17

und damit Lösung

x \equiv 19 \cdot 2 - 1 = 37 mod 323

Kleini aktiv_icon

16:36 Uhr, 07.06.2024

Danke erstmal für die schnelle Antwort.
Ich habe allerdings noch Probleme bzw. verstehe nicht ganz die Umformung.
Könntest du mir vielleicht den Teil

x \equiv 113^{247} \equiv 3 mod 17

x \equiv 113^{247} \equiv - 1 mod 19

bitte nochmal genauer erklären?

HAL9000

16:51 Uhr, 07.06.2024

113 \equiv 113 - 7 \cdot 17 = - 6 mod 17

dürfte klar sein.

Die Potenzregeln solltest du auch kennen, insbesondere

a^{b + c} = a^{b} \cdot a^{c}

sowie

a^{b c} = {(a^{b})}^{c}

{(- 6)}^{7} = {(- 6)}^{2 \cdot 3 + 1} = {({(- 6)}^{2})}^{3} \cdot {(- 6)}^{1} = 3 6^{3} \cdot (- 6)

und dann noch

36 \equiv 36 - 2 \cdot 17 = 2 mod 17

genutzt.

Bei Modul 19 geht es viel schneller wegen

113 \equiv 113 - 6 \cdot 19 = - 1 mod 19

.

Ein bisschen solltest du dich auch selbst anstrengen, und vor allem die Grundzüge der Modulrechnung kennen - wenn ich jeden läppischen kleinen Schritt ausführlichst dokumentieren soll, dann werde ich ja nie fertig.

Außerdem: Es ist kein "Muss", genauso in der Rechnung vorzugehen wie ich es oben getan habe. Ich habe nur einen Weg gewählt, der sich mit moderater Kopfrechnung bewältigen lässt. Genauso sind andere Varianten da möglich - letztendlich sollte selbstverständlich immer dasselbe Endergebnis rauskommen.

Kleini aktiv_icon

19:05 Uhr, 07.06.2024

Ich hab meinen Denkfehler gefunden. Ich hab mein Beispiel einfach nur so schlecht gewählt, das gilt:

x \equiv 128^{247} \equiv 2 mod 17

x \equiv 128^{247} \equiv 2 mod 19

Deshalb war ich verwirrt, warum man den chinesischen Restsatz überhaut benötigt.

1586362

1586322

	Status: nicht eingeloggt	Noch nicht registriert?