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