Dotaz: RSA, vypocet hodnoty d

[Marian Romero]

Zdravim, pro procviceni jsem se rozhodl, ze si implementuji algoritmus RSA. Zasekl jsem vsak na vypoctu hodnoty d, coz je bod 5 viz zde:

http://en.wikipedia.org/wiki/RSA_%28algorithm%29#Key_generation

Docetl jsem se, ze d mohu vypocitet prostrednictvim rozsireneho euklidova algoritmu (http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm). Neni mi na tom ale jasne par veci.

1) Budu mit funkci pocitajici rosireny eukl. alg. takto: egcd(int a, int b). Co zvolit za ty parametry a a b kdyz budu chtit vypocist d v ramci RSA?

2) Druha vec co mi neni jasna: ten rozsireny eukl. alg. vraci tri hodnoty - GCD, x a y tak kterou z techto hodnot ja pouziju jako to moje d?

Odpovědi

[Marek]

Je to tam presne napisane - d = e^-1 mod phi(n), resp. d.e = 1 mod phi(n).

Plati veta, ak d = nsd(a,b), tak existuju cele cisla A, B take, ze d = a.A + b . B. Rozsireny Euklidov algoritmus je algoritmus, ktory okrem hodnoty d - najvacsieho spolocneho delitela cisel a, b - pocita aj koeficienty A, B.

Kedze e sa voli nesudelitelne s phi(n), t.j. 1 = nsd(e, phi(n)), tak pouzitim rozsireneho Euklidovho algoritmu dostaneme koeficienty A, B take , ze e . A + B . phi(n) = d = 1. Potom staci uz len poslednu rovnost zobrat modulo phi(n), clen B. phi(n) vypadne a e . A = 1 mod phi(n). Potom d = A mod phi(n).

[Filip Jirsák]

1, 2, 3 To je zase nějaký domácí úkol? Nechcete to raději řešit v jedné diskusi místo ve třech?