[secnet] / montladder.h

/*
 * montladder.h: Montgomery's ladder
 */
/*
 * This file is Free Software.  It has been modified to as part of its
 * incorporation into secnet.
 *
 * Copyright 2017 Mark Wooding
 *
 * You may redistribute this file and/or modify it under the terms of
 * the permissive licence shown below.
 *
 * You may redistribute secnet as a whole and/or modify it under the
 * terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 3, or (at your option) any
 * later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see
 * https://www.gnu.org/licenses/gpl.html.
 */
/*
 * Imported from Catacomb (2017-04-30).  The file's original comment headers
 * are preserved below.
 */
/* -*-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
Commit	Line	Data
0bcb8184 MW	1	/*
	2	* montladder.h: Montgomery's ladder
	3	*/
	4	/*
	5	* This file is Free Software. It has been modified to as part of its
	6	* incorporation into secnet.
	7	*
	8	* Copyright 2017 Mark Wooding
	9	*
	10	* You may redistribute this file and/or modify it under the terms of
	11	* the permissive licence shown below.
	12	*
	13	* You may redistribute secnet as a whole and/or modify it under the
	14	* terms of the GNU General Public License as published by the Free
	15	* Software Foundation; either version 3, or (at your option) any
	16	* later version.
	17	*
	18	* This program is distributed in the hope that it will be useful,
	19	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	20	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	21	* GNU General Public License for more details.
	22	*
	23	* You should have received a copy of the GNU General Public License
	24	* along with this program; if not, see
	25	* https://www.gnu.org/licenses/gpl.html.
	26	*/
	27	/*
	28	* Imported from Catacomb (2017-04-30). The file's original comment headers
	29	* are preserved below.
	30	*/
