[工学]密码学复习.ppt

1.密码学概述 l主动攻击与被动攻击：对一个保密系统采取 截获密文进行分析的这类攻击方法称为被动攻 击(passive attack)。非法入侵者主动干扰系统 ，采用删除、更改、增添、重放等方法向系统 加入假消息 ，则这种攻击为主动攻击(active attack)。 从攻击效果看，敌手可能达到以下结果： l（1）完全攻破。敌手找到了相应的密钥，从而可以 恢复任意的密文。 l（2）部分攻破。敌手没有找到相应的密钥，但对于 给定的密文，敌手能够获得明文的特定信息。 l（3）密文识别。如对于两个给定的不同明文及其中 一个明文的密文，敌手能够识别出该密文对应于哪个 明文，或者能够识别出给定明文的密文和随机字符串 。 第二章 经典密码学 线性同余密码 将移位密码和乘数密码进行组合就可以得到更多的选择方式，也叫 仿射密码(affine cipher)。 若选取k1，k2两个参数，其中( k1, 26 )1，即 k1 和26互素， 令C k1 mk2 mod 26 k11时便是Kaiser变换。 例如 k17，k210，则明文 please send moneys的对应数据为 16 12 5 1 19 5 19 5 14 4 13 15 14 5 25 19 通过变换c7m10 mod 26可得 18 16 19 17 13 19 13 19 4 12 23 11 4 19 3 13 对应的密文为 R P S Q M S M S D L W K D S C M 习题 l1、对于线性替代密码，设已知明码字母J(9) 对应于密文字母P(15)，即9k mod 26 = 15, 试 计算密钥k以破译此密码。 l 答： k=9-1*15 mod 26 9-1 mod 26=3 k=3*15 mod 26=19 第四章 序列密码 序列密码的加密和解密就是用一个 随机序列与明文序列叠加产生密文，用 同一个随机序列与密文序列叠加来恢复 明文。 若设明文为m，密钥为k，加密后的 密文为c，则加密变换为：cm k，解 密变换：mc k，其中m，k，c是0、1 随机序列，表示模2加法运算。 4.1 序列密码的基本概念 图4.1 序列密码的加密和解密 4.2 密钥流与密钥生成器 一般地，序列密码中对密钥流有如下要求： （1）极大的周期。因为随机序列是非周期的 ，而按任何算法产生的序列都是周期的，因 此应要求密钥流具有尽可能大的周期。 （2）良好的统计特性。随机序列有均匀 的游程分布。游程指序列中相同符号的连 续段，其前后均为异种符号。 如 0 111 0000 10 中3个段分别为长为3的1游程、长为4的0游程、长为1 的1游程。 一般要求其在一周期内满足：同样长度的0游程和1游程 的个数相等，或近似相等。 （3）不能用级数较小的线性移位寄存器近 似代替，即要有很高的线性复杂度。 （4）用统计方法由密钥序列k0 k1 k2 ki 提取密钥生成器结构或种子密钥的足够 信息在计算上是不可能的。 目前密钥流生成器大都是基于移位寄 存器的，这种基于移位寄存器的密钥流序 列称为移位寄存器序列。 4.3 线性反馈移位寄存器序列 移位寄存器是序列密码产生密钥序列 的一个主要组成部分。 GF(2)上一个n级反馈移位寄存器由n个二 元存储器与一个反馈函数f(a1 a2 . an)组 成，如图4.3所示。 图4.3 GF(2)上的n级反馈移位寄存器 每一个存储器称为移位寄存器的一级。 在任一时刻，这些级的内容构成该反馈移位寄存器的状态。 表4.1 三级反馈移位 寄存器的输出状态表 图4.4 一个3级反馈移位寄存器 这个反馈移位寄存器的状态对应于一个GF(2)上的 n维向量 ，共有2n种可能的状态。 每一时刻的状态可用n长序列a1, a2, a3, , an或n维行向量 (a1, a2, a3, , an)表示，其中ai是第i级存储器的内容。 每一级存储器ai都将其内容向下一级ai1传递 ，并根据存储器当前状态计算f(a1, a2, a3, , an)作为an下一时间的内容。 l函f(a1, a2, a3, , an)称为反馈函数，其中 f(a1,a2,a3, an)是n元布尔函数，即n个变元 a1, a2, a3, , an可以独立地取0和1这两个可 能的值.最后的函数值也为0或1。 表4.1 三级反馈移位 寄存器的输出状态表 图4.4 一个3级反馈移位寄存器 三级反馈移位寄存器，其初始状态为(a1,a2,a3)(1,0,1)， 输出可由表4.1求出，其输出序列为10111011101，周期为4。 如果移位寄存器的反馈函数f(a1, a2, , an)是a1, a2, , an的线性函数，则称之为线性 反馈移位寄存器（LFSR）。 此时反馈函数f可写为 f(a1, a2, , an)cn a1 cn1 a2 c1 an， 其中常数ci0或1，是模2加法。 线性反馈移位寄存器（LFSR） f(a1, a2, , a5)a1 a4 图4.6 一个5级线性反馈移位寄存器 n级线性反馈移位寄存器最多有2n个不同的状态。 若其初始状态非0，则其后继状态不会为0。 因此n级线性反馈移位寄存器的状态周期2n -1。 其输出序列的周期与状态周期相等，也2n -1 。 只要选择合适的反馈函数便可使序列的周期达到 最大值2n -1，周期达到最大值的序列称为m序列。 反馈函数:b1+b3 设n级线性移位寄存器的输出序列 ai 满足递推关系 ak+nc1 akn1 c2 akn2 . cn ak， 对任何k1成立。将这种递推关系用一个一 元高次多项式 表示，称这个多项式为线性移位寄存器的连 接多项式。 4.4 线性移位寄存器的一元多项式表示 反馈函数:b1+b3 l反馈函数:b1+b2+b3+b4 试题 l设g(x)=x4+x2+1，g(x)为GF（2）上的多项 式，以其为连接多项式组成线性移位寄存器。 画出逻辑框图。设法遍历其所有状态，并写出 其状态变迁及相应的输出序列。 解答 l l 通常采用的方法是，由线性移位寄存器 (LFSR)和一个非线性组合函数即布尔函数组 合，构成一个密钥流生成器，如图4.2所示 的密钥流生成器。 4.2 密码流生成器 （a）由一个线性移位寄存器和一个滤波 器构成。 （b）由多个线性移位寄存器和一个组合 器构成。 通常将这类生成器分解成两部分，其 中线性移位寄存器部分称为驱动部分，另 一部分称为非线性组合部分。 各自用途 l驱动部分：控制生成器的状态序列，并为非线性 组合部分提供统计性能良好的序列。 l如周期很大；分布较随机 l非线性部分：将驱动部分所提供的序列组合成密 码特性好的序列。 l可隐蔽驱动序列与密钥k之间过分明显的依赖关系 第五章 分组密码 5.2.1 DES加密算法概述 lDES的加密过程可简单描述为三个阶段： 5.2.5 DES的安全性 l对DES安全性的主要争论： 1、对DES的S盒、迭代次数、密钥长度等设计 准则的争议 2、DES存在着一些弱密钥和半弱密钥 3、DES的56位密钥无法抵抗穷举工具 三重DES加密 加密：C=Ek1Dk2Ek1 P 解密：P =Dk1Ek2Dk1C 三重DES加密 两个密钥的三重DES称为加密-解密-加密方案，简记为 EDE(encrypt-decrypt-encrypt)。 l此方案已在ANSI X9.17和ISO 8732标准中采用，并在保密增 强邮递(PEM)系统中得到利用。 l破译它的穷举密钥搜索量为211251035量级，而用差分分析 破译也要超过1052量级。此方案仍有足够的安全性。 l三个密钥的三重DES已在因特网的许多应用（如PGP 和S/MIME）中被采用 习题 *现代密码学理论与实践0544 复习 The AES Cipher *现代密码学理论与实践0545/28 第5章 高级加密标准之要点 lAES是一种分组密码，用以取代DES的商业应 用。其分组长度为128位，密钥长度为128位 、192位或256位 lAES没有使用Feistel结构。每轮由四个独立的 运算组成：字节代换、置换、有限域上的算术 运算，以及与密钥的异或运算 *现代密码学理论与实践0546/28 AES密码 l由比利时密码学家Vincent Rijmen和Joan Daemen 设计 l分组长度，密钥长度可以是128/192/256位 之一 *现代密码学理论与实践0547/28 *现代密码学理论与实践0548/28 *现代密码学理论与实践0549/28 GF(28)上的域元素加法 *现代密码学理论与实践0550/28 乘法 l在多项式表示中，有限域 GF(28)上的乘法(记为 )定义为多项式的乘积模 一个次数为8的不可约多项式： lm(x) = x8 + x4 + x3 + x +1 l用十六进制表示该多项式为011b。例如，57 83=c1， l因为 l (x6+ x4+ x2+ x+1)(x7+ x+1) l= x13+ x11+ x9+ x8+ x7+x7+ x5+ x3+ x2+ x+x6+ x4+ x2+ x+1 l= x13+ x11+ x9+x8+x6+x5+x4+x3+1 l而 x13+ x11+ x9+x8+x6+x5+x4+x3+1 modulo (x8+x4+x3+x+1) = x7+ x6+1 *现代密码学理论与实践0551/28 扩展欧几里德算法求逆 l元素01是乘法单位元。对任意次数小于8 的非零二元多项式b(x)，其 乘法逆元记为b-1(x)，可通过下述方法找到：使用扩展欧几里德算法计 算多项式a(x)和c(x)使得 lb(x)a(x)+m(x)c(x)=1 m(x) = x8 + x4 + x3 + x +1 l因此a(x) b(x) mod m(x)=1 意味着b-1(x)=a(x) mod m(x). l由此可见，由所有256 个可能的字节值组成的集合构成有限域GF(28) ，其每个元素(除了0)都可用扩展欧几里德算法求逆。 *现代密码学理论与实践0552/28 *现代密码学理论与实践0553/28 逆字节代换 *现代密码学理论与实践0554/28 逆S盒 *现代密码学理论与实践0555/28 系数在GF(28)中的多项式 l考虑含有 4 个项、且系数为有限域元素的多项 式，即 l注意本节中的多项式与有限域元素定义中使用 的多项式操作起来是不同的，该节中的系数本 身就是有限域元素，即字节(bytes)而不是比特 (bits) *现代密码学理论与实践0556/28 c(x) = a(x) b(x) *现代密码学理论与实践0557/28 *现代密码学理论与实践0558/28 *现代密码学理论与实践0559/28 *现代密码学理论与实践0560/28 *现代密码学理论与实践0561/28 安全性 l暴力攻擊 l單就金鑰長度來看，AES 裡面最少 128 位元的 金鑰絕對比 DES 的 56 位元金鑰要安全得 多。 l差異攻擊與線性攻擊 lAES 系統目前仍然沒有任何已知的差異攻擊或 者線性攻擊存在。 *现代密码学理论与实践0562/28 l国际数据加密算法IDEA l密码强度 l分组长度：64位 l密钥长度：128位 国际数据加密算法IDEA IDEA的基本操作是将两个16位的值映射成一个16位的值 l逐位异或， l整数模216(65536)加 l整数模216+1(65537)乘 IDEA的三种基本操作 5.4 IDEA思想 l该算法所依据的设计思想是“混合使用来自不 同代数群中的运算”。 l该算法所需要的“混乱”可通过连续使用三个“ 不相容”的群运算于两个16比特子块来获得， l并且该算法所选择使用的密码结构可提供必要 的“扩散”。 5.5 SMS4密码算法 lSMS4是用于WAPI（WLAN Authentication and Privacy Infrastructure）的分组密码算法，是国 内官方公布的第一个商用密码算法。 lSMS4算法是一个分组算法。SMS4算法的分组 长度为128比特，密钥长度为128比特。加密算 法与密钥扩展算法都采用32轮非线性迭代结构 。 5.6 分组密码的工作模式 l分组密码的工作模式就是以该分组密码算法为 基础构造的各种密码系统。 l模式适用于所有的分组密码，包括DES、AES 和IDEA 等。 5.6 分组密码的工作模式 l5.6.1 电子密码本模式（ECB） l5.6.2 密码分组链接模式（CBC） l5.6.3 密码反馈模式（CFB） l5.6.4 输出反馈模式（OFB） l5.6.5 记数模式（CTR） 分组链接模式Cipher Block Chaining (CBC) l加密输入是当前明文分组和前一密文分组的异或，形成一条链 ，使用相同的密钥， 这样每个明文分组的加密函数输入与明文 分组之间不再有固定的关系 5.6.2 CBC模式的优点 l如果明文分组中的一位出错，将影响该分组的 密文及其以后的所有密文分组。 l在一定程度上等防止数据篡改. l但是如果密文序列中丢失1位，那么所有后续 分组要移动1位，并且解密将全部错误。 CBC模式的缺点 l加密的消息的长度只能是分组长度的倍数，不是任意 长度的消息。 l以des为例，必须等到每8个字节都接受到之后 才能开始加密，否则就不能得到正确的结果。 l这在要求实时性比较高的时候就显得不合适了 。 CFB模式的优点和局限 l当数据以位或字节形式到达时使用都是适当的 l在加密解密两端都需要用分组加密器 l明文发生错误时，错误会传播 l如果其中有一个字节的密文在传输的时候发生错误（即使是其中 的一位），那么它出现在移位寄存器期间解密的8个字节的数据都 会得不到正确的解密结果，当然，这8个字节过去之后，依然可以 得到正确的解密结果。 l该模式也是比较浪费的，因为在每轮加解密中都丢弃了大部分结 果,j 通常为一字节（8 位）. 输出反馈模式（OFB） 5.6.4 输出反馈模式（OFB） l优点是：错误传播小，当前明文分组的错误不 会影响后继的密文分组；且密文中的1比特错 误只导致明文中的1个错误；消息长度是任意 的。 lOFB模式的缺点是：密文篡改难于检测 l适合传输语音图像 计数器模式Counter (CRT) CTR的优点 l预处理： 算法和加密盒的输出不依靠明文和密文的输入 l高效:可以做并行加密,允许同时处理多块明文 / 密文 l第 i 块密文的解密不依赖于第 i-1 块密文，提供很高的随机访问能力 l加密算法将仅仅是一系列异或运算，这将极大地提高吞吐量。 l仅要求实现加密算法，但不要求实现解密算法。对于 AES 等加/解密本质 上不同的算法来说，这种简化是巨大的 第六章 Hash函数 第1类生日问题 假设已经知道A的生日为某一天，问至少有 多少个人在一起时，至少有1/2的概率使有一 个人和A的生日相同？ 在此，我们假定一年有365天，且所有人的 生日均匀分布于365天中。 如果已知一个Hash函数H有n 个可能的 输出，其中H(x)是一个特定的输出。 随机取k个输入，则至少有一个输入y使 得H(y)H(x)的概率为0.5时，k有多大？ 第1类生日攻击 假设一年有365天，每个人的生日均匀分 布于365天 那么至少有多少个人在一起是，能保证至 少有1/2的概率存在2个人有相同的生日。 第2类生日问题 若一文件m的Hash值H(m)为n比特，试问 至少有多少的文件在一起，有两个文件的 Hash值以至少1/2的概率相同。 第2类生日攻击 MD5的安全性 lMD5算法抗密码分析的能力较弱，对MD5的生日攻击 所需代价是需要试验264个消息。 l2004年8月17日，在美国加州圣巴巴拉召开的美密会 （Crypto2004）上，中国的王小云、冯登国、来学嘉 、于红波4位学者宣布，只需1小时就可找出MD5的碰 撞。（利用差分分析） 图6.6 SHA-1 消息处理框图 SHA-1 与MD5的比较 安全性： SHA-1的报文摘要比MD5的长32比特 抗密码分析攻击的强度， SHA-1似乎高于MD5 效率： MD5效率比SHA-1高。 MD5已被破解；SHA-1目前还可以应用 总的说来， SHA-1的安全性是以牺牲效率为代价的， 类似于分组密码的加密 第七章 消息认证码 MAC实质上是一个双方共享的密钥k和消息m作 为输入的函数 l记为MAC = CK(M) lMAC-”带密钥的hash函数” MAC: 消息认证码是什么 一种是基于分组密码的 一种是基于带密钥的Hash函数的。 7.1 消息认证码的构造 基于分组密码的MAC CBC-MAC （1）接收者确信消息未被更改过。 （2）接收者确信消息来自所谓的发送者。 消息认证码实现认证 公钥密码体制的基本概 念 公钥密码所依赖的数学难题 l背包问题 l二次剩余问题 l模n的平方根问题 l多变量方程系统 l格规约:NTRU l大整数分解问题（The Integer Factorization Problem, RSA体制） l离散对数问题： l有限域的乘法群上的离散对数问题（The Discrete Logarithm Problem, ELGamal体制） l定义在有限域的椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem，类比的 ELGamal体制） RSA算法 概况： lMIT三位年青数学家R.L.Rivest，A.Shamir和 L.Adleman 在1978年发现了一种用数论构造 双钥体制的方法，称作MIT体制，后来被广泛 称之为RSA体制。 l它既可用于加密、又可用于数字签名。 lRSA算法的安全性基于数论中大整数分解的困 难性。 2、RSA算法 算法描述密钥产生KG( )： l独立地选取两大素数p和q(各100200位十进制数 字) l计算 n=pq，其欧拉函数值(n)=(p1)(q1) l随机选一整数e，1e(n)，gcd(n), e)=1 l在模(n)下，计算e的有逆元d=e -1 mod (n) l以n，e为公钥。私钥为d。(p, q不再需要，可以销 毁。) 算法描述加密E( )和解密D( )： l加密 将明文分组，各组对应的十进制数小于n c=me mod n l解密 m=cd mod n 3、RSA的安全性 lRSA的安全性是基于分解大整数的困难性假定 （尚未证明分解大整数是NP问题） l如果分解n=pq，则立即获得(n)=(p1)(q 1)，从而能够确定e的模(n)乘法逆d lRSA-129历时8个月被于1996年4月被成功 分解，RSA-130于1996年4月被成功分解 ln的长度应该介于1024bit到2048bit之间 l1、大素数的产生 1.试除法 2.费马法 3.Rabin-Miller算法 l未通过检测的整数一定是合数 l但，并非所有通过检测的整数都是素数 l实用最广泛，是一种概率算法 l2、求乘法逆元：扩展的欧几里得算法 RSA的实现 3、快速指数计算 利用反复平方乘算法 每次乘法运算后就取模 3、椭圆曲线密码体制的优点 l安全性高（椭圆曲线群上的离散对数更难计算） l攻击有限域上的离散对数可用指数积分法，运算复杂 度为亚指数复杂。 对ECC上离散对数攻击并不有效。 l攻击ECC上离散对数问题的方法只有大步小步法，复 杂度为指数。因此ECC上的密码体制比基于有限域上 离散对数问题的公钥体制更安全 数字签名 ElGamal数字签名 公钥数学基础 Euler定理-费马定理 lEuler定理:对任意互素的a和n, 有a(n) mod n=1 l费马定理 :ap-1 mod p = 1 密码学考试感想 l一 简答 l1 密码体制 l2 什么是强无碰撞的散列函数，解释强无碰撞与弱无碰