summaryrefslogtreecommitdiff
path: root/modarith.h
blob: a00582ebc9992ef4a8962dac518b6c108ea1165c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
// modarith.h - originally written and placed in the public domain by Wei Dai

/// \file modarith.h
/// \brief Class file for performing modular arithmetic.

#ifndef CRYPTOPP_MODARITH_H
#define CRYPTOPP_MODARITH_H

// implementations are in integer.cpp

#include "cryptlib.h"
#include "integer.h"
#include "algebra.h"
#include "secblock.h"
#include "misc.h"

#if CRYPTOPP_MSC_VERSION
# pragma warning(push)
# pragma warning(disable: 4231 4275)
#endif

NAMESPACE_BEGIN(CryptoPP)

CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<Integer>;
CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<Integer>;
CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<Integer>;

/// \brief Ring of congruence classes modulo n
/// \details This implementation represents each congruence class as the smallest
///   non-negative integer in that class.
/// \details <tt>const Element&</tt> returned by member functions are references
///   to internal data members. Since each object may have only
///   one such data member for holding results, the following code
///   will produce incorrect results:
///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>
///   But this should be fine:
///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>
class CRYPTOPP_DLL ModularArithmetic : public AbstractRing<Integer>
{
public:

	typedef int RandomizationParameter;
	typedef Integer Element;

	virtual ~ModularArithmetic() {}

	/// \brief Construct a ModularArithmetic
	/// \param modulus congruence class modulus
	ModularArithmetic(const Integer &modulus = Integer::One())
		: AbstractRing<Integer>(), m_modulus(modulus), m_result(static_cast<word>(0), modulus.reg.size()) {}

	/// \brief Copy construct a ModularArithmetic
	/// \param ma other ModularArithmetic
	ModularArithmetic(const ModularArithmetic &ma)
		: AbstractRing<Integer>(), m_modulus(ma.m_modulus), m_result(static_cast<word>(0), ma.m_modulus.reg.size()) {}

	/// \brief Construct a ModularArithmetic
	/// \param bt BER encoded ModularArithmetic
	ModularArithmetic(BufferedTransformation &bt);	// construct from BER encoded parameters

	/// \brief Clone a ModularArithmetic
	/// \returns pointer to a new ModularArithmetic
	/// \details Clone effectively copy constructs a new ModularArithmetic. The caller is
	///   responsible for deleting the pointer returned from this method.
	virtual ModularArithmetic * Clone() const {return new ModularArithmetic(*this);}

	/// \brief Encodes in DER format
	/// \param bt BufferedTransformation object
	void DEREncode(BufferedTransformation &bt) const;

	/// \brief Encodes element in DER format
	/// \param out BufferedTransformation object
	/// \param a Element to encode
	void DEREncodeElement(BufferedTransformation &out, const Element &a) const;

	/// \brief Decodes element in DER format
	/// \param in BufferedTransformation object
	/// \param a Element to decode
	void BERDecodeElement(BufferedTransformation &in, Element &a) const;

	/// \brief Retrieves the modulus
	/// \returns the modulus
	const Integer& GetModulus() const {return m_modulus;}

	/// \brief Sets the modulus
	/// \param newModulus the new modulus
	void SetModulus(const Integer &newModulus)
		{m_modulus = newModulus; m_result.reg.resize(m_modulus.reg.size());}

	/// \brief Retrieves the representation
	/// \returns true if the if the modulus is in Montgomery form for multiplication, false otherwise
	virtual bool IsMontgomeryRepresentation() const {return false;}

	/// \brief Reduces an element in the congruence class
	/// \param a element to convert
	/// \returns the reduced element
	/// \details ConvertIn is useful for derived classes, like MontgomeryRepresentation, which
	///   must convert between representations.
	virtual Integer ConvertIn(const Integer &a) const
		{return a%m_modulus;}

	/// \brief Reduces an element in the congruence class
	/// \param a element to convert
	/// \returns the reduced element
	/// \details ConvertOut is useful for derived classes, like MontgomeryRepresentation, which
	///   must convert between representations.
	virtual Integer ConvertOut(const Integer &a) const
		{return a;}

	/// \brief Divides an element by 2
	/// \param a element to convert
	const Integer& Half(const Integer &a) const;

