ElGamal加密算法基础到实现详解
先从数学基础开始
群
群是一个集合G，连同一个运算 "·"，它结合任何两个元素 a 和 b 而形成另一个元素，记为 a · b。符号 "·" 是对具体给出的运算，比如加法的一般的占位符。要具备成为群的资格，这个集合和运算 (G, ·) 必须满足叫做群公理的四个要求：
1.
封闭性。
对于所有 G 中 a, b，运算 a · b 的结果也在 G 中。
2.
结合性。
对于所有 G 中的 a, b 和 c，等式 (a · b) ·c = a · (b · c) 成立。
3.
单位元。
存在 G 中的一个元素 e，使得对于所有 G 中的元素 a，等式 e · a = a · e = a 成立。
4.
反元素。
对于每个 G 中的 a，存在 G 中的一个元素 b 使得 a ·b = b · a = e，这里的 e 是单位元。
例如整数集合 和加法运算，具有以下性质
对于任何两个整数 a 和 b，它们的和 a + b 也是整数。换句话说，在任何时候，把两个整数相加都能得出整数的结果。这个性质叫做在加法下封闭。
对于任何整数 a, b 和 c，(a + b) + c = a + (b + c)。用话语来表达，先把 a 加到 b，然后把它们的和加到 c，所得到的结果与把 a 加到 b 与 c 的和是相等的。这个性质叫做结合律。
如果 a 是任何整数，那么 0 + a = a + 0 = a。零叫做加法的单位元，因为把它加到任何整数都得到相同的整数。
对于任何整数 a，存在另一个整数 b 使得 a + b = b + a = 0。整数 b 叫做整数 a 的逆元，记为 −a。
一个群被称为有限群，如果它有有限个元素。元素的数阶叫做群 G 的阶
例如，模19下7的阶为3，[1, 7, 49, 343, 2401, 16807, 117649, 823543, 5764801...]={1,7,11,1,7,11,1,7,11...}这里的1,7,11循环，实际只有3个元素
循环群
循环群是其所有元素都是特定元素 a 的幂的群(在群运算被写为加法的时候使用术语倍数)。在乘法符号下，群的元素是:
..., a−3, a−2, a−1, a0 = e,a, a2, a3, ...,
这个元素 a叫做这个群的生成元或本原元。
本原元
模n下a的阶m=φ(n)，m就是n的本原元，如3是19的本原元
19为质数，因此φ(19)=18（参见http://blog.csdn.net/boksic/article/details/6912381）,模19下3的群为
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441,1594323, 4782969,
14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401L,10460353203L, 31381059609L, 94143178827L...]
用模19来表示
[1, 3, 9, 8, 5, 15, 7, 2, 6, 18, 16, 10, 11, 14, 4, 12, 17, 13, 1, 3, 9L,8L, 5L, 15L]
循环为1, 3, 9, 8, 5, 15, 7, 2, 6, 18, 16, 10, 11, 14, 4, 12, 17, 13,因此该循环群阶为18与欧拉函数结果相等
剩下的都是简单的套公式了
ElGamal密钥生成
随机选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。
随机选择一个整数d作为密钥，2≤d≤p-2 。
计算y=α^d mod p，取y为公钥。
ElGamal加密
对于明文M加密
随机地选取一个整数k，2≤k≤p-2。
C1＝α^k mod p；
C2＝MY^k mod p；
密文为（C1,C2）
ElGamal解密
由密文可得明文M
M=C2/C1^d mod p
实例
密钥生成选取素数p=150001，本原元a=7，密钥113
>>> p=150001
>>> a=7
>>> d=113
>>> a**d%p
66436L
>>> y=a**d%p
>>> print y
66436
由公式可得公钥为y=66436
加密，明文为m=809,随机整数为k=1000
>>> m=809
>>> k=1000
>>> c1=a**k%p
>>> c1
90429L
>>> c2=m*y**k%p
>>> c2
15061L
得到密文为(c1,c2)=(90429,15061)
解密
根据公式m1=c2/c1**y%p，但其中有模逆运算，不能直接计算，可以用扩展欧几里得算法（参见：http://www.zzzyk.com/kf/201111/112426.html）先求c1**y的模逆
>>> extended_gcd(c1**d%p,p)
(-69199L, 2147L)
我们所需要的是正数，所以加上p，-69199+p=80802
然后就可以
>>> 80802*c2%p
809L
正是刚开始的明文809
摘自 boksic的专栏
补充：综合编程 , 安全编程 ,
