ed448.c

   1 /* -*-c-*-
   2  *
   3  * The Ed448 signature scheme
   4  *
   5  * (c) 2017 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of secnet.
  11  * See README for full list of copyright holders.
  12  *
  13  * secnet is free software; you can redistribute it and/or modify it
  14  * under the terms of the GNU General Public License as published by
  15  * the Free Software Foundation; either version d of the License, or
  16  * (at your option) any later version.
  17  *
  18  * secnet is distributed in the hope that it will be useful, but
  19  * WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21  * General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * version 3 along with secnet; if not, see
  25  * https://www.gnu.org/licenses/gpl.html.
  26  *
  27  * This file was originally part of Catacomb, but has been automatically
  28  * modified for incorporation into secnet: see `import-catacomb-crypto'
  29  * for details.
  30  *
  31  * Catacomb is free software; you can redistribute it and/or modify
  32  * it under the terms of the GNU Library General Public License as
  33  * published by the Free Software Foundation; either version 2 of the
  34  * License, or (at your option) any later version.
  35  *
  36  * Catacomb is distributed in the hope that it will be useful,
  37  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  38  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  39  * GNU Library General Public License for more details.
  40  *
  41  * You should have received a copy of the GNU Library General Public
  42  * License along with Catacomb; if not, write to the Free
  43  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  44  * MA 02111-1307, USA.
  45  */
  46
  47 /*----- Header files ------------------------------------------------------*/
  48
  49 #include <string.h>
  50
  51 #include "fgoldi.h"
  52 #include "ed448.h"
  53 #include "scaf.h"
  54 #include "scmul.h"
  55 #include "sha3.h"
  56
  57 /*----- A number of magic numbers -----------------------------------------*/
  58
  59 # define PIECEWD 24
  60   static const scaf_piece l[] = {
  61     0x5844f3, 0xc292ab, 0x552378, 0x8dc58f, 0x6cc272,
  62     0x369021, 0x49aed6, 0xc44edb, 0xca23e9, 0xffff7c,
  63     0xffffff, 0xffffff, 0xffffff, 0xffffff, 0xffffff,
  64     0xffffff, 0xffffff, 0xffffff, 0x003fff
  65   };
  66   static const scaf_piece mu[] = {
  67     0xe0d00a, 0x4a7bb0, 0x73d6d5, 0x0aadc8, 0xd723a7,
  68     0xe933d8, 0x9c96fd, 0x4b6512, 0x63bb12, 0x335dc1,
  69     0x000008, 0x000000, 0x000000, 0x000000, 0x000000,
  70     0x000000, 0x000000, 0x000000, 0x000000, 0x000400
  71  };
  72
  73 #define NPIECE SCAF_NPIECE(448, PIECEWD)
  74
  75 # define P p28
  76   static const fgoldi_piece bx_pieces[] = {
  77      118276190,  40534716,    9670182, -133293904,
  78       85017404,  -9262234,   68333083,  -96650682,
  79      -93461723,  15824511,   73756743,   57518561,
  80       94773951, -19783215,  107736334,   82941708
  81   }, by_pieces[] = {
  82       36764180,   8885695,  130592152,   20104429,
  83     -104530499,  30304196,  121295871,    5901357,
  84      125344798, -96893944,  -93097107,  -59366209,
  85        3626698,  38307682,   24032956,  110359655
  86   };
  87
  88 static const fgoldi_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ };
  89 #define BX ((const fgoldi *)bx_pieces)
  90 #define BY ((const fgoldi *)by_pieces)
  91 #define BZ ((const fgoldi *)bz_pieces)
  92 #define D (-39081)
  93
  94 /*----- Point encoding and decoding ---------------------------------------*/
  95
  96 static void ptencode(octet q[57],
  97                      const fgoldi *X, const fgoldi *Y, const fgoldi *Z)
  98 {
  99   fgoldi x, y, t;
 100   octet b[56];
 101
 102   fgoldi_inv(&t, Z); fgoldi_mul(&x, X, &t); fgoldi_mul(&y, Y, &t);
 103   fgoldi_store(q, &y); fgoldi_store(b, &x); q[56] = (b[0]&1u) << 7;
 104 }
 105
 106 static int ptdecode(fgoldi *X, fgoldi *Y, fgoldi *Z, const octet q[57])
 107 {
 108   octet b[56];
 109   unsigned i, a;
 110   fgoldi t, u;
 111   uint32 m;
 112   int rc = 0;
 113
 114   /* Load the y-coordinate. */
 115   fgoldi_load(Y, q);
 116
 117   /* Check that the coordinate was in range.  If we store it, we'll get a
 118    * canonical version which we can compare against Q.  Also, check that the
 119    * extra bits in the top byte are zero.
 120    */
 121   fgoldi_store(b, Y);
 122   for (i = a = 0; i < 56; i++) a |= b[i] ^ q[i];
 123   a |= q[56]&0x7fu;
 124   a = ((a - 1) >> 8)&0x01u;             /* 0 |-> 1, non-0 |-> 0 */
 125   rc |= (int)a - 1;
 126
 127   /* Decompress the x-coordinate. */
 128   fgoldi_sqr(&t, Y); fgoldi_mulconst(&u, &t, D); t.P[0] -= 1; u.P[0] -= 1;
 129   rc |= fgoldi_quosqrt(X, &t, &u);
 130   fgoldi_store(b, X); m = -(uint32)(((q[56] >> 7) ^ b[0])&0x1u);
 131   fgoldi_condneg(X, X, m);
 132
 133   /* Set Z. */
 134   fgoldi_set(Z, 1);
 135
 136   /* And we're done. */
 137   return (rc);
 138 }
 139
 140 /*----- Edwards curve arithmetic ------------------------------------------*/
 141
 142 static void ptadd(fgoldi *X, fgoldi *Y, fgoldi *Z,
 143                   const fgoldi *X0, const fgoldi *Y0, const fgoldi *Z0,
 144                   const fgoldi *X1, const fgoldi *Y1, const fgoldi *Z1)
 145 {
 146   fgoldi t0, t1, t2, t3;
 147
 148   /* Bernstein and Lange, `Faster addition and doubling on elliptic curves',
 149    * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows
 150    * the formulae as:
 151    *
 152    *    A = Z1 Z2;   B = A^2;   C = X1 X2;   D = Y1 Y2;
 153    *    E = d C D;   F = B - E;   G = B + E;
 154    *    X3 = A F ((X1 + Y1) (X2 + Y2) - C - D);
 155    *    Y3 = A G (D - C);   Z3 = c F G.
 156    *
 157    * But c = 1 here.
 158    */
 159
 160   fgoldi_mul(&t0, Z0, Z1);              /* t0 = A = Z0 Z1 */
 161   fgoldi_add(&t1, X0, Y0);              /* t1 = X0 + Y0 */
 162   fgoldi_add(&t2, X1, Y1);              /* t2 = X1 + Y1 */
 163   fgoldi_mul(&t1, &t1, &t2);            /* t1 = (X0 + Y0) (X1 + Y1) */
 164   fgoldi_mul(&t2, X0, X1);              /* t2 = C = X0 X1 */
 165   fgoldi_mul(&t3, Y0, Y1);              /* t3 = D = Y0 Y1 */
 166   fgoldi_sub(X, &t1, &t2);              /* X = (X0 + Y0) (X1 + Y1) - C */
 167   fgoldi_sub(X, X, &t3);                /* X = (X0 + Y0) (X1 + Y1) - C - D */
 168   fgoldi_sub(Y, &t3, &t2);              /* Y = D - C */
 169   fgoldi_mul(X, X, &t0);            /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
 170   fgoldi_mul(Y, Y, &t0);                /* Y = A (D - C) */
 171   fgoldi_sqr(&t0, &t0);                 /* t0 = B = A^2 */
 172   fgoldi_mul(&t1, &t2, &t3);            /* t1 = C D */
 173   fgoldi_mulconst(&t1, &t1, D);         /* t1 = E = d C D */
 174   fgoldi_sub(&t2, &t0, &t1);            /* t2 = F = B - E */
 175   fgoldi_add(&t1, &t0, &t1);            /* t1 = G = B + E */
 176   fgoldi_mul(X, X, &t2);          /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
 177   fgoldi_mul(Y, Y, &t1);                /* Y = A G (D - C) */
 178   fgoldi_mul(Z, &t1, &t2);              /* Z = c F G */
 179 }
 180
 181 static void ptdbl(fgoldi *X, fgoldi *Y, fgoldi *Z,
 182                   const fgoldi *X0, const fgoldi *Y0, const fgoldi *Z0)
 183 {
 184   fgoldi t0, t1, t2;
 185
 186   /* Bernstein and Lange, `Faster addition and doubling on elliptic curves',
 187    * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows
 188    * the formulae as:
 189    *
 190    *    B = (X1 + Y1)^2;   C = X1^2;   D = Y1^2;
 191    *    E = C + D;   H = (c Z1)^2;   J = E - 2 H;
 192    *    X3 = c (B - E) J;   Y3 = c E (C - D);   Z3 = E J
 193    *
 194    * But c = 1 here.
 195    */
 196
 197   fgoldi_add(&t0, X0, Y0);              /* t0 = X0 + Y0 */
 198   fgoldi_sqr(&t0, &t0);                 /* t0 = B = (X0 + Y0)^2 */
 199   fgoldi_sqr(&t1, X0);                  /* t1 = C = X0^2 */
 200   fgoldi_sqr(&t2, Y0);                  /* t2 = D = Y0^2 */
 201   fgoldi_add(Y, &t1, &t2);              /* Y = E = C + D */
 202   fgoldi_sub(&t1, &t1, &t2);            /* t1 = C - D */
 203   fgoldi_sub(X, &t0, Y);                /* X = c (B - E) */
 204   fgoldi_sqr(&t0, Z0);                  /* t0 = H = (c Z0)^2 */
 205   fgoldi_add(&t0, &t0, &t0);            /* t0 = 2 H */
 206   fgoldi_sub(&t0, Y, &t0);              /* t0 = J = E - 2 H */
 207   fgoldi_mul(X, X, &t0);                /* X = c (B - E) J */
 208   fgoldi_mul(Z, Y, &t0);                /* Z = E J */
 209   fgoldi_mul(Y, Y, &t1);                /* Y = c E (C - D) */
 210 }
 211
 212 static DEFINE_SCMUL(ptmul, fgoldi, 4, PIECEWD, NPIECE, ptadd, ptdbl)
 213 static DEFINE_SCSIMMUL(ptsimmul, fgoldi, 2, PIECEWD, NPIECE, ptadd, ptdbl)
 214
 215 /*----- Key derivation utilities ------------------------------------------*/
 216
 217 static void unpack_key(scaf_piece a[NPIECE], octet h1[57],
 218                        const octet *k, size_t ksz)
 219 {
 220   shake_ctx h;
 221   octet b[57];
 222
 223   shake256_init(&h); shake_hash(&h, k, ksz);
 224   shake_xof(&h); shake_get(&h, b, sizeof(b));
 225   b[0] &= 0xfcu; b[55] |= 0x80u; scaf_load(a, b, 56, NPIECE, PIECEWD);
 226   if (h1) shake_get(&h, h1, 57);
 227 }
 228
 229 #define PREFIX_BUFSZ 266
 230 static size_t prefix(octet b[PREFIX_BUFSZ],
 231                      int phflag, const octet *p, size_t psz)
 232 {
 233   memcpy(b, "SigEd448", 8);
 234   b[8] = phflag;
 235   assert(psz <= ED448_MAXPERSOSZ); b[9] = psz; memcpy(b + 10, p, psz);
 236   return (psz + 10);
 237 }
 238
 239 /*----- Main code ---------------------------------------------------------*/
 240
 241 /* --- @ed448_pubkey@ --- *
 242  *
 243  * Arguments:   @octet K[ED448_PUBSZ]@ = where to put the public key
 244  *              @const void *k@ = private key
 245  *              @size_t ksz@ = length of private key
 246  *
 247  * Returns:     ---
 248  *
 249  * Use:         Derives the public key from a private key.
 250  */
 251
 252 void ed448_pubkey(octet K[ED448_PUBSZ], const void *k, size_t ksz)
 253 {
 254   scaf_piece a[NPIECE];
 255   fgoldi AX, AY, AZ;
 256
 257   unpack_key(a, 0, k, ksz);
 258   ptmul(&AX, &AY, &AZ, a, BX, BY, BZ);
 259   ptencode(K, &AX, &AY, &AZ);
 260 }
 261
 262 /* --- @ed448_sign@ --- *
 263  *
 264  * Arguments:   @octet sig[ED448_SIGSZ]@ = where to put the signature
 265  *              @const void *k@ = private key
 266  *              @size_t ksz@ = length of private key
 267  *              @const octet K[ED448_PUBSZ]@ = public key
 268  *              @int phflag@ = whether the `message' has been hashed already
 269  *              @const void *p@ = personalization string
 270  *              @size_t psz@ = length of personalization string
 271  *              @const void *m@ = message to sign
 272  *              @size_t msz@ = length of message
 273  *
 274  * Returns:     ---
 275  *
 276  * Use:         Signs a message.
 277  */
 278
 279 void ed448_sign(octet sig[ED448_SIGSZ],
 280                 const void *k, size_t ksz, const octet K[ED448_PUBSZ],
 281                 int phflag, const void *p, size_t psz,
 282                 const void *m, size_t msz)
 283 {
 284   shake_ctx h;
 285   scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE];
 286   scaf_dblpiece tt[2*NPIECE];
 287   fgoldi RX, RY, RZ;
 288   octet h1[57], pb[PREFIX_BUFSZ], rb[114];
 289   unsigned i;
 290
 291   /* Get my private key. */
 292   unpack_key(a, h1, k, ksz);
 293
 294   /* Determine the prefix string. */
 295   psz = prefix(pb, phflag, p, psz);
 296
 297   /* Select the nonce and the vector part. */
 298   shake256_init(&h);
 299   shake_hash(&h, pb, psz);
 300   shake_hash(&h, h1, sizeof(h1));
 301   shake_hash(&h, m, msz);
 302   shake_done(&h, rb, 114);
 303   scaf_loaddbl(tt, rb, 114, 2*NPIECE, PIECEWD);
 304   scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch);
 305   ptmul(&RX, &RY, &RZ, r, BX, BY, BZ);
 306   ptencode(sig, &RX, &RY, &RZ);
 307
 308   /* Calculate the scalar part. */
 309   shake256_init(&h);
 310   shake_hash(&h, pb, psz);
 311   shake_hash(&h, sig, 57);
 312   shake_hash(&h, K, 57);
 313   shake_hash(&h, m, msz);
 314   shake_done(&h, rb, 114);
 315   scaf_loaddbl(tt, rb, 114, 2*NPIECE, PIECEWD);
 316   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 317   scaf_mul(tt, t, a, NPIECE);
 318   for (i = 0; i < NPIECE; i++) tt[i] += r[i];
 319   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 320   scaf_store(sig + 57, 57, t, NPIECE, PIECEWD);
 321 }
 322
 323 /* --- @ed448_verify@ --- *
 324  *
 325  * Arguments:   @const octet K[ED448_PUBSZ]@ = public key
 326  *              @const void *m@ = message to sign
 327  *              @int phflag@ = whether the `message' has been hashed already
 328  *              @const void *p@ = personalization string
 329  *              @size_t psz@ = length of personalization string
 330  *              @size_t msz@ = length of message
 331  *              @const octet sig[ED448_SIGSZ]@ = signature
 332  *
 333  * Returns:     Zero if OK, negative on failure.
 334  *
 335  * Use:         Verify a signature.
 336  */
 337
 338 int ed448_verify(const octet K[ED448_PUBSZ],
 339                  int phflag, const void *p, size_t psz,
 340                  const void *m, size_t msz,
 341                  const octet sig[ED448_SIGSZ])
 342 {
 343   shake_ctx h;
 344   scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE];
 345   scaf_dblpiece tt[2*NPIECE];
 346   fgoldi AX, AY, AZ, RX, RY, RZ;
 347   octet b[PREFIX_BUFSZ];
 348
 349   /* Unpack the public key.  Negate it: we're meant to subtract the term
 350    * involving the public key point, and this is easier than negating the
 351    * scalar.
 352    */
 353   if (ptdecode(&AX, &AY, &AZ, K)) return (-1);
 354   fgoldi_neg(&AX, &AX);
 355
 356   /* Load the scalar and check that it's in range.  The easy way is to store
 357    * it again and see if the two match.
 358    */
 359   scaf_loaddbl(tt, sig + 57, 57, 2*NPIECE, PIECEWD);
 360   scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch);
 361   scaf_store(b, 57, s, NPIECE, PIECEWD);
 362   if (memcmp(b, sig + 57, 57) != 0) return (-1);
 363
 364   /* Check the signature. */
 365   psz = prefix(b, phflag, p, psz);
 366   shake256_init(&h);
 367   shake_hash(&h, b, psz);
 368   shake_hash(&h, sig, 57);
 369   shake_hash(&h, K, ED448_PUBSZ);
 370   shake_hash(&h, m, msz);
 371   shake_done(&h, b, 114);
 372   scaf_loaddbl(tt, b, 114, 2*NPIECE, PIECEWD);
 373   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 374   ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ);
 375   ptencode(b, &RX, &RY, &RZ);
 376   if (memcmp(b, sig, 57) != 0) return (-1);
 377
 378   /* All is good. */
 379   return (0);
 380 }
 381
 382 /*----- That's all, folks -------------------------------------------------*/