Crypto++
gfpcrypt.cpp
1 // dsa.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 
5 #ifndef CRYPTOPP_IMPORTS
6 
7 #include "gfpcrypt.h"
8 #include "asn.h"
9 #include "oids.h"
10 #include "nbtheory.h"
11 
12 NAMESPACE_BEGIN(CryptoPP)
13 
14 void TestInstantiations_gfpcrypt()
15 {
16  GDSA<SHA>::Signer test;
17  GDSA<SHA>::Verifier test1;
18  DSA::Signer test5(NullRNG(), 100);
19  DSA::Signer test2(test5);
20  NR<SHA>::Signer test3;
21  NR<SHA>::Verifier test4;
22  DLIES<>::Encryptor test6;
23  DLIES<>::Decryptor test7;
24 }
25 
27 {
28  Integer p, q, g;
29 
30  if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
31  {
32  q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
33  Initialize(p, q, g);
34  }
35  else
36  {
37  int modulusSize = 1024, defaultSubgroupOrderSize;
38  alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
39 
40  switch (modulusSize)
41  {
42  case 1024:
43  defaultSubgroupOrderSize = 160;
44  break;
45  case 2048:
46  defaultSubgroupOrderSize = 224;
47  break;
48  case 3072:
49  defaultSubgroupOrderSize = 256;
50  break;
51  default:
52  throw InvalidArgument("DSA: not a valid prime length");
53  }
54 
55  DL_GroupParameters_GFP::GenerateRandom(rng, CombinedNameValuePairs(alg, MakeParameters(Name::SubgroupOrderSize(), defaultSubgroupOrderSize, false)));
56  }
57 }
58 
60 {
61  bool pass = DL_GroupParameters_GFP::ValidateGroup(rng, level);
62  int pSize = GetModulus().BitCount(), qSize = GetSubgroupOrder().BitCount();
63  pass = pass && ((pSize==1024 && qSize==160) || (pSize==2048 && qSize==224) || (pSize==2048 && qSize==256) || (pSize==3072 && qSize==256));
64  return pass;
65 }
66 
67 void DL_SignatureMessageEncodingMethod_DSA::ComputeMessageRepresentative(RandomNumberGenerator &rng,
68  const byte *recoverableMessage, size_t recoverableMessageLength,
69  HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
70  byte *representative, size_t representativeBitLength) const
71 {
72  assert(recoverableMessageLength == 0);
73  assert(hashIdentifier.second == 0);
74  const size_t representativeByteLength = BitsToBytes(representativeBitLength);
75  const size_t digestSize = hash.DigestSize();
76  const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
77 
78  memset(representative, 0, paddingLength);
79  hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
80 
81  if (digestSize*8 > representativeBitLength)
82  {
83  Integer h(representative, representativeByteLength);
84  h >>= representativeByteLength*8 - representativeBitLength;
85  h.Encode(representative, representativeByteLength);
86  }
87 }
88 
89 void DL_SignatureMessageEncodingMethod_NR::ComputeMessageRepresentative(RandomNumberGenerator &rng,
90  const byte *recoverableMessage, size_t recoverableMessageLength,
91  HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
92  byte *representative, size_t representativeBitLength) const
93 {
94  assert(recoverableMessageLength == 0);
95  assert(hashIdentifier.second == 0);
96  const size_t representativeByteLength = BitsToBytes(representativeBitLength);
97  const size_t digestSize = hash.DigestSize();
98  const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
99 
100  memset(representative, 0, paddingLength);
101  hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
102 
103  if (digestSize*8 >= representativeBitLength)
104  {
105  Integer h(representative, representativeByteLength);
106  h >>= representativeByteLength*8 - representativeBitLength + 1;
107  h.Encode(representative, representativeByteLength);
108  }
109 }
110 
111 bool DL_GroupParameters_IntegerBased::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
112 {
113  const Integer &p = GetModulus(), &q = GetSubgroupOrder();
114 
115  bool pass = true;
116  pass = pass && p > Integer::One() && p.IsOdd();
117  pass = pass && q > Integer::One() && q.IsOdd();
118 
119  if (level >= 1)
120  pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero();
121  if (level >= 2)
122  pass = pass && VerifyPrime(rng, q, level-2) && VerifyPrime(rng, p, level-2);
123 
124  return pass;
125 }
126 
127 bool DL_GroupParameters_IntegerBased::ValidateElement(unsigned int level, const Integer &g, const DL_FixedBasePrecomputation<Integer> *gpc) const
128 {
129  const Integer &p = GetModulus(), &q = GetSubgroupOrder();
130 
131  bool pass = true;
132  pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative();
133  pass = pass && g < p && !IsIdentity(g);
134 
135  if (level >= 1)
136  {
137  if (gpc)
138  pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g;
139  }
140  if (level >= 2)
141  {
142  if (GetFieldType() == 2)
143  pass = pass && Jacobi(g*g-4, p)==-1;
144 
145  // verifying that Lucas((p+1)/2, w, p)==2 is omitted because it's too costly
146  // and at most 1 bit is leaked if it's false
147  bool fullValidate = (GetFieldType() == 2 && level >= 3) || !FastSubgroupCheckAvailable();
148 
149  if (fullValidate && pass)
150  {
151  Integer gp = gpc ? gpc->Exponentiate(GetGroupPrecomputation(), q) : ExponentiateElement(g, q);
152  pass = pass && IsIdentity(gp);
153  }
154  else if (GetFieldType() == 1)
155  pass = pass && Jacobi(g, p) == 1;
156  }
157 
158  return pass;
159 }
160 
162 {
163  Integer p, q, g;
164 
165  if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
166  {
167  q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
168  }
169  else
170  {
171  int modulusSize, subgroupOrderSize;
172 
173  if (!alg.GetIntValue("ModulusSize", modulusSize))
174  modulusSize = alg.GetIntValueWithDefault("KeySize", 2048);
175 
176  if (!alg.GetIntValue("SubgroupOrderSize", subgroupOrderSize))
177  subgroupOrderSize = GetDefaultSubgroupOrderSize(modulusSize);
178 
180  pg.Generate(GetFieldType() == 1 ? 1 : -1, rng, modulusSize, subgroupOrderSize);
181  p = pg.Prime();
182  q = pg.SubPrime();
183  g = pg.Generator();
184  }
185 
186  Initialize(p, q, g);
187 }
188 
189 Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const
190 {
191  Integer g(encoded, GetModulus().ByteCount());
192  if (!ValidateElement(1, g, NULL))
193  throw DL_BadElement();
194  return g;
195 }
196 
198 {
199  BERSequenceDecoder parameters(bt);
200  Integer p(parameters);
201  Integer q(parameters);
202  Integer g;
203  if (parameters.EndReached())
204  {
205  g = q;
206  q = ComputeGroupOrder(p) / 2;
207  }
208  else
209  g.BERDecode(parameters);
210  parameters.MessageEnd();
211 
212  SetModulusAndSubgroupGenerator(p, g);
213  SetSubgroupOrder(q);
214 }
215 
217 {
218  DERSequenceEncoder parameters(bt);
219  GetModulus().DEREncode(parameters);
220  m_q.DEREncode(parameters);
221  GetSubgroupGenerator().DEREncode(parameters);
222  parameters.MessageEnd();
223 }
224 
225 bool DL_GroupParameters_IntegerBased::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
226 {
227  return GetValueHelper<DL_GroupParameters<Element> >(this, name, valueType, pValue)
228  CRYPTOPP_GET_FUNCTION_ENTRY(Modulus);
229 }
230 
232 {
233  AssignFromHelper(this, source)
234  CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator)
235  CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder)
236  ;
237 }
238 
239 OID DL_GroupParameters_IntegerBased::GetAlgorithmID() const
240 {
241  return ASN1::id_dsa();
242 }
243 
244 void DL_GroupParameters_GFP::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
245 {
246  ModularArithmetic ma(GetModulus());
247  ma.SimultaneousExponentiate(results, base, exponents, exponentsCount);
248 }
249 
250 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::MultiplyElements(const Element &a, const Element &b) const
251 {
252  return a_times_b_mod_c(a, b, GetModulus());
253 }
254 
255 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::CascadeExponentiate(const Element &element1, const Integer &exponent1, const Element &element2, const Integer &exponent2) const
256 {
257  ModularArithmetic ma(GetModulus());
258  return ma.CascadeExponentiate(element1, exponent1, element2, exponent2);
259 }
260 
261 Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const
262 {
263  return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount())));
264 }
265 
266 unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const
267 {
268  return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize);
269 }
270 
271 NAMESPACE_END
272 
273 #endif
void DEREncode(BufferedTransformation &bt) const
encode this object into a BufferedTransformation, using DER (Distinguished Encoding Rules) ...
Definition: gfpcrypt.cpp:216
void AssignFrom(const NameValuePairs &source)
assign values from source to this object
Definition: gfpcrypt.cpp:231
exception thrown when an invalid argument is detected
Definition: cryptlib.h:145
void BERDecode(BufferedTransformation &bt)
decode this object from a BufferedTransformation, using BER (Basic Encoding Rules) ...
Definition: gfpcrypt.cpp:197
T GetValueWithDefault(const char *name, T defaultValue) const
get a named value, returns the default if the name doesn&#39;t exist
Definition: cryptlib.h:269
virtual void TruncatedFinal(byte *digest, size_t digestSize)=0
truncated version of Final()
ring of congruence classes modulo n
Definition: modarith.h:19
interface for random number generators
Definition: cryptlib.h:669
generator of prime numbers of special forms
Definition: nbtheory.h:105
BER Sequence Decoder.
Definition: asn.h:177
interface for buffered transformations
Definition: cryptlib.h:771
static const Integer & One()
avoid calling constructors for these frequently used integers
Definition: integer.cpp:2867
bool GetIntValue(const char *name, int &value) const
get a named value with type int
Definition: cryptlib.h:282
unsigned int BitCount() const
number of significant bits = floor(log2(abs(*this))) + 1
Definition: integer.cpp:3054
const char * SubgroupOrderSize()
int, in bits
Definition: argnames.h:25
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Definition: gfpcrypt.cpp:59
bool GetValue(const char *name, T &value) const
get a named value, returns true if the name exists
Definition: cryptlib.h:262
int GetIntValueWithDefault(const char *name, int defaultValue) const
get a named value with type int, with default
Definition: cryptlib.h:286
static Integer Power2(size_t e)
return the integer 2**e
Definition: integer.cpp:2846
multiple precision integer and basic arithmetics
Definition: integer.h:26
Implementation of schemes based on DL over GF(p)
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: gfpcrypt.cpp:161
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
to be implemented by derived classes, users should use one of the above functions instead ...
Definition: gfpcrypt.cpp:225
to be thrown by DecodeElement and AgreeWithStaticPrivateKey
Definition: pubkey.h:513
RandomNumberGenerator & NullRNG()
returns a reference that can be passed to functions that ask for a RNG but doesn&#39;t actually use it ...
Definition: cryptlib.cpp:295
void DEREncode(BufferedTransformation &bt) const
encode using Distinguished Encoding Rules, put result into a BufferedTransformation object ...
Definition: integer.cpp:3133
DER Sequence Encoder.
Definition: asn.h:187
virtual unsigned int DigestSize() const =0
size of the hash/digest/MAC returned by Final()
interface for hash functions and data processing part of MACs
Definition: cryptlib.h:531
static const Integer & Zero()
avoid calling constructors for these frequently used integers
Definition: integer.cpp:2862
Object Identifier.
Definition: asn.h:82
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: gfpcrypt.cpp:26
interface for retrieving values given their names
Definition: cryptlib.h:225
A template implementing constructors for public key algorithm classes.
Definition: pubkey.h:1488