1 /*
2 Copyright (c) 2005, 2012, Oracle and/or its affiliates
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; see the file COPYING. If not, write to the
15 Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
16 MA 02110-1335 USA.
17 */
18
19 /* based on Wei Dai's algebra.cpp from CryptoPP */
20 #undef NDEBUG
21
22 #include "runtime.hpp"
23 #include "algebra.hpp"
24 #ifdef USE_SYS_STL
25 #include <vector>
26 #else
27 #include "vector.hpp"
28 #endif
29
30
31 namespace STL = STL_NAMESPACE;
32
33
34 namespace TaoCrypt {
35
36
Double(const Element & a) const37 const Integer& AbstractGroup::Double(const Element &a) const
38 {
39 return Add(a, a);
40 }
41
Subtract(const Element & a,const Element & b) const42 const Integer& AbstractGroup::Subtract(const Element &a, const Element &b) const
43 {
44 // make copy of a in case Inverse() overwrites it
45 Element a1(a);
46 return Add(a1, Inverse(b));
47 }
48
Accumulate(Element & a,const Element & b) const49 Integer& AbstractGroup::Accumulate(Element &a, const Element &b) const
50 {
51 return a = Add(a, b);
52 }
53
Reduce(Element & a,const Element & b) const54 Integer& AbstractGroup::Reduce(Element &a, const Element &b) const
55 {
56 return a = Subtract(a, b);
57 }
58
Square(const Element & a) const59 const Integer& AbstractRing::Square(const Element &a) const
60 {
61 return Multiply(a, a);
62 }
63
64
Divide(const Element & a,const Element & b) const65 const Integer& AbstractRing::Divide(const Element &a, const Element &b) const
66 {
67 // make copy of a in case MultiplicativeInverse() overwrites it
68 Element a1(a);
69 return Multiply(a1, MultiplicativeInverse(b));
70 }
71
72
Mod(const Element & a,const Element & b) const73 const Integer& AbstractEuclideanDomain::Mod(const Element &a,
74 const Element &b) const
75 {
76 Element q;
77 DivisionAlgorithm(result, q, a, b);
78 return result;
79 }
80
Gcd(const Element & a,const Element & b) const81 const Integer& AbstractEuclideanDomain::Gcd(const Element &a,
82 const Element &b) const
83 {
84 STL::vector<Element> g(3);
85 g[0]= b;
86 g[1]= a;
87 unsigned int i0=0, i1=1, i2=2;
88
89 while (!Equal(g[i1], this->Identity()))
90 {
91 g[i2] = Mod(g[i0], g[i1]);
92 unsigned int t = i0; i0 = i1; i1 = i2; i2 = t;
93 }
94
95 return result = g[i0];
96 }
97
98
ScalarMultiply(const Element & base,const Integer & exponent) const99 Integer AbstractGroup::ScalarMultiply(const Element &base,
100 const Integer &exponent) const
101 {
102 Element result;
103 SimultaneousMultiply(&result, base, &exponent, 1);
104 return result;
105 }
106
107
CascadeScalarMultiply(const Element & x,const Integer & e1,const Element & y,const Integer & e2) const108 Integer AbstractGroup::CascadeScalarMultiply(const Element &x,
109 const Integer &e1, const Element &y, const Integer &e2) const
110 {
111 const unsigned expLen = max(e1.BitCount(), e2.BitCount());
112 if (expLen==0)
113 return Identity();
114
115 const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3));
116 const unsigned tableSize = 1<<w;
117 STL::vector<Element> powerTable(tableSize << w);
118
119 powerTable[1] = x;
120 powerTable[tableSize] = y;
121 if (w==1)
122 powerTable[3] = Add(x,y);
123 else
124 {
125 powerTable[2] = Double(x);
126 powerTable[2*tableSize] = Double(y);
127
128 unsigned i, j;
129
130 for (i=3; i<tableSize; i+=2)
131 powerTable[i] = Add(powerTable[i-2], powerTable[2]);
132 for (i=1; i<tableSize; i+=2)
133 for (j=i+tableSize; j<(tableSize<<w); j+=tableSize)
134 powerTable[j] = Add(powerTable[j-tableSize], y);
135
136 for (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize)
137 powerTable[i] = Add(powerTable[i-2*tableSize],
138 powerTable[2*tableSize]);
139 for (i=tableSize; i<(tableSize<<w); i+=2*tableSize)
140 for (j=i+2; j<i+tableSize; j+=2)
141 powerTable[j] = Add(powerTable[j-1], x);
142 }
143
144 Element result;
145 unsigned power1 = 0, power2 = 0, prevPosition = expLen-1;
146 bool firstTime = true;
147
148 for (int i = expLen-1; i>=0; i--)
149 {
150 power1 = 2*power1 + e1.GetBit(i);
151 power2 = 2*power2 + e2.GetBit(i);
152
153 if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize)
154 {
155 unsigned squaresBefore = prevPosition-i;
156 unsigned squaresAfter = 0;
157 prevPosition = i;
158 while ((power1 || power2) && power1%2 == 0 && power2%2==0)
159 {
160 power1 /= 2;
161 power2 /= 2;
162 squaresBefore--;
163 squaresAfter++;
164 }
165 if (firstTime)
166 {
167 result = powerTable[(power2<<w) + power1];
168 firstTime = false;
169 }
170 else
171 {
172 while (squaresBefore--)
173 result = Double(result);
174 if (power1 || power2)
175 Accumulate(result, powerTable[(power2<<w) + power1]);
176 }
177 while (squaresAfter--)
178 result = Double(result);
179 power1 = power2 = 0;
180 }
181 }
182 return result;
183 }
184
185
186 struct WindowSlider
187 {
WindowSliderTaoCrypt::WindowSlider188 WindowSlider(const Integer &exp, bool fastNegate,
189 unsigned int windowSizeIn=0)
190 : exp(exp), windowModulus(Integer::One()), windowSize(windowSizeIn),
191 windowBegin(0), fastNegate(fastNegate), firstTime(true),
192 finished(false)
193 {
194 if (windowSize == 0)
195 {
196 unsigned int expLen = exp.BitCount();
197 windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 :
198 (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 :
199 (expLen <= 1434 ? 6 : 7)))));
200 }
201 windowModulus <<= windowSize;
202 }
203
FindNextWindowTaoCrypt::WindowSlider204 void FindNextWindow()
205 {
206 unsigned int expLen = exp.WordCount() * WORD_BITS;
207 unsigned int skipCount = firstTime ? 0 : windowSize;
208 firstTime = false;
209 while (!exp.GetBit(skipCount))
210 {
211 if (skipCount >= expLen)
212 {
213 finished = true;
214 return;
215 }
216 skipCount++;
217 }
218
219 exp >>= skipCount;
220 windowBegin += skipCount;
221 expWindow = (unsigned int)(exp % (1LL << windowSize));
222
223 if (fastNegate && exp.GetBit(windowSize))
224 {
225 negateNext = true;
226 expWindow = (1 << windowSize) - expWindow;
227 exp += windowModulus;
228 }
229 else
230 negateNext = false;
231 }
232
233 Integer exp, windowModulus;
234 unsigned int windowSize, windowBegin, expWindow;
235 bool fastNegate, negateNext, firstTime, finished;
236 };
237
238
SimultaneousMultiply(Integer * results,const Integer & base,const Integer * expBegin,unsigned int expCount) const239 void AbstractGroup::SimultaneousMultiply(Integer *results, const Integer &base,
240 const Integer *expBegin, unsigned int expCount) const
241 {
242 STL::vector<STL::vector<Element> > buckets(expCount);
243 STL::vector<WindowSlider> exponents;
244 exponents.reserve(expCount);
245 unsigned int i;
246
247 for (i=0; i<expCount; i++)
248 {
249 exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0));
250 exponents[i].FindNextWindow();
251 buckets[i].resize(size_t(1)<<(exponents[i].windowSize-1), Identity());
252 }
253
254 unsigned int expBitPosition = 0;
255 Element g = base;
256 bool notDone = true;
257
258 while (notDone)
259 {
260 notDone = false;
261 for (i=0; i<expCount; i++)
262 {
263 if (!exponents[i].finished && expBitPosition ==
264 exponents[i].windowBegin)
265 {
266 Element &bucket = buckets[i][exponents[i].expWindow/2];
267 if (exponents[i].negateNext)
268 Accumulate(bucket, Inverse(g));
269 else
270 Accumulate(bucket, g);
271 exponents[i].FindNextWindow();
272 }
273 notDone = notDone || !exponents[i].finished;
274 }
275
276 if (notDone)
277 {
278 g = Double(g);
279 expBitPosition++;
280 }
281 }
282
283 for (i=0; i<expCount; i++)
284 {
285 Element &r = *results++;
286 r = buckets[i][buckets[i].size()-1];
287 if (buckets[i].size() > 1)
288 {
289 for (size_t j = buckets[i].size()-2; j >= 1; j--)
290 {
291 Accumulate(buckets[i][j], buckets[i][j+1]);
292 Accumulate(r, buckets[i][j]);
293 }
294 Accumulate(buckets[i][0], buckets[i][1]);
295 r = Add(Double(r), buckets[i][0]);
296 }
297 }
298 }
299
Exponentiate(const Element & base,const Integer & exponent) const300 Integer AbstractRing::Exponentiate(const Element &base,
301 const Integer &exponent) const
302 {
303 Element result;
304 SimultaneousExponentiate(&result, base, &exponent, 1);
305 return result;
306 }
307
308
CascadeExponentiate(const Element & x,const Integer & e1,const Element & y,const Integer & e2) const309 Integer AbstractRing::CascadeExponentiate(const Element &x,
310 const Integer &e1, const Element &y, const Integer &e2) const
311 {
312 return MultiplicativeGroup().AbstractGroup::CascadeScalarMultiply(
313 x, e1, y, e2);
314 }
315
316
SimultaneousExponentiate(Integer * results,const Integer & base,const Integer * exponents,unsigned int expCount) const317 void AbstractRing::SimultaneousExponentiate(Integer *results,
318 const Integer &base,
319 const Integer *exponents, unsigned int expCount) const
320 {
321 MultiplicativeGroup().AbstractGroup::SimultaneousMultiply(results, base,
322 exponents, expCount);
323 }
324
325
326 } // namespace
327
328