--- /dev/null
+/* -*-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
~mdw / secnet / blobdiff