diff options
Diffstat (limited to 'mysql/extra/yassl/taocrypt/src/algebra.cpp')
| -rw-r--r-- | mysql/extra/yassl/taocrypt/src/algebra.cpp | 336 |
1 files changed, 336 insertions, 0 deletions
diff --git a/mysql/extra/yassl/taocrypt/src/algebra.cpp b/mysql/extra/yassl/taocrypt/src/algebra.cpp new file mode 100644 index 0000000..ace1704 --- /dev/null +++ b/mysql/extra/yassl/taocrypt/src/algebra.cpp @@ -0,0 +1,336 @@ +/* + Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */ + +/* based on Wei Dai's algebra.cpp from CryptoPP */ +#undef NDEBUG +#define DEBUG // GCC 4.0 bug if NDEBUG and Optimize > 1 + +#include "runtime.hpp" +#include "algebra.hpp" +#ifdef USE_SYS_STL + #include <vector> +#else + #include "vector.hpp" +#endif + + +namespace STL = STL_NAMESPACE; + + +namespace TaoCrypt { + + +const Integer& AbstractGroup::Double(const Element &a) const +{ + return Add(a, a); +} + +const Integer& AbstractGroup::Subtract(const Element &a, const Element &b) const +{ + // make copy of a in case Inverse() overwrites it + Element a1(a); + return Add(a1, Inverse(b)); +} + +Integer& AbstractGroup::Accumulate(Element &a, const Element &b) const +{ + return a = Add(a, b); +} + +Integer& AbstractGroup::Reduce(Element &a, const Element &b) const +{ + return a = Subtract(a, b); +} + +const Integer& AbstractRing::Square(const Element &a) const +{ + return Multiply(a, a); +} + + +const Integer& AbstractRing::Divide(const Element &a, const Element &b) const +{ + // make copy of a in case MultiplicativeInverse() overwrites it + Element a1(a); + return Multiply(a1, MultiplicativeInverse(b)); +} + + +const Integer& AbstractEuclideanDomain::Mod(const Element &a, + const Element &b) const +{ + Element q; + DivisionAlgorithm(result, q, a, b); + return result; +} + +const Integer& AbstractEuclideanDomain::Gcd(const Element &a, + const Element &b) const +{ + STL::vector<Element> g(3); + g[0]= b; + g[1]= a; + unsigned int i0=0, i1=1, i2=2; + + while (!Equal(g[i1], this->Identity())) + { + g[i2] = Mod(g[i0], g[i1]); + unsigned int t = i0; i0 = i1; i1 = i2; i2 = t; + } + + return result = g[i0]; +} + + +Integer AbstractGroup::ScalarMultiply(const Element &base, + const Integer &exponent) const +{ + Element result; + SimultaneousMultiply(&result, base, &exponent, 1); + return result; +} + + +Integer AbstractGroup::CascadeScalarMultiply(const Element &x, + const Integer &e1, const Element &y, const Integer &e2) const +{ + const unsigned expLen = max(e1.BitCount(), e2.BitCount()); + if (expLen==0) + return Identity(); + + const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3)); + const unsigned tableSize = 1<<w; + STL::vector<Element> powerTable(tableSize << w); + + powerTable[1] = x; + powerTable[tableSize] = y; + if (w==1) + powerTable[3] = Add(x,y); + else + { + powerTable[2] = Double(x); + powerTable[2*tableSize] = Double(y); + + unsigned i, j; + + for (i=3; i<tableSize; i+=2) + powerTable[i] = Add(powerTable[i-2], powerTable[2]); + for (i=1; i<tableSize; i+=2) + for (j=i+tableSize; j<(tableSize<<w); j+=tableSize) + powerTable[j] = Add(powerTable[j-tableSize], y); + + for (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize) + powerTable[i] = Add(powerTable[i-2*tableSize], + powerTable[2*tableSize]); + for (i=tableSize; i<(tableSize<<w); i+=2*tableSize) + for (j=i+2; j<i+tableSize; j+=2) + powerTable[j] = Add(powerTable[j-1], x); + } + + Element result; + unsigned power1 = 0, power2 = 0, prevPosition = expLen-1; + bool firstTime = true; + + for (int i = expLen-1; i>=0; i--) + { + power1 = 2*power1 + e1.GetBit(i); + power2 = 2*power2 + e2.GetBit(i); + + if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize) + { + unsigned squaresBefore = prevPosition-i; + unsigned squaresAfter = 0; + prevPosition = i; + while ((power1 || power2) && power1%2 == 0 && power2%2==0) + { + power1 /= 2; + power2 /= 2; + squaresBefore--; + squaresAfter++; + } + if (firstTime) + { + result = powerTable[(power2<<w) + power1]; + firstTime = false; + } + else + { + while (squaresBefore--) + result = Double(result); + if (power1 || power2) + Accumulate(result, powerTable[(power2<<w) + power1]); + } + while (squaresAfter--) + result = Double(result); + power1 = power2 = 0; + } + } + return result; +} + + +struct WindowSlider +{ + WindowSlider(const Integer &exp, bool fastNegate, + unsigned int windowSizeIn=0) + : exp(exp), windowModulus(Integer::One()), windowSize(windowSizeIn), + windowBegin(0), fastNegate(fastNegate), firstTime(true), + finished(false) + { + if (windowSize == 0) + { + unsigned int expLen = exp.BitCount(); + windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 : + (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 : + (expLen <= 1434 ? 6 : 7))))); + } + windowModulus <<= windowSize; + } + + void FindNextWindow() + { + unsigned int expLen = exp.WordCount() * WORD_BITS; + unsigned int skipCount = firstTime ? 0 : windowSize; + firstTime = false; + while (!exp.GetBit(skipCount)) + { + if (skipCount >= expLen) + { + finished = true; + return; + } + skipCount++; + } + + exp >>= skipCount; + windowBegin += skipCount; + expWindow = exp % (1 << windowSize); + + if (fastNegate && exp.GetBit(windowSize)) + { + negateNext = true; + expWindow = (1 << windowSize) - expWindow; + exp += windowModulus; + } + else + negateNext = false; + } + + Integer exp, windowModulus; + unsigned int windowSize, windowBegin, expWindow; + bool fastNegate, negateNext, firstTime, finished; +}; + + +void AbstractGroup::SimultaneousMultiply(Integer *results, const Integer &base, + const Integer *expBegin, unsigned int expCount) const +{ + STL::vector<STL::vector<Element> > buckets(expCount); + STL::vector<WindowSlider> exponents; + exponents.reserve(expCount); + unsigned int i; + + for (i=0; i<expCount; i++) + { + exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0)); + exponents[i].FindNextWindow(); + buckets[i].resize(1<<(exponents[i].windowSize-1), Identity()); + } + + unsigned int expBitPosition = 0; + Element g = base; + bool notDone = true; + + while (notDone) + { + notDone = false; + for (i=0; i<expCount; i++) + { + if (!exponents[i].finished && expBitPosition == + exponents[i].windowBegin) + { + Element &bucket = buckets[i][exponents[i].expWindow/2]; + if (exponents[i].negateNext) + Accumulate(bucket, Inverse(g)); + else + Accumulate(bucket, g); + exponents[i].FindNextWindow(); + } + notDone = notDone || !exponents[i].finished; + } + + if (notDone) + { + g = Double(g); + expBitPosition++; + } + } + + for (i=0; i<expCount; i++) + { + Element &r = *results++; + r = buckets[i][buckets[i].size()-1]; + if (buckets[i].size() > 1) + { + for (size_t j = buckets[i].size()-2; j >= 1; j--) + { + Accumulate(buckets[i][j], buckets[i][j+1]); + Accumulate(r, buckets[i][j]); + } + Accumulate(buckets[i][0], buckets[i][1]); + r = Add(Double(r), buckets[i][0]); + } + } +} + +Integer AbstractRing::Exponentiate(const Element &base, + const Integer &exponent) const +{ + Element result; + SimultaneousExponentiate(&result, base, &exponent, 1); + return result; +} + + +Integer AbstractRing::CascadeExponentiate(const Element &x, + const Integer &e1, const Element &y, const Integer &e2) const +{ + return MultiplicativeGroup().AbstractGroup::CascadeScalarMultiply( + x, e1, y, e2); +} + + +void AbstractRing::SimultaneousExponentiate(Integer *results, + const Integer &base, + const Integer *exponents, unsigned int expCount) const +{ + MultiplicativeGroup().AbstractGroup::SimultaneousMultiply(results, base, + exponents, expCount); +} + + +} // namespace + + +#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION +namespace mySTL { +template TaoCrypt::WindowSlider* uninit_copy<TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*>(TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*); +template void destroy<TaoCrypt::WindowSlider*>(TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*); +template TaoCrypt::WindowSlider* GetArrayMemory<TaoCrypt::WindowSlider>(size_t); +template void FreeArrayMemory<TaoCrypt::WindowSlider>(TaoCrypt::WindowSlider*); +} +#endif + |