Crypto++
|
00001 // dsa.cpp - written and placed in the public domain by Wei Dai 00002 00003 #include "pch.h" 00004 00005 #ifndef CRYPTOPP_IMPORTS 00006 00007 #include "gfpcrypt.h" 00008 #include "asn.h" 00009 #include "oids.h" 00010 #include "nbtheory.h" 00011 00012 NAMESPACE_BEGIN(CryptoPP) 00013 00014 void TestInstantiations_gfpcrypt() 00015 { 00016 GDSA<SHA>::Signer test; 00017 GDSA<SHA>::Verifier test1; 00018 DSA::Signer test5(NullRNG(), 100); 00019 DSA::Signer test2(test5); 00020 NR<SHA>::Signer test3; 00021 NR<SHA>::Verifier test4; 00022 DLIES<>::Encryptor test6; 00023 DLIES<>::Decryptor test7; 00024 } 00025 00026 void DL_GroupParameters_DSA::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 00027 { 00028 Integer p, q, g; 00029 00030 if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g)) 00031 { 00032 q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2); 00033 } 00034 else 00035 { 00036 int modulusSize = 1024; 00037 alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize); 00038 00039 if (!DSA::IsValidPrimeLength(modulusSize)) 00040 throw InvalidArgument("DSA: not a valid prime length"); 00041 00042 SecByteBlock seed(SHA::DIGESTSIZE); 00043 Integer h; 00044 int c; 00045 00046 do 00047 { 00048 rng.GenerateBlock(seed, SHA::DIGESTSIZE); 00049 } while (!DSA::GeneratePrimes(seed, SHA::DIGESTSIZE*8, c, p, modulusSize, q)); 00050 00051 do 00052 { 00053 h.Randomize(rng, 2, p-2); 00054 g = a_exp_b_mod_c(h, (p-1)/q, p); 00055 } while (g <= 1); 00056 } 00057 00058 Initialize(p, q, g); 00059 } 00060 00061 bool DL_GroupParameters_DSA::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const 00062 { 00063 bool pass = DL_GroupParameters_GFP::ValidateGroup(rng, level); 00064 pass = pass && DSA::IsValidPrimeLength(GetModulus().BitCount()); 00065 pass = pass && GetSubgroupOrder().BitCount() == 160; 00066 return pass; 00067 } 00068 00069 void DL_SignatureMessageEncodingMethod_DSA::ComputeMessageRepresentative(RandomNumberGenerator &rng, 00070 const byte *recoverableMessage, size_t recoverableMessageLength, 00071 HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty, 00072 byte *representative, size_t representativeBitLength) const 00073 { 00074 assert(recoverableMessageLength == 0); 00075 assert(hashIdentifier.second == 0); 00076 const size_t representativeByteLength = BitsToBytes(representativeBitLength); 00077 const size_t digestSize = hash.DigestSize(); 00078 const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize); 00079 00080 memset(representative, 0, paddingLength); 00081 hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize)); 00082 00083 if (digestSize*8 > representativeBitLength) 00084 { 00085 Integer h(representative, representativeByteLength); 00086 h >>= representativeByteLength*8 - representativeBitLength; 00087 h.Encode(representative, representativeByteLength); 00088 } 00089 } 00090 00091 void DL_SignatureMessageEncodingMethod_NR::ComputeMessageRepresentative(RandomNumberGenerator &rng, 00092 const byte *recoverableMessage, size_t recoverableMessageLength, 00093 HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty, 00094 byte *representative, size_t representativeBitLength) const 00095 { 00096 assert(recoverableMessageLength == 0); 00097 assert(hashIdentifier.second == 0); 00098 const size_t representativeByteLength = BitsToBytes(representativeBitLength); 00099 const size_t digestSize = hash.DigestSize(); 00100 const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize); 00101 00102 memset(representative, 0, paddingLength); 00103 hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize)); 00104 00105 if (digestSize*8 >= representativeBitLength) 00106 { 00107 Integer h(representative, representativeByteLength); 00108 h >>= representativeByteLength*8 - representativeBitLength + 1; 00109 h.Encode(representative, representativeByteLength); 00110 } 00111 } 00112 00113 bool DL_GroupParameters_IntegerBased::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const 00114 { 00115 const Integer &p = GetModulus(), &q = GetSubgroupOrder(); 00116 00117 bool pass = true; 00118 pass = pass && p > Integer::One() && p.IsOdd(); 00119 pass = pass && q > Integer::One() && q.IsOdd(); 00120 00121 if (level >= 1) 00122 pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero(); 00123 if (level >= 2) 00124 pass = pass && VerifyPrime(rng, q, level-2) && VerifyPrime(rng, p, level-2); 00125 00126 return pass; 00127 } 00128 00129 bool DL_GroupParameters_IntegerBased::ValidateElement(unsigned int level, const Integer &g, const DL_FixedBasePrecomputation<Integer> *gpc) const 00130 { 00131 const Integer &p = GetModulus(), &q = GetSubgroupOrder(); 00132 00133 bool pass = true; 00134 pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative(); 00135 pass = pass && g < p && !IsIdentity(g); 00136 00137 if (level >= 1) 00138 { 00139 if (gpc) 00140 pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g; 00141 } 00142 if (level >= 2) 00143 { 00144 if (GetFieldType() == 2) 00145 pass = pass && Jacobi(g*g-4, p)==-1; 00146 00147 // verifying that Lucas((p+1)/2, w, p)==2 is omitted because it's too costly 00148 // and at most 1 bit is leaked if it's false 00149 bool fullValidate = (GetFieldType() == 2 && level >= 3) || !FastSubgroupCheckAvailable(); 00150 00151 if (fullValidate && pass) 00152 { 00153 Integer gp = gpc ? gpc->Exponentiate(GetGroupPrecomputation(), q) : ExponentiateElement(g, q); 00154 pass = pass && IsIdentity(gp); 00155 } 00156 else if (GetFieldType() == 1) 00157 pass = pass && Jacobi(g, p) == 1; 00158 } 00159 00160 return pass; 00161 } 00162 00163 void DL_GroupParameters_IntegerBased::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 00164 { 00165 Integer p, q, g; 00166 00167 if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g)) 00168 { 00169 q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2); 00170 } 00171 else 00172 { 00173 int modulusSize, subgroupOrderSize; 00174 00175 if (!alg.GetIntValue("ModulusSize", modulusSize)) 00176 modulusSize = alg.GetIntValueWithDefault("KeySize", 2048); 00177 00178 if (!alg.GetIntValue("SubgroupOrderSize", subgroupOrderSize)) 00179 subgroupOrderSize = GetDefaultSubgroupOrderSize(modulusSize); 00180 00181 PrimeAndGenerator pg; 00182 pg.Generate(GetFieldType() == 1 ? 1 : -1, rng, modulusSize, subgroupOrderSize); 00183 p = pg.Prime(); 00184 q = pg.SubPrime(); 00185 g = pg.Generator(); 00186 } 00187 00188 Initialize(p, q, g); 00189 } 00190 00191 Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const 00192 { 00193 Integer g(encoded, GetModulus().ByteCount()); 00194 if (!ValidateElement(1, g, NULL)) 00195 throw DL_BadElement(); 00196 return g; 00197 } 00198 00199 void DL_GroupParameters_IntegerBased::BERDecode(BufferedTransformation &bt) 00200 { 00201 BERSequenceDecoder parameters(bt); 00202 Integer p(parameters); 00203 Integer q(parameters); 00204 Integer g; 00205 if (parameters.EndReached()) 00206 { 00207 g = q; 00208 q = ComputeGroupOrder(p) / 2; 00209 } 00210 else 00211 g.BERDecode(parameters); 00212 parameters.MessageEnd(); 00213 00214 SetModulusAndSubgroupGenerator(p, g); 00215 SetSubgroupOrder(q); 00216 } 00217 00218 void DL_GroupParameters_IntegerBased::DEREncode(BufferedTransformation &bt) const 00219 { 00220 DERSequenceEncoder parameters(bt); 00221 GetModulus().DEREncode(parameters); 00222 m_q.DEREncode(parameters); 00223 GetSubgroupGenerator().DEREncode(parameters); 00224 parameters.MessageEnd(); 00225 } 00226 00227 bool DL_GroupParameters_IntegerBased::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 00228 { 00229 return GetValueHelper<DL_GroupParameters<Element> >(this, name, valueType, pValue) 00230 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus); 00231 } 00232 00233 void DL_GroupParameters_IntegerBased::AssignFrom(const NameValuePairs &source) 00234 { 00235 AssignFromHelper(this, source) 00236 CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator) 00237 CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder) 00238 ; 00239 } 00240 00241 OID DL_GroupParameters_IntegerBased::GetAlgorithmID() const 00242 { 00243 return ASN1::id_dsa(); 00244 } 00245 00246 void DL_GroupParameters_GFP::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const 00247 { 00248 ModularArithmetic ma(GetModulus()); 00249 ma.SimultaneousExponentiate(results, base, exponents, exponentsCount); 00250 } 00251 00252 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::MultiplyElements(const Element &a, const Element &b) const 00253 { 00254 return a_times_b_mod_c(a, b, GetModulus()); 00255 } 00256 00257 DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::CascadeExponentiate(const Element &element1, const Integer &exponent1, const Element &element2, const Integer &exponent2) const 00258 { 00259 ModularArithmetic ma(GetModulus()); 00260 return ma.CascadeExponentiate(element1, exponent1, element2, exponent2); 00261 } 00262 00263 Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const 00264 { 00265 return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount()))); 00266 } 00267 00268 unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const 00269 { 00270 return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize); 00271 } 00272 00273 NAMESPACE_END 00274 00275 #endif