Security Scol plugin
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
21NAMESPACE_BEGIN(CryptoPP)
22
23#if defined(CRYPTOPP_DEBUG) && !defined(CRYPTOPP_DOXYGEN_PROCESSING)
24void TestInstantiations_gfpcrypt()
25{
28 DSA::Signer test5(NullRNG(), 100);
29 DSA::Signer test2(test5);
30 NR<SHA1>::Signer test3;
34}
35#endif
36
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
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
82void 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
107void 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
134{
135 const Integer &p = GetModulus(), &q = GetSubgroupOrder();
136 bool pass = true;
137
138 CRYPTOPP_ASSERT(p > Integer::One() && p.IsOdd());
139 pass = pass && p > Integer::One() && p.IsOdd();
140
141 CRYPTOPP_ASSERT(q > Integer::One() && q.IsOdd());
142 pass = pass && q > Integer::One() && q.IsOdd();
143
144 if (level >= 1)
145 {
146 CRYPTOPP_ASSERT(GetCofactor() > Integer::One());
147 CRYPTOPP_ASSERT(GetGroupOrder() % q == Integer::Zero());
148
149 pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero();
150 }
151 if (level >= 2)
152 {
153 CRYPTOPP_ASSERT(VerifyPrime(rng, q, level-2));
154 CRYPTOPP_ASSERT(VerifyPrime(rng, p, level-2));
155
156 pass = pass && VerifyPrime(rng, q, level-2) && VerifyPrime(rng, p, level-2);
157 }
158
159 return pass;
160}
161
163{
164 const Integer &p = GetModulus(), &q = GetSubgroupOrder();
165 bool pass = true;
166
167 CRYPTOPP_ASSERT(GetFieldType() == 1 ? g.IsPositive() : g.NotNegative());
168 pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative();
169
170 CRYPTOPP_ASSERT(g < p && !IsIdentity(g));
171 pass = pass && g < p && !IsIdentity(g);
172
173 if (level >= 1)
174 {
175 if (gpc)
176 {
177 CRYPTOPP_ASSERT(gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g);
178 pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g;
179 }
180 }
181 if (level >= 2)
182 {
183 if (GetFieldType() == 2)
184 {
185 CRYPTOPP_ASSERT(Jacobi(g*g-4, p)==-1);
186 pass = pass && Jacobi(g*g-4, p)==-1;
187 }
188
189 // verifying that Lucas((p+1)/2, w, p)==2 is omitted because it's too costly
190 // and at most 1 bit is leaked if it's false
191 bool fullValidate = (GetFieldType() == 2 && level >= 3) || !FastSubgroupCheckAvailable();
192
193 if (fullValidate && pass)
194 {
196 CRYPTOPP_ASSERT(IsIdentity(gp));
197 pass = pass && IsIdentity(gp);
198 }
199 else if (GetFieldType() == 1)
200 {
201 CRYPTOPP_ASSERT(Jacobi(g, p) == 1);
202 pass = pass && Jacobi(g, p) == 1;
203 }
204 }
205
206 return pass;
207}
208
210{
211 Integer p, q, g;
212
213 if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
214 {
215 q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
216 }
217 else
218 {
219 int modulusSize, subgroupOrderSize;
220
221 if (!alg.GetIntValue("ModulusSize", modulusSize))
222 modulusSize = alg.GetIntValueWithDefault("KeySize", 2048);
223
224 if (!alg.GetIntValue("SubgroupOrderSize", subgroupOrderSize))
225 subgroupOrderSize = GetDefaultSubgroupOrderSize(modulusSize);
226
228 pg.Generate(GetFieldType() == 1 ? 1 : -1, rng, modulusSize, subgroupOrderSize);
229 p = pg.Prime();
230 q = pg.SubPrime();
231 g = pg.Generator();
232 }
233
234 Initialize(p, q, g);
235}
236
237void DL_GroupParameters_IntegerBased::EncodeElement(bool reversible, const Element &element, byte *encoded) const
238{
239 CRYPTOPP_UNUSED(reversible);
240 element.Encode(encoded, GetModulus().ByteCount());
241}
242
244{
245 CRYPTOPP_UNUSED(reversible);
246 return GetModulus().ByteCount();
247}
248
249Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const
250{
251 CRYPTOPP_UNUSED(checkForGroupMembership);
252 Integer g(encoded, GetModulus().ByteCount());
253 if (!ValidateElement(1, g, NULLPTR))
254 throw DL_BadElement();
255 return g;
256}
257
259{
260 BERSequenceDecoder parameters(bt);
261 Integer p(parameters);
262 Integer q(parameters);
263 Integer g;
264 if (parameters.EndReached())
265 {
266 g = q;
267 q = ComputeGroupOrder(p) / 2;
268 }
269 else
270 g.BERDecode(parameters);
271 parameters.MessageEnd();
272
275}
276
278{
279 DERSequenceEncoder parameters(bt);
280 GetModulus().DEREncode(parameters);
281 m_q.DEREncode(parameters);
282 GetSubgroupGenerator().DEREncode(parameters);
283 parameters.MessageEnd();
284}
285
286bool DL_GroupParameters_IntegerBased::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
287{
288 return GetValueHelper<DL_GroupParameters<Element> >(this, name, valueType, pValue)
289 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus);
290}
291
293{
294 AssignFromHelper(this, source)
295 CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator)
296 CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder)
297 ;
298}
299
301{
302 return ASN1::id_dsa();
303}
304
305void DL_GroupParameters_GFP::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
306{
308 ma.SimultaneousExponentiate(results, base, exponents, exponentsCount);
309}
310
311DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::MultiplyElements(const Element &a, const Element &b) const
312{
313 return a_times_b_mod_c(a, b, GetModulus());
314}
315
316DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::CascadeExponentiate(const Element &element1, const Integer &exponent1, const Element &element2, const Integer &exponent2) const
317{
319 return ma.CascadeExponentiate(element1, exponent1, element2, exponent2);
320}
321
323{
324 return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount())));
325}
326
327unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const
328{
329 return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize);
330}
331
332NAMESPACE_END
333
334#endif
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition algparam.h:508
Classes and functions for working with ANS.1 objects.
bool EndReached() const
Determine end of stream.
Definition asn.cpp:527
void MessageEnd()
Signals the end of messages to the object.
Definition asn.cpp:553
BER Sequence Decoder.
Definition asn.h:525
Interface for buffered transformations.
Definition cryptlib.h:1652
Combines two sets of NameValuePairs.
Definition algparam.h:129
void MessageEnd()
Signals the end of messages to the object.
Definition asn.cpp:624
DER Sequence Encoder.
Definition asn.h:557
Exception thrown when an invalid group element is encountered.
Definition pubkey.h:772
DL_FixedBasePrecomputation interface.
Definition eprecomp.h:61
virtual Element Exponentiate(const DL_GroupPrecomputation< Element > &group, const Integer &exponent) const =0
Exponentiates an element.
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Check the group for errors.
Definition gfpcrypt.cpp:70
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key or crypto parameters.
Definition gfpcrypt.cpp:37
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents.
Definition gfpcrypt.cpp:305
void AssignFrom(const NameValuePairs &source)
Initialize or reinitialize this key.
Definition gfpcrypt.cpp:292
Integer GetGroupOrder() const
Retrieves the order of the group.
Definition gfpcrypt.h:99
virtual void SetModulusAndSubgroupGenerator(const Integer &p, const Integer &g)=0
Set group parameters.
OID GetAlgorithmID() const
Retrieve the OID of the algorithm.
Definition gfpcrypt.cpp:300
void DEREncode(BufferedTransformation &bt) const
Encode this object into a BufferedTransformation.
Definition gfpcrypt.cpp:277
Integer GetMaxExponent() const
Retrieve the maximum exponent for the group.
Definition gfpcrypt.cpp:322
void SetSubgroupOrder(const Integer &q)
Set subgroup order.
Definition gfpcrypt.h:161
Integer DecodeElement(const byte *encoded, bool checkForGroupMembership) const
Decodes the element.
Definition gfpcrypt.cpp:249
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key.
Definition gfpcrypt.cpp:209
void BERDecode(BufferedTransformation &bt)
Decode this object from a BufferedTransformation.
Definition gfpcrypt.cpp:258
virtual const Integer & GetModulus() const =0
Retrieve the modulus for the group.
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Check the group for errors.
Definition gfpcrypt.cpp:133
void Initialize(const DL_GroupParameters_IntegerBased &params)
Initialize a group parameters over integers.
Definition gfpcrypt.h:43
bool FastSubgroupCheckAvailable() const
Determine if subgroup membership check is fast.
Definition gfpcrypt.h:105
unsigned int GetEncodedElementSize(bool reversible) const
Retrieve the encoded element's size.
Definition gfpcrypt.cpp:243
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition gfpcrypt.cpp:286
bool ValidateElement(unsigned int level, const Integer &element, const DL_FixedBasePrecomputation< Integer > *precomp) const
Check the element for errors.
Definition gfpcrypt.cpp:162
const Integer & GetSubgroupOrder() const
Retrieves the subgroup order.
Definition gfpcrypt.h:98
void EncodeElement(bool reversible, const Element &element, byte *encoded) const
Encodes the element.
Definition gfpcrypt.cpp:237
const Integer & GetModulus() const
Retrieve the modulus for the group.
Definition gfpcrypt.h:205
virtual Element ExponentiateElement(const Element &base, const Integer &exponent) const
Exponentiates an element.
Definition pubkey.h:879
virtual Integer GetCofactor() const
Retrieves the cofactor.
Definition pubkey.h:914
virtual bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const =0
Check the group for errors.
virtual const Element & GetSubgroupGenerator() const
Retrieves the subgroup generator.
Definition pubkey.h:859
virtual const DL_GroupPrecomputation< Element > & GetGroupPrecomputation() const=0
Retrieves the group precomputation.
virtual const Integer & GetSubgroupOrder() const =0
Retrieves the subgroup order.
virtual bool IsIdentity(const Element &element) const=0
Determines if an element is an identity.
virtual void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random key or crypto parameters.
Definition cryptlib.h:2520
Interface for hash functions and data processing part of MACs.
Definition cryptlib.h:1113
virtual void TruncatedFinal(byte *digest, size_t digestSize)=0
Computes the hash of the current message.
virtual unsigned int DigestSize() const =0
Multiple precision integer with arithmetic operations.
Definition integer.h:50
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition integer.cpp:3449
static const Integer &CRYPTOPP_API Zero()
Integer representing 0.
Definition integer.cpp:4908
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition integer.cpp:3364
static const Integer &CRYPTOPP_API One()
Integer representing 1.
Definition integer.cpp:4920
static Integer CRYPTOPP_API Power2(size_t e)
Exponentiates to a power of 2.
Definition integer.cpp:3087
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Definition integer.cpp:3355
bool IsOdd() const
Determines if the Integer is odd parity.
Definition integer.h:356
An invalid argument was detected.
Definition cryptlib.h:203
Ring of congruence classes modulo n.
Definition modarith.h:44
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents in the ring.
Definition integer.cpp:4678
Interface for retrieving values given their names.
Definition cryptlib.h:322
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition cryptlib.h:392
bool GetValue(const char *name, T &value) const
Get a named value.
Definition cryptlib.h:379
CRYPTOPP_DLL int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition cryptlib.h:424
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition cryptlib.h:415
Object Identifier.
Definition asn.h:265
Template implementing constructors for public key algorithm classes.
Definition pubkey.h:2198
Generator of prime numbers of special forms.
Definition nbtheory.h:264
const Integer & SubPrime() const
Retrieve second prime.
Definition nbtheory.h:305
const Integer & Generator() const
Retrieve the generator.
Definition nbtheory.h:309
void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Generate a Prime and Generator.
const Integer & Prime() const
Retrieve first prime.
Definition nbtheory.h:301
Interface for random number generators.
Definition cryptlib.h:1435
Library configuration file.
Classes and functions for schemes based on Discrete Logs (DL) over GF(p)
Multiple precision integer with arithmetic operations.
Utility functions for the Crypto++ library.
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition misc.h:1093
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition misc.h:655
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:938
Class file for performing modular arithmetic.
Classes and functions for number theoretic operations.
ASN.1 object identifiers for algorithms and schemes.
Precompiled header file.