RSA (cryptosystem)

RSA is an asymmetric algorithm for public key cryptography. It is named after its inventors, Ron Rivest, Adi Shamir, and Len Adleman, who described the algorithm in 1977. Its security is believed to rely on the difficulty of factoring very large numbers. RSA is widely used in electronic commerce.

The algorithm was patented by MIT in 1983 in the United States of America. The patent expired in September 2000. Since the algorithm had been published prior to the patent application, it could not be patented in other countries.

Key Generation

Suppose a user Alice wishes to allow Bob to send her a private message over an insecure transmission medium. She takes the following steps to generate a public key and a private key:

Find two large prime numbers p ≠ q and compute N = p q.
Compute φ(N) = (p-1)(q-1), where φ denotes Euler's φ function.
Choose a small integer e > 1 coprime to φ(N).
Compute d such that d e ≡ 1 (mod φ(N)). This can be performed with the extended Euclidean algorithm; see modular arithmetic.
Destroy all records of p, q, and φ(N).

N and e are the public key, and d is the private key. Alice transmits the public key to Bob, and keeps the private key secret.

Encrypting messages

Suppose Bob wishes to send a message m to Alice. He knows N and e, which Alice has announced. He turns m into a number n < N coprime to N, using some previously agreed-upon reversible protocol. For example, each character in a plaintext message could be converted to its ASCII code, and the codes concatenated into a single number. If necessary, he can break m into pieces and encrypt each piece separately. He then computes the ciphertext c:

c ≡ n^e (mod N)

This can be done using the method of exponentiation by squaring. Bob then transmits c to Alice.

Decrypting messages

Alice receives c from Bob, and knows her private key d. She can recover n from c by the following procedure:

c^d ≡ n (mod N)

Alice can then extract n, since n < N. Given n, she can recover m.

The decryption procedure works because

c^d = n^ed = n^{k (p-1)(q-1) + 1}

for some integer k. Using Euler's generalization of Fermat's little theorem:

n^(p-1)(q-1) ≡ n ^φ(N) ≡ 1 (mod N)

Thus,

n^{k (p-1)(q-1) + 1} ≡ n (mod N)

Signing Messages

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, encrypts it with her secret key, and attaches it as a "signature" to the message. This signature can only be decrypted with her public key. When Bob receives the signed message, he decrypts the signature with Alice's public key, 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.

Security

Suppose Eve, an eavesdropper, intercepts the public key N and e, and the ciphertext c. However, she is unable to directly obtain d, which Alice keeps secret. The most obvious way for Eve to deduce n from c is to factor N into p and q, in order to recover φ(N) and therefore d. However, no polynomial-time method for factoring large integers on a classical computer has yet been found. See integer factorization for a discussion of this problem.

It is not known exactly which complexity classes contain the factoring problem. The decision-problem form of it ("does N have a factor less than M?") is known to be in NP and co-NP, since YES and NO answers can both be checked if given the prime factors along with primality proofs. It is probably not an NP-Hard problem, but is suspected to be outside P, outside NP-Complete, and outside Co-NP-Complete. It is known to be in BQP because of Shor's algorithm (discussed below.)

It has not been proven that factoring N is the only way of deducing n from c, but no easier method has been discovered (at least to public knowledge.) Therefore, we may suppose that Eve is defeated if N is sufficiently large.

If N is 256 bits or shorter, it can be factored in a few hours on a personal computer, using software freely available on the Internet. If N is 512 bits or shorter, it can be factored by several hundred computers as of 1999. It is currently recommended that N be at least 1024 bits long.

In 1993, Peter Shor showed that a quantum computer could in principle perform the factorization in polynomial time. If (or when) quantum computers become a practical technology, Shor's algorithm will make RSA and related algorithms obsolete.

Should an efficient classical factorization code be discovered or a practical quantum computer constructed, using still larger key lengths would provide a stopgap measure. However, any such security break in RSA would be retroactive. An eavesdropper can record the key and the ciphertext, and wait until it becomes practical to decipher the message. Therefore, it is inherently unsafe for long-term secrets to be exchanged with RSA.

Practical considerations

RSA is much slower than DES and other symmetric cryptosystems. In practice, Bob typically encrypts a secret message with a symmetric algorithm, encrypts the (comparatively short) symmetric key with RSA, and transmits both the RSA-encrypted symmetric key and the symmetrically-encypted message to Alice.

This procedure raises additional security issues. For instance, it is of utmost importance to use a strong random number generator for the symmetric key, because otherwise Eve could bypass RSA by guessing the symmetric key.

As with all ciphers, it is important how RSA public keys are distributed. Key distribution must be secured against a man-in-the-middle attack. Suppose Eve has some way to give Bob arbitrary keys and make him believe they belong to Alice. Suppose further than Eve can intercept transmissions between Alice and Bob. Eve sends Bob her own public key, which Bob believes to be Alice's. Eve can then intercept any ciphertext sent by Bob, decrypt it with her own secret key, keep a copy of the message, encrypt the message with Alice's public key, and send the new ciphertext to Alice. In principle, neither Alice nor Bob would be able to detect Eve's presence. Defenses against such attacks are often based on digital certificates or other components of a public key infrastructure.