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.



Breaking the RSA encryption based on a $(e,N)$ given an integer $w \neq 0$ such that $e^w = 1 \mod(N)$?
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](http://www.karlin.mff.cuni.cz/~krajicek/j-crypto.ps), [journal doi](http://dx.doi.org/10.1006/inco.1997.2674)


