/* NIST P-256 ECDH; see tls_p256.h. */ #include "tls_p256.h" typedef unsigned int fe[8]; /* little-endian 32-bit limbs */ struct jac { fe x, y, z; /* Montgomery form; z = 0: infinity */ int inf; }; /* p = 2^256 - 2^224 + 2^192 + 2^96 - 1 */ static const fe P = { 0xffffffff, 0xffffffff, 0xffffffff, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0xffffffff }; /* b, Gx, Gy (normal form, little-endian limbs) */ static const fe B = { 0x27d2604b, 0x3bce3c3e, 0xcc53b0f6, 0x651d06b0, 0x769886bc, 0xb3ebbd55, 0xaa3a93e7, 0x5ac635d8 }; static const fe GX = { 0xd898c296, 0xf4a13945, 0x2deb33a0, 0x77037d81, 0x63a440f2, 0xf8bce6e5, 0xe12c4247, 0x6b17d1f2 }; static const fe GY = { 0x37bf51f5, 0xcbb64068, 0x6b315ece, 0x2bce3357, 0x7c0f9e16, 0x8ee7eb4a, 0xfe1a7f9b, 0x4fe342e2 }; static fe R2; /* R^2 mod p, R = 2^256 */ static fe ONE_M; /* 1 in Montgomery form */ static int ready; static void fe_copy(fe r, const fe a) { int i; for (i = 0; i < 8; i++) r[i] = a[i]; } static int fe_is_zero(const fe a) { unsigned int d = 0; int i; for (i = 0; i < 8; i++) d |= a[i]; return d == 0; } static int fe_eq(const fe a, const fe b) { unsigned int d = 0; int i; for (i = 0; i < 8; i++) d |= a[i] ^ b[i]; return d == 0; } /* r = a - b (raw); returns the borrow. */ static unsigned int raw_sub(fe r, const fe a, const fe b) { unsigned long long t; unsigned int borrow = 0; int i; for (i = 0; i < 8; i++) { t = (unsigned long long)a[i] - b[i] - borrow; r[i] = (unsigned int)t; borrow = (unsigned int)(t >> 63); } return borrow; } /* r = a + b (raw); returns the carry. */ static unsigned int raw_add(fe r, const fe a, const fe b) { unsigned long long t; unsigned int carry = 0; int i; for (i = 0; i < 8; i++) { t = (unsigned long long)a[i] + b[i] + carry; r[i] = (unsigned int)t; carry = (unsigned int)(t >> 32); } return carry; } static int fe_lt_p(const fe a) { fe t; return raw_sub(t, a, P) != 0; } static void fe_add(fe r, const fe a, const fe b) { fe t; unsigned int carry = raw_add(r, a, b); if (carry || !fe_lt_p(r)) { raw_sub(t, r, P); fe_copy(r, t); } } static void fe_sub(fe r, const fe a, const fe b) { fe t; if (raw_sub(r, a, b)) { raw_add(t, r, P); fe_copy(r, t); } } /* Montgomery product r = a * b / R mod p (CIOS; -p^-1 mod 2^32 = 1). */ static void fe_mul(fe r, const fe a, const fe b) { unsigned int t[10]; unsigned long long c; unsigned int m; int i, j; for (i = 0; i < 10; i++) t[i] = 0; for (i = 0; i < 8; i++) { c = 0; for (j = 0; j < 8; j++) { c += (unsigned long long)t[j] + (unsigned long long)a[j] * b[i]; t[j] = (unsigned int)c; c >>= 32; } c += t[8]; t[8] = (unsigned int)c; t[9] = (unsigned int)(c >> 32); m = t[0]; c = (unsigned long long)t[0] + (unsigned long long)m * P[0]; c >>= 32; for (j = 1; j < 8; j++) { c += (unsigned long long)t[j] + (unsigned long long)m * P[j]; t[j - 1] = (unsigned int)c; c >>= 32; } c += t[8]; t[7] = (unsigned int)c; t[8] = t[9] + (unsigned int)(c >> 32); } for (i = 0; i < 8; i++) r[i] = t[i]; if (t[8] || !fe_lt_p(r)) { fe s; raw_sub(s, r, P); fe_copy(r, s); } } static void fe_sqr(fe r, const fe a) { fe_mul(r, a, a); } static void fe_to_mont(fe r, const fe a) { fe_mul(r, a, R2); } static void fe_from_mont(fe r, const fe a) { fe one = { 1, 0, 0, 0, 0, 0, 0, 0 }; fe_mul(r, a, one); } /* r = a^(p-2) = a^-1 (Montgomery domain). */ static void fe_inv(fe r, const fe a) { fe pm2, acc; int i; fe_copy(pm2, P); pm2[0] -= 2; fe_copy(acc, ONE_M); for (i = 255; i >= 0; i--) { fe_sqr(acc, acc); if ((pm2[i >> 5] >> (i & 31)) & 1) fe_mul(acc, acc, a); } fe_copy(r, acc); } static void p256_init(void) { fe x, t; int i; if (ready) return; /* R mod p = 2^256 - p, then double 256 times: R^2 mod p. */ for (i = 0; i < 8; i++) t[i] = 0; raw_sub(x, t, P); /* 2^256 - p (wraps) */ for (i = 0; i < 256; i++) fe_add(x, x, x); fe_copy(R2, x); { fe one = { 1, 0, 0, 0, 0, 0, 0, 0 }; fe_to_mont(ONE_M, one); } ready = 1; } /* ---- points (Jacobian, a = -3) ---- */ static void pt_double(struct jac *r, const struct jac *p) { fe delta, gamma, beta, alpha, t1, t2, x3, y3, z3; if (p->inf || fe_is_zero(p->y)) { r->inf = 1; return; } fe_sqr(delta, p->z); fe_sqr(gamma, p->y); fe_mul(beta, p->x, gamma); fe_sub(t1, p->x, delta); fe_add(t2, p->x, delta); fe_mul(alpha, t1, t2); fe_add(t1, alpha, alpha); fe_add(alpha, t1, alpha); /* 3 (x - d)(x + d) */ fe_sqr(x3, alpha); fe_add(t1, beta, beta); fe_add(t1, t1, t1); fe_add(t2, t1, t1); /* 8 beta */ fe_sub(x3, x3, t2); fe_add(t2, p->y, p->z); fe_sqr(z3, t2); fe_sub(z3, z3, gamma); fe_sub(z3, z3, delta); fe_sub(t1, t1, x3); /* 4 beta - x3 */ fe_mul(y3, alpha, t1); fe_sqr(t2, gamma); fe_add(t2, t2, t2); fe_add(t2, t2, t2); fe_add(t2, t2, t2); /* 8 gamma^2 */ fe_sub(y3, y3, t2); fe_copy(r->x, x3); fe_copy(r->y, y3); fe_copy(r->z, z3); r->inf = 0; } static void pt_add(struct jac *r, const struct jac *a, const struct jac *b) { fe z1z1, z2z2, u1, u2, s1, s2, h, rr, i, j, v, t, x3, y3, z3; if (a->inf) { *r = *b; return; } if (b->inf) { *r = *a; return; } fe_sqr(z1z1, a->z); fe_sqr(z2z2, b->z); fe_mul(u1, a->x, z2z2); fe_mul(u2, b->x, z1z1); fe_mul(t, b->z, z2z2); fe_mul(s1, a->y, t); fe_mul(t, a->z, z1z1); fe_mul(s2, b->y, t); fe_sub(h, u2, u1); fe_sub(rr, s2, s1); if (fe_is_zero(h)) { if (fe_is_zero(rr)) { pt_double(r, a); return; } r->inf = 1; return; } fe_add(rr, rr, rr); fe_add(t, h, h); fe_sqr(i, t); fe_mul(j, h, i); fe_mul(v, u1, i); fe_sqr(x3, rr); fe_sub(x3, x3, j); fe_sub(x3, x3, v); fe_sub(x3, x3, v); fe_sub(t, v, x3); fe_mul(y3, rr, t); fe_mul(t, s1, j); fe_add(t, t, t); fe_sub(y3, y3, t); fe_add(t, a->z, b->z); fe_sqr(z3, t); fe_sub(z3, z3, z1z1); fe_sub(z3, z3, z2z2); fe_mul(z3, z3, h); fe_copy(r->x, x3); fe_copy(r->y, y3); fe_copy(r->z, z3); r->inf = 0; } static void pt_mul(struct jac *r, const unsigned char k[32], const struct jac *p) { struct jac acc; int i, bit; acc.inf = 1; for (i = 0; i < 256; i++) { bit = (k[i >> 3] >> (7 - (i & 7))) & 1; /* big-endian bits */ pt_double(&acc, &acc); if (bit) pt_add(&acc, &acc, p); } *r = acc; } /* Affine coordinates in normal form. */ static int pt_affine(const struct jac *p, fe x, fe y) { fe zi, zi2, t; if (p->inf) return -1; fe_inv(zi, p->z); fe_sqr(zi2, zi); fe_mul(t, p->x, zi2); fe_from_mont(x, t); fe_mul(zi2, zi2, zi); fe_mul(t, p->y, zi2); fe_from_mont(y, t); return 0; } static void fe_from_bytes(fe r, const unsigned char *b) { int i; for (i = 0; i < 8; i++) r[i] = ((unsigned int)b[28 - 4 * i] << 24) | ((unsigned int)b[29 - 4 * i] << 16) | ((unsigned int)b[30 - 4 * i] << 8) | b[31 - 4 * i]; } static void fe_to_bytes(unsigned char *b, const fe a) { int i; for (i = 0; i < 8; i++) { b[28 - 4 * i] = (unsigned char)(a[i] >> 24); b[29 - 4 * i] = (unsigned char)(a[i] >> 16); b[30 - 4 * i] = (unsigned char)(a[i] >> 8); b[31 - 4 * i] = (unsigned char)a[i]; } } static int scalar_zero(const unsigned char k[32]) { unsigned int d = 0, i; for (i = 0; i < 32; i++) d |= k[i]; return d == 0; } static void base_point(struct jac *g) { fe_to_mont(g->x, GX); fe_to_mont(g->y, GY); fe_copy(g->z, ONE_M); g->inf = 0; } int p256_public(const unsigned char priv[32], unsigned char pub[65]) { struct jac g, q; fe x, y; p256_init(); if (scalar_zero(priv)) return -1; base_point(&g); pt_mul(&q, priv, &g); if (pt_affine(&q, x, y) != 0) return -1; pub[0] = 0x04; fe_to_bytes(pub + 1, x); fe_to_bytes(pub + 33, y); return 0; } int p256_shared(const unsigned char priv[32], const unsigned char *peer, unsigned int peer_len, unsigned char out[32]) { struct jac p, q; fe x, y, xm, ym, lhs, rhs, t, three, bm; p256_init(); if (peer_len != 65 || peer[0] != 0x04 || scalar_zero(priv)) return -1; fe_from_bytes(x, peer + 1); fe_from_bytes(y, peer + 33); if (!fe_lt_p(x) || !fe_lt_p(y)) return -1; /* On the curve: y^2 = x^3 - 3x + b. */ fe_to_mont(xm, x); fe_to_mont(ym, y); fe_sqr(lhs, ym); fe_sqr(t, xm); fe_mul(rhs, t, xm); fe_add(three, xm, xm); fe_add(three, three, xm); fe_sub(rhs, rhs, three); fe_to_mont(bm, B); fe_add(rhs, rhs, bm); if (!fe_eq(lhs, rhs)) return -1; fe_copy(p.x, xm); fe_copy(p.y, ym); fe_copy(p.z, ONE_M); p.inf = 0; pt_mul(&q, priv, &p); if (pt_affine(&q, x, y) != 0) return -1; fe_to_bytes(out, x); return 0; }