Как реализовать c=m^e модификацию n для огромного количества?
Я пытаюсь выяснить, как реализовать RSA crypto с нуля (только для интеллектуального осуществления), и я застреваю по этому вопросу:
Для шифрования, c = меня модификация n
Теперь, e обычно 65537. m и n являются 1024-разрядными целыми числами (например, 128 массивов байтов). Это является очевидно слишком большим для стандартных методов. Как Вы реализовали бы это?
Я читал немного о возведении в степень здесь, но оно просто не нажимает для меня:
Возведение в степень Википедии путем обработки на квадрат
Эта Глава (см. раздел 14.85),
Спасибо.
править: Также найденный это - является этим больше, на что я должен смотреть? Википедия - Модульное Возведение в степень
4 ответа
Экспоненциация путем возведения в квадрат:
Рассмотрим пример. Вы хотите найти 1723. Обратите внимание, что 23 - это 10111 в двоичном исчислении. Давайте попробуем возвести его в степень слева направо.
// a exponent in binary
a = 17 //17^1 1
a = a * a //17^2 10
a = a * a //17^4 100
a = a * 17 //17^5 101
a = a * a //17^10 1010
a = a * 17 //17^11 1011
a = a * a //17^22 10110
a = a * 17 //17^23 10111
Когда вы возводите в квадрат, вы удваиваете экспоненту (сдвиг влево на 1 бит). Когда вы умножаете на m, вы прибавляете 1 к экспоненте.
Если вы хотите уменьшить по модулю n, вы можете делать это после каждого умножения (а не оставлять это на конец, что привело бы к тому, что числа стали бы очень большими).
65537 - это 1000000000000000001 в двоичном исчислении, что делает все это довольно простым. По сути это
a = m
repeat 16 times:
a = a * a
a = a mod n
a = a * m
a = a mod n
где, конечно, a, n и m - "большие целые числа". a должно быть не менее 2048 бит, так как оно может стать большим, как (n-1)2.
Для эффективного алгоритма вам необходимо объединить возведение в степень возведения в квадрат с повторным применением mod после каждого шага.
Для нечетного e это верно:
m e mod n = m ⋅ m e-1 mod n
Для четного ] e :
m e mod n = (m e / 2 mod n) 2 mod n
С m 1 = m в качестве базового случая это определяет рекурсивный способ выполнения эффективного модульного возведения в степень.
Но даже с таким алгоритмом, поскольку m и n будут очень большими, вам все равно потребуется использовать тип / библиотеку, которая может обрабатывать целые числа таких размеров.
Если g (x) = x mod 2 ^ k вычисляется быстрее для вашей библиотеки bignum, чем f (x) = x mod N для N, не делимого на 2, затем рассмотрите возможность использования умножения Монтгомери . При использовании с модульным возведением в степень это позволяет избежать вычисления по модулю N на каждом шаге, вам просто нужно выполнить «Монтгомеризацию» / «не-Монтгомеризацию» в начале и в конце.
result = 1
while e>0:
if (e & 1) != 0:
result = result * m
result = result mod n
m = m*m
m = m mod n
e = e>>1
return result
Это проверяет биты в экспоненте, начиная с наименее значимого бита. Каждый раз, когда мы немного двигаемся вверх, это соответствует удвоению мощности m - следовательно, мы сдвигаем e и квадрат m. Результат получает степень m, умноженную на только в том случае, если экспонента имеет 1 бит в этой позиции. Все умножения должны быть уменьшены mod n.
В качестве примера рассмотрим m^13. 11 = 1101 в двоичном коде. так что это то же самое, что m^8 * m^4 * m. Обратите внимание на степени 8,4,(а не 2),1, которые совпадают с битами 1101. А потом вспомним, что m^8 = (m^4)^2 и m^4 = (m^2)^2.