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)
14 * Elliptic curves in SSH are specified in RFC 5656:
15 * http://tools.ietf.org/html/rfc5656
17 * That specification delegates details of public key formatting and a
18 * lot of underlying mechanism to SEC 1:
19 * http://www.secg.org/sec1-v2.pdf
21 * Montgomery maths from:
22 * Handbook of elliptic and hyperelliptic curve cryptography, Chapter 13
23 * http://cs.ucsb.edu/~koc/ccs130h/2013/EllipticHyperelliptic-CohenFrey.pdf
31 /* ----------------------------------------------------------------------
32 * Elliptic curve definitions
35 static int initialise_wcurve(struct ec_curve *curve, int bits, unsigned char *p,
36 unsigned char *a, unsigned char *b,
37 unsigned char *n, unsigned char *Gx,
40 int length = bits / 8;
41 if (bits % 8) ++length;
43 curve->type = EC_WEIERSTRASS;
45 curve->fieldBits = bits;
46 curve->p = bignum_from_bytes(p, length);
47 if (!curve->p) goto error;
49 /* Curve co-efficients */
50 curve->w.a = bignum_from_bytes(a, length);
51 if (!curve->w.a) goto error;
52 curve->w.b = bignum_from_bytes(b, length);
53 if (!curve->w.b) goto error;
55 /* Group order and generator */
56 curve->w.n = bignum_from_bytes(n, length);
57 if (!curve->w.n) goto error;
58 curve->w.G.x = bignum_from_bytes(Gx, length);
59 if (!curve->w.G.x) goto error;
60 curve->w.G.y = bignum_from_bytes(Gy, length);
61 if (!curve->w.G.y) goto error;
62 curve->w.G.curve = curve;
63 curve->w.G.infinity = 0;
67 if (curve->p) freebn(curve->p);
68 if (curve->w.a) freebn(curve->w.a);
69 if (curve->w.b) freebn(curve->w.b);
70 if (curve->w.n) freebn(curve->w.n);
71 if (curve->w.G.x) freebn(curve->w.G.x);
75 static int initialise_mcurve(struct ec_curve *curve, int bits, unsigned char *p,
76 unsigned char *a, unsigned char *b,
79 int length = bits / 8;
80 if (bits % 8) ++length;
82 curve->type = EC_MONTGOMERY;
84 curve->fieldBits = bits;
85 curve->p = bignum_from_bytes(p, length);
86 if (!curve->p) goto error;
88 /* Curve co-efficients */
89 curve->m.a = bignum_from_bytes(a, length);
90 if (!curve->m.a) goto error;
91 curve->m.b = bignum_from_bytes(b, length);
92 if (!curve->m.b) goto error;
95 curve->m.G.x = bignum_from_bytes(Gx, length);
96 if (!curve->m.G.x) goto error;
99 curve->m.G.curve = curve;
100 curve->m.G.infinity = 0;
104 if (curve->p) freebn(curve->p);
105 if (curve->m.a) freebn(curve->m.a);
106 if (curve->m.b) freebn(curve->m.b);
110 unsigned char nistp256_oid[] = {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07};
111 int nistp256_oid_len = 8;
112 unsigned char nistp384_oid[] = {0x2b, 0x81, 0x04, 0x00, 0x22};
113 int nistp384_oid_len = 5;
114 unsigned char nistp521_oid[] = {0x2b, 0x81, 0x04, 0x00, 0x23};
115 int nistp521_oid_len = 5;
116 unsigned char curve25519_oid[] = {0x06, 0x0A, 0x2B, 0x06, 0x01, 0x04, 0x01, 0x97, 0x55, 0x01, 0x05, 0x01};
117 int curve25519_oid_len = 12;
119 struct ec_curve *ec_p256(void)
121 static struct ec_curve curve = { 0 };
122 static unsigned char initialised = 0;
126 unsigned char p[] = {
127 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
128 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
129 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
130 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff
132 unsigned char a[] = {
133 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
134 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
135 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
136 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc
138 unsigned char b[] = {
139 0x5a, 0xc6, 0x35, 0xd8, 0xaa, 0x3a, 0x93, 0xe7,
140 0xb3, 0xeb, 0xbd, 0x55, 0x76, 0x98, 0x86, 0xbc,
141 0x65, 0x1d, 0x06, 0xb0, 0xcc, 0x53, 0xb0, 0xf6,
142 0x3b, 0xce, 0x3c, 0x3e, 0x27, 0xd2, 0x60, 0x4b
144 unsigned char n[] = {
145 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
146 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
147 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
148 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51
150 unsigned char Gx[] = {
151 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47,
152 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2,
153 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0,
154 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96
156 unsigned char Gy[] = {
157 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b,
158 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e, 0x16,
159 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce,
160 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5
163 if (!initialise_wcurve(&curve, 256, p, a, b, n, Gx, Gy)) {
167 /* Now initialised, no need to do it again */
174 struct ec_curve *ec_p384(void)
176 static struct ec_curve curve = { 0 };
177 static unsigned char initialised = 0;
181 unsigned char p[] = {
182 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
183 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
184 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
185 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
186 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
187 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff
189 unsigned char a[] = {
190 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
191 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
192 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
193 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
194 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
195 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xfc
197 unsigned char b[] = {
198 0xb3, 0x31, 0x2f, 0xa7, 0xe2, 0x3e, 0xe7, 0xe4,
199 0x98, 0x8e, 0x05, 0x6b, 0xe3, 0xf8, 0x2d, 0x19,
200 0x18, 0x1d, 0x9c, 0x6e, 0xfe, 0x81, 0x41, 0x12,
201 0x03, 0x14, 0x08, 0x8f, 0x50, 0x13, 0x87, 0x5a,
202 0xc6, 0x56, 0x39, 0x8d, 0x8a, 0x2e, 0xd1, 0x9d,
203 0x2a, 0x85, 0xc8, 0xed, 0xd3, 0xec, 0x2a, 0xef
205 unsigned char n[] = {
206 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
207 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
208 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
209 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
210 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
211 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73
213 unsigned char Gx[] = {
214 0xaa, 0x87, 0xca, 0x22, 0xbe, 0x8b, 0x05, 0x37,
215 0x8e, 0xb1, 0xc7, 0x1e, 0xf3, 0x20, 0xad, 0x74,
216 0x6e, 0x1d, 0x3b, 0x62, 0x8b, 0xa7, 0x9b, 0x98,
217 0x59, 0xf7, 0x41, 0xe0, 0x82, 0x54, 0x2a, 0x38,
218 0x55, 0x02, 0xf2, 0x5d, 0xbf, 0x55, 0x29, 0x6c,
219 0x3a, 0x54, 0x5e, 0x38, 0x72, 0x76, 0x0a, 0xb7
221 unsigned char Gy[] = {
222 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f,
223 0x5d, 0x9e, 0x98, 0xbf, 0x92, 0x92, 0xdc, 0x29,
224 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c,
225 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0,
226 0x0a, 0x60, 0xb1, 0xce, 0x1d, 0x7e, 0x81, 0x9d,
227 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f
230 if (!initialise_wcurve(&curve, 384, p, a, b, n, Gx, Gy)) {
234 /* Now initialised, no need to do it again */
241 struct ec_curve *ec_p521(void)
243 static struct ec_curve curve = { 0 };
244 static unsigned char initialised = 0;
248 unsigned char p[] = {
249 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
250 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
251 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
252 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
253 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
254 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
255 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
256 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
259 unsigned char a[] = {
260 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
261 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
262 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
263 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
264 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
265 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
266 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
267 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
270 unsigned char b[] = {
271 0x00, 0x51, 0x95, 0x3e, 0xb9, 0x61, 0x8e, 0x1c,
272 0x9a, 0x1f, 0x92, 0x9a, 0x21, 0xa0, 0xb6, 0x85,
273 0x40, 0xee, 0xa2, 0xda, 0x72, 0x5b, 0x99, 0xb3,
274 0x15, 0xf3, 0xb8, 0xb4, 0x89, 0x91, 0x8e, 0xf1,
275 0x09, 0xe1, 0x56, 0x19, 0x39, 0x51, 0xec, 0x7e,
276 0x93, 0x7b, 0x16, 0x52, 0xc0, 0xbd, 0x3b, 0xb1,
277 0xbf, 0x07, 0x35, 0x73, 0xdf, 0x88, 0x3d, 0x2c,
278 0x34, 0xf1, 0xef, 0x45, 0x1f, 0xd4, 0x6b, 0x50,
281 unsigned char n[] = {
282 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
283 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
284 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
285 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
286 0xff, 0xfa, 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f,
287 0x96, 0x6b, 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09,
288 0xa5, 0xd0, 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c,
289 0x47, 0xae, 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38,
292 unsigned char Gx[] = {
293 0x00, 0xc6, 0x85, 0x8e, 0x06, 0xb7, 0x04, 0x04,
294 0xe9, 0xcd, 0x9e, 0x3e, 0xcb, 0x66, 0x23, 0x95,
295 0xb4, 0x42, 0x9c, 0x64, 0x81, 0x39, 0x05, 0x3f,
296 0xb5, 0x21, 0xf8, 0x28, 0xaf, 0x60, 0x6b, 0x4d,
297 0x3d, 0xba, 0xa1, 0x4b, 0x5e, 0x77, 0xef, 0xe7,
298 0x59, 0x28, 0xfe, 0x1d, 0xc1, 0x27, 0xa2, 0xff,
299 0xa8, 0xde, 0x33, 0x48, 0xb3, 0xc1, 0x85, 0x6a,
300 0x42, 0x9b, 0xf9, 0x7e, 0x7e, 0x31, 0xc2, 0xe5,
303 unsigned char Gy[] = {
304 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b,
305 0xc0, 0x04, 0x5c, 0x8a, 0x5f, 0xb4, 0x2c, 0x7d,
306 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b,
307 0x44, 0x68, 0x17, 0xaf, 0xbd, 0x17, 0x27, 0x3e,
308 0x66, 0x2c, 0x97, 0xee, 0x72, 0x99, 0x5e, 0xf4,
309 0x26, 0x40, 0xc5, 0x50, 0xb9, 0x01, 0x3f, 0xad,
310 0x07, 0x61, 0x35, 0x3c, 0x70, 0x86, 0xa2, 0x72,
311 0xc2, 0x40, 0x88, 0xbe, 0x94, 0x76, 0x9f, 0xd1,
315 if (!initialise_wcurve(&curve, 521, p, a, b, n, Gx, Gy)) {
319 /* Now initialised, no need to do it again */
326 struct ec_curve *ec_curve25519(void)
328 static struct ec_curve curve = { 0 };
329 static unsigned char initialised = 0;
333 unsigned char p[] = {
334 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
335 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
336 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
337 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
339 unsigned char a[] = {
340 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
341 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
342 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
343 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x6d, 0x06
345 unsigned char b[] = {
346 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
347 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
348 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
349 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
351 unsigned char gx[32] = {
352 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
353 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
354 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
355 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x09
358 if (!initialise_mcurve(&curve, 256, p, a, b, gx)) {
362 /* Now initialised, no need to do it again */
369 static struct ec_curve *ec_name_to_curve(const char *name, int len) {
370 if (len > 11 && !memcmp(name, "ecdsa-sha2-", 11)) {
373 } else if (len > 10 && !memcmp(name, "ecdh-sha2-", 10)) {
378 if (len == 8 && !memcmp(name, "nistp", 5)) {
380 if (!memcmp(name, "256", 3)) {
382 } else if (!memcmp(name, "384", 3)) {
384 } else if (!memcmp(name, "521", 3)) {
389 if (len == 28 && !memcmp(name, "curve25519-sha256@libssh.org", 28)) {
390 return ec_curve25519();
396 /* Type enumeration for specifying the curve name */
397 enum ec_name_type { EC_TYPE_DSA, EC_TYPE_DH, EC_TYPE_CURVE };
399 static int ec_curve_to_name(enum ec_name_type type, const struct ec_curve *curve,
400 unsigned char *name, int len) {
401 if (curve->type == EC_WEIERSTRASS) {
403 if (type == EC_TYPE_DSA) {
406 } else if (type == EC_TYPE_DH) {
414 /* Return length of string */
415 if (name == NULL) return length;
417 /* Not enough space for the name */
418 if (len < length) return 0;
420 /* Put the name in the buffer */
421 switch (curve->fieldBits) {
423 memcpy(name+loc, "256", 3);
426 memcpy(name+loc, "384", 3);
429 memcpy(name+loc, "521", 3);
435 if (type == EC_TYPE_DSA) {
436 memcpy(name, "ecdsa-sha2-nistp", 16);
437 } else if (type == EC_TYPE_DH) {
438 memcpy(name, "ecdh-sha2-nistp", 15);
440 memcpy(name, "nistp", 5);
445 /* No DSA for curve25519 */
446 if (type == EC_TYPE_DSA || type == EC_TYPE_CURVE) return 0;
448 /* Return length of string */
449 if (name == NULL) return 28;
451 /* Not enough space for the name */
452 if (len < 28) return 0;
454 /* Unknown curve field */
455 if (curve->fieldBits != 256) return 0;
457 memcpy(name, "curve25519-sha256@libssh.org", 28);
462 /* Return 1 if a is -3 % p, otherwise return 0
463 * This is used because there are some maths optimisations */
464 static int ec_aminus3(const struct ec_curve *curve)
469 if (curve->type != EC_WEIERSTRASS) {
473 _p = bignum_add_long(curve->w.a, 3);
476 ret = !bignum_cmp(curve->p, _p);
481 /* ----------------------------------------------------------------------
482 * Elliptic curve field maths
485 static Bignum ecf_add(const Bignum a, const Bignum b,
486 const struct ec_curve *curve)
488 Bignum a1, b1, ab, ret;
490 a1 = bigmod(a, curve->p);
491 if (!a1) return NULL;
492 b1 = bigmod(b, curve->p);
502 if (!ab) return NULL;
504 ret = bigmod(ab, curve->p);
510 static Bignum ecf_square(const Bignum a, const struct ec_curve *curve)
512 return modmul(a, a, curve->p);
515 static Bignum ecf_treble(const Bignum a, const struct ec_curve *curve)
520 tmp = bignum_lshift(a, 1);
521 if (!tmp) return NULL;
523 /* Add itself (i.e. treble) */
524 ret = bigadd(tmp, a);
528 while (ret != NULL && bignum_cmp(ret, curve->p) >= 0)
530 tmp = bigsub(ret, curve->p);
538 static Bignum ecf_double(const Bignum a, const struct ec_curve *curve)
540 Bignum ret = bignum_lshift(a, 1);
541 if (!ret) return NULL;
542 if (bignum_cmp(ret, curve->p) >= 0)
544 Bignum tmp = bigsub(ret, curve->p);
554 /* ----------------------------------------------------------------------
558 void ec_point_free(struct ec_point *point)
560 if (point == NULL) return;
562 if (point->x) freebn(point->x);
563 if (point->y) freebn(point->y);
564 if (point->z) freebn(point->z);
569 static struct ec_point *ec_point_new(const struct ec_curve *curve,
570 const Bignum x, const Bignum y, const Bignum z,
571 unsigned char infinity)
573 struct ec_point *point = snewn(1, struct ec_point);
574 point->curve = curve;
578 point->infinity = infinity ? 1 : 0;
582 static struct ec_point *ec_point_copy(const struct ec_point *a)
584 if (a == NULL) return NULL;
585 return ec_point_new(a->curve,
586 a->x ? copybn(a->x) : NULL,
587 a->y ? copybn(a->y) : NULL,
588 a->z ? copybn(a->z) : NULL,
592 static int ec_point_verify(const struct ec_point *a)
596 } else if (a->curve->type == EC_WEIERSTRASS) {
597 /* Verify y^2 = x^3 + ax + b */
600 Bignum lhs = NULL, x3 = NULL, ax = NULL, x3ax = NULL, x3axm = NULL, x3axb = NULL, rhs = NULL;
602 Bignum Three = bignum_from_long(3);
603 if (!Three) return 0;
605 lhs = modmul(a->y, a->y, a->curve->p);
606 if (!lhs) goto error;
608 /* This uses montgomery multiplication to optimise */
609 x3 = modpow(a->x, Three, a->curve->p);
612 ax = modmul(a->curve->w.a, a->x, a->curve->p);
614 x3ax = bigadd(x3, ax);
615 if (!x3ax) goto error;
616 freebn(x3); x3 = NULL;
617 freebn(ax); ax = NULL;
618 x3axm = bigmod(x3ax, a->curve->p);
619 if (!x3axm) goto error;
620 freebn(x3ax); x3ax = NULL;
621 x3axb = bigadd(x3axm, a->curve->w.b);
622 if (!x3axb) goto error;
623 freebn(x3axm); x3axm = NULL;
624 rhs = bigmod(x3axb, a->curve->p);
625 if (!rhs) goto error;
628 ret = bignum_cmp(lhs, rhs) ? 0 : 1;
637 if (x3ax) freebn(x3ax);
638 if (x3axm) freebn(x3axm);
639 if (x3axb) freebn(x3axb);
640 if (lhs) freebn(lhs);
647 /* ----------------------------------------------------------------------
648 * Elliptic curve point maths
651 /* Returns 1 on success and 0 on memory error */
652 static int ecp_normalise(struct ec_point *a)
660 /* Point is at infinity - i.e. normalised */
664 if (a->curve->type == EC_WEIERSTRASS) {
665 /* In Jacobian Coordinates the triple (X, Y, Z) represents
666 the affine point (X / Z^2, Y / Z^3) */
668 Bignum Z2, Z2inv, Z3, Z3inv, tx, ty;
670 if (!a->x || !a->y) {
671 /* No point defined */
674 /* Already normalised */
678 Z2 = ecf_square(a->z, a->curve);
682 Z2inv = modinv(Z2, a->curve->p);
687 tx = modmul(a->x, Z2inv, a->curve->p);
694 Z3 = modmul(Z2, a->z, a->curve->p);
700 Z3inv = modinv(Z3, a->curve->p);
706 ty = modmul(a->y, Z3inv, a->curve->p);
720 } else if (a->curve->type == EC_MONTGOMERY) {
721 /* In Montgomery (X : Z) represents the x co-ord (X / Z, ?) */
726 /* No point defined */
729 /* Already normalised */
733 tmp = modinv(a->z, a->curve->p);
737 tmp2 = modmul(a->x, tmp, a->curve->p);
753 static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3)
755 Bignum S, M, outx, outy, outz;
757 if (bignum_cmp(a->y, Zero) == 0)
760 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
765 Bignum Y2, XY2, _2XY2;
767 Y2 = ecf_square(a->y, a->curve);
771 XY2 = modmul(a->x, Y2, a->curve->p);
777 _2XY2 = ecf_double(XY2, a->curve);
782 S = ecf_double(_2XY2, a->curve);
789 /* Faster calculation if a = -3 */
791 /* if a = -3, then M can also be calculated as M = 3*(X + Z^2)*(X - Z^2) */
792 Bignum Z2, XpZ2, XmZ2, second;
797 Z2 = ecf_square(a->z, a->curve);
804 XpZ2 = ecf_add(a->x, Z2, a->curve);
810 XmZ2 = modsub(a->x, Z2, a->curve->p);
818 second = modmul(XpZ2, XmZ2, a->curve->p);
826 M = ecf_treble(second, a->curve);
833 /* M = 3*X^2 + a*Z^4 */
834 Bignum _3X2, X2, aZ4;
837 aZ4 = copybn(a->curve->w.a);
841 Z2 = ecf_square(a->z, a->curve);
846 Z4 = ecf_square(Z2, a->curve);
852 aZ4 = modmul(a->curve->w.a, Z4, a->curve->p);
860 X2 = modmul(a->x, a->x, a->curve->p);
866 _3X2 = ecf_treble(X2, a->curve);
873 M = ecf_add(_3X2, aZ4, a->curve);
886 M2 = ecf_square(M, a->curve);
893 _2S = ecf_double(S, a->curve);
901 outx = modsub(M2, _2S, a->curve->p);
911 /* Y' = M*(S - X') - 8*Y^4 */
913 Bignum SX, MSX, Eight, Y2, Y4, _8Y4;
915 SX = modsub(S, outx, a->curve->p);
922 MSX = modmul(M, SX, a->curve->p);
929 Y2 = ecf_square(a->y, a->curve);
935 Y4 = ecf_square(Y2, a->curve);
942 Eight = bignum_from_long(8);
949 _8Y4 = modmul(Eight, Y4, a->curve->p);
957 outy = modsub(MSX, _8Y4, a->curve->p);
973 YZ = modmul(a->y, a->z, a->curve->p);
981 outz = ecf_double(YZ, a->curve);
990 return ec_point_new(a->curve, outx, outy, outz, 0);
993 static struct ec_point *ecp_doublem(const struct ec_point *a)
995 Bignum z, outx, outz, xpz, xmz;
1002 /* 4xz = (x + z)^2 - (x - z)^2 */
1006 tmp = ecf_add(a->x, z, a->curve);
1010 xpz = ecf_square(tmp, a->curve);
1016 tmp = modsub(a->x, z, a->curve->p);
1021 xmz = ecf_square(tmp, a->curve);
1029 /* outx = (x + z)^2 * (x - z)^2 */
1030 outx = modmul(xpz, xmz, a->curve->p);
1037 /* outz = 4xz * ((x - z)^2 + ((A + 2) / 4)*4xz) */
1039 Bignum _4xz, tmp, tmp2, tmp3;
1041 tmp = bignum_from_long(2);
1048 tmp2 = ecf_add(a->curve->m.a, tmp, a->curve);
1057 _4xz = modsub(xpz, xmz, a->curve->p);
1065 tmp = modmul(tmp2, _4xz, a->curve->p);
1074 tmp2 = bignum_from_long(4);
1082 tmp3 = modinv(tmp2, a->curve->p);
1091 tmp2 = modmul(tmp, tmp3, a->curve->p);
1101 tmp = ecf_add(xmz, tmp2, a->curve);
1109 outz = modmul(_4xz, tmp, a->curve->p);
1118 return ec_point_new(a->curve, outx, NULL, outz, 0);
1121 static struct ec_point *ecp_double(const struct ec_point *a, const int aminus3)
1126 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
1129 if (a->curve->type == EC_WEIERSTRASS)
1131 return ecp_doublew(a, aminus3);
1135 return ecp_doublem(a);
1139 static struct ec_point *ecp_addw(const struct ec_point *a,
1140 const struct ec_point *b,
1143 Bignum U1, U2, S1, S2, outx, outy, outz;
1150 Z2 = ecf_square(b->z, a->curve);
1154 U1 = modmul(a->x, Z2, a->curve->p);
1159 Z3 = modmul(Z2, b->z, a->curve->p);
1165 S1 = modmul(a->y, Z3, a->curve->p);
1188 Z2 = ecf_square(a->z, b->curve);
1194 U2 = modmul(b->x, Z2, b->curve->p);
1201 Z3 = modmul(Z2, a->z, b->curve->p);
1209 S2 = modmul(b->y, Z3, b->curve->p);
1233 /* Check if multiplying by self */
1234 if (bignum_cmp(U1, U2) == 0)
1238 if (bignum_cmp(S1, S2) == 0)
1242 return ecp_double(a, aminus3);
1249 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
1254 Bignum H, R, UH2, H3;
1257 H = modsub(U2, U1, a->curve->p);
1267 R = modsub(S2, S1, a->curve->p);
1276 /* X3 = R^2 - H^3 - 2*U1*H^2 */
1278 Bignum R2, H2, _2UH2, first;
1280 H2 = ecf_square(H, a->curve);
1288 UH2 = modmul(U1, H2, a->curve->p);
1297 H3 = modmul(H2, H, a->curve->p);
1306 R2 = ecf_square(R, a->curve);
1315 _2UH2 = ecf_double(UH2, a->curve);
1325 first = modsub(R2, H3, a->curve->p);
1336 outx = modsub(first, _2UH2, a->curve->p);
1349 /* Y3 = R*(U1*H^2 - X3) - S1*H^3 */
1351 Bignum RUH2mX, UH2mX, SH3;
1353 UH2mX = modsub(UH2, outx, a->curve->p);
1363 RUH2mX = modmul(R, UH2mX, a->curve->p);
1373 SH3 = modmul(S1, H3, a->curve->p);
1383 outy = modsub(RUH2mX, SH3, a->curve->p);
1397 ZZ = modmul(a->z, b->z, a->curve->p);
1404 outz = modmul(H, ZZ, a->curve->p);
1413 outz = modmul(H, a->z, a->curve->p);
1421 outz = modmul(H, b->z, a->curve->p);
1433 return ec_point_new(a->curve, outx, outy, outz, 0);
1436 static struct ec_point *ecp_addm(const struct ec_point *a,
1437 const struct ec_point *b,
1438 const struct ec_point *base)
1440 Bignum outx, outz, az, bz;
1451 /* a-b is maintained at 1 due to Montgomery ladder implementation */
1452 /* Xa+b = Za-b * ((Xa - Za)*(Xb + Zb) + (Xa + Za)*(Xb - Zb))^2 */
1453 /* Za+b = Xa-b * ((Xa - Za)*(Xb + Zb) - (Xa + Za)*(Xb - Zb))^2 */
1455 Bignum tmp, tmp2, tmp3, tmp4;
1457 /* (Xa + Za) * (Xb - Zb) */
1458 tmp = ecf_add(a->x, az, a->curve);
1462 tmp2 = modsub(b->x, bz, a->curve->p);
1467 tmp3 = modmul(tmp, tmp2, a->curve->p);
1474 /* (Xa - Za) * (Xb + Zb) */
1475 tmp = modsub(a->x, az, a->curve->p);
1480 tmp2 = ecf_add(b->x, bz, a->curve);
1486 tmp4 = modmul(tmp, tmp2, a->curve->p);
1494 tmp = ecf_add(tmp3, tmp4, a->curve);
1500 outx = ecf_square(tmp, a->curve);
1508 tmp = modsub(tmp3, tmp4, a->curve->p);
1515 tmp2 = ecf_square(tmp, a->curve);
1521 outz = modmul(base->x, tmp2, a->curve->p);
1529 return ec_point_new(a->curve, outx, NULL, outz, 0);
1532 static struct ec_point *ecp_add(const struct ec_point *a,
1533 const struct ec_point *b,
1536 if (a->curve != b->curve) {
1540 /* Check if multiplying by infinity */
1541 if (a->infinity) return ec_point_copy(b);
1542 if (b->infinity) return ec_point_copy(a);
1544 if (a->curve->type == EC_WEIERSTRASS)
1546 return ecp_addw(a, b, aminus3);
1552 static struct ec_point *ecp_mul_(const struct ec_point *a, const Bignum b, int aminus3)
1554 struct ec_point *A, *ret;
1557 A = ec_point_copy(a);
1558 ret = ec_point_new(a->curve, NULL, NULL, NULL, 1);
1560 bits = bignum_bitcount(b);
1561 for (i = 0; ret != NULL && A != NULL && i < bits; ++i)
1563 if (bignum_bit(b, i))
1565 struct ec_point *tmp = ecp_add(ret, A, aminus3);
1571 struct ec_point *tmp = ecp_double(A, aminus3);
1587 static struct ec_point *ecp_mulw(const struct ec_point *a, const Bignum b)
1589 struct ec_point *ret = ecp_mul_(a, b, ec_aminus3(a->curve));
1591 if (!ecp_normalise(ret)) {
1599 static struct ec_point *ecp_mulm(const struct ec_point *p, const Bignum n)
1601 struct ec_point *P1, *P2;
1604 /* P1 <- P and P2 <- [2]P */
1605 P2 = ecp_double(p, 0);
1609 P1 = ec_point_copy(p);
1615 /* for i = bits − 2 down to 0 */
1616 bits = bignum_bitcount(n);
1617 for (i = bits - 2; P1 != NULL && P2 != NULL && i >= 0; --i)
1619 if (!bignum_bit(n, i))
1622 struct ec_point *tmp = ecp_addm(P1, P2, p);
1627 tmp = ecp_double(P1, 0);
1634 struct ec_point *tmp = ecp_addm(P1, P2, p);
1639 tmp = ecp_double(P2, 0);
1646 if (P1) ec_point_free(P1);
1652 if (!ecp_normalise(P1)) {
1660 /* Not static because it is used by sshecdsag.c to generate a new key */
1661 struct ec_point *ecp_mul(const struct ec_point *a, const Bignum b)
1663 if (a->curve->type == EC_WEIERSTRASS) {
1664 return ecp_mulw(a, b);
1666 return ecp_mulm(a, b);
1670 static struct ec_point *ecp_summul(const Bignum a, const Bignum b,
1671 const struct ec_point *point)
1673 struct ec_point *aG, *bP, *ret;
1676 if (point->curve->type != EC_WEIERSTRASS) {
1680 aminus3 = ec_aminus3(point->curve);
1682 aG = ecp_mul_(&point->curve->w.G, a, aminus3);
1683 if (!aG) return NULL;
1684 bP = ecp_mul_(point, b, aminus3);
1690 ret = ecp_add(aG, bP, aminus3);
1695 if (!ecp_normalise(ret)) {
1703 /* ----------------------------------------------------------------------
1704 * Public point from private
1707 struct ec_point *ec_public(const Bignum privateKey, const struct ec_curve *curve)
1709 if (curve->type == EC_WEIERSTRASS) {
1710 return ecp_mul(&curve->w.G, privateKey);
1716 /* ----------------------------------------------------------------------
1717 * Basic sign and verify routines
1720 static int _ecdsa_verify(const struct ec_point *publicKey,
1721 const unsigned char *data, const int dataLen,
1722 const Bignum r, const Bignum s)
1728 if (publicKey->curve->type != EC_WEIERSTRASS) {
1733 if (bignum_cmp(r, Zero) == 0 || bignum_cmp(r, publicKey->curve->w.n) >= 0
1734 || bignum_cmp(s, Zero) == 0 || bignum_cmp(s, publicKey->curve->w.n) >= 0)
1739 /* z = left most bitlen(curve->n) of data */
1740 z = bignum_from_bytes(data, dataLen);
1742 n_bits = bignum_bitcount(publicKey->curve->w.n);
1743 z_bits = bignum_bitcount(z);
1744 if (z_bits > n_bits)
1746 Bignum tmp = bignum_rshift(z, z_bits - n_bits);
1752 /* Ensure z in range of n */
1754 Bignum tmp = bigmod(z, publicKey->curve->w.n);
1760 /* Calculate signature */
1762 Bignum w, x, u1, u2;
1763 struct ec_point *tmp;
1765 w = modinv(s, publicKey->curve->w.n);
1770 u1 = modmul(z, w, publicKey->curve->w.n);
1776 u2 = modmul(r, w, publicKey->curve->w.n);
1784 tmp = ecp_summul(u1, u2, publicKey);
1792 x = bigmod(tmp->x, publicKey->curve->w.n);
1799 valid = (bignum_cmp(r, x) == 0) ? 1 : 0;
1808 static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve,
1809 const unsigned char *data, const int dataLen,
1810 Bignum *r, Bignum *s)
1812 unsigned char digest[20];
1815 struct ec_point *kG;
1820 if (curve->type != EC_WEIERSTRASS) {
1824 /* z = left most bitlen(curve->n) of data */
1825 z = bignum_from_bytes(data, dataLen);
1827 n_bits = bignum_bitcount(curve->w.n);
1828 z_bits = bignum_bitcount(z);
1829 if (z_bits > n_bits)
1832 tmp = bignum_rshift(z, z_bits - n_bits);
1838 /* Generate k between 1 and curve->n, using the same deterministic
1839 * k generation system we use for conventional DSA. */
1840 SHA_Simple(data, dataLen, digest);
1841 k = dss_gen_k("ECDSA deterministic k generator", curve->w.n, privateKey,
1842 digest, sizeof(digest));
1845 kG = ecp_mul(&curve->w.G, k);
1852 /* r = kG.x mod n */
1853 *r = bigmod(kG->x, curve->w.n);
1861 /* s = (z + r * priv)/k mod n */
1863 Bignum rPriv, zMod, first, firstMod, kInv;
1864 rPriv = modmul(*r, privateKey, curve->w.n);
1871 zMod = bigmod(z, curve->w.n);
1879 first = bigadd(rPriv, zMod);
1887 firstMod = bigmod(first, curve->w.n);
1894 kInv = modinv(k, curve->w.n);
1901 *s = modmul(firstMod, kInv, curve->w.n);
1911 /* ----------------------------------------------------------------------
1915 static void getstring(const char **data, int *datalen,
1916 const char **p, int *length)
1921 *length = toint(GET_32BIT(*data));
1926 if (*datalen < *length)
1930 *datalen -= *length;
1933 static Bignum getmp(const char **data, int *datalen)
1938 getstring(data, datalen, &p, &length);
1942 return NULL; /* negative mp */
1943 return bignum_from_bytes((unsigned char *)p, length);
1946 static int decodepoint(const char *p, int length, struct ec_point *point)
1948 if (length < 1 || p[0] != 0x04) /* Only support uncompressed point */
1950 /* Skip compression flag */
1953 /* The two values must be equal length */
1954 if (length % 2 != 0) {
1960 length = length / 2;
1961 point->x = bignum_from_bytes((unsigned char *)p, length);
1962 if (!point->x) return 0;
1964 point->y = bignum_from_bytes((unsigned char *)p, length);
1972 /* Verify the point is on the curve */
1973 if (!ec_point_verify(point)) {
1984 static int getmppoint(const char **data, int *datalen, struct ec_point *point)
1989 getstring(data, datalen, &p, &length);
1991 return decodepoint(p, length, point);
1994 /* ----------------------------------------------------------------------
1995 * Exposed ECDSA interface
1998 static void ecdsa_freekey(void *key)
2000 struct ec_key *ec = (struct ec_key *) key;
2003 if (ec->publicKey.x)
2004 freebn(ec->publicKey.x);
2005 if (ec->publicKey.y)
2006 freebn(ec->publicKey.y);
2007 if (ec->publicKey.z)
2008 freebn(ec->publicKey.z);
2010 freebn(ec->privateKey);
2014 static void *ecdsa_newkey(const char *data, int len)
2019 struct ec_curve *curve;
2021 getstring(&data, &len, &p, &slen);
2026 curve = ec_name_to_curve(p, slen);
2027 if (!curve) return NULL;
2029 if (curve->type != EC_WEIERSTRASS) {
2033 /* Curve name is duplicated for Weierstrass form */
2034 if (curve->type == EC_WEIERSTRASS) {
2035 getstring(&data, &len, &p, &slen);
2036 if (curve != ec_name_to_curve(p, slen)) return NULL;
2039 ec = snew(struct ec_key);
2041 ec->publicKey.curve = curve;
2042 ec->publicKey.infinity = 0;
2043 ec->publicKey.x = NULL;
2044 ec->publicKey.y = NULL;
2045 ec->publicKey.z = NULL;
2046 if (!getmppoint(&data, &len, &ec->publicKey)) {
2050 ec->privateKey = NULL;
2052 if (!ec->publicKey.x || !ec->publicKey.y ||
2053 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
2054 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
2063 static char *ecdsa_fmtkey(void *key)
2065 struct ec_key *ec = (struct ec_key *) key;
2067 int len, i, pos, nibbles;
2068 static const char hex[] = "0123456789abcdef";
2069 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
2072 pos = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0);
2073 if (pos == 0) return NULL;
2075 len = 4 + 2 + 1; /* 2 x "0x", punctuation, \0 */
2076 len += pos; /* Curve name */
2077 len += 4 * (bignum_bitcount(ec->publicKey.x) + 15) / 16;
2078 len += 4 * (bignum_bitcount(ec->publicKey.y) + 15) / 16;
2079 p = snewn(len, char);
2081 pos = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, (unsigned char*)p, pos);
2082 pos += sprintf(p + pos, ",0x");
2083 nibbles = (3 + bignum_bitcount(ec->publicKey.x)) / 4;
2086 for (i = nibbles; i--;) {
2088 hex[(bignum_byte(ec->publicKey.x, i / 2) >> (4 * (i % 2))) & 0xF];
2090 pos += sprintf(p + pos, ",0x");
2091 nibbles = (3 + bignum_bitcount(ec->publicKey.y)) / 4;
2094 for (i = nibbles; i--;) {
2096 hex[(bignum_byte(ec->publicKey.y, i / 2) >> (4 * (i % 2))) & 0xF];
2102 static unsigned char *ecdsa_public_blob(void *key, int *len)
2104 struct ec_key *ec = (struct ec_key *) key;
2105 int pointlen, bloblen, fullnamelen, namelen;
2107 unsigned char *blob, *p;
2109 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2110 fullnamelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0);
2111 if (fullnamelen == 0) return NULL;
2112 namelen = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0);
2113 if (namelen == 0) return NULL;
2115 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2118 * string "ecdsa-sha2-<name>", string "<name>", 0x04 point x, y.
2120 bloblen = 4 + fullnamelen + 4 + namelen + 4 + 1 + (pointlen * 2);
2121 blob = snewn(bloblen, unsigned char);
2124 PUT_32BIT(p, fullnamelen);
2126 p += ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, p, fullnamelen);
2127 PUT_32BIT(p, namelen);
2129 p += ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, p, namelen);
2130 PUT_32BIT(p, (2 * pointlen) + 1);
2133 for (i = pointlen; i--;) {
2134 *p++ = bignum_byte(ec->publicKey.x, i);
2136 for (i = pointlen; i--;) {
2137 *p++ = bignum_byte(ec->publicKey.y, i);
2143 assert(p == blob + bloblen);
2149 static unsigned char *ecdsa_private_blob(void *key, int *len)
2151 struct ec_key *ec = (struct ec_key *) key;
2152 int keylen, bloblen;
2154 unsigned char *blob, *p;
2156 if (!ec->privateKey) return NULL;
2158 keylen = (bignum_bitcount(ec->privateKey) + 8) / 8;
2161 * mpint privateKey. Total 4 + keylen.
2163 bloblen = 4 + keylen;
2164 blob = snewn(bloblen, unsigned char);
2167 PUT_32BIT(p, keylen);
2169 for (i = keylen; i--;)
2170 *p++ = bignum_byte(ec->privateKey, i);
2172 assert(p == blob + bloblen);
2177 static void *ecdsa_createkey(const unsigned char *pub_blob, int pub_len,
2178 const unsigned char *priv_blob, int priv_len)
2181 struct ec_point *publicKey;
2182 const char *pb = (const char *) priv_blob;
2184 ec = (struct ec_key*)ecdsa_newkey((const char *) pub_blob, pub_len);
2189 ec->privateKey = getmp(&pb, &priv_len);
2190 if (!ec->privateKey) {
2195 /* Check that private key generates public key */
2196 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
2199 bignum_cmp(publicKey->x, ec->publicKey.x) ||
2200 bignum_cmp(publicKey->y, ec->publicKey.y))
2205 ec_point_free(publicKey);
2210 static void *ecdsa_openssh_createkey(const unsigned char **blob, int *len)
2212 const char **b = (const char **) blob;
2216 struct ec_curve *curve;
2217 struct ec_point *publicKey;
2219 getstring(b, len, &p, &slen);
2224 curve = ec_name_to_curve(p, slen);
2225 if (!curve) return NULL;
2227 ec = snew(struct ec_key);
2229 ec->publicKey.curve = curve;
2230 ec->publicKey.infinity = 0;
2231 ec->publicKey.x = NULL;
2232 ec->publicKey.y = NULL;
2233 ec->publicKey.z = NULL;
2234 if (!getmppoint(b, len, &ec->publicKey)) {
2238 ec->privateKey = NULL;
2240 if (!ec->publicKey.x || !ec->publicKey.y ||
2241 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
2242 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
2248 ec->privateKey = getmp(b, len);
2249 if (ec->privateKey == NULL)
2255 /* Now check that the private key makes the public key */
2256 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
2263 if (bignum_cmp(ec->publicKey.x, publicKey->x) ||
2264 bignum_cmp(ec->publicKey.y, publicKey->y))
2266 /* Private key doesn't make the public key on the given curve */
2268 ec_point_free(publicKey);
2272 ec_point_free(publicKey);
2277 static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len)
2279 struct ec_key *ec = (struct ec_key *) key;
2287 if (ec->publicKey.curve->type != EC_WEIERSTRASS) {
2291 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2292 namelen = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0);
2294 4 + namelen /* <LEN> nistpXXX */
2295 + 4 + 1 + (pointlen * 2) /* <LEN> 0x04 pX pY */
2296 + ssh2_bignum_length(ec->privateKey);
2303 PUT_32BIT(blob+bloblen, namelen);
2306 bloblen += ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, blob+bloblen, namelen);
2308 PUT_32BIT(blob+bloblen, 1 + (pointlen * 2));
2310 blob[bloblen++] = 0x04;
2311 for (i = pointlen; i--; )
2312 blob[bloblen++] = bignum_byte(ec->publicKey.x, i);
2313 for (i = pointlen; i--; )
2314 blob[bloblen++] = bignum_byte(ec->publicKey.y, i);
2316 pointlen = (bignum_bitcount(ec->privateKey) + 8) / 8;
2317 PUT_32BIT(blob+bloblen, pointlen);
2319 for (i = pointlen; i--; )
2320 blob[bloblen++] = bignum_byte(ec->privateKey, i);
2325 static int ecdsa_pubkey_bits(const void *blob, int len)
2330 ec = (struct ec_key*)ecdsa_newkey((const char *) blob, len);
2333 ret = ec->publicKey.curve->fieldBits;
2339 static char *ecdsa_fingerprint(void *key)
2341 struct ec_key *ec = (struct ec_key *) key;
2342 struct MD5Context md5c;
2343 unsigned char digest[16], lenbuf[4];
2345 unsigned char *name, *fullname;
2346 int pointlen, namelen, fullnamelen, i, j;
2350 namelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0);
2351 name = snewn(namelen, unsigned char);
2352 ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, name, namelen);
2354 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2355 fullnamelen = ec_curve_to_name(EC_TYPE_CURVE, ec->publicKey.curve, NULL, 0);
2356 fullname = snewn(namelen, unsigned char);
2357 ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, fullname, fullnamelen);
2359 PUT_32BIT(lenbuf, fullnamelen);
2360 MD5Update(&md5c, lenbuf, 4);
2361 MD5Update(&md5c, fullname, fullnamelen);
2364 PUT_32BIT(lenbuf, namelen);
2365 MD5Update(&md5c, lenbuf, 4);
2366 MD5Update(&md5c, name, namelen);
2368 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2369 PUT_32BIT(lenbuf, 1 + (pointlen * 2));
2370 MD5Update(&md5c, lenbuf, 4);
2371 MD5Update(&md5c, (const unsigned char *)"\x04", 1);
2372 for (i = pointlen; i--; ) {
2373 unsigned char c = bignum_byte(ec->publicKey.x, i);
2374 MD5Update(&md5c, &c, 1);
2376 for (i = pointlen; i--; ) {
2377 unsigned char c = bignum_byte(ec->publicKey.y, i);
2378 MD5Update(&md5c, &c, 1);
2385 MD5Final(digest, &md5c);
2387 ret = snewn(namelen + 1 + (16 * 3), char);
2390 memcpy(ret, name, namelen);
2394 for (j = 0; j < 16; j++) {
2395 i += sprintf(ret + i, "%s%02x", j ? ":" : "", digest[j]);
2401 static int ecdsa_verifysig(void *key, const char *sig, int siglen,
2402 const char *data, int datalen)
2404 struct ec_key *ec = (struct ec_key *) key;
2407 unsigned char digest[512 / 8];
2412 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
2415 /* Check the signature curve matches the key curve */
2416 getstring(&sig, &siglen, &p, &slen);
2420 if (ec->publicKey.curve != ec_name_to_curve(p, slen)) {
2424 getstring(&sig, &siglen, &p, &slen);
2427 r = getmp(&p, &slen);
2429 s = getmp(&p, &slen);
2435 /* Perform correct hash function depending on curve size */
2436 if (ec->publicKey.curve->fieldBits <= 256) {
2437 SHA256_Simple(data, datalen, digest);
2438 digestLen = 256 / 8;
2439 } else if (ec->publicKey.curve->fieldBits <= 384) {
2440 SHA384_Simple(data, datalen, digest);
2441 digestLen = 384 / 8;
2443 SHA512_Simple(data, datalen, digest);
2444 digestLen = 512 / 8;
2447 /* Verify the signature */
2448 ret = _ecdsa_verify(&ec->publicKey, digest, digestLen, r, s);
2456 static unsigned char *ecdsa_sign(void *key, const char *data, int datalen,
2459 struct ec_key *ec = (struct ec_key *) key;
2460 unsigned char digest[512 / 8];
2462 Bignum r = NULL, s = NULL;
2463 unsigned char *buf, *p;
2464 int rlen, slen, namelen;
2467 if (!ec->privateKey || !ec->publicKey.curve) {
2471 /* Perform correct hash function depending on curve size */
2472 if (ec->publicKey.curve->fieldBits <= 256) {
2473 SHA256_Simple(data, datalen, digest);
2474 digestLen = 256 / 8;
2475 } else if (ec->publicKey.curve->fieldBits <= 384) {
2476 SHA384_Simple(data, datalen, digest);
2477 digestLen = 384 / 8;
2479 SHA512_Simple(data, datalen, digest);
2480 digestLen = 512 / 8;
2483 /* Do the signature */
2484 _ecdsa_sign(ec->privateKey, ec->publicKey.curve, digest, digestLen, &r, &s);
2491 rlen = (bignum_bitcount(r) + 8) / 8;
2492 slen = (bignum_bitcount(s) + 8) / 8;
2494 namelen = ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, NULL, 0);
2496 /* Format the output */
2497 *siglen = 8+namelen+rlen+slen+8;
2498 buf = snewn(*siglen, unsigned char);
2500 PUT_32BIT(p, namelen);
2502 p += ec_curve_to_name(EC_TYPE_DSA, ec->publicKey.curve, p, namelen);
2503 PUT_32BIT(p, rlen + slen + 8);
2507 for (i = rlen; i--;)
2508 *p++ = bignum_byte(r, i);
2511 for (i = slen; i--;)
2512 *p++ = bignum_byte(s, i);
2520 const struct ssh_signkey ssh_ecdsa_nistp256 = {
2527 ecdsa_openssh_createkey,
2528 ecdsa_openssh_fmtkey,
2529 3 /* curve name, point, private exponent */,
2534 "ecdsa-sha2-nistp256",
2535 "ecdsa-sha2-nistp256",
2538 const struct ssh_signkey ssh_ecdsa_nistp384 = {
2545 ecdsa_openssh_createkey,
2546 ecdsa_openssh_fmtkey,
2547 3 /* curve name, point, private exponent */,
2552 "ecdsa-sha2-nistp384",
2553 "ecdsa-sha2-nistp384",
2556 const struct ssh_signkey ssh_ecdsa_nistp521 = {
2563 ecdsa_openssh_createkey,
2564 ecdsa_openssh_fmtkey,
2565 3 /* curve name, point, private exponent */,
2570 "ecdsa-sha2-nistp521",
2571 "ecdsa-sha2-nistp521",
2574 /* ----------------------------------------------------------------------
2575 * Exposed ECDH interface
2578 static Bignum ecdh_calculate(const Bignum private,
2579 const struct ec_point *public)
2583 p = ecp_mul(public, private);
2584 if (!p) return NULL;
2588 if (p->curve->type == EC_MONTGOMERY) {
2589 /* Do conversion in network byte order */
2591 int bytes = (bignum_bitcount(ret)+7) / 8;
2592 unsigned char *byteorder = snewn(bytes, unsigned char);
2598 for (i = 0; i < bytes; ++i) {
2599 byteorder[i] = bignum_byte(ret, i);
2602 ret = bignum_from_bytes(byteorder, bytes);
2610 void *ssh_ecdhkex_newkey(const char *name)
2612 struct ec_curve *curve;
2614 struct ec_point *publicKey;
2616 curve = ec_name_to_curve(name, strlen(name));
2618 key = snew(struct ec_key);
2623 key->publicKey.curve = curve;
2625 if (curve->type == EC_MONTGOMERY) {
2626 unsigned char bytes[32] = {0};
2629 for (i = 0; i < sizeof(bytes); ++i)
2631 bytes[i] = (unsigned char)random_byte();
2636 key->privateKey = bignum_from_bytes(bytes, sizeof(bytes));
2637 for (i = 0; i < sizeof(bytes); ++i)
2639 ((volatile char*)bytes)[i] = 0;
2641 if (!key->privateKey) {
2645 publicKey = ecp_mul(&key->publicKey.curve->m.G, key->privateKey);
2647 freebn(key->privateKey);
2651 key->publicKey.x = publicKey->x;
2652 key->publicKey.y = publicKey->y;
2653 key->publicKey.z = NULL;
2656 key->privateKey = bignum_random_in_range(One, key->publicKey.curve->w.n);
2657 if (!key->privateKey) {
2661 publicKey = ecp_mul(&key->publicKey.curve->w.G, key->privateKey);
2663 freebn(key->privateKey);
2667 key->publicKey.x = publicKey->x;
2668 key->publicKey.y = publicKey->y;
2669 key->publicKey.z = NULL;
2675 char *ssh_ecdhkex_getpublic(void *key, int *len)
2677 struct ec_key *ec = (struct ec_key*)key;
2682 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2684 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2685 *len = 1 + pointlen * 2;
2689 point = (char*)snewn(*len, char);
2695 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2697 for (i = pointlen; i--;) {
2698 *p++ = bignum_byte(ec->publicKey.x, i);
2700 for (i = pointlen; i--;) {
2701 *p++ = bignum_byte(ec->publicKey.y, i);
2704 for (i = 0; i < pointlen; ++i) {
2705 *p++ = bignum_byte(ec->publicKey.x, i);
2712 Bignum ssh_ecdhkex_getkey(void *key, char *remoteKey, int remoteKeyLen)
2714 struct ec_key *ec = (struct ec_key*) key;
2715 struct ec_point remote;
2718 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2719 remote.curve = ec->publicKey.curve;
2720 remote.infinity = 0;
2721 if (!decodepoint(remoteKey, remoteKeyLen, &remote)) {
2725 /* Point length has to be the same length */
2726 if (remoteKeyLen != (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8) {
2730 remote.curve = ec->publicKey.curve;
2731 remote.infinity = 0;
2732 remote.x = bignum_from_bytes_le((unsigned char*)remoteKey, remoteKeyLen);
2737 ret = ecdh_calculate(ec->privateKey, &remote);
2738 if (remote.x) freebn(remote.x);
2739 if (remote.y) freebn(remote.y);
2743 void ssh_ecdhkex_freekey(void *key)
2748 static const struct ssh_kex ssh_ec_kex_curve25519 = {
2749 "curve25519-sha256@libssh.org", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha256
2752 static const struct ssh_kex ssh_ec_kex_nistp256 = {
2753 "ecdh-sha2-nistp256", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha256
2756 static const struct ssh_kex ssh_ec_kex_nistp384 = {
2757 "ecdh-sha2-nistp384", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha384
2760 static const struct ssh_kex ssh_ec_kex_nistp521 = {
2761 "ecdh-sha2-nistp521", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha512
2764 static const struct ssh_kex *const ec_kex_list[] = {
2765 &ssh_ec_kex_curve25519,
2766 &ssh_ec_kex_nistp256,
2767 &ssh_ec_kex_nistp384,
2768 &ssh_ec_kex_nistp521
2771 const struct ssh_kexes ssh_ecdh_kex = {
2772 sizeof(ec_kex_list) / sizeof(*ec_kex_list),