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∗yu2mod p)mod q
当
v
=
=
r
v==r
v==r时，校验成功
CTF应用
一般的CTF题考察DSA算法，是求私钥
x
x
x
下面的例题来自CTF-wiki
根据
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
签名消息为
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算法
