1
$\begingroup$

I have Montgomery exponentiation working, but it's working quite slow. I suspect there are two reasons for this - I implemented it bit size instead of word size (I didn't realize at the time that software implementation should use word size).

The second is how I select R. Given a modulus N with bit length n, I'm calculating R by raising 2 to the power of the bit length of N, n. i.e. This is way all the examples I've seen use, but they all use small numbers. Every number I'm dealing with here has at least 1024 bits. 

BigInteger R = new BigInteger("2").pow(n.bitLength());

I suspect this might be why my Montgomery is running slower than my Right-To-Left binary implementation - can anyone give me a more efficient way of selecting r? (In as simple English as possible please!)

Edit - the full code is at - https://codereview.stackexchange.com/questions/18199/optimization-of-exponentiation if anyone want to have a look at it.

Improve this question
$\endgroup$
2
  • $\begingroup$ (I hope this is just for fun. You'll have huge side channels with such an implementation) $\endgroup$ – CodesInChaos Nov 13 '12 at 17:02
  • $\begingroup$ @CodesInChaos no it was an assignment! Would you care to make a comment or two on codereview.stackexchange.com/questions/18199/…? The assignment due date has passed so you can say as much as you like. $\endgroup$ – Saf Nov 13 '12 at 22:03
4
$\begingroup$

Montgomery multiplication makes sense only with word sizes. If your word size is $w$ (e.g. $w = 32$ if you have 32-bit words), then $R = 2^{kw}$ for some integer $k$; you choose $k$ as small as possible, given that you must have $R \geq N$.

In plain words, if your modulus $N$ has size $n$ bits, then you look for the next multiple of $w$. For a 1024-bit modulus, which is already a multiple of 32, you use $R = 2^{1024}$. For a 1025-bit modulus, you would use $R = 2^{1056}$.

You really want to read chapter 14 of the Handbook of Applied Cryptography.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, this was how I was calculating R. I guess the slowdown is the way I programmed the actual Montgomery methods monPro and modExp (See the code review I example I linked if you are a coder) $\endgroup$ – Saf Nov 11 '12 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.