[secnet] / scmul.h

/* -*-c-*-
 *
 * Scalar multiplication on elliptic curves
 *
 * (c) 2017 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of secnet.
 * See README for full list of copyright holders.
 *
 * secnet is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version d of the License, or
 * (at your option) any later version.
 *
 * secnet 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
 * version 3 along with secnet; if not, see
 * https://www.gnu.org/licenses/gpl.html.
 *
 * This file was originally part of Catacomb, but has been automatically
 * modified for incorporation into secnet: see `import-catacomb-crypto'
 * for details.
 *
 * 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_SCMUL_H
#define CATACOMB_SCMUL_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Macros provided ---------------------------------------------------*/

#define SCMUL_WINLIM(winwd) (1 << (winwd))
#define SCMUL_WINMASK(winwd) (SCMUL_WINLIM(winwd) - 1)
#define SCMUL_TABSZ(winwd) (SCMUL_WINLIM(winwd)/2 + 1)

#define DEFINE_SCMUL(mulfn, f, winwd, scafwd, npiece, addfn, dblfn)	\
void mulfn(f *X, f *Y, f *Z, const scaf_piece n[npiece],		\
	   const f *X0, const f *Y0, const f *Z0)			\
{									\
  f VX[SCMUL_TABSZ(winwd)],						\
    VY[SCMUL_TABSZ(winwd)],						\
    VZ[SCMUL_TABSZ(winwd)];						\
  f TX, TY, TZ, UX, UY, UZ;						\
  unsigned i, j, k, w;							\
  uint32 m_neg;								\
  scaf_piece ni;							\
									\
  /* Build a table of small multiples. */				\
  f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1);		\
  VX[1] = *X0; VY[1] = *Y0; VZ[1] = *Z0;				\
  ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]);		\
  for (i = 3; i < SCMUL_TABSZ(winwd); i += 2) {				\
    addfn(&VX[i], &VY[i], &VZ[i],					\
	  &VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0);		\
    dblfn(&VX[i + 1], &VY[i + 1], &VZ[i + 1],				\
	  &VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]);		\
  }									\
									\
  /* Now do the multiplication.  We lag a window behind the cursor	\
   * position because of the scalar recoding we do.			\
   */									\
  f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1);			\
  for (i = (npiece), w = 0, m_neg = 0; i--; ) {				\
    ni = n[i];								\
									\
    /* Work through each window in the scalar piece. */			\
    for (j = 0; j < (scafwd); j += (winwd)) {				\
									\
      /* Shift along by a window. */					\
      for (k = 0; k < (winwd); k++)					\
	dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ);				\
									\
      /* Peek at the next window of four bits.  If the top bit is set	\
       * we lend a bit leftwards, into w.  It's too late for this to	\
       * affect the sign now, but if we negated earlier then the	\
       * addition would be wrong.					\
       */								\
      w += (ni >> ((scafwd) - 1))&0x1u;					\
      w = ((SCMUL_WINLIM(winwd) - w)&m_neg) | (w&~m_neg);		\
									\
      /* Collect the entry from the table, and add or subtract. */	\
      f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w);			\
      f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w);			\
      f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w);			\
      f##_condneg(&UX, &UX, m_neg);					\
      addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ);		\
									\
      /* Move the next window into the delay slot.  If its top bit is	\
       * set, then negate it and set m_neg.				\
       */								\
      w = (ni >> ((scafwd) - (winwd)))&SCMUL_WINMASK(winwd);		\
      m_neg = -(uint32)((w >> ((winwd) - 1))&0x1u);			\
      ni <<= (winwd);							\
    }									\
  }									\
									\
  /* Do the final window.  Just fix the sign and go. */			\
  for (k = 0; k < (winwd); k++)						\
    dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ);				\
  w = ((SCMUL_WINLIM(winwd) - w)&m_neg) | (w&~m_neg);			\
  f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w);				\
  f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w);				\
  f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w);				\
  f##_condneg(&UX, &UX, m_neg);						\
  addfn(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ);				\
}

#define SCSIMMUL_WINLIM(winwd) (1 << (winwd))
#define SCSIMMUL_WINMASK(winwd) (SCSIMMUL_WINLIM(winwd) - 1)
#define SCSIMMUL_TABSZ(winwd) (1 << 2*(winwd))

