include/cryptopp/xtr.h

0001 #ifndef CRYPTOPP_XTR_H
0002 #define CRYPTOPP_XTR_H
0003
0004 /// \file xtr.h

0005 /// \brief The XTR public key system

0006 /// \details The XTR public key system by Arjen K. Lenstra and Eric R. Verheul

0007
0008 #include "cryptlib.h"
0009 #include "modarith.h"
0010 #include "integer.h"
0011 #include "algebra.h"
0012
0013 NAMESPACE_BEGIN(CryptoPP)
0014
0015 /// \brief an element of GF(p^2)

0016 class GFP2Element
0017 {
0018 public:
0019     GFP2Element() {}
0020     GFP2Element(const Integer &c1, const Integer &c2) : c1(c1), c2(c2) {}
0021     GFP2Element(const byte *encodedElement, unsigned int size)
0022         : c1(encodedElement, size/2), c2(encodedElement+size/2, size/2) {}
0023
0024     void Encode(byte *encodedElement, unsigned int size)
0025     {
0026         c1.Encode(encodedElement, size/2);
0027         c2.Encode(encodedElement+size/2, size/2);
0028     }
0029
0030     bool operator==(const GFP2Element &rhs) const {return c1 == rhs.c1 && c2 == rhs.c2;}
0031     bool operator!=(const GFP2Element &rhs) const {return !operator==(rhs);}
0032
0033     void swap(GFP2Element &a)
0034     {
0035         c1.swap(a.c1);
0036         c2.swap(a.c2);
0037     }
0038
0039     static const GFP2Element & Zero();
0040
0041     Integer c1, c2;
0042 };
0043
0044 /// \brief GF(p^2), optimal normal basis

