Skip to content

Instantly share code, notes, and snippets.

@theoremoon

theoremoon/solve.sage Secret

Created Oct 11, 2020
Embed
What would you like to do?
SECCON 2020 Online CTF - solution for crypto01
def decrypt(c, d, n):
size = n.bit_length() // 2
c_high, c_low = c
b = (c_low**2 - c_high**3) % n
EC = EllipticCurve(Zmod(n), [0, b])
m_high, m_low = (EC((c_high, c_low)) * d).xy()
m_high, m_low = int(m_high), int(m_low)
return (m_high << size) | m_low
def contfrac(x, y):
"""
calculate continuated fraction of x/y
"""
while y:
a = x // y
yield a
x, y = y, x - a * y
def covergents(e, n):
numerator, denominator = 1, 0
numerator2, denominator2 = 0, 1
for x in contfrac(e, n):
numerator, numerator2 = x * numerator + numerator2, numerator
denominator, denominator2 = x * denominator + denominator2, denominator
yield numerator, denominator
def solve(n, e, plow):
low_size = int(plow).bit_length()
approx_size = (int(n).bit_length() // 2 - low_size) // 2 - 8
print("known: {}, approx: {}".format(low_size, approx_size))
for cov in covergents(e, n):
x, y = cov
if x == 0:
continue
if x * x > n:
continue
u = round(e*y / x - n - 1)
v = round(sqrt(abs(u**2 - 4 * n)))
if u < 0:
continue
p_ = Integer(u + v) // 2
size = p_.nbits() - approx_size
p_ = (p_ >> size) << size
PR, x = PolynomialRing(Zmod(n), name="x").objgen()
f = x*2**low_size + plow + p_
f = f.monic()
roots = f.small_roots(X=2**(size - low_size), beta=0.5, epsilon=0.05)
for r in roots:
p = int(p_ + plow + r * 2 ** low_size)
if n % p == 0:
return p, n // p
return None, None
exec(open("output.txt").read())
# set_verbose(2)
for param in ciphertexts:
n, e, c, hint = param["n"], param["e"], param["c"], param["hint"]
p, q = solve(n, e, hint)
d = inverse_mod(e, (p+1)*(q+1))
masked_flag = masked_flag ^^ decrypt(c, d, int(n))
print(bytes.fromhex(hex(masked_flag)[2:]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment