use idn2.h or idna.h depending on HAVE_LIBIDN/HAVE_LIBIDN
[oweals/gnunet.git] / src / util / crypto_paillier.c
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 GNUNET_CRYPTO_PaillierPublicKey *public_key,
40                                struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
41 {
42   gcry_mpi_t p;
43   gcry_mpi_t q;
44   gcry_mpi_t phi;
45   gcry_mpi_t mu;
46   gcry_mpi_t n;
47
48   /* Generate two distinct primes.  The probability that the loop body
49      is executed more than once is very very low... */
50   p = NULL;
51   q = NULL;
52   do {
53     if (NULL != p)
54       gcry_mpi_release (p);
55     if (NULL != q)
56       gcry_mpi_release (q);
57     GNUNET_assert (0 ==
58                    gcry_prime_generate (&p,
59                                         GNUNET_CRYPTO_PAILLIER_BITS / 2,
60                                         0, NULL, NULL, NULL,
61                                         GCRY_STRONG_RANDOM, 0));
62     GNUNET_assert (0 ==
63                    gcry_prime_generate (&q,
64                                         GNUNET_CRYPTO_PAILLIER_BITS / 2,
65                                         0, NULL, NULL, NULL,
66                                         GCRY_STRONG_RANDOM, 0));
67   }
68   while (0 == gcry_mpi_cmp (p, q));
69   /* n = p * q */
70   GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
71   gcry_mpi_mul (n,
72                 p,
73                 q);
74   GNUNET_CRYPTO_mpi_print_unsigned (public_key,
75                                     sizeof (struct GNUNET_CRYPTO_PaillierPublicKey),
76                                     n);
77
78   /* compute phi(n) = (p-1)(q-1) */
79   GNUNET_assert (NULL != (phi = gcry_mpi_new (0)));
80   gcry_mpi_sub_ui (p, p, 1);
81   gcry_mpi_sub_ui (q, q, 1);
82   gcry_mpi_mul (phi, p, q);
83   gcry_mpi_release (p);
84   gcry_mpi_release (q);
85
86   /* lambda equals phi(n) in the simplified key generation */
87   GNUNET_CRYPTO_mpi_print_unsigned (private_key->lambda,
88                                     GNUNET_CRYPTO_PAILLIER_BITS / 8,
89                                     phi);
90   /* mu = phi^{-1} mod n, as we use g = n + 1 */
91   GNUNET_assert (NULL != (mu = gcry_mpi_new (0)));
92   GNUNET_assert (0 != gcry_mpi_invm (mu,
93                                      phi,
94                                      n));
95   gcry_mpi_release (phi);
96   gcry_mpi_release (n);
97   GNUNET_CRYPTO_mpi_print_unsigned (private_key->mu,
98                                     GNUNET_CRYPTO_PAILLIER_BITS / 8,
99                                     mu);
100   gcry_mpi_release (mu);
101 }
102
103
104 /**
105  * Encrypt a plaintext with a paillier public key.
106  *
107  * @param public_key Public key to use.
108  * @param m Plaintext to encrypt.
109  * @param desired_ops How many homomorphic ops the caller intends to use
110  * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
111  * @return guaranteed number of supported homomorphic operations >= 1,
112  *         or desired_ops, in case that is lower,
113  *         or -1 if less than one homomorphic operation is possible
114  */
115 int
116 GNUNET_CRYPTO_paillier_encrypt1 (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
117                                 const gcry_mpi_t m,
118                                 int desired_ops,
119                                 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
120 {
121   int possible_opts;
122   gcry_mpi_t n_square;
123   gcry_mpi_t r;
124   gcry_mpi_t c;
125   gcry_mpi_t n;
126   gcry_mpi_t tmp1;
127   gcry_mpi_t tmp2;
128   unsigned int highbit;
129
130   /* determine how many operations we could allow, if the other number
131      has the same length. */
132   GNUNET_assert (NULL != (tmp1 = gcry_mpi_set_ui (NULL, 1)));
133   GNUNET_assert (NULL != (tmp2 = gcry_mpi_set_ui (NULL, 2)));
134   gcry_mpi_mul_2exp (tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
135
136   /* count number of possible operations
137      this would be nicer with gcry_mpi_get_nbits, however it does not return
138      the BITLENGTH of the given MPI's value, but the bits required
139      to represent the number as MPI. */
140   for (possible_opts = -2; gcry_mpi_cmp (tmp1, m) > 0; possible_opts++)
141     gcry_mpi_div (tmp1, NULL, tmp1, tmp2, 0);
142   gcry_mpi_release (tmp1);
143   gcry_mpi_release (tmp2);
144
145   if (possible_opts < 1)
146     possible_opts = 0;
147   /* soft-cap by caller */
148   possible_opts = (desired_ops < possible_opts)? desired_ops : possible_opts;
149
150   ciphertext->remaining_ops = htonl (possible_opts);
151
152   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
153                                    public_key,
154                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
155   highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
156   while ( (! gcry_mpi_test_bit (n, highbit)) &&
157           (0 != highbit) )
158     highbit--;
159   if (0 == highbit)
160   {
161     /* invalid public key */
162     GNUNET_break_op (0);
163     gcry_mpi_release (n);
164     return GNUNET_SYSERR;
165   }
166   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
167   GNUNET_assert (0 != (r = gcry_mpi_new (0)));
168   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
169   gcry_mpi_mul (n_square, n, n);
170
171   /* generate r < n (without bias) */
172   do {
173     gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
174   }
175   while (gcry_mpi_cmp (r, n) >= 0);
176
177   /* c = (n+1)^m mod n^2 */
178   /* c = n + 1 */
179   gcry_mpi_add_ui (c, n, 1);
180   /* c = (n+1)^m mod n^2 */
181   gcry_mpi_powm (c, c, m, n_square);
182   /* r <- r^n mod n^2 */
183   gcry_mpi_powm (r, r, n, n_square);
184   /* c <- r*c mod n^2 */
185   gcry_mpi_mulm (c, r, c, n_square);
186
187   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
188                                     sizeof ciphertext->bits,
189                                     c);
190
191   gcry_mpi_release (n_square);
192   gcry_mpi_release (n);
193   gcry_mpi_release (r);
194   gcry_mpi_release (c);
195
196   return possible_opts;
197 }
198
199
200 /**
201  * Encrypt a plaintext with a paillier public key.
202  *
203  * @param public_key Public key to use.
204  * @param m Plaintext to encrypt.
205  * @param desired_ops How many homomorphic ops the caller intends to use
206  * @param[out] ciphertext Encrytion of @a plaintext with @a public_key.
207  * @return guaranteed number of supported homomorphic operations >= 1,
208  *         or desired_ops, in case that is lower,
209  *         or -1 if less than one homomorphic operation is possible
210  */
211 int
212 GNUNET_CRYPTO_paillier_encrypt (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
213                                 const gcry_mpi_t m,
214                                 int desired_ops,
215                                 struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
216 {
217   int possible_opts;
218   gcry_mpi_t n_square;
219   gcry_mpi_t r;
220   gcry_mpi_t rn;
221   gcry_mpi_t g;
222   gcry_mpi_t gm;
223   gcry_mpi_t c;
224   gcry_mpi_t n;
225   gcry_mpi_t max_num;
226   unsigned int highbit;
227
228   /* set max_num = 2^{GNUNET_CRYPTO_PAILLIER_BITS}, the largest
229      number we can have as a result */
230   GNUNET_assert (NULL != (max_num = gcry_mpi_set_ui (NULL, 1)));
231   gcry_mpi_mul_2exp (max_num,
232                      max_num,
233                      GNUNET_CRYPTO_PAILLIER_BITS);
234
235   /* Determine how many operations we could allow, assuming the other
236      number has the same length (or is smaller), by counting the
237      number of possible operations.  We essentially divide max_num by
238      2 until the result is no longer larger than 'm', incrementing the
239      maximum number of operations in each round, starting at -2 */
240   for (possible_opts = -2; gcry_mpi_cmp (max_num, m) > 0; possible_opts++)
241     gcry_mpi_div (max_num,
242                   NULL,
243                   max_num,
244                   GCRYMPI_CONST_TWO,
245                   0);
246   gcry_mpi_release (max_num);
247
248   if (possible_opts < 1)
249     possible_opts = 0;
250   /* Enforce soft-cap by caller */
251   possible_opts = GNUNET_MIN (desired_ops, possible_opts);
252   ciphertext->remaining_ops = htonl (possible_opts);
253
254   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
255                                    public_key,
256                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
257
258   /* check public key for number of bits, bail out if key is all zeros */
259   highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
260   while ( (! gcry_mpi_test_bit (n, highbit)) &&
261           (0 != highbit) )
262     highbit--;
263   if (0 == highbit)
264   {
265     /* invalid public key */
266     GNUNET_break_op (0);
267     gcry_mpi_release (n);
268     return GNUNET_SYSERR;
269   }
270
271   /* generate r < n (without bias) */
272   GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
273   do {
274     gcry_mpi_randomize (r, highbit + 1, GCRY_STRONG_RANDOM);
275   }
276   while (gcry_mpi_cmp (r, n) >= 0);
277
278   /* g = n + 1 */
279   GNUNET_assert (0 != (g = gcry_mpi_new (0)));
280   gcry_mpi_add_ui (g, n, 1);
281
282   /* n_square = n^2 */
283   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
284   gcry_mpi_mul (n_square,
285                 n,
286                 n);
287
288   /* gm = g^m mod n^2 */
289   GNUNET_assert (0 != (gm = gcry_mpi_new (0)));
290   gcry_mpi_powm (gm, g, m, n_square);
291   gcry_mpi_release (g);
292
293   /* rn <- r^n mod n^2 */
294   GNUNET_assert (0 != (rn = gcry_mpi_new (0)));
295   gcry_mpi_powm (rn, r, n, n_square);
296   gcry_mpi_release (r);
297   gcry_mpi_release (n);
298
299   /* c <- rn * gm mod n^2 */
300   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
301   gcry_mpi_mulm (c, rn, gm, n_square);
302   gcry_mpi_release (n_square);
303   gcry_mpi_release (gm);
304   gcry_mpi_release (rn);
305
306   GNUNET_CRYPTO_mpi_print_unsigned (ciphertext->bits,
307                                     sizeof (ciphertext->bits),
308                                     c);
309   gcry_mpi_release (c);
310
311   return possible_opts;
312 }
313
314
315 /**
316  * Decrypt a paillier ciphertext with a private key.
317  *
318  * @param private_key Private key to use for decryption.
319  * @param public_key Public key to use for encryption.
320  * @param ciphertext Ciphertext to decrypt.
321  * @param[out] m Decryption of @a ciphertext with @private_key.
322  */
323 void
324 GNUNET_CRYPTO_paillier_decrypt (const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key,
325                                 const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
326                                 const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext,
327                                 gcry_mpi_t m)
328 {
329   gcry_mpi_t mu;
330   gcry_mpi_t lambda;
331   gcry_mpi_t n;
332   gcry_mpi_t n_square;
333   gcry_mpi_t c;
334   gcry_mpi_t cmu;
335   gcry_mpi_t cmum1;
336   gcry_mpi_t mod;
337
338   GNUNET_CRYPTO_mpi_scan_unsigned (&lambda,
339                                    private_key->lambda,
340                                    sizeof (private_key->lambda));
341   GNUNET_CRYPTO_mpi_scan_unsigned (&mu,
342                                    private_key->mu,
343                                    sizeof (private_key->mu));
344   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
345                                    public_key,
346                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
347   GNUNET_CRYPTO_mpi_scan_unsigned (&c,
348                                    ciphertext->bits,
349                                    sizeof (ciphertext->bits));
350
351   /* n_square = n * n */
352   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
353   gcry_mpi_mul (n_square, n, n);
354
355   /* cmu = c^lambda mod n^2 */
356   GNUNET_assert (0 != (cmu = gcry_mpi_new (0)));
357   gcry_mpi_powm (cmu,
358                  c,
359                  lambda,
360                  n_square);
361   gcry_mpi_release (n_square);
362   gcry_mpi_release (lambda);
363   gcry_mpi_release (c);
364
365   /* cmum1 = cmu - 1 */
366   GNUNET_assert (0 != (cmum1 = gcry_mpi_new (0)));
367   gcry_mpi_sub_ui (cmum1, cmu, 1);
368   gcry_mpi_release (cmu);
369
370   /* mod = cmum1 / n (mod n) */
371   GNUNET_assert (0 != (mod = gcry_mpi_new (0)));
372   gcry_mpi_div (mod, NULL, cmum1, n, 0);
373   gcry_mpi_release (cmum1);
374
375   /* m = mod * mu mod n */
376   gcry_mpi_mulm (m, mod, mu, n);
377   gcry_mpi_release (mod);
378   gcry_mpi_release (mu);
379   gcry_mpi_release (n);
380 }
381
382
383 /**
384  * Compute a ciphertext that represents the sum of the plaintext in @a
385  * c1 and @a c2.
386  *
387  * Note that this operation can only be done a finite number of times
388  * before an overflow occurs.
389  *
390  * @param public_key Public key to use for encryption.
391  * @param c1 Paillier cipher text.
392  * @param c2 Paillier cipher text.
393  * @param[out] result Result of the homomorphic operation.
394  * @return #GNUNET_OK if the result could be computed,
395  *         #GNUNET_SYSERR if no more homomorphic operations are remaining.
396  */
397 int
398 GNUNET_CRYPTO_paillier_hom_add (const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
399                                 const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
400                                 const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
401                                 struct GNUNET_CRYPTO_PaillierCiphertext *result)
402 {
403   gcry_mpi_t a;
404   gcry_mpi_t b;
405   gcry_mpi_t c;
406   gcry_mpi_t n;
407   gcry_mpi_t n_square;
408   int32_t o1;
409   int32_t o2;
410
411   o1 = (int32_t) ntohl (c1->remaining_ops);
412   o2 = (int32_t) ntohl (c2->remaining_ops);
413   if ( (0 >= o1) || (0 >= o2) )
414   {
415     GNUNET_break_op (0);
416     return GNUNET_SYSERR;
417   }
418
419   GNUNET_CRYPTO_mpi_scan_unsigned (&a,
420                                    c1->bits,
421                                    sizeof (c1->bits));
422   GNUNET_CRYPTO_mpi_scan_unsigned (&b,
423                                    c2->bits,
424                                    sizeof (c2->bits));
425   GNUNET_CRYPTO_mpi_scan_unsigned (&n,
426                                    public_key,
427                                    sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
428
429   /* n_square = n * n */
430   GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
431   gcry_mpi_mul (n_square, n, n);
432   gcry_mpi_release (n);
433
434   /* c = a * b mod n_square */
435   GNUNET_assert (0 != (c = gcry_mpi_new (0)));
436   gcry_mpi_mulm (c, a, b, n_square);
437   gcry_mpi_release (n_square);
438   gcry_mpi_release (a);
439   gcry_mpi_release (b);
440
441   result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1);
442   GNUNET_CRYPTO_mpi_print_unsigned (result->bits,
443                                     sizeof (result->bits),
444                                     c);
445   gcry_mpi_release (c);
446   return ntohl (result->remaining_ops);
447 }
448
449
450 /**
451  * Get the number of remaining supported homomorphic operations.
452  *
453  * @param c Paillier cipher text.
454  * @return the number of remaining homomorphic operations
455  */
456 int
457 GNUNET_CRYPTO_paillier_hom_get_remaining (const struct GNUNET_CRYPTO_PaillierCiphertext *c)
458 {
459   GNUNET_assert (NULL != c);
460   return ntohl (c->remaining_ops);
461 }
462
463 /* end of crypto_paillier.c */
464