nss

本题为交互题目，nc连接后发现每次交互时需要我们输入1，然后程序会生成一组公钥来加密同一个明文，并且这些公钥中的e都相同，

输入输出形式决定了后续对数据处理的操作

则我们有

ci≡memod  nic_i \equiv m^e \mod n_i

并且我们可以无限次交互获得足够多的数据，那么我们是否能够恢复m呢？
将 m^e 看成一个整体， 那么问题则变成了给定一个数取模不同数的余数，问原数几何？
显然是中国剩余定理

则我们可以通过CRT得到 m^e 的值，再通过开e次方即可得到m的值。
考虑到交互问题，我们需要再kali下使用pwntools这个库
我比较喜欢本地编写代码后直接到kali上运行

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from Crypto.Util.number import *
from gmpy2 import *
from pwn import *

def crt(n_list, c_list):
    n = 1
    for i in n_list:
        n *= i
    N = []
    for i in n_list:
        N.append(n//i)
    t = []
    for i in range(len(n_list)):
        t.append(inverse(N[i], n_list[i]))
        
    summary = 0
    for i in range(len(n_list)):
        summary += N[i] * t[i] * c_list[i]
    summary %= n
    
    return summary


# 告诉了e时,循环次数就是e,range(e)
'''
io = remote('node4.anna.nssctf.cn', 28649)
e = 127
n_list = []
c_list = []
for i in range(127):
    io.sendlineafter(b'input>', b'1')
    n = int(io.recvline().decode()[2:])
    c = int(io.recvline().decode()[2:])
    n_list.append(n)
    c_list.append(c)
    
M = crt(n_list, c_list)
m = gmpy2.iroot(M, e)[0]
print(long_to_bytes(m))
'''

# 没有告诉e时，需要爆破

k = 1000
io = remote('node4.anna.nssctf.cn', 28649)
n_list = []
c_list = []
for i in range(k):
    print(i)  # 这里把接受数据的序数打印出来了，用于可视化进程
    io.sendlineafter(b'input>', b'1')
    n = int(io.recvline().decode().split(':')[1]) # 因为输出是 n: 6423142657687, 转换为字符串后按:分割去后面数字部分, 等价于[3:],因为有个空格
    c = int(io.recvline().decode()[3:])
    n_list.append(n)
    c_list.append(c)
    if i > 2:
        M = crt(n_list, c_list)
        m,_ = gmpy2.iroot(M, i)  # iroot返回两个值：开根的结果和是否完全开根，这里把结果赋值给m，true或false给_,用于直接判断
        if _:
            print(i, long_to_bytes(m))
            break