Crypto++
xtr.cpp
1 // cryptlib.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 #include "xtr.h"
5 #include "nbtheory.h"
6 
7 #include "algebra.cpp"
8 
9 NAMESPACE_BEGIN(CryptoPP)
10 
11 const GFP2Element & GFP2Element::Zero()
12 {
13  return Singleton<GFP2Element>().Ref();
14 }
15 
16 void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits)
17 {
18  assert(qbits > 9); // no primes exist for pbits = 10, qbits = 9
19  assert(pbits > qbits);
20 
21  const Integer minQ = Integer::Power2(qbits - 1);
22  const Integer maxQ = Integer::Power2(qbits) - 1;
23  const Integer minP = Integer::Power2(pbits - 1);
24  const Integer maxP = Integer::Power2(pbits) - 1;
25 
26  Integer r1, r2;
27  do
28  {
29  bool qFound = q.Randomize(rng, minQ, maxQ, Integer::PRIME, 7, 12);
30  assert(qFound);
31  bool solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q);
32  assert(solutionsExist);
33  } while (!p.Randomize(rng, minP, maxP, Integer::PRIME, CRT(rng.GenerateBit()?r1:r2, q, 2, 3, EuclideanMultiplicativeInverse(p, 3)), 3*q));
34  assert(((p.Squared() - p + 1) % q).IsZero());
35 
37  GFP2Element three = gfp2.ConvertIn(3), t;
38 
39  while (true)
40  {
41  g.c1.Randomize(rng, Integer::Zero(), p-1);
42  g.c2.Randomize(rng, Integer::Zero(), p-1);
43  t = XTR_Exponentiate(g, p+1, p);
44  if (t.c1 == t.c2)
45  continue;
46  g = XTR_Exponentiate(g, (p.Squared()-p+1)/q, p);
47  if (g != three)
48  break;
49  }
50  assert(XTR_Exponentiate(g, q, p) == three);
51 }
52 
53 GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p)
54 {
55  unsigned int bitCount = e.BitCount();
56  if (bitCount == 0)
57  return GFP2Element(-3, -3);
58 
59  // find the lowest bit of e that is 1
60  unsigned int lowest1bit;
61  for (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {}
62 
64  GFP2Element c = gfp2.ConvertIn(b);
65  GFP2Element cp = gfp2.PthPower(c);
66  GFP2Element S[5] = {gfp2.ConvertIn(3), c, gfp2.SpecialOperation1(c)};
67 
68  // do all exponents bits except the lowest zeros starting from the top
69  unsigned int i;
70  for (i = e.BitCount() - 1; i>lowest1bit; i--)
71  {
72  if (e.GetBit(i))
73  {
74  gfp2.RaiseToPthPower(S[0]);
75  gfp2.Accumulate(S[0], gfp2.SpecialOperation2(S[2], c, S[1]));
76  S[1] = gfp2.SpecialOperation1(S[1]);
77  S[2] = gfp2.SpecialOperation1(S[2]);
78  S[0].swap(S[1]);
79  }
80  else
81  {
82  gfp2.RaiseToPthPower(S[2]);
83  gfp2.Accumulate(S[2], gfp2.SpecialOperation2(S[0], cp, S[1]));
84  S[1] = gfp2.SpecialOperation1(S[1]);
85  S[0] = gfp2.SpecialOperation1(S[0]);
86  S[2].swap(S[1]);
87  }
88  }
89 
90  // now do the lowest zeros
91  while (i--)
92  S[1] = gfp2.SpecialOperation1(S[1]);
93 
94  return gfp2.ConvertOut(S[1]);
95 }
96 
97 template class AbstractRing<GFP2Element>;
98 template class AbstractGroup<GFP2Element>;
99 
100 NAMESPACE_END
bool GetBit(size_t i) const
return the i-th bit, i=0 being the least significant bit
Definition: integer.cpp:2894
interface for random number generators
Definition: cryptlib.h:669
unsigned int BitCount() const
number of significant bits = floor(log2(abs(*this))) + 1
Definition: integer.cpp:3054
an element of GF(p^2)
Definition: xtr.h:13
"The XTR public key system" by Arjen K.
static Integer Power2(size_t e)
return the integer 2**e
Definition: integer.cpp:2846
multiple precision integer and basic arithmetics
Definition: integer.h:26
virtual unsigned int GenerateBit()
generate new random bit and return it
Definition: cryptlib.cpp:236
static const Integer & Zero()
avoid calling constructors for these frequently used integers
Definition: integer.cpp:2862
GF(p^2), optimal normal basis.
Definition: xtr.h:43