| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442 |
- /* 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;
- }
|