2 * Elliptic-curve crypto module for PuTTY
3 * Implements the three required curves, no optional curves
5 * NOTE: Only curves on prime field are handled by the maths functions
6 * in Weierstrass form using Jacobian co-ordinates.
8 * Montgomery form curves are supported for DH. (Curve25519)
10 * Edwards form curves are supported for DSA. (Ed25519)
16 * Elliptic curves in SSH are specified in RFC 5656:
17 * http://tools.ietf.org/html/rfc5656
19 * That specification delegates details of public key formatting and a
20 * lot of underlying mechanism to SEC 1:
21 * http://www.secg.org/sec1-v2.pdf
23 * Montgomery maths from:
24 * Handbook of elliptic and hyperelliptic curve cryptography, Chapter 13
25 * http://cs.ucsb.edu/~koc/ccs130h/2013/EllipticHyperelliptic-CohenFrey.pdf
28 * http://ed25519.cr.yp.to/ed25519-20110926.pdf
36 /* ----------------------------------------------------------------------
37 * Elliptic curve definitions
40 static void initialise_wcurve(struct ec_curve *curve, int bits,
42 unsigned char *a, unsigned char *b,
43 unsigned char *n, unsigned char *Gx,
46 int length = bits / 8;
47 if (bits % 8) ++length;
49 curve->type = EC_WEIERSTRASS;
51 curve->fieldBits = bits;
52 curve->p = bignum_from_bytes(p, length);
54 /* Curve co-efficients */
55 curve->w.a = bignum_from_bytes(a, length);
56 curve->w.b = bignum_from_bytes(b, length);
58 /* Group order and generator */
59 curve->w.n = bignum_from_bytes(n, length);
60 curve->w.G.x = bignum_from_bytes(Gx, length);
61 curve->w.G.y = bignum_from_bytes(Gy, length);
62 curve->w.G.curve = curve;
63 curve->w.G.infinity = 0;
66 static void initialise_mcurve(struct ec_curve *curve, int bits,
68 unsigned char *a, unsigned char *b,
71 int length = bits / 8;
72 if (bits % 8) ++length;
74 curve->type = EC_MONTGOMERY;
76 curve->fieldBits = bits;
77 curve->p = bignum_from_bytes(p, length);
79 /* Curve co-efficients */
80 curve->m.a = bignum_from_bytes(a, length);
81 curve->m.b = bignum_from_bytes(b, length);
84 curve->m.G.x = bignum_from_bytes(Gx, length);
87 curve->m.G.curve = curve;
88 curve->m.G.infinity = 0;
91 static void initialise_ecurve(struct ec_curve *curve, int bits,
93 unsigned char *l, unsigned char *d,
94 unsigned char *Bx, unsigned char *By)
96 int length = bits / 8;
97 if (bits % 8) ++length;
99 curve->type = EC_EDWARDS;
101 curve->fieldBits = bits;
102 curve->p = bignum_from_bytes(p, length);
104 /* Curve co-efficients */
105 curve->e.l = bignum_from_bytes(l, length);
106 curve->e.d = bignum_from_bytes(d, length);
108 /* Group order and generator */
109 curve->e.B.x = bignum_from_bytes(Bx, length);
110 curve->e.B.y = bignum_from_bytes(By, length);
111 curve->e.B.curve = curve;
112 curve->e.B.infinity = 0;
115 static struct ec_curve *ec_p256(void)
117 static struct ec_curve curve = { 0 };
118 static unsigned char initialised = 0;
122 unsigned char p[] = {
123 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
124 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
125 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
126 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff
128 unsigned char a[] = {
129 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
130 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
131 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
132 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc
134 unsigned char b[] = {
135 0x5a, 0xc6, 0x35, 0xd8, 0xaa, 0x3a, 0x93, 0xe7,
136 0xb3, 0xeb, 0xbd, 0x55, 0x76, 0x98, 0x86, 0xbc,
137 0x65, 0x1d, 0x06, 0xb0, 0xcc, 0x53, 0xb0, 0xf6,
138 0x3b, 0xce, 0x3c, 0x3e, 0x27, 0xd2, 0x60, 0x4b
140 unsigned char n[] = {
141 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
142 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
143 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
144 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51
146 unsigned char Gx[] = {
147 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47,
148 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2,
149 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0,
150 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96
152 unsigned char Gy[] = {
153 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b,
154 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e, 0x16,
155 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce,
156 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5
159 initialise_wcurve(&curve, 256, p, a, b, n, Gx, Gy);
160 curve.name = "nistp256";
162 /* Now initialised, no need to do it again */
169 static struct ec_curve *ec_p384(void)
171 static struct ec_curve curve = { 0 };
172 static unsigned char initialised = 0;
176 unsigned char p[] = {
177 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
178 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
179 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
180 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
181 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
182 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff
184 unsigned char a[] = {
185 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
186 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
187 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
188 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
189 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
190 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xfc
192 unsigned char b[] = {
193 0xb3, 0x31, 0x2f, 0xa7, 0xe2, 0x3e, 0xe7, 0xe4,
194 0x98, 0x8e, 0x05, 0x6b, 0xe3, 0xf8, 0x2d, 0x19,
195 0x18, 0x1d, 0x9c, 0x6e, 0xfe, 0x81, 0x41, 0x12,
196 0x03, 0x14, 0x08, 0x8f, 0x50, 0x13, 0x87, 0x5a,
197 0xc6, 0x56, 0x39, 0x8d, 0x8a, 0x2e, 0xd1, 0x9d,
198 0x2a, 0x85, 0xc8, 0xed, 0xd3, 0xec, 0x2a, 0xef
200 unsigned char n[] = {
201 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
202 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
203 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
204 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
205 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
206 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73
208 unsigned char Gx[] = {
209 0xaa, 0x87, 0xca, 0x22, 0xbe, 0x8b, 0x05, 0x37,
210 0x8e, 0xb1, 0xc7, 0x1e, 0xf3, 0x20, 0xad, 0x74,
211 0x6e, 0x1d, 0x3b, 0x62, 0x8b, 0xa7, 0x9b, 0x98,
212 0x59, 0xf7, 0x41, 0xe0, 0x82, 0x54, 0x2a, 0x38,
213 0x55, 0x02, 0xf2, 0x5d, 0xbf, 0x55, 0x29, 0x6c,
214 0x3a, 0x54, 0x5e, 0x38, 0x72, 0x76, 0x0a, 0xb7
216 unsigned char Gy[] = {
217 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f,
218 0x5d, 0x9e, 0x98, 0xbf, 0x92, 0x92, 0xdc, 0x29,
219 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c,
220 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0,
221 0x0a, 0x60, 0xb1, 0xce, 0x1d, 0x7e, 0x81, 0x9d,
222 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f
225 initialise_wcurve(&curve, 384, p, a, b, n, Gx, Gy);
226 curve.name = "nistp384";
228 /* Now initialised, no need to do it again */
235 static struct ec_curve *ec_p521(void)
237 static struct ec_curve curve = { 0 };
238 static unsigned char initialised = 0;
242 unsigned char p[] = {
243 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
244 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
245 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
246 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
247 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
248 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
249 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
250 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
253 unsigned char a[] = {
254 0x01, 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,
257 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
258 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
259 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
260 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
261 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
264 unsigned char b[] = {
265 0x00, 0x51, 0x95, 0x3e, 0xb9, 0x61, 0x8e, 0x1c,
266 0x9a, 0x1f, 0x92, 0x9a, 0x21, 0xa0, 0xb6, 0x85,
267 0x40, 0xee, 0xa2, 0xda, 0x72, 0x5b, 0x99, 0xb3,
268 0x15, 0xf3, 0xb8, 0xb4, 0x89, 0x91, 0x8e, 0xf1,
269 0x09, 0xe1, 0x56, 0x19, 0x39, 0x51, 0xec, 0x7e,
270 0x93, 0x7b, 0x16, 0x52, 0xc0, 0xbd, 0x3b, 0xb1,
271 0xbf, 0x07, 0x35, 0x73, 0xdf, 0x88, 0x3d, 0x2c,
272 0x34, 0xf1, 0xef, 0x45, 0x1f, 0xd4, 0x6b, 0x50,
275 unsigned char n[] = {
276 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
277 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
278 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
279 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
280 0xff, 0xfa, 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f,
281 0x96, 0x6b, 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09,
282 0xa5, 0xd0, 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c,
283 0x47, 0xae, 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38,
286 unsigned char Gx[] = {
287 0x00, 0xc6, 0x85, 0x8e, 0x06, 0xb7, 0x04, 0x04,
288 0xe9, 0xcd, 0x9e, 0x3e, 0xcb, 0x66, 0x23, 0x95,
289 0xb4, 0x42, 0x9c, 0x64, 0x81, 0x39, 0x05, 0x3f,
290 0xb5, 0x21, 0xf8, 0x28, 0xaf, 0x60, 0x6b, 0x4d,
291 0x3d, 0xba, 0xa1, 0x4b, 0x5e, 0x77, 0xef, 0xe7,
292 0x59, 0x28, 0xfe, 0x1d, 0xc1, 0x27, 0xa2, 0xff,
293 0xa8, 0xde, 0x33, 0x48, 0xb3, 0xc1, 0x85, 0x6a,
294 0x42, 0x9b, 0xf9, 0x7e, 0x7e, 0x31, 0xc2, 0xe5,
297 unsigned char Gy[] = {
298 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b,
299 0xc0, 0x04, 0x5c, 0x8a, 0x5f, 0xb4, 0x2c, 0x7d,
300 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b,
301 0x44, 0x68, 0x17, 0xaf, 0xbd, 0x17, 0x27, 0x3e,
302 0x66, 0x2c, 0x97, 0xee, 0x72, 0x99, 0x5e, 0xf4,
303 0x26, 0x40, 0xc5, 0x50, 0xb9, 0x01, 0x3f, 0xad,
304 0x07, 0x61, 0x35, 0x3c, 0x70, 0x86, 0xa2, 0x72,
305 0xc2, 0x40, 0x88, 0xbe, 0x94, 0x76, 0x9f, 0xd1,
309 initialise_wcurve(&curve, 521, p, a, b, n, Gx, Gy);
310 curve.name = "nistp521";
312 /* Now initialised, no need to do it again */
319 static struct ec_curve *ec_curve25519(void)
321 static struct ec_curve curve = { 0 };
322 static unsigned char initialised = 0;
326 unsigned char p[] = {
327 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
328 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
329 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
330 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
332 unsigned char a[] = {
333 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
334 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
335 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
336 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x6d, 0x06
338 unsigned char b[] = {
339 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
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, 0x01
344 unsigned char gx[32] = {
345 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
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, 0x09
351 initialise_mcurve(&curve, 256, p, a, b, gx);
352 /* This curve doesn't need a name, because it's never used in
353 * any format that embeds the curve name */
356 /* Now initialised, no need to do it again */
363 static struct ec_curve *ec_ed25519(void)
365 static struct ec_curve curve = { 0 };
366 static unsigned char initialised = 0;
370 unsigned char q[] = {
371 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
372 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
373 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
374 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
376 unsigned char l[32] = {
377 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
378 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
379 0x14, 0xde, 0xf9, 0xde, 0xa2, 0xf7, 0x9c, 0xd6,
380 0x58, 0x12, 0x63, 0x1a, 0x5c, 0xf5, 0xd3, 0xed
382 unsigned char d[32] = {
383 0x52, 0x03, 0x6c, 0xee, 0x2b, 0x6f, 0xfe, 0x73,
384 0x8c, 0xc7, 0x40, 0x79, 0x77, 0x79, 0xe8, 0x98,
385 0x00, 0x70, 0x0a, 0x4d, 0x41, 0x41, 0xd8, 0xab,
386 0x75, 0xeb, 0x4d, 0xca, 0x13, 0x59, 0x78, 0xa3
388 unsigned char Bx[32] = {
389 0x21, 0x69, 0x36, 0xd3, 0xcd, 0x6e, 0x53, 0xfe,
390 0xc0, 0xa4, 0xe2, 0x31, 0xfd, 0xd6, 0xdc, 0x5c,
391 0x69, 0x2c, 0xc7, 0x60, 0x95, 0x25, 0xa7, 0xb2,
392 0xc9, 0x56, 0x2d, 0x60, 0x8f, 0x25, 0xd5, 0x1a
394 unsigned char By[32] = {
395 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
396 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
397 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
398 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x58
401 /* This curve doesn't need a name, because it's never used in
402 * any format that embeds the curve name */
405 initialise_ecurve(&curve, 256, q, l, d, Bx, By);
407 /* Now initialised, no need to do it again */
414 /* Return 1 if a is -3 % p, otherwise return 0
415 * This is used because there are some maths optimisations */
416 static int ec_aminus3(const struct ec_curve *curve)
421 if (curve->type != EC_WEIERSTRASS) {
425 _p = bignum_add_long(curve->w.a, 3);
427 ret = !bignum_cmp(curve->p, _p);
432 /* ----------------------------------------------------------------------
433 * Elliptic curve field maths
436 static Bignum ecf_add(const Bignum a, const Bignum b,
437 const struct ec_curve *curve)
439 Bignum a1, b1, ab, ret;
441 a1 = bigmod(a, curve->p);
442 b1 = bigmod(b, curve->p);
448 ret = bigmod(ab, curve->p);
454 static Bignum ecf_square(const Bignum a, const struct ec_curve *curve)
456 return modmul(a, a, curve->p);
459 static Bignum ecf_treble(const Bignum a, const struct ec_curve *curve)
464 tmp = bignum_lshift(a, 1);
466 /* Add itself (i.e. treble) */
467 ret = bigadd(tmp, a);
471 while (bignum_cmp(ret, curve->p) >= 0)
473 tmp = bigsub(ret, curve->p);
482 static Bignum ecf_double(const Bignum a, const struct ec_curve *curve)
484 Bignum ret = bignum_lshift(a, 1);
485 if (bignum_cmp(ret, curve->p) >= 0)
487 Bignum tmp = bigsub(ret, curve->p);
498 /* ----------------------------------------------------------------------
502 void ec_point_free(struct ec_point *point)
504 if (point == NULL) return;
506 if (point->x) freebn(point->x);
507 if (point->y) freebn(point->y);
508 if (point->z) freebn(point->z);
513 static struct ec_point *ec_point_new(const struct ec_curve *curve,
514 const Bignum x, const Bignum y, const Bignum z,
515 unsigned char infinity)
517 struct ec_point *point = snewn(1, struct ec_point);
518 point->curve = curve;
522 point->infinity = infinity ? 1 : 0;
526 static struct ec_point *ec_point_copy(const struct ec_point *a)
528 if (a == NULL) return NULL;
529 return ec_point_new(a->curve,
530 a->x ? copybn(a->x) : NULL,
531 a->y ? copybn(a->y) : NULL,
532 a->z ? copybn(a->z) : NULL,
536 static int ec_point_verify(const struct ec_point *a)
540 } else if (a->curve->type == EC_EDWARDS) {
541 /* Check y^2 - x^2 - 1 - d * x^2 * y^2 == 0 */
542 Bignum y2, x2, tmp, tmp2, tmp3;
545 y2 = ecf_square(a->y, a->curve);
546 x2 = ecf_square(a->x, a->curve);
547 tmp = modmul(a->curve->e.d, x2, a->curve->p);
548 tmp2 = modmul(tmp, y2, a->curve->p);
550 tmp = modsub(y2, x2, a->curve->p);
553 tmp3 = modsub(tmp, tmp2, a->curve->p);
556 ret = !bignum_cmp(tmp3, One);
559 } else if (a->curve->type == EC_WEIERSTRASS) {
560 /* Verify y^2 = x^3 + ax + b */
563 Bignum lhs = NULL, x3 = NULL, ax = NULL, x3ax = NULL, x3axm = NULL, x3axb = NULL, rhs = NULL;
565 Bignum Three = bignum_from_long(3);
567 lhs = modmul(a->y, a->y, a->curve->p);
569 /* This uses montgomery multiplication to optimise */
570 x3 = modpow(a->x, Three, a->curve->p);
572 ax = modmul(a->curve->w.a, a->x, a->curve->p);
573 x3ax = bigadd(x3, ax);
574 freebn(x3); x3 = NULL;
575 freebn(ax); ax = NULL;
576 x3axm = bigmod(x3ax, a->curve->p);
577 freebn(x3ax); x3ax = NULL;
578 x3axb = bigadd(x3axm, a->curve->w.b);
579 freebn(x3axm); x3axm = NULL;
580 rhs = bigmod(x3axb, a->curve->p);
583 ret = bignum_cmp(lhs, rhs) ? 0 : 1;
593 /* ----------------------------------------------------------------------
594 * Elliptic curve point maths
597 /* Returns 1 on success and 0 on memory error */
598 static int ecp_normalise(struct ec_point *a)
606 /* Point is at infinity - i.e. normalised */
610 if (a->curve->type == EC_WEIERSTRASS) {
611 /* In Jacobian Coordinates the triple (X, Y, Z) represents
612 the affine point (X / Z^2, Y / Z^3) */
614 Bignum Z2, Z2inv, Z3, Z3inv, tx, ty;
616 if (!a->x || !a->y) {
617 /* No point defined */
620 /* Already normalised */
624 Z2 = ecf_square(a->z, a->curve);
625 Z2inv = modinv(Z2, a->curve->p);
630 tx = modmul(a->x, Z2inv, a->curve->p);
633 Z3 = modmul(Z2, a->z, a->curve->p);
635 Z3inv = modinv(Z3, a->curve->p);
641 ty = modmul(a->y, Z3inv, a->curve->p);
651 } else if (a->curve->type == EC_MONTGOMERY) {
652 /* In Montgomery (X : Z) represents the x co-ord (X / Z, ?) */
657 /* No point defined */
660 /* Already normalised */
664 tmp = modinv(a->z, a->curve->p);
668 tmp2 = modmul(a->x, tmp, a->curve->p);
676 } else if (a->curve->type == EC_EDWARDS) {
677 /* Always normalised */
684 static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3)
686 Bignum S, M, outx, outy, outz;
688 if (bignum_cmp(a->y, Zero) == 0)
691 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
696 Bignum Y2, XY2, _2XY2;
698 Y2 = ecf_square(a->y, a->curve);
699 XY2 = modmul(a->x, Y2, a->curve->p);
702 _2XY2 = ecf_double(XY2, a->curve);
704 S = ecf_double(_2XY2, a->curve);
708 /* Faster calculation if a = -3 */
710 /* if a = -3, then M can also be calculated as M = 3*(X + Z^2)*(X - Z^2) */
711 Bignum Z2, XpZ2, XmZ2, second;
716 Z2 = ecf_square(a->z, a->curve);
719 XpZ2 = ecf_add(a->x, Z2, a->curve);
720 XmZ2 = modsub(a->x, Z2, a->curve->p);
723 second = modmul(XpZ2, XmZ2, a->curve->p);
727 M = ecf_treble(second, a->curve);
730 /* M = 3*X^2 + a*Z^4 */
731 Bignum _3X2, X2, aZ4;
734 aZ4 = copybn(a->curve->w.a);
738 Z2 = ecf_square(a->z, a->curve);
739 Z4 = ecf_square(Z2, a->curve);
741 aZ4 = modmul(a->curve->w.a, Z4, a->curve->p);
745 X2 = modmul(a->x, a->x, a->curve->p);
746 _3X2 = ecf_treble(X2, a->curve);
748 M = ecf_add(_3X2, aZ4, a->curve);
757 M2 = ecf_square(M, a->curve);
758 _2S = ecf_double(S, a->curve);
759 outx = modsub(M2, _2S, a->curve->p);
764 /* Y' = M*(S - X') - 8*Y^4 */
766 Bignum SX, MSX, Eight, Y2, Y4, _8Y4;
768 SX = modsub(S, outx, a->curve->p);
770 MSX = modmul(M, SX, a->curve->p);
773 Y2 = ecf_square(a->y, a->curve);
774 Y4 = ecf_square(Y2, a->curve);
776 Eight = bignum_from_long(8);
777 _8Y4 = modmul(Eight, Y4, a->curve->p);
780 outy = modsub(MSX, _8Y4, a->curve->p);
792 YZ = modmul(a->y, a->z, a->curve->p);
795 outz = ecf_double(YZ, a->curve);
799 return ec_point_new(a->curve, outx, outy, outz, 0);
802 static struct ec_point *ecp_doublem(const struct ec_point *a)
804 Bignum z, outx, outz, xpz, xmz;
811 /* 4xz = (x + z)^2 - (x - z)^2 */
815 tmp = ecf_add(a->x, z, a->curve);
816 xpz = ecf_square(tmp, a->curve);
819 tmp = modsub(a->x, z, a->curve->p);
820 xmz = ecf_square(tmp, a->curve);
824 /* outx = (x + z)^2 * (x - z)^2 */
825 outx = modmul(xpz, xmz, a->curve->p);
827 /* outz = 4xz * ((x - z)^2 + ((A + 2) / 4)*4xz) */
829 Bignum _4xz, tmp, tmp2, tmp3;
831 tmp = bignum_from_long(2);
832 tmp2 = ecf_add(a->curve->m.a, tmp, a->curve);
835 _4xz = modsub(xpz, xmz, a->curve->p);
837 tmp = modmul(tmp2, _4xz, a->curve->p);
840 tmp2 = bignum_from_long(4);
841 tmp3 = modinv(tmp2, a->curve->p);
850 tmp2 = modmul(tmp, tmp3, a->curve->p);
854 tmp = ecf_add(xmz, tmp2, a->curve);
857 outz = modmul(_4xz, tmp, a->curve->p);
862 return ec_point_new(a->curve, outx, NULL, outz, 0);
865 /* Forward declaration for Edwards curve doubling */
866 static struct ec_point *ecp_add(const struct ec_point *a,
867 const struct ec_point *b,
870 static struct ec_point *ecp_double(const struct ec_point *a, const int aminus3)
875 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
878 if (a->curve->type == EC_EDWARDS)
880 return ecp_add(a, a, aminus3);
882 else if (a->curve->type == EC_WEIERSTRASS)
884 return ecp_doublew(a, aminus3);
888 return ecp_doublem(a);
892 static struct ec_point *ecp_addw(const struct ec_point *a,
893 const struct ec_point *b,
896 Bignum U1, U2, S1, S2, outx, outy, outz;
903 Z2 = ecf_square(b->z, a->curve);
904 U1 = modmul(a->x, Z2, a->curve->p);
905 Z3 = modmul(Z2, b->z, a->curve->p);
907 S1 = modmul(a->y, Z3, a->curve->p);
919 Z2 = ecf_square(a->z, b->curve);
920 U2 = modmul(b->x, Z2, b->curve->p);
921 Z3 = modmul(Z2, a->z, b->curve->p);
923 S2 = modmul(b->y, Z3, b->curve->p);
930 /* Check if multiplying by self */
931 if (bignum_cmp(U1, U2) == 0)
935 if (bignum_cmp(S1, S2) == 0)
939 return ecp_double(a, aminus3);
946 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
951 Bignum H, R, UH2, H3;
954 H = modsub(U2, U1, a->curve->p);
958 R = modsub(S2, S1, a->curve->p);
961 /* X3 = R^2 - H^3 - 2*U1*H^2 */
963 Bignum R2, H2, _2UH2, first;
965 H2 = ecf_square(H, a->curve);
966 UH2 = modmul(U1, H2, a->curve->p);
968 H3 = modmul(H2, H, a->curve->p);
970 R2 = ecf_square(R, a->curve);
971 _2UH2 = ecf_double(UH2, a->curve);
972 first = modsub(R2, H3, a->curve->p);
974 outx = modsub(first, _2UH2, a->curve->p);
979 /* Y3 = R*(U1*H^2 - X3) - S1*H^3 */
981 Bignum RUH2mX, UH2mX, SH3;
983 UH2mX = modsub(UH2, outx, a->curve->p);
985 RUH2mX = modmul(R, UH2mX, a->curve->p);
988 SH3 = modmul(S1, H3, a->curve->p);
992 outy = modsub(RUH2mX, SH3, a->curve->p);
1001 ZZ = modmul(a->z, b->z, a->curve->p);
1002 outz = modmul(H, ZZ, a->curve->p);
1006 outz = modmul(H, a->z, a->curve->p);
1009 outz = modmul(H, b->z, a->curve->p);
1016 return ec_point_new(a->curve, outx, outy, outz, 0);
1019 static struct ec_point *ecp_addm(const struct ec_point *a,
1020 const struct ec_point *b,
1021 const struct ec_point *base)
1023 Bignum outx, outz, az, bz;
1034 /* a-b is maintained at 1 due to Montgomery ladder implementation */
1035 /* Xa+b = Za-b * ((Xa - Za)*(Xb + Zb) + (Xa + Za)*(Xb - Zb))^2 */
1036 /* Za+b = Xa-b * ((Xa - Za)*(Xb + Zb) - (Xa + Za)*(Xb - Zb))^2 */
1038 Bignum tmp, tmp2, tmp3, tmp4;
1040 /* (Xa + Za) * (Xb - Zb) */
1041 tmp = ecf_add(a->x, az, a->curve);
1042 tmp2 = modsub(b->x, bz, a->curve->p);
1043 tmp3 = modmul(tmp, tmp2, a->curve->p);
1047 /* (Xa - Za) * (Xb + Zb) */
1048 tmp = modsub(a->x, az, a->curve->p);
1049 tmp2 = ecf_add(b->x, bz, a->curve);
1050 tmp4 = modmul(tmp, tmp2, a->curve->p);
1054 tmp = ecf_add(tmp3, tmp4, a->curve);
1055 outx = ecf_square(tmp, a->curve);
1058 tmp = modsub(tmp3, tmp4, a->curve->p);
1061 tmp2 = ecf_square(tmp, a->curve);
1063 outz = modmul(base->x, tmp2, a->curve->p);
1067 return ec_point_new(a->curve, outx, NULL, outz, 0);
1070 static struct ec_point *ecp_adde(const struct ec_point *a,
1071 const struct ec_point *b)
1073 Bignum outx, outy, dmul;
1075 /* outx = (a->x * b->y + b->x * a->y) /
1076 * (1 + a->curve->e.d * a->x * b->x * a->y * b->y) */
1078 Bignum tmp, tmp2, tmp3, tmp4;
1080 tmp = modmul(a->x, b->y, a->curve->p);
1081 tmp2 = modmul(b->x, a->y, a->curve->p);
1082 tmp3 = ecf_add(tmp, tmp2, a->curve);
1084 tmp4 = modmul(tmp, tmp2, a->curve->p);
1087 dmul = modmul(a->curve->e.d, tmp4, a->curve->p);
1090 tmp = ecf_add(One, dmul, a->curve);
1091 tmp2 = modinv(tmp, a->curve->p);
1100 outx = modmul(tmp3, tmp2, a->curve->p);
1105 /* outy = (a->y * b->y + a->x * b->x) /
1106 * (1 - a->curve->e.d * a->x * b->x * a->y * b->y) */
1108 Bignum tmp, tmp2, tmp3, tmp4;
1110 tmp = modsub(One, dmul, a->curve->p);
1113 tmp2 = modinv(tmp, a->curve->p);
1121 tmp = modmul(a->y, b->y, a->curve->p);
1122 tmp3 = modmul(a->x, b->x, a->curve->p);
1123 tmp4 = ecf_add(tmp, tmp3, a->curve);
1127 outy = modmul(tmp4, tmp2, a->curve->p);
1132 return ec_point_new(a->curve, outx, outy, NULL, 0);
1135 static struct ec_point *ecp_add(const struct ec_point *a,
1136 const struct ec_point *b,
1139 if (a->curve != b->curve) {
1143 /* Check if multiplying by infinity */
1144 if (a->infinity) return ec_point_copy(b);
1145 if (b->infinity) return ec_point_copy(a);
1147 if (a->curve->type == EC_EDWARDS)
1149 return ecp_adde(a, b);
1152 if (a->curve->type == EC_WEIERSTRASS)
1154 return ecp_addw(a, b, aminus3);
1160 static struct ec_point *ecp_mul_(const struct ec_point *a, const Bignum b, int aminus3)
1162 struct ec_point *A, *ret;
1165 A = ec_point_copy(a);
1166 ret = ec_point_new(a->curve, NULL, NULL, NULL, 1);
1168 bits = bignum_bitcount(b);
1169 for (i = 0; i < bits; ++i)
1171 if (bignum_bit(b, i))
1173 struct ec_point *tmp = ecp_add(ret, A, aminus3);
1179 struct ec_point *tmp = ecp_double(A, aminus3);
1189 static struct ec_point *ecp_mulw(const struct ec_point *a, const Bignum b)
1191 struct ec_point *ret = ecp_mul_(a, b, ec_aminus3(a->curve));
1193 if (!ecp_normalise(ret)) {
1201 static struct ec_point *ecp_mule(const struct ec_point *a, const Bignum b)
1204 struct ec_point *ret;
1206 ret = ec_point_new(a->curve, NULL, NULL, NULL, 1);
1208 for (i = bignum_bitcount(b); i >= 0 && ret; --i)
1211 struct ec_point *tmp = ecp_double(ret, 0);
1215 if (ret && bignum_bit(b, i))
1217 struct ec_point *tmp = ecp_add(ret, a, 0);
1226 static struct ec_point *ecp_mulm(const struct ec_point *p, const Bignum n)
1228 struct ec_point *P1, *P2;
1231 /* P1 <- P and P2 <- [2]P */
1232 P2 = ecp_double(p, 0);
1233 P1 = ec_point_copy(p);
1235 /* for i = bits − 2 down to 0 */
1236 bits = bignum_bitcount(n);
1237 for (i = bits - 2; i >= 0; --i)
1239 if (!bignum_bit(n, i))
1242 struct ec_point *tmp = ecp_addm(P1, P2, p);
1247 tmp = ecp_double(P1, 0);
1254 struct ec_point *tmp = ecp_addm(P1, P2, p);
1259 tmp = ecp_double(P2, 0);
1267 if (!ecp_normalise(P1)) {
1275 /* Not static because it is used by sshecdsag.c to generate a new key */
1276 struct ec_point *ecp_mul(const struct ec_point *a, const Bignum b)
1278 if (a->curve->type == EC_WEIERSTRASS) {
1279 return ecp_mulw(a, b);
1280 } else if (a->curve->type == EC_EDWARDS) {
1281 return ecp_mule(a, b);
1283 return ecp_mulm(a, b);
1287 static struct ec_point *ecp_summul(const Bignum a, const Bignum b,
1288 const struct ec_point *point)
1290 struct ec_point *aG, *bP, *ret;
1293 if (point->curve->type != EC_WEIERSTRASS) {
1297 aminus3 = ec_aminus3(point->curve);
1299 aG = ecp_mul_(&point->curve->w.G, a, aminus3);
1300 if (!aG) return NULL;
1301 bP = ecp_mul_(point, b, aminus3);
1307 ret = ecp_add(aG, bP, aminus3);
1312 if (!ecp_normalise(ret)) {
1319 static Bignum *ecp_edx(const struct ec_curve *curve, const Bignum y)
1321 /* Get the x value on the given Edwards curve for a given y */
1324 /* xx = (y^2 - 1) / (d * y^2 + 1) */
1326 Bignum tmp, tmp2, tmp3;
1328 tmp = ecf_square(y, curve);
1329 tmp2 = modmul(curve->e.d, tmp, curve->p);
1330 tmp3 = ecf_add(tmp2, One, curve);
1332 tmp2 = modinv(tmp3, curve->p);
1339 tmp3 = modsub(tmp, One, curve->p);
1341 xx = modmul(tmp3, tmp2, curve->p);
1346 /* x = xx^((p + 3) / 8) */
1350 tmp = bignum_add_long(curve->p, 3);
1351 tmp2 = bignum_rshift(tmp, 3);
1353 x = modpow(xx, tmp2, curve->p);
1357 /* if x^2 - xx != 0 then x = x*(2^((p - 1) / 4)) */
1361 tmp = ecf_square(x, curve);
1362 tmp2 = modsub(tmp, xx, curve->p);
1365 if (bignum_cmp(tmp2, Zero)) {
1370 tmp = modsub(curve->p, One, curve->p);
1371 tmp2 = bignum_rshift(tmp, 2);
1373 tmp = bignum_from_long(2);
1374 tmp3 = modpow(tmp, tmp2, curve->p);
1378 tmp = modmul(x, tmp3, curve->p);
1387 /* if x % 2 != 0 then x = p - x */
1388 if (bignum_bit(x, 0)) {
1389 Bignum tmp = modsub(curve->p, x, curve->p);
1397 /* ----------------------------------------------------------------------
1398 * Public point from private
1401 struct ec_point *ec_public(const Bignum privateKey, const struct ec_curve *curve)
1403 if (curve->type == EC_WEIERSTRASS) {
1404 return ecp_mul(&curve->w.G, privateKey);
1405 } else if (curve->type == EC_EDWARDS) {
1406 /* hash = H(sk) (where hash creates 2 * fieldBits)
1408 * a = 2^(b-2) + SUM(2^i * h_i) for i = 2 -> b-2
1410 struct ec_point *ret;
1411 unsigned char hash[512/8];
1417 keylen = curve->fieldBits / 8;
1418 for (i = 0; i < keylen; ++i) {
1419 unsigned char b = bignum_byte(privateKey, i);
1420 SHA512_Bytes(&s, &b, 1);
1422 SHA512_Final(&s, hash);
1424 /* The second part is simply turning the hash into a Bignum,
1425 * however the 2^(b-2) bit *must* be set, and the bottom 3
1426 * bits *must* not be */
1427 hash[0] &= 0xf8; /* Unset bottom 3 bits (if set) */
1428 hash[31] &= 0x7f; /* Unset above (b-2) */
1429 hash[31] |= 0x40; /* Set 2^(b-2) */
1430 /* Chop off the top part and convert to int */
1431 a = bignum_from_bytes_le(hash, 32);
1433 ret = ecp_mul(&curve->e.B, a);
1441 /* ----------------------------------------------------------------------
1442 * Basic sign and verify routines
1445 static int _ecdsa_verify(const struct ec_point *publicKey,
1446 const unsigned char *data, const int dataLen,
1447 const Bignum r, const Bignum s)
1453 if (publicKey->curve->type != EC_WEIERSTRASS) {
1458 if (bignum_cmp(r, Zero) == 0 || bignum_cmp(r, publicKey->curve->w.n) >= 0
1459 || bignum_cmp(s, Zero) == 0 || bignum_cmp(s, publicKey->curve->w.n) >= 0)
1464 /* z = left most bitlen(curve->n) of data */
1465 z = bignum_from_bytes(data, dataLen);
1466 n_bits = bignum_bitcount(publicKey->curve->w.n);
1467 z_bits = bignum_bitcount(z);
1468 if (z_bits > n_bits)
1470 Bignum tmp = bignum_rshift(z, z_bits - n_bits);
1475 /* Ensure z in range of n */
1477 Bignum tmp = bigmod(z, publicKey->curve->w.n);
1482 /* Calculate signature */
1484 Bignum w, x, u1, u2;
1485 struct ec_point *tmp;
1487 w = modinv(s, publicKey->curve->w.n);
1492 u1 = modmul(z, w, publicKey->curve->w.n);
1493 u2 = modmul(r, w, publicKey->curve->w.n);
1496 tmp = ecp_summul(u1, u2, publicKey);
1504 x = bigmod(tmp->x, publicKey->curve->w.n);
1507 valid = (bignum_cmp(r, x) == 0) ? 1 : 0;
1516 static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve,
1517 const unsigned char *data, const int dataLen,
1518 Bignum *r, Bignum *s)
1520 unsigned char digest[20];
1523 struct ec_point *kG;
1528 if (curve->type != EC_WEIERSTRASS) {
1532 /* z = left most bitlen(curve->n) of data */
1533 z = bignum_from_bytes(data, dataLen);
1534 n_bits = bignum_bitcount(curve->w.n);
1535 z_bits = bignum_bitcount(z);
1536 if (z_bits > n_bits)
1539 tmp = bignum_rshift(z, z_bits - n_bits);
1544 /* Generate k between 1 and curve->n, using the same deterministic
1545 * k generation system we use for conventional DSA. */
1546 SHA_Simple(data, dataLen, digest);
1547 k = dss_gen_k("ECDSA deterministic k generator", curve->w.n, privateKey,
1548 digest, sizeof(digest));
1550 kG = ecp_mul(&curve->w.G, k);
1557 /* r = kG.x mod n */
1558 *r = bigmod(kG->x, curve->w.n);
1561 /* s = (z + r * priv)/k mod n */
1563 Bignum rPriv, zMod, first, firstMod, kInv;
1564 rPriv = modmul(*r, privateKey, curve->w.n);
1565 zMod = bigmod(z, curve->w.n);
1567 first = bigadd(rPriv, zMod);
1570 firstMod = bigmod(first, curve->w.n);
1572 kInv = modinv(k, curve->w.n);
1579 *s = modmul(firstMod, kInv, curve->w.n);
1585 /* ----------------------------------------------------------------------
1589 static void getstring(const char **data, int *datalen,
1590 const char **p, int *length)
1595 *length = toint(GET_32BIT(*data));
1600 if (*datalen < *length)
1604 *datalen -= *length;
1607 static Bignum getmp(const char **data, int *datalen)
1612 getstring(data, datalen, &p, &length);
1616 return NULL; /* negative mp */
1617 return bignum_from_bytes((unsigned char *)p, length);
1620 static Bignum getmp_le(const char **data, int *datalen)
1625 getstring(data, datalen, &p, &length);
1628 return bignum_from_bytes_le((const unsigned char *)p, length);
1631 static int decodepoint_ed(const char *p, int length, struct ec_point *point)
1633 /* Got some conversion to do, first read in the y co-ord */
1636 point->y = bignum_from_bytes_le((const unsigned char*)p, length);
1637 if ((unsigned)bignum_bitcount(point->y) > point->curve->fieldBits) {
1642 /* Read x bit and then reset it */
1643 negative = bignum_bit(point->y, point->curve->fieldBits - 1);
1644 bignum_set_bit(point->y, point->curve->fieldBits - 1, 0);
1646 /* Get the x from the y */
1647 point->x = ecp_edx(point->curve, point->y);
1654 Bignum tmp = modsub(point->curve->p, point->x, point->curve->p);
1659 /* Verify the point is on the curve */
1660 if (!ec_point_verify(point)) {
1671 static int decodepoint(const char *p, int length, struct ec_point *point)
1673 if (point->curve->type == EC_EDWARDS) {
1674 return decodepoint_ed(p, length, point);
1677 if (length < 1 || p[0] != 0x04) /* Only support uncompressed point */
1679 /* Skip compression flag */
1682 /* The two values must be equal length */
1683 if (length % 2 != 0) {
1689 length = length / 2;
1690 point->x = bignum_from_bytes((const unsigned char *)p, length);
1692 point->y = bignum_from_bytes((const unsigned char *)p, length);
1695 /* Verify the point is on the curve */
1696 if (!ec_point_verify(point)) {
1707 static int getmppoint(const char **data, int *datalen, struct ec_point *point)
1712 getstring(data, datalen, &p, &length);
1714 return decodepoint(p, length, point);
1717 /* ----------------------------------------------------------------------
1718 * Exposed ECDSA interface
1721 struct ecsign_extra {
1722 struct ec_curve *(*curve)(void);
1723 const struct ssh_hash *hash;
1725 /* These fields are used by the OpenSSH PEM format importer/exporter */
1726 const unsigned char *oid;
1730 static void ecdsa_freekey(void *key)
1732 struct ec_key *ec = (struct ec_key *) key;
1735 if (ec->publicKey.x)
1736 freebn(ec->publicKey.x);
1737 if (ec->publicKey.y)
1738 freebn(ec->publicKey.y);
1739 if (ec->publicKey.z)
1740 freebn(ec->publicKey.z);
1742 freebn(ec->privateKey);
1746 static void *ecdsa_newkey(const struct ssh_signkey *self,
1747 const char *data, int len)
1749 const struct ecsign_extra *extra =
1750 (const struct ecsign_extra *)self->extra;
1754 struct ec_curve *curve;
1756 getstring(&data, &len, &p, &slen);
1761 curve = extra->curve();
1762 assert(curve->type == EC_WEIERSTRASS || curve->type == EC_EDWARDS);
1764 /* Curve name is duplicated for Weierstrass form */
1765 if (curve->type == EC_WEIERSTRASS) {
1766 getstring(&data, &len, &p, &slen);
1767 if (!match_ssh_id(slen, p, curve->name)) return NULL;
1770 ec = snew(struct ec_key);
1773 ec->publicKey.curve = curve;
1774 ec->publicKey.infinity = 0;
1775 ec->publicKey.x = NULL;
1776 ec->publicKey.y = NULL;
1777 ec->publicKey.z = NULL;
1778 if (!getmppoint(&data, &len, &ec->publicKey)) {
1782 ec->privateKey = NULL;
1784 if (!ec->publicKey.x || !ec->publicKey.y ||
1785 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
1786 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
1795 static char *ecdsa_fmtkey(void *key)
1797 struct ec_key *ec = (struct ec_key *) key;
1799 int len, i, pos, nibbles;
1800 static const char hex[] = "0123456789abcdef";
1801 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
1804 len = 4 + 2 + 1; /* 2 x "0x", punctuation, \0 */
1805 if (ec->publicKey.curve->name)
1806 len += strlen(ec->publicKey.curve->name); /* Curve name */
1807 len += 4 * (bignum_bitcount(ec->publicKey.x) + 15) / 16;
1808 len += 4 * (bignum_bitcount(ec->publicKey.y) + 15) / 16;
1809 p = snewn(len, char);
1812 if (ec->publicKey.curve->name)
1813 pos += sprintf(p + pos, "%s,", ec->publicKey.curve->name);
1814 pos += sprintf(p + pos, "0x");
1815 nibbles = (3 + bignum_bitcount(ec->publicKey.x)) / 4;
1818 for (i = nibbles; i--;) {
1820 hex[(bignum_byte(ec->publicKey.x, i / 2) >> (4 * (i % 2))) & 0xF];
1822 pos += sprintf(p + pos, ",0x");
1823 nibbles = (3 + bignum_bitcount(ec->publicKey.y)) / 4;
1826 for (i = nibbles; i--;) {
1828 hex[(bignum_byte(ec->publicKey.y, i / 2) >> (4 * (i % 2))) & 0xF];
1834 static unsigned char *ecdsa_public_blob(void *key, int *len)
1836 struct ec_key *ec = (struct ec_key *) key;
1837 int pointlen, bloblen, fullnamelen, namelen;
1839 unsigned char *blob, *p;
1841 fullnamelen = strlen(ec->signalg->name);
1843 if (ec->publicKey.curve->type == EC_EDWARDS) {
1844 /* Edwards compressed form "ssh-ed25519" point y[:-1] + x[0:1] */
1846 pointlen = ec->publicKey.curve->fieldBits / 8;
1848 /* Can't handle this in our loop */
1849 if (pointlen < 2) return NULL;
1851 bloblen = 4 + fullnamelen + 4 + pointlen;
1852 blob = snewn(bloblen, unsigned char);
1855 PUT_32BIT(p, fullnamelen);
1857 memcpy(p, ec->signalg->name, fullnamelen);
1859 PUT_32BIT(p, pointlen);
1862 /* Unset last bit of y and set first bit of x in its place */
1863 for (i = 0; i < pointlen - 1; ++i) {
1864 *p++ = bignum_byte(ec->publicKey.y, i);
1866 /* Unset last bit of y and set first bit of x in its place */
1867 *p = bignum_byte(ec->publicKey.y, i) & 0x7f;
1868 *p++ |= bignum_bit(ec->publicKey.x, 0) << 7;
1869 } else if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
1870 assert(ec->publicKey.curve->name);
1871 namelen = strlen(ec->publicKey.curve->name);
1873 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
1876 * string "ecdsa-sha2-<name>", string "<name>", 0x04 point x, y.
1878 bloblen = 4 + fullnamelen + 4 + namelen + 4 + 1 + (pointlen * 2);
1879 blob = snewn(bloblen, unsigned char);
1882 PUT_32BIT(p, fullnamelen);
1884 memcpy(p, ec->signalg->name, fullnamelen);
1886 PUT_32BIT(p, namelen);
1888 memcpy(p, ec->publicKey.curve->name, namelen);
1890 PUT_32BIT(p, (2 * pointlen) + 1);
1893 for (i = pointlen; i--;) {
1894 *p++ = bignum_byte(ec->publicKey.x, i);
1896 for (i = pointlen; i--;) {
1897 *p++ = bignum_byte(ec->publicKey.y, i);
1903 assert(p == blob + bloblen);
1909 static unsigned char *ecdsa_private_blob(void *key, int *len)
1911 struct ec_key *ec = (struct ec_key *) key;
1912 int keylen, bloblen;
1914 unsigned char *blob, *p;
1916 if (!ec->privateKey) return NULL;
1918 if (ec->publicKey.curve->type == EC_EDWARDS) {
1920 keylen = (bignum_bitcount(ec->privateKey) + 7) / 8;
1923 keylen = (bignum_bitcount(ec->privateKey) + 8) / 8;
1927 * mpint privateKey. Total 4 + keylen.
1929 bloblen = 4 + keylen;
1930 blob = snewn(bloblen, unsigned char);
1933 PUT_32BIT(p, keylen);
1935 if (ec->publicKey.curve->type == EC_EDWARDS) {
1937 for (i = 0; i < keylen; ++i)
1938 *p++ = bignum_byte(ec->privateKey, i);
1940 for (i = keylen; i--;)
1941 *p++ = bignum_byte(ec->privateKey, i);
1944 assert(p == blob + bloblen);
1949 static void *ecdsa_createkey(const struct ssh_signkey *self,
1950 const unsigned char *pub_blob, int pub_len,
1951 const unsigned char *priv_blob, int priv_len)
1954 struct ec_point *publicKey;
1955 const char *pb = (const char *) priv_blob;
1957 ec = (struct ec_key*)ecdsa_newkey(self, (const char *) pub_blob, pub_len);
1962 if (ec->publicKey.curve->type != EC_WEIERSTRASS
1963 && ec->publicKey.curve->type != EC_EDWARDS) {
1968 if (ec->publicKey.curve->type == EC_EDWARDS) {
1969 ec->privateKey = getmp_le(&pb, &priv_len);
1971 ec->privateKey = getmp(&pb, &priv_len);
1973 if (!ec->privateKey) {
1978 /* Check that private key generates public key */
1979 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
1982 bignum_cmp(publicKey->x, ec->publicKey.x) ||
1983 bignum_cmp(publicKey->y, ec->publicKey.y))
1988 ec_point_free(publicKey);
1993 static void *ed25519_openssh_createkey(const struct ssh_signkey *self,
1994 const unsigned char **blob, int *len)
1997 struct ec_point *publicKey;
2001 getstring((const char**)blob, len, &p, &plen);
2007 ec = snew(struct ec_key);
2010 ec->publicKey.curve = ec_ed25519();
2011 ec->publicKey.infinity = 0;
2012 ec->privateKey = NULL;
2013 ec->publicKey.x = NULL;
2014 ec->publicKey.z = NULL;
2015 ec->publicKey.y = NULL;
2017 if (!decodepoint_ed(p, plen, &ec->publicKey))
2023 getstring((const char**)blob, len, &q, &qlen);
2029 ec->privateKey = bignum_from_bytes_le((const unsigned char *)q, 32);
2031 /* Check that private key generates public key */
2032 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
2035 bignum_cmp(publicKey->x, ec->publicKey.x) ||
2036 bignum_cmp(publicKey->y, ec->publicKey.y))
2041 ec_point_free(publicKey);
2043 /* The OpenSSH format for ed25519 private keys also for some
2044 * reason encodes an extra copy of the public key in the second
2045 * half of the secret-key string. Check that that's present and
2046 * correct as well, otherwise the key we think we've imported
2047 * won't behave identically to the way OpenSSH would have treated
2049 if (plen != 32 || 0 != memcmp(q + 32, p, 32)) {
2057 static int ed25519_openssh_fmtkey(void *key, unsigned char *blob, int len)
2059 struct ec_key *ec = (struct ec_key *) key;
2066 if (ec->publicKey.curve->type != EC_EDWARDS) {
2070 pointlen = (bignum_bitcount(ec->publicKey.y) + 7) / 8;
2071 keylen = (bignum_bitcount(ec->privateKey) + 7) / 8;
2072 bloblen = 4 + pointlen + 4 + keylen + pointlen;
2077 /* Encode the public point */
2078 PUT_32BIT(blob, pointlen);
2081 for (i = 0; i < pointlen - 1; ++i) {
2082 *blob++ = bignum_byte(ec->publicKey.y, i);
2084 /* Unset last bit of y and set first bit of x in its place */
2085 *blob = bignum_byte(ec->publicKey.y, i) & 0x7f;
2086 *blob++ |= bignum_bit(ec->publicKey.x, 0) << 7;
2088 PUT_32BIT(blob, keylen + pointlen);
2090 for (i = 0; i < keylen; ++i) {
2091 *blob++ = bignum_byte(ec->privateKey, i);
2093 /* Now encode an extra copy of the public point as the second half
2094 * of the private key string, as the OpenSSH format for some
2095 * reason requires */
2096 for (i = 0; i < pointlen - 1; ++i) {
2097 *blob++ = bignum_byte(ec->publicKey.y, i);
2099 /* Unset last bit of y and set first bit of x in its place */
2100 *blob = bignum_byte(ec->publicKey.y, i) & 0x7f;
2101 *blob++ |= bignum_bit(ec->publicKey.x, 0) << 7;
2106 static void *ecdsa_openssh_createkey(const struct ssh_signkey *self,
2107 const unsigned char **blob, int *len)
2109 const struct ecsign_extra *extra =
2110 (const struct ecsign_extra *)self->extra;
2111 const char **b = (const char **) blob;
2115 struct ec_curve *curve;
2116 struct ec_point *publicKey;
2118 getstring(b, len, &p, &slen);
2123 curve = extra->curve();
2124 assert(curve->type == EC_WEIERSTRASS);
2126 ec = snew(struct ec_key);
2129 ec->publicKey.curve = curve;
2130 ec->publicKey.infinity = 0;
2131 ec->publicKey.x = NULL;
2132 ec->publicKey.y = NULL;
2133 ec->publicKey.z = NULL;
2134 if (!getmppoint(b, len, &ec->publicKey)) {
2138 ec->privateKey = NULL;
2140 if (!ec->publicKey.x || !ec->publicKey.y ||
2141 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
2142 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
2148 ec->privateKey = getmp(b, len);
2149 if (ec->privateKey == NULL)
2155 /* Now check that the private key makes the public key */
2156 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
2163 if (bignum_cmp(ec->publicKey.x, publicKey->x) ||
2164 bignum_cmp(ec->publicKey.y, publicKey->y))
2166 /* Private key doesn't make the public key on the given curve */
2168 ec_point_free(publicKey);
2172 ec_point_free(publicKey);
2177 static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len)
2179 struct ec_key *ec = (struct ec_key *) key;
2186 if (ec->publicKey.curve->type != EC_WEIERSTRASS) {
2190 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2191 namelen = strlen(ec->publicKey.curve->name);
2193 4 + namelen /* <LEN> nistpXXX */
2194 + 4 + 1 + (pointlen * 2) /* <LEN> 0x04 pX pY */
2195 + ssh2_bignum_length(ec->privateKey);
2202 PUT_32BIT(blob+bloblen, namelen);
2204 memcpy(blob+bloblen, ec->publicKey.curve->name, namelen);
2207 PUT_32BIT(blob+bloblen, 1 + (pointlen * 2));
2209 blob[bloblen++] = 0x04;
2210 for (i = pointlen; i--; )
2211 blob[bloblen++] = bignum_byte(ec->publicKey.x, i);
2212 for (i = pointlen; i--; )
2213 blob[bloblen++] = bignum_byte(ec->publicKey.y, i);
2215 pointlen = (bignum_bitcount(ec->privateKey) + 8) / 8;
2216 PUT_32BIT(blob+bloblen, pointlen);
2218 for (i = pointlen; i--; )
2219 blob[bloblen++] = bignum_byte(ec->privateKey, i);
2224 static int ecdsa_pubkey_bits(const struct ssh_signkey *self,
2225 const void *blob, int len)
2230 ec = (struct ec_key*)ecdsa_newkey(self, (const char *) blob, len);
2233 ret = ec->publicKey.curve->fieldBits;
2239 static int ecdsa_verifysig(void *key, const char *sig, int siglen,
2240 const char *data, int datalen)
2242 struct ec_key *ec = (struct ec_key *) key;
2243 const struct ecsign_extra *extra =
2244 (const struct ecsign_extra *)ec->signalg->extra;
2250 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
2253 /* Check the signature starts with the algorithm name */
2254 getstring(&sig, &siglen, &p, &slen);
2258 if (!match_ssh_id(slen, p, ec->signalg->name)) {
2262 getstring(&sig, &siglen, &p, &slen);
2263 if (ec->publicKey.curve->type == EC_EDWARDS) {
2267 /* Check that the signature is two times the length of a point */
2268 if (slen != (ec->publicKey.curve->fieldBits / 8) * 2) {
2272 /* Check it's the 256 bit field so that SHA512 is the correct hash */
2273 if (ec->publicKey.curve->fieldBits != 256) {
2277 /* Get the signature */
2278 r = ec_point_new(ec->publicKey.curve, NULL, NULL, NULL, 0);
2282 if (!decodepoint(p, ec->publicKey.curve->fieldBits / 8, r)) {
2286 s = bignum_from_bytes_le((unsigned char*)p + (ec->publicKey.curve->fieldBits / 8),
2287 ec->publicKey.curve->fieldBits / 8);
2289 /* Get the hash of the encoded value of R + encoded value of pk + message */
2293 unsigned char digest[512 / 8];
2297 /* Add encoded r (no need to encode it again, it was in the signature) */
2298 SHA512_Bytes(&hs, p, ec->publicKey.curve->fieldBits / 8);
2300 /* Encode pk and add it */
2301 pointlen = ec->publicKey.curve->fieldBits / 8;
2302 for (i = 0; i < pointlen - 1; ++i) {
2303 b = bignum_byte(ec->publicKey.y, i);
2304 SHA512_Bytes(&hs, &b, 1);
2306 /* Unset last bit of y and set first bit of x in its place */
2307 b = bignum_byte(ec->publicKey.y, i) & 0x7f;
2308 b |= bignum_bit(ec->publicKey.x, 0) << 7;
2309 SHA512_Bytes(&hs, &b, 1);
2311 /* Add the message itself */
2312 SHA512_Bytes(&hs, data, datalen);
2315 SHA512_Final(&hs, digest);
2317 /* Convert to Bignum */
2318 h = bignum_from_bytes_le(digest, sizeof(digest));
2321 /* Verify sB == r + h*publicKey */
2323 struct ec_point *lhs, *rhs, *tmp;
2326 lhs = ecp_mul(&ec->publicKey.curve->e.B, s);
2334 /* rhs = r + h*publicKey */
2335 tmp = ecp_mul(&ec->publicKey, h);
2342 rhs = ecp_add(r, tmp, 0);
2350 /* Check the point is the same */
2351 ret = !bignum_cmp(lhs->x, rhs->x);
2353 ret = !bignum_cmp(lhs->y, rhs->y);
2363 unsigned char digest[512 / 8];
2366 r = getmp(&p, &slen);
2368 s = getmp(&p, &slen);
2374 digestLen = extra->hash->hlen;
2375 assert(digestLen <= sizeof(digest));
2376 hashctx = extra->hash->init();
2377 extra->hash->bytes(hashctx, data, datalen);
2378 extra->hash->final(hashctx, digest);
2380 /* Verify the signature */
2381 ret = _ecdsa_verify(&ec->publicKey, digest, digestLen, r, s);
2390 static unsigned char *ecdsa_sign(void *key, const char *data, int datalen,
2393 struct ec_key *ec = (struct ec_key *) key;
2394 const struct ecsign_extra *extra =
2395 (const struct ecsign_extra *)ec->signalg->extra;
2396 unsigned char digest[512 / 8];
2398 Bignum r = NULL, s = NULL;
2399 unsigned char *buf, *p;
2400 int rlen, slen, namelen;
2403 if (!ec->privateKey || !ec->publicKey.curve) {
2407 if (ec->publicKey.curve->type == EC_EDWARDS) {
2408 struct ec_point *rp;
2409 int pointlen = ec->publicKey.curve->fieldBits / 8;
2411 /* hash = H(sk) (where hash creates 2 * fieldBits)
2413 * a = 2^(b-2) + SUM(2^i * h_i) for i = 2 -> b-2
2414 * r = H(h[b/8:b/4] + m)
2416 * S = (r + H(encodepoint(R) + encodepoint(pk) + m) * a) % l */
2418 unsigned char hash[512/8];
2424 for (i = 0; i < pointlen; ++i) {
2425 unsigned char b = (unsigned char)bignum_byte(ec->privateKey, i);
2426 SHA512_Bytes(&hs, &b, 1);
2429 SHA512_Final(&hs, hash);
2431 /* The second part is simply turning the hash into a
2432 * Bignum, however the 2^(b-2) bit *must* be set, and the
2433 * bottom 3 bits *must* not be */
2434 hash[0] &= 0xf8; /* Unset bottom 3 bits (if set) */
2435 hash[31] &= 0x7f; /* Unset above (b-2) */
2436 hash[31] |= 0x40; /* Set 2^(b-2) */
2437 /* Chop off the top part and convert to int */
2438 a = bignum_from_bytes_le(hash, 32);
2442 hash+(ec->publicKey.curve->fieldBits / 8),
2443 (ec->publicKey.curve->fieldBits / 4)
2444 - (ec->publicKey.curve->fieldBits / 8));
2445 SHA512_Bytes(&hs, data, datalen);
2446 SHA512_Final(&hs, hash);
2448 r = bignum_from_bytes_le(hash, 512/8);
2449 rp = ecp_mul(&ec->publicKey.curve->e.B, r);
2456 /* Now calculate s */
2458 /* Encode the point R */
2459 for (i = 0; i < pointlen - 1; ++i) {
2460 b = bignum_byte(rp->y, i);
2461 SHA512_Bytes(&hs, &b, 1);
2463 /* Unset last bit of y and set first bit of x in its place */
2464 b = bignum_byte(rp->y, i) & 0x7f;
2465 b |= bignum_bit(rp->x, 0) << 7;
2466 SHA512_Bytes(&hs, &b, 1);
2468 /* Encode the point pk */
2469 for (i = 0; i < pointlen - 1; ++i) {
2470 b = bignum_byte(ec->publicKey.y, i);
2471 SHA512_Bytes(&hs, &b, 1);
2473 /* Unset last bit of y and set first bit of x in its place */
2474 b = bignum_byte(ec->publicKey.y, i) & 0x7f;
2475 b |= bignum_bit(ec->publicKey.x, 0) << 7;
2476 SHA512_Bytes(&hs, &b, 1);
2478 /* Add the message */
2479 SHA512_Bytes(&hs, data, datalen);
2480 SHA512_Final(&hs, hash);
2485 tmp = bignum_from_bytes_le(hash, 512/8);
2486 tmp2 = modmul(tmp, a, ec->publicKey.curve->e.l);
2489 tmp = bigadd(r, tmp2);
2492 s = bigmod(tmp, ec->publicKey.curve->e.l);
2497 /* Format the output */
2498 namelen = strlen(ec->signalg->name);
2499 *siglen = 4+namelen+4+((ec->publicKey.curve->fieldBits / 8)*2);
2500 buf = snewn(*siglen, unsigned char);
2502 PUT_32BIT(p, namelen);
2504 memcpy(p, ec->signalg->name, namelen);
2506 PUT_32BIT(p, ((ec->publicKey.curve->fieldBits / 8)*2));
2509 /* Encode the point */
2510 pointlen = ec->publicKey.curve->fieldBits / 8;
2511 for (i = 0; i < pointlen - 1; ++i) {
2512 *p++ = bignum_byte(rp->y, i);
2514 /* Unset last bit of y and set first bit of x in its place */
2515 *p = bignum_byte(rp->y, i) & 0x7f;
2516 *p++ |= bignum_bit(rp->x, 0) << 7;
2519 /* Encode the int */
2520 for (i = 0; i < pointlen; ++i) {
2521 *p++ = bignum_byte(s, i);
2527 digestLen = extra->hash->hlen;
2528 assert(digestLen <= sizeof(digest));
2529 hashctx = extra->hash->init();
2530 extra->hash->bytes(hashctx, data, datalen);
2531 extra->hash->final(hashctx, digest);
2533 /* Do the signature */
2534 _ecdsa_sign(ec->privateKey, ec->publicKey.curve, digest, digestLen, &r, &s);
2541 rlen = (bignum_bitcount(r) + 8) / 8;
2542 slen = (bignum_bitcount(s) + 8) / 8;
2544 namelen = strlen(ec->signalg->name);
2546 /* Format the output */
2547 *siglen = 8+namelen+rlen+slen+8;
2548 buf = snewn(*siglen, unsigned char);
2550 PUT_32BIT(p, namelen);
2552 memcpy(p, ec->signalg->name, namelen);
2554 PUT_32BIT(p, rlen + slen + 8);
2558 for (i = rlen; i--;)
2559 *p++ = bignum_byte(r, i);
2562 for (i = slen; i--;)
2563 *p++ = bignum_byte(s, i);
2572 const struct ecsign_extra sign_extra_ed25519 = {
2576 const struct ssh_signkey ssh_ecdsa_ed25519 = {
2583 ed25519_openssh_createkey,
2584 ed25519_openssh_fmtkey,
2585 2 /* point, private exponent */,
2591 &sign_extra_ed25519,
2594 /* OID: 1.2.840.10045.3.1.7 (ansiX9p256r1) */
2595 static const unsigned char nistp256_oid[] = {
2596 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07
2598 const struct ecsign_extra sign_extra_nistp256 = {
2599 ec_p256, &ssh_sha256,
2600 nistp256_oid, lenof(nistp256_oid),
2602 const struct ssh_signkey ssh_ecdsa_nistp256 = {
2609 ecdsa_openssh_createkey,
2610 ecdsa_openssh_fmtkey,
2611 3 /* curve name, point, private exponent */,
2615 "ecdsa-sha2-nistp256",
2616 "ecdsa-sha2-nistp256",
2617 &sign_extra_nistp256,
2620 /* OID: 1.3.132.0.34 (secp384r1) */
2621 static const unsigned char nistp384_oid[] = {
2622 0x2b, 0x81, 0x04, 0x00, 0x22
2624 const struct ecsign_extra sign_extra_nistp384 = {
2625 ec_p384, &ssh_sha384,
2626 nistp384_oid, lenof(nistp384_oid),
2628 const struct ssh_signkey ssh_ecdsa_nistp384 = {
2635 ecdsa_openssh_createkey,
2636 ecdsa_openssh_fmtkey,
2637 3 /* curve name, point, private exponent */,
2641 "ecdsa-sha2-nistp384",
2642 "ecdsa-sha2-nistp384",
2643 &sign_extra_nistp384,
2646 /* OID: 1.3.132.0.35 (secp521r1) */
2647 static const unsigned char nistp521_oid[] = {
2648 0x2b, 0x81, 0x04, 0x00, 0x23
2650 const struct ecsign_extra sign_extra_nistp521 = {
2651 ec_p521, &ssh_sha512,
2652 nistp521_oid, lenof(nistp521_oid),
2654 const struct ssh_signkey ssh_ecdsa_nistp521 = {
2661 ecdsa_openssh_createkey,
2662 ecdsa_openssh_fmtkey,
2663 3 /* curve name, point, private exponent */,
2667 "ecdsa-sha2-nistp521",
2668 "ecdsa-sha2-nistp521",
2669 &sign_extra_nistp521,
2672 /* ----------------------------------------------------------------------
2673 * Exposed ECDH interface
2676 struct eckex_extra {
2677 struct ec_curve *(*curve)(void);
2680 static Bignum ecdh_calculate(const Bignum private,
2681 const struct ec_point *public)
2685 p = ecp_mul(public, private);
2686 if (!p) return NULL;
2690 if (p->curve->type == EC_MONTGOMERY) {
2691 /* Do conversion in network byte order */
2693 int bytes = (bignum_bitcount(ret)+7) / 8;
2694 unsigned char *byteorder = snewn(bytes, unsigned char);
2695 for (i = 0; i < bytes; ++i) {
2696 byteorder[i] = bignum_byte(ret, i);
2699 ret = bignum_from_bytes(byteorder, bytes);
2707 void *ssh_ecdhkex_newkey(const struct ssh_kex *kex)
2709 const struct eckex_extra *extra = (const struct eckex_extra *)kex->extra;
2710 struct ec_curve *curve;
2712 struct ec_point *publicKey;
2714 curve = extra->curve();
2716 key = snew(struct ec_key);
2718 key->signalg = NULL;
2719 key->publicKey.curve = curve;
2721 if (curve->type == EC_MONTGOMERY) {
2722 unsigned char bytes[32] = {0};
2725 for (i = 0; i < sizeof(bytes); ++i)
2727 bytes[i] = (unsigned char)random_byte();
2732 key->privateKey = bignum_from_bytes(bytes, sizeof(bytes));
2733 for (i = 0; i < sizeof(bytes); ++i)
2735 ((volatile char*)bytes)[i] = 0;
2737 if (!key->privateKey) {
2741 publicKey = ecp_mul(&key->publicKey.curve->m.G, key->privateKey);
2743 freebn(key->privateKey);
2747 key->publicKey.x = publicKey->x;
2748 key->publicKey.y = publicKey->y;
2749 key->publicKey.z = NULL;
2752 key->privateKey = bignum_random_in_range(One, key->publicKey.curve->w.n);
2753 if (!key->privateKey) {
2757 publicKey = ecp_mul(&key->publicKey.curve->w.G, key->privateKey);
2759 freebn(key->privateKey);
2763 key->publicKey.x = publicKey->x;
2764 key->publicKey.y = publicKey->y;
2765 key->publicKey.z = NULL;
2771 char *ssh_ecdhkex_getpublic(void *key, int *len)
2773 struct ec_key *ec = (struct ec_key*)key;
2778 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2780 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2781 *len = 1 + pointlen * 2;
2785 point = (char*)snewn(*len, char);
2788 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2790 for (i = pointlen; i--;) {
2791 *p++ = bignum_byte(ec->publicKey.x, i);
2793 for (i = pointlen; i--;) {
2794 *p++ = bignum_byte(ec->publicKey.y, i);
2797 for (i = 0; i < pointlen; ++i) {
2798 *p++ = bignum_byte(ec->publicKey.x, i);
2805 Bignum ssh_ecdhkex_getkey(void *key, char *remoteKey, int remoteKeyLen)
2807 struct ec_key *ec = (struct ec_key*) key;
2808 struct ec_point remote;
2811 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2812 remote.curve = ec->publicKey.curve;
2813 remote.infinity = 0;
2814 if (!decodepoint(remoteKey, remoteKeyLen, &remote)) {
2818 /* Point length has to be the same length */
2819 if (remoteKeyLen != (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8) {
2823 remote.curve = ec->publicKey.curve;
2824 remote.infinity = 0;
2825 remote.x = bignum_from_bytes_le((unsigned char*)remoteKey, remoteKeyLen);
2830 ret = ecdh_calculate(ec->privateKey, &remote);
2831 if (remote.x) freebn(remote.x);
2832 if (remote.y) freebn(remote.y);
2836 void ssh_ecdhkex_freekey(void *key)
2841 static const struct eckex_extra kex_extra_curve25519 = { ec_curve25519 };
2842 static const struct ssh_kex ssh_ec_kex_curve25519 = {
2843 "curve25519-sha256@libssh.org", NULL, KEXTYPE_ECDH,
2844 &ssh_sha256, &kex_extra_curve25519,
2847 const struct eckex_extra kex_extra_nistp256 = { ec_p256 };
2848 static const struct ssh_kex ssh_ec_kex_nistp256 = {
2849 "ecdh-sha2-nistp256", NULL, KEXTYPE_ECDH,
2850 &ssh_sha256, &kex_extra_nistp256,
2853 const struct eckex_extra kex_extra_nistp384 = { ec_p384 };
2854 static const struct ssh_kex ssh_ec_kex_nistp384 = {
2855 "ecdh-sha2-nistp384", NULL, KEXTYPE_ECDH,
2856 &ssh_sha384, &kex_extra_nistp384,
2859 const struct eckex_extra kex_extra_nistp521 = { ec_p521 };
2860 static const struct ssh_kex ssh_ec_kex_nistp521 = {
2861 "ecdh-sha2-nistp521", NULL, KEXTYPE_ECDH,
2862 &ssh_sha512, &kex_extra_nistp521,
2865 static const struct ssh_kex *const ec_kex_list[] = {
2866 &ssh_ec_kex_curve25519,
2867 &ssh_ec_kex_nistp256,
2868 &ssh_ec_kex_nistp384,
2869 &ssh_ec_kex_nistp521,
2872 const struct ssh_kexes ssh_ecdh_kex = {
2873 sizeof(ec_kex_list) / sizeof(*ec_kex_list),
2877 /* ----------------------------------------------------------------------
2878 * Helper functions for finding key algorithms and returning auxiliary
2882 const struct ssh_signkey *ec_alg_by_oid(int len, const void *oid,
2883 const struct ec_curve **curve)
2885 static const struct ssh_signkey *algs_with_oid[] = {
2886 &ssh_ecdsa_nistp256,
2887 &ssh_ecdsa_nistp384,
2888 &ssh_ecdsa_nistp521,
2892 for (i = 0; i < lenof(algs_with_oid); i++) {
2893 const struct ssh_signkey *alg = algs_with_oid[i];
2894 const struct ecsign_extra *extra =
2895 (const struct ecsign_extra *)alg->extra;
2896 if (len == extra->oidlen && !memcmp(oid, extra->oid, len)) {
2897 *curve = extra->curve();
2904 const unsigned char *ec_alg_oid(const struct ssh_signkey *alg,
2907 const struct ecsign_extra *extra = (const struct ecsign_extra *)alg->extra;
2908 *oidlen = extra->oidlen;
2912 const int ec_nist_alg_and_curve_by_bits(int bits,
2913 const struct ec_curve **curve,
2914 const struct ssh_signkey **alg)
2917 case 256: *alg = &ssh_ecdsa_nistp256; break;
2918 case 384: *alg = &ssh_ecdsa_nistp384; break;
2919 case 521: *alg = &ssh_ecdsa_nistp521; break;
2920 default: return FALSE;
2922 *curve = ((struct ecsign_extra *)(*alg)->extra)->curve();
2926 const int ec_ed_alg_and_curve_by_bits(int bits,
2927 const struct ec_curve **curve,
2928 const struct ssh_signkey **alg)
2931 case 256: *alg = &ssh_ecdsa_ed25519; break;
2932 default: return FALSE;
2934 *curve = ((struct ecsign_extra *)(*alg)->extra)->curve();