Как реализовать c = m ^ e mod n для огромных чисел?

Question

Я пытаюсь выяснить, как реализовать шифрование RSA с нуля (только для интеллектуальных упражнений), и я застрял в этой точке:

Для шифрования, c = m ^e mod n

Теперь e обычно равно 65537. m и n - это 1024-битные целые числа (например, 128-байтовые массивы).Это явно слишком велико для стандартных методов.Как бы вы это реализовали?

Я читал здесь немного о возведении в степень, но это просто не для меня:

Википедия-Возведение в квадрат

Эта глава (см. Раздел 14.85)

Спасибо.

edit: Также нашел это - это то, на что я должен смотреть? Википедия - Модульное экспонирование

Answer 1

Вычисление по квадрату:

Давайте рассмотрим пример.Вы хотите найти 17 ²³ .Обратите внимание, что 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 - это 10000000000000001 в двоичном формате, что делает все это довольно простым.Это в основном

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) ² .

Answer 2

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 бит в этой позиции. Все умножения должны быть уменьшены в мод.

В качестве примера рассмотрим m ^ 13. 11 = 1101 в двоичном виде. так что это так же, как м ^ 8 * м ^ 4 * м. Обратите внимание на степени 8,4, (не 2), 1, что совпадает с битами 1101. А затем напомним, что m ^ 8 = (m ^ 4) ^ 2 и m ^ 4 = (m ^ 2) ^ 2.

Answer 3

Для эффективного алгоритма вам необходимо объединить возведение в квадрат путем возведения в квадрат с повторным применением mod после каждого шага.

Для нечетного e это имеет место:

m ^e mod n = m ⋅ m ^e-1 mod n

Для четных e :

m ^e mod n = (m ^{e / 2} mod n) ² mod n

С m ¹ = m в качестве базового варианта это определяет рекурсивный способ эффективного модульного возведения в степень.

Но даже с таким алгоритмом, как это, потому что m и n будут очень большими, вам все равно нужно будет использовать тип / библиотеку, которая может обрабатывать целые числа таких размеров.

Answer 4

Если g(x) = x mod 2^k быстрее вычислить для вашей библиотеки bignum, чем f(x) = x mod N для N, не делимого на 2, то подумайте об использовании умножения Монтгомери . При использовании модульного возведения в степень не требуется вычислять по модулю N на каждом шаге, вам просто нужно выполнить «Montgomeryization» / «un-Montgomeryization» в начале и конце.