Cryptopals Challenge 43

本文最后更新于:4 年前

Cryptopals Challenge 43 的题解,很简单
DSA key recovery from nonce

题意

已知

1
2
3
4
5
6
7
8
m = For those that envy a MC it can be hazardous to your health
So be friendly, a matter of life and death, just like a etch-a-sketch
p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291
r0 = 548099063082341131477253921760299949438196259240
s = 857042759984254168557880549501802188789837994940
k = 0-65536 的一个数

求 x(即 private key)

DSA 复习

算法中应用了下述参数:

p:L bits 长的素数。L 是 64 的倍数,范围是 512 到 1024;

q:p - 1 的 160bits 的素因子;

g: $g =h^{\frac{p-1}{q}} mod \,p$,$h$ 满足 $h < p - 1$, $h^{\frac{p-1}{q}} mod \,p>1$;

x:$x < q$,x 为私钥;

y:$y = g^{x} mod p$ ,$( p, q, g, y )$ 为公钥;

H( x ):One-Way Hash 函数。DSS ( FIPS186-4 )中选用 SHA-1 或者 SHA-2( Secure Hash Algorithm 系列中的 2 个较新版本,其中 SHA-2 有 4 个,SHA-224,SHA-256,SHA-384,SHA-512,最原始的 SHA 已经不再被使用)。

p, q, g 可由一组用户共享,但在实际应用中,使用公共模数可能会带来一定的威胁。签名及验证协议如下:

  1. P 产生随机数 k,k < q;

  2. P 计算

    r = $ g^{k}\,mod \,p \,mod\,q$

    $s = ( k^{-1} (H(m) + xr))\,mod\,q$

    签名结果是( r, s )。

  3. 验证时计算

    $w = s^{-1}mod q$

    $u_1 = ( H( m ) * w )\,mod\,q$

    $u_2 = ( r * w )\,mod\,q$

    $v = (( g^{u_1} * y^{u_2} )\,mod\,p )\,mod\,q$

    若 $v = r$,则认为签名有效。

推导 x 的公式

若 $k$ 已知,则

$sk = (H(m)+xr)\,mod\,q$

$xr = (sk - H(m))\,mod\,q$

$x = \frac{sk - H(m)}{r}\,mod\,q$

解题过程

题中给出了 k 的范围,暴力一下就好了。对于每个 k,先求出对应的 r,若 r 等于题中给出的 r0,则证明 k 就是对的。得到了 k,可求 x,即 private key。

方法 1

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
from Crypto.Hash import SHA
from gmpy2 import *
from time import *
clock()

anSHA1 = '0954edd5e0afe5542a4adf012611a91912a3ec16'
print '[+]Cal SHA-1(M)...'
sha = SHA.new()
sha.update('''For those that envy a MC it can be hazardous to your health
So be friendly, a matter of life and death, just like a etch-a-sketch
''')
H = sha.hexdigest()
print ' [-]SHA-1(M) is:', H
print ' [-]Done!'

p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291
r0 = 548099063082341131477253921760299949438196259240
s = 857042759984254168557880549501802188789837994940

print '[+]Searching key...'
for k in xrange(65537):
r = pow(g, k, p) % q
if r == r0:
print ' [-]key Found!'
print ' [-]key is:', k

print ' [-]Cal x...'
x = (s*k - int(H,16)) * invert(r,q) % q
print ' [-]x is:', x

print ' [+]Cal SHA-1(x)...'
sha = SHA.new()
sha.update('%x' %(x))
H = sha.hexdigest()
print ' [-]SHA-1(x) is:', H
print ' [-]Done!'

print '[+]SHA-1(x) == %s:' %anSHA1, H == anSHA1
assert H == anSHA1
break

print '[!]All Done!'
print '[!]Timer:', round(clock()), 's'

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[+]Cal SHA-1(M)...
[-]SHA-1(M) is: d2d0714f014a9784047eaeccf956520045c45265
[-]Done!
[+]Searching key...
[-]key Found!
[-]key is: 16575
[-]Cal x...
[-]x is: 125489817134406768603130881762531825565433175625
[+]Cal SHA-1(x)...
[-]SHA-1(x) is: 0954edd5e0afe5542a4adf012611a91912a3ec16
[-]Done!
[+]SHA-1(x) == 0954edd5e0afe5542a4adf012611a91912a3ec16: True
[!]All Done!
[!]Timer: 5.0 s

方法 2

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
from Crypto.Hash import SHA
from gmpy2 import *
from time import *
clock()

ansSHA1 = '0954edd5e0afe5542a4adf012611a91912a3ec16'
print '[+]Cal SHA-1(M)...'
sha = SHA.new()
sha.update('''For those that envy a MC it can be hazardous to your health
So be friendly, a matter of life and death, just like a etch-a-sketch
''')
ansH = int(sha.hexdigest(),16)
print ' [-]SHA-1(M) is:', ansH
print ' [-]Done!'

p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291
r = 548099063082341131477253921760299949438196259240
s = 857042759984254168557880549501802188789837994940

print '[+]Searching key...'

for k in xrange(65537):
x = (s*k - ansH) * invert(r,q) % q
sha = SHA.new()
sha.update('%x' %(x))
H = sha.hexdigest()

if H == ansSHA1:
r = pow(g, k, p) % q
print ' [-]key Found!'
print ' [-]key is:', k
print ' [-]x is:', x
print ' [+]Cal SHA-1(x)...'
print ' [-]SHA-1(x) is:', H
print ' [-]Done!'
print '[+]SHA-1(x) == %s:' %ansSHA1, H == ansSHA1
assert H == ansSHA1
break

print '[!]All Done!'
print '[!]Timer:', round(clock()), 's'

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[+]Cal SHA-1(M)...
[-]SHA-1(M) is: 1203536487446634476431084512413493461057142018661
[-]Done!
[+]Searching key...
[-]key Found!
[-]key is: 16575
[-]x is: 125489817134406768603130881762531825565433175625
[+]Cal SHA-1(x)...
[-]SHA-1(x) is: 0954edd5e0afe5542a4adf012611a91912a3ec16
[-]Done!
[+]SHA-1(x) == 0954edd5e0afe5542a4adf012611a91912a3ec16: True
[!]All Done!
[!]Timer: 0.0 s


这个更快

坑点

计算明文 Hash 的时候,注意最后还有一个换行,,,,,,

来呀快活呀