1#ifndef CRYPTOPP_XTR_H 2#define CRYPTOPP_XTR_H 3 4/** \file 5 "The XTR public key system" by Arjen K. Lenstra and Eric R. Verheul 6*/ 7 8#include "modarith.h" 9 10NAMESPACE_BEGIN(CryptoPP) 11 12//! an element of GF(p^2) 13class GFP2Element 14{ 15public: 16 GFP2Element() {} 17 GFP2Element(const Integer &c1, const Integer &c2) : c1(c1), c2(c2) {} 18 GFP2Element(const byte *encodedElement, unsigned int size) 19 : c1(encodedElement, size/2), c2(encodedElement+size/2, size/2) {} 20 21 void Encode(byte *encodedElement, unsigned int size) 22 { 23 c1.Encode(encodedElement, size/2); 24 c2.Encode(encodedElement+size/2, size/2); 25 } 26 27 bool operator==(const GFP2Element &rhs) const {return c1 == rhs.c1 && c2 == rhs.c2;} 28 bool operator!=(const GFP2Element &rhs) const {return !operator==(rhs);} 29 30 void swap(GFP2Element &a) 31 { 32 c1.swap(a.c1); 33 c2.swap(a.c2); 34 } 35 36 static const GFP2Element & Zero(); 37 38 Integer c1, c2; 39}; 40 41//! GF(p^2), optimal normal basis 42template <class F> 43class GFP2_ONB : public AbstractRing<GFP2Element> 44{ 45public: 46 typedef F BaseField; 47 48 GFP2_ONB(const Integer &p) : modp(p) 49 { 50 if (p%3 != 2) 51 throw InvalidArgument("GFP2_ONB: modulus must be equivalent to 2 mod 3"); 52 } 53 54 const Integer& GetModulus() const {return modp.GetModulus();} 55 56 GFP2Element ConvertIn(const Integer &a) const 57 { 58 t = modp.Inverse(modp.ConvertIn(a)); 59 return GFP2Element(t, t); 60 } 61 62 GFP2Element ConvertIn(const GFP2Element &a) const 63 {return GFP2Element(modp.ConvertIn(a.c1), modp.ConvertIn(a.c2));} 64 65 GFP2Element ConvertOut(const GFP2Element &a) const 66 {return GFP2Element(modp.ConvertOut(a.c1), modp.ConvertOut(a.c2));} 67 68 bool Equal(const GFP2Element &a, const GFP2Element &b) const 69 { 70 return modp.Equal(a.c1, b.c1) && modp.Equal(a.c2, b.c2); 71 } 72 73 const Element& Identity() const 74 { 75 return GFP2Element::Zero(); 76 } 77 78 const Element& Add(const Element &a, const Element &b) const 79 { 80 result.c1 = modp.Add(a.c1, b.c1); 81 result.c2 = modp.Add(a.c2, b.c2); 82 return result; 83 } 84 85 const Element& Inverse(const Element &a) const 86 { 87 result.c1 = modp.Inverse(a.c1); 88 result.c2 = modp.Inverse(a.c2); 89 return result; 90 } 91 92 const Element& Double(const Element &a) const 93 { 94 result.c1 = modp.Double(a.c1); 95 result.c2 = modp.Double(a.c2); 96 return result; 97 } 98 99 const Element& Subtract(const Element &a, const Element &b) const 100 { 101 result.c1 = modp.Subtract(a.c1, b.c1); 102 result.c2 = modp.Subtract(a.c2, b.c2); 103 return result; 104 } 105 106 Element& Accumulate(Element &a, const Element &b) const 107 { 108 modp.Accumulate(a.c1, b.c1); 109 modp.Accumulate(a.c2, b.c2); 110 return a; 111 } 112 113 Element& Reduce(Element &a, const Element &b) const 114 { 115 modp.Reduce(a.c1, b.c1); 116 modp.Reduce(a.c2, b.c2); 117 return a; 118 } 119 120 bool IsUnit(const Element &a) const 121 { 122 return a.c1.NotZero() || a.c2.NotZero(); 123 } 124 125 const Element& MultiplicativeIdentity() const 126 { 127 result.c1 = result.c2 = modp.Inverse(modp.MultiplicativeIdentity()); 128 return result; 129 } 130 131 const Element& Multiply(const Element &a, const Element &b) const 132 { 133 t = modp.Add(a.c1, a.c2); 134 t = modp.Multiply(t, modp.Add(b.c1, b.c2)); 135 result.c1 = modp.Multiply(a.c1, b.c1); 136 result.c2 = modp.Multiply(a.c2, b.c2); 137 result.c1.swap(result.c2); 138 modp.Reduce(t, result.c1); 139 modp.Reduce(t, result.c2); 140 modp.Reduce(result.c1, t); 141 modp.Reduce(result.c2, t); 142 return result; 143 } 144 145 const Element& MultiplicativeInverse(const Element &a) const 146 { 147 return result = Exponentiate(a, modp.GetModulus()-2); 148 } 149 150 const Element& Square(const Element &a) const 151 { 152 const Integer &ac1 = (&a == &result) ? (t = a.c1) : a.c1; 153 result.c1 = modp.Multiply(modp.Subtract(modp.Subtract(a.c2, a.c1), a.c1), a.c2); 154 result.c2 = modp.Multiply(modp.Subtract(modp.Subtract(ac1, a.c2), a.c2), ac1); 155 return result; 156 } 157 158 Element Exponentiate(const Element &a, const Integer &e) const 159 { 160 Integer edivp, emodp; 161 Integer::Divide(emodp, edivp, e, modp.GetModulus()); 162 Element b = PthPower(a); 163 return AbstractRing<GFP2Element>::CascadeExponentiate(a, emodp, b, edivp); 164 } 165 166 const Element & PthPower(const Element &a) const 167 { 168 result = a; 169 result.c1.swap(result.c2); 170 return result; 171 } 172 173 void RaiseToPthPower(Element &a) const 174 { 175 a.c1.swap(a.c2); 176 } 177 178 // a^2 - 2a^p 179 const Element & SpecialOperation1(const Element &a) const 180 { 181 assert(&a != &result); 182 result = Square(a); 183 modp.Reduce(result.c1, a.c2); 184 modp.Reduce(result.c1, a.c2); 185 modp.Reduce(result.c2, a.c1); 186 modp.Reduce(result.c2, a.c1); 187 return result; 188 } 189 190 // x * z - y * z^p 191 const Element & SpecialOperation2(const Element &x, const Element &y, const Element &z) const 192 { 193 assert(&x != &result && &y != &result && &z != &result); 194 t = modp.Add(x.c2, y.c2); 195 result.c1 = modp.Multiply(z.c1, modp.Subtract(y.c1, t)); 196 modp.Accumulate(result.c1, modp.Multiply(z.c2, modp.Subtract(t, x.c1))); 197 t = modp.Add(x.c1, y.c1); 198 result.c2 = modp.Multiply(z.c2, modp.Subtract(y.c2, t)); 199 modp.Accumulate(result.c2, modp.Multiply(z.c1, modp.Subtract(t, x.c2))); 200 return result; 201 } 202 203protected: 204 BaseField modp; 205 mutable GFP2Element result; 206 mutable Integer t; 207}; 208 209void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits); 210 211GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p); 212 213NAMESPACE_END 214 215#endif 216