Как решить задачу с открытым ключом? Алиса поссорилась с Бобом и решила использовать при переписке с ним ненадежный ключ шифрования. Она отправила ему свой открытый ключ: 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 = 275361343
p = 17677
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 n
m = 42666716^110135893 mod 275361343
m = 28251133

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