初闻不识曲中意，再听已是曲中人。

理论：

密钥生成

选取一个合适的哈希函数记为 $H$ 函数，例如SHA1。
选择合适的密钥长度记$(L,N)$，其中DSS建议 $64|L$ ，且 $512≤L≤1024$，$N$ 不能大于 $H$ 函数输出的长度。
选取$N$ 比特的素数 $q$ 和 $L$ 比特的素数 $p$，并且满足 $q|(p-1)$ 。
选择满足模 $p$ 意义下阶为 $q$ 的整数 $g$ ，这里可以通过关系式
$g \equiv h^{(p-1)/q} \ mod \ p$

得出，其中 $1<h<p−1$ 。

选择整数 $x∈(0,q)$，记为私钥，并且计算 $y \equiv g^x \ mod \ p$。

最终公钥为 $(p,q,g,y)$，私钥为 $x$。

签名

选择临时密钥 $k$ ，满足 $0<k<q$。
计算 $r \equiv (g^k \ mod \ p)(mod \ q)$
计算 $s \equiv (H(m)+xr)k^{−1}(mod \ q)$

最终签名为 $(r,s)$

验签

1.设 $w \equiv s^{-1} \ mod \ q$ ，$u_1 \equiv H(m)w \ mod \ q$，$u_2 \equiv rw \ mod \ q$

2.设 $v \equiv g^{u_1}y^{u_2} \ mod \ p \ (mod \ q)$

3.若 $v=r$，则签名有效，否则则为非法签名。

代码

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

题目

2024i春秋夏季赛

signature

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())

题解

HNP

$s\equiv k^{-1}(H+xr) \bmod q $ ，变形为：

$k\equiv s^{-1}H+s^{-1}xr \bmod q$

令 $A = s^{-1}r \bmod q,B=s^{-1}H$

1 2	a = inverse((S[i]), q) * (R[i]) % q b = inverse((S[i]), q) * (H[i]) % q

即 $k_i\equiv A_ix+B_i \bmod q=>k_i=A_ix+B_i+l_iq $

构建lattice：

$[l_0~~l_1~~\dots ~~l_7~~x~~1]\begin{bmatrix} q& 0& \dots & 0 & 0 & 0\\ 0& q& \dots & 0 & 0 & 0\\ \vdots& \vdots& \ddots& \vdots& \vdots& \vdots\\ 0& 0& \dots& q & 0 & 0\\ A_0& A_1& \dots& A_7 & 1 & 0\\ B_0& B_1& \dots & B_7 & 0 & K \end{bmatrix}=[k_0~~k_1~~\dots~~k_7~~x~~K]$

但是 x 是160bit的，k是128bit的，K是k的上界，所以K取 $2^{128}$ ，也是128bit的，就不能直接算出 x

同时q也是160bit的，10行10列矩阵，所以n 是 10

数的大小

$\left \| \overrightarrow{v} \right \| \le \sqrt{n}\det(L)^{\frac{1}{n}} ,\det(L)=q^8*1*K$

计算出的bit大小是：

$(160*8+128)/10=140.8 ~~bit$

所以我们需要处理一下，把 x 消掉来求解

Dexterjie 师傅的做法如下：（膜拜）

$s_ik_i\equiv H_i+xr_i \bmod q=>s_ik_ir_0\equiv H_ir_0+xr_ir_0 \bmod q$

$s_0k_0\equiv H_0+xr_0 \bmod q=>s_0k_0r_i\equiv H_0r_i+xr_ir_0 \bmod q $

两式相减就消去 x 了

再转换成HNP的形式

$k_i=(r_0s_i)^{-1}(H_ir_0-H_0r_i)+(r_0s_i)^{-1}(r_is_0)k_0 \bmod q$

令 $A_i =(r_0s_i)^{-1}(r_is_0)，B_i= (r_0s_i)^{-1}(H_ir_0-H_0r_i)$

再构造如上同样的格

$[l_0~~l_1~~\dots ~~l_7~~k_0~~1]\begin{bmatrix} q& 0& \dots & 0 & 0 & 0\\ 0& q& \dots & 0 & 0 & 0\\ \vdots& \vdots& \ddots& \vdots& \vdots& \vdots\\ 0& 0& \dots& q & 0 & 0\\ A_0& A_1& \dots& A_7 & 1 & 0\\ B_0& B_1& \dots & B_7 & 0 & K \end{bmatrix}=[k_0~~k_1~~\dots~~k_7~~k_0~~K]$

