GNUnet  0.17.6
crypto_paillier.c
Go to the documentation of this file.
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 
27 #include "platform.h"
28 #include <gcrypt.h>
29 #include "gnunet_util_lib.h"
30 
31 
38 void
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,
63  0, NULL, NULL, NULL,
64  GCRY_STRONG_RANDOM, 0));
65  GNUNET_assert (0 ==
66  gcry_prime_generate (&q,
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);
78  sizeof(struct
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 */
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,
103  mu);
104  gcry_mpi_release (mu);
105 }
106 
107 
119 int
122  const gcry_mpi_t m,
123  int desired_ops,
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 
159  public_key,
160  sizeof(struct
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 
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 
219 int
222  const gcry_mpi_t m,
223  int desired_ops,
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,
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 
264  public_key,
265  sizeof(struct
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 
318  sizeof(ciphertext->bits),
319  c);
320  gcry_mpi_release (c);
321 
322  return possible_opts;
323 }
324 
325 
326 void
329  const struct
331  const struct
333  gcry_mpi_t m)
334 {
335  gcry_mpi_t mu;
336  gcry_mpi_t lambda;
337  gcry_mpi_t n;
338  gcry_mpi_t n_square;
339  gcry_mpi_t c;
340  gcry_mpi_t cmu;
341  gcry_mpi_t cmum1;
342  gcry_mpi_t mod;
343 
345  private_key->lambda,
346  sizeof(private_key->lambda));
348  private_key->mu,
349  sizeof(private_key->mu));
351  public_key,
352  sizeof(struct
355  ciphertext->bits,
356  sizeof(ciphertext->bits));
357 
358  /* n_square = n * n */
359  GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
360  gcry_mpi_mul (n_square, n, n);
361 
362  /* cmu = c^lambda mod n^2 */
363  GNUNET_assert (0 != (cmu = gcry_mpi_new (0)));
364  gcry_mpi_powm (cmu,
365  c,
366  lambda,
367  n_square);
368  gcry_mpi_release (n_square);
369  gcry_mpi_release (lambda);
370  gcry_mpi_release (c);
371 
372  /* cmum1 = cmu - 1 */
373  GNUNET_assert (0 != (cmum1 = gcry_mpi_new (0)));
374  gcry_mpi_sub_ui (cmum1, cmu, 1);
375  gcry_mpi_release (cmu);
376 
377  /* mod = cmum1 / n (mod n) */
378  GNUNET_assert (0 != (mod = gcry_mpi_new (0)));
379  gcry_mpi_div (mod, NULL, cmum1, n, 0);
380  gcry_mpi_release (cmum1);
381 
382  /* m = mod * mu mod n */
383  gcry_mpi_mulm (m, mod, mu, n);
384  gcry_mpi_release (mod);
385  gcry_mpi_release (mu);
386  gcry_mpi_release (n);
387 }
388 
389 
390 int
393  const struct
395  const struct
398 {
399  gcry_mpi_t a;
400  gcry_mpi_t b;
401  gcry_mpi_t c;
402  gcry_mpi_t n;
403  gcry_mpi_t n_square;
404  int32_t o1;
405  int32_t o2;
406 
407  o1 = (int32_t) ntohl (c1->remaining_ops);
408  o2 = (int32_t) ntohl (c2->remaining_ops);
409  if ((0 >= o1) || (0 >= o2))
410  {
411  GNUNET_break_op (0);
412  return GNUNET_SYSERR;
413  }
414 
416  c1->bits,
417  sizeof(c1->bits));
419  c2->bits,
420  sizeof(c2->bits));
422  public_key,
423  sizeof(struct
425 
426  /* n_square = n * n */
427  GNUNET_assert (0 != (n_square = gcry_mpi_new (0)));
428  gcry_mpi_mul (n_square, n, n);
429  gcry_mpi_release (n);
430 
431  /* c = a * b mod n_square */
432  GNUNET_assert (0 != (c = gcry_mpi_new (0)));
433  gcry_mpi_mulm (c, a, b, n_square);
434  gcry_mpi_release (n_square);
435  gcry_mpi_release (a);
436  gcry_mpi_release (b);
437 
438  result->remaining_ops = htonl (GNUNET_MIN (o1, o2) - 1);
440  sizeof(result->bits),
441  c);
442  gcry_mpi_release (c);
443  return ntohl (result->remaining_ops);
444 }
445 
446 
453 int
456 {
457  GNUNET_assert (NULL != c);
458  return ntohl (c->remaining_ops);
459 }
460 
461 
462 /* end of crypto_paillier.c */
int GNUNET_CRYPTO_paillier_encrypt1(const struct GNUNET_CRYPTO_PaillierPublicKey *public_key, const gcry_mpi_t m, int desired_ops, struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
Encrypt a plaintext with a paillier public key.
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition: gnunet-arm.c:104
static int result
Global testing status.
static struct GNUNET_REVOCATION_Query * q
Handle for revocation query.
static struct GNUNET_SECRETSHARING_Ciphertext ciphertext
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-uri.c:37
void GNUNET_CRYPTO_mpi_scan_unsigned(gcry_mpi_t *result, const void *data, size_t size)
Convert data buffer into MPI value.
Definition: crypto_mpi.c:131
int GNUNET_CRYPTO_paillier_hom_get_remaining(const struct GNUNET_CRYPTO_PaillierCiphertext *c)
Get the number of remaining supported homomorphic operations.
#define GNUNET_CRYPTO_PAILLIER_BITS
Size of paillier plain texts and public keys.
int GNUNET_CRYPTO_paillier_encrypt(const struct GNUNET_CRYPTO_PaillierPublicKey *public_key, const gcry_mpi_t m, int desired_ops, struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext)
Encrypt a plaintext with a paillier public key.
void GNUNET_CRYPTO_mpi_print_unsigned(void *buf, size_t size, gcry_mpi_t val)
Output the given MPI value to the given buffer in network byte order.
Definition: crypto_mpi.c:78
void GNUNET_CRYPTO_paillier_create(struct GNUNET_CRYPTO_PaillierPublicKey *public_key, struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
Create a freshly generated paillier public key.
int GNUNET_CRYPTO_paillier_hom_add(const struct GNUNET_CRYPTO_PaillierPublicKey *public_key, const struct GNUNET_CRYPTO_PaillierCiphertext *c1, const struct GNUNET_CRYPTO_PaillierCiphertext *c2, struct GNUNET_CRYPTO_PaillierCiphertext *result)
Compute a ciphertext that represents the sum of the plaintext in c1 and c2.
void GNUNET_CRYPTO_paillier_decrypt(const struct GNUNET_CRYPTO_PaillierPrivateKey *private_key, const struct GNUNET_CRYPTO_PaillierPublicKey *public_key, const struct GNUNET_CRYPTO_PaillierCiphertext *ciphertext, gcry_mpi_t m)
Decrypt a paillier ciphertext with a private key.
#define GNUNET_MIN(a, b)
@ GNUNET_SYSERR
Definition: gnunet_common.h:97
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
int32_t remaining_ops
Guaranteed minimum number of homomorphic operations with this ciphertext, in network byte order (NBO)...
unsigned char bits[2048 *2/8]
The bits of the ciphertext.
unsigned char mu[2048/8]
Mu-component of the private key.
unsigned char lambda[2048/8]
Lambda-component of the private key.