RSA-Verfahren < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:16 Mo 15.07.2013 | | Autor: | Flixx |
| Aufgabe | a) Verschlüsseln Sie die Zahl m=5 nach dem RSA-Verfahren mit p = 7, q = 11, e=7.
b)Bestimmen Sie den zu e=7 gehörigen privaten Schlüssel mit Hilfe des euklidischen Algorithmus |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich sitze grad vor meiner Prüfungsvorbereitung und habe ein massives Problem bei der Findung des privaten Schlüssel für ein RSA-Verfahren mit den oben genannten Werten.
Wie ist mein Stand:
Meine bisherige Aufgabe sieht so aus:
m =5
p = 7
q = 11
n = 77
phi(n) =60
d=?
Verschlüsselung ergab bei G = [mm] m^e [/mm] mod 77 G = 47
Entschlüsselung
Öffentlicher Schlüssel (7, 77)
ggT(7,60) =1
60 = 8*7 Rest 4
7 = 1*4 Rest 3
4 = 1*3 Rest 1
3 = 3*1 Rest 0
weiter habe ich dann mit den erweiterten euklidischen Algorithmus in rekursiver Form gearbeitet - sah dann so aus
a b q s t
60 7 8 -1 9
7 4 1 1 -1
4 3 1 0 1
3 0 1 0
gerechnet wurde hier immer mit s= t^alt und t = s^alt - q * t^alt
Danach wurde in die Formel 1= s * a + t *b eingesetzt, was ergab:
-1 * 60 + 9 * 7 = 3
Somit d = 3
d = 3 wurde in K = [mm] G^d [/mm] mod n eingesetzt
K = [mm] 47^3 [/mm] mod 77 = 27
Laut WolframAlpha bräuchte ich für die Entschlüsselung jedoch 47^13...aber ich komm ums verrecken nicht drauf, wäre absolut dankbar für jede Hilfe! :) Ist dringend.
|
|
| |
|
Hallo Flixx,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> a) Verschlüsseln Sie die Zahl m=5 nach dem RSA-Verfahren
> mit p = 7, q = 11, e=7.
> b)Bestimmen Sie den zu e=7 gehörigen privaten Schlüssel
> mit Hilfe des euklidischen Algorithmus
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hallo,
>
> ich sitze grad vor meiner Prüfungsvorbereitung und habe
> ein massives Problem bei der Findung des privaten
> Schlüssel für ein RSA-Verfahren mit den oben genannten
> Werten.
>
> Wie ist mein Stand:
>
> Meine bisherige Aufgabe sieht so aus:
>
> m =5
> p = 7
> q = 11
> n = 77
> phi(n) =60
> d=?
>
> Verschlüsselung ergab bei G = [mm]m^e[/mm] mod 77 G = 47
>
> Entschlüsselung
>
> Öffentlicher Schlüssel (7, 77)
>
> ggT(7,60) =1
>
> 60 = 8*7 Rest 4
> 7 = 1*4 Rest 3
> 4 = 1*3 Rest 1
> 3 = 3*1 Rest 0
>
> weiter habe ich dann mit den erweiterten euklidischen
> Algorithmus in rekursiver Form gearbeitet - sah dann so aus
>
> a b q s t
> 60 7 8 -1 9
> 7 4 1 1 -1
> 4 3 1 0 1
> 3 0 1 0
>
> gerechnet wurde hier immer mit s= t^alt und t = s^alt - q *
> t^alt
>
> Danach wurde in die Formel 1= s * a + t *b eingesetzt, was
> ergab:
>
> -1 * 60 + 9 * 7 = 3
>
> Somit d = 3
>
> d = 3 wurde in K = [mm]G^d[/mm] mod n eingesetzt
>
> K = [mm]47^3[/mm] mod 77 = 27
>
> Laut WolframAlpha bräuchte ich für die Entschlüsselung
> jedoch 47^13...aber ich komm ums verrecken nicht drauf,
> wäre absolut dankbar für jede Hilfe! :) Ist dringend.
47 ist die verschlüsselte Nachricht,
denn [mm] 5^e [/mm] mod 77 = [mm] 5^7 [/mm] mod 77 = 47.
Berechne das multiplikative Inverse von e mod phi(N).
Weiterhin ist [mm]47^{30} \equiv 1 \ \operator{mod}\left(77\right)[/mm].
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:37 Mo 15.07.2013 | | Autor: | Flixx |
Also, mir hilft die Antwort grad nicht weiter, da mir klar ist, dass die verschlüsselung 47 ist.
Meine Frage ist, warum ich den privaten Schlüssel nicht richtig ermitteln kann, bzw. wo genau mein Fehler liegt.
|
|
|
| |
|
Hallo flixx,
> weiter habe ich dann mit den erweiterten euklidischen Algorithmus in
> rekursiver Form gearbeitet - sah dann so aus
>
> a b q s t
> 60 7 8 -1 9
> 7 4 1 1 -1
> 4 3 1 0 1
Es fehlt hier die Zeile:
3 1 3 ..... (zu deiner 4. Gleichung)
> 3 0 1 0
> gerechnet wurde hier immer mit s= t^alt und t = s^alt - q * t^alt
>
> Danach wurde in die Formel 1= s * a + t *b eingesetzt, was ergab:
>
> -1 * 60 + 9 * 7 = 3
Hier hättest du sofort abbrechen müssen. Der richtig angewandte erw. eukl.Alg. liefert eine Darstellung
[mm] $x\cdot [/mm] a ´+y [mm] \cdot [/mm] b =ggT(a,b)$
Die obige Gleichung ist nicht von dieser Form.
> Somit d = 3
Wie schlussfolgerst du denn das?
> Also, mir hilft die Antwort grad nicht weiter, da mir klar
> ist, dass die verschlüsselung 47 ist.
>
> Meine Frage ist, warum ich den privaten Schlüssel nicht
> richtig ermitteln kann, bzw. wo genau mein Fehler liegt.
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:03 Di 16.07.2013 | | Autor: | Flixx |
Es fehlt hier die Zeile:
3 1 3 ..... (zu deiner 4. Gleichung)
Das habe ich auch schon probiert, dann wird mein oberstes t zu -7 und d wird zu 11.
"Hier hättest du sofort abbrechen müssen. Der richtig angewandte erw. eukl.Alg. liefert eine Darstellung
$ [mm] x\cdot [/mm] a ´+y [mm] \cdot [/mm] b =ggT(a,b) $
Die obige Gleichung ist nicht von dieser Form."
Wieso, die Form ist doch genau die gleiche, nur das statt x s in der formel steht und statt y t, oder sehe ich etwas falsch.
"Wie schlussfolgerst du denn das? "
47 ist das Ergebnis der Verschlüsselung über G = [mm] 5^7 [/mm] mod 77
|
|
|
| |
|
Hallo,
> Es fehlt hier die Zeile:
> 3 1 3 ..... (zu deiner 4. Gleichung)
>
> Das habe ich auch schon probiert, dann wird mein oberstes t
> zu -7 und d wird zu 11.
Versuch des ganze doch mal ohne die rekursive Tabelle.
Oder wenn esw unbedingt mit der rekursiven Tabelle sein muss, überprüfe jeden einzelnen Schritt.
So kann ich nicht sagen was du falsch machst.
(Übrigens was ist jetzt s?)
> "Hier hättest du sofort abbrechen müssen. Der richtig
> angewandte erw. eukl.Alg. liefert eine Darstellung
> [mm]x\cdot a ´+y \cdot b =ggT(a,b)[/mm]
> Die obige Gleichung ist
> nicht von dieser Form."
>
> Wieso, die Form ist doch genau die gleiche, nur das statt x
> s in der formel steht und statt y t, oder sehe ich etwas
> falsch.
Dir ist klar, dass $ggT(7,60)=1 [mm] \neq [/mm] 3$?
>
> "Wie schlussfolgerst du denn das? "
>
> 47 ist das Ergebnis der Verschlüsselung über G = [mm]5^7[/mm] mod
> 77
Ich schreibe meine Anmerkungen immer unter das worauf ich mich beziehe, nicht darüber.
Ist imho im deutschen Sprachraum auch so üblich.
>
|
|
|
|
