Raw RSA

From Crypto++ Wiki
Jump to navigation Jump to 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 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.

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]\{n, e\}[/math] and the private key is [math]\{n, e, d\}[/math]. [math]e[/math] is the public exponent, and [math]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.

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

Encryption

Next, we want to encrypt the string "secret". In RSA, encryption is simply [math]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]m[/math] (the word secret) is encoded as an integer. We can use C++'s insertion operator to inspect [math]m[/math]:

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

m: 736563726574h

At this point, we have [math]n[/math], [math]e[/math], [math]d[/math] and [math]m[/math]. To encrypt [math]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]e ∙ d ≡ 1 mod Φ(n)[/math]. The relationship is also written as [math]e ≡ d^{-1} mod Φ(n)[/math]. [math]Φ(n)[/math] is Euler's Phi function, and [math]Φ(n)[/math] is equal to [math](p - 1)(q -1)[/math].

Decryption is performed by raising [math]c[/math] to the private exponent ([math]m = c^d[/math]). Since the private exponent [math]d[/math] is part of the private key, the private key must be used to undo the encryption operation. Below, we use [math]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.

$ ./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 [math]\{n,d\}[/math] pair.

Rabin Cryptosystem

Rabin is a cryptosystem similar to RSA, based on square roots modulo [math]p[/math] and [math]q[/math]. Under Rabin, the public key is [math]\{n\}[/math] and the private key consists of [math]\{p,q\}[/math]. 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[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

RSA Blind Signature

The Crypto++ library does not offer blind signature classes. As far as we know there is no standard covering the signature scheme. The lack of standardization will surely cause interop problems. For example, the code below uses SHA256 to hash the message to be signed, while RSA Blind Signature Scheme for golang uses full domain hashing. Also see Is there a standard padding/format for RSA Blind Signatures? on Crypto.SE.

Blind signature can achieved with the following code. Thanks to Cory Geesaman for raising the topic on the mailing list. Also see Is there a standard padding/format for RSA Blind Signatures?, Usability of padding scheme in blinded RSA signature? and RSA blind signatures in practice on the Crypto Stack Exchange.

We will probably add a blind signature class in the future. The tricky parts are (1) finding a standard or accepted practice; and (2) adding classes that fit in the existing framework.

#include "cryptlib.h"
#include "integer.h"
#include "nbtheory.h"
#include "osrng.h"
#include "rsa.h"
#include "sha.h"
using namespace CryptoPP;

#include <iostream>
#include <stdexcept>
using std::cout;
using std::endl;
using std::runtime_error;

int main(int argc, char* argv[])
{
    // Bob artificially small key pair
    AutoSeededRandomPool prng;
    RSA::PrivateKey privKey;

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

    // Convenience
    const Integer& n = pubKey.GetModulus();
    const Integer& e = pubKey.GetPublicExponent();
    const Integer& d = privKey.GetPrivateExponent();

    // Print params
    cout << "Pub mod: " << std::hex << pubKey.GetModulus() << endl;
    cout << "Pub exp: " << std::hex << e << endl;
    cout << "Priv mod: " << std::hex << privKey.GetModulus() << endl;
    cout << "Priv exp: " << std::hex << d << endl;

    // For sizing the hashed message buffer. This should be SHA256 size.
    const size_t SIG_SIZE = UnsignedMin(SHA256::BLOCKSIZE, n.ByteCount());

    // Scratch
    SecByteBlock buff1, buff2, buff3;

    // Alice original message to be signed by Bob
    SecByteBlock orig((const byte*)"secret", 6);
    Integer m(orig.data(), orig.size());
    cout << "Message: " << std::hex << m << endl;

    // Hash message per Rabin (1979)
    buff1.resize(SIG_SIZE);
    SHA256 hash1;
    hash1.CalculateTruncatedDigest(buff1, buff1.size(), orig, orig.size());

    // H(m) as Integer
    Integer hm(buff1.data(), buff1.size());
    cout << "H(m): " << std::hex << hm << endl;

    // Alice blinding
    Integer r;
    do {
        r.Randomize(prng, Integer::One(), n - Integer::One());
    } while (!RelativelyPrime(r, n));

    // Blinding factor
    Integer b = a_exp_b_mod_c(r, e, n);
    cout << "Random: " << std::hex << b << endl;

    // Alice blinded message
    Integer mm = a_times_b_mod_c(hm, b, n);
    cout << "Blind msg: " << std::hex << mm << endl;

    // Bob sign
    Integer ss = privKey.CalculateInverse(prng, mm);
    cout << "Blind sign: " << ss << endl;

    // Alice checks s(s'(x)) = x. This is from Chaum's paper
    Integer c = pubKey.ApplyFunction(ss);
    cout << "Check sign: " << c << endl;
    if (c != mm)
        throw runtime_error("Alice cross-check failed");

    // Alice remove blinding
    Integer s = a_times_b_mod_c(ss, r.InverseMod(n), n);
    cout << "Unblind sign: " << s << endl;

    // Eve verifies
    Integer v = pubKey.ApplyFunction(s);    
    cout << "Verify: " << std::hex << v << endl;

    // Convert to a string
    size_t req = v.MinEncodedSize();
    buff2.resize(req);
    v.Encode(&buff2[0], buff2.size());

    // Hash message per Rabin (1979)
    buff3.resize(SIG_SIZE);
    SHA256 hash2;
    hash2.CalculateTruncatedDigest(buff3, buff3.size(), orig, orig.size());

    // Constant time compare
    bool equal = buff2.size() == buff3.size() && VerifyBufsEqual(
        buff2.data(), buff3.data(), buff3.size());

    if (!equal)
        throw runtime_error("Eve verified failed");

    cout << "Verified signature" << endl;

    return 0;
}

Running the program results in:

$ g++ blind.cxx ./libcryptopp.a -o blind.exe
$ ./blind.exe
Pub mod: ef0a8e12b020cb43h
Pub exp: 11h
Priv mod: ef0a8e12b020cb43h
Priv exp: 626dc206e636cc49h
Message: 736563726574h
H(m): 2bb80d537b1da3e3h
Random: b5ebee0076e53fcbh
Blind msg: 6b327b608027df1fh
Blind sign: c2e92d5c262a524ch
Check sign: 6b327b608027df1fh
Unblind sign: 58c28011bd85b1f9h
Verify: 2bb80d537b1da3e3h
Verified signature

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.