Crypto++
xtr.h
Go to the documentation of this file.
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 
10 NAMESPACE_BEGIN(CryptoPP)
11 
12 //! an element of GF(p^2)
14 {
15 public:
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
42 template <class F>
43 class GFP2_ONB : public AbstractRing<GFP2Element>
44 {
45 public:
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 
203 protected:
204  BaseField modp;
205  mutable GFP2Element result;
206  mutable Integer t;
207 };
208 
209 void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits);
210 
211 GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p);
212 
213 NAMESPACE_END
214 
215 #endif
exception thrown when an invalid argument is detected
Definition: cryptlib.h:144
static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d)
calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
Square
Definition: square.h:19
interface for random number generators
Definition: cryptlib.h:668
Abstract Ring.
Definition: algebra.h:44
an element of GF(p^2)
Definition: xtr.h:13
multiple precision integer and basic arithmetics
Definition: integer.h:26
void Encode(byte *output, size_t outputLen, Signedness=UNSIGNED) const
encode in big-endian format
GF(p^2), optimal normal basis.
Definition: xtr.h:43