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