# <https://git.lain.faith/BLAHAJ/writeups/src/branch/writeups/2021/corctf/dividing_secrets># dividing\_secrets
by [haskal](https://awoo.systems)
crypto / 434 pts / 121 solves
>I won't give you the secret. But, I'll let you divide it.>>`nc crypto.be.ax 6000`
provided files: [server.py](https://git.lain.faith/BLAHAJ/writeups/src/branch/writeups/2021/corctf/dividing_secrets/server.py)
## solution
inspecting the server script... it seems to be using a 512 bit prime `p` and taking a random number`g` to the power of the secret flag message `x` mod `p`. in order to crack this you'd need to comeup with an efficient solution for the [Discrete LogProblem](https://en.wikipedia.org/wiki/Discrete_logarithm#Algorithms)
luckily, the server also lets you divide the exponent by an arbitrary input number up to 64 times(that's `512/8` for those who are paying attention, which suggests taking a character-by-characterapproach). the exploit concept is to use the division to shift `x` all the way to 8 bits, then tryto guess what those 8 bits are by trying all 256 possible values. then, once that is known, move onto the next 8 bits using the known segment and combining it with another round of 256 guesses
it looks kinda like this
```python# start by doing x >> 504# (this is the same as x / (2**504))position = 504top_bits = 0
while True:    # send off the next guess    r.recvuntil("number> ")    r.sendline(str(2**position))    h = int(r.recvline().decode())    # guess every possible character    for i in range(256):        if pow(g, (top_bits << 8) | i, p) == h:            # once it is found, move on            sys.stdout.write(chr(i))            top_bits = (top_bits << 8) | i            position -= 8            break```
running the `exploit.py` script should produce
```[+] Opening connection to crypto.be.ax on port 6000: Doneg 3163314640353309966974084350140065528835797402483351605270276213160985733919488025191658477221550585332241782718778635951464919000972247044376608291073497p 9937890065686116796205186685937536971919686769106263396090623316690565375989826956720662974087853527508968612312091794142094431426690835778526649323968253enc 5829222177042077791091257368279368382423357539393247444397252396260207162571334610710294330374985463989052071335431112395334343144642068220012344459731980corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}[*] Closed connection to crypto.be.ax port 6000Traceback (most recent call last):........  File "/usr/lib/python3.9/site-packages/pwnlib/tubes/sock.py", line 58, in recv_raw    raise EOFErrorEOFError```