2024BeginCTF Crypto--fake_N

发表于 分类于 阅读次数： 本文字数： 883 阅读时长 ≈ 2 分钟

FIRST

首先分解fake_n,使用factordb.com，得到17个质因子

factor

second

阅读题目得真实的n为15个质因子的积，遍历17个质因子中15个的积作为真实的n，并求出phi，写出对应脚本为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Cryptodome.Util.number import *
import gmpy2
import sympy
fake_n_list=[2215221821 , 2290486867 , 2333428577 , 2361589081 , 2446301969 , 2507934301, 2590663067 ,3107210929 ,3278987191,3389689241,3417707929,3429664037,3716624207, 3859354699, 3965529989, 4098704749, 4267348123]
c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
fake_n = 1
e = 65537
for i in range(len(fake_n_list)):
    fake_n *= fake_n_list[i]
for i in range(len(fake_n_list)):
    for k in range(len(fake_n_list)):
        n=fake_n//(fake_n_list[i]*fake_n_list[k])
        phi=1
        for j in fake_n_list:
            if(j!=fake_n_list[i] and j!=fake_n_list[k]):
                phi=phi*(j-1)
        d=inverse(e,phi)
        x=long_to_bytes(pow(c,d,n))
        if(b'begin' in x):
            print(x)

得到结果为

begin{y0u_f1nd_th3_re4l_n}