## File: xtr.cpp

package info (click to toggle)
libcrypto++ 5.6.4-8
 `123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103` ``````// xtr.cpp - written and placed in the public domain by Wei Dai #include "pch.h" #include "xtr.h" #include "nbtheory.h" #include "integer.h" #include "algebra.h" #include "modarith.h" #include "algebra.cpp" NAMESPACE_BEGIN(CryptoPP) const GFP2Element & GFP2Element::Zero() { return Singleton().Ref(); } void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits) { assert(qbits > 9); // no primes exist for pbits = 10, qbits = 9 assert(pbits > qbits); const Integer minQ = Integer::Power2(qbits - 1); const Integer maxQ = Integer::Power2(qbits) - 1; const Integer minP = Integer::Power2(pbits - 1); const Integer maxP = Integer::Power2(pbits) - 1; Integer r1, r2; do { bool qFound = q.Randomize(rng, minQ, maxQ, Integer::PRIME, 7, 12); CRYPTOPP_UNUSED(qFound); assert(qFound); bool solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q); CRYPTOPP_UNUSED(solutionsExist); assert(solutionsExist); } while (!p.Randomize(rng, minP, maxP, Integer::PRIME, CRT(rng.GenerateBit()?r1:r2, q, 2, 3, EuclideanMultiplicativeInverse(p, 3)), 3*q)); assert(((p.Squared() - p + 1) % q).IsZero()); GFP2_ONB gfp2(p); GFP2Element three = gfp2.ConvertIn(3), t; while (true) { g.c1.Randomize(rng, Integer::Zero(), p-1); g.c2.Randomize(rng, Integer::Zero(), p-1); t = XTR_Exponentiate(g, p+1, p); if (t.c1 == t.c2) continue; g = XTR_Exponentiate(g, (p.Squared()-p+1)/q, p); if (g != three) break; } assert(XTR_Exponentiate(g, q, p) == three); } GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p) { unsigned int bitCount = e.BitCount(); if (bitCount == 0) return GFP2Element(-3, -3); // find the lowest bit of e that is 1 unsigned int lowest1bit; for (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {} GFP2_ONB gfp2(p); GFP2Element c = gfp2.ConvertIn(b); GFP2Element cp = gfp2.PthPower(c); GFP2Element S[5] = {gfp2.ConvertIn(3), c, gfp2.SpecialOperation1(c)}; // do all exponents bits except the lowest zeros starting from the top unsigned int i; for (i = e.BitCount() - 1; i>lowest1bit; i--) { if (e.GetBit(i)) { gfp2.RaiseToPthPower(S[0]); gfp2.Accumulate(S[0], gfp2.SpecialOperation2(S[2], c, S[1])); S[1] = gfp2.SpecialOperation1(S[1]); S[2] = gfp2.SpecialOperation1(S[2]); S[0].swap(S[1]); } else { gfp2.RaiseToPthPower(S[2]); gfp2.Accumulate(S[2], gfp2.SpecialOperation2(S[0], cp, S[1])); S[1] = gfp2.SpecialOperation1(S[1]); S[0] = gfp2.SpecialOperation1(S[0]); S[2].swap(S[1]); } } // now do the lowest zeros while (i--) S[1] = gfp2.SpecialOperation1(S[1]); return gfp2.ConvertOut(S[1]); } template class AbstractRing; template class AbstractGroup; NAMESPACE_END ``````