I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated.
Suppose that the RSA modulus of $n := 42313421$ used with an encryption exponent of $2015$ produces the pair $(27285537, 25251845)$ of ciphertexts. Use the fact that
$26437093^2 ≡ 1 \pmod n$
to find the original plaintext message. Show your work.
I don't see how fact stated helps with the problem.
Consider two numbers $a$ and $b$ that square to the same value modulo $n$ and don't just differ by the sign.
$$a^2 \equiv b^2 \pmod n2$$ $$(a-b)(a+b) \equiv 0 \pmod n$$
Neither of the factors on the left is 0 (or equivalently a multiple of $n$), thus each of them must contain one of the prime factors of $n$.
Thus you can use $\operatorname{GCD}(a-b, n)$ and $\operatorname{GCD}(a+b, n)$ to recover factors of $n$. If $n$ is the product of two primes, you thus factored $n$. Once you factored $n$, follow the standard RSA key generation procedure to obtain the decryption exponent $d$.
In your example $a=\pm 1$ and $b=\pm 26437093$.
This attack is important in the context of the Rabin cryptosystem, which works like RSA, except it uses the public exponent $2$. So the decrypter/signer has to make sure that they never produce information about different roots for a given square, otherwise an attacker can recover their public key.
