release/src/router/mysql/extra/yassl/taocrypt/src/algebra.cpp

   1 /*
   2    Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved.
   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-1301  USA.
  17 */
  18
  19 /* based on Wei Dai's algebra.cpp from CryptoPP */
  20 #undef  NDEBUG
  21 #define DEBUG   // GCC 4.0 bug if NDEBUG and Optimize > 1
  22
  23 #include "runtime.hpp"
  24 #include "algebra.hpp"
  25 #ifdef USE_SYS_STL
  26     #include <vector>
  27 #else
  28     #include "vector.hpp"
  29 #endif
  30
  31
  32 namespace STL = STL_NAMESPACE;
  33
  34
  35 namespace TaoCrypt {
  36
  37
  38 const Integer& AbstractGroup::Double(const Element &a) const
  39 {
  40     return Add(a, a);
  41 }
  42
  43 const Integer& AbstractGroup::Subtract(const Element &a, const Element &b) const
  44 {
  45     // make copy of a in case Inverse() overwrites it
  46     Element a1(a);
  47     return Add(a1, Inverse(b));
  48 }
  49
  50 Integer& AbstractGroup::Accumulate(Element &a, const Element &b) const
  51 {
  52     return a = Add(a, b);
  53 }
  54
  55 Integer& AbstractGroup::Reduce(Element &a, const Element &b) const
  56 {
  57     return a = Subtract(a, b);
  58 }
  59
  60 const Integer& AbstractRing::Square(const Element &a) const
  61 {
  62     return Multiply(a, a);
  63 }
  64
  65
  66 const Integer& AbstractRing::Divide(const Element &a, const Element &b) const
  67 {
  68     // make copy of a in case MultiplicativeInverse() overwrites it
  69     Element a1(a);
  70     return Multiply(a1, MultiplicativeInverse(b));
  71 }
  72
  73
  74 const Integer& AbstractEuclideanDomain::Mod(const Element &a,
  75                                             const Element &b) const
  76 {
  77     Element q;
  78     DivisionAlgorithm(result, q, a, b);
  79     return result;
  80 }
  81
  82 const Integer& AbstractEuclideanDomain::Gcd(const Element &a,
  83                                             const Element &b) const
  84 {
  85     STL::vector<Element> g(3);
  86     g[0]= b;
  87     g[1]= a;
  88     unsigned int i0=0, i1=1, i2=2;
  89
  90     while (!Equal(g[i1], this->Identity()))
  91     {
  92         g[i2] = Mod(g[i0], g[i1]);
  93         unsigned int t = i0; i0 = i1; i1 = i2; i2 = t;
  94     }
  95
  96     return result = g[i0];
  97 }
  98
  99
 100 Integer AbstractGroup::ScalarMultiply(const Element &base,
 101                                       const Integer &exponent) const
 102 {
 103     Element result;
 104     SimultaneousMultiply(&result, base, &exponent, 1);
 105     return result;
 106 }
 107
 108
 109 Integer AbstractGroup::CascadeScalarMultiply(const Element &x,
 110                   const Integer &e1, const Element &y, const Integer &e2) const
 111 {
 112     const unsigned expLen = max(e1.BitCount(), e2.BitCount());
 113     if (expLen==0)
 114         return Identity();
 115
 116     const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3));
 117     const unsigned tableSize = 1<<w;
 118     STL::vector<Element> powerTable(tableSize << w);
 119
 120     powerTable[1] = x;
 121     powerTable[tableSize] = y;
 122     if (w==1)
 123         powerTable[3] = Add(x,y);
 124     else
 125     {
 126         powerTable[2] = Double(x);
 127         powerTable[2*tableSize] = Double(y);
 128
 129         unsigned i, j;
 130
 131         for (i=3; i<tableSize; i+=2)
 132             powerTable[i] = Add(powerTable[i-2], powerTable[2]);
 133         for (i=1; i<tableSize; i+=2)
 134             for (j=i+tableSize; j<(tableSize<<w); j+=tableSize)
 135                 powerTable[j] = Add(powerTable[j-tableSize], y);
 136
 137         for (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize)
 138             powerTable[i] = Add(powerTable[i-2*tableSize],
 139             powerTable[2*tableSize]);
 140         for (i=tableSize; i<(tableSize<<w); i+=2*tableSize)
 141             for (j=i+2; j<i+tableSize; j+=2)
 142                 powerTable[j] = Add(powerTable[j-1], x);
 143     }
 144
 145     Element result;
 146     unsigned power1 = 0, power2 = 0, prevPosition = expLen-1;
 147     bool firstTime = true;
 148
 149     for (int i = expLen-1; i>=0; i--)
 150     {
 151         power1 = 2*power1 + e1.GetBit(i);
 152         power2 = 2*power2 + e2.GetBit(i);
 153
 154         if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize)
 155         {
 156             unsigned squaresBefore = prevPosition-i;
 157             unsigned squaresAfter = 0;
 158             prevPosition = i;
 159             while ((power1 || power2) && power1%2 == 0 && power2%2==0)
 160             {
 161                 power1 /= 2;
 162                 power2 /= 2;
 163                 squaresBefore--;
 164                 squaresAfter++;
 165             }
 166             if (firstTime)
 167             {
 168                 result = powerTable[(power2<<w) + power1];
 169                 firstTime = false;
 170             }
 171             else
 172             {
 173                 while (squaresBefore--)
 174                 result = Double(result);
 175                 if (power1 || power2)
 176                     Accumulate(result, powerTable[(power2<<w) + power1]);
 177             }
 178             while (squaresAfter--)
 179                 result = Double(result);
 180             power1 = power2 = 0;
 181         }
 182     }
 183     return result;
 184 }
 185
 186
 187 struct WindowSlider
 188 {
 189     WindowSlider(const Integer &expIn, bool fastNegateIn,
 190                  unsigned int windowSizeIn=0)
 191         : exp(expIn), windowModulus(Integer::One()), windowSize(windowSizeIn),
 192           windowBegin(0), fastNegate(fastNegateIn), firstTime(true),
 193           finished(false)
 194     {
 195         if (windowSize == 0)
 196         {
 197             unsigned int expLen = exp.BitCount();
 198             windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 :
 199                 (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 :
 200                 (expLen <= 1434 ? 6 : 7)))));
 201         }
 202         windowModulus <<= windowSize;
 203     }
 204
 205     void FindNextWindow()
 206     {
 207         unsigned int expLen = exp.WordCount() * WORD_BITS;
 208         unsigned int skipCount = firstTime ? 0 : windowSize;
 209         firstTime = false;
 210         while (!exp.GetBit(skipCount))
 211         {
 212             if (skipCount >= expLen)
 213             {
 214                 finished = true;
 215                 return;
 216             }
 217             skipCount++;
 218         }
 219
 220         exp >>= skipCount;
 221         windowBegin += skipCount;
 222         expWindow = exp % (1 << windowSize);
 223
 224         if (fastNegate && exp.GetBit(windowSize))
 225         {
 226             negateNext = true;
 227             expWindow = (1 << windowSize) - expWindow;
 228             exp += windowModulus;
 229         }
 230         else
 231             negateNext = false;
 232     }
 233
 234     Integer exp, windowModulus;
 235     unsigned int windowSize, windowBegin, expWindow;
 236     bool fastNegate, negateNext, firstTime, finished;
 237 };
 238
 239
 240 void AbstractGroup::SimultaneousMultiply(Integer *results, const Integer &base,
 241                           const Integer *expBegin, unsigned int expCount) const
 242 {
 243     STL::vector<STL::vector<Element> > buckets(expCount);
 244     STL::vector<WindowSlider> exponents;
 245     exponents.reserve(expCount);
 246     unsigned int i;
 247
 248     for (i=0; i<expCount; i++)
 249     {
 250         exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0));
 251         exponents[i].FindNextWindow();
 252         buckets[i].resize(1<<(exponents[i].windowSize-1), Identity());
 253     }
 254
 255     unsigned int expBitPosition = 0;
 256     Element g = base;
 257     bool notDone = true;
 258
 259     while (notDone)
 260     {
 261         notDone = false;
 262         for (i=0; i<expCount; i++)
 263         {
 264             if (!exponents[i].finished && expBitPosition ==
 265                  exponents[i].windowBegin)
 266             {
 267                 Element &bucket = buckets[i][exponents[i].expWindow/2];
 268                 if (exponents[i].negateNext)
 269                     Accumulate(bucket, Inverse(g));
 270                 else
 271                     Accumulate(bucket, g);
 272                 exponents[i].FindNextWindow();
 273             }
 274             notDone = notDone || !exponents[i].finished;
 275         }
 276
 277         if (notDone)
 278         {
 279             g = Double(g);
 280             expBitPosition++;
 281         }
 282     }
 283
 284     for (i=0; i<expCount; i++)
 285     {
 286         Element &r = *results++;
 287         r = buckets[i][buckets[i].size()-1];
 288         if (buckets[i].size() > 1)
 289         {
 290             for (size_t j = buckets[i].size()-2; j >= 1; j--)
 291             {
 292                 Accumulate(buckets[i][j], buckets[i][j+1]);
 293                 Accumulate(r, buckets[i][j]);
 294             }
 295             Accumulate(buckets[i][0], buckets[i][1]);
 296             r = Add(Double(r), buckets[i][0]);
 297         }
 298     }
 299 }
 300
 301 Integer AbstractRing::Exponentiate(const Element &base,
 302                                    const Integer &exponent) const
 303 {
 304     Element result;
 305     SimultaneousExponentiate(&result, base, &exponent, 1);
 306     return result;
 307 }
 308
 309
 310 Integer AbstractRing::CascadeExponentiate(const Element &x,
 311                   const Integer &e1, const Element &y, const Integer &e2) const
 312 {
 313     return MultiplicativeGroup().AbstractGroup::CascadeScalarMultiply(
 314                 x, e1, y, e2);
 315 }
 316
 317
 318 void AbstractRing::SimultaneousExponentiate(Integer *results,
 319                                             const Integer &base,
 320                          const Integer *exponents, unsigned int expCount) const
 321 {
 322     MultiplicativeGroup().AbstractGroup::SimultaneousMultiply(results, base,
 323                                                           exponents, expCount);
 324 }
 325
 326
 327 } // namespace
 328
 329
 330 #ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
 331 namespace mySTL {
 332 template TaoCrypt::WindowSlider* uninit_copy<TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*>(TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*);
 333 template void destroy<TaoCrypt::WindowSlider*>(TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*);
 334 template TaoCrypt::WindowSlider* GetArrayMemory<TaoCrypt::WindowSlider>(size_t);
 335 template void FreeArrayMemory<TaoCrypt::WindowSlider>(TaoCrypt::WindowSlider*);
 336 }
 337 #endif
 338