1 #include "ge.h"
2
slide(signed char * r,const unsigned char * a)3 static void slide(signed char *r,const unsigned char *a)
4 {
5 int i;
6 int b;
7 int k;
8
9 for (i = 0;i < 256;++i)
10 r[i] = 1 & (a[i >> 3] >> (i & 7));
11
12 for (i = 0;i < 256;++i)
13 if (r[i]) {
14 for (b = 1;b <= 6 && i + b < 256;++b) {
15 if (r[i + b]) {
16 if (r[i] + (r[i + b] << b) <= 15) {
17 r[i] += r[i + b] << b; r[i + b] = 0;
18 } else if (r[i] - (r[i + b] << b) >= -15) {
19 r[i] -= r[i + b] << b;
20 for (k = i + b;k < 256;++k) {
21 if (!r[k]) {
22 r[k] = 1;
23 break;
24 }
25 r[k] = 0;
26 }
27 } else
28 break;
29 }
30 }
31 }
32
33 }
34
35 static ge_precomp Bi[8] = {
36 #include "base2.h"
37 } ;
38
39 /*
40 r = a * A + b * B
41 where a = a[0]+256*a[1]+...+256^31 a[31].
42 and b = b[0]+256*b[1]+...+256^31 b[31].
43 B is the Ed25519 base point (x,4/5) with x positive.
44 */
45
ge_double_scalarmult_vartime(ge_p2 * r,const unsigned char * a,const ge_p3 * A,const unsigned char * b)46 void ge_double_scalarmult_vartime(ge_p2 *r,const unsigned char *a,const ge_p3 *A,const unsigned char *b)
47 {
48 signed char aslide[256];
49 signed char bslide[256];
50 ge_cached Ai[8]; /* A,3A,5A,7A,9A,11A,13A,15A */
51 ge_p1p1 t;
52 ge_p3 u;
53 ge_p3 A2;
54 int i;
55
56 slide(aslide,a);
57 slide(bslide,b);
58
59 ge_p3_to_cached(&Ai[0],A);
60 ge_p3_dbl(&t,A); ge_p1p1_to_p3(&A2,&t);
61 ge_add(&t,&A2,&Ai[0]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[1],&u);
62 ge_add(&t,&A2,&Ai[1]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[2],&u);
63 ge_add(&t,&A2,&Ai[2]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[3],&u);
64 ge_add(&t,&A2,&Ai[3]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[4],&u);
65 ge_add(&t,&A2,&Ai[4]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[5],&u);
66 ge_add(&t,&A2,&Ai[5]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[6],&u);
67 ge_add(&t,&A2,&Ai[6]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[7],&u);
68
69 ge_p2_0(r);
70
71 for (i = 255;i >= 0;--i) {
72 if (aslide[i] || bslide[i]) break;
73 }
74
75 for (;i >= 0;--i) {
76 ge_p2_dbl(&t,r);
77
78 if (aslide[i] > 0) {
79 ge_p1p1_to_p3(&u,&t);
80 ge_add(&t,&u,&Ai[aslide[i]/2]);
81 } else if (aslide[i] < 0) {
82 ge_p1p1_to_p3(&u,&t);
83 ge_sub(&t,&u,&Ai[(-aslide[i])/2]);
84 }
85
86 if (bslide[i] > 0) {
87 ge_p1p1_to_p3(&u,&t);
88 ge_madd(&t,&u,&Bi[bslide[i]/2]);
89 } else if (bslide[i] < 0) {
90 ge_p1p1_to_p3(&u,&t);
91 ge_msub(&t,&u,&Bi[(-bslide[i])/2]);
92 }
93
94 ge_p1p1_to_p2(r,&t);
95 }
96 }
97