Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Sonstige Fragen zu Delphi (https://www.delphipraxis.net/19-sonstige-fragen-zu-delphi/)
-   -   Delphi RSA: wie komme ich vom ggt zur vielfachsummendarstellung? (https://www.delphipraxis.net/136700-rsa-wie-komme-ich-vom-ggt-zur-vielfachsummendarstellung.html)

qwertz543221 6. Jul 2009 12:41


RSA: wie komme ich vom ggt zur vielfachsummendarstellung?
 
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 6. Jul 2009 15:39

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
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 :wink: 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 6. Jul 2009 16:47

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
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 6. Jul 2009 17:02

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
Zitat:

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:

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 7. Jul 2009 19:11

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
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 7. Jul 2009 19:50

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
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 7. Jul 2009 22:32

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
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 7. Jul 2009 22:53

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
Zitat:

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 7. Jul 2009 23:38

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
Auf diesen (und den Vorläufer-Thread) mit den verschiedenen vergeblichen Versuchen ein funktionierende ModInverse zu schreiben.

Mithrandir 7. Jul 2009 23:39

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
Achso, ok, das ging nicht so ganz daraus hervor. ;)

Klaus01 8. Jul 2009 08:31

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
Zitat:

Zitat von 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

Guten Morgen gammatester,

danke für das Testen des Codes.

Die Funktion extEuclidian berechnet d und gcd (den größten gemeinsamen Teiler)
und sie arbeitet mit int64, d.h. sie ist nur bedingt für große Zahlen geeignet.

Mit den Beispieldaten aus Beitrag #5 funktioniert sie.

Grüße
Klaus

gammatester 8. Jul 2009 09:37

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
Zitat:

Zitat von Klaus01
Die Funktion extEuclidian berechnet d und gcd (den größten gemeinsamen Teiler) und sie arbeitet mit int64, d.h. sie ist nur bedingt für große Zahlen geeignet.

Mit den Beispieldaten aus Beitrag #5 funktioniert sie.

Also berechnet extEuclidian(e,phi,gcd) doch das modulare Inverse e^-1 mod phi!? Das ist dann doch wohl kein intuitiver Name. (Es war mir noch nie einsichtig, wie jemand viel Zeit mit der Entwicklung von Funktionen verbringen kann, ohne sich die paar Sekunden zu nehmen und hinzuschreiben, was eigentlich gemacht wird).

Mit den Beispieldaten aus Beitrag #5 hast Du einfach nur Glück gehabt. Hier ein ganzes Rudel von falschen Berechnungen, wobei ich ausdrücklich nur immer einen Wert aus #5 geändert habe und nur kleine Werte benutze:
Code:
Richtig (#5)
p=31, q=97, e=23  -> d=1127

Falsch mit Deinem extEuclidian
p=31, q=97, e=17  -> d=5
p=31, q=29, e=23  -> d=2
p=83, q=97, e=23  -> d=4
p=31, q=97, e=3   -> d=1
...

Richtig mit meinem modinverse
p=31, q=97, e=17  -> d=2033
p=31, q=29, e=23  -> d=767
p=83, q=97, e=23  -> d=6503
p=31, q=97, e=3   -> Result=false
Gruß Gammatester

Klaus01 8. Jul 2009 09:47

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
.. danke, schau ich mir heute abend genauer an.

Zur Namensgebung:
Das inverse Element eines Elements a Element ganze Zahlenn* lässt sich mit Hilfe des erweiterten euklidischen Algorithmus berechnen . (Quelle)

Grüße
Klaus

gammatester 8. Jul 2009 10:45

Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
 
Hier eine korrigierte Fassung namens InvModKlaus:

- Zuerst wird das hier unsägliche move entfernt (Pascal kennt schon seit > 20 Jahren die Zuweisung von arrays).

- Dann wird der Bug beseitigt: Wenn das Inverse kleiner 0 ist wird natürlich nicht der andere Bezout-Koeffizient genommen, sondern einfach phi addiert.

- Dann stellen wir fest, daß wir die 1-er Komponenten gar nicht brauchen; wir werfen sie also raus.

- Dann noch ein Kommentar: was wird gemacht, Voraussetzungen, wann ist das Ergebnis gültig

Delphi-Quellcode:
{---------------------------------------------------------------------------}
function InvModKlaus(e,phi: Int64; var gcd: Int64): Int64;
  {-Modulare Inverse mit erweitertem Euklidischen Algorithmus; e, phi > 0;}
  { gcd=gcd(e,phi); result = e^-1 mod phi, nur gültig wenn gcd=1 !!}
var
  u,v,t: array[2..3] of Int64;
  q: Int64;
begin
  u[2] := 0;
  u[3] := phi;
  v[2] := 1;
  v[3] := e;
  while v[3] <> 0 do begin
    q := u[3] div v[3];
    t[2] := u[2] - q * v[2];
    t[3] := u[3] - q * v[3];
    u := v;
    v := t;
  end;
  result := u[2];
  if result<0 then result := result + phi;
  gcd := u[3];
end;


Alle Zeitangaben in WEZ +1. Es ist jetzt 00:13 Uhr.

Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz