2024-网鼎杯-wp-crypto

一场都没有打，但是从其他师傅那里拿到题发现题目质量似乎越来越高，这里记录几个上手尝试了的。

白虎组

Crypto3

题目：

from bfv.batch_encoder import BatchEncoder
from bfv.bfv_encryptor import BFVEncryptor
from bfv.bfv_decryptor import BFVDecryptor
from bfv.bfv_key_generator import BFVKeyGenerator
from bfv.bfv_parameters import BFVParameters 
from util.polynomial import Polynomial
from util.ciphertext import Ciphertext
import os

degree = 128 
plain_modulus = 257
ciph_modulus = 0x9000000000000

def unpad(msg):
    for i in range(len(msg)):
        if msg[i] != 0: 
            return bytes(msg[i:])

def init(degree,plain_modulus,ciph_modulus):
    params = BFVParameters(poly_degree=degree,
                            plain_modulus=plain_modulus,
                            ciph_modulus=ciph_modulus)
    encoder = BatchEncoder(params)
    key_generator = BFVKeyGenerator(params)

    public_key = key_generator.public_key
    secret_key = key_generator.secret_key
    
    encryptor = BFVEncryptor(params, public_key)
    decryptor = BFVDecryptor(params,secret_key)
    return encryptor,decryptor,encoder

def check(msg):
    p,n = 3**40 + 118, 1337 
    for c in msg:
        if c == '+': n += n
        elif c == '*': n *= n
        n %= p
    return n == 31337

def main():
    encryptor,decryptor,encoder = init(degree,plain_modulus,ciph_modulus)
    for _ in range(2):
        option = input("Option: ")[:1].upper()
        if option == "E":
            msg = os.urandom(degree)
            encoded_msg = encoder.encode(list(msg))
            cipher = encryptor.encrypt(encoded_msg)
            print(f"plain = {msg.hex()}\ncipher = {cipher}")

        elif option == "D":
            c0 = Polynomial(degree,list(map(int,input("c0: ")
                                            .strip().split(", "))))

            c1 = Polynomial(degree,list(map(int,input("c1: ")
                                            .strip().split(", "))))

            cipher = Ciphertext(c0, c1)
            encoded_msg = decryptor.decrypt(cipher) 
            msg = unpad(encoder.decode(encoded_msg)).decode()
            if check(msg):
                try:
                    f = open("/flag.txt","r")
                    print("flag is: ",f.read())
                except:
                    print("flag is: flag{xxxxxxxx}")

        else:
            exit(0)

main()

题目基于bfv，有关bfv的一些基础可以参考：

FHE全同态加密算法学习-BFV | tl2cents blog (tanglee.top)

而对于这个题目来说，为了让我们拿到flag，提供了两次交互机会：

• 第一次发送”E”，靶机会随机产生一个128字节的明文msg，靶机会发回该明文以及对他的bfv加密结果

• 第一次发送”D”，可以输入密文多项式(c0，c1)，靶机会对他做解密之后做decode并且解填充，之后检查msg是不是满足：

  def check(msg):
      p,n = 3**40 + 118, 1337 
      for c in msg:
          if c == '+': n += n
          elif c == '*': n *= n
          n %= p
      return n == 31337

  满足则可以拿到flag

解开本题的关键在于了解bfv的加密是什么样的。

明密文空间

本题的明文空间和密文空间分别是：

$$R_p : \quad \frac{Z_{p}[x]}{x^{128}+1} \quad ,\quad p=257$$ $$R_q : \quad \frac{Z_{q}[x]}{x^{128}+1} \quad ,\quad q=0x9000000000000$$

密钥

bfv的公钥是一个二元组$(PK_1,PK_2)$，满足：

$$PK_1 = -(SK \cdot a + e)$$ $$PK_1 = a$$

$a$是$R_q$下的随机多项式，$SK,e$是小系数多项式，系数由$1,0,-1$组成。

加解密

给定一个msg，加密方式为将他编码成一个$R_p$上的多项式$m$之后，做：

$$c_0 = PK_1 \cdot u + e_1 + \Delta m$$ $$c_1 = PK_2 \cdot u + e_2$$

其中$\Delta = \lfloor \frac{q}{p} \rfloor$，完整的密文为$c_0,c_1$组成的二元组$(c_0,c_1)$。

解密则是做：

$$m' = \lfloor \frac{1}{\Delta}\cdot (c_0 + c_1 \cdot SK) \rceil$$

之后将$m’$转回$R_p$即可恢复$m$。

可以发现解密中对误差处理的方式其实非常类似NTRU

解题

回到题目，在第一次交互发送”E”之后，我们得到了明文msg以及对应的密文$c_0,c_1$，这等价于我们拥有了：

$$m$$ $$c_0 = PK_1 \cdot u + e_1 + \Delta m$$ $$c_1 = PK_2 \cdot u + e_2$$

而我们想要伪造出一个指定消息的密文，也就是要密文解密出来的结果是$m’$，而对照一下加密过程可以发现，我们只需要令：

$$c_0' = c_0 - \Delta m + \Delta m'$$ $$c_1' = c_1$$

就可以满足要求了。

所以核心问题在于如何求出需要的$m’$来，我们知道它满足：

def check(msg):
    p,n = 3**40 + 118, 1337 
    for c in msg:
        if c == '+': n += n
        elif c == '*': n *= n
        n %= p
    return n == 31337

也就是在模p下，如何只用乘2和平方两个操作，使1337在128步以内到达31337。在这个问题放在指数上会比较简单，我们令：

$$g^a = 1337 \quad , \quad g^b = 31337$$

以及：

$$g^t = 2$$

那么对于$g^k$来讲，乘2和平方在指数上就分别对应于：

$$g^k \rightarrow g^{k+t}$$ $$g^k \rightarrow g^{2k}$$

p并不大，p-1的因子更小，所以dlp很好求，所以此时问题转换为：在模p-1下，如何只用+t和乘2两个操作，使a在128步以内到达31337。而转换后的问题显然简单很多，由于p-1是64bit的，我们就让：

$$b = 2^{64}a + rt \quad(mod\;p-1)$$

我们显然能求出r，而$2^{64}$每次乘2都对应于一个乘号，之后按r的二进制就可以知道哪些乘号之后有加的操作，如此一来我们就找到了满足要求的msg，并在之前填充上全0使得其长度为128即可。

之后就是按前述步骤伪造密文即可，需要注意的一点是，明文的encode多项式是fft表示的，而密文是系数表示，所以要对应上才行。

exp：

from bfv.batch_encoder import BatchEncoder
from bfv.bfv_encryptor import BFVEncryptor
from bfv.bfv_decryptor import BFVDecryptor
from bfv.bfv_key_generator import BFVKeyGenerator
from bfv.bfv_parameters import BFVParameters 
from util.polynomial import Polynomial
from util.ciphertext import Ciphertext

d = 128 
p = 257
q = 0x9000000000000

def init(degree,plain_modulus,ciph_modulus):
    params = BFVParameters(poly_degree=degree,
                            plain_modulus=plain_modulus,
                            ciph_modulus=ciph_modulus)
    encoder = BatchEncoder(params)
    key_generator = BFVKeyGenerator(params)

    public_key = key_generator.public_key
    secret_key = key_generator.secret_key
    
    encryptor = BFVEncryptor(params, public_key)
    decryptor = BFVDecryptor(params,secret_key)
    return encryptor,decryptor,encoder

encryptor,decryptor,ENCODER = init(d,p,q)

delta = q // p
PRq = PolynomialRing(Zmod(q), 'xq')
PRp = PolynomialRing(Zmod(p), 'xp')
PRz = PolynomialRing(ZZ, 'x')
x = PRz.gens()[0]
mod_polynomial = x^d + 1
PRqm = PRq.quotient(mod_polynomial)
PRpm = PRp.quotient(mod_polynomial)

from Crypto.Util.number import *
from pwn import *

context.log_level = "critical"
sh = remote("node7.anna.nssctf.cn", 24345)

