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