Electroneum
ed25519-donna-impl-base.h
Go to the documentation of this file.
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);
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);
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];
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 
340  contract256_window4_modm(b, s);
341 
342  ge25519_scalarmult_base_choose_niels(&t, basepoint_table, 0, b[1]);
343  curve25519_sub_reduce(r->x, t.xaddy, t.ysubx);
344  curve25519_add_reduce(r->y, t.xaddy, t.ysubx);
345  memset(r->z, 0, sizeof(bignum25519));
346  curve25519_copy(r->t, t.t2d);
347  r->z[0] = 2;
348  for (i = 3; i < 64; i += 2) {
349  ge25519_scalarmult_base_choose_niels(&t, basepoint_table, i / 2, b[i]);
350  ge25519_nielsadd2(r, &t);
351  }
352  ge25519_double_partial(r, r);
353  ge25519_double_partial(r, r);
354  ge25519_double_partial(r, r);
355  ge25519_double(r, r);
356  ge25519_scalarmult_base_choose_niels(&t, basepoint_table, 0, b[0]);
357  curve25519_mul(t.t2d, t.t2d, ge25519_ecd);
358  ge25519_nielsadd2(r, &t);
359  for(i = 2; i < 64; i += 2) {
360  ge25519_scalarmult_base_choose_niels(&t, basepoint_table, i / 2, b[i]);
361  ge25519_nielsadd2(r, &t);
362  }
363 }
364 
bignum25519 x
Definition: ed25519-donna.h:86
bignum25519 xaddy
Definition: ed25519-donna.h:94
std::vector< std::vector< _variant_t > > table
bignum25519 x
Definition: ed25519-donna.h:82
bignum25519 t2d
Definition: ed25519-donna.h:90
bignum25519 y
Definition: ed25519-donna.h:82
bignum25519 ysubx
Definition: ed25519-donna.h:94
bignum25519 z
Definition: ed25519-donna.h:94
bignum25519 z
Definition: ed25519-donna.h:82
#define curve25519_square(r, n)
bignum25519 xaddy
Definition: ed25519-donna.h:90
bignum25519 t2d
Definition: ed25519-donna.h:94
#define curve25519_add_after_basic
#define DONNA_INLINE
bignum25519 ysubx
Definition: ed25519-donna.h:90
unsigned char uint8_t
Definition: stdint.h:124
bignum25519 t
Definition: ed25519-donna.h:82
uint32_t bignum25519[10]
unsigned int uint32_t
Definition: stdint.h:126
#define S1_TABLE_SIZE
#define S2_SWINDOWSIZE
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
bignum25519 z
Definition: ed25519-donna.h:86
bignum256modm_element_t bignum256modm[9]
#define S1_SWINDOWSIZE
signed int int32_t
Definition: stdint.h:123
key zero()
Definition: rctOps.h:70
bignum25519 t
Definition: ed25519-donna.h:86
bignum25519 y
Definition: ed25519-donna.h:86