2020国赛觅马wp

本篇是对《第十三届全国大学生信息安全竞赛创新实践能力赛（线上初赛）》参赛经历的一个整理。

bd

题目描述如此：

数学在密码学里面很重要的！现在知道吃亏了吧！

显然，他说的是大实话，确实应该好好学习数学。

下载附件，可以看到里面是一个py文件，文件内容如下：

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

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p-1) * (q-1)
while True:
    d = getRandomNBitInteger(200)
    if GCD(d, phi) == 1:
        e = inverse(d, phi)
        break

c = pow(m, e, N)

print(c, e, N, sep='\n')

# 37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
# 46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
# 86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289

打开映入眼帘的就是pq等字样，毫无疑问，多半是一个RSA了。

然后，再对代码逐行看过之后，看到11行，生成的d是比较小的，同时可以看到21行打印的e是比较大的（和n相比）。

因此，这个是一个妥妥的 RSA小解密指数攻击 的题目。（常规题型，不了解请Google一下）

于是，贴上解密代码，一瞬得到flag

from myrsa import hack_d, decrypt

n = 86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289
e = 46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
c = 37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066

d = hack_d(e, n)

flag = decrypt(c, d, n)[0]
print(flag)

# flag{d3752538-90d0-c373-cfef-9247d3e16848}

lfsr

题目描述如下：

弱鸡看着题目给的信息束手无策，丈二和尚摸不着头脑 ，你嘿嘿一笑，拿出来了你随身带着的笔记本电脑，噼里啪啦的敲起来了键盘，清晰的函数逻辑和流程出现在了电脑屏幕上，你敲敲键盘，答案变出现在了电脑屏幕上。

读完题目描述，觉得这段话索然无味。。。。。。

还是依旧下载文件，里面是两个文件，一个是加密的程序，另一个是程序的输出。

加密程序 lfsr.py 如下：（注释都是我打的，原文是没有的）

import random

from secret import flag

N = 100
MASK = 2**(N+1) - 1

def lfsr(state, mask):
    feedback = state & mask
    feed_bit = bin(feedback)[2:].count("1") & 1  # feed_bit feedback中二进制位中1的个数是奇数个就是1
    output_bit = state & 1 # 输出位就是state的奇偶 所以初始的state就是偶数  所以output里面前某位（最多100位）联合起来就是初始state
    state = (state >> 1) | (feed_bit << (N-1)) # 就是把feed_bit填入最高位
    return state, output_bit

def main():
    assert flag.startswith("flag{")
    assert flag.endswith("}")

    mask = int(flag[5:-1])
    assert mask.bit_length() == N
    
    state  = random.randint(0, MASK) # 最多100位
    print(state)
    
    outputs = ''
    for _ in range(N**2):
        state, output_bit = lfsr(state, mask)
        outputs += str(output_bit)
    
    with open("output.txt", "w") as f:
        f.write(outputs)

main()

输出文件 output.txt 如下：

