[catacomb] / pub / ed25519.c

/* -*-c-*-
 *
 * The Ed25519 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 <string.h>

#include "f25519.h"
#include "ed25519.h"
#include "scaf.h"
#include "sha512.h"

/*----- Key fetching ------------------------------------------------------*/

const key_fetchdef ed25519_pubfetch[] = {
  { "pub",      offsetof(ed25519_pub, pub),     KENC_BINARY,    0 },
  { 0,          0,                              0,              0 }
};

static const key_fetchdef priv[] = {
  { "priv",     offsetof(ed25519_priv, priv),   KENC_BINARY,    0 },
  { 0,          0,                              0,              0 }
};

const key_fetchdef ed25519_privfetch[] = {
  { "pub",      offsetof(ed25519_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[] = {
    0xf5d3ed, 0x631a5c, 0xd65812, 0xa2f79c, 0xdef9de, 0x000014,
    0x000000, 0x000000, 0x000000, 0x000000, 0x001000
  };
  static const scaf_piece mu[] = {
    0x1b3994, 0x0a2c13, 0x9ce5a3, 0x29a7ed, 0x5d0863, 0x210621,
    0xffffeb, 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0x000fff
  };
#endif

#if SCAF_IMPL == 16
# define PIECEWD 12
  static const scaf_piece l[] = {
    0x3ed, 0xf5d, 0xa5c, 0x631, 0x812, 0xd65,
    0x79c, 0xa2f, 0x9de, 0xdef, 0x014, 0x000,
    0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
    0x000, 0x000, 0x000, 0x001
  };
  static const scaf_piece mu[] = {
    0x994, 0x1b3, 0xc13, 0x0a2, 0x5a3, 0x9ce,
    0x7ed, 0x29a, 0x863, 0x5d0, 0x621, 0x210,
    0xfeb, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff,
    0xfff, 0xfff, 0xfff, 0xfff, 0xfff
  };
#endif

#define NPIECE SCAF_NPIECE(255, PIECEWD)

#if F25519_IMPL == 26
# define P p26
  static const f25519_piece bx_pieces[] = {
    -14297830,  -7645148,  16144683, -16471763,  27570974,
     -2696100, -26142465,   8378389,  20764389,   8758491
  }, by_pieces[] = {
    -26843541,  -6710886,  13421773, -13421773,  26843546,
      6710886, -13421773,  13421773, -26843546,  -6710886
  }, d_pieces[] = {
    -10913610,  13857413, -15372611,   6949391,    114729,
     -8787816,  -6275908,  -3247719, -18696448, -12055116
  };
#endif
#if F25519_IMPL == 10
# define P p10
  static const f25519_piece bx_pieces[] = {
     282,  373,  242,  386, -467,   86, -423,  318, -437,
      75,  236, -308,  421,   92,  439,  -35,  400,  452,
      82,  -40,  160,  441,  -51,  437, -365,  134
  }, by_pieces[] = {
    -405,  410, -410,  410, -410, -102,  205, -205,  205,
    -205,  205, -410,  410, -410,  410,  102, -205,  205,
    -205,  205, -205,  410, -410,  410, -410, -102
  }, d_pieces[] = {
     182, -418,  310, -216, -178, -133,  367, -315, -380,
    -351, -182, -255,    2,  152, -390, -136,  -52, -383,
    -412, -398,  -12,  448, -469, -196,   55, -184
  };
#endif

static const f25519_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ };
#define BX ((const f25519 *)bx_pieces)
#define BY ((const f25519 *)by_pieces)
#define BZ ((const f25519 *)bz_pieces)
#define D ((const f25519 *)d_pieces)

/*----- Point encoding and decoding ---------------------------------------*/

static void ptencode(octet q[32],
                     const f25519 *X, const f25519 *Y, const f25519 *Z)
{
  f25519 x, y, t;
  octet b[32];

  f25519_inv(&t, Z); f25519_mul(&x, X, &t); f25519_mul(&y, Y, &t);
  f25519_store(q, &y); f25519_store(b, &x); q[31] |= (b[0]&1u) << 7;
}

static int ptdecode(f25519 *X, f25519 *Y, f25519 *Z, const octet q[32])
{
  octet b[32];
  unsigned i, a;
  f25519 t, u;
  uint32 m;
  int rc = 0;

  /* Load the y-coordinate. */
  memcpy(b, q, 32); b[31] &= 0x7fu; f25519_load(Y, b);

  /* Check that the coordinate was in range.  If we store it, we'll get a
   * canonical version which we can compare against Q; be careful not to
   * check the top bit.
   */
  f25519_store(b, Y);
  for (i = a = 0; i < 31; i++) a |= b[i] ^ q[i];
  a |= (b[31] ^ q[31])&0x7fu;
  a = ((a - 1) >> 8)&0x01u;             /* 0 |-> 1, non-0 |-> 0 */
  rc |= (int)a - 1;

  /* Decompress the x-coordinate. */
  f25519_sqr(&t, Y); f25519_mul(&u, &t, D); t.P[0] -= 1; u.P[0] += 1;
  rc |= f25519_quosqrt(X, &t, &u);
  f25519_store(b, X); m = -(uint32)(((q[31] >> 7) ^ b[0])&0x1u);
  f25519_condneg(X, X, m);

  /* Set Z. */
  f25519_set(Z, 1);

  /* And we're done. */
  return (rc);
}

/*----- Edwards curve arithmetic ------------------------------------------*/

static void ptadd(f25519 *X, f25519 *Y, f25519 *Z,
                  const f25519 *X0, const f25519 *Y0, const f25519 *Z0,
                  const f25519 *X1, const f25519 *Y1, const f25519 *Z1)
{
  f25519 t0, t1, t2, t3;

  /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
   * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.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 - a C);   Z3 = F G.
   *
   * Note that a = -1, which things easier.
   */

  f25519_mul(&t0, Z0, Z1);              /* t0 = A = Z0 Z1 */
  f25519_add(&t1, X0, Y0);              /* t1 = X0 + Y0 */
  f25519_add(&t2, X1, Y1);              /* t2 = X1 + Y1 */
  f25519_mul(&t1, &t1, &t2);            /* t1 = (X0 + Y0) (X1 + Y1) */
  f25519_mul(&t2, X0, X1);              /* t2 = C = X0 X1 */
  f25519_mul(&t3, Y0, Y1);              /* t3 = D = Y0 Y1 */
  f25519_add(Y, &t2, &t3);              /* Y = C + D = D - a C */
  f25519_sub(X, &t1, Y);                /* X = (X0 + Y0) (X1 + Y1) - C - D */
  f25519_mul(X, X, &t0);            /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
  f25519_mul(Y, Y, &t0);                /* Y = A (D - a C) */
  f25519_sqr(&t0, &t0);                 /* t0 = B = A^2 */
  f25519_mul(&t1, &t2, &t3);            /* t1 = C D */
  f25519_mul(&t1, &t1, D);              /* t1 = E = d C D */
  f25519_sub(&t2, &t0, &t1);            /* t2 = F = B - E */
  f25519_add(&t1, &t0, &t1);            /* t1 = G = B + E */
  f25519_mul(X, X, &t2);          /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
  f25519_mul(Y, Y, &t1);                /* Y = A G (D - a C) */
  f25519_mul(Z, &t1, &t2);              /* Z = F G */
}

static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z,
                  const f25519 *X0, const f25519 *Y0, const f25519 *Z0)
{
  f25519 t0, t1, t2;

  /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
   * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
   * formulae as:
   *
   *    B = (X1 + Y1)^2;   C = X1^2;   D = Y1^2;   E = a C;
   *    F = E + D;   H = Z1^2;   J = F - 2 H;
   *    X3 = (B - C - D) J;   Y3 = F (E - D);   Z3 = F J.
   *
   * Note that a = -1, which things easier.
   */

  f25519_add(&t0, X0, Y0);              /* t0 = X0 + Y0 */
  f25519_sqr(&t0, &t0);                 /* t0 = B = (X0 + Y0)^2 */
  f25519_sqr(&t1, X0);                  /* t1 = C = X0^2 */
  f25519_sqr(&t2, Y0);                  /* t2 = D = Y0^2 */
  f25519_add(Y, &t1, &t2);              /* Y = C + D = -(E - D) */
  f25519_sub(X, &t0, Y);                /* X = B - C - D */
                                        /* (E = a C = -C) */
  f25519_sub(&t0, &t2, &t1);            /* t0 = F = D - C = E + D */
  f25519_sqr(&t1, Z0);                  /* t1 = H = Z0^2 */
  f25519_mulconst(&t1, &t1, 2);         /* t1 = 2 H */
  f25519_sub(&t1, &t0, &t1);            /* t1 = J = F - 2 H */
  f25519_mul(X, X, &t1);                /* X = (B - C - D) J */
  f25519_mul(Y, Y, &t0);                /* Y = -F (E - D) */
  f25519_neg(Y, Y);                     /* Y = F (E - D) */
  f25519_mul(Z, &t0, &t1);              /* Z = F J */
}