	/// \brief Compare two elements for equality
	/// \param a first element
	/// \param b second element
	/// \returns true if the elements are equal, false otherwise
	/// \details Equal() tests the elements for equality using <tt>a==b</tt>
	bool Equal(const Integer &a, const Integer &b) const
		{return a==b;}

	/// \brief Provides the Identity element
	/// \returns the Identity element
	const Integer& Identity() const
		{return Integer::Zero();}

	/// \brief Adds elements in the ring
	/// \param a first element
	/// \param b second element
	/// \returns the sum of <tt>a</tt> and <tt>b</tt>
	const Integer& Add(const Integer &a, const Integer &b) const;

	/// \brief TODO
	/// \param a first element
	/// \param b second element
	/// \returns TODO
	Integer& Accumulate(Integer &a, const Integer &b) const;

	/// \brief Inverts the element in the ring
	/// \param a first element
	/// \returns the inverse of the element
	const Integer& Inverse(const Integer &a) const;

	/// \brief Subtracts elements in the ring
	/// \param a first element
	/// \param b second element
	/// \returns the difference of <tt>a</tt> and <tt>b</tt>. The element <tt>a</tt> must provide a Subtract member function.
	const Integer& Subtract(const Integer &a, const Integer &b) const;

	/// \brief TODO
	/// \param a first element
	/// \param b second element
	/// \returns TODO
	Integer& Reduce(Integer &a, const Integer &b) const;

	/// \brief Doubles an element in the ring
	/// \param a the element
	/// \returns the element doubled
	/// \details Double returns <tt>Add(a, a)</tt>. The element <tt>a</tt> must provide an Add member function.
	const Integer& Double(const Integer &a) const
		{return Add(a, a);}

	/// \brief Retrieves the multiplicative identity
	/// \returns the multiplicative identity
	/// \details the base class implementations returns 1.
	const Integer& MultiplicativeIdentity() const
		{return Integer::One();}

	/// \brief Multiplies elements in the ring
	/// \param a the multiplicand
	/// \param b the multiplier
	/// \returns the product of a and b
	/// \details Multiply returns <tt>a*b\%n</tt>.
	const Integer& Multiply(const Integer &a, const Integer &b) const
		{return m_result1 = a*b%m_modulus;}

	/// \brief Square an element in the ring
	/// \param a the element
	/// \returns the element squared
	/// \details Square returns <tt>a*a\%n</tt>. The element <tt>a</tt> must provide a Square member function.
	const Integer& Square(const Integer &a) const
		{return m_result1 = a.Squared()%m_modulus;}

	/// \brief Determines whether an element is a unit in the ring
	/// \param a the element
	/// \returns true if the element is a unit after reduction, false otherwise.
	bool IsUnit(const Integer &a) const
		{return Integer::Gcd(a, m_modulus).IsUnit();}

	/// \brief Calculate the multiplicative inverse of an element in the ring
	/// \param a the element
	/// \details MultiplicativeInverse returns <tt>a<sup>-1</sup>\%n</tt>. The element <tt>a</tt> must
	///   provide a InverseMod member function.
	const Integer& MultiplicativeInverse(const Integer &a) const
		{return m_result1 = a.InverseMod(m_modulus);}

	/// \brief Divides elements in the ring
	/// \param a the dividend
	/// \param b the divisor
	/// \returns the quotient
	/// \details Divide returns <tt>a*b<sup>-1</sup>\%n</tt>.
	const Integer& Divide(const Integer &a, const Integer &b) const
		{return Multiply(a, MultiplicativeInverse(b));}

	/// \brief TODO
	/// \param x first element
	/// \param e1 first exponent
	/// \param y second element
	/// \param e2 second exponent
	/// \returns TODO
	Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const;

	/// \brief Exponentiates a base to multiple exponents in the ring
	/// \param results an array of Elements
	/// \param base the base to raise to the exponents
	/// \param exponents an array of exponents
	/// \param exponentsCount the number of exponents in the array
	/// \details SimultaneousExponentiate() raises the base to each exponent in the exponents array and stores the
	///   result at the respective position in the results array.
	/// \details SimultaneousExponentiate() must be implemented in a derived class.
	/// \pre <tt>COUNTOF(results) == exponentsCount</tt>
	/// \pre <tt>COUNTOF(exponents) == exponentsCount</tt>
	void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const;

