7.10 Performing Raw Encryption with an RSA Public Key

7.10.1 Problem

You want to encrypt a small message using an RSA public key so that only an entity with the corresponding private key can decrypt the message.

7.10.2 Solution

Your cryptographic library should have a straightforward API to the RSA encryption algorithm: you should be able to give it the public key, the data to encrypt, a buffer for the results, an indication of the data's length, and a specification as to what kind of padding to use (EME-OAEP padding is recommended).

When using OpenSSL, this can be done with the RSA_public_encrypt( ) function, defined in openssl/rsa.h.

If, for some reason, you need to implement RSA on your own (which we strongly recommend against), refer to the Public Key Cryptography Standard (PKCS) #1, Version 2.1 (the latest version).

7.10.3 Discussion

Be sure to read the generic considerations for public key cryptography in Recipe 7.1 and Recipe 7.2.

Conceptually, RSA encryption is very simple. A message is translated into an integer and encrypted with integer math. Given a message m written as an integer, if you want to encrypt to a public key, you take the modulus n and the exponent e from that public key. Then compute c = m^e mod n, where c is the ciphertext, written as an integer. Given the ciphertext, you must have the private key to recover m. The private key consists of a single integer d, which can undo the encipherment with the operation m = cd mod n.

This scheme is believed to be as "hard" as factoring a very large number. That's because n is the product of two secret primes, p and q. Given p and q, it is easy to compute d. Without those two primes, it's believed that the most practical way to decrypt messages is by factoring n to get p and q.

RSA is mathematically simple and elegant. Unfortunately, a straightforward implementation of RSA based directly on the math will usually fall prey to a number of attacks. RSA itself is secure, but only if it is deployed correctly, and that can be quite a challenge. Therefore, if you're going to use RSA (and not something high-level), we strongly recommend sticking to preexisting standards. In particular, you should use a preexisting API or, at the very worst, follow PKCS#1 recommendations for deployment.

It's important to note that using RSA properly is predicated on your having received a known-to-be-valid public key over a secure channel (otherwise, man-in-the-middle attacks are possible; see Recipe 7.1 for a discussion of this problem). Generally, secure public key distribution is done with a PKI (see Recipe 10.1 for an introduction to PKI).

From the average API's point of view, RSA encryption is similar to standard symmetric encryption, except that there are practical limitations imposed on RSA mainly due to the fact that RSA is brutally slow compared to symmetric encryption. As a result, many libraries have two APIs for RSA encryption: one performs "raw" RSA encryption, and the other uses RSA to encrypt a temporary key, then uses that temporary key to encrypt the data you actually wanted to encrypt. Such an interface is sometimes called an enveloping interface.

As with symmetric encryption, you need to pass in relevant key material, the input buffer, and the output buffer. There will be a length associated with the input buffer, but you are probably expected to know the size of the output in advance. With OpenSSL, if you have a pointer to an RSA object x, you can call RSA_size(x) to determine the output size of an RSA encryption, measured in bytes.

When performing raw RSA encryption, you should expect there to be a small maximum message length. Generally, the maximum message length is dependent on the type of padding that you're using.

While RSA is believed to be secure if used properly, it is very easy not to use properly. Secure padding schemes are an incredibly important part of securely deploying RSA. Note that there's no good reason to invent your own padding format (you strongly risk messing something up, too). Instead, we recommend EME-OAEP padding (specified in PKCS #1 v2.0 or later).

There are primarily two types of padding: PKCS #1 v1.5 padding and EME-OAEP padding. The latter is specified in Version 2.0 and later of PKCS #1, and is recommended for all new applications. Use PKCS #1 v1.5 padding only for legacy systems. Do not mix padding types in a single application.

With EME-OAEP padding, the message is padded by a random value output from a cryptographic one-way hash function. There are two parameters for EME-OAEP padding: the hash function to use and an additional function used internally by the padding mechanism. The only internal function in widespread use is called MGF1 and is defined in PKCS #1 v2.0 and later. While any cryptographic one-way hash algorithm can be used with EME-OAEP padding, many implementations are hardwired to use SHA1. Generally, you should decide which hash algorithm to use based on the level of security you need overall in your application, assuming that hash functions give you half their output length in security. That is, if you're comfortable with 80 bits of security (which we believe you should be for the foreseeable future), SHA1 is sufficient. If you're feeling conservative, use SHA-256, SHA-384, or SHA-512 instead.