0100110011101111011111011010100111001010010100001111110110111101011110011111010010010111011100110111011001100001010010011101101000110110000011111011110000010100001001000011001011011011011001111110101111001010011011100010011110101100100101111001011100011110111101001010000000100100000111100101100100100000100110001111110011100110101000110100011001110110000110111111010111000001101110011001101111010110101000101011110111001011001111111000100100100011100100010101001100111011101111100110101011101101001001110010111011010011111001100001111111100001000001101101000001010100110011001101000101001010001001011000010111111100101111000000101000010110100110101001001100100011000111101000110011110101101111100110101010101000000001110010101001001111101001010111011110110001100101001111110111000110101011011010110101100011110010000011000110010111101010010000011101110111100011011110110001111010101011101100101101001111100100011000100101111011110001111100000110111000111111000111100000110011011011111110011111100010010110000010011100001010101011011101100011001100101100011001010010001101010011000000011110110111000000110001010010111110101011100000010100100001101011010101100110000101100010001010010111011000100001000001001110101011000010111000000010101100001010000010110110000111100011011000010111001111101110111010110000011001011101100000100000100010100100000010011010000111110010001111010000100011110000101111000110100010110101110001011101101100111000001110100100000000010011001110101110000001101100000001010111010011111000101101011001010011001101000111000010111111010101000011011001001110000011100100100010110101100001110110111001000001011111100101100011010010010110000011110100110000111011011010101110101001100110100101100101000100011001011000001011110010000011000110111011110011010001101100010010111110101101101110100111010000001101000011011010011110111101000000100011000000101001000000011010101010000100001110110000110011000111101011100100101111101111111110101000011010001101100010010100111000000010000101100100110101000001001011100011111001101001101100010100000111010101111011101111111101100000010000111110011101010100101110100101010100011110100100000111010001000100011010011100010011000001110110100110110010100100110111011001010010010100000110101110000011110010110100010101000110000111101011011010111101100111100101001101001101100111101000100101101100010111010010111100100111101101110101110011010110011111011111010000011000100010010101110001001000111111100100010100000001001010111010100010111001011011101110010110111110110100011111101110111011000111001010010110001001011011100110101111100100000101110000001011110011101110101101001011111100011001100111001011011001011011101000101100100011101000011101011010110010111111010011110111111111100001101101001101101111000100110010010100000100000100110100100110010000100101100000101010101000111110101001111111011011111101101110010100110000010110111001101110011101100001111111001110110010010011101111100111111000010011010010011100000001010011111111110001111110110110110001001001111011001101110110101100011010001111110010001011010000011110101100110010010001110010100010000000010101010010111011010101011011000010010011010110101101011100100101110001100000111110010101100010100010100010000101111000011111000111000011110001110110000011000100110010101111111111100011010000010010010111111110000000010100100101101101010111011000001010000000101011010110011101000110011011001110101101001001101100010011110001101001001000011001101100001101100000101111000001110100001100001000100000000011010011001001011110011000011011000100011011001011100111111000011011010000100000011110110011011110111000001011101101110110101000101011111110000100000111111110011111111100010101001000011010001110111111011100010111001110110001000101010001001001111111110111001101001001000110000110100000000010010100001010111101001110001011101011000100000001001001011111000100011111000011010001110001111111110111100010001110101011101011100010100000011110000100011001100000100111000111011011101000110010011010011110010010000111010001011111111010110011100111011110100111000101100100111001001010001000100011110101100100010000000000110010111101101111101011001101111000000000100000101001011110000010011110011000000100111001001110001000010011111010100001001010010100111111010111001001110110101010010100010010100101100000001010010111101101000110100111110000000111110000011110011001101010111101010111010111010000000110010001011110101110110001000110111101110101101001001100001101110001000100000110100000100000111110010110110010011111100010011111001110111011010101010001011111110000000011110001010011001101010110010101100101100110010111001100100111101000100010100010010100000010010111101100111110101101111101001010110010001111111001101010111110101111001000111101001110100000111111010000111000010101001001101100111001111111111100011010111110001101000100001010000000001101101001110001000001110010000010110001001001101010111111001001010100011011111011000011001001101000110010101000010100001001000011111001101101111011111001000010010111011010110010011010101100100000101100110110011011110000110011000000001011000111100101000011011011010010111000110101110101111100100010101010101000011000111000010001001000100110101111001001001111100110000101100010011101100001000010100010101110001111110101100101000101110000110010100101100101100101100100111111010100101010011100110100011111001000100010001101111111101011110100111001110101001101000010001011000111101110001010100101101111000110101001011101110110110110110101011010001110011111011110011010100110100111111010101111101111100110000110010111110110100110000011110110111111101111010011010000101010111100001111110110000001000001000011101001010010100100100000001101011101110011001011011110010111101111101010011010000110110101000100010110110101101010110110010011010011111111100001001000110111101001111000011001000010111100110001110110011011011100101011010101100011001111111000100000011100110011001001011000100010110000100001100011010000110110011100000111000010001011010001110010101000100010001001110001011001010000111010010101110001010100011101101110010111100010110010000011010111001101000100111011010100001010011100000100001010100010110100111000000001111100000100011100101011011101111111101101110011111010000110111101000001001110111000001000101100110100100111100100011011100010011111101010001101010100101110000110011000100001111100100001000000100011101101011011111000011110010110110101010011101000001111001011100101001001101111000011110000001010011010001110000111001101100011110011001100000111101001011000110111011001101101101100101100110100101011111111110110000111101000000100101011100111001111111011010100110010001000001101010001110010010000101111000001010100000101100000010101110100000000110011001011000011101101000000100111111010111110100011111101100001001110001100101100001010000100000110111101001101010000011100000000100000101101010010101111101100110110111000011100111001010010100101000111011001001110011111100010010010110100111101100110110111001011110010000111011111010101000010001101110011111010110011100010001111111011100110100011110110001101001110001010001110011110101111101011101100000111011011101110000110111101010001000011110011011101100011100101110100000100010110110011010101011000010010110000000100010011001110010011110010110111001111011010101111011000000111110000011011100100010011110010110000001111110111000100111010100110010111100010000110101011110011010110011001011011010010111001000000000001001010101010001100000110111101000000010100100010100101011111110011011100111101001110101010001100000100100110111110001111000011100010110001101101010011001011111101011000110110000111111101100000000001000010010010011101001000111100000010111011011001001100110000101010110001011000001011010111000111100111011010101010011100100100100010000001101001101010111110010100101000001100111110111111110000101111100110001110111010111001111110111100000111011011010111011001111010100010000111011111111000100110110001100000110101000001010010010100111011100000011111110001000010011010101001111010111100011110110110111000000111101010110001100000100001101101001101010111110001101101100101101101001000100000100110111111010011010011111010110110111101001000100010111101100011010111011111010011110000100001100101101111110010101000000101111101000001111110100000001011011111111100100110101101011100101101001011010001100010101101100000101000001110110101010100001011100010000111010011101110000000010000000000010111100111000010000000110110011011101110000001111011100011101111100011000011001000100111010101011010101110011010011011011010100011011000110111101001110011110000100010011000010000001101010010011000111000000000101100011010001000100010100100100011000101110100010001111101001010100001000000110010011101011101000000100010000011010110100111110101110001111001000000101011101010111110110100100011010000011010111111001001111101101110111110111000001010111100010001001001100000000110011100001100100111010011111011001010001101111111000010110101000011100001010110100101110111001001100000000110110101011001110000011001111100001101110100101101111100110001010011011001010110111000100010000110001111101110011100001101000100110000111000110001011011110100010101011011001001111101001110011100001110001010100011001110110101101001101010101001110011110001011101011100100001101100110110110101011101010110011100000001011010111011101000000101110111110010000000000101001110011111011001110001100010111001010010110011100001000011111101111101100111000101011100011000001100000000000010000111111010010101110101011100010100001000000100111111010111110010010111010110010100111000010111100000000100010111010010011010011001100010001000001100110100101110100110110111101010001100001010011111011100000010110110110000000100101100110100101100111001010100010001011010001010011110100110101000110001110000100111111001000110011110010111000110010001111111111101011110100111101001001101110110011111000110010111000011011111001110101101101000011010101011010111101011101111011100101001111111000101100100000011000100101001011001011110001101001100101001

