本文介绍了ElGamal算法。其中过程又提到了费马小定理等。
写在前面
上一节介绍了模运算之除法运算即逆元运算， 看过上节的朋友可能还记得，本来计划这一篇写写RSA算法。但是想起之前一篇介绍Schnoor签名的基础篇，有些东西需要补充，如Schnoor签名的背景基础等，Schnoor签名是Elgamal签名方案的变种。Elgamas算法又属于求解离散对数困难的一类算法，之前介绍的ECC也属于这一类， 为了同类描述的完整性，本节先介绍Elgamal算法。
ElGamal算法是由Tather ElGamal在1985年提出的，它是一种基于离散对数难题的加密体系，既能用于数据加密，也能用于数字签名。现代密码学一般是基于因数分解、或者离散对数等数学难题，ElGamal算法就是基于离散对数问题，其安全性依赖于计算有限域上离散对数这一难题，目前求解离散对数仍然是很困难的。
签名过程
Elgamal数字签名过程如下：
-
选择一个大素数P、一个本原元G、一个随机整数d，d属于[2，p-2]，d作为私钥
-
生成β，β = $G^d$ mod P；
-
此时P、G公开、β就是公钥;
-
被签信息摘要为M，选择临时随机数k ， k与 p - 1互素，计算：
-
r = $G^k$ mod P;
-
s = $(M-dr)k^{-1}$ mod (p-1)；
-
签名结果记为：sig=(r,s);
-
r,s是构成签名的两个整数；生成签名后，签名sig随同明文一起发送给接收方；
验证过程
-
接收者收到消息和签名结果（r，s）后计算:
$t = β^r ·r^s\ mod\ P$
-
验证：
当 t ≡ $G^M$ mod P 则该签名有效，数据未被篡改，反之则签名无效；注意：一定要检验s是否满足1<= s < p。否则签名容易伪造.
-
验证过程推导：
由于：
s = $(M-dr)k^{-1}$ mod (p-1)
可得:
ks ≡ M-dr mod(p-1) 移位得:
M ≡ ks+ dr mod(p-1)
根据费马小定理扩展（或者说推论）[注：即如果 m ≡ n mod (p-1) 则任意整数a, $a^m$≡ $a^n$mod p]，
得：$g^M \equiv g^{(ks+dr)} \equiv (g^k)^s (g^d)^r \equiv r^s \beta^r \ mod \ p = t$
到这里，验证完毕。如果你对以上过程尤其是推演过程不明白，说明你对前两节涉及到的模运算及其性质还没掌握，这里用到的有同余加，乘等性质。建议多看几遍遍，否则后续的文章读起来也会有诸多困难。
实例操练
假定选取P=23, G=3, d=11, 消息摘要M = 56
- 生成签名
计算 β =$G^d$ mod P =$3^{11}$ mod 23 = 1
选择临时随机数k = 15，计算：
$r =G^k\ mod\ P =3^{15}\ mod\ 23 = 12$
$s =(M-dr)k^{-1}\ mod\ (p-1)= (56 - 66)*15^{-1}\ mod\ 22 = 3$
得到sig=(6,14)
2. 验证签名
$t = β^r ·r^s\ mod\ P =1^6 · 12^{14}\ mod\ 23 = 3$
$g^M\ mod\ p =3^{56}\ mod\ 23 = 3 = t$ 可以得证。
加密解密
ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算 $a \equiv g^k ( mod\ p ) b \equiv y^k M ( mod\ p ) ( a, b )$为密文，是明文的两倍长。解密时计算$ M ≡ b / a^x ( mod\ p ) $非常简洁不再赘述！素数p必须足够大，且p-1至少包含一个大素数。
小结
本文介绍了ElGamal算法。其中过程又提到了费马小定理等。
好了，下一节就讲费马小定理及其相关。
欢迎关注公众号：blocksight
