d0_bignum-gmp.c

   1 /*
   2  * FILE:        d0_bignum-gmp.c
   3  * AUTHOR:      Rudolf Polzer - divVerent@xonotic.org
   4  *
   5  * Copyright (c) 2010, Rudolf Polzer
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the copyright holder nor the names of contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTOR(S) ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTOR(S) BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * $Format:commit %H$
  33  * $Id$
  34  */
  35
  36 /* NOTE: this file links against libgmp (http://gmplib.org), which is under the
  37  * Lesser General Public License 2.1 or later. You may have to abide to its
  38  * terms too if you use this file.
  39  * To alternatively link to OpenSSL, provide the option --with-openssl to
  40  * ./configure.
  41  */
  42
  43 #ifdef WIN32
  44 #include <windows.h>
  45 #include <wincrypt.h>
  46 #endif
  47
  48 #include "d0_bignum.h"
  49
  50 #include <gmp.h>
  51 #include <string.h>
  52 #include <stdlib.h>
  53
  54 struct d0_bignum_s
  55 {
  56         mpz_t z;
  57 };
  58
  59 static gmp_randstate_t RANDSTATE;
  60 static d0_bignum_t temp;
  61 static unsigned char numbuf[65536];
  62 static void *tempmutex = NULL; // hold this mutex when using RANDSTATE or temp or numbuf
  63
  64 #include <time.h>
  65 #include <stdio.h>
  66
  67 static void *allocate_function (size_t alloc_size)
  68 {
  69         return d0_malloc(alloc_size);
  70 }
  71 static void *reallocate_function (void *ptr, size_t old_size, size_t new_size)
  72 {
  73         void *data;
  74         if(old_size == new_size)
  75                 return ptr;
  76         data = d0_malloc(new_size);
  77         memcpy(data, ptr, (old_size < new_size) ? old_size : new_size);
  78         d0_free(ptr);
  79         return data;
  80 }
  81 void deallocate_function (void *ptr, size_t size)
  82 {
  83         d0_free(ptr);
  84 }
  85
  86 D0_WARN_UNUSED_RESULT D0_BOOL d0_bignum_INITIALIZE(void)
  87 {
  88         FILE *f;
  89         D0_BOOL ret = 1;
  90         unsigned char buf[256];
  91
  92         tempmutex = d0_createmutex();
  93         d0_lockmutex(tempmutex);
  94
  95         mp_set_memory_functions(allocate_function, reallocate_function, deallocate_function);
  96
  97         d0_bignum_init(&temp);
  98         gmp_randinit_mt(RANDSTATE);
  99         gmp_randseed_ui(RANDSTATE, time(NULL));
 100         * (time_t *) (&buf[0]) = time(0); // if everything else fails, we use the current time + uninitialized data
 101 #ifdef WIN32
 102         {
 103                 HCRYPTPROV hCryptProv;
 104                 if(CryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
 105                 {
 106                         if(!CryptGenRandom(hCryptProv, sizeof(buf), (PBYTE) &buf[0]))
 107                         {
 108                                 fprintf(stderr, "WARNING: could not initialize random number generator (CryptGenRandom failed)\n");
 109                                 ret = 0;
 110                         }
 111                         CryptReleaseContext(hCryptProv, 0);
 112                 }
 113                 else if(CryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT | CRYPT_NEWKEYSET))
 114                 {
 115                         if(!CryptGenRandom(hCryptProv, sizeof(buf), (PBYTE) &buf[0]))
 116                         {
 117                                 fprintf(stderr, "WARNING: could not initialize random number generator (CryptGenRandom failed)\n");
 118                                 ret = 0;
 119                         }
 120                         CryptReleaseContext(hCryptProv, 0);
 121                 }
 122                 else
 123                 {
 124                         fprintf(stderr, "WARNING: could not initialize random number generator (CryptAcquireContext failed)\n");
 125                         ret = 0;
 126                 }
 127         }
 128 #else
 129         f = fopen("/dev/urandom", "rb");
 130         if(!f)
 131                 f = fopen("/dev/random", "rb");
 132         if(f)
 133         {
 134                 setbuf(f, NULL);
 135                 if(fread(buf, sizeof(buf), 1, f) != 1)
 136                 {
 137                         fprintf(stderr, "WARNING: could not initialize random number generator (read from random device failed)\n");
 138                         ret = 0;
 139                 }
 140                 fclose(f);
 141         }
 142         else
 143         {
 144                 fprintf(stderr, "WARNING: could not initialize random number generator (no random device found)\n");
 145                 ret = 0;
 146         }
 147 #endif
 148
 149         mpz_import(temp.z, sizeof(buf), 1, 1, 0, 0, buf);
 150         gmp_randseed(RANDSTATE, temp.z);
 151
 152         d0_unlockmutex(tempmutex);
 153
 154         return ret;
 155 }
 156
 157 void d0_bignum_SHUTDOWN(void)
 158 {
 159         d0_lockmutex(tempmutex);
 160
 161         d0_bignum_clear(&temp);
 162         gmp_randclear(RANDSTATE);
 163
 164         d0_unlockmutex(tempmutex);
 165         d0_destroymutex(tempmutex);
 166         tempmutex = NULL;
 167 }
 168
 169 D0_BOOL d0_iobuf_write_bignum(d0_iobuf_t *buf, const d0_bignum_t *bignum)
 170 {
 171         D0_BOOL ret;
 172         size_t count = 0;
 173
 174         d0_lockmutex(tempmutex);
 175         numbuf[0] = mpz_sgn(bignum->z) & 3;
 176         if((numbuf[0] & 3) != 0) // nonzero
 177         {
 178                 count = (mpz_sizeinbase(bignum->z, 2) + 7) / 8;
 179                 if(count > sizeof(numbuf) - 1)
 180                 {
 181                         d0_unlockmutex(tempmutex);
 182                         return 0;
 183                 }
 184                 mpz_export(numbuf+1, &count, 1, 1, 0, 0, bignum->z);
 185         }
 186         ret = d0_iobuf_write_packet(buf, numbuf, count + 1);
 187         d0_unlockmutex(tempmutex);
 188         return ret;
 189 }
 190
 191 d0_bignum_t *d0_iobuf_read_bignum(d0_iobuf_t *buf, d0_bignum_t *bignum)
 192 {
 193         size_t count = sizeof(numbuf);
 194
 195         d0_lockmutex(tempmutex);
 196         if(!d0_iobuf_read_packet(buf, numbuf, &count))
 197         {
 198                 d0_unlockmutex(tempmutex);
 199                 return NULL;
 200         }
 201         if(count < 1)
 202         {
 203                 d0_unlockmutex(tempmutex);
 204                 return NULL;
 205         }
 206         if(!bignum)
 207                 bignum = d0_bignum_new();
 208         if(!bignum)
 209         {
 210                 d0_unlockmutex(tempmutex);
 211                 return NULL;
 212         }
 213         if(numbuf[0] & 3) // nonzero
 214         {
 215                 mpz_import(bignum->z, count-1, 1, 1, 0, 0, numbuf+1);
 216                 if(numbuf[0] & 2) // negative
 217                         mpz_neg(bignum->z, bignum->z);
 218         }
 219         else // zero
 220         {
 221                 mpz_set_ui(bignum->z, 0);
 222         }
 223         d0_unlockmutex(tempmutex);
 224         return bignum;
 225 }
 226
 227 ssize_t d0_bignum_export_unsigned(const d0_bignum_t *bignum, void *buf, size_t bufsize)
 228 {
 229         size_t count;
 230         count = (mpz_sizeinbase(bignum->z, 2) + 7) / 8;
 231         if(count > bufsize)
 232                 return -1;
 233         if(bufsize > count)
 234         {
 235                 // pad from left (big endian numbers!)
 236                 memset(buf, 0, bufsize - count);
 237                 buf += bufsize - count;
 238         }
 239         bufsize = count;
 240         mpz_export(buf, &bufsize, 1, 1, 0, 0, bignum->z);
 241         if(bufsize > count)
 242         {
 243                 // REALLY BAD
 244                 // mpz_sizeinbase lied to us
 245                 // buffer overflow
 246                 // there is no sane way whatsoever to handle this
 247                 abort();
 248         }
 249         if(bufsize < count)
 250         {
 251                 // BAD
 252                 // mpz_sizeinbase lied to us
 253                 // move the number
 254                 if(count == 0)
 255                 {
 256                         memset(buf, 0, count);
 257                 }
 258                 else
 259                 {
 260                         memmove(buf + count - bufsize, buf, bufsize);
 261                         memset(buf, 0, count - bufsize);
 262                 }
 263         }
 264         return bufsize;
 265 }
 266
 267 d0_bignum_t *d0_bignum_import_unsigned(d0_bignum_t *bignum, const void *buf, size_t bufsize)
 268 {
 269         size_t count;
 270         if(!bignum) bignum = d0_bignum_new(); if(!bignum) return NULL;
 271         mpz_import(bignum->z, bufsize, 1, 1, 0, 0, buf);
 272         return bignum;
 273 }
 274
 275 d0_bignum_t *d0_bignum_new(void)
 276 {
 277         d0_bignum_t *b = d0_malloc(sizeof(d0_bignum_t));
 278         mpz_init(b->z);
 279         return b;
 280 }
 281
 282 void d0_bignum_free(d0_bignum_t *a)
 283 {
 284         mpz_clear(a->z);
 285         d0_free(a);
 286 }
 287
 288 void d0_bignum_init(d0_bignum_t *b)
 289 {
 290         mpz_init(b->z);
 291 }
 292
 293 void d0_bignum_clear(d0_bignum_t *a)
 294 {
 295         mpz_clear(a->z);
 296 }
 297
 298 size_t d0_bignum_size(const d0_bignum_t *r)
 299 {
 300         return mpz_sizeinbase(r->z, 2);
 301 }
 302
 303 int d0_bignum_cmp(const d0_bignum_t *a, const d0_bignum_t *b)
 304 {
 305         return mpz_cmp(a->z, b->z);
 306 }
 307
 308 d0_bignum_t *d0_bignum_rand_range(d0_bignum_t *r, const d0_bignum_t *min, const d0_bignum_t *max)
 309 {
 310         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 311         d0_lockmutex(tempmutex);
 312         mpz_sub(temp.z, max->z, min->z);
 313         mpz_urandomm(r->z, RANDSTATE, temp.z);
 314         d0_unlockmutex(tempmutex);
 315         mpz_add(r->z, r->z, min->z);
 316         return r;
 317 }
 318
 319 d0_bignum_t *d0_bignum_rand_bit_atmost(d0_bignum_t *r, size_t n)
 320 {
 321         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 322         d0_lockmutex(tempmutex);
 323         mpz_urandomb(r->z, RANDSTATE, n);
 324         d0_unlockmutex(tempmutex);
 325         return r;
 326 }
 327
 328 d0_bignum_t *d0_bignum_rand_bit_exact(d0_bignum_t *r, size_t n)
 329 {
 330         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 331         d0_lockmutex(tempmutex);
 332         mpz_urandomb(r->z, RANDSTATE, n-1);
 333         d0_unlockmutex(tempmutex);
 334         mpz_setbit(r->z, n-1);
 335         return r;
 336 }
 337
 338 d0_bignum_t *d0_bignum_zero(d0_bignum_t *r)
 339 {
 340         return d0_bignum_int(r, 0);
 341 }
 342
 343 d0_bignum_t *d0_bignum_one(d0_bignum_t *r)
 344 {
 345         return d0_bignum_int(r, 1);
 346 }
 347
 348 d0_bignum_t *d0_bignum_int(d0_bignum_t *r, int n)
 349 {
 350         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 351         mpz_set_si(r->z, n);
 352         return r;
 353 }
 354
 355 d0_bignum_t *d0_bignum_mov(d0_bignum_t *r, const d0_bignum_t *a)
 356 {
 357         if(r == a)
 358                 return r; // trivial
 359         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 360         mpz_set(r->z, a->z);
 361         return r;
 362 }
 363
 364 d0_bignum_t *d0_bignum_neg(d0_bignum_t *r, const d0_bignum_t *a)
 365 {
 366         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 367         mpz_neg(r->z, a->z);
 368         return r;
 369 }
 370
 371 d0_bignum_t *d0_bignum_shl(d0_bignum_t *r, const d0_bignum_t *a, ssize_t n)
 372 {
 373         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 374         if(n > 0)
 375                 mpz_mul_2exp(r->z, a->z, n);
 376         else if(n < 0)
 377                 mpz_fdiv_q_2exp(r->z, a->z, -n);
 378         else
 379                 mpz_set(r->z, a->z);
 380         return r;
 381 }
 382
 383 d0_bignum_t *d0_bignum_add(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 384 {
 385         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 386         mpz_add(r->z, a->z, b->z);
 387         return r;
 388 }
 389
 390 d0_bignum_t *d0_bignum_sub(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 391 {
 392         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 393         mpz_sub(r->z, a->z, b->z);
 394         return r;
 395 }
 396
 397 d0_bignum_t *d0_bignum_mul(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 398 {
 399         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 400         mpz_mul(r->z, a->z, b->z);
 401         return r;
 402 }
 403
 404 d0_bignum_t *d0_bignum_divmod(d0_bignum_t *q, d0_bignum_t *m, const d0_bignum_t *a, const d0_bignum_t *b)
 405 {
 406         if(!q && !m)
 407                 m = d0_bignum_new();
 408         if(q)
 409                 if(m)
 410                         mpz_fdiv_qr(q->z, m->z, a->z, b->z);
 411                 else
 412                         mpz_fdiv_q(q->z, a->z, b->z);
 413         else
 414                 mpz_fdiv_r(m->z, a->z, b->z);
 415         if(m)
 416                 return m;
 417         else
 418                 return q;
 419 }
 420
 421 d0_bignum_t *d0_bignum_mod_add(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b, const d0_bignum_t *m)
 422 {
 423         r = d0_bignum_add(r, a, b);
 424         mpz_fdiv_r(r->z, r->z, m->z);
 425         return r;
 426 }
 427
 428 d0_bignum_t *d0_bignum_mod_sub(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b, const d0_bignum_t *m)
 429 {
 430         r = d0_bignum_sub(r, a, b);
 431         mpz_fdiv_r(r->z, r->z, m->z);
 432         return r;
 433 }
 434
 435 d0_bignum_t *d0_bignum_mod_mul(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b, const d0_bignum_t *m)
 436 {
 437         r = d0_bignum_mul(r, a, b);
 438         mpz_fdiv_r(r->z, r->z, m->z);
 439         return r;
 440 }
 441
 442 d0_bignum_t *d0_bignum_mod_pow(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b, const d0_bignum_t *m)
 443 {
 444         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 445         mpz_powm(r->z, a->z, b->z, m->z);
 446         return r;
 447 }
 448
 449 D0_BOOL d0_bignum_mod_inv(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *m)
 450 {
 451         // here, r MUST be set, as otherwise we cannot return error state!
 452         return mpz_invert(r->z, a->z, m->z);
 453 }
 454
 455 int d0_bignum_isprime(const d0_bignum_t *r, int param)
 456 {
 457         return mpz_probab_prime_p(r->z, param);
 458 }
 459
 460 d0_bignum_t *d0_bignum_gcd(d0_bignum_t *r, d0_bignum_t *s, d0_bignum_t *t, const d0_bignum_t *a, const d0_bignum_t *b)
 461 {
 462         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 463         if(s)
 464                 mpz_gcdext(r->z, s->z, t ? t->z : NULL, a->z, b->z);
 465         else if(t)
 466                 mpz_gcdext(r->z, t->z, NULL, b->z, a->z);
 467         else
 468                 mpz_gcd(r->z, a->z, b->z);
 469         return r;
 470 }
 471
 472 char *d0_bignum_tostring(const d0_bignum_t *x, unsigned int base)
 473 {
 474         return mpz_get_str(NULL, base, x->z); // this allocates!
 475 }