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

发表于 2024-07-13 更新于 2024-07-16 分类于 -CTF学习阅读次数： 191 Disqus： 2 Comments

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

1.ezzzecc

题目附件：

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} + a x + b m o d p$
因为K和G都在曲线上，所以我们可以把K和G两个点代入到椭圆方程当中求kp
$k 1 p = x_{K}^{3} + a x + b - y_{K}^{2}$
$k 2 p = x_{G}^{3} + a x + b - y_{G}^{2}$
然后在gcd(k1p,k2p)，最后就可以把p给求出来

exp:

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

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和这道题较为类似，因为这道题也是靶机题，有环境再复现

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

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 + x r) m o d q$
$其中 x 为 p r i$
$求 k$
$k = s^{- 1} (H + x r) m o d q$
$式子展开 k = H s^{- 1} + s^{- 1} x r m o d q$
$我们可以把 s^{- 1} r 记作 A ， H s^{- 1} 记作 B$
$所以有： k = A_{i} x + B_{i} m o d q$
$然后就可以构造格$
然后我们在login函数里发现times=8，所以我们造格时i最大也为8

所以有：
$v M = [\begin{matrix} l_{1} & l_{2} & \dots & l_{8} & x & 1 \end{matrix}] [\begin{matrix} q \\ q \\ ⋱ \\ q \\ A_{1} & A_{2} & \dots & A_{8} & 1 \\ B_{1} & B_{2} & \dots & B_{8} & K \end{matrix}] = [\begin{matrix} k_{1} & k_{2} & \dots & k_{8} & x & K \end{matrix}] = 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_{0} s_{i}) k_{i} - (r_{i} s_{0}) k_{0} = (r_{0} h_{i} - r_{i} h_{0}) m o d q$
$使 k i 的系数为 1 ，然后乘上一个 (r_{0} s_{i})^{- 1}, 就有：$
$k_{i} - ((r_{i} s_{0}) (r_{0} s_{i})^{- 1}) k_{0} = ((r_{0} h_{i} - r_{i} h_{0}) (r_{0} s_{i})^{- 1}) m o d q$
$现在令：$
$A_{i} = ((r_{i} s_{0}) (r_{0} s_{i})^{- 1}) B_{i} = ((r_{0} h_{i} - r_{i} h_{0}) (r_{0} s_{i})^{- 1})$
$所以有：$
$k_{i} = A_{i} k_{0} + B_{i} (m o d q)$
$构造格：$
$v M = [\begin{matrix} l_{1} & l_{2} & \dots & l_{8} & k_{0} & 1 \end{matrix}] [\begin{matrix} q \\ q \\ ⋱ \\ q \\ A_{1} & A_{2} & \dots & A_{8} & 1 \\ B_{1} & B_{2} & \dots & B_{8} & K \end{matrix}] = [\begin{matrix} k_{1} & k_{2} & \dots & k_{8} & k_{0} & K \end{matrix}] = v_{k}$
求出k0之后，然后就可以解r和s

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

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

*NPUCTF 2020 - babyLCG

*RCTF 2022 - IS_THIS_LCG

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