Crypto++  5.6.5
Free C++ class library of cryptographic schemes
gfpcrypt.cpp
1 // dsa.cpp - 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<SHA>::Signer test;
27  GDSA<SHA>::Verifier test1;
28  DSA::Signer test5(NullRNG(), 100);
29  DSA::Signer test2(test5);
30  NR<SHA>::Signer test3;
31  NR<SHA>::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 = 1024, 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  int pSize = GetModulus().BitCount(), qSize = GetSubgroupOrder().BitCount();
74  pass = pass && ((pSize==1024 && qSize==160) || (pSize==2048 && qSize==224) || (pSize==2048 && qSize==256) || (pSize==3072 && qSize==256));
75  return pass;
76 }
77 
78 void DL_SignatureMessageEncodingMethod_DSA::ComputeMessageRepresentative(RandomNumberGenerator &rng,
79  const byte *recoverableMessage, size_t recoverableMessageLength,
80  HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
81  byte *representative, size_t representativeBitLength) const
82 {
83  CRYPTOPP_UNUSED(rng), CRYPTOPP_UNUSED(recoverableMessage), CRYPTOPP_UNUSED(recoverableMessageLength);
84  CRYPTOPP_UNUSED(messageEmpty), CRYPTOPP_UNUSED(hashIdentifier);
85  CRYPTOPP_ASSERT(recoverableMessageLength == 0);
86  CRYPTOPP_ASSERT(hashIdentifier.second == 0);
87 
88  const size_t representativeByteLength = BitsToBytes(representativeBitLength);
89  const size_t digestSize = hash.DigestSize();
90  const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
91 
92  memset(representative, 0, paddingLength);
93  hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
94 
95  if (digestSize*8 > representativeBitLength)
96  {
97  Integer h(representative, representativeByteLength);
98  h >>= representativeByteLength*8 - representativeBitLength;
99  h.Encode(representative, representativeByteLength);
100  }
101 }
102 
103 void DL_SignatureMessageEncodingMethod_NR::ComputeMessageRepresentative(RandomNumberGenerator &rng,
104  const byte *recoverableMessage, size_t recoverableMessageLength,
105  HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
106  byte *representative, size_t representativeBitLength) const
107 {
108  CRYPTOPP_UNUSED(rng);CRYPTOPP_UNUSED(recoverableMessage); CRYPTOPP_UNUSED(recoverableMessageLength);
109  CRYPTOPP_UNUSED(hash); CRYPTOPP_UNUSED(hashIdentifier); CRYPTOPP_UNUSED(messageEmpty);
110  CRYPTOPP_UNUSED(representative); CRYPTOPP_UNUSED(representativeBitLength);
111 
112  CRYPTOPP_ASSERT(recoverableMessageLength == 0);
113  CRYPTOPP_ASSERT(hashIdentifier.second == 0);
114  const size_t representativeByteLength = BitsToBytes(representativeBitLength);
115  const size_t digestSize = hash.DigestSize();
116  const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
117 
118  memset(representative, 0, paddingLength);
119  hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
120 
121  if (digestSize*8 >= representativeBitLength)
122  {
123  Integer h(representative, representativeByteLength);
124  h >>= representativeByteLength*8 - representativeBitLength + 1;
125  h.Encode(representative, representativeByteLength);
126  }
127 }
128 
130 {
131  const Integer &p = GetModulus(), &q = GetSubgroupOrder();
132 
133  bool pass = true;
134  pass = pass && p > Integer::One() && p.IsOdd();
135  pass = pass && q > Integer::One() && q.IsOdd();
136 
137  if (level >= 1)
138  pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero();
139  if (level >= 2)
140  pass = pass && VerifyPrime(rng, q, level-2) && VerifyPrime(rng, p, level-2);
141 
142  return pass;
143 }
144 
146 {
147  const Integer &p = GetModulus(), &q = GetSubgroupOrder();
148 
149  bool pass = true;
150  pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative();
151  pass = pass && g < p && !IsIdentity(g);
152 
153  if (level >= 1)
154  {
155  if (gpc)
156  pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g;
157  }
158  if (level >= 2)
159  {
160  if (GetFieldType() == 2)
161  pass = pass && Jacobi(g*g-4, p)==-1;
162 
163  // verifying that Lucas((p+1)/2, w, p)==2 is omitted because it's too costly
164  // and at most 1 bit is leaked if it's false
165  bool fullValidate = (GetFieldType() == 2 && level >= 3) || !FastSubgroupCheckAvailable();
166 
167  if (fullValidate && pass)
168  {
169  Integer gp = gpc ? gpc->Exponentiate(GetGroupPrecomputation(), q) : ExponentiateElement(g, q);
170  pass = pass && IsIdentity(gp);
171  }
172  else if (GetFieldType() == 1)
173  pass = pass && Jacobi(g, p) == 1;
174  }
175 
176  return pass;
177 }
178 
180 {
181  Integer p, q, g;
182 
183  if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
184  {
185  q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
186  }
187  else
188  {
189  int modulusSize, subgroupOrderSize;
190 
191  if (!alg.GetIntValue("ModulusSize", modulusSize))
192  modulusSize = alg.GetIntValueWithDefault("KeySize", 2048);
193 
194  if (!alg.GetIntValue("SubgroupOrderSize", subgroupOrderSize))
195  subgroupOrderSize = GetDefaultSubgroupOrderSize(modulusSize);
196 
198  pg.Generate(GetFieldType() == 1 ? 1 : -1, rng, modulusSize, subgroupOrderSize);
199  p = pg.Prime();
200  q = pg.SubPrime();
201  g = pg.Generator();
202  }
203 
204  Initialize(p, q, g);
205 }
206 
207 void DL_GroupParameters_IntegerBased::EncodeElement(bool reversible, const Element &element, byte *encoded) const
208 {
209  CRYPTOPP_UNUSED(reversible);
210  element.Encode(encoded, GetModulus().ByteCount());
211 }
212 
214 {
215  CRYPTOPP_UNUSED(reversible);
216  return GetModulus().ByteCount();
217 }
218 
219 Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const
220 {
221  CRYPTOPP_UNUSED(checkForGroupMembership);
222  Integer g(encoded, GetModulus().ByteCount());
223  if (!ValidateElement(1, g, NULL))
224  throw DL_BadElement();
225  return g;
226 }
227 
229 {
230  BERSequenceDecoder parameters(bt);
231  Integer p(parameters);
232  Integer q(parameters);
233  Integer g;
234  if (parameters.EndReached())
235  {
236  g = q;
237  q = ComputeGroupOrder(p) / 2;
238  }
239  else
240  g.BERDecode(parameters);
241  parameters.MessageEnd();
242 
243  SetModulusAndSubgroupGenerator(p, g);
244  SetSubgroupOrder(q);
245 }
246 
248 {
249  DERSequenceEncoder parameters(bt);
250  GetModulus().DEREncode(parameters);
251  m_q.DEREncode(parameters);
252  GetSubgroupGenerator().DEREncode(parameters);
253  parameters.MessageEnd();
254 }
255 
256 bool DL_GroupParameters_IntegerBased::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
257 {
258  return GetValueHelper<DL_GroupParameters<Element> >(this, name, valueType, pValue)
259  CRYPTOPP_GET_FUNCTION_ENTRY(Modulus);
260 }
261 
263 {
264  AssignFromHelper(this, source)
265  CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator)
266  CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder)
267  ;
268 }
269 
270 OID DL_GroupParameters_IntegerBased::GetAlgorithmID() const
271 {
272  return ASN1::id_dsa();
273 }
274 
275 void DL_GroupParameters_GFP::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
276 {
277  ModularArithmetic ma(GetModulus());
278  ma.SimultaneousExponentiate(results, base, exponents, exponentsCount);
279 }
280 
281 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::MultiplyElements(const Element &a, const Element &b) const
282 {
283  return a_times_b_mod_c(a, b, GetModulus());
284 }
285 
286 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::CascadeExponentiate(const Element &element1, const Integer &exponent1, const Element &element2, const Integer &exponent2) const
287 {
288  ModularArithmetic ma(GetModulus());
289  return ma.CascadeExponentiate(element1, exponent1, element2, exponent2);
290 }
291 
293 {
294  return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount())));
295 }
296 
297 unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const
298 {
299  return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize);
300 }
301 
302 NAMESPACE_END
303 
304 #endif
void DEREncode(BufferedTransformation &bt) const
Encode this object into a BufferedTransformation.
Definition: gfpcrypt.cpp:247
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: gfpcrypt.cpp:262
An invalid argument was detected.
Definition: cryptlib.h:184
bool ValidateElement(unsigned int level, const Integer &element, const DL_FixedBasePrecomputation< Integer > *precomp) const
Check the element for errors.
Definition: gfpcrypt.cpp:145
void BERDecode(BufferedTransformation &bt)
Decode this object from a BufferedTransformation.
Definition: gfpcrypt.cpp:228
Utility functions for the Crypto++ library.
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
Definition: integer.cpp:3369
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:345
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:350
Integer GetGroupOrder() const
Retrieves the order of the group.
Definition: gfpcrypt.h:79
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:749
virtual void TruncatedFinal(byte *digest, size_t digestSize)=0
Computes the hash of the current message.
virtual const DL_GroupPrecomputation< Element > & GetGroupPrecomputation() const =0
Retrieves the group precomputation.
ASN.1 object identifiers for algorthms and schemes.
void EncodeElement(bool reversible, const Element &element, byte *encoded) const
Encodes the element.
Definition: gfpcrypt.cpp:207
Library configuration file.
Ring of congruence classes modulo n.
Definition: modarith.h:34
Interface for random number generators.
Definition: cryptlib.h:1188
Combines two sets of NameValuePairs.
Definition: algparam.h:135
Generator of prime numbers of special forms.
Definition: nbtheory.h:148
BER Sequence Decoder.
Definition: asn.h:302
Interface for buffered transformations.
Definition: cryptlib.h:1352
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:3035
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:373
virtual const Element & GetSubgroupGenerator() const
Retrieves the subgroup generator.
Definition: pubkey.h:787
Integer GetMaxExponent() const
Retrieves the maximum exponent for the group.
Definition: gfpcrypt.cpp:292
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3305
const char * SubgroupOrderSize()
int, in bits
Definition: argnames.h:31
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:336
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Definition: gfpcrypt.cpp:70
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:337
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:382
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:500
const Integer & Generator() const
Retrieve the generator.
Definition: nbtheory.h:194
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
Definition: nbtheory.cpp:249
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:3008
const Integer & GetSubgroupOrder() const
Retrieves the subgroup order.
Definition: gfpcrypt.h:78
Multiple precision integer with arithmetic operations.
Definition: integer.h:43
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition: misc.h:847
const char * SubgroupGenerator()
Integer, ECP::Point, or EC2N::Point.
Definition: argnames.h:39
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: gfpcrypt.cpp:179
virtual bool IsIdentity(const Element &element) const =0
Determines if an element is an identity.
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: gfpcrypt.cpp:256
Exception thrown when an invalid group element is encountered.
Definition: pubkey.h:720
virtual Integer GetCofactor() const
Retrieves the cofactor.
Definition: pubkey.h:842
RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
Definition: cryptlib.cpp:402
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:477
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:62
unsigned int GetEncodedElementSize(bool reversible) const
Retrieves the encoded element's size.
Definition: gfpcrypt.cpp:213
Classes and functions for working with ANS.1 objects.
void Initialize(const DL_GroupParameters_IntegerBased &params)
Initialize a group parameters over integers.
Definition: gfpcrypt.h:42
Classes and functions for number theoretic operations.
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3391
DER Sequence Encoder.
Definition: asn.h:312
virtual unsigned int DigestSize() const =0
Provides the digest size of the hash.
Integer DecodeElement(const byte *encoded, bool checkForGroupMembership) const
Decodes the element.
Definition: gfpcrypt.cpp:219
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Check the group for errors.
Definition: gfpcrypt.cpp:129
Interface for hash functions and data processing part of MACs.
Definition: cryptlib.h:930
const char * Modulus()
Integer.
Definition: argnames.h:33
void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Generate a Prime and Generator.
Definition: nbtheory.cpp:1038
Multiple precision integer with arithmetic operations.
static const Integer & Zero()
Integer representing 0.
Definition: integer.cpp:3027
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Definition: integer.cpp:3398
Class file for performing modular arithmetic.
Crypto++ library namespace.
const Integer & Prime() const
Retrieve first prime.
Definition: nbtheory.h:186
Object Identifier.
Definition: asn.h:165
const char * SubgroupOrder()
Integer.
Definition: argnames.h:37
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: gfpcrypt.cpp:37
virtual Element ExponentiateElement(const Element &base, const Integer &exponent) const
Exponentiates an element.
Definition: pubkey.h:807
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Definition: integer.cpp:3296
const Integer & SubPrime() const
Retrieve second prime.
Definition: nbtheory.h:190
bool NotNegative() const
Determines if the Integer is non-negative.
Definition: integer.h:333
Interface for retrieving values given their names.
Definition: cryptlib.h:279
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:1954