RSA Public-Key Cryptography
RSA Public-Key Cryptography
RSA (Rivest-Shamir-Adleman) was the first practical public-key cryptosystem. Its security rests on the difficulty of factoring large integers. Despite its age, RSA underpins much of today's internet security when used correctly.
Definition
Key generation: choose distinct primes \(p, q\); set \(n = pq\), \(\phi(n)=(p-1)(q-1)\); pick \(e\) with \(\gcd(e,\phi(n))=1\); compute \(d\equiv e^{-1}\pmod{\phi(n)}\). Public key: \((n,e)\); private key: \((n,d)\).
Key Result
Correctness: \(c = m^e\pmod{n}\), \(m' = c^d\pmod{n}\). By Euler's theorem \(m^{\phi(n)}\equiv 1\), so \(m' = m^{ed} = m^{1+k\phi(n)} = m\cdot(m^{\phi(n)})^k \equiv m\pmod{n}\).
Example 1
Example with small primes: \(p=11,q=13,n=143,\phi=120\). Choose \(e=7\); then \(d=103\) (since \(7\times103=721=6\times120+1\)). Encrypt \(m=10\): \(10^7\bmod 143=10\). Decrypt: \(10^{103}\bmod 143=10\).
Example 2
RSA padding: raw RSA is deterministic and malleable. OAEP (Optimal Asymmetric Encryption Padding) adds randomness and redundancy, making the ciphertext indistinguishable under chosen-ciphertext attacks (IND-CCA2 secure).
Loading rsa-cipher...
Practice
- Why is it insecure to use the same RSA key pair to encrypt and sign?
- What is the RSA problem and how does it relate to integer factorization?
- Describe a timing side-channel attack on RSA and how to mitigate it.
- Why should RSA key sizes be at least 2048 bits today?
Show Answer Key
1. If the same key pair encrypts and signs: an adversary who submits a ciphertext $c$ for 'signing' gets $c^d\bmod n$ — which is the decryption of $c$. This is a chosen-ciphertext attack. Even with padding, using the same key for both operations weakens security proofs (which assume independent keys). Best practice: separate key pairs for encryption and signing.
2. RSA problem: given $(n,e,c)$, find $m$ such that $m^e \equiv c \pmod{n}$. This is at least as hard as factoring $n$ (if you can factor, you can solve RSA), but it's unknown whether it's strictly harder. No efficient reduction from factoring to RSA is known. In practice, RSA security assumes the RSA problem is hard, which implies factoring is hard.
3. Timing attack: RSA decryption time depends on the bits of the private exponent $d$ (in square-and-multiply, multiplications vary with bit values). An attacker measures decryption times for many ciphertexts and statistically infers $d$ bit by bit. Mitigation: constant-time modular exponentiation (Montgomery multiplication), RSA blinding ($c' = c \cdot r^e$, decrypt, unblind by dividing by $r$), or always performing both square and multiply.
4. Factoring algorithms (GNFS) have subexponential complexity $\sim e^{(\ln n)^{1/3}(\ln\ln n)^{2/3}}$. A 1024-bit key is within reach of well-resourced attackers (estimated at ~$2^{80}$ operations). 2048 bits provides ~$2^{112}$ security, sufficient for the near term. NIST recommends $\geq 2048$ bits. Quantum computers (Shor's algorithm) would break RSA regardless of key size, motivating post-quantum alternatives.