DSA数字签名

发表于 更新于 阅读次数： Waline： 本文字数： 7.2k 阅读时长 ≈ 26 分钟

简单记录DSA数字签名

始发于2023年8月18日，于2024年7月26日更新

DSA数字签名

密钥生成

  1. 选择一个合适的哈希函数，一般选择SHA1
  2. 选择密钥的长度$L$和$N$
  3. 选择$N$比特的素数$q$
  4. 选择$L$比特的素数$p$，使得$p-1$是$q$的倍数
  5. 选择满足$g^k \equiv 1 \mod p$的最小正整数$k$为$q$的g，就是在模$p$的前提下，$ord(g) = q$的$g$
  6. 选择私钥$x \in (0,q)$，计算$y\equiv g^x \mod p$
  7. 公钥为$(p,q,g,y)$，私钥为$x$

签名过程

  1. 选择随机整数$k(0,q)$作为临时密钥
  2. 计算$r\equiv (g^k \mod p) \mod q$
  3. 计算$s \equiv k^{-1}(H(m)+xr) \mod q$

公开$(r,s)$，$H(m)$指明文m的哈希值

验证过程

  1. 计算$\omega \equiv s^{-1} \mod q$

  2. 计算$\mu_1 \equiv H(m)×\omega \mod q$

  3. 计算$\mu_2 \equiv r×\omega \mod q$

  4. 计算$v \equiv (g^{\mu_1}y^{\mu_2}\mod p) \mod q$

  5. 如果$v = r$则验证成功

    证明:

$$
v \equiv g^{\mu_1}y^{\mu_2} \equiv g^{H(m)s^{-1}}\times g^{xrs^{-1}} \equiv g^{s^{-1}(H(m)+xr)} \equiv g^{k} \equiv r \mod q
$$

题型1:复用k

如果两次签名用了同一个$k$，就可以进行攻击，推导如下

当$k$一样时，两个$r$是一样的，则有

$$
s_1 \equiv k^{-1}(H(m_1)+xr) \mod q
$$

$$
s_2 \equiv k^{-1}(H(m_2)+xr) \mod q
$$

两式相减得

$$
(s_1-s_2) \equiv k^{-1}(H(m_1)-H(m_2)) \mod q
$$

$$
k \equiv (s_1-s_2)^{-1}(H(m_1)-H(m_2)) \mod q
$$

求出$k$后，根据
$$
s \equiv k^{-1}(H(m)+xr) \mod q
$$

$$
sk \equiv H(m)+xr \mod q
$$

$$
x\equiv (ks - H(m))r^{-1}\mod q
$$

长城杯 2022——known_phi

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
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
from Crypto.PublicKey import DSA
from hashlib import sha256
import random
from secret import flag

def gen(a):
    p = getPrime(a) 
    q = getPrime(a)
    r = getPrime(a)
    x = getPrime(a)
    n = p*q*r*x
    phi = (p-1)*(q-1)*(r-1)*(x-1)

    return n, phi, [p, q, r, x]

def sign(m, k, x, p, q, g):
    hm = bytes_to_long(sha256(m).digest())
    r = pow(g, k, p) % q
    s = (hm + x*r) * inverse(k, q) % q

    return r,s

e = 65537
a = 256
x = bytes_to_long(flag)
# print(x)

n, phi, n_factors = gen(a)
n_factors = sorted(n_factors)
print(f'n = {n}')
print(f'phi = {phi}')
m1 = long_to_bytes(n_factors[0] + n_factors[3])
m2 = long_to_bytes(n_factors[1] + n_factors[2])
# print(f'm1 = {m1}')
# print(f'm2 = {m2}')

key = DSA.generate(int(2048))
q = key.q
p = key.p
g = key.g
assert q > x
k = random.randint(1, q-1)
r1, s1 = sign(m1, k, x, p, q, g)
r2, s2 = sign(m2, k, x, p, q, g)
# print(f'k = {k}')
print(f'q = {q}')
print(f'r1 = {r1}')
print(f's1 = {s1}')
print(f'r2 = {r2}')
print(f's2 = {s2}')

'''
n = 104228256293611313959676852310116852553951496121352860038971098657350022997841589403091722735802150153734050783858816709247647536393314564077002364012463220999962114186339228164032217361145009468516448617173972835797623658266515762201804936729547278758839604969469770650218191574897316410254695420895895051693
phi = 104228256293611313959676852310116852553951496121352860038971098657350022997837434645707418205268240995284026522165519145773852565112344453740579163420312890001524537570675468046604347184376661743552799809753709321949095844960227307733389258381950812717245522599433727311919405966404418872873961877021696812800
q = 24513014442114004234202354110477737650785387286781126308169912007819
r1 = 8881880595434882344509893789458546908449907797285477983407324325035
s1 = 764450933738974696530033347966845551587903750431946039815672438603
r2 = 8881880595434882344509893789458546908449907797285477983407324325035
s2 = 22099482232399385060035569388467035727015978742301259782677969649659
'''

已知$n,phi$，网上找个脚本把n分解之后，可以得到$m_1,m_2$。

有了$m_1,m_2$即可求哈希后的值$h_1,h_2$

求得$k \equiv (s_1-s_2)^{-1}(h_1-h_2) \mod q$

最后求得$x\equiv (ks_1 - H_1)r_1^{-1}\mod q$

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
from Crypto.Util.number import *
import gmpy2
from hashlib import sha256


n = 
phi = 
q = 24513014442114004234202354110477737650785387286781126308169912007819
r1 = 8881880595434882344509893789458546908449907797285477983407324325035
s1 = 764450933738974696530033347966845551587903750431946039815672438603
r2 = 8881880595434882344509893789458546908449907797285477983407324325035
s2 = 22099482232399385060035569388467035727015978742301259782677969649659

primes = sorted(factorize_multi_prime(n,phi))

m1 = long_to_bytes(primes[0]+primes[3])
m2 = long_to_bytes(primes[1]+primes[2])

h1 = bytes_to_long(sha256(m1).digest())
h2 = bytes_to_long(sha256(m2).digest())

k = gmpy2.invert((s1-s2),q)*(h1-h2) % q
r_ = gmpy2.invert(r1,q)

d = ((k * s1) - h1)*r_ % q
print(long_to_bytes(int(d)))

题型2:线性k

NSSRound#1 Basic——number_by_number

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
import hashlib
from Crypto.Util.number import *
from gmpy2 import *
FLAG = b'******************'
assert FLAG.startswith(b'NSSCTF{') and FLAG.endswith(b'}')
FLAG = FLAG[7:-1]