exp：

想改一下的，但改无可改，proof过的比我的顺滑，数据接收处理的比我的好，再次膜拜Dexter佬

import itertools
from tqdm import *
from pwn import *
from Crypto.Util.number import *

def pass_proof(head):
    password = 'happytheyearofloong'
    table = itertools.product([0, 1], repeat=19)
    for i in tqdm(table):
        getin = ""
        for j in range(len(i)):
            if i[j] == 0:
                getin += password[j].lower()
            else:
                getin += password[j].upper()
        msg = getin[:5] + "_" + getin[5:8] + "_" + getin[8:12] + "_" + getin[12:14] + "_" + getin[14:]
        h = hashlib.sha256(msg.encode()).hexdigest()
        if h[:6] == head:
            print(msg)
            return msg

context.log_level = 'debug'
sh = remote("27.25.151.50", int(9999))
head = sh.recvline().strip().decode().split(" ")[-1]
msg = pass_proof(head)
sh.recvuntil(b"Plz input your token")
sh.sendlineafter(b">", msg.encode())
sh.recvuntil(b"3.get my key\n")
sh.sendlineafter(b">", b"3")
(p, q, g) = eval(sh.recvline().strip().decode().split("Oh,your key is ")[-1])

H = []
R = []
S = []

for i in range(8):
    name = b"a" * (i + 1)
    sh.recvuntil(b"3.get my key\n")
    sh.sendlineafter(b">", b"1")
    sh.sendlineafter(b"Username:", name)
    data = sh.recvline().strip().decode()
    print(data)
    r = int(data.split(" ")[-1].split(',')[0])
    s = int(data.split(" ")[-1].split(',')[1])
    h = int(hashlib.sha256(name).hexdigest(), 16)
    R.append(r)
    S.append(s)
    H.append(h)


def get_k():
    n = len(R)
    r0 = R[0]
    h0 = H[0]
    s0 = S[0]
    A = []
    B = []

    for i in range(n):
        a = inverse((r0 * S[i]), q) * (R[i] * s0) % q
        b = inverse((r0 * S[i]), q) * (H[i] * r0 - h0 * R[i])
        A.append(a)
        B.append(b)

    Ge = Matrix(ZZ, n + 2, n + 2)
    for i in range(n):
        Ge[i, i] = q
        Ge[-2, i] = A[i]
        Ge[-1, i] = B[i]
    K = 2 ** 128
    Ge[-2, -2] = 1
    Ge[-1, -1] = K

    for line in Ge.LLL():
        if abs(line[-1]) == K:
            print(line)
            return line[-2]

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

k0 = get_k()
sh.recvuntil(b"3.get my key\n")
sh.sendlineafter(b">", b"2")
sh.recvline()
x = int(sh.recvline().strip().decode())

r, s = sign(b'admin', k0, x)

sh.sendlineafter(b"r:", str(r).encode())
sh.sendlineafter(b"s:", str(s).encode())
sh.interactive()

非预期：

我们需要的是含 admin 的 r，s

k 非必求项，题目直接给了 pri

exp：

import hashlib
import os
import random
from tqdm import *

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 solve_token(gift):
    for i in trange(2**21):
        getin,ans = gen_proof_key()
        anss = hashlib.sha256(getin.encode()).hexdigest()
        if anss[:6]==gift:
            print(getin)
            return getin
            break

# solve_token('604193')

p,q,g = (174662622154158042971439982212645053687190696768104775225196868992055548704642342585163415973699422033290443580951357526191653161749722322451110110268184889380915621382635156065871162267003276761161722633765289736136153198156831242721193650259121770648937505294914913701513461232854894448353391015513916766209, 1001603163301580546725538891279059276434399384247, 65517437300009715735633486850159617721548442636115700615863608530591756077096959306295830462609328157311116901616191868098474362388535531484218575841378509656901762529213776351766920344254289468341484076432764116887320535684191024038293728392038508496466213863242290672124853717731912458365180056919340701259)

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

pri = 985857368299046143947813211772527824444297963606
r,s = sign(b'admin',pri)
print(r)
print(s)

body、babysign

2024 数字中国积分争夺赛线下半决赛 babysign

金砖北区 body

from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randint, getrandbits
from hashlib import sha256, md5
from secret import flag


def pad(x):
    return x + b"\x00" * (16 - len(x) % 16)

