• Main Page
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

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

Generated on Sun Jul 25 2010 14:44:11 for Crypto++ by  doxygen 1.7.1