RSA Cryptography

From Crypto++ Wiki
(Redirected from RSA)
Jump to navigation Jump to search
RSA Cryptography
Documentation
#include <cryptopp/rsa.h>

RSA is a public key cryptosystem by Ron Rivest, Adi Shamir, and Leonard Adleman. This article is an introduction to using RSA in Crypto++. For more information on encryption schemes, visit RSA Encryption Schemes. For more information on signature schemes, visit RSA Signature Schemes. Raw RSA provides information about low level RSA operations. For a detailed treatment of key generation, loading, saving, validation, and formats, see Keys and Formats.

Generally speaking you should use OAEP padding and avoid PCKS v1.5 padding. Also see A bad couple of years for the cryptographic token industry.

History

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, the 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.

Crypto++ 1.0 was released in the early 1990s and it included the RSA algorithm. The Crypto++ 1.0 release was withdrawn due to RSA Data Security, Inc asserting a patent claim over the RSA algorithm. As such, the earliest version of Crypto++ available for download is Crypto++ 2.3.

Background

Crypto++ exposes most RSA encrpytion and signatures operations through rsa.h. There's a RSAES (encryption scheme) and RSASS (signature scheme). 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 is desired, then the following would be performed. 

RSASS<PSSR, Whirlpool>::Signer signer;
RSASS<PSSR, Whirlpool>::Verifier verifier;

For those interested in SHA-2 family of hashes, then SHA256 would be used. 

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);

Profiling Key Generation

The following demonstrates profiling key generation times using Crypto++'s ThreadUserTimer. 

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)
{
  ...
}
...

The program was executed on an Intel Core2 Duo machine from around 2010. 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

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 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;

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.

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

// 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

Retrieved from "https://www.cryptopp.com/w/index.php?title=RSA_Cryptography&oldid=29313"