下载之后，一开始我一脸懵逼，不知道这是在考什么。

于是我就Google了一下 “lfsr”，结果Google给了我这个↓

哎呀！我这个觅马菜鸡，觅马学都没学好，居然对学过的LFSR都不敏感了。 Linear（线性） Feedback（反馈） Shift（移位） Register（寄存器） 看看多好记的。

不知道的同学可以随便先去了解下

简单说说（意思就是我个人的理解，不代表真实定义）这个反馈移位寄存器，FSR就是下面这个图的样子👇，

有一个框框有固定长度n，每一个小格子中的数要么是0，要么是1，我们就可以称其为寄存器，代码中可以用数组来模拟。

这个框框每次都从右边输出固定m位的a_i，然后就会往右移动m位，再利用某种算法计算出m个数，依次填在左边的m位，这样是不是就是相当于移动起来了？于是就可以称其位移位寄存器。一般情况下，都是输出一位，移动一位，计算出新的一位，即m=1。下面都以m=1来谈。

上面提到的某种算法，在这里我们就称之为，“反馈函数”，表达式为 a_n+1 = f(a_n, a_n-1,,,,,a₁) 这样通过前面的n个状态，我们就可以推算出下一个状态。

当这里的反馈函数为线性函数时，我们就称其为 “线性反馈移位寄存器”，那么在GF(2)上（不知道的同学可以简单理解为取值只有0和1），线性函数的即是寄存器中的某些位的异或。（不要问我怎么知道的，想想那异或运算的性质，0和1的计算结果还是0和1，我们就可以简单地通过是仅仅选择某些位来进行异或） 此时，反馈函数就是下面这样👇

$$\begin{equation} f(a_1,a_2,...,a_n) = c_1a_1 \oplus c_2a_2 \oplus ... \oplus c_na_n \end{equation}$$

其中c_i 取值只能是0或者1，为0可以理解为没有选择这一位，为1可以理解为选择了这一位。

那既然咱已经学过了，应该还是有可能做得出来哦。那代码肯定就是整了一个LFSR来构建流觅马咯。那就康康代码先。

果然，代码第8~13行定义了一个 lfsr 函数了作为LFSR。我们暂且跳过它，看 main 函数。

16~17行就是告诉我们，flag 是 flag{***************} 这个样子的。 20行就是告诉我们中间需要我们求的部分是100位的（二进制位哈）。然后它把我们要的 flag 变成了它的 mask 了，所以我们就是要整出来这个玩意，就是我们要的 flag 了。22行，接着它随机了一个 state，也是最多100位的。26~32行它把 LFSR 的前10000个输出结果告诉我们了。

接下来就是分析 lfsr ：

第9行，其将输入的 state 和 mask 进行了一个与操作，并赋值给了 feedback，暂且不懂其意义，但是多半是反馈函数的一部分，毕竟 feedback 的英文意思在这里，搁置先。

第10行，将上面与运算后的结果 feedback 转化为了2进制，然后切片去掉了前面的’0b’字段， .count("1") 是个什么玩意？？不过顾名思义，应该或许大概就是统计1的个数。关于这一点，可以自己写一个py很好进行验证。结果证明就是这样。

s = bin(5)[2:].count("1")
print(s)

# 5 = 101
# s = 2

然后又与了一个1，那就是第10行是在判断，state 和 mask 中一样都是1的个数是奇数个还是偶数个。

第11行，就是将当前的 state 的最后一位赋值给 output_bit

第12行，就是将 state 右移1位再和 feed_bit 左移 N-1位相或。并更新 state 。那到这里，也即是说 state 就是我们前面所说的 那个框框。而12行就是将原来的 state 右移1位，feed_bit 填在了最高位，也就是说，feed_bit 就是反馈函数的输出。

第13行，就将新寄存器（那个框框）和旧寄存器的最后一位返回出去了。而后者就是在我们的output文件中。

再回到前面可以看到，9行和10行，就是我们的反馈函数。

那么，如果我们知道寄存器的位数，即最前面随机生成的 state 的位数，其实我们是可以知道寄存器的初始状态的。也就是output的前多少位，因为不管怎么反馈，初始状态的值是肯定会全部一位一位地输出完了，才会输出新的生成的值，所以输出的前面部分就是一定是 state 的初始值，只是现在不知道位数，无法确定具体是哪些。

现在，才到了问题最关键的地方，怎么把9行和10行，转化为我们前面的公式（1） 的样儿呢？

思考思考思考……

好的，我思考出来了。

为了方便，我们把公式（1）给贴一份到这里。

$$\begin{equation} f(a_1,a_2,...,a_n) = c_1a_1 \oplus c_2a_2 \oplus ... \oplus c_na_n \end{equation}$$

然后考虑第9行和第10行代码，为了方便，也贴这里。

feedback = state & mask
feed_bit = bin(feedback)[2:].count("1") & 1

因为是在按位进行与，所以我们可以把他们看做一个等长的bool数组。于是可以将第9行转化为👇这个。

feedback[i] = state[i] & mask[i] 
# i from 0 to length

那原代码的第10行，不就是在看这些所有的 feedback[i] 中1的个数是奇数还是偶数嘛？

那一堆01的串，你要统计他的个数是奇数还是偶数，除了一个个数，还能怎么计算呢？

那你试试，把他们这一堆01的串，逐位进行异或会怎么样呢？

好吧，事实就是这样，你把一堆01串逐位异或起来得到的结果，和你直接去数1的个数是奇数还是偶数，再与上1进行判断，结果是一样的。如公式（3）所示：

$$feed\_bit == (\sum\limits_{k=1}^na_k) \& 1 == a_1\oplus a_2 \ \oplus ... \oplus\ a_n \ ,\ \forall\ a_k \in \{0\ ,\ 1\}$$

那既然这样了，岂不是就已经可以得到 反馈函数了？如果把公式（3）中的 a_k 视作 feedback[k] 是不是就ok了？

原来的代码的第10行，不正是公式（3）中的左半部分吗？统计1的个数和把他们直接加起来是一样的效果吧？毕竟取值只有0和1

于是，我们可以把原来第10行，直接相当于公式（3）中的右半部分，对吧？那么和我们想要的反馈函数，公式（1）相比，差了什么呢？是不是就是 a_k 前面的系数 c_k ?

