斯坦福大学密码学-分组密码 03

ppt链接：

什么是分组密码？

分组密码取N位明文作为输入，它的输出与输入具有严格相同的位数。

密钥越长，密码工作速度越慢，但是越长越安全。

典型的分组密码以迭代的形式构建。输入密钥k，然后将密钥扩张成一系列的回合密钥 k_1 到 k_n 。使用这些回合密钥一次又一次的迭代使用回合函数加密明文信息。

指定一种类型的分组密码，需要制定密钥扩张的机制，需要制定回合函数。本节只关注回合函数，不会讨论太多密钥扩张的情况。

性能函数。

分组密码比流密码慢的多。

PRPs 和 PRFs

PRP

K：密钥空间 X：输入空间 Y：输出空间

要求是有一个有效的方法能够计算下面这个函数。并不需要是可逆函数。

PRF 更能表明分组密码的特征。

可计算，必须是一一对应的，可逆函数。

PRP的例子。

PRF vs PRP

安全的PRFs

在伪随机函数集上的均匀分布与全体函数上的均匀分布不可区分。

举例说明：

安全的PRFs

安全的PRPs

例题：

应用：PRF \Rightarrow PRG

可并行：有两个处理器，一个计算所有偶数位，一个计算所有奇数位。

安全性是因为 PRF是安全的，意味着PRF和一个真随机函数不可区分，如果G(k)由真随机函数生成，那么G(k)是一个随机的输出

所以用伪随机函数生成的G(k)也是安全的。

分组密码：DES

DES的历史。

有一个经典的网络叫做电子打扫房间，银行利用这个网络来处理支票，DES被用来保护这些事务的完整性。

核心构造-Feistel 网络

函数f并不要求可逆。目的是是d个f函数构成一个可逆函数。

证明构成的 F函数可逆。

DES解密。

定理。

假设有一个安全的伪随机函数，如果在3轮Feistel网络中使用这个函数，最终得到的是一个安全的伪随机置换。

注意：K^3 3个独立的密钥。

DES的构造。

IP 初始置换，IP^{-1} 初始置换的逆置换，与安全无关，只是DES的设置。

函数 F(k_i,x) 。

E-box：复制某些位，移动其它位，例如：将x的第一位被复制到输出的第二位。

S-box：6位映射到4位的函数，使用了一个查找表。

P-box：置换。

S-box。4行16列。

一个糟糕的S-box。

设想一些S盒子仅是将6位输入以不同的方式进行异或，然后输出4位。S盒子是线性的。

线性S盒子是不安全的。如果S盒子是线性的，那么DES所做的无非是计算异或和置换各位，因此所有的DES只是一个线性函数。

这样的DES是不安全的。将三个明文M_1,M_2,M_3 的输出结果异或，可以得到在点 M_1 异或点 M_2 异或点 M_3 处的DES加密结果。这不应该是一个随机函数应该满足的关系，一个随机函数无法满足这个等式。

S盒子和P盒子的选择。

DES中的穷举攻击。

目标：给定输入输出对，找到密钥k。

只要给定了一组输入输出对，那么只有一个密钥k满足 c=DES(k,m) 的概率大于 99.5%。这是穷举攻击实现的核心。

第二个小于号用了并集上限。

如果给定两对DES输入输出，那么唯一的密钥使得其满足的概率非常非常接近于1。

所以，给定两对输出输出文，完全足够进行穷举攻击。

DES的穷举攻击。

DES的加强。

方法1：Triple-DES

为什么不用 2-DES？

meet-in-middle 攻击。

建立解密表2^{56} ,进行排序log(2^{56}) ,然后对解密中的2^{56} 项分别进行查找log(2^{56}) 。

方法2：DESX。

分组密码的其它攻击。

1.旁道攻击。基于时间或者功耗。

2.错误攻击。最后一轮计算错误，极有可能暴露密钥。

3.线性攻击密码分析。

DES第5个S盒子设计的有些问题，有点太接近线性函数了。然后这个线性函数传遍了整个DES，导致了如下的关系。

如何利用上面的关系？取 1/{\varepsilon^2} 个随机的 m,c 对，然后进行异或计算，计算结果中的绝大多数的数值就是密钥的异或值。

应用到DES中

4.量子攻击。

Grover 算法。F是黑盒，量子计算机对于如下的搜索算法，所需时间仅为|X|^{1/2}

在分组密码中的应用。

AES分组密码

AES的历史。

代换置换网络。

代换置换网络每一步都要可逆，并且数据的每一位都要变化。

ByteSub

使用当前值作为查找表的索引，然后输出查找表里的值。

ShiftRow。

MixColumn。一个线性计算。

代码量和性能之间的权衡。

举例。Javascript AES。

发送给浏览器的代码不含有任何预先计算好的表。但当到达了浏览器，则浏览器会预先计算好所需要的表。

硬件中的AES。

运行一次AES，需要运行9次aesenc和1次aesenclast。

AES中的攻击。

AES-256中的密钥扩展有问题。

从伪随机发生器构建分组密码。

PRG \Rightarrow PRF

如果x等于0，我们用左边的输出；如果x等于1，我们用右边的输出。

想要证明左上的分布和左下的随机分布不可区分。因为第一层安全的PRG G与真随机生成器不可区分，所以用真随机值替换PRG的两个输出。再替换下一层，所以都是不可区分的。

如何计算？0往左走，1往右走。

GGM PRF。没有广泛使用的原因是速度很慢。

三回合Feistel网络，即可用安全的PRF构造出安全的PRP。