GBI/GSS: Diskreter Logarithmus Problem // Diffie-Hellmann-Key-Exchange
2008-02-23 23:10
Southwood
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!
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!