DSA签名算法常见攻击方法

基本原理

密钥生成

\[1. N比特的素数q（N不大于哈希函数H的长度，一般为160或256）\\2. L比特的素数p，p-1是q的倍数（L为64的倍数，一般大于512）\\3.g=h^{\frac{p-1}{q}} \bmod p，其中1<h<p-1，使得g^k \equiv 1 \bmod p的最小正整数k为q，即g的指数幂在模p下有q个元素\\4.选择私钥x，0<x<q，计算y \equiv g^x \bmod p\]

公钥为（p，q，g，y），私钥为（x）

签名

\[1.选择随机整数k作为临时密钥，0<k<q\\2.计算r\equiv (g^k \bmod p) \bmod q\\3.计算s\equiv (H(m)+xr)k^{-1} \bmod q\]

签名结果为（r，s）

验证

\[1.计算辅助值，w=s^{-1} \bmod q\\2.计算辅助值，u_1=H(m)w \bmod q\\3.计算辅助值，u_2=rw \bmod q\\4.计算v=(g^{u_1}y^{u_2} \bmod p) \bmod q\]

如果v==r，则校验成功

验证原理

\[满足g^k \equiv 1 \bmod p的最小正整数k为q，因此，g^q \equiv 1 \bmod p，对于任意x，有：g^x \equiv g^{x \bmod q} \bmod p\\因为s\equiv (H(m)+xr)k^{-1} \bmod q且w=s^{-1} \bmod q\\因此k \equiv s^{-1}(H(m)+xr) \equiv H(m)w+xrw \bmod q\\v=(g^{u_1}y^{u_2} \bmod p) \bmod q=g^{u_1}g^{xu_2} \equiv g^{H(m)w}g^{xrw} \equiv g^{H(m)w+xrw} \equiv g^k=r\]

常用命令

1 2 3 4

openssl dgst -sha1 -sign dsa_private.pem -out sign.bin message.txt #签名 openssl sha1 -verify dsa_public.pem -signature sign.bin message.txt #验证 openssl dsa -in dsa_public.pem -text -noout -pubin #读取公钥 openssl asn1parse -inform der -in packet4/sign4.bin #读取签名r和s的值

针对k相关攻击

k已知

\[s\equiv (H(m)+xr)k^{-1} \bmod q\\求得x \equiv r^{-1}(ks-H(m)) \bmod q\]

两次签名的r值相同，表示使用了相同的k

\[s_1\equiv (H(m_1)+xr)k^{-1} \bmod q，得：s_1k \equiv H(m_1)+xr\\同理得到：s_2k \equiv H(m_2)+xr\\由于xr相同，两式相减，得：k(s_1-s_2) \equiv H(m_1)-H(m_2) \bmod q\]

求得k，进而求得x