ppt链接:
分组密码取N位明文作为输入,它的输出与输入具有严格相同的位数。
密钥越长,密码工作速度越慢,但是越长越安全。
典型的分组密码以迭代的形式构建。输入密钥k,然后将密钥扩张成一系列的回合密钥 k_1 到 k_n 。使用这些回合密钥一次又一次的迭代使用回合函数加密明文信息。
指定一种类型的分组密码,需要制定密钥扩张的机制,需要制定回合函数。本节只关注回合函数,不会讨论太多密钥扩张的情况。
分组密码比流密码慢的多。
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被用来保护这些事务的完整性。
核心构造-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盒子的选择。
目标:给定输入输出对,找到密钥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}
在分组密码中的应用。
代换置换网络每一步都要可逆,并且数据的每一位都要变化。
ByteSub
使用当前值作为查找表的索引,然后输出查找表里的值。
ShiftRow。
MixColumn。一个线性计算。
举例。Javascript AES。
发送给浏览器的代码不含有任何预先计算好的表。但当到达了浏览器,则浏览器会预先计算好所需要的表。
运行一次AES,需要运行9次aesenc和1次aesenclast。
AES-256中的密钥扩展有问题。
PRG \Rightarrow PRF
如果x等于0,我们用左边的输出;如果x等于1,我们用右边的输出。
想要证明左上的分布和左下的随机分布不可区分。因为第一层安全的PRG G与真随机生成器不可区分,所以用真随机值替换PRG的两个输出。再替换下一层,所以都是不可区分的。
如何计算?0往左走,1往右走。
GGM PRF。没有广泛使用的原因是速度很慢。
三回合Feistel网络,即可用安全的PRF构造出安全的PRP。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。