lib/nettle/mpi.c

   1 /*
   2  * Copyright (C) 2010-2012 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 3 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 License
  19  * along with this program.  If not, see <http://www.gnu.org/licenses/>
  20  *
  21  */
  22
  23 /* Here lie everything that has to do with large numbers, gmp.
  24  */
  25
  26 #include <gnutls_int.h>
  27 #include <gnutls_errors.h>
  28 #include <algorithms.h>
  29 #include <gnutls_num.h>
  30 #include <gnutls_mpi.h>
  31 #include <gmp.h>
  32 #include <nettle/bignum.h>
  33 #include <gnettle.h>
  34 #include <random.h>
  35
  36 #define TOMPZ(x) (*((mpz_t*)(x)))
  37
  38 static int
  39 wrap_nettle_mpi_print (const bigint_t a, void *buffer, size_t * nbytes,
  40                        gnutls_bigint_format_t format)
  41 {
  42   unsigned int size;
  43   mpz_t *p = (void *) a;
  44
  45   if (format == GNUTLS_MPI_FORMAT_USG)
  46     {
  47       size = nettle_mpz_sizeinbase_256_u (*p);
  48     }
  49   else if (format == GNUTLS_MPI_FORMAT_STD)
  50     {
  51       size = nettle_mpz_sizeinbase_256_s (*p);
  52     }
  53   else if (format == GNUTLS_MPI_FORMAT_PGP)
  54     {
  55       size = nettle_mpz_sizeinbase_256_u (*p) + 2;
  56     }
  57   else
  58     {
  59       gnutls_assert ();
  60       return GNUTLS_E_INVALID_REQUEST;
  61     }
  62
  63   if (buffer == NULL || size > *nbytes)
  64     {
  65       *nbytes = size;
  66       return GNUTLS_E_SHORT_MEMORY_BUFFER;
  67     }
  68
  69   if (format == GNUTLS_MPI_FORMAT_PGP)
  70     {
  71       uint8_t *buf = buffer;
  72       unsigned int nbits = _gnutls_mpi_get_nbits (a);
  73       buf[0] = (nbits >> 8) & 0xff;
  74       buf[1] = (nbits) & 0xff;
  75       nettle_mpz_get_str_256 (size - 2, buf + 2, *p);
  76     }
  77   else
  78     {
  79       nettle_mpz_get_str_256 (size, buffer, *p);
  80     }
  81   *nbytes = size;
  82
  83   return 0;
  84 }
  85
  86 static bigint_t
  87 wrap_nettle_mpi_new (int nbits)
  88 {
  89   mpz_t *p;
  90
  91   p = gnutls_malloc (sizeof (*p));
  92   if (p == NULL)
  93     {
  94       gnutls_assert ();
  95       return NULL;
  96     }
  97   mpz_init2 (*p, nbits);
  98
  99   return p;
 100 }
 101
 102 static bigint_t
 103 wrap_nettle_mpi_scan (const void *buffer, size_t nbytes,
 104                       gnutls_bigint_format_t format)
 105 {
 106   bigint_t r = wrap_nettle_mpi_new (nbytes * 8);
 107
 108   if (r == NULL)
 109     {
 110       gnutls_assert ();
 111       return r;
 112     }
 113
 114   if (format == GNUTLS_MPI_FORMAT_USG)
 115     {
 116       nettle_mpz_set_str_256_u (TOMPZ (r), nbytes, buffer);
 117     }
 118   else if (format == GNUTLS_MPI_FORMAT_STD)
 119     {
 120       nettle_mpz_set_str_256_s (TOMPZ (r), nbytes, buffer);
 121     }
 122   else if (format == GNUTLS_MPI_FORMAT_PGP)
 123     {
 124       const uint8_t *buf = buffer;
 125       size_t size;
 126
 127       if (nbytes < 3)
 128         {
 129           gnutls_assert ();
 130           goto fail;
 131         }
 132
 133       size = (buf[0] << 8) | buf[1];
 134       size = (size + 7) / 8;
 135
 136       if (size > nbytes - 2)
 137         {
 138           gnutls_assert ();
 139           goto fail;
 140         }
 141       nettle_mpz_set_str_256_u (TOMPZ (r), size, buf + 2);
 142     }
 143   else
 144     {
 145       gnutls_assert ();
 146       goto fail;
 147     }
 148
 149   return r;
 150 fail:
 151   _gnutls_mpi_release (&r);
 152   return NULL;
 153
 154 }
 155
 156 static int
 157 wrap_nettle_mpi_cmp (const bigint_t u, const bigint_t v)
 158 {
 159   mpz_t *i1 = u, *i2 = v;
 160
 161   return mpz_cmp (*i1, *i2);
 162 }
 163
 164 static int
 165 wrap_nettle_mpi_cmp_ui (const bigint_t u, unsigned long v)
 166 {
 167   mpz_t *i1 = u;
 168
 169   return mpz_cmp_ui (*i1, v);
 170 }
 171
 172 static bigint_t
 173 wrap_nettle_mpi_set (bigint_t w, const bigint_t u)
 174 {
 175   mpz_t *i1, *i2 = u;
 176
 177   if (w == NULL)
 178     w = _gnutls_mpi_alloc_like (u);
 179   i1 = w;
 180
 181   mpz_set (*i1, *i2);
 182
 183   return i1;
 184 }
 185
 186 static bigint_t
 187 wrap_nettle_mpi_set_ui (bigint_t w, unsigned long u)
 188 {
 189   mpz_t *i1;
 190
 191   if (w == NULL)
 192     w = wrap_nettle_mpi_new (32);
 193
 194   i1 = w;
 195
 196   mpz_set_ui (*i1, u);
 197
 198   return i1;
 199 }
 200
 201 static unsigned int
 202 wrap_nettle_mpi_get_nbits (bigint_t a)
 203 {
 204   return mpz_sizeinbase (*((mpz_t *) a), 2);
 205 }
 206
 207 static void
 208 wrap_nettle_mpi_release (bigint_t a)
 209 {
 210   mpz_clear (*((mpz_t *) a));
 211   gnutls_free (a);
 212 }
 213
 214 static bigint_t
 215 wrap_nettle_mpi_mod (const bigint_t a, const bigint_t b)
 216 {
 217   bigint_t r = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (b));
 218
 219   if (r == NULL)
 220     return NULL;
 221
 222   mpz_mod (*((mpz_t *) r), *((mpz_t *) a), *((mpz_t *) b));
 223
 224   return r;
 225 }
 226
 227 static bigint_t
 228 wrap_nettle_mpi_powm (bigint_t w, const bigint_t b, const bigint_t e,
 229                       const bigint_t m)
 230 {
 231   if (w == NULL)
 232     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (m));
 233
 234   if (w == NULL)
 235     return NULL;
 236
 237   mpz_powm (*((mpz_t *) w), *((mpz_t *) b), *((mpz_t *) e), *((mpz_t *) m));
 238
 239   return w;
 240 }
 241
 242 static bigint_t
 243 wrap_nettle_mpi_addm (bigint_t w, const bigint_t a, const bigint_t b,
 244                       const bigint_t m)
 245 {
 246   if (w == NULL)
 247     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 248
 249   if (w == NULL)
 250     return NULL;
 251
 252   mpz_add (*((mpz_t *) w), *((mpz_t *) b), *((mpz_t *) a));
 253   mpz_fdiv_r (*((mpz_t *) w), *((mpz_t *) w), *((mpz_t *) m));
 254
 255   return w;
 256 }
 257
 258 static bigint_t
 259 wrap_nettle_mpi_subm (bigint_t w, const bigint_t a, const bigint_t b,
 260                       const bigint_t m)
 261 {
 262   if (w == NULL)
 263     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 264
 265   if (w == NULL)
 266     return NULL;
 267
 268   mpz_sub (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
 269   mpz_fdiv_r (*((mpz_t *) w), *((mpz_t *) w), *((mpz_t *) m));
 270
 271   return w;
 272 }
 273
 274 static bigint_t
 275 wrap_nettle_mpi_mulm (bigint_t w, const bigint_t a, const bigint_t b,
 276                       const bigint_t m)
 277 {
 278   if (w == NULL)
 279     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (m));
 280
 281   if (w == NULL)
 282     return NULL;
 283
 284   mpz_mul (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
 285   mpz_fdiv_r (*((mpz_t *) w), *((mpz_t *) w), *((mpz_t *) m));
 286
 287   return w;
 288 }
 289
 290 static bigint_t
 291 wrap_nettle_mpi_add (bigint_t w, const bigint_t a, const bigint_t b)
 292 {
 293   if (w == NULL)
 294     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (b));
 295
 296   if (w == NULL)
 297     return NULL;
 298
 299   mpz_add (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
 300
 301   return w;
 302 }
 303
 304 static bigint_t
 305 wrap_nettle_mpi_sub (bigint_t w, const bigint_t a, const bigint_t b)
 306 {
 307   if (w == NULL)
 308     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 309
 310   if (w == NULL)
 311     return NULL;
 312
 313   mpz_sub (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
 314
 315   return w;
 316 }
 317
 318 static bigint_t
 319 wrap_nettle_mpi_mul (bigint_t w, const bigint_t a, const bigint_t b)
 320 {
 321   if (w == NULL)
 322     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 323
 324   if (w == NULL)
 325     return NULL;
 326
 327   mpz_mul (*((mpz_t *) w), *((mpz_t *) a), *((mpz_t *) b));
 328
 329   return w;
 330 }
 331
 332 /* q = a / b */
 333 static bigint_t
 334 wrap_nettle_mpi_div (bigint_t q, const bigint_t a, const bigint_t b)
 335 {
 336   if (q == NULL)
 337     q = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 338
 339   if (q == NULL)
 340     return NULL;
 341
 342   mpz_cdiv_q (*((mpz_t *) q), *((mpz_t *) a), *((mpz_t *) b));
 343
 344   return q;
 345 }
 346
 347 static bigint_t
 348 wrap_nettle_mpi_add_ui (bigint_t w, const bigint_t a, unsigned long b)
 349 {
 350   if (w == NULL)
 351     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 352
 353   if (w == NULL)
 354     return NULL;
 355
 356   mpz_add_ui (*((mpz_t *) w), *((mpz_t *) a), b);
 357
 358   return w;
 359 }
 360
 361 static bigint_t
 362 wrap_nettle_mpi_sub_ui (bigint_t w, const bigint_t a, unsigned long b)
 363 {
 364   if (w == NULL)
 365     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 366
 367   if (w == NULL)
 368     return NULL;
 369
 370   mpz_sub_ui (*((mpz_t *) w), *((mpz_t *) a), b);
 371
 372   return w;
 373
 374 }
 375
 376 static bigint_t
 377 wrap_nettle_mpi_mul_ui (bigint_t w, const bigint_t a, unsigned long b)
 378 {
 379   if (w == NULL)
 380     w = wrap_nettle_mpi_new (wrap_nettle_mpi_get_nbits (a));
 381
 382   if (w == NULL)
 383     return NULL;
 384
 385   mpz_mul_ui (*((mpz_t *) w), *((mpz_t *) a), b);
 386
 387   return w;
 388
 389 }
 390
 391 static int
 392 wrap_nettle_prime_check (bigint_t pp)
 393 {
 394   int ret;
 395   ret = mpz_probab_prime_p (*((mpz_t *) pp), PRIME_CHECK_PARAM);
 396
 397   if (ret > 0)
 398     {
 399       return 0;
 400     }
 401
 402   return GNUTLS_E_INTERNAL_ERROR;       /* ignored */
 403 }
 404
 405
 406 /* generate a prime of the form p=2qw+1
 407  * The algorithm is simple but probably it has to be modified to gcrypt's
 408  * since it is slow. Nature did not want 2qw+1 to be prime.
 409  * The generator will be the generator of a subgroup of order q-1.
 410  *
 411  * Algorithm based on the algorithm in "A Computational Introduction to Number
 412  * Theory and Algebra" by V. Shoup, sec 11.1 Finding a generator for Z^{*}_p
 413  *
 414  */
 415 inline static int
 416 gen_group (mpz_t * prime, mpz_t * generator, unsigned int nbits, unsigned int *q_bits)
 417 {
 418   mpz_t q, w, r;
 419   unsigned int p_bytes = nbits / 8;
 420   uint8_t *buffer = NULL;
 421   unsigned int q_bytes, w_bytes, r_bytes, w_bits;
 422   int ret;
 423
 424   /* security level enforcement.
 425    * Values for q are selected according to ECRYPT II recommendations.
 426    */
 427   q_bytes = _gnutls_pk_bits_to_subgroup_bits (nbits);
 428   q_bytes /= 8;
 429
 430   if (q_bytes == 0 || q_bytes >= p_bytes)
 431     {
 432       gnutls_assert ();
 433       return GNUTLS_E_INVALID_REQUEST;
 434     }
 435
 436   if (nbits % 8 != 0)
 437     p_bytes++;
 438
 439   w_bits = nbits - q_bytes * 8;
 440   w_bytes = w_bits / 8;
 441   if (w_bits % 8 != 0)
 442     w_bytes++;
 443
 444   _gnutls_debug_log
 445     ("Generating group of prime of %u bits and format of 2wq+1. q_size=%u bits\n",
 446      nbits, q_bytes * 8);
 447   buffer = gnutls_malloc (p_bytes);     /* p_bytes > q_bytes */
 448   if (buffer == NULL)
 449     {
 450       gnutls_assert ();
 451       return GNUTLS_E_MEMORY_ERROR;
 452     }
 453
 454   mpz_init (q);
 455   mpz_init (w);
 456   mpz_init (r);
 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 q of size p_bytes - w_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   *q_bits = wrap_nettle_mpi_get_nbits (&q);
 519   _gnutls_debug_log ("Found prime q of %u bits. Looking for generator...\n",
 520                      *q_bits);
 521
 522   /* finally a prime! Let's calculate generator
 523    */
 524
 525   /* c = r^((p-1)/q), r == random
 526    * c = r^(2w)
 527    * if c!=1 c is the generator for the subgroup of order q-1
 528    *
 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_NONCE, buffer, r_bytes);
 538       if (ret < 0)
 539         {
 540           gnutls_assert ();
 541           return ret;
 542         }
 543
 544       nettle_mpz_set_str_256_u (r, r_bytes, buffer);
 545       mpz_fdiv_r (r, r, *prime);
 546
 547       /* check if r^w mod n != 1 mod n */
 548       mpz_powm (*generator, r, 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 %u bits\n",
 559                      wrap_nettle_mpi_get_nbits (prime));
 560
 561   ret = 0;
 562   goto exit;
 563
 564 fail:
 565   mpz_clear (*prime);
 566   mpz_clear (*generator);
 567
 568 exit:
 569   mpz_clear (q);
 570   mpz_clear (w);
 571   mpz_clear (r);
 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   unsigned int q_bits;
 584
 585   if (p == NULL)
 586     {
 587       gnutls_assert ();
 588       return GNUTLS_E_MEMORY_ERROR;
 589     }
 590
 591   g = wrap_nettle_mpi_new (bits);
 592   if (g == NULL)
 593     {
 594       gnutls_assert ();
 595       _gnutls_mpi_release (&p);
 596       return GNUTLS_E_MEMORY_ERROR;
 597     }
 598
 599   ret = gen_group (p, g, bits, &q_bits);
 600   if (ret < 0)
 601     {
 602       _gnutls_mpi_release (&g);
 603       _gnutls_mpi_release (&p);
 604       gnutls_assert ();
 605       return ret;
 606     }
 607
 608   group->p = p;
 609   group->g = g;
 610   group->q_bits = q_bits;
 611
 612   return 0;
 613 }
 614
 615
 616 int crypto_bigint_prio = INT_MAX;
 617
 618 gnutls_crypto_bigint_st _gnutls_mpi_ops = {
 619   .bigint_new = wrap_nettle_mpi_new,
 620   .bigint_cmp = wrap_nettle_mpi_cmp,
 621   .bigint_cmp_ui = wrap_nettle_mpi_cmp_ui,
 622   .bigint_mod = wrap_nettle_mpi_mod,
 623   .bigint_set = wrap_nettle_mpi_set,
 624   .bigint_set_ui = wrap_nettle_mpi_set_ui,
 625   .bigint_get_nbits = wrap_nettle_mpi_get_nbits,
 626   .bigint_powm = wrap_nettle_mpi_powm,
 627   .bigint_addm = wrap_nettle_mpi_addm,
 628   .bigint_subm = wrap_nettle_mpi_subm,
 629   .bigint_add = wrap_nettle_mpi_add,
 630   .bigint_sub = wrap_nettle_mpi_sub,
 631   .bigint_add_ui = wrap_nettle_mpi_add_ui,
 632   .bigint_sub_ui = wrap_nettle_mpi_sub_ui,
 633   .bigint_mul = wrap_nettle_mpi_mul,
 634   .bigint_mulm = wrap_nettle_mpi_mulm,
 635   .bigint_mul_ui = wrap_nettle_mpi_mul_ui,
 636   .bigint_div = wrap_nettle_mpi_div,
 637   .bigint_prime_check = wrap_nettle_prime_check,
 638   .bigint_release = wrap_nettle_mpi_release,
 639   .bigint_print = wrap_nettle_mpi_print,
 640   .bigint_scan = wrap_nettle_mpi_scan,
 641   .bigint_generate_group = wrap_nettle_generate_group
 642 };