2023-DASCTF-CBCTF-wp-crypto

*代表赛中未解出的题目，包含全四道赛题的复现。

EzRSA

题目描述：

来做简单的RSA啦

题目：

from Crypto.Util.number import *
import random
from gmpy2 import *
from libnum import *
from flag import flag

def padding(f):
    random_chars = bytes([random.randint(0, 255) for _ in range(32)])
    f = f + random_chars
    return f

def guess_p(p):
    e = 65537
    
    P = p
    n1 = getPrime(512)*getPrime(512)
    with open('enc.txt', 'w+') as f:
        while jacobi(2,n1) == 1:
            n1 = getPrime(512)*getPrime(512)
        while P:
            pad = random.randint(0, 2**2023)**2 
            message = pad << 1 + P % 2
            cipher = pow(message, e, n1)
            f.write(str(cipher)+'n')
            P //= 2
    print("n1 = "+ str(n1) )    
    
def guess_q(q):
    
    def encrypt(q, n):
        e = random.randint(1000,2000)
        noise = random.randint(0, n - 1)
        c = pow(q+noise,e,n)
        return e, noise,c 
    
    n2 = getPrime(512)*getPrime(512)
    e1, noise1, c1 = encrypt(q, n2)
    e2, noise2, c2 = encrypt(q, n2)
    print("n2 = "+ str(n2) ) 
    print('(e1, noise1, c1) =', (e1,noise1,c1))
    print('(e2, noise2, c2) =', (e2,noise2,c2))
p = getPrime(512)
q = getPrime(512)

n = p*q
guess_p(p)
guess_q(q)
e = 0x10001
flag = padding(flag)
m = bytes_to_long(flag)
c = pow(m,e,n)

print("c = " + str(c))
'''
n1 = 65634094430927080732256164808833233563732628654160389042977689628512527168256899310662239009610512772020503283842588142453533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554634493581962527475555869292091755676130810562421465063412235309
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802940810851806104430306195931179902098180199167945649526235613636163362672777298968943319216325949503045377100235181706964846408396946496139224344270391027205106691880999410424150216806861393
(e1, noise1, c1) = (1743, 44560588075773853612820227436439937514195680734214431948441190347878274184937952381785302837541202705212687700521129385632776241537669208088777729355349833215443048466316517110778502508209433792603420158786772339233397583637570006255153020675167597396958251208681121668808253767520416175569161674463861719776, 65643009354198075182587766550521107063140340983433852821580802983736094225036497335607400197479623208915379722646955329855681601551282788854644359967909570360251550766970054185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853621152905983)
(e2, noise2, c2) = (1325, 35282006599813744140721262875292395887558561517759721467291789696459426702600397172655624765281531167221787036009507833425145071265739486735993631460189629709591456017092661028839951392247601628468621576100035700437892164435424035004463142959219067199451575338270613300215815894328788753564798153516122567683, 50327632090778183759544755226710110702046850880299488259739672542025916422119065179822210884622225945376465802069464782311211031263046593145733701591371950349735709553105217501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773715759733714)
c = 124349762993424531697403299350944207725577290992189948388824124986066269514204313888980321088629462472088631052329128042837153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177197863522573410860341245613331398610013697803459403446614221369
'''

本题分为两部分，先要用guess_p求出p、然后用guess_q求出q，之后就可以正常RSA解密得到flag。

其中，q的求解相对容易一点，由guess_q知道：

$$(q+noise1)^{e1} \equiv c1 \quad(mod\;n2)$$ $$(q+noise2)^{e2} \equiv c2 \quad(mod\;n2)$$

将q看作未知数，写作多项式如下：

$$(x+noise1)^{e1} \equiv c1 \quad(mod\;n2)$$ $$(x+noise2)^{e2} \equiv c2 \quad(mod\;n2)$$

那么显然q是两个多项式的公共根，因此两个多项式有公因式(x-q)，求解gcd即可得到(x-q)，进而得到q。

然后就是p的求解。这里用到了雅可比符号，因此需要先了解一下雅可比符号的一些相关概念：

而其中勒让德符号(a,pi)的作用是判断a是否是模pi下的二次剩余，若勒让德符号值为1则是二次剩余，为-1则是二次非剩余。

而在这个题目中，还需要知道雅可比符号的一个性质：

• 完全积性：

$$(\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})$$

那么再回头看这个题，首先它保证了：

$$(\frac{2}{n}) \neq 1$$

也就是说值为-1，而由雅可比符号的性质知道：

$$(\frac{2}{n}) = (\frac{2}{p})(\frac{2}{q}) = -1$$

也就是说，2不能同为p、q的二次剩余或二次非剩余，而必须是其中一个的二次剩余，是另一个的二次非剩余。不过本题后续其实没有用到这一点。

再看guess_p中RSA的加密过程(此处要注意优先级，先计算的是加法运算，然后才是移位运算)：

$$message = pad^2<<(1+ P_{lastbit})$$ $$cipher = message^e \quad(mod\;n1)$$

而由雅可比符号的完全积性，我们知道：

$$(\frac{cipher}{n1}) = (\frac{message}{n1})^e$$

而e是一个奇数，因此无论是-1还是1都会维持原值，也就有：

$$(\frac{cipher}{n1}) = (\frac{message}{n1})^e = (\frac{message}{n1})$$

也就是说，我们计算密文的雅可比符号，其实就能得到明文的雅可比符号，这也就是说明RSA语义不安全的其中一点。那么我们有了明文的雅可比符号后，如何得到P的取值呢？

试想，如果P当前位为0，那么就有：

$$message = pad^2<<1 =2*pad^2$$ $$(\frac{message}{n1}) = (\frac{2*pad^2}{n1}) = (\frac{2}{n1})(\frac{pad^2}{n1}) = -1*(\frac{pad^2}{p1})(\frac{pad^2}{q1})$$

显然，pad^2肯定既是p1的二次剩余，也是q1的二次剩余，因此当P的该位为0时，计算出的雅可比符号值为-1

而当P当前位为1时，有如下式：

$$message = pad^2<<2 =4*pad^2$$ $$(\frac{message}{n1}) = (\frac{4*pad^2}{n1}) = (\frac{4*pad^2}{p1})(\frac{4*pad^2}{q1})=(\frac{4}{p1})(\frac{4}{q1})(\frac{pad^2}{p1})(\frac{pad^2}{q1})$$

显然全部都是二次剩余，因此该部分一定是1。所以我们可以把这个作为判断依据来还原P的每一个比特位，还原p、q后就可以解密RSA了。

exp：

from Crypto.Util.number import *
from gmpy2 import *

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()

n1 = 65634094430927080732256164808833233563732628654160389042977689628512527168256899310662239009610512772020503283842588142453533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554634493581962527475555869292091755676130810562421465063412235309
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802940810851806104430306195931179902098180199167945649526235613636163362672777298968943319216325949503045377100235181706964846408396946496139224344270391027205106691880999410424150216806861393
(e1, noise1, c1) = (1743, 44560588075773853612820227436439937514195680734214431948441190347878274184937952381785302837541202705212687700521129385632776241537669208088777729355349833215443048466316517110778502508209433792603420158786772339233397583637570006255153020675167597396958251208681121668808253767520416175569161674463861719776, 65643009354198075182587766550521107063140340983433852821580802983736094225036497335607400197479623208915379722646955329855681601551282788854644359967909570360251550766970054185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853621152905983)
(e2, noise2, c2) = (1325, 35282006599813744140721262875292395887558561517759721467291789696459426702600397172655624765281531167221787036009507833425145071265739486735993631460189629709591456017092661028839951392247601628468621576100035700437892164435424035004463142959219067199451575338270613300215815894328788753564798153516122567683, 50327632090778183759544755226710110702046850880299488259739672542025916422119065179822210884622225945376465802069464782311211031263046593145733701591371950349735709553105217501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773715759733714)
c = 124349762993424531697403299350944207725577290992189948388824124986066269514204313888980321088629462472088631052329128042837153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177197863522573410860341245613331398610013697803459403446614221369

#getq
PR.<x>=PolynomialRing(Zmod(n2))
g1 = (x+noise1)^e1-c1
g2 = (x+noise2)^e2-c2
q = int(-gcd(g1, g2)[0])

with open("E:\题\CBCTF 2023\crypto\CB_rsa\enc.txt","r") as f:
    c1 = f.read().split("n")
tt = ""
for i in range(len(c1)-1):
    if(jacobi(int(c1[i]),n1) == -1):
        tt += "0"
    else:
        tt += "1"
p = int(tt[::-1],2)

phi = (p-1)*(q-1)
d = inverse(65537,phi)
print(long_to_bytes(int(pow(c,d,p*q))))

#DASCTF{W05-y03r_m2st1r-j2c0b1_2nd_p01yn0mi2l!}

CB backpack

题目描述：

Cryptography Based on 8-balanced-backpack

题目：

from random import shuffle

def gen_e():
    e = []
    for i in range(8):
        ee = [0]*3+[1]*3
        shuffle(ee)
        e += ee
    return e
    
e = gen_e()
nbit = len(e)
flag = 'DASCTF{'+sha256(''.join([str(i) for i in e]).encode()).hexdigest()+'}'

a = [randint(1,2^nbit) for i in range(nbit)]

re = 0
for i in range(nbit):
    re += e[i]*a[i]

print(a)
print(re)

相较于普通的01背包密码，这一题的背包有一个特别之处，即每六个比特位之和为3。

开始觉得影响好像不大，但是直接上普通背包的LLL会发现规约不出全为0、1的最短向量，因此肯定需要用上这个特别之处来构造格。

先看看普通的背包密码的格是怎么样的：

$$\left( \begin{matrix} 1 & & & & &a_{1}\\ & 1 & & & &a_{2} \\ & &...& & & ...\\ & & & 1 & & a_{47} \\ & & & & 1 & a_{48} \\ & & & & &-c \\ \end{matrix} \right)$$

这是因为，这个格具有如下线性关系：

$$(b_1,b_1,...b_{47},b_{48},1)* \left( \begin{matrix} 1 & & & & &a_{1}\\ & 1 & & & &a_{2} \\ & &...& & & ...\\ & & & 1 & & a_{47} \\ & & & & 1 & a_{48} \\ & & & & &-c \\ \end{matrix} \right) = (b_1,b_1,...b_{47},b_{48},0)$$

而由于有每六个的和为3，所以可以尝试扩充八列格，如下：

$$\left( \begin{matrix} 1 & & & & &a_{1} & 1 & & \\ & 1 & & & &a_{2} & 1 & & \\ & &...& & &... & &...& \\ & & & 1 & &a_{47}& & & 1 \\ & & & & 1 &a_{48}& & & 1 \\ & & & & &-c &-3 & &-3 \\ \end{matrix} \right)$$

右边新增的八列，每一列对应位置有6个1，然后最后一行为-3。这样构造格的依据是下列线性关系：

$$(b_1,b_1,...b_{47},b_{48},1)* \left( \begin{matrix} 1 & & & & &a_{1} & 1 & & \\ & 1 & & & &a_{2} & 1 & & \\ & &...& & &... & &...& \\ & & & 1 & &a_{47}& & & 1 \\ & & & & 1 &a_{48}& & & 1 \\ & & & & &-c &-3 & &-3 \\ \end{matrix} \right) = (b_1,b_1,...b_{47},b_{48},0,0,0,0,0,0,0,0,0)$$

其中，后九列可以乘上K倍系数来确保规约得到0。但是这样构造格，规约出来的仍然没有满足条件的01向量。然后又改变思路，构造下面的格：

$$\left( \begin{matrix} 1 & & & & &a_{1} & 1 \\ & 1 & & & &a_{2} & 1 \\ & &...& & &... & 1 \\ & & & 1 & &a_{47}& 1\\ & & & & 1 &a_{48}& 1 \\ & & & & &-c &-24 \\ \end{matrix} \right)$$

其线性关系如下：

$$(b_1,b_1,...b_{47},b_{48},1)* \left( \begin{matrix} 1 & & & & &a_{1} & 1 \\ & 1 & & & &a_{2} & 1 \\ & &...& & &... & 1 \\ & & & 1 & &a_{47}& 1\\ & & & & 1 &a_{48}& 1 \\ & & & & &-c &-24 \\ \end{matrix} \right) = (b_1,b_1,...b_{47},b_{48},0,0)$$

仍然是将最后两列扩充K倍，保证规约出0，这样用LLL之后可以找到对应01向量。

不过应该依然是运气好，碰上非预期解，因为前一个格出不来，没想通为什么这个格能出来。

exp：

from Crypto.Util.number import *
from hashlib import sha256
from random import shuffle

b = [65651991706497, 247831871690373, 120247087605020, 236854536567393, 38795708921144, 256334857906663, 120089773523233, 165349388120302, 123968326805899, 79638234559694, 259559389823590, 256776519514651, 107733244474073, 216508566448440, 39327578905012, 118682486932022, 263357223061004, 132872609024098, 44605761726563, 24908360451602, 237906955893793, 204469770496199, 7055254513808, 221802659519968, 169686619990988, 23128789035141, 208847144870760, 272339624469135, 269511404473473, 112830627321371, 73203551744776, 42843503010671, 118193938825623, 49625220390324, 230439888723036, 241486656550572, 107149406378865, 233503862264755, 269502011971514, 181805192674559, 152612003195556, 184127512098087, 165959151027513, 188723045133473, 241615906682300, 216101484550038, 81190147709444, 124498742419309]
c = 4051501228761632

n = len(b)
L = Matrix(ZZ, n+1, n+2)

K = 2**20
for i in range(n):
    L[i,i] = 1
    L[i,-2] = b[i]*K
L[-1,-2] = -c*K

for i in range(48):
    L[i,-1] = 1*K
L[-1,-1] = -24*K

#print(L)
res = L.LLL()
for i in res:
    error = 0
    for j in i:
        if(j != 1 and j != 0):
            error = 1
        if(error == 1):
            break
    if(error == 0):
        e = i[:-2]
        break

