tls_x25519.c 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321
  1. /* X25519: see tls_x25519.h.
  2. *
  3. * The field elements are kept below 2^255: adds wrap with 2^256 == 38 and
  4. * subtracts borrow-fix with the same identity, so a single conditional
  5. * subtraction of p restores the invariant. Multiplication is 8x8 u32
  6. * schoolbook with per-step carries, then the high half is folded with *38
  7. * (2^256 mod p). Slow but simple and testable against RFC 7748. */
  8. #include "tls_x25519.h"
  9. struct fe {
  10. unsigned int v[8];
  11. };
  12. const unsigned char x25519_base_point[32] = { 9 };
  13. static unsigned int fe_ld32(const unsigned char *p)
  14. {
  15. return (unsigned int)p[0] | ((unsigned int)p[1] << 8) |
  16. ((unsigned int)p[2] << 16) | ((unsigned int)p[3] << 24);
  17. }
  18. static void fe_st32(unsigned char *p, unsigned int v)
  19. {
  20. p[0] = (unsigned char)v;
  21. p[1] = (unsigned char)(v >> 8);
  22. p[2] = (unsigned char)(v >> 16);
  23. p[3] = (unsigned char)(v >> 24);
  24. }
  25. static void fe_frombytes(struct fe *r, const unsigned char b[32])
  26. {
  27. unsigned int i;
  28. for (i = 0; i < 8; i++)
  29. r->v[i] = fe_ld32(b + i * 4);
  30. r->v[7] &= 0x7fffffffu;
  31. }
  32. static void fe_tobytes(unsigned char out[32], const struct fe *a)
  33. {
  34. unsigned int i;
  35. for (i = 0; i < 8; i++)
  36. fe_st32(out + i * 4, a->v[i]);
  37. }
  38. static void fe_copy(struct fe *r, const struct fe *a)
  39. {
  40. unsigned int i;
  41. for (i = 0; i < 8; i++)
  42. r->v[i] = a->v[i];
  43. }
  44. static void fe_zero(struct fe *r)
  45. {
  46. unsigned int i;
  47. for (i = 0; i < 8; i++)
  48. r->v[i] = 0;
  49. }
  50. static void fe_one(struct fe *r)
  51. {
  52. fe_zero(r);
  53. r->v[0] = 1;
  54. }
  55. /* r -= p (2^255 - 19); the caller guarantees r >= p. */
  56. static void fe_sub_p(struct fe *r)
  57. {
  58. unsigned long long d = 0;
  59. unsigned int i;
  60. unsigned int borrow = 0;
  61. for (i = 0; i < 8; i++) {
  62. unsigned int p = (i == 7) ? 0x7fffffffu :
  63. (i == 0) ? 0xffffffedu : 0xffffffffu;
  64. d = (unsigned long long)r->v[i] - p - borrow;
  65. r->v[i] = (unsigned int)d;
  66. borrow = (unsigned int)((d >> 32) & 1);
  67. }
  68. }
  69. /* If the value is >= 2^255, subtract p once (result < 2^255). */
  70. static void fe_reduce1(struct fe *r)
  71. {
  72. if (r->v[7] >> 31)
  73. fe_sub_p(r);
  74. }
  75. static void fe_add(struct fe *r, const struct fe *a, const struct fe *b)
  76. {
  77. unsigned long long carry = 0;
  78. unsigned int i;
  79. for (i = 0; i < 8; i++) {
  80. carry += (unsigned long long)a->v[i] + b->v[i];
  81. r->v[i] = (unsigned int)carry;
  82. carry >>= 32;
  83. }
  84. while (carry) {
  85. carry = (unsigned long long)r->v[0] + carry * 38;
  86. r->v[0] = (unsigned int)carry;
  87. carry >>= 32;
  88. for (i = 1; i < 8 && carry; i++) {
  89. carry += r->v[i];
  90. r->v[i] = (unsigned int)carry;
  91. carry >>= 32;
  92. }
  93. }
  94. fe_reduce1(r);
  95. }
  96. static void fe_sub(struct fe *r, const struct fe *a, const struct fe *b)
  97. {
  98. unsigned long long d = 0;
  99. unsigned int i;
  100. unsigned int borrow = 0;
  101. for (i = 0; i < 8; i++) {
  102. d = (unsigned long long)a->v[i] - b->v[i] - borrow;
  103. r->v[i] = (unsigned int)d;
  104. borrow = (unsigned int)((d >> 32) & 1);
  105. }
  106. if (borrow) {
  107. /* a - b + 2^256 == a - b + 38 (mod p): subtract the 38. */
  108. d = (unsigned long long)r->v[0] - 38;
  109. r->v[0] = (unsigned int)d;
  110. borrow = (unsigned int)((d >> 32) & 1);
  111. for (i = 1; i < 8 && borrow; i++) {
  112. d = (unsigned long long)r->v[i] - borrow;
  113. r->v[i] = (unsigned int)d;
  114. borrow = (unsigned int)((d >> 32) & 1);
  115. }
  116. }
  117. fe_reduce1(r);
  118. }
  119. static void fe_mul(struct fe *r, const struct fe *a, const struct fe *b)
  120. {
  121. unsigned int t[16];
  122. unsigned long long u[8];
  123. unsigned long long carry;
  124. unsigned int i, j;
  125. for (i = 0; i < 16; i++)
  126. t[i] = 0;
  127. for (i = 0; i < 8; i++) {
  128. carry = 0;
  129. for (j = 0; j < 8; j++) {
  130. carry += (unsigned long long)a->v[i] * b->v[j] +
  131. t[i + j];
  132. t[i + j] = (unsigned int)carry;
  133. carry >>= 32;
  134. }
  135. t[i + 8] = (unsigned int)carry;
  136. }
  137. /* Fold the limbs above 2^256: 2^256 == 38 (mod p). */
  138. for (j = 0; j < 8; j++)
  139. u[j] = (unsigned long long)t[j] + 38ull * t[j + 8];
  140. carry = 0;
  141. for (j = 0; j < 8; j++) {
  142. carry += u[j];
  143. r->v[j] = (unsigned int)carry;
  144. carry >>= 32;
  145. }
  146. while (carry) {
  147. carry = (unsigned long long)r->v[0] + carry * 38;
  148. r->v[0] = (unsigned int)carry;
  149. carry >>= 32;
  150. for (j = 1; j < 8 && carry; j++) {
  151. carry += r->v[j];
  152. r->v[j] = (unsigned int)carry;
  153. carry >>= 32;
  154. }
  155. }
  156. fe_reduce1(r);
  157. }
  158. static void fe_sq(struct fe *r, const struct fe *a)
  159. {
  160. fe_mul(r, a, a);
  161. }
  162. static void fe_mul_small(struct fe *r, const struct fe *a, unsigned int k)
  163. {
  164. unsigned long long carry = 0;
  165. unsigned int i;
  166. for (i = 0; i < 8; i++) {
  167. carry += (unsigned long long)a->v[i] * k;
  168. r->v[i] = (unsigned int)carry;
  169. carry >>= 32;
  170. }
  171. while (carry) {
  172. carry = (unsigned long long)r->v[0] + carry * 38;
  173. r->v[0] = (unsigned int)carry;
  174. carry >>= 32;
  175. for (i = 1; i < 8 && carry; i++) {
  176. carry += r->v[i];
  177. r->v[i] = (unsigned int)carry;
  178. carry >>= 32;
  179. }
  180. }
  181. fe_reduce1(r);
  182. }
  183. /* r = a^-1 = a^(p-2); generic square-and-multiply over 2^255 - 21. */
  184. static void fe_invert(struct fe *r, const struct fe *a)
  185. {
  186. static const unsigned int exp[8] = {
  187. 0xffffffebu, 0xffffffffu, 0xffffffffu, 0xffffffffu,
  188. 0xffffffffu, 0xffffffffu, 0xffffffffu, 0x7fffffffu
  189. };
  190. struct fe base, acc;
  191. int i;
  192. fe_copy(&base, a);
  193. fe_one(&acc);
  194. for (i = 254; i >= 0; i--) {
  195. fe_sq(&acc, &acc);
  196. if ((exp[i >> 5] >> (i & 31)) & 1)
  197. fe_mul(&acc, &acc, &base);
  198. }
  199. fe_copy(r, &acc);
  200. }
  201. static void fe_cswap(struct fe *a, struct fe *b, unsigned int swap)
  202. {
  203. unsigned int mask = 0u - swap;
  204. unsigned int i;
  205. for (i = 0; i < 8; i++) {
  206. unsigned int t = mask & (a->v[i] ^ b->v[i]);
  207. a->v[i] ^= t;
  208. b->v[i] ^= t;
  209. }
  210. }
  211. /* Canonicalize: one conditional subtraction of p (input < 2^255). */
  212. static void fe_canon(struct fe *r)
  213. {
  214. struct fe t;
  215. unsigned int i;
  216. unsigned int borrow = 0;
  217. for (i = 0; i < 8; i++) {
  218. unsigned int p = (i == 7) ? 0x7fffffffu :
  219. (i == 0) ? 0xffffffedu : 0xffffffffu;
  220. unsigned long long d = (unsigned long long)r->v[i] - p - borrow;
  221. t.v[i] = (unsigned int)d;
  222. borrow = (unsigned int)((d >> 32) & 1);
  223. }
  224. if (!borrow)
  225. fe_copy(r, &t);
  226. }
  227. void x25519(unsigned char out[32], const unsigned char scalar[32],
  228. const unsigned char point[32])
  229. {
  230. unsigned char k[32];
  231. struct fe x1, x2, z2, x3, z3;
  232. struct fe A, AA, B, BB, E, C, D, DA, CB, t0, t1;
  233. int i;
  234. unsigned int swap = 0;
  235. for (i = 0; i < 32; i++)
  236. k[i] = scalar[i];
  237. k[0] &= 248;
  238. k[31] &= 127;
  239. k[31] |= 64;
  240. fe_frombytes(&x1, point);
  241. fe_one(&x2);
  242. fe_zero(&z2);
  243. fe_copy(&x3, &x1);
  244. fe_one(&z3);
  245. for (i = 254; i >= 0; i--) {
  246. unsigned int kt = (k[(unsigned int)i >> 3] >>
  247. ((unsigned int)i & 7)) & 1;
  248. swap ^= kt;
  249. fe_cswap(&x2, &x3, swap);
  250. fe_cswap(&z2, &z3, swap);
  251. swap = kt;
  252. fe_add(&A, &x2, &z2);
  253. fe_sq(&AA, &A);
  254. fe_sub(&B, &x2, &z2);
  255. fe_sq(&BB, &B);
  256. fe_sub(&E, &AA, &BB);
  257. fe_add(&C, &x3, &z3);
  258. fe_sub(&D, &x3, &z3);
  259. fe_mul(&DA, &D, &A);
  260. fe_mul(&CB, &C, &B);
  261. fe_add(&t0, &DA, &CB);
  262. fe_sq(&x3, &t0);
  263. fe_sub(&t1, &DA, &CB);
  264. fe_sq(&t1, &t1);
  265. fe_mul(&z3, &x1, &t1);
  266. fe_mul(&x2, &AA, &BB);
  267. fe_mul_small(&t0, &E, 121665);
  268. fe_add(&t0, &AA, &t0);
  269. fe_mul(&z2, &E, &t0);
  270. }
  271. fe_cswap(&x2, &x3, swap);
  272. fe_cswap(&z2, &z3, swap);
  273. fe_invert(&z2, &z2);
  274. fe_mul(&x2, &x2, &z2);
  275. fe_canon(&x2);
  276. fe_tobytes(out, &x2);
  277. }