CyberSecurityRumble | PADY McPADaFACE

#!/usr/bin/env python3
from random import SystemRandom
from config import p,q,e,flag

print("="*50)
print(open(__file__).read())
print("~"*50)

random = SystemRandom()

flag = int.from_bytes(flag,"big")

n = p*q
assert(p<q<2*p)

print(f"{n=}")
print(f"{e=}")

def pad(m):
    assert(m<2**128)
    r = random.randrange(2**(p.bit_length()-65))
    return m+r**2

def encrypt(m):
    return pow(pad(m), e, n)

for i in bin(flag)[2:]:
    print(encrypt(int(i)))

をRSA暗号化している。のjacobi記号を見ることによってがquadratic residueかどうかがわかる。厳密にはわからなくて、jacobi記号はがquadratic residueなら必ず1を返すというだけで、がnon quadratic residueのときにも1を返す可能性がある。そこで平文が固定されていることを利用して、インスタンスを何個か手に入れて、絶対に-1を返さないものはがquadratic resude、つまりとしてやる。逆に、一つでも-1を返すものはがわかる

from ptrlib import Socket

# https://rosettacode.org/wiki/Jacobi_symbol#Python
def jacobi(a, n):
    assert n > 0
    assert n % 2 == 1

    a = a % n
    result = 1
    while a != 0:
        while a % 2 == 0:
            a = a//2
            n_mod_8 = n % 8
            if n_mod_8 in (3, 5):
                result = -result
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            result = -result
        a = a % n

    if n == 1:
        return result
    else:
        return 0


def collect(numofbits=None):
    sock = Socket("localhost", 9999)
    sock.recvuntil("~~~~~~~~\n")
    n = int(sock.recvlineafter("n="))
    e = int(sock.recvlineafter("e="))

    cs = []
    while True:
        if numofbits:
            if len(cs) >= numofbits:
                break
        else:
            print(len(cs))
        try:
            c = int(sock.recvline(timeout=1))
            cs.append(c)
        except (TimeoutError, KeyboardInterrupt):
            break
    return n, e, cs

ns = []
css = []
for i in range(10):
    if i == 0:
        n, _, cs = collect()
    else:
        n, _, cs = collect(len(css[0]))
    ns.append(n)
    css.append(cs)

bits = ""
for i in range(len(css[0])):
    is_one = False
    for j in range(len(ns)):
        if jacobi(css[j][i], ns[j]) == -1:
            is_one = True
            break

    if is_one:
        bits += "1"
    else:
        bits += "0"

m = int(bits, 2)
print(bytes.fromhex(hex(m)[2:]))