CISCN2026 • Misay's blog

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

ECDSA#

task.py

#!/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()

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

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

r\equiv x \mod n

s\equiv k^{-1}(h+r\times d)\mod n

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

d\equiv r^{-1}(sk-h)\mod n

exp

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函数源逻辑

def f(v11) {
	v5 = 0
	v4 = 1
	for i in range(v11) :
		v2 = v4
		v4 = (v5+v4) % 16
		v5 = v2
	return v5
}

可以转化为等价的逻辑

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

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

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函数

有

p=2\times p_1\times sp_1\times\cdots\times sp_n \times bp_1\times bp_2 + 1

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

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

我们有

p-1=s_1\times p_1

利用平滑数的思路我们可以轻松的找到 $2\times p_1\times sp_1\times\cdots\times sp_n \times bp_1\times bp_2$ 的倍数

设集合 $P$ 包含 $(1\sim2^{20})$ 的所有素数令

k = \prod p_i\;\;p_i\in P

有

s_1|k

所以说 $p-1 | k\times p_1$

从而我们可以得到 $k\times \phi(p)$

进而得到

\phi(n) | k^4n_1

也就是说我们拿到了一个 $\phi(n)$ 的倍数 $k\phi$ 接下来我们来分解 $n$

参考Miller-Rabin方法

我们的期望是找到一个数 $x$ 满足

x^2\equiv 1\mod n

而且

x^2\not\equiv1\;\;,\;\;-1\mod n

那么就可以有 $x^2-1\equiv0\mod n$

通过 $gcd(n,x-1)$ 与 $gcd(x,n+1)$ 可以找到一个解

而为什么需要 $\phi$ 的倍数呢我们由欧拉定理不难得到

x^{\phi}\equiv1\mod n

有了倍数那么

x^{k\phi}\equiv1 \mod n

令

K=k\phi=2^t\times m

在模 $n$ 下我们分析如下平方链

a^m\rightarrow a^{2m}\rightarrow a^{4m}\rightarrow\cdots\rightarrow a^{2^t\times m}

为什么要用这根平方链？因为我们知道终点一定是 $a^{K}\equiv 1\mod n$

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

我们分解 $n$ 后再看

p=s\times p_1 + 1

就可以用光滑数的方法直接给 $p_1$ 搓下来然后转到 $n_1$ 解密rsa exp

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}

plaintext