def sign(message, sk):
    global state
    new_state = sum([state[i] * c[i] for i in range(t+1)]) % N
    state = [1] + state[2:] + [new_state]
    nonce = new_state
    r = pow(g, nonce, p) % q
    s = inverse(nonce, q) * (sk * r + int(sha256(message).hexdigest(), 16)) % q
    return r, s

p = getPrime(1024)
q = getPrime(200)
g = 3
N = getPrime(320)
sk = getrandbits(200)
n = 6
t = 3
state = [1] + [randint(0, N) for i in range(t)]
c = [getrandbits(320) for i in range(t+1)]
messages = [b"114514" * (i+1) for i in range(n)]

aes = AES.new(key = md5(long_to_bytes(sk)).digest(), mode = AES.MODE_ECB)
enc = bytes_to_long(aes.encrypt(pad(flag)))

R = []
S = []
for i in range(n):
    ri, si = sign(messages[i], sk)
    R.append(ri)
    S.append(si)

print(f"p = {p}")
print(f"q = {q}")
print(f"N = {N}")
print(f"c = {c}")
print(f"R = {R}")
print(f"S = {S}")
print(f"enc = {enc}")

# p = 116785031927093815079233136633589947752028911814800868369869578931870316046596785184894055371144036776064669868249704618985421271853448853632376254540547823104322168401953544967240347406778720423318565073239690241326817042043484929051576775448673203463074117804649959541507698229893054556550320469203456146047
# q = 1162013185697688453861664553499752399253322748004409113204127
# N = 1323897959325310735325275996475445031975979778815661937579963020223071860214584612380772205207187
# c = [1574322976538315862255039136507109494732893739698961604892927232272176602957720633460435741950981, 982748104570818459054599891053556093959178786766931425281691326835429426630180908134485622115900, 1736434097211081733335115305035342227336962166280217992786003296206828586078433857642947981291194, 1611245572755629905925930221417986751829942084516991104467460999051993831140932783222153911156935]
# R = [250723510788061232081262385603532530634797991937698265582129, 1119721148493144310690267430343591660519419423686023703999507, 327545854313187207152129310491071838289266078925279902580373, 294674329401405307401702457581449942310191500297502018110890, 663517568607778388357638916138325550655894605288185145315867, 580405277132704993594863659545429137977778544843615107482308]
# S = [1098300247591937477578678390124289151378133148552007096408606, 346993462577560155944670863440470223701841323677343217088457, 933695813746504256108426703091701687206684474504987617246020, 1100476120163015325635271971069982126075015834609795493295818, 733513755429731444068237311173894585893520394841207986015275, 1004580193918286835282796048415957927624525481538935452518194]
# enc = 11598259742163605745958985708470844817127222649553248988499234398208575208165607188940106811244327384195175174260322

最开始以为是 DSA + LFSR，后面才知道是论文 DSA+LCG变形

《“Pseudo-Random” Number Generation within Cryptographic Algorithms: the DSS Case》

eg：

