Как найти базовое значение в модульной арифметике?

Question

Мне нужна какая-то эффективная формула, которая позволит выяснить исходное сообщение (msg) относительно следующей формулы: C = msg ^ e mod N. Если пользователю предоставлены C, e и N Есть ли эффективный способ рассчитать MSG? В этом примере C - это зашифрованный текст, e - открытый ключ, а N - открытый модуль.

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

Answer 1

Модуль - это необратимая операция .В лучшем случае вы знаете, что msg ^ e = C + k*N, и вам необходимо определить значение k.

. Рассмотрим следующий простой случай:

e = 2
N = 10
msg =  1 | C = 1  'Note1
msg =  2 | C = 4  'Note2
msg =  3 | C = 9  'Note3
msg =  4 | C = 6  'Note4
msg =  5 | C = 5
msg =  6 | C = 6  'Note4
msg =  7 | C = 9  'Note3
msg =  8 | C = 4  'Note2
msg =  9 | C = 1  'Note1
msg = 10 | C = 0

Должно быть сразу очевидно, что если C = 6, это может означать, что Msg = 6 или , что Msg = 4 (или Msg = 24, и так далее, до бесконечности) безспособ узнать разницу без дополнительной информации.

Однако , учитывая то же msg для различных известных значений e иN, тогда вы можете сузить возможности так:

e = 3
N = 10
Msg =  1 | C = 1
Msg =  2 | C = 8
Msg =  3 | C = 7
Msg =  4 | C = 4  'We can now see that this
Msg =  5 | C = 5
Msg =  6 | C = 6  'Is different from this
Msg =  7 | C = 3
Msg =  8 | C = 2
Msg =  9 | C = 9
Msg = 10 | C = 0