首页 网络安全 CTFwp

# Nepsign：

# 问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from gmssl import sm3
from random import SystemRandom
from ast import literal_eval
import os
flag = os.environ["FLAG"]
def SM3(data):
    d = [i for i in data]
    h = sm3.sm3_hash(d)
    return h
def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        data = bytes.fromhex(SM3(data))
    return data.hex()[:bits // 4]


class Nepsign():
    def __init__(self):
        self.n = 256
        self.hex_symbols = '0123456789abcdef'
        self.keygen()

    def keygen(self):
        rng = SystemRandom()
        self.sk = [rng.randbytes(32) for _ in range(48)]
        self.pk = [SM3_n(self.sk[_], 255, self.n) for _ in range(48)]
        return self.sk, self.pk

    def sign(self, msg, sk=None):
        sk = sk if sk else self.sk
        m = SM3(msg)
        m_bin = bin(int(m, 16))[2:].zfill(256)
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)]
        step = [0] * 48;
        qq = [0] * 48
        for i in range(32):
            step[i] = a[i]
            qq[i] = SM3_n(sk[i], step[i])
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]:
                    sum[i] += j
            step[i + 32] = sum[i] % 255
            qq[i + 32] = SM3_n(sk[i + 32], step[i + 32])
        return [i for i in qq]

    def verify(self, msg, qq, pk=None):
        qq = [bytes.fromhex(i) for i in qq]
        pk = pk if pk else self.pk
        m = SM3(msg)
        m_bin = bin(int(m, 16))[2:].zfill(256)
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)]
        step = [0] * 48;
        pk_ = [0] * 48
        for i in range(32):
            step[i] = a[i]
            pk_[i] = SM3_n(qq[i], 255 - step[i])
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]:
                    sum[i] += j
            step[i + 32] = sum[i] % 255
            pk_[i + 32] = SM3_n(qq[i + 32], 255 - step[i + 32])
        return True if pk_ == pk else False


print('initializing...')
Sign = Nepsign()
while 1:
    match int(input('> ')):
        case 1:
            msg = bytes.fromhex(input('msg: '))
            if msg != b'happy for NepCTF 2025':
                print(Sign.sign(msg))
            else:
                print("You can't do that")
        case 2:
            qq = literal_eval(input('give me a qq: '))
            if Sign.verify(b'happy for NepCTF 2025', qq):
                print(flag)

# 解题思路：
# 1、分析目标包括 “happy for NepCTF 2025”，并计算目标的 SM3 哈希值。

​ 将哈希拆分为 32 个字节以确定前 32 个步骤值。对于每个十六进制数字 （0-9a-f），计算其在哈希（基于 1 的索引）中的位置总和，模 255，以确定剩余的 16 个步长值。

# 2、查找每个步骤值的有效消息：

​ 对于 48 个步骤值中的每一个（32 个来自哈希字节，16 个来自十六进制数字总和），找到一条消息，其哈希值满足该步骤的特定条件：

​ 对于前 32 个步骤，消息哈希的第 i 个字节必须与目标的第 i 个字节匹配。对于最后 16 个步骤，消息哈希中特定十六进制数字的位置总和（模 255）必须与目标的相应步长值匹配。

# 3、收集签名部件：

​ 对于找到的每条有效邮件，请向服务器请求签名。提取与当前步骤对应的签名的相关部分。

# 4、伪造签名：

​ 将收集到的签名部分组合成目标消息的完整伪造签名。将此伪造签名提交给服务器以检索标志。

# 解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import ast
from gmssl import sm3
from pwn import *

# 预先计算目标步骤值
msg0 = b'happy for NepCTF 2025'
h0 = sm3.sm3_hash(list(msg0))
print("Target hash:", h0)
h0_int = int(h0, 16)
h0_bin = bin(h0_int)[2:].zfill(256)
a_target = []
for i in range(32):
    chunk = h0_bin[8*i:8*i+8]
    a_target.append(int(chunk, 2))

hex_symbols = '0123456789abcdef'
step_target = []
for i in range(16):
    d = hex_symbols[i]
    s = 0
    for j in range(1, 65):
        if h0[j-1] == d:
            s += j
    step_target.append(s % 255)

