Fabcoin Core  0.16.2
P2P Digital Currency
integer.h
Go to the documentation of this file.
1 // integer.h - written and placed in the public domain by Wei Dai
2 
12 
13 #ifndef CRYPTOPP_INTEGER_H
14 #define CRYPTOPP_INTEGER_H
15 
16 #include "cryptlib.h"
17 #include "secblock.h"
18 #include "stdcpp.h"
19 
20 #include <iosfwd>
21 
23 
24 struct InitializeInteger
27 {
28  InitializeInteger();
29 };
30 
31 // Always align, http://github.com/weidai11/cryptopp/issues/256
33 
44 {
45 public:
47 
48  class DivideByZero : public Exception
50  {
51  public:
52  DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {}
53  };
54 
58  {
59  public:
60  RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {}
61  };
62 
67  enum Sign {
69  POSITIVE=0,
71  NEGATIVE=1};
72 
77  enum Signedness {
81  SIGNED};
82 
87  ANY,
89  PRIME};
91 
93 
94  Integer();
96 
98  Integer(const Integer& t);
99 
101  Integer(signed long value);
102 
106  Integer(Sign sign, lword value);
107 
112  Integer(Sign sign, word highWord, word lowWord);
113 
121  explicit Integer(const char *str, ByteOrder order = BIG_ENDIAN_ORDER);
122 
130  explicit Integer(const wchar_t *str, ByteOrder order = BIG_ENDIAN_ORDER);
131 
139  Integer(const byte *encodedInteger, size_t byteCount, Signedness sign=UNSIGNED, ByteOrder order = BIG_ENDIAN_ORDER);
140 
148  Integer(BufferedTransformation &bt, size_t byteCount, Signedness sign=UNSIGNED, ByteOrder order = BIG_ENDIAN_ORDER);
149 
152  explicit Integer(BufferedTransformation &bt);
153 
158  Integer(RandomNumberGenerator &rng, size_t bitCount);
159 
163  static const Integer & CRYPTOPP_API Zero();
167  static const Integer & CRYPTOPP_API One();
171  static const Integer & CRYPTOPP_API Two();
172 
189  Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());
190 
194  static Integer CRYPTOPP_API Power2(size_t e);
196 
198 
199  size_t MinEncodedSize(Signedness sign=UNSIGNED) const;
203 
211  void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const;
212 
220  void Encode(BufferedTransformation &bt, size_t outputLen, Signedness sign=UNSIGNED) const;
221 
226  void DEREncode(BufferedTransformation &bt) const;
227 
231  void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
232 
239  size_t OpenPGPEncode(byte *output, size_t bufferSize) const;
240 
246  size_t OpenPGPEncode(BufferedTransformation &bt) const;
247 
252  void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED);
253 
259  void Decode(BufferedTransformation &bt, size_t inputLen, Signedness sign=UNSIGNED);
260 
264  void BERDecode(const byte *input, size_t inputLen);
265 
268  void BERDecode(BufferedTransformation &bt);
269 
273  void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
274 
277  {
278  public:
279  OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {}
280  };
281 
285  void OpenPGPDecode(const byte *input, size_t inputLen);
288  void OpenPGPDecode(BufferedTransformation &bt);
290 
292 
293  bool IsConvertableToLong() const;
300  signed long ConvertToLong() const;
301 
304  unsigned int BitCount() const;
307  unsigned int ByteCount() const;
310  unsigned int WordCount() const;
311 
314  bool GetBit(size_t i) const;
317  byte GetByte(size_t i) const;
320  lword GetBits(size_t i, size_t n) const;
321 
324  bool IsZero() const {return !*this;}
327  bool NotZero() const {return !IsZero();}
330  bool IsNegative() const {return sign == NEGATIVE;}
333  bool NotNegative() const {return !IsNegative();}
336  bool IsPositive() const {return NotNegative() && NotZero();}
339  bool NotPositive() const {return !IsPositive();}
342  bool IsEven() const {return GetBit(0) == 0;}
345  bool IsOdd() const {return GetBit(0) == 1;}
347 
349 
350  Integer& operator=(const Integer& t);
352 
354  Integer& operator+=(const Integer& t);
356  Integer& operator-=(const Integer& t);
359  Integer& operator*=(const Integer& t) {return *this = Times(t);}
361  Integer& operator/=(const Integer& t) {return *this = DividedBy(t);}
364  Integer& operator%=(const Integer& t) {return *this = Modulo(t);}
366  Integer& operator/=(word t) {return *this = DividedBy(t);}
369  Integer& operator%=(word t) {return *this = Integer(POSITIVE, 0, Modulo(t));}
370 
372  Integer& operator<<=(size_t n);
374  Integer& operator>>=(size_t n);
375 
387  Integer& operator&=(const Integer& t);
399  Integer& operator|=(const Integer& t);
411  Integer& operator^=(const Integer& t);
412 
417  void Randomize(RandomNumberGenerator &rng, size_t bitCount);
418 
424  void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);
425 
442  bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());
443 
444  bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs);
446  {
447  if (!GenerateRandomNoThrow(rng, params))
448  throw RandomNumberNotFound();
449  }
450 
453  void SetBit(size_t n, bool value=1);
454 
457  void SetByte(size_t n, byte value);
458 
460  void Negate();
461 
463  void SetPositive() {sign = POSITIVE;}
464 
466  void SetNegative() {if (!!(*this)) sign = NEGATIVE;}
467 
469  void swap(Integer &a);
471 
473 
474  bool operator!() const;
477  Integer operator+() const {return *this;}
479  Integer operator-() const;
481  Integer& operator++();
483  Integer& operator--();
485  Integer operator++(int) {Integer temp = *this; ++*this; return temp;}
487  Integer operator--(int) {Integer temp = *this; --*this; return temp;}
489 
491 
492  int Compare(const Integer& a) const;
498 
500  Integer Plus(const Integer &b) const;
502  Integer Minus(const Integer &b) const;
505  Integer Times(const Integer &b) const;
507  Integer DividedBy(const Integer &b) const;
510  Integer Modulo(const Integer &b) const;
512  Integer DividedBy(word b) const;
515  word Modulo(word b) const;
516 
528  Integer And(const Integer&) const;
529 
541  Integer Or(const Integer&) const;
542 
554  Integer Xor(const Integer&) const;
555 
557  Integer operator>>(size_t n) const {return Integer(*this)>>=n;}
559  Integer operator<<(size_t n) const {return Integer(*this)<<=n;}
561 
563 
564  Integer AbsoluteValue() const;
567  Integer Doubled() const {return Plus(*this);}
570  Integer Squared() const {return Times(*this);}
573  Integer SquareRoot() const;
575  bool IsSquare() const;
576 
578  bool IsUnit() const;
580  Integer MultiplicativeInverse() const;
581 
583  static void CRYPTOPP_API Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
585  static void CRYPTOPP_API Divide(word &r, Integer &q, const Integer &a, word d);
586 
588  static void CRYPTOPP_API DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);
589 
591  static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n);
593  Integer InverseMod(const Integer &n) const;
596  word InverseMod(word n) const;
598 
600 
601  friend CRYPTOPP_DLL std::istream& CRYPTOPP_API operator>>(std::istream& in, Integer &a);
617  friend CRYPTOPP_DLL std::ostream& CRYPTOPP_API operator<<(std::ostream& out, const Integer &a);
619 
620 #ifndef CRYPTOPP_DOXYGEN_PROCESSING
621  CRYPTOPP_DLL friend Integer CRYPTOPP_API a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
624  CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
625 #endif
626 
627 private:
628 
629  Integer(word value, size_t length);
630  int PositiveCompare(const Integer &t) const;
631 
634 
635 #ifndef CRYPTOPP_DOXYGEN_PROCESSING
636  friend class ModularArithmetic;
638  friend class HalfMontgomeryRepresentation;
639 
640  friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
641  friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
642  friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
643  friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor);
644 #endif
645 };
646 
648 inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
650 inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
652 inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
654 inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
656 inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
658 inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
660 inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
662 inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
665 inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
667 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
670 inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
672 inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
675 inline CryptoPP::word operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}
676 
689 inline CryptoPP::Integer operator&(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.And(b);}
690 
703 inline CryptoPP::Integer operator|(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Or(b);}
704 
717 inline CryptoPP::Integer operator^(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Xor(b);}
718 
720 
721 #ifndef __BORLANDC__
724 {
725  a.swap(b);
726 }
728 #endif
729 
730 #endif
Base class for all exceptions thrown by the library.
Definition: cryptlib.h:140
CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Subtraction.
Definition: integer.h:662
SecBlock< word, AllocatorWithCleanup< word, true > > IntegerSecBlock
Definition: integer.h:32
void SetNegative()
Sets the Integer to negative.
Definition: integer.h:466
Integer & operator/=(word t)
Division Assignment.
Definition: integer.h:366
NAMESPACE_END void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
Definition: integer.h:723
Integer operator+() const
Addition.
Definition: integer.h:477
uint8_t byte
Definition: Common.h:57
Integer operator--(int)
Post-decrement.
Definition: integer.h:487
ByteOrder
Provides the byte ordering.
Definition: cryptlib.h:124
bool NotZero() const
Determines if the Integer is non-0.
Definition: integer.h:327
CryptoPP::Integer operator^(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Bitwise XOR.
Definition: integer.h:717
an unsigned value
Definition: integer.h:79
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:345
Integer a_times_b_mod_c(const Integer &x, const Integer &y, const Integer &m)
Definition: integer.cpp:4354
void SetPositive()
Sets the Integer to positive.
Definition: integer.h:463
void PositiveMultiply(Integer &product, const Integer &a, const Integer &b)
Definition: integer.cpp:4066
#define NAMESPACE_BEGIN(x)
Definition: config.h:200
CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Multiplication.
Definition: integer.h:665
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:342
Secure memory block with allocator and cleanup.
Definition: secblock.h:437
Abstract base classes that provide a uniform interface to this library.
bool operator<(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Comparison.
Definition: integer.h:656
Signedness
Used when importing and exporting integers.
Definition: integer.h:77
Ring of congruence classes modulo n.
Definition: modarith.h:34
std::hash for asio::adress
Definition: Common.h:323
Interface for random number generators.
Definition: cryptlib.h:1188
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Definition: integer.h:445
ExecStats::duration min
Definition: ExecStats.cpp:35
Interface for buffered transformations.
Definition: cryptlib.h:1352
IntegerSecBlock reg
Definition: integer.h:632
Sign
Used internally to represent the integer.
Definition: integer.h:67
void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b)
Definition: integer.cpp:3844
Classes and functions for secure memory allocations.
Integer & operator/=(const Integer &t)
Division Assignment.
Definition: integer.h:361
Integer operator<<(size_t n) const
Left-shift.
Definition: integer.h:559
#define a(i)
#define x(i)
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:336
a number with no special properties
Definition: integer.h:87
Integer Squared() const
Multiply this integer by itself.
Definition: integer.h:570
bool IsNegative() const
Determines if the Integer is negative.
Definition: integer.h:330
bool NotPositive() const
Determines if the Integer is non-positive.
Definition: integer.h:339
Exception thrown when an error is encountered decoding an OpenPGP integer.
Definition: integer.h:276
Interface for encoding and decoding ASN1 objects.
Definition: cryptlib.h:2942
ExecStats::duration max
Definition: ExecStats.cpp:36
void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &a, const Integer &b)
Definition: integer.cpp:4115
Performs static initialization of the Integer class.
Definition: integer.h:26
bool operator==(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Comparison.
Definition: integer.h:648
void PositiveAdd(Integer &sum, const Integer &a, const Integer &b)
Definition: integer.cpp:3814
bool operator>(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Comparison.
Definition: integer.h:652
CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Addition.
Definition: integer.h:660
Multiple precision integer with arithmetic operations.
Definition: integer.h:43
void Divide(word *R, word *Q, word *T, const word *A, size_t NA, const word *B, size_t NB)
Definition: integer.cpp:2692
CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Remainder.
Definition: integer.h:670
#define CRYPTOPP_API
Definition: config.h:705
RandomNumberType
Properties of a random integer.
Definition: integer.h:85
CryptoPP::Integer operator&(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Bitwise AND.
Definition: integer.h:689
byte order is big-endian
Definition: cryptlib.h:128
Integer & operator*=(const Integer &t)
Multiplication Assignment.
Definition: integer.h:359
volatile double sum
Definition: Examples.cpp:23
#define b(i, j)
const NameValuePairs & g_nullNameValuePairs
An empty set of name-value pairs.
Definition: cryptlib.cpp:76
bool IsZero() const
Determines if the Integer is 0.
Definition: integer.h:324
std::ostream & operator<<(std::ostream &_out, bytes const &_e)
Definition: CommonIO.h:80
Integer operator++(int)
Post-increment.
Definition: integer.h:485
Signature sign(Secret const &_k, h256 const &_hash)
Returns siganture of message hash.
Definition: Common.cpp:233
Exception thrown when division by 0 is encountered.
Definition: integer.h:49
CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Division.
Definition: integer.h:667
Exception thrown when a random number cannot be found that satisfies the condition.
Definition: integer.h:57
Performs modular arithmetic in Montgomery representation for increased speed.
Definition: modarith.h:271
std::vector< T > & operator+=(std::vector< typename std::enable_if< std::is_pod< T >::value, T >::type > &_a, std::vector< T > const &_b)
Concatenate two vectors of elements of POD types.
Definition: CommonData.h:236
Integer Doubled() const
Add this integer to itself.
Definition: integer.h:567
N diff(N const &_a, N const &_b)
Definition: Common.h:212
std::istream & operator>>(std::istream &in, Integer &a)
Definition: integer.cpp:3604
bool operator<=(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Comparison.
Definition: integer.h:658
bool operator!=(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Comparison.
Definition: integer.h:650
Sign sign
Definition: integer.h:633
#define NAMESPACE_END
Definition: config.h:201
#define e(i)
Definition: sha.cpp:733
CryptoPP::Integer operator|(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Bitwise OR.
Definition: integer.h:703
Integer operator>>(size_t n) const
Right-shift.
Definition: integer.h:557
word64 lword
Definition: config.h:245
Integer & operator%=(word t)
Remainder Assignment.
Definition: integer.h:369
#define d(i)
Definition: sha.cpp:732
bool operator>=(const CryptoPP::Integer &a, const CryptoPP::Integer &b)
Comparison.
Definition: integer.h:654
Integer a_exp_b_mod_c(const Integer &x, const Integer &e, const Integer &m)
Definition: integer.cpp:4359
#define CRYPTOPP_DLL
Definition: config.h:704
unsigned int GetByte(ByteOrder order, T value, unsigned int index)
Gets a byte from a value.
Definition: misc.h:1652
Integer & operator%=(const Integer &t)
Remainder Assignment.
Definition: integer.h:364
word32 word
Definition: config.h:308
bool NotNegative() const
Determines if the Integer is non-negative.
Definition: integer.h:333
Interface for retrieving values given their names.
Definition: cryptlib.h:279