Crypto++  8.3
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;
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 
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 
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 
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 
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  {
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  {
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  {
195  Integer gp = gpc ? gpc->Exponentiate(GetGroupPrecomputation(), q) : ExponentiateElement(g, q);
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 
237 void 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 
249 Integer 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 
274  SetSubgroupOrder(q);
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 
286 bool 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 
305 void 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 
311 DL_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 
316 DL_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 
327 unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const
328 {
329  return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize);
330 }
331 
332 NAMESPACE_END
333 
334 #endif
Name::SubgroupOrder
const char * SubgroupOrder()
Integer.
Definition: argnames.h:37
DL_GroupParameters_IntegerBased::GetMaxExponent
Integer GetMaxExponent() const
Retrieve the maximum exponent for the group.
Definition: gfpcrypt.cpp:322
PrimeAndGenerator::SubPrime
const Integer & SubPrime() const
Retrieve second prime.
Definition: nbtheory.h:305
NameValuePairs::GetValueWithDefault
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:392
MakeParameters
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:508
DL_GroupParameters_IntegerBased::AssignFrom
void AssignFrom(const NameValuePairs &source)
Initialize or reinitialize this key.
Definition: gfpcrypt.cpp:292
nbtheory.h
Classes and functions for number theoretic operations.
Integer::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3433
Name::Modulus
const char * Modulus()
Integer.
Definition: argnames.h:33
DL_GroupParameters_IntegerBased::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key.
Definition: gfpcrypt.cpp:209
ModularArithmetic::SimultaneousExponentiate
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:4626
DL_GroupParameters< Integer >::GetCofactor
virtual Integer GetCofactor() const
Retrieves the cofactor.
Definition: pubkey.h:914
HashTransformation::TruncatedFinal
virtual void TruncatedFinal(byte *digest, size_t digestSize)=0
Computes the hash of the current message.
DL_GroupParameters_IntegerBasedImpl< ModExpPrecomputation >::GetModulus
const Integer & GetModulus() const
Retrieve the modulus for the group.
Definition: gfpcrypt.h:205
DL_GroupParameters_IntegerBased::GetAlgorithmID
OID GetAlgorithmID() const
Retrieve the OID of the algorithm.
Definition: gfpcrypt.cpp:300
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:557
Integer::One
static const Integer &CRYPTOPP_API 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
HashTransformation
Interface for hash functions and data processing part of MACs.
Definition: cryptlib.h:1113
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1631
DL_GroupParameters_DSA::ValidateGroup
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Check the group for errors.
Definition: gfpcrypt.cpp:70
DL_FixedBasePrecomputation< Integer >
ModularArithmetic
Ring of congruence classes modulo n.
Definition: modarith.h:44
BERGeneralDecoder::MessageEnd
void MessageEnd()
Signals the end of messages to the object.
Definition: asn.cpp:553
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68
DL_GroupParameters_IntegerBased::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode this object into a BufferedTransformation.
Definition: gfpcrypt.cpp:277
DL_GroupParameters_IntegerBased::FastSubgroupCheckAvailable
bool FastSubgroupCheckAvailable() const
Determine if subgroup membership check is fast.
Definition: gfpcrypt.h:105
gfpcrypt.h
Classes and functions for schemes based on Discrete Logs (DL) over GF(p)
PrimeAndGenerator::Generator
const Integer & Generator() const
Retrieve the generator.
Definition: nbtheory.h:309
VerifyPrime
CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Definition: nbtheory.cpp:247
modarith.h
Class file for performing modular arithmetic.
PrimeAndGenerator::Generate
void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Generate a Prime and Generator.
Definition: nbtheory.cpp:1054
DL_GroupParameters_GFP::SimultaneousExponentiate
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents.
Definition: gfpcrypt.cpp:305
Integer::Power2
static Integer CRYPTOPP_API Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:3087
pch.h
Precompiled header file.
DL_GroupParameters_IntegerBased::SetSubgroupOrder
void SetSubgroupOrder(const Integer &q)
Set subgroup order.
Definition: gfpcrypt.h:161
OID
Object Identifier.
Definition: asn.h:265
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1414
Integer::ByteCount
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Definition: integer.cpp:3339
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:918
DL_GroupParameters_IntegerBased::GetModulus
virtual const Integer & GetModulus() const =0
Retrieve the modulus for the group.
DL_GroupParameters_IntegerBased::EncodeElement
void EncodeElement(bool reversible, const Element &element, byte *encoded) const
Encodes the element.
Definition: gfpcrypt.cpp:237
misc.h
Utility functions for the Crypto++ library.
DL_GroupParameters_DSA::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key or crypto parameters.
Definition: gfpcrypt.cpp:37
DL_GroupParameters_IntegerBased::DecodeElement
Integer DecodeElement(const byte *encoded, bool checkForGroupMembership) const
Decodes the element.
Definition: gfpcrypt.cpp:249
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:635
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:354
DL_GroupParameters_IntegerBased::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: gfpcrypt.cpp:286
DL_GroupParameters_IntegerBased::Initialize
void Initialize(const DL_GroupParameters_IntegerBased &params)
Initialize a group parameters over integers.
Definition: gfpcrypt.h:43
DL_GroupParameters_IntegerBased::BERDecode
void BERDecode(BufferedTransformation &bt)
Decode this object from a BufferedTransformation.
Definition: gfpcrypt.cpp:258
DL_GroupParameters< Integer >::GetGroupPrecomputation
virtual const DL_GroupPrecomputation< Element > & GetGroupPrecomputation() const=0
Retrieves the group precomputation.
asn.h
Classes and functions for working with ANS.1 objects.
oids.h
ASN.1 object identifiers for algorthms and schemes.
DERGeneralEncoder::MessageEnd
void MessageEnd()
Signals the end of messages to the object.
Definition: asn.cpp:624
NameValuePairs::GetIntValue
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:415
PrimeAndGenerator
Generator of prime numbers of special forms.
Definition: nbtheory.h:264
Name::SubgroupGenerator
const char * SubgroupGenerator()
Integer, ECP::Point, or EC2N::Point.
Definition: argnames.h:39
DL_GroupParameters< Integer >::GetSubgroupGenerator
virtual const Element & GetSubgroupGenerator() const
Retrieves the subgroup generator.
Definition: pubkey.h:859
DL_GroupParameters_IntegerBased::GetEncodedElementSize
unsigned int GetEncodedElementSize(bool reversible) const
Retrieve the encoded element's size.
Definition: gfpcrypt.cpp:243
Integer::BitCount
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3348
Jacobi
CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Definition: nbtheory.cpp:792
DiscreteLogWorkFactor
CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor(unsigned int bitlength)
Estimate work factor.
Definition: nbtheory.cpp:1045
HashTransformation::DigestSize
virtual unsigned int DigestSize() const =0
Provides the digest size of the hash.
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:203
Name::SubgroupOrderSize
const char * SubgroupOrderSize()
int, in bits
Definition: argnames.h:31
DL_FixedBasePrecomputation::Exponentiate
virtual Element Exponentiate(const DL_GroupPrecomputation< Element > &group, const Integer &exponent) const =0
Exponentiates an element.
DL_GroupParameters< Integer >::ExponentiateElement
virtual Element ExponentiateElement(const Element &base, const Integer &exponent) const
Exponentiates an element.
Definition: pubkey.h:879
Integer::Zero
static const Integer &CRYPTOPP_API Zero()
Integer representing 0.
Definition: integer.cpp:4856
CryptoPP
Crypto++ library namespace.
DL_GroupParameters_IntegerBased::SetModulusAndSubgroupGenerator
virtual void SetModulusAndSubgroupGenerator(const Integer &p, const Integer &g)=0
Set group parameters.
NameValuePairs::GetValue
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:379
DL_GroupParameters< Integer >::IsIdentity
virtual bool IsIdentity(const Element &element) const=0
Determines if an element is an identity.
config.h
Library configuration file.
CombinedNameValuePairs
Combines two sets of NameValuePairs.
Definition: algparam.h:129
NullRNG
CRYPTOPP_DLL RandomNumberGenerator &CRYPTOPP_API NullRNG()
Random Number Generator that does not produce random numbers.
Definition: cryptlib.cpp:400
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:162
SaturatingSubtract
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition: misc.h:1073
DL_BadElement
Exception thrown when an invalid group element is encountered.
Definition: pubkey.h:772
PrimeAndGenerator::Prime
const Integer & Prime() const
Retrieve first prime.
Definition: nbtheory.h:301
NameValuePairs::GetIntValueWithDefault
CRYPTOPP_DLL int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:424
PK_FinalTemplate
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2188
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:322
BERGeneralDecoder::EndReached
bool EndReached() const
Determine end of stream.
Definition: asn.cpp:527
integer.h
Multiple precision integer with arithmetic operations.
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:50
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:525