Ataques a RSA
Tres ataques clásicos cuando RSA se usa mal o con parámetros débiles.
¿Por qué funcionan estos ataques matemáticamente?
Factorización: toda la seguridad de RSA depende de que factorizar n sea inviable. Si n es pequeño, la división de tanteo (probar cada divisor hasta √n) lo rompe en tiempo lineal.
Módulo común: si a·e1 + b·e2 = 1 (Euclides extendido, posible cuando gcd(e1,e2)=1), entonces c1^a · c2^b = (m^e1)^a · (m^e2)^b = m^(a·e1 + b·e2) = m^1 = m (mod n) — sin necesitar ninguna llave privada. Por eso nunca se debe reusar el mismo n para cifrar el mismo mensaje a distintos destinatarios con distinto e.
Wiener: los convergentes de la fracción continua de e/n son, matemáticamente, las mejores aproximaciones racionales posibles a e/n con denominador pequeño. Se puede demostrar que si d < (1/3)·n^(1/4), entonces k/d (para algún k relacionado con φ(n)) aparece necesariamente como uno de esos convergentes — por eso basta probarlos todos, en vez de buscar d por fuerza bruta.