GNUnet 0.24.1-16-gbc519cf4b
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
39void
40GNUNET_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
120static int
121GNUNET_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
220int
221GNUNET_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
327void
328GNUNET_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
391int
392GNUNET_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
454int
455GNUNET_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
static 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:103
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
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:532
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:117
GNUNET_SYSERR
@ GNUNET_SYSERR
Definition: gnunet_common.h:109
GNUNET_break_op
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
Definition: gnunet_common.h:1064
GNUNET_assert
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Definition: gnunet_common.h:957
GNUNET_CRYPTO_PaillierCiphertext
Paillier ciphertext.
Definition: gnunet_crypto_lib.h:567
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:572
GNUNET_CRYPTO_PaillierCiphertext::bits
unsigned char bits[2048 *2/8]
The bits of the ciphertext.
Definition: gnunet_crypto_lib.h:577
GNUNET_CRYPTO_PaillierPrivateKey
Paillier private key.
Definition: gnunet_crypto_lib.h:551
GNUNET_CRYPTO_PaillierPrivateKey::mu
unsigned char mu[2048/8]
Mu-component of the private key.
Definition: gnunet_crypto_lib.h:559
GNUNET_CRYPTO_PaillierPrivateKey::lambda
unsigned char lambda[2048/8]
Lambda-component of the private key.
Definition: gnunet_crypto_lib.h:555
GNUNET_CRYPTO_PaillierPublicKey
Paillier public key.
Definition: gnunet_crypto_lib.h:539