RSA: wie komme ich vom ggt zur vielfachsummendarstellung?

[Klaus01]

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]

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]

.. 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]

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;