Crypto++  5.6.3
Free C++ class library of cryptographic schemes
eprecomp.cpp
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  assert(m_bases.size() > 0);
31  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 
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 
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
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
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
Definition: integer.cpp:2975
virtual bool InversionIsFast() const
Determine if inversion is fast.
Definition: algebra.h:57
static void DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n)
returns same result as Divide(r, q, a, Power2(n)), but faster
Definition: integer.cpp:3921
BER Sequence Decoder.
Definition: asn.h:294
Classes for performing mathematics over different fields.
Interface for buffered transformations.
Definition: cryptlib.h:1352
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:2927
Multiple precision integer with arithmetic operations.
Definition: integer.h:31
Abstract group.
Definition: algebra.h:26
Classes and functions for working with ANS.1 objects.
Classes for precomputation in a group.
DER Sequence Encoder.
Definition: asn.h:304
virtual const Element & Inverse(const Element &a) const =0
Inverts the element in the group.
Base and exponent.
Definition: algebra.h:249
Crypto++ library namespace.