CrewCTF 2022 | Malleable Metal

#CrewCTF_2022

#uninterested_challenge_list

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
import random
import binascii
from secret import flag

e = 3
BITSIZE =  8192
key = RSA.generate(BITSIZE)
n = key.n
flag = bytes_to_long(flag)
m = floor(BITSIZE/(e*e)) - 400
assert (m < BITSIZE - len(bin(flag)[2:]))
r1 = random.randint(1,pow(2,m))
r2 = random.randint(r1,pow(2,m))
msg1 = pow(2,m)*flag + r1
msg2 = pow(2,m)*flag + r2
C1 = Integer(pow(msg1,e,n))
C2 = Integer(pow(msg2,e,n))
print(f'{n = }\n{C1 = }\n{C2 = }')

https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage のぱくり

そういうわけなのでCoppersmith's Short Pad Attackで解ける

def resultant(f1, f2, remove_var):
    """
    PR.<x, y> = PolynomialRing(Zmod(n))
    f1 = ...
    f2 = ...

    fn, xn = resultant(f1, f2, y) # yを消去する
    # fnはxnについての1変数多項式であることが期待できる
    """

    modulus = f1.base_ring().cardinality()
    gens = f1.parent().gens()
    assert len(gens) == 2
    gen_idx = list(gens).index(remove_var)

    gen_name = f1.parent().variable_names()[1 - gen_idx]
    namez = [name + "z" for name in f1.parent().variable_names()]
    namen = gen_name + "n"

    PRz = PolynomialRing(Zmod(modulus), namez)
    q1 = f1.change_ring(PRz)
    q2 = f2.change_ring(PRz)

    PRn = PolynomialRing(Zmod(modulus), [namen])
    xn = PRn.gen()
    f = q1.resultant(q2, gens[gen_idx])
    f = f.univariate_polynomial().change_ring(PRn).subs(**{gen_name: xn})
    return f, xn

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a.monic()

with open("out.txt") as f:
    n = int(f.readline().strip().split(" = ")[1])
    c1 = int(f.readline().strip().split(" = ")[1])
    c2 = int(f.readline().strip().split(" = ")[1])

e = 3

PR.<m, d> = PolynomialRing(Zmod(n))

f1 = m**e - c1
f2 = (m + d)**e - c2

fn, dn = resultant(f1, f2, m)
roots = fn.small_roots(X=2**510, beta=1, epsilon=0.05)

PR.<x> = PolynomialRing(Zmod(n))
f1 = x**e - c1
f2 = (x + roots[0])**e - c2
m = -gcd(f1, f2).constant_coefficient()

e = 3
BITSIZE =  8192
x = floor(BITSIZE/(e*e)) - 400

print(bytes.fromhex(hex(int(m) // 2**x)[2:]))