modarith.hpp 4.88 KB
Newer Older
unknown's avatar
unknown committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/*
   Copyright (C) 2000-2007 MySQL AB

   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; see the file COPYING. If not, write to the
   Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
   MA  02110-1301  USA.
*/
18 19 20 21 22 23 24 25 26 27 28 29 30 31


/* based on Wei Dai's modarith.h from CryptoPP */


#ifndef TAO_CRYPT_MODARITH_HPP
#define TAO_CRYPT_MODARITH_HPP

#include "misc.hpp"
#include "algebra.hpp"

namespace TaoCrypt {


unknown's avatar
unknown committed
32 33
// ModularArithmetic
class ModularArithmetic : public AbstractRing
34 35 36 37 38 39
{
public:

    typedef int RandomizationParameter;
    typedef Integer Element;

unknown's avatar
unknown committed
40 41
    ModularArithmetic(const Integer &modulus = Integer::One())
        : modulus(modulus), result((word)0, modulus.reg_.size()) {}
42 43

    ModularArithmetic(const ModularArithmetic &ma)
unknown's avatar
unknown committed
44
        : AbstractRing(),
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
        modulus(ma.modulus), result((word)0, modulus.reg_.size()) {}

    const Integer& GetModulus() const {return modulus;}
    void SetModulus(const Integer &newModulus) 
    {   
        modulus = newModulus;
        result.reg_.resize(modulus.reg_.size());
    }

    virtual bool IsMontgomeryRepresentation() const {return false;}

    virtual Integer ConvertIn(const Integer &a) const
        {return a%modulus;}

    virtual Integer ConvertOut(const Integer &a) const
        {return a;}

    const Integer& Half(const Integer &a) const;

    bool Equal(const Integer &a, const Integer &b) const
        {return a==b;}

    const Integer& Identity() const
        {return Integer::Zero();}

    const Integer& Add(const Integer &a, const Integer &b) const;

    Integer& Accumulate(Integer &a, const Integer &b) const;

    const Integer& Inverse(const Integer &a) const;

    const Integer& Subtract(const Integer &a, const Integer &b) const;

    Integer& Reduce(Integer &a, const Integer &b) const;

    const Integer& Double(const Integer &a) const
        {return Add(a, a);}

    const Integer& MultiplicativeIdentity() const
        {return Integer::One();}

    const Integer& Multiply(const Integer &a, const Integer &b) const
        {return result1 = a*b%modulus;}

    const Integer& Square(const Integer &a) const
        {return result1 = a.Squared()%modulus;}

    bool IsUnit(const Integer &a) const
        {return Integer::Gcd(a, modulus).IsUnit();}

    const Integer& MultiplicativeInverse(const Integer &a) const
        {return result1 = a.InverseMod(modulus);}

    const Integer& Divide(const Integer &a, const Integer &b) const
        {return Multiply(a, MultiplicativeInverse(b));}

    Integer CascadeExponentiate(const Integer &x, const Integer &e1,
                                const Integer &y, const Integer &e2) const;

    void SimultaneousExponentiate(Element *results, const Element &base,
                  const Integer *exponents, unsigned int exponentsCount) const;

    unsigned int MaxElementBitLength() const
        {return (modulus-1).BitCount();}

    unsigned int MaxElementByteLength() const
        {return (modulus-1).ByteCount();}


    static const RandomizationParameter DefaultRandomizationParameter;

protected:
    Integer modulus;
    mutable Integer result, result1;

};



//! do modular arithmetics in Montgomery representation for increased speed
class MontgomeryRepresentation : public ModularArithmetic
{
public:
    MontgomeryRepresentation(const Integer &modulus);	// modulus must be odd

    bool IsMontgomeryRepresentation() const {return true;}

    Integer ConvertIn(const Integer &a) const
        {return (a<<(WORD_BITS*modulus.reg_.size()))%modulus;}

    Integer ConvertOut(const Integer &a) const;

    const Integer& MultiplicativeIdentity() const
     {return result1 = Integer::Power2(WORD_BITS*modulus.reg_.size())%modulus;}

    const Integer& Multiply(const Integer &a, const Integer &b) const;

    const Integer& Square(const Integer &a) const;

    const Integer& MultiplicativeInverse(const Integer &a) const;

    Integer CascadeExponentiate(const Integer &x, const Integer &e1,
                                const Integer &y, const Integer &e2) const
unknown's avatar
unknown committed
148
        {return AbstractRing::CascadeExponentiate(x, e1, y, e2);}
149 150 151

    void SimultaneousExponentiate(Element *results, const Element &base,
            const Integer *exponents, unsigned int exponentsCount) const
unknown's avatar
unknown committed
152 153
        {AbstractRing::SimultaneousExponentiate(results, base,
                                                exponents, exponentsCount);}
154 155 156 157 158 159 160 161 162 163 164 165

private:
    Integer u;
    mutable AlignedWordBlock workspace;
};




} // namespace

#endif // TAO_CRYPT_MODARITH_HPP