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 12NAMESPACE_BEGIN(CryptoPP) 13 14void 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 26void DL_GroupParameters_DSA::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 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 61bool DL_GroupParameters_DSA::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const 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 69void 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 91void 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 113bool 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 129bool 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 163void DL_GroupParameters_IntegerBased::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 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 181 PrimeAndGenerator pg; 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 191Integer 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 199void DL_GroupParameters_IntegerBased::BERDecode(BufferedTransformation &bt) 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 218void DL_GroupParameters_IntegerBased::DEREncode(BufferedTransformation &bt) const 219{ 220 DERSequenceEncoder parameters(bt); 221 GetModulus().DEREncode(parameters); 222 m_q.DEREncode(parameters); 223 GetSubgroupGenerator().DEREncode(parameters); 224 parameters.MessageEnd(); 225} 226 227bool 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 233void DL_GroupParameters_IntegerBased::AssignFrom(const NameValuePairs &source) 234{ 235 AssignFromHelper(this, source) 236 CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator) 237 CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder) 238 ; 239} 240 241OID DL_GroupParameters_IntegerBased::GetAlgorithmID() const 242{ 243 return ASN1::id_dsa(); 244} 245 246void 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 252DL_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 257DL_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 263Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const 264{ 265 return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount()))); 266} 267 268unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const 269{ 270 return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize); 271} 272 273NAMESPACE_END 274 275#endif 276