lib/nettle/mpi.c

   1 /*
   2  * Copyright (C) 2010,2011 Free Software Foundation, Inc.
   3  *
   4  * Author: Nikos Mavrogiannopoulos
   5  *
   6  * This file is part of GNUTLS.
   7  *
   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.
  12  *
  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.
  17  *
  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,
  21  * USA
  22  *
  23  */
  24
  25 /* Here lie everything that has to do with large numbers, gmp.
  26  */
  27
  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>
  33 #include <gmp.h>
  34 #include <nettle/bignum.h>
  35 #include <random.h>
  36
  37 #define TOMPZ(x) (*((mpz_t*)(x)))
  38
  39 static int
  40 wrap_nettle_mpi_print (const bigint_t a, void *buffer, size_t * nbytes,
  41                        gnutls_bigint_format_t format)
  42 {
  43   unsigned int size;
  44   mpz_t *p = (void *) a;
  45
  46   if (format == GNUTLS_MPI_FORMAT_USG)
  47     {
  48       size = nettle_mpz_sizeinbase_256_u (*p);
  49     }
  50   else if (format == GNUTLS_MPI_FORMAT_STD)
  51     {
  52       size = nettle_mpz_sizeinbase_256_s (*p);
  53     }
  54   else if (format == GNUTLS_MPI_FORMAT_PGP)
  55     {
  56       size = nettle_mpz_sizeinbase_256_u (*p) + 2;
  57     }
  58   else
  59     {
  60       gnutls_assert ();
  61       return GNUTLS_E_INVALID_REQUEST;
  62     }
  63
  64   if (buffer == NULL || size > *nbytes)
  65     {
  66       *nbytes = size;
  67       return GNUTLS_E_SHORT_MEMORY_BUFFER;
  68     }
  69
  70   if (format == GNUTLS_MPI_FORMAT_PGP)
  71     {
  72       opaque *buf = buffer;
  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);
  77     }
  78   else
  79     {
  80       nettle_mpz_get_str_256 (size, buffer, *p);
  81     }
  82   *nbytes = size;
  83
  84   return 0;
  85 }
  86
  87 static bigint_t
  88 wrap_nettle_mpi_new (int nbits)
  89 {
  90   mpz_t *p;
  91
  92   p = gnutls_malloc (sizeof (*p));
  93   if (p == NULL)
  94     {
  95       gnutls_assert ();
  96       return NULL;
  97     }
  98   mpz_init2 (*p, nbits);
  99
 100   return p;
 101 }
 102
 103 static bigint_t
 104 wrap_nettle_mpi_scan (const void *buffer, size_t nbytes,
 105                       gnutls_bigint_format_t format)
 106 {
 107   bigint_t r = wrap_nettle_mpi_new (nbytes * 8);
 108
 109   if (r == NULL)
 110     {
 111       gnutls_assert ();
 112       return r;
 113     }
 114
 115   if (format == GNUTLS_MPI_FORMAT_USG)
 116     {
 117       nettle_mpz_set_str_256_u (TOMPZ (r), nbytes, buffer);
 118     }
 119   else if (format == GNUTLS_MPI_FORMAT_STD)
 120     {
 121       nettle_mpz_set_str_256_s (TOMPZ (r), nbytes, buffer);
 122     }
 123   else if (format == GNUTLS_MPI_FORMAT_PGP)
 124     {
 125       const opaque *buf = buffer;
 126       size_t size;
 127
 128       if (nbytes < 3)
 129         {
 130           gnutls_assert ();
 131           goto fail;
 132         }
 133
 134       size = (buf[0] << 8) | buf[1];
 135       size = (size + 7) / 8;
 136
 137       if (size > nbytes - 2)
 138         {
 139           gnutls_assert ();
 140           goto fail;
 141         }
 142       nettle_mpz_set_str_256_u (TOMPZ (r), size, buf + 2);
 143     }
 144   else
 145     {
 146       gnutls_assert ();
 147       goto fail;
 148     }
 149
 150   return r;
 151 fail:
 152   _gnutls_mpi_release (&r);
 153   return NULL;
 154
 155 }
 156
 157 static int
 158 wrap_nettle_mpi_cmp (const bigint_t u, const bigint_t v)
 159 {
 160   mpz_t *i1 = u, *i2 = v;
 161
 162   return mpz_cmp (*i1, *i2);
 163 }
 164
 165 static int
 166 wrap_nettle_mpi_cmp_ui (const bigint_t u, unsigned long v)
 167 {
 168   mpz_t *i1 = u;
 169
 170   return mpz_cmp_ui (*i1, v);
 171 }
 172
 173 static bigint_t
 174 wrap_nettle_mpi_set (bigint_t w, const bigint_t u)
 175 {
 176   mpz_t *i1, *i2 = u;
 177
 178   if (w == NULL)
 179     w = _gnutls_mpi_alloc_like (u);
 180   i1 = w;
 181
 182   mpz_set (*i1, *i2);
 183
 184   return i1;
 185 }
 186
 187 static bigint_t
 188 wrap_nettle_mpi_set_ui (bigint_t w, unsigned long u)
 189 {
 190   mpz_t *i1;
 191
 192   if (w == NULL)
 193     w = wrap_nettle_mpi_new (32);
 194
 195   i1 = w;
 196
 197   mpz_set_ui (*i1, u);
 198
 199   return i1;
 200 }
 201
 202 static unsigned int
 203 wrap_nettle_mpi_get_nbits (bigint_t a)
 204 {
 205   return mpz_sizeinbase (*((mpz_t *) a), 2);
 206 }
 207
 208 static void
 209 wrap_nettle_mpi_release (bigint_t a)
 210 {
 211   mpz_clear (*((mpz_t *) a));
 212   gnutls_free (a);
 213 }
 214
 215 static bigint_t
 216 wrap_nettle_mpi_mod (const bigint_t a, const bigint_t b)
 217 {
 218   bigint_t r = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (b));
 219
 220   if (r == NULL)
 221     return NULL;
 222
 223   mpz_mod (*((mpz_t *) r), *((mpz_t *) a), *((mpz_t *) b));
 224
 225   return r;
 226 }
 227
 228 static bigint_t
 229 wrap_nettle_mpi_powm (bigint_t w, const bigint_t b, const bigint_t e,
 230                       const bigint_t m)
 231 {
 232   if (w == NULL)
 233     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (m));
 234
 235   if (w == NULL)
 236     return NULL;
 237
 238   mpz_powm (*((mpz_t *) w), *((mpz_t *) b), *((mpz_t *) e), *((mpz_t *) m));
 239
 240   return w;
 241 }
 242
 243 static bigint_t
 244 wrap_nettle_mpi_addm (bigint_t w, const bigint_t a, const bigint_t b,
 245                       const bigint_t m)
 246 {
 247   if (w == NULL)
 248     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 249
 250   if (w == NULL)
 251     return NULL;
 252
 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));
 255
 256   return w;
 257 }
 258
 259 static bigint_t
 260 wrap_nettle_mpi_subm (bigint_t w, const bigint_t a, const bigint_t b,
 261                       const bigint_t m)
 262 {
 263   if (w == NULL)
 264     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 265
 266   if (w == NULL)
 267     return NULL;
 268
 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));
 271
 272   return w;
 273 }
 274
 275 static bigint_t
 276 wrap_nettle_mpi_mulm (bigint_t w, const bigint_t a, const bigint_t b,
 277                       const bigint_t m)
 278 {
 279   if (w == NULL)
 280     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (m));
 281
 282   if (w == NULL)
 283     return NULL;
 284
 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));
 287
 288   return w;
 289 }
 290
 291 static bigint_t
 292 wrap_nettle_mpi_add (bigint_t w, const bigint_t a, const bigint_t b)
 293 {
 294   if (w == NULL)
 295     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (b));
 296
 297   if (w == NULL)
 298     return NULL;
 299
 300   mpz_add (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
 301
 302   return w;
 303 }
 304
 305 static bigint_t
 306 wrap_nettle_mpi_sub (bigint_t w, const bigint_t a, const bigint_t b)
 307 {
 308   if (w == NULL)
 309     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 310
 311   if (w == NULL)
 312     return NULL;
 313
 314   mpz_sub (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
 315
 316   return w;
 317 }
 318
 319 static bigint_t
 320 wrap_nettle_mpi_mul (bigint_t w, const bigint_t a, const bigint_t b)
 321 {
 322   if (w == NULL)
 323     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 324
 325   if (w == NULL)
 326     return NULL;
 327
 328   mpz_mul (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
 329
 330   return w;
 331 }
 332
 333 /* q = a / b */
 334 static bigint_t
 335 wrap_nettle_mpi_div (bigint_t q, const bigint_t a, const bigint_t b)
 336 {
 337   if (q == NULL)
 338     q = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 339
 340   if (q == NULL)
 341     return NULL;
 342
 343   mpz_cdiv_q (*((mpz_t *) q), *((mpz_t *) a), *((mpz_t *) b));
 344
 345   return q;
 346 }
 347
 348 static bigint_t
 349 wrap_nettle_mpi_add_ui (bigint_t w, const bigint_t a, unsigned long b)
 350 {
 351   if (w == NULL)
 352     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 353
 354   if (w == NULL)
 355     return NULL;
 356
 357   mpz_add_ui (*((mpz_t *) w), *((mpz_t *) a), b);
 358
 359   return w;
 360 }
 361
 362 static bigint_t
 363 wrap_nettle_mpi_sub_ui (bigint_t w, const bigint_t a, unsigned long b)
 364 {
 365   if (w == NULL)
 366     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 367
 368   if (w == NULL)
 369     return NULL;
 370
 371   mpz_sub_ui (*((mpz_t *) w), *((mpz_t *) a), b);
 372
 373   return w;
 374
 375 }
 376
 377 static bigint_t
 378 wrap_nettle_mpi_mul_ui (bigint_t w, const bigint_t a, unsigned long b)
 379 {
 380   if (w == NULL)
 381     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 382
 383   if (w == NULL)
 384     return NULL;
 385
 386   mpz_mul_ui (*((mpz_t *) w), *((mpz_t *) a), b);
 387
 388   return w;
 389
 390 }
 391
 392 #define PRIME_CHECK_PARAM 8
 393 static int
 394 wrap_nettle_prime_check (bigint_t pp)
 395 {
 396   int ret;
 397   ret = mpz_probab_prime_p (*((mpz_t *) pp), PRIME_CHECK_PARAM);
 398
 399   if (ret > 0)
 400     {
 401       return 0;
 402     }
 403
 404   return GNUTLS_E_INTERNAL_ERROR;       /* ignored */
 405 }
 406
 407
 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.
 412  *
 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
 415  */
 416 inline static int
 417 gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits)
 418 {
 419   mpz_t q, w;
 420   unsigned int p_bytes = nbits / 8;
 421   opaque *buffer = NULL;
 422   unsigned int q_bytes, w_bytes, r_bytes, w_bits;
 423   int ret;
 424
 425   /* security level enforcement.
 426    * Values for q are selected according to ECRYPT II recommendations.
 427    */
 428   q_bytes = _gnutls_pk_bits_to_subgroup_bits (nbits);
 429   q_bytes /= 8;
 430
 431   if (q_bytes == 0)
 432     {
 433       gnutls_assert ();
 434       return GNUTLS_E_INVALID_REQUEST;
 435     }
 436
 437   if (nbits % 8 != 0)
 438     p_bytes++;
 439
 440   w_bits = nbits - q_bytes * 8;
 441   w_bytes = w_bits / 8;
 442   if (w_bits % 8 != 0)
 443     w_bytes++;
 444
 445   _gnutls_debug_log
 446     ("Generating group of prime of %u bits and format of 2wq+1. q_size=%u bits\n",
 447      nbits, q_bytes * 8);
 448   buffer = gnutls_malloc (p_bytes);     /* p_bytes > q_bytes */
 449   if (buffer == NULL)
 450     {
 451       gnutls_assert ();
 452       return GNUTLS_E_MEMORY_ERROR;
 453     }
 454
 455   mpz_init (q);
 456   mpz_init (w);
 457
 458   /* search for a prime. We are not that unlucky so search
 459    * forever.
 460    */
 461   for (;;)
 462     {
 463       ret = _gnutls_rnd (GNUTLS_RND_RANDOM, buffer, w_bytes);
 464       if (ret < 0)
 465         {
 466           gnutls_assert ();
 467           goto fail;
 468         }
 469
 470       nettle_mpz_set_str_256_u (w, w_bytes, buffer);
 471       /* always odd */
 472       mpz_setbit (w, 0);
 473
 474       ret = mpz_probab_prime_p (w, PRIME_CHECK_PARAM);
 475       if (ret > 0)
 476         {
 477           break;
 478         }
 479     }
 480
 481   /* now generate w of size p_bytes - q_bytes */
 482
 483   _gnutls_debug_log
 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);
 486
 487   for (;;)
 488     {
 489       ret = _gnutls_rnd (GNUTLS_RND_RANDOM, buffer, q_bytes);
 490       if (ret < 0)
 491         {
 492           gnutls_assert ();
 493           return ret;
 494         }
 495
 496       nettle_mpz_set_str_256_u (q, q_bytes, buffer);
 497       /* always odd */
 498       mpz_setbit (q, 0);
 499
 500       ret = mpz_probab_prime_p (q, PRIME_CHECK_PARAM);
 501       if (ret == 0)
 502         {
 503           continue;
 504         }
 505
 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);
 510
 511       ret = mpz_probab_prime_p (*prime, PRIME_CHECK_PARAM);
 512       if (ret > 0)
 513         {
 514           break;
 515         }
 516     }
 517
 518   _gnutls_debug_log ("Found prime q of %u bits. Looking for generator...\n",
 519                      wrap_nettle_mpi_get_nbits (&q));
 520
 521   /* finally a prime! Let calculate generator
 522    */
 523
 524   /* c = r^((p-1)/q), r == random
 525    * c = r^(2w)
 526    * if c!=1 c is the generator for the subgroup of order q-1
 527    *
 528    * (here we reuse q as r)
 529    */
 530   r_bytes = p_bytes;
 531
 532   mpz_mul_ui (w, w, 2);         /* w = w*2 */
 533   mpz_fdiv_r (w, w, *prime);
 534
 535   for (;;)
 536     {
 537       ret = _gnutls_rnd (GNUTLS_RND_RANDOM, buffer, r_bytes);
 538       if (ret < 0)
 539         {
 540           gnutls_assert ();
 541           return ret;
 542         }
 543
 544       nettle_mpz_set_str_256_u (q, r_bytes, buffer);
 545       mpz_fdiv_r (q, q, *prime);
 546
 547       /* check if r^w mod n != 1 mod n */
 548       mpz_powm (*generator, q, w, *prime);
 549
 550       if (mpz_cmp_ui (*generator, 1) == 0)
 551         continue;
 552       else
 553         break;
 554     }
 555
 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));
 560
 561   mpz_clear (q);
 562   mpz_clear (w);
 563   gnutls_free (buffer);
 564
 565   return 0;
 566
 567 fail:
 568   mpz_clear (q);
 569   mpz_clear (w);
 570   mpz_clear (*prime);
 571   mpz_clear (*generator);
 572   gnutls_free (buffer);
 573
 574   return ret;
 575 }
 576
 577 static int
 578 wrap_nettle_generate_group (gnutls_group_st * group, unsigned int bits)
 579 {
 580   int ret;
 581   bigint_t p = wrap_nettle_mpi_new (bits);
 582   bigint_t g;
 583
 584   if (p == NULL)
 585     {
 586       gnutls_assert ();
 587       return GNUTLS_E_MEMORY_ERROR;
 588     }
 589
 590   g = wrap_nettle_mpi_new (bits);
 591   if (g == NULL)
 592     {
 593       gnutls_assert ();
 594       _gnutls_mpi_release (&p);
 595       return GNUTLS_E_MEMORY_ERROR;
 596     }
 597
 598   ret = gen_group (p, g, bits);
 599   if (ret < 0)
 600     {
 601       _gnutls_mpi_release (&g);
 602       _gnutls_mpi_release (&p);
 603       gnutls_assert ();
 604       return ret;
 605     }
 606
 607   group->p = p;
 608   group->g = g;
 609
 610   return 0;
 611 }
 612
 613
 614 int crypto_bigint_prio = INT_MAX;
 615
 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
 640 };