Montgomery Reduction form using OpenSSL library

Question

I have N of 1024 bits. I need to convert a message M ( 512 bits ) into Montgomery reduction form as below.

M' = M * R^{-1} mod N

where , R = 2 ^ 512 (mod N)

How can I achieve the result ?

Answer 1

The following should work if you use the bignum package from OpenSSL directly.

Use the function BN_mod_exp to calculate your R=2^512 (mod N).

Afterwards you calculate the multiplicative modulo inverse of R by calling BN_mod_inverse. This will give you the R^-1.

Once done you just calculate your M' by calling BN_mod_mul to do the multiplication using your just calculated R^-1 and your original message.

You'll find the functions mentioned above in the OpenSSL BigNum Package. They are located in the include file: openssl/bn.h