Elgamal加密算法

Elgamal加密算法是一种基于离散对数问题的、基于迪菲-赫尔曼密钥交换协议的非对称加密算法

它的加解密过程还挺简单易懂的

首先我们准备好食材：

一个大素数p、一个$Z_p^*$的生成元g、随机选择整数$k(0 \le k \le p-2)$

然后计算$y \equiv g^k \mod{p}$

这样子我们记私钥为$\{k\}$ 公钥为$\{ p,g,y\}$

起锅烧水！！

Alice选取一个整数r，并计算如下两个方程

$y_1 \equiv g^r \mod p$ (1)

$y_2 \equiv my^r \mod p$ (2)

这样做就把m隐藏在$y_2$中

Alice再把$y_1\ y_2$发送给Bob

不难发现加密过程使用的是公钥$\{ p,g,y\}$

Bob还原m的过程也非常简单

将$y \equiv g^k \mod{p}$代入(2)中，将(1)左右两侧同时k次幂

得到

$y_1^k\equiv g^{kr}\mod p$

$y_2 \equiv mg^{kr} \mod p$

两式左右分别相乘

$m \equiv y_2(y_1^{k})^{-1} \mod p$

不难发现解密使用的是私钥$\{k\}$