chiark - git - mdw - catacomb/blob - pub/ed25519.c

   1 /* -*-c-*-
   2  *
   3  * The Ed25519 signature scheme
   4  *
   5  * (c) 2017 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <string.h>
  31
  32 #include "f25519.h"
  33 #include "ed25519.h"
  34 #include "scaf.h"
  35 #include "sha512.h"
  36
  37 /*----- Key fetching ------------------------------------------------------*/
  38
  39 const key_fetchdef ed25519_pubfetch[] = {
  40   { "pub",      offsetof(ed25519_pub, pub),     KENC_BINARY,    0 },
  41   { 0,          0,                              0,              0 }
  42 };
  43
  44 static const key_fetchdef priv[] = {
  45   { "priv",     offsetof(ed25519_priv, priv),   KENC_BINARY,    0 },
  46   { 0,          0,                              0,              0 }
  47 };
  48
  49 const key_fetchdef ed25519_privfetch[] = {
  50   { "pub",      offsetof(ed25519_priv, pub),    KENC_BINARY,    0 },
  51   { "private",  0,                              KENC_STRUCT,    priv },
  52   { 0,          0,                              0,              0 }
  53 };
  54
  55 /*----- A number of magic numbers -----------------------------------------*/
  56
  57 #if SCAF_IMPL == 32
  58 # define PIECEWD 24
  59   static const scaf_piece l[] = {
  60     0xf5d3ed, 0x631a5c, 0xd65812, 0xa2f79c, 0xdef9de, 0x000014,
  61     0x000000, 0x000000, 0x000000, 0x000000, 0x001000
  62   };
  63   static const scaf_piece mu[] = {
  64     0x1b3994, 0x0a2c13, 0x9ce5a3, 0x29a7ed, 0x5d0863, 0x210621,
  65     0xffffeb, 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0x000fff
  66   };
  67 #endif
  68
  69 #if SCAF_IMPL == 16
  70 # define PIECEWD 12
  71   static const scaf_piece l[] = {
  72     0x3ed, 0xf5d, 0xa5c, 0x631, 0x812, 0xd65,
  73     0x79c, 0xa2f, 0x9de, 0xdef, 0x014, 0x000,
  74     0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
  75     0x000, 0x000, 0x000, 0x001
  76   };
  77   static const scaf_piece mu[] = {
  78     0x994, 0x1b3, 0xc13, 0x0a2, 0x5a3, 0x9ce,
  79     0x7ed, 0x29a, 0x863, 0x5d0, 0x621, 0x210,
  80     0xfeb, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff,
  81     0xfff, 0xfff, 0xfff, 0xfff, 0xfff
  82   };
  83 #endif
  84
  85 #define NPIECE SCAF_NPIECE(255, PIECEWD)
  86
  87 #if F25519_IMPL == 26
  88 # define P p26
  89   static const f25519_piece bx_pieces[] = {
  90     -14297830,  -7645148,  16144683, -16471763,  27570974,
  91      -2696100, -26142465,   8378389,  20764389,   8758491
  92   }, by_pieces[] = {
  93     -26843541,  -6710886,  13421773, -13421773,  26843546,
  94       6710886, -13421773,  13421773, -26843546,  -6710886
  95   }, d_pieces[] = {
  96     -10913610,  13857413, -15372611,   6949391,    114729,
  97      -8787816,  -6275908,  -3247719, -18696448, -12055116
  98   };
  99 #endif
 100 #if F25519_IMPL == 10
 101 # define P p10
 102   static const f25519_piece bx_pieces[] = {
 103      282,  373,  242,  386, -467,   86, -423,  318, -437,
 104       75,  236, -308,  421,   92,  439,  -35,  400,  452,
 105       82,  -40,  160,  441,  -51,  437, -365,  134
 106   }, by_pieces[] = {
 107     -405,  410, -410,  410, -410, -102,  205, -205,  205,
 108     -205,  205, -410,  410, -410,  410,  102, -205,  205,
 109     -205,  205, -205,  410, -410,  410, -410, -102
 110   }, d_pieces[] = {
 111      182, -418,  310, -216, -178, -133,  367, -315, -380,
 112     -351, -182, -255,    2,  152, -390, -136,  -52, -383,
 113     -412, -398,  -12,  448, -469, -196,   55, -184
 114   };
 115 #endif
 116
 117 static const f25519_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ };
 118 #define BX ((const f25519 *)bx_pieces)
 119 #define BY ((const f25519 *)by_pieces)
 120 #define BZ ((const f25519 *)bz_pieces)
 121 #define D ((const f25519 *)d_pieces)
 122
 123 /*----- Point encoding and decoding ---------------------------------------*/
 124
 125 static void ptencode(octet q[32],
 126                      const f25519 *X, const f25519 *Y, const f25519 *Z)
 127 {
 128   f25519 x, y, t;
 129   octet b[32];
 130
 131   f25519_inv(&t, Z); f25519_mul(&x, X, &t); f25519_mul(&y, Y, &t);
 132   f25519_store(q, &y); f25519_store(b, &x); q[31] |= (b[0]&1u) << 7;
 133 }
 134
 135 static int ptdecode(f25519 *X, f25519 *Y, f25519 *Z, const octet q[32])
 136 {
 137   octet b[32];
 138   unsigned i, a;
 139   f25519 t, u;
 140   uint32 m;
 141   int rc = 0;
 142
 143   /* Load the y-coordinate. */
 144   memcpy(b, q, 32); b[31] &= 0x7fu; f25519_load(Y, b);
 145
 146   /* Check that the coordinate was in range.  If we store it, we'll get a
 147    * canonical version which we can compare against Q; be careful not to
 148    * check the top bit.
 149    */
 150   f25519_store(b, Y);
 151   for (i = a = 0; i < 31; i++) a |= b[i] ^ q[i];
 152   a |= (b[31] ^ q[31])&0x7fu;
 153   a = ((a - 1) >> 8)&0x01u;             /* 0 |-> 1, non-0 |-> 0 */
 154   rc |= (int)a - 1;
 155
 156   /* Decompress the x-coordinate. */
 157   f25519_sqr(&t, Y); f25519_mul(&u, &t, D); t.P[0] -= 1; u.P[0] += 1;
 158   rc |= f25519_quosqrt(X, &t, &u);
 159   f25519_store(b, X); m = -(uint32)(((q[31] >> 7) ^ b[0])&0x1u);
 160   f25519_condneg(X, X, m);
 161
 162   /* Set Z. */
 163   f25519_set(Z, 1);
 164
 165   /* And we're done. */
 166   return (rc);
 167 }
 168
 169 /*----- Edwards curve arithmetic ------------------------------------------*/
 170
 171 static void ptadd(f25519 *X, f25519 *Y, f25519 *Z,
 172                   const f25519 *X0, const f25519 *Y0, const f25519 *Z0,
 173                   const f25519 *X1, const f25519 *Y1, const f25519 *Z1)
 174 {
 175   f25519 t0, t1, t2, t3;
 176
 177   /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
 178    * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
 179    * formulae as:
 180    *
 181    *    A = Z1 Z2;   B = A^2;   C = X1 X2;   D = Y1 Y2;
 182    *    E = d C D;   F = B - E;   G = B + E;
 183    *    X3 = A F ((X1 + Y1) (X2 + Y2) - C - D);
 184    *    Y3 = A G (D - a C);   Z3 = F G.
 185    *
 186    * Note that a = -1, which things easier.
 187    */
 188
 189   f25519_mul(&t0, Z0, Z1);              /* t0 = A = Z0 Z1 */
 190   f25519_add(&t1, X0, Y0);              /* t1 = X0 + Y0 */
 191   f25519_add(&t2, X1, Y1);              /* t2 = X1 + Y1 */
 192   f25519_mul(&t1, &t1, &t2);            /* t1 = (X0 + Y0) (X1 + Y1) */
 193   f25519_mul(&t2, X0, X1);              /* t2 = C = X0 X1 */
 194   f25519_mul(&t3, Y0, Y1);              /* t3 = D = Y0 Y1 */
 195   f25519_add(Y, &t2, &t3);              /* Y = C + D = D - a C */
 196   f25519_sub(X, &t1, Y);                /* X = (X0 + Y0) (X1 + Y1) - C - D */
 197   f25519_mul(X, X, &t0);            /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
 198   f25519_mul(Y, Y, &t0);                /* Y = A (D - a C) */
 199   f25519_sqr(&t0, &t0);                 /* t0 = B = A^2 */
 200   f25519_mul(&t1, &t2, &t3);            /* t1 = C D */
 201   f25519_mul(&t1, &t1, D);              /* t1 = E = d C D */
 202   f25519_sub(&t2, &t0, &t1);            /* t2 = F = B - E */
 203   f25519_add(&t1, &t0, &t1);            /* t1 = G = B + E */
 204   f25519_mul(X, X, &t2);          /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
 205   f25519_mul(Y, Y, &t1);                /* Y = A G (D - a C) */
 206   f25519_mul(Z, &t1, &t2);              /* Z = F G */
 207 }
 208
 209 static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z,
 210                   const f25519 *X0, const f25519 *Y0, const f25519 *Z0)
 211 {
 212   f25519 t0, t1, t2;
 213
 214   /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
 215    * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
 216    * formulae as:
 217    *
 218    *    B = (X1 + Y1)^2;   C = X1^2;   D = Y1^2;   E = a C;
 219    *    F = E + D;   H = Z1^2;   J = F - 2 H;
 220    *    X3 = (B - C - D) J;   Y3 = F (E - D);   Z3 = F J.
 221    *
 222    * Note that a = -1, which things easier.
 223    */
 224
 225   f25519_add(&t0, X0, Y0);              /* t0 = X0 + Y0 */
 226   f25519_sqr(&t0, &t0);                 /* t0 = B = (X0 + Y0)^2 */
 227   f25519_sqr(&t1, X0);                  /* t1 = C = X0^2 */
 228   f25519_sqr(&t2, Y0);                  /* t2 = D = Y0^2 */
 229   f25519_add(Y, &t1, &t2);              /* Y = C + D = -(E - D) */
 230   f25519_sub(X, &t0, Y);                /* X = B - C - D */
 231                                         /* (E = a C = -C) */
 232   f25519_sub(&t0, &t2, &t1);            /* t0 = F = D - C = E + D */
 233   f25519_sqr(&t1, Z0);                  /* t1 = H = Z0^2 */
 234   f25519_mulconst(&t1, &t1, 2);         /* t1 = 2 H */
 235   f25519_sub(&t1, &t0, &t1);            /* t1 = J = F - 2 H */
 236   f25519_mul(X, X, &t1);                /* X = (B - C - D) J */
 237   f25519_mul(Y, Y, &t0);                /* Y = -F (E - D) */
 238   f25519_neg(Y, Y);                     /* Y = F (E - D) */
 239   f25519_mul(Z, &t0, &t1);              /* Z = F J */
 240 }
 241
 242 static void ptmul(f25519 *X, f25519 *Y, f25519 *Z,
 243                   const scaf_piece n[NPIECE],
 244                   const f25519 *X0, const f25519 *Y0, const f25519 *Z0)
 245 {
 246   /* We assume that the window width divides the scalar piece width. */
 247 #define WINWD 4
 248 #define WINLIM (1 << WINWD)
 249 #define WINMASK (WINLIM - 1)
 250 #define TABSZ (WINLIM/2 + 1)
 251
 252   f25519 VX[TABSZ], VY[TABSZ], VZ[TABSZ];
 253   f25519 TX, TY, TZ, UX, UY, UZ;
 254   unsigned i, j, k, w;
 255   uint32 m_neg;
 256   scaf_piece ni;
 257
 258   /* Build a table of small multiples. */
 259   f25519_set(&VX[0], 0); f25519_set(&VY[0], 1); f25519_set(&VZ[0], 1);
 260   VX[1] = *X0; VY[1] = *Y0; VZ[1] = *Z0;
 261   ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]);
 262   for (i = 3; i < TABSZ; i += 2) {
 263     ptadd(&VX[i], &VY[i], &VZ[i],
 264           &VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0);
 265     ptdbl(&VX[i + 1], &VY[i + 1], &VZ[i + 1],
 266           &VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]);
 267   }
 268
 269   /* Now do the multiplication.  We lag a window behind the cursor position
 270    * because of the scalar recoding we do.
 271    */
 272   f25519_set(&TX, 0); f25519_set(&TY, 1); f25519_set(&TZ, 1);
 273   for (i = NPIECE, w = 0, m_neg = 0; i--; ) {
 274     ni = n[i];
 275
 276     /* Work through each window in the scalar piece. */
 277     for (j = 0; j < PIECEWD; j += WINWD) {
 278
 279       /* Shift along by a window. */
 280       for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ);
 281
 282       /* Peek at the next window of four bits.  If the top bit is set we lend
 283        * a bit leftwards, into w.  It's too late for this to affect the sign
 284        * now, but if we negated earlier then the addition would be wrong.
 285        */
 286       w += (ni >> (PIECEWD - 1))&0x1u;
 287       w = ((WINLIM - w)&m_neg) | (w&~m_neg);
 288
 289       /* Collect the entry from the table, and add or subtract. */
 290       f25519_pickn(&UX, VX, TABSZ, w);
 291       f25519_pickn(&UY, VY, TABSZ, w);
 292       f25519_pickn(&UZ, VZ, TABSZ, w);
 293       f25519_condneg(&UX, &UX, m_neg);
 294       ptadd(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ);
 295
 296       /* Move the next window into the delay slot.  If its top bit is set,
 297        * then negate it and set m_neg.
 298        */
 299       w = (ni >> (PIECEWD - WINWD))&WINMASK;
 300       m_neg = -(uint32)((w >> (WINWD - 1))&0x1u);
 301       ni <<= WINWD;
 302     }
 303   }
 304
 305   /* Do the final window.  Just fix the sign and go. */
 306   for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ);
 307   w = ((WINLIM - w)&m_neg) | (w&~m_neg);
 308   f25519_pickn(&UX, VX, TABSZ, w);
 309   f25519_pickn(&UY, VY, TABSZ, w);
 310   f25519_pickn(&UZ, VZ, TABSZ, w);
 311   f25519_condneg(&UX, &UX, m_neg);
 312   ptadd(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ);
 313
 314 #undef WINWD
 315 #undef WINLIM
 316 #undef WINMASK
 317 #undef TABSZ
 318 }
 319
 320 static void ptsimmul(f25519 *X, f25519 *Y, f25519 *Z,
 321                      const scaf_piece n0[NPIECE],
 322                      const f25519 *X0, const f25519 *Y0, const f25519 *Z0,
 323                      const scaf_piece n1[NPIECE],
 324                      const f25519 *X1, const f25519 *Y1, const f25519 *Z1)
 325 {
 326   /* We assume that the window width divides the scalar piece width. */
 327 #define WINWD 2
 328 #define WINLIM (1 << WINWD)
 329 #define WINMASK (WINLIM - 1)
 330 #define TABSZ (1 << 2*WINWD)
 331
 332   f25519 VX[TABSZ], VY[TABSZ], VZ[TABSZ];
 333   f25519 TX, TY, TZ, UX, UY, UZ;
 334   unsigned i, j, k, w, ni0, ni1;
 335
 336   /* Build a table of small linear combinations. */
 337   f25519_set(&VX[0], 0); f25519_set(&VY[0], 1); f25519_set(&VZ[0], 1);
 338   VX[1] = *X0; VX[WINLIM] = *X1;
 339   VY[1] = *Y0; VY[WINLIM] = *Y1;
 340   VZ[1] = *Z0; VZ[WINLIM] = *Z1;
 341   for (i = 2; i < WINLIM; i <<= 1) {
 342     ptdbl(&VX[i], &VY[i], &VZ[i],
 343           &VX[i/2], &VY[i/2], &VZ[i/2]);
 344     ptdbl(&VX[i*WINLIM], &VY[i*WINLIM], &VZ[i*WINLIM],
 345           &VX[i*WINLIM/2], &VY[i*WINLIM/2], &VZ[i*WINLIM/2]);
 346   }
 347   for (i = 2; i < TABSZ; i <<= 1) {
 348     for (j = 1; j < i; j++)
 349       ptadd(&VX[i + j], &VY[i + j], &VZ[i + j],
 350             &VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]);
 351   }
 352
 353   /* Do the multiplication. */
 354   f25519_set(&TX, 0); f25519_set(&TY, 1); f25519_set(&TZ, 1);
 355   for (i = NPIECE; i--; ) {
 356     ni0 = n0[i]; ni1 = n1[i];
 357
 358     /* Work through each window in the scalar pieces. */
 359     for (j = 0; j < PIECEWD; j += WINWD) {
 360
 361       /* Shift along by a window. */
 362       for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ);
 363
 364       /* Collect the next window from the scalars. */
 365       w = ((ni0 >> (PIECEWD - WINWD))&WINMASK) |
 366         ((ni1 >> (PIECEWD - 2*WINWD))&(WINMASK << WINWD));
 367       ni0 <<= WINWD; ni1 <<= WINWD;
 368
 369       /* Collect the entry from the table, and add. */
 370       f25519_pickn(&UX, VX, TABSZ, w);
 371       f25519_pickn(&UY, VY, TABSZ, w);
 372       f25519_pickn(&UZ, VZ, TABSZ, w);
 373       ptadd(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ);
 374     }
 375   }
 376
 377   /* Done. */
 378   *X = TX; *Y = TY; *Z = TZ;
 379 }
 380
 381 /*----- Key derivation utilities ------------------------------------------*/
 382
 383 static void unpack_key(scaf_piece a[NPIECE], octet h1[32],
 384                        const octet *k, size_t ksz)
 385 {
 386   sha512_ctx h;
 387   octet b[SHA512_HASHSZ];
 388
 389   sha512_init(&h); sha512_hash(&h, k, ksz); sha512_done(&h, b);
 390   b[0] &= 0xf8u; b[31] = (b[31]&0x3f) | 0x40;
 391   scaf_load(a, b, 32, NPIECE, PIECEWD);
 392   if (h1) memcpy(h1, b + 32, 32);
 393 }
 394
 395 #define PREFIX_BUFSZ 290
 396 static size_t prefix(octet b[PREFIX_BUFSZ],
 397                      int phflag, const octet *p, size_t psz)
 398 {
 399   if (phflag < 0) return (0);
 400   memcpy(b, "SigEd25519 no Ed25519 collisions", 32);
 401   b[32] = phflag;
 402   assert(psz < ED25519_MAXPERSOSZ); b[33] = psz; memcpy(b + 34, p, psz);
 403   return (psz + 34);
 404 }
 405
 406 /*----- Main code ---------------------------------------------------------*/
 407
 408 /* --- @ed25519_pubkey@ --- *
 409  *
 410  * Arguments:   @octet K[ED25519_PUBSZ]@ = where to put the public key
 411  *              @const void *k@ = private key
 412  *              @size_t ksz@ = length of private key
 413  *
 414  * Returns:     ---
 415  *
 416  * Use:         Derives the public key from a private key.
 417  */
 418
 419 void ed25519_pubkey(octet K[ED25519_PUBSZ], const void *k, size_t ksz)
 420 {
 421   scaf_piece a[NPIECE];
 422   f25519 AX, AY, AZ;
 423
 424   unpack_key(a, 0, k, ksz);
 425   ptmul(&AX, &AY, &AZ, a, BX, BY, BZ);
 426   ptencode(K, &AX, &AY, &AZ);
 427 }
 428
 429 /* --- @ed25519_sign@, @ed25519ctx_sign@ --- *
 430  *
 431  * Arguments:   @octet sig[ED25519_SIGSZ]@ = where to put the signature
 432  *              @const void *k@ = private key
 433  *              @size_t ksz@ = length of private key
 434  *              @const octet K[ED25519_PUBSZ]@ = public key
 435  *              @int phflag@ = whether the `message' has been hashed already
 436  *              @const void *p@ = personalization string
 437  *              @size_t psz@ = length of personalization string
 438  *              @const void *m@ = message to sign
 439  *              @size_t msz@ = length of message
 440  *
 441  * Returns:     ---
 442  *
 443  * Use:         Signs a message.
 444  *
 445  *              In @ed25519ctx_sign@, if @phflag@ is @-1@ then you get plain
 446  *              old Ed25519: the personalization string pointer @p@ will be
 447  *              ignored.  If @phflag > 0@ then the `message' @m@ should be a
 448  *              SHA512 hash of the actual message.
 449  */
 450
 451 void ed25519ctx_sign(octet sig[ED25519_SIGSZ],
 452                      const void *k, size_t ksz, const octet K[ED25519_PUBSZ],
 453                      int phflag, const void *p, size_t psz,
 454                      const void *m, size_t msz)
 455 {
 456   sha512_ctx h;
 457   scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE + 1];
 458   scaf_dblpiece tt[2*NPIECE];
 459   f25519 RX, RY, RZ;
 460   octet h1[32], pb[PREFIX_BUFSZ], rb[SHA512_HASHSZ];
 461   unsigned i;
 462
 463   /* Get my private key. */
 464   unpack_key(a, h1, k, ksz);
 465
 466   /* Determine the prefix string. */
 467   psz = prefix(pb, phflag, p, psz);
 468
 469   /* Select the nonce and the vector part. */
 470   sha512_init(&h);
 471   sha512_hash(&h, pb, psz);
 472   sha512_hash(&h, h1, 32);
 473   sha512_hash(&h, m, msz);
 474   sha512_done(&h, rb);
 475   scaf_loaddbl(tt, rb, 64, 2*NPIECE, PIECEWD);
 476   scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch);
 477   ptmul(&RX, &RY, &RZ, r, BX, BY, BZ);
 478   ptencode(sig, &RX, &RY, &RZ);
 479
 480   /* Calculate the scalar part. */
 481   sha512_init(&h);
 482   sha512_hash(&h, pb, psz);
 483   sha512_hash(&h, sig, 32);
 484   sha512_hash(&h, K, 32);
 485   sha512_hash(&h, m, msz);
 486   sha512_done(&h, rb);
 487   scaf_loaddbl(tt, rb, 64, 2*NPIECE, PIECEWD);
 488   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 489   scaf_mul(tt, t, a, NPIECE);
 490   for (i = 0; i < NPIECE; i++) tt[i] += r[i];
 491   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 492   scaf_store(sig + 32, 32, t, NPIECE, PIECEWD);
 493 }
 494
 495 void ed25519_sign(octet sig[ED25519_SIGSZ],
 496                   const void *k, size_t ksz, const octet K[ED25519_PUBSZ],
 497                   const void *m, size_t msz)
 498   { ed25519ctx_sign(sig, k, ksz, K, -1, 0, 0, m, msz); }
 499
 500 /* --- @ed25519_verify@, @ed25519ctx_verify@ --- *
 501  *
 502  * Arguments:   @const octet K[ED25519_PUBSZ]@ = public key
 503  *              @int phflag@ = whether the `message' has been hashed already
 504  *              @const void *p@ = personalization string
 505  *              @size_t psz@ = length of personalization string
 506  *              @const void *m@ = message to sign
 507  *              @size_t msz@ = length of message
 508  *              @const octet sig[ED25519_SIGSZ]@ = signature
 509  *
 510  * Returns:     Zero if OK, negative on failure.
 511  *
 512  * Use:         Verify a signature.
 513  *
 514  *              In @ed25519ctx_verify@, if @phflag@ is @-1@ then you get
 515  *              plain old Ed25519: the personalization string pointer @p@
 516  *              will be ignored.  If @phflag > 0@ then the `message' @m@
 517  *              should be a SHA512 hash of the actual message.
 518  */
 519
 520 int ed25519ctx_verify(const octet K[ED25519_PUBSZ],
 521                       int phflag, const void *p, size_t psz,
 522                       const void *m, size_t msz,
 523                       const octet sig[ED25519_SIGSZ])
 524 {
 525   sha512_ctx h;
 526   scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE + 1];
 527   scaf_dblpiece tt[2*NPIECE];
 528   f25519 AX, AY, AZ, RX, RY, RZ;
 529   octet b[PREFIX_BUFSZ];
 530
 531   /* Unpack the public key.  Negate it: we're meant to subtract the term
 532    * involving the public key point, and this is easier than negating the
 533    * scalar.
 534    */
 535   if (ptdecode(&AX, &AY, &AZ, K)) return (-1);
 536   f25519_neg(&AX, &AX);
 537
 538   /* Load the scalar and check that it's in range.  The easy way is to store
 539    * it again and see if the two match.
 540    */
 541   scaf_loaddbl(tt, sig + 32, 32, 2*NPIECE, PIECEWD);
 542   scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch);
 543   scaf_store(b, 32, s, NPIECE, PIECEWD);
 544   if (memcmp(b, sig + 32, 32) != 0) return (-1);
 545
 546   /* Check the signature. */
 547   psz = prefix(b, phflag, p, psz);
 548   sha512_init(&h);
 549   sha512_hash(&h, b, psz);
 550   sha512_hash(&h, sig, 32);
 551   sha512_hash(&h, K, 32);
 552   sha512_hash(&h, m, msz);
 553   sha512_done(&h, b);
 554   scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD);
 555   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 556   ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ);
 557   ptencode(b, &RX, &RY, &RZ);
 558   if (memcmp(b, sig, 32) != 0) return (-1);
 559
 560   /* All is good. */
 561   return (0);
 562 }
 563
 564 int ed25519_verify(const octet K[ED25519_PUBSZ],
 565                    const void *m, size_t msz,
 566                    const octet sig[ED25519_SIGSZ])
 567   { return (ed25519ctx_verify(K, -1, 0, 0, m, msz, sig)); }
 568
 569 /*----- Test rig ----------------------------------------------------------*/
 570
 571 #ifdef TEST_RIG
 572
 573 #include <stdio.h>
 574 #include <string.h>
 575
 576 #include <mLib/report.h>
 577 #include <mLib/testrig.h>
 578
 579 static int vrf_pubkey(dstr dv[])
 580 {
 581   dstr dpub = DSTR_INIT;
 582   int ok = 1;
 583
 584   if (dv[1].len != ED25519_PUBSZ) die(1, "bad pub length");
 585
 586   dstr_ensure(&dpub, ED25519_PUBSZ); dpub.len = ED25519_PUBSZ;
 587   ed25519_pubkey((octet *)dpub.buf, dv[0].buf, dv[0].len);
 588   if (memcmp(dpub.buf, dv[1].buf, ED25519_PUBSZ) != 0) {
 589     ok = 0;
 590     fprintf(stderr, "failed!");
 591     fprintf(stderr, "\n\tpriv = "); type_hex.dump(&dv[0], stderr);
 592     fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dpub, stderr);
 593     fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[1], stderr);
 594     fprintf(stderr, "\n");
 595   }
 596
 597   dstr_destroy(&dpub);
 598   return (ok);
 599 }
 600
 601 static int vrf_sign(dstr *priv, int phflag, dstr *perso,
 602                     dstr *msg, dstr *want)
 603 {
 604   sha512_ctx h;
 605   octet K[ED25519_PUBSZ];
 606   dstr d = DSTR_INIT, dsig = DSTR_INIT, *m;
 607   int ok = 1;
 608
 609   if (want->len != ED25519_SIGSZ) die(1, "bad result length");
 610
 611   dstr_ensure(&dsig, ED25519_SIGSZ); dsig.len = ED25519_SIGSZ;
 612   if (phflag <= 0)
 613     m = msg;
 614   else {
 615     dstr_ensure(&d, SHA512_HASHSZ); d.len = SHA512_HASHSZ;
 616     sha512_init(&h);
 617     sha512_hash(&h, msg->buf, msg->len);
 618     sha512_done(&h, d.buf);
 619     m = &d;
 620   }
 621   ed25519_pubkey(K, priv->buf, priv->len);
 622   ed25519ctx_sign((octet *)dsig.buf, priv->buf, priv->len, K,
 623                   phflag, perso ? perso->buf : 0, perso ? perso->len : 0,
 624                   m->buf, m->len);
 625   if (memcmp(dsig.buf, want->buf, ED25519_SIGSZ) != 0) {
 626     ok = 0;
 627     fprintf(stderr, "failed!");
 628     fprintf(stderr, "\n\tpriv = "); type_hex.dump(priv, stderr);
 629     if (phflag >= 0) {
 630       fprintf(stderr, "\n\t  ph = %d", phflag);
 631       fprintf(stderr, "\n\tpers = "); type_hex.dump(perso, stderr);
 632     }
 633     fprintf(stderr, "\n\t msg = "); type_hex.dump(msg, stderr);
 634     if (phflag > 0)
 635       { fprintf(stderr, "\n\thash = "); type_hex.dump(m, stderr); }
 636     fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dsig, stderr);
 637     fprintf(stderr, "\n\twant = "); type_hex.dump(want, stderr);
 638     fprintf(stderr, "\n");
 639   }
 640
 641   dstr_destroy(&dsig);
 642   return (ok);
 643 }
 644
 645 static int vrf_sign_trad(dstr *dv)
 646   { return (vrf_sign(&dv[0], -1, 0, &dv[1], &dv[2])); }
 647
 648 static int vrf_sign_ctx(dstr *dv)
 649   { return (vrf_sign(&dv[0], *(int *)dv[1].buf, &dv[2], &dv[3], &dv[4])); }
 650
 651 static int vrf_verify(dstr *pub, int phflag, dstr *perso,
 652                       dstr *msg, dstr *sig, int rc_want)
 653 {
 654   sha512_ctx h;
 655   int rc_calc;
 656   dstr d = DSTR_INIT, *m;
 657   int ok = 1;
 658
 659   if (pub->len != ED25519_PUBSZ) die(1, "bad pub length");
 660   if (sig->len != ED25519_SIGSZ) die(1, "bad sig length");
 661
 662   if (phflag <= 0)
 663     m = msg;
 664   else {
 665     dstr_ensure(&d, SHA512_HASHSZ); d.len = SHA512_HASHSZ;
 666     sha512_init(&h);
 667     sha512_hash(&h, msg->buf, msg->len);
 668     sha512_done(&h, d.buf);
 669     m = &d;
 670   }
 671   rc_calc = ed25519ctx_verify((const octet *)pub->buf,
 672                               phflag, perso ? perso->buf : 0,
 673                               perso ? perso->len : 0,
 674                               m->buf, m->len,
 675                               (const octet *)sig->buf);
 676   if (!rc_want != !rc_calc) {
 677     ok = 0;
 678     fprintf(stderr, "failed!");
 679     fprintf(stderr, "\n\t pub = "); type_hex.dump(pub, stderr);
 680     if (phflag >= 0) {
 681       fprintf(stderr, "\n\t  ph = %d", phflag);
 682       fprintf(stderr, "\n\tpers = "); type_hex.dump(perso, stderr);
 683     }
 684     fprintf(stderr, "\n\t msg = "); type_hex.dump(msg, stderr);
 685     if (phflag > 0)
 686       { fprintf(stderr, "\n\thash = "); type_hex.dump(m, stderr); }
 687     fprintf(stderr, "\n\t sig = "); type_hex.dump(sig, stderr);
 688     fprintf(stderr, "\n\tcalc = %d", rc_calc);
 689     fprintf(stderr, "\n\twant = %d", rc_want);
 690     fprintf(stderr, "\n");
 691   }
 692
 693   return (ok);
 694 }
 695
 696 static int vrf_verify_trad(dstr *dv)
 697   { return (vrf_verify(&dv[0], -1, 0, &dv[1], &dv[2], *(int *)dv[3].buf)); }
 698
 699 static int vrf_verify_ctx(dstr *dv)
 700 {
 701   return (vrf_verify(&dv[0], *(int *)dv[1].buf, &dv[2],
 702                      &dv[3], &dv[4], *(int *)dv[5].buf));
 703 }
 704
 705 static test_chunk tests[] = {
 706   { "pubkey", vrf_pubkey,
 707     { &type_hex, &type_hex } },
 708   { "sign", vrf_sign_trad,
 709     { &type_hex, &type_hex, &type_hex } },
 710   { "verify", vrf_verify_trad,
 711     { &type_hex, &type_hex, &type_hex, &type_int } },
 712   { "sign-ctx", vrf_sign_ctx,
 713     { &type_hex, &type_int, &type_hex, &type_hex, &type_hex } },
 714   { "verify-ctx", vrf_verify_ctx,
 715     { &type_hex, &type_int, &type_hex, &type_hex, &type_hex, &type_int } },
 716   { 0, 0, { 0 } }
 717 };
 718
 719 int main(int argc, char *argv[])
 720 {
 721   test_run(argc, argv, tests, SRCDIR "/t/ed25519");
 722   return (0);
 723 }
 724
 725 #endif
 726
 727 /*----- That's all, folks -------------------------------------------------*/