RSA: wie komme ich vom ggt zur vielfachsummendarstellung?

[qwertz543221]

hallo ich habe folgendes problem

Delphi-Quellcode:

function modinvers(e,n:ansistring):ansistring;
        var de,k:ansistring;
        begin
        k:='1';
        de:='1';
        while mathe.Modulo(de,e)<>'0'  do
        begin
        de:=mathe.produkt(k,phi);
        mathe.Plus1(de);
        mathe.Plus1(k);
        end;
        result:=mathe.Quotient(de,e);
       if mathe.ProduktModulo(result,e,n)<>'1'
          then showmessage('invmod falsch');  
        end;

das klappt soweit auch schon, nur - es ist einfach zu lngsam.
Daher hatte ich vor die "echte" berechnungsmethode zu benutzen, bei der habe ich leider einige probleme.

1)wähle p und q als primzahlen
2) n:=pq;
3) phi=(p-1)*(q-1)
4)wähle d mit ed mod phi=1
=> ed+k*phi=1=ggt(e,phi)

und hier hab ich probleme:

den einfachen euklidischen algorithmus kann ich durchführen, nur dann soll das ganze rückwärts wieder zur Vielfachsummendarstellung führen - dies ist der teil, der mir probleme bereitet.

(im moment noch auf dem papier - das coding folgt, sobald ich weiß wie ich vom ggt des einfachen euklidischen algo zur vielfachsummendarstellung komme, um das d zu berechnen. genau das ist mein problem)



beispiel:
p=11, q=13
n=143
phi=120
e=23

ed+k phi=1=ggt(e,phi)

120= 5*23+5
23= 4* 5+3
5= 1* 3+2
3= 1* 2+1
2= 1* 1+1 =>Ergebnis=1
1= 1* 1+0 =>Abbruchbedingung


Nur wie komme ich jetzt zur darstellung des ergebnisses als vielfachsumme, damit ich d ausrechnen kann? - und wie kann man das effizient und schnell (vom algorithmus her) in delphi beschreiben?

Danke für eure tips (ich hoffe ich hab nichts durcheinandergebracht, bisher hab ich das ganze wie oben durch den delphi code angegeben ausgerechnet)

[gammatester]

Willst Du es diesmal ernsthaft wissen und auf Vorschläge eingehen, oder soll's wieder so laufen wie im Thread Chinesischer Restsatz?

Einen Tip schon mal kostenlos Dein modinvers beschreibt immer noch nicht, was Du eigentlich machen willst. In Deinem neuen Beitrag willst Du modulo phi invertieren, testest aber ob das Produkt = 1 mod n ist!

Zum dritten Mal: Wirf n als Parameter von modinvers raus, und wirf endlich das globale phi raus. Schreibe eine function modinvers(a,b: ansistring): ansistring; mit der Eigenschaft modinvers(a,b)*a = 1 mod b.

Wie Du das machen kannst, ist zB in dem Link zum BUGs Beitrag 2 des Chinesischen Threads beschrieben.

Wenn Du allerdings weiterhin alle Hilfsversuche ignorierst, wird Dir wohl kaum einer mehr helfen wollen.

[qwertz543221]

wikipeida schreibt doch:

Zitat:

Wir wählen p und q
Der RSA-Modul ist n:=pq .
Die eulersche φ-Funktion nimmt damit den Wert (p-1) (q-1) an.
Die Zahl e muss zu phi teilerfremd sein. Damit bilden e und N den öffentlichen Schlüssel.
Berechnung der Inversen zu e:
Es gilt:
e*d+k*phi=ggt(e,phi)=1.
d ist der private Schlüssel, während k nicht weiter benötigt wird.

so soll das laufen
und dafür brauch ich die vielfachsummendarstellung, die sich an den euklidischen algorithmus anschließt, nur weiß ich nicht mehr wie das geht - du weißt ja ich hatte es anders probiert, weil ich das hier eben nicht hinbekam.

und was die parameter in der funtion angeht - sollte dem programm doch egal sein wie die im funktionskopf heißen, hauptsache er bekommt die richtigen zum rechnen.


Hm noch was

Zitat:

Willst Du es diesmal ernsthaft wissen und auf Vorschläge eingehen, oder soll's wieder so laufen wie im Thread Chinesischer Restsatz?

