Convert CVP to SVP – Embedding Technique

例题:中科大2021Hackergame 灯

题目给了以下规则:

游戏目标是使得各方块亮度尽可能接近给定图案:


所以我们的任务是解出每个块的点按次数

触碰方块会提升附近方块的亮度, 不同关卡中亮度增加幅度可能有所差别;方块的亮度范围为[0, 255], 当某个方块的亮度达到 256 时会归零;2-3关卡中会存在禁止触碰的方块,在详细数据中会以红色勾勒出来;当前局面的分值为各方块亮度与目标图案对应方块的亮度之差的绝对值之和;当分值降至目标分数时, 可点击标题按钮获取关卡对应的 FLAG。

​ 我们将每个方块从0到143编号,设每个方块的点按次数为x_i组成点按向量\pmb x,点按每个方块所产生的影响(对附近方块亮度的改变量)向量为\pmb a_i构成矩阵A,最终目标图像对应的向量为\pmb b。模数p为256

第一问很简单,没有禁止点按的方块,列方程:
A \pmb x=\pmb b \pmod p
我们可以直接解模矩阵方程得到\pmb x(见附录1)。

​ 第二问和第三问给了禁止点按的方块,此时我们只能操作其他方块,使最终误差小于给定的值:我们要找到一个 足够接近目标向量\pmb b 的 可以由 没被禁止的\pmb a_i(下文记为\pmb a’_i,组成矩阵A’)的线性组合表示 的向量t
A’ \pmb x=\pmb t \pmod p
去掉\mod p,继续化简
\pmb k pI+A’\pmb x=\pmb t\\\left[ \begin{array}{c|c}pI& A’ \end{array} \right]\begin{bmatrix} \pmb k\\\pmb x\end{bmatrix}=\pmb t\\\left[ \begin{array}{c|c}\pmb k&\pmb x \end{array} \right]\begin{bmatrix} pI\\A’^T \end{bmatrix}=\pmb t^T
​ 其中,I是单位矩阵,下文记M=\begin{bmatrix} pI\\A’^T \end{bmatrix}中的行向量为\pmb m_i。最后全部转置了一下(一个原因是sage中的vector是反人类横着的)

​ 也就是说,\pmb m_i张成了格\Lambda\pmb b不在\Lambda上,求与\pmb b最接近的向量\pmb t,这就是CVP(Closest Vector Problem)问题。

​ 而利用Embedding Technique,CVP问题又可以转化为SVP问题:

我们定义:
\pmb \delta^T=(\pmb b-\pmb t)^T=\pmb b^T-\left[ \begin{array}{c|c}\pmb k&\pmb x \end{array} \right]M
上式中||\pmb \delta||很小。

​ Embedding Technique的想法是:定义一个包含了向量\pmb \delta的格 L,且L要比\Lambda多一维。多出来的一维是由(\pmb \delta,e)

张成的。这样(\pmb b,e)也在L中,它也可以成为L的某一组基中的一个。由于||\pmb \delta||很小,我们可以利用格规约算法 (比如LLL或BKZ) 从包含(\pmb b,e)的一组基 规约成 包含(\pmb \delta,e)的基,\pmb \delta就是L的SVP。

​ 我们构造L的基B_L就是在M的基础上添一维,再添加向量(\pmb b,e)
B_L=\left[ \begin{array}{c|c} pI&0\\A’^T&0\\\hline \pmb b^T&e \end{array} \right]
我们规约B_L,得到:
B’_L=\left[ \begin{array}{c|c} …&0\\…&0\\\hline \pmb \delta^T&e \end{array} \right]
于是最终可以计算出\pmb t
\pmb t=\pmb b-\pmb \delta
带回A’\pmb x=\pmb t \pmod p解方程即可。

附录1

1.1第一问

