1 /*
2    Copyright (C) 2000-2007 MySQL AB
3    Use is subject to license terms
4 
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation; version 2 of the License.
8 
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13 
14    You should have received a copy of the GNU General Public License
15    along with this program; see the file COPYING. If not, write to the
16    Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
17    MA  02110-1335  USA.
18 */
19 
20 
21 /* based on Wei Dai's modarith.h from CryptoPP */
22 
23 
24 #ifndef TAO_CRYPT_MODARITH_HPP
25 #define TAO_CRYPT_MODARITH_HPP
26 
27 #include "misc.hpp"
28 #include "algebra.hpp"
29 
30 namespace TaoCrypt {
31 
32 
33 // ModularArithmetic
34 class ModularArithmetic : public AbstractRing
35 {
36 public:
37 
38     typedef int RandomizationParameter;
39     typedef Integer Element;
40 
41     ModularArithmetic(const Integer &modulus = Integer::One())
42         : modulus(modulus), result((word)0, modulus.reg_.size()) {}
43 
44     ModularArithmetic(const ModularArithmetic &ma)
45         : AbstractRing(),
46         modulus(ma.modulus), result((word)0, modulus.reg_.size()) {}
47 
48     const Integer& GetModulus() const {return modulus;}
49     void SetModulus(const Integer &newModulus)
50     {
51         modulus = newModulus;
52         result.reg_.resize(modulus.reg_.size());
53     }
54 
55     virtual bool IsMontgomeryRepresentation() const {return false;}
56 
57     virtual Integer ConvertIn(const Integer &a) const
58         {return a%modulus;}
59 
60     virtual Integer ConvertOut(const Integer &a) const
61         {return a;}
62 
63     const Integer& Half(const Integer &a) const;
64 
65     bool Equal(const Integer &a, const Integer &b) const
66         {return a==b;}
67 
68     const Integer& Identity() const
69         {return Integer::Zero();}
70 
71     const Integer& Add(const Integer &a, const Integer &b) const;
72 
73     Integer& Accumulate(Integer &a, const Integer &b) const;
74 
75     const Integer& Inverse(const Integer &a) const;
76 
77     const Integer& Subtract(const Integer &a, const Integer &b) const;
78 
79     Integer& Reduce(Integer &a, const Integer &b) const;
80 
81     const Integer& Double(const Integer &a) const
82         {return Add(a, a);}
83 
84     const Integer& MultiplicativeIdentity() const
85         {return Integer::One();}
86 
87     const Integer& Multiply(const Integer &a, const Integer &b) const
88         {return result1 = a*b%modulus;}
89 
90     const Integer& Square(const Integer &a) const
91         {return result1 = a.Squared()%modulus;}
92 
93     bool IsUnit(const Integer &a) const
94         {return Integer::Gcd(a, modulus).IsUnit();}
95 
96     const Integer& MultiplicativeInverse(const Integer &a) const
97         {return result1 = a.InverseMod(modulus);}
98 
99     const Integer& Divide(const Integer &a, const Integer &b) const
100         {return Multiply(a, MultiplicativeInverse(b));}
101 
102     Integer CascadeExponentiate(const Integer &x, const Integer &e1,
103                                 const Integer &y, const Integer &e2) const;
104 
105     void SimultaneousExponentiate(Element *results, const Element &base,
106                   const Integer *exponents, unsigned int exponentsCount) const;
107 
108     unsigned int MaxElementBitLength() const
109         {return (modulus-1).BitCount();}
110 
111     unsigned int MaxElementByteLength() const
112         {return (modulus-1).ByteCount();}
113 
114 
115     static const RandomizationParameter DefaultRandomizationParameter;
116 
117 protected:
118     Integer modulus;
119     mutable Integer result, result1;
120 
121 };
122 
123 
124 
125 //! do modular arithmetics in Montgomery representation for increased speed
126 class MontgomeryRepresentation : public ModularArithmetic
127 {
128 public:
129     MontgomeryRepresentation(const Integer &modulus);	// modulus must be odd
130 
131     bool IsMontgomeryRepresentation() const {return true;}
132 
133     Integer ConvertIn(const Integer &a) const
134         {return (a<<(WORD_BITS*modulus.reg_.size()))%modulus;}
135 
136     Integer ConvertOut(const Integer &a) const;
137 
138     const Integer& MultiplicativeIdentity() const
139      {return result1 = Integer::Power2(WORD_BITS*modulus.reg_.size())%modulus;}
140 
141     const Integer& Multiply(const Integer &a, const Integer &b) const;
142 
143     const Integer& Square(const Integer &a) const;
144 
145     const Integer& MultiplicativeInverse(const Integer &a) const;
146 
147     Integer CascadeExponentiate(const Integer &x, const Integer &e1,
148                                 const Integer &y, const Integer &e2) const
149         {return AbstractRing::CascadeExponentiate(x, e1, y, e2);}
150 
151     void SimultaneousExponentiate(Element *results, const Element &base,
152             const Integer *exponents, unsigned int exponentsCount) const
153         {AbstractRing::SimultaneousExponentiate(results, base,
154                                                 exponents, exponentsCount);}
155 
156 private:
157     Integer u;
158     mutable AlignedWordBlock workspace;
159 };
160 
161 
162 
163 
164 } // namespace
165 
166 #endif // TAO_CRYPT_MODARITH_HPP
167