2 This file is part of GNUnet.
3 Copyright (C) 2014 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
17 * @file util/crypto_paillier.c
18 * @brief implementation of the paillier crypto system with libgcrypt
19 * @author Florian Dold
20 * @author Christian Fuchs
24 #include "gnunet_util_lib.h"
28 * Create a freshly generated paillier public key.
30 * @param[out] public_key Where to store the public key?
31 * @param[out] private_key Where to store the private key?
34 GNUNET_CRYPTO_paillier_create (struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
35 struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
43 /* Generate two distinct primes. The probability that the loop body
44 is executed more than once is very very low... */
53 gcry_prime_generate (&p,
54 GNUNET_CRYPTO_PAILLIER_BITS / 2,
56 GCRY_STRONG_RANDOM, 0));
58 gcry_prime_generate (&q,
59 GNUNET_CRYPTO_PAILLIER_BITS / 2,
61 GCRY_STRONG_RANDOM, 0));
63 while (0 == gcry_mpi_cmp (p, q));
65 GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
69 GNUNET_CRYPTO_mpi_print_unsigned (public_key,
70 sizeof (struct GNUNET_CRYPTO_PaillierPublicKey),
73 /* compute phi(n) = (p-1)(q-1) */
74 GNUNET_assert (NULL != (phi = gcry_mpi_new (0)));
75 gcry_mpi_sub_ui (p, p, 1);
76 gcry_mpi_sub_ui (q, q, 1);
77 gcry_mpi_mul (phi, p, q);
81 /* lambda equals phi(n) in the simplified key generation */
82 GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda,
83 GNUNET_CRYPTO_PAILLIER_BITS / 8,
85 /* mu = phi^{-1} mod n, as we use g = n + 1 */
86 GNUNET_assert (NULL != (mu = gcry_mpi_new (0)));
87 GNUNET_assert (0 != gcry_mpi_invm (mu,
90 gcry_mpi_release (phi);
92 GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu,
93 GNUNET_CRYPTO_PAILLIER_BITS / 8,
95 gcry_mpi_release (mu);
100 * Encrypt a plaintext with a paillier public key.
102 * @param public_key Public key to use.
103 * @param m Plaintext to encrypt.
104 * @param desired_ops How many homomorphic ops the caller intends to use
105 * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
106 * @return guaranteed number of supported homomorphic operations >= 1,
107 * or desired_ops, in case that is lower,
108 * or -1 if less than one homomorphic operation is possible
111 GNUNET_CRYPTO_paillier_encrypt1 (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
114 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
123 unsigned int highbit;
125 /* determine how many operations we could allow, if the other number
126 has the same length. */
127 GNUNET_assert (NULL != (tmp1 = gcry_mpi_set_ui (NULL, 1)));
128 GNUNET_assert (NULL != (tmp2 = gcry_mpi_set_ui (NULL, 2)));
129 gcry_mpi_mul_2exp (tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
131 /* count number of possible operations
132 this would be nicer with gcry_mpi_get_nbits, however it does not return
133 the BITLENGTH of the given MPI's value, but the bits required
134 to represent the number as MPI. */
135 for (possible_opts = -2; gcry_mpi_cmp (tmp1, m) > 0; possible_opts++)
136 gcry_mpi_div (tmp1, NULL, tmp1, tmp2, 0);
137 gcry_mpi_release (tmp1);
138 gcry_mpi_release (tmp2);
140 if (possible_opts < 1)
142 /* soft-cap by caller */
143 possible_opts = (desired_ops < possible_opts)? desired_ops : possible_opts;
145 ciphertext->remaining_ops = htonl (possible_opts);
147 GNUNET_CRYPTO_mpi_scan_unsigned (&n,
149 sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
150 highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
151 while ( (! gcry_mpi_test_bit (n, highbit)) &&
156 /* invalid public key */
158 gcry_mpi_release (n);
159 return GNUNET_SYSERR;
161 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
162 GNUNET_assert (0 != (r = gcry_mpi_new (0)));
163 GNUNET_assert (0 != (c = gcry_mpi_new (0)));
164 gcry_mpi_mul (n_square, n, n);
166 /* generate r < n (without bias) */
168 gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
170 while (gcry_mpi_cmp (r, n) >= 0);
172 /* c = (n+1)^m mod n^2 */
174 gcry_mpi_add_ui (c, n, 1);
175 /* c = (n+1)^m mod n^2 */
176 gcry_mpi_powm (c, c, m, n_square);
177 /* r <- r^n mod n^2 */
178 gcry_mpi_powm (r, r, n, n_square);
179 /* c <- r*c mod n^2 */
180 gcry_mpi_mulm (c, r, c, n_square);
182 GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
183 sizeof ciphertext->bits,
186 gcry_mpi_release (n_square);
187 gcry_mpi_release (n);
188 gcry_mpi_release (r);
189 gcry_mpi_release (c);
191 return possible_opts;
196 * Encrypt a plaintext with a paillier public key.
198 * @param public_key Public key to use.
199 * @param m Plaintext to encrypt.
200 * @param desired_ops How many homomorphic ops the caller intends to use
201 * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
202 * @return guaranteed number of supported homomorphic operations >= 1,
203 * or desired_ops, in case that is lower,
204 * or -1 if less than one homomorphic operation is possible
207 GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
210 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
221 unsigned int highbit;
223 /* set max_num = 2^{GNUNET_CRYPTO_PAILLIER_BITS}, the largest
224 number we can have as a result */
225 GNUNET_assert (NULL != (max_num = gcry_mpi_set_ui (NULL, 1)));
226 gcry_mpi_mul_2exp (max_num,
228 GNUNET_CRYPTO_PAILLIER_BITS);
230 /* Determine how many operations we could allow, assuming the other
231 number has the same length (or is smaller), by counting the
232 number of possible operations. We essentially divide max_num by
233 2 until the result is no longer larger than 'm', incrementing the
234 maximum number of operations in each round, starting at -2 */
235 for (possible_opts = -2; gcry_mpi_cmp (max_num, m) > 0; possible_opts++)
236 gcry_mpi_div (max_num,
241 gcry_mpi_release (max_num);
243 if (possible_opts < 1)
245 /* Enforce soft-cap by caller */
246 possible_opts = GNUNET_MIN (desired_ops, possible_opts);
247 ciphertext->remaining_ops = htonl (possible_opts);
249 GNUNET_CRYPTO_mpi_scan_unsigned (&n,
251 sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
253 /* check public key for number of bits, bail out if key is all zeros */
254 highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
255 while ( (! gcry_mpi_test_bit (n, highbit)) &&
260 /* invalid public key */
262 gcry_mpi_release (n);
263 return GNUNET_SYSERR;
266 /* generate r < n (without bias) */
267 GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
269 gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
271 while (gcry_mpi_cmp (r, n) >= 0);
274 GNUNET_assert (0 != (g = gcry_mpi_new (0)));
275 gcry_mpi_add_ui (g, n, 1);
278 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
279 gcry_mpi_mul (n_square,
283 /* gm = g^m mod n^2 */
284 GNUNET_assert (0 != (gm = gcry_mpi_new (0)));
285 gcry_mpi_powm (gm, g, m, n_square);
286 gcry_mpi_release (g);
288 /* rn <- r^n mod n^2 */
289 GNUNET_assert (0 != (rn = gcry_mpi_new (0)));
290 gcry_mpi_powm (rn, r, n, n_square);
291 gcry_mpi_release (r);
292 gcry_mpi_release (n);
294 /* c <- rn * gm mod n^2 */
295 GNUNET_assert (0 != (c = gcry_mpi_new (0)));
296 gcry_mpi_mulm (c, rn, gm, n_square);
297 gcry_mpi_release (n_square);
298 gcry_mpi_release (gm);
299 gcry_mpi_release (rn);
301 GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
302 sizeof (ciphertext->bits),
304 gcry_mpi_release (c);
306 return possible_opts;
311 * Decrypt a paillier ciphertext with a private key.
313 * @param private_key Private key to use for decryption.
314 * @param public_key Public key to use for encryption.
315 * @param ciphertext Ciphertext to decrypt.
316 * @param[out] m Decryption of @a ciphertext with @private_key.
319 GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
320 const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
321 const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
333 GNUNET_CRYPTO_mpi_scan_unsigned (&lambda,
335 sizeof (private_key->lambda));
336 GNUNET_CRYPTO_mpi_scan_unsigned (&mu,
338 sizeof (private_key->mu));
339 GNUNET_CRYPTO_mpi_scan_unsigned (&n,
341 sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
342 GNUNET_CRYPTO_mpi_scan_unsigned (&c,
344 sizeof (ciphertext->bits));
346 /* n_square = n * n */
347 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
348 gcry_mpi_mul (n_square, n, n);
350 /* cmu = c^lambda mod n^2 */
351 GNUNET_assert (0 != (cmu = gcry_mpi_new (0)));
356 gcry_mpi_release (n_square);
357 gcry_mpi_release (lambda);
358 gcry_mpi_release (c);
360 /* cmum1 = cmu - 1 */
361 GNUNET_assert (0 != (cmum1 = gcry_mpi_new (0)));
362 gcry_mpi_sub_ui (cmum1, cmu, 1);
363 gcry_mpi_release (cmu);
365 /* mod = cmum1 / n (mod n) */
366 GNUNET_assert (0 != (mod = gcry_mpi_new (0)));
367 gcry_mpi_div (mod, NULL, cmum1, n, 0);
368 gcry_mpi_release (cmum1);
370 /* m = mod * mu mod n */
371 gcry_mpi_mulm (m, mod, mu, n);
372 gcry_mpi_release (mod);
373 gcry_mpi_release (mu);
374 gcry_mpi_release (n);
379 * Compute a ciphertext that represents the sum of the plaintext in @a
382 * Note that this operation can only be done a finite number of times
383 * before an overflow occurs.
385 * @param public_key Public key to use for encryption.
386 * @param c1 Paillier cipher text.
387 * @param c2 Paillier cipher text.
388 * @param[out] result Result of the homomorphic operation.
389 * @return #GNUNET_OK if the result could be computed,
390 * #GNUNET_SYSERR if no more homomorphic operations are remaining.
393 GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
394 const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
395 const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
396 struct GNUNET_CRYPTO_PaillierCiphertext *result)
406 o1 = (int32_t) ntohl (c1->remaining_ops);
407 o2 = (int32_t) ntohl (c2->remaining_ops);
408 if ( (0 >= o1) || (0 >= o2) )
411 return GNUNET_SYSERR;
414 GNUNET_CRYPTO_mpi_scan_unsigned (&a,
417 GNUNET_CRYPTO_mpi_scan_unsigned (&b,
420 GNUNET_CRYPTO_mpi_scan_unsigned (&n,
422 sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
424 /* n_square = n * n */
425 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
426 gcry_mpi_mul (n_square, n, n);
427 gcry_mpi_release (n);
429 /* c = a * b mod n_square */
430 GNUNET_assert (0 != (c = gcry_mpi_new (0)));
431 gcry_mpi_mulm (c, a, b, n_square);
432 gcry_mpi_release (n_square);
433 gcry_mpi_release (a);
434 gcry_mpi_release (b);
436 result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1);
437 GNUNET_CRYPTO_mpi_print_unsigned (result->bits,
438 sizeof (result->bits),
440 gcry_mpi_release (c);
441 return ntohl (result->remaining_ops);
446 * Get the number of remaining supported homomorphic operations.
448 * @param c Paillier cipher text.
449 * @return the number of remaining homomorphic operations
452 GNUNET_CRYPTO_paillier_hom_get_remaining (const struct GNUNET_CRYPTO_PaillierCiphertext *c)
454 GNUNET_assert (NULL != c);
455 return ntohl (c->remaining_ops);
458 /* end of crypto_paillier.c */