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.
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.
