1. 题目描述

题目连接：戳我💋

拿到题目看到：

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

一眼鉴定为 dp、dq 泄露

2. 解题过程

RSA-CRT

中国剩余定理

目的：降低指数加快 RSA 算法的解密过程

需要计算额外的 dp、dq、qlnv

加密：

解密：

直接上代码：

import libnum

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852


def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = extended_gcd(b, a % b)
        return gcd, y, x - (a // b) * y


def find_modular_inverse(q, p):
    gcd, x, _ = extended_gcd(q, p)
    if gcd == 1:
        return x % p
    else:
        raise ValueError("The modular inverse does not exist.")


qlnv = find_modular_inverse(q, p)
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
h = qlnv * (m1 - m2) % p
m = m2 + h * q
# m = 11630208090204506176302961171539022042721137807911818876637821759101

# 解密出来的 m 是十进制数，要转换为字符
print(libnum.n2s(m))
# 获得flag：noxCTF{W31c0m3_70_Ch1n470wn}

3. 所需工具

无

4. 写在最后

本文完

敬爱与明天🌹