ich hab darauf übrigens nie eine antwort erhalten, auch wenn ich jetzt die bisherigen fehler geändert habe, weiß ich immmer noch nicht wie der chin RS richtig funktioniert(sbsegeshen von der imlpementierungh).

Man hatte mir damals gesagt, ich solle mich mit dem erweiterten euklid. algo. beschäftigen
soweit so gut, nur brauch ich den noch nicht zu benutzten, wenn ich nicht mehr weiß wie das mit der eben angesprochenen vielfachsummendarstellung gehen soll.

und genau dafür hatte ich hier um erklärungen gebeten.

[gammatester]

Zitat von qwertz543221:

die vielfachsummendarstellung, die sich an den euklidischen algorithmus anschließt

Nein, tut sie eben sinnvollerweise nicht. Sie wird zusammen mit dem ggt im Erweiterten Euklidischen Algorithmus berechnet (und nicht mit Deiner Bruteforcemethode: nimm den ggt und probier der Reihe nach alle Möglichkeiten)

Zitat von qwertz543221:

und was die parameter in der funtion angeht - sollte dem programm doch egal sein wie die im funktionskop heißen, hauptsache er bekommt die richtigen zum rechnen.

Richtig, aber in der Funktion sollten auch nur die Parameter aus dem Funktionskopf und keine globalen Variablen verwendet werden.

Dies war wohl mein letzter Beitrag hier, da nicht abzusehen ist, daß die Diskussion zu irgendetwas führt.

[qwertz543221]

ok ich hab hier mal ein schriftliches beispiel gerechnet, nur wie kann man das
in einen algorithmus packen? - d.h. wie lasse ich den algorithmus die umformungen bis zur vielfachsummendarstellung machen?
- so wie man es auf papier macht (s.o.) geht das kaum, oder?


Beispiel
p=31,q=97
n=3007
phi=2880
e=23

ed+k*phi=1=ggt(23,2880)

2880=125*23+ 5
23= 4* 5+ 3
5= 1* 3+ 2
3= 1* 2+ 1(**)
1= 1* 1+ 0


(**)
1=2-1*1

1=2-1(3-1*2)=2*2-1*3

1=2(5-1*3)-1(23-4*5)
=2*5 - 2*3 - 1*23 + 4*5
=6*5 - 2*3 - 1*23

1=2(5 - 1*3) - 1*3
=2*5 - 3*3

1=2(2880 - 125*23) - 3(23 - 4*5)
=2*2880 - 250*23 - 3*23 + 12*5
=2*2880 - 253*23 + 12*5

1=2*2880 - 250*23 - 3*23 + 12(2880 - 125*23)

1=14*2880 - 1753*23
1= k*phi + d*e
1=1 ok


da d<0:
d=-1753 + phi (vielfaches von phi)
d=1127


=>e=23,d=1127,n=3007

[Klaus01]

Delphi-Quellcode:

function TRSA.Gcd(n, m: Int64): Int64;
begin
  if m = 0 then
    Result := n
  else
    Result := Gcd(m, n mod m);
end;

Schau Dir zur folgenden Funktion mal diesen Link an - und auch mal durcharbeiten.

Delphi-Quellcode:

function TRSA.extEuclidian(e,phi:Int64;var gcd:Int64):Int64;
var
  u,v,t : Array[1..3] of Int64;
  q : Int64;
  i : Byte;

begin
  u[1] := 1;
  u[2] := 0;
  u[3] := phi;
  v[1] := 0;
  v[2] := 1;
  v[3] := e;
  while v[3] <> 0 do
    begin
      q := u[3] div v[3];
      for i:=1 to 3 do
        begin
          t[i] := u[i] - q * v[i];
        end;
      move(v[1],u[1],3*sizeOf(Int64));
      move(t[1],v[1],3*sizeOf(Int64))
    end;

  result := u[2];
  if u[2] < 0 then
    result := u[1];
  gcd := u[3];
end;

Grüße
Klaus

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

[Mithrandir]

Zitat von gammatester:

[...](wie hier leider üblich) nicht richtig beschrieben.

Von Einem (oder meinetwegen einigen) auf das ganze Forum zu schließen, halte ich für gewagt und ungerecht. Oder bezieht sich das nur auf diesen Thread?

[gammatester]

Auf diesen (und den Vorläufer-Thread) mit den verschiedenen vergeblichen Versuchen ein funktionierende ModInverse zu schreiben.

[Mithrandir]

Achso, ok, das ging nicht so ganz daraus hervor.