Редукционная форма Монтгомери с использованием библиотеки OpenSSL

Question

У меня N 1024 бит. Мне нужно преобразовать сообщение M ( 512 бит) в форму сокращения Монтгомери, как показано ниже.

M '= M * R ^ {- 1} мод N

где R = 2 ^ 512 (мод N)

Как я могу достичь результата?

Answer 1

Следующее должно работать, если вы используете пакет bignum из OpenSSL напрямую.

Используйте функцию BN_mod_exp рассчитать ваш R=2^512 (мод N).

После этого вы вычисляете мультипликативный обратный по модулю R, вызывая BN_mod_inverse, Это даст вам R^-1.

После того, как вы сделали, просто рассчитайте свой M', позвонив BN_mod_mul чтобы сделать умножение, используя только что вычисленный R ^ -1 и ваше исходное сообщение.

Вы найдете функции, упомянутые выше, в пакете OpenSSL BigNum. Они находятся во включаемом файле: openssl/bn.h