- 2070 Asar · 4 marks
Short note: RSA
Short answer
RSA is a public-key algorithm using a public key (e,n) for encryption and a private key (d,n) for decryption. Security relies on the difficulty of factoring large primes p and q where n=p×q. Key generation computes φ(n)=(p-1)(q-1), chooses e coprime to φ(n), and finds d as e's modular inverse. Used for key exchange, digital signatures, and encrypting small data like session keys; 2048-bit keys are recommended.
Write a short note on RSA (printed as "RSK").
RSA (Rivest, Shamir, Adleman, 1977) is the most widely used public-key (asymmetric) algorithm. It uses two different but related keys: the public key to encrypt (or verify) and the private key to decrypt (or sign). Its strength is the difficulty of factorising n = p × q when p and q are large primes.
Key generation
- Choose primes p, q. 2. n = p × q. 3. φ(n) = (p − 1)(q − 1). 4. Choose e with gcd(e, φ(n)) = 1. 5. d = e⁻¹ mod φ(n). Public key = (e, n); private key = (d, n).
Operation
- Encryption: C = Mᵉ mod n. Decryption: M = Cᵈ mod n.
Small example
p = 3, q = 11, n = 33, φ = 20, e = 3, d = 7 (3 × 7 = 21 ≡ 1 mod 20). Message M = 4: C = 4³ mod 33 = 64 mod 33 = 31; M = 31⁷ mod 33 = 4.
Uses and features
- Key exchange, digital signatures, and encryption of small data such as session keys (SSL/TLS, PGP).
- Slower than symmetric ciphers (like AES), so it is used with them.
- Key sizes 2048 bits or more are recommended today.
✓ Answer checked by Claude Opus 5.5 (high effort)