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
9NAMESPACE_BEGIN(CryptoPP)
10
11const GFP2Element & GFP2Element::Zero()
12{
13	return Singleton<GFP2Element>().Ref();
14}
15
16void 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
36	GFP2_ONB<ModularArithmetic> gfp2(p);
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
53GFP2Element 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
63	GFP2_ONB<MontgomeryRepresentation> gfp2(p);
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
97template class AbstractRing<GFP2Element>;
98template class AbstractGroup<GFP2Element>;
99
100NAMESPACE_END
101