简介

上一篇介绍了非对称加密算法中的RSA算法简介，这次看一下ElGamal算法。

首先它是一个基于迪菲-赫尔曼密钥交换的非对称加密算法。它在1985年由塔希尔·盖莫尔提出。它可以定义在任何循环群G上。它的安全性取决于G上的离散对数难题。（RSA基于大数的因数分解）

在介绍算法原理之前先熟悉几个概念：

阶

设n>1,a和n互质，则必有一个x (1≤x ≤n-1)使得： a^x ≡ 1 (mod n )

满足a^x ≡ 1 (mod n ) 的最小整数x , 称为a模n的阶。符号表示为Ordn(a)

观察方程 a^x ≡1(mod n) 根据欧拉定理，显然我们可以知道φ(n) 是方程的一个解，但它未必是最小的，所以不一定是阶，而当φ(n) 是a模n的阶时，我们称a为n的一个本原元。

本原元

当a模n的阶为φ(n)，也就是说当且仅当x是φ(n)的倍数，使得ax ≡1(mod n)成立，此时称a为n的本原元。

举个例子：

这些余数构成了一个模7的完全剩余系1,2,3,4,5,6，也就是对于任意a，都可以找到x0使得:

5^x0 ≡a (mod 7)。

本原元求解Python：

# 用辗转相除求最大公因子def gcd(a, b):    r = a % b    while r != 0:        a = b        b = r        r = a % b    return b# 欧拉函数def euler(a):    cnt = 0    for i in range(1, a):        if gcd(a, i) == 1:            cnt += 1    return cnt# 阶def order(a, n, b):    #   输出b在mod(a)中的阶    #   n是mod(a)群的阶    p = 1    while p <= n and b ** p % a != 1:        p += 1    if p <= n:        return p    else:        return -1# 求本原元def primitive_root(a):    n = euler(a)    for b in range(2, a):        if order(a, n, b) == n:            return bprint(primitive_root(37))# 可以看到，是2

同样是通过一个案例来介绍，还是Alice欲使用ElGamal加密算法向 Bob 发送信息。。

1.密钥生成对于Bob,首先要随机选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。我们为了方便计算取p = 37,则Z37的一个本原元α = 2.随机选择一个整数d作为密钥，2≤d≤p-2 。我们选择d = 5,计算β=α^d mod p，β=25 mod 37 = 322.加密

假设Alice 想发送消息 x = 29

首先选取随机数k , 假设k = 7

则： y1 = α^k mod p = 27 mod 37 = 17

y2 = x*β^k mod p = 29×32^7 mod 37 = 33将密文y = (17,33)发送给Bob3.解密

Bob收到密文y = (17,33) 后恢复明文如下：

x = y2 (y1^d)^ -1 mod p

= 33 (17^5)^ -1 mod 37

= 33×2 mod 37

= 29