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
27 * Curve25519 spec from libssh (with reference to other things in the
29 * https://git.libssh.org/users/aris/libssh.git/tree/doc/curve25519-sha256@libssh.org.txt
32 * http://ed25519.cr.yp.to/ed25519-20110926.pdf
40 /* ----------------------------------------------------------------------
41 * Elliptic curve definitions
44 static void initialise_wcurve(struct ec_curve *curve, int bits,
45 const unsigned char *p,
46 const unsigned char *a, const unsigned char *b,
47 const unsigned char *n, const unsigned char *Gx,
48 const unsigned char *Gy)
50 int length = bits / 8;
51 if (bits % 8) ++length;
53 curve->type = EC_WEIERSTRASS;
55 curve->fieldBits = bits;
56 curve->p = bignum_from_bytes(p, length);
58 /* Curve co-efficients */
59 curve->w.a = bignum_from_bytes(a, length);
60 curve->w.b = bignum_from_bytes(b, length);
62 /* Group order and generator */
63 curve->w.n = bignum_from_bytes(n, length);
64 curve->w.G.x = bignum_from_bytes(Gx, length);
65 curve->w.G.y = bignum_from_bytes(Gy, length);
66 curve->w.G.curve = curve;
67 curve->w.G.infinity = 0;
70 static void initialise_mcurve(struct ec_curve *curve, int bits,
71 const unsigned char *p,
72 const unsigned char *a, const unsigned char *b,
73 const unsigned char *Gx)
75 int length = bits / 8;
76 if (bits % 8) ++length;
78 curve->type = EC_MONTGOMERY;
80 curve->fieldBits = bits;
81 curve->p = bignum_from_bytes(p, length);
83 /* Curve co-efficients */
84 curve->m.a = bignum_from_bytes(a, length);
85 curve->m.b = bignum_from_bytes(b, length);
88 curve->m.G.x = bignum_from_bytes(Gx, length);
91 curve->m.G.curve = curve;
92 curve->m.G.infinity = 0;
95 static void initialise_ecurve(struct ec_curve *curve, int bits,
96 const unsigned char *p,
97 const unsigned char *l, const unsigned char *d,
98 const unsigned char *Bx, const unsigned char *By)
100 int length = bits / 8;
101 if (bits % 8) ++length;
103 curve->type = EC_EDWARDS;
105 curve->fieldBits = bits;
106 curve->p = bignum_from_bytes(p, length);
108 /* Curve co-efficients */
109 curve->e.l = bignum_from_bytes(l, length);
110 curve->e.d = bignum_from_bytes(d, length);
112 /* Group order and generator */
113 curve->e.B.x = bignum_from_bytes(Bx, length);
114 curve->e.B.y = bignum_from_bytes(By, length);
115 curve->e.B.curve = curve;
116 curve->e.B.infinity = 0;
119 static struct ec_curve *ec_p256(void)
121 static struct ec_curve curve = { 0 };
122 static unsigned char initialised = 0;
126 static const unsigned char p[] = {
127 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
128 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
129 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
130 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff
132 static const unsigned char a[] = {
133 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01,
134 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
135 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
136 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc
138 static const unsigned char b[] = {
139 0x5a, 0xc6, 0x35, 0xd8, 0xaa, 0x3a, 0x93, 0xe7,
140 0xb3, 0xeb, 0xbd, 0x55, 0x76, 0x98, 0x86, 0xbc,
141 0x65, 0x1d, 0x06, 0xb0, 0xcc, 0x53, 0xb0, 0xf6,
142 0x3b, 0xce, 0x3c, 0x3e, 0x27, 0xd2, 0x60, 0x4b
144 static const unsigned char n[] = {
145 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
146 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
147 0xbc, 0xe6, 0xfa, 0xad, 0xa7, 0x17, 0x9e, 0x84,
148 0xf3, 0xb9, 0xca, 0xc2, 0xfc, 0x63, 0x25, 0x51
150 static const unsigned char Gx[] = {
151 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47,
152 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2,
153 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0,
154 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96
156 static const unsigned char Gy[] = {
157 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b,
158 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e, 0x16,
159 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce,
160 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5
163 initialise_wcurve(&curve, 256, p, a, b, n, Gx, Gy);
164 curve.textname = curve.name = "nistp256";
166 /* Now initialised, no need to do it again */
173 static struct ec_curve *ec_p384(void)
175 static struct ec_curve curve = { 0 };
176 static unsigned char initialised = 0;
180 static const unsigned char p[] = {
181 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
182 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
183 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
184 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
185 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
186 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff
188 static const unsigned char a[] = {
189 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
190 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
191 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
192 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
193 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
194 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xfc
196 static const unsigned char b[] = {
197 0xb3, 0x31, 0x2f, 0xa7, 0xe2, 0x3e, 0xe7, 0xe4,
198 0x98, 0x8e, 0x05, 0x6b, 0xe3, 0xf8, 0x2d, 0x19,
199 0x18, 0x1d, 0x9c, 0x6e, 0xfe, 0x81, 0x41, 0x12,
200 0x03, 0x14, 0x08, 0x8f, 0x50, 0x13, 0x87, 0x5a,
201 0xc6, 0x56, 0x39, 0x8d, 0x8a, 0x2e, 0xd1, 0x9d,
202 0x2a, 0x85, 0xc8, 0xed, 0xd3, 0xec, 0x2a, 0xef
204 static const unsigned char n[] = {
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 0xc7, 0x63, 0x4d, 0x81, 0xf4, 0x37, 0x2d, 0xdf,
209 0x58, 0x1a, 0x0d, 0xb2, 0x48, 0xb0, 0xa7, 0x7a,
210 0xec, 0xec, 0x19, 0x6a, 0xcc, 0xc5, 0x29, 0x73
212 static const unsigned char Gx[] = {
213 0xaa, 0x87, 0xca, 0x22, 0xbe, 0x8b, 0x05, 0x37,
214 0x8e, 0xb1, 0xc7, 0x1e, 0xf3, 0x20, 0xad, 0x74,
215 0x6e, 0x1d, 0x3b, 0x62, 0x8b, 0xa7, 0x9b, 0x98,
216 0x59, 0xf7, 0x41, 0xe0, 0x82, 0x54, 0x2a, 0x38,
217 0x55, 0x02, 0xf2, 0x5d, 0xbf, 0x55, 0x29, 0x6c,
218 0x3a, 0x54, 0x5e, 0x38, 0x72, 0x76, 0x0a, 0xb7
220 static const unsigned char Gy[] = {
221 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f,
222 0x5d, 0x9e, 0x98, 0xbf, 0x92, 0x92, 0xdc, 0x29,
223 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c,
224 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0,
225 0x0a, 0x60, 0xb1, 0xce, 0x1d, 0x7e, 0x81, 0x9d,
226 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f
229 initialise_wcurve(&curve, 384, p, a, b, n, Gx, Gy);
230 curve.textname = curve.name = "nistp384";
232 /* Now initialised, no need to do it again */
239 static struct ec_curve *ec_p521(void)
241 static struct ec_curve curve = { 0 };
242 static unsigned char initialised = 0;
246 static const unsigned char p[] = {
247 0x01, 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,
251 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
252 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
253 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
254 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
257 static const unsigned char a[] = {
258 0x01, 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,
262 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
263 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
264 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
265 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
268 static const unsigned char b[] = {
269 0x00, 0x51, 0x95, 0x3e, 0xb9, 0x61, 0x8e, 0x1c,
270 0x9a, 0x1f, 0x92, 0x9a, 0x21, 0xa0, 0xb6, 0x85,
271 0x40, 0xee, 0xa2, 0xda, 0x72, 0x5b, 0x99, 0xb3,
272 0x15, 0xf3, 0xb8, 0xb4, 0x89, 0x91, 0x8e, 0xf1,
273 0x09, 0xe1, 0x56, 0x19, 0x39, 0x51, 0xec, 0x7e,
274 0x93, 0x7b, 0x16, 0x52, 0xc0, 0xbd, 0x3b, 0xb1,
275 0xbf, 0x07, 0x35, 0x73, 0xdf, 0x88, 0x3d, 0x2c,
276 0x34, 0xf1, 0xef, 0x45, 0x1f, 0xd4, 0x6b, 0x50,
279 static const unsigned char n[] = {
280 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
281 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
282 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
283 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
284 0xff, 0xfa, 0x51, 0x86, 0x87, 0x83, 0xbf, 0x2f,
285 0x96, 0x6b, 0x7f, 0xcc, 0x01, 0x48, 0xf7, 0x09,
286 0xa5, 0xd0, 0x3b, 0xb5, 0xc9, 0xb8, 0x89, 0x9c,
287 0x47, 0xae, 0xbb, 0x6f, 0xb7, 0x1e, 0x91, 0x38,
290 static const unsigned char Gx[] = {
291 0x00, 0xc6, 0x85, 0x8e, 0x06, 0xb7, 0x04, 0x04,
292 0xe9, 0xcd, 0x9e, 0x3e, 0xcb, 0x66, 0x23, 0x95,
293 0xb4, 0x42, 0x9c, 0x64, 0x81, 0x39, 0x05, 0x3f,
294 0xb5, 0x21, 0xf8, 0x28, 0xaf, 0x60, 0x6b, 0x4d,
295 0x3d, 0xba, 0xa1, 0x4b, 0x5e, 0x77, 0xef, 0xe7,
296 0x59, 0x28, 0xfe, 0x1d, 0xc1, 0x27, 0xa2, 0xff,
297 0xa8, 0xde, 0x33, 0x48, 0xb3, 0xc1, 0x85, 0x6a,
298 0x42, 0x9b, 0xf9, 0x7e, 0x7e, 0x31, 0xc2, 0xe5,
301 static const unsigned char Gy[] = {
302 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b,
303 0xc0, 0x04, 0x5c, 0x8a, 0x5f, 0xb4, 0x2c, 0x7d,
304 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b,
305 0x44, 0x68, 0x17, 0xaf, 0xbd, 0x17, 0x27, 0x3e,
306 0x66, 0x2c, 0x97, 0xee, 0x72, 0x99, 0x5e, 0xf4,
307 0x26, 0x40, 0xc5, 0x50, 0xb9, 0x01, 0x3f, 0xad,
308 0x07, 0x61, 0x35, 0x3c, 0x70, 0x86, 0xa2, 0x72,
309 0xc2, 0x40, 0x88, 0xbe, 0x94, 0x76, 0x9f, 0xd1,
313 initialise_wcurve(&curve, 521, p, a, b, n, Gx, Gy);
314 curve.textname = curve.name = "nistp521";
316 /* Now initialised, no need to do it again */
323 static struct ec_curve *ec_curve25519(void)
325 static struct ec_curve curve = { 0 };
326 static unsigned char initialised = 0;
330 static const unsigned char p[] = {
331 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
332 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
333 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
334 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
336 static const unsigned char a[] = {
337 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
338 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
339 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
340 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x6d, 0x06
342 static const unsigned char b[] = {
343 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
344 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
345 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
346 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
348 static const unsigned char gx[32] = {
349 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
350 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
351 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
352 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x09
355 initialise_mcurve(&curve, 256, p, a, b, gx);
356 /* This curve doesn't need a name, because it's never used in
357 * any format that embeds the curve name */
359 curve.textname = "Curve25519";
361 /* Now initialised, no need to do it again */
368 static struct ec_curve *ec_ed25519(void)
370 static struct ec_curve curve = { 0 };
371 static unsigned char initialised = 0;
375 static const unsigned char q[] = {
376 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
377 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
378 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
379 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
381 static const unsigned char l[32] = {
382 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
383 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
384 0x14, 0xde, 0xf9, 0xde, 0xa2, 0xf7, 0x9c, 0xd6,
385 0x58, 0x12, 0x63, 0x1a, 0x5c, 0xf5, 0xd3, 0xed
387 static const unsigned char d[32] = {
388 0x52, 0x03, 0x6c, 0xee, 0x2b, 0x6f, 0xfe, 0x73,
389 0x8c, 0xc7, 0x40, 0x79, 0x77, 0x79, 0xe8, 0x98,
390 0x00, 0x70, 0x0a, 0x4d, 0x41, 0x41, 0xd8, 0xab,
391 0x75, 0xeb, 0x4d, 0xca, 0x13, 0x59, 0x78, 0xa3
393 static const unsigned char Bx[32] = {
394 0x21, 0x69, 0x36, 0xd3, 0xcd, 0x6e, 0x53, 0xfe,
395 0xc0, 0xa4, 0xe2, 0x31, 0xfd, 0xd6, 0xdc, 0x5c,
396 0x69, 0x2c, 0xc7, 0x60, 0x95, 0x25, 0xa7, 0xb2,
397 0xc9, 0x56, 0x2d, 0x60, 0x8f, 0x25, 0xd5, 0x1a
399 static const unsigned char By[32] = {
400 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
401 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
402 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
403 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x58
406 /* This curve doesn't need a name, because it's never used in
407 * any format that embeds the curve name */
410 initialise_ecurve(&curve, 256, q, l, d, Bx, By);
411 curve.textname = "Ed25519";
413 /* Now initialised, no need to do it again */
420 /* Return 1 if a is -3 % p, otherwise return 0
421 * This is used because there are some maths optimisations */
422 static int ec_aminus3(const struct ec_curve *curve)
427 if (curve->type != EC_WEIERSTRASS) {
431 _p = bignum_add_long(curve->w.a, 3);
433 ret = !bignum_cmp(curve->p, _p);
438 /* ----------------------------------------------------------------------
439 * Elliptic curve field maths
442 static Bignum ecf_add(const Bignum a, const Bignum b,
443 const struct ec_curve *curve)
445 Bignum a1, b1, ab, ret;
447 a1 = bigmod(a, curve->p);
448 b1 = bigmod(b, curve->p);
454 ret = bigmod(ab, curve->p);
460 static Bignum ecf_square(const Bignum a, const struct ec_curve *curve)
462 return modmul(a, a, curve->p);
465 static Bignum ecf_treble(const Bignum a, const struct ec_curve *curve)
470 tmp = bignum_lshift(a, 1);
472 /* Add itself (i.e. treble) */
473 ret = bigadd(tmp, a);
477 while (bignum_cmp(ret, curve->p) >= 0)
479 tmp = bigsub(ret, curve->p);
488 static Bignum ecf_double(const Bignum a, const struct ec_curve *curve)
490 Bignum ret = bignum_lshift(a, 1);
491 if (bignum_cmp(ret, curve->p) >= 0)
493 Bignum tmp = bigsub(ret, curve->p);
504 /* ----------------------------------------------------------------------
508 void ec_point_free(struct ec_point *point)
510 if (point == NULL) return;
512 if (point->x) freebn(point->x);
513 if (point->y) freebn(point->y);
514 if (point->z) freebn(point->z);
519 static struct ec_point *ec_point_new(const struct ec_curve *curve,
520 const Bignum x, const Bignum y, const Bignum z,
521 unsigned char infinity)
523 struct ec_point *point = snewn(1, struct ec_point);
524 point->curve = curve;
528 point->infinity = infinity ? 1 : 0;
532 static struct ec_point *ec_point_copy(const struct ec_point *a)
534 if (a == NULL) return NULL;
535 return ec_point_new(a->curve,
536 a->x ? copybn(a->x) : NULL,
537 a->y ? copybn(a->y) : NULL,
538 a->z ? copybn(a->z) : NULL,
542 static int ec_point_verify(const struct ec_point *a)
546 } else if (a->curve->type == EC_EDWARDS) {
547 /* Check y^2 - x^2 - 1 - d * x^2 * y^2 == 0 */
548 Bignum y2, x2, tmp, tmp2, tmp3;
551 y2 = ecf_square(a->y, a->curve);
552 x2 = ecf_square(a->x, a->curve);
553 tmp = modmul(a->curve->e.d, x2, a->curve->p);
554 tmp2 = modmul(tmp, y2, a->curve->p);
556 tmp = modsub(y2, x2, a->curve->p);
559 tmp3 = modsub(tmp, tmp2, a->curve->p);
562 ret = !bignum_cmp(tmp3, One);
565 } else if (a->curve->type == EC_WEIERSTRASS) {
566 /* Verify y^2 = x^3 + ax + b */
569 Bignum lhs = NULL, x3 = NULL, ax = NULL, x3ax = NULL, x3axm = NULL, x3axb = NULL, rhs = NULL;
571 Bignum Three = bignum_from_long(3);
573 lhs = modmul(a->y, a->y, a->curve->p);
575 /* This uses montgomery multiplication to optimise */
576 x3 = modpow(a->x, Three, a->curve->p);
578 ax = modmul(a->curve->w.a, a->x, a->curve->p);
579 x3ax = bigadd(x3, ax);
580 freebn(x3); x3 = NULL;
581 freebn(ax); ax = NULL;
582 x3axm = bigmod(x3ax, a->curve->p);
583 freebn(x3ax); x3ax = NULL;
584 x3axb = bigadd(x3axm, a->curve->w.b);
585 freebn(x3axm); x3axm = NULL;
586 rhs = bigmod(x3axb, a->curve->p);
589 ret = bignum_cmp(lhs, rhs) ? 0 : 1;
599 /* ----------------------------------------------------------------------
600 * Elliptic curve point maths
603 /* Returns 1 on success and 0 on memory error */
604 static int ecp_normalise(struct ec_point *a)
612 /* Point is at infinity - i.e. normalised */
616 if (a->curve->type == EC_WEIERSTRASS) {
617 /* In Jacobian Coordinates the triple (X, Y, Z) represents
618 the affine point (X / Z^2, Y / Z^3) */
620 Bignum Z2, Z2inv, Z3, Z3inv, tx, ty;
622 if (!a->x || !a->y) {
623 /* No point defined */
626 /* Already normalised */
630 Z2 = ecf_square(a->z, a->curve);
631 Z2inv = modinv(Z2, a->curve->p);
636 tx = modmul(a->x, Z2inv, a->curve->p);
639 Z3 = modmul(Z2, a->z, a->curve->p);
641 Z3inv = modinv(Z3, a->curve->p);
647 ty = modmul(a->y, Z3inv, a->curve->p);
657 } else if (a->curve->type == EC_MONTGOMERY) {
658 /* In Montgomery (X : Z) represents the x co-ord (X / Z, ?) */
663 /* No point defined */
666 /* Already normalised */
670 tmp = modinv(a->z, a->curve->p);
674 tmp2 = modmul(a->x, tmp, a->curve->p);
682 } else if (a->curve->type == EC_EDWARDS) {
683 /* Always normalised */
690 static struct ec_point *ecp_doublew(const struct ec_point *a, const int aminus3)
692 Bignum S, M, outx, outy, outz;
694 if (bignum_cmp(a->y, Zero) == 0)
697 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
702 Bignum Y2, XY2, _2XY2;
704 Y2 = ecf_square(a->y, a->curve);
705 XY2 = modmul(a->x, Y2, a->curve->p);
708 _2XY2 = ecf_double(XY2, a->curve);
710 S = ecf_double(_2XY2, a->curve);
714 /* Faster calculation if a = -3 */
716 /* if a = -3, then M can also be calculated as M = 3*(X + Z^2)*(X - Z^2) */
717 Bignum Z2, XpZ2, XmZ2, second;
722 Z2 = ecf_square(a->z, a->curve);
725 XpZ2 = ecf_add(a->x, Z2, a->curve);
726 XmZ2 = modsub(a->x, Z2, a->curve->p);
729 second = modmul(XpZ2, XmZ2, a->curve->p);
733 M = ecf_treble(second, a->curve);
736 /* M = 3*X^2 + a*Z^4 */
737 Bignum _3X2, X2, aZ4;
740 aZ4 = copybn(a->curve->w.a);
744 Z2 = ecf_square(a->z, a->curve);
745 Z4 = ecf_square(Z2, a->curve);
747 aZ4 = modmul(a->curve->w.a, Z4, a->curve->p);
751 X2 = modmul(a->x, a->x, a->curve->p);
752 _3X2 = ecf_treble(X2, a->curve);
754 M = ecf_add(_3X2, aZ4, a->curve);
763 M2 = ecf_square(M, a->curve);
764 _2S = ecf_double(S, a->curve);
765 outx = modsub(M2, _2S, a->curve->p);
770 /* Y' = M*(S - X') - 8*Y^4 */
772 Bignum SX, MSX, Eight, Y2, Y4, _8Y4;
774 SX = modsub(S, outx, a->curve->p);
776 MSX = modmul(M, SX, a->curve->p);
779 Y2 = ecf_square(a->y, a->curve);
780 Y4 = ecf_square(Y2, a->curve);
782 Eight = bignum_from_long(8);
783 _8Y4 = modmul(Eight, Y4, a->curve->p);
786 outy = modsub(MSX, _8Y4, a->curve->p);
798 YZ = modmul(a->y, a->z, a->curve->p);
801 outz = ecf_double(YZ, a->curve);
805 return ec_point_new(a->curve, outx, outy, outz, 0);
808 static struct ec_point *ecp_doublem(const struct ec_point *a)
810 Bignum z, outx, outz, xpz, xmz;
817 /* 4xz = (x + z)^2 - (x - z)^2 */
821 tmp = ecf_add(a->x, z, a->curve);
822 xpz = ecf_square(tmp, a->curve);
825 tmp = modsub(a->x, z, a->curve->p);
826 xmz = ecf_square(tmp, a->curve);
830 /* outx = (x + z)^2 * (x - z)^2 */
831 outx = modmul(xpz, xmz, a->curve->p);
833 /* outz = 4xz * ((x - z)^2 + ((A + 2) / 4)*4xz) */
835 Bignum _4xz, tmp, tmp2, tmp3;
837 tmp = bignum_from_long(2);
838 tmp2 = ecf_add(a->curve->m.a, tmp, a->curve);
841 _4xz = modsub(xpz, xmz, a->curve->p);
843 tmp = modmul(tmp2, _4xz, a->curve->p);
846 tmp2 = bignum_from_long(4);
847 tmp3 = modinv(tmp2, a->curve->p);
856 tmp2 = modmul(tmp, tmp3, a->curve->p);
860 tmp = ecf_add(xmz, tmp2, a->curve);
863 outz = modmul(_4xz, tmp, a->curve->p);
868 return ec_point_new(a->curve, outx, NULL, outz, 0);
871 /* Forward declaration for Edwards curve doubling */
872 static struct ec_point *ecp_add(const struct ec_point *a,
873 const struct ec_point *b,
876 static struct ec_point *ecp_double(const struct ec_point *a, const int aminus3)
881 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
884 if (a->curve->type == EC_EDWARDS)
886 return ecp_add(a, a, aminus3);
888 else if (a->curve->type == EC_WEIERSTRASS)
890 return ecp_doublew(a, aminus3);
894 return ecp_doublem(a);
898 static struct ec_point *ecp_addw(const struct ec_point *a,
899 const struct ec_point *b,
902 Bignum U1, U2, S1, S2, outx, outy, outz;
909 Z2 = ecf_square(b->z, a->curve);
910 U1 = modmul(a->x, Z2, a->curve->p);
911 Z3 = modmul(Z2, b->z, a->curve->p);
913 S1 = modmul(a->y, Z3, a->curve->p);
925 Z2 = ecf_square(a->z, b->curve);
926 U2 = modmul(b->x, Z2, b->curve->p);
927 Z3 = modmul(Z2, a->z, b->curve->p);
929 S2 = modmul(b->y, Z3, b->curve->p);
936 /* Check if multiplying by self */
937 if (bignum_cmp(U1, U2) == 0)
941 if (bignum_cmp(S1, S2) == 0)
945 return ecp_double(a, aminus3);
952 return ec_point_new(a->curve, NULL, NULL, NULL, 1);
957 Bignum H, R, UH2, H3;
960 H = modsub(U2, U1, a->curve->p);
964 R = modsub(S2, S1, a->curve->p);
967 /* X3 = R^2 - H^3 - 2*U1*H^2 */
969 Bignum R2, H2, _2UH2, first;
971 H2 = ecf_square(H, a->curve);
972 UH2 = modmul(U1, H2, a->curve->p);
974 H3 = modmul(H2, H, a->curve->p);
976 R2 = ecf_square(R, a->curve);
977 _2UH2 = ecf_double(UH2, a->curve);
978 first = modsub(R2, H3, a->curve->p);
980 outx = modsub(first, _2UH2, a->curve->p);
985 /* Y3 = R*(U1*H^2 - X3) - S1*H^3 */
987 Bignum RUH2mX, UH2mX, SH3;
989 UH2mX = modsub(UH2, outx, a->curve->p);
991 RUH2mX = modmul(R, UH2mX, a->curve->p);
994 SH3 = modmul(S1, H3, a->curve->p);
998 outy = modsub(RUH2mX, SH3, a->curve->p);
1007 ZZ = modmul(a->z, b->z, a->curve->p);
1008 outz = modmul(H, ZZ, a->curve->p);
1012 outz = modmul(H, a->z, a->curve->p);
1015 outz = modmul(H, b->z, a->curve->p);
1022 return ec_point_new(a->curve, outx, outy, outz, 0);
1025 static struct ec_point *ecp_addm(const struct ec_point *a,
1026 const struct ec_point *b,
1027 const struct ec_point *base)
1029 Bignum outx, outz, az, bz;
1040 /* a-b is maintained at 1 due to Montgomery ladder implementation */
1041 /* Xa+b = Za-b * ((Xa - Za)*(Xb + Zb) + (Xa + Za)*(Xb - Zb))^2 */
1042 /* Za+b = Xa-b * ((Xa - Za)*(Xb + Zb) - (Xa + Za)*(Xb - Zb))^2 */
1044 Bignum tmp, tmp2, tmp3, tmp4;
1046 /* (Xa + Za) * (Xb - Zb) */
1047 tmp = ecf_add(a->x, az, a->curve);
1048 tmp2 = modsub(b->x, bz, a->curve->p);
1049 tmp3 = modmul(tmp, tmp2, a->curve->p);
1053 /* (Xa - Za) * (Xb + Zb) */
1054 tmp = modsub(a->x, az, a->curve->p);
1055 tmp2 = ecf_add(b->x, bz, a->curve);
1056 tmp4 = modmul(tmp, tmp2, a->curve->p);
1060 tmp = ecf_add(tmp3, tmp4, a->curve);
1061 outx = ecf_square(tmp, a->curve);
1064 tmp = modsub(tmp3, tmp4, a->curve->p);
1067 tmp2 = ecf_square(tmp, a->curve);
1069 outz = modmul(base->x, tmp2, a->curve->p);
1073 return ec_point_new(a->curve, outx, NULL, outz, 0);
1076 static struct ec_point *ecp_adde(const struct ec_point *a,
1077 const struct ec_point *b)
1079 Bignum outx, outy, dmul;
1081 /* outx = (a->x * b->y + b->x * a->y) /
1082 * (1 + a->curve->e.d * a->x * b->x * a->y * b->y) */
1084 Bignum tmp, tmp2, tmp3, tmp4;
1086 tmp = modmul(a->x, b->y, a->curve->p);
1087 tmp2 = modmul(b->x, a->y, a->curve->p);
1088 tmp3 = ecf_add(tmp, tmp2, a->curve);
1090 tmp4 = modmul(tmp, tmp2, a->curve->p);
1093 dmul = modmul(a->curve->e.d, tmp4, a->curve->p);
1096 tmp = ecf_add(One, dmul, a->curve);
1097 tmp2 = modinv(tmp, a->curve->p);
1106 outx = modmul(tmp3, tmp2, a->curve->p);
1111 /* outy = (a->y * b->y + a->x * b->x) /
1112 * (1 - a->curve->e.d * a->x * b->x * a->y * b->y) */
1114 Bignum tmp, tmp2, tmp3, tmp4;
1116 tmp = modsub(One, dmul, a->curve->p);
1119 tmp2 = modinv(tmp, a->curve->p);
1127 tmp = modmul(a->y, b->y, a->curve->p);
1128 tmp3 = modmul(a->x, b->x, a->curve->p);
1129 tmp4 = ecf_add(tmp, tmp3, a->curve);
1133 outy = modmul(tmp4, tmp2, a->curve->p);
1138 return ec_point_new(a->curve, outx, outy, NULL, 0);
1141 static struct ec_point *ecp_add(const struct ec_point *a,
1142 const struct ec_point *b,
1145 if (a->curve != b->curve) {
1149 /* Check if multiplying by infinity */
1150 if (a->infinity) return ec_point_copy(b);
1151 if (b->infinity) return ec_point_copy(a);
1153 if (a->curve->type == EC_EDWARDS)
1155 return ecp_adde(a, b);
1158 if (a->curve->type == EC_WEIERSTRASS)
1160 return ecp_addw(a, b, aminus3);
1166 static struct ec_point *ecp_mul_(const struct ec_point *a, const Bignum b, int aminus3)
1168 struct ec_point *A, *ret;
1171 A = ec_point_copy(a);
1172 ret = ec_point_new(a->curve, NULL, NULL, NULL, 1);
1174 bits = bignum_bitcount(b);
1175 for (i = 0; i < bits; ++i)
1177 if (bignum_bit(b, i))
1179 struct ec_point *tmp = ecp_add(ret, A, aminus3);
1185 struct ec_point *tmp = ecp_double(A, aminus3);
1195 static struct ec_point *ecp_mulw(const struct ec_point *a, const Bignum b)
1197 struct ec_point *ret = ecp_mul_(a, b, ec_aminus3(a->curve));
1199 if (!ecp_normalise(ret)) {
1207 static struct ec_point *ecp_mule(const struct ec_point *a, const Bignum b)
1210 struct ec_point *ret;
1212 ret = ec_point_new(a->curve, NULL, NULL, NULL, 1);
1214 for (i = bignum_bitcount(b); i >= 0 && ret; --i)
1217 struct ec_point *tmp = ecp_double(ret, 0);
1221 if (ret && bignum_bit(b, i))
1223 struct ec_point *tmp = ecp_add(ret, a, 0);
1232 static struct ec_point *ecp_mulm(const struct ec_point *p, const Bignum n)
1234 struct ec_point *P1, *P2;
1237 /* P1 <- P and P2 <- [2]P */
1238 P2 = ecp_double(p, 0);
1239 P1 = ec_point_copy(p);
1241 /* for i = bits − 2 down to 0 */
1242 bits = bignum_bitcount(n);
1243 for (i = bits - 2; i >= 0; --i)
1245 if (!bignum_bit(n, i))
1248 struct ec_point *tmp = ecp_addm(P1, P2, p);
1253 tmp = ecp_double(P1, 0);
1260 struct ec_point *tmp = ecp_addm(P1, P2, p);
1265 tmp = ecp_double(P2, 0);
1273 if (!ecp_normalise(P1)) {
1281 /* Not static because it is used by sshecdsag.c to generate a new key */
1282 struct ec_point *ecp_mul(const struct ec_point *a, const Bignum b)
1284 if (a->curve->type == EC_WEIERSTRASS) {
1285 return ecp_mulw(a, b);
1286 } else if (a->curve->type == EC_EDWARDS) {
1287 return ecp_mule(a, b);
1289 return ecp_mulm(a, b);
1293 static struct ec_point *ecp_summul(const Bignum a, const Bignum b,
1294 const struct ec_point *point)
1296 struct ec_point *aG, *bP, *ret;
1299 if (point->curve->type != EC_WEIERSTRASS) {
1303 aminus3 = ec_aminus3(point->curve);
1305 aG = ecp_mul_(&point->curve->w.G, a, aminus3);
1306 if (!aG) return NULL;
1307 bP = ecp_mul_(point, b, aminus3);
1313 ret = ecp_add(aG, bP, aminus3);
1318 if (!ecp_normalise(ret)) {
1325 static Bignum *ecp_edx(const struct ec_curve *curve, const Bignum y)
1327 /* Get the x value on the given Edwards curve for a given y */
1330 /* xx = (y^2 - 1) / (d * y^2 + 1) */
1332 Bignum tmp, tmp2, tmp3;
1334 tmp = ecf_square(y, curve);
1335 tmp2 = modmul(curve->e.d, tmp, curve->p);
1336 tmp3 = ecf_add(tmp2, One, curve);
1338 tmp2 = modinv(tmp3, curve->p);
1345 tmp3 = modsub(tmp, One, curve->p);
1347 xx = modmul(tmp3, tmp2, curve->p);
1352 /* x = xx^((p + 3) / 8) */
1356 tmp = bignum_add_long(curve->p, 3);
1357 tmp2 = bignum_rshift(tmp, 3);
1359 x = modpow(xx, tmp2, curve->p);
1363 /* if x^2 - xx != 0 then x = x*(2^((p - 1) / 4)) */
1367 tmp = ecf_square(x, curve);
1368 tmp2 = modsub(tmp, xx, curve->p);
1371 if (bignum_cmp(tmp2, Zero)) {
1376 tmp = modsub(curve->p, One, curve->p);
1377 tmp2 = bignum_rshift(tmp, 2);
1379 tmp = bignum_from_long(2);
1380 tmp3 = modpow(tmp, tmp2, curve->p);
1384 tmp = modmul(x, tmp3, curve->p);
1393 /* if x % 2 != 0 then x = p - x */
1394 if (bignum_bit(x, 0)) {
1395 Bignum tmp = modsub(curve->p, x, curve->p);
1403 /* ----------------------------------------------------------------------
1404 * Public point from private
1407 struct ec_point *ec_public(const Bignum privateKey, const struct ec_curve *curve)
1409 if (curve->type == EC_WEIERSTRASS) {
1410 return ecp_mul(&curve->w.G, privateKey);
1411 } else if (curve->type == EC_EDWARDS) {
1412 /* hash = H(sk) (where hash creates 2 * fieldBits)
1414 * a = 2^(b-2) + SUM(2^i * h_i) for i = 2 -> b-2
1416 struct ec_point *ret;
1417 unsigned char hash[512/8];
1423 keylen = curve->fieldBits / 8;
1424 for (i = 0; i < keylen; ++i) {
1425 unsigned char b = bignum_byte(privateKey, i);
1426 SHA512_Bytes(&s, &b, 1);
1428 SHA512_Final(&s, hash);
1430 /* The second part is simply turning the hash into a Bignum,
1431 * however the 2^(b-2) bit *must* be set, and the bottom 3
1432 * bits *must* not be */
1433 hash[0] &= 0xf8; /* Unset bottom 3 bits (if set) */
1434 hash[31] &= 0x7f; /* Unset above (b-2) */
1435 hash[31] |= 0x40; /* Set 2^(b-2) */
1436 /* Chop off the top part and convert to int */
1437 a = bignum_from_bytes_le(hash, 32);
1439 ret = ecp_mul(&curve->e.B, a);
1447 /* ----------------------------------------------------------------------
1448 * Basic sign and verify routines
1451 static int _ecdsa_verify(const struct ec_point *publicKey,
1452 const unsigned char *data, const int dataLen,
1453 const Bignum r, const Bignum s)
1459 if (publicKey->curve->type != EC_WEIERSTRASS) {
1464 if (bignum_cmp(r, Zero) == 0 || bignum_cmp(r, publicKey->curve->w.n) >= 0
1465 || bignum_cmp(s, Zero) == 0 || bignum_cmp(s, publicKey->curve->w.n) >= 0)
1470 /* z = left most bitlen(curve->n) of data */
1471 z = bignum_from_bytes(data, dataLen);
1472 n_bits = bignum_bitcount(publicKey->curve->w.n);
1473 z_bits = bignum_bitcount(z);
1474 if (z_bits > n_bits)
1476 Bignum tmp = bignum_rshift(z, z_bits - n_bits);
1481 /* Ensure z in range of n */
1483 Bignum tmp = bigmod(z, publicKey->curve->w.n);
1488 /* Calculate signature */
1490 Bignum w, x, u1, u2;
1491 struct ec_point *tmp;
1493 w = modinv(s, publicKey->curve->w.n);
1498 u1 = modmul(z, w, publicKey->curve->w.n);
1499 u2 = modmul(r, w, publicKey->curve->w.n);
1502 tmp = ecp_summul(u1, u2, publicKey);
1510 x = bigmod(tmp->x, publicKey->curve->w.n);
1513 valid = (bignum_cmp(r, x) == 0) ? 1 : 0;
1522 static void _ecdsa_sign(const Bignum privateKey, const struct ec_curve *curve,
1523 const unsigned char *data, const int dataLen,
1524 Bignum *r, Bignum *s)
1526 unsigned char digest[20];
1529 struct ec_point *kG;
1534 if (curve->type != EC_WEIERSTRASS) {
1538 /* z = left most bitlen(curve->n) of data */
1539 z = bignum_from_bytes(data, dataLen);
1540 n_bits = bignum_bitcount(curve->w.n);
1541 z_bits = bignum_bitcount(z);
1542 if (z_bits > n_bits)
1545 tmp = bignum_rshift(z, z_bits - n_bits);
1550 /* Generate k between 1 and curve->n, using the same deterministic
1551 * k generation system we use for conventional DSA. */
1552 SHA_Simple(data, dataLen, digest);
1553 k = dss_gen_k("ECDSA deterministic k generator", curve->w.n, privateKey,
1554 digest, sizeof(digest));
1556 kG = ecp_mul(&curve->w.G, k);
1563 /* r = kG.x mod n */
1564 *r = bigmod(kG->x, curve->w.n);
1567 /* s = (z + r * priv)/k mod n */
1569 Bignum rPriv, zMod, first, firstMod, kInv;
1570 rPriv = modmul(*r, privateKey, curve->w.n);
1571 zMod = bigmod(z, curve->w.n);
1573 first = bigadd(rPriv, zMod);
1576 firstMod = bigmod(first, curve->w.n);
1578 kInv = modinv(k, curve->w.n);
1585 *s = modmul(firstMod, kInv, curve->w.n);
1591 /* ----------------------------------------------------------------------
1595 static void getstring(const char **data, int *datalen,
1596 const char **p, int *length)
1601 *length = toint(GET_32BIT(*data));
1606 if (*datalen < *length)
1610 *datalen -= *length;
1613 static Bignum getmp(const char **data, int *datalen)
1618 getstring(data, datalen, &p, &length);
1622 return NULL; /* negative mp */
1623 return bignum_from_bytes((unsigned char *)p, length);
1626 static Bignum getmp_le(const char **data, int *datalen)
1631 getstring(data, datalen, &p, &length);
1634 return bignum_from_bytes_le((const unsigned char *)p, length);
1637 static int decodepoint_ed(const char *p, int length, struct ec_point *point)
1639 /* Got some conversion to do, first read in the y co-ord */
1642 point->y = bignum_from_bytes_le((const unsigned char*)p, length);
1643 if ((unsigned)bignum_bitcount(point->y) > point->curve->fieldBits) {
1648 /* Read x bit and then reset it */
1649 negative = bignum_bit(point->y, point->curve->fieldBits - 1);
1650 bignum_set_bit(point->y, point->curve->fieldBits - 1, 0);
1652 /* Get the x from the y */
1653 point->x = ecp_edx(point->curve, point->y);
1660 Bignum tmp = modsub(point->curve->p, point->x, point->curve->p);
1665 /* Verify the point is on the curve */
1666 if (!ec_point_verify(point)) {
1677 static int decodepoint(const char *p, int length, struct ec_point *point)
1679 if (point->curve->type == EC_EDWARDS) {
1680 return decodepoint_ed(p, length, point);
1683 if (length < 1 || p[0] != 0x04) /* Only support uncompressed point */
1685 /* Skip compression flag */
1688 /* The two values must be equal length */
1689 if (length % 2 != 0) {
1695 length = length / 2;
1696 point->x = bignum_from_bytes((const unsigned char *)p, length);
1698 point->y = bignum_from_bytes((const unsigned char *)p, length);
1701 /* Verify the point is on the curve */
1702 if (!ec_point_verify(point)) {
1713 static int getmppoint(const char **data, int *datalen, struct ec_point *point)
1718 getstring(data, datalen, &p, &length);
1720 return decodepoint(p, length, point);
1723 /* ----------------------------------------------------------------------
1724 * Exposed ECDSA interface
1727 struct ecsign_extra {
1728 struct ec_curve *(*curve)(void);
1729 const struct ssh_hash *hash;
1731 /* These fields are used by the OpenSSH PEM format importer/exporter */
1732 const unsigned char *oid;
1736 static void ecdsa_freekey(void *key)
1738 struct ec_key *ec = (struct ec_key *) key;
1741 if (ec->publicKey.x)
1742 freebn(ec->publicKey.x);
1743 if (ec->publicKey.y)
1744 freebn(ec->publicKey.y);
1745 if (ec->publicKey.z)
1746 freebn(ec->publicKey.z);
1748 freebn(ec->privateKey);
1752 static void *ecdsa_newkey(const struct ssh_signkey *self,
1753 const char *data, int len)
1755 const struct ecsign_extra *extra =
1756 (const struct ecsign_extra *)self->extra;
1760 struct ec_curve *curve;
1762 getstring(&data, &len, &p, &slen);
1767 curve = extra->curve();
1768 assert(curve->type == EC_WEIERSTRASS || curve->type == EC_EDWARDS);
1770 /* Curve name is duplicated for Weierstrass form */
1771 if (curve->type == EC_WEIERSTRASS) {
1772 getstring(&data, &len, &p, &slen);
1773 if (!p) return NULL;
1774 if (!match_ssh_id(slen, p, curve->name)) return NULL;
1777 ec = snew(struct ec_key);
1780 ec->publicKey.curve = curve;
1781 ec->publicKey.infinity = 0;
1782 ec->publicKey.x = NULL;
1783 ec->publicKey.y = NULL;
1784 ec->publicKey.z = NULL;
1785 ec->privateKey = NULL;
1786 if (!getmppoint(&data, &len, &ec->publicKey)) {
1791 if (!ec->publicKey.x || !ec->publicKey.y ||
1792 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
1793 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
1802 static char *ecdsa_fmtkey(void *key)
1804 struct ec_key *ec = (struct ec_key *) key;
1806 int len, i, pos, nibbles;
1807 static const char hex[] = "0123456789abcdef";
1808 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
1811 len = 4 + 2 + 1; /* 2 x "0x", punctuation, \0 */
1812 if (ec->publicKey.curve->name)
1813 len += strlen(ec->publicKey.curve->name); /* Curve name */
1814 len += 4 * (bignum_bitcount(ec->publicKey.x) + 15) / 16;
1815 len += 4 * (bignum_bitcount(ec->publicKey.y) + 15) / 16;
1816 p = snewn(len, char);
1819 if (ec->publicKey.curve->name)
1820 pos += sprintf(p + pos, "%s,", ec->publicKey.curve->name);
1821 pos += sprintf(p + pos, "0x");
1822 nibbles = (3 + bignum_bitcount(ec->publicKey.x)) / 4;
1825 for (i = nibbles; i--;) {
1827 hex[(bignum_byte(ec->publicKey.x, i / 2) >> (4 * (i % 2))) & 0xF];
1829 pos += sprintf(p + pos, ",0x");
1830 nibbles = (3 + bignum_bitcount(ec->publicKey.y)) / 4;
1833 for (i = nibbles; i--;) {
1835 hex[(bignum_byte(ec->publicKey.y, i / 2) >> (4 * (i % 2))) & 0xF];
1841 static unsigned char *ecdsa_public_blob(void *key, int *len)
1843 struct ec_key *ec = (struct ec_key *) key;
1844 int pointlen, bloblen, fullnamelen, namelen;
1846 unsigned char *blob, *p;
1848 fullnamelen = strlen(ec->signalg->name);
1850 if (ec->publicKey.curve->type == EC_EDWARDS) {
1851 /* Edwards compressed form "ssh-ed25519" point y[:-1] + x[0:1] */
1853 pointlen = ec->publicKey.curve->fieldBits / 8;
1855 /* Can't handle this in our loop */
1856 if (pointlen < 2) return NULL;
1858 bloblen = 4 + fullnamelen + 4 + pointlen;
1859 blob = snewn(bloblen, unsigned char);
1862 PUT_32BIT(p, fullnamelen);
1864 memcpy(p, ec->signalg->name, fullnamelen);
1866 PUT_32BIT(p, pointlen);
1869 /* Unset last bit of y and set first bit of x in its place */
1870 for (i = 0; i < pointlen - 1; ++i) {
1871 *p++ = bignum_byte(ec->publicKey.y, i);
1873 /* Unset last bit of y and set first bit of x in its place */
1874 *p = bignum_byte(ec->publicKey.y, i) & 0x7f;
1875 *p++ |= bignum_bit(ec->publicKey.x, 0) << 7;
1876 } else if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
1877 assert(ec->publicKey.curve->name);
1878 namelen = strlen(ec->publicKey.curve->name);
1880 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
1883 * string "ecdsa-sha2-<name>", string "<name>", 0x04 point x, y.
1885 bloblen = 4 + fullnamelen + 4 + namelen + 4 + 1 + (pointlen * 2);
1886 blob = snewn(bloblen, unsigned char);
1889 PUT_32BIT(p, fullnamelen);
1891 memcpy(p, ec->signalg->name, fullnamelen);
1893 PUT_32BIT(p, namelen);
1895 memcpy(p, ec->publicKey.curve->name, namelen);
1897 PUT_32BIT(p, (2 * pointlen) + 1);
1900 for (i = pointlen; i--;) {
1901 *p++ = bignum_byte(ec->publicKey.x, i);
1903 for (i = pointlen; i--;) {
1904 *p++ = bignum_byte(ec->publicKey.y, i);
1910 assert(p == blob + bloblen);
1916 static unsigned char *ecdsa_private_blob(void *key, int *len)
1918 struct ec_key *ec = (struct ec_key *) key;
1919 int keylen, bloblen;
1921 unsigned char *blob, *p;
1923 if (!ec->privateKey) return NULL;
1925 if (ec->publicKey.curve->type == EC_EDWARDS) {
1927 keylen = (bignum_bitcount(ec->privateKey) + 7) / 8;
1930 keylen = (bignum_bitcount(ec->privateKey) + 8) / 8;
1934 * mpint privateKey. Total 4 + keylen.
1936 bloblen = 4 + keylen;
1937 blob = snewn(bloblen, unsigned char);
1940 PUT_32BIT(p, keylen);
1942 if (ec->publicKey.curve->type == EC_EDWARDS) {
1944 for (i = 0; i < keylen; ++i)
1945 *p++ = bignum_byte(ec->privateKey, i);
1947 for (i = keylen; i--;)
1948 *p++ = bignum_byte(ec->privateKey, i);
1951 assert(p == blob + bloblen);
1956 static void *ecdsa_createkey(const struct ssh_signkey *self,
1957 const unsigned char *pub_blob, int pub_len,
1958 const unsigned char *priv_blob, int priv_len)
1961 struct ec_point *publicKey;
1962 const char *pb = (const char *) priv_blob;
1964 ec = (struct ec_key*)ecdsa_newkey(self, (const char *) pub_blob, pub_len);
1969 if (ec->publicKey.curve->type != EC_WEIERSTRASS
1970 && ec->publicKey.curve->type != EC_EDWARDS) {
1975 if (ec->publicKey.curve->type == EC_EDWARDS) {
1976 ec->privateKey = getmp_le(&pb, &priv_len);
1978 ec->privateKey = getmp(&pb, &priv_len);
1980 if (!ec->privateKey) {
1985 /* Check that private key generates public key */
1986 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
1989 bignum_cmp(publicKey->x, ec->publicKey.x) ||
1990 bignum_cmp(publicKey->y, ec->publicKey.y))
1995 ec_point_free(publicKey);
2000 static void *ed25519_openssh_createkey(const struct ssh_signkey *self,
2001 const unsigned char **blob, int *len)
2004 struct ec_point *publicKey;
2008 getstring((const char**)blob, len, &p, &plen);
2014 ec = snew(struct ec_key);
2017 ec->publicKey.curve = ec_ed25519();
2018 ec->publicKey.infinity = 0;
2019 ec->privateKey = NULL;
2020 ec->publicKey.x = NULL;
2021 ec->publicKey.z = NULL;
2022 ec->publicKey.y = NULL;
2024 if (!decodepoint_ed(p, plen, &ec->publicKey))
2030 getstring((const char**)blob, len, &q, &qlen);
2036 ec->privateKey = bignum_from_bytes_le((const unsigned char *)q, 32);
2038 /* Check that private key generates public key */
2039 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
2042 bignum_cmp(publicKey->x, ec->publicKey.x) ||
2043 bignum_cmp(publicKey->y, ec->publicKey.y))
2048 ec_point_free(publicKey);
2050 /* The OpenSSH format for ed25519 private keys also for some
2051 * reason encodes an extra copy of the public key in the second
2052 * half of the secret-key string. Check that that's present and
2053 * correct as well, otherwise the key we think we've imported
2054 * won't behave identically to the way OpenSSH would have treated
2056 if (plen != 32 || 0 != memcmp(q + 32, p, 32)) {
2064 static int ed25519_openssh_fmtkey(void *key, unsigned char *blob, int len)
2066 struct ec_key *ec = (struct ec_key *) key;
2073 if (ec->publicKey.curve->type != EC_EDWARDS) {
2077 pointlen = (bignum_bitcount(ec->publicKey.y) + 7) / 8;
2078 keylen = (bignum_bitcount(ec->privateKey) + 7) / 8;
2079 bloblen = 4 + pointlen + 4 + keylen + pointlen;
2084 /* Encode the public point */
2085 PUT_32BIT(blob, pointlen);
2088 for (i = 0; i < pointlen - 1; ++i) {
2089 *blob++ = bignum_byte(ec->publicKey.y, i);
2091 /* Unset last bit of y and set first bit of x in its place */
2092 *blob = bignum_byte(ec->publicKey.y, i) & 0x7f;
2093 *blob++ |= bignum_bit(ec->publicKey.x, 0) << 7;
2095 PUT_32BIT(blob, keylen + pointlen);
2097 for (i = 0; i < keylen; ++i) {
2098 *blob++ = bignum_byte(ec->privateKey, i);
2100 /* Now encode an extra copy of the public point as the second half
2101 * of the private key string, as the OpenSSH format for some
2102 * reason requires */
2103 for (i = 0; i < pointlen - 1; ++i) {
2104 *blob++ = bignum_byte(ec->publicKey.y, i);
2106 /* Unset last bit of y and set first bit of x in its place */
2107 *blob = bignum_byte(ec->publicKey.y, i) & 0x7f;
2108 *blob++ |= bignum_bit(ec->publicKey.x, 0) << 7;
2113 static void *ecdsa_openssh_createkey(const struct ssh_signkey *self,
2114 const unsigned char **blob, int *len)
2116 const struct ecsign_extra *extra =
2117 (const struct ecsign_extra *)self->extra;
2118 const char **b = (const char **) blob;
2122 struct ec_curve *curve;
2123 struct ec_point *publicKey;
2125 getstring(b, len, &p, &slen);
2130 curve = extra->curve();
2131 assert(curve->type == EC_WEIERSTRASS);
2133 ec = snew(struct ec_key);
2136 ec->publicKey.curve = curve;
2137 ec->publicKey.infinity = 0;
2138 ec->publicKey.x = NULL;
2139 ec->publicKey.y = NULL;
2140 ec->publicKey.z = NULL;
2141 if (!getmppoint(b, len, &ec->publicKey)) {
2145 ec->privateKey = NULL;
2147 if (!ec->publicKey.x || !ec->publicKey.y ||
2148 bignum_cmp(ec->publicKey.x, curve->p) >= 0 ||
2149 bignum_cmp(ec->publicKey.y, curve->p) >= 0)
2155 ec->privateKey = getmp(b, len);
2156 if (ec->privateKey == NULL)
2162 /* Now check that the private key makes the public key */
2163 publicKey = ec_public(ec->privateKey, ec->publicKey.curve);
2170 if (bignum_cmp(ec->publicKey.x, publicKey->x) ||
2171 bignum_cmp(ec->publicKey.y, publicKey->y))
2173 /* Private key doesn't make the public key on the given curve */
2175 ec_point_free(publicKey);
2179 ec_point_free(publicKey);
2184 static int ecdsa_openssh_fmtkey(void *key, unsigned char *blob, int len)
2186 struct ec_key *ec = (struct ec_key *) key;
2193 if (ec->publicKey.curve->type != EC_WEIERSTRASS) {
2197 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2198 namelen = strlen(ec->publicKey.curve->name);
2200 4 + namelen /* <LEN> nistpXXX */
2201 + 4 + 1 + (pointlen * 2) /* <LEN> 0x04 pX pY */
2202 + ssh2_bignum_length(ec->privateKey);
2209 PUT_32BIT(blob+bloblen, namelen);
2211 memcpy(blob+bloblen, ec->publicKey.curve->name, namelen);
2214 PUT_32BIT(blob+bloblen, 1 + (pointlen * 2));
2216 blob[bloblen++] = 0x04;
2217 for (i = pointlen; i--; )
2218 blob[bloblen++] = bignum_byte(ec->publicKey.x, i);
2219 for (i = pointlen; i--; )
2220 blob[bloblen++] = bignum_byte(ec->publicKey.y, i);
2222 pointlen = (bignum_bitcount(ec->privateKey) + 8) / 8;
2223 PUT_32BIT(blob+bloblen, pointlen);
2225 for (i = pointlen; i--; )
2226 blob[bloblen++] = bignum_byte(ec->privateKey, i);
2231 static int ecdsa_pubkey_bits(const struct ssh_signkey *self,
2232 const void *blob, int len)
2237 ec = (struct ec_key*)ecdsa_newkey(self, (const char *) blob, len);
2240 ret = ec->publicKey.curve->fieldBits;
2246 static int ecdsa_verifysig(void *key, const char *sig, int siglen,
2247 const char *data, int datalen)
2249 struct ec_key *ec = (struct ec_key *) key;
2250 const struct ecsign_extra *extra =
2251 (const struct ecsign_extra *)ec->signalg->extra;
2257 if (!ec->publicKey.x || !ec->publicKey.y || !ec->publicKey.curve)
2260 /* Check the signature starts with the algorithm name */
2261 getstring(&sig, &siglen, &p, &slen);
2265 if (!match_ssh_id(slen, p, ec->signalg->name)) {
2269 getstring(&sig, &siglen, &p, &slen);
2270 if (ec->publicKey.curve->type == EC_EDWARDS) {
2274 /* Check that the signature is two times the length of a point */
2275 if (slen != (ec->publicKey.curve->fieldBits / 8) * 2) {
2279 /* Check it's the 256 bit field so that SHA512 is the correct hash */
2280 if (ec->publicKey.curve->fieldBits != 256) {
2284 /* Get the signature */
2285 r = ec_point_new(ec->publicKey.curve, NULL, NULL, NULL, 0);
2289 if (!decodepoint(p, ec->publicKey.curve->fieldBits / 8, r)) {
2293 s = bignum_from_bytes_le((unsigned char*)p + (ec->publicKey.curve->fieldBits / 8),
2294 ec->publicKey.curve->fieldBits / 8);
2296 /* Get the hash of the encoded value of R + encoded value of pk + message */
2300 unsigned char digest[512 / 8];
2304 /* Add encoded r (no need to encode it again, it was in the signature) */
2305 SHA512_Bytes(&hs, p, ec->publicKey.curve->fieldBits / 8);
2307 /* Encode pk and add it */
2308 pointlen = ec->publicKey.curve->fieldBits / 8;
2309 for (i = 0; i < pointlen - 1; ++i) {
2310 b = bignum_byte(ec->publicKey.y, i);
2311 SHA512_Bytes(&hs, &b, 1);
2313 /* Unset last bit of y and set first bit of x in its place */
2314 b = bignum_byte(ec->publicKey.y, i) & 0x7f;
2315 b |= bignum_bit(ec->publicKey.x, 0) << 7;
2316 SHA512_Bytes(&hs, &b, 1);
2318 /* Add the message itself */
2319 SHA512_Bytes(&hs, data, datalen);
2322 SHA512_Final(&hs, digest);
2324 /* Convert to Bignum */
2325 h = bignum_from_bytes_le(digest, sizeof(digest));
2328 /* Verify sB == r + h*publicKey */
2330 struct ec_point *lhs, *rhs, *tmp;
2333 lhs = ecp_mul(&ec->publicKey.curve->e.B, s);
2341 /* rhs = r + h*publicKey */
2342 tmp = ecp_mul(&ec->publicKey, h);
2349 rhs = ecp_add(r, tmp, 0);
2357 /* Check the point is the same */
2358 ret = !bignum_cmp(lhs->x, rhs->x);
2360 ret = !bignum_cmp(lhs->y, rhs->y);
2370 unsigned char digest[512 / 8];
2373 r = getmp(&p, &slen);
2375 s = getmp(&p, &slen);
2381 digestLen = extra->hash->hlen;
2382 assert(digestLen <= sizeof(digest));
2383 hashctx = extra->hash->init();
2384 extra->hash->bytes(hashctx, data, datalen);
2385 extra->hash->final(hashctx, digest);
2387 /* Verify the signature */
2388 ret = _ecdsa_verify(&ec->publicKey, digest, digestLen, r, s);
2397 static unsigned char *ecdsa_sign(void *key, const char *data, int datalen,
2400 struct ec_key *ec = (struct ec_key *) key;
2401 const struct ecsign_extra *extra =
2402 (const struct ecsign_extra *)ec->signalg->extra;
2403 unsigned char digest[512 / 8];
2405 Bignum r = NULL, s = NULL;
2406 unsigned char *buf, *p;
2407 int rlen, slen, namelen;
2410 if (!ec->privateKey || !ec->publicKey.curve) {
2414 if (ec->publicKey.curve->type == EC_EDWARDS) {
2415 struct ec_point *rp;
2416 int pointlen = ec->publicKey.curve->fieldBits / 8;
2418 /* hash = H(sk) (where hash creates 2 * fieldBits)
2420 * a = 2^(b-2) + SUM(2^i * h_i) for i = 2 -> b-2
2421 * r = H(h[b/8:b/4] + m)
2423 * S = (r + H(encodepoint(R) + encodepoint(pk) + m) * a) % l */
2425 unsigned char hash[512/8];
2431 for (i = 0; i < pointlen; ++i) {
2432 unsigned char b = (unsigned char)bignum_byte(ec->privateKey, i);
2433 SHA512_Bytes(&hs, &b, 1);
2436 SHA512_Final(&hs, hash);
2438 /* The second part is simply turning the hash into a
2439 * Bignum, however the 2^(b-2) bit *must* be set, and the
2440 * bottom 3 bits *must* not be */
2441 hash[0] &= 0xf8; /* Unset bottom 3 bits (if set) */
2442 hash[31] &= 0x7f; /* Unset above (b-2) */
2443 hash[31] |= 0x40; /* Set 2^(b-2) */
2444 /* Chop off the top part and convert to int */
2445 a = bignum_from_bytes_le(hash, 32);
2449 hash+(ec->publicKey.curve->fieldBits / 8),
2450 (ec->publicKey.curve->fieldBits / 4)
2451 - (ec->publicKey.curve->fieldBits / 8));
2452 SHA512_Bytes(&hs, data, datalen);
2453 SHA512_Final(&hs, hash);
2455 r = bignum_from_bytes_le(hash, 512/8);
2456 rp = ecp_mul(&ec->publicKey.curve->e.B, r);
2463 /* Now calculate s */
2465 /* Encode the point R */
2466 for (i = 0; i < pointlen - 1; ++i) {
2467 b = bignum_byte(rp->y, i);
2468 SHA512_Bytes(&hs, &b, 1);
2470 /* Unset last bit of y and set first bit of x in its place */
2471 b = bignum_byte(rp->y, i) & 0x7f;
2472 b |= bignum_bit(rp->x, 0) << 7;
2473 SHA512_Bytes(&hs, &b, 1);
2475 /* Encode the point pk */
2476 for (i = 0; i < pointlen - 1; ++i) {
2477 b = bignum_byte(ec->publicKey.y, i);
2478 SHA512_Bytes(&hs, &b, 1);
2480 /* Unset last bit of y and set first bit of x in its place */
2481 b = bignum_byte(ec->publicKey.y, i) & 0x7f;
2482 b |= bignum_bit(ec->publicKey.x, 0) << 7;
2483 SHA512_Bytes(&hs, &b, 1);
2485 /* Add the message */
2486 SHA512_Bytes(&hs, data, datalen);
2487 SHA512_Final(&hs, hash);
2492 tmp = bignum_from_bytes_le(hash, 512/8);
2493 tmp2 = modmul(tmp, a, ec->publicKey.curve->e.l);
2496 tmp = bigadd(r, tmp2);
2499 s = bigmod(tmp, ec->publicKey.curve->e.l);
2504 /* Format the output */
2505 namelen = strlen(ec->signalg->name);
2506 *siglen = 4+namelen+4+((ec->publicKey.curve->fieldBits / 8)*2);
2507 buf = snewn(*siglen, unsigned char);
2509 PUT_32BIT(p, namelen);
2511 memcpy(p, ec->signalg->name, namelen);
2513 PUT_32BIT(p, ((ec->publicKey.curve->fieldBits / 8)*2));
2516 /* Encode the point */
2517 pointlen = ec->publicKey.curve->fieldBits / 8;
2518 for (i = 0; i < pointlen - 1; ++i) {
2519 *p++ = bignum_byte(rp->y, i);
2521 /* Unset last bit of y and set first bit of x in its place */
2522 *p = bignum_byte(rp->y, i) & 0x7f;
2523 *p++ |= bignum_bit(rp->x, 0) << 7;
2526 /* Encode the int */
2527 for (i = 0; i < pointlen; ++i) {
2528 *p++ = bignum_byte(s, i);
2534 digestLen = extra->hash->hlen;
2535 assert(digestLen <= sizeof(digest));
2536 hashctx = extra->hash->init();
2537 extra->hash->bytes(hashctx, data, datalen);
2538 extra->hash->final(hashctx, digest);
2540 /* Do the signature */
2541 _ecdsa_sign(ec->privateKey, ec->publicKey.curve, digest, digestLen, &r, &s);
2548 rlen = (bignum_bitcount(r) + 8) / 8;
2549 slen = (bignum_bitcount(s) + 8) / 8;
2551 namelen = strlen(ec->signalg->name);
2553 /* Format the output */
2554 *siglen = 8+namelen+rlen+slen+8;
2555 buf = snewn(*siglen, unsigned char);
2557 PUT_32BIT(p, namelen);
2559 memcpy(p, ec->signalg->name, namelen);
2561 PUT_32BIT(p, rlen + slen + 8);
2565 for (i = rlen; i--;)
2566 *p++ = bignum_byte(r, i);
2569 for (i = slen; i--;)
2570 *p++ = bignum_byte(s, i);
2579 const struct ecsign_extra sign_extra_ed25519 = {
2583 const struct ssh_signkey ssh_ecdsa_ed25519 = {
2590 ed25519_openssh_createkey,
2591 ed25519_openssh_fmtkey,
2592 2 /* point, private exponent */,
2598 &sign_extra_ed25519,
2601 /* OID: 1.2.840.10045.3.1.7 (ansiX9p256r1) */
2602 static const unsigned char nistp256_oid[] = {
2603 0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07
2605 const struct ecsign_extra sign_extra_nistp256 = {
2606 ec_p256, &ssh_sha256,
2607 nistp256_oid, lenof(nistp256_oid),
2609 const struct ssh_signkey ssh_ecdsa_nistp256 = {
2616 ecdsa_openssh_createkey,
2617 ecdsa_openssh_fmtkey,
2618 3 /* curve name, point, private exponent */,
2622 "ecdsa-sha2-nistp256",
2623 "ecdsa-sha2-nistp256",
2624 &sign_extra_nistp256,
2627 /* OID: 1.3.132.0.34 (secp384r1) */
2628 static const unsigned char nistp384_oid[] = {
2629 0x2b, 0x81, 0x04, 0x00, 0x22
2631 const struct ecsign_extra sign_extra_nistp384 = {
2632 ec_p384, &ssh_sha384,
2633 nistp384_oid, lenof(nistp384_oid),
2635 const struct ssh_signkey ssh_ecdsa_nistp384 = {
2642 ecdsa_openssh_createkey,
2643 ecdsa_openssh_fmtkey,
2644 3 /* curve name, point, private exponent */,
2648 "ecdsa-sha2-nistp384",
2649 "ecdsa-sha2-nistp384",
2650 &sign_extra_nistp384,
2653 /* OID: 1.3.132.0.35 (secp521r1) */
2654 static const unsigned char nistp521_oid[] = {
2655 0x2b, 0x81, 0x04, 0x00, 0x23
2657 const struct ecsign_extra sign_extra_nistp521 = {
2658 ec_p521, &ssh_sha512,
2659 nistp521_oid, lenof(nistp521_oid),
2661 const struct ssh_signkey ssh_ecdsa_nistp521 = {
2668 ecdsa_openssh_createkey,
2669 ecdsa_openssh_fmtkey,
2670 3 /* curve name, point, private exponent */,
2674 "ecdsa-sha2-nistp521",
2675 "ecdsa-sha2-nistp521",
2676 &sign_extra_nistp521,
2679 /* ----------------------------------------------------------------------
2680 * Exposed ECDH interface
2683 struct eckex_extra {
2684 struct ec_curve *(*curve)(void);
2687 static Bignum ecdh_calculate(const Bignum private,
2688 const struct ec_point *public)
2692 p = ecp_mul(public, private);
2693 if (!p) return NULL;
2697 if (p->curve->type == EC_MONTGOMERY) {
2699 * Endianness-swap. The Curve25519 algorithm definition
2700 * assumes you were doing your computation in arrays of 32
2701 * little-endian bytes, and now specifies that you take your
2702 * final one of those and convert it into a bignum in
2703 * _network_ byte order, i.e. big-endian.
2705 * In particular, the spec says, you convert the _whole_ 32
2706 * bytes into a bignum. That is, on the rare occasions that
2707 * p->x has come out with the most significant 8 bits zero, we
2708 * have to imagine that being represented by a 32-byte string
2709 * with the last byte being zero, so that has to be converted
2710 * into an SSH-2 bignum with the _low_ byte zero, i.e. a
2714 int bytes = (p->curve->fieldBits+7) / 8;
2715 unsigned char *byteorder = snewn(bytes, unsigned char);
2716 for (i = 0; i < bytes; ++i) {
2717 byteorder[i] = bignum_byte(ret, i);
2720 ret = bignum_from_bytes(byteorder, bytes);
2721 smemclr(byteorder, bytes);
2729 const char *ssh_ecdhkex_curve_textname(const struct ssh_kex *kex)
2731 const struct eckex_extra *extra = (const struct eckex_extra *)kex->extra;
2732 struct ec_curve *curve = extra->curve();
2733 return curve->textname;
2736 void *ssh_ecdhkex_newkey(const struct ssh_kex *kex)
2738 const struct eckex_extra *extra = (const struct eckex_extra *)kex->extra;
2739 struct ec_curve *curve;
2741 struct ec_point *publicKey;
2743 curve = extra->curve();
2745 key = snew(struct ec_key);
2747 key->signalg = NULL;
2748 key->publicKey.curve = curve;
2750 if (curve->type == EC_MONTGOMERY) {
2751 unsigned char bytes[32] = {0};
2754 for (i = 0; i < sizeof(bytes); ++i)
2756 bytes[i] = (unsigned char)random_byte();
2761 key->privateKey = bignum_from_bytes(bytes, sizeof(bytes));
2762 for (i = 0; i < sizeof(bytes); ++i)
2764 ((volatile char*)bytes)[i] = 0;
2766 if (!key->privateKey) {
2770 publicKey = ecp_mul(&key->publicKey.curve->m.G, key->privateKey);
2772 freebn(key->privateKey);
2776 key->publicKey.x = publicKey->x;
2777 key->publicKey.y = publicKey->y;
2778 key->publicKey.z = NULL;
2781 key->privateKey = bignum_random_in_range(One, key->publicKey.curve->w.n);
2782 if (!key->privateKey) {
2786 publicKey = ecp_mul(&key->publicKey.curve->w.G, key->privateKey);
2788 freebn(key->privateKey);
2792 key->publicKey.x = publicKey->x;
2793 key->publicKey.y = publicKey->y;
2794 key->publicKey.z = NULL;
2800 char *ssh_ecdhkex_getpublic(void *key, int *len)
2802 struct ec_key *ec = (struct ec_key*)key;
2807 pointlen = (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8;
2809 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2810 *len = 1 + pointlen * 2;
2814 point = (char*)snewn(*len, char);
2817 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2819 for (i = pointlen; i--;) {
2820 *p++ = bignum_byte(ec->publicKey.x, i);
2822 for (i = pointlen; i--;) {
2823 *p++ = bignum_byte(ec->publicKey.y, i);
2826 for (i = 0; i < pointlen; ++i) {
2827 *p++ = bignum_byte(ec->publicKey.x, i);
2834 Bignum ssh_ecdhkex_getkey(void *key, char *remoteKey, int remoteKeyLen)
2836 struct ec_key *ec = (struct ec_key*) key;
2837 struct ec_point remote;
2840 if (ec->publicKey.curve->type == EC_WEIERSTRASS) {
2841 remote.curve = ec->publicKey.curve;
2842 remote.infinity = 0;
2843 if (!decodepoint(remoteKey, remoteKeyLen, &remote)) {
2847 /* Point length has to be the same length */
2848 if (remoteKeyLen != (bignum_bitcount(ec->publicKey.curve->p) + 7) / 8) {
2852 remote.curve = ec->publicKey.curve;
2853 remote.infinity = 0;
2854 remote.x = bignum_from_bytes_le((unsigned char*)remoteKey, remoteKeyLen);
2859 ret = ecdh_calculate(ec->privateKey, &remote);
2860 if (remote.x) freebn(remote.x);
2861 if (remote.y) freebn(remote.y);
2865 void ssh_ecdhkex_freekey(void *key)
2870 static const struct eckex_extra kex_extra_curve25519 = { ec_curve25519 };
2871 static const struct ssh_kex ssh_ec_kex_curve25519 = {
2872 "curve25519-sha256@libssh.org", NULL, KEXTYPE_ECDH,
2873 &ssh_sha256, &kex_extra_curve25519,
2876 const struct eckex_extra kex_extra_nistp256 = { ec_p256 };
2877 static const struct ssh_kex ssh_ec_kex_nistp256 = {
2878 "ecdh-sha2-nistp256", NULL, KEXTYPE_ECDH,
2879 &ssh_sha256, &kex_extra_nistp256,
2882 const struct eckex_extra kex_extra_nistp384 = { ec_p384 };
2883 static const struct ssh_kex ssh_ec_kex_nistp384 = {
2884 "ecdh-sha2-nistp384", NULL, KEXTYPE_ECDH,
2885 &ssh_sha384, &kex_extra_nistp384,
2888 const struct eckex_extra kex_extra_nistp521 = { ec_p521 };
2889 static const struct ssh_kex ssh_ec_kex_nistp521 = {
2890 "ecdh-sha2-nistp521", NULL, KEXTYPE_ECDH,
2891 &ssh_sha512, &kex_extra_nistp521,
2894 static const struct ssh_kex *const ec_kex_list[] = {
2895 &ssh_ec_kex_curve25519,
2896 &ssh_ec_kex_nistp256,
2897 &ssh_ec_kex_nistp384,
2898 &ssh_ec_kex_nistp521,
2901 const struct ssh_kexes ssh_ecdh_kex = {
2902 sizeof(ec_kex_list) / sizeof(*ec_kex_list),
2906 /* ----------------------------------------------------------------------
2907 * Helper functions for finding key algorithms and returning auxiliary
2911 const struct ssh_signkey *ec_alg_by_oid(int len, const void *oid,
2912 const struct ec_curve **curve)
2914 static const struct ssh_signkey *algs_with_oid[] = {
2915 &ssh_ecdsa_nistp256,
2916 &ssh_ecdsa_nistp384,
2917 &ssh_ecdsa_nistp521,
2921 for (i = 0; i < lenof(algs_with_oid); i++) {
2922 const struct ssh_signkey *alg = algs_with_oid[i];
2923 const struct ecsign_extra *extra =
2924 (const struct ecsign_extra *)alg->extra;
2925 if (len == extra->oidlen && !memcmp(oid, extra->oid, len)) {
2926 *curve = extra->curve();
2933 const unsigned char *ec_alg_oid(const struct ssh_signkey *alg,
2936 const struct ecsign_extra *extra = (const struct ecsign_extra *)alg->extra;
2937 *oidlen = extra->oidlen;
2941 const int ec_nist_alg_and_curve_by_bits(int bits,
2942 const struct ec_curve **curve,
2943 const struct ssh_signkey **alg)
2946 case 256: *alg = &ssh_ecdsa_nistp256; break;
2947 case 384: *alg = &ssh_ecdsa_nistp384; break;
2948 case 521: *alg = &ssh_ecdsa_nistp521; break;
2949 default: return FALSE;
2951 *curve = ((struct ecsign_extra *)(*alg)->extra)->curve();
2955 const int ec_ed_alg_and_curve_by_bits(int bits,
2956 const struct ec_curve **curve,
2957 const struct ssh_signkey **alg)
2960 case 256: *alg = &ssh_ecdsa_ed25519; break;
2961 default: return FALSE;
2963 *curve = ((struct ecsign_extra *)(*alg)->extra)->curve();