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 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);      // no primes exist for pbits = 10, 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         // find the lowest bit of e that is 1
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         // do all exponents bits except the lowest zeros starting from the top
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         // now do the lowest zeros
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

Generated on Sun Mar 14 20:44:29 2004 for Crypto++ by doxygen 1.3.6-20040222