Guess [crypto]

# guess

Try to guess all encrypted bits and get your reward!

## Recon

TElgamal/attack-on-pycrypto-elgamal/attack-pycrypto.py

## Solution

```from pwn import *
from Crypto.PublicKey import ElGamal
from Crypto import Random
import Crypto.Random.random

def kronecker(x,p):
q = (p-1)//2
return pow(x,q,p)

def findQNR(p):
r = Crypto.Random.random.randrange(2,p-1)
while kronecker(r,p) == 1:
r = Crypto.Random.random.randrange(2,p-1)
return r

def findQR(p):
r = Crypto.Random.random.randrange(2,p-1)
return pow(r,2,p)

conn = remote('guess.q.2020.volgactf.ru', 7777)

res = conn.recv()
res = res.decode()
res = res.split(' = ')[-1].replace('(', '').replace(')', '').replace('\r\n', '').split(', ')
y = int(res[0])
p = int(res[1])

for i in range(1000):
res = conn.recv()
res = res.decode().replace('(', '').replace(')', '').replace('L', '').split(', ')
c = (int(res[0]), int(res[1]))
if kronecker(y, p) == 1 or kronecker(c[0], p) == 1:
if kronecker(c[1], p) == 1:
output = b'1'
else:
output = b'0'
else:
if kronecker(c[1], p) == 1:
output = b'0'
else:
output = b'1'
print(f'[{i}] Sending {output.decode()}')
conn.sendline(output)

try:
while True:
print(conn.recv())
except:
pass

conn.close()
```

## Flag

`VolgaCTF{B3_c4r3ful_with_4lg0rithm5_impl3m3nt4ti0n5}`