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

gfpcrypt.cpp
1 // dsa.cpp - originally written and placed in the public domain by Wei Dai
2
3 #include "pch.h"
4 #include "config.h"
5
6 // TODO: fix the C4589 warnings
7 #if CRYPTOPP_MSC_VERSION
8 # pragma warning(disable: 4189 4589)
9 #endif
10
11 #ifndef CRYPTOPP_IMPORTS
12
13 #include "gfpcrypt.h"
14 #include "nbtheory.h"
15 #include "modarith.h"
16 #include "integer.h"
17 #include "asn.h"
18 #include "oids.h"
19 #include "misc.h"
20
21 NAMESPACE_BEGIN(CryptoPP)
22
23 #if defined(CRYPTOPP_DEBUG) && !defined(CRYPTOPP_DOXYGEN_PROCESSING)
24 void TestInstantiations_gfpcrypt()
25 {
26 GDSA<SHA1>::Signer test;
27 GDSA<SHA1>::Verifier test1;
28 DSA::Signer test5(NullRNG(), 100);
29 DSA::Signer test2(test5);
30 NR<SHA1>::Signer test3;
31 NR<SHA1>::Verifier test4;
32 DLIES<>::Encryptor test6;
33 DLIES<>::Decryptor test7;
34 }
35 #endif
36
37 void DL_GroupParameters_DSA::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
38 {
39 Integer p, q, g;
40
41 if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
42 {
43 q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
44 Initialize(p, q, g);
45 }
46 else
47 {
48 int modulusSize = 2048, defaultSubgroupOrderSize;
49 alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
50
51 switch (modulusSize)
52 {
53 case 1024:
54 defaultSubgroupOrderSize = 160;
55 break;
56 case 2048:
57 defaultSubgroupOrderSize = 224;
58 break;
59 case 3072:
60 defaultSubgroupOrderSize = 256;
61 break;
62 default:
63 throw InvalidArgument("DSA: not a valid prime length");
64 }
65
66 DL_GroupParameters_GFP::GenerateRandom(rng, CombinedNameValuePairs(alg, MakeParameters(Name::SubgroupOrderSize(), defaultSubgroupOrderSize, false)));
67 }
68 }
69
70 bool DL_GroupParameters_DSA::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
71 {
72 bool pass = DL_GroupParameters_GFP::ValidateGroup(rng, level);
73 CRYPTOPP_ASSERT(pass);
74
75 const int pSize = GetModulus().BitCount(), qSize = GetSubgroupOrder().BitCount();
76 pass = pass && ((pSize==1024 && qSize==160) || (pSize==2048 && qSize==224) || (pSize==2048 && qSize==256) || (pSize==3072 && qSize==256));
77 CRYPTOPP_ASSERT(pass);
78
79 return pass;
80 }
81
82 void DL_SignatureMessageEncodingMethod_DSA::ComputeMessageRepresentative(RandomNumberGenerator &rng,
83 const byte *recoverableMessage, size_t recoverableMessageLength,
84 HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
85 byte *representative, size_t representativeBitLength) const
86 {
87 CRYPTOPP_UNUSED(rng), CRYPTOPP_UNUSED(recoverableMessage), CRYPTOPP_UNUSED(recoverableMessageLength);
88 CRYPTOPP_UNUSED(messageEmpty), CRYPTOPP_UNUSED(hashIdentifier);
89 CRYPTOPP_ASSERT(recoverableMessageLength == 0);
90 CRYPTOPP_ASSERT(hashIdentifier.second == 0);
91
92 const size_t representativeByteLength = BitsToBytes(representativeBitLength);
93 const size_t digestSize = hash.DigestSize();
94 const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
95
96 memset(representative, 0, paddingLength);
97 hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
98
99 if (digestSize*8 > representativeBitLength)
100 {
101 Integer h(representative, representativeByteLength);
102 h >>= representativeByteLength*8 - representativeBitLength;
103 h.Encode(representative, representativeByteLength);
104 }
105 }
106
107 void DL_SignatureMessageEncodingMethod_NR::ComputeMessageRepresentative(RandomNumberGenerator &rng,
108 const byte *recoverableMessage, size_t recoverableMessageLength,
109 HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
110 byte *representative, size_t representativeBitLength) const
111 {
112 CRYPTOPP_UNUSED(rng);CRYPTOPP_UNUSED(recoverableMessage); CRYPTOPP_UNUSED(recoverableMessageLength);
113 CRYPTOPP_UNUSED(hash); CRYPTOPP_UNUSED(hashIdentifier); CRYPTOPP_UNUSED(messageEmpty);
114 CRYPTOPP_UNUSED(representative); CRYPTOPP_UNUSED(representativeBitLength);
115
116 CRYPTOPP_ASSERT(recoverableMessageLength == 0);
117 CRYPTOPP_ASSERT(hashIdentifier.second == 0);
118 const size_t representativeByteLength = BitsToBytes(representativeBitLength);
119 const size_t digestSize = hash.DigestSize();
120 const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
121
122 memset(representative, 0, paddingLength);
123 hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
124
125 if (digestSize*8 >= representativeBitLength)
126 {
127 Integer h(representative, representativeByteLength);
128 h >>= representativeByteLength*8 - representativeBitLength + 1;
129 h.Encode(representative, representativeByteLength);
130 }
131 }
132
133 bool DL_GroupParameters_IntegerBased::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
134 {
135 const Integer &p = GetModulus(), &q = GetSubgroupOrder();
136
137 bool pass = true;
138 pass = pass && p > Integer::One() && p.IsOdd();
139 CRYPTOPP_ASSERT(pass);
140 pass = pass && q > Integer::One() && q.IsOdd();
141 CRYPTOPP_ASSERT(pass);
142
143 if (level >= 1)
144 {
145 pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero();
146 CRYPTOPP_ASSERT(pass);
147 }
148 if (level >= 2)
149 {
150 pass = pass && VerifyPrime(rng, q, level-2) && VerifyPrime(rng, p, level-2);
151 CRYPTOPP_ASSERT(pass);
152 }
153
154 return pass;
155 }
156
157 bool DL_GroupParameters_IntegerBased::ValidateElement(unsigned int level, const Integer &g, const DL_FixedBasePrecomputation<Integer> *gpc) const
158 {
159 const Integer &p = GetModulus(), &q = GetSubgroupOrder();
160
161 bool pass = true;
162 pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative();
163 CRYPTOPP_ASSERT(pass);
164
165 pass = pass && g < p && !IsIdentity(g);
166 CRYPTOPP_ASSERT(pass);
167
168 if (level >= 1)
169 {
170 if (gpc)
171 {
172 pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g;
173 CRYPTOPP_ASSERT(pass);
174 }
175 }
176 if (level >= 2)
177 {
178 if (GetFieldType() == 2)
179 {
180 pass = pass && Jacobi(g*g-4, p)==-1;
181 CRYPTOPP_ASSERT(pass);
182 }
183
184 // verifying that Lucas((p+1)/2, w, p)==2 is omitted because it's too costly
185 // and at most 1 bit is leaked if it's false
186 bool fullValidate = (GetFieldType() == 2 && level >= 3) || !FastSubgroupCheckAvailable();
187
188 if (fullValidate && pass)
189 {
190 Integer gp = gpc ? gpc->Exponentiate(GetGroupPrecomputation(), q) : ExponentiateElement(g, q);
191 pass = pass && IsIdentity(gp);
192 CRYPTOPP_ASSERT(pass);
193 }
194 else if (GetFieldType() == 1)
195 {
196 pass = pass && Jacobi(g, p) == 1;
197 CRYPTOPP_ASSERT(pass);
198 }
199 }
200
201 return pass;
202 }
203
204 void DL_GroupParameters_IntegerBased::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
205 {
206 Integer p, q, g;
207
208 if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
209 {
210 q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
211 }
212 else
213 {
214 int modulusSize, subgroupOrderSize;
215
216 if (!alg.GetIntValue("ModulusSize", modulusSize))
217 modulusSize = alg.GetIntValueWithDefault("KeySize", 2048);
218
219 if (!alg.GetIntValue("SubgroupOrderSize", subgroupOrderSize))
220 subgroupOrderSize = GetDefaultSubgroupOrderSize(modulusSize);
221
222 PrimeAndGenerator pg;
223 pg.Generate(GetFieldType() == 1 ? 1 : -1, rng, modulusSize, subgroupOrderSize);
224 p = pg.Prime();
225 q = pg.SubPrime();
226 g = pg.Generator();
227 }
228
229 Initialize(p, q, g);
230 }
231
232 void DL_GroupParameters_IntegerBased::EncodeElement(bool reversible, const Element &element, byte *encoded) const
233 {
234 CRYPTOPP_UNUSED(reversible);
235 element.Encode(encoded, GetModulus().ByteCount());
236 }
237
238 unsigned int DL_GroupParameters_IntegerBased::GetEncodedElementSize(bool reversible) const
239 {
240 CRYPTOPP_UNUSED(reversible);
241 return GetModulus().ByteCount();
242 }
243
244 Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const
245 {
246 CRYPTOPP_UNUSED(checkForGroupMembership);
247 Integer g(encoded, GetModulus().ByteCount());
248 if (!ValidateElement(1, g, NULLPTR))
249 throw DL_BadElement();
250 return g;
251 }
252
253 void DL_GroupParameters_IntegerBased::BERDecode(BufferedTransformation &bt)
254 {
255 BERSequenceDecoder parameters(bt);
256 Integer p(parameters);
257 Integer q(parameters);
258 Integer g;
259 if (parameters.EndReached())
260 {
261 g = q;
262 q = ComputeGroupOrder(p) / 2;
263 }
264 else
265 g.BERDecode(parameters);
266 parameters.MessageEnd();
267
268 SetModulusAndSubgroupGenerator(p, g);
269 SetSubgroupOrder(q);
270 }
271
272 void DL_GroupParameters_IntegerBased::DEREncode(BufferedTransformation &bt) const
273 {
274 DERSequenceEncoder parameters(bt);
275 GetModulus().DEREncode(parameters);
276 m_q.DEREncode(parameters);
277 GetSubgroupGenerator().DEREncode(parameters);
278 parameters.MessageEnd();
279 }
280
281 bool DL_GroupParameters_IntegerBased::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
282 {
283 return GetValueHelper<DL_GroupParameters<Element> >(this, name, valueType, pValue)
284 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus);
285 }
286
287 void DL_GroupParameters_IntegerBased::AssignFrom(const NameValuePairs &source)
288 {
289 AssignFromHelper(this, source)
290 CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator)
291 CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder)
292 ;
293 }
294
295 OID DL_GroupParameters_IntegerBased::GetAlgorithmID() const
296 {
297 return ASN1::id_dsa();
298 }
299
300 void DL_GroupParameters_GFP::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
301 {
302 ModularArithmetic ma(GetModulus());
303 ma.SimultaneousExponentiate(results, base, exponents, exponentsCount);
304 }
305
306 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::MultiplyElements(const Element &a, const Element &b) const
307 {
308 return a_times_b_mod_c(a, b, GetModulus());
309 }
310
311 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::CascadeExponentiate(const Element &element1, const Integer &exponent1, const Element &element2, const Integer &exponent2) const
312 {
313 ModularArithmetic ma(GetModulus());
314 return ma.CascadeExponentiate(element1, exponent1, element2, exponent2);
315 }
316
317 Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const
318 {
319 return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount())));
320 }
321
322 unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const
323 {
324 return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize);
325 }
326
327 NAMESPACE_END
328
329 #endif
DL_GroupParameters_IntegerBased::AssignFrom
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: gfpcrypt.cpp:287
NameValuePairs::GetIntValueWithDefault
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:395
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:202
DL_GroupParameters_IntegerBased::BERDecode
void BERDecode(BufferedTransformation &bt)
Decode this object from a BufferedTransformation.
Definition: gfpcrypt.cpp:253
DL_FixedBasePrecomputation::Exponentiate
virtual Element Exponentiate(const DL_GroupPrecomputation< Element > &group, const Integer &exponent) const =0
Exponentiates an element.
DL_GroupParameters< Integer >::GetCofactor
virtual Integer GetCofactor() const
Retrieves the cofactor.
Definition: pubkey.h:884
misc.h
Utility functions for the Crypto++ library.
NameValuePairs::GetValueWithDefault
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:363
DL_GroupParameters_IntegerBased::GetGroupOrder
Integer GetGroupOrder() const
Retrieves the order of the group.
Definition: gfpcrypt.h:80
Integer::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3432
BitsToBytes
size_t BitsToBytes(size_t bitCount)
Returns the number of 8-bit bytes or octets required for the specified number of bits.
Definition: misc.h:818
HashTransformation::TruncatedFinal
virtual void TruncatedFinal(byte *digest, size_t digestSize)=0
Computes the hash of the current message.
oids.h
ASN.1 object identifiers for algorthms and schemes.
config.h
Library configuration file.
ModularArithmetic
Ring of congruence classes modulo n.
Definition: modarith.h:38
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1383
Jacobi
int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Definition: nbtheory.cpp:785
CombinedNameValuePairs
Combines two sets of NameValuePairs.
Definition: algparam.h:124
PrimeAndGenerator
Generator of prime numbers of special forms.
Definition: nbtheory.h:262
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:309
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1598
Integer::One
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:4868
DL_GroupParameters_IntegerBased::ValidateGroup
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Check the group for errors.
Definition: gfpcrypt.cpp:133
Integer::ByteCount
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Definition: integer.cpp:3336
Name::SubgroupOrderSize
const char * SubgroupOrderSize()
int, in bits
Definition: argnames.h:31
PrimeAndGenerator::SubPrime
const Integer & SubPrime() const
Retrieve second prime.
Definition: nbtheory.h:304
PrimeAndGenerator::Prime
const Integer & Prime() const
Retrieve first prime.
Definition: nbtheory.h:300
MakeParameters
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:502
VerifyPrime
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Definition: nbtheory.cpp:247
DL_GroupParameters< Integer >::GetSubgroupGenerator
virtual const Element & GetSubgroupGenerator() const
Retrieves the subgroup generator.
Definition: pubkey.h:829
Integer::Power2
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:3079
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:49
pch.h
Precompiled header file.
SaturatingSubtract
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition: misc.h:972
Name::SubgroupGenerator
const char * SubgroupGenerator()
Integer, ECP::Point, or EC2N::Point.
Definition: argnames.h:39
gfpcrypt.h
Classes and functions for schemes based on Discrete Logs (DL) over GF(p)
DL_GroupParameters_IntegerBased::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: gfpcrypt.cpp:204
DL_GroupParameters_DSA::ValidateGroup
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Definition: gfpcrypt.cpp:70
DL_BadElement
Exception thrown when an invalid group element is encountered.
Definition: pubkey.h:743
NullRNG
RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
Definition: cryptlib.cpp:400
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:535
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69
asn.h
Classes and functions for working with ANS.1 objects.
DL_FixedBasePrecomputation< Integer >
DL_GroupParameters_IntegerBased::Initialize
void Initialize(const DL_GroupParameters_IntegerBased &params)
Initialize a group parameters over integers.
Definition: gfpcrypt.h:43
Integer::BitCount
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3345
nbtheory.h
Classes and functions for number theoretic operations.
DiscreteLogWorkFactor
unsigned int DiscreteLogWorkFactor(unsigned int bitlength)
Estimate work factor.
Definition: nbtheory.cpp:1027
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:319
DL_GroupParameters_IntegerBased::ValidateElement
bool ValidateElement(unsigned int level, const Integer &element, const DL_FixedBasePrecomputation< Integer > *precomp) const
Check the element for errors.
Definition: gfpcrypt.cpp:157
DL_GroupParameters< Integer >::GetGroupPrecomputation
virtual const DL_GroupPrecomputation< Element > & GetGroupPrecomputation() const=0
Retrieves the group precomputation.
HashTransformation::DigestSize
virtual unsigned int DigestSize() const =0
Provides the digest size of the hash.
DL_GroupParameters_IntegerBased::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode this object into a BufferedTransformation.
Definition: gfpcrypt.cpp:272
HashTransformation
Interface for hash functions and data processing part of MACs.
Definition: cryptlib.h:1084
DL_GroupParameters_IntegerBased::GetMaxExponent
Integer GetMaxExponent() const
Retrieves the maximum exponent for the group.
Definition: gfpcrypt.cpp:317
Name::Modulus
const char * Modulus()
Integer.
Definition: argnames.h:33
PrimeAndGenerator::Generate
void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Generate a Prime and Generator.
Definition: nbtheory.cpp:1036
integer.h
Multiple precision integer with arithmetic operations.
DL_GroupParameters_IntegerBased::GetSubgroupOrder
const Integer & GetSubgroupOrder() const
Retrieves the subgroup order.
Definition: gfpcrypt.h:79
Integer::Zero
static const Integer & Zero()
Integer representing 0.
Definition: integer.cpp:4856
DL_GroupParameters_IntegerBased::GetEncodedElementSize
unsigned int GetEncodedElementSize(bool reversible) const
Retrieves the encoded element&#39;s size.
Definition: gfpcrypt.cpp:238
modarith.h
Class file for performing modular arithmetic.
CryptoPP
Crypto++ library namespace.
NameValuePairs::GetValue
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:350
NameValuePairs::GetIntValue
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:386
DL_GroupParameters_IntegerBased::DecodeElement
Integer DecodeElement(const byte *encoded, bool checkForGroupMembership) const
Decodes the element.
Definition: gfpcrypt.cpp:244
DL_GroupParameters< Integer >::ExponentiateElement
virtual Element ExponentiateElement(const Element &base, const Integer &exponent) const
Exponentiates an element.
Definition: pubkey.h:849
OID
Object Identifier.
Definition: asn.h:166
Name::SubgroupOrder
const char * SubgroupOrder()
Integer.
Definition: argnames.h:37
PrimeAndGenerator::Generator
const Integer & Generator() const
Retrieve the generator.
Definition: nbtheory.h:308
DL_GroupParameters_DSA::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: gfpcrypt.cpp:37
DL_GroupParameters< Integer >::IsIdentity
virtual bool IsIdentity(const Element &element) const=0
Determines if an element is an identity.
DL_GroupParameters_IntegerBased::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: gfpcrypt.cpp:281
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:351
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:293
PK_FinalTemplate
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2134