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