标题: DSA相关的趣味数学题(1)

https://scz.617.cn/misc/201607011637.txt

DSA算法简要描述:

--------------------------------------------------------------------------
Digital Signature Algorithm
http://en.wikipedia.org/wiki/Digital_Signature_Algorithm
--------------------------------------------------------------------------
p

    L-bits的素数，L是64的倍数，过去的范围[512,1024]，现在推荐2048或3072

    2^(L-1) < p < 2^L

    p-1至少包含一个大素因子，以抵御Pohlig-Hellman算法

q

    p-1的素因子

    q的位数必须小于等于HASH值的位数

g=h^((p-1)/q) mod p

    1 < h < p-1
    h^((p-1)/q) mod p > 1

    g是满足"g^q mod p=1"的最小正整数，ord(g)=q。

    由g生成Zp*中唯一的q阶循环子群

x

    0 < x < q
    (p,q,g,x)是私钥

y

    y=g^x mod p
    (p,q,g,y)是公钥
--------------------------------------------------------------------------

签名过程:

--------------------------------------------------------------------------
a.

产生随机数0<k<q

b.

r=(g^k mod p) mod q
s=k^(-1)*(HASH(m)+x*r) mod q

c.

签名是(r,s)，发送(m,r,s)给对方
--------------------------------------------------------------------------

已知某DSA签名实现在产生随机数k时存在BUG，导致攻击者获取到两组(m,r,s)，它们
使用同一个k值:

hashtype    = sha1

q           = 0x843437e860962d85d17d6ee4dd2c43bc4aec07a5

m1          = 0x3132333435363738
r1          = 0x4d91a491d95e4eef4196a583cd282ca0e625f36d
s1          = 0x3639b47678abf7545397fc9a1af108537fd1dfac

m2          = 0x49276c6c206265206261636b2e
r2          = 0x4d91a491d95e4eef4196a583cd282ca0e625f36d
s2          = 0x314c044409a94f4961340212b42ade005fb27b0a

该BUG最终导致私钥x泄露。

提问:

x           = ?