第2章-密码学基础

1、密码学基础主讲人：王弈E-mail: n密码学基本概念 n对称密码体制 n公钥密码体制 n散列函数 n数字签名n信息隐藏与数字水印n无线网络中的密码应用 密码学Crypology密码编码学Crypography密码分析学Cryptoanalysis对称密码体制Sysmetic-key公钥密码体制Public-key安全协议Protocols流密码Steam cipher分组密码Block ciphern现代密码系统(通常简称为密码体制)一般由五个部分组成：明文空间M 密文空间C 密钥空间K 加密算法E 解密算法D n则五元组（M，C，K，E，D）称为一个密码体制。n对称密钥体制：n非对称密钥体

2、制n根据密码算法对明文信息的加密方式，对称密码体制常分为两类：分组密码(Block cipher，也叫块密码)DES、IDEA 、 BLOWFISH 序列密码(Stream cipher，也叫流密码)。A5 、FISH 、PIKE n当明文中的字符变化时，截取者不能预知密文会有何变化。我们把这种特性称为混乱性(Confusion)。n混乱性好的算法，其明文、密钥对和密文之间有着复杂的函数关系。这样，截取者就要花很长时间才能确定明文、密钥和密文之间的关系，从而要花很长的时间才能破译密码。n密码还应该把明文的信息扩展到整个密文中去，这样，明文的变化就可以影响到密文的很多部分，该原则称为扩散性(Di

3、fusion)。n这是一种将明文中单一字母包含的信息散布到整个输出中去的特性。好的扩散性意味着截取者需要获得很多密文，才能去推测算法。又称作蛮力攻击，是指密码分析者用试遍所有密钥的方法来破译密码对可能的密钥或明文的穷举。指密码分析者通过分析密文和明文的统计规律来破译密码。指密码分析者针对加密算法的数学依据，通过数学求解的方法来破译密码。 根据密码分析者掌握明、密文的程度密码分析可分类为：仅根据密文进行的密码攻击。根据一些相应的明、密文对进行的密码攻击。可以选择一些明文，并获取相应的密文，这是密码分析者最理想的情形。例如，在公钥体制中。密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文

4、，密码分析者的任务是推出密钥。这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间关系的有关知识。 ：密码分析者威胁、勒索，或者折磨某人，直到他给出密钥为止。n理论上，除一文一密外，没有绝对安全的密码体制，通常，称一个密码体制是安全的是指计算上安全的，即：密码分析者为了破译密码，穷尽其时间、存储资源仍不可得，或破译所耗资材已超出因破译而获得的获益。经典的密码体制中，加密密钥与解密密钥是相同的，或者可以简单相互推导，也就是说：知道了加密密钥，也就知道了解密密钥；知道了解密密钥，也就知道了加密密钥。所以，加、解密密钥必须同时保密。这种密码体制称为最典型的是DES数据加密标准，

5、应该说数据加密标准DES是单钥体制的最成功的例子。n1973.5.15： 美国国家标准局（NSA）公开征求密码体制的联邦注册；n1975.3.17：DES首次在联邦记事公开，它由IBM开发，它是LUCIFER的改进；n1977.2.15：DES被采用作为非国家机关使用的数据加密标准，此后，大约每五年对DES进行依次审查，1992年是最后一次审查，美国政府已声明，1998年后对DES不再审查了；n1977.2.15：联邦信息处理标准版46（FIPS PUB46）给出了DES的完整描述。nDES密码体制：它是应用56位密钥，加密64比特明文分组的分组秘钥密码体制nDES加密算法：（一）初始置换：x

