安全第3讲——实用的计算安全

上一讲对完善加密解密的一些理论进行简单介绍，对于完善加密解密，无论攻击者有多强大的计算能力，都不能完成攻击。

这种安全，是信息理论安全，是完美的安全。

而现代加密方案，只要给攻击者足够的攻击时间和计算能力，它们都能被攻破，我们称之为“计算安全”。

1、计算安全的基本思想

计算安全的基本思想是：算法即使不能在数学上无法被攻破，也要保证在实践上无法被攻破。

“实践上无法被攻破”，指算法不能在合理的时间内，以合理的概率被攻破。

我们常常看到这样的描述：“本加密算法，使用配置I7 CPU的PC机进行破解，在100年时间内，被破解的概率是十亿分之一”。这就是“实践上无法被攻破”的一个描述。

2、概率多项式时间PPT

概率多项式时间PPT，是probabilistic polynomial time的缩写，表示时间是一个以n为参数的多项式值，下面是一个PPT的例子：

上图中，t是时间，a、b是常量，n是安全参数。

对于一个PPT攻击者，如果只能以可以忽略的概率成功地攻破一个方案，则认为方案是安全的。

通过PPT的定义，我们可以得出，当安全参数n值越大时，时间值越大，可以得到更高的安全级别。

3、方案安全性的证明

由于计算安全不是完美安全，因此，只要时间充足，计算安全的密码方案总能被攻破。

如果要证明密码方案是计算安全的，我们需要证明破解该方案需要的时间下限。但实际上，我们也没有办法证明这个时间下限。

我们现在采用的证明方法是：

假设某个难题很难解决，则基于这个假设，构造的加密方案也是安全的。

4、伪随机性

如果密文是随机的，则密文是均匀分布的，没有泄漏关于明文的任何信息，因此没有攻击者能够从明文获得任何明文的信息。

伪随机性，只是看上去是“随机的”，其实不是。

伪随机bit串的好处是：可以用一个相对短的随机种子或密钥，来生成比较长的伪随机bit串。

5、使用伪随机发生器的加密方案

下面是一个经典的使用伪随机发生器的加密方案：

（1）Gen算法生成随机的密钥k；（2）G为伪随机发生器，G(k, l)根据密钥k，生成一个伪随机的长度为l的bit串；（3）Enc算法，将长度为l的明文m转换为长度为l的密文c，Enc的实现方法是：将m与G(k, l)进行异或；（4）Dec算法，将长度为l的密文c转换为长度为l的明文m，Dec的实现方法是：将c与G(k, l)进行异或。

这个算法中，我们可以自己选择伪随机生成器。

实际上，这是一种不错的对称加密算法的实现思路。