X-Git-Url: https://git.distorted.org.uk/~mdw/secnet/blobdiff_plain/1047c205103e6da9fc6a317f41583147dbc11aa3..a1a6042e24c9873aa6abf668bcb68d39d0eb4190:/ed448.c diff --git a/ed448.c b/ed448.c new file mode 100644 index 0000000..35b198b --- /dev/null +++ b/ed448.c @@ -0,0 +1,382 @@ +/* -*-c-*- + * + * The Ed448 signature scheme + * + * (c) 2017 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of secnet. + * See README for full list of copyright holders. + * + * secnet is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version d of the License, or + * (at your option) any later version. + * + * secnet 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 a copy of the GNU General Public License + * version 3 along with secnet; if not, see + * https://www.gnu.org/licenses/gpl.html. + * + * This file was originally part of Catacomb, but has been automatically + * modified for incorporation into secnet: see `import-catacomb-crypto' + * for details. + * + * 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" + +/*----- A number of magic numbers -----------------------------------------*/ + +# 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 + }; + +#define NPIECE SCAF_NPIECE(448, PIECEWD) + +# 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 + }; + +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_add(&t0, &t0, &t0); /* 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]; + 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]; + 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); +} + +/*----- That's all, folks -------------------------------------------------*/