一、基本原理

    ElGamal是1985年由T. EIGamal提出的一个著名的公钥密码算法，ElGamal 加密算法是一个基于 DH 的非对称加密算法 (基于离散对数难题) 。本质上就是用 DH 获得一个密钥，然后用它加解密消息。该算法既能用于数据加密也能用于数字签名，其安全性是依赖于计算有限域上离散对数这一难题。

1.1 第一种描述

    密钥生成：

1. Alice 和 Bob 选定一个素数 p，以及它的一个原根 g
   

2. Alice 选择一个私钥 XA
    ，计算公钥 YA=gXAmodp
    ，公开

3. Bob 选择一个私钥 XB ，计算公钥 YB=gXBmodp ，公开

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

1. Bob 计算密钥 k=(YA)XBmodp=gXAXBmodp
   

2. Bob 发送 c1=YB, c2=kmmodp
   

    Alice 收到密文，解密过程：

1. Alice 计算密钥 k=(c1)XAmodp=(YB)XAmodp=gXAYAmodp
   

2. Alice 解密消息 m=(c2⋅k−1)modp，这里的k-1是k的逆

1.2 第二种方式描述

1) 密钥产生

    任选一个大素数p，使得p-1有大素因子，g是模p的一个本原根，公开p与g。

    使用者任选一私钥x，x∈[0, p-1]

    计算公钥 y=g^x mod p

    公开公钥：y, p, g

    保密私钥：x

2) 本原根简介：

    如果a的阶m等于φ(n)，则称a为n的本原根（生成元）。如果a是n的本原根，则a, a^2, …, a^φ(n)在mod n下互不相同且都与n互素。

    特别地，如果a是素数p的本原根，则a, a^2, …, a^(p-1)在 mod p下都不相同。

3) 加密

    欲加密明文消息M，随机选一与p-1互素的整数k，计算

   C1=g^k mod p，

   C2=(y^k)*M mod p,

   密文为C=(C1,C2)

4) 解密

   先计算 w=(c1^x)^(-1) mod p再计算出明文 m=c2*w mod p

  也可以 M=C2/(C1^x) mod p

这是因为：

C2/(C1^x)modp=((y^k)M)/g^k* xmod p=((y^k)M)/y^k mod p=M mod p

二、题目求解

在上一篇文章“密码学题目-简答题与计算题”中，求解计算题题目，以下所示：

3. Bob和Alice采用GlGamal（或ElGamal）密码体制来进行加密通信，假定他们选定的素数q等于19，则原根有{2, 3, 10, 13, 14, 15}，从中选择10作为原根a，则：

(1) 假设Alice选择随机数5作为其私钥x，计算公钥y的值。

答：y = a^x mod p = 10^5 mod 19 = 3

 这样Alice的私钥为5，公钥为{3, 10, 19}。

(2) Bob想要将m = 17发送，并选择k = 6，计算m的密文(m1, m2)值。

m1 = a^k mod q = 10^6 mod 19 = 11

m2 = ((y^k mod q) × m) mod p  = ((3^6 mod 19) × 17) mod 19 = 5

得到密文(11, 5)。

(3) Alice收到Bob的密文后，给出其解密过程。

解密时计算 m = 5 × (11^5 mod 19)^(-1) mod 19 = 17，从而得到明文17。其中，第一个5是c2，第二个是私钥x，-1是逆。

原文始发于微信公众号（豆豆咨询）：密码学-EIGamal密码体制