From e613b7acfde2427b5ea48f2ac866489f2d9b6589 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 9 Dec 2014 20:57:07 +0000 Subject: -fixing paillier bug, improving testcase --- src/util/crypto_paillier.c | 275 ++++++++++++++++++++++++++++++++-------- src/util/test_crypto_paillier.c | 178 ++++++++++++++++++++------ 2 files changed, 358 insertions(+), 95 deletions(-) (limited to 'src/util') 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, @@ -183,6 +195,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. * @@ -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 */ + diff --git a/src/util/test_crypto_paillier.c b/src/util/test_crypto_paillier.c index cd8c77e5e..750eeece1 100644 --- a/src/util/test_crypto_paillier.c +++ b/src/util/test_crypto_paillier.c @@ -29,7 +29,7 @@ #include -int +static int test_crypto () { gcry_mpi_t plaintext; @@ -38,30 +38,95 @@ test_crypto () struct GNUNET_CRYPTO_PaillierPublicKey public_key; struct GNUNET_CRYPTO_PaillierPrivateKey private_key; - GNUNET_CRYPTO_paillier_create (&public_key, &private_key); - + GNUNET_CRYPTO_paillier_create (&public_key, + &private_key); GNUNET_assert (NULL != (plaintext = gcry_mpi_new (0))); GNUNET_assert (NULL != (plaintext_result = gcry_mpi_new (0))); + gcry_mpi_randomize (plaintext, + GNUNET_CRYPTO_PAILLIER_BITS / 2, + GCRY_WEAK_RANDOM); + + GNUNET_CRYPTO_paillier_encrypt (&public_key, + plaintext, + 0 /* 0 hom ops */, + &ciphertext); + GNUNET_CRYPTO_paillier_decrypt (&private_key, + &public_key, + &ciphertext, + plaintext_result); + + if (0 != gcry_mpi_cmp (plaintext, + plaintext_result)) + { + fprintf (stderr, + "Paillier decryption failed with plaintext of size %u\n", + gcry_mpi_get_nbits (plaintext)); + gcry_log_debugmpi ("\n", + plaintext); + gcry_log_debugmpi ("\n", + plaintext_result); + return 1; + } + return 0; +} - gcry_mpi_randomize (plaintext, GNUNET_CRYPTO_PAILLIER_BITS / 2, GCRY_WEAK_RANDOM); - GNUNET_CRYPTO_paillier_encrypt (&public_key, plaintext, 0, &ciphertext); +static int +test_hom_simple (unsigned int a, + unsigned int b) +{ + gcry_mpi_t m1; + gcry_mpi_t m2; + gcry_mpi_t result; + gcry_mpi_t hom_result; + struct GNUNET_CRYPTO_PaillierCiphertext c1; + struct GNUNET_CRYPTO_PaillierCiphertext c2; + struct GNUNET_CRYPTO_PaillierCiphertext c_result; + struct GNUNET_CRYPTO_PaillierPublicKey public_key; + struct GNUNET_CRYPTO_PaillierPrivateKey private_key; - GNUNET_CRYPTO_paillier_decrypt (&private_key, &public_key, - &ciphertext, plaintext_result); + GNUNET_CRYPTO_paillier_create (&public_key, + &private_key); - if (0 != gcry_mpi_cmp (plaintext, plaintext_result)) + GNUNET_assert (NULL != (m1 = gcry_mpi_new (0))); + GNUNET_assert (NULL != (m2 = gcry_mpi_new (0))); + GNUNET_assert (NULL != (result = gcry_mpi_new (0))); + GNUNET_assert (NULL != (hom_result = gcry_mpi_new (0))); + m1 = gcry_mpi_set_ui (m1, a); + m2 = gcry_mpi_set_ui (m2, b); + gcry_mpi_add (result, + m1, + m2); + GNUNET_CRYPTO_paillier_encrypt (&public_key, + m1, + 2, + &c1); + GNUNET_CRYPTO_paillier_encrypt (&public_key, + m2, + 2, + &c2); + GNUNET_CRYPTO_paillier_hom_add (&public_key, + &c1, + &c2, + &c_result); + GNUNET_CRYPTO_paillier_decrypt (&private_key, + &public_key, + &c_result, + hom_result); + if (0 != gcry_mpi_cmp (result, hom_result)) { - printf ("paillier failed with plaintext of size %u\n", gcry_mpi_get_nbits (plaintext)); - gcry_log_debugmpi("\n", plaintext); - gcry_log_debugmpi("\n", plaintext_result); + fprintf (stderr, + "GNUNET_CRYPTO_paillier failed simple math!\n"); + gcry_log_debugmpi ("got ", hom_result); + gcry_log_debugmpi ("wanted ", result); return 1; } return 0; } -int -test_hom() + +static int +test_hom () { int ret; gcry_mpi_t m1; @@ -73,54 +138,89 @@ test_hom() struct GNUNET_CRYPTO_PaillierCiphertext c_result; struct GNUNET_CRYPTO_PaillierPublicKey public_key; struct GNUNET_CRYPTO_PaillierPrivateKey private_key; - - GNUNET_CRYPTO_paillier_create (&public_key, &private_key); + + GNUNET_CRYPTO_paillier_create (&public_key, + &private_key); GNUNET_assert (NULL != (m1 = gcry_mpi_new (0))); GNUNET_assert (NULL != (m2 = gcry_mpi_new (0))); GNUNET_assert (NULL != (result = gcry_mpi_new (0))); GNUNET_assert (NULL != (hom_result = gcry_mpi_new (0))); - //gcry_mpi_randomize (m1, GNUNET_CRYPTO_PAILLIER_BITS-2, GCRY_WEAK_RANDOM); - m1 = gcry_mpi_set_ui(m1,1); - gcry_mpi_mul_2exp(m1,m1,GNUNET_CRYPTO_PAILLIER_BITS-3); - //gcry_mpi_randomize (m2, GNUNET_CRYPTO_PAILLIER_BITS-2, GCRY_WEAK_RANDOM); - m2 = gcry_mpi_set_ui(m2,1); - gcry_mpi_mul_2exp(m2,m2,GNUNET_CRYPTO_PAILLIER_BITS-3); - gcry_mpi_add(result,m1,m2); - - if (1 != (ret = GNUNET_CRYPTO_paillier_encrypt (&public_key, m1, 2, &c1))){ - printf ("GNUNET_CRYPTO_paillier_encrypt 1 failed, should return 1 allowed operation, got %d!\n", ret); + m1 = gcry_mpi_set_ui (m1, 1); + /* m1 = m1 * 2 ^ (GCPB - 3) */ + gcry_mpi_mul_2exp (m1, + m1, + GNUNET_CRYPTO_PAILLIER_BITS - 3); + m2 = gcry_mpi_set_ui (m2, 15); + /* m1 = m1 * 2 ^ (GCPB / 2) */ + gcry_mpi_mul_2exp (m2, + m2, + GNUNET_CRYPTO_PAILLIER_BITS / 2); + gcry_mpi_add (result, + m1, + m2); + + if (1 != (ret = GNUNET_CRYPTO_paillier_encrypt (&public_key, + m1, + 2, + &c1))) + { + fprintf (stderr, + "GNUNET_CRYPTO_paillier_encrypt 1 failed, should return 1 allowed operation, got %d!\n", + ret); return 1; } - if (1 != (ret = GNUNET_CRYPTO_paillier_encrypt (&public_key, m2, 2, &c2))){ - printf ("GNUNET_CRYPTO_paillier_encrypt 2 failed, should return 1 allowed operation, got %d!\n", ret); + if (2 != (ret = GNUNET_CRYPTO_paillier_encrypt (&public_key, + m2, + 2, + &c2))) + { + fprintf (stderr, + "GNUNET_CRYPTO_paillier_encrypt 2 failed, should return 2 allowed operation, got %d!\n", + ret); return 1; } - if (0 != (ret = GNUNET_CRYPTO_paillier_hom_add (&public_key, &c1,&c2, &c_result))){ - printf ("GNUNET_CRYPTO_paillier_hom_add failed, expected 0 remaining operations, got %d!\n", ret); + if (0 != (ret = GNUNET_CRYPTO_paillier_hom_add (&public_key, + &c1, + &c2, + &c_result))) + { + fprintf (stderr, + "GNUNET_CRYPTO_paillier_hom_add failed, expected 0 remaining operations, got %d!\n", + ret); return 1; } - - GNUNET_CRYPTO_paillier_decrypt (&private_key, &public_key, - &c_result, hom_result); - - gcry_log_debugmpi("\n", hom_result); - gcry_log_debugmpi("\n", result); - if (0 != gcry_mpi_cmp(result, hom_result)){ - printf ("GNUNET_CRYPTO_paillier miscalculated!\n"); + + GNUNET_CRYPTO_paillier_decrypt (&private_key, + &public_key, + &c_result, + hom_result); + + if (0 != gcry_mpi_cmp (result, hom_result)) + { + fprintf (stderr, + "GNUNET_CRYPTO_paillier miscalculated with large numbers!\n"); + gcry_log_debugmpi ("got", hom_result); + gcry_log_debugmpi ("wanted", result); return 1; } - return 0; } int -main (int argc, char *argv[]) +main (int argc, + char *argv[]) { int ret; ret = test_crypto (); + if (0 != ret) + return ret; + ret = test_hom_simple (2,4); + if (0 != ret) + return ret; + ret = test_hom_simple (13,17); if (0 != ret) return ret; ret = test_hom (); -- cgit v1.2.3