aboutsummaryrefslogtreecommitdiff
path: root/src/util/crypto_paillier.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/crypto_paillier.c')
-rw-r--r--src/util/crypto_paillier.c484
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 */
38void
39GNUNET_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 */
119int
120GNUNET_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 */
219int
220GNUNET_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 */
334void
335GNUNET_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 */
412int
413GNUNET_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 */
475int
476GNUNET_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 */