常规加密的现代技术杨寿保中国科技大学计算机系syang@ustc cn3601540 二六年二月
Network and Information Security(3)
第3章 常规加密的现代技术
本章先介绍一个DES的简化版本,理解算法的工作过程,以及对DES本身的理解讨论对称分组密码的一般原理,讲述完整的DES,并对分组密码设计作一般性讨论.
3.1 简化的DES
S-DES与DES有相似的性质和结构,参数小得多,适用于教学S-DES加密算法输入为8位明文组和10位密钥,输出8位密文加密算法包括5个函数:初始置换IP,复杂函数fk,简单置换函数SW,再次fk, 逆置换函数IP-1
简化的DES工作过程
加密过程: ciphertext = IP-1 (fK2(SW(fK1(IP(plaintext)where K1 = P8(Shift(P10(key)K2 = P8(Shift(Shift(P10(key))))解密过程: plaintext = IP-1(fK1(SW(fK2(IP(ciphertext)))))
对简化DES的分析
对简化DES的穷举攻击是可行的,只有1024种密钥密码分析(考虑已知明文攻击)假设明文为(p1,p2,p3,p4,p5,p6,p7,p8),其密文为(c1,c2,c3,c4,c5,c6,c7,c8),密钥(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)未知,则ci是pj和kj的多项式函数gi加密算法可以表示成10个未知量的8个非线性等式,可能有多个解,但是每一个都可以计算出来并用于分析置换和加法是线性映射,S盒是非线性的.把(p0,0,p0,1,p0,2,p0,3)写作(a,b,c,d),把(p1,0,p1,1,p1,2,p1,3)写作(w,x,y,z),它们的输出是(q,r,s,t),S0的操作可以定义为: q = abcd + ab + ac + b + d r = abcd + abd + ab + ac + ad + a + c + 1 类似地,可以定义S1的方程,10个未知二进制位所表示的多项式有210个可能项,平均而言假定8个方程中的每一个都有29个项
3.2 分组密码的原理
分组密码(Block Cipher)和流密码(Stream Cipher)分组密码 如果经过加密所得到的密文仅与给定的密码算法和密钥有关,与被处理的明文数据在整个明文中的位置无关,则称为分组密码体制.通常以大于等于64位的数据块为单位,加密得相同长度的密文.流密码 如果密文不仅与最初给定的算法和密钥有关,同时也与明文位置有关(是所处位置的函数),则称为流密码体制.加密以明文比特为单位,以伪随机序列与明文序列模2加后,作为密文序列,一次一比特或字节.
分组密码大多数分组密码基于 Feistel Cipher Structure分组加密器本质上就是一个巨大的替换器64位的分组就会有 264种输入采用了乘积加密器的思想Feistel密码结构的设计动机分组密码对n比特的明文分组进行操作,产生一个n比特的密文分组,共有2n个不同的明文分组,每一种都必须产生一个唯一的密文分组,这种变换称为可逆的或非奇异的.可逆映射 不可逆映射 00 11 00 11 01 10 01 10 10 00 10 01 11 01 11 01
n = 4时的一个普通代换密码的结构
Feistel密码Claude Shannon and Substitution-Permutation Ciphers 1949年,Claude Shannon 引进了substitution-permutation (S-P) networks的思想,即现代的乘积加密器modern substitution-transposition product cipher,形成了现代分组加密的基础.S-P networks 是基于替代substitution (S-box)和置换permutation (P-box)这两个基本操作的.提供了对明文信息处理所做的confusion和diffusion .Shannon认为,为了对付基于统计分析的密码破译,必须对明文作confusion(扰乱)和diffusion(扩散)处理,以减少密文的统计特性,为统计分析制造障碍.diffusion – dissipates statistical structure of plaintext over bulk of ciphertext,明文统计结构扩散消失到大批密文统计特性中,使明文和密文之间统计关系尽量复杂;confusion – makes relationship between ciphertext and key as complex as possible,使密文和加密密钥之间的关系尽量复杂.
Feistel密码结构1973年,Horst Feistel提出了基于可逆乘积加密器概念的Feistel Cipher:将输入分组分成左右两部分,实施Shannon's的substitution-permutation network 概念对左半部数据实施多回合的替代操作(substitution)对右半部数据和子密钥应用round函数F,其输出与左一半做异或将这两部分进行互换(permutation swapping)
Feistel加密器设计原则分组长度:分组越长则安全性越高,但加/解密速度越低,分组长度为64位是一个合理的折衷密钥长度:密钥越长越安全,但加/解密速度越低,64位长的密钥已被证明是不安全的,128位是常用的长度迭代次数:迭代越多越安全,通常为16次迭代子密钥产生算法:越复杂则密码分析越困难Round循环函数:越复杂则抗密码分析的能力越强快速的软件加密/解密:算法的执行速度很重要简化分析难度:算法简洁清楚,易于分析弱点,发现密码Feistel解密算法:以密文作为算法的输入,以相反的次序使用密钥Ki,Kn、Kn-1、...、K0.
Feistel Cipher Encryption and Decryption
历史的回顾IBM developed Lucifer cipher (1971)by team led by Horst Feistelused 64-bit data blocks with 128-bit keyTuchman-Mayer redeveloped as a commercial cipher with input from NSA and others, 56-bit key, easy to implement on single chipin 1973 NBS issued request for proposals for a national cipher standardIBM submitted their revised Lucifer which was eventually accepted as the DESDES加密
3.3 数据加密标准
DES加密算法的一般描述
初始置换IP (Initial Permutation)和逆置换IP-1
扩展置换和置换函数
循环细节将明文分成左右两部分,如Feistel cipher:Li = Ri–1Ri = Li–1 xor F(Ri–1, Ki)将32-bit右半部和48-bit子密钥做以下动作:expands R to 48-bits using permutation Eadds to subkeypasses through 8 S-boxes to get 32-bit resultfinally permutes this using 32-bit perm P
Substitution Boxes S
Have eight S-boxes which map 6 to 4 bits Each S-box is actually 6 to 4 bit boxes outer bits 1 & 6 (row bits) select one rows inner bits 2-5 (col bits) are substituted result is 8 lots of 4 bits, or 32 bitsRow selection depends on both data & keyfeature known as autoclaving (autokeying)Example S(18 09 12 3d 11 17 38 39) = 5fd25e03
子密钥的产生
Forms subkeys used in each roundConsists of:initial permutation of the key (PC1) which selects 56-bits in two 28-bit halves 16 stages consisting of: selecting 24-bits from each half permuting them by PC2 for use in function f, rotating each half separately eit
……

欲阅读全文，请下载！