Raw RSA
| Documentation |
#include <cryptopp/rsa.h>
|
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 low level operations using Crypto++'s RSA primitives can be useful at times, so this page will demonstrate performing RSA encryption, decryption and signing using the low level primitives.
A couple words of warning before proceeding. Encrypt with the private key is questionable since its usually not considered a valid cryptographic operation. Frequently a signature scheme with recovery (PSSR) is a more appropriate choice. Also see How do I encrypt a message using a private* key? in the Crypto++ FAQ.
The second warning is, encryption, decryption and signing using the low level primitives directly can be tricky and should be avoided. Instead of using low level primitives, you should use an Encryption Scheme or Signature Scheme to ensure you don't repeat past mistakes. Also see Signing a Hash, US-Cert Vulnerability Note VU845620, Generate digest and signature separately and RSA signatures without padding.
If the RSA 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.
Finally, you can find an example of RSA blind signatures using low level primitives at Blind Signature.
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 [math]\displaystyle{ \{n, e\} }[/math] and the private key is [math]\displaystyle{ \{n, e, d\} }[/math]. [math]\displaystyle{ e }[/math] is the public exponent, and [math]\displaystyle{ d }[/math] 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.
$ ./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 the class members used with the Chinese Remainder Theorem (CRT) 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 155.
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, and Rabin Williams (see Rabin Cryptosystem below).
Encryption
Next, we want to encrypt the string "secret". In RSA, encryption is simply [math]\displaystyle{ c = m^e }[/math]. So our task is to encode the string as an Integer in preparation for encryption. To accomplish the encoding, we perform the following. (See this example in one file)
string message = "secret"; Integer m((const byte *)message.data(), message.size());
After the above, [math]\displaystyle{ m }[/math] (the word secret) is encoded as an integer. We can use C++'s insertion operator to inspect [math]\displaystyle{ m }[/math]:
cout << "m: " << m << endl; m: 736563726574h
At this point, we have [math]\displaystyle{ n }[/math], [math]\displaystyle{ e }[/math], [math]\displaystyle{ d }[/math] and [math]\displaystyle{ m }[/math]. To encrypt [math]\displaystyle{ m }[/math], 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 is [math]\displaystyle{ e ∙ d ≡ 1 mod Φ(n) }[/math]. The relationship is also written as [math]\displaystyle{ e ≡ d^{-1} mod Φ(n) }[/math]. [math]\displaystyle{ Φ(n) }[/math] is Euler's Phi function, and [math]\displaystyle{ Φ(n) }[/math] is equal to [math]\displaystyle{ (p - 1)(q -1) }[/math].
Decryption is performed by raising [math]\displaystyle{ c }[/math] to the private exponent ([math]\displaystyle{ m = c^d }[/math]). Since the private exponent [math]\displaystyle{ d }[/math] is part of the private key, the private key must be used to undo the encryption operation. Below, we use [math]\displaystyle{ r }[/math] 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 operation using Chinese Remainder Theorem (CRT) parameters is about 8 times faster on common modulus sizes, such as 2048 and 3072. The CRT parameters were acquired by factoring during Initialize.
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[0], 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.
$ ./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 [math]\displaystyle{ \{n,d\} }[/math] pair.
Rabin Cryptosystem
Rabin is a cryptosystem similar to RSA, based on square roots modulo [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math]. Under Rabin, the public key is [math]\displaystyle{ \{n\} }[/math] and the private key consists of [math]\displaystyle{ \{p,q\} }[/math]. Since Rabin is a trapdoor system, a copy/paste of RSA → Rabin 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[0], recovered.size()); cout << "recovered: " << recovered << endl;
The program outputs the following.
$ ./raw-rabin.exe modulus: b2ee1ab79e47f999dd9ade0820701fb9h prime 1: dbac2dd38515f2dbh prime 2: d08518824c5cf9fbh message: secret m: 736563726574h c: 2d83b790594a74ba741424fe0h r: 736563726574h recovered: secret
Downloads
raw-rsa.zip - RSA encryption and decryption using Crypto++'s ApplyFunction and CalculateInverse.
raw-rabin.zip - Rabin encryption and decryption using Crypto++'s ApplyFunction and CalculateInverse.