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 /* based on Wei Dai's algebra.h from CryptoPP */
21 
22 #ifndef TAO_CRYPT_ALGEBRA_HPP
23 #define TAO_CRYPT_ALGEBRA_HPP
24 
25 #include "integer.hpp"
26 
27 namespace TaoCrypt {
28 
29 
30 // "const Element&" returned by member functions are references
31 // to internal data members. Since each object may have only
32 // one such data member for holding results, the following code
33 // will produce incorrect results:
34 // abcd = group.Add(group.Add(a,b), group.Add(c,d));
35 // But this should be fine:
36 // abcd = group.Add(a, group.Add(b, group.Add(c,d));
37 
38 // Abstract Group
39 class TAOCRYPT_NO_VTABLE AbstractGroup : public virtual_base
40 {
41 public:
42     typedef Integer Element;
43 
~AbstractGroup()44     virtual ~AbstractGroup() {}
45 
46     virtual bool Equal(const Element &a, const Element &b) const =0;
47     virtual const Element& Identity() const =0;
48     virtual const Element& Add(const Element &a, const Element &b) const =0;
49     virtual const Element& Inverse(const Element &a) const =0;
InversionIsFast() const50     virtual bool InversionIsFast() const {return false;}
51 
52     virtual const Element& Double(const Element &a) const;
53     virtual const Element& Subtract(const Element &a, const Element &b) const;
54     virtual Element& Accumulate(Element &a, const Element &b) const;
55     virtual Element& Reduce(Element &a, const Element &b) const;
56 
57     virtual Element ScalarMultiply(const Element &a, const Integer &e) const;
58     virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1,
59                                     const Element &y, const Integer &e2) const;
60 
61     virtual void SimultaneousMultiply(Element *results, const Element &base,
62                   const Integer *exponents, unsigned int exponentsCount) const;
63 };
64 
65 // Abstract Ring
66 class TAOCRYPT_NO_VTABLE AbstractRing : public AbstractGroup
67 {
68 public:
69     typedef Integer Element;
70 
AbstractRing()71     AbstractRing() : AbstractGroup() {m_mg.m_pRing = this;}
AbstractRing(const AbstractRing & source)72     AbstractRing(const AbstractRing &source) : AbstractGroup()
73                                                 {m_mg.m_pRing = this;}
operator =(const AbstractRing & source)74     AbstractRing& operator=(const AbstractRing &source) {return *this;}
75 
76     virtual bool IsUnit(const Element &a) const =0;
77     virtual const Element& MultiplicativeIdentity() const =0;
78     virtual const Element& Multiply(const Element&, const Element&) const =0;
79     virtual const Element& MultiplicativeInverse(const Element &a) const =0;
80 
81     virtual const Element& Square(const Element &a) const;
82     virtual const Element& Divide(const Element &a, const Element &b) const;
83 
84     virtual Element Exponentiate(const Element &a, const Integer &e) const;
85     virtual Element CascadeExponentiate(const Element &x, const Integer &e1,
86                                     const Element &y, const Integer &e2) const;
87 
88     virtual void SimultaneousExponentiate(Element *results, const Element&,
89                   const Integer *exponents, unsigned int exponentsCount) const;
90 
MultiplicativeGroup() const91     virtual const AbstractGroup& MultiplicativeGroup() const
92         {return m_mg;}
93 
94 private:
95     class MultiplicativeGroupT : public AbstractGroup
96     {
97     public:
GetRing() const98         const AbstractRing& GetRing() const
99             {return *m_pRing;}
100 
Equal(const Element & a,const Element & b) const101         bool Equal(const Element &a, const Element &b) const
102             {return GetRing().Equal(a, b);}
103 
Identity() const104         const Element& Identity() const
105             {return GetRing().MultiplicativeIdentity();}
106 
Add(const Element & a,const Element & b) const107         const Element& Add(const Element &a, const Element &b) const
108             {return GetRing().Multiply(a, b);}
109 
Accumulate(Element & a,const Element & b) const110         Element& Accumulate(Element &a, const Element &b) const
111             {return a = GetRing().Multiply(a, b);}
112 
Inverse(const Element & a) const113         const Element& Inverse(const Element &a) const
114             {return GetRing().MultiplicativeInverse(a);}
115 
Subtract(const Element & a,const Element & b) const116         const Element& Subtract(const Element &a, const Element &b) const
117             {return GetRing().Divide(a, b);}
118 
Reduce(Element & a,const Element & b) const119         Element& Reduce(Element &a, const Element &b) const
120             {return a = GetRing().Divide(a, b);}
121 
Double(const Element & a) const122         const Element& Double(const Element &a) const
123             {return GetRing().Square(a);}
124 
ScalarMultiply(const Element & a,const Integer & e) const125         Element ScalarMultiply(const Element &a, const Integer &e) const
126             {return GetRing().Exponentiate(a, e);}
127 
CascadeScalarMultiply(const Element & x,const Integer & e1,const Element & y,const Integer & e2) const128         Element CascadeScalarMultiply(const Element &x, const Integer &e1,
129                                      const Element &y, const Integer &e2) const
130             {return GetRing().CascadeExponentiate(x, e1, y, e2);}
131 
SimultaneousMultiply(Element * results,const Element & base,const Integer * exponents,unsigned int exponentsCount) const132         void SimultaneousMultiply(Element *results, const Element &base,
133                    const Integer *exponents, unsigned int exponentsCount) const
134             {GetRing().SimultaneousExponentiate(results, base, exponents,
135                                                 exponentsCount);}
136 
137         const AbstractRing* m_pRing;
138     };
139 
140     MultiplicativeGroupT m_mg;
141 };
142 
143 
144 // Abstract Euclidean Domain
145 class TAOCRYPT_NO_VTABLE AbstractEuclideanDomain
146     : public AbstractRing
147 {
148 public:
149     typedef Integer Element;
150 
151     virtual void DivisionAlgorithm(Element &r, Element &q, const Element &a,
152                                    const Element &d) const =0;
153 
154     virtual const Element& Mod(const Element &a, const Element &b) const =0;
155     virtual const Element& Gcd(const Element &a, const Element &b) const;
156 
157 protected:
158     mutable Element result;
159 };
160 
161 
162 // EuclideanDomainOf
163 class EuclideanDomainOf : public AbstractEuclideanDomain
164 {
165 public:
166     typedef Integer Element;
167 
EuclideanDomainOf()168     EuclideanDomainOf() {}
169 
Equal(const Element & a,const Element & b) const170     bool Equal(const Element &a, const Element &b) const
171         {return a==b;}
172 
Identity() const173     const Element& Identity() const
174         {return Element::Zero();}
175 
Add(const Element & a,const Element & b) const176     const Element& Add(const Element &a, const Element &b) const
177         {return result = a+b;}
178 
Accumulate(Element & a,const Element & b) const179     Element& Accumulate(Element &a, const Element &b) const
180         {return a+=b;}
181 
Inverse(const Element & a) const182     const Element& Inverse(const Element &a) const
183         {return result = -a;}
184 
Subtract(const Element & a,const Element & b) const185     const Element& Subtract(const Element &a, const Element &b) const
186         {return result = a-b;}
187 
Reduce(Element & a,const Element & b) const188     Element& Reduce(Element &a, const Element &b) const
189         {return a-=b;}
190 
Double(const Element & a) const191     const Element& Double(const Element &a) const
192         {return result = a.Doubled();}
193 
MultiplicativeIdentity() const194     const Element& MultiplicativeIdentity() const
195         {return Element::One();}
196 
Multiply(const Element & a,const Element & b) const197     const Element& Multiply(const Element &a, const Element &b) const
198         {return result = a*b;}
199 
Square(const Element & a) const200     const Element& Square(const Element &a) const
201         {return result = a.Squared();}
202 
IsUnit(const Element & a) const203     bool IsUnit(const Element &a) const
204         {return a.IsUnit();}
205 
MultiplicativeInverse(const Element & a) const206     const Element& MultiplicativeInverse(const Element &a) const
207         {return result = a.MultiplicativeInverse();}
208 
Divide(const Element & a,const Element & b) const209     const Element& Divide(const Element &a, const Element &b) const
210         {return result = a/b;}
211 
Mod(const Element & a,const Element & b) const212     const Element& Mod(const Element &a, const Element &b) const
213         {return result = a%b;}
214 
DivisionAlgorithm(Element & r,Element & q,const Element & a,const Element & d) const215     void DivisionAlgorithm(Element &r, Element &q, const Element &a,
216                            const Element &d) const
217         {Element::Divide(r, q, a, d);}
218 
219 private:
220     mutable Element result;
221 };
222 
223 
224 
225 } // namespace
226 
227 #endif // TAO_CRYPT_ALGEBRA_HPP
228