возведение в степень RSA

Question

Я пытаюсь реализовать RSA в C ++ для очень больших чисел.Я не использую какую-либо библиотеку.Я хотел написать свой собственный код :) Так что я использовал строки для хранения этих больших чисел.Умножение и деление больших чисел чрезвычайно быстро, так что это не проблема.Но когда я делаю шифрование или дешифрование, то есть используя мод ^ ^, это очень медленно.Я использовал p и q в качестве 50-значных чисел и пытался зашифровать текст длиной около 20 символов.Мне потребовался один час, чтобы зашифровать и расшифровать.Я использовал возведение в степень методом возведения в квадрат, чтобы уменьшить вычислительное время.Какое возможное улучшение я могу сделать?

Кроме того, каков наилучший способ получения простых чисел p & q. (Желательно отраслевой стандарт)

Answer 1

Как говорили другие, если вы хотите, чтобы RSA в чем-то, что вы пишете, вы должны использовать хорошо протестированную библиотеку, а не собственный код. Однако написание кода может быть очень полезно для изучения вещей, поэтому в этом нет абсолютно ничего плохого.

1. То, что я думаю, замедляет вас - это вычисление a ^ b в a ^ b mod m, потому что a ^ b будет чрезвычайно большим числом. Использование квадратов для вычисления этого несколько помогает среде выполнения, но вы все равно получите огромные промежуточные числа и огромный результат, прежде чем брать модуль. Есть много хитростей для более быстрого выполнения модульного возведения в степень, но википедия знает о них лучше, чем я: http://en.wikipedia.org/wiki/Modular_exponentiation. Я бы посмотрел там первым.

2. Я ничего не знаю о состоянии RSA в отрасли, так что это всего лишь толчок в правильном направлении: поскольку простое тестирование обычно медленное, для p и q вам, вероятно, нужны «вероятные простые числа»: http://en.wikipedia.org/wiki/Probable_prime

3. Струны звучат как довольно неэффективный способ сделать это. Если # 1 не помогает, вы можете заглянуть в библиотеку Java BigInteger и либо найти эквивалент в C ++, либо написать свой собственный. Однако это обеспечит только постоянный коэффициент улучшения скорости и использования памяти (если только проверка кода не покажет вам лучший алгоритм для того, что вы выполняете), поэтому, возможно, не стоит тратить время на написание своего собственного. Принятие чьих-либо еще может быть полезным.

Answer 2

Делаете ли вы модульное сокращение после возведения в квадрат / умножения во время возведения в степень? Вы должны вычислять модуль после каждого возведения в квадрат / умножения, чтобы промежуточные результаты никогда не превышали вдвое больше цифр, чем в вашем значении для m.

Answer 3

Я думаю, что арифметические библиотеки произвольной точности, такие как, например, GMP содержит некоторые очень тщательно настроенные функции (и даже некоторый код сборки вручную).

Арифметические алгоритмы с высокой точностью очень сложны (и не очень интуитивны). Есть книги на эту тему (я однажды позаимствовал одну, слишком трудно было разобраться во всех деталях, если вы не потратили много часов на изучение математики внутри).

Если бы я был там, где вы, я бы использовал существующую библиотеку, такую ​​как GMP.

Или же потратьте время на изучение, чтение и изучение трудной математики.