斯坦福大学密码学-流密码 02

ppt 链接：

The One Time Pad 一次性密码本

定义。什么是对称加密？

有效加引号：理论上：必须在多项式时间内完成。应用上：在特定时间内完成(例如：一分钟内加密1G的数据)。

一次性密码本加密过程

$M=C=\{0,1\}^n,k=\{0,1\}^n\\ C:=E(k,m)=k\oplus m\\ \ \ \ \ \ \ \ \ \ D(k,m)=k\oplus c$

优点 加密速度很快。

缺点 密钥需要和明文一样长。

什么是一个安全的加密？

Shannon 的观点：

证明OPT是完美安全的。

#keys key的数目。

计算出 $\underset{k}{Pr}[E(k,m)=c]$ 是一个常量，说明对于任意m和c而言，概率一样，所以是完美安全的。

问题。

答案为1.证明：

OPT 唯密文攻击不可能。

如果一个密码是完美安全的，其全体密钥数，不少于其能处理的明文数。OPT很难应用于实践。

流密码：伪随机生成器。

因为OPT并不实用，所以用流密码在OPT的基础上让其更加实用。原理是用伪随机生成器替换掉随机生成器。

伪随机生成器是确定的函数。

加解密过程。

流密码不是完美安全的，因为密钥的长度小于明文的长度。

PRG必须是不可预测的。如果可预测的话，攻击者知道一段密文对应的明文，可以计算出密钥的前一部分，然后根据可预测，计算后面的密钥，明文被还原出来。只可预测一位也是不可以的，这样可以一位一位的恢复出密钥。

可预测和不可预测定义。

弱伪随机生成器。

线性同余算法，A、B是整数，P是一个质数，不可用，可预测。glibc C语言库中的随机生成函数不应该用。

可忽略vs不可忽略。

密码学不同的领域不同的定义。实用派和理论派。

理论派：讨论事件概率时，不会对概率定值进行讨论，而是把它看作一个安全参数的函数，它是对一个从自然数域到实数域的函数做定义的，这些函数本质上输出正实数，这些非负实数被认为是概率，函数的定义域是非负整数。

如果这个函数对足够大的x，该函数都小于任意多项式函数的倒数，则说这个函数是可忽略的。

举例。

$1/2^{\lambda}$是可忽略的，因为他的分母是指数的，比多项式增长还快，因此，他比任意多项式函数的倒数增长得慢很多。 $1/\lambda^{10000}$是不可忽略的，因为存在多项式比这个式子的分母增长得还快（例如10000次方），因此这个函数是不可忽略的。

也就是说如果要可忽略的话，分母要比多项式函数还高阶。

注意：

对OPT和流密码的攻击。

攻击1 两次密码本攻击。

举例：

1.苏联人掷骰子生成密钥。比较麻烦，一条密钥加密好几条消息。

2.MS-PPTP (windows NT)。PPTP协议是一个点到点协议。客户端加密的信息被当成一个长流，使用相同密钥加密，问题在于，服务端也在进行相同的事情。

3.802.11b WEP：802.11b 协议中包含了一个加密层，叫做WEP。

IV为24比特，每个数据包的IV不同，于是每个数据包的IV加一。

问题在于：

1.IV只有24比特，也就是说，经过1600万帧的传输后，IV又要从0开始循环了，这就造成了二次密码本。并且电脑重启后，IV也会从0开始计数，这样就造成了更多的二次密码本。

2.密钥之间紧密关联，容易造成攻击。

解决办法：对帧进行处理，再次使用PRG，首先用PRG得到一个长流，然后分组，对每一个帧再次使用PRG。

4.硬盘加密。两个不同的消息让攻击者知道改变了什么？甚至怎么改变的？

一次性加密不是用来加密硬盘的好点子。

总结：

攻击2：不提供完整性保护。(可修改性)

结果为 $m \oplus p$ ,无法检测对还原的明文有特定的影响。

篡改邮件的发送者。

流密码：实际应用。

RC4

面向软件设计。RC4的种子长度可变。

缺点：1.不够随机。2.(0,0)输出概率大。3.相关密钥关联。

