第三章 密码学基础与应用.ppt

1、第三章 密码学基础与应用,3.1 密码学概述 3.2 古典密码学 3.3 对称密码学 3.4 非对称密码学 3.5 Hash算法 3.6 数字签名 3.7 密码与网络安全协议,3.1 密码学概述,密码学包括密码编码学和密码分析学。 密码算法：用于加密和解密的数学函数。 明文：原本的消息。 密文：加密后的消息。 密码系统：由算法以及所有可能的明文、密文和密钥组成。 C=E(M)表示加密，M=D(C)表示解密，M=D(E(M),密码算法的分类（一）,按照保密的内容分: 受限制的（restricted)算法 对数据的保密性基于对算法的保密。 基于密钥（key-based)的算法 算法的保密性基于对密

2、钥的保密。,密码算法的分类（二）,按照对明文的处理方法： 分组密码（block cipher) 将明文分成固定长度的组，用同一密钥和 算法对每一块加密，输出也是固定长度的密 文。 流密码（stream cipher) 又称序列密码。序列密码每次加密一位或 一字节的明文。序列密码是手工和机械密码 时代的主流。,序列密码,分组密码,密码算法的分类(三),在基于密钥的算法中，按照密钥的特点分类： 对称密码算法（symmetric cipher) 又称传统密码算法（conventional cipher)， 就是加密密钥和解密密钥相同，或实质上等 同，即从一个易于推出另一个。又称秘密密 钥算法或单密钥

3、算法。 非对称密钥算法（asymmetric cipher) 加密密钥和解密密钥不相同，从一个很难 推出另一个。又称公开密钥算法（public-key cipher) 。,3.2 古典密码学,密码技术是信息安全的核心技术。 密码技术要求很高的数学基础：群和域的理论、计算复杂性以及实时分析，更不用说概率与统计。 我们希望建立这样一种密码算法，它对于合法的发送者和接受者来说易于操作，而对于恶意的截取者却十分困难。 可靠的密码学建立在数学和形式化的计算机科学产生的结论之上。,密码学的产生与发展,滚筒密码 看下面一段话： 经大们的意日那方过家参名被的些式短启观字埋凉投进暂程了和 在风奔行的去一生教吹他

4、着欢一个前堂来的沟迎家大从里，灵通仪 中教事，庭魂。式国堂的是院就后餐。职因里在，馆围业为的风一 吃绕。据古中本饭着副说树，正。一市这沙和经途个长样沙一的中 天说他作群市。井们响不长副的那死，信公市石底后让神干长板下 的人的去先路埋位惬中了生上着置意国，又，死离，人爱兴许人上 也用开致多。帝让一玩勃石人最人种笑勃板们近觉超的地上之。得 越市带刻所一上语长领着以阵帝言和我人愿夏和的,经大们的意日那方 过家参名被的些式 短启观字埋凉投进 暂程了和在风奔行 的去一生教吹他着 欢一个前堂来的沟 迎家大从里，灵通 仪中教事，庭魂。 式国堂的是院就 后餐。职因里在 ，馆围业为的风 一吃绕。据古中 本饭着副

5、说树， 正。一市这沙和 经途个长样沙一 的中天说他作群 市。井，们响不,长副的那死，信 公市石底后让神 干长板下的人的 去先路埋位惬中 了生上着置意国 ，又，死离，人 爱兴许人上也用 开致多。帝让一 玩勃石人最人种 笑勃板们近觉超 的地上之。得越 市带刻所一上语 长领着以阵帝言 和我人愿夏和的,滚筒密码,经,过,短,暂,的,欢,大,家,启,程,去,关键参数：滚筒的宽度（密钥）,恺撒密码（Caesar）,原理：把一个字母替换为它后面固定位置的 另一个字母（单表代换密码）。 A B C D E F G X Y Z D E F G H I J A B C 明文:Caesar cipher is a