static void ptmul(f25519 *X, f25519 *Y, f25519 *Z,
                  const scaf_piece n[NPIECE],
                  const f25519 *X0, const f25519 *Y0, const f25519 *Z0)
{
  /* We assume that the window width divides the scalar piece width. */
#define WINWD 4
#define WINLIM (1 << WINWD)
#define WINMASK (WINLIM - 1)
#define TABSZ (WINLIM/2 + 1)

  f25519 VX[TABSZ], VY[TABSZ], VZ[TABSZ];
  f25519 TX, TY, TZ, UX, UY, UZ;
  unsigned i, j, k, w;
  uint32 m_neg;
  scaf_piece ni;

  /* Build a table of small multiples. */
  f25519_set(&VX[0], 0); f25519_set(&VY[0], 1); f25519_set(&VZ[0], 1);
  VX[1] = *X0; VY[1] = *Y0; VZ[1] = *Z0;
  ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]);
  for (i = 3; i < TABSZ; i += 2) {
    ptadd(&VX[i], &VY[i], &VZ[i],
          &VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0);
    ptdbl(&VX[i + 1], &VY[i + 1], &VZ[i + 1],
          &VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]);
  }

  /* Now do the multiplication.  We lag a window behind the cursor position
   * because of the scalar recoding we do.
   */
  f25519_set(&TX, 0); f25519_set(&TY, 1); f25519_set(&TZ, 1);
  for (i = NPIECE, w = 0, m_neg = 0; i--; ) {
    ni = n[i];

    /* Work through each window in the scalar piece. */
    for (j = 0; j < PIECEWD; j += WINWD) {

      /* Shift along by a window. */
      for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ);

      /* Peek at the next window of four bits.  If the top bit is set we lend
       * a bit leftwards, into w.  It's too late for this to affect the sign
       * now, but if we negated earlier then the addition would be wrong.
       */
      w += (ni >> (PIECEWD - 1))&0x1u;
      w = ((WINLIM - w)&m_neg) | (w&~m_neg);

      /* Collect the entry from the table, and add or subtract. */
      f25519_pickn(&UX, VX, TABSZ, w);
      f25519_pickn(&UY, VY, TABSZ, w);
      f25519_pickn(&UZ, VZ, TABSZ, w);
      f25519_condneg(&UX, &UX, m_neg);
      ptadd(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ);

      /* Move the next window into the delay slot.  If its top bit is set,
       * then negate it and set m_neg.
       */
      w = (ni >> (PIECEWD - WINWD))&WINMASK;
      m_neg = -(uint32)((w >> (WINWD - 1))&0x1u);
      ni <<= WINWD;
    }
  }

  /* Do the final window.  Just fix the sign and go. */
  for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ);
  w = ((WINLIM - w)&m_neg) | (w&~m_neg);
  f25519_pickn(&UX, VX, TABSZ, w);
  f25519_pickn(&UY, VY, TABSZ, w);
  f25519_pickn(&UZ, VZ, TABSZ, w);
  f25519_condneg(&UX, &UX, m_neg);
  ptadd(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ);