b7a5ecfc MW	31	/* --c--
	32	*
	33	* Definitions for Montgomery's ladder
	34	*
	35	* (c) 2017 Straylight/Edgeware
	36	*/
	37
	38	/----- Licensing notice --------------------------------------------------
	39	*
	40	* This file is part of Catacomb.
	41	*
	42	* Catacomb is free software; you can redistribute it and/or modify
	43	* it under the terms of the GNU Library General Public License as
	44	* published by the Free Software Foundation; either version 2 of the
	45	* License, or (at your option) any later version.
	46	*
	47	* Catacomb is distributed in the hope that it will be useful,
	48	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	49	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	50	* GNU Library General Public License for more details.
	51	*
	52	* You should have received a copy of the GNU Library General Public
	53	* License along with Catacomb; if not, write to the Free
	54	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	55	* MA 02111-1307, USA.
	56	*/
	57
	58	#ifndef CATACOMB_MONTLADDER_H
	59	#define CATACOMB_MONTLADDER_H
	60
	61	#ifdef __cplusplus
	62	extern "C" {
	63	#endif
	64
	65	/----- Notes on the Montgomery ladder ------------------------------------
	66	*
	67	* The algorithm here is Montgomery's famous binary ladder for calculating
	68	* x-coordinates of scalar products on a particular shape of elliptic curve,
	69	* as elucidated by Daniel Bernstein.
	70	*
	71	* Let Q = (x_1, y_1) be the base point, for some unknown y_1 (which will
	72	* turn out to be unimportant). Define x_n, z_n by x(n Q) = (x_n : z_n).
	73	* Given x_n, z_n, x_{n+1}, z_{n+1}, Montgomery's differential addition
	74	* formulae calculate x_{2i}, z_{2i}, x_{2i+1}, z_{2i+1}. Furthermore,
	75	* calculating x_{2i}, z_{2i} requires only x_n, z_n, and the calculation of
	76	* x_{2i+1}, z_{2i+1} is symmetrical.
	77	*/
	78
	79	/----- Functions provided ------------------------------------------------/
	80
	81	/* F designates a field, both naming the type of its elements and acting as a
	82	* prefix for the standard field operations `F_add', `F_sub', `F_mul',
	83	* `F_sqr', and `F_inv' (the last of which should return zero its own
	84	* inverse); and the constant-time utility `F_condswap'.
	85	*
	86	* The macro calculates the x-coordinate of the product k Q, where Q is a
	87	* point on the elliptic curve B y^2 = x^3 + A x^2 + x or its quadratic
	88	* twist, for some irrelevant B. The x-coordinate of Q is given as X1 (a
	89	* pointer to a field element). The scalar k is given as a vector of NK
	90	* unsigned integers KW, each containing NBITS significant bits, with the
	91	* least-significant element first. The result is written to the field
	92	* element pointed to by Z.
	93	*
	94	* The curve coefficient A is given indirectly, as the name of a macro MULA0
95	* such that
96	*
97	* MULA0(z, x)
98	*
99	* will store in z the value (A - 2)/4 x.
100	*/
101	#define MONT_LADDER(f, mula0, kw, nk, nbits, z, x1) do { \
102	f _x, _z, _u, _w; \
103	f _t0, _t1, _t2, _t3, _t4; \
104	uint32 _m = 0, _mm = 0, _k; \
105	unsigned _i, _j; \
106	\
107	/* Initialize the main variables. We'll have, (x, z) and (u, w) \
108	* holding (x_n, z_n) and (x_{n+1}, z_{n+1}) in some order, but \
109	* there's some weirdness: if m = 0 then (x, z) = (x_n, z_n) and \
110	* (u, v) = (x_{n+1}, z_{n+1}); if m /= 0, then the pairs are \
111	* swapped over. \
112	* \
113	* Initially, we have (x_0, z_0) = (1, 0), representing the identity \
114	* at projective-infinity, which works fine; and we have z_1 = 1. \
115	*/ \
116	_u = *(x1); f##_set(&_w, 1); f##_set(&_x, 1); f##_set(&_z, 0); \
117	\
118	/* The main ladder loop. Work through each bit of the clamped key. */ \
119	for (_i = (nk); _i--; ) { \
120	_k = (kw)[_i]; \
121	for (_j = 0; _j < (nbits); _j++) { \
122	/* We're at bit i of the scalar key (represented by 32 (7 - i) + \
123	* (31 - j) in our loop variables -- don't worry about that). \
124	* Let k = 2^i k_i + k'_i, with 0 <= k'_i < 2^i. In particular, \
125	* then, k_0 = k. Write Q(i) = (x_i, z_i). \
126	* \
127	* We currently have, in (x, z) and (u, w), Q(k_i) and Q(k_i + \
128	* 1), in some order. The ladder step will double the point in \
129	* (x, z), and leave the sum of (x : z) and (u : w) in (u, w). \
130	*/ \
131	\
132	_mm = -((_k >> ((nbits) - 1))&1u); _k <<= 1; \
133	f##_condswap(&_x, &_u, _m ^ _mm); \
134	f##_condswap(&_z, &_w, _m ^ _mm); \
135	_m = _mm; \
136	\
137	f##_add(&_t0, &_x, &_z); /* x + z */ \
138	f##_sub(&_t1, &_x, &_z); /* x - z */ \
139	f##_add(&_t2, &_u, &_w); /* u + w */ \
140	f##_sub(&_t3, &_u, &_w); /* u - w */ \
141	f##_mul(&_t2, &_t2, &_t1); /* (x - z) (u + w) */ \
142	f##_mul(&_t3, &_t3, &_t0); /* (x + z) (u - w) */ \
143	f##_sqr(&_t0, &_t0); /* (x + z)^2 */ \
144	f##_sqr(&_t1, &_t1); /* (x - z)^2 */ \
145	f##_mul(&_x, &_t0, &_t1); /* (x + z)^2 (x - z)^2 */ \
146	f##_sub(&_t1, &_t0, &_t1); /* (x + z)^2 - (x - z)^2 */ \
147	mula0(&_t4, &_t1); /* A_0 ((x + z)^2 - (x - z)^2) */ \
148	f##_add(&_t0, &_t0, &_t4); /* A_0 ... + (x + z)^2 */ \
149	f##_mul(&_z, &_t0, &_t1); /* (...^2 - ...^2) (A_0 ... + ...) */ \
150	f##_add(&_t0, &_t2, &_t3); /* (x - z) (u + w) + (x + z) (u - w) */ \
151	f##_sub(&_t1, &_t2, &_t3); /* (x - z) (u + w) - (x + z) (u - w) */ \
152	f##_sqr(&_u, &_t0); /* (... + ...)^2 */ \
153	f##_sqr(&_t1, &_t1); /* (... - ...)^2 */ \
154	f##_mul(&_w, &_t1, (x1)); /* x_1 (... - ...)^2 */ \
155	} \
156	} \
157	\
158	/* Almost done. Undo the swap, if any. */ \
159	f##_condswap(&_x, &_u, _m); \
160	f##_condswap(&_z, &_w, _m); \
161	\
162	/* And convert to affine. */ \
163	f##_inv(&_t0, &_z); \
164	f##_mul((z), &_x, &_t0); \
165	} while (0)
166
167	/----- That's all, folks -------------------------------------------------/
168
169	#ifdef __cplusplus
170	}
171	#endif
172
173	#endif