Misay's blog

CISCN2026

发表于 分类于
本文字数： 9.8k
2026国赛初赛CryptoWP

今年和DAMN的队友看了看题 题量和深度都较去年下降了不少，传统misc也被代替为取证了，给cryptoak掉后就一直在帮pwn手看rw的proxy 可惜最后还是没能拿下 明年继续加油吧

ECDSA

task.py

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
#!/usr/bin/env python3
from ecdsa import SigningKey, NIST521p
from hashlib import sha512
from Crypto.Util.number import long_to_bytes
import random
import binascii
import sys

digest_int = int.from_bytes(sha512(b"Welcome to this challenge!").digest(), "big")
curve_order = NIST521p.order
priv_int = digest_int % curve_order
priv_bytes = long_to_bytes(priv_int, 66)
sk = SigningKey.from_string(priv_bytes, curve=NIST521p)
vk = sk.verifying_key

f_pub = open("public.pem", "wb")
f_pub.write(vk.to_pem())
f_pub.close()


# k完全和i确定 
def nonce(i):
    seed = sha512(b"bias" + bytes([i])).digest()
    k = int.from_bytes(seed, "big")
    return k

msgs = [b"message-" + bytes([i]) for i in range(60)]
sigs = []

for i, msg in enumerate(msgs):
    k = nonce(i)
    sig = sk.sign(msg, k=k)
    sigs.append((binascii.hexlify(msg).decode(), binascii.hexlify(sig).decode()))

f_sig = open("signatures.txt", "w")
for m, s in sigs:
    f_sig.write("%s:%s\n" % (m, s))
f_sig.close()

要求计算出私钥后转md5得到flag

我们来复习下ECDSA的签名思路

这里关键在于nonce函数中的生成完全是白盒,我们得到后，计算就能得到 随后结合已有的解密 可以得到 exp

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
from hashlib import sha512 , md5, sha1
from ecdsa import SigningKey, VerifyingKey, NIST521p
from Crypto.Util.number import long_to_bytes
import binascii

# 解析16进制的签名 拆分为前后
def parse(sig_hex):
    sig = binascii.unhexlify(sig_hex)
    r = int.from_bytes(sig[:66], "big")
    s = int.from_bytes(sig[66:], "big")
    return r, s

# 计算nonce 转化为数字
def nonce(i):
    seed = sha512(b"bias" + bytes([i])).digest()
    return int.from_bytes(seed, "big")


# 从已知信息对私钥进行恢复
def recover(sig_line, idx,  curve_order):

    # 解析数据
    msg_hex, sig_hex = sig_line.strip().split(":")
    msg = binascii.unhexlify(msg_hex)
    r, s = parse(sig_hex)

    # 计算ECDSA参数
    z = int.from_bytes(sha1(msg).digest(), "big") % curve_order
    k = nonce(idx) % curve_order
    r_inv = pow(r, -1, curve_order)
    d = (s * k - z) * r_inv % curve_order
    return d

curve = NIST521p
n = curve.order
with open("signatures.txt", "r") as f:
    lines = [line.strip() for line in f if line.strip()]

d = recover(lines[1], 1, n)

# 验证私钥正确性

sk = SigningKey.from_string(long_to_bytes(d, 66), curve=curve)
vk0 = sk.verifying_key
with open("public.pem", "rb") as f:
    vk = VerifyingKey.from_pem(f.read())

if vk.to_string() == vk0.to_string():
    # 谜语人题目没说怎么转化的 多试一下就行
    print("flag{" + md5(str(d).encode()).hexdigest() + "}")

# flag{581bdf717b780c3cd8282e5a4d50f3a0}

后面注意验证下即可

ezflag

逆向题，，

elf ida打开一目了然

