标题: 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)+xr) 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 = ?