from Crypto.Util.number import getStrongPrime, inverse, bytes_to_long, GCD from random import randint from flag import flag p = getStrongPrime(512) q = getStrongPrime(512) n = p * q while True: d = randint(int(n ^ (0.200 + 0.198)), int(n ^ 0.400)) if GCD(d, (p-1)*(q-1)) == 1: break phi = (p - 1) * (q - 1) e = inverse(d, phi) the_d = d >> 120 enc = pow(bytes_to_long(flag), e, n) print(f"{n = }") print(f"{e = }") print(f"{the_d = }") print(f"{enc = }")
pbctf2020 | Special Giftのパクり。そういうわけでmultivariate coppersmithで解ける
https://rbtree.blog/posts/2022-04-16-about-one-challenge-in-crewctf/
load("./defund.sage") N = 108632663721119265653629732004609859912298449722633799380285883216648160372857601675801760067880978603917847166703692881045035049896529437951217729992932290717211826160576978461392959086020394468359011218552688774321371304568720044645937228650936226679777817165681833656879074060600223318274941034682744658669 e = 14345844425098016213772256482412079289738393745812073498070209808609907033131393382491530045098843233130881036367887366122371869140643548114038280798707335512800598771342888649856115041456779942132451953091263382954458865505900604068867390149259907682124384405206933288176074626319327127085393581350114292491 gift = 352073377710397761326601223497407217398962745361852626950893310432240855120282253164273 enc = 3809030071658869024019958989413816190555340165190309349307102024078006074888098309799897882917168240924288075419204826634001055954925033995420530107957711139551352690895168173180794129426016555460621859927958574473508871402627777469014569797460317116847974290121701679302684325635172184673761623938649140825 d_ = gift << 120 k_ = round((e * d_ - 1) / N) PR.<x, y> = PolynomialRing(Zmod(e)) f = 1 + k_*N - k_*y + x*N - x*y k0, s = small_roots(f, [2^120, floor(3 * N^0.5)], m=3, d=5)[0] print(s) from Crypto.Util.number import inverse, long_to_bytes phi = N - int(s) d = inverse(e, phi) m = pow(enc, d, N) print(long_to_bytes(m))
