第2章 密码学基础

2020/2/23计算机系统安全原理与技术1第2章密码学基础2020/2/23计算机系统安全原理与技术2本章主要内容密码学基本概念对称密码体制公钥密码体制散列函数数字签名信息隐藏与数字水印2020/2/23计算机系统安全原理与技术32.1概述经典密码：古埃及人用以保密传递的消息；单表置换密码，凯撒密码，多表置换密码，Vigenere密码等等近代密码：DES数据加密标准，70年代Diffie,Hellman的开创性工作——公钥体制的提出密码应用：电子数据，军事目的，经济目的。应用形式：数据的保密性、真实性、完整性。主要内容：数据加密，密码分析，数字签名，信息鉴别，零泄密认证，秘密共享等等。信息攻击：主动攻击——对数据的恶意删除、篡改等被动攻击——从信道上截取、偷窃、拷贝信息。无意攻击——错误操作、机器故障等。2020/2/23计算机系统安全原理与技术42.2密码学基本概念现代密码系统的组成现代密码系统(通常简称为密码体制)一般由五个部分组成：明文空间M密文空间C密钥空间K加密算法E解密算法D则五元组（M，C，K，E，D）称为一个密码体制。2020/2/23计算机系统安全原理与技术5密码体制对称密钥体制非对称密钥体制2020/2/23计算机系统安全原理与技术6根据密码算法对明文信息的加密方式，对称密码体制常分为两类：分组密码(Blockcipher，也叫块密码)DES、IDEA、BLOWFISH序列密码(Streamcipher，也叫流密码)。A5、FISH、PIKE2020/2/23计算机系统安全原理与技术7密码分析学穷举攻击：又称作蛮力攻击，是指密码分析者用试遍所有密钥的方法来破译密码对可能的密钥或明文的穷举统计分析攻击：指密码分析者通过分析密文和明文的统计规律来破译密码。数学分析攻击：指密码分析者针对加密算法的数学依据，通过数学求解的方法来破译密码。2020/2/23计算机系统安全原理与技术81、唯密文攻击：仅根据密文进行的密码攻击；2、已知明文攻击：根据一些相应的明、密文对进行的密码攻击。3、选择明文攻击：可以选择一些明文，并获取相应的密文，这是密码分析者最理想的情形。例如，在公钥体制中。4、选择密文攻击：密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，密码分析者的任务是推出密钥。5、选择密钥攻击：这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间关系的有关知识。6、软磨硬泡攻击：密码分析者威胁、勒索，或者折磨某人，直到他给出密钥为止。根据密码分析者掌握明、密文的程度密码分析可分类为：2020/2/23计算机系统安全原理与技术9密码算法的安全性：理论上，除一文一密外，没有绝对安全的密码体制，通常，称一个密码体制是安全的是指计算上安全的，即：密码分析者为了破译密码，穷尽其时间、存储资源仍不可得，或破译所耗资材已超出因破译而获得的获益。2020/2/23计算机系统安全原理与技术102.3对称密码体制经典的密码体制中，加密密钥与解密密钥是相同的，或者可以简单相互推导，也就是说：知道了加密密钥，也就知道了解密密钥；知道了解密密钥，也就知道了加密密钥。所以，加、解密密钥必须同时保密。这种密码体制称为对称（也称单钥）密码体制。最典型的是DES数据加密标准，应该说数据加密标准DES是单钥体制的最成功的例子。2020/2/23计算机系统安全原理与技术111973.5.15：美国国家标准局（NSA）公开征求密码体制的联邦注册；1975.3.17：DES首次在《联邦记事》公开，它由IBM开发，它是LUCIFER的改进；1977.2.15：DES被采用作为非国家机关使用的数据加密标准，此后，大约每五年对DES进行依次审查，1992年是最后一次审查，美国政府已声明，1998年后对DES不再审查了；1977.2.15：《联邦信息处理》标准版46（FIPSPUB46）给出了DES的完整描述。2020/2/23计算机系统安全原理与技术122.3.1DES分组密码系统DES密码体制：它是应用56位密钥，加密64比特明文分组的分组秘钥密码体制DES加密算法：（一）初始置换：x0=L0R0=IP(x)；（二）16次迭代：xi-1=Li-1Ri-1，Li=Ri，Ri=Lif(Ri-1,ki)i=1,2,…,16；（三）逆置换：x16=L16R16，y=IP-1(x16)。密钥生成器：密钥ki是由56位系统密钥k生成的32位子密钥。函数f及S盒：f(Ri-1,ki)=P(S(E(Ri-1)ki))2020/2/23计算机系统安全原理与技术13其中E，P是两个置换，表示比特的“异或”，S是一组八个变换S1，S2，S3，…，S8，称为S盒，每个盒以6位输入，4位输出，S盒构成了DES安全的核心。DES算法流程图2020/2/23计算机系统安全原理与技术14函数f及S盒的示意图•DES解密：DES的解密过程与加密过程相同，只不过子密钥的使用相反，即，首先使用k16，再使用k15，…，最后使用k1。2020/2/23计算机系统安全原理与技术152.3.2关于DES的讨论S盒是唯一非线性组件：有人认为其中可能含有某种“陷门”，国家安全机关可以解密。DES的密钥量太小：密钥量为2561977年：Diffie.Hellman提出制造一个每秒测试106的VLSI芯片，则一天就可以搜索完整个密钥空间，当时造价2千万美圆。CRYPTO’93：R.Session，M.Wiener提出并行密钥搜索芯片，每秒测试5x107个密钥，5760片这种芯片，造价10万美圆，平均一天即可找到密钥。2020/2/23计算机系统安全原理与技术16Internet的超级计算能力：1997年1月28日，美国RSA数据安全公司在Internet上开展了一项“秘密密钥挑战”的竞赛，悬赏一万美圆，破解一段DES密文。计划公布后，得到了许多网络用户的强力相应。科罗拉州的程序员R.Verser设计了一个可以通过互联网分段运行的密钥搜索程序，组织了一个称为DESCHALL的搜索行动，成千上万的的志愿者加入到计划中。2020/2/23计算机系统安全原理与技术17第96天，即竞赛公布后的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司职员M.Sanders成功地找到了密钥，解密出明文：TheunknownMessageis：“Strongecryptographymakesthewordasaferplace”(高强度密码技术使世界更安全)。Internet仅仅利用闲散资源，毫无代价就破译了DES密码，这是对密码方法的挑战，是Internet超级计算能力的显示.2020/2/23计算机系统安全原理与技术18差分分析法：除去穷举搜索密钥外，还有其他形式的攻击方法，最著名的有Biham，Shamir的差分分析法。这是一个选择明文攻击方法。虽然对16轮DES没有攻破，但是，如果迭代的轮数降低，则它可成功地被攻破。例如，8轮DES在一个个人计算机上只需要2分钟即可被攻破。2020/2/23计算机系统安全原理与技术192.3.3DES扩展形式多重DESS盒可选择的DES具有独立子密钥的DESG-DES2020/2/23计算机系统安全原理与技术202.4公钥密码体制一个安全的对称密钥密码系统，可以达到下列功能：保护信息机密认证发送方之身份确保信息完整性对称密钥密码系统具有下列缺点：收发双方如何获得其加密密钥及解密密钥？密钥的数目太大无法达到不可否认服务2.4.1传统密码体制的缺陷与公钥密码体制的产生2020/2/23计算机系统安全原理与技术21现代密码学修正了密钥的对称性，1976年，Diffie，Hellmann提出了公开密钥密码体制（简称公钥体制），它的加密、解密密钥是不同的，也是不能（在有效的时间内）相互推导。所以，它可称为双钥密码体制。它的产生，是密码学革命性的发展，它一方面，为数据的保密性、完整性、真实性提供了有效方便的技术。另一方面，科学地解决了密码技术的瓶颈──密钥的分配问题。2020/2/23计算机系统安全原理与技术22第一个公钥体制是1977年由Rivest，Shamir，Adleman提出的，称为RSA公钥体制，其安全性是基于整数的因子分解的困难性。RSA公钥体制已得到了广泛的应用。其后，诸如基于背包问题的Merkle-Hellman背包公钥体制，基于有限域上离散对数问题的EIGamal公钥体制，基于椭圆曲线的密码体制等等公钥体制不断出现，使密码学得到了蓬勃的发展，2020/2/23计算机系统安全原理与技术232.4.2公钥密码体制介绍公钥密码体制加解密过程主要有以下几步：2020/2/23计算机系统安全原理与技术24安全的公开密钥密码可以达到下列功能：（1）简化密钥分配及管理问题公钥体制用于数据加密时：用户将自己的公开（加密）密钥登记在一个公开密钥库或实时公开，秘密密钥则被严格保密。信源为了向信宿发送信息，去公开密钥库查找对方的公开密钥，或临时向对方索取公钥，将要发送的信息用这个公钥加密后在公开信道上发送给对方，对方收到信息（密文）后，则用自己的秘密（解密）密钥解密密文，从而，读取信息。可见，这里省去了从秘密信道传递密钥的过程。这是公钥体制的一大优点。2020/2/23计算机系统安全原理与技术25（2）保护信息机密任何人均可将明文加密成密文，此后只有拥有解密密钥的人才能解密。2020/2/23计算机系统安全原理与技术26（3）实现不可否认功能公钥体制用于数字签名时：信源为了他人能够验证自己发送的消息确实来自本人，他将自己的秘密（解密）密钥公布，而将公开（加密）密钥严格保密。与别人通信时，则用自己的加密密钥对消息加密──称为签名，将原消息与签名后的消息一起发送.对方收到消息后，为了确定信源的真实性，用对方的解密密钥解密签名消息──称为（签名）验证，如果解密后的消息与原消息一致，则说明信源是真实的，可以接受，否则，拒绝接受。2020/2/23计算机系统安全原理与技术272.4.3基本数学概念群模逆元费尔马小定理Euler函数生成元2020/2/23计算机系统安全原理与技术282.4.4RSA算法1976年：Diffie，Hellman在“NewDirectioninCryptography”(密码学新方向)一文中首次提出公开密钥密码体制的思想。1977年：Rivest,Shamir,Adleman第一次实现了公开密钥密码体制，现称为RSA公钥体制。2020/2/23计算机系统安全原理与技术29基本算法：①生成两个大素数p和q（保密）；②计算这两个素数的乘积n=pq（公开）；③计算小于n并且与n互素的整数的个数，即欧拉函数(n)=(p–1)(q–1)（保密）；④选取一个随机整数e满足1e(n)，并且e和(n)互素，即gcd(e,(n))=1（公开）；⑤计算d，满足de=1mod(n)（保密）；2020/2/23计算机系统安全原理与技术30E(m)Kb1AKa1BD(E(m))Kb2mmRSA的加解密过程公开信道2020/2/23计算机系统安全原理与技术31一个利用RSA算法的加密实例设p=101，q=113，n=pq=11413，(n)=(p-1)(q-1)=100×112=11200，a=6597，b=3533，x=9726。加密：y=xb=97263533=5761mod11413；解密：x=ya=57616597=9726mod11413。2020/2/23计算机系统安全原理与技术32算法分析：该体制的数学依据是Euler定理及大数分解的困难性，体制中使用的是Zn中的计算。设是两个不同奇素数p,q的乘积，对于这样的正整数，其Euler函数值是容易计算的，它是(n)=(p-1)(q-1)。对于给定的明文xn，选定一个正整数b，称为加密密钥。2020/2/23计算机系统安全原理与技术33作Zn中的指数运算，将明文以指数形式xb表示出来，即以指数形式将明文隐藏起来。即使知道一个