Problem: [SWPUCTF 2021 新生赛]crypto4

Crypto

#RSA #素数分解

源码分析

注意到

q = next_prime(p)
​

p-q过小

在RSA中 p≈q 可通过费马分解n得到私钥

EXP

from gmpy2 import *
from Crypto.Util.number import *

n = 52147017298260357180329101776864095134806848020663558064141648200366079331962132411967917697877875277103045755972006084078559453777291403087575061382674872573336431876500128247133861957730154418461680506403680189755399752882558438393107151815794295272358955300914752523377417192504702798450787430403387076153
c = 10227915341268619536932290456122384969242151167487654201363877568935534996454863939953106193665663567559506242151019201314446286458150141991211233219320700112533775367958964780047682920839507351492644735811096995884754664899221842470772096509258104067131614630939533042322095150722344048082688772981180270243
e = 0x10001

# 费马分解
a = isqrt(n)
while (b2 := a*a - n) and not is_square(b2):
    a += 1
b = isqrt(b2)
p = a + b
q = a - b

# 计算私钥并解密
phi = (p-1) * (q-1)
d = invert(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)

print(f"Flag: {flag}")
​
            
AI代码解释
            
                
            
        

得到flag

Flag: b'NSSCTF{no_why}'
​