Как расшифровать шифрование RSA?

Question

Мне задали вопрос:

"Расшифруйте это сообщение, используя RSA: 072 062 120 129 (Подсказка: вам нужно будет преобразовать ваш окончательный ответ из ASCII в простой текст. Открытый ключ, используемый для шифрованиясообщение было (n, e) = (143, 7). "

Я понятия не имею, как его расшифровать, и это единственная информация, которая нам была предоставлена. Однако я знаю, чтоp и q равны 13 и 11, что можно найти, найдя 2 простых числа, которые умножаются на n.

Кто-нибудь знает, как расшифровать это?

Заранее спасибо, это было любезноподавляющий.

Answer 1

Вы можете использовать статью из Википедии в качестве руководства.

Из p и q вы можете вычислить λ (n):

λ (n) = lcm (p-1, q-1) = lcm (12, 10) =60

Как только вы знаете λ (n), вы можете использовать его для вычисления d, мультипликативной обратной величины e по модулю λ (n):

d = e⁻¹ (mod λ(n))

По сути это означает нахождение натурального числа d, такого что d * e = 1 (mod 60).

Это делает следующий фрагмент кода Python:

d = next(d for d in range(60) if d*7 % 60 == 1)

Значение d равно 43.

Получив d, мы можем использовать его для расшифровки отдельных номеров сообщения:

decrypted_ascii = [(x**d) % 143 for x in [72, 62, 120, 129]]
decrypted_text = ''.join(chr(x) for x in decrypted_ascii)

Расшифрованный текст: Text.