密码学-常规加密体制

《密码学-常规加密体制》由会员分享，可在线阅读，更多相关《密码学-常规加密体制（83页珍藏版）》请在金锄头文库上搜索。

1、信息安全技术之常规分组加密体制,一、分组密码概述,1、分组密码定义 2、通用代换密码结构 3、 Feistel密码结构,1、分组密码定义,分组密码是将明文消息编码表示后的数字序列x0,x1,xi,划分成长为 n 的分组 x=(x0,x1,xn-1)，各组（长为n的矢量）分别在密钥 k=(k0,k1,kt-1) 的控制下变换成等长的输出数字序列 y=(y0,y1,ym-1)（长为m的矢量），该变换必须是可逆的： (y0,y1,ym-1) = Ek(x0,x1,xn-1)，k= (k0,k1,kt-1) (x0,x1,xn-1) = Dk(y0,y1,ym-1) , k= (k0,k1,kt-1)

2、 分组密码实质上是字长为 n 的数字序列的代换密码。 一般情况下有： 1）n = m 2）xi, yi GF(2),2、通用代换密码结构,如果明密文分组的长度都为 n 比特，则每个分组有 2n 个可能的取值，因此，从明文分组到密文分组的可逆变换的总数为：2n! 个。 例如，当n=4时，代换密码的一般结构如下所示:,该代换结构对应的代换表（这样的表显然有 16！=24！个）：,通用代换密码结构,显然，可以采用上述（明文分组、密文分组）表格来定义分组密码，表示明、密文间的任何一种可逆变换，一个代换表相当于一个密钥。 使用通用代换结构构造分组密码的问题： 1）为了表达 n 比特分组的任意可逆变换，需

3、要的表达式的总长度为：n 2n bit，是分组长度 n 的指数函数； 2）现代分组密码为了达到计算安全性，要求分组长度 n不能太小(一般要求n=64bit)，否则将等价于古典代换密码； 3）在这种情况下（n=64比特），定义一种变换需要 642641021bit=1.251011GB，这在实现上显然是不可行的。,3、Feistel密码结构的设计动机,Feistel指出我们真正需要的是在n很大时对上述理想分组密码系统的一个近似，这个近似要能够用容易实现的部分组合起来。 Feistel提出，可以用乘积密码的概念对理想的分组密码系统进行近似，采用较短的密钥和简单操作的组合，以接近理想分组系统的性能。

4、,扰乱(confusion)和扩散(diffusion),特别地，Feistel提出交替采用替代和置换的方式构造密码，这正是Shannon关于用扰乱和扩散交替的方法构造乘积密码的一个实际应用。 所谓扩散，是让明文的每个数字影响许多密文数字的取值，使明文的统计结构被扩散消失到密文的长程统计特性中。 而扰乱是使密文的统计特性和密钥的取值之间的关系尽量复杂，以挫败发现密钥的尝试。 扩散和扰乱非常成功地抓住了分组密码应该具有的特性的本质，因此成为现代分组密码设计的基础。,Feistel密码结构,Feistel密码结构是Shannon提出的替代-置换网络SPN的一种特殊形式。 该算法的输入是长度为2w比

5、特的明文分组和一个密钥k，明文分组被分成两个部分L0和R0，这两个部分经过n轮处理后组合起来产生密文分组。每一轮 i 以从前一轮得到的Li-1和Ri-1为输入，另外的输入还有从总的密钥K中生成的子密钥Ki。 算法的每一轮都对数据的右边一半应用round函数F(在各轮子密钥的参与下)，然后将函数的输出和数据的左边一半做异或。 在上述操作后，算法把数据的两个部分互换。,Feistel密码设计特点的选择,分组大小(一般为64比特) 密钥大小(一般为56, 64, 128比特) 循环次数(一般为16轮) 以上三点的值越大越安全，但加密速度会越慢 子密钥产生算法 Round函数 以上两点越复杂越安全，但

