Montgomery Ladder with affin/projective Coordinates

Question

So I'm trying to understand why the montgomery arithmetic is fast and what the montgomery ladder is.

With this Post i understood the basic affin arithmetic and Ladder.

So this is not really faster than arithmetic on common weierstrass equations. In the original Paper from Montgomery, he defined the projective arithmetic for adding and doubling.

My first questions are: Is the projective arithmetic faster because of not having a division? Does the ladder have constant time, because there is not division? Does that mean, that the ladder with affine coordinates don't have constant time? ( My idea is, that division in a field is a multiplication with a inverse. For calculating an inverse you need the euklidiean algorithm. This algorithms is not the fastest and can't be computed in constant time)

Then i was looking into the work of Bernstein. In this Paper and in his Curve25519 he describes a optimized double and add formula. It looks like this:

When i get it right, you can use the montgomery ladder for affine coordinates with the affine arithmetic and for projective coordinates with the projective coordinates. So Bernstein made the shown graph for the projective montgomery ladder in order to give an optimized implementation, where already computed results are used again. So i tried to write the graph into Pseudocode:

R0 = (0,0)
R1 = (x,y)
x1 = 
    for i from m downto 0 do:
        if xi = 0 then:
            x,z,x',z' =  R0[0], R0[1], R1[0], R1[1]
            tmp1, tmp2 = x, x'

            x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

            x',z',x,z = (z * x'), (x * z'), (x * x), (z*z)
            tmp1, tmp2 = x, x'

            x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

            z = z*( tmp1 + ((A-2)/4)*z )
            x' = x' * x'
            z' = z' * z' * x1

            R0[0], R0[1], R1[0], R1[1] = x, z, x' , z'
        else
            x,z,x',z' =  R1[0], R1[1], R0[0], R0[1]
            tmp1, tmp2 = x, x'

            x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

            x',z',x,z = (z * x'), (x * z'), (x * x), (z*z)
            tmp1, tmp2 = x, x'

            x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

            z = z*( tmp1 + ((A-2)/4)*z )
            x' = x' * x'
            z' = z' * z' * x1

            R0[0], R0[1], R1[0], R1[1] = x',z',x, z
return R0

That brings me to my next questions: Where is the x1 comming from, how is it calculated? I saw in his paper, that x1/z1 = X(Q - Q'), but it remains unclear how to substract those points.

Next question is: Is this peudocode logical correct ( at least everything except the x1)?

I hope this are not too many questions!

Answer 1

Maybe one day someone finds this Post again and has the same questions. To you: I hope you're having a great day!

1. Questions: The projective Arithmetic is faster, because there are only multiplications, squarings, additions to do. The affine Artihmetic is slower, because it takes a lot of time to compute the division. Especially for the big numbers used in modern cryptographie. BUT: That is not the answer to the constant time ladder. Yes affin coordinates with division can't be computed with constant time, but the reason for the projective ladder is a different. You can tranform different types of elliptic curve into the projective form, but for them you can't always use the montgomery ladder. For a long time ( at least when montgomery published his work ) elliptic curve scalar multiplikation on weierstraß was only possible with double and add algorithms. Those algorithms tranformed the scalar into the binary form and had different operations for 1 and 0. Therefor one could approximate how many 1 and 0 there are. The Montgomery ladder has the same operations for both. So there is no difference in time.

2. Question: With projective coordinates it is only possible to add/double multiples of the same point. The montgomery ladder starts with a given scalar $n$ and Point $P$. In each step two results are calculates $R0$ and $R1$. The important point here is, that those results are either of the form $(n')R0$, $(n'+1)R1$ or $(n'+1)R0$, $(n')R1$. That means the difference between them is always 1. (When you look at the definition for the projective Arithmetic it is clear what that means). For the ladder this means, that $x1$ is always the x coordinate of the starting Point $P$. Therefore it is always the same and must not be computed!

Note: I still can't say, whether my pseudocode is correct or not.