Diffie-Hellman < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei die Primzahl 20809 und ein Erzeugendes Element aus [mm] Z_{p} [/mm] g = 22. Geheime Zahl von Alice a = 23, von Bob b = 37
a) berechnen sie die Geheimzahl k
nun sei mir k = 11518 ebenfalls bekannt.
b) Ich soll nun die Menge {a, b} berechnen
übrigens, ich halte mich an den Wiki Artikel:
http://de.wikipedia.org/wiki/Diffie-Hellman-Schl%C3%BCsselaustausch
sowie
http://de.wikipedia.org/wiki/Diskreter_Logarithmus |
Hallo zusammen
Aufgabe a ist ok.
Bei b denke ich den Weg zu kennen, scheitere aber an der Mathematik.
K = [mm] g^{a*b} [/mm] mod(p) wobei a und b jeweils eine Primzahl ist.
K, g und p ist bekannt. wenn ich jetzt a*b = j setze, erhalte ich eine Gleichung mit nur noch einer Unbekannten. Diese müsste mit dem Diskreten Logarithmus zu knaken sein. Daran scheidere ich jetzt aber.
wenn diese gleichung gelöst wäre, könnte ich j faktorisieren und würde damit a und b erhalten.
wer kann mir beim Lösen dieser Gleichung helfen?
11518 = [mm] 22^{j} [/mm] mod(20809)
resultat müsste 221 geben
lieber Gruess
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:10 So 06.06.2010 | | Autor: | felixf |
Moin!
> Gegeben sei die Primzahl 20809 und ein Erzeugendes Element
> aus [mm]Z_{p}[/mm] g = 22. Geheime Zahl von Alice a = 23, von Bob b
> = 37
>
> a) berechnen sie die Geheimzahl k
>
> nun sei mir k = 11518 ebenfalls bekannt.
>
> b) Ich soll nun die Menge {a, b} berechnen
Und was ist gegeben? a und b kennst du ja schon aus der Aufgabenstellung. Darfst du [mm] $g^a, g^b, [/mm] g$ benutzen, oder nur [mm] $g^k, [/mm] g$?
> übrigens, ich halte mich an den Wiki Artikel:
>
> http://de.wikipedia.org/wiki/Diffie-Hellman-Schl%C3%BCsselaustausch
> sowie
> http://de.wikipedia.org/wiki/Diskreter_Logarithmus
> Hallo zusammen
>
> Aufgabe a ist ok.
>
> Bei b denke ich den Weg zu kennen, scheitere aber an der
> Mathematik.
>
> K = [mm]g^{a*b}[/mm] mod(p) wobei a und b jeweils eine Primzahl
> ist.
Wieso muessen $a$ und $b$ Primzahlen sein?
> K, g und p ist bekannt. wenn ich jetzt a*b = j setze,
> erhalte ich eine Gleichung mit nur noch einer Unbekannten.
> Diese müsste mit dem Diskreten Logarithmus zu knaken sein.
> Daran scheidere ich jetzt aber.
>
> wenn diese gleichung gelöst wäre, könnte ich j
> faktorisieren und würde damit a und b erhalten.
>
> wer kann mir beim Lösen dieser Gleichung helfen?
>
> 11518 = [mm]22^{j}[/mm] mod(20809)
>
> resultat müsste 221 geben
Der diskrete Logarithmus ist nunmal nicht so einfach zu berechnen. Hier musst du schon etwas arbeiten. Und vor allem erstmal sagen, was ihr fuer Methoden zur Berechnung des diskreten Logarithmus hattet.
Hier wuerde ich Pohlig-Hellman verwenden, da $20809 - 1 = (2 [mm] \cdot [/mm] 3 [mm] \cdot 17)^2$ [/mm] ziemlich glatt ist.
LG Felix
|
|
|
|
