ed25519-donna-impl-sse2.h (11815B)
1 /* 2 conversions 3 */ 4 5 static void 6 ge25519_p1p1_to_partial(ge25519 *r, const ge25519_p1p1 *p) { 7 packed64bignum25519 ALIGN(16) xz, tt, xzout; 8 curve25519_mul(r->y, p->y, p->z); 9 curve25519_tangle64(xz, p->x, p->z); 10 curve25519_tangleone64(tt, p->t); 11 curve25519_mul_packed64(xzout, xz, tt); 12 curve25519_untangle64(r->x, r->z, xzout); 13 } 14 15 static void 16 ge25519_p1p1_to_full(ge25519 *r, const ge25519_p1p1 *p) { 17 packed64bignum25519 ALIGN(16) zy, xt, xx, zz, ty; 18 curve25519_tangle64(ty, p->t, p->y); 19 curve25519_tangleone64(xx, p->x); 20 curve25519_mul_packed64(xt, xx, ty); 21 curve25519_untangle64(r->x, r->t, xt); 22 curve25519_tangleone64(zz, p->z); 23 curve25519_mul_packed64(zy, zz, ty); 24 curve25519_untangle64(r->z, r->y, zy); 25 } 26 27 static void 28 ge25519_full_to_pniels(ge25519_pniels *p, const ge25519 *r) { 29 curve25519_sub(p->ysubx, r->y, r->x); 30 curve25519_add(p->xaddy, r->x, r->y); 31 curve25519_copy(p->z, r->z); 32 curve25519_mul(p->t2d, r->t, ge25519_ec2d); 33 } 34 35 /* 36 adding & doubling 37 */ 38 39 static void 40 ge25519_add_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519 *q) { 41 bignum25519 ALIGN(16) a,b,c,d; 42 packed32bignum25519 ALIGN(16) xx, yy, yypxx, yymxx, bd, ac, bdmac, bdpac; 43 packed64bignum25519 ALIGN(16) at, bu, atbu, ptz, qtz, cd; 44 45 curve25519_tangle32(yy, p->y, q->y); 46 curve25519_tangle32(xx, p->x, q->x); 47 curve25519_add_packed32(yypxx, yy, xx); 48 curve25519_sub_packed32(yymxx, yy, xx); 49 curve25519_tangle64_from32(at, bu, yymxx, yypxx); 50 curve25519_mul_packed64(atbu, at, bu); 51 curve25519_untangle64(a, b, atbu); 52 curve25519_tangle64(ptz, p->t, p->z); 53 curve25519_tangle64(qtz, q->t, q->z); 54 curve25519_mul_packed64(cd, ptz, qtz); 55 curve25519_untangle64(c, d, cd); 56 curve25519_mul(c, c, ge25519_ec2d); 57 curve25519_add_reduce(d, d, d); 58 /* reduce, so no after_basic is needed later */ 59 curve25519_tangle32(bd, b, d); 60 curve25519_tangle32(ac, a, c); 61 curve25519_sub_packed32(bdmac, bd, ac); 62 curve25519_add_packed32(bdpac, bd, ac); 63 curve25519_untangle32(r->x, r->t, bdmac); 64 curve25519_untangle32(r->y, r->z, bdpac); 65 } 66 67 68 static void 69 ge25519_double_p1p1(ge25519_p1p1 *r, const ge25519 *p) { 70 bignum25519 ALIGN(16) a,b,c,x; 71 packed64bignum25519 ALIGN(16) xy, zx, ab, cx; 72 packed32bignum25519 ALIGN(16) xc, yz, xt, yc, ac, bc; 73 74 curve25519_add(x, p->x, p->y); 75 curve25519_tangle64(xy, p->x, p->y); 76 curve25519_square_packed64(ab, xy); 77 curve25519_untangle64(a, b, ab); 78 curve25519_tangle64(zx, p->z, x); 79 curve25519_square_packed64(cx, zx); 80 curve25519_untangle64(c, x, cx); 81 curve25519_tangle32(bc, b, c); 82 curve25519_tangle32(ac, a, c); 83 curve25519_add_reduce_packed32(yc, bc, ac); 84 curve25519_untangle32(r->y, c, yc); 85 curve25519_sub(r->z, b, a); 86 curve25519_tangle32(yz, r->y, r->z); 87 curve25519_tangle32(xc, x, c); 88 curve25519_sub_after_basic_packed32(xt, xc, yz); 89 curve25519_untangle32(r->x, r->t, xt); 90 } 91 92 static void 93 ge25519_nielsadd2_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519_niels *q, unsigned char signbit) { 94 const bignum25519 *qb = (const bignum25519 *)q; 95 bignum25519 *rb = (bignum25519 *)r; 96 bignum25519 ALIGN(16) a,b,c; 97 packed64bignum25519 ALIGN(16) ab, yx, aybx; 98 packed32bignum25519 ALIGN(16) bd, ac, bdac; 99 100 curve25519_sub(a, p->y, p->x); 101 curve25519_add(b, p->y, p->x); 102 curve25519_tangle64(ab, a, b); 103 curve25519_tangle64(yx, qb[signbit], qb[signbit^1]); 104 curve25519_mul_packed64(aybx, ab, yx); 105 curve25519_untangle64(a, b, aybx); 106 curve25519_add(r->y, b, a); 107 curve25519_add_reduce(r->t, p->z, p->z); 108 curve25519_mul(c, p->t, q->t2d); 109 curve25519_copy(r->z, r->t); 110 curve25519_add(rb[2+signbit], rb[2+signbit], c); 111 curve25519_tangle32(bd, b, rb[2+(signbit^1)]); 112 curve25519_tangle32(ac, a, c); 113 curve25519_sub_packed32(bdac, bd, ac); 114 curve25519_untangle32(r->x, rb[2+(signbit^1)], bdac); 115 } 116 117 static void 118 ge25519_pnielsadd_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519_pniels *q, unsigned char signbit) { 119 const bignum25519 *qb = (const bignum25519 *)q; 120 bignum25519 *rb = (bignum25519 *)r; 121 bignum25519 ALIGN(16) a,b,c; 122 packed64bignum25519 ALIGN(16) ab, yx, aybx, zt, zt2d, tc; 123 packed32bignum25519 ALIGN(16) bd, ac, bdac; 124 125 curve25519_sub(a, p->y, p->x); 126 curve25519_add(b, p->y, p->x); 127 curve25519_tangle64(ab, a, b); 128 curve25519_tangle64(yx, qb[signbit], qb[signbit^1]); 129 curve25519_mul_packed64(aybx, ab, yx); 130 curve25519_untangle64(a, b, aybx); 131 curve25519_add(r->y, b, a); 132 curve25519_tangle64(zt, p->z, p->t); 133 curve25519_tangle64(zt2d, q->z, q->t2d); 134 curve25519_mul_packed64(tc, zt, zt2d); 135 curve25519_untangle64(r->t, c, tc); 136 curve25519_add_reduce(r->t, r->t, r->t); 137 curve25519_copy(r->z, r->t); 138 curve25519_add(rb[2+signbit], rb[2+signbit], c); 139 curve25519_tangle32(bd, b, rb[2+(signbit^1)]); 140 curve25519_tangle32(ac, a, c); 141 curve25519_sub_packed32(bdac, bd, ac); 142 curve25519_untangle32(r->x, rb[2+(signbit^1)], bdac); 143 } 144 145 static void 146 ge25519_double(ge25519 *r, const ge25519 *p) { 147 ge25519_p1p1 ALIGN(16) t; 148 ge25519_double_p1p1(&t, p); 149 ge25519_p1p1_to_full(r, &t); 150 } 151 152 static void 153 ge25519_add(ge25519 *r, const ge25519 *p, const ge25519 *q) { 154 ge25519_p1p1 ALIGN(16) t; 155 ge25519_add_p1p1(&t, p, q); 156 ge25519_p1p1_to_full(r, &t); 157 } 158 159 static void 160 ge25519_double_partial(ge25519 *r, const ge25519 *p) { 161 ge25519_p1p1 ALIGN(16) t; 162 ge25519_double_p1p1(&t, p); 163 ge25519_p1p1_to_partial(r, &t); 164 } 165 166 static void 167 ge25519_nielsadd2(ge25519 *r, const ge25519_niels *q) { 168 packed64bignum25519 ALIGN(16) ab, yx, aybx, eg, ff, hh, xz, ty; 169 packed32bignum25519 ALIGN(16) bd, ac, bdac; 170 bignum25519 ALIGN(16) a,b,c,d,e,f,g,h; 171 172 curve25519_sub(a, r->y, r->x); 173 curve25519_add(b, r->y, r->x); 174 curve25519_tangle64(ab, a, b); 175 curve25519_tangle64(yx, q->ysubx, q->xaddy); 176 curve25519_mul_packed64(aybx, ab, yx); 177 curve25519_untangle64(a, b, aybx); 178 curve25519_add(h, b, a); 179 curve25519_add_reduce(d, r->z, r->z); 180 curve25519_mul(c, r->t, q->t2d); 181 curve25519_add(g, d, c); /* d is reduced, so no need for after_basic */ 182 curve25519_tangle32(bd, b, d); 183 curve25519_tangle32(ac, a, c); 184 curve25519_sub_packed32(bdac, bd, ac); /* d is reduced, so no need for after_basic */ 185 curve25519_untangle32(e, f, bdac); 186 curve25519_tangle64(eg, e, g); 187 curve25519_tangleone64(ff, f); 188 curve25519_mul_packed64(xz, eg, ff); 189 curve25519_untangle64(r->x, r->z, xz); 190 curve25519_tangleone64(hh, h); 191 curve25519_mul_packed64(ty, eg, hh); 192 curve25519_untangle64(r->t, r->y, ty); 193 } 194 195 static void 196 ge25519_pnielsadd(ge25519_pniels *r, const ge25519 *p, const ge25519_pniels *q) { 197 ge25519_p1p1 ALIGN(16) t; 198 ge25519 ALIGN(16) f; 199 ge25519_pnielsadd_p1p1(&t, p, q, 0); 200 ge25519_p1p1_to_full(&f, &t); 201 ge25519_full_to_pniels(r, &f); 202 } 203 204 /* 205 pack & unpack 206 */ 207 208 static void 209 ge25519_pack(unsigned char r[32], const ge25519 *p) { 210 bignum25519 ALIGN(16) tx, ty, zi; 211 unsigned char parity[32]; 212 curve25519_recip(zi, p->z); 213 curve25519_mul(tx, p->x, zi); 214 curve25519_mul(ty, p->y, zi); 215 curve25519_contract(r, ty); 216 curve25519_contract(parity, tx); 217 r[31] ^= ((parity[0] & 1) << 7); 218 } 219 220 221 static int 222 ge25519_unpack_negative_vartime(ge25519 *r, const unsigned char p[32]) { 223 static const bignum25519 ALIGN(16) one = {1}; 224 static const unsigned char zero[32] = {0}; 225 unsigned char parity = p[31] >> 7; 226 unsigned char check[32]; 227 bignum25519 ALIGN(16) t, root, num, den, d3; 228 229 curve25519_expand(r->y, p); 230 curve25519_copy(r->z, one); 231 curve25519_square_times(num, r->y, 1); /* x = y^2 */ 232 curve25519_mul(den, num, ge25519_ecd); /* den = dy^2 */ 233 curve25519_sub_reduce(num, num, r->z); /* x = y^2 - 1 */ 234 curve25519_add(den, den, r->z); /* den = dy^2 + 1 */ 235 236 /* Computation of sqrt(num/den) */ 237 /* 1.: computation of num^((p-5)/8)*den^((7p-35)/8) = (num*den^7)^((p-5)/8) */ 238 curve25519_square_times(t, den, 1); 239 curve25519_mul(d3, t, den); 240 curve25519_square_times(r->x, d3, 1); 241 curve25519_mul(r->x, r->x, den); 242 curve25519_mul(r->x, r->x, num); 243 curve25519_pow_two252m3(r->x, r->x); 244 245 /* 2. computation of r->x = t * num * den^3 */ 246 curve25519_mul(r->x, r->x, d3); 247 curve25519_mul(r->x, r->x, num); 248 249 /* 3. Check if either of the roots works: */ 250 curve25519_square_times(t, r->x, 1); 251 curve25519_mul(t, t, den); 252 curve25519_copy(root, t); 253 curve25519_sub_reduce(root, root, num); 254 curve25519_contract(check, root); 255 if (!ed25519_verify(check, zero, 32)) { 256 curve25519_add_reduce(t, t, num); 257 curve25519_contract(check, t); 258 if (!ed25519_verify(check, zero, 32)) 259 return 0; 260 curve25519_mul(r->x, r->x, ge25519_sqrtneg1); 261 } 262 263 curve25519_contract(check, r->x); 264 if ((check[0] & 1) == parity) { 265 curve25519_copy(t, r->x); 266 curve25519_neg(r->x, t); 267 } 268 curve25519_mul(r->t, r->x, r->y); 269 return 1; 270 } 271 272 273 274 /* 275 scalarmults 276 */ 277 278 #define S1_SWINDOWSIZE 5 279 #define S1_TABLE_SIZE (1<<(S1_SWINDOWSIZE-2)) 280 #define S2_SWINDOWSIZE 7 281 #define S2_TABLE_SIZE (1<<(S2_SWINDOWSIZE-2)) 282 283 static void 284 ge25519_double_scalarmult_vartime(ge25519 *r, const ge25519 *p1, const bignum256modm s1, const bignum256modm s2) { 285 signed char slide1[256], slide2[256]; 286 ge25519_pniels ALIGN(16) pre1[S1_TABLE_SIZE]; 287 ge25519 ALIGN(16) d1; 288 ge25519_p1p1 ALIGN(16) t; 289 int32_t i; 290 291 contract256_slidingwindow_modm(slide1, s1, S1_SWINDOWSIZE); 292 contract256_slidingwindow_modm(slide2, s2, S2_SWINDOWSIZE); 293 294 ge25519_double(&d1, p1); 295 ge25519_full_to_pniels(pre1, p1); 296 for (i = 0; i < S1_TABLE_SIZE - 1; i++) 297 ge25519_pnielsadd(&pre1[i+1], &d1, &pre1[i]); 298 299 /* set neutral */ 300 memset(r, 0, sizeof(ge25519)); 301 r->y[0] = 1; 302 r->z[0] = 1; 303 304 i = 255; 305 while ((i >= 0) && !(slide1[i] | slide2[i])) 306 i--; 307 308 for (; i >= 0; i--) { 309 ge25519_double_p1p1(&t, r); 310 311 if (slide1[i]) { 312 ge25519_p1p1_to_full(r, &t); 313 ge25519_pnielsadd_p1p1(&t, r, &pre1[abs(slide1[i]) / 2], (unsigned char)slide1[i] >> 7); 314 } 315 316 if (slide2[i]) { 317 ge25519_p1p1_to_full(r, &t); 318 ge25519_nielsadd2_p1p1(&t, r, &ge25519_niels_sliding_multiples[abs(slide2[i]) / 2], (unsigned char)slide2[i] >> 7); 319 } 320 321 ge25519_p1p1_to_partial(r, &t); 322 } 323 } 324 325 #if !defined(HAVE_GE25519_SCALARMULT_BASE_CHOOSE_NIELS) 326 327 static uint32_t 328 ge25519_windowb_equal(uint32_t b, uint32_t c) { 329 return ((b ^ c) - 1) >> 31; 330 } 331 332 static void 333 ge25519_scalarmult_base_choose_niels(ge25519_niels *t, const uint8_t table[256][96], uint32_t pos, signed char b) { 334 bignum25519 ALIGN(16) neg; 335 uint32_t sign = (uint32_t)((unsigned char)b >> 7); 336 uint32_t mask = ~(sign - 1); 337 uint32_t u = (b + mask) ^ mask; 338 uint32_t i; 339 340 /* ysubx, xaddy, t2d in packed form. initialize to ysubx = 1, xaddy = 1, t2d = 0 */ 341 uint8_t ALIGN(16) packed[96] = {0}; 342 packed[0] = 1; 343 packed[32] = 1; 344 345 for (i = 0; i < 8; i++) 346 curve25519_move_conditional_bytes(packed, table[(pos * 8) + i], ge25519_windowb_equal(u, i + 1)); 347 348 /* expand in to t */ 349 curve25519_expand(t->ysubx, packed + 0); 350 curve25519_expand(t->xaddy, packed + 32); 351 curve25519_expand(t->t2d , packed + 64); 352 353 /* adjust for sign */ 354 curve25519_swap_conditional(t->ysubx, t->xaddy, sign); 355 curve25519_neg(neg, t->t2d); 356 curve25519_swap_conditional(t->t2d, neg, sign); 357 } 358 359 #endif /* HAVE_GE25519_SCALARMULT_BASE_CHOOSE_NIELS */ 360 361 static void 362 ge25519_scalarmult_base_niels(ge25519 *r, const uint8_t table[256][96], const bignum256modm s) { 363 signed char b[64]; 364 uint32_t i; 365 ge25519_niels ALIGN(16) t; 366 367 contract256_window4_modm(b, s); 368 369 ge25519_scalarmult_base_choose_niels(&t, table, 0, b[1]); 370 curve25519_sub_reduce(r->x, t.xaddy, t.ysubx); 371 curve25519_add_reduce(r->y, t.xaddy, t.ysubx); 372 memset(r->z, 0, sizeof(bignum25519)); 373 r->z[0] = 2; 374 curve25519_copy(r->t, t.t2d); 375 for (i = 3; i < 64; i += 2) { 376 ge25519_scalarmult_base_choose_niels(&t, table, i / 2, b[i]); 377 ge25519_nielsadd2(r, &t); 378 } 379 ge25519_double_partial(r, r); 380 ge25519_double_partial(r, r); 381 ge25519_double_partial(r, r); 382 ge25519_double(r, r); 383 ge25519_scalarmult_base_choose_niels(&t, table, 0, b[0]); 384 curve25519_mul(t.t2d, t.t2d, ge25519_ecd); 385 ge25519_nielsadd2(r, &t); 386 for(i = 2; i < 64; i += 2) { 387 ge25519_scalarmult_base_choose_niels(&t, table, i / 2, b[i]); 388 ge25519_nielsadd2(r, &t); 389 } 390 }