Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I would like to know what (if any) are the advantages of using Montgomery Power ladder over the Double-and-Add-Always algorithm.
I think that firstly, Monty would be slightly faster than DoubleAndAdd. But I'm not too sure about side-channel security.

I'm asking this in the context of RSA's modular exponentiation and ECC's Elliptic Curve Scalar Multiplication.

share|improve this question
    
I can add the algorithms if anyone needs them, just leave a comment. Thanks! –  BlackAdder Jun 2 at 2:24
1  
It will be hard to beat this article with excellent information: Marc Joye and Sung-Ming Yen, The Montgomery Powering Ladder (in proceedings of CHES 2002; alternate link). –  fgrieu Jun 2 at 16:49
    
On montgomery curves montgomery ladders enable cheap addition via differential addition in x/z form. In most other situations I'd rather create a lookup table with 32 or so entries and then double 5 times followed by one lookup and one addition. –  CodesInChaos Jun 3 at 17:31
    
@CodesInChaos: the point of these algorithms is that they try to resist cache-based side channel attacks; that's hard to do with a look-up based algorithm. Yes, if you don't care about those side channel attacks (either you know no one else is sharing your cache, or you're doing ECDSA signature verify), there are considerably more efficient alternative available. –  poncho Jun 3 at 18:30

1 Answer 1

up vote 2 down vote accepted

Actually, those two algorithms are surprisingly close; I'll write both of them up to show how close they are.

They both can be written as a combination of three substeps:

A := Add( B, C )

This takes the two points B and C, and adds them together (I'll be writing things in additive notation; in RSA, with would be a modular multiplication)

A := Double( B )

This takes the point B, and adds it to itself (or, in RSA, a modular squaring)

If (cond) swap( A, B )

This tests a condition on the multiplier (exponent in RSA), and depending on that, either exchanges A and B, or leaves them alone. Note that if it leaves them alone, it still performs the read and write operations; however when it writes A, it writes A's original value (and not B's value); this allows this operation not to leak any information via the cache.

Note that all these three can be done in constant time, and with constant memory accesses; hence we don't leak any information, even against an attacker who can listen to cache accesses.

Now, both algorithms use temp variables A and B, and I'll call the original point G. The core of the DoubleAndAdd algorithm can be written as:

A := Double(A)
B := Add(A, G)
if (bit_i_of_multiplier_is_set) Swap(A, B)

(Actually, the swap operation here can be simplified; we don't care if it actually updates B)

The core of the Montgomery Ladder can be written as:

if (bit_i_xor_bit_i_1_is set) Swap(A, B)
A := Add(A, B)
B := Double(B)

There are also differences with how the two algorithms initialize A and B (Montgomery stirs in G by how it initializes A and B), and where they find the final result -- those are relatively minor.

So, given that both algorithms solve the problem of doing a point multiplication in constant time without leaking any information via the cache, how do they compare?

Well, for one, if you look at the Montgomery Ladder, the two operations it does can be done in parallel. I would be skeptical if it would be a win to give them to two different cores (core synchronization is not cheap); however if you could have them done on a 2-way SIMD (if the add and double operations are sufficiently similar), that may be a win.

On the other hand, if you look at the DoubleAndAdd algorithm, we always add the point G. Now, with Elliptic Curves and RSA, this doesn't buy us anything, but with Diffie-Hellman, we can pick G to make this operation cheap (say, G=2); that would speed up the first phase of the operation. Also, in my humble opinion, DoubleAndAdd is a bit less complex than the Montgomery Ladder.

So, bottom line: there isn't actually that big of a difference; there might be some minor implementation differences.

share|improve this answer
    
The presence of answers of this nature is why I love SE! –  BlackAdder Jun 4 at 0:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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