#define DEFINE_SCSIMMUL(simmulfn, f, winwd,				\
			scafwd, npiece, addfn, dblfn)			\
void simmulfn(f *X, f *Y, f *Z,						\
	      const scaf_piece n0[npiece],				\
	      const f *X0, const f *Y0, const f *Z0,			\
	      const scaf_piece n1[npiece],				\
	      const f *X1, const f *Y1, const f *Z1)			\
{									\
  f VX[SCSIMMUL_TABSZ(winwd)],						\
    VY[SCSIMMUL_TABSZ(winwd)],						\
    VZ[SCSIMMUL_TABSZ(winwd)];						\
  f TX, TY, TZ, UX, UY, UZ;						\
  unsigned i, j, k, w, ni0, ni1;					\
									\
  /* Build a table of small linear combinations. */			\
  f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1);		\
  VX[1] = *X0; VX[SCSIMMUL_WINLIM(winwd)] = *X1;			\
  VY[1] = *Y0; VY[SCSIMMUL_WINLIM(winwd)] = *Y1;			\
  VZ[1] = *Z0; VZ[SCSIMMUL_WINLIM(winwd)] = *Z1;			\
  for (i = 2; i < SCSIMMUL_WINLIM(winwd); i <<= 1) {			\
    dblfn(&VX[i], &VY[i], &VZ[i],					\
	  &VX[i/2], &VY[i/2], &VZ[i/2]);				\
    dblfn(&VX[i*SCSIMMUL_WINLIM(winwd)],				\
	  &VY[i*SCSIMMUL_WINLIM(winwd)],				\
	  &VZ[i*SCSIMMUL_WINLIM(winwd)],				\
	  &VX[i*SCSIMMUL_WINLIM(winwd)/2],				\
	  &VY[i*SCSIMMUL_WINLIM(winwd)/2],				\
	  &VZ[i*SCSIMMUL_WINLIM(winwd)/2]);				\
  }									\
  for (i = 2; i < SCSIMMUL_TABSZ(winwd); i <<= 1) {			\
    for (j = 1; j < i; j++)						\
      addfn(&VX[i + j], &VY[i + j], &VZ[i + j],				\
	    &VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]);		\
  }									\
									\
  /* Do the multiplication. */						\
  f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1);			\
  for (i = (npiece); i--; ) {						\
    ni0 = n0[i]; ni1 = n1[i];						\
									\
    /* Work through each window in the scalar pieces. */		\
    for (j = 0; j < (scafwd); j += (winwd)) {				\
									\
      /* Shift along by a window. */					\
      for (k = 0; k < (winwd); k++)					\
	dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ);				\
									\
      /* Collect the next window from the scalars. */			\
      w = (((ni0 >> ((scafwd) - (winwd)))&				\
	    SCSIMMUL_WINMASK(winwd)) |					\
	   ((ni1 >> ((scafwd) - 2*(winwd)))&				\
	    (SCSIMMUL_WINMASK(winwd) << (winwd))));			\
      ni0 <<= (winwd); ni1 <<= (winwd);					\
									\
      /* Collect the entry from the table, and add. */			\
      f##_pickn(&UX, VX, SCSIMMUL_TABSZ(winwd), w);			\
      f##_pickn(&UY, VY, SCSIMMUL_TABSZ(winwd), w);			\
      f##_pickn(&UZ, VZ, SCSIMMUL_TABSZ(winwd), w);			\
      addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ);		\
    }									\
  }									\
									\
  /* Done. */								\
  *X = TX; *Y = TY; *Z = TZ;						\
}

/*----- That's all, folks -------------------------------------------------*/

#ifdef __cplusplus
  }
#endif

