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 (the work was considered classified), so the credit lay with Rivest, Shamir, and Adleman.

Contents 1 Mathematical Problem 2 Remarks 3 Usage 3.1 Plain Text Length 3.2 Cipher Text Length 4 Examples 4.1 Generate Keys - 1 4.2 Generate Keys - 2 4.3 Dump Keys 4.4 RSA Signature 4.5 RSA Signature Verification 5 RSA Signature Verification Given e and n 6 RSA Probabilistic Signature Scheme with Recovery 7 Sample Programs 7.1 RSA Key Generation 7.2 RSA Key Dump 7.3 RSA Signature 7.4 RSA Signature Verification 7.5 RSA Probabilistic Signature Scheme with Recovery 8 Keywords

Mathematical Problem

The underlying mathematical problem of RSA is Integer Factorization [1].

Remarks

When encrypting and decrypting using Crypto++, the plaintext and ciphertext buffers can be the same. This effectively means you can do in-place encryption and decryption:

// Encrypt
publicKey.Encrypt(rnd, (byte*)plainText, sizeof(byte) * plainTextLen, (byte*)plainText);
int cipherTextSize = (int)publicKey.CiphertextLength(plainTextLen);

// Decrypt
DecodingResult result = privateKey.Decrypt(rnd, (byte*)plainText, cipherTextSize, (byte*)plainText);
int plainTextSize = (int)result.messageLength;

However, always make sure the buffer is big enough to hold the encrypted data (which will be larger than the plaintext).

Usage

Plain Text Length

The maximum length of a plaintext string that can be encrypted with RSA can be determined by FixedMaxPlaintextLength().

Cipher Text Length

The length of the resulting ciphertext can be determined by FixedCiphertextLength().

Examples

Please see also BEREncode and BERDecode

Generate Keys - 1

std::string PrivateKeyFile = "key.pv";
std::string PublicKeyFile  = "key.pb";

CryptoPP::AutoSeededRandomPool rng;

// Specify 512 bit modulus, accept e = 17
CryptoPP::RSAES_OAEP_SHA_Decryptor Decryptor( rng, 512 /*, e */ );
CryptoPP::HexEncoder privFile(new
   CryptoPP::FileSink( PrivateKeyFile.c_str() )
); // Hex Encoder

Decryptor.DEREncode(privFile);
privFile.MessageEnd();

CryptoPP:: RSAES_OAEP_SHA_Encryptor Encryptor(Decryptor);
CryptoPP::HexEncoder pubFile(new
   CryptoPP::FileSink( PublicKeyFile.c_str() )
); // Hex Encoder
        
Encryptor.DEREncode(pubFile);
pubFile.MessageEnd();

Generate Keys - 2

///////////////////////////////////////
// Pseudo Random Number Generator
CryptoPP::AutoSeededRandomPool rng;

///////////////////////////////////////
// Key Generation
CryptoPP::InvertibleRSAFunction keys;
keys.GenerateRandomWithKeySize( rng, 512 );

///////////////////////////////////////
// Generated Parameters
CryptoPP::Integer n = keys.GetModulus();
CryptoPP::Integer p = keys.GetPrime1();
CryptoPP::Integer q = keys.GetPrime2();
CryptoPP::Integer d = keys.GetPrivateExponent();
CryptoPP::Integer e = keys.GetPublicExponent();

///////////////////////////////////////
// Dump
std::cout << "RSA Parameters:" << std::endl;
std::cout << " n: " << n << std::endl;
std::cout << " p: " << p << std::endl;
std::cout << " q: " << q << std::endl;
std::cout << " d: " << d << std::endl;
std::cout << " e: " << e << std::endl;
std::cout << std::endl;

Dump Keys

std::string PrivateKeyFile = "key.pv";
std::string PublicKeyFile  = "key.pb";

CryptoPP::FileSource pubFile( PublicKeyFile.c_str(),
   true, new CryptoPP::HexDecoder );

CryptoPP::FileSource privFile( PrivateKeyFile.c_str(),
   true, new CryptoPP::HexDecoder);

CryptoPP::RSAES_OAEP_SHA_Decryptor Decryptor( privFile );
CryptoPP::RSAES_OAEP_SHA_Encryptor Encryptor ( pubFile );

std::cout << "n: " << Encryptor.GetTrapdoorFunction().GetModulus();
std::cout << std::endl;

std::cout << "d: " << Decryptor.GetTrapdoorFunction().GetPrivateExponent();
std::cout << std::endl;
std::cout << "e: " << Encryptor.GetTrapdoorFunction().GetPublicExponent();
std::cout << std::endl;

std::cout << "p: " << Decryptor.GetTrapdoorFunction().GetPrime1();
std::cout << std::endl;
std::cout << "q: " << Decryptor.GetTrapdoorFunction().GetPrime2();
std::cout << std::endl;

RSA Signature

CryptoPP::AutoSeededRandomPool rng;
std::string message = "Yoda said, Do or Do Not. There is not try.";

