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