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) |
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. |
Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
wikipeida schreibt doch:
Zitat:
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:
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. |
Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
Zitat:
Zitat:
Dies war wohl mein letzter Beitrag hier, da nicht abzusehen ist, daß die Diskussion zu irgendetwas führt. |
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 |
Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
Delphi-Quellcode:
Schau Dir zur folgenden Funktion mal diesen Link an - und auch mal durcharbeiten.
function TRSA.Gcd(n, m: Int64): Int64;
begin if m = 0 then Result := n else Result := Gcd(m, n mod m); end;
Delphi-Quellcode:
Grüße
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; Klaus |
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:
Habe schnell zwei Codeschnipsel für xgcd und modinverse geschrieben, die funktionieren. xgcd und modinverse müssen in StringMatheLib eingefügt werden.
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;
Delphi-Quellcode:
Der folgende Testcode liefert: d=20013004186393, und test = ProduktModulo(e,d,phi) = 1
{-----------------------------------------------------------------------------
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;
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; |
Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
Zitat:
|
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.
|
Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
Achso, ok, das ging nicht so ganz daraus hervor. ;)
|
Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
Zitat:
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 |
Re: RSA: wie komme ich vom ggt zur vielfachsummendarstellun
Zitat:
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:
Gruß Gammatester
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 |
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 |
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