DSA签名

发表于 更新于 阅读次数： 本文字数： 11k 阅读时长 ≈ 20 分钟

基本流程

生成密钥

  1. 选择一个合适的哈希函数，目前一般选择 SHA1，当前也可以选择强度更高的哈希函数 H。
  2. ^选择密钥的长度^ L 和 N，这两个值决定了签名的安全程度。在最初的 DSS（Digital Signature Standard ）中建议 L 必须为 64 的倍数，并且512≤L≤1024 ，当然，也可以更大。N 必须大小必须不大于哈希函数 H 输出的长度。
  3. 选择 N 比特的素数 q。
  4. 选择 L 比特的素数 p，使得 p-1 是 q 的倍数。
  5. 选择满足 g^k^≡1modp的最小正整数 k 为 q 的 g，即在模 p 的背景下，ord(g)=q 的 g。即 g 在模 p 的意义下，其指数次幂可以生成具有 q 个元素的子群。这里，我们可以通过计算g=h$$\frac{p-1}{q}$$modp 来得到 g，其中1<h<p−1 。
  6. 选择私钥 x，0<x<q ，计算y≡g^x^modp 。

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

进行签名

  1. 选择随机整数数 k 作为临时密钥，0<k<q0<k<q 。
  2. 计算r≡(g^k^modp)modq
  3. 计算s≡(H(m)+xr)k^−1^modq

签名结果为 (r,s)。H(m)为明文的哈希值。

验证过程

  1. 计算辅助值，w=s^−1^modq
  2. 计算辅助值，u1=H(m)wmodq
  3. 计算辅助值，u2=rwmodq
  4. 计算v=(g^u1^y^u2^modp)modq
  5. 如果 v 与 r 相等，则校验成功。

题型总结

1，已知随机密钥k

已知k时，我们就可以根据s≡(H(m)+xr)k^−1^modq 推出x≡r^−1^(ks−H(m))modq，一般这类题的H都会给出。

2，多个签名使用相同密钥k

举个栗子[]

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
#!/usr/bin/env python
from Crypto.Util.number import *
from hashlib import sha512,md5
from os import urandom
import random

def hash(message):
	return int(sha512(message).hexdigest(), 16)

def key_gen():
	q = getPrime(256)
	while True:
		p = random.getrandbits(2816)*q + 1
		if isPrime(p):
			print(p.bit_length())
			break
	while True:
		g = pow(random.randrange(1, p-1), (p-1)/q, p)
		if g != 1:
			break
	x = random.randrange(1, q)
	y = pow(g, x, p)
	pubkey = (p, q, g, y)
	privkey = x
	return pubkey, privkey

def sign(message, pubkey, privkey):
	p, q, g, y = pubkey
	x = privkey
	k = pow(y, x, g) * random.randrange(1, 512) % q
	r = pow(g, k, p) % q
	s = inverse(k, q) * (hash(message) + x * r) % q
	return r, s

def verify(message, signature, pubkey):
	p, q, g, y = pubkey
	r, s = signature
	if not (0 < r < q) or not (0 < s < q):
		return False
	w = inverse(s, q)
	u1 = (hash(message) * w) % q
	u2 = (r * w) % q
	v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
	return v == r

pubkey, privkey = key_gen()
print(pubkey)

message1 = urandom(16).encode('hex')
signature1 = sign(message1, pubkey, privkey)
print(message1,signature1)
print(verify(message1, signature1, pubkey))

message2 = urandom(16).encode('hex')
signature2 = sign(message2, pubkey, privkey)
print(message2,signature2)
print(verify(message2, signature2, pubkey))

flag = 'flag{'+md5(long_to_bytes(privkey)).hexdigest()+'}'


显然是一个经典的复用k的情况，但是做了一点小小的升级

注意看这一段

1
2
3
4
5
6
7
def sign(message, pubkey, privkey):
	p, q, g, y = pubkey
	x = privkey
	k = pow(y, x, g) * random.randrange(1, 512) % q
	r = pow(g, k, p) % q
	s = inverse(k, q) * (hash(message) + x * r) % q
	return r, s

原版dsa的sign中k = pow(y, x, g) % q

而此题k = pow(y, x, g) * random.randrange(1, 512) % q

乘了一个随机数。(其实可以直接穷举爆出来的)

那么来一点小小的推导吧

两组数据，则有两个表达式，如下
k1s1 = (H(M1)+xr1) mod q
k2s2 = (H(M2)+xr2) mod q
同时也有
k1 = (y^x^ mod g * random1) mod q
k2 = (y^x^ mod g * random2) mod q
k1，k2表达式，将随机数移到左边
k1 * random1^-1^ = （y^x^ mod g) mod q
k2 * random2^-1^ = （y^x^ mod g) mod q
所以得到：k1 * random1^-1^ = k2 * random2^-1^
此式子缺乏x，需要引入含有x的表达式，ks = (H(M)+xr) mod q，两边同时乘以s1s2
k1 * random1^-1^ * s1s2 = k2 * random2^-1^ * s1s2
式子也等价于
H(M1)random1^-1^ s2 + xr1random1^-1^ * s2 = H(M2)random2^-1^ s1 + xr2random2^-1^ * s1
再化简
H(M1)random1^-1^ s2 * random2 + xr1random1^-1^ * s2 * random2 = H(M2) * s1 + xr2s1
移项
H(M1)random1^-1^ s2 * random2 - H(M2) * s1 = xr2s1 - xr1random1^-1^ * s2 * random2
x = H(M1)random1^-1^ s2 * random2 - H(M2) * s1 / (r2s1 - r1random1^-1^ * s2 * random2)

