Große Zahlen in Delphi.
Problem!
Lösung
Die BigNum2.pas von Sebastian Jänicke. Mit dieser Unit ist es möglich (fast) beliebig große Zahlen in Delphi miteinander zu verrechnen. Der neue Typ TBigNumber, den die Unit liefert, ist ein Array aus Bytes. Da diese Arrays im RAM angelegt werden, können die Zahlen so lang sein wie der RAM freie Bytes hat 
aber auch nur veralgemeinert gesprochen.
Ein Test
Ich habe als Test einfach mal das RSA-Verschlüsselungs-Verfahren implementiert und die RSA-Funktionen in eine .dll ausgelagert. (Wenn Interesse an der dll besteht, kann die mit Dokumentation hochladen)
Der Text links wird im dem Programm als Zeichenvektor bzw Stringvektor (für lange Zahlen) gespeichert und Buchstabe für Buchstabe nach dem RSA-Verfahren verschlüsselt.
Zur Erinnerung: Das RSA-Verfahren arbeitet wie folgt.
(Nachricht ^ Schlüssel) modulo Schlüssel-Modul
Die „Nachricht“ ist der ASCII-Wert der zu verschlüsselnden Zeichens. Der Schlüssel ist ‘e‘ beim verschlüsseln und ‘d‘ beim entschlüsseln. Das Schlüssel-Modul ist ‘n‘. (Rote Zeichen im Bild sind die Schlüsselparameter)
Die Basis beim Verschlüsseln ist eine 3-stellige Zahl, der Exponent beim verschlüsseln lautete 267.657.413 und doch betrug die Berechnungsdauer nur 45ms !
Da steckt ein Trick dahinter ! Würde man einfach xxx^267657413 (xxx<256) rechnen, dürfte man lange warten. Das Geheimnis liegt in der Diskreten Exponentialfunktion. Das Prinzip ist auf Wikipedia recht gut erklärt.
In Delphi mit der BigNum2.pas implementiert sieht es wie folgt aus:
if bigexp = true then // geschickte methode
begin
while BM_CompareNC(k, BMD_StrToBigNum(‘1′, false)) do
begin
gu := BMD_BigNumToStr(BM_Modulo(k, BMD_StrToBigNum(‘2′, false)), false);
if gu = “ then
gu := inttostr(0);
if strtoint(gu) = 1 then
begin
e := BM_Multiply(e, m);
e := BM_Modulo(e, n);
end;
m := BM_Multiply(m, m);
m := BM_Modulo(m, n);
keystring := inttostr(strtoint(keystring) shr 1);
k := BMD_StrToBigNum(keystring, false);
end;
result := e;
end;
Die Variable ‘gu’ steht hierbei für gerade/ungerade und dient im Prinzip zur binären Verarbeitung von k, da geprüft wird ob in der binären Schreibweise von k, das ganz rechte Zeichen (kleinste 2er Potenz) eine 1 ist oder anders ausgedrückt, ob k gerade oder ungerade ist. Das Ergebnis liefert die Rechnung k modulo 2.
Darunter ist die Diskrete Exponentialfunktion implementiert.
Die RSA.dll liefert außer dem RSA-Algorithmus für BigInt auch noch einen der das Ergebnis als int64 zurückgibt, sowie einen RSA-Schlüssel-Generator.