6、shift substitution 密文:FDHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQ,弗纳姆密码（Vernam Cipher）,1918年Gilbert Vernam 为AT&T设计的一种一次一密乱码本密码（多表代换密码）。 原理：使用一个任意长的不重复数字序列，把它和明文组合在一起。 明文： V E R N A M C I P H E R 等价数字：21 4 17 13 0 12 2 8 15 7 4 17 +随机数： 76 48 16 82 44 3 58 11 60 5 48 88 和mod26： 19 0 7 17 18 15 8 19 23 12 0

7、 1 密文： t a h r s p i t x m a b,维吉尼亚密码,m个移位代换表由m个字母组成的密钥字确定 明文：w e a r d i s c o v e r e d s a v e 密钥：d e c e p t i v e d e c e p t i v e 对应数字：3 4 2 15 19 8 21 密文：Z I C V T WQNGRZGVTWAVZH,换位密码（置换密码）（一）,换位就是将明文中的字母的位置重排。 最简单的换位就是逆序法： 明文：computer system 密文：metsys retupmoc,换位密码（置换密码）（二）,列置换（纵行换位）：把明文中的字

8、符按列重新排列。例如 明文：THIS IS A MESSAGE. T H I S I S A M E S S A G E X 密文：TSSHAAIMGSEEISX 问题：1.排成的矩阵的宽度（有多少列）。 2.排成矩阵后，各列按什么顺序输出。,换位密码（置换密码）（三）,引入密钥k，如k=COMPUTER，明文为：WHAT CAN YOU LEARN FROM THIS BOOK 密文为：WORO NNSX ALMK HUOO TETX YFBX ARIX CAHX,现代密码学的原理,加密体系的安全性并不依赖于加密的方法本身，而是依赖于所使用的密钥。 当时的密码体系缺乏数学背景，因而也缺少测量

9、或评价这些体系抗攻击的能力。 1948年，Shannon发表的论文通信的数学原理将数学背景加入了密码学。,对称加密算法,分为两种： 分组密码 每次对一块数据加密，多数网络加密应用，如DES，IDEA，RC6，Rijndael。 流密码（序列密码） 每次对一位或一字节加密，语音和视频流 的加密传输，如Vigenre，Vernam。 速度快，安全强度高，主要用做数据加密 算法。,非对称密钥算法（公开密钥算法）,用一个密钥进行加密，而用另一个进行解密。 加密密钥可以公开，又称公开密钥（public key），简称公钥。解密密钥必须保密，又称私人密钥（private key），简称私钥。 大部分为分组

10、密码。如RSA，ECC，ElGamal 数据加密、身份认证、密钥分发、数字签名。 加密解密速度慢。,密码分析,密码分析学是研究密钥未知的情况下恢复明文的科学。 编码的特征： 转明文为密文的方法：代替和换位 所用的密钥数：对称密码、非对称密码 处理明文的方法：分块和单字节,密码分析可以发现密码体制的弱点。 常见的攻击（密码分析方法）,密码分析方法,确定性 利用若干已知的数学关系式表示出所求的未知量。 统计性 利用明文的已知统计规律进行破译。,代替密码和换位密码,计算机出现前，以字符代替或换位 计算机出现后，以比特代替或换位 代替密码（substitution cipher)：就是明文中的每一个字

11、符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。如恺撒密码。 换位密码（transposition cipher) ，又称置换密码(permutation cipher)：明文的字母保持相同，但顺序被打乱了。,代替密码,简单代替密码（单字母密码）：明文的一个字符用相应的一个密文字符代替。如恺撒密码（密钥为3）。 多名码代替密码：明文的一个字符可以映射成密文的几个字符之一。 字母代替密码：组成加密字符块。 多表代替密码：由多个简单的代替密码构成。如滚动密钥密码。,代替密码的破译,猜测密钥的长度 利用字母频度表进行破译 单个字母对单个字母，不管怎样变换，字母的出现概率在一个具

