Crypto++
integer.h
Go to the documentation of this file.
1 #ifndef CRYPTOPP_INTEGER_H
2 #define CRYPTOPP_INTEGER_H
3 
4 /** \file */
5 
6 #include "cryptlib.h"
7 #include "secblock.h"
8 
9 #include <iosfwd>
10 #include <algorithm>
11 
12 NAMESPACE_BEGIN(CryptoPP)
13 
14 struct InitializeInteger // used to initialize static variables
15 {
16  InitializeInteger();
17 };
18 
20 
21 //! multiple precision integer and basic arithmetics
22 /*! This class can represent positive and negative integers
23  with absolute value less than (256**sizeof(word)) ** (256**sizeof(int)).
24  \nosubgrouping
25 */
26 class CRYPTOPP_DLL Integer : private InitializeInteger, public ASN1Object
27 {
28 public:
29  //! \name ENUMS, EXCEPTIONS, and TYPEDEFS
30  //@{
31  //! division by zero exception
32  class DivideByZero : public Exception
33  {
34  public:
35  DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {}
36  };
37 
38  //!
40  {
41  public:
42  RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {}
43  };
44 
45  //!
46  enum Sign {POSITIVE=0, NEGATIVE=1};
47 
48  //!
49  enum Signedness {
50  //!
51  UNSIGNED,
52  //!
53  SIGNED};
54 
55  //!
56  enum RandomNumberType {
57  //!
58  ANY,
59  //!
60  PRIME};
61  //@}
62 
63  //! \name CREATORS
64  //@{
65  //! creates the zero integer
66  Integer();
67 
68  //! copy constructor
69  Integer(const Integer& t);
70 
71  //! convert from signed long
72  Integer(signed long value);
73 
74  //! convert from lword
75  Integer(Sign s, lword value);
76 
77  //! convert from two words
78  Integer(Sign s, word highWord, word lowWord);
79 
80  //! convert from string
81  /*! str can be in base 2, 8, 10, or 16. Base is determined by a
82  case insensitive suffix of 'h', 'o', or 'b'. No suffix means base 10.
83  */
84  explicit Integer(const char *str);
85  explicit Integer(const wchar_t *str);
86 
87  //! convert from big-endian byte array
88  Integer(const byte *encodedInteger, size_t byteCount, Signedness s=UNSIGNED);
89 
90  //! convert from big-endian form stored in a BufferedTransformation
91  Integer(BufferedTransformation &bt, size_t byteCount, Signedness s=UNSIGNED);
92 
93  //! convert from BER encoded byte array stored in a BufferedTransformation object
94  explicit Integer(BufferedTransformation &bt);
95 
96  //! create a random integer
97  /*! The random integer created is uniformly distributed over [0, 2**bitcount). */
98  Integer(RandomNumberGenerator &rng, size_t bitcount);
99 
100  //! avoid calling constructors for these frequently used integers
101  static const Integer & CRYPTOPP_API Zero();
102  //! avoid calling constructors for these frequently used integers
103  static const Integer & CRYPTOPP_API One();
104  //! avoid calling constructors for these frequently used integers
105  static const Integer & CRYPTOPP_API Two();
106 
107  //! create a random integer of special type
108  /*! Ideally, the random integer created should be uniformly distributed
109  over {x | min <= x <= max and x is of rnType and x % mod == equiv}.
110  However the actual distribution may not be uniform because sequential
111  search is used to find an appropriate number from a random starting
112  point.
113  May return (with very small probability) a pseudoprime when a prime
114  is requested and max > lastSmallPrime*lastSmallPrime (lastSmallPrime
115  is declared in nbtheory.h).
116  \throw RandomNumberNotFound if the set is empty.
117  */
118  Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());
119 
120  //! return the integer 2**e
121  static Integer CRYPTOPP_API Power2(size_t e);
122  //@}
123 
124  //! \name ENCODE/DECODE
125  //@{
126  //! minimum number of bytes to encode this integer
127  /*! MinEncodedSize of 0 is 1 */
128  size_t MinEncodedSize(Signedness=UNSIGNED) const;
129  //! encode in big-endian format
130  /*! unsigned means encode absolute value, signed means encode two's complement if negative.
131  if outputLen < MinEncodedSize, the most significant bytes will be dropped
132  if outputLen > MinEncodedSize, the most significant bytes will be padded
133  */
134  void Encode(byte *output, size_t outputLen, Signedness=UNSIGNED) const;
135  //!
136  void Encode(BufferedTransformation &bt, size_t outputLen, Signedness=UNSIGNED) const;
137 
138  //! encode using Distinguished Encoding Rules, put result into a BufferedTransformation object
139  void DEREncode(BufferedTransformation &bt) const;
140 
141  //! encode absolute value as big-endian octet string
142  void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
143 
144  //! encode absolute value in OpenPGP format, return length of output
145  size_t OpenPGPEncode(byte *output, size_t bufferSize) const;
146  //! encode absolute value in OpenPGP format, put result into a BufferedTransformation object
147  size_t OpenPGPEncode(BufferedTransformation &bt) const;
148 
149  //!
150  void Decode(const byte *input, size_t inputLen, Signedness=UNSIGNED);
151  //!
152  //* Precondition: bt.MaxRetrievable() >= inputLen
153  void Decode(BufferedTransformation &bt, size_t inputLen, Signedness=UNSIGNED);
154 
155  //!
156  void BERDecode(const byte *input, size_t inputLen);
157  //!
159 
160  //! decode nonnegative value as big-endian octet string
161  void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
162 
164  {
165  public:
166  OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {}
167  };
168 
169  //!
170  void OpenPGPDecode(const byte *input, size_t inputLen);
171  //!
172  void OpenPGPDecode(BufferedTransformation &bt);
173  //@}
174 
175  //! \name ACCESSORS
176  //@{
177  //! return true if *this can be represented as a signed long
178  bool IsConvertableToLong() const;
179  //! return equivalent signed long if possible, otherwise undefined
180  signed long ConvertToLong() const;
181 
182  //! number of significant bits = floor(log2(abs(*this))) + 1
183  unsigned int BitCount() const;
184  //! number of significant bytes = ceiling(BitCount()/8)
185  unsigned int ByteCount() const;
186  //! number of significant words = ceiling(ByteCount()/sizeof(word))
187  unsigned int WordCount() const;
188 
189  //! return the i-th bit, i=0 being the least significant bit
190  bool GetBit(size_t i) const;
191  //! return the i-th byte
192  byte GetByte(size_t i) const;
193  //! return n lowest bits of *this >> i
194  lword GetBits(size_t i, size_t n) const;
195 
196  //!
197  bool IsZero() const {return !*this;}
198  //!
199  bool NotZero() const {return !IsZero();}
200  //!
201  bool IsNegative() const {return sign == NEGATIVE;}
202  //!
203  bool NotNegative() const {return !IsNegative();}
204  //!
205  bool IsPositive() const {return NotNegative() && NotZero();}
206  //!
207  bool NotPositive() const {return !IsPositive();}
208  //!
209  bool IsEven() const {return GetBit(0) == 0;}
210  //!
211  bool IsOdd() const {return GetBit(0) == 1;}
212  //@}
213 
214  //! \name MANIPULATORS
215  //@{
216  //!
217  Integer& operator=(const Integer& t);
218 
219  //!
220  Integer& operator+=(const Integer& t);
221  //!
222  Integer& operator-=(const Integer& t);
223  //!
224  Integer& operator*=(const Integer& t) {return *this = Times(t);}
225  //!
226  Integer& operator/=(const Integer& t) {return *this = DividedBy(t);}
227  //!
228  Integer& operator%=(const Integer& t) {return *this = Modulo(t);}
229  //!
230  Integer& operator/=(word t) {return *this = DividedBy(t);}
231  //!
232  Integer& operator%=(word t) {return *this = Integer(POSITIVE, 0, Modulo(t));}
233 
234  //!
235  Integer& operator<<=(size_t);
236  //!
237  Integer& operator>>=(size_t);
238 
239  //!
240  void Randomize(RandomNumberGenerator &rng, size_t bitcount);
241  //!
242  void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);
243  //! set this Integer to a random element of {x | min <= x <= max and x is of rnType and x % mod == equiv}
244  /*! returns false if the set is empty */
245  bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());
246 
247  bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs);
248  void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs)
249  {
250  if (!GenerateRandomNoThrow(rng, params))
251  throw RandomNumberNotFound();
252  }
253 
254  //! set the n-th bit to value
255  void SetBit(size_t n, bool value=1);
256  //! set the n-th byte to value
257  void SetByte(size_t n, byte value);
258 
259  //!
260  void Negate();
261  //!
262  void SetPositive() {sign = POSITIVE;}
263  //!
264  void SetNegative() {if (!!(*this)) sign = NEGATIVE;}
265 
266  //!
267  void swap(Integer &a);
268  //@}
269 
270  //! \name UNARY OPERATORS
271  //@{
272  //!
273  bool operator!() const;
274  //!
275  Integer operator+() const {return *this;}
276  //!
277  Integer operator-() const;
278  //!
279  Integer& operator++();
280  //!
281  Integer& operator--();
282  //!
283  Integer operator++(int) {Integer temp = *this; ++*this; return temp;}
284  //!
285  Integer operator--(int) {Integer temp = *this; --*this; return temp;}
286  //@}
287 
288  //! \name BINARY OPERATORS
289  //@{
290  //! signed comparison
291  /*! \retval -1 if *this < a
292  \retval 0 if *this = a
293  \retval 1 if *this > a
294  */
295  int Compare(const Integer& a) const;
296 
297  //!
298  Integer Plus(const Integer &b) const;
299  //!
300  Integer Minus(const Integer &b) const;
301  //!
302  Integer Times(const Integer &b) const;
303  //!
304  Integer DividedBy(const Integer &b) const;
305  //!
306  Integer Modulo(const Integer &b) const;
307  //!
308  Integer DividedBy(word b) const;
309  //!
310  word Modulo(word b) const;
311 
312  //!
313  Integer operator>>(size_t n) const {return Integer(*this)>>=n;}
314  //!
315  Integer operator<<(size_t n) const {return Integer(*this)<<=n;}
316  //@}
317 
318  //! \name OTHER ARITHMETIC FUNCTIONS
319  //@{
320  //!
321  Integer AbsoluteValue() const;
322  //!
323  Integer Doubled() const {return Plus(*this);}
324  //!
325  Integer Squared() const {return Times(*this);}
326  //! extract square root, if negative return 0, else return floor of square root
327  Integer SquareRoot() const;
328  //! return whether this integer is a perfect square
329  bool IsSquare() const;
330 
331  //! is 1 or -1
332  bool IsUnit() const;
333  //! return inverse if 1 or -1, otherwise return 0
334  Integer MultiplicativeInverse() const;
335 
336  //! modular multiplication
337  CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
338  //! modular exponentiation
339  CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
340 
341  //! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
342  static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
343  //! use a faster division algorithm when divisor is short
344  static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d);
345 
346  //! returns same result as Divide(r, q, a, Power2(n)), but faster
347  static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);
348 
349  //! greatest common divisor
350  static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n);
351  //! calculate multiplicative inverse of *this mod n
352  Integer InverseMod(const Integer &n) const;
353  //!
354  word InverseMod(word n) const;
355  //@}
356 
357  //! \name INPUT/OUTPUT
358  //@{
359  //!
360  friend CRYPTOPP_DLL std::istream& CRYPTOPP_API operator>>(std::istream& in, Integer &a);
361  //!
362  friend CRYPTOPP_DLL std::ostream& CRYPTOPP_API operator<<(std::ostream& out, const Integer &a);
363  //@}
364 
365 private:
366  friend class ModularArithmetic;
367  friend class MontgomeryRepresentation;
368  friend class HalfMontgomeryRepresentation;
369 
370  Integer(word value, size_t length);
371 
372  int PositiveCompare(const Integer &t) const;
373  friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
374  friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
375  friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
376  friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor);
377 
378  IntegerSecBlock reg;
379  Sign sign;
380 };
381 
382 //!
383 inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
384 //!
385 inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
386 //!
387 inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
388 //!
389 inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
390 //!
391 inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
392 //!
393 inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
394 //!
395 inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
396 //!
397 inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
398 //!
399 inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
400 //!
401 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
402 //!
403 inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
404 //!
405 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
406 //!
407 inline CryptoPP::word operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}
408 
409 NAMESPACE_END
410 
411 #ifndef __BORLANDC__
412 NAMESPACE_BEGIN(std)
413 inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
414 {
415  a.swap(b);
416 }
417 NAMESPACE_END
418 #endif
419 
420 #endif
base class for all exceptions thrown by Crypto++
Definition: cryptlib.h:109
bool operator>=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:249
bool operator>(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:246
virtual void DEREncode(BufferedTransformation &bt) const =0
encode this object into a BufferedTransformation, using DER (Distinguished Encoding Rules) ...
a block of memory allocated using A
Definition: secblock.h:238
ring of congruence classes modulo n
Definition: modarith.h:19
interface for random number generators
Definition: cryptlib.h:668
interface for buffered transformations
Definition: cryptlib.h:770
virtual void BERDecode(BufferedTransformation &bt)=0
decode this object from a BufferedTransformation, using BER (Basic Encoding Rules) ...
interface for encoding and decoding ASN1 objects
Definition: cryptlib.h:1633
multiple precision integer and basic arithmetics
Definition: integer.h:26
const NameValuePairs & g_nullNameValuePairs
empty set of name-value pairs
bool operator<(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:252
division by zero exception
Definition: integer.h:32
do modular arithmetics in Montgomery representation for increased speed
Definition: modarith.h:122
bool operator<=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:255
interface for retrieving values given their names
Definition: cryptlib.h:224