*CTF 2021 | little case

#*CTF_2021

from Crypto.Util.number import *
from libnum import *
from secret import flag,special,p,q,n


def little_trick(msg):
    p1 = getPrime(1024)
    q1 = getPrime(1024)
    n1 = p1 * q1
    d1=random.randint(1,2**256)
    e1=inverse(d1,(p1-1)*(q1-1))
    print(n1)
    print(e1)
    print(pow(msg,e1,n1))


def real_trick():
    assert (special > (ord("*")*100) and gcd(special,(p-1)*(q-1))!=1 )
    print(n)
    print(pow(libnum.s2n(flag),special,n))


if __name__ == '__main__':
    little_trick(p-1)
    real_trick()

little_trick と real_trick の2段回の構成になっている。

little_trick　は の値が小さいので自明に Boneh Durfee Attackができる

これでの値がわかったが、real_trick は の値がわからない上、である gcd(phi, e) != 1のRSA

多少のguess(またはは簡単に解けてしまう )によりと考えると、

あとは時間をかけて解く

N1 = 21669699875387343975765484834175962461348837371447024695458479154615348697330944566714587217852888702291368306637977095490953192701450127798670425959768118384915082017373951315699899009631834471691811815393784748930880954114446745814058132752897827717077886547911476575751254872623927783670252969995075629255541621917767501261249192653546875104532649043219697616464205772025267019328364349763854659490144531087349974469079255236823096415094552037488277752927579909539401311624671444833332618177513356173537573280352724384376372955100031534236816681805396608147647003653628203258681097552049114308367967967184116839561

e1 = 20717541468269984768938524534679430706714860712589983300712432366828367981392533792814384884126053081363266457682162675931547901815985830455612301105504518353600255693451085179954519939635263372257973143178677586338992274607959326361412487748088349413448526455377296931144384663805056580662706419414607407821761761574754611275621927387380065975844282519447660467416826579669726178901884060454994606177784839804528666823956703141147239309978420776148158425922031573513062568162012505209805669623841355103885621402814626329355281853436655713194649170570579414480803671531927080535374958180810697826214794117466378050607

c1 = 17653913822265292046140436077352027388518012934178497059850703004839268622175666123728756590505344279395546682262531546841391088108347695091027910544112830270722179480786859703225421972669021406495452107007154426730798752912163553332446929049057464612267870012438268458914652129391150217932076946886301294155031704279222594842585123671871118879574946424138391703308869753154497665630799300138651304835205755177940116680821142858923842124294529640719629497853598914963074656319325664210104788201957945801990296604585721820046391439235286951088086966253038989586737352467905401107613763487302070546247282406664431777475

N = 22346087036331379968192118389403047568445805414881948978518580277027027486284293415097623011228506968071753709256352246733181304513713003096615266613365080909760605498017330085960699607777361429562376124376340215426398797920168016137830563564636922257215066266075494625782943973857490781916694118187094786034792437781964601089843549995939887939410763350338658901108020658475956489391300528691289604149598720803012371765770928211044755626045817053870803040863722458554924076011151695567147976903053993914859714631837755435592006986598006207692599019026644753575853382810261910332197447386727419606073948645238377595719

c = 12732299056226934743176360461051108799706450051853623472248552066649321279227693844417404789169416642586313895494292082308084823101092675162498154181999270703392144766031531668783213589136974486867571090321426005719333327425286160436925591205840653712046866950957876967715226097699016798471712274797888761218915345301238306497841970203137048433491914195023230951832644259526895087301990301002618450573323078919808182376666320244077837033894089805640452791930176084416087344594957596135877833163152566525019063919662459299054294655118065279192807949989681674190983739625056255497842063989284921411358232926435537518406L

def boneh_durfee(e, N):
    s = floor(sqrt(N))
    M = Matrix([[e, s], [N, 0]])
    Mred = M.LLL()
    D = [abs(Mred[i, 1]) // s for i in [0,1]]

    for d in D:
        flag = True
        for _ in range(10):
            t = randint(2, N - 2)
            tt = pow(t, e, N)
            if tt^d != t:
                flag = False
                break

        if flag:
            return d


def eth_root(x, e, p):
    """
    Adleman-Manders-Miller e-th root extraction algorithm in Fp
    x: e-th residue in Fq
    e: exponent (e | p-1)
    p: prime
    """
    assert is_prime(p)
    assert (p - 1) % e == 0
    assert (p - 1) % (e**2) != 0

    l = (p - 1) % (e**2) // e
    a = -inverse_mod(l, e) % e
    return pow(c, (1 + a * (p - 1) // e) // e, p)


def all_roots(known_root, e, p):
    """
    Find all e-th roots in Fp
    known_root: one of e-th root of something
    e: exponent size
    p: prime
    """

    # primitive e-th roots
    proots = set()
    while len(proots) < e:
        proots.add(pow(randint(2, p-1), (p - 1) // e, p))

    # all e-th roots
    roots = set()
    for root in proots:
        roots.add(known_root * root % p)

    return roots

d1 = boneh_durfee(e1, N1)
print("[+] d1={}".format(d1))
assert d1

p = int(pow(c1, d1, N1) + 1)
assert is_prime(p)

q = int(N // p)
assert is_prime(q)
assert N == p * q

# special = gcd(p-1, q-1)
# specials = [x**e for x, e in factor(special)]
# print(specials)
special = 4919

print("[+] calculating roots...")
mps = all_roots(eth_root(c % p, special, p), special, p)
mqs = all_roots(eth_root(c % q, special, q), special, q)


from Crypto.Util.number import long_to_bytes
print("[+] CRT...")
for mp in mps:
    for mq in mqs:
        m = CRT_list([int(mp), int(mq)], [p, q])
        s = long_to_bytes(m)
        if b"*CTF" in s:
            print(s)