密码学 | 3.10 概率加密与Goldwasser–Micali 密码系统

密码学 2年前 (2022) admin
754 0 0

3.10 Probabilistic Encryption and

the Goldwasser–Micali Cryptosystem

  假设 Alice 想使用公钥密码系统给Bob传输 1 bit 信息,即 Alice 想发送给 Bob 值 0 或者 1。乍一看,这似乎天生就不安全。Eve 所要做的就是加密两个可能的明文 ,然后她将加密的结果与 Alice 的密文进行比较。更一般地说,在任何可能的明文集很小的密码系统中,Eve 可以使用 Bob 的公钥加密每个明文,直到找到那个和 Alice 密文相同的结果为止。

  Probabilistic encryption 是由 Goldwasser 和 Micali 围绕这个问题发明的公钥密码系统。主要思想是 Alice 选择明文 和随机数据串 ,然后她使用 Bob 的公钥加密这对数据 。理想情况下,当 在其所有可能值上变化时, 的密文也将在所有可能值上“随机”变化。更准确地说,对于任何确定的 以及随机的 ,我们无法区分 。注意到 Bob 在解密的时候没必要恢复完整的数据对 ,他只需要恢复明文 即可。

  现在我们已经有了这样一个抽象的想法,那么在实践中该如何创建 Probabilistic encryption 呢?Goldwasser和Michali描述了一种这样的方案,虽然不切实际,因为它一次只加密1 bit 信息,但其优点是描述和分析都非常简单。这个想法是基于以下困难问题

  设有秘密素数 ,公开 。对于给出的值 ,判断 是否为模 下的二次剩余,即判断是否存在一个数 满足

  注意到 Bob 是知道如何分解 的,所以他可以很轻易的解决这个问题,因为当且仅当 才是模 下的二次剩余。

  而对于 Eve 来说,就比较困难了,虽然她可以计算 ,但前面我们已经提到(注 3.68),这并不能给出说 是否为模 下的二次剩余。Goldwasser 和 Michali 利用这一事实创建了表3.9中描述的 Probabilistic encryption

密码学 | 3.10 概率加密与Goldwasser–Micali 密码系统

  我们很容易就可以验证 Goldwasser 和 Michali 的密码系统是否有效。

  因为如果 ,则

  如果 ,则

  此外,由于 Alice 随机选择 ,因此当 Alice 加密 时,Eve 看到的值模 二次剩余,而当Alice加密 时,Eve 看到的值是满足 但模 非二次剩余。

  那么如果 Eve 计算了雅各比符号 ,他能得到什么呢?如果 ,那么 ,所以

  如果 ,那么 ,所以

  还是 1,注意到 Bob 选择的 满足 ,所以无论 值如何, ,因此雅各比符号没有给到 Eve 任何有用的信息。

例 3.70 Bob 使用上述密码系统,他首先生成参数

  注意到 满足性质 ,然后他公开数对 ,素数 选择保密。

  Alice 首先想给 Bob 发送比特 ,她选择区间 中的一个随机数 ,然后计算

  然后将密文 发送给 Bob,Bob尝试进行解密,计算 ,于是获得明文信息

  然后 Alice 决定给 Bob 发送明文比特 ,这次他选择随机数 ,然后她计算

  Bob尝试进行解密,计算 ,于是获得明文信息

  最后,Alice 想给 Bob 发送明文比特 ,这次他选择随机数 ,然后她计算

  注意到这次对于 的密文和上次的完全不相关。Bob尝试进行解密,计算 ,于是获得明文信息

注 3.71 Goldwasser–Micali公钥密码系统并不实用,因为明文的每一比特都是用模 的数字加密的。为了安全,Eve 必须不能将数字 分解,因此在实践中, 将(至少)是1000比特的数字。因此,如果 Alice 想将 位明文发送给 Bob,她的密文将是 比特长。

  因此,Goldwasswer–Micali公钥密码系统的消息扩展比为1000,因为密文的长度是明文的1000倍。更一般的,Goldwasswer–Micali公钥密码系统将消息扩展了 倍。

  还存在其他概率密码系统,其消息扩展比小的多。事实上,我们已经看到了一个:Elgamal公钥密码系统(第2.4节)使用的随机元素 使 Elgamal 成为概率密码系统。Elgamal的消息扩展比为2,如注2.9所述。后面在7.10一节中,我们将看到另一种称为NTRU的概率密码系统。更一般地说,采用确定性密码系统 (**deterministic cryptosystem **),如RSA,并将其转化为概率密码系统是可能的,而且实际上通常也是可取的,即使代价是增加其消息扩展比。(见练习3.43和第8.6节。)

             

原文始发于微信公众号(山石网科安全技术研究院):密码学 | 3.10 概率加密与Goldwasser–Micali 密码系统

版权声明:admin 发表于 2022年9月19日 上午11:29。
转载请注明:密码学 | 3.10 概率加密与Goldwasser–Micali 密码系统 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...