Security Scol plugin
modarith.h
Go to the documentation of this file.
1// modarith.h - originally written and placed in the public domain by Wei Dai
2
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#if CRYPTOPP_MSC_VERSION
18# pragma warning(push)
19# pragma warning(disable: 4231 4275)
20#endif
21
22NAMESPACE_BEGIN(CryptoPP)
23
24CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<Integer>;
25CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<Integer>;
26CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<Integer>;
27
43class CRYPTOPP_DLL ModularArithmetic : public AbstractRing<Integer>
44{
45public:
46
47 typedef int RandomizationParameter;
48 typedef Integer Element;
49
50 virtual ~ModularArithmetic() {}
51
55 : m_modulus(modulus), m_result(static_cast<word>(0), modulus.reg.size()) {}
56
60 : AbstractRing<Integer>(ma), m_modulus(ma.m_modulus), m_result(static_cast<word>(0), m_modulus.reg.size()) {}
61
65 if (this != &ma)
66 {
67 m_modulus = ma.m_modulus;
68 m_result = Integer(static_cast<word>(0), m_modulus.reg.size());
69 }
70 return *this;
71 }
72
75 ModularArithmetic(BufferedTransformation &bt); // construct from BER encoded parameters
76
81 virtual ModularArithmetic * Clone() const {return new ModularArithmetic(*this);}
82
85 void DEREncode(BufferedTransformation &bt) const;
86
90 void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
91
95 void BERDecodeElement(BufferedTransformation &in, Element &a) const;
96
99 const Integer& GetModulus() const {return m_modulus;}
100
103 void SetModulus(const Integer &newModulus)
104 {m_modulus = newModulus; m_result.reg.resize(m_modulus.reg.size());}
105
108 virtual bool IsMontgomeryRepresentation() const {return false;}
109
115 virtual Integer ConvertIn(const Integer &a) const
116 {return a%m_modulus;}
117
123 virtual Integer ConvertOut(const Integer &a) const
124 {return a;}
125
128 const Integer& Half(const Integer &a) const;
129
135 bool Equal(const Integer &a, const Integer &b) const
136 {return a==b;}
137
140 const Integer& Identity() const
141 {return Integer::Zero();}
142
147 const Integer& Add(const Integer &a, const Integer &b) const;
148
153 Integer& Accumulate(Integer &a, const Integer &b) const;
154
158 const Integer& Inverse(const Integer &a) const;
159
164 const Integer& Subtract(const Integer &a, const Integer &b) const;
165
170 Integer& Reduce(Integer &a, const Integer &b) const;
171
176 const Integer& Double(const Integer &a) const
177 {return Add(a, a);}
178
183 {return Integer::One();}
184
190 const Integer& Multiply(const Integer &a, const Integer &b) const
191 {return m_result1 = a*b%m_modulus;}
192
197 const Integer& Square(const Integer &a) const
198 {return m_result1 = a.Squared()%m_modulus;}
199
203 bool IsUnit(const Integer &a) const
204 {return Integer::Gcd(a, m_modulus).IsUnit();}
205
210 const Integer& MultiplicativeInverse(const Integer &a) const
211 {return m_result1 = a.InverseMod(m_modulus);}
212
218 const Integer& Divide(const Integer &a, const Integer &b) const
219 {return Multiply(a, MultiplicativeInverse(b));}
220
227 Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const;
228
239 void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;
240
243 unsigned int MaxElementBitLength() const
244 {return (m_modulus-1).BitCount();}
245
248 unsigned int MaxElementByteLength() const
249 {return (m_modulus-1).ByteCount();}
250
258 Element RandomElement(RandomNumberGenerator &rng, const RandomizationParameter &ignore_for_now = 0) const
259 // left RandomizationParameter arg as ref in case RandomizationParameter becomes a more complicated struct
260 {
261 CRYPTOPP_UNUSED(ignore_for_now);
262 return Element(rng, Integer::Zero(), m_modulus - Integer::One()) ;
263 }
264
269 bool operator==(const ModularArithmetic &rhs) const
270 {return m_modulus == rhs.m_modulus;}
271
272 static const RandomizationParameter DefaultRandomizationParameter;
273
274private:
275 // TODO: Clang on OS X needs a real operator=.
276 // Squash warning on missing assignment operator.
277 // ModularArithmetic& operator=(const ModularArithmetic &ma);
278
279protected:
280 Integer m_modulus;
281 mutable Integer m_result, m_result1;
282};
283
284// const ModularArithmetic::RandomizationParameter ModularArithmetic::DefaultRandomizationParameter = 0 ;
285
296{
297public:
298 virtual ~MontgomeryRepresentation() {}
299
303 MontgomeryRepresentation(const Integer &modulus);
304
309 virtual ModularArithmetic * Clone() const {return new MontgomeryRepresentation(*this);}
310
311 bool IsMontgomeryRepresentation() const {return true;}
312
313 Integer ConvertIn(const Integer &a) const
314 {return (a<<(WORD_BITS*m_modulus.reg.size()))%m_modulus;}
315
316 Integer ConvertOut(const Integer &a) const;
317
319 {return m_result1 = Integer::Power2(WORD_BITS*m_modulus.reg.size())%m_modulus;}
320
321 const Integer& Multiply(const Integer &a, const Integer &b) const;
322
323 const Integer& Square(const Integer &a) const;
324
325 const Integer& MultiplicativeInverse(const Integer &a) const;
326
327 Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
328 {return AbstractRing<Integer>::CascadeExponentiate(x, e1, y, e2);}
329
330 void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
331 {AbstractRing<Integer>::SimultaneousExponentiate(results, base, exponents, exponentsCount);}
332
333private:
334 Integer m_u;
335 mutable IntegerSecBlock m_workspace;
336};
337
338NAMESPACE_END
339
340#if CRYPTOPP_MSC_VERSION
341# pragma warning(pop)
342#endif
343
344#endif
Classes for performing mathematics over different fields.
Abstract Euclidean domain.
Definition algebra.h:277
Abstract group.
Definition algebra.h:27
virtual Element & Reduce(Element &a, const Element &b) const
Reduces an element in the congruence class.
Definition algebra.cpp:32
virtual const Element & Add(const Element &a, const Element &b) const =0
Adds elements in the group.
virtual const Element & Subtract(const Element &a, const Element &b) const
Subtracts elements in the group.
Definition algebra.cpp:20
virtual Element & Accumulate(Element &a, const Element &b) const
TODO.
Definition algebra.cpp:27
virtual const Element & Inverse(const Element &a) const =0
Inverts the element in the group.
Abstract ring.
Definition algebra.h:119
virtual const Element & Multiply(const Element &a, const Element &b) const =0
Multiplies elements in the group.
virtual void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the Ring.
Definition algebra.cpp:334
virtual const Element & MultiplicativeInverse(const Element &a) const =0
Calculate the multiplicative inverse of an element in the group.
virtual Element CascadeExponentiate(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Definition algebra.cpp:323
Interface for buffered transformations.
Definition cryptlib.h:1652
Multiple precision integer with arithmetic operations.
Definition integer.h:50
static const Integer &CRYPTOPP_API Zero()
Integer representing 0.
Definition integer.cpp:4908
static Integer CRYPTOPP_API Gcd(const Integer &a, const Integer &n)
Calculate greatest common divisor.
Definition integer.cpp:4468
static const Integer &CRYPTOPP_API One()
Integer representing 1.
Definition integer.cpp:4920
static Integer CRYPTOPP_API Power2(size_t e)
Exponentiates to a power of 2.
Definition integer.cpp:3087
bool IsUnit() const
Determine if 1 or -1.
Definition integer.cpp:4439
Ring of congruence classes modulo n.
Definition modarith.h:44
bool IsUnit(const Integer &a) const
Determines whether an element is a unit in the ring.
Definition modarith.h:203
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Definition modarith.h:182
bool operator==(const ModularArithmetic &rhs) const
Compares two ModularArithmetic for equality.
Definition modarith.h:269
ModularArithmetic(const Integer &modulus=Integer::One())
Construct a ModularArithmetic.
Definition modarith.h:54
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
Definition modarith.h:210
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition modarith.h:197
void SetModulus(const Integer &newModulus)
Sets the modulus.
Definition modarith.h:103
const Integer & Double(const Integer &a) const
Doubles an element in the ring.
Definition modarith.h:176
unsigned int MaxElementBitLength() const
Provides the maximum bit size of an element in the ring.
Definition modarith.h:243
unsigned int MaxElementByteLength() const
Provides the maximum byte size of an element in the ring.
Definition modarith.h:248
virtual ModularArithmetic * Clone() const
Clone a ModularArithmetic.
Definition modarith.h:81
Element RandomElement(RandomNumberGenerator &rng, const RandomizationParameter &ignore_for_now=0) const
Provides a random element in the ring.
Definition modarith.h:258
ModularArithmetic & operator=(const ModularArithmetic &ma)
Assign a ModularArithmetic.
Definition modarith.h:64
ModularArithmetic(const ModularArithmetic &ma)
Copy construct a ModularArithmetic.
Definition modarith.h:59
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.
Definition modarith.h:108
bool Equal(const Integer &a, const Integer &b) const
Compare two elements for equality.
Definition modarith.h:135
const Integer & GetModulus() const
Retrieves the modulus.
Definition modarith.h:99
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition modarith.h:190
const Integer & Identity() const
Provides the Identity element.
Definition modarith.h:140
virtual Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
Definition modarith.h:123
const Integer & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
Definition modarith.h:218
virtual Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
Definition modarith.h:115
Performs modular arithmetic in Montgomery representation for increased speed.
Definition modarith.h:296
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the Ring.
Definition modarith.h:330
Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
Definition modarith.h:313
bool IsMontgomeryRepresentation() const
Retrieves the representation.
Definition modarith.h:311
Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
TODO.
Definition modarith.h:327
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Definition modarith.h:318
virtual ModularArithmetic * Clone() const
Clone a MontgomeryRepresentation.
Definition modarith.h:309
Interface for random number generators.
Definition cryptlib.h:1435
void resize(size_type newSize)
Change size and preserve contents.
Definition secblock.h:1198
Square block cipher.
Definition square.h:25
const unsigned int WORD_BITS
Size of a platform word in bits.
Definition config_int.h:249
Abstract base classes that provide a uniform interface to this library.
Multiple precision integer with arithmetic operations.
Utility functions for the Crypto++ library.
Classes and functions for secure memory allocations.