9.1Symmetric and public-key cryptography, RSA
The idea
Public-key cryptography uses a pair of keys: anything locked with one is unlocked with the other. In RSA you pick two primes, compute n and φ, choose e, and find d with e·d ≡ 1 mod φ.
Think of it like this: A mailbox with a slot: anyone can drop a letter in (public key) but only the owner with the key can take letters out (private key).
Why it exists
GATE asks for the private key d, a prime factor of n, or the ciphertext.
How it works
- n = p × q, φ = (p − 1)(q − 1).
- Public key (e, n) with gcd(e, φ) = 1; private d = e−1 mod φ.
- Encrypt c = me mod n; decrypt m = cd mod n.
- If you know n and φ: p + q = n − φ + 1, so p and q are the roots of x² − (p + q)x + n.
Worked example: n = 3007 and φ(n) = 2880, find the larger prime factor.
p + q = 3007 − 2880 + 1 = 128, pq = 3007: roots of x² − 128x + 3007 = (x − 97)(x − 31). Larger = 97 (GATE 2019). Also p = 13, q = 17, e = 35 gives d = 11 (GATE 2017).
Now play with it
- →Use the lab with p = 13, q = 17, e = 35 and read d.
- →Try a message and check that decryption returns it.
Encryption uses the receiver's public key (e, n); decryption uses the receiver's private key d. A signature is the reverse: sign with your private key, anyone verifies with your public key. If you know n and φ(n) you can factor n: p + q = n − φ + 1.
Check yourself
In RSA with φ(n) = 192 and e = 35, the private exponent d satisfies
Exam notes (the dense version)
Symmetric ciphers (DES, 3DES, AES) use one shared secret key: fast, but the key must be distributed. Public-key ciphers use a pair: encrypt with the receiver's public key, decrypt with the receiver's private key. RSA: choose primes p, q; n = p·q; φ(n) = (p − 1)(q − 1); pick e with gcd(e, φ) = 1; compute d = e⁻¹ mod φ (e · d ≡ 1 mod φ). Public key (e, n), private key (d, n). Ciphertext c = mᵉ mod n; plaintext m = cᵈ mod n. If you know n and φ(n), then p + q = n − φ(n) + 1 and you can factor n.
Previous year questions: Network Security (6)
PYQs are grouped by topic, so this is the full set for Network Security; try the ones that match this subtopic. Open all 6 on the topic page.