1、一、密码学概论1. 密码体制及其分类2. 密码学发展简史3. 密码分析概念和原理二、密码编码学基本原理1. 对称密码概念与典型算法：Feistel结构、DES等2. 公钥密码概念与典型算法：RSA等3. 消息认证概念与典型算法：MD5等三、密码学典型应用1. 加密设备的部署2. 密钥管理与密钥分配3. 数字证书与PKI一、密码学概论1. 密码体制及其分类2. 密码学发展简史3. 密码分析概念和原理*学科内涵*研究如何隐秘地传递信息的学科*对信息以及其传输的数学性研究*与数学、信息论、计算机科学等紧密相关*是信息安全（认证、访问控制等技术）的基础和核心*其首要目的是隐藏信息的涵义，而不是隐藏信息
2、的存在*密码学（Cryptology） 泛指研究保密通信的学科，包括设计和破译两个方面*密码编码学（Cryptography） 研究如何达到信息秘密性、鉴别性等的科学，研究编码系统*密码编码者（cryptographer）*密码分析学（Cryptanalysis） 研究如何破解密码系统，或伪造信息使密码系统失效的科学*密码分析者（cryptanalyst）*加密和破译既相互对立又密切相关，二者的相互作用促进了密码学的发展*密码系统五元组（M，C，K，E，D）*明文空间 M*密文空间 C*密钥空间 K*加密算法 E*解密算法 D*明文(plaintext)原始的消息。*加密算法(encrypti
3、on algorithm) 对明文进行各种代替和变换的算法，加密算法的输入为明文和密钥，输出为密文。*密文(ciphertext) 加密后的消息。*解密算法(decryption algorithm) 加密算法的逆运算，输入密文和密钥，输出原始明文。*密钥(secret key) 加密算法的输入，密钥独立于明文和算法，算法根据所用的特定密钥而产生不同的输出。*明文转换为密文的运算类型*代替(Substitution) ：明文中每个元素映射成另一个元素*置换(Transposition) ：将明文元素重新排列*基本要求是不允许信息丢失（即可逆）*大多数密码体制使用多层代替和置换（即乘积密码系统）
4、*所用的密钥数*对称密码：收发双方使用相同的密钥（又称为单钥或传统密码）*非对称密码：收发双方使用不同的密钥（又称为双钥或公钥密码）*明文处理方式*分组密码：每次处理输入的一组元素，相应地输出一组元素*流密码：连续地处理输入元素，每次输出一个元素（又称为序列密码）*密码学发展史简图*密码学发展两大阶段*古典密码阶段(1949)：特定应用领域（军事、政治、外交）*现代密码学阶段(1949)：密码技术成为一门学科*著名论文: Communication theory of secrecy systems, Bell Syst. Tech. J.,Volume 28, 656-715, 1949.*
5、古典密码*密码学还不是科学,而是艺术*出现一些密码算法和加密设备*密码算法的基本手段出现，针对的是字符*简单的密码分析手段出现*主要特点：数据的安全基于算法的保密*二十世纪早期密码机*现代密码发展初期（1949-1975）*计算机使得基于复杂计算的密码成为可能*相关技术的发展*1949年Shannon的The Communication Theory of Secret Systems*1967年David Kahn的The Codebreakers*1971-73年IBM Watson实验室的Horst Feistel等几篇技术报告*主要特点：数据的安全基于密钥而不是算法的保密*现代密码公钥
6、密码学（1976-）*W. Diffie和E. M. Hellman提出公钥密码的思想(1976)*著名论文：W. Diffie and M. E. Hellman, New direction in cryptography, IEEE Tran. On Information Theory, IT-22, (6), 644-654,1976.*1977年Rivest,Shamir & Adleman提出了RSA公钥算法*90年代逐步出现椭圆曲线等其他公钥算法*主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能*现代密码系统设计要求*系统即使达不到理论上是不可破的，也应当为实际
7、上不可破的。就是说，从截获的密文或某些已知的明文密文对，要决定密钥或任意明文，在计算上是不可行的*系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥保密。这是著名的Kerckhoff原则*加密和解密算法适用于所有密钥空间中的元素*系统便于实现和使用*现代密码密码技术的商用化（1977-）*1977：美国国家标准局(现美国家标准与技术研究所NIST)颁布对称密码算法数据加密标准DES (Data Encryption Standard)*80年代出现“过渡性”的“Post DES”算法,如 IDEA、RCx、CAST等*90年代对称密钥密码进一步成熟，Rijndael、RC6、MARS、T
8、wofish、Serpent等出现*2001年Rijndael成为DES的替代者*非授权者通过各种办法（如搭线窃听电磁信号等）来窃取机密信息，称其为截收者。*截收者虽然不知道系统所用的密钥，但通过分析可能从截获的密文推断出原来的明文或密钥，这一过程称为密码分析。*研究如何从密文推演出明文或密钥的科学称为密码分析学。*破译者使用的策略取决于加密方案的固有性质以及破译者掌握的信息。*传统破译法穷举破译法*方法：*对截获的密文依次用各种可能的密钥试译，直到获得有意义的明文；*或者利用对手已注入密钥的加密机（比如缴获得到），对所有可能的明文依次加密直到得出与截获的密文一致的密文。*对策：将密钥空间和明
9、文空间设计得足够大。*传统破译法数学分析法*确定性分析法*方法：利用密文和部分明文等已知量以数学关系式表示出所求未知量（如密钥等），然后计算出未知量。*对策：设计具有坚实数学基础和足够复杂的加密函数*统计分析法*方法：密码破译者对截获的密文进行统计分析，找出其统计规律或特征，并与明文空间的统计特征进行对照比较，从中提取出密文与明文间的对应关系，最终确定密钥或明文。*对策：扰乱密文的语言统计规律*边信道攻击法（side channel attack）*利用密码系统实现时泄漏的额外信息，推导密码系统各种的秘密参数，也被称为“侧信道攻击方法”、“物理分析方法” *密码算法执行器件（加密芯片）的功耗*
10、密码算法各步骤执行的时间度量*电磁辐射*计算错误*与具体实现有关，非通用的分析方法，但更有效、更强大*当加密方案产生的密文满足下面条件之一或全部条件时，则称该方案是计算安全的(computationally secure)*破解密文的代价超出被加密信息的价值*破解密文需要的时间超出信息的有用寿命*问题的关键是，我们很难定量的评估成功破译密文需要付出的努力。但是，假设算法没有内在的数学弱点，那么就只剩下穷举攻击方法了，我们就能够对其成本和时间做出合理的评估。*穷举搜索密钥需要的平均时间*穷举方法尝试所有可能的密钥直到把密文翻译成可解的明文。平均而言，一般需要尝试所有可能密钥的一半才能成功。*下面
11、的表格给出了不同密钥长度所需的时间二、密码编码学基本原理1. 对称密码概念与典型算法：Feistel结构、DES等2. 公钥密码概念与典型算法：RSA等3. 消息认证概念与典型算法：MD5等*对称密码体制（Symmetric System）*传统密码算法（又称为单密钥算法）*加密密钥和解密密钥相同，或从一个易于推出另一个*能加密就能解密，加密能力和解密能力是结合在一起的，开放性差*如：DES、IDEA、RC5、AES等算法*对称密码体制*优点：*算法多、速度快、安全性好*缺点：*密钥更换、传递和交换需要可靠信道*如有N用户，则需要C=N(N-1)/2个密钥，N很大时，秘钥管理困难*不能实现数字
12、签名*对称密码体制的细分*根据明文处理方式，可以分为：*分组密码（block cipher) 将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。如DES、IDEA、AES等*流密码（stream cipher) 又称序列密码。流密码每次通过输出密钥流序列加密(通常是模2加)一位或一字节的明文。如A5、E0 、RC4等*DES (Data Encryption Standard,数据加密标准)*DES也称为DEA (Data Encryption Algorithm,数据加密算法)；*1972年，IBM设计完成；*1975年，IBM发布该算法的详细内容；*1976年，
13、美国联邦政府采用该算法，成为从二十世纪80年代到二十世纪末事实上的对称加密标准；*采用56位密钥（64位，其中每个字节一个奇偶校验位），64位明文；*共进行16轮加密操作。*输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。其第i轮迭代的输入为前一轮输出的函数：其中Ki是第i轮用的子密钥，由加密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。111,iiiiiiLRRLF RK*DES加密过程加密过程密文（64bits）IP置换（64bits）L0(32bits)R0(32bits)L1=R0R1=L0 f(R
14、0,k1)fki+16轮同样运算L16+R16=L15 f(R15,ki)+IP-1置换（64bits）明文（64bits）*IDEA(International Data Encryption Algorithm,国际数据加密算法)*1990年提出，1992年确定*IDEA受专利保护*应用于PGP（Pretty Good Privacy）*分组为64位，密钥为128位，52个子密钥，每个子密钥16位*8轮输出置换，每轮使用6个子密钥*过程与DES相似，但是相对简单一些*AES(Advanced Encryption Standard,高级加密标准)*虽然到目前为止，尚没有致命的攻击能够破解D
15、ES（目前大多数的破解都是针对DES密钥长度太短来破解） 但是已经影响到了DES密码体制的安全。*1997年4月15日，美国国家标准技术研究所（NIST）发起征集高级加密标准（Advanced Encryption Standard,AES）的活动，活动目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。*1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。作为进入AES候选过程的一个条件，开发者承诺放弃被选中算法的知识产权。*对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128
16、/192/256比特。*AES(Advanced Encryption Standard,高级加密标准)*1998年8月12日，在首届AES会议上指定了15个候选算法。*1999年3月22日第二次AES会议上，将候选名单减少为5个，这5个算法是RC6，Rijndael，SERPENT，Twofish和MARS。*2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进行了讨论。*2000年10月2日，NIST宣布了获胜者Rijndael算法。*2001年11月出版了最终标准FIPS PUB197。*AES的特点*非Feistel结构*采用对称和并行结构算法的实现更加灵活*适合
17、于现代处理器，也可在智能卡上实现*AES每轮主要包括四个步骤*字节代替*移位行（置换）*混合列（有限域上算术运算）*轮密钥加（与部分密钥异或）*RC4算法是由Ron Rivest于1987年为RSA公司设计的一种可变密钥长度（1-256B）的序列密码。*广泛应用于商业密码产品中。软件实现速度快，有广泛应用，如无线网络WEP、WAP，BT protocol encryption，Microsoft Point-to-Point Encryption，SSL (optionally)，Remote Desktop Protocol， Kerberos (optionally)*该算法的速度可以达到
18、普通分组加密的10倍左右，且具有很高级别的非线性。*非对称（公钥）密码体制*加密密钥和解密密钥不同，一个用于加密，一个用于解密，且从一个密钥导出另一个密钥是计算上不可行的*1976年Diffie 和 Hellman在New Directions in Cryptography中提出了非对称密钥密码*加密与解密由不同的密钥完成*加密：*解密：*知道加密算法，从加密密钥得到解密密钥在计算上是不可行的*两个密钥中任何一个都可以作为加密而另一个用作解密 XEYYXKU : XEDYDXXYKUKRKR :*保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信*签名：
19、将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读*签名保密 XDEZBAabKRKU : XZDEBbaKRKU:*优点：优点：*加密能力与解密能力是分开的*可满足不相识的人之间保密通信，适合网络应用*需要保存的密钥量大大减少，N个用户只需要N个*可以实现用户身份的确认*缺点：缺点：*速度较慢、密钥长(通常是1024比特以上)*Ron Rivest, Adi Shamir, Leonard Adleman于1977年发明*第一个非对称密码算法*安全性基于大数分解的难题*RSA安全性基于大数分解的难题*产生一对大素数很容易*求一对大素数的乘积很容易，但要对这个乘积
20、进行因式分解则非常困难*公钥和私钥经过一对大素数运算而来，破解算法的难度等价于分解这两个大素数的乘积1）取两个随机大宿舍p和q (保密)2）计算公开的模数n=p*q (公开）3）计算秘密的欧拉函数欧拉函数(n)=(p-1)(q-1) (保密)4）随机选择整数e(0e(n)，满足e和(n)互素(公开e，加密密钥)5）计算d，使得de1 mod (n) (保密d，解密密钥）6）公钥为(n,e),私钥为(n,d)7）将明文x加密得密文y，y=xe (mod n)8）密文y解密得明文x， x=yd (mod n)*密码分析者攻击RSA体制的关键点在于如何分解n*若分解成功使n=pq，则可以算出(n)(
21、p-1)(q-1)，然后由公开的e，解出秘密的d*计算能力的不断提高和分解算法的进一步改进，原来被认为是不可能分解的大数已被成功分解*RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解*RSA-155（512比特）已于1999年8月被成功分得到了两个78位（十进制）的素数*RSA-768（232十进制）已于2009年12月被成功分得到了两个116位（十进制）的素数*估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的*数字信封数字信封是一种解决两个对等实体之间通过网络发送大量数据的解决方法。*
22、通信方A用B的公钥K2加密A与B之间的共享密钥K1，并将其发送给B。*B用自己的私钥K3解密收到的消息，得到共享密钥K1。*A、B之间用对称密钥K1对收发的数据加解密。*数字信封的优点*由于非对称密码用于对称密码密钥的发布，较好地解决了对称密码的密钥发布问题。*由于对称密钥相对于要发送的明文而言通常要小，因此，密钥交换过程中的加解密过程很快。*由于使用对称密码进行实际数据的传输，因此，实际数据传输过程中的加解密过程很快。*消息认证是用来验证消息完整性的一种机制或服务。确保收到的数据确实和发送时一样（未被修改、插入、删除或重放），且发送方声称的身份是真实有效的*消息认证主要是为了防范（检测）主动
23、的完整性攻击*在网络环境中，传统的攻击类型有：* 认证内容认证消息（数据）的内容内容认证消息（数据）的来源来源认证消息（数据）的时效性时效性*使用认证函数产生某种认证符，分为三类：*消息加密：将整个消息的密文作为认证符。*消息认证码（MAC）：消息和密钥的函数，它产生定长的值，以该值作为认证符。*杂凑函数（Hash）：又称散列函数，将任意长的消息映射为定长的散列值的函数，以该散列值作为认证符。*对称加密*非对称加密*消息认证码Message Authentication Code(MAC)*利用密钥生成一个固定长度的短数据块，并将该数据附加在消息之后。M消息C MAC函数K 共享的密钥MAC
24、消息认证码MACC(K,M)*消息和MAC一起发送给接收方，接收方对收到的消息用相同的密钥进行相同的运算得到新的MAC，若新MAC与收到的MAC一致，则可确保：*（1）消息未被修改*（2）消息来自真正的发送方*（3）若消息中含有序列号，则可相信消息顺序是正确的。*单向散列函数(Hash) 又称为杂凑函数，是消息认证码的一种变形。*Hash与MAC的相同之处：*输入是可变大小的消息M，输出是固定大小的散列码。*Hash与MAC的不同之处：*散列码并不使用密钥，它仅是输入消息的函数。*散列码，也称为消息摘要(Message Digest)或者散列值，是消息的一个指纹。*散列码的应用*用对称密码对消
25、息及附在其后的散列码加密（冗余保护，提供认证与保密）*用对称密码仅对散列加密，对那些不要求保密性的应用，这种方法处理代价小（提供认证）*用发送方的私钥仅对散列加密（原理同上）*先用发送方的私钥对散列码加密，再用对称密码对消息和上述加密结果进行加密（常用的技术，提供保密与认证）*通信双方共享公共的秘密值S（类似于密钥），A将M和S的联合体计算散列值，并将其附在M后（提供认证）*散列函数的要求*给定一个消息，计算其散列值应该非常容易。*对给定的消息，散列值总是一致的。*给定一个散列值，找出创建该散列值的原消息是非常困难的。*任意给定两个消息，如果计算其消息摘要，两者的消息摘要必须不同。*如果两个消
26、息产生相同的散列值，则称为冲突(Collision)。*如果散列值的长度为n，则两个消息产生同样的散列值的概率为1/2n，n较大时，如为128位时，小概率事件难以发生。*散列函数的雪崩效应*两个原消息之间非常小的变化，得到的消息摘要应该有很大的变化。*散列函数的性质*散列函数可应用于任意大小的数据块；* 散列函数产生定长的输出；*对任意给定的x，计算H（x）比较容易，用硬件和软件均可实现；*对任意散列函数，找出满足 H（x）h 的x在计算上是不可行的，有些文献中称之为单向性；*对任意给定的分组x，找到满足y不等于x，且H（y） H（x）的y在计算上是不可行的，称之为抗弱冲突性；*找出任何满足H
27、（x）H（y）的偶对（x，y）在计算上是不可行的，称之为抗强冲突性。*1990年MIT的 Ron Rivest 提出MD4。*1992年 Ron Rivest 完成MD5 (RFC 1321)。*其发展历程为MD、MD2、MD3、MD4、MD5。*现行美国标准SHA-1以MD5的前身MD4为基础。*输入：任意长度的报文。*输入分组长度：512位。*输出：128 位的消息摘要。*MD5不是足够安全的*Dobbertin在1996年找到了两个不同的512位块,它们在MD5计算下产生相同的hash，但对一般性的一个512位分组，并不能总是找到一个产生同样hash的另一个分组；*2004年，山东大学王
28、小云教授针对一个X，计算MD5(X)，能够通过更改X的某些位，得到一个Y，使得MD5(X)=MD5(Y)。*Rivest说，我们不得不做更多的重新思考了。三、密码学典型应用1. 加密设备的部署2. 密钥管理与密钥分配3. 数字证书与PKI*链路加密*很多的加密设备*较高的安全性* 在每个交换节点都需要解密数据包*端到端加密*源主机加密和接收端解密*静载荷加密*包头为明文*链路加密：*对于链路层加密，每条易受攻击的通信链路都在包交换器两端装备加密设备。因此，所有通信链路的所有通信都受到保护。*尽管这在大型网络中需要很多加密设备，但它提供了较高的安全性。*缺点：消息每次进入包交换机都要被解密。*这
29、是必要的，因为交换机必须读取包头（packet header）地址来发送包。*因此，每次交换时消息都易受攻击。如果这是一个公共包交换网络， 则用户不可控制节点安全。*端到端加密：*对于端到端加密，加密过程在两个端系统上实现。*主机只能加密包中的用户数据部分而必须保留包头为明文，使得它能被网络读取。*因此使用端到端加密，用户数据是安全的，但是通信模式不安全，因为包头以明文传递。*为获得更高安全性，两种形式都采用。 主机使用端到端加密密钥加密包的用户数据部分。然后使用链路加密密钥加密整个包。*这样除了在包交换机里存储包时包头是明文外，整个包都是安全的。*密码技术的安全性都依赖于密钥*密码学的原则：
30、一切秘密寓于密钥之中*密钥管理：处理密钥自产生到最终销毁的整个过程中的有关问题*密钥分配技术是在不让其他人看到密钥的情况下将一个密钥传递给希望交换数据的双方的方法。*密钥分配往往和身份认证联系在一起。*一个密码系统的安全强度依赖于密钥分配技术。*密钥管理方法因所使用的密码体制（对称密码体制和公钥密码体制）而异。*对称密钥的分配*对称加密基于共同密钥实现，如何建立安全的数据通道传输密钥成为密钥管理的关键！*解决：建立安全传输密钥的数据通道*非对称密钥的分配*正确地获取其他用户的公钥是密钥管理的关键！*解决：公开密钥的集中式管理*分布式：网络中的主机具有相同的地位，他们之间的密钥分配取决于他们之间
31、的协商如基于公钥密码体制的密钥分配方法、Diffie-Hellman密钥交换协议*集中式：一个中心服务器(密钥分配中心KDC)，团体中的任何一个实体与中心服务器共享一个密钥。KDC接受用户的请求，为用户提供安全的密钥分配服务*PKI (Public Key Infrastructure)：X.509定义PKI为：创建、管理、存储、发布和撤消基于公钥密码系统的数字证书所需要的硬件、软件、人和过程的集合*一种标准的密钥管理平台，它能够为所有网络应用透明地提供采用加密和数据签名等密码服务所必须的密钥和证书管理*登记注册、管理、发布公钥证书，撤销过去签发但现已失效的密钥证书*公钥证书又称数字证书，可以
32、理解为是一种数据结构*证书中包含用户的合法公开密钥，并由颁发证书的授权机构签名*任何人可以阅读证书以确定证书拥有者的姓名和公钥，可以验证证书是由授权机构发出而非伪造的*只有授权机构才可以发行和更新证书*引入公认可信的第三方，依赖证书上的可信第三方的数字签名，用户可以确认公钥的真实性，即公钥没有丢失也不是假冒的*最常用的证书格式为X.509 v3 。X.509证书是经发布者数字签名的、用于绑定某公开密钥及其持有者身份的数据结构。*提供一个安全的框架，应用于：*Web服务器和浏览器之间的通信*电子邮件的安全通信*电子数据的内部交换*Internet上的信用卡交易*原理：*建立单一的认证机构（CA）
33、，由它管理所有证书*问题：*不易扩展到支持大量或者不同群体的用户*证书库难于维护，难于满足实际性能的需求*根私钥的维护困难*解决：*建立多个CA*问题：*如何建立多个CA之间的信任关系*层次结构模型*随着PKI规模的增大，CA要有效追踪它所认证的所有实体的身份就会变得困难。随着证书数量的增加，一个单一的认证机构可能会变成认证过程的瓶颈。采用认证层次结构是解决问题的办法。*在层次结构中，CA将它的权利授予一个或多个子CA。这些CA再依次指派它们的子CA，这个过程将遍历整个层次结构，直到某个CA实际颁发了某一证书。*交叉认证模型*交叉认证是把以前无关的CA连接到一起的认证机制。*当两者隶属于不同的
34、CA时，可以通过信任传递的机制来完成两者信任关系的建立。*CA签发交叉认证证书是为了形成非层次的信任路径。*一个双边信任关系需要两个证书，他们覆盖每一方向中的信任关系。这些证书必须由CA之间的交叉认证协议来支持。当某证书被认为是假的或者令人误解的时候，该协议将决定合作伙伴的责任。*证书链*由于用户拥有的可信证书管理机构数量有限，要与大量不同管理域的用户建立安全通信就需要建立信任关系，这就需要构建一个证书链。*证书链是最长用于 验证实体和其公钥 之间的绑定的方法。*为了获得对某一证书的信任，验证者必须验证每个证书的三个方面，直到到达一个可信的根。*有效性：证书是否在有效期内*可用性：证书是否已被撤销*真实性：证书是否为可信任的CA签发*验证者必须验证在证书链上的证书是否是由可信任CA的公钥对应的私钥签发的。通过验证可信根CA的证书，信任此证书并且使用该证书的应用程序就可以建立起对该实体的公钥的信任。
