d0_bignum-gmp.c

   1 /*
   2 Blind-ID library for user identification using RSA blind signatures
   3 Copyright (C) 2010  Rudolf Polzer
   4
   5 This library is free software; you can redistribute it and/or
   6 modify it under the terms of the GNU Lesser General Public
   7 License as published by the Free Software Foundation; either
   8 version 2.1 of the License, or (at your option) any later version.
   9
  10 This library is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public
  16 License along with this library; if not, write to the Free Software
  17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18 */
  19
  20 #include "d0_bignum.h"
  21
  22 #include <gmp.h>
  23 #include <string.h>
  24 #include <stdlib.h>
  25
  26 struct d0_bignum_s
  27 {
  28         mpz_t z;
  29 };
  30
  31 static gmp_randstate_t RANDSTATE;
  32 static d0_bignum_t temp;
  33
  34 #include <time.h>
  35 #include <stdio.h>
  36 void d0_bignum_INITIALIZE(void)
  37 {
  38         FILE *f;
  39         d0_bignum_init(&temp);
  40         gmp_randinit_mt(RANDSTATE);
  41         gmp_randseed_ui(RANDSTATE, time(NULL));
  42         f = fopen("/dev/urandom", "rb");
  43         if(!f)
  44                 f = fopen("/dev/random", "rb");
  45         if(f)
  46         {
  47                 unsigned char buf[256];
  48                 setbuf(f, NULL);
  49                 if(fread(buf, sizeof(buf), 1, f) == 1)
  50                 {
  51                         mpz_import(temp.z, sizeof(buf), 1, 1, 0, 0, buf);
  52                         gmp_randseed(RANDSTATE, temp.z);
  53                 }
  54                 fclose(f);
  55         }
  56 }
  57
  58 void d0_bignum_SHUTDOWN(void)
  59 {
  60         d0_bignum_clear(&temp);
  61         gmp_randclear(RANDSTATE);
  62 }
  63
  64 BOOL d0_iobuf_write_bignum(d0_iobuf_t *buf, const d0_bignum_t *bignum)
  65 {
  66         static unsigned char numbuf[65536];
  67         size_t count = 0;
  68         numbuf[0] = mpz_sgn(bignum->z) & 3;
  69         if((numbuf[0] & 3) != 0) // nonzero
  70         {
  71                 count = (mpz_sizeinbase(bignum->z, 2) + 7) / 8;
  72                 if(count > sizeof(numbuf) - 1)
  73                         return 0;
  74                 mpz_export(numbuf+1, &count, 1, 1, 0, 0, bignum->z);
  75         }
  76         return d0_iobuf_write_packet(buf, numbuf, count + 1);
  77 }
  78
  79 d0_bignum_t *d0_iobuf_read_bignum(d0_iobuf_t *buf, d0_bignum_t *bignum)
  80 {
  81         static unsigned char numbuf[65536];
  82         size_t count = sizeof(numbuf);
  83         if(!d0_iobuf_read_packet(buf, numbuf, &count))
  84                 return NULL;
  85         if(count < 1)
  86                 return NULL;
  87         if(!bignum) bignum = d0_bignum_new(); if(!bignum) return NULL;
  88         if(numbuf[0] & 3) // nonzero
  89         {
  90                 mpz_import(bignum->z, count-1, 1, 1, 0, 0, numbuf+1);
  91                 if(numbuf[0] & 2) // negative
  92                         mpz_neg(bignum->z, bignum->z);
  93         }
  94         else // zero
  95         {
  96                 mpz_set_ui(bignum->z, 0);
  97         }
  98         return bignum;
  99 }
 100
 101 ssize_t d0_bignum_export_unsigned(const d0_bignum_t *bignum, void *buf, size_t bufsize)
 102 {
 103         size_t count;
 104         count = (mpz_sizeinbase(bignum->z, 2) + 7) / 8;
 105         if(count > bufsize)
 106                 return -1;
 107         if(bufsize > count)
 108         {
 109                 // pad from left (big endian numbers!)
 110                 memset(buf, 0, bufsize - count);
 111                 buf += bufsize - count;
 112         }
 113         bufsize = count;
 114         mpz_export(buf, &bufsize, 1, 1, 0, 0, bignum->z);
 115         if(bufsize > count)
 116         {
 117                 // REALLY BAD
 118                 // mpz_sizeinbase lied to us
 119                 // buffer overflow
 120                 // there is no sane way whatsoever to handle this
 121                 abort();
 122         }
 123         if(bufsize < count)
 124         {
 125                 // BAD
 126                 // mpz_sizeinbase lied to us
 127                 // move the number
 128                 if(bufsize == 0)
 129                 {
 130                         memset(buf, 0, count);
 131                 }
 132                 else
 133                 {
 134                         memmove(buf + count - bufsize, buf, bufsize);
 135                         memset(buf, 0, count - bufsize);
 136                 }
 137         }
 138         return bufsize;
 139 }
 140
 141 d0_bignum_t *d0_bignum_import_unsigned(d0_bignum_t *bignum, const void *buf, size_t bufsize)
 142 {
 143         size_t count;
 144         if(!bignum) bignum = d0_bignum_new(); if(!bignum) return NULL;
 145         mpz_import(bignum->z, bufsize, 1, 1, 0, 0, buf);
 146         return bignum;
 147 }
 148
 149 d0_bignum_t *d0_bignum_new(void)
 150 {
 151         d0_bignum_t *b = d0_malloc(sizeof(d0_bignum_t));
 152         mpz_init(b->z);
 153         return b;
 154 }
 155
 156 void d0_bignum_free(d0_bignum_t *a)
 157 {
 158         mpz_clear(a->z);
 159         d0_free(a);
 160 }
 161
 162 void d0_bignum_init(d0_bignum_t *b)
 163 {
 164         mpz_init(b->z);
 165 }
 166
 167 void d0_bignum_clear(d0_bignum_t *a)
 168 {
 169         mpz_clear(a->z);
 170 }
 171
 172 size_t d0_bignum_size(const d0_bignum_t *r)
 173 {
 174         return mpz_sizeinbase(r->z, 2);
 175 }
 176
 177 int d0_bignum_cmp(const d0_bignum_t *a, const d0_bignum_t *b)
 178 {
 179         return mpz_cmp(a->z, b->z);
 180 }
 181
 182 d0_bignum_t *d0_bignum_rand_range(d0_bignum_t *r, const d0_bignum_t *min, const d0_bignum_t *max)
 183 {
 184         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 185         mpz_sub(temp.z, max->z, min->z);
 186         mpz_urandomm(r->z, RANDSTATE, temp.z);
 187         mpz_add(r->z, r->z, min->z);
 188         return r;
 189 }
 190
 191 d0_bignum_t *d0_bignum_rand_bit_atmost(d0_bignum_t *r, size_t n)
 192 {
 193         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 194         mpz_urandomb(r->z, RANDSTATE, n);
 195         return r;
 196 }
 197
 198 d0_bignum_t *d0_bignum_rand_bit_exact(d0_bignum_t *r, size_t n)
 199 {
 200         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 201         mpz_urandomb(r->z, RANDSTATE, n-1);
 202         mpz_setbit(r->z, n-1);
 203         return r;
 204 }
 205
 206 d0_bignum_t *d0_bignum_zero(d0_bignum_t *r)
 207 {
 208         return d0_bignum_int(r, 0);
 209 }
 210
 211 d0_bignum_t *d0_bignum_one(d0_bignum_t *r)
 212 {
 213         return d0_bignum_int(r, 1);
 214 }
 215
 216 d0_bignum_t *d0_bignum_int(d0_bignum_t *r, int n)
 217 {
 218         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 219         mpz_set_si(r->z, n);
 220         return r;
 221 }
 222
 223 d0_bignum_t *d0_bignum_mov(d0_bignum_t *r, const d0_bignum_t *a)
 224 {
 225         if(r == a)
 226                 return r; // trivial
 227         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 228         mpz_set(r->z, a->z);
 229         return r;
 230 }
 231
 232 d0_bignum_t *d0_bignum_neg(d0_bignum_t *r, const d0_bignum_t *a)
 233 {
 234         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 235         mpz_neg(r->z, a->z);
 236         return r;
 237 }
 238
 239 d0_bignum_t *d0_bignum_shl(d0_bignum_t *r, const d0_bignum_t *a, ssize_t n)
 240 {
 241         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 242         if(n > 0)
 243                 mpz_mul_2exp(r->z, a->z, n);
 244         else if(n < 0)
 245                 mpz_fdiv_q_2exp(r->z, a->z, -n);
 246         else
 247                 mpz_set(r->z, a->z);
 248         return r;
 249 }
 250
 251 d0_bignum_t *d0_bignum_add(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 252 {
 253         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 254         mpz_add(r->z, a->z, b->z);
 255         return r;
 256 }
 257
 258 d0_bignum_t *d0_bignum_sub(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 259 {
 260         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 261         mpz_sub(r->z, a->z, b->z);
 262         return r;
 263 }
 264
 265 d0_bignum_t *d0_bignum_mul(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 266 {
 267         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 268         mpz_mul(r->z, a->z, b->z);
 269         return r;
 270 }
 271
 272 d0_bignum_t *d0_bignum_divmod(d0_bignum_t *q, d0_bignum_t *m, const d0_bignum_t *a, const d0_bignum_t *b)
 273 {
 274         if(!q && !m)
 275                 m = d0_bignum_new();
 276         if(q)
 277                 if(m)
 278                         mpz_fdiv_qr(q->z, m->z, a->z, b->z);
 279                 else
 280                         mpz_fdiv_q(q->z, a->z, b->z);
 281         else
 282                 mpz_fdiv_r(m->z, a->z, b->z);
 283         if(m)
 284                 return m;
 285         else
 286                 return q;
 287 }
 288
 289 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)
 290 {
 291         r = d0_bignum_add(r, a, b);
 292         mpz_fdiv_r(r->z, r->z, m->z);
 293         return r;
 294 }
 295
 296 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)
 297 {
 298         r = d0_bignum_mul(r, a, b);
 299         mpz_fdiv_r(r->z, r->z, m->z);
 300         return r;
 301 }
 302
 303 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)
 304 {
 305         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 306         mpz_powm(r->z, a->z, b->z, m->z);
 307         return r;
 308 }
 309
 310 BOOL d0_bignum_mod_inv(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *m)
 311 {
 312         // here, r MUST be set, as otherwise we cannot return error state!
 313         return mpz_invert(r->z, a->z, m->z);
 314 }
 315
 316 int d0_bignum_isprime(d0_bignum_t *r, int param)
 317 {
 318         return mpz_probab_prime_p(r->z, param);
 319 }
 320
 321 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)
 322 {
 323         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 324         if(s)
 325                 mpz_gcdext(r->z, s->z, t ? t->z : NULL, a->z, b->z);
 326         else if(t)
 327                 mpz_gcdext(r->z, t->z, NULL, b->z, a->z);
 328         else
 329                 mpz_gcd(r->z, a->z, b->z);
 330         return r;
 331 }
 332
 333 char *d0_bignum_tostring(const d0_bignum_t *x, unsigned int base)
 334 {
 335         return mpz_get_str(NULL, base, x->z);
 336 }