6、0=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)。n密钥生成器：密钥ki是由56位系统密钥k生成的32位子密钥。n函数f及S盒：f(Ri-1,ki)=P(S(E(Ri-1)ki)其中E，P是两个置换， 表示比特的“异或”，S是一组八个变换S1，S2，S3， ，S8 ，称为S盒，每个盒以6位输入，4位输出，S盒构成了DES 安全的核心。nDES算法流程图nS盒是唯一非线性组件：有人认为其中可能含有某种“陷门”，国家安全机关可以解密。nDES的密钥量太

7、小：密钥量为256n1977年：Diffie.Hellman提出制造一个每秒测试106的VLSI芯片，则一天就可以搜索完整个密钥空间，当时造价2千万美圆。nCRYPTO93：R.Session，M.Wiener提出并行密钥搜索芯片，每秒测试5x107个密钥，5760片这种芯片，造价10万美元，平均一天即可找到密钥。nInternet的超级计算能力：1997年1月28日，美国RSA数据安全公司在Internet上开展了一项“秘密密钥挑战”的竞赛，悬赏一万美圆，破解一段DES密文。计划公布后，得到了许多网络用户的强力相应。科罗拉州的程序员R.Verser设计了一个可以通过互联网分段运行的密钥搜索程

8、序，组织了一个称为DESCHALL的搜索行动，成千上万的的志愿者加入到计划中。n第96天，即竞赛公布后的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司职员M.Sanders成功地找到了密钥，解密出明文：The unknown Message is：“Stronge cryptography makes the word a safer place”(高强度密码技术使世界更安全)。 Internet仅仅利用闲散资源，毫无代价就破译了DES密码，这是对密码方法的挑战，是Internet超级计算能力的显示.n差分分析法：除去穷举搜索密钥外，还有其他形式的攻击方法，最著名的

9、有Biham，Shamir的差分分析法。这是一个选择明文攻击方法。虽然对16轮DES没有攻破，但是，如果迭代的轮数降低，则它可成功地被攻破。例如，8轮DES在一个个人计算机上只需要2分钟即可被攻破。n在攻击面前，虽然多重DES表现良好。不过，考虑到计算机能力的持续增长，人们需要一种新的、更加强有力的加密算法。1995年，美国国家标准技术研究所NIST开始寻找这种算法。最终，美国政府采纳了由密码学家Rijmen和Daemen发明的Rijindael算法，使其成为了高级加密标准AES(Advanced Encryption Standard)。nRijindael算法之所以最后当选，是因为它集安全

10、性、效率、可实现性及灵活性于一体。nAES算法是具有分组长度和密钥长度均可变的多轮迭代型加密算法。分组长度一般为128比特位，密钥长度可以是128/192/256位。实际上，AES算法的密钥长度可以扩展为64的任意整数倍，尽管AES标准中只有128，192和256被认可。nAES的128位块可以很方便地考虑成一个44矩阵，这个矩阵称为“状态”(state)。例如，假设输入为16字节b0,b1,b15，这些字节在状态中的位置及其用矩阵的表示如表2-8所示。注意，这些状态用输入数据逐列填充。保护信息机密 认证发送方之身份 确保信息完整性 收发双方如何获得其加密密钥及解密密钥？ 密钥的数目太大 无法

11、达到不可否认服务 n现代密码学修正了密钥的对称性，1976年，Diffie，Hellmann提出了公开密钥密码体制提出了公开密钥密码体制（简称公钥体制）（简称公钥体制），它的加密、解密密钥是不同的，也是不能（在有效的时间内）相互推导。所以，它可称为双钥密码体制双钥密码体制。它的产生，是密码学革命性的发展，它一方面，为数据的保密性、完整性、真实性提供了有效方便的技术。另一方面，科学地解决了密码技术的瓶颈密钥的分配问题。 nRSA公钥体制已得到了广泛的应用。其后，诸如基于背包问题的Merkle-Hellman背包公钥体制，基于有限域上离散对数问题的EIGamal公钥体制，基于椭圆曲线的密码体制等等

12、公钥体制不断出现，使密码学得到了蓬勃的发展。 n 公钥体制用于数据加密时：用户将自己的公开（加密）密钥登记在一个公开密钥库或实时公开，秘密密钥则被严格保密。信源为了向信宿发送信息，去公开密钥库查找对方的公开密钥，或临时向对方索取公钥，将要发送的信息用这个公钥加密后在公开信道上发送给对方，对方收到信息（密文）后，则用自己的秘密（解密）密钥解密密文，从而，读取信息。可见，这里省去了从秘密信道传递密钥的过程。这是公钥体制的一大优点。 n任何人均可将明文加密成密文，此后只有拥有解密密钥的人才能解密。 n公钥体制用于数字签名时：n信源为了他人能够验证自己发送的消息确实来自本人，他将自己的秘密（解密）密钥

13、公布，而将公开（加密）密钥严格保密。与别人通信时，则用自己的加密密钥对消息加密称为签名，将原消息与签名后的消息一起发送.n对方收到消息后，为了确定信源的真实性，用对方的解密密钥解密签名消息称为（签名）验证，如果解密后的消息与原消息一致，则说明信源是真实的，可以接受，否则，拒绝接受。 Diffie，Hellman在“New Direction in Cryptography”(密码学新方向)一文中首次提出公开密钥密码体制的思想。Rivest,Shamir,Adleman第一次实现了公开密钥密码体制，现称为RSA公钥体制。n散列函数没有密钥，散列函数就是把可变输入长度串(叫做预映射，Pre-ima

14、ge)转换成固定长度输出串(叫做散列值)的一种函数。n散列函数又可称为压缩函数、杂凑函数、消息摘要、指纹、密码校验和、信息完整性检验(DIC)、操作认证码(Message Authentication Code，MAC)。（1）它能处理任意大小的信息，并将其信息摘要生成固定大小的数据块(例如128位，即16字节)，对同一个源数据反复执行Hash函数将总是得到同样的结果。（2）它是不可预见的。产生的数据块的大小与原始信息的大小没有任何联系，同时源数据和产生的数据块的数据看起来没有明显关系，但源信息的一个微小变化都会对数据块产生很大的影响。（3）它是完全不可逆的，即散列函数是单向的，从预映射的值很

15、容易计算其散列值，没有办法通过生成的散列值恢复源数据。（4）它是抗碰撞的，即寻找两个输入得到相同的输出值在计算上是不可行的。n假设单向散列函数H(M)作用于任意长度的消息M，它返回一个固定长度的散列值h，其中h的长度为定数m，该函数必须满足如下特性：给定M，很容易计算h；给定h，计算M很难；给定M，要找到另一消息M并满足H(M)=H(M)很难。（1）MD2算法（2）MD4和MD5算法（3）SHA算法（4）RIPEMD算法nSHA (Secure Hash Algorithm)由美国国家标准和技术局NIST设计，1993年被作为联邦信息处理标准(FIPS PUB 180)公布，1995年又公布了修订版FIPS PUB 180-1，通常称为SHA-1。n就当前的情况来看，SHA-1由于其安全强度及运算效率方面的优势已经成为使用最为广泛的散列函数。n该算法输入消息的最大长度为264-1位，产生的输出是一个160位的消息摘要。输入按512 位的分组进行处理。n数字签名最早被建议用来对禁止核试验条律的验证。禁止核试验条律的缔约国为了检测对方的核试验，需要把地震测