ElGamal (Subgroup and Quadratic-Residue Leakage)

Updated 19 Sep 2026

• •

  What it is

  • •

    An ElGamal mask confined to the quadratic-residue subgroup preserves whether the encoded plaintext is a square. In Bit by Bit, that one-bit subgroup distinction is exactly the flag bit.

• •

  When to apply

  • •

    Inspect multiplicative encryption when messages can occupy different cosets of the mask’s subgroup. Fresh keys and randomness do not erase a property shared by every mask.

• •

  Symbols and assumptions

  • •

    $q$ is an odd prime; $\chi(v)=v^{(q-1)/2}\bmod q$ is 1 for nonzero squares and q−1 (meaning −1) for nonsquares. Public key $h=g^x$; shared mask $s=h^y$; ciphertext component $c_2=sM\bmod q$.

• •

  Math — step by step

  • •
    1. In the supplied parameters, $q-1=2r$ with r prime and $g^r=1$, $g\ne1$. Thus g generates the order-r square subgroup. Every $h=g^x$ and $s=g^{xy}$ is a square, so $\chi(s)=1$.
  • •
    2. The code shifts padding << (1 + bit), where padding = pow(256, e, q). As a congruence, $M\equiv2^{8e+1+b}\pmod q$. The already-reduced integer padding need not literally equal $2^{8e}$.
  • •
    3. Multiplicativity gives $\chi(c_2)=\chi(s)\chi(M)=\chi(2)^{8e+1+b}$. Here $q\equiv3\pmod8$, so 2 is a nonsquare and $\chi(2)=-1$. The even exponent 8e disappears, leaving $(-1)^{1+b}$.
  • •
    4. Therefore character −1 means b=0, and character +1 means b=1. Read ciphertexts in source order: the loop extracts least-significant bits first. Reconstruct $m=\sum_i b_i2^i$, then convert that integer back to big-endian bytes. Public h and c1 are unnecessary for this particular extraction.
• •

  Worked example

  • •

    Toy parameters $q=11,g=4,x=2,y=3,e=1$: $h=4^2\bmod11=5$, $s=5^3\bmod11=4$, padding $=256\bmod11=3$.

  • •

    If b=0: $M=3\cdot2=6$, $c_2=4\cdot6\bmod11=2$, and $2^5\bmod11=10=-1$. If b=1: $M=3\cdot4\equiv1$, $c_2=4$, and $4^5\bmod11=1$.

  • •

    For recovered bits [1,0,1] in emission order, $m=1\cdot2^0+0\cdot2^1+1\cdot2^2=5$. Reversing their interpretation would generally change the message.

• •

  Checks and pitfalls

  • •

    Check primality, nonzero ciphertexts, and the actual subgroup before applying the rule. Character 0 means a zero residue and is not either encoded case.

  • •

    This c2-only rule is specific to a square-valued mask. Proper subgroup message encoding prevents this particular message-coset leak; it does not by itself supply integrity or prove the whole implementation secure.

  • •

    Offline checks confirmed both supplied primes, q mod8=3, g^r=1 and the toy calculations. The attached text did not include output.txt, so ciphertext-to-flag recovery was not replayed.

• •

  Related

  • •

    Legendre Symbol

  • •

    Quadratic Residue

  • •

    Fermat's Little Theorem

• •

  Python

  • •

    def recover(c2_values, q):
        bits = []
        for c2 in c2_values:
            chi = pow(c2, (q - 1) // 2, q)
            if chi not in (1, q - 1):
                raise ValueError('zero or invalid residue')
            bits.append(int(chi == 1))
        value = sum(bit << i for i, bit in enumerate(bits))
        return value.to_bytes((value.bit_length() + 7) // 8, 'big')
    

◌ Explore connections in Graph view