# RSA Cryptography

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. If interested in directly performing exponentiation using RSA primitives, see Raw RSA.

### Keys

Operations on keys, such as generating, validating, loading, saving, importing, exporting, and formats are discussed in detail at Keys and Formats.

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.

/////////////////////////////////////// // Generate Parameters InvertibleRSAFunction params; params.GenerateRandomWithKeySize(rng, 3072); /////////////////////////////////////// // Create Keys RSA::PrivateKey privateKey(params); RSA::PublicKey publicKey(params);

In practice, `RSA::PrivateKey` could be used instead of `InvertibleRSAFunction` (to improve readability); and `RSAES_PKCS1v15_Encryptor`, `RSAES_OAEP_SHA_Encryptor`, and friends should be used. A more detailed treatment of keys, generation, loading, saving, and formats can be found at Keys and Formats.

/////////////////////////////////////// // Create Keys RSA::PrivateKey privateKey; privateKey.GenerateRandomWithKeySize(rng, 3072); RSA::PublicKey publicKey(privateKey);

Once the keys are created, they can be passed to Encryptors, Decryptors, Signers, and Verifiers.

To persist the keys to disk in the most inter-operable manner, use the `Save` function. If loading from disk, use the `Load` function. A more complete treatment of saving and loading keys is covered in Keys and Formats.

If you have a RSA private key composed of {n,e,d} and are interested in calculating all parameters specified in PKCS #1, see RSA CRT key? on sci.crypt. In addition, Mounir Idrassi offers an open source tool at Sourceforge: RSA Converter.

If you need to import the {n,e,d} private key or {n,e} public key into Crypto++, use `Initialize`. Both `RSA::PublicKey` and `RSA::PrivateKey` provide the function overloads.

### Encryption Schemes

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.

Note: RSA encryption with PKCS v1.5 padding should only be used with extreme caution due to padding oracle attacks. See A bad couple of years for the cryptographic token industry.

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. **TF** stands for trapdoor function, and **ES** stands for encryption scheme. 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 version 1.5, and the second is based on OAEP and SHA. Due to implementation problems with PKCS padding, you should favor OAEP padding.

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 Schemes

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`. **TF** stands for trapdoor function, and **SS** stands for signature scheme. 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;

For those interested in NIST compliance after 2010, code might need to be migrated to the SHA-2 family of hashes.

RSASS<PSSR, SHA256>::Signer signer; RSASS<PSSR, SHA256>::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, 3072); /////////////////////////////////////// // Generated Parameters const Integer& n = params.GetModulus(); const Integer& p = params.GetPrime1(); const Integer& q = params.GetPrime2(); const Integer& d = params.GetPrivateExponent(); const 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);

### 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.

Note: RSA encryption with PKCS v1.5 padding should only be used with extreme caution due to padding oracle attacks. See A bad couple of years for the cryptographic token industry.

//////////////////////////////////////////////// // 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 ss1(plain, true, new PK_EncryptorFilter(rng, e, new StringSink(cipher) ) // PK_EncryptorFilter ); // StringSource //////////////////////////////////////////////// // Decryption RSAES_OAEP_SHA_Decryptor d(privateKey); StringSource ss2(cipher, true, new PK_DecryptorFilter(rng, d, new StringSink(recovered) ) // PK_DecryptorFilter ); // StringSource cout << "Recovered plain text" << endl;

### RSA Signature Scheme (PKCS v1.5)

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 ss1(message, true, new SignerFilter(rng, signer, new StringSink(signature) ) // SignerFilter ); // StringSource //////////////////////////////////////////////// // Verify and Recover RSASSA_PKCS1v15_SHA_Verifier verifier(publicKey); StringSource ss2(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_prof.zip - Generates a RSA key pair with profiling