那其实我们知道 feedback 只是一个中间变量，我们其实是不需要它的，我们事实上是关心的 state 毕竟他才是寄存器。 而反馈函数中的每一个 a_k 其实都是寄存器中的一个元素。因此，刚才我们将 feedback[k] 这个中间变量视作了 a_k ，现在我们要给他还回去，变成 state[k] ，而原代码的第9行，不就是 state 和 feedback 的关系吗？而且刚好是 与关系 。看到这里明白了吧？ state[k] 才是我们的 a_k 而 mask[k] 则刚好构成我们的 c_k。

如果还是很迷，不妨回到刚才， a_k 视作 feedback[k] 。 那么 feedback[k] = state[k] & mask[k] 没毛病吧？然后在换元，把a_k 替换成 state[k] & mask[k] 为了书写方便，我们可以将 state[k] 记为 b_k 将 mask[k] 记为 c_k 。于是公式（3）就是公式（4）

$$feed\_bit == a_1\oplus a_2 \ \oplus ... \oplus\ a_n \ == c_1b_1 \oplus c_2b_2 \oplus ... \oplus c_nb_n$$

可以看到，此时，公式（4）的最左侧和最右侧。 b_k 是 state (寄存器)此时的状态，而 c_k 是 mask ，而 feed_bit 是寄存器的反馈状态，也就是下一位，用这里的统一符号就是 feed_bit 就是 b_N+1 (N 是寄存器的位数)。为了表示习惯的统一，我们还是将b换为a统一表示，就有了下面的公式（5的 反馈函数：

$$a_{n+1} = c_1a_1 \oplus c_2a_2 \oplus ... \oplus c_na_n$$

那么现在，问题就很清楚了，我们要找的 flag 就是mask，而mask就是我们反馈函数中的系数 c_k，我们把这个玩意求出来了，flag就到手了。

偶滴个乖乖讲了半天，还是不知道这个c_k 咋求哒。莫方莫方。接下来就快了。

根据公式（5）我们能得到什么？ 能得到公式（6）。

$$a_{n+1} = c_1a_1 \oplus c_2a_2 \oplus ... \oplus c_na_n \\ a_{n+2} = c_1a_2 \oplus c_2a_3 \oplus ... \oplus c_na_{n+1} \\ a_{n+3} = c_1a_3 \oplus c_2a_4 \oplus ... \oplus c_na_{n+2} \\ \vdots \\a_{n+n} = c_1a_n \oplus c_2a_{n+1} \oplus ... \oplus c_na_{n+(n-1)} \\$$

公式（6）太过于冗余不好看，我们给它换一个写法。写作如下的矩阵形式。

$$\begin{pmatrix} a_{n + 1} \\ a_{n + 2} \\ \vdots \\ a_{n + n} \\ \end{pmatrix} = \begin{pmatrix} a_1 \quad a_2 & \cdots & \quad a_n \\ a_2 \quad a_3 & \cdots & a_{n+1} \\ \vdots \quad \vdots & \ddots & \vdots \\ a_n \quad a_{n+1} & \cdots & a_{n+n} \end{pmatrix} \times \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \\ \end{pmatrix} = A \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \\ \end{pmatrix}$$

那么，根据公式（7），显然，如果我们能得到 2*n 个 a_k ，我们就能构造出上述的A矩阵和左边的列向量。同时，如果A是可逆的。我们可以直接左乘一个 A^-1 就可得到系数向量 c 了。即

$$\begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \\ \end{pmatrix} = A^{-1} \begin{pmatrix} a_{n + 1} \\ a_{n + 2} \\ \vdots \\ a_{n + n} \\ \end{pmatrix}$$

于是这个题就迎刃而解了。题目中给了 n² 位输出，所以我们直接枚举就好。虽然不知道n是多少，但是可以枚举n从2~100。然后求出mask，即flag。

这里有个小投机，虽然不知道n的大小，但是我们知道flag是100位的，所以只把100位的flag打出来就好了

下面就直接贴代码了。

