《信息安全概论课件-lecture042》由会员分享,可在线阅读,更多相关《信息安全概论课件-lecture042(92页珍藏版)》请在金锄头文库上搜索。
1、LECTURE042DES分组密码学目 录1.数据加密标准2.公开密钥算法数据加密标准 (Data Encryption Standard,DES)背景发明人:美国IBM公司 W. Tuchman 和 C. Meyer 1971-1972年研制成功 基础:1967年美国Horst Feistel提出的理论 产生:美国国家标准局(NBS)1973年5月到1974年8月两次发布通告,公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案 标准化:DES算法1975年3月公开发表,1977年1月15日由美国国家标准局颁布为数据加密标准(Data Encryption
2、Standard),于1977年7月15日生效背景美国国家安全局(NSA, National Security Agency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议,对算法做了修改,并将密钥长度从LUCIFER方案中的128位压缩到56位 1979年,美国银行协会批准使用DES 1980年,DES成为美国标准化协会(ANSI)标准 1984年2月,ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作DES概述分组加密算法:明文和密文为64位分组长度 对称算法:加密和解密除密钥编排不同外,使用同一算法 密钥长度:56位,但每个第8位
3、为奇偶校验位,可忽略 密钥可为任意的56位数,但存在弱密钥,容易避开 采用混乱和扩散的组合,每个组合先替代后置换,共16轮 只使用了标准的算术和逻辑运算,易于实现DES加密算法的一般描述输入64比特明文数据初始置换IP在密钥控制下 16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特 DES加密过程DES加密过程令i表示迭代次数,表示逐位模2求和,f为 加密函数DES解密过程令i表示迭代次数,表示逐位模2求和,f为 加密函数DES中的各种置换、扩展和替代初始置换IP和初始逆置换IP1 IP和IP1IPIP1Li-1(32比特)Ri-1(32比特)Li(32比特)48比特寄存器选择扩
4、展运算E48比特寄存器子密钥Ki (48比特)32比特寄存器选择压缩运算S置换运算PRi(32比特)Li=Ri-1DES的 一轮迭代扩展置换-盒32位扩展到48位扩展压缩替代S-盒48位压缩到32位共8个S盒S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的构造S-盒的构造DES中其它算法都是线性的,而S-盒运算则是非线性的 S-盒不易于分析,它提供了更好的安全性 所以S-盒是算法的关键所在S-盒的构造准则S盒的每一行是整数0,15的一个置换 没有一个S盒是它输入变量的线性函数 改变S盒的一个输入位至少要引起两位的输出改变 对任何一个S盒和任何一个输入X,S(X)和 S(
5、X001100)至少有两个比特不同(这里X是长度为6的比特串) 对任何一个S盒,对任何一个输入对e,f属于0,1,S(X) S(X11ef00) 对任何一个S盒,如果固定一个输入比特,来看一个固定输出比特的值,这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目S-盒的构造要求S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度 提供了密码算法所必须的混乱作用 如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题 非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门置换p-盒的构造p-盒的构造准则P置换的目的是提供雪崩效应 明文或
6、密钥的一点小的变动都引起密文的较大变化DES中的子密钥的生成密钥置换算法的构造准则设计目标:子密钥的统计独立性和灵活性 实现简单 速度 不存在简单关系:( 给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系) 种子密钥的所有比特对每个子密钥比特的影响大致相同 从一些子密钥比特获得其他的子密钥比特在计算上是难的 没有弱密钥Li-1(32比特)Ri-1(32比特)Li(32比特)48比特寄存器选择扩展运算E48比特寄存器子密钥Ki (48比特)32比特寄存器选择压缩运算S置换运算PRi(32比特)Li=Ri-1DES的 一轮迭代DES加密算法的一般描述DES的工作模式电子密码本 ECB (
7、electronic codebook mode) 密码分组链接 CBC (cipher block chaining) 密码反馈 CFB (cipher feedback) 输出反馈 OFB (output feedback)电子密码本ECBECB的特点简单和有效 可以并行实现 不能隐藏明文的模式信息相同明文生成相同密文,同样信息多次出现造成泄漏 对明文的主动攻击是可能的信息块可被替换、重排、删除、重放 误差传递:密文块损坏仅对应明文块损坏 适合于传输短信息密码分组链接CBCCBC的特点没有已知的并行实现算法 能隐藏明文的模式信息需要共同的初始化向量IV相同明文生成不同密文初始化向量IV可以
8、用来改变第一块 对明文的主动攻击是不容易的信息块不容易被替换、重排、删除、重放误差传递:密文块损坏两明文块损坏 安全性好于ECB 适合于传输长度大于64位的报文,还可以进行用户鉴别, 是大多系统的标准如 SSL、IPSec密码反馈CFB CFB:分组密码流密码假定:Si 为移位寄存器,传输单位为jbit加密: Ci =Pi(EK(Si)的高j位) Si+1=(Si,并且对任意正整数x,计算gx是容易的;但是已知g和y求x使y= gx,是计算上几乎不可能的 这个问题称为有限域F上的离散对数问题。公钥密码学中使用最广泛的有限域为素域FPDiffie-Hellman密钥交换协议描述Alice和Bob
9、协商好一个大素数p,和大的整数g,1 p和g无须保密,可为网络上的所有用户共享Diffie-Hellman密钥交换协议描述当Alice和Bob要进行保密通信时,他们可以按如下步骤来做:(1) Alice选取大的随机数x,并计算 X = gx(mod P)(2) Bob选取大的随机数x,并计算 X = gx (mod P)(3) Alice将X传送给Bob;Bob将X 传送给Alice(4) Alice计算K= (X )X(mod P); Bob计算K =(X) X (mod P), 易见,K = K =g xx (mod P) 由(4)知,Alice和Bob已获得了相同的秘密值K 双方以K作为
10、加解密钥以传统对称密钥算法进行保密通信RSA 算法Euler 函数 所有模m和r同余的整数组成剩余类r 剩余类r中的每一个数和m互素的充要条件是r和m互素 和m互素的同余类数目用(m)表示,称m的Euler函数 当m是素数时,小于m的所有整数均与m互素,因此(m)=m-1 对n=pq, p和q 是素数,(n)=(p)(q)=(p-1)(q-1)Euler 函数举例 设p=3, q=5, 那么(15)=(3-1)*(5-1)=8这8个模15的剩余类是:1,2,4,7,8,11,13,14 RSA算法的实现 实现的步骤如下:Bob为实现者(1) Bob寻找出两个大素数p和q(2) Bob计算出n=
11、pq 和(n)=(p-1)(q-1)(3) Bob选择一个随机数e (0e (n),满足(e,(n)=1(4) Bob使用辗转相除法计算d=e-1(mod(n)(5) Bob在目录中公开n和e作为公钥 密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq,则可以算出(n)(p-1)(q-1),然后由公 开的e,解出秘密的dRSA算法编制 参数T=N; 私钥SK=D; 公钥PK=E;设:明文M,密文C,那么:用公钥作业:ME mod N = C用私钥作业:MD mod N = MRSA算法举例设 p=7, q=17, n=7*17=119; 参数T=n=119; (n)=(7-1
12、)(17-1)=96; 选择e=5, gcd(5,96)=1; 公钥pk=5; 计算d, ( d*e) mod 96=1; d=77; 私钥sk=77;设:明文m=19加密:(19)5 mod 119 = 66脱密:(66)77 mod 119 = 19RSA算法的安全性分析密码分析者攻击RSA体制的关键点在于如何分解n 若分解成功使n=pq,则可以算出(n)(p-1)(q-1),然后由公开的e,解出秘密的d 若使RSA安全,p与q必为足够大的素数,使分析者没有办法在多项式时间内将n分解出来RSA算法的安全性分析建议选择p和q大约是100位的十进制素数 模n的长度要求至少是512比特 EDI攻
13、击标准使用的RSA算法中规定n的长度为512至1024比特位之间,但必须是128的倍数 国际数字签名标准ISO/IEC 9796中规定n的长度位512比特位RSA算法的安全性分析为了抵抗现有的整数分解算法,对RSA模n的素因子p和q还有如下要求:(1) |p-q|很大,通常 p和q的长度相同;(2) p-1 和q-1分别含有大素因子p1和q1(3) P1-1和q1-1分别含有大素因子p2和q2(4) p+1和q+1分别含有大素因子p3和q3RSA算法的安全性分析为了提高加密速度,通常取e为特定的小整数 如EDI国际标准中规定 e2161 ISO/IEC9796中甚至允许取e3 这时加密速度一般比解密速度快10倍以上