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