RSA

RSA wp

题目概要

题目地址：https://ctf.wgpsec.org/challenges

title：女朋友的聊天记录

题目：给了加密方式和一个txt文件

1. m明文使用libsum转为字符串

2. 随机生成0,30中的一个数并对m乘方处理

   c1 = m ** rand

3. 对c1进行一次常规的RSA加密

   c2 = pow(c1, e, n)

4. 对c2进行第二次RSA加密

   c3 = pow(c2, e, peiqi)

txt给的已知为n，e，peiqi，c3

且peiqi = (p + 520)(q + 520)

思路分析

根据两个方程解两个未知量的原则，知道n和peiqi肯定能解出p，q，构造二次函数为x² + (p + q)x + p * q = 0算根

因为求出p，q的目的是为了求解phi欧拉函数的值

可以直接凑phi_n = (p - 1)(q - 1) = pq - (p + q) +1

(p + q) = (peiqi - n - 520²) / 520

这里要注意，在进行第二次RSA加密的时候，大素数为peiqi

即p_peiqi = p + 520，q_peiqi同理

phi_peiqi = (p + 519)(q + 519) = pq + 519(p + q) + 519²

两次RSA的欧拉函数已知，可容易解密

最后一个乘方爆破即可

exp

import gmpy2
import libnum
import binascii
n=
e=65537
peiqi=
c=

paq = ((peiqi - n - pow(520, 2)) // 520)
phi_n = n - paq + 1
phi_peiqi = n + 519 * paq + pow(519, 2)

d_peiqi = gmpy2.invert(e, phi_peiqi)
c_n = pow(c, d_peiqi, peiqi)

d_n = gmpy2.invert(e, phi_n)
c_fi = pow(c_n, d_n, n)

for k in range(1, 30):
	mid = gmpy2.iroot(c_fi, 4)[0]
	try:
		print libnum.n2s(mid)
		#print (binascii.unhexlify(hex(mid)[2:]).decode('utf-8'))
		break
	except:
		continue

flag：wgpsec{wo_nei_gui_go_to_papapa}