Cryptopals Challenge 44

Cryptopals Challenge 44 的题解，很简单
DSA nonce recovery from repeated nonce

题意

已知

msg * 11
s * 11
r * 1
m * 11（这个是 msg 的 SHA）
p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291

求 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 可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。签名及验证协议如下：

P 产生随机数 k，k < q；
P 计算

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

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

签名结果是 (r, s)。
验证时计算

$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 的公式

首先由题意

$p_1=p_2=p$

$q_1=q_2=q$

$y_1=y_2$

$\therefore x_1=x_2=x$

若 k 是重复利用的，即：

$k_1=k_2=k$

则由 r 的公式可知

$r_1 = r_2 = r$

对于 s 的公式可知

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

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

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

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

即

$\therefore k=\frac{H(m_1)-H(m_2)}{s_1-s_2}\ mod\ q$

解题过程

将 txt 中的 data 分组，r 相同的在一组。txt 中有很多组 r 是相同的，而有一组 r 是相同的就可以解出 x 了

代码

import re
from gmpy2 import *
from time import *
from Crypto.Hash import SHA
clock()

with open('44.txt','r') as fp:
    data = re.findall('msg: (.+)\ns: (.+)\nr: (.+)\nm: (.+)', fp.read())
    r = [i[2] for i in data]
    
p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
anSHA1 = 'ca8f6f7c66fa362d40760d135b763eb8527d3d52'
for ri in set(r):
    same_k = filter(lambda x : ri==x[2], data)
    if len(same_k)==2:
        print '[+]Found Common r!'
        m1 = int(same_k[0][0].encode('hex'),16)
        m2 = int(same_k[1][0].encode('hex'),16)
        s1 = int(same_k[0][1])
        s2 = int(same_k[1][1])
        H1 = int(same_k[0][3],16)
        H2 = int(same_k[1][3],16)
        
        print '  [-]Cal k...'
        k = ((H1 - H2) * invert(s1-s2,q))%q
        print '  [-]k is:', k
        r = int(same_k[0][2])

        print '  [-]Cal x...'
        x = (s1*k - H1) * 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 '[+]SHA-1(x) == %s:' %anSHA1, H == anSHA1
        assert H == anSHA1        
        break

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

结果

[+]Found Common r!
  [-]Cal k...
  [-]k is: 24198682723248112355954353902117453120
  [-]Cal x...
  [-]x is: 1379952329417023174824742221952501647027600451162
    [+]Cal SHA-1(x)...
      [-]SHA-1(x) is: ca8f6f7c66fa362d40760d135b763eb8527d3d52
[+]SHA-1(x) == ca8f6f7c66fa362d40760d135b763eb8527d3d52: True
[!]All Done!
[!]Timer: 0.0 s