English
Menu

What is RSA cryptosystem?

A public-key cryptosystem devised in 1977 by Rivest, Shamir and Adleman. The public key is the product n of two large primes p and q together with a public exponent e, and the private key is the d that satisfies e × d ≡ 1 (mod (p − 1)(q − 1)). Encryption is c = m^e mod n and decryption m = c^d mod n. Its security rests on the difficulty of factoring n, and it can be used for both encryption and signatures. In practice it is combined with randomized padding such as OAEP or PSS.

Japanese name: RSA暗号

RSA cryptosystem appears in 10 practice questions across 2 topics, including Applied Cryptography, Quantum Computing Hardware.

Field: Applied Cryptography

A small-number example

With p = 5 and q = 11, n = 55 and (p − 1)(q − 1) = 40. Taking e = 3, 3 × 27 = 81 ≡ 1 (mod 40), so d = 27. The plaintext m = 7 is encrypted as 7³ = 343 ≡ 13 (mod 55), and computing 13^27 mod 55 gives back 7.

Key length and security

In the table of NIST SP 800-57, a 2048-bit n is a guideline for 112-bit security and 3072 bits for 128-bit security. For the same security, RSA needs much longer keys and signatures than elliptic-curve cryptography, and key generation and signing are heavier. The public exponent is usually 65537 (2^16 + 1), which keeps the computation fast.

How its use has changed

Older versions of TLS widely used a key exchange in which the client encrypted key material with the server's RSA public key, but it was removed in TLS 1.3 because it lacks forward secrecy. Today RSA is mainly used for signatures on certificates and software. A large quantum computer could break it with Shor's algorithm, so migration to post-quantum cryptography is under way.

Try it: questions about RSA cryptosystem

The mechanism of RSA is checked with small numbers. From the primes p = 5 and q = 11, n = pq is formed, and the public exponent is e = 3. With φ(n) = (p − 1)(q − 1), which of the following is the private exponent d (0 < d < φ(n)) that satisfies e × d ≡ 1 (mod φ(n))?

  1. A5
  2. B27
  3. C37
Show answer and explanation

Answer: B. 27

n = 5 × 11 = 55 and φ(n) = 4 × 10 = 40. Looking for d such that 3 × d leaves a remainder of 1 when divided by 40, 3 × 27 = 81 = 2 × 40 + 1, so d = 27. The public key is (n, e) = (55, 3) and the private key is d = 27; the security rests on the fact that without knowing p and q one cannot find φ(n), and so cannot find d. In real RSA, p and q are each large primes of more than 1000 bits, and e is commonly 65537.

FAQ

Why must p and q be kept secret?

Because anyone who knows p and q can compute (p − 1)(q − 1) and then derive d from the public e. Since n is public, the security relies on the difficulty of factoring n.

Why is RSA not used to encrypt files directly?

RSA can only encrypt numbers smaller than n at a time, and it is far slower than symmetric-key encryption. In practice the file is encrypted with a symmetric cipher such as AES, and only that symmetric key is protected with the public key, which is called hybrid encryption.

RSA cryptosystem in the explanations

Questions that mention RSA cryptosystem (10)

  1. The mechanism of RSA is checked with small numbers. From the primes p = 5 and q = 11, n = pq is formed, and the public exponent is e = 3. With φ(n) = (p − 1)(q − 1), which of the following is the private exponent d (0 < d < φ(n)) that satisfies e × d ≡ 1 (mod φ(n))?
  2. In RSA, let the public key be n = 55 and e = 3. Which of the following is the ciphertext c when the plaintext m = 7 is encrypted as c = m^e mod n?
  3. Which of the following correctly describes a problem with using textbook RSA (computing c = m^e mod n directly from the plaintext m) without padding in real communication?
  4. In the table of NIST SP 800-57, which of the following is the combination of RSA key length (the number of bits of n) and elliptic-curve key length given as the guideline for security comparable to a 128-bit symmetric-key cipher (AES-128)?
  5. Once large fault-tolerant quantum computers are built, which ciphers are expected to have their security seriously undermined by Shor's algorithm?
  6. Which correctly describes post-quantum cryptography (PQC)?
  7. In TLS, which of the following key exchange methods provides the property that previously recorded communications cannot be decrypted even if the private key of the server certificate leaks later (forward secrecy)?
  8. Which of the following correctly describes a change from TLS 1.2 in TLS 1.3 (RFC 8446)?
  9. Which of the following is the correct combination of what the TLS 1.3 cipher suite TLS_AES_128_GCM_SHA256 specifies?
  10. Which of the following is an appropriate measure to increase crypto agility (the property of making cryptographic schemes easy to replace) in system design?

Books on Applied Cryptography Ad

As an Amazon Associate I earn from qualifying purchases.

Comparisons that include this term

Related terms

TLS Modulo operation Elliptic-curve cryptography Diffie–Hellman key exchange Shor's algorithm AES (Advanced Encryption Standard) Post-quantum cryptography Forward secrecy Authenticated encryption (AEAD) Public-key cryptography

Back to the glossary