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