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