/*
This file is part of GNUnet.
- (C) 2014 Christian Grothoff (and other contributing authors)
+ Copyright (C) 2014 GNUnet e.V.
GNUnet is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published
You should have received a copy of the GNU General Public License
along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
+ Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
*/
/**
{
gcry_mpi_t p;
gcry_mpi_t q;
-
gcry_mpi_t phi;
+ gcry_mpi_t mu;
gcry_mpi_t n;
- GNUNET_assert (NULL != (phi = gcry_mpi_new (0)));
- GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
-
- p = q = NULL;
-
- // Generate two distinct primes.
- // The probability that the loop body
- // is executed more than once is very low.
+ /* Generate two distinct primes. The probability that the loop body
+ is executed more than once is very very low... */
+ p = NULL;
+ q = NULL;
do {
if (NULL != p)
gcry_mpi_release (p);
if (NULL != q)
gcry_mpi_release (q);
- // generate rsa modulus
- GNUNET_assert (0 == gcry_prime_generate (&p, GNUNET_CRYPTO_PAILLIER_BITS / 2, 0, NULL, NULL, NULL,
- GCRY_WEAK_RANDOM, 0));
- GNUNET_assert (0 == gcry_prime_generate (&q, GNUNET_CRYPTO_PAILLIER_BITS / 2, 0, NULL, NULL, NULL,
- GCRY_WEAK_RANDOM, 0));
+ GNUNET_assert (0 ==
+ gcry_prime_generate (&p,
+ GNUNET_CRYPTO_PAILLIER_BITS / 2,
+ 0, NULL, NULL, NULL,
+ GCRY_STRONG_RANDOM, 0));
+ GNUNET_assert (0 ==
+ gcry_prime_generate (&q,
+ GNUNET_CRYPTO_PAILLIER_BITS / 2,
+ 0, NULL, NULL, NULL,
+ GCRY_STRONG_RANDOM, 0));
}
while (0 == gcry_mpi_cmp (p, q));
- gcry_mpi_mul (n, p, q);
- GNUNET_CRYPTO_mpi_print_unsigned (public_key, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey), n);
-
- // compute phi(n) = (p-1)(q-1)
+ /* n = p * q */
+ GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
+ gcry_mpi_mul (n,
+ p,
+ q);
+ GNUNET_CRYPTO_mpi_print_unsigned (public_key,
+ sizeof (struct GNUNET_CRYPTO_PaillierPublicKey),
+ n);
+
+ /* compute phi(n) = (p-1)(q-1) */
+ GNUNET_assert (NULL != (phi = gcry_mpi_new (0)));
gcry_mpi_sub_ui (p, p, 1);
gcry_mpi_sub_ui (q, q, 1);
gcry_mpi_mul (phi, p, q);
-
- // lambda equals phi(n) in the simplified key generation
- GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda, GNUNET_CRYPTO_PAILLIER_BITS / 8, phi);
-
- // invert phi and abuse the phi mpi to store the result ...
- GNUNET_assert (0 != gcry_mpi_invm (phi, phi, n));
- GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu, GNUNET_CRYPTO_PAILLIER_BITS / 8, phi);
-
gcry_mpi_release (p);
gcry_mpi_release (q);
+
+ /* lambda equals phi(n) in the simplified key generation */
+ GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda,
+ GNUNET_CRYPTO_PAILLIER_BITS / 8,
+ phi);
+ /* mu = phi^{-1} mod n, as we use g = n + 1 */
+ GNUNET_assert (NULL != (mu = gcry_mpi_new (0)));
+ GNUNET_assert (0 != gcry_mpi_invm (mu,
+ phi,
+ n));
gcry_mpi_release (phi);
gcry_mpi_release (n);
+ GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu,
+ GNUNET_CRYPTO_PAILLIER_BITS / 8,
+ mu);
+ gcry_mpi_release (mu);
}
* @param m Plaintext to encrypt.
* @param desired_ops How many homomorphic ops the caller intends to use
* @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
- * @return guaranteed number of supported homomorphic operations >= 1,
+ * @return guaranteed number of supported homomorphic operations >= 1,
* or desired_ops, in case that is lower,
* or -1 if less than one homomorphic operation is possible
*/
int
-GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
+GNUNET_CRYPTO_paillier_encrypt1 (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
const gcry_mpi_t m,
int desired_ops,
struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
gcry_mpi_t n;
gcry_mpi_t tmp1;
gcry_mpi_t tmp2;
+ unsigned int highbit;
- // determine how many operations we could allow, if the other number
- // has the same length.
+ /* determine how many operations we could allow, if the other number
+ has the same length. */
GNUNET_assert (NULL != (tmp1 = gcry_mpi_set_ui (NULL, 1)));
GNUNET_assert (NULL != (tmp2 = gcry_mpi_set_ui (NULL, 2)));
gcry_mpi_mul_2exp (tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
-
- // count number of possible operations
- // this would be nicer with gcry_mpi_get_nbits, however it does not return
- // the BITLENGTH of the given MPI's value, but the bits required
- // to represent the number as MPI.
- for (possible_opts = -2; gcry_mpi_cmp (tmp1, m) > 0; possible_opts++) {
+
+ /* count number of possible operations
+ this would be nicer with gcry_mpi_get_nbits, however it does not return
+ the BITLENGTH of the given MPI's value, but the bits required
+ to represent the number as MPI. */
+ for (possible_opts = -2; gcry_mpi_cmp (tmp1, m) > 0; possible_opts++)
gcry_mpi_div (tmp1, NULL, tmp1, tmp2, 0);
- }
gcry_mpi_release (tmp1);
gcry_mpi_release (tmp2);
-
+
if (possible_opts < 1)
possible_opts = 0;
- //soft-cap by caller
+ /* soft-cap by caller */
possible_opts = (desired_ops < possible_opts)? desired_ops : possible_opts;
-
+
ciphertext->remaining_ops = htonl (possible_opts);
+ GNUNET_CRYPTO_mpi_scan_unsigned (&n,
+ public_key,
+ sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
+ highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
+ while ( (! gcry_mpi_test_bit (n, highbit)) &&
+ (0 != highbit) )
+ highbit--;
+ if (0 == highbit)
+ {
+ /* invalid public key */
+ GNUNET_break_op (0);
+ gcry_mpi_release (n);
+ return GNUNET_SYSERR;
+ }
GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
GNUNET_assert (0 != (r = gcry_mpi_new (0)));
GNUNET_assert (0 != (c = gcry_mpi_new (0)));
-
- GNUNET_CRYPTO_mpi_scan_unsigned (&n, public_key, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
-
gcry_mpi_mul (n_square, n, n);
- // generate r < n
+ /* generate r < n (without bias) */
do {
- gcry_mpi_randomize (r, GNUNET_CRYPTO_PAILLIER_BITS, GCRY_WEAK_RANDOM);
+ gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
}
while (gcry_mpi_cmp (r, n) >= 0);
- // c = (n+1)^m mod n^2
+ /* c = (n+1)^m mod n^2 */
+ /* c = n + 1 */
gcry_mpi_add_ui (c, n, 1);
+ /* c = (n+1)^m mod n^2 */
gcry_mpi_powm (c, c, m, n_square);
- // r <- r^n mod n^2
+ /* r <- r^n mod n^2 */
gcry_mpi_powm (r, r, n, n_square);
- // c <- r*c mod n^2
+ /* c <- r*c mod n^2 */
gcry_mpi_mulm (c, r, c, n_square);
GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
c);
gcry_mpi_release (n_square);
+ gcry_mpi_release (n);
gcry_mpi_release (r);
gcry_mpi_release (c);
}
+/**
+ * Encrypt a plaintext with a paillier public key.
+ *
+ * @param public_key Public key to use.
+ * @param m Plaintext to encrypt.
+ * @param desired_ops How many homomorphic ops the caller intends to use
+ * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
+ * @return guaranteed number of supported homomorphic operations >= 1,
+ * or desired_ops, in case that is lower,
+ * or -1 if less than one homomorphic operation is possible
+ */
+int
+GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
+ const gcry_mpi_t m,
+ int desired_ops,
+ struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
+{
+ int possible_opts;
+ gcry_mpi_t n_square;
+ gcry_mpi_t r;
+ gcry_mpi_t rn;
+ gcry_mpi_t g;
+ gcry_mpi_t gm;
+ gcry_mpi_t c;
+ gcry_mpi_t n;
+ gcry_mpi_t max_num;
+ unsigned int highbit;
+
+ /* set max_num = 2^{GNUNET_CRYPTO_PAILLIER_BITS}, the largest
+ number we can have as a result */
+ GNUNET_assert (NULL != (max_num = gcry_mpi_set_ui (NULL, 1)));
+ gcry_mpi_mul_2exp (max_num,
+ max_num,
+ GNUNET_CRYPTO_PAILLIER_BITS);
+
+ /* Determine how many operations we could allow, assuming the other
+ number has the same length (or is smaller), by counting the
+ number of possible operations. We essentially divide max_num by
+ 2 until the result is no longer larger than 'm', incrementing the
+ maximum number of operations in each round, starting at -2 */
+ for (possible_opts = -2; gcry_mpi_cmp (max_num, m) > 0; possible_opts++)
+ gcry_mpi_div (max_num,
+ NULL,
+ max_num,
+ GCRYMPI_CONST_TWO,
+ 0);
+ gcry_mpi_release (max_num);
+
+ if (possible_opts < 1)
+ possible_opts = 0;
+ /* Enforce soft-cap by caller */
+ possible_opts = GNUNET_MIN (desired_ops, possible_opts);
+ ciphertext->remaining_ops = htonl (possible_opts);
+
+ GNUNET_CRYPTO_mpi_scan_unsigned (&n,
+ public_key,
+ sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
+
+ /* check public key for number of bits, bail out if key is all zeros */
+ highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
+ while ( (! gcry_mpi_test_bit (n, highbit)) &&
+ (0 != highbit) )
+ highbit--;
+ if (0 == highbit)
+ {
+ /* invalid public key */
+ GNUNET_break_op (0);
+ gcry_mpi_release (n);
+ return GNUNET_SYSERR;
+ }
+
+ /* generate r < n (without bias) */
+ GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
+ do {
+ gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
+ }
+ while (gcry_mpi_cmp (r, n) >= 0);
+
+ /* g = n + 1 */
+ GNUNET_assert (0 != (g = gcry_mpi_new (0)));
+ gcry_mpi_add_ui (g, n, 1);
+
+ /* n_square = n^2 */
+ GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
+ gcry_mpi_mul (n_square,
+ n,
+ n);
+
+ /* gm = g^m mod n^2 */
+ GNUNET_assert (0 != (gm = gcry_mpi_new (0)));
+ gcry_mpi_powm (gm, g, m, n_square);
+ gcry_mpi_release (g);
+
+ /* rn <- r^n mod n^2 */
+ GNUNET_assert (0 != (rn = gcry_mpi_new (0)));
+ gcry_mpi_powm (rn, r, n, n_square);
+ gcry_mpi_release (r);
+ gcry_mpi_release (n);
+
+ /* c <- rn * gm mod n^2 */
+ GNUNET_assert (0 != (c = gcry_mpi_new (0)));
+ gcry_mpi_mulm (c, rn, gm, n_square);
+ gcry_mpi_release (n_square);
+ gcry_mpi_release (gm);
+ gcry_mpi_release (rn);
+
+ GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
+ sizeof (ciphertext->bits),
+ c);
+ gcry_mpi_release (c);
+
+ return possible_opts;
+}
+
+
/**
* Decrypt a paillier ciphertext with a private key.
*
gcry_mpi_t n;
gcry_mpi_t n_square;
gcry_mpi_t c;
-
+ gcry_mpi_t cmu;
+ gcry_mpi_t cmum1;
+ gcry_mpi_t mod;
+
+ GNUNET_CRYPTO_mpi_scan_unsigned (&lambda,
+ private_key->lambda,
+ sizeof (private_key->lambda));
+ GNUNET_CRYPTO_mpi_scan_unsigned (&mu,
+ private_key->mu,
+ sizeof (private_key->mu));
+ GNUNET_CRYPTO_mpi_scan_unsigned (&n,
+ public_key,
+ sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
+ GNUNET_CRYPTO_mpi_scan_unsigned (&c,
+ ciphertext->bits,
+ sizeof (ciphertext->bits));
+
+ /* n_square = n * n */
GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
+ gcry_mpi_mul (n_square, n, n);
- GNUNET_CRYPTO_mpi_scan_unsigned (&lambda, private_key->lambda, sizeof private_key->lambda);
- GNUNET_CRYPTO_mpi_scan_unsigned (&mu, private_key->mu, sizeof private_key->mu);
- GNUNET_CRYPTO_mpi_scan_unsigned (&n, public_key, sizeof *public_key);
- GNUNET_CRYPTO_mpi_scan_unsigned (&c, ciphertext->bits, sizeof ciphertext->bits);
+ /* cmu = c^lambda mod n^2 */
+ GNUNET_assert (0 != (cmu = gcry_mpi_new (0)));
+ gcry_mpi_powm (cmu,
+ c,
+ lambda,
+ n_square);
+ gcry_mpi_release (n_square);
+ gcry_mpi_release (lambda);
+ gcry_mpi_release (c);
- gcry_mpi_mul (n_square, n, n);
- // m = c^lambda mod n^2
- gcry_mpi_powm (m, c, lambda, n_square);
- // m = m - 1
- gcry_mpi_sub_ui (m, m, 1);
- // m <- m/n
- gcry_mpi_div (m, NULL, m, n, 0);
- gcry_mpi_mulm (m, m, mu, n);
+ /* cmum1 = cmu - 1 */
+ GNUNET_assert (0 != (cmum1 = gcry_mpi_new (0)));
+ gcry_mpi_sub_ui (cmum1, cmu, 1);
+ gcry_mpi_release (cmu);
+ /* mod = cmum1 / n (mod n) */
+ GNUNET_assert (0 != (mod = gcry_mpi_new (0)));
+ gcry_mpi_div (mod, NULL, cmum1, n, 0);
+
+ /* m = mod * mu mod n */
+ gcry_mpi_mulm (m, mod, mu, n);
gcry_mpi_release (mu);
- gcry_mpi_release (lambda);
gcry_mpi_release (n);
- gcry_mpi_release (n_square);
- gcry_mpi_release (c);
}
/**
- * Compute a ciphertext that represents the sum of the plaintext in @a x1 and @a x2
+ * Compute a ciphertext that represents the sum of the plaintext in @a
+ * c1 and @a c2.
*
* Note that this operation can only be done a finite number of times
* before an overflow occurs.
gcry_mpi_t a;
gcry_mpi_t b;
gcry_mpi_t c;
+ gcry_mpi_t n;
gcry_mpi_t n_square;
int32_t o1;
int32_t o2;
- o1 = ntohl (c1->remaining_ops);
- o2 = ntohl (c2->remaining_ops);
- if (0 >= o1 || 0 >= o2)
+ o1 = (int32_t) ntohl (c1->remaining_ops);
+ o2 = (int32_t) ntohl (c2->remaining_ops);
+ if ( (0 >= o1) || (0 >= o2) )
+ {
+ GNUNET_break_op (0);
return GNUNET_SYSERR;
+ }
- GNUNET_assert (0 != (c = gcry_mpi_new (0)));
+ GNUNET_CRYPTO_mpi_scan_unsigned (&a,
+ c1->bits,
+ sizeof (c1->bits));
+ GNUNET_CRYPTO_mpi_scan_unsigned (&b,
+ c2->bits,
+ sizeof (c2->bits));
+ GNUNET_CRYPTO_mpi_scan_unsigned (&n,
+ public_key,
+ sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
+
+ /* n_square = n * n */
+ GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
+ gcry_mpi_mul (n_square, n, n);
+ gcry_mpi_release (n);
- GNUNET_CRYPTO_mpi_scan_unsigned (&a, c1->bits, sizeof c1->bits);
- GNUNET_CRYPTO_mpi_scan_unsigned (&b, c1->bits, sizeof c2->bits);
- GNUNET_CRYPTO_mpi_scan_unsigned (&n_square, public_key, sizeof *public_key);
- gcry_mpi_mul (n_square, n_square, n_square);
+ /* c = a * b mod n_square */
+ GNUNET_assert (0 != (c = gcry_mpi_new (0)));
gcry_mpi_mulm (c, a, b, n_square);
+ gcry_mpi_release (n_square);
+ gcry_mpi_release (a);
+ gcry_mpi_release (b);
- result->remaining_ops = htonl (((o2 > o1) ? o1 : o2) - 1);
+ result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1);
GNUNET_CRYPTO_mpi_print_unsigned (result->bits,
- sizeof result->bits,
+ sizeof (result->bits),
c);
- gcry_mpi_release (a);
- gcry_mpi_release (b);
gcry_mpi_release (c);
- gcry_mpi_release (n_square);
return ntohl (result->remaining_ops);
}
/**
- * Get the number of remaining supported homomorphic operations.
+ * Get the number of remaining supported homomorphic operations.
*
* @param c Paillier cipher text.
* @return the number of remaining homomorphic operations
}
/* end of crypto_paillier.c */
+