rsa.cpp
// rsa.cpp - originally written and placed in the public domain by Wei Dai
#include "pch.h"
#include "rsa.h"
#include "asn.h"
#include "sha.h"
#include "oids.h"
#include "modarith.h"
#include "nbtheory.h"
#include "algparam.h"
#include "fips140.h"
#include "pkcspad.h"
#if defined(CRYPTOPP_DEBUG) && !defined(CRYPTOPP_DOXYGEN_PROCESSING) && !defined(CRYPTOPP_IS_DLL)
#include "sha3.h"
#include "pssr.h"
NAMESPACE_BEGIN(CryptoPP)
void RSA_TestInstantiations()
{
RSASS<PKCS1v15, SHA1>::Verifier x1(1, 1);
RSASS<PKCS1v15, SHA1>::Signer x2(NullRNG(), 1);
RSASS<PKCS1v15, SHA1>::Verifier x3(x2);
RSASS<PKCS1v15, SHA1>::Verifier x4(x2.GetKey());
RSASS<PSS, SHA1>::Verifier x5(x3);
#ifndef __MWERKS__
RSASS<PSSR, SHA1>::Signer x6 = x2;
x3 = x2;
x6 = x2;
#endif
RSAES<PKCS1v15>::Encryptor x7(x2);
#ifndef __GNUC__
RSAES<PKCS1v15>::Encryptor x8(x3);
#endif
RSAES<OAEP<SHA1> >::Encryptor x9(x2);
x4 = x2.GetKey();
RSASS<PKCS1v15, SHA3_256>::Verifier x10(1, 1);
RSASS<PKCS1v15, SHA3_256>::Signer x11(NullRNG(), 1);
RSASS<PKCS1v15, SHA3_256>::Verifier x12(x11);
RSASS<PKCS1v15, SHA3_256>::Verifier x13(x11.GetKey());
}
NAMESPACE_END
#endif
#ifndef CRYPTOPP_IMPORTS
NAMESPACE_BEGIN(CryptoPP)
OID RSAFunction::GetAlgorithmID() const
{
return ASN1::rsaEncryption();
}
void RSAFunction::BERDecodePublicKey(BufferedTransformation &bt, bool, size_t)
{
BERSequenceDecoder seq(bt);
m_n.BERDecode(seq);
m_e.BERDecode(seq);
seq.MessageEnd();
}
void RSAFunction::DEREncodePublicKey(BufferedTransformation &bt) const
{
DERSequenceEncoder seq(bt);
m_n.DEREncode(seq);
m_e.DEREncode(seq);
seq.MessageEnd();
}
Integer RSAFunction::ApplyFunction(const Integer &x) const
{
DoQuickSanityCheck();
return a_exp_b_mod_c(x, m_e, m_n);
}
bool RSAFunction::Validate(RandomNumberGenerator& rng, unsigned int level) const
{
CRYPTOPP_UNUSED(rng), CRYPTOPP_UNUSED(level);
bool pass = true;
pass = pass && m_n > Integer::One() && m_n.IsOdd();
CRYPTOPP_ASSERT(pass);
pass = pass && m_e > Integer::One() && m_e.IsOdd() && m_e < m_n;
CRYPTOPP_ASSERT(pass);
return pass;
}
bool RSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
{
return GetValueHelper(this, name, valueType, pValue).Assignable()
CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent)
;
}
void RSAFunction::AssignFrom(const NameValuePairs &source)
{
AssignFromHelper(this, source)
CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
;
}
// *****************************************************************************
class RSAPrimeSelector : public PrimeSelector
{
public:
RSAPrimeSelector(const Integer &e) : m_e(e) {}
bool IsAcceptable(const Integer &candidate) const {return RelativelyPrime(m_e, candidate-Integer::One());}
Integer m_e;
};
void InvertibleRSAFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
{
int modulusSize = 2048;
alg.GetIntValue(Name::ModulusSize(), modulusSize) || alg.GetIntValue(Name::KeySize(), modulusSize);
CRYPTOPP_ASSERT(modulusSize >= 16);
if (modulusSize < 16)
throw InvalidArgument("InvertibleRSAFunction: specified modulus size is too small");
m_e = alg.GetValueWithDefault(Name::PublicExponent(), Integer(17));
CRYPTOPP_ASSERT(m_e >= 3); CRYPTOPP_ASSERT(!m_e.IsEven());
if (m_e < 3 || m_e.IsEven())
throw InvalidArgument("InvertibleRSAFunction: invalid public exponent");
RSAPrimeSelector selector(m_e);
AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
(Name::PointerToPrimeSelector(), selector.GetSelectorPointer());
m_p.GenerateRandom(rng, primeParam);
m_q.GenerateRandom(rng, primeParam);
m_d = m_e.InverseMod(LCM(m_p-1, m_q-1));
CRYPTOPP_ASSERT(m_d.IsPositive());
m_dp = m_d % (m_p-1);
m_dq = m_d % (m_q-1);
m_n = m_p * m_q;
m_u = m_q.InverseMod(m_p);
if (FIPS_140_2_ComplianceEnabled())
{
RSASS<PKCS1v15, SHA1>::Signer signer(*this);
RSASS<PKCS1v15, SHA1>::Verifier verifier(signer);
SignaturePairwiseConsistencyTest_FIPS_140_Only(signer, verifier);
RSAES<OAEP<SHA1> >::Decryptor decryptor(*this);
RSAES<OAEP<SHA1> >::Encryptor encryptor(decryptor);
EncryptionPairwiseConsistencyTest_FIPS_140_Only(encryptor, decryptor);
}
}
void InvertibleRSAFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
{
GenerateRandom(rng, MakeParameters(Name::ModulusSize(), (int)keybits)(Name::PublicExponent(), e+e.IsEven()));
}
void InvertibleRSAFunction::Initialize(const Integer &n, const Integer &e, const Integer &d)
{
if (n.IsEven() || e.IsEven() | d.IsEven())
throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
m_n = n;
m_e = e;
m_d = d;
Integer r = --(d*e);
unsigned int s = 0;
while (r.IsEven())
{
r >>= 1;
s++;
}
ModularArithmetic modn(n);
for (Integer i = 2; ; ++i)
{
Integer a = modn.Exponentiate(i, r);
if (a == 1)
continue;
Integer b;
unsigned int j = 0;
while (a != n-1)
{
b = modn.Square(a);
if (b == 1)
{
m_p = GCD(a-1, n);
m_q = n/m_p;
m_dp = m_d % (m_p-1);
m_dq = m_d % (m_q-1);
m_u = m_q.InverseMod(m_p);
return;
}
if (++j == s)
throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
a = b;
}
}
}
void InvertibleRSAFunction::BERDecodePrivateKey(BufferedTransformation &bt, bool, size_t)
{
BERSequenceDecoder privateKey(bt);
word32 version;
BERDecodeUnsigned<word32>(privateKey, version, INTEGER, 0, 0); // check version
m_n.BERDecode(privateKey);
m_e.BERDecode(privateKey);
m_d.BERDecode(privateKey);
m_p.BERDecode(privateKey);
m_q.BERDecode(privateKey);
m_dp.BERDecode(privateKey);
m_dq.BERDecode(privateKey);
m_u.BERDecode(privateKey);
privateKey.MessageEnd();
}
void InvertibleRSAFunction::DEREncodePrivateKey(BufferedTransformation &bt) const
{
DERSequenceEncoder privateKey(bt);
DEREncodeUnsigned<word32>(privateKey, 0); // version
m_n.DEREncode(privateKey);
m_e.DEREncode(privateKey);
m_d.DEREncode(privateKey);
m_p.DEREncode(privateKey);
m_q.DEREncode(privateKey);
m_dp.DEREncode(privateKey);
m_dq.DEREncode(privateKey);
m_u.DEREncode(privateKey);
privateKey.MessageEnd();
}
Integer InvertibleRSAFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
{
DoQuickSanityCheck();
ModularArithmetic modn(m_n);
Integer r, rInv;
do { // do this in a loop for people using small numbers for testing
r.Randomize(rng, Integer::One(), m_n - Integer::One());
rInv = modn.MultiplicativeInverse(r);
} while (rInv.IsZero());
Integer re = modn.Exponentiate(r, m_e);
re = modn.Multiply(re, x); // blind
// here we follow the notation of PKCS #1 and let u=q inverse mod p
// but in ModRoot, u=p inverse mod q, so we reverse the order of p and q
Integer y = ModularRoot(re, m_dq, m_dp, m_q, m_p, m_u);
y = modn.Multiply(y, rInv); // unblind
if (modn.Exponentiate(y, m_e) != x) // check
throw Exception(Exception::OTHER_ERROR, "InvertibleRSAFunction: computational error during private key operation");
return y;
}
bool InvertibleRSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
{
bool pass = RSAFunction::Validate(rng, level);
CRYPTOPP_ASSERT(pass);
pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
CRYPTOPP_ASSERT(pass);
pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
CRYPTOPP_ASSERT(pass);
pass = pass && m_d > Integer::One() && m_d.IsOdd() && m_d < m_n;
CRYPTOPP_ASSERT(pass);
pass = pass && m_dp > Integer::One() && m_dp.IsOdd() && m_dp < m_p;
CRYPTOPP_ASSERT(pass);
pass = pass && m_dq > Integer::One() && m_dq.IsOdd() && m_dq < m_q;
CRYPTOPP_ASSERT(pass);
pass = pass && m_u.IsPositive() && m_u < m_p;
CRYPTOPP_ASSERT(pass);
if (level >= 1)
{
pass = pass && m_p * m_q == m_n;
CRYPTOPP_ASSERT(pass);
pass = pass && m_e*m_d % LCM(m_p-1, m_q-1) == 1;
CRYPTOPP_ASSERT(pass);
pass = pass && m_dp == m_d%(m_p-1) && m_dq == m_d%(m_q-1);
CRYPTOPP_ASSERT(pass);
pass = pass && m_u * m_q % m_p == 1;
CRYPTOPP_ASSERT(pass);
}
if (level >= 2)
{
pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
CRYPTOPP_ASSERT(pass);
}
return pass;
}
bool InvertibleRSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
{
return GetValueHelper<RSAFunction>(this, name, valueType, pValue).Assignable()
CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
CRYPTOPP_GET_FUNCTION_ENTRY(PrivateExponent)
CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
;
}
void InvertibleRSAFunction::AssignFrom(const NameValuePairs &source)
{
AssignFromHelper<RSAFunction>(this, source)
CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
CRYPTOPP_SET_FUNCTION_ENTRY(PrivateExponent)
CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
;
}
// *****************************************************************************
Integer RSAFunction_ISO::ApplyFunction(const Integer &x) const
{
Integer t = RSAFunction::ApplyFunction(x);
return t % 16 == 12 ? t : m_n - t;
}
Integer InvertibleRSAFunction_ISO::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
{
Integer t = InvertibleRSAFunction::CalculateInverse(rng, x);
return STDMIN(t, m_n-t);
}
NAMESPACE_END
#endif
algparam.h
Classes for working with NameValuePairs.
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.
INTEGER
@ INTEGER
ASN.1 Integer.
Definition: asn.h:34
AlgorithmParameters
An object that implements NameValuePairs.
Definition: algparam.h:426
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:525
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1652
CryptoMaterial::DoQuickSanityCheck
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition: cryptlib.h:2493
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:557
Exception
Base class for all exceptions thrown by the library.
Definition: cryptlib.h:159
Exception::OTHER_ERROR
@ OTHER_ERROR
Some other error occurred not belonging to other categories.
Definition: cryptlib.h:177
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:50
Integer::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Integer::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random number.
Definition: integer.h:506
Integer::IsPositive
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:345
Integer::Randomize
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Integer::BERDecode
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Integer::One
static const Integer & One()
Integer representing 1.
Integer::IsZero
bool IsZero() const
Determines if the Integer is 0.
Definition: integer.h:333
Integer::MultiplicativeInverse
Integer MultiplicativeInverse() const
Calculate multiplicative inverse.
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:354
Integer::InverseMod
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
Integer::IsEven
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:351
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:203
InvertibleRSAFunction_ISO::CalculateInverse
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
InvertibleRSAFunction::Validate
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
InvertibleRSAFunction::Initialize
void Initialize(RandomNumberGenerator &rng, unsigned int modulusBits, const Integer &e=17)
Create a RSA private key.
InvertibleRSAFunction::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key or crypto parameters.
InvertibleRSAFunction::AssignFrom
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
InvertibleRSAFunction::DEREncodePrivateKey
void DEREncodePrivateKey(BufferedTransformation &bt) const
Encode privateKey part of privateKeyInfo.
InvertibleRSAFunction::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
InvertibleRSAFunction::CalculateInverse
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
InvertibleRSAFunction::BERDecodePrivateKey
void BERDecodePrivateKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
Decode privateKey part of privateKeyInfo.
ModularArithmetic
Ring of congruence classes modulo n.
Definition: modarith.h:44
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:322
NameValuePairs::GetValueWithDefault
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:392
NameValuePairs::GetIntValue
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:415
OID
Object Identifier.
Definition: asn.h:265
PK_FinalTemplate
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2198
PrimeSelector
Application callback to signal suitability of a cabdidate prime.
Definition: nbtheory.h:114
RSAFunction_ISO::ApplyFunction
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
RSAFunction::Validate
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
RSAFunction::GetAlgorithmID
OID GetAlgorithmID() const
Retrieves the OID of the algorithm.
RSAFunction::ApplyFunction
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
RSAFunction::BERDecodePublicKey
void BERDecodePublicKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
Decode subjectPublicKey part of subjectPublicKeyInfo.
RSAFunction::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
RSAFunction::DEREncodePublicKey
void DEREncodePublicKey(BufferedTransformation &bt) const
Encode subjectPublicKey part of subjectPublicKeyInfo.
RSAFunction::AssignFrom
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1435
word32
unsigned int word32
32-bit unsigned datatype
Definition: config_int.h:62
NullRNG
CRYPTOPP_DLL RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
fips140.h
Classes and functions for the FIPS 140-2 validated library.
FIPS_140_2_ComplianceEnabled
CRYPTOPP_DLL bool FIPS_140_2_ComplianceEnabled()
Determines whether the library provides FIPS validated cryptography.
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:655
modarith.h
Class file for performing modular arithmetic.
CryptoPP
Crypto++ library namespace.
Name::PrivateExponent
const char * PrivateExponent()
Integer.
Definition: argnames.h:35
Name::PointerToPrimeSelector
const char * PointerToPrimeSelector()
const PrimeSelector *
Definition: argnames.h:42
Name::ModPrime1PrivateExponent
const char * ModPrime1PrivateExponent()
Integer.
Definition: argnames.h:45
Name::Prime1
const char * Prime1()
Integer.
Definition: argnames.h:43
Name::KeySize
const char * KeySize()
int, in bits
Definition: argnames.h:29
Name::Modulus
const char * Modulus()
Integer.
Definition: argnames.h:33
Name::MultiplicativeInverseOfPrime2ModPrime1
const char * MultiplicativeInverseOfPrime2ModPrime1()
Integer.
Definition: argnames.h:47
Name::PublicExponent
const char * PublicExponent()
Integer.
Definition: argnames.h:34
Name::ModulusSize
const char * ModulusSize()
int, in bits
Definition: argnames.h:30
Name::ModPrime2PrivateExponent
const char * ModPrime2PrivateExponent()
Integer.
Definition: argnames.h:46
Name::Prime2
const char * Prime2()
Integer.
Definition: argnames.h:44
nbtheory.h
Classes and functions for number theoretic operations.
RelativelyPrime
bool RelativelyPrime(const Integer &a, const Integer &b)
Determine relative primality.
Definition: nbtheory.h:150
VerifyPrime
CRYPTOPP_DLL bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
ModularRoot
CRYPTOPP_DLL Integer ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Extract a modular root.
GCD
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
Definition: nbtheory.h:143
LCM
Integer LCM(const Integer &a, const Integer &b)
Calculate the least common multiple.
Definition: nbtheory.h:157
oids.h
ASN.1 object identifiers for algorthms and schemes.
pch.h
Precompiled header file.
pkcspad.h
Classes for PKCS padding schemes.
pssr.h
Classes for probabilistic signature schemes.
rsa.h
Classes for the RSA cryptosystem.
sha3.h
Classes for SHA3 message digests.
sha.h
Classes for SHA-1 and SHA-2 family of message digests.
RSAES
RSA encryption algorithm.
Definition: rsa.h:173
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68