######################################################################################### send E
sh.recvuntil(b"Option: ")
sh.sendline(b"E")

sh.recvuntil(b"plain = ")
plain = sh.recvline().strip().decode()
plain = bytes.fromhex(plain)
plain_f = str(ENCODER.encode(plain))
plain_f = plain_f.replace("x", "*x").replace("^", "**")
plain_f = PRq(eval(plain_f))

sh.recvuntil(b"cipher = ")
sh.recvuntil(b"c0: ")
c0 = sh.recvline().strip().decode()
c0 = c0.replace("x", "*x").replace("^", "**")
c0 = PRq(eval(c0))
sh.recvuntil(b"c1: ")
c1 = sh.recvline().strip().decode()
c1 = c1.replace("x", "*x").replace("^", "**")
c1 = PRq(eval(c1))

######################################################################################### calc msg
def check(msg):
    p,n = 3**40 + 118, 1337 
    for c in msg:
        if c == '+': n += n
        elif c == '*': n *= n
        n %= p
    return n == 31337

p,n = 3**40 + 118, 1337 
Fp = GF(p)
g = Fp.primitive_element()
t = discrete_log(Fp(2), Fp(g)) # g^t = 2
a = discrete_log(Fp(1337), Fp(g)) # g^a = 1337
b = discrete_log(Fp(31337), Fp(g)) # g^b = 31337