#undef WINWD
#undef WINLIM
#undef WINMASK
#undef TABSZ
}

static void ptsimmul(f25519 *X, f25519 *Y, f25519 *Z,
                     const scaf_piece n0[NPIECE],
                     const f25519 *X0, const f25519 *Y0, const f25519 *Z0,
                     const scaf_piece n1[NPIECE],
                     const f25519 *X1, const f25519 *Y1, const f25519 *Z1)
{
  /* We assume that the window width divides the scalar piece width. */
#define WINWD 2
#define WINLIM (1 << WINWD)
#define WINMASK (WINLIM - 1)
#define TABSZ (1 << 2*WINWD)

  f25519 VX[TABSZ], VY[TABSZ], VZ[TABSZ];
  f25519 TX, TY, TZ, UX, UY, UZ;
  unsigned i, j, k, w, ni0, ni1;

  /* Build a table of small linear combinations. */
  f25519_set(&VX[0], 0); f25519_set(&VY[0], 1); f25519_set(&VZ[0], 1);
  VX[1] = *X0; VX[WINLIM] = *X1;
  VY[1] = *Y0; VY[WINLIM] = *Y1;
  VZ[1] = *Z0; VZ[WINLIM] = *Z1;
  for (i = 2; i < WINLIM; i <<= 1) {
    ptdbl(&VX[i], &VY[i], &VZ[i],
          &VX[i/2], &VY[i/2], &VZ[i/2]);
    ptdbl(&VX[i*WINLIM], &VY[i*WINLIM], &VZ[i*WINLIM],
          &VX[i*WINLIM/2], &VY[i*WINLIM/2], &VZ[i*WINLIM/2]);
  }
  for (i = 2; i < TABSZ; i <<= 1) {
    for (j = 1; j < i; j++)
      ptadd(&VX[i + j], &VY[i + j], &VZ[i + j],
            &VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]);
  }

  /* Do the multiplication. */
  f25519_set(&TX, 0); f25519_set(&TY, 1); f25519_set(&TZ, 1);
  for (i = NPIECE; i--; ) {
    ni0 = n0[i]; ni1 = n1[i];

    /* Work through each window in the scalar pieces. */
    for (j = 0; j < PIECEWD; j += WINWD) {

      /* Shift along by a window. */
      for (k = 0; k < WINWD; k++) ptdbl(&TX, &TY, &TZ, &TX, &TY, &TZ);

      /* Collect the next window from the scalars. */
      w = ((ni0 >> (PIECEWD - WINWD))&WINMASK) |
        ((ni1 >> (PIECEWD - 2*WINWD))&(WINMASK << WINWD));
      ni0 <<= WINWD; ni1 <<= WINWD;

      /* Collect the entry from the table, and add. */
      f25519_pickn(&UX, VX, TABSZ, w);
      f25519_pickn(&UY, VY, TABSZ, w);
      f25519_pickn(&UZ, VZ, TABSZ, w);
      ptadd(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ);
    }
  }

  /* Done. */
  *X = TX; *Y = TY; *Z = TZ;
}

