[catacomb] / math / scmul.h

/* -*-c-*-
 *
 * Scalar multiplication on elliptic curves
 *
 * (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_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
581ac808 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 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	#ifndef CATACOMB_SCMUL_H
	29	#define CATACOMB_SCMUL_H
	30
	31	#ifdef __cplusplus
	32	extern "C" {
	33	#endif
	34
	35	/----- Macros provided ---------------------------------------------------/
	36
	37	#define SCMUL_WINLIM(winwd) (1 << (winwd))
	38	#define SCMUL_WINMASK(winwd) (SCMUL_WINLIM(winwd) - 1)
	39	#define SCMUL_TABSZ(winwd) (SCMUL_WINLIM(winwd)/2 + 1)
	40
	41	#define DEFINE_SCMUL(mulfn, f, winwd, scafwd, npiece, addfn, dblfn) \
	42	void mulfn(f X, f Y, f *Z, const scaf_piece n[npiece], \
	43	const f X0, const f Y0, const f *Z0) \
	44	{ \
	45	f VX[SCMUL_TABSZ(winwd)], \
	46	VY[SCMUL_TABSZ(winwd)], \
	47	VZ[SCMUL_TABSZ(winwd)]; \
	48	f TX, TY, TZ, UX, UY, UZ; \
	49	unsigned i, j, k, w; \
	50	uint32 m_neg; \
	51	scaf_piece ni; \
	52	\
	53	/* Build a table of small multiples. */ \
	54	f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1); \
	55	VX[1] = X0; VY[1] = Y0; VZ[1] = *Z0; \
	56	ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]); \
	57	for (i = 3; i < SCMUL_TABSZ(winwd); i += 2) { \
	58	addfn(&VX[i], &VY[i], &VZ[i], \
	59	&VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0); \
	60	dblfn(&VX[i + 1], &VY[i + 1], &VZ[i + 1], \
	61	&VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]); \
	62	} \
	63	\
	64	/* Now do the multiplication. We lag a window behind the cursor \
65	* position because of the scalar recoding we do. \
66	*/ \
67	f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1); \
68	for (i = (npiece), w = 0, m_neg = 0; i--; ) { \
69	ni = n[i]; \
70	\
71	/* Work through each window in the scalar piece. */ \
72	for (j = 0; j < (scafwd); j += (winwd)) { \
73	\
74	/* Shift along by a window. */ \
75	for (k = 0; k < (winwd); k++) \
76	dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
77	\
78	/* Peek at the next window of four bits. If the top bit is set \
79	* we lend a bit leftwards, into w. It's too late for this to \
80	* affect the sign now, but if we negated earlier then the \
81	* addition would be wrong. \
82	*/ \
83	w += (ni >> ((scafwd) - 1))&0x1u; \
84	w = ((SCMUL_WINLIM(winwd) - w)&m_neg) \| (w&~m_neg); \
85	\
86	/* Collect the entry from the table, and add or subtract. */ \
87	f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w); \
88	f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w); \
89	f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w); \
90	f##_condneg(&UX, &UX, m_neg); \
91	addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); \
92	\
93	/* Move the next window into the delay slot. If its top bit is \
94	* set, then negate it and set m_neg. \
95	*/ \
96	w = (ni >> ((scafwd) - (winwd)))&SCMUL_WINMASK(winwd); \
97	m_neg = -(uint32)((w >> ((winwd) - 1))&0x1u); \
98	ni <<= (winwd); \
99	} \
100	} \
101	\
102	/* Do the final window. Just fix the sign and go. */ \
103	for (k = 0; k < (winwd); k++) \
104	dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
105	w = ((SCMUL_WINLIM(winwd) - w)&m_neg) \| (w&~m_neg); \
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(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ); \
111	}
112
113	#define SCSIMMUL_WINLIM(winwd) (1 << (winwd))
114	#define SCSIMMUL_WINMASK(winwd) (SCSIMMUL_WINLIM(winwd) - 1)
115	#define SCSIMMUL_TABSZ(winwd) (1 << 2*(winwd))
116
117	#define DEFINE_SCSIMMUL(simmulfn, f, winwd, \
118	scafwd, npiece, addfn, dblfn) \
119	void simmulfn(f X, f Y, f *Z, \
120	const scaf_piece n0[npiece], \
121	const f X0, const f Y0, const f *Z0, \
122	const scaf_piece n1[npiece], \
123	const f X1, const f Y1, const f *Z1) \
124	{ \
125	f VX[SCSIMMUL_TABSZ(winwd)], \
126	VY[SCSIMMUL_TABSZ(winwd)], \
127	VZ[SCSIMMUL_TABSZ(winwd)]; \
128	f TX, TY, TZ, UX, UY, UZ; \
129	unsigned i, j, k, w, ni0, ni1; \
130	\
131	/* Build a table of small linear combinations. */ \
132	f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1); \
133	VX[1] = X0; VX[SCSIMMUL_WINLIM(winwd)] = X1; \
134	VY[1] = Y0; VY[SCSIMMUL_WINLIM(winwd)] = Y1; \
135	VZ[1] = Z0; VZ[SCSIMMUL_WINLIM(winwd)] = Z1; \
136	for (i = 2; i < SCSIMMUL_WINLIM(winwd); i <<= 1) { \
137	dblfn(&VX[i], &VY[i], &VZ[i], \
138	&VX[i/2], &VY[i/2], &VZ[i/2]); \
139	dblfn(&VX[i*SCSIMMUL_WINLIM(winwd)], \
140	&VY[i*SCSIMMUL_WINLIM(winwd)], \
141	&VZ[i*SCSIMMUL_WINLIM(winwd)], \
142	&VX[i*SCSIMMUL_WINLIM(winwd)/2], \
143	&VY[i*SCSIMMUL_WINLIM(winwd)/2], \
144	&VZ[i*SCSIMMUL_WINLIM(winwd)/2]); \
145	} \
146	for (i = 2; i < SCSIMMUL_TABSZ(winwd); i <<= 1) { \
147	for (j = 1; j < i; j++) \
148	addfn(&VX[i + j], &VY[i + j], &VZ[i + j], \
149	&VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]); \
150	} \
151	\
152	/* Do the multiplication. */ \
153	f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1); \
154	for (i = (npiece); i--; ) { \
155	ni0 = n0[i]; ni1 = n1[i]; \
156	\
157	/* Work through each window in the scalar pieces. */ \
158	for (j = 0; j < (scafwd); j += (winwd)) { \
159	\
160	/* Shift along by a window. */ \
161	for (k = 0; k < (winwd); k++) \
162	dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
163	\
164	/* Collect the next window from the scalars. */ \
165	w = (((ni0 >> ((scafwd) - (winwd)))& \
166	SCSIMMUL_WINMASK(winwd)) \| \
167	((ni1 >> ((scafwd) - 2*(winwd)))& \
168	(SCSIMMUL_WINMASK(winwd) << (winwd)))); \
169	ni0 <<= (winwd); ni1 <<= (winwd); \
170	\
171	/* Collect the entry from the table, and add. */ \
172	f##_pickn(&UX, VX, SCSIMMUL_TABSZ(winwd), w); \
173	f##_pickn(&UY, VY, SCSIMMUL_TABSZ(winwd), w); \
174	f##_pickn(&UZ, VZ, SCSIMMUL_TABSZ(winwd), w); \
175	addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); \
176	} \
177	} \
178	\
179	/* Done. */ \
180	X = TX; Y = TY; *Z = TZ; \
181	}
182
183	/----- That's all, folks -------------------------------------------------/
184
185	#ifdef __cplusplus
186	}
187	#endif
188
189	#endif