gfpcrypt.cpp
// dsa.cpp - written and placed in the public domain by Wei Dai
#include "pch.h"
#include "config.h"
// TODO: fix the C4589 warnings
#if CRYPTOPP_MSC_VERSION
# pragma warning(disable: 4189 4589)
#endif
#ifndef CRYPTOPP_IMPORTS
#include "gfpcrypt.h"
#include "nbtheory.h"
#include "modarith.h"
#include "integer.h"
#include "asn.h"
#include "oids.h"
#include "misc.h"
NAMESPACE_BEGIN(CryptoPP)
#if !defined(NDEBUG) && !defined(CRYPTOPP_DOXYGEN_PROCESSING)
void TestInstantiations_gfpcrypt()
{
GDSA<SHA>::Signer test;
GDSA<SHA>::Verifier test1;
DSA::Signer test5(NullRNG(), 100);
DSA::Signer test2(test5);
NR<SHA>::Signer test3;
NR<SHA>::Verifier test4;
DLIES<>::Encryptor test6;
DLIES<>::Decryptor test7;
}
#endif
void DL_GroupParameters_DSA::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
{
Integer p, q, g;
if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
{
q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
Initialize(p, q, g);
}
else
{
int modulusSize = 1024, defaultSubgroupOrderSize;
alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
switch (modulusSize)
{
case 1024:
defaultSubgroupOrderSize = 160;
break;
case 2048:
defaultSubgroupOrderSize = 224;
break;
case 3072:
defaultSubgroupOrderSize = 256;
break;
default:
throw InvalidArgument("DSA: not a valid prime length");
}
DL_GroupParameters_GFP::GenerateRandom(rng, CombinedNameValuePairs(alg, MakeParameters(Name::SubgroupOrderSize(), defaultSubgroupOrderSize, false)));
}
}
bool DL_GroupParameters_DSA::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
{
bool pass = DL_GroupParameters_GFP::ValidateGroup(rng, level);
int pSize = GetModulus().BitCount(), qSize = GetSubgroupOrder().BitCount();
pass = pass && ((pSize==1024 && qSize==160) || (pSize==2048 && qSize==224) || (pSize==2048 && qSize==256) || (pSize==3072 && qSize==256));
return pass;
}
void DL_SignatureMessageEncodingMethod_DSA::ComputeMessageRepresentative(RandomNumberGenerator &rng,
const byte *recoverableMessage, size_t recoverableMessageLength,
HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
byte *representative, size_t representativeBitLength) const
{
CRYPTOPP_UNUSED(rng), CRYPTOPP_UNUSED(recoverableMessage), CRYPTOPP_UNUSED(recoverableMessageLength);
CRYPTOPP_UNUSED(messageEmpty), CRYPTOPP_UNUSED(hashIdentifier);
assert(recoverableMessageLength == 0);
assert(hashIdentifier.second == 0);
const size_t representativeByteLength = BitsToBytes(representativeBitLength);
const size_t digestSize = hash.DigestSize();
const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
memset(representative, 0, paddingLength);
hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
if (digestSize*8 > representativeBitLength)
{
Integer h(representative, representativeByteLength);
h >>= representativeByteLength*8 - representativeBitLength;
h.Encode(representative, representativeByteLength);
}
}
void DL_SignatureMessageEncodingMethod_NR::ComputeMessageRepresentative(RandomNumberGenerator &rng,
const byte *recoverableMessage, size_t recoverableMessageLength,
HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
byte *representative, size_t representativeBitLength) const
{
CRYPTOPP_UNUSED(rng);CRYPTOPP_UNUSED(recoverableMessage); CRYPTOPP_UNUSED(recoverableMessageLength);
CRYPTOPP_UNUSED(hash); CRYPTOPP_UNUSED(hashIdentifier); CRYPTOPP_UNUSED(messageEmpty);
CRYPTOPP_UNUSED(representative); CRYPTOPP_UNUSED(representativeBitLength);
assert(recoverableMessageLength == 0);
assert(hashIdentifier.second == 0);
const size_t representativeByteLength = BitsToBytes(representativeBitLength);
const size_t digestSize = hash.DigestSize();
const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
memset(representative, 0, paddingLength);
hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
if (digestSize*8 >= representativeBitLength)
{
Integer h(representative, representativeByteLength);
h >>= representativeByteLength*8 - representativeBitLength + 1;
h.Encode(representative, representativeByteLength);
}
}
bool DL_GroupParameters_IntegerBased::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
{
const Integer &p = GetModulus(), &q = GetSubgroupOrder();
bool pass = true;
pass = pass && p > Integer::One() && p.IsOdd();
pass = pass && q > Integer::One() && q.IsOdd();
if (level >= 1)
pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero();
if (level >= 2)
pass = pass && VerifyPrime(rng, q, level-2) && VerifyPrime(rng, p, level-2);
return pass;
}
bool DL_GroupParameters_IntegerBased::ValidateElement(unsigned int level, const Integer &g, const DL_FixedBasePrecomputation<Integer> *gpc) const
{
const Integer &p = GetModulus(), &q = GetSubgroupOrder();
bool pass = true;
pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative();
pass = pass && g < p && !IsIdentity(g);
if (level >= 1)
{
if (gpc)
pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g;
}
if (level >= 2)
{
if (GetFieldType() == 2)
pass = pass && Jacobi(g*g-4, p)==-1;
// verifying that Lucas((p+1)/2, w, p)==2 is omitted because it's too costly
// and at most 1 bit is leaked if it's false
bool fullValidate = (GetFieldType() == 2 && level >= 3) || !FastSubgroupCheckAvailable();
if (fullValidate && pass)
{
Integer gp = gpc ? gpc->Exponentiate(GetGroupPrecomputation(), q) : ExponentiateElement(g, q);
pass = pass && IsIdentity(gp);
}
else if (GetFieldType() == 1)
pass = pass && Jacobi(g, p) == 1;
}
return pass;
}
void DL_GroupParameters_IntegerBased::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
{
Integer p, q, g;
if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
{
q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
}
else
{
int modulusSize, subgroupOrderSize;
if (!alg.GetIntValue("ModulusSize", modulusSize))
modulusSize = alg.GetIntValueWithDefault("KeySize", 2048);
if (!alg.GetIntValue("SubgroupOrderSize", subgroupOrderSize))
subgroupOrderSize = GetDefaultSubgroupOrderSize(modulusSize);
PrimeAndGenerator pg;
pg.Generate(GetFieldType() == 1 ? 1 : -1, rng, modulusSize, subgroupOrderSize);
p = pg.Prime();
q = pg.SubPrime();
g = pg.Generator();
}
Initialize(p, q, g);
}
#ifndef CRYPTOPP_MAINTAIN_BACKWARDS_COMPATIBILITY_562
void DL_GroupParameters_IntegerBased::EncodeElement(bool reversible, const Element &element, byte *encoded) const
{
CRYPTOPP_UNUSED(reversible);
element.Encode(encoded, GetModulus().ByteCount());
}
unsigned int DL_GroupParameters_IntegerBased::GetEncodedElementSize(bool reversible) const
{
CRYPTOPP_UNUSED(reversible);
return GetModulus().ByteCount();
}
#endif
Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const
{
CRYPTOPP_UNUSED(checkForGroupMembership);
Integer g(encoded, GetModulus().ByteCount());
if (!ValidateElement(1, g, NULL))
throw DL_BadElement();
return g;
}
void DL_GroupParameters_IntegerBased::BERDecode(BufferedTransformation &bt)
{
BERSequenceDecoder parameters(bt);
Integer p(parameters);
Integer q(parameters);
Integer g;
if (parameters.EndReached())
{
g = q;
q = ComputeGroupOrder(p) / 2;
}
else
g.BERDecode(parameters);
parameters.MessageEnd();
SetModulusAndSubgroupGenerator(p, g);
SetSubgroupOrder(q);
}
void DL_GroupParameters_IntegerBased::DEREncode(BufferedTransformation &bt) const
{
DERSequenceEncoder parameters(bt);
GetModulus().DEREncode(parameters);
m_q.DEREncode(parameters);
GetSubgroupGenerator().DEREncode(parameters);
parameters.MessageEnd();
}
bool DL_GroupParameters_IntegerBased::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
{
return GetValueHelper<DL_GroupParameters<Element> >(this, name, valueType, pValue)
CRYPTOPP_GET_FUNCTION_ENTRY(Modulus);
}
void DL_GroupParameters_IntegerBased::AssignFrom(const NameValuePairs &source)
{
AssignFromHelper(this, source)
CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator)
CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder)
;
}
OID DL_GroupParameters_IntegerBased::GetAlgorithmID() const
{
return ASN1::id_dsa();
}
void DL_GroupParameters_GFP::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
{
ModularArithmetic ma(GetModulus());
ma.SimultaneousExponentiate(results, base, exponents, exponentsCount);
}
DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::MultiplyElements(const Element &a, const Element &b) const
{
return a_times_b_mod_c(a, b, GetModulus());
}
DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::CascadeExponentiate(const Element &element1, const Integer &exponent1, const Element &element2, const Integer &exponent2) const
{
ModularArithmetic ma(GetModulus());
return ma.CascadeExponentiate(element1, exponent1, element2, exponent2);
}
Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const
{
return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount())));
}
unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const
{
return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize);
}
NAMESPACE_END
#endif
NameValuePairs::GetValueWithDefault
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:348
MakeParameters
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:554
DL_GroupParameters_IntegerBased::AssignFrom
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: gfpcrypt.cpp:264
nbtheory.h
Classes and functions for number theoretic operations.
Integer::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3372
DL_GroupParameters_IntegerBased::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: gfpcrypt.cpp:179
DL_GroupParameters< Integer >::GetCofactor
virtual Integer GetCofactor() const
Retrieves the cofactor.
Definition: pubkey.h:866
HashTransformation::TruncatedFinal
virtual void TruncatedFinal(byte *digest, size_t digestSize)=0
Computes the hash of the current message.
NameValuePairs::GetIntValueWithDefault
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:380
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:305
Integer::One
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:3016
DL_GroupParameters_IntegerBased::ValidateGroup
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Check the group for errors.
Definition: gfpcrypt.cpp:129
HashTransformation
Interface for hash functions and data processing part of MACs.
Definition: cryptlib.h:922
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1352
DL_GroupParameters_DSA::ValidateGroup
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Definition: gfpcrypt.cpp:70
DL_FixedBasePrecomputation< Integer >
ModularArithmetic
Ring of congruence classes modulo n.
Definition: modarith.h:34
DL_GroupParameters_IntegerBased::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode this object into a BufferedTransformation.
Definition: gfpcrypt.cpp:249
gfpcrypt.h
modarith.h
Class file for performing modular arithmetic.
Integer::Power2
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Definition: integer.cpp:2995
OID
Object Identifier.
Definition: asn.h:159
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1186
Integer::ByteCount
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Definition: integer.cpp:3280
BitsToBytes
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:740
DL_GroupParameters_IntegerBased::EncodeElement
void EncodeElement(bool reversible, const Element &element, byte *encoded) const
Encodes the element.
Definition: gfpcrypt.h:67
misc.h
Utility functions for the Crypto++ library.
DL_GroupParameters_DSA::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: gfpcrypt.cpp:37
DL_GroupParameters_IntegerBased::DecodeElement
Integer DecodeElement(const byte *encoded, bool checkForGroupMembership) const
Decodes the element.
Definition: gfpcrypt.cpp:221
NullRNG
RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
Definition: cryptlib.cpp:406
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:467
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:351
DL_GroupParameters_IntegerBased::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: gfpcrypt.cpp:258
DL_GroupParameters_IntegerBased::BERDecode
void BERDecode(BufferedTransformation &bt)
Decode this object from a BufferedTransformation.
Definition: gfpcrypt.cpp:230
DL_GroupParameters< Integer >::GetGroupPrecomputation
virtual const DL_GroupPrecomputation< Element > & GetGroupPrecomputation() const=0
Retrieves the group precomputation.
VerifyPrime
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
Definition: nbtheory.cpp:249
asn.h
Classes and functions for working with ANS.1 objects.
oids.h
ASN.1 object identifiers for algorthms and schemes.
PrimeAndGenerator
generator of prime numbers of special forms
Definition: nbtheory.h:147
DL_GroupParameters< Integer >::GetSubgroupGenerator
virtual const Element & GetSubgroupGenerator() const
Retrieves the subgroup generator.
Definition: pubkey.h:811
DL_GroupParameters_IntegerBased::GetEncodedElementSize
unsigned int GetEncodedElementSize(bool reversible) const
Retrieves the encoded element's size.
Definition: gfpcrypt.h:69
Integer::BitCount
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition: integer.cpp:3289
HashTransformation::DigestSize
virtual unsigned int DigestSize() const =0
Provides the digest size of the hash.
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:182
DL_GroupParameters< Integer >::ExponentiateElement
virtual Element ExponentiateElement(const Element &base, const Integer &exponent) const
Exponentiates an element.
Definition: pubkey.h:831
Integer::Zero
static const Integer & Zero()
Integer representing 0.
Definition: integer.cpp:3011
CryptoPP
Crypto++ library namespace.
NameValuePairs::GetValue
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:335
DL_GroupParameters< Integer >::IsIdentity
virtual bool IsIdentity(const Element &element) const=0
Determines if an element is an identity.
config.h
Library configuration file.
CombinedNameValuePairs
Combines two sets of NameValuePairs.
Definition: algparam.h:135
DL_GroupParameters_IntegerBased::ValidateElement
bool ValidateElement(unsigned int level, const Integer &element, const DL_FixedBasePrecomputation< Integer > *precomp) const
Check the element for errors.
Definition: gfpcrypt.cpp:145
SaturatingSubtract
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition: misc.h:961
NameValuePairs::GetIntValue
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:371
DL_BadElement
Exception thrown when an invalid group element is encountered.
Definition: pubkey.h:742
PK_FinalTemplate
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2040
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:277
integer.h
Multiple precision integer with arithmetic operations.
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:45
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:295