/*----- Key derivation utilities ------------------------------------------*/

static void unpack_key(scaf_piece a[NPIECE], octet h1[32],
                       const octet *k, size_t ksz)
{
  sha512_ctx h;
  octet b[SHA512_HASHSZ];

  sha512_init(&h); sha512_hash(&h, k, ksz); sha512_done(&h, b);
  b[0] &= 0xf8u; b[31] = (b[31]&0x3f) | 0x40;
  scaf_load(a, b, 32, NPIECE, PIECEWD);
  if (h1) memcpy(h1, b + 32, 32);
}

#define PREFIX_BUFSZ 290
static size_t prefix(octet b[PREFIX_BUFSZ],
                     int phflag, const octet *p, size_t psz)
{
  if (phflag < 0) return (0);
  memcpy(b, "SigEd25519 no Ed25519 collisions", 32);
  b[32] = phflag;
  assert(psz < ED25519_MAXPERSOSZ); b[33] = psz; memcpy(b + 34, p, psz);
  return (psz + 34);
}

/*----- Main code ---------------------------------------------------------*/

/* --- @ed25519_pubkey@ --- *
 *
 * Arguments:   @octet K[ED25519_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 ed25519_pubkey(octet K[ED25519_PUBSZ], const void *k, size_t ksz)
{
  scaf_piece a[NPIECE];
  f25519 AX, AY, AZ;

  unpack_key(a, 0, k, ksz);
  ptmul(&AX, &AY, &AZ, a, BX, BY, BZ);
  ptencode(K, &AX, &AY, &AZ);
}

/* --- @ed25519_sign@, @ed25519ctx_sign@ --- *
 *
 * Arguments:   @octet sig[ED25519_SIGSZ]@ = where to put the signature
 *              @const void *k@ = private key
 *              @size_t ksz@ = length of private key
 *              @const octet K[ED25519_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.
 *
 *              In @ed25519ctx_sign@, if @phflag@ is @-1@ then you get plain
 *              old Ed25519: the personalization string pointer @p@ will be
 *              ignored.  If @phflag > 0@ then the `message' @m@ should be a
 *              SHA512 hash of the actual message.
 */

