Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | 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 Fri Aug 27 14:07:42 2004 for Crypto++ by doxygen 1.3.8