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     BIGNUM* get() const {
 472         return bn;
 473     }
 474
 475     unsigned int GetSerializeSize(int nType=0, int nVersion=PROTOCOL_VERSION) const
 476     {
 477         return ::GetSerializeSize(getvch(), nType, nVersion);
 478     }
 479
 480     template<typename Stream>
 481     void Serialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION) const
 482     {
 483         ::Serialize(s, getvch(), nType, nVersion);
 484     }
 485
 486     template<typename Stream>
 487     void Unserialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION)
 488     {
 489         std::vector<uint8_t> vch;
 490         ::Unserialize(s, vch, nType, nVersion);
 491         setvch(vch);
 492     }
 493
 494     /**
 495     * exponentiation with an int. this^e
 496     * @param e the exponent as an int
 497     * @return
 498     */
 499     CBigNum pow(const int e) const {
 500         return this->pow(CBigNum(e));
 501     }
 502
 503     /**
 504      * exponentiation this^e
 505      * @param e the exponent
 506      * @return
 507      */
 508     CBigNum pow(const CBigNum& e) const {
 509         CAutoBN_CTX pctx;
 510         CBigNum ret;
 511         if (!BN_exp(ret.bn, bn, e.bn, pctx))
 512             throw bignum_error("CBigNum::pow : BN_exp failed");
 513         return ret;
 514     }
 515
 516     /**
 517      * modular multiplication: (this * b) mod m
 518      * @param b operand
 519      * @param m modulus
 520      */
 521     CBigNum mul_mod(const CBigNum& b, const CBigNum& m) const {
 522         CAutoBN_CTX pctx;
 523         CBigNum ret;
 524         if (!BN_mod_mul(ret.bn, bn, b.bn, m.bn, pctx))
 525             throw bignum_error("CBigNum::mul_mod : BN_mod_mul failed");
 526
 527         return ret;
 528     }
 529
 530     /**
 531      * modular exponentiation: this^e mod n
 532      * @param e exponent
 533      * @param m modulus
 534      */
 535     CBigNum pow_mod(const CBigNum& e, const CBigNum& m) const {
 536         CAutoBN_CTX pctx;
 537         CBigNum ret;
 538         if( e < 0){
 539             // g^-x = (g^-1)^x
 540             CBigNum inv = this->inverse(m);
 541             CBigNum posE = e * -1;
 542             if (!BN_mod_exp(ret.bn, inv.bn, posE.bn, m.bn, pctx))
 543                 throw bignum_error("CBigNum::pow_mod: BN_mod_exp failed on negative exponent");
 544         }else
 545             if (!BN_mod_exp(ret.bn, bn, e.bn, m.bn, pctx))
 546                 throw bignum_error("CBigNum::pow_mod : BN_mod_exp failed");
 547
 548         return ret;
 549     }
 550
 551     /**
 552     * Calculates the inverse of this element mod m.
 553     * i.e. i such this*i = 1 mod m
 554     * @param m the modu
 555     * @return the inverse
 556     */
 557     CBigNum inverse(const CBigNum& m) const {
 558         CAutoBN_CTX pctx;
 559         CBigNum ret;
 560         if (!BN_mod_inverse(ret.bn, bn, m.bn, pctx))
 561             throw bignum_error("CBigNum::inverse*= :BN_mod_inverse");
 562         return ret;
 563     }
 564
 565     /**
 566      * Generates a random (safe) prime of numBits bits
 567      * @param numBits the number of bits
 568      * @param safe true for a safe prime
 569      * @return the prime
 570      */
 571     static CBigNum generatePrime(const unsigned int numBits, bool safe = false) {
 572         CBigNum ret;
 573         if(!BN_generate_prime_ex(ret.bn, numBits, (safe == true), NULL, NULL, NULL))
 574             throw bignum_error("CBigNum::generatePrime*= :BN_generate_prime_ex");
 575         return ret;
 576     }
 577
 578     /**
 579      * Calculates the greatest common divisor (GCD) of two numbers.
 580      * @param m the second element
 581      * @return the GCD
 582      */
 583     CBigNum gcd( const CBigNum& b) const{
 584         CAutoBN_CTX pctx;
 585         CBigNum ret;
 586         if (!BN_gcd(ret.bn, bn, b.bn, pctx))
 587             throw bignum_error("CBigNum::gcd*= :BN_gcd");
 588         return ret;
 589     }
 590
 591     /**
 592     * Miller-Rabin primality test on this element
 593     * @param checks: optional, the number of Miller-Rabin tests to run
 594     * default causes error rate of 2^-80.
 595     * @return true if prime
 596     */
 597     bool isPrime(const int checks=BN_prime_checks) const {
 598         CAutoBN_CTX pctx;
 599         int ret = BN_is_prime(bn, checks, NULL, pctx, NULL);
 600         if(ret < 0){
 601             throw bignum_error("CBigNum::isPrime :BN_is_prime");
 602         }
 603         return ret != 0;
 604     }
 605
 606     bool isOne() const {
 607         return BN_is_one(bn);
 608     }
 609
 610
 611     bool operator!() const
 612     {
 613         return BN_is_zero(bn);
 614     }
 615
 616     CBigNum& operator+=(const CBigNum& b)
 617     {
 618         if (!BN_add(bn, bn, b.bn))
 619             throw bignum_error("CBigNum::operator+= : BN_add failed");
 620         return *this;
 621     }
 622
 623     CBigNum& operator-=(const CBigNum& b)
 624     {
 625         *this = *this - b;
 626         return *this;
 627     }
 628
 629     CBigNum& operator*=(const CBigNum& b)
 630     {
 631         CAutoBN_CTX pctx;
 632         if (!BN_mul(bn, bn, b.bn, pctx))
 633             throw bignum_error("CBigNum::operator*= : BN_mul failed");
 634         return *this;
 635     }
 636
 637     CBigNum& operator/=(const CBigNum& b)
 638     {
 639         *this = *this / b;
 640         return *this;
 641     }
 642
 643     CBigNum& operator%=(const CBigNum& b)
 644     {
 645         *this = *this % b;
 646         return *this;
 647     }
 648
 649     CBigNum& operator<<=(unsigned int shift)
 650     {
 651         if (!BN_lshift(bn, bn, shift))
 652             throw bignum_error("CBigNum:operator<<= : BN_lshift failed");
 653         return *this;
 654     }
 655
 656     CBigNum& operator>>=(unsigned int shift)
 657     {
 658         // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
 659         //   if built on ubuntu 9.04 or 9.10, probably depends on version of OpenSSL
 660         CBigNum a = 1;
 661         a <<= shift;
 662         if (BN_cmp(a.bn, bn) > 0)
 663         {
 664             *this = 0;
 665             return *this;
 666         }
 667
 668         if (!BN_rshift(bn, bn, shift))
 669             throw bignum_error("CBigNum:operator>>= : BN_rshift failed");
 670         return *this;
 671     }
 672
 673
 674     CBigNum& operator++()
 675     {
 676         // prefix operator
 677         if (!BN_add(bn, bn, BN_value_one()))
 678             throw bignum_error("CBigNum::operator++ : BN_add failed");
 679         return *this;
 680     }
 681
 682     const CBigNum operator++(int)
 683     {
 684         // postfix operator
 685         const CBigNum ret = *this;
 686         ++(*this);
 687         return ret;
 688     }
 689
 690     CBigNum& operator--()
 691     {
 692         // prefix operator
 693         CBigNum r;
 694         if (!BN_sub(r.bn, bn, BN_value_one()))
 695             throw bignum_error("CBigNum::operator-- : BN_sub failed");
 696         *this = r;
 697         return *this;
 698     }
 699
 700     const CBigNum operator--(int)
 701     {
 702         // postfix operator
 703         const CBigNum ret = *this;
 704         --(*this);
 705         return ret;
 706     }
 707
 708     friend inline const CBigNum operator-(const CBigNum& a, const CBigNum& b);
 709     friend inline const CBigNum operator/(const CBigNum& a, const CBigNum& b);
 710     friend inline const CBigNum operator%(const CBigNum& a, const CBigNum& b);
 711     friend inline const CBigNum operator*(const CBigNum& a, const CBigNum& b);
 712     friend inline bool 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);
 716
 717     friend inline const CBigNum operator-(const CBigNum& a);
 718     friend inline const CBigNum operator<<(const CBigNum& a, unsigned int shift);
 719
 720     friend inline bool operator==(const CBigNum& a, const CBigNum& b);
 721     friend inline bool operator!=(const CBigNum& a, const CBigNum& b);
 722     friend inline bool operator<=(const CBigNum& a, const CBigNum& b);
 723     friend inline bool operator>=(const CBigNum& a, const CBigNum& b);
 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 std::ostream& operator<<(std::ostream &strm, const CBigNum &b);
 727 };
 728
 729
 730
 731 inline const CBigNum operator+(const CBigNum& a, const CBigNum& b)
 732 {
 733     CBigNum r;
 734     if (!BN_add(r.bn, a.bn, b.bn))
 735         throw bignum_error("CBigNum::operator+ : BN_add failed");
 736     return r;
 737 }
 738
 739 inline const CBigNum operator-(const CBigNum& a, const CBigNum& b)
 740 {
 741     CBigNum r;
 742     if (!BN_sub(r.bn, a.bn, b.bn))
 743         throw bignum_error("CBigNum::operator- : BN_sub failed");
 744     return r;
 745 }
 746
 747 inline const CBigNum operator-(const CBigNum& a)
 748 {
 749     CBigNum r(a);
 750     BN_set_negative(r.bn, !BN_is_negative(r.bn));
 751     return r;
 752 }
 753
 754 inline const CBigNum operator*(const CBigNum& a, const CBigNum& b)
 755 {
 756     CAutoBN_CTX pctx;
 757     CBigNum r;
 758     if (!BN_mul(r.bn, a.bn, b.bn, pctx))
 759         throw bignum_error("CBigNum::operator* : BN_mul failed");
 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_div(r.bn, NULL, a.bn, b.bn, pctx))
 768         throw bignum_error("CBigNum::operator/ : BN_div 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_nnmod(r.bn, 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, unsigned int shift)
 782 {
 783     CBigNum r;
 784     if (!BN_lshift(r.bn, a.bn, shift))
 785         throw bignum_error("CBigNum:operator<< : BN_lshift failed");
 786     return r;
 787 }
 788
 789 inline const CBigNum operator>>(const CBigNum& a, unsigned int shift)
 790 {
 791     CBigNum r = a;
 792     r >>= shift;
 793     return r;
 794 }
 795
 796 inline bool operator==(const CBigNum& a, const CBigNum& b) { return (BN_cmp(a.bn, b.bn) == 0); }
 797 inline bool operator!=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(a.bn, b.bn) != 0); }
 798 inline bool operator<=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(a.bn, b.bn) <= 0); }
 799 inline bool operator>=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(a.bn, b.bn) >= 0); }
 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
 803 inline std::ostream& operator<<(std::ostream &strm, const CBigNum &b) { return strm << b.ToString(10); }
 804
 805 typedef  CBigNum Bignum;
 806
 807 #endif