DEFCON CTF 2020 Writeup

coppersmith.sage

import nclib
import base64
import rsa
from ctypes import CDLL


nc = nclib.Netcat(('coooppersmith.challenges.ooo', 5000), verbose=True)

nc.recv_until(b':')
nc.write(b'0' * 105 + b"1" + b"0" * 14 + b"\n")
nc.recv_until(b"Your public key:\n")
rsa_key = nc.recv_until(b"-----END RSA PUBLIC KEY-----\n")
rsa_key = rsa.PublicKey.load_pkcs1(rsa_key)
print(rsa_key)
libc = CDLL("libc.so.6")
libc.srand(libc.time(None))
x = libc.rand()
y = libc.rand()
nc.write(str(x+y).encode('utf-8') + b"\n")
nc.recv_until(b'Your flag message:\n')
flag_message = nc.recv_until(b'\n')

n = rsa_key.n
print(n)
p = None
for j in range(64, 192):
    for i in range(65536):
        if (n - 1) % ((2 ** j) + i) == 0:
            p = (2 ** j) + i
            print(p)
            break
    else:
        continue
    break
print('%x' % p)
assert (n-1) % p == 0
# n = (2p r1+1)(2p r2 + 1)
# n = 4p^2 r1 * r2 + 2p(r1 + r2) + 1
# n / 2p = 2p r1 * r2 + (r1 + r2)
rem = (n - 1) // (2 * p) // 2 // p
print(len(bin(rem)))
fac = factor(rem)
def search(fac, i=0, cur1 = 1, cur2 = 1):
    if i == len(fac):
        pp = cur1 * 2 * p + 1
        qq=  cur2 * 2 * p + 1
        if n % pp == 0:
            return pp
        return None
    prime, exp = fac[i]
    for j in range(0, exp + 1):
        ret = search(fac, i + 1, cur1 * prime ^ j, cur2 * prime ^ (exp - j))
        if ret:
            return ret
print(fac)
p = search(fac)
q = n // p
assert p * q == n
d = lift(Mod(65537, (p - 1) * (q - 1)) ^ -1)
flag = Mod(int(flag_message, 16), n) ^ d
print(repr(int(flag).to_bytes(64, 'big')))

not-be-fooled.sage

# https://math.boisestate.edu/reu/publications/AnomalousPrimesAndEllipticCarmichaelNumbers.pdf

while True:
    n = ZZ.random_element(2**200)
    p = (n + 1) ^ 3 - n ^ 3
    if is_prime(p):
        break

for i in range(1,100):
    E = EllipticCurve(GF(p), [0, i])
    if E.order() == p:
        print(0)
        print(i)
        print(p)
        g = E.gens()[0]
        print(g[0])
        print(g[1])
        break

ooo-flag-shares.ipynb