Number Theory and Asymmetric Cryptography
This domain tests the arithmetic behind RSA, Diffie-Hellman and elliptic-curve cryptography, and the distinction between key exchange, encryption and digital signatures. Expect small-number RSA calculations and questions about which hard problem underpins each algorithm.
Core number theory
- Modular arithmetic reduces values to a fixed range; gcd(a,b)=1 means a and b are coprime.
- Euler's totient φ(n) counts integers below n that are coprime to n. For distinct primes p and q, φ(pq)=(p−1)(q−1).
- Fermat's little theorem: if p is prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p).
- A modular inverse d satisfies e·d ≡ 1 (mod φ(n)).
RSA
Choose primes p and q, compute n=pq and φ(n). Choose e with 1<e<φ(n) and gcd(e,φ(n))=1. Compute d=e^(−1) mod φ(n). Public key is (n,e); private key is d. Encryption is c=m^e mod n; decryption is m=c^d mod n. Security rests on the difficulty of factoring n. Textbook RSA is deterministic, so real systems use padding such as OAEP.
Diffie-Hellman, ECC and signatures
Diffie-Hellman lets two parties derive a shared secret over a public channel; its hardness assumption is the discrete logarithm problem, and it is unauthenticated, so it is vulnerable to man-in-the-middle unless bound to certificates or signatures. ECC offers comparable security with much smaller keys. DSA/ECDSA produce signatures: the signer uses the private key, and anyone can verify with the public key.
Worked example
Let p=5, q=11, so n=55 and φ=40. Choose e=3 because gcd(3,40)=1. Find d: 3×27=81 ≡ 1 (mod 40), so d=27. Encrypt m=7: 7^3=343; 343−330=13, so c=13. Decrypt: 13^27 mod 55 = 7. The public key is (55,3); the private key is 27.
Traps
- Using n instead of φ(n) when computing d.
- Choosing e that shares a factor with φ(n).
- Saying RSA “encrypts with the private key” for confidentiality; encryption uses the public key, signing uses the private key.
- Treating Diffie-Hellman as authenticated by itself.
- Using RSA directly on large files instead of a hybrid scheme.