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 :lol: - 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.

[Dax]

Bitte häng doch deinen Code (der ja nicht kurz ist) als Anhang an. Danke :)

PS: OpenSource wäre doch die bessere Sparte gewesen? In die Codelib sollen verzugsweise kleine Schnipsel :)

[shmia]

Falsch!!!

Delphi-Quellcode:

procedure TBigInt.Free;
begin
  if (Assigned(Self)) then
  begin
    ZeroMemory(@FDigits[0], DigitCount*4); // object might handle prime factors for
    SetLength(FDigits, 0);                 // crypto keys - overwrite memory with zeros
    FNegative := False;
    Inherited Free;
  end;
end;

Richtig:

Delphi-Quellcode:

destructor TBigInt.Destroy;
begin
   ZeroMemory(@FDigits[0], DigitCount*4); // object might handle prime factors for
                                      // crypto keys - overwrite memory with zeros
// SetLength(FDigits, 0); // Delphi destroys dyn. arrays
   inherited;
end;

[DP-Maintenance]

Dieses Thema wurde von "Dax" von "Neuen Beitrag zur Code-Library hinzufügen" nach "Open-Source" verschoben.
Passt hier dann doch besser ;)

[himitsu]

ich auch, ich auch ._.

Delphi-Quellcode:

procedure TBigInt.Free;
begin
  if (Assigned(Self)) then
  begin
    ZeroMemory(@FDigits[0], DigitCount*4); // object might handle prime factors for
    SetLength(FDigits, 0);                 // crypto keys - overwrite memory with zeros
    FNegative := False;
  end;
  Inherited Free;
end;

Inherited Free; oderauch nur Inherited; (der Name kann hier weggelassen werden) muß unbedingt aufgerufen werden, also wenn du schon eine IF-Abrfage machst, dann muß dieses außerhalb stehen

Und wie mein Vorgänger schon sagte ... der Rest wird eh freigegeben (aber nur, wenn INHERITED aufgerufen wird)

Delphi-Quellcode:

procedure TBigInt.Free;
begin
  ZeroMemory(@FDigits[0], DigitCount*4); // object might handle prime factors for
  Inherited Free;                        // crypto keys - overwrite memory with zeros
end;

[Dax]

