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