Я пытаюсь сделать модуль RSA на VHDL, который, в свою очередь, будет развернут на FPGA. Я пытаюсь реализовать полный алгоритм Монтгомери, что означает, что я работаю с алгоритмом экспонирования Монтгомери и алгоритмом умножения Монтгомери. В основном мои тесты состоят из генерации случайных чисел (ключи, модуль, r, сообщения), которые я использую для выполнения шифрования/дешифрования. Если исходное сообщение равно расшифрованному сообщению, тест пройден.
Сначала я сделал высокоуровневый код битовой версии умножения Монтгомери на Python. Пытаясь избавиться от окончательного вычитания, я обнаружил это сообщение Бретта о переполнении стека. Он же сделал пост здесь об одном и том же. Это помогло мне заставить битовый алгоритм работать в Python без окончательного вычитания. Кроме того, казалось, что он работает в VHDL при выполнении моделирования.
Далее нужно было заставить работать алгоритм на уровне слов. Чтение документа c03gfp от Ãetin Kaya Koç найдено здесь, мне удалось заставить высокоуровневый код Python алгоритма на уровне слов работать, но не так, как я надеялся, поскольку мне пришлось сохранить окончательное вычитание.Использование того же R, который использовался в коде на уровне битов, не работало для кода на уровне слов. Честно говоря, я не уверен, что Бретт спрашивает о том же самом. здесь, но он может быть.
Я пытался найти документы, описывающие, как это должно быть сделано, в основном с помощью Google, но мне не повезло найти их. Если я и находил что-то, что действительно могло бы помочь мне избавиться от окончательного вычитания в алгоритме на уровне слов, то в этом случае я не понимал содержания документов.
У меня возникла идея, что я мог бы попытаться увеличить R больше, чем это было сделано при использовании оптимизации Уолтера для алгоритма битового уровня. Учитывая, что я работаю с уровень слова Алгоритм, почему бы R не быть на одно слово шире, чем модуль?
Для битового алгоритма я установил R = 2 ^ (2 * NUM_BITS) по модулю n как было предложено Рено Пакале, куда NUM_BITS = 256 + 2 в моем случае, когда я работал с 256-битными числами.
С другой стороны, для алгоритма на уровне слов я попытался установить R = 2 ^ (2 * (NUM_BITS + WORD_WIDTH)) по модулю n. В моем случае NUM_BITS = 256 и WORD_WIDTH = 32, но WORD_WIDTH также может быть, например, 8, 16, 64 или 128 (обратите внимание, что WORD_WIDTH $\leq$ NUM_BITS). Это сработало и сработало во всех тестах, которые я проводил в Python со случайными числами. Мне еще предстоит реализовать это в VHDL, так как я хотел бы проверить, правильно ли это, прежде чем делать это, или, по крайней мере, иметь больше оснований для этого.
Итак, мой вопрос в том, правильно ли установить R = 2 ^ (2 * (NUM_BITS + WORD_WIDTH)) по модулю n для умножения Монтгомери на уровне слов, как я сделал сейчас.
Кроме того, есть ли какие-либо документы, описывающие это?
РЕДАКТИРОВАТЬ 1
Кажется, после переформулировки моего вопроса, когда я гуглил, я наткнулся на это пост Сафа. Ответ, предоставленный Томасом Порнином, кажется почти ответьте на мой вопрос, так как мой вопрос в основном был тем же вопросом, что и тот, который задал Саф.
Томас Порнин писал, что если модуль $n$ имеет размер NUM_BITS, то я должен был искать следующее кратное WORD_WIDTH.
Повторяя пример Томаса Порнина, где WORD_WIDTH = ш = 32:
Для 1024-битного модуля, который уже кратен 32, вы используете $R=2^{1024}$. Для 1025-битного модуля вы должны использовать $R=2^{1056}$.
Для меня это не так, если я что-то неправильно понял. Через мое тестирование с NUM_BITS = 256 и WORD_WIDTH = 32 Я нашел эту настройку $R=2^{256}$ мощь потерпеть неудачу, хотя $n$ является 256-битным числом, и даже если $n$ представляет собой 255-битное число. С другой стороны, тесты всегда успешны, когда $R=2^{256 + 32\cdot c}$, куда $с$ является положительным целым числом. Я тестировал только с $с = [1,2,3]$, поэтому я не могу гарантировать, что все положительные числа будут работать. Следует также учитывать качество моих тестов и их количество ($+1000000$).
Следующее также из ответа Томаса Порнина на вопрос Сафа:
Дело в том, что умножение Монтгомери имеет смысл только с размерами слов. С $w$ как размер слова, то $ R = 2 ^ {кВт} $ для некоторого целого числа k, которое следует выбрать как можно меньшим, учитывая, что $R\ge N$.
мне кажется $ Р > Н $ должно быть так. Есть комментарии по этому поводу?
