工学密码学复习.pptx

1.密码学概述密码学概述l主动攻击与被动攻击主动攻击与被动攻击：对一个保密系统采取截获密文进行分析的这类攻击方法称为被动攻被动攻击击(passiveattack)。非法入侵者主动干扰系统，采用删除、更改、增添、重放等方法向系统加入假消息，则这种攻击为主动攻击主动攻击(activeattack)。从攻击效果看，敌手可能达到以下结果：l（1）完全攻破。敌手找到了相应的密钥，从而可以恢复任意的密文。l（2）部分攻破。敌手没有找到相应的密钥，但对于给定的密文，敌手能够获得明文的特定信息。l（3）密文识别。如对于两个给定的不同明文及其中一个明文的密文，敌手能够识别出该密文对应于哪个明文，或者能够识别出给定明文的密文和随机字符串。第二章第二章 经典密码学经典密码学线性同余密码线性同余密码将移位密码和乘数密码进行组合就可以得到更多的选择方式，也叫仿射密码(affinecipher)。若选取k1，k2两个参数，其中(k1,26)1，即k1和26互素，令Ck1mk2mod26 k11时便是Kaiser变换。例如例如k17，k210，则明文pleasesendmoneys的对应数据为16125119519514413151452519通过变换c7m10mod26可得18161917131913194122311419313对应的密文为RPSQMSMSDLWKDSCM习题习题l1、对于线性替代密码，设已知明码字母、对于线性替代密码，设已知明码字母J(9)对应于密文字母对应于密文字母P(15)，即，即9k mod 26=15,试试计算密钥计算密钥k以破译此密码。以破译此密码。l答：k=9-1*15mod269-1mod26=3k=3*15mod26=19第四章序列密码序列密码的加密和解密就是用一个随机序列与明文序列叠加产生密文，用同一个随机序列与密文序列叠加来恢复明文。若设明文为m，密钥为k，加密后的密文为c，则加密变换为：cmk，解密变换：mck，其中m，k，c是0、1随机序列，表示模2加法运算。4.1 序列密码的基本概念序列密码的基本概念图4.1序列密码的加密和解密4.2 密钥流与密钥生成器密钥流与密钥生成器一般地，序列密码中对密钥流有如下要求：（1）极大的周期。因为随机序列是非周期的，而按任何算法产生的序列都是周期的，因此应要求密钥流具有尽可能大的周期。（2）良好的统计特性。随机序列有均匀的游程分布。游程指序列中相同符号的连续段，其前后均为异种符号。如0111000010中3个段分别为长为3的1游程、长为4的0游程、长为1的1游程。一般要求其在一周期内满足：同样长度的0游程和1游程的个数相等，或近似相等。（3）不能用级数较小的线性移位寄存器近似代替，即要有很高的线性复杂度。（4）用统计方法由密钥序列k0k1k2ki提取密钥生成器结构或种子密钥的足够信息在计算上是不可能的。目前密钥流生成器大都是基于移位寄存器的，这种基于移位寄存器的密钥流序列称为移位寄存器序列。4.3 线性反馈移位寄存器序列线性反馈移位寄存器序列移位寄存器是序列密码产生密钥序列的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1a2.an)组成，如图4.3所示。图4.3GF(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)cna1cn1a2c1an，其中常数ci0或1，是模2加法。线性反馈移位寄存器（LFSR）f(a1,a2,a5)a1a4图4.6一个5级线性反馈移位寄存器n级线性反馈移位寄存器最多有2n个不同的状态。若其初始状态非0，则其后继状态不会为0。因此n级线性反馈移位寄存器的状态周期2n-1。其输出序列的周期与状态周期相等，也2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。反馈函数反馈函数:b1+b3设n级线性移位寄存器的输出序列ai满足递推关系ak+ak，对任何k1成立。将这种递推关系用一个一元高次多项式表示，称这个多项式为线性移位寄存器的连接多项式。4.4 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示反馈函数反馈函数:b1+b3l反馈函数:b1+b2+b3+b4试题试题l设g(x)=x4+x2+1，g(x)为GF（2）上的多项式，以其为连接多项式组成线性移位寄存器。画出逻辑框图。设法遍历其所有状态，并写出其状态变迁及相应的输出序列。解答ll通常采用的方法是，由线性移位寄存器(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破破译译它它的的穷穷举举密密钥钥搜搜索索量量为为2112 51035量量级级，而而用用差差分分分分析析破译也要超过破译也要超过1052量级。此方案仍有足够的安全性。量级。此方案仍有足够的安全性。l三个密钥的三重DES已在因特网的许多应用（如PGP和S/MIME）中被采用习题习题2024/4/22周一现代密码学理论与实践0544复习TheAESCipher2024/4/22周一现代密码学理论与实践0545/28第第5章章 高级加密标准之要点高级加密标准之要点lAES是一种分组密码，用以取代DES的商业应用。其分组长度为128位，密钥长度为128位、192位或256位lAES没有使用Feistel结构。每轮由四个独立的运算组成：字节代换、置换、有限域上的算术运算，以及与密钥的异或运算2024/4/22周一现代密码学理论与实践0546/28AES密码密码l由比利时密码学家VincentRijmen和JoanDaemen设计l分组长度，密钥长度可以是128/192/256位之一2024/4/22周一现代密码学理论与实践0547/282024/4/22周一现代密码学理论与实践0548/282024/4/22周一现代密码学理论与实践0549/28GF(28)上的域元素上的域元素加法2024/4/22周一现代密码学理论与实践0550/28乘法l在多项式表示中，有限域GF(28)上的乘法(记为)定义为多项式的乘积模一个次数为8的不可约多项式：lm(x)=x8+x4+x3+x+1l用十六进制表示该多项式为011b。例如，5783=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+1l=x13+x11+x9+x8+x6+x5+x4+x3+1l而x13+x11+x9+x8+x6+x5+x4+x3+1modulo(x8+x4+x3+x+1)=x7+x6+12024/4/22周一现代密码学理论与实践0551/28扩展欧几里德算法求逆l元素01是乘法单位元。对任意次数小于8的非零二元多项式b(x)，其乘法逆元记为b-1(x)，可通过下述方法找到：使用扩展欧几里德算法计算多项式a(x)和c(x)使得lb(x)a(x)+m(x)c(x)=1m(x)=x8+x4+x3+x+1l因此a(x)b(x)modm(x)=1意味着b-1(x)=a(x)modm(x).l由此可见，由所有256个可能的字节值组成的集合构成有限域GF(28)，其每个元素(除了0)都可用扩展欧几里德算法求逆。2024/4/22周一现代密码学理论与实践0552/282024/4/22周一现代密码学理论与实践0553/28逆字节代换逆字节代换2024/4/22周一现代密码学理论与实践0554/28逆逆S盒盒2024/4/22周一现代密码学理论与实践0555/28系数在GF(28)中的多项式l考虑含有4个项、且系数为有限域元素的多项式，即l注意本节中的多项式与有限域元素定义中使用的多项式操作起来是不同的，该节中的系数本身就是有限域元素，即字节(bytes)而不是比特(bits)2024/4/22周一现代密码学理论与实践0556/28c(x)=a(x)b(x)2024/4/22周一现代密码学理论与实践0557/282024/4/22周一现代密码学理论与实践0558/282024/4/22周一现代密码学理论与实践0559/282024/4/22周一现代密码学理论与实践0560/282024/4/22周一现代密码学理论与实践0561/28安全性安全性l暴力攻擊l單就金鑰長度來看，AES 裡面最少 128 位元的金鑰絕對比 DES 的 56 位元金鑰要安全得 多。l差異攻擊與線性攻擊lAES 系統目前仍然沒有任何已知的差異攻擊或者線性攻擊存在。2024/4/22周一现代密码学理论与实践0562/28l国际数据加密算法IDEAl密码强度l分组长度：64位l密钥长度：128位国际数据加密算法国际数据加密算法IDEAIDEA的基本操作是将两个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.6SHA-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 消息认证码的构造消息认证码的构造基于分组密码的基于分组密码的MACCBC-MAC（1）接收者确信消息未被更改过。（2）接收者确信消息来自所谓的发送者。消息认证码实现认证公钥密码体制的基本概公钥密码体制的基本概念念公钥密码所依赖的数学难题公钥密码所依赖的数学难题l背包问题l二次剩余问题l模n的平方根问题l多变量方程系统l格规约:NTRUl大整数分解问题（The Integer Factorization Problem,RSA体制）l离散对数问题：l有限域的乘法群上的离散对数问题（TheDiscreteLogarithmProblem,ELGamal体制）l定义在有限域的椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem，类比的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，1 e(n)，gcd(n),e)=1l在模在模(n)下，计算下，计算e的有逆元的有逆元d=e-1 mod (n)l以以n，e为为公公钥钥。私私钥钥为为d。(p,q不不再再需需要要，可可以以销销毁。毁。)算法描述加密E()和解密D()：l加密将明文分组，各组对应的十进制数小于n c=me mod nl解密 m=cd mod n3、RSA的安全性的安全性lRSA的安全性是基于分解大整数的困难性假定（尚未证明分解大整数是NP问题）l如果分解n=pq，则立即获得(n)=(p1)(q1)，从而能够确定e的模(n)乘法逆dlRSA-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)modn=1l费马定理:ap-1modp=1密码学考试感想密码学考试感想l一简答l1密码体制l2什么是强无碰撞的散列函数，解释强无碰撞与弱无碰撞的含义l二RSA密码，给定N11*7，从e1=3和e2=17，选择一个合适的公钥，并计算出私钥l三实数域上的椭圆曲线，即由y2=x3-36x定义的曲线，推导曲线上点的加法公式，并已知P=(-3,9),Q=(-2,8)，计算P+Q和2P。（课后作业的改造）l四简述AES的特征，它与DES的本质区别是什么？l五证明由如下方式中构造的Hash函数是强无碰撞的：q=(p-1)/2，p和q都是素数，是本原根，=a(a是保密指数)，h(x1,x2)=x1x2（课件中有详细证明）。l六古典密码：用VigenereCipher解密一串密文，密钥由六个字母组成：HCPIRE。l做完考题，感触很深：ll1第五题要证明Hash函数强无碰撞，没有做完全，让我最郁闷的是，昨天晚上，我把这个证明在纸上写了一遍，感觉没有什么问题了。可是，今天一考试，又傻了，不会做了。看来我没有理解证明的原理，对证明过程没有宏观的把握，还没有完全明白为什么要这样证明，昨天晚上我能写下来，仅仅是强记的而已。ll2第六题没有做对，同样让我一样郁闷，我没有看清题目，我以为密钥就是HCPIRE，而不知道应该对这六个字母进行组合；我太笨了，做题的时候还纳闷呢，这明明是cipher单词的字母嘛，怎么要把它的顺序打乱来做密钥呢。原来题目考的就是要对这六个字母重新排列，恢复出cipher，看来我是傻呼呼地到家了。l3时间没有合理安排好，前面时间用得多，到后面就没有时间做了。之所以第五题与第六题没有做好，很大原因也是时间到后面不够了，如果第六题放在前面的话，我在很大概率上能做出来，可惜到了后来没有时间仔细看题目了；还有第五题也是，如果给我足够的时间，我应该能把卡住的问题解决。唉，以后考试得合理安排时间，不能在前面慢慢磨蹭啊。4考了多少分并不重要，重要的是通过考试能够发现自己学习的方式和习惯的不足之处，接下来还有信息安全数学基础，形式化方法，信息系统安全的考试，我得借鉴此次教训，把基础打扎实一些，不能再忽悠自己了，不要浮躁，要做到知其然知其所以然。