When using EME-OAEP padding, if k is the number of bytes in your public RSA modulus, and if h is the number of bytes output by the hash function you choose, the maximum message length you can encrypt is k - (2h + 2) bytes. For example, if you're using 2,048-bit RSA and SHA1, then k = 2,048 / 8 and h = 20. Therefore, you can encrypt up to 214 bytes. With OpenSSL, specifying EME-OAEP padding forces the use of SHA1.

Do not use PKCS #1 v1.5 public key padding for any purpose other than encrypting session keys or hash values. This form of padding can encrypt messages up to 11 bytes smaller than the modulus size in bytes. For example, if you're using 2,048-bit RSA, you can encrypt 245-byte messages.

With OpenSSL, encryption with RSA can be done using the function RSA_public_encrypt( ):

int RSA_public_encrypt(int l, unsigned char *pt, unsigned char *ct, RSA *r, int p);

This function has the following arguments:

l

Length of the plaintext to be encrypted.

pt

Buffer that contains the plaintext data to be encrypted.

ct

Buffer into which the resulting ciphertext data will be placed. The size of the buffer must be equal to the size in bytes of the public modulus. This value can be obtained by passing the RSA object to RSA_size( ).

r

RSA object containing the public key to be used to encrypt the plaintext data. The public modulus (n) and the public exponent (e) must be filled in, but everything else may be absent.

p

Type of padding to use.

The constants that may be used to specify the type of padding to use, as well as the prototype for RSA_public_encrypt( ), are defined in the header file openssl/rsa.h. The defined constants are:

RSA_PKCS1_PADDING

Padding mode specified in version 1.5 of PKCS #1. This mode is in wide use, but it should only be used for compatibility. Use the EME-OAEP padding method instead.

RSA_PKCS1_OAEP_PADDING

EME-OAEP padding as specified in PKCS #1 Version 2.0 and later. It is what you should use for new applications.

RSA_SSLV23_PADDING

The SSL and TLS protocols specify a slight variant of PKCS #1 v1.5 padding. This shouldn't be used outside the context of the SSL or TLS protocols.

RSA_NO_PADDING

This mode disables padding. Do not use this mode unless you're using it to implement a known-secure padding mode.

When you're encrypting with RSA, the message you're actually trying to encrypt is represented as an integer. The binary string you pass in is converted to an integer for you, using the algorithm described in Recipe 7.8.

You can encrypt only one integer at a time with most low-level interfaces, and the OpenSSL interface is no exception. This is part of the reason there are limits to message size. In practice, you should never need a larger message size. Instead, RSA is usually used to encrypt a temporary key for a much faster encryption algorithm, or to encrypt some other small piece of data.

If there are a small number of possible plaintext inputs to RSA encryption, the attacker can figure out which plaintext was used via a dictionary attack. Therefore, make sure that there are always a reasonable number of possible plaintexts and that all plaintexts are equally likely. Again, it is best to simply encrypt a 16-byte symmetric key.

If you forego padding (which is insecure; we discuss it just to explain how RSA works), the number you encrypt must be a value between 0 and n - 1, where n is the public modulus (the public key). Also, the value must be represented in the minimum number of bytes it takes to represent n. We recommend that you not do this unless you absolutely understand the security issues involved. For example, if you're using OpenSSL, the only reason you should ever consider implementing your own padding mechanism would be if you wanted to use EME-OAEP padding with a hash algorithm stronger than SHA1, such as SHA-256. See the PKCS #1 v2.1 document for a comprehensive implementation guide for EME-OAEP padding.

If you are using a predefined padding method, you don't have to worry about performing any padding yourself. However, you do need to worry about message length. If you try to encrypt a message that is too long, RSA_public_encrypt( ) will return 0. Again, you should be expecting to encrypt messages of no more than 32 bytes, so this should not be a problem.

7.10.4 See Also

• PKCS #1 page: http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1/

• Recipe 7.1, Recipe 7.2, Recipe 7.8, Recipe 10.1