#cryptography #rsa #prime-factoring
#криптография #rsa #простое разложение на множители
Вопрос:
RSAcryptosystem имеет открытый ключ n = 18721 и e = 25. Сообщения шифруются зашифрованными по одной букве за раз, преобразуя буквы в цифры на A = 2, B = 3 c _ 27. Оскар перехватывает сообщение «365, 18242, 4845, 18242, 17173, 16;134:»» от Алисы к Бобу.
(la) Расшифровать сообщение путем разложения n.
(lb) Расшифруйте сообщение, предполагая, что вы не можете разложить n на множители.
может ли какой-либо орган научить меня шаг за шагом, как расшифровать сообщение, а также что такое p amp; q
Ответ №1:
На ваши вопросы можно ответить, прочитав страницу Википедии о RSA.
1a
Когда вы множите n, вы находите целые числа p и q, такие, что n = p * q . Вы вычисляете Y = (p — 1) (q — 1). Затем вы можете найти показатель степени закрытого ключа d, который вычисляется как d = 1 / e mod Y.
Чтобы расшифровать одно из значений c в перехваченном сообщении, вы просто вычисляете m = c ^ d mod n, где m — расшифрованное сообщение. Это работает, потому что (m ^ e) ^ d mod n равно 1.
Я оставлю фактические вычисления вам. Если вы застряли, на вики-странице есть несколько хороших примеров.
1b
Если вы не можете разложить n на множители, вы не сможете расшифровать сообщение. Если бы было возможно расшифровать сообщение, используя только открытый ключ (n, e), то зачем кому-либо использовать RSA?
Комментарии:
1. В стандартной модели никто не доказал, что если вы не можете разложить на множители, то вы не сможете расшифровать, однако считается, что это правда, и случайные предположения oracle подтверждают это, если используется правильное заполнение, такое как OAEP.
2. я сделал это самостоятельно в прошлый день, и это было похоже на ваш подход
Ответ №2:
1a. правильный ответ на вопрос, за который проголосовали
1b. Зная, что каждый фрагмент сообщения состоит только из 1 символа, Оскар может зашифровать каждый символ алфавита одинаковыми e и n и сравнить их.
a = 2 ^ 25 mod 18721 = 6400
b = 3 ^ 25 mod 18721 = 18718
c = 4 ^ 25 mod 18721 = 17173 …
Поддержанный ответ верен для шифрования более одного символа, но не в том случае, когда каждый символ зашифрован индивидуально.
Ответ №3:
Для подхода 1b фраза Rainbow Table может быть показательной (хотя намеренно несколько чрезмерно специфичной / вводящей в заблуждение).
Это было довольно весело. Я скажу вам, что ваши 2-я и 4-я буквы; и что я почти уверен, что вы опечатали последнее значение () . 'E' 134 Это либо 1375 (что имеет для меня наибольший смысл), либо 13444 (ближайшее совпадение строк, а также вроде имеет смысл).
ответ @bkjvbx верен в случае RSA, используемого в дикой природе; но поскольку в этом (предположительно) домашнем задании используется необработанный RSA на входах с удивительно ограниченным охватом, это совершенно другой зверь.