[nsucrypto] Non-linear hiding

因为一次偶然机会做了一下nsucrypto round 2 的第五题。

题目

数据在这里获取

起初刚看到这道题时，认为只是个GF(2)上的solve_right问题，将所有的x构成一个n*40矩阵，乘以一个40*1矩阵，能够得到y，当x矩阵满秩时，而这个40*1矩阵有且仅有一个汉明重量为20的解，即为我们希望的解。

然而并不是这么简单，直接这么解是无解的。仔细看题会发现，40个x给的是S上的元素，从F₂⁵到S上的映射为一个secret bijective，意味着我们得不到这张映射表，结合上题目名的non-linear hiding，很明显，意思是我们需要先求出这个映射表才能继续做下去。

困难点

若仅仅只是不给映射表，通过解方程组，很容易解出映射表。但是问题是这40个x还仅仅只取了20个进行操作，导致若问题表示为n*40矩阵乘以40*1向量，则这个问题被转化为了一个有72个未知数的二次非线性方程(32个字母加上40个0/1)。

整体思路

非线性方程是我们不想看到的，所以我们先不去考虑40*1的选择矩阵，而去考虑n*41的增广矩阵，其中，左边40列为x组成的矩阵，组成元素为S中的元素；最右边一列为y向量，组成元素为F₂⁵的元素。

我们并不知道S中元素相互异或的结果，但我们知道两个相同的元素，异或为0，S中所有元素异或的结果也为0。所以我们的入手点就在这。如果我们可以通过一些行向量的线性组合，得到一些前39列均为0的矩阵行，那么假如y列不为0,那么我们可以得到第40列一定被选取，并且第40列 == y列，从而得到很多条方程，解出映射表，从而回到最初的solveright问题。若y列为0,说明该列不被选取，往前找倒最后一个令y不为0的列即可。

数据结构

在消去第一列的元素时，第一列会变为0,而剩下的列会是一些元素的异或，因为我们不知道这些异或的结果，无法写成一个数。随着消去过程逐渐进行，后面的列的位会是相当多S中元素异或的结果。

最直观的方法(我最初的想法)是直接用字符串或是字符列表来表示，但这样会导致这些元素在异或时，需要遍历所有的位，来进行删除或是添加。导致大量的时间消耗。

因此我们可以才用一个32位int来表示，将字母k表示为2**table.index(k)，table为S中所有元素集合。字母k与字母m的异或则可以写成2**table.index(k) ^ 2**table.index(m)。使用这样的数据结构，可以让元素异或时直接将对应的32位int异或即可得到结果，并且0就代表0，能够获得更高的效率。

寻求能消去的位

这是这个问题最重要的一点，直观来看，我们将一些第一维相等的向量相互异或能够得到一些第一维为0的向量，但是这样的向量个数肯定是比最初的少的，如果说向量个数下降速度很快那么这题就需要大量的数据以及计算量，无法解决。比如若一次会将向量数除以2,则总共需要2**39的数据与计算量才能够解决，这显然是不可能的。但如果一次只是将向量数减k，那么只要39*k的数据与计算量即可。题目给了6432位数据。除以5为1286,只要k不大即可。

确定下降速度为第一种还是第二种，先分析如何去寻找这些消去的位。

用枚举的方法能够求第一维的结果，因为第一次所有的元素都只有一位是1,所以很容易找到，但是后面的就会有多位是1,所以就没办法直接枚举了。所以我们可以用矩阵来求解。

设某一列x = (m₁, m₂, m₃, ...,m_k)^T

这里 \[ m_i = \Sigma^{32}_{j=0}2^jc_{i,j} \] 其中，\(c_{i,j}\)为0或1.

我们想要找一个向量v使得vx = 0

也就是 \[ \Sigma^k_{i=0} (v[i]\Sigma^{32}_{j=0}2^jc_{j,i}) = 0 \] 将2^j提出，可以得到 \[ \Sigma^{32}_{j=0} (2^j\Sigma^{k}_{i=0}v[i]c_{j,i}) = 0 \] 由于每一位都必须为0,所以我们可以，得到32条方程： \[ \Sigma^{k}_{i=0}v[i]c_{j,i} = 0 (j = 0,1,...,31) \] 设矩阵\(M = \{c_{j,i}\}\),是一个32*k维矩阵，有 \[ Mv = 0 \] 也就是将问题转化为求齐次线性方程组的通解问题。将M化为行阶梯型，写出所有的通解即可。v的数量为k - M.rank()。M的阶至多为32,在k大的情况下极大概率为32.所以下降速度为第二种情况，并不算太大，可以求解。

代码实现：

def getzero(vec):
    M = Matrix(GF(2) , 32 , len(vec))
    for i in range(len(vec)):
        temp = vec[i]
        for j in range(32):
            if temp %2 == 1:
                M[j,i] = 1
            temp //= 2
    tempM = M
    M = M.rref() #行阶梯型
    resvec = []
    one_position = []
    for i in range(32):
        for j in range(len(vec)):
            if M[i , j] == 1:
                one_position.append(j)
                break
        else:
            break
    for i in range(len(vec)):
        tempv = vector(GF(2) , len(vec))
        if i in one_position:
            continue
        tempv[i] = 1
        for j in range(32):
            if M[j , i] == 1:
                tempv[one_position[j]] = 1
        resvec.append(tempv)
    res = resvec
    return res

