ElGamal加密、簽名算法筆記

ElGamal加密算法是一種非對稱加密算法，基于Diffie-Hellman密鑰交換算法，由Taher Elgamal在1985年提出。

ElGamal加密算法可以應用在任意一個循環群(cyclic group)上。在群中有的運算求解很困難，這些運算通常與求解離散對數(Discrete logarithm)相關，求解的困難程度決定了算法的安全性。

群(Group)的定義：

群是數學中的概念。

一些元素組成的集合，如果元素滿足以下條件，則把這些元素組成的集合叫做群：

在元素上可以定義一個2元運算，運算滿足封閉性、結合律、單位元和逆元。

群的例子：

所有整數構成一個群，如果定義的2元運算為整數加法的話。加法可以滿足上述條件：

封閉性：a+b之后仍然是整數

集合率：(a + b) + c = a +（b + c）

單位元：0 + a = a + 0 = a，則整數0為加法的單位元

逆元：a + b = b + a = 0，則整數b叫做整數a的逆元

所以可以簡單的將群理解為一些元素的集合加上一個選定的運算方式。

循環群的定義：

循環群中的所有其它元素都是由某個元素g運用不同次數的選定運算方式計算出來的。

公鑰生成：

1、選取一個循環群G，且循環群G的階數為q

2、選擇一個隨機數x，1<x<q-1

3、計算h=g^x

h和g，G，q就構成公鑰

x是保密的，x與h，g，G，q一起構成密鑰

公鑰加密：

1、選取一個隨機數y，1<y<q-1

2、計算c1=g^y

3、計算s=h^y=(g^x)^y=g^(x*y)

4、加密數m得c2=m*s

c1、c2構成加密結果，交給私鑰解密

私鑰解密：

1、通過c1計算得到s=c1^x=(g^y)^x=g^(x*y)

2、計算c2*(s^-1)=(m*s)*(s^-1)，得到原來數m

注意以上的運算不再是普通的乘(*)和乘方(^)運算，而且有循環群G對應的運算衍生出來的運算。但這些運算的意義和規律還是和普通數字運算的規律一樣的，所以上面的等式仍然成立。

由上面看出s的計算過程和Diffie-Hellman密鑰交換算法類似。

在應用中通常使用的循環群G為整數模n乘法群(Multiplicative group of integers modulo n)。

同余：

如果整數a、b的對于整數n的模相等即a%n=b%n，則稱a和關于模n同余。可以記做：

a≡b (mod n)

互質(Coprime integers)：

如果整數a、b的最大公因數為1，則a、b互質。

整數模n乘法群：由模n的互質同余類組成一個乘法群。

簽名和驗證算法，基于整數模n乘法群：

私鑰，公鑰生成：

1、選取一個隨機數k，1<x<p-1

2、計算y=g^x%p

(g, p, y)為公鑰，x為私鑰。

用私鑰簽名：

1、選取一個隨機數k，1<k<p-1，且k和p-1同余

2、計算r，r滿足：r≡g^k (mod p)

3、計算s，s滿足：s≡(H(m)-xr)*(k^(-1))  (mod p-1)

m為待簽名信息，H(m)為m的哈希(比如sha1)結果。

（r，s）構成對m的簽名

用公鑰驗證簽名：

1、驗證：0<r<p，0<s<p-1

2、驗證：g^(H(m))≡(y^r)*(r^s) (mod p)

簽名算法正確性證明：

由簽名過程得：H(m) ≡s*k+x*r (mod p-1)

根據費馬小定理：

g^(H(m))≡g^(x*r)*g^(k*s) (mod p)≡((g^x)^r)*(g^k)^s (mod p) ≡ (y^r)*(r^s) (mod p)

參考：

ElGamal加密算法： http://en.wikipedia.org/wiki/ElGamal_encryption

群： http://zh.wikipedia.org/wiki/%E7%BE%A4

循環群:  http://zh.wikipedia.org/wiki/%E5%BE%AA%E7%92%B0%E7%BE%A4

同余運算：    http://zh.wikipedia.org/wiki/%E5%90%8C%E9%A4%98

互質：  http://zh.wikipedia.org/wiki/%E4%BA%92%E8%B3%AA

整數模n乘法群：  http://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E6%A8%A1n%E4%B9%98%E6%B3%95%E7%BE%A4

離散對數： http://en.wikipedia.org/wiki/Discrete_logarithm

Diffie-Hellman密鑰交換算法： http://my.oschina.net/u/1382972/blog/330456

費馬小定理： http://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86