25Jan1

huangx607087 1月的切题1(NTRU Note 1)

0.Introduction

自从从贵州回来之后，就持续红温了45天，又是课程论文又是pre的，做了3个ppt，3个课程论文，5场考试，中途打了个CISCN。两门背诵的课搞了我15天，对我这种背书不行的家伙来说真的很难顶。。。

1 月 9 日11:00，终于考完了，反正能过。不得不说 12 月 5 号的密码学考试，不仅全是本科的知识，还比我本科密码学考得东西简单多了，大作业 5 个模块（AES,DES,MD5,SHA1,RSA），我本科全通过自定义代码写过，封装个GUI，三天光速完成，最后直接毫无压力地规格化 94 拿下它！

CTF，启动！竞赛，启动！

1.[2024强网杯决赛]fak1

1x01 题目大意

一个NTRU题目，先看眼题目：

from sage.all import *
from Crypto.Util.number import long_to_bytes
import os
import signal
from datetime import datetime

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 60
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

load("ntru.sage")
p,n,q,dg,df = 3,117,1091,35,37


cs = []
def Game():
    while True:
        pk,sk = genKeys()
        try:
            1 / pk
            print(pk.list())
            break
        except:
            pass
                
    secret = os.urandom(23)
    secretPoly = MsgtoPoly(secret)
    print("Welcome to fak1. You can send some message to me. Have fun!")
    msgs = [[0 for _ in range(116)]]

    for _ in range(10):
        msg = [round(int(i,16) % 3329) for i in input("Give me a list of message (hex):").split(" ")]
        if len(msg) != 116 or (msg in msgs):
            print("You bad!")
            return
        msgs.append(msg)
        m = secretPoly + QR([round(i / 3329 * q) for i in msg])
        c = encrypt(pk,m)
        try:
            assert m == decrypt(sk,c)
        except:
            print("You bad!!")
            return
        print(c.list())

    if long_to_bytes(int(input("You wanner say something? :"), 16)) == secret:
        print('flag{Success at :'+str(datetime.now())+'}')
        print("You good!")
    else:
        print("OK, bye bye~") 

Game()

其中：

#ntru.sage
import random
from Crypto.Util.number import bytes_to_long,long_to_bytes

p,n,q,dg,df = 3,117,1091,35,37
R.<x> = PolynomialRing(Zmod(q))
RR.<xx> = PolynomialRing(Zmod(p))
QR = R.quotient(x ^ n + 1)
QRR = RR.quotient(xx ^ n + 1)
flag = b"flag{*******************************************}"

def balancemodlist(List,p):
    for i in range(len(List)):
        if int(List[i]) > p / 2:
            List[i] = int(List[i]) - p
    return List

def randomPoly(d = 0):
    if d == 0:
        poly = QR([random.randint(0,1) for _ in range(n)])
    else:
        L_0 = [0] * (n - 2 * d - 1)
        L_1 = (d + 1) * [1]
        L_2 = d * [-1]
        L = L_0 + L_1 + L_2
        for i in range(randint(5,10)):
            random.shuffle(L)
        poly = QR(L)
    return poly

def genPrivKey():
    while True:
        poly = randomPoly(df)
        try:
            poly_q = (1 / QR(poly))
            poly_p = (1 / QRR(RR(balancemodlist(poly.list(),q))))   
            break
        except:
            pass
    return poly, poly_q, poly_p

def MsgtoPoly(msg):
    msg = Integer(bytes_to_long(msg))
    m = msg.digits(p)
    for i in range(len(m)):
        if m[i] > p / 2:
            m[i] -= p
    return QR(m)

def genKeys():
    f, f_q, f_p = genPrivKey()
    g = randomPoly(dg)
    pk = QR(p * g * f_q)
    sk = (f,f_q,f_p,g)
    return pk,sk

def encrypt(pk, m):
    r = randomPoly()
    return pk * r + m

def decrypt(sk,c):
    f,_,f_p,_ = sk
    m = QR(balancemodlist((QRR(balancemodlist((f * c).list(),q)) * f_p).list(),p))
    return m

1x02 题目分析

先回顾一下NTRU加密过程：产生私钥 $f(x)\in T(d_f,d_f-1)$，其中 $T(d_1,d_2)$ 表示具有 $d_1$ 个系数为 $1$，$d_2$ 个系数为 $-1$ 的多项式集合。然后计算 $f_p(x)=R_p\left(\dfrac{1}{f(x)}\right)$， $f_q(x)=R_q\left(\dfrac{1}{f(x)}\right)$。在此基础上，随机产生仅含系数 $0,1$ 的多项式 $g(x)\in R_q$。私钥为 $f(x),f_p(x),f_q(x),g(x)$，公钥为 $h(x)=pg(x)f_q(x)\in R_q$。加密方式为随机产生小系数多项式 $r(x)$，计算 $c(x)=h(x)r(x)+m(x)$

这里，是给出了 10 次机会，每次让你选择一个 $m(x)$，然后会给出 $c_i(x)=h(x)r_i(x)+s(x)+m_i(x)$ 。其中：$h(x),c(x)$ 已知，$m_i(x)$ 自行构造。那么我们可以有 $\bar c_i(x)=c_i(x)-m_i(x)=h(x)r_i(x)+s(x)$。

处理之后，由于 $r(x)$ 仅包含 $0,1$，可以计算 $d_i(x)=\bar c_0(x)-\bar c_i(x),x=1,2,…,9$，来消除 $s(x)$。再计算 $\bar d_i(x)=\dfrac{d_i(x)}{h(x)}$，就可以得到两个 $r_0(x)-r_i(x)$ 的差了，如果某个系数是 $1$，则说明 $r_0(x)$ 对应系数为 $1$；如果某个系数是 $-1$，则说明 $r_0(x)$ 对应的系数为 $0$；如果为 $0$，说明无法确定这个情况。但 $9$ 组数据，基本够用了。。。

1x03 exp

不是很难，但NTRU以前自己没见过，确实不太好搞。

#from sage.all import *
from pwn import *
from random import *
o1.<u>=PolynomialRing(GF(3))
o2.<v>=PolynomialRing(GF(1091))
Rp=o1.quotient(u**117+1)
Rq=o2.quotient(v**117+1)
sh=process(['python3','task.py'])

Hx=eval(sh.recvline(keepends=False))
print(Hx)
farr=[]
carr=[]
for i in range(10):
	sh.recvuntil(b"Give me a list of message (hex):")
	f="1"
	for i in range(115):
		f+=" "+str(randint(0,1))
	farr.append(f)
	sh.sendline(f.encode())
	c=eval(sh.recvline(keepends=False))
	#print(c)
	carr.append(c)

for i in range(10):
	farr[i]=farr[i].split(" ")
	farr[i]=[round(int(j)/3329) for j in farr[i]]
	farr[i]=Rq(farr[i])
	carr[i]=Rq(carr[i])
Hx=Rq(Hx)

dcarr=[(-carr[i]+carr[0])/Hx for i in range(1,10)]
# print(dcarr[7])
# # #print(dcarr[0])
rx=[-2]*116
for i in range(9):
	ldci=list(dcarr[i])
	#print(ldci)
	for j in range(116):
		if(rx[j]==-2):
			if(ldci[j]==1):
				rx[j]=1
			if(ldci[j]==1090):
				rx[j]=0

assert -2 not in rx
rx=Rq(rx)
sx=carr[0]-Hx*rx
print(sx)
assert set(list(sx))=={0,1,1090}
sh.recvuntil(b"You wanner say something? :")
A=0
lsx=list(sx)
for i in range(117):
	if(lsx[i]==1):
		A+=3**i
	if(lsx[i]==1090):
		A+=2*3**i
sh.sendline(hex(A)[2:].encode())
print(sh.recvall())
sh.close()

可能的运行结果：

2.[2024强网杯决赛]f2ke

2x01 题目大意

老规矩，还是先看一看题目：

from sage.all import *
from Crypto.Util.number import long_to_bytes
import os
import signal
from datetime import *

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 70
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

load("ntru.sage")
p,n,q,dg,df = 3,117,1091,35,37


