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.
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 occurs during the decryption phase and we have ! 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 :
Setting we can solve the above equations and get our new values which are :
Those brings up our final flag when submitted: