Breaking the RSA encryption based on a $(e,N)$ given an integer $w \neq 0$ such that $e^w = 1 \mod(N)$?

Question

In his book 'Forcing with Random Variables and Proof Complexity' Jan Krajíček claims (p.154) that it is possible to break the RSA encryption with public key $(e,N)$ if one has has an integer $w \neq 0$ such that $e^w = 1 \mod(N)$ holds.

Can anybody explain how this is done or give a source for the claim?

PS: In the application it is also assumed that the binary representations of the prime factors $p$ and $q$ of $N$ have the same length. I am, however, not sure if this has any relevance to the question.

Answer 1

I think you got confused by the somewhat peculiar notation. Krajíček actually writes on p. 155 that one can break the given instance of RSA using $w\ne0$ such that $$g^w=1\pmod N.$$ Now, what is $g$? Well, on p. 154 we see: By an RSA function based on such a pair $(g,N)$ we mean a function $$x<N\to g^x\bmod N.$$ So, as odd as it seems, $g$ is the RSA plaintext, and the “RSA function” maps the public encryption key $x$ to the ciphertext. Your $e$ is $x$, not $g$.

Now, given a $w$ such that $g^w=1\pmod N$, it is easy to see how to compute the plaintext $g$ using the ciphertext $g^x$ and the public key $x$, which is what I’d consider breaking RSA. Unfortunately, this does not invert the function Krajíček calls “RSA function” (where we are given $g$ and $g^x$ and want to compute $x$), which I’d call discrete logarithm.

Knowing my former supervisor, this whole confusion may well be just an unintentional mistake.

The original argument for independence of WPHP assuming security of RSA, not yet framed into the forcing set-up of this book, is from the paper [1]. RSA is defined correctly there, so I suggest you have a look at the paper, specifically Theorem 3.

[1] J. Krajíček, P. Pudlák, Some consequences of cryptographical conjectures for $S^1_2$ and EF, Information and Computation 140 (1998), no. 1, pp. 82–94. ps preprint, journal doi

Answer 2

Note that RSA can actually be defined by performing the operations in the exponent modulo the Carmicheal function $\lambda(N)=\textrm{lcm}(p-1,q-1)$ more efficiently than the Euler totient function $\varphi(n)=(p-1)(q-1)$ as it is traditionally viewed.

Let $C=M^e~(mod~N)$ be the ciphertext. Define the sequence $$X_0=M,\quad X_i=X_{i-1}^e~(mod~N),\quad i\geq 1.$$

This will repeat at some point, and the smallest $k$ such that $X_{k+1}=X_1$ is denoted the period of $M.$ This $k$ is unique and is also the order of $e$ modulo $\lambda(N)$, so it divides $w.$ Thus $k$ divides $\lambda(\lambda(N))$ and $\phi(\lambda(N))$ and $O(k)$ RSA evaluations can break the cipher. Of course $k\leq w,$ so at worst $O(w)$ evaluations may be needed.

This attack is called the message iteration attack and to prevent it being efficient both $\lambda(\lambda(N))$ and $k,$ the order of $e$ with respect to $\lambda(N)$ have to be large enough, say $10^{200}.$ For this one uses doubly safe primes $p$ and $q.$ Note that $p$ is doubly safe if both $(p-1)/2$ and $(p-3)/4$ are also primes.