flag = 'DASCTF{'+sha256(''.join([str(i) for i in e]).encode()).hexdigest()+'}'
print(flag)

#DASCTF{22a53e95a21f1000ac5dcc618f67586c412e1072f5bb1fee0ee5ce3d1794e3f3}

*CB curve

题目描述：

Cryptography Based on curve

题目：

from Crypto.Util.number import *
from random import randint
from secret import flag,order


class CB_curve:
    def __init__(self):
        self.p = 1141741939958844590498346884870015122543626602665954681008204697160652371664923
        self.a = 727131475903635498678013730344448225340496007388151739960305539398192321065043
        self.b = 840714623434321649308065401328602364673881568379142278640950034404861312007307

    def add(self, P, Q):
        if P == -1:
            return Q
        (x1, y1) = P
        (x2, y2) = Q
        x3 =  (x1+x2)*(1+self.a*y1*y2)*inverse((1+self.b*x1*x2)*(1-self.a*y1*y2),self.p)% self.p
        y3 =  (y1+y2)*(1+self.b*x1*x2)*inverse((1-self.b*x1*x2)*(1+self.a*y1*y2),self.p)% self.p
        return (x3, y3)

    def mul(self, x, P):
        Q = -1
        while x > 0:
            if x & 1:
                Q = self.add(Q, P)
            P = self.add(P, P)
            x = x >> 1
        return Q
    
    def negG(self,G):
        return self.mul(order-1,G)

ecc = CB_curve()
G = (586066762126624229327260483658353973556531595840920560414263113786807168248797, 66727759687879628160487324122999265926655929132333860726404158613654375336028)
P = (ecc.mul(bytes_to_long(flag),G)[0],randint(1,ecc.p))
Q = (460843895959181097343292934009653542386784127282375019764638432240505304648101, 739422832583403823403837831802136107593509589942947902014204968923412689379907)

e = randint(1,p)
pl = [ecc.add(P,ecc.mul(10-i,ecc.negG(Q)))[0] + e for i in range(10)]
ph = [ecc.add(P,ecc.mul(10-i,Q))[0] + e for i in range(10)]

print(pl)
print(ph)

梳理一下加密流程：

• 定义了一条曲线ecc，并给定其上的点加法与倍乘法
• 给出两点G、Q
• 对于G，将flag转为大整数后，求出G的flag倍点并取其横坐标作为P点的横坐标，并另生成一个随机数作为P点的纵坐标
• 对于Q，生成一个随机数e，然后进行10次如下运算(其中，[0]代表取横坐标，negG是取逆元点)：

$$pl_i = (P + (10-i)*negG(Q))[0] + e$$ $$ph_i = (P + (10-i)*Q)[0] + e$$

那么大致思路就是：

• 先通过pl、ph求出点P的坐标
• 通过曲线映射求解DLP，得到flag

接下来进入具体题目分析。

negG

要求出P点的坐标就要利用pli与phi，但是利用pli之前，首先要知道negG(Q)的具体坐标是多少。由题目中：

def negG(self,G):
    return self.mul(order-1,G)

可以看出，negG(Q)操作其实就是在取Q的该曲线上的逆元，但是我们没有order，也没有有效的计算order的方法，因此只能用题目已知信息推算Q逆元的坐标形式。

首先要确认曲线的单位元O，由于普通ECC的单位元是无穷远点，不好计算，所以我们先测试O=(0，0)，看他是不是单位元。测试方法就是看对于曲线上任意一点X，是否有O+X=X。

而我们有该曲线的加法如下：

x3 =  (x1+x2)*(1+self.a*y1*y2)*inverse((1+self.b*x1*x2)*(1-self.a*y1*y2),self.p)% self.p
y3 =  (y1+y2)*(1+self.b*x1*x2)*inverse((1-self.b*x1*x2)*(1+self.a*y1*y2),self.p)% self.p

把数学表达式写的直观一点(以下均在模p下进行)：

$$x_3 = \frac{(x_1+x_2)(1+ay_1y_2)}{(1+bx_1x_2)(1-ay_1y_2)}$$ $$y_3 = \frac{(y_1+y_2)(1+bx_1x_2)}{(1-bx_1x_2)(1+ay_1y_2)}$$

很显然对曲线上任意一点X，O=(0，0)满足O+X=X，因此(0，0)是该曲线的单位元。这一点也可以用题目给定的add函数测试。

那么有了单位元后，由于negG(Q)是Q的逆元，所以有：

$$negG(Q) + Q = O$$

那么设negG(Q)=(x1,y1)，代入点加法就有：

$$0 = \frac{(x_1+x_Q)(1+ay_1y_Q)}{(1+bx_1x_Q)(1-ay_1y_Q)}$$ $$0 = \frac{(y_1+y_Q)(1+bx_1x_Q)}{(1-bx_1x_Q)(1+ay_1y_Q)}$$

这个时候就可以看出来其实Q和negG(Q)的坐标关系其实就是模p下互为相反数，因此我们就有了negG(Q)的坐标了。可能有的师傅看到这里会觉得这很显然，但其实对于认识一个曲线，这些分析步骤其实并不显然，而且很重要。

groebner求P点坐标

那么现在有了negG(Q)的坐标，我们就可以着手利用pl和ph了。仍然把他们先写成直观的数学表达式如下：

$$pl_i = \frac{(x_P-x_i)(1-ay_Py_i)}{(1-bx_Px_i)(1+ay_Py_i)} + e$$ $$ph_i = \frac{(x_P+x_i)(1+ay_Py_i)}{(1+bx_Px_i)(1-ay_Py_i)} + e$$

其中，(xi,yi)是当次Q的(10-i)倍点的坐标。现在有了十组pli、phi，而这些方程组只有三个未知数xP、yP、e，因此朴素的想法是直接groebner基求出三个未知数就有P点的坐标。但是实际上这样是求不出的，我觉得可能是以下两个原因：

• yP并不是P点在该曲线上的纵坐标，而是一个随机数，因此直接用曲线加法会产生一些错误
• 多项式形式过于复杂，直接groebner难以求解

赛后看别的师傅wp，才发现只要采用一个小技巧，这两个问题就可以同时解决。这个技巧就是发现平方差公式可以利用在消元中，如下：

$$pl_i - e = \frac{(x_P-x_i)(1-ay_Py_i)}{(1-bx_Px_i)(1+ay_Py_i)}$$ $$ph_i - e = \frac{(x_P+x_i)(1+ay_Py_i)}{(1+bx_Px_i)(1-ay_Py_i)}$$

上下两式相乘可以得到：

$$(pl_i - e)(ph_i - e) = \frac{(x_P-x_i)(1-ay_Py_i)}{(1-bx_Px_i)(1+ay_Py_i)} \frac{(x_P+x_i)(1+ay_Py_i)}{(1+bx_Px_i)(1-ay_Py_i)}$$

就可以消掉yP，并得到：

$$(pl_i - e)(ph_i - e) = \frac{xP^2-x_i^2}{1-b^2x_P^2x_i^2}$$

