Writeup Веселый RSA [Writeup]

[M4x]

Без лишних предисловий перейдем к делу.

У нас есть три шифртекста, которые на самом деле представляют одно и то же сообщение. Подсказка намекает на то, что Боб не слишком хорошо разбирается в RSA и допустил серьезную ошибку при шифровании. Мы видим, что вместо стандартной экспоненты e = 65537 он использовал значения 5, 7 и 13. А модули n1, n2 и n3 такие маленькие, что их легко разложить на множители. Это можно назвать критической уязвимостью.

Чтобы решить эту задачку тем способом, который я предлагаю, вам потребуется хорошее знание Python.

Если мы возьмем первое сообщение и попытаемся вычислить приватную экспоненту d, то у нас ничего не выйдет:

>>> e1 = 5
>>> p1 = 181
>>> q1 = 331
>>> n1 = 181 * 331  # 59911
>>> phi_n1 = (p1 - 1) * (q1 - 1)
>>> d = pow(e1, -1, phi_n1)

# Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: base is not invertible for the given modulus

На простом языке это означает, что Боб допустил фатальную ошибку в процессе шифрования.

Пробуем второе сообщение — и снова та же история:

>>> e2 = 7
>>> p2 = 449
>>> q2 = 809
>>> n2 = 449 * 809  # 363241
>>> phi_n2 = (p2 - 1) * (q2 - 1)
>>> d = pow(e2, -1, phi_n2)

# Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: base is not invertible for the given modulus

Но вот третье сообщение, по-видимому, зашифровали правильно, и мы можем вычислить d:

>>> e3 = 13
>>> p3 = 647
>>> q3 = 727
>>> n3 = 647 * 727  # 470369
>>> phi_n3 = (p3 - 1) * (q3 - 1)
>>> d = pow(e3, -1, phi_n3)

Теперь, когда у нас есть d, расшифровать флаг — проще простого:

>>> С3 = 76794
>>> message = pow(С3, d, n3)

В итоге мы получаем трехзначное число, которое, разумеется, я вам не покажу, чтобы вы не жульничали, а решили таск самостоятельно и научились чему-нибудь новому.

Вернемся к условию задачки:

Боб шифрует для трех сторон одно и то же сообщение с помощью RSA.
Узнайте сообщение, отправленное Бобом. Во флаге укажите SHA256 от сообщения.

Нас просят указать SHA256 от расшифрованного сообщения. Это делается очень просто:

>>> from hashlib import sha256
>>> result = sha256(str(message).encode()).hexdigest()

Получившуюся строку оборачиваем в CODEBY и сдаем флаг.