d0_bignum-openssl.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 <assert.h>
  23 #include <string.h>
  24 #include <openssl/bn.h>
  25
  26 struct d0_bignum_s
  27 {
  28         BIGNUM z;
  29 };
  30
  31 static d0_bignum_t temp;
  32 static BN_CTX *ctx;
  33
  34 #include <time.h>
  35 #include <stdio.h>
  36
  37 WARN_UNUSED_RESULT BOOL d0_bignum_INITIALIZE(void)
  38 {
  39         ctx = BN_CTX_new();
  40         d0_bignum_init(&temp);
  41         return 1;
  42 }
  43
  44 void d0_bignum_SHUTDOWN(void)
  45 {
  46         d0_bignum_clear(&temp);
  47         BN_CTX_free(ctx);
  48         ctx = NULL;
  49 }
  50
  51 BOOL d0_iobuf_write_bignum(d0_iobuf_t *buf, const d0_bignum_t *bignum)
  52 {
  53         static unsigned char numbuf[65536];
  54         size_t count = 0;
  55         numbuf[0] = BN_is_zero(&bignum->z) ? 0 : BN_is_negative(&bignum->z) ? 3 : 1;
  56         if((numbuf[0] & 3) != 0) // nonzero
  57         {
  58                 count = BN_num_bytes(&bignum->z);
  59                 if(count > sizeof(numbuf) - 1)
  60                         return 0;
  61                 BN_bn2bin(&bignum->z, numbuf+1);
  62         }
  63         return d0_iobuf_write_packet(buf, numbuf, count + 1);
  64 }
  65
  66 d0_bignum_t *d0_iobuf_read_bignum(d0_iobuf_t *buf, d0_bignum_t *bignum)
  67 {
  68         static unsigned char numbuf[65536];
  69         size_t count = sizeof(numbuf);
  70         if(!d0_iobuf_read_packet(buf, numbuf, &count))
  71                 return NULL;
  72         if(count < 1)
  73                 return NULL;
  74         if(!bignum) bignum = d0_bignum_new(); if(!bignum) return NULL;
  75         if(numbuf[0] & 3) // nonzero
  76         {
  77                 BN_bin2bn(numbuf+1, count-1, &bignum->z);
  78                 if(numbuf[0] & 2) // negative
  79                         BN_set_negative(&bignum->z, 1);
  80         }
  81         else // zero
  82         {
  83                 BN_zero(&bignum->z);
  84         }
  85         return bignum;
  86 }
  87
  88 ssize_t d0_bignum_export_unsigned(const d0_bignum_t *bignum, void *buf, size_t bufsize)
  89 {
  90         size_t count;
  91         count = BN_num_bytes(&bignum->z);
  92         if(count > bufsize)
  93                 return -1;
  94         if(bufsize > count)
  95         {
  96                 // pad from left (big endian numbers!)
  97                 memset(buf, 0, bufsize - count);
  98                 buf += bufsize - count;
  99         }
 100         BN_bn2bin(&bignum->z, buf);
 101         return bufsize;
 102 }
 103
 104 d0_bignum_t *d0_bignum_import_unsigned(d0_bignum_t *bignum, const void *buf, size_t bufsize)
 105 {
 106         size_t count;
 107         if(!bignum) bignum = d0_bignum_new(); if(!bignum) return NULL;
 108         BN_bin2bn(buf, bufsize, &bignum->z);
 109         return bignum;
 110 }
 111
 112 d0_bignum_t *d0_bignum_new(void)
 113 {
 114         d0_bignum_t *b = d0_malloc(sizeof(d0_bignum_t));
 115         BN_init(&b->z);
 116         return b;
 117 }
 118
 119 void d0_bignum_free(d0_bignum_t *a)
 120 {
 121         BN_free(&a->z);
 122         d0_free(a);
 123 }
 124
 125 void d0_bignum_init(d0_bignum_t *b)
 126 {
 127         BN_init(&b->z);
 128 }
 129
 130 void d0_bignum_clear(d0_bignum_t *a)
 131 {
 132         BN_free(&a->z);
 133 }
 134
 135 size_t d0_bignum_size(const d0_bignum_t *r)
 136 {
 137         return BN_num_bits(&r->z);
 138 }
 139
 140 int d0_bignum_cmp(const d0_bignum_t *a, const d0_bignum_t *b)
 141 {
 142         return BN_cmp(&a->z, &b->z);
 143 }
 144
 145 d0_bignum_t *d0_bignum_rand_range(d0_bignum_t *r, const d0_bignum_t *min, const d0_bignum_t *max)
 146 {
 147         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 148         BN_sub(&temp.z, &max->z, &min->z);
 149         BN_rand_range(&r->z, &temp.z);
 150         BN_add(&r->z, &r->z, &min->z);
 151         return r;
 152 }
 153
 154 d0_bignum_t *d0_bignum_rand_bit_atmost(d0_bignum_t *r, size_t n)
 155 {
 156         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 157         BN_rand(&r->z, n, -1, 0);
 158         return r;
 159 }
 160
 161 d0_bignum_t *d0_bignum_rand_bit_exact(d0_bignum_t *r, size_t n)
 162 {
 163         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 164         BN_rand(&r->z, n, 0, 0);
 165         return r;
 166 }
 167
 168 d0_bignum_t *d0_bignum_zero(d0_bignum_t *r)
 169 {
 170         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 171         BN_zero(&r->z);
 172         return r;
 173 }
 174
 175 d0_bignum_t *d0_bignum_one(d0_bignum_t *r)
 176 {
 177         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 178         BN_one(&r->z);
 179         return r;
 180 }
 181
 182 d0_bignum_t *d0_bignum_int(d0_bignum_t *r, int n)
 183 {
 184         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 185         BN_set_word(&r->z, n);
 186         return r;
 187 }
 188
 189 d0_bignum_t *d0_bignum_mov(d0_bignum_t *r, const d0_bignum_t *a)
 190 {
 191         if(r == a)
 192                 return r; // trivial
 193         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 194         BN_copy(&r->z, &a->z);
 195         return r;
 196 }
 197
 198 d0_bignum_t *d0_bignum_neg(d0_bignum_t *r, const d0_bignum_t *a)
 199 {
 200         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 201         if(r != a)
 202                 BN_copy(&r->z, &a->z);
 203         BN_set_negative(&r->z, !BN_is_negative(&r->z));
 204         return r;
 205 }
 206
 207 d0_bignum_t *d0_bignum_shl(d0_bignum_t *r, const d0_bignum_t *a, ssize_t n)
 208 {
 209         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 210         if(n > 0)
 211                 BN_lshift(&r->z, &a->z, n);
 212         else if(n < 0)
 213                 BN_rshift(&r->z, &a->z, -n);
 214         else if(r != a)
 215                 BN_copy(&r->z, &a->z);
 216         return r;
 217 }
 218
 219 d0_bignum_t *d0_bignum_add(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 220 {
 221         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 222         BN_add(&r->z, &a->z, &b->z);
 223         return r;
 224 }
 225
 226 d0_bignum_t *d0_bignum_sub(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 227 {
 228         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 229         BN_sub(&r->z, &a->z, &b->z);
 230         return r;
 231 }
 232
 233 d0_bignum_t *d0_bignum_mul(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *b)
 234 {
 235         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 236         BN_mul(&r->z, &a->z, &b->z, ctx);
 237         return r;
 238 }
 239
 240 d0_bignum_t *d0_bignum_divmod(d0_bignum_t *q, d0_bignum_t *m, const d0_bignum_t *a, const d0_bignum_t *b)
 241 {
 242         if(!q && !m)
 243                 m = d0_bignum_new();
 244         if(q)
 245         {
 246                 if(m)
 247                         BN_div(&q->z, &m->z, &a->z, &b->z, ctx);
 248                 else
 249                         BN_div(&q->z, NULL, &a->z, &b->z, ctx);
 250                 assert(!"I know this code is broken (rounds towards zero), need handle negative correctly");
 251         }
 252         else
 253                 BN_nnmod(&m->z, &a->z, &b->z, ctx);
 254         if(m)
 255                 return m;
 256         else
 257                 return q;
 258 }
 259
 260 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)
 261 {
 262         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 263         BN_mod_add(&r->z, &a->z, &b->z, &m->z, ctx);
 264         return r;
 265 }
 266
 267 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)
 268 {
 269         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 270         BN_mod_mul(&r->z, &a->z, &b->z, &m->z, ctx);
 271         return r;
 272 }
 273
 274 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)
 275 {
 276         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 277         BN_mod_exp(&r->z, &a->z, &b->z, &m->z, ctx);
 278         return r;
 279 }
 280
 281 BOOL d0_bignum_mod_inv(d0_bignum_t *r, const d0_bignum_t *a, const d0_bignum_t *m)
 282 {
 283         // here, r MUST be set, as otherwise we cannot return error state!
 284         return !!BN_mod_inverse(&r->z, &a->z, &m->z, ctx);
 285 }
 286
 287 int d0_bignum_isprime(d0_bignum_t *r, int param)
 288 {
 289         return BN_is_prime(&r->z, param, NULL, ctx, NULL);
 290 }
 291
 292 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)
 293 {
 294         if(!r) r = d0_bignum_new(); if(!r) return NULL;
 295         if(s)
 296                 assert(!"Extended gcd not implemented");
 297         else if(t)
 298                 assert(!"Extended gcd not implemented");
 299         else
 300                 BN_gcd(&r->z, &a->z, &b->z, ctx);
 301         return r;
 302 }
 303
 304 char *d0_bignum_tostring(const d0_bignum_t *x, unsigned int base)
 305 {
 306         if(base == 10)
 307                 return BN_bn2dec(&x->z);
 308         else if(base == 16)
 309                 return BN_bn2hex(&x->z);
 310         else
 311                 assert(!"Other bases not implemented");
 312 }