2 * Copyright (C) 2010,2011 Free Software Foundation, Inc.
4 * Author: Nikos Mavrogiannopoulos
6 * This file is part of GNUTLS.
8 * The GNUTLS library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation; either version 2.1 of
11 * the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
25 /* Here lie everything that has to do with large numbers, gmp.
28 #include <gnutls_int.h>
29 #include <gnutls_errors.h>
30 #include <gnutls_algorithms.h>
31 #include <gnutls_num.h>
32 #include <gnutls_mpi.h>
34 #include <nettle/bignum.h>
37 #define TOMPZ(x) (*((mpz_t*)(x)))
40 wrap_nettle_mpi_print (const bigint_t a, void *buffer, size_t * nbytes,
41 gnutls_bigint_format_t format)
44 mpz_t *p = (void *) a;
46 if (format == GNUTLS_MPI_FORMAT_USG)
48 size = nettle_mpz_sizeinbase_256_u (*p);
50 else if (format == GNUTLS_MPI_FORMAT_STD)
52 size = nettle_mpz_sizeinbase_256_s (*p);
54 else if (format == GNUTLS_MPI_FORMAT_PGP)
56 size = nettle_mpz_sizeinbase_256_u (*p) + 2;
61 return GNUTLS_E_INVALID_REQUEST;
64 if (buffer == NULL || size > *nbytes)
67 return GNUTLS_E_SHORT_MEMORY_BUFFER;
70 if (format == GNUTLS_MPI_FORMAT_PGP)
73 unsigned int nbits = _gnutls_mpi_get_nbits (a);
74 buf[0] = (nbits >> 8) & 0xff;
75 buf[1] = (nbits) & 0xff;
76 nettle_mpz_get_str_256 (size - 2, buf + 2, *p);
80 nettle_mpz_get_str_256 (size, buffer, *p);
88 wrap_nettle_mpi_new (int nbits)
92 p = gnutls_malloc (sizeof (*p));
98 mpz_init2 (*p, nbits);
104 wrap_nettle_mpi_scan (const void *buffer, size_t nbytes,
105 gnutls_bigint_format_t format)
107 bigint_t r = wrap_nettle_mpi_new (nbytes * 8);
115 if (format == GNUTLS_MPI_FORMAT_USG)
117 nettle_mpz_set_str_256_u (TOMPZ (r), nbytes, buffer);
119 else if (format == GNUTLS_MPI_FORMAT_STD)
121 nettle_mpz_set_str_256_s (TOMPZ (r), nbytes, buffer);
123 else if (format == GNUTLS_MPI_FORMAT_PGP)
125 const opaque *buf = buffer;
134 size = (buf[0] << 8) | buf[1];
135 size = (size + 7) / 8;
137 if (size > nbytes - 2)
142 nettle_mpz_set_str_256_u (TOMPZ (r), size, buf + 2);
152 _gnutls_mpi_release (&r);
158 wrap_nettle_mpi_cmp (const bigint_t u, const bigint_t v)
160 mpz_t *i1 = u, *i2 = v;
162 return mpz_cmp (*i1, *i2);
166 wrap_nettle_mpi_cmp_ui (const bigint_t u, unsigned long v)
170 return mpz_cmp_ui (*i1, v);
174 wrap_nettle_mpi_set (bigint_t w, const bigint_t u)
179 w = _gnutls_mpi_alloc_like (u);
188 wrap_nettle_mpi_set_ui (bigint_t w, unsigned long u)
193 w = wrap_nettle_mpi_new (32);
203 wrap_nettle_mpi_get_nbits (bigint_t a)
205 return mpz_sizeinbase (*((mpz_t *) a), 2);
209 wrap_nettle_mpi_release (bigint_t a)
211 mpz_clear (*((mpz_t *) a));
216 wrap_nettle_mpi_mod (const bigint_t a, const bigint_t b)
218 bigint_t r = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (b));
223 mpz_mod (*((mpz_t *) r), *((mpz_t *) a), *((mpz_t *) b));
229 wrap_nettle_mpi_powm (bigint_t w, const bigint_t b, const bigint_t e,
233 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (m));
238 mpz_powm (*((mpz_t *) w), *((mpz_t *) b), *((mpz_t *) e), *((mpz_t *) m));
244 wrap_nettle_mpi_addm (bigint_t w, const bigint_t a, const bigint_t b,
248 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
253 mpz_add (*((mpz_t *) w), *((mpz_t *) b), *((mpz_t *) a));
254 mpz_fdiv_r (*((mpz_t *) w), *((mpz_t *) w), *((mpz_t *) m));
260 wrap_nettle_mpi_subm (bigint_t w, const bigint_t a, const bigint_t b,
264 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
269 mpz_sub (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
270 mpz_fdiv_r (*((mpz_t *) w), *((mpz_t *) w), *((mpz_t *) m));
276 wrap_nettle_mpi_mulm (bigint_t w, const bigint_t a, const bigint_t b,
280 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (m));
285 mpz_mul (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
286 mpz_fdiv_r (*((mpz_t *) w), *((mpz_t *) w), *((mpz_t *) m));
292 wrap_nettle_mpi_add (bigint_t w, const bigint_t a, const bigint_t b)
295 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (b));
300 mpz_add (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
306 wrap_nettle_mpi_sub (bigint_t w, const bigint_t a, const bigint_t b)
309 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
314 mpz_sub (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
320 wrap_nettle_mpi_mul (bigint_t w, const bigint_t a, const bigint_t b)
323 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
328 mpz_mul (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
335 wrap_nettle_mpi_div (bigint_t q, const bigint_t a, const bigint_t b)
338 q = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
343 mpz_cdiv_q (*((mpz_t *) q), *((mpz_t *) a), *((mpz_t *) b));
349 wrap_nettle_mpi_add_ui (bigint_t w, const bigint_t a, unsigned long b)
352 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
357 mpz_add_ui (*((mpz_t *) w), *((mpz_t *) a), b);
363 wrap_nettle_mpi_sub_ui (bigint_t w, const bigint_t a, unsigned long b)
366 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
371 mpz_sub_ui (*((mpz_t *) w), *((mpz_t *) a), b);
378 wrap_nettle_mpi_mul_ui (bigint_t w, const bigint_t a, unsigned long b)
381 w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
386 mpz_mul_ui (*((mpz_t *) w), *((mpz_t *) a), b);
392 #define PRIME_CHECK_PARAM 8
394 wrap_nettle_prime_check (bigint_t pp)
397 ret = mpz_probab_prime_p (*((mpz_t *) pp), PRIME_CHECK_PARAM);
404 return GNUTLS_E_INTERNAL_ERROR; /* ignored */
408 /* generate a prime of the form p=2qw+1
409 * The algorithm is simple but probably it has to be modified to gcrypt's
410 * since it is slow. Nature did not want 2qw+1 to be prime.
411 * The generator will be the generator of a subgroup of order q-1.
413 * Algorithm based on the algorithm in "A Computational Introduction to Number
414 * Theory and Algebra" by V. Shoup, sec 11.1 Finding a generator for Z^{*}_p
417 gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
420 unsigned int p_bytes = nbits / 8;
421 opaque *buffer = NULL;
422 unsigned int q_bytes, w_bytes, r_bytes, w_bits;
425 /* security level enforcement.
426 * Values for q are selected according to ECRYPT II recommendations.
428 q_bytes = _gnutls_pk_bits_to_subgroup_bits (nbits);
434 return GNUTLS_E_INVALID_REQUEST;
440 w_bits = nbits - q_bytes * 8;
441 w_bytes = w_bits / 8;
446 ("Generating group of prime of %u bits and format of 2wq+1. q_size=%u bits\n",
448 buffer = gnutls_malloc (p_bytes); /* p_bytes > q_bytes */
452 return GNUTLS_E_MEMORY_ERROR;
458 /* search for a prime. We are not that unlucky so search
463 ret = _gnutls_rnd (GNUTLS_RND_RANDOM, buffer, w_bytes);
470 nettle_mpz_set_str_256_u (w, w_bytes, buffer);
474 ret = mpz_probab_prime_p (w, PRIME_CHECK_PARAM);
481 /* now generate w of size p_bytes - q_bytes */
484 ("Found prime w of %u bits. Will look for q of %u bits...\n",
485 wrap_nettle_mpi_get_nbits (&w), q_bytes*8);
489 ret = _gnutls_rnd (GNUTLS_RND_RANDOM, buffer, q_bytes);
496 nettle_mpz_set_str_256_u (q, q_bytes, buffer);
500 ret = mpz_probab_prime_p (q, PRIME_CHECK_PARAM);
506 /* check if 2wq+1 is prime */
507 mpz_mul_ui (*prime, w, 2);
508 mpz_mul (*prime, *prime, q);
509 mpz_add_ui (*prime, *prime, 1);
511 ret = mpz_probab_prime_p (*prime, PRIME_CHECK_PARAM);
518 _gnutls_debug_log ("Found prime q of %u bits. Looking for generator...\n",
519 wrap_nettle_mpi_get_nbits (&q));
521 /* finally a prime! Let calculate generator
524 /* c = r^((p-1)/q), r == random
526 * if c!=1 c is the generator for the subgroup of order q-1
528 * (here we reuse q as r)
532 mpz_mul_ui (w, w, 2); /* w = w*2 */
533 mpz_fdiv_r (w, w, *prime);
537 ret = _gnutls_rnd (GNUTLS_RND_RANDOM, buffer, r_bytes);
544 nettle_mpz_set_str_256_u (q, r_bytes, buffer);
545 mpz_fdiv_r (q, q, *prime);
547 /* check if r^w mod n != 1 mod n */
548 mpz_powm (*generator, q, w, *prime);
550 if (mpz_cmp_ui (*generator, 1) == 0)
556 _gnutls_debug_log ("Found generator g of %u bits\n",
557 wrap_nettle_mpi_get_nbits (generator));
558 _gnutls_debug_log ("Prime n is of %u bits\n",
559 wrap_nettle_mpi_get_nbits (prime));
563 gnutls_free (buffer);
571 mpz_clear (*generator);
572 gnutls_free (buffer);
578 wrap_nettle_generate_group (gnutls_group_st * group, unsigned int bits)
581 bigint_t p = wrap_nettle_mpi_new (bits);
587 return GNUTLS_E_MEMORY_ERROR;
590 g = wrap_nettle_mpi_new (bits);
594 _gnutls_mpi_release (&p);
595 return GNUTLS_E_MEMORY_ERROR;
598 ret = gen_group (p, g, bits);
601 _gnutls_mpi_release (&g);
602 _gnutls_mpi_release (&p);
614 int crypto_bigint_prio = INT_MAX;
616 gnutls_crypto_bigint_st _gnutls_mpi_ops = {
617 .bigint_new = wrap_nettle_mpi_new,
618 .bigint_cmp = wrap_nettle_mpi_cmp,
619 .bigint_cmp_ui = wrap_nettle_mpi_cmp_ui,
620 .bigint_mod = wrap_nettle_mpi_mod,
621 .bigint_set = wrap_nettle_mpi_set,
622 .bigint_set_ui = wrap_nettle_mpi_set_ui,
623 .bigint_get_nbits = wrap_nettle_mpi_get_nbits,
624 .bigint_powm = wrap_nettle_mpi_powm,
625 .bigint_addm = wrap_nettle_mpi_addm,
626 .bigint_subm = wrap_nettle_mpi_subm,
627 .bigint_add = wrap_nettle_mpi_add,
628 .bigint_sub = wrap_nettle_mpi_sub,
629 .bigint_add_ui = wrap_nettle_mpi_add_ui,
630 .bigint_sub_ui = wrap_nettle_mpi_sub_ui,
631 .bigint_mul = wrap_nettle_mpi_mul,
632 .bigint_mulm = wrap_nettle_mpi_mulm,
633 .bigint_mul_ui = wrap_nettle_mpi_mul_ui,
634 .bigint_div = wrap_nettle_mpi_div,
635 .bigint_prime_check = wrap_nettle_prime_check,
636 .bigint_release = wrap_nettle_mpi_release,
637 .bigint_print = wrap_nettle_mpi_print,
638 .bigint_scan = wrap_nettle_mpi_scan,
639 .bigint_generate_group = wrap_nettle_generate_group