Rating:

Connecting to the server, it requested me to give data that makes the last 32 bits of SHA-256 zero when added to the given prefix.
I created [a program](https://github.com/mikecat/ctf-writeups/blob/main/2021/20211218_hxp_CTF_2021/CRY/gipfel/get_S_mp.py) to solve this by brute-forcing.
(this program looks taking upto 30 minutes to get the answer on my PC. Fortunately the server was patient enough to wait for the answer.)

Dividing g with small values, I found that g modulo 4 is 1.

Therefore, I calculated the 4th root of 1 modulo g. One of the roots is:


4689615487177589107664782585032558388794418913529425573939737788208931564987743250881967962324438559511711351322406


Putting this value as pubB will make shared (pubB to the privA-th power modulo g) be 1 because privA is a multiple of 40, which is a multiple of 4.

Then shared**3 and shared**5 are also 1.
This means that the value of g is printed as verA and we can put the value as verB to pass the check.

Also knowing that g is the SHA-256 of password, we can obtain the value of password via hashcat.

Now it is easy to obtain the encryption key key,
which is SHA-256 of a string created by concatenating password, "\0", and shared (1).

Finally it's time to decrypt AES. The encryption is done with AES.MODE_CTR and nonce=b''.
CyberChef asked a 16-byte IV to decrypt in CTR mode. 16 bytes of zero worked as IV.

Original writeup (https://mikecat.github.io/ctf-writeups/2021/20211218_hxp_CTF_2021/CRY/gipfel/#en).