除法改成乘法的逆即可

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

pubkey = (3297226463037324458008837284498963372649038889390685051849680175016505646001761220109858921624266044035133134135402561235635833428206886888308027772353030767400921078346868377298401213812053250316002033941692272192644613252296579884516731560436501073253924457646558698855484781747029397755111633297587215976579633451933658235385386539518006570069653575146060016811911140614606471930327341368582979836042585406811352236326065292636484550807213756482153084427714549694264685695977531537425682212155553568848666088576932888234659355213664909753781753917401161977762663658097504411914908081677033980915039079517766159760522261279115347385813009437510156898969769563687869495721977265444799585634019880951532080217960456901788918439265788169910062822889580199366417455186595489973000351770200485095008494228829300145039695936946379585625051402553034971207474762463147744467360158847593356030745194143276254949463650698210515569533L,82302835442112137125891403368151249910268706824854786126600390413622302196443L,1156233264299340971106498371495495695225880592354374034142195518472540521911699506391311324676590685365234887170345722135060009885002334748836477169806166169806180231794918961214520698361874839110454610266388341977984902756569838594616255112661600466818870137432772800368859461445854700956291885576855069405183771903076277144927769029433730710613058788277691211698675287829143272152835171859480781061918556840079857761203012054552142555673071865310355331986288606422711525790877591376770834180618492794265362178603111236615495225612101250344421932588038244804199229449738675082560512062564365473035097263889257937140778993389305893378514344032352806521972367991027459721160744835688761657797398841523104074451793557924512992305640697344011520550723893828185707635141404445213445935586965289450282024222064488965878769991566367115153619761583843561579531705057955933288008556165952066173304891391375100346312776539530448611005L,290999623787731812697719691852061290246619413463636312382146969900546384514710782843153962704851916091601679028830866176332331519515156301401537173069908181509028464322647352256632424684809349121024262597006913707483811117644197481959053785475083406472583099140506505071300193356002443007750220524932219191932969202270343323955035291396808472686684787610559114702054784699365490860392737061056233160308943296478540798353134878937088336672928162894332961762277559345860479916248086821117811990391025187125193074059001086441305977133252774698996653122297123447837449168657347308016270030881395674066421144002959751936839166935726200833785132736328859710351871352567511516142170956091885352178579302299634322254818383978585773136692588922976043617337904545396146755609284163743476297772686548475170197605412847689587171522453229055932712714154869989454808561458852031769119489235598402066924082778376081494632258448434048562053L)
p,q,g,y = pubkey

message1xx = (b'0234e7971889def7e60348f77db94b7a',(10859236269959765735236393779936305217305574331839234502190226708929991582386L,13707557323895695260471053137828523837745895683218331343360027380310980108819L))

message1 = b'0234e7971889def7e60348f77db94b7a'
r1 = 10859236269959765735236393779936305217305574331839234502190226708929991582386L
s1 = 13707557323895695260471053137828523837745895683218331343360027380310980108819L

message2 = b'16c5ac270b72f70319657b4410d985d4'
r2 = 41960642246379067640524709416001536058292817319109764317369777224426218746518L
s2 = 74676725322515593502346275468843411563746982149373670021082686341369076719088L

def hash(message):
        return int(sha512(message).hexdigest(), 16)

def sign(message, pubkey, privkey,randoms):
        p, q, g, y = pubkey
        x = privkey
        k = pow(y,x,g) * randoms
        r = pow(g,k,p)%q
        s = inverse(k,q)*(hash(message)+x*r)%q
        return r,s

H1 = hash(message1)
H2 = hash(message2)

#x = H(M1)*random1^-1 *s2 * random2 - H(M2) * s1 / (r2*s1 - r1*random1^-1 * s2 * random2)
print "Now attack start..."
for random2 in range(1,512):
    print "Now random2 is:%d\n" % random2
    for random1 in range(1,512):
        print "Now random1 is:%d" %random1
        random1_inverse = inverse(random1,q)
        x = (H1*random1_inverse*s2*random2-H2*s1) * inverse(r2*s1-r1*random1_inverse*s2*random2,q)%q
        if sign(message1,pubkey,x,random1) == message1xx[1]:
            flag = 'flag{'+md5(long_to_bytes(x)).hexdigest()+'}'
            print flag
            print "Success!"
            exit()

虽然但是随机数好像要爆蛮久……

3，不同次签名使用的k存在线性关系

找了半天没看到合适的例题，只有拿Dexter佬的水一水捏

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

附上丑丑的推导

c572b534fc3cd26be69322c1fcf23c68.png

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

还有的题型遇到了再补上叭……