[BJDCTF 2020]EasyRSA cigerant的WriteUp

from gmpy2 import invert
from libnum import nroot
from Crypto.Util.number import long_to_bytes

e = 65537
c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
# z = Fraction(1, Derivative(arctan(p), p)) - Fraction(1, Derivative(arth(q), q))
# z = (1 + p^2) - (1 - q^2) = p^2 + q^2
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
# n = p * q
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441


# n^2 = p^2*q^2 => p^2 = n^2/q^2
# z = n^2/q^2 + q^2 => (q^2)^2 - z*q^2 + n^2 = 0
def get_q(z, n):
    q = []
    for qq in [(z + nroot((z ** 2 - 4 * n ** 2), 2)) // 2, (z - nroot((z ** 2 - 4 * n ** 2), 2)) // 2]:
        if n % nroot(qq, 2) == 0:
            q.append(nroot(qq, 2))
    return q


def get_m(p, q, e, c):
    return pow(c, invert(e, (p - 1) * (q - 1)), p * q)


q = get_q(z, n)
print("q的解个数为:", len(q))
q1 = q[0]
p1 = n // q1
q2 = q[1]
p2 = n // q2
m1 = get_m(p1, q1, e, c)
m2 = get_m(p2, q2, e, c)
print("flag1:", long_to_bytes(m1))
print("flag2:", long_to_bytes(m2))