xtr.cpp
// xtr.cpp - written and placed in the public domain by Wei Dai
#include "pch.h"
#include "xtr.h"
#include "nbtheory.h"
#include "integer.h"
#include "algebra.h"
#include "modarith.h"
#include "algebra.cpp"
NAMESPACE_BEGIN(CryptoPP)
const GFP2Element & GFP2Element::Zero()
{
return Singleton<GFP2Element>().Ref();
}
void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits)
{
assert(qbits > 9); // no primes exist for pbits = 10, qbits = 9
assert(pbits > qbits);
const Integer minQ = Integer::Power2(qbits - 1);
const Integer maxQ = Integer::Power2(qbits) - 1;
const Integer minP = Integer::Power2(pbits - 1);
const Integer maxP = Integer::Power2(pbits) - 1;
Integer r1, r2;
do
{
bool qFound = q.Randomize(rng, minQ, maxQ, Integer::PRIME, 7, 12);
CRYPTOPP_UNUSED(qFound); assert(qFound);
bool solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q);
CRYPTOPP_UNUSED(solutionsExist); assert(solutionsExist);
} while (!p.Randomize(rng, minP, maxP, Integer::PRIME, CRT(rng.GenerateBit()?r1:r2, q, 2, 3, EuclideanMultiplicativeInverse(p, 3)), 3*q));
assert(((p.Squared() - p + 1) % q).IsZero());
GFP2_ONB<ModularArithmetic> gfp2(p);
GFP2Element three = gfp2.ConvertIn(3), t;
while (true)
{
g.c1.Randomize(rng, Integer::Zero(), p-1);
g.c2.Randomize(rng, Integer::Zero(), p-1);
t = XTR_Exponentiate(g, p+1, p);
if (t.c1 == t.c2)
continue;
g = XTR_Exponentiate(g, (p.Squared()-p+1)/q, p);
if (g != three)
break;
}
assert(XTR_Exponentiate(g, q, p) == three);
}
GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p)
{
unsigned int bitCount = e.BitCount();
if (bitCount == 0)
return GFP2Element(-3, -3);
// find the lowest bit of e that is 1
unsigned int lowest1bit;
for (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {}
GFP2_ONB<MontgomeryRepresentation> gfp2(p);
GFP2Element c = gfp2.ConvertIn(b);
GFP2Element cp = gfp2.PthPower(c);
GFP2Element S[5] = {gfp2.ConvertIn(3), c, gfp2.SpecialOperation1(c)};
// do all exponents bits except the lowest zeros starting from the top
unsigned int i;
for (i = e.BitCount() - 1; i>lowest1bit; i--)
{
if (e.GetBit(i))
{
gfp2.RaiseToPthPower(S[0]);
gfp2.Accumulate(S[0], gfp2.SpecialOperation2(S[2], c, S[1]));
S[1] = gfp2.SpecialOperation1(S[1]);
S[2] = gfp2.SpecialOperation1(S[2]);
S[0].swap(S[1]);
}
else
{
gfp2.RaiseToPthPower(S[2]);
gfp2.Accumulate(S[2], gfp2.SpecialOperation2(S[0], cp, S[1]));
S[1] = gfp2.SpecialOperation1(S[1]);
S[0] = gfp2.SpecialOperation1(S[0]);
S[2].swap(S[1]);
}
}
// now do the lowest zeros
while (i--)
S[1] = gfp2.SpecialOperation1(S[1]);
return gfp2.ConvertOut(S[1]);
}
template class AbstractRing<GFP2Element>;
template class AbstractGroup<GFP2Element>;
NAMESPACE_END
GFP2_ONB
GF(p^2), optimal normal basis.
Definition: xtr.h:48
Singleton::Ref
const T & Ref(...) const
Return a reference to the inner Singleton object.
Definition: misc.h:308
AbstractGroup< GFP2Element >
nbtheory.h
Classes and functions for number theoretic operations.
Integer::Squared
Integer Squared() const
Definition: integer.h:500
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:19
xtr.h
The XTR public key system.
Singleton
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:264
modarith.h
Class file for performing modular arithmetic.
Integer::Power2
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:2995
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1186
GFP2Element
an element of GF(p^2)
Definition: xtr.h:17
RandomNumberGenerator::GenerateBit
virtual unsigned int GenerateBit()
Generate new random bit and return it.
Definition: cryptlib.cpp:290
Integer::Randomize
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Definition: integer.cpp:3439
algebra.h
Classes for performing mathematics over different fields.
Integer::Zero
static const Integer & Zero()
Integer representing 0.
Definition: integer.cpp:3011
CryptoPP
Crypto++ library namespace.
AbstractRing< GFP2Element >
Integer::PRIME
@ PRIME
a number which is probabilistically prime
Definition: integer.h:91
integer.h
Multiple precision integer with arithmetic operations.
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:45