This was the 100 point crypto challenge from SharifCTF dealing with a homomorphic encryption scheme based on the idea of Universal ReEncryption (URE) (hence the name of the challenge). It’s a pretty straightforward concept that made for a fun little crypto challenge that was excellently presented by the people at SharifCTF.

The Problem

For this one we are given the following prompt:

We are also given the following valid ciphertext:

The description of the challenge is pretty specific, and it is pretty clear that they just want us to understand how to apply the idea of URE in this slightly-ElGamal looking system. Using the ciphertext values given to us we just need to find another set of ciphertext messages that decrypt to the same values. Let’s just re-encrypt the ciphertext! We can’t do the described encryption method because we don’t have the public key; however, the modulus operation over $p$ occurs during the decryption phase and we have $p$! So we can’t encrypt the ciphertext, but we can find an equivalence!

We just need to find another value that solves:

The properties of modular arithmetic shows that these will be:

Checking the page source we can see that our final answers have to be $\leq128$:

Setting $n=1$ we can solve the above equations and get our new values which are $\leq128$:

$a' =$ a1068ff62cc5edae391b948f35fe4e77cfaf33153210598af06611455a2265d0ae3e7826792a86fc52272894d1d6d539b0b6e44c721f73aa2cdbfa186b4c913a

$b' =$ c36c1aa36276dfeefaafa28596c7aee1dbe9a8da7534f37c3c8f11ddfe8fa734cbc503496c0ea870ccd95766113074aeca8a8151cffdcd20b8a039f3a6345f5a

$c' =$ fdd53f94ddd05824e143a4ec14c3d86b9885376308f11489cca44767110abf5039cfab97a4dae613e6f68b28b2e4be7414b7732869e3f40f1ec58bbd7390d9db

$d' =$ 9a50350d2f25bebe460825d68a411a96530f89226d4e1576aef4612adfa1fbb782584dc7f0fb058c21dc0199eb34a51e470a40f9911e688988e2411241c37e31

Those brings up our final flag when submitted: