Guess [crypto]
VolgaCTF 2020 Qualifier

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}