RSA

RSA is a public-key cryptosystem used for secure data transmission and digital signatures. It was described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. The security of RSA rests on the difficulty of factoring the product of two large primes. The system uses a pair of keys: a public key for encryption and signature verification, and a private key for decryption and signing.

Key generation chooses two large primes p and q, computes n = pq, and uses φ(n) or lcm(p−1,q−1). Choose e with gcd(e,φ(n))=1; compute d as the modular inverse of e mod φ(n). Public key is (e,n); private key is d. Encryption: c ≡ m^e mod n; decryption: m ≡ c^d mod n. Signatures: use private key to produce s ≡ hash(m)^d mod n; verification uses e.

Security rests on factoring resistance and correct implementation. Modern practice uses 2048-bit keys or larger and padding schemes such as OAEP for encryption and PSS for signatures; PKCS#1 v1.5 is older. RSA is widely used in TLS, S/MIME, and PGP. Attacks include side-channel and timing attacks; RSA blinding mitigates some leaks. Quantum computing via Shor’s algorithm could break RSA.

Variants include RSA-OAEP, RSASSA-PKCS1-v1_5, RSASSA-PSS.