分组加密和DES

分组密码是一种加密解密算法,将输入明文分组当做一个整体处理,输出一个等长的密文分组。
许多分组密码都采用Feistel结构,这样的结构由许多相同的轮函数组成。每一轮里,对输入数据的一半进行代换,接着用一个置换来交换数据的两个部分,扩展初始的密钥使得每一轮使用不同的子密钥。
DES是应用最为广泛的分组密码,它扩展了经典的Feistel结构。DES的分组和密钥分别是64位和56位的。

乘积密码的设计思想

1949年,Claude Shannon 引进了substitution-permutation (S-P) networks的思想,即现代的乘积加密器,形成了现代分组加密的基础。S-P Networks 是基于替代和置换这两个基本操作的。

提供了对明文信息处理所做的confusion和diffusion

Shannon认为,为了对付基于统计分析的密码破译,必须对明文作confusion(混淆)和diffusion(扩散)处理,以减少密文的统计特性,为统计分析制造障碍。

diffusion

明文统计结构扩散消失到大批密文统计特性中,使明文和密文之间统计关系尽量复杂;

confusion

混淆,使密文和加密密钥之间的关系尽量复杂。

Feistel密码结构的设计动机

分组密码

  • 大多数分组密码基于 Feistel Cipher Structure
  • 分组加密器本质上就是一个巨大的替换器
  • 64位的分组就有 264种输入
  • 采用了乘积加密器的思想,即轮流使用替代和置换

Feistel密码结构的设计动机

分组密码对n比特的明文分组进行操作,产生一个n比特的密文分组,共有2n个不同的明文分组,每一种都必须产生一个唯一的密文分组,这种变换称为可逆的或非奇异的。

有两个图

Feistel密码结构

1973年,Horst Feistel提出了基于可逆乘积加密器概念的Feistel Cipher:
将输入分组分成左右两部分,实施Shannon’s的substitution-permutation network 概念
对左半部数据实施多回合的替代操作(substitution)
对右半部数据和子密钥应用轮函数F,其输出与左一半做异或
将这两部分进行互换(permutation swapping)

有一个图

Feistel加密器设计原则

  • 分组长度:分组越长则安全性越高,但加/解密速度越低,分组长度为64位是一个合理的折衷
  • 密钥长度:密钥越长越安全,但加/解密速度越低,64位长的密钥已被证明是不安全的,128位是常用的长度
  • 迭代次数:迭代越多越安全,通常为16次迭代
  • 子密钥产生算法:越复杂则密码分析越困难
  • 轮循环函数:越复杂则抗密码分析的能力越强
  • 快速的软件加密/解密:算法的执行速度很重要
  • 简化分析难度:算法简洁清楚,易于分析弱点,发现问题
  • Feistel解密算法:以密文作为算法的输入,以相反的次序使用密钥$K_i,K_n、K_{n-1}、…、K_0$.

有一个图

DES

历史

  • IBM公司在1971年由Horst Feistel领导开发了Lucifer Cipher,使用128位密钥加密64位的分组
  • Tuchman-Mayer在此基础上开发了一个商用密码,使用56位密钥加密64位分组,容易在单个芯片上硬件实现
  • 1973美国国家标准局NBS全面征集加密方案,作为国家密码标准
  • IBM提交了经过修改的Lucifer加密器,并最终在1976年被接受,公布为数据加密标准DES

DES加密的一般描述

有一个图

初始置换IP (Initial Permutation)和逆置换$IP^{-1}$

有一个图

扩充置换(E)和置换函数(P)

有一个图

Feistel Cipher分组加密循环细节

将明文分成左右两部分

将32-bit右半部和48-bit子密钥做以下动作

  • 使用置换表E,将32位右半部R扩展成48位
  • 与48位子密钥做异或
  • 48位结果送给8个替换盒S-boxes,得到32位结果
  • 最后使用32位置换表P,把32位结果再进行一次置换处理

