强网杯-Qualifier-2022/强网先锋/ASR writeup

1. challenge

from Crypto.Util.number import getPrime
from secret import falg
pad = lambda s:s + bytes([(len(s)-1)%16+1]*((len(s)-1)%16+1))

n = getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2
e = 3

flag = pad(flag)
print(flag)
assert(len(flag) >= 48)
m = int.from_bytes(flag,'big')
c = pow(m,e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
'''

2. 分析

n是一个平方数，平方根是4个128bit素数的乘积，应该可以通过ecm分解。

e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
pqrs = 2872432989693854281918578458293603200587306199407874717707522587993136874097838265650829958344702997782980206004276973399784460125581362617464018665640001
assert pqrs*pqrs == n

使用yafu在一台8U的云主机上可以分解n。

docker run -ti ssst0n3/yafu:2.10
# yafu -threads 128
...
Total factoring time = 977.9845 seconds


***factors found***

P39 = 218566259296037866647273372633238739089
P39 = 225933944608558304529179430753170813347
P39 = 223213222467584072959434495118689164399
P39 = 260594583349478633632570848336184053653

ans = 1

接下来可以考虑求得d。

p = 225933944608558304529179430753170813347
assert(p.is_prime())
assert(n%p==0)
q = 260594583349478633632570848336184053653
assert(q.is_prime())
assert(n%q==0)
r = 223213222467584072959434495118689164399
assert(r.is_prime())
assert(n%r==0)
s = 218566259296037866647273372633238739089
assert(s.is_prime())
assert(n%s==0)

phi = p*(p-1)*q*(q-1)*r*(r-1)*s*(s-1)
print(gcd(e, phi))
# d = inverse_mod(e, phi)

但本题中e和phi不互素。

因为e较小，可以在对每个素数的模域上，解出$c^{\frac{1}{3}}$, 每组会有至多3个解，共4组。

对每个解要与素因子进行CRT还原出原始解。

from itertools import product

def euler_totient(factors):
    return reduce(lambda t, p: t * (p - 1), factors, 1)

def e_phi_not_coprime(primes, e, c):
    """
    for gcd(e, phi) != 1 and it's small
    """
    phi = euler_totient(primes)
    gcd_e_phi = gcd(phi, e)
    small_roots = []
    for prime in primes:
        P.<a> = PolynomialRing(Zmod(prime),implementation='NTL')
        f = a^gcd_e_phi-c
        roots = f.monic().roots()
        # print(roots)
        for root in roots:
            assert len(root) == 2
            assert root[1] == 1
        small_roots.append([Integer(root[0]) for root in roots])

    roots = []
    for iter_roots in product(*small_roots):
        roots.append(CRT_list(list(iter_roots), primes))
    return roots

def solve():
    primes = [p,q,r,s]
    roots = e_phi_not_coprime(primes, e, c)
    for root in roots:
        flag = int(root).to_bytes(64, 'big')
        if b"flag" in flag:
            print(flag)
            break

solve()

b'\x00\x00\x00\x00flag{Fear_can_hold_you_prisoner_Hope_can_set_you_free}\x06\x06\x06\x06\x06\x06'