Dan Boneh密码学笔记2

这一篇记录了长达两个小时的全英文斯坦福密码学课。

实际上我的学习时间得在四个小时才够，而且得是脑子清醒的四个小时。这还是刚开始简单的流密码......感觉也就听懂了90%，真正消化完......尤其那些安全性的证明，太刺激了。

密码学，还是有门槛的。

但是这样做笔记，虽然别人看不懂，但是确实是一个很好的学习方式，帮助我加深印象，促使我更认真听课。

Stream ciphers

1.The One Time Pad（OTP）

1.1简介

对称加密：

-加密算法是随机算法

-解密算法是确定算法

一次性密码本，密钥空间和明文空间一样，K=C=M

key = (random bit string as long as message)

证明了一次性密码本却是是密码，但没有解释其安全性

缺点是，密钥需要与明文一样长。

1.2安全性证明

完美安全的定义：

k在K（密钥空间）上均匀分布。密钥分布是均匀的。Pr表示概率

adv.攻击者，PT=plain text明文，CT密文

概率就是能将m映射到c的密钥数除以全体密钥的个数

#表示数量

不能被惟密文攻击。

很难用，过长的密钥。

2.Stream Ciphers

2.1流密码，使OTP变得更加实用

流密码，密钥不是完全随机的，使用一种伪随机密钥PRG（pseudorandom）

PRG是个函数G，n远大于s。seed是G的输入，输出看起来是随机的。

使用种子K作为私钥，使用发生器G将种子扩张成长得多的看起来很随机的序列G（K）。

2.2流密码不是完美安全的密码

PRG必须不可预测。因为如果攻击者得知明文的前缀，可以推出伪随机序列的前缀，进而计算出序列的其他部分，从而还原整个明文。

eff，存在有效算法，该算法记为A，并且，有一个位置为i位于0到n-1之间

如果我们看分布在随机密钥上的概率，我生成一个随机密钥，这个记号表示从密钥空间K中随机选取一个密钥。这个带r的箭头表示从K中随机选取一个密钥。如果我把输出前缀输入给这个算法A，我给输出的前i个字节，该算法能预测出下一位的概率大于1/2+Epislon。对于一些不可忽略的量，表示为Epislon。

PRG必须是不可预测的，对于所有的位置i，都没有有效的破解算法A以不可忽略的概率预测出第i+1位。

2.3一些脆弱的PRG千万不要用

比如：

1、线性同余方法：有三个参数A、B、P，A、B是整数，P是一个质数。r[0]是种子发生器。

这种方法有统计特征，容易被预测，不应该使用。

2、glibc发生器，容易被预测，不应该使用。

3.Attacks on OTP and stream ciphers

3.1第一种攻击：两次密码本攻击

使用同样的密钥加密多条消息，攻击者截获密文，可以破解出原文。

所以，流密码的密钥使用次数不应该超过一次。

3.2举例

3.2.1多条信息串联再加密，被破解。永远不要使用相同密钥加密两个方向的流量。

WEP反面教材。流密码加密，为了密钥每次不同， 每次IV+1，直接发送密文，接受方也知道密钥K，也知道IV，就能通过联结IV和K来重新推出PRG来，然后就能解密密文，还原明文m了。

每经过1600万帧循环一次，IV重0开始循环。两次密码吧，K不变，破解。

更惨的是，重启系统，IV重置到0.

在WEP中PRG用的是RC4算法，2001年，有人提出，约一百万帧后可以还原密钥。

更好的解决方案，把K分组，加密不同帧。密钥看起来更加独立。

3.2.2最后一个例子，硬盘加密

3.3第二种攻击方式：不完整性，OTP是可修改的。

4.Example Stream Ciphers

4.1两个老例子。

4.1.1.RC4

两个弱点，1，不够随机。2，数据量大时i，00序列出现的可能性大。

4.1.2.CSS

加密DVD电影，混淆系统CSS，面向硬件设计的流密码，基于线性反馈移位寄存器LFSR。右移，最后一位扔掉，第一位是之前的异或结果。

LFSR的种子就是寄存器的初始状态。

DVD\GSM（全球移动通信）\蓝牙，里面的这些算法都被完全破解了。

CSS用了两个LFSR，一个17位一个25位。

种子是，第一个的是1+key的前两个字节=17bits

第二个是1+key的后三个字节=25bits

两个LFSR运行8次，输出8位，相加，mod256，一轮输出一个字节。这个字节和电影数据里的字节进行异或加密，CSS是个简单的流密码。

2^17次可以破解。很容易。

4.2再看两个好点的例子。

4.2.1.eStream

nonce(新鲜值)只要密钥定下来，永不重复的唯一值。

此处PRG需要密钥和新鲜值两个输入。