def sign(msg, pub, pri, k):
    (p,q,g,y) = pub
    x = pri
    r = int(pow(g, k, p) % q)
    h = int(hashlib.sha256(msg).digest().hex(),16)
    s = int((h + x * r) * invert(k, q) % q)
    return (r, s)

p = 12521300600879647215212622604478307167614802603722694432672492518732844280050451647647783544918670551333939947202324314036106883627652934658092246151569719841172139651756731975948641752941369320985906043813128667949407263418091261521078015038472125264708315959943830171678415621896727622381651264882655845219115471323352719455064712014904581019529062436850895982568432772820884304927292484611574315452532539622439874476205201585972439739033662281856954069390915294301650596122027017512657387126870291348326594014789938826560641601265413964203409968207292456857314148848395645091850604205535043035332961436498283695843
q = 89333150710898097819726085329049525002843220030438497258487456281988064920981
g = 4659169190462665152432024005060362819268084070474399613244522271693166269703240438309526888954293382169994621221386886590606442329876391429681914154130453072540079426475110538234340272617964838185872575922598867083747162403217264242469640383596415974818773608247780785279490355462362699968367544837511541267300331418420849521244364899679912282991493675152166261501255315036943693486335864565853496499243373834189894710718862409646613179068080762011713847012853815796678705445232715083564615906424779193638984542271665075749327914765645357163924702265124479067028868769369414557728443665123548337757950887923116453268
x = bytes_to_long(FLAG)
y = powmod(g, x, p)

pub = (p,q,g,y)
pri = x

nonce = getPrime(64)
print('y =', y)
print(sign(b'nssctfround#1', pub, pri, nonce))
print(sign(b'nssctfround#1', pub, pri, 12345*nonce + 67890))

'''
y = 516079379252376231001717898324355848864109868582016554029703521946402522000955354396295307046881971504216991061930299508521161039333927590076006514531946316725453062373440451679354041777376121961468715242703413529070177041819221792817124111175287475946526246377103779752133378942603534385789689950337366490082828044596711426514502752548887337695502949798115745655734033592905036846835127551577851715558217775334831352232997052342694255476534837857477388530834954919414905007702912216496977764789386913244009912368937860550222726279524193115767983754873150853915852619223039800432272818237552774389220137762595332280
(81900716895065212453759953296615257914462909922962929287345063257120550453427, 45144894416226080526306932143570511284754744855790908537643986192724824691890)
(60471460394555700734359895323450929800168788093422384886037011624642263106556, 74754852228035293908666429128869604520827363733944834534730568060790683199921)
'''

两次签名用的$k$存在线性关系，$k_2 = ak_1+b$

第一个签名:
$$
r_1 \equiv g^{k_1} \mod p \mod q
$$

$$
s_1 \equiv k_1^{-1}(H(m) + xr_1) \mod q
$$

第二个签名:
$$
r_2 \equiv g^{k_2} \mod p \mod q
$$

$$
s_2 \equiv k_2^{-1}(H(m)+xr_2) \mod q
$$

把$k_2$用$k_1$表示有
$$
s_1 \equiv k_1^{-1}(H(m)+xr_1) \mod q
$$

$$
s_2 \equiv (ak_1+b)^{-1}(H(m)+xr_2) \mod q
$$

然后有
$$
s_1k_1 \equiv H(m) + xr_1 \mod q
$$

$$
s_2(ak_1+b) \equiv H(m)+xr_2 \mod q
$$

接下来把$x$消去
$$
s_1k_1r_2 \equiv H(m)r_2+xr_1r_2 \mod q
$$

$$
s_2(ak_1+b)r_1 \equiv H(m)r_1 + xr_1r_2 \mod q
$$

相减得
$$
k_1(ar_1s_2 - s_1r_2) \equiv H(m)(r_1-r_2) -br_1s_2 \mod q
$$

$$
\therefore k_1 \equiv (H(m)(r_1-r_2)-br_1s_2) \times (ar_1s_2-s_1r_2)^{-1} \mod q
$$

求出$k_1$之后求私钥即可

exp.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
from Crypto.Util.number import *
import hashlib
import gmpy2

y = 
r1,s1 = (, )
r2,s2 = (, )
p = 
q = 
g = 
msg = b''
h = int(hashlib.sha256(msg).digest().hex(),16)

a = 
b = 

k = ((h*(r2 - r1) + b*r1*s2)*gmpy2.invert((r2*s1-a*r1*s2),q)) % q

m1 = (k*s1 - h)*gmpy2.invert(r1,q) % q
print(long_to_bytes(m1))

k1 = a*k+b

m2 = (k1*s2 - h)*gmpy2.invert(r2,q) % q
print(long_to_bytes(m2))

[HZNUCTF 2023 preliminary]easyDSA

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
from hash import *
from sage import *
from secrets import flag
from Crypto.Util.number import *
from gmpy2 import invert


def dsa(hmac, _pk, _sk, k):
    _p, _q, _g, _y = _pk
    x = _sk
    r = pow(_g, k, _p) % _q
    s = ((hmac + x * r) * invert(k, _q)) % _q
    return int(r), int(s)


m = int(flag.hex(), 16)
p = getPrime(2048)
q = getPrime(256)
g = getRandomNBitInteger(2048)
y = pow(g, m, p)
pk = (p, q, g, y)
sk = m
hm1 = int(SM3(default_hm1), 16)
hm2 = int(SM3(default_hm2), 16)
nonce = getPrime(64)
xxxx = getPrime(20)
print(f"(r1, s1) = {dsa(hm1, pk, sk, nonce)}")
print(f"(r2, s2) = {dsa(hm1, pk, sk, nonce ** 2 + xxxx)}")
print(f"p = {p}\nq = {q}\ng = {g}\ny = {y}")
# (r1, s1) = (, )
# (r2, s2) = (, )
# p = 
# q = 69375998045163628324086568160767337544901252262545889505892695427466730978301
# g = 
# y =

hash.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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import bytes_to_long

IV = 0x7380166f4914b2b9172442d7da8a0600a96f30bc163138aae38dee4db0fb0e4e
default_hm1 = b'HZNUCTFRound#1'
default_hm2 = b'HZNUCTFRound#1'

def solve_k(l):
    for i in range(512):
        if (l + 1 + i - 448) % 512 == 0:
            return i


