Crypto++  5.6.3
Free C++ class library of cryptographic schemes
modarith.h
Go to the documentation of this file.
1 // modarith.h - written and placed in the public domain by Wei Dai
2 
3 //! \file modarith.h
4 //! \brief Class file for performing modular arithmetic.
5 
6 #ifndef CRYPTOPP_MODARITH_H
7 #define CRYPTOPP_MODARITH_H
8 
9 // implementations are in integer.cpp
10 
11 #include "cryptlib.h"
12 #include "integer.h"
13 #include "algebra.h"
14 #include "secblock.h"
15 #include "misc.h"
16 
17 NAMESPACE_BEGIN(CryptoPP)
18 
19 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<Integer>;
20 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<Integer>;
21 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<Integer>;
22 
23 //! \class ModularArithmetic
24 //! \brief Ring of congruence classes modulo n
25 //! \note this implementation represents each congruence class as the smallest
26 //! non-negative integer in that class
27 class CRYPTOPP_DLL ModularArithmetic : public AbstractRing<Integer>
28 {
29 public:
30 
31  typedef int RandomizationParameter;
32  typedef Integer Element;
33 
34  ModularArithmetic(const Integer &modulus = Integer::One())
35  : AbstractRing<Integer>(), m_modulus(modulus), m_result((word)0, modulus.reg.size()) {}
37  : AbstractRing<Integer>(), m_modulus(ma.m_modulus), m_result((word)0, ma.m_modulus.reg.size()) {}
38 
39  ModularArithmetic(BufferedTransformation &bt); // construct from BER encoded parameters
40 
41  virtual ModularArithmetic * Clone() const {return new ModularArithmetic(*this);}
42 
43  void DEREncode(BufferedTransformation &bt) const;
44 
45  void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
46  void BERDecodeElement(BufferedTransformation &in, Element &a) const;
47 
48  const Integer& GetModulus() const {return m_modulus;}
49  void SetModulus(const Integer &newModulus)
50  {m_modulus = newModulus; m_result.reg.resize(m_modulus.reg.size());}
51 
52  virtual bool IsMontgomeryRepresentation() const {return false;}
53 
54  virtual Integer ConvertIn(const Integer &a) const
55  {return a%m_modulus;}
56 
57  virtual Integer ConvertOut(const Integer &a) const
58  {return a;}
59 
60  const Integer& Half(const Integer &a) const;
61 
62  bool Equal(const Integer &a, const Integer &b) const
63  {return a==b;}
64 
65  const Integer& Identity() const
66  {return Integer::Zero();}
67 
68  const Integer& Add(const Integer &a, const Integer &b) const;
69 
70  Integer& Accumulate(Integer &a, const Integer &b) const;
71 
72  const Integer& Inverse(const Integer &a) const;
73 
74  const Integer& Subtract(const Integer &a, const Integer &b) const;
75 
76  Integer& Reduce(Integer &a, const Integer &b) const;
77 
78  const Integer& Double(const Integer &a) const
79  {return Add(a, a);}
80 
81  const Integer& MultiplicativeIdentity() const
82  {return Integer::One();}
83 
84  const Integer& Multiply(const Integer &a, const Integer &b) const
85  {return m_result1 = a*b%m_modulus;}
86 
87  const Integer& Square(const Integer &a) const
88  {return m_result1 = a.Squared()%m_modulus;}
89 
90  bool IsUnit(const Integer &a) const
91  {return Integer::Gcd(a, m_modulus).IsUnit();}
92 
93  const Integer& MultiplicativeInverse(const Integer &a) const
94  {return m_result1 = a.InverseMod(m_modulus);}
95 
96  const Integer& Divide(const Integer &a, const Integer &b) const
97  {return Multiply(a, MultiplicativeInverse(b));}
98 
99  Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const;
100 
101  void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
102 
103  unsigned int MaxElementBitLength() const
104  {return (m_modulus-1).BitCount();}
105 
106  unsigned int MaxElementByteLength() const
107  {return (m_modulus-1).ByteCount();}
108 
109  Element RandomElement( RandomNumberGenerator &rng , const RandomizationParameter &ignore_for_now = 0 ) const
110  // left RandomizationParameter arg as ref in case RandomizationParameter becomes a more complicated struct
111  {
112  CRYPTOPP_UNUSED(ignore_for_now);
113  return Element(rng, Integer::Zero(), m_modulus - Integer::One()) ;
114  }
115 
116  bool operator==(const ModularArithmetic &rhs) const
117  {return m_modulus == rhs.m_modulus;}
118 
119  static const RandomizationParameter DefaultRandomizationParameter ;
120 
121 #ifndef CRYPTOPP_MAINTAIN_BACKWARDS_COMPATIBILITY_562
122  virtual ~ModularArithmetic() {}
123 #endif
124 
125 protected:
126  Integer m_modulus;
127  mutable Integer m_result, m_result1;
128 
129 };
130 
131 // const ModularArithmetic::RandomizationParameter ModularArithmetic::DefaultRandomizationParameter = 0 ;
132 
133 //! \class MontgomeryRepresentation
134 //! \brief Performs modular arithmetic in Montgomery representation for increased speed
135 //! \details The Montgomery representation represents each congruence class <tt>[a]</tt> as
136 //! <tt>a*r%n</tt>, where r is a convenient power of 2.
137 class CRYPTOPP_DLL MontgomeryRepresentation : public ModularArithmetic
138 {
139 public:
140  MontgomeryRepresentation(const Integer &modulus); // modulus must be odd
141 
142  virtual ModularArithmetic * Clone() const {return new MontgomeryRepresentation(*this);}
143 
144  bool IsMontgomeryRepresentation() const {return true;}
145 
146  Integer ConvertIn(const Integer &a) const
147  {return (a<<(WORD_BITS*m_modulus.reg.size()))%m_modulus;}
148 
149  Integer ConvertOut(const Integer &a) const;
150 
151  const Integer& MultiplicativeIdentity() const
152  {return m_result1 = Integer::Power2(WORD_BITS*m_modulus.reg.size())%m_modulus;}
153 
154  const Integer& Multiply(const Integer &a, const Integer &b) const;
155 
156  const Integer& Square(const Integer &a) const;
157 
158  const Integer& MultiplicativeInverse(const Integer &a) const;
159 
160  Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
161  {return AbstractRing<Integer>::CascadeExponentiate(x, e1, y, e2);}
162 
163  void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
164  {AbstractRing<Integer>::SimultaneousExponentiate(results, base, exponents, exponentsCount);}
165 
166 #ifndef CRYPTOPP_MAINTAIN_BACKWARDS_COMPATIBILITY_562
167  virtual ~MontgomeryRepresentation() {}
168 #endif
169 
170 private:
171  Integer m_u;
172  mutable IntegerSecBlock m_workspace;
173 };
174 
175 NAMESPACE_END
176 
177 #endif
Utility functions for the Crypto++ library.
static Integer Gcd(const Integer &a, const Integer &n)
greatest common divisor
Definition: integer.cpp:4118
void resize(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:697
Abstract base classes that provide a uniform interface to this library.
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:516
Abstract Euclidean Domain.
Definition: algebra.h:148
Square block cipher.
Definition: square.h:24
Ring of congruence classes modulo n.
Definition: modarith.h:27
Interface for random number generators.
Definition: cryptlib.h:1176
Classes for performing mathematics over different fields.
Interface for buffered transformations.
Definition: cryptlib.h:1342
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:2944
Abstract Ring.
Definition: algebra.h:52
Classes and functions for secure memory allocations.
bool IsUnit() const
is 1 or -1
Definition: integer.cpp:4097
Integer Squared() const
Definition: integer.h:482
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:2923
Multiple precision integer with arithmetic operations.
Definition: integer.h:31
Abstract Group.
Definition: algebra.h:27
Performs modular arithmetic in Montgomery representation for increased speed.
Definition: modarith.h:137
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:4123
static const Integer & Zero()
Integer representing 0.
Definition: integer.cpp:2939
Crypto++ library namespace.