crypto_paillier.c File Reference

implementation of the paillier crypto system with libgcrypt More...

#include "platform.h"
#include <gcrypt.h>
#include "gnunet_util_lib.h"

Include dependency graph for crypto_paillier.c:

Go to the source code of this file.

Functions
void	GNUNET_CRYPTO_paillier_create (struct GNUNET_CRYPTO_PaillierPublicKey *public_key, struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
	Create a freshly generated paillier public key. More...
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)
	Encrypt a plaintext with a paillier public key. More...
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)
	Encrypt a plaintext with a paillier public key. More...
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)
	Decrypt a paillier ciphertext with a private key. More...
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)
	Compute a ciphertext that represents the sum of the plaintext in c1 and c2. More...
int	GNUNET_CRYPTO_paillier_hom_get_remaining (const struct GNUNET_CRYPTO_PaillierCiphertext *c)
	Get the number of remaining supported homomorphic operations. More...

Detailed Description

implementation of the paillier crypto system with libgcrypt

Author

Florian Dold

Christian Fuchs

Definition in file crypto_paillier.c.

Function Documentation

GNUNET_CRYPTO_paillier_create()

void GNUNET_CRYPTO_paillier_create	(	struct GNUNET_CRYPTO_PaillierPublicKey *	public_key,
		struct GNUNET_CRYPTO_PaillierPrivateKey *	private_key
	)

Create a freshly generated paillier public key.

Parameters

[out]	public_key	Where to store the public key?
[out]	private_key	Where to store the private key?

Definition at line 39 of file crypto_paillier.c.

References GNUNET_assert, GNUNET_CRYPTO_mpi_print_unsigned(), GNUNET_CRYPTO_PAILLIER_BITS, GNUNET_CRYPTO_PaillierPrivateKey::lambda, GNUNET_CRYPTO_PaillierPrivateKey::mu, p, and q.

Referenced by handle_client_keygen(), and run().

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

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CRYPTO_paillier_encrypt1()

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
	)

Encrypt a plaintext with a paillier public key.

Parameters

	public_key	Public key to use.
	m	Plaintext to encrypt.
	desired_ops	How many homomorphic ops the caller intends to use
[out]	ciphertext	Encrytion of plaintext with public_key.

Returns

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

Definition at line 117 of file crypto_paillier.c.

References GNUNET_CRYPTO_PaillierCiphertext::bits, GNUNET_assert, GNUNET_break_op, GNUNET_CRYPTO_mpi_print_unsigned(), GNUNET_CRYPTO_mpi_scan_unsigned(), GNUNET_CRYPTO_PAILLIER_BITS, GNUNET_SYSERR, and GNUNET_CRYPTO_PaillierCiphertext::remaining_ops.

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

Here is the call graph for this function:

GNUNET_CRYPTO_paillier_encrypt()

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
	)

Encrypt a plaintext with a paillier public key.

Parameters

	public_key	Public key to use.
	m	Plaintext to encrypt.
	desired_ops	How many homomorphic ops the caller intends to use
[out]	ciphertext	Encrytion of plaintext with public_key.

Returns

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

Definition at line 214 of file crypto_paillier.c.

References GNUNET_CRYPTO_PaillierCiphertext::bits, GNUNET_assert, GNUNET_break_op, GNUNET_CRYPTO_mpi_print_unsigned(), GNUNET_CRYPTO_mpi_scan_unsigned(), GNUNET_CRYPTO_PAILLIER_BITS, GNUNET_MIN, GNUNET_SYSERR, and GNUNET_CRYPTO_PaillierCiphertext::remaining_ops.

Referenced by compute_service_response(), and send_alices_cryptodata_message().

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

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CRYPTO_paillier_decrypt()

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
	)

Decrypt a paillier ciphertext with a private key.

Parameters

	private_key	Private key to use for decryption.
	public_key	Public key to use for encryption.
	ciphertext	Ciphertext to decrypt.
[out]	m	Decryption of ciphertext with .

Definition at line 327 of file crypto_paillier.c.

References GNUNET_CRYPTO_PaillierCiphertext::bits, GNUNET_assert, GNUNET_CRYPTO_mpi_scan_unsigned(), GNUNET_CRYPTO_PaillierPrivateKey::lambda, and GNUNET_CRYPTO_PaillierPrivateKey::mu.

Referenced by compute_scalar_product(), and keygen_round2_new_element().

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

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CRYPTO_paillier_hom_add()

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
	)

Compute a ciphertext that represents the sum of the plaintext in c1 and c2.

Compute a ciphertext that represents the sum of the plaintext in x1 and x2.

Note that this operation can only be done a finite number of times before an overflow occurs.

Parameters

	public_key	Public key to use for encryption.
	c1	Paillier cipher text.
	c2	Paillier cipher text.
[out]	result	Result of the homomorphic operation.

Returns

GNUNET_OK if the result could be computed, GNUNET_SYSERR if no more homomorphic operations are remaining.

Definition at line 401 of file crypto_paillier.c.

References GNUNET_CRYPTO_PaillierCiphertext::bits, GNUNET_assert, GNUNET_break_op, GNUNET_CRYPTO_mpi_print_unsigned(), GNUNET_CRYPTO_mpi_scan_unsigned(), GNUNET_MIN, GNUNET_SYSERR, and GNUNET_CRYPTO_PaillierCiphertext::remaining_ops.

Referenced by compute_service_response().

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

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CRYPTO_paillier_hom_get_remaining()

int GNUNET_CRYPTO_paillier_hom_get_remaining

(

const struct GNUNET_CRYPTO_PaillierCiphertext *

c

)

Get the number of remaining supported homomorphic operations.

Parameters

c	Paillier cipher text.

Returns

the number of remaining homomorphic operations

Definition at line 460 of file crypto_paillier.c.

References GNUNET_assert, and GNUNET_CRYPTO_PaillierCiphertext::remaining_ops.

{
  GNUNET_assert(NULL != c);
  return ntohl(c->remaining_ops);
}