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 */
 250   for (possible_opts = -2; gcry_mpi_cmp (max_num, m) > 0; possible_opts++)
 251     gcry_mpi_div (max_num,
 252                   NULL,
 253                   max_num,
 254                   GCRYMPI_CONST_TWO,
 255                   0);
 256   gcry_mpi_release (max_num);
 257
 258   if (possible_opts < 1)
 259     possible_opts = 0;
 260   /* Enforce soft-cap by caller */
 261   possible_opts = GNUNET_MIN (desired_ops, possible_opts);
 262   ciphertext->remaining_ops = htonl (possible_opts);
 263
 264   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 265                                    public_key,
 266                                    sizeof(struct
 267                                           GNUNET_CRYPTO_PaillierPublicKey));
 268
 269   /* check public key for number of bits, bail out if key is all zeros */
 270   highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
 271   while ((! gcry_mpi_test_bit (n, highbit)) &&
 272          (0 != highbit))
 273     highbit--;
 274   if (0 == highbit)
 275   {
 276     /* invalid public key */
 277     GNUNET_break_op (0);
 278     gcry_mpi_release (n);
 279     return GNUNET_SYSERR;
 280   }
 281
 282   /* generate r < n (without bias) */
 283   GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
 284   do
 285   {
 286     gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
 287   }
 288   while (gcry_mpi_cmp (r, n) >= 0);
 289
 290   /* g = n + 1 */
 291   GNUNET_assert (0 != (g = gcry_mpi_new (0)));
 292   gcry_mpi_add_ui (g, n, 1);
 293
 294   /* n_square = n^2 */
 295   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 296   gcry_mpi_mul (n_square,
 297                 n,
 298                 n);
 299
 300   /* gm = g^m mod n^2 */
 301   GNUNET_assert (0 != (gm = gcry_mpi_new (0)));
 302   gcry_mpi_powm (gm, g, m, n_square);
 303   gcry_mpi_release (g);
 304
 305   /* rn <- r^n mod n^2 */
 306   GNUNET_assert (0 != (rn = gcry_mpi_new (0)));
 307   gcry_mpi_powm (rn, r, n, n_square);
 308   gcry_mpi_release (r);
 309   gcry_mpi_release (n);
 310
 311   /* c <- rn * gm mod n^2 */
 312   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 313   gcry_mpi_mulm (c, rn, gm, n_square);
 314   gcry_mpi_release (n_square);
 315   gcry_mpi_release (gm);
 316   gcry_mpi_release (rn);
 317
 318   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
 319                                     sizeof(ciphertext->bits),
 320                                     c);
 321   gcry_mpi_release (c);
 322
 323   return possible_opts;
 324 }
 325
 326
 327 /**
 328  * Decrypt a paillier ciphertext with a private key.
 329  *
 330  * @param private_key Private key to use for decryption.
 331  * @param public_key Public key to use for encryption.
 332  * @param ciphertext Ciphertext to decrypt.
 333  * @param[out] m Decryption of @a ciphertext with @private_key.
 334  */
 335 void
 336 GNUNET_CRYPTO_paillier_decrypt (const struct
 337                                 GNUNET_CRYPTO_PaillierPrivateKey *private_key,
 338                                 const struct
 339                                 GNUNET_CRYPTO_PaillierPublicKey *public_key,
 340                                 const struct
 341                                 GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
 342                                 gcry_mpi_t m)
 343 {
 344   gcry_mpi_t mu;
 345   gcry_mpi_t lambda;
 346   gcry_mpi_t n;
 347   gcry_mpi_t n_square;
 348   gcry_mpi_t c;
 349   gcry_mpi_t cmu;
 350   gcry_mpi_t cmum1;
 351   gcry_mpi_t mod;
 352
 353   GNUNET_CRYPTO_mpi_scan_unsigned (&lambda,
 354                                    private_key->lambda,
 355                                    sizeof(private_key->lambda));
 356   GNUNET_CRYPTO_mpi_scan_unsigned (&mu,
 357                                    private_key->mu,
 358                                    sizeof(private_key->mu));
 359   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 360                                    public_key,
 361                                    sizeof(struct
 362                                           GNUNET_CRYPTO_PaillierPublicKey));
 363   GNUNET_CRYPTO_mpi_scan_unsigned (&c,
 364                                    ciphertext->bits,
 365                                    sizeof(ciphertext->bits));
 366
 367   /* n_square = n * n */
 368   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 369   gcry_mpi_mul (n_square, n, n);
 370
 371   /* cmu = c^lambda mod n^2 */
 372   GNUNET_assert (0 != (cmu = gcry_mpi_new (0)));
 373   gcry_mpi_powm (cmu,
 374                  c,
 375                  lambda,
 376                  n_square);
 377   gcry_mpi_release (n_square);
 378   gcry_mpi_release (lambda);
 379   gcry_mpi_release (c);
 380
 381   /* cmum1 = cmu - 1 */
 382   GNUNET_assert (0 != (cmum1 = gcry_mpi_new (0)));
 383   gcry_mpi_sub_ui (cmum1, cmu, 1);
 384   gcry_mpi_release (cmu);
 385
 386   /* mod = cmum1 / n (mod n) */
 387   GNUNET_assert (0 != (mod = gcry_mpi_new (0)));
 388   gcry_mpi_div (mod, NULL, cmum1, n, 0);
 389   gcry_mpi_release (cmum1);
 390
 391   /* m = mod * mu mod n */
 392   gcry_mpi_mulm (m, mod, mu, n);
 393   gcry_mpi_release (mod);
 394   gcry_mpi_release (mu);
 395   gcry_mpi_release (n);
 396 }
 397
 398
 399 /**
 400  * Compute a ciphertext that represents the sum of the plaintext in @a
 401  * c1 and @a c2.
 402  *
 403  * Note that this operation can only be done a finite number of times
 404  * before an overflow occurs.
 405  *
 406  * @param public_key Public key to use for encryption.
 407  * @param c1 Paillier cipher text.
 408  * @param c2 Paillier cipher text.
 409  * @param[out] result Result of the homomorphic operation.
 410  * @return #GNUNET_OK if the result could be computed,
 411  *         #GNUNET_SYSERR if no more homomorphic operations are remaining.
 412  */
 413 int
 414 GNUNET_CRYPTO_paillier_hom_add (const struct
 415                                 GNUNET_CRYPTO_PaillierPublicKey *public_key,
 416                                 const struct
 417                                 GNUNET_CRYPTO_PaillierCiphertext *c1,
 418                                 const struct
 419                                 GNUNET_CRYPTO_PaillierCiphertext *c2,
 420                                 struct GNUNET_CRYPTO_PaillierCiphertext *result)
 421 {
 422   gcry_mpi_t a;
 423   gcry_mpi_t b;
 424   gcry_mpi_t c;
 425   gcry_mpi_t n;
 426   gcry_mpi_t n_square;
 427   int32_t o1;
 428   int32_t o2;
 429
 430   o1 = (int32_t) ntohl (c1->remaining_ops);
 431   o2 = (int32_t) ntohl (c2->remaining_ops);
 432   if ((0 >= o1) || (0 >= o2))
 433   {
 434     GNUNET_break_op (0);
 435     return GNUNET_SYSERR;
 436   }
 437
 438   GNUNET_CRYPTO_mpi_scan_unsigned (&a,
 439                                    c1->bits,
 440                                    sizeof(c1->bits));
 441   GNUNET_CRYPTO_mpi_scan_unsigned (&b,
 442                                    c2->bits,
 443                                    sizeof(c2->bits));
 444   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 445                                    public_key,
 446                                    sizeof(struct
 447                                           GNUNET_CRYPTO_PaillierPublicKey));
 448
 449   /* n_square = n * n */
 450   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 451   gcry_mpi_mul (n_square, n, n);
 452   gcry_mpi_release (n);
 453
 454   /* c = a * b mod n_square */
 455   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 456   gcry_mpi_mulm (c, a, b, n_square);
 457   gcry_mpi_release (n_square);
 458   gcry_mpi_release (a);
 459   gcry_mpi_release (b);
 460
 461   result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1);
 462   GNUNET_CRYPTO_mpi_print_unsigned (result->bits,
 463                                     sizeof(result->bits),
 464                                     c);
 465   gcry_mpi_release (c);
 466   return ntohl (result->remaining_ops);
 467 }
 468
 469
 470 /**
 471  * Get the number of remaining supported homomorphic operations.
 472  *
 473  * @param c Paillier cipher text.
 474  * @return the number of remaining homomorphic operations
 475  */
 476 int
 477 GNUNET_CRYPTO_paillier_hom_get_remaining (const struct
 478                                           GNUNET_CRYPTO_PaillierCiphertext *c)
 479 {
 480   GNUNET_assert (NULL != c);
 481   return ntohl (c->remaining_ops);
 482 }
 483
 484 /* end of crypto_paillier.c */