RSA- Ver- und Entschlüsselung: Problem mit großen Zahlen

[Suppenhuhn]

Hi,
Also ich habe vor kurzem meine Facharbeit in Informatik angefangen.
Die bezieht sich auf Kryptologie, spezialisiert auf das RSA-Verfahren.

Zugegeben, ich habe ein wenig spät angefangen und stehe jetzt etwas unter Zeitdruck :roll:,
mein Problem ist folgendes:

Die Grundstruktur hab ich jetzt eigentlich schon fertig, nur habe ich noch ein paar Probleme mit den Potenzen.
Durch das Potenzieren in den Chiffrier-Funktion werden die ganzen Zahlen natürlich irre groß, selbst für 64Bit-Integer zu groß.

Jetzt habe ich mich an einer Funktion versucht, die die Potenzen zerlegt und einzeln berechnet, so dass ich sie erst nach dem Modula zusammenfüge.
Das sieht beispielsweise so aus:

M = 11^23 mod 187 = [11 mod 187 * 11² mod 187 * 11^4 mod 187 x 11^16 mod 187] mod 187
M = [11 * 121 * 55 * 154] mod 187 = 88

Das ganze habe ich mit Binärzahlen realisiert, also teilt er die Potenzen einfach nach einem binären System auf, das ganze sieht so aus:

Delphi-Quellcode:

Procedure TForm1.PotZerlegung(Exponent:integer;var Exponenten:TBinArray);
var sExpo:string; i:integer;
begin
 sExpo := DezToBin(2,Exponent);
 For i := length(sExpo) downto 1 do
  Exponenten[length(sExpo) - (i-1)] :=
   expo(2,(length(sExpo) - i)) * StrToInt(sExpo[i]);
end;

Nur bleiben da größere Exponenten wie 16,32 usw weiterhin bestehen,
also müsste ich das ganze noch weiter aufteilen.
Dabei dürfen sie allerdings auch nicht zu klein werden, weil sie mir sonst bei dem Modula nicht weiterhelfen.

Klingt jetzt vieleicht alles etwas verwirrend, vieleicht ist die Funktion, die ich brauche auch nicht so schwer zu realisieren.
Nur habe ich für sowas derzeit irgendwie absolut keinen Kopf, müsste aber bis Montag die Facharbeit fertig haben. ^^

Thx im vorraus!

[generic]

wenns dir hilft mit dieser lib kannst du auch grosse int-zahlen bearbeiten.

http://triade.studentenweb.org/GInt/index.htm

aber ich denke das du mit der zerlegung nicht weit kommst.
die primfaktoren zerlegung ist der knackpunkt von rsa.

[Suppenhuhn]

Ja, die GInts bringen mich da natürlich weiter, das erspart mir dann die ganze Arbeit.
Vielen dank, hatte da bis jetzt noch nichts gefunden.

[Toto88]

hallo, sry dass ich den alten thread nochmal ausgrabe, aber bin durch die boardsuche darauf gekommen

weiss vll jemand, wo ich die genannte lib noch herbekommen koennte, denn der link scheint tot zu sein, und braeuchte das auch .

danke schonmal, falls einer weiter weiss :)

[Sergej]

Öhm...geht doch Gint