RSA: Privaten Schlüssel schneller berechnen

[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