How to perform mathematical operations on large numbers
У меня есть вопрос о работе с очень большими числами. Я пытаюсь запустить алгоритм RSA и давайте представим, что у меня 512-битное число d и 1024-битное число n. decrypted_word = crypted_word^d mod n, не так ли? Но эти d и n очень большие числа! Нестандартные типы переменных могут обрабатывать мои 512-битные числа. Везде написано, что rsa наконец-то нужно 512-битное простое число, но как на самом деле я могу выполнить какие-либо математические операции с таким числом?
И еще один думаю. Я не могу использовать дополнительные библиотеки. Я генерирую свои простые числа с помощью Java, используя BigInteger, но в моей системе у меня есть только базовые типы переменных, и STRING256 - самый большой.
2 ответа
Предположим, ваш максимальный целочисленный размер равен 64 битам. Строки не так полезны для математики в большинстве языков, поэтому игнорируйте строковые типы. Теперь выберите целое число, равное половине этого размера, то есть 32 бита. Их массив можно интерпретировать как цифры числа в базе 2 32. С их помощью вы можете делать длинное сложение и умножение, как вы привыкли к основанию 10, ручке и бумаге. На каждом элементарном шаге вы объединяете две 32-битные величины, чтобы получить как 32-битный результат, так и, возможно, некоторый перенос. Если вы выполните элементарную операцию в 64-битной арифметике, вы будете иметь оба этих элемента как часть одной 64-битной переменной, которую затем нужно будет разбить на 32-битную цифру результата (с помощью битовой маски или простого усечение приведения) и оставшийся перенос (через сдвиг битов).
Деление сложнее. Но если делитель известен, то вы можете избежать деления на константу, используя вместо этого умножение. Рассмотрим пример: деление на 7. Обратное значение 7 равно 1/7=0,142857…. Таким образом, вы можете умножить на это, чтобы получить тот же результат. Очевидно, что мы не хотим делать здесь математику с плавающей точкой. Но вы также можете просто умножить на 14286 и пропустить последние шесть цифр результата. Это будет совершенно правильный результат, если ваш дивиденд достаточно мал. Как маленький? Итак, вы вычисляете x/7 как x*14286/100000, поэтому ошибка будет x*(14286/100000 - 1/7)=x/350000, поэтому вы на безопасной стороне, если x<350000. Пока модуль в вашей настройке RSA известен, т.е. пока пара ключей остается неизменной, вы можете использовать этот подход для целочисленного деления, а также использовать его для вычисления остатка. Не забудьте использовать базу 2 32 вместо базы 10, и проверьте, сколько цифр вам нужно для обратной константы.
Есть альтернатива, которую вы, возможно, захотите рассмотреть, чтобы сделать уменьшение по модулю более простым, возможно, даже если n является переменной. Вместо того, чтобы выражать свои остатки как числа от 0 до n-1, вы также можете использовать от 2 1024 -n до 2 1024 -1. Поэтому, если ваше начальное число меньше 2 1024 -n, вы добавляете n для преобразования в эту новую кодировку. Преимущество этого состоит в том, что вы можете выполнить шаг сокращения, не выполняя никакого деления вообще. 2 1024 эквивалентно 2 1024 -n в этой настройке, поэтому элементарное уменьшение по модулю началось бы с разбиения некоторого числа на его младшие 1024 бита и его более высокий остаток. Более высокий остаток будет смещен вправо на 1024 бита (что является просто изменением индексации вашего массива), затем умножен на 2 1024 -n и, наконец, добавлен к нижней части. Вам придется делать это до тех пор, пока вы не будете уверены, что результат имеет не более 1024 бит. Как часто это зависит от n, так что для фиксированного n вы можете предварительно рассчитать это (и для большого n я бы ожидал, что это будет два шага сокращения после сложения, но три шага после умножения, но, пожалуйста, проверьте это еще раз), тогда как для переменной n Вы должны будете проверить во время выполнения. В самом конце вы можете вернуться к обычному представлению: если результат не меньше n, вычтите n. Все это должно работать как описано, если n> 2 512. Если нет, то есть если верхний бит вашего модуля равен нулю, то вам, возможно, придется внести дополнительные корректировки. Я не думал об этом, так как я использовал этот подход только для фиксированных модулей, близких к степени двойки.
Теперь для этого возведения в степень. Я очень советую вам сделать бинарный подход для этого. При вычислении x d вы начинаете с x, x 2 = x * x, x 4 = x 2 * x 2, x 8 =…, т.е. вы вычисляете все степени степени двух. Вы также поддерживаете некоторый промежуточный результат, который вы инициализируете одним. На каждом шаге, если соответствующий бит установлен в показателе степени d, вы умножаете соответствующую мощность на этот промежуточный результат. Допустим, у вас d=11. Тогда вы бы вычислили 1 * x 1 * x 2 * x 8, потому что d = 11 = 1 + 2 + 8 = 1011 2. Таким образом, вам понадобится не более 1024 умножений, если ваш показатель имеет 512 бит. Половина из них для возведения в степень двух, другая для объединения правильных полномочий двух. Каждое умножение во всем этом должно немедленно сопровождаться уменьшением по модулю, чтобы поддерживать низкие требования к памяти.
Обратите внимание, что скорость описанного выше процесса возведения в степень в этой простой форме будет зависеть от того, сколько битов в d фактически установлено. Таким образом, это может открыть атаку по побочному каналу, которая может дать злоумышленнику доступ к информации о d. Но если вы беспокоитесь о атаках по сторонним каналам, тогда вам действительно нужно, чтобы эксперт разработал вашу реализацию, потому что, я думаю, там может быть больше тех, о которых я не задумывался.
Вы можете написать некоторые макросы, которые вы можете выполнять под Microsoft для таких функций, как +, -, x, /, по модулю, x power y, которые обычно работают для любого целого числа, меньшего десяти или сотен тысяч цифр (практический - не теоретический - предел будучи внутренней памятью вашего процессора). Обратите внимание, что логика точно такая же, как у вас в начальной школе.
Например: p= 1819181918953471 делитель (2^8091) - 1, q = ((2^8091) - 1)/p, mod(2^8043; q) =.
Последний шаг занял около 0,1 сек.
wpjo (willibrord oomen на academia.edu)