RSA: Privaten Schlüssel schneller berechnen

[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

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

[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

[Dano]

Zitat von negaH:

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.
Gruß Hagen

warum wäre man dann ein gemachter mann? wie sollte er diese formel zu geld machen wenn er eine hätte?
er könnte seine forschungsarbeit puplizieren.... aber es wird ihm keiner geld geben?
(abgesehen vom paar zeitungen die ein interview wollen)

ruhm wäre ihm sicher... aber unter "gemachter man" denke ich auch das geld über den tisch wandert^^

Mfg Dano

PS: sry, bin beim lesen drüber gestolpert... aber erfindungen in der mathematik bringen doch kein geld?