- Main Page
- Namespaces
- Classes
- Files

# xtr.h

Go to the documentation of this file.

    00001 #ifndef CRYPTOPP_XTR_H
    00002 #define CRYPTOPP_XTR_H
    00003
    00004 /** \file
    00005         "The XTR public key system" by Arjen K. Lenstra and Eric R. Verheul
    00006 */
    00007
    00008 #include "modarith.h"
    00009
    00010 NAMESPACE_BEGIN(CryptoPP)
    00011
    00012 //! an element of GF(p^2)
    00013 class GFP2Element
    00014 {
    00015 public:
    00016         GFP2Element() {}
    00017         GFP2Element(const Integer &c1, const Integer &c2) : c1(c1), c2(c2) {}
    00018         GFP2Element(const byte *encodedElement, unsigned int size)
    00019                 : c1(encodedElement, size/2), c2(encodedElement+size/2, size/2) {}
    00020
    00021         void Encode(byte *encodedElement, unsigned int size)
    00022         {
    00023                 c1.Encode(encodedElement, size/2);
    00024                 c2.Encode(encodedElement+size/2, size/2);
    00025         }
    00026
    00027         bool operator==(const GFP2Element &rhs) const {return c1 == rhs.c1 && c2 == rhs.c2;}
    00028         bool operator!=(const GFP2Element &rhs) const {return !operator==(rhs);}
    00029
    00030         void swap(GFP2Element &a)
    00031         {
    00032                 c1.swap(a.c1);
    00033                 c2.swap(a.c2);
    00034         }
    00035
    00036         static const GFP2Element & Zero();
    00037
    00038         Integer c1, c2;
    00039 };
    00040
    00041 //! GF(p^2), optimal normal basis
    00042 template <class F>
    00043 class GFP2_ONB : public AbstractRing<GFP2Element>
    00044 {
    00045 public:
    00046         typedef F BaseField;
    00047
    00048         GFP2_ONB(const Integer &p) : modp(p)
    00049         {
    00050                 if (p%3 != 2)
    00051                         throw InvalidArgument("GFP2_ONB: modulus must be equivalent to 2 mod 3");
    00052         }
    00053
    00054         const Integer& GetModulus() const {return modp.GetModulus();}
    00055
    00056         GFP2Element ConvertIn(const Integer &a) const
    00057         {
    00058                 t = modp.Inverse(modp.ConvertIn(a));
    00059                 return GFP2Element(t, t);
    00060         }
    00061
    00062         GFP2Element ConvertIn(const GFP2Element &a) const
    00063                 {return GFP2Element(modp.ConvertIn(a.c1), modp.ConvertIn(a.c2));}
    00064
    00065         GFP2Element ConvertOut(const GFP2Element &a) const
    00066                 {return GFP2Element(modp.ConvertOut(a.c1), modp.ConvertOut(a.c2));}
    00067
    00068         bool Equal(const GFP2Element &a, const GFP2Element &b) const
    00069         {
    00070                 return modp.Equal(a.c1, b.c1) && modp.Equal(a.c2, b.c2);
    00071         }
    00072
    00073         const Element& Identity() const
    00074         {
    00075                 return GFP2Element::Zero();
    00076         }
    00077
    00078         const Element& Add(const Element &a, const Element &b) const
    00079         {
    00080                 result.c1 = modp.Add(a.c1, b.c1);
    00081                 result.c2 = modp.Add(a.c2, b.c2);
    00082                 return result;
    00083         }
    00084
    00085         const Element& Inverse(const Element &a) const
    00086         {
    00087                 result.c1 = modp.Inverse(a.c1);
    00088                 result.c2 = modp.Inverse(a.c2);
    00089                 return result;
    00090         }
    00091
    00092         const Element& Double(const Element &a) const
    00093         {
    00094                 result.c1 = modp.Double(a.c1);
    00095                 result.c2 = modp.Double(a.c2);
    00096                 return result;
    00097         }
    00098
    00099         const Element& Subtract(const Element &a, const Element &b) const
    00100         {
    00101                 result.c1 = modp.Subtract(a.c1, b.c1);
    00102                 result.c2 = modp.Subtract(a.c2, b.c2);
    00103                 return result;
    00104         }
    00105
    00106         Element& Accumulate(Element &a, const Element &b) const
    00107         {
    00108                 modp.Accumulate(a.c1, b.c1);
    00109                 modp.Accumulate(a.c2, b.c2);
    00110                 return a;
    00111         }
    00112
    00113         Element& Reduce(Element &a, const Element &b) const
    00114         {
    00115                 modp.Reduce(a.c1, b.c1);
    00116                 modp.Reduce(a.c2, b.c2);
    00117                 return a;
    00118         }
    00119
    00120         bool IsUnit(const Element &a) const
    00121         {
    00122                 return a.c1.NotZero() || a.c2.NotZero();
    00123         }
    00124
    00125         const Element& MultiplicativeIdentity() const
    00126         {
    00127                 result.c1 = result.c2 = modp.Inverse(modp.MultiplicativeIdentity());
    00128                 return result;
    00129         }
    00130
    00131         const Element& Multiply(const Element &a, const Element &b) const
    00132         {
    00133                 t = modp.Add(a.c1, a.c2);
    00134                 t = modp.Multiply(t, modp.Add(b.c1, b.c2));
    00135                 result.c1 = modp.Multiply(a.c1, b.c1);
    00136                 result.c2 = modp.Multiply(a.c2, b.c2);
    00137                 result.c1.swap(result.c2);
    00138                 modp.Reduce(t, result.c1);
    00139                 modp.Reduce(t, result.c2);
    00140                 modp.Reduce(result.c1, t);
    00141                 modp.Reduce(result.c2, t);
    00142                 return result;
    00143         }
    00144
    00145         const Element& MultiplicativeInverse(const Element &a) const
    00146         {
    00147                 return result = Exponentiate(a, modp.GetModulus()-2);
    00148         }
    00149
    00150         const Element& Square(const Element &a) const
    00151         {
    00152                 const Integer &ac1 = (&a == &result) ? (t = a.c1) : a.c1;
    00153                 result.c1 = modp.Multiply(modp.Subtract(modp.Subtract(a.c2, a.c1), a.c1), a.c2);
    00154                 result.c2 = modp.Multiply(modp.Subtract(modp.Subtract(ac1, a.c2), a.c2), ac1);
    00155                 return result;
    00156         }
    00157
    00158         Element Exponentiate(const Element &a, const Integer &e) const
    00159         {
    00160                 Integer edivp, emodp;
    00161                 Integer::Divide(emodp, edivp, e, modp.GetModulus());
    00162                 Element b = PthPower(a);
    00163                 return AbstractRing<GFP2Element>::CascadeExponentiate(a, emodp, b, edivp);
    00164         }
    00165
    00166         const Element & PthPower(const Element &a) const
    00167         {
    00168                 result = a;
    00169                 result.c1.swap(result.c2);
    00170                 return result;
    00171         }
    00172
    00173         void RaiseToPthPower(Element &a) const
    00174         {
    00175                 a.c1.swap(a.c2);
    00176         }
    00177
    00178         // a^2 - 2a^p
    00179         const Element & SpecialOperation1(const Element &a) const
    00180         {
    00181                 assert(&a != &result);
    00182                 result = Square(a);
    00183                 modp.Reduce(result.c1, a.c2);
    00184                 modp.Reduce(result.c1, a.c2);
    00185                 modp.Reduce(result.c2, a.c1);
    00186                 modp.Reduce(result.c2, a.c1);
    00187                 return result;
    00188         }
    00189
    00190         // x * z - y * z^p
    00191         const Element & SpecialOperation2(const Element &x, const Element &y, const Element &z) const
    00192         {
    00193                 assert(&x != &result && &y != &result && &z != &result);
    00194                 t = modp.Add(x.c2, y.c2);
    00195                 result.c1 = modp.Multiply(z.c1, modp.Subtract(y.c1, t));
    00196                 modp.Accumulate(result.c1, modp.Multiply(z.c2, modp.Subtract(t, x.c1)));
    00197                 t = modp.Add(x.c1, y.c1);
    00198                 result.c2 = modp.Multiply(z.c2, modp.Subtract(y.c2, t));
    00199                 modp.Accumulate(result.c2, modp.Multiply(z.c1, modp.Subtract(t, x.c2)));
    00200                 return result;
    00201         }
    00202
    00203 protected:
    00204         BaseField modp;
    00205         mutable GFP2Element result;
    00206         mutable Integer t;
    00207 };
    00208
    00209 void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits);
    00210
    00211 GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p);
    00212
    00213 NAMESPACE_END
    00214
    00215 #endif