有一个图

S盒(Substitution Boxes)

有8个将6位数据映射成4位数据的S盒
6到4的映射规则是

  • 外侧的第1位和第6位用作行选择
  • 其余4位(2-5bit)用作列选择
  • 这样每盒就有4行16列,输出4位,8个S盒输出32位

行的选择依赖于数据和密钥

例如

S(18 09 12 3d 11 17 38 39) = 5fd25e03

有两个图

子密钥的产生

每一轮都要生成一个子密钥以供加密使用

  • 子密钥生成过程包括
  • 使用密钥置换选择1(PC-1),将56位密钥分成两半,每一部分28位
  • 使用置换选择2(PC-2),从每一半中选出24位,形成48位子密钥用在某一轮的F函数中
  • 根据密钥左移表K将这两半分别左移1位或2位
  • 重复置换选择2(PC-2),形成新的48位子密钥用在下一轮的F函数中

有两个图

DES的解密

DES的解密是加密的逆过程,采用相同算法,但是子密钥使用的次序正好相反。

DES加密的雪崩效应

明文或密钥的一比特的变化,引起密文许多比特的改变。如果变化太小,就可能找到一种方法减小有待搜索的明文和密文空间的大小。

如果用同样密钥加密只差一比特的两个明文:

0000000000000000......00000000
1000000000000000......00000000

3次循环以后密文有21个比特不同,16次循环后有34个比特不同

如果用只差一比特的两个密钥加密同样明文:
3次循环以后密文有14个比特不同,16次循环后有35个比特不同

有一个图

DES的安全强度

密钥的长度问题

56-bit 密钥有$2^56$ = 72,057,584,037,927,936 ≈ 7.2亿亿之多

强力搜索( brute force search ) 似乎很困难,20世纪70年代估计要1000-2000年

技术进步使穷举搜索成为可能

  • 1997年1月29日,RSA公司发起破译RC4、RC5、MD2、MD5,以及DES的活动,破译DES奖励10000美金。明文是:Strong cryptography makes the world a safer place. 结果仅搜索了24.6%的密钥空间便得到结果,耗时96天。
  • 1998年在一台专用机上(EFF)只要三天时间即可
  • 1999年在超级计算机上只要22小时!
  • 现在只需要10小时!

S-box问题

其设计标准没有公开,但是迄今没有发现S盒存在致命弱点

计时攻击

计时攻击利用的事实是加密或解密算法对于不同的输入所花的时间有细微的差别
DES能够很好地抵抗计时攻击

差分密码分析攻击问题

DES对差分分析攻击有较好的免疫力
针对DES的密码分析攻击主要利用了加密器的深层结构

  • 搜集加密信息
  • 最终设法恢复部分或全部子密钥的位
  • 如果必要的话对其余部分再辅以穷举搜索
    这些攻击实际上是统计分析,包括
  • 差分分析、线性分析、相关密钥攻击

差分分析和线性分析

1990年,Murphy、Biham和Shamir首次提出用差分密码分析攻击分组密码和散列函数,是第一种可以以少于$2^55$的复杂性对DES进行破译的方法。若有$2^47$个选择明文,用差分分析就可以在$2^47$次加密运算内成功攻击DES。尽管$2^47$比$2^55$小得多,但是要拥有$2^47$个选择明文的条件使得这种方法只具有理论上的意义。对DES并不奏效。

差分密码攻击

假设函数f有许多对具有相同差分的输入,当使用相同的子密钥时产生相同差分的输出。精确地说,若差分为X的所有输入,产生差分为Y的输出占所有输出的百分比为p,则称由差分X导致差分Y的概率为p。

假设有许多X都会以很高的概率产生某些特定的差分,因此如果我们以很高的概率知道Δmi-1和Δmi,就能以很高的概率知道Δmi+1。而且,如果知道很多有关差分的数据,那么确定函数f所使用的子密钥就是可行的。

反复加密已知输入异或的明文对,直到得到期望的输出异或
如果找到

  • 中间轮次有满足所需的异或,则找到了正确的一对输入right pairs
  • 否则找到的是错误的一对输入wrong pairs,对攻击来说比例是S/N

这样可以推测中间轮次使用的密钥值

  • right pairs 说明了同样的密钥位
  • wrong pairs 说明是随机数

对于大轮次加密来说,找到正确的概率很低,要分析的对数比存在的64-bit inputs多

Biham和Shamir表明,13轮的分析可以破解整个16轮的DES

如果使用相同子密钥,对于f,具有系统差值的许多输入对将产生相同的输出差值,即如果在异或值为X的输入对中,有p部分使输出异或值为Y,则X产生Y的概率为p。假定存在很多X,具有很大概率产生一个特定的输出差值。如果已知Δmi-1和Δmi具有很大概率,则Δmi+1也具有很大概率。如果确定很多这样的差值,则容易确定函数f中使用的子密钥。

右图说明差值经过三次循环后的传播情况,输出差值为所示差值的概率为0.25x1x0.25=0.0625

有一个图

线性密码分析Linear Cryptanalysis

是1993年提出的另一种统计攻击,基于找到DES中进行变换的线性近似来进行攻击,可以在有243个已知明文的情况下破译DES密钥,但仍然是不可行的。

基本原理
令明文分组为P[1], …, P[n], 密文分组为C[1], …, C[n],密钥为K[1], …, K[m], 则定义:

A[i, j, ..., k] = A[i]⊕A[j]⊕...⊕A[k]

线性密码分析的目标是找到如下有效线性方程:

P[α1, α2, ..., αa]⊕C[β1, β2, ..., βb] = K[γ1, γ2, ..., γc]

其中,x=0或1;1≤a,b≤n,1≤c≤m,α,β和γ等表示固定的唯一的比特位置。方程以概率p≠0.5成立,p离0.5越远,方程越有效。

对于大量的明文密文对,计算方程左边的值,如果结果中有一半以上为0,则假定K[γ1, γ2, …, γc] =0;如果大多为1,则假定K[γ1, γ2, …, γc] =1。

分组密码的设计原理

S-boxes的设计准则:增加扰乱性

  • 输出比特不应太接近输入比特的一个线性函数
  • 每一行应该包括所有16种比特组合
  • 两个输入相差一个比特,输出必须相差两个比特
  • 如果两个输入刚好在两个中间比特上不同,输出必须在至少两个比特上不同
  • 两个输入前两位不同而最后两位相同,两个输出必须不同
  • 具有非零6比特差值的输入,32对中有不超过8对输出相同

置换P的设计准则:增加扩散性

  • 第i次循环时每个S盒输出的四个比特被分布开,以便其中两个影响下一循环的中间比特,两个影响两端的比特
  • 每个S盒输出的四个比特影响下一循环的6个不同的S盒,并且任何两个都不会影响同一个S盒
  • 如果Sj的一个输出比特影响下一循环Sk的中间比特,则Sk的一个输出比特就不能影响Sj的一个中间比特。

迭代轮数

迭代次数越多则进行密码分析的难度就越大,选择准则是要使已知的密码分析工作量大于简单的穷举密钥搜索的工作量。

函数F的设计

函数F的设计准则(非线性、严格雪崩效应、位独立)
提供扰乱作用,要求强非线性,良好的雪崩性质

S-boxes的设计

  • 希望S盒输入向量的任何变动在输出方都产生看似随机的变动,这两种变动之间的关系应该是非线性的并难以用线性函数近似。
  • S盒的大小:较大的抗攻击能力强,但越大实现越困难
  • S盒的组织:要求高度非线性,随机性

密钥扩展算法

选择子密钥时要使得推测各子密钥和由此推出主密钥的难度尽可能大,应该保证密钥/密文的严格雪崩效应准则和位独立准则