afriess / gnurz Goto Github PK

Moin @afriess ,

ich bin grade dabei eine Funktion für einen RSA-Schlüssel generator zu schreiben.
Da ich hierfür um die minimale Sicherheit zu erhalten die Primzahlen p & q in der Größenordnung 600 Stellen benötige bin ich auf diese Lib gestoßen.

Mir ist nun beim rumprobieren aufgefallen, dass sobald ich eine Zufallszahl mit der Obergrenze >= 10^31 mit gnzZufall() erzeuge und durch den Miller-Rabin-Test gnzMillerRabin() jage, dieser plötzlich ernorm viel länger benötigt als mit 10^30 bzw. nicht innerhalb von 10 Minuten eine Primzahl findet.

Hier meine Funktion zum Testen:

procedure TForm1.Button2Click(Sender: TObject);
var
s: String;
begin
gnz:= TGnurz.create;
repeat
p:= gnz.GNZZufall(gnz.GNZPotenz(gnz.WordToGNZTyp(10), gnz.WordToGNZTyp(StrToInt(LabeledEdit1.Text))));
until gnz.GNZMillerRabin(p, 10);
p:= gnz.GNZadd(p, gnz.GNZPotenz(gnz.WordToGNZTyp(10), gnz.WordToGNZTyp(StrToInt(LabeledEdit2.Text))));
Memo1.Append('Random prim generated from 10^' + LabeledEdit1.Text + ' with a length of ' + LabeledEdit2.Text + 'is: ');
s:= gnz.GNZTypToStr(p);
s:= Trim(s);
Memo1.Append(s + sLineBreak);
gnz.Free;
end;

Ich habe die Pascal datei als Anhang beigelegt.
Das Problem lässt sich reproduzieren, indem man im linken Feld 31 oder mehr eingibt und im rechten Feld 600.
Nimmt man stattdessen 30 & 600 funktioniert alles einwandfrei.

Es wäre schön, wenn das gefixt werden könnte, ich werde mir die Funktion gnzMillerRabin bei zeiten selbst auch noch mal ansehen, aber ich weiß nicht ob ich den Fehler finden werde.

Nette Grüße
Jan-Niklas

Test_RSA.zip