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  {
54  if (NULL != p)
55  gcry_mpi_release(p);
56  if (NULL != q)
57  gcry_mpi_release(q);
58  GNUNET_assert(0 ==
59  gcry_prime_generate(&p,
61  0, NULL, NULL, NULL,
62  GCRY_STRONG_RANDOM, 0));
63  GNUNET_assert(0 ==
64  gcry_prime_generate(&q,
66  0, NULL, NULL, NULL,
67  GCRY_STRONG_RANDOM, 0));
68  }
69  while (0 == gcry_mpi_cmp(p, q));
70  /* n = p * q */
71  GNUNET_assert(NULL != (n = gcry_mpi_new(0)));
72  gcry_mpi_mul(n,
73  p,
74  q);
76  sizeof(struct GNUNET_CRYPTO_PaillierPublicKey),
77  n);
78 
79  /* compute phi(n) = (p-1)(q-1) */
80  GNUNET_assert(NULL != (phi = gcry_mpi_new(0)));
81  gcry_mpi_sub_ui(p, p, 1);
82  gcry_mpi_sub_ui(q, q, 1);
83  gcry_mpi_mul(phi, p, q);
84  gcry_mpi_release(p);
85  gcry_mpi_release(q);
86 
87  /* lambda equals phi(n) in the simplified key generation */
90  phi);
91  /* mu = phi^{-1} mod n, as we use g = n + 1 */
92  GNUNET_assert(NULL != (mu = gcry_mpi_new(0)));
93  GNUNET_assert(0 != gcry_mpi_invm(mu,
94  phi,
95  n));
96  gcry_mpi_release(phi);
97  gcry_mpi_release(n);
100  mu);
101  gcry_mpi_release(mu);
102 }
103 
104 
116 int
118  const gcry_mpi_t m,
119  int desired_ops,
121 {
122  int possible_opts;
123  gcry_mpi_t n_square;
124  gcry_mpi_t r;
125  gcry_mpi_t c;
126  gcry_mpi_t n;
127  gcry_mpi_t tmp1;
128  gcry_mpi_t tmp2;
129  unsigned int highbit;
130 
131  /* determine how many operations we could allow, if the other number
132  has the same length. */
133  GNUNET_assert(NULL != (tmp1 = gcry_mpi_set_ui(NULL, 1)));
134  GNUNET_assert(NULL != (tmp2 = gcry_mpi_set_ui(NULL, 2)));
135  gcry_mpi_mul_2exp(tmp1, tmp1, GNUNET_CRYPTO_PAILLIER_BITS);
136 
137  /* count number of possible operations
138  this would be nicer with gcry_mpi_get_nbits, however it does not return
139  the BITLENGTH of the given MPI's value, but the bits required
140  to represent the number as MPI. */
141  for (possible_opts = -2; gcry_mpi_cmp(tmp1, m) > 0; possible_opts++)
142  gcry_mpi_div(tmp1, NULL, tmp1, tmp2, 0);
143  gcry_mpi_release(tmp1);
144  gcry_mpi_release(tmp2);
145 
146  if (possible_opts < 1)
147  possible_opts = 0;
148  /* soft-cap by caller */
149  possible_opts = (desired_ops < possible_opts) ? desired_ops : possible_opts;
150 
151  ciphertext->remaining_ops = htonl(possible_opts);
152 
154  public_key,
155  sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
156  highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
157  while ((!gcry_mpi_test_bit(n, highbit)) &&
158  (0 != highbit))
159  highbit--;
160  if (0 == highbit)
161  {
162  /* invalid public key */
163  GNUNET_break_op(0);
164  gcry_mpi_release(n);
165  return GNUNET_SYSERR;
166  }
167  GNUNET_assert(0 != (n_square = gcry_mpi_new(0)));
168  GNUNET_assert(0 != (r = gcry_mpi_new(0)));
169  GNUNET_assert(0 != (c = gcry_mpi_new(0)));
170  gcry_mpi_mul(n_square, n, n);
171 
172  /* generate r < n (without bias) */
173  do
174  {
175  gcry_mpi_randomize(r, highbit + 1, GCRY_STRONG_RANDOM);
176  }
177  while (gcry_mpi_cmp(r, n) >= 0);
178 
179  /* c = (n+1)^m mod n^2 */
180  /* c = n + 1 */
181  gcry_mpi_add_ui(c, n, 1);
182  /* c = (n+1)^m mod n^2 */
183  gcry_mpi_powm(c, c, m, n_square);
184  /* r <- r^n mod n^2 */
185  gcry_mpi_powm(r, r, n, n_square);
186  /* c <- r*c mod n^2 */
187  gcry_mpi_mulm(c, r, c, n_square);
188 
190  sizeof ciphertext->bits,
191  c);
192 
193  gcry_mpi_release(n_square);
194  gcry_mpi_release(n);
195  gcry_mpi_release(r);
196  gcry_mpi_release(c);
197 
198  return possible_opts;
199 }
200 
201 
213 int
215  const gcry_mpi_t m,
216  int desired_ops,
218 {
219  int possible_opts;
220  gcry_mpi_t n_square;
221  gcry_mpi_t r;
222  gcry_mpi_t rn;
223  gcry_mpi_t g;
224  gcry_mpi_t gm;
225  gcry_mpi_t c;
226  gcry_mpi_t n;
227  gcry_mpi_t max_num;
228  unsigned int highbit;
229 
230  /* set max_num = 2^{GNUNET_CRYPTO_PAILLIER_BITS}, the largest
231  number we can have as a result */
232  GNUNET_assert(NULL != (max_num = gcry_mpi_set_ui(NULL, 1)));
233  gcry_mpi_mul_2exp(max_num,
234  max_num,
236 
237  /* Determine how many operations we could allow, assuming the other
238  number has the same length (or is smaller), by counting the
239  number of possible operations. We essentially divide max_num by
240  2 until the result is no longer larger than 'm', incrementing the
241  maximum number of operations in each round, starting at -2 */
242  for (possible_opts = -2; gcry_mpi_cmp(max_num, m) > 0; possible_opts++)
243  gcry_mpi_div(max_num,
244  NULL,
245  max_num,
246  GCRYMPI_CONST_TWO,
247  0);
248  gcry_mpi_release(max_num);
249 
250  if (possible_opts < 1)
251  possible_opts = 0;
252  /* Enforce soft-cap by caller */
253  possible_opts = GNUNET_MIN(desired_ops, possible_opts);
254  ciphertext->remaining_ops = htonl(possible_opts);
255 
257  public_key,
258  sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
259 
260  /* check public key for number of bits, bail out if key is all zeros */
261  highbit = GNUNET_CRYPTO_PAILLIER_BITS - 1;
262  while ((!gcry_mpi_test_bit(n, highbit)) &&
263  (0 != highbit))
264  highbit--;
265  if (0 == highbit)
266  {
267  /* invalid public key */
268  GNUNET_break_op(0);
269  gcry_mpi_release(n);
270  return GNUNET_SYSERR;
271  }
272 
273  /* generate r < n (without bias) */
274  GNUNET_assert(NULL != (r = gcry_mpi_new(0)));
275  do
276  {
277  gcry_mpi_randomize(r, highbit + 1, GCRY_STRONG_RANDOM);
278  }
279  while (gcry_mpi_cmp(r, n) >= 0);
280 
281  /* g = n + 1 */
282  GNUNET_assert(0 != (g = gcry_mpi_new(0)));
283  gcry_mpi_add_ui(g, n, 1);
284 
285  /* n_square = n^2 */
286  GNUNET_assert(0 != (n_square = gcry_mpi_new(0)));
287  gcry_mpi_mul(n_square,
288  n,
289  n);
290 
291  /* gm = g^m mod n^2 */
292  GNUNET_assert(0 != (gm = gcry_mpi_new(0)));
293  gcry_mpi_powm(gm, g, m, n_square);
294  gcry_mpi_release(g);
295 
296  /* rn <- r^n mod n^2 */
297  GNUNET_assert(0 != (rn = gcry_mpi_new(0)));
298  gcry_mpi_powm(rn, r, n, n_square);
299  gcry_mpi_release(r);
300  gcry_mpi_release(n);
301 
302  /* c <- rn * gm mod n^2 */
303  GNUNET_assert(0 != (c = gcry_mpi_new(0)));
304  gcry_mpi_mulm(c, rn, gm, n_square);
305  gcry_mpi_release(n_square);
306  gcry_mpi_release(gm);
307  gcry_mpi_release(rn);
308 
310  sizeof(ciphertext->bits),
311  c);
312  gcry_mpi_release(c);
313 
314  return possible_opts;
315 }
316 
317 
326 void
328  const struct GNUNET_CRYPTO_PaillierPublicKey *public_key,
330  gcry_mpi_t m)
331 {
332  gcry_mpi_t mu;
333  gcry_mpi_t lambda;
334  gcry_mpi_t n;
335  gcry_mpi_t n_square;
336  gcry_mpi_t c;
337  gcry_mpi_t cmu;
338  gcry_mpi_t cmum1;
339  gcry_mpi_t mod;
340 
342  private_key->lambda,
343  sizeof(private_key->lambda));
345  private_key->mu,
346  sizeof(private_key->mu));
348  public_key,
349  sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
351  ciphertext->bits,
352  sizeof(ciphertext->bits));
353 
354  /* n_square = n * n */
355  GNUNET_assert(0 != (n_square = gcry_mpi_new(0)));
356  gcry_mpi_mul(n_square, n, n);
357 
358  /* cmu = c^lambda mod n^2 */
359  GNUNET_assert(0 != (cmu = gcry_mpi_new(0)));
360  gcry_mpi_powm(cmu,
361  c,
362  lambda,
363  n_square);
364  gcry_mpi_release(n_square);
365  gcry_mpi_release(lambda);
366  gcry_mpi_release(c);
367 
368  /* cmum1 = cmu - 1 */
369  GNUNET_assert(0 != (cmum1 = gcry_mpi_new(0)));
370  gcry_mpi_sub_ui(cmum1, cmu, 1);
371  gcry_mpi_release(cmu);
372 
373  /* mod = cmum1 / n (mod n) */
374  GNUNET_assert(0 != (mod = gcry_mpi_new(0)));
375  gcry_mpi_div(mod, NULL, cmum1, n, 0);
376  gcry_mpi_release(cmum1);
377 
378  /* m = mod * mu mod n */
379  gcry_mpi_mulm(m, mod, mu, n);
380  gcry_mpi_release(mod);
381  gcry_mpi_release(mu);
382  gcry_mpi_release(n);
383 }
384 
385 
400 int
402  const struct GNUNET_CRYPTO_PaillierCiphertext *c1,
403  const struct GNUNET_CRYPTO_PaillierCiphertext *c2,
405 {
406  gcry_mpi_t a;
407  gcry_mpi_t b;
408  gcry_mpi_t c;
409  gcry_mpi_t n;
410  gcry_mpi_t n_square;
411  int32_t o1;
412  int32_t o2;
413 
414  o1 = (int32_t)ntohl(c1->remaining_ops);
415  o2 = (int32_t)ntohl(c2->remaining_ops);
416  if ((0 >= o1) || (0 >= o2))
417  {
418  GNUNET_break_op(0);
419  return GNUNET_SYSERR;
420  }
421 
423  c1->bits,
424  sizeof(c1->bits));
426  c2->bits,
427  sizeof(c2->bits));
429  public_key,
430  sizeof(struct GNUNET_CRYPTO_PaillierPublicKey));
431 
432  /* n_square = n * n */
433  GNUNET_assert(0 != (n_square = gcry_mpi_new(0)));
434  gcry_mpi_mul(n_square, n, n);
435  gcry_mpi_release(n);
436 
437  /* c = a * b mod n_square */
438  GNUNET_assert(0 != (c = gcry_mpi_new(0)));
439  gcry_mpi_mulm(c, a, b, n_square);
440  gcry_mpi_release(n_square);
441  gcry_mpi_release(a);
442  gcry_mpi_release(b);
443 
444  result->remaining_ops = htonl(GNUNET_MIN(o1, o2) - 1);
446  sizeof(result->bits),
447  c);
448  gcry_mpi_release(c);
449  return ntohl(result->remaining_ops);
450 }
451 
452 
459 int
461 {
462  GNUNET_assert(NULL != c);
463  return ntohl(c->remaining_ops);
464 }
465 
466 /* end of crypto_paillier.c */
467 
#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:80
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:76
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.