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 (GNUNET_CRYPTO_PAILLIER_BITS)));
  49   GNUNET_assert (NULL != (n = gcry_mpi_new (GNUNET_CRYPTO_PAILLIER_BITS)));
  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_WEAK_RANDOM, 0));
  64     GNUNET_assert (0 == gcry_prime_generate (&q, GNUNET_CRYPTO_PAILLIER_BITS / 2, 0, NULL, NULL, NULL,
  65                                              GCRY_WEAK_RANDOM, 0));
  66   } while (0 == gcry_mpi_cmp (p, q));
  67   gcry_mpi_mul (n, p, q);
  68   GNUNET_CRYPTO_mpi_print_unsigned (public_key, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey), n);
  69
  70   // compute phi(n) = (p-1)(q-1)
  71   gcry_mpi_sub_ui (p, p, 1);
  72   gcry_mpi_sub_ui (q, q, 1);
  73   gcry_mpi_mul (phi, p, q);
  74
  75   // lambda equals phi(n) in the simplified key generation
  76   GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda, GNUNET_CRYPTO_PAILLIER_BITS / 8, phi);
  77
  78   // invert phi and abuse the phi mpi to store the result ...
  79   GNUNET_assert (0 != gcry_mpi_invm (phi, phi, n));
  80   GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu, GNUNET_CRYPTO_PAILLIER_BITS / 8, phi);
  81
  82   gcry_mpi_release (p);
  83   gcry_mpi_release (q);
  84   gcry_mpi_release (phi);
  85   gcry_mpi_release (n);
  86 }
  87
  88
  89 /**
  90  * Encrypt a plaintext with a paillier public key.
  91  *
  92  * @param public_key Public key to use.
  93  * @param plaintext Plaintext to encrypt.
  94  * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
  95  */
  96 void
  97 GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
  98                                 const struct GNUNET_CRYPTO_PaillierPlaintext *plaintext,
  99                                 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
 100 {
 101   gcry_mpi_t n_square;
 102   gcry_mpi_t r;
 103   gcry_mpi_t g;
 104   gcry_mpi_t c;
 105
 106   gcry_mpi_t n;
 107   gcry_mpi_t m;
 108
 109
 110   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 111   GNUNET_assert (0 != (r = gcry_mpi_new (0)));
 112   GNUNET_assert (0 != (g = gcry_mpi_new (0)));
 113   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
 114
 115   GNUNET_CRYPTO_mpi_scan_unsigned (&m, plaintext, sizeof (struct GNUNET_CRYPTO_PaillierPlaintext));
 116   GNUNET_CRYPTO_mpi_scan_unsigned (&n, public_key, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 117
 118   gcry_mpi_mul (n_square, n, n);
 119
 120   // generate r < n
 121   do
 122   {
 123     gcry_mpi_randomize (r, GNUNET_CRYPTO_PAILLIER_BITS, GCRY_WEAK_RANDOM);
 124   }
 125   while (gcry_mpi_cmp (r, n) >= 0);
 126
 127   // c = (n+1)^m mod n^2
 128   gcry_mpi_add_ui (c, n, 1);
 129   gcry_mpi_powm (c, c, m, n_square);
 130   // r <- r^n mod n^2
 131   gcry_mpi_powm (r, r, n, n_square);
 132   // c <- r*c mod n^2
 133   gcry_mpi_mulm (c, r, c, n_square);
 134
 135   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext, sizeof *ciphertext, c);
 136
 137   gcry_mpi_release (n_square);
 138   gcry_mpi_release (r);
 139   gcry_mpi_release (m);
 140   gcry_mpi_release (c);
 141 }
 142
 143
 144 /**
 145  * Decrypt a paillier ciphertext with a private key.
 146  *
 147  * @param private_key Private key to use for decryption.
 148  * @param public_key Public key to use for decryption.
 149  * @param ciphertext Ciphertext to decrypt.
 150  * @param[out] plaintext Decryption of @a ciphertext with @private_key.
 151  */
 152 void
 153 GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
 154                                 const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
 155                                 const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
 156                                 struct GNUNET_CRYPTO_PaillierPlaintext *plaintext)
 157 {
 158   gcry_mpi_t m;
 159   gcry_mpi_t mu;
 160   gcry_mpi_t lambda;
 161   gcry_mpi_t n;
 162   gcry_mpi_t n_square;
 163   gcry_mpi_t c;
 164
 165   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
 166   GNUNET_assert (0 != (m = gcry_mpi_new (0)));
 167
 168   GNUNET_CRYPTO_mpi_scan_unsigned (&lambda, private_key->lambda, sizeof private_key->lambda);
 169   GNUNET_CRYPTO_mpi_scan_unsigned (&mu, private_key->mu, sizeof private_key->mu);
 170   GNUNET_CRYPTO_mpi_scan_unsigned (&n, public_key, sizeof *public_key);
 171   GNUNET_CRYPTO_mpi_scan_unsigned (&c, ciphertext, sizeof *ciphertext);
 172
 173   gcry_mpi_mul (n_square, n, n);
 174   // m = c^lambda mod n^2
 175   gcry_mpi_powm (m, c, lambda, n_square);
 176   // m = m - 1
 177   gcry_mpi_sub_ui (m, m, 1);
 178   // m <- m/n
 179   gcry_mpi_div (m, NULL, m, n, 0);
 180   gcry_mpi_mulm (m, m, mu, n);
 181
 182   GNUNET_CRYPTO_mpi_print_unsigned (plaintext, sizeof *plaintext, m);
 183
 184   gcry_mpi_release (m);
 185   gcry_mpi_release (mu);
 186   gcry_mpi_release (lambda);
 187   gcry_mpi_release (n);
 188   gcry_mpi_release (n_square);
 189   gcry_mpi_release (c);
 190 }
 191
 192
 193 /**
 194  * Compute a ciphertext that represents the sum of the plaintext in @a x1 and @a x2
 195  *
 196  * Note that this operation can only be done a finite number of times
 197  * before an overflow occurs.
 198  *
 199  * @param x1 Paillier cipher text.
 200  * @param x2 Paillier cipher text.
 201  * @param[out] result Result of the homomorphic operation.
 202  * @return #GNUNET_OK if the result could be computed,
 203  *         #GNUNET_SYSERR if no more homomorphic operations are remaining.
 204  */
 205 int
 206 GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierCiphertext *x1,
 207                                 const struct GNUNET_CRYPTO_PaillierCiphertext *x2,
 208                                 const struct GNUNET_CRYPTO_PaillierCiphertext *result)
 209 {
 210   // not implemented yet
 211   GNUNET_assert (0);
 212   return GNUNET_SYSERR;
 213 }
 214
 215
 216 /* end of crypto_paillier.c */