Nikos Mavrogiannopoulos nmav@gnutls.org writes:
On Mon, Feb 18, 2013 at 10:55 AM, Niels Möller nisse@lysator.liu.se wrote:
I'm looking into an interface redesign of the high-level ecdsa, using types
/* Represents a point on the ECC curve */ struct ecc_point { const struct ecc_curve *ecc; /* Allocated using the same allocation function as GMP. */ mp_limb_t *p; };
Wouldn't you need more than one members there? I'd expect x,y,z.
The idea is to use an internal representation which is the same as what the low-level interface expects. So, e.g, if we have 64 bit limbs, and work over the secp256r1 curve, p would point at an area of 8 limbs, where the first 4 represent x and the next 4 represent y.
But you're not expected to need to know the internal representation, just use the get and set functions with coordinates in mpz_t form.
/* Represents a non-zero scalar, an element of Z_q^*, where q is the group order of the curve. */ struct ecc_scalar { const struct ecc_curve *ecc; /* Allocated using the same allocation function as GMP. */ mp_limb_t *p; };
Why not keep the scalar as just a number (i.e. mpz_t)?
mpz_t is not suitable for side-channel silent operations, since it uses a limb count dependent on the actual value. So if you put a value related to the 521-bit curve in an mpz_t, most values would use 9 64-bit limbs, but with a probability of about 1/512 you'd get only 8 limbs.
Is there any advantage in treating it as related to the curve?
Not sure, but if we add some operations, like add, mul, invert, ..., they should all be mod the curve order, and hence need the curve data.
- For the final multiplication in ECDH, do you want the complete point, or do you need the x coordinate only?
For TLS we only need x. I don't know about other protocols. P1363 should discuss some but it is not publicly available (and it is a shame that IETF ECC-TLS only refers to that).
Ok, then it makes sense to have a function to return x only.
- I wonder if I should somehow add some aliases, ecdsa_public_key <=> ecc_point, ecdsa_private_key <=> ecc_scalar?
They could typedefs, or defines, but I don't know whether this would make it more clear.
First question is if it is desirable. If it is, it may be a bit difficult to define cleanly, since I use struct tags rather than typedefs for naming.
- Is there any need to support operations involving the zero point (group zero, curve infinity)? For now, I don't have any high-level function to add two points.
Few implementations don't handle it at all, but couldn't that be the result of an intermediate calculation?
For the most important operation, n * P, you should not get any zero intermediates assuming that P is non-zero to start with, and that n != 0 (mod group order). Except initially when processing leading zero bits of n, which I handle specially in the multiplication code.
So it doesn't seem essential until we support addition of arbitrary points.
And during signing, would it make sense to check if z s_1 = h (here, z is the private key, s_1 is the x coordinate of k G, and h is the message digest), and try a new random k in that case? In addition to the checks for s_1 == 0 or s_2 == 0?
The check looks like a good one on a first read, but isn't it the same as checking for k being 3? (or whatever fixed value).
No, just as for the other checks, the condition depends on both k and h.
Regards, /Niels