RSA2 - Writeup by AI

RSA2 - Writeup by AI题目信息项目内容题目来源Bugku CTF题目类型Crypto (密码学)考点RSA 小指数攻击、Rabin 加密题目描述给定 RSA 加密参数加密指数 e 2模数 N3072 位密文 c要求解密得到 flag。考点分析核心知识点RSA 小指数攻击当加密指数 e 很小时如果明文 m 较小使得 m^e N则可以直接对密文开 e 次方得到明文Rabin 加密体制当 e2 时这实际上是 Rabin 加密是 RSA 的一个特例数学判断能力需要快速识别 e2 的特殊性并选择合适的攻击方法技术路线e2e 较大成功失败读取题目参数检查 e 值Rabin 加密体制常规 RSA 攻击尝试直接开平方得到明文分解 N 后解密提取 Flag解题思路步骤 1: 分析题目参数观察给定的参数e 2这是关键线索正常的 RSA 通常使用 e65537e2 说明这是 Rabin 加密N 是 3072 位大数直接分解难度较大密文 c约 1024 位步骤 2: 判断攻击方法对于 e2 的情况有两种可能直接开平方如果 m^2 N则 c m^2直接开平方即可得到 mRabin 解密如果 m^2 N需要先分解 N然后使用 Rabin 解密算法关键判断如果 flag 长度较短如几十字节转换为整数后 m 的位数会远小于 N 的位数此时 m^2 N 很可能成立步骤 3: 实施攻击尝试直接对密文 c 开平方计算 sqrt_c isqrt©验证 sqrt_c^2 c如果成立sqrt_c 就是明文 m步骤 4: 字节转换将整数 m 转换为字节串flag_bytesm.to_bytes((m.bit_length()7)//8,big)详细步骤完整代码#!/usr/bin/env python3# -*- coding: utf-8 -*- RSA2 题解 - e2 的 Rabin 加密 考点小指数攻击 大数分解 importgmpy2fromgmpy2importmpz# 题目给定的参数e2Nmpz(5004569440512110095315912424236175274218550002178520628553704610188181488300107757918726993816925107576358839207238392032724279712357944600981150418044342904955183246544920154528020203647228706080590639340343735982316211703073337574981350845754016638561933765280884678570680367503568140933515083469472139275415872875491138960647889141175026872713919095134528223443650952975885468899247330481542073142242487522406896050936375863486400486804933954660288571791351740728080243533354249689085912022147064731371745696132875825246594817148582726296487493779171982197115211832071128542525685567572109806874753150627688296718782579760309570820648240192966871855147357680212713231986714423893717406698898987306268449007903381646144106494586566066635414476454341566286646898749536138451297644386089944695562753778211546095612829981319898508937274774759125681653612693566131588017270700916204903608877962939755738345796258686161864194209)cmpz(178578054113587665880573638525543971357824122622159505488720384368602953181166564534730680603152376825130794419393716164247143515361066971379409790862584250121)deftry_direct_sqrt():尝试直接开平方如果 m^2 Nprint([*] 尝试直接对密文开平方...)sqrt_cgmpy2.isqrt(c)ifsqrt_c*sqrt_cc:print(f[] 找到整数平方根{sqrt_c})try:flagint(sqrt_c).to_bytes((int(sqrt_c).bit_length()7)//8,big)print(f[] 解密结果{flag})returnTrueexcept:print([-] 无法转换为字节)else:print([-] 密文不是完全平方数需要分解 N)returnFalseif__name____main__:print(*60)print(RSA2 Writeup - e2 的 Rabin 加密攻击)print(*60)print(f\n[*] e {e})print(f[*] N 位数{N.bit_length()}bits)print(f[*] 密文 c {c})# 尝试直接开平方iftry_direct_sqrt():print(\n[] 解题完成)用户原始问题请阅读目录下的文件解出这道CTF题目。