Untitled

from gmpy2 import gcd, invert, isqrt
from Crypto.Util.number import *

def fermat_factorization(n):
    """ 使用 Fermat 分解法高效因子分解 n """
    a = isqrt(n)
    b2 = a * a - n
    while not is_square(b2):
        a += 1
        b2 = a * a - n
    b = isqrt(b2)
    return a - b, a + b  # 返回 p, q

def rsa_decrypt(n, d1, d2, c):
    # 使用 Fermat 因式分解快速找到 p 和 q
    p, q = fermat_factorization(n)
    
    # 计算解密后的明文
    m1 = pow(c, d1, q)
    m2 = pow(c, d2, p)
    
    # 使用中国剩余定理（CRT）合并结果
    q_inv = invert(q, p)
    h = (q_inv * (m2 - m1)) % p
    m = m1 + h * q
    
    return long_to_bytes(m)

# 示例数据（从题目提供的数据替换）
n = 94581028682900113123648734937784634645486813867065294159875516514520556881461611966096883566806571691879115766917833117123695776131443081658364855087575006641022211136751071900710589699171982563753011439999297865781908255529833932820965169382130385236359802696280004495552191520878864368741633686036192501791
d1 = 4218387668018915625720266396593862419917073471510522718205354605765842130260156168132376152403329034145938741283222306099114824746204800218811277063324566
d2 = 9600627113582853774131075212313403348273644858279673841760714353580493485117716382652419880115319186763984899736188607228846934836782353387850747253170850
c = 36423517465893675519815622861961872192784685202298519340922692662559402449554596309518386263035128551037586034375613936036935256444185038640625700728791201299960866688949056632874866621825012134973285965672502404517179243752689740766636653543223559495428281042737266438408338914031484466542505299050233075829

# 解密
plaintext = rsa_decrypt(n, d1, d2, c)
print(plaintext)