• source navigation  • diff markup  • identifier search  • freetext search  • 

Sources/usign/ed25519.c

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

This page was automatically generated by LXR 0.3.1.  •  OpenWrt