本文为人工撰写，仅使用生成式AI校对。

题目链接

题目附件baby_next.py:

from Crypto.Util.number import *
from gmpy2 import next_prime
from functools import reduce
from secret import flag

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

def main():
    p = getPrime(512)
    q = int(reduce(lambda res, _: next_prime(res), range(114514), p))

    n = p * q
    e = 65537

    m = bytes_to_long(flag)

    c = pow(m, e, n)

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

if __name__ == '__main__':
    main()

"""
n = 96742777571959902478849172116992100058097986518388851527052638944778038830381328778848540098201307724752598903628039482354215330671373992156290837979842156381411957754907190292238010742130674404082688791216045656050228686469536688900043735264177699512562466087275808541376525564145453954694429605944189276397
c = 17445962474813629559693587749061112782648120738023354591681532173123918523200368390246892643206880043853188835375836941118739796280111891950421612990713883817902247767311707918305107969264361136058458670735307702064189010952773013588328843994478490621886896074511809007736368751211179727573924125553940385967
"""

注意到这是RSA加密，并且公钥(n, e)已给出，私钥缺少d。

m=cd(modn)m = c^d \pmod{n}

d=e−1(modλ(n))d = e^{-1} \pmod{\lambda(n)}

λ(n)=lcm⁡(p−1,q−1)\lambda(n) = \operatorname{lcm}(p - 1, q - 1)

所以我们需要pp和qq。

注意到:

令p=2k+1p = 2k + 1 q=2t+1q = 2t + 1，

有a=q+p2a = \frac{q + p}{2} b=q−p2b = \frac{q - p}{2},

所以有a+b=qa + b = q a−b=pa - b = p，

所以n=p∗q=(a+b)×(a−b)=a2−b2n = p * q = (a + b) \times (a - b) = a^2 - b^2。

所以我们可以从n\sqrt{n}开始寻找aa，只需要检验a2−n=b\sqrt {a^2 - n} = b是否为完全平方数即可。

爆破脚本如下:

import math
from Crypto.Util.number import long_to_bytes

n = 96742777571959902478849172116992100058097986518388851527052638944778038830381328778848540098201307724752598903628039482354215330671373992156290837979842156381411957754907190292238010742130674404082688791216045656050228686469536688900043735264177699512562466087275808541376525564145453954694429605944189276397
c = 17445962474813629559693587749061112782648120738023354591681532173123918523200368390246892643206880043853188835375836941118739796280111891950421612990713883817902247767311707918305107969264361136058458670735307702064189010952773013588328843994478490621886896074511809007736368751211179727573924125553940385967
e = 65537
sn = math.isqrt(n)
print(sn)

a = sn
while(True):
    b2 = a * a - n
    if(b2 <= 0):
        a += 1
        continue
    b = math.isqrt(b2)
    if(b * b == b2):
        print(f"a:{a}")
        print(f"b:{b}")
        print(f"p = a - b:{a - b}")
        print(f"q = a + b:{a + b}")

        lambdaN = math.lcm(a - b - 1, a + b - 1)
        d = pow(e, -1, lambdaN)
        m = pow(c, d, n)

        print(f"m:{m}")
        print(f"flag:{long_to_bytes(m)}")

        break;
    a += 1

输出:

9835790642950870702456388102541833011851580184211232019829465812360043670916676289614924432072209183922656300400121695605187082642402117584019839317552728
a:9835790642950870702456388102541833011851580184211232019829465812360043670916676289614924432072209183922656300400121695605187082642402117584019839317552729
b:20372862
p = a - b:9835790642950870702456388102541833011851580184211232019829465812360043670916676289614924432072209183922656300400121695605187082642402117584019839297179867
q = a + b:9835790642950870702456388102541833011851580184211232019829465812360043670916676289614924432072209183922656300400121695605187082642402117584019839337925591
m:13932707432295201762915447416760117532731261009261834621470110290846674770286488746417998205
flag:b'moectf{THIS_IS_FLAG}'