Update 2019-09-10: Thanks to acut3 for pointing out that the operator precedence is different than I initially assumed. The write-up is changed accordingly.

We are given the following program and its output, i.e., the encrypted flag.

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
from Crypto.Util import number
import random
from secret import flag
N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
m = number.bytes_to_long(flag)
with open('flag.enc', 'w') as f:
    while m:
        padding = random.randint(0, 2**1000) ** 2
        message = padding << 1 + m % 2
        cipher = pow(message, e, N)
        f.write(hex(cipher)+'\n')
        m /= 2

We see that the flag is encrypted bit by bit. To encrypt a bit of the flag, the program adds it to a large random integer that is squared (padding) and multiplied by $2^{1 + \text{flag}[i]}$ (padding << 1 + m % 2). So the plaintext is $\text{pt}[i] = 2^{1 + \text{flag}[i]} \cdot r^2$. Observe that if flag[i] == 1, then $\text{pt}[i] = (2r)^2 \pmod{N}$ is a quadratic residue. On the other hand, if flag[i] == 0, then $\text{pt}[i] = 2r^2$ and so $2^{-1} \cdot \text{pt}[i] = r^2 \pmod{N}$ is a quadratic residue.

The Legendre symbol $\left(\frac{x}{p}\right)$ indicates whether a number $x$ is a quadratic residue modulo a prime $p$. If the Legendre symbol is $1$ then $x$ is a quadratic residue, if $-1$ it is a quadratic non-residue.

The Jacobi symbol is a generalization of the Legendre symbol, defined for a composite number $N = pq$ as $\left(\frac{x}{N}\right) = \left(\frac{x}{p}\right)\left(\frac{x}{q}\right)$. If the Jacobi symbol is $-1$, we can be sure that $x$ is a quadratic non-residue modulo $N$.1

We are given the values $\text{ct}[i] = \bigl(2^{1 + \text{flag}[i]} \cdot r^2\bigr)^e \pmod{N}$ and so we can compute the Jacobi symbol $$ \begin{aligned} \left(\frac{(2^{-1})^e \cdot \text{ct}[i]}{N}\right) &= \left(\frac{(2^{-1} \cdot 2^{1 + \text{flag}[i]} \cdot r^2)^e}{N}\right) \cr &= \left(\frac{2^{\text{flag}[i]} \cdot r^2}{N}\right)^e \cr &= \left(\frac{2^{\text{flag}[i]} \cdot r^2}{N}\right) \qquad\text{\small(since $e$ is odd)}\cr &= \left(\frac{2^{\text{flag}[i]}}{N}\right) \left(\frac{r^2}{N}\right) \cr &= \left(\frac{2^{\text{flag}[i]}}{N}\right). \end{aligned} $$ Since $N = 5 \pmod{8}$, we have that $\left(\frac{2}{N}\right) = -1$. We conclude that if the computed Jacobi symbol equals $-1$, $\text{flag}[i] = 1$, and if it equals $1$, $\text{flag}[i] = 0$ since $\left(\frac{1}{N}\right) = 1$.

#!/usr/bin/env python3
import gmpy2

N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
two_inv = pow(gmpy2.invert(2, N), e, N)

with open('flag.enc', 'r') as f:
    s, bits = '', 0
    for ct in f:
        ct = int(ct.strip().rstrip('L'), 16)
        jacobi = gmpy2.jacobi(two_inv * ct, N)
        if jacobi == 0:
            import math
            raise ValueError('found a factor of N:', math.gcd(two_inv * ct, N)) 
        elif jacobi == -1:
            s = '1' + s
        else:
            s = '0' + s
        bits += 1
    s = '0' * (-bits % 8) + s

print(int(s, 2).to_bytes(len(s) // 8, 'big').decode())

Running the program gives us the flag N1CTF{You_can_leak_the_jacobi_symbol_from_RSA}.

  1. Sadly, we do not have a similar property for when the Jacobi symbol is $1$, but we know that if $x$ is a quadratic residue and $\gcd(x, N) = 1$, then $\left(\frac{x}{N}\right) = 1$. If the Jacobi symbol is $0$, then $x$ contains a factor of $N$. ↩︎