-fixing paillier bug, improving testcase

1 files changed, 219 insertions, 56 deletions

diff --git a/src/util/crypto_paillier.c b/src/util/crypto_paillier.c
index c16706dcb..1104aee62 100644
--- a/src/util/crypto_paillier.c
+++ b/src/util/crypto_paillier.c
@@ -41,51 +41,63 @@ GNUNET_CRYPTO_paillier_create (struct GNUNET_CRYPTO_PaillierPublicKey *public_ke
 {
   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_STRONG_RANDOM, 0));
-    GNUNET_assert (0 == gcry_prime_generate (&q, GNUNET_CRYPTO_PAILLIER_BITS / 2, 0, NULL, NULL, NULL,
-                                             GCRY_STRONG_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);
+  /* 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)
+  /* 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);
 }
 
 
@@ -101,7 +113,7 @@ GNUNET_CRYPTO_paillier_create (struct GNUNET_CRYPTO_PaillierPublicKey *public_ke
  *         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)
@@ -163,12 +175,12 @@ GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *pu
   while (gcry_mpi_cmp (r, n) >= 0);
 
   // c = (n+1)^m mod n^2
-  gcry_mpi_add_ui (c, n, 1);
-  gcry_mpi_powm (c, c, m, n_square);
+  gcry_mpi_add_ui (c, n, 1); // c = n + 1
+  gcry_mpi_powm (c, c, m, n_square); // c = (n+1)^m mod n^2
   // r <- r^n mod n^2
-  gcry_mpi_powm (r, r, n, n_square);
+  gcry_mpi_powm (r, r, n, n_square); // r = r^n mod n^2
   // c <- r*c mod n^2
-  gcry_mpi_mulm (c, r, c, n_square);
+  gcry_mpi_mulm (c, r, c, n_square); // c = r*c mod n^2
 
   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
                                     sizeof ciphertext->bits,
@@ -184,6 +196,121 @@ GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *pu
 
 
 /**
+ * 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 (0 != (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.
  *
  * @param private_key Private key to use for decryption.
@@ -202,33 +329,56 @@ GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *p
   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.
@@ -249,31 +399,43 @@ GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierPublicKey *pu
   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)
+  if ( (0 >= o1) || (0 >= o2) )
     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));
 
-  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);
+  /* n_square = n * n */
+  GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
+  gcry_mpi_mul (n_square, n, n);
+  gcry_mpi_release (n);
+
+  /* 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);
 }
 
@@ -292,3 +454,4 @@ GNUNET_CRYPTO_paillier_hom_get_remaining (const struct GNUNET_CRYPTO_PaillierCip
 }
 
 /* end of crypto_paillier.c */
+