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