XSCTF联合招新赛-baigeiRSA Writeup

拿到附件后查看内容

import libnum
from Crypto.Util import number
from secret import flag

size = 128
e = 65537
p = number.getPrime(size)
q = number.
<!--more-->
getPrime(size)
n = p*q

m = libnum.s2n(flag)
c = pow(m, e, n)

print('n = %d' % n)
print('c = %d' % c)

分析

参数设置

size = 128
e = 65537

size处设置了生成的素数p和q的比特长度

e=65537：RSA的公钥指数，这是一个常用的固定值

生成RSA密钥

p = number.getPrime(size)
q = number.getPrime(size)
n = p*q

number.getPrime(size)生成一个size比特的随机素数

n = p*q：计算RSA的模数n（一个256位的数）。

加密flag

m = libnum.s2n(flag)
c = pow(m, e, n)

libnum.s2n(flag)：将flag字符串转换为一个大整数m（s2n表示“string to number”）。

c = pow(m, e, n)：计算密文c，即m^e mod n（RSA加密的核心操作）。

输出结果

print('n = %d' % n)
print('c = %d' % c)

解密思路

1. 分解n得到p和q（因为n是256位的，对于现代计算机来说分解是可行的）。
2. 计算欧拉函数φ(n) = (p-1)*(q-1)。
3. 计算私钥d，即e模φ(n)的逆元：d = pow(e, -1, φ(n))。
4. 解密密文：m = pow(c, d, n)。
5. 将m转换为字符串：flag = libnum.n2s(m)。

于是我们构造以下exploit

import libnum
from Crypto.Util.number import inverse
from Crypto.Util import number

size = 128
n = 88503001447845031603457048661635807319447136634748350130947825183012205093541
c = 40876621398366534035989065383910105526025410999058860023908252093679681817257
e=65537

# 分解n得到的p和q
p=unknown
q=unknown

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = libnum.n2s(m)
print("解密后的flag:", flag)

然后暴力分解因数n得到p和q

则最终的exp如下：

import libnum
from Crypto.Util.number import inverse
from Crypto.Util import number

size = 128
n = 88503001447845031603457048661635807319447136634748350130947825183012205093541
c = 40876621398366534035989065383910105526025410999058860023908252093679681817257
e=65537

p=274539690398523616505159415195049044439
q=322368694010594584041053487661458382819

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = libnum.n2s(m)
print("解密后的flag:", flag)

成功Caught the flag!

workspace# python3 exploit.py 
解密后的flag: b'HSCTF{@Zh3n_Ba1_G3i!@}'