Himi, du enttäuschst mich :(

Finalisationscode gehört immer in den Destruktor! :warn:

Free ist nicht umsonst nur als

Delphi-Quellcode:

if Assigned(Self) then
  Destroy;

implementiert... Und vor allem statisch. Free ist nur deshalb die Freigabemethode der Wahl, eben deshalb, weils mit .Destroy bei ner Nil-Referenz knallt, bei Free nicht.

[sir-archimedes]

Zitat:

Zitat von himitsu

ich auch, ich auch ._.

Delphi-Quellcode:

procedure TBigInt.Free;
begin
  if (Assigned(Self)) then
  begin
    ZeroMemory(@FDigits[0], DigitCount*4); // object might handle prime factors for
    SetLength(FDigits, 0);                 // crypto keys - overwrite memory with zeros
    FNegative := False;
  end;
  Inherited Free;
end;

Inherited Free; oderauch nur Inherited; (der Name kann hier weggelassen werden) muß unbedingt aufgerufen werden, also wenn du schon eine IF-Abrfage machst, dann muß dieses außerhalb stehen

Aber das ist doch totaler Blödsinn, oder? Wenn ich mich nicht ganz irre (und ich will es jetzt nicht nachschauen), prüft auch das Free von TObject erst, ob self assigned ist und ruft dann den Destructor auf. Das heißt wenn auch auf jeden Fall Inherited aufgerufen wird, ist das Ergebnis immer das gleiche.

Desweiteren ist die Möglichkeit, Methoden zu überschreiben ja teilweise auch dazu gedacht, die ursprüngliche Methode nämlich nicht immer, sondern nur im passenden Moment aufzurufen... Daher gehört das inherited sicherlich nicht immer nach außen, ans Ende oder sonst wohin!

[Triples]

Hallo
könntest du nicht mal ein beispiel Projeckt adden,habe keine ahnung wie ich das nutzen kann!
Ich selber was nun nicht was ich machen muß um RSA anzuwenden?
Bin für jede hilfe dankbar :P
Grüße
Triples

Code:

procedure TForm1.BitBtn1Click(Sender: TObject);
begin
  if edit1.text='Hilfe' then begin
  enabel.Butten1
showmessage(' Das Kennwort ist Richtig!');
    close;
  end else begin
    showmessage(' Das Kennwort ist FALSCH!');
    edit1.SelectAll;
    edit1.SetFocus;
  end;
end;

[peanut]

Hallo,

habe es korrigiert und mich für himitsu's Vorschlag entschieden... Danke für die Hinweise!

Zitat:

Zitat von Triples

könntest du nicht mal ein beispiel Projeckt adden

Ja, kommt in den nächsten Tagen.

[Flocke]

Zitat:

Zitat von peanut

Hallo,

habe es korrigiert und mich für himitsu's Vorschlag entschieden... Danke für die Hinweise!

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.

[peanut]

Zitat:

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 :-D. Ursprünglich waren die Funktionen nicht in einer Klasse, das wurde erst später gemacht - dementsprechend sieht das jetzt auch aus (wie man sieht :zwinker: )...

Die aktualisierte Version ist jetzt online.

[Mackhack]

Kann jemand diesen Thread loeschen bitte von mir?

[peanut]

Zitat:

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 :wink: 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:

Delphi-Quellcode:

  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

[dominikkv]

so, dann will ich noch ein paar ideen hier reinwerfen:

Wenn du Delphi 2006 oder höher hast kannst du methoden und property in Records deklarieren.
Dadurch entfällt der Constructor und Destructor.
Außerdem kannst du dann Operatoren überladen.
Mit der Impliciten Typumwandlung wird das arbeiten mit dem Datentyp auch angenehmer.
Schau dir einfach mal dieses Beispiel an:

Delphi-Quellcode:

  TBigInt = record
  private
    Data: Integer;
  public
    class operator Implicit(I: Integer): TBigInt;
    class operator Implicit(T: TBigInt): Integer;
    class operator Add(A, B: TBigInt): TBigInt;
  end;

// ...

class operator TBigInt.Add(A, B: TBigInt): TBigInt;
begin
  result.Data := A.Data + B.Data;
end;

class operator TBigInt.Implicit(I: Integer): TBigInt;
begin
  Result.Data := I;
end;

class operator TBigInt.Implicit(T: TBigInt): Integer;
begin
  result := T.Data;
end;

Und jetzt ist das hier problemlos möglich:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var A, B, C: TBigInt;
begin
  a := 5;
  b := 3;
  c := a + b;
  showmessage(IntToStr(c));
end;

[negaH]

Ja das stimmt.

Nun baue mal das

A := B^C mod D

Das wirst du nicht effizient bewerkstelligen könne das das Operatoren Überladen keine Funktionen mit 2 Parametern zulässt.
Man kann zwar

A := B^C;
A := A mod D;

berechnen aber nur theoretisch nicht praktisch. Da B^C beides Zahlen jenseits 2^1024 sein können entstehen durch die Exponenation gigantische Zahlen. Diese sind so groß das sie nie in einen Rechner berechnet werden können.

Die Operation B^C mod D wird also überlicherweise so gelöst das man in jedem Zwischenschritt der Berechnung von C^B modular mit D reduziert. Die nun größten Zahlen die auftreten können sind maximal 2^Ln2(D)*2 Bits groß, also doppelte Anzahl von Bits als D hat.

Nun es gibt noch viele solcher Beispiele die mit dem Operatoren Überladen nicht sauber umgesetzt werden können. Das hat zur Konsequenz das mit deinem Ansatz wir einen Misch Masch aus Funktionen/Objekten und überladenen Operatoren haben. Also keine sinnvolle und homogene Schnittstelle mehr.

Den Ansatz mit Operatoren Überladung eine gute math. Bibliothek bauen zu wollen erachte ich für zu kurzsichtig gedacht.
Es ist dann besser die Operatoren +,- usw. wirklich als Funktionen oder Mehtoden eines Objektes zu bauen.

Aber auch den OOP Ansatz halte ich für schlecht. Stellen wir uns mal ein Object TInteger vor und bauen darin alle wesentlichesten math. Methode rein. Schwups entsteht eine Monsterklasse mit mehr als 100 Methoden. Nun wollen wir diese Schnittstelle in Zukunft durch weitere Mathematische Funktionen erweitern. Also müssen wir diese Monster-Klasse erneut verändern und fügen weitere Methoden hinzu. Das ist dann keine auf's wesentliche abstrajierte OOP Schnittstelle mehr sondern eher eine Sammlung wichtiger Funktionen gruppiert in einem Objekt das bei nachträglichen Veränderungen alle darauf aufsetzten Quellcodes neu complieren lässt.

Nein ich sehe es so: unser Typ TInteger ist nur ein Datentyp wie Integer, LongString usw. Dieser Datentyp wird in normalen prozeduralen Funktionen verwendet die selber die Mathematik für diesen Datentyp implelemtieren. Das ist erweiterbar, wiederverwendbar, einfach zu verstehen und effizient (es vermeidet den mittlerweile gigantischen Overhead der OOP).

OOP gut und schön, aber in diesem Falle kontroproduktiv. Und ich weiß wovon ich rede. Meine DECMath Library ist nun das 4. Konzept in der Schnittselle. Alle 3 Versionen davor waren OOP konform und vom Handling längst nicht so sauber wie die jetzige 4. Version. Diese arbeitet rein Prozedural, benutzt aber Interface-Records als Datentypen der IInteger.

Gruß Hagen

PS: hier mal ein Beispiel wie eine Berechnung der Zahl Pi per AGM aussieht

Delphi-Quellcode:

  procedure NPi_AGM(var R: IInteger; Decimals: Cardinal);
{AGM start with:
   a = 1, b = 1/Sqrt(2), t = 1/2, k = 1

 iteration:

   s = (a + b) / 2
   d = a - s
   d = d^2
   a = s
   s = s^2
   t = t - d * 2^k
   b = Sqrt(s - d)
   k = k +1

 final:
   pi ~ (a + b)^2 / 2t }
  var
    A,B,D,T: IInteger;
    W: Integer;
  begin
    Inc(Decimals, 3);           // +3 digits reserve
    NPow(R, 5, Decimals);       // R =  5^Decimals
    NShl(A, R, Decimals);       // A = 10^Decimals
    NShl(D, R, Decimals -1);    // D = 10^(Decimals -1)^2
    NSqr(D);
    NSqr(B, A);                 // B = (10^Decimals^2 * 2)^0.5 div 2
    NShl(B, 1);
    NSqrt(B);
    NShr(B, 1);
    W := 0;
    repeat
      NAdd(T, A, B);            // T = (A + B) div 2, new A
      NShr(T, 1);
      NMul(B, A);               // B = (B * A)^0.5
      NSqrt(B);
      NSub(A, T);               // A = (A - T)^2 * 2^W
      NSqr(A);
      NShl(A, W);
      Inc(W);
      NSub(D, A);               // D = D - A
      NSwp(A, T);
    until NCmp(B, A) = 0;
    NShr(D, Decimals);
    NDiv(D, R);
    NMul(D, 1000);
    NSqr(R, A);
    NDiv(R, D);
  end;

Wenn man sich an die Schreibweise gewöhnt hat ist alles strikt und konsistent auch wenn man später noch weitere mathematische Funktonen in anderen Units der Bibliothek hinzufügt.
Wollte man das per Operatoren Überladung erreichen das müsste der Compiler viel weitreichendere Features in diesem Bereich zur Verfügung stellen. Der Compiler müsste eben

B^C mod D

erkennen und einen Operator der Form Result = Var1 op1 var2 op3 var3 umsetzen können.

[negaH]

Es gibt einige Crypto Bibliotheken die das denoch versuchen.
Sie definieren bei der Operation A := B^C mod D einen neuen Datentyp, den Modularen Ring. Ein Integer der immer modulo einem anderen Integer gerechnet wird.

ähnlich so:

Delphi-Quellcode:

var
  A: IModuloRing;
  C,B,D: IInteger;
begin
  A.Modulo := D;

  A := C^B;
end;

Nun kann ^ als Operator in A überladen werden, da A nun einen modularen Ring beschreibt rechnet diese Klasse/Record die Exponenation in spezieller Form, eben modular, aus.

Aber auch dieses Konzept wird auf lang oder kurz scheitern, zb. bei Matrizen, Elliptischen Kurven usw.

Gruß Hagen

[termodox]

Ah Menschen, wie kann ich denn die Wurzel ziehen aus dem Dicken Int?

[TurboMagic]

Zur Not mit dem Algorithmus von Herrn.