How do I attack an RSA setup where e is even? 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.
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.