output = '0100110011101111011111011010100111001010010100001111110110111101011110011111010010010111011100110111011001100001010010011101101000110110000011111011110000010100001001000011001011011011011001111110101111001010011011100010011110101100100101111001011100011110111101001010000000100100000111100101100100100000100110001111110011100110101000110100011001110110000110111111010111000001101110011001101111010110101000101011110111001011001111111000100100100011100100010101001100111011101111100110101011101101001001110010111011010011111001100001111111100001000001101101000001010100110011001101000101001010001001011000010111111100101111000000101000010110100110101001001100100011000111101000110011110101101111100110101010101000000001110010101001001111101001010111011110110001100101001111110111000110101011011010110101100011110010000011000110010111101010010000011101110111100011011110110001111010101011101100101101001111100100011000100101111011110001111100000110111000111111000111100000110011011011111110011111100010010110000010011100001010101011011101100011001100101100011001010010001101010011000000011110110111000000110001010010111110101011100000010100100001101011010101100110000101100010001010010111011000100001000001001110101011000010111000000010101100001010000010110110000111100011011000010111001111101110111010110000011001011101100000100000100010100100000010011010000111110010001111010000100011110000101111000110100010110101110001011101101100111000001110100100000000010011001110101110000001101100000001010111010011111000101101011001010011001101000111000010111111010101000011011001001110000011100100100010110101100001110110111001000001011111100101100011010010010110000011110100110000111011011010101110101001100110100101100101000100011001011000001011110010000011000110111011110011010001101100010010111110101101101110100111010000001101000011011010011110111101000000100011000000101001000000011010101010000100001110110000110011000111101011100100101111101111111110101000011010001101100010010100111000000010000101100100110101000001001011100011111001101001101100010100000111010101111011101111111101100000010000111110011101010100101110100101010100011110100100000111010001000100011010011100010011000001110110100110110010100100110111011001010010010100000110101110000011110010110100010101000110000111101011011010111101100111100101001101001101100111101000100101101100010111010010111100100111101101110101110011010110011111011111010000011000100010010101110001001000111111100100010100000001001010111010100010111001011011101110010110111110110100011111101110111011000111001010010110001001011011100110101111100100000101110000001011110011101110101101001011111100011001100111001011011001011011101000101100100011101000011101011010110010111111010011110111111111100001101101001101101111000100110010010100000100000100110100100110010000100101100000101010101000111110101001111111011011111101101110010100110000010110111001101110011101100001111111001110110010010011101111100111111000010011010010011100000001010011111111110001111110110110110001001001111011001101110110101100011010001111110010001011010000011110101100110010010001110010100010000000010101010010111011010101011011000010010011010110101101011100100101110001100000111110010101100010100010100010000101111000011111000111000011110001110110000011000100110010101111111111100011010000010010010111111110000000010100100101101101010111011000001010000000101011010110011101000110011011001110101101001001101100010011110001101001001000011001101100001101100000101111000001110100001100001000100000000011010011001001011110011000011011000100011011001011100111111000011011010000100000011110110011011110111000001011101101110110101000101011111110000100000111111110011111111100010101001000011010001110111111011100010111001110110001000101010001001001111111110111001101001001000110000110100000000010010100001010111101001110001011101011000100000001001001011111000100011111000011010001110001111111110111100010001110101011101011100010100000011110000100011001100000100111000111011011101000110010011010011110010010000111010001011111111010110011100111011110100111000101100100111001001010001000100011110101100100010000000000110010111101101111101011001101111000000000100000101001011110000010011110011000000100111001001110001000010011111010100001001010010100111111010111001001110110101010010100010010100101100000001010010111101101000110100111110000000111110000011110011001101010111101010111010111010000000110010001011110101110110001000110111101110101101001001100001101110001000100000110100000100000111110010110110010011111100010011111001110111011010101010001011111110000000011110001010011001101010110010101100101100110010111001100100111101000100010100010010100000010010111101100111110101101111101001010110010001111111001101010111110101111001000111101001110100000111111010000111000010101001001101100111001111111111100011010111110001101000100001010000000001101101001110001000001110010000010110001001001101010111111001001010100011011111011000011001001101000110010101000010100001001000011111001101101111011111001000010010111011010110010011010101100100000101100110110011011110000110011000000001011000111100101000011011011010010111000110101110101111100100010101010101000011000111000010001001000100110101111001001001111100110000101100010011101100001000010100010101110001111110101100101000101110000110010100101100101100101100100111111010100101010011100110100011111001000100010001101111111101011110100111001110101001101000010001011000111101110001010100101101111000110101001011101110110110110110101011010001110011111011110011010100110100111111010101111101111100110000110010111110110100110000011110110111111101111010011010000101010111100001111110110000001000001000011101001010010100100100000001101011101110011001011011110010111101111101010011010000110110101000100010110110101101010110110010011010011111111100001001000110111101001111000011001000010111100110001110110011011011100101011010101100011001111111000100000011100110011001001011000100010110000100001100011010000110110011100000111000010001011010001110010101000100010001001110001011001010000111010010101110001010100011101101110010111100010110010000011010111001101000100111011010100001010011100000100001010100010110100111000000001111100000100011100101011011101111111101101110011111010000110111101000001001110111000001000101100110100100111100100011011100010011111101010001101010100101110000110011000100001111100100001000000100011101101011011111000011110010110110101010011101000001111001011100101001001101111000011110000001010011010001110000111001101100011110011001100000111101001011000110111011001101101101100101100110100101011111111110110000111101000000100101011100111001111111011010100110010001000001101010001110010010000101111000001010100000101100000010101110100000000110011001011000011101101000000100111111010111110100011111101100001001110001100101100001010000100000110111101001101010000011100000000100000101101010010101111101100110110111000011100111001010010100101000111011001001110011111100010010010110100111101100110110111001011110010000111011111010101000010001101110011111010110011100010001111111011100110100011110110001101001110001010001110011110101111101011101100000111011011101110000110111101010001000011110011011101100011100101110100000100010110110011010101011000010010110000000100010011001110010011110010110111001111011010101111011000000111110000011011100100010011110010110000001111110111000100111010100110010111100010000110101011110011010110011001011011010010111001000000000001001010101010001100000110111101000000010100100010100101011111110011011100111101001110101010001100000100100110111110001111000011100010110001101101010011001011111101011000110110000111111101100000000001000010010010011101001000111100000010111011011001001100110000101010110001011000001011010111000111100111011010101010011100100100100010000001101001101010111110010100101000001100111110111111110000101111100110001110111010111001111110111100000111011011010111011001111010100010000111011111111000100110110001100000110101000001010010010100111011100000011111110001000010011010101001111010111100011110110110111000000111101010110001100000100001101101001101010111110001101101100101101101001000100000100110111111010011010011111010110110111101001000100010111101100011010111011111010011110000100001100101101111110010101000000101111101000001111110100000001011011111111100100110101101011100101101001011010001100010101101100000101000001110110101010100001011100010000111010011101110000000010000000000010111100111000010000000110110011011101110000001111011100011101111100011000011001000100111010101011010101110011010011011011010100011011000110111101001110011110000100010011000010000001101010010011000111000000000101100011010001000100010100100100011000101110100010001111101001010100001000000110010011101011101000000100010000011010110100111110101110001111001000000101011101010111110110100100011010000011010111111001001111101101110111110111000001010111100010001001001100000000110011100001100100111010011111011001010001101111111000010110101000011100001010110100101110111001001100000000110110101011001110000011001111100001101110100101101111100110001010011011001010110111000100010000110001111101110011100001101000100110000111000110001011011110100010101011011001001111101001110011100001110001010100011001110110101101001101010101001110011110001011101011100100001101100110110110101011101010110011100000001011010111011101000000101110111110010000000000101001110011111011001110001100010111001010010110011100001000011111101111101100111000101011100011000001100000000000010000111111010010101110101011100010100001000000100111111010111110010010111010110010100111000010111100000000100010111010010011010011001100010001000001100110100101110100110110111101010001100001010011111011100000010110110110000000100101100110100101100111001010100010001011010001010011110100110101000110001110000100111111001000110011110010111000110010001111111111101011110100111101001001101110110011111000110010111000011011111001110101101101000011010101011010111101011101111011100101001111111000101100100000011000100101001011001011110001101001100101001'

def work(n, key):
    array_1 = []
    for i in range(n):
        for j in range(n):
            array_1.append(int(key[i + j]))
    A = matrix(GF(2), n, n, array_1)
    array_2 = []
    for i in range(n):
        array_2.append(int(key[i + n]))
    B = matrix(GF(2), n, 1, array_2)
    try:
        c = A.solve_right(B)
        return c
    except:
        return None

for n in range(2, 100):
    c = work(n = n, key = output)
    if len(c) == 100:
        break

tmp = ''
for x in c[::-1]:
	tmp += str(x[0])

flag = 'flag{' + str(int(tmp, 2)) + '}'

print(flag)
# flag{856137228707110492246853478448}

rsa

题目描述如下：

小明经过研究，发现RSA加密算法可以推广，也就是它的模不仅仅是只能为两个素数的乘积，只要是2个以上不同的素数相乘都可以。

根据题目和描述，这个题是一个多质数的RSA（multi-prime RSA）

给出的文件 cipher.txt 很简单，就只有n,e,c

n = 50142032499469550407421604706771611415193641755639270667473328045908799316205905505167271138079522738272643811917325451177986948493659090203974349370248583120022500722759239305447823602875823849366662503027591858371125301505134216095903796534740686834236150999
e = 65537
c = 45005399504992587510006608300548120810512973768886391125598523343330913326304417790989607300367232977960116381108873363343598357102136548218343380795022179607741940866191404186680657699739176842869814452906110393321567314747096161480003824583613027819960172221

