HTW Berlin Fachbereich 4 Internationaler Studiengang Internationale Medieninformatik (Bachelor) Aktuelle Themen: Cryptography Winter Term 2024/25

Lab 5: Getting Ready for Diffie-Hellmann

1. Wie viele Multiplikationen braucht man, um x¹⁶ auszurechnen? Wie viele für x²¹, x³⁴¹, x²¹⁶⁺¹?
   
   Schreiben Sie ein Programm zur möglichst effektiven Berechnung von x^y mod n, wobei x, y, und n vom Typ long sind.
   
   Zusatzaufgabe: Schätzen Sie ab, wie viele Multiplikationen modulo n in Ihren Algorithmus in Abhängigkeit von y durchschnittlich ausgeführt werden.
   
   
2. Es sei 7^x ≡ 10 mod 31 . Bestimmen Sie x ohne elektronische Hilfe!
   
   Schreiben Sie ein Programm zur Bestimmung des diskreten Logarithmus:
   Parameter seien: Eine Primzahl p und zwei Zahlen a, b ∈ {1, 2, ..., p-1}.
   Rückgabewert: Die kleinste natürliche Zahl x, welche die Kongruenz a^x ≡ b mod p erfüllt, falls dies möglich ist, sonst 0.
   
   Zusatzaufgabe: Berechnen Sie mit Ihrem Programm zu einer gegebenen großen Primzahl p eine Primitivwurzel g modulo p. Benutzen Sie dieses g als Parameter a in Ihrem Programm und messen Sie die Laufzeit für die Berechnung des diskreten Logarithmus x für verschiedene von Ihnen gewählte Werte für b.
   

Your report is due the evening before your next lecture at 22.00!