$\left\{\begin{matrix} s_1k_1-r_1x = m_1 \bmod q \\ s_2k_2-r_2x = m_2 \bmod q\\ -ak_1+k_2=b \bmod M \end{matrix}\right.$

构建格：

$M = \begin{bmatrix} s_1& 0 & -a & E_1 & 0 & 0\\ 0& s_2& 1 & 0 & E_2 & 0\\ -r_1 & -r_2 & 0 & 0 & 0 & E_3\\ q & 0 & 0 & 0 & 0 & 0\\ 0 & q & 0 & 0 & 0 & 0\\ 0 & 0 & M & 0 & 0 & 0 \end{bmatrix}$

则存在向量 $a=(k_1,k_2,x,j_1,j_2,j_3)$ ，使得 $a\times M = (m_1,m_2,b,k_1E_1,k_2E_2,xE_3) $

直接进行格基规约的话可能得不到想要的向量，因此设

$E_1 =\frac{1}{\gamma_1},E_2 =\frac{1}{\gamma_1},E_3 =\frac{1}{\gamma_2}$

其中 $\gamma_1 $ 是和相同数量级的一个数，$\gamma_2$ 是和 x 相同数量级的一个数，这样就能够让 $k_1E_1,k_2E_2,xE_3$ 都趋向于 1，然后我们就再在这个规约后的格子上找一个 $(m_1,m_2,b,1,1,1)$ 的 CVP 就行了

题解：

回到本题

LCG变形：

$k_{i+3}=c_0+c_1*k_i+c_2*k_{i+1}+c_3*k_{i+2} \pmod N$

利用上面的例子，我们可以去得到：

$\left\{\begin{matrix} s_0k_0-r_0x = m_0 \bmod q \\ s_1k_1-r_1x = m_1 \bmod q \\ s_2k_2-r_2x = m_2 \bmod q\\ s_3k_3-r_3x = m_3 \bmod q\\ s_4k_4-r_4x = m_4 \bmod q\\ s_5k_5-r_5x = m_5 \bmod q\\ k_{3}=c_0+c_1*k_0+c_2*k_{1}+c_3*k_{2} \pmod N\\ k_{4}=c_0+c_1*k_1+c_2*k_{2}+c_3*k_{3} \pmod N\\ k_{5}=c_0+c_1*k_2+c_2*k_{3}+c_3*k_{4} \pmod N\\ \end{matrix}\right.$

构建格：

L = Matrix(QQ,
[   [ s0,  0,  0,  0,  0,  0,-c1,  0,  0,1/E1,0,0,0,0,0,0], 
    [  0, s1,  0,  0,  0,  0,-c2,-c1,  0,0,1/E1,0,0,0,0,0], 
    [  0,  0, s2,  0,  0,  0,-c3,-c2,-c1,0,0,1/E1,0,0,0,0], 
    [  0,  0,  0, s3,  0,  0,  1,-c3,-c2,0,0,0,1/E1,0,0,0], 
    [  0,  0,  0,  0, s4,  0,  0,  1,-c3,0,0,0,0,1/E1,0,0], 
    [  0,  0,  0,  0,  0, s5,  0,  0,  1,0,0,0,0,0,1/E1,0], 
    [-r0,-r1,-r2,-r3,-r4,-r5,  0,  0,  0,0,0,0,0,0,0,1/E2], 
    [  q,  0,  0,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  q,  0,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  q,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  q,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  q,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  q,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  N,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  0,  N,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  0,  0,  N,0,0,0,0,0,0,0]]
)

则存在向量 $a=(k_0,k_1,k_2,k_3,k_4,k_5,x,j_0,j_1,j_2,j_3,j_4,j_5,j_6,j_7,j_8)$ ，使得 $a\times M = (m_0,m_1,m_2,m_3,m_4,m_5,c_0,c_0,c_0,k_0E_1,k_1E_1,k_2E_1,k_3E_1,k_4E_1,,k_5E_1,xE_2) $

因为 x ，也即 sk 是 200 bit 的，k ，也即 nonce 是 320 bit 的，所以对应调一下

$E_1 = \frac{1}{2^{320}},E_2 = \frac{1}{2^{200}} $

然后利用LLL算法和Babai最近平面算法，可以在多项式时间内找到SVP近似解。

也就是上述的找一个 $(m_0,m_1,m_2,m_3,m_4,m_5,c_0,c_0,c_0,1,1,1,1,1,1,1)$ 的 CVP

exp：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randint, getrandbits
from hashlib import sha256, md5

p = 116785031927093815079233136633589947752028911814800868369869578931870316046596785184894055371144036776064669868249704618985421271853448853632376254540547823104322168401953544967240347406778720423318565073239690241326817042043484929051576775448673203463074117804649959541507698229893054556550320469203456146047
q = 1162013185697688453861664553499752399253322748004409113204127
N = 1323897959325310735325275996475445031975979778815661937579963020223071860214584612380772205207187
c = [1574322976538315862255039136507109494732893739698961604892927232272176602957720633460435741950981, 982748104570818459054599891053556093959178786766931425281691326835429426630180908134485622115900, 1736434097211081733335115305035342227336962166280217992786003296206828586078433857642947981291194, 1611245572755629905925930221417986751829942084516991104467460999051993831140932783222153911156935]
R = [250723510788061232081262385603532530634797991937698265582129, 1119721148493144310690267430343591660519419423686023703999507, 327545854313187207152129310491071838289266078925279902580373, 294674329401405307401702457581449942310191500297502018110890, 663517568607778388357638916138325550655894605288185145315867, 580405277132704993594863659545429137977778544843615107482308]
S = [1098300247591937477578678390124289151378133148552007096408606, 346993462577560155944670863440470223701841323677343217088457, 933695813746504256108426703091701687206684474504987617246020, 1100476120163015325635271971069982126075015834609795493295818, 733513755429731444068237311173894585893520394841207986015275, 1004580193918286835282796048415957927624525481538935452518194]
enc = 11598259742163605745958985708470844817127222649553248988499234398208575208165607188940106811244327384195175174260322


r0,r1,r2,r3,r4,r5 = R
s0,s1,s2,s3,s4,s5 = S
c0,c1,c2,c3 = c
E1=2^320
E2=2^200

L = Matrix(QQ,
[   [ s0,  0,  0,  0,  0,  0,-c1,  0,  0,1/E1,0,0,0,0,0,0],  
    [  0, s1,  0,  0,  0,  0,-c2,-c1,  0,0,1/E1,0,0,0,0,0], 
    [  0,  0, s2,  0,  0,  0,-c3,-c2,-c1,0,0,1/E1,0,0,0,0], 
    [  0,  0,  0, s3,  0,  0,  1,-c3,-c2,0,0,0,1/E1,0,0,0], 
    [  0,  0,  0,  0, s4,  0,  0,  1,-c3,0,0,0,0,1/E1,0,0], 
    [  0,  0,  0,  0,  0, s5,  0,  0,  1,0,0,0,0,0,1/E1,0], 
    [-r0,-r1,-r2,-r3,-r4,-r5,  0,  0,  0,0,0,0,0,0,0,1/E2], 
    [  q,  0,  0,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  q,  0,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  q,  0,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  q,  0,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  q,  0,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  q,  0,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  N,  0,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  0,  N,  0,0,0,0,0,0,0,0], 
    [  0,  0,  0,  0,  0,  0,  0,  0,  N,0,0,0,0,0,0,0]]
)



L_lll = L.LLL()

def BabaisClosestPlaneAlgorithm(L, w):
    G, _ = L.gram_schmidt()
    t = w
    i = L.nrows() - 1
    while i >= 0:
        w -= round( (w*G[i]) / G[i].norm()**2 ) * L[i]
        i -= 1
    return t - w

messages = [b"114514" * (i+1) for i in range(6)]


m0,m1,m2,m3,m4,m5 = [int(sha256(i).hexdigest(),16)  for i in messages]
Y = vector([m0, m1, m2, m3 , m4, m5, c0, c0, c0, 1, 1, 1, 1, 1, 1, 1]) # target vector
X = BabaisClosestPlaneAlgorithm(L_lll, Y)
sk = X[-1]*E2##

aes = AES.new(key = md5(long_to_bytes(int(sk))).digest(), mode = AES.MODE_ECB)
flag = aes.decrypt(long_to_bytes(enc))
print(flag)

# flag{d41d8cd98f00b204e9800998ecf8427e}

DAS_DSA

DDAASSSAA.py

from Crypto.Util.number import *
import hashlib

b2l=lambda x:bytes_to_long(x)
l2b=lambda x:long_to_bytes(x)
def xor(A,B):
  return bytes([a ^ b for a, b in zip(A, B)])
class SimpleDSASigner:
    def __init__(self, p, q, g, x,KEY):
        self.p = p
        self.q = q
        self.g = g
        self.x = x
        self.y = pow(self.g, self.x, self.p)
        self.KEY=KEY
    def sign(self, message):
        h = int(hashlib.sha256(message).hexdigest(), 16)
        k = b2l(xor(message,self.KEY))
        r = pow(self.g, k, self.p) % self.q
        s = (inverse(k, self.q) * (h + self.x * r)) % self.q
        if r != 0 and s != 0:
            return (r, s)
    def verify(self, message, r, s):
        h = int(hashlib.sha256(message).hexdigest(), 16)
        w = inverse(s, self.q)
        u1 = (h * w) % self.q
        u2 = (r * w) % self.q
        v = ((pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p) % self.q
        return v == r
    def give_gift(self):
        return (self.p,self.q,self.g,self.y)

task.py

import random
from DDAASSSAA import *
from Crypto.Util.Padding import pad
from flag import FLAG
ALPHABET = "DAS"
KEY_LENGTH = 32

def generate_random_string(length, chars):
    return ''.join(random.choice(chars) for _ in range(length))

def get_message(num_messages):
    return [generate_random_string(random.randint(20, 32), ALPHABET) for _ in range(num_messages)]

def get_key():
    return generate_random_string(KEY_LENGTH, ALPHABET).encode()

def get_strong_prime(kbits):
    while True:
        q = getPrime(kbits)
        p = q * 2 + 1
        if isPrime(p):
            return p, q

def write_to_file(filename, data, rwx="w"):
    with open(filename, rwx) as file:
        for item in data:
            file.write(f"{item}\n")

if __name__ == "__main__":
    num_messages = 2024 // 65
    messages = get_message(num_messages)
    p, q = get_strong_prime(256)
    x = random.randrange(q)
    key = get_key()

    signer = SimpleDSASigner(p, q, 2, x, key)
    write_to_file("GIFT.txt", messages)
    signatures = [signer.sign(pad(msg.encode(), 32)) for msg in messages]
    write_to_file("enc.txt", map(str, signatures))
    write_to_file("enc.txt", [str(signer.give_gift())],"a")

    assert FLAG==b"DASCTF{"+key+b"}"

GIFT.txt

SDSSDASSAAASSDADSASADASSSSADDS
SADADDAASSAASDSAAAAADS
SSASDDDSSSSDDSDAAAAAASAASDSA
SASSDSDSSSDSSDSDASADDA
SDDAAASASADDAADDSSSSDASAASADSA
AASADASADDSDDASADSAS
DASDDDDAASADDASADAAAAAADS
DSAAAASASDDDDDDSSASDADSASDDA
ADSSSSAADDSDDDADAADD
ASDDSADAASSASSDSDDSSD
SASSDDAASDDSADSDSSDAASSAD
DADSDAASAADDAAASASSSA
DADDADSSDADAADSSADDADDDSSDAS
AAASDSSDSAASDADDSADSDA
ASDASSDSDDADADSDSDDDDADSSAADAS
SDSASDADDASDASSDSAAASSASSDADA
AADDSSDSDADSASDDSASSDDD
SAADASAADAASDDDSASSDAASAAAS
SSDDADSAADSDSSADSADSAASASDSAS
DSDDAAASDDDSAASSDDDAASADSS
SASSAAAAAAADSDASSDASSDAS
DDDASAASDAADSSSASAAAADSDD
SASADSSSAADDASADDDADD
ASDDDDSDDSSSAASASDSSDDASA
DSAASDSDAADAAAAASADSDDDDAAA
ADSDADDDASASDSDADSADADDSASSSD
ADADDASSDSDASADDSADSD
SASAASDSDDASADASSSDSAAA
SASDDADSSDASDDSSDSDA
ADAASDSSDSDASSASADDSDDASAS
AADADDSAADDDSASADASSDAADADAA

enc.txt

(59254487398967388114905667045028363843329923626238494813205814542210325221866, 38134152657262330507433713437784426184950965354807113354631630191330303144120)
(7272091585909282735283006759301331954064261183899338079418296410637263888770, 25499964678151126566605578540840513489434638253159604087981425065951344757164)
(6899645492048427857621143178962093646174799398991863666101058693217698732368, 9791582686238213337967141368906212036310014918808878260483336268832064128819)
(25004120896291255053237639070744331951278481119827357255754648579794346195560, 141512006531073436448016797005260994098008785866923890662245540709534244927)
(2970680424634969125510981613739745658897845410407912521400879068659540408508, 21793011307831199247000930716490000926029175766326909085969585420590222327264)
(54566000630497640561512172245143554745650114820675965968691149808463168361994, 14349862994826483344159692458388566295460798903541941504424537018216650283613)
(75159685495692974866291952764676724718763580667689472941977359299782008334398, 70458140884809949567915541063312538538372757595177423386408938073672211639375)
(20041025052466338500977838626769109456575569706600589389016534358968746705758, 65530083011107720400920780939345704754954869671333734672594688826098321351660)
(70127192435034402135747706941502224672808592757766109942714487474501491910214, 57063474646503909216126596725677068514339517777473453937098665282959018241139)
(9691674719110233709152049443866537766465800386755314400120771762265195237696, 62093763551744197212031574855244002702924782008725363963219173846480120194830)
(71705536377844454384479609516094364197930343317149881589774662842233960882414, 77374603032347186343803094100249733360600621594214414598796066240713702791608)
(52879693221782582945807231749976747516107564896599455986464226581743117039645, 1344584960351311598238142429846629993914377848692708811135221930719773821079)
(77382790022991362370508965243223326049308313776687214599186184000848696471646, 43641233828500431963081402892838426285406919342406723474664571883294369141394)
(56346141869522955969887972614456267251604757060687228073793419107933969328162, 76285674574149814839616688665569434237657824816977670694242559140508233840268)
(13673786393914569132256858604647869957632869873889606981549833789272316263013, 55327829510120473782794486945583818434703312785066895788282945944551470490709)
(64767740468987944636292946852714160626094908713011502873333251460983428727987, 13259490361346409766866273875042192439139048727072955549892484859673179719539)
(3957421961183318932163297455146838208380750250268324980567615749312524020603, 26882140137481455957383933013829466811327529673163422516945649296787438630196)
(26427922029900012253901950242265848521558605010629901777129266992870754082725, 69951840114040217998552588969628162605092507207522992695398095063314527794456)
(41377529326816743042387061355650636824586430044255853849728865473372840135697, 11219359019456290145545276763003725218855047474525360923001515509608652449000)
(25716607607446503241765016815241812755718791371526314953930748513731536667770, 28453782213087434330094261632474010077787574243224303728751260500450723227337)
(19800391798756020076641438144957219387739406397111495660920822320302304854123, 45451686690348328576376896082606976500453603983712180502700202971927238065259)
(38726290839677684687529233274549282905118675478275260942535144771737271586397, 40829316203033016996956478373044348905634931325393076578307296318880401948880)
(39209612764454560795450300186392582769693156243512973558204034254768849812055, 1354495451811853700039180690705948597695565424847801455594169929311025313998)
(65513712517147774905818288938959930101260466094015953149923879872714745367445, 15372704507991354781967074099137226451034611060413049367266363154832614415805)
(15729001560566023616632342669016214191974988848807788455841465085832368458445, 16327134664007312833089147621817036851276111964898734022794700122827444854947)
(42181696175119369852613642818168055609726913997313538977450877772345284116500, 9844926061501886811803369928846120575402269452312877926396348651872911440254)
(66136301537002842836817588252827389434354772150463143258637074246966542574050, 40179237579762663098604891208246052072476264271372972425562554108399403298795)
(28759447425094984124057238672075080352158483766211322160596339820824930247130, 31809179023991813094371890170356817265600467849999331763205655801654108159032)
(46713611880672324334213026166944979498146683097425440783760089321619754080806, 23270114877894114090584274918755188867365261145736710892185678426446455871613)
(57079205189933243387798430767693634017842334556643904914267966016857671112460, 18247249527866143497935092319901700668290600772967638096649240924154901762810)
(10688647176294432598580110142909961685073598720504815121442568862023227643325, 54331697420125697460151875535555752680845260504979536685075170636565355173106)
(156169498993837300941969389078565637464689185713213578550979549862042014984607, 78084749496918650470984694539282818732344592856606789275489774931021007492303, 2, 59080272611010540206200716660225398487916425104605746321153704646003914371135)

31 组 r，s，典型 HNP，不过直接规约不出来

这里 key 的构成已知，无非 “DAS” 可重复组合

可以接受爆破 key 的高位

已知 k 的高位

直接拿上面的下来：

$k_i=(r_0s_i)^{-1}(H_ir_0-H_0r_i)+(r_0s_i)^{-1}(r_is_0)k_0 \pmod q$ $令 ~~~k_i = 2^{l_{bit}}k_{ih}+k_{il}$

最后会得到

$k_{il}=(r_0s_i)^{-1}(r_is_0)k_{0l} +(H_ir_0-H_0r_i+s_0r_i2^{l_{bit}}k_{0h}-s_ir_02^{l_{bit}}k_{ih})(s_ir_0)^{-1} \pmod q$

令 $A_i=(r_0s_i)^{-1}(r_is_0) \pmod q$

$B_i=(H_ir_0-H_0r_i+s_0r_i2^{l_{bit}}k_{0h}-s_ir_02^{l_{bit}}k_{ih})(s_ir_0)^{-1}$

HNP 的形式就出来了

$[l_0~~l_1~~\dots ~~l_n~~k_{0l}~~1]\begin{bmatrix} q& 0& \dots & 0 & 0 & 0\\ 0& q& \dots & 0 & 0 & 0\\ \vdots& \vdots& \ddots& \vdots& \vdots& \vdots\\ 0& 0& \dots& q & 0 & 0\\ A_0& A_1& \dots& A_n & 1 & 0\\ B_0& B_1& \dots & B_n & 0 & K \end{bmatrix}=[k_{0l}~~k_{1l}~~\dots~~k_{nl}~~k_{0l}~~K]$

exp：

from Crypto.Util.Padding import pad
import hashlib
from itertools import product
from Crypto.Util.number import *

with open('enc.txt','r') as f:
    f = (f.read().encode().split(b'\n'))

p,q,g,y = eval(f[-2])

R = []
S = []
for i in range(len(f)-2):
    R.append(eval(f[i])[0])
    S.append(eval(f[i])[1])

with open('GIFT.txt','r') as f:
    f = (f.read().split('\n'))

H = []
for i in range(len(f)-1):
    message = pad(f[i].encode(), 32)
    h = int(hashlib.sha256(message).hexdigest(), 16)
    H.append(h)

r0 = R[0]
s0 = S[0]
h0 = H[0]
n = len(R)

A = [(s0 * R[i] * inverse((S[i] * r0), q)) % q for i in range(n)]

for k in product('DAS',repeat = 3):
    keyh = ''.join(k).encode()
    kih = []
    for i in range(n):
        kih.append((bytes_to_long(f[i][:3].encode()) ^^ bytes_to_long(keyh)) * 256 ^ 29)

    B = [(H[i]*r0 - h0*R[i] + s0*R[i] * kih[0] - S[i]*r0*kih[i]) * inverse((S[i]*r0),q) % q for i in range(n)]

    K = 256^29
    L = Matrix(ZZ, n + 2, n + 2)
    for i in range(n):
        L[i, i] = q
        L[-2, i] = A[i]
        L[-1, i] = B[i]
    L[-2, -2] = 1
    L[-1, -1] = K

    for line in L.LLL():
        if line[-1] == K:
            k_low = abs(line[-2])
            k0 = kih[0] + k_low
            key = long_to_bytes(k0 ^^ bytes_to_long(pad(f[0].encode(), 32)))
            if (i in b"DAS" for i in key):
                print(key)
                # print(line)
                break
    
# b'AADDAASAAASSSASSDSSASSDDDSDAAASS'

已知 k 的低位

同理，爆破 k 的低位也是可以接受的

最后会得到

$k_{ih}=(r_0s_i2^{l_{bit}})^{-1}(r_is_02^{l_{bit}})k_{0h} +(H_ir_0-H_0r_i+s_0r_ik_{0l}-s_ir_0k_{il})(s_ir_02^{l_{bit}})^{-1} \pmod q$ $令~~~A_i=(r_0s_i2^{l_{bit}})^{-1}(r_is_02^{l_{bit}}) \pmod q$ $B_i=(H_ir_0-H_0r_i+s_0r_ik_{0l}-s_ir_0k_{il})(s_ir_02^{l_{bit}})^{-1}$

n = len(R)
bit = int(k_low).bit_length()
A = [((S[0]*R[i]*2**(bit)) * inverse((S[i]*R[0]*2**(bit)),q)) % q for i in range(n)]
B = [(H[i]*R[0] - H[0]*R[i] + S[0]*R[i]*j - S[i]*R[0]*j) * inverse((S[i]*R[0]*2**(bit)),q) % q for i in range(n)]

已知 k 的高位和低位

同理，这里也不是不能接受。。。

`HNP` 补充

2024-08-06

$[l_0~~l_1~~\dots ~~l_7~~x~~1]\begin{bmatrix} q& 0& \dots & 0 & 0 & 0\\ 0& q& \dots & 0 & 0 & 0\\ \vdots& \vdots& \ddots& \vdots& \vdots& \vdots\\ 0& 0& \dots& q & 0 & 0\\ A_0& A_1& \dots& A_7 & \frac{K}{q} & 0\\ B_0& B_1& \dots & B_7 & 0 & K \end{bmatrix}=[k_0~~k_1~~\dots~~k_7~~\frac{K}{q}x~~K]$

注意构建矩阵的时候，矩阵类型就变成 QQ 了，(报错原因找到了🥲)

L = Matrix(QQ, n + 2, n + 2)
K = 2 ** 128
L[-2][-2] = K / q
L[-1][-1] = 2 ** 128

细节就需要自己去test了😊😊

dsa常见题型：

DSA数字签名 | DexterJie’Blog

reference：

【星盟安全】2024年春秋杯夏季赛密码讲解_哔哩哔哩_bilibili

浅尝 Lattice 之 HNP-安全客 - 安全资讯平台 (anquanke.com)

2024 数字中国积分争夺赛线下

理论：

密钥生成

签名

验签

代码

题目

signature

HNP

非预期：

body、babysign

eg：

题解：

exp：

DAS_DSA

已知 k 的高位

已知 k 的低位

已知 k 的高位和低位

HNP 补充

dsa常见题型：

reference：

`HNP` 补充