12、体的语言里面是十分稳定的。 稳定的概率是破译这种经典密码体制的关键。,各个明文字母的概率和密文字母频率的对照,换位密码的破译,判断密码类型：利用密文中字母出现的频率判断是否为换位密码。 根据消息的上下文猜测密钥的长度，即列数。 确定各列的顺序。,3.3 对称密码学,DES数据加密标准 1973年5月，美国国家标准局发出通告，公开征求 对计算机数据在传输和存储期间的进行数据加密的 算法。要求： 必须提供高度的安全性； 具有相当高的复杂性，使得破译的开销超过获得的利益，但同时又便于理解和掌握； 安全性应当不依赖于算法的保密，加密的安全性仅以加密密钥的保密为基础；,必须适合不同的用户和不同的应用场合

13、； 实现算法的电子器件必须很经济，运行有效； 必须能够出口。 1975年，IBM提出的算法被采纳，并向全国公 布，征求意见。1977年1月15日，美国国家标 准局正式采用这个算法作为数据加密标准（同 年7月15日生效）。1998年12月以后新的美国 联邦加密标准被称为高级加密标准AES。,DES的算法思想,将二进制序列的输入明文，以64位为数据分组，然后对这些明文进行替换和换位，最后形成密文。,DES算法的基本特点,对称算法：既可用于加密，也可用于解密。 64位的密钥，使用长度为56位（64位密钥中，有8位用于奇偶校验）。 加密算法是换位与置换的结合。 每个DES都在明文上实施16重相同的组合

14、技术，这种重复性可以被理想地应用到一个专用芯片中。,DES加密过程,DES加密过程细化,DES加密过程主要涉及如下环节（模块）： 初始换位和逆初始换位 将64位明文分为32位的左右两段：L0和R0 生成每一轮的子密钥 进行16轮相同的迭代运算：混淆+异或+交换 将最后左右两段合并,DES的安全性,密钥长度太小，IBM建议用112比特； 差分密码分析与线性分析； 20世纪90年代，RSA公司发起对DES的三次挑战； 1999年一百多个CPU利用并行算法，用23小时左右成功破译； 1999年在互联网上，用分割密钥方法成功破译。,三重DES（TDES）,执行3次DES算法，相当于使用3倍DES的密钥

15、长度的密钥，记加密密钥为 加密： 解密：,初始换位IP,逆初始换位,子密钥的生成,PC-1变换及密钥的分割,每轮左移位数,压缩置换PC-2,从56位密钥中取出48位,PC-2压缩算法,f算法,f算法是DES精华所在，用它来实现分组加密的扩展和混淆。在DES中，其他部分是线性的，而f算法是非线性的。 f算法主要由E-盒、S-盒和P-盒组成。,f算法的组成,E-盒（Expansion Permutation）,把数据明文的右半部分Ri从32位扩展到48位。 这样的好处有： 可以与48位的密钥进行异或运算； 有利于产生雪崩效应（Avalanche Effect）尽快地使输出（密文）的每一位依赖输入

16、（明文和密钥）的每一位。,E-盒扩展置换,S-盒代换,对48位的输入替代压缩成32位的输出。替代由8个S-盒进行。每个S-盒有6位输入，4位输出。,P-盒置换,对S-盒的32位输出进行一次换位,3.4 非对称密码学,公钥密码体制的基本原理 1976年，Diffie和Hellman提出了公钥密码体制 密钥公开是否有价值？,基于公开密钥的加密过程,公钥密码体制的加密功能,A向B发消息X， B的公钥为KUb,私钥为KRb 加密 Y = EKUb(X) 解密 X = DKRb(Y),基于公开密钥的认证过程,公钥密码体制的认证,A向B发送消息X A的公钥为KUa，私钥为Kra “加密”： Y = EKR

