EIGamal加密算法-HSM's Blog

1. ElGamal算法简介

ElGamal算法是由Tather ElGamal在1985年提出的，它是一种基于离散对数难题的加密体系，与RAS算法一样，既能用于数据加密，也能用于数字签名。ElGamal算法是基于因数分解，而ElGamal算法是基于离散对数问题。与RSA算法相比，ElGamal算法哪怕是使用相同的私钥，对相同的明文进行加密，每次加密后得到的签名也各不相同，有效的防止了网络中可能出现的重放攻击。

2. ElGamal算法原理

2.1 ElGamal密钥生成

（1）随机选择一个大素数p，且要求p-1有大素数因子。再选择一个模p的本原元α。将p和α公开。
模p的本原元就是满足：[math-inline]${\alpha}^{\phi(p)}\equiv 1 \ mod \ p$ [math-inline]
（2）随机选择一个d作为私钥密钥,d为整数，1≤d≤p-1 。
（3）计算:$ \beta=\alpha^d\ mod\ p $ 取β为公钥。

2.2 ElGamal加密

（1）对于明文M加密，随机地选取一个整数k，1≤k≤p-2
（2）$ C1\ ＝\ α^k\ mod\ p（3） C2\ ＝\ Mβ^k\ mod\ p $
（4）密文为（C1,C2）

2.3 ElGamal解密

由密文可得明文M:$ M\ =\ \frac{C2}{C1^d}\ mod\ p $

3. 算法实现

3.1 Python程序

import random
# 欧拉函数
def phi(n):
        listN = []
        #符合条件的质因子
        for i in range(2,n+1):
            if n%i == 0:   # n = 16  i = 2，4，6，8，16
                flag = True
                for j in range(2,i):
                    if i%j == 0:
                        flag = False
                        break
                if flag:
                    listN.append(i) # 当i是质数就存入列表
        # 返回值
        result = n
        for i in range(len(listN)):
            result *= 1-(1/listN[i])
        return int(result)

# 求分数的模p同余   a/b mod p
def mod(a,b,n):
    """
    分数0<a/b<1
    求解a/b mod n的结果
    """
     # 统一b为正数
    if b < 0:
        b = -b
        a = -a

    # 统一a为非负数
    while a < 0:
        a += p

    a = a % p
    i = 1
    while True:
        if i*b % n == a:
            return i
        i += 1
def get_a(p:int):
    result_list = []
    for a in  range(0,p):
        # print("a:",a)
        if a**phi(p)%p == 1:
            result_list.append(a)
    # print(result_list)
    return result_list[random.randint(0,len(result_list)-1)]

def gen_EIGamal_key(p):
    a = get_a(p)  # alphi
    d = random.randint(1,p-1)
    b = a**d % p # beta
    return b,d,a #公钥和私钥
def EIGamal_encode(p:int,a:int,public_key:int,M:int):
    k = random.randint(1,p-2) # 加密随机数 随机选取一个整数k,使得1<=k<=p-2
    C1 = int(a**k) % p
    C2 = int(M*int(public_key**k)) % p
    return (C1,C2)
def EIGamal_decode(p:int,private_key:int,C:int):
    decode = mod(C[1],C[0]**private_key,p)
    return decode

p = 1235
M1 = 1231
public_key,private_key,a = gen_EIGamal_key(p)
C = EIGamal_encode(p,a,public_key,M1)
M = EIGamal_decode(p,private_key,C)
print("密文：",C)
print("明文：",M)

目录CONTENT

EIGamal加密算法