From fc2d44af772db6c046820007555609c8352e101e Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Tue, 18 Apr 2017 00:39:24 +0100 Subject: [PATCH] pub/, progs/: Implement Bernstein's X25519 key-exchange algorithm. --- math/Makefile.am | 2 + math/montladder.h | 143 ++++++++++++++++++++++++++++++++++++ progs/catcrypt.1 | 12 ++++ progs/cc-kem.c | 67 +++++++++++++++++ progs/key.1 | 8 +++ progs/key.c | 20 ++++++ progs/perftest.c | 20 ++++++ pub/Makefile.am | 6 ++ pub/t/x25519 | 51 +++++++++++++ pub/x25519.c | 196 ++++++++++++++++++++++++++++++++++++++++++++++++++ pub/x25519.h | 103 ++++++++++++++++++++++++++ utils/curve25519.sage | 80 ++++++++++++++++++++- 12 files changed, 707 insertions(+), 1 deletion(-) create mode 100644 math/montladder.h create mode 100644 pub/t/x25519 create mode 100644 pub/x25519.c create mode 100644 pub/x25519.h diff --git a/math/Makefile.am b/math/Makefile.am index 2a60ee0f..73b9d142 100644 --- a/math/Makefile.am +++ b/math/Makefile.am @@ -431,4 +431,6 @@ f25519_p10_t_CPPFLAGS += -DF25519_IMPL=10 f25519_p10_t_LDADD = $(TEST_LIBS) $(top_builddir)/libcatacomb.la f25519_p10_t_LDADD += $(mLib_LIBS) $(CATACOMB_LIBS) $(LIBS) +pkginclude_HEADERS += montladder.h + ###----- That's all, folks -------------------------------------------------- diff --git a/math/montladder.h b/math/montladder.h new file mode 100644 index 00000000..02d29618 --- /dev/null +++ b/math/montladder.h @@ -0,0 +1,143 @@ +/* -*-c-*- + * + * Definitions for Montgomery's ladder + * + * (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. + */ + +#ifndef CATACOMB_MONTLADDER_H +#define CATACOMB_MONTLADDER_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Notes on the Montgomery ladder ------------------------------------* + * + * The algorithm here is Montgomery's famous binary ladder for calculating + * x-coordinates of scalar products on a particular shape of elliptic curve, + * as elucidated by Daniel Bernstein. + * + * Let Q = (x_1, y_1) be the base point, for some unknown y_1 (which will + * turn out to be unimportant). Define x_n, z_n by x(n Q) = (x_n : z_n). + * Given x_n, z_n, x_{n+1}, z_{n+1}, Montgomery's differential addition + * formulae calculate x_{2i}, z_{2i}, x_{2i+1}, z_{2i+1}. Furthermore, + * calculating x_{2i}, z_{2i} requires only x_n, z_n, and the calculation of + * x_{2i+1}, z_{2i+1} is symmetrical. + */ + +/*----- Functions provided ------------------------------------------------*/ + +/* F designates a field, both naming the type of its elements and acting as a + * prefix for the standard field operations `F_add', `F_sub', `F_mul', + * `F_sqr', and `F_inv' (the last of which should return zero its own + * inverse); and the constant-time utility `F_condswap'. + * + * The macro calculates the x-coordinate of the product k Q, where Q is a + * point on the elliptic curve B y^2 = x^3 + A x^2 + x or its quadratic + * twist, for some irrelevant B. The x-coordinate of Q is given as X1 (a + * pointer to a field element). The scalar k is given as a vector of NK + * unsigned integers KW, each containing NBITS significant bits, with the + * least-significant element first. The result is written to the field + * element pointed to by Z. + * + * The curve coefficient A is given indirectly, as the name of a macro MULA0 + * such that + * + * MULA0(z, x) + * + * will store in z the value (A - 2)/4 x. + */ +#define MONT_LADDER(f, mula0, kw, nk, nbits, z, x1) do { \ + f _x, _z, _u, _w; \ + f _t0, _t1, _t2, _t3, _t4; \ + uint32 _m = 0, _mm = 0, _k; \ + unsigned _i, _j; \ + \ + /* Initialize the main variables. We'll have, (x, z) and (u, w) \ + * holding (x_n, z_n) and (x_{n+1}, z_{n+1}) in some order, but \ + * there's some weirdness: if m = 0 then (x, z) = (x_n, z_n) and \ + * (u, v) = (x_{n+1}, z_{n+1}); if m /= 0, then the pairs are \ + * swapped over. \ + * \ + * Initially, we have (x_0, z_0) = (1, 0), representing the identity \ + * at projective-infinity, which works fine; and we have z_1 = 1. \ + */ \ + _u = *(x1); f##_set(&_w, 1); f##_set(&_x, 1); f##_set(&_z, 0); \ + \ + /* The main ladder loop. Work through each bit of the clamped key. */ \ + for (_i = (nk); _i--; ) { \ + _k = (kw)[_i]; \ + for (_j = 0; _j < (nbits); _j++) { \ + /* We're at bit i of the scalar key (represented by 32 (7 - i) + \ + * (31 - j) in our loop variables -- don't worry about that). \ + * Let k = 2^i k_i + k'_i, with 0 <= k'_i < 2^i. In particular, \ + * then, k_0 = k. Write Q(i) = (x_i, z_i). \ + * \ + * We currently have, in (x, z) and (u, w), Q(k_i) and Q(k_i + \ + * 1), in some order. The ladder step will double the point in \ + * (x, z), and leave the sum of (x : z) and (u : w) in (u, w). \ + */ \ + \ + _mm = -((_k >> ((nbits) - 1))&1u); _k <<= 1; \ + f##_condswap(&_x, &_u, _m ^ _mm); \ + f##_condswap(&_z, &_w, _m ^ _mm); \ + _m = _mm; \ + \ + f##_add(&_t0, &_x, &_z); /* x + z */ \ + f##_sub(&_t1, &_x, &_z); /* x - z */ \ + f##_add(&_t2, &_u, &_w); /* u + w */ \ + f##_sub(&_t3, &_u, &_w); /* u - w */ \ + f##_mul(&_t2, &_t2, &_t1); /* (x - z) (u + w) */ \ + f##_mul(&_t3, &_t3, &_t0); /* (x + z) (u - w) */ \ + f##_sqr(&_t0, &_t0); /* (x + z)^2 */ \ + f##_sqr(&_t1, &_t1); /* (x - z)^2 */ \ + f##_mul(&_x, &_t0, &_t1); /* (x + z)^2 (x - z)^2 */ \ + f##_sub(&_t1, &_t0, &_t1); /* (x + z)^2 - (x - z)^2 */ \ + mula0(&_t4, &_t1); /* A_0 ((x + z)^2 - (x - z)^2) */ \ + f##_add(&_t0, &_t0, &_t4); /* A_0 ... + (x + z)^2 */ \ + f##_mul(&_z, &_t0, &_t1); /* (...^2 - ...^2) (A_0 ... + ...) */ \ + f##_add(&_t0, &_t2, &_t3); /* (x - z) (u + w) + (x + z) (u - w) */ \ + f##_sub(&_t1, &_t2, &_t3); /* (x - z) (u + w) - (x + z) (u - w) */ \ + f##_sqr(&_u, &_t0); /* (... + ...)^2 */ \ + f##_sqr(&_t1, &_t1); /* (... - ...)^2 */ \ + f##_mul(&_w, &_t1, (x1)); /* x_1 (... - ...)^2 */ \ + } \ + } \ + \ + /* Almost done. Undo the swap, if any. */ \ + f##_condswap(&_x, &_u, _m); \ + f##_condswap(&_z, &_w, _m); \ + \ + /* And convert to affine. */ \ + f##_inv(&_t0, &_z); \ + f##_mul((z), &_x, &_t0); \ +} while (0) + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/progs/catcrypt.1 b/progs/catcrypt.1 index a3ebff8a..a505376a 100644 --- a/progs/catcrypt.1 +++ b/progs/catcrypt.1 @@ -204,6 +204,18 @@ algorithm of the command (see .BR key (1)) to generate the key. +.TP +.B x25519 +This is Bernstein's Curve25519, a fast Diffie-Hellman using a specific +elliptic curve. +Use the +.B x25519 +algorithm of the +.B key add +command +(see +.BR key (1)) +to generate the key. .PP The bulk crypto transform is chosen based on the .B bulk diff --git a/progs/cc-kem.c b/progs/cc-kem.c index 4a2cf192..71c89e47 100644 --- a/progs/cc-kem.c +++ b/progs/cc-kem.c @@ -43,6 +43,7 @@ #include "ec-keys.h" #include "dh.h" #include "rsa.h" +#include "x25519.h" #include "rmd160.h" #include "blowfish-cbc.h" @@ -602,6 +603,71 @@ static const kemops ec_decops = { ec_decinit, dh_decdoit, dh_enccheck, dh_encdestroy }; +/* --- X25519 --- */ + +static kem *x25519_encinit(key *k, void *kd) { return (CREATE(kem)); } +static void x25519_encdestroy(kem *k) { DESTROY(k); } + +static const char *x25519_enccheck(kem *k) +{ + x25519_pub *kd = k->kd; + + if (kd->pub.sz != X25519_PUBSZ) + return ("incorrect X25519 public key length"); + return (0); +} + +static int x25519_encdoit(kem *k, dstr *d, ghash *h) +{ + octet t[X25519_KEYSZ], z[X25519_OUTSZ]; + x25519_pub *kd = k->kd; + + rand_get(RAND_GLOBAL, t, sizeof(t)); + dstr_ensure(d, X25519_PUBSZ); + x25519((octet *)d->buf, t, x25519_base); + x25519(z, t, kd->pub.k); + d->len += X25519_PUBSZ; + GH_HASH(h, d->buf, X25519_PUBSZ); + GH_HASH(h, z, X25519_OUTSZ); + return (0); +} + +static const char *x25519_deccheck(kem *k) +{ + x25519_priv *kd = k->kd; + + if (kd->priv.sz != X25519_KEYSZ) + return ("incorrect X25519 private key length"); + if (kd->pub.sz != X25519_PUBSZ) + return ("incorrect X25519 public key length"); + return (0); +} + +static int x25519_decdoit(kem *k, dstr *d, ghash *h) +{ + octet z[X25519_OUTSZ]; + x25519_priv *kd = k->kd; + int rc = -1; + + if (d->len != X25519_PUBSZ) goto done; + x25519(z, kd->priv.k, (const octet *)d->buf); + GH_HASH(h, d->buf, X25519_PUBSZ); + GH_HASH(h, z, X25519_OUTSZ); + rc = 0; +done: + return (rc); +} + +static const kemops x25519_encops = { + x25519_pubfetch, sizeof(x25519_pub), + x25519_encinit, x25519_encdoit, x25519_enccheck, x25519_encdestroy +}; + +static const kemops x25519_decops = { + x25519_privfetch, sizeof(x25519_priv), + x25519_encinit, x25519_decdoit, x25519_deccheck, x25519_encdestroy +}; + /* --- Symmetric --- */ typedef struct symm_ctx { @@ -670,6 +736,7 @@ const struct kemtab kemtab[] = { { "dh", &dh_encops, &dh_decops }, { "bindh", &bindh_encops, &bindh_decops }, { "ec", &ec_encops, &ec_decops }, + { "x25519", &x25519_encops, &x25519_decops }, { "symm", &symm_encops, &symm_decops }, { 0, 0, 0 } }; diff --git a/progs/key.1 b/progs/key.1 index abd399d9..8a43f82f 100644 --- a/progs/key.1 +++ b/progs/key.1 @@ -846,6 +846,14 @@ the public point is then \(mu .IR G . .TP +.B x25519 +Generate a private scalar and a corresponding public point on the +(Montgomery-form) Curve25519 elliptic curve. +The scalar is simply a random 256-bit string; +the public key is the +.IR x -coordinate +of the corresponding point. +.TP .B empty Generate an empty key, with trivial contents. This is useful as a `parameters' key, diff --git a/progs/key.c b/progs/key.c index 29cc1b7a..79c78ae7 100644 --- a/progs/key.c +++ b/progs/key.c @@ -69,6 +69,7 @@ #include "pgen.h" #include "ptab.h" #include "rsa.h" +#include "x25519.h" #include "cc.h" #include "sha-mgf.h" @@ -936,6 +937,24 @@ static void alg_ec(keyopts *k) mp_drop(x); } +static void alg_x25519(keyopts *k) +{ + key_data *kd, *kkd; + octet priv[X25519_KEYSZ], pub[X25519_PUBSZ]; + + copyparam(k, 0); + k->r->ops->fill(k->r, priv, sizeof(priv)); + x25519(pub, priv, x25519_base); + kkd = key_newstruct(); + key_structsteal(kkd, "priv", + key_newbinary(KCAT_PRIV | KF_BURN, priv, sizeof(priv))); + kd = key_newstruct(); + key_structsteal(kd, "private", kkd); + key_structsteal(kd, "pub", key_newbinary(KCAT_PUB, pub, sizeof(pub))); + + key_setkeydata(k->kf, k->k, kd); +} + /* --- The algorithm tables --- */ typedef struct keyalg { @@ -957,6 +976,7 @@ static keyalg algtab[] = { { "bindh-param", alg_binparam, "Binary-field DH parameters" }, { "ec-param", alg_ecparam, "Elliptic curve parameters" }, { "ec", alg_ec, "Elliptic curve crypto" }, + { "x25519", alg_x25519, "X25519 key exchange" }, { "empty", alg_empty, "Empty parametrs-only key" }, { 0, 0 } }; diff --git a/progs/perftest.c b/progs/perftest.c index e6f7ddf0..ebed0173 100644 --- a/progs/perftest.c +++ b/progs/perftest.c @@ -62,6 +62,7 @@ #include "pgen.h" #include "ec.h" #include "group.h" +#include "x25519.h" #include "cc.h" #include "gcipher.h" @@ -269,6 +270,24 @@ static void grsim_run(void *cc) G_DESTROY(c->g, x); } +/* --- x25519 --- */ + +typedef struct x25519_jobctx { + octet k[X25519_KEYSZ]; + octet p[X25519_PUBSZ]; +} x25519_jobctx; + +static void *x25519_jobinit(opts *o) +{ + x25519_jobctx *c = CREATE(x25519_jobctx); + rand_get(RAND_GLOBAL, c->k, sizeof(c->k)); + rand_get(RAND_GLOBAL, c->p, sizeof(c->p)); + return (c); +} + +static void x25519_jobrun(void *cc) + { x25519_jobctx *c = cc; octet z[X25519_OUTSZ]; x25519(z, c->k, c->p); } + /* --- RSA --- */ typedef struct rsapriv_ctx { @@ -485,6 +504,7 @@ static const jobops jobtab[] = { { "rsa-priv", rsapriv_init, rsapriv_run }, { "rsa-priv-blind", rsaprivblind_init, rsapriv_run }, { "rsa-pub", rsapub_init, rsapub_run }, + { "x25519", x25519_jobinit, x25519_jobrun }, { "ksched", ksched_init, ksched_run }, { "enc", enc_init, enc_run }, { "hash", hash_init, hash_run }, diff --git a/pub/Makefile.am b/pub/Makefile.am index b21d6afc..e1b99788 100644 --- a/pub/Makefile.am +++ b/pub/Makefile.am @@ -98,4 +98,10 @@ EXTRA_DIST += rsa-test.c TESTS += rsa-test.t$(EXEEXT) EXTRA_DIST += t/rsa +## Bernstein's X25519 key-agreement algorithm. +pkginclude_HEADERS += x25519.h +libpub_la_SOURCES += x25519.c +TESTS += x25519.t$(EXEEXT) +EXTRA_DIST += t/x25519 + ###----- That's all, folks -------------------------------------------------- diff --git a/pub/t/x25519 b/pub/t/x25519 new file mode 100644 index 00000000..b80521d1 --- /dev/null +++ b/pub/t/x25519 @@ -0,0 +1,51 @@ +### Tests for X25519. + +x25519 { + ## These are from Daniel J. Bernstein, `Cryptography in NaCl', 2009-03-10, + ## https://cr.yp.to/highspeed/naclcrypto-20090310.pdf + + ## Make Alice's public key. + 77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a + 0900000000000000000000000000000000000000000000000000000000000000 + 8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a; + + ## Make Bob's public key. + 5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb + 0900000000000000000000000000000000000000000000000000000000000000 + de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f; + + ## Make the shared secret using Alice's private key. + 77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a + de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f + 4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742; + + ## Make the (same) shared secret using Bob's private key. + 5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb + 8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a + 4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742; + + ## These tests are from RFC7748. I've clamped the public values because + ## RFC7748 wants the top bits ignored. + a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4 + e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c + c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552; + 4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d + e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a413 + 95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957; +} + +x25519-mct { + ## These tests are from RFC7748. + + 0900000000000000000000000000000000000000000000000000000000000000 + 0900000000000000000000000000000000000000000000000000000000000000 + 1 422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079; + 0900000000000000000000000000000000000000000000000000000000000000 + 0900000000000000000000000000000000000000000000000000000000000000 + 1000 684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51; + + ## This one takes aaaaages. + ##0900000000000000000000000000000000000000000000000000000000000000 + ## 0900000000000000000000000000000000000000000000000000000000000000 + ## 1000000 7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424; +} diff --git a/pub/x25519.c b/pub/x25519.c new file mode 100644 index 00000000..8e9649ec --- /dev/null +++ b/pub/x25519.c @@ -0,0 +1,196 @@ +/* -*-c-*- + * + * The X25519 key-agreement algorithm + * + * (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 + +#include "montladder.h" +#include "f25519.h" +#include "x25519.h" + +/*----- Important constants -----------------------------------------------*/ + +const octet x25519_base[32] = { 9, 0, /* ... */ }; + +#define A0 121665 + +/*----- Key fetching ------------------------------------------------------*/ + +const key_fetchdef x25519_pubfetch[] = { + { "pub", offsetof(x25519_pub, pub), KENC_BINARY, 0 }, + { 0, 0, 0, 0 } +}; + +static const key_fetchdef priv[] = { + { "priv", offsetof(x25519_priv, priv), KENC_BINARY, 0 }, + { 0, 0, 0, 0 } +}; + +const key_fetchdef x25519_privfetch[] = { + { "pub", offsetof(x25519_priv, pub), KENC_BINARY, 0 }, + { "private", 0, KENC_STRUCT, priv }, + { 0, 0, 0, 0 } +}; + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @x25519@ --- * + * + * Arguments: @octet zz[X25519_OUTSZ]@ = where to put the result + * @const octet k[X25519_KEYSZ]@ = pointer to private key + * @const octet qx[X25519_PUBSZ]@ = pointer to public value + * + * Returns: --- + * + * Use: Calculates X25519 of @k@ and @qx@. + * + * Note that there is disagreement over whether the most + * significant bit of @qx@ (i.e., the value @qx[31]&0x80@) + * should be ignored or counted towards the represented value. + * Historically implementations respected the bit; later + * convention seems to be to ignore it. This implementation + * honours the bit: a caller who wants to ignore the bit can + * easily clear it, while caller who wants to respect it has a + * difficult job if this function ignores it. + */ + +void x25519(octet zz[X25519_OUTSZ], + const octet k[X25519_KEYSZ], + const octet qx[X25519_PUBSZ]) +{ + uint32 kw[8]; + f25519 x1; + + /* Load and clamp the key. The low bits are cleared to kill the small + * subgroups on the curve and its twist, and a high bit is set to guard + * against careless implementations, though this isn't one of those. + */ + kw[0] = LOAD32_L(k + 0); kw[1] = LOAD32_L(k + 4); + kw[2] = LOAD32_L(k + 8); kw[3] = LOAD32_L(k + 12); + kw[4] = LOAD32_L(k + 16); kw[5] = LOAD32_L(k + 20); + kw[6] = LOAD32_L(k + 24); kw[7] = LOAD32_L(k + 28); + kw[0] &= 0xfffffff8; kw[7] = (kw[7]&0x3fffffff) | 0x40000000; + + /* And run the ladder. */ + f25519_load(&x1, qx); +#define MULA0(z, x) do { f25519_mulconst((z), (x), A0); } while (0) + MONT_LADDER(f25519, MULA0, kw, 8, 32, &x1, &x1); +#undef MULA0 + f25519_store(zz, &x1); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +#include +#include + +#include +#include + +static int vrf_x25519(dstr dv[]) +{ + dstr dz = DSTR_INIT; + int ok = 1; + + if (dv[0].len != 32) die(1, "bad key length"); + if (dv[1].len != 32) die(1, "bad public length"); + if (dv[2].len != 32) die(1, "bad result length"); + + dstr_ensure(&dz, 32); dz.len = 32; + x25519((octet *)dz.buf, + (const octet *)dv[0].buf, + (const octet *)dv[1].buf); + if (memcmp(dz.buf, dv[2].buf, 32) != 0) { + ok = 0; + fprintf(stderr, "failed!"); + fprintf(stderr, "\n\t k = "); type_hex.dump(&dv[0], stderr); + fprintf(stderr, "\n\t p = "); type_hex.dump(&dv[1], stderr); + fprintf(stderr, "\n\twant = "); type_hex.dump(&dv[2], stderr); + fprintf(stderr, "\n\tcalc = "); type_hex.dump(&dz, stderr); + fprintf(stderr, "\n"); + } + + dstr_destroy(&dz); + return (ok); +} + +static int vrf_mct(dstr dv[]) +{ + octet b0[32], b1[32], *k = b0, *x = b1, *t; + unsigned long i, niter; + dstr d = DSTR_INIT; + int ok = 1; + + if (dv[0].len != sizeof(b0)) { fprintf(stderr, "k len\n"); exit(2); } + if (dv[1].len != sizeof(b1)) { fprintf(stderr, "x len\n"); exit(2); } + if (dv[3].len != sizeof(b0)) { fprintf(stderr, "result len\n"); exit(2); } + memcpy(b0, dv[0].buf, sizeof(b0)); + memcpy(b1, dv[1].buf, sizeof(b1)); + niter = *(unsigned long *)dv[2].buf; + dstr_ensure(&d, 32); d.len = 32; t = (octet *)d.buf; + + for (i = 0; i < niter; i++) { + x[31] &= 0x7f; + x25519(x, k, x); + t = x; x = k; k = t; + } + memcpy(d.buf, k, d.len); + + if (memcmp(d.buf, dv[3].buf, d.len) != 0) { + ok = 0; + fprintf(stderr, "failed..."); + fprintf(stderr, "\n\tinitial k = "); type_hex.dump(&dv[0], stderr); + fprintf(stderr, "\n\tinitial x = "); type_hex.dump(&dv[1], stderr); + fprintf(stderr, "\n\titerations = %lu", niter); + fprintf(stderr, "\n\texpected = "); type_hex.dump(&dv[3], stderr); + fprintf(stderr, "\n\tcalculated = "); type_hex.dump(&d, stderr); + fputc('\n', stderr); + } + + dstr_destroy(&d); + return (ok); +} + +static test_chunk tests[] = { + { "x25519", vrf_x25519, { &type_hex, &type_hex, &type_hex } }, + { "x25519-mct", vrf_mct, + { &type_hex, &type_hex, &type_ulong, &type_hex } }, + { 0, 0, { 0 } } +}; + +int main(int argc, char *argv[]) +{ + test_run(argc, argv, tests, SRCDIR "/t/x25519"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/pub/x25519.h b/pub/x25519.h new file mode 100644 index 00000000..56008df3 --- /dev/null +++ b/pub/x25519.h @@ -0,0 +1,103 @@ +/* -*-c-*- + * + * The X25519 key-agreement algorithm + * + * (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. + */ + +#ifndef CATACOMB_X25519_H +#define CATACOMB_X25519_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Notes on the X25519 key-agreement algorithm -----------------------* + * + * This is X25519, as described in Daniel J. Bernstein, `Curve25519: new + * Diffie--Hellman speed records', PKC 2006, + * https://cr.yp.to/ecdh/curve25519-20060209.pdf + * + * Since then, the name `Curve25519' has shifted somewhat, to refer to the + * specific elliptic curve used, and the x-coordinate Diffie--Hellman + * operation is now named `X25519'. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include + +#ifndef CATACOMB_KEY_H +# include "key.h" +#endif + +/*----- Important constants -----------------------------------------------*/ + +#define X25519_KEYSZ 32u +#define X25519_PUBSZ 32u +#define X25519_OUTSZ 32u + +extern const octet x25519_base[32]; + +/*----- Key fetching ------------------------------------------------------*/ + +typedef struct x25519_priv { key_bin priv, pub; } x25519_priv; +typedef struct x25519_pub { key_bin pub; } x25519_pub; + +extern const key_fetchdef x25519_pubfetch[], x25519_privfetch[]; +#define X25519_PUBFETCHSZ 3 +#define X25519_PRIVFETCHSZ 6 + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @x25519@ --- * + * + * Arguments: @octet zz[X25519_OUTSZ]@ = where to put the result + * @const octet k[X25519_KEYSZ]@ = pointer to private key + * @const octet qx[X25519_PUBSZ]@ = pointer to public value + * + * Returns: --- + * + * Use: Calculates X25519 of @k@ and @qx@. + * + * Note that there is disagreement over whether the most + * significant bit of @qx@ (i.e., the value @qx[31]&0x80@) + * should be ignored or counted towards the represented value. + * Historically implementations respected the bit; later + * convention seems to be to ignore it. This implementation + * honours the bit: a caller who wants to ignore the bit can + * easily clear it, while caller who wants to respect it has a + * difficult job if this function ignores it. + */ + +extern void x25519(octet /*zz*/[X25519_OUTSZ], + const octet /*k*/[X25519_KEYSZ], + const octet /*qx*/[X25519_PUBSZ]); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/utils/curve25519.sage b/utils/curve25519.sage index 32ddb17c..ec21d4b2 100644 --- a/utils/curve25519.sage +++ b/utils/curve25519.sage @@ -2,9 +2,41 @@ ### -*- mode: python; coding: utf-8 -*- ###-------------------------------------------------------------------------- -### Define the field. +### Some general utilities. + +def ld(v): + return 0 + sum(ord(v[i]) << 8*i for i in xrange(len(v))) + +def st(x, n): + return ''.join(chr((x >> 8*i)&0xff) for i in xrange(n)) + +###-------------------------------------------------------------------------- +### Define the curve. p = 2^255 - 19; k = GF(p) +A = k(486662); A0 = (A - 2)/4 +E = EllipticCurve(k, [0, A, 0, 1, 0]); P = E.lift_x(9) +l = 2^252 + 27742317777372353535851937790883648493 + +assert is_prime(l) +assert (l*P).is_zero() +assert (p + 1 - 8*l)^2 <= 4*p + +###-------------------------------------------------------------------------- +### Example points from `Cryptography in NaCl'. + +x = ld(map(chr, [0x70,0x07,0x6d,0x0a,0x73,0x18,0xa5,0x7d +,0x3c,0x16,0xc1,0x72,0x51,0xb2,0x66,0x45 +,0xdf,0x4c,0x2f,0x87,0xeb,0xc0,0x99,0x2a +,0xb1,0x77,0xfb,0xa5,0x1d,0xb9,0x2c,0x6a])) +y = ld(map(chr, [0x58,0xab,0x08,0x7e,0x62,0x4a,0x8a,0x4b +,0x79,0xe1,0x7f,0x8b,0x83,0x80,0x0e,0xe6 +,0x6f,0x3b,0xb1,0x29,0x26,0x18,0xb6,0xfd +,0x1c,0x2f,0x8b,0x27,0xff,0x88,0xe0,0x6b])) +X = x*P +Y = y*P +Z = x*Y +assert Z == y*X ###-------------------------------------------------------------------------- ### Arithmetic implementation. @@ -40,4 +72,50 @@ def inv(x): assert inv(k(9))*9 == 1 +###-------------------------------------------------------------------------- +### The Montgomery ladder. + +A0 = (A - 2)/4 + +def x25519(n, x1): + + ## Let Q = (x_1 : y_1 : 1) be an input point. We calculate + ## n Q = (x_n : y_n : z_n), returning x_n/z_n (unless z_n = 0, + ## in which case we return zero). + ## + ## We're given that n = 2^254 + n'_254, where 0 <= n'_254 < 2^254. + bb = n.bits() + x, z = 1, 0 + u, w = x1, 1 + + ## Initially, let i = 255. + for i in xrange(len(bb) - 1, -1, -1): + + ## Split n = n_i 2^i + n'_i, where 0 <= n'_i < 2^i, so n_0 = n. + ## We have x, z = x_{n_{i+1}}, z_{n_{i+1}}, and + ## u, w = x_{n_{i+1}+1}, z_{n_{i+1}+1}. + ## Now either n_i = 2 n_{i+1} or n_i = 2 n_{i+1} + 1, depending + ## on bit i of n. + + ## Swap (x : z) and (u : w) if bit i of n is set. + if bb[i]: x, z, u, w = u, w, x, z + + ## Do the ladder step. + xmz, xpz = x - z, x + z + umw, upw = u - w, u + w + xmz2, xpz2 = xmz^2, xpz^2 + xpz2mxmz2 = xpz2 - xmz2 + xmzupw, xpzumw = xmz*upw, xpz*umw + x, z = xmz2*xpz2, xpz2mxmz2*(xpz2 + A0*xpz2mxmz2) + u, w = (xmzupw + xpzumw)^2, x1*(xmzupw - xpzumw)^2 + + ## Finally, unswap. + if bb[i]: x, z, u, w = u, w, x, z + + ## Almost done. + return x*inv(z) + +assert x25519(y, k(9)) == Y[0] +assert x25519(x, Y[0]) == x25519(y, X[0]) == Z[0] + ###----- That's all, folks -------------------------------------------------- -- 2.11.0