void ed25519ctx_sign(octet sig[ED25519_SIGSZ],
                     const void *k, size_t ksz, const octet K[ED25519_PUBSZ],
                     int phflag, const void *p, size_t psz,
                     const void *m, size_t msz)
{
  sha512_ctx h;
  scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE + 1];
  scaf_dblpiece tt[2*NPIECE];
  f25519 RX, RY, RZ;
  octet h1[32], pb[PREFIX_BUFSZ], rb[SHA512_HASHSZ];
  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. */
  sha512_init(&h);
  sha512_hash(&h, pb, psz);
  sha512_hash(&h, h1, 32);
  sha512_hash(&h, m, msz);
  sha512_done(&h, rb);
  scaf_loaddbl(tt, rb, 64, 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. */
  sha512_init(&h);
  sha512_hash(&h, pb, psz);
  sha512_hash(&h, sig, 32);
  sha512_hash(&h, K, 32);
  sha512_hash(&h, m, msz);
  sha512_done(&h, rb);
  scaf_loaddbl(tt, rb, 64, 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 + 32, 32, t, NPIECE, PIECEWD);
}

void ed25519_sign(octet sig[ED25519_SIGSZ],
                  const void *k, size_t ksz, const octet K[ED25519_PUBSZ],
                  const void *m, size_t msz)
  { ed25519ctx_sign(sig, k, ksz, K, -1, 0, 0, m, msz); }

/* --- @ed25519_verify@, @ed25519ctx_verify@ --- *
 *
 * Arguments:   @const octet K[ED25519_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
 *              @const octet sig[ED25519_SIGSZ]@ = signature
 *
 * Returns:     Zero if OK, negative on failure.
 *
 * Use:         Verify a signature.
 *
 *              In @ed25519ctx_verify@, if @phflag@ is @-1@ then you get
 *              plain old Ed25519: the personalization string pointer @p@
 *              will be ignored.  If @phflag > 0@ then the `message' @m@
 *              should be a SHA512 hash of the actual message.
 */