6、加密速度会越慢 快速的软件加密/解密 便于分析 使算法的安全性容易得到证实,Feistel解密算法,Feistel密码的解密过程与其加密过程实质上是相同的，解密规则如下：以密文作为算法的输入，但是以相反的次序使用子密钥Ki。 Feistel解密正确性的证明,二、数据加密标准DES,1、DES概况； 2、DES算法描述； 3、DES的安全性和强度。,1、数据加密标准(DES),DES Data Encryption Standard； DES是第一个得到广泛应用的密码算法； DES是一种单钥分组密码体制； DES的明密文分组均为64比特； DES的密钥长度为64比特，但每隔8比特位是一个奇偶校验

7、位，其实际密钥长度为56比特；,DES的历史和意义,DES出现之前； 1972，NBS为保护计算机和通信安全，提出开发一个单独的标准加密算法，并于1973年提出具体需求（见下页）； IBM提出LUCIFER算法作为候选； NBS在NSA的协助下对LUCIFER进行评估和修改，并公开了算法细节，征求各研究机构和学者的评论； 经过激烈讨论和责难，经过修改的算法于1976年11月被采纳作为联邦标准（ FIPS PUB 46，即为DES），允许在非密级的政府通信和商业领域中应用。,NBS提出的具体需求,针对DES的主要争论,争论焦点 DES的密钥长度56比特(Lucifer算法的密钥长度为128比特)

8、； DES内部结构(即S盒)的设计标准没有完全公开。 虽然有以上争论，但DES事实上获得了很大成功，得到了广泛的应用(特别是在金融领域)；,2、DES算法的一般描述,初始置换IP和逆初始置换IP-1,IP和IP-1的作用在于通过变更排列次序将明文打乱，并分成左右两半(各32比特，其中偶数位比特在左边，奇数位比特在右边)。 二者的作用是互逆的。 它们本身没有密码学上的意义，且软件实现困难。 例: IP(675a6967 5e5a6b5a)=(ffb2194d 004df6fb),DES每个循环的详细过程,DES每个循环的详细过程,每轮函数的处理过程公式为 Li = Ri1 Ri = Li1 xo

9、r F(Ri1, Ki) 其中F(Ri1, Ki)是在48比特子密钥的参与下，对右边32比特进行如下操作 1）扩展置换到48比特 2）与48比特子密钥按位异或 3）经过8个S盒进行非线性变换, 生成32比特输出 4）该32比特再经过一个置换，产生最后输出,选择扩展置换E,选择扩展运算E将输入的32比特扩展成48比特，使输出对输入的依赖性更强，传播更快(造成雪崩效应),S盒代换结构,S盒运算方法及意义,S盒的每一行定义了一个4比特的可逆变换。 S盒选择方式：假设输入的6比特为s0s1s2s3s4s5，则s0s5构成一个2比特的数，对应于S盒中的一行，s1s4构成一个4比特的数，对应于S盒中的一列

10、，行列相交的数即为S盒的4比特输出。 S盒是DES中唯一的非线性部件，可以对输入进行混乱。它的安全性和设计原则是DES的关键 例: S盒1如下,输入为100101,则输出为: 8（1000）,置换 P,DES子密钥产生,DES子密钥产生,置换选择PC-1和PC-2 循环左移次数,DES的解密,和任何Feistel密码一样，DES的解密使用和加密一样的算法，不过子密钥的使用次序要反过来。如果加密的子密钥顺序为k1k16，则相应解密的子密钥顺序为k16k1。,DES的雪崩效应,雪崩效应指明文或密钥的一点小的变动，都能使密文发生一个大的变化。 DES具有很强的雪崩效应。 其中一个特例的情况如下,DE

11、S的弱密钥,如果一个主密钥所产生的16个子密钥都相同，这个主密钥就是弱密钥（Weak Key）； 显然弱密钥满足： DESk DESk (m) =m； DES有4个弱密钥：,DES的半弱密钥,如果一个主密钥在16轮中只产生两个不同的子密钥，每个被使用8次，这个主密钥就是半弱密钥（semi-weak key）。 DES有12个这样的半弱密钥（分成6对，每一对半弱密钥满足 DESk DESk(m) =m）： 01FE 01FE 01FE 01FE 和 FE01 FE01 FE01 FE01 1FE0 1FE0 1FE0 1FE0 和 E01F E01F E01F E01F 01E0 01E0 01

