RandomNumberGenerator requirement during RSA encryption and decryption?

Question

I'm trying to encrypt a message with a public key and decrypt the cipher with the private key using crypto++ like this in the shell:

openssl rsautl -encrypt -inkey id_rsa.pub.pem -pubin -in message -out message.enc

and

openssl rsautl -decrypt -inkey id_rsa.pem -in message.enc -out message.dec

Encryption/Decryption is done in separate applications. I started with the example from https://www.cryptopp.com/wiki/RSA_Cryptography. My code:

std::string publicEncrypt(std::string const& plain) {
    auto cipher = std::string{};
    CryptoPP::RSAES_OAEP_SHA_Encryptor e(getPublicKey());
    CryptoPP::StringSource(plain, true,
        new CryptoPP::PK_EncryptorFilter(CryptoPP::NullRNG(), e,
                new CryptoPP::StringSink(cipher)));
   return cipher;
}

std::string privateDecrypt(std::string const& cipher) {
    auto decrypted = std::string{};
    CryptoPP::RSAES_OAEP_SHA_Decryptor d(getPrivateKey());
    CryptoPP::StringSource(cipher, true,
        new CryptoPP::PK_DecryptorFilter(CryptoPP::NullRNG(), d,
                new CryptoPP::StringSink(decrypted)));
    return decrypted;
}

My questions:

1. Why is a random number generator (RNG) needed for EncryptorFilter/DecryptorFilter?
2. The RNG has to be the same for encryption/decription, right? So, how to share between processes?

Using the NullRNG() as recommended by https://stackoverflow.com/users/608639/jww in Unable to do RSA Encrption/Decryption using Crypto++ (isValidCoding is false) leads to

std::exception NullRNG: NullRNG should only be passed to functions that don't need to generate random bytes.

I guess I fundamentally miss something. Thanks for hints and advices.

If I use this code in a unit test with a global RNG, everything works fine.

Answer 1

Why is a random number generator (RNG) needed for EncryptorFilter/DecryptorFilter?

The signing and verification classes are abstract interfaces setup in cryptlib.h. Some cryptosystems use them, others do not. A class will specialize and can forgo using a generator. Sometimes a class does not need a generator for one of the operations. NullRNG can be used if not needed.

The reason RSA needs a RNG during public key operations is message padding. Padding is often part of the message formatting function. As @PuzzlePalace pointed out, OAEP padding is randomized and not deterministic.

The reason RSA needs a RNG during private key operations is blinding. For RSA and other RSA-like schemes (like Rabin-Williams), blinding is just a multiplication by a random value to mask the inversion by the priavte key to recover the original value. Later, after signing or decryption, the blinding value is removed and the result of the operation remains.

Related, a reason DSA or ECDSA would not need a RNG during private key operations is RFC 6979, Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). Deterministic signatures don't use randomized formatting or randomized k's.

Another reason a RNG is needed for public key and private key operations is validation checks on the key. For example, a key might be checked to ensure a particular constraint holds, like its prime or it has a particular Jacobi symbol.

---

The RNG has to be the same for encryption/decryption, right? So, how to share between processes?

No, the generators can be different. The only requirements is they produce a random stream for some reasonable definition of what it means to be "random". Without splitting too many hairs, it means the generator produces a uniform distribution.

You can find more reading on Crypto++ generators at RandomNumberGenerator on the wiki.

---

If I use this code in a unit test with a global RNG, everything works fine.

One quick word of caution... GlobalRNG is part of the Test namespace. It is defined in test.cpp : 115:

NAMESPACE_BEGIN(CryptoPP)
NAMESPACE_BEGIN(Test)

ANONYMOUS_NAMESPACE_BEGIN
OFB_Mode<AES>::Encryption s_globalRNG;
NAMESPACE_END

RandomNumberGenerator & GlobalRNG()
{
    return dynamic_cast<RandomNumberGenerator&>(s_globalRNG);
}

NAMESPACE_END  // Test
NAMESPACE_END  // CryptoPP

GlobalRNG is a deterministic generator and its not part of the library proper. Your code will fail to compile in the field if you depend on it.

Use one of the other generators discussed at RandomNumberGenerator on the wiki. AutoSeededRandomPool is a good choice.

---

Using the NullRNG() as recommended by https://stackoverflow.com/users/608639/jww in Unable to do RSA Encrption/Decryption using Crypto++ (isValidCoding is false) leads to

std::exception NullRNG: NullRNG should only be passed to functions that don't need to generate random bytes.

That information is incorrect. I need to fix it. Thanks.

---

Interestingly (in a morbid sort of way), Crypto++ took CVE-2015-2141 due to blinding in Rabin-Williams. The blinding value needed to be a quadratic residue; otherwise an attacker could prepare special messages to reveal the private key.

The full paper by Evgeny Sidorov is available at Breaking the Rabin-Williams digital signature system implementation in the Crypto++ library. Here's what the new and improved inverse function looks like after fixing Sidorov's attack (from rw.cpp):

ModularArithmetic modn(m_n), modp(m_p), modq(m_q);
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());
    // Fix for CVE-2015-2141. Thanks to Evgeny Sidorov for reporting.
    // Squaring to satisfy Jacobi requirements suggested by Jean-Pierre Munch.
    r = modn.Square(r);
    rInv = modn.MultiplicativeInverse(r);
} while (rInv.IsZero());

If you read Section 6 of Sidorov's paper, he suggests generating a random r, and then checking the Jacobi symbol of r to ensure its a quadratic residue. If it was not a QR, then try a new random r. The triage used the method, but it showed the scheme slowed down considerably because a random r satisfies the condition with probability 1/16.

However, we knew squaring r ensured we satisfied Jacobi on the first try because r² mod n was always a quadratic residue. The squaring/multiplication only takes log (exp) (not n log (n)), so it turned out to be a significant speedup over trial and error. Before we released the next version of the library, we switched to the squaring method.