[catacomb] / pub / x25519.c

/* -*-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/macros.h>
#include <mLib/report.h>
#include <mLib/testrig.h>

#include "ct.h"

static int vrf_x25519(dstr dv[])
{
  dstr dz = DSTR_INIT;
  int ok = 1;

  if (dv[0].len != X25519_KEYSZ) die(1, "bad key length");
  if (dv[1].len != X25519_PUBSZ) die(1, "bad public length");
  if (dv[2].len != X25519_OUTSZ) die(1, "bad result length");

  ct_poison(dv[0].buf, dv[0].len);
  dstr_ensure(&dz, X25519_OUTSZ); dz.len = X25519_OUTSZ;
  x25519((octet *)dz.buf,
	 (const octet *)dv[0].buf,
	 (const octet *)dv[1].buf);
  ct_remedy(dz.buf, dz.len);
  if (MEMCMP(dz.buf, !=, dv[2].buf, X25519_OUTSZ)) {
    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[X25519_OUTSZ], b1[X25519_OUTSZ], *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, X25519_OUTSZ); d.len = X25519_OUTSZ; 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)) {
    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 -------------------------------------------------*/
Commit	Line	Data
fc2d44af MW	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
141c1284	114	#include <mLib/macros.h>
fc2d44af MW	115	#include <mLib/report.h>
	116	#include <mLib/testrig.h>
	117
1aaccf40 MW	118	#include "ct.h"
1aaccf40 MW	119
fc2d44af MW	120	static int vrf_x25519(dstr dv[])
	121	{
	122	dstr dz = DSTR_INIT;
	123	int ok = 1;
	124
1b59808c MW	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");
fc2d44af	128
1aaccf40	129	ct_poison(dv[0].buf, dv[0].len);
1b59808c	130	dstr_ensure(&dz, X25519_OUTSZ); dz.len = X25519_OUTSZ;
fc2d44af MW	131	x25519((octet *)dz.buf,
	132	(const octet *)dv[0].buf,
	133	(const octet *)dv[1].buf);
1aaccf40	134	ct_remedy(dz.buf, dz.len);
141c1284	135	if (MEMCMP(dz.buf, !=, dv[2].buf, X25519_OUTSZ)) {
fc2d44af MW	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	{
1b59808c	151	octet b0[X25519_OUTSZ], b1[X25519_OUTSZ], k = b0, x = b1, *t;
fc2d44af MW	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;
1b59808c	162	dstr_ensure(&d, X25519_OUTSZ); d.len = X25519_OUTSZ; t = (octet *)d.buf;
fc2d44af MW	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
141c1284	171	if (MEMCMP(d.buf, !=, dv[3].buf, d.len)) {
fc2d44af MW	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 -------------------------------------------------/