```python
def enc(a):
f = {str: str.encode, int: int.__str__}.get(type(a))
return enc(f(a)) if f else a

def H(*args):
data = b'\0'.join(map(enc, args))
return SHA256.new(data).digest()

def F(h, x):
return pow(h, x, q)

################################################################

password = random.randrange(10**6)

def go(publicB,verB):
generator = int(H(password).hex(), 16)

private_A = 40*random.randrange(2**999)
publicA = F(generator, private_A)
print(f'{publicA = :#x}')

if not 1 < publicB < q:
exit('nope')

shared = F(publicB, private_A)

verA = F(generator, shared**3)
print(f'{verA = :#x}')

if verB == F(generator, shared**5):
key = H(password, shared)
flag = "this is a test"
aes = AES.new(key, AES.MODE_CTR, nonce=b'')
encrypted = aes.encrypt(flag.encode()).hex()
print(f'flag:', encrypted)
return (publicA,verA,encrypted)
else:
print(f'nope! {shared:#x}')
return (publicA,verA,shared)
```

We can query the oracle `go` three times, but one query already succeeds.

## Observations

Seems like a DH-exchange where an additional value (`verA` and `verB`) will be compared. However, we do not even know the generator on which the exchange is based on. Therefore, we first have to get the generator in order to solve the puzzle `verB == F(generator, shared**5)`. After receiving the encrypted flag, we can just bruteforce all possible passwords because it is at max $10^6$

### Step 1) Getting the generator

We do this by setting `P_B := publicB` to `q-1`. This will lead to the following:

$shared = P{_B}^{sk_A} = (q-1)^{40 \cdot rnd} = (q-1)^{2^{20 \cdot rnd }} = 1 \mod q$ because $(q-1)^2 = q^2 - 2q + 1= 1 \mod q$

We then receive `verA` which is the generator in our case because `shared` is one. Then we just send `verA` for `verB` in order to receive the encrypted flag.

### Step 2) Bruteforce flag

```python
flags = []

import string
pable = set(bytes(string.printable.encode()))

for i in range(10**6):
key = H(i,1)
aes = AES.new(key, AES.MODE_CTR, nonce=b'')

plaintext = aes.decrypt(ciphertext)

# check if chars are printable
if set(plaintext).issubset(pable):
flags.append(plaintext)

list(filter(lambda x:b"{" in x,flags))
```

Outputs

` hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345} `

At first I was unaware of the flag format such that I tested every value for the password. This took roughly 30 seconds.