RSA Security Analysis

Cryptography · Axiom Academy

Understanding what makes RSA secure and its security assumptions The fundamental security question in RSA: Given the public key (n, e) and a ciphertext c, can an attacker find the original message m? Without the private key d, the attacker must somehow reverse the encryption process. The difficulty of this problem forms the foundation of RSA security. 2. The Connection to Factoring The RSA problem is closely related to the integer factorization problem. If an attacker can factor n into its prime components p and q, they can reconstruct the private key. Why factoring reveals the private key: 1. If you know p and q, you can compute φ(n) = (p - 1)(q - 1) 2. With φ(n) and e, you can compute d = e -1 mod φ(n) 3. Now you have the complete private key! 3. Key Size Recommendations Over Time As computing power increases, the size of RSA keys must grow to maintain security. The evolution of key size recommendations reflects advances in factoring algorithms and hardware. 4. NIST Recommendations and Current Standards The National Institute of Standards and Technology (NIST) provides guidelines for cryptographic key sizes based on desired security levels. 2048 bits: Minimum for new systems (112 bits of security) 3072 bits: Recommended for long-term protection (128 bits of security) 4096 bits: High security applications (152 bits of security)

This is the written version of the interactive lesson above. See the full Cryptography course.