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演算法