Hallo,

ich habe Probleme mit dem DHKE … Es ist schwer den diskreten Logaritmus einer Gleichung g^x mod p = m zu berechnen.
Aber warum muss g eine Primwurzel (von p) sein?
Ist die Berechnung dann besonders rechenintensiv?
Was hat es für die Lösung des DL-Problems zu bedeuten, dass ich mit g^x mod p (x=1..n) alle Zahlen für p von 1 bis p-1 darstellen kann?
Kann mir das jemand in Worten erklären?


Ein DHKE-Beispiel (vielleicht kann man es daran leicht erklären):
A und B einigen sich auf Primzahl p=53 und Primwurzel g=2 (von 53).

1.
A errechnet Zufallszahl x. –> g^x mod p.
B errechnet Zufallszahl y. –> g^y mod p.

A berechnet 2^29 mod 53 = 45
B berechnet 2^12 mod 53 = 15 … 45 und 15 werden zwischen A und B ausgetauscht.

Die setzen das dann als g bei 1. ein und erhalten A=36 und B=36.

2.
Ein Angreifer könnte g=2, p=53 und die 45 von A und 15 von B beim Austausch beobachten.


Vielen dank für die Mühe!

g^x mod p = m zu berechnen.
Aber warum muss g eine Primwurzel (von p) sein?

Damit die Funktion die Wertemenge komplett ausfüllt. Stell Dir vor, g wäre 2 und p 10. Dann könnte m niemals ungerade werden.

hmm, das leuchtet ein… aber wäre es nicht sinnvoll es so zu wählen, das man auch mal die gleichen keys bei verschiedenen werten raus bekommt? so kommt man doch niemal auf gleiche werte und ein angreifer bräuchte nur alle y bis (p-1) ausprobieren, bis er auf den richtigen wert kommt. o.k., bei großen werten wäre die berechenzeit zu hoch…