| 1 | // eprecomp.cpp - written and placed in the public domain by Wei Dai |
|---|
| 2 | |
|---|
| 3 | #include "pch.h" |
|---|
| 4 | |
|---|
| 5 | #ifndef CRYPTOPP_IMPORTS |
|---|
| 6 | |
|---|
| 7 | #include "eprecomp.h" |
|---|
| 8 | #include "integer.h" |
|---|
| 9 | #include "algebra.h" |
|---|
| 10 | #include "asn.h" |
|---|
| 11 | |
|---|
| 12 | NAMESPACE_BEGIN(CryptoPP) |
|---|
| 13 | |
|---|
| 14 | template <class T> void DL_FixedBasePrecomputationImpl<T>::SetBase(const DL_GroupPrecomputation<Element> &group, const Element &i_base) |
|---|
| 15 | { |
|---|
| 16 | m_base = group.NeedConversions() ? group.ConvertIn(i_base) : i_base; |
|---|
| 17 | |
|---|
| 18 | if (m_bases.empty() || !(m_base == m_bases[0])) |
|---|
| 19 | { |
|---|
| 20 | m_bases.resize(1); |
|---|
| 21 | m_bases[0] = m_base; |
|---|
| 22 | } |
|---|
| 23 | |
|---|
| 24 | if (group.NeedConversions()) |
|---|
| 25 | m_base = i_base; |
|---|
| 26 | } |
|---|
| 27 | |
|---|
| 28 | template <class T> void DL_FixedBasePrecomputationImpl<T>::Precompute(const DL_GroupPrecomputation<Element> &group, unsigned int maxExpBits, unsigned int storage) |
|---|
| 29 | { |
|---|
| 30 | CRYPTOPP_ASSERT(m_bases.size() > 0); |
|---|
| 31 | CRYPTOPP_ASSERT(storage <= maxExpBits); |
|---|
| 32 | |
|---|
| 33 | if (storage > 1) |
|---|
| 34 | { |
|---|
| 35 | m_windowSize = (maxExpBits+storage-1)/storage; |
|---|
| 36 | m_exponentBase = Integer::Power2(m_windowSize); |
|---|
| 37 | } |
|---|
| 38 | |
|---|
| 39 | m_bases.resize(storage); |
|---|
| 40 | for (unsigned i=1; i<storage; i++) |
|---|
| 41 | m_bases[i] = group.GetGroup().ScalarMultiply(m_bases[i-1], m_exponentBase); |
|---|
| 42 | } |
|---|
| 43 | |
|---|
| 44 | template <class T> void DL_FixedBasePrecomputationImpl<T>::Load(const DL_GroupPrecomputation<Element> &group, BufferedTransformation &bt) |
|---|
| 45 | { |
|---|
| 46 | BERSequenceDecoder seq(bt); |
|---|
| 47 | word32 version; |
|---|
| 48 | BERDecodeUnsigned<word32>(seq, version, INTEGER, 1, 1); |
|---|
| 49 | m_exponentBase.BERDecode(seq); |
|---|
| 50 | m_windowSize = m_exponentBase.BitCount() - 1; |
|---|
| 51 | m_bases.clear(); |
|---|
| 52 | while (!seq.EndReached()) |
|---|
| 53 | m_bases.push_back(group.BERDecodeElement(seq)); |
|---|
| 54 | if (!m_bases.empty() && group.NeedConversions()) |
|---|
| 55 | m_base = group.ConvertOut(m_bases[0]); |
|---|
| 56 | seq.MessageEnd(); |
|---|
| 57 | } |
|---|
| 58 | |
|---|
| 59 | template <class T> void DL_FixedBasePrecomputationImpl<T>::Save(const DL_GroupPrecomputation<Element> &group, BufferedTransformation &bt) const |
|---|
| 60 | { |
|---|
| 61 | DERSequenceEncoder seq(bt); |
|---|
| 62 | DEREncodeUnsigned<word32>(seq, 1); // version |
|---|
| 63 | m_exponentBase.DEREncode(seq); |
|---|
| 64 | for (unsigned i=0; i<m_bases.size(); i++) |
|---|
| 65 | group.DEREncodeElement(seq, m_bases[i]); |
|---|
| 66 | seq.MessageEnd(); |
|---|
| 67 | } |
|---|
| 68 | |
|---|
| 69 | template <class T> void DL_FixedBasePrecomputationImpl<T>::PrepareCascade(const DL_GroupPrecomputation<Element> &i_group, std::vector<BaseAndExponent<Element> > &eb, const Integer &exponent) const |
|---|
| 70 | { |
|---|
| 71 | const AbstractGroup<T> &group = i_group.GetGroup(); |
|---|
| 72 | |
|---|
| 73 | Integer r, q, e = exponent; |
|---|
| 74 | bool fastNegate = group.InversionIsFast() && m_windowSize > 1; |
|---|
| 75 | unsigned int i; |
|---|
| 76 | |
|---|
| 77 | for (i=0; i+1<m_bases.size(); i++) |
|---|
| 78 | { |
|---|
| 79 | Integer::DivideByPowerOf2(r, q, e, m_windowSize); |
|---|
| 80 | std::swap(q, e); |
|---|
| 81 | if (fastNegate && r.GetBit(m_windowSize-1)) |
|---|
| 82 | { |
|---|
| 83 | ++e; |
|---|
| 84 | eb.push_back(BaseAndExponent<Element>(group.Inverse(m_bases[i]), m_exponentBase - r)); |
|---|
| 85 | } |
|---|
| 86 | else |
|---|
| 87 | eb.push_back(BaseAndExponent<Element>(m_bases[i], r)); |
|---|
| 88 | } |
|---|
| 89 | eb.push_back(BaseAndExponent<Element>(m_bases[i], e)); |
|---|
| 90 | } |
|---|
| 91 | |
|---|
| 92 | template <class T> T DL_FixedBasePrecomputationImpl<T>::Exponentiate(const DL_GroupPrecomputation<Element> &group, const Integer &exponent) const |
|---|
| 93 | { |
|---|
| 94 | std::vector<BaseAndExponent<Element> > eb; // array of segments of the exponent and precalculated bases |
|---|
| 95 | eb.reserve(m_bases.size()); |
|---|
| 96 | PrepareCascade(group, eb, exponent); |
|---|
| 97 | return group.ConvertOut(GeneralCascadeMultiplication<Element>(group.GetGroup(), eb.begin(), eb.end())); |
|---|
| 98 | } |
|---|
| 99 | |
|---|
| 100 | template <class T> T |
|---|
| 101 | DL_FixedBasePrecomputationImpl<T>::CascadeExponentiate(const DL_GroupPrecomputation<Element> &group, const Integer &exponent, |
|---|
| 102 | const DL_FixedBasePrecomputation<T> &i_pc2, const Integer &exponent2) const |
|---|
| 103 | { |
|---|
| 104 | std::vector<BaseAndExponent<Element> > eb; // array of segments of the exponent and precalculated bases |
|---|
| 105 | const DL_FixedBasePrecomputationImpl<T> &pc2 = static_cast<const DL_FixedBasePrecomputationImpl<T> &>(i_pc2); |
|---|
| 106 | eb.reserve(m_bases.size() + pc2.m_bases.size()); |
|---|
| 107 | PrepareCascade(group, eb, exponent); |
|---|
| 108 | pc2.PrepareCascade(group, eb, exponent2); |
|---|
| 109 | return group.ConvertOut(GeneralCascadeMultiplication<Element>(group.GetGroup(), eb.begin(), eb.end())); |
|---|
| 110 | } |
|---|
| 111 | |
|---|
| 112 | NAMESPACE_END |
|---|
| 113 | |
|---|
| 114 | #endif |
|---|
