Entwickler-Ecke :: Thema anzeigen - RSA - Erweiterter Euklidischer Algorithmus

galaxy2k - Fr 27.02.04 00:53
Titel: RSA - Erweiterter Euklidischer Algorithmus

Ich habe leider mit dem folgenden Algorithmus Probleme in der Hinsicht, dass mir einfach nicht klar wird, wann u0/v0 ihre Werte zugewiesen bekommen. Was rauskommen soll usw. hab ich begriffen und das u0 den privaten Schlüssel ,laut der Formel d = e^-1 1 mod n bzw. u*e + v*n0 = 1, repräsentiert ist auch klar. Nur leider sehe ich vor lauter Bäumen den Wald nicht mehr. Der Algorithmus selbst funktioniert und gibt mir auch den relevanten Wert zurück, nur leider hab ich die bereits erwähnten Verständnisprobleme. Ich hoffe, dass mir hier einer im Forum den Rekursivaufruf näher erläutern kann.

mfg g2k

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

Function TMathe.ggTerw(a,b: int64; var u,v: int64):int64;
  var u0, v0:int64;
begin
  if b = 0 then Begin
    result := a;
    u := 1;
    v := 0;
  End else Begin
    result := ggTerw(b, a mod b, u0, v0);//rekursiv
    u := v0;
    v := u0 - (a div b)*v0;
  End;
end;

function TMathe.invers_mod(e,m: int64): int64;
  var d,v: int64;
begin
  ggTerw(e,m,d,v); //der Funktionswert von ggT wird nicht benötigt
  if d < 0 then d := d + m;
  result := d;
end;

Urba - Fr 27.02.04 01:26

Hallo,

Folgendermaßen :

Deine Funktion :

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

Function TMathe.ggTerw(a,b: int64; var u,v: int64):int64; 
  var u0, v0:int64; 
begin 
  if b = 0 then Begin 
    result := a; 
    u := 1; 
    v := 0; 
  End else Begin 
    result := ggTerw(b, a mod b, u0, v0);//rekursiv 
    u := v0; 
    v := u0 - (a div b)*v0; 
  End; 
end;

Wird die Funktion das erste Mal aufgerufen, dann haben u0 und v0 den Wert 0. Dann hast du aber richtig geschrieben, wann rekursiv gearbeitet wird. Damit werden den Parametern u und v die Werte von u0 und v0 zugewiesen. Somit wird dann im folgenden bei u := 1 usw. mit diesen Werten weitergerechnet.

Urba

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!