Dla RSA, jak obliczyć tajny wykładnik?

Question

Dla RSA, jak obliczyć tajny wykładnik?

Biorąc pod uwagę p i q dwie liczby pierwsze i phi = (p-1) (q-1), a publiczny wykładnik (0x10001), jak uzyskać tajny wykładnik "d"?

Czytałem, że mam do zrobienia: d = e ^-1 mod phi użyciu modular inversion i euclidean equation ale nie mogę zrozumieć, jak powyższe mapy formuła albo do a ^-1 ≡ x mod m formuła na modularnej stronie wiki inwersyjnej lub jak odwzorowuje równanie euklidesowe GCD.

Czy ktoś może pomóc proszę, okrzyki

Answer 1

Można użyć extended Euclidean algorithm rozwiązać za d w kongruencji

de = 1 mod phi(m) 

Dla szyfrowania RSA, e jest kluczem szyfrowania d jest kluczem deszyfrowania, a szyfrowanie i deszyfrowanie są wykonywane przez potęgowanie mod m. Jeśli zaszyfrować wiadomość a z kluczem e, a następnie odszyfrować go za pomocą klawisza d, można obliczyć (a ^e) ^d = a ^de mod m. Ale od de = 1 mod phi(m), Euler's totient theorem mówi nam, że ^de przystaje do mod m - innymi słowy, wrócisz oryginalny a.

Nie są znane skuteczne sposoby, aby uzyskać klucz deszyfrujący d znając tylko szyfrowanie klucza e i moduł m, bez znajomości faktoryzacji m = pq, więc szyfrowania RSA jest uważane za bezpieczne.