int ed25519ctx_verify(const octet K[ED25519_PUBSZ],
                      int phflag, const void *p, size_t psz,
                      const void *m, size_t msz,
                      const octet sig[ED25519_SIGSZ])
{
  sha512_ctx h;
  scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE + 1];
  scaf_dblpiece tt[2*NPIECE];
  f25519 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);
  f25519_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 + 32, 32, 2*NPIECE, PIECEWD);
  scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch);
  scaf_store(b, 32, s, NPIECE, PIECEWD);
  if (memcmp(b, sig + 32, 32) != 0) return (-1);

  /* Check the signature. */
  psz = prefix(b, phflag, p, psz);
  sha512_init(&h);
  sha512_hash(&h, b, psz);
  sha512_hash(&h, sig, 32);
  sha512_hash(&h, K, 32);
  sha512_hash(&h, m, msz);
  sha512_done(&h, b);
  scaf_loaddbl(tt, b, 64, 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, 32) != 0) return (-1);

  /* All is good. */
  return (0);
}

int ed25519_verify(const octet K[ED25519_PUBSZ],
                   const void *m, size_t msz,
                   const octet sig[ED25519_SIGSZ])
  { return (ed25519ctx_verify(K, -1, 0, 0, m, msz, sig)); }

/*----- Test rig ----------------------------------------------------------*/

#ifdef TEST_RIG

#include <stdio.h>
#include <string.h>

#include <mLib/report.h>
#include <mLib/testrig.h>

static int vrf_pubkey(dstr dv[])
{
  dstr dpub = DSTR_INIT;
  int ok = 1;

  if (dv[1].len != ED25519_PUBSZ) die(1, "bad pub length");

  dstr_ensure(&dpub, ED25519_PUBSZ); dpub.len = ED25519_PUBSZ;
  ed25519_pubkey((octet *)dpub.buf, dv[0].buf, dv[0].len);
  if (memcmp(dpub.buf, dv[1].buf, ED25519_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)
{
  sha512_ctx h;
  octet K[ED25519_PUBSZ];
  dstr d = DSTR_INIT, dsig = DSTR_INIT, *m;
  int ok = 1;

  if (want->len != ED25519_SIGSZ) die(1, "bad result length");

  dstr_ensure(&dsig, ED25519_SIGSZ); dsig.len = ED25519_SIGSZ;
  if (phflag <= 0)
    m = msg;
  else {
    dstr_ensure(&d, SHA512_HASHSZ); d.len = SHA512_HASHSZ;
    sha512_init(&h);
    sha512_hash(&h, msg->buf, msg->len);
    sha512_done(&h, d.buf);
    m = &d;
  }
  ed25519_pubkey(K, priv->buf, priv->len);
  ed25519ctx_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, ED25519_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_trad(dstr *dv)
  { return (vrf_sign(&dv[0], -1, 0, &dv[1], &dv[2])); }

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)
{
  sha512_ctx h;
  int rc_calc;
  dstr d = DSTR_INIT, *m;
  int ok = 1;

  if (pub->len != ED25519_PUBSZ) die(1, "bad pub length");
  if (sig->len != ED25519_SIGSZ) die(1, "bad sig length");

  if (phflag <= 0)
    m = msg;
  else {
    dstr_ensure(&d, SHA512_HASHSZ); d.len = SHA512_HASHSZ;
    sha512_init(&h);
    sha512_hash(&h, msg->buf, msg->len);
    sha512_done(&h, d.buf);
    m = &d;
  }
  rc_calc = ed25519ctx_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_trad(dstr *dv)
  { return (vrf_verify(&dv[0], -1, 0, &dv[1], &dv[2], *(int *)dv[3].buf)); }

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_trad,
    { &type_hex, &type_hex, &type_hex } },
  { "verify", vrf_verify_trad,
    { &type_hex, &type_hex, &type_hex, &type_int } },
  { "sign-ctx", vrf_sign_ctx,
    { &type_hex, &type_int, &type_hex, &type_hex, &type_hex } },
  { "verify-ctx", 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/ed25519");
  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/