The shortest answer to any question about securely using RSA is: Don't.

Because there are much better cryptography choices available today, if you can avoid using RSA, don't use RSA. Then everything else in this document becomes not your problem.

Throughout this post, we assume at least a casual understanding of what RSA is, and the role of asymmetric cryptography in general.

If you do not meet these prerequisites, or experience any difficulty understanding the rest of this post, this is a good introduction to RSA and this talk by Colin Percival (slides) is a good follow-up. If you're more of a book learner, you can't go wrong with a copy of Serious Cryptography by Dr. Jean-Philippe Aumasson.

The Web Developers' Guide to RSA Security Failures

There are a lot of common (and a few uncommon) ways to use RSA insecurely. So many, in fact, that most cryptographers have discouraged its use in favor of elliptic curve cryptography. (Soon, this will be replaced by post-quantum cryptography.)

RSA Failure #1: Textbook/Unpadded RSA

The most dangerous thing you can do with RSA is build it yourself using bignum libraries (e.g. GMP).

The second most dangerous thing you can do with RSA is to use it without what the literature calls padding (but is more appropriately called armor).

Most of the time, when people do the most dangerous thing, they also do the second most dangerous thing.

To illustrate why this is dangerous with an example: If you're encrypting a 256-bit AES key with unpadded 2048-bit RSA, I can decrypt the ciphertext simply by taking the cube root of the ciphertext (assuming $e = 3$).

The reason for this is simple: If your message raised to the $e$ power doesn't wrap the modulus, taking the $e^{th}$ root will reveal your original message.

This is why RSA padding schemes were originally specified. Unfortunately, almost everyone uses an insecure one.

RSA Failure #2: PKCS#1 v1.5 Padding

There are two attacks against RSA PKCS#1 v1.5 padding, published by Daniel Bleichenbacher, which make it a dangerous standard to use:

1. Bleichenbacher's 1998 padding oracle attack on RSA encryption.
2. Bleichenbacher's 2006 forgery attack on RSA signatures.

Unfortunately, despite how straightforward these attacks are, PKCS1v1.5 is still the default mode used today. It even surfaced in the recently published WebAuthn standard for RSA signatures.

In December 2017, Hanno Böck, et al. managed to combine these two to sign a chosen plaintext message using Facebook's RSA private key, in what they call the ROBOT Attack.

In response to the failure of PKCS#1 v1.5 padding, a new padding scheme called OAEP was standardized.

RSA Failure #3: Low Exponent

If you sign a lot of messages with the same RSA private key, and use a low exponent ($e = 3$) and/or part of your private key is known (for example, if it was generated using a vulnerable library that had a small number of possible values for one of the values for p or q), be prepared for an attacker to steal your entire private key using Coppersmith's Attack.

