Branch data Line data Source code
1 : : /* Edwards curve operations
2 : : * Daniel Beer <dlbeer@gmail.com>, 9 Jan 2014
3 : : *
4 : : * This file is in the public domain.
5 : : */
6 : :
7 : : #include "ed25519.h"
8 : :
9 : : #ifndef COMPACT_DISABLE_ED25519
10 : :
11 : : /* Base point is (numbers wrapped):
12 : : *
13 : : * x = 151122213495354007725011514095885315114
14 : : * 54012693041857206046113283949847762202
15 : : * y = 463168356949264781694283940034751631413
16 : : * 07993866256225615783033603165251855960
17 : : *
18 : : * y is derived by transforming the original Montgomery base (u=9). x
19 : : * is the corresponding positive coordinate for the new curve equation.
20 : : * t is x*y.
21 : : */
22 : : const struct ed25519_pt ed25519_base = {
23 : : .x = {
24 : : 0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9,
25 : : 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69,
26 : : 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0,
27 : : 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21
28 : : },
29 : : .y = {
30 : : 0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
31 : : 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
32 : : 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
33 : : 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66
34 : : },
35 : : .t = {
36 : : 0xa3, 0xdd, 0xb7, 0xa5, 0xb3, 0x8a, 0xde, 0x6d,
37 : : 0xf5, 0x52, 0x51, 0x77, 0x80, 0x9f, 0xf0, 0x20,
38 : : 0x7d, 0xe3, 0xab, 0x64, 0x8e, 0x4e, 0xea, 0x66,
39 : : 0x65, 0x76, 0x8b, 0xd7, 0x0f, 0x5f, 0x87, 0x67
40 : : },
41 : : .z = {1, 0}
42 : : };
43 : :
44 : : const struct ed25519_pt ed25519_neutral = {
45 : : .x = {0},
46 : : .y = {1, 0},
47 : : .t = {0},
48 : : .z = {1, 0}
49 : : };
50 : :
51 : : /* Conversion to and from projective coordinates */
52 : 4 : void ed25519_project(struct ed25519_pt *p,
53 : : const uint8_t *x, const uint8_t *y)
54 : : {
55 : 4 : f25519_copy(p->x, x);
56 : 4 : f25519_copy(p->y, y);
57 : 4 : f25519_load(p->z, 1);
58 : 4 : f25519_mul__distinct(p->t, x, y);
59 : 4 : }
60 : :
61 : 6 : void ed25519_unproject(uint8_t *x, uint8_t *y,
62 : : const struct ed25519_pt *p)
63 : : {
64 : 6 : uint8_t z1[F25519_SIZE];
65 : :
66 : 6 : f25519_inv__distinct(z1, p->z);
67 : 6 : f25519_mul__distinct(x, p->x, z1);
68 : 6 : f25519_mul__distinct(y, p->y, z1);
69 : :
70 : 6 : f25519_normalize(x);
71 : 6 : f25519_normalize(y);
72 : 6 : }
73 : :
74 : : /* Compress/uncompress points. We compress points by storing the x
75 : : * coordinate and the parity of the y coordinate.
76 : : *
77 : : * Rearranging the curve equation, we obtain explicit formulae for the
78 : : * coordinates:
79 : : *
80 : : * x = sqrt((y^2-1) / (1+dy^2))
81 : : * y = sqrt((x^2+1) / (1-dx^2))
82 : : *
83 : : * Where d = (-121665/121666), or:
84 : : *
85 : : * d = 370957059346694393431380835087545651895
86 : : * 42113879843219016388785533085940283555
87 : : */
88 : :
89 : : static const uint8_t ed25519_d[F25519_SIZE] = {
90 : : 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
91 : : 0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
92 : : 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
93 : : 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52
94 : : };
95 : :
96 : 6 : void ed25519_pack(uint8_t *c, const uint8_t *x, const uint8_t *y)
97 : : {
98 : 6 : uint8_t tmp[F25519_SIZE];
99 : 6 : uint8_t parity;
100 : :
101 : 6 : f25519_copy(tmp, x);
102 : 6 : f25519_normalize(tmp);
103 : 6 : parity = (tmp[0] & 1) << 7;
104 : :
105 : 6 : f25519_copy(c, y);
106 : 6 : f25519_normalize(c);
107 : 6 : c[31] |= parity;
108 : 6 : }
109 : :
110 : 4 : uint8_t ed25519_try_unpack(uint8_t *x, uint8_t *y, const uint8_t *comp)
111 : : {
112 : 4 : const int parity = comp[31] >> 7;
113 : 4 : uint8_t a[F25519_SIZE];
114 : 4 : uint8_t b[F25519_SIZE];
115 : 4 : uint8_t c[F25519_SIZE];
116 : :
117 : : /* Unpack y */
118 : 4 : f25519_copy(y, comp);
119 : 4 : y[31] &= 127;
120 : :
121 : : /* Compute c = y^2 */
122 : 4 : f25519_mul__distinct(c, y, y);
123 : :
124 : : /* Compute b = (1+dy^2)^-1 */
125 : 4 : f25519_mul__distinct(b, c, ed25519_d);
126 : 4 : f25519_add(a, b, f25519_one);
127 : 4 : f25519_inv__distinct(b, a);
128 : :
129 : : /* Compute a = y^2-1 */
130 : 4 : f25519_sub(a, c, f25519_one);
131 : :
132 : : /* Compute c = a*b = (y^2-1)/(1-dy^2) */
133 : 4 : f25519_mul__distinct(c, a, b);
134 : :
135 : : /* Compute a, b = +/-sqrt(c), if c is square */
136 : 4 : f25519_sqrt(a, c);
137 : 4 : f25519_neg(b, a);
138 : :
139 : : /* Select one of them, based on the compressed parity bit */
140 : 4 : f25519_select(x, a, b, (a[0] ^ parity) & 1);
141 : :
142 : : /* Verify that x^2 = c */
143 : 4 : f25519_mul__distinct(a, x, x);
144 : 4 : f25519_normalize(a);
145 : 4 : f25519_normalize(c);
146 : :
147 : 4 : return f25519_eq(a, c);
148 : : }
149 : :
150 : : /* k = 2d */
151 : : static const uint8_t ed25519_k[F25519_SIZE] = {
152 : : 0x59, 0xf1, 0xb2, 0x26, 0x94, 0x9b, 0xd6, 0xeb,
153 : : 0x56, 0xb1, 0x83, 0x82, 0x9a, 0x14, 0xe0, 0x00,
154 : : 0x30, 0xd1, 0xf3, 0xee, 0xf2, 0x80, 0x8e, 0x19,
155 : : 0xe7, 0xfc, 0xdf, 0x56, 0xdc, 0xd9, 0x06, 0x24
156 : : };
157 : :
158 : 1538 : void ed25519_add(struct ed25519_pt *r,
159 : : const struct ed25519_pt *p1, const struct ed25519_pt *p2)
160 : : {
161 : : /* Explicit formulas database: add-2008-hwcd-3
162 : : *
163 : : * source 2008 Hisil--Wong--Carter--Dawson,
164 : : * http://eprint.iacr.org/2008/522, Section 3.1
165 : : * appliesto extended-1
166 : : * parameter k
167 : : * assume k = 2 d
168 : : * compute A = (Y1-X1)(Y2-X2)
169 : : * compute B = (Y1+X1)(Y2+X2)
170 : : * compute C = T1 k T2
171 : : * compute D = Z1 2 Z2
172 : : * compute E = B - A
173 : : * compute F = D - C
174 : : * compute G = D + C
175 : : * compute H = B + A
176 : : * compute X3 = E F
177 : : * compute Y3 = G H
178 : : * compute T3 = E H
179 : : * compute Z3 = F G
180 : : */
181 : 1538 : uint8_t a[F25519_SIZE];
182 : 1538 : uint8_t b[F25519_SIZE];
183 : 1538 : uint8_t c[F25519_SIZE];
184 : 1538 : uint8_t d[F25519_SIZE];
185 : 1538 : uint8_t e[F25519_SIZE];
186 : 1538 : uint8_t f[F25519_SIZE];
187 : 1538 : uint8_t g[F25519_SIZE];
188 : 1538 : uint8_t h[F25519_SIZE];
189 : :
190 : : /* A = (Y1-X1)(Y2-X2) */
191 : 1538 : f25519_sub(c, p1->y, p1->x);
192 : 1538 : f25519_sub(d, p2->y, p2->x);
193 : 1538 : f25519_mul__distinct(a, c, d);
194 : :
195 : : /* B = (Y1+X1)(Y2+X2) */
196 : 1538 : f25519_add(c, p1->y, p1->x);
197 : 1538 : f25519_add(d, p2->y, p2->x);
198 : 1538 : f25519_mul__distinct(b, c, d);
199 : :
200 : : /* C = T1 k T2 */
201 : 1538 : f25519_mul__distinct(d, p1->t, p2->t);
202 : 1538 : f25519_mul__distinct(c, d, ed25519_k);
203 : :
204 : : /* D = Z1 2 Z2 */
205 : 1538 : f25519_mul__distinct(d, p1->z, p2->z);
206 : 1538 : f25519_add(d, d, d);
207 : :
208 : : /* E = B - A */
209 : 1538 : f25519_sub(e, b, a);
210 : :
211 : : /* F = D - C */
212 : 1538 : f25519_sub(f, d, c);
213 : :
214 : : /* G = D + C */
215 : 1538 : f25519_add(g, d, c);
216 : :
217 : : /* H = B + A */
218 : 1538 : f25519_add(h, b, a);
219 : :
220 : : /* X3 = E F */
221 : 1538 : f25519_mul__distinct(r->x, e, f);
222 : :
223 : : /* Y3 = G H */
224 : 1538 : f25519_mul__distinct(r->y, g, h);
225 : :
226 : : /* T3 = E H */
227 : 1538 : f25519_mul__distinct(r->t, e, h);
228 : :
229 : : /* Z3 = F G */
230 : 1538 : f25519_mul__distinct(r->z, f, g);
231 : 1538 : }
232 : :
233 : 1536 : void ed25519_double(struct ed25519_pt *r, const struct ed25519_pt *p)
234 : : {
235 : : /* Explicit formulas database: dbl-2008-hwcd
236 : : *
237 : : * source 2008 Hisil--Wong--Carter--Dawson,
238 : : * http://eprint.iacr.org/2008/522, Section 3.3
239 : : * compute A = X1^2
240 : : * compute B = Y1^2
241 : : * compute C = 2 Z1^2
242 : : * compute D = a A
243 : : * compute E = (X1+Y1)^2-A-B
244 : : * compute G = D + B
245 : : * compute F = G - C
246 : : * compute H = D - B
247 : : * compute X3 = E F
248 : : * compute Y3 = G H
249 : : * compute T3 = E H
250 : : * compute Z3 = F G
251 : : */
252 : 1536 : uint8_t a[F25519_SIZE];
253 : 1536 : uint8_t b[F25519_SIZE];
254 : 1536 : uint8_t c[F25519_SIZE];
255 : 1536 : uint8_t e[F25519_SIZE];
256 : 1536 : uint8_t f[F25519_SIZE];
257 : 1536 : uint8_t g[F25519_SIZE];
258 : 1536 : uint8_t h[F25519_SIZE];
259 : :
260 : : /* A = X1^2 */
261 : 1536 : f25519_mul__distinct(a, p->x, p->x);
262 : :
263 : : /* B = Y1^2 */
264 : 1536 : f25519_mul__distinct(b, p->y, p->y);
265 : :
266 : : /* C = 2 Z1^2 */
267 : 1536 : f25519_mul__distinct(c, p->z, p->z);
268 : 1536 : f25519_add(c, c, c);
269 : :
270 : : /* D = a A (alter sign) */
271 : : /* E = (X1+Y1)^2-A-B */
272 : 1536 : f25519_add(f, p->x, p->y);
273 : 1536 : f25519_mul__distinct(e, f, f);
274 : 1536 : f25519_sub(e, e, a);
275 : 1536 : f25519_sub(e, e, b);
276 : :
277 : : /* G = D + B */
278 : 1536 : f25519_sub(g, b, a);
279 : :
280 : : /* F = G - C */
281 : 1536 : f25519_sub(f, g, c);
282 : :
283 : : /* H = D - B */
284 : 1536 : f25519_neg(h, b);
285 : 1536 : f25519_sub(h, h, a);
286 : :
287 : : /* X3 = E F */
288 : 1536 : f25519_mul__distinct(r->x, e, f);
289 : :
290 : : /* Y3 = G H */
291 : 1536 : f25519_mul__distinct(r->y, g, h);
292 : :
293 : : /* T3 = E H */
294 : 1536 : f25519_mul__distinct(r->t, e, h);
295 : :
296 : : /* Z3 = F G */
297 : 1536 : f25519_mul__distinct(r->z, f, g);
298 : 1536 : }
299 : :
300 : 6 : void ed25519_smult(struct ed25519_pt *r_out, const struct ed25519_pt *p,
301 : : const uint8_t *e)
302 : : {
303 : 6 : struct ed25519_pt r;
304 : 6 : int i;
305 : :
306 : 6 : ed25519_copy(&r, &ed25519_neutral);
307 : :
308 [ + + ]: 1548 : for (i = 255; i >= 0; i--) {
309 : 1536 : const uint8_t bit = (e[i >> 3] >> (i & 7)) & 1;
310 : 1536 : struct ed25519_pt s;
311 : :
312 : 1536 : ed25519_double(&r, &r);
313 : 1536 : ed25519_add(&s, &r, p);
314 : :
315 : 1536 : f25519_select(r.x, r.x, s.x, bit);
316 : 1536 : f25519_select(r.y, r.y, s.y, bit);
317 : 1536 : f25519_select(r.z, r.z, s.z, bit);
318 : 1536 : f25519_select(r.t, r.t, s.t, bit);
319 : : }
320 : :
321 : 6 : ed25519_copy(r_out, &r);
322 : 6 : }
323 : : #endif
|
