Lektion Erzeugerkriterium

Anleitung zum Selbstudium

• Folie 1: (nicht zum Thema Erzeuger) es wird errechnet, wieviele Schlüssel man mit 10000 CPUs testen kann, vorausgesetzt
  • jeder Schlüssel wird in einem Takt getestet
  • die Prozessoren sind mit 3,6GHz getaktet
  • die Prozessoren laufen 1 Jahr
• man merke sich die Größenordnung des Ergebnisses: 10^21
• rechnen Sie das in Bits um (wie?), es sollte 70 herauskommen
• also 70 Bits ist das was man durch Ausprobieren zur Zeit etwa maximal erreichen kann ... hierbei ist zu beachten, das jeweils 1 Bit mehr die doppelte Rechenzeit verursacht (exponentiell), also obige Prozessoren laufen für 73 Bits 8 Jahre
• Folien 2: Benutzen Sie das Erzeugerkriterium, um von Hand nachzurechnen
  • 3 ist ein Erzeuger mod 7
  • 2 ist ein Erzeuger mod 11
  • 2 ist ein Erzeuger mod 13
  • 3 ist ein Erzeuger mod 17
  • 3 ist ein Erzeuger mod 31
• Programmieren Sie! Schreiben Sie ein Programm, das als Eingabe g und p erhält und als Ausgabe angibt, ob g ein Erzeuger mod p ist.
• Programmieren Sie weiter! Schreiben Sie ein Programm, das als Eingabe p erhält und als Ausgabe alle Erzeuger g mod p ausgibt.
• Folien 3 und 4 enthalten teilweise Ergebnisse zu den obigen Aufgaben und eignen sich als Testfälle, um die eigene Implementierung zu checken
• Folie 5 (sichere Primzahlen)
  • kryptographisch relevant sind die Primzahlen p, für die (p-1)/2 ebenfalls prim ist
  • finden Sie neben den genannten weitere solche p mit p>47
• Folien 6+7: erklären die Methode von Shanks zur Berechnung des diskreten Logarithmus (d.h. Gleichungen der Form g^x = h mod p lösen)
• hier findet man eine erste Implementierung
• hier findet man eine zweite Implementierung