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.

[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.