	/// \brief Provides the maximum bit size of an element in the ring
	/// \returns maximum bit size of an element
	unsigned int MaxElementBitLength() const
		{return (m_modulus-1).BitCount();}

	/// \brief Provides the maximum byte size of an element in the ring
	/// \returns maximum byte size of an element
	unsigned int MaxElementByteLength() const
		{return (m_modulus-1).ByteCount();}

	/// \brief Provides a random element in the ring
	/// \param rng RandomNumberGenerator used to generate material
	/// \param ignore_for_now unused
	/// \returns a random element that is uniformly distributed
	/// \details RandomElement constructs a new element in the range <tt>[0,n-1]</tt>, inclusive.
	///   The element's class must provide a constructor with the signature <tt>Element(RandomNumberGenerator rng,
	///   Element min, Element max)</tt>.
	Element RandomElement(RandomNumberGenerator &rng , const RandomizationParameter &ignore_for_now = 0) const
		// left RandomizationParameter arg as ref in case RandomizationParameter becomes a more complicated struct
	{
		CRYPTOPP_UNUSED(ignore_for_now);
		return Element(rng, Integer::Zero(), m_modulus - Integer::One()) ;
	}

	/// \brief Compares two ModularArithmetic for equality
	/// \param rhs other ModularArithmetic
	/// \returns true if this is equal to the other, false otherwise
	/// \details The operator tests for equality using <tt>this.m_modulus == rhs.m_modulus</tt>.
	bool operator==(const ModularArithmetic &rhs) const
		{return m_modulus == rhs.m_modulus;}

	static const RandomizationParameter DefaultRandomizationParameter ;

protected:
	Integer m_modulus;
	mutable Integer m_result, m_result1;
};

// const ModularArithmetic::RandomizationParameter ModularArithmetic::DefaultRandomizationParameter = 0 ;

/// \brief Performs modular arithmetic in Montgomery representation for increased speed
/// \details The Montgomery representation represents each congruence class <tt>[a]</tt> as
///   <tt>a*r\%n</tt>, where <tt>r</tt> is a convenient power of 2.
/// \details <tt>const Element&</tt> returned by member functions are references to
///   internal data members. Since each object may have only one such data member for holding
///   results, the following code will produce incorrect results:
///   <pre>    abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre>
///   But this should be fine:
///   <pre>    abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre>
class CRYPTOPP_DLL MontgomeryRepresentation : public ModularArithmetic
{
public:
	virtual ~MontgomeryRepresentation() {}

	/// \brief Construct a MontgomeryRepresentation
	/// \param modulus congruence class modulus
	/// \note The modulus must be odd.
	MontgomeryRepresentation(const Integer &modulus);

	/// \brief Clone a MontgomeryRepresentation
	/// \returns pointer to a new MontgomeryRepresentation
	/// \details Clone effectively copy constructs a new MontgomeryRepresentation. The caller is
	///   responsible for deleting the pointer returned from this method.
	virtual ModularArithmetic * Clone() const {return new MontgomeryRepresentation(*this);}

	bool IsMontgomeryRepresentation() const {return true;}

	Integer ConvertIn(const Integer &a) const
		{return (a<<(WORD_BITS*m_modulus.reg.size()))%m_modulus;}

	Integer ConvertOut(const Integer &a) const;

	const Integer& MultiplicativeIdentity() const
		{return m_result1 = Integer::Power2(WORD_BITS*m_modulus.reg.size())%m_modulus;}

	const Integer& Multiply(const Integer &a, const Integer &b) const;

	const Integer& Square(const Integer &a) const;

	const Integer& MultiplicativeInverse(const Integer &a) const;

	Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
		{return AbstractRing<Integer>::CascadeExponentiate(x, e1, y, e2);}

	void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
		{AbstractRing<Integer>::SimultaneousExponentiate(results, base, exponents, exponentsCount);}

private:
	Integer m_u;
	mutable IntegerSecBlock m_workspace;
};

NAMESPACE_END

#if CRYPTOPP_MSC_VERSION
# pragma warning(pop)
#endif

#endif