X-Git-Url: https://git.distorted.org.uk/~mdw/secnet/blobdiff_plain/d1d3b5e8b505f5349ca1ed12097c539296e01743..a3ec8ad20d3f88f6d188b5adf2ec4ae7465c3a81:/scmul.h diff --git a/scmul.h b/scmul.h new file mode 100644 index 0000000..e236ac3 --- /dev/null +++ b/scmul.h @@ -0,0 +1,208 @@ +/* -*-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