реализация библиотеки bignum для шифрования RSA

Поэтому, конечно, я знаю, что есть простые решения для этого, такие как использование библиотеки GMP или многочисленных других библиотек произвольной точности. Это для работы в классе, поэтому мне не разрешено следовать ни одному из этих маршрутов. После того, как мы построим все наши операции, мы сможем создать схему шифрования RSA.

Я использую векторы для хранения n-битных чисел, представленных в двоичном формате. У меня есть преобразования в десятичную позже, но я должен работать с двоичным и конвертировать только для отображения.

Я успешно реализовал сложение, вычитание и умножение. Я застрял на делении и модульных операциях … особенно модульных возведения в степень. Я понимаю алгоритмы хотя бы на базовом уровне, но, похоже, не могу перевести его в код, который будет работать с числами произвольной длины. Кажется, я не могу найти какие-либо примеры такого рода работы, выполненной на с ++ без внешних библиотек.

Некоторые конкретные вопросы:

Есть ли лучший способ сделать модуль для n-битного числа, кроме простого вызова функции деления, которую я пишу, и использования возвращаемого остатка?

Мне бы очень хотелось увидеть несколько хороших примеров на С ++, поскольку я вообще не могу хорошо следовать исходному коду GMP.

Будем весьма благодарны за любые полезные ресурсы для учебы или некоторую помощь. Спасибо

1

Решение

Вы можете подделать операции модуля с делением. Ваша операция по модулю эквивалентна:

v = n - (n / m) * m

где n — делитель, m — модуль, а v — выходное значение (все числа произвольной точности)

Если вы застряли на делении, вы можете просто реализовать его, как если бы вы выполняли длинное деление вручную. (Вы должны были научиться делать это в средней школе с помощью умножения и вычитания. Достаточно легко перевести процесс на основание 2. Если вы застряли, сделайте несколько на бумаге. Если вы хотите более эффективный алгоритм, вы, вероятно, можете найти его, выполнив поиск в Google для чего-то вроде «алгоритма произвольного деления точности»)

Получив модуль, вы можете вычислить модульное возведение в степень с повторным возведением в квадрат. Обратите внимание, как мы вычисляем некоторое большое целое число X до степени 67, mod N:

v1  = X mod N         // X^1 mod N
v2  = v1  * v1  mod N // X^2 mod N
v4  = v2  * v2  mod N // X^4 mod N
v8  = v4  * v4  mod N
v16 = v8  * v8  mod N
v32 = v16 * v16 mod N
v64 = v32 * v32 mod N // X^64 mod N

v66 = v64 * v2  mod N // X^66 mod N
v67 = v66 * v1  mod N // X^67 mod N

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

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

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector