# Raw rsa

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 scheme with recovery (PSSR) is a more appropriate choice; see

*How do I encrypt a message using a *private* key?*.

In addition, raw RSA or 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 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.

## Contents

## 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 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, Rabin, and Rabin Williams (see Rabin Cryptosystem below).

### Encryption

Next, we want to encrypt the `string` "secret". In RSA, encryption is simply `c = m ^{e}`. 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, `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 = c`). Since the private exponent

^{d}`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[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.

$ ./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 *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.

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