输入正确的pwd 程序输出flag 但是实测发现下来输出flag{10632674-1d21后就巨慢 这很反常 我们看看f函数

它涉及一个对i1的循环 i1就是v11 但是我们外面循环也对v11有一个v1 * 8 + i + 64 明显是这里拖慢了

注意到我们计算的其实是fibonacci mod 16的值,经过查询可以得到这段数列的周期是24，那么返回值其实是就很好预测的 我们完全没有必要每次都去穷举这么大一个i

f函数源逻辑

1
2
3
4
5
6
7
8
9
def f(v11) {
	v5 = 0
	v4 = 1
	for i in range(v11) :
		v2 = v4
		v4 = (v5+v4) % 16
		v5 = v2
	return v5
}

可以转化为等价的逻辑

1
2
3
4
5
6
7
8
9
def f(v11) {
	v5 = 0
	v4 = 1
	for i in range(v11%24):
		v2 = v4
		v4 = (v5+v4) % 16
		v5 = v2
	return v5
}

理论上是可以在这段f函数中修改汇编 直接把循环上界改成i%24 实现瞬间输出flag的 不过作为二进制苦手还是选用古法re了）

我们来看flag是怎么被计算输出的

v11完全已知 这里的函数我们也完全已知 那么v9就是已知的 我们直接打印v9 故而往f里面看返回值

v5是计算的int 没有问题 那么K是什么呢 查看交叉引用 找到了在程序初始化的定义

所以逻辑非常清楚 对于变量v11循环自增 随后调用f计算fibonacci计算v5 查表得到flag 我们静态写一个exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
charset = "012ab9c3478d56ef"
mod = 16
mask64 = (1<<64) - 1

def fib(n):
    if n == 0:
        return 0, 1
    a, b = fib(n>>1)
    c = (a*((b*2 - a)%mod)) %mod
    d = (a*a+b*b)%mod
    if n&1:
        return d, (c+d)%mod
    return c, d

state = 1
out = []
for i in range(32):
    fn = fib(state)[0]
    out.append(charset[fn])
    if i in (7, 12, 17, 22):
        out.append("-")
    state = (state*8 + 64 + i)&mask64 # c中64位int溢出处理
print("flag{" + "".join(out) + "}")
# flag{10632674-1d219-09f29-14769-f60219a24}

和输出结果符合

RAS-Nesting-Doll

src.py

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
from Crypto.Util.number import *
from tqdm import tqdm
import os

flag=open("./flag.txt","rb").read()
flag=bytes_to_long(flag+os.urandom(2048//8-len(flag)))
e=65537

def get_smooth_prime(bits, smoothness, max_prime=None):
    assert bits - 2 * smoothness > 0
    p = 2
    if max_prime!=None:
        assert max_prime>smoothness
        p*=max_prime
        
    while p.bit_length() < bits - 2 * smoothness:
        factor = getPrime(smoothness)
        p *= factor

    bitcnt = (bits - p.bit_length()) // 2
    while True:
        prime1 = getPrime(bitcnt)
        prime2 = getPrime(bitcnt)
        tmpp = p * prime1 * prime2
        if tmpp.bit_length() < bits:
            bitcnt += 1
            continue
        if tmpp.bit_length() > bits:
            bitcnt -= 1
            continue
        if isPrime(tmpp + 1):
            p = tmpp + 1
            break
    return p

p1=getPrime(512)
q1=getPrime(512)
r1=getPrime(512)
s1=getPrime(512)
n1=p1*q1*r1*s1
assert n1>flag

p=get_smooth_prime(1024,20,p1)
q=get_smooth_prime(1024,20,q1)
r=get_smooth_prime(1024,20,r1)
s=get_smooth_prime(1024,20,s1)
n=p*q*r*s

print(f"[+] inner RSA modulus = {n1}")
print(f"[+] outer RSA modulus = {n}")
print(f"[+] Ciphertext = {pow(flag,e,n1)}")

第一个正经的密码题，，

一个基于平滑数的RSA系统 我们主要看get_smooth_prime函数

有 

1
assert p.is_prime() and p.bit_length() == 1024

这里的个数可以大致估算为几十个 让的比特从513到985＋

我们有 利用平滑数的思路 我们可以轻松的找到的倍数

设集合包含的所有素数令 有 所以说

从而我们可以得到

进而得到 也就是说我们拿到了一个的倍数 接下来我们来分解

参考Miller-Rabin方法

我们的期望是找到一个数满足 而且 那么就可以有

通过与可以找到一个解

而为什么需要的倍数呢 我们由欧拉定理不难得到 有了倍数 那么 令 在模下 我们分析如下平方链 为什么要用这根平方链？因为我们知道终点一定是

在中途一定有平方到1的情况 那么我们只要关注 是否前一个项不为？如果是 我们就找到了一个自己需要的解 否则我们换一根链子就行 因为平方到1后面肯定就不变化了

我们分解后再看 就可以用光滑数的方法直接给搓下来 然后转到 解密rsa exp

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
from Crypto.Util.number import *
import random
n1 = 16141229822582999941795528434053604024130834376743380417543848154510567941426284503974843508505293632858944676904777719167211264225017879544879766461905421764911145115313698529148118556481569662427943129906246669392285465962009760415398277861235401144473728421924300182818519451863668543279964773812681294700932779276119980976088388578080667457572761731749115242478798767995746571783659904107470270861418250270529189065684265364754871076595202944616294213418165898411332609375456093386942710433731450591144173543437880652898520275020008888364820928962186107055633582315448537508963579549702813766809204496344017389879
n  = 484831124108275939341366810506193994531550055695853253298115538101629337644848848341479419438032232339003236906071864005366050185096955712484824249228197577223248353640366078747360090084446361275032026781246854700074896711976487694783856878403247312312487197243272330518861346981470353394149785086635163868023866817552387681890963052199983782800993485245670437818180617561464964987316161927118605512017355921555464359512280368738197370963036482455976503266489446554327046948670215814974461717020804892983665655107351050779151227099827044949961517305345415735355361979690945791766389892262659146088374064423340675969505766640604405056526597458482705651442368165084488267428304515239897907407899916127394598273176618290300112450670040922567688605072749116061905175316975711341960774150260004939250949738836358264952590189482518415728072191137713935386026127881564386427069721229262845412925923228235712893710368875996153516581760868562584742909664286792076869106489090142359608727406720798822550560161176676501888507397207863998129261472631954482761264406483807145805232317147769145985955267206369675711834485845321043623959730914679051434102698588945009836642922614296598336035078421463808774940679339890140690147375340294139027290793
e  = 65537
c  = 657984921229942454933933403447729006306657607710326864301226455143743298424203173231485254106370042482797921667656700155904329772383820736458855765136793243316671212869426397954684784861721375098512569633961083815312918123032774700110069081262242921985864796328969423527821139281310369981972743866271594590344539579191695406770264993187783060116166611986577690957583312376226071223036478908520539670631359415937784254986105845218988574365136837803183282535335170744088822352494742132919629693849729766426397683869482842748401000853783134170305075124230522253670782186531697976487673160305610021244587265868919495629

# 求0 ~ 1<<20所有素数
def sieve_prime(limit):
    limit = int(limit) 
    sieve = bytearray(b"\x01") * (limit + 1)
    sieve[0:2] = b"\x00\x00"
    for i in range(2, int(limit**0.5) + 1):
        if sieve[i]:
            step = i
            start = i * i
            sieve[start:limit + 1:step] = b"\x00" * (((limit - start) // step) + 1)
    return [p for p in range(2, limit + 1) if sieve[p]]

    
# 求phi的倍数
def find_phi(mod, k_odd, two_pow):
    for _ in range(80):
        a = random.randrange(2, mod - 1)
        g = GCD(a, mod)
        if 1 < g < mod:
            return g
        x = pow(a, k_odd, mod)
        if x == 1 or x == mod - 1:
            continue
        for _ in range(two_pow):
            y = pow(x, 2, mod)
            if y == 1:
                g = GCD(x-1, mod)
                if 1 < g < mod:
                    return g
                break
            if y == mod - 1:
                break
            x = y
    return None


# 分解n
def factor_n(mod, n1, bits):
    limit = 1 << bits
    primes = sieve_prime(limit)
    l_odd = 1
    for p in primes:
        if p != 2:
            l_odd *= p

    k_odd = n1 * l_odd
    two_pow = 4
    factors = []
    stack =  [mod]
    while stack:
        m = stack.pop()
        if m == 1:
            continue
        for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
            if m % p == 0:
                factors.append(p)
                stack.append(m//p)
                break
        else:
            if isPrime(m):
                factors.append(m)
                continue
            f = find_phi(m, k_odd, two_pow)
            if f is None:
                break
            stack.append(f)
            stack.append(m//f)
    return sorted(factors)                      

outer = factor_n(n, n1, 20)

inner = [GCD(p-1, n1) for p in outer]

phi = 1
for p in inner:
    phi *= p-1

d = pow(e, -1, phi)
print(long_to_bytes(pow(c,d,n1)))
# flag{fak3_r5a_0f_euler_ph1_of_RSA_040a2d35}