0045 template <class F>
0046 class GFP2_ONB : public AbstractRing<GFP2Element>
0047 {
0048 public:
0049     typedef F BaseField;
0050
0051     GFP2_ONB(const Integer &p) : modp(p)
0052     {
0053         if (p%3 != 2)
0054             throw InvalidArgument("GFP2_ONB: modulus must be equivalent to 2 mod 3");
0055     }
0056
0057     const Integer& GetModulus() const {return modp.GetModulus();}
0058
0059     GFP2Element ConvertIn(const Integer &a) const
0060     {
0061         t = modp.Inverse(modp.ConvertIn(a));
0062         return GFP2Element(t, t);
0063     }
0064
0065     GFP2Element ConvertIn(const GFP2Element &a) const
0066         {return GFP2Element(modp.ConvertIn(a.c1), modp.ConvertIn(a.c2));}
0067
0068     GFP2Element ConvertOut(const GFP2Element &a) const
0069         {return GFP2Element(modp.ConvertOut(a.c1), modp.ConvertOut(a.c2));}
0070
0071     bool Equal(const GFP2Element &a, const GFP2Element &b) const
0072     {
0073         return modp.Equal(a.c1, b.c1) && modp.Equal(a.c2, b.c2);
0074     }
0075
0076     const Element& Identity() const
0077     {
0078         return GFP2Element::Zero();
0079     }
0080
0081     const Element& Add(const Element &a, const Element &b) const
0082     {
0083         result.c1 = modp.Add(a.c1, b.c1);
0084         result.c2 = modp.Add(a.c2, b.c2);
0085         return result;
0086     }
0087
0088     const Element& Inverse(const Element &a) const
0089     {
0090         result.c1 = modp.Inverse(a.c1);
0091         result.c2 = modp.Inverse(a.c2);
0092         return result;
0093     }
0094
0095     const Element& Double(const Element &a) const
0096     {
0097         result.c1 = modp.Double(a.c1);
0098         result.c2 = modp.Double(a.c2);
0099         return result;
0100     }
0101
0102     const Element& Subtract(const Element &a, const Element &b) const
0103     {
0104         result.c1 = modp.Subtract(a.c1, b.c1);
0105         result.c2 = modp.Subtract(a.c2, b.c2);
0106         return result;
0107     }
0108
0109     Element& Accumulate(Element &a, const Element &b) const
0110     {
0111         modp.Accumulate(a.c1, b.c1);
0112         modp.Accumulate(a.c2, b.c2);
0113         return a;
0114     }
0115
0116     Element& Reduce(Element &a, const Element &b) const
0117     {
0118         modp.Reduce(a.c1, b.c1);
0119         modp.Reduce(a.c2, b.c2);
0120         return a;
0121     }
0122
0123     bool IsUnit(const Element &a) const
0124     {
0125         return a.c1.NotZero() || a.c2.NotZero();
0126     }
0127
0128     const Element& MultiplicativeIdentity() const
0129     {
0130         result.c1 = result.c2 = modp.Inverse(modp.MultiplicativeIdentity());
0131         return result;
0132     }
0133
0134     const Element& Multiply(const Element &a, const Element &b) const
0135     {
0136         t = modp.Add(a.c1, a.c2);
0137         t = modp.Multiply(t, modp.Add(b.c1, b.c2));
0138         result.c1 = modp.Multiply(a.c1, b.c1);
0139         result.c2 = modp.Multiply(a.c2, b.c2);
0140         result.c1.swap(result.c2);
0141         modp.Reduce(t, result.c1);
0142         modp.Reduce(t, result.c2);
0143         modp.Reduce(result.c1, t);
0144         modp.Reduce(result.c2, t);
0145         return result;
0146     }
0147
0148     const Element& MultiplicativeInverse(const Element &a) const
0149     {
0150         return result = Exponentiate(a, modp.GetModulus()-2);
0151     }
0152
0153     const Element& Square(const Element &a) const
0154     {
0155         const Integer &ac1 = (&a == &result) ? (t = a.c1) : a.c1;
0156         result.c1 = modp.Multiply(modp.Subtract(modp.Subtract(a.c2, a.c1), a.c1), a.c2);
0157         result.c2 = modp.Multiply(modp.Subtract(modp.Subtract(ac1, a.c2), a.c2), ac1);
0158         return result;
0159     }
0160
0161     Element Exponentiate(const Element &a, const Integer &e) const
0162     {
0163         Integer edivp, emodp;
0164         Integer::Divide(emodp, edivp, e, modp.GetModulus());
0165         Element b = PthPower(a);
0166         return AbstractRing<GFP2Element>::CascadeExponentiate(a, emodp, b, edivp);
0167     }
0168
0169     const Element & PthPower(const Element &a) const
0170     {
0171         result = a;
0172         result.c1.swap(result.c2);
0173         return result;
0174     }
0175
0176     void RaiseToPthPower(Element &a) const
0177     {
0178         a.c1.swap(a.c2);
0179     }
0180
0181     // a^2 - 2a^p

0182     const Element & SpecialOperation1(const Element &a) const
0183     {
0184         CRYPTOPP_ASSERT(&a != &result);
0185         result = Square(a);
0186         modp.Reduce(result.c1, a.c2);
0187         modp.Reduce(result.c1, a.c2);
0188         modp.Reduce(result.c2, a.c1);
0189         modp.Reduce(result.c2, a.c1);
0190         return result;
0191     }
0192
0193     // x * z - y * z^p

0194     const Element & SpecialOperation2(const Element &x, const Element &y, const Element &z) const
0195     {
0196         CRYPTOPP_ASSERT(&x != &result && &y != &result && &z != &result);
0197         t = modp.Add(x.c2, y.c2);
0198         result.c1 = modp.Multiply(z.c1, modp.Subtract(y.c1, t));
0199         modp.Accumulate(result.c1, modp.Multiply(z.c2, modp.Subtract(t, x.c1)));
0200         t = modp.Add(x.c1, y.c1);
0201         result.c2 = modp.Multiply(z.c2, modp.Subtract(y.c2, t));
0202         modp.Accumulate(result.c2, modp.Multiply(z.c1, modp.Subtract(t, x.c2)));
0203         return result;
0204     }
0205
0206 protected:
0207     BaseField modp;
0208     mutable GFP2Element result;
0209     mutable Integer t;
0210 };
0211
0212 /// \brief Creates primes p,q and generator g for XTR

0213 void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits);
0214
0215 GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p);
0216
0217 NAMESPACE_END
0218
0219 #endif