plibc: win32 related, socket
[oweals/gnunet.git] / src / util / crypto_paillier.c
index c16706dcb09538a41eeb7579174026c985b5c275..27a9af5de744de3029a0472253074166c42d6802 100644 (file)
@@ -1,21 +1,21 @@
 /*
      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
-     by the Free Software Foundation; either version 3, or (at your
-     option) any later version.
+     GNUnet is free software: you can redistribute it and/or modify it
+     under the terms of the GNU Affero General Public License as published
+     by the Free Software Foundation, either version 3 of the License,
+     or (at your option) any later version.
 
      GNUnet is distributed in the hope that it will be useful, but
      WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-     General Public License for more details.
+     Affero General Public License for more details.
 
-     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.
+     You should have received a copy of the GNU Affero General Public License
+     along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+     SPDX-License-Identifier: AGPL3.0-or-later
  */
 
 /**
  * @param[out] private_key Where to store the private key?
  */
 void
-GNUNET_CRYPTO_paillier_create (struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
-                               struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
+GNUNET_CRYPTO_paillier_create(struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
+                              struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
 {
   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.
-  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));
-  }
-  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)
-  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);
-  gcry_mpi_release (phi);
-  gcry_mpi_release (n);
+  /* 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);
+      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));
+  /* 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);
+  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 +114,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)
@@ -115,69 +128,188 @@ GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *pu
   gcry_mpi_t tmp2;
   unsigned int highbit;
 
-  // 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++)
-    gcry_mpi_div (tmp1, NULL, tmp1, tmp2, 0);
-  gcry_mpi_release (tmp1);
-  gcry_mpi_release (tmp2);
+  /* 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++)
+    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
-  possible_opts = (desired_ops < possible_opts)? desired_ops : possible_opts;
+  /* soft-cap by caller */
+  possible_opts = (desired_ops < possible_opts) ? desired_ops : possible_opts;
 
-  ciphertext->remaining_ops = htonl (possible_opts);
+  ciphertext->remaining_ops = htonl(possible_opts);
 
-  GNUNET_CRYPTO_mpi_scan_unsigned (&n,
-                                   public_key,
-                                   sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
+  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) )
+  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)));
-  gcry_mpi_mul (n_square, n, n);
-
-  // generate r < n (without bias)
-  do {
-    gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
-  }
-  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);
-  // r <- r^n mod n^2
-  gcry_mpi_powm (r, r, n, n_square);
-  // c <- r*c mod n^2
-  gcry_mpi_mulm (c, r, c, n_square);
-
-  GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
-                                    sizeof ciphertext->bits,
-                                    c);
-
-  gcry_mpi_release (n_square);
-  gcry_mpi_release (n);
-  gcry_mpi_release (r);
-  gcry_mpi_release (c);
+    {
+      /* 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)));
+  gcry_mpi_mul(n_square, n, n);
+
+  /* generate r < n (without bias) */
+  do
+    {
+      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 */
+  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 */
+  gcry_mpi_powm(r, r, n, n_square);
+  /* c <- r*c mod n^2 */
+  gcry_mpi_mulm(c, r, c, n_square);
+
+  GNUNET_CRYPTO_mpi_print_unsigned(ciphertext->bits,
+                                   sizeof ciphertext->bits,
+                                   c);
+
+  gcry_mpi_release(n_square);
+  gcry_mpi_release(n);
+  gcry_mpi_release(r);
+  gcry_mpi_release(c);
+
+  return possible_opts;
+}
+
+
+/**
+ * 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;
 }
@@ -192,43 +324,68 @@ GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *pu
  * @param[out] m Decryption of @a ciphertext with @private_key.
  */
 void
-GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
-                                const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
-                                const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
-                                gcry_mpi_t m)
+GNUNET_CRYPTO_paillier_decrypt(const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
+                               const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
+                               const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
+                               gcry_mpi_t m)
 {
   gcry_mpi_t mu;
   gcry_mpi_t lambda;
   gcry_mpi_t n;
   gcry_mpi_t n_square;
   gcry_mpi_t c;
-
-  GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
-
-  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);
-
-  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);
-
-  gcry_mpi_release (mu);
-  gcry_mpi_release (lambda);
-  gcry_mpi_release (n);
-  gcry_mpi_release (n_square);
-  gcry_mpi_release (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);
+
+  /* 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);
+
+  /* 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);
+  gcry_mpi_release(cmum1);
+
+  /* m = mod * mu mod n */
+  gcry_mpi_mulm(m, mod, mu, n);
+  gcry_mpi_release(mod);
+  gcry_mpi_release(mu);
+  gcry_mpi_release(n);
 }
 
 
 /**
- * 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.
@@ -241,40 +398,55 @@ GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *p
  *         #GNUNET_SYSERR if no more homomorphic operations are remaining.
  */
 int
-GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
-                                const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
-                                const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
-                                struct GNUNET_CRYPTO_PaillierCiphertext *result)
+GNUNET_CRYPTO_paillier_hom_add(const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
+                               const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
+                               const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
+                               struct GNUNET_CRYPTO_PaillierCiphertext *result)
 {
   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)
-    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, 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);
-  gcry_mpi_mulm (c, a, b, n_square);
-
-  result->remaining_ops = htonl (((o2 > o1) ? o1 : o2) - 1);
-  GNUNET_CRYPTO_mpi_print_unsigned (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);
+  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_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);
+
+  /* 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(GNUNET_MIN(o1, o2) - 1);
+  GNUNET_CRYPTO_mpi_print_unsigned(result->bits,
+                                   sizeof(result->bits),
+                                   c);
+  gcry_mpi_release(c);
+  return ntohl(result->remaining_ops);
 }
 
 
@@ -285,10 +457,11 @@ GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierPublicKey *pu
  * @return the number of remaining homomorphic operations
  */
 int
-GNUNET_CRYPTO_paillier_hom_get_remaining (const struct GNUNET_CRYPTO_PaillierCiphertext *c)
+GNUNET_CRYPTO_paillier_hom_get_remaining(const struct GNUNET_CRYPTO_PaillierCiphertext *c)
 {
-  GNUNET_assert (NULL != c);
-  return ntohl (c->remaining_ops);
+  GNUNET_assert(NULL != c);
+  return ntohl(c->remaining_ops);
 }
 
 /* end of crypto_paillier.c */
+