from sage.all import *
delta=[[-1,0,2],[1,0,2],[0,-1,2],[0,1,2],[-2,0,1],[2,0,1],[0,-2,1],[0,2,1]]
target=[
        189,189,189,189,189,33,33,33,189,189,189,189,
        189,189,189,33,33,33,189,33,44,189,189,189,
        189,189,189,189,189,33,33,33,33,189,189,189,
        189,189,189,189,189,33,189,33,33,189,189,189,
        189,189,189,33,33,189,189,33,33,33,189,189,
        189,134,33,33,189,189,189,189,33,33,189,189,
        189,144,33,33,189,189,189,189,33,189,189,189,
        189,142,33,33,189,189,189,189,33,33,33,189,
        189,100,142,33,189,189,189,189,33,33,33,189,
        189,142,142,189,189,189,189,189,189,33,189,189,
        189,59,142,33,189,189,189,189,33,189,189,189,
        189,189,33,33,189,189,189,189,189,189,189,189]
basis=[]
for i in range(144):
    t=[0]*144
    t[i]=3
    for j in range(8):
        x=i%12+delta[j][0]
        y=i//12+delta[j][1]
        pos=x+y*12
        if(x>=0 and x<12 and y>=0 and y<12 and pos>=0 and pos<144):
            t[pos]=delta[j][2]
    basis.append(t)
basis=Matrix(Zmod(256),basis)

ans=basis.inverse()*Matrix(Zmod(256),target).transpose()
print(vector(ans))

1.2第二和第三问

from sage.all import *
delta=[[-1,0,2],[1,0,2],[0,-1,2],[0,1,2],
          [-2,0,1],[2,0,1],[0,-2,1],[0,2,1]]
banned=[26,28,38,39,40,50,52,79,80,81,91,103,105,115,116,117]
target=[
        189,189,189,189,189,33,33,33,189,189,189,189,
        189,189,189,33,33,33,189,33,44,189,189,189,
        189,189,189,189,189,33,33,33,33,189,189,189,
        189,189,189,189,189,33,189,33,33,189,189,189,
        189,189,189,33,33,189,189,33,33,33,189,189,
        189,134,33,33,189,189,189,189,33,33,189,189,
        189,144,33,33,189,189,189,189,33,189,189,189,
        189,142,33,33,189,189,189,189,33,33,33,189,
        189,100,142,33,189,189,189,189,33,33,33,189,
        189,142,142,189,189,189,189,189,189,33,189,189,
        189,59,142,33,189,189,189,189,33,189,189,189,
        189,189,33,33,189,189,189,189,189,189,189,189,1]
basis=[]
for i in range(144):
    t=[0]*145
    t[i]=256
    basis.append(t)
for i in range(144):
    t=[0]*145
    if(i not in banned):
        t[i]=3
        for j in range(8):
            x=i%12+delta[j][0]
            y=i//12+delta[j][1]
            pos=x+y*12
            if(x>=0 and x<12 and y>=0 and y<12 and pos>=0 and pos<144):
                t[pos]=delta[j][2]
    basis.append(t)
basis.append(target)

L=Matrix(ZZ,basis)
L=L.LLL()
ans=Matrix(Zmod(256),Matrix(target)-Matrix(L[288]))

target=ans[0][:144]
newbasis=[]
for i in range(144):
    t=[0]*144
    t[i]=3
    for j in range(8):
        x=i%12+delta[j][0]
        y=i//12+delta[j][1]
        pos=x+y*12
        if(x>=0 and x<12 and y>=0 and y<12 and pos>=0 and pos<144):
            t[pos]=delta[j][2]
    newbasis.append(t)
newbasis=Matrix(Zmod(256),basis)

finalans=newbasis.inverse()*Matrix(Zmod(256),target).transpose()
print(vector(finalans))

第三问只需仔细的把deltabanned改一下就行了(做第三问的时候因为delta写错了,查了半天)

附录2

自动化点击程序

from pymouse import PyMouse
ans=[]
for i in range(144):
    x=i%12
    y=i//12
    PyMouse().click(int(140+45*x), int(285+45*y), 1 ,ans[i])
    print(x,y,ans[i])

参考文献

Lattice problem:https://en.wikipedia.org/wiki/Lattice_problem

格基规约相关 by Coinc1dens:http://coinc1dens.me/2020/02/27/%E6%A0%BC%E7%9B%B8%E5%85%B3-0.0.1.html

Steven Galbraith Mathematics of Public Key Cryptography Part IV: Lattices:https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