密码学系列｜2.4 The Elgamal Public Key Cryptosystem

 尽管Diffie–Hellman密钥交换算法提供了一种公开共享随机密钥的方法，但它并没有实现作为公钥密码系统的全部目标，因为密码系统允许交换特定信息，而不仅仅是一个随机的比特串。第一个公钥密码系统是 Rivest、Shamir 和 Adleman 在1978年发布的RSA系统，RSA加密系统是一个尤为重要的发现，我们将在第3章详细讨论它。然而，尽管RSA是历史上第一个公钥密码系统，但继 Diffie–Hellman 发表论文《New directions in cryptography》之后，公钥密码系统最自然的发展是 Taher Elgamal 在1985年描述的加密系统，Elgamal公钥加密算法基于离散对数问题，与2.3章节中 Diffie–Hellman 密钥交换系统很相似。在本节中，我们将介绍基于  下离散对数问题的Elgamal加密算法，但依然在加密系统中密切使用了DLP，特别我们将在6.4.2章节中继续讨论基于椭圆曲线群的Elgamal加密算法。

  Elgamal-PKC是我们的第一个公钥密码系统的示例，因此我们将详细地介绍。Alice 首先发布由公钥和算法组成的信息，公钥只是一个数字，算法就是 Bob 用 Alice 的公钥加密消息的方法。Alice 没有透露她的私钥，私钥是另一个数字。私钥允许 Alice（只有 Alice）解密使用其公钥加密的消息。

  以上描述是非常笼统的，适用于任何公钥密码系统。对于Elgamal-PKC，Alice需要一个大素数 ，而 中的离散对数问题是困难的，她需要一个在模  下有大素数阶的元素 。她可能会自己选择  和 ，也可能是由某个值得信任的组织（如行业委员会或政府机构）预先选择的。

  Alice选择一个密钥a作为她的私钥，并计算

  我们注意到与 Diffie–Hellman 密钥交换很相似之处，Alice 发布了她的公钥 A，并对她的私钥保密。

  现在假设Bob希望使用 Alice 的公钥  加密消息，我们将假设Bob的消息  是介于 2 和  之间的整数。（回想一下，我们在第1.7.2节中讨论了如何将消息转换为数字。）为了加密 ，Bob首先随机选择另一个模  下的数字 ，Bob使用  加密一条消息后再丢弃，数字  称为随机元素，它的唯一目的是加密单个消息。

  Bob获取他的明文消息 ，随机元素  和 Alice 的公钥 A，并使用它们计算这两个量

  （注意， 和  是公共参数，因此 Bob 也知道它们的值）Bob的密文，即他对  的加密，是他发送给 Alice 的一对数字 。

  Alice如何解密Bob的密文？由于Alice已知私钥  值，可以进行如下计算

  她可以通过快速幂算法来计算 ，然后使用扩展欧几里德算法计算其逆。或者可以直接使用快速幂算法计算 ，Alice 接下来将  乘以 ，发现结果是明文 。为啥嘞？我们将  的值展开，然后发现

 Eve解密信息的任务是什么？Eve知道公共参数  和 ，她还知道 A 值，因为 Alice 的公钥 A 是公共信息。如果 Eve 能解决离散对数问题，那么她就可以找到私钥并解密消息。更准确地说，Eve 解决Diffie-Hellman问题就足够了，否则，Eve 似乎很难找到明文。

Example 2.8 

Alice使用素数  和原根 ，她选择  作为她的私钥，并计算她的公钥

 Bob决定向Alice发送消息 。他选择一个随机元素，比如说他选择 ，然后他计算这两个量

 这对，，是 Bob 发送给 Alice 的密文。

 Alice知道 ，首先计算

 最后计算

 则恢复出明文 

注： 在Elgamal密码系统中，明文  是介于  和  之间的整数，而密文由相同范围内的两个整数c1和c2组成。因此，密文所需的比特数是明文所需比特数的两倍，所以我们称Elgamal有一个  的消息扩展。

  那么Elgamal密码系统和 Diffie–Hellman 问题一样难解决吗？或者，我们引入的这种简便的消息加密方法，是否在无意中打开了一扇后门，使得在不解决Diffie-Hellman问题的情况下能够轻松解密消息？现代密码学的目标之一是确定一个潜在的难题，如 Diffie–Hellman 问题，并证明像 Elgamal 这样的给定密码结构的加密系统至少与潜在问题一样难以攻破。

  在这种情况下，我们想证明，只要能解密由 Elgamal 加密的信息，也必须能够解决 Diffie–Hellman 问题。具体而言，我们想证明以下几点：

命题 2.10 

确定用于 Elgamal 加密的素数  和原根 。假设 Eve 可以访问一个 oracle，该 oracle 可以解密任意由 Elgamal 公钥加密的密文。然后她可以使用 oracle 来解决上一节中描述的Diffie-Hellman问题。

相反，如果Eve能够解决 Diffie–Hellman 问题，那么她就可以破解 Elgamal-PKC。

证明

  我们将详细的解释如何使用 Elgamal oracle 解决 Diffie-Hellman 问题。回想一下，在 Diffie-Hellman 问题中，Eve 被得到了两个值

  现在假设 Eve 可以使用一个 Elgamal 的 oracle。这意味着 Eve 可以向 oracle 发送素数 、原根 、公钥 A 和密文、。参考上文中的表，oracle将返回  值给Eve

  如果 Eve 想解决 Diffie-Hellman 问题，她应该选择  和  的哪些值？经过考虑，和是不错的选择，因为有了这个输入，oracle 将返回，然后 Eve 可以通过取逆得到 ，从而解决Diffie–Hellman问题。

  但也许 oracle 存在某种设定，永远不解密  的密文。Eve 仍然可以通过发送如下随机密文来欺骗oracle。她为  选择一个任意值，并告诉 oracle 公钥是 ，密文是 ，，oracle返回的  值满足以下条件

  在 oracle 告诉 Eve  的值后，她只需进行如下计算，求 的值

  值得注意的是，尽管在 oracle 的帮助下，Eve 计算出了，但她仍然不知道  和  的值，因此她只解决了 Diffie-Hellman 问题，而没有解决离散对数的问题。