Easy_RSA - Writeup by AI题目信息来源: Bugku CTF类别: Crypto (密码学)文件: file.txt题目描述Hey, youre a hacker, right? I think I am too, look at what I made! ----------- (2531257, 43) My super secret message: 906851 991083 1780304 2380434 438490 356019 921472 822283 817856 556932 2102538 2501908 2211404 991083 1562919 38268 ----------- Problem is, I dont remember how to decrypt it... could you help me out?考点分析考点权重说明RSA基础原理30%理解RSA加密解密流程小模数分解25%n较小时可直接分解获取私钥编码识别25%识别非标准的ASCII编码方式模式分析20%通过部分解密结果推测完整Flag技术背景:标准RSA加密c m^e mod nRSA安全性依赖于大整数分解的困难性当n较小时如本题n≈2^21可以通过试除法快速分解解题思路攻击策略分解模数n: 由于n2531257相对较小使用试除法分解计算私钥d: 利用扩展欧几里得算法求模逆元标准RSA解密:m c^d mod n编码分析: 识别明文数值的编码规则模式推断: 根据已知字符推测完整Flag技术路线file.txt → 提取参数(n,e,密文) → 分解n得到p,q → 计算φ(n)和私钥d → RSA解密得到明文数值 → 分析编码规则 → 还原Flag详细步骤步骤1: 提取RSA参数从题目文件中提取公钥:(n2531257, e43)密文序列: 16个数字n2531257e43ciphertexts[906851,991083,1780304,2380434,438490,356019,921472,822283,817856,556932,2102538,2501908,2211404,991083,1562919,38268]步骤2: 分解模数n由于n只有约21位2531257 ≈ 2^21.3可以使用试除法快速分解importmathdeffactorize(n):foriinrange(2,int(math.isqrt(n))1):ifn%i0:pi qn//ireturnp,qreturnNone,Nonep,qfactorize(n)# 结果: p 509, q 4973# 验证: 509 × 4973 2531257 ✓步骤3: 计算私钥d使用RSA密钥生成公式# 计算欧拉函数phi_n(p-1)*(q-1)# phi_n 508 × 4972 2525776# 扩展欧几里得算法求模逆元defextended_gcd(a,b):ifa0:returnb,0,1gcd,x1,y1extended_gcd(b%a,a)xy1-(b//a)*x1 yx1returngcd,x,ydefmod_inverse(e,phi):gcd,x,_extended_gcd(e%phi,phi)ifgcd!1:raiseException(模逆元不存在)returnx%phi dmod_inverse(e,phi_n)# 结果: d 58739# 验证: e×d mod φ(n) 43×58739 mod 2525776 1 ✓步骤4: RSA解密对每个密文执行标准RSA解密m c^d mod nplaintexts[pow(c,d,n)forcinciphertexts]# 解密结果:# [103, 105103, 101109, 12383, 97118, 97103, 10195, 83105,# 12095, 70108, 121105, 110103, 9584, 105103, 101114, 115125]步骤5: 分析编码规则观察解密后的数值发现它们不是直接的ASCII码而是多个ASCII码的十进制拼接索引明文数值分解方式ASCII码字符0103103‘g’g1105103105103‘i’‘g’ig2101109101109‘e’‘m’em31238312383‘{’‘S’{S49711897118‘a’‘v’av59710397103‘a’‘g’ag61019510195‘e’‘_’e_78310583105‘S’‘i’Si81209512095‘x’‘_’x_97010870108‘F’‘l’Fl10121105121105‘y’‘i’yi11110103110103‘n’‘g’ng1295849584‘_’‘T’_T13105103105103‘i’‘g’ig14101114101114‘e’‘r’er15115125115125‘s’‘}’s}编码规则: 将1-2个字符的ASCII码十进制表示直接拼接成一个整数。例如ig→ ASCII: 105, 103 → 拼接:105103{S→ ASCII: 123, 83 → 拼接:12383步骤6: 还原Flag将所有解码后的字符片段拼接g ig em {S av ag e_ Si x_ Fl yi ng _T ig er s} gigem{Savage_Six_Flying_Tigers}完整代码#!/usr/bin/env python3# -*- coding: utf-8 -*- Easy_RSA - CTF解题脚本 importmathdefextended_gcd(a,b):扩展欧几里得算法ifa0:returnb,0,1gcd,x1,y1extended_gcd(b%a,a)xy1-(b//a)*x1 yx1returngcd,x,ydefmod_inverse(e,phi):计算模逆元 d e^(-1) mod phigcd,x,_extended_gcd(e%phi,phi)ifgcd!1:raiseException(模逆元不存在)returnx%phideffactorize(n):试除法分解nforiinrange(2,int(math.isqrt(n))1):ifn%i0:returni,n//ireturnNone,Nonedefsolve():# RSA参数n2531257e43# 密文序列ciphertexts[906851,991083,1780304,2380434,438490,356019,921472,822283,817856,556932,2102538,2501908,2211404,991083,1562919,38268]print([*] Step 1: 分解模数n)p,qfactorize(n)print(f p {p}, q {q})print(f 验证:{p}×{q}{p*q})print(\n[*] Step 2: 计算私钥d)phi_n(p-1)*(q-1)dmod_inverse(e,phi_n)print(f φ(n) {phi_n})print(f d {d})print(f 验证: e×d mod φ(n) {(e*d)%phi_n})print(\n[*] Step 3: RSA解密)plaintexts[pow(c,d,n)forcinciphertexts]fori,minenumerate(plaintexts):print(f [{i:2d}]{m})print(\n[*] Step 4: 分析编码并还原Flag)# 根据分析分组解码groups[g,ig,em,{S,av,ag,e_,Si,x_,Fl,yi,ng,_T,ig,er,s}]flag.join(groups)print(f\n[] Flag:{flag})# 最终验证print(\n[*] Step 5: 验证Flag)encoded_nums[]forgroupingroups:numint(.join(str(ord(c))forcingroup))encoded_nums.append(num)encrypted[pow(m,e,n)forminencoded_nums]ifencryptedciphertexts:print( ✓✓✓ 加密验证通过Flag确认无误 ✓✓✓)else:print( [-] 验证失败)if__name____main__:solve()运行结果[*] Step 1: 分解模数n p 509, q 4973 验证: 509 × 4973 2531257 [*] Step 2: 计算私钥d φ(n) 2525776 d 58739 验证: e×d mod φ(n) 1 [*] Step 3: RSA解密 [ 0] 103 [ 1] 105103 ... [*] Step 4: 分析编码并还原Flag [] Flag: gigem{Savage_Six_Flying_Tigers} [*] Step 5: 验证Flag ✓✓✓ 加密验证通过Flag确认无误 ✓✓✓