现代密码学复习.

现代密码学复习主讲人：闫玺玺[e-mail]河南理工大学计算机科学与技术学院12/22/2019112/22/20192课件下载的信箱用户名：[e-mail]密码：hpu2013第一章密码学概论密码学是对与信息安全各方面（比如机密性、完整性、认证性和不可否认性）有关的数学技术的研究。密码学是保障信息安全的核心技术，但密码学不是提供信息安全的唯一方式。信息安全是密码学研究与发展的目的。信息安全的理论基础是密码学，信息安全的问题根本解决往往依靠密码学理论。12/22/2019312/22/20194密码编码学+密码分析学=密码学密码编码学(Cryptography)：主要研究密码体制及其安全应用方式，并研究以实现隐藏或鉴别为目的的信息编码手段。密码分析学(Cryptanalysis)：主要研究破译密态信息或伪造明态信息的方法。被动攻击即窃听，是对系统的保密性进行攻击，如搭线窃听、对文件或程序的非法拷贝等，以获取他人的信息。被动攻击分为两类一类是获取消息的内容第二类是进行业务流分析（交换信息的频率和长度，主机位置和标识）被动攻击因不对消息做任何修改，因而是难以检测的，所以抗击这种攻击的重点在于预防而非检测。被动攻击12/22/20195主动攻击又可分为以下四个子类：①中断：是对系统的可用性进行攻击，如破坏计算机硬件、网络或文件管理系统。②篡改：是对系统的真实性、完整性和有序性进行攻击，如修改数据文件中的数据、替换某一程序使其执行不同的功能、修改网络中传送的消息内容等。③伪造：是对系统的身份真实性进行攻击。如在网络中插入伪造的消息或在文件中插入伪造的记录。④重放：将一个数据单元截获后进行重传，产生一个未授权的消息。主动攻击12/22/20196密码学的发展历程密码学发展大致分为三个阶段：古典密码时期近代密码时期现代密码时期12/22/20197现代密码学的重要事件1949年Shannon发表题为《保密系统的通信理论》，为密码系统建立了理论基础，从此密码学成了一门科学。（第一次飞跃）1976年后，美国数据加密标准（DES）的公布使密码学的研究公开，密码学得到了迅速发展。1976年，Diffe和Hellman发表了《密码学的新方向》，提出了一种新的密码设计思想，从而开创了公钥密码学的新纪元。（第二次飞跃）1978年由Rivest、Shamire和Adleman首先提出第一个实用的公钥密码体制RSA，使公钥密码的研究进入了快速发展阶段。12/22/20198对称密码(单钥密码,私钥密码)加密密钥与解密密钥相同，如：分组密码，流密码非对称密码体制(双钥密码,公钥密码)加密密钥与解密密钥不同，如：公钥密码密码体制分类12/22/2019910对于加密体制，可有以下不同级别攻击形式：（1）唯密文攻击。此时攻击者只能从截获的密文进行分析，试图获得相应的明文或密钥；（2）已知明文攻击。此时攻击者不但能够截获密文，而且能够得到一些已知的明文和密文对；（3）选择明文攻击（CPA－ChosenPlaintextAttack）。此时攻击者可以选择他认为有用的明文，并可以获得相应的密文。（4）选择密文攻击（CCA-ChosenCiphertextAttack）此时攻击者可以选择密文，并可以得到相应的明文。（5）选择文本攻击能够选择明文并得到对应的密文，也能选择密文得到对应的明文。密码体制的攻击12/22/2019第二章主要内容置换密码（列置换密码和周期置换密码）代换密码（单表代换密码、多表代换密码)典型传统密码的分析（统计分析法和明文-密文对分析法)1112/22/2019古典密码在1949年ClaudeShannon发表“保密系统的通信理论”之前，密码学算法主要通过字符间的置换和代换实现，一般认为这些密码体制属于传统密码范畴。传统密码体制是指那些比较简单的、大多数采用手工或机械操作对明文进行加密、对密文进行解密的密码体制(对称)),其安全性绝大多数与加解密算法保密性密切相关。传统密码体制的技术、思想以及破译方法虽然很简单，但是反映了密码设计和破译的思想，是学习密码学的基本入口，对于理解、设计和分析现代密码仍然具有借鉴的价值。1212/22/2019代换密码的分类按照一个明文字母是否总是被一个固定的字符代换进行划分：单表代换密码(移位、仿射、替换)对明文消息中出现的同一个字母，在加密时都使用同一固定的字母来代换，不管它出现在什么地方。多表代换密码(维吉利亚、Playfair、转轮)明文消息中出现的同一个字母，在加密时不是完全被同一固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。1312/22/2019字母代换密码（Hill密码）希尔密码(HillCipher)密钥产生首先要决定所采用的密钥矩阵det(K)必须和26互质，即gcd(det(K),26)=1;否则不存在K的反矩阵，无法正常解密。1412/22/2019加密过程设要传输的明文字母是hill，被数字化后的4个数字是：7，8，11，11C=(98824)=(JIIY)希尔密码(HillCipher)加密过程1512/22/2019解密过程希尔密码(HillCipher)解密过程首先计算密钥矩阵的逆矩阵1612/22/2019解密过程M＝C×K-1＝=(781111)=(HILL)希尔密码(HillCipher)解密过程1712/22/2019希尔密码举例明文是“cyber”，数字化后为2,24,1,4,17；密钥：加密：1051200100223142100355172241417mod268911005391900011895170003715121TTWRcTRV1051200314210089110000011800037k1812/22/2019明文Friday是用Hill密码加密的，m=2,得到密文POCFKU，则有12/22/2019195,1715,16kE8,32,5kE0,2410,20kE我们可以从两个明文对中，得到矩阵方程15165172583k希尔密码分析举例1517317183851211121mod26?12/22/201920sjqr1-12121026301-59415285-2-9116314801121mod263希尔密码分析举例12/22/2019211517151691151671983252152583k我们可以验证：71902410208315173173179113838585215121传统密码的一些启发代换或置换交叉使用；加解密码算法；密钥空间；密文的数量；多次使用一种代换或置换不增加安全性。算法保密增加安全性，但实际应用往往难于保证。应能抵御穷举攻击。常更新密钥可减少密文的数量。明文密文对；做好已用信息的保密。2212/22/2019第七章主要内容序列密码的介绍线性反馈移位寄存器12/22/201923在序列密码中，将明文消息按一定长度（长度较小）分组，然后对各组用相关但不同的密钥进行加密，产生相应的密文，相同的明文分组会因在明文序列中的位置不同而对应于不同的密文分组。解密用相同的密钥序列对密文序列进行分组解密以恢复出明文序列。pi∈GF(2),i≥0ki∈GF(2),i≥0yi∈GF(2),i≥0i≥0i≥0设明文为p=p0p1p2…设密钥为k=k0k1k2…设密文为c=c0c1c2…则加密变换为ci＝Eki(pi)则解密变换为pi＝Dki(ci)12/22/201924序列密码的描述12/22/201925LFSR1LFSR2F密钥序列KiLFSRn...驱动部分非线性组合部分LFSRF密钥序列Ki...一般由m-序列生成器构成，提供若干周期大、分布特性好的序列。把产生的多条驱动序列综合在一起的一些非线性编码手段，目的是有效地破坏和掩盖多条驱动序列中存在的规律或关系，提高复杂度。密钥流生成器工作原理：移位寄存器中所有位的值右移1位，最右边的一个寄存器移出的值是输出位，最左边一个寄存器的值由反馈函数的输出值填充，此过程称为进动1拍。反馈函数f是n个变元(b1,b2,…,bn)的布尔函数。移位寄存器根据需要不断地进动m拍，便有m位的输出，形成输出序列o1,o2,…,om。12/22/201926反馈移位寄存器反馈移位寄存器(feedbackshiftregister,FSR)是由n位的移位寄存器和反馈函数(feedbackfunction)组成，如下图所示，n位的寄存器中的初始值称为移位寄存器的初态。反馈函数f(a1,a2,…,an)anan-1…a2a1输出序列12/22/201927线性反馈移位寄存器如果移位寄存器的反馈函数f(a1,a2,…,an)是a1，a2，…，an的线性函数，则称之为线性反馈移位寄存器LFSR（linearfeedbackshiftregister）。此时f可写为f(a1,a2,…,an)=cna1cn-1a2…c1an其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如图所示。anan-1…a2a1输出序列…c1c2cn-1cn例1：一个3-级的反馈移位寄存器，反馈函数f(x)=b1⊕b3，初态为100，输出序列生成过程如下：上面输出序列周期长度为7。12/22/201928线性反馈移位寄存器（举例）b3b2b1f(b1,b2,b3)=b1⊕b3状态输出位10001100111101111011010000111000m序列的简介线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。n级线性反馈移位寄存器最多有2n个不同的状态。若其初始状态为0，则其状态恒为0。若其初始状态非0，则其后继状态不会为0。因此，n级线性反馈移位寄存器的状态周期小于等于2n-1，其输出序列的周期与状态周期相等，也小于等于2n-1。12/22/201929定义：n级线性反馈移位寄存器产生的序列{ai}的周期达到最大值2n-1时，称{ai}为n级m序列。第八章主要内容分组密码的简介DES密码算法AES密码算法12/22/201930也称块密码，它是将明文消息经编码表示后的二进制序列p0,p1,…,pi,…划分成若干固定长度(譬如m)的组(或块)p=(p0,p1,…,pm-1)，各组分别在密钥k=(k0,k1,…,kt-1)的控制下转换成长度为n的密文分组c=(c0,c1,…,cn-1)。其本质是一个从明文空间（m长的比特串的集合）P到密文空间(n长的比特串的集合)C的一一映射。(一般而言，m=n)12/22/201931解密算法加密算法密钥k=(k0,k1,…,kt-1)密钥k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)分组密码的含义8.2分组密码的设计原则扩散混乱12/22/2019328.5.1DES概述分组加密算法：明文和密文为64位分组长度。对称算法：加密和解密除密钥编排不同外，使用同一算法。密钥长度：56位，但存在弱密钥，容易避开。采用混乱和扩散的组合，每个组合先替代后置换，共16轮。只使用了标准的算术和逻辑运算，易于实现。现代密码学诞生的标志之一，揭开了商用密码研究的序幕。12/22/20193312/22/201934输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特DES算法框图DES一轮的实现流程图12/22/201935Li-1