src/bignum.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2012 The Bitcoin developers
   3 // Distributed under the MIT/X11 software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5 #ifndef BITCOIN_BIGNUM_H
   6 #define BITCOIN_BIGNUM_H
   7
   8 #include <stdexcept>
   9 #include <vector>
  10 #include <openssl/bn.h>
  11 #include "util.h"
  12
  13 /** Errors thrown by the bignum class */
  14 class bignum_error : public std::runtime_error
  15 {
  16 public:
  17     explicit bignum_error(const std::string& str) : std::runtime_error(str) {}
  18 };
  19
  20
  21 /** RAII encapsulated BN_CTX (OpenSSL bignum context) */
  22 class CAutoBN_CTX
  23 {
  24 protected:
  25     BN_CTX* pctx;
  26     BN_CTX* operator=(BN_CTX* pnew) { return pctx = pnew; }
  27
  28 public:
  29     CAutoBN_CTX()
  30     {
  31         pctx = BN_CTX_new();
  32         if (pctx == NULL)
  33             throw bignum_error("CAutoBN_CTX : BN_CTX_new() returned NULL");
  34     }
  35
  36     ~CAutoBN_CTX()
  37     {
  38         if (pctx != NULL)
  39             BN_CTX_free(pctx);
  40     }
  41
  42     operator BN_CTX*() { return pctx; }
  43     BN_CTX& operator*() { return *pctx; }
  44     BN_CTX** operator&() { return &pctx; }
  45     bool operator!() { return (pctx == NULL); }
  46 };
  47
  48
  49 /** C++ wrapper for BIGNUM (OpenSSL bignum) */
  50 class CBigNum
  51 {
  52 private:
  53     BIGNUM* bn;
  54 public:
  55     CBigNum()
  56     {
  57         bn = BN_new();
  58     }
  59
  60     CBigNum(const CBigNum& b)
  61     {
  62         BIGNUM *dup = BN_dup(b.bn);
  63         if (!dup)
  64         {
  65             throw bignum_error("CBigNum::CBigNum(const CBigNum&) : BN_dup failed");
  66         }
  67         bn = dup;
  68     }
  69
  70     CBigNum& operator=(const CBigNum& b)
  71     {
  72         BIGNUM *dup = BN_dup(b.bn);
  73         if (!dup)
  74         {
  75             throw bignum_error("CBigNum::operator= : BN_dup failed");
  76         }
  77         bn = dup;
  78         return (*this);
  79     }
  80
  81     CBigNum(const BIGNUM *bnp) {
  82         BIGNUM *dup = BN_dup(bnp);
  83         if (!dup)
  84         {
  85             throw bignum_error("CBigNum::CBigNum(const BIGNUM*) : BN_dup failed");
  86         }
  87         bn = dup;
  88     }
  89
  90     ~CBigNum()
  91     {
  92         BN_clear_free(bn);
  93     }
  94
  95     CBigNum(bool n)     { bn = BN_new(); setuint32(n); }
  96
  97     CBigNum(int8_t  n)  { bn = BN_new(); if (n >= 0) setuint32(n); else setint64(n); }
  98     CBigNum(int16_t n)  { bn = BN_new(); if (n >= 0) setuint32(n); else setint64(n); }
  99     CBigNum(int32_t n)  { bn = BN_new(); if (n >= 0) setuint32(n); else setint64(n); }
 100     CBigNum(int64_t n)  { bn = BN_new(); if (n >= 0) setuint64(n); else setint64(n); }
 101
 102     CBigNum(uint8_t  n) { bn = BN_new(); setuint32(n); }
 103     CBigNum(uint16_t n) { bn = BN_new(); setuint32(n); }
 104     CBigNum(uint32_t n) { bn = BN_new(); setuint32(n); }
 105     CBigNum(uint64_t n) { bn = BN_new(); setuint64(n); }
 106
 107     explicit CBigNum(uint256 n) { bn = BN_new(); setuint256(n); }
 108     explicit CBigNum(const std::vector<uint8_t>& vch)
 109     {
 110         bn = BN_new();
 111         setvch(vch);
 112     }
 113
 114     /** Generates a cryptographically secure random number between zero and range exclusive
 115     * i.e. 0 < returned number < range
 116     * @param range The upper bound on the number.
 117     * @return
 118     */
 119     static CBigNum  randBignum(const CBigNum& range) {
 120         CBigNum ret;
 121         if(!BN_rand_range(ret.bn, range.bn)){
 122             throw bignum_error("CBigNum:rand element : BN_rand_range failed");
 123         }
 124         return ret;
 125     }
 126
 127     /** Generates a cryptographically secure random k-bit number
 128     * @param k The bit length of the number.
 129     * @return
 130     */
 131     static CBigNum RandKBitBigum(const uint32_t k){
 132         CBigNum ret;
 133         if(!BN_rand(ret.bn, k, -1, 0)){
 134             throw bignum_error("CBigNum:rand element : BN_rand failed");
 135         }
 136         return ret;
 137     }
 138
 139     /**Returns the size in bits of the underlying bignum.
 140      *
 141      * @return the size
 142      */
 143     int bitSize() const{
 144         return  BN_num_bits(bn);
 145     }
 146
 147
 148     void setuint32(uint32_t n)
 149     {
 150         if (!BN_set_word(bn, n))
 151             throw bignum_error("CBigNum conversion from uint32_t : BN_set_word failed");
 152     }
 153
 154     uint32_t getuint32() const
 155     {
 156         return BN_get_word(bn);
 157     }
 158
 159     int32_t getint32() const
 160     {
 161         uint64_t n = BN_get_word(bn);
 162         if (!BN_is_negative(bn))
 163             return (n > (uint64_t)std::numeric_limits<int32_t>::max() ? std::numeric_limits<int32_t>::max() : (int32_t)n);
 164         else
 165             return (n > (uint64_t)std::numeric_limits<int32_t>::max() ? std::numeric_limits<int32_t>::min() : -(int32_t)n);
 166     }
 167
 168     void setint64(int64_t sn)
 169     {
 170         uint8_t pch[sizeof(sn) + 6];
 171         uint8_t* p = pch + 4;
 172         bool fNegative;
 173         uint64_t n;
 174
 175         if (sn < (int64_t)0)
 176         {
 177             // Since the minimum signed integer cannot be represented as positive so long as its type is signed, and it's not well-defined what happens if you make it unsigned before negating it, we instead increment the negative integer by 1, convert it, then increment the (now positive) unsigned integer by 1 to compensate
 178             n = -(sn + 1);
 179             ++n;
 180             fNegative = true;
 181         } else {
 182             n = sn;
 183             fNegative = false;
 184         }
 185
 186         bool fLeadingZeroes = true;
 187         for (int i = 0; i < 8; i++)
 188         {
 189             uint8_t c = (n >> 56) & 0xff;
 190             n <<= 8;
 191             if (fLeadingZeroes)
 192             {
 193                 if (c == 0)
 194                     continue;
 195                 if (c & 0x80)
 196                     *p++ = (fNegative ? 0x80 : 0);
 197                 else if (fNegative)
 198                     c |= 0x80;
 199                 fLeadingZeroes = false;
 200             }
 201             *p++ = c;
 202         }
 203         uint32_t nSize = (uint32_t) (p - (pch + 4));
 204         pch[0] = (nSize >> 24) & 0xff;
 205         pch[1] = (nSize >> 16) & 0xff;
 206         pch[2] = (nSize >> 8) & 0xff;
 207         pch[3] = (nSize) & 0xff;
 208         BN_mpi2bn(pch, (int)(p - pch), bn);
 209     }
 210
 211     uint64_t getuint64()
 212     {
 213         size_t nSize = BN_bn2mpi(bn, NULL);
 214         if (nSize < 4)
 215             return 0;
 216         std::vector<uint8_t> vch(nSize);
 217         BN_bn2mpi(bn, &vch[0]);
 218         if (vch.size() > 4)
 219             vch[4] &= 0x7f;
 220         uint64_t n = 0;
 221         for (size_t i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
 222             ((uint8_t*)&n)[i] = vch[j];
 223         return n;
 224     }
 225
 226     //supress msvc C4127: conditional expression is constant
 227     inline bool check(bool value) {return value;}
 228
 229     void setuint64(uint64_t n)
 230     {
 231         // Use BN_set_word if word size is sufficient for uint64_t
 232         if (check(sizeof(n) <= sizeof(BN_ULONG)))
 233         {
 234             if (!BN_set_word(bn, (BN_ULONG)n))
 235                 throw bignum_error("CBigNum conversion from uint64_t : BN_set_word failed");
 236             return;
 237         }
 238
 239         uint8_t pch[sizeof(n) + 6];
 240         uint8_t* p = pch + 4;
 241         bool fLeadingZeroes = true;
 242         for (int i = 0; i < 8; i++)
 243         {
 244             uint8_t c = (n >> 56) & 0xff;
 245             n <<= 8;
 246             if (fLeadingZeroes)
 247             {
 248                 if (c == 0)
 249                     continue;
 250                 if (c & 0x80)
 251                     *p++ = 0;
 252                 fLeadingZeroes = false;
 253             }
 254             *p++ = c;
 255         }
 256         uint32_t nSize = (uint32_t) (p - (pch + 4));
 257         pch[0] = (nSize >> 24) & 0xff;
 258         pch[1] = (nSize >> 16) & 0xff;
 259         pch[2] = (nSize >> 8) & 0xff;
 260         pch[3] = (nSize) & 0xff;
 261         BN_mpi2bn(pch, (int)(p - pch), bn);
 262     }
 263
 264     void setuint160(uint160 n)
 265     {
 266         uint8_t pch[sizeof(n) + 6];
 267         uint8_t* p = pch + 4;
 268         bool fLeadingZeroes = true;
 269         uint8_t* pbegin = (uint8_t*)&n;
 270         uint8_t* psrc = pbegin + sizeof(n);
 271         while (psrc != pbegin)
 272         {
 273             uint8_t c = *(--psrc);
 274             if (fLeadingZeroes)
 275             {
 276                 if (c == 0)
 277                     continue;
 278                 if (c & 0x80)
 279                     *p++ = 0;
 280                 fLeadingZeroes = false;
 281             }
 282             *p++ = c;
 283         }
 284         uint32_t nSize = (uint32_t) (p - (pch + 4));
 285         pch[0] = (nSize >> 24) & 0xff;
 286         pch[1] = (nSize >> 16) & 0xff;
 287         pch[2] = (nSize >> 8) & 0xff;
 288         pch[3] = (nSize >> 0) & 0xff;
 289         BN_mpi2bn(pch, (int) (p - pch), bn);
 290     }
 291
 292     uint160 getuint160() const
 293     {
 294         unsigned int nSize = BN_bn2mpi(bn, NULL);
 295         if (nSize < 4)
 296             return 0;
 297         std::vector<uint8_t> vch(nSize);
 298         BN_bn2mpi(bn, &vch[0]);
 299         if (vch.size() > 4)
 300             vch[4] &= 0x7f;
 301         uint160 n = 0;
 302         for (size_t i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
 303             ((uint8_t*)&n)[i] = vch[j];
 304         return n;
 305     }
 306
 307     void setuint256(uint256 n)
 308     {
 309         uint8_t pch[sizeof(n) + 6];
 310         uint8_t* p = pch + 4;
 311         bool fLeadingZeroes = true;
 312         uint8_t* pbegin = (uint8_t*)&n;
 313         uint8_t* psrc = pbegin + sizeof(n);
 314         while (psrc != pbegin)
 315         {
 316             uint8_t c = *(--psrc);
 317             if (fLeadingZeroes)
 318             {
 319                 if (c == 0)
 320                     continue;
 321                 if (c & 0x80)
 322                     *p++ = 0;
 323                 fLeadingZeroes = false;
 324             }
 325             *p++ = c;
 326         }
 327         uint32_t nSize = (uint32_t) (p - (pch + 4));
 328         pch[0] = (nSize >> 24) & 0xff;
 329         pch[1] = (nSize >> 16) & 0xff;
 330         pch[2] = (nSize >> 8) & 0xff;
 331         pch[3] = (nSize >> 0) & 0xff;
 332         BN_mpi2bn(pch, (int) (p - pch), bn);
 333     }
 334
 335     uint256 getuint256() const
 336     {
 337         unsigned int nSize = BN_bn2mpi(bn, NULL);
 338         if (nSize < 4)
 339             return 0;
 340         std::vector<uint8_t> vch(nSize);
 341         BN_bn2mpi(bn, &vch[0]);
 342         if (vch.size() > 4)
 343             vch[4] &= 0x7f;
 344         uint256 n = 0;
 345         for (size_t i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
 346             ((uint8_t*)&n)[i] = vch[j];
 347         return n;
 348     }
 349
 350     void setBytes(const std::vector<uint8_t>& vchBytes)
 351     {
 352         BN_bin2bn(&vchBytes[0], (int) vchBytes.size(), bn);
 353     }
 354
 355     std::vector<uint8_t> getBytes() const
 356     {
 357         int nBytes = BN_num_bytes(bn);
 358
 359         std::vector<uint8_t> vchBytes(nBytes);
 360
 361         int n = BN_bn2bin(bn, &vchBytes[0]);
 362         if (n != nBytes) {
 363             throw bignum_error("CBigNum::getBytes : BN_bn2bin failed");
 364         }
 365
 366         return vchBytes;
 367     }
 368
 369     void setvch(const std::vector<uint8_t>& vch)
 370     {
 371         std::vector<uint8_t> vch2(vch.size() + 4);
 372         uint32_t nSize = (uint32_t) vch.size();
 373         // BIGNUM's byte stream format expects 4 bytes of
 374         // big endian size data info at the front
 375         vch2[0] = (nSize >> 24) & 0xff;
 376         vch2[1] = (nSize >> 16) & 0xff;
 377         vch2[2] = (nSize >> 8) & 0xff;
 378         vch2[3] = (nSize >> 0) & 0xff;
 379         // swap data to big endian
 380         reverse_copy(vch.begin(), vch.end(), vch2.begin() + 4);
 381         BN_mpi2bn(&vch2[0], (int) vch2.size(), bn);
 382     }
 383
 384     std::vector<uint8_t> getvch() const
 385     {
 386         unsigned int nSize = BN_bn2mpi(bn, NULL);
 387         if (nSize <= 4)
 388             return std::vector<uint8_t>();
 389         std::vector<uint8_t> vch(nSize);
 390         BN_bn2mpi(bn, &vch[0]);
 391         vch.erase(vch.begin(), vch.begin() + 4);
 392         reverse(vch.begin(), vch.end());
 393         return vch;
 394     }
 395
 396     CBigNum& SetCompact(uint32_t nCompact)
 397     {
 398         uint32_t nSize = nCompact >> 24;
 399         std::vector<uint8_t> vch(4 + nSize);
 400         vch[3] = nSize;
 401         if (nSize >= 1) vch[4] = (nCompact >> 16) & 0xff;
 402         if (nSize >= 2) vch[5] = (nCompact >> 8) & 0xff;
 403         if (nSize >= 3) vch[6] = (nCompact >> 0) & 0xff;
 404         BN_mpi2bn(&vch[0], (int) vch.size(), bn);
 405         return *this;
 406     }
 407
 408     uint32_t GetCompact() const
 409     {
 410         uint32_t nSize = BN_bn2mpi(bn, NULL);
 411         std::vector<uint8_t> vch(nSize);
 412         nSize -= 4;
 413         BN_bn2mpi(bn, &vch[0]);
 414         uint32_t nCompact = nSize << 24;
 415         if (nSize >= 1) nCompact |= (vch[4] << 16);
 416         if (nSize >= 2) nCompact |= (vch[5] << 8);
 417         if (nSize >= 3) nCompact |= (vch[6] << 0);
 418         return nCompact;
 419     }
 420
 421     void SetHex(const std::string& str)
 422     {
 423         // skip 0x
 424         const char* psz = str.c_str();
 425         while (isspace(*psz))
 426             psz++;
 427         bool fNegative = false;
 428         if (*psz == '-')
 429         {
 430             fNegative = true;
 431             psz++;
 432         }
 433         if (psz[0] == '0' && tolower(psz[1]) == 'x')
 434             psz += 2;
 435         while (isspace(*psz))
 436             psz++;
 437
 438         // hex string to bignum
 439         static const signed char phexdigit[256] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0 };
 440         *this = 0;
 441         while (isxdigit(*psz))
 442         {
 443             *this <<= 4;
 444             int n = phexdigit[(uint8_t)*psz++];
 445             *this += n;
 446         }
 447         if (fNegative)
 448             *this = 0 - *this;
 449     }
 450
 451     std::string ToString(int nBase=10) const
 452     {
 453         CAutoBN_CTX pctx;
 454         CBigNum bnBase = nBase;
 455         CBigNum bn0 = 0;
 456         std::string str;
 457         CBigNum bn = *this;
 458         BN_set_negative(bn.bn, false);
 459         CBigNum dv;
 460         CBigNum rem;
 461         if (BN_cmp(bn.bn, bn0.bn) == 0)
 462             return "0";
 463         while (BN_cmp(bn.bn, bn0.bn) > 0)
 464         {
 465             if (!BN_div(dv.bn, rem.bn, bn.bn, bnBase.bn, pctx))
 466                 throw bignum_error("CBigNum::ToString() : BN_div failed");
 467             bn = dv;
 468             uint32_t c = rem.getuint32();
 469             str += "0123456789abcdef"[c];
 470         }
 471         if (BN_is_negative(bn.bn))
 472             str += "-";
 473         reverse(str.begin(), str.end());
 474         return str;
 475     }
 476
 477     std::string GetHex() const
 478     {
 479         return ToString(16);
 480     }
 481
 482     BIGNUM* get() const {
 483         return BN_dup(bn);
 484     }
 485
 486     unsigned int GetSerializeSize(int nType=0, int nVersion=PROTOCOL_VERSION) const
 487     {
 488         return ::GetSerializeSize(getvch(), nType, nVersion);
 489     }
 490
 491     template<typename Stream>
 492     void Serialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION) const
 493     {
 494         ::Serialize(s, getvch(), nType, nVersion);
 495     }
 496
 497     template<typename Stream>
 498     void Unserialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION)
 499     {
 500         std::vector<uint8_t> vch;
 501         ::Unserialize(s, vch, nType, nVersion);
 502         setvch(vch);
 503     }
 504
 505     /**
 506     * exponentiation with an int. this^e
 507     * @param e the exponent as an int
 508     * @return
 509     */
 510     CBigNum pow(const int e) const {
 511         return this->pow(CBigNum(e));
 512     }
 513
 514     /**
 515      * exponentiation this^e
 516      * @param e the exponent
 517      * @return
 518      */
 519     CBigNum pow(const CBigNum& e) const {
 520         CAutoBN_CTX pctx;
 521         CBigNum ret;
 522         if (!BN_exp(ret.bn, bn, e.bn, pctx))
 523             throw bignum_error("CBigNum::pow : BN_exp failed");
 524         return ret;
 525     }
 526
 527     /**
 528      * modular multiplication: (this * b) mod m
 529      * @param b operand
 530      * @param m modulus
 531      */
 532     CBigNum mul_mod(const CBigNum& b, const CBigNum& m) const {
 533         CAutoBN_CTX pctx;
 534         CBigNum ret;
 535         if (!BN_mod_mul(ret.bn, bn, b.bn, m.bn, pctx))
 536             throw bignum_error("CBigNum::mul_mod : BN_mod_mul failed");
 537
 538         return ret;
 539     }
 540
 541     /**
 542      * modular exponentiation: this^e mod n
 543      * @param e exponent
 544      * @param m modulus
 545      */
 546     CBigNum pow_mod(const CBigNum& e, const CBigNum& m) const {
 547         CAutoBN_CTX pctx;
 548         CBigNum ret;
 549         if( e < 0){
 550             // g^-x = (g^-1)^x
 551             CBigNum inv = this->inverse(m);
 552             CBigNum posE = e * -1;
 553             if (!BN_mod_exp(ret.bn, inv.bn, posE.bn, m.bn, pctx))
 554                 throw bignum_error("CBigNum::pow_mod: BN_mod_exp failed on negative exponent");
 555         }else
 556             if (!BN_mod_exp(ret.bn, bn, e.bn, m.bn, pctx))
 557                 throw bignum_error("CBigNum::pow_mod : BN_mod_exp failed");
 558
 559         return ret;
 560     }
 561
 562     /**
 563     * Calculates the inverse of this element mod m.
 564     * i.e. i such this*i = 1 mod m
 565     * @param m the modu
 566     * @return the inverse
 567     */
 568     CBigNum inverse(const CBigNum& m) const {
 569         CAutoBN_CTX pctx;
 570         CBigNum ret;
 571         if (!BN_mod_inverse(ret.bn, bn, m.bn, pctx))
 572             throw bignum_error("CBigNum::inverse*= :BN_mod_inverse");
 573         return ret;
 574     }
 575
 576     /**
 577      * Generates a random (safe) prime of numBits bits
 578      * @param numBits the number of bits
 579      * @param safe true for a safe prime
 580      * @return the prime
 581      */
 582     static CBigNum generatePrime(const unsigned int numBits, bool safe = false) {
 583         CBigNum ret;
 584         if(!BN_generate_prime_ex(ret.bn, numBits, (safe == true), NULL, NULL, NULL))
 585             throw bignum_error("CBigNum::generatePrime*= :BN_generate_prime_ex");
 586         return ret;
 587     }
 588
 589     /**
 590      * Calculates the greatest common divisor (GCD) of two numbers.
 591      * @param m the second element
 592      * @return the GCD
 593      */
 594     CBigNum gcd( const CBigNum& b) const{
 595         CAutoBN_CTX pctx;
 596         CBigNum ret;
 597         if (!BN_gcd(ret.bn, bn, b.bn, pctx))
 598             throw bignum_error("CBigNum::gcd*= :BN_gcd");
 599         return ret;
 600     }
 601
 602     /**
 603     * Miller-Rabin primality test on this element
 604     * @param checks: optional, the number of Miller-Rabin tests to run
 605     * default causes error rate of 2^-80.
 606     * @return true if prime
 607     */
 608     bool isPrime(const int checks=BN_prime_checks) const {
 609         CAutoBN_CTX pctx;
 610         int ret = BN_is_prime_ex(bn, checks, pctx, NULL);
 611         if(ret < 0){
 612             throw bignum_error("CBigNum::isPrime :BN_is_prime");
 613         }
 614         return ret != 0;
 615     }
 616
 617     bool isOne() const {
 618         return BN_is_one(bn);
 619     }
 620
 621
 622     bool operator!() const
 623     {
 624         return BN_is_zero(bn);
 625     }
 626
 627     CBigNum& operator+=(const CBigNum& b)
 628     {
 629         if (!BN_add(bn, bn, b.bn))
 630             throw bignum_error("CBigNum::operator+= : BN_add failed");
 631         return *this;
 632     }
 633
 634     CBigNum& operator-=(const CBigNum& b)
 635     {
 636         *this = *this - b;
 637         return *this;
 638     }
 639
 640     CBigNum& operator*=(const CBigNum& b)
 641     {
 642         CAutoBN_CTX pctx;
 643         if (!BN_mul(bn, bn, b.bn, pctx))
 644             throw bignum_error("CBigNum::operator*= : BN_mul failed");
 645         return *this;
 646     }
 647
 648     CBigNum& operator/=(const CBigNum& b)
 649     {
 650         *this = *this / b;
 651         return *this;
 652     }
 653
 654     CBigNum& operator%=(const CBigNum& b)
 655     {
 656         *this = *this % b;
 657         return *this;
 658     }
 659
 660     CBigNum& operator<<=(unsigned int shift)
 661     {
 662         if (!BN_lshift(bn, bn, shift))
 663             throw bignum_error("CBigNum:operator<<= : BN_lshift failed");
 664         return *this;
 665     }
 666
 667     CBigNum& operator>>=(unsigned int shift)
 668     {
 669         // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
 670         //   if built on ubuntu 9.04 or 9.10, probably depends on version of OpenSSL
 671         CBigNum a = 1;
 672         a <<= shift;
 673         if (BN_cmp(a.bn, bn) > 0)
 674         {
 675             *this = 0;
 676             return *this;
 677         }
 678
 679         if (!BN_rshift(bn, bn, shift))
 680             throw bignum_error("CBigNum:operator>>= : BN_rshift failed");
 681         return *this;
 682     }
 683
 684
 685     CBigNum& operator++()
 686     {
 687         // prefix operator
 688         if (!BN_add(bn, bn, BN_value_one()))
 689             throw bignum_error("CBigNum::operator++ : BN_add failed");
 690         return *this;
 691     }
 692
 693     const CBigNum operator++(int)
 694     {
 695         // postfix operator
 696         const CBigNum ret = *this;
 697         ++(*this);
 698         return ret;
 699     }
 700
 701     CBigNum& operator--()
 702     {
 703         // prefix operator
 704         CBigNum r;
 705         if (!BN_sub(r.bn, bn, BN_value_one()))
 706             throw bignum_error("CBigNum::operator-- : BN_sub failed");
 707         *this = r;
 708         return *this;
 709     }
 710
 711     const CBigNum operator--(int)
 712     {
 713         // postfix operator
 714         const CBigNum ret = *this;
 715         --(*this);
 716         return ret;
 717     }
 718
 719     friend inline const CBigNum operator-(const CBigNum& a, const CBigNum& b);
 720     friend inline const CBigNum operator/(const CBigNum& a, const CBigNum& b);
 721     friend inline const CBigNum operator%(const CBigNum& a, const CBigNum& b);
 722     friend inline const CBigNum operator*(const CBigNum& a, const CBigNum& b);
 723     friend inline const CBigNum operator+(const CBigNum& a, const CBigNum& b);
 724     friend inline const CBigNum operator*(const CBigNum& a);
 725
 726     friend inline const CBigNum operator-(const CBigNum& a);
 727     friend inline const CBigNum operator<<(const CBigNum& a, unsigned int shift);
 728
 729     friend inline bool operator==(const CBigNum& a, const CBigNum& b);
 730     friend inline bool operator!=(const CBigNum& a, const CBigNum& b);
 731     friend inline bool operator<=(const CBigNum& a, const CBigNum& b);
 732     friend inline bool operator>=(const CBigNum& a, const CBigNum& b);
 733     friend inline bool operator<(const CBigNum& a, const CBigNum& b);
 734     friend inline bool operator>(const CBigNum& a, const CBigNum& b);
 735     friend inline std::ostream& operator<<(std::ostream &strm, const CBigNum &b);
 736 };
 737
 738
 739
 740 inline const CBigNum operator+(const CBigNum& a, const CBigNum& b)
 741 {
 742     CBigNum r;
 743     if (!BN_add(r.bn, a.bn, b.bn))
 744         throw bignum_error("CBigNum::operator+ : BN_add failed");
 745     return r;
 746 }
 747
 748 inline const CBigNum operator-(const CBigNum& a, const CBigNum& b)
 749 {
 750     CBigNum r;
 751     if (!BN_sub(r.bn, a.bn, b.bn))
 752         throw bignum_error("CBigNum::operator- : BN_sub failed");
 753     return r;
 754 }
 755
 756 inline const CBigNum operator-(const CBigNum& a)
 757 {
 758     CBigNum r(a);
 759     BN_set_negative(r.bn, !BN_is_negative(r.bn));
 760     return r;
 761 }
 762
 763 inline const CBigNum operator*(const CBigNum& a, const CBigNum& b)
 764 {
 765     CAutoBN_CTX pctx;
 766     CBigNum r;
 767     if (!BN_mul(r.bn, a.bn, b.bn, pctx))
 768         throw bignum_error("CBigNum::operator* : BN_mul failed");
 769     return r;
 770 }
 771
 772 inline const CBigNum operator/(const CBigNum& a, const CBigNum& b)
 773 {
 774     CAutoBN_CTX pctx;
 775     CBigNum r;
 776     if (!BN_div(r.bn, NULL, a.bn, b.bn, pctx))
 777         throw bignum_error("CBigNum::operator/ : BN_div failed");
 778     return r;
 779 }
 780
 781 inline const CBigNum operator%(const CBigNum& a, const CBigNum& b)
 782 {
 783     CAutoBN_CTX pctx;
 784     CBigNum r;
 785     if (!BN_nnmod(r.bn, a.bn, b.bn, pctx))
 786         throw bignum_error("CBigNum::operator% : BN_div failed");
 787     return r;
 788 }
 789
 790 inline const CBigNum operator<<(const CBigNum& a, unsigned int shift)
 791 {
 792     CBigNum r;
 793     if (!BN_lshift(r.bn, a.bn, shift))
 794         throw bignum_error("CBigNum:operator<< : BN_lshift failed");
 795     return r;
 796 }
 797
 798 inline const CBigNum operator>>(const CBigNum& a, unsigned int shift)
 799 {
 800     CBigNum r = a;
 801     r >>= shift;
 802     return r;
 803 }
 804
 805 inline bool operator==(const CBigNum& a, const CBigNum& b) { return (BN_cmp(a.bn, b.bn) == 0); }
 806 inline bool operator!=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(a.bn, b.bn) != 0); }
 807 inline bool operator<=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(a.bn, b.bn) <= 0); }
 808 inline bool operator>=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(a.bn, b.bn) >= 0); }
 809 inline bool operator<(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(a.bn, b.bn) < 0); }
 810 inline bool operator>(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(a.bn, b.bn) > 0); }
 811
 812 inline std::ostream& operator<<(std::ostream &strm, const CBigNum &b) { return strm << b.ToString(10); }
 813
 814 typedef  CBigNum Bignum;
 815
 816 #endif