step_target_full = a_target + step_target
print("Target step array:", step_target_full)

# 连接服务器
conn = remote('xxxxxxx.nepctf.com', 443, ssl=True)#替换为你的问题服务器
conn.recvuntil(b'> ')

forged_qq = [0] * 48

for i in range(48):
    print(f"Part {i}: Searching for candidate...")
    nonce = 0
    found = False
    candidate = None
    while nonce < 1000000 and not found:
        candidate = b'forgery_' + str(i).encode() + b'_' + str(nonce).encode()
        h = sm3.sm3_hash(list(candidate))
        if i < 32:
            if len(h) < 2*i+2:
                nonce += 1
                continue
            byte_str = h[2*i:2*i+2]
            try:
                byte_val = int(byte_str, 16)
            except:
                nonce += 1
                continue
            if byte_val == step_target_full[i]:
                found = True
            else:
                nonce += 1
        else:
            j = i - 32
            d = hex_symbols[j]
            s = 0
            for pos in range(1, 65):
                if pos-1 < len(h) and h[pos-1] == d:
                    s += pos
            if s % 255 == step_target_full[i]:
                found = True
            else:
                nonce += 1

    if not found:
        print(f"Part {i}: Not found after {nonce} trials")
        conn.close()
        exit(1)

    print(f"Part {i}: Found candidate with nonce {nonce}")
    conn.sendline(b'1')
    conn.recvuntil(b'msg: ')
    conn.sendline(candidate.hex().encode())
    sig_line = conn.recvline().strip()
    try:
        sig_list = ast.literal_eval(sig_line.decode())
    except:
        print("Failed to parse signature:", sig_line)
        conn.close()
        exit(1)

    if len(sig_list) != 48:
        print("Signature list length not 48:", len(sig_list))
        conn.close()
        exit(1)

    forged_qq[i] = sig_list[i]
    print(f"Part {i}: Got signature part: {sig_list[i]}")

# 提交伪造签名
conn.sendline(b'2')
conn.recvuntil(b'give me a qq: ')
qq_str = repr(forged_qq)
conn.sendline(qq_str.encode())
flag_line = conn.recvline()
print(flag_line)
conn.interactive()

# latticebros

# 问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#已知α的极小多项式为三次多项式f(x),即f(α)=0,且α≈54236.606188881754809671280151541781895183337725393
#上述极小多项式的常数项为a0

from secret import a0,alpha
import gmpy2
from Crypto.Util.number import long_to_bytes
import random
from math import sqrt,log2

d=981020902672546902438782010902608140583199504862558032616415
p = d - a0

k=sqrt(log2(p))+log2(log2(p))
B = 2**30
assert B < p/2**k

m = 30
assert m > 2*sqrt(log2(p))

samples = []
betas = []

f = open("samples.txt",'w')
for _ in range(m):
    t = random.randint(1, p-1)
    beta = random.randint(-B + 1, B - 1)
    a = (t * alpha - beta) % p
    samples.append((t, a))
    betas.append(beta)

f.write(str(samples))

for i in range(0,30):
    assert (betas[i]-samples[i][0]*alpha+samples[i][1])%p == 0

#flag = long_to_bytes(alpha)

# 解题思路：

该题目需要用到格密码原理：

通过已知的三次多项式

α3+a2α2+a1α+a0=0α^3+a_2α^2+a_1α+a_0=0

构造格：

(1,a2,a1,a0)(α3C100α2C010αC001C000)=(eC,1,a2,a1)(1,a_2,a_1,a_0)\begin{pmatrix} α^3C&1&0&0\\ α^2C&0&1&0 \\ αC&0&0&1 \\ C&0&0&0 \end{pmatrix}=(eC,1,a_2,a_1)

# 解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from Crypto.Util.number import *

