Как решить задачу с открытым ключом? Алиса поссорилась с Бобом и решила использовать при переписке с ним ненадежный ключ шифрования. Она отправила ему свой открытый ключ: e = 5, n = 275361343. Боб, конечно, зашифровал его открытый текст и получил следующее: 42666716. Но он решил не отправлять ничего Алисе, так как понял, что она ненадежный собеседник. Какой же все-таки был открытый текст Боба?

Предыдущий
вопрос Следующий
вопрос

Для решения задачи с открытым ключом необходимо воспользоваться алгоритмом RSA.

Зная открытый ключ Алисы (e = 5, n = 275361343) и зашифрованный текст (c = 42666716), можно найти закрытый ключ. Для этого необходимо вычислить значение функции Эйлера от числа n
φ(n) = (p-1)(q-1), где n = p * q (p и q - простые числа)

Сначала найдем p и q
p * q = 27536134
p = 1767
q = 15583

Теперь найдем значение функции Эйлера
φ(275361343) = (17677-1)(15583-1) = 275339732

Далее необходимо найти закрытый ключ d, обратно сравнимый с e по модулю функции Эйлера
d = e^-1 mod φ(n)

d = 5^-1 mod 275339732 = 110135893

Теперь, используя закрытый ключ (d = 110135893), можно расшифровать зашифрованный текст
m = c^d mod
m = 42666716^110135893 mod 27536134
m = 28251133

Таким образом, открытый текст, который Боб зашифровал и отправил, равен 28251133.