Tags: rabin math

Rating:

# GolanG_Heights Writeup

### Affinity 2019 - crypto 350 - 29 solves

> Note: put flag into AFFCTF{} format

#### Observations and getting the flag

After observing the given [go script](golang_heights.go), I immediately realize the algorithm for generating pub. The flag is encrypted by [rabin cryptosytem](https://en.wikipedia.org/wiki/Rabin_cryptosystem), so factoring the public key pub leads to decryption of the [flag](flag.txt).

The algorithm of generating public key pub is ported as the following python code.

python
p = 4 * B ** 2 + 3 * B + 7351
q = 19 * B ** 2 + 18 * B + 1379
pub = p * q


Ask sage to solve the equation to find integer B.

sage
out = solve([p * q == Integer(pubkey)], B)
B = int(out[3].rhs())
p = int(p.subs(B=B))
q = int(q.subs(B=B))


Integer B is recovered, and we get the value of p and q, which is the factor of pub. Decrypt flag by applying modular sqrt algorithm and chinese remainder theorem. I get the flag.


AFFCTF{##just!c3_just!c3_y0u_sh@ll_pursu3_##_d3m@nd__p3@c3__@nd__pursu3__!t##}


exploit driver code: [solve.sage](solve.sage)

constants: [config.py](config,py)

Original problem: [golang_heights.go](golang_heights.go), [flag.txt](flag.txt)

Modular sqrt algorithm: [modular_sqrt.py](modular_sqrt.py)

Original writeup (https://github.com/pcw109550/write-up/tree/master/2019/Affinity/GolanG_Heights).