2 * Elliptic-curve crypto module for PuTTY
3 * Implements the three required curves, no optional curves
4 * NOTE: Only curves on prime field are handled by the maths functions
10 * Elliptic curves in SSH are specified in RFC 5656:
11 * http://tools.ietf.org/html/rfc5656
13 * That specification delegates details of public key formatting and a
14 * lot of underlying mechanism to SEC 1:
15 * http://www.secg.org/sec1-v2.pdf
23 /* ----------------------------------------------------------------------
24 * Elliptic curve definitions
27 static int initialise_curve(struct ec_curve *curve, int bits, unsigned char *p,
28 unsigned char *a, unsigned char *b,
29 unsigned char *n, unsigned char *Gx,
32 int length = bits / 8;
33 if (bits % 8) ++length;
35 curve->fieldBits = bits;
36 curve->p = bignum_from_bytes(p, length);
37 if (!curve->p) goto error;
39 /* Curve co-efficients */
40 curve->a = bignum_from_bytes(a, length);
41 if (!curve->a) goto error;
42 curve->b = bignum_from_bytes(b, length);
43 if (!curve->b) goto error;
45 /* Group order and generator */
46 curve->n = bignum_from_bytes(n, length);
47 if (!curve->n) goto error;
48 curve->G.x = bignum_from_bytes(Gx, length);
49 if (!curve->G.x) goto error;
50 curve->G.y = bignum_from_bytes(Gy, length);
51 if (!curve->G.y) goto error;
52 curve->G.curve = curve;
53 curve->G.infinity = 0;
57 if (curve->p) freebn(curve->p);
58 if (curve->a) freebn(curve->a);
59 if (curve->b) freebn(curve->b);
60 if (curve->n) freebn(curve->n);
61 if (curve->G.x) freebn(curve->G.x);
65 unsigned char nistp256_oid[] = {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07};
66 int nistp256_oid_len = 8;
67 unsigned char nistp384_oid[] = {0x2b, 0x81, 0x04, 0x00, 0x22};
68 int nistp384_oid_len = 5;
69 unsigned char nistp521_oid[] = {0x2b, 0x81, 0x04, 0x00, 0x23};
70 int nistp521_oid_len = 5;
72 struct ec_curve *ec_p256(void)
74 static struct ec_curve curve = { 0 };
75 static unsigned char initialised = 0;
80 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
81 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
82 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
83 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff
86 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
87 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
88 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
89 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc
92 0x5a, 0xc6, 0x35, 0xd8, 0xaa, 0x3a, 0x93, 0xe7,
93 0xb3, 0xeb, 0xbd, 0x55, 0x76, 0x98, 0x86, 0xbc,
94 0x65, 0x1d, 0x06, 0xb0, 0xcc, 0x53, 0xb0, 0xf6,
95 0x3b, 0xce, 0x3c, 0x3e, 0x27, 0xd2, 0x60, 0x4b
98 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
99 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
100 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
101 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51
103 unsigned char Gx[] = {
104 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47,
105 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2,
106 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0,
107 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96
109 unsigned char Gy[] = {
110 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b,
111 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e, 0x16,
112 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce,
113 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5
116 if (!initialise_curve(&curve, 256, p, a, b, n, Gx, Gy)) {
120 /* Now initialised, no need to do it again */
127 struct ec_curve *ec_p384(void)
129 static struct ec_curve curve = { 0 };
130 static unsigned char initialised = 0;
134 unsigned char p[] = {
135 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
136 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
137 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
138 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
139 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
140 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff
142 unsigned char a[] = {
143 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
144 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
145 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
146 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
147 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
148 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xfc
150 unsigned char b[] = {
151 0xb3, 0x31, 0x2f, 0xa7, 0xe2, 0x3e, 0xe7, 0xe4,
152 0x98, 0x8e, 0x05, 0x6b, 0xe3, 0xf8, 0x2d, 0x19,
153 0x18, 0x1d, 0x9c, 0x6e, 0xfe, 0x81, 0x41, 0x12,
154 0x03, 0x14, 0x08, 0x8f, 0x50, 0x13, 0x87, 0x5a,
155 0xc6, 0x56, 0x39, 0x8d, 0x8a, 0x2e, 0xd1, 0x9d,
156 0x2a, 0x85, 0xc8, 0xed, 0xd3, 0xec, 0x2a, 0xef
158 unsigned char n[] = {
159 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
160 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
161 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
162 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
163 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
164 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73
166 unsigned char Gx[] = {
167 0xaa, 0x87, 0xca, 0x22, 0xbe, 0x8b, 0x05, 0x37,
168 0x8e, 0xb1, 0xc7, 0x1e, 0xf3, 0x20, 0xad, 0x74,
169 0x6e, 0x1d, 0x3b, 0x62, 0x8b, 0xa7, 0x9b, 0x98,
170 0x59, 0xf7, 0x41, 0xe0, 0x82, 0x54, 0x2a, 0x38,
171 0x55, 0x02, 0xf2, 0x5d, 0xbf, 0x55, 0x29, 0x6c,
172 0x3a, 0x54, 0x5e, 0x38, 0x72, 0x76, 0x0a, 0xb7
174 unsigned char Gy[] = {
175 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f,
176 0x5d, 0x9e, 0x98, 0xbf, 0x92, 0x92, 0xdc, 0x29,
177 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c,
178 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0,
179 0x0a, 0x60, 0xb1, 0xce, 0x1d, 0x7e, 0x81, 0x9d,
180 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f
183 if (!initialise_curve(&curve, 384, p, a, b, n, Gx, Gy)) {
187 /* Now initialised, no need to do it again */
194 struct ec_curve *ec_p521(void)
196 static struct ec_curve curve = { 0 };
197 static unsigned char initialised = 0;
201 unsigned char p[] = {
202 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
203 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
204 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
205 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
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 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
212 unsigned char a[] = {
213 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
214 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
215 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
216 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
217 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
218 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
219 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
220 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
223 unsigned char b[] = {
224 0x00, 0x51, 0x95, 0x3e, 0xb9, 0x61, 0x8e, 0x1c,
225 0x9a, 0x1f, 0x92, 0x9a, 0x21, 0xa0, 0xb6, 0x85,
226 0x40, 0xee, 0xa2, 0xda, 0x72, 0x5b, 0x99, 0xb3,
227 0x15, 0xf3, 0xb8, 0xb4, 0x89, 0x91, 0x8e, 0xf1,
228 0x09, 0xe1, 0x56, 0x19, 0x39, 0x51, 0xec, 0x7e,
229 0x93, 0x7b, 0x16, 0x52, 0xc0, 0xbd, 0x3b, 0xb1,
230 0xbf, 0x07, 0x35, 0x73, 0xdf, 0x88, 0x3d, 0x2c,
231 0x34, 0xf1, 0xef, 0x45, 0x1f, 0xd4, 0x6b, 0x50,
234 unsigned char n[] = {
235 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
236 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
237 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
238 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
239 0xff, 0xfa, 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f,
240 0x96, 0x6b, 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09,
241 0xa5, 0xd0, 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c,
242 0x47, 0xae, 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38,
245 unsigned char Gx[] = {
246 0x00, 0xc6, 0x85, 0x8e, 0x06, 0xb7, 0x04, 0x04,
247 0xe9, 0xcd, 0x9e, 0x3e, 0xcb, 0x66, 0x23, 0x95,
248 0xb4, 0x42, 0x9c, 0x64, 0x81, 0x39, 0x05, 0x3f,
249 0xb5, 0x21, 0xf8, 0x28, 0xaf, 0x60, 0x6b, 0x4d,
250 0x3d, 0xba, 0xa1, 0x4b, 0x5e, 0x77, 0xef, 0xe7,
251 0x59, 0x28, 0xfe, 0x1d, 0xc1, 0x27, 0xa2, 0xff,
252 0xa8, 0xde, 0x33, 0x48, 0xb3, 0xc1, 0x85, 0x6a,
253 0x42, 0x9b, 0xf9, 0x7e, 0x7e, 0x31, 0xc2, 0xe5,
256 unsigned char Gy[] = {
257 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b,
258 0xc0, 0x04, 0x5c, 0x8a, 0x5f, 0xb4, 0x2c, 0x7d,
259 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b,
260 0x44, 0x68, 0x17, 0xaf, 0xbd, 0x17, 0x27, 0x3e,
261 0x66, 0x2c, 0x97, 0xee, 0x72, 0x99, 0x5e, 0xf4,
262 0x26, 0x40, 0xc5, 0x50, 0xb9, 0x01, 0x3f, 0xad,
263 0x07, 0x61, 0x35, 0x3c, 0x70, 0x86, 0xa2, 0x72,
264 0xc2, 0x40, 0x88, 0xbe, 0x94, 0x76, 0x9f, 0xd1,
268 if (!initialise_curve(&curve, 521, p, a, b, n, Gx, Gy)) {
272 /* Now initialised, no need to do it again */
279 static struct ec_curve *ec_name_to_curve(char *name, int len) {
280 if (len == 8 && !memcmp(name, "nistp", 5)) {
282 if (!memcmp(name, "256", 3)) {
284 } else if (!memcmp(name, "384", 3)) {
286 } else if (!memcmp(name, "521", 3)) {
294 static int ec_curve_to_name(const struct ec_curve *curve, unsigned char *name, int len) {
295 /* Return length of string */
296 if (name == NULL) return 8;
298 /* Not enough space for the name */
299 if (len < 8) return 0;
301 /* Put the name in the buffer */
302 switch (curve->fieldBits) {
304 memcpy(name+5, "256", 3);
307 memcpy(name+5, "384", 3);
310 memcpy(name+5, "521", 3);
316 memcpy(name, "nistp", 5);
320 /* Return 1 if a is -3 % p, otherwise return 0
321 * This is used because there are some maths optimisations */
322 static int ec_aminus3(const struct ec_curve *curve)
327 _p = bignum_add_long(curve->a, 3);
330 ret = !bignum_cmp(curve->p, _p);
335 /* ----------------------------------------------------------------------
336 * Elliptic curve field maths
339 static Bignum ecf_add(const Bignum a, const Bignum b,
340 const struct ec_curve *curve)
342 Bignum a1, b1, ab, ret;
344 a1 = bigmod(a, curve->p);
345 if (!a1) return NULL;
346 b1 = bigmod(b, curve->p);
356 if (!ab) return NULL;
358 ret = bigmod(ab, curve->p);
364 static Bignum ecf_square(const Bignum a, const struct ec_curve *curve)
366 return modmul(a, a, curve->p);
369 static Bignum ecf_treble(const Bignum a, const struct ec_curve *curve)
374 tmp = bignum_lshift(a, 1);
375 if (!tmp) return NULL;
377 /* Add itself (i.e. treble) */
378 ret = bigadd(tmp, a);
382 while (ret != NULL && bignum_cmp(ret, curve->p) >= 0)
384 tmp = bigsub(ret, curve->p);
392 static Bignum ecf_double(const Bignum a, const struct ec_curve *curve)
394 Bignum ret = bignum_lshift(a, 1);
395 if (!ret) return NULL;
396 if (bignum_cmp(ret, curve->p) >= 0)
398 Bignum tmp = bigsub(ret, curve->p);
408 /* ----------------------------------------------------------------------
412 void ec_point_free(struct ec_point *point)
414 if (point == NULL) return;
416 if (point->x) freebn(point->x);
417 if (point->y) freebn(point->y);
418 if (point->z) freebn(point->z);
423 static struct ec_point *ec_point_new(const struct ec_curve *curve,
424 const Bignum x, const Bignum y, const Bignum z,
425 unsigned char infinity)
427 struct ec_point *point = snewn(1, struct ec_point);
428 point->curve = curve;
432 point->infinity = infinity ? 1 : 0;
436 static struct ec_point *ec_point_copy(const struct ec_point *a)
438 if (a == NULL) return NULL;
439 return ec_point_new(a->curve,
440 a->x ? copybn(a->x) : NULL,
441 a->y ? copybn(a->y) : NULL,
442 a->z ? copybn(a->z) : NULL,
446 static int ec_point_verify(const struct ec_point *a)
454 /* Verify y^2 = x^3 + ax + b */
457 Bignum lhs = NULL, x3 = NULL, ax = NULL, x3ax = NULL, x3axm = NULL, x3axb = NULL, rhs = NULL;
459 Bignum Three = bignum_from_long(3);
460 if (!Three) return 0;
462 lhs = modmul(a->y, a->y, a->curve->p);
463 if (!lhs) goto error;
465 /* This uses montgomery multiplication to optimise */
466 x3 = modpow(a->x, Three, a->curve->p);
469 ax = modmul(a->curve->a, a->x, a->curve->p);
471 x3ax = bigadd(x3, ax);
472 if (!x3ax) goto error;
473 freebn(x3); x3 = NULL;
474 freebn(ax); ax = NULL;
475 x3axm = bigmod(x3ax, a->curve->p);
476 if (!x3axm) goto error;
477 freebn(x3ax); x3ax = NULL;
478 x3axb = bigadd(x3axm, a->curve->b);
479 if (!x3axb) goto error;
480 freebn(x3axm); x3axm = NULL;
481 rhs = bigmod(x3axb, a->curve->p);
482 if (!rhs) goto error;
485 ret = bignum_cmp(lhs, rhs) ? 0 : 1;
494 if (x3ax) freebn(x3ax);
495 if (x3axm) freebn(x3axm);
496 if (x3axb) freebn(x3axb);
497 if (lhs) freebn(lhs);
502 /* ----------------------------------------------------------------------
503 * Elliptic curve point maths
506 /* Returns 1 on success and 0 on memory error */
507 static int ecp_normalise(struct ec_point *a)
509 Bignum Z2, Z2inv, Z3, Z3inv, tx, ty;
511 /* In Jacobian Coordinates the triple (X, Y, Z) represents
512 the affine point (X / Z^2, Y / Z^3) */
518 /* Point is at infinity - i.e. normalised */
520 } else if (!a->x || !a->y) {
521 /* No point defined */
524 /* Already normalised */
528 Z2 = ecf_square(a->z, a->curve);
532 Z2inv = modinv(Z2, a->curve->p);
537 tx = modmul(a->x, Z2inv, a->curve->p);
544 Z3 = modmul(Z2, a->z, a->curve->p);
550 Z3inv = modinv(Z3, a->curve->p);
556 ty = modmul(a->y, Z3inv, a->curve->p);
572 static struct ec_point *ecp_double(const struct ec_point *a, const int aminus3)
574 Bignum S, M, outx, outy, outz;
576 if (a->infinity || bignum_cmp(a->y, Zero) == 0)
579 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
584 Bignum Y2, XY2, _2XY2;
586 Y2 = ecf_square(a->y, a->curve);
590 XY2 = modmul(a->x, Y2, a->curve->p);
596 _2XY2 = ecf_double(XY2, a->curve);
601 S = ecf_double(_2XY2, a->curve);
608 /* Faster calculation if a = -3 */
610 /* if a = -3, then M can also be calculated as M = 3*(X + Z^2)*(X - Z^2) */
611 Bignum Z2, XpZ2, XmZ2, second;
616 Z2 = ecf_square(a->z, a->curve);
623 XpZ2 = ecf_add(a->x, Z2, a->curve);
629 XmZ2 = modsub(a->x, Z2, a->curve->p);
637 second = modmul(XpZ2, XmZ2, a->curve->p);
645 M = ecf_treble(second, a->curve);
652 /* M = 3*X^2 + a*Z^4 */
653 Bignum _3X2, X2, aZ4;
656 aZ4 = copybn(a->curve->a);
660 Z2 = ecf_square(a->z, a->curve);
665 Z4 = ecf_square(Z2, a->curve);
671 aZ4 = modmul(a->curve->a, Z4, a->curve->p);
679 X2 = modmul(a->x, a->x, a->curve->p);
685 _3X2 = ecf_treble(X2, a->curve);
692 M = ecf_add(_3X2, aZ4, a->curve);
705 M2 = ecf_square(M, a->curve);
712 _2S = ecf_double(S, a->curve);
720 outx = modsub(M2, _2S, a->curve->p);
730 /* Y' = M*(S - X') - 8*Y^4 */
732 Bignum SX, MSX, Eight, Y2, Y4, _8Y4;
734 SX = modsub(S, outx, a->curve->p);
741 MSX = modmul(M, SX, a->curve->p);
748 Y2 = ecf_square(a->y, a->curve);
754 Y4 = ecf_square(Y2, a->curve);
761 Eight = bignum_from_long(8);
768 _8Y4 = modmul(Eight, Y4, a->curve->p);
776 outy = modsub(MSX, _8Y4, a->curve->p);
792 YZ = modmul(a->y, a->z, a->curve->p);
800 outz = ecf_double(YZ, a->curve);
809 return ec_point_new(a->curve, outx, outy, outz, 0);
812 static struct ec_point *ecp_add(const struct ec_point *a,
813 const struct ec_point *b,
816 Bignum U1, U2, S1, S2, outx, outy, outz;
818 /* Check if multiplying by infinity */
819 if (a->infinity) return ec_point_copy(b);
820 if (b->infinity) return ec_point_copy(a);
827 Z2 = ecf_square(b->z, a->curve);
831 U1 = modmul(a->x, Z2, a->curve->p);
836 Z3 = modmul(Z2, b->z, a->curve->p);
842 S1 = modmul(a->y, Z3, a->curve->p);
865 Z2 = ecf_square(a->z, b->curve);
871 U2 = modmul(b->x, Z2, b->curve->p);
878 Z3 = modmul(Z2, a->z, b->curve->p);
886 S2 = modmul(b->y, Z3, b->curve->p);
910 /* Check if multiplying by self */
911 if (bignum_cmp(U1, U2) == 0)
915 if (bignum_cmp(S1, S2) == 0)
919 return ecp_double(a, aminus3);
926 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
931 Bignum H, R, UH2, H3;
934 H = modsub(U2, U1, a->curve->p);
944 R = modsub(S2, S1, a->curve->p);
953 /* X3 = R^2 - H^3 - 2*U1*H^2 */
955 Bignum R2, H2, _2UH2, first;
957 H2 = ecf_square(H, a->curve);
965 UH2 = modmul(U1, H2, a->curve->p);
974 H3 = modmul(H2, H, a->curve->p);
983 R2 = ecf_square(R, a->curve);
992 _2UH2 = ecf_double(UH2, a->curve);
1002 first = modsub(R2, H3, a->curve->p);
1013 outx = modsub(first, _2UH2, a->curve->p);
1026 /* Y3 = R*(U1*H^2 - X3) - S1*H^3 */
1028 Bignum RUH2mX, UH2mX, SH3;
1030 UH2mX = modsub(UH2, outx, a->curve->p);
1040 RUH2mX = modmul(R, UH2mX, a->curve->p);
1050 SH3 = modmul(S1, H3, a->curve->p);
1060 outy = modsub(RUH2mX, SH3, a->curve->p);
1074 ZZ = modmul(a->z, b->z, a->curve->p);
1081 outz = modmul(H, ZZ, a->curve->p);
1090 outz = modmul(H, a->z, a->curve->p);
1098 outz = modmul(H, b->z, a->curve->p);
1110 return ec_point_new(a->curve, outx, outy, outz, 0);
1113 static struct ec_point *ecp_mul_(const struct ec_point *a, const Bignum b, int aminus3)
1115 struct ec_point *A, *ret;
1118 A = ec_point_copy(a);
1119 ret = ec_point_new(a->curve, NULL, NULL, NULL, 1);
1121 bits = bignum_bitcount(b);
1122 for (i = 0; ret != NULL && A != NULL && i < bits; ++i)
1124 if (bignum_bit(b, i))
1126 struct ec_point *tmp = ecp_add(ret, A, aminus3);
1132 struct ec_point *tmp = ecp_double(A, aminus3);
1148 /* Not static because it is used by sshecdsag.c to generate a new key */
1149 struct ec_point *ecp_mul(const struct ec_point *a, const Bignum b)
1151 struct ec_point *ret = ecp_mul_(a, b, ec_aminus3(a->curve));
1153 if (!ecp_normalise(ret)) {
1161 static struct ec_point *ecp_summul(const Bignum a, const Bignum b,
1162 const struct ec_point *point)
1164 struct ec_point *aG, *bP, *ret;
1165 int aminus3 = ec_aminus3(point->curve);
1167 aG = ecp_mul_(&point->curve->G, a, aminus3);
1168 if (!aG) return NULL;
1169 bP = ecp_mul_(point, b, aminus3);
1175 ret = ecp_add(aG, bP, aminus3);
1180 if (!ecp_normalise(ret)) {
1188 /* ----------------------------------------------------------------------
1189 * Basic sign and verify routines
1192 static int _ecdsa_verify(const struct ec_point *publicKey,
1193 const unsigned char *data, const int dataLen,
1194 const Bignum r, const Bignum s)
1201 if (bignum_cmp(r, Zero) == 0 || bignum_cmp(r, publicKey->curve->n) >= 0
1202 || bignum_cmp(s, Zero) == 0 || bignum_cmp(s, publicKey->curve->n) >= 0)
1207 /* z = left most bitlen(curve->n) of data */
1208 z = bignum_from_bytes(data, dataLen);
1210 n_bits = bignum_bitcount(publicKey->curve->n);
1211 z_bits = bignum_bitcount(z);
1212 if (z_bits > n_bits)
1214 Bignum tmp = bignum_rshift(z, z_bits - n_bits);
1220 /* Ensure z in range of n */
1222 Bignum tmp = bigmod(z, publicKey->curve->n);
1228 /* Calculate signature */
1230 Bignum w, x, u1, u2;
1231 struct ec_point *tmp;
1233 w = modinv(s, publicKey->curve->n);
1238 u1 = modmul(z, w, publicKey->curve->n);
1244 u2 = modmul(r, w, publicKey->curve->n);
1252 tmp = ecp_summul(u1, u2, publicKey);
1260 x = bigmod(tmp->x, publicKey->curve->n);
1267 valid = (bignum_cmp(r, x) == 0) ? 1 : 0;
1276 static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve,
1277 const unsigned char *data, const int dataLen,
1278 Bignum *r, Bignum *s)
1280 unsigned char digest[20];
1283 struct ec_point *kG;
1288 /* z = left most bitlen(curve->n) of data */
1289 z = bignum_from_bytes(data, dataLen);
1291 n_bits = bignum_bitcount(curve->n);
1292 z_bits = bignum_bitcount(z);
1293 if (z_bits > n_bits)
1296 tmp = bignum_rshift(z, z_bits - n_bits);
1302 /* Generate k between 1 and curve->n, using the same deterministic
1303 * k generation system we use for conventional DSA. */
1304 SHA_Simple(data, dataLen, digest);
1305 k = dss_gen_k("ECDSA deterministic k generator", curve->n, privateKey,
1306 digest, sizeof(digest));
1309 kG = ecp_mul(&curve->G, k);
1316 /* r = kG.x mod n */
1317 *r = bigmod(kG->x, curve->n);
1325 /* s = (z + r * priv)/k mod n */
1327 Bignum rPriv, zMod, first, firstMod, kInv;
1328 rPriv = modmul(*r, privateKey, curve->n);
1335 zMod = bigmod(z, curve->n);
1343 first = bigadd(rPriv, zMod);
1351 firstMod = bigmod(first, curve->n);
1358 kInv = modinv(k, curve->n);
1365 *s = modmul(firstMod, kInv, curve->n);
1375 /* ----------------------------------------------------------------------
1379 static void getstring(char **data, int *datalen, char **p, int *length)
1384 *length = toint(GET_32BIT(*data));
1389 if (*datalen < *length)
1393 *datalen -= *length;
1396 static Bignum getmp(char **data, int *datalen)
1401 getstring(data, datalen, &p, &length);
1405 return NULL; /* negative mp */
1406 return bignum_from_bytes((unsigned char *)p, length);
1409 static int decodepoint(char *p, int length, struct ec_point *point)
1411 if (length < 1 || p[0] != 0x04) /* Only support uncompressed point */
1413 /* Skip compression flag */
1416 /* The two values must be equal length */
1417 if (length % 2 != 0) {
1423 length = length / 2;
1424 point->x = bignum_from_bytes((unsigned char *)p, length);
1425 if (!point->x) return 0;
1427 point->y = bignum_from_bytes((unsigned char *)p, length);
1435 /* Verify the point is on the curve */
1436 if (!ec_point_verify(point)) {
1447 static int getmppoint(char **data, int *datalen, struct ec_point *point)
1452 getstring(data, datalen, &p, &length);
1454 return decodepoint(p, length, point);
1457 /* ----------------------------------------------------------------------
1458 * Exposed ECDSA interface
1461 static void ecdsa_freekey(void *key)
1463 struct ec_key *ec = (struct ec_key *) key;
1466 if (ec->publicKey.x)
1467 freebn(ec->publicKey.x);
1468 if (ec->publicKey.y)
1469 freebn(ec->publicKey.y);
1470 if (ec->publicKey.z)
1471 freebn(ec->publicKey.z);
1473 freebn(ec->privateKey);
1477 static void *ecdsa_newkey(char *data, int len)
1482 struct ec_curve *curve;
1484 getstring(&data, &len, &p, &slen);
1486 if (!p || slen < 11 || memcmp(p, "ecdsa-sha2-", 11)) {
1489 curve = ec_name_to_curve(p+11, slen-11);
1490 if (!curve) return NULL;
1492 getstring(&data, &len, &p, &slen);
1494 if (curve != ec_name_to_curve(p, slen)) return NULL;
1496 ec = snew(struct ec_key);
1498 ec->publicKey.curve = curve;
1499 ec->publicKey.infinity = 0;
1500 ec->publicKey.x = NULL;
1501 ec->publicKey.y = NULL;
1502 ec->publicKey.z = NULL;
1503 if (!getmppoint(&data, &len, &ec->publicKey)) {
1507 ec->privateKey = NULL;
1509 if (!ec->publicKey.x || !ec->publicKey.y ||
1510 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
1511 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
1520 static char *ecdsa_fmtkey(void *key)
1522 struct ec_key *ec = (struct ec_key *) key;
1524 int len, i, pos, nibbles;
1525 static const char hex[] = "0123456789abcdef";
1526 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
1529 pos = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1530 if (pos == 0) return NULL;
1532 len = 4 + 2 + 1; /* 2 x "0x", punctuation, \0 */
1533 len += pos; /* Curve name */
1534 len += 4 * (bignum_bitcount(ec->publicKey.x) + 15) / 16;
1535 len += 4 * (bignum_bitcount(ec->publicKey.y) + 15) / 16;
1536 p = snewn(len, char);
1538 pos = ec_curve_to_name(ec->publicKey.curve, (unsigned char*)p, pos);
1539 pos += sprintf(p + pos, ",0x");
1540 nibbles = (3 + bignum_bitcount(ec->publicKey.x)) / 4;
1543 for (i = nibbles; i--;) {
1545 hex[(bignum_byte(ec->publicKey.x, i / 2) >> (4 * (i % 2))) & 0xF];
1547 pos += sprintf(p + pos, ",0x");
1548 nibbles = (3 + bignum_bitcount(ec->publicKey.y)) / 4;
1551 for (i = nibbles; i--;) {
1553 hex[(bignum_byte(ec->publicKey.y, i / 2) >> (4 * (i % 2))) & 0xF];
1559 static unsigned char *ecdsa_public_blob(void *key, int *len)
1561 struct ec_key *ec = (struct ec_key *) key;
1562 int pointlen, bloblen, namelen;
1564 unsigned char *blob, *p;
1566 namelen = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1567 if (namelen == 0) return NULL;
1569 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
1572 * string "ecdsa-sha2-<name>", string "<name>", 0x04 point x, y.
1574 bloblen = 4 + 11 + namelen + 4 + namelen + 4 + 1 + (pointlen * 2);
1575 blob = snewn(bloblen, unsigned char);
1578 PUT_32BIT(p, 11 + namelen);
1580 memcpy(p, "ecdsa-sha2-", 11);
1582 p += ec_curve_to_name(ec->publicKey.curve, p, namelen);
1583 PUT_32BIT(p, namelen);
1585 p += ec_curve_to_name(ec->publicKey.curve, p, namelen);
1586 PUT_32BIT(p, (2 * pointlen) + 1);
1589 for (i = pointlen; i--;)
1590 *p++ = bignum_byte(ec->publicKey.x, i);
1591 for (i = pointlen; i--;)
1592 *p++ = bignum_byte(ec->publicKey.y, i);
1594 assert(p == blob + bloblen);
1600 static unsigned char *ecdsa_private_blob(void *key, int *len)
1602 struct ec_key *ec = (struct ec_key *) key;
1603 int keylen, bloblen;
1605 unsigned char *blob, *p;
1607 if (!ec->privateKey) return NULL;
1609 keylen = (bignum_bitcount(ec->privateKey) + 8) / 8;
1612 * mpint privateKey. Total 4 + keylen.
1614 bloblen = 4 + keylen;
1615 blob = snewn(bloblen, unsigned char);
1618 PUT_32BIT(p, keylen);
1620 for (i = keylen; i--;)
1621 *p++ = bignum_byte(ec->privateKey, i);
1623 assert(p == blob + bloblen);
1628 static void *ecdsa_createkey(unsigned char *pub_blob, int pub_len,
1629 unsigned char *priv_blob, int priv_len)
1632 struct ec_point *publicKey;
1633 char *pb = (char *) priv_blob;
1635 ec = (struct ec_key*)ecdsa_newkey((char *) pub_blob, pub_len);
1640 ec->privateKey = getmp(&pb, &priv_len);
1641 if (!ec->privateKey) {
1646 /* Check that private key generates public key */
1647 publicKey = ecp_mul(&ec->publicKey.curve->G, ec->privateKey);
1650 bignum_cmp(publicKey->x, ec->publicKey.x) ||
1651 bignum_cmp(publicKey->y, ec->publicKey.y))
1656 ec_point_free(publicKey);
1661 static void *ecdsa_openssh_createkey(unsigned char **blob, int *len)
1663 char **b = (char **) blob;
1667 struct ec_curve *curve;
1668 struct ec_point *publicKey;
1670 getstring(b, len, &p, &slen);
1675 curve = ec_name_to_curve(p, slen);
1676 if (!curve) return NULL;
1678 ec = snew(struct ec_key);
1680 ec->publicKey.curve = curve;
1681 ec->publicKey.infinity = 0;
1682 ec->publicKey.x = NULL;
1683 ec->publicKey.y = NULL;
1684 ec->publicKey.z = NULL;
1685 if (!getmppoint(b, len, &ec->publicKey)) {
1689 ec->privateKey = NULL;
1691 if (!ec->publicKey.x || !ec->publicKey.y ||
1692 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
1693 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
1699 ec->privateKey = getmp(b, len);
1700 if (ec->privateKey == NULL)
1706 /* Now check that the private key makes the public key */
1707 publicKey = ecp_mul(&ec->publicKey.curve->G, ec->privateKey);
1714 if (bignum_cmp(ec->publicKey.x, publicKey->x) ||
1715 bignum_cmp(ec->publicKey.y, publicKey->y))
1717 /* Private key doesn't make the public key on the given curve */
1719 ec_point_free(publicKey);
1723 ec_point_free(publicKey);
1728 static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len)
1730 struct ec_key *ec = (struct ec_key *) key;
1732 int pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
1734 int namelen = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1737 4 + namelen /* <LEN> nistpXXX */
1738 + 4 + 1 + (pointlen * 2) /* <LEN> 0x04 pX pY */
1739 + ssh2_bignum_length(ec->privateKey);
1748 PUT_32BIT(blob+bloblen, namelen);
1751 bloblen += ec_curve_to_name(ec->publicKey.curve, blob+bloblen, namelen);
1753 PUT_32BIT(blob+bloblen, 1 + (pointlen * 2));
1755 blob[bloblen++] = 0x04;
1756 for (i = pointlen; i--; )
1757 blob[bloblen++] = bignum_byte(ec->publicKey.x, i);
1758 for (i = pointlen; i--; )
1759 blob[bloblen++] = bignum_byte(ec->publicKey.y, i);
1761 pointlen = (bignum_bitcount(ec->privateKey) + 8) / 8;
1762 PUT_32BIT(blob+bloblen, pointlen);
1764 for (i = pointlen; i--; )
1765 blob[bloblen++] = bignum_byte(ec->privateKey, i);
1770 static int ecdsa_pubkey_bits(void *blob, int len)
1775 ec = (struct ec_key*)ecdsa_newkey((char *) blob, len);
1778 ret = ec->publicKey.curve->fieldBits;
1784 static char *ecdsa_fingerprint(void *key)
1786 struct ec_key *ec = (struct ec_key *) key;
1787 struct MD5Context md5c;
1788 unsigned char digest[16], lenbuf[4];
1790 unsigned char *name;
1791 int pointlen, namelen, i, j;
1793 namelen = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1794 name = snewn(namelen, unsigned char);
1795 ec_curve_to_name(ec->publicKey.curve, name, namelen);
1799 PUT_32BIT(lenbuf, namelen + 11);
1800 MD5Update(&md5c, lenbuf, 4);
1801 MD5Update(&md5c, (const unsigned char *)"ecdsa-sha2-", 11);
1802 MD5Update(&md5c, name, namelen);
1804 PUT_32BIT(lenbuf, namelen);
1805 MD5Update(&md5c, lenbuf, 4);
1806 MD5Update(&md5c, name, namelen);
1808 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
1809 PUT_32BIT(lenbuf, 1 + (pointlen * 2));
1810 MD5Update(&md5c, lenbuf, 4);
1811 MD5Update(&md5c, (const unsigned char *)"\x04", 1);
1812 for (i = pointlen; i--; ) {
1813 unsigned char c = bignum_byte(ec->publicKey.x, i);
1814 MD5Update(&md5c, &c, 1);
1816 for (i = pointlen; i--; ) {
1817 unsigned char c = bignum_byte(ec->publicKey.y, i);
1818 MD5Update(&md5c, &c, 1);
1821 MD5Final(digest, &md5c);
1823 ret = snewn(11 + namelen + 1 + (16 * 3), char);
1826 memcpy(ret, "ecdsa-sha2-", 11);
1827 memcpy(ret+i, name, namelen);
1831 for (j = 0; j < 16; j++)
1832 i += sprintf(ret + i, "%s%02x", j ? ":" : "", digest[j]);
1837 static int ecdsa_verifysig(void *key, char *sig, int siglen,
1838 char *data, int datalen)
1840 struct ec_key *ec = (struct ec_key *) key;
1843 unsigned char digest[512 / 8];
1848 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
1851 /* Check the signature curve matches the key curve */
1852 getstring(&sig, &siglen, &p, &slen);
1853 if (!p || slen < 11 || memcmp(p, "ecdsa-sha2-", 11)) {
1856 if (ec->publicKey.curve != ec_name_to_curve(p+11, slen-11)) {
1860 getstring(&sig, &siglen, &p, &slen);
1861 r = getmp(&p, &slen);
1863 s = getmp(&p, &slen);
1869 /* Perform correct hash function depending on curve size */
1870 if (ec->publicKey.curve->fieldBits <= 256) {
1871 SHA256_Simple(data, datalen, digest);
1872 digestLen = 256 / 8;
1873 } else if (ec->publicKey.curve->fieldBits <= 384) {
1874 SHA384_Simple(data, datalen, digest);
1875 digestLen = 384 / 8;
1877 SHA512_Simple(data, datalen, digest);
1878 digestLen = 512 / 8;
1881 /* Verify the signature */
1882 if (!_ecdsa_verify(&ec->publicKey, digest, digestLen, r, s)) {
1894 static unsigned char *ecdsa_sign(void *key, char *data, int datalen,
1897 struct ec_key *ec = (struct ec_key *) key;
1898 unsigned char digest[512 / 8];
1900 Bignum r = NULL, s = NULL;
1901 unsigned char *buf, *p;
1902 int rlen, slen, namelen;
1905 if (!ec->privateKey || !ec->publicKey.curve) {
1909 /* Perform correct hash function depending on curve size */
1910 if (ec->publicKey.curve->fieldBits <= 256) {
1911 SHA256_Simple(data, datalen, digest);
1912 digestLen = 256 / 8;
1913 } else if (ec->publicKey.curve->fieldBits <= 384) {
1914 SHA384_Simple(data, datalen, digest);
1915 digestLen = 384 / 8;
1917 SHA512_Simple(data, datalen, digest);
1918 digestLen = 512 / 8;
1921 /* Do the signature */
1922 _ecdsa_sign(ec->privateKey, ec->publicKey.curve, digest, digestLen, &r, &s);
1929 rlen = (bignum_bitcount(r) + 8) / 8;
1930 slen = (bignum_bitcount(s) + 8) / 8;
1932 namelen = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1934 /* Format the output */
1935 *siglen = 8+11+namelen+rlen+slen+8;
1936 buf = snewn(*siglen, unsigned char);
1938 PUT_32BIT(p, 11+namelen);
1940 memcpy(p, "ecdsa-sha2-", 11);
1942 p += ec_curve_to_name(ec->publicKey.curve, p, namelen);
1943 PUT_32BIT(p, rlen + slen + 8);
1947 for (i = rlen; i--;)
1948 *p++ = bignum_byte(r, i);
1951 for (i = slen; i--;)
1952 *p++ = bignum_byte(s, i);
1960 const struct ssh_signkey ssh_ecdsa_nistp256 = {
1967 ecdsa_openssh_createkey,
1968 ecdsa_openssh_fmtkey,
1973 "ecdsa-sha2-nistp256",
1974 "ecdsa-sha2-nistp256",
1977 const struct ssh_signkey ssh_ecdsa_nistp384 = {
1984 ecdsa_openssh_createkey,
1985 ecdsa_openssh_fmtkey,
1990 "ecdsa-sha2-nistp384",
1991 "ecdsa-sha2-nistp384",
1994 const struct ssh_signkey ssh_ecdsa_nistp521 = {
2001 ecdsa_openssh_createkey,
2002 ecdsa_openssh_fmtkey,
2007 "ecdsa-sha2-nistp521",
2008 "ecdsa-sha2-nistp521",
2011 /* ----------------------------------------------------------------------
2012 * Exposed ECDH interface
2015 static Bignum ecdh_calculate(const Bignum private,
2016 const struct ec_point *public)
2020 p = ecp_mul(public, private);
2021 if (!p) return NULL;
2028 void *ssh_ecdhkex_newkey(struct ec_curve *curve)
2030 struct ec_key *key = snew(struct ec_key);
2031 struct ec_point *publicKey;
2032 key->publicKey.curve = curve;
2033 key->privateKey = bignum_random_in_range(One, key->publicKey.curve->n);
2034 if (!key->privateKey) {
2038 publicKey = ecp_mul(&key->publicKey.curve->G, key->privateKey);
2040 freebn(key->privateKey);
2044 key->publicKey.x = publicKey->x;
2045 key->publicKey.y = publicKey->y;
2046 key->publicKey.z = NULL;
2051 char *ssh_ecdhkex_getpublic(void *key, int *len)
2053 struct ec_key *ec = (struct ec_key*)key;
2056 int pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2058 *len = 1 + pointlen * 2;
2059 point = (char*)snewn(*len, char);
2063 for (i = pointlen; i--;)
2064 *p++ = bignum_byte(ec->publicKey.x, i);
2065 for (i = pointlen; i--;)
2066 *p++ = bignum_byte(ec->publicKey.y, i);
2071 Bignum ssh_ecdhkex_getkey(void *key, char *remoteKey, int remoteKeyLen)
2073 struct ec_key *ec = (struct ec_key*) key;
2074 struct ec_point remote;
2076 remote.curve = ec->publicKey.curve;
2077 remote.infinity = 0;
2078 if (!decodepoint(remoteKey, remoteKeyLen, &remote)) {
2082 return ecdh_calculate(ec->privateKey, &remote);
2085 void ssh_ecdhkex_freekey(void *key)
2090 static const struct ssh_kex ssh_ec_kex_nistp256 = {
2091 "ecdh-sha2-nistp256", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha256
2094 static const struct ssh_kex ssh_ec_kex_nistp384 = {
2095 "ecdh-sha2-nistp384", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha384
2098 static const struct ssh_kex ssh_ec_kex_nistp521 = {
2099 "ecdh-sha2-nistp521", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha512
2102 static const struct ssh_kex *const ec_kex_list[] = {
2103 &ssh_ec_kex_nistp256,
2104 &ssh_ec_kex_nistp384,
2105 &ssh_ec_kex_nistp521
2108 const struct ssh_kexes ssh_ecdh_kex = {
2109 sizeof(ec_kex_list) / sizeof(*ec_kex_list),