[tangcuxiaojkuai]easy_mod

Problem: [tangcuxiaojkuai]easy_mod

[[toc]]

思路

可以看到m的特殊性在于：除了NSSCTF{}组成的前后缀以外，仅由0-7的数字拼接而成，一共有70个数字。

那么思路首先肯定是把前后缀给去掉，从而减小明文数量级。由字节转数字的方式可以知道m其实可以写成如下形式(其中pre指"NSSCTF{"，suf指"}"，m0就是中间的长为70数字串)：

m = 256^{71}pre + 256m_0 + suf

那么就有：

c = (256^{71}pre + 256m_0 + suf) \quad(mod\;p)

就可以得到m0模p的值：

m_0 = 256^{-1}(c - 256^{71}pre - suf) \quad(mod\;p)

接下来的问题是如何利用m0的特殊性去求解他，由于m0仅由0-7的数字组成，用ASCII码的角度去看就是48-53，所以一个很自然的思路是把m0写成如下形式(记m0的每个字节值为si)：

m_0 = \sum_{i=0}^{69}256^is_i =s_0 + 256s_1 + 256^2s^2 + ... + 256^{69}s^{69} \quad (mod\;p)

那么可以写成一个等式即：

m_0 = \sum_{i=0}^{69}256^is_i + kp

这个等式就给造格提供了一个依据，可以造出如下格：

\left(\begin{matrix} 1 &&& &&1\\ &1&& &&256\\ &&\ddots& &&\vdots\\ &&&1 &&256^{69}\\ &&& &1&-m_0\\ &&& &&p\\ \end{matrix}\right)

具有的线性关系是：

(s_0,s_1,...,s_{69},1,k) \left(\begin{matrix} 1 &&& &&1\\ &1&& &&256\\ &&\ddots& &&\vdots\\ &&&1 &&256^{69}\\ &&& &1&-m_0\\ &&& &&p\\ \end{matrix}\right) = (s_0,s_1,...,s_{69},1,0)

那么如果界符合的话，用这个等式去造格，规约出来的向量预期应该是由48-53的一系列值组成的短向量，但一做就知道这样并不能得到预期结果。

然后一个朴素的优化想法就是，不妨新令一组变量：

t_i = s_i - 48

那么就可以将刚才的等式做如下处理：

m_0 = \sum_{i=0}^{69}256^i(t_i+48) \quad(mod\;p)

那么减去48(也就是0对应的ASCII码值)之后，预期规约出的向量就都变成了0-7的短向量，机会就大很多。并且由于48与256^i的乘积都可以计算，所以可以仅处理上面格中的m0项而不需要改动其他地方，也就是：

m_1 = m_0 - 48\sum_{i=0}^{69}256^i

此时造格的等式为：

m_1 = \sum_{i=0}^{69}256^it_i + kp

然后是做一些老生常谈的使格规约本身更有利的一些优化，比如说，现在目标向量为：

(t_0,t_1,...,t_{69},1,0)

为了保证规约出0，就要给格的最后一列配上个大系数。同时，ti的取值为0-7，也就是说平均值在3、4左右，因此给倒数第二列配上个3、4能使目标向量中值的数量级更加接近。

EXP

exp：


from Crypto.Util.number import *


p = 501785758961383005891491265699612686883993041794260611346802080899615437298977076093878384543577171
c = 327005346153237517234971706274055111857447948791422192829214537757745905845319188257204611848165263
prefix = b"NSSCTF{"
suffix = b"}"
length = 78 - len(prefix) - len(suffix)

#part1 remove prefix and suffix
c -= 256^(len(suffix) + length) * bytes_to_long(prefix)
c -= bytes_to_long(suffix)
c = c * inverse(256,p) % p

L = Matrix(ZZ,length+2,length+2)
for i in range(length):
    L[i,i] = 1
    L[i,-1] = 256^i
    c -= 256^i*48

L[-2,-2] = 4
L[-2,-1] = -c
L[-1,-1] = p
L[:,-1:] *= p
res = L.BKZ()
flag = ""
for i in res[:-1]:
    if(abs(i[-2]) == 4 and all(abs(j) < 8 for j in i[:-2])):
        for j in i[:-2][::-1]:
            flag += chr(48 + abs(j))
print(flag)


#NSSCTF{5036541772751046406531362142757356307107252723754051320011253505562041}