Crypto++  8.6
Free C++ class library of cryptographic schemes
xtr.cpp
1 // xtr.cpp - originally 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 #if defined(CRYPTOPP_CXX11_STATIC_INIT)
17  static const GFP2Element s_zero;
18  return s_zero;
19 #else
20  return Singleton<GFP2Element>().Ref();
21 #endif
22 }
23 
24 void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits)
25 {
26  CRYPTOPP_ASSERT(qbits > 9); // no primes exist for pbits = 10, qbits = 9
27  CRYPTOPP_ASSERT(pbits > qbits);
28 
29  const Integer minQ = Integer::Power2(qbits - 1);
30  const Integer maxQ = Integer::Power2(qbits) - 1;
31  const Integer minP = Integer::Power2(pbits - 1);
32  const Integer maxP = Integer::Power2(pbits) - 1;
33 
34 top:
35 
36  Integer r1, r2;
37  do
38  {
39  (void)q.Randomize(rng, minQ, maxQ, Integer::PRIME, 7, 12);
40  // Solution always exists because q === 7 mod 12.
41  (void)SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q);
42  // I believe k_i, r1 and r2 are being used slightly different than the
43  // paper's algorithm. I believe it is leading to the failed asserts.
44  // Just make the assert part of the condition.
45  if(!p.Randomize(rng, minP, maxP, Integer::PRIME, CRT(rng.GenerateBit() ?
46  r1 : r2, q, 2, 3, EuclideanMultiplicativeInverse(p, 3)), 3 * q)) { continue; }
47  } while (((p % 3U) != 2) || (((p.Squared() - p + 1) % q).NotZero()));
48 
49  // CRYPTOPP_ASSERT((p % 3U) == 2);
50  // CRYPTOPP_ASSERT(((p.Squared() - p + 1) % q).IsZero());
51 
53  GFP2Element three = gfp2.ConvertIn(3), t;
54 
55  while (true)
56  {
57  g.c1.Randomize(rng, Integer::Zero(), p-1);
58  g.c2.Randomize(rng, Integer::Zero(), p-1);
59  t = XTR_Exponentiate(g, p+1, p);
60  if (t.c1 == t.c2)
61  continue;
62  g = XTR_Exponentiate(g, (p.Squared()-p+1)/q, p);
63  if (g != three)
64  break;
65  }
66 
67  if (XTR_Exponentiate(g, q, p) != three)
68  goto top;
69 
70  // CRYPTOPP_ASSERT(XTR_Exponentiate(g, q, p) == three);
71 }
72 
73 GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p)
74 {
75  unsigned int bitCount = e.BitCount();
76  if (bitCount == 0)
77  return GFP2Element(-3, -3);
78 
79  // find the lowest bit of e that is 1
80  unsigned int lowest1bit;
81  for (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {}
82 
84  GFP2Element c = gfp2.ConvertIn(b);
85  GFP2Element cp = gfp2.PthPower(c);
86  GFP2Element S[5] = {gfp2.ConvertIn(3), c, gfp2.SpecialOperation1(c)};
87 
88  // do all exponents bits except the lowest zeros starting from the top
89  unsigned int i;
90  for (i = e.BitCount() - 1; i>lowest1bit; i--)
91  {
92  if (e.GetBit(i))
93  {
94  gfp2.RaiseToPthPower(S[0]);
95  gfp2.Accumulate(S[0], gfp2.SpecialOperation2(S[2], c, S[1]));
96  S[1] = gfp2.SpecialOperation1(S[1]);
97  S[2] = gfp2.SpecialOperation1(S[2]);
98  S[0].swap(S[1]);
99  }
100  else
101  {
102  gfp2.RaiseToPthPower(S[2]);
103  gfp2.Accumulate(S[2], gfp2.SpecialOperation2(S[0], cp, S[1]));
104  S[1] = gfp2.SpecialOperation1(S[1]);
105  S[0] = gfp2.SpecialOperation1(S[0]);
106  S[2].swap(S[1]);
107  }
108  }
109 
110  // now do the lowest zeros
111  while (i--)
112  S[1] = gfp2.SpecialOperation1(S[1]);
113 
114  return gfp2.ConvertOut(S[1]);
115 }
116 
117 template class AbstractRing<GFP2Element>;
118 template class AbstractGroup<GFP2Element>;
119 
120 NAMESPACE_END
Integer::GetBit
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
GFP2_ONB
GF(p^2), optimal normal basis.
Definition: xtr.h:46
Singleton::Ref
const T & Ref(...) const
Return a reference to the inner Singleton object.
Definition: misc.h:327
Integer::Power2
static Integer Power2(size_t e)
Exponentiates to a power of 2.
AbstractGroup< GFP2Element >
nbtheory.h
Classes and functions for number theoretic operations.
Integer::Squared
Integer Squared() const
Multiply this integer by itself.
Definition: integer.h:633
EuclideanMultiplicativeInverse
Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
Calculate multiplicative inverse.
Definition: nbtheory.h:166
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
CRT
CRYPTOPP_DLL Integer CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
Chinese Remainder Theorem.
xtr.h
The XTR public key system.
Singleton
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:306
modarith.h
Class file for performing modular arithmetic.
pch.h
Precompiled header file.
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1434
RandomNumberGenerator::GenerateBit
virtual unsigned int GenerateBit()
Generate new random bit and return it.
GFP2Element
an element of GF(p^2)
Definition: xtr.h:16
Integer::Zero
static const Integer & Zero()
Integer representing 0.
Integer::Randomize
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Integer::BitCount
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
algebra.h
Classes for performing mathematics over different fields.
CryptoPP
Crypto++ library namespace.
SolveModularQuadraticEquation
CRYPTOPP_DLL bool SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
Solve a Modular Quadratic Equation.
AbstractRing< GFP2Element >
Integer::PRIME
@ PRIME
a number which is probabilistically prime
Definition: integer.h:95
integer.h
Multiple precision integer with arithmetic operations.
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:49