VolgaCTF2020Qualifier Crypto Guess writeup

#!/usr/bin/python
# -*- coding: utf-8 -*-
from __future__ import print_function
from Crypto.PublicKey import ElGamal
from Crypto import Random
from flag_file import flag
import Crypto.Random.random
import time
import sys


"""
    Communication utils
"""

def read_message():
    return sys.stdin.readline()


def send_message(message):
    sys.stdout.write('{0}\r\n'.format(message))
    sys.stdout.flush()


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


"""
    Algebra
"""

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)


"""
    Main
"""

if __name__ == '__main__':
    try:
        while True:
            key = ElGamal.generate(512, Random.new().read)
            runs = 1000
            successful_tries = 0

            send_message('(y, p) = ({0}, {1})'.format(key.y, key.p))

            for i in xrange(runs):
                plaintexts = dict()
                plaintexts[0] = findQNR(key.p)
                plaintexts[1] = findQR(key.p)

                challenge_bit = Crypto.Random.random.randrange(0,2)
                eprint('[{0}][INFO] Bit {1} was generated.'.format(time.strftime("%Y-%m-%d. %H:%M:%S"), challenge_bit))
                r = Crypto.Random.random.randrange(1,key.p-1) 
                challenge = key.encrypt(plaintexts[challenge_bit], r)

                # Send challenge
                send_message(challenge)

                # Receive challenge_bit
                received_bit = read_message()
                eprint('[{0}][INFO] Bit {1} was received.'.format(time.strftime("%Y-%m-%d. %H:%M:%S"), received_bit))
                if int(received_bit) == challenge_bit:
                    successful_tries += 1
                    eprint(successful_tries)
                    
            if successful_tries == runs:
                send_message(flag)

    except Exception as ex:
        send_message('Something must have gone very, very wrong...')
        eprint('[{0}][ERROR] {1}'.format(time.strftime("%Y-%m-%d. %H:%M:%S"), ex))

    finally:
        pass

obj.x=number.getRandomRange(2, obj.p-1, randfunc)

from pwn import *


def solve():
    pattern_y_p = re.compile("\(y, p\) = \(([0-9]+), ([0-9]+)\)")
    pattern_y1_y2 = re.compile("\(([0-9]+)L, ([0-9]+)L\)")

    r = remote("guess.q.2020.volgactf.ru", 7777)
    # r = process(["python", "server.py"])
    match = pattern_y_p.search(r.recvline().strip())
    y, p = int(match.group(1)), int(match.group(2))
    for i in range(1000):
        print(i)
        recv = r.recvline()
        # print(recv)
        match = pattern_y1_y2.search(recv.strip())
        y1, y2 = int(match.group(1)), int(match.group(2))
        if pow(y2, (p - 1) / 2, p) == 1:
            r.sendline("1")
        else:
            r.sendline("0")

    print(r.recvline())
    print(r.recvline())
    print(r.recvline())

from pwn import remote

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

def qr(x, p):
    return ec(x, p) == 1

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

y, p = map(int, conn.recvline().split('= (')[1][:-3].split(', '))

for i in range(1000):
    c1, c2 = eval(conn.recvline())

    b = ''
    if qr(y, p):
        if qr(c2, p):
            b = '1'
        else:
            b = '0'
    else:
        if qr(c1, p):
            if qr(c2, p):
                b = '1'
            else:
                b = '0'
        else:
            if qr(c2, p):
                b = '0'
            else:
                b = '1'
    conn.sendline(b)
    print('challenge', i)
print(conn.recvline())

obj.g = pow(number.getRandomRange(2, obj.p, randfunc), 2, obj.p)

# Choose a square residue; it will generate a cyclic group of order q.
obj.g = pow(number.getRandomRange(2, obj.p, randfunc), 2, obj.p)

while 1:
    # Choose a square residue; it will generate a cyclic group of order q.
    obj.g = pow(number.getRandomRange(2, obj.p, randfunc), 2, obj.p)

    # We must avoid g=2 because of Bleichenbacher's attack described
    # in "Generating ElGamal signatures without knowning the secret key",
    # 1996
    if obj.g in (1, 2):
        continue

    # Discard g if it divides p-1 because of the attack described
    # in Note 11.67 (iii) in HAC
    if (obj.p - 1) % obj.g == 0:
        continue

    # g^{-1} must not divide p-1 because of Khadir's attack
    # described in "Conditions of the generator for forging ElGamal
    # signature", 2011
    ginv = number.inverse(obj.g, obj.p)
    if (obj.p - 1) % ginv == 0:
        continue

    # Found
    break