Finding Y from X in ECC point

[Francisco Ruiz]

I'm working on a Diffie-Hellmann scheme using the SJCL ECC routines, and I've got it working pretty well thanks to all the help I've gotten from you guys. After I generate a public key pub from a secret key sec by doing   

pub = curve.G.mult(sec)

I find that the pub object contains both x and y coordinates of the point on the elliptic curve, which is somewhat redundant. I'd like to display/send only one of the coordinates and have the program compute the other one, saving half the size of the transmitted public key.

Looking through the code, I see that ecc.js determines if a point pub is on the curve by doing this:

pub.y.square().equals(pub.curve.b.add(pub.x.mul(pub.curve.a.add(pub.x.square()))))

so if it returns "true" the point is on the curve. I wonder if I could use something like this to find y^2 from x:

y2 = pub.curve.b.add(pub.x.mul(pub.curve.a.add(pub.x.square())))

and then take the square root of y2 in order to find y. Is there such a function in SJCL?

Maybe there is a better way to do this?

Thanks!

Francisco

[Ron Garret]

I don't know if it exists in SJCL, but the scheme you describe will certainly work. You have to carry one extra bit to keep track of the sign of Y. Finding a modular square root is not trivial, but there are known ways to do it, e.g.:

http://planetmath.org/encyclopedia/ShanksTonelliAlgorithm.html

But it turns out that to do ECDH you don't actually need to compute Y at all, you can do all the calculations using X-coordinate math only using an X/Z coordinate transform. See:

http://cr.yp.to/ecdh.html

http://cr.yp.to/highspeed/naclcrypto-20090310.pdf

Or, if you just want to cut to the chase:

http://www.flownet.com/ron/code/djbec.js

The D-H code is at the bottom.

rg

> --
> You received this message because you are subscribed to the Google Groups "SJCL discussion" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sjcl-discuss...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Francisco Ruiz]

Thanks, Ron,

I've found that, at least for the 521-bit NIST curve, which is what I'm using in ECC, there is a very easy way to extract the square root, based on the Tonelli-Shanks algorithm, which has a trivial case when the prime field mod 8 is 7.

if y2 is the square of y and p is the prime number on which the curve is based, the square root is:

y = (y2)^ ((p+1)/4)  mod p

in SJCL, I can implement this as: 

curve = sjcl.ecc.curves['c521']

p = curve.field.modulus    //13th Mersenne prime = 2^521 -1, as a bn object

q = "8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"  

q = sjcl.bn.fromBits(sjcl.codec.hex.toBits(q)) //I wish there was an easy way to do (p+1)/4

//let's say y2 is obtained this way:

y2 = y.square() //where y is an object containing the y coordinate, then

y2sqrt = y2.powermod(q,p)

//returns an object containing the same data as the original y.

The problem is that the powermod operation is very slow, even slower than the regular ecc public key derivation.

I've taken a look at the Bernstein program, but the algorithm looks so different from those in the current ecc.js that I'm afraid I'd have to rebuild everything. Plus it's for a different curve and it's not obvious to me how to adapt it for the 521-bit NIST curve.

Is there a faster version of powermod? If I were to use the Bernstein code, how would I implement the 521-bit curve?

Many thanks!

[Mike Hamburg]

Hi Francisco,

I believe that the Bernstein code is just for Dan Bernstein's
non-standard Curve25519 elliptic curve, not for the NIST curves.

If your y2 is a p521 object, you *should* be able to use y2.power()
instead of y2.powerMod(). This should be much faster, because the
reduce() function is specialized for primes of these forms. This should
work for the other primes as well. For the specific prime p521 (but not
for essentially any other prime) you can say:

y = y2;
for (i=0; i<519; i++) {
y = y.square();
}
return y;

This is because (p+1)/4 = 2^519.

-- Mike

>> an email to sjcl-discuss...@googlegroups.com <javascript:>.

[Ron Garret]

On Apr 1, 2013, at 4:23 PM, Mike Hamburg wrote:

> I believe that the Bernstein code is just for Dan Bernstein's non-standard Curve25519 elliptic curve, not for the NIST curves.

That's right. DJB's code makes use of some efficiency hacks that are applicable only to the particular prime he's using (2^255-19). (Well, actually, they can be applied to any prime of the form 2^N-d where d is small.) I only cited Curve25519 as an existence proof that ECC can be done with x-coordinate math only.

