RSA-Algorithmus Bsp.

Neue Frage »

pusteblume987 Auf diesen Beitrag antworten »
RSA-Algorithmus Bsp.
Meine Frage:
Die Aufgabe lautet: Entschlüssel mit dem RSA-Algorithmus (n=55, s=7) die Zahl y=11.


Meine Ideen:
n = 55 = 5 x 11
phi(n) = phi(5x11) = 4x10 = 40
s = 7 (ggT(s,phi(n)) = 1 )

Bestimme t mit txs kongruent 1 mod phi(n)
-> tx7 kongruent 1 mod 40

das kann ich mithilfe des euklidischen Algorithmus ausrechnen:
ggT(a,m) = ggT(7,40) = 1
-> 40 = 5 x 7 + 5
-> 7 = 1 x 5 + 2
-> 5 = 2 x 2 + 1 <--
-> 2 = 2 x 1 + 0

gesucht ist jetzt c,d mit ggT(a,m)= cxa + dxm, also ggT(7,40)= cx7 + dx40.
-> 1 = 5 - 2 x 2
= 5 - 2 x (7 - 1 x 5)
= 5 - 2 x 7 + 2 x 5
= 3 x 5 - 2 x 7
= 3 x (40 - 5 x 7) - 2 x 7
= 3 x 40 - 15 x 7 - 2 x 7
= -17 x 7 + 3 x 40

also c = -17, d = 3

x0 = c x b/ggT(a,m) = - 17 = t


entschüsseln: ey kongruent ^t mod n
-> ey kongruent 11^-17 mod 55

da komm ich nicht weiter, ich finde keinen weg das umzuformen...
oder hab ich mich schon beim euklidischen algorithmus vertan?
URL Auf diesen Beitrag antworten »
RE: RSA-Algorithmus Bsp.
Ob du dich vertan hast, kannst du doch leicht selbst prüfen:
Verwende und dann ist

Für die Entschlüsselung: Schau dir an
 
 
pusteblume987 Auf diesen Beitrag antworten »
RE: RSA-Algorithmus Bsp.
ach stimmt ja... Hammer

11^2 kongruent 11 mod 55...

11^-17 kann ich ja durch satz von fermat zu 11^23 mod 40 machen, hilft mir das weiter?
URL Auf diesen Beitrag antworten »
RE: RSA-Algorithmus Bsp.
Zitat:
11^2 kongruent 11 mod 55...

Und da fällt dir nichts weiter dazu ein???? unglücklich

Zitat:
11^-17 kann ich ja durch satz von fermat zu 11^23 mod 40 machen, hilft mir das weiter?

Was willst du denn damit?? Wie ich schon schrieb ist . Dazu muss man nicht Fermat bemühen.
pusteblume987 Auf diesen Beitrag antworten »
RE: RSA-Algorithmus Bsp.
das -17 irritiert mich etwas...

-(11^2)^5 x (-(11^2)^2 x (-11^3), aber das hilft ja nicht weiter..
URL Auf diesen Beitrag antworten »
RE: RSA-Algorithmus Bsp.
Was willst du denn ständig mit der -17 ???
Du suchst ein t mit und hast -17 herausbekommen. Aber mod 40 ist -17 das gleiche wie 23. Also nimm t=23, wenn du mit -17 nicht zurecht kommst (was ich übrigens auch nicht würde)
pusteblume987 Auf diesen Beitrag antworten »
RE: RSA-Algorithmus Bsp.
achso.... ja gut, dann (11^5)^2 x (11^5)^2 x 11^3 = 11^2 x 11^2 x 11 = 11 x 11 x 11 = 11 x 11 = 11 (alles mod 55)
URL Auf diesen Beitrag antworten »
RE: RSA-Algorithmus Bsp.
und damit ist 11 ein Fixpunkt, d.h. die Verschlüsselung ist hier nutzlos smile
pusteblume987 Auf diesen Beitrag antworten »
RE: RSA-Algorithmus Bsp.
ok alles klar!!! danke smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »