I've now pushed some crude code (on the curve25519 branch) which agrees with the test vectors in draft-josefsson-tls-curve25519-05.
It uses the equivalent Edwards curve for the internal operations. For scalar multiplication of the fix generator, it uses Pippenger's algorithm and tables very similar to the other curves, just with different point operations and no special caes (since the Edwards operations are "complete"). At the end, the x-coordinate of the corresponding point on the Montgomery-form curve25519 is computed.
For scalar multiplication of an arbitrary point (with only x coordinate provided), I first have to compute the y-coordinate using Shanks-Tonelli (this could be used to implement "point compression") also for other curves). Then transform to a point on the Edwards curve, using homogeneneous/projective coordinates. Then the actual scalar multiply is currently done with the binary algorithm; I have code for window-based scalar multiply, but it needs a bit more debugging. All this is very similar to the other corves, but without special cases.
Regards, /Niels
You wrote:
I've now pushed some crude code (on the curve25519 branch) which agrees with the test vectors in draft-josefsson-tls-curve25519-05.
Wonderful. There is another document coming out (describing the Curve25519 algo only) which contains test vectors from the NaCl library as well, including them would be good.
/Simon
Simon Josefsson simon@josefsson.org writes:
Wonderful. There is another document coming out (describing the Curve25519 algo only) which contains test vectors from the NaCl library as well, including them would be good.
URL?
I have a couple of questions ragarding curve25519.
1. The input of the curve255519 function is the x coordiante only. I compute the y cordinate, via a square root. This might fail... I don't really understand Theorem 2.1 in the curve25519 paper, but it seems to indicate that for curve25519 to be defined for arbitrary x, one needs to consider coordinates in the extended field
x = x_0 + x_1 sqrt(2) y = y_0 + y_1 sqrt(2)
Obviously I don't want to do this. I think one can get away with treating x inputs where the square root fails as invalid. That shouldn't happen for public keys computed according to the spec.
Are there any testcases for such questionable inputs?
2. API for the curve25519 function. I think I sent a mail about this previously. Should it be a single function (with some magic optimization for the input x == 9), or two functions? What do the NaCl and Sodium libraries do, and do they get it right?
3. I haven't yet figured out how to do the user-api using struct ecc_curve. I think I'll have to make functions like ecc_mul_g and ecc_mul_a go via function pointers in this struct, and also some abstract functions for converting points to and from an unspecified internal coordinate representation, which will be jacobian or edwards, with or without redc.
Internal functions like ecc_add_jja have to move from ecc.h to ecc-internal.h, and there maybe some new more abstract functions for operating on points, regardless of internal coordinate representation.
4. Also, things need to be organized so that curve2519 and EdDSA can share the internals in a clean way. Maybe there could be two struct ecc_curve for the two equivalent curves, which differ only in conversions done on input and output.
Regards, /Niels
"NM" == Niels Möller nisse@lysator.liu.se writes:
SJ>> Wonderful. There is another document coming out (describing the SJ>> Curve25519 algo only) which contains test vectors from the NaCl SJ>> library as well, including them would be good.
NM> URL?
Presumably Sean Turner's draft-turner-thecurve25519function-00.txt
He has a copy at https://seanturner/draft-turner-thecurve25519function
Based on that, it does not look like sqrt is ever required?
-JimC
The URL is: http://tools.ietf.org/html/draft-turner-thecurve25519function-00
/Simon
You wrote:
"NM" == Niels Möller nisse@lysator.liu.se writes:
SJ>> Wonderful. There is another document coming out (describing the SJ>> Curve25519 algo only) which contains test vectors from the NaCl SJ>> library as well, including them would be good.
NM> URL?
Presumably Sean Turner's draft-turner-thecurve25519function-00.txt
He has a copy at https://seanturner/draft-turner-thecurve25519function
Based on that, it does not look like sqrt is ever required?
-JimC
Simon Josefsson simon@josefsson.org writes:
The URL is: http://tools.ietf.org/html/draft-turner-thecurve25519function-00
Hmm. I've had a look. I think the test vector there is identical to the one in your draft, except that the secret keys are random 256-bit values (little endian), *before* the specified masking to force bits 0, 1, 2, 255 = 0 and bit 254 = 1. Which had me confused for a while.
Regards, /Niels
"JC" == James Cloos cloos@jhcloos.com writes:
JC> Based on that, it does not look like sqrt is ever required?
Sorry, I wrote that w/o considering mont->ed conversion. ☹
Does using edwards rather than the pocedure in the draft improve things?
-JimC
James Cloos cloos@jhcloos.com writes:
Does using edwards rather than the pocedure in the draft improve things?
I'm not sure, but at least it makes it easier to use precomputed tables.
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
I have a couple of questions regarding curve25519.
I can answer a few of them myself now.
The input of the curve255519 function is the x coordiante only. I compute the y cordinate, via a square root. This might fail... I don't really understand Theorem 2.1 in the curve25519 paper, but it seems to indicate that for curve25519 to be defined for arbitrary x, one needs to consider coordinates in the extended field
x = x_0 + x_1 sqrt(2) y = y_0 + y_1 sqrt(2)
Doing these coordinates in the extended field just tacks on the factor sqrt(2) on the y coordinates (and similarly to one of the cooordinates of the corresponding Edwards curve), and in this special case, that's equivalent to working on a "twist" curve over the base field F_p.
Probably not too painful to implement, but unclear if it's worth the effort.
Are there any testcases for such questionable inputs?
This question remains, as well as the question of interesting usecases.
- API for the curve25519 function. I think I sent a mail about this previously. Should it be a single function (with some magic optimization for the input x == 9), or two functions? What do the NaCl and Sodium libraries do, and do they get it right?
See http://nacl.cr.yp.to/scalarmult.html. It's two functions,
crypto_scalarmult(q,n,p);
and
crypto_scalarmult_base(q,n);
I think nettle should use some different names (unless, maybe, some curve25519-compat.h file is included). But I think we can use the same arguments. If we don't implement points with y coordinates outside of the base field, the crypto_scalarmult function needs a return value, to indicate success or failure.
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
See http://nacl.cr.yp.to/scalarmult.html. It's two functions,
crypto_scalarmult(q,n,p);
and
crypto_scalarmult_base(q,n);
I think nettle should use some different names (unless, maybe, some curve25519-compat.h file is included). But I think we can use the same arguments. If we don't implement points with y coordinates outside of the base field, the crypto_scalarmult function needs a return value, to indicate success or failure.
Implemented now. The two functions are called curve25519_mul and curve25519_mul_g. The former has a return value, returning failure if the y-coordinate of the given point doesn't belong to the base field (i.e., sqrt fails). Passes the test vectors in http://tools.ietf.org/html/draft-turner-thecurve25519function-00.
The square-root computation done by curve25519_mul is *not* side-channel silent. That could be fixed, but it's not clear to me if that's needed. At least in the DH usecase, the input to the square root is a *public* key, so there's no reason to make efforts to hide it.
Still on the curve25519 branch, but maybe it can be merged soon. Testing and feedback highly appreciated.
Next steps are:
1. Extending struct ecc_curve with more function pointers to support other curves. Review the set of public ecc functions.
2. Benchmarking code.
3. EdDSA (where can I find test vectors for that?).
4. curve25519-specific assembly optimizations. One candidate is an modp_sqr which does the squaring and the reduction all in registers.
Regards, /Niels
I've now merged the curve25519 branch to master. Seems to work fine, but I would expect that it's slower than other implementations; there are *lots* of optimizations left to do. I've done only a little benchmarking, mainly for x86/ecc-25519-modp.asm.
I've also read the ecdsa paper now (http://ed25519.cr.yp.to/ed25519-20110926.pdf), and it suggests several important optimizations, most of which apply to all uses of curve25519.
Things I'd like to do, besides optimizations:
* Switch from the plain Edwards curve to the twist used for Ed25519. Should be pretty a small change.
* Implement Ed25519 signatures.
* Make the ecdsa code work over curve25519. Not that I'd expect anyone to use ecdsa over that curve, but I think it's useful for validating the generality of the ecc interface, and maybe for benchmarking.
* Review the public interface, moving functions which depend on the type of curve out of ecc.h into ecc-internal.h.
As far as optimizations go, I think the most important ones to try are
* Use the faster ecc addition formulas specific to the twist curve.
* Try radix 51 for the mod p operations (outlined in the paper), and write assembly functions for doing squaring and multiplication in registers, without storing intermediate results to memory. This should be quite similar to the arithmetic for poly1305.
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
Things I'd like to do, besides optimizations:
- Switch from the plain Edwards curve to the twist used for Ed25519. Should be pretty a small change.
Done (but not yet pushed to the public repo). With only minor changes to the addition formulas, not yet using the new optimizations which become possible with this curve.
- Implement Ed25519 signatures.
This is the next thing to do, I think, before turning to optimizations. If anyone knows some eddsa25519 test vectors, that would be great. The paper doesn't include any.
- Make the ecdsa code work over curve25519. Not that I'd expect anyone to use ecdsa over that curve, but I think it's useful for validating the generality of the ecc interface, and maybe for benchmarking.
Works now, and with little impact on the normal use of ecdsa (for a while I feared it would add useless overhead for operatinos using the other curves, which I find inappropriate).
- Review the public interface, moving functions which depend on the type of curve out of ecc.h into ecc-internal.h.
Not started, but I'm getting a better idea of how it should look like.
Also, I think I'll replace
struct ecc_curve nettle_curve25519;
by
struct ecc_curve nettle_ed25519; /* or whatever name is appropriate */
since this curve is what's really implemented, and it's better defined. The spec for curve25519 doesn't define the sign of the generator (which is the sign of the y coordinate) so to provide ecc operations that involve the y coordiante as input or output, I have to choose a sign, and that can't be expected to interoperate with anything else anyway.
Regards, /Niels
On Fri, Aug 29, 2014 at 2:27 PM, Niels Möller nisse@lysator.liu.se wrote:
Things I'd like to do, besides optimizations:
- Switch from the plain Edwards curve to the twist used for Ed25519. Should be pretty a small change.
Done (but not yet pushed to the public repo). With only minor changes to the addition formulas, not yet using the new optimizations which become possible with this curve.
- Implement Ed25519 signatures.
This is the next thing to do, I think, before turning to optimizations. If anyone knows some eddsa25519 test vectors, that would be great. The paper doesn't include any.
I know that ligcrypt added eddsa support recently and they use the vectors from http://ed25519.cr.yp.to/python/sign.input
regards, Nikos
Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:
I know that ligcrypt added eddsa support recently and they use the vectors from http://ed25519.cr.yp.to/python/sign.input
Thanks, I'll have a look at that. And I've found the python program to process that file as well.
Regards, /Niels
nisse@lysator.liu.se (Niels Möller) writes:
Also, I think I'll replace
struct ecc_curve nettle_curve25519;
by
struct ecc_curve nettle_ed25519; /* or whatever name is appropriate */
since this curve is what's really implemented, and it's better defined.
Done now, except for the renaming. This means, that for input and output, coordinates represent points on the -1 twisted Edwards curve. It's only the curve25519_mul* functions which use the Montgomery curve for inputs and outputs.
For the renaming, I'm no longer sure that's a good idea. http://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html seems to recommend "curve25519" as the name of the curve, regardless of which coordinates are used.
Regards, /Niels
I've still looking at eddsa, and how to design the interface. I think we need some structs ed25519_sha512_private_key and ed25519_sha512_public_key, which can keep track of "expanded" keys. And a low-level function, possibly like
void _eddsa_sign (const struct ecc_curve *ecc, const struct nettle_hash *H, const uint8_t *pub, void *k1, const mp_limb_t *k2, size_t length, const uint8_t *msg, uint8_t *signature);
where
ecc is the curve,
H the hash function,
pub is the public key as a string (I don't quite like it, but it is needed in the hashing, and it seems inefficient to have to recompute it from the private key)
k1 is a context struct for the hashing, updated with the secret prefix. And destroyed in the process, so if the caller want's to sing several messages, it should keep a copy.
k2 is the secret scalar
The output is produced as a string, not a pair of bignums, since that's how eddsa is specified.
It's possible to also have an all-in-one functions, say,
ed25519_sha512_sign (const uint8_t *key, size_t length, const uint8_t *msg, uint8_t *signature);
One thing that's a bit unclear is in which form applications will store private keys. Will they be *only* the private key (256 bits, according to the spec), or will they be kept together with the public key? If the public key is not included, it has to be recomputed (which will be pretty fast, but I think it's desirable to do it once, when the key is read, not for each signature created). It could be an optional input somewhere in the interface.
nisse@lysator.liu.se (Niels Möller) writes:
And a low-level function, possibly like
void _eddsa_sign (const struct ecc_curve *ecc, const struct nettle_hash *H, const uint8_t *pub, void *k1, const mp_limb_t *k2, size_t length, const uint8_t *msg, uint8_t *signature);
Something very similar to this is now implemented, including a couple of tests. We also need a helper function to expand a private key, generating the three arguments pub, k1, and k2 above; currently there's code to do that in the test program, and it's a bit error prone. And then corresponding _eddsa_verify, and the higher-level more user-friendly functions.
Regards, /Niels
I've pushed some eddsa internal functions to the repo the last few weeks.
Now I have an initial implementation of some friendlier high-level functions for ed25519-sha512 signatures. Patch below, comments appreciated, in particular on the interface.
I have a test program that can process http://ed25519.cr.yp.to/python/sign.input successfully. But that input file is a bit large (2.4M, or 670K after lzip --best), so I hesitate before just including a copy of it in the testsuite directory.
Regards, /Niels
diff --git a/Makefile.in b/Makefile.in index 7006211..19269af 100644 --- a/Makefile.in +++ b/Makefile.in @@ -178,6 +178,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ curve25519-mul-g.c curve25519-mul.c curve25519-eh-to-x.c \ eddsa-compress.c eddsa-decompress.c eddsa-expand.c \ eddsa-hash.c eddsa-sign.c eddsa-verify.c \ + ed25519-sha512-sign.c ed25519-sha512-verify.c \ $(OPT_HOGWEED_SOURCES)
HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h \ diff --git a/ed25519-sha512-sign.c b/ed25519-sha512-sign.c new file mode 100644 index 0000000..d401621 --- /dev/null +++ b/ed25519-sha512-sign.c @@ -0,0 +1,69 @@ +/* ed25519-sha512-sign.c + + Copyright (C) 2014 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "eddsa.h" + +#include "ecc-internal.h" + +void +ed25519_sha512_set_private_key (struct ed25519_private_key *priv, + const uint8_t *key) +{ + mp_size_t itch = _eddsa_expand_key_itch (&nettle_curve25519); + mp_limb_t *scratch = gmp_alloc_limbs (itch); + struct sha512_ctx ctx; + + _eddsa_expand_key (&nettle_curve25519, &nettle_sha512, &ctx, + key, priv->pub, priv->k1, priv->k2, scratch); + gmp_free_limbs (scratch, itch); +} + +void +ed25519_sha512_sign (const struct ed25519_private_key *priv, + size_t length, const uint8_t *msg, + uint8_t *signature) +{ + mp_size_t itch = _eddsa_sign_itch (&nettle_curve25519); + mp_limb_t *scratch = gmp_alloc_limbs (itch); + struct sha512_ctx ctx; + + sha512_init (&ctx); + sha512_update (&ctx, ED25519_KEY_SIZE, priv->k1); + _eddsa_sign (&nettle_curve25519, &nettle_sha512, priv->pub, + &ctx, + priv->k2, length, msg, signature, scratch); + + gmp_free_limbs (scratch, itch); +} diff --git a/ed25519-sha512-verify.c b/ed25519-sha512-verify.c new file mode 100644 index 0000000..f8d781a --- /dev/null +++ b/ed25519-sha512-verify.c @@ -0,0 +1,74 @@ +/* ed25519-sha512-sign.c + + Copyright (C) 2014 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <string.h> + +#include "eddsa.h" + +#include "ecc-internal.h" + +int +ed25519_sha512_set_public_key (struct ed25519_public_key *pub, + const uint8_t *key) +{ + mp_size_t itch = _eddsa_decompress_itch (&nettle_curve25519); + mp_limb_t *scratch = gmp_alloc_limbs (itch); + int res; + + memcpy (pub->pub, key, sizeof(pub->pub)); + res =_eddsa_decompress (&nettle_curve25519, + pub->A, key, scratch); + + gmp_free_limbs (scratch, itch); + return res; +} + +int +ed25519_sha512_verify (const struct ed25519_public_key *pub, + size_t length, const uint8_t *msg, + const uint8_t *signature) +{ + mp_size_t itch = _eddsa_verify_itch (&nettle_curve25519); + mp_limb_t *scratch = gmp_alloc_limbs (itch); + struct sha512_ctx ctx; + int res; + + res = _eddsa_verify (&nettle_curve25519, &nettle_sha512, + pub->pub, pub->A, &ctx, + length, msg, signature, + scratch); + gmp_free_limbs (scratch, itch); + return res; +} diff --git a/eddsa.h b/eddsa.h index 5021486..68a6b1c 100644 --- a/eddsa.h +++ b/eddsa.h @@ -35,12 +35,18 @@ #include "nettle-types.h"
#include "bignum.h" +#include "sha2.h"
#ifdef __cplusplus extern "C" { #endif
/* Name mangling */ +#define ed25519_sha512_set_private_key nettle_ed25519_sha512_set_private_key +#define ed25519_sha512_sign nettle_ed25519_sha512_sign +#define ed25519_sha512_set_public_key nettle_ed25519_sha512_set_public_key +#define ed25519_sha512_verify nettle_ed25519_sha512_verify + #define _eddsa_compress _nettle_eddsa_compress #define _eddsa_compress_itch _nettle_eddsa_compress_itch #define _eddsa_decompress _nettle_eddsa_decompress @@ -54,6 +60,44 @@ extern "C" { #define _eddsa_verify_itch _nettle_eddsa_verify_itch
#define ED25519_KEY_SIZE 32 +#define ED25519_SIGNATURE_SIZE 64 + +/* Number of limbs needed to represent a point koordinate, or a secret + exponent (note that exponents are 254 bits, larger than q). */ +#define _ED25519_LIMB_SIZE ((255 + (GMP_NUMB_BITS - 1)) / GMP_NUMB_BITS) + +struct ed25519_private_key +{ + uint8_t pub[ED25519_KEY_SIZE]; + uint8_t k1[ED25519_KEY_SIZE]; + mp_limb_t k2[_ED25519_LIMB_SIZE]; +}; + +void +ed25519_sha512_set_private_key (struct ed25519_private_key *priv, + const uint8_t *key); + +void +ed25519_sha512_sign (const struct ed25519_private_key *priv, + size_t length, const uint8_t *msg, + uint8_t *signature); + +struct ed25519_public_key +{ + uint8_t pub[ED25519_KEY_SIZE]; + mp_limb_t A[2*_ED25519_LIMB_SIZE]; +}; + +int +ed25519_sha512_set_public_key (struct ed25519_public_key *pub, + const uint8_t *key); + +int +ed25519_sha512_verify (const struct ed25519_public_key *pub, + size_t length, const uint8_t *msg, + const uint8_t *signature); + +/* Low-level internal functions */
struct ecc_curve; struct ecc_modulo;
nisse@lysator.liu.se (Niels Möller) writes:
Now I have an initial implementation of some friendlier high-level functions for ed25519-sha512 signatures.
Pushed now.
I have a test program that can process http://ed25519.cr.yp.to/python/sign.input successfully. But that input file is a bit large (2.4M, or 670K after lzip --best), so I hesitate before just including a copy of it in the testsuite directory.
Also added, as testsuite/ed25519-test.c. By default, it uses just the first four lines (copied into the source file). But if ED25519_SIGN_INPUT is set in the environment, it will open and process that file instead.
Regards, /Niels
nettle-bugs@lists.lysator.liu.se
-
James Cloos -
Nikos Mavrogiannopoulos -
nisse＠lysator.liu.se -
Simon Josefsson