Crypter.h security improvement, start working on ZeroCoin support
[novacoin.git] / src / bignum.h
index 0d57dc8..6b2bada 100644 (file)
@@ -1,7 +1,7 @@
 // Copyright (c) 2009-2010 Satoshi Nakamoto
 // Copyright (c) 2009-2012 The Bitcoin developers
 // Distributed under the MIT/X11 software license, see the accompanying
-// file license.txt or http://www.opensource.org/licenses/mit-license.php.
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 #ifndef BITCOIN_BIGNUM_H
 #define BITCOIN_BIGNUM_H
 
@@ -97,6 +97,40 @@ public:
         setvch(vch);
     }
 
+    /** Generates a cryptographically secure random number between zero and range exclusive
+    * i.e. 0 < returned number < range
+    * @param range The upper bound on the number.
+    * @return
+    */
+    static CBigNum  randBignum(const CBigNum& range) {
+        CBigNum ret;
+        if(!BN_rand_range(&ret, &range)){
+            throw bignum_error("CBigNum:rand element : BN_rand_range failed");
+        }
+        return ret;
+    }
+
+    /** Generates a cryptographically secure random k-bit number
+    * @param k The bit length of the number.
+    * @return
+    */
+    static CBigNum RandKBitBigum(const uint32_t k){
+        CBigNum ret;
+        if(!BN_rand(&ret, k, -1, 0)){
+            throw bignum_error("CBigNum:rand element : BN_rand failed");
+        }
+        return ret;
+    }
+
+    /**Returns the size in bits of the underlying bignum.
+     *
+     * @return the size
+     */
+    int bitSize() const{
+        return  BN_num_bits(this);
+    }
+
+
     void setulong(unsigned long n)
     {
         if (!BN_set_word(this, n))
@@ -117,21 +151,29 @@ public:
     {
         unsigned long n = BN_get_word(this);
         if (!BN_is_negative(this))
-            return (n > std::numeric_limits<int>::max() ? std::numeric_limits<int>::max() : n);
+            return (n > (unsigned long)std::numeric_limits<int>::max() ? std::numeric_limits<int>::max() : n);
         else
-            return (n > std::numeric_limits<int>::max() ? std::numeric_limits<int>::min() : -(int)n);
+            return (n > (unsigned long)std::numeric_limits<int>::max() ? std::numeric_limits<int>::min() : -(int)n);
     }
 
-    void setint64(int64 n)
+    void setint64(int64 sn)
     {
-        unsigned char pch[sizeof(n) + 6];
+        unsigned char pch[sizeof(sn) + 6];
         unsigned char* p = pch + 4;
-        bool fNegative = false;
-        if (n < (int64)0)
+        bool fNegative;
+        uint64 n;
+
+        if (sn < (int64)0)
         {
-            n = -n;
+            // 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
+            n = -(sn + 1);
+            ++n;
             fNegative = true;
+        } else {
+            n = sn;
+            fNegative = false;
         }
+
         bool fLeadingZeroes = true;
         for (int i = 0; i < 8; i++)
         {
@@ -157,6 +199,21 @@ public:
         BN_mpi2bn(pch, p - pch, this);
     }
 
+    uint64 getuint64()
+    {
+        unsigned int nSize = BN_bn2mpi(this, NULL);
+        if (nSize < 4)
+            return 0;
+        std::vector<unsigned char> vch(nSize);
+        BN_bn2mpi(this, &vch[0]);
+        if (vch.size() > 4)
+            vch[4] &= 0x7f;
+        uint64 n = 0;
+        for (unsigned int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
+            ((unsigned char*)&n)[i] = vch[j];
+        return n;
+    }
+
     void setuint64(uint64 n)
     {
         unsigned char pch[sizeof(n) + 6];
@@ -212,7 +269,7 @@ public:
         BN_mpi2bn(pch, p - pch, this);
     }
 
-    uint256 getuint256()
+    uint256 getuint256() const
     {
         unsigned int nSize = BN_bn2mpi(this, NULL);
         if (nSize < 4)
@@ -222,11 +279,12 @@ public:
         if (vch.size() > 4)
             vch[4] &= 0x7f;
         uint256 n = 0;
-        for (int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
+        for (unsigned int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
             ((unsigned char*)&n)[i] = vch[j];
         return n;
     }
 
+
     void setvch(const std::vector<unsigned char>& vch)
     {
         std::vector<unsigned char> vch2(vch.size() + 4);
@@ -297,7 +355,7 @@ public:
             psz++;
 
         // hex string to bignum
-        static 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 };
+        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 };
         *this = 0;
         while (isxdigit(*psz))
         {
@@ -359,6 +417,122 @@ public:
         setvch(vch);
     }
 
+    /**
+    * exponentiation with an int. this^e
+    * @param e the exponent as an int
+    * @return
+    */
+    CBigNum pow(const int e) const {
+        return this->pow(CBigNum(e));
+    }
+
+    /**
+     * exponentiation this^e
+     * @param e the exponent
+     * @return
+     */
+    CBigNum pow(const CBigNum& e) const {
+        CAutoBN_CTX pctx;
+        CBigNum ret;
+        if (!BN_exp(&ret, this, &e, pctx))
+            throw bignum_error("CBigNum::pow : BN_exp failed");
+        return ret;
+    }
+
+    /**
+     * modular multiplication: (this * b) mod m
+     * @param b operand
+     * @param m modulus
+     */
+    CBigNum mul_mod(const CBigNum& b, const CBigNum& m) const {
+        CAutoBN_CTX pctx;
+        CBigNum ret;
+        if (!BN_mod_mul(&ret, this, &b, &m, pctx))
+            throw bignum_error("CBigNum::mul_mod : BN_mod_mul failed");
+        
+        return ret;
+    }
+
+    /**
+     * modular exponentiation: this^e mod n
+     * @param e exponent
+     * @param m modulus
+     */
+    CBigNum pow_mod(const CBigNum& e, const CBigNum& m) const {
+        CAutoBN_CTX pctx;
+        CBigNum ret;
+        if( e < 0){
+            // g^-x = (g^-1)^x
+            CBigNum inv = this->inverse(m);
+            CBigNum posE = e * -1;
+            if (!BN_mod_exp(&ret, &inv, &posE, &m, pctx))
+                throw bignum_error("CBigNum::pow_mod: BN_mod_exp failed on negative exponent");
+        }else
+            if (!BN_mod_exp(&ret, this, &e, &m, pctx))
+                throw bignum_error("CBigNum::pow_mod : BN_mod_exp failed");
+
+        return ret;
+    }
+
+    /**
+    * Calculates the inverse of this element mod m.
+    * i.e. i such this*i = 1 mod m
+    * @param m the modu
+    * @return the inverse
+    */
+    CBigNum inverse(const CBigNum& m) const {
+        CAutoBN_CTX pctx;
+        CBigNum ret;
+        if (!BN_mod_inverse(&ret, this, &m, pctx))
+            throw bignum_error("CBigNum::inverse*= :BN_mod_inverse");
+        return ret;
+    }
+
+    /**
+     * Generates a random (safe) prime of numBits bits
+     * @param numBits the number of bits
+     * @param safe true for a safe prime
+     * @return the prime
+     */
+    static CBigNum generatePrime(const unsigned int numBits, bool safe = false) {
+        CBigNum ret;
+        if(!BN_generate_prime_ex(&ret, numBits, (safe == true), NULL, NULL, NULL))
+            throw bignum_error("CBigNum::generatePrime*= :BN_generate_prime_ex");
+        return ret;
+    }
+
+    /**
+     * Calculates the greatest common divisor (GCD) of two numbers.
+     * @param m the second element
+     * @return the GCD
+     */
+    CBigNum gcd( const CBigNum& b) const{
+        CAutoBN_CTX pctx;
+        CBigNum ret;
+        if (!BN_gcd(&ret, this, &b, pctx))
+            throw bignum_error("CBigNum::gcd*= :BN_gcd");
+        return ret;
+    }
+
+    /**
+    * Miller-Rabin primality test on this element
+    * @param checks: optional, the number of Miller-Rabin tests to run
+    * default causes error rate of 2^-80.
+    * @return true if prime
+    */
+    bool isPrime(const int checks=BN_prime_checks) const {
+        CAutoBN_CTX pctx;
+        int ret = BN_is_prime(this, checks, NULL, pctx, NULL);
+        if(ret < 0){
+            throw bignum_error("CBigNum::isPrime :BN_is_prime");
+        }
+        return ret;
+    }
+
+    bool isOne() const {
+        return BN_is_one(this);
+    }
+
 
     bool operator!() const
     {
@@ -408,7 +582,7 @@ public:
     CBigNum& operator>>=(unsigned int shift)
     {
         // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
-        //   if built on ubuntu 9.04 or 9.10, probably depends on version of openssl
+        //   if built on ubuntu 9.04 or 9.10, probably depends on version of OpenSSL
         CBigNum a = 1;
         a <<= shift;
         if (BN_cmp(&a, this) > 0)
@@ -461,6 +635,8 @@ public:
     friend inline const CBigNum operator-(const CBigNum& a, const CBigNum& b);
     friend inline const CBigNum operator/(const CBigNum& a, const CBigNum& b);
     friend inline const CBigNum operator%(const CBigNum& a, const CBigNum& b);
+    friend inline const CBigNum operator*(const CBigNum& a, const CBigNum& b);
+    friend inline bool operator<(const CBigNum& a, const CBigNum& b);
 };
 
 
@@ -510,7 +686,7 @@ inline const CBigNum operator%(const CBigNum& a, const CBigNum& b)
 {
     CAutoBN_CTX pctx;
     CBigNum r;
-    if (!BN_mod(&r, &a, &b, pctx))
+    if (!BN_nnmod(&r, &a, &b, pctx))
         throw bignum_error("CBigNum::operator% : BN_div failed");
     return r;
 }
@@ -537,4 +713,8 @@ inline bool operator>=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a,
 inline bool operator<(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(&a, &b) < 0); }
 inline bool operator>(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(&a, &b) > 0); }
 
+inline std::ostream& operator<<(std::ostream &strm, const CBigNum &b) { return strm << b.ToString(10); }
+
+typedef  CBigNum Bignum;
+
 #endif