Electroneum
ed25519-donna-impl-sse2.h
Go to the documentation of this file.
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];
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 }
std::vector< std::vector< _variant_t > > table
#define ALIGN(x)
bignum25519 t2d
Definition: ed25519-donna.h:90
bignum25519 y
Definition: ed25519-donna.h:82
bignum25519 z
Definition: ed25519-donna.h:82
packedelem64 packed64bignum25519[10]
packedelem32 packed32bignum25519[5]
bignum25519 xaddy
Definition: ed25519-donna.h:90
bignum25519 ysubx
Definition: ed25519-donna.h:90
unsigned char uint8_t
Definition: stdint.h:124
uint32_t bignum25519[10]
for(i=1;i< 1;++i) fe_sq(t0
#define S1_TABLE_SIZE
unsigned int uint32_t
Definition: stdint.h:126
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
bignum256modm_element_t bignum256modm[9]
#define S2_SWINDOWSIZE
else if(0==res)
signed int int32_t
Definition: stdint.h:123
key zero()
Definition: rctOps.h:70
#define S1_SWINDOWSIZE