rsa.cpp
// rsa.cpp - 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"
#if !defined(NDEBUG) && !defined(CRYPTOPP_DOXYGEN_PROCESSING) && !defined(CRYPTOPP_IS_DLL)
#include "pssr.h"
NAMESPACE_BEGIN(CryptoPP)
void RSA_TestInstantiations()
{
RSASS<PKCS1v15, SHA>::Verifier x1(1, 1);
RSASS<PKCS1v15, SHA>::Signer x2(NullRNG(), 1);
RSASS<PKCS1v15, SHA>::Verifier x3(x2);
RSASS<PKCS1v15, SHA>::Verifier x4(x2.GetKey());
RSASS<PSS, SHA>::Verifier x5(x3);
#ifndef __MWERKS__
RSASS<PSSR, SHA>::Signer x6 = x2;
x3 = x2;
x6 = x2;
#endif
RSAES<PKCS1v15>::Encryptor x7(x2);
#ifndef __GNUC__
RSAES<PKCS1v15>::Encryptor x8(x3);
#endif
RSAES<OAEP<SHA> >::Encryptor x9(x2);
x4 = x2.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();
pass = pass && m_e > Integer::One() && m_e.IsOdd() && m_e < m_n;
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);
assert(modulusSize >= 16);
if (modulusSize < 16)
throw InvalidArgument("InvertibleRSAFunction: specified modulus size is too small");
m_e = alg.GetValueWithDefault(Name::PublicExponent(), Integer(17));
assert(m_e >= 3); 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));
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, SHA>::Signer signer(*this);
RSASS<PKCS1v15, SHA>::Verifier verifier(signer);
SignaturePairwiseConsistencyTest_FIPS_140_Only(signer, verifier);
RSAES<OAEP<SHA> >::Decryptor decryptor(*this);
RSAES<OAEP<SHA> >::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);
pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
pass = pass && m_d > Integer::One() && m_d.IsOdd() && m_d < m_n;
pass = pass && m_dp > Integer::One() && m_dp.IsOdd() && m_dp < m_p;
pass = pass && m_dq > Integer::One() && m_dq.IsOdd() && m_dq < m_q;
pass = pass && m_u.IsPositive() && m_u < m_p;
if (level >= 1)
{
pass = pass && m_p * m_q == m_n;
pass = pass && m_e*m_d % LCM(m_p-1, m_q-1) == 1;
pass = pass && m_dp == m_d%(m_p-1) && m_dq == m_d%(m_q-1);
pass = pass && m_u * m_q % m_p == 1;
}
if (level >= 2)
pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
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
Exception
Base class for all exceptions thrown by the library.
Definition: cryptlib.h:139
Name::MultiplicativeInverseOfPrime2ModPrime1
const char * MultiplicativeInverseOfPrime2ModPrime1()
Integer.
Definition: argnames.h:46
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:182
algparam.h
Classes for working with NameValuePairs.
ModularArithmetic::Square
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition: modarith.h:179
Name::Prime2
const char * Prime2()
Integer.
Definition: argnames.h:43
NameValuePairs::GetValueWithDefault
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:348
Integer::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3372
InvertibleRSAFunction::BERDecodePrivateKey
void BERDecodePrivateKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
decode privateKey part of privateKeyInfo, without the OCTET STRING header
Definition: rsa.cpp:196
InvertibleRSAFunction::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: rsa.cpp:106
InvertibleRSAFunction::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: rsa.cpp:268
ModularArithmetic::MultiplicativeInverse
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
Definition: modarith.h:192
Exception::OTHER_ERROR
Some other error occurred not belonging to other categories.
Definition: cryptlib.h:158
oids.h
ASN.1 object identifiers for algorthms and schemes.
ModularArithmetic
Ring of congruence classes modulo n.
Definition: modarith.h:34
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1186
Integer::Randomize
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Definition: integer.cpp:3439
Integer::InverseMod
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:4207
InvertibleRSAFunction::Validate
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: rsa.cpp:247
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:295
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1352
Integer::One
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:3016
RSAFunction::BERDecodePublicKey
void BERDecodePublicKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
decode subjectPublicKey part of subjectPublicKeyInfo, without the BIT STRING header ...
Definition: rsa.cpp:48
Name::PrivateExponent
const char * PrivateExponent()
Integer.
Definition: argnames.h:34
RSAFunction::ApplyFunction
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
Definition: rsa.cpp:64
RSAFunction::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: rsa.cpp:80
Name::Prime1
const char * Prime1()
Integer.
Definition: argnames.h:42
CryptoMaterial::DoQuickSanityCheck
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition: cryptlib.h:2148
FIPS_140_2_ComplianceEnabled
bool FIPS_140_2_ComplianceEnabled()
Determines whether the library provides FIPS validated cryptography.
Definition: fips140.cpp:29
InvertibleRSAFunction::Initialize
void Initialize(RandomNumberGenerator &rng, unsigned int modulusBits, const Integer &e=17)
Create a RSA private key.
Definition: rsa.cpp:147
ModularArithmetic::Multiply
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition: modarith.h:172
MakeParameters
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:554
Name::PublicExponent
const char * PublicExponent()
Integer.
Definition: argnames.h:33
Integer::IsZero
bool IsZero() const
Determines if the Integer is 0.
Definition: integer.h:330
VerifyPrime
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
Definition: nbtheory.cpp:249
RSAFunction::AssignFrom
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: rsa.cpp:88
Name::ModPrime1PrivateExponent
const char * ModPrime1PrivateExponent()
Integer.
Definition: argnames.h:44
PrimeSelector
Application callback to signal suitability of a cabdidate prime.
Definition: nbtheory.h:80
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:45
AbstractRing::Exponentiate
virtual Element Exponentiate(const Element &a, const Integer &e) const
Raises a base to an exponent in the group.
Definition: algebra.cpp:316
Name::ModPrime2PrivateExponent
const char * ModPrime2PrivateExponent()
Integer.
Definition: argnames.h:45
InvertibleRSAFunction::AssignFrom
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: rsa.cpp:280
InvertibleRSAFunction::CalculateInverse
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
Definition: rsa.cpp:227
Integer::IsEven
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:348
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
asn.h
Classes and functions for working with ANS.1 objects.
sha.h
Classes for SHA-1 and SHA-2 family of message digests.
Name::PointerToPrimeSelector
const char * PointerToPrimeSelector()
const PrimeSelector *
Definition: argnames.h:41
nbtheory.h
Classes and functions for number theoretic operations.
Name::KeySize
const char * KeySize()
int, in bits
Definition: argnames.h:28
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:305
rsa.h
Classes for the RSA cryptosystem.
RSAFunction::Validate
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: rsa.cpp:70
fips140.h
Classes and functions for the FIPS 140-2 validated library.
InvertibleRSAFunction_ISO::CalculateInverse
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
Definition: rsa.cpp:300
AlgorithmParameters
An object that implements NameValuePairs.
Definition: algparam.h:489
Name::Modulus
const char * Modulus()
Integer.
Definition: argnames.h:32
RSAES
RSA encryption algorithm.
Definition: rsa.h:165
RSAFunction_ISO::ApplyFunction
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
Definition: rsa.cpp:294
Integer::BERDecode
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Definition: integer.cpp:3379
modarith.h
Class file for performing modular arithmetic.
CryptoPP
Crypto++ library namespace.
Name::ModulusSize
const char * ModulusSize()
int, in bits
Definition: argnames.h:29
NameValuePairs::GetIntValue
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:371
RSAFunction::DEREncodePublicKey
void DEREncodePublicKey(BufferedTransformation &bt) const
encode subjectPublicKey part of subjectPublicKeyInfo, without the BIT STRING header ...
Definition: rsa.cpp:56
OID
Object Identifier.
Definition: asn.h:159
pssr.h
Classes for probablistic signature schemes.
InvertibleRSAFunction::DEREncodePrivateKey
void DEREncodePrivateKey(BufferedTransformation &bt) const
encode privateKey part of privateKeyInfo, without the OCTET STRING header
Definition: rsa.cpp:212
RSAPrimeSelector
Definition: rsa.cpp:98
RSAFunction
RSA trapdoor function using the public key.
Definition: rsa.h:23
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:351
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:277
PK_FinalTemplate
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2030