Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

# xtr.cpp

    00001 // cryptlib.cpp - written and placed in the public domain by Wei Dai
    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 const GFP2Element & GFP2Element::Zero()
    00012 {
    00013         return Singleton<GFP2Element>().Ref();
    00014 }
    00015
    00016 void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits)
    00017 {
    00018         assert(qbits > 9);      // no primes exist for pbits = 10, qbits = 9
    00019         assert(pbits > qbits);
    00020
    00021         const Integer minQ = Integer::Power2(qbits - 1);
    00022         const Integer maxQ = Integer::Power2(qbits) - 1;
    00023         const Integer minP = Integer::Power2(pbits - 1);
    00024         const Integer maxP = Integer::Power2(pbits) - 1;
    00025
    00026         Integer r1, r2;
    00027         do
    00028         {
    00029                 bool qFound = q.Randomize(rng, minQ, maxQ, Integer::PRIME, 7, 12);
    00030                 assert(qFound);
    00031                 bool solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q);
    00032                 assert(solutionsExist);
    00033         } while (!p.Randomize(rng, minP, maxP, Integer::PRIME, CRT(rng.GenerateBit()?r1:r2, q, 2, 3), 3*q));
    00034         assert(((p.Squared() - p + 1) % q).IsZero());
    00035
    00036         GFP2_ONB<ModularArithmetic> gfp2(p);
    00037         GFP2Element three = gfp2.ConvertIn(3), t;
    00038
    00039         while (true)
    00040         {
    00041                 g.c1.Randomize(rng, Integer::Zero(), p-1);
    00042                 g.c2.Randomize(rng, Integer::Zero(), p-1);
    00043                 t = XTR_Exponentiate(g, p+1, p);
    00044                 if (t.c1 == t.c2)
    00045                         continue;
    00046                 g = XTR_Exponentiate(g, (p.Squared()-p+1)/q, p);
    00047                 if (g != three)
    00048                         break;
    00049         }
    00050         assert(XTR_Exponentiate(g, q, p) == three);
    00051 }
    00052
    00053 GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p)
    00054 {
    00055         unsigned int bitCount = e.BitCount();
    00056         if (bitCount == 0)
    00057                 return GFP2Element(-3, -3);
    00058
    00059         // find the lowest bit of e that is 1
    00060         unsigned int lowest1bit;
    00061         for (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {}
    00062
    00063         GFP2_ONB<MontgomeryRepresentation> gfp2(p);
    00064         GFP2Element c = gfp2.ConvertIn(b);
    00065         GFP2Element cp = gfp2.PthPower(c);
    00066         GFP2Element S[5] = {gfp2.ConvertIn(3), c, gfp2.SpecialOperation1(c)};
    00067
    00068         // do all exponents bits except the lowest zeros starting from the top
    00069         unsigned int i;
    00070         for (i = e.BitCount() - 1; i>lowest1bit; i--)
    00071         {
    00072                 if (e.GetBit(i))
    00073                 {
    00074                         gfp2.RaiseToPthPower(S[0]);
    00075                         gfp2.Accumulate(S[0], gfp2.SpecialOperation2(S[2], c, S[1]));
    00076                         S[1] = gfp2.SpecialOperation1(S[1]);
    00077                         S[2] = gfp2.SpecialOperation1(S[2]);
    00078                         S[0].swap(S[1]);
    00079                 }
    00080                 else
    00081                 {
    00082                         gfp2.RaiseToPthPower(S[2]);
    00083                         gfp2.Accumulate(S[2], gfp2.SpecialOperation2(S[0], cp, S[1]));
    00084                         S[1] = gfp2.SpecialOperation1(S[1]);
    00085                         S[0] = gfp2.SpecialOperation1(S[0]);
    00086                         S[2].swap(S[1]);
    00087                 }
    00088         }
    00089
    00090         // now do the lowest zeros
    00091         while (i--)
    00092                 S[1] = gfp2.SpecialOperation1(S[1]);
    00093
    00094         return gfp2.ConvertOut(S[1]);
    00095 }
    00096
    00097 template class AbstractRing<GFP2Element>;
    00098 template class AbstractGroup<GFP2Element>;
    00099
    00100 NAMESPACE_END