RSA: Privaten Schlüssel schneller berechnen

[gammatester]

Zitat von Micha88:

Also funktionieren tut das alles nicht so recht.

Wie soll's es auch, wenn Du planlos einen normalen GGT statt eines erweiterten GGT zur Berechnung des modularen Inversen einsetzt. Versuchs mal mit Bjoerks GreatestCommonDivisorAdvanced.

[Bjoerk]

Zitat von Micha88:

Vielen Dank für diese Beschreibung, Hagen. Sehr gut verständlich.


Also funktionieren tut das alles nicht so recht.

Delphi-Quellcode:

uses IsPrimeHRUnit {DEC 5.2}
// ...

var FE, FD, FN, FM, FP, FQ: Int64;

function GreatestCommonDivisor(a, b: Int64): Int64;
VAR
 r: INTEGER;
begin
 if b = 0 then
  begin
   result := 0;
   exit;
  end;

 while b > 0 do
  begin
   r := a mod b;
   a := b;
   b := r;
  end;

 result := a;
end;

function InversMod(a, b: Int64): Int64;
var
 V: Int64;
begin
 V := GreatestCommonDivisor(a, b);
 if result < 0 then
  result := result + b;
end;

procedure FindD(const N, E: Int64); // get the private Key D
var
 P, Q, M: Int64;
begin
 FE := 0;
 FD := 0;
 FN := 0;
 FM := 0;
 FP := 0;
 FQ := 0;
 P := 2;
 while P < N do
  begin
   if IsPrime(P) then
    begin
     Q := N div P;
     if IsPrime(Q) then
      begin
       if P * Q = N then
        begin
         M := (P - 1) * (Q - 1);
         if GreatestCommonDivisor(M, E) = 1 then
          begin
           FD := InversMod(E, M);
           FE := E;
           FN := N;
           FM := M;
           FP := P;
           FQ := Q;
           Break;
          end;
        end;
      end;
    end;
   P := P + 1;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
 FindD(StrToInt(Edit1.Text), StrToInt(Edit2.Text));

 // Alles ist '0'
 Label3.Caption := IntToStr(FE);
 Label4.Caption := IntToStr(FN);
 Label5.Caption := IntToStr(FM);
 Label6.Caption := IntToStr(FQ);
end;

Also, Copy and Paste Fähigkeiten hab' ich jetzt einfach mal vorausgesetzt...

Edit: Die while Schleife braucht übrigens nur bis <= N div 2 zu laufen

[Micha88]

Was bringt mir denn aber FE, FN, FM und FQ. Wie berechnet man daraus den Private Key?

[gammatester]

Zitat von Micha88:

Was bringt mir denn aber FE, FN, FM und FQ. Wie berechnet man daraus den Private Key?

Das steht doch da:

Delphi-Quellcode:

  FD := InversMod(E, M);
  FN := N;

Das Paar (N,D) bzw. (FN,FD) ist der private Schlüssel! Vielleicht solltest Du Dich mal mit den Grundlagen vertraut machen.

[Bjoerk]

Was auch ganz interessant ist, daß P und Q nicht unbedingt Primzahlen sein müssen. Dann muß man aber vorher auf Plausibilität prüfen, d.h. für alle zu verschlüsselnden I muß die Bedingung I = Decrypt(Encrypt(I)) erfüllt sein.

P: 190
Q: 129
N : 24510
M: 24192
E: 14417
D: 11825

Für I im Bereich 1..255 getestet.

[negaH]

Zitat von Bjoerk:

Was auch ganz interessant ist, daß P und Q nicht unbedingt Primzahlen sein müssen. Dann muß man aber vorher auf Plausibilität prüfen, d.h. für alle zu verschlüsselnden I muß die Bedingung I = Decrypt(Encrypt(I)) erfüllt sein.

Diese Annahme ist korrekt und falsch zugleich. Mathem. kann man RSA auch mit zusammengesetzten Zahlen machen das wäre dann ein RSA dessen N aus mehr als 2 Primzahlen besteht. Das ist aber kryptographisch nur dann vergleichbar sicher zu einem RSA Modul aus 2 Primzahlen wenn alle Primzahlen so groß sind wie die 2 Primzahlen. Dh. ein 1024 Bit RSA Schlüssel besteht aus zwei Primnzahlen a 512 Bit. Nehmen wir mal an wir lösen diese Forderung bischen auf und nehmen eine 1020 Bit Primzahl und eine 4 Bit Primzahl. Jeder kann sich ausrechnen wie lange nun die Suche bei der Faktorisierung dieses N nach dieser 4 Bit Primzahl dauert. Kryptographsich ist das also ziemlicher Blödsinn es so zu machen. Falls aber N zb. 2048 Bit groß wäre und das Produkt aus 4 Primzahlen a 512 Bit ist dann wäre dieser RSA fast so sicher wie ein 2048 Bit Schlüssel der aus 2x 512Bit Primzahlen bestünde.

