+ 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);