Of course, it is possible to implement Curve25519 using generic ECC math routines as well.

Just out of curiosity, why are you using p-521? It seems like overkill for anything short of securing nuclear weapons.

rg

[Mike Hamburg]

Curve25519 is also a Montgomery curve, rather than a short Weierstrass curve, which changes the formulas and some of the other properties. For example, it's much more efficient to do the x-coordinate-only ECDH with a Montgomery curve, and less efficient to use projective or Jacobian coordinates, compared to the NIST curves, and you can also turn it into an Edwards curve. The security properties are also slightly different in ways that don't usually matter -- the NIST curves have prime order vs almost-prime order, but Curve25519 has an almost-prime-order twist.

And I agree with rg. While I can see uses for p521 outside of nuclear weapons, it is overkill for anything in Javascript. And overkill is fine if it doesn't cost you anything, but given how slow Javascript ECC is, I wouldn't bother with it unless you have a really good reason.

-- Mike

> --
> You received this message because you are subscribed to the Google Groups "SJCL discussion" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to sjcl-discuss...@googlegroups.com.

[Francisco Ruiz]

Thanks Ron, Mike,

I'm using this for a self-contained mobile page, where I want to use SJCL to do some PGP-like functions. If you want to take a look, the most recent stable version is always at: http://prgomez.com/ursa 

The reason why I'm using the p521 curve is that I've seen webpages where they say that the security of the p521 ecc is "comparable" to that of 256-bit AES, so to be consistent I'm pairing them in my application. This is not a code for computers to talk to one another, but for people to exchange messages. The p521 curve is not particularly slow, in my tests: the typical operation takes 2 seconds to execute in an iPhone 4S, which is quite acceptable. Using the strongest encryption available is a "selling" point (though the app is free ;-) and I think it gives more time-stability to the public keys that people are going to make. The downside is a slightly slower execution. 

The reason why I wanted a square root function was to halve the size of the public keys displayed. I just added the for loop to calculate the modular square root that Mike suggests, and I can reconstruct the complete public key point from the x component, to be used in a DH scheme and signatures.

At this point the DH scheme works superbly, and fast, but signatures fail half the time, starting from random private keys. Now, Ron Garrett says that I should keep track of the sign of the y component because the square root might produce the wrong sign.

This would happen statistically half the time, which is consistent with the problem I'm seeing, since I don't keep track of the sign of y. So, how do I do this? Is there a function to return the sign of a bn object in SJCL? What function would switch the sign if it's wrong? Forgive my ignorance of basic SJCL methods.

Maybe it would be easier to mess with the signature code and have it accept the wrong sign of pub.y as good?

Thanks!

Francisco

[Francisco Ruiz]

Thanks,

I figured out a workaround:

When the modular square root based on Tonelli-Shanks (in post 4 of this thread, by Mike Hamburg) leads to the wrong root, the other can be found from the fact that the two roots must add to the modulus, so:

if   y1  is one root:

p = curve.field.modulus.copy()      //makes an object containing the modulus

y2 = p.sub(y1)     //produces the other root

I've implemented this in my program, but only for signature verification since the DH exchange seems to work fine even with the wrong root.

Thanks a million! Version 3.2 of URSA will be available soon at http://prgomez.com/ursa

Francisco

[Ron Garret]

On Apr 3, 2013, at 12:26 PM, Francisco Ruiz wrote:

> Thanks,
>
> I figured out a workaround:

Those words should strike fear in the heart of anyone who cares about security.

> When the modular square root based on Tonelli-Shanks (in post 4 of this thread, by Mike Hamburg) leads to the wrong root, the other can be found from the fact that the two roots must add to the modulus

Notice that this is just another way of saying that the two roots are additive inverses, i.e. the two roots are X and -X. :-)

> if y1 is one root:
>
> p = curve.field.modulus.copy() //makes an object containing the modulus
>
> y2 = p.sub(y1) //produces the other root

Yes, but you still need a reliable way of figuring out which root is the one you want. Doing something that seems intuitively correct and empirically produces the right answer is a classic way of introducing subtle security holes.

You really should consider using Curve25519. It has all these details worked out, it's as secure as you'll ever need for any reasonable application, and it's almost certainly faster than anything else with a comparable level of security (if you use code that's optimized for q=2^255-19).

rg