chiark - git - mdw - secnet/blob - 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 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 "f25519.h"
  52 #include "ed25519.h"
  53 #include "scaf.h"
  54 #include "scmul.h"
  55 #include "sha512.h"
  56
  57 /*----- A number of magic numbers -----------------------------------------*/
  58
  59 # define PIECEWD 24
  60   static const scaf_piece l[] = {
  61     0xf5d3ed, 0x631a5c, 0xd65812, 0xa2f79c, 0xdef9de, 0x000014,
  62     0x000000, 0x000000, 0x000000, 0x000000, 0x001000
  63   };
  64   static const scaf_piece mu[] = {
  65     0x1b3994, 0x0a2c13, 0x9ce5a3, 0x29a7ed, 0x5d0863, 0x210621,
  66     0xffffeb, 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0x000fff
  67   };
  68
  69 #define NPIECE SCAF_NPIECE(255, PIECEWD)
  70
  71 # define P p26
  72   static const f25519_piece bx_pieces[] = {
  73     -14297830,  -7645148,  16144683, -16471763,  27570974,
  74      -2696100, -26142465,   8378389,  20764389,   8758491
  75   }, by_pieces[] = {
  76     -26843541,  -6710886,  13421773, -13421773,  26843546,
  77       6710886, -13421773,  13421773, -26843546,  -6710886
  78   }, d_pieces[] = {
  79     -10913610,  13857413, -15372611,   6949391,    114729,
  80      -8787816,  -6275908,  -3247719, -18696448, -12055116
  81   };
  82
  83 static const f25519_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ };
  84 #define BX ((const f25519 *)bx_pieces)
  85 #define BY ((const f25519 *)by_pieces)
  86 #define BZ ((const f25519 *)bz_pieces)
  87 #define D ((const f25519 *)d_pieces)
  88
  89 /*----- Point encoding and decoding ---------------------------------------*/
  90
  91 static void ptencode(octet q[32],
  92                      const f25519 *X, const f25519 *Y, const f25519 *Z)
  93 {
  94   f25519 x, y, t;
  95   octet b[32];
  96
  97   f25519_inv(&t, Z); f25519_mul(&x, X, &t); f25519_mul(&y, Y, &t);
  98   f25519_store(q, &y); f25519_store(b, &x); q[31] |= (b[0]&1u) << 7;
  99 }
 100
 101 static int ptdecode(f25519 *X, f25519 *Y, f25519 *Z, const octet q[32])
 102 {
 103   octet b[32];
 104   unsigned i, a;
 105   f25519 t, u;
 106   uint32 m;
 107   int rc = 0;
 108
 109   /* Load the y-coordinate. */
 110   memcpy(b, q, 32); b[31] &= 0x7fu; f25519_load(Y, b);
 111
 112   /* Check that the coordinate was in range.  If we store it, we'll get a
 113    * canonical version which we can compare against Q; be careful not to
 114    * check the top bit.
 115    */
 116   f25519_store(b, Y);
 117   for (i = a = 0; i < 31; i++) a |= b[i] ^ q[i];
 118   a |= (b[31] ^ q[31])&0x7fu;
 119   a = ((a - 1) >> 8)&0x01u;             /* 0 |-> 1, non-0 |-> 0 */
 120   rc |= (int)a - 1;
 121
 122   /* Decompress the x-coordinate. */
 123   f25519_sqr(&t, Y); f25519_mul(&u, &t, D); t.P[0] -= 1; u.P[0] += 1;
 124   rc |= f25519_quosqrt(X, &t, &u);
 125   f25519_store(b, X); m = -(uint32)(((q[31] >> 7) ^ b[0])&0x1u);
 126   f25519_condneg(X, X, m);
 127
 128   /* Set Z. */
 129   f25519_set(Z, 1);
 130
 131   /* And we're done. */
 132   return (rc);
 133 }
 134
 135 /*----- Edwards curve arithmetic ------------------------------------------*/
 136
 137 static void ptadd(f25519 *X, f25519 *Y, f25519 *Z,
 138                   const f25519 *X0, const f25519 *Y0, const f25519 *Z0,
 139                   const f25519 *X1, const f25519 *Y1, const f25519 *Z1)
 140 {
 141   f25519 t0, t1, t2, t3;
 142
 143   /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
 144    * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
 145    * formulae as:
 146    *
 147    *    A = Z1 Z2;   B = A^2;   C = X1 X2;   D = Y1 Y2;
 148    *    E = d C D;   F = B - E;   G = B + E;
 149    *    X3 = A F ((X1 + Y1) (X2 + Y2) - C - D);
 150    *    Y3 = A G (D - a C);   Z3 = F G.
 151    *
 152    * Note that a = -1, which things easier.
 153    */
 154
 155   f25519_mul(&t0, Z0, Z1);              /* t0 = A = Z0 Z1 */
 156   f25519_add(&t1, X0, Y0);              /* t1 = X0 + Y0 */
 157   f25519_add(&t2, X1, Y1);              /* t2 = X1 + Y1 */
 158   f25519_mul(&t1, &t1, &t2);            /* t1 = (X0 + Y0) (X1 + Y1) */
 159   f25519_mul(&t2, X0, X1);              /* t2 = C = X0 X1 */
 160   f25519_mul(&t3, Y0, Y1);              /* t3 = D = Y0 Y1 */
 161   f25519_add(Y, &t2, &t3);              /* Y = C + D = D - a C */
 162   f25519_sub(X, &t1, Y);                /* X = (X0 + Y0) (X1 + Y1) - C - D */
 163   f25519_mul(X, X, &t0);            /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
 164   f25519_mul(Y, Y, &t0);                /* Y = A (D - a C) */
 165   f25519_sqr(&t0, &t0);                 /* t0 = B = A^2 */
 166   f25519_mul(&t1, &t2, &t3);            /* t1 = C D */
 167   f25519_mul(&t1, &t1, D);              /* t1 = E = d C D */
 168   f25519_sub(&t2, &t0, &t1);            /* t2 = F = B - E */
 169   f25519_add(&t1, &t0, &t1);            /* t1 = G = B + E */
 170   f25519_mul(X, X, &t2);          /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
 171   f25519_mul(Y, Y, &t1);                /* Y = A G (D - a C) */
 172   f25519_mul(Z, &t1, &t2);              /* Z = F G */
 173 }
 174
 175 static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z,
 176                   const f25519 *X0, const f25519 *Y0, const f25519 *Z0)
 177 {
 178   f25519 t0, t1, t2;
 179
 180   /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
 181    * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
 182    * formulae as:
 183    *
 184    *    B = (X1 + Y1)^2;   C = X1^2;   D = Y1^2;   E = a C;
 185    *    F = E + D;   H = Z1^2;   J = F - 2 H;
 186    *    X3 = (B - C - D) J;   Y3 = F (E - D);   Z3 = F J.
 187    *
 188    * Note that a = -1, which things easier.
 189    */
 190
 191   f25519_add(&t0, X0, Y0);              /* t0 = X0 + Y0 */
 192   f25519_sqr(&t0, &t0);                 /* t0 = B = (X0 + Y0)^2 */
 193   f25519_sqr(&t1, X0);                  /* t1 = C = X0^2 */
 194   f25519_sqr(&t2, Y0);                  /* t2 = D = Y0^2 */
 195   f25519_add(Y, &t1, &t2);              /* Y = C + D = -(E - D) */
 196   f25519_sub(X, &t0, Y);                /* X = B - C - D */
 197                                         /* (E = a C = -C) */
 198   f25519_sub(&t0, &t2, &t1);            /* t0 = F = D - C = E + D */
 199   f25519_sqr(&t1, Z0);                  /* t1 = H = Z0^2 */
 200   f25519_add(&t1, &t1, &t1);            /* t1 = 2 H */
 201   f25519_sub(&t1, &t0, &t1);            /* t1 = J = F - 2 H */
 202   f25519_mul(X, X, &t1);                /* X = (B - C - D) J */
 203   f25519_mul(Y, Y, &t0);                /* Y = -F (E - D) */
 204   f25519_neg(Y, Y);                     /* Y = F (E - D) */
 205   f25519_mul(Z, &t0, &t1);              /* Z = F J */
 206 }
 207
 208 static DEFINE_SCMUL(ptmul, f25519, 4, PIECEWD, NPIECE, ptadd, ptdbl)
 209 static DEFINE_SCSIMMUL(ptsimmul, f25519, 2, PIECEWD, NPIECE, ptadd, ptdbl)
 210
 211 /*----- Key derivation utilities ------------------------------------------*/
 212
 213 static void unpack_key(scaf_piece a[NPIECE], octet h1[32],
 214                        const octet *k, size_t ksz)
 215 {
 216   struct sha512_ctx h;
 217   octet b[SHA512_DIGEST_SIZE];
 218
 219   sha512_init_ctx(&h); sha512_process_bytes(k, ksz, &h); sha512_finish_ctx(&h, b);
 220   b[0] &= 0xf8u; b[31] = (b[31]&0x3f) | 0x40;
 221   scaf_load(a, b, 32, NPIECE, PIECEWD);
 222   if (h1) memcpy(h1, b + 32, 32);
 223 }
 224
 225 #define PREFIX_BUFSZ 290
 226 static size_t prefix(octet b[PREFIX_BUFSZ],
 227                      int phflag, const octet *p, size_t psz)
 228 {
 229   if (phflag < 0) return (0);
 230   memcpy(b, "SigEd25519 no Ed25519 collisions", 32);
 231   b[32] = phflag;
 232   assert(psz < ED25519_MAXPERSOSZ); b[33] = psz; memcpy(b + 34, p, psz);
 233   return (psz + 34);
 234 }
 235
 236 /*----- Main code ---------------------------------------------------------*/
 237
 238 /* --- @ed25519_pubkey@ --- *
 239  *
 240  * Arguments:   @octet K[ED25519_PUBSZ]@ = where to put the public key
 241  *              @const void *k@ = private key
 242  *              @size_t ksz@ = length of private key
 243  *
 244  * Returns:     ---
 245  *
 246  * Use:         Derives the public key from a private key.
 247  */
 248
 249 void ed25519_pubkey(octet K[ED25519_PUBSZ], const void *k, size_t ksz)
 250 {
 251   scaf_piece a[NPIECE];
 252   f25519 AX, AY, AZ;
 253
 254   unpack_key(a, 0, k, ksz);
 255   ptmul(&AX, &AY, &AZ, a, BX, BY, BZ);
 256   ptencode(K, &AX, &AY, &AZ);
 257 }
 258
 259 /* --- @ed25519_sign@, @ed25519ctx_sign@ --- *
 260  *
 261  * Arguments:   @octet sig[ED25519_SIGSZ]@ = where to put the signature
 262  *              @const void *k@ = private key
 263  *              @size_t ksz@ = length of private key
 264  *              @const octet K[ED25519_PUBSZ]@ = public key
 265  *              @int phflag@ = whether the `message' has been hashed already
 266  *              @const void *p@ = personalization string
 267  *              @size_t psz@ = length of personalization string
 268  *              @const void *m@ = message to sign
 269  *              @size_t msz@ = length of message
 270  *
 271  * Returns:     ---
 272  *
 273  * Use:         Signs a message.
 274  *
 275  *              In @ed25519ctx_sign@, if @phflag@ is @-1@ then you get plain
 276  *              old Ed25519: the personalization string pointer @p@ will be
 277  *              ignored.  If @phflag > 0@ then the `message' @m@ should be a
 278  *              SHA512 hash of the actual message.
 279  */
 280
 281 void ed25519ctx_sign(octet sig[ED25519_SIGSZ],
 282                      const void *k, size_t ksz, const octet K[ED25519_PUBSZ],
 283                      int phflag, const void *p, size_t psz,
 284                      const void *m, size_t msz)
 285 {
 286   struct sha512_ctx h;
 287   scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE];
 288   scaf_dblpiece tt[2*NPIECE];
 289   f25519 RX, RY, RZ;
 290   octet h1[32], pb[PREFIX_BUFSZ], rb[SHA512_DIGEST_SIZE];
 291   unsigned i;
 292
 293   /* Get my private key. */
 294   unpack_key(a, h1, k, ksz);
 295
 296   /* Determine the prefix string. */
 297   psz = prefix(pb, phflag, p, psz);
 298
 299   /* Select the nonce and the vector part. */
 300   sha512_init_ctx(&h);
 301   sha512_process_bytes(pb, psz, &h);
 302   sha512_process_bytes(h1, 32, &h);
 303   sha512_process_bytes(m, msz, &h);
 304   sha512_finish_ctx(&h, rb);
 305   scaf_loaddbl(tt, rb, 64, 2*NPIECE, PIECEWD);
 306   scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch);
 307   ptmul(&RX, &RY, &RZ, r, BX, BY, BZ);
 308   ptencode(sig, &RX, &RY, &RZ);
 309
 310   /* Calculate the scalar part. */
 311   sha512_init_ctx(&h);
 312   sha512_process_bytes(pb, psz, &h);
 313   sha512_process_bytes(sig, 32, &h);
 314   sha512_process_bytes(K, 32, &h);
 315   sha512_process_bytes(m, msz, &h);
 316   sha512_finish_ctx(&h, rb);
 317   scaf_loaddbl(tt, rb, 64, 2*NPIECE, PIECEWD);
 318   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 319   scaf_mul(tt, t, a, NPIECE);
 320   for (i = 0; i < NPIECE; i++) tt[i] += r[i];
 321   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 322   scaf_store(sig + 32, 32, t, NPIECE, PIECEWD);
 323 }
 324
 325 void ed25519_sign(octet sig[ED25519_SIGSZ],
 326                   const void *k, size_t ksz, const octet K[ED25519_PUBSZ],
 327                   const void *m, size_t msz)
 328   { ed25519ctx_sign(sig, k, ksz, K, -1, 0, 0, m, msz); }
 329
 330 /* --- @ed25519_verify@, @ed25519ctx_verify@ --- *
 331  *
 332  * Arguments:   @const octet K[ED25519_PUBSZ]@ = public key
 333  *              @int phflag@ = whether the `message' has been hashed already
 334  *              @const void *p@ = personalization string
 335  *              @size_t psz@ = length of personalization string
 336  *              @const void *m@ = message to sign
 337  *              @size_t msz@ = length of message
 338  *              @const octet sig[ED25519_SIGSZ]@ = signature
 339  *
 340  * Returns:     Zero if OK, negative on failure.
 341  *
 342  * Use:         Verify a signature.
 343  *
 344  *              In @ed25519ctx_verify@, if @phflag@ is @-1@ then you get
 345  *              plain old Ed25519: the personalization string pointer @p@
 346  *              will be ignored.  If @phflag > 0@ then the `message' @m@
 347  *              should be a SHA512 hash of the actual message.
 348  */
 349
 350 int ed25519ctx_verify(const octet K[ED25519_PUBSZ],
 351                       int phflag, const void *p, size_t psz,
 352                       const void *m, size_t msz,
 353                       const octet sig[ED25519_SIGSZ])
 354 {
 355   struct sha512_ctx h;
 356   scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE];
 357   scaf_dblpiece tt[2*NPIECE];
 358   f25519 AX, AY, AZ, RX, RY, RZ;
 359   octet b[PREFIX_BUFSZ];
 360
 361   /* Unpack the public key.  Negate it: we're meant to subtract the term
 362    * involving the public key point, and this is easier than negating the
 363    * scalar.
 364    */
 365   if (ptdecode(&AX, &AY, &AZ, K)) return (-1);
 366   f25519_neg(&AX, &AX);
 367
 368   /* Load the scalar and check that it's in range.  The easy way is to store
 369    * it again and see if the two match.
 370    */
 371   scaf_loaddbl(tt, sig + 32, 32, 2*NPIECE, PIECEWD);
 372   scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch);
 373   scaf_store(b, 32, s, NPIECE, PIECEWD);
 374   if (memcmp(b, sig + 32, 32) != 0) return (-1);
 375
 376   /* Check the signature. */
 377   psz = prefix(b, phflag, p, psz);
 378   sha512_init_ctx(&h);
 379   sha512_process_bytes(b, psz, &h);
 380   sha512_process_bytes(sig, 32, &h);
 381   sha512_process_bytes(K, 32, &h);
 382   sha512_process_bytes(m, msz, &h);
 383   sha512_finish_ctx(&h, b);
 384   scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD);
 385   scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
 386   ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ);
 387   ptencode(b, &RX, &RY, &RZ);
 388   if (memcmp(b, sig, 32) != 0) return (-1);
 389
 390   /* All is good. */
 391   return (0);
 392 }
 393
 394 int ed25519_verify(const octet K[ED25519_PUBSZ],
 395                    const void *m, size_t msz,
 396                    const octet sig[ED25519_SIGSZ])
 397   { return (ed25519ctx_verify(K, -1, 0, 0, m, msz, sig)); }
 398
 399 /*----- That's all, folks -------------------------------------------------*/