Gammatester hat s schon korrekt angesprochen: asymmertische Kryptoverfahren sind sehr anfällig für Designfehler. Weit mehr anfällig als symmetrische Verfahren wie AES, SHA1 usw. Denn selbst bei der Wahl der zB. beiden 512 Bit Primzahlen eines 1024 RSA Schlüssels muß man höllisch aufpassen. Die Primzahlen dürfen von keiner speziellen Form sein, bzw. wenn diese Formk von spezieller Natur ist dann muß es eine sein die nachweislich sicher ist, zB. sogenannte Safe primes = Sophie Germain Primzahlen wären solche Kandidaten. Deren Nutzen im Vergleich zu guten industriellen Primzahlen beim RSA aber sehr gering ist. Dem gegenüber steht der Aufwand solche Primzahlen zu erzeugen.

Aber gerade diese Schlüsselerzeugung ist es die man so manipulieren kann das man einen verdeckten Kanal in das public Modul N einbauen kann. Dabei gilt das dieser verdeckte Kanal selber geschützt wird durch das Faktorisierungsproblem. Dh. der "Angreifer" der einem solchen Schlüssel unterjubeln kann hat die Chance sehr effeizient aus einem solchen public Modul N die Faktorisation zu berechnen. Ich selber habe dazu den praktischen Beweis angetreten. Fazit: traue niemals einem privatem RSA Schlüssel den du selber nicht berechnet hast und bei dem die Art&Weise der Erzeugung der benutzten Primzahlen nicht bekannt und nicht verifizierbar ist. Das betrifft jede Technologie wie SmartCards oder komplexe Cryptobibliotheken ohne Sourcen wie das MS CryptoAPI oder die erzeugten Schlüssel eines TrustCenters für dessen Kunden.

Gruß hagen

[Bjoerk]

Du kennst dich da mit Sicherheit besser aus als ich, ein Vorteil dabei ist m. E. jedoch nicht von der Hand zu weisen: Es gibt dann mehrere Möglichkeiten, aus denen sich N zusammensetzen kann, was den Hackeraufwand erheblich verlängern dürfte.

[negaH]

Zitat von Bjoerk:

Du kennst dich da mit Sicherheit besser aus als ich, ein Vorteil dabei ist m. E. jedoch nicht von der Hand zu weisen: Es gibt dann mehrere Möglichkeiten, aus denen sich N zusammensetzen kann, was den Hackeraufwand erheblich verlängern dürfte.

Ne eben nicht, das Gegenteil wäre der Fall. Je zusammengestzter N ist desto kleiner werden seine Primzahlpotenzen der Faktorisation und das würde bedeuten das umgekehrt exponentiell die Geschwindigkeit des Knackens wächst. Es erleichtert also das Knakcen von RSA da es gerade an dem Punkt wodurch RSA erst sicher wird eine Schwäche einbaut.

Es gibt/gab Versuche mit RSA in dieser Richtung weil man damals wollte das die RSA Operationen schneller ablaufen. Das ist auch der Fall da man mit solchen RSA Schlüssel und dem CRT (Chinese Remainder Theorem) besonders die Entschlüsselung beschleunigen kann. Bei RSA mit 2 Primzahlen im N kann man mit dem CRT (Garner Algorithmus) die Entschlüsselung um Faktor 4 beschleunigen. Das steigert sich je mehr Primzahlen man im Modul N benutzt.

Und es gibt tatsächlich Algorithmen die die sich ergebenden Schwächen bei der Benutzung vom mehr als 2 Primzahlen so ausgleichen können das dieser RSA Schlüssel nicht ganz so unsicher ist als wenn man wahlfrei mit mehr als 2 Primzahlen arbeitet. Denoch sind solche Schlüssel eben weniger stark als diejenigen die mit 2 etwa gleichgroßen, zufällig gewählten Primzahlen arbeiten. Da die Rechentechnik aber fortgeschiritten ist, der Schlüsselerzeugungprozess offline und nicht zeitkritisch ist, man heute ohne Probleme im Millisekundenbereich 512 Bit Primzahlen erzeugen kann, sind diese speziellen RSA Varianten überflüssig geworden.

Gruß hagen

[Bjoerk]

Okay. Aber mal was anderes. Wenn man mit mehr als 2 Primzahlen arbeiten möchte, ist das Procedere dann analog, also N=P*Q*R M:=(P-1)*(Q-1)*(R-1) usw. ?

[gammatester]

Der Standard RFC 3447 - PKCS #1: RSA Encryption Version 2.1 (Abschnitt 3.2) nimmt hier die Carmichaelfunktion M = lambda(N), wobei in Deinem Fall, wenn P,Q,R paarweise verschiedene Primzahlen sind, lambda(N) = LCM(P-1,Q-1,R-1) das kleinste gemeinsame Vielfache ist.