d0_bignum-tommath.c

   1 /*
   2  * FILE:        d0_bignum-tommath.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 #ifdef WIN32
  37 #include <windows.h>
  38 #include <wincrypt.h>
  39 #endif
  40
  41 #include "d0_bignum.h"
  42
  43 #include <tommath.h>
  44 #include <string.h>
  45 #include <stdlib.h>
  46 #include <assert.h>
  47
  48 struct d0_bignum_s
  49 {
  50         mp_int z;
  51 };
  52
  53 static d0_bignum_t temp;
  54 static void *tempmutex = NULL; // hold this mutex when using temp
  55
  56 #include <stdio.h>
  57
  58 #ifdef WIN32
  59 HCRYPTPROV hCryptProv;
  60 #else
  61 static FILE *randf;
  62 #endif
  63
  64 void rand_bytes(unsigned char *buf, size_t n)
  65 {
  66 #ifdef WIN32
  67         CryptGenRandom(hCryptProv, n, (PBYTE) buf);
  68 #else
  69         if(!randf)
  70                 return;
  71         fread(buf, 1, n, randf);
  72 #endif
  73 }
  74
  75 D0_WARN_UNUSED_RESULT D0_BOOL d0_bignum_INITIALIZE(void)
  76 {
  77         D0_BOOL ret = 1;
  78         unsigned char buf[256];
  79
  80         tempmutex = d0_createmutex();
  81         d0_lockmutex(tempmutex);
  82
  83         d0_bignum_init(&temp);
  84 #ifdef WIN32
  85         {
  86                 if(CryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
  87                 {
  88                 }
  89                 else if(CryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT | CRYPT_NEWKEYSET))
  90                 {
  91                 }
  92                 else
  93                 {
  94                         fprintf(stderr, "WARNING: could not initialize random number generator (CryptAcquireContext failed)\n");
  95                         ret = 0;
  96                         hCryptProv = NULL;
  97                 }
  98         }
  99 #else
 100         randf = fopen("/dev/urandom", "rb");
 101         if(!randf)
 102                 randf = fopen("/dev/random", "rb");
 103         if(randf)
 104         {
 105                 setbuf(randf, NULL);
 106         }
 107         else
 108         {
 109                 fprintf(stderr, "WARNING: could not initialize random number generator (no random device found)\n");
 110                 ret = 0;
 111         }
 112 #endif
 113
 114         d0_unlockmutex(tempmutex);
 115
 116         return ret;
 117 }
 118
 119 void d0_bignum_SHUTDOWN(void)
 120 {
 121         d0_lockmutex(tempmutex);
 122
 123         d0_bignum_clear(&temp);
 124 #ifdef WIN32
 125         if(hCryptProv)
 126         {
 127                 CryptReleaseContext(hCryptProv, 0);
 128                 hCryptProv = NULL;
 129         }
 130 #endif
 131
 132         d0_unlockmutex(tempmutex);
 133         d0_destroymutex(tempmutex);
 134         tempmutex = NULL;
 135 }
 136
 137 D0_BOOL d0_iobuf_write_bignum(d0_iobuf_t *buf, const d0_bignum_t *bignum)
 138 {
 139         static __thread unsigned char numbuf[65536];
 140         size_t count = 0;
 141         numbuf[0] = (mp_iszero(&bignum->z) ? 0 : (bignum->z.sign == MP_ZPOS) ? 1 : 3);
 142         if((numbuf[0] & 3) != 0) // nonzero
 143         {
 144                 count = mp_unsigned_bin_size((mp_int *) &bignum->z);
 145                 if(count > sizeof(numbuf) - 1)
 146                         return 0;
 147                 mp_to_unsigned_bin((mp_int *) &bignum->z, numbuf+1);
 148         }
 149         return d0_iobuf_write_packet(buf, numbuf, count + 1);
 150 }
 151
 152 d0_bignum_t *d0_iobuf_read_bignum(d0_iobuf_t *buf, d0_bignum_t *bignum)
 153 {
 154         static __thread unsigned char numbuf[65536];
 155         size_t count = sizeof(numbuf);
 156         if(!d0_iobuf_read_packet(buf, numbuf, &count))
 157                 return NULL;
 158         if(count < 1)
 159                 return NULL;
 160         if(!bignum) bignum = d0_bignum_new(); if(!bignum) return NULL;
 161         if(numbuf[0] & 3) // nonzero
 162         {
 163                 mp_read_unsigned_bin(&bignum->z, numbuf+1, count-1);
 164                 if(numbuf[0] & 2) // negative
 165                         bignum->z.sign = MP_NEG;
 166         }
 167         else // zero
 168         {
 169                 mp_zero(&bignum->z);
 170         }
 171         return bignum;
 172 }
 173
 174 ssize_t d0_bignum_export_unsigned(const d0_bignum_t *bignum, void *buf, size_t bufsize)
 175 {
 176         unsigned long bufsize_;
 177         unsigned long count;
 178         count = mp_unsigned_bin_size((mp_int *) &bignum->z);
 179         if(count > bufsize)
 180                 return -1;
 181         if(bufsize > count)
 182         {
 183                 // pad from left (big endian numbers!)
 184                 memset(buf, 0, bufsize - count);
 185                 buf += bufsize - count;
 186         }
 187         bufsize_ = count;
 188         mp_to_unsigned_bin_n((mp_int *) &bignum->z, buf, &bufsize_);
 189         bufsize = bufsize_;
 190         if(bufsize > count)
 191         {
 192                 // REALLY BAD
 193                 // mpz_sizeinbase lied to us
 194                 // buffer overflow
 195                 // there is no sane way whatsoever to handle this
 196                 abort();
 197         }
 198         if(bufsize < count)
 199         {
 200                 // BAD
 201                 // mpz_sizeinbase lied to us
 202                 // move the number
 203                 if(count == 0)
 204                 {
 205                         memset(buf, 0, count);
 206                 }
 207                 else
 208                 {
 209                         memmove(buf + count - bufsize, buf, bufsize);
 210                         memset(buf, 0, count - bufsize);
 211                 }
 212         }
 213         return bufsize;
 214 }
 215
 216 d0_bignum_t *d0_bignum_import_unsigned(d0_bignum_t *bignum, const void *buf, size_t bufsize)
 217 {
 218         size_t count;
 219         if(!bignum) bignum = d0_bignum_new(); if(!bignum) return NULL;
 220         mp_read_unsigned_bin(&bignum->z, buf, bufsize);
 221         return bignum;
 222 }
 223
 224 d0_bignum_t *d0_bignum_new(void)
 225 {
 226         d0_bignum_t *b = d0_malloc(sizeof(d0_bignum_t));
 227         mp_init(&b->z);
 228         return b;
 229 }
 230
 231 void d0_bignum_free(d0_bignum_t *a)
 232 {
 233         mp_clear(&a->z);
 234         d0_free(a);
 235 }
 236
 237 void d0_bignum_init(d0_bignum_t *b)
 238 {
 239         mp_init(&b->z);
 240 }
 241
 242 void d0_bignum_clear(d0_bignum_t *a)
 243 {
 244         mp_clear(&a->z);
 245 }
 246
 247 size_t d0_bignum_size(const d0_bignum_t *r)
 248 {
 249         return mp_count_bits((mp_int *) &r->z);
 250 }
 251
 252 int d0_bignum_cmp(const d0_bignum_t *a, const d0_bignum_t *b)
 253 {
 254         return mp_cmp((mp_int *) &a->z, (mp_int *) &b->z);
 255 }
 256
 257 static d0_bignum_t *d0_bignum_rand_0_to_limit(d0_bignum_t *r, const d0_bignum_t *limit)
 258 {
 259         size_t n = d0_bignum_size(limit);
 260         size_t b = (n + 7) / 8;
 261         unsigned char mask = "\xFF\x7F\x3F\x1F\x0F\x07\x03\x01"[8*b - n];
 262         unsigned char numbuf[65536];
 263         assert(b <= sizeof(numbuf));
 264         for(;;)
 265         {
 266                 rand_bytes(numbuf, b);
 267                 numbuf[0] &= mask;
 268                 r = d0_bignum_import_unsigned(r, numbuf, b);
 269                 if(d0_bignum_cmp(r, limit) < 0)
 270                         return r;
 271         }
 272 }
 273
 274 d0_bignum_t *d0_bignum_rand_range(d0_bignum_t *r, const d0_bignum_t *min, const d0_bignum_t *max)
 275 {
 276         d0_lockmutex(tempmutex);
 277         mp_sub((mp_int *) &max->z, (mp_int *) &min->z, &temp.z);
 278         r = d0_bignum_rand_0_to_limit(r, &temp);
 279         d0_unlockmutex(tempmutex);
 280         mp_add((mp_int *) &r->z, (mp_int *) &min->z, &r->z);
 281         return r;
 282 }
 283
 284 d0_bignum_t *d0_bignum_rand_bit_atmost(d0_bignum_t *r, size_t n)
 285 {
 286         d0_lockmutex(tempmutex);
 287         if(!d0_bignum_one(&temp))
 288         {
 289                 d0_unlockmutex(tempmutex);
 290                 return NULL;
 291         }
 292         if(!d0_bignum_shl(&temp, &temp, n))
 293         {
 294                 d0_unlockmutex(tempmutex);
 295                 return NULL;
 296         }
 297         r = d0_bignum_rand_0_to_limit(r, &temp);
 298         d0_unlockmutex(tempmutex);
 299         return r;
 300 }
 301
 302 d0_bignum_t *d0_bignum_rand_bit_exact(d0_bignum_t *r, size_t n)
 303 {
 304         d0_lockmutex(tempmutex);
 305         if(!d0_bignum_one(&temp))
 306         {
 307                 d0_unlockmutex(tempmutex);
 308                 return NULL;
 309         }
 310         if(!d0_bignum_shl(&temp, &temp, n-1))
 311         {
 312                 d0_unlockmutex(tempmutex);
 313                 return NULL;
 314         }
 315         r = d0_bignum_rand_0_to_limit(r, &temp);
 316         if(!d0_bignum_add(r, r, &temp))
 317         {
 318                 d0_unlockmutex(tempmutex);
 319                 return NULL;
 320         }
 321         d0_unlockmutex(tempmutex);
 322         return r;
 323 }
 324
 325 d0_bignum_t *d0_bignum_zero(d0_bignum_t *r)
 326 {
 327         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 328         mp_zero(&r->z);
 329         return r;
 330 }
 331
 332 d0_bignum_t *d0_bignum_one(d0_bignum_t *r)
 333 {
 334         return d0_bignum_int(r, 1);
 335 }
 336
 337 d0_bignum_t *d0_bignum_int(d0_bignum_t *r, int n)
 338 {
 339         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 340         mp_set_int(&r->z, n);
 341         return r;
 342 }
 343
 344 d0_bignum_t *d0_bignum_mov(d0_bignum_t *r, const d0_bignum_t *a)
 345 {
 346         if(r == a)
 347                 return r; // trivial
 348         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 349         mp_copy((mp_int *) &a->z, &r->z);
 350         return r;
 351 }
 352
 353 d0_bignum_t *d0_bignum_neg(d0_bignum_t *r, const d0_bignum_t *a)
 354 {
 355         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 356         mp_neg((mp_int *) &a->z, &r->z);
 357         return r;
 358 }
 359
 360 d0_bignum_t *d0_bignum_shl(d0_bignum_t *r, const d0_bignum_t *a, ssize_t n)
 361 {
 362         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 363         if(n > 0)
 364                 mp_mul_2d((mp_int *) &a->z,  n, &r->z);
 365         else if(n < 0)
 366                 mp_div_2d((mp_int *) &a->z, -n, &r->z, NULL);
 367         else
 368                 mp_copy((mp_int *) &a->z, &r->z);
 369         return r;
 370 }
 371
 372 d0_bignum_t *d0_bignum_add(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 373 {
 374         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 375         mp_add((mp_int *) &a->z, (mp_int *) &b->z, &r->z);
 376         return r;
 377 }
 378
 379 d0_bignum_t *d0_bignum_sub(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 380 {
 381         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 382         mp_sub((mp_int *) &a->z, (mp_int *) &b->z, &r->z);
 383         return r;
 384 }
 385
 386 d0_bignum_t *d0_bignum_mul(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 387 {
 388         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 389         mp_mul((mp_int *) &a->z, (mp_int *) &b->z, &r->z);
 390         return r;
 391 }
 392
 393 d0_bignum_t *d0_bignum_divmod(d0_bignum_t *q, d0_bignum_t *m, const d0_bignum_t *a, const d0_bignum_t *b)
 394 {
 395         if(!q && !m)
 396                 m = d0_bignum_new();
 397         if(q)
 398                 mp_div((mp_int *) &a->z, (mp_int *) &b->z, &q->z, m ? &m->z : NULL);
 399         else
 400                 mp_mod((mp_int *) &a->z, (mp_int *) &b->z, &m->z);
 401         if(m)
 402                 return m;
 403         else
 404                 return q;
 405 }
 406
 407 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)
 408 {
 409         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 410         mp_addmod((mp_int *) &a->z, (mp_int *) &b->z, (mp_int *) &m->z, &r->z);
 411         return r;
 412 }
 413
 414 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)
 415 {
 416         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 417         mp_submod((mp_int *) &a->z, (mp_int *) &b->z, (mp_int *) &m->z, &r->z);
 418         return r;
 419 }
 420
 421 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)
 422 {
 423         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 424         mp_mulmod((mp_int *) &a->z, (mp_int *) &b->z, (mp_int *) &m->z, &r->z);
 425         return r;
 426 }
 427
 428 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)
 429 {
 430         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 431         mp_exptmod((mp_int *) &a->z, (mp_int *) &b->z, (mp_int *) &m->z, &r->z);
 432         return r;
 433 }
 434
 435 D0_BOOL d0_bignum_mod_inv(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *m)
 436 {
 437         // here, r MUST be set, as otherwise we cannot return error state!
 438         return mp_invmod((mp_int *) &a->z, (mp_int *) &m->z, &r->z) == MP_OKAY;
 439 }
 440
 441 int d0_bignum_isprime(const d0_bignum_t *r, int param)
 442 {
 443         int ret = 0;
 444         if(param < 1)
 445                 param = 1;
 446         mp_prime_is_prime((mp_int *) &r->z, param, &ret);
 447         return ret;
 448 }
 449
 450 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)
 451 {
 452         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 453         if(s || t)
 454                 mp_exteuclid((mp_int *) &a->z, (mp_int *) &b->z, s ? &s->z : NULL, t ? &t->z : NULL, &r->z);
 455         else
 456                 mp_gcd((mp_int *) &a->z, (mp_int *) &b->z, &r->z);
 457         return r;
 458 }
 459
 460 char *d0_bignum_tostring(const d0_bignum_t *x, unsigned int base)
 461 {
 462         static __thread char str[65536];
 463         mp_toradix_n((mp_int *) &x->z, str, base, sizeof(str));
 464         return str;
 465 }