MORPHING TIME
The all revealing Oracle may be revealing a little too much...
From the script chal.py
, we can see that the program uses the ElGamal encryption scheme, which is a public-key cipher. The decryption operation involves computing an inverse modulo the prime number p
. The decrypt function takes as input two numbers c1
and c2
and returns a message m
. The interesting behavior here is that you can provide the oracle with an encryption of a message and the oracle will return the decrypted message multiplied by the flag.
The goal here is to use this property to your advantage to recover the flag. You can do this by sending an encryption of 1
to the oracle, which will return the decrypted flag itself.
Let's walk through the steps of how to calculate the encrypted 1
:
Recall the ElGamal encryption process: to encrypt a message
m
, we choose a randomk
from[2, p-1]
, computec1 = g^k mod p
,c2 = m * A^k mod p
, and the ciphertext is(c1, c2)
.To encrypt
1
, we choosek = 1
to simplify the computation:c1_ = g^1 mod p = g
,c2_ = 1 * A^1 mod p = A
.You can then submit
(c1_, c2_)
to the oracle, which is(g, A)
, to get the flag.
After we obtained the integer m
, we convert it into bytes and then decode it as a string to obtain the flag. You might need to handle padding or non-ASCII bytes in the decoded string, but those can be usually resolved by ignoring non-ASCII characters or removing the padding.
Here is an example of the final script used to retrieve the flag:
Flag:
uiuctf{h0m0m0rpi5sms_ar3_v3ry_fun!!11!!11!!}
Last updated