src/util/crypto_paillier.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2014 Christian Grothoff (and other contributing authors)
   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., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, 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
  45   gcry_mpi_t phi;
  46   gcry_mpi_t n;
  47
  48   GNUNET_assert (NULL != (phi = gcry_mpi_new (0)));
  49   GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
  50
  51   p = q = NULL;
  52
  53   // Generate two distinct primes.
  54   // The probability that the loop body
  55   // is executed more than once is very low.
  56   do {
  57     if (NULL != p)
  58       gcry_mpi_release (p);
  59     if (NULL != q)
  60       gcry_mpi_release (q);
  61     // generate rsa modulus
  62     GNUNET_assert (0 == gcry_prime_generate (&p, GNUNET_CRYPTO_PAILLIER_BITS / 2, 0, NULL, NULL, NULL,
  63                                              GCRY_STRONG_RANDOM, 0));
  64     GNUNET_assert (0 == gcry_prime_generate (&q, GNUNET_CRYPTO_PAILLIER_BITS / 2, 0, NULL, NULL, NULL,
  65                                              GCRY_STRONG_RANDOM, 0));
  66   }
  67   while (0 == gcry_mpi_cmp (p, q));
  68   gcry_mpi_mul (n, p, 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   gcry_mpi_sub_ui (p, p, 1);
  75   gcry_mpi_sub_ui (q, q, 1);
  76   gcry_mpi_mul (phi, p, q);
  77
  78   // lambda equals phi(n) in the simplified key generation
  79   GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda, GNUNET_CRYPTO_PAILLIER_BITS / 8, phi);
  80
  81   // invert phi and abuse the phi mpi to store the result ...
  82   GNUNET_assert (0 != gcry_mpi_invm (phi, phi, n));
  83   GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu, GNUNET_CRYPTO_PAILLIER_BITS / 8, phi);
  84
  85   gcry_mpi_release (p);
  86   gcry_mpi_release (q);
  87   gcry_mpi_release (phi);
  88   gcry_mpi_release (n);
  89 }
  90
  91
  92 /**
  93  * Encrypt a plaintext with a paillier public key.
  94  *
  95  * @param public_key Public key to use.
  96  * @param m Plaintext to encrypt.
  97  * @param desired_ops How many homomorphic ops the caller intends to use
  98  * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
  99  * @return guaranteed number of supported homomorphic operations >= 1,
 100  *         or desired_ops, in case that is lower,
 101  *         or -1 if less than one homomorphic operation is possible
 102  */
 103 int
 104 GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 105                                 const gcry_mpi_t m,
 106                                 int desired_ops,
 107                                 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
 108 {
 109   int possible_opts;
 110   gcry_mpi_t n_square;
 111   gcry_mpi_t r;
 112   gcry_mpi_t c;
 113   gcry_mpi_t n;
 114   gcry_mpi_t tmp1;
 115   gcry_mpi_t tmp2;
 116   unsigned int highbit;
 117
 118   // determine how many operations we could allow, if the other number
 119   // has the same length.
 120   GNUNET_assert (NULL != (tmp1 = gcry_mpi_set_ui (NULL, 1)));
 121   GNUNET_assert (NULL != (tmp2 = gcry_mpi_set_ui (NULL, 2)));
 122   gcry_mpi_mul_2exp (tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
 123
 124   // count number of possible operations
 125   // this would be nicer with gcry_mpi_get_nbits, however it does not return
 126   // the BITLENGTH of the given MPI's value, but the bits required
 127   // to represent the number as MPI.
 128   for (possible_opts = -2; gcry_mpi_cmp (tmp1, m) > 0; possible_opts++)
 129     gcry_mpi_div (tmp1, NULL, tmp1, tmp2, 0);
 130   gcry_mpi_release (tmp1);
 131   gcry_mpi_release (tmp2);
 132
 133   if (possible_opts < 1)
 134     possible_opts = 0;
 135   //soft-cap by caller
 136   possible_opts = (desired_ops < possible_opts)? desired_ops : possible_opts;
 137
 138   ciphertext->remaining_ops = htonl (possible_opts);
 139
 140   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
 141                                    public_key,
 142                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 143   highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
 144   while ( (! gcry_mpi_test_bit (n, highbit)) &&
 145           (0 != highbit) )
 146     highbit--;
 147   if (0 == highbit)
 148   {
 149     /* invalid public key */
 150     GNUNET_break_op (0);
 151     gcry_mpi_release (n);
 152     return GNUNET_SYSERR;
 153   }
 154   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 155   GNUNET_assert (0 != (r = gcry_mpi_new (0)));
 156   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 157   gcry_mpi_mul (n_square, n, n);
 158
 159   // generate r < n (without bias)
 160   do {
 161     gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
 162   }
 163   while (gcry_mpi_cmp (r, n) >= 0);
 164
 165   // c = (n+1)^m mod n^2
 166   gcry_mpi_add_ui (c, n, 1);
 167   gcry_mpi_powm (c, c, m, n_square);
 168   // r <- r^n mod n^2
 169   gcry_mpi_powm (r, r, n, n_square);
 170   // c <- r*c mod n^2
 171   gcry_mpi_mulm (c, r, c, n_square);
 172
 173   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
 174                                     sizeof ciphertext->bits,
 175                                     c);
 176
 177   gcry_mpi_release (n_square);
 178   gcry_mpi_release (n);
 179   gcry_mpi_release (r);
 180   gcry_mpi_release (c);
 181
 182   return possible_opts;
 183 }
 184
 185
 186 /**
 187  * Decrypt a paillier ciphertext with a private key.
 188  *
 189  * @param private_key Private key to use for decryption.
 190  * @param public_key Public key to use for encryption.
 191  * @param ciphertext Ciphertext to decrypt.
 192  * @param[out] m Decryption of @a ciphertext with @private_key.
 193  */
 194 void
 195 GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
 196                                 const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 197                                 const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
 198                                 gcry_mpi_t m)
 199 {
 200   gcry_mpi_t mu;
 201   gcry_mpi_t lambda;
 202   gcry_mpi_t n;
 203   gcry_mpi_t n_square;
 204   gcry_mpi_t c;
 205
 206   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 207
 208   GNUNET_CRYPTO_mpi_scan_unsigned (&lambda, private_key->lambda, sizeof private_key->lambda);
 209   GNUNET_CRYPTO_mpi_scan_unsigned (&mu, private_key->mu, sizeof private_key->mu);
 210   GNUNET_CRYPTO_mpi_scan_unsigned (&n, public_key, sizeof *public_key);
 211   GNUNET_CRYPTO_mpi_scan_unsigned (&c, ciphertext->bits, sizeof ciphertext->bits);
 212
 213   gcry_mpi_mul (n_square, n, n);
 214   // m = c^lambda mod n^2
 215   gcry_mpi_powm (m, c, lambda, n_square);
 216   // m = m - 1
 217   gcry_mpi_sub_ui (m, m, 1);
 218   // m <- m/n
 219   gcry_mpi_div (m, NULL, m, n, 0);
 220   gcry_mpi_mulm (m, m, mu, n);
 221
 222   gcry_mpi_release (mu);
 223   gcry_mpi_release (lambda);
 224   gcry_mpi_release (n);
 225   gcry_mpi_release (n_square);
 226   gcry_mpi_release (c);
 227 }
 228
 229
 230 /**
 231  * Compute a ciphertext that represents the sum of the plaintext in @a x1 and @a x2
 232  *
 233  * Note that this operation can only be done a finite number of times
 234  * before an overflow occurs.
 235  *
 236  * @param public_key Public key to use for encryption.
 237  * @param c1 Paillier cipher text.
 238  * @param c2 Paillier cipher text.
 239  * @param[out] result Result of the homomorphic operation.
 240  * @return #GNUNET_OK if the result could be computed,
 241  *         #GNUNET_SYSERR if no more homomorphic operations are remaining.
 242  */
 243 int
 244 GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 245                                 const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
 246                                 const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
 247                                 struct GNUNET_CRYPTO_PaillierCiphertext *result)
 248 {
 249   gcry_mpi_t a;
 250   gcry_mpi_t b;
 251   gcry_mpi_t c;
 252   gcry_mpi_t n_square;
 253   int32_t o1;
 254   int32_t o2;
 255
 256   o1 = ntohl (c1->remaining_ops);
 257   o2 = ntohl (c2->remaining_ops);
 258   if (0 >= o1 || 0 >= o2)
 259     return GNUNET_SYSERR;
 260
 261   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 262
 263   GNUNET_CRYPTO_mpi_scan_unsigned (&a, c1->bits, sizeof c1->bits);
 264   GNUNET_CRYPTO_mpi_scan_unsigned (&b, c1->bits, sizeof c2->bits);
 265   GNUNET_CRYPTO_mpi_scan_unsigned (&n_square, public_key, sizeof *public_key);
 266   gcry_mpi_mul (n_square, n_square, n_square);
 267   gcry_mpi_mulm (c, a, b, n_square);
 268
 269   result->remaining_ops = htonl (((o2 > o1) ? o1 : o2) - 1);
 270   GNUNET_CRYPTO_mpi_print_unsigned (result->bits,
 271                                     sizeof result->bits,
 272                                     c);
 273   gcry_mpi_release (a);
 274   gcry_mpi_release (b);
 275   gcry_mpi_release (c);
 276   gcry_mpi_release (n_square);
 277   return ntohl (result->remaining_ops);
 278 }
 279
 280
 281 /**
 282  * Get the number of remaining supported homomorphic operations.
 283  *
 284  * @param c Paillier cipher text.
 285  * @return the number of remaining homomorphic operations
 286  */
 287 int
 288 GNUNET_CRYPTO_paillier_hom_get_remaining (const struct GNUNET_CRYPTO_PaillierCiphertext *c)
 289 {
 290   GNUNET_assert (NULL != c);
 291   return ntohl (c->remaining_ops);
 292 }
 293
 294 /* end of crypto_paillier.c */