2024-DubheCTF-wp-crypto

太坐牢了，最后也只做出一个题目，归根结底还是自己水平不够，还要多学。赛中没做出的题目前面打*，赛后也还不会的打$。

*签到

题目描述：

嗯没错 还是Common Prime RSA

题目：

from Crypto.Util.number import *


n = 1000
gamma = 0.42
beta = 0.25


def keyGen(n, gamma):
    g = getPrime(round(n * gamma))
    while True:
        a, b = 2, 2
        while GCD(a, b) != 1:
            a = getRandomNBitInteger(round((.5 - gamma) * n - 1))
            b = getRandomNBitInteger(round((.5 - gamma) * n - 1))
        p, q, h = 2 * g * a + 1, 2 * g * b + 1, 2 * g * a * b + a + b
        if isPrime(p) and isPrime(q) and isPrime(h):
            break
    return p, q, g, a, b


p, q, g, a, b = keyGen(n, gamma)
d = getPrime(round(n * beta))
e = inverse(d, 2 * g * a * b)
print(f'N = {hex(p * q)}')
print(f'e = {hex(e)}')
flag = 'DubheCTF{{{:x}}}'.format(d & (2**128 - 1))

"""
N = 0xbe9ccc83003bedf45421b58377b946f87dfd85be82124dc5d732070d77ef68e0231c3f34dc803a8984de0573db6d83ccea0bd53a885059a10cfa3764c658c4d42c5fa90ecad8573fff8f2c41e513278c59121e42ad83310fb22b4d20e7ada42c76f08891f38c92a1b1aac712bfa7d717a4c4802ed023f12c768972ca1b
e = 0x5dc97ed7250e57ce6fac4f57885c0538b1ea540fbaca79730470b6b990f7e861adc4c5fee3acdcd9ae9a2834b606ddfae01ade33edfa96a47a0ffc0036a4497a84c38b7cdac20c38f
"""

题目描述也明确说了，这是common prime RSA，其形式可以总结为：

$$p = 2ga + 1$$ $$q = 2gb + 1$$ $$ed = 1 \quad(mod\;2gab)$$

其中各参数大小关系是：

$$d = N^{\beta} , g = N^{\gamma}$$

显然是一道论文题，用common prime当关键词可以搜到比较新的这篇：

Notes on Small Private Key Attacks on Common Prime RSA (iacr.org)

之后的步骤就比较固定，首先找到他的copper多项式：

其中小根分别是$(d,ak,nk)$，然后找他的shift多项式：

对着造一遍就可以copper试一试了。

然后就会发现这个论文对于这个题目情境好像并不是很满足，首先就是论文的界好像本来就并不满足题目条件：

然后就是论文的实际上界和理论界差的还有点多：

不过本着试一试说不定力大砖飞这个想法，还是对着论文写了一遍他的copper：

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

N = 0x4d1b4d1495283a766919e55365fd68ae1f729595401467b06fa67f7386be57ec089951679eaedbac8fddaf943828b5942d879e331d4583018049c7a6bbaed870e5db2a444730da0d550b3eb31c9cfa682cb43b5ea30fb4994ef2fbd6c317b0e8d2ea6fbd74de6ae357bd4c96ca95275b8efd211136c24b8968485b320f
e = 0xf2d57267270670ebd61f5f0a62030c7a94bdfde353ddb8af46e9cf1a8ab907479ee46084465ff400c02e547572f4736826fbe43a6e3765ae18dfce95a4854100ab9e1085ae1d17
d = 0x17c8548e5b2330ab435c698c1db1ea9e150f13582cb0dc7202e7b

gamma = 430/1000
beta = 0.209


X1 = int(N^beta)
X2 = int(N^(beta-gamma+0.5))
X3 = int(N^(beta-gamma+0.5))
X_ = int(N^(2*beta-2*gamma+2))


s = 4
#tau = (2*gamma - 8*beta + 1) / (4 * beta)
#actually for the task' params tau<0 ,so emm...
t = 0

poly=[]
monomials=set()
S = [(i1,i2,i3) for i2 in range(s) for i3 in range(s) for i1 in range(2*(s-1)-i2-i3-t+1)]
M = [(i1,i2,i3) for i2 in range(s+1) for i3 in range(s+1) for i1 in range(2*s-i2-i3-t+1)]

PR.<x1,x2,x3> = PolynomialRing(ZZ)
x1,x2,x3 = PR.gens()
f = 1 - 2*e*x1 + e^2*x1^2 - x2 - x3 + e*x1*x2 + e*x1*x3 + (1-N)*x2*x3


R = X_ * X1^(2*(s-1)+t) * (X2*X3)^(s-1)
for item in M:
    if(item in S):
        i1,i2,i3 = item
        g = x1^i1 * x2^i2 * x3^i3 * f * X1^(2*(s-1)+t-i1) * X2^(s-1-i2) * X3^(s-1-i3)
    else:
        i1,i2,i3 = item
        g = R * x1^i1 * x2^i2 * x3^i3
    poly.append(g)
    monomials.add(x1^i1 * x2^i2 * x3^i3)

L = Matrix(ZZ,len(poly),len(monomials))

for row,shift in enumerate(poly):
    for col,monomial in enumerate(monomials):
        L[row,col] = shift.monomial_coefficient(monomial)*monomial(X1,X2,X3)

res = L.LLL()
vec1 = res[0]
vec2 = res[1]

