1 #include "fe25519.h"
2 #include "sc25519.h"
3 #include "ge25519.h"
4 #include "index_heap.h"
5
setneutral(ge25519 * r)6 static void setneutral(ge25519 *r)
7 {
8 fe25519_setint(&r->x,0);
9 fe25519_setint(&r->y,1);
10 fe25519_setint(&r->z,1);
11 fe25519_setint(&r->t,0);
12 }
13
ge25519_scalarmult_vartime_2limbs(ge25519 * r,ge25519 * p,sc25519 * s)14 static void ge25519_scalarmult_vartime_2limbs(ge25519 *r, ge25519 *p, sc25519 *s)
15 {
16 if (s->v[1] == 0 && s->v[0] == 1) /* This will happen most of the time after Bos-Coster */
17 *r = *p;
18 else if (s->v[1] == 0 && s->v[0] == 0) /* This won't ever happen, except for all scalars == 0 in Bos-Coster */
19 setneutral(r);
20 else
21 {
22 ge25519 d;
23 unsigned long long mask = (1ULL << 63);
24 int i = 1;
25 while(!(mask & s->v[1]) && mask != 0)
26 mask >>= 1;
27 if(mask == 0)
28 {
29 mask = (1ULL << 63);
30 i = 0;
31 while(!(mask & s->v[0]) && mask != 0)
32 mask >>= 1;
33 }
34 d = *p;
35 mask >>= 1;
36 for(;mask != 0;mask >>= 1)
37 {
38 ge25519_double(&d,&d);
39 if(s->v[i] & mask)
40 ge25519_add(&d,&d,p);
41 }
42 if(i==1)
43 {
44 mask = (1ULL << 63);
45 for(;mask != 0;mask >>= 1)
46 {
47 ge25519_double(&d,&d);
48 if(s->v[0] & mask)
49 ge25519_add(&d,&d,p);
50 }
51 }
52 *r = d;
53 }
54 }
55
56 /* caller's responsibility to ensure npoints >= 5 */
ge25519_multi_scalarmult_vartime(ge25519_p3 * r,ge25519_p3 * p,sc25519 * s,const unsigned long long npoints)57 void ge25519_multi_scalarmult_vartime(ge25519_p3 *r, ge25519_p3 *p, sc25519 *s, const unsigned long long npoints)
58 {
59 unsigned long long pos[npoints];
60 unsigned long long hlen=((npoints+1)/2)|1;
61 unsigned long long max1, max2,i;
62
63 heap_init(pos, hlen, s);
64
65 for(i=0;;i++)
66 {
67 heap_get2max(pos, &max1, &max2, s);
68 if((s[max1].v[3] == 0) || (sc25519_iszero_vartime(&s[max2]))) break;
69 sc25519_sub_nored(&s[max1],&s[max1],&s[max2]);
70 ge25519_add(&p[max2],&p[max2],&p[max1]);
71 heap_rootreplaced(pos, hlen, s);
72 }
73 for(;;i++)
74 {
75 heap_get2max(pos, &max1, &max2, s);
76 if((s[max1].v[2] == 0) || (sc25519_iszero_vartime(&s[max2]))) break;
77 sc25519_sub_nored(&s[max1],&s[max1],&s[max2]);
78 ge25519_add(&p[max2],&p[max2],&p[max1]);
79 heap_rootreplaced_3limbs(pos, hlen, s);
80 }
81 /* We know that (npoints-1)/2 scalars are only 128-bit scalars */
82 heap_extend(pos, hlen, npoints, s);
83 hlen = npoints;
84 for(;;i++)
85 {
86 heap_get2max(pos, &max1, &max2, s);
87 if((s[max1].v[1] == 0) || (sc25519_iszero_vartime(&s[max2]))) break;
88 sc25519_sub_nored(&s[max1],&s[max1],&s[max2]);
89 ge25519_add(&p[max2],&p[max2],&p[max1]);
90 heap_rootreplaced_2limbs(pos, hlen, s);
91 }
92 for(;;i++)
93 {
94 heap_get2max(pos, &max1, &max2, s);
95 if(sc25519_iszero_vartime(&s[max2])) break;
96 sc25519_sub_nored(&s[max1],&s[max1],&s[max2]);
97 ge25519_add(&p[max2],&p[max2],&p[max1]);
98 heap_rootreplaced_1limb(pos, hlen, s);
99 }
100
101 ge25519_scalarmult_vartime_2limbs(r, &p[max1], &s[max1]);
102 }
103