[简单] 初识RSA - Writeup by AI题目信息题目名称初识RSA题目类型Crypto密码学题目来源攻防世界题目描述p 和 q 藏起来了你能帮我找到它们吗题目分析给出的代码fromCrypto.Util.numberimportbytes_to_long,inverse,getPrimefromflagimportflag mbytes_to_long(flag)pgetPrime(1024)qgetPrime(1024)np*qprint(n)e65537cpow(m,e,n)pqp*(q-1)qpq*(p-1)print(c,c)print(n,n)print(pq,pq)print(qp,qp)给出的数据c 8722269075970644434253339592758512788160408912707387632591552130175707843950684315083250494010055435391879036285103810263591951437829414438640307561645721347859659807138051841516634704123100270651976676182059252251162982609391666023674158274992400910869692389001622774140191223807887675081808561012755545464977015973615407965906513878979919700065923364884766974187303774330319143647840846354404070430118235352622445115153298578370521811697710289716188726587743282814946239856766713516166990341116198180068191759095913957606379780234116317390622824096667107736103270907349927467971817639795094030622157581511033950777 n 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074584935050067254029262890188260006596141011807724688556673520261743199388391094490191001701011230322653422314758778116196105077883955436582364267530633358016652912054880813710531145973799193443828969535902856467548523653920307742364119002349899553478815101092655897400295925170383678499125295006364960124859003 pq 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074488896197029704465200125337817646702009123916866455067019234171839614862660036737875747177391796376553159880972782837853473250804807544086701088829096838316550146794766718580877976153967582795248676367265069623900208276878140709691073369415161936376086988069213820933152601453587292943483693378833664901178324 qp 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074475956379708898904933143429835002718457573266164923043251954374464149976302585916538814746811455883837138715445492053610047383292461097590195481556557381952895539341802954749542143253491617052100969586396996063822508764438280468492894012685918249843558593322831683872737943676955669923498182824352081785243246 e 65537解题思路1. RSA 加密原理回顾标准 RSA 加密过程选择两个大素数p和q计算n p * q计算欧拉函数φ(n) (p-1) * (q-1)选择公钥指数e通常为 65537计算私钥d e^(-1) mod φ(n)加密c m^e mod n解密m c^d mod n2. 关键发现题目中给出了两个特殊值pqp*(q-1)qpq*(p-1)展开这两个式子pq p*(q-1) p*q - p n - pqp q*(p-1) p*q - q n - q因此可以得到p n - pqq n - qp这就是题目的突破口虽然 p 和 q 被藏起来了但通过给出的pq和qp值我们可以直接计算出它们。3. 解题步骤步骤操作说明1计算 pp n - pq2计算 qq n - qp3验证确保p * q n4计算 φ(n)phi (p-1) * (q-1)5计算私钥 dd inverse(e, phi)6解密消息m pow(c, d, n)7转换为 flagflag long_to_bytes(m)解题脚本fromCrypto.Util.numberimportlong_to_bytes,inverse# 题目给出的数据c8722269075970644434253339592758512788160408912707387632591552130175707843950684315083250494010055435391879036285103810263591951437829414438640307561645721347859659807138051841516634704123100270651976676182059252251162982609391666023674158274992400910869692389001622774140191223807887675081808561012755545464977015973615407965906513878979919700065923364884766974187303774330319143647840846354404070430118235352622445115153298578370521811697710289716188726587743282814946239856766713516166990341116198180068191759095913957606379780234116317390622824096667107736103270907349927467971817639795094030622157581511033950777n10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074584935050067254029262890188260006596141011807724688556673520261743199388391094490191001701011230322653422314758778116196105077883955436582364267530633358016652912054880813710531145973799193443828969535902856467548523653920307742364119002349899553478815101092655897400295925170383678499125295006364960124859003pq10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074488896197029704465200125337817646702009123916866455067019234171839614862660036737875747177391796376553159880972782837853473250804807544086701088829096838316550146794766718580877976153967582795248676367265069623900208276878140709691073369415161936376086988069213820933152601453587292943483693378833664901178324qp10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074475956379708898904933143429835002718457573266164923043251954374464149976302585916538814746811455883837138715445492053610047383292461097590195481556557381952895539341802954749542143253491617052100969586396996063822508764438280468492894012685918249843558593322831683872737943676955669923498182824352081785243246e65537# 关键步骤通过 pq 和 qp 求 p 和 qpn-pq qn-qpprint(fp {p})print(fq {q})# 验证assertp*qn,计算错误p*q ! nprint(✓ p*q n 验证通过)# 计算欧拉函数 φ(n) (p-1)*(q-1)phi(p-1)*(q-1)# 计算私钥 ddinverse(e,phi)# 解密消息mpow(c,d,n)# 将整数转换为字节串得到 flagflaglong_to_bytes(m)print(f\n解密成功)print(fflag {flag.decode()})运行结果执行上述脚本后输出p 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074584935050067254029262890188260006596141011807724688556673520261743199388391094490191001701011230322653422314758778116196105077883955436582364267530633358016652912054880813710531145973799193443828969535902856467548523653920307742364119002349899553478815101092655897400295925170383678499125295006364960124859003 q 10466186506773626671397261081802640650185744558208505628349249045496105597268556020207175016523119333667851114848452038431498926527983706092607207796937431312520131882751891731564121558651246025754915145600686076505962750195353958781726515647847167067621799990588328894365930423844435964506372428647802381074584935050067254029262890188260006596141011807724688556673520261743199388391094490191001701011230322653422314758778116196105077883955436582364267530633358016652912054880813710531145973799193443828969535902856467548523653920307742364119002349899553478815101092655897400295925170383678499125295006364960124859003 ✓ p*q n 验证通过 解密成功 flag flag{...}知识点总结知识点说明RSA 加密基础理解 RSA 的加密解密原理数学推导能力通过代数变形找出隐藏的关系Python Crypto 库使用long_to_bytes和inverse函数CTF 解题技巧注意题目给出的每一个条件都可能是突破口心得体会这道题是 RSA 入门的经典题目主要考察对 RSA 算法的理解需要明白 p、q 在 RSA 中的重要性数学推导能力通过pq p*(q-1)这个式子推导出p n - pq细心观察题目描述说p 和 q 藏起来了提示我们要从给出的数据中找到它们解题的关键在于发现pq和qp的真正含义一旦找到了 p 和 q剩下的就是标准的 RSA 解密流程。Flagflag{...}注实际 flag 需要运行解题脚本获得此处省略具体值。提示词1请阅读代码解这一道 CTF 题目。提示词2该题目是攻防世界中Ctypto类型的题目信息如下 题目[简单] 初识RSA 题目描述p和q藏起来了你能帮我找到它们吗请根据现有文件内容 输出一份解题的writeup格式为md文件。