Bit by Bit

I solve this challenge with some misinterpretations, but in the end I got the correct overall theme: Legendre Symbols. I guess I got lucky with the local testing and derive the correct relation.

The challenge, as suggested by the category, is about the ElGamal construction. More information can be found at this Wikipedia link, or any textbook in cryptography should cover this.

The very first observation is that each iteration of the while loop is operating 1 bit of the flag at a time, starting from the last bit of the flag.

We are given the public key $h=g^x$$h = g ^ x$, the two ciphertexts $c_1=g^y$$c_1 = g ^ y$ and $c_2=m\ast g^{xy}$$c_2 = m * g ^ {xy}$. However, the message $m$$m$ encrypted is the result of the padding with a bit of the flag. The first observation is that the padding is of the form ${256}^r=2^{8r}$$256 ^ r = 2 ^ {8r}$, where $r$$r$ is some randomly chosen value. The message me generated is of the form me = padding << 1 + m % 2. What's interesting (and what I misinterpreted after solving the challenge) is that << takes precedence before the addition. In other words, me can be written as me = padding << (1 + m % 2).

Hence, if m % 2 == 0, padding is equal to $2^{8r+1}$$2 ^ {8r + 1}$, and if m % 2 == 1, padding is equal to $2^{8r+2}$$2 ^{8r + 2}$. We can think of using the Legendre symbol here, as the Legendre symbol when m % 2 == 1 is 1 (the padding is a quadratic residue) and not 1 when m % 2 == 0 (the padding is not a quadratic residue). Luckily, from the parameters given, $g$$g$ is a quadratic residue mod $q$$q$, by calculating the Legendre symbol.

Hence, if the bit of the flag is 1, $c_2=m\ast g^{xy}$$c_2 = m * g ^ {xy}$ is a quadratic residue, and if the bit of the flag is 0, $c_2$$c_2$ is not a quadratic residue. With this, we should be able to recover each bit of the flag.

Python Implementation:

xxxxxxxxxx
from Crypto.Util.number import long_to_bytes

q = 117477667918738952579183719876352811442282667176975299658506388983916794266542270944999203435163206062215810775822922421123910464455461286519153688505926472313006014806485076205663018026742480181999336912300022514436004673587192018846621666145334296696433207116469994110066128730623149834083870252895489152123
g = 104831378861792918406603185872102963672377675787070244288476520132867186367073243128721932355048896327567834691503031058630891431160772435946803430038048387919820523845278192892527138537973452950296897433212693740878617106403233353998322359462259883977147097970627584785653515124418036488904398507208057206926

def legendre_symbol(a, p):
    return pow(a, (p - 1) // 2, p)

assert(legendre_symbol(g, q) == 1)
f = open('output.txt')

lines = f.readlines()

flag = ""

for i in range(0, len(lines), 2):
    public_key = lines[i][1:-2]
    ciphertexts = lines[i + 1][1:-2]

    public_key = int(public_key.split("=")[1], 16)
    c1, c2 = ciphertexts.split(", ")
    c1 = int(c1.split("=")[1], 16) 
    c2 = int(c2.split("=")[1], 16)

    if legendre_symbol(c2, q) == 1: 
        flag += "1"
    else:
        flag += "0"

flag = flag[::-1]
print(long_to_bytes(int(flag, 2)))

This challenge may be extended (have not really verified this) even when $g$$g$ is not a quadratic residue. We can figure out whether $g^{xy}$$g ^ {xy}$ is a quadratic residue or not by observing the Legendre symbol of $h=g^x$$h = g ^ x$ and $c_1=g^y$$c_1 = g ^ y$. If any $h$$h$ and $c_1$$c_1$ is not a quadratic residue, then $g^{xy}$$g ^ {xy}$ is not a quadratic residue ($x,y$$x, y$ are both odd if that happens). If that is the case, then $c_1\ast g^{-1}$$c_1 * g ^ {-1}$ will be a quadratic residue (using the same reasoning above) if m % 2 == 0, and not a quadratic residue otherwise.