Skip to content

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