Crypto++  5.6.3
Free C++ class library of cryptographic schemes
xtr.cpp
1 // xtr.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 
5 #include "xtr.h"
6 #include "nbtheory.h"
7 #include "integer.h"
8 #include "algebra.h"
9 #include "modarith.h"
10 #include "algebra.cpp"
11 
12 NAMESPACE_BEGIN(CryptoPP)
13 
14 const GFP2Element & GFP2Element::Zero()
15 {
16  return Singleton<GFP2Element>().Ref();
17 }
18 
19 void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits)
20 {
21  assert(qbits > 9); // no primes exist for pbits = 10, qbits = 9
22  assert(pbits > qbits);
23 
24  const Integer minQ = Integer::Power2(qbits - 1);
25  const Integer maxQ = Integer::Power2(qbits) - 1;
26  const Integer minP = Integer::Power2(pbits - 1);
27  const Integer maxP = Integer::Power2(pbits) - 1;
28 
29  Integer r1, r2;
30  do
31  {
32  bool qFound = q.Randomize(rng, minQ, maxQ, Integer::PRIME, 7, 12);
33  CRYPTOPP_UNUSED(qFound); assert(qFound);
34  bool solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q);
35  CRYPTOPP_UNUSED(solutionsExist); assert(solutionsExist);
36  } while (!p.Randomize(rng, minP, maxP, Integer::PRIME, CRT(rng.GenerateBit()?r1:r2, q, 2, 3, EuclideanMultiplicativeInverse(p, 3)), 3*q));
37  assert(((p.Squared() - p + 1) % q).IsZero());
38 
40  GFP2Element three = gfp2.ConvertIn(3), t;
41 
42  while (true)
43  {
44  g.c1.Randomize(rng, Integer::Zero(), p-1);
45  g.c2.Randomize(rng, Integer::Zero(), p-1);
46  t = XTR_Exponentiate(g, p+1, p);
47  if (t.c1 == t.c2)
48  continue;
49  g = XTR_Exponentiate(g, (p.Squared()-p+1)/q, p);
50  if (g != three)
51  break;
52  }
53  assert(XTR_Exponentiate(g, q, p) == three);
54 }
55 
56 GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p)
57 {
58  unsigned int bitCount = e.BitCount();
59  if (bitCount == 0)
60  return GFP2Element(-3, -3);
61 
62  // find the lowest bit of e that is 1
63  unsigned int lowest1bit;
64  for (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {}
65 
67  GFP2Element c = gfp2.ConvertIn(b);
68  GFP2Element cp = gfp2.PthPower(c);
69  GFP2Element S[5] = {gfp2.ConvertIn(3), c, gfp2.SpecialOperation1(c)};
70 
71  // do all exponents bits except the lowest zeros starting from the top
72  unsigned int i;
73  for (i = e.BitCount() - 1; i>lowest1bit; i--)
74  {
75  if (e.GetBit(i))
76  {
77  gfp2.RaiseToPthPower(S[0]);
78  gfp2.Accumulate(S[0], gfp2.SpecialOperation2(S[2], c, S[1]));
79  S[1] = gfp2.SpecialOperation1(S[1]);
80  S[2] = gfp2.SpecialOperation1(S[2]);
81  S[0].swap(S[1]);
82  }
83  else
84  {
85  gfp2.RaiseToPthPower(S[2]);
86  gfp2.Accumulate(S[2], gfp2.SpecialOperation2(S[0], cp, S[1]));
87  S[1] = gfp2.SpecialOperation1(S[1]);
88  S[0] = gfp2.SpecialOperation1(S[0]);
89  S[2].swap(S[1]);
90  }
91  }
92 
93  // now do the lowest zeros
94  while (i--)
95  S[1] = gfp2.SpecialOperation1(S[1]);
96 
97  return gfp2.ConvertOut(S[1]);
98 }
99 
100 template class AbstractRing<GFP2Element>;
101 template class AbstractGroup<GFP2Element>;
102 
103 NAMESPACE_END
a number which is probabilistically prime
Definition: integer.h:77
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:238
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
Definition: integer.cpp:2971
Interface for random number generators.
Definition: cryptlib.h:1176
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Definition: integer.cpp:3355
Classes for performing mathematics over different fields.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3205
an element of GF(p^2)
Definition: xtr.h:17
Integer Squared() const
Definition: integer.h:482
The XTR public key system.
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:2923
Multiple precision integer with arithmetic operations.
Definition: integer.h:31
Classes and functions for number theoretic operations.
virtual unsigned int GenerateBit()
Generate new random bit and return it.
Definition: cryptlib.cpp:289
static const Integer & Zero()
Integer representing 0.
Definition: integer.cpp:2939
Class file for performing modular arithmetic.
Crypto++ library namespace.
GF(p^2), optimal normal basis.
Definition: xtr.h:48
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