| 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 |