Eine BigInt Klasse + RSA-Beispiel

[peanut]

Hallo,

ich habe vor einiger Zeit eine BigInt-Klasse implementiert und sie erfolgreich in einigen Verschlüsselungsprojekten eingesetzt.

Die BigInt-Klasse implementiert große (big, large oder huge) Integerzahlen, die in einem dynamischen Array von 32-Bit-Werten gespeichert werden. Die Basis ist demnach 2^32, wobei man sich darüber keine großen Gedanken machen muss, da Konvertierungsfunktionen zur Basis 10 bereitstehen. Wer möchte, kann die einzelnen digits jedoch auch direkt ansprechen und verändern.

Implementiert wurden Vergleichsoperatoren (>, <, =, >= usw.) und arithmetische Funktionen wie +, -, *, div, mod, exp sowie der erweiterte Euklidsche Algorithmus, so dass man ohne all zu großen Aufwand die typischen asymmetrischen kryptografischen Verfahren implementieren kann (für Elliptische Kurven muss man die Klasse um Punktoperationen erweitern, das sollte jedoch kein all zu großes Problem darstellen.).

Die Lizenz ist fair - habe ich von Assarbad übernommen, ich hoffe mal, er verzeiht mir...

Klasse:
Siehe Anhang und Text oben.

Beispiel:
Erzeugt RSA-Schlüssel bis 4096bit. Mehr sollte man nicht wählen, das dauert sonst zu lange. Ich habe auf Wunsch nun auch noch die zwei Funktionen rsa_encrypt und rsa_decrypt implementiert, mit denen man Puffer beliebiger Länge verschlüsseln kann. Ich rate aber dringend davon ab, ganze Dateien auf diese Weise zu verschlüsseln. Häufig wird mit RSA nur ein zufällig erstellter Schlüssel z.B. für AES oder RC4 mittels RSA verschlüsselt, der Rest wird dann mittels AES/RC4 und dem zufälligen Schlüssel "unkenntlich" gemacht.

Gruß peanut.

[peanut]

Zitat von Flocke:

Aber das ist gerade die "nicht so gute" Variante gewesen (sorry Himi).

Was shmia vielleicht hätte etwas hervorheben sollen und was Dax auch schon geschrieben hat: du solltest nie die Methode Free überschreiben sondern immer den Destruktor Destroy, und das mit override - dort gehört dein Aufräumcode hinein.

Ich bin für alle Hinweise dankbar . Ursprünglich waren die Funktionen nicht in einer Klasse, das wurde erst später gemacht - dementsprechend sieht das jetzt auch aus (wie man sieht )...

Die aktualisierte Version ist jetzt online.

[Mackhack]

Kann jemand diesen Thread loeschen bitte von mir?

[peanut]

Zitat von Mackhack:

Kann jemand diesen Thread loeschen bitte von mir?

Wieso löschen, gibt es ein Problem?

Gruß peanut.

[Balu der Bär]

Ich denke Mackhack hat sich verschrieben, er meinte nicht den Thread löschen sondern nur seinen Post.

[peanut]

Ich hoffe doch Ich werde bei so etwas aber immer hellhörig, da in der Vergangenheit bereits BigInt-Klassen anderer Autoren wegen irgendwelcher Patentansprüche nicht mehr öffentlich als Download angeboten werden durften....

[Mackhack]

Ja sorry,

meinte meinen Post net den ganzen Thread. Entschuldige fuer den erhoeten Puls den ich dir wohl verpasst habe!

[dominikkv]

hmm... wie kann ich eigendlich zu diesem BigInt eine zahl addieren...?

also sowas irgendwie:

  MyBigInt.Add(548); weil bei der add-methode kann ja nur ein weiterer BigInt übergeben werden...

[peanut]

Hallo!

Dies Funktion habe ich damals nicht implementiert, wäre allerdings ganz sinnvoll - muss ich zugeben

