## Challenge description
Anna Julia is a childhood friend of Laura. In hiding, they spent years studying hacking and technology together. In order to communicate in secret, Julia developed a programming language and invented an encryption scheme. Now Laura needs to know if this scheme really protects them from government spies.

Server: nc oh-anna-julia.pwn2win.party 1337

Challenge code: [chall.jl](chall.jl)

## Solution
First we notice that for the challenge to work, we need to generate 4-10 keys. Keys are made of a pair of public and secret key. Secret keys are arrays of random elements under modulus q. One key per character in flag. Then the public key is generated by putting 2 to the power of the product of secret keys, modulo q.
```
for i in 1:len
push!(sk, rand(1:data.q))
pk = powermod(data.g, sk[i], data.q) * pk % data.q
end
```
Then we need to send the secret, which is a byte array of the same length as the flag. It is used for to xor it with the flag during encryption.

Then we can request the server to "Show data". From that we get the modulus q.

Now we examine how the encryption works. We notice that when we call "Encrypt flag", only one character of our choosing gets encrypted and sent to us.
First c and d get set:
```
for ki in 1:2:(length(data.pks)-1) #
c = powermod(data.pks[ki], data.sks[ki + 1][i], data.q) * c % data.q
d = powermod(data.pks[ki + 1], data.sks[ki][i], data.q) * d % data.q
end
```
Then one character of the flag is encrypted:
```
r = rand(1:data.q)
s = data.secret[i] ⊻ Int(flag[i])
c = powermod(data.g, s + r, data.q) * c % data.q
d = powermod(data.g, r, data.q) * d % data.q
```
We notice that if we invert d and multiply it with c, we get:

r = c * d^-1 = 2^s * c * d^-1 (mod q)

If we change the secret, the value of s will change, thus we can use 2 lookups to get:

r1 * r2^-1 = 2^{s1 - s2}

By changing the secret to flip 1 bit of the flag character, and a baseline that doesnt flip anything, we can get the flag character bit by bit with 9 different secrets. Then we just loop over to get the entire flag.

Solution: [solv.py](solv.py)
## Flag
CTF-BR{Qu3m_te_v3_pass4r_4ssim_p0r_Mim.}