PaillierAdapter.cpp 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630
  1. /* Copyright (C) 2014 Carlos Aguilar Melchor, Joris Barrier, Marc-Olivier Killijian
  2. * This file is part of XPIR.
  3. *
  4. * XPIR is free software: you can redistribute it and/or modify
  5. * it under the terms of the GNU General Public License as published by
  6. * the Free Software Foundation, either version 3 of the License, or
  7. * (at your option) any later version.
  8. *
  9. * XPIR is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with XPIR. If not, see <http://www.gnu.org/licenses/>.
  16. */
  17. #include "PaillierAdapter.hpp"
  18. #include <set>
  19. #include <iostream>
  20. namespace {
  21. const int kMagicConstant1 = 1;
  22. const int kMillion = 1000000;
  23. }
  24. /**
  25. * Static fonction to feet approximately standards. NIST SP800-57 table 2 page 64
  26. * Beyond 128 bits of security modules will not be used as getCryptoParams blocks when ciphertext modulus is above 10K bits.
  27. **/
  28. unsigned int PaillierAdapter::securityToModulus(int security_bits)
  29. {
  30. if(security_bits <= 40)
  31. return 128;
  32. if (security_bits <= 80)
  33. return 1024;
  34. if (security_bits <= 112)
  35. return 2048;
  36. if (security_bits <= 128)
  37. return 3072;
  38. if (security_bits <= 192)
  39. return 7680;
  40. // Unimplemented
  41. //return 15360;
  42. return 0;
  43. }
  44. PaillierAdapter::PaillierAdapter() :
  45. HomomorphicCrypto("Paillier")
  46. {
  47. initRandomGenerator();
  48. }
  49. /**
  50. * PaillierAdapter constructor
  51. * Params:
  52. * - int security_bits : number of security bit wanted (size of the cipher space);
  53. * - int recLvl : number of recursion level.
  54. **/
  55. PaillierAdapter::PaillierAdapter(int _security_bits, int init_s ) :
  56. HomomorphicCrypto("Paillier"),
  57. security_bits(_security_bits),
  58. privateParameters(),
  59. modulusbits(securityToModulus(_security_bits)),
  60. publicParameters()
  61. {
  62. initRandomGenerator();
  63. publicParameters.setModulusbits(modulusbits);
  64. keygen(
  65. modulusbits,
  66. publicParameters.getPubKey(),
  67. privateParameters.getPrvKey(),
  68. init_s );
  69. }
  70. void PaillierAdapter::initRandomGenerator()
  71. {
  72. mpz_t s;
  73. mpz_init(s);
  74. gmp_randinit_default(rand);
  75. // Get a 1024 bit seed from /dev/urandom
  76. getRandFromfile( 128 , &s);
  77. gmp_randseed(rand, s);
  78. mpz_clear(s);
  79. }
  80. /**
  81. * Encrypt an unsigned int and return the encrypted bytes in char*
  82. * Params :
  83. * - unsigned int ui : the value to encrypt ;
  84. * - unsigned int s : the exponent (recursion lvl).
  85. *
  86. * Return :
  87. * - char* : an allocated pointer to the encrypted data.
  88. **/
  89. char*
  90. PaillierAdapter::encrypt(unsigned int ui, unsigned int s)
  91. {
  92. unsigned int ciph_size = publicParameters.getKeyBitsize()*(s+1)/8;
  93. char *tmp, *request = (char*) calloc((ciph_size + 1), sizeof(char));
  94. size_t n;
  95. mpz_t pt, ct;
  96. mpz_init(ct);
  97. mpz_init_set_ui( pt, ui); // convert the 0 or the 1 to an mpz_t
  98. enc( this->publicParameters.getPubKey(), pt, s, ct );
  99. #ifdef CRYPTO_DEBUG
  100. gmp_printf("Created query element: %Zd with args %Zd and %d\n",ct, pt, s);
  101. #endif
  102. tmp = (char*)mpz_export(NULL, &n, 1, sizeof(char), 0, 0, ct);
  103. //Padding
  104. memcpy(request+sizeof(char)*((ciph_size) - n), tmp, n);
  105. //Free memory
  106. mpz_clears(ct, pt, NULL);
  107. free(tmp);
  108. return request;
  109. }
  110. // To test decryption performance
  111. char* PaillierAdapter::encrypt_perftest()
  112. {
  113. return encrypt(1,1);// Decryption performance test work well with this small plaintext
  114. }
  115. /**
  116. * Encrypt an char* of size dataSize and return char*
  117. * Params :
  118. * - char* data : data to encrypt ;
  119. * - size_t dataSize : size of the data ;
  120. * - unsigned exponent : the exponent (recursion lvl).
  121. * Return :
  122. * - char* : an allocated pointer to the encrypted data.
  123. **/
  124. char* PaillierAdapter::encrypt(char* data, size_t dataSize, unsigned int exponent)
  125. {
  126. char* request;
  127. mpz_t ct, imported_data;
  128. mpz_inits(ct, imported_data, NULL);
  129. mpz_import(imported_data, dataSize, 1, sizeof(char), 0, 0, data);
  130. enc( this->publicParameters.getPubKey(),
  131. imported_data,
  132. exponent,
  133. ct );
  134. request = (char*)mpz_export(NULL, NULL, 1, sizeof(char) , 0, 0, ct);
  135. mpz_clears(ct, imported_data, NULL);
  136. return request;
  137. }
  138. /**
  139. * Decrypt reply sended by the server and return clear bytes in char*.
  140. * Params :
  141. * - char* cipheredData : encrypted data ;
  142. * - unsigned int exp_fac : the exponent (recursion lvl) ;
  143. * - size_t ciph_size : size of encrypted data ;
  144. * - size_t clear_size : size of decrypted data to return.
  145. * Return :
  146. * - char* : an allocated pointer to the decrypted data.
  147. **/
  148. char* PaillierAdapter::decrypt( char* cipheredData,
  149. unsigned int exp_fac,
  150. size_t ciph_size ,
  151. size_t clear_size)
  152. {
  153. size_t n = 0;
  154. mpz_t ct, res;
  155. char* tmp;
  156. mpz_inits(ct, res, NULL);
  157. mpz_import(ct, ciph_size, 1, sizeof(char), 0, 0, cipheredData);
  158. dec(publicParameters.getPubKey(),
  159. privateParameters.getPrvKey(),
  160. ct,
  161. exp_fac,
  162. res );
  163. #ifdef DEBUG_ENCRYPT
  164. gmp_printf("PaillierAdapter : Decrypting %Zd into %Zd\n\n", ct, res);
  165. #endif
  166. tmp = (char*) mpz_export(NULL, &n, 1, sizeof(char) , 0, 0, res);
  167. mpz_clears(res, ct, NULL); //clear content of mpz_t, t
  168. if( n < clear_size)
  169. {
  170. char *pt = (char*)calloc(clear_size+1, sizeof(char));
  171. memcpy(pt+sizeof(char)*((clear_size) - n), tmp, n);
  172. free(tmp); // malloc'd
  173. return pt;
  174. }
  175. else
  176. {
  177. return tmp;
  178. }
  179. }
  180. PaillierAdapter::~PaillierAdapter()
  181. {
  182. gmp_randclear(rand);
  183. }
  184. AbstractPublicParameters& PaillierAdapter::getPublicParameters()
  185. {
  186. return publicParameters;
  187. }
  188. /**
  189. * Private encrypt methode.
  190. * Params :
  191. * - paillier_pubkey* pub : Paillier public key pointer ;
  192. * - mpz_t m : data to encrypt ;
  193. * - unsigned int s : recursion level ;
  194. * - mpz_t c : result operande .
  195. **/
  196. void
  197. PaillierAdapter::enc( paillier_pubkey* pub,
  198. mpz_t m,
  199. unsigned int s,
  200. mpz_t c )
  201. {
  202. mpz_t gm, rns, r;
  203. mpz_inits( gm, rns, r, NULL);
  204. unsigned int modulusbits = publicParameters.getKeyBitsize();
  205. do
  206. {
  207. mpz_urandomb(r, rand, (s+1)*modulusbits);
  208. } while( mpz_cmp(r, *pub->getnj(s+1)) >= 0 );
  209. mpz_powm(gm, *pub->getg(), m, *pub->getnj(s+1));
  210. mpz_powm(rns, r, *pub->getnj(s), *pub->getnj(s+1));
  211. mpz_mul(c, gm, rns);
  212. mpz_mod(c,c, *pub->getnj(s+1));
  213. #ifdef DEBUG_ENCRYPT
  214. mpz_t test;
  215. mpz_init(test);
  216. dec(pub, privateParameters.getPrvKey(), c, s, test);
  217. gmp_printf("Decrypting %Zd into %Zd\n\n", c, test);
  218. #endif
  219. mpz_clears(gm, rns, r, NULL);
  220. }
  221. /**
  222. * Reimplemented version of decrypt to not use paillier structures.
  223. * Params:
  224. * - paillier_prvkey* prv : Paillier private key pointer ;
  225. * - mpz_t c : encrypted data ;
  226. * - unsigned int s : recursion level ;
  227. * - mpz_t i : result operande .
  228. * This function is an exact copy of the one in libdj
  229. **/
  230. /*
  231. libdj - A library implementing the Damgård-Jurik cryptosystem.
  232. Copyright 2012 Fred Douglas (fed2@illinois.edu)
  233. This library is an extension/modification of libpaillier.
  234. libpaillier is copyright 2006 SRI International (written by John Bethencourt).
  235. This file is part of libdj.
  236. libdj is free software: you can redistribute it and/or modify
  237. it under the terms of the GNU General Public License as published by
  238. the Free Software Foundation, either version 3 of the License, or
  239. (at your option) any later version.
  240. libdj is distributed in the hope that it will be useful,
  241. but WITHOUT ANY WARRANTY; without even the implied warranty of
  242. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  243. GNU General Public License for more details.
  244. You should have received a copy of the GNU General Public License
  245. along with libdj. If not, see <http://www.gnu.org/licenses/>.
  246. */
  247. void
  248. PaillierAdapter::dec( paillier_pubkey* pub,
  249. paillier_prvkey* prv,
  250. mpz_t c,
  251. unsigned int s,
  252. mpz_t res)
  253. {
  254. int i,j,k;
  255. mpz_t cprime, temp, tempDivisor, i_jCur, i_jPrev;
  256. mpz_init(cprime);
  257. //cprime = c^key mod n^{s+1}
  258. mpz_powm(cprime,c,prv->d,*pub->getnj(s+1));
  259. //the algorithm from extracting i from (1+n)^i described in the paper.
  260. //the algorithm iteratively extracts i mod n, i mod n^2, etc. i mod n starts us off, and is just input - 1 / n.
  261. mpz_init(temp);
  262. mpz_init(tempDivisor);
  263. mpz_init(i_jCur);
  264. mpz_init_set(i_jPrev,cprime);
  265. mpz_sub_ui(i_jPrev,i_jPrev,1);
  266. mpz_divexact(i_jPrev,i_jPrev,*pub->getnj(1));
  267. mpz_mod(i_jPrev,i_jPrev,*pub->getnj(2));
  268. //just in case s=1; in that case we need this line to actually set i_jcur
  269. if(s==1)
  270. mpz_set(i_jCur,i_jPrev);
  271. //extract i_j = i mod n^j given i_{j-1}. this is done by taking (input - 1 mod n^{j+1}) / n , and subtracting
  272. //from that: (( (i_{j-1} choose 2)*n + (i_{j-1} choose 3)*n^2 + ... + (i_{j-1} choose j)*n^{j-1} )) mod n^j
  273. for(j=2;j<=s;j++)
  274. {
  275. //L((1+n)^i) as they call it
  276. mpz_mod(i_jCur,cprime,*pub->getnj(j+1));
  277. mpz_sub_ui(i_jCur,i_jCur,1);
  278. mpz_divexact(i_jCur,i_jCur,*pub->getnj(1));
  279. mpz_mod(i_jCur,i_jCur,*pub->getnj(j));
  280. //subtract each of the binomial things
  281. for(k=2;k<=j;k++)
  282. {
  283. mpz_bin_ui(temp,i_jPrev,k);
  284. mpz_mul(temp,temp,*pub->getnj(k-1));
  285. mpz_mod(temp,temp,*pub->getnj(j));
  286. mpz_sub(i_jCur,i_jCur,temp);
  287. mpz_mod(i_jCur,i_jCur,*pub->getnj(j));
  288. }
  289. mpz_set(i_jPrev,i_jCur);
  290. }
  291. //i_jCur is currently the message times the private key.
  292. mpz_invert(temp, prv->d, *pub->getnj(s));
  293. mpz_mul(res, i_jCur, temp);
  294. mpz_mod(res, res, *pub->getnj(s));
  295. //cleanup and return
  296. mpz_clear(cprime);
  297. mpz_clear(i_jPrev);
  298. mpz_clear(i_jCur);
  299. mpz_clear(temp);
  300. mpz_clear(tempDivisor);
  301. // unsigned int kfac, k;
  302. // mpz_t t1, t2, t3, a, id ;
  303. // std::cout << "dec called with s="<<s<<std::endl;
  304. // mpz_inits(t1, t2, t3, a, NULL);
  305. // mpz_init_set_ui(id, 0);
  306. //
  307. // mpz_powm(a, c, prv->d, *pub->getnj(s+1));
  308. //
  309. // for(unsigned int j = 1 ; j <= s; j++)
  310. // {
  311. // mpz_set(t1, a);
  312. // mpz_mod(t1, t1, *pub->getnj(j+1));
  313. // mpz_sub_ui(t1, t1, 1);
  314. // mpz_div(t1, t1, *pub->getnj(1));
  315. // mpz_set(t2, id);
  316. // kfac = 1;
  317. //
  318. // for (k = 2; k <= j; k++)
  319. // {
  320. // kfac *= k;
  321. // mpz_sub_ui(id, id, 1);
  322. // mpz_mul(t2, t2, id);
  323. // mpz_mod(t2, t2, *pub->getnj(j));
  324. // mpz_set_ui(t3, kfac);
  325. //
  326. // mpz_invert(t3, t3, *pub->getnj(j));
  327. //
  328. // mpz_mul(t3, t3, t2);
  329. // mpz_mod(t3, t3, *pub->getnj(j));
  330. // mpz_mul(t3, t3, *pub->getnj(k-1));
  331. // mpz_mod(t3, t3, *pub->getnj(j));
  332. // mpz_sub(t1, t1, t3);
  333. // mpz_mod(t1, t1, *pub->getnj(j));
  334. // }
  335. // mpz_set(id, t1);
  336. // }
  337. //
  338. // mpz_mul(rop, id, prv->inv_d);
  339. //
  340. // mpz_mod(rop, rop, *pub->getnj(s));
  341. //
  342. // mpz_clears(t1, t2, t3, a, id, NULL);
  343. }
  344. void
  345. PaillierAdapter::keygen( unsigned int modulusbits,
  346. paillier_pubkey* pub,
  347. paillier_prvkey* prv,
  348. unsigned int init_s)
  349. {
  350. mpz_t p, q;
  351. mpz_inits(p, q, NULL);
  352. /* pick random (modulusbits/2)-bit primes p and q */
  353. do
  354. {
  355. get_prime_of_size(p, modulusbits / 2);
  356. get_prime_of_size(q, modulusbits / 2);
  357. mpz_mul(*pub->getnj(1), p, q);
  358. }while(mpz_sizeinbase(*pub->getnj(1), 2) != modulusbits);
  359. pub->setbits(modulusbits);
  360. pub->setinit_s(init_s);
  361. pub->complete_key(init_s+1); /*we don't know if it will be used beyond one level*/
  362. /* compute the private key lambda = lcm(p-1,q-1) */
  363. mpz_sub_ui(p, p, 1);
  364. mpz_sub_ui(q, q, 1);
  365. mpz_lcm(prv->d, p, q);
  366. mpz_invert(prv->inv_d, prv->d ,*pub->getnj(init_s));
  367. /* clear temporary integers */
  368. mpz_clears(p, q, NULL);
  369. }
  370. /**
  371. * Get prime number of given size.
  372. * Parms :
  373. * - mpz_t rop : result operand ;
  374. * - unsigned int length : length in bit.
  375. **/
  376. void
  377. PaillierAdapter::get_prime_of_size(mpz_t rop, unsigned int length)
  378. {
  379. mpz_t z_p, z_min;
  380. mpz_init(z_p);
  381. mpz_init_set_ui(z_min, 1);
  382. mpz_mul_2exp(z_min, z_min, length - 1);
  383. do
  384. {
  385. mpz_urandomb(z_p, rand, length);
  386. mpz_add(z_p, z_min, z_p);
  387. mpz_nextprime(z_p, z_p);
  388. }
  389. while(mpz_sizeinbase(z_p, 2) != length);
  390. mpz_set(rop, z_p);
  391. mpz_clears(z_p, z_min, NULL);
  392. }
  393. void
  394. PaillierAdapter::getRandFromfile(int len, mpz_t* val )
  395. {
  396. char* p = new char[len + 1]();
  397. std::ifstream f("/dev/urandom", ios::in | ios::binary);
  398. for(int i = 0; i < len; i++)
  399. {
  400. f.read(p+i, 1);
  401. }
  402. mpz_import(*val, len, 1, sizeof(char), 0, 0, p);
  403. f.close();
  404. delete[] p;
  405. }
  406. void
  407. PaillierAdapter::setNewParameters(const std::string& crypto_params)
  408. {
  409. std::vector<std::string> fields;
  410. boost::algorithm::split(fields, crypto_params, boost::algorithm::is_any_of(":"));
  411. unsigned int keySize = (unsigned)atoi(fields[2].c_str());
  412. security_bits = atoi(fields[1].c_str());
  413. publicParameters.setModulusbits(keySize);
  414. publicParameters.setSecurityBits(security_bits);
  415. // TODO(performance) : Takes too much time when generating the encrypt and decrypt caches
  416. // An option should be included so that it is a fixed key from a file when called to build caches
  417. keygen(
  418. keySize,
  419. publicParameters.getPubKey(),
  420. privateParameters.getPrvKey(),
  421. kMagicConstant1);
  422. }
  423. double
  424. PaillierAdapter::getDecCost(unsigned int length, unsigned int s)
  425. {
  426. double start, result;
  427. unsigned int cores = omp_get_num_procs();
  428. unsigned int rounds = 2000/pow((length*(s+1)/2048), 3);//Amount of rounds for a one second test on the poor devlopper's computer.
  429. mpz_t z_r, z_a[cores];
  430. mpz_init(z_r);
  431. #pragma omp parallel for
  432. for (unsigned int i = 0 ; i < cores ; i++)
  433. mpz_init(z_a[i]);
  434. gmp_randstate_t prng;
  435. gmp_randinit_default(prng);
  436. gmp_randseed_ui(prng, time(NULL));
  437. getRandInteger(z_r, length, prng);
  438. start = omp_get_wtime();
  439. for(unsigned int round = 0 ; round < rounds ; round++)
  440. {
  441. #pragma omp parallel for
  442. for (unsigned int i = 0 ; i < cores ; i++)
  443. {
  444. dec(publicParameters.getPubKey(),
  445. privateParameters.getPrvKey(),
  446. z_r,
  447. s ,
  448. z_a[i] );
  449. usleep(5);
  450. }
  451. }
  452. mpz_clear(z_r);
  453. #pragma omp parallel for
  454. for (unsigned int i = 0 ; i < cores ; i++)
  455. mpz_clear(z_a[i]);
  456. result = omp_get_wtime() - start;
  457. return result /(cores)/rounds ;
  458. }
  459. void
  460. PaillierAdapter::getRandInteger(mpz_t rop, unsigned int length, gmp_randstate_t prng)
  461. {
  462. do {
  463. mpz_urandomb(rop, prng, length);
  464. }while(mpz_sizeinbase(rop, 2) != length);
  465. }
  466. unsigned int PaillierAdapter::getAllCryptoParams(std::set<std::string>& crypto_params)
  467. {
  468. unsigned int params_nbr = 0;
  469. unsigned int k_array_size = 4;
  470. // k=256 gives a 15K bit plaintext modulus and a 30K bit ciphertext modulus
  471. // as this is huge we turn off this proposal by default
  472. unsigned int k[4] = {80, 100, 128, 192};
  473. for (unsigned int i = 0 ; i < k_array_size ; i++)
  474. {
  475. params_nbr += getCryptoParams(k[i], crypto_params);
  476. }
  477. return params_nbr;
  478. }
  479. unsigned int PaillierAdapter::getCryptoParams(unsigned int k, std::set<std::string>& crypto_params)
  480. {
  481. unsigned int params_nbr = 0;
  482. string k_str = std::to_string(k);
  483. unsigned int modulus_size = securityToModulus(k);
  484. if (modulus_size == 0) return 0;
  485. // We'll increase params_nbr when the client handles better s
  486. for (unsigned int s = 1 ; params_nbr < 1 ; s++)
  487. {
  488. string param = cryptoName + ":" + k_str + ":" + to_string(modulus_size*s) + ":" + to_string(modulus_size*(s+1));
  489. if(crypto_params.insert(param).second) params_nbr++;
  490. param = "";
  491. }
  492. return params_nbr;
  493. }
  494. long PaillierAdapter::setandgetAbsBitPerCiphertext(unsigned int elt_nbr)
  495. {
  496. return publicParameters.getAbsorptionBitsize();
  497. }
  498. std::string PaillierAdapter::getSerializedCryptoParams(bool shortversion)
  499. {
  500. return publicParameters.getSerializedParams(shortversion);
  501. }
  502. double PaillierAdapter::estimateAbsTime(std::string crypto_param)
  503. {
  504. vector<string> fields;
  505. boost::algorithm::split(fields, crypto_param, boost::algorithm::is_any_of(":"));
  506. const double mod_size_s = static_cast<double>(atoi(fields[3].c_str()));
  507. return 1.0 / (kMillion/(3.0*1016) * pow(2048 / mod_size_s, 3));
  508. }
  509. /**
  510. * Compute a modular exponentiation in crypted space who is a operation in clear space.
  511. * Params :
  512. * - mpz_t res : operation result;
  513. * - mpz_t a : first operand, crypted data ;
  514. * - mpz_t b : second operans, crypted data;
  515. * - int s : modulus index .
  516. **/
  517. void PaillierAdapter::e_add(mpz_t res, mpz_t a, mpz_t b, int s)
  518. {
  519. mpz_mul(res, a, b);
  520. mpz_mod(res, res, *publicParameters.getPubKey()->getnj(s));
  521. }
  522. /**
  523. * Compute modular multiplication in crypted space who is a multiplicaton in clear space.
  524. * Params :
  525. * - mpz_t res : operation result;
  526. * - mpz_t a : first operand, crypted data ;
  527. * - mpz_t n : second operand, a constant ;
  528. * - int s : modulus index .
  529. **/
  530. void PaillierAdapter::e_mul_const(mpz_t res, mpz_t a, mpz_t n, int s)
  531. {
  532. mpz_powm(res, a, n , *publicParameters.getPubKey()->getnj(s));
  533. }