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
   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., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, 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   /* c = n + 1 */
 179   gcry_mpi_add_ui (c, n, 1);
 180   /* c = (n+1)^m mod n^2 */
 181   gcry_mpi_powm (c, c, m, n_square);
 182   /* r <- r^n mod n^2 */
 183   gcry_mpi_powm (r, r, n, n_square);
 184   /* c <- r*c mod n^2 */
 185   gcry_mpi_mulm (c, r, c, n_square);
 186
 187   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
 188                                     sizeof ciphertext->bits,
 189                                     c);
 190
 191   gcry_mpi_release (n_square);
 192   gcry_mpi_release (n);
 193   gcry_mpi_release (r);
 194   gcry_mpi_release (c);
 195
 196   return possible_opts;
 197 }
 198
 199
 200 /**
 201  * Encrypt a plaintext with a paillier public key.
 202  *
 203  * @param public_key Public key to use.
 204  * @param m Plaintext to encrypt.
 205  * @param desired_ops How many homomorphic ops the caller intends to use
 206  * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
 207  * @return guaranteed number of supported homomorphic operations >= 1,
 208  *         or desired_ops, in case that is lower,
 209  *         or -1 if less than one homomorphic operation is possible
 210  */
 211 int
 212 GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 213                                 const gcry_mpi_t m,
 214                                 int desired_ops,
 215                                 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
 216 {
 217   int possible_opts;
 218   gcry_mpi_t n_square;
 219   gcry_mpi_t r;
 220   gcry_mpi_t rn;
 221   gcry_mpi_t g;
 222   gcry_mpi_t gm;
 223   gcry_mpi_t c;
 224   gcry_mpi_t n;
 225   gcry_mpi_t max_num;
 226   unsigned int highbit;
 227
 228   /* set max_num = 2^{GNUNET_CRYPTO_PAILLIER_BITS}, the largest
 229      number we can have as a result */
 230   GNUNET_assert (NULL != (max_num = gcry_mpi_set_ui (NULL, 1)));
 231   gcry_mpi_mul_2exp (max_num,
 232                      max_num,
 233                      GNUNET_CRYPTO_PAILLIER_BITS);
 234
 235   /* Determine how many operations we could allow, assuming the other
 236      number has the same length (or is smaller), by counting the
 237      number of possible operations.  We essentially divide max_num by
 238      2 until the result is no longer larger than 'm', incrementing the
 239      maximum number of operations in each round, starting at -2 */
 240   for (possible_opts = -2; gcry_mpi_cmp (max_num, m) > 0; possible_opts++)
 241     gcry_mpi_div (max_num,
 242                   NULL,
 243                   max_num,
 244                   GCRYMPI_CONST_TWO,
 245                   0);
 246   gcry_mpi_release (max_num);
 247
 248   if (possible_opts < 1)
 249     possible_opts = 0;
 250   /* Enforce soft-cap by caller */
 251   possible_opts = GNUNET_MIN (desired_ops, possible_opts);
 252   ciphertext->remaining_ops = htonl (possible_opts);
 253
 254   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 255                                    public_key,
 256                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 257
 258   /* check public key for number of bits, bail out if key is all zeros */
 259   highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
 260   while ( (! gcry_mpi_test_bit (n, highbit)) &&
 261           (0 != highbit) )
 262     highbit--;
 263   if (0 == highbit)
 264   {
 265     /* invalid public key */
 266     GNUNET_break_op (0);
 267     gcry_mpi_release (n);
 268     return GNUNET_SYSERR;
 269   }
 270
 271   /* generate r < n (without bias) */
 272   GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
 273   do {
 274     gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
 275   }
 276   while (gcry_mpi_cmp (r, n) >= 0);
 277
 278   /* g = n + 1 */
 279   GNUNET_assert (0 != (g = gcry_mpi_new (0)));
 280   gcry_mpi_add_ui (g, n, 1);
 281
 282   /* n_square = n^2 */
 283   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 284   gcry_mpi_mul (n_square,
 285                 n,
 286                 n);
 287
 288   /* gm = g^m mod n^2 */
 289   GNUNET_assert (0 != (gm = gcry_mpi_new (0)));
 290   gcry_mpi_powm (gm, g, m, n_square);
 291   gcry_mpi_release (g);
 292
 293   /* rn <- r^n mod n^2 */
 294   GNUNET_assert (0 != (rn = gcry_mpi_new (0)));
 295   gcry_mpi_powm (rn, r, n, n_square);
 296   gcry_mpi_release (r);
 297   gcry_mpi_release (n);
 298
 299   /* c <- rn * gm mod n^2 */
 300   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 301   gcry_mpi_mulm (c, rn, gm, n_square);
 302   gcry_mpi_release (n_square);
 303   gcry_mpi_release (gm);
 304   gcry_mpi_release (rn);
 305
 306   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
 307                                     sizeof (ciphertext->bits),
 308                                     c);
 309   gcry_mpi_release (c);
 310
 311   return possible_opts;
 312 }
 313
 314
 315 /**
 316  * Decrypt a paillier ciphertext with a private key.
 317  *
 318  * @param private_key Private key to use for decryption.
 319  * @param public_key Public key to use for encryption.
 320  * @param ciphertext Ciphertext to decrypt.
 321  * @param[out] m Decryption of @a ciphertext with @private_key.
 322  */
 323 void
 324 GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
 325                                 const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 326                                 const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
 327                                 gcry_mpi_t m)
 328 {
 329   gcry_mpi_t mu;
 330   gcry_mpi_t lambda;
 331   gcry_mpi_t n;
 332   gcry_mpi_t n_square;
 333   gcry_mpi_t c;
 334   gcry_mpi_t cmu;
 335   gcry_mpi_t cmum1;
 336   gcry_mpi_t mod;
 337
 338   GNUNET_CRYPTO_mpi_scan_unsigned (&lambda,
 339                                    private_key->lambda,
 340                                    sizeof (private_key->lambda));
 341   GNUNET_CRYPTO_mpi_scan_unsigned (&mu,
 342                                    private_key->mu,
 343                                    sizeof (private_key->mu));
 344   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 345                                    public_key,
 346                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 347   GNUNET_CRYPTO_mpi_scan_unsigned (&c,
 348                                    ciphertext->bits,
 349                                    sizeof (ciphertext->bits));
 350
 351   /* n_square = n * n */
 352   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 353   gcry_mpi_mul (n_square, n, n);
 354
 355   /* cmu = c^lambda mod n^2 */
 356   GNUNET_assert (0 != (cmu = gcry_mpi_new (0)));
 357   gcry_mpi_powm (cmu,
 358                  c,
 359                  lambda,
 360                  n_square);
 361   gcry_mpi_release (n_square);
 362   gcry_mpi_release (lambda);
 363   gcry_mpi_release (c);
 364
 365   /* cmum1 = cmu - 1 */
 366   GNUNET_assert (0 != (cmum1 = gcry_mpi_new (0)));
 367   gcry_mpi_sub_ui (cmum1, cmu, 1);
 368   gcry_mpi_release (cmu);
 369
 370   /* mod = cmum1 / n (mod n) */
 371   GNUNET_assert (0 != (mod = gcry_mpi_new (0)));
 372   gcry_mpi_div (mod, NULL, cmum1, n, 0);
 373
 374   /* m = mod * mu mod n */
 375   gcry_mpi_mulm (m, mod, mu, n);
 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