TSG LIVE CTF 10 | random duo

#tsg_live_ctf_10

#!/usr/bin/python3

from Crypto.Util.number import getPrime, bytes_to_long
import flag 
import secrets

assert(len(flag.flag) == 33)

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 3
assert(phi%e!=0)
d = pow(e, -1, phi)

secret_bytes = secrets.token_bytes(80)
m1 = bytes_to_long(flag.flag+secret_bytes+secrets.token_bytes(8))
m2 = bytes_to_long(flag.flag+secret_bytes+secrets.token_bytes(8))

c1 = pow(m1, e, N)
c2 = pow(m2, e, N)

print(f'N = {N}')
print(f'e = {e}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

RSA。TSG Live CTF 10 | random_pairと同様なので、Coppersmith's Short Pad Attack で解ける

N = 88514316563512879494623038195836664351937567894693534710038379189014201738600441320930701787465333959723689879136504359256101701497215740395585980297980037308246431410913892443941861931264280677081787414747628772470500268453262104902273750184435639148584505036960489689277592575246284187355445145185298950547
e = 3
c1 = 27962784309136702827078425255662563529771454120801846586316474175920891882897399697532160136134305562402000873419407805988912396878983267355448671983874127533624353009062811512922588478877693162951414889231084998608048780806278652796744546133371271501977858188616434486932456489240359031033397239428954927263
c2 = 71134590510821103274291289760747463716022331508477046378755631215525590015440656167203580720397866851660348920265543172428820230666288397747757378382183302803514748428047655413523613772375373880953912213943275224259975495443032538947913983560135891639017264504473841493065901709877437510532248929962088576516


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()

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**(8 * 8), beta=1, epsilon=0.02)
# print(roots)
roots = [588089528649909681]

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

print(bytes.fromhex(hex(m)[2:]))