Raw RSA

From Crypto++ Wiki
Jump to: navigation, search

The Crypto++ mailing list occasionally receives questions on how to preform Raw RSA encryption and decryption, or how to 'encrypt with the private key'. Performing encryption and decryption operations using Crypto++'s RSA primitives can be useful at times, so this page will demonstrate performing RSA encryption and decryption using Crypto++'s RSA primitives.

'Encrypt with the private key' is questionable since its usually not considered a valid cryptographic operation. Frequently a signature (or signature with recovery) is a more appropriate choice - see How do I encrypt a message using a *private* key?. In addition, signing a hash can be tricky - see Signing a Hash, US-Cert Vulnerability Note VU845620, and Generate digest and signature seperately.

If the primitives are not low-level enough, you can use Crypto++'s Integer class and modular exponentiation (a_exp_b_mod_c) in nbtheory.h. If the primitives are too low, try the higher level objects at RSA keys, RSA encryption schemes, and RSA signature schemes.

Trapdoor Functions

RSA uses a trapdoor function, meaning a result is easy to compute one way, but hard to compute the other way without special knowledge. For RSA, the public function (which is easy to compute) is exponentiation with the public exponent. The hard problem is undoing the exponentiation with the public exponent. Without knowledge of the factors of the modulus or the private exponent, its hard to undo the previous exponentiation and recover the message. Since the owner of the private key has the private exponent, the earlier exponentiation can be easily reversed (ergo, the trapdoor).

Keys, Exponents and Moduli

RSA uses two keys - a public key and a private key. Under RSA, the public key is {n, e} and the private key is {n, e, d}. e is the public exponent, and d is the private exponent. The public key is for mass consumption and is usually published or readily available. The private key should remain secret.

