DSA

本文主要叙述在CTF中的DSA，根据我自己的理解重述一遍CTF-wiki对DSA的描述

公私钥的生成

• 选择一个哈希函数 H ( ) H() H()；一般选作SHA1

• 选择比特数为 64 64 64​的倍数的素数 p p p​​，且位数处于 512 512 512​到 1024 1024 1024​之间

• 选择 160 b i t s 160bits 160bits​​的素数 q q q​（这里对 q q q的大小限制准确来说是不大于哈希函数H输出的长度），满足 q q q是 p − 1 p-1 p−1​的素因子

总之 ( p , q ) (p,q) (p,q)的大小一般是 ( 1024 , 160 ) , ( 2048 , 224 ) , ( 2048 , 256 ) (1024,160),(2048,224),(2048,256) (1024,160),(2048,224),(2048,256)以及 ( 3072 , 256 ) (3072,256) (3072,256)​，单位比特

• 选择满足 g ≡ h p − 1 q ( m o d   p ) g\equiv h^{\frac{p-1}{q}}(mod~p) g≡hqp−1​(mod p)​；其中 1 < h < p − 1 1<h<p-1 1<h<p−1​​

• 选择私钥 x x x， 0 < x < q 0<x<q 0<x<q，计算 y ≡ g x ( m o d   p ) y\equiv g^x(mod~p) y≡gx(mod p)

公钥为 ( p , q , g , y ) (p,q,g,y) (p,q,g,y)

私钥为 ( x ) (x) (x)

数字签名

选择随机整数 k k k作为临时密钥， 0 < k < q 0<k<q 0<k<q

r ≡ ( g k   m o d   p ) m o d   q r\equiv (g^k~mod~p)mod~q r≡(gk mod p)mod q

s ≡ ( H ( m ) + x ∗ r ) ∗ k − 1 ( m o d   q ) s\equiv (H(m)+x*r)*k^{-1}(mod~q) s≡(H(m)+x∗r)∗k−1(mod q)​

签名结果为 ( r , s ) (r,s) (r,s)

验证

w ≡ s − 1 ( m o d   q ) w\equiv s^{-1}(mod~q) w≡s−1(mod q)

u 1 ≡ H ( m ) ∗ w ( m o d   q ) u_1\equiv H(m)*w(mod~q) u1​≡H(m)∗w(mod q)

u 2 ≡ r ∗ w ( m o d   q ) u_2\equiv r*w(mod~q) u2​≡r∗w(mod q)

v ≡ ( g u 1 ∗ y u 2 m o d   p ) m o d   q v\equiv (g^{u_1}*y^{u_2}mod~p)mod~q v≡(gu1​∗yu2​mod p)mod q

当 v = = r v==r v==r时，校验成功

CTF应用

一般的CTF题考察DSA算法，是求私钥 x x x

下面的例题来自CTF-wiki

• 已知随机密钥 k k k

根据 s ≡ ( H ( m ) + x ∗ r ) ∗ k − 1 ( m o d   q ) s\equiv (H(m)+x*r)*k^{-1}(mod~q) s≡(H(m)+x∗r)∗k−1(mod q)

解得 x ≡ r − 1 ∗ ( k ∗ s − H ( m ) ) ( m o d   q ) x\equiv r^{-1}*(k*s-H(m))(mod~q) x≡r−1∗(k∗s−H(m))(mod q)

• k k k共享

在两次签名中共享 k k k

签名消息为 m 1 , m 2 m_1,m_2 m1​,m2​

s 1 ≡ ( H ( m 1 ) + x ∗ r ) ∗ k − 1 ( m o d   q ) s_1\equiv(H(m_1)+x*r)*k^{-1}(mod~q) s1​≡(H(m1​)+x∗r)∗k−1(mod q)

s 2 ≡ ( H ( m 2 ) + x ∗ r ) ∗ k − 1 ( m o d   q ) s_2\equiv(H(m_2)+x*r)*k^{-1}(mod~q) s2​≡(H(m2​)+x∗r)∗k−1(mod q)​

推导

s 1 ∗ k ≡ H ( m 1 ) + x ∗ r ( m o d   q ) s_1*k\equiv H(m_1)+x*r(mod~q) s1​∗k≡H(m1​)+x∗r(mod q)

s 2 ∗ k ≡ H ( m 2 ) + x ∗ r ( m o d   q ) s_2*k\equiv H(m_2)+x*r(mod~q) s2​∗k≡H(m2​)+x∗r(mod q)

相减得到

k ∗ ( s 1 − s 2 ) ≡ H ( m 1 ) − H ( m 2 ) ( m o d   q ) k*(s_1-s_2)\equiv H(m_1)-H(m_2)(mod~q) k∗(s1​−s2​)≡H(m1​)−H(m2​)(mod q)

求逆元

k ≡ ( H ( m 1 ) − H ( m 2 ) ) ∗ ( s 1 − s 2 ) − 1 ( m o d   q ) k\equiv (H(m_1)-H(m_2))*(s_1-s_2)^{-1}(mod~q) k≡(H(m1​)−H(m2​))∗(s1​−s2​)−1(mod q)​

已知 k k k之后重复已知密钥 k k k的解密过程即可

参考文章

DSA - CTF Wiki (ctf-wiki.org)

(11条消息) DSA加密算法以及破解_happend的博客-CSDN博客_dsa加密算法

(11条消息) DSA-数据签名算法（理论）_aaqian1的博客-CSDN博客_dsa算法