def padding(msg):
    l = len(msg)
    k = solve_k(l)
    l64 = bin(l)[2:].rjust(64, '0')  # what if msg is too long, how?
    # so mention the condition in guideline of Algorithm
    msg = msg + '1' + '0' * k + l64
    assert len(msg) % 512 == 0
    return msg, l, k


def iteration():
    pass


def ring_shift_left(x, num):
    x = bin(x)[2:].rjust(32, '0')               # shift in 32 bit, take care of it
    x = int(x[num:] + x[:num], 2)
    return x


def p0(x):
    return x ^ ring_shift_left(x, 9) ^ ring_shift_left(x, 17)


def p1(x):
    return x ^ ring_shift_left(x, 15) ^ ring_shift_left(x, 23)


def extending(msg):
    WW = []
    for i in range(len(msg) // 512):
        W = ['0' for _ in range(132)]
        msgi = msg[i * 512:(i + 1) * 512]
        # 512 ====> 16 * 32
        for ii in range(len(msgi) // 32):
            W[ii] = msgi[ii * 32:(ii + 1) * 32]
            assert len(W[ii]) == 32
        for j in range(16, 68):
            # how to xor word, change to number or bytes?
            # number, of course
            W[j] = p1(int(W[j - 16], 2) ^ int(W[j - 9], 2) ^ ring_shift_left(int(W[j - 3], 2), 15)) ^ \
                   ring_shift_left(int(W[j - 13], 2), 7) ^ int(W[j - 6], 2)
            W[j] = bin(W[j])[2:]
            W[j] = W[j].rjust(32, '0')
        for j in range(68, 132):
            W[j] = int(W[j - 68], 2) ^ int(W[j - 68 + 4], 2)
            W[j] = bin(W[j])[2:]
            W[j] = W[j].rjust(32, '0')
        WW.append(W)
    return WW


def cons(j):
    if 0 <= j <= 15:
        return 0x79cc4519
    elif 16 <= j <= 63:
        return 0x7a879d8a


def bool_ff(param, j):
    x, y, z = param
    if 0 <= j <= 15:
        return x ^ y ^ z
    elif 16 <= j <= 63:
        return (x & y) | (x & z) | (y & z)


def bool_gg(param, j):
    x, y, z = param
    if 0 <= j <= 15:
        return x ^ y ^ z
    elif 16 <= j <= 63:                # take care of not
        if len(bin(x)[2:]) < 32:
            ans = ''
            x = bin(x)[2:].rjust(32, '0')
            y = bin(y)[2:].rjust(32, '0')
            z = bin(z)[2:].rjust(32, '0')
            for i in range(0, 32):
                if x[i] == '0':
                    ans += str((int(x[i], 2) & int(y[i], 2)) | (1 & int(z[i], 2)))
                elif x[i] == '1':
                    ans += str((int(x[i], 2) & int(y[i], 2)) | (0 & int(z[i], 2)))
            return int(ans, 2)
        elif len(bin(x)[2:]) == 32:
            return (x & y) | (~x & z)


def cf(v, w):
    W, W_ = w[:68], w[68:]
    # for i in W:
    #     print(hex(int(i, 2)), end=' ')
    # for i in W_:
    #     print(hex(int(i, 2)), end=' ')
    # print()
    v = bin(v)[2:].rjust(256, '0')
    A, B, C, D, E, F, G, H = [v[_ * 32:(_ + 1) * 32] for _ in range(256 // 32)]
    for j in range(64):
        # be care of plus, it may surpass 32 bits
        # remember j mod 32, or output will be wrong
        tmp = (ring_shift_left(int(A, 2), 12) + int(E, 2) + ring_shift_left(cons(j), j % 32)) & 0xffffffff
        SS1 = ring_shift_left(tmp, 7)
        SS1 = bin(SS1)[2:].rjust(32, '0')

        SS2 = int(SS1, 2) ^ ring_shift_left(int(A, 2), 12)
        SS2 = bin(SS2)[2:].rjust(32, '0')

        tmp = (bool_ff([int(A, 2), int(B, 2), int(C, 2)], j) + int(D, 2) + int(SS2, 2) + int(W_[j], 2)) & 0xffffffff
        TT1 = bin(tmp)[2:].rjust(32, '0')

        tmp = (bool_gg([int(E, 2), int(F, 2), int(G, 2)], j) + int(H, 2) + int(SS1, 2) + int(W[j], 2)) & 0xffffffff
        TT2 = bin(tmp)[2:].rjust(32, '0')

        D = C.rjust(32, '0')
        C = ring_shift_left(int(B, 2), 9)
        C = bin(C)[2:].rjust(32, '0')
        B = A.rjust(32, '0')
        A = TT1.rjust(32, '0')
        H = G.rjust(32, '0')
        G = ring_shift_left(int(F, 2), 19)
        G = bin(G)[2:].rjust(32, '0')
        F = E.rjust(32, '0')
        E = p0(int(TT2, 2))
        E = bin(E)[2:].rjust(32, '0')

        # print(j, end=' ')
        # for i in [A, B, C, D, E, F, G, H]:
        #     print(hex(int(i, 2)), end=' ')
        # print()
    ans = A + B + C + D + E + F + G + H
    ans = int(ans, 2)
    return ans


def SM3(msg):
    msg = bytes_to_long(msg)
    if msg.bit_length() % 4 != 0:
        msg = (4 - (msg.bit_length() % 4)) * '0' + bin(msg)[2:]
    msg, l, k = padding(msg)

    # extend
    W = extending(msg)

    # iteration
    vi = IV
    n = (l + k + 65) // 512
    for i in range(n):
        res = cf(vi, W[i])
        vi = vi ^ res

    # compress
    return hex(vi)[2:]

hash这个文件很长，主要就是算SM3，然后本题的k存在的关系是$k_2 = k_1^2 + b$，推导一下
$$
k_2 = k_1^2 + b
$$
第一对签名
$$
r_1 \equiv g^{k_1} \mod p \mod q
$$

$$
s_1 \equiv k_1^{-1}(H(m)+xr_1) \mod q
$$

第二对签名
$$
r_2 \equiv g^{k_1^2+b} \mod p \mod q
$$

$$
s_2 \equiv (k_1^2+b)^{-1}(H(m)+xr_2)\mod q
$$

于是有
$$
s_1k_1 \equiv H(m)+xr_1 \mod q
$$

$$
s_2(k_1^2+b)\equiv H(m)+xr_2 \mod q
$$

做线性变化消去x
$$
s_1r_2k_1 \equiv H(m)r_2 + xr_1r_2 \mod q
$$

$$
r_1s_2(k_1^2+b) \equiv H(m)r_1 + xr_1r_2 \mod q
$$

两式相减消去x
$$
r_1s_2k_1^2 +r_1s_2b - s_1r_2k_1 \equiv H(m)(r_1-r_2) \mod q
$$
这里有两个未知量，应该用二元copper可以求解

还可以换个推导，由
$$
s_1k_1 \equiv H(m)+xr_1 \mod q
$$

$$
s_2(k_1^2+b)\equiv H(m)+xr_2 \mod q
$$

得到
$$
x \equiv (s_1k_1 -H(m))r_1^{-1} \mod q
$$
$$
x \equiv (s_2(k_1^2+b)-H(m))r_2^{-1} \mod q
$$

两式相减构造一个模q的多项式
$$
f(x) = (s_2(k_1^2+b)-H(m))r_2^{-1} - (s_1k_1-H(m))r_1^{-1} \mod q
$$
先求出h=19905280947443115569469777697852124038269468456842113763109865796452965095134

二元copper求出$k_1,x$，即可求解

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
from Crypto.Util.number import *
import itertools
import gmpy2

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

(r1, s1) = (43665657147136977892760835332544097729763754398125679419859037123212964274095, 11372107439153704547599978617809027960018057676066118055075660375442954789009)
(r2, s2) = (29184887007213204285288676779168140587575609668559831035949650649308618592275, 5011738292572181542092375902756977363590922060964162373234404450451520414798)
p = 31961141251107494919420190534228520246958409864267239760354623819192809291490262139213317490432416411403367763443527530375117617196123131270496004125231254335150221348901335274505489844222882171272650010562960614279185073793274638651086760235178963210965828168433516820007716846876686795459738332444629111764967204355463398049697867061034126529189537688874999118692225915790053920062142349951686250122300061810240375783724631961234942175580462986265098353263395579346466921241016500821787793395554444982717141449909744838267161237273856377774256250949274635575801148994817767751541256849860886577256992383324866941911
q = 69375998045163628324086568160767337544901252262545889505892695427466730978301
g = 23095306638137759877487469277470910487928442296144598697677211337473146684728707820084075779044942034329888686699655576145455963231144004571165817481066424910959951439014314776050521403558035997997820617824839889597136772108383034876458141163933312284054415480674388788905935457149956424898637134087874179010376667509489926236214865373552518669840236207944772752416668193786003948717604980584661094548997197117467440864460714843246250800575997370964173558788145639802963655916833143883799542309432910222224223561677245110195809587171802538978009246887077924173034608600837785506594525481696000424121705524449481831586
y = 30195133393879069638917191223585579396119430591488890396938821804398771785068454607425044458865556053274470709839502680269466948174813926392729790863065933078609827279352860810689776644132512095691760326095517755483748554008211568781998662554432781285208646921699265866446498342049913829592480268053599307065979016922204438675164034767731708343084371572648019835171087671868322447023378942812010740490724160077164191297435291229504616686997442254543493394641023587237077429236872101951650325361004443988267286616139798736713430746804524113024341440435623834197278500144543476528466395780355874841379098027115073850819
h = 19905280947443115569469777697852124038269468456842113763109865796452965095134

R.<k,x> = PolynomialRing(Zmod(q))
f = (s2*(k^2+x)-h)*int(gmpy2.invert(r2,q)) - (s1*k-h)*int(gmpy2.invert(r1,q))
roots = small_roots(f,(2^64,2^20),m=1,d=2)
print(roots)

k,b = roots[0]
m = (s1*k-h)*gmpy2.invert(r1,q) % q
print(long_to_bytes(int(m)))

一类基于DSA的HNP问题

参考：一类基于各种DSA的HNP问题求解

常规

这类题常常给出多组签名对
$$
r_i \equiv g^{k_i} \mod p \mod q
$$

$$
s_i \equiv k_i^{-1}(H_i+ xr_i) \mod q
$$

大多数要造格来做，常规情况下是根据
$$
s\equiv k^{-1}(H+xr) \mod q
$$

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

记$A = s^{-1}r \mod q$，$B = s^{-1}H \mod q$
$$
\therefore k \equiv Ax + B \mod q
$$
构造格
$$
\begin{pmatrix}
t_1 & t_2 &…&t_n & x & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots &\vdots &\vdots & \vdots\\
0 & 0 & … & q &0 & 0\\
A_1 & A_2 & … & A_n & 1 & 0\\
B_1 & B_2 & … & B_n & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_1 & k_2 & … & k_n & x &K
\end{pmatrix}
$$
如果x不太大的情况下，这个格就可以规约出私钥x了。

简单搞了一个例子

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
40
41
42
43
44
45
46
47
48
49
from Crypto.Util.number import *
from Crypto.PublicKey import DSA
import random
import hashlib

def gen_key():
    pri = getPrime(128)
    pub = pow(g,pri,p)
    return pri,pub

def sign(m,pri):
    k = getPrime(128)
    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


key = DSA.generate(1024)
p, q, g = key.p, key.q, key.g
pri, pub = gen_key()
print(f"p = {p}")
print(f"q = {q}")
print(f"g = {g}")
print(f"pub = {pub}")

flag = "flag{" + hashlib.sha256(str(pri).encode()).hexdigest() + "}"

for i in range(5):
    r,s = sign(str(i).encode(),pri)
    print(f"r = {r}")
    print(f"s = {s}")
    
"""
p = 
q = 
g = 
pub = 
r =
s = 
r = 
s = 
r = 
s =
r = 
s = 
r = 
s = 
"""

exp.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
import hashlib
from Crypto.Util.number import *

p = 
q = 
g = 
pub = 

R = [,,,,]
S = [,,,,]
H = [int(hashlib.sha256(str(i).encode()).hexdigest(),16) for i in range(5)]

A = [inverse(S[i],q) * R[i] % q for i in range(5)]
B = [inverse(S[i],q) * H[i] % q for i in range(5)]
n = len(A)
K = 2^128

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]
    
Ge[-2,-2] = 1
Ge[-1,-1] = K

for line in Ge.LLL():
    if line[-1] == K:
        x = line[-2]
        print(f"x = {x}")
        flag = "flag{" + hashlib.sha256(str(x).encode()).hexdigest() + "}"
        print(flag)

消元x

当格能够规约出来的结果无法满足x的数量级的时候，我们需要把x消去，推导如下
$$
s_i \equiv k_i^{-1}(H_i + xr_i) \mod q
$$

$$
\therefore k_is_i \equiv H_i + xr_i \mod q
$$

取另外一组签名消去x得
$$
k_is_ir_j \equiv H_ir_j + xr_ir_j \mod q
$$

$$
k_js_jr_i \equiv H_jr_i + xr_ir_j \mod q
$$

$$
\therefore s_ir_jk_i - s_jr_ik_j \equiv H_ir_j - H_jr_i \mod q
$$

直接取$j = 0$
$$
(s_ir_0)k_i -(s_0r_i)k_0 \equiv (H_ir_0 - H_0r_i) \mod q
$$
同乘$(r_0s_i)^{-1}$得到
$$
k_i - (r_0s_i)^{-1}(r_is_0)k_0 \equiv (r_0s_i)^{-1}(H_ir_0-H_0r_i) \mod q
$$
令$A_i = (r_0s_i)^{-1}(r_is_0) \mod q$，$B = (r_0s_i)^{-1}(H_ir_0-H_0r_i) \mod q$

所以有
$$
k_i \equiv A_ik_0 +B_i \mod q
$$
构造格
$$
\begin{pmatrix}
t_1 & t_2 &…&t_n & k_0 & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots &\vdots &\vdots & \vdots\\
0 & 0 & … & q &0 & 0\\
A_1 & A_2 & … & A_n & 1 & 0\\
B_1 & B_2 & … & B_n & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_1 & k_2 & … & k_n & k_0 &K
\end{pmatrix}
$$
这样就把目标向量变小了

春秋杯夏季赛——signature

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

题目要求用admin来验签，我们只需要求出私钥，然后构造一组签名对即可

题目给了8次获得签名对的机会，我们先获取8组签名对然后格即可
$$
\begin{pmatrix}
t_1 & t_2 & … & t_8 & x & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & q & 0 & 0\\
A_1 & A_2 & … & A_8 & 1 & 0\\
B_1 & B_2 & … & B_8 & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_1 & k_2 & … & k_8 & x & K
\end{pmatrix}
$$
注意到q = 160bit，k = 128bit，x = 160bit

如果用常规的格，规约的结果大概在140bit左右，无法满足x的数量级，于是我们消去x之后再构造格
$$
\begin{pmatrix}
t_1 & t_2 & … & t_8 & k_0 & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & q & 0 & 0\\
A_1 & A_2 & … & A_8 & 1 & 0\\
B_1 & B_2 & … & B_8 & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_1 & k_2 & … & k_8 & k_0 & K
\end{pmatrix}
$$
其中$A_i = (r_0s_i)^{-1}(r_1s_0) \mod q$，$B_i = (r_0s_i)^{-1}(h_ir_0-h_0r_i) \mod q$

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
88
89
import hashlib
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
        
sh = remote("8.147.132.12",41792)
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:
            return line[-2]

k0 = get_k()
print(f"k0 = {k0}")
sh.recvuntil(b"3.get my key\n")
sh.sendlineafter(b">",b"2")
sh.recvline()
x = int(sh.recvline().strip().decode())
r = pow(g,k0,p) % q
hh = int(hashlib.sha256(b"admin").hexdigest(),16)
s = pow(k0,-1,q) * (hh + x*r) % q
sh.sendlineafter(b"r:",str(r).encode())
sh.sendlineafter(b"s:",str(s).encode())
print(sh.recvline().strip().decode())
print(sh.recvline().strip().decode())

给出k的高位

把k写成这种形式:$k = 2^{h}k_h + k_l$

直接从这式子入手
$$
(s_ir_0)k_i -(s_0r_i)k_0 \equiv (H_ir_0 - H_0r_i) \mod q
$$
此时把k的高位形式带入
$$
(s_ir_0)(2^hk_{ih} + k_{il}) -(s_0r_i)(2^hk_{0h}+k_{0l}) \equiv (H_ir_0-H_0r_i) \mod q
$$

把常数项全部放到同余号右边
$$
(s_ir_0)k_{il} - (s_0r_i)k_{0l} \equiv (H_ir_0-H_0r_i + s_0r_i2^{h}k_{0h}- s_ir_02^{h}k_{ih}) \mod q
$$
同乘$(s_ir_0)^{-1}$得
$$
k_{il} - (s_0r_i)(s_0r_i)^{-1}k_{0l} \equiv (H_ir_0-H_0r_i + s_0r_i2^hk_{0h}-s_ir_02^hk_{ih})(s_ir_0)^{-1} \mod q
$$
记$A_i \equiv (s_0r_i)(s_ir_0)^{-1} \mod q$

$B_i \equiv (H_ir_0-H_0r_i + s_0r_i2^hk_{0h}-s_ir_02^hk_{ih})(s_ir_0)^{-1} \mod q$

于是有
$$
k_{il} \equiv A_ik_{0l} + B_i \mod q
$$
造格规约出$k_{0l}$即可恢复$k_0$
$$
\begin{pmatrix}
t_1& t_2 & … & t_n & k_{0l} & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & q & 0& 0 \\
A_1 & A_2 & … & A_n & 1 & 0\\
B_1 & B_2 & … & B_n & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_{1l} & k_{2l} & … & k_{nl} & k_{0l} & K
\end{pmatrix}
$$
测试代码:

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
from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from random import randint
import hashlib
from sage.all import *

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

def sign(khigh,m,pri):
    k = int(khigh + bin(getPrime(120))[2:],2)
    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


key = DSA.generate(1024)
p, q, g = key.p, key.q, key.g
pri, pub = gen_key()
khigh = bin(getPrime(8))[2:].zfill(8)

R = []
S = []

for i in range(5):
    r,s = sign(khigh,str(i).encode(),pri)
    R.append(r)
    S.append(s)
H = [int(hashlib.sha256(str(i).encode()).hexdigest(),16) for i in range(5)]

for j in range(256):
    A = [(S[0]*R[i] * inverse((S[i]*R[0]),q)) % q for i in range(5)]
    B = [(H[i]*R[0] - H[0]*R[i] + S[0]*R[i]*2**120*j - S[i]*R[0]*2**120*j) * inverse((S[i]*R[0]),q) % q for i in range(5)]
    n = len(A)
    K = 2**120

    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]
        
    Ge[-2,-2] = 1
    Ge[-1,-1] = K

    for line in Ge.LLL():
        if line[-1] == K:
            k_low = abs(line[-2])
            k0 = j * 2**120 + k_low
            x = (k0 * S[0] - H[0]) * inverse(R[0],q) % q
            if pow(g,x,p) == pub:
                print(x)

给出k的低位

同样把k写成这种形式:$k = 2^{h}k_h + k_l$

同样从这式子入手
$$
(s_ir_0)k_i -(s_0r_i)k_0 \equiv (H_ir_0 - H_0r_i) \mod q
$$
此时把k的高位形式带入
$$
(s_ir_0)(2^hk_{ih} + k_{il}) -(s_0r_i)(2^hk_{0h}+k_{0l}) \equiv (H_ir_0-H_0r_i) \mod q
$$

把常数项全部放到同余号右边
$$
(s_ir_02^h)k_{ih} - (s_0r_i2^h)k_{0h} \equiv (H_ir_0-H_0r_i + s_0r_ik_{0l} - s_ir_0k_{il}) \mod q
$$
同乘$(s_ir_02^h)^{-1}$得
$$
k_{ih} - (s_ir_02^h)^{-1}(s_0r_i2^h)k_{0h} \equiv(H_ir_0-H_0r_i + s_0r_ik_{0l} - s_ir_0k_{il})(s_ir_02^h)^{-1} \mod q
$$
即
$$
k_{ih} - (s_ir_0)^{-1}(s_0r_i)k_{0h} \equiv (H_ir_0-H_0r_i + s_0r_ik_{0l} - s_ir_0k_{il})(s_ir_02^h)^{-1} \mod q
$$
令$A_i \equiv (s_ir_02^h)^{-1}(s_0r_i2^h) \mod q$

$B_i \equiv (H_ir_0-H_0r_i + s_0r_ik_{0l} - s_ir_0k_{il})(s_ir_02^h)^{-1} \mod q$

于是有
$$
k_{ih} \equiv A_ik_{0h} + B_i \mod q
$$
造格规约出$k_{0h}$即可恢复$k_0$
$$
\begin{pmatrix}
t_1& t_2 & … & t_n & k_{0h} & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & q & 0& 0 \\
A_1 & A_2 & … & A_n & 1 & 0\\
B_1 & B_2 & … & B_n & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_{1h} & k_{2h} & … & k_{nh} & k_{0h} & K
\end{pmatrix}
$$
测试代码:

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
from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from random import randint
import hashlib
from sage.all import *

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

def sign(klow,m,pri):
    k = int(bin(getPrime(120))[2:] + klow,2)
    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


key = DSA.generate(1024)
p, q, g = key.p, key.q, key.g
pri, pub = gen_key()
klow = bin(getPrime(8))[2:].zfill(8)

R = []
S = []

for i in range(5):
    r,s = sign(klow,str(i).encode(),pri)
    R.append(r)
    S.append(s)
H = [int(hashlib.sha256(str(i).encode()).hexdigest(),16) for i in range(5)]

for j in range(256):
    A = [((S[0]*R[i]*2**8) * inverse((S[i]*R[0]*2**8),q)) % q for i in range(5)]
    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**8),q) % q for i in range(5)]
    n = len(A)
    K = 2**120

    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]
        
    Ge[-2,-2] = 1
    Ge[-1,-1] = K

    for line in Ge.LLL():
        if line[-1] == K:
            k0_high = abs(line[-2])
            k0 = k0_high * 2**8 + j
            x = (k0 * S[0] - H[0]) * inverse(R[0],q) % q
            if pow(g,x,p) == pub:
                print(x)

