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 Affero 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.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
22 * @file util/crypto_paillier.c
23 * @brief implementation of the paillier crypto system with libgcrypt
24 * @author Florian Dold
25 * @author Christian Fuchs
29 #include "gnunet_util_lib.h"
33 * Create a freshly generated paillier public key.
35 * @param[out] public_key Where to store the public key?
36 * @param[out] private_key Where to store the private key?
39 GNUNET_CRYPTO_paillier_create (struct
40 GNUNET_CRYPTO_PaillierPublicKey *public_key,
41 struct GNUNET_CRYPTO_PaillierPrivateKey *
50 /* Generate two distinct primes. The probability that the loop body
51 is executed more than once is very very low... */
61 gcry_prime_generate (&p,
62 GNUNET_CRYPTO_PAILLIER_BITS / 2,
64 GCRY_STRONG_RANDOM, 0));
66 gcry_prime_generate (&q,
67 GNUNET_CRYPTO_PAILLIER_BITS / 2,
69 GCRY_STRONG_RANDOM, 0));
71 while (0 == gcry_mpi_cmp (p, q));
73 GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
77 GNUNET_CRYPTO_mpi_print_unsigned (public_key,
79 GNUNET_CRYPTO_PaillierPublicKey),
82 /* compute phi(n) = (p-1)(q-1) */
83 GNUNET_assert (NULL != (phi = gcry_mpi_new (0)));
84 gcry_mpi_sub_ui (p, p, 1);
85 gcry_mpi_sub_ui (q, q, 1);
86 gcry_mpi_mul (phi, p, q);
90 /* lambda equals phi(n) in the simplified key generation */
91 GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda,
92 GNUNET_CRYPTO_PAILLIER_BITS / 8,
94 /* mu = phi^{-1} mod n, as we use g = n + 1 */
95 GNUNET_assert (NULL != (mu = gcry_mpi_new (0)));
96 GNUNET_assert (0 != gcry_mpi_invm (mu,
99 gcry_mpi_release (phi);
100 gcry_mpi_release (n);
101 GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu,
102 GNUNET_CRYPTO_PAILLIER_BITS / 8,
104 gcry_mpi_release (mu);
109 * Encrypt a plaintext with a paillier public key.
111 * @param public_key Public key to use.
112 * @param m Plaintext to encrypt.
113 * @param desired_ops How many homomorphic ops the caller intends to use
114 * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
115 * @return guaranteed number of supported homomorphic operations >= 1,
116 * or desired_ops, in case that is lower,
117 * or -1 if less than one homomorphic operation is possible
120 GNUNET_CRYPTO_paillier_encrypt1 (const struct
121 GNUNET_CRYPTO_PaillierPublicKey *public_key,
124 struct GNUNET_CRYPTO_PaillierCiphertext *
134 unsigned int highbit;
136 /* determine how many operations we could allow, if the other number
137 has the same length. */
138 GNUNET_assert (NULL != (tmp1 = gcry_mpi_set_ui (NULL, 1)));
139 GNUNET_assert (NULL != (tmp2 = gcry_mpi_set_ui (NULL, 2)));
140 gcry_mpi_mul_2exp (tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
142 /* count number of possible operations
143 this would be nicer with gcry_mpi_get_nbits, however it does not return
144 the BITLENGTH of the given MPI's value, but the bits required
145 to represent the number as MPI. */
146 for (possible_opts = -2; gcry_mpi_cmp (tmp1, m) > 0; possible_opts++)
147 gcry_mpi_div (tmp1, NULL, tmp1, tmp2, 0);
148 gcry_mpi_release (tmp1);
149 gcry_mpi_release (tmp2);
151 if (possible_opts < 1)
153 /* soft-cap by caller */
154 possible_opts = (desired_ops < possible_opts) ? desired_ops : possible_opts;
156 ciphertext->remaining_ops = htonl (possible_opts);
158 GNUNET_CRYPTO_mpi_scan_unsigned (&n,
161 GNUNET_CRYPTO_PaillierPublicKey));
162 highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
163 while ((! gcry_mpi_test_bit (n, highbit)) &&
168 /* invalid public key */
170 gcry_mpi_release (n);
171 return GNUNET_SYSERR;
173 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
174 GNUNET_assert (0 != (r = gcry_mpi_new (0)));
175 GNUNET_assert (0 != (c = gcry_mpi_new (0)));
176 gcry_mpi_mul (n_square, n, n);
178 /* generate r < n (without bias) */
181 gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
183 while (gcry_mpi_cmp (r, n) >= 0);
185 /* c = (n+1)^m mod n^2 */
187 gcry_mpi_add_ui (c, n, 1);
188 /* c = (n+1)^m mod n^2 */
189 gcry_mpi_powm (c, c, m, n_square);
190 /* r <- r^n mod n^2 */
191 gcry_mpi_powm (r, r, n, n_square);
192 /* c <- r*c mod n^2 */
193 gcry_mpi_mulm (c, r, c, n_square);
195 GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
196 sizeof ciphertext->bits,
199 gcry_mpi_release (n_square);
200 gcry_mpi_release (n);
201 gcry_mpi_release (r);
202 gcry_mpi_release (c);
204 return possible_opts;
209 * Encrypt a plaintext with a paillier public key.
211 * @param public_key Public key to use.
212 * @param m Plaintext to encrypt.
213 * @param desired_ops How many homomorphic ops the caller intends to use
214 * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
215 * @return guaranteed number of supported homomorphic operations >= 1,
216 * or desired_ops, in case that is lower,
217 * or -1 if less than one homomorphic operation is possible
220 GNUNET_CRYPTO_paillier_encrypt (const struct
221 GNUNET_CRYPTO_PaillierPublicKey *public_key,
224 struct GNUNET_CRYPTO_PaillierCiphertext *
236 unsigned int highbit;
238 /* set max_num = 2^{GNUNET_CRYPTO_PAILLIER_BITS}, the largest
239 number we can have as a result */
240 GNUNET_assert (NULL != (max_num = gcry_mpi_set_ui (NULL, 1)));
241 gcry_mpi_mul_2exp (max_num,
243 GNUNET_CRYPTO_PAILLIER_BITS);
245 /* Determine how many operations we could allow, assuming the other
246 number has the same length (or is smaller), by counting the
247 number of possible operations. We essentially divide max_num by
248 2 until the result is no longer larger than 'm', incrementing the
249 maximum number of operations in each round, starting at -2 */for (possible_opts = -2; gcry_mpi_cmp (max_num, m) > 0; possible_opts++)
250 gcry_mpi_div (max_num,
255 gcry_mpi_release (max_num);
257 if (possible_opts < 1)
259 /* Enforce soft-cap by caller */
260 possible_opts = GNUNET_MIN (desired_ops, possible_opts);
261 ciphertext->remaining_ops = htonl (possible_opts);
263 GNUNET_CRYPTO_mpi_scan_unsigned (&n,
266 GNUNET_CRYPTO_PaillierPublicKey));
268 /* check public key for number of bits, bail out if key is all zeros */
269 highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
270 while ((! gcry_mpi_test_bit (n, highbit)) &&
275 /* invalid public key */
277 gcry_mpi_release (n);
278 return GNUNET_SYSERR;
281 /* generate r < n (without bias) */
282 GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
285 gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
287 while (gcry_mpi_cmp (r, n) >= 0);
290 GNUNET_assert (0 != (g = gcry_mpi_new (0)));
291 gcry_mpi_add_ui (g, n, 1);
294 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
295 gcry_mpi_mul (n_square,
299 /* gm = g^m mod n^2 */
300 GNUNET_assert (0 != (gm = gcry_mpi_new (0)));
301 gcry_mpi_powm (gm, g, m, n_square);
302 gcry_mpi_release (g);
304 /* rn <- r^n mod n^2 */
305 GNUNET_assert (0 != (rn = gcry_mpi_new (0)));
306 gcry_mpi_powm (rn, r, n, n_square);
307 gcry_mpi_release (r);
308 gcry_mpi_release (n);
310 /* c <- rn * gm mod n^2 */
311 GNUNET_assert (0 != (c = gcry_mpi_new (0)));
312 gcry_mpi_mulm (c, rn, gm, n_square);
313 gcry_mpi_release (n_square);
314 gcry_mpi_release (gm);
315 gcry_mpi_release (rn);
317 GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
318 sizeof(ciphertext->bits),
320 gcry_mpi_release (c);
322 return possible_opts;
327 * Decrypt a paillier ciphertext with a private key.
329 * @param private_key Private key to use for decryption.
330 * @param public_key Public key to use for encryption.
331 * @param ciphertext Ciphertext to decrypt.
332 * @param[out] m Decryption of @a ciphertext with @private_key.
335 GNUNET_CRYPTO_paillier_decrypt (const struct
336 GNUNET_CRYPTO_PaillierPrivateKey *private_key,
338 GNUNET_CRYPTO_PaillierPublicKey *public_key,
340 GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
352 GNUNET_CRYPTO_mpi_scan_unsigned (&lambda,
354 sizeof(private_key->lambda));
355 GNUNET_CRYPTO_mpi_scan_unsigned (&mu,
357 sizeof(private_key->mu));
358 GNUNET_CRYPTO_mpi_scan_unsigned (&n,
361 GNUNET_CRYPTO_PaillierPublicKey));
362 GNUNET_CRYPTO_mpi_scan_unsigned (&c,
364 sizeof(ciphertext->bits));
366 /* n_square = n * n */
367 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
368 gcry_mpi_mul (n_square, n, n);
370 /* cmu = c^lambda mod n^2 */
371 GNUNET_assert (0 != (cmu = gcry_mpi_new (0)));
376 gcry_mpi_release (n_square);
377 gcry_mpi_release (lambda);
378 gcry_mpi_release (c);
380 /* cmum1 = cmu - 1 */
381 GNUNET_assert (0 != (cmum1 = gcry_mpi_new (0)));
382 gcry_mpi_sub_ui (cmum1, cmu, 1);
383 gcry_mpi_release (cmu);
385 /* mod = cmum1 / n (mod n) */
386 GNUNET_assert (0 != (mod = gcry_mpi_new (0)));
387 gcry_mpi_div (mod, NULL, cmum1, n, 0);
388 gcry_mpi_release (cmum1);
390 /* m = mod * mu mod n */
391 gcry_mpi_mulm (m, mod, mu, n);
392 gcry_mpi_release (mod);
393 gcry_mpi_release (mu);
394 gcry_mpi_release (n);
399 * Compute a ciphertext that represents the sum of the plaintext in @a
402 * Note that this operation can only be done a finite number of times
403 * before an overflow occurs.
405 * @param public_key Public key to use for encryption.
406 * @param c1 Paillier cipher text.
407 * @param c2 Paillier cipher text.
408 * @param[out] result Result of the homomorphic operation.
409 * @return #GNUNET_OK if the result could be computed,
410 * #GNUNET_SYSERR if no more homomorphic operations are remaining.
413 GNUNET_CRYPTO_paillier_hom_add (const struct
414 GNUNET_CRYPTO_PaillierPublicKey *public_key,
416 GNUNET_CRYPTO_PaillierCiphertext *c1,
418 GNUNET_CRYPTO_PaillierCiphertext *c2,
419 struct GNUNET_CRYPTO_PaillierCiphertext *result)
429 o1 = (int32_t) ntohl (c1->remaining_ops);
430 o2 = (int32_t) ntohl (c2->remaining_ops);
431 if ((0 >= o1) || (0 >= o2))
434 return GNUNET_SYSERR;
437 GNUNET_CRYPTO_mpi_scan_unsigned (&a,
440 GNUNET_CRYPTO_mpi_scan_unsigned (&b,
443 GNUNET_CRYPTO_mpi_scan_unsigned (&n,
446 GNUNET_CRYPTO_PaillierPublicKey));
448 /* n_square = n * n */
449 GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
450 gcry_mpi_mul (n_square, n, n);
451 gcry_mpi_release (n);
453 /* c = a * b mod n_square */
454 GNUNET_assert (0 != (c = gcry_mpi_new (0)));
455 gcry_mpi_mulm (c, a, b, n_square);
456 gcry_mpi_release (n_square);
457 gcry_mpi_release (a);
458 gcry_mpi_release (b);
460 result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1);
461 GNUNET_CRYPTO_mpi_print_unsigned (result->bits,
462 sizeof(result->bits),
464 gcry_mpi_release (c);
465 return ntohl (result->remaining_ops);
470 * Get the number of remaining supported homomorphic operations.
472 * @param c Paillier cipher text.
473 * @return the number of remaining homomorphic operations
476 GNUNET_CRYPTO_paillier_hom_get_remaining (const struct
477 GNUNET_CRYPTO_PaillierCiphertext *c)
479 GNUNET_assert (NULL != c);
480 return ntohl (c->remaining_ops);
484 /* end of crypto_paillier.c */