From c578d5d85b11f004c151948684ca5753a5ac5962 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 10 May 2017 21:58:36 +0100 Subject: [PATCH] pub/ed448.[ch], etc.: Add the Ed448 signature scheme from RFC8032. --- progs/catcrypt.1 | 22 +++ progs/catsign.1 | 22 +++ progs/cc-sig.c | 5 +- progs/dsig.1 | 22 +++ progs/key.1 | 7 + progs/key.c | 4 +- progs/perftest.c | 53 ++++++ pub/Makefile.am | 6 + pub/ed448.c | 564 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ pub/ed448.h | 144 ++++++++++++++ pub/t/ed448 | 228 ++++++++++++++++++++++ pub/x448.h | 3 +- 12 files changed, 1077 insertions(+), 3 deletions(-) create mode 100644 pub/ed448.c create mode 100644 pub/ed448.h create mode 100644 pub/t/ed448 diff --git a/progs/catcrypt.1 b/progs/catcrypt.1 index 143b2c52..6c554408 100644 --- a/progs/catcrypt.1 +++ b/progs/catcrypt.1 @@ -445,6 +445,24 @@ command .BR key (1)) to generate the key. .TP +.B ed448 +This is Bernstein, Duif, Lange, Schwabe, and Yang's EdDSA algorithm, +using Hamburg's Ed448-Goldilocks elliptic curve, +as specified in RFC8032. +More specifically, this is HashEd448 +using the selected +.B hash +algorithm \(en by default +.BR sha3-512 . +Use the +.B ed448 +algorithm of the +.B key add +command +(see +.BR key (1)) +to generate the key. +.TP .B mac This uses a symmetric message-authentication algorithm rather than a digital signature. The precise message-authentication scheme used is @@ -488,6 +506,10 @@ For .BR ed25519 , the default hash function is .BR sha512 . +For +.BR ed448 , +the default hash function is +.BR shake256 . .PP Run .B catcrypt show hash diff --git a/progs/catsign.1 b/progs/catsign.1 index 3aed8ed5..937e05f8 100644 --- a/progs/catsign.1 +++ b/progs/catsign.1 @@ -262,6 +262,24 @@ command .BR key (1)) to generate the key. .TP +.B ed448 +This is Bernstein, Duif, Lange, Schwabe, and Yang's EdDSA algorithm, +using Hamburg's Ed448-Goldilocks elliptic curve, +as specified in RFC8032. +More specifically, this is HashEd448 +using the selected +.B hash +algorithm \(en by default +.BR sha3-512 . +Use the +.B ed448 +algorithm of the +.B key add +command +(see +.BR key (1)) +to generate the key. +.TP .B mac This uses a symmetric message-authentication algorithm rather than a digital signature. The precise message-authentication scheme used is @@ -305,6 +323,10 @@ For .BR ed25519 , the default hash function is .BR sha512 . +For +.BR ed448 , +the default hash function is +.BR shake256 . .PP Run .B catsign show hash diff --git a/progs/cc-sig.c b/progs/cc-sig.c index fb5e1c3d..a416c6e5 100644 --- a/progs/cc-sig.c +++ b/progs/cc-sig.c @@ -37,6 +37,7 @@ #include "sha.h" #include "has160.h" #include "sha512.h" +#include "sha3.h" #include "ct.h" #include "ec.h" @@ -46,6 +47,7 @@ #include "gkcdsa.h" #include "rsa.h" #include "ed25519.h" +#include "ed448.h" #include "cc.h" @@ -577,7 +579,8 @@ static const sigops eckcdsa_vrf = { /* --- EdDSA --- */ #define EDDSAS(_) \ - _(ed25519, ed25519ctx, ED25519, "Ed25519", sha512) + _(ed25519, ed25519ctx, ED25519, "Ed25519", sha512) \ + _(ed448, ed448, ED448, "Ed448", shake256) typedef struct eddsa_sigctx { sig s; diff --git a/progs/dsig.1 b/progs/dsig.1 index 72753f5f..aaeff42d 100644 --- a/progs/dsig.1 +++ b/progs/dsig.1 @@ -208,6 +208,24 @@ command (see .BR key (1)) to generate the key. +.TP +.B ed448 +This is Bernstein, Duif, Lange, Schwabe, and Yang's EdDSA algorithm, +using Hamburg's Ed448-Goldilocks elliptic curve, +as specified in RFC8032. +More specifically, this is HashEd448 +using the selected +.B hash +algorithm \(en by default +.BR sha3-512 . +Use the +.B ed448 +algorithm of the +.B key add +command +(see +.BR key (1)) +to generate the key. .PP As well as the signature algorithm itself, a hash function is used. This is taken from the @@ -237,6 +255,10 @@ For .BR ed25519 , the default hash function is .BR sha512 . +For +.BR ed448 , +the default hash function is +.BR shake256 . .PP Run .B dsig show hash diff --git a/progs/key.1 b/progs/key.1 index 0ffd0769..47a0efee 100644 --- a/progs/key.1 +++ b/progs/key.1 @@ -877,6 +877,13 @@ The private key is simply a random 256-bit string, from which a scalar and secret prefix are derived; the public key is the compressed form of the corresponding point. .TP +.B ed448 +Generate a private key and a corresponding public point on the +(Edwards-form) Ed448-Goldilocks elliptic curve. +The private key is simply a random 456-bit string, +from which a scalar and secret prefix are derived; +the public key is the compressed form of the corresponding point. +.TP .B empty Generate an empty key, with trivial contents. This is useful as a `parameters' key, diff --git a/progs/key.c b/progs/key.c index 74060cd1..0c817d4d 100644 --- a/progs/key.c +++ b/progs/key.c @@ -73,6 +73,7 @@ #include "x25519.h" #include "x448.h" #include "ed25519.h" +#include "ed448.h" #include "cc.h" #include "sha-mgf.h" @@ -975,7 +976,8 @@ XDHS(XDHALG) #undef XDHALG #define EDDSAS(_) \ - _(ed25519, ED25519, "Ed25519") + _(ed25519, ED25519, "Ed25519") \ + _(ed448, ED448, "Ed448") #define EDDSAALG(ed, ED, name) \ \ diff --git a/progs/perftest.c b/progs/perftest.c index 80f060aa..f064c2aa 100644 --- a/progs/perftest.c +++ b/progs/perftest.c @@ -67,6 +67,7 @@ #include "x25519.h" #include "x448.h" #include "ed25519.h" +#include "ed448.h" #include "cc.h" #include "gcipher.h" @@ -361,6 +362,56 @@ static void ed25519_vrfrun(void *cc) ed25519_verify(c->K, c->m, sizeof(c->m), c->sig); } +/* --- Ed448 --- */ + +typedef struct ed448_signctx { + octet k[ED448_KEYSZ]; + octet K[ED448_PUBSZ]; + octet m[64]; +} ed448_signctx; + +typedef struct ed448_vrfctx { + octet K[ED448_PUBSZ]; + octet m[64]; + octet sig[ED448_SIGSZ]; +} ed448_vrfctx; + +static void *ed448_signinit(opts *o) +{ + ed448_signctx *c = CREATE(ed448_signctx); + + rand_get(RAND_GLOBAL, c->k, sizeof(c->k)); + rand_get(RAND_GLOBAL, c->m, sizeof(c->m)); + ed448_pubkey(c->K, c->k, sizeof(c->k)); + return (c); +} + +static void ed448_signrun(void *cc) +{ + ed448_signctx *c = cc; + octet sig[ED448_SIGSZ]; + + ed448_sign(sig, c->k, sizeof(c->k), c->K, 0, 0, 0, c->m, sizeof(c->m)); +} + +static void *ed448_vrfinit(opts *o) +{ + octet k[ED448_KEYSZ]; + ed448_vrfctx *c = CREATE(ed448_vrfctx); + + rand_get(RAND_GLOBAL, k, sizeof(k)); + rand_get(RAND_GLOBAL, c->m, sizeof(c->m)); + ed448_pubkey(c->K, k, sizeof(k)); + ed448_sign(c->sig, k, sizeof(k), c->K, 0, 0, 0, c->m, sizeof(c->m)); + return (c); +} + +static void ed448_vrfrun(void *cc) +{ + ed448_vrfctx *c = cc; + ed448_verify(c->K, 0, 0, 0, c->m, sizeof(c->m), c->sig); +} + /* --- RSA --- */ typedef struct rsapriv_ctx { @@ -584,6 +635,8 @@ static const jobops jobtab[] = { { "x448", x448_jobinit, x448_jobrun }, { "ed25519-sign", ed25519_signinit, ed25519_signrun }, { "ed25519-vrf", ed25519_vrfinit, ed25519_vrfrun }, + { "ed448-sign", ed448_signinit, ed448_signrun }, + { "ed448-vrf", ed448_vrfinit, ed448_vrfrun }, { "ksched", ksched_init, ksched_run }, { "enc", enc_init, enc_run }, { "hash", hash_init, hash_run }, diff --git a/pub/Makefile.am b/pub/Makefile.am index 98c0a15f..e21355e4 100644 --- a/pub/Makefile.am +++ b/pub/Makefile.am @@ -128,4 +128,10 @@ libpub_la_SOURCES += x448.c TESTS += x448.t$(EXEEXT) EXTRA_DIST += t/x448 +## Ed448: Bernstein's EdDSA over Hamburg's Ed448-Goldilocks curve. +pkginclude_HEADERS += ed448.h +libpub_la_SOURCES += ed448.c +TESTS += ed448.t$(EXEEXT) +EXTRA_DIST += t/ed448 + ###----- That's all, folks -------------------------------------------------- diff --git a/pub/ed448.c b/pub/ed448.c new file mode 100644 index 00000000..a3a94214 --- /dev/null +++ b/pub/ed448.c @@ -0,0 +1,564 @@ +/* -*-c-*- + * + * The Ed448 signature scheme + * + * (c) 2017 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include + +#include "fgoldi.h" +#include "ed448.h" +#include "scaf.h" +#include "scmul.h" +#include "sha3.h" + +/*----- Key fetching ------------------------------------------------------*/ + +const key_fetchdef ed448_pubfetch[] = { + { "pub", offsetof(ed448_pub, pub), KENC_BINARY, 0 }, + { 0, 0, 0, 0 } +}; + +static const key_fetchdef priv[] = { + { "priv", offsetof(ed448_priv, priv), KENC_BINARY, 0 }, + { 0, 0, 0, 0 } +}; + +const key_fetchdef ed448_privfetch[] = { + { "pub", offsetof(ed448_priv, pub), KENC_BINARY, 0 }, + { "private", 0, KENC_STRUCT, priv }, + { 0, 0, 0, 0 } +}; + +/*----- A number of magic numbers -----------------------------------------*/ + +#if SCAF_IMPL == 32 +# define PIECEWD 24 + static const scaf_piece l[] = { + 0x5844f3, 0xc292ab, 0x552378, 0x8dc58f, 0x6cc272, + 0x369021, 0x49aed6, 0xc44edb, 0xca23e9, 0xffff7c, + 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0xffffff, + 0xffffff, 0xffffff, 0xffffff, 0x003fff + }; + static const scaf_piece mu[] = { + 0xe0d00a, 0x4a7bb0, 0x73d6d5, 0x0aadc8, 0xd723a7, + 0xe933d8, 0x9c96fd, 0x4b6512, 0x63bb12, 0x335dc1, + 0x000008, 0x000000, 0x000000, 0x000000, 0x000000, + 0x000000, 0x000000, 0x000000, 0x000000, 0x000400 + }; +#endif + +#if SCAF_IMPL == 16 +# define PIECEWD 12 + static const scaf_piece l[] = { + 0x4f3, 0x584, 0x2ab, 0xc29, 0x378, 0x552, 0x58f, 0x8dc, + 0x272, 0x6cc, 0x021, 0x369, 0xed6, 0x49a, 0xedb, 0xc44, + 0x3e9, 0xca2, 0xf7c, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, + 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, + 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0x003 + }; + static const scaf_piece mu[] = { + 0x00a, 0xe0d, 0xbb0, 0x4a7, 0x6d5, 0x73d, 0xdc8, 0x0aa, + 0x3a7, 0xd72, 0x3d8, 0xe93, 0x6fd, 0x9c9, 0x512, 0x4b6, + 0xb12, 0x63b, 0xdc1, 0x335, 0x008, 0x000, 0x000, 0x000, + 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, + 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x400 + }; +#endif + +#define NPIECE SCAF_NPIECE(448, PIECEWD) + +#if FGOLDI_IMPL == 28 +# define P p28 + static const fgoldi_piece bx_pieces[] = { + 118276190, 40534716, 9670182, -133293904, + 85017404, -9262234, 68333083, -96650682, + -93461723, 15824511, 73756743, 57518561, + 94773951, -19783215, 107736334, 82941708 + }, by_pieces[] = { + 36764180, 8885695, 130592152, 20104429, + -104530499, 30304196, 121295871, 5901357, + 125344798, -96893944, -93097107, -59366209, + 3626698, 38307682, 24032956, 110359655 + }; +#endif +#if FGOLDI_IMPL == 12 +# define P p12 + static const fgoldi_piece bx_pieces[] = { + 94, 204, -114, 523, 309, -474, 313, -511, 99, -1017, + 828, 276, -822, 686, -71, -485, 299, 200, -791, -737, + 805, -290, -43, -550, 121, 71, -425, -983, -344, 439, + 703, 610, 555, 135, -151, -754, -321, 397, -420, 633 + }, by_pieces[] = { + -1516, 784, -28, -425, 68, -616, -885, -592, 788, 153, + -579, -944, 116, 415, 231, 1023, 941, -594, 49, 45, + -994, -118, 271, -496, -739, 877, -201, -43, 147, -453, + 1738, 885, -960, 542, 292, 1724, -277, -797, -46, 842 + }; +#endif + +static const fgoldi_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ }; +#define BX ((const fgoldi *)bx_pieces) +#define BY ((const fgoldi *)by_pieces) +#define BZ ((const fgoldi *)bz_pieces) +#define D (-39081) + +/*----- Point encoding and decoding ---------------------------------------*/ + +static void ptencode(octet q[57], + const fgoldi *X, const fgoldi *Y, const fgoldi *Z) +{ + fgoldi x, y, t; + octet b[56]; + + fgoldi_inv(&t, Z); fgoldi_mul(&x, X, &t); fgoldi_mul(&y, Y, &t); + fgoldi_store(q, &y); fgoldi_store(b, &x); q[56] = (b[0]&1u) << 7; +} + +static int ptdecode(fgoldi *X, fgoldi *Y, fgoldi *Z, const octet q[57]) +{ + octet b[56]; + unsigned i, a; + fgoldi t, u; + uint32 m; + int rc = 0; + + /* Load the y-coordinate. */ + fgoldi_load(Y, q); + + /* Check that the coordinate was in range. If we store it, we'll get a + * canonical version which we can compare against Q. Also, check that the + * extra bits in the top byte are zero. + */ + fgoldi_store(b, Y); + for (i = a = 0; i < 56; i++) a |= b[i] ^ q[i]; + a |= q[56]&0x7fu; + a = ((a - 1) >> 8)&0x01u; /* 0 |-> 1, non-0 |-> 0 */ + rc |= (int)a - 1; + + /* Decompress the x-coordinate. */ + fgoldi_sqr(&t, Y); fgoldi_mulconst(&u, &t, D); t.P[0] -= 1; u.P[0] -= 1; + rc |= fgoldi_quosqrt(X, &t, &u); + fgoldi_store(b, X); m = -(uint32)(((q[56] >> 7) ^ b[0])&0x1u); + fgoldi_condneg(X, X, m); + + /* Set Z. */ + fgoldi_set(Z, 1); + + /* And we're done. */ + return (rc); +} + +/*----- Edwards curve arithmetic ------------------------------------------*/ + +static void ptadd(fgoldi *X, fgoldi *Y, fgoldi *Z, + const fgoldi *X0, const fgoldi *Y0, const fgoldi *Z0, + const fgoldi *X1, const fgoldi *Y1, const fgoldi *Z1) +{ + fgoldi t0, t1, t2, t3; + + /* Bernstein and Lange, `Faster addition and doubling on elliptic curves', + * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows + * the formulae as: + * + * A = Z1 Z2; B = A^2; C = X1 X2; D = Y1 Y2; + * E = d C D; F = B - E; G = B + E; + * X3 = A F ((X1 + Y1) (X2 + Y2) - C - D); + * Y3 = A G (D - C); Z3 = c F G. + * + * But c = 1 here. + */ + + fgoldi_mul(&t0, Z0, Z1); /* t0 = A = Z0 Z1 */ + fgoldi_add(&t1, X0, Y0); /* t1 = X0 + Y0 */ + fgoldi_add(&t2, X1, Y1); /* t2 = X1 + Y1 */ + fgoldi_mul(&t1, &t1, &t2); /* t1 = (X0 + Y0) (X1 + Y1) */ + fgoldi_mul(&t2, X0, X1); /* t2 = C = X0 X1 */ + fgoldi_mul(&t3, Y0, Y1); /* t3 = D = Y0 Y1 */ + fgoldi_sub(X, &t1, &t2); /* X = (X0 + Y0) (X1 + Y1) - C */ + fgoldi_sub(X, X, &t3); /* X = (X0 + Y0) (X1 + Y1) - C - D */ + fgoldi_sub(Y, &t3, &t2); /* Y = D - C */ + fgoldi_mul(X, X, &t0); /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */ + fgoldi_mul(Y, Y, &t0); /* Y = A (D - C) */ + fgoldi_sqr(&t0, &t0); /* t0 = B = A^2 */ + fgoldi_mul(&t1, &t2, &t3); /* t1 = C D */ + fgoldi_mulconst(&t1, &t1, D); /* t1 = E = d C D */ + fgoldi_sub(&t2, &t0, &t1); /* t2 = F = B - E */ + fgoldi_add(&t1, &t0, &t1); /* t1 = G = B + E */ + fgoldi_mul(X, X, &t2); /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */ + fgoldi_mul(Y, Y, &t1); /* Y = A G (D - C) */ + fgoldi_mul(Z, &t1, &t2); /* Z = c F G */ +} + +static void ptdbl(fgoldi *X, fgoldi *Y, fgoldi *Z, + const fgoldi *X0, const fgoldi *Y0, const fgoldi *Z0) +{ + fgoldi t0, t1, t2; + + /* Bernstein and Lange, `Faster addition and doubling on elliptic curves', + * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows + * the formulae as: + * + * B = (X1 + Y1)^2; C = X1^2; D = Y1^2; + * E = C + D; H = (c Z1)^2; J = E - 2 H; + * X3 = c (B - E) J; Y3 = c E (C - D); Z3 = E J + * + * But c = 1 here. + */ + + fgoldi_add(&t0, X0, Y0); /* t0 = X0 + Y0 */ + fgoldi_sqr(&t0, &t0); /* t0 = B = (X0 + Y0)^2 */ + fgoldi_sqr(&t1, X0); /* t1 = C = X0^2 */ + fgoldi_sqr(&t2, Y0); /* t2 = D = Y0^2 */ + fgoldi_add(Y, &t1, &t2); /* Y = E = C + D */ + fgoldi_sub(&t1, &t1, &t2); /* t1 = C - D */ + fgoldi_sub(X, &t0, Y); /* X = c (B - E) */ + fgoldi_sqr(&t0, Z0); /* t0 = H = (c Z0)^2 */ + fgoldi_mulconst(&t0, &t0, 2); /* t0 = 2 H */ + fgoldi_sub(&t0, Y, &t0); /* t0 = J = E - 2 H */ + fgoldi_mul(X, X, &t0); /* X = c (B - E) J */ + fgoldi_mul(Z, Y, &t0); /* Z = E J */ + fgoldi_mul(Y, Y, &t1); /* Y = c E (C - D) */ +} + +static DEFINE_SCMUL(ptmul, fgoldi, 4, PIECEWD, NPIECE, ptadd, ptdbl) +static DEFINE_SCSIMMUL(ptsimmul, fgoldi, 2, PIECEWD, NPIECE, ptadd, ptdbl) + +/*----- Key derivation utilities ------------------------------------------*/ + +static void unpack_key(scaf_piece a[NPIECE], octet h1[57], + const octet *k, size_t ksz) +{ + shake_ctx h; + octet b[57]; + + shake256_init(&h); shake_hash(&h, k, ksz); + shake_xof(&h); shake_get(&h, b, sizeof(b)); + b[0] &= 0xfcu; b[55] |= 0x80u; scaf_load(a, b, 56, NPIECE, PIECEWD); + if (h1) shake_get(&h, h1, 57); +} + +#define PREFIX_BUFSZ 266 +static size_t prefix(octet b[PREFIX_BUFSZ], + int phflag, const octet *p, size_t psz) +{ + memcpy(b, "SigEd448", 8); + b[8] = phflag; + assert(psz <= ED448_MAXPERSOSZ); b[9] = psz; memcpy(b + 10, p, psz); + return (psz + 10); +} + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @ed448_pubkey@ --- * + * + * Arguments: @octet K[ED448_PUBSZ]@ = where to put the public key + * @const void *k@ = private key + * @size_t ksz@ = length of private key + * + * Returns: --- + * + * Use: Derives the public key from a private key. + */ + +void ed448_pubkey(octet K[ED448_PUBSZ], const void *k, size_t ksz) +{ + scaf_piece a[NPIECE]; + fgoldi AX, AY, AZ; + + unpack_key(a, 0, k, ksz); + ptmul(&AX, &AY, &AZ, a, BX, BY, BZ); + ptencode(K, &AX, &AY, &AZ); +} + +/* --- @ed448_sign@ --- * + * + * Arguments: @octet sig[ED448_SIGSZ]@ = where to put the signature + * @const void *k@ = private key + * @size_t ksz@ = length of private key + * @const octet K[ED448_PUBSZ]@ = public key + * @int phflag@ = whether the `message' has been hashed already + * @const void *p@ = personalization string + * @size_t psz@ = length of personalization string + * @const void *m@ = message to sign + * @size_t msz@ = length of message + * + * Returns: --- + * + * Use: Signs a message. + */ + +void ed448_sign(octet sig[ED448_SIGSZ], + const void *k, size_t ksz, const octet K[ED448_PUBSZ], + int phflag, const void *p, size_t psz, + const void *m, size_t msz) +{ + shake_ctx h; + scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE + 1]; + scaf_dblpiece tt[2*NPIECE]; + fgoldi RX, RY, RZ; + octet h1[57], pb[PREFIX_BUFSZ], rb[114]; + unsigned i; + + /* Get my private key. */ + unpack_key(a, h1, k, ksz); + + /* Determine the prefix string. */ + psz = prefix(pb, phflag, p, psz); + + /* Select the nonce and the vector part. */ + shake256_init(&h); + shake_hash(&h, pb, psz); + shake_hash(&h, h1, sizeof(h1)); + shake_hash(&h, m, msz); + shake_done(&h, rb, 114); + scaf_loaddbl(tt, rb, 114, 2*NPIECE, PIECEWD); + scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch); + ptmul(&RX, &RY, &RZ, r, BX, BY, BZ); + ptencode(sig, &RX, &RY, &RZ); + + /* Calculate the scalar part. */ + shake256_init(&h); + shake_hash(&h, pb, psz); + shake_hash(&h, sig, 57); + shake_hash(&h, K, 57); + shake_hash(&h, m, msz); + shake_done(&h, rb, 114); + scaf_loaddbl(tt, rb, 114, 2*NPIECE, PIECEWD); + scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); + scaf_mul(tt, t, a, NPIECE); + for (i = 0; i < NPIECE; i++) tt[i] += r[i]; + scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); + scaf_store(sig + 57, 57, t, NPIECE, PIECEWD); +} + +/* --- @ed448_verify@ --- * + * + * Arguments: @const octet K[ED448_PUBSZ]@ = public key + * @const void *m@ = message to sign + * @int phflag@ = whether the `message' has been hashed already + * @const void *p@ = personalization string + * @size_t psz@ = length of personalization string + * @size_t msz@ = length of message + * @const octet sig[ED448_SIGSZ]@ = signature + * + * Returns: Zero if OK, negative on failure. + * + * Use: Verify a signature. + */ + +int ed448_verify(const octet K[ED448_PUBSZ], + int phflag, const void *p, size_t psz, + const void *m, size_t msz, + const octet sig[ED448_SIGSZ]) +{ + shake_ctx h; + scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE + 1]; + scaf_dblpiece tt[2*NPIECE]; + fgoldi AX, AY, AZ, RX, RY, RZ; + octet b[PREFIX_BUFSZ]; + + /* Unpack the public key. Negate it: we're meant to subtract the term + * involving the public key point, and this is easier than negating the + * scalar. + */ + if (ptdecode(&AX, &AY, &AZ, K)) return (-1); + fgoldi_neg(&AX, &AX); + + /* Load the scalar and check that it's in range. The easy way is to store + * it again and see if the two match. + */ + scaf_loaddbl(tt, sig + 57, 57, 2*NPIECE, PIECEWD); + scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch); + scaf_store(b, 57, s, NPIECE, PIECEWD); + if (memcmp(b, sig + 57, 57) != 0) return (-1); + + /* Check the signature. */ + psz = prefix(b, phflag, p, psz); + shake256_init(&h); + shake_hash(&h, b, psz); + shake_hash(&h, sig, 57); + shake_hash(&h, K, ED448_PUBSZ); + shake_hash(&h, m, msz); + shake_done(&h, b, 114); + scaf_loaddbl(tt, b, 114, 2*NPIECE, PIECEWD); + scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); + ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ); + ptencode(b, &RX, &RY, &RZ); + if (memcmp(b, sig, 57) != 0) return (-1); + + /* All is good. */ + return (0); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +#include +#include + +#include +#include + +static int vrf_pubkey(dstr dv[]) +{ + dstr dpub = DSTR_INIT; + int ok = 1; + + if (dv[1].len != ED448_PUBSZ) die(1, "bad pub length"); + + dstr_ensure(&dpub, ED448_PUBSZ); dpub.len = ED448_PUBSZ; + ed448_pubkey((octet *)dpub.buf, dv[0].buf, dv[0].len); + if (memcmp(dpub.buf, dv[1].buf, ED448_PUBSZ) != 0) { + ok = 0; + fprintf(stderr, "failed!"); + fprintf(stderr, "\n\tpriv = "); type_hex.dump(&dv[0], stderr); + fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dpub, stderr); + fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[1], stderr); + fprintf(stderr, "\n"); + } + + dstr_destroy(&dpub); + return (ok); +} + +static int vrf_sign(dstr *priv, int phflag, dstr *perso, + dstr *msg, dstr *want) +{ + shake_ctx h; + octet K[ED448_PUBSZ]; + dstr d = DSTR_INIT, dsig = DSTR_INIT, *m; + int ok = 1; + + if (want->len != ED448_SIGSZ) die(1, "bad result length"); + + dstr_ensure(&dsig, ED448_SIGSZ); dsig.len = ED448_SIGSZ; + if (phflag <= 0) + m = msg; + else { + dstr_ensure(&d, 64); d.len = 64; + shake256_init(&h); + shake_hash(&h, msg->buf, msg->len); + shake_done(&h, d.buf, d.len); + m = &d; + } + ed448_pubkey(K, priv->buf, priv->len); + ed448_sign((octet *)dsig.buf, priv->buf, priv->len, K, + phflag, perso ? perso->buf : 0, perso ? perso->len : 0, + m->buf, m->len); + if (memcmp(dsig.buf, want->buf, ED448_SIGSZ) != 0) { + ok = 0; + fprintf(stderr, "failed!"); + fprintf(stderr, "\n\tpriv = "); type_hex.dump(priv, stderr); + if (phflag >= 0) { + fprintf(stderr, "\n\t ph = %d", phflag); + fprintf(stderr, "\n\tpers = "); type_hex.dump(perso, stderr); + } + fprintf(stderr, "\n\t msg = "); type_hex.dump(msg, stderr); + if (phflag > 0) + { fprintf(stderr, "\n\thash = "); type_hex.dump(m, stderr); } + fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dsig, stderr); + fprintf(stderr, "\n\twant = "); type_hex.dump(want, stderr); + fprintf(stderr, "\n"); + } + + dstr_destroy(&dsig); + return (ok); +} + +static int vrf_sign_ctx(dstr *dv) + { return (vrf_sign(&dv[0], *(int *)dv[1].buf, &dv[2], &dv[3], &dv[4])); } + +static int vrf_verify(dstr *pub, int phflag, dstr *perso, + dstr *msg, dstr *sig, int rc_want) +{ + shake_ctx h; + int rc_calc; + dstr d = DSTR_INIT, *m; + int ok = 1; + + if (pub->len != ED448_PUBSZ) die(1, "bad pub length"); + if (sig->len != ED448_SIGSZ) die(1, "bad sig length"); + + if (phflag <= 0) + m = msg; + else { + dstr_ensure(&d, 64); d.len = 64; + shake256_init(&h); + shake_hash(&h, msg->buf, msg->len); + shake_done(&h, d.buf, d.len); + m = &d; + } + rc_calc = ed448_verify((const octet *)pub->buf, + phflag, perso ? perso->buf : 0, + perso ? perso->len : 0, + m->buf, m->len, + (const octet *)sig->buf); + if (!rc_want != !rc_calc) { + ok = 0; + fprintf(stderr, "failed!"); + fprintf(stderr, "\n\t pub = "); type_hex.dump(pub, stderr); + if (phflag >= 0) { + fprintf(stderr, "\n\t ph = %d", phflag); + fprintf(stderr, "\n\tpers = "); type_hex.dump(perso, stderr); + } + fprintf(stderr, "\n\t msg = "); type_hex.dump(msg, stderr); + if (phflag > 0) + { fprintf(stderr, "\n\thash = "); type_hex.dump(m, stderr); } + fprintf(stderr, "\n\t sig = "); type_hex.dump(sig, stderr); + fprintf(stderr, "\n\tcalc = %d", rc_calc); + fprintf(stderr, "\n\twant = %d", rc_want); + fprintf(stderr, "\n"); + } + + return (ok); +} + +static int vrf_verify_ctx(dstr *dv) +{ + return (vrf_verify(&dv[0], *(int *)dv[1].buf, &dv[2], + &dv[3], &dv[4], *(int *)dv[5].buf)); +} + +static test_chunk tests[] = { + { "pubkey", vrf_pubkey, { &type_hex, &type_hex } }, + { "sign", vrf_sign_ctx, + { &type_hex, &type_int, &type_hex, &type_hex, &type_hex } }, + { "verify", vrf_verify_ctx, + { &type_hex, &type_int, &type_hex, &type_hex, &type_hex, &type_int } }, + { 0, 0, { 0 } } +}; + +int main(int argc, char *argv[]) +{ + test_run(argc, argv, tests, SRCDIR "/t/ed448"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/pub/ed448.h b/pub/ed448.h new file mode 100644 index 00000000..86a82155 --- /dev/null +++ b/pub/ed448.h @@ -0,0 +1,144 @@ +/* -*-c-*- + * + * The Ed448 signature scheme + * + * (c) 2017 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb 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 Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Notes on the Ed448 signature scheme -------------------------------* + * + * This is Ed448, as described in RFC8032, using the EdDSA signature scheme + * defined by Daniel J. Bernstein, Neils Duif, Simon Josefsson, Tanja Lange, + * Peter Schwabe, and Bo-Yin Yang, `High-speed high-security signatures', + * CHES 2011, https://ed25519.cr.yp.to/ed25519-20110926.pdf and `EdDSA for + * more curves', http://ed25519.cr.yp.to/eddsa-20150704.pdf. + * + * This is not the signature scheme described in Hamburg's paper + * `Ed448-Goldilocks, a new elliptic curve', EUROCRYPT 2016, + * https://eprint.iacr.org/2015/625/, which (a) made use of his `Decaf' + * cofactor elimination technique, and (b) was based on Schnorr rather than + * EdDSA. + * + * This code implements the `Ed448' and `Ed448ph' schemes described in + * RFC8032, though in the latter case it assumes that you've already done the + * hashing and have provided the hash as the `message' input. + */ + +#ifndef CATACOMB_ED448_H +#define CATACOMB_ED448_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +#ifndef CATACOMB_KEY_H +# include "key.h" +#endif + +/*----- Important constants -----------------------------------------------*/ + +#define ED448_KEYSZ 57u +#define ED448_PUBSZ 57u +#define ED448_SIGSZ 114u + +#define ED448_MAXPERSOSZ 255u + +/*----- Key fetching ------------------------------------------------------*/ + +typedef struct ed448_priv { key_bin priv, pub; } ed448_priv; +typedef struct ed448_pub { key_bin pub; } ed448_pub; + +extern const key_fetchdef ed448_pubfetch[], ed448_privfetch[]; +#define ED448_PUBFETCHSZ 3 +#define ED448_PRIVFETCHSZ 6 + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @ed448_pubkey@ --- * + * + * Arguments: @octet K[ED448_PUBSZ]@ = where to put the public key + * @const void *k@ = private key + * @size_t ksz@ = length of private key + * + * Returns: --- + * + * Use: Derives the public key from a private key. + */ + +extern void ed448_pubkey(octet /*K*/[ED448_PUBSZ], + const void */*k*/, size_t /*ksz*/); + +/* --- @ed448_sign@ --- * + * + * Arguments: @octet sig[ED448_SIGSZ]@ = where to put the signature + * @const void *k@ = private key + * @size_t ksz@ = length of private key + * @const octet K[ED448_PUBSZ]@ = public key + * @int phflag@ = whether the `message' has been hashed already + * @const void *p@ = personalization string + * @size_t psz@ = length of personalization string + * @const void *m@ = message to sign + * @size_t msz@ = length of message + * + * Returns: --- + * + * Use: Signs a message. + */ + +extern void ed448_sign(octet /*sig*/[ED448_SIGSZ], + const void */*k*/, size_t /*ksz*/, + const octet /*K*/[ED448_PUBSZ], + int /*phflag*/, const void */*p*/, size_t /*psz*/, + const void */*m*/, size_t /*msz*/); + +/* --- @ed448_verify@ --- * + * + * Arguments: @const octet K[ED448_PUBSZ]@ = public key + * @const void *m@ = message to sign + * @int phflag@ = whether the `message' has been hashed already + * @const void *p@ = personalization string + * @size_t psz@ = length of personalization string + * @size_t msz@ = length of message + * @const octet sig[ED448_SIGSZ]@ = signature + * + * Returns: Zero if OK, negative on failure. + * + * Use: Verify a signature. + */ + +extern int ed448_verify(const octet /*K*/[ED448_PUBSZ], + int /*phflag*/, const void */*p*/, size_t /*psz*/, + const void */*m*/, size_t /*msz*/, + const octet /*sig*/[ED448_SIGSZ]); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/pub/t/ed448 b/pub/t/ed448 new file mode 100644 index 00000000..59c5cd56 --- /dev/null +++ b/pub/t/ed448 @@ -0,0 +1,228 @@ +### Test vectors for Ed448. + +pubkey { + ## Tests from RFC8032. + 6c82a562cb808d10d632be89c8513ebf6c929f34ddfa8c9f63c9960ef6e348a3528c8a3fcc2f044e39a3fc5b94492f8f032e7549a20098f95b + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180; + c4eab05d357007c632f3dbb48489924d552b08fe0c353a0d4a1f00acda2c463afbea67c5e8d2877c5e3bc397a659949ef8021e954e0a12274e + 43ba28f430cdff456ae531545f7ecd0ac834a55d9358c0372bfa0c6c6798c0866aea01eb00742802b8438ea4cb82169c235160627b4c3a9480; + cd23d24f714274e744343237b93290f511f6425f98e64459ff203e8985083ffdf60500553abc0e05cd02184bdb89c4ccd67e187951267eb328 + dcea9e78f35a1bf3499a831b10b86c90aac01cd84b67a0109b55a36e9328b1e365fce161d71ce7131a543ea4cb5f7e9f1d8b00696447001400; + 258cdd4ada32ed9c9ff54e63756ae582fb8fab2ac721f2c8e676a72768513d939f63dddb55609133f29adf86ec9929dccb52c1c5fd2ff7e21b + 3ba16da0c6f2cc1f30187740756f5e798d6bc5fc015d7c63cc9510ee3fd44adc24d8e968b6e46e6f94d19b945361726bd75e149ef09817f580; + 7ef4e84544236752fbb56b8f31a23a10e42814f5f55ca037cdcc11c64c9a3b2949c1bb60700314611732a6c2fea98eebc0266a11a93970100e + b3da079b0aa493a5772029f0467baebee5a8112d9d3a22532361da294f7bb3815c5dc59e176b4d9f381ca0938e13c6c07b174be65dfa578e80; + d65df341ad13e008567688baedda8e9dcdc17dc024974ea5b4227b6530e339bff21f99e68ca6968f3cca6dfe0fb9f4fab4fa135d5542ea3f01 + df9705f58edbab802c7f8363cfe5560ab1c6132c20a9f1dd163483a26f8ac53a39d6808bf4a1dfbd261b099bb03b3fb50906cb28bd8a081f00; + 2ec5fe3c17045abdb136a5e6a913e32ab75ae68b53d2fc149b77e504132d37569b7e766ba74a19bd6162343a21c8590aa9cebca9014c636df5 + 79756f014dcfe2079f5dd9e718be4171e2ef2486a08f25186f6bff43a9936b9bfe12402b08ae65798a3d81e22e9ec80e7690862ef3d4ed3a00; + 872d093780f5d3730df7c212664b37b8a0f24f56810daa8382cd4fa3f77634ec44dc54f1c2ed9bea86fafb7632d8be199ea165f5ad55dd9ce8 + a81b2e8a70a5ac94ffdbcc9badfc3feb0801f258578bb114ad44ece1ec0e799da08effb81c5d685c0c56f64eecaef8cdf11cc38737838cf400; + 833fe62409237b9d62ec77587520911e9a759cec1d19755b7da901b96dca3d42ef7822e0d5104127dc05d6dbefde69e3ab2cec7c867c6e2c49 + 259b71c19f83ef77a7abd26524cbdb3161b590a48f7d17de3ee0ba9c52beb743c09428a131d6b1b57303d90d8132c276d5ed3d5d01c0f53880; +} + +verify { + ## Tests from RFC8032. + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 "" + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652600 + 0; + 43ba28f430cdff456ae531545f7ecd0ac834a55d9358c0372bfa0c6c6798c0866aea01eb00742802b8438ea4cb82169c235160627b4c3a9480 + 0 "" + 03 + 26b8f91727bd62897af15e41eb43c377efb9c610d48f2335cb0bd0087810f4352541b143c4b981b7e18f62de8ccdf633fc1bf037ab7cd779805e0dbcc0aae1cbcee1afb2e027df36bc04dcecbf154336c19f0af7e0a6472905e799f1953d2a0ff3348ab21aa4adafd1d234441cf807c03a00 + 0; + 43ba28f430cdff456ae531545f7ecd0ac834a55d9358c0372bfa0c6c6798c0866aea01eb00742802b8438ea4cb82169c235160627b4c3a9480 + 0 666f6f + 03 + d4f8f6131770dd46f40867d6fd5d5055de43541f8c5e35abbcd001b32a89f7d2151f7647f11d8ca2ae279fb842d607217fce6e042f6815ea000c85741de5c8da1144a6a1aba7f96de42505d7a7298524fda538fccbbb754f578c1cad10d54d0d5428407e85dcbc98a49155c13764e66c3c00 + 0; + dcea9e78f35a1bf3499a831b10b86c90aac01cd84b67a0109b55a36e9328b1e365fce161d71ce7131a543ea4cb5f7e9f1d8b00696447001400 + 0 "" + 0c3e544074ec63b0265e0c + 1f0a8888ce25e8d458a21130879b840a9089d999aaba039eaf3e3afa090a09d389dba82c4ff2ae8ac5cdfb7c55e94d5d961a29fe0109941e00b8dbdeea6d3b051068df7254c0cdc129cbe62db2dc957dbb47b51fd3f213fb8698f064774250a5028961c9bf8ffd973fe5d5c206492b140e00 + 0; + 3ba16da0c6f2cc1f30187740756f5e798d6bc5fc015d7c63cc9510ee3fd44adc24d8e968b6e46e6f94d19b945361726bd75e149ef09817f580 + 0 "" + 64a65f3cdedcdd66811e2915 + 7eeeab7c4e50fb799b418ee5e3197ff6bf15d43a14c34389b59dd1a7b1b85b4ae90438aca634bea45e3a2695f1270f07fdcdf7c62b8efeaf00b45c2c96ba457eb1a8bf075a3db28e5c24f6b923ed4ad747c3c9e03c7079efb87cb110d3a99861e72003cbae6d6b8b827e4e6c143064ff3c00 + 0; + b3da079b0aa493a5772029f0467baebee5a8112d9d3a22532361da294f7bb3815c5dc59e176b4d9f381ca0938e13c6c07b174be65dfa578e80 + 0 "" + 64a65f3cdedcdd66811e2915e7 + 6a12066f55331b6c22acd5d5bfc5d71228fbda80ae8dec26bdd306743c5027cb4890810c162c027468675ecf645a83176c0d7323a2ccde2d80efe5a1268e8aca1d6fbc194d3f77c44986eb4ab4177919ad8bec33eb47bbb5fc6e28196fd1caf56b4e7e0ba5519234d047155ac727a1053100 + 0; + df9705f58edbab802c7f8363cfe5560ab1c6132c20a9f1dd163483a26f8ac53a39d6808bf4a1dfbd261b099bb03b3fb50906cb28bd8a081f00 + 0 "" + bd0f6a3747cd561bdddf4640a332461a4a30a12a434cd0bf40d766d9c6d458e5512204a30c17d1f50b5079631f64eb3112182da3005835461113718d1a5ef944 + 554bc2480860b49eab8532d2a533b7d578ef473eeb58c98bb2d0e1ce488a98b18dfde9b9b90775e67f47d4a1c3482058efc9f40d2ca033a0801b63d45b3b722ef552bad3b4ccb667da350192b61c508cf7b6b5adadc2c8d9a446ef003fb05cba5f30e88e36ec2703b349ca229c2670833900 + 0; + 79756f014dcfe2079f5dd9e718be4171e2ef2486a08f25186f6bff43a9936b9bfe12402b08ae65798a3d81e22e9ec80e7690862ef3d4ed3a00 + 0 "" + 15777532b0bdd0d1389f636c5f6b9ba734c90af572877e2d272dd078aa1e567cfa80e12928bb542330e8409f3174504107ecd5efac61ae7504dabe2a602ede89e5cca6257a7c77e27a702b3ae39fc769fc54f2395ae6a1178cab4738e543072fc1c177fe71e92e25bf03e4ecb72f47b64d0465aaea4c7fad372536c8ba516a6039c3c2a39f0e4d832be432dfa9a706a6e5c7e19f397964ca4258002f7c0541b590316dbc5622b6b2a6fe7a4abffd96105eca76ea7b98816af0748c10df048ce012d901015a51f189f3888145c03650aa23ce894c3bd889e030d565071c59f409a9981b51878fd6fc110624dcbcde0bf7a69ccce38fabdf86f3bef6044819de11 + c650ddbb0601c19ca11439e1640dd931f43c518ea5bea70d3dcde5f4191fe53f00cf966546b72bcc7d58be2b9badef28743954e3a44a23f880e8d4f1cfce2d7a61452d26da05896f0a50da66a239a8a188b6d825b3305ad77b73fbac0836ecc60987fd08527c1a8e80d5823e65cafe2a3d00 + 0; + 259b71c19f83ef77a7abd26524cbdb3161b590a48f7d17de3ee0ba9c52beb743c09428a131d6b1b57303d90d8132c276d5ed3d5d01c0f53880 + 1 666f6f + 616263 + c32299d46ec8ff02b54540982814dce9a05812f81962b649d528095916a2aa481065b1580423ef927ecf0af5888f90da0f6a9a85ad5dc3f280d91224ba9911a3653d00e484e2ce232521481c8658df304bb7745a73514cdb9bf3e15784ab71284f8d0704a608c54a6b62d97beb511d132100 + 0; + 259b71c19f83ef77a7abd26524cbdb3161b590a48f7d17de3ee0ba9c52beb743c09428a131d6b1b57303d90d8132c276d5ed3d5d01c0f53880 + 1 "" + 616263 + 822f6901f7480f3d5f562c592994d9693602875614483256505600bbc281ae381f54d6bce2ea911574932f52a4e6cadd78769375ec3ffd1b801a0d9b3f4030cd433964b6457ea39476511214f97469b57dd32dbc560a9a94d00bff07620464a3ad203df7dc7ce360c3cd3696d9d9fab90f00 + 0; + a81b2e8a70a5ac94ffdbcc9badfc3feb0801f258578bb114ad44ece1ec0e799da08effb81c5d685c0c56f64eecaef8cdf11cc38737838cf400 + 0 "" + 6ddf802e1aae4986935f7f981ba3f0351d6273c0a0c22c9c0e8339168e675412a3debfaf435ed651558007db4384b650fcc07e3b586a27a4f7a00ac8a6fec2cd86ae4bf1570c41e6a40c931db27b2faa15a8cedd52cff7362c4e6e23daec0fbc3a79b6806e316efcc7b68119bf46bc76a26067a53f296dafdbdc11c77f7777e972660cf4b6a9b369a6665f02e0cc9b6edfad136b4fabe723d2813db3136cfde9b6d044322fee2947952e031b73ab5c603349b307bdc27bc6cb8b8bbd7bd323219b8033a581b59eadebb09b3c4f3d2277d4f0343624acc817804728b25ab797172b4c5c21a22f9c7839d64300232eb66e53f31c723fa37fe387c7d3e50bdf9813a30e5bb12cf4cd930c40cfb4e1fc622592a49588794494d56d24ea4b40c89fc0596cc9ebb961c8cb10adde976a5d602b1c3f85b9b9a001ed3c6a4d3b1437f52096cd1956d042a597d561a596ecd3d1735a8d570ea0ec27225a2c4aaff26306d1526c1af3ca6d9cf5a2c98f47e1c46db9a33234cfd4d81f2c98538a09ebe76998d0d8fd25997c7d255c6d66ece6fa56f11144950f027795e653008f4bd7ca2dee85d8e90f3dc315130ce2a00375a318c7c3d97be2c8ce5b6db41a6254ff264fa6155baee3b0773c0f497c573f19bb4f4240281f0b1f4f7be857a4e59d416c06b4c50fa09e1810ddc6b1467baeac5a3668d11b6ecaa901440016f389f80acc4db977025e7f5924388c7e340a732e554440e76570f8dd71b7d640b3450d1fd5f0410a18f9a3494f707c717b79b4bf75c98400b096b21653b5d217cf3565c9597456f70703497a078763829bc01bb1cbc8fa04eadc9a6e3f6699587a9e75c94e5bab0036e0b2e711392cff0047d0d6b05bd2a588bc109718954259f1d86678a579a3120f19cfb2963f177aeb70f2d4844826262e51b80271272068ef5b3856fa8535aa2a88b2d41f2a0e2fda7624c2850272ac4a2f561f8f2f7a318bfd5caf9696149e4ac824ad3460538fdc25421beec2cc6818162d06bbed0c40a387192349db67a118bada6cd5ab0140ee273204f628aad1c135f770279a651e24d8c14d75a6059d76b96a6fd857def5e0b354b27ab937a5815d16b5fae407ff18222c6d1ed263be68c95f32d908bd895cd76207ae726487567f9a67dad79abec316f683b17f2d02bf07e0ac8b5bc6162cf94697b3c27cd1fea49b27f23ba2901871962506520c392da8b6ad0d99f7013fbc06c2c17a569500c8a7696481c1cd33e9b14e40b82e79a5f5db82571ba97bae3ad3e0479515bb0e2b0f3bfcd1fd33034efc6245eddd7ee2086ddae2600d8ca73e214e8c2b0bdb2b047c6a464a562ed77b73d2d841c4b34973551257713b753632efba348169abc90a68f42611a40126d7cb21b58695568186f7e569d2ff0f9e745d0487dd2eb997cafc5abf9dd102e62ff66cba87 + e301345a41a39a4d72fff8df69c98075a0cc082b802fc9b2b6bc503f926b65bddf7f4c8f1cb49f6396afc8a70abe6d8aef0db478d4c6b2970076c6a0484fe76d76b3a97625d79f1ce240e7c576750d295528286f719b413de9ada3e8eb78ed573603ce30d8bb761785dc30dbc320869e1a00 + 0; + + ## Some negative tests. + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 1 "" + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652600 + -1; + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 ff + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652600 + -1; + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 "" + ff + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652600 + -1; + 5ed7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 "" + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652600 + -1; + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 "" + "" + 633a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652600 + -1; + + ## Check that noncanonical scalars are rejected. The first base test is + ## repeated from below, for context; let s be the scalar part of the + ## signature, and ℓ be the curve order. The first negative test has s' = s + ## + ℓ < 2^448, so the top byte is still zero. The second negative test + ## has s'' = s + 2^224, and the third has 2^448 < s'' = s + 4 ℓ < 2^448 + + ## ℓ; an implementation which handles the top byte incorrectly will fail at + ## least one of these. + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 "" + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652600 + 0; + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 "" + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980f25278d3667403c14bcec5f9cfde9955ebc8333c0ae78fc86e518317c5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e656600 + -1; + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 "" + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652601 + -1; + 5fd7449b59b461fd2ce787ec616ad46a1da1342485a70e1f8a0ea75d80e96778edf124769b46c7061bd6783df1e50f6cd1fa1abeafe8256180 + 0 "" + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980cb2181d51ebc6d2b4b7c16a32726e0b99b6cb648e7787c152cbde18dc3c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652601 + -1; + + ## OK, so this is a massive cheat, but otherwise testing that out-of-range + ## coordinates are rejected is really hard. Pick A = (0, 1), which is the + ## identity in E. Then n A = A for all n; in particular, H(R, A, M) A = A + ## for any choice of R and M. Furthermore, R = R + H(R, A, M) A for any R. + ## Let's pick R = A = (0, 1), because that seems to be working out for us. + ## Then s P = R + H(R, A, M) A exactly when s = 0 (mod ℓ). + ## + ## This is obviously a really daft choice of public key for security, + ## because the following is a completely general-purpose signature for all + ## messages. + ## + ## Why bother, you ask? Well, because (0, 1) is one of the few points + ## which has a reduntant representation. So we can use this to check that + ## we're correctly rejecting signatures which aren't in normal form. + 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 0 "" + 416c6c2d707572706f7365207369676e6174757265210a + 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 0; + 00000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff + 0 "" + 416c6c2d707572706f7365207369676e6174757265210a + 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + -1; + 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 0 "" + 416c6c2d707572706f7365207369676e6174757265210a + 00000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + -1; + + ## Also check that the dead bits in the top byte of a public key and + ## signature are ignored. + 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000a + 0 "" + 416c6c2d707572706f7365207369676e6174757265210a + 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + -1; + 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 0 "" + 416c6c2d707572706f7365207369676e6174757265210a + 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000a000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + -1; +} + +sign { + ## Tests from RFC8032. + 6c82a562cb808d10d632be89c8513ebf6c929f34ddfa8c9f63c9960ef6e348a3528c8a3fcc2f044e39a3fc5b94492f8f032e7549a20098f95b + 0 "" + "" + 533a37f6bbe457251f023c0d88f976ae2dfb504a843e34d2074fd823d41a591f2b233f034f628281f2fd7a22ddd47d7828c59bd0a21bfd3980ff0d2028d4b18a9df63e006c5d1c2d345b925d8dc00b4104852db99ac5c7cdda8530a113a0f4dbb61149f05a7363268c71d95808ff2e652600; + c4eab05d357007c632f3dbb48489924d552b08fe0c353a0d4a1f00acda2c463afbea67c5e8d2877c5e3bc397a659949ef8021e954e0a12274e + 0 "" + 03 + 26b8f91727bd62897af15e41eb43c377efb9c610d48f2335cb0bd0087810f4352541b143c4b981b7e18f62de8ccdf633fc1bf037ab7cd779805e0dbcc0aae1cbcee1afb2e027df36bc04dcecbf154336c19f0af7e0a6472905e799f1953d2a0ff3348ab21aa4adafd1d234441cf807c03a00; + c4eab05d357007c632f3dbb48489924d552b08fe0c353a0d4a1f00acda2c463afbea67c5e8d2877c5e3bc397a659949ef8021e954e0a12274e + 0 666f6f + 03 + d4f8f6131770dd46f40867d6fd5d5055de43541f8c5e35abbcd001b32a89f7d2151f7647f11d8ca2ae279fb842d607217fce6e042f6815ea000c85741de5c8da1144a6a1aba7f96de42505d7a7298524fda538fccbbb754f578c1cad10d54d0d5428407e85dcbc98a49155c13764e66c3c00; + cd23d24f714274e744343237b93290f511f6425f98e64459ff203e8985083ffdf60500553abc0e05cd02184bdb89c4ccd67e187951267eb328 + 0 "" + 0c3e544074ec63b0265e0c + 1f0a8888ce25e8d458a21130879b840a9089d999aaba039eaf3e3afa090a09d389dba82c4ff2ae8ac5cdfb7c55e94d5d961a29fe0109941e00b8dbdeea6d3b051068df7254c0cdc129cbe62db2dc957dbb47b51fd3f213fb8698f064774250a5028961c9bf8ffd973fe5d5c206492b140e00; + 258cdd4ada32ed9c9ff54e63756ae582fb8fab2ac721f2c8e676a72768513d939f63dddb55609133f29adf86ec9929dccb52c1c5fd2ff7e21b + 0 "" + 64a65f3cdedcdd66811e2915 + 7eeeab7c4e50fb799b418ee5e3197ff6bf15d43a14c34389b59dd1a7b1b85b4ae90438aca634bea45e3a2695f1270f07fdcdf7c62b8efeaf00b45c2c96ba457eb1a8bf075a3db28e5c24f6b923ed4ad747c3c9e03c7079efb87cb110d3a99861e72003cbae6d6b8b827e4e6c143064ff3c00; + 7ef4e84544236752fbb56b8f31a23a10e42814f5f55ca037cdcc11c64c9a3b2949c1bb60700314611732a6c2fea98eebc0266a11a93970100e + 0 "" + 64a65f3cdedcdd66811e2915e7 + 6a12066f55331b6c22acd5d5bfc5d71228fbda80ae8dec26bdd306743c5027cb4890810c162c027468675ecf645a83176c0d7323a2ccde2d80efe5a1268e8aca1d6fbc194d3f77c44986eb4ab4177919ad8bec33eb47bbb5fc6e28196fd1caf56b4e7e0ba5519234d047155ac727a1053100; + d65df341ad13e008567688baedda8e9dcdc17dc024974ea5b4227b6530e339bff21f99e68ca6968f3cca6dfe0fb9f4fab4fa135d5542ea3f01 + 0 "" + bd0f6a3747cd561bdddf4640a332461a4a30a12a434cd0bf40d766d9c6d458e5512204a30c17d1f50b5079631f64eb3112182da3005835461113718d1a5ef944 + 554bc2480860b49eab8532d2a533b7d578ef473eeb58c98bb2d0e1ce488a98b18dfde9b9b90775e67f47d4a1c3482058efc9f40d2ca033a0801b63d45b3b722ef552bad3b4ccb667da350192b61c508cf7b6b5adadc2c8d9a446ef003fb05cba5f30e88e36ec2703b349ca229c2670833900; + 2ec5fe3c17045abdb136a5e6a913e32ab75ae68b53d2fc149b77e504132d37569b7e766ba74a19bd6162343a21c8590aa9cebca9014c636df5 + 0 "" + 15777532b0bdd0d1389f636c5f6b9ba734c90af572877e2d272dd078aa1e567cfa80e12928bb542330e8409f3174504107ecd5efac61ae7504dabe2a602ede89e5cca6257a7c77e27a702b3ae39fc769fc54f2395ae6a1178cab4738e543072fc1c177fe71e92e25bf03e4ecb72f47b64d0465aaea4c7fad372536c8ba516a6039c3c2a39f0e4d832be432dfa9a706a6e5c7e19f397964ca4258002f7c0541b590316dbc5622b6b2a6fe7a4abffd96105eca76ea7b98816af0748c10df048ce012d901015a51f189f3888145c03650aa23ce894c3bd889e030d565071c59f409a9981b51878fd6fc110624dcbcde0bf7a69ccce38fabdf86f3bef6044819de11 + c650ddbb0601c19ca11439e1640dd931f43c518ea5bea70d3dcde5f4191fe53f00cf966546b72bcc7d58be2b9badef28743954e3a44a23f880e8d4f1cfce2d7a61452d26da05896f0a50da66a239a8a188b6d825b3305ad77b73fbac0836ecc60987fd08527c1a8e80d5823e65cafe2a3d00; + 872d093780f5d3730df7c212664b37b8a0f24f56810daa8382cd4fa3f77634ec44dc54f1c2ed9bea86fafb7632d8be199ea165f5ad55dd9ce8 + 0 "" + 6ddf802e1aae4986935f7f981ba3f0351d6273c0a0c22c9c0e8339168e675412a3debfaf435ed651558007db4384b650fcc07e3b586a27a4f7a00ac8a6fec2cd86ae4bf1570c41e6a40c931db27b2faa15a8cedd52cff7362c4e6e23daec0fbc3a79b6806e316efcc7b68119bf46bc76a26067a53f296dafdbdc11c77f7777e972660cf4b6a9b369a6665f02e0cc9b6edfad136b4fabe723d2813db3136cfde9b6d044322fee2947952e031b73ab5c603349b307bdc27bc6cb8b8bbd7bd323219b8033a581b59eadebb09b3c4f3d2277d4f0343624acc817804728b25ab797172b4c5c21a22f9c7839d64300232eb66e53f31c723fa37fe387c7d3e50bdf9813a30e5bb12cf4cd930c40cfb4e1fc622592a49588794494d56d24ea4b40c89fc0596cc9ebb961c8cb10adde976a5d602b1c3f85b9b9a001ed3c6a4d3b1437f52096cd1956d042a597d561a596ecd3d1735a8d570ea0ec27225a2c4aaff26306d1526c1af3ca6d9cf5a2c98f47e1c46db9a33234cfd4d81f2c98538a09ebe76998d0d8fd25997c7d255c6d66ece6fa56f11144950f027795e653008f4bd7ca2dee85d8e90f3dc315130ce2a00375a318c7c3d97be2c8ce5b6db41a6254ff264fa6155baee3b0773c0f497c573f19bb4f4240281f0b1f4f7be857a4e59d416c06b4c50fa09e1810ddc6b1467baeac5a3668d11b6ecaa901440016f389f80acc4db977025e7f5924388c7e340a732e554440e76570f8dd71b7d640b3450d1fd5f0410a18f9a3494f707c717b79b4bf75c98400b096b21653b5d217cf3565c9597456f70703497a078763829bc01bb1cbc8fa04eadc9a6e3f6699587a9e75c94e5bab0036e0b2e711392cff0047d0d6b05bd2a588bc109718954259f1d86678a579a3120f19cfb2963f177aeb70f2d4844826262e51b80271272068ef5b3856fa8535aa2a88b2d41f2a0e2fda7624c2850272ac4a2f561f8f2f7a318bfd5caf9696149e4ac824ad3460538fdc25421beec2cc6818162d06bbed0c40a387192349db67a118bada6cd5ab0140ee273204f628aad1c135f770279a651e24d8c14d75a6059d76b96a6fd857def5e0b354b27ab937a5815d16b5fae407ff18222c6d1ed263be68c95f32d908bd895cd76207ae726487567f9a67dad79abec316f683b17f2d02bf07e0ac8b5bc6162cf94697b3c27cd1fea49b27f23ba2901871962506520c392da8b6ad0d99f7013fbc06c2c17a569500c8a7696481c1cd33e9b14e40b82e79a5f5db82571ba97bae3ad3e0479515bb0e2b0f3bfcd1fd33034efc6245eddd7ee2086ddae2600d8ca73e214e8c2b0bdb2b047c6a464a562ed77b73d2d841c4b34973551257713b753632efba348169abc90a68f42611a40126d7cb21b58695568186f7e569d2ff0f9e745d0487dd2eb997cafc5abf9dd102e62ff66cba87 + e301345a41a39a4d72fff8df69c98075a0cc082b802fc9b2b6bc503f926b65bddf7f4c8f1cb49f6396afc8a70abe6d8aef0db478d4c6b2970076c6a0484fe76d76b3a97625d79f1ce240e7c576750d295528286f719b413de9ada3e8eb78ed573603ce30d8bb761785dc30dbc320869e1a00; + 833fe62409237b9d62ec77587520911e9a759cec1d19755b7da901b96dca3d42ef7822e0d5104127dc05d6dbefde69e3ab2cec7c867c6e2c49 + 1 "" + 616263 + 822f6901f7480f3d5f562c592994d9693602875614483256505600bbc281ae381f54d6bce2ea911574932f52a4e6cadd78769375ec3ffd1b801a0d9b3f4030cd433964b6457ea39476511214f97469b57dd32dbc560a9a94d00bff07620464a3ad203df7dc7ce360c3cd3696d9d9fab90f00; + 833fe62409237b9d62ec77587520911e9a759cec1d19755b7da901b96dca3d42ef7822e0d5104127dc05d6dbefde69e3ab2cec7c867c6e2c49 + 1 666f6f + 616263 + c32299d46ec8ff02b54540982814dce9a05812f81962b649d528095916a2aa481065b1580423ef927ecf0af5888f90da0f6a9a85ad5dc3f280d91224ba9911a3653d00e484e2ce232521481c8658df304bb7745a73514cdb9bf3e15784ab71284f8d0704a608c54a6b62d97beb511d132100; +} diff --git a/pub/x448.h b/pub/x448.h index f1b0f2cc..4561d41a 100644 --- a/pub/x448.h +++ b/pub/x448.h @@ -36,7 +36,8 @@ * * This is X448, as described in RFC7748, based on the elliptic curve defined * in Mike Hamburg, `Ed448-Goldilocks, a new elliptic curve', EUROCRYPT 2016, - * https://eprint.iacr.org/2015/625/. + * https://eprint.iacr.org/2015/625/. (The curve here is 4-isogenous to + * Hamburg's curve.) * * The RFC-specified operation is simpler than the Diffie--Hellman function * described in Hamburg's paper, since it doesn't involve the `Decaf' -- 2.11.0