Sorry aber deine Frage ist sehr unklar.
Du möchtest den Privaten RSA Schlüssel aus dem öffentlichen Exponenten E und Phi == (P-1) * (Q-1) berechnen. Das geht nur über die Faktorization des öffentlichen Modulus N = P * Q. Dh. das was du machen möchtest ist es einen öffentlichen RSA Schlüssel zu knacken, richtig ?
Falls die beiden Primzahlen P,Q entsprechend groß und sauber gewählt wurden, wirst du selbst mit der besten mathm. Library und den besten mathematischen Verfahren nicht in der Lage sein mit vertretbaren zeitlichem/technischen Aufwand ein solches public Modul N in P,Q zu faktorisieren. Logisch, da ja exakt dieses Verhalten die Sicherheit ausmacht.
Solltest du aber mit deiner Frage auf die korrekte Erzeugung eines RSA Schlüsselpaares abzielen, dann gibt es tatsächlich weit bessere Verfahren.
Du hast
1.) die beiden Primzahlen P und Q erzeugt.
2.) den öffentlichen Esxponenten E berechnet oder dich für einen festen Exponenten E entschieden (z.b 3, 17, $10001)
3.) Phi = (P -1) * (Q -1) berechnet
4.) public Modul N = P * Q berechnet
und suchst nun den privaten Entschlüsselungs-Exponenten D.
Du rechnest jetzt
Delphi-Quellcode:
U := LCM(P -1, Q -1);
// LCM = Leat Common Multiple == letztes gemeinsames Vielfaches == Phi(N) falls N=P*Q Primzahlen sind.
repeat
repeat
E := Random() mod (2^(Log2(Log2(N)) * 4));
E := E or 1;
// erzeuge Zufälligen öffentlichen Exponenten E. Sollte 4*Ln2(Ln2(N)) Bits groß sein und ungerade.
// E sollte auch Teilerfremd zu P,Q sein. Wir überprüfen dies mit dem GCD = greatest common divisor == ggT() ==
// größter gemeinsammer Teiler. Da P,Q Primzahlen sind muß der GCD mit E immer 1 sein, ergo E kann und darf KEIN
// Teiler der Primzahlen P,Q sein. Sollte GCD <> 1 sein so kann P,Q keine Primzahl sein, ergo der RSA Schlüssel
// wäre absolut unsicher weil man nicht mit Primzahlen arbeitet.
until (GCD(E, P) == 1) and (GCD(E, Q) == 1);
// erzeuge nun den privaten Entschlüsselungs Exponenten D
// D = E^-1 mod LCM(P-1, Q-1) == E^-1 mod Phi(N)
// E^-1 mod X ist eine Division in einem modularem Ring. Man lösst diese Berechnung mit Hilfe
// des Muliplikativen Inversen. Das modulare Multiplikative Inverse lässt sich mit dem erweiterten GCD() berechnen.
// D muß größer als E sein und teilerfremd zu N. Da die einzigsten Teiler von N die Primzahlen P,Q sein sollten
// kann D nur dann ein Teiler von N sein wenn D==P oder D==Q ist oder eben P,Q keine Primzahlen sind.
// GCD(D, N) == 1 überprüfen wird dies.
until NInvMod(D, E, U) and (NSize(D) >= NSize(E)) and NGCD1(D, N);
So fertig ist dein RSA Schlüsselpaar.
Die FGInt == Fast Gigantic Integers (M. Waldenburg glaube ich mich zu erinnern hat diese Lib gecodet) sind leider alles andere als Fast und Gigantic. Such hier im Forum nach meinem
DEC und den vielen Beispielsourcen für RSA. Ich habe nämlich im besonderen RSA hier schon mehrmals als Source gepostet.
Denoch solltest du in den FGInt Sourcen alle angesprochenen Funktionen finden, sprich GCD(), LCM(), Modulare Inversion -> InvMod() oder ExtGCD(). Deren algorithmische Implementierung in FGInt ist allerdings alles andere als auf dem modernsten Stand der Mathematik, denoch aber korrekt.
Gruß Hagen