第七届西湖论剑·中国杭州网络安全技能大赛-wp-crypto

记录一下赛题题解。

Or1cle

题目描述：

蒸馍会是，又是签到! :D

预期解

这个题目是没有附件的，只有先nc上去看看，连上靶机后会显示一下信息：

   _  __                                       __________        ___________ 
  | |/_/__ ___  ___  __ __    __              /\____;;___\      |          |
 _>  </ -_) _ \/ _ \/ // /   /o \________    | /  haruki /      |  flag    |
/_/|_|\__/_//_/_//_/\_, /    \_/       | |   .', ----. /|       |———————————
                   /___/                     ||     ||||        |
                                             \'.____.'||        |
                                              '--------'

1. get_signature
2. get_flag
3. gift
4. exit

但是这些是干什么的我们都一无所知，当务之急还是先尽可能获取有关源程序代码的信息。于是就想到去触发各种错误，看下有些什么报错信息。

首先发现输入2的时候，如果再输入的信息不是十六进制字符的话，就会触发报错，然后会暴露一段程序：

    self.P = self.d*secp256k1.G

    def signature(self,msg):
        h = int(hashlib.sha256(msg).hexdigest(),16)
        k = h^self.d
        r = (k*secp256k1.G).x
        s = inverse(k,secp256k1.q) * (h + r*self.d) % secp256k1.q
        return '%064x%064x' % (r, s)

    def verify(self,z, signature):
        r, s = int(signature[:64], 16), int(signature[64:], 16)
        z = int(hashlib.sha256(z).hexdigest(), 16)
        s_inv = pow(s, secp256k1.q - 2, secp256k1.q)
        u1 = (z * s_inv) % secp256k1.q
        u2 = (r * s_inv) % secp256k1.q
        point = u1 * secp256k1.G + u2 * self.P
        return point.x == r

banner = """
   _  __            

然后就是输入1可以获得自定义消息的签名值，但是最多五次，如果超过五次就会报错，就会暴露如下代码：

a = getPrime(256)
private_key = random.getrandbits(256) ^ a
xenny = Xenny(private_key)
client_socket.send(banner.encode())
co = 5
while True:
    client_socket.send(Menu.encode())
    choice = client_socket.recv(1024).decode().strip()
    if choice == '1' :
        if co == 0:
            raise CountError("No more!!!!")
        client_socket.send("give me something sign: ".encode())
        s = client_socket.recv(1024)[:-1]
        if b"xenny" in s:
            client_socket.send("What makes you think you can pose as Xenny?\n".encode())
            break
        sign = xenny.signature(s)
        client_socket.send(f"{sign}\n".encode())
        co -= 1
    elif choice == '2':
        client_socket.send("sign: ".encode())

这差不多就是能得到的所有信息了，拼凑起来，再补充上一点肯定有的代码(比如调库)，程序大概长下面这样：

import hashlib
from Crypto.Util.number import *
from fastecdsa.curve import secp256k1
import random





class Xenny():












    self.P = self.d*secp256k1.G

    def signature(self,msg):
        h = int(hashlib.sha256(msg).hexdigest(),16)
        k = h^self.d
        r = (k*secp256k1.G).x
        s = inverse(k,secp256k1.q) * (h + r*self.d) % secp256k1.q
        return '%064x%064x' % (r, s)

    def verify(self,z, signature):
        r, s = int(signature[:64], 16), int(signature[64:], 16)
        z = int(hashlib.sha256(z).hexdigest(), 16)
        s_inv = pow(s, secp256k1.q - 2, secp256k1.q)
        u1 = (z * s_inv) % secp256k1.q
        u2 = (r * s_inv) % secp256k1.q
        point = u1 * secp256k1.G + u2 * self.P
        return point.x == r

banner = """
   _  __                                       __________        ___________ 
  | |/_/__ ___  ___  __ __    __              /\____;;___\      |          |
 _>  </ -_) _ \/ _ \/ // /   /o \________    | /  haruki /      |  flag    |
/_/|_|\__/_//_/_//_/\_, /    \_/       | |   .', ----. /|       |———————————
                   /___/                     ||     ||||        |
                                             \'.____.'||        |
                                              '--------'
