Bugku CTF---简单的RSA

一、题目信息：简单的rsa - Bugk CTF平台

二、解题步骤

1.点击题目附件下载，解压得到字节码文件

2.打开在线Python pyc文件编译与反编译，上传pyc文件进行反编译，还原出源代码

3.从反编译后的代码中提取RSA参数：p,q,e,n,c
RSA解密公式：m=c^d mod n

只需要求出私钥d，就能解出明文，接下来编写python脚本去解密

from Crypto.Util.number import * import gmpy2 import base64 p = int("0xED7FCFABD3C81C78E212323329DC1EE2BEB6945AB29AB51B9E3A2F9D8B0A22101E467",16) q = int("0xAD85852F9964DA87880E48ADA5C4487480AA4023A4DE2C0321C170AD801C9",16) e = 65537 n = p * q c = int("0x75AB3202DE3E103B03C680F2BEBBD1EA689C8BF260963FE347B3533B99FB391F0A358FFAE5160D6DCB9FCD75CD3E46B2FE3CFFE9FA2E9508702FD6E4CE43486631",16) phi = (p-1)*(q-1) #求φ(n)，φ(n)=(p-1)(q-1) d = gmpy2.invert(e,phi) #求e对于模n的逆元，即解密指数d m = pow(c,d,n) #m=c^e mod n，m为10进制格式 flag = long_to_bytes(m) #m的字符串形式 print(base64.b64decode(flag)) #上面得到的flag是base64编码，进行一次base64解码即可

4.运行脚本得到flag

flag{IlikeCTFbutCTFdon'tlikeme}

三、额外补充内容

依赖库：pycryptodome,gmpy2

安装命令：pip install pycryptodome gmpy2

四、RSA密码核心知识点

1. 密钥生成公式
- n=p\times q，p、q为两个大素数；

- 欧拉函数：\varphi(n)=(p-1)(q-1)；

- 私钥 d 是公钥e在模\varphi(n)下的乘法逆元，满足 e\cdot d \equiv 1 \pmod{\varphi(n)}。

2. 加解密公式
- 加密：c=m^e \pmod{n}

- 解密：m=c^d \pmod{n}