def Game():
    secret = os.urandom(23)
    secretpoly = MsgtoPoly(secret)
    print("Welcome to f2ke. You can send some message to me. Have fun!")
    msgs = [[0 for _ in range(116)]]

    for _ in range((n + 3) // 2):
        while True:
            pk,sk = genKeys()
            try:
                1 / pk
                break
            except:
                pass
        msg = [round(int(i,16) % 3329) for i in input("Give me a list of message (hex):").split(" ")]
        if len(msg) != 116 or (msg in msgs):
            print("You bad!")
            return
        msgs.append(msg)
        m = secretpoly + QR([round(i / 3329 * q) for i in msg])
        c = encrypt(pk,m)
        try:
            assert m == decrypt(sk,c)
        except:
            print("You bad!!")
            return
        print(c.list())
        print(pk.list())

    if long_to_bytes(int(input("You wanner say something? :"), 16)) == secret:
        print('flag{Success at :'+str(datetime.now())+'}')
        print("You good!")
    else:
        print("OK, bye bye~") 

Game()

这个和上一题的区别，就在于：每一次的公钥 $h(x)$ 都产生了变化，并且交互次数达到了 $60$ 次。乍一看，感觉是NTRU的广播攻击，但感觉次数不太够。（确实不太够，要 $176$ 次交互）

2x02 NTRU的广播攻击学习

2x02.1 modulus=$x^n-1$

不过，自己这个时候还不太会NTRU的广播攻击，于是，先学一下NTRU的广播攻击。在原始NTRU中，使用的取模多项式是 $x^n-1$，但题目是 $x^n+1$，因此先看 $x^n-1$ 的情况：

当模数为 $x^n-1$ 时，对应的公钥 $h(x)$ 的系数矩阵为一个循环矩阵，类似于这样的形式，该矩阵大概率可逆：

因此，NTRU写成矩阵的形式就是：
$$
H\vec r+\vec m=\vec c
$$
由于矩阵 $H$ 大概率可逆，那么可以有：
$$
\vec r+H^{-1}\vec m=H^{-1}\vec c
$$
设 $H^{-1}=K,H^{-1}\vec c=\vec b$，那么这个式子变成：
$$
\vec r+K\vec m=\vec b
$$
移项，有
$$
\vec r=\vec b-K\vec m
$$
两边平方：
$$
\vec r^2=\vec b^2-2\vec b\cdot(K\vec m)+(K\vec m)^2
$$
如果我们已知 $\vec r^2$，那么，可以有：
$$
\vec r^2-\vec b^2=(K\vec m)^2-2\vec b\cdot(K\vec m)
$$
写得规范一点，就是：
$$
\vec r^2-\vec b^2=\vec m^TK^TK\vec m-2\left(\vec b^TK\right)\vec m
$$
设：

可以得到：

其中 $s=\vec r^2-\vec b^2$，这里 $\vec r^2$ 已知。由于 $\vec r$ 仅含 $0,1,-1$，那么 $\vec r^2$ 就是 $\vec r$ 中非零分量的个数，那么最终结果为

因此，这里有 $n+\left\lceil\dfrac{n}{2}\right\rceil$ 个未知数，我们只需要构造对应数量的方程，就可以去解方程了！

不过自己根据论文代码实现时，发现总有点小问题，矩阵不满秩，导致最后结果总是会偏移 $x^{n-1}$ 的系数。反正那个值就是 $0,±1$，特判一下就行。

Code：

import random
from Crypto.Util.number import bytes_to_long,long_to_bytes

p,n,q,dg,df = 3,117,1091,35,37
dr=37 #有变化
R.<x> = PolynomialRing(Zmod(q))
RR.<xx> = PolynomialRing(Zmod(p))
QR = R.quotient(x ^ n - 1) #有变化
QRR = RR.quotient(xx ^ n - 1) #有变化

def balancemodlist(List,p):
    for i in range(len(List)):
        if int(List[i]) > p / 2:
            List[i] = int(List[i]) - p
    return List


def randomPoly(d = 0):
    if d == 0:
        poly = QR([random.randint(0,1) for _ in range(n)])
    else:
        L_0 = [0] * (n - 2 * d - 1)
        L_1 = (d + 1) * [1]
        L_2 = d * [-1]
        L = L_0 + L_1 + L_2
        for i in range(randint(5,10)):
            random.shuffle(L)
        poly = QR(L)
    return poly

def genPrivKey():
    while True:
        poly = randomPoly(df)
        try:
            poly_q = (1 / QR(poly))
            poly_p = (1 / QRR(RR(balancemodlist(poly.list(),q))))
            break
        except:
            pass
    return poly, poly_q, poly_p

def genKeys():
    f, f_q, f_p = genPrivKey()
    g = randomPoly(dg)
    pk = QR(p * g * f_q)
    sk = (f,f_q,f_p,g)
    return pk,sk

def encrypt(pk, m):
    r = randomPoly(dr)#有变化
    return pk * r + m


mx=R([randint(-1,1) for i in range(n)])
Fxarr=[]
Fqxarr=[]
Fpxarr=[]
Gxarr=[]
Hxarr=[]
Cxarr=[]
for i in range(200):
    pk,sk=genKeys()
    fx,fqx,fpx,gx=sk
    hx=pk
    Fxarr.append(fx)
    Fqxarr.append(fqx)
    Fpxarr.append(fpx)
    Gxarr.append(gx)
    Hxarr.append(hx)
    cx=encrypt(hx,mx)
    Cxarr.append(cx)

print('mx(for debug check)=',list(mx))
HxMatrixarr=[]
CxVecarr=[]
for hx in Hxarr:
    HxMatrixarr.append(Matrix(GF(q),[list(hx*x**(i)) for i in range(n)]).T)
KxMatrixarr=[mhx**-1 for mhx in HxMatrixarr]
for cx in Cxarr:
    CxVecarr.append(vector(GF(q),list(cx)))
BxVecarr=[mkx*vcx for mkx,vcx in zip(KxMatrixarr,CxVecarr)]
A=[]
y=[]
for i in range(1+n+((n+1)>>1)):
    Kx=KxMatrixarr[i]
    vecb=BxVecarr[i]
    vecw=vecb*Kx
    veca=((Kx.T*Kx).T)[0]
    uke=[veca[0]]+[2*veca[i+1] for i in range(n//2)]
    uke+=list(-2*vecw)
    A.append(uke)
    y.append(2*dr+1-vecb*vecb)
A=matrix(GF(q),A)
y=vector(GF(q),y)
res=(A.solve_right(y))
print(res[-n:])
print(list(mx))
reschk=set(list(res[-n:]))
if(2 in reschk):
    res-=vector([1 for _ in range(len(res))])
elif(q-2 in reschk):
    res+=vector([1 for _ in range(len(res))])
print(res[-n:])
print(list(res[-n:])==list(mx))
from datetime import *
print(str(datetime.now()))

可能的输出结果（很显然，解出来的结果有 $-2$，说明整体偏移了一个 $ -1$，直接调回来就行）：

(1089, 1089, 0, 1090, 1090, 0, 0, 1089, 1089, 1090, 0, 1089, 1089, 0, 1089, 1089, 1090, 1089, 1090, 0, 1090, 0, 0, 1090, 1089, 1090, 1090, 0, 0, 1090, 0, 1089, 0, 1089, 1089, 1089, 1090, 1090, 1090, 1089, 0, 1089, 0, 1090, 1090, 0, 1089, 1089, 1090, 1090, 0, 0, 0, 1089, 0, 1090, 0, 1090, 0, 1089, 0, 1090, 0, 1090, 1090, 1089, 1089, 0, 1090, 1089, 1089, 1090, 1090, 0, 1089, 0, 0, 1089, 1089, 0, 1090, 0, 1090, 0, 1089, 1089, 0, 1090, 1090, 1089, 0, 0, 1089, 1089, 1090, 1090, 0, 1089, 1090, 0, 0, 1090, 1089, 0, 0, 1090, 1090, 1090, 1090, 1090, 1089, 1090, 1089, 0, 1090, 1090, 0) 
[1090, 1090, 1, 0, 0, 1, 1, 1090, 1090, 0, 1, 1090, 1090, 1, 1090, 1090, 0, 1090, 0, 1, 0, 1, 1, 0, 1090, 0, 0, 1, 1, 0, 1, 1090, 1, 1090, 1090, 1090, 0, 0, 0, 1090, 1, 1090, 1, 0, 0, 1, 1090, 1090, 0, 0, 1, 1, 1, 1090, 1, 0, 1, 0, 1, 1090, 1, 0, 1, 0, 0, 1090, 1090, 1, 0, 1090, 1090, 0, 0, 1, 1090, 1, 1, 1090, 1090, 1, 0, 1, 0, 1, 1090, 1090, 1, 0, 0, 1090, 1, 1, 1090, 1090, 0, 0, 1, 1090, 0, 1, 1, 0, 1090, 1, 1, 0, 0, 0, 0, 0, 1090, 0, 1090, 1, 0, 0, 1]
(1090, 1090, 1, 0, 0, 1, 1, 1090, 1090, 0, 1, 1090, 1090, 1, 1090, 1090, 0, 1090, 0, 1, 0, 1, 1, 0, 1090, 0, 0, 1, 1, 0, 1, 1090, 1, 1090, 1090, 1090, 0, 0, 0, 1090, 1, 1090, 1, 0, 0, 1, 1090, 1090, 0, 0, 1, 1, 1, 1090, 1, 0, 1, 0, 1, 1090, 1, 0, 1, 0, 0, 1090, 1090, 1, 0, 1090, 1090, 0, 0, 1, 1090, 1, 1, 1090, 1090, 1, 0, 1, 0, 1, 1090, 1090, 1, 0, 0, 1090, 1, 1, 1090, 1090, 0, 0, 1, 1090, 0, 1, 1, 0, 1090, 1, 1, 0, 0, 0, 0, 0, 1090, 0, 1090, 1, 0, 0, 1)
True
2025-01-11 10:11:33.085945

2x02.2题目参数

在搞懂基本原理后，我们回到题目的参数，由于模数变成了 $x^n+1$，并且， $\vec r$ 为完全随机的 $0,1$ 向量。

既然模数改变了，那么之前的矩阵也会有所变化，需要重新设为：

由于刚才是 $\vec r=\vec b-K\vec m$，这里可以两边乘 $2$，再减去一个全 $1$ 向量，变为：
$$
2\vec r-\vec 1=2(\vec b-K\vec m)-\vec 1
$$
由于 $\vec r$ 仅含 $0,1$，那么 $2\vec r-\vec 1$ 就仅含 $-1,1$ 了，两边平方有：
$$
(2\vec r-\vec 1)^2=4(\vec b-K\vec m)^2-4(\vec b-K\vec m)\cdot \vec 1+\vec 1^2
$$
由于 $(2\vec r-\vec 1)^2=\vec 1^2=n$，这两个可以直接约掉，然后进行系数化简：
$$
0=(\vec b-K\vec m)^2-(\vec b-K\vec m)\cdot \vec 1
$$
继续处理一下：
$$
\vec b^2-\vec b\cdot \vec 1=2\vec b^TK\vec m-\vec m^TK^TK\vec m-(K\vec m)\cdot \vec 1
$$
左边的都是已知量，很好算，然后我们看看右边三项的表达式：

第一项给所有的 $m_i$ 项带来了一个 $w_i$；第三项给每个 $ m_i$ 又带来了一个 $K$ 的第 $i$ 列系数之和，即 $m_i$ 的系数为$\sum_j K^{T}_{ij}$

而第二项也出现了一点点小变化：我们来测试一下，发现此时有 $x_i=-x_{n-i}$。

var("a0 a1 a2 a3 a4")
var("m0 m1 m2 m3 m4")
v=vector([m0,m1,m2,m3,m4])
M=[[a0,-a4,-a3,-a2,-a1],
[a1,a0,-a4,-a3,-a2],
[a2,a1,a0,-a4,-a3],
[a3,a2,a1,a0,-a4],
[a4,a3,a2,a1,a0]]
M=matrix(M)
v*M*v
f=v*M*v
xarr=[]
for i in [a0,a1,a2,a3,a4]:
    xarr.append(f.differentiate(i))
print(xarr[1]+xarr[4],xarr[2]+xarr[3])
#0 0

然后再考察一下 $K^TK$，测试发现，有 $a_i=-a_{n-i}$

那么： $a_ix_i+a_{n-i}x_{n-i}$，照样等于 $2a_ix_i$。那么可以不对原来的ntru.sage文件做任何改变。

load('ntru.sage')
mx=R([randint(0,2)-1 for i in range(n)])
Fxarr=[]
Fqxarr=[]
Fpxarr=[]
Gxarr=[]
Hxarr=[]
Cxarr=[]
for i in range(400):
    pk,sk=genKeys()
    fx,fqx,fpx,gx=sk
    hx=pk
    Fxarr.append(fx)
    Fqxarr.append(fqx)
    Fpxarr.append(fpx)
    Gxarr.append(gx)
    Hxarr.append(hx)
    cx=encrypt(hx,mx)
    Cxarr.append(cx)

HxMatrixarr=[]
CxVecarr=[]
for hx in Hxarr:
    HxMatrixarr.append(Matrix(GF(q),[list(hx*x**(i)) for i in range(n)]).T)
KxMatrixarr=[mhx**-1 for mhx in HxMatrixarr]
for cx in Cxarr:
    CxVecarr.append(vector(GF(q),list(cx)))
BxVecarr=[mkx*vcx for mkx,vcx in zip(KxMatrixarr,CxVecarr)]
A=[]
y=[]
for i in range(n+((n+1)>>1)):
    Kx=KxMatrixarr[i]
    vecb=BxVecarr[i]
    vecw=vecb*Kx
    veca=((Kx.T*Kx).T)[0]
    uke=[veca[0]]+[2*veca[i+1] for i in range(n//2)]
    ukep=list(2*vecw)
    for j in range(n):
        ukep[j]-=sum(list(Kx.T[j]))
    uke=uke+ukep
    A.append(uke)
    y.append(vecb*vecb-sum(list(vecb)))
A=matrix(GF(q),A)
y=vector(GF(q),y)
res=(A.solve_right(y))
res=R(list(res[-n:]))
print(list(mx))
print(list(res))
print(res-mx)
from datetime import *
print(str(datetime.now()))

可能的运行结果，可以看出，这个不一定总能正常运行，因为矩阵 $H$ 的逆矩阵 $H^{-1}$ 并非总存在。

2x03 简化版本：400次询问

因此，如果原题给出 400 次询问，那么就可以使用广播攻击方式去做（其实176次就够了，这里搞成400次，主要是因为一开始懒得算次数了，实际也只用了176组数据）

from pwn import *
from tqdm import *
from random import *
sh=process(['python3','task.py'])
q=1091
n=117
Mxarr=[[getrandbits(1) for _ in range(116)]for __ in range(400)]
Cxarr=[]
Hxarr=[]
O7.<x_>=PolynomialRing(GF(q))
Rq.<x>=O7.quotient(x_**117+1)
for i in tqdm(range(400)):
    sh.recvuntil(b'Give me a list of message (hex):')
    s=str(Mxarr[i])[1:-1]
    s=s.replace(' ','')
    s=s.replace(',',' ')
    #print(s)
    sh.sendline(s.encode())
    Cx=(eval(sh.recvline()))
    Hx=(eval(sh.recvline()))
    Cxarr.append(Rq(Cx))
    Hxarr.append(Rq(Hx))
for i in range(400):
    for j in range(116):
        Mxarr[i][j]=round(Mxarr[i][j]/3329*q)
    Mxarr[i]=Rq(Mxarr[i])
for i in range(400):
    Cxarr[i]=Cxarr[i]-Mxarr[i]
HxMatrixarr=[]
CxVecarr=[]
for hx in Hxarr:
    HxMatrixarr.append(Matrix(GF(q),[list(hx*x**(i)) for i in range(n)]).T)
KxMatrixarr=[mhx**-1 for mhx in HxMatrixarr]
for cx in Cxarr:
    CxVecarr.append(vector(GF(q),list(cx)))
BxVecarr=[mkx*vcx for mkx,vcx in zip(KxMatrixarr,CxVecarr)]
A=[]
y=[]
for i in range(n+((n+1)>>1)):
    Kx=KxMatrixarr[i]
    vecb=BxVecarr[i]
    vecw=vecb*Kx
    veca=((Kx.T*Kx).T)[0]
    uke=[veca[0]]+[2*veca[i+1] for i in range(n//2)]
    ukep=list(2*vecw)
    for j in range(n):
        ukep[j]-=sum(list(Kx.T[j]))
    uke=uke+ukep
    A.append(uke)
    y.append(vecb*vecb-sum(list(vecb)))
A=matrix(GF(q),A)
y=vector(GF(q),y)
res=(A.solve_right(y))
res=Rq(list(res[-n:]))
#print(res)
from datetime import *
print(str(datetime.now()))
res=list(res)
print(res)
for i in range(len(res)):
    if(res[i]==q-1):
        res[i]=2
res=vector(ZZ,res+[0]*(117-len(res)))
exp3=vector(ZZ,[3**i for i in range(117)])
ans=res*exp3
print(ans)
sh.recvuntil(b'You wanner say something? :')
sh.sendline(hex(ans)[2:].encode())
sh.interactive()

可能的运行结果：

2x04 原题做法

原题的话，只有60次询问机会，次数还是不太够。

然后在2010-598那篇论文中，我看到了这样一句话：

如果 $ES$ 只有 $0,1$ 两种取值，那么我们可以增加 $n$ 个方程： $r_i^2-r_i=0$。

在 $\vec r=\vec b-K\vec m$ 中，我们考察 $\vec r$ 的每一个分量所涉及到的关系，以三个为例：
$$
r_0=b_0-\vec K_0\vec m=b_0-(K_{00}m_0+K_{01}m_1+K_{02}m_2)
$$
两边变换，有：
$$
r_0^2-r_0=\left(b_0-(K_{00}m_0+K_{01}m_1+K_{02}m_2)\right)^2-(b_0-(K_{00}m_0+K_{01}m_1+K_{02}m_2))
$$
等号左边显然为 $0$，对等号右边展开：

sage: var("b0 K00 K01 K02 m0 m1 m2")
(b0, K00, K01, K02, m0, m1, m2)
sage: f=b0-K00*m0-K01*m1-K02*m2
sage: f*(f-1)
(K00*m0 + K01*m1 + K02*m2 - b0 + 1)*(K00*m0 + K01*m1 + K02*m2 - b0)
sage: f*(f-1).expand()
(K00*m0 + K01*m1 + K02*m2 - b0 + 1)*(K00*m0 + K01*m1 + K02*m2 - b0)
sage: y=f*(f-1)
sage: y.expand()
K00^2*m0^2 + 2*K00*K01*m0*m1 + K01^2*m1^2 + 2*K00*K02*m0*m2 + 2*K01*K02*m1*m2 + K02^2*m2^2 - 2*K00*b0*m0 - 2*K01*b0*m1 - 2*K02*b0*m2 + b0^2 + K00*m0 + K01*m1 + K02*m2 - b0

等号一遍留下 $b_0^2-b_0$，那么右边就是这一堆玩意：

1	`-K00^2m0^2 - 2K00K01m0m1 - K01^2m1^2 - 2K00K02m0m2 - 2K01K02m1m2 - K02^2m2^2 + 2K00b0m0 + 2K01b0m1 + 2K02b0m2 - K00m0 - K01m1 - K02*m2`

整理一下：

一次项： $m_0$ 系数为 $-2K_{00}b_0+K_{00}$，$m_1$ 系数为 $-2K_{01}b_0+K_{01}$，$m_2$ 系数为 $-2K_{02}b_0+K_{02}$

平方项： $m_0^2$ 系数为 $-K_{00}^2$，同理，$m_1^2,m_2^2$ 的系数分别为 $-K_{01}^2,-K_{02}^2$ 。

交叉项： $m_im_j$ 系数为 $-2K_{0i}K_{0j}$。

那么，我们就有了 $n$ 个一次项，$n$ 个平方项，$\dfrac{n(n-1)}{2}$ 个交叉项，一共 $\dfrac{n(n+3)}{2}$ 个未知数，一次广播攻击可以取得 $n$ 个未知数。

然后，原题是 $117$，最后的矩阵规模高达 $7020\times7020$，光是跑这个构造就要耗我一小时，在服务器上跑快一点，但2核2G的服务器，直接炸掉了。。。。

不过，为了测试正确性，还是得做一下的。。。。因此，我把 $n$ 从 $117$ 调成了 $47$，$d_f,d_g$ 从 $(35,37)$ 调为 $(7,7)$，仅用于测试正确性，因此，最后的交互次数也从 $60$ 下降到了 $25$。

from pwn import *
from tqdm import *
from random import *
sh=process(['python3','task.py'])
q=1091
n=47
Mxarr=[[getrandbits(1) for _ in range(46)]for __ in range(400)]
Cxarr=[]
Hxarr=[]
K7.<x_>=PolynomialRing(GF(q))
Rq.<x>=K7.quotient(x_**n+1)
for i in tqdm(range(25)):
    sh.recvuntil(b'Give me a list of message (hex):')
    s=str(Mxarr[i])[1:-1]
    s=s.replace(' ','')
    s=s.replace(',',' ')
    sh.sendline(s.encode())
    Cx=(eval(sh.recvline()))
    Hx=(eval(sh.recvline()))
    Cxarr.append(Rq(Cx))
    Hxarr.append(Rq(Hx))

for i in range(25):
    Cxarr[i]=Rq(Cxarr[i])
    Hxarr[i]=Rq(Hxarr[i])
from tqdm import *
from datetime import *
HxMatrixarr=[]
CxVecarr=[]
for hx in Hxarr:
    HxMatrixarr.append(Matrix(GF(q),[list(hx*x**(i)) for i in range(n)]).T)
KxMatrixarr=[mhx**-1 for mhx in HxMatrixarr]
for cx in Cxarr:
    CxVecarr.append(vector(GF(q),list(cx)))
BxVecarr=[mkx*vcx for mkx,vcx in zip(KxMatrixarr,CxVecarr)]
A=[]
y=[]
for ttt in tqdm(range(25)):
    K=KxMatrixarr[ttt]
    b=BxVecarr[ttt]
    Kt=K.T
    G=Kt*K
    for i in range(n):
        y.append(b[i]*b[i]-b[i])
        singlem=[]
        for j in range(n):
            singlem.append(b[i]*K[i][j]+(b[i]-1)*K[i][j]) 
        squarem=[]
        for j in range(n):
            squarem.append(K[i][j]**2)
        crossm=[]
        for j in range(n):
            for k in range(j+1, n):
                crossm.append(-2*K[i][j]*K[i][k])
        A.append(singlem+squarem+crossm)
A=matrix(GF(q),A)
y=vector(GF(q),y)
res=A.solve_right(y)
print(str(datetime.now()))
print(res[:n])
sh.recvuntil(b"You wanner say something? :")
vres=res[:n]
ans=0
for i in range(n):
    ans+=min(2,Integer(res[i]))*3**i
sh.sendline(hex(ans)[2:].encode())
print(sh.recvall())
sh.close()

运行结果：

原题的数据就不测了，两边设备条件都不是很允许我测。。。。根据 $O(n^3)$ 的复杂度看，目测要跑一天！

3.fake2的非预期做法—NTRU子环攻击

3x01 分析

其实我一开始就发现，这里用 $117$ 作为指数，就不太对。很明显，$117=3^2\times13$ ，不是一个素数。又看到是广播攻击，因此也许可能能CRT？

我们可以注意到：
$$
x^3+1=(x+1)(x^2-x+1)
$$
那么，$x^{117}+1$ 也可以被分解成：
$$
x^{117}+1=(x^{39}+1)(x^{78}-x^{39}+1)
$$
然后题目的交互次数是 $60$ 次，对于 $x^{39}+1$ 的模数，貌似刚好够打（59次）。但对于 $x^{78}-x^{39}+1$ 呢？

不过据说可以直接对公钥开打，构造NTRU矩阵，其中 $H$ 的第 $i$ 行表示 $x^ih(x)$ 的列表表示，请注意，$i$ 从 $0$ 开始。

对这个 $M$ 进行 BKZ ，最后有可能得到 $(f,3g)$ 的值（因为题目是 $h(x)=pg(x)r(x),p=3$）。不过这个 $f$ 可能会出现 $2$，因为是在子环上打的。因此，可以对 60 组公钥分别开打，寻找一个合适的公钥，使其在 $R_{q,78}$ 和 $R_{q,39}$ 上都能得到很小的值。60次机会，貌似还是够用的。

3x02 实验测试

然后就是实验测试：

f39=None
f78=None
from tqdm import *
avail=[]
for T in trange(60):
    M39=[list(Rq39(Hxarr[T])*Rq39([0,1])**i) for i in range(39)]
    M39=matrix(M39)
    M=block_matrix(ZZ,[[1,M39],[0,q]])
    M3L=M.BKZ()
    fxtest=list(M3L[0])[:39]
    if(max(fxtest)<=2 and min(fxtest)>=-2):
        avail.append((T,fxtest))
print(f'find {len(avail)} possible')
for T,_f39 in avail:
    M78=[list(Rq78(Hxarr[T])*Rq78([0,1])**i) for i in range(78)]
    M78=matrix(M78)
    M=block_matrix(ZZ,[[1,M78],[0,q]])
    M3L=M.BKZ()
    fxtest=list(M3L[0])[:78]
    if(max(fxtest)<=2 and min(fxtest)>=-2):
        f78=fxtest
        f39=_f39
        print(T)
        break
print(f78)
print(f39)

可能的输出结果

find 14 possible
50
[-2, -1, -2, 1, -1, 0, 0, -1, 1, -1, 0, 0, -2, 2, 0, -1, 1, 2, 1, -1, -1, -2, -1, -1, 1, -2, -1, 0, 1, 0, 2, 1, 2, -2, -2, -1, 1, 1, 0, 0, 1, 0, 0, -1, -2, -1, 1, -1, 0, 2, -1, 0, -1, 1, 0, 0, 0, -1, 0, 1, 1, 0, 2, 0, 1, 1, -1, -2, 0, 0, -2, 0, 2, 0, 0, 0, -1, -2]
[1, 1, 1, -2, 1, 1, 0, -1, -2, -2, 2, -1, 1, 1, 1, 0, -1, -1, 1, -1, -1, -1, 1, 0, 2, 0, 1, 0, -2, -2, 0, 0, -1, 0, -1, -1, 1, 2, 1]

为了方便调试，我对原题进行了修改，令其每次生成的私钥 $f(x)$ 会被写入一个文件中去。我打开这个文件，找到了第 $50$ 组私钥

i:50,sk=[0, 1, 1090, 1090, 1090, 0, 0, 1, 0, 1, 1090, 1090, 0, 1, 0, 1090, 1090, 1, 1090, 0, 1090, 1090, 0, 1, 1090, 0, 1, 1090, 1090, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1090, 1, 0, 0, 1, 0, 1090, 0, 1, 1090, 1, 1, 1090, 1090, 0, 0, 1090, 1, 0, 1, 0, 0, 1090, 1090, 0, 0, 0, 1, 0, 1, 1090, 0, 0, 0, 1090, 1090, 0, 1, 1, 1, 1, 0, 1, 0, 1090, 1090, 0, 1090, 1090, 1090, 1, 1, 1, 0, 1090, 1090, 1, 1, 1, 1090, 1, 1, 1, 1, 1090, 1, 1090, 0, 1, 1090, 0, 1, 1090, 1090, 0, 1, 0, 1, 0]

然后测一下：

ycrt=crt([O7(f78),O7(f39)],[x_**78-x_**39+1,x_**39+1])
y=Rq(list(ycrt))
listskreal=[0, 1, 1090, 1090, 1090, 0, 0, 1, 0, 1, 1090, 1090, 0, 1, 0, 1090, 1090, 1, 1090, 0, 1090, 1090, 0, 1, 1090, 0, 1, 1090, 1090, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1090, 1, 0, 0, 1, 0, 1090, 0, 1, 1090, 1, 1, 1090, 1090, 0, 0, 1090, 1, 0, 1, 0, 0, 1090, 1090, 0, 0, 0, 1, 0, 1, 1090, 0, 0, 0, 1090, 1090, 0, 1, 1, 1, 1, 0, 1, 0, 1090, 1090, 0, 1090, 1090, 1090, 1, 1, 1, 0, 1090, 1090, 1, 1, 1, 1090, 1, 1, 1, 1, 1090, 1, 1090, 0, 1, 1090, 0, 1, 1090, 1090, 0, 1, 0, 1, 0]
skreal=Rq(listskreal)
print(list(y))
#[1090, 0, 1090, 0, 363, 727, 727, 363, 727, 726, 365, 363, 1090, 365, 728, 363, 364, 1, 728, 1090, 363, 726, 727, 0, 365, 1090, 0, 727, 363, 363, 365, 0, 1, 363, 362, 1090, 1, 1, 727, 1090, 0, 1090, 1, 726, 362, 363, 728, 364, 364, 728, 727, 1090, 727, 364, 727, 728, 1, 363, 0, 728, 364, 363, 1, 727, 0, 0, 363, 727, 728, 728, 1090, 1, 728, 727, 0, 0, 1090, 362, 1, 1, 1, 1090, 364, 727, 727, 364, 726, 727, 365, 363, 1, 363, 728, 364, 363, 1090, 727, 0, 364, 728, 728, 1, 364, 1, 1, 727, 362, 363, 363, 1090, 1090, 365, 364, 0, 0, 0, 727]

你会发现，$y$ 并不是仅包含 $0,1,-1$，还包含了很多其他的值。因为我们BKZ出来的是得到循环移位的东西。

测一下：

1/Rq78(listskreal)*Rq78(y)
# x^23
Rq39(y)/Rq39(listskreal)
# x^25

也就是，在 $R_{q,78}$ 中，$\dfrac{y(x)}{f(x)}=x^{23}$，在 $R_{q,39}$ 中，$\dfrac{y(x)}{f(x)}=x^{25}$。看来可以爆破？还真是。

for i in range(-78,78):
    for j in range(-39,39):
        y39x=Rq39(f39)*Rq39([0,1])**j
        y78x=Rq78(f78)*Rq78([0,1])**i
        y39x=O7(list(y39x))
        y78x=O7(list(y78x))
        yguess=crt([y39x,y78x],[x_**39+1,x_**78-x_**39+1])
        if(Rq(yguess)==Rq(listskreal)):
            print(i,j)
# -23 -25

但，在实际做题的时候，我们并不知道私钥，因此需要加一个判断测试一下：

for i in range(-78,78):
    for j in range(-39,39):
        y39x=Rq39(f39)*Rq39([0,1])**j
        y78x=Rq78(f78)*Rq78([0,1])**i
        y39x=O7(list(y39x))
        y78x=O7(list(y78x))
        yguess=crt([y39x,y78x],[x_**39+1,x_**78-x_**39+1])
        ylist=list(yguess)
        yset=set(ylist)
        vecy=vector(GF(1091),ylist)
        if(yset=={0,1,1090} ):
            print(i,j,Rq(yguess)/Rq(listskreal))

"""
Output:
-78 -2 1090*x^62
-77 -1 1090*x^63
-76 0 1090*x^64
-75 1 1090*x^65
-74 2 1090*x^66
... ... ... ...
-25 -27 1090*x^115
-24 -26 1090*x^116
-23 -25 1
-22 -24 x
-21 -23 x^2
... ... ... ...
73 -7 x^96
74 -6 x^97
75 -5 x^98
76 -4 x^99
77 -3 x^100
"""

这个输出结果是有规律的，最后解出来的东西也是私钥的循环移位。不过貌似不是每次都能解出来的，因为 $x^{39}+1$ 的分解太多了，很容易出现不可逆的结果。

多调试了几次，拿到了一组结果，随机取最后一组结果

def balancemodlist(List,p):
    for i in range(len(List)):
        if int(List[i]) > p / 2:
            List[i] = int(List[i]) - p
    return List
def decrypt(f,fp,c):
    m = Rq(balancemodlist((Rp(balancemodlist((f * c).list(),q)) * fp).list(),p))
    return m

print(fx)
fp = (1 / Rp(O8(balancemodlist(fx.list(),q))))
s=decrypt(fx,fp,Rq(Cxarr[16]))
print(s)
#fx:[0, 1090, 1090, 0, 0, 1090, 0, 0, 1, 1, 0, 1090, 1090, 1090, 0, 1, 1, 1, 1, 1090, 1090, 0, 0, 1090, 1, 1090, 0, 1, 0, 0, 1090, 0, 1, 0, 1, 1090, 1, 1, 0, 1, 1090, 1090, 1090, 1090, 1, 1090, 0, 1, 0, 1090, 1, 1090, 1090, 1, 1090, 0, 1090, 0, 0, 0, 1090, 0, 0, 1, 0, 1090, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1090, 0, 1, 1090, 1, 1, 0, 0, 1090, 1090, 1, 0, 1090, 0, 1090, 1090, 1090, 0, 0, 0, 0, 1090, 1, 1090, 1090, 1090, 0, 0, 1, 0, 1090, 1090, 1, 1, 1, 1090, 1090, 1090, 1090, 1090, 1]
#s:[0, 1090, 1090, 1090, 1090, 1090, 1090, 1, 1090, 1090, 1, 0, 0, 1, 1090, 1, 1090, 1, 1, 1, 0, 1090, 1, 1090, 0, 0, 1090, 1, 1, 1, 1090, 0, 1, 0, 0, 0, 1090, 1, 1, 0, 0, 1, 1090, 0, 1, 1, 1, 1090, 1, 1090, 1090, 0, 1, 0, 1090, 1090, 1090, 1090, 0, 1090, 0, 1090, 1090, 1, 1, 1090, 0, 1, 1090, 1090, 0, 1090, 1, 1, 0, 0, 1090, 1090, 1, 0, 0, 1090, 0, 0, 1090, 0, 1, 1, 1090, 1, 0, 1090, 1090, 1090, 0, 1, 1, 1, 1, 0, 1090, 1090, 0, 0, 1, 1090, 1090, 1090, 0, 1, 0, 1, 1, 0, 1, 0, 0]

然后调试了一下：

sreal=Rq([0, 1090, 1090, 1090, 1090, 1090, 1090, 1, 1090, 1090, 1, 0, 0, 1, 1090, 1, 1090, 1, 1, 1, 0, 1090, 1, 1090, 0, 0, 1090, 1, 1, 1, 1090, 0, 1, 0, 0, 0, 1090, 1, 1, 0, 0, 1, 1090, 0, 1, 1, 1, 1090, 1, 1090, 1090, 0, 1, 0, 1090, 1090, 1090, 1090, 0, 1090, 0, 1090, 1090, 1, 1, 1090, 0, 1, 1090, 1090, 0, 1090, 1, 1, 0, 0, 1090, 1090, 1, 0, 0, 1090, 0, 0, 1090, 0, 1, 1, 1090, 1, 0, 1090, 1090, 1090, 0, 1, 1, 1, 1, 0, 1090, 1090, 0, 0, 1, 1090, 1090, 1090, 0, 1, 0, 1, 1, 0, 1, 0, 0])
#从文件中预先获取的sreal
sreal-s
#0

然后发现第一组也可以，看来私钥的移位不影响最后解密结果。那干脆直接找到一组break掉就ok了。

3x03 exp

from pwn import *
from tqdm import *
from random import *
sh=process(['python3','task.py'])
#load('ntru.sage')
p,n,q,dg,df = 3,117,1091,35,37
Mxarr=[[getrandbits(1) for _ in range(116)]for __ in range(400)]
Cxarr=[]
Hxarr=[]
O7.<x_>=PolynomialRing(GF(q))
O8.<xp_>=PolynomialRing(GF(p))
Rp.<xp>=O8.quotient(xp_**117+1)
Rq.<x>=O7.quotient(x_**117+1)
Rq39.<x>=O7.quotient(x_**39+1)
Rq78.<x>=O7.quotient(x_**78-x_**39+1)
for i in tqdm(range(60)):
    sh.recvuntil(b'Give me a list of message (hex):')
    s=str(Mxarr[i])[1:-1]
    s=s.replace(' ','')
    s=s.replace(',',' ')
    #print(s)
    sh.sendline(s.encode())
    Cx=(eval(sh.recvline()))
    Hx=(eval(sh.recvline()))
    Cxarr.append((Cx))
    Hxarr.append((Hx))
f39=None
f78=None
Tfinal=None
from tqdm import *
avail=[]
for T in trange(60):
    M39=[list(Rq39(Hxarr[T])*Rq39([0,1])**i) for i in range(39)]
    M39=matrix(M39)
    M=block_matrix(ZZ,[[1,M39],[0,q]])
    M3L=M.BKZ()
    fxtest=list(M3L[0])[:39]
    if(max(fxtest)<=2 and min(fxtest)>=-2):
        avail.append((T,fxtest))
print(f'find {len(avail)} possible')
for T,_f39 in avail:
    M78=[list(Rq78(Hxarr[T])*Rq78([0,1])**i) for i in range(78)]
    M78=matrix(M78)
    M=block_matrix(ZZ,[[1,M78],[0,q]])
    M3L=M.BKZ()
    fxtest=list(M3L[0])[:78]
    if(max(fxtest)<=2 and min(fxtest)>=-2):
        f78=fxtest
        f39=_f39
        Tfinal=T
        break
print(f78)
print(f39)
fx=None
for i in range(-77,78):
    if(fx):
        break
    for j in range(-38,39):
        y39x=Rq39(f39)*Rq39([0,1])**j
        y78x=Rq78(f78)*Rq78([0,1])**i
        y39x=O7(list(y39x))
        y78x=O7(list(y78x))
        yguess=crt([y39x,y78x],[x_**39+1,x_**78-x_**39+1])
        ylist=list(yguess)
        yset=set(ylist)
        vecy=vector(GF(1091),ylist)
        if(yset=={0,1,1090}):
            fx=Rq(ylist)
            print(fx)
            break
def balancemodlist(List,p):
    for i in range(len(List)):
        if int(List[i]) > p / 2:
            List[i] = int(List[i]) - p
    return List
def decrypt(f,fp,c):
    m = Rq(balancemodlist((Rp(balancemodlist((f * c).list(),q)) * fp).list(),p))
    return m

print(list(fx))
fp = (1 / Rp(O8(balancemodlist(fx.list(),q))))
s=decrypt(fx,fp,Rq(Cxarr[Tfinal]))
print(list(s))
lists=list(s)
ans=0
for i in range(len(lists)):
    ans+=min(2,Integer(s[i]))*3**i
sh.recvuntil(b"You wanner say something? :")
sh.sendline(hex(ans)[2:].encode())
print(sh.recvall())