RSimple - Writeup by AI

RSimple - Writeup by AI题目信息项目内容题目名称RSimple题目来源Bugku CTF题目类型Crypto (密码学)题目描述I created this unbreackable RSA applicstion, go ahead and try hack me.考点分析核心考点RSA 低指数攻击Low Public Exponent Attack当 RSA 的公钥指数 e 较小时如 e3, 5, 17 等存在特殊攻击方法本题中 e17Håstad 广播攻击Broadcast Attack同一明文用不同的 RSA 公钥加密且指数 e 相同收集至少 e 组密文后可使用中国剩余定理CRT恢复明文无需分解模数 n中国剩余定理Chinese Remainder Theorem, CRT求解同余方程组的重要工具在密码学攻击中有广泛应用分值权重预估考点权重说明识别广播攻击场景30%发现每次连接 n 不同但 e 固定中国剩余定理实现30%正确实现 CRT 算法低指数开方还原25%对 CRT 结果开 e 次方根数据格式转换15%整数转字节串得到 flag解题思路1. 初步侦察连接到服务器后发现有 4 个选项1) encrypt data 2) decrypt data 3) get the flag 4) exit选择选项 3 后得到一个公钥 n模数加密后的 flag密文 c关键观察每次重新连接n 都会变化说明是动态生成的 RSA 参数。2. 攻击思路分析由于每次连接的 n 不同动态生成加密的是同一个 flag明文 m 固定使用相同的公钥指数 e推测 e 较小这满足了Håstad 广播攻击的条件3. 数学原理设明文为mmm即 flag公钥指数为eee本题 e17第 i 次连接的模数为nin_ini​第 i 次连接的密文为cic_ici​则有ci≡me(modni)c_i \equiv m^e \pmod{n_i}ci​≡me(modni​)收集至少eee组(ni,ci)(n_i, c_i)(ni​,ci​)后使用中国剩余定理求解xxx使得x≡ci(modni),∀i∈{1,2,…,e}x \equiv c_i \pmod{n_i}, \quad \forall i \in \{1,2,\ldots,e\}x≡ci​(modni​),∀i∈{1,2,…,e}根据 CRT 性质在整数域上有xmex m^exme因此对xxx开eee次方根即可得到明文mmmmxem \sqrt[e]{x}mex​4. 技术路线图graph TD A[连接服务器] -- B[获取 n_i, c_i] B -- C{收集到 e 组} C --|否 | B C --|是 | D[验证 n_i 互质] D -- E[中国剩余定理 CRT] E -- F[得到 x m^e] F -- G[开 e 次方根] G -- H[得到明文 m] H -- I[转换为字符串] I -- J[提取 Flag]详细步骤步骤 1: 收集多组 (n, c) 对编写脚本自动连接服务器重复选择选项 3收集至少 17 组数据因为 e17。defcollect_samples(num_samples):pairs[]foriinrange(num_samples):socksocket.socket(socket.AF_INET,socket.SOCK_STREAM)sock.connect((49.232.142.230,13874))# 选择选项 3sock.send(b3\n)responserecv_all(sock,timeout2)# 提取 n 和 cn_matchre.search(rpublic key: (\d),response)c_matchre.search(rencrypted flag is: (\d),response)ifn_matchandc_match:nint(n_match.group(1))cint(c_match.group(1))pairs.append((n,c))sock.close()returnpairs步骤 2: 验证所有 n 互质确保所有模数两两互质这是 CRT 成立的前提defgcd(a,b):whileb:a,bb,a%breturna# 验证互质foriinrange(len(ns)):forjinrange(i1,len(ns)):assertgcd(ns[i],ns[j])1,n 不互质步骤 3: 实现中国剩余定理fromfunctoolsimportreducedefchinese_remainder_theorem(remainders,moduli):total0prodreduce(lambdaa,b:a*b,moduli)forr,ninzip(remainders,moduli):pprod//n totalr*mod_inverse(p,n)*preturntotal%proddefmod_inverse(a,m):g,x,_extended_gcd(a,m)ifg!1:raiseException(模逆不存在)returnx%mdefextended_gcd(a,b):ifa0:returnb,0,1else:g,y,xextended_gcd(b%a,a)returng,x-(b//a)*y,y步骤 4: 计算 17 次方根由于数字很大使用二分法计算整数方根definteger_nth_root(x,n):ifx0:returnNoneifx0:return0low1highxwhilelowhigh:mid(lowhigh)//2powermid**nifpowerx:returnmidelifpowerx:lowmid1else:highmid-1returnhigh步骤 5: 整数转字节串defint_to_bytes(n):ifn0:returnb\x00hex_strhex(n)[2:]iflen(hex_str)%2:hex_str0hex_strreturnbytes.fromhex(hex_str)步骤 6: 运行结果 Bugku CTF - RSimple - 广播攻击 低指数攻击 [*] 开始收集 19 组 (n, c) 对... [*] 每次连接选择选项 3 获取加密的 flag [] 第 1 组: n bits 511, c bits 511 [] 第 2 组: n bits 511, c bits 510 ... [] 成功收集 19 组数据 [*] 验证所有 n 是否互质... [] 所有 n 互质可以进行 CRT [*] 使用前 17 组数据进行中国剩余定理计算... [*] 计算 CRT 中... [] CRT 结果 x 位数8141 bits [*] 对 x 开 17 次方根... [] 方根结果140732080020983337604301220392576184042976423941621345066538658356160610267051067986423126522189195581948679775931972574115191990376366343733726077 [✓] 验证成功flag_int^17 x [*] 转换 flag_int 为字节串... [] Flag bytes: bshellmates{XXX} Flag: shellmates{XXX}