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