CSS

加密DVD，混淆系统CSS。已经被完全破解。面向硬件设计的流密码。

线性反馈移位寄存器(LFSR)：

LISR是由若干单位组成的寄存器，每个单位含一位，接着对特定的单元由出头，不是全部单元都有，特定的位置叫出头，然后，这些出头被异或。在每一个时钟周期，寄存器向右移一位，最右位被遗弃，而异或结果被当作第一位。

CSS：种子为5字节，40字节。用两个LISR寄存器，一个是17比特的LISR，种子构成是 1||种子的前两个字节。一个是25比特的LISR，种子构成是 1||种子的后三个字节。运行八轮，输出8位，然后相加，取模256。

破译：

eStream

eStream: Salsa 20

面向软件和硬件。

性能参数。

流密码：PRG安全性定义。

伪随机与真随机不可区分。

统计测试。

A(X) X是随机字符串。

1.对于一个随机字符串，0的个数和1的个数大体相等。

2.对于一个随机字符串，00的概率大约是四分之一。

3.对于一个随机字符串，在字符串中最长的连续的0大约是log N(2为底数)。

如何评估一个统计测试？引入了优势的概念。

最后答案是0。

举例：

1/6 是个很大的值了，A可以区分。

什么是安全的PRG？对所有有效的统计测试，如果看优势，统计测试A对G的优势基本上是可忽略的。

注意：有效指在多项式时间内完成的测试。

是否有安全的PRG？不知道。但是如果说没有安全的PRG，则意味着 $P=NP$

安全的PRG是不可预测的。

逆否命题。

意味着如果A可以以优势$\varepsilon$ 预测下一位，那么测试算法B可以以优势$\varepsilon$ 区分出发生器的输出序列。

逆否命题：如果G安全，那么没有任何好的统计测试，也就没有任何好的预测算法。 发生器不可预测。

一个不可预测的PRG是安全的。

next-bit predictors 泛指预测算法。

习题：不用构造一个预测算法，证明其存在。容易构造一个统计测试来区分G的输出和均匀分布的序列，所以G不安全。意味着G是可预测的。

推广。

流密码：语义安全。

什么是安全的密码？

Shannon的完美安全。

我们不要求两个分布绝对相同，我们要求两个分布在计算上不可区分。

只对攻击者能想到的明文 $m_0,m_1 \in M$ 满足。

一次性密码本的语义安全。

在实验0中，给攻击者$M_0$ 的加密。在实验1中，给攻击者$M_1$ 的加密。

注：$W_b$ 表示在实验b中攻击者输出1的概率。

我们对攻击者在哪个实验中输出1感兴趣。如果在两个实验中攻击者以同样的概率输出1，意味着攻击者无法区分两个实验。

如果在两个实验中攻击者输出1的概率非常不一样，意味着攻击者可以区分两个实验。

定义

举例：

有个被破解的加密机制。有攻击者A，给定密文，能够推出明文的最低位。

这个系统不是语义安全的。

OPT是语义安全还是完美安全？ 都是，OPT是完美安全，也是语义安全。

最后是0。

流密码：流密码是语义安全的。

用安全的PRG构成的流密码是语义安全的。(注意流密码不是完美安全的。因为它的密钥太短)

如何证明上面的定理呢？证明逆否命题。

假设有一威胁语义安全的攻击者A，我们将构造一个PRG攻击者B，以满足以下的不等式。

如果B是一个有效的攻击者，由于G是安全的，那么$Adv_{PRG}[B,G]$ 是可以忽略的。这样的话，左边也是可忽略的。得证。

所以，给定A，我们要构造B。

首先A，和挑战者A玩一个游戏。就是攻击者不能判断我们是否从伪随机字符串切换到了真随机字符串。如果是真随机字符串的话，那么就是OPT。OPT已经被证明了是语义安全。

证明 $W_0$ 和 $W_1$ 实际上很接近 $R_b$ 的概率，从而它们彼此也很接近。

证明论断2

按需要构建统计测试B，内部使用攻击者A。

证明完毕。