(Honorable mention: ROCA, the Return Of Coppersmith's Attack.)

Having a low value for $e$ also sets you up for Bleichenbacher's 2006 forgery attack (see above).

RSA Failure #4: Timing Side-Channels

If you've read this far and haven't recoiled in horror yet, you're probably thinking something to the tune of, "Joke's on you! I'm already using RSAES-OAEP with e = 65537 so I'm totally safe." Not necessarily. Enter Manger's attack on RSA OAEP, which uses a timing leak to decrypt messages encrypted with RSA using OAEP padding.

Public exploit code for Manger's attack is available online, courtesy of Kudelski Security.

Cooking With Petrol, or Using RSA Securely

Now that we have a good understanding of how RSA goes wrong in the real world, we can hopefully begin to design systems that use RSA but aren't trivially broken.

Use RSA Only with Secure Parameters

Following Colin Percival's advice in 2009:

Asymmetric encryption: Use RSAES-OAEP with SHA256 as the hash function, MGF1+SHA256 as the mask generation function, and a public exponent of 65537. Make sure that you follow the decryption algorithm to the letter in order to avoid side channel attacks.

[...]

Asymmetric signatures: Use RSASSA-PSS with SHA256 as the hash function, MGF1+SHA256 as the mask generation function, and a public exponent of 65537.

If you can adhere to Colin's recommendations, you're (probably) safe.

• You're not using textbook/unpadded RSA.
• Both Bleichenbacher attacks are avoided by using secure padding modes (a.k.a. RSA armor)
• Coppersmith's attack won't work against low exponents ($e = 3$ instead of $e = 65537$).
• Manger's attack won't work if you avoid side-channel attacks.

If you're using a cryptography library in 2018 that supports OAEP and PSS with MGF1+SHA256, there's a good chance it also supports elliptic curve cryptography too.

Otherwise, remain vigilant against downgrade attacks and don't ever encrypt messages directly with RSA. (See below for what to do instead.)

The Anti-BB'98 Dance

Okay, let's say you're forced to accept RSA-encrypted ciphertexts that use PKCS #1v1.5 padding. Game over, right? Not necessarily, but you're still playing with fire (and/or thermite).

Recall that the exploit against PKCS#1 v1.5 depends on the attacker's capability to discern RSA padding errors. There is a strategy for decrypting PKCS1v1.5-padded ciphertexts without exposing the error oracle (and, thus, denying any exploit), but it requires that your entire RSA handling code perform in constant-time, even when given invalid inputs. We call it the anti-BB'98 dance (BB'98 is short for "Bleichenbacher 1998").

Let's assume that you're given a message consisting of an RSA-encrypted ciphertext ($C$) and a ciphertext produced using symmetric-key cryptography ($D$). If you decrypt $C$ with your RSA private key, you'll get the key needed to decrypt $D$.

(For the sake of argument, assume $D$ is encrypted with either AES-GCM or AES-CBC+HMAC-SHA2 using an Encrypt then MAC construction, where the MAC also covers the IV.)

This is a naive hybrid cryptosystem, but it works well enough for our purposes.

A vulnerable decryption algorithm would look something like this:

1. Decrypt $C$ using your RSA private key, to obtain $k$ (one-time AES key).
2. If step 1 failed, abort.
3. Use $k$ to verify-then-decrypt $D$.

Given enough guesses at $C$, an attacker can exploit PKCS1v1.5 to decrypt $k$ which in turn violates the confidentiality of $D$.

The non-vulnerable decryption algorithm looks like this:

1. Generate a random dummy key, which we'll call $k^{\prime}$.
2. Decrypt $C$ using your RSA private key, to obtain $k$ (one-time AES key).
3. If step 2 failed, use a constant-time algorithm to swap $k$ out for $k^{\prime}$.
4. Use $k$ to verify-then-decrypt $D$.

Because we can make all chosen ciphertexts for $C$ result in a decryption failure for $D$, as long as...

• $D$ isn't vulnerable to chosen-ciphertext attacks
• The algorithm as described above leaks no timing information

...then the padding oracle exploit is effectively mitigated. The anti-BB'98 dance, as described here, is implemented in BearSSL. If it were implemented in PHP, it might look like this:

<?php
declare(strict_types=1);
namespace ParagonIE\BlogExampleCode;

/**
 * Implements encryption RSA with PKCS1v1.5 padding
 * using the Anti-BB'98 dance.
 *
 * @ref https://paragonie.com/b/_8qH-xPuGPUoSSsc
 */
class RSAPKCS1v15
{
    public static function encrypt(string $message, string $publicKey): array
    {
        $key = \random_bytes(32);
        $C = '';

        // This defaults to PKCS1v1.5:
        \openssl_public_encrypt($key, $C, $publicKey);

        $iv = \random_bytes(16);
        $cipher = \openssl_encrypt(
            $message,
            'aes-256-ctr',
            $key,
            OPENSSL_RAW_DATA,
            $iv
        );
        $mac = \hash_hmac('sha256', $iv . $cipher, $key, true);
        $D = $mac . $iv . $cipher;
        return [\bin2hex($C), \bin2hex($D)];
    }

    public static function decrypt(string $CHex, string $DHex, string $privateKey): string
    {
        $kPrime = \random_bytes(32);
        $C = \hex2bin($CHex);
        $D = \hex2bin($DHex);
        $k = '';
        $success = \openssl_private_decrypt($C, $k, $privateKey);

        // Do a constant-time swap:
        $key = self::cswap32($k, (string) $kPrime, $success);

        $mac = \mb_substr($D, 0, 32, '8bit');
        $iv = \mb_substr($D, 32, 16, '8bit');
        $cipher = \mb_substr($D, 48, null, '8bit');
        $recalc = \hash_hmac('sha256', $iv . $cipher, $key, true);
        if (!\hash_equals($recalc, $mac)) {
            throw new \Exception('Invalid MAC');
        }
        return \openssl_decrypt(
            $cipher,
            'aes-256-ctr',
            $key,
            OPENSSL_RAW_DATA,
            $iv
        );
    }

    /**
     * Branch-less, timing safe version of
     *   $A = ($switch === 0 ? $A : $B);
     *
     * @param string $A
     * @param string $B
     * @param bool $success
     * @return string
     */
    public static function cswap32(string $A, string $B, bool $success): string
    {
        $A .= \str_repeat("\x00", 32);
        $B .= \str_repeat("\x00", 32);
        /** @var int $mask 0 if $success is true, otherwise 255 */
        $mask = (((int) $success) - 1) & 0xff;

        $C = '';
        for ($i = 0; $i < 32; ++$i) {
            $C .= self::intToChr(
                (self::chrToInt($A[$i]) ^ self::chrToInt($B[$i])) & $mask
            );
        }
        return (string) mb_substr($A ^ $C, 0, 32, '8bit');
    }

    public static function chrToInt(string $chr): int
    {
        $chunk = \unpack('C', $chr);
        return (int) ($chunk[1]);
    }

    public static function intToChr(int $int): string
    {
        return \pack('C', $int);
    }
}

An online demo for this example code is available, thanks to 3v4l.org. The linked snippet demonstrates that, whether you tamper with the RSA or AES ciphertext, the whole system behaves as if the MAC was invalid on the AES ciphertext, and doesn't leak any hints about this discrepancy in timing information.

Thus, the Bleichenbacher attack is stopped short in its tracks.

Secure Hybrid Cryptosystem

In the previous section, we described a naive hybrid cryptosystem that looks like this:

• Encryption
  1. Generate a random 32-byte key, $k$.
  2. Encrypt $k$ with your RSA public key to get $C$.
  3. Encrypt your message with $k$ to get $D$.
  4. Return $C$ and $D$.
• Decryption
  1. Decrypt $C$ with your RSA private key to get $k$.
  2. Decrypt $D$ using $k$.
  3. Return the decrypted plaintext (or fail because of the authentication tag).

An example implementation in JavaScript, with an imaginary cryptography abstraction library loaded in as crylib, might look like this:

/**
 * WARNING: This example code is naive and should not be used.
 */
function encrypt(message, publicKey) {
    var k = crylib.randomBytes(32);
    var C = crylib.rsaEncrypt(k, publicKey);
    var D = crylib.aesEncrypt(message, k);
    return [C, D];
}
function decrypt(C, D, privateKey) {
    var k = crylib.rsaDecrypt(C, privateKey);
    return crylib.aesDecrypt(D, k);
}

This code is especially dangerous if the hypothetical crylib defaults to PKCS1v1.5 padding. If it uses OAEP, it might be secure, but let's say we have no knowledge of whether or not our hypothetical crylib is secure against side-channels. What can we do?

For starters, we can reuse the strategy outlined in the previous section. This protects us if PKCS1v1.5 is accepted by the underlying cryptography library.

We can also change how we handle $k$ to minimize the risk of information leakage during decryption. To this end, we'll use HMAC-SHA256 over the RSA ciphertext ($C$), using the RSA plaintext ($k$) as the HMAC key, and use the output for our symmetric encryption. We'll call it something else ($m$?) for simplicity.

By using HMAC in this way, we can make it so any attempts to attack $C$ (whether or not they leak some information about $k$) result in a pseudorandom message key ($m$) and $D$ will fail to decrypt because of an invalid MAC.

Our protocol now looks like this:

• Encryption
  1. Generate a random 32-byte key, $k$.
  2. Encrypt $k$ with your RSA public key to get $C$.
  3. Calculate the HMAC-SHA256($C$, $k$) to get the message key $m$.
  4. Encrypt your message with $m$ to get $D$.
  5. Return $C$ and $D$.
• Decryption
  1. Generate a random dummy key, which we'll call $k^{\prime}$.
  2. Decrypt $C$ using your RSA private key, to obtain $k$ (one-time AES key).
  3. If step 2 failed, use a constant-time algorithm to swap $k$ out for $k^{\prime}$.
  4. Calculate the HMAC-SHA256($C$, $k$) to get the message key $m$.
  5. Decrypt $D$ using $m$.
  6. Return the decrypted plaintext (or fail because of the authentication tag).

One possible advantage of this construction is domain separation between derived keys, but the main purpose is to put less burden on RSA alone to keep your keys secret.

Sidenote: We're reasonably sure this construction has a distinct name in the cryptographic literature, but we cannot recall what it was. Our old notes just say "KEM+DEM" but that only comes up when discussing NTRU-Prime.

Summary

RSA is painful to implement securely. Compare the level of effort here with using libsodium's crypto_box_seal() or crypto_sign_detached() and you'll quickly see why cryptography experts tell developers, "Just use NaCl/libsodium".

Further Reading: Cryptographically Secure PHP Development