给出k的高位和低位

把k写成这种形式:$k = 2^{h}k_h + k_{un}2^l + k_l$

带入到这个式子
$$
(s_ir_0)k_i -(s_0r_i)k_0 \equiv (H_ir_0 - H_0r_i) \mod q
$$
得
$$
(s_ir_0)(k_{ih}2^{h}+ k_{iun}2^l + k_{il}) - (s_0r_i)(k_{0h}2^h + k_{0un}2^l + k_{0l}) \equiv (H_ir_0-H_0r_i) \mod q
$$
把常数项全部放到同余号右边
$$
(s_ir_02^l)k_{iun} - (s_0r_i2^l)k_{0un} \equiv (H_ir_0-H_0r_i + (s_0r_i)(k_{0h}2^h + k_{0l}) - (s_ir_0)(k_{ih}2^h+k_{il})) \mod q
$$
同乘$(s_ir_02^l)^{-1}$得
$$
k_{iun} - (s_ir_02^l)^{-1}(s_0r_i2^l)k_{0un} \equiv (s_ir_02^l)^{-1}(H_ir_0-H_0r_i + (s_0r_i)(k_{0h}2^h + k_{0l}) - (s_ir_0)(k_{ih}2^h+k_{il})) \mod q
$$
记$A_i \equiv (s_ir_02^l)^{-1}(s_0r_i2^l)k_{0un} \mod q$