s = ((b-2^64*a) * inverse(t//2, p-1) % (p-1)) // 2 # s*t = b-2^64*a
assert s*t % (p-1) == (b-2^64*a) % (p-1)

msg = ""
for i in range(64):
    msg += "*"
    if(bin(s)[2:].zfill(64)[i] == "1"):
        msg += "+"
msg = b"\x00"*(d-len(msg)) + msg.encode()
msg_f = str(ENCODER.encode(msg))
msg_f = msg_f.replace("x", "*x").replace("^", "**")
msg_f = PRq(eval(msg_f))

######################################################################################### forge msg
C0 = c0 - plain_f*delta + msg_f*delta
C0_send = str(C0.list())[1:-1]
C1_send = str(c1.list())[1:-1]

######################################################################################### send D
sh.recvuntil(b"Option: ")
sh.sendline(b"D")
sh.recvuntil(b"c0: ")
sh.sendline(C0_send.encode())
sh.recvuntil(b"c1: ")
sh.sendline(C1_send.encode())
print(sh.recvline())


#NSSCTF{fa6c7373-c17e-42ac-a903-7dcb94dd69ce}

朱雀组

Crypto1

题目：

from sage.all import *
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from secret import flag

std_limit = 0.01


def get_accurate_Discrete_Gaussian(sigma, limit=std_limit):
    factor = 1
    while True:
        Df = DiscreteGaussianDistributionIntegerSampler(sigma * factor)
        if abs(RR(std([Df() for _ in range(2 ** 15)])) - sigma) / sigma < limit:
            return Df
        factor += 0.01


def ZZ_to_Fq(_vector, _q, _n):
    return [int(i % _q) if abs(_q - int(i % _q)) > int(i % _q) else (int(i % _q) - _q) for i in _vector] + [0] * (
            _n - len(_vector))


def My_generator(Sampler, _n, limit=std_limit):
    while True:
        tmp = [Sampler() for _ in range(_n)]
        if abs(RR(std(tmp)) - Sampler.sigma) < limit:
            return tmp


def generate_key():
    while True:
        F = Matrix([[PRz(My_generator(Df, d)) for _ in range(n)] for _ in range(n)])
        G = Matrix([[PRz(My_generator(Df, d)) for _ in range(k)] for _ in range(n)])
        try:
            H = F.change_ring(PRqm).inverse() * G.change_ring(PRqm)
            H = Matrix([[PRz(Hij.lift()) for Hij in Hi] for Hi in H.transpose()]).transpose()
            return F, G, H
        except ArithmeticError:
            continue


d = 64
q = 12289
p = 17
n = 2
k = 1
sigma_f, sigma_s, sigma_e = 0.4, 0.6, 0.6

PRq = PolynomialRing(Zmod(q), 'xq')
PRp = PolynomialRing(Zmod(p), 'xp')
PRz = PolynomialRing(ZZ, 'xz')
mod_polynomial = PRz.cyclotomic_polynomial(d * 2)
PRqm = PRq.quotient(mod_polynomial)
PRpm = PRp.quotient(mod_polynomial)
Df = get_accurate_Discrete_Gaussian(sigma_f)
Ds = get_accurate_Discrete_Gaussian(sigma_s)
De = get_accurate_Discrete_Gaussian(sigma_e)
m = []
base = int.from_bytes(flag, byteorder='big')
while base > 0:
    m.append(int(base % p))
    base = base // p
m = PRz(m)

s = vector([PRz(My_generator(Ds, d)) for _ in range(n)])
e = PRz(My_generator(Ds, d))
open('data.txt', 'w').write('H = ' + str([list(vi) for vi in H]) + '\n' + 'c = ' + str(c) + '\n')

output.txt：

H = [[10338*xz^63 + 5659*xz^62 + 7251*xz^61 + 7632*xz^60 + 8142*xz^59 + 363*xz^58 + 3634*xz^57 + 2947*xz^56 + 9288*xz^55 + 1867*xz^54 + 5690*xz^53 + 4934*xz^52 + 2322*xz^51 + 11697*xz^50 + 8113*xz^49 + 5472*xz^48 + 8651*xz^47 + 1450*xz^46 + 7334*xz^45 + 10656*xz^44 + 9694*xz^43 + 6701*xz^42 + 124*xz^41 + 2283*xz^40 + 966*xz^39 + 8835*xz^38 + 1720*xz^37 + 5065*xz^36 + 6857*xz^35 + 8343*xz^34 + 11548*xz^33 + 1665*xz^32 + 9899*xz^31 + 5937*xz^30 + 7553*xz^29 + 9893*xz^28 + 6033*xz^27 + 5261*xz^26 + 7621*xz^25 + 4421*xz^24 + 2302*xz^23 + 8276*xz^22 + 8207*xz^21 + 8804*xz^20 + 6810*xz^19 + 6386*xz^18 + 11503*xz^17 + 1009*xz^16 + 8225*xz^15 + 4103*xz^14 + 1221*xz^13 + 6719*xz^12 + 1078*xz^11 + 12276*xz^10 + 2439*xz^9 + 10249*xz^8 + 8729*xz^7 + 586*xz^6 + 5458*xz^5 + 1390*xz^4 + 883*xz^3 + 3545*xz^2 + 7612*xz + 6526], [7467*xz^63 + 1749*xz^62 + 581*xz^61 + 10547*xz^60 + 10587*xz^59 + 4082*xz^58 + 12278*xz^57 + 6510*xz^56 + 10619*xz^55 + 1234*xz^54 + 9068*xz^53 + 6259*xz^52 + 9917*xz^51 + 2929*xz^50 + 9486*xz^49 + 3623*xz^48 + 10823*xz^47 + 3410*xz^46 + 1739*xz^45 + 7184*xz^44 + 2134*xz^43 + 1225*xz^42 + 4494*xz^41 + 6443*xz^40 + 11111*xz^39 + 6039*xz^38 + 2081*xz^37 + 5900*xz^36 + 7868*xz^35 + 9967*xz^34 + 9020*xz^33 + 267*xz^32 + 9958*xz^31 + 1727*xz^30 + 11266*xz^29 + 8962*xz^28 + 8017*xz^27 + 442*xz^26 + 7393*xz^25 + 11646*xz^24 + 2781*xz^23 + 12150*xz^22 + 1683*xz^21 + 11684*xz^20 + 3116*xz^19 + 97*xz^18 + 2427*xz^17 + 10442*xz^16 + 4564*xz^15 + 1257*xz^14 + 7279*xz^13 + 948*xz^12 + 600*xz^11 + 9812*xz^10 + 2646*xz^9 + 3120*xz^8 + 3788*xz^7 + 10679*xz^6 + 11350*xz^5 + 4268*xz^4 + 2544*xz^3 + 8194*xz^2 + 11682*xz + 2468]]
c = 11137*xz^63 + 3950*xz^62 + 11472*xz^61 + 1420*xz^60 + 1644*xz^59 + 1735*xz^58 + 4207*xz^57 + 3488*xz^56 + 4679*xz^55 + 5384*xz^54 + 9774*xz^53 + 2638*xz^52 + 5163*xz^51 + 9623*xz^50 + 5275*xz^49 + 10991*xz^48 + 3953*xz^47 + 2673*xz^46 + 5974*xz^45 + 1789*xz^44 + 8974*xz^43 + 11827*xz^42 + 9371*xz^41 + 9856*xz^40 + 7715*xz^39 + 2132*xz^38 + 155*xz^37 + 11099*xz^36 + 2711*xz^35 + 3342*xz^34 + 3754*xz^33 + 14*xz^32 + 8853*xz^31 + 10130*xz^30 + 3582*xz^29 + 10280*xz^28 + 6135*xz^27 + 11024*xz^26 + 1591*xz^25 + 1310*xz^24 + 6936*xz^23 + 10754*xz^22 + 10007*xz^21 + 7388*xz^20 + 9773*xz^19 + 3045*xz^18 + 11749*xz^17 + 11162*xz^16 + 12106*xz^15 + 946*xz^14 + 5087*xz^13 + 10047*xz^12 + 10162*xz^11 + 10073*xz^10 + 897*xz^9 + 8104*xz^8 + 11379*xz^7 + 3784*xz^6 + 5291*xz^5 + 2350*xz^4 + 12281*xz^3 + 1941*xz^2 + 5903*xz + 11188

题目基于MNTRU，其密钥生成过程为：

• 建立三个多项式环：

  $$PRqm = \frac{Z_q[x]}{x^{64}+1}$$ $$PRpm = \frac{Z_p[x]}{x^{64}+1}$$ $$PRz = \frac{Z[x]}{x^{64}+1}$$

  其中$q=12289,p=17$

• 生成多个满足高斯分布的小系数多项式，用这些元素组成：

  $$F_{2\times2} , G_{2 \times 1}$$

  当$F$在$PRqm$下可逆时，计算：

  $$H = F^{-1}G$$

  得到的$H$就是公钥

• 之后将flag编码成$PRz$下的多项式$m$

• 最后生成由满足高斯分布的小系数多项式组成的向量：

  $$\textbf{s}_{1\times 2}$$

  并且令一个小系数多项式为$e$，应该是加密会用到的小误差，接下来不出意外是要进入加密过程了

诶？我加密过程呢？

很绷不住，这个题在生成完这一系列参数之后，直接就给出了密文，加密过程不知道落到哪里去了。

我猜是把decrypt函数删了，结果不小心把encrypt也删了

所以说这加密方式整的还得靠猜，很无语，想了一下觉得前半部分代码还挺整齐，估计是有按照什么文章标准实现过的，所以搜了下论文找到了：

732.pdf (iacr.org)

论文提到的加密方式为：

$$c = pH^T\textbf{r} + pe + m$$

那么不妨试一试这个加密吧，对于这个题目的表示来说，也就等价于：

$$c = p\textbf{s}H + pe + m$$

把这个结构中的公钥拆开，有利于观察解密：

$$c = p\textbf{s}F^{-1}G + pe + m$$

解密很简单，论文中也有提到，我们先同时乘上$det(F)$，注意是在$PRqm$下：

$$|F|c = |F|p\textbf{s}F^{-1}G + |F|pe + |F|m$$

由于：

$$F^{-1} = \frac{1}{|F|}F^*$$

所以有：

$$|F|F^{-1} = F^*$$

而$F$是小系数多项式组成的矩阵，那么$F^{*}$也应该如此，这对于二阶矩阵尤其明显，因为求伴随矩阵只涉及每个元素位置和正负号的改变，所以此时得到：

$$|F|c = p\textbf{s}F^*G + |F|pe + |F|m$$

由于$\textbf{s},F^*,G,e$全都很小，$m$也不大，所以此时式子是在$PRz$上成立的，因此可以把整个式子放到$PRpm$下，模p就全部没有了，就得到：

$$|F|c = |F|m$$

此时将$|F|$求逆再乘至左侧就可以还原$m$了。

其实这个和论文中的标准解密并不一样，因为论文中对于keygen中的$F$有额外设计，但是这里没有，所以要自己加上最后这个步骤

那么对于题目来讲，我们只有公钥$H$，要想办法求出等价的密钥$F’,G’$使得满足：

$$H = F'^{-1}G'$$

那么此时加密过程等价于：

$$c = p\textbf{s}F'^{-1}G' + pe + m$$

所以只要我们求出的$F’,G’$满足大小要求就可以正确解密了。而要找到足够小的$F’,G’$方法当然是用格来做，主要是利用：

$$FH = G \quad (in \; \frac{Z_q[x]}{x^{64}+1})$$

去在商环下做BKZ规约即可，blocksize调大一些就能找到满足条件的等价密钥了。之后进行解密发现确实能得到flag，所以加密方式应该就是这样。

我在NSSCTF上传了一个fixed的版本，有兴趣的师傅可以复现fixed的，就可以跳过猜谜环节

exp：

from Crypto.Util.number import *

#part1 construct matrix of poly_mul

#n:The highest degree of a modular polynomial
#v:vector of modular polynomial
#a:vector of a polynomial multiplier

#aim to construct a matrix of c=a*b%v
def construct_poly_mul_mat(n,v,b):
    assert v[-1] == 1 #use this after monic

    #step1 construct a matrix of d=a*b
    mat1 = Matrix(ZZ,n,2*n-1)
    for i in range(n):
        for j in range(n):
            mat1[i,j+i] = b[j] 

    #step2 construct a matrix of c=d%v
    mat2 = Matrix(ZZ,2*n-1,n)
    for i in range(n):
        mat2[i,i] = 1
    for i in range(n,2*n-1):
        for j in range(i-n,n):
            mat2[i,j] = -v[j-(i-n)]
        
        init_row = vector(ZZ,n*[0])
        for j in range(i-n):
            temp = -v[n-1-j]*vector(ZZ,mat2[i-j-1])
            init_row += temp
        for j in range(n):
            mat2[i,j] += init_row[j]   
             
    #step3 multiply them and return
    return(mat1*mat2)

PRz.<xz> = PolynomialRing(ZZ)

H = [[340*xz^63 + 6589*xz^62 + 9575*xz^61 + 4261*xz^60 + 9906*xz^59 + 11186*xz^58 + 5860*xz^57 + 6300*xz^56 + 4276*xz^55 + 8065*xz^54 + 210*xz^53 + 7651*xz^52 + 3878*xz^51 + 11603*xz^50 + 377*xz^49 + 430*xz^48 + 10266*xz^47 + 8188*xz^46 + 5862*xz^45 + 2120*xz^44 + 10826*xz^43 + 9725*xz^42 + 8649*xz^41 + 7542*xz^40 + 4844*xz^39 + 8890*xz^38 + 3557*xz^37 + 3464*xz^36 + 6286*xz^35 + 339*xz^34 + 1568*xz^33 + 3339*xz^32 + 9565*xz^31 + 902*xz^30 + 11481*xz^29 + 10054*xz^28 + 11924*xz^27 + 7489*xz^26 + 8207*xz^25 + 10399*xz^24 + 294*xz^23 + 2985*xz^22 + 10059*xz^21 + 114*xz^20 + 3318*xz^19 + 10651*xz^18 + 7350*xz^17 + 8787*xz^16 + 11489*xz^15 + 7445*xz^14 + 5324*xz^13 + 4422*xz^12 + 6575*xz^11 + 8443*xz^10 + 7554*xz^9 + 6439*xz^8 + 1488*xz^7 + 6768*xz^6 + 5127*xz^5 + 750*xz^4 + 9322*xz^3 + 5255*xz^2 + 4156*xz + 4291], [6189*xz^63 + 9351*xz^62 + 11071*xz^61 + 8053*xz^60 + 2746*xz^59 + 5677*xz^58 + 5943*xz^57 + 4387*xz^56 + 407*xz^55 + 1577*xz^54 + 9989*xz^53 + 1726*xz^52 + 6740*xz^51 + 5127*xz^50 + 5901*xz^49 + 5004*xz^48 + 9808*xz^47 + 2810*xz^46 + 10420*xz^45 + 4875*xz^44 + 5158*xz^43 + 1833*xz^42 + 4553*xz^41 + 10006*xz^40 + 4791*xz^39 + 878*xz^38 + 2751*xz^37 + 4081*xz^36 + 9118*xz^35 + 8861*xz^34 + 5331*xz^33 + 5666*xz^32 + 7687*xz^31 + 11612*xz^30 + 5272*xz^29 + 6484*xz^28 + 5476*xz^27 + 9345*xz^26 + 232*xz^25 + 11574*xz^24 + 4098*xz^23 + 6049*xz^22 + 11200*xz^21 + 4069*xz^20 + 1174*xz^19 + 623*xz^18 + 8097*xz^17 + 8936*xz^16 + 9210*xz^15 + 59*xz^14 + 10331*xz^13 + 125*xz^12 + 9892*xz^11 + 5265*xz^10 + 8680*xz^9 + 2033*xz^8 + 7892*xz^7 + 11764*xz^6 + 11402*xz^5 + 10937*xz^4 + 3805*xz^3 + 264*xz^2 + 4073*xz + 11142]]
c = 11253*xz^63 + 6375*xz^62 + 3301*xz^61 + 1515*xz^60 + 4564*xz^59 + 5340*xz^58 + 1877*xz^57 + 7208*xz^56 + 10575*xz^55 + 11607*xz^54 + 4932*xz^53 + 7070*xz^52 + 10676*xz^51 + 11171*xz^50 + 4221*xz^49 + 10963*xz^48 + 6195*xz^47 + 11489*xz^46 + 734*xz^45 + 2749*xz^44 + 3224*xz^43 + 6341*xz^42 + 10369*xz^41 + 9646*xz^40 + 2654*xz^39 + 9068*xz^38 + 2065*xz^37 + 6202*xz^36 + 4976*xz^35 + 7781*xz^34 + 7385*xz^33 + 8779*xz^32 + 10589*xz^31 + 1649*xz^30 + 6891*xz^29 + 1467*xz^28 + 8305*xz^27 + 3161*xz^26 + 4675*xz^25 + 7001*xz^24 + 7618*xz^23 + 2312*xz^22 + 1400*xz^21 + 2579*xz^20 + 959*xz^19 + 4575*xz^18 + 695*xz^17 + 6919*xz^16 + 5992*xz^15 + 272*xz^14 + 9179*xz^13 + 9188*xz^12 + 10138*xz^11 + 8342*xz^10 + 10160*xz^9 + 6264*xz^8 + 1513*xz^7 + 1860*xz^6 + 9258*xz^5 + 3903*xz^4 + 5820*xz^3 + 7053*xz^2 + 4386*xz + 11507
q = 12289
p = 17
n = 64

PRq = PolynomialRing(Zmod(q), 'xq')
PRp = PolynomialRing(Zmod(p), 'xp')
mod_polynomial = PRz.cyclotomic_polynomial(64 * 2)
PRqm = PRq.quotient(mod_polynomial)
PRpm = PRp.quotient(mod_polynomial)

n = 64
PRq.<x> = PolynomialRing(Zmod(q))
f = x^n + 1
v = f.list()

H1 = construct_poly_mul_mat(n,v,H[0][0].list())
H2 = construct_poly_mul_mat(n,v,H[1][0].list())
# F(0,0)H1 + F(0,1)H2 = G(0,0)
# -> BKZ

L = block_matrix(ZZ, [
    [identity_matrix(n), matrix.zero(n,n), H1],
    [matrix.zero(n,n), identity_matrix(n), H2],
    [matrix.zero(n,n), matrix.zero(n,n), identity_matrix(n)*q]
])
L = L.BKZ(block_size=30)

Found = 0
for i in range(128):
    for j in range(i+1,128):
        F = Matrix(PRz, [
            [list(map(int,L[i][:n])), list(map(int,L[i][n:2*n]))],
            [list(map(int,L[j][:n])), list(map(int,L[j][n:2*n]))]
        ])

        G = Matrix(PRqm, [
            [list(map(int,L[i][-n:]))],
            [list(map(int,L[j][-n:]))]
        ])

        FF = Matrix(PRqm,2,2)
        for ii in range(2):
            for jj in range(2):
                FF[ii,jj] = PRqm(F[ii,jj])

        FFF = Matrix(PRpm,2,2)
        for ii in range(2):
            for jj in range(2):
                FFF[ii,jj] = PRpm(F[ii,jj])

        if(FF.det() != 0):
            Found = 1
            print(i,j)
            print(L[i].norm())
            print(L[j].norm())
            print((FF^(-1)*G).list())
            print(H)
            break
    if(Found == 1):
        break

from itertools import *

def ZZ_to_Fq(_vector, _q, _n):
    return [int(i % _q) if abs(_q - int(i % _q)) > int(i % _q) else (int(i % _q) - _q) for i in _vector] + [0] * (
            _n - len(_vector))

PRp = PolynomialRing(Zmod(p), 'xp')
PRpm = PRp.quotient(mod_polynomial)
xp = PRp.gens()[0]

m = FF.det()*(PRqm(c.list()))
mmm = ZZ_to_Fq(m.list(), q, n)
mmmm = (PRpm(mmm)*(FFF.det()^(-1))).list()

flag = 0
for tt in range(len(mmmm)):
    flag += int(mmmm[tt])*p^tt
flag = long_to_bytes(flag)
print(flag)


#wdflag{1cfa5581d8c6add650d1a318}

玄武组

Crypto1

题目：

# SageMath version 10.0, Release Date: 2023-05-20

from sage.all import *
from Crypto.Util.number import *

from secret import flag
flag = flag.lstrip(b"NSSCTF{").rstrip(b"}")

class ShamirSS:
    def __init__(self, coefs, value):
        self.coefs = coefs
        self.value = value

class ShamirProtocol:
    def __init__(self, n_players, threshold, modulus):
        self.n_players = n_players
        self.threshold = threshold
        
        assert isPrime(modulus), "Modulus must be a prime number"
        self.modulus = modulus
        
        
    def input_share(self, values):
        coefs = [
            [getRandomRange(1, self.modulus) for _ in range(self.threshold)]
            for _ in range(self.n_players)
        ]

        randoms = values + [getRandomRange(1, self.modulus) for _ in range(self.threshold - len(values))]

        values = [
            sum([r * c for r, c in zip(randoms, coef)]) % self.modulus
            for coef in coefs
        ]

        shares = [ShamirSS(coef, value) for coef, value in zip(coefs, values)]
        return shares
    


protocol = ShamirProtocol(len(flag), len(flag) * 2, 257)
values = list(flag)

import os
os.mkdir("shares")

for i in range(10000):
    shares = protocol.input_share(values)
    save(shares, f"shares/share_{i}.sobj")

题目基于Shamir门限方案，一眼看过去似乎一切都很正常，就是Shamir秘密分享而已。

但是细看会发现player和threshold似乎反了，一般来说，假设Shamir共享的秘密是一个度为d的多项式，那么应该设置d的shreshold，然后由大于d的player每个人持有一个多项式函数点对，凑够threshold就可以插值出多项式从而恢复秘密值了。

而这个题目呢？他进行了10000轮的Shamir秘密分享，而每一轮的流程是（设flag长度为n）：

• 设置player数量为n

• 设置threshold为2n

• 生成coefs，其由n个模257下的随机数列表组成，每个列表长为2n，记这些长为2n的向量为$\textbf{c}_i$

• 生成randoms，其长度为2n，前n个为flag，后n个为模257下的随机数，记为$\textbf{r}$

• 计算：

  $$v_i = \textbf{r} \cdot \textbf{c}_i$$

  给出每一轮的$\textbf{c}_i$和$v_i$，要求还原$\textbf{r}$

解题

首先从输出长度可以判断出n的具体值，之后对于每一轮的Shamir秘密分享，可以把所有向量的点积拼成一个矩阵乘法：

$$\textbf{r}_{1\times 2n} \cdot C_{2n\times n} = \textbf{v}_{1\times n}$$

等式只有变量数量的一半，所以直接求矩阵方程肯定不行。但是注意到$\textbf{r}$的前半段就是flag，因此我们可以把整个矩阵乘法拆成下面的形式：

$$(\textbf{f | g}) \cdot (\frac{A_{n\times n}}{B_{n\times n}}) = \textbf{v}$$

这等价于：

$$\textbf{f} \cdot A + \textbf{g} \cdot B = \textbf{v}$$

而当$B$不满秩时，如下的方程有非零解：

$$Bx = 0$$

记非零解为$\textbf{s}$，那么有：

$$\textbf{f} \cdot A \cdot \textbf{s} + \textbf{g} \cdot B \cdot \textbf{s} = \textbf{v} \cdot \textbf{s}$$

也就是：

$$\textbf{f} \cdot A \cdot \textbf{s} = \textbf{v} \cdot \textbf{s}$$

此时我们就消掉了后半段$\textbf{g}$的影响，得到了一组关于flag向量的方程，也就是说我们可以对每一轮的Shamir去检查$B$是否满秩，不满秩就可以得到一组方程，收集足够数量的方程就可以解出flag了。

exp：

from Crypto.Util.number import *
from tqdm import *

class ShamirSS:
    def __init__(self, coefs, value):
        self.coefs = coefs
        self.value = value

shares = []
for i in trange(10000):
    files = "share_" + str(i) + ".sobj"
    sharesi = load(files)
    shares.append(sharesi)

def convert_2_Matrix(single_share):
    L = []
    R = []
    for i in single_share:
        L.append(i.coefs)
        R.append(i.value)
    L = Matrix(Zmod(257), L)
    R = vector(Zmod(257), R)
    A = L[:, :36]
    B = L[:, 36:]
    if(B.rank() != 36):
        v = B.left_kernel().basis()[0]
        return (v*A, v*R)

L = Matrix(Zmod(257), 0, 36)
R = []
for i in tqdm(shares):
    res = convert_2_Matrix(i)
    if(res != None):
        l, r = res
        L = L.stack(l)
        R.append(r)
R = vector(Zmod(257), R)

flag = L.solve_right(R)
print("".join(list(map(chr, flag))))


#7d988e52-c2ab-4370-893f-3f2a89861f0f

概率分析

实际测试一下可以发现，虽然题目的1w组数据给出了足够的36个B不满秩情形对应的方程，但是有时候数据是并不足够的：

p = 257
n = 36
for time in range(10):
    count1 = 0
    for i in range(10000):
        A = random_matrix(Zmod(p), n, n)
        if(A.rank() != n):
            count1 += 1
    print(count1)

34
46
36
36
37
40
44
53
35
39

如果在数据不满的情况下（一般也会有30多组），结合flag长度是36，所以可以推测应该是uuid形的，所以可以确定四个”-“字符的位置，还不够的时候就再爆几个十六进制字符。

那么B不满秩的概率究竟是多少呢？从反面想会比较简单，对于一个$F_p$下的$n\times n$矩阵来说，将他看作$n$个行向量，我们想办法计算他满秩的概率。

首先，对于第一个行向量，其一定不能为0向量，因此其可以选择的向量共有：

$$p^n - 1$$

而对于第二个行向量，要保证整个矩阵一定满秩，他既不能是0向量，也不能是第一个行向量的线性表示，因此他能选择的向量范围有：

$$p^n - 1 - (p-1) = p^n - p$$

这里是p-1是因为线性表示没有包含0倍的第一行向量，不然0向量会重复

同理，对于第三个行向量，要保证整个矩阵一定满秩，他既不能是0向量，也不能是前两个行向量的线性表示，所以他能选择的向量范围是：

$$p^n - 1 - 2(p-1) - (p-1)^2 = p^n - p^2$$

其中，1表示0向量，$2(p-1)$表示仅由其中一个向量能线性表示的向量，$(p-1)^2$表示由前两个向量系数均非0的线性组合能表示的向量

到这里会发现，其实这样计算显然把问题麻烦化了，因为对于$k$个线性无关的向量来说，其张成的向量空间中有$p^k$个向量，接下来向量选择的范围就是在$p^n$中把这些线性有关的子空间删去即可，也就是$p^n-p^k$

因此接下来一直如法炮制，那么最后一个行向量能选择的向量范围是：

$$p^n - p^{n-1}$$

那么整个矩阵满秩的概率就是：

$$\prod_{i=0}^{n-1}{\frac{(p^n - p^i)}{p^n}}$$

因此不满秩序的概率为：

$$P = 1 - \prod_{i=0}^{n-1}{\frac{(p^n - p^i)}{p^n}}$$

上个程序测试一下：

from tqdm import *

count1 = 0
times = 1000000
for i in trange(times):
    A = random_matrix(Zmod(p), n, n)
    if(A.rank() != n):
        count1 += 1
print(count1)

P = 1
for i in range(n):
    P *= (p^n - p^i) / p^n
P = 1 - P
print(int(P*times))

3864
3906

可以看出符合的较好。

进一步可以发现两个事实：

• $P$与矩阵维数n似乎关系不大
• $P$与模数p关系很大

对于题目来讲，B不满秩的情况符合的是一个$(10000, P)$的二项分布，计算一下其不满秩出现的次数大于等于flag长度36的概率大概有$0.709866$，把四个”-“利用上的话，不满秩出现次数大于等于32的概率约为$0.890127$，所以一般来说1w组数据足够了。

运气实在不好，要爆六个十六进制字符及以上的概率大约是0.01出头

*Crypto2

题目：

pkcs1.py：

import os

def encode(message, k, ps=None):
    '''Take a message of length inferior to k - 11 and return
       the concatenation of length k:

        0x00 || 0x02 || PS || 0x00 || message

       where PS is a random string containing no zero byte of length
       k - len(message) - 3.

       message - the message to encode, a byte string
       k - the length of the padded byte string
       ps - a fixed string to use instead of generating a random one, it's
       necessary for testing using test vectors,
       rnd - the random generator to use, it must conform to the interface of
       the random.Random class.
    '''
    m_len = len(message)
    if m_len > k - 11:
        raise Exception('MessageTooLong')
    ps_len = k - len(message) - 3
    if ps:
        if len(ps) != ps_len:
            raise Exception('wrong ps length', len(ps), ps_len)
    else:
        ps = b""
        while len(ps) != ps_len:
            byte = os.urandom(1)
            if byte != b"\x00":
                ps += byte
    return b'\x00\x02' + ps + b'\x00' + message

def decode(message: bytes):
    '''
       Verify that a padded message conform to the PKCSv1 1.5 encoding and
       return the unpadded message.
    '''
    if message[:2] != b'\x00\x02':
        raise Exception('DecryptionError')
    i = message.find(b'\x00', 2)
    if i == -1:
        raise Exception('DecryptionError')
    if i < 10:
        raise Exception('DecryptionError')        
    return message[i+1:]

main.py：

from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from pkcs1 import encode, decode
import os
import hashlib
import signal


FLAG = os.getenv("FLAG", "wdflag{******************************}")

class RSA_OT:
    
    def __init__(self, key: RSA):
        self.key = key
        self.n = key.n
        self.e = key.e
        self.d = key.d
        self.nbyte = key.size_in_bytes()
        
    @staticmethod
    def new(nbits: int) -> "RSA_OT":
        key = RSA.generate(nbits)
        return RSA_OT(key)
        
    def encrypt(self, message: bytes) -> bytes:
        padded = encode(message, self.nbyte)
        ct = self.key._encrypt(padded)
        return int(ct).to_bytes(self.nbyte, "big")
    
    def decrypt(self, ciphertext: bytes) -> bytes:
        padded = self.key._decrypt(int.from_bytes(ciphertext, "big"))
        return decode(padded)
    
    def show_public_key(self):
        print("[+] n =", self.n)
        print("[+] e =", self.e)
        
    def run(self, m0, m1):
        print("[+] OT Protocol Starts")
        m0 = int.from_bytes(encode(m0, self.nbyte), "big")
        m1 = int.from_bytes(encode(m1, self.nbyte), "big")
        x0 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
        x1 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
        print(f"[+] x0 = {x0}")
        print(f"[+] x1 = {x1}")
        v = int(input("[+] v = "))
        M0 = (m0 + pow(v - x0, self.d, self.n)) % self.n
        M1 = (m1 + pow(v - x1, self.d, self.n)) % self.n
        print(f"[+] M0 = {M0}")
        print(f"[+] M1 = {M1}")
        print("[+] OT Protocol Ends")
        
def xor(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))
        
def challenge(rounds = 70):
    aes_key = os.urandom(32)
    xor_key = os.urandom(32)
    aes = AES.new(aes_key, AES.MODE_ECB)
    rsa_ot = RSA_OT.new(1024)
    secrets = [os.urandom(32) for i in range(rounds)]
    message_pairs = [(aes_key, xor_key)]
    message_pairs += [(aes.encrypt(secret), xor(xor_key, secret)) for secret in secrets]
    signal.alarm(120)
    print("[+] Sharing secrets through aes or xor, I won't know which one is used.")
    rsa_ot.show_public_key()
    for i, (m0, m1) in enumerate(message_pairs):
        print(f"[+] Round {i + 1}")
        rsa_ot.run(m0, m1)
    print("[+] All OTs Done!")
    verify_hash = hashlib.sha256(b''.join(secrets)).hexdigest()
    credential = input("[+] prove that you are honest: ").strip()
    if credential == verify_hash:
        print("[+] You are an honest player.")
    else:
        print("[+] Lies detected.")
        return
    
    master = hashlib.sha256(aes_key + xor_key).hexdigest()
    credential = input("[+] prove that you know both keys: ").strip()
    
    if credential == master:
        print(f"[+] Here is your flag: {FLAG}")
    else:
        print("[+] You are too honest!")
        return

if __name__ == "__main__":
    challenge()

数据生成

题目基于OT，连接上靶机后靶机会生成：

• 32字节的aeskey
• 32字节的xorkey
• 1024bit的RSA公私钥对
• 长度为70的secrets列表，其中每个元素都是随机的32个字节

有了这些量之后，靶机接着生成一个长为71的列表message_pairs，其中元素构成为：

• 第一个值为(aeskey, xorkey)
• 后70个值为AES和XOR分别对secrets列表中每个元素的加密结果构成的二元组

RSA-OT

之后正式进入限时120s的交互， 交互基于1 out of 2的RSA-OT，共71轮。具体一轮交互过程为：

• 输入两个值m0，m1，对于题目来讲这都是32字节的量

• 将两个量分别做PKCS#1 v1.5的encode，得到128字节的m0和m1

  PKCS#1 v1.5的encode结果就是：

  b"\x00\x02" + ps + b"\x00" + m0 (128 bytes)

  其中ps是随机填充的每个字节都不等于0的字节串

• 随机生成128字节的x0，x1并给出

• 我们需要输入一个v，之后靶机会返回：

  $$M_0 = m_0 + (v - x_0)^d \quad(mod\;n)$$ $$M_1 = m_1 + (v - x_1)^d \quad(mod\;n)$$

• 我们的任务是在71轮交互全部完成后，解出所有的secret，并且拿到完整的aeskey和xorkey从而拿到flag

对RSA-OT的基本分析

这个RSA-OT单从返回值来说其实实现的蛮标准，具体来说，如果我们要拿m0的话，我们应该构造：

$$v = k^e + x_0 \quad(mod\;n)$$

其中k是我们选取的随机数，这样子我们拿到的返回值就是：

$$M_0 = m_0 + k \quad(mod\;n)$$ $$M_1 = m_1 + (k^e + x_0- x_1)^d \quad(mod\;n)$$

所以我们只需要将得到的M0减去k就拿到了m0，这样子的交互实现了：

• 我们仅能拿到发放数据的其中一个值
• 发放数据方无法从我们发送的v中判断我们拿了哪一个值

第一点很自然，因为我们没有私钥，自然计算不出$(k^e + x_0- x_1)^d$，也就无法消掉他。

而第二点的话似乎没有那么显然，第一眼可能会觉得，发放数据方有私钥d，把v减去x0之后再做d次方不就得到k了吗？这确实可以得到，然而靶机方把v减去x1之后再做d次方依然可以得到一个数字k’，而他无法区分这两个数究竟哪一个才是我们选择的随机数，所以自然不知道我们拿走了哪一个。

但是要是k选的“很不随机数”，发送数据方当然就有理由做出判断了，比如就令$v=x_0$，那么很显然这次要拿的大概率是$x_0$吧

对于这样的标准OT，想要拿到一些特殊的数据的话，一般来说可以构造：

• 令$v-x_1 = -(v-x_0)$，那么就有：

  $$M_0 = m_0 + (v - x_0)^d \quad(mod\;n)$$ $$M_1 = m_1 + (-(v - x_0))^d = m_1 + -(v - x_0)^d \quad(mod\;n)$$

  此时将两者相加可以拿到：

  $$M_0 + M_1 = m_0 + m_1 \quad(mod\;n)$$

  也就是我们牺牲了拿其中任意一个数据的机会，转而获得了两个数据的和。

• 推而广之，令$v-x_1 = -a^e(v-x_0)$，那么就有：

  $$M_0 = m_0 + (v - x_0)^d \quad(mod\;n)$$ $$M_1 = m_1 + (-a^e(v - x_0))^d = m_1 - a(v - x_0)^d \quad(mod\;n)$$

  所以此时有：

  $$aM_0 + M_1 = am_0 + m_1 \quad(mod\;n)$$

  比如对于这一题，如果m0和m1没有做pkcs填充的话，他们就是32字节的量，那么我们只需要构造：

  $$v-x_1 = -(256^{32})^e(v-x_0)$$

  那么我们就能拿到：

  $$256^{32}m_0 + m_1 = 256^{32}M_0 + M_1 \quad(mod\;n)$$

  也就等于我们一次拿到了两个量

解题

第1轮

首先需要先根据题目信息整合一下思路，构建一个解题的轮廓出来，对于这个题目来说，首先需要思考的大概是以下几个问题：

• 为什么要给70轮的对secrets的交互？
• 为什么要用PKCS#1 v1.5做填充？

两个问题都相当关键，我的思路分别是：

• 每一轮都可以通过构造泄露一定量的某个数据，70轮才可以泄露完全

• 而PKCS#1 v1.5填充正好与上一个问题呼应了起来，因为PKCS#1 v1.5的填充中有三个已知字节：

  b"\x00\x02", b"\x00"

  比起m0，m1是模n下的随机数来说，这样其实会给我们泄露三个字节的额外信息，所以有机会做做文章

此外还有一个比较重要的基本逻辑，在于AES和XOR两种加密方式的不同。可以想象一下在拥有完整的message_pairs列表的情况下：

• 如果有aeskey，那么可以解AES加密的密文得到secret，然后和XOR加密的密文异或得到xorkey
• 如果有xorkey，那么可以解XOR加密的密文得到secret，但是已知AES的明密文显然不能获得aeskey

所以说aeskey的作用显然是比xorkey大的，所以说第一轮OT中没有任何只拿xorkey的道理，要么拿aeskey，要么通过我们刚才的构造去拿一个$am_0+m_1$形式的和。

继续往下推，我们拿这种和有用吗？由于后面的密文中泄露不出任何关于aeskey的信息，所以无论怎么样我们都拿不到aeskey了，因此可以确定第一个基本逻辑点：第一轮只能拿aeskey。

而我们并不关心发送数据方能不能判断我们拿了哪个数据，因此我们就用最简单的构造，也就是：

$$v = x_0$$

此时我们拿到的数据是：

$$M_0 = m_0$$ $$M_1 = m_1 + (x_0-x_1)^d \quad(mod\;n)$$

接下来我们的目的很明确：

• 求出所有secret
• 求出xorkey

第2-71轮

要求出xorkey，有两种可能的方式：

• 拿到message_pairs第2-71轮完整的二元组，这样就可以照刚刚的方式：解AES加密的密文得到secret，然后和XOR加密的密文异或得到xorkey
• 拿到第1轮里的$(x_0-x_1)^d$

而我们同样可以用OT的性质来排除第一种方法，因此我们的目的就变成了求出$(x_0-x_1)^d$来，为了表示方便，后面将这个值记作$K$。

这很巧妙，由于OT的存在，整个求解思路到现在为止其实都是“注定的”，是一条完整的、没有其他路可走的逻辑链条

当然也不能说死没有其他方法，也有可能我的推理哪里出了问题

而要拿到这个值，所有可能可以利用的信息有：

• $M_1,x_0,x_1$
• 公钥$n,e$
• 每一轮的$m_{i,0}, m_{i,1}$都是PKCS#1 v1.5填充的
• 一个70轮的解密oracle

而再看看第1轮的返回值：

$$M_1 = m_1 + K \quad(mod\;n)$$

把K看作一个128字节，由于m1是PKCS#1 v1.5填充的，所以通过M1我们可以得到K的部分字节信息，具体来说也就是前两个字节以及倒数第33个字节。这样一来，我们在第一轮中似乎就得到了K的三个字节的信息。因此我们可以确定接下来的思路：利用PKCS#1 v1.5的填充方式，在后续轮次中泄露K的其他字节。

就以第二轮为例，我们在第二轮中能得到如下的值：

$$x'_{0} \quad x'_{1}$$

有第一轮的经验，我们第二轮的想法就是构造一个v，使得返回的值中可以透过pkcs的填充结构看出K的其他字节，所以我们不妨令：

$$v = 256^{2e}(x_0 - x_1) + x'_0$$

那么就有：

$$M'_0 = m'_0 + (256^{2e}(x_0 - x_1) + x'_0 - x'_0)^d \quad(mod\;n)$$

也就是：

$$M'_0 = m'_0 + 256^{2}K \quad(mod\;n)$$

一个问题在于，$256^2K$显然会超过n，但由于我们第一轮已经获取了K的部分字节，所以我们可以把K写作：

$$M'_0 = m'_0 + 256^{2}(K_{known} + K_{unknown}) \quad(mod\;n)$$

那么我们把已知的部分减去掉之后，剩下的部分就等于：

$$M'_0 - 256^{2}K_{known} = m'_0 + 256^{2}K_{unknown} \quad(mod\;n)$$

这个步骤相当于我们减去了已知的高位，从而又将范围控制在了n的数量级下，此时透过pkcs的填充结构我们又可以得到泄露的K的另外三字节。如此反复下去，K只有128字节，所以总共71轮的交互完全足够泄露K的所有字节了。

而注意到，我们每一轮构造的v并不是标准的OT构造形式，这意味着我们每一轮都拿不到AES加密的密文或者XOR加密的密文。但是从返回值可以看出，我们只要有了完整的K，自然就可以获得每一轮的AES密文，然后就可以获得secret；同时有了K等价于我们有了xorkey，所以就可以通过靶机的所有check，从而拿到flag了。

理想似乎很丰满，然而这个想法存在很多细节上的问题需要处理，这也相当程度上加大了了这个题的难度。

本来就很难了，完全没想到这么构造TT

问题

第一个问题在于，我们每一轮真的能泄露三个字节吗？比如对于第一轮，我们拿到的M1是：

$$M_1 = m_1 + K \quad(mod\;n)$$

这里是加号，而m1我们只知道其三个字节的值，并且高位只知道两个字节为b"\x00\x02"，所以如果我们把M1的高两字节减去这两个字节后，得到的K其实可能会被进位影响，实际上，我们得到的值可能是K正确的高位，也可能是K正确的高位+1。

对这一轮似乎只有1的误差，然而在接下来的轮次我们是需要利用我们已经求出的K高位的，那么上一轮的误差会直接导致这一轮完全错误。

为了减小进位的影响，我做了两个处理：

• 每一次取少一点二进制位，比如只取前12位，这样子受进位影响的概率就会小一些

• 每轮作差时将m1用b"\x80"填充，之后作差：

  M0 - bytes_to_long(b"\x00\x02"+126*b"\x80")

  这样之后再取高位的二进制位也可以减少进位影响，因为相当于做了个平均。

然后是第二个问题，再回顾一下每一轮的式子：

$$M'_0 - 256^{2}K_{known} = m'_0 + 256^{2}K_{unknown} \quad(mod\;n)$$

也就是说每一轮减掉已知高位后，剩下的部分是K的低位左移后的结果，也就是我们通过pkcs填充结构泄露的其实是$256^{2}K_{unknown}$的数据。然而一个严峻的问题在于，$256^{2}K_{unknown}$移位过来之后完全可能会大于n，而他们数量级相近，也就是说我们得到的可能是以下两个值其中一个的高位：

$$256^{2}K_{unknown}$$ $$256^{2}K_{unknown} - n$$

我们需要的是第一个，但是我没想到什么好办法能判断返回值是第一个还是第二个，所以这个也需要处理。

我的处理办法是每次相对于已知的比特位来说少左移一个比特位。打个比方，如果第一轮我们获得了K的高12位，那么接下来我们只左移11位，然后减掉高12位的已知值，这样子这个问题肯定就不复存在了。

然而做上述两个处理之后又会引出第三个问题——如果拿key的第一轮我们泄露13bit，那么之后70轮我们只能泄露12bit，这样一共才：

$$13 + 70 \cdot 12 = 853$$

这和我们需要的1024bit差太多了，所以我们只能尝试更多的bit，但对应的就只有更低的成功率。算下来如果第一轮拿15bit，之后拿14bit的话，那么有：

$$15 + 14 \cdot 70 = 995$$

和1024bit还差29位，多进程爆破一下这29位$K_{unknown}$，检查是否满足如下关系式：

$$(K_known + K_{unknown})^e = x_0 - x_1 \quad(mod\;n)$$

这理论上似乎能行，但是实际上测下来如果真这样拿15bit的话，几千次才可能会成功一次，这对于题目来说意味着几千次重连靶机，完全不能接受。

何况这都是假设timeout内能爆完剩下29bit来说的，实际上每次连接靶机之后，搜到最后都不知道前面有没有出错，所以只能一视同仁的爆29bit，所以这样做的话，不知道赌到那一次成功要猴年马月

这个时候可能会想，每一次不是还有倒数第三十三个字节的值可以利用吗，这的确可以利用，只是它的作用非常局限，局限性体现在：

• 这也是会被加法进位影响的，所以不能直接取这一整个字节当作K的对应位置的值，也只能取前几个比特（比如说三个）来减少被进位影响的概率

• 这个得到的比特是离散的，比如每一次左移12位，这里只能得到3位，相当于每12位只能得到3位

• 当前面主要部分搜到这些已经利用过的比特的时候，的确可以跳过几个二进制位，但是在之后，主要部分和这些部分“对齐了”，所以之后的比特都提供不了新的帮助

  这里我实在不知道怎么才能描述清楚了，画个图可能直观点

• 可能会想这里的比特位可以帮助检查前面的是不是搜错了，但是实际上到这里的时候已经搜了好几十层了，要DFS的话剪枝的层数已经比较深，DFS不过来

• 总而言之，这些比特可以帮上忙，但是只是锦上添花，不是雪中送炭，最终他只能把未知比特降到20左右，还是得爆，但是鉴于当前做法的概率，只要需要爆就不是很现实，必须要优化

所以思路就暂时卡死在这里了，下面放两个测试脚本，分别是不利用倒数第33字节和利用的。

跑之前先把本地的run改成：

def run(self, m0, m1):
    print("[+] OT Protocol Starts")
    m0 = int.from_bytes(encode(m0, self.nbyte), "big")
    m1 = int.from_bytes(encode(m1, self.nbyte), "big")
    x0 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
    x1 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
    print(f"[+] x0 = {x0}")
    print(f"[+] x1 = {x1}")
    v = int(input("[+] v = "))
    M0 = (m0 + pow(v - x0, self.d, self.n)) % self.n
    M1 = (m1 + pow(v - x1, self.d, self.n)) % self.n
    print(f"[+] M0 = {M0}")
    print(f"[+] M1 = {M1}")
    print(f"[+] K = {pow(x0-x1, self.d, self.n)}")  # ADD HERE
    print("[+] OT Protocol Ends")

不利用倒数第33字节的测试脚本如下（nums指第一轮泄露的高位bit，后面70轮每轮泄露nums-1个bit）：

from Crypto.Util.number import *
from tqdm import *
from pwn import *

context.log_level = "CRITICAL"

SUCCESS = 0
for ROUNDS in trange(100):
    sh = process(["python3", "crypto2.py"])

    #################################################################################### get n, e
    sh.recvuntil(b"[+] n =")
    n = int(sh.recvline().strip().decode())
    sh.recvuntil(b"[+] e =")
    e = int(sh.recvline().strip().decode())

    #################################################################################### get aeskey
    sh.recvuntil(b"[+] x0 =")
    x0 = int(sh.recvline().strip().decode())
    sh.recvuntil(b"[+] x1 =")
    x1 = int(sh.recvline().strip().decode())
    sh.recvuntil(b"[+] v =")
    v = x0
    sh.sendline(str(v).encode())
    sh.recvuntil(b"[+] M0 =")
    M0 = int(sh.recvline().strip().decode())
    sh.recvuntil(b"[+] M1 =")
    M1 = int(sh.recvline().strip().decode())
    aeskey = long_to_bytes(M0)[-32:]
    sh.recvuntil(b"[+] K =")

    nums = 14
    KK = int(sh.recvline().strip().decode())
    KK = bin(KK)[2:].zfill(1024)

    #################################################################################### CCA
    rounds = 70
    padding = bytes_to_long(b"\x00\x02"+126*b"\x80")
    K = (bin((M1 - padding) >> (1024-nums))[2:]).zfill(nums)
    known = nums

    secrets = []
    for i in range(1, rounds+1):
        sh.recvuntil(b"[+] x0 =")
        x0_i = int(sh.recvline().strip().decode())
        sh.recvuntil(b"[+] x1 =")
        x1_i = int(sh.recvline().strip().decode())
        
        sh.recvuntil(b"[+] v =")
        v = (pow(2, (known-1)*e, n) * (x0-x1) + x0_i) % n
        sh.sendline(str(v).encode())

        sh.recvuntil(b"[+] M0 =")
        M0_i = int(sh.recvline().strip().decode())
        sh.recvuntil(b"[+] M1 =")
        M1_i = int(sh.recvline().strip().decode())
        sh.recvuntil(b"[+] OT Protocol Ends")

        secrets.append(M0_i) # M0_i = 2^(known-1) * (Kh+Kl) + m0_i % n

        M0_i = (M0_i - pow(2, known-1, n) * int(K.ljust(1024, "0"), 2)) % n
        K += (bin(((M0_i - padding) % n) >> (1024-nums))[2:]).zfill(nums-1)
        known += (nums-1)
        if(len(K) > 1024):
            break

    if(K[:nums+rounds*(nums-1)] == KK[:nums+rounds*(nums-1)]):
        SUCCESS += 1
    sh.close()


print(SUCCESS)

利用倒数第33字节的测试脚本如下（nums指第一轮泄露的高位bit，后面70轮每轮泄露nums-1个bit；nums2指倒数第三十三个字节取几个高位）：

from Crypto.Util.number import *
from tqdm import *
from pwn import *

context.log_level = "CRITICAL"

def comp(a1,a2):
    for i in range(len(a1)):
        if(a1[i] != a2[i] and a1[i] != "*"):
            return False
    return True

SUCCESS = 0
for ROUNDS in trange(10000):
    sh = process(["python3", "crypto2.py"])

    #################################################################################### get n, e
    sh.recvuntil(b"[+] n =")
    n = int(sh.recvline().strip().decode())
    sh.recvuntil(b"[+] e =")
    e = int(sh.recvline().strip().decode())

    #################################################################################### get aeskey
    sh.recvuntil(b"[+] x0 =")
    x0 = int(sh.recvline().strip().decode())
    sh.recvuntil(b"[+] x1 =")
    x1 = int(sh.recvline().strip().decode())
    sh.recvuntil(b"[+] v =")
    v = x0
    sh.sendline(str(v).encode())
    sh.recvuntil(b"[+] M0 =")
    M0 = int(sh.recvline().strip().decode())
    sh.recvuntil(b"[+] M1 =")
    M1 = int(sh.recvline().strip().decode())
    aeskey = long_to_bytes(M0)[-32:]
    sh.recvuntil(b"[+] K =")

    nums = 15
    nums2 = 3
    KK = int(sh.recvline().strip().decode())
    KK = bin(KK)[2:].zfill(1024)

    #################################################################################### CCA
    padding = bytes_to_long(b"\x00\x02"+126*b"\x80")
    rounds = 70
    K = ["*" for i in range(1024)]
    ind1 = 0
    for i in range(nums):
        K[ind1] = bin((M1 - padding) >> (1024-nums))[2:].zfill(nums)[i]
        ind1 += 1
    for i in range(nums2):
        K[-(33*8)+i] = (bin(M1)[2:]).zfill(1024)[-(33*8)+i]
    known = nums

    def ALL0(k):
        return int(k.replace("*", "0"), 2)

    secrets = []
    for i in range(1, rounds+1):
        sh.recvuntil(b"[+] x0 =")
        x0_i = int(sh.recvline().strip().decode())
        sh.recvuntil(b"[+] x1 =")
        x1_i = int(sh.recvline().strip().decode())
        
        sh.recvuntil(b"[+] v =")
        v = (pow(2, (known-1)*e, n) * (x0-x1) + x0_i) % n
        sh.sendline(str(v).encode())

        sh.recvuntil(b"[+] M0 =")
        M0_i = int(sh.recvline().strip().decode())
        sh.recvuntil(b"[+] M1 =")
        M1_i = int(sh.recvline().strip().decode())
        sh.recvuntil(b"[+] OT Protocol Ends")

        secrets.append(M0_i) # M0_i = 2^(known-1) * (Kh+Kl) + m0_i % n

        if("b" in K):
            print("".join(K))
        M0_i = (M0_i - pow(2, known-1, n) * ALL0("".join(K))) % n

        for i in range(nums-1):
            if(known + i < 1024 and K[known + i] == "*"):
                K[known + i] =  bin(((M0_i - padding) % n) >> (1024-nums))[2:].zfill(nums-1)[i]
        for i in range(nums2):
            if(-(33*8-(known-1))+i < 0):
                K[-(33*8-(known-1))+i] = (bin(M0_i)[2:]).zfill(1024)[-(33*8)+i]
        known = K.index("*")
        if("*" not in K):
            break

    K = "".join(K)


    if(comp(K, KK)):
        SUCCESS += 1
        print(K.count("*"))
    sh.close()

print(SUCCESS)

可以看出取15bit后成功率很低很低，不想新方法优化是绝对做不出的，但是实在黔驴技穷了。

要是有80轮就好了