src/util/crypto_paillier.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2014 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 /**
  20  * @file util/crypto_paillier.c
  21  * @brief implementation of the paillier crypto system with libgcrypt
  22  * @author Florian Dold
  23  * @author Christian Fuchs
  24  */
  25 #include "platform.h"
  26 #include <gcrypt.h>
  27 #include "gnunet_util_lib.h"
  28
  29
  30 /**
  31  * Create a freshly generated paillier public key.
  32  *
  33  * @param[out] public_key Where to store the public key?
  34  * @param[out] private_key Where to store the private key?
  35  */
  36 void
  37 GNUNET_CRYPTO_paillier_create (struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
  38                                struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
  39 {
  40   gcry_mpi_t p;
  41   gcry_mpi_t q;
  42   gcry_mpi_t phi;
  43   gcry_mpi_t mu;
  44   gcry_mpi_t n;
  45
  46   /* Generate two distinct primes.  The probability that the loop body
  47      is executed more than once is very very low... */
  48   p = NULL;
  49   q = NULL;
  50   do {
  51     if (NULL != p)
  52       gcry_mpi_release (p);
  53     if (NULL != q)
  54       gcry_mpi_release (q);
  55     GNUNET_assert (0 ==
  56                    gcry_prime_generate (&p,
  57                                         GNUNET_CRYPTO_PAILLIER_BITS / 2,
  58                                         0, NULL, NULL, NULL,
  59                                         GCRY_STRONG_RANDOM, 0));
  60     GNUNET_assert (0 ==
  61                    gcry_prime_generate (&q,
  62                                         GNUNET_CRYPTO_PAILLIER_BITS / 2,
  63                                         0, NULL, NULL, NULL,
  64                                         GCRY_STRONG_RANDOM, 0));
  65   }
  66   while (0 == gcry_mpi_cmp (p, q));
  67   /* n = p * q */
  68   GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
  69   gcry_mpi_mul (n,
  70                 p,
  71                 q);
  72   GNUNET_CRYPTO_mpi_print_unsigned (public_key,
  73                                     sizeof (struct GNUNET_CRYPTO_PaillierPublicKey),
  74                                     n);
  75
  76   /* compute phi(n) = (p-1)(q-1) */
  77   GNUNET_assert (NULL != (phi = gcry_mpi_new (0)));
  78   gcry_mpi_sub_ui (p, p, 1);
  79   gcry_mpi_sub_ui (q, q, 1);
  80   gcry_mpi_mul (phi, p, q);
  81   gcry_mpi_release (p);
  82   gcry_mpi_release (q);
  83
  84   /* lambda equals phi(n) in the simplified key generation */
  85   GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda,
  86                                     GNUNET_CRYPTO_PAILLIER_BITS / 8,
  87                                     phi);
  88   /* mu = phi^{-1} mod n, as we use g = n + 1 */
  89   GNUNET_assert (NULL != (mu = gcry_mpi_new (0)));
  90   GNUNET_assert (0 != gcry_mpi_invm (mu,
  91                                      phi,
  92                                      n));
  93   gcry_mpi_release (phi);
  94   gcry_mpi_release (n);
  95   GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu,
  96                                     GNUNET_CRYPTO_PAILLIER_BITS / 8,
  97                                     mu);
  98   gcry_mpi_release (mu);
  99 }
 100
 101
 102 /**
 103  * Encrypt a plaintext with a paillier public key.
 104  *
 105  * @param public_key Public key to use.
 106  * @param m Plaintext to encrypt.
 107  * @param desired_ops How many homomorphic ops the caller intends to use
 108  * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
 109  * @return guaranteed number of supported homomorphic operations >= 1,
 110  *         or desired_ops, in case that is lower,
 111  *         or -1 if less than one homomorphic operation is possible
 112  */
 113 int
 114 GNUNET_CRYPTO_paillier_encrypt1 (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 115                                 const gcry_mpi_t m,
 116                                 int desired_ops,
 117                                 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
 118 {
 119   int possible_opts;
 120   gcry_mpi_t n_square;
 121   gcry_mpi_t r;
 122   gcry_mpi_t c;
 123   gcry_mpi_t n;
 124   gcry_mpi_t tmp1;
 125   gcry_mpi_t tmp2;
 126   unsigned int highbit;
 127
 128   /* determine how many operations we could allow, if the other number
 129      has the same length. */
 130   GNUNET_assert (NULL != (tmp1 = gcry_mpi_set_ui (NULL, 1)));
 131   GNUNET_assert (NULL != (tmp2 = gcry_mpi_set_ui (NULL, 2)));
 132   gcry_mpi_mul_2exp (tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
 133
 134   /* count number of possible operations
 135      this would be nicer with gcry_mpi_get_nbits, however it does not return
 136      the BITLENGTH of the given MPI's value, but the bits required
 137      to represent the number as MPI. */
 138   for (possible_opts = -2; gcry_mpi_cmp (tmp1, m) > 0; possible_opts++)
 139     gcry_mpi_div (tmp1, NULL, tmp1, tmp2, 0);
 140   gcry_mpi_release (tmp1);
 141   gcry_mpi_release (tmp2);
 142
 143   if (possible_opts < 1)
 144     possible_opts = 0;
 145   /* soft-cap by caller */
 146   possible_opts = (desired_ops < possible_opts)? desired_ops : possible_opts;
 147
 148   ciphertext->remaining_ops = htonl (possible_opts);
 149
 150   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 151                                    public_key,
 152                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 153   highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
 154   while ( (! gcry_mpi_test_bit (n, highbit)) &&
 155           (0 != highbit) )
 156     highbit--;
 157   if (0 == highbit)
 158   {
 159     /* invalid public key */
 160     GNUNET_break_op (0);
 161     gcry_mpi_release (n);
 162     return GNUNET_SYSERR;
 163   }
 164   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 165   GNUNET_assert (0 != (r = gcry_mpi_new (0)));
 166   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 167   gcry_mpi_mul (n_square, n, n);
 168
 169   /* generate r < n (without bias) */
 170   do {
 171     gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
 172   }
 173   while (gcry_mpi_cmp (r, n) >= 0);
 174
 175   /* c = (n+1)^m mod n^2 */
 176   /* c = n + 1 */
 177   gcry_mpi_add_ui (c, n, 1);
 178   /* c = (n+1)^m mod n^2 */
 179   gcry_mpi_powm (c, c, m, n_square);
 180   /* r <- r^n mod n^2 */
 181   gcry_mpi_powm (r, r, n, n_square);
 182   /* c <- r*c mod n^2 */
 183   gcry_mpi_mulm (c, r, c, n_square);
 184
 185   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
 186                                     sizeof ciphertext->bits,
 187                                     c);
 188
 189   gcry_mpi_release (n_square);
 190   gcry_mpi_release (n);
 191   gcry_mpi_release (r);
 192   gcry_mpi_release (c);
 193
 194   return possible_opts;
 195 }
 196
 197
 198 /**
 199  * Encrypt a plaintext with a paillier public key.
 200  *
 201  * @param public_key Public key to use.
 202  * @param m Plaintext to encrypt.
 203  * @param desired_ops How many homomorphic ops the caller intends to use
 204  * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
 205  * @return guaranteed number of supported homomorphic operations >= 1,
 206  *         or desired_ops, in case that is lower,
 207  *         or -1 if less than one homomorphic operation is possible
 208  */
 209 int
 210 GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 211                                 const gcry_mpi_t m,
 212                                 int desired_ops,
 213                                 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
 214 {
 215   int possible_opts;
 216   gcry_mpi_t n_square;
 217   gcry_mpi_t r;
 218   gcry_mpi_t rn;
 219   gcry_mpi_t g;
 220   gcry_mpi_t gm;
 221   gcry_mpi_t c;
 222   gcry_mpi_t n;
 223   gcry_mpi_t max_num;
 224   unsigned int highbit;
 225
 226   /* set max_num = 2^{GNUNET_CRYPTO_PAILLIER_BITS}, the largest
 227      number we can have as a result */
 228   GNUNET_assert (NULL != (max_num = gcry_mpi_set_ui (NULL, 1)));
 229   gcry_mpi_mul_2exp (max_num,
 230                      max_num,
 231                      GNUNET_CRYPTO_PAILLIER_BITS);
 232
 233   /* Determine how many operations we could allow, assuming the other
 234      number has the same length (or is smaller), by counting the
 235      number of possible operations.  We essentially divide max_num by
 236      2 until the result is no longer larger than 'm', incrementing the
 237      maximum number of operations in each round, starting at -2 */
 238   for (possible_opts = -2; gcry_mpi_cmp (max_num, m) > 0; possible_opts++)
 239     gcry_mpi_div (max_num,
 240                   NULL,
 241                   max_num,
 242                   GCRYMPI_CONST_TWO,
 243                   0);
 244   gcry_mpi_release (max_num);
 245
 246   if (possible_opts < 1)
 247     possible_opts = 0;
 248   /* Enforce soft-cap by caller */
 249   possible_opts = GNUNET_MIN (desired_ops, possible_opts);
 250   ciphertext->remaining_ops = htonl (possible_opts);
 251
 252   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 253                                    public_key,
 254                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 255
 256   /* check public key for number of bits, bail out if key is all zeros */
 257   highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
 258   while ( (! gcry_mpi_test_bit (n, highbit)) &&
 259           (0 != highbit) )
 260     highbit--;
 261   if (0 == highbit)
 262   {
 263     /* invalid public key */
 264     GNUNET_break_op (0);
 265     gcry_mpi_release (n);
 266     return GNUNET_SYSERR;
 267   }
 268
 269   /* generate r < n (without bias) */
 270   GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
 271   do {
 272     gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
 273   }
 274   while (gcry_mpi_cmp (r, n) >= 0);
 275
 276   /* g = n + 1 */
 277   GNUNET_assert (0 != (g = gcry_mpi_new (0)));
 278   gcry_mpi_add_ui (g, n, 1);
 279
 280   /* n_square = n^2 */
 281   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 282   gcry_mpi_mul (n_square,
 283                 n,
 284                 n);
 285
 286   /* gm = g^m mod n^2 */
 287   GNUNET_assert (0 != (gm = gcry_mpi_new (0)));
 288   gcry_mpi_powm (gm, g, m, n_square);
 289   gcry_mpi_release (g);
 290
 291   /* rn <- r^n mod n^2 */
 292   GNUNET_assert (0 != (rn = gcry_mpi_new (0)));
 293   gcry_mpi_powm (rn, r, n, n_square);
 294   gcry_mpi_release (r);
 295   gcry_mpi_release (n);
 296
 297   /* c <- rn * gm mod n^2 */
 298   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 299   gcry_mpi_mulm (c, rn, gm, n_square);
 300   gcry_mpi_release (n_square);
 301   gcry_mpi_release (gm);
 302   gcry_mpi_release (rn);
 303
 304   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
 305                                     sizeof (ciphertext->bits),
 306                                     c);
 307   gcry_mpi_release (c);
 308
 309   return possible_opts;
 310 }
 311
 312
 313 /**
 314  * Decrypt a paillier ciphertext with a private key.
 315  *
 316  * @param private_key Private key to use for decryption.
 317  * @param public_key Public key to use for encryption.
 318  * @param ciphertext Ciphertext to decrypt.
 319  * @param[out] m Decryption of @a ciphertext with @private_key.
 320  */
 321 void
 322 GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
 323                                 const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 324                                 const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
 325                                 gcry_mpi_t m)
 326 {
 327   gcry_mpi_t mu;
 328   gcry_mpi_t lambda;
 329   gcry_mpi_t n;
 330   gcry_mpi_t n_square;
 331   gcry_mpi_t c;
 332   gcry_mpi_t cmu;
 333   gcry_mpi_t cmum1;
 334   gcry_mpi_t mod;
 335
 336   GNUNET_CRYPTO_mpi_scan_unsigned (&lambda,
 337                                    private_key->lambda,
 338                                    sizeof (private_key->lambda));
 339   GNUNET_CRYPTO_mpi_scan_unsigned (&mu,
 340                                    private_key->mu,
 341                                    sizeof (private_key->mu));
 342   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 343                                    public_key,
 344                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 345   GNUNET_CRYPTO_mpi_scan_unsigned (&c,
 346                                    ciphertext->bits,
 347                                    sizeof (ciphertext->bits));
 348
 349   /* n_square = n * n */
 350   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 351   gcry_mpi_mul (n_square, n, n);
 352
 353   /* cmu = c^lambda mod n^2 */
 354   GNUNET_assert (0 != (cmu = gcry_mpi_new (0)));
 355   gcry_mpi_powm (cmu,
 356                  c,
 357                  lambda,
 358                  n_square);
 359   gcry_mpi_release (n_square);
 360   gcry_mpi_release (lambda);
 361   gcry_mpi_release (c);
 362
 363   /* cmum1 = cmu - 1 */
 364   GNUNET_assert (0 != (cmum1 = gcry_mpi_new (0)));
 365   gcry_mpi_sub_ui (cmum1, cmu, 1);
 366   gcry_mpi_release (cmu);
 367
 368   /* mod = cmum1 / n (mod n) */
 369   GNUNET_assert (0 != (mod = gcry_mpi_new (0)));
 370   gcry_mpi_div (mod, NULL, cmum1, n, 0);
 371   gcry_mpi_release (cmum1);
 372
 373   /* m = mod * mu mod n */
 374   gcry_mpi_mulm (m, mod, mu, n);
 375   gcry_mpi_release (mod);
 376   gcry_mpi_release (mu);
 377   gcry_mpi_release (n);
 378 }
 379
 380
 381 /**
 382  * Compute a ciphertext that represents the sum of the plaintext in @a
 383  * c1 and @a c2.
 384  *
 385  * Note that this operation can only be done a finite number of times
 386  * before an overflow occurs.
 387  *
 388  * @param public_key Public key to use for encryption.
 389  * @param c1 Paillier cipher text.
 390  * @param c2 Paillier cipher text.
 391  * @param[out] result Result of the homomorphic operation.
 392  * @return #GNUNET_OK if the result could be computed,
 393  *         #GNUNET_SYSERR if no more homomorphic operations are remaining.
 394  */
 395 int
 396 GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 397                                 const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
 398                                 const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
 399                                 struct GNUNET_CRYPTO_PaillierCiphertext *result)
 400 {
 401   gcry_mpi_t a;
 402   gcry_mpi_t b;
 403   gcry_mpi_t c;
 404   gcry_mpi_t n;
 405   gcry_mpi_t n_square;
 406   int32_t o1;
 407   int32_t o2;
 408
 409   o1 = (int32_t) ntohl (c1->remaining_ops);
 410   o2 = (int32_t) ntohl (c2->remaining_ops);
 411   if ( (0 >= o1) || (0 >= o2) )
 412   {
 413     GNUNET_break_op (0);
 414     return GNUNET_SYSERR;
 415   }
 416
 417   GNUNET_CRYPTO_mpi_scan_unsigned (&a,
 418                                    c1->bits,
 419                                    sizeof (c1->bits));
 420   GNUNET_CRYPTO_mpi_scan_unsigned (&b,
 421                                    c2->bits,
 422                                    sizeof (c2->bits));
 423   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 424                                    public_key,
 425                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 426
 427   /* n_square = n * n */
 428   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 429   gcry_mpi_mul (n_square, n, n);
 430   gcry_mpi_release (n);
 431
 432   /* c = a * b mod n_square */
 433   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 434   gcry_mpi_mulm (c, a, b, n_square);
 435   gcry_mpi_release (n_square);
 436   gcry_mpi_release (a);
 437   gcry_mpi_release (b);
 438
 439   result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1);
 440   GNUNET_CRYPTO_mpi_print_unsigned (result->bits,
 441                                     sizeof (result->bits),
 442                                     c);
 443   gcry_mpi_release (c);
 444   return ntohl (result->remaining_ops);
 445 }
 446
 447
 448 /**
 449  * Get the number of remaining supported homomorphic operations.
 450  *
 451  * @param c Paillier cipher text.
 452  * @return the number of remaining homomorphic operations
 453  */
 454 int
 455 GNUNET_CRYPTO_paillier_hom_get_remaining (const struct GNUNET_CRYPTO_PaillierCiphertext *c)
 456 {
 457   GNUNET_assert (NULL != c);
 458   return ntohl (c->remaining_ops);
 459 }
 460
 461 /* end of crypto_paillier.c */
 462