3.4 概率公钥系统 虽然可以通过在明文后面附上随机生成指定长度的字符串挫败上述攻击，但是要付出时空代价。 为了针对一个被动敌手从密文恢复出相应的明文，我们要求解密算法对几乎所有明文都难以解出明文。这是最起码的要求。如何能达到更强一些的安全性呢？我们回想RSA, Rabin, 背包等公钥加密算法它们都是确定的加密算法，即相同的密钥和相同的明文总是加密成相同的密文。对确定的加密算法可能有如下缺点： 对有的消息空间概率分布算法不都是安全的。例如消息0或1加密后不变，所以很容易查出来； 有时容易从密文得到明文的部分信息。如明文m的RSA密文 从密文的直接得到明文的Jacobi值 ， 从而得到明文的一位信息。 容易察觉相同明文传送两次 虽然可以通过在明文后面附上随机生成指定长度的字符串挫败上述攻击，但是要付出时空代价。

我们说公钥密码系统在语义上是安全的(Semantically Secure)是指在多项式时间内从密文不会泄露关于明文的任何信息，即对手有多项式界定的计算资源，他不能从密文悟出明文的任何信息。 二次剩余公钥加密是一种概率加密（Probabilistic Encryption）技术，使敌手在多项式时间内不能从密文得到关于明文的任何信息。因此，假设二次剩余问题是难解问题，那么二次剩余公钥密码系统是在语义上安全的。

3.4.1 Goldwasser-Micali 概率公钥密码系统 公私钥对的生成 选择长度相同的两个大素数p和q作为私钥，计算n=p.q 选择一个模n非二次剩余正整数t且 。具体步骤为： ⑴在 中有一半是模p非二次剩余，选取 使之满足 ⑵同样选取 使之满足 ⑶解同余方程 ， 。显然 公布公钥n和t，p和q是私钥。

加密算法 首先得到对方的公钥 。 对明文， 。对明文的每一位 随机选择 计算 m是的密文 首先得到对方的公钥 。 对明文， 。对明文的每一位 随机选择 计算 m是的密文 显然当 = 0时是模二次剩余，而当 = 1时 是模n非 二次剩余

解密算法 接收者用自己的私钥p，对每位密文计算 ， ， 明文为 ， ， 明文为 Goldwasser-Micali 概率公钥密码系统的缺点是消息加密后扩展 倍。所以该密码系统适用于对单bit 加密，否则运算量大、速度慢。

3.4.2 Blum-Goldwasser概率公钥密码系统 Blum-Goldwasser概率公钥密码在消息扩展和运算速度上都可以跟RSA相比美，它是目前最有效的概率加密方案。为此我们先介绍Blum-Goldwasser概率公钥密码中需要的一种BBS伪随机位生成器(Blum-Blum-Shub Pseudo-Random Bit Generator ) Blum-Blum-Shub PRBG 首先生成两个大素数 ，令 ，n称为Blum数 选取随机整数 ，使 。W称为种子，计算 。 对 ，计算 ， 的最后一位 输出长度为t的伪随机序列

Blum-Goldwasser概率公钥密码系统 密钥生成 选择两个不同的大随机素数p和q， ，计算 n=p.q ，用扩展的Euclidean算法计算a，b使ap+bq=1。 公布公钥n，保密私钥p,q,a,b 加密算法 首先得到对方真实公钥n。令 明文 ，其中 长度为h，1≤i≤t。 取 ，令 对 做 且 的最后h位 计算 将 传送给对方

解密算法 ⑴计算 ， ⑵计算 ， ⑶使用自己的私钥p,q,a,b，计算 ⑷ 对 做 且 的最后h位 下面给出在第3）步中计算 的推理过程。从加密过程知 是 模n二次剩余，由Euler准则知 而 ， ，同理 ，即 依次递推下去

下面给出在第3）步中计算 的推理过程。从加密过程知 是 模n二次剩余，由Euler准则知 而 ， ，同理 ，即 依次递推下去 。同理 又 ， 同理 从而 建议：取n为1025bit，h取10bit。