$B_i \equiv (s_ir_02^l)^{-1}(H_ir_0-H_0r_i + (s_0r_i)(k_{0h}2^h + k_{0l}) - (s_ir_0)(k_{ih}2^h+k_{il})) \mod q$

于是有
$$
k_{iun} \equiv A_i k_{0un} + B_i \mod q
$$
造格规约出$k_{0un}$即可恢复$k_0$
$$
\begin{pmatrix}
t_1& t_2 & … & t_n & k_{0un} & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 & 0\\
0 & q & … & 0 & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & q & 0& 0 \\
A_1 & A_2 & … & A_n & 1 & 0\\
B_1 & B_2 & … & B_n & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_{1un} & k_{2un} & … & k_{nun} & k_{0un} & K
\end{pmatrix}
$$
测试代码

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
from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from random import randint
import hashlib
from sage.all import *

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

def sign(khigh,klow,m,pri):
    k = int(khigh + bin(getPrime(120))[2:] + klow,2)
    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


key = DSA.generate(1024)
p, q, g = key.p, key.q, key.g
pri, pub = gen_key()
klow = bin(getPrime(4))[2:].zfill(4)
khigh = bin(getPrime(4))[2:].zfill(4)

R = []
S = []

for i in range(5):
    r,s = sign(khigh,klow,str(i).encode(),pri)
    R.append(r)
    S.append(s)
