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