00001
00002
00003
#include "pch.h"
00004
#include "xtr.h"
00005
#include "nbtheory.h"
00006
00007
#include "algebra.cpp"
00008
00009 NAMESPACE_BEGIN(CryptoPP)
00010
00011
GFP2Element &
GFP2Element::Zero()
00012 {
00013
static GFP2Element zero;
00014
return zero;
00015 }
00016
00017
void XTR_FindPrimesAndGenerator(
RandomNumberGenerator &rng,
Integer &p,
Integer &q,
GFP2Element &g,
unsigned int pbits,
unsigned int qbits)
00018 {
00019 assert(qbits > 9);
00020 assert(pbits > qbits);
00021
00022
const Integer minQ =
Integer::Power2(qbits - 1);
00023
const Integer maxQ =
Integer::Power2(qbits) - 1;
00024
const Integer minP =
Integer::Power2(pbits - 1);
00025
const Integer maxP =
Integer::Power2(pbits) - 1;
00026
00027
Integer r1, r2;
00028
do
00029 {
00030
bool qFound = q.
Randomize(rng, minQ, maxQ, Integer::PRIME, 7, 12);
00031 assert(qFound);
00032
bool solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q);
00033 assert(solutionsExist);
00034 }
while (!p.
Randomize(rng, minP, maxP, Integer::PRIME, CRT(rng.
GenerateBit()?r1:r2, q, 2, 3), 3*q));
00035 assert(((p.
Squared() - p + 1) % q).IsZero());
00036
00037
GFP2_ONB<ModularArithmetic> gfp2(p);
00038
GFP2Element three = gfp2.
ConvertIn(3), t;
00039
00040
while (
true)
00041 {
00042 g.c1.Randomize(rng, Integer::Zero(), p-1);
00043 g.c2.Randomize(rng, Integer::Zero(), p-1);
00044 t = XTR_Exponentiate(g, p+1, p);
00045
if (t.c1 == t.c2)
00046
continue;
00047 g = XTR_Exponentiate(g, (p.
Squared()-p+1)/q, p);
00048
if (g != three)
00049
break;
00050 }
00051 assert(XTR_Exponentiate(g, q, p) == three);
00052 }
00053
00054
GFP2Element XTR_Exponentiate(
const GFP2Element &b,
const Integer &e,
const Integer &p)
00055 {
00056
unsigned int bitCount = e.BitCount();
00057
if (bitCount == 0)
00058
return GFP2Element(-3, -3);
00059
00060
00061
unsigned int lowest1bit;
00062
for (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {}
00063
00064
GFP2_ONB<MontgomeryRepresentation> gfp2(p);
00065
GFP2Element c = gfp2.
ConvertIn(b);
00066
GFP2Element cp = gfp2.
PthPower(c);
00067
GFP2Element S[5] = {gfp2.
ConvertIn(3), c, gfp2.
SpecialOperation1(c)};
00068
00069
00070
unsigned int i;
00071
for (i = e.BitCount() - 1; i>lowest1bit; i--)
00072 {
00073
if (e.GetBit(i))
00074 {
00075 gfp2.
RaiseToPthPower(S[0]);
00076 gfp2.
Accumulate(S[0], gfp2.
SpecialOperation2(S[2], c, S[1]));
00077 S[1] = gfp2.
SpecialOperation1(S[1]);
00078 S[2] = gfp2.
SpecialOperation1(S[2]);
00079 S[0].swap(S[1]);
00080 }
00081
else
00082 {
00083 gfp2.
RaiseToPthPower(S[2]);
00084 gfp2.
Accumulate(S[2], gfp2.
SpecialOperation2(S[0], cp, S[1]));
00085 S[1] = gfp2.
SpecialOperation1(S[1]);
00086 S[0] = gfp2.
SpecialOperation1(S[0]);
00087 S[2].swap(S[1]);
00088 }
00089 }
00090
00091
00092
while (i--)
00093 S[1] = gfp2.
SpecialOperation1(S[1]);
00094
00095
return gfp2.
ConvertOut(S[1]);
00096 }
00097
00098
template class AbstractRing<GFP2Element>;
00099
template class AbstractGroup<GFP2Element>;
00100
00101 NAMESPACE_END