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