而这样用groebner基就可以求出xP和e了，当然求出来的xP有两种取值。

mapping

这也是赛后看别的师傅wp(DASCTF-CBCTF 2023 - ZimaB1ue - 博客园 (cnblogs.com))才看到的，赛中没找到这是huff曲线(其实赛后自己找也没找到)。而huff曲线可以利用如下映射mapping到普通椭圆曲线上(也就是常见的Weiestrass Curve)：

那么就先用huff曲线方程求出P点坐标，然后将P点映射到对应椭圆曲线上。

然后由于映射是一一对应，因此曲线阶不会变，所以我们可以直接用order函数求出映射后的曲线阶，发现其除了一个因子外都光滑，因此之后就是pohlig_Hellman求一个DLP就能得到flag。

exp：

from Crypto.Util.number import *
from random import randint

class CB_curve:
    def __init__(self):
        self.p = 1141741939958844590498346884870015122543626602665954681008204697160652371664923
        self.a = 727131475903635498678013730344448225340496007388151739960305539398192321065043
        self.b = 840714623434321649308065401328602364673881568379142278640950034404861312007307

    def add(self, P, Q):
        if P == -1:
            return Q
        (x1, y1) = P
        (x2, y2) = Q
        x3 =  (x1+x2)*(1+self.a*y1*y2)*inverse((1+self.b*x1*x2)*(1-self.a*y1*y2),self.p)% self.p
        y3 =  (y1+y2)*(1+self.b*x1*x2)*inverse((1-self.b*x1*x2)*(1+self.a*y1*y2),self.p)% self.p
        return (x3, y3)

    def mul(self, x, P):
        Q = -1
        while x > 0:
            if x & 1:
                Q = self.add(Q, P)
            P = self.add(P, P)
            x = x >> 1
        return Q
    
    def negG(self,G):
        return self.mul(order-1,G)

ecc = CB_curve()
G = (586066762126624229327260483658353973556531595840920560414263113786807168248797, 66727759687879628160487324122999265926655929132333860726404158613654375336028)
Q = (460843895959181097343292934009653542386784127282375019764638432240505304648101, 739422832583403823403837831802136107593509589942947902014204968923412689379907)
pl = [908996880816674413953945844149350915331956247471480600840221415119794882139724, 971918808384910355828135603762747020183688585728289421786279444571287619529246, 1285550352531583269956802123237391199017403081800977678246201935580429758051904, 1551774945769448705387900437472951015954157193946719575845523359198154668857591, 676185408751480221545400062950292727848016906516506232986883519673765317932582, 1250300209784131850574858927023046353058343552115735540789593580037130054384362, 1298409778422699298367007023890818793557023853717180295526932023194697263501748, 1332552452292482549702793642987623159617988974910321945878093492007278710993114, 1030239404875082841481045525469865919289388171602293245905162820968158543176773, 1154148024180033719999293176590867264297899817449945744942661351655533433871621]
ph = [584297112520340495757457954416165393828472756298945167299482077258411155766756, 886432149227960827335266910774569034430464592640209168563805700117347063152246, 613528590036968449893421430816319461615130635882647544978722093413694101540550, 576162106332135829961234799085370038425761945928004579456101802617485243023987, 627570890346195626159365118862437334953500165050236216404858019114288681512171, 1015503424232985454098149884321288932492551183126601131968495641510550575005042, 1532737675157046782602115678180407262847166210963507805526455422934164759886583, 1540047002602145805476906585925538790245968214992837106009502002588479779602195, 505097517314409449404205152068185149808364887623922221197462411159844816865696, 873498218680784138428154510303205366133389839886911286745954821800632158315951]

#get coordinate_P
PR.<xp,e> = PolynomialRing(Zmod(ecc.p))
F = []
for i in range(10):
    f = (pl[i]-e)*(ph[i]-e)*(1-ecc.b^2*xp^2*(ecc.mul(10-i,Q)[0]^2)) - (xp^2-(ecc.mul(10-i,Q)[0]^2))
    F.append(f)
res = Ideal(F).groebner_basis()
#print(res)
#[xp^2 + 219493165434454878473973957507132663767650700404392831423708684433961924200902, e + 716700711017198421972376297958894204723153539777056104579499803899129208364755]

xp_2 = -219493165434454878473973957507132663767650700404392831423708684433961924200902
F = Zmod(ecc.p)
xp_2 = F(xp_2)
xp = xp_2.nth_root(2,all=True)

points = []
PR.<yp> = PolynomialRing(Zmod(ecc.p))
for x in xp:
    f = x*(ecc.a*yp^2-1) - yp*(ecc.b*x^2-1)
    res = f.roots()
    points.append((int(x),int(res[0][0])))
    points.append((int(x),int(res[1][0])))


#mapping and pohlig_hellman
def mapping(point):
    x = point[0]
    y = point[1]
    Ex = (ecc.b*x-ecc.a*y) * inverse(y-x,ecc.p) % ecc.p
    Ey = (ecc.b-ecc.a) * inverse(y-x,ecc.p) % ecc.p
    return (Ex,Ey)

def pohlig_hellman(q,g,primes,order):
    logs=[]
    for fac in primes:
        t=int(order)//int(fac)
        log=discrete_log(t*q,t*g,operation='+')
        logs+=[log]
    m = crt(logs,primes)
    return m


# DLP
E = EllipticCurve(GF(ecc.p),[0,ecc.a+ecc.b,0,ecc.a*ecc.b,0])
#print(E.order())
order = 1141741939958844590498346884870015122544171009688372185479632675211885925945760
order_factors = [3,5,37,271,4297,6983,9679,52631,139571,84666937,558977989]
EG = E(mapping(G))
for point in points:
    try:
        EP = E(mapping(point))
        m = pohlig_hellman(EP,EG,order_factors,order)
        print(long_to_bytes(m))
    except:
        pass

#DASCTF{goodathuff}

*CB cipher

题目描述：

Cryptography Based on cipher

题目：

from random import randint
from pylfsr import LFSR
from Crypto.Util.number import *
from secret import state1,state2,state3,flag

assert b'DASCTF' in flag

fpoly1 = [14,13,6,2]
fpoly2 = [20,15,12,9,7,4,3]
fpoly3 = [13,12,11,9,7,6,3]

def iv():
    a,b,c = L1.next(),L2.next(),L3.next()
    return (a & b) ^ (b & c) ^ c

