diff options
Diffstat (limited to 'nacl/crypto_sign/edwards25519sha512batch/ref/ge25519.c')
-rw-r--r-- | nacl/crypto_sign/edwards25519sha512batch/ref/ge25519.c | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/nacl/crypto_sign/edwards25519sha512batch/ref/ge25519.c b/nacl/crypto_sign/edwards25519sha512batch/ref/ge25519.c new file mode 100644 index 00000000..a57b8f3c --- /dev/null +++ b/nacl/crypto_sign/edwards25519sha512batch/ref/ge25519.c | |||
@@ -0,0 +1,227 @@ | |||
1 | #include "fe25519.h" | ||
2 | #include "sc25519.h" | ||
3 | #include "ge25519.h" | ||
4 | |||
5 | /* | ||
6 | * Arithmetic on the twisted Edwards curve -x^2 + y^2 = 1 + dx^2y^2 | ||
7 | * with d = -(121665/121666) = 37095705934669439343138083508754565189542113879843219016388785533085940283555 | ||
8 | * Base point: (15112221349535400772501151409588531511454012693041857206046113283949847762202,46316835694926478169428394003475163141307993866256225615783033603165251855960); | ||
9 | */ | ||
10 | |||
11 | typedef struct | ||
12 | { | ||
13 | fe25519 x; | ||
14 | fe25519 z; | ||
15 | fe25519 y; | ||
16 | fe25519 t; | ||
17 | } ge25519_p1p1; | ||
18 | |||
19 | typedef struct | ||
20 | { | ||
21 | fe25519 x; | ||
22 | fe25519 y; | ||
23 | fe25519 z; | ||
24 | } ge25519_p2; | ||
25 | |||
26 | #define ge25519_p3 ge25519 | ||
27 | |||
28 | /* Windowsize for fixed-window scalar multiplication */ | ||
29 | #define WINDOWSIZE 2 /* Should be 1,2, or 4 */ | ||
30 | #define WINDOWMASK ((1<<WINDOWSIZE)-1) | ||
31 | |||
32 | /* packed parameter d in the Edwards curve equation */ | ||
33 | static const unsigned char ecd[32] = {0xA3, 0x78, 0x59, 0x13, 0xCA, 0x4D, 0xEB, 0x75, 0xAB, 0xD8, 0x41, 0x41, 0x4D, 0x0A, 0x70, 0x00, | ||
34 | 0x98, 0xE8, 0x79, 0x77, 0x79, 0x40, 0xC7, 0x8C, 0x73, 0xFE, 0x6F, 0x2B, 0xEE, 0x6C, 0x03, 0x52}; | ||
35 | |||
36 | /* Packed coordinates of the base point */ | ||
37 | static const unsigned char ge25519_base_x[32] = {0x1A, 0xD5, 0x25, 0x8F, 0x60, 0x2D, 0x56, 0xC9, 0xB2, 0xA7, 0x25, 0x95, 0x60, 0xC7, 0x2C, 0x69, | ||
38 | 0x5C, 0xDC, 0xD6, 0xFD, 0x31, 0xE2, 0xA4, 0xC0, 0xFE, 0x53, 0x6E, 0xCD, 0xD3, 0x36, 0x69, 0x21}; | ||
39 | static const unsigned char ge25519_base_y[32] = {0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, | ||
40 | 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66}; | ||
41 | static const unsigned char ge25519_base_z[32] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; | ||
42 | static const unsigned char ge25519_base_t[32] = {0xA3, 0xDD, 0xB7, 0xA5, 0xB3, 0x8A, 0xDE, 0x6D, 0xF5, 0x52, 0x51, 0x77, 0x80, 0x9F, 0xF0, 0x20, | ||
43 | 0x7D, 0xE3, 0xAB, 0x64, 0x8E, 0x4E, 0xEA, 0x66, 0x65, 0x76, 0x8B, 0xD7, 0x0F, 0x5F, 0x87, 0x67}; | ||
44 | |||
45 | /* Packed coordinates of the neutral element */ | ||
46 | static const unsigned char ge25519_neutral_x[32] = {0}; | ||
47 | static const unsigned char ge25519_neutral_y[32] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; | ||
48 | static const unsigned char ge25519_neutral_z[32] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; | ||
49 | static const unsigned char ge25519_neutral_t[32] = {0}; | ||
50 | |||
51 | static void p1p1_to_p2(ge25519_p2 *r, const ge25519_p1p1 *p) | ||
52 | { | ||
53 | fe25519_mul(&r->x, &p->x, &p->t); | ||
54 | fe25519_mul(&r->y, &p->y, &p->z); | ||
55 | fe25519_mul(&r->z, &p->z, &p->t); | ||
56 | } | ||
57 | |||
58 | static void p1p1_to_p3(ge25519_p3 *r, const ge25519_p1p1 *p) | ||
59 | { | ||
60 | p1p1_to_p2((ge25519_p2 *)r, p); | ||
61 | fe25519_mul(&r->t, &p->x, &p->y); | ||
62 | } | ||
63 | |||
64 | /* Constant-time version of: if(b) r = p */ | ||
65 | static void cmov_p3(ge25519_p3 *r, const ge25519_p3 *p, unsigned char b) | ||
66 | { | ||
67 | fe25519_cmov(&r->x, &p->x, b); | ||
68 | fe25519_cmov(&r->y, &p->y, b); | ||
69 | fe25519_cmov(&r->z, &p->z, b); | ||
70 | fe25519_cmov(&r->t, &p->t, b); | ||
71 | } | ||
72 | |||
73 | /* See http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#doubling-dbl-2008-hwcd */ | ||
74 | static void dbl_p1p1(ge25519_p1p1 *r, const ge25519_p2 *p) | ||
75 | { | ||
76 | fe25519 a,b,c,d; | ||
77 | fe25519_square(&a, &p->x); | ||
78 | fe25519_square(&b, &p->y); | ||
79 | fe25519_square(&c, &p->z); | ||
80 | fe25519_add(&c, &c, &c); | ||
81 | fe25519_neg(&d, &a); | ||
82 | |||
83 | fe25519_add(&r->x, &p->x, &p->y); | ||
84 | fe25519_square(&r->x, &r->x); | ||
85 | fe25519_sub(&r->x, &r->x, &a); | ||
86 | fe25519_sub(&r->x, &r->x, &b); | ||
87 | fe25519_add(&r->z, &d, &b); | ||
88 | fe25519_sub(&r->t, &r->z, &c); | ||
89 | fe25519_sub(&r->y, &d, &b); | ||
90 | } | ||
91 | |||
92 | static void add_p1p1(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_p3 *q) | ||
93 | { | ||
94 | fe25519 a, b, c, d, t, fd; | ||
95 | fe25519_unpack(&fd, ecd); | ||
96 | |||
97 | fe25519_sub(&a, &p->y, &p->x); // A = (Y1-X1)*(Y2-X2) | ||
98 | fe25519_sub(&t, &q->y, &q->x); | ||
99 | fe25519_mul(&a, &a, &t); | ||
100 | fe25519_add(&b, &p->x, &p->y); // B = (Y1+X1)*(Y2+X2) | ||
101 | fe25519_add(&t, &q->x, &q->y); | ||
102 | fe25519_mul(&b, &b, &t); | ||
103 | fe25519_mul(&c, &p->t, &q->t); //C = T1*k*T2 | ||
104 | fe25519_mul(&c, &c, &fd); | ||
105 | fe25519_add(&c, &c, &c); //XXX: Can save this addition by precomputing 2*ecd | ||
106 | fe25519_mul(&d, &p->z, &q->z); //D = Z1*2*Z2 | ||
107 | fe25519_add(&d, &d, &d); | ||
108 | fe25519_sub(&r->x, &b, &a); // E = B-A | ||
109 | fe25519_sub(&r->t, &d, &c); // F = D-C | ||
110 | fe25519_add(&r->z, &d, &c); // G = D+C | ||
111 | fe25519_add(&r->y, &b, &a); // H = B+A | ||
112 | } | ||
113 | |||
114 | /* ******************************************************************** | ||
115 | * EXPORTED FUNCTIONS | ||
116 | ******************************************************************** */ | ||
117 | |||
118 | /* return 0 on success, -1 otherwise */ | ||
119 | int ge25519_unpack_vartime(ge25519_p3 *r, const unsigned char p[32]) | ||
120 | { | ||
121 | int ret; | ||
122 | fe25519 t, fd; | ||
123 | fe25519_setone(&r->z); | ||
124 | fe25519_unpack(&fd, ecd); | ||
125 | unsigned char par = p[31] >> 7; | ||
126 | fe25519_unpack(&r->y, p); | ||
127 | fe25519_square(&r->x, &r->y); | ||
128 | fe25519_mul(&t, &r->x, &fd); | ||
129 | fe25519_sub(&r->x, &r->x, &r->z); | ||
130 | fe25519_add(&t, &r->z, &t); | ||
131 | fe25519_invert(&t, &t); | ||
132 | fe25519_mul(&r->x, &r->x, &t); | ||
133 | ret = fe25519_sqrt_vartime(&r->x, &r->x, par); | ||
134 | fe25519_mul(&r->t, &r->x, &r->y); | ||
135 | return ret; | ||
136 | } | ||
137 | |||
138 | void ge25519_pack(unsigned char r[32], const ge25519_p3 *p) | ||
139 | { | ||
140 | fe25519 tx, ty, zi; | ||
141 | fe25519_invert(&zi, &p->z); | ||
142 | fe25519_mul(&tx, &p->x, &zi); | ||
143 | fe25519_mul(&ty, &p->y, &zi); | ||
144 | fe25519_pack(r, &ty); | ||
145 | r[31] ^= fe25519_getparity(&tx) << 7; | ||
146 | } | ||
147 | |||
148 | void ge25519_add(ge25519_p3 *r, const ge25519_p3 *p, const ge25519_p3 *q) | ||
149 | { | ||
150 | ge25519_p1p1 grp1p1; | ||
151 | add_p1p1(&grp1p1, p, q); | ||
152 | p1p1_to_p3(r, &grp1p1); | ||
153 | } | ||
154 | |||
155 | void ge25519_double(ge25519_p3 *r, const ge25519_p3 *p) | ||
156 | { | ||
157 | ge25519_p1p1 grp1p1; | ||
158 | dbl_p1p1(&grp1p1, (ge25519_p2 *)p); | ||
159 | p1p1_to_p3(r, &grp1p1); | ||
160 | } | ||
161 | |||
162 | void ge25519_scalarmult(ge25519_p3 *r, const ge25519_p3 *p, const sc25519 *s) | ||
163 | { | ||
164 | int i,j,k; | ||
165 | ge25519_p3 g; | ||
166 | fe25519_unpack(&g.x, ge25519_neutral_x); | ||
167 | fe25519_unpack(&g.y, ge25519_neutral_y); | ||
168 | fe25519_unpack(&g.z, ge25519_neutral_z); | ||
169 | fe25519_unpack(&g.t, ge25519_neutral_t); | ||
170 | |||
171 | ge25519_p3 pre[(1 << WINDOWSIZE)]; | ||
172 | ge25519_p3 t; | ||
173 | ge25519_p1p1 tp1p1; | ||
174 | unsigned char w; | ||
175 | unsigned char sb[32]; | ||
176 | sc25519_to32bytes(sb, s); | ||
177 | |||
178 | // Precomputation | ||
179 | pre[0] = g; | ||
180 | pre[1] = *p; | ||
181 | for(i=2;i<(1<<WINDOWSIZE);i+=2) | ||
182 | { | ||
183 | dbl_p1p1(&tp1p1, (ge25519_p2 *)(pre+i/2)); | ||
184 | p1p1_to_p3(pre+i, &tp1p1); | ||
185 | add_p1p1(&tp1p1, pre+i, pre+1); | ||
186 | p1p1_to_p3(pre+i+1, &tp1p1); | ||
187 | } | ||
188 | |||
189 | // Fixed-window scalar multiplication | ||
190 | for(i=32;i>0;i--) | ||
191 | { | ||
192 | for(j=8-WINDOWSIZE;j>=0;j-=WINDOWSIZE) | ||
193 | { | ||
194 | for(k=0;k<WINDOWSIZE-1;k++) | ||
195 | { | ||
196 | dbl_p1p1(&tp1p1, (ge25519_p2 *)&g); | ||
197 | p1p1_to_p2((ge25519_p2 *)&g, &tp1p1); | ||
198 | } | ||
199 | dbl_p1p1(&tp1p1, (ge25519_p2 *)&g); | ||
200 | p1p1_to_p3(&g, &tp1p1); | ||
201 | // Cache-timing resistant loading of precomputed value: | ||
202 | w = (sb[i-1]>>j) & WINDOWMASK; | ||
203 | t = pre[0]; | ||
204 | for(k=1;k<(1<<WINDOWSIZE);k++) | ||
205 | cmov_p3(&t, &pre[k], k==w); | ||
206 | |||
207 | add_p1p1(&tp1p1, &g, &t); | ||
208 | if(j != 0) p1p1_to_p2((ge25519_p2 *)&g, &tp1p1); | ||
209 | else p1p1_to_p3(&g, &tp1p1); /* convert to p3 representation at the end */ | ||
210 | } | ||
211 | } | ||
212 | r->x = g.x; | ||
213 | r->y = g.y; | ||
214 | r->z = g.z; | ||
215 | r->t = g.t; | ||
216 | } | ||
217 | |||
218 | void ge25519_scalarmult_base(ge25519_p3 *r, const sc25519 *s) | ||
219 | { | ||
220 | /* XXX: Better algorithm for known-base-point scalar multiplication */ | ||
221 | ge25519_p3 t; | ||
222 | fe25519_unpack(&t.x, ge25519_base_x); | ||
223 | fe25519_unpack(&t.y, ge25519_base_y); | ||
224 | fe25519_unpack(&t.z, ge25519_base_z); | ||
225 | fe25519_unpack(&t.t, ge25519_base_t); | ||
226 | ge25519_scalarmult(r, &t, s); | ||
227 | } | ||