DSA

Digital Signature Standard (DSS) 數位憑證標準，而有一個 DSA 演算法來完成憑證。

每一次憑證傳送三個參數 $(r, s, M)$，利用私用金鑰進行加密。讓對方使用公鑰進行驗證。

• $r = (g^k \mod p) \mod q$
• $s = k^{-1}(SHA(M) + x \times r) \mod q$

give receiver $(r, s, M)$, we have random (one-time) $k$ & private key $x$

每一次簽名時，最好使用隨機亂數 $k$ 作為簽章用途，隨用即棄，若發生重複使用，將會發生被攻擊，被攻擊者拿到私鑰後，攻擊者就能進行偽裝。

Attack

if reused $k$

如果重複使用隨機變數 $k$，可以藉由夾擊的方式得到，雖然不知道加密的隨機亂數 $k$ 究竟是什麼，藉由夾擊可以把 $k$ 消除，利用乘法反元素反求 $x$ 是多少，公式如下所述。

• $k = s1^{-1} (SHA(M1) + x \times r) \mod q$ - (1)
• $k = s2^{-1} (SHA(M2) + x \times r) \mod q$ - (2)

subtract (1) - (2)

• $0 = s1^{-1} SHA(M1) - s2^{-1} SHA(M2) + (s1^{-1} - s2^{-1}) x \times r \mod q$
• $s1^{-1} SHA(M1) - s2^{-1} SHA(M2) = (s2^{-1} - s1^{-1}) x \times r \mod q$
• $x = (s1^{-1} SHA(M1) - s2^{-1} SHA(M2)) \times (s2^{-1} - s1^{-1})^{-1} \times r^{-1} \mod q$

get private key. Dangerous !

Verify

驗證的正確性與否，接收者需要計算以下四個步驟來完成驗證。

• $w = s^{-1} \mod q$
• $u1 = (SHA(M) \times w) \mod q$
• $u2 = r \times w \mod q$
• $v = g^{u1} y^{u2} \mod q$

test $v = r$, why correct ?

理論的正確性可以參考以下證明，把公開的 $y = g^x \mod p$ 拿出來，這個安全性取決於離散對數的算法難度。

• known $y = g^x \mod p$, $x$ is a private key
• because $s = k^{-1}(SHA(M) + x \times r) \mod q$
• then $k = s^{-1}(SHA(M) + x \times r) \mod q$

want $r = (g^k \mod p) \mod q$

• $r = (g^k \mod p) \mod q = g^{s^{-1}(SHA(M) + x \times r)} \mod q$
• $r = g^{s^{-1} SHA(M)} \times g^{x (s^{-1} \times r)} \mod q$
• $r = g^{s^{-1} SHA(M)} \times g^{x^{(s^{-1} \times r)}} \mod q$
• $r = g^{s^{-1} SHA(M)} \times y^{(s^{-1} \times r)} \mod q$

而我們事實上就是在處理指數部分，

離散對數

解決問題 $y = g^x \mod p$，當已知 $y, g, p$，要解出 $x$ 的難度大為提升，不像國高中學的指數計算，可以藉由 log() 運算來完成，離散對數可以的複雜度相當高，當 $p$ 是一個相當大的整數時，通常會取用到 256 bits 以上，複雜度則會在 $O(2^{100})$ 以上。

實際上有一個有趣的算法 body-step, giant-step algorithm，中文翻譯為 小步大步算法 ，在 ACM-ICPC 競賽中也可以找到一些題目來玩玩，算法的時間複雜度為 $O(\sqrt{p})$，空間複雜度也是 $O(\sqrt{p})$。相信除了這個外，還有更好的算法可以完成。

小步大步算法其實很類似塊狀表的算法，分塊處理，每一塊的大小為 $\sqrt{p}$，為了找尋答案計算其中一塊的所有資訊，每一塊就是一小步，接著就是利用數學運算，拉動數線，把這一塊往前推動 (或者反過來把目標搜尋結果相對往塊的地方推動)。因此需要走 $\sqrt{p}$ 大步完成。