--- title: ElGamal Encryption tags: crypto lang: zh_tw --- * [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS) [TOC] # ElGamal Encryption ElGamal Encryption 建立在 DHKE 上 ## DHKE Diffie-Hellman Key Exchange ### 流程 1. 找一個大質數 $p$ ($p > 2^{1024}$ 較安全) 2. 選擇一個 $\alpha \in \{2, 3, ..., p-2\}$ 將 $p, \alpha$ 公開出來 | Alice | 傳遞過程 | Bob | | -------- | -------- | -------- | | 隨機挑選私鑰 $K_{priA} = a \in \{1, 2, ..., p-1\}$ | | 隨機挑選私鑰 $K_{priB} = b \in \{1, 2, ..., p-1\}$ | | 計算公鑰 $K_{pubA} = A = \alpha^a\ mod\ p$ | | 計算公鑰 $K_{pubB} = B = \alpha^b\ mod\ p$ | | | ----> 傳送 A | | | | <---- 傳送 B | | | 計算 $k_{AB} \equiv B^a \equiv (\alpha^b)^a\ mod\ p$ | | 計算 $k_{AB} \equiv A^b \equiv (\alpha^a)^b\ mod\ p$ | 到這裡後, 就可以用對稱式加密, 以 $k_{AB}$ 當作對稱金鑰來加密溝通流程 ### 安全性 第三者能看到一開始就公布的 $p, \alpha$ 和產生 $k_{AB}$ 過程中的 $A, B$ 得知 $A = \alpha^a\ mod\ p$ 此公式的三個變數, 可以暴力求 $a$ 解出 $a$ 後就能以 $k_{AB} \equiv B^a\ mod\ p$ 破解已建立起來的對稱式加密 所以 DH 的演算法安全性建立在 **[離散對數難題](https://hackmd.io/@LJP/HJL5anU8F)** 也就是說 **$A = \alpha^a\ mod\ p$, $p$ 為質數, 已知 $A, \alpha, p$, 仍然很難求 $a$** ### 攻擊手段 #### Shanks’ Baby-Step-Giant-Step Method TBD #### Pollard’s Rho Method TBD #### Pohlig-Hellman Method TBD ## 流程 1. 找一個大質數 $p$ ($p > 2^{1024}$ 較安全) 2. 選擇一個 $\alpha \in \{2, 3, ..., p-2\}$ 將 $p, \alpha$ 公開出來 | Alice | 傳遞過程 | Bob | | -------- | -------- | -------- | | 隨機挑選私鑰 $K_{priA} = a \in \{1, 2, ..., p-1\}$ | | 隨機挑選私鑰 $K_{priB} = b \in \{1, 2, ..., p-1\}$ | | 計算公鑰 $K_{pubA} = A = \alpha^a\ mod\ p$ | | 計算公鑰 $K_{pubB} = B = \alpha^b\ mod\ p$ | | | ----> 傳送 A | | | | <---- 傳送 B | | | 計算 $k_{AB} \equiv B^a \equiv (\alpha^b)^a\ mod\ p$ | | 計算 $k_{AB} \equiv A^b \equiv (\alpha^a)^b\ mod\ p$ | 接下來雙方都能這樣加密 $m$ $c \equiv m \times K_{AB}\ (mod\ p)$ 這樣解密 $c$ $m \equiv c \times K_{AB}^{-1}\ (mod\ p)$ 跟 DHKE 非常像，差別在後面怎麼運用共同金鑰 ## 攻擊手段 ### Passive attacks 竊聽溝通過程中傳送的 $K_{pubA}, K_{pubB}$ 並試圖解回雙方的私鑰 難度建立在 **[離散對數難題](https://hackmd.io/@LJP/HJL5anU8F)** ### Man-in-the-Middle Attack ![](https://i.imgur.com/HUKYu0v.png) 因為傳遞公鑰的過程缺法驗證性 導致潛在的中間人攻擊