17、a(X) （数字签名） “解密”： X = DKUa(Y) 注意：不能保证消息的保密性,对称密码 公钥密码,公钥密码体制实现的关键问题： 如何确定公钥PK和私钥SK及加密、解密的算法。 SK与PK成对出现，需满足如下条件： Dsk(Epk(X)=X Dpk(Epk(X)X 在计算机上可以容易地产生成对的PK和SK 从已知的PK实际上不可能推导出SK 加密和解密运算可以对调，即 Dsk(Epk(X)=X=Epk(Dsk(X),如何确定PK和SK？,陷门单向函数 一个函数，若计算函数值很容易，并且在缺 少一些附加信息时计算函数的逆是不可行的，但 是已知这些附加信息（如SK）时，可在多项式 时间内计

18、算出函数的逆，那么我们称这样的函数 为陷门单向函数。 将特定的某类陷门单向函数记为F，随机选 取一个属于F的函数f，作为公开加密函数，其逆 函数是秘密解密函数，利用SK将可有效解密。,公钥密钥的应用范围,加密/解密 数字签名（身份认证） 密钥交换,公钥密码体制基于的数学难题,背包问题 大整数分解问题（The Integer FactorizationProblem,RSA体制） 有限域的乘法群上的离散对数问题(The Discrete Logarithm Problem,ElGamal体制） 椭圆曲线上的离散对数问题（The EllipticCurve Discrete Logarithm P

19、roblem,类比的ElGamal体制）,目前受到广泛认可的加密系统,大整数因子分解系统（如RSA） 椭圆曲线离散对数系统（ECC） 离散对数系统（如DSA）,RSA算法,由MIT的 Rivest,Shamir & Adleman 在 1977 提出 最著名的且被广泛应用的公钥加密体制 明文、密文是0到n-1之间的整数，通常n的大小为1024位或309位十进制数,RSA算法描述,加密： C=Me mod N, where 0MN,N=pq 解密： M=Cd mod N 公钥为（e，N）， 私钥为（d，p,q） 必须满足以下条件： Med = M mod N 计算Me和Cd是比较容易的 由e和n

20、确定d是不可行的,RSA 密钥产生过程,随机选择两个大素数 p, q 计算 N=p.q 注意 (N)=(p-1)(q-1) 选择 e使得1e(N),且gcd(e,(N)=1 解下列方程求出 d e.d=1 mod (N) 且 0dN 公布公钥: KU=e,N 保存私钥: KR=d,p,q,RSA的使用,发送方要加密明文M: 获得接收方的公钥 KU=e,N 计算: C=Me mod N, where 0MN 接收方解密密文C: 使用自己的私钥 KR=d,p,q 计算: M=Cd mod N 注意：M必须比N小,RSA Example,选择素数: p=17 e=7 求d: de=1 mod 160

21、 and d 160 因此d=23 （ 如何计算？） 公钥KU=7,187 私钥KR=23,17,11,RSA Example cont,利用 RSA 加解密： 明文M = 88 (88187) 加密: C = 887 mod 187 = 11 解密: M = 1123 mod 187 = 88,信息的认证是通过认证符进行。 产生认证符的方法一般分为三类： 信息加密：对明文加密后以密文作为认证符。 消息认证码（MAC）：用一个公开函数作用后，产生固定长度的数值作为认证符，也称为密码校验和。 散列函数：定义一个函数将任意长度的消息映射为定长的散列值，用散列值作为认证符。,消息认证：保证数据的完整

22、性,3.5 Hash算法,散列（Hash）函数,也称杂凑函数、哈希函数，通常简写为H，是一个单向公开函数。它可以将任意长的消息M映射为较短的、固定长度的一个值H(M)作为消息M的认证符。 H(M)也称消息摘要MD（message digest）或杂凑码、散列码。其目的是为文件、消息或其他的分组数据产生“指纹”。,Hash函数的结构,对不定长的输入产生定长的输出，且最后的结果要与所有字节有关。 分块填充链接模式，迭代型结构： 将输入数据分为L个固定长度为b比特的分组（分块、填充）； 散列算法中重复使用一个压缩函数f，产生一个n比特的输出（链接）。,Hash函数举例,典型的Hash算法有MD5（Rivest提出，1992年RFC 1321公布，码长128比特）和安全Hash算法SHA和SHA-1（Secure Hash Algorithm，码长160比特）。由于SHA和SHA-1比MD5多了32比特，所以更安全，但实现速度要慢些。,3.6 数字签名,数字签名（Digital Signature）在ISO74