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