1// cryptlib.cpp - written and placed in the public domain by Wei Dai 2 3#include "pch.h" 4#include "xtr.h" 5#include "nbtheory.h" 6 7#include "algebra.cpp" 8 9NAMESPACE_BEGIN(CryptoPP) 10 11const GFP2Element & GFP2Element::Zero() 12{ 13 return Singleton<GFP2Element>().Ref(); 14} 15 16void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits) 17{ 18 assert(qbits > 9); // no primes exist for pbits = 10, qbits = 9 19 assert(pbits > qbits); 20 21 const Integer minQ = Integer::Power2(qbits - 1); 22 const Integer maxQ = Integer::Power2(qbits) - 1; 23 const Integer minP = Integer::Power2(pbits - 1); 24 const Integer maxP = Integer::Power2(pbits) - 1; 25 26 Integer r1, r2; 27 do 28 { 29 bool qFound = q.Randomize(rng, minQ, maxQ, Integer::PRIME, 7, 12); 30 assert(qFound); 31 bool solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q); 32 assert(solutionsExist); 33 } while (!p.Randomize(rng, minP, maxP, Integer::PRIME, CRT(rng.GenerateBit()?r1:r2, q, 2, 3, EuclideanMultiplicativeInverse(p, 3)), 3*q)); 34 assert(((p.Squared() - p + 1) % q).IsZero()); 35 36 GFP2_ONB<ModularArithmetic> gfp2(p); 37 GFP2Element three = gfp2.ConvertIn(3), t; 38 39 while (true) 40 { 41 g.c1.Randomize(rng, Integer::Zero(), p-1); 42 g.c2.Randomize(rng, Integer::Zero(), p-1); 43 t = XTR_Exponentiate(g, p+1, p); 44 if (t.c1 == t.c2) 45 continue; 46 g = XTR_Exponentiate(g, (p.Squared()-p+1)/q, p); 47 if (g != three) 48 break; 49 } 50 assert(XTR_Exponentiate(g, q, p) == three); 51} 52 53GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p) 54{ 55 unsigned int bitCount = e.BitCount(); 56 if (bitCount == 0) 57 return GFP2Element(-3, -3); 58 59 // find the lowest bit of e that is 1 60 unsigned int lowest1bit; 61 for (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {} 62 63 GFP2_ONB<MontgomeryRepresentation> gfp2(p); 64 GFP2Element c = gfp2.ConvertIn(b); 65 GFP2Element cp = gfp2.PthPower(c); 66 GFP2Element S[5] = {gfp2.ConvertIn(3), c, gfp2.SpecialOperation1(c)}; 67 68 // do all exponents bits except the lowest zeros starting from the top 69 unsigned int i; 70 for (i = e.BitCount() - 1; i>lowest1bit; i--) 71 { 72 if (e.GetBit(i)) 73 { 74 gfp2.RaiseToPthPower(S[0]); 75 gfp2.Accumulate(S[0], gfp2.SpecialOperation2(S[2], c, S[1])); 76 S[1] = gfp2.SpecialOperation1(S[1]); 77 S[2] = gfp2.SpecialOperation1(S[2]); 78 S[0].swap(S[1]); 79 } 80 else 81 { 82 gfp2.RaiseToPthPower(S[2]); 83 gfp2.Accumulate(S[2], gfp2.SpecialOperation2(S[0], cp, S[1])); 84 S[1] = gfp2.SpecialOperation1(S[1]); 85 S[0] = gfp2.SpecialOperation1(S[0]); 86 S[2].swap(S[1]); 87 } 88 } 89 90 // now do the lowest zeros 91 while (i--) 92 S[1] = gfp2.SpecialOperation1(S[1]); 93 94 return gfp2.ConvertOut(S[1]); 95} 96 97template class AbstractRing<GFP2Element>; 98template class AbstractGroup<GFP2Element>; 99 100NAMESPACE_END 101