Для кругозора, как работает RSA?

Question

[Epic18]

Помогите понять некоторые моменты криптоалгоритма RSA.
Каким образом тут вычисляется секретная экспонента, выше в теории написано что это мультипликативно обратная операции mod, не могли бы привести пример, и откуда там появился коэффициент к, выше в теории о нем не говорится.

Answer 1

[galaxy]

откуда там появился коэффициент к

Подобрался методом научного тыка.

Мультипликативно обратный элемент d по модулю phi(n) означает e*d = 1 mod phi(n), т.е. e*d = k*phi(n) + 1, для некоторого целого k. Нужно подобрать k, чтобы правая часть последнего равенства без остатка делилась на e

Comments

[Epic18]

Интуитивно не понятно как число d помогает при дешифровке
c = m^e mod n
m = c^d mod n

[galaxy]

Epic18, а как вы без d вообще собираетесь что-то расшифровать?

[Epic18]

galaxy, я не собираюсь расшифровать без d ничего, мне не понятно взаимосвязь как число (сообщение) m переходит в другое число и потом через операцию возведения в степень d и мод она возвращает искомое m
интуитивно не понятно

[galaxy]

Epic18, ну тут надо немножечко с математикой разобраться (кольца вычетов и пр). Для начала хотя бы: https://ru.wikipedia.org/wiki/RSA#%D0%9A%D0%BE%D1%...