data = [(541847931463604073209188621415697353813245102261880389530448, 293760933113243563398917466885108625646262447370201484418246), (235213326900086489464935804156966465366154623411555613791270, 660823982268225103178763707015491421784294988488272636270997), (826464884761457937459245903152143755707241416981488127320435, 428521663319038461250005113612781686761766888058391496085911), (589542000504317435156560078533519448295689695687499354390208, 155284353896000150766154807679279597476176668344402166959399), (968823371588600973965757332601758200815345862153455338808286, 870008943690791009196027169525956126827736285614393106689402), (621636099728440147413990266662022925118216803638588918660041, 265635912066749696542909843111997941904342442664219734956888), (426696569424050102229606043215592727790577655338668728275370, 279313121876980354011480010042682666651614765507190502627689), (89450479064580125731654556963306718472532905610952012502649, 465933125964565419295325650759566635253450915499965633327941), (480355476500393865742379469913983270769356894135485925662119, 894041172171871806404285309781862268351135623868845025443422), (842436524669577199024236805258573090764419350786291073287889, 345478552143958037534551648319293899442551000874041707820740), (650054674429185550652935714084022116516082323269321462104664, 441999979283903658157822753439653947343822546158589507765994), (46289431385578693366971976442426853079852982529357847290686, 625618376463384339878849844467050454204685252824782609369180), (71444185449163133531919043374545893927347050624346741281881, 955925578289311966288639224625142299309823207245807788495453), (192579726169321656812883068526498248523814846320328766176253, 626481822474054336470183912297952839011392733501646931370367), (736527635648804640774976580747540045854351230084566721853611, 276626211757586963928788091386096607703513204646314683038338), (177922521867185878959621840269164617147915792720210315529733, 541058782621716573816245900423919799500476442285991532228641), (40610451174818168154306630612571678739921107216052349044576, 727642592899858828601137105077611015328512898368636299587376), (385012983728389322601149562441674995471397288632464238356283, 353921151307105661267278594470212933060655245893209524497156), (750447975601038834764379841158092390933760641866111445401426, 391626416964965737035878375834907580903143512300198923948189), (115058604943298010958881205548782439407592353731185670266593, 491630592857258949793489206081490523001249620510479961058022), (327389234395954477946639629629085910688793716425320663599360, 24975272330009592102362429346350824580378490147041708568130), (115595274689129534885608766476695918464309130165432995990883, 757961876891952019297626599379744405302595090402128271144165), (950804723308776351161744501221236453742418549093165078282534, 20307246759635231945223392614290397512873344480184942904518), (724537610412063699714461780160573528810830178440136810747811, 149681928388378582933943374524511804362928290938917573644613), (340891278018589324130004945217960336392205386747747011263373, 683307718413135477104477081812052183267507312278283317237187), (104379682905784169840335131193505192063050242530811180817410, 715010230598797717533306270232399781090458356371977748416491), (644160326926600986730919713173510327120201404569141824224075, 127877985489410167008195578625004740882394608402141169695352), (549253388716005399852261816416312267100135940382820676807345, 210560134643237517255193955173709174155305784935427470113433), (968265711632086435506163736279856957220961064226797549228006, 273174723915971720522674140326199419265943707917542063022561), (704367622558261900937184683100177434487519780290678439135652, 959106497548134540301589019840013331842784496835379005298630)]
alpha = 54236.606188881754809671280151541781895183337725393
d = 981020902672546902438782010902608140583199504862558032616415
alpha = QQ(alpha)
M = matrix(QQ, [
    [alpha**3, 1, 0, 0],
    [alpha**2, 0, 1, 0],
    [alpha**1, 0, 0, 1],
    [alpha**0, 0, 0, 0]
])
M[:, 0] *= getrandbits(32)
L = M.LLL()
v = L[0]
if v[1] == -1:
    v *= -1
a2, a1 = v[2], v[3]
a0 = -(alpha**3 + a2 * alpha**2 + a1 * alpha)
p = d - int(a0)

al = []
tl = []
for t, a in data:
    al.append(a)
    tl.append(t)
M = matrix(ZZ, [al, tl])
M = M.stack(p * identity_matrix(ZZ, M.ncols()))
L = M.LLL()
beta = L[2]
b0, b1 = beta[0], beta[1]
t0, t1 = tl[0], tl[1]
a0, a1 = al[0], al[1]
alpha = (b0 + a0) * pow(t0, -1, p) % p

print(long_to_bytes(int(alpha)))

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*