RSA Cryptography
From Crypto++ Wiki
RSA is the work of Ron Rivest, Adi Shamir, and Leonard Adleman. It is based on the Integer Factorization Problem. The system was developed in 1977 and patented by the Massachusetts Institute of Technology. Though Rivest, Shamir, and Adleman are generally credited with the discovery, Clifford Cocks (Chief Mathematician at GCHQ - the British equivalent of the NSA) described the system in 1973. However, Cocks did not publish since the work was considered classified, so the credit lay with Rivest, Shamir, and Adleman.
Contents |
Background
Crypto++ exposes most RSA encrpytion and signatures operations through rsa.h and pssr.h. The following will discuss some of the finer details of Crypto++, RSA keys, RSA encryption schemes, and RSA signature schemes.
Keys
Various Crypto++ supported key formats, importing exporting, loading, and saving are discussed in detail at Key Formats. This discussion is limited to using an RSA key. Crypto++ RSA keys are typedef'd in rsa.h as follows.
struct RSA
{
typedef RSAFunction PublicKey;
typedef InvertibleRSAFunction PrivateKey;
};
To generate a key pair, InvertibleRSAFunction offers GenerateRandomWithKeySize:
GenerateRandomWithKeySize (RandomNumberGenerator &rng, unsigned int keySize)
The parameters to the function are a RandomNumberGenerator and the modulus size specified in bits. GenerateRandomWithKeySize calls GenerateRandom with the modulus size encoded as a NameValuePairs.
In much of the sample code, InvertibleRSAFunction is used as follows to create a logical separation for demonstration purposes. In practice, this could be performed through a single variable (privateKey). Once the keys are created, they can be passed to Encryptors, Decryptors, Signers, and Verifiers.
/////////////////////////////////////// // Generate Parameters InvertibleRSAFunction params; params.GenerateRandomWithKeySize( rng, 1536 ); /////////////////////////////////////// // Create Keys RSA::PrivateKey privateKey( params ); RSA::PublicKey publicKey( params );
To persist the keys to disk in the most interoperable manner, use the Save function. If loading from disk, use the Load function. The format used by Save and Load is either PKCS #8 or X.509 (structure subjectPublicKeyInfo), depending on whether the key is public or private. Details of the other methods (BER Encoding, BER Decoding, DER Encoding, DER Decoding) are covered in key formats.
At times, Crypto++ might have to accept keys which are not encoded. For example, the application might have Integers e and n but needs to convert the integers to a RSA::PublicKey. In this case, use Initialize. For a RSA::PrivateKey, n, e, and d are needed.
Encryption Scheme
The high level RSA encryption schemes are exposed through RSAES, which is defined as follows. The template parameter, STANDARD, simply specifies additional algorithms. For example, when PKCS processing is required, PKCS1v15 is specified as the parameter.
template <class STANDARD>
struct RSAES : public TF_ES<STANDARD, RSA>
{ };
The TF_ES class exposes the functionality that is often used when working with RSA. For example, Encrpyt and Decrypt. There is some hand waiving here - at least two layers of templates exist before encountering TF_EncryptorBase and TF_DecryptorBase in cryptlib.h. To ease use of the library, two typedefs are offered. The first is based on PKCS #1 v 1.5, and the second is OAEP and SHA.
typedef RSAES<PKCS1v15>::Decryptor RSAES_PKCS1v15_Decryptor; typedef RSAES<PKCS1v15>::Encryptor RSAES_PKCS1v15_Encryptor; typedef RSAES<OAEP<SHA> >::Decryptor RSAES_OAEP_SHA_Decryptor; typedef RSAES<OAEP<SHA> >::Encryptor RSAES_OAEP_SHA_Encryptor;
Signature Scheme
The high level RSA signature schemes are exposed through RSASS, which is defined as follows.
template <class STANDARD, class H>
struct RSASS : public TF_SS<STANDARD, H, RSA>
{ };
As with RSAES, RSASS needs a STANDARD. In addition to the standard parameter, a one way hash function must be specified through H. The classes of interest for signers and verifiers are PK_Signer and PK_Verifier from cryptlib.h. The later classes offer familiar functions such as MaxSignatureLength, SignMessage, and VerifyMessage.
The Crypto++ RSA implementation of a Signature Scheme with Appendix (SSA) is typedef'd as follows. Note that two additional hashes are specified in PKCS (MD2 and MD5), but should not be used.
typedef RSASS<PKCS1v15, SHA>::Signer RSASSA_PKCS1v15_SHA_Signer; typedef RSASS<PKCS1v15, SHA>::Verifier RSASSA_PKCS1v15_SHA_Verifier;
The Crypto++ RSA implementation of a Signature Scheme with Recovery (PSSR) is similar to SSA. However, there are no typedef's so the objects are declared using template syntax. Below, PSSR (from pssr.h) is specified (the recovery mechanism), and a hash is specified.
RSASS<PSSR, SHA1>::Signer signer; RSASS<PSSR, SHA1>::Verifier verifier;
If Whirlpool were desired, the following would be performed.
RSASS<PSSR, Whirlpool>::Signer signer; RSASS<PSSR, Whirlpool>::Verifier verifier;
Regardless of the type of signature (PSSR vs SSA), the signers and verifiers are most easily constructed using the private key or the public key.
// Generate or Load keys RSA::PrivateKey privateKey; RSA::PublicKey publicKey; ... RSASS<PSSR, SHA1>::Signer signer( privateKey ); // Create signature ... RSASS<PSSR, SHA1>::Verifier verifier( publicKey ); // Verify signature on message ...
Sample Programs
Due to the number and size of RSA sample programs, two additional pages have been created for RSA Encryption Schemes and RSA Signature Schemes. Below, four samples are presented. Additional samples can be found at RSA Encryption Schemes and RSA Signature Schemes.
Key Generation
/////////////////////////////////////// // Pseudo Random Number Generator AutoSeededRandomPool rng; /////////////////////////////////////// // Generate Parameters InvertibleRSAFunction params; params.GenerateRandomWithKeySize( rng, 1536 ); /////////////////////////////////////// // Generated Parameters Integer n = params.GetModulus(); Integer p = params.GetPrime1(); Integer q = params.GetPrime2(); Integer d = params.GetPrivateExponent(); Integer e = params.GetPublicExponent(); /////////////////////////////////////// // Dump cout << "RSA Parameters:" << endl; cout << " n: " << n << endl; cout << " p: " << p << endl; cout << " q: " << q << endl; cout << " d: " << d << endl; cout << " e: " << e << endl; cout << endl; /////////////////////////////////////// // Create Keys RSA::PrivateKey privateKey( params ); RSA::PublicKey publicKey( params );
Profiling Key Generation
try
{
AutoSeededRandomPool prng;
RSA::PrivateKey rsa;
ThreadUserTimer timer(TimerBase::MILLISECONDS);
timer.StartTimer();
const int bits = 2048;
rsa.GenerateRandomWithKeySize(prng, bits);
///////////////////////////////////////
unsigned long elapsed = timer.GetCurrentTimerValue();
unsigned long ticks = timer.TicksPerSecond();
unsigned long seconds = elapsed / ticks;
// days, hours, minutes, seconds, 100th seconds
unsigned int d=0, h=0, m=0, s=0, p=0;
p = ((elapsed * 100) / ticks) % 100;
s = seconds % 60;
m = (seconds / 60) % 60;
h = (seconds / 60 / 60) % 60;
d = (seconds / 60 / 60 / 24) % 24;
float fs = (seconds + ((float)p/100));
///////////////////////////////////////
stringstream ss;
if(d) {
ss << d << ((d == 1) ? " day, " : " days, ");
goto print_hours;
}
if(h) {
print_hours:
ss << h << ((h == 1) ? " hour, " : " hours, ");
goto print_minutes;
}
if(m) {
print_minutes:
ss << m << ((m == 1) ? " minute, " : " minutes, ");
}
ss << s << ((s == 1) ? " second" : " seconds");
cout << "Elapsed time for " << bits << " RSA key: ";
cout << fixed << setprecision(2) << fs << "s";
if(seconds)
cout << " (" << ss.str() << ")";
cout << endl;
}
catch(CryptoPP::Exception& e)
{
...
}
...
Typical runs will look similar to below.
cryptopp$ rsa_kgen.exe 61440 Elapsed time for 61140 RSA key: 25654.01s (7 hours, 7 minutes, 34 seconds) cryptopp$ rsa_kgen.exe 30720 Elapsed time for 30720 RSA key: 2255.30s (37 minutes, 35 seconds) cryptopp$ rsa_kgen.exe 15360 Elapsed time for 15360 RSA key: 285.05s (4 minutes, 45 seconds) cryptopp$ rsa_kgen.exe 11776 Elapsed time for 11776 RSA key: 142.52s (2 minutes, 22 seconds) cryptopp$ rsa_kgen.exe 8192 Elapsed time for 8192 RSA key: 43.08s (43 seconds) cryptopp$ rsa_kgen.exe 4096 Elapsed time for 4096 RSA key: 0.70s cryptopp$ rsa_kgen.exe 2048 Elapsed time for 2048 RSA key: 0.09s cryptopp$ rsa_kgen.exe 1024 Elapsed time for 1024 RSA key: 0.01s cryptopp$ rsa_kgen.exe 512 Elapsed time for 512 RSA key: 0.00s cryptopp$ rsa_kgen.exe 256 Elapsed time for 256 RSA key: 0.00s
RSA Encryption Scheme (OAEP using SHA)
The following code demonstrates RSA encryption using OAEP. The complete list of RSA encryption scheme samples can be found at RSA Encryption Schemes.
////////////////////////////////////////////////
// Generate keys
AutoSeededRandomPool rng;
InvertibleRSAFunction params;
params.GenerateRandomWithKeySize( rng, 3072 );
RSA::PrivateKey privateKey( params );
RSA::PublicKey publicKey( params );
string plain="RSA Encryption", cipher, recovered;
////////////////////////////////////////////////
// Encryption
RSAES_OAEP_SHA_Encryptor e( publicKey );
StringSource( plain, true,
new PK_EncryptorFilter( rng, e,
new StringSink( cipher )
) // PK_EncryptorFilter
); // StringSource
////////////////////////////////////////////////
// Decryption
RSAES_OAEP_SHA_Decryptor d( privateKey );
StringSource( cipher, true,
new PK_DecryptorFilter( rng, d,
new StringSink( recovered )
) // PK_DecryptorFilter
); // StringSource
cout << "Recovered plain text" << endl;
RSA Signature Scheme (PKCS v2.0)
Though similar to RSA-SSA, RSASSA_PKCS1v15_SHA_Signer and RSASSA_PKCS1v15_SHA_Verifier use PKCS v1.5 padding. The MD2 and MD5 variants of RSASSA_PKCS1v15_<Digest>_Signer and RSASSA_PKCS1v15_<Digest>_Verifier should not be used. The complete list of RSA signature scheme samples can be found at RSA Signature Schemes.
// Generate or Load keys
RSA::PrivateKey privateKey = ...;
RSA::PublicKey publicKey = ...;
// Message
string message = "RSA Signature", signature;
////////////////////////////////////////////////
// Sign and Encode
RSASSA_PKCS1v15_SHA_Signer signer( privateKey );
StringSource( message, true,
new SignerFilter( rng, signer,
new StringSink( signature )
) // SignerFilter
); // StringSource
////////////////////////////////////////////////
// Verify and Recover
RSASSA_PKCS1v15_SHA_Verifier verifier( publicKey );
StringSource( message+signature, true,
new SignatureVerificationFilter(
verifier, NULL,
SignatureVerificationFilter::THROW_EXCEPTION
) // SignatureVerificationFilter
); // StringSource
cout << "Verified signature on message" << endl;
Downloads
RSA-ES-OAEP-SHA-Filter-Test.zip - Demonstrates RSA-ES (OAEP/SHA) using Filters
RSA-SSA-Filter-Test.zip - Demonstrates RSA-SSA using Filters
rsa_kgen.zip - Generaters a RSA key pair with profiling
