wir greifen die Primzahlerzeugung für die beiden Fälle
auf und erläutern das Siebverfahren aus der letzten Lektion noch einmal grafisch. Die durch das Sieb übriggebliebenen Kandidaten werden mit dem Primzahltest (im roten Kasten) auf Primzahleigenschaft geprüft.
Für p wird nun ein zweites Sieb aufgesetzt. Startend bei t_min werden an den durch h teilbaren Stellen Zahlen markiert, sodass nur noch diejenigen t übrigbleiben, für die qt+1 - wahrscheinlich - eine Primzahl ist. Diese werden
(hierbei können Sie folgende Formel benutzen, um 1/q mod h auszurechnen: q^(h-2) siehe kleiner Fermat'scher Satz)
Für den Parameter g muss in DSA gelten: g^q=1 mod p
Dies erreicht man durch eine einfache Schleife, die auf der Folie dargestellt ist. Falls die Bereichnung 1 liefert und dann "ja" herauskommt, wird die Schleife wiederholt.
Andernfalls hat man g gefunden.
Die Zusammenfassung gibt nun in übersichtlicher Form an, wie für 2048-bit-DSA die Parameterwahl zu einem öffentlichen Schlüssel (p,g,q,y) führt.