1 /* 2 * Copyright 2019 Google Inc. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * https://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef CRYPTO_BIG_NUM_H_ 17 #define CRYPTO_BIG_NUM_H_ 18 19 #include <stdint.h> 20 21 #include <memory> 22 #include <string> 23 24 #include "third_party/private-join-and-compute/src/crypto/openssl.inc" 25 #include "third_party/private-join-and-compute/src/util/status.inc" 26 27 namespace private_join_and_compute { 28 29 // Immutable wrapper class for openssl BIGNUM numbers. 30 // Used for arithmetic operations on big numbers. 31 // Makes use of a BN_CTX structure that holds temporary BIGNUMs needed for 32 // arithmetic operations as dynamic memory allocation to create BIGNUMs is 33 // expensive. 34 class BigNum { 35 public: 36 // Deletes a BIGNUM. 37 class BnDeleter { 38 public: operator()39 void operator()(BIGNUM* bn) { BN_clear_free(bn); } 40 }; 41 42 // Copies the given BigNum. 43 BigNum(const BigNum& other); 44 BigNum& operator=(const BigNum& other); 45 46 // Moves the given BigNum. 47 BigNum(BigNum&& other); 48 BigNum& operator=(BigNum&& other); 49 50 typedef std::unique_ptr<BIGNUM, BnDeleter> BignumPtr; 51 52 // Returns the absolute value of this in big-endian form. 53 std::string ToBytes() const; 54 55 // Converts this BigNum to a uint64_t value. Returns an INVALID_ARGUMENT 56 // error code if the value of *this is larger than 64 bits. 57 StatusOr<uint64_t> ToIntValue() const; 58 59 // Returns the bit length of this BigNum. 60 int BitLength() const; 61 62 // Returns False if the number is composite, True if it is prime with an 63 // error probability of 1e-40, which gives at least 128 bit security. 64 bool IsPrime(double prime_error_probability = 1e-40) const; 65 66 // Returns False if the number is composite, True if it is safe prime with an 67 // error probability of at most 1e-40. 68 bool IsSafePrime(double prime_error_probability = 1e-40) const; 69 70 // Return True if this BigNum is zero. 71 bool IsZero() const; 72 73 // Return True if this BigNum is one. 74 bool IsOne() const; 75 76 // Returns True if this BigNum is not negative. 77 bool IsNonNegative() const; 78 79 // Returns a BigNum that is equal to the last n bits of this BigNum. 80 BigNum GetLastNBits(int n) const; 81 82 // Returns true if n-th bit of this big_num is set, false otherwise. 83 bool IsBitSet(int n) const; 84 85 // Returns a BigNum whose value is (- *this). 86 // Causes a check failure if the operation fails. 87 BigNum Neg() const; 88 89 // Returns a BigNum whose value is (*this + val). 90 // Causes a check failure if the operation fails. 91 BigNum Add(const BigNum& val) const; 92 93 // Returns a BigNum whose value is (*this * val). 94 // Causes a check failure if the operation fails. 95 BigNum Mul(const BigNum& val) const; 96 97 // Returns a BigNum whose value is (*this - val). 98 // Causes a check failure if the operation fails. 99 BigNum Sub(const BigNum& val) const; 100 101 // Returns a BigNum whose value is (*this / val). 102 // Causes a check failure if the remainder != 0 or if the operation fails. 103 BigNum Div(const BigNum& val) const; 104 105 // Returns a BigNum whose value is *this / val, rounding towards zero. 106 // Causes a check failure if the remainder != 0 or if the operation fails. 107 BigNum DivAndTruncate(const BigNum& val) const; 108 109 // Compares this BigNum with the specified BigNum. 110 // Returns -1 if *this < val, 0 if *this == val and 1 if *this > val. 111 int CompareTo(const BigNum& val) const; 112 113 // Returns a BigNum whose value is (*this ^ exponent). 114 // Causes a check failure if the operation fails. 115 BigNum Exp(const BigNum& exponent) const; 116 117 // Returns a BigNum whose value is (*this mod m). 118 BigNum Mod(const BigNum& m) const; 119 120 // Returns a BigNum whose value is (*this + val mod m). 121 // Causes a check failure if the operation fails. 122 BigNum ModAdd(const BigNum& val, const BigNum& m) const; 123 124 // Returns a BigNum whose value is (*this - val mod m). 125 // Causes a check failure if the operation fails. 126 BigNum ModSub(const BigNum& val, const BigNum& m) const; 127 128 // Returns a BigNum whose value is (*this * val mod m). 129 // For efficiency, please use Montgomery multiplication module if this is done 130 // multiple times with the same modulus. 131 // Causes a check failure if the operation fails. 132 BigNum ModMul(const BigNum& val, const BigNum& m) const; 133 134 // Returns a BigNum whose value is (*this ^ exponent mod m). 135 // Causes a check failure if the operation fails. 136 BigNum ModExp(const BigNum& exponent, const BigNum& m) const; 137 138 // Return a BigNum whose value is (*this ^ 2 mod m). 139 // Causes a check failure if the operation fails. 140 BigNum ModSqr(const BigNum& m) const; 141 142 // Returns a BigNum whose value is (*this ^ -1 mod m). 143 // Causes a check failure if the operation fails. 144 BigNum ModInverse(const BigNum& m) const; 145 146 // Returns r such that r ^ 2 == *this mod p. 147 // Causes a check failure if the operation fails. 148 BigNum ModSqrt(const BigNum& m) const; 149 150 // Computes -a mod m. 151 // Causes a check failure if the operation fails. 152 BigNum ModNegate(const BigNum& m) const; 153 154 // Returns a BigNum whose value is (*this >> n). 155 BigNum Rshift(int n) const; 156 157 // Returns a BigNum whose value is (*this << n). 158 // Causes a check failure if the operation fails. 159 BigNum Lshift(int n) const; 160 161 // Computes the greatest common divisor of *this and val. 162 // Causes a check failure if the operation fails. 163 BigNum Gcd(const BigNum& val) const; 164 165 // Returns a pointer to const BIGNUM to be used with openssl functions. 166 const BIGNUM* GetConstBignumPtr() const; 167 168 private: 169 // Creates a new BigNum object from a bytes string. 170 explicit BigNum(BN_CTX* bn_ctx, const std::string& bytes); 171 // Creates a new BigNum object from a char array. 172 explicit BigNum(BN_CTX* bn_ctx, const unsigned char* bytes, int length); 173 // Creates a new BigNum object from the number. 174 explicit BigNum(BN_CTX* bn_ctx, uint64_t number); 175 // Creates a new BigNum object with no defined value. 176 explicit BigNum(BN_CTX* bn_ctx); 177 // Creates a new BigNum object from the given BIGNUM value. 178 explicit BigNum(BN_CTX* bn_ctx, BignumPtr bn); 179 180 BignumPtr bn_; 181 BN_CTX* bn_ctx_; 182 183 // Context is a factory for BigNum objects. 184 friend class Context; 185 }; 186 187 inline BigNum operator-(const BigNum& a) { return a.Neg(); } 188 189 inline BigNum operator+(const BigNum& a, const BigNum& b) { return a.Add(b); } 190 191 inline BigNum operator*(const BigNum& a, const BigNum& b) { return a.Mul(b); } 192 193 inline BigNum operator-(const BigNum& a, const BigNum& b) { return a.Sub(b); } 194 195 // Returns a BigNum whose value is (a / b). 196 // Causes a check failure if the remainder != 0. 197 inline BigNum operator/(const BigNum& a, const BigNum& b) { return a.Div(b); } 198 199 inline BigNum& operator+=(BigNum& a, const BigNum& b) { return a = a + b; } 200 201 inline BigNum& operator*=(BigNum& a, const BigNum& b) { return a = a * b; } 202 203 inline BigNum& operator-=(BigNum& a, const BigNum& b) { return a = a - b; } 204 205 inline BigNum& operator/=(BigNum& a, const BigNum& b) { return a = a / b; } 206 207 inline bool operator==(const BigNum& a, const BigNum& b) { 208 return 0 == a.CompareTo(b); 209 } 210 211 inline bool operator!=(const BigNum& a, const BigNum& b) { return !(a == b); } 212 213 inline bool operator<(const BigNum& a, const BigNum& b) { 214 return -1 == a.CompareTo(b); 215 } 216 217 inline bool operator>(const BigNum& a, const BigNum& b) { 218 return 1 == a.CompareTo(b); 219 } 220 221 inline bool operator<=(const BigNum& a, const BigNum& b) { 222 return a.CompareTo(b) <= 0; 223 } 224 225 inline bool operator>=(const BigNum& a, const BigNum& b) { 226 return a.CompareTo(b) >= 0; 227 } 228 229 inline BigNum operator%(const BigNum& a, const BigNum& m) { return a.Mod(m); } 230 231 inline BigNum operator>>(const BigNum& a, int n) { return a.Rshift(n); } 232 233 inline BigNum operator<<(const BigNum& a, int n) { return a.Lshift(n); } 234 235 inline BigNum& operator%=(BigNum& a, const BigNum& b) { return a = a % b; } 236 237 inline BigNum& operator>>=(BigNum& a, int n) { return a = a >> n; } 238 239 inline BigNum& operator<<=(BigNum& a, int n) { return a = a << n; } 240 241 } // namespace private_join_and_compute 242 243 #endif // CRYPTO_BIG_NUM_H_ 244