2024年春秋杯夏季赛Crypto部分题目复现

发表于 更新于 分类于 阅读次数： Disqus：

触不可及。正因为触不可及，天空才是湎于幻想之人的归宿。

1.ezzzecc

题目附件：

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
p = getPrime(256)
a = getPrime(256)
b = getPrime(256)
E = EllipticCurve(GF(p),[a,b])
m = E.random_point()
G = E.random_point()
k = getPrime(18)
K = k * G
r = getPrime(256)
c1 = m + r * K

c2 = r * G

cipher_left = s2n(flag[:len(flag)//2]) * m[0]   #flag的前半部分乘m[0]，所以只要用密文的除于m[0]即可得到flag前半部分
cipher_right = s2n(flag[len(flag)//2:]) * m[1]   #flag的后半部分点乘m[1]


p = koZP3YQAklARRNrmYfjxoKIAXegOcG4jMOmKb08uESOkCCn72d6UM2NWgefYPEMq4EJ1M0jKaqt02Guo5Ubccjqg4QZaaHbScREx38UMLQKwG0LcDd8VFX1zkobc1ZQn4L3DhKQrgJZI55todgOdJuHN532bxScAvOF26gJyQclPtRHn3M6SHrRCEXzzmszd68PJlLB6HaabrRrCW9ZoAYSZetM5jDBtNCJLpR0CBZUUk3Oeh2MZQu2vk8DZ1QqNG49hlxGfawp1FXvAZPdMwixzkhEQnbCDcOKzYyT6BZF2Dfd940tazl7HNOswuIpLsqXQ2h56guGngMeYfMXEZV09fsB3TE0N934CLF8TbZnzFzEkOe8TPTK2mWPVSrgmbsGHnxgYWhaRQWg3yosgDfrEa5qfVl9De41PVtTw024gltovypMXK5XMhuhogs0EMN7hkLapLn6lMj
p的格式为p={p}

a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939 : 43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565 : 74331715224220154299708533566163247663094029276428146274456519014761122295496)
私钥k小于1000000
c1 = (3315847183153421424358678117707706758962521458183324187760613108746362414091 : 61422809633368910312843316855658127170184420570309973276760547643460231548014)
c2 = (12838481482175070256758359669437500951915904121998959094172291545942862161864 : 60841550842604234546787351747017749679783606696419878692095419214989669624971)
cipher_left = 75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right = 61560856815190247060747741878070276409743228362585436028144398174723191051815

当时看到这道题的时候，这不就是个ecc的板子题嘛！只要再多搞个k爆破就可以出来了

但是我还是有点低估了这道题

p = koZP3YQAklARRNrmYfjxoKIAXegOcG4jMOmKb08uESOkCCn72d6UM2NWgefYPEMq4EJ1M0jKaqt02Guo5Ubccjqg4QZaaHbScREx38UMLQKwG0LcDd8VFX1zkobc1ZQn4L3DhKQrgJZI55todgOdJuHN532bxScAvOF26gJyQclPtRHn3M6SHrRCEXzzmszd68PJlLB6HaabrRrCW9ZoAYSZetM5jDBtNCJLpR0CBZUUk3Oeh2MZQu2vk8DZ1QqNG49hlxGfawp1FXvAZPdMwixzkhEQnbCDcOKzYyT6BZF2Dfd940tazl7HNOswuIpLsqXQ2h56guGngMeYfMXEZV09fsB3TE0N934CLF8TbZnzFzEkOe8TPTK2mWPVSrgmbsGHnxgYWhaRQWg3yosgDfrEa5qfVl9De41PVtTw024gltovypMXK5XMhuhogs0EMN7hkLapLn6lMj

额，这p是什么东西？

尝试了很多种编码方式，就是解不出p，“p的格式为p={p}”也没看明白是什么意思

后面朋友把学长的脚本分享给了我，我发现我遗漏了一个很重要的点，就是椭圆曲线的方程：
$$
y^2=x^3+ax+b mod p
$$
因为K和G都在曲线上，所以我们可以把K和G两个点代入到椭圆方程当中求kp
$$
k1p=x_K^3+ax+b-y_K^2
$$
$$
k2p=x_G^3+ax+b-y_G^2
$$
然后在gcd(k1p,k2p)，最后就可以把p给求出来

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import*
from gmpy2 import*
a=87425770561190618633288232353256495656281438408946725202136726983601884085917
b=107879772066707091306779801409109036008421651378615140327877558014536331974777
K = (49293150360761418309411209621405185437426003792008480206387047056777011104939 , 43598371886286324285673726736628847559547403221353820773139325027318579443479)
G = (34031022567935512558184471533035716554557378321289293120392294258731566673565 , 74331715224220154299708533566163247663094029276428146274456519014761122295496)
k1p=K[0]**3+a*K[0]+b-K[1]**2
k2p=G[0]**3+a*G[0]+b-G[1]**2
p=gcd(k1p,k2p)
E = EllipticCurve(GF(p),[a,b])
c1=E([3315847183153421424358678117707706758962521458183324187760613108746362414091,61422809633368910312843316855658127170184420570309973276760547643460231548014])
c2=E([12838481482175070256758359669437500951915904121998959094172291545942862161864,60841550842604234546787351747017749679783606696419878692095419214989669624971])
cipher_left=75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right=61560856815190247060747741878070276409743228362585436028144398174723191051815
for k in range(1000000):
    m=c1-k*c2
    left=cipher_left//m[0]
    right=cipher_right//m[1]
    M=long_to_bytes(int(left))+long_to_bytes(int(right))
    if b'flag'in M:
        print(M)
        break
b'flag{2d6a7e4e-02d3-11ef-8836-a4b1c1c5a2d2}'

跑了挺长时间的，用虚拟机好像跑的快一点

2.signatrue

这道题因为是一道靶机题，就先分析一下解题思路，以后有环境了再复现一下：

附件：

server.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
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
import os
import hashlib
from Crypto.Util.number import *
from Crypto.PublicKey import DSA
import random
def gen_proof_key():
    password = 'happy_the_year_of_loong'
    getin = ''
    for i in password:
        if random.randint(0, 1):
            getin += i.lower()
        else:
            getin += i.upper()
    ans = hashlib.sha256(getin.encode()).hexdigest()
    return getin,ans

def gen_key():
    pri = random.randint(2,q - 2)
    pub = pow(g,pri,p)
    return pri,pub

def sign(m,pri):
    k = int(hashlib.md5(os.urandom(20)).hexdigest(),16)
    H = int(hashlib.sha256(m).hexdigest(),16)
    r = pow(g,k,p) % q
    s = pow(k,-1,q) * (H + pri * r) % q
    return r,s

def verify(pub,m,signature):
    r,s = signature
    if r <= 0 or r >= q or s <= 0 or s >= q:
        return False
    w = pow(s,-1,q)
    H = int(hashlib.sha256(m).hexdigest(),16)
    u1 = H * w % q
    u2 = r * w % q
    v = (pow(g,u1,p) * pow(pub,u2,p) % p) % q
    return v == r
    
def login():
    print('Hello sir,Plz login first')
    menu = '''
    1.sign
    2.verify
    3.get my key
    '''
    times = 8
    while True:
        print(menu)
        if times < 0:
            print('Timeout!')
            return False
        choice = int(input('>'))
        if choice == 1:
            name = input('Username:').encode()
            if b'admin' in name:
                print('Get out!')
                return False
            r,s = sign(name,pri)
            print(f'This is your signature -- > {r},{s}')
            times -= 1
        elif choice == 2:
            print('Sure,Plz input your signature')
            print(pri)
            r = int(input('r:'))
            s = int(input('s:'))
            if verify(pub,b'admin',(r,s)) == True:
                print('login success!')
                return True
            else:
                print('you are not admin')
                return False
        elif choice == 3:
            print(f'Oh,your key is {(p,q,g)}')
getin,ans = gen_proof_key()
print(f'Your gift --> {ans[:6]}')
your_token = input('Plz input your token\n>')
if your_token != getin:
    print('Get out!')
    exit(0)

key = DSA.generate(1024)
p, q, g = key.p, key.q, key.g
pri, pub = gen_key()
if login() == False:
    exit(0)
print(open('/flag','r').read())

这道题是DSA+HNP的结合题，XCTF2020-高校战役-NHP和这道题较为类似，因为这道题也是靶机题，有环境再复现

我们粗略看一下这些代码块：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def gen_key():
    pri = random.randint(2,q - 2)
    pub = pow(g,pri,p)
    return pri,pub

def sign(m,pri):
    k = int(hashlib.md5(os.urandom(20)).hexdigest(),16)
    H = int(hashlib.sha256(m).hexdigest(),16)
    r = pow(g,k,p) % q
    s = pow(k,-1,q) * (H + pri * r) % q
    return r,s

def verify(pub,m,signature):
    r,s = signature
    if r <= 0 or r >= q or s <= 0 or s >= q:
        return False
    w = pow(s,-1,q)
    H = int(hashlib.sha256(m).hexdigest(),16)
    u1 = H * w % q
    u2 = r * w % q
    v = (pow(g,u1,p) * pow(pub,u2,p) % p) % q
    return v == r

我们能够看得出，这里考察的是隐藏数问题（HNP / Hidden Number Problem），用admin来检验签名

多次签名造格

（春秋杯是真的喜欢考DSA的知识啊，今年冬季赛也考了DSA）

我们有：
$$
s=k^{-1}(H+xr)mod q
$$
$$
其中x为pri
$$
$$
求k
$$
$$
k=s^{-1}(H+xr)mod q
$$
$$
式子展开 k=Hs^{-1}+s^{-1}xr mod q
$$
$$
我们可以把s^{-1}r记作A，Hs^{-1}记作B
$$
$$
所以有： k=A_ix+B_i mod q
$$
$$
然后就可以构造格
$$
然后我们在login函数里发现times=8，所以我们造格时i最大也为8

所以有：
$$
vM = \begin{bmatrix} l_1 & l_2 & \cdots & l_8 & x & 1 \end{bmatrix} \begin{bmatrix} q & & & & & & \newline & q & & & & & \newline & &\ddots& & & & \newline & & & q & & & \newline A_1&A_2&\dots & A_8&1& & \newline B_1&B_2&\dots & B_8& & K & \newline \end{bmatrix} = \begin{bmatrix} k_1 & k_2 & \cdots & k_8 & x& K \end{bmatrix} = v_k
$$
把x,k求出来

然后我们来估算一下：

1
k = int(hashlib.md5(os.urandom(20)).hexdigest(),16)

通过这里的代码，我们可以估计k(K)的长度大概在32*4=128bits左右

DSA通常使用 1024 比特的 p 和 160 比特的 q,所以q应该就是160比特长

1
pri = random.randint(2,q - 2)

x在（2，q-2）的范围内，所以x的长度和q应该也差不多，为160bits左右

然后估算造的这个格x的大小，大概在140.8bit左右，所以很明显小了，因为x至少都有160bits左右，所以这个格要重新造

HNP造格的一些其它思路：

https://zhuanlan.zhihu.com/p/581146119

我们发现k小x大，所以我们可以先消去x：

（步骤简化了一些，详细步骤上面的博客里有）
$$
(r_0s_i)k_i-(r_is_0)k_0=(r_0h_i-r_ih_0)mod q
$$
$$
使ki的系数为1，然后乘上一个(r_0s_i)^{-1},就有：
$$
$$
k_i-((r_is_0)(r_0s_i)^{-1})k_0=((r_0h_i-r_ih_0)(r_0s_i)^{-1})mod q
$$
$$
现在令：
$$
$$
A_i=((r_is_0)(r_0s_i)^{-1})\ B_i=((r_0h_i-r_ih_0)(r_0s_i)^{-1})\
$$
$$
所以有：
$$
$$
k_i=A_ik_0+B_i(mod q)
$$
$$
构造格：
$$
$$
vM = \begin{bmatrix} l_1 & l_2 & \cdots & l_8 & k_0& 1 \end{bmatrix} \begin{bmatrix} q & & & & & & \newline & q & & & & & \newline & &\ddots& & & & \newline & & & q & & & \newline A_1&A_2&\dots & A_8&1& & \newline B_1&B_2&\dots & B_8& & K & \newline \end{bmatrix} = \begin{bmatrix} k_1 & k_2 & \cdots & k_8 & k_0& K \end{bmatrix} = v_k
$$
求出k0之后，然后就可以解r和s

学完这道题，收获还是很大的

HNP也经常和LCG一起考察，到时候一并更新

*NPUCTF 2020 - babyLCG

*RCTF 2022 - IS_THIS_LCG

第一次尝试在自己的博客上记录自己的学习心得，还有很多不足之处，希望各位师傅批评指正！