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)) {
1437 ec_point_free(point);
1444 static int getmppoint(char **data, int *datalen, struct ec_point *point)
1449 getstring(data, datalen, &p, &length);
1451 return decodepoint(p, length, point);
1454 /* ----------------------------------------------------------------------
1455 * Exposed ECDSA interface
1458 static void ecdsa_freekey(void *key)
1460 struct ec_key *ec = (struct ec_key *) key;
1463 if (ec->publicKey.x)
1464 freebn(ec->publicKey.x);
1465 if (ec->publicKey.y)
1466 freebn(ec->publicKey.y);
1467 if (ec->publicKey.z)
1468 freebn(ec->publicKey.z);
1470 freebn(ec->privateKey);
1474 static void *ecdsa_newkey(char *data, int len)
1479 struct ec_curve *curve;
1481 getstring(&data, &len, &p, &slen);
1483 if (!p || slen < 11 || memcmp(p, "ecdsa-sha2-", 11)) {
1486 curve = ec_name_to_curve(p+11, slen-11);
1487 if (!curve) return NULL;
1489 getstring(&data, &len, &p, &slen);
1491 if (curve != ec_name_to_curve(p, slen)) return NULL;
1493 ec = snew(struct ec_key);
1495 ec->publicKey.curve = curve;
1496 ec->publicKey.infinity = 0;
1497 ec->publicKey.x = NULL;
1498 ec->publicKey.y = NULL;
1499 ec->publicKey.z = NULL;
1500 if (!getmppoint(&data, &len, &ec->publicKey)) {
1504 ec->privateKey = NULL;
1506 if (!ec->publicKey.x || !ec->publicKey.y ||
1507 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
1508 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
1517 static char *ecdsa_fmtkey(void *key)
1519 struct ec_key *ec = (struct ec_key *) key;
1521 int len, i, pos, nibbles;
1522 static const char hex[] = "0123456789abcdef";
1523 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
1526 pos = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1527 if (pos == 0) return NULL;
1529 len = 4 + 2 + 1; /* 2 x "0x", punctuation, \0 */
1530 len += pos; /* Curve name */
1531 len += 4 * (bignum_bitcount(ec->publicKey.x) + 15) / 16;
1532 len += 4 * (bignum_bitcount(ec->publicKey.y) + 15) / 16;
1533 p = snewn(len, char);
1535 pos = ec_curve_to_name(ec->publicKey.curve, (unsigned char*)p, pos);
1536 pos += sprintf(p + pos, ",0x");
1537 nibbles = (3 + bignum_bitcount(ec->publicKey.x)) / 4;
1540 for (i = nibbles; i--;) {
1542 hex[(bignum_byte(ec->publicKey.x, i / 2) >> (4 * (i % 2))) & 0xF];
1544 pos += sprintf(p + pos, ",0x");
1545 nibbles = (3 + bignum_bitcount(ec->publicKey.y)) / 4;
1548 for (i = nibbles; i--;) {
1550 hex[(bignum_byte(ec->publicKey.y, i / 2) >> (4 * (i % 2))) & 0xF];
1556 static unsigned char *ecdsa_public_blob(void *key, int *len)
1558 struct ec_key *ec = (struct ec_key *) key;
1559 int pointlen, bloblen, namelen;
1561 unsigned char *blob, *p;
1563 namelen = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1564 if (namelen == 0) return NULL;
1566 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
1569 * string "ecdsa-sha2-<name>", string "<name>", 0x04 point x, y.
1571 bloblen = 4 + 11 + namelen + 4 + namelen + 4 + 1 + (pointlen * 2);
1572 blob = snewn(bloblen, unsigned char);
1575 PUT_32BIT(p, 11 + namelen);
1577 memcpy(p, "ecdsa-sha2-", 11);
1579 p += ec_curve_to_name(ec->publicKey.curve, p, namelen);
1580 PUT_32BIT(p, namelen);
1582 p += ec_curve_to_name(ec->publicKey.curve, p, namelen);
1583 PUT_32BIT(p, (2 * pointlen) + 1);
1586 for (i = pointlen; i--;)
1587 *p++ = bignum_byte(ec->publicKey.x, i);
1588 for (i = pointlen; i--;)
1589 *p++ = bignum_byte(ec->publicKey.y, i);
1591 assert(p == blob + bloblen);
1597 static unsigned char *ecdsa_private_blob(void *key, int *len)
1599 struct ec_key *ec = (struct ec_key *) key;
1600 int keylen, bloblen;
1602 unsigned char *blob, *p;
1604 if (!ec->privateKey) return NULL;
1606 keylen = (bignum_bitcount(ec->privateKey) + 8) / 8;
1609 * mpint privateKey. Total 4 + keylen.
1611 bloblen = 4 + keylen;
1612 blob = snewn(bloblen, unsigned char);
1615 PUT_32BIT(p, keylen);
1617 for (i = keylen; i--;)
1618 *p++ = bignum_byte(ec->privateKey, i);
1620 assert(p == blob + bloblen);
1625 static void *ecdsa_createkey(unsigned char *pub_blob, int pub_len,
1626 unsigned char *priv_blob, int priv_len)
1629 struct ec_point *publicKey;
1630 char *pb = (char *) priv_blob;
1632 ec = (struct ec_key*)ecdsa_newkey((char *) pub_blob, pub_len);
1637 ec->privateKey = getmp(&pb, &priv_len);
1638 if (!ec->privateKey) {
1643 /* Check that private key generates public key */
1644 publicKey = ecp_mul(&ec->publicKey.curve->G, ec->privateKey);
1647 bignum_cmp(publicKey->x, ec->publicKey.x) ||
1648 bignum_cmp(publicKey->y, ec->publicKey.y))
1653 ec_point_free(publicKey);
1658 static void *ecdsa_openssh_createkey(unsigned char **blob, int *len)
1660 char **b = (char **) blob;
1664 struct ec_curve *curve;
1665 struct ec_point *publicKey;
1667 getstring(b, len, &p, &slen);
1672 curve = ec_name_to_curve(p, slen);
1673 if (!curve) return NULL;
1675 ec = snew(struct ec_key);
1677 ec->publicKey.curve = curve;
1678 ec->publicKey.infinity = 0;
1679 ec->publicKey.x = NULL;
1680 ec->publicKey.y = NULL;
1681 ec->publicKey.z = NULL;
1682 if (!getmppoint(b, len, &ec->publicKey)) {
1686 ec->privateKey = NULL;
1688 if (!ec->publicKey.x || !ec->publicKey.y ||
1689 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
1690 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
1696 ec->privateKey = getmp(b, len);
1697 if (ec->privateKey == NULL)
1703 /* Now check that the private key makes the public key */
1704 publicKey = ecp_mul(&ec->publicKey.curve->G, ec->privateKey);
1711 if (bignum_cmp(ec->publicKey.x, publicKey->x) ||
1712 bignum_cmp(ec->publicKey.y, publicKey->y))
1714 /* Private key doesn't make the public key on the given curve */
1716 ec_point_free(publicKey);
1719 ec_point_free(publicKey);
1724 static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len)
1726 struct ec_key *ec = (struct ec_key *) key;
1728 int pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
1730 int namelen = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1733 4 + namelen /* <LEN> nistpXXX */
1734 + 4 + 1 + (pointlen * 2) /* <LEN> 0x04 pX pY */
1735 + ssh2_bignum_length(ec->privateKey);
1744 PUT_32BIT(blob+bloblen, namelen);
1747 bloblen += ec_curve_to_name(ec->publicKey.curve, blob+bloblen, namelen);
1749 PUT_32BIT(blob+bloblen, 1 + (pointlen * 2));
1751 blob[bloblen++] = 0x04;
1752 for (i = pointlen; i--; )
1753 blob[bloblen++] = bignum_byte(ec->publicKey.x, i);
1754 for (i = pointlen; i--; )
1755 blob[bloblen++] = bignum_byte(ec->publicKey.y, i);
1757 pointlen = (bignum_bitcount(ec->privateKey) + 8) / 8;
1758 PUT_32BIT(blob+bloblen, pointlen);
1760 for (i = pointlen; i--; )
1761 blob[bloblen++] = bignum_byte(ec->privateKey, i);
1766 static int ecdsa_pubkey_bits(void *blob, int len)
1771 ec = (struct ec_key*)ecdsa_newkey((char *) blob, len);
1774 ret = ec->publicKey.curve->fieldBits;
1780 static char *ecdsa_fingerprint(void *key)
1782 struct ec_key *ec = (struct ec_key *) key;
1783 struct MD5Context md5c;
1784 unsigned char digest[16], lenbuf[4];
1786 unsigned char *name;
1787 int pointlen, namelen, i, j;
1789 namelen = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1790 name = snewn(namelen, unsigned char);
1791 ec_curve_to_name(ec->publicKey.curve, name, namelen);
1795 PUT_32BIT(lenbuf, namelen + 11);
1796 MD5Update(&md5c, lenbuf, 4);
1797 MD5Update(&md5c, (const unsigned char *)"ecdsa-sha2-", 11);
1798 MD5Update(&md5c, name, namelen);
1800 PUT_32BIT(lenbuf, namelen);
1801 MD5Update(&md5c, lenbuf, 4);
1802 MD5Update(&md5c, name, namelen);
1804 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
1805 PUT_32BIT(lenbuf, 1 + (pointlen * 2));
1806 MD5Update(&md5c, lenbuf, 4);
1807 MD5Update(&md5c, (const unsigned char *)"\x04", 1);
1808 for (i = pointlen; i--; ) {
1809 unsigned char c = bignum_byte(ec->publicKey.x, i);
1810 MD5Update(&md5c, &c, 1);
1812 for (i = pointlen; i--; ) {
1813 unsigned char c = bignum_byte(ec->publicKey.y, i);
1814 MD5Update(&md5c, &c, 1);
1817 MD5Final(digest, &md5c);
1819 ret = snewn(11 + namelen + 1 + (16 * 3), char);
1822 memcpy(ret, "ecdsa-sha2-", 11);
1823 memcpy(ret+i, name, namelen);
1827 for (j = 0; j < 16; j++)
1828 i += sprintf(ret + i, "%s%02x", j ? ":" : "", digest[j]);
1833 static int ecdsa_verifysig(void *key, char *sig, int siglen,
1834 char *data, int datalen)
1836 struct ec_key *ec = (struct ec_key *) key;
1839 unsigned char digest[512 / 8];
1844 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
1847 /* Check the signature curve matches the key curve */
1848 getstring(&sig, &siglen, &p, &slen);
1849 if (!p || slen < 11 || memcmp(p, "ecdsa-sha2-", 11)) {
1852 if (ec->publicKey.curve != ec_name_to_curve(p+11, slen-11)) {
1856 getstring(&sig, &siglen, &p, &slen);
1857 r = getmp(&p, &slen);
1859 s = getmp(&p, &slen);
1865 /* Perform correct hash function depending on curve size */
1866 if (ec->publicKey.curve->fieldBits <= 256) {
1867 SHA256_Simple(data, datalen, digest);
1868 digestLen = 256 / 8;
1869 } else if (ec->publicKey.curve->fieldBits <= 384) {
1870 SHA384_Simple(data, datalen, digest);
1871 digestLen = 384 / 8;
1873 SHA512_Simple(data, datalen, digest);
1874 digestLen = 512 / 8;
1877 /* Verify the signature */
1878 if (!_ecdsa_verify(&ec->publicKey, digest, digestLen, r, s)) {
1890 static unsigned char *ecdsa_sign(void *key, char *data, int datalen,
1893 struct ec_key *ec = (struct ec_key *) key;
1894 unsigned char digest[512 / 8];
1896 Bignum r = NULL, s = NULL;
1897 unsigned char *buf, *p;
1898 int rlen, slen, namelen;
1901 if (!ec->privateKey || !ec->publicKey.curve) {
1905 /* Perform correct hash function depending on curve size */
1906 if (ec->publicKey.curve->fieldBits <= 256) {
1907 SHA256_Simple(data, datalen, digest);
1908 digestLen = 256 / 8;
1909 } else if (ec->publicKey.curve->fieldBits <= 384) {
1910 SHA384_Simple(data, datalen, digest);
1911 digestLen = 384 / 8;
1913 SHA512_Simple(data, datalen, digest);
1914 digestLen = 512 / 8;
1917 /* Do the signature */
1918 _ecdsa_sign(ec->privateKey, ec->publicKey.curve, digest, digestLen, &r, &s);
1925 rlen = (bignum_bitcount(r) + 8) / 8;
1926 slen = (bignum_bitcount(s) + 8) / 8;
1928 namelen = ec_curve_to_name(ec->publicKey.curve, NULL, 0);
1930 /* Format the output */
1931 *siglen = 8+11+namelen+rlen+slen+8;
1932 buf = snewn(*siglen, unsigned char);
1934 PUT_32BIT(p, 11+namelen);
1936 memcpy(p, "ecdsa-sha2-", 11);
1938 p += ec_curve_to_name(ec->publicKey.curve, p, namelen);
1939 PUT_32BIT(p, rlen + slen + 8);
1943 for (i = rlen; i--;)
1944 *p++ = bignum_byte(r, i);
1947 for (i = slen; i--;)
1948 *p++ = bignum_byte(s, i);
1953 const struct ssh_signkey ssh_ecdsa_nistp256 = {
1960 ecdsa_openssh_createkey,
1961 ecdsa_openssh_fmtkey,
1966 "ecdsa-sha2-nistp256",
1967 "ecdsa-sha2-nistp256",
1970 const struct ssh_signkey ssh_ecdsa_nistp384 = {
1977 ecdsa_openssh_createkey,
1978 ecdsa_openssh_fmtkey,
1983 "ecdsa-sha2-nistp384",
1984 "ecdsa-sha2-nistp384",
1987 const struct ssh_signkey ssh_ecdsa_nistp521 = {
1994 ecdsa_openssh_createkey,
1995 ecdsa_openssh_fmtkey,
2000 "ecdsa-sha2-nistp521",
2001 "ecdsa-sha2-nistp521",
2004 /* ----------------------------------------------------------------------
2005 * Exposed ECDH interface
2008 static Bignum ecdh_calculate(const Bignum private,
2009 const struct ec_point *public)
2013 p = ecp_mul(public, private);
2014 if (!p) return NULL;
2021 void *ssh_ecdhkex_newkey(struct ec_curve *curve)
2023 struct ec_key *key = snew(struct ec_key);
2024 struct ec_point *publicKey;
2025 key->publicKey.curve = curve;
2026 key->privateKey = bignum_random_in_range(One, key->publicKey.curve->n);
2027 if (!key->privateKey) {
2031 publicKey = ecp_mul(&key->publicKey.curve->G, key->privateKey);
2033 freebn(key->privateKey);
2037 key->publicKey.x = publicKey->x;
2038 key->publicKey.y = publicKey->y;
2039 key->publicKey.z = NULL;
2044 char *ssh_ecdhkex_getpublic(void *key, int *len)
2046 struct ec_key *ec = (struct ec_key*)key;
2049 int pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2051 *len = 1 + pointlen * 2;
2052 point = (char*)snewn(*len, char);
2056 for (i = pointlen; i--;)
2057 *p++ = bignum_byte(ec->publicKey.x, i);
2058 for (i = pointlen; i--;)
2059 *p++ = bignum_byte(ec->publicKey.y, i);
2064 Bignum ssh_ecdhkex_getkey(void *key, char *remoteKey, int remoteKeyLen)
2066 struct ec_key *ec = (struct ec_key*) key;
2067 struct ec_point remote;
2069 remote.curve = ec->publicKey.curve;
2070 remote.infinity = 0;
2071 if (!decodepoint(remoteKey, remoteKeyLen, &remote)) {
2075 return ecdh_calculate(ec->privateKey, &remote);
2078 void ssh_ecdhkex_freekey(void *key)
2083 static const struct ssh_kex ssh_ec_kex_nistp256 = {
2084 "ecdh-sha2-nistp256", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha256
2087 static const struct ssh_kex ssh_ec_kex_nistp384 = {
2088 "ecdh-sha2-nistp384", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha384
2091 static const struct ssh_kex ssh_ec_kex_nistp521 = {
2092 "ecdh-sha2-nistp521", NULL, KEXTYPE_ECDH, NULL, NULL, 0, 0, &ssh_sha512
2095 static const struct ssh_kex *const ec_kex_list[] = {
2096 &ssh_ec_kex_nistp256,
2097 &ssh_ec_kex_nistp384,
2098 &ssh_ec_kex_nistp521
2101 const struct ssh_kexes ssh_ecdh_kex = {
2102 sizeof(ec_kex_list) / sizeof(*ec_kex_list),