昨天介紹了RSA，今天就介紹

ElGamal

ElGamal跟RSA一樣都是公開金鑰密碼系統，並且計算的流程也是一樣都是計算密鑰、加密、解密。

那麼為什麼會有ElGamal呢?

在RSA中，如果使用相同的明文會產生出相同的密文，但是ElGamal卻不會有這樣的問題。(都相同的密鑰)

那麼相同明文產生出相同密文會有什麼問題呢? 簡單說現在的密碼學看似安全但在科技持續進步，算力也會更著持續加快，那麼RSA原始密鑰長度是用512位元放到現在已經是很快就能被破解了。以前加密的東西流出是使用512位元的話，那麼有一個密文被解出來後，其他相同的明文也就不安全了。

ElGamal的計算流程：這邊假設有2個人，A和B

• 計算密鑰 (A的回合)
  1.首先選擇質數P，並與P互質的generator(原根)g。
  2.選擇一個私鑰x，並計算公鑰y = mod P
  3.公開金鑰(y,P,g)
• 加密 (B的回合)
  1.產生一個隨機數r(這邊的r要小於P的整數)。
  2.計算b和c，其中b = mod P，c = M mod P。
  3.把密文b和c傳給A
• 解密 (A的回合)
  收到密文b和c，使用私鑰x解密。
  解密是：M = c x () mod P。(-1是在指數)
  到這裡就完成ElGamal的加解密了。

ElGamal的安全性在於解離散對數x，給你公鑰(y,P,g)很難求出x。