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 Wed Jul 28 08:07:09 2004 for Crypto++ by doxygen 1.3.7