Ich schau mal, was ich da machen kann... braucht aber ein paar Stunden/Tage...

[negaH]

Par Sachen sind mir aufgefallen (habe ja selber so'ne Library programmiert http://www.michael-puff.de/Developer...agen_Reddmann/

1.) TBigInt.Trim; sollte umbenannt werden in TBIgInt.Normalize;
2.) Ein TBigInt der 0 ist wird bei dir mit FDigit[0] := 0; initialisiert. Das führt dazu das Length(FDigit) = 1 ist. Du solltest die 0 intern mit FDigit = nil = Lenght(FDigit) = 0 definieren. Das vereinfacht alle nachfolgenden Operationen.
TBigInt.IsZero := FDigits = nil;
3.) Es ist clever FDigits in Schritten von zb. 16 TDigits zu erhöhen. Parallel dazu ein neues Feld FCount das die Anzahl der real benutzten TDIgits in FDigits speichert. So verhindert du die vielen Reallokationen des dynam. Arrays FDigits. Das bringt ne ganze Menge mehr Performance
4.) Deine Konvertierungsfunktionen eines TBigInt von/nach String zu einer beliebigen Basis sind ineffizient Das geht bei weitem schneller, bzw. dein Algorithmus ist ineffizient.
5.) Die ganzen Funktionen wie .IsGreater, .IsEqual usw. sind überflüssig. Das ist "Programmiererdenken" und nicht Denken eines Mathematikers. In meiner Lib gibts nur eine Funktion .NCmp(A, B): Integer; vergleiche A mit B und gebe -1 zurück wenn A < B, +1 wenn A > B und 0 wenn A = B.
6.) Zur Überprüfung einer Zahl auf Prime gibt es bessere Algos. als Rabin Miller. Zb. Test nach Selfridge-Wagstaff-Pomerance.
7.) Add() und Sub() sind die gleiche Operation nur mit inversen Vorzeichen, warum zwei getrennte Funktionen
8.) Warum subtrahisert du im 2'Complement, die vorherige Konvertierung macht deine Sub/Add unnötig langsam.
9.) die Funktionen für Add()/Sub()/Mul() etc. sollten in Assembler codiert werden. Besonders weil du als Basis 2^32 benutzt. Das hat primär nichts mit Peformance zu tuen, sondern als erstes mit der Fähigkeit in Assembler die speziellen Features der CPU besser benutzen zu können. Dh. in Assembler haben wir Möglichkeiten die Opcode für ADD/SUB/MUL/DIV chained zu benutzen. Deine jetzge Konvertierung und Rechnung mit Int64 macht deine Funktionen mindestens 3 mal so langsame wie sie sei könnten. Int64 ist in der Delphi RTL absolut miserable implementiert, soll heisen ineffizient. Fast alle meiner eigenen Int64 Routinen sind 2-5 mal schneller als die von Borland.
10.) deine Division geht weit besser. Schau mal bei D.Knuth rein, Absatz "Arithmetics".
11.) die Barret Reduction ist im Vergleich zum Montgomery Trick ineffizienter

Gruß Hagen

[negaH]

Delphi-Quellcode:

function DoAddC(Digits: Pointer; Value: Cardinal; Count: Integer): Cardinal; 
asm
         
         LEA EAX,[EAX + ECX]
         NEG ECX
         ADD [EAX + ECX],EDX
         MOV EDX, 0
         JMP @@2 
@@1:     ADC [EAX + ECX],EDX
@@2:     JNC @@3
         INC ECX
         JNZ @@1
@@3:     ADC EDX,EDX
         MOV EAX,EDX
end;

procedure TBigInt.Add(Value: Cardinal);
var
  Carry: Cardinal;
begin
  Carry := DoAddC(@FDigits, Value, Length(FDigits));
  if Carry <> 0 then
  begin
    SetLength(FDigits, Length(FDigits) +1);
    FDigits[High(FDigits)] := Carry;
  end;
end;

Gruß Hagen