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  }
34  else
35  {
36  int modulusSize = 1024;
37  alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
38 
39  if (!DSA::IsValidPrimeLength(modulusSize))
40  throw InvalidArgument("DSA: not a valid prime length");
41 
42  SecByteBlock seed(SHA::DIGESTSIZE);
43  Integer h;
44  int c;
45 
46  do
47  {
48  rng.GenerateBlock(seed, SHA::DIGESTSIZE);
49  } while (!DSA::GeneratePrimes(seed, SHA::DIGESTSIZE*8, c, p, modulusSize, q));
50 
51  do
52  {
53  h.Randomize(rng, 2, p-2);
54  g = a_exp_b_mod_c(h, (p-1)/q, p);
55  } while (g <= 1);
56  }
57 
58  Initialize(p, q, g);
59 }
60 
62 {
63  bool pass = DL_GroupParameters_GFP::ValidateGroup(rng, level);
64  pass = pass && DSA::IsValidPrimeLength(GetModulus().BitCount());
65  pass = pass && GetSubgroupOrder().BitCount() == 160;
66  return pass;
67 }
68 
69 void DL_SignatureMessageEncodingMethod_DSA::ComputeMessageRepresentative(RandomNumberGenerator &rng,
70  const byte *recoverableMessage, size_t recoverableMessageLength,
71  HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
72  byte *representative, size_t representativeBitLength) const
73 {
74  assert(recoverableMessageLength == 0);
75  assert(hashIdentifier.second == 0);
76  const size_t representativeByteLength = BitsToBytes(representativeBitLength);
77  const size_t digestSize = hash.DigestSize();
78  const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
79 
80  memset(representative, 0, paddingLength);
81  hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
82 
83  if (digestSize*8 > representativeBitLength)
84  {
85  Integer h(representative, representativeByteLength);
86  h >>= representativeByteLength*8 - representativeBitLength;
87  h.Encode(representative, representativeByteLength);
88  }
89 }
90 
91 void DL_SignatureMessageEncodingMethod_NR::ComputeMessageRepresentative(RandomNumberGenerator &rng,
92  const byte *recoverableMessage, size_t recoverableMessageLength,
93  HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
94  byte *representative, size_t representativeBitLength) const
95 {
96  assert(recoverableMessageLength == 0);
97  assert(hashIdentifier.second == 0);
98  const size_t representativeByteLength = BitsToBytes(representativeBitLength);
99  const size_t digestSize = hash.DigestSize();
100  const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
101 
102  memset(representative, 0, paddingLength);
103  hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
104 
105  if (digestSize*8 >= representativeBitLength)
106  {
107  Integer h(representative, representativeByteLength);
108  h >>= representativeByteLength*8 - representativeBitLength + 1;
109  h.Encode(representative, representativeByteLength);
110  }
111 }
112 
113 bool DL_GroupParameters_IntegerBased::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
114 {
115  const Integer &p = GetModulus(), &q = GetSubgroupOrder();
116 
117  bool pass = true;
118  pass = pass && p > Integer::One() && p.IsOdd();
119  pass = pass && q > Integer::One() && q.IsOdd();
120 
121  if (level >= 1)
122  pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero();
123  if (level >= 2)
124  pass = pass && VerifyPrime(rng, q, level-2) && VerifyPrime(rng, p, level-2);
125 
126  return pass;
127 }
128 
129 bool DL_GroupParameters_IntegerBased::ValidateElement(unsigned int level, const Integer &g, const DL_FixedBasePrecomputation<Integer> *gpc) const
130 {
131  const Integer &p = GetModulus(), &q = GetSubgroupOrder();
132 
133  bool pass = true;
134  pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative();
135  pass = pass && g < p && !IsIdentity(g);
136 
137  if (level >= 1)
138  {
139  if (gpc)
140  pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g;
141  }
142  if (level >= 2)
143  {
144  if (GetFieldType() == 2)
145  pass = pass && Jacobi(g*g-4, p)==-1;
146 
147  // verifying that Lucas((p+1)/2, w, p)==2 is omitted because it's too costly
148  // and at most 1 bit is leaked if it's false
149  bool fullValidate = (GetFieldType() == 2 && level >= 3) || !FastSubgroupCheckAvailable();
150 
151  if (fullValidate && pass)
152  {
153  Integer gp = gpc ? gpc->Exponentiate(GetGroupPrecomputation(), q) : ExponentiateElement(g, q);
154  pass = pass && IsIdentity(gp);
155  }
156  else if (GetFieldType() == 1)
157  pass = pass && Jacobi(g, p) == 1;
158  }
159 
160  return pass;
161 }
162 
164 {
165  Integer p, q, g;
166 
167  if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
168  {
169  q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
170  }
171  else
172  {
173  int modulusSize, subgroupOrderSize;
174 
175  if (!alg.GetIntValue("ModulusSize", modulusSize))
176  modulusSize = alg.GetIntValueWithDefault("KeySize", 2048);
177 
178  if (!alg.GetIntValue("SubgroupOrderSize", subgroupOrderSize))
179  subgroupOrderSize = GetDefaultSubgroupOrderSize(modulusSize);
180 
182  pg.Generate(GetFieldType() == 1 ? 1 : -1, rng, modulusSize, subgroupOrderSize);
183  p = pg.Prime();
184  q = pg.SubPrime();
185  g = pg.Generator();
186  }
187 
188  Initialize(p, q, g);
189 }
190 
191 Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const
192 {
193  Integer g(encoded, GetModulus().ByteCount());
194  if (!ValidateElement(1, g, NULL))
195  throw DL_BadElement();
196  return g;
197 }
198 
200 {
201  BERSequenceDecoder parameters(bt);
202  Integer p(parameters);
203  Integer q(parameters);
204  Integer g;
205  if (parameters.EndReached())
206  {
207  g = q;
208  q = ComputeGroupOrder(p) / 2;
209  }
210  else
211  g.BERDecode(parameters);
212  parameters.MessageEnd();
213 
214  SetModulusAndSubgroupGenerator(p, g);
215  SetSubgroupOrder(q);
216 }
217 
219 {
220  DERSequenceEncoder parameters(bt);
221  GetModulus().DEREncode(parameters);
222  m_q.DEREncode(parameters);
223  GetSubgroupGenerator().DEREncode(parameters);
224  parameters.MessageEnd();
225 }
226 
227 bool DL_GroupParameters_IntegerBased::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
228 {
229  return GetValueHelper<DL_GroupParameters<Element> >(this, name, valueType, pValue)
230  CRYPTOPP_GET_FUNCTION_ENTRY(Modulus);
231 }
232 
234 {
235  AssignFromHelper(this, source)
236  CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator)
237  CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder)
238  ;
239 }
240 
241 OID DL_GroupParameters_IntegerBased::GetAlgorithmID() const
242 {
243  return ASN1::id_dsa();
244 }
245 
246 void DL_GroupParameters_GFP::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
247 {
248  ModularArithmetic ma(GetModulus());
249  ma.SimultaneousExponentiate(results, base, exponents, exponentsCount);
250 }
251 
252 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::MultiplyElements(const Element &a, const Element &b) const
253 {
254  return a_times_b_mod_c(a, b, GetModulus());
255 }
256 
257 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::CascadeExponentiate(const Element &element1, const Integer &exponent1, const Element &element2, const Integer &exponent2) const
258 {
259  ModularArithmetic ma(GetModulus());
260  return ma.CascadeExponentiate(element1, exponent1, element2, exponent2);
261 }
262 
263 Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const
264 {
265  return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount())));
266 }
267 
268 unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const
269 {
270  return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize);
271 }
272 
273 NAMESPACE_END
274 
275 #endif