RSA: wie komme ich vom ggt zur vielfachsummendarstellung?

[gammatester]

Hallo Klaus,

Dein Code ist entweder falsch oder (wie hie leider üblich) nicht richtig beschrieben. Für p = 4523621, q = 5785379, d.h. phi=(p-1)*(q-1)=26170851628360 liefert Dein Code d=4 für d := extEuclidian(e,phi,gcd). Soll das ModInverse sein? Wohlt nicht da 4*17 = 68 <> 1 mod phi ist? Berechnet mit

Delphi-Quellcode:

procedure TForm1.Button2Click(Sender: TObject);
var
  p,q,e,phi,d,gcd: int64;
begin
  p := 4523621;
  q := 5785379;
  phi := (p-1)*(q-1);
  memo1.Lines.Append('phi='+IntToStr(phi));
  e := 17;
  d := extEuclidian(e,phi,gcd);
  memo1.Lines.Append('d='+IntToStr(d));
  memo1.Lines.Append('test='+IntToStr(d*e mod phi));
end;

Habe schnell zwei Codeschnipsel für xgcd und modinverse geschrieben, die funktionieren. xgcd und modinverse müssen in StringMatheLib eingefügt werden.

Delphi-Quellcode:

{-----------------------------------------------------------------------------
  Procedure: TMathe.xgcd
  Author:    W.Ehrhardt
  Date:      07-Jul-2009
  Arguments: u,v: ansistring; var u1,u2,u3: ansistring
  Result:    None
-----------------------------------------------------------------------------}
  procedure TMathe.xgcd(u,v: ansistring; var u1,u2,u3: ansistring);
    {-Extended gcd: calculate  u*u1 + v*u2 = u3 = gcd(u,v) via Knuth's Alg X}
  var
    v1,v3,t1,t3,q: ansistring;
    nu: boolean;
  begin
    { Ref: D.E. Knuth: The Art of computer programming, Volume 2, Seminumerical}
    { Algorithms, 3rd ed., 1998, page 342}

    {Note: the following setup returns 1*0 + 0*0 = 0, for a=b=0! This}
    {is somewhat strange but OK. Knuth's algorithm X gives the same. }
    {usage of u2,v2,t2 suppressed, y = u2 will be = (u3 - a*u1)/b}

    {initialize: (u1,u2,u3) = (1,0,a), (v1,v2,v3) = (0,1,b)}
    if _ImmerNormalisieren then begin
       _Normalisieren(u);
       _Normalisieren(v);
    end;
    nu := IstNegativ(u);
    u1 := '1'; u3 := Absolut(u);
    v1 := '0'; v3 := Absolut(v);

    {loop while v3 != 0}
    while v3<>'0' do begin
      {q = u3/v3}
      q  := Quotient(u3,v3);
      {(t1,t2,t3) = (u1,u2,u3) - (v1,v2,v3)q}
      t1 := Differenz(u1, Produkt(v1,q));
      t3 := Differenz(u3, Produkt(v3,q));
      {(u1,u2,u3) = (v1,v2,v3)}
      u1 := v1;
      u3 := v3;
      {(v1,v2,v3) = (t1,t2,t3)}
      v1 := t1;
      v3 := t3;
    end;

    {make gcd positive}
    if istNegativ(u3) then begin
      Negieren(u1);
      Negieren(u3);
    end;
    if nu then Negieren(u1);

    {calculate u2, here v3=0}
    if v<>'0' then begin
      {u2 = (u3 - u*u1)/v}
      t1 := Produkt(u,u1);
      t3 := Differenz(u3,t1);
      u2 := Quotient(t3,v)
    end
    else u2 := '0';
  end;

{-----------------------------------------------------------------------------
  Procedure: TMathe.modinverse
  Author:    W.Ehrhardt
  Date:      07-Jul-2009
  Arguments: a,b: ansistring; var c: ansistring
  Result:    boolean
-----------------------------------------------------------------------------}
  function TMathe.modinverse(a,b: ansistring; var c: ansistring): boolean;
    {-Calculate c := a^-1 mod b, return true if inverse exists, i.e. gcd(a,b)=1}
  var
    d,y: ansistring;
  begin
    xgcd(a,b,c,y,d);
    if IstNegativ(c) then c := Summe(c,b);
    result := d='1';
  end;

Der folgende Testcode liefert: d=20013004186393, und test = ProduktModulo(e,d,phi) = 1

Delphi-Quellcode:

procedure TForm1.Button3Click(Sender: TObject);
var
 p,q,e,phi,d,gcd,test: ansistring;
begin
  p := '4523621';
  q := '5785379';
  Mathe.Minus1(p);
  Mathe.Minus1(q);
  phi := Mathe.Produkt(p,q);
  e := '17';
  Mathe.modinverse(e,phi,d);
  memo1.Lines.Append('d='+d);
  test := mathe.ProduktModulo(e,d,phi);
  memo1.Lines.Append('test='+test);
end;