Ataque a la CRT-RSA

Question

El artículo del profesor Dan Boneh titulado "Twenty years of attacks on the RSA cryptosystem" menciona que (Página 5) se puede atacar a CRT-RSA en la raíz cuadrada del exponente de descifrado. Sin embargo, ningún argumento se da. Sé que esto proviene de un ataque man-in-the-middle. Sin embargo, no puedo entender la idea claramente. ¿Existe alguna nota de clase/papel donde se explique claramente este ataque?

Answer 1

Es una buena pregunta, ya que parece que el documento de Boneh no da ninguna referencia. En realidad no es un ataque de hombre en el medio, al menos no el ataque que yo he visto. En su lugar, es una reminiscencia de baby-step giant-step pero con un giro extra. Así es como funciona.

Supongamos que nos dan $N$ y $e$ , donde $N=pq$ con $p$ y $q$ primos distintos y $ed \equiv 1 \pmod{p-1}$ con $0 < d < D^2$ . No se nos da $p$ , $q$ o $d$ pero conocemos el límite $D$ . Queremos que el factor $N$ en aproximadamente $D$ pasos (hasta los factores logarítmicos). Para lo que voy a hacer, tendremos que asumir que la inversa de $e$ modulo $q-1$ no es $d$ y de hecho no es nada parecido a $d$ pero esta suposición se mantiene para CRT RSA.

Para un valor aleatorio de $x$ , $\gcd(x^{ed}-x,N)$ será $p$ con buena probabilidad (aquí es donde necesitamos la suposición). Si escribimos $d = a + bD$ con $0 \le a,b < D$ entonces $\gcd(x^{ea}x^{ebD}-x,N)$ será $p$ y de hecho el gcd de $\prod_{i=0}^{D-1} (x^{ei}x^{ebD} - x)$ y $N$ también será $p$ con buena probabilidad. (Nótese que si la inversa de $e$ modulo $q-1$ eran de la forma $i+bD$ con $0 \le i < D$ entonces esto fallaría ya que recogeríamos un factor de $q$ en el producto. Esto es lo que quería decir con "cualquier cosa como $d$ " arriba).

Consideremos ahora el polinomio $\prod_{i=0}^{D-1} (x^{ei}y - x)$ en la variable $y$ . En un número de pasos casi lineal en $D$ podemos calcular este polinomio módulo $N$ y luego podemos evaluarlo en cualquier $D$ puntos dados. (Esto requiere algoritmos especiales, ya que, por ejemplo, multiplicar los factores de uno en uno requeriría unos $D^2$ operaciones. Véase el capítulo 10 del libro Modern Computer Algebra de von zur Gathen y Gerhard para conocer los antecedentes de los algoritmos de evaluación e interpolación rápidos).

Dados estos rápidos algoritmos, los pasos finales son fáciles: calculamos el polinomio, calculamos el $D$ puntos de evaluación $y = x^{ebD}$ con $0 \le b < D$ , calcular las evaluaciones del polinomio en estos puntos, y tomar sus gcds con $N$ . Todo esto es en tiempo casi lineal en $D$ y uno de los gcds nos dará el factor $p$ .