"""






















a = getPrime(256)
private_key = random.getrandbits(256) ^ a
xenny = Xenny(private_key)
client_socket.send(banner.encode())
co = 5
while True:
    client_socket.send(Menu.encode())
    choice = client_socket.recv(1024).decode().strip()
    if choice == '1' :
        if co == 0:
            raise CountError("No more!!!!")
        client_socket.send("give me something sign: ".encode())
        s = client_socket.recv(1024)[:-1]
        if b"xenny" in s:
            client_socket.send("What makes you think you can pose as Xenny?\n".encode())
            break
        sign = xenny.signature(s)
        client_socket.send(f"{sign}\n".encode())
        co -= 1
    elif choice == '2':
        client_socket.send("sign: ".encode())

目的是拿到flag。

除了程序代码以外，在随便乱试的时候还能看出一些程序的功能，比如：

• 输入3后，似乎可以进行MT19937产生的32bit的伪随机数预测，虽然预测正确好像也没什么用
• 输入2后，如果输入的确实是十六进制串，也即没有让程序报错，那么程序会返回的是”Only xenny can get flag”

那么再结合代码对于输入1时的描述，大概可以知道要干什么了：

• 可以得到最多五组对自定义消息的签名值，并且自定义的消息不能有”xenny”
• 输入2是对签名值进行核验，如果我们给出的签名值能对”xenny”验签通过，那么就会得到flag
• 输入3可以得到多组随机数，可以用MT19937相关办法进行伪随机数向后预测或者向前预测，比如可以得到private_key中的getrandbits(256)的值，但是好像也并没有什么用

所以问题就转化成了已知五组签名值，进行”xenny”的签名伪造。进一步来说，也就是已知五组签名求出签名用的私钥d。(因为sha256想找到一个”xenny”的碰撞几乎是不可能的)

那么就聚焦在签名函数上找突破口：

def signature(self,msg):
    h = int(hashlib.sha256(msg).hexdigest(),16)
    k = h^self.d
    r = (k*secp256k1.G).x
    s = inverse(k,secp256k1.q) * (h + r*self.d) % secp256k1.q
    return '%064x%064x' % (r, s)

很显眼的一个地方是：

k = h^self.d

也就是每次用的临时密钥k是和d有关系的，把这个关系写出来：

$$s_i(h_i\oplus d) = h_i + r_id \quad(mod\;q)$$

而由于曲线参数都是公开的，那么这样一来，等式其实就只有d一个未知量，并且我们还可以有五组这样的等式。所以自然的想法就是z3梭一下。

但是这样出不来，因为中间的异或运算很麻烦，异或相当于把一个未知数变成了他的bit那么多个未知数，所以这样是解不了的。

然后就想到N1CTF的e2D1p那个题目，就是把两个量的异或转化成累加和的形式，但是那会依赖于d的每一bit本身是0还是1，因此会有未知数在指数上，没有办法计算。

思路也就一直卡在这里，中间一直在想几个问题：

• 输入3那个选项到底有什么用？因为我就算预测正确，提交下一个伪随机数，他也只是hahaha就过去了，不会给什么额外信息
• 有没有什么更好的办法解上面那个方程？

最后在maple的博客上找到了这个题目的原版，改一改脚本就能直接用。不过思路我觉得非常有意思，就详细记录一下，原wp指路：

TSJ CTF 2022 WriteUps | 廢文集中區 (maple3142.net)

主要思路是从以下等式出发，对于任意两个整数a、b，有：

$$a \oplus b = a + b - 2(a \;and\; b)$$

其中and就是与运算(转义有点问题，数学公式里打不了&符号)，这个等式很神奇，并且验证一下确实是正确的：

from Crypto.Util.number import *

for i in range(100):
    a = getPrime(200)
    b = getPrime(200)
    print((a^b) == (a+b-2*(a&b)))

而&运算又可以转化成累加和的形式如下：

$$a \; and \; b = \sum_{i=0}^{n}{2^ia_ib_i}$$

其中ai和bi就是a和b的每个比特位，再把这个式子代回上一个式子，我们就可以将位运算完全变成四则运算了：

$$a \oplus b = a + b - 2(\sum_{i=0}^{n}{2^ia_ib_i})$$

那么再回看签名式：

$$s_i(h_i\oplus d) = h_i + r_id \quad(mod\;q)$$

就变成：

$$s_i(h_i + d - 2(\sum_{j=0}^{n}{2^jh_{ij}d_j})) = h_i + r_id \quad(mod\;q)$$

而这样写出来等式又能干什么？注意到这里未知量只有d和d的各个bit，而每个bit都是0或1，是非常小的量，因此可以造格。我们就拿其中一个式子举例：

$$s_0(h_0 + d - 2(\sum_{j=0}^{n}{2^jh_{0j}d_j})) = h_0 + r_0d \quad(mod\;q)$$

写成更方便造出格的等式形式：

$$h_0(s_0-1) + d(s_0-r_0) - 2^{(0+1)}s_0h_{0,0}d_0 - 2^{(1+1)}s_0h_{0,1}d_1 - ... 2^{(255+1)}s_0h_{0,255}d_{255} + t_iq = 0$$

用五组签名写出五个上面这样的等式，于是就造出如下格：

$$\left(\begin{matrix} 1& & && &-2^{1}s_0h_{0,0} &-2^{1}s_1h_{1,0} & &-2^{1}s_4h_{4,0}\\ &1& && &-2^{2}s_0h_{0,1} &-2^{2}s_1h_{1,1} & &-2^{2}s_4h_{4,1}\\ & & ... && &...&... &...&...\\ & & &1& &-2^{256}s_0h_{0,255} &-2^{256}s_1h_{1,255} & &-2^{256}s_4h_{4,255}\\ & & &&1 &h_0(s_0-1) &h_1(s_1-1) & &h_4(s_4-1)\\ & & && &s_0-r_0 &s_1-r_1 & &s_4-r_4\\ & & && &q & & &\\ & & && & &q& &\\ & & && & &&...&\\ & & && & && &q\\ \end{matrix} \right)$$

这个格具有如下线性关系：

$$(d_0,d_1,d_2,...d_{255},1,d,t_0,t_1,t_2,t_3,t_4) \left(\begin{matrix} 1& & && &-2^{1}s_0h_{0,0} &-2^{1}s_1h_{1,0} & &-2^{1}s_4h_{4,0}\\ &1& && &-2^{2}s_0h_{0,1} &-2^{2}s_1h_{1,1} & &-2^{2}s_4h_{4,1}\\ & & ... && &...&... &...&...\\ & & &1& &-2^{256}s_0h_{0,255} &-2^{256}s_1h_{1,255} & &-2^{256}s_4h_{4,255}\\ & & &&1 &h_0(s_0-1) &h_1(s_1-1) & &h_4(s_4-1)\\ & & && &s_0-r_0 &s_1-r_1 & &s_4-r_4\\ & & && &q & & &\\ & & && & &q& &\\ & & && & &&...&\\ & & && & && &q\\ \end{matrix} \right) = (d_0,d_1,d_2,...d_{255},1,0,0,0,0,0)$$

仍然可以在最后几列配上大系数保证规约出0，并且注意，为了目标向量中不出现d这个较大的量，单位矩阵中刻意少了他的那一列。然后在LLL得到的向量中找全为01的就能还原d。

不过这样写格的话，首先会比maple那样造的格慢两分钟左右，并且实际测出来有两三位是错的，所以可能还要爆破几个位置来求出正确的d，至于错误的原因，我想应该是因为这样造格会多出一些有线性关系的量。所以有兴趣的师傅可以看看maple怎么造的格(虽然我怎么看都觉得没啥区别)，我也就直接用maple的轮子做题了。

还原出d后伪造”xenny”的签名，就可以通过验签拿到flag。下面先给出我自己造格的测试脚本，有兴趣的师傅可以看看为什么会出错：

from fastecdsa.curve import secp256k1
from hashlib import sha256

length = 5
h = [int(sha256(i).hexdigest(),16) for i in [b"0",b"1",b"2",b"3",b"4"]]
R = [31096735160651542514594148009444423392167145102850530827072444936893298085958, 1667700963153923083527357426619475090281803852648628765437316264051704897418, 16771314321505205143350123534500543552096118001424456331703672486750061761147, 111915263401277449638289396518382362342281446247506473910053678600849562173658, 4006411196893119279631442159210712836445881069979083382732132911330173248009]
S = [81657507529738672978079292900378814222549660333861377490434484387584127131100, 18471119190696882624802078010087114511389523902107255054021489181061816819234, 60234894853906247501079104442478939240255694078000750083432688313202661346696, 86544211048945675316874110304800510445472680246693352484986608188131953425157, 78874088475992399611084479122315153430100025584295640315650967987201653683057]
#d = 64875426355440626643099882733692643061105383093107059159523050961269086610413
sigs = []
for i in range(length):
    sigs.append((h[i],R[i],S[i]))

T = 2^100
L = Matrix(ZZ,256+length+2,256+length+1)
for i in range(256+1):
    L[i,i] = 1
for i in range(length):
    for j in range(256):
        temp = bin(h[i])[2:].zfill(256)[::-1]
        L[j,i+256+1] = -S[i]*2*2^j*int(temp[j])*T
    L[256,i+256+1] = h[i]*(S[i]-1)*T
    L[257,i+256+1] = (S[i]-R[i])*T
    L[258+i,i+256+1] = secp256k1.q*T

res = L.LLL()
for i in res:
    if(all(j == 0 or j == 1 for j in i) and (1 in i)):
        tt = i[:-6][::-1]
        temp = "".join(list(map(str,tt)))
        print(int(temp,2))

题目exp：

from Pwn4Sage.pwn import *
from tqdm import *
from Crypto.Util.number import *
from fastecdsa.curve import secp256k1 as CURVE
from hashlib import sha256

#context.log_level = 'debug'

sh = remote("1.14.108.193",32252)

R = []
S = []
z = [int(sha256(i).hexdigest(),16) for i in [b"0",b"1",b"2",b"3",b"4"]]
if(1):
    for i in range(5):
        sh.sendline(b"1")

        sh.recvuntil(b"give me something sign:")
        msg = str(i).encode()
        sh.sendline(msg)
        rs = sh.recvline().strip().decode()
        r,s = int(rs[:len(rs)//2],16),int(rs[len(rs)//2:],16)
        R.append(r)
        S.append(s) 
print(R)
print(S) 
sigs = []
for i in range(5):
    sigs.append((z[i],R[i],S[i]))


#part2 get d
def recover_d(sigs):
    P = PolynomialRing(Zmod(CURVE.q), "d", 256)
    ds = P.gens()
    dd = sum([2 ** i * di for i, di in enumerate(ds)])
    polys = []
    for z, r, s in sigs:
        d_and_z = sum([2 ** i * ((z & (1 << i)) >> i) * di for i, di in enumerate(ds)])
        # fact: (a xor b) = a + b - 2 * (a and b)
        k = dd + z - 2 * d_and_z
        polys.append((s * k) - (z + r * dd))
    M, v = Sequence(polys).coefficient_matrix()
    print(v.T)
    M = M.T.dense_matrix()
    a, b = M.dimensions()
    B = block_matrix(
        ZZ, [[matrix.identity(b) * CURVE.q, matrix.zero(b, a)], [M, matrix.identity(a)]]
    )
    B[:, :b] *= 2 ^ 64
    print("LLL", B.dimensions())
    for row in B.LLL():
        if row[:b] == 0 and row[-1] == 1 and all(0 <= x <= 1 for x in row[b:-1]):
            dbits = row[b:-1]
            d = int("".join(map(str, dbits[::-1])), 2)
            return d

d = recover_d(sigs)
print(d)
#part3 get flag
h = int(sha256(b"xenny").hexdigest(),16)
k = h^^d
r = (k*CURVE.G).x
s = inverse(k,CURVE.q) * (h + r*d) % CURVE.q
signature = hex(r)[2:].zfill(64)+hex(s)[2:].zfill(64)

sh.sendline(b"2")
sh.recvuntil(b"sign: ")
sh.sendline(signature.encode())
sh.recvline()
print(sh.recvline())

#DASCTF{78943141727048138370021112939999}

非预期解

绷不住了，请看大屏幕：

而之所以可以这样是因为verify里没有对0进行检查，并且求逆用的不是inverse，而是：

s_inv = pow(s, secp256k1.q - 2, secp256k1.q)

导致点的乘数都是0，所以验签自然通过。

(2.1更新)

突然就想明白为什么自己造的格不太对了，确实是因为多了一些线性相关的量。回看刚才的展开式：

$$h_0(s_0-1) + d(s_0-r_0) - 2^{(0+1)}s_0h_{0,0}d_0 - 2^{(1+1)}s_0h_{0,1}d_1 - ... 2^{(255+1)}s_0h_{0,255}d_{255} + t_iq = 0$$

这里面的d也是完全可以展开写成256个bit的线性表达式的，所以就可以完全没有d这个量，也就是写成如下形式：

$$h_0(s_0-1) + (\sum_{i=0}^{255}{2^id_i})(s_0-r_0) - 2^{(0+1)}s_0h_{0,0}d_0 - 2^{(1+1)}s_0h_{0,1}d_1 - ... 2^{(255+1)}s_0h_{0,255}d_{255} + t_iq = 0$$

那么合并同类项就是：

$$h_0(s_0-1) + ((s_0-r_0)2^0-2^{(0+1)}s_0h_{0,0})d_0 + ((s_0-r_0)2^1-2^{(1+1)}s_0h_{0,1})d_1 + ... +((s_0-r_0)2^{255}-2^{(255+1)}s_0h_{0,255})d_{255} + t_iq = 0$$

格也就对应改成：

$$\left(\begin{matrix} 1& & && &(s_0-r_0)2^0-2^{(0+1)}s_0h_{0,0} &(s_1-r_1)2^0-2^{(0+1)}s_1h_{1,0} & &(s_4-r_4)2^0-2^{(0+1)}s_4h_{4,0}\\ &1& && &(s_0-r_0)2^1-2^{(1+1)}s_0h_{0,1} &(s_1-r_1)2^1-2^{(1+1)}s_1h_{1,1} & &(s_4-r_4)2^1-2^{(1+1)}s_4h_{4,1}\\ & & ... && &...&... &...&...\\ & & &1& &(s_0-r_0)2^{255}-2^{(255+1)}s_0h_{0,255} &(s_1-r_1)2^{255}-2^{(255+1)}s_1h_{1,255} & &(s_4-r_4)2^{255}-2^{(255+1)}s_4h_{4,255}\\ & & &&1 &h_0(s_0-1) &h_1(s_1-1) & &h_4(s_4-1)\\ & & && &q & & &\\ & & && & &q& &\\ & & && & &&...&\\ & & && & && &q\\ \end{matrix} \right)$$

这样就完全成功了，exp如下：

from fastecdsa.curve import secp256k1
from hashlib import sha256

length = 5
h = [int(sha256(i).hexdigest(),16) for i in [b"0",b"1",b"2",b"3",b"4",b"5"]]
R = [55438565207338188985477948297707383628133456043967096650050086162051382496685, 34370854298730072144481322984891357107485048475128920596006200148827039913808, 42184687889006972324884463428221215625989889935954570330229503951065096406265, 11807003657326746264282983667121063011176360419977702570602350915945501544482, 47805548692870774375076399860895996704082492117937603108794432517276992511135, 105429926378257594893189380170635466553420743820842445505795357046243674098923]
S = [91437568456730022379614175047567583259582804228196202671899274499409848470343, 68469458461887354512592080860220721446661199513502071317692562031156156711233, 8599215819039971355550707782160988410370689757696771960517487446632997405198, 2897666418217511899561751558853778473112016259151461180116106453564309557576, 7457580251740237348721776132961481664010839036161094090135121076623209719605, 79701192002212969894680356281723834279212313476946240809672720170860816327146]
#d = 76843059829300774502301911378398708933327237745683561605401157268735347763583
sigs = []
for i in range(length):
    sigs.append((h[i],R[i],S[i]))

T = 2^100
L = Matrix(ZZ,256+length+1,256+length+1)
for i in range(256+1):
    L[i,i] = 1
for i in range(length):
    for j in range(256):
        temp = bin(h[i])[2:].zfill(256)[::-1]
        L[j,i+256+1] = ((S[i]-R[i])*2^j-S[i]*2*2^j*int(temp[j]))*T
    L[256,i+256+1] = h[i]*(S[i]-1)*T
    L[257+i,i+256+1] = secp256k1.q*T

res = L.LLL()
for i in res:
    if(all(j == 0 or j == 1 for j in i) and (1 in i)):
        tt = i[:-length-1][::-1]
        temp = "".join(list(map(str,tt)))
        print(int(temp,2))
    if(all(j == 0 or j == -1 for j in i) and (-1 in i)):
        tt = i[:-length-1][::-1]
        for i in range(len(tt)):
            tt[i] = -tt[i]
        temp = "".join(list(map(str,tt)))
        print(int(temp,2))

测下来其实四组签名也能出，但三组就不行了。

Or2cle

题目描述：

签到题！ :D

hint：

附件中proof是被修改过的，不影响做题

题目：

from Crypto.Util.number import *
from hashlib import *
import os
from Crypto.Cipher import AES
from Crypto.Util import Counter
from random import *
import socket
import threading
import base64

FLAG = bytes(os.getenv("DASFLAG").encode())

class Proof():
    def S(self,n):
        factors = set()
        while n % 2 == 0:
            factors.add(2)
            n //= 2
        for i in range(3, int(n**0.5) + 1, 2):
            while n % i == 0:
                factors.add(i)
                n //= i
        if n > 2:
            factors.add(n)
        
        return factors

    def Y(self,n):
        if n == 1:
            return 1

        result = n
        for p in self.S(n):
            result *= (1 - 1 / p)
        return int(result)


    def proof(self,n):
        res = 0
        for m in range(1, n+1):
            for l in range(1, m+1):
                for k in range(1, l+1):
                    for j in range(1, k+1):
                        for i in range(1, j+1):
                            for h in range(1, i+1):
                                for g in range(1, h+1):
                                    for f in range(1, g+1):
                                        for e in range(1, f+1):
                                            for d in range(1, e+1):
                                                for c in range(1, d+1):
                                                    for b in range(1, c+1):
                                                        for a in range(1, b+1):
                                                            res +=  b//a*(self.Y(a))
        return res


class Harukii_Oracle:

    def __init__(self,key):
        self.k  = key

    def pad(self, plaintext):
        block_size = randint(1,len(plaintext)-1)
        if len(plaintext) <  block_size :
            return plaintext
        else:
            padding_length = len(plaintext) // 16
            padding_byets = bytes([padding_length])
            plaintext = plaintext.replace(padding_byets,b"\x00")
            p = plaintext[:16]
            for i in range(1 , padding_length+1):
                p += padding_byets + plaintext[16*i:16*(i+1)]
            return p

    def encrypt(self,plaintext):
        aes = AES.new(self.k,mode=AES.MODE_CTR,counter=Counter.new(128))
        chipertext = aes.encrypt(self.pad(plaintext))
        return chipertext
    
    def gift(self,ciphertext):
        aes = AES.new(self.k,mode=AES.MODE_CTR,counter=Counter.new(128))
        plaintext = aes.decrypt(ciphertext)
        padding_length = len(plaintext) // 16
        padding_bytes = bytes([padding_length])
        return plaintext.count(padding_bytes) == padding_length
        

Menu = """
1. get flag
2. gift
3. exit
"""

def task(client_socket):
    client_socket.settimeout(60)
    s = str((getPrime(128)))
    client_socket.send(f"s : {s}\n".encode())
    client_socket.send("Give me a hash: ".encode())
    hash = client_socket.recv(1024)[:-1]
    hash = int(hash,16)
    if hash != int(sha256(str(Proof.proof(s)).encode()).hexdigest(),16):
        client_socket.send(": C".encode())
        exit(-1)
    key = randbytes(16)
    YSGS = Harukii_Oracle(key=key)
    while True:
        try:
            client_socket.send(Menu.encode())
            choice = client_socket.recv(1024).decode().strip()
            if choice == '1' :
                enc_flag = base64.b64encode(YSGS.encrypt(FLAG))
                client_socket.send(f"This is Your flag {enc_flag}".encode())
            elif choice == '2':
                c = client_socket.recv(1024)[:-1]
                if YSGS.gift(c):
                    client_socket.send("Dec successfully".encode())
                else:
                    client_socket.send("Dec faild".encode())

            else:
                exit(-1)
        except Exception as e:
            print(e)


def main():
    server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    server.bind(("0.0.0.0", 9999))
    server.listen(100)
    
    try:
        while True:
            client_sock, address = server.accept()
            
            print(f"Accepted connection from {address[0]}:{address[1]}")
            client_handler = threading.Thread(target=task, args=(client_sock,))
            client_handler.start()
    finally:
        server.close()

if __name__ == "__main__":
    main()

题目略长，具体题意需要自己看一下理解清楚，我就直接进入解题流程。

题目首先会给出一个s，需要你快速计算出s的proof函数的值，而proof函数长这样：

class Proof():
    def S(self,n):
        factors = set()
        while n % 2 == 0:
            factors.add(2)
            n //= 2
        for i in range(3, int(n**0.5) + 1, 2):
            while n % i == 0:
                factors.add(i)
                n //= i
        if n > 2:
            factors.add(n)
        
        return factors

    def Y(self,n):
        if n == 1:
            return 1

        result = n
        for p in self.S(n):
            result *= (1 - 1 / p)
        return int(result)


    def proof(self,n):
        res = 0
        for m in range(1, n+1):
            for l in range(1, m+1):
                for k in range(1, l+1):
                    for j in range(1, k+1):
                        for i in range(1, j+1):
                            for h in range(1, i+1):
                                for g in range(1, h+1):
                                    for f in range(1, g+1):
                                        for e in range(1, f+1):
                                            for d in range(1, e+1):
                                                for c in range(1, d+1):
                                                    for b in range(1, c+1):
                                                        for a in range(1, b+1):
                                                            res +=  b//a*(self.Y(a))
        return res

这么多层循环，直接用他的跑肯定不可能，所以要想其他办法。熟悉一点的可以看出，函数S是分解n，而函数Y是计算phi(n)，但是好像还是没什么用。

不过小的数字还是能跑的，所以可以取前几项过后，上oeis查数列，会发现它计算的其实是组合数C(n,14)，所以直接用math里的comb函数就可以快速计算了。计算出结果，并求得其哈希返回给靶机，就能进入下一环节。

下一环节其实就很简单，他用了一个很奇怪的padding，自己试一下就知道，他会在每个分组的后面加上一个代表分组数量的字节来进行padding，并且提供两个功能：

• 输入1，获得flag的AES-CTR模式加密结果
• 输入2，可以解密一个消息，判断它是不是正确padding了，判断的依据是padding字节的数量正不正确

而问题就在于CTR模式，CTR模式中，AES加密的是Counter，然后把加密得到的Counter与明文异或得到密文。因此，我们对输入1得到的flag密文，改变其中任意一个不是padding位置的字节，在AES解密后得到的明文中，就也只有这一个位置的字节被改变了。

而我们对这一个被改变的字节，遍历256种可能取值，当且仅当解密后的明文恰为padding字节的值时，靶机会返回给我们failed，因为这个时候padding字节多出来一个。我们将这时候的这个字节值记为t。

而padding字节的值是多少，这个我们是知道的，因为我们从输入1返回的密文中，可以知道flag的长度是42，也就自然知道了有几个分组。我们把它记为r。而CTR模式又有一个很重要的性质，也就是同一分组的明文异或等于密文异或，因此对于当前这个字节，其本身的加密值是enc的话，我们就可以由：

$$m = enc \oplus t \oplus r$$

求出当前这个字节的明文值。因此我们就可以逐字符爆破，并求出flag的全部内容。

exp：

from pwn import *
from Crypto.Util.number import *
from hashlib import *
from math import comb
from base64 import *
from tqdm import *

#context.log_level = 'debug'

sh = remote("1.14.108.193",30376)

#part1 pass hash
sh.recvuntil(b"s : ")
s = int(sh.recvline().strip().decode())
sh.recvuntil(b"Give me a hash: ")
hash = sha256(str(comb(s+13,14)).encode()).hexdigest().encode()
sh.sendline(hash)

#part2 oracle
sh.sendline(b"1")
sh.recvuntil(b"This is Your flag ")
enc_flag = b64decode(sh.recvline().strip().decode()[2:-1])

#group1
if(0):
    for i in range(15,16):
        for j in trange(256):
            sh.sendline(b"2")
            msg = enc_flag[:i] + long_to_bytes(j) + enc_flag[i+1:]
            sh.sendline(msg)
            sh.recvuntil(b"Dec ")
            temp = sh.recvline()
            if(b"fail" in temp):
                print(chr(j ^ enc_flag[i] ^ 2))
                break

#group2
if(0):
    for i in range(17,33):
        for j in trange(256):
            sh.sendline(b"2")
            msg = enc_flag[:i] + long_to_bytes(j) + enc_flag[i+1:]
            sh.sendline(msg)
            sh.recvuntil(b"Dec ")
            temp = sh.recvline()
            if(b"fail" in temp):
                print(chr(j ^ enc_flag[i] ^ 2))
                break

#group3
if(1):
    for i in range(41,43):
        for j in trange(256):
            sh.sendline(b"2")
            msg = enc_flag[:i] + long_to_bytes(j) + enc_flag[i+1:]
            sh.sendline(msg)
            sh.recvuntil(b"Dec ")
            temp = sh.recvline()
            if(b"fail" in temp):
                print(chr(j ^ enc_flag[i] ^ 2))
                break
            
#DASCTF{76155910447198639966109820260259}