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 GNUNET_CRYPTO_PaillierPublicKey *public_key,
40 struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
48 /* Generate two distinct primes. The probability that the loop body
49 is executed more than once is very very low... */
59 gcry_prime_generate(&p,
60 GNUNET_CRYPTO_PAILLIER_BITS / 2,
62 GCRY_STRONG_RANDOM, 0));
64 gcry_prime_generate(&q,
65 GNUNET_CRYPTO_PAILLIER_BITS / 2,
67 GCRY_STRONG_RANDOM, 0));
69 while (0 == gcry_mpi_cmp(p, q));
71 GNUNET_assert(NULL != (n = gcry_mpi_new(0)));
75 GNUNET_CRYPTO_mpi_print_unsigned(public_key,
76 sizeof(struct GNUNET_CRYPTO_PaillierPublicKey),
79 /* compute phi(n) = (p-1)(q-1) */
80 GNUNET_assert(NULL != (phi = gcry_mpi_new(0)));
81 gcry_mpi_sub_ui(p, p, 1);
82 gcry_mpi_sub_ui(q, q, 1);
83 gcry_mpi_mul(phi, p, q);
87 /* lambda equals phi(n) in the simplified key generation */
88 GNUNET_CRYPTO_mpi_print_unsigned(private_key->lambda,
89 GNUNET_CRYPTO_PAILLIER_BITS / 8,
91 /* mu = phi^{-1} mod n, as we use g = n + 1 */
92 GNUNET_assert(NULL != (mu = gcry_mpi_new(0)));
93 GNUNET_assert(0 != gcry_mpi_invm(mu,
96 gcry_mpi_release(phi);
98 GNUNET_CRYPTO_mpi_print_unsigned(private_key->mu,
99 GNUNET_CRYPTO_PAILLIER_BITS / 8,
101 gcry_mpi_release(mu);
106 * Encrypt a plaintext with a paillier public key.
108 * @param public_key Public key to use.
109 * @param m Plaintext to encrypt.
110 * @param desired_ops How many homomorphic ops the caller intends to use
111 * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
112 * @return guaranteed number of supported homomorphic operations >= 1,
113 * or desired_ops, in case that is lower,
114 * or -1 if less than one homomorphic operation is possible
117 GNUNET_CRYPTO_paillier_encrypt1(const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
120 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
129 unsigned int highbit;
131 /* determine how many operations we could allow, if the other number
132 has the same length. */
133 GNUNET_assert(NULL != (tmp1 = gcry_mpi_set_ui(NULL, 1)));
134 GNUNET_assert(NULL != (tmp2 = gcry_mpi_set_ui(NULL, 2)));
135 gcry_mpi_mul_2exp(tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
137 /* count number of possible operations
138 this would be nicer with gcry_mpi_get_nbits, however it does not return
139 the BITLENGTH of the given MPI's value, but the bits required
140 to represent the number as MPI. */
141 for (possible_opts = -2; gcry_mpi_cmp(tmp1, m) > 0; possible_opts++)
142 gcry_mpi_div(tmp1, NULL, tmp1, tmp2, 0);
143 gcry_mpi_release(tmp1);
144 gcry_mpi_release(tmp2);
146 if (possible_opts < 1)
148 /* soft-cap by caller */
149 possible_opts = (desired_ops < possible_opts) ? desired_ops : possible_opts;
151 ciphertext->remaining_ops = htonl(possible_opts);
153 GNUNET_CRYPTO_mpi_scan_unsigned(&n,
155 sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
156 highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
157 while ((!gcry_mpi_test_bit(n, highbit)) &&
162 /* invalid public key */
165 return GNUNET_SYSERR;
167 GNUNET_assert(0 != (n_square = gcry_mpi_new(0)));
168 GNUNET_assert(0 != (r = gcry_mpi_new(0)));
169 GNUNET_assert(0 != (c = gcry_mpi_new(0)));
170 gcry_mpi_mul(n_square, n, n);
172 /* generate r < n (without bias) */
175 gcry_mpi_randomize(r, highbit + 1, GCRY_STRONG_RANDOM);
177 while (gcry_mpi_cmp(r, n) >= 0);
179 /* c = (n+1)^m mod n^2 */
181 gcry_mpi_add_ui(c, n, 1);
182 /* c = (n+1)^m mod n^2 */
183 gcry_mpi_powm(c, c, m, n_square);
184 /* r <- r^n mod n^2 */
185 gcry_mpi_powm(r, r, n, n_square);
186 /* c <- r*c mod n^2 */
187 gcry_mpi_mulm(c, r, c, n_square);
189 GNUNET_CRYPTO_mpi_print_unsigned(ciphertext->bits,
190 sizeof ciphertext->bits,
193 gcry_mpi_release(n_square);
198 return possible_opts;
203 * Encrypt a plaintext with a paillier public key.
205 * @param public_key Public key to use.
206 * @param m Plaintext to encrypt.
207 * @param desired_ops How many homomorphic ops the caller intends to use
208 * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
209 * @return guaranteed number of supported homomorphic operations >= 1,
210 * or desired_ops, in case that is lower,
211 * or -1 if less than one homomorphic operation is possible
214 GNUNET_CRYPTO_paillier_encrypt(const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
217 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
228 unsigned int highbit;
230 /* set max_num = 2^{GNUNET_CRYPTO_PAILLIER_BITS}, the largest
231 number we can have as a result */
232 GNUNET_assert(NULL != (max_num = gcry_mpi_set_ui(NULL, 1)));
233 gcry_mpi_mul_2exp(max_num,
235 GNUNET_CRYPTO_PAILLIER_BITS);
237 /* Determine how many operations we could allow, assuming the other
238 number has the same length (or is smaller), by counting the
239 number of possible operations. We essentially divide max_num by
240 2 until the result is no longer larger than 'm', incrementing the
241 maximum number of operations in each round, starting at -2 */
242 for (possible_opts = -2; gcry_mpi_cmp(max_num, m) > 0; possible_opts++)
243 gcry_mpi_div(max_num,
248 gcry_mpi_release(max_num);
250 if (possible_opts < 1)
252 /* Enforce soft-cap by caller */
253 possible_opts = GNUNET_MIN(desired_ops, possible_opts);
254 ciphertext->remaining_ops = htonl(possible_opts);
256 GNUNET_CRYPTO_mpi_scan_unsigned(&n,
258 sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
260 /* check public key for number of bits, bail out if key is all zeros */
261 highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
262 while ((!gcry_mpi_test_bit(n, highbit)) &&
267 /* invalid public key */
270 return GNUNET_SYSERR;
273 /* generate r < n (without bias) */
274 GNUNET_assert(NULL != (r = gcry_mpi_new(0)));
277 gcry_mpi_randomize(r, highbit + 1, GCRY_STRONG_RANDOM);
279 while (gcry_mpi_cmp(r, n) >= 0);
282 GNUNET_assert(0 != (g = gcry_mpi_new(0)));
283 gcry_mpi_add_ui(g, n, 1);
286 GNUNET_assert(0 != (n_square = gcry_mpi_new(0)));
287 gcry_mpi_mul(n_square,
291 /* gm = g^m mod n^2 */
292 GNUNET_assert(0 != (gm = gcry_mpi_new(0)));
293 gcry_mpi_powm(gm, g, m, n_square);
296 /* rn <- r^n mod n^2 */
297 GNUNET_assert(0 != (rn = gcry_mpi_new(0)));
298 gcry_mpi_powm(rn, r, n, n_square);
302 /* c <- rn * gm mod n^2 */
303 GNUNET_assert(0 != (c = gcry_mpi_new(0)));
304 gcry_mpi_mulm(c, rn, gm, n_square);
305 gcry_mpi_release(n_square);
306 gcry_mpi_release(gm);
307 gcry_mpi_release(rn);
309 GNUNET_CRYPTO_mpi_print_unsigned(ciphertext->bits,
310 sizeof(ciphertext->bits),
314 return possible_opts;
319 * Decrypt a paillier ciphertext with a private key.
321 * @param private_key Private key to use for decryption.
322 * @param public_key Public key to use for encryption.
323 * @param ciphertext Ciphertext to decrypt.
324 * @param[out] m Decryption of @a ciphertext with @private_key.
327 GNUNET_CRYPTO_paillier_decrypt(const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
328 const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
329 const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
341 GNUNET_CRYPTO_mpi_scan_unsigned(&lambda,
343 sizeof(private_key->lambda));
344 GNUNET_CRYPTO_mpi_scan_unsigned(&mu,
346 sizeof(private_key->mu));
347 GNUNET_CRYPTO_mpi_scan_unsigned(&n,
349 sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
350 GNUNET_CRYPTO_mpi_scan_unsigned(&c,
352 sizeof(ciphertext->bits));
354 /* n_square = n * n */
355 GNUNET_assert(0 != (n_square = gcry_mpi_new(0)));
356 gcry_mpi_mul(n_square, n, n);
358 /* cmu = c^lambda mod n^2 */
359 GNUNET_assert(0 != (cmu = gcry_mpi_new(0)));
364 gcry_mpi_release(n_square);
365 gcry_mpi_release(lambda);
368 /* cmum1 = cmu - 1 */
369 GNUNET_assert(0 != (cmum1 = gcry_mpi_new(0)));
370 gcry_mpi_sub_ui(cmum1, cmu, 1);
371 gcry_mpi_release(cmu);
373 /* mod = cmum1 / n (mod n) */
374 GNUNET_assert(0 != (mod = gcry_mpi_new(0)));
375 gcry_mpi_div(mod, NULL, cmum1, n, 0);
376 gcry_mpi_release(cmum1);
378 /* m = mod * mu mod n */
379 gcry_mpi_mulm(m, mod, mu, n);
380 gcry_mpi_release(mod);
381 gcry_mpi_release(mu);
387 * Compute a ciphertext that represents the sum of the plaintext in @a
390 * Note that this operation can only be done a finite number of times
391 * before an overflow occurs.
393 * @param public_key Public key to use for encryption.
394 * @param c1 Paillier cipher text.
395 * @param c2 Paillier cipher text.
396 * @param[out] result Result of the homomorphic operation.
397 * @return #GNUNET_OK if the result could be computed,
398 * #GNUNET_SYSERR if no more homomorphic operations are remaining.
401 GNUNET_CRYPTO_paillier_hom_add(const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
402 const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
403 const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
404 struct GNUNET_CRYPTO_PaillierCiphertext *result)
414 o1 = (int32_t)ntohl(c1->remaining_ops);
415 o2 = (int32_t)ntohl(c2->remaining_ops);
416 if ((0 >= o1) || (0 >= o2))
419 return GNUNET_SYSERR;
422 GNUNET_CRYPTO_mpi_scan_unsigned(&a,
425 GNUNET_CRYPTO_mpi_scan_unsigned(&b,
428 GNUNET_CRYPTO_mpi_scan_unsigned(&n,
430 sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
432 /* n_square = n * n */
433 GNUNET_assert(0 != (n_square = gcry_mpi_new(0)));
434 gcry_mpi_mul(n_square, n, n);
437 /* c = a * b mod n_square */
438 GNUNET_assert(0 != (c = gcry_mpi_new(0)));
439 gcry_mpi_mulm(c, a, b, n_square);
440 gcry_mpi_release(n_square);
444 result->remaining_ops = htonl(GNUNET_MIN(o1, o2) - 1);
445 GNUNET_CRYPTO_mpi_print_unsigned(result->bits,
446 sizeof(result->bits),
449 return ntohl(result->remaining_ops);
454 * Get the number of remaining supported homomorphic operations.
456 * @param c Paillier cipher text.
457 * @return the number of remaining homomorphic operations
460 GNUNET_CRYPTO_paillier_hom_get_remaining(const struct GNUNET_CRYPTO_PaillierCiphertext *c)
462 GNUNET_assert(NULL != c);
463 return ntohl(c->remaining_ops);
466 /* end of crypto_paillier.c */