Line | Count | Source (jump to first uncovered line) |
1 | | // modarith.h - originally 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 | | #if CRYPTOPP_MSC_VERSION |
18 | | # pragma warning(push) |
19 | | # pragma warning(disable: 4231 4275) |
20 | | #endif |
21 | | |
22 | | NAMESPACE_BEGIN(CryptoPP) |
23 | | |
24 | | CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<Integer>; |
25 | | CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<Integer>; |
26 | | CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<Integer>; |
27 | | |
28 | | /// \brief Ring of congruence classes modulo n |
29 | | /// \details This implementation represents each congruence class as |
30 | | /// the smallest non-negative integer in that class. |
31 | | /// \details <tt>const Element&</tt> returned by member functions are |
32 | | /// references to internal data members. Since each object may have |
33 | | /// only one such data member for holding results, you should use the |
34 | | /// class like this: |
35 | | /// <pre> abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre> |
36 | | /// The following code will produce <i>incorrect</i> results: |
37 | | /// <pre> abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre> |
38 | | /// \details If a ModularArithmetic() is copied or assigned the modulus |
39 | | /// is copied, but not the internal data members. The internal data |
40 | | /// members are undefined after copy or assignment. |
41 | | /// \sa <A HREF="https://cryptopp.com/wiki/Integer">Integer</A> on the |
42 | | /// Crypto++ wiki. |
43 | | class CRYPTOPP_DLL ModularArithmetic : public AbstractRing<Integer> |
44 | | { |
45 | | public: |
46 | | |
47 | | typedef int RandomizationParameter; |
48 | | typedef Integer Element; |
49 | | |
50 | 114k | virtual ~ModularArithmetic() {} |
51 | | |
52 | | /// \brief Construct a ModularArithmetic |
53 | | /// \param modulus congruence class modulus |
54 | | ModularArithmetic(const Integer &modulus = Integer::One()) |
55 | 59.7k | : m_modulus(modulus), m_result(static_cast<word>(0), modulus.reg.size()) {} |
56 | | |
57 | | /// \brief Copy construct a ModularArithmetic |
58 | | /// \param ma other ModularArithmetic |
59 | | ModularArithmetic(const ModularArithmetic &ma) |
60 | 54.3k | : AbstractRing<Integer>(ma), m_modulus(ma.m_modulus), m_result(static_cast<word>(0), m_modulus.reg.size()) {} |
61 | | |
62 | | /// \brief Assign a ModularArithmetic |
63 | | /// \param ma other ModularArithmetic |
64 | 0 | ModularArithmetic& operator=(const ModularArithmetic &ma) { |
65 | 0 | if (this != &ma) |
66 | 0 | { |
67 | 0 | m_modulus = ma.m_modulus; |
68 | 0 | m_result = Integer(static_cast<word>(0), m_modulus.reg.size()); |
69 | 0 | } |
70 | 0 | return *this; |
71 | 0 | } |
72 | | |
73 | | /// \brief Construct a ModularArithmetic |
74 | | /// \param bt BER encoded ModularArithmetic |
75 | | ModularArithmetic(BufferedTransformation &bt); // construct from BER encoded parameters |
76 | | |
77 | | /// \brief Clone a ModularArithmetic |
78 | | /// \return pointer to a new ModularArithmetic |
79 | | /// \details Clone effectively copy constructs a new ModularArithmetic. The caller is |
80 | | /// responsible for deleting the pointer returned from this method. |
81 | 54.3k | virtual ModularArithmetic * Clone() const {return new ModularArithmetic(*this);} |
82 | | |
83 | | /// \brief Encodes in DER format |
84 | | /// \param bt BufferedTransformation object |
85 | | void DEREncode(BufferedTransformation &bt) const; |
86 | | |
87 | | /// \brief Encodes element in DER format |
88 | | /// \param out BufferedTransformation object |
89 | | /// \param a Element to encode |
90 | | void DEREncodeElement(BufferedTransformation &out, const Element &a) const; |
91 | | |
92 | | /// \brief Decodes element in DER format |
93 | | /// \param in BufferedTransformation object |
94 | | /// \param a Element to decode |
95 | | void BERDecodeElement(BufferedTransformation &in, Element &a) const; |
96 | | |
97 | | /// \brief Retrieves the modulus |
98 | | /// \return the modulus |
99 | 27.1k | const Integer& GetModulus() const {return m_modulus;} |
100 | | |
101 | | /// \brief Sets the modulus |
102 | | /// \param newModulus the new modulus |
103 | | void SetModulus(const Integer &newModulus) |
104 | 0 | {m_modulus = newModulus; m_result.reg.resize(m_modulus.reg.size());} |
105 | | |
106 | | /// \brief Retrieves the representation |
107 | | /// \return true if the if the modulus is in Montgomery form for multiplication, false otherwise |
108 | 27.1k | virtual bool IsMontgomeryRepresentation() const {return false;} |
109 | | |
110 | | /// \brief Reduces an element in the congruence class |
111 | | /// \param a element to convert |
112 | | /// \return the reduced element |
113 | | /// \details ConvertIn is useful for derived classes, like MontgomeryRepresentation, which |
114 | | /// must convert between representations. |
115 | | virtual Integer ConvertIn(const Integer &a) const |
116 | 0 | {return a%m_modulus;} |
117 | | |
118 | | /// \brief Reduces an element in the congruence class |
119 | | /// \param a element to convert |
120 | | /// \return the reduced element |
121 | | /// \details ConvertOut is useful for derived classes, like MontgomeryRepresentation, which |
122 | | /// must convert between representations. |
123 | | virtual Integer ConvertOut(const Integer &a) const |
124 | 0 | {return a;} |
125 | | |
126 | | /// \brief Divides an element by 2 |
127 | | /// \param a element to convert |
128 | | const Integer& Half(const Integer &a) const; |
129 | | |
130 | | /// \brief Compare two elements for equality |
131 | | /// \param a first element |
132 | | /// \param b second element |
133 | | /// \return true if the elements are equal, false otherwise |
134 | | /// \details Equal() tests the elements for equality using <tt>a==b</tt> |
135 | | bool Equal(const Integer &a, const Integer &b) const |
136 | 0 | {return a==b;} |
137 | | |
138 | | /// \brief Provides the Identity element |
139 | | /// \return the Identity element |
140 | | const Integer& Identity() const |
141 | 0 | {return Integer::Zero();} |
142 | | |
143 | | /// \brief Adds elements in the ring |
144 | | /// \param a first element |
145 | | /// \param b second element |
146 | | /// \return the sum of <tt>a</tt> and <tt>b</tt> |
147 | | const Integer& Add(const Integer &a, const Integer &b) const; |
148 | | |
149 | | /// \brief TODO |
150 | | /// \param a first element |
151 | | /// \param b second element |
152 | | /// \return TODO |
153 | | Integer& Accumulate(Integer &a, const Integer &b) const; |
154 | | |
155 | | /// \brief Inverts the element in the ring |
156 | | /// \param a first element |
157 | | /// \return the inverse of the element |
158 | | const Integer& Inverse(const Integer &a) const; |
159 | | |
160 | | /// \brief Subtracts elements in the ring |
161 | | /// \param a first element |
162 | | /// \param b second element |
163 | | /// \return the difference of <tt>a</tt> and <tt>b</tt>. The element <tt>a</tt> must provide a Subtract member function. |
164 | | const Integer& Subtract(const Integer &a, const Integer &b) const; |
165 | | |
166 | | /// \brief TODO |
167 | | /// \param a first element |
168 | | /// \param b second element |
169 | | /// \return TODO |
170 | | Integer& Reduce(Integer &a, const Integer &b) const; |
171 | | |
172 | | /// \brief Doubles an element in the ring |
173 | | /// \param a the element |
174 | | /// \return the element doubled |
175 | | /// \details Double returns <tt>Add(a, a)</tt>. The element <tt>a</tt> must provide an Add member function. |
176 | | const Integer& Double(const Integer &a) const |
177 | 0 | {return Add(a, a);} |
178 | | |
179 | | /// \brief Retrieves the multiplicative identity |
180 | | /// \return the multiplicative identity |
181 | | /// \details the base class implementations returns 1. |
182 | | const Integer& MultiplicativeIdentity() const |
183 | 2.01k | {return Integer::One();} |
184 | | |
185 | | /// \brief Multiplies elements in the ring |
186 | | /// \param a the multiplicand |
187 | | /// \param b the multiplier |
188 | | /// \return the product of a and b |
189 | | /// \details Multiply returns <tt>a*b\%n</tt>. |
190 | | const Integer& Multiply(const Integer &a, const Integer &b) const |
191 | 202k | {return m_result1 = a*b%m_modulus;} |
192 | | |
193 | | /// \brief Square an element in the ring |
194 | | /// \param a the element |
195 | | /// \return the element squared |
196 | | /// \details Square returns <tt>a*a\%n</tt>. The element <tt>a</tt> must provide a Square member function. |
197 | | const Integer& Square(const Integer &a) const |
198 | 1.00M | {return m_result1 = a.Squared()%m_modulus;} |
199 | | |
200 | | /// \brief Determines whether an element is a unit in the ring |
201 | | /// \param a the element |
202 | | /// \return true if the element is a unit after reduction, false otherwise. |
203 | | bool IsUnit(const Integer &a) const |
204 | 0 | {return Integer::Gcd(a, m_modulus).IsUnit();} |
205 | | |
206 | | /// \brief Calculate the multiplicative inverse of an element in the ring |
207 | | /// \param a the element |
208 | | /// \details MultiplicativeInverse returns <tt>a<sup>-1</sup>\%n</tt>. The element <tt>a</tt> must |
209 | | /// provide a InverseMod member function. |
210 | | const Integer& MultiplicativeInverse(const Integer &a) const |
211 | 0 | {return m_result1 = a.InverseMod(m_modulus);} |
212 | | |
213 | | /// \brief Divides elements in the ring |
214 | | /// \param a the dividend |
215 | | /// \param b the divisor |
216 | | /// \return the quotient |
217 | | /// \details Divide returns <tt>a*b<sup>-1</sup>\%n</tt>. |
218 | | const Integer& Divide(const Integer &a, const Integer &b) const |
219 | 0 | {return Multiply(a, MultiplicativeInverse(b));} |
220 | | |
221 | | /// \brief TODO |
222 | | /// \param x first element |
223 | | /// \param e1 first exponent |
224 | | /// \param y second element |
225 | | /// \param e2 second exponent |
226 | | /// \return TODO |
227 | | Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const; |
228 | | |
229 | | /// \brief Exponentiates a base to multiple exponents in the ring |
230 | | /// \param results an array of Elements |
231 | | /// \param base the base to raise to the exponents |
232 | | /// \param exponents an array of exponents |
233 | | /// \param exponentsCount the number of exponents in the array |
234 | | /// \details SimultaneousExponentiate() raises the base to each exponent in the exponents array and stores the |
235 | | /// result at the respective position in the results array. |
236 | | /// \details SimultaneousExponentiate() must be implemented in a derived class. |
237 | | /// \pre <tt>COUNTOF(results) == exponentsCount</tt> |
238 | | /// \pre <tt>COUNTOF(exponents) == exponentsCount</tt> |
239 | | void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const; |
240 | | |
241 | | /// \brief Provides the maximum bit size of an element in the ring |
242 | | /// \return maximum bit size of an element |
243 | | unsigned int MaxElementBitLength() const |
244 | 0 | {return (m_modulus-1).BitCount();} |
245 | | |
246 | | /// \brief Provides the maximum byte size of an element in the ring |
247 | | /// \return maximum byte size of an element |
248 | | unsigned int MaxElementByteLength() const |
249 | 54.3k | {return (m_modulus-1).ByteCount();} |
250 | | |
251 | | /// \brief Provides a random element in the ring |
252 | | /// \param rng RandomNumberGenerator used to generate material |
253 | | /// \param ignore_for_now unused |
254 | | /// \return a random element that is uniformly distributed |
255 | | /// \details RandomElement constructs a new element in the range <tt>[0,n-1]</tt>, inclusive. |
256 | | /// The element's class must provide a constructor with the signature <tt>Element(RandomNumberGenerator rng, |
257 | | /// Element min, Element max)</tt>. |
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 | 0 | { |
261 | 0 | CRYPTOPP_UNUSED(ignore_for_now); |
262 | 0 | return Element(rng, Integer::Zero(), m_modulus - Integer::One()) ; |
263 | 0 | } |
264 | | |
265 | | /// \brief Compares two ModularArithmetic for equality |
266 | | /// \param rhs other ModularArithmetic |
267 | | /// \return true if this is equal to the other, false otherwise |
268 | | /// \details The operator tests for equality using <tt>this.m_modulus == rhs.m_modulus</tt>. |
269 | | bool operator==(const ModularArithmetic &rhs) const |
270 | 0 | {return m_modulus == rhs.m_modulus;} |
271 | | |
272 | | static const RandomizationParameter DefaultRandomizationParameter; |
273 | | |
274 | | private: |
275 | | // TODO: Clang on OS X needs a real operator=. |
276 | | // Squash warning on missing assignment operator. |
277 | | // ModularArithmetic& operator=(const ModularArithmetic &ma); |
278 | | |
279 | | protected: |
280 | | Integer m_modulus; |
281 | | mutable Integer m_result, m_result1; |
282 | | }; |
283 | | |
284 | | // const ModularArithmetic::RandomizationParameter ModularArithmetic::DefaultRandomizationParameter = 0 ; |
285 | | |
286 | | /// \brief Performs modular arithmetic in Montgomery representation for increased speed |
287 | | /// \details The Montgomery representation represents each congruence class <tt>[a]</tt> as |
288 | | /// <tt>a*r\%n</tt>, where <tt>r</tt> is a convenient power of 2. |
289 | | /// \details <tt>const Element&</tt> returned by member functions are references to |
290 | | /// internal data members. Since each object may have only one such data member for holding |
291 | | /// results, the following code will produce incorrect results: |
292 | | /// <pre> abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre> |
293 | | /// But this should be fine: |
294 | | /// <pre> abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre> |
295 | | class CRYPTOPP_DLL MontgomeryRepresentation : public ModularArithmetic |
296 | | { |
297 | | public: |
298 | 28.8k | virtual ~MontgomeryRepresentation() {} |
299 | | |
300 | | /// \brief Construct a MontgomeryRepresentation |
301 | | /// \param modulus congruence class modulus |
302 | | /// \note The modulus must be odd. |
303 | | MontgomeryRepresentation(const Integer &modulus); |
304 | | |
305 | | /// \brief Clone a MontgomeryRepresentation |
306 | | /// \return pointer to a new MontgomeryRepresentation |
307 | | /// \details Clone effectively copy constructs a new MontgomeryRepresentation. The caller is |
308 | | /// responsible for deleting the pointer returned from this method. |
309 | 0 | virtual ModularArithmetic * Clone() const {return new MontgomeryRepresentation(*this);} |
310 | | |
311 | 0 | bool IsMontgomeryRepresentation() const {return true;} |
312 | | |
313 | | Integer ConvertIn(const Integer &a) const |
314 | 110k | {return (a<<(WORD_BITS*m_modulus.reg.size()))%m_modulus;} |
315 | | |
316 | | Integer ConvertOut(const Integer &a) const; |
317 | | |
318 | | const Integer& MultiplicativeIdentity() const |
319 | 1.68k | {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 | 0 | {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 | 1.68k | {AbstractRing<Integer>::SimultaneousExponentiate(results, base, exponents, exponentsCount);} |
332 | | |
333 | | private: |
334 | | Integer m_u; |
335 | | mutable IntegerSecBlock m_workspace; |
336 | | }; |
337 | | |
338 | | NAMESPACE_END |
339 | | |
340 | | #if CRYPTOPP_MSC_VERSION |
341 | | # pragma warning(pop) |
342 | | #endif |
343 | | |
344 | | #endif |