Как решить задачу с открытым ключом?

Question

[danil_ka51]

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

Comments

[Rsa97]

Для начала поймать Алису и/или Боба и узнать, какой алгоритм шифрования они использовали в переписке.

[mayton2019]

Это какая-то классическая задачка на тему разложения чисел на простые множители. Я так понимаю что ей долбят по мозгам всем учащимся.

Хотя щас вобщем-то не только RSA но и эллиптические формулы могут использоваться. Вообще - было-бы вежливее если-бы автор дал больше контекста.

[danil_ka51]

mayton2019, Это и есть вся задача.

[unk1nD000]

danil_ka51, это очень странная задача, попробуйте поискать
про RSA, ищите что-то типо RSA {e, n} decrypt
cs.bc.edu/~straubin/crypto-2014/LecturePK.pdf

[Dimonchik]

и узнать,

терморектальным криптоанализом

какой алгоритм

[Кот Абсолютный]

Dimonchik, Ну зачем же так сразу? Предлагаю Бобу поймать Алису и заняться с ней обычной любовью пока Алиса Боба не простит :)

[Модератор]

Покажите свою попытку решения проблемы, иначе это не вопрос, а задание. См.п.5.12 правил.

[AlexVWill]

Who the fuck is Alice?
https://www.youtube.com/watch?v=CsrfovOPcjk

[shurshur]

275361343=11719×23497 - два простых. Это похоже на RSA. Так что можно попробовать сделать обратный ключ и расшифровать.

[danil_ka51]

shurshur, Обратный - то есть приватный?

[danil_ka51]

Rsa97, Что значит поймать?) Я не очень в этом разбираюсь

[shurshur]

danil_ka51, да, в алгоритме RSA написано, как получить его, зная разложение на простые множители.

[danil_ka51]

shurshur, я его нашел: d = 165195677. Но если подставить это число в формулу для расшифровки, то есть будет 42666716 в степени 165195677 mod 275361343. Как такую степень посчитать я не знаю даже

[shurshur]

danil_ka51, это как раз несложно. Раскладываем 165195677 в бинарное представление: 1001110110001010111110011101, затем начинаем возводить 42666716 в квадрат по модулю 275361343 и если у нас в бинарном представлении есть единица на нужной позиции то умножаем это текущее число по модулю. Тут в 64-битные int всё прекрасно уложится, поскольку любую операцию мы берём по модулю. Пояснение алгоритма на примере возведения в степень 19: https://www.HostMath.com/Show.aspx?Code=p%3D19%3D1...

В конце концов, можно у wolframalpha спросить ответ.

[danil_ka51]

shurshur, Ответ нашел, спасибо за помощь