The public exponent is often 3, 17, or 65537 (3 can be a bad choice for signing keys when coupled with an implementation flaw - see US-Cert Vulnerability Note VU#845620). The public exponent values are selected because they have a low Hamming Weight. Any choice of e and d will do as long as the selections satisfy the congruence and co-primality requirements. In fact, Crypto++'s RSA has an overloaded version of Initialize which will generate a RSA object with an arbitrary public exponent (see rsa.cpp around line 145).

For demonstration purposes, the program below will use a 64 bit modulus. The modulus is artificially small, and the parameters were generated with the following program:

AutoSeededRandomPool prng;
RSA::PrivateKey privKey;

privKey.GenerateRandomWithKeySize(prng, 64);
RSA::PublicKey pubKey(privKey);

The program produced the following results, which will be used for the remainder of this discussion.

$ ./cryptopp-raw-rsa.exe 
modulus: beaadb3d839f3b5fh
private exp: 21a5ae37b9959db9h
public exp: 11h

To load the values into public and private RSA keys, we perform the following. In the case of the private key, Crypto++ will factor n and populate other class members such as m_p, m_q, m_dp, m_dq, and m_u. For those interested, the algorithm is located in rsa.cpp, near line 150.

Integer n("0xbeaadb3d839f3b5f"), e("0x11"), d("0x21a5ae37b9959db9");

RSA::PrivateKey privKey;
privKey.Initialize(n, e, d);

RSA::PublicKey pubKey;
pubKey.Initialize(n, e);

Its always a good idea to validate any loaded keys. The code below validates the private and public keys ate level 3, which is most thorough (for a full discussion, see Keys and Formats). The check on the public key is redundant since the private key is validated. It is shown for completeness.

if(!privKey.Validate(rnd, 3))
    throw runtime_error("Rsa private key validation failed");

if(!pubKey.Validate(rnd, 3))
    throw runtime_error("Rsa public key validation failed");

Encryption and Decryption

Crypto++ uses two functions for encryption and decryption. The encryption function is ApplyFunction and the decryption function is CalculateInverse.

Though the code below is written for RSA using a RSA::PrivateKey and RSA::PublicKey, Crypto++'s parameterized design allows us to use any class which derives from TrapdoorFunction. So the code below would apply equally well to ESIGN, LUC, Rabin, and Rabin Williams (see Rabin Cryptosystem below).

Encryption

Next, we want to encrypt the string "secret". In RSA, encryption is simply c = me. So our task is to encode the string as an Integer in preparation for encryption. To accomplish the encoding, we perform the following.

string message = "secret";
Integer m((const byte *)message.data(), message.size());

After the above, m (the word secret) is encoded as an integer. We can use C++'s insertion operator to inspect m:

cout << "m: " << m << endl;

m: 736563726574h

At this point, we have n, e, d and m. To encrypt m, we perform the following.

Integer c = pubKey.ApplyFunction(m);
cout << "c: " << hex << c << endl;

c: 3f47c32e8e17e291h

ApplyFunction is the 'easy to compute' transformation. If we look at rsa.cpp near line 65, we see the RSA class performs the expected exponentiation.

Integer RSAFunction::ApplyFunction(const Integer &x) const
{
	DoQuickSanityCheck();
	return a_exp_b_mod_c(x, m_e, m_n);
}

Decryption

In RSA, the relationship between encryption and decryption - or e and d is: e ∙ d ≡ 1 mod Φ(n) (the relation is also written as e ≡ d-1 mod Φ(n)). Decryption is performed by raising c to the private exponent (m = cd). Since the private exponent d is part of the private key, we must use the private key to undo the encryption operation. Below, we use r to denote "recovered" to ensure no cross pollination or slight-of-hands are occurring.

r = privKey.CalculateInverse(prng, c);
cout << "r: " << hex << r << endl;

r: 736563726574h

To no surprise, m is equal to r. If we examine rsa.cpp around line 225, we find the following. Notice that the private exponent, m_d, is not used in the computation below. The pre-computed members (gained by factoring during Initialize) offer efficient transformations on common modulus sizes (such as 2048 and 3072).

Integer InvertibleRSAFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const 
{
	DoQuickSanityCheck();
	ModularArithmetic modn(m_n);
	Integer r, rInv;
	do {	// do this in a loop for people using small numbers for testing
		r.Randomize(rng, Integer::One(), m_n - Integer::One());
		rInv = modn.MultiplicativeInverse(r);
	} while (rInv.IsZero());
	Integer re = modn.Exponentiate(r, m_e);
	re = modn.Multiply(re, x);			// blind
	// here we follow the notation of PKCS #1 and let u=q inverse mod p
	// but in ModRoot, u=p inverse mod q, so we reverse the order of p and q
	Integer y = ModularRoot(re, m_dq, m_dp, m_q, m_p, m_u);
	y = modn.Multiply(y, rInv);				// unblind
	if (modn.Exponentiate(y, m_e) != x)		// check
		throw Exception(Exception::OTHER_ERROR, "InvertibleRSAFunction: computational error during private key operation");
	return y;
}

Finally, we recover the original string.

size_t req = r.MinEncodedSize();
recovered.resize(req);

r.Encode((byte *)recovered.data(), recovered.size());
cout << "recovered: " << recovered << endl;

recovered: secret

Private Key Encryption

Now would be a good time to review How do I encrypt a message using a *private* key? from the original Crypto++ FAQ.

Previously, we encrypted with the public exponent of 17, and decrypted with the private exponent of 0x21a5ae37b9959db9. Below, we swap the roles of e and d so that we can encrypt with the private key (which is really only encrypting with the previously private exponent).

Integer n("0xbeaadb3d839f3b5f"), e("0x11"), d("0x21a5ae37b9959db9");

RSA::PrivateKey privKey;
privKey.Initialize(n, d, e);

RSA::PublicKey pubKey;
pubKey.Initialize(n, d);

We then follow the same steps of (1) encode the message, (2) call ApplyFunctions, and (3) call CalculateInverse. Following the steps results in the following. Note that the cipher text has changed from 0x3f47c32e8e17e291 to 0x2f13630ffa8bde2e.

$ ./cryptopp-priv-key-enc.exe
message: secret
m: 736563726574h
c: 2f13630ffa8bde2eh
r: 736563726574h
recovered: secret

If you wanted the world to have the previously private key, publish the {n,d} pair.

Rabin Cryptosystem

Rabin is a cryptosystem similar to RSA, based on square roots modulo p and q. Under Rabin, the public key is {n} and the private key consists of {p,q}. Since Rabin is a trapdoor system, a copy/paste of RSARabin will get us a working program.

AutoSeededRandomPool prng;

Rabin::PrivateKey privKey;
privKey.GenerateRandomWithKeySize(prng, 128);
Rabin::PublicKey pubKey(privKey);

string message, recovered;
Integer m, c, r;

message = "secret";
cout << "message: " << message << endl;

// Treat the message as a big endian array
m = Integer((const byte *)message.data(), message.size());
cout << "m: " << hex << m << endl;

// Encrypt
c = pubKey.ApplyFunction(m);
cout << "c: " << hex << c << endl;

// Decrypt
r = privKey.CalculateInverse(prng, c);
cout << "r: " << hex << r << endl;

// Round trip it
size_t req = r.MinEncodedSize();
recovered.resize(req);
r.Encode((byte *)recovered.data(), recovered.size());

cout << "recovered: " << recovered << endl;	

The program outputs the following.

$ ./cryptopp-raw-rabin.exe
modulus: b2ee1ab79e47f999dd9ade0820701fb9h
prime 1: dbac2dd38515f2dbh
prime 2: d08518824c5cf9fbh

message: secret
m: 736563726574h
c: 2d83b790594a74ba741424fe0h
r: 736563726574h
recovered: secret

Downloads

cryptopp-raw-rsa.zip - RSA encryption and decryption using Crypto++'s ApplyFunction and CalculateInverse.

cryptopp-raw-rabin.zip - Rabin encryption and decryption using Crypto++'s ApplyFunction and CalculateInverse.