RSA public key encryption

Public and private keys

Each user has a key pair. The public key is shared with everyone; the private key is kept secret. A message encrypted with someone's public key can only be decrypted with their private key. This solves the key exchange problem: no secret key ever needs to be sent.

Generating RSA keys

1. Choose two large prime numbers, p and q.

2. Compute n = p x q (the modulus) and φ(n) = (p - 1)(q - 1).

3. Choose e, with 1 < e < φ(n), sharing no common factor with φ(n).

4. Find d such that (e x d) mod φ(n) = 1.

5. Public key = (e, n); private key = (d, n). p, q and φ(n) are kept secret or destroyed.

Encrypt: c = m^e mod n. Decrypt: m = c^d mod n.

Why it is secure

Anyone can see n and e. To find d you need φ(n), which needs p and q. With n hundreds of digits long, factorising n would take impractically long with known methods on ordinary computers, while multiplying p by q is quick. Real keys are 2048 bits or more.

Benefits, drawbacks and vulnerabilities

Benefits: no shared secret to exchange; supports digital signatures (encrypt a hash with the private key); widely supported.

Drawbacks: much slower than symmetric encryption, so it is used to exchange a symmetric session key (as in TLS) rather than to encrypt bulk data; keys must be long.

Vulnerabilities: small or poorly chosen primes can be factorised; a stolen private key breaks everything; without certificates, an attacker could substitute their own public key (man-in-the-middle); a large enough quantum computer running Shor's algorithm could factorise n quickly.

Worked example

Using the public key (e, n) = (3, 55), encrypt the message m = 7.

1. c = m^e mod n = 7³ mod 55
2. 7³ = 343
3. 343 = 6 x 55 + 13

Answer: c = 13

Check yourself

1. In RSA, p = 7 and q = 13. Calculate n.
   Show answer

   91. n = 7 x 13 = 91.

2. In RSA, p = 7 and q = 13. Calculate φ(n).
   Show answer

   72. φ(n) = 6 x 12 = 72.

3. In RSA, φ(n) = 72 and e = 5. Find d, the smallest positive number with (e x d) mod 72 = 1.
   Show answer

   29. 5 x 29 = 145 = 2 x 72 + 1.

4. Using the public key (e, n) = (7, 33), encrypt m = 4.
   Show answer

   16. 4⁷ = 16384; 16384 mod 33 = 16.

5. The private key for the key pair (7, 33) is (d, n) = (3, 33). Decrypt c = 16.
   Show answer

   4. 16³ = 4096; 4096 mod 33 = 4.

6. Alice wants to send Bob a confidential message using RSA. Which key does she encrypt it with?
   • Bob's private key
   • Bob's public key
   • Alice's private key
   • Alice's public key
   Show answer

   Bob's public key. Only Bob's private key can then decrypt it.

7. Why does using very large primes make RSA secure?
   • Large primes cannot be stored by attackers
   • Large primes make the message shorter
   • Large primes are kept in the public key
   • Multiplying the primes is easy, but factorising their product takes an impractically long time
   Show answer

   Multiplying the primes is easy, but factorising their product takes an impractically long time. No known efficient method factorises large n on classical computers.

8. Which is a vulnerability of RSA?
   • The public key must be sent secretly
   • It cannot be used for digital signatures
   • A sufficiently powerful quantum computer could factorise n quickly
   • It only works with symmetric keys
   Show answer

   A sufficiently powerful quantum computer could factorise n quickly. Shor's algorithm on a large quantum computer threatens RSA.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.