Una idea casi (pero no del todo) completa. Al principio pensé que lo tenía, pero era demasiado optimista :-( ¡Esto necesita más trabajo!
Creo que tener un algoritmo como $A$ abriría el camino para el siguiente ataque.
- Generar un conjunto "probable $D$ de representantes de cosets del subgrupo $H$ . Obsérvese que el índice de $H$ en $G$ es como máximo dieciséis, por lo que $D$ es un conjunto razonablemente pequeño. En realidad, podemos utilizar un conjunto mayor en lugar de $D$ mientras siga siendo razonablemente pequeño, y probablemente contenga un conjunto de representantes de cosets de $H$ .
- Si $e$ es el exponente público, y $c$ es el texto cifrado dado, entonces uno de $c\ell^{-e}$ , $\ell\in D$ estará en el subgrupo $H$ . Esto se debe a que $xH=\ell H$ para uno $\ell\in D$ (según la hipótesis deseada).
- Así que para cada candidato $\ell\in D$ probamos el algoritmo $A$ con la entrada $c\ell^{-e}$ . Si tiene éxito, pasamos al paso 4. En caso contrario, probaremos con otro $\ell$ .
- Si $x$ es el texto plano correspondiente a $c\ell^{-e}$ . Entonces $x'=x\ell$ es el texto plano correspondiente a $x$ . En otras palabras, se agrietó $c$ .
Tengo algunas dudas sobre la mejor manera de localizar $D$ . Mi primer pensamiento fue buscar un número primo $\ell\equiv1\pmod4$ tal que $\left(\dfrac n\ell\right)=-1$ . Entonces $\left(\dfrac p\ell\right)=-1$ o $\left(\dfrac q\ell\right)=-1$ y, por reciprocidad cuadrática, o bien $\left(\dfrac \ell p\right)=-1$ o $\left(\dfrac \ell q\right)=-1$ . Si encontramos suficientes primos $\ell_i, i=1,2,\ldots,m,$ entonces es probable que sus cosets generen el grupo $G/H$ . En ese momento el conjunto de números $\prod_{j=1}^m\ell_j^{a_j}, 0\le a_j<4$ puede desempeñar el papel de $D$ .
Una posibilidad aún más simple (no determinista) es simplemente seguir probando números aleatorios en el papel de $\ell$ en el paso 3.
