**Tags:** modular-arithmetic crypto

Rating:

# dirty laundry Writeup

### zer0pts CTF 2020 - crypto 636

> Do you wanna air my dirty laundry?

#### Observations

[Paillier cryptosystem](https://en.wikipedia.org/wiki/Paillier_cryptosystem) with [Shamir's secret sharing](https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing) is given to me. The algorithms for the system are summarized below.

0. Let `secret = bytes_to_long(flag)`

1. 1024 bit strong prime `PRIME` is chosen.

2. Lower 256 bit of `PRIME` will be the initial `seed` of prng(`PRNG256`) having output size of 256 bits.

3. Polynomial `f(x) = secret + a * x + b * x ** 2 (mod PRIME)` is generated. `a` and `b` are randomly choosn in `GF(PRIME)`.

4. Public key `n`, `g` and ciphertext `c` is generated and exposed. Iterate below five times, by changing `x in range(1, 6)`.

- `noise`, `key`, and `r` is produced from `PRNG256`, having size of 256 bits.

- `n = next_prime(PRIME + noise) * getStrongPrime(512)`, having size of 1024 + 512 = 1536 bits.

- `g = (1 + key * n) % n ** 2`, having max size of 256 + 1536 = 1792

- `c = pow(g, f(x) + noise, n ** 2) * pow(r, n, n ** 2) % n ** 2`

#### Gaining information gradually by mathematics

1. Recover `key` values

- Observe the generation method for `g = (1 + key * n) % n ** 2`. There is no point of modulo division of `n ** 2` because `1 + key * n` has at most 1792 bit length, but `n ** 2` has length of 1536 * 2 = 3072 bits.

- Therefore, by knowing `g` and `n`, I can calculate `key = (g - 1) // n`. Sanity check performed by checking bitlength of `key` is about 256 bits.

2. Break `PRNG256` by z3.

- `key` is the output of `PRNG256`. Supplying constraints to z3, I could recover initial `seed`, which is 256 LSBs of `PRIME`.

- Sanity check performed, by comparing next `key` values with outputs generated by `PRNG256` initialized by recovered `seed`.

3. Reduce solving systems of equations over `GF(PRIME)`.

- `c = pow(g, f(x) + noise, n ** 2) * pow(r, n, n ** 2) % n ** 2`

- I now know `r` and `noise` because I broke `PRNG256`.

- Let `c_ = pow(g, f(x) + noise, n ** 2) = c * inverse_mod(pow(r, n, n ** 2), n ** 2) % n ** 2`

- `c_ = pow(g, f(x) + noise, n ** 2) = (1 + key * n) ** (f(x) + noise) % n ** 2`

- Perform binomial expansion. Starting from third term will be divided by `n ** 2`, so simplify the equation.

- `c_ = 1 + key * n * (secret + a * x + b * x ** 2 + noise) % n ** 2`

- `noise` is known, so simplify again.

- Let `c__ = key * n * (secret + a * x + b * x ** 2) = (c_ - 1) * inverse_mod(key * n * noise, n ** 2) % n ** 2`

- Sanity check of `c__`; it must have max bit length of 256 + 1536 + 1024 = 2816.

- Luckily, `c__` was dividable by each `n`! Now we do not need to think about operation over `GF`.

4. Solve plain systems of equations.

- Let `c__[i]` be the result per each `x in range(1, 6)`

- `c__[0] = secret + a * 1 + b * 1 ** 2 = secret + a + b`

- `c__[1] = secret + a * 2 + b * 2 ** 2 = secret + 2 * a + 4 * b`

- `c__[2] = secret + a * 3 + b * 3 ** 2 = secret + 3 * a + 9 * b`

- I only need three equations because there are three unknown variables, `secret`, `a`, `b`.

- `secret = c__[0] * 3 + c__[1] * -3 + c__[2] * 1`

- `flag = l2b(secret)`

I strongly think this solution is unintended, because 256 LSBs of `PRIME` was never used. The system may be broken by using LLL. After all these tedious computations, I finally get the flag:

```

zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}

```

Exploit code: [solve.py](solve.py)

Run with `python3 -O solve.py`

Original writeup (https://github.com/pcw109550/write-up/tree/master/2020/zer0pts/dirty_laundry).