[NewStarCTF 2023 公开赛道]babyrsa
Python源码:
# coding: utf-8
import gmpy2, libnum
n = 17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
c = 14322038433761655404678393568158537849783589481463521075694802654611048898878605144663750410655734675423328256213114422929994037240752995363595
e = 65537
# 使用在线工具http://www.factordb.com/index.php
# 分解n,得到15个质数:
list_p_q = [2217990919, 2338725373, 2370292207, 2463878387, 2706073949, 2794985117, 2804303069, 2923072267, 2970591037, 3207148519, 3654864131, 3831680819, 3939901243, 4093178561, 4278428893]
i_len_list_p_q = len(list_p_q)
'''
欧拉函数φ(n)的性质:
如果n可以分解成两个互质的整数之积,n = p1 * p2,则有:
φ(n) = φ(p1*p2) = φ(p1) * φ(p2),
即:
积的欧拉函数等于各个乘数的欧拉函数之积。
举个栗子:
φ(36) = φ(4*9) = φ(4) * φ(9)
= 2 * 6
= 12
我们可以把列表list_p_q中的15个元素分成2组:
第1组group1包括:第0个元素;
第2组group2包括:第1个元素,第2个元素,...,第14个元素。
因为:
n = list_p_q[0] * list_p_q[1] * list_p_q[2] * ... * list_p_q[13] * list_p_q[14]
所以,
我们也可以把n看成:
group1 = list_p_q[0]
group2 = list_p_q[1] * list_p_q[2] * ... * list_p_q[13] * list_p_q[14]
n = group1 * group2
group1与group2是两个互质的整数。
所以,
φ(n) = φ(group1*group2) = φ(group1) * φ(group2),
一个质数m的欧拉函数 = m - 1
所以,
φ(n) = (group1 - 1) * (group2 - 1)
针对这道题,则有:
φ(n) = φ(group1*group2) = φ(group1) * φ(group2)
= (list_p_q[0] - 1) * (list_p_q[1] - 1) * (list_p_q[2] - 1) * ... * (list_p_q[13] - 1) * (list_p_q[14] - 1)
接下来,就开始求欧拉函数φ(n)的值:
'''
φ_n = 1
for i in range(i_len_list_p_q):
φ_n *= list_p_q[i] - 1
d = gmpy2.invert(e, φ_n)
m = pow(c, d, n)
print('flag:', libnum.n2s(int(m)))
运行结果:
flag: b'flag{us4_s1ge_t0_cal_phI}'
进程已结束,退出代码为 0
更多推荐



所有评论(0)