src/util/crypto_paillier.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2014 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      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      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19  */
  20
  21 /**
  22  * @file util/crypto_paillier.c
  23  * @brief implementation of the paillier crypto system with libgcrypt
  24  * @author Florian Dold
  25  * @author Christian Fuchs
  26  */
  27 #include "platform.h"
  28 #include <gcrypt.h>
  29 #include "gnunet_util_lib.h"
  30
  31
  32 /**
  33  * Create a freshly generated paillier public key.
  34  *
  35  * @param[out] public_key Where to store the public key?
  36  * @param[out] private_key Where to store the private key?
  37  */
  38 void
  39 GNUNET_CRYPTO_paillier_create (struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
  40                                struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
  41 {
  42   gcry_mpi_t p;
  43   gcry_mpi_t q;
  44   gcry_mpi_t phi;
  45   gcry_mpi_t mu;
  46   gcry_mpi_t n;
  47
  48   /* Generate two distinct primes.  The probability that the loop body
  49      is executed more than once is very very low... */
  50   p = NULL;
  51   q = NULL;
  52   do {
  53     if (NULL != p)
  54       gcry_mpi_release (p);
  55     if (NULL != q)
  56       gcry_mpi_release (q);
  57     GNUNET_assert (0 ==
  58                    gcry_prime_generate (&p,
  59                                         GNUNET_CRYPTO_PAILLIER_BITS / 2,
  60                                         0, NULL, NULL, NULL,
  61                                         GCRY_STRONG_RANDOM, 0));
  62     GNUNET_assert (0 ==
  63                    gcry_prime_generate (&q,
  64                                         GNUNET_CRYPTO_PAILLIER_BITS / 2,
  65                                         0, NULL, NULL, NULL,
  66                                         GCRY_STRONG_RANDOM, 0));
  67   }
  68   while (0 == gcry_mpi_cmp (p, q));
  69   /* n = p * q */
  70   GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
  71   gcry_mpi_mul (n,
  72                 p,
  73                 q);
  74   GNUNET_CRYPTO_mpi_print_unsigned (public_key,
  75                                     sizeof (struct GNUNET_CRYPTO_PaillierPublicKey),
  76                                     n);
  77
  78   /* compute phi(n) = (p-1)(q-1) */
  79   GNUNET_assert (NULL != (phi = gcry_mpi_new (0)));
  80   gcry_mpi_sub_ui (p, p, 1);
  81   gcry_mpi_sub_ui (q, q, 1);
  82   gcry_mpi_mul (phi, p, q);
  83   gcry_mpi_release (p);
  84   gcry_mpi_release (q);
  85
  86   /* lambda equals phi(n) in the simplified key generation */
  87   GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda,
  88                                     GNUNET_CRYPTO_PAILLIER_BITS / 8,
  89                                     phi);
  90   /* mu = phi^{-1} mod n, as we use g = n + 1 */
  91   GNUNET_assert (NULL != (mu = gcry_mpi_new (0)));
  92   GNUNET_assert (0 != gcry_mpi_invm (mu,
  93                                      phi,
  94                                      n));
  95   gcry_mpi_release (phi);
  96   gcry_mpi_release (n);
  97   GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu,
  98                                     GNUNET_CRYPTO_PAILLIER_BITS / 8,
  99                                     mu);
 100   gcry_mpi_release (mu);
 101 }
 102
 103
 104 /**
 105  * Encrypt a plaintext with a paillier public key.
 106  *
 107  * @param public_key Public key to use.
 108  * @param m Plaintext to encrypt.
 109  * @param desired_ops How many homomorphic ops the caller intends to use
 110  * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
 111  * @return guaranteed number of supported homomorphic operations >= 1,
 112  *         or desired_ops, in case that is lower,
 113  *         or -1 if less than one homomorphic operation is possible
 114  */
 115 int
 116 GNUNET_CRYPTO_paillier_encrypt1 (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 117                                 const gcry_mpi_t m,
 118                                 int desired_ops,
 119                                 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
 120 {
 121   int possible_opts;
 122   gcry_mpi_t n_square;
 123   gcry_mpi_t r;
 124   gcry_mpi_t c;
 125   gcry_mpi_t n;
 126   gcry_mpi_t tmp1;
 127   gcry_mpi_t tmp2;
 128   unsigned int highbit;
 129
 130   // determine how many operations we could allow, if the other number
 131   // has the same length.
 132   GNUNET_assert (NULL != (tmp1 = gcry_mpi_set_ui (NULL, 1)));
 133   GNUNET_assert (NULL != (tmp2 = gcry_mpi_set_ui (NULL, 2)));
 134   gcry_mpi_mul_2exp (tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
 135
 136   // count number of possible operations
 137   // this would be nicer with gcry_mpi_get_nbits, however it does not return
 138   // the BITLENGTH of the given MPI's value, but the bits required
 139   // to represent the number as MPI.
 140   for (possible_opts = -2; gcry_mpi_cmp (tmp1, m) > 0; possible_opts++)
 141     gcry_mpi_div (tmp1, NULL, tmp1, tmp2, 0);
 142   gcry_mpi_release (tmp1);
 143   gcry_mpi_release (tmp2);
 144
 145   if (possible_opts < 1)
 146     possible_opts = 0;
 147   //soft-cap by caller
 148   possible_opts = (desired_ops < possible_opts)? desired_ops : possible_opts;
 149
 150   ciphertext->remaining_ops = htonl (possible_opts);
 151
 152   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 153                                    public_key,
 154                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 155   highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
 156   while ( (! gcry_mpi_test_bit (n, highbit)) &&
 157           (0 != highbit) )
 158     highbit--;
 159   if (0 == highbit)
 160   {
 161     /* invalid public key */
 162     GNUNET_break_op (0);
 163     gcry_mpi_release (n);
 164     return GNUNET_SYSERR;
 165   }
 166   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 167   GNUNET_assert (0 != (r = gcry_mpi_new (0)));
 168   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 169   gcry_mpi_mul (n_square, n, n);
 170
 171   // generate r < n (without bias)
 172   do {
 173     gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
 174   }
 175   while (gcry_mpi_cmp (r, n) >= 0);
 176
 177   // c = (n+1)^m mod n^2
 178   gcry_mpi_add_ui (c, n, 1); // c = n + 1
 179   gcry_mpi_powm (c, c, m, n_square); // c = (n+1)^m mod n^2
 180   // r <- r^n mod n^2
 181   gcry_mpi_powm (r, r, n, n_square); // r = r^n mod n^2
 182   // c <- r*c mod n^2
 183   gcry_mpi_mulm (c, r, c, n_square); // c = r*c mod n^2
 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 (0 != (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
 372   /* m = mod * mu mod n */
 373   gcry_mpi_mulm (m, mod, mu, n);
 374   gcry_mpi_release (mu);
 375   gcry_mpi_release (n);
 376 }
 377
 378
 379 /**
 380  * Compute a ciphertext that represents the sum of the plaintext in @a
 381  * c1 and @a c2.
 382  *
 383  * Note that this operation can only be done a finite number of times
 384  * before an overflow occurs.
 385  *
 386  * @param public_key Public key to use for encryption.
 387  * @param c1 Paillier cipher text.
 388  * @param c2 Paillier cipher text.
 389  * @param[out] result Result of the homomorphic operation.
 390  * @return #GNUNET_OK if the result could be computed,
 391  *         #GNUNET_SYSERR if no more homomorphic operations are remaining.
 392  */
 393 int
 394 GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 395                                 const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
 396                                 const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
 397                                 struct GNUNET_CRYPTO_PaillierCiphertext *result)
 398 {
 399   gcry_mpi_t a;
 400   gcry_mpi_t b;
 401   gcry_mpi_t c;
 402   gcry_mpi_t n;
 403   gcry_mpi_t n_square;
 404   int32_t o1;
 405   int32_t o2;
 406
 407   o1 = (int32_t) ntohl (c1->remaining_ops);
 408   o2 = (int32_t) ntohl (c2->remaining_ops);
 409   if ( (0 >= o1) || (0 >= o2) )
 410   {
 411     GNUNET_break_op (0);
 412     return GNUNET_SYSERR;
 413   }
 414
 415   GNUNET_CRYPTO_mpi_scan_unsigned (&a,
 416                                    c1->bits,
 417                                    sizeof (c1->bits));
 418   GNUNET_CRYPTO_mpi_scan_unsigned (&b,
 419                                    c2->bits,
 420                                    sizeof (c2->bits));
 421   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 422                                    public_key,
 423                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 424
 425   /* n_square = n * n */
 426   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 427   gcry_mpi_mul (n_square, n, n);
 428   gcry_mpi_release (n);
 429
 430   /* c = a * b mod n_square */
 431   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 432   gcry_mpi_mulm (c, a, b, n_square);
 433   gcry_mpi_release (n_square);
 434   gcry_mpi_release (a);
 435   gcry_mpi_release (b);
 436
 437   result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1);
 438   GNUNET_CRYPTO_mpi_print_unsigned (result->bits,
 439                                     sizeof (result->bits),
 440                                     c);
 441   gcry_mpi_release (c);
 442   return ntohl (result->remaining_ops);
 443 }
 444
 445
 446 /**
 447  * Get the number of remaining supported homomorphic operations.
 448  *
 449  * @param c Paillier cipher text.
 450  * @return the number of remaining homomorphic operations
 451  */
 452 int
 453 GNUNET_CRYPTO_paillier_hom_get_remaining (const struct GNUNET_CRYPTO_PaillierCiphertext *c)
 454 {
 455   GNUNET_assert (NULL != c);
 456   return ntohl (c->remaining_ops);
 457 }
 458
 459 /* end of crypto_paillier.c */
 460