class CB_cipher():
    def __init__(self):
        key = [''.join([str(randint(0,1)) for i in range(16)]) for j in range(2)]

        self.key = [[int(j) for j in i] for i in key]
        
        self.sbox = [0x6, 0x4, 0xc, 0x5,
                     0x0, 0x7, 0x2, 0xe,
                     0x1, 0xf, 0x3, 0xd,
                     0x8, 0xa, 0x9, 0xb]
    
    def s_trans(self,pt):
        pt = ''.join([str(i) for i in pt])
        pt = [self.sbox[int(i,16)] for i in hex(int(pt,2))[2:].rjust(4,'0')]
        ct = ''.join([bin(i)[2:].rjust(4,'0') for i in pt])
        ct = [int(i) for i in ct]
        return ct
        
    def encrypt(self,pltxt):
        key_add = lambda x,key : [x[i]^key[i] for i in range(len(x))]
        bit_move = lambda x : [x[(i//4)+(i%4)*4] for i in range(len(x))]
        
        ct = [int(i) for i in pltxt]
        
        for i in range(5):
            ct = key_add(ct,self.key[i%2])
            ct = self.s_trans(ct)
            if (i+1)%2:
                ct = bit_move(ct)
        
        ct = key_add(ct,self.key[1])
        return ''.join([str(i) for i in ct]) 
    
    def bt_to_bin(self,msg):
        msg = msg if (len(msg)+1)%2 else msg+b'\x00'
        return bin(bytes_to_long(msg))[2:].rjust(8*len(msg),'0')
        
    def txt_encrypt(self,msg):
        time = (len(msg)+1)//2
        pltxt = [self.bt_to_bin(msg)[i*16:i*16+16] for i in range(time)]
        #print(pltxt)
        output = []
        
        for i in range(time):
            now_re = self.encrypt(pltxt[i])
            if output != []:
                now_re = bin(int(now_re,2) ^ int(output[-1],2))[2:].rjust(16,'0')
            output.append(now_re)
        
        return long_to_bytes(int(''.join(output),2))
    
L1 = LFSR(fpoly = fpoly1, initstate = state1)
L2 = LFSR(fpoly = fpoly2, initstate = state2)
L3 = LFSR(fpoly = fpoly3, initstate = state3)

iv_txt = ''
for i in range(len(flag)*8):
    iv_txt += str(iv())
    
a = CB_cipher()

print(iv_txt[:320])
print(a.txt_encrypt(b'Welcome to our CBCTF! I hope you can have a nice day here. Come with me.'))
print(long_to_bytes(bytes_to_long(a.txt_encrypt(flag))^int(iv_txt,2)))

#10101010100110100000111111011110111101010010011000011011001010010010111000100101011111010001110110110111000010100001010111110110000011110100110011011110001100100011101101110001000100111100001111100111010100010000001101001001000011110001100110101100101000101001110011101100001100100000011101011110100110110110000110010101
#b'\x10\x07t9\x88\x95\x8b&\xb2\x8fp\xe7\xce\\k{\xbb\xe5\xa7\xb8\x92\xbe\xd1\n\x84.\xe1\xe0\xab\x08\x97\x92\x1a\xbd\xdf\x80R\xbe\xe2\x84\xe17\x14\x8a\x07\x03\x87)\xb2\xa6W:\xda\x04Y\xa5\xca\x16o1\x93\x9d\x90.\xcdS\xd6\xcbK\xf4\xd8G'
#b"\xec\x16<[D;F6\xb6\xcc\x7f\x80jL1\xb1@\x84iF[\xfcW\xbbbp\xdc\x0fI,%\x15\x1a\xbe\x86hT\r\xf0\x8a\xa91\x9aF\xe3\x84n\xeb\xe9\xa3,T\xec\x8f\xdbb\xc1\xd7\xe7&'u\xe9A\xe9\x03\xe1\x89\x04\x8f\xa77\x8a\xd7\x97x\xccl\x1e\xc6\xea%\xb1/P\x98\x8e\x9bS\xca\xf5kR\x98H\xc6d\x15"

分析一下题目流程：

• 题目给出了三个LFSR，并结合三个LFSR的每一比特输出生成了iv_txt，并给出了iv_txt的前320位
• 题目自定义了一个CB_cipher类，并生成一个对象a，对一段已知明文进行了加密，并给出密文
• 将flag也用对象a加密后，与完整的iv_txt异或，并给出密文

尝试

首先，三个LFSR这部分有点类似于前段时间柏鹭杯的Stream。

2023-网信柏鹭杯-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

只是这道题里采用了pylfsr实现，把特征多项式换成等价的移位操作就仍然可以用z3解出三个state，从而还原出完整iv_txt，如下：

from Crypto.Util.number import *
from z3 import *

c = "10101010100110100000111111011110111101010010011000011011001010010010111000100101011111010001110110110111000010100001010111110110000011110100110011011110001100100011101101110001000100111100001111100111010100010000001101001001000011110001100110101100101000101001110011101100001100100000011101011110100110110110000110010101"

#part1 get_init_state
def lfsr1(R):
    return ((R >> 13) & 1) ^ ((R >> 12) & 1) ^ ((R >> 5) & 1) ^ ((R >> 1) & 1)

def lfsr2(R):
    return ((R >> 19) & 1) ^ ((R >> 14) & 1) ^ ((R >> 11) & 1) ^ ((R >> 8) & 1) ^ ((R >> 6) & 1) ^ ((R >> 3) & 1) ^ ((R >> 2) & 1)

def lfsr3(R):
    return ((R >> 12) & 1) ^ ((R >> 11) & 1) ^ ((R >> 10) & 1) ^ ((R >> 8) & 1) ^ ((R >> 6) & 1) ^ ((R >> 5) & 1) ^ ((R >> 2) & 1)

def z3_sol():
    R1 = BitVec('R1',20)
    R2 = BitVec('R2',20)
    R3 = BitVec('R3',20)
    sol = Solver()
    for i in range(320):
        sol.add(((lfsr1(R1) & lfsr2(R2))^(lfsr2(R2) & lfsr3(R3))^lfsr3(R3)) == int(c[i]))
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    if(sol.check() == sat):
        print(sol.model())

z3_sol()

得到三个初始state：

[R2 = 68217, R3 = 3230, R1 = 6464]

可以验证该种子产生的iv_txt前320位与给定的相等：

#part2 check_init_state
R2 = 68217;R3 = 3230;R1 = 6464
iv_txt = ""
for i in range(98*8):
    iv_txt += str((lfsr1(R1)&lfsr2(R2)) ^ (lfsr2(R2)&lfsr3(R3)) ^ lfsr3(R3))
    R1 = (R1 << 1) ^ lfsr1(R1)
    R2 = (R2 << 1) ^ lfsr2(R2)
    R3 = (R3 << 1) ^ lfsr3(R3)
print(iv_txt[:320] == c)

然后我们就可以去除iv_txt对flag的密文异或的影响。

接下来的问题就是：如何由一组已知的明密文对，解密flag对应的密文？这就需要分析加密的具体过程了。不过大致浏览一下可以发现几个比较重要的性质：

• 把明文每两个字节分为一组，对于相同的两个字节，encrypt的结果是一样的
• txt_encrypt其实只是对每个明文分组encrypt的结果做了一个类似CBC的操作，也就是当前组的最终密文，由该组encrypt的加密结果与前一组的最终密文异或得到

可以发现，性质二其实提供了一个逆操作，我们只需要知道前一组的最终密文，与当前分组的最终密文异或，就能得到当前分组的encrypt结果。比如对于题目中给定的已知的一组明文c1，可以用以下操作恢复其encrypt结果：

c1 = b'\x10\x07t9\x88\x95\x8b&\xb2\x8fp\xe7\xce\\k{\xbb\xe5\xa7\xb8\x92\xbe\xd1\n\x84.\xe1\xe0\xab\x08\x97\x92\x1a\xbd\xdf\x80R\xbe\xe2\x84\xe17\x14\x8a\x07\x03\x87)\xb2\xa6W:\xda\x04Y\xa5\xca\x16o1\x93\x9d\x90.\xcdS\xd6\xcbK\xf4\xd8G'
plain = b'Welcome to our CBCTF! I hope you can have a nice day here. Come with me.'

final_c1 = b"\x10\x07"
for i in range(2,len(c1),2):
    tt1 = bytes_to_long(c1[i:i+2])
    tt2 = bytes_to_long(c1[i-2:i])
    final_c1 += long_to_bytes(tt1^tt2,2)

print(final_c1)

得到的结果如下：

b"\x10\x07d>\xfc\xac\x03\xb39\xa9\xc2h\xbe\xbb\xa5'\xd0\x9e\x1c]5\x06C\xb4U$e\xceJ\xe8<\x9a\x8d/\xc5=\x8d>\xb0:\x03\xb3\xf5\xbd\x13\x89\x80*5\x8f\xe5\x9c\x8d>\x83\xa1\x93\xb3\xa5'\xfc\xac\x03\xb3]}\x1b\x98\x9d?\x93\xb3"

得到了原始的encrypt的结果，其用处是什么呢？这个时候就需要用到刚才提到的性质一：把明文每两个字节分为一组，对于相同的两个字节，encrypt的结果是一样的。

而由于两次加密用的是同一个对象a，因此密钥key不变，所以同样的两字节密文肯定会得到同样的两字节密文。而我们现在相当于有了36组2字节的明密文对应关系，也许可以根据这些关系恢复一部分flag串，然后用猜单词之类的方式猜测flag的完整串？

那么如法炮制，先把c2的CBC加密去掉：

c2 = b"\xec\x16<[D;F6\xb6\xcc\x7f\x80jL1\xb1@\x84iF[\xfcW\xbbbp\xdc\x0fI,%\x15\x1a\xbe\x86hT\r\xf0\x8a\xa91\x9aF\xe3\x84n\xeb\xe9\xa3,T\xec\x8f\xdbb\xc1\xd7\xe7&'u\xe9A\xe9\x03\xe1\x89\x04\x8f\xa77\x8a\xd7\x97x\xccl\x1e\xc6\xea%\xb1/P\x98\x8e\x9bS\xca\xf5kR\x98H\xc6d\x15"
c2 = long_to_bytes(bytes_to_long(c2)^int(iv_txt,2))
final_c2 = b"F\x8c"
for i in range(2,len(c2),2):
    tt1 = bytes_to_long(c2[i:i+2])
    tt2 = bytes_to_long(c2[i-2:i])
    final_c2 += long_to_bytes(tt1^tt2,2)
print(final_c2)

得到的结果为：

b'F\x8cu\t\x82\x98\xec\x02\xc5\xf6\x9at\xdf\xdb\xf9\x01k\x8f\xf8\xbc\xd7\xf9$\xf5\xc1YZg\x99s\xcf\x82\x0f\xe52=\xbe\xf9\x9b\x89+\xdf\x8dYr\xac\x06\xf3W\x8e\x81\x82\x00L\xf0%\xd7*Ea\xb6=\xd4(\x1f\x17Gck2\xde\xc1r8\xcdSY\x8a\xd63\xfa\x1a{yNO\xe5\xe7%\x98\xc7\x84\xff\x9cr\r\xf3!'

然后由于题目保证了”DASCTF”在flag串中，然后由已知明密文对可以分析出：

"TF" --> "\x1c]"

但是很可惜在密文串中没有发现这组加密结果，这说明”DASCTF”应该是按如下分组加密的：

"xD","AS","CT","Fx"

然后就期望可以找到别的已有的密文对，结果一组都没有找到，尝试彻底失败！

那么通过这种方式肯定是不行的，还是要结合提示”中间相遇”去分析具体加密流程才能找出密钥，从而进行解密。

正确思路

在研究了wp以及与出题师傅交流后，基本理清了这道题的思路，接下来我会尝试把wp的思路阐述的更清楚一点。

iv

首先就是纠正一下尝试中对于iv求解的一点小错误。这里的错误主要是由于题目iv的生成方式：

iv_txt = ''
for i in range(len(flag)*8):
    iv_txt += str(iv())

可以看到，他生成了flag长度乘8个比特，也就是flag长度个字节。而由于题目中给定的flag最终密文是98字节，所以很容易就会像我一样直接认为iv也是98个字节的长度。但其实并不一定，因为flag在txt_encrypt中可能会进行填充，因此flag的初始长度既可能是98字节，也可能是97字节！

而在上面我的尝试中，我生成了98字节的iv并消除类似CBC的影响后，竟然一组明文都找不到(包括”TF”这种很大概率存在的明文对)，因此很可能iv其实是97个字节。我们生成97字节的iv后重新求解，就可以重新得到c2的两两一组的纯encrypt加密结果如下：

b'F\x8cJ\xe8<\x9a\xfa\xe3\xff\xcf\xc5\x1f-\x06L_\x8d/\x93\x13L_Oo\x87?,\x9b\x8d/<\x9a\x84\x9b\xd2x9\t8\xb8W\xc9W\xc9W\xc9\xe3\xe4\x1b\x98\x03\xb3\xb5\x1b\xa0*\xd2x\xb9\x92P%\xa0.\x1c]]\xc5\x0c\x88\x97\xc5T\xbf\xc5\x7f\xa7\x16L\xaem\xed\xa2*\x92\x18&89\xa9o\xc0\x82\xabu6\x7f\x0c'

这个时候可以发现里面就存在包括”\x1c]”在内的一些密文对了，并且拓展一下也可以知道诸如”DA”、”SC”之类明文对应的密文，不过这已经不重要了，因为还有非常多对密文对没有出现在已知明密文对中，所以这个方法无法完全求解。

不过至少这说明iv长度为97应该才是正解。

中间相遇

然后接下来是对中间相遇步骤的分析，这才是本题的重头戏。

首先由之前的分析我们可以知道，我们完全可以把每两个字节都当作独立的明文进行处理。因此现在我们只需要关注encrypt函数的加密流程了。而encrypt函数一共加密五轮，再贴一下其加密流程如下：

def encrypt(self,pltxt):
    key_add = lambda x,key : [x[i]^key[i] for i in range(len(x))]
    bit_move = lambda x : [x[(i//4)+(i%4)*4] for i in range(len(x))]
    
    ct = [int(i) for i in pltxt]
    
    for i in range(5):
        ct = key_add(ct,self.key[i%2])
        ct = self.s_trans(ct)
        if (i+1)%2:
            ct = bit_move(ct)
    
    ct = key_add(ct,self.key[1])
    return ''.join([str(i) for i in ct]) 

其中，s_trans函数如下：

def s_trans(self,pt):
    pt = ''.join([str(i) for i in pt])
    pt = [self.sbox[int(i,16)] for i in hex(int(pt,2))[2:].rjust(4,'0')]
    ct = ''.join([bin(i)[2:].rjust(4,'0') for i in pt])
    ct = [int(i) for i in ct]
    return ct

它实现的功能是：把输入的长度为16的01列表，转化为4个十六进制数，并使用sbox对这4个十六进制数分别进行代换，代换完毕后，将其重新转为长度为16的01列表并返回。

然后还有一个bit_move函数：

bit_move = lambda x : [x[(i//4)+(i%4)*4] for i in range(len(x))]

它实现的功能是一个比特置换，我们打印一下其置换结果：

print([i for i in range(16)])
print([(i//4)+(i%4)*4 for i in range(16)])

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15]

这也就是说，进行bit_move操作后，位置为0的比特换到位置0，位置为4的比特换到位置1，位置为8的比特换到位置2，以此类推。其实这两个函数也就是一个代换置换网络每一轮的代换与置换操作。

那么我们可以发现encrypt函数几个不安全的地方：

• 加密轮数只有5轮，轮数比较少
• 只有1、3、5轮进行了bit_move，2、4轮没有进行
• bit_move函数中，有4个比特位并没有进行置换，分别是：0，5，10，15

那么接下来我们尝试进行中间相遇攻击，那么首先假设我们通过爆破操作，可以拥有正确的密钥K[0]的全16个比特以及密钥K[1]的前4个比特，然后对已知的明文加密三轮。我们把已知的两字节明文分成每4bit一组，这样符合每一轮的代换置换过程，然后对前三轮依次进行分析：

• 第一轮：由于我们拥有完全正确的K[0]，因此我们可以获得完全正确的第一轮加密结果。

• 第二轮：由于我们只拥有K[1]的前四个比特，而第二轮只进行了S盒代换没有进行bit_move，因此我们能获得完全正确的第二轮加密得到的前4bit

• 第三轮：仍然由于拥有K[0]的全16个bit，因此自然拥有完全正确的K[0]前4bit，所以在第三轮bit_move之前，得到的前4bit加密结果仍然是完全正确的。然后就需要进行bit_move，而正如刚才分析得到的一样，由于bit_move中第0比特位并没有进行置换，所以三轮加密完全结束后，我们可以得到完全正确的第0比特。

也就是说，我们爆破密钥K[0]的全16个比特以及密钥K[1]的前4个比特，其中正确的那一组就可以得到36组已知明文的三轮加密的第0比特，所以我们可以依据此建立中间相遇攻击的字典。

同理，对于解密操作，我们爆破正确的密钥K[1]的全16个比特以及密钥K[0]的前4个比特，就可以得到完全正确的三轮解密得到的前四个bit，但是我们只需要第0比特来进行中间相遇攻击。

而这个步骤还可以简化，就是wp说的那样分为内层和外层，外层爆破两个密钥的前4bit，内层使用两个密钥的后12bit去中间相遇。这样就可以每次建立一个较小字典进行中间相遇攻击，而不需要先花较长时间把完整的很大的加密字典完全建立好，然后再通过解密操作反查字典进行中间相遇。

现在我们有已知的36组明密文，那么如果中间相遇攻击发现了一组密钥对36个碰撞比特都满足，那么就很大概率是正确的密钥了。有了正确密钥后写个解密逆操作就可以得到flag。

exp(偷了点懒，完整的CB_cipher类就直接用wp的了)：

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

c = "10101010100110100000111111011110111101010010011000011011001010010010111000100101011111010001110110110111000010100001010111110110000011110100110011011110001100100011101101110001000100111100001111100111010100010000001101001001000011110001100110101100101000101001110011101100001100100000011101011110100110110110000110010101"

#part1 get_init_state
def lfsr1(R):
    return ((R >> 13) & 1) ^ ((R >> 12) & 1) ^ ((R >> 5) & 1) ^ ((R >> 1) & 1)

def lfsr2(R):
    return ((R >> 19) & 1) ^ ((R >> 14) & 1) ^ ((R >> 11) & 1) ^ ((R >> 8) & 1) ^ ((R >> 6) & 1) ^ ((R >> 3) & 1) ^ ((R >> 2) & 1)

def lfsr3(R):
    return ((R >> 12) & 1) ^ ((R >> 11) & 1) ^ ((R >> 10) & 1) ^ ((R >> 8) & 1) ^ ((R >> 6) & 1) ^ ((R >> 5) & 1) ^ ((R >> 2) & 1)

def z3_sol():
    R1 = BitVec('R1',20)
    R2 = BitVec('R2',20)
    R3 = BitVec('R3',20)
    sol = Solver()
    for i in range(320):
        sol.add(((lfsr1(R1) & lfsr2(R2))^(lfsr2(R2) & lfsr3(R3))^lfsr3(R3)) == int(c[i]))
        R1 = R1 << 1 ^ lfsr1(R1)
        R2 = R2 << 1 ^ lfsr2(R2)
        R3 = R3 << 1 ^ lfsr3(R3)
    if(sol.check() == sat):
        print(sol.model())
#z3_sol()


#part2 check_init_state
R2 = 68217;R3 = 3230;R1 = 6464
iv_txt = ""
for i in range(97*8):
    iv_txt += str((lfsr1(R1)&lfsr2(R2)) ^ (lfsr2(R2)&lfsr3(R3)) ^ lfsr3(R3))
    R1 = (R1 << 1) ^ lfsr1(R1)
    R2 = (R2 << 1) ^ lfsr2(R2)
    R3 = (R3 << 1) ^ lfsr3(R3)
#print(iv_txt[:320] == c)


#part3 get_cipher
c1 = b'\x10\x07t9\x88\x95\x8b&\xb2\x8fp\xe7\xce\\k{\xbb\xe5\xa7\xb8\x92\xbe\xd1\n\x84.\xe1\xe0\xab\x08\x97\x92\x1a\xbd\xdf\x80R\xbe\xe2\x84\xe17\x14\x8a\x07\x03\x87)\xb2\xa6W:\xda\x04Y\xa5\xca\x16o1\x93\x9d\x90.\xcdS\xd6\xcbK\xf4\xd8G'
plain = b'Welcome to our CBCTF! I hope you can have a nice day here. Come with me.'
final_c1 = b"\x10\x07"
for i in range(2,len(c1),2):
    tt1 = bytes_to_long(c1[i:i+2])
    tt2 = bytes_to_long(c1[i-2:i])
    final_c1 += long_to_bytes(tt1^tt2,2)

c2 = b"\xec\x16<[D;F6\xb6\xcc\x7f\x80jL1\xb1@\x84iF[\xfcW\xbbbp\xdc\x0fI,%\x15\x1a\xbe\x86hT\r\xf0\x8a\xa91\x9aF\xe3\x84n\xeb\xe9\xa3,T\xec\x8f\xdbb\xc1\xd7\xe7&'u\xe9A\xe9\x03\xe1\x89\x04\x8f\xa77\x8a\xd7\x97x\xccl\x1e\xc6\xea%\xb1/P\x98\x8e\x9bS\xca\xf5kR\x98H\xc6d\x15"
c2 = long_to_bytes(bytes_to_long(c2)^int(iv_txt,2))
final_c2 = b"F\x8c"
for i in range(2,len(c2),2):
    tt1 = bytes_to_long(c2[i:i+2])
    tt2 = bytes_to_long(c2[i-2:i])
    final_c2 += long_to_bytes(tt1^tt2,2)


#part4 Meet-in-the-Middle attack
class CB_cipher():
    def __init__(self):      
        self.sbox = [0x6, 0x4, 0xc, 0x5,
                     0x0, 0x7, 0x2, 0xe,
                     0x1, 0xf, 0x3, 0xd,
                     0x8, 0xa, 0x9, 0xb]
        self.inv_sbox = [0x4, 0x8, 0x6, 0xa, 
                         0x1, 0x3, 0x0, 0x5, 
                         0xc, 0xe, 0xd, 0xf, 
                         0x2, 0xb, 0x7, 0x9]
    
    def s_trans(self,pt):
        pt = ''.join([str(i) for i in pt])
        pt = [self.sbox[int(i,16)] for i in hex(int(pt,2))[2:].rjust(4,'0')]
        ct = ''.join([bin(i)[2:].rjust(4,'0') for i in pt])
        ct = [int(i) for i in ct]
        return ct
    
    def inv_s_trans(self,pt):
        pt = ''.join([str(i) for i in pt])
        pt = [self.inv_sbox[int(i,16)] for i in hex(int(pt,2))[2:].rjust(4,'0')]
        ct = ''.join([bin(i)[2:].rjust(4,'0') for i in pt])
        ct = [int(i) for i in ct]
        return ct
    
    def e1(self,pltxt,k0,k1_4):
        key_add = lambda x,key : [x[i]^key[i] for i in range(len(x))]
        bit_move = lambda x : [x[(i//4)+(i%4)*4] for i in range(len(x))]
        
        ct = [int(i) for i in pltxt]
        ct = key_add(ct,k0)
        ct = self.s_trans(ct)
        ct = bit_move(ct)
        ct = key_add(ct[:4],k1_4)
        ct = self.sbox[int(''.join([str(i) for i in ct]),2)]
        ct = key_add([int(i) for i in bin(ct)[2:].rjust(4,'0')],k0[:4])
        ct = self.sbox[int(''.join([str(i) for i in ct]),2)]
        ct = ct>>3
        return ct
        
    def d1(self,pltxt,k1,k0_4):
        #print(self)
        key_add = lambda x,key : [x[i]^key[i] for i in range(len(x))]
        bit_move = lambda x : [x[(i//4)+(i%4)*4] for i in range(len(x))]
        
        ct = [int(i) for i in pltxt]
        ct = key_add(ct,k1)
        ct = bit_move(ct)
        ct = self.inv_s_trans(ct)
        ct = key_add(ct[:4],k0_4)
        ct = self.inv_sbox[int(''.join([str(i) for i in ct]),2)]
        ct = key_add([int(i) for i in bin(ct)[2:].rjust(4,'0')],k1[:4])
        return ct[0]
    
    def bt_to_bin(self,msg):
        msg = msg if (len(msg)+1)%2 else msg+b'\x00'
        return bin(bytes_to_long(msg))[2:].rjust(8*len(msg),'0')
    
    def decrypt(self,pltxt,key):
        key_add = lambda x,key : [x[i]^key[i] for i in range(len(x))]
        bit_move = lambda x : [x[(i//4)+(i%4)*4] for i in range(len(x))]
        
        ct = [int(i) for i in pltxt]
        #print(ct,key)
        ct = key_add(ct,key[1])
        
        for i in range(5):
            if (i+1)%2:
                ct = bit_move(ct)
            ct = self.inv_s_trans(ct)
            ct = key_add(ct,key[i%2])
        
        return ''.join([str(i) for i in ct]) 
    
    def txt_decrypt(self,msg,key):
        output = []
        
        for i in range(len(msg)):
            now_re = self.decrypt(msg[i],key)
            output.append(now_re)
            
        return long_to_bytes(int(''.join(output),2))


m1 = [bin(bytes_to_long(plain[2*i:2*i+2]))[2:].rjust(16,'0') for i in range(36)]
c1 = [bin(bytes_to_long(final_c1[2*i:2*i+2]))[2:].rjust(16,'0') for i in range(36)]
c2 = [bin(bytes_to_long(final_c2[2*i:2*i+2]))[2:].rjust(16,'0') for i in range(49)]
a = CB_cipher()

for i in trange(2**8):
    dic_encbit = {}
    k0_4 = [int(k) for k in bin(i&0xffff0000)[2:].rjust(4,'0')]
    k1_4 = [int(k) for k in bin(i&0x0000ffff)[2:].rjust(4,'0')]
    for j in range(2**12):
        k0_12 = [int(k) for k in bin(j)[2:].rjust(12,'0')]
        k0 = k0_4+k0_12
        enc = ''
        for i in range(36):
            enc += str(a.e1(m1[i],k0,k1_4))
        enc = int(enc,2)
        if(enc in dic_encbit.keys()):
            dic_encbit[enc].append(k0)
        else:
            dic_encbit[enc] = [k0]
    for j in range(2**12):
        k1_12 = [int(k) for k in bin(j)[2:].rjust(12,'0')]
        k1 = k1_4+k1_12
        dec = ''
        for i in range(36):
            dec += str(a.d1(c1[i],k1,k0_4))
        dec = int(dec,2)
        if(dec in dic_encbit.keys()):
            for k0 in dic_encbit[dec]:
                message = a.txt_decrypt(c2,[k0,k1])
                if(b"DASCTF" in message):
                    print(message)
                    exit()

解得：

b'n\xa3 you break the cipher!!how could it be??????? the flag is:DASCTF{God_on_syM@etric_cRypto9raPhy}\x00'

其实前两个字节还有点小错误，正确flag中是”oh”，不过这个小bug暂时就不d了。

这样利用中间相遇攻击，复杂度就由爆破完整密钥的2^32降低到了2*2^20，因此最多约半小时就能爆破出结果。而且运气比较好，其实一分多钟就有正确结果。

一些补充

在复现完成后，出题师傅对我的一些说法进行了更细致的补充。就比如，其实再回头看我们刚才讲的encrypt函数不安全的第三点：

• bit_move函数中，有4个比特位并没有进行置换，分别是：0，5，10，15

其实这一点对安全性影响并不大，因为即使进行了置换，依然是可以中间相遇攻击的，步骤并没有什么大变化。这是因为，第三轮如何置换并不重要，我们需要的其实只是加密三轮和解密三轮后得到的位置相同的碰撞比特。这也就是说，我们其实也不一定非要在外层爆破K[0]，K[1]的前四比特，其实任选两组，只要能得到满足要求的碰撞比特，都是可以建立字典的。

通过这题收获到了很多，也非常感谢出题师傅对我思路上的帮助。