+1 Daumen
1,5k Aufrufe

Hallo zusammen,

ich stecke in der Vorbereitung für eine Kryptologie-Klausur und bin mehrmals das RSA-Verfahren durchgegangen, bekomme aber für d immer andere Werte heraus als Online-Rechner, die ich mit denselben Werten für p, q und e füttere.

Den erweiterten euklidischen Algorithmus mache ich in tabellarischer Form wie von Prof. Spannagel in seinen Videos erklärt. Vielleicht sieht ja jemand, was für einen Fehler ich dabei mache. Bei kleineren p und q komme ich auf das richtige Ergebnis für d (vielleicht Zufall?) aber in u.a. diesem Beispiel haut es einfach nicht hin:


p = 23,  q = 1
n = 437
phi(n) = 396
e = 7


Bestimme d mit e * d mod phi(n) = 1 mit dem erweiterten euklidischen Algorithmus.

Euklidischer Algorithmus (a:b = q rest r):

a
b
q
r
7
396
0
396
396
7
56
4
7
4
1
3
4
3
1
1
3
1
3
0


Erweiterter euklidischer Algorithmus

a
b
q
r
x
y
7
396
0
396
-113
2
396
7
56
4
2
-113
7
4
1
3
-1
2
4
3
1
1
1
-1
3
1
3
0
0
1



dabei gehe ich nach der youtube-Anleitung so vor:
in die untere Zeile schreibe ich x*a + y*b = 1

dann immer in jeder Zeile
x(neu) = y(alt) und y(neu) = x(alt) - q(neu) * y(alt) oder auch mit index geschrieben neu = i, alt = i-1

Mein d wäre also 113, der Online-Calculator sagt aber d müsste 283 sein.

Als Probe rechne ich e * x + phi(n) * y = 1 und das kommt sogar hin: 7 * -113 + 396 * 2 = 1

Ich hoffe mir kann jemand sagen, was ich falsch mache. Besten Dank vorab!

Avatar von

rsa das nächste Mal bitte direkt in der Stacklounge fragen. Nun kannst du dort schon mal die "ähnlichen Fragen" anschauen. Bsp. https://www.stacklounge.de/3867/anzahl-verschlusselungsexponenten-eines-moduls-berechnen

Bitte diese Frage aber NICHT noch ein zweites Mal einstellen. Auch in der mathelounge gibt es "ähnliche Fragen".

Müssten nicht p und q Primzahlen sein?

Also ich kenne es so:

p und q sind prim und n = pq. phi(n) = (p-1)*(q-1).

1 Antwort

+1 Daumen
 
Beste Antwort
Mein d wäre also 113

Dein d wäre -113 und es gilt -113 ≡ 283 mod 396.

Avatar von 5,7 k

Das verstehe ich leider nicht. Wieso ist -113  ≡ 283 mod 396,

wenn doch -113 mod 396 = -113 ist und 283 mod 396 = 283

wenn doch -113 mod 396 = -113 ist

Das ist es nicht. Stattdessen ist -113 mod 396 = 283.

Der Ausdruck

        a mod b

bedeutet

        Rest bei ganzzahliger Division von a durch b.

Dabei ist der Rest eine natürliche Zahl zwischen 0 (inklusive) und b (exklusiv).

Wieso ist -113  ≡ 283 mod 396,

Weil 1·396 + (-113) = 0·396 + 283.

Beachte, dass

        -113  ≡ 283 mod 396

nicht das gleiche ist wie

        -113  ≡ (283 mod 396)

sondern das gleiche wie

        (-113  ≡ 283) mod 396

Ausdrücke der Form

        a ≡ b mod n

bedeuten

        "a und b haben bei ganzzahliger Division durch n den gleichen Rest."

Vielen Dank!

Dass a und b kongruent sein müssen und somit denselben Rest lassen, war mir bewusst.

Ich glaube

Weil 2·396 + (-113) = 0·396 + 283.

dort meinst du 1·396 + 283, dann passt die Gleichung und ich verstehe, dass es richtig ist, weil derselbe Rest gelassen wird, danke für die Erklärung.

Was mir jetzt noch fehlt, ist der Ansatz, wie ich darauf komme. Ich habe den erweiterten euklidischen Algortihmus durchgeführt, weiß aber nicht so richtig, wie ich dann bei negativen Zahlen die richtige (diophantische?) Gleichung aufstelle, um auf das d zu kommen. Gibt es da einen einfachen Trick oder muss ich mit negativen Zahlen modulo rechnen können?

Danke für die viele Hilfe!

dort meinst du 1·396 + 283

Habe ich mittlerweilse korrigiert.

wie ich dann bei negativen Zahlen die richtige (diophantische?) Gleichung aufstelle, um auf das d zu kommen

396 - 113 = 283

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community