/*
     This file is part of GNUnet.
     Copyright (C) 2014 GNUnet e.V.

     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
     Affero General Public License for more details.

     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
 */

/**
 * @file util/crypto_paillier.c
 * @brief implementation of the paillier crypto system with libgcrypt
 * @author Florian Dold
 * @author Christian Fuchs
 */
#include "platform.h"
#include <gcrypt.h>
#include "gnunet_util_lib.h"


/**
 * Create a freshly generated paillier public key.
 *
 * @param[out] public_key Where to store the public key?
 * @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)
{
  gcry_mpi_t p;
  gcry_mpi_t q;
  gcry_mpi_t phi;
  gcry_mpi_t mu;
  gcry_mpi_t 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);
}


/**
 * 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_encrypt1(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 c;
  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. */
  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;

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


/**
 * Decrypt a paillier ciphertext with a private key.
 *
 * @param private_key Private key to use for decryption.
 * @param public_key Public key to use for encryption.
 * @param ciphertext Ciphertext to decrypt.
 * @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)
{
  gcry_mpi_t mu;
  gcry_mpi_t lambda;
  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);

  /* 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
 * c1 and @a c2.
 *
 * Note that this operation can only be done a finite number of times
 * before an overflow occurs.
 *
 * @param public_key Public key to use for encryption.
 * @param c1 Paillier cipher text.
 * @param c2 Paillier cipher text.
 * @param[out] result Result of the homomorphic operation.
 * @return #GNUNET_OK if the result could be computed,
 *         #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)
{
  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 = (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);
}


/**
 * Get the number of remaining supported homomorphic operations.
 *
 * @param c Paillier cipher text.
 * @return the number of remaining homomorphic operations
 */
int
GNUNET_CRYPTO_paillier_hom_get_remaining(const struct GNUNET_CRYPTO_PaillierCiphertext *c)
{
  GNUNET_assert(NULL != c);
  return ntohl(c->remaining_ops);
}

/* end of crypto_paillier.c */