Re: [Cfrg] On the use of Montgomery form curves for key agreement

[Andrey Jivsov <[e-mail]>]

On 09/02/2014 05:20 PM, Michael Hamburg wrote:
> There isn’t actually a 10% penalty for switching forms unless you are
> translating between two different wire formats.  If one side or the
> other is internal to the application, it will be projective, which makes
> translation free unless the format is compressed.

[ http://www.ietf.org/mail-archive/web/cfrg/current/msg05045.html ]

I followed up on the idea that one can convert between Montgomery 
canonical compressed representation to Edwards projective coordinates 
without extra one or two inverses. Here are my notes, confirming the above.

To convert from Montgomery M(x,y): y^2 = x^3 + A*x^2 + x to -1 twisted 
Edwards coordinate (x_e,y_e) on the curve E(x,y): -x^2+y^2 = 1 + 
d*x^2*y^2 the following formula is used:

x_e = sqrt( -(A+2) ) * x / y
y_e = (x-1)/(x+1)

O = (0,0) for M
O = (0,1) for E, (0,-1) is exceptional

d = -(A-2)/(A+2)

y is not sent and we calculate it based on y_e and E(x,y) equation as 
follows:

x_e = sqrt( (y_e^2-1) / (d*y_e^2+1) )

The numerator and denominator in the above formula are:

y_e^2-1 = -4x = Y^2 - T^2
d*y_e^2+1 = d*Y^2+T^2

Y = x - 1
T = x + 1

This is x_e = sqrt( (T^2-Y^2)/(-dY^2-T^2) ) and this can be calculated 
in terms of Montgomery x at no additional cost, but this is not enough 
because y_e = Y/T would require an additional inverse. In addition, 
there may be a second extra inverse corresponding to the conversion back 
to the canonical representation.  These two inverses would have added 
20% performance penalty, a significant hit in some instances. For 
example, Curve25519 is 50% faster than NIST P-256 between openssl 
optimized for AVX2 v.s. curve25519-donna on the same modern x86_64 CPUs.

Fortunately, it is possible to avoid the overhead of conversion both ways:
* from affine Montgomery compressed coordinates (x only) to affine -1 
twisted Edwards  coordinates (from which one can use projective coordinates)
* from projective -1 twisted Endwards coordinates to Montgomery

First, let's look at conversion to Edwards affine coordinates. This 
conversion has a nice property that it's affine-to-affine.

The following 3 "tricks" will be used to accomplish this.

The simultaneous square root and inversion are explained in section 5 of 
http://ed25519.cr.yp.to/ed25519-20110705.pdf )

The "Montgomery trick" is easily generalized to any number of inverses 
as follows, shown for 3. To calculate 1/a, 1/b, 1/c, we do

t = 1/(abc), 1/a = bct, 1/b = act,  1/c = abt.

Also, sqrt(zz) = zz/sqrt(zz).

( See also http://moderncrypto.org/mail-archive/curves/2014/000064.html, 
http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html )

x_e = sqrt(T^2-Y^2) / sqrt(-dY^2-T^2) =
(T^2-Y^2) / sqrt( (T^2-Y^2)(-dY^2-T^2) )

With this in mind, here is the algorithm:

1. t = (T^2-Y^2)*(-d*Y^2-T^2) * T^2

2. tt = sqrt(1/t) ( paying the cost close to 1 inverse )

3. x_e = tt * (T^2-Y^2) * T

4. y_e = tt^2 * (T^2-Y^2)*(-d*Y^2-T^2) * T ( this is 1 / T )
    y_e = Y * y_e

5. Test that E(x_e,y_e)==0 (otherwise more thoughts are needed for point 
x validation and handling of O)

The sign of x_e will need to be adjusted, not discussed here.

Finally, the conversion back to Montgomery representation is simpler.

Let's assume that there is a projective (x/z, y/z) representation. 
(Other internal representations should work as well, as long as there is 
an inverse calculation to piggy-back on)

We know that Montgomery x is obtained from Edwards y_e as follows:

x = -(y_e+1)/(y_e-1).

To calculate affine y_e = y_e'/z_e' we calculate x directly from 
projective y_e' as follows:

x = - (y_e'+z_e')/(y_e'-z_e').

Thank you.