2 * Elliptic-curve crypto module for PuTTY
3 * Implements the three required curves, no optional curves
5 * NOTE: Only curves on prime field are handled by the maths functions
6 * in Weierstrass form using Jacobian co-ordinates.
8 * Montgomery form curves are supported for DH. (Curve25519)
10 * Edwards form curves are supported for DSA. (Ed25519)
16 * Elliptic curves in SSH are specified in RFC 5656:
17 * http://tools.ietf.org/html/rfc5656
19 * That specification delegates details of public key formatting and a
20 * lot of underlying mechanism to SEC 1:
21 * http://www.secg.org/sec1-v2.pdf
23 * Montgomery maths from:
24 * Handbook of elliptic and hyperelliptic curve cryptography, Chapter 13
25 * http://cs.ucsb.edu/~koc/ccs130h/2013/EllipticHyperelliptic-CohenFrey.pdf
28 * http://ed25519.cr.yp.to/ed25519-20110926.pdf
36 /* ----------------------------------------------------------------------
37 * Elliptic curve definitions
40 static int initialise_wcurve(struct ec_curve *curve, int bits, unsigned char *p,
41 unsigned char *a, unsigned char *b,
42 unsigned char *n, unsigned char *Gx,
45 int length = bits / 8;
46 if (bits % 8) ++length;
48 curve->type = EC_WEIERSTRASS;
50 curve->fieldBits = bits;
51 curve->p = bignum_from_bytes(p, length);
52 if (!curve->p) goto error;
54 /* Curve co-efficients */
55 curve->w.a = bignum_from_bytes(a, length);
56 if (!curve->w.a) goto error;
57 curve->w.b = bignum_from_bytes(b, length);
58 if (!curve->w.b) goto error;
60 /* Group order and generator */
61 curve->w.n = bignum_from_bytes(n, length);
62 if (!curve->w.n) goto error;
63 curve->w.G.x = bignum_from_bytes(Gx, length);
64 if (!curve->w.G.x) goto error;
65 curve->w.G.y = bignum_from_bytes(Gy, length);
66 if (!curve->w.G.y) goto error;
67 curve->w.G.curve = curve;
68 curve->w.G.infinity = 0;
72 if (curve->p) freebn(curve->p);
73 if (curve->w.a) freebn(curve->w.a);
74 if (curve->w.b) freebn(curve->w.b);
75 if (curve->w.n) freebn(curve->w.n);
76 if (curve->w.G.x) freebn(curve->w.G.x);
80 static int initialise_mcurve(struct ec_curve *curve, int bits, unsigned char *p,
81 unsigned char *a, unsigned char *b,
84 int length = bits / 8;
85 if (bits % 8) ++length;
87 curve->type = EC_MONTGOMERY;
89 curve->fieldBits = bits;
90 curve->p = bignum_from_bytes(p, length);
91 if (!curve->p) goto error;
93 /* Curve co-efficients */
94 curve->m.a = bignum_from_bytes(a, length);
95 if (!curve->m.a) goto error;
96 curve->m.b = bignum_from_bytes(b, length);
97 if (!curve->m.b) goto error;
100 curve->m.G.x = bignum_from_bytes(Gx, length);
101 if (!curve->m.G.x) goto error;
104 curve->m.G.curve = curve;
105 curve->m.G.infinity = 0;
109 if (curve->p) freebn(curve->p);
110 if (curve->m.a) freebn(curve->m.a);
111 if (curve->m.b) freebn(curve->m.b);
115 static int initialise_ecurve(struct ec_curve *curve, int bits, unsigned char *p,
116 unsigned char *l, unsigned char *d,
117 unsigned char *Bx, unsigned char *By)
119 int length = bits / 8;
120 if (bits % 8) ++length;
122 curve->type = EC_EDWARDS;
124 curve->fieldBits = bits;
125 curve->p = bignum_from_bytes(p, length);
126 if (!curve->p) goto error;
128 /* Curve co-efficients */
129 curve->e.l = bignum_from_bytes(l, length);
130 if (!curve->e.l) goto error;
131 curve->e.d = bignum_from_bytes(d, length);
132 if (!curve->e.d) goto error;
134 /* Group order and generator */
135 curve->e.B.x = bignum_from_bytes(Bx, length);
136 if (!curve->e.B.x) goto error;
137 curve->e.B.y = bignum_from_bytes(By, length);
138 if (!curve->e.B.y) goto error;
139 curve->e.B.curve = curve;
140 curve->e.B.infinity = 0;
144 if (curve->p) freebn(curve->p);
145 if (curve->e.l) freebn(curve->e.l);
146 if (curve->e.d) freebn(curve->e.d);
147 if (curve->e.B.x) freebn(curve->e.B.x);
151 unsigned char nistp256_oid[] = {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07};
152 int nistp256_oid_len = 8;
153 unsigned char nistp384_oid[] = {0x2b, 0x81, 0x04, 0x00, 0x22};
154 int nistp384_oid_len = 5;
155 unsigned char nistp521_oid[] = {0x2b, 0x81, 0x04, 0x00, 0x23};
156 int nistp521_oid_len = 5;
157 unsigned char curve25519_oid[] = {0x06, 0x0A, 0x2B, 0x06, 0x01, 0x04, 0x01, 0x97, 0x55, 0x01, 0x05, 0x01};
158 int curve25519_oid_len = 12;
160 struct ec_curve *ec_p256(void)
162 static struct ec_curve curve = { 0 };
163 static unsigned char initialised = 0;
167 unsigned char p[] = {
168 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
169 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
170 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
171 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff
173 unsigned char a[] = {
174 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
175 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
176 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
177 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc
179 unsigned char b[] = {
180 0x5a, 0xc6, 0x35, 0xd8, 0xaa, 0x3a, 0x93, 0xe7,
181 0xb3, 0xeb, 0xbd, 0x55, 0x76, 0x98, 0x86, 0xbc,
182 0x65, 0x1d, 0x06, 0xb0, 0xcc, 0x53, 0xb0, 0xf6,
183 0x3b, 0xce, 0x3c, 0x3e, 0x27, 0xd2, 0x60, 0x4b
185 unsigned char n[] = {
186 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
187 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
188 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
189 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51
191 unsigned char Gx[] = {
192 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47,
193 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2,
194 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0,
195 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96
197 unsigned char Gy[] = {
198 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b,
199 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e, 0x16,
200 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce,
201 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5
204 if (!initialise_wcurve(&curve, 256, p, a, b, n, Gx, Gy)) {
208 /* Now initialised, no need to do it again */
215 struct ec_curve *ec_p384(void)
217 static struct ec_curve curve = { 0 };
218 static unsigned char initialised = 0;
222 unsigned char p[] = {
223 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
224 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
225 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
226 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
227 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
228 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff
230 unsigned char a[] = {
231 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
232 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
233 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
234 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
235 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
236 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xfc
238 unsigned char b[] = {
239 0xb3, 0x31, 0x2f, 0xa7, 0xe2, 0x3e, 0xe7, 0xe4,
240 0x98, 0x8e, 0x05, 0x6b, 0xe3, 0xf8, 0x2d, 0x19,
241 0x18, 0x1d, 0x9c, 0x6e, 0xfe, 0x81, 0x41, 0x12,
242 0x03, 0x14, 0x08, 0x8f, 0x50, 0x13, 0x87, 0x5a,
243 0xc6, 0x56, 0x39, 0x8d, 0x8a, 0x2e, 0xd1, 0x9d,
244 0x2a, 0x85, 0xc8, 0xed, 0xd3, 0xec, 0x2a, 0xef
246 unsigned char n[] = {
247 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
248 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
249 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
250 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
251 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
252 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73
254 unsigned char Gx[] = {
255 0xaa, 0x87, 0xca, 0x22, 0xbe, 0x8b, 0x05, 0x37,
256 0x8e, 0xb1, 0xc7, 0x1e, 0xf3, 0x20, 0xad, 0x74,
257 0x6e, 0x1d, 0x3b, 0x62, 0x8b, 0xa7, 0x9b, 0x98,
258 0x59, 0xf7, 0x41, 0xe0, 0x82, 0x54, 0x2a, 0x38,
259 0x55, 0x02, 0xf2, 0x5d, 0xbf, 0x55, 0x29, 0x6c,
260 0x3a, 0x54, 0x5e, 0x38, 0x72, 0x76, 0x0a, 0xb7
262 unsigned char Gy[] = {
263 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f,
264 0x5d, 0x9e, 0x98, 0xbf, 0x92, 0x92, 0xdc, 0x29,
265 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c,
266 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0,
267 0x0a, 0x60, 0xb1, 0xce, 0x1d, 0x7e, 0x81, 0x9d,
268 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f
271 if (!initialise_wcurve(&curve, 384, p, a, b, n, Gx, Gy)) {
275 /* Now initialised, no need to do it again */
282 struct ec_curve *ec_p521(void)
284 static struct ec_curve curve = { 0 };
285 static unsigned char initialised = 0;
289 unsigned char p[] = {
290 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
291 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
292 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
293 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
294 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
295 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
296 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
297 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
300 unsigned char a[] = {
301 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
302 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
303 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
304 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
305 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
306 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
307 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
308 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
311 unsigned char b[] = {
312 0x00, 0x51, 0x95, 0x3e, 0xb9, 0x61, 0x8e, 0x1c,
313 0x9a, 0x1f, 0x92, 0x9a, 0x21, 0xa0, 0xb6, 0x85,
314 0x40, 0xee, 0xa2, 0xda, 0x72, 0x5b, 0x99, 0xb3,
315 0x15, 0xf3, 0xb8, 0xb4, 0x89, 0x91, 0x8e, 0xf1,
316 0x09, 0xe1, 0x56, 0x19, 0x39, 0x51, 0xec, 0x7e,
317 0x93, 0x7b, 0x16, 0x52, 0xc0, 0xbd, 0x3b, 0xb1,
318 0xbf, 0x07, 0x35, 0x73, 0xdf, 0x88, 0x3d, 0x2c,
319 0x34, 0xf1, 0xef, 0x45, 0x1f, 0xd4, 0x6b, 0x50,
322 unsigned char n[] = {
323 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
324 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
325 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
326 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
327 0xff, 0xfa, 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f,
328 0x96, 0x6b, 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09,
329 0xa5, 0xd0, 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c,
330 0x47, 0xae, 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38,
333 unsigned char Gx[] = {
334 0x00, 0xc6, 0x85, 0x8e, 0x06, 0xb7, 0x04, 0x04,
335 0xe9, 0xcd, 0x9e, 0x3e, 0xcb, 0x66, 0x23, 0x95,
336 0xb4, 0x42, 0x9c, 0x64, 0x81, 0x39, 0x05, 0x3f,
337 0xb5, 0x21, 0xf8, 0x28, 0xaf, 0x60, 0x6b, 0x4d,
338 0x3d, 0xba, 0xa1, 0x4b, 0x5e, 0x77, 0xef, 0xe7,
339 0x59, 0x28, 0xfe, 0x1d, 0xc1, 0x27, 0xa2, 0xff,
340 0xa8, 0xde, 0x33, 0x48, 0xb3, 0xc1, 0x85, 0x6a,
341 0x42, 0x9b, 0xf9, 0x7e, 0x7e, 0x31, 0xc2, 0xe5,
344 unsigned char Gy[] = {
345 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b,
346 0xc0, 0x04, 0x5c, 0x8a, 0x5f, 0xb4, 0x2c, 0x7d,
347 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b,
348 0x44, 0x68, 0x17, 0xaf, 0xbd, 0x17, 0x27, 0x3e,
349 0x66, 0x2c, 0x97, 0xee, 0x72, 0x99, 0x5e, 0xf4,
350 0x26, 0x40, 0xc5, 0x50, 0xb9, 0x01, 0x3f, 0xad,
351 0x07, 0x61, 0x35, 0x3c, 0x70, 0x86, 0xa2, 0x72,
352 0xc2, 0x40, 0x88, 0xbe, 0x94, 0x76, 0x9f, 0xd1,
356 if (!initialise_wcurve(&curve, 521, p, a, b, n, Gx, Gy)) {
360 /* Now initialised, no need to do it again */
367 struct ec_curve *ec_curve25519(void)
369 static struct ec_curve curve = { 0 };
370 static unsigned char initialised = 0;
374 unsigned char p[] = {
375 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
376 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
377 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
378 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
380 unsigned char a[] = {
381 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
382 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
383 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
384 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x6d, 0x06
386 unsigned char b[] = {
387 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
388 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
389 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
390 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
392 unsigned char gx[32] = {
393 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
394 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
395 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
396 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x09
399 if (!initialise_mcurve(&curve, 256, p, a, b, gx)) {
403 /* Now initialised, no need to do it again */
409 struct ec_curve *ec_ed25519(void)
411 static struct ec_curve curve = { 0 };
412 static unsigned char initialised = 0;
416 unsigned char q[] = {
417 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
418 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
419 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
420 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
422 unsigned char l[32] = {
423 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
424 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
425 0x14, 0xde, 0xf9, 0xde, 0xa2, 0xf7, 0x9c, 0xd6,
426 0x58, 0x12, 0x63, 0x1a, 0x5c, 0xf5, 0xd3, 0xed
428 unsigned char d[32] = {
429 0x52, 0x03, 0x6c, 0xee, 0x2b, 0x6f, 0xfe, 0x73,
430 0x8c, 0xc7, 0x40, 0x79, 0x77, 0x79, 0xe8, 0x98,
431 0x00, 0x70, 0x0a, 0x4d, 0x41, 0x41, 0xd8, 0xab,
432 0x75, 0xeb, 0x4d, 0xca, 0x13, 0x59, 0x78, 0xa3
434 unsigned char Bx[32] = {
435 0x21, 0x69, 0x36, 0xd3, 0xcd, 0x6e, 0x53, 0xfe,
436 0xc0, 0xa4, 0xe2, 0x31, 0xfd, 0xd6, 0xdc, 0x5c,
437 0x69, 0x2c, 0xc7, 0x60, 0x95, 0x25, 0xa7, 0xb2,
438 0xc9, 0x56, 0x2d, 0x60, 0x8f, 0x25, 0xd5, 0x1a
440 unsigned char By[32] = {
441 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
442 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
443 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
444 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x58
448 if (!initialise_ecurve(&curve, 256, q, l, d, Bx, By)) {
452 /* Now initialised, no need to do it again */
459 static struct ec_curve *ec_name_to_curve(const char *name, int len) {
460 if (len > 11 && !memcmp(name, "ecdsa-sha2-", 11)) {
463 } else if (len > 10 && !memcmp(name, "ecdh-sha2-", 10)) {
466 } else if (len == 11 && !memcmp(name, "ssh-ed25519", 11)) {
470 if (len == 8 && !memcmp(name, "nistp", 5)) {
472 if (!memcmp(name, "256", 3)) {
474 } else if (!memcmp(name, "384", 3)) {
476 } else if (!memcmp(name, "521", 3)) {
481 if (len == 28 && !memcmp(name, "curve25519-sha256@libssh.org", 28)) {
482 return ec_curve25519();
488 /* Type enumeration for specifying the curve name */
489 enum ec_name_type { EC_TYPE_DSA, EC_TYPE_DH, EC_TYPE_CURVE };
491 static int ec_curve_to_name(enum ec_name_type type, const struct ec_curve *curve,
492 unsigned char *name, int len) {
493 if (curve->type == EC_WEIERSTRASS) {
495 if (type == EC_TYPE_DSA) {
498 } else if (type == EC_TYPE_DH) {
506 /* Return length of string */
507 if (name == NULL) return length;
509 /* Not enough space for the name */
510 if (len < length) return 0;
512 /* Put the name in the buffer */
513 switch (curve->fieldBits) {
515 memcpy(name+loc, "256", 3);
518 memcpy(name+loc, "384", 3);
521 memcpy(name+loc, "521", 3);
527 if (type == EC_TYPE_DSA) {
528 memcpy(name, "ecdsa-sha2-nistp", 16);
529 } else if (type == EC_TYPE_DH) {
530 memcpy(name, "ecdh-sha2-nistp", 15);
532 memcpy(name, "nistp", 5);
536 } else if (curve->type == EC_EDWARDS) {
537 /* No DH for ed25519 - use Montgomery instead */
538 if (type == EC_TYPE_DH) return 0;
540 if (type == EC_TYPE_CURVE) {
541 /* Return length of string */
542 if (name == NULL) return 7;
544 /* Not enough space for the name */
545 if (len < 7) return 0;
547 /* Unknown curve field */
548 if (curve->fieldBits != 256) return 0;
550 memcpy(name, "ed25519", 7);
554 /* Return length of string */
555 if (name == NULL) return 11;
557 /* Not enough space for the name */
558 if (len < 11) return 0;
560 /* Unknown curve field */
561 if (curve->fieldBits != 256) return 0;
563 memcpy(name, "ssh-ed25519", 11);
567 /* No DSA for curve25519 */
568 if (type == EC_TYPE_DSA || type == EC_TYPE_CURVE) return 0;
570 /* Return length of string */
571 if (name == NULL) return 28;
573 /* Not enough space for the name */
574 if (len < 28) return 0;
576 /* Unknown curve field */
577 if (curve->fieldBits != 256) return 0;
579 memcpy(name, "curve25519-sha256@libssh.org", 28);
584 /* Return 1 if a is -3 % p, otherwise return 0
585 * This is used because there are some maths optimisations */
586 static int ec_aminus3(const struct ec_curve *curve)
591 if (curve->type != EC_WEIERSTRASS) {
595 _p = bignum_add_long(curve->w.a, 3);
598 ret = !bignum_cmp(curve->p, _p);
603 /* ----------------------------------------------------------------------
604 * Elliptic curve field maths
607 static Bignum ecf_add(const Bignum a, const Bignum b,
608 const struct ec_curve *curve)
610 Bignum a1, b1, ab, ret;
612 a1 = bigmod(a, curve->p);
613 if (!a1) return NULL;
614 b1 = bigmod(b, curve->p);
624 if (!ab) return NULL;
626 ret = bigmod(ab, curve->p);
632 static Bignum ecf_square(const Bignum a, const struct ec_curve *curve)
634 return modmul(a, a, curve->p);
637 static Bignum ecf_treble(const Bignum a, const struct ec_curve *curve)
642 tmp = bignum_lshift(a, 1);
643 if (!tmp) return NULL;
645 /* Add itself (i.e. treble) */
646 ret = bigadd(tmp, a);
650 while (ret != NULL && bignum_cmp(ret, curve->p) >= 0)
652 tmp = bigsub(ret, curve->p);
660 static Bignum ecf_double(const Bignum a, const struct ec_curve *curve)
662 Bignum ret = bignum_lshift(a, 1);
663 if (!ret) return NULL;
664 if (bignum_cmp(ret, curve->p) >= 0)
666 Bignum tmp = bigsub(ret, curve->p);
676 /* ----------------------------------------------------------------------
680 void ec_point_free(struct ec_point *point)
682 if (point == NULL) return;
684 if (point->x) freebn(point->x);
685 if (point->y) freebn(point->y);
686 if (point->z) freebn(point->z);
691 static struct ec_point *ec_point_new(const struct ec_curve *curve,
692 const Bignum x, const Bignum y, const Bignum z,
693 unsigned char infinity)
695 struct ec_point *point = snewn(1, struct ec_point);
696 point->curve = curve;
700 point->infinity = infinity ? 1 : 0;
704 static struct ec_point *ec_point_copy(const struct ec_point *a)
706 if (a == NULL) return NULL;
707 return ec_point_new(a->curve,
708 a->x ? copybn(a->x) : NULL,
709 a->y ? copybn(a->y) : NULL,
710 a->z ? copybn(a->z) : NULL,
714 static int ec_point_verify(const struct ec_point *a)
718 } else if (a->curve->type == EC_EDWARDS) {
719 /* Check y^2 - x^2 - 1 - d * x^2 * y^2 == 0 */
720 Bignum y2, x2, tmp, tmp2, tmp3;
723 y2 = ecf_square(a->y, a->curve);
727 x2 = ecf_square(a->x, a->curve);
732 tmp = modmul(a->curve->e.d, x2, a->curve->p);
738 tmp2 = modmul(tmp, y2, a->curve->p);
745 tmp = modsub(y2, x2, a->curve->p);
752 tmp3 = modsub(tmp, tmp2, a->curve->p);
758 ret = !bignum_cmp(tmp3, One);
761 } else if (a->curve->type == EC_WEIERSTRASS) {
762 /* Verify y^2 = x^3 + ax + b */
765 Bignum lhs = NULL, x3 = NULL, ax = NULL, x3ax = NULL, x3axm = NULL, x3axb = NULL, rhs = NULL;
767 Bignum Three = bignum_from_long(3);
768 if (!Three) return 0;
770 lhs = modmul(a->y, a->y, a->curve->p);
771 if (!lhs) goto error;
773 /* This uses montgomery multiplication to optimise */
774 x3 = modpow(a->x, Three, a->curve->p);
777 ax = modmul(a->curve->w.a, a->x, a->curve->p);
779 x3ax = bigadd(x3, ax);
780 if (!x3ax) goto error;
781 freebn(x3); x3 = NULL;
782 freebn(ax); ax = NULL;
783 x3axm = bigmod(x3ax, a->curve->p);
784 if (!x3axm) goto error;
785 freebn(x3ax); x3ax = NULL;
786 x3axb = bigadd(x3axm, a->curve->w.b);
787 if (!x3axb) goto error;
788 freebn(x3axm); x3axm = NULL;
789 rhs = bigmod(x3axb, a->curve->p);
790 if (!rhs) goto error;
793 ret = bignum_cmp(lhs, rhs) ? 0 : 1;
802 if (x3ax) freebn(x3ax);
803 if (x3axm) freebn(x3axm);
804 if (x3axb) freebn(x3axb);
805 if (lhs) freebn(lhs);
812 /* ----------------------------------------------------------------------
813 * Elliptic curve point maths
816 /* Returns 1 on success and 0 on memory error */
817 static int ecp_normalise(struct ec_point *a)
825 /* Point is at infinity - i.e. normalised */
829 if (a->curve->type == EC_WEIERSTRASS) {
830 /* In Jacobian Coordinates the triple (X, Y, Z) represents
831 the affine point (X / Z^2, Y / Z^3) */
833 Bignum Z2, Z2inv, Z3, Z3inv, tx, ty;
835 if (!a->x || !a->y) {
836 /* No point defined */
839 /* Already normalised */
843 Z2 = ecf_square(a->z, a->curve);
847 Z2inv = modinv(Z2, a->curve->p);
852 tx = modmul(a->x, Z2inv, a->curve->p);
859 Z3 = modmul(Z2, a->z, a->curve->p);
865 Z3inv = modinv(Z3, a->curve->p);
871 ty = modmul(a->y, Z3inv, a->curve->p);
885 } else if (a->curve->type == EC_MONTGOMERY) {
886 /* In Montgomery (X : Z) represents the x co-ord (X / Z, ?) */
891 /* No point defined */
894 /* Already normalised */
898 tmp = modinv(a->z, a->curve->p);
902 tmp2 = modmul(a->x, tmp, a->curve->p);
913 } else if (a->curve->type == EC_EDWARDS) {
914 /* Always normalised */
921 static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3)
923 Bignum S, M, outx, outy, outz;
925 if (bignum_cmp(a->y, Zero) == 0)
928 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
933 Bignum Y2, XY2, _2XY2;
935 Y2 = ecf_square(a->y, a->curve);
939 XY2 = modmul(a->x, Y2, a->curve->p);
945 _2XY2 = ecf_double(XY2, a->curve);
950 S = ecf_double(_2XY2, a->curve);
957 /* Faster calculation if a = -3 */
959 /* if a = -3, then M can also be calculated as M = 3*(X + Z^2)*(X - Z^2) */
960 Bignum Z2, XpZ2, XmZ2, second;
965 Z2 = ecf_square(a->z, a->curve);
972 XpZ2 = ecf_add(a->x, Z2, a->curve);
978 XmZ2 = modsub(a->x, Z2, a->curve->p);
986 second = modmul(XpZ2, XmZ2, a->curve->p);
994 M = ecf_treble(second, a->curve);
1001 /* M = 3*X^2 + a*Z^4 */
1002 Bignum _3X2, X2, aZ4;
1005 aZ4 = copybn(a->curve->w.a);
1009 Z2 = ecf_square(a->z, a->curve);
1014 Z4 = ecf_square(Z2, a->curve);
1020 aZ4 = modmul(a->curve->w.a, Z4, a->curve->p);
1028 X2 = modmul(a->x, a->x, a->curve->p);
1034 _3X2 = ecf_treble(X2, a->curve);
1041 M = ecf_add(_3X2, aZ4, a->curve);
1050 /* X' = M^2 - 2*S */
1054 M2 = ecf_square(M, a->curve);
1061 _2S = ecf_double(S, a->curve);
1069 outx = modsub(M2, _2S, a->curve->p);
1079 /* Y' = M*(S - X') - 8*Y^4 */
1081 Bignum SX, MSX, Eight, Y2, Y4, _8Y4;
1083 SX = modsub(S, outx, a->curve->p);
1090 MSX = modmul(M, SX, a->curve->p);
1097 Y2 = ecf_square(a->y, a->curve);
1103 Y4 = ecf_square(Y2, a->curve);
1110 Eight = bignum_from_long(8);
1117 _8Y4 = modmul(Eight, Y4, a->curve->p);
1125 outy = modsub(MSX, _8Y4, a->curve->p);
1141 YZ = modmul(a->y, a->z, a->curve->p);
1149 outz = ecf_double(YZ, a->curve);
1158 return ec_point_new(a->curve, outx, outy, outz, 0);
1161 static struct ec_point *ecp_doublem(const struct ec_point *a)
1163 Bignum z, outx, outz, xpz, xmz;
1170 /* 4xz = (x + z)^2 - (x - z)^2 */
1174 tmp = ecf_add(a->x, z, a->curve);
1178 xpz = ecf_square(tmp, a->curve);
1184 tmp = modsub(a->x, z, a->curve->p);
1189 xmz = ecf_square(tmp, a->curve);
1197 /* outx = (x + z)^2 * (x - z)^2 */
1198 outx = modmul(xpz, xmz, a->curve->p);
1205 /* outz = 4xz * ((x - z)^2 + ((A + 2) / 4)*4xz) */
1207 Bignum _4xz, tmp, tmp2, tmp3;
1209 tmp = bignum_from_long(2);
1216 tmp2 = ecf_add(a->curve->m.a, tmp, a->curve);
1225 _4xz = modsub(xpz, xmz, a->curve->p);
1233 tmp = modmul(tmp2, _4xz, a->curve->p);
1242 tmp2 = bignum_from_long(4);
1250 tmp3 = modinv(tmp2, a->curve->p);
1259 tmp2 = modmul(tmp, tmp3, a->curve->p);
1269 tmp = ecf_add(xmz, tmp2, a->curve);
1277 outz = modmul(_4xz, tmp, a->curve->p);
1286 return ec_point_new(a->curve, outx, NULL, outz, 0);
1289 /* Forward declaration for Edwards curve doubling */
1290 static struct ec_point *ecp_add(const struct ec_point *a,
1291 const struct ec_point *b,
1294 static struct ec_point *ecp_double(const struct ec_point *a, const int aminus3)
1299 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
1302 if (a->curve->type == EC_EDWARDS)
1304 return ecp_add(a, a, aminus3);
1306 else if (a->curve->type == EC_WEIERSTRASS)
1308 return ecp_doublew(a, aminus3);
1312 return ecp_doublem(a);
1316 static struct ec_point *ecp_addw(const struct ec_point *a,
1317 const struct ec_point *b,
1320 Bignum U1, U2, S1, S2, outx, outy, outz;
1327 Z2 = ecf_square(b->z, a->curve);
1331 U1 = modmul(a->x, Z2, a->curve->p);
1336 Z3 = modmul(Z2, b->z, a->curve->p);
1342 S1 = modmul(a->y, Z3, a->curve->p);
1365 Z2 = ecf_square(a->z, b->curve);
1371 U2 = modmul(b->x, Z2, b->curve->p);
1378 Z3 = modmul(Z2, a->z, b->curve->p);
1386 S2 = modmul(b->y, Z3, b->curve->p);
1410 /* Check if multiplying by self */
1411 if (bignum_cmp(U1, U2) == 0)
1415 if (bignum_cmp(S1, S2) == 0)
1419 return ecp_double(a, aminus3);
1426 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
1431 Bignum H, R, UH2, H3;
1434 H = modsub(U2, U1, a->curve->p);
1444 R = modsub(S2, S1, a->curve->p);
1453 /* X3 = R^2 - H^3 - 2*U1*H^2 */
1455 Bignum R2, H2, _2UH2, first;
1457 H2 = ecf_square(H, a->curve);
1465 UH2 = modmul(U1, H2, a->curve->p);
1474 H3 = modmul(H2, H, a->curve->p);
1483 R2 = ecf_square(R, a->curve);
1492 _2UH2 = ecf_double(UH2, a->curve);
1502 first = modsub(R2, H3, a->curve->p);
1513 outx = modsub(first, _2UH2, a->curve->p);
1526 /* Y3 = R*(U1*H^2 - X3) - S1*H^3 */
1528 Bignum RUH2mX, UH2mX, SH3;
1530 UH2mX = modsub(UH2, outx, a->curve->p);
1540 RUH2mX = modmul(R, UH2mX, a->curve->p);
1550 SH3 = modmul(S1, H3, a->curve->p);
1560 outy = modsub(RUH2mX, SH3, a->curve->p);
1574 ZZ = modmul(a->z, b->z, a->curve->p);
1581 outz = modmul(H, ZZ, a->curve->p);
1590 outz = modmul(H, a->z, a->curve->p);
1598 outz = modmul(H, b->z, a->curve->p);
1610 return ec_point_new(a->curve, outx, outy, outz, 0);
1613 static struct ec_point *ecp_addm(const struct ec_point *a,
1614 const struct ec_point *b,
1615 const struct ec_point *base)
1617 Bignum outx, outz, az, bz;
1628 /* a-b is maintained at 1 due to Montgomery ladder implementation */
1629 /* Xa+b = Za-b * ((Xa - Za)*(Xb + Zb) + (Xa + Za)*(Xb - Zb))^2 */
1630 /* Za+b = Xa-b * ((Xa - Za)*(Xb + Zb) - (Xa + Za)*(Xb - Zb))^2 */
1632 Bignum tmp, tmp2, tmp3, tmp4;
1634 /* (Xa + Za) * (Xb - Zb) */
1635 tmp = ecf_add(a->x, az, a->curve);
1639 tmp2 = modsub(b->x, bz, a->curve->p);
1644 tmp3 = modmul(tmp, tmp2, a->curve->p);
1651 /* (Xa - Za) * (Xb + Zb) */
1652 tmp = modsub(a->x, az, a->curve->p);
1657 tmp2 = ecf_add(b->x, bz, a->curve);
1663 tmp4 = modmul(tmp, tmp2, a->curve->p);
1671 tmp = ecf_add(tmp3, tmp4, a->curve);
1677 outx = ecf_square(tmp, a->curve);
1685 tmp = modsub(tmp3, tmp4, a->curve->p);
1692 tmp2 = ecf_square(tmp, a->curve);
1698 outz = modmul(base->x, tmp2, a->curve->p);
1706 return ec_point_new(a->curve, outx, NULL, outz, 0);
1709 static struct ec_point *ecp_adde(const struct ec_point *a,
1710 const struct ec_point *b)
1712 Bignum outx, outy, dmul;
1714 /* outx = (a->x * b->y + b->x * a->y) /
1715 * (1 + a->curve->e.d * a->x * b->x * a->y * b->y) */
1717 Bignum tmp, tmp2, tmp3, tmp4;
1719 tmp = modmul(a->x, b->y, a->curve->p);
1724 tmp2 = modmul(b->x, a->y, a->curve->p);
1730 tmp3 = ecf_add(tmp, tmp2, a->curve);
1738 tmp4 = modmul(tmp, tmp2, a->curve->p);
1746 dmul = modmul(a->curve->e.d, tmp4, a->curve->p);
1753 tmp = ecf_add(One, dmul, a->curve);
1760 tmp2 = modinv(tmp, a->curve->p);
1769 outx = modmul(tmp3, tmp2, a->curve->p);
1779 /* outy = (a->y * b->y + a->x * b->x) /
1780 * (1 - a->curve->e.d * a->x * b->x * a->y * b->y) */
1782 Bignum tmp, tmp2, tmp3, tmp4;
1784 tmp = modsub(One, dmul, a->curve->p);
1792 tmp2 = modinv(tmp, a->curve->p);
1800 tmp = modmul(a->y, b->y, a->curve->p);
1807 tmp3 = modmul(a->x, b->x, a->curve->p);
1815 tmp4 = ecf_add(tmp, tmp3, a->curve);
1825 outy = modmul(tmp4, tmp2, a->curve->p);
1835 return ec_point_new(a->curve, outx, outy, NULL, 0);
1838 static struct ec_point *ecp_add(const struct ec_point *a,
1839 const struct ec_point *b,
1842 if (a->curve != b->curve) {
1846 /* Check if multiplying by infinity */
1847 if (a->infinity) return ec_point_copy(b);
1848 if (b->infinity) return ec_point_copy(a);
1850 if (a->curve->type == EC_EDWARDS)
1852 return ecp_adde(a, b);
1855 if (a->curve->type == EC_WEIERSTRASS)
1857 return ecp_addw(a, b, aminus3);
1863 static struct ec_point *ecp_mul_(const struct ec_point *a, const Bignum b, int aminus3)
1865 struct ec_point *A, *ret;
1868 A = ec_point_copy(a);
1869 ret = ec_point_new(a->curve, NULL, NULL, NULL, 1);
1871 bits = bignum_bitcount(b);
1872 for (i = 0; ret != NULL && A != NULL && i < bits; ++i)
1874 if (bignum_bit(b, i))
1876 struct ec_point *tmp = ecp_add(ret, A, aminus3);
1882 struct ec_point *tmp = ecp_double(A, aminus3);
1898 static struct ec_point *ecp_mulw(const struct ec_point *a, const Bignum b)
1900 struct ec_point *ret = ecp_mul_(a, b, ec_aminus3(a->curve));
1902 if (!ecp_normalise(ret)) {
1910 static struct ec_point *ecp_mule(const struct ec_point *a, const Bignum b)
1913 struct ec_point *ret;
1915 ret = ec_point_new(a->curve, NULL, NULL, NULL, 1);
1917 for (i = bignum_bitcount(b); i >= 0 && ret; --i)
1920 struct ec_point *tmp = ecp_double(ret, 0);
1924 if (ret && bignum_bit(b, i))
1926 struct ec_point *tmp = ecp_add(ret, a, 0);
1935 static struct ec_point *ecp_mulm(const struct ec_point *p, const Bignum n)
1937 struct ec_point *P1, *P2;
1940 /* P1 <- P and P2 <- [2]P */
1941 P2 = ecp_double(p, 0);
1945 P1 = ec_point_copy(p);
1951 /* for i = bits − 2 down to 0 */
1952 bits = bignum_bitcount(n);
1953 for (i = bits - 2; P1 != NULL && P2 != NULL && i >= 0; --i)
1955 if (!bignum_bit(n, i))
1958 struct ec_point *tmp = ecp_addm(P1, P2, p);
1963 tmp = ecp_double(P1, 0);
1970 struct ec_point *tmp = ecp_addm(P1, P2, p);
1975 tmp = ecp_double(P2, 0);
1982 if (P1) ec_point_free(P1);
1988 if (!ecp_normalise(P1)) {
1996 /* Not static because it is used by sshecdsag.c to generate a new key */
1997 struct ec_point *ecp_mul(const struct ec_point *a, const Bignum b)
1999 if (a->curve->type == EC_WEIERSTRASS) {
2000 return ecp_mulw(a, b);
2001 } else if (a->curve->type == EC_EDWARDS) {
2002 return ecp_mule(a, b);
2004 return ecp_mulm(a, b);
2008 static struct ec_point *ecp_summul(const Bignum a, const Bignum b,
2009 const struct ec_point *point)
2011 struct ec_point *aG, *bP, *ret;
2014 if (point->curve->type != EC_WEIERSTRASS) {
2018 aminus3 = ec_aminus3(point->curve);
2020 aG = ecp_mul_(&point->curve->w.G, a, aminus3);
2021 if (!aG) return NULL;
2022 bP = ecp_mul_(point, b, aminus3);
2028 ret = ecp_add(aG, bP, aminus3);
2033 if (!ecp_normalise(ret)) {
2040 static Bignum *ecp_edx(const struct ec_curve *curve, const Bignum y)
2042 /* Get the x value on the given Edwards curve for a given y */
2045 /* xx = (y^2 - 1) / (d * y^2 + 1) */
2047 Bignum tmp, tmp2, tmp3;
2049 tmp = ecf_square(y, curve);
2053 tmp2 = modmul(curve->e.d, tmp, curve->p);
2058 tmp3 = ecf_add(tmp2, One, curve);
2064 tmp2 = modinv(tmp3, curve->p);
2071 tmp3 = modsub(tmp, One, curve->p);
2077 xx = modmul(tmp3, tmp2, curve->p);
2085 /* x = xx^((p + 3) / 8) */
2089 tmp = bignum_add_long(curve->p, 3);
2094 tmp2 = bignum_rshift(tmp, 3);
2100 x = modpow(xx, tmp2, curve->p);
2108 /* if x^2 - xx != 0 then x = x*(2^((p - 1) / 4)) */
2112 tmp = ecf_square(x, curve);
2118 tmp2 = modsub(tmp, xx, curve->p);
2125 if (bignum_cmp(tmp2, Zero)) {
2130 tmp = modsub(curve->p, One, curve->p);
2135 tmp2 = bignum_rshift(tmp, 2);
2141 tmp = bignum_from_long(2);
2147 tmp3 = modpow(tmp, tmp2, curve->p);
2155 tmp = modmul(x, tmp3, curve->p);
2167 /* if x % 2 != 0 then x = p - x */
2168 if (bignum_bit(x, 0)) {
2169 Bignum tmp = modsub(curve->p, x, curve->p);
2180 /* ----------------------------------------------------------------------
2181 * Public point from private
2184 struct ec_point *ec_public(const Bignum privateKey, const struct ec_curve *curve)
2186 if (curve->type == EC_WEIERSTRASS) {
2187 return ecp_mul(&curve->w.G, privateKey);
2188 } else if (curve->type == EC_EDWARDS) {
2189 /* hash = H(sk) (where hash creates 2 * fieldBits)
2191 * a = 2^(b-2) + SUM(2^i * h_i) for i = 2 -> b-2
2193 struct ec_point *ret;
2194 unsigned char hash[512/8];
2200 keylen = curve->fieldBits / 8;
2201 for (i = 0; i < keylen; ++i) {
2202 unsigned char b = bignum_byte(privateKey, i);
2203 SHA512_Bytes(&s, &b, 1);
2205 SHA512_Final(&s, hash);
2207 /* The second part is simply turning the hash into a Bignum,
2208 * however the 2^(b-2) bit *must* be set, and the bottom 3
2209 * bits *must* not be */
2210 hash[0] &= 0xf8; /* Unset bottom 3 bits (if set) */
2211 hash[31] &= 0x7f; /* Unset above (b-2) */
2212 hash[31] |= 0x40; /* Set 2^(b-2) */
2213 /* Chop off the top part and convert to int */
2214 a = bignum_from_bytes_le(hash, 32);
2219 ret = ecp_mul(&curve->e.B, a);
2227 /* ----------------------------------------------------------------------
2228 * Basic sign and verify routines
2231 static int _ecdsa_verify(const struct ec_point *publicKey,
2232 const unsigned char *data, const int dataLen,
2233 const Bignum r, const Bignum s)
2239 if (publicKey->curve->type != EC_WEIERSTRASS) {
2244 if (bignum_cmp(r, Zero) == 0 || bignum_cmp(r, publicKey->curve->w.n) >= 0
2245 || bignum_cmp(s, Zero) == 0 || bignum_cmp(s, publicKey->curve->w.n) >= 0)
2250 /* z = left most bitlen(curve->n) of data */
2251 z = bignum_from_bytes(data, dataLen);
2253 n_bits = bignum_bitcount(publicKey->curve->w.n);
2254 z_bits = bignum_bitcount(z);
2255 if (z_bits > n_bits)
2257 Bignum tmp = bignum_rshift(z, z_bits - n_bits);
2263 /* Ensure z in range of n */
2265 Bignum tmp = bigmod(z, publicKey->curve->w.n);
2271 /* Calculate signature */
2273 Bignum w, x, u1, u2;
2274 struct ec_point *tmp;
2276 w = modinv(s, publicKey->curve->w.n);
2281 u1 = modmul(z, w, publicKey->curve->w.n);
2287 u2 = modmul(r, w, publicKey->curve->w.n);
2295 tmp = ecp_summul(u1, u2, publicKey);
2303 x = bigmod(tmp->x, publicKey->curve->w.n);
2310 valid = (bignum_cmp(r, x) == 0) ? 1 : 0;
2319 static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve,
2320 const unsigned char *data, const int dataLen,
2321 Bignum *r, Bignum *s)
2323 unsigned char digest[20];
2326 struct ec_point *kG;
2331 if (curve->type != EC_WEIERSTRASS) {
2335 /* z = left most bitlen(curve->n) of data */
2336 z = bignum_from_bytes(data, dataLen);
2338 n_bits = bignum_bitcount(curve->w.n);
2339 z_bits = bignum_bitcount(z);
2340 if (z_bits > n_bits)
2343 tmp = bignum_rshift(z, z_bits - n_bits);
2349 /* Generate k between 1 and curve->n, using the same deterministic
2350 * k generation system we use for conventional DSA. */
2351 SHA_Simple(data, dataLen, digest);
2352 k = dss_gen_k("ECDSA deterministic k generator", curve->w.n, privateKey,
2353 digest, sizeof(digest));
2356 kG = ecp_mul(&curve->w.G, k);
2363 /* r = kG.x mod n */
2364 *r = bigmod(kG->x, curve->w.n);
2372 /* s = (z + r * priv)/k mod n */
2374 Bignum rPriv, zMod, first, firstMod, kInv;
2375 rPriv = modmul(*r, privateKey, curve->w.n);
2382 zMod = bigmod(z, curve->w.n);
2390 first = bigadd(rPriv, zMod);
2398 firstMod = bigmod(first, curve->w.n);
2405 kInv = modinv(k, curve->w.n);
2412 *s = modmul(firstMod, kInv, curve->w.n);
2422 /* ----------------------------------------------------------------------
2426 static void getstring(const char **data, int *datalen,
2427 const char **p, int *length)
2432 *length = toint(GET_32BIT(*data));
2437 if (*datalen < *length)
2441 *datalen -= *length;
2444 static Bignum getmp(const char **data, int *datalen)
2449 getstring(data, datalen, &p, &length);
2453 return NULL; /* negative mp */
2454 return bignum_from_bytes((unsigned char *)p, length);
2457 static Bignum getmp_le(const char **data, int *datalen)
2462 getstring(data, datalen, &p, &length);
2465 return bignum_from_bytes_le((const unsigned char *)p, length);
2468 static int decodepoint_ed(const char *p, int length, struct ec_point *point)
2470 /* Got some conversion to do, first read in the y co-ord */
2473 point->y = bignum_from_bytes_le((const unsigned char*)p, length);
2477 if ((unsigned)bignum_bitcount(point->y) > point->curve->fieldBits) {
2482 /* Read x bit and then reset it */
2483 negative = bignum_bit(point->y, point->curve->fieldBits - 1);
2484 bignum_set_bit(point->y, point->curve->fieldBits - 1, 0);
2486 /* Get the x from the y */
2487 point->x = ecp_edx(point->curve, point->y);
2494 Bignum tmp = modsub(point->curve->p, point->x, point->curve->p);
2504 /* Verify the point is on the curve */
2505 if (!ec_point_verify(point)) {
2516 static int decodepoint(const char *p, int length, struct ec_point *point)
2518 if (point->curve->type == EC_EDWARDS) {
2519 return decodepoint_ed(p, length, point);
2522 if (length < 1 || p[0] != 0x04) /* Only support uncompressed point */
2524 /* Skip compression flag */
2527 /* The two values must be equal length */
2528 if (length % 2 != 0) {
2534 length = length / 2;
2535 point->x = bignum_from_bytes((const unsigned char *)p, length);
2536 if (!point->x) return 0;
2538 point->y = bignum_from_bytes((const unsigned char *)p, length);
2546 /* Verify the point is on the curve */
2547 if (!ec_point_verify(point)) {
2558 static int getmppoint(const char **data, int *datalen, struct ec_point *point)
2563 getstring(data, datalen, &p, &length);
2565 return decodepoint(p, length, point);
2568 /* ----------------------------------------------------------------------
2569 * Exposed ECDSA interface
2572 static void ecdsa_freekey(void *key)
2574 struct ec_key *ec = (struct ec_key *) key;
2577 if (ec->publicKey.x)
2578 freebn(ec->publicKey.x);
2579 if (ec->publicKey.y)
2580 freebn(ec->publicKey.y);
2581 if (ec->publicKey.z)
2582 freebn(ec->publicKey.z);
2584 freebn(ec->privateKey);
2588 static void *ecdsa_newkey(const char *data, int len)
2593 struct ec_curve *curve;
2595 getstring(&data, &len, &p, &slen);
2600 curve = ec_name_to_curve(p, slen);
2601 if (!curve) return NULL;
2603 if (curve->type != EC_WEIERSTRASS && curve->type != EC_EDWARDS) {
2607 /* Curve name is duplicated for Weierstrass form */
2608 if (curve->type == EC_WEIERSTRASS) {
2609 getstring(&data, &len, &p, &slen);
2610 if (curve != ec_name_to_curve(p, slen)) return NULL;
2613 ec = snew(struct ec_key);
2615 ec->publicKey.curve = curve;
2616 ec->publicKey.infinity = 0;
2617 ec->publicKey.x = NULL;
2618 ec->publicKey.y = NULL;
2619 ec->publicKey.z = NULL;
2620 if (!getmppoint(&data, &len, &ec->publicKey)) {
2624 ec->privateKey = NULL;
2626 if (!ec->publicKey.x || !ec->publicKey.y ||
2627 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
2628 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
2637 static char *ecdsa_fmtkey(void *key)
2639 struct ec_key *ec = (struct ec_key *) key;
2641 int len, i, pos, nibbles;
2642 static const char hex[] = "0123456789abcdef";
2643 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
2646 pos = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0);
2647 if (pos == 0) return NULL;
2649 len = 4 + 2 + 1; /* 2 x "0x", punctuation, \0 */
2650 len += pos; /* Curve name */
2651 len += 4 * (bignum_bitcount(ec->publicKey.x) + 15) / 16;
2652 len += 4 * (bignum_bitcount(ec->publicKey.y) + 15) / 16;
2653 p = snewn(len, char);
2655 pos = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, (unsigned char*)p, pos);
2656 pos += sprintf(p + pos, ",0x");
2657 nibbles = (3 + bignum_bitcount(ec->publicKey.x)) / 4;
2660 for (i = nibbles; i--;) {
2662 hex[(bignum_byte(ec->publicKey.x, i / 2) >> (4 * (i % 2))) & 0xF];
2664 pos += sprintf(p + pos, ",0x");
2665 nibbles = (3 + bignum_bitcount(ec->publicKey.y)) / 4;
2668 for (i = nibbles; i--;) {
2670 hex[(bignum_byte(ec->publicKey.y, i / 2) >> (4 * (i % 2))) & 0xF];
2676 static unsigned char *ecdsa_public_blob(void *key, int *len)
2678 struct ec_key *ec = (struct ec_key *) key;
2679 int pointlen, bloblen, fullnamelen, namelen;
2681 unsigned char *blob, *p;
2683 if (ec->publicKey.curve->type == EC_EDWARDS) {
2684 /* Edwards compressed form "ssh-ed25519" point y[:-1] + x[0:1] */
2685 fullnamelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0);
2686 if (fullnamelen == 0) return NULL;
2688 pointlen = ec->publicKey.curve->fieldBits / 8;
2690 /* Can't handle this in our loop */
2691 if (pointlen < 2) return NULL;
2693 bloblen = 4 + fullnamelen + 4 + pointlen;
2694 blob = snewn(bloblen, unsigned char);
2695 if (!blob) return NULL;
2698 PUT_32BIT(p, fullnamelen);
2700 p += ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, p, fullnamelen);
2701 PUT_32BIT(p, pointlen);
2704 /* Unset last bit of y and set first bit of x in its place */
2705 for (i = 0; i < pointlen - 1; ++i) {
2706 *p++ = bignum_byte(ec->publicKey.y, i);
2708 /* Unset last bit of y and set first bit of x in its place */
2709 *p = bignum_byte(ec->publicKey.y, i) & 0x7f;
2710 *p++ |= bignum_bit(ec->publicKey.x, 0) << 7;
2711 } else if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2712 fullnamelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0);
2713 if (fullnamelen == 0) return NULL;
2714 namelen = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0);
2715 if (namelen == 0) return NULL;
2717 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2720 * string "ecdsa-sha2-<name>", string "<name>", 0x04 point x, y.
2722 bloblen = 4 + fullnamelen + 4 + namelen + 4 + 1 + (pointlen * 2);
2723 blob = snewn(bloblen, unsigned char);
2726 PUT_32BIT(p, fullnamelen);
2728 p += ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, p, fullnamelen);
2729 PUT_32BIT(p, namelen);
2731 p += ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, p, namelen);
2732 PUT_32BIT(p, (2 * pointlen) + 1);
2735 for (i = pointlen; i--;) {
2736 *p++ = bignum_byte(ec->publicKey.x, i);
2738 for (i = pointlen; i--;) {
2739 *p++ = bignum_byte(ec->publicKey.y, i);
2745 assert(p == blob + bloblen);
2751 static unsigned char *ecdsa_private_blob(void *key, int *len)
2753 struct ec_key *ec = (struct ec_key *) key;
2754 int keylen, bloblen;
2756 unsigned char *blob, *p;
2758 if (!ec->privateKey) return NULL;
2760 if (ec->publicKey.curve->type == EC_EDWARDS) {
2762 keylen = (bignum_bitcount(ec->privateKey) + 7) / 8;
2765 keylen = (bignum_bitcount(ec->privateKey) + 8) / 8;
2769 * mpint privateKey. Total 4 + keylen.
2771 bloblen = 4 + keylen;
2772 blob = snewn(bloblen, unsigned char);
2775 PUT_32BIT(p, keylen);
2777 if (ec->publicKey.curve->type == EC_EDWARDS) {
2779 for (i = 0; i < keylen; ++i)
2780 *p++ = bignum_byte(ec->privateKey, i);
2782 for (i = keylen; i--;)
2783 *p++ = bignum_byte(ec->privateKey, i);
2786 assert(p == blob + bloblen);
2791 static void *ecdsa_createkey(const unsigned char *pub_blob, int pub_len,
2792 const unsigned char *priv_blob, int priv_len)
2795 struct ec_point *publicKey;
2796 const char *pb = (const char *) priv_blob;
2798 ec = (struct ec_key*)ecdsa_newkey((const char *) pub_blob, pub_len);
2803 if (ec->publicKey.curve->type != EC_WEIERSTRASS
2804 && ec->publicKey.curve->type != EC_EDWARDS) {
2809 if (ec->publicKey.curve->type == EC_EDWARDS) {
2810 ec->privateKey = getmp_le(&pb, &priv_len);
2812 ec->privateKey = getmp(&pb, &priv_len);
2814 if (!ec->privateKey) {
2819 /* Check that private key generates public key */
2820 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
2823 bignum_cmp(publicKey->x, ec->publicKey.x) ||
2824 bignum_cmp(publicKey->y, ec->publicKey.y))
2829 ec_point_free(publicKey);
2834 static void *ed25519_openssh_createkey(const unsigned char **blob, int *len)
2837 struct ec_point *publicKey;
2841 getstring((const char**)blob, len, &p, &plen);
2847 ec = snew(struct ec_key);
2853 ec->publicKey.curve = ec_ed25519();
2854 ec->publicKey.infinity = 0;
2855 ec->privateKey = NULL;
2856 ec->publicKey.x = NULL;
2857 ec->publicKey.z = NULL;
2858 ec->publicKey.y = NULL;
2860 if (!decodepoint_ed(p, plen, &ec->publicKey))
2866 getstring((const char**)blob, len, &q, &qlen);
2872 ec->privateKey = bignum_from_bytes_le((const unsigned char *)q, 32);
2873 if (!ec->privateKey) {
2878 /* Check that private key generates public key */
2879 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
2882 bignum_cmp(publicKey->x, ec->publicKey.x) ||
2883 bignum_cmp(publicKey->y, ec->publicKey.y))
2888 ec_point_free(publicKey);
2890 /* The OpenSSH format for ed25519 private keys also for some
2891 * reason encodes an extra copy of the public key in the second
2892 * half of the secret-key string. Check that that's present and
2893 * correct as well, otherwise the key we think we've imported
2894 * won't behave identically to the way OpenSSH would have treated
2896 if (plen != 32 || 0 != memcmp(q + 32, p, 32)) {
2904 static int ed25519_openssh_fmtkey(void *key, unsigned char *blob, int len)
2906 struct ec_key *ec = (struct ec_key *) key;
2913 if (ec->publicKey.curve->type != EC_EDWARDS) {
2917 pointlen = (bignum_bitcount(ec->publicKey.y) + 7) / 8;
2918 keylen = (bignum_bitcount(ec->privateKey) + 7) / 8;
2919 bloblen = 4 + pointlen + 4 + keylen + pointlen;
2924 /* Encode the public point */
2925 PUT_32BIT(blob, pointlen);
2928 for (i = 0; i < pointlen - 1; ++i) {
2929 *blob++ = bignum_byte(ec->publicKey.y, i);
2931 /* Unset last bit of y and set first bit of x in its place */
2932 *blob = bignum_byte(ec->publicKey.y, i) & 0x7f;
2933 *blob++ |= bignum_bit(ec->publicKey.x, 0) << 7;
2935 PUT_32BIT(blob, keylen + pointlen);
2937 for (i = 0; i < keylen; ++i) {
2938 *blob++ = bignum_byte(ec->privateKey, i);
2940 /* Now encode an extra copy of the public point as the second half
2941 * of the private key string, as the OpenSSH format for some
2942 * reason requires */
2943 for (i = 0; i < pointlen - 1; ++i) {
2944 *blob++ = bignum_byte(ec->publicKey.y, i);
2946 /* Unset last bit of y and set first bit of x in its place */
2947 *blob = bignum_byte(ec->publicKey.y, i) & 0x7f;
2948 *blob++ |= bignum_bit(ec->publicKey.x, 0) << 7;
2953 static void *ecdsa_openssh_createkey(const unsigned char **blob, int *len)
2955 const char **b = (const char **) blob;
2959 struct ec_curve *curve;
2960 struct ec_point *publicKey;
2962 getstring(b, len, &p, &slen);
2967 curve = ec_name_to_curve(p, slen);
2968 if (!curve) return NULL;
2970 if (curve->type != EC_WEIERSTRASS) {
2974 ec = snew(struct ec_key);
2976 ec->publicKey.curve = curve;
2977 ec->publicKey.infinity = 0;
2978 ec->publicKey.x = NULL;
2979 ec->publicKey.y = NULL;
2980 ec->publicKey.z = NULL;
2981 if (!getmppoint(b, len, &ec->publicKey)) {
2985 ec->privateKey = NULL;
2987 if (!ec->publicKey.x || !ec->publicKey.y ||
2988 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
2989 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
2995 ec->privateKey = getmp(b, len);
2996 if (ec->privateKey == NULL)
3002 /* Now check that the private key makes the public key */
3003 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
3010 if (bignum_cmp(ec->publicKey.x, publicKey->x) ||
3011 bignum_cmp(ec->publicKey.y, publicKey->y))
3013 /* Private key doesn't make the public key on the given curve */
3015 ec_point_free(publicKey);
3019 ec_point_free(publicKey);
3024 static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len)
3026 struct ec_key *ec = (struct ec_key *) key;
3033 if (ec->publicKey.curve->type != EC_WEIERSTRASS) {
3037 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
3038 namelen = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0);
3040 4 + namelen /* <LEN> nistpXXX */
3041 + 4 + 1 + (pointlen * 2) /* <LEN> 0x04 pX pY */
3042 + ssh2_bignum_length(ec->privateKey);
3049 PUT_32BIT(blob+bloblen, namelen);
3052 bloblen += ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, blob+bloblen, namelen);
3054 PUT_32BIT(blob+bloblen, 1 + (pointlen * 2));
3056 blob[bloblen++] = 0x04;
3057 for (i = pointlen; i--; )
3058 blob[bloblen++] = bignum_byte(ec->publicKey.x, i);
3059 for (i = pointlen; i--; )
3060 blob[bloblen++] = bignum_byte(ec->publicKey.y, i);
3062 pointlen = (bignum_bitcount(ec->privateKey) + 8) / 8;
3063 PUT_32BIT(blob+bloblen, pointlen);
3065 for (i = pointlen; i--; )
3066 blob[bloblen++] = bignum_byte(ec->privateKey, i);
3071 static int ecdsa_pubkey_bits(const void *blob, int len)
3076 ec = (struct ec_key*)ecdsa_newkey((const char *) blob, len);
3079 ret = ec->publicKey.curve->fieldBits;
3085 static int ecdsa_verifysig(void *key, const char *sig, int siglen,
3086 const char *data, int datalen)
3088 struct ec_key *ec = (struct ec_key *) key;
3094 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
3097 /* Check the signature curve matches the key curve */
3098 getstring(&sig, &siglen, &p, &slen);
3102 if (ec->publicKey.curve != ec_name_to_curve(p, slen)) {
3106 getstring(&sig, &siglen, &p, &slen);
3107 if (ec->publicKey.curve->type == EC_EDWARDS) {
3111 /* Check that the signature is two times the length of a point */
3112 if (slen != (ec->publicKey.curve->fieldBits / 8) * 2) {
3116 /* Check it's the 256 bit field so that SHA512 is the correct hash */
3117 if (ec->publicKey.curve->fieldBits != 256) {
3121 /* Get the signature */
3122 r = ec_point_new(ec->publicKey.curve, NULL, NULL, NULL, 0);
3126 if (!decodepoint(p, ec->publicKey.curve->fieldBits / 8, r)) {
3130 s = bignum_from_bytes_le((unsigned char*)p + (ec->publicKey.curve->fieldBits / 8),
3131 ec->publicKey.curve->fieldBits / 8);
3137 /* Get the hash of the encoded value of R + encoded value of pk + message */
3141 unsigned char digest[512 / 8];
3145 /* Add encoded r (no need to encode it again, it was in the signature) */
3146 SHA512_Bytes(&hs, p, ec->publicKey.curve->fieldBits / 8);
3148 /* Encode pk and add it */
3149 pointlen = ec->publicKey.curve->fieldBits / 8;
3150 for (i = 0; i < pointlen - 1; ++i) {
3151 b = bignum_byte(ec->publicKey.y, i);
3152 SHA512_Bytes(&hs, &b, 1);
3154 /* Unset last bit of y and set first bit of x in its place */
3155 b = bignum_byte(ec->publicKey.y, i) & 0x7f;
3156 b |= bignum_bit(ec->publicKey.x, 0) << 7;
3157 SHA512_Bytes(&hs, &b, 1);
3159 /* Add the message itself */
3160 SHA512_Bytes(&hs, data, datalen);
3163 SHA512_Final(&hs, digest);
3165 /* Convert to Bignum */
3166 h = bignum_from_bytes_le(digest, sizeof(digest));
3174 /* Verify sB == r + h*publicKey */
3176 struct ec_point *lhs, *rhs, *tmp;
3179 lhs = ecp_mul(&ec->publicKey.curve->e.B, s);
3187 /* rhs = r + h*publicKey */
3188 tmp = ecp_mul(&ec->publicKey, h);
3195 rhs = ecp_add(r, tmp, 0);
3203 /* Check the point is the same */
3204 ret = !bignum_cmp(lhs->x, rhs->x);
3206 ret = !bignum_cmp(lhs->y, rhs->y);
3216 unsigned char digest[512 / 8];
3218 r = getmp(&p, &slen);
3220 s = getmp(&p, &slen);
3226 /* Perform correct hash function depending on curve size */
3227 if (ec->publicKey.curve->fieldBits <= 256) {
3228 SHA256_Simple(data, datalen, digest);
3229 digestLen = 256 / 8;
3230 } else if (ec->publicKey.curve->fieldBits <= 384) {
3231 SHA384_Simple(data, datalen, digest);
3232 digestLen = 384 / 8;
3234 SHA512_Simple(data, datalen, digest);
3235 digestLen = 512 / 8;
3238 /* Verify the signature */
3239 ret = _ecdsa_verify(&ec->publicKey, digest, digestLen, r, s);
3248 static unsigned char *ecdsa_sign(void *key, const char *data, int datalen,
3251 struct ec_key *ec = (struct ec_key *) key;
3252 unsigned char digest[512 / 8];
3254 Bignum r = NULL, s = NULL;
3255 unsigned char *buf, *p;
3256 int rlen, slen, namelen;
3259 if (!ec->privateKey || !ec->publicKey.curve) {
3263 if (ec->publicKey.curve->type == EC_EDWARDS) {
3264 struct ec_point *rp;
3265 int pointlen = ec->publicKey.curve->fieldBits / 8;
3267 /* hash = H(sk) (where hash creates 2 * fieldBits)
3269 * a = 2^(b-2) + SUM(2^i * h_i) for i = 2 -> b-2
3270 * r = H(h[b/8:b/4] + m)
3272 * S = (r + H(encodepoint(R) + encodepoint(pk) + m) * a) % l */
3274 unsigned char hash[512/8];
3280 for (i = 0; i < pointlen; ++i) {
3281 unsigned char b = (unsigned char)bignum_byte(ec->privateKey, i);
3282 SHA512_Bytes(&hs, &b, 1);
3285 SHA512_Final(&hs, hash);
3287 /* The second part is simply turning the hash into a
3288 * Bignum, however the 2^(b-2) bit *must* be set, and the
3289 * bottom 3 bits *must* not be */
3290 hash[0] &= 0xf8; /* Unset bottom 3 bits (if set) */
3291 hash[31] &= 0x7f; /* Unset above (b-2) */
3292 hash[31] |= 0x40; /* Set 2^(b-2) */
3293 /* Chop off the top part and convert to int */
3294 a = bignum_from_bytes_le(hash, 32);
3301 hash+(ec->publicKey.curve->fieldBits / 8),
3302 (ec->publicKey.curve->fieldBits / 4)
3303 - (ec->publicKey.curve->fieldBits / 8));
3304 SHA512_Bytes(&hs, data, datalen);
3305 SHA512_Final(&hs, hash);
3307 r = bignum_from_bytes_le(hash, 512/8);
3312 rp = ecp_mul(&ec->publicKey.curve->e.B, r);
3319 /* Now calculate s */
3321 /* Encode the point R */
3322 for (i = 0; i < pointlen - 1; ++i) {
3323 b = bignum_byte(rp->y, i);
3324 SHA512_Bytes(&hs, &b, 1);
3326 /* Unset last bit of y and set first bit of x in its place */
3327 b = bignum_byte(rp->y, i) & 0x7f;
3328 b |= bignum_bit(rp->x, 0) << 7;
3329 SHA512_Bytes(&hs, &b, 1);
3331 /* Encode the point pk */
3332 for (i = 0; i < pointlen - 1; ++i) {
3333 b = bignum_byte(ec->publicKey.y, i);
3334 SHA512_Bytes(&hs, &b, 1);
3336 /* Unset last bit of y and set first bit of x in its place */
3337 b = bignum_byte(ec->publicKey.y, i) & 0x7f;
3338 b |= bignum_bit(ec->publicKey.x, 0) << 7;
3339 SHA512_Bytes(&hs, &b, 1);
3341 /* Add the message */
3342 SHA512_Bytes(&hs, data, datalen);
3343 SHA512_Final(&hs, hash);
3348 tmp = bignum_from_bytes_le(hash, 512/8);
3355 tmp2 = modmul(tmp, a, ec->publicKey.curve->e.l);
3363 tmp = bigadd(r, tmp2);
3370 s = bigmod(tmp, ec->publicKey.curve->e.l);
3379 /* Format the output */
3380 namelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0);
3381 *siglen = 4+namelen+4+((ec->publicKey.curve->fieldBits / 8)*2);
3382 buf = snewn(*siglen, unsigned char);
3384 PUT_32BIT(p, namelen);
3386 p += ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, p, namelen);
3387 PUT_32BIT(p, ((ec->publicKey.curve->fieldBits / 8)*2));
3390 /* Encode the point */
3391 pointlen = ec->publicKey.curve->fieldBits / 8;
3392 for (i = 0; i < pointlen - 1; ++i) {
3393 *p++ = bignum_byte(rp->y, i);
3395 /* Unset last bit of y and set first bit of x in its place */
3396 *p = bignum_byte(rp->y, i) & 0x7f;
3397 *p++ |= bignum_bit(rp->x, 0) << 7;
3400 /* Encode the int */
3401 for (i = 0; i < pointlen; ++i) {
3402 *p++ = bignum_byte(s, i);
3406 /* Perform correct hash function depending on curve size */
3407 if (ec->publicKey.curve->fieldBits <= 256) {
3408 SHA256_Simple(data, datalen, digest);
3409 digestLen = 256 / 8;
3410 } else if (ec->publicKey.curve->fieldBits <= 384) {
3411 SHA384_Simple(data, datalen, digest);
3412 digestLen = 384 / 8;
3414 SHA512_Simple(data, datalen, digest);
3415 digestLen = 512 / 8;
3418 /* Do the signature */
3419 _ecdsa_sign(ec->privateKey, ec->publicKey.curve, digest, digestLen, &r, &s);
3426 rlen = (bignum_bitcount(r) + 8) / 8;
3427 slen = (bignum_bitcount(s) + 8) / 8;
3429 namelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0);
3431 /* Format the output */
3432 *siglen = 8+namelen+rlen+slen+8;
3433 buf = snewn(*siglen, unsigned char);
3435 PUT_32BIT(p, namelen);
3437 p += ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, p, namelen);
3438 PUT_32BIT(p, rlen + slen + 8);
3442 for (i = rlen; i--;)
3443 *p++ = bignum_byte(r, i);
3446 for (i = slen; i--;)
3447 *p++ = bignum_byte(s, i);
3456 const struct ssh_signkey ssh_ecdsa_ed25519 = {
3463 ed25519_openssh_createkey,
3464 ed25519_openssh_fmtkey,
3465 2 /* point, private exponent */,
3473 const struct ssh_signkey ssh_ecdsa_nistp256 = {
3480 ecdsa_openssh_createkey,
3481 ecdsa_openssh_fmtkey,
3482 3 /* curve name, point, private exponent */,
3486 "ecdsa-sha2-nistp256",
3487 "ecdsa-sha2-nistp256",
3490 const struct ssh_signkey ssh_ecdsa_nistp384 = {
3497 ecdsa_openssh_createkey,
3498 ecdsa_openssh_fmtkey,
3499 3 /* curve name, point, private exponent */,
3503 "ecdsa-sha2-nistp384",
3504 "ecdsa-sha2-nistp384",
3507 const struct ssh_signkey ssh_ecdsa_nistp521 = {
3514 ecdsa_openssh_createkey,
3515 ecdsa_openssh_fmtkey,
3516 3 /* curve name, point, private exponent */,
3520 "ecdsa-sha2-nistp521",
3521 "ecdsa-sha2-nistp521",
3524 /* ----------------------------------------------------------------------
3525 * Exposed ECDH interface
3528 static Bignum ecdh_calculate(const Bignum private,
3529 const struct ec_point *public)
3533 p = ecp_mul(public, private);
3534 if (!p) return NULL;
3538 if (p->curve->type == EC_MONTGOMERY) {
3539 /* Do conversion in network byte order */
3541 int bytes = (bignum_bitcount(ret)+7) / 8;
3542 unsigned char *byteorder = snewn(bytes, unsigned char);
3548 for (i = 0; i < bytes; ++i) {
3549 byteorder[i] = bignum_byte(ret, i);
3552 ret = bignum_from_bytes(byteorder, bytes);
3560 void *ssh_ecdhkex_newkey(const char *name)
3562 struct ec_curve *curve;
3564 struct ec_point *publicKey;
3566 curve = ec_name_to_curve(name, strlen(name));
3568 key = snew(struct ec_key);
3573 key->publicKey.curve = curve;
3575 if (curve->type == EC_MONTGOMERY) {
3576 unsigned char bytes[32] = {0};
3579 for (i = 0; i < sizeof(bytes); ++i)
3581 bytes[i] = (unsigned char)random_byte();
3586 key->privateKey = bignum_from_bytes(bytes, sizeof(bytes));
3587 for (i = 0; i < sizeof(bytes); ++i)
3589 ((volatile char*)bytes)[i] = 0;
3591 if (!key->privateKey) {
3595 publicKey = ecp_mul(&key->publicKey.curve->m.G, key->privateKey);
3597 freebn(key->privateKey);
3601 key->publicKey.x = publicKey->x;
3602 key->publicKey.y = publicKey->y;
3603 key->publicKey.z = NULL;
3606 key->privateKey = bignum_random_in_range(One, key->publicKey.curve->w.n);
3607 if (!key->privateKey) {
3611 publicKey = ecp_mul(&key->publicKey.curve->w.G, key->privateKey);
3613 freebn(key->privateKey);
3617 key->publicKey.x = publicKey->x;
3618 key->publicKey.y = publicKey->y;
3619 key->publicKey.z = NULL;
3625 char *ssh_ecdhkex_getpublic(void *key, int *len)
3627 struct ec_key *ec = (struct ec_key*)key;
3632 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
3634 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
3635 *len = 1 + pointlen * 2;
3639 point = (char*)snewn(*len, char);
3645 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
3647 for (i = pointlen; i--;) {
3648 *p++ = bignum_byte(ec->publicKey.x, i);
3650 for (i = pointlen; i--;) {
3651 *p++ = bignum_byte(ec->publicKey.y, i);
3654 for (i = 0; i < pointlen; ++i) {
3655 *p++ = bignum_byte(ec->publicKey.x, i);
3662 Bignum ssh_ecdhkex_getkey(void *key, char *remoteKey, int remoteKeyLen)
3664 struct ec_key *ec = (struct ec_key*) key;
3665 struct ec_point remote;
3668 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
3669 remote.curve = ec->publicKey.curve;
3670 remote.infinity = 0;
3671 if (!decodepoint(remoteKey, remoteKeyLen, &remote)) {
3675 /* Point length has to be the same length */
3676 if (remoteKeyLen != (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8) {
3680 remote.curve = ec->publicKey.curve;
3681 remote.infinity = 0;
3682 remote.x = bignum_from_bytes_le((unsigned char*)remoteKey, remoteKeyLen);
3687 ret = ecdh_calculate(ec->privateKey, &remote);
3688 if (remote.x) freebn(remote.x);
3689 if (remote.y) freebn(remote.y);
3693 void ssh_ecdhkex_freekey(void *key)
3698 static const struct ssh_kex ssh_ec_kex_curve25519 = {
3699 "curve25519-sha256@libssh.org", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha256
3702 static const struct ssh_kex ssh_ec_kex_nistp256 = {
3703 "ecdh-sha2-nistp256", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha256
3706 static const struct ssh_kex ssh_ec_kex_nistp384 = {
3707 "ecdh-sha2-nistp384", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha384
3710 static const struct ssh_kex ssh_ec_kex_nistp521 = {
3711 "ecdh-sha2-nistp521", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha512
3714 static const struct ssh_kex *const ec_kex_list[] = {
3715 &ssh_ec_kex_curve25519,
3716 &ssh_ec_kex_nistp256,
3717 &ssh_ec_kex_nistp384,
3718 &ssh_ec_kex_nistp521
3721 const struct ssh_kexes ssh_ecdh_kex = {
3722 sizeof(ec_kex_list) / sizeof(*ec_kex_list),