这一段是问题的核心，剩下的就是一些边边角角的补充了。

迭代过程

得到向量后，需要对原本的x进行更新

也就是使用所有的向量，对剩余的x和y更新一次。这里是主要的时间花费地方，需要对40列，每一列的k维遍历k-32次。

即需要计算40*(k-32)k，k在最开始能够达到1200左右，则我们第一次需要计算5kw次以上。

def apply_vec(ms,vecs):
    newlist = []
    for m in ms:
        templist = []
        for v in vecs:
            temp = 0
            for i in range(len(v)):
                if v[i] == 1:
                    temp ^= m[i]
            templist.append(temp)
        newlist.append(templist)
    return newlist
def apply_y(y,vecs):
    res = []
    for v in vecs:
        temp = 0
        for j in range(len(v)):
            if v[j] == 1:
                temp ^= y[j]
        res.append(temp)
    return res

主函数

首先我们需要先确定数据量，由于我们需要39次消去过程，每次减去32个位，为最后一次仍有足够的信息去得到映射表，我们需要3932+ 32 = 1280，恰好y给了6432位 = 1280 5 + 32。将数据进行预处理后直接调用函数迭代即可

def tolist(y):
    res = []
    for i in range(1280):
        temp = 0
        for j in range(5):
            temp <<=1
            temp += int(y[i*5+j])
        res.append(temp)
    return res
y = tolist(y)
ms = []
size = 64
for i in xs:
    temp = [[j] for j in i[:1280]]
    ms.append(temp)
for i in range(39):
    vecs = getzero(ms[0])
    
    y1 = apply_y(y , vecs)
    print(y1[:64])
    for i in y1:
        if i != 0:
            y = y1
            break
    else:
        print('y is zero')
        break
    ms = ms[1:]
    print(len(vecs))
    ms = apply_vec(ms , vecs)
print(y)

print(ms[0])

最后的结果即为最后一个选取的列，与y。这里我们得到的结果是最后一个选取的列为倒数第三列，最后两列不被选取。因此我们会有60多条方程，足够我们计算出映射表。

y = 
m = 
table = '0123456789abcdefghijklmnopqrstuy'
def getzero(m , c):
    M = Matrix(GF(2) , len(m) , 32)
    for i in range(len(m)):
        temp = m[i]
        for j in range(32):
            if temp %2 == 1:
                M[i,j] = 1
            temp //= 2
    v = vector(GF(2) , len(m))
    for i in range(len(y)):
        v[i] = y[i]%2
    return M.solve_right(v)

dic = {}
for i in range(32):
    dic[table[i]] = 0
for i in range(5):
    temp = getzero(m , y)
    for j in range(32):
        dic[table[j]] += int(temp[j]) * 2**i
    y = [x >> 1 for x in y]
print(dic)

这里可以用GF(2^5)上的矩阵来一步求出映射表，但由于写出这上面的元素过于麻烦，于是才用GF(2)矩阵求五次，一样的效果。

获得映射表

{'0': 4, '1': 25, '2': 1, '3': 14, '4': 27, '5': 6, '6': 31, '7': 10, '8': 17, '9': 11, 'a': 15, 'b': 18, 'c': 16, 'd': 26, 'e': 23, 'f': 3, 'g': 13, 'h': 20, 'i': 8, 'j': 9, 'k': 29, 'l': 19, 'm': 30, 'n': 28, 'o': 12, 'p': 7, 'q': 2, 'r': 5, 's': 21, 't': 24, 'u': 22, 'y': 0}

最后得到答案

from sage.all import *
y = 
xs = 
dic = {'0': 4, '1': 25, '2': 1, '3': 14, '4': 27, '5': 6, '6': 31, '7': 10, '8': 17, '9': 11, 'a': 15, 'b': 18, 'c': 16, 'd': 26, 'e': 23, 'f': 3, 'g': 13, 'h': 20, 'i': 8, 'j': 9, 'k': 29, 'l': 19, 'm': 30, 'n': 28, 'o': 12, 'p': 7, 'q': 2, 'r': 5, 's': 21, 't': 24, 'u': 22, 'y': 0}
ms = []
for i in range(40):
    temp = ''
    for j in xs[i]:
        temp += bin(dic[j])[2:].rjust(5 , '0')
    ms.append(temp)
M = Matrix(GF(2) , 6000 , 40)
for i in range(40):
    for j in range(6000):
        M[j ,i] = int(ms[i][j])
v = vector(GF(2) , 6000)
for i in range(6000):
    v[i] = int(y[i])
choose = M.solve_right(v)
ms = 0
for i in range(40):
    if choose[i] == 1:
        temp = 0
        for j in xs[i]:
            temp <<= 5
            temp += dic[j]
        ms ^= temp
print(bin(ms))
ans = []
for i in range(40):
    if choose[i] == 1:
        ans.append(i)
print(ans)

总结

总得来讲是一道很有趣的题目，主要还是将一个非线性方程，利用线性的性质进行求解，通过仅有的一个单射条件从非线性的结构中找到一些线性的部分，从而解出整道题。

但实际上，这道题给的条件并不是单射，而是双射，双射除此之外还能找到一个整体性质，也就是 \[ \Sigma_{i=0}^{32}S[i] = 0 \] 但这道题中并没有用到这个性质，给的条件过强了，如果说以后有机会再研究研究说不定也能通过这个性质出道题啥的。