diff options
Diffstat (limited to 'src/util/crypto_paillier.c')
-rw-r--r-- | src/util/crypto_paillier.c | 484 |
1 files changed, 0 insertions, 484 deletions
diff --git a/src/util/crypto_paillier.c b/src/util/crypto_paillier.c deleted file mode 100644 index 97dfad630..000000000 --- a/src/util/crypto_paillier.c +++ /dev/null | |||
@@ -1,484 +0,0 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2014 GNUnet e.V. | ||
4 | |||
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. | ||
9 | |||
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. | ||
14 | |||
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/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @file util/crypto_paillier.c | ||
23 | * @brief implementation of the paillier crypto system with libgcrypt | ||
24 | * @author Florian Dold | ||
25 | * @author Christian Fuchs | ||
26 | */ | ||
27 | #include "platform.h" | ||
28 | #include <gcrypt.h> | ||
29 | #include "gnunet_util_lib.h" | ||
30 | |||
31 | |||
32 | /** | ||
33 | * Create a freshly generated paillier public key. | ||
34 | * | ||
35 | * @param[out] public_key Where to store the public key? | ||
36 | * @param[out] private_key Where to store the private key? | ||
37 | */ | ||
38 | void | ||
39 | GNUNET_CRYPTO_paillier_create (struct | ||
40 | GNUNET_CRYPTO_PaillierPublicKey *public_key, | ||
41 | struct GNUNET_CRYPTO_PaillierPrivateKey * | ||
42 | private_key) | ||
43 | { | ||
44 | gcry_mpi_t p; | ||
45 | gcry_mpi_t q; | ||
46 | gcry_mpi_t phi; | ||
47 | gcry_mpi_t mu; | ||
48 | gcry_mpi_t n; | ||
49 | |||
50 | /* Generate two distinct primes. The probability that the loop body | ||
51 | is executed more than once is very very low... */ | ||
52 | p = NULL; | ||
53 | q = NULL; | ||
54 | do | ||
55 | { | ||
56 | if (NULL != p) | ||
57 | gcry_mpi_release (p); | ||
58 | if (NULL != q) | ||
59 | gcry_mpi_release (q); | ||
60 | GNUNET_assert (0 == | ||
61 | gcry_prime_generate (&p, | ||
62 | GNUNET_CRYPTO_PAILLIER_BITS / 2, | ||
63 | 0, NULL, NULL, NULL, | ||
64 | GCRY_STRONG_RANDOM, 0)); | ||
65 | GNUNET_assert (0 == | ||
66 | gcry_prime_generate (&q, | ||
67 | GNUNET_CRYPTO_PAILLIER_BITS / 2, | ||
68 | 0, NULL, NULL, NULL, | ||
69 | GCRY_STRONG_RANDOM, 0)); | ||
70 | } | ||
71 | while (0 == gcry_mpi_cmp (p, q)); | ||
72 | /* n = p * q */ | ||
73 | GNUNET_assert (NULL != (n = gcry_mpi_new (0))); | ||
74 | gcry_mpi_mul (n, | ||
75 | p, | ||
76 | q); | ||
77 | GNUNET_CRYPTO_mpi_print_unsigned (public_key, | ||
78 | sizeof(struct | ||
79 | GNUNET_CRYPTO_PaillierPublicKey), | ||
80 | n); | ||
81 | |||
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); | ||
87 | gcry_mpi_release (p); | ||
88 | gcry_mpi_release (q); | ||
89 | |||
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, | ||
93 | phi); | ||
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, | ||
97 | phi, | ||
98 | n)); | ||
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, | ||
103 | mu); | ||
104 | gcry_mpi_release (mu); | ||
105 | } | ||
106 | |||
107 | |||
108 | /** | ||
109 | * Encrypt a plaintext with a paillier public key. | ||
110 | * | ||
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 Encryption 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 | ||
118 | */ | ||
119 | int | ||
120 | GNUNET_CRYPTO_paillier_encrypt1 (const struct | ||
121 | GNUNET_CRYPTO_PaillierPublicKey *public_key, | ||
122 | const gcry_mpi_t m, | ||
123 | int desired_ops, | ||
124 | struct GNUNET_CRYPTO_PaillierCiphertext * | ||
125 | ciphertext) | ||
126 | { | ||
127 | int possible_opts; | ||
128 | gcry_mpi_t n_square; | ||
129 | gcry_mpi_t r; | ||
130 | gcry_mpi_t c; | ||
131 | gcry_mpi_t n; | ||
132 | gcry_mpi_t tmp1; | ||
133 | gcry_mpi_t tmp2; | ||
134 | unsigned int highbit; | ||
135 | |||
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); | ||
141 | |||
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); | ||
150 | |||
151 | if (possible_opts < 1) | ||
152 | possible_opts = 0; | ||
153 | /* soft-cap by caller */ | ||
154 | possible_opts = (desired_ops < possible_opts) ? desired_ops : possible_opts; | ||
155 | |||
156 | ciphertext->remaining_ops = htonl (possible_opts); | ||
157 | |||
158 | GNUNET_CRYPTO_mpi_scan_unsigned (&n, | ||
159 | public_key, | ||
160 | sizeof(struct | ||
161 | GNUNET_CRYPTO_PaillierPublicKey)); | ||
162 | highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1; | ||
163 | while ((! gcry_mpi_test_bit (n, highbit)) && | ||
164 | (0 != highbit)) | ||
165 | highbit--; | ||
166 | if (0 == highbit) | ||
167 | { | ||
168 | /* invalid public key */ | ||
169 | GNUNET_break_op (0); | ||
170 | gcry_mpi_release (n); | ||
171 | return GNUNET_SYSERR; | ||
172 | } | ||
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); | ||
177 | |||
178 | /* generate r < n (without bias) */ | ||
179 | do | ||
180 | { | ||
181 | gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM); | ||
182 | } | ||
183 | while (gcry_mpi_cmp (r, n) >= 0); | ||
184 | |||
185 | /* c = (n+1)^m mod n^2 */ | ||
186 | /* c = n + 1 */ | ||
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); | ||
194 | |||
195 | GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits, | ||
196 | sizeof ciphertext->bits, | ||
197 | c); | ||
198 | |||
199 | gcry_mpi_release (n_square); | ||
200 | gcry_mpi_release (n); | ||
201 | gcry_mpi_release (r); | ||
202 | gcry_mpi_release (c); | ||
203 | |||
204 | return possible_opts; | ||
205 | } | ||
206 | |||
207 | |||
208 | /** | ||
209 | * Encrypt a plaintext with a paillier public key. | ||
210 | * | ||
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 Encryption 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 | ||
218 | */ | ||
219 | int | ||
220 | GNUNET_CRYPTO_paillier_encrypt (const struct | ||
221 | GNUNET_CRYPTO_PaillierPublicKey *public_key, | ||
222 | const gcry_mpi_t m, | ||
223 | int desired_ops, | ||
224 | struct GNUNET_CRYPTO_PaillierCiphertext * | ||
225 | ciphertext) | ||
226 | { | ||
227 | int possible_opts; | ||
228 | gcry_mpi_t n_square; | ||
229 | gcry_mpi_t r; | ||
230 | gcry_mpi_t rn; | ||
231 | gcry_mpi_t g; | ||
232 | gcry_mpi_t gm; | ||
233 | gcry_mpi_t c; | ||
234 | gcry_mpi_t n; | ||
235 | gcry_mpi_t max_num; | ||
236 | unsigned int highbit; | ||
237 | |||
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, | ||
242 | max_num, | ||
243 | GNUNET_CRYPTO_PAILLIER_BITS); | ||
244 | |||
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, | ||
251 | NULL, | ||
252 | max_num, | ||
253 | GCRYMPI_CONST_TWO, | ||
254 | 0); | ||
255 | gcry_mpi_release (max_num); | ||
256 | |||
257 | if (possible_opts < 1) | ||
258 | possible_opts = 0; | ||
259 | /* Enforce soft-cap by caller */ | ||
260 | possible_opts = GNUNET_MIN (desired_ops, possible_opts); | ||
261 | ciphertext->remaining_ops = htonl (possible_opts); | ||
262 | |||
263 | GNUNET_CRYPTO_mpi_scan_unsigned (&n, | ||
264 | public_key, | ||
265 | sizeof(struct | ||
266 | GNUNET_CRYPTO_PaillierPublicKey)); | ||
267 | |||
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)) && | ||
271 | (0 != highbit)) | ||
272 | highbit--; | ||
273 | if (0 == highbit) | ||
274 | { | ||
275 | /* invalid public key */ | ||
276 | GNUNET_break_op (0); | ||
277 | gcry_mpi_release (n); | ||
278 | return GNUNET_SYSERR; | ||
279 | } | ||
280 | |||
281 | /* generate r < n (without bias) */ | ||
282 | GNUNET_assert (NULL != (r = gcry_mpi_new (0))); | ||
283 | do | ||
284 | { | ||
285 | gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM); | ||
286 | } | ||
287 | while (gcry_mpi_cmp (r, n) >= 0); | ||
288 | |||
289 | /* g = n + 1 */ | ||
290 | GNUNET_assert (0 != (g = gcry_mpi_new (0))); | ||
291 | gcry_mpi_add_ui (g, n, 1); | ||
292 | |||
293 | /* n_square = n^2 */ | ||
294 | GNUNET_assert (0 != (n_square = gcry_mpi_new (0))); | ||
295 | gcry_mpi_mul (n_square, | ||
296 | n, | ||
297 | n); | ||
298 | |||
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); | ||
303 | |||
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); | ||
309 | |||
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); | ||
316 | |||
317 | GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits, | ||
318 | sizeof(ciphertext->bits), | ||
319 | c); | ||
320 | gcry_mpi_release (c); | ||
321 | |||
322 | return possible_opts; | ||
323 | } | ||
324 | |||
325 | |||
326 | /** | ||
327 | * Decrypt a paillier ciphertext with a private key. | ||
328 | * | ||
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. | ||
333 | */ | ||
334 | void | ||
335 | GNUNET_CRYPTO_paillier_decrypt (const struct | ||
336 | GNUNET_CRYPTO_PaillierPrivateKey *private_key, | ||
337 | const struct | ||
338 | GNUNET_CRYPTO_PaillierPublicKey *public_key, | ||
339 | const struct | ||
340 | GNUNET_CRYPTO_PaillierCiphertext *ciphertext, | ||
341 | gcry_mpi_t m) | ||
342 | { | ||
343 | gcry_mpi_t mu; | ||
344 | gcry_mpi_t lambda; | ||
345 | gcry_mpi_t n; | ||
346 | gcry_mpi_t n_square; | ||
347 | gcry_mpi_t c; | ||
348 | gcry_mpi_t cmu; | ||
349 | gcry_mpi_t cmum1; | ||
350 | gcry_mpi_t mod; | ||
351 | |||
352 | GNUNET_CRYPTO_mpi_scan_unsigned (&lambda, | ||
353 | private_key->lambda, | ||
354 | sizeof(private_key->lambda)); | ||
355 | GNUNET_CRYPTO_mpi_scan_unsigned (&mu, | ||
356 | private_key->mu, | ||
357 | sizeof(private_key->mu)); | ||
358 | GNUNET_CRYPTO_mpi_scan_unsigned (&n, | ||
359 | public_key, | ||
360 | sizeof(struct | ||
361 | GNUNET_CRYPTO_PaillierPublicKey)); | ||
362 | GNUNET_CRYPTO_mpi_scan_unsigned (&c, | ||
363 | ciphertext->bits, | ||
364 | sizeof(ciphertext->bits)); | ||
365 | |||
366 | /* n_square = n * n */ | ||
367 | GNUNET_assert (0 != (n_square = gcry_mpi_new (0))); | ||
368 | gcry_mpi_mul (n_square, n, n); | ||
369 | |||
370 | /* cmu = c^lambda mod n^2 */ | ||
371 | GNUNET_assert (0 != (cmu = gcry_mpi_new (0))); | ||
372 | gcry_mpi_powm (cmu, | ||
373 | c, | ||
374 | lambda, | ||
375 | n_square); | ||
376 | gcry_mpi_release (n_square); | ||
377 | gcry_mpi_release (lambda); | ||
378 | gcry_mpi_release (c); | ||
379 | |||
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); | ||
384 | |||
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); | ||
389 | |||
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); | ||
395 | } | ||
396 | |||
397 | |||
398 | /** | ||
399 | * Compute a ciphertext that represents the sum of the plaintext in @a | ||
400 | * c1 and @a c2. | ||
401 | * | ||
402 | * Note that this operation can only be done a finite number of times | ||
403 | * before an overflow occurs. | ||
404 | * | ||
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. | ||
411 | */ | ||
412 | int | ||
413 | GNUNET_CRYPTO_paillier_hom_add (const struct | ||
414 | GNUNET_CRYPTO_PaillierPublicKey *public_key, | ||
415 | const struct | ||
416 | GNUNET_CRYPTO_PaillierCiphertext *c1, | ||
417 | const struct | ||
418 | GNUNET_CRYPTO_PaillierCiphertext *c2, | ||
419 | struct GNUNET_CRYPTO_PaillierCiphertext *result) | ||
420 | { | ||
421 | gcry_mpi_t a; | ||
422 | gcry_mpi_t b; | ||
423 | gcry_mpi_t c; | ||
424 | gcry_mpi_t n; | ||
425 | gcry_mpi_t n_square; | ||
426 | int32_t o1; | ||
427 | int32_t o2; | ||
428 | |||
429 | o1 = (int32_t) ntohl (c1->remaining_ops); | ||
430 | o2 = (int32_t) ntohl (c2->remaining_ops); | ||
431 | if ((0 >= o1) || (0 >= o2)) | ||
432 | { | ||
433 | GNUNET_break_op (0); | ||
434 | return GNUNET_SYSERR; | ||
435 | } | ||
436 | |||
437 | GNUNET_CRYPTO_mpi_scan_unsigned (&a, | ||
438 | c1->bits, | ||
439 | sizeof(c1->bits)); | ||
440 | GNUNET_CRYPTO_mpi_scan_unsigned (&b, | ||
441 | c2->bits, | ||
442 | sizeof(c2->bits)); | ||
443 | GNUNET_CRYPTO_mpi_scan_unsigned (&n, | ||
444 | public_key, | ||
445 | sizeof(struct | ||
446 | GNUNET_CRYPTO_PaillierPublicKey)); | ||
447 | |||
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); | ||
452 | |||
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); | ||
459 | |||
460 | result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1); | ||
461 | GNUNET_CRYPTO_mpi_print_unsigned (result->bits, | ||
462 | sizeof(result->bits), | ||
463 | c); | ||
464 | gcry_mpi_release (c); | ||
465 | return ntohl (result->remaining_ops); | ||
466 | } | ||
467 | |||
468 | |||
469 | /** | ||
470 | * Get the number of remaining supported homomorphic operations. | ||
471 | * | ||
472 | * @param c Paillier cipher text. | ||
473 | * @return the number of remaining homomorphic operations | ||
474 | */ | ||
475 | int | ||
476 | GNUNET_CRYPTO_paillier_hom_get_remaining (const struct | ||
477 | GNUNET_CRYPTO_PaillierCiphertext *c) | ||
478 | { | ||
479 | GNUNET_assert (NULL != c); | ||
480 | return ntohl (c->remaining_ops); | ||
481 | } | ||
482 | |||
483 | |||
484 | /* end of crypto_paillier.c */ | ||