RSA-Algorithmus Bsp.

08.01.2016, 12:39

pusteblume987

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?

08.01.2016, 12:48

URL

Auf diesen Beitrag antworten »

RE: RSA-Algorithmus Bsp.
Ob du dich vertan hast, kannst du doch leicht selbst prüfen:
Verwende $\begin{eqnarray*} -17\equiv 23 \bmod 40 \end{eqnarray*}$ und dann ist $\begin{eqnarray*} 7\ 23=161\equiv 1 \bmod 40 \end{eqnarray*}$

Für die Entschlüsselung: Schau dir $\begin{eqnarray*} 11^2 \bmod 55 \end{eqnarray*}$ an

08.01.2016, 12:59

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?

08.01.2016, 13:03

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 $\begin{eqnarray*} -17\equiv 23 \bmod 40 \end{eqnarray*}$ . Dazu muss man nicht Fermat bemühen.

08.01.2016, 14:04

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

08.01.2016, 14:07

URL

Auf diesen Beitrag antworten »

RE: RSA-Algorithmus Bsp.
Was willst du denn ständig mit der -17 ???
Du suchst ein t mit $\begin{eqnarray*} t s \equiv 1 \bmod \varphi(n) \end{eqnarray*}$ 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)