GNUnet  0.10.x
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
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,
60  0, NULL, NULL, NULL,
61  GCRY_STRONG_RANDOM, 0));
62  GNUNET_assert (0 ==
63  gcry_prime_generate (&q,
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);
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 */
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);
99  mu);
100  gcry_mpi_release (mu);
101 }
102 
103 
115 int
117  const gcry_mpi_t m,
118  int desired_ops,
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 
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 
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 
211 int
213  const gcry_mpi_t m,
214  int desired_ops,
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,
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 
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 
307  sizeof (ciphertext->bits),
308  c);
309  gcry_mpi_release (c);
310 
311  return possible_opts;
312 }
313 
314 
323 void
325  const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
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 
339  private_key->lambda,
340  sizeof (private_key->lambda));
342  private_key->mu,
343  sizeof (private_key->mu));
345  public_key,
346  sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
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 
397 int
399  const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
400  const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
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 
420  c1->bits,
421  sizeof (c1->bits));
423  c2->bits,
424  sizeof (c2->bits));
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);
443  sizeof (result->bits),
444  c);
445  gcry_mpi_release (c);
446  return ntohl (result->remaining_ops);
447 }
448 
449 
456 int
458 {
459  GNUNET_assert (NULL != c);
460  return ntohl (c->remaining_ops);
461 }
462 
463 /* end of crypto_paillier.c */
464 
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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:75
unsigned char lambda[2048/8]
Lambda-component of the private key.
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.
int32_t remaining_ops
Guaranteed minimum number of homomorphic operations with this ciphertext, in network byte order (NBO)...
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition: gnunet-arm.c:99
unsigned char bits[2048 *2/8]
The bits of the ciphertext.
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
int GNUNET_CRYPTO_paillier_hom_get_remaining(const struct GNUNET_CRYPTO_PaillierCiphertext *c)
Get the number of remaining supported homomorphic operations.
unsigned char mu[2048/8]
Mu-component of the private key.
#define GNUNET_MIN(a, b)
Definition: gnunet_common.h:83
static int result
Global testing status.
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.
static struct GNUNET_SECRETSHARING_Ciphertext ciphertext
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.
static struct GNUNET_REVOCATION_Query * q
Handle for revocation query.
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:128
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.
#define GNUNET_SYSERR
Definition: gnunet_common.h:79
void GNUNET_CRYPTO_paillier_create(struct GNUNET_CRYPTO_PaillierPublicKey *public_key, struct GNUNET_CRYPTO_PaillierPrivateKey *private_key)
Create a freshly generated paillier public key.
#define GNUNET_CRYPTO_PAILLIER_BITS
Size of paillier plain texts and public keys.