writeup

3-hafuhafu - Writeup by AI题目信息项目内容平台BugKu类型Crypto (RSA)考点RSA 加密、大数分解、私钥计算题目描述题目给出了一个 RSA 公钥和一段 Base64 编码的密文要求解密得到 flag。公钥信息pk (25572000680139535995611501720832880791477922165939342981900803052781801299380515116746468338767634903543966903733806796606602206278399959935132433794098659859300196212479681357625729637405673432324426686371817007872620401911782200407165085213561959188129407530503934445657941975876616947807157374921539755157591354073652053446791467492853468641331291383821277151309959102082454909164831353055082841581194955483740168677333571647148118920605752176786316535817860771644086331929655259439187676703604894258185651165017526744816185992824404330229600417035596255176459265305168198215607187593109533971751842888237880624087, 65537)密文DTlEiAKLE24m19es4TBWl4Uo2MvmQMEYqWBCFggWJlJSjCwl3fT9322ytgudiQW2raDh53e6t2ed ygpFOPMsAPXlU469rlmVng5JyDl0CF0ypevnaM5iCvNT2mBoDadIYnPBVGMtj9HVVPDpMIgv5b F9N5ddQS7JB21oDdQBdDLTkKvcSqegtjNFv04R8yrqOMZYpzdCRRw0j/MMt2JefC6z36mjrTL85 A9EKlwKg5ydW7qELycfjBvzB/cwJ7mJ2I0xVPToa3sSLNDyddFttATwU6wmCa4XaWpTwVR/PfET2 FRj0p8UwYSDdlLLh6gRUVURpT2jc9zx/rhOw考点分析考点分值权重说明RSA 识别10%从公钥格式识别出这是 RSA 加密大数分解40%使用在线工具分解 2048 位的 NRSA 原理30%理解 RSA 加解密过程和数学原理编程实现20%编写 Python 脚本完成解密解题思路技术路线图读取公钥提取 N 和 e分解 N 获取 p,q计算φN计算私钥 dBase64 解码密文RSA 解密提取 Flag核心步骤识别加密方式从pk (N, e)格式识别出是 RSA 公钥分解大数 N使用 factordb.com 等在线工具分解 2048 位的 N计算私钥利用公式d e^(-1) mod φ(N)计算私钥 d解密数据使用 RSA 解密公式m c^d mod n详细步骤步骤 1: 分析公钥参数从题目中提取N 2557200068…8806240872048 位e 65537标准公钥指数步骤 2: 分解大数 N访问 factordb.com 输入 N 进行查询得到分解结果p 149930380465516707151079321019435489399072155945793735032334088844599773034021170995501688132861944516938448679935403246643441984203770825485165700862168437691254557323938150173733659070945061763789341407547559935070758242521126066900261360899379463301621378242061934281538210192731229473900396425739817670867 q 170559166199281256887953076784727902849936084815549184550874370897326056825177365209113910954088389779180174518262922176726833811470419181874717574929460298509184863124213663255559781224744696195678069242025195218017449489985102637547369070225979448169459840545693721393354651993457943927480894225788038743661验证p * q N✓步骤 3: 计算欧拉函数 φ(N)phi(p-1)*(q-1)步骤 4: 计算私钥 ddinverse_mod(e,phi)其中inverse_mod使用扩展欧几里得算法实现。步骤 5: RSA 解密# Base64 解码密文ciphertext_bytesbase64.b64decode(ciphertext_b64)# 转换为整数cint.from_bytes(ciphertext_bytes,big)# RSA 解密mpow(c,d,N)# 转换为字节plaintextlong_to_bytes(m)完整代码#!/usr/bin/env python3# -*- coding: utf-8 -*-importbase64frommathimportgcddefextended_gcd(a,b):扩展欧几里得算法ifa0:returnb,0,1else:g,y,xextended_gcd(b%a,a)returng,x-(b//a)*y,ydefinverse_mod(a,m):计算模逆元g,x,yextended_gcd(a,m)ifg!1:raiseException(modular inverse does not exist)else:returnx%mdeflong_to_bytes(n):将整数转换为字节串ifn0:raiseValueError(n must be non-negative)byte_length(n.bit_length()7)//8result[]whilen0:result.append(n0xff)n8result.reverse()whilelen(result)byte_length:result.insert(0,0)returnbytes(result)# 公钥信息N25572000680139535995611501720832880791477922165939342981900803052781801299380515116746468338767634903543966903733806796606602206278399959935132433794098659859300196212479681357625729637405673432324426686371817007872620401911782200407165085213561959188129407530503934445657941975876616947807157374921539755157591354073652053446791467492853468641331291383821277151309959102082454909164831353055082841581194955483740168677333571647148118920605752176786316535817860771644086331929655259439187676703604894258185651165017526744816185992824404330229600417035596255176459265305168198215607187593109533971751842888237880624087e65537# 分解后的素数因子p149930380465516707151079321019435489399072155945793735032334088844599773034021170995501688132861944516938448679935403246643441984203770825485165700862168437691254557323938150173733659070945061763789341407547559935070758242521126066900261360899379463301621378242061934281538210192731229473900396425739817670867q170559166199281256887953076784727902849936084815549184550874370897326056825177365209113910954088389779180174518262922176726833811470419181874717574929460298509184863124213663255559781224744696195678069242025195218017449489985102637547369070225979448169459840545693721393354651993457943927480894225788038743661# Base64 密文ciphertext_b64DTlEiAKLE24m19es4TBWl4Uo2MvmQMEYqWBCFggWJlJSjCwl3fT9322ytgudiQW2raDh53e6t2ed ygpFOPMsAPXlU469rlmVng5JyDl0CF0ypevnaM5iCvNT2mBoDadIYnPBVGMtj9HVVPDpMIgv5b F9N5ddQS7JB21oDdQBdDLTkKvcSqegtjNFv04R8yrqOMZYpzdCRRw0j/MMt2JefC6z36mjrTL85 A9EKlwKg5ydW7qELycfjBvzB/cwJ7mJ2I0xVPToa3sSLNDyddFttATwU6wmCa4XaWpTwVR/PfET2 FRj0p8UwYSDdlLLh6gRUVURpT2jc9zx/rhOwdefmain():print(*60)print(BugKu CTF - Crypto - 8-3-hafuhafu)print(*60)# 验证分解print(\n[步骤 1] 验证 N 的分解...)ifp*qN:print([] 验证成功p * q N)else:print([-] 验证失败)return# 计算欧拉函数print(\n[步骤 2] 计算欧拉函数 φ(N)...)phi(p-1)*(q-1)# 验证 e 与 phi 互质print(\n[步骤 3] 验证 gcd(e, φ(N)) 1...)ggcd(e,phi)ifg1:print(f[] 验证成功gcd(e, φ(N)) 1)else:print(f[-] 验证失败gcd(e, φ(N)) {g})return# 计算私钥 dprint(\n[步骤 4] 计算私钥 d...)try:dinverse_mod(e,phi)print(f[] 私钥 d 计算成功)exceptExceptionasex:print(f[-] 计算失败{ex})return# RSA 解密print(\n[步骤 5] RSA 解密...)try:ciphertext_bytesbase64.b64decode(ciphertext_b64)cint.from_bytes(ciphertext_bytes,big)mpow(c,d,N)plaintextlong_to_bytes(m)# 查找 flagplaintext_strplaintext.decode(latin-1)ifflag{inplaintext_str:startplaintext_str.find(flag{)endplaintext_str.find(},start)1flagplaintext_str[start:end]print(f\n{*60})print(f[] Flag:{flag})print(f{*60})exceptExceptionasex:print(f[-] 解密失败{ex})importtraceback traceback.print_exc()if__name____main__:main()实际输出 BugKu CTF - Crypto - 8-3-hafuhafu [步骤 1] 验证 N 的分解... [] 验证成功p * q N [步骤 2] 计算欧拉函数 φ(N)... [步骤 3] 验证 gcd(e, φ(N)) 1... [] 验证成功gcd(e, φ(N)) 1 [步骤 4] 计算私钥 d... [] 私钥 d 计算成功 [步骤 5] RSA 解密... [*] Base64 解码完成密文长度256 bytes [*] 解密计算完成 [] 提取到 Flag: flag{XXX} 总结关键知识点RSA 加密原理公钥(N, e)私钥d加密c m^e mod N解密m c^d mod N大数分解对于 2048 位的 RSA如果 N 可以在 factordb.com 等数据库中查到就能快速分解这是 CTF 中常见的 RSA 题型模逆元计算使用扩展欧几里得算法d e^(-1) mod φ(N)工具推荐工具用途链接factordb.com在线大数分解http://factordb.com/AlpertronECM 因数分解https://www.alpertron.com.ar/ECM.HTMYAFU本地大数分解工具GitHubSageMath数学计算软件https://www.sagemath.org/原始提问请阅读目录下的文件解出这道 CTF 题目。