RSA Cryptography

From Crypto++ Wiki
(Redirected from RSA)
Jump to: navigation, search

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.

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.

  • RSA Key Generation
  • RSA Encryption and Decryption
  • RSA Signature and Verification (PKCS v1.5)

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

Additional Downloads