4
$\begingroup$

As a challenge, we were shown an RSA setup where we have a big $n$ (617 decimal digits), $e=4$, and asked to recover three messages. (However, the messages are padded to the same length as the key with random bytes.)

I don't have a very strong background in cryptography, and this is apparently so poor that nobody bothered to explain how you'd wreck it. For instance, I've been reading the Wikipedia article on Coppersmith's attack, and it reads:

[e=3, 17 or 65537] are chosen because they make the modular exponentiation operation faster. Also, having chosen such e, it is simpler to test whether $gcd(e, p-1)=1$ and $gcd(e, q-1)=1$ while generating and testing the primes in step 1 of the key generation.

I'm not super good at this, but given that $e$ is even, I'm pretty sure that it can't be coprime with $p-1$ or $q-1$.

How would I go around to crack it?

EDIT: as some of you have guessed, this was not RSA. Instead, the single number $p$ was a ~2048 bits prime. The crypted message was essentially $pad(m)^4 \mod p$, which could be deciphered using the modular square root twice.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Small note: usually the size of RSA (and other primitives) is represented in bits. A small calculation (basically multiplying by 3.28, or about times ten divided by 3) would indicate that you have a 2048 bit key to worry about. $\endgroup$
    – Maarten Bodewes ♦
    Mar 13, 2016 at 14:50
  • $\begingroup$ Can't you use Coppersmith's attack on 'stereotyped' messages here? Look at section 4.4 on the short-pad attack: crypto.stanford.edu/~dabo/papers/RSA-survey.pdf $\endgroup$
    – pg1989
    Mar 13, 2016 at 23:21
  • 3
    $\begingroup$ This isn't really RSA, but a variant of the Rabin cryptosystem. See e.g. this question for the difference. $\endgroup$
    – Ilmari Karonen
    Mar 13, 2016 at 23:42

1 Answer 1

Reset to default
9
$\begingroup$

Unless they did something wrong (either accidentally, or deliberately to make it easy), there is no practical way.

It's well known that, if you're able to compute the squareroot of an arbitrary number modulo a composite, you can efficiently factor that composite. And, solving $e=4$ is equivalent for solving the RSA problem twice with $e=2$.

Now, it's possible that they somehow made it feasible for you, such as:

  • Selecting a prime $N$, or one that is easy to factor

  • Selecting a tiny message (however, you did indicate that they didn't do that)

As for why we generally select $e$ relatively prime to $p-1$ and $q-1$, well, that's not actually to make things more difficult for the attacker. Instead, it's so that the legitimate decryptor (that is, the guy with the private key) can uniquely determine the original message.

After all, we have $M^4 = (N-M)^4 \bmod N$ for all messages $M$; hence if the decryptor got the value $M^e \bmod N$, he would have not inherent way to determine if $M$ or $N-M$ was the original message.

However, that doesn't help you.

Improve this answer
$\endgroup$

Your Answer

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

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