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