ElGamal是个啥子玩意

Posted on

很早之前就听说ElGamal加密算法是一种公钥密码，但是具体实现和用途不甚了解，今天阅读了 A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS 一文，故去了解了一下。特开此文，记录一下

省流：ElGamal是DH密钥交换的抵抗中间人攻击版本

ElGamal加密算法是一个基于DH密钥交换的非对称算法，可以定义在任何循环群上，它的安全性取决于循环群上的离散对数难题

离散对数问题指的是：

  • 已知 ，计算 是简单的。
  • 已知 ，计算 是困难的。

Diffie-Hellman 密钥交换过程：

  1. Alice 和 Bob选定一个素数 ，以及它的一个原根
  2. Alice 选择一个密钥 ，计算 ，发给 Bob
  3. Bob 选择一个密钥 bb ，计算 ，发给 Alice
  4. Alice 计算 ，Bob 计算 这样，Alice 和 Bob 就共享了一个密钥

通俗理解：在调色板上将两种颜色混合容易，而将两种颜色分开是困难的。

由于离散对数问题是一个数学困难问题，在选择了合适的 和 时，Diffie-Hellman 密钥交换协议被认为是 窃听安全 的。攻击者 Eve 在已知 的情况下，难以计算出

缺陷无法抵抗中间人攻击

DH 本身没有提供任何身份认证，因此容易遭受中间人攻击：

  • 中间人 Eve 假装自己是 Bob 与 Alice 通信
  • 中间人 Eve 假装自己是 Alice 与 Bob 通信
  • Eve 将 Alice 发来的消息用 解密，使用 加密，发送给 Bob
  • Eve 将 Bob 发来的消息用 解密，使用 加密，发送给 Alice
  • Alice 和 Bob 对此一无所知，还无知地以为在与对方通信

需要一种能验证通信双方身份的机制 (如签名) 来防止这类攻击

ElGamal 加密算法：

本质上就是用 DH 获得一个密钥，然后用它加解密消息。

密钥生成：

  1. Alice 和 Bob 选定一个素数 ，以及它的一个原根
  2. Alice 选择一个私钥 ，计算公钥 ，公开
  3. Bob 选择一个私钥 ，计算公钥 ，公开

假如 Bob 要给 Alice 发送一条消息 ，加密过程：

  1. Bob 计算密钥
  2. Bob 发送

Alice 收到密文，解密过程：

  1. Alice 计算密钥
  2. Alice 解密消息

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from Crypto.Util.number import *

p = None ; g = None
pub = None#公钥也是公共可见的
c = None#加密方加密后并传输给解密方的密文，这个也是可以被攻击者截获的

#初始化，公共可见的大素数和生成元
def init():
    global p , g
    p = getPrime(512)
    g = 2

#接收方(A)需要干的事情，即生成密钥（包括公钥和私钥
def reciver_need_do():
    global pub
    a_pri = bytes_to_long(b'I am priviate key of A.')
    a_pub = pow( g , a_pri , p )
    pub = a_pub
    return a_pri

#发送方(B)需要进行的加密操作，生成密文并
def ElGamal_encode():
    m = bytes_to_long(b'miao miao miao wo shi ming wen 233')
    k = getRandomInteger(10)
    c1 = pow( g , k , p )
    c2 = m * pow( pub , k , p ) % p
    return c1 , c2

#解密方需要进行的解密操作
def ElGamal_decode( pri ):
    global c
    c1 , c2 = c
    c1 = pow( c1 , p-2 , p )
    m = c2 * pow( c1 , pri , p ) % p
    return m

if __name__ == '__main__':
    init()
    a_pri = reciver_need_do()#返回接受者的私钥，a_pri只有接受者可以用
    c = ElGamal_encode()#B将信息进行加密，然后传给A
    m = ElGamal_decode( a_pri )#A使用自己的密钥，对信息进行解密
    print( long_to_bytes(m) )