H = [int(hashlib.sha256(str(i).encode()).hexdigest(),16) for i in range(5)]

for high in range(16):
    for low in range(16):
        A = [((S[0]*R[i]*2**4) * inverse((S[i]*R[0]*2**4),q)) % q for i in range(5)]
        B = [(H[i]*R[0] - H[0]*R[i] + S[0]*R[i]*(high*2**124 + low) - S[i]*R[0]*(high*2**124 + low)) * inverse((S[i]*R[0]*2**4),q) % q for i in range(5)]
        n = len(A)
        K = 2**120

        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]
            
        Ge[-2,-2] = 1
        Ge[-1,-1] = K

        for line in Ge.LLL():
            if line[-1] == K:
                k0_unknown = abs(line[-2])
                k0 = high * 2**124 + k0_unknown * 2**4 + low
                x = (k0 * S[0] - H[0]) * inverse(R[0],q) % q
                if pow(g,x,p) == pub:
                    print(x)

2024RCTF——SignSystem

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
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
from random import getrandbits, randint
from Crypto.Util.number import getPrime, isPrime, inverse
from hashlib import sha1
import signal


def gen(l, n):
    q = getPrime(l)
    while True:
        t = getrandbits(n - l)
        p = t * q + 1
        if isPrime(p):
            break
    h = randint(1, p - 1)
    g = pow(h, t, p)
    x = randint(1, q)
    y = pow(g, x, p)
    return (p, q, g, y), x


