DSA - HackMD

--- title: DSA tags: crypto lang: zh_tw --- * [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS) [TOC] # DSA Digital Signature Algorithm 基於 Elgamal Signature scheme 以下先講如何簽章、驗章再講這些過程中用到的 key 怎麼生最後證明這樣簽這樣驗是否是對的 ## Sign $m$: 欲簽章的訊息 $d$: 私鑰 $p, q, \alpha$: 公鑰 1. 隨機選一個 $k, 0 < k < q$ 2. 計算 $r \equiv (\alpha^k\ mod\ p)\ mod\ q$ 3. 計算 $k^{-1}, k^{-1} \times k \equiv 1\ mod\ q$ 4. 計算 $s \equiv (H(m) + d \times r) \times k^{-1}\ mod\ q$ 這邊的 $H()$ 是 SHA-1 Hash, 算出 160 bit 的 hash 值 $r, s$ 兩者一起就是 Signature 的部分 ## Verification $m$: 欲驗章的訊息 $r, s$: Signature $p, q, \alpha, \beta$: 公鑰 1. 計算 $w \equiv s^{-1}\ mod\ q$ 2. 計算 $u_1 \equiv w \times H(m)\ mod\ q$ 這邊的 $H()$ 也是 SHA-1 Hash 3. 計算 $u_2 \equiv w \times r\ mod\ q$ 4. 計算 $v \equiv ((\alpha^{u_1} \times \beta^{u_2})\ mod\ p)\ mod\ q$ 若 $v \equiv r$ 表示 Signature 正確, 反之 GG ## Key generation 1. 首先產生 $q, 2^{159} < q < 2^{160}$ 2. 隨機挑一個 $k$, 使得 $p = kq + 1, 2^{1023} < p < 2^{1024}$ 且 $p$ 要是質數 3. 挑一個 $h, 1 < h < p$, 算出 $\alpha \equiv h^{(p-1)/q}\ (mod\ p)$ $\alpha$ 主要是要滿足 $\alpha^q \equiv 1\ (mod\ p)$ 根據[Fermat’s Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y) 可以將上式改寫成 $\alpha^q \equiv h^{p-1}\ (mod\ p), 1 < h < p$ 進而得到 $\alpha \equiv h^{(p-1)/q}\ (mod\ p)$ 4. 挑一個 $d, 0 < d < q$ 5. 計算 $\beta \equiv \alpha^d\ mod\ p$ 公鑰的部分: $p, q, \alpha, \beta$ 私鑰的部分: $d$ ## Proof 這邊需要證明的是 $r \equiv v\ mod\ q$ 先從 sign 時產生 $s$ 的方式推導一下 $$ \begin{split} s &\equiv (H(m) + d \times r) \times k^{-1}\ (mod\ q) \\ s^{-1} \times s \times k &\equiv s^{-1} \times (H(m) + d \times r) \times k^{-1} \times k\ (mod\ q) \\ k &\equiv s^{-1} \times (H(m) + d \times r)\ (mod\ q) \\ k &\equiv s^{-1} \times H(m) + s^{-1} \times d \times r\ (mod\ q) \\ \end{split} $$ 配合 Verification 對於 $u_1, u_2$ 的定義 $$ w \equiv s^{-1}\ mod\ q $$ $$ u_1 \equiv w \times H(m)\ mod\ q $$ $$ u_2 \equiv w \times r\ mod\ q $$ 可以繼續推導 $$ \begin{split} k &\equiv s^{-1} \times H(m) + s^{-1} \times d \times r\ (mod\ q) \\ k &\equiv u_1 + d \times u_2\ (mod\ q) \\ \end{split} $$ $$ \begin{split} \alpha^{k\ mod\ q} &\equiv \alpha^{(u_1 + d \times u_2)\ mod\ q}\ (mod\ p) \\ \alpha^{k} &\equiv \alpha^{u_1 + d \times u_2}\ (mod\ p) \\ \alpha^k &\equiv \alpha^{u_1} \times \alpha^{d \times u_2}\ (mod\ p) \\ \end{split} $$ 上面這區的證明參考[這篇](http://mercury.webster.edu/aleshunas/COSC%205130/K-DSA.pdf) 這部分的證明放到[DSA Lemma1](#DSA-Lemma1) 配合 key generation 生出 $\beta$ 的方式 $$ \beta \equiv \alpha^d\ mod\ p $$ 繼續推 $$ \begin{split} \alpha^k &\equiv \alpha^{u_1} \times \alpha^{d \times u_2}\ (mod\ p) \\ \alpha^k &\equiv \alpha^{u_1} \times \beta^{u_2}\ (mod\ p) \\ (\alpha^k\ mod\ p)mod\ q &\equiv ((\alpha^{u_1} \times \beta^{u_2})\ mod\ p)mod\ q \\ \end{split} $$ 配合 Sing 產生 $r$ 的方式 - $r \equiv (\alpha^k\ mod\ p)\ mod\ q$ 以及 Verification 產生 $v$ 的方式 - $v \equiv ((\alpha^{u_1} \times \beta^{u_2})\ mod\ p)\ mod\ q$ $$ \begin{split} (\alpha^k\ mod\ p)mod\ q &\equiv ((\alpha^{u_1} \times \beta^{u_2})\ mod\ p)mod\ q \\ r &\equiv v \\ \end{split} $$ 得證經過以上簽、驗章流程, $r$ 的確會與 $v$ 相同 ### DSA Lemma1 參考[這篇](http://mercury.webster.edu/aleshunas/COSC%205130/K-DSA.pdf) Lemma1 是說如果 $\alpha \equiv h^{(p-1)/q}\ (mod\ p)$ 成立則 $\alpha^t \equiv \alpha^{t\ mod\ q}\ mod\ p$ 成立那麼以下的式子 $$ \begin{split} \alpha^{k\ mod\ q} &\equiv \alpha^{(u_1 + d \times u_2)\ mod\ q}\ (mod\ p) \\ \alpha^{k} &\equiv \alpha^{u_1 + d \times u_2}\ (mod\ p) \\ \end{split} $$ 就沒有錯那麼開始證明囉 $$ \alpha \equiv h^{(p-1)/q}\ (mod\ p) $$ 以上式子是 key generation 中生出 $\alpha$ 的方式可以回去 [Key generation](#Key-generation) Check 一下推導以下式子 $$ \begin{split} \alpha &\equiv h^{(p-1)/q}\ (mod\ p) \\ \alpha^{nq} &\equiv (h^{(p-1)/q})^{nq}\ (mod\ p) \\ &\equiv h^{((p-1)/q) \times nq}\ (mod\ p) \\ &\equiv h^{(p-1) \times n}\ (mod\ p) \\ \end{split} $$ 套用 [Fermat’s Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y) $$ \begin{split} \alpha^{nq} &\equiv h^{(p-1) \times n}\ (mod\ p) \\ &\equiv (h^{(p-1)})^n\ (mod\ p) \\ &\equiv (1)^n\ (mod\ p) \\ &\equiv 1\ (mod\ p) \\ \alpha^{nq+z} &\equiv \alpha^z\ (mod\ p) \\ \end{split} $$ 其中 $0 < z < q$, 超過就被 $n$ 吸收了令 $t = nq + z$, 則 $z = t\ mod\ q$ $$ \begin{split} \alpha^{nq+z} &\equiv \alpha^z\ (mod\ p) \\ \alpha^t &\equiv \alpha^{t\ mod\ q}\ (mod\ p) \\ \end{split} $$ 得證 ## 安全性回顧一下 key generation >5. 計算 $\beta \equiv \alpha^d\ mod\ p$ > >公鑰的部分: $p, q, \alpha, \beta$ >私鑰的部分: $d$ > $$ \beta \equiv \alpha^d\ mod\ p $$ 這個式子中唯一未公開的是 $d$ 所以 DSA 的安全性建立在即使得知 $\beta, \alpha, p$, 仍然破不出 $d$ 屬於[離散對數難題](https://hackmd.io/@LJP/HJL5anU8F)