f1 = 0
for idx,monomial in enumerate(monomials):
        f1 += (vec1[idx] // monomial(X1,X2,X3)) * monomial
f1 = f1.change_ring(ZZ)
f2 = 0
for idx,monomial in enumerate(monomials):
        f2 += (vec2[idx] // monomial(X1,X2,X3)) * monomial
f2 = f2.change_ring(ZZ)

g1 = f.sylvester_matrix(f1, x3).det()
g2 = f.sylvester_matrix(f2, x3).det()


h = g1.sylvester_matrix(g2, x2).det()

res = h.univariate_polynomial().monic().roots()
print(res)
print(d)

数据是自己生成的，和论文s=4，t=0的情况基本符合，并且经过测试gamma最小也就只能取到0.43，再往下就copper不出来了，经测试大概需要跑10min就能跑出来。

s=4需要跑10min左右，那么对于题目数据，其减小了gamma，增大了beta，所以肯定要换用更大的s才有机会。然后我就试了试s=5，跑了3h没出，最后狠下心试了试s=6，然后就有了下图的惨案：

跑了27h，对于题目的界还是没跑出来哈哈。

请教了hashhash师傅这个问题，他指出这篇论文其实只是对gamma较小的情况做了优化，而gamma较大(也就是大于0.3)的情况这篇论文并没有优化到什么，而gamma较大的情况其实是15asia的一篇论文效果更好：

Solving Linear Equations Modulo Unknown Divisors: Revisited | SpringerLink

首先就可以注意到他的实验数据的界确实和题目符合的很好：

其实这一点在前面那篇论文有展示过，只是自己做的时候完全没看前面，直接往后看了OwO：

所以对于题目的参数$\gamma=0.42$，由图可以看出上界最大、效果最好的应该是Lu et al.’s Attack，那么就在论文里看看他的实现，首先是copper多项式：

这是一个模g^k下的多项式组，对这种多项式组进行copper的方法需要看上面的theorem10：

然后可以发现他的shift多项式以及项序的调整方式如下：

那么接下来就是用这个shift多项式去造copper然后LLL了。

但是这个论文就有点古怪，首先好像用来筛多项式的t似乎并没有说是什么东西，问了hashhash师傅后，才知道t是用下面这个不等式的bound算出的：

这里w是格L的维数。这里就会觉得很奇怪，明明需要t才能造出L，但是却又要用L的行列式和维数来算t，有点循环论证的感觉，不知道该怎么处理。然后又问hashhash师傅，他指出这就需要遍历t，造出每个t对应的格L，检查这个bound满不满足。

这下思路就通了，然后就是造格，造完过后resultant消去y就得到x的多项式，求根就得到d了，最后造出的L是81维，sage10.2大概需要跑10min的样子。

exp：

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

N = 0xbe9ccc83003bedf45421b58377b946f87dfd85be82124dc5d732070d77ef68e0231c3f34dc803a8984de0573db6d83ccea0bd53a885059a10cfa3764c658c4d42c5fa90ecad8573fff8f2c41e513278c59121e42ad83310fb22b4d20e7ada42c76f08891f38c92a1b1aac712bfa7d717a4c4802ed023f12c768972ca1b
e = 0x5dc97ed7250e57ce6fac4f57885c0538b1ea540fbaca79730470b6b990f7e861adc4c5fee3acdcd9ae9a2834b606ddfae01ade33edfa96a47a0ffc0036a4497a84c38b7cdac20c38f

gamma = 0.42
beta = 0.25


#fixed params
n = 2
r = 1
R = [0,1,2]
Gamma = [0,beta,1/2]
miu = gamma
E = inverse(e,N-1)
X = int(N^beta)
Y = int(N^(1/2))

PR.<x,y> = PolynomialRing(ZZ)
x,y = PR.gens()
f1 = E-x
f2 = N-y


#attack
t = 2
while(1):
    poly=[]
    monomials=set()

    #throw poly
    for j in range(1,n+1):
        if(Gamma[j] / R[j] > miu):
            continue

    for i1 in range(50):
        for i2 in range(50):
            I = [0,i1,i2]
            sum2 = 0
            for i in range(1,len(R)):
                sum2 += Gamma[i]*I[i]
            if(sum2 > miu*t):
                continue

            sum1 = 0
            for i in range(1,len(R)):
                sum1 += R[i]*I[i]
            d = max([0 , ceil(((t-sum1))/r)])
            G = f1^i1*f2^i2*(N-1)^d

            poly.append(G)
            monomials.add(x^i1*y^i2)

    L = Matrix(ZZ,len(poly),len(monomials))

    monomials = sorted(monomials)
    for row,shift in enumerate(poly):
        for col,monomial in enumerate(monomials):
            L[row,col] = shift.monomial_coefficient(monomial)*monomial(X,Y)

    w = L.dimensions()[0]

    #check t
    left = abs(2^((w-1)*w/4) * L.det())
    right = abs(((N-1)^(miu*t) / sqrt(w))^w)


    #if satisfy then LLL
    if(left < right):
        print(L.dimensions())
        res = L.LLL()
        vec1 = res[0]
        vec2 = res[1]

        g1 = 0
        for idx,monomial in enumerate(monomials):
                g1 += (vec1[idx] // monomial(X,Y)) * monomial
        g1 = g1.change_ring(ZZ)
        g2 = 0
        for idx,monomial in enumerate(monomials):
                g2 += (vec2[idx] // monomial(X,Y)) * monomial
        g2 = g2.change_ring(ZZ)

        h = g1.sylvester_matrix(g2, y).det()

        res = h.univariate_polynomial().monic().roots()
        d = int(res[0][0])
        break

    t += 1

flag = 'DubheCTF{{{:x}}}'.format(d & (2**128 - 1))
print(flag)

#DubheCTF{b896a5fef7abec06cd2e6256be4ba40b}

ezcrc

题目描述：

just a ezcrc :)

polys in the server are random,have fun
1.95.38.136 8888
1.95.38.136 9999
1.95.38.136 10000

题目：

#!/usr/bin/env python3
from socketserver import BaseRequestHandler,ThreadingTCPServer
import random
import os
import string
from hashlib import sha256
import signal
import json
from flag import flag

assert len(flag) == 42 and flag.startswith(b"DubheCTF{")

with open("polys.txt","r") as f:
    polys = json.load(f)

def random_poly():
    return polys[random.randint(0,len(polys)-1)]

N = 256

BANNER = br'''
 CCCCC  RRRRRR   CCCCC       GGGG    AAA   MM    MM EEEEEEE 
CC    C RR   RR CC    C     GG  GG  AAAAA  MMM  MMM EE      
CC      RRRRRR  CC         GG      AA   AA MM MM MM EEEEE   
CC    C RR  RR  CC    C    GG   GG AAAAAAA MM    MM EE      
 CCCCC  RR   RR  CCCCC      GGGGGG AA   AA MM    MM EEEEEEE 
 '''

class Task(BaseRequestHandler):

    def send(self, msg,newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def _recv(self, sz):
        try:
            r = sz
            res = b""
            while r > 0:
                res += self.request.recv(r)
                if res.endswith(b"\n"):
                    r = 0
                else:
                    r = sz - len(res)
            res = res.strip()
        except:
            res = b""
        return res.strip(b"\n")

    def recv(self, sz,prompt=b"> "):
        self.send(prompt,newline=False)
        return self._recv(sz)

    def _recvall(self):
        BUFF_SIZE = 1024
        data = b''
        while True:
            _recv = self.request.recv(BUFF_SIZE)
            data += _recv
            if len(_recv) < BUFF_SIZE:
                break
        return data

    def recvall(self,prompt=b"> "):
        self.send(prompt,newline=False)
        return self._recvall()

    def close(self):
        self.send(b'see you next time~~')
        self.request.close()



    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recvall(prompt=b'Give me XXXX: ')
        if len(x) != 4 or sha256(x + proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def crc256(self,msg,IN,OUT,POLY):
        crc = IN
        for b in msg:
            crc ^= b
            for _ in range(8):
                crc = (crc >> 1) ^ (POLY & -(crc & 1))
        return (crc ^ OUT).to_bytes(32,'big')

    def setup(self):
        self.send(BANNER)

    def handle(self):
        signal.alarm(120)
        if not self.proof_of_work():
            return
        # initial
        IN = random.getrandbits(N)
        OUT = random.getrandbits(N)
        POLY = random_poly()

        for i in range(5):
            self.send(b"what do you want to do?")
            self.send(b"1.calculate crc")
            self.send(b"2.getflag")
            self.send(b"3.exit")
            try:
                choice = self.recv(5).decode()
                if choice == '1':
                    self.send(b"Give me your message")
                    msg = self.recv(100)
                    crc_hex = self.crc256(msg,IN,OUT,POLY).hex()
                    self.send(b"Here is your crc: "+crc_hex.encode())
                elif choice == '2':
                    flag_crc = self.crc256(flag,IN,OUT,POLY).hex()
                    self.send(b"Here is your flag: "+flag_crc.encode())
                else:
                    self.close()
                    return
            except:
                self.send(b"error")
                pass


if __name__ == '__main__':
    HOST, PORT = "0.0.0.0", 10000
    server = ThreadingTCPServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

题目基于CRC256，只是做了如下改动：

def crc256(self,msg,IN,OUT,POLY):
    crc = IN
    for b in msg:
        crc ^= b
        for _ in range(8):
            crc = (crc >> 1) ^ (POLY & -(crc & 1))
    return (crc ^ OUT).to_bytes(32,'big')

其中IN和OUT是每次连接上靶机后生成的256bit的随机数。

然后我们有总共五次交互机会，每次交互机会可以：

• 输入”1”，能够输入一串长度小于100的消息，然后获得他的CRC256的值
• 输入”2”，能够获得flag的CRC256的值，并且题目保证了flag是”DubheCTF{}”包裹的长为42的串

而由于题目的poly、IN、OUT都是未知的，所以要获得利用flag的CRC256值去反求flag，就需要先利用选项1去把这些参数求出来。而对于一个标准的CRC256，也就是IN和OUT固定为预设值0和0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF(下面简记为FF)，其过程可以写作：

def crc256(self,msg,IN,OUT,POLY):
    crc = 0 ^^ 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    for b in msg:
        crc = crc ^^ c
        for i in range(8):
            crc = (crc >> 1) ^^ (POLY & -(crc & 1))
    return 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF ^^ crc

而看maple的一篇博客知道，这种标准的CRC可以用多项式表示成如下形式：

$$CRC(M) = Mx^n + Y + (Y+I)x^b \quad(mod\;G)$$

其中每个值的意义是：

• n是CRC的输出比特长度，对于CRC256也就是256

• b是输入消息msg的比特长度，对于flag来讲就是42x8

• M是msg的比特串对应的多项式，需要reverse

• Y是标准的OUT预设值，也就是FF对应的多项式，也需要reverse(虽然对于这个值来讲并没有区别)
• I是标准的IN预设值，是0，也需要reverse。这里要注意到题目的CRC256其实在最开始没有异或FF，所以对应的起始值应该是IN^FF

然后对于题目的CRC来讲，最后异或OUT的过程可以看作是先异或FF，再异或FF和OUT，也就是说可以看成是一个标准的CRC过程后面追加一个异或FF和OUT的操作，这在模2的多项式下可以看作是再加上一个Z多项式，因此对于这样的更一般的CRC，其过程可以写作：

$$CRC(M) = Mx^n + Y + (Y+I)x^b + Z \quad(mod\;G)$$

具体的等价形式与细节可以看下方的test。

那么回顾题目，我们不知道的是IN、OUT和G，但是n、b、M、Y以及CRC(M)的值都知道，所以我们可以尝试把所有已知的量放到同侧：

$$CRC(M) - Mx^n - Y - Yx^b = Ix^b + Z \quad(mod\;G)$$

此时等式左侧为已知量，右侧以及G为未知量。而对于题目，我们最多可以获取4组这样的消息以及CRC256值，，那么可以发现，只要我们输入的消息长度都相等，那么b就相等，也就是说等式右侧都相等。此时我们就可以计算三组等式左侧得到：

$$t_1 = CRC(M_1) - M_1x^n - Y - Yx^b$$ $$t_2 = CRC(M_2) - M_2x^n - Y - Yx^b$$ $$t_3 = CRC(M_3) - M_3x^n - Y - Yx^b$$

那么由于等式右侧相等，就有：

$$t_1 - t_2 = k_1G$$ $$t_1 - t_3 = k_2G$$

所以求GCD就能得到G。得到G过后建立商环，再简单作差就可以得到等式右侧的值，也就是：

$$Ix^b + Z \quad(mod\;G)$$

而如果我们控制输入消息长度都和flag一样，那么对于flag满足的多项式等式，其b也就相同，所以他也满足：

$$CRC(flag) = flagx^n + Y + (Y+I)x^b + Z \quad(mod\;G)$$

那么现在就可以求出：

$$flag \quad(mod\;G)$$

但是注意到flag长度是42，其对应多项式超过了模多项式的度，所以不能直接转整数得到flag。但是处理方式也很简单，比如我想到的两种做法就分别是：

• 由于给了已知flag的前后缀，刚好是10个字符，所以可以降低多项式的度，恰好得到flag中间段对应的度不超过G的多项式，就可以转整数

• 由于flag是静态的，所以连两次靶机拿两组数据可以得到：

  $$flag \quad(mod\;G_1)$$ $$flag \quad(mod\;G_2)$$

• 然后就可以CRT直接拿到flag了

我最后用的是CRT的方式，一些代码如下：

test(测试CRC256对于不同IN和OUT的统一形式)：

from Crypto.Util.number import *
import random
from os import urandom

polys = [74203660077649608144780466269496535818632419705053623866573741446360619747532]

def random_poly():
    return polys[random.randint(0,len(polys)-1)]

N = 256

def crc256(msg,IN,OUT,POLY):
    crc = IN
    for b in msg:
        crc ^^= b
        for _ in range(8):
            crc = (crc >> 1) ^^ (POLY & -(crc & 1))
    return int(crc ^^ OUT).to_bytes(32,'big').hex()

FF = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
IN = random.getrandbits(N)
OUT = random.getrandbits(N)
POLY = random_poly()

msg1 = b"1"*42
c1 = int(crc256(msg1,IN,OUT,POLY),16)
msg2 = b"2"*42
c2 = int(crc256(msg2,IN,OUT,POLY),16)
msg3 = b"DubheCTF{" + b"\x00" + b"}"
c3 = int(crc256(msg2,IN,OUT,POLY),16)

#poly check
R.<x> = GF(2)['x']
def i2p(p):
    return R(Integer(p).bits())

def p2i(p):
    return Integer(p.list(), 2)

def rev(p, n):
    p = (p.list() + [0] * n)[:n]
    return R(p[::-1])

POLY_rev = int("10100100000011011100100010000011101000101010011101010110011011001110010010100011011111001111011011001010110111001000000100001000011101000100000010100111011000010001100100011000000001100010000110000011111110001111001111100001001110111101001100001000110011001"[::-1],2)
G = i2p(POLY_rev)
I = i2p(FF ^^ IN)
Y = i2p(FF)
Z = i2p(OUT ^^ FF)
n = 256
b = len(msg1)*8
Y = rev(Y, n)
I = rev(I, n)
Z = rev(Z, n)


M1 = i2p(int.from_bytes(msg1, 'little'))
M1 = rev(M1, b)
crc1 = (M1 * x ^ n + (Y + I) * x ^ b + Y + Z) % G
t1 = (crc1 - M1 * x ^ n - Y*x^b - Y) % G
crc1 = rev(crc1, n)
print(t1)

print()

M2 = i2p(int.from_bytes(msg2, 'little'))
M2 = rev(M2, b)
crc2 = rev(i2p(c2),n)
print(crc2)
crc2 = (M2 * x ^ n + (Y + I) * x ^ b + Y + Z) % G
print(crc2)
t2 = (crc2 - M2 * x ^ n - Y*x^b - Y) % G
crc2 = rev(crc2, n)
print(t2)

print()


b = 10*8
M3 = i2p(int.from_bytes(msg2, 'little'))
M3 = rev(M3, b)
print(M3 % G)
T = GF(2^256, 'x', modulus = G)
enc = rev(i2p(c3),n)
cc = T(enc - Y*x^b - Y - t1) * (T(x^n)^(-1))
print(cc)

getdata(交互拿数据)：

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

#context.log_level = 'debug'

sh = remote("1.95.38.136",10000)

#part1 proof
def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = sh.recvuntil(b"sha256(XXXX+")
	temp = sh.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						sh.send(temp1.encode())
						return
proof_of_work()

#get msg
sh.recvuntil(b"3.exit")
sh.sendline(b"1")
sh.recvuntil(b"Give me your message")
sh.sendline(b"1"*42)
sh.recvuntil(b"Here is your crc: ")
print(sh.recvline())

sh.recvuntil(b"3.exit")
sh.sendline(b"1")
sh.recvuntil(b"Give me your message")
sh.sendline(b"2"*42)
sh.recvuntil(b"Here is your crc: ")
print(sh.recvline())

sh.recvuntil(b"3.exit")
sh.sendline(b"1")
sh.recvuntil(b"Give me your message")
sh.sendline(b"3"*42)
sh.recvuntil(b"Here is your crc: ")
print(sh.recvline())

sh.recvuntil(b"3.exit")
sh.sendline(b"2")
sh.recvuntil(b"Here is your flag: ")
print(sh.recvline())

data1：

from Crypto.Util.number import *
import random
from os import urandom



#poly check
R.<x> = GF(2)['x']

def i2p(p):
    return R(Integer(p).bits())

def p2i(p):
    return Integer(p.list(), 2)

def rev(p, n):
    p = (p.list() + [0] * n)[:n]
    return R(p[::-1])

ttt = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
POLY_rev = int("10100100000011011100100010000011101000101010011101010110011011001110010010100011011111001111011011001010110111001000000100001000011101000100000010100111011000010001100100011000000001100010000110000011111110001111001111100001001110111101001100001000110011001"[::-1],2)
G = i2p(POLY_rev)
Y = i2p(ttt)
n = 256
Y = rev(Y, n)


msg1 = b"1"*42
msg2 = b"2"*42
msg3 = b"3"*42

c1 = int("65eeaf9a8be0ca6d93d50fd29074741ffff3dbdcba129e370af3bf3f050ed774",16)
c2 = int("a809333633c9eea1c8dedf1098b78b01ee62f78058d5ad82c60b1ea43b59541e",16)
c3 = int("10a4a5949bc9d435af9c9d2c8ec89961eac9cde252849bd3991e4b45bd4bdc69",16)
flag_enc = int("6383fcb4aa2fe350634d3a2597bd4637e6d23fb19704231bcea94e7fc7b6d7de",16)

b = len(msg1)*8
#m1
M1 = i2p(int.from_bytes(msg1, 'little'))
M1 = rev(M1, b)
crc1 = rev(i2p(c1),n)
t1 = (crc1 - M1*x^n - Y*x^b - Y)

#m2
M2 = i2p(int.from_bytes(msg2, 'little'))
M2 = rev(M2, b)
crc2 = rev(i2p(c2),n)
t2 = (crc2 - M2*x^n - Y*x^b - Y)

#m2
M3 = i2p(int.from_bytes(msg3, 'little'))
M3 = rev(M3, b)
crc3 = rev(i2p(c3),n)
t3 = (crc3 - M3*x^n - Y*x^b - Y)


G = gcd(t1-t2,t1-t3)

#flag
T = GF(2^256, 'x', modulus = G)
b = 42*8
enc = rev(i2p(flag_enc),n)
cc = T(enc - Y*x^b - Y - t1) * (T(x^n)^(-1))
print(cc)

print(G)

data2：

from Crypto.Util.number import *
import random
from os import urandom



#poly check
R.<x> = GF(2)['x']

def i2p(p):
    return R(Integer(p).bits())

def p2i(p):
    return Integer(p.list(), 2)

def rev(p, n):
    p = (p.list() + [0] * n)[:n]
    return R(p[::-1])

ttt = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
POLY_rev = int("10100100000011011100100010000011101000101010011101010110011011001110010010100011011111001111011011001010110111001000000100001000011101000100000010100111011000010001100100011000000001100010000110000011111110001111001111100001001110111101001100001000110011001"[::-1],2)
G = i2p(POLY_rev)
Y = i2p(ttt)
n = 256
Y = rev(Y, n)


msg1 = b"1"*42
msg2 = b"2"*42
msg3 = b"3"*42

c1 = int("d49cc7e9274c9b586876da9e273c246aef66f71079c4c1c3979ffe9dbd5ce5bd",16)
c2 = int("e55ccd7ed71aa12da014ce00832f14a94d74c5a6d76a8bf1ea47a67a755d59d1",16)
c3 = int("725ab382552d6bfb42940c7afc005595d95d17cca96e669ed5d93d0196d71c62",16)
flag_enc = int("ccff536dbd0227a856c83bd42143770339ef5433dcfb3e3af773a751a37784a2",16)

b = len(msg1)*8
#m1
M1 = i2p(int.from_bytes(msg1, 'little'))
M1 = rev(M1, b)
crc1 = rev(i2p(c1),n)
t1 = (crc1 - M1*x^n - Y*x^b - Y)

#m2
M2 = i2p(int.from_bytes(msg2, 'little'))
M2 = rev(M2, b)
crc2 = rev(i2p(c2),n)
t2 = (crc2 - M2*x^n - Y*x^b - Y)

#m2
M3 = i2p(int.from_bytes(msg3, 'little'))
M3 = rev(M3, b)
crc3 = rev(i2p(c3),n)
t3 = (crc3 - M3*x^n - Y*x^b - Y)


G = gcd(t1-t2,t1-t3)
print(G)
#flag
T = GF(2^256, 'x', modulus = G)
b = 42*8
enc = rev(i2p(flag_enc),n)

cc = T(enc - Y*x^b - Y - t1) * (T(x^n)^(-1))
print(cc)

crt：

from Crypto.Util.number import *

R.<x> = GF(2)['x']

c1 = x^255 + x^254 + x^252 + x^250 + x^247 + x^246 + x^245 + x^243 + x^242 + x^241 + x^239 + x^238 + x^232 + x^229 + x^228 + x^227 + x^225 + x^224 + x^222 + x^217 + x^214 + x^213 + x^210 + x^208 + x^207 + x^204 + x^203 + x^202 + x^201 + x^199 + x^196 + x^195 + x^193 + x^191 + x^190 + x^189 + x^186 + x^185 + x^184 + x^178 + x^177 + x^175 + x^172 + x^169 + x^168 + x^167 + x^164 + x^161 + x^160 + x^159 + x^155 + x^152 + x^150 + x^148 + x^145 + x^144 + x^137 + x^135 + x^134 + x^133 + x^131 + x^130 + x^127 + x^124 + x^121 + x^119 + x^118 + x^115 + x^113 + x^112 + x^108 + x^107 + x^106 + x^104 + x^103 + x^102 + x^101 + x^97 + x^96 + x^93 + x^92 + x^91 + x^90 + x^89 + x^88 + x^86 + x^85 + x^83 + x^81 + x^77 + x^76 + x^74 + x^73 + x^70 + x^69 + x^62 + x^61 + x^59 + x^58 + x^55 + x^54 + x^51 + x^50 + x^49 + x^47 + x^46 + x^44 + x^43 + x^42 + x^41 + x^38 + x^36 + x^34 + x^31 + x^30 + x^28 + x^26 + x^25 + x^24 + x^23 + x^22 + x^18 + x^17 + x^14 + x^8 + x^7 + x^6 + x
G1 = x^256 + x^255 + x^252 + x^251 + x^250 + x^249 + x^248 + x^247 + x^245 + x^244 + x^235 + x^234 + x^230 + x^228 + x^227 + x^225 + x^224 + x^221 + x^220 + x^219 + x^217 + x^216 + x^215 + x^214 + x^213 + x^212 + x^210 + x^208 + x^207 + x^206 + x^202 + x^201 + x^200 + x^198 + x^197 + x^195 + x^191 + x^190 + x^186 + x^184 + x^181 + x^179 + x^178 + x^174 + x^172 + x^171 + x^166 + x^165 + x^164 + x^163 + x^162 + x^161 + x^159 + x^157 + x^156 + x^155 + x^154 + x^153 + x^151 + x^147 + x^146 + x^142 + x^141 + x^139 + x^138 + x^134 + x^133 + x^132 + x^127 + x^126 + x^125 + x^124 + x^123 + x^121 + x^120 + x^117 + x^114 + x^113 + x^111 + x^106 + x^103 + x^100 + x^99 + x^95 + x^94 + x^89 + x^87 + x^86 + x^84 + x^80 + x^78 + x^77 + x^74 + x^73 + x^71 + x^68 + x^67 + x^66 + x^65 + x^60 + x^59 + x^58 + x^56 + x^55 + x^53 + x^51 + x^50 + x^48 + x^45 + x^43 + x^34 + x^32 + x^31 + x^29 + x^26 + x^24 + x^23 + x^22 + x^19 + x^16 + x^12 + x^6 + 1
G2 = x^256 + x^253 + x^252 + x^251 + x^249 + x^247 + x^244 + x^243 + x^242 + x^240 + x^239 + x^238 + x^237 + x^236 + x^233 + x^230 + x^229 + x^227 + x^226 + x^225 + x^224 + x^223 + x^221 + x^219 + x^218 + x^216 + x^214 + x^212 + x^211 + x^210 + x^209 + x^208 + x^207 + x^205 + x^204 + x^203 + x^202 + x^200 + x^198 + x^197 + x^196 + x^195 + x^192 + x^191 + x^185 + x^184 + x^182 + x^181 + x^180 + x^179 + x^178 + x^176 + x^175 + x^171 + x^169 + x^166 + x^165 + x^163 + x^157 + x^150 + x^146 + x^141 + x^139 + x^138 + x^135 + x^134 + x^133 + x^132 + x^127 + x^126 + x^121 + x^120 + x^119 + x^116 + x^115 + x^114 + x^113 + x^111 + x^107 + x^106 + x^104 + x^102 + x^99 + x^92 + x^87 + x^84 + x^82 + x^80 + x^79 + x^75 + x^74 + x^73 + x^72 + x^71 + x^70 + x^69 + x^67 + x^66 + x^65 + x^63 + x^62 + x^61 + x^56 + x^54 + x^51 + x^50 + x^47 + x^46 + x^45 + x^39 + x^38 + x^36 + x^35 + x^34 + x^31 + x^28 + x^25 + x^24 + x^21 + x^17 + x^15 + x^13 + x^10 + x^9 + x^5 + x + 1
c2 = x^248 + x^247 + x^246 + x^245 + x^244 + x^243 + x^241 + x^240 + x^238 + x^237 + x^236 + x^233 + x^232 + x^231 + x^229 + x^226 + x^225 + x^224 + x^222 + x^220 + x^218 + x^216 + x^213 + x^212 + x^209 + x^206 + x^205 + x^204 + x^201 + x^196 + x^195 + x^194 + x^193 + x^192 + x^191 + x^189 + x^186 + x^185 + x^183 + x^182 + x^179 + x^171 + x^169 + x^168 + x^159 + x^158 + x^157 + x^156 + x^155 + x^152 + x^151 + x^150 + x^149 + x^148 + x^147 + x^143 + x^141 + x^139 + x^136 + x^135 + x^133 + x^132 + x^130 + x^125 + x^121 + x^119 + x^117 + x^114 + x^112 + x^110 + x^108 + x^107 + x^106 + x^104 + x^103 + x^100 + x^96 + x^92 + x^91 + x^88 + x^87 + x^83 + x^82 + x^77 + x^76 + x^74 + x^71 + x^66 + x^64 + x^59 + x^57 + x^54 + x^53 + x^52 + x^51 + x^46 + x^45 + x^44 + x^41 + x^40 + x^39 + x^37 + x^34 + x^33 + x^30 + x^26 + x^21 + x^20 + x^18 + x^17 + x^15 + x^11 + x^6 + x^4 + x^2 + 1

def p2i(p):
    return Integer(p.list(), 2)

def rev(p, n):
    p = (p.list() + [0] * n)[:n]
    return R(p[::-1])


M = crt([c1,c2],[G1,G2])
print(long_to_bytes(p2i(rev(M,42*8)))[::-1])


#DubheCTF{990676d29c2e351c80f382b065ba7418}

比赛过程中整个人很凌乱所以也就偷懒没有写成自动化，都是手动拿的数据。还有个比较坑的是proof of work需要用send而不是sendline，不然会多读一个换行而直接退出。

*MDH

题目描述：

题目提示：
【MDH】 代码中a和b的生成条件应该为getrandbits(590)，题目中代码有误，数据没有问题

题目：

from sage.all import *
from secret import flag
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime
from random import getrandbits


p = getPrime(256)
G = Zmod(p**3)
M = Matrix(G,[G.random_element() for i in range(64)],ncols=8)
a = getrandbits(560)
b = getrandbits(560)
S = M ** (a * b)


key = sha256(S.str().encode()).digest()
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex()


with open("output", "w") as f:
    f.write('p = ' + str(p) + '\n')
    f.write('M = ' + str(list(M)) + '\n')
    f.write('Ma =' + str(list(M**a)) + '\n')
    f.write('Mb = ' + str(list(M**b)) + '\n')
    f.write('ct = 0x' + ct)

题目是基于矩阵的Diffie-Hellman密钥交换，他给了基础矩阵M、M^a和M^b，需要求出共享密钥矩阵M^ab来解AES得到flag。其中a、b均是590bit，矩阵定义在$Z_{p^3}$下。

如果题目就只是题面看上去这样的话，其实做法很简单，比如对于Ma有：

$$Ma = M^a$$

两边取行列式就得到：

$$|Ma| = |M|^a \quad(mod\;p^3)$$

那么问题就变成已知下式的g、y和p，求解a的数域上的DLP了：

$$y = g^a \quad(mod\;p^3)$$

由欧拉定理可以知道：

$$y = g^{a \;mod \; \phi(p^3) } \quad(mod\;p^3)$$

也就是：

$$y = g^{a \;mod \; p^2(p-1) } \quad(mod\;p^3)$$

那么对于模p^3下的DLP，可以用p-adic求出a模p^2下的值，这就有大概512bit的信息；然后对于p-1，又可以取他的一些光滑因子去做pohlig-hellman，经测试他的光华因子有如下一些：

2^2 * 11 * 1399 * 576647 * 707717 * 31455197

可以发现刚刚好80bit，所以crt起来模数大概有592bit，因此就基本上可以得到准确的a、b了，即使差一点也可以很小范围爆破一下得到。

虽然这并不能解决题目的数据(至于为什么，马上就会提到)，不过我还是写了个简单的solver：

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime
from random import getrandbits


#gen data
p = 79008119711208495443423312926395331665944721527891616265679009115440018598629
G = Zmod(p**3)
M = Matrix(G,[G.random_element() for i in range(64)],ncols=8)
a = getrandbits(590)
b = getrandbits(590)
Ma = M^a
Mb = M^b
S = M ** (a * b)
print(a)
print(b)


#solve
print()
g = M.det()
ya = Ma.det()
yb = Mb.det()

#part1 p-adic
R = Zp(p, prec=3)
xa1 = (R(ya).log() / R(g).log()).lift()
xb1 = (R(yb).log() / R(g).log()).lift()


#part2 pohlig-hellman
T = 99986015309131554073222673357191122700463502810799771
order = 2^2 * 11 * 1399 * 576647 * 707717 * 31455197
xa2 = discrete_log(Mod(pow(ya,T,p),p),Mod(pow(g,T,p),p),ord=order)
xb2 = discrete_log(Mod(pow(yb,T,p),p),Mod(pow(g,T,p),p),ord=order)


#part3 crt
a_sol = crt([xa1,xa2],[p^2,order])
b_sol = crt([xb1,xb2],[p^2,order])
print(a_sol)
print(b_sol)
#maybe need a little bit bruteforce

然而用这种方法来求解题目数据的时候马上就遇到了困难，这是因为题目给的Ma、Mb都是奇异的，也就是行列式为0，那么这个解法直接就作废了。

开始觉得应该是题目数据有点问题，毕竟就题面这个代码，感觉怎么都生成不出来这么特殊的矩阵，何况根本就没有地方表现过”选择特殊矩阵”这一点。不过后面说题目数据没有问题，那就只能换方法了。

其实矩阵的DLP的核心思路都是相通的，就是把矩阵的乘方操作想办法转化成更易求DLP的东西的乘方操作。就比如行列式的这种解法，其实本质上就是把矩阵的幂看成了行列式的幂，从而建立了数域上的幂次，变成了数域上的DLP来简化。又比如常见的把矩阵对角化、抑或是化成jordan form这种求DLP的做法，其实本质上也是把矩阵化成对角线上元素的DLP、或者通过二项式把jordan块具有的关系展开，最终还是变成数域上的DLP。

而通过刚才对一般情况(行列式不为0)下DLP的求解，显然最终肯定还是要利用p-adic和pohlig-hellman的，也就是说无论怎么样，最后都要转化成一个模p^3下的数域上的DLP问题来解决本题目。所以核心就在于：对于行列式为0的矩阵，到底该怎么样转化才好。

而对于这个题目，由于Ma、Mb都是奇异的，所以没法对角化，也没法化成jordan form，然后我这里想过打印出特征多项式来看一看，确实都可以求特征多项式，那么现在矩阵DLP变成了多项式DLP。但接下来又该怎样把多项式DLP转化成数域上的DLP？到比赛结束也没想明白这个问题。

然后赛后问了问deebato师傅，他点出可以直接尝试选取一次特征根来变成数域上的DLP。想了想确实很有道理，对于一个矩阵M来说，他的特征多项式的根就是他的特征值，假设其中一个为t，那么M^e的对应特征值就是t^e，所以可以变成数域上的DLP。

而之所以不直接求eigenvalues，是因为对于模p^3下的奇异矩阵sage似乎求不了，所以要转成求charpoly的根。而其实模p^3下的根sage必须用multiplicities=False，也求的很慢，所以我选择先求模p下的根，然后hensel lifting到模p^3下解决。

不过自己直接照hensel lifting的迭代公式写的，不知道什么原因一直不行(我猜是因为导函数的问题)：

#lift to p^3
def hensel_lifting_broken(f,p):
    f_ = f.derivative()
    gp = int(f.change_ring(Zmod(p)).roots()[1][0])
    f = f.change_ring(ZZ)

    #lift to p^2
    gp2 = (gp - f(gp)*int(inverse(f_(gp),p))) % p^2
    #lift to p^3
    gp3 = (gp2 - f(gp2)*int(inverse(f_(gp2),p))) % p^3

    return gp3

所以最后改用求每次迭代的系数t：

#lift to p^3
def hensel_lifting(f,p):
    gp = int((f.change_ring(Zmod(p)).roots())[1][0])

    #lift to p^2
    f1 = (f(gp + x*p).change_ring(ZZ) / p).change_ring(Zmod(p))
    t1 = int(f1.roots()[0][0])

    #lift to p^3
    f2 = (f(gp + t1*p + x*p^2).change_ring(ZZ) / p^2).change_ring(Zmod(p))
    t2 = int(f2.roots()[0][0])

    return int(gp + t1*p + t2*p^2)

最终exp(pohlig带上2^2的话似乎会有点小错误，所以不用这个因子，缺少的bit小范围爆破解决)：

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import *
from random import getrandbits

p = 
M = 
Ma =
Mb = 
ct = 


#lift to p^3
def hensel_lifting_broken(f,p):
    f_ = f.derivative()
    gp = int(f.change_ring(Zmod(p)).roots()[1][0])
    f = f.change_ring(ZZ)

    #lift to p^2
    gp2 = (gp - f(gp)*int(inverse(f_(gp),p))) % p^2
    #lift to p^3
    gp3 = (gp2 - f(gp2)*int(inverse(f_(gp2),p))) % p^3

    return gp3

#lift to p^3
def hensel_lifting(f,p):
    gp = int((f.change_ring(Zmod(p)).roots())[1][0])

    #lift to p^2
    f1 = (f(gp + x*p).change_ring(ZZ) / p).change_ring(Zmod(p))
    t1 = int(f1.roots()[0][0])

    #lift to p^3
    f2 = (f(gp + t1*p + x*p^2).change_ring(ZZ) / p^2).change_ring(Zmod(p))
    t2 = int(f2.roots()[0][0])

    return int(gp + t1*p + t2*p^2)


G = Zmod(p^3)
M = Matrix(G,M)
Ma = Matrix(G,Ma)
Mb = Matrix(G,Mb)

#get eigenvalue in Zmod(p^3)
PR.<x> = PolynomialRing(G)
f = M.charpoly()
fa = Ma.charpoly()
fb = Mb.charpoly()
g = hensel_lifting(f,p)
ya = hensel_lifting(fa,p)
yb = hensel_lifting(fb,p)

#part1 p-adic
R = Zp(p, prec=3)
xa1 = (R(ya).log() / R(g).log()).lift()
xb1 = (R(yb).log() / R(g).log()).lift()


#part2 pohlig-hellman
T = 99986015309131554073222673357191122700463502810799771
order = 11 * 1399 * 576647 * 707717 * 31455197
xa2 = discrete_log(Mod(pow(ya,T,p),p),Mod(pow(g,T,p),p),ord=order)
xb2 = discrete_log(Mod(pow(yb,T,p),p),Mod(pow(g,T,p),p),ord=order)


#part3 crt
a = crt([xa1,xa2],[p^2,order])
b = crt([xb1,xb2],[p^2,order])

for i in range(10):
    if(M^a != Ma):
        a += order * p^2
        continue
    S = Mb^a
    key = sha256(S.str().encode()).digest()
    flag = AES.new(key, AES.MODE_ECB).decrypt(long_to_bytes(ct))
    print(flag)
    break

#DubheCTF{f8a014ae-d907-11ee-b427-d5accb963a48}

*$简简又单单

题目描述：

真是简简又单单啊，你们有做过这样简单的题吗？
题目提示：
1.代码中多余的部分为提示 2.题目类似于NTRU lattice trapdoor做解密

题目：

from sage.all import *
from hashlib import md5


def ternary_with_density(density):
    tmp = randrange(0, density)
    if tmp == 0:
        return 1
    elif tmp == 1:
        return -1
    else:
        return 0


def get_matrix(density):
    P = identity_matrix(ZZ, dims)
    for _ in range(2):
        Li = identity_matrix(ZZ, dims)
        Ui = identity_matrix(ZZ, dims)
        for i in range(dims):
            for j in range(i + 1, dims):
                Li[i, j] = ternary_with_density(density)
                Ui[j, i] = ternary_with_density(density)
        P *= Li * Ui
    return P


dims = 190
bits = 20
density = 30
p = random_prime(2**bits, lbound=2**(bits-1))
q = random_prime(2**bits, lbound=2**(bits-1))
N = p * q

X = get_matrix(density)
B = get_matrix(density)
limit = round(2.3 * RR(mean([abs(vi) for vi in (X * B).list()])))
K = random_matrix(ZZ, dims, x=-limit, y=limit+1)

Y = random_matrix(Zmod(N), dims).change_ring(ZZ)
C = p * random_matrix(Zmod(q), dims).change_ring(ZZ)
A = (X.inverse() * (K - Y * C)).change_ring(ZZ)

secret = get_matrix(density)[0]
flag = 'DubheCTF{' + md5(str(secret).encode()).hexdigest() + '}'

r = random_vector(ZZ, dims, x=-N, y=N)
t = get_matrix(density)[0]
cipher = secret * A + r * C + t
data = str(cipher.list()) + '\n' + str(X.list()) + '\n' + str(B.list()) + '\n' + str(C.list()) + '\n' + str(K.list())
open('./cipher.txt', 'w').write(data)

题目给出了一个等式：

$$cipher = secretA + rC + t$$

其中A为：

$$A = X^{-1}(K-YC)$$

然后给出cipher、X、B、C、K的值，要求解出secret来还原flag。其中secret、t都较小。

我首先想的就是把A先代回去，就有：

$$cipher = secret(X^{-1}(K-YC)) + rC + t$$

然后展开一下：

$$cipher = secretX^{-1}K + (secretX^{-1}Y + r)C + t$$

然后由于t比较小，我就想到了正交格的做法，就是找到一些短向量x，使得：

$$x \cdot cipher = 0$$ $$x \cdot X^{-1}K = 0$$ $$x \cdot C = 0$$

那么这样的x肯定也满足：

$$x \cdot t = 0$$

然后由于t较小，所以我在想有没有可能在x组成的向量空间的右核去规约找到他，但是题目维数有点大，所以失败了。

然后赛后交流了一下这个思路，rec师傅指出这中正交格的思路本质上其实和LWE没啥区别，也就是对于上面这个等式：

$$cipher = secretX^{-1}K + (secretX^{-1}Y + r)C + t$$

那么就应该存在线性关系：

$$(secret,(secretX^{-1}Y + r),1) \left( \begin{matrix} E & X^{-1}K & 0 \\ 0 & C & 0 \\ 0 & -cipher & 1 \end{matrix} \right) = (secret,t,1)$$

也就是说这就是一个格：

$$\left( \begin{matrix} E & X^{-1}K & 0 \\ 0 & C & 0 \\ 0 & -cipher & 1 \end{matrix} \right)$$

它里面存在着一个短向量：

$$(secret,t,1)$$

所以应该有机会规约出来。但是捣鼓了一下并没有成功XD：

exp：

from Crypto.Util.number import *
from hashlib import md5


dims = 190
cipher = 
X = 
B = 
C = 
K = 


X = Matrix(ZZ,dims,dims,X)
B = Matrix(ZZ,dims,dims,B)
C = Matrix(ZZ,dims,dims,C)
K = Matrix(ZZ,dims,dims,K)

L = block_matrix(
    [
        [1 , X.inverse()*K , 0],
        [0 , C , 0],
        [0 , Matrix(ZZ,cipher) , -1]
    ]
)
L = Matrix(ZZ,L)
print(L.dimensions())
L = L.LLL()

secret = L[0]
print(secret)
flag = 'DubheCTF{' + md5(str(secret).encode()).hexdigest() + '}'
print(flag)


#below is right answer
#secret : (11, -9, 6, -1, -1, 3, 4, 1, -10, 4, 17, -4, 7, 1, 8, -9, 7, -3, -2, -6, -4, 2, -4, 1, 3, -5, -10, -3, 1, -1, 1, -10, 4, 6, 6, 7, 4, 1, -5, 2, 1, 3, 8, -16, -2, 6, -5, 3, 5, 3, 6, 3, 8, -5, -3, -7, -8, 5, 7, -12, 1, -12, 1, 12, -2, 2, 5, 10, 5, 9, 8, 12, -3, 11, -7, -1, 14, -5, 5, 0, 4, -2, 5, 8, -3, -3, -6, -2, 17, 0, -3, -4, 0, 4, 0, 8, 3, 14, -17, 7, 14, -18, -2, 3, 14, 0, 3, -4, -4, -7, -2, 8, -9, 11, -4, 2, 3, 3, -1, 2, -8, -1, 3, -13, 1, -3, 0, -3, 1, 2, 4, -7, 3, -3, -3, 5, 4, 17, 3, 0, -3, 1, 0, 3, 3, 2, 0, 1, -1, 4, 8, -2, -6, -3, -5, 2, -3, 5, 0, -1, -3, 0, 6, 0, -4, 1, 2, -1, 0, 0, 0, -1, 3, -8, 1, -5, -1, -3, 3, 1, 1, -1, 3, -1, 3, -2, 0, 2, 3, 2)
#right : DubheCTF{b9a5671e706f26f52378e8b3139ab588}
#but I failed :(

有空去看看官方wp的思路。