#endif
Commit	Line	Data
a1a6042e MW	1	/* --c--
	2	*
	3	* Scalar multiplication on elliptic curves
	4	*
	5	* (c) 2017 Straylight/Edgeware
	6	*/
	7
	8	/----- Licensing notice --------------------------------------------------
	9	*
	10	* This file is part of secnet.
	11	* See README for full list of copyright holders.
	12	*
	13	* secnet is free software; you can redistribute it and/or modify it
	14	* under the terms of the GNU General Public License as published by
	15	* the Free Software Foundation; either version d of the License, or
	16	* (at your option) any later version.
	17	*
	18	* secnet is distributed in the hope that it will be useful, but
	19	* WITHOUT ANY WARRANTY; without even the implied warranty of
	20	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	21	* General Public License for more details.
	22	*
	23	* You should have received a copy of the GNU General Public License
	24	* version 3 along with secnet; if not, see
	25	* https://www.gnu.org/licenses/gpl.html.
	26	*
	27	* This file was originally part of Catacomb, but has been automatically
	28	* modified for incorporation into secnet: see `import-catacomb-crypto'
	29	* for details.
	30	*
	31	* Catacomb is free software; you can redistribute it and/or modify
	32	* it under the terms of the GNU Library General Public License as
	33	* published by the Free Software Foundation; either version 2 of the
	34	* License, or (at your option) any later version.
	35	*
	36	* Catacomb is distributed in the hope that it will be useful,
	37	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	38	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	39	* GNU Library General Public License for more details.
	40	*
	41	* You should have received a copy of the GNU Library General Public
	42	* License along with Catacomb; if not, write to the Free
	43	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	44	* MA 02111-1307, USA.
	45	*/
	46
	47	#ifndef CATACOMB_SCMUL_H
	48	#define CATACOMB_SCMUL_H
	49
	50	#ifdef __cplusplus
	51	extern "C" {
	52	#endif
	53
	54	/----- Macros provided ---------------------------------------------------/
	55
	56	#define SCMUL_WINLIM(winwd) (1 << (winwd))
	57	#define SCMUL_WINMASK(winwd) (SCMUL_WINLIM(winwd) - 1)
	58	#define SCMUL_TABSZ(winwd) (SCMUL_WINLIM(winwd)/2 + 1)
	59
	60	#define DEFINE_SCMUL(mulfn, f, winwd, scafwd, npiece, addfn, dblfn) \
	61	void mulfn(f X, f Y, f *Z, const scaf_piece n[npiece], \
	62	const f X0, const f Y0, const f *Z0) \
	63	{ \
	64	f VX[SCMUL_TABSZ(winwd)], \
65	VY[SCMUL_TABSZ(winwd)], \
66	VZ[SCMUL_TABSZ(winwd)]; \
67	f TX, TY, TZ, UX, UY, UZ; \
68	unsigned i, j, k, w; \
69	uint32 m_neg; \
70	scaf_piece ni; \
71	\
72	/* Build a table of small multiples. */ \
73	f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1); \
74	VX[1] = X0; VY[1] = Y0; VZ[1] = *Z0; \
75	ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]); \
76	for (i = 3; i < SCMUL_TABSZ(winwd); i += 2) { \
77	addfn(&VX[i], &VY[i], &VZ[i], \
78	&VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0); \
79	dblfn(&VX[i + 1], &VY[i + 1], &VZ[i + 1], \
80	&VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]); \
81	} \
82	\
83	/* Now do the multiplication. We lag a window behind the cursor \
84	* position because of the scalar recoding we do. \
85	*/ \
86	f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1); \
87	for (i = (npiece), w = 0, m_neg = 0; i--; ) { \
88	ni = n[i]; \
89	\
90	/* Work through each window in the scalar piece. */ \
91	for (j = 0; j < (scafwd); j += (winwd)) { \
92	\
93	/* Shift along by a window. */ \
94	for (k = 0; k < (winwd); k++) \
95	dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
96	\
97	/* Peek at the next window of four bits. If the top bit is set \
98	* we lend a bit leftwards, into w. It's too late for this to \
99	* affect the sign now, but if we negated earlier then the \
100	* addition would be wrong. \
101	*/ \
102	w += (ni >> ((scafwd) - 1))&0x1u; \
103	w = ((SCMUL_WINLIM(winwd) - w)&m_neg) \| (w&~m_neg); \
104	\
105	/* Collect the entry from the table, and add or subtract. */ \
106	f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w); \
107	f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w); \
108	f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w); \
109	f##_condneg(&UX, &UX, m_neg); \
110	addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); \
111	\
112	/* Move the next window into the delay slot. If its top bit is \
113	* set, then negate it and set m_neg. \
114	*/ \
115	w = (ni >> ((scafwd) - (winwd)))&SCMUL_WINMASK(winwd); \
116	m_neg = -(uint32)((w >> ((winwd) - 1))&0x1u); \
117	ni <<= (winwd); \
118	} \
119	} \
120	\
121	/* Do the final window. Just fix the sign and go. */ \
122	for (k = 0; k < (winwd); k++) \
123	dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
124	w = ((SCMUL_WINLIM(winwd) - w)&m_neg) \| (w&~m_neg); \
125	f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w); \
126	f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w); \
127	f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w); \
128	f##_condneg(&UX, &UX, m_neg); \
129	addfn(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ); \
130	}
131
132	#define SCSIMMUL_WINLIM(winwd) (1 << (winwd))
133	#define SCSIMMUL_WINMASK(winwd) (SCSIMMUL_WINLIM(winwd) - 1)
134	#define SCSIMMUL_TABSZ(winwd) (1 << 2*(winwd))
135
136	#define DEFINE_SCSIMMUL(simmulfn, f, winwd, \
137	scafwd, npiece, addfn, dblfn) \
138	void simmulfn(f X, f Y, f *Z, \
139	const scaf_piece n0[npiece], \
140	const f X0, const f Y0, const f *Z0, \
141	const scaf_piece n1[npiece], \
142	const f X1, const f Y1, const f *Z1) \
143	{ \
144	f VX[SCSIMMUL_TABSZ(winwd)], \
145	VY[SCSIMMUL_TABSZ(winwd)], \
146	VZ[SCSIMMUL_TABSZ(winwd)]; \
147	f TX, TY, TZ, UX, UY, UZ; \
148	unsigned i, j, k, w, ni0, ni1; \
149	\
150	/* Build a table of small linear combinations. */ \
151	f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1); \
152	VX[1] = X0; VX[SCSIMMUL_WINLIM(winwd)] = X1; \
153	VY[1] = Y0; VY[SCSIMMUL_WINLIM(winwd)] = Y1; \
154	VZ[1] = Z0; VZ[SCSIMMUL_WINLIM(winwd)] = Z1; \
155	for (i = 2; i < SCSIMMUL_WINLIM(winwd); i <<= 1) { \
156	dblfn(&VX[i], &VY[i], &VZ[i], \
157	&VX[i/2], &VY[i/2], &VZ[i/2]); \
158	dblfn(&VX[i*SCSIMMUL_WINLIM(winwd)], \
159	&VY[i*SCSIMMUL_WINLIM(winwd)], \
160	&VZ[i*SCSIMMUL_WINLIM(winwd)], \
161	&VX[i*SCSIMMUL_WINLIM(winwd)/2], \
162	&VY[i*SCSIMMUL_WINLIM(winwd)/2], \
163	&VZ[i*SCSIMMUL_WINLIM(winwd)/2]); \
164	} \
165	for (i = 2; i < SCSIMMUL_TABSZ(winwd); i <<= 1) { \
166	for (j = 1; j < i; j++) \
167	addfn(&VX[i + j], &VY[i + j], &VZ[i + j], \
168	&VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]); \
169	} \
170	\
171	/* Do the multiplication. */ \
172	f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1); \
173	for (i = (npiece); i--; ) { \
174	ni0 = n0[i]; ni1 = n1[i]; \
175	\
176	/* Work through each window in the scalar pieces. */ \
177	for (j = 0; j < (scafwd); j += (winwd)) { \
178	\
179	/* Shift along by a window. */ \
180	for (k = 0; k < (winwd); k++) \
181	dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
182	\
183	/* Collect the next window from the scalars. */ \
184	w = (((ni0 >> ((scafwd) - (winwd)))& \
185	SCSIMMUL_WINMASK(winwd)) \| \
186	((ni1 >> ((scafwd) - 2*(winwd)))& \
187	(SCSIMMUL_WINMASK(winwd) << (winwd)))); \
188	ni0 <<= (winwd); ni1 <<= (winwd); \
189	\
190	/* Collect the entry from the table, and add. */ \
191	f##_pickn(&UX, VX, SCSIMMUL_TABSZ(winwd), w); \
192	f##_pickn(&UY, VY, SCSIMMUL_TABSZ(winwd), w); \
193	f##_pickn(&UZ, VZ, SCSIMMUL_TABSZ(winwd), w); \
194	addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); \
195	} \
196	} \
197	\
198	/* Done. */ \
199	X = TX; Y = TY; *Z = TZ; \
200	}
201
202	/----- That's all, folks -------------------------------------------------/
203
204	#ifdef __cplusplus
205	}
206	#endif
207
208	#endif