Ian Goldberg tor@cypherpunks.ca writes:
On Thu, Apr 20, 2017 at 03:40:58PM +0300, George Kadianakis wrote:
Hey Ian,
so the current problem with ed25519-donna is that when I'm doing the above, I'm getting the following 32-byte key after ge25519_pack(). Here it is hexed up:
0x0100000000000000000000000000000000000000000000000000000000000000I don't see any methods in ed25519-donna for checking a point or a packed point to see if it's the point at infinity (identity element).
There actually is such a function, but it's buried in a weird place. ge25519_is_neutral_vartime in ed25519-donna-batchverify.h does what you want, but it's static, so you would need to copy it (and remove the line involving batch_point_buffer). Probably not worthwhile.
I can easily believe the representation of the identity (neutral) element in ed25519 is the hex value above. (And it is; see below.)
I've been assuming that the point at infinity would be an all-zeroes 32-byte array, because that's what we are doing in curve25519, but I actually have no idea how the array representation of ge25519_pack() works. Here is our process for curve25519: https://gitweb.torproject.org/tor.git/tree/src/common/crypto_curve25519.c#n1...
Curve25519 only outputs the x coordinate, which is indeed 0, so you get the all-zero value. ed25519 outputs the y coordinate (which is the 255-bit value 0x000...0001 in little-endian format) and the single-bit parity of the x coordinate (which is 0), so you do get the hex you give above. (The identity element is the point (0,1) in Edwards curves, not actually the point at infinity.)
The above packed point is an all zeroes 32-byte string, apart from the very first bit which is set. Could it be that the first bit is the compressed sign of the 'x' coordinate or something, and that's actually the point at infinity?
But then what's the right way to check for the point at infinity? Check that everything is 0 apart from the first sign bit?
Yes, pack the point, and compare it to the above 32-byte value.
And after I figure this out, I need to do the same for the reference implementation of ed25519, because as it seems Tor uses two simultaneous implementations of ed25519: https://gitweb.torproject.org/tor.git/tree/src/ext/ed25519
Yes, hopefully that implementation packs points in the same way!
Thanks for the help Ian :) Very much appreciated!
No worries.
[CCing tor-dev since people might find it interesting]
Thanks for the advice Ian :)
With your help, I have now implemented the validation check. Check out the ticket #22006 and the branch `bug22006` here: https://gitweb.torproject.org/user/asn/tor.git/commit/?h=bug22006&id=628...
One last thing I'd like to do here is test our validation function against a pubkey with torsion component to make sure that it gets rejected. How would you go about generating such a pubkey?
I was thinking of using the CRT to find an integer a \in Z, s.t a == 0 (mod l) && a == 1 (mod 8) but then I didn't know how to go from that scalar with a torsion component to an ed25519 point...
Cheers!