RSA: Privaten Schlüssel schneller berechnen

[Bjoerk]

Zitat von NamenLozer:

Zitat von Micha88:

Leider geht aus diesem Thread nicht hervor, wie man den private key mit Hilfe des public keys findet.

Geht das überhaupt?

Ich bin wirklich kein Krypto-Experte, aber eins weiß ich mit Sicherheit: Man kann den Private Key nicht aus dem Public Key errechnen, denn das ist ja gerade der Sinn der Sache.

Das ist leider nicht richtig.

RSA-Encryption:
2 Prime P, Q
P <> Q
N = P*Q
M = (P-1)*(Q-1)
Find an E and a D so that is:
S * M + 1 = E * D, E <> D, E relatively prime to M, D 1..M, E 1..M, S > 0
Encrypt: J = I^E mod N, I 0..N
Decrypt: I = J^D mod N

N, E = Public
M, P, Q, D = Private

Der Private Schlüssel D lässt sich sogar direkt aus N und E berechnen.
Guckst du hier:

Delphi-Quellcode:

procedure TRSAEncryption.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 IsPrimeNumber(P) then
    begin
      Q:= N div P;
      if IsPrimeNumber(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;

Fazit: Der einzige Schutz, den man bei der RSA Verschlüsselung hat, ist, das bei großen Zahlen, empfohlen sind 155 Stellen (int512), diese Procedure Jahre dauert. Für Zahlen im int64 Bereich ist die RSA Verschlüsselung nicht geeignet.

[Bummi]

Dann sind wir alle jetzt beruhigter...

[negaH]

Zitat von Bjoerk:

Das ist leider nicht richtig.

Leider ist das was du als Beispiel bringst ebenfalls nicht richtig. Du berechnest nicht direkt aus dem öffentlichen Schlüssel den privaten sondern du testest alle Kandidaten durch bis es stimmt. Das ist ein Unterschied.

Man kann N faktorisieren und das wird letzendlich, nach meinem Wissenstand, immer ein Such-Algorithmus sein der letzendlich per Trial&Error funktioniert.

Ich kenne kein praktisches Verfahren um eine zusammengesetzte Zahl, wie beim RSA notwendig, direkt in ihre Primzahlfaktoren zu zerlegen.

Gruß Hagen

[Bjoerk]

Doch, da N das Produkt von 2 Primzahlen ist, gibt es genau eine Möglichkeit. Und D = InversMod(E, M)

[Micha88]

Ich bekomme es fast kompiliert.

Nur findet er InversMod() nicht.
Gibt es dazu einen Code? Möchte nur ungern eine komplette Komponente nur für eine Funktion installieren.

[Bjoerk]

Delphi-Quellcode:

function GreatestCommonDivisorAdvanced
  (A, B: int64; var U, V: int64): int64;
var
  U0, V0: int64;
begin
  if B = 0 then
  begin
    Result:= A;
    U:= 1;
    V:= 0;
  end
  else
  begin
    Result:= GreatestCommonDivisorAdvanced(B, A mod B, U0, V0);
    U:= V0;
    V:= U0-(A div B)*V0;
  end;
end;

function InversMod(A, B: int64): int64;
var
  V: int64;
begin
  GreatestCommonDivisorAdvanced(A, B, Result, V);
  if Result < 0 then Result:= Result+B;
end;

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

[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

[negaH]

Zitat von Bjoerk:

Doch, da N das Produkt von 2 Primzahlen ist, gibt es genau eine Möglichkeit. Und D = InversMod(E, M)

ich denke du verstehst mich falsch.

Du berechnest nicht P,Q direkt aus N sondern du gehst alle Primzahlen per Brute Force durch, also Trial & Error. Wenn es eine mathm. Formel gäbe mit der man aus N direkt dessen Primzahlfaktorization berechnen könnte dann wärste jetzt ein gemachter Mann.

Der RSA Schlüssel, bzw. dessen Sicherheit besteht nur aus P*Q=N wobei P,Q zur privaten Schlüsselform und N zur öffentlichen Schlüsselform zählen. Mathematisch gibt es keinen Unterschied von N zu P*Q da ja N = P*Q ist. Deshalb sollte man von Formen des gleichen RSA Schlüssels reden, da erst die gelieferte Form, also N oder eben P,Q entscheidet wie schnell man die einzelnen RSA Operationen durchführen kann.

D ergibt sich direkt aus E dem öffentlichen Exponenten wenn man P,Q kennt. Du kannst D, privater Exponent, nur dann berechnen wenn du vorher N in P,Q faktorisiert hast. Und es gibt keinen Faktorizierungsalgo. der aus N direkt P,Q berechnen kann. Alle Algos. müssen per Trial&Error arbeiten. Somit kann man einen Algorithmus programmieren der zwar iterativ sich der korrekten Lösung durch Versuche immer weiter annähert, aber es gibt keinen Algorithmus der aus einer beliebigen zusammengesetzen Zahl direkt deren Faktorisation berechnen kann. Und dein Beispiel faktoriziert noch nichtmal N sondern geht alle Primzahlen solange durch bis er durch Produktbildung ein gleiches Modul N erzeugt hat.

Und exakt das es so ist bedeutet kryptographische berechenbare Sicherheit beim RSA Verfahren.

Gut lange Rede wenig Inhalt, letztendlich geile ich mich nur an der falschen Wortwahl auf. Man kann sich nun streiten ob "berechnen" das ist was dein Algo. da macht, ich sehe es bischen strikter in der Wortwahl.

Gruß Hagen