本文人工撰写；生成式AI仅用于校对和手写公式转 LaTeX。

题目链接

题目附件ez_square.py:

from Crypto.Util.number import *
from secret import flag

assert len(flag) == 35
assert flag[:7] == b'moectf{'
assert flag[-1:] == b'}'

def main():
    p = getPrime(512)
    q = getPrime(512)

    n = p * q
    e = 65537

    m = bytes_to_long(flag)

    c = pow(m, e, n)
    hint = pow(p + q, 2, n)

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

if __name__ == '__main__':
    main()

"""
n = 83917281059209836833837824007690691544699901753577294450739161840987816051781770716778159151802639720854808886223999296102766845876403271538287419091422744267873129896312388567406645946985868002735024896571899580581985438021613509956651683237014111116217116870686535030557076307205101926450610365611263289149
c = 69694813399964784535448926320621517155870332267827466101049186858004350675634768405333171732816667487889978017750378262941788713673371418944090831542155613846263236805141090585331932145339718055875857157018510852176248031272419248573911998354239587587157830782446559008393076144761176799690034691298870022190
hint = 5491796378615699391870545352353909903258578093592392113819670099563278086635523482350754035015775218028095468852040957207028066409846581454987397954900268152836625448524886929236711403732984563866312512753483333102094024510204387673875968726154625598491190530093961973354413317757182213887911644502704780304
"""

依旧是RSA加解密，需要我们想办法求出pp和qq。

hint=(p+q)2 mod pq=(p2+q2) mod pq=(p−q)2 mod pq \begin{aligned} \mathrm{hint} &= (p+q)^2 \bmod pq \\ &= (p^2+q^2) \bmod pq \\ &= (p-q)^2 \bmod pq \end{aligned}

由于

(p−q)2≪pq, (p-q)^2 \ll pq,

因此

p−q=hint. p-q=\sqrt{\mathrm{hint}}.

又因为 pqpq 与 p−qp-q 已知，所以

p+q=(p−q)2+4pq. p+q = \sqrt{(p-q)^2+4pq}.

于是

p=(p−q)2+4pq+(p−q)2, p = \frac{\sqrt{(p-q)^2+4pq}+(p-q)}{2}, q=(p−q)2+4pq−(p−q)2. q = \frac{\sqrt{(p-q)^2+4pq}-(p-q)}{2}.

然后就可以RSA解密了。

脚本:

import math
from Crypto.Util.number import long_to_bytes


n = 83917281059209836833837824007690691544699901753577294450739161840987816051781770716778159151802639720854808886223999296102766845876403271538287419091422744267873129896312388567406645946985868002735024896571899580581985438021613509956651683237014111116217116870686535030557076307205101926450610365611263289149
c = 69694813399964784535448926320621517155870332267827466101049186858004350675634768405333171732816667487889978017750378262941788713673371418944090831542155613846263236805141090585331932145339718055875857157018510852176248031272419248573911998354239587587157830782446559008393076144761176799690034691298870022190
hint = 5491796378615699391870545352353909903258578093592392113819670099563278086635523482350754035015775218028095468852040957207028066409846581454987397954900268152836625448524886929236711403732984563866312512753483333102094024510204387673875968726154625598491190530093961973354413317757182213887911644502704780304
e = 65537


p_q = math.isqrt(hint)
print(f"p-q:{p_q}")

p_plus_q = math.isqrt(p_q * p_q + 4 * n)
print(f"p+q:{p_plus_q}")

p = (p_q + p_plus_q) // 2
q = (p_plus_q - p_q) // 2

N = math.lcm(p -  1, q - 1)

d = pow(e, -1, N)

m = pow(c, d, n)

print(long_to_bytes(m))

输出:

p-q:2343458209274425996985047093820966198128351630302072151512123489799998738482601894111632387083653590921895308705989628111300210058143690024967352474744452
p+q:18470541968644424341853360787392124964912376035057025304283994397475806910690870232956788598297125214076864380379470271723684322545326168920856938288029630
b'moectf{THIS_IS_FLAG}'