EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:55:05
0001 // modarith.h - originally written and placed in the public domain by Wei Dai 0002 0003 /// \file modarith.h 0004 /// \brief Class file for performing modular arithmetic. 0005 0006 #ifndef CRYPTOPP_MODARITH_H 0007 #define CRYPTOPP_MODARITH_H 0008 0009 // implementations are in integer.cpp 0010 0011 #include "cryptlib.h" 0012 #include "integer.h" 0013 #include "algebra.h" 0014 #include "secblock.h" 0015 #include "misc.h" 0016 0017 #if CRYPTOPP_MSC_VERSION 0018 # pragma warning(push) 0019 # pragma warning(disable: 4231 4275) 0020 #endif 0021 0022 NAMESPACE_BEGIN(CryptoPP) 0023 0024 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<Integer>; 0025 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<Integer>; 0026 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<Integer>; 0027 0028 /// \brief Ring of congruence classes modulo n 0029 /// \details This implementation represents each congruence class as 0030 /// the smallest non-negative integer in that class. 0031 /// \details <tt>const Element&</tt> returned by member functions are 0032 /// references to internal data members. Since each object may have 0033 /// only one such data member for holding results, you should use the 0034 /// class like this: 0035 /// <pre> abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre> 0036 /// The following code will produce <i>incorrect</i> results: 0037 /// <pre> abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre> 0038 /// \details If a ModularArithmetic() is copied or assigned the modulus 0039 /// is copied, but not the internal data members. The internal data 0040 /// members are undefined after copy or assignment. 0041 /// \sa <A HREF="https://cryptopp.com/wiki/Integer">Integer</A> on the 0042 /// Crypto++ wiki. 0043 class CRYPTOPP_DLL ModularArithmetic : public AbstractRing<Integer> 0044 { 0045 public: 0046 0047 typedef int RandomizationParameter; 0048 typedef Integer Element; 0049 0050 virtual ~ModularArithmetic() {} 0051 0052 /// \brief Construct a ModularArithmetic 0053 /// \param modulus congruence class modulus 0054 ModularArithmetic(const Integer &modulus = Integer::One()) 0055 : m_modulus(modulus), m_result(static_cast<word>(0), modulus.reg.size()) {} 0056 0057 /// \brief Copy construct a ModularArithmetic 0058 /// \param ma other ModularArithmetic 0059 ModularArithmetic(const ModularArithmetic &ma) 0060 : AbstractRing<Integer>(ma), m_modulus(ma.m_modulus), m_result(static_cast<word>(0), m_modulus.reg.size()) {} 0061 0062 /// \brief Assign a ModularArithmetic 0063 /// \param ma other ModularArithmetic 0064 ModularArithmetic& operator=(const ModularArithmetic &ma) { 0065 if (this != &ma) 0066 { 0067 m_modulus = ma.m_modulus; 0068 m_result = Integer(static_cast<word>(0), m_modulus.reg.size()); 0069 } 0070 return *this; 0071 } 0072 0073 /// \brief Construct a ModularArithmetic 0074 /// \param bt BER encoded ModularArithmetic 0075 ModularArithmetic(BufferedTransformation &bt); // construct from BER encoded parameters 0076 0077 /// \brief Clone a ModularArithmetic 0078 /// \return pointer to a new ModularArithmetic 0079 /// \details Clone effectively copy constructs a new ModularArithmetic. The caller is 0080 /// responsible for deleting the pointer returned from this method. 0081 virtual ModularArithmetic * Clone() const {return new ModularArithmetic(*this);} 0082 0083 /// \brief Encodes in DER format 0084 /// \param bt BufferedTransformation object 0085 void DEREncode(BufferedTransformation &bt) const; 0086 0087 /// \brief Encodes element in DER format 0088 /// \param out BufferedTransformation object 0089 /// \param a Element to encode 0090 void DEREncodeElement(BufferedTransformation &out, const Element &a) const; 0091 0092 /// \brief Decodes element in DER format 0093 /// \param in BufferedTransformation object 0094 /// \param a Element to decode 0095 void BERDecodeElement(BufferedTransformation &in, Element &a) const; 0096 0097 /// \brief Retrieves the modulus 0098 /// \return the modulus 0099 const Integer& GetModulus() const {return m_modulus;} 0100 0101 /// \brief Sets the modulus 0102 /// \param newModulus the new modulus 0103 void SetModulus(const Integer &newModulus) 0104 {m_modulus = newModulus; m_result.reg.resize(m_modulus.reg.size());} 0105 0106 /// \brief Retrieves the representation 0107 /// \return true if the if the modulus is in Montgomery form for multiplication, false otherwise 0108 virtual bool IsMontgomeryRepresentation() const {return false;} 0109 0110 /// \brief Reduces an element in the congruence class 0111 /// \param a element to convert 0112 /// \return the reduced element 0113 /// \details ConvertIn is useful for derived classes, like MontgomeryRepresentation, which 0114 /// must convert between representations. 0115 virtual Integer ConvertIn(const Integer &a) const 0116 {return a%m_modulus;} 0117 0118 /// \brief Reduces an element in the congruence class 0119 /// \param a element to convert 0120 /// \return the reduced element 0121 /// \details ConvertOut is useful for derived classes, like MontgomeryRepresentation, which 0122 /// must convert between representations. 0123 virtual Integer ConvertOut(const Integer &a) const 0124 {return a;} 0125 0126 /// \brief Divides an element by 2 0127 /// \param a element to convert 0128 const Integer& Half(const Integer &a) const; 0129 0130 /// \brief Compare two elements for equality 0131 /// \param a first element 0132 /// \param b second element 0133 /// \return true if the elements are equal, false otherwise 0134 /// \details Equal() tests the elements for equality using <tt>a==b</tt> 0135 bool Equal(const Integer &a, const Integer &b) const 0136 {return a==b;} 0137 0138 /// \brief Provides the Identity element 0139 /// \return the Identity element 0140 const Integer& Identity() const 0141 {return Integer::Zero();} 0142 0143 /// \brief Adds elements in the ring 0144 /// \param a first element 0145 /// \param b second element 0146 /// \return the sum of <tt>a</tt> and <tt>b</tt> 0147 const Integer& Add(const Integer &a, const Integer &b) const; 0148 0149 /// \brief TODO 0150 /// \param a first element 0151 /// \param b second element 0152 /// \return TODO 0153 Integer& Accumulate(Integer &a, const Integer &b) const; 0154 0155 /// \brief Inverts the element in the ring 0156 /// \param a first element 0157 /// \return the inverse of the element 0158 const Integer& Inverse(const Integer &a) const; 0159 0160 /// \brief Subtracts elements in the ring 0161 /// \param a first element 0162 /// \param b second element 0163 /// \return the difference of <tt>a</tt> and <tt>b</tt>. The element <tt>a</tt> must provide a Subtract member function. 0164 const Integer& Subtract(const Integer &a, const Integer &b) const; 0165 0166 /// \brief TODO 0167 /// \param a first element 0168 /// \param b second element 0169 /// \return TODO 0170 Integer& Reduce(Integer &a, const Integer &b) const; 0171 0172 /// \brief Doubles an element in the ring 0173 /// \param a the element 0174 /// \return the element doubled 0175 /// \details Double returns <tt>Add(a, a)</tt>. The element <tt>a</tt> must provide an Add member function. 0176 const Integer& Double(const Integer &a) const 0177 {return Add(a, a);} 0178 0179 /// \brief Retrieves the multiplicative identity 0180 /// \return the multiplicative identity 0181 /// \details the base class implementations returns 1. 0182 const Integer& MultiplicativeIdentity() const 0183 {return Integer::One();} 0184 0185 /// \brief Multiplies elements in the ring 0186 /// \param a the multiplicand 0187 /// \param b the multiplier 0188 /// \return the product of a and b 0189 /// \details Multiply returns <tt>a*b\%n</tt>. 0190 const Integer& Multiply(const Integer &a, const Integer &b) const 0191 {return m_result1 = a*b%m_modulus;} 0192 0193 /// \brief Square an element in the ring 0194 /// \param a the element 0195 /// \return the element squared 0196 /// \details Square returns <tt>a*a\%n</tt>. The element <tt>a</tt> must provide a Square member function. 0197 const Integer& Square(const Integer &a) const 0198 {return m_result1 = a.Squared()%m_modulus;} 0199 0200 /// \brief Determines whether an element is a unit in the ring 0201 /// \param a the element 0202 /// \return true if the element is a unit after reduction, false otherwise. 0203 bool IsUnit(const Integer &a) const 0204 {return Integer::Gcd(a, m_modulus).IsUnit();} 0205 0206 /// \brief Calculate the multiplicative inverse of an element in the ring 0207 /// \param a the element 0208 /// \details MultiplicativeInverse returns <tt>a<sup>-1</sup>\%n</tt>. The element <tt>a</tt> must 0209 /// provide a InverseMod member function. 0210 const Integer& MultiplicativeInverse(const Integer &a) const 0211 {return m_result1 = a.InverseMod(m_modulus);} 0212 0213 /// \brief Divides elements in the ring 0214 /// \param a the dividend 0215 /// \param b the divisor 0216 /// \return the quotient 0217 /// \details Divide returns <tt>a*b<sup>-1</sup>\%n</tt>. 0218 const Integer& Divide(const Integer &a, const Integer &b) const 0219 {return Multiply(a, MultiplicativeInverse(b));} 0220 0221 /// \brief TODO 0222 /// \param x first element 0223 /// \param e1 first exponent 0224 /// \param y second element 0225 /// \param e2 second exponent 0226 /// \return TODO 0227 Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const; 0228 0229 /// \brief Exponentiates a base to multiple exponents in the ring 0230 /// \param results an array of Elements 0231 /// \param base the base to raise to the exponents 0232 /// \param exponents an array of exponents 0233 /// \param exponentsCount the number of exponents in the array 0234 /// \details SimultaneousExponentiate() raises the base to each exponent in the exponents array and stores the 0235 /// result at the respective position in the results array. 0236 /// \details SimultaneousExponentiate() must be implemented in a derived class. 0237 /// \pre <tt>COUNTOF(results) == exponentsCount</tt> 0238 /// \pre <tt>COUNTOF(exponents) == exponentsCount</tt> 0239 void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const; 0240 0241 /// \brief Provides the maximum bit size of an element in the ring 0242 /// \return maximum bit size of an element 0243 unsigned int MaxElementBitLength() const 0244 {return (m_modulus-1).BitCount();} 0245 0246 /// \brief Provides the maximum byte size of an element in the ring 0247 /// \return maximum byte size of an element 0248 unsigned int MaxElementByteLength() const 0249 {return (m_modulus-1).ByteCount();} 0250 0251 /// \brief Provides a random element in the ring 0252 /// \param rng RandomNumberGenerator used to generate material 0253 /// \param ignore_for_now unused 0254 /// \return a random element that is uniformly distributed 0255 /// \details RandomElement constructs a new element in the range <tt>[0,n-1]</tt>, inclusive. 0256 /// The element's class must provide a constructor with the signature <tt>Element(RandomNumberGenerator rng, 0257 /// Element min, Element max)</tt>. 0258 Element RandomElement(RandomNumberGenerator &rng, const RandomizationParameter &ignore_for_now = 0) const 0259 // left RandomizationParameter arg as ref in case RandomizationParameter becomes a more complicated struct 0260 { 0261 CRYPTOPP_UNUSED(ignore_for_now); 0262 return Element(rng, Integer::Zero(), m_modulus - Integer::One()) ; 0263 } 0264 0265 /// \brief Compares two ModularArithmetic for equality 0266 /// \param rhs other ModularArithmetic 0267 /// \return true if this is equal to the other, false otherwise 0268 /// \details The operator tests for equality using <tt>this.m_modulus == rhs.m_modulus</tt>. 0269 bool operator==(const ModularArithmetic &rhs) const 0270 {return m_modulus == rhs.m_modulus;} 0271 0272 static const RandomizationParameter DefaultRandomizationParameter; 0273 0274 private: 0275 // TODO: Clang on OS X needs a real operator=. 0276 // Squash warning on missing assignment operator. 0277 // ModularArithmetic& operator=(const ModularArithmetic &ma); 0278 0279 protected: 0280 Integer m_modulus; 0281 mutable Integer m_result, m_result1; 0282 }; 0283 0284 // const ModularArithmetic::RandomizationParameter ModularArithmetic::DefaultRandomizationParameter = 0 ; 0285 0286 /// \brief Performs modular arithmetic in Montgomery representation for increased speed 0287 /// \details The Montgomery representation represents each congruence class <tt>[a]</tt> as 0288 /// <tt>a*r\%n</tt>, where <tt>r</tt> is a convenient power of 2. 0289 /// \details <tt>const Element&</tt> returned by member functions are references to 0290 /// internal data members. Since each object may have only one such data member for holding 0291 /// results, the following code will produce incorrect results: 0292 /// <pre> abcd = group.Add(group.Add(a,b), group.Add(c,d));</pre> 0293 /// But this should be fine: 0294 /// <pre> abcd = group.Add(a, group.Add(b, group.Add(c,d));</pre> 0295 class CRYPTOPP_DLL MontgomeryRepresentation : public ModularArithmetic 0296 { 0297 public: 0298 virtual ~MontgomeryRepresentation() {} 0299 0300 /// \brief Construct a MontgomeryRepresentation 0301 /// \param modulus congruence class modulus 0302 /// \note The modulus must be odd. 0303 MontgomeryRepresentation(const Integer &modulus); 0304 0305 /// \brief Clone a MontgomeryRepresentation 0306 /// \return pointer to a new MontgomeryRepresentation 0307 /// \details Clone effectively copy constructs a new MontgomeryRepresentation. The caller is 0308 /// responsible for deleting the pointer returned from this method. 0309 virtual ModularArithmetic * Clone() const {return new MontgomeryRepresentation(*this);} 0310 0311 bool IsMontgomeryRepresentation() const {return true;} 0312 0313 Integer ConvertIn(const Integer &a) const 0314 {return (a<<(WORD_BITS*m_modulus.reg.size()))%m_modulus;} 0315 0316 Integer ConvertOut(const Integer &a) const; 0317 0318 const Integer& MultiplicativeIdentity() const 0319 {return m_result1 = Integer::Power2(WORD_BITS*m_modulus.reg.size())%m_modulus;} 0320 0321 const Integer& Multiply(const Integer &a, const Integer &b) const; 0322 0323 const Integer& Square(const Integer &a) const; 0324 0325 const Integer& MultiplicativeInverse(const Integer &a) const; 0326 0327 Integer CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const 0328 {return AbstractRing<Integer>::CascadeExponentiate(x, e1, y, e2);} 0329 0330 void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const 0331 {AbstractRing<Integer>::SimultaneousExponentiate(results, base, exponents, exponentsCount);} 0332 0333 private: 0334 Integer m_u; 0335 mutable IntegerSecBlock m_workspace; 0336 }; 0337 0338 NAMESPACE_END 0339 0340 #if CRYPTOPP_MSC_VERSION 0341 # pragma warning(pop) 0342 #endif 0343 0344 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|