1 /*
2 Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; see the file COPYING. If not, write to the
15 Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
16 MA 02110-1335 USA.
17 */
18
19 /* based on Wei Dai's integer.h from CryptoPP */
20
21
22 #ifndef TAO_CRYPT_INTEGER_HPP
23 #define TAO_CRYPT_INTEGER_HPP
24
25
26 #ifdef _MSC_VER
27 // 4250: dominance
28 // 4660: explicitly instantiating a class already implicitly instantiated
29 // 4661: no suitable definition provided for explicit template request
30 // 4786: identifer was truncated in debug information
31 // 4355: 'this' : used in base member initializer list
32 # pragma warning(disable: 4250 4660 4661 4786 4355)
33 #endif
34
35
36 #include "misc.hpp"
37 #include "block.hpp"
38 #include "random.hpp"
39 #include "file.hpp"
40 #include <string.h>
41 #ifdef USE_SYS_STL
42 #include <algorithm>
43 #else
44 #include "algorithm.hpp"
45 #endif
46
47
48 #ifdef TAOCRYPT_X86ASM_AVAILABLE
49 #if defined(__GNUC__) && (__GNUC__ >= 4)
50 // GCC 4 or greater optimizes too much inline on recursive for bigint,
51 // -O3 just as fast without asm here anyway
52 #undef TAOCRYPT_X86ASM_AVAILABLE
53 #endif
54 #endif
55
56 #ifdef TAOCRYPT_X86ASM_AVAILABLE
57
58 #ifdef _M_IX86
59 #if (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 500)) || \
60 (defined(__ICL) && (__ICL >= 500))
61 #define SSE2_INTRINSICS_AVAILABLE
62 #define TAOCRYPT_MM_MALLOC_AVAILABLE
63 #elif defined(_MSC_VER)
64 // _mm_free seems to be the only way to tell if the Processor Pack is
65 //installed or not
66 #include <malloc.h>
67 #if defined(_mm_free)
68 #define SSE2_INTRINSICS_AVAILABLE
69 #define TAOCRYPT_MM_MALLOC_AVAILABLE
70 #endif
71 #endif
72 #endif
73
74 // SSE2 intrinsics work in GCC 3.3 or later
75 #if defined(__SSE2__) && (__GNUC__ == 4 || __GNUC_MAJOR__ > 3 || \
76 __GNUC_MINOR__ > 2)
77 #define SSE2_INTRINSICS_AVAILABLE
78 #endif
79
80 #endif // X86ASM
81
82
83
84
85 namespace TaoCrypt {
86
87 #if defined(SSE2_INTRINSICS_AVAILABLE)
88
89 // Allocator handling proper alignment
90 template <class T>
91 class AlignedAllocator : public AllocatorBase<T>
92 {
93 public:
94 typedef typename AllocatorBase<T>::pointer pointer;
95 typedef typename AllocatorBase<T>::size_type size_type;
96
97 pointer allocate(size_type n, const void* = 0);
98 void deallocate(void* p, size_type n);
reallocate(T * p,size_type oldSize,size_type newSize,bool preserve)99 pointer reallocate(T* p, size_type oldSize, size_type newSize,
100 bool preserve)
101 {
102 return StdReallocate(*this, p, oldSize, newSize, preserve);
103 }
104
105 #if !(defined(TAOCRYPT_MALLOC_ALIGNMENT_IS_16) || \
106 defined(TAOCRYPT_MEMALIGN_AVAILABLE) || \
107 defined(TAOCRYPT_MM_MALLOC_AVAILABLE))
108 #define TAOCRYPT_NO_ALIGNED_ALLOC
AlignedAllocator()109 AlignedAllocator() : m_pBlock(0) {}
110 protected:
111 void *m_pBlock;
112 #endif
113 };
114
115 typedef Block<word, AlignedAllocator<word> > AlignedWordBlock;
116 #else
117 typedef WordBlock AlignedWordBlock;
118 #endif
119
120
121
122 #ifdef _WIN32
123 #undef max // avoid name clash
124 #endif
125 // general MAX
126 template<typename T> inline
max(const T & a,const T & b)127 const T& max(const T& a, const T& b)
128 {
129 return a > b ? a : b;
130 }
131
132
133 // Large Integer class
134 class Integer {
135 public:
136 enum Sign {POSITIVE = 0, NEGATIVE = 1 };
137 enum Signedness { UNSIGNED, SIGNED };
138 enum RandomNumberType { ANY, PRIME };
139
140 class DivideByZero {};
141
142 Integer();
143 Integer(const Integer& t);
144 Integer(signed long value);
145 Integer(Sign s, word highWord, word lowWord);
146
147 // BER Decode Source
148 explicit Integer(Source&);
149
150 Integer(const byte* encodedInteger, unsigned int byteCount,
151 Signedness s = UNSIGNED);
152
~Integer()153 ~Integer() {}
154
155 static const Integer& Zero();
156 static const Integer& One();
157
Ref()158 Integer& Ref() { return *this; }
159
160 Integer(RandomNumberGenerator& rng, const Integer& min,
161 const Integer& max);
162
163 static Integer Power2(unsigned int e);
164
165 unsigned int MinEncodedSize(Signedness = UNSIGNED) const;
166 unsigned int Encode(byte* output, unsigned int outputLen,
167 Signedness = UNSIGNED) const;
168
169 void Decode(const byte* input, unsigned int inputLen,
170 Signedness = UNSIGNED);
171 void Decode(Source&);
172
173 bool IsConvertableToLong() const;
174 signed long ConvertToLong() const;
175
176 unsigned int BitCount() const;
177 unsigned int ByteCount() const;
178 unsigned int WordCount() const;
179
180 bool GetBit(unsigned int i) const;
181 byte GetByte(unsigned int i) const;
182 unsigned long GetBits(unsigned int i, unsigned int n) const;
183
IsZero() const184 bool IsZero() const { return !*this; }
NotZero() const185 bool NotZero() const { return !IsZero(); }
IsNegative() const186 bool IsNegative() const { return sign_ == NEGATIVE; }
NotNegative() const187 bool NotNegative() const { return !IsNegative(); }
IsPositive() const188 bool IsPositive() const { return NotNegative() && NotZero(); }
NotPositive() const189 bool NotPositive() const { return !IsPositive(); }
IsEven() const190 bool IsEven() const { return GetBit(0) == 0; }
IsOdd() const191 bool IsOdd() const { return GetBit(0) == 1; }
192
193 Integer& operator=(const Integer& t);
194 Integer& operator+=(const Integer& t);
195 Integer& operator-=(const Integer& t);
operator *=(const Integer & t)196 Integer& operator*=(const Integer& t) { return *this = Times(t); }
operator /=(const Integer & t)197 Integer& operator/=(const Integer& t)
198 { return *this = DividedBy(t);}
operator %=(const Integer & t)199 Integer& operator%=(const Integer& t) { return *this = Modulo(t); }
operator /=(word t)200 Integer& operator/=(word t) { return *this = DividedBy(t); }
operator %=(word t)201 Integer& operator%=(word t) { return *this = Modulo(t); }
202 Integer& operator<<=(unsigned int);
203 Integer& operator>>=(unsigned int);
204
205
206 void Randomize(RandomNumberGenerator &rng, unsigned int bitcount);
207 void Randomize(RandomNumberGenerator &rng, const Integer &min,
208 const Integer &max);
209
210 void SetBit(unsigned int n, bool value = 1);
211 void SetByte(unsigned int n, byte value);
212
213 void Negate();
SetPositive()214 void SetPositive() { sign_ = POSITIVE; }
SetNegative()215 void SetNegative() { if (!!(*this)) sign_ = NEGATIVE; }
216 void Swap(Integer& a);
217
218 bool operator!() const;
operator +() const219 Integer operator+() const {return *this;}
220 Integer operator-() const;
221 Integer& operator++();
222 Integer& operator--();
operator ++(int)223 Integer operator++(int)
224 { Integer temp = *this; ++*this; return temp; }
operator --(int)225 Integer operator--(int)
226 { Integer temp = *this; --*this; return temp; }
227
228 int Compare(const Integer& a) const;
229
230 Integer Plus(const Integer &b) const;
231 Integer Minus(const Integer &b) const;
232 Integer Times(const Integer &b) const;
233 Integer DividedBy(const Integer &b) const;
234 Integer Modulo(const Integer &b) const;
235 Integer DividedBy(word b) const;
236 word Modulo(word b) const;
237
operator >>(unsigned int n) const238 Integer operator>>(unsigned int n) const { return Integer(*this)>>=n; }
operator <<(unsigned int n) const239 Integer operator<<(unsigned int n) const { return Integer(*this)<<=n; }
240
241 Integer AbsoluteValue() const;
Doubled() const242 Integer Doubled() const { return Plus(*this); }
Squared() const243 Integer Squared() const { return Times(*this); }
244 Integer SquareRoot() const;
245
246 bool IsSquare() const;
247 bool IsUnit() const;
248
249 Integer MultiplicativeInverse() const;
250
251 friend Integer a_times_b_mod_c(const Integer& x, const Integer& y,
252 const Integer& m);
253 friend Integer a_exp_b_mod_c(const Integer& x, const Integer& e,
254 const Integer& m);
255
256 static void Divide(Integer& r, Integer& q, const Integer& a,
257 const Integer& d);
258 static void Divide(word& r, Integer& q, const Integer& a, word d);
259 static void DivideByPowerOf2(Integer& r, Integer& q, const Integer& a,
260 unsigned int n);
261 static Integer Gcd(const Integer& a, const Integer& n);
262
263 Integer InverseMod(const Integer& n) const;
264 word InverseMod(word n) const;
265
266 private:
267 friend class ModularArithmetic;
268 friend class MontgomeryRepresentation;
269
270 Integer(word value, unsigned int length);
271 int PositiveCompare(const Integer& t) const;
272
273 friend void PositiveAdd(Integer& sum, const Integer& a, const Integer& b);
274 friend void PositiveSubtract(Integer& diff, const Integer& a,
275 const Integer& b);
276 friend void PositiveMultiply(Integer& product, const Integer& a,
277 const Integer& b);
278 friend void PositiveDivide(Integer& remainder, Integer& quotient, const
279 Integer& dividend, const Integer& divisor);
280 AlignedWordBlock reg_;
281 Sign sign_;
282 };
283
operator ==(const Integer & a,const Integer & b)284 inline bool operator==(const Integer& a, const Integer& b)
285 {return a.Compare(b)==0;}
operator !=(const Integer & a,const Integer & b)286 inline bool operator!=(const Integer& a, const Integer& b)
287 {return a.Compare(b)!=0;}
operator >(const Integer & a,const Integer & b)288 inline bool operator> (const Integer& a, const Integer& b)
289 {return a.Compare(b)> 0;}
operator >=(const Integer & a,const Integer & b)290 inline bool operator>=(const Integer& a, const Integer& b)
291 {return a.Compare(b)>=0;}
operator <(const Integer & a,const Integer & b)292 inline bool operator< (const Integer& a, const Integer& b)
293 {return a.Compare(b)< 0;}
operator <=(const Integer & a,const Integer & b)294 inline bool operator<=(const Integer& a, const Integer& b)
295 {return a.Compare(b)<=0;}
296
operator +(const Integer & a,const Integer & b)297 inline Integer operator+(const Integer &a, const Integer &b)
298 {return a.Plus(b);}
operator -(const Integer & a,const Integer & b)299 inline Integer operator-(const Integer &a, const Integer &b)
300 {return a.Minus(b);}
operator *(const Integer & a,const Integer & b)301 inline Integer operator*(const Integer &a, const Integer &b)
302 {return a.Times(b);}
operator /(const Integer & a,const Integer & b)303 inline Integer operator/(const Integer &a, const Integer &b)
304 {return a.DividedBy(b);}
operator %(const Integer & a,const Integer & b)305 inline Integer operator%(const Integer &a, const Integer &b)
306 {return a.Modulo(b);}
operator /(const Integer & a,word b)307 inline Integer operator/(const Integer &a, word b) {return a.DividedBy(b);}
operator %(const Integer & a,word b)308 inline word operator%(const Integer &a, word b) {return a.Modulo(b);}
309
swap(Integer & a,Integer & b)310 inline void swap(Integer &a, Integer &b)
311 {
312 a.Swap(b);
313 }
314
315
316 Integer CRT(const Integer& xp, const Integer& p, const Integer& xq,
317 const Integer& q, const Integer& u);
318
ModularExponentiation(const Integer & a,const Integer & e,const Integer & m)319 inline Integer ModularExponentiation(const Integer& a, const Integer& e,
320 const Integer& m)
321 {
322 return a_exp_b_mod_c(a, e, m);
323 }
324
325 Integer ModularRoot(const Integer& a, const Integer& dp, const Integer& dq,
326 const Integer& p, const Integer& q, const Integer& u);
327
328
329
330 } // namespace
331
332 #endif // TAO_CRYPT_INTEGER_HPP
333