区块链中的数学 - ElGamal算法

本文介绍了ElGamal算法。其中过程又提到了费马小定理等。

写在前面

上一节介绍了模运算之除法运算即逆元运算, 看过上节的朋友可能还记得,本来计划这一篇写写RSA算法。但是想起之前一篇介绍Schnoor签名的基础篇,有些东西需要补充,如Schnoor签名的背景基础等,Schnoor签名是Elgamal签名方案的变种。Elgamas算法又属于求解离散对数困难的一类算法,之前介绍的ECC也属于这一类, 为了同类描述的完整性,本节先介绍Elgamal算法。

ElGamal算法是由Tather ElGamal在1985年提出的,它是一种基于离散对数难题的加密体系,既能用于数据加密,也能用于数字签名。现代密码学一般是基于因数分解、或者离散对数等数学难题,ElGamal算法就是基于离散对数问题,其安全性依赖于计算有限域上离散对数这一难题,目前求解离散对数仍然是很困难的。

签名过程

Elgamal数字签名过程如下:

  1. 选择一个大素数P、一个本原元G、一个随机整数d,d属于[2,p-2],d作为私钥

  2. 生成β,β = $G^d$ mod P;

  3. 此时P、G公开、β就是公钥;

  4. 被签信息摘要为M,选择临时随机数k , k与 p - 1互素,计算:

  5. r = $G^k$ mod P;

  6. s = $(M-dr)k^{-1}$ mod (p-1);

  7. 签名结果记为:sig=(r,s);

  8. r,s是构成签名的两个整数;生成签名后,签名sig随同明文一起发送给接收方;

验证过程

  1. 接收者收到消息和签名结果(r,s)后计算: $t = β^r ·r^s\ mod\ P$

  2. 验证: 当 t ≡ $G^M$ mod P 则该签名有效,数据未被篡改,反之则签名无效;注意:一定要检验s是否满足1<= s < p。否则签名容易伪造.

  3. 验证过程推导: 由于: 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

  1. 生成签名 计算 β =$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

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-05-29 22:28
  • 阅读 ( 666 )
  • 学分 ( 0 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

72 篇文章, 1660 学分