Holzweg.
Beim DH sollte man mit speziellen Primzahlen arbeiten, den Safe Primes oder auch Sophie German Primzahlen genannt. Diese haben folgende Form
P := 2*Q+1
wobei P und Q Primzahlen sein müssen und 2 auch eine Primzahl ist.
Arbeitet man mit diesen Primzahlen dann kann man den Generator so berechnen
Delphi-Quellcode:
G := 3;
repeat
repeat
G := G +1;
T := G^2 mod P;
until T <> 1;
T := G^Q mod P;
until T <> 1;
G ist dann die kleinste Zahl, größer 3, die ein Generator in dieser Domain ist. Das ist sogar erwünscht da dadurch sich die Berechnungen in der DH Domain per Brickel's modularer Exponentation um den Faktor 3 im Vergleich zur k'ary Sliding Window Exponentation beschleunigen lassen.
Arbeitet man nicht mit Safe Primes so benötigst du die Faktorization von P -1 = Phi(P) und musst alle so ermittelten Primzahlen nach obiger Methode austesten. Das Problem könnte diese Faktorization sein, da P meisten >= 2^2048 ist. Es ist dann sinnvoll die Konstruktion von P zu kennen. Dazu gibt es von Lim&Lee die LimLee Primes
"A Key recovery Attack on Discrete Log-based Schemes using a Prime Order Subgroup", Lim & Lee, Crypto '97
deren konstruierte Form sieht so aus
P := 2 * Q * P1 * P2 * ... * Pi +1,
P,2,Q,P1..Pi sind industrielle Primzahlen
P ist zb. 2048 Bits groß
Q ist zb. 160 Bits groß
P1..Pi sind > 160 Bits
Damit ist Q die kleinste Primzahl und bestimmt die Sicherheitsschranke wie sicher P ist. Man wird also beim "Knacken" = Faktorisieren von P als erstes immer Q finden.
Nachdem eine solche Primzahl erzeugt wurde hat man auch dessen komplette Faktorisation und kann im Anschluß den Generator berechnen. Bis auf P und G werden die restlichen Zahlen dann vernichtet.
Im Grunde konstruiert man eine abgeschwächte Variante der Sophie Germain Primzahlen. Wenn man eine gute Crypto Lib hat dann dauert die Konstruktion einer Safe Prime nicht wesentlich länger als die einer LimLee Primzahl. Das Ratio düfte so bei 3 zu 1 liegen. Mit meinem DECMath erzeugt ich eine solche Safe Prime in durchschnittlich unter 1 Sekunde auf einem P4. Nun beim DH Verfahren ist es üblich das alle beteiligten Parteien sich eine verifizierte und hardcoded Primzahl P teilen. Das heist man berechnet den ganzen Kram nur ein einzigstes mal. Es besteht also nicht der geringste Grund Safe Primes nicht zu benutzen und stattdessen irgendeine andere Form der Primzahlen zu benutzen. Besonderst weil man so das hardcoded speichern vom Generator G verzichten kann und mit obiger Methode live diesen Generator berechnen kann. So ist auch zusätzlich noch sichergestellt das man wirklich eine Safe Prime für DH benutzt, da ansonsten obiger Code eben falsche Resultate liefern muß. Ein möglicher Angriff wäre nämlich der Austasuch dieser Domain Parameter.
Gruß Hagen