# [zer0pts CTF 2020] dirty laundry
###### tags: `zer0pts CTF` `crypto`

## Challenge Summary
The challenge has the following code:

#!/usr/bin/sage
from sage.all import *
from Crypto.Util.number import getStrongPrime, bytes_to_long

from secret import flag

class PRNG256(object):
    def __init__(self, seed):
        self.mask = (1 << 256) - 1
        self.seed = seed & self.mask

    def _pick(self):
        b = ((self.seed>>0)^(self.seed>>2)^(self.seed>>5)^(self.seed>>10)^1)&1
        self.seed = ((self.seed>>1)|(b<<255)) & self.mask
        return b

    def rand(self):
        x = 0
        for i in range(256):
            x = (x << 1) | self._pick()
        return x

PRIME = getStrongPrime(1024)
prng = PRNG256(PRIME)

def paillier_enc(m, p, noise):
    p = next_prime(p + noise)
    q = getStrongPrime(512)
    n = p * q
    g = (1 + prng.rand() * n) % n**2
    c = pow(g, m, n**2) * pow(prng.rand(), n, n**2) % n**2
    return n, g, c

def make_shares(secret, k, shares, prime=PRIME):
    PR, x = PolynomialRing(GF(prime), name='x').objgen()
    f = PR([secret] + [ZZ.random_element(prime) for _ in range(k-1)])
    xy = []
    pubkey = []
    for x in range(1, shares+1):
        noise = prng.rand()
        n, g, y = paillier_enc(f(x) + noise, prime, noise)
        pubkey.append([n, g])
        xy.append([x, y])
    return pubkey, xy

secret = bytes_to_long(flag)
pubkey, shares = make_shares(secret, 3, 5)

print("[+] len(flag):", len(flag))
print("[+] pubkey:", pubkey)
print("[+] shares:", shares)

The challenge is the secret sharing scheme with the paillier encryption. We need to get the PRIME and pure $f(x)$ velues to solve this.

## How to solve
First, we crack the paillier encryption, because it has wierd modulis.
### factoring $n_i$
The paillier encryption has wierd modulis.
$$
n_i = next\_prime(PRIME + noise_i) q_i
$$
PRIME is 1024-bit, each noise is 256-bit, and $q$ is 526-bit. If we define $p_i \approx PRIME + noise_i$, we can say that $n_i = (PRIME + noise_i) q_i$. Since
$$
\begin{cases}
n_1 = (PRIME + noise_1) q_1 \\
n_2 = (PRIME + noise_2) q_2
\end{cases}
$$
as a consequence, $q_1 n_2 - q_2 n_1 = q_1 q_2 noise_2 - q_1 q_2 noise_1$
(left-hand side is big compared to right-hand side)
We can apply LLL.

Consider the following lattice:
\begin{pmatrix}
2^{768} & n_2 & n_3 & n_4 & n_5 \\
0 & -n_1 & 0 & 0 & 0\\
0 & 0 & -n_1 & 0 & 0\\
0 & 0 & 0 & -n_1 & 0\\
0 & 0 & 0 & 0 & -n_1
\end{pmatrix}
As a result, the vector in the lattice is equal to $(2^{278}q_1, v_2, v_3, v_4, v_5)$ where $v_i = (noise_i - noise_1) q_1 q_i$. We can get $q_1$ by using LLL.

Therefore, we can calculate $q_2 \sim q_5$($q_i = gcd(q_1, (noise_i - noise_1)q_1 q_i)$).

### get noise
By the public key of the paillier encryption,
$$g^{\lambda} = 1 + k\lambda n$$
$g, \lambda, n$ are known values so we can get $k$. Since we were able to find the value of prng, we could extract noise before it was used in paillier (note the order)
### get flag
Now, we have noise, so we can calculate pure $f(x)$ and the correct $PRIME$. Finally, we can the flag by using lagrange interpolation.

Script:

from sage.all import *
from Crypto.Util.number import inverse, long_to_bytes
from re import compile

with open("./../distfiles/output.txt") as f:
    output = f.read()

pubkey = eval(compile(r"pubkey: (.+)\n").findall(output)[0])
shares = eval(compile(r"shares: (.+)\n").findall(output)[0])

ns = []
gs = []
for n, g in pubkey:
    ns.append(n)
    gs.append(g)

# factoring
print("[+] n bits:", [n.bit_length() for n in ns])
m = matrix(ZZ, 5, 5)
m[0, 0] = 2**768
for i in range(1, m.dimensions()[0]):
    m[0, i] = ns[i]
    m[i, i] = -ns[0]
print("[+] matrix")
for i in range(m.dimensions()[0]):
    print(i, [int(x).bit_length() for x in m[i]])

ml = m.LLL()
print("[+] LLL done")
print("[+] matrix")
for i in range(ml.dimensions()[0]):
    print(i, [int(x).bit_length() for x in ml[i]])

# decrypt and get samples of prng
def dec(c, p, q, g):
    n = int(p) * int(q)
    l = int(lcm(p-1, q-1))
    m = ((pow(c, l, n**2)-1) // n) * inverse((pow(g, l, n**2)-1) // n, n)
    k = ((pow(g, l, n**2) - 1) // n) * inverse(l, n)
    return m % n, k % n

q0 = gcd(abs(ml[0][0]), ns[0])
p0 = ns[0] // q0

qs = [q0]
ps = [p0]
res = dec(shares[0][1], p0, q0, gs[0])
ms = [res[0]]
samples = [res[1]]
for i in range(1, 5):
    qi = gcd(abs(ml[0][i])//q0, ns[i])
    pi = ns[i] // qi
    mi, ki = dec(shares[i][1], pi, qi, gs[i])
    qs.append(qi)
    ps.append(pi)
    ms.append(mi)
    samples.append(ki)

# find noises
def bit_reverse(x):
    y = 0
    for i in range(256):
        y = (y << 1) | ((x >> i) & 1)
    return y

s = bit_reverse(samples[-1])
noises = []
idx = 3
for j in range(13):
    x = 0
    for i in range(256):
        msb = s >> 255
        s <<= 1
        lsb = (msb^(s>>0)^(s>>2)^(s>>5)^(s>>10)^1)&1
        s = (s|lsb) & ((1<<256)-1)
        x = (x << 1) | lsb
    noise = bit_reverse(x)
    if j % 3 == 0:
        noises.append(noise)
    elif j % 3 == 2:
        assert noise == samples[idx]
        idx -= 1
noises.reverse()
print("[+] found all noises")

xy = []
for i in range(5):
    xy.append((i+1, ms[i] - noises[i]))

# find PRIME
prev = previous_prime(ps[0])
for x in range(prev, ps[0]):
    prime = x - noises[0]
    if is_prime(prime):
        R = PolynomialRing(GF(prime), name='x')
        f = R.lagrange_polynomial(xy)
        print("[+] flag:", long_to_bytes(f(0)))