def gen_ephemeral_key(k, lsb, msb):
    return msb << (k + lsb.bit_length()) | getrandbits(k) << lsb.bit_length() | lsb


def sign(pubkey, x, msg, lsb, msb):
    p, q, g, y = pubkey
    k = gen_ephemeral_key(150, lsb, msb)
    r = pow(g, k, p) % q
    Hm = int(sha1(msg).hexdigest(), 16)
    s = (Hm + x * r) * inverse(k, q) % q
    return (r, s)


def verify(pubkey, sig, msg):
    p, q, g, y = pubkey
    r, s = sig
    if not 0 < r < q or not 0 < s < q:
        return False
    w = inverse(s, q)
    Hm = int(sha1(msg).hexdigest(), 16)
    u1 = Hm * w % q
    u2 = r * w % q
    v = pow(g, u1, p) * pow(y, u2, p) % p % q
    return v == r


signal.alarm(900)
with open("flag.txt", "r") as f:
    flag = f.read()

l, n = 160, 1024
pub, x = gen(l, n)
print("your pubKey: {}".format(pub))
msb = getrandbits(8)
lsb = getrandbits(2)

menu = """
[1] sign message
[2] verify signature
"""

for i in range(20):
    print(menu)
    op = int(input(">").strip())
    if op == 1:
        msg = input("Which message to sign?: ").strip().encode()
        if msg == b"get flag":
            print("I'm afraid I can't do that.")
            break
        else:
            sig = sign(pub, x, msg, lsb, msb)
            print(f"Signature: {sig}")
    elif op == 2:
        msg = input("Which message to verify?: ").strip().encode()
        r = int(input("r:").strip())
        s = int(input("s:").strip())
        v = verify(pub, (r, s), msg)
        if v and msg == b"get flag":
            print(flag)
        else:
            print(v)
    else:
        print("Invalid option")

简单审计代码可以知道，本题的每个k的高8位和低2位是一样的。我们的目的是求出k之后再求私钥构造get flag的签名

这题常规的格也无法直接规约出x，所以还是采取消去x的方式

先把$k$写成高低位的形式:$k = k_h2^{152} + k_{un}2^2 + k_l$
$$
\because s_i \equiv k_i^{-1}(H _i+ xr_i) \mod q
$$

$$
\therefore s_ik_i \equiv H_i + xr_i \mod q
$$

同样，我们直接化简到下面这个形式
$$
(r_0s_i)k_i - (r_is_0)k_0 \equiv (H_ir_0 - H_0r_i) \mod q
$$
即
$$
(r_0s_i)(k_{ih}2^{152} + k_{iun}2^2 + k_{il}) - (r_is_0)(k_{0h}2^{152}+k_{0un}2^2 + k_{0l}) \equiv (H_ir_0 - H_0r_i) \mod q
$$
同乘$(4r_0s_i)^{-1}$得
$$
k_{iun}-(4r_0s_i)^{-1}(4r_is_0)k_{0un} \equiv (4r_0s_i)^{-1}(H_ir_0-H_0r_i +(r_is_0)(k_{0un}2^{152}+k_{0l})-(r_0s_i)(k_{iun}2^{152}+k_{il})) \mod q
$$
记$A_i \equiv (4r_0s_i)^{-1}(4r_is_0) \mod q$

$B_i \equiv (4r_0s_i)^{-1}(H_ir_0-H_0r_i +(r_is_0)(k_{0un}2^{152}+k_{0l})-(r_0s_i)(k_{iun}2^{152}+k_{il})) \mod q$

所以有
$$
k_{iun} \equiv A_ik_{0un} + B_i \mod q
$$
构造格
$$
\begin{pmatrix}
t_1 & t_2 & … & t_n & k_{0un} & 1
\end{pmatrix}
\begin{pmatrix}
q & 0 & … & 0 & 0 &0\\
0 & q & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots &\vdots \\
0 & 0 & … & q & 0 & 0 \\
A_1 & A_2 & … & A_n & 1 & 0 \\
B_1 & B_2 & … & B_n & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
k_{1un} & k_{2un} & … & k_{nun} & k_{0un} & K
\end{pmatrix}
$$
这里k的高位和低位都是需要爆破的，求出$k_{0un}$之后即可恢复k，从而求私钥

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
88
89
90
91
92
93
from random import choices
from hashlib import sha1
from Crypto.Util.number import *
import string
from pwn import *
from sage.all import *
from tqdm import *
import gmpy2
import time

table = string.ascii_lowercase

host = ''                  #ip地址
port =                     #端口

sh = remote(host,port)                  #建立连接  
sh.recvuntil(b"your pubKey:")

pub = eval(sh.recvline().decode().strip())

p,q,g,y = pub

R = []
S = []
H = []
for i in range(19):
    sh.recvuntil(b">")
    sh.sendline(b"1")
    sh.recvuntil(b"Which message to sign?: ")
    m = "".join(choices(table,k=16))
    msg = m.encode()
    h = bytes_to_long(sha1(msg).digest())
    sh.sendline(msg)
    sh.recvuntil(b"Signature:")
    data1 = eval(sh.recvline().decode().strip())
    r,s = data1
    S.append(s)
    R.append(r)
    H.append(h)


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

def sign(pubkey, x, msg, k):
    p, q, g, y = pubkey
    r = pow(g, k, p) % q
    Hm = int(sha1(msg).hexdigest(), 16)
    s = (Hm + x * r) * inverse(k, q) % q
    return (r, s)

