RSA algorithm

RSA is an algorithm used by modern computers to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys. This is also called public key cryptography, because one of them can be given to everyone. The other key must be kept private. It is based on the fact that finding the factors of an integer is hard (the factoring problem). RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described it in 1978. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message.

Operation

Avash

Alice gives her public key ($n\,$ & $e\,$) to Bob and keeps her private key secret. Bob wants to send message M to Alice.

First he turns M into a number $m$ smaller than $n$ by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext $c\,$ corresponding to:

$c=m^{e}\mod {n}$

This can be done quickly using the method of exponentiation by squaring. Bob then sends $c\,$ to Alice.

Decrypting messages

Avash

Fermat's little theorem yields

$m^{ed}\equiv m{\pmod {p}}$ and

$m^{ed}\equiv m{\pmod {q}}$.

Since $p\,$ and $q\,$ are distinct prime numbers, applying the Chinese remainder theorem to these two congruences yields

$m^{ed}\equiv m{\pmod {pq}}$.

Thus,

$c^{d}\equiv m{\pmod {n}}$.

A working example

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but you can also use OpenSSL to generate and examine a real keypair.

1. Choose two random prime numbers
2. :$p=61$ and $q=53$
3. Compute $n=pq\,$
4. :$n=61*53=3233$
5. Compute the totient $\phi (n)=(p-1)(q-1)\,$
6. :$\phi (n)=(61-1)(53-1)=3120$
7. Choose $e>1$ coprime to 3120
8. :$e=17$
9. Choose $d\,$ to satisfy $de\equiv 1{\pmod {\phi (n)}}\,$
10. :$d=2753$
11. :$17*2753=46801=1+15*3120$.

The public key is ($n=3233$, $e=17$). For a padded message $m\,$ the encryption function is:

$c=m^{e}\mod {n}=m^{17}\mod 3233\,$.

The private key is ($n=3233$, $d=2753$). The decryption function is:

$m=c^{d}\mod {n}=c^{2753}\mod 3233\,$.

For example, to encrypt $m=123$, we calculate

$c=123^{17}\mod 3233=855$

To decrypt $c=855$, we calculate

$m=855^{2753}\mod 3233=123$.

Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation.

Padding schemes

When used in practice, RSA must be combined with some form of padding scheme, so that no values of M result in insecure ciphertexts. RSA used without padding may have some problems:

• The values m = 0 or m = 1 always produce ciphertexts equal to 0 or 1 respectively, due to the properties of exponentiation.
• When encrypting with small encryption exponents (e.g., e = 3) and small values of the m, the (non-modular) result of $m^{e}$ may be strictly less than the modulus n. In this case, ciphertexts may be easily decrypted by taking the eth root of the ciphertext with no regard to the modulus.
• RSA encryption is a deterministic encryption algorithm. It has no random component. Therefore, an attacker can successfully launch a chosen plaintext attack against the cryptosystem. They can make a dictionary by encrypting likely plaintexts under the public key, and storing the resulting ciphertexts. The attacker can then observe the communication channel. As soon as they see ciphertexts that match the ones in their dictionary, the attackers can then use this dictionary in order to learn the content of the message.

In practice, the first two problems can arise when short ASCII messages are sent. In such messages, m might be the concatenation of one or more ASCII-encoded character(s). A message consisting of a single ASCII NUL character (whose numeric value is 0) would be encoded as m = 0, which produces a ciphertext of 0 no matter which values of e and N are used. Likewise, a single ASCII SOH (whose numeric value is 1) would always produce a ciphertext of 1. For systems which conventionally use small values of e, such as 3, all single character ASCII messages encoded using this scheme would be insecure, since the largest m would have a value of 255, and 255³ is less than any reasonable modulus. Such plaintexts could be recovered by simply taking the cube root of the ciphertext.

To avoid these problems, practical RSA implementations typically embed some form of structured, randomized padding into the value m before encrypting it. This padding ensures that m does not fall into the range of insecure plaintexts, and that a given message, once padded, will encrypt to one of a large number of different possible ciphertexts. The latter property can increase the cost of a dictionary attack beyond the capabilities of a reasonable attacker.

Standards such as PKCS have been carefully designed to securely pad messages prior to RSA encryption. Because these schemes pad the plaintext m with some number of additional bits, the size of the un-padded message M must be somewhat smaller. RSA padding schemes must be carefully designed so as to prevent sophisticated attacks. This may be made easier by a predictable message structure. Early versions of the PKCS standard used ad-hoc constructions, which were later found vulnerable to a practical adaptive chosen ciphertext attack. Modern constructions use secure techniques such as Optimal Asymmetric Encryption Padding (OAEP) to protect messages while preventing these attacks. The PKCS standard also has processing schemes designed to provide additional security for RSA signatures, e.g., the Probabilistic Signature Scheme for RSA (RSA-PSS).

Signing messages

Suppose Alice uses Bob's public key to send him an encrypted message. In the message, she can claim to be Alice but Bob has no way of verifying that the message was actually from Alice since anyone can use Bob's public key to send him encrypted messages. So, in order to verify the origin of a message, RSA can also be used to sign a message.

Suppose Alice wishes to send a signed message to Bob. She produces a hash value of the message, raises it to the power of d mod n (just like when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he raises the signature to the power of e mod n (just like encrypting a message), and compares the resulting hash value with the message's actual hash value. If the two agree, he knows that the author of the message was in possession of Alice's secret key, and that the message has not been tampered with since.

Note that secure padding schemes such as RSA-PSS are as essential for the security of message signing as they are for message encryption, and that the same key should never be used for both encryption and signing purposes.

Other websites

• The Original RSA Patent as filed with the U.S. Patent Office by Rivest; Ronald L. (Belmont, MA), Shamir; Adi (Cambridge, MA), Adleman; Leonard M. (Arlington, MA), December 14, 1977, U.S. Patent 4,405,829.
• PKCS #1: RSA Cryptography Standard (RSA Laboratories website)
• Thorough walk through of RSA
• Prime Number Hide-And-Seek: How the RSA Cipher Works
• Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (free PDF downloads), see Chapter 8
• Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: On the Power of Simple Branch Prediction Analysis
• A New Vulnerability In RSA Cryptography, CAcert NEWS Blog
• Example of an RSA implementation with PKCS#1 padding (GPL source code)
• Kocher's article about timing attacks