release/src/router/mysql/extra/yassl/taocrypt/include/modarith.hpp

   1 /*
   2    Copyright (C) 2000-2007 MySQL AB
   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
  20 /* based on Wei Dai's modarith.h from CryptoPP */
  21
  22
  23 #ifndef TAO_CRYPT_MODARITH_HPP
  24 #define TAO_CRYPT_MODARITH_HPP
  25
  26 #include "misc.hpp"
  27 #include "algebra.hpp"
  28
  29 namespace TaoCrypt {
  30
  31
  32 // ModularArithmetic
  33 class ModularArithmetic : public AbstractRing
  34 {
  35 public:
  36
  37     typedef int RandomizationParameter;
  38     typedef Integer Element;
  39
  40     ModularArithmetic(const Integer &modulus = Integer::One())
  41         : modulus(modulus), result((word)0, modulus.reg_.size()) {}
  42
  43     ModularArithmetic(const ModularArithmetic &ma)
  44         : AbstractRing(),
  45         modulus(ma.modulus), result((word)0, modulus.reg_.size()) {}
  46
  47     const Integer& GetModulus() const {return modulus;}
  48     void SetModulus(const Integer &newModulus)
  49     {
  50         modulus = newModulus;
  51         result.reg_.resize(modulus.reg_.size());
  52     }
  53
  54     virtual bool IsMontgomeryRepresentation() const {return false;}
  55
  56     virtual Integer ConvertIn(const Integer &a) const
  57         {return a%modulus;}
  58
  59     virtual Integer ConvertOut(const Integer &a) const
  60         {return a;}
  61
  62     const Integer& Half(const Integer &a) const;
  63
  64     bool Equal(const Integer &a, const Integer &b) const
  65         {return a==b;}
  66
  67     const Integer& Identity() const
  68         {return Integer::Zero();}
  69
  70     const Integer& Add(const Integer &a, const Integer &b) const;
  71
  72     Integer& Accumulate(Integer &a, const Integer &b) const;
  73
  74     const Integer& Inverse(const Integer &a) const;
  75
  76     const Integer& Subtract(const Integer &a, const Integer &b) const;
  77
  78     Integer& Reduce(Integer &a, const Integer &b) const;
  79
  80     const Integer& Double(const Integer &a) const
  81         {return Add(a, a);}
  82
  83     const Integer& MultiplicativeIdentity() const
  84         {return Integer::One();}
  85
  86     const Integer& Multiply(const Integer &a, const Integer &b) const
  87         {return result1 = a*b%modulus;}
  88
  89     const Integer& Square(const Integer &a) const
  90         {return result1 = a.Squared()%modulus;}
  91
  92     bool IsUnit(const Integer &a) const
  93         {return Integer::Gcd(a, modulus).IsUnit();}
  94
  95     const Integer& MultiplicativeInverse(const Integer &a) const
  96         {return result1 = a.InverseMod(modulus);}
  97
  98     const Integer& Divide(const Integer &a, const Integer &b) const
  99         {return Multiply(a, MultiplicativeInverse(b));}
 100
 101     Integer CascadeExponentiate(const Integer &x, const Integer &e1,
 102                                 const Integer &y, const Integer &e2) const;
 103
 104     void SimultaneousExponentiate(Element *results, const Element &base,
 105                   const Integer *exponents, unsigned int exponentsCount) const;
 106
 107     unsigned int MaxElementBitLength() const
 108         {return (modulus-1).BitCount();}
 109
 110     unsigned int MaxElementByteLength() const
 111         {return (modulus-1).ByteCount();}
 112
 113
 114     static const RandomizationParameter DefaultRandomizationParameter;
 115
 116 protected:
 117     Integer modulus;
 118     mutable Integer result, result1;
 119
 120 };
 121
 122
 123
 124 //! do modular arithmetics in Montgomery representation for increased speed
 125 class MontgomeryRepresentation : public ModularArithmetic
 126 {
 127 public:
 128     MontgomeryRepresentation(const Integer &modulus);   // modulus must be odd
 129
 130     bool IsMontgomeryRepresentation() const {return true;}
 131
 132     Integer ConvertIn(const Integer &a) const
 133         {return (a<<(WORD_BITS*modulus.reg_.size()))%modulus;}
 134
 135     Integer ConvertOut(const Integer &a) const;
 136
 137     const Integer& MultiplicativeIdentity() const
 138      {return result1 = Integer::Power2(WORD_BITS*modulus.reg_.size())%modulus;}
 139
 140     const Integer& Multiply(const Integer &a, const Integer &b) const;
 141
 142     const Integer& Square(const Integer &a) const;
 143
 144     const Integer& MultiplicativeInverse(const Integer &a) const;
 145
 146     Integer CascadeExponentiate(const Integer &x, const Integer &e1,
 147                                 const Integer &y, const Integer &e2) const
 148         {return AbstractRing::CascadeExponentiate(x, e1, y, e2);}
 149
 150     void SimultaneousExponentiate(Element *results, const Element &base,
 151             const Integer *exponents, unsigned int exponentsCount) const
 152         {AbstractRing::SimultaneousExponentiate(results, base,
 153                                                 exponents, exponentsCount);}
 154
 155 private:
 156     Integer u;
 157     mutable AlignedWordBlock workspace;
 158 };
 159
 160
 161
 162
 163 } // namespace
 164
 165 #endif // TAO_CRYPT_MODARITH_HPP