显然，这个题我们只有分解n，因为e是安全的，同时没有额外的信息，能利用的仅仅就是n有多个因数。

那么，二话不说，暴力分解走起。

遗憾的是，在线查找和yafu分解都失败了。yafu跑了好久都没有出来。

于是，我又尝试，自己手动来，从小质数开始枚举，一直枚举到了第100000*70个质数，还是没有成功枚举到一个因子。

这说明，这个n是没有小质因数的。

同时他又有多个质因数。

猜测1：因此他的各个质因数的差距应该不大。

然后，我开始Google，毕竟我坚信这个是一种我没见过的新题型。看了好多英文论文，但是感觉写得都很垃圾。（我英文垃圾，时间又很紧迫） 各个论文都证明了半天，但是我感觉没啥用。倒是Google的搜索结果中，针对这种multi-prime RSA的攻击基本上都是基于他的质因数差异比较小来进行的。 这更加坚定了我的猜测1。

于是，借鉴普通RSA问题中，p和q太接近时的费马分解法的思路

由于n = p * q,当p和q的差距太小时，这意味着p和q都会在 n^1/2 附近。由于差距较小，所以我们可以在这个差距范围内进行枚举，进而实现对n的分解。

我局得这个多因数的也是可以用类似的手法进行攻击的。

于是我枚举根次，从3枚举到20，每个附近的差异我定义为10亿。

代码如下：

import gmpy2

n = gmpy2.mpz(50142032499469550407421604706771611415193641755639270667473328045908799316205905505167271138079522738272643811917325451177986948493659090203974349370248583120022500722759239305447823602875823849366662503027591858371125301505134216095903796534740686834236150999)

# 猜测的差异范围
tot = 1000000000

for num in range(3, 21):
    
    p0 = gmpy2.iroot(n, num)[0]
    
    for i in range(tot):
        if n % (p0 + i) == 0:
            print(p0 + i)
            break
        if n % (p0 - i) == 0:
            print(p0 - i)
            break

很可惜，我没有跑出来它的因数，于是我又扩大了范围从20~100.

终于跑完了之后，我还是没有得到解。

于是我又扎进了寻找论文和Google方法中，因为我坚信，这是一类有其他方法一瞬得到结果的。

很遗憾，我没有在规定时间内拿到flag

赛后，我从同学哪里得知，开3次方根，将范围改到 2³⁰ 次方就可以爆破出来。

于是，新的代码如下

import gmpy2
from time import time

n = gmpy2.mpz(50142032499469550407421604706771611415193641755639270667473328045908799316205905505167271138079522738272643811917325451177986948493659090203974349370248583120022500722759239305447823602875823849366662503027591858371125301505134216095903796534740686834236150999)

p0 = gmpy2.iroot(n, 3)[0]

tot = 1 << 30

start = time()

for i in range(tot):
	if n % (p0 + i) == 0:
		print(p0 + i)
		break
	if n % (p0 - i) == 0:
		print(p0 - i)
		break

end = time()

print(f"用时：{end - start} s")

我计了一个时，442秒，就成功爆破出了n的一个质因数，后面就简单了，直接yafu分解剩下的部分，然后就可以得到flag。

flag{4e9f2a7f-bda9-4a46-af51-b29e0c61973e}

我算了算，2³⁰ - 10⁹ = 73741824，原来我离AK，甚至一血只差了73741824。

谨以此，已备忘。

参考链接：

• https://nonuplebroken.com/2020/06/10/%E5%8F%8D%E9%A6%88%E7%A7%BB%E4%BD%8D%E5%AF%84%E5%AD%98%E5%99%A8/#%E5%8F%8D%E9%A6%88%E7%A7%BB%E4%BD%8D%E5%AF%84%E5%AD%98%E5%99%A8