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 /*----- Main code ---------------------------------------------------------*/
 396
 397 /* --- @ed25519_pubkey@ --- *
 398  *
 399  * Arguments:   @octet K[ED25519_PUBSZ]@ = where to put the public key
 400  *              @const void *k@ = private key
 401  *              @size_t ksz@ = length of private key
 402  *
 403  * Returns:     ---
 404  *
 405  * Use:         Derives the public key from a private key.
 406  */
 407
 408 void ed25519_pubkey(octet K[ED25519_PUBSZ], const void *k, size_t ksz)
 409 {
 410   scaf_piece a[NPIECE];
 411   f25519 AX, AY, AZ;
 412
 413   unpack_key(a, 0, k, ksz);
 414   ptmul(&AX, &AY, &AZ, a, BX, BY, BZ);
 415   ptencode(K, &AX, &AY, &AZ);
 416 }
 417
 418 /* --- @ed25519_sign@ --- *
 419  *
 420  * Arguments:   @octet sig[ED25519_SIGSZ]@ = where to put the signature
 421  *              @const void *k@ = private key
 422  *              @size_t ksz@ = length of private key
 423  *              @const octet K[ED25519_PUBSZ]@ = public key
 424  *              @const void *m@ = message to sign
 425  *              @size_t msz@ = length of message
 426  *
 427  * Returns:     ---
 428  *
 429  * Use:         Signs a message.
 430  */
 431
 432 void ed25519_sign(octet sig[ED25519_SIGSZ],
 433                   const void *k, size_t ksz,
 434                   const octet K[ED25519_PUBSZ],
 435                   const void *m, size_t msz)
 436 {
 437   sha512_ctx h;
 438   scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE + 1];
 439   scaf_dblpiece tt[2*NPIECE];
 440   f25519 RX, RY, RZ;
 441   octet h1[32], b[SHA512_HASHSZ];
 442   unsigned i;
 443
 444   /* Get my private key. */
 445   unpack_key(a, h1, k, ksz);
 446
 447   /* Select the nonce and the vector part. */
 448   sha512_init(&h);
 449   sha512_hash(&h, h1, 32);
 450   sha512_hash(&h, m, msz);
 451   sha512_done(&h, b);
 452   scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD);
 453   scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch);
 454   ptmul(&RX, &RY, &RZ, r, BX, BY, BZ);
 455   ptencode(sig, &RX, &RY, &RZ);
 456
 457   /* Calculate the scalar part. */
 458   sha512_init(&h);
 459   sha512_hash(&h, sig, 32);
 460   sha512_hash(&h, K, 32);
 461   sha512_hash(&h, m, msz);
 462   sha512_done(&h, b);
 463   scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD);
 464   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 465   scaf_mul(tt, t, a, NPIECE);
 466   for (i = 0; i < NPIECE; i++) tt[i] += r[i];
 467   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 468   scaf_store(sig + 32, 32, t, NPIECE, PIECEWD);
 469 }
 470
 471 /* --- @ed25519_verify@ --- *
 472  *
 473  * Arguments:   @const octet K[ED25519_PUBSZ]@ = public key
 474  *              @const void *m@ = message to sign
 475  *              @size_t msz@ = length of message
 476  *              @const octet sig[ED25519_SIGSZ]@ = signature
 477  *
 478  * Returns:     Zero if OK, negative on failure.
 479  *
 480  * Use:         Verify a signature.
 481  */
 482
 483 int ed25519_verify(const octet K[ED25519_PUBSZ],
 484                    const void *m, size_t msz,
 485                    const octet sig[ED25519_SIGSZ])
 486 {
 487   sha512_ctx h;
 488   scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE + 1];
 489   scaf_dblpiece tt[2*NPIECE];
 490   f25519 AX, AY, AZ, RX, RY, RZ;
 491   octet b[SHA512_HASHSZ];
 492
 493   /* Unpack the public key.  Negate it: we're meant to subtract the term
 494    * involving the public key point, and this is easier than negating the
 495    * scalar.
 496    */
 497   if (ptdecode(&AX, &AY, &AZ, K)) return (-1);
 498   f25519_neg(&AX, &AX);
 499
 500   /* Load the scalar and check that it's in range.  The easy way is to store
 501    * it again and see if the two match.
 502    */
 503   scaf_loaddbl(tt, sig + 32, 32, 2*NPIECE, PIECEWD);
 504   scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch);
 505   scaf_store(b, 32, s, NPIECE, PIECEWD);
 506   if (memcmp(b, sig + 32, 32) != 0) return (-1);
 507
 508   /* Check the signature. */
 509   sha512_init(&h);
 510   sha512_hash(&h, sig, 32);
 511   sha512_hash(&h, K, 32);
 512   sha512_hash(&h, m, msz);
 513   sha512_done(&h, b);
 514   scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD);
 515   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 516   ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ);
 517   ptencode(b, &RX, &RY, &RZ);
 518   if (memcmp(b, sig, 32) != 0) return (-1);
 519
 520   /* All is good. */
 521   return (0);
 522 }
 523
 524 /*----- Test rig ----------------------------------------------------------*/
 525
 526 #ifdef TEST_RIG
 527
 528 #include <stdio.h>
 529 #include <string.h>
 530
 531 #include <mLib/report.h>
 532 #include <mLib/testrig.h>
 533
 534 static int vrf_pubkey(dstr dv[])
 535 {
 536   dstr dpub = DSTR_INIT;
 537   int ok = 1;
 538
 539   if (dv[1].len != ED25519_PUBSZ) die(1, "bad pub length");
 540
 541   dstr_ensure(&dpub, ED25519_PUBSZ); dpub.len = ED25519_PUBSZ;
 542   ed25519_pubkey((octet *)dpub.buf, dv[0].buf, dv[0].len);
 543   if (memcmp(dpub.buf, dv[1].buf, ED25519_PUBSZ) != 0) {
 544     ok = 0;
 545     fprintf(stderr, "failed!");
 546     fprintf(stderr, "\n\tpriv = "); type_hex.dump(&dv[0], stderr);
 547     fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dpub, stderr);
 548     fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[1], stderr);
 549     fprintf(stderr, "\n");
 550   }
 551
 552   dstr_destroy(&dpub);
 553   return (ok);
 554 }
 555
 556 static int vrf_sign(dstr dv[])
 557 {
 558   octet K[ED25519_PUBSZ];
 559   dstr dsig = DSTR_INIT;
 560   int ok = 1;
 561
 562   if (dv[2].len != ED25519_SIGSZ) die(1, "bad result length");
 563
 564   dstr_ensure(&dsig, ED25519_SIGSZ); dsig.len = ED25519_SIGSZ;
 565   ed25519_pubkey(K, dv[0].buf, dv[0].len);
 566   ed25519_sign((octet *)dsig.buf, dv[0].buf, dv[0].len, K,
 567                dv[1].buf, dv[1].len);
 568   if (memcmp(dsig.buf, dv[2].buf, ED25519_SIGSZ) != 0) {
 569     ok = 0;
 570     fprintf(stderr, "failed!");
 571     fprintf(stderr, "\n\tpriv = "); type_hex.dump(&dv[0], stderr);
 572     fprintf(stderr, "\n\t msg = "); type_hex.dump(&dv[1], stderr);
 573     fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dsig, stderr);
 574     fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[2], stderr);
 575     fprintf(stderr, "\n");
 576   }
 577
 578   dstr_destroy(&dsig);
 579   return (ok);
 580 }
 581
 582 static int vrf_verify(dstr dv[])
 583 {
 584   int rc_want, rc_calc;
 585   int ok = 1;
 586
 587   if (dv[0].len != ED25519_PUBSZ) die(1, "bad pub length");
 588   if (dv[2].len != ED25519_SIGSZ) die(1, "bad sig length");
 589   rc_want = *(int *)dv[3].buf;
 590
 591   rc_calc = ed25519_verify((const octet *)dv[0].buf,
 592                            dv[1].buf, dv[1].len,
 593                            (const octet *)dv[2].buf);
 594   if (!rc_want != !rc_calc) {
 595     ok = 0;
 596     fprintf(stderr, "failed!");
 597     fprintf(stderr, "\n\t pub = "); type_hex.dump(&dv[0], stderr);
 598     fprintf(stderr, "\n\t msg = "); type_hex.dump(&dv[1], stderr);
 599     fprintf(stderr, "\n\t sig = "); type_hex.dump(&dv[2], stderr);
 600     fprintf(stderr, "\n\tcalc = %d", rc_calc);
 601     fprintf(stderr, "\n\twant = %d", rc_want);
 602     fprintf(stderr, "\n");
 603   }
 604
 605   return (ok);
 606 }
 607
 608 static test_chunk tests[] = {
 609   { "pubkey", vrf_pubkey, { &type_hex, &type_hex } },
 610   { "sign", vrf_sign, { &type_hex, &type_hex, &type_hex } },
 611   { "verify", vrf_verify, { &type_hex, &type_hex, &type_hex, &type_int } },
 612   { 0, 0, { 0 } }
 613 };
 614
 615 int main(int argc, char *argv[])
 616 {
 617   test_run(argc, argv, tests, SRCDIR "/t/ed25519");
 618   return (0);
 619 }
 620
 621 #endif
 622
 623 /*----- That's all, folks -------------------------------------------------*/