TSG Live CTF 10 | random_pair

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

m1 = bytes_to_long(flag.flag+secrets.token_bytes(12))
m2 = bytes_to_long(flag.flag+secrets.token_bytes(12))

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 で、平文の後ろに異なる12バイトのパディングがついた暗号文が2つ得られる。普通にCoppersmith's Short Pad Attack で解けるが、https://www.youtube.com/live/RvMF4u1Ifgc?feature=share&t=15496 によるとより天才的な解法でも解けるらしい

N = 131524088884825815804488932464729357040334400654894482058463384631465646564218562087397372641691153724192714309237816737178676891008253858742684770007206270690351261617425456727727358875299906146914830254560972052930255319744195538734348410986466067329708785605858045414804679488686183262367088579297015291141
e = 3
c1 = 53446890814226238195814900775610146361354688642953984822875182297861976571235892581728318314459205473773163777796449566433544434134073179844466939691972553393776130664306258111549148944010961079361802647342130537687069419065674984241592765378827102906801889899262139334877519178755098426417577535191788787887
c2 = 53446890814226238195814900775610146361354688642953984822875182321385725425008957482596867857544541131433772697093663878596038952458110930478268276653144018403231153004739183129121025413011758697599979926904528387653993851636222310955660828650069081991070148602980332627389671548440711748081532341124803683994


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()
# 
# p = random_prime(2**512)
# q = random_prime(2**512)
# 
# n = p * q
# e = 3
# 
# m1 = randint(2, n-1)
# delta = randint(2, 2**60)
# m2 = m1 + delta
# 
# assert m2 < n
# 
# c1 = pow(m1, e, n)
# c2 = pow(m2, e, n)

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**(13 * 8), beta=1, epsilon=0.01)
roots = [13102448862201039697373809223]

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

print(m)