for high in trange(256):
    for low in range(4):
        lowbit = low.bit_length()
        A = []
        B = []
        tt = 2**lowbit
        for i in range(1,len(R)):
            a = tt*R[i]*s0 * gmpy2.invert(tt*r0*S[i],q) % q
            b = (r0*H[i] - R[i]*h0 + R[i]*s0*(high*2**152+low) - r0*S[i]*(high*2**152+low)) * gmpy2.invert(tt*r0*S[i],q) % q
            A.append(a)
            B.append(b)
        
        n = len(A)
        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**150
        Ge[-2,-2] = 1
        Ge[-1,-1] = K
        for line in Ge.BKZ(block_size=30):
            if abs(line[-1]) == K:
                k0_unknown = line[-2]
                k0 = high*2**152 + k0_unknown*tt + low
                d = (k0 * s0 - h0) * gmpy2.invert(r0,q) % q
                if pow(g,d,p) == y:
                    print(1)
                    sig = sign(pub,d,b"get flag",k0)
                    r,s = sig
                    sh.recvuntil(b">")
                    sh.sendline(b"2")
                    sh.recvuntil(b"Which message to verify?: ")
                    sh.sendline(b"get flag")
                    sh.sendlineafter(b"r:",str(r).encode())
                    sh.sendlineafter(b"s:",str(s).encode())
                    print(sh.recvline())

# RCTF{Ev3ry_fighter_h@s_their_signature_style}

ECDSA

签名过程

  1. 首先选择一条椭圆曲线$E_p(a,b)$，和基点$G$
  2. 选择私钥$d,(d<n)$，$n$是基点$G$的阶
  3. 利用基点计算公钥$Q = dG$，$Q$表示为$(Q_X,Q_Y)$并公开$Q$
  4. 选择一个随机数$k,(k<n)$，计算$R = kG$，$R$表示为$(R_X,R_Y)$
  5. 计算$r \equiv R_X \mod n$，如果$r = 0$，则选取另一个$k$并重新计算
  6. 计算明文$m$的哈希值，记为$H = hash(m)$
  7. 计算$s \equiv k^{-1}(H+rd)\mod n$
  8. 如果$s=0$，则选取另外一个$k$并重新计算
  9. 输出签名$(r,s)$

验证过程

  1. 计算整数$u_1 = s^{-1}×H \mod n$
  2. 计算整数$u_2 =s^{-1}×r \mod n$
  3. 计算点$R = u_1G+u_2Q \mod n$

证明验证过程的正确性

$\because R = u_1G + u_2Q \mod n \longrightarrow R = u_1G+u_2dG = (u_1+u_2d) \mod n$

把$u_1,u_2$替换掉

$\therefore R = (s^{-1}H+s^{-1}rd)G \mod n$

$\therefore R = s^{-1}(H+rd)G \mod n$

结合$s \equiv k ^{-1}(H+rd) \mod n$，我们能得到$s^{-1} \equiv k(H+rd)^{-1} \mod n$

则$R = k(H+rd)^{-1}×(H+rd) \mod n = kG$

与签名过程的$R=kG$一致

攻击

这类题做的少，只接触了k复用

如果使用同一个k，危险性很大，在此情况下，很容易反推出$d$

我们需要两个哈希值$H_1,H_2$，两组签名$(r_1,s_1),(r_2,s_2)$，还有椭圆曲线的参数

因为$R \equiv kG$，$r = R_x \mod n$，如果$k$一样，则$r_1 = r_2$

$\because s \equiv k^{-1}(H+rd)$，$\therefore (s_1-s_2) \equiv k^{-1}(H_1-H_2) \mod n$

两边同乘$k$得$k(s_1-s_2) \equiv H_1-H_2 \mod n$

$\therefore k \equiv (s_1-s_2)^{-1}(H_1-H_2) \mod n$

求出k之后，根据$s \equiv k^{-1}(H+rd) \longrightarrow ks \equiv H+rd \longrightarrow d \equiv (ks - H)r^{-1}\mod n$

例题

(复用k)2024蓝桥杯密码3

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
import ecdsa
import random

def ecdsa_test(dA,k):

    sk = ecdsa.SigningKey.from_secret_exponent(
        secexp=dA,
        curve=ecdsa.SECP256k1
    )
    sig1 = sk.sign(data=b'Hi.', k=k).hex()
    sig2 = sk.sign(data=b'hello.', k=k).hex()
    
    r1 = int(sig1[:64], 16)
    s1 = int(sig1[64:], 16)
    s2 = int(sig2[64:], 16)
    return r1,s1,s2

if __name__ == '__main__':
    n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
    a = random.randint(0,n)
    flag = 'flag{' + str(a) + "}"
    b = random.randint(0,n)
    print(ecdsa_test(a,b))

# (4690192503304946823926998585663150874421527890534303129755098666293734606680, 111157363347893999914897601390136910031659525525419989250638426589503279490788, 74486305819584508240056247318325239805160339288252987178597122489325719901254)

首先阅读代码要知道这里的$a,b$分别就是私钥$d$和$k$

曲线SECP256k1的参数是公开的，即
$$
y^2 \equiv x^3 + 7 \mod 115792089237316195423570985008687907852837564279074904382605163141518161494337
$$
也就是$a = 0,b = 7$

$p = 115792089237316195423570985008687907852837564279074904382605163141518161494337$

题目考点是k的复用，这里比较关键的是知道下sk.sign()用的哈希函数是sha1，然后用上面k复用的思路即可得解

exp.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
import ecdsa
from Crypto.Util.number import *
import gmpy2
from hashlib import *

p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
a = 0
b = 7
order = ecdsa.SECP256k1.generator.order()

print(order == p)

m1 = b"Hi."
m2 = b"hello."
r1,s1,s2 = (4690192503304946823926998585663150874421527890534303129755098666293734606680, 111157363347893999914897601390136910031659525525419989250638426589503279490788, 74486305819584508240056247318325239805160339288252987178597122489325719901254)

h1 = bytes_to_long(sha1(m1).digest())
h2 = bytes_to_long(sha1(m2).digest())

k = gmpy2.invert((s1-s2),p)*(h1-h2) % p
r_ = gmpy2.invert(r1,p)

d = ((k * s1) - h1)*r_ % p

flag = "flag{" + str(d) + "}"
print(flag)
# flag{40355055231406097504270940121798355439363616832290875140843417522164091270174}
-------------已经到底啦！-------------