Past exam of the computer science course of the University of Oxford / 2015 / Computer security / 1 / d

Avoid constructing the huge integers $c^{3^j}$ explicitly. Maintain $a_0=c$ and $a_j=a_{j-1}^3\mathrm{mod}n$, computing $g_j=\gcd (a_j-c,n)$ after each step.

In case (1), the nontrivial greatest common divisor $g_k$ is one of the prime factors $p,q$. Divide $n$ by it, compute $d$ with the extended Euclidean algorithm, and return $c^d\mathrm{mod}n$.

In case (2), $a_k=c(\mathrm{mod}n)$. The preceding value satisfies $a_{k-1}^3=c(\mathrm{mod}n)$. Cubing is a bijection on the residue classes modulo $n$, so there is only one such cube root, namely the original plaintext $m$. ThereforeFor $k=1$, the preceding value is $a_0=c$; a fixed point is its own plaintext. Keeping the previous iterate makes the recovery immediate once the RSA cycling attack succeeds.

Take the positive integer $k$ whose existence is allowed by the question and writeModulo $p$, if $c=0$ then $c^{3^k}=c$ directly. Otherwise Fermat's little theorem applies, since $3^k-1$ is a multiple of $p-1$. Hence $c^{3^k}=c(\mathrm{mod}p)$. The same two-case argument works modulo $q$. By the Chinese remainder theorem,soThis also covers a ciphertext that is not coprime to $n$; applying Euler's theorem without checking that hypothesis would miss this detail. Equivalently, repeated application of a permutation on a finite set eventually returns to the starting point, although the arithmetic argument gives the requested sufficient exponent.

The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo $p$ and $q$ need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.

If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.

Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.