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 --------------------------------------------------
--- /dev/null
+/* -*-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
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
#include "ec-keys.h"
#include "dh.h"
#include "rsa.h"
+#include "x25519.h"
#include "rmd160.h"
#include "blowfish-cbc.h"
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 {
{ "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 }
};
\(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,
#include "pgen.h"
#include "ptab.h"
#include "rsa.h"
+#include "x25519.h"
#include "cc.h"
#include "sha-mgf.h"
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 {
{ "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 }
};
#include "pgen.h"
#include "ec.h"
#include "group.h"
+#include "x25519.h"
#include "cc.h"
#include "gcipher.h"
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 {
{ "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 },
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 --------------------------------------------------
--- /dev/null
+### 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;
+}
--- /dev/null
+/* -*-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 <mLib/bits.h>
+
+#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 <stdio.h>
+#include <string.h>
+
+#include <mLib/report.h>
+#include <mLib/testrig.h>
+
+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 -------------------------------------------------*/
--- /dev/null
+/* -*-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 <mLib/bits.h>
+
+#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
### -*- 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.
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 --------------------------------------------------
~mdw / catacomb / commitdiff