gfpcrypt.cpp
// dsa.cpp - originally 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(CRYPTOPP_DEBUG) && !defined(CRYPTOPP_DOXYGEN_PROCESSING)
void TestInstantiations_gfpcrypt()
{
GDSA<SHA1>::Signer test;
GDSA<SHA1>::Verifier test1;
DSA::Signer test5(NullRNG(), 100);
DSA::Signer test2(test5);
NR<SHA1>::Signer test3;
NR<SHA1>::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 = 2048, 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);
CRYPTOPP_ASSERT(pass);
const 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));
CRYPTOPP_ASSERT(pass);
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);
CRYPTOPP_ASSERT(recoverableMessageLength == 0);
CRYPTOPP_ASSERT(hashIdentifier.second == 0);
const size_t representativeByteLength = BitsToBytes(representativeBitLength);
const size_t digestSize = hash.DigestSize();
const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
std::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);
CRYPTOPP_ASSERT(recoverableMessageLength == 0);
CRYPTOPP_ASSERT(hashIdentifier.second == 0);
const size_t representativeByteLength = BitsToBytes(representativeBitLength);
const size_t digestSize = hash.DigestSize();
const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
std::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;
CRYPTOPP_ASSERT(p > Integer::One() && p.IsOdd());
pass = pass && p > Integer::One() && p.IsOdd();
CRYPTOPP_ASSERT(q > Integer::One() && q.IsOdd());
pass = pass && q > Integer::One() && q.IsOdd();
if (level >= 1)
{
CRYPTOPP_ASSERT(GetCofactor() > Integer::One());
CRYPTOPP_ASSERT(GetGroupOrder() % q == Integer::Zero());
pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero();
}
if (level >= 2)
{
CRYPTOPP_ASSERT(VerifyPrime(rng, q, level-2));
CRYPTOPP_ASSERT(VerifyPrime(rng, p, 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;
CRYPTOPP_ASSERT(GetFieldType() == 1 ? g.IsPositive() : g.NotNegative());
pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative();
CRYPTOPP_ASSERT(g < p && !IsIdentity(g));
pass = pass && g < p && !IsIdentity(g);
if (level >= 1)
{
if (gpc)
{
CRYPTOPP_ASSERT(gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g);
pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g;
}
}
if (level >= 2)
{
if (GetFieldType() == 2)
{
CRYPTOPP_ASSERT(Jacobi(g*g-4, p)==-1);
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);
CRYPTOPP_ASSERT(IsIdentity(gp));
pass = pass && IsIdentity(gp);
}
else if (GetFieldType() == 1)
{
CRYPTOPP_ASSERT(Jacobi(g, p) == 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);
}
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();
}
Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const
{
CRYPTOPP_UNUSED(checkForGroupMembership);
Integer g(encoded, GetModulus().ByteCount());
if (!ValidateElement(1, g, NULLPTR))
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
MakeParameters
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition algparam.h:508
asn.h
Classes and functions for working with ANS.1 objects.
BERSequenceDecoder
BER Sequence Decoder.
Definition asn.h:525
BufferedTransformation
Interface for buffered transformations.
Definition cryptlib.h:1657
CombinedNameValuePairs
Combines two sets of NameValuePairs.
Definition algparam.h:129
DERSequenceEncoder
DER Sequence Encoder.
Definition asn.h:557
DL_BadElement
Exception thrown when an invalid group element is encountered.
Definition pubkey.h:772
DL_FixedBasePrecomputation
DL_FixedBasePrecomputation interface.
Definition eprecomp.h:61
DL_FixedBasePrecomputation::Exponentiate
virtual Element Exponentiate(const DL_GroupPrecomputation< Element > &group, const Integer &exponent) const =0
Exponentiates an element.
DL_GroupParameters_DSA::ValidateGroup
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Check the group for errors.
DL_GroupParameters_DSA::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key or crypto parameters.
DL_GroupParameters_GFP::SimultaneousExponentiate
void SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Exponentiates a base to multiple exponents.
DL_GroupParameters_IntegerBased::AssignFrom
void AssignFrom(const NameValuePairs &source)
Initialize or reinitialize this key.
DL_GroupParameters_IntegerBased::GetGroupOrder
Integer GetGroupOrder() const
Retrieves the order of the group.
Definition gfpcrypt.h:99
DL_GroupParameters_IntegerBased::SetModulusAndSubgroupGenerator
virtual void SetModulusAndSubgroupGenerator(const Integer &p, const Integer &g)=0
Set group parameters.
DL_GroupParameters_IntegerBased::GetAlgorithmID
OID GetAlgorithmID() const
Retrieve the OID of the algorithm.
DL_GroupParameters_IntegerBased::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode this object into a BufferedTransformation.
DL_GroupParameters_IntegerBased::GetMaxExponent
Integer GetMaxExponent() const
Retrieve the maximum exponent for the group.
DL_GroupParameters_IntegerBased::SetSubgroupOrder
void SetSubgroupOrder(const Integer &q)
Set subgroup order.
Definition gfpcrypt.h:161
DL_GroupParameters_IntegerBased::DecodeElement
Integer DecodeElement(const byte *encoded, bool checkForGroupMembership) const
Decodes the element.
DL_GroupParameters_IntegerBased::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key.
DL_GroupParameters_IntegerBased::BERDecode
void BERDecode(BufferedTransformation &bt)
Decode this object from a BufferedTransformation.
DL_GroupParameters_IntegerBased::GetModulus
virtual const Integer & GetModulus() const =0
Retrieve the modulus for the group.
DL_GroupParameters_IntegerBased::ValidateGroup
bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
Check the group for errors.
DL_GroupParameters_IntegerBased::Initialize
void Initialize(const DL_GroupParameters_IntegerBased &params)
Initialize a group parameters over integers.
Definition gfpcrypt.h:43
DL_GroupParameters_IntegerBased::FastSubgroupCheckAvailable
bool FastSubgroupCheckAvailable() const
Determine if subgroup membership check is fast.
Definition gfpcrypt.h:105
DL_GroupParameters_IntegerBased::GetEncodedElementSize
unsigned int GetEncodedElementSize(bool reversible) const
Retrieve the encoded element's size.
DL_GroupParameters_IntegerBased::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
DL_GroupParameters_IntegerBased::ValidateElement
bool ValidateElement(unsigned int level, const Integer &element, const DL_FixedBasePrecomputation< Integer > *precomp) const
Check the element for errors.
DL_GroupParameters_IntegerBased::GetSubgroupOrder
const Integer & GetSubgroupOrder() const
Retrieves the subgroup order.
Definition gfpcrypt.h:98
DL_GroupParameters_IntegerBased::EncodeElement
void EncodeElement(bool reversible, const Element &element, byte *encoded) const
Encodes the element.
DL_GroupParameters_IntegerBasedImpl< ModExpPrecomputation >::GetModulus
const Integer & GetModulus() const
Retrieve the modulus for the group.
Definition gfpcrypt.h:205
DL_GroupParameters< Integer >::ExponentiateElement
virtual Element ExponentiateElement(const Element &base, const Integer &exponent) const
Exponentiates an element.
Definition pubkey.h:879
DL_GroupParameters< Integer >::GetCofactor
virtual Integer GetCofactor() const
Retrieves the cofactor.
Definition pubkey.h:914
DL_GroupParameters::ValidateGroup
virtual bool ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const =0
Check the group for errors.
DL_GroupParameters< Integer >::GetSubgroupGenerator
virtual const Element & GetSubgroupGenerator() const
Retrieves the subgroup generator.
Definition pubkey.h:859
DL_GroupParameters< Integer >::GetGroupPrecomputation
virtual const DL_GroupPrecomputation< Element > & GetGroupPrecomputation() const=0
Retrieves the group precomputation.
DL_GroupParameters::GetSubgroupOrder
virtual const Integer & GetSubgroupOrder() const =0
Retrieves the subgroup order.
DL_GroupParameters< Integer >::IsIdentity
virtual bool IsIdentity(const Element &element) const=0
Determines if an element is an identity.
GeneratableCryptoMaterial::GenerateRandom
virtual void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random key or crypto parameters.
Definition cryptlib.h:2525
HashTransformation
Interface for hash functions and data processing part of MACs.
Definition cryptlib.h:1118
HashTransformation::TruncatedFinal
virtual void TruncatedFinal(byte *digest, size_t digestSize)=0
Computes the hash of the current message.
HashTransformation::DigestSize
virtual unsigned int DigestSize() const =0
Provides the digest size of the hash.
Integer
Multiple precision integer with arithmetic operations.
Definition integer.h:50
Integer::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Integer::IsPositive
bool IsPositive() const
Determines if the Integer is positive.
Definition integer.h:347
Integer::Zero
static const Integer & Zero()
Integer representing 0.
Integer::Power2
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Integer::BERDecode
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Integer::BitCount
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Integer::NotNegative
bool NotNegative() const
Determines if the Integer is non-negative.
Definition integer.h:344
Integer::ByteCount
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition integer.h:356
Integer::One
static const Integer & One()
Integer representing 1.
InvalidArgument
An invalid argument was detected.
Definition cryptlib.h:208
ModularArithmetic
Ring of congruence classes modulo n.
Definition modarith.h:44
NameValuePairs
Interface for retrieving values given their names.
Definition cryptlib.h:327
NameValuePairs::GetValueWithDefault
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition cryptlib.h:397
NameValuePairs::GetValue
bool GetValue(const char *name, T &value) const
Get a named value.
Definition cryptlib.h:384
NameValuePairs::GetIntValueWithDefault
CRYPTOPP_DLL int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition cryptlib.h:429
NameValuePairs::GetIntValue
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition cryptlib.h:420
OID
Object Identifier.
Definition asn.h:265
PK_FinalTemplate
Template implementing constructors for public key algorithm classes.
Definition pubkey.h:2198
PrimeAndGenerator
Generator of prime numbers of special forms.
Definition nbtheory.h:267
PrimeAndGenerator::SubPrime
const Integer & SubPrime() const
Retrieve second prime.
Definition nbtheory.h:308
PrimeAndGenerator::Generator
const Integer & Generator() const
Retrieve the generator.
Definition nbtheory.h:312
PrimeAndGenerator::Generate
void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Generate a Prime and Generator.
PrimeAndGenerator::Prime
const Integer & Prime() const
Retrieve first prime.
Definition nbtheory.h:304
RandomNumberGenerator
Interface for random number generators.
Definition cryptlib.h:1440
config.h
Library configuration file.
NullRNG
CRYPTOPP_DLL RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
gfpcrypt.h
Classes and functions for schemes based on Discrete Logs (DL) over GF(p)
integer.h
Multiple precision integer with arithmetic operations.
misc.h
Utility functions for the Crypto++ library.
SaturatingSubtract
T1 SaturatingSubtract(const T1 &a, const T2 &b)
Performs a saturating subtract clamped at 0.
Definition misc.h:1302
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition misc.h:657
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:1143
modarith.h
Class file for performing modular arithmetic.
CryptoPP
Crypto++ library namespace.
Name::SubgroupOrderSize
const char * SubgroupOrderSize()
int, in bits
Definition argnames.h:31
nbtheory.h
Classes and functions for number theoretic operations.
Jacobi
CRYPTOPP_DLL int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
DiscreteLogWorkFactor
CRYPTOPP_DLL unsigned int DiscreteLogWorkFactor(unsigned int bitlength)
Estimate work factor.
VerifyPrime
CRYPTOPP_DLL bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
oids.h
ASN.1 object identifiers for algorithms and schemes.
pch.h
Precompiled header file.
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition trap.h:68