4
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Look at this answer of voloch: mathoverflow.net/questions/6248/… $\endgroup$
    – Lucia
    May 31, 2016 at 3:27
  • $\begingroup$ Unfortunately this algorithm is probabilistic and the application in the book needs an deterministic algorithm. Furthermore only this one $w$ can be computed by the attacker, therefore if $w$ is odd, he can not break the encryption. $\endgroup$
    – Jan Maly
    May 31, 2016 at 11:28

2 Answers 2

5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ You are right. I got confused by the notation. The paper you mentioned was very helpful. If I am correct, $g$ is not the plaintext but the cyphertext. Otherwise the algorithm for braking RSA attained on p. 155 would be rather strange as it gets $g$ as an input. However, as described in the paper, finding a $w$ such that $g^w = 1 \mod{N}$ suffices to break the encryption because we can compute the inverse $d$ of the encryption key $e$ modulo $w$. Then $g^d \mod{N}$ is the plaintext. $\endgroup$
    – Jan Maly
    May 31, 2016 at 16:14
  • $\begingroup$ I am still a bit confused by the line above the definition of the RSA function that you cited. There it is assumed that $g$ is coprime to $\phi(N)$. It seems to me, that this is a rather strange assumption if $g$ is the cyphertext and not the public key. In the paper, this assumption is not made (It is assumed that $g$ is coprime to $N$, which seems a lot more sensible). May I assume that this assumption is there by mistake? Or am I overlooking something? $\endgroup$
    – Jan Maly
    May 31, 2016 at 16:24
  • $\begingroup$ Yes, I believe the assumptions are mistaken. $\endgroup$ May 31, 2016 at 16:40
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. I thought, I understood your solution, but now I am not so sure any more. I do understand how one can break the RSA encryption given $\lambda(N)$ or, alternatively, the order of $e$ modulo $\lambda(N)$. However I do not understand how to compute one of those two given a $w$ as above. Especially I do not understand why the order of $e$ modulo $\lambda(N)$ should divide $w$, a multiple of the order of $e$ modulo $N$. $\endgroup$
    – Jan Maly
    May 31, 2016 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.