Crypto++ 8.1 Free C++ class library of cryptographic schemes

eprecomp.cpp
1 // eprecomp.cpp - originally 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
DL_GroupPrecomputation
DL_GroupPrecomputation interface.
Definition: eprecomp.h:19
DL_FixedBasePrecomputationImpl::Precompute
void Precompute(const DL_GroupPrecomputation< Element > &group, unsigned int maxExpBits, unsigned int storage)
Perform precomputation.
Definition: eprecomp.cpp:28
Integer::DivideByPowerOf2
static void DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n)
Extended Division.
Definition: integer.cpp:4200
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:309
algebra.h
Classes for performing mathematics over different fields.
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1598
DL_GroupPrecomputation::GetGroup
virtual const AbstractGroup< Element > & GetGroup() const =0
Retrieves AbstractGroup interface.
DL_FixedBasePrecomputationImpl::CascadeExponentiate
Element CascadeExponentiate(const DL_GroupPrecomputation< Element > &pc1, const Integer &exponent1, const DL_FixedBasePrecomputation< Element > &pc2, const Integer &exponent2) const
Exponentiates an element.
Definition: eprecomp.cpp:101
DL_FixedBasePrecomputationImpl::Load
void Load(const DL_GroupPrecomputation< Element > &group, BufferedTransformation &storedPrecomputation)
Retrieve previously saved precomputation.
Definition: eprecomp.cpp:44
DL_GroupPrecomputation::BERDecodeElement
virtual Element BERDecodeElement(BufferedTransformation &bt) const =0
Decodes element in DER format.
AbstractGroup::InversionIsFast
virtual bool InversionIsFast() const
Determine if inversion is fast.
Definition: algebra.h:57
Integer::Power2
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:3079
DL_GroupPrecomputation::NeedConversions
virtual bool NeedConversions() const
Determines if elements needs conversion.
Definition: eprecomp.h:29
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:49
pch.h
Precompiled header file.
AbstractGroup::Inverse
virtual const Element & Inverse(const Element &a) const =0
Inverts the element in the group.
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69
AbstractGroup
Abstract group.
Definition: algebra.h:26
DL_FixedBasePrecomputationImpl::Exponentiate
Element Exponentiate(const DL_GroupPrecomputation< Element > &group, const Integer &exponent) const
Exponentiates an element.
Definition: eprecomp.cpp:92
asn.h
Classes and functions for working with ANS.1 objects.
DL_FixedBasePrecomputation
DL_FixedBasePrecomputation interface.
Definition: eprecomp.h:60
eprecomp.h
Classes for precomputation in a group.
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:319
integer.h
Multiple precision integer with arithmetic operations.
BaseAndExponent
Base and exponent.
Definition: algebra.h:249
CryptoPP
Crypto++ library namespace.
Integer::GetBit
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
Definition: integer.cpp:3103
DL_FixedBasePrecomputationImpl::Save
void Save(const DL_GroupPrecomputation< Element > &group, BufferedTransformation &storedPrecomputation) const
Save precomputation for later use.
Definition: eprecomp.cpp:59
DL_FixedBasePrecomputationImpl
DL_FixedBasePrecomputation adapter class.
Definition: eprecomp.h:126
DL_GroupPrecomputation::DEREncodeElement
virtual void DEREncodeElement(BufferedTransformation &bt, const Element &P) const =0
Encodes element in DER format.
DL_GroupPrecomputation::ConvertOut
virtual Element ConvertOut(const Element &v) const
Converts an element between representations.
Definition: eprecomp.h:40