输入表示成（k,r）（密钥，新鲜值）这个有序对永不重复。它不能被多次使用。

底线是可以重复使用密钥，因为新鲜值确保了有序对唯一（k,r）只使用一次。

这样我们不必每次换密钥了。

4.2.2salsa20

先把状态扩充至64字节长：

4B常数Tau0

16B密钥K

4B常数Tau1

8B新鲜值

8B索引index

4B常数Tau2

16B密钥K

4B常数Tau3

接下来进行十次H函数操作。

给定最后的输出，很容易求h的逆，然后回到最初的输入，测出输入的正确结构。

目前salsa还没有重大攻击，其安全性接近于2^128。非常快的流密码。

额stream有五个这样的项目，这次只讲了salsa。

5.PRG Security Defs

5.1 PRG，有密钥空间K，即N位字符串的集合。

PRG要做的，从集合K中，均匀随机选取，再输出。伪随机密钥。

我们要做的就是让攻击者无法辨认出我们的seed密钥集合。

What we're arguing is that an adversary who looks at the output of the generator in this tiny set can't distinguish it from the output of the uniform distribution over the entire set.

5.2 统计测试算法

How to define this concept of indistinguishability from random.

A(x)=1, X中的1和0个数相差小于10*sqr(n),则说X是随机的。

5.3 advantage

好的PRG=统计测试输出1的概率 - 输入是真随机字符串输入1的概率

若结果接近1，说明PRG的效果差被破解，我们可以区分出伪随机序列和真随机序列。

若结果接近0，PRG不错。

这个测试不考虑输入，其实根本无法区分真伪随机。

1/6不可忽略，说明这个发生器不好，被破解了。

所以，综上所述，我们定义安全的PRG：

A值必须接近0可以忽略，才算安全。

我们不能严格地证明某个PRG是安全的。

相当于这是个逆否命题。

5.4接下来谈一下这个定义的一些应用和影响

1）安全的PRG是不可预测的。

-给定PRG输出的前缀，是不可能预测出输出的下一位是什么的。

反证法，证明它的逆否命题。

2）一个不可预测的PRG是安全的（姚期智）

Next-bit predictors 泛指预测算法

If next-bit predictors cannot distinguish G from random then no statistical test can！

5.5一些重要的概念、记号

P1和P2这两个分布，可不可区分呢？

在多项式里，计算上不可区分，记为P1≈p P2

这个记号，使用它来表述安全PRG的定义

一个安全的PRG，给出一个伪随机分布，这个分布与均匀分布计算上是不可区分的。

6.Semantic security（语义安全）

6.1我们如何定义流密码安全

从攻击者的角度定义：

1.不应该从还原密钥的角度来定义安全。

2.不应该从还原所有明文的角度来定义安全

香农Shanon的完美安全定义：

当攻击者截获密文时，他不能获得任何明文的信息，还不能够预测明文中的任何一位。

6.2回顾，香农的完美安全定义

这个定义有些太强了，需要很长的密钥。

减弱一下定义，攻击者无法区分两个分布。这个定义还是有些太强了。

再减弱一下，前提条件，对所有的m0和m1都成立，改为对攻击者能想到的明文m0和m1成立。

6.3语义安全的定义

攻击者A发出等长的m0和m1，挑战者选取随机密钥k发出m0或m1的加密结果。

在实验0里，挑战者输出m0的加密

在实验1里，挑战者输出m1的加密

攻击者视图试图去猜他得到的是m0还是m1的加密

定义事件Wb为在实验b中攻击者输出1的所有事件

接下来，这就是攻击者A对加密机制E的语义安全的优势

定义两个事件概率的差距

Adv趋近于1，意味着攻击者能很好地区分实验0和1，也就是可以区分M0和M1的加密。

Adv趋近于0，意味着攻击者不能区分实验0和1。

E是一个对称加密机制，是语义安全的。对所有有效的攻击者(破解成功)，优势可以忽略(Adv~0)。

总的来说，就是攻击者获得m0和m11，无法区分这两个分布。

6.4一个不安全的例子：

假设我们有个被破解的加密机制E，LSB of PT明文的最低位。

OTP一次性密码本是语义安全的

K异或m0的分布和K异或m1的分布是一样的。这些分部是绝对同分布。这是异或的性质。

OTP是语义安全的，对所有攻击者都是有效的。

7.Stream ciphers are semantically secure

现在我们理解了安全PRG和语义安全，我们可以证明用安全PRG的流密码是语义安全的。

流密码不可能满足香农的完美安全。

我们将多次使用语义安全这个概念。

要证明用安全PRG的流密码是语义安全的。

先证明它的逆否命题。

若A优势不可忽略，则我们能构造出B来破解PRG，即PRG不安全。