tweetnacl-gnunet.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560
  1. /*
  2. This file has been placed in the public domain.
  3. Based on TweetNaCl version 20140427
  4. Originally obtained from:
  5. https://tweetnacl.cr.yp.to/20140427/tweetnacl.h
  6. SPDX-License-Identifier: 0BSD
  7. */
  8. #include "platform.h"
  9. #include "gnunet_crypto_lib.h"
  10. #include "tweetnacl-gnunet.h"
  11. #define FOR(i,n) for (i = 0; i < n; ++i)
  12. typedef uint8_t u8;
  13. typedef uint32_t u32;
  14. typedef uint64_t u64;
  15. typedef int64_t i64;
  16. typedef i64 gf[16];
  17. static const u8 _9[32] = {9};
  18. static const gf
  19. gf0,
  20. gf1 = {1},
  21. _121665 = {0xDB41,1},
  22. D = {0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, 0xe898,
  23. 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203},
  24. D2 = {0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, 0xd130,
  25. 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406},
  26. X = {0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, 0xdc5c,
  27. 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169},
  28. Y = {0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666,
  29. 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666},
  30. I = {0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, 0xd7a7,
  31. 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83};
  32. static int
  33. vn (const u8 *x,const u8 *y,int n)
  34. {
  35. u32 i,d = 0;
  36. FOR (i,n) d |= x[i] ^ y[i];
  37. return (1 & ((d - 1) >> 8)) - 1;
  38. }
  39. static int
  40. crypto_verify_32 (const u8 *x,const u8 *y)
  41. {
  42. return vn (x,y,32);
  43. }
  44. static void
  45. set25519 (gf r, const gf a)
  46. {
  47. int i;
  48. FOR (i,16) r[i] = a[i];
  49. }
  50. static void
  51. car25519 (gf o)
  52. {
  53. int i;
  54. i64 c;
  55. FOR (i,16) {
  56. o[i] += (1LL << 16);
  57. c = o[i] >> 16;
  58. o[(i + 1) * (i<15)] += c - 1 + 37 * (c - 1) * (i==15);
  59. o[i] -= c << 16;
  60. }
  61. }
  62. static void
  63. sel25519 (gf p,gf q,int b)
  64. {
  65. i64 t,i,c = ~(b - 1);
  66. FOR (i,16) {
  67. t = c & (p[i] ^ q[i]);
  68. p[i] ^= t;
  69. q[i] ^= t;
  70. }
  71. }
  72. static void
  73. pack25519 (u8 *o,const gf n)
  74. {
  75. int i,j,b;
  76. gf m,t;
  77. FOR (i,16) t[i] = n[i];
  78. car25519 (t);
  79. car25519 (t);
  80. car25519 (t);
  81. FOR (j,2) {
  82. m[0] = t[0] - 0xffed;
  83. for (i = 1; i<15; i++) {
  84. m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1);
  85. m[i - 1] &= 0xffff;
  86. }
  87. m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1);
  88. b = (m[15] >> 16) & 1;
  89. m[14] &= 0xffff;
  90. sel25519 (t,m,1 - b);
  91. }
  92. FOR (i,16) {
  93. o[2 * i] = t[i] & 0xff;
  94. o[2 * i + 1] = t[i] >> 8;
  95. }
  96. }
  97. static int
  98. neq25519 (const gf a, const gf b)
  99. {
  100. u8 c[32],d[32];
  101. pack25519 (c,a);
  102. pack25519 (d,b);
  103. return crypto_verify_32 (c,d);
  104. }
  105. static uint8_t
  106. par25519 (const gf a)
  107. {
  108. u8 d[32];
  109. pack25519 (d,a);
  110. return d[0] & 1;
  111. }
  112. static void
  113. unpack25519 (gf o, const u8 *n)
  114. {
  115. int i;
  116. FOR (i,16) o[i] = n[2 * i] + ((i64) n[2 * i + 1] << 8);
  117. o[15] &= 0x7fff;
  118. }
  119. static void
  120. A (gf o,const gf a,const gf b)
  121. {
  122. int i;
  123. FOR (i,16) o[i] = a[i] + b[i];
  124. }
  125. static void
  126. Z (gf o,const gf a,const gf b)
  127. {
  128. int i;
  129. FOR (i,16) o[i] = a[i] - b[i];
  130. }
  131. static void
  132. M (gf o,const gf a,const gf b)
  133. {
  134. i64 i,j,t[31];
  135. FOR (i,31) t[i] = 0;
  136. FOR (i,16) FOR (j,16) t[i + j] += a[i] * b[j];
  137. FOR (i,15) t[i] += 38 * t[i + 16];
  138. FOR (i,16) o[i] = t[i];
  139. car25519 (o);
  140. car25519 (o);
  141. }
  142. static void
  143. S (gf o,const gf a)
  144. {
  145. M (o,a,a);
  146. }
  147. static void
  148. inv25519 (gf o,const gf i)
  149. {
  150. gf c;
  151. int a;
  152. FOR (a,16) c[a] = i[a];
  153. for (a = 253; a>=0; a--) {
  154. S (c,c);
  155. if ((a!=2)&&(a!=4))
  156. M (c,c,i);
  157. }
  158. FOR (a,16) o[a] = c[a];
  159. }
  160. static void pow2523 (gf o,const gf i)
  161. {
  162. gf c;
  163. int a;
  164. FOR (a,16) c[a] = i[a];
  165. for (a = 250; a>=0; a--) {
  166. S (c,c);
  167. if (a!=1)
  168. M (c,c,i);
  169. }
  170. FOR (a,16) o[a] = c[a];
  171. }
  172. int
  173. GNUNET_TWEETNACL_scalarmult_curve25519 (u8 *q,const u8 *n,const u8 *p)
  174. {
  175. u8 z[32];
  176. i64 x[80],r,i;
  177. gf a,b,c,d,e,f;
  178. FOR (i,31) z[i] = n[i];
  179. z[31] = (n[31] & 127) | 64;
  180. z[0] &= 248;
  181. unpack25519 (x,p);
  182. FOR (i,16) {
  183. b[i] = x[i];
  184. d[i] = a[i] = c[i] = 0;
  185. }
  186. a[0] = d[0] = 1;
  187. for (i = 254; i>=0; --i) {
  188. r = (z[i >> 3] >> (i & 7)) & 1;
  189. sel25519 (a,b,r);
  190. sel25519 (c,d,r);
  191. A (e,a,c);
  192. Z (a,a,c);
  193. A (c,b,d);
  194. Z (b,b,d);
  195. S (d,e);
  196. S (f,a);
  197. M (a,c,a);
  198. M (c,b,e);
  199. A (e,a,c);
  200. Z (a,a,c);
  201. S (b,a);
  202. Z (c,d,f);
  203. M (a,c,_121665);
  204. A (a,a,d);
  205. M (c,c,a);
  206. M (a,d,f);
  207. M (d,b,x);
  208. S (b,e);
  209. sel25519 (a,b,r);
  210. sel25519 (c,d,r);
  211. }
  212. FOR (i,16) {
  213. x[i + 16] = a[i];
  214. x[i + 32] = c[i];
  215. x[i + 48] = b[i];
  216. x[i + 64] = d[i];
  217. }
  218. inv25519 (x + 32,x + 32);
  219. M (x + 16,x + 16,x + 32);
  220. pack25519 (q,x + 16);
  221. return 0;
  222. }
  223. int
  224. GNUNET_TWEETNACL_scalarmult_curve25519_base (u8 *q,const u8 *n)
  225. {
  226. return GNUNET_TWEETNACL_scalarmult_curve25519 (q,n,_9);
  227. }
  228. static int
  229. crypto_hash (u8 *out,const u8 *m,u64 n)
  230. {
  231. struct GNUNET_HashCode *hc = (void *) out;
  232. GNUNET_CRYPTO_hash (m, n, hc);
  233. return 0;
  234. }
  235. static void
  236. add (gf p[4],gf q[4])
  237. {
  238. gf a,b,c,d,t,e,f,g,h;
  239. Z (a, p[1], p[0]);
  240. Z (t, q[1], q[0]);
  241. M (a, a, t);
  242. A (b, p[0], p[1]);
  243. A (t, q[0], q[1]);
  244. M (b, b, t);
  245. M (c, p[3], q[3]);
  246. M (c, c, D2);
  247. M (d, p[2], q[2]);
  248. A (d, d, d);
  249. Z (e, b, a);
  250. Z (f, d, c);
  251. A (g, d, c);
  252. A (h, b, a);
  253. M (p[0], e, f);
  254. M (p[1], h, g);
  255. M (p[2], g, f);
  256. M (p[3], e, h);
  257. }
  258. static void
  259. cswap (gf p[4],gf q[4],u8 b)
  260. {
  261. int i;
  262. FOR (i,4)
  263. sel25519 (p[i],q[i],b);
  264. }
  265. static void
  266. pack (u8 *r,gf p[4])
  267. {
  268. gf tx, ty, zi;
  269. inv25519 (zi, p[2]);
  270. M (tx, p[0], zi);
  271. M (ty, p[1], zi);
  272. pack25519 (r, ty);
  273. r[31] ^= par25519 (tx) << 7;
  274. }
  275. static void
  276. scalarmult (gf p[4],gf q[4],const u8 *s)
  277. {
  278. int i;
  279. set25519 (p[0],gf0);
  280. set25519 (p[1],gf1);
  281. set25519 (p[2],gf1);
  282. set25519 (p[3],gf0);
  283. for (i = 255; i >= 0; --i) {
  284. u8 b = (s[i / 8] >> (i & 7)) & 1;
  285. cswap (p,q,b);
  286. add (q,p);
  287. add (p,p);
  288. cswap (p,q,b);
  289. }
  290. }
  291. static void
  292. scalarbase (gf p[4],const u8 *s)
  293. {
  294. gf q[4];
  295. set25519 (q[0],X);
  296. set25519 (q[1],Y);
  297. set25519 (q[2],gf1);
  298. M (q[3],X,Y);
  299. scalarmult (p,q,s);
  300. }
  301. static const u64 L[32] = {0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6,
  302. 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0, 0, 0, 0,
  303. 0, 0, 0, 0, 0, 0, 0, 0,
  304. 0, 0, 0, 0x10};
  305. static void
  306. modL (u8 *r,i64 x[64])
  307. {
  308. i64 carry,i,j;
  309. for (i = 63; i >= 32; --i) {
  310. carry = 0;
  311. for (j = i - 32; j < i - 12; ++j) {
  312. x[j] += carry - 16 * x[i] * L[j - (i - 32)];
  313. carry = (x[j] + 128) >> 8;
  314. x[j] -= carry << 8;
  315. }
  316. x[j] += carry;
  317. x[i] = 0;
  318. }
  319. carry = 0;
  320. FOR (j,32) {
  321. x[j] += carry - (x[31] >> 4) * L[j];
  322. carry = x[j] >> 8;
  323. x[j] &= 255;
  324. }
  325. FOR (j,32) x[j] -= carry * L[j];
  326. FOR (i,32) {
  327. x[i + 1] += x[i] >> 8;
  328. r[i] = x[i] & 255;
  329. }
  330. }
  331. static void
  332. reduce (u8 *r)
  333. {
  334. i64 x[64],i;
  335. FOR (i,64) x[i] = (u64) r[i];
  336. FOR (i,64) r[i] = 0;
  337. modL (r,x);
  338. }
  339. static int
  340. unpackneg (gf r[4],const u8 p[32])
  341. {
  342. gf t, chk, num, den, den2, den4, den6;
  343. set25519 (r[2],gf1);
  344. unpack25519 (r[1],p);
  345. S (num,r[1]);
  346. M (den,num,D);
  347. Z (num,num,r[2]);
  348. A (den,r[2],den);
  349. S (den2,den);
  350. S (den4,den2);
  351. M (den6,den4,den2);
  352. M (t,den6,num);
  353. M (t,t,den);
  354. pow2523 (t,t);
  355. M (t,t,num);
  356. M (t,t,den);
  357. M (t,t,den);
  358. M (r[0],t,den);
  359. S (chk,r[0]);
  360. M (chk,chk,den);
  361. if (neq25519 (chk, num))
  362. M (r[0],r[0],I);
  363. S (chk,r[0]);
  364. M (chk,chk,den);
  365. if (neq25519 (chk, num))
  366. return -1;
  367. if (par25519 (r[0]) == (p[31] >> 7))
  368. Z (r[0],gf0,r[0]);
  369. M (r[3],r[0],r[1]);
  370. return 0;
  371. }
  372. /* The following functions have been added for GNUnet */
  373. void
  374. GNUNET_TWEETNACL_sign_pk_from_seed (u8 *pk, const u8 *seed)
  375. {
  376. u8 d[64];
  377. gf p[4];
  378. crypto_hash (d, seed, 32);
  379. d[0] &= 248;
  380. d[31] &= 127;
  381. d[31] |= 64;
  382. scalarbase (p, d);
  383. pack (pk, p);
  384. }
  385. void
  386. GNUNET_TWEETNACL_scalarmult_gnunet_ecdsa (u8 *pk, const u8 *s)
  387. {
  388. u8 d[64];
  389. gf p[4];
  390. // Treat s as little endian.
  391. for (u32 i = 0; i < 32; i++)
  392. d[i] = s[31 - i];
  393. // For GNUnet, we don't normalize d
  394. scalarbase (p, d);
  395. pack (pk, p);
  396. }
  397. void
  398. GNUNET_TWEETNACL_sign_sk_from_seed (u8 *sk, const u8 *seed)
  399. {
  400. u8 d[64];
  401. gf p[4];
  402. u8 pk[32];
  403. int i;
  404. crypto_hash (d, seed, 32);
  405. d[0] &= 248;
  406. d[31] &= 127;
  407. d[31] |= 64;
  408. scalarbase (p,d);
  409. pack (pk,p);
  410. FOR (i,32) sk[i] = seed[i];
  411. FOR (i,32) sk[32 + i] = pk[i];
  412. }
  413. int
  414. GNUNET_TWEETNACL_sign_ed25519_pk_to_curve25519 (u8 *x25519_pk,
  415. const u8 *ed25519_pk)
  416. {
  417. gf ge_a[4];
  418. gf x;
  419. gf one_minus_y;
  420. if (0 != unpackneg (ge_a, ed25519_pk))
  421. return -1;
  422. set25519 (one_minus_y, gf1);
  423. Z (one_minus_y, one_minus_y, ge_a[1]);
  424. set25519 (x, gf1);
  425. A (x, x, ge_a[1]);
  426. inv25519 (one_minus_y, one_minus_y);
  427. M (x, x, one_minus_y);
  428. pack25519 (x25519_pk, x);
  429. return 0;
  430. }
  431. int GNUNET_TWEETNACL_sign_detached_verify (const u8 *sig,
  432. const u8 *m,
  433. u64 n,
  434. const u8 *pk)
  435. {
  436. struct GNUNET_HashContext *hc;
  437. u8 t[32],h[64];
  438. gf p[4],q[4];
  439. if (unpackneg (q,pk))
  440. return -1;
  441. hc = GNUNET_CRYPTO_hash_context_start ();
  442. GNUNET_CRYPTO_hash_context_read (hc, sig, 32);
  443. GNUNET_CRYPTO_hash_context_read (hc, pk, 32);
  444. GNUNET_CRYPTO_hash_context_read (hc, m, n);
  445. GNUNET_CRYPTO_hash_context_finish (hc, (void *) h);
  446. reduce (h);
  447. scalarmult (p,q,h);
  448. scalarbase (q,sig+32);
  449. add (p,q);
  450. pack (t,p);
  451. if (crypto_verify_32 (sig, t))
  452. return -1;
  453. return 0;
  454. }
  455. int
  456. GNUNET_TWEETNACL_sign_detached (u8 *sig,
  457. const u8 *m,
  458. u64 n,
  459. const u8 *sk)
  460. {
  461. struct GNUNET_HashContext *hc;
  462. u8 d[64],h[64],r[64];
  463. i64 i,j,x[64];
  464. gf p[4];
  465. crypto_hash (d, sk, 32);
  466. d[0] &= 248;
  467. d[31] &= 127;
  468. d[31] |= 64;
  469. hc = GNUNET_CRYPTO_hash_context_start ();
  470. GNUNET_CRYPTO_hash_context_read (hc, d + 32, 32);
  471. GNUNET_CRYPTO_hash_context_read (hc, m, n);
  472. GNUNET_CRYPTO_hash_context_finish (hc, (void *) r);
  473. reduce (r);
  474. scalarbase (p,r);
  475. pack (sig,p);
  476. hc = GNUNET_CRYPTO_hash_context_start ();
  477. GNUNET_CRYPTO_hash_context_read (hc, sig, 32);
  478. GNUNET_CRYPTO_hash_context_read (hc, sk + 32, 32);
  479. GNUNET_CRYPTO_hash_context_read (hc, m, n);
  480. GNUNET_CRYPTO_hash_context_finish (hc, (void *) h);
  481. reduce (h);
  482. FOR (i,64) x[i] = 0;
  483. FOR (i,32) x[i] = (u64) r[i];
  484. FOR (i,32) FOR (j,32) x[i + j] += h[i] * (u64) d[j];
  485. modL (sig + 32,x);
  486. return 0;
  487. }