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

   1 /* -*-c-*-
   2  *
   3  * The X25519 key-agreement algorithm
   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 <mLib/bits.h>
  31
  32 #include "montladder.h"
  33 #include "f25519.h"
  34 #include "x25519.h"
  35
  36 /*----- Important constants -----------------------------------------------*/
  37
  38 const octet x25519_base[32] = { 9, 0, /* ... */ };
  39
  40 #define A0 121665
  41
  42 /*----- Key fetching ------------------------------------------------------*/
  43
  44 const key_fetchdef x25519_pubfetch[] = {
  45   { "pub",      offsetof(x25519_pub, pub),      KENC_BINARY,    0 },
  46   { 0,          0,                              0,              0 }
  47 };
  48
  49 static const key_fetchdef priv[] = {
  50   { "priv",     offsetof(x25519_priv, priv),    KENC_BINARY,    0 },
  51   { 0,          0,                              0,              0 }
  52 };
  53
  54 const key_fetchdef x25519_privfetch[] = {
  55   { "pub",      offsetof(x25519_priv, pub),     KENC_BINARY,    0 },
  56   { "private",  0,                              KENC_STRUCT,    priv },
  57   { 0,          0,                              0,              0 }
  58 };
  59
  60 /*----- Main code ---------------------------------------------------------*/
  61
  62 /* --- @x25519@ --- *
  63  *
  64  * Arguments:   @octet zz[X25519_OUTSZ]@ = where to put the result
  65  *              @const octet k[X25519_KEYSZ]@ = pointer to private key
  66  *              @const octet qx[X25519_PUBSZ]@ = pointer to public value
  67  *
  68  * Returns:     ---
  69  *
  70  * Use:         Calculates X25519 of @k@ and @qx@.
  71  *
  72  *              Note that there is disagreement over whether the most
  73  *              significant bit of @qx@ (i.e., the value @qx[31]&0x80@)
  74  *              should be ignored or counted towards the represented value.
  75  *              Historically implementations respected the bit; later
  76  *              convention seems to be to ignore it.  This implementation
  77  *              honours the bit: a caller who wants to ignore the bit can
  78  *              easily clear it, while caller who wants to respect it has a
  79  *              difficult job if this function ignores it.
  80  */
  81
  82 void x25519(octet zz[X25519_OUTSZ],
  83             const octet k[X25519_KEYSZ],
  84             const octet qx[X25519_PUBSZ])
  85 {
  86   uint32 kw[8];
  87   f25519 x1;
  88
  89   /* Load and clamp the key.  The low bits are cleared to kill the small
  90    * subgroups on the curve and its twist, and a high bit is set to guard
  91    * against careless implementations, though this isn't one of those.
  92    */
  93   kw[0] = LOAD32_L(k +  0); kw[1] = LOAD32_L(k +  4);
  94   kw[2] = LOAD32_L(k +  8); kw[3] = LOAD32_L(k + 12);
  95   kw[4] = LOAD32_L(k + 16); kw[5] = LOAD32_L(k + 20);
  96   kw[6] = LOAD32_L(k + 24); kw[7] = LOAD32_L(k + 28);
  97   kw[0] &= 0xfffffff8; kw[7] = (kw[7]&0x3fffffff) | 0x40000000;
  98
  99   /* And run the ladder. */
 100   f25519_load(&x1, qx);
 101 #define MULA0(z, x) do { f25519_mulconst((z), (x), A0); } while (0)
 102   MONT_LADDER(f25519, MULA0, kw, 8, 32, &x1, &x1);
 103 #undef MULA0
 104   f25519_store(zz, &x1);
 105 }
 106
 107 /*----- Test rig ----------------------------------------------------------*/
 108
 109 #ifdef TEST_RIG
 110
 111 #include <stdio.h>
 112 #include <string.h>
 113
 114 #include <mLib/macros.h>
 115 #include <mLib/report.h>
 116 #include <mLib/testrig.h>
 117
 118 #include "ct.h"
 119
 120 static int vrf_x25519(dstr dv[])
 121 {
 122   dstr dz = DSTR_INIT;
 123   int ok = 1;
 124
 125   if (dv[0].len != X25519_KEYSZ) die(1, "bad key length");
 126   if (dv[1].len != X25519_PUBSZ) die(1, "bad public length");
 127   if (dv[2].len != X25519_OUTSZ) die(1, "bad result length");
 128
 129   ct_poison(dv[0].buf, dv[0].len);
 130   dstr_ensure(&dz, X25519_OUTSZ); dz.len = X25519_OUTSZ;
 131   x25519((octet *)dz.buf,
 132          (const octet *)dv[0].buf,
 133          (const octet *)dv[1].buf);
 134   ct_remedy(dz.buf, dz.len);
 135   if (MEMCMP(dz.buf, !=, dv[2].buf, X25519_OUTSZ)) {
 136     ok = 0;
 137     fprintf(stderr, "failed!");
 138     fprintf(stderr, "\n\t   k = "); type_hex.dump(&dv[0], stderr);
 139     fprintf(stderr, "\n\t   p = "); type_hex.dump(&dv[1], stderr);
 140     fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[2], stderr);
 141     fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dz, stderr);
 142     fprintf(stderr, "\n");
 143   }
 144
 145   dstr_destroy(&dz);
 146   return (ok);
 147 }
 148
 149 static int vrf_mct(dstr dv[])
 150 {
 151   octet b0[X25519_OUTSZ], b1[X25519_OUTSZ], *k = b0, *x = b1, *t;
 152   unsigned long i, niter;
 153   dstr d = DSTR_INIT;
 154   int ok = 1;
 155
 156   if (dv[0].len != sizeof(b0)) { fprintf(stderr, "k len\n"); exit(2); }
 157   if (dv[1].len != sizeof(b1)) { fprintf(stderr, "x len\n"); exit(2); }
 158   if (dv[3].len != sizeof(b0)) { fprintf(stderr, "result len\n"); exit(2); }
 159   memcpy(b0, dv[0].buf, sizeof(b0));
 160   memcpy(b1, dv[1].buf, sizeof(b1));
 161   niter = *(unsigned long *)dv[2].buf;
 162   dstr_ensure(&d, X25519_OUTSZ); d.len = X25519_OUTSZ; t = (octet *)d.buf;
 163
 164   for (i = 0; i < niter; i++) {
 165     x[31] &= 0x7f;
 166     x25519(x, k, x);
 167     t = x; x = k; k = t;
 168   }
 169   memcpy(d.buf, k, d.len);
 170
 171   if (MEMCMP(d.buf, !=, dv[3].buf, d.len)) {
 172     ok = 0;
 173     fprintf(stderr, "failed...");
 174     fprintf(stderr, "\n\tinitial k = "); type_hex.dump(&dv[0], stderr);
 175     fprintf(stderr, "\n\tinitial x = "); type_hex.dump(&dv[1], stderr);
 176     fprintf(stderr, "\n\titerations = %lu", niter);
 177     fprintf(stderr, "\n\texpected = "); type_hex.dump(&dv[3], stderr);
 178     fprintf(stderr, "\n\tcalculated = "); type_hex.dump(&d, stderr);
 179     fputc('\n', stderr);
 180   }
 181
 182   dstr_destroy(&d);
 183   return (ok);
 184 }
 185
 186 static test_chunk tests[] = {
 187   { "x25519", vrf_x25519, { &type_hex, &type_hex, &type_hex } },
 188   { "x25519-mct", vrf_mct,
 189     { &type_hex, &type_hex, &type_ulong, &type_hex } },
 190   { 0, 0, { 0 } }
 191 };
 192
 193 int main(int argc, char *argv[])
 194 {
 195   test_run(argc, argv, tests, SRCDIR "/t/x25519");
 196   return (0);
 197 }
 198
 199 #endif
 200
 201 /*----- That's all, folks -------------------------------------------------*/