Wie d in diesem RSA-Algorithmus Beispiel zu bestimmen?

Question

Als Teil meines College-Kurses habe ich eine Frage zu lösen bekommen. Es geht um den RSA-Algorithmus.

I gegeben wurden, p = 29, q = 17 und E = 5.

I d zu bestimmen, haben.

So weiß ich, n = 29 x 17 => 493 und phi (n) = 448

So bekomme ich bis zu dem Punkt, wo ich weiß,

5 * d mod 448 = 1 

ich dann dem euklidischen Algorithmus folgen zu

Mit 3 ist der Rest (Quotient) da. In vorherigen Beispielen, in denen der Quotient am Ende 1 war, war es sehr einfach zu lösen, was d war. Allerdings habe ich keine Ahnung, wie es für dieses Beispiel mit dem Rest zu tun ist.

Weiß jemand, wie man das macht? Hilfe wäre sehr willkommen.

Answer 1

Sie haben den erweiterten euklidischen Algorithmus nicht beendet. (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)

Sie sollten (r_i, s_i, t_i) haben:

(448,1,0) => 1*448 + 0*5 = 448 
(5, 0, 1) => 0*448 + 1*5 = 5 
(3, 1, -89) => 1*448 - 89*5 = 3 
(2, -1, 90) => -1*448 + 90*5 = 2 
(1, 2, -179) => 2*448 - 179*5 = 1 

Sie können prüfen, um zu sehen, dass 2*448 - 179*5 = 1, so -179 * 5 = 1 mod 448 oder 269*5 = 1 mod 448, und Ihre Antwort ist d = 269