// Input: Private Key
std::string PrivateKeyFile = "key.pv";
      
// Output: Signed Message M
std::string SignedFile = "message.sig";

CryptoPP::FileSource privFile( PrivateKeyFile.c_str(), true,
   new CryptoPP::HexDecoder);
CryptoPP::RSASSA_PKCS1v15_SHA_Signer priv(privFile);
      
// Sign Away...
CryptoPP::StringSource( message, true,
   new CryptoPP::SignerFilter( rng, priv,
      new CryptoPP::HexEncoder(
         new CryptoPP::FileSink( SignedFile.c_str() )
      ) // HexEncoder
   ) // SignerFilter
); // StringSource

RSA Signature Verification

std::string PublicKeyFile = "key.pb";
std::string SignatureFile = "message.sig";
std::string message = "Yoda said, Do or Do Not. There is no try.";

// Inputs
CryptoPP::FileSource pubFile( PublicKeyFile.c_str(), true
   new CryptoPP::HexDecoder );
CryptoPP::FileSource SignatureFile( SignatureFile.c_str()
   true, new CryptoPP::HexDecoder);

// Verifier Object
CryptoPP::RSASSA_PKCS1v15_SHA_Verifier pub(pubFile);

// Sanity Check
if (SignatureFile.MaxRetrievable() != pub.SignatureLength() )
   { throw error; }

CryptoPP::SecByteBlock signature( pub.SignatureLength() )
SignatureFile.Get( signature, signature.size() );

// Setup
CryptoPP::VerifierFilter *verifierFilter =
   new CryptoPP::VerifierFilter(pub);
verifierFilter->Put(signature, pub.SignatureLength());

// Invoke Verifier
CryptoPP::StringSource tmpSS( message, true, verifierFilter );

// Paydirt
if( false == verifierFilter->GetLastResult() )
   { throw error; }

RSA Signature Verification Given e and n

CryptoPP::RSASS<CryptoPP::PSS, CryptoPP::SHA>::Verifier pub(n, e);

CryptoPP::RSASS<CryptoPP::PSS, CryptoPP::SHA>::Verifier pub;
pub.AccessKey().Initialize(n, e);

RSA Probabilistic Signature Scheme with Recovery

// Specify modulus, accept e = 17
CryptoPP::RSAES_OAEP_SHA_Decryptor Decryptor( rng, 384 /*, e */ );
CryptoPP::RSAES_OAEP_SHA_Encryptor Encryptor( Decryptor );

// BER Encoded Keys
std::string pubkey, prvkey;

{ // BER Encode Private Key
   Decryptor.AccessKey().Save(
      CryptoPP::HexEncoder(
         new CryptoPP::StringSink( prvkey )
      )
   );
} // BER Encode Private Key

{ // BER Encode Public Key
   Encryptor.AccessKey().Save(
      CryptoPP::HexEncoder(
         new CryptoPP::StringSink( pubkey )
      )
   );
} // BER Encode Public Key

// Signing      
CryptoPP::StringSource s( prvkey, true, new CryptoPP::HexDecoder);
CryptoPP::RSASS<CryptoPP::PSSR, CryptoPP::SHA>::Signer signer( s );
CryptoPP::RSASS<CryptoPP::PSSR, CryptoPP::SHA>::Verifier verifier( signer );

// Setup
byte message[] = "Test";
unsigned int messageLen = sizeof(message);      

// Sign
CryptoPP::SecByteBlock signature(signer.MaxSignatureLength(messageLen));

unsigned int signatureLen =
   signer.SignMessageWithRecovery(rng, message, messageLen, NULL, 0, signature);

//Recover
CryptoPP::SecByteBlock recovered(
   verifier.MaxRecoverableLengthFromSignatureLength(signatureLen)
);

// Verify
CryptoPP::DecodingResult result =
   verifier.RecoverMessage(recovered, NULL, 0, signature, signatureLen);

if (!result.isValidCoding) { throw "Invalid Signature"; }

unsigned int recoveredLen = result.messageLength;

Sample Programs

RSA Key Generation

RSAKeyGen.zip - Generates a Public and Private key pair, and then saves to separate files after DER and Hex Encoding. Based on Wei Dai's example.

RSA Key Dump

RSADumpKeys.zip - Loads the DER and Hex Encoded Keys from disk, and dumps the parameters p, q, e, d, and n.

RSA Signature

RSASign.zip - Loads a DER and Hex Encoded Private Key from disk, signs a std::string message, and then writes the signature to disk after Hex Encoding.

RSA Signature Verification

RSASignVer.zip - Loads a Hex encoded Signature from disk, loads a DER and Hex Encoded Public Key from disk, and then verifies the signature.

RSA Probabilistic Signature Scheme with Recovery

RSAPSSR.zip - Demonstrates PSSR using RSA with OAEP and BER Encoded Keys - 3.6Kb

Keywords

RSA Sample Samples Example Examples Source Code Project Workspace