3

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 ?

dudedev
  • 451
  • 1
  • 5
  • 19

1 Answers1

2

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

Nils Pipenbrinck
  • 83,631
  • 31
  • 151
  • 221
  • I did exactly the same. However, I am getting R & R^-1 as 1. Is it correct ? I am unable to figure out the issue. – dudedev Nov 13 '14 at 15:25
  • Can you post your prime N? – Nils Pipenbrinck Nov 13 '14 at 15:37
  • Thanks.. It worked.. I changed the Initialization of BIGNUM structure. – dudedev Nov 13 '14 at 15:39
  • @user3648560 Congratulations! – Nils Pipenbrinck Nov 13 '14 at 16:05
  • Thank You. Still I am not able to get the actual task done. Do you have any idea regarding "Brumley Time Attack on RSA". – dudedev Nov 13 '14 at 16:37
  • Yes, I have (it is actually quite easy to perform this attack, you just have to measure the time of your operations and correlate them with the 1 bits in N). However, this was not part of this question. You may find better help for such things at: https://crypto.stackexchange.com/ – Nils Pipenbrinck Nov 14 '14 at 00:11
  • It would be great if you could help me out. I have already asked it at below [link](https://crypto.stackexchange.com/questions/20009/timing-attack-on-openssl-by-brumley). However, no answer yet. – dudedev Nov 14 '14 at 10:34