# OK - zer0pts CTF 2022
###### tags: `zer0pts CTF 2022`

Writeups: https://hackmd.io/@ptr-yudai/rJgjygUM9

## overview

The program implements Oblivisous Transfer by RSA. We can get either $K$ or $C$. Our purpose is to get $K \oplus C$.

## solution

### step1

By sending $v$ such that $v - x_1 \equiv -(v - x_2) \mod n$, the $k_1 \equiv -k_2 \mod n$ stands.

Because $k_1 \equiv (v - x_1)^d \mod n$ and $k_2 \equiv (v - x_2)^d \equiv (-(v - x_1))^d \equiv -(v - x_1)^d \mod n$. ($d$ is odd value)

Thus, $c_1 + c_2 \equiv K + C \mod n$ where $c_1 \equiv k_1 + K \mod n$, $c_2 \equiv k_2 + C \mod n$ stands.

Additionaly, the LSB of $c_1 + c_2$ is always fixed because $K \oplus C$ is consistent. Hence we can assume the parity of $c_1 + c_2$ and find $K + C$ without modulo under the assumption. If the parity of $K + C \mod n$ is different from our assumption, we can get $K + C$ by adding $n$ to $|K + C \mod n|$. Otherwise $|K + C \mod n| = K + C$. Because $n$ is odd value.

Now we have $K + C \mod n$. Can we determine $K \oplus C$ uniquely?

Appearently no. But for now, we know $K$ and $C$ are different in every connection while $K \oplus C$ is consistent. So considering about collecting some cases of $(K, C)$ pair.

For now, the problem is turned into to find $X = K_i \oplus C_i$ from some $Y_i = K_i + C_i$.

### step2

Therefore, if the following problem is solved, <code>secret</code> has been recovered.

> **Statement:**
> Generate an integer sequence $B_i=A_i + (m \oplus A_i)$ from a random integer $m$ of $N$ bits and an integer sequence $A$ of random $N$ bits. Recover $m$ from the integer sequence $B$.
> **Constraints:**
> - $N=1024$
> - $|A|=20$

First, let us make an observation about the generated number $A_i + (m \oplus A_i)$. From the facts about addition, the following formula transformation holds.

$$
\begin{align}
A_i + (m \oplus A_i) &= (A_i \oplus m \oplus A_i)+2\cdot (A_i \& (m \oplus A_i)) \\
&= m+2\cdot (A_i \& (m \oplus A_i)) \tag{1}
\end{align}
$$

Here, the XOR in the $A_i \& (m \oplus A_i)$ part can be taken as inverting the bit extracted by &. So it should be the same if all the bits are inverted first and then extracted. Let us denote the bit inversion of $x$ as $\overline{x}$, then the following holds.

$$
\begin{align}
(1) &= m+2\cdot (A_i \& \overline{m})\\
&= m+\overline{m}+(A_i \& \overline{m})+( (A_i \& \overline{m})-\overline{m}) \\
&= \overline{0}+(A_i \& \overline{m})+( (A_i \& \overline{m})-( (A_i \& \overline{m})+(\overline{A_i} \& \overline{m}) ) ) \\
&= \overline{0}+(A_i \& \overline{m})-(\overline{A_i} \& \overline{m}) \tag{2}
\end{align}
$$

The equation transformation regarding bit inversion is a bit cumbersome, but it is no problem to think of it as the one's complement in a sufficiently large finite number of bits. In this case, since $N=1024$ bits, we can write the following using $C=2^\rm{N+1}-1$.

\begin{align}
(2) &= C+(A_i \& (C-m))-(\overline{A_i} \& (C-m) )
\end{align}

This equation can be interpreted as a script like the following.

C = 2 ** (N + 1) - 1
B_i = C
for i in range(N):
  if not (C-m & (1 << i)): continue
  res += (1 << i) * choice([-1, 1])

Now consider the probability that the most significant bit of $|B_i-C|$ is equal to the most significant bit of $C-m$. It turns out that this is 1 if $C-m$ and the most significant bit are equal, and 1/2 if they are not ((symmetry makes it clear)). Since the most significant bit is always smaller when they are not equal, we can find the most significant bit of $C-m$ from the sequence $B$ with probability more than $1-2^{-|B|}$ by taking the largest most significant bit. Next, subtract the most significant bit from $|B_i-C|$ and take its absolute value. Then we have the same problem for the second bit from the top.

Thus, we found that by repeating this process, we can find $m$ with probability greater than $(1-2^{-|B|})^{N}$. The script will be as follows.

def solve(bs):
    BIT = 1024
    C = 2 ** (BIT + 1) - 1
    bs = [abs(b - C) for b in bs]

    res = C
    while not all([b == 0 for b in bs]):
        msb = 1 << (max(bs).bit_length() - 1)
        res -= msb
        bs = [abs(b - msb) for b in bs]
    if any([b != 0 for b in bs]): return None
    return res