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