tls_p256.c 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442
  1. /* NIST P-256 ECDH; see tls_p256.h. */
  2. #include "tls_p256.h"
  3. typedef unsigned int fe[8]; /* little-endian 32-bit limbs */
  4. struct jac {
  5. fe x, y, z; /* Montgomery form; z = 0: infinity */
  6. int inf;
  7. };
  8. /* p = 2^256 - 2^224 + 2^192 + 2^96 - 1 */
  9. static const fe P = {
  10. 0xffffffff, 0xffffffff, 0xffffffff, 0x00000000,
  11. 0x00000000, 0x00000000, 0x00000001, 0xffffffff
  12. };
  13. /* b, Gx, Gy (normal form, little-endian limbs) */
  14. static const fe B = {
  15. 0x27d2604b, 0x3bce3c3e, 0xcc53b0f6, 0x651d06b0,
  16. 0x769886bc, 0xb3ebbd55, 0xaa3a93e7, 0x5ac635d8
  17. };
  18. static const fe GX = {
  19. 0xd898c296, 0xf4a13945, 0x2deb33a0, 0x77037d81,
  20. 0x63a440f2, 0xf8bce6e5, 0xe12c4247, 0x6b17d1f2
  21. };
  22. static const fe GY = {
  23. 0x37bf51f5, 0xcbb64068, 0x6b315ece, 0x2bce3357,
  24. 0x7c0f9e16, 0x8ee7eb4a, 0xfe1a7f9b, 0x4fe342e2
  25. };
  26. static fe R2; /* R^2 mod p, R = 2^256 */
  27. static fe ONE_M; /* 1 in Montgomery form */
  28. static int ready;
  29. static void fe_copy(fe r, const fe a)
  30. {
  31. int i;
  32. for (i = 0; i < 8; i++)
  33. r[i] = a[i];
  34. }
  35. static int fe_is_zero(const fe a)
  36. {
  37. unsigned int d = 0;
  38. int i;
  39. for (i = 0; i < 8; i++)
  40. d |= a[i];
  41. return d == 0;
  42. }
  43. static int fe_eq(const fe a, const fe b)
  44. {
  45. unsigned int d = 0;
  46. int i;
  47. for (i = 0; i < 8; i++)
  48. d |= a[i] ^ b[i];
  49. return d == 0;
  50. }
  51. /* r = a - b (raw); returns the borrow. */
  52. static unsigned int raw_sub(fe r, const fe a, const fe b)
  53. {
  54. unsigned long long t;
  55. unsigned int borrow = 0;
  56. int i;
  57. for (i = 0; i < 8; i++) {
  58. t = (unsigned long long)a[i] - b[i] - borrow;
  59. r[i] = (unsigned int)t;
  60. borrow = (unsigned int)(t >> 63);
  61. }
  62. return borrow;
  63. }
  64. /* r = a + b (raw); returns the carry. */
  65. static unsigned int raw_add(fe r, const fe a, const fe b)
  66. {
  67. unsigned long long t;
  68. unsigned int carry = 0;
  69. int i;
  70. for (i = 0; i < 8; i++) {
  71. t = (unsigned long long)a[i] + b[i] + carry;
  72. r[i] = (unsigned int)t;
  73. carry = (unsigned int)(t >> 32);
  74. }
  75. return carry;
  76. }
  77. static int fe_lt_p(const fe a)
  78. {
  79. fe t;
  80. return raw_sub(t, a, P) != 0;
  81. }
  82. static void fe_add(fe r, const fe a, const fe b)
  83. {
  84. fe t;
  85. unsigned int carry = raw_add(r, a, b);
  86. if (carry || !fe_lt_p(r)) {
  87. raw_sub(t, r, P);
  88. fe_copy(r, t);
  89. }
  90. }
  91. static void fe_sub(fe r, const fe a, const fe b)
  92. {
  93. fe t;
  94. if (raw_sub(r, a, b)) {
  95. raw_add(t, r, P);
  96. fe_copy(r, t);
  97. }
  98. }
  99. /* Montgomery product r = a * b / R mod p (CIOS; -p^-1 mod 2^32 = 1). */
  100. static void fe_mul(fe r, const fe a, const fe b)
  101. {
  102. unsigned int t[10];
  103. unsigned long long c;
  104. unsigned int m;
  105. int i, j;
  106. for (i = 0; i < 10; i++)
  107. t[i] = 0;
  108. for (i = 0; i < 8; i++) {
  109. c = 0;
  110. for (j = 0; j < 8; j++) {
  111. c += (unsigned long long)t[j] +
  112. (unsigned long long)a[j] * b[i];
  113. t[j] = (unsigned int)c;
  114. c >>= 32;
  115. }
  116. c += t[8];
  117. t[8] = (unsigned int)c;
  118. t[9] = (unsigned int)(c >> 32);
  119. m = t[0];
  120. c = (unsigned long long)t[0] + (unsigned long long)m * P[0];
  121. c >>= 32;
  122. for (j = 1; j < 8; j++) {
  123. c += (unsigned long long)t[j] +
  124. (unsigned long long)m * P[j];
  125. t[j - 1] = (unsigned int)c;
  126. c >>= 32;
  127. }
  128. c += t[8];
  129. t[7] = (unsigned int)c;
  130. t[8] = t[9] + (unsigned int)(c >> 32);
  131. }
  132. for (i = 0; i < 8; i++)
  133. r[i] = t[i];
  134. if (t[8] || !fe_lt_p(r)) {
  135. fe s;
  136. raw_sub(s, r, P);
  137. fe_copy(r, s);
  138. }
  139. }
  140. static void fe_sqr(fe r, const fe a)
  141. {
  142. fe_mul(r, a, a);
  143. }
  144. static void fe_to_mont(fe r, const fe a)
  145. {
  146. fe_mul(r, a, R2);
  147. }
  148. static void fe_from_mont(fe r, const fe a)
  149. {
  150. fe one = { 1, 0, 0, 0, 0, 0, 0, 0 };
  151. fe_mul(r, a, one);
  152. }
  153. /* r = a^(p-2) = a^-1 (Montgomery domain). */
  154. static void fe_inv(fe r, const fe a)
  155. {
  156. fe pm2, acc;
  157. int i;
  158. fe_copy(pm2, P);
  159. pm2[0] -= 2;
  160. fe_copy(acc, ONE_M);
  161. for (i = 255; i >= 0; i--) {
  162. fe_sqr(acc, acc);
  163. if ((pm2[i >> 5] >> (i & 31)) & 1)
  164. fe_mul(acc, acc, a);
  165. }
  166. fe_copy(r, acc);
  167. }
  168. static void p256_init(void)
  169. {
  170. fe x, t;
  171. int i;
  172. if (ready)
  173. return;
  174. /* R mod p = 2^256 - p, then double 256 times: R^2 mod p. */
  175. for (i = 0; i < 8; i++)
  176. t[i] = 0;
  177. raw_sub(x, t, P); /* 2^256 - p (wraps) */
  178. for (i = 0; i < 256; i++)
  179. fe_add(x, x, x);
  180. fe_copy(R2, x);
  181. {
  182. fe one = { 1, 0, 0, 0, 0, 0, 0, 0 };
  183. fe_to_mont(ONE_M, one);
  184. }
  185. ready = 1;
  186. }
  187. /* ---- points (Jacobian, a = -3) ---- */
  188. static void pt_double(struct jac *r, const struct jac *p)
  189. {
  190. fe delta, gamma, beta, alpha, t1, t2, x3, y3, z3;
  191. if (p->inf || fe_is_zero(p->y)) {
  192. r->inf = 1;
  193. return;
  194. }
  195. fe_sqr(delta, p->z);
  196. fe_sqr(gamma, p->y);
  197. fe_mul(beta, p->x, gamma);
  198. fe_sub(t1, p->x, delta);
  199. fe_add(t2, p->x, delta);
  200. fe_mul(alpha, t1, t2);
  201. fe_add(t1, alpha, alpha);
  202. fe_add(alpha, t1, alpha); /* 3 (x - d)(x + d) */
  203. fe_sqr(x3, alpha);
  204. fe_add(t1, beta, beta);
  205. fe_add(t1, t1, t1);
  206. fe_add(t2, t1, t1); /* 8 beta */
  207. fe_sub(x3, x3, t2);
  208. fe_add(t2, p->y, p->z);
  209. fe_sqr(z3, t2);
  210. fe_sub(z3, z3, gamma);
  211. fe_sub(z3, z3, delta);
  212. fe_sub(t1, t1, x3); /* 4 beta - x3 */
  213. fe_mul(y3, alpha, t1);
  214. fe_sqr(t2, gamma);
  215. fe_add(t2, t2, t2);
  216. fe_add(t2, t2, t2);
  217. fe_add(t2, t2, t2); /* 8 gamma^2 */
  218. fe_sub(y3, y3, t2);
  219. fe_copy(r->x, x3);
  220. fe_copy(r->y, y3);
  221. fe_copy(r->z, z3);
  222. r->inf = 0;
  223. }
  224. static void pt_add(struct jac *r, const struct jac *a, const struct jac *b)
  225. {
  226. fe z1z1, z2z2, u1, u2, s1, s2, h, rr, i, j, v, t, x3, y3, z3;
  227. if (a->inf) {
  228. *r = *b;
  229. return;
  230. }
  231. if (b->inf) {
  232. *r = *a;
  233. return;
  234. }
  235. fe_sqr(z1z1, a->z);
  236. fe_sqr(z2z2, b->z);
  237. fe_mul(u1, a->x, z2z2);
  238. fe_mul(u2, b->x, z1z1);
  239. fe_mul(t, b->z, z2z2);
  240. fe_mul(s1, a->y, t);
  241. fe_mul(t, a->z, z1z1);
  242. fe_mul(s2, b->y, t);
  243. fe_sub(h, u2, u1);
  244. fe_sub(rr, s2, s1);
  245. if (fe_is_zero(h)) {
  246. if (fe_is_zero(rr)) {
  247. pt_double(r, a);
  248. return;
  249. }
  250. r->inf = 1;
  251. return;
  252. }
  253. fe_add(rr, rr, rr);
  254. fe_add(t, h, h);
  255. fe_sqr(i, t);
  256. fe_mul(j, h, i);
  257. fe_mul(v, u1, i);
  258. fe_sqr(x3, rr);
  259. fe_sub(x3, x3, j);
  260. fe_sub(x3, x3, v);
  261. fe_sub(x3, x3, v);
  262. fe_sub(t, v, x3);
  263. fe_mul(y3, rr, t);
  264. fe_mul(t, s1, j);
  265. fe_add(t, t, t);
  266. fe_sub(y3, y3, t);
  267. fe_add(t, a->z, b->z);
  268. fe_sqr(z3, t);
  269. fe_sub(z3, z3, z1z1);
  270. fe_sub(z3, z3, z2z2);
  271. fe_mul(z3, z3, h);
  272. fe_copy(r->x, x3);
  273. fe_copy(r->y, y3);
  274. fe_copy(r->z, z3);
  275. r->inf = 0;
  276. }
  277. static void pt_mul(struct jac *r, const unsigned char k[32],
  278. const struct jac *p)
  279. {
  280. struct jac acc;
  281. int i, bit;
  282. acc.inf = 1;
  283. for (i = 0; i < 256; i++) {
  284. bit = (k[i >> 3] >> (7 - (i & 7))) & 1; /* big-endian bits */
  285. pt_double(&acc, &acc);
  286. if (bit)
  287. pt_add(&acc, &acc, p);
  288. }
  289. *r = acc;
  290. }
  291. /* Affine coordinates in normal form. */
  292. static int pt_affine(const struct jac *p, fe x, fe y)
  293. {
  294. fe zi, zi2, t;
  295. if (p->inf)
  296. return -1;
  297. fe_inv(zi, p->z);
  298. fe_sqr(zi2, zi);
  299. fe_mul(t, p->x, zi2);
  300. fe_from_mont(x, t);
  301. fe_mul(zi2, zi2, zi);
  302. fe_mul(t, p->y, zi2);
  303. fe_from_mont(y, t);
  304. return 0;
  305. }
  306. static void fe_from_bytes(fe r, const unsigned char *b)
  307. {
  308. int i;
  309. for (i = 0; i < 8; i++)
  310. r[i] = ((unsigned int)b[28 - 4 * i] << 24) |
  311. ((unsigned int)b[29 - 4 * i] << 16) |
  312. ((unsigned int)b[30 - 4 * i] << 8) | b[31 - 4 * i];
  313. }
  314. static void fe_to_bytes(unsigned char *b, const fe a)
  315. {
  316. int i;
  317. for (i = 0; i < 8; i++) {
  318. b[28 - 4 * i] = (unsigned char)(a[i] >> 24);
  319. b[29 - 4 * i] = (unsigned char)(a[i] >> 16);
  320. b[30 - 4 * i] = (unsigned char)(a[i] >> 8);
  321. b[31 - 4 * i] = (unsigned char)a[i];
  322. }
  323. }
  324. static int scalar_zero(const unsigned char k[32])
  325. {
  326. unsigned int d = 0, i;
  327. for (i = 0; i < 32; i++)
  328. d |= k[i];
  329. return d == 0;
  330. }
  331. static void base_point(struct jac *g)
  332. {
  333. fe_to_mont(g->x, GX);
  334. fe_to_mont(g->y, GY);
  335. fe_copy(g->z, ONE_M);
  336. g->inf = 0;
  337. }
  338. int p256_public(const unsigned char priv[32], unsigned char pub[65])
  339. {
  340. struct jac g, q;
  341. fe x, y;
  342. p256_init();
  343. if (scalar_zero(priv))
  344. return -1;
  345. base_point(&g);
  346. pt_mul(&q, priv, &g);
  347. if (pt_affine(&q, x, y) != 0)
  348. return -1;
  349. pub[0] = 0x04;
  350. fe_to_bytes(pub + 1, x);
  351. fe_to_bytes(pub + 33, y);
  352. return 0;
  353. }
  354. int p256_shared(const unsigned char priv[32], const unsigned char *peer,
  355. unsigned int peer_len, unsigned char out[32])
  356. {
  357. struct jac p, q;
  358. fe x, y, xm, ym, lhs, rhs, t, three, bm;
  359. p256_init();
  360. if (peer_len != 65 || peer[0] != 0x04 || scalar_zero(priv))
  361. return -1;
  362. fe_from_bytes(x, peer + 1);
  363. fe_from_bytes(y, peer + 33);
  364. if (!fe_lt_p(x) || !fe_lt_p(y))
  365. return -1;
  366. /* On the curve: y^2 = x^3 - 3x + b. */
  367. fe_to_mont(xm, x);
  368. fe_to_mont(ym, y);
  369. fe_sqr(lhs, ym);
  370. fe_sqr(t, xm);
  371. fe_mul(rhs, t, xm);
  372. fe_add(three, xm, xm);
  373. fe_add(three, three, xm);
  374. fe_sub(rhs, rhs, three);
  375. fe_to_mont(bm, B);
  376. fe_add(rhs, rhs, bm);
  377. if (!fe_eq(lhs, rhs))
  378. return -1;
  379. fe_copy(p.x, xm);
  380. fe_copy(p.y, ym);
  381. fe_copy(p.z, ONE_M);
  382. p.inf = 0;
  383. pt_mul(&q, priv, &p);
  384. if (pt_affine(&q, x, y) != 0)
  385. return -1;
  386. fe_to_bytes(out, x);
  387. return 0;
  388. }