12、E0 01E0 和 E001 E001 E001 E001 1FFE 1FFE 1FFE 1FFE 和 FE1F FE1F FE1F FE1F 011F 011F 011F 011F 和 1F01 1F01 1F01 1F01 E0FE E0FE E0FE E0FE 和 FEE0 FEE0 FEE0 FEE0,DES的半弱密钥,此外DES还有只产生4个不同子密钥的密钥，每个子密钥在算法中被使用4次，总共大约有48个这样的密钥。 所有这些（半）弱密钥在DES的整个密钥空间（ 256=7.2*1016 ）中所占的比例是极小的，如果密钥随机选取，选中（半）弱密钥的概率可以忽略。也可以采用判断的方式保

13、证不会使用（半）弱密钥。,3、DES的强度,56比特密钥(共256=7.2*1016个)的使用 穷举搜索,DES的强度,Wiener的分析设计 RSA公司的破解密钥比赛：获胜者用了96天,这个比赛显示了分布式个人计算机在对付密码分析问题时的威力。,对DES的分析攻击,差分分析 差分分析对于选择性明文攻击，是一个很有效的方法。对于攻击8轮DES，在486那样的计算机上，只需2分钟可攻破。 线性分析,三、分组密码的操作方式,1、概况 2、电子密码本模式(ECB) 3、密码分组链接模式(CBC) 4、密码反馈模式(CFB) 5、输出反馈模式(OFB),1、分组密码的操作方式,DES(分组密码)通常对

14、固定的明密文分组进行操作，提供了数据安全的一个基本构件; 为了在各种应用场合使用DES,定义了四种“操作方式”(ANSI X3.106-1983 Modes of Use) 这四种模式基本覆盖了所有可能的应用场合，如加密单个数据、任意长度数据、流式数据;,2、电子密码本模式(ECB),ECBElectronic Code Book 在该模式下，明文被分成独立的64bit分组，在相同密钥的作用下加密成独立的64bit密文分组，Ci = DESK(Pi) ECB模式对于加密少量数据(比如一个加密密钥)来说很理想，效率最高； 但对于长报文,ECB模式的安全性较差 明文分组中的重复模式可能在密文分组中

15、同样表现出来,ECB模式示意图,3、密码分组链接模式(CBC),CBCCipher Block Chaining 在该模式下，加密算法的输入是当前的明文分组和前边一组密文分组的异或，同时当前密文分组要与下一组明文异或，这样就将明文分组序列的处理连接起来了；对每个分组使用相同的密钥。 为了对第一组明文加密，需要使用初始向量IV( Initial Vector)； Ci = DESK (Pi XOR Ci-1) C0 = IV 该方法适用于对长度大于64比特的任意长度数据加密，同时可用于鉴别。,CBC模式示意图,CBC模式的正确性,加密,解密,CBC模式的优点和局限,在CBC模式下，每个密文分组依

16、赖于它以前的所有明文分组，同时，明文中1比特的变化也将使其后的所有密文分组发生改变。因此，每个明文分组的加密函数的输入与明文分组之间不再具有固定的关系，64比特的重复模式不再会出现。 IV需要收发双方都知道 如果IV是明文,则攻击者可能更改第一个明文分组,同时依靠修改IV来补偿,使接收者被欺骗； 因此IV必须是一个固定的值，或者向密钥一样受到保护。 具有长度为2的错误传播 密文中一个分组的传输错误将引起解密时两个明文分组的错误； 如果最后一个明文分组不到64比特，则必须处理 如：采用填充指示符(PI) b1 b2 b3 0 0 0 0 5 - 3 字节数据, 5 字节填充(包括PI),4、密码反馈模式(CFB),CFB(Cipher Feedback Mode) CFB模式将DES转换为一个流密码来使用，这样，不再要求明文分组被填充成整数个分组，可以实时运行。 CFB模式同样将密文反馈到输入端，与明文进行异或，以产生下一组密文。 CFB模式一次对j比特进行加密，j可以从1到64的任意值，通