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

admin 2022年1月25日15:04:33评论167 views字数 2540阅读8分28秒阅读模式

 尽管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 接下来将  乘以 ,发现结果是明文 。为啥嘞?我们将  的值展开,然后发现

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

如下表总结了Elgamal公钥密码系统。


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

 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 被得到了两个值

  她需要计算 的值。她知道 A 和 B 的两个值,但她不知道 a 和 b 中的任何一个值。

  现在假设 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 问题,而没有解决离散对数的问题。

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

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

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月25日15:04:33
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   密码学系列|2.4 The Elgamal Public Key Cryptosystemhttps://cn-sec.com/archives/752901.html

发表评论

匿名网友 填写信息