《第二讲密码学及其应用课件.ppt》由会员分享，可在线阅读，更多相关《第二讲密码学及其应用课件.ppt（72页珍藏版）》请在三一办公上搜索。
1、第二讲 密码学及其应用,提纲,密码学的基本概念典型的加密技术 替换 一次一密 置换典型加密标准 对称密钥 分组加密 DES AES 流加密 RC4 公开密钥 RSA Diffie-Hellman 哈希与认证码,Cryptography,IsA tremendous toolThe basis for many security mechanismsIs notThe solution to all security problemsReliable unless implemented properlyReliable unless used properlySomething you sho
2、uld try to invent yourself unless you spend a lot of time becoming an expertyou subject your design to outside review,Basic Concepts in Cryptography,Encryption scheme:functions to encrypt, decrypt data key generation algorithmSecret key vs. public keyPublic key: publishing key does not reveal key-1S
3、ecret key: more efficient, generally key = key-1 Hash function, MACMap input to short hash; ideally, no collisionsMAC (keyed hash) used for message integritySignature schemeFunctions to sign data, verify signature,术语,加密（encryption）解密(decryption)明文（plaintext） 密文（ciphertext） 算法（algorithm） 密钥（key） C=E(
4、K,P) 对称（symmetric） P=D(K,E(K,P) 非对称（asymmetric）P=D(KD,E(KE,P),KE,KD公私密钥对,典型的加密算法举例-替换法(substitution),单一字母替换密码(monoalphabetic cipher) 或简单替换法(simple substitution)凯撒密码(Caesar cipher) 将一个字母替换成它后面固定位置的另一个字母. ci=E(pi)=pi+3 优缺点:简单易记.容易被推出完整的加密模式. 分析破译: 线索- 单词间的间隔被保留,双字母被保留.基于猜测的推论.也可以使用更加系统的方法.哪些字母通常在词首词尾哪
5、些前缀后缀常用.,破译的难度,字母表替换- 26!种尝试 每微秒1种,1000多年简化破译的方法: 利用语言知识(字母出现的频度). 当报文足够长时,分析分布频率能快速暴露明文中的很多字母.密码专家的两难选择: 规律化算法化方便记忆 但规律性给破译者提供了线索,典型的加密算法举例-一次一密乱码本(one-time pad),特点：密码本,发送者与接收者一样,需要无限数量的密钥.(每次替换都不一样)长随机数序列 随机数发生器, 不是真正的随机数,实际上是具有很长周期的序列弗纳姆密码(Vernam Cipher) 使用任意长的不重复数序列,与明文组合在一起.电传打字机.只要密钥不重复使用,对破译攻
6、击具有免疫力.,字母先转换成与它们等价的数字（0-25） 与随机数字求和，然后模26,典型的加密算法举例-一次一密乱码本(one-time pad),密码本,随机数来源于任何书籍乐谱或其他具有可分析结构的对象.例如:电话本协商从35页开始,使用每个电话号码的中间2位.再mod 26作为替换密码的密钥.,Evaluation of one-time pad,AdvantagesEasy to compute encrypt, decrypt from key, textAs hard to break as possibleThis is an information-theoretically
7、 secure cipherGiven ciphertext, all possible plaintexts are equally likely, assuming that key is chosen randomlyDisadvantageKey is as long as the plaintextHow does sender get key to receiver securely? Idea for stream cipher: use pseudo-random generators for key.,置换(transposition ) 排列(permutation),列置
8、换加密/解密复杂度: 处理时间与报文长度成正比;存储空间与报文长度直接相关当时间要求很严格时,不特别适合于长报文,列置换举例,T H I S IS A M E SS A G E TO S H O WH O W A CO L U M NA R T R AN S P O S I T I O NW O R K S,tssoh oaniw hasso lrsto imghw utpir seeoa mrook istwc nasns,双字母组三字母组英语中最常见的双字母组(digram)和三字母组(trigram) 出现频率有的高,有的低.置换密码的分析破译 计算字母的出现频率,推断置换-分割成列(如
9、何分割? 使用双字母分析破译,滑动窗口,看常见的双字母出现吗? 大多数双字母组看起来是否合理),列置换给破译者的线索,优质密码特征,加密解密工作量 应由所要求的安全程度决定密钥集合和加密算法 不应过于复杂（不应对密钥的选择和算法能处理的明文类型加以限制）执行过程要尽量简单 （复杂算法常常使编程出错。）密码中的差错不应具有传播性，也不应影响报文中的其他信息。 （列置换中丢了一个字母，会影响到后面的加密；替换中则只影响一个字符。）密文不应比原文大不能携带更多的信息，反而会给破译者更多资料去推测,可信赖加密体制的特点,基于可靠的数学基础严格分析证实是可靠的经得起时间检验符合商业级加密标准的三种流行算
10、法DES(Data Encryption Standard) RSA(Rivest-Shamir-Adelman) AES(Advanced Encryption Standard),密码分析学：破译加密体制,惟密文攻击（ciphertext-only attack） 只有密文可用。依赖分布、可能性、可用密文的特性全部或部分明文： 已知明文攻击（known plaintext）知道全部或部分明文。有C,P推出C=E(P)中的E ； 可能明文攻击（probable plaintext）可能发现已知报文和解密部分相匹配的位置，从而推测整个转换； 选择明文攻击（chosen plaintext）,分
11、析者渗透发送过程（如发送特定报文给特定用户，看效果）有加密算法和密文： 选择密文攻击（chosen ciphertext）分析者可以对大量的明文使用算法，从而找出恰好加密成密文的那份明文。 目的-推断出发送者的加密密钥获得了几对明文和密文，推出加密密钥,当加密方案产生的密文满足下面条件之一或者全部条件时，则称该加密方案是计算安全的。（computationally secure）破解密文的代价超出被加密信息的价值破解密文需要的时间超出信息的有用寿命。暴力破解Brute Force Search 穷举搜索密钥的时间,对称和非对称加密体制,对称：效率高 问题：如何进行密钥分配非对称:公开密钥 密钥
12、管理（key management）存储、维护、激活密钥,对称和非对称加密体制,非对称:公开密钥需要解决：密钥管理（key management）存储、维护、激活密钥,流密码和块密码,流密码（stream cipher） 优点-转换速度快，低错误扩散率 缺点- 低扩散性 易被恶意插入和篡改,流密码设计要素,加密序列应该有一个长周期（伪随机数生成器使用一个函数产生一个实际上不断重复的确定比特流）密钥流应该尽可能接近真随机数流的性质。为了抵抗穷举攻击，伪随机数生成器的输入密钥必须足够长。至少128位,块密码（block cipher） 优点-高扩散性，无法插入符号 缺点-加密较慢 错误扩散,混乱性
13、（confusion）明文中字母发生变化时，截获者不能预知密文会有什么变化 .即明文密文之间有很复杂的关系。 （恺撒密码混乱性不好）扩散性（diffusion）将明文中单一字母包含的信息散布到整个输出中。 （明文的变化可以影响到密文的很多部分）,分组密码与Feistel 密码结构大多数分组密码基于 Feistel Cipher Structure分组加密器本质上就是一个巨大的替换器64位的分组就会有 264种输入采用了乘积加密器的思想Feistel密码结构的设计动机分组密码对n比特的明文分组进行操作，产生一个n比特的密文分组，共有2n个不同的明文分组，每一种都必须产生一个唯一的密文分组，这种变
14、换称为可逆的或非奇异的。 可逆映射 不可逆映射 00 11 00 11 01 10 01 10 10 00 10 01 11 01 11 01,n = 4时的一个普通代换密码的结构,Feistel密码Claude Shannon and Substitution-Permutation Ciphers 1949年，Claude Shannon 引进了substitution-permutation (S-P) networks的思想，即现代的乘积加密器modern substitution-transposition product cipher，形成了现代分组加密的基础。 S-P netwo
15、rks 是基于替代substitution (S-box)和置换permutation (P-box)这两个基本操作的。提供了对明文信息处理所做的confusion和diffusion 。Shannon认为，为了对付基于统计分析的密码破译，必须对明文作confusion(扰乱)和diffusion(扩散)处理，以减少密文的统计特性，为统计分析制造障碍。diffusion 明文统计结构扩散消失到大批密文统计特性中，使明文和密文之间统计关系尽量复杂；confusion 使密文和加密密钥之间的关系尽量复杂。,Feistel密码结构（所有对称密钥使用的最普通的结构）1973年，Horst Feiste
16、l提出了基于可逆乘积加密器概念的Feistel Cipher：将输入分组分成左右两部分，实施Shannons的substitution-permutation network 概念对左半部数据实施多回合的替代操作(substitution)对右半部数据和子密钥应用round函数F，其输出与左一半做异或将这两部分进行互换(permutation swapping),Feistel加密器设计原则分组长度：分组越长则安全性越高，但加/解密速度越低，分组长度为64位是一个合理的折衷密钥长度：密钥越长越安全，但加/解密速度越低，64位长的密钥已被证明是不安全的，128位是常用的长度迭代次数：迭代越多越安
17、全，通常为16次迭代子密钥产生算法：越复杂则密码分析越困难Round循环函数：越复杂则抗密码分析的能力越强快速的软件加密/解密：算法的执行速度很重要简化分析难度：算法简洁清楚，易于分析弱点，发现密码Feistel解密算法：以密文作为算法的输入，以相反的次序使用密钥Ki，Kn、Kn1、.、K0.,数据加密标准（DES）,背景历史70年代初期，美国国家标准局（National Bureau of Standard,NBS） 研制更大众化的加密技术 加密应该被评估和标准化，提高不同公司间交换加密信息的能力。1972年征集制订公开加密算法。要求算法是公开的，安全性依赖于密钥（由用户控制）IBM 的Lu
18、cifer后来成为DES, 1977年被NIST采纳为FIPS PUB46 。 用于无类别的公共和私人通信。后被ISO接纳为国际标准,DES 算法概述,替换和置换相结合，16次反复的置换和替换明文分块64位 密钥64位（任意56位数字+8位效验位），用户可随意改变密钥利用了混乱（输入和输出没有明显的联系）和扩散（将明文中一位的影响扩展到密文的多个位）使用标准的算术和逻辑运算，软件实现，芯片实现70年代，更长密钥的DES感兴趣， 问题-DES算法固定56位密钥,替换与置换循环,循环细节将明文分成左右两部分，如Feistel cipher:Li = Ri1Ri = Li1 xor F(Ri1, K
19、i)将32-bit右半部和48-bit子密钥做以下动作:expands R to 48-bits using permutation Eadds to subkeypasses through 8 S-boxes to get 32-bit resultfinally permutes this using 32-bit perm P,双重DES,两个密钥k1和k2 ,双重加密E(k2,E(k1,m) Merkle和Hellman指出两次加密不比一次更好。破译者需要已知的两对明文P1,P2和密文C1,C2. （1）尝试用所有可能的密钥对P1加密，保留加密结果Ps，Ps=E(P1,Ki) (需要
20、256步,有256种可能的Ki) （2）然后用单一密钥解密C1, P=D(C1,Kj) 在Ps中找匹配者 得到一对密钥（ki,kj）.用P2,C2检查。看C2=E(kj,E(ki,P2)?需要时间2*256=257仅加倍了破译者的工作。,三重DES (Triple DES),C=E(k1,D(k2,E(k1,m) 有效密钥长度增加到112位。已经非常坚固。 缺点：要求3倍于DES的计算量 速度慢；与DES一样分组长度是64位，就效率与安全性而言，应更加长,密钥长度问题56-bit 密钥有256 = 72,057,584,037,927,936 7.2亿亿之多强力搜索( brute force
21、search ) 似乎很困难，20世纪70年代估计要10002000年技术进步使穷举搜索成为可能1997年1月29日，RSA公司发起破译RC4、RC5、MD2、MD5，以及DES的活动，破译DES奖励10000美金。明文是：Strong cryptography makes the world a safer place. 结果仅搜索了24.6%的密钥空间便得到结果，耗时96天。1998年在一台专用机上(EFF)只要三天时间即可 1999年在超级计算机上只要22小时!,DES的安全强度,DES的安全性,90年，Biham和Shamir 发明了差分密码分析法（differential crypt
22、analysis）,研究加密算法发生变化时，算法健壮性的变化。 91年应用于DES，发现DES的设计似乎是最佳的。改变重复次数、扩展替换规律以及改变重复的顺序，算法都会削弱且能破译。1997年，使用3500台计算机并行计算，在4个月内推测出一个DES密钥，98年，研制出“DES cracker”4天内找到一个DES密钥。价值10万美元在这些攻击面前，三重DES仍然表现良好。95年，美国国家标准技术研究所（National Institute of Standard and Technology,NIST ,以前的NBS）寻找一种新的、更强有力的加密算法-结果是AES,AES产生背景,97年1月
23、，NIST召集专家研制新的加密体制， 要求：算法公开；对称块密码算法，每块128位；可用密钥长度128、192、25698年，选出15种，99年，5种候选。评估准则：考虑安全性，计算效率，存储空间要求，硬件和软件平台的适应性和灵活性荷兰密码学家 Vincent Rijmen,Joan Daemen研制的Rijndael算法。,Rijndael算法概述,特点：快速的算法，易在简单处理器上实现，坚实的数学基础。 没有使用 Feistel结构，在每一轮使用代换和移位时都并行处理整个数据分组。替换、置换、移位、加、特殊的或运算与DES一样，重复循环，对128、192、256位的密钥分别有9、11、13
24、次循环（轮）。,循环中的4个步骤,字节替换根据一张替换表替换128位分块中的每个字节(混乱操作) 行移位置换. 对128/192位的分块,第n行循环左移(n-1)个字节. 对256位的分块,第2行移位1个字节,第3,4行分别移位3,4个字节(移位操作). 列混合左移、与自身异或（混乱、扩散） 加上子密钥 结果与密钥的一部分(密钥的变体)进行异或运算（混乱性、合并了密钥） 对输入数据实现了很好的混乱和扩散。密钥频繁与中间结果混合，在结果中很好的扩散了,与DES的比较,其他设计良好的对称密码算法,公开密钥加密,对称密钥机制的问题：密钥分配和管理公钥加密思想 Diffie 和Hellman 1976
25、年首次公开提出公钥加密思想，完全不同于传统密码学方法，真正革命性的进步。基于数学函数，两个单独的密钥。非对称加密体制 公开密钥-每个用户有两个密钥，公钥kpub 私钥kpriv P=D(kpriv,E(kpub,P);一些算法还满足 P=D(kpub,E(kpriv,P),对公钥密码算法的要求,产生一对密钥在计算上容易实现加密过程在计算上容易，即已知公钥和要加密的消息，容易得到C=E(kpub,M)接收方利用私钥解密过程在计算上容易已知公钥，要确定私钥在计算上不可行已知公钥和密文，要恢复明文在计算上不可行加密解密函数在顺序可以交换 M=D(kpub,E(kpriv,M)=D(kpriv,E(k
26、pub,M),公开密钥加密,关于公钥加密的常见误解误解一 公钥加密比传统加密更抗密码分析 没有任何原理能说明传统加密和公钥加密哪个更优越误解二 公钥加密是一种通用技术，传统加密过时了。 公钥加密计算开销太大误解三 相对于传统加密使用密钥分发中心的握手协议而言，使用公钥分发密钥的代价是微不足道的 公钥加密需要协议、还常常需要中心代理,公开密码系统的应用,从广义上将公钥加密系统分为三类机密/解密：发送者用接收者的公钥加密消息数字签名：发送者用自己的私钥“签名”消息。把加密算法用于消息或者消息函数的一小块数据，完成对消息的签名。密钥交换：双方联合操作交换会话密钥。可以使用多种方法，要单方或双方的私钥
27、。,公开密码系统的应用,RSA 、椭圆曲线 可用于加密解密、数字签名、密钥交换Diffie-Hellman 用于密钥交换DSS 用于数字签名,RSA加密(Rivest-Shamir-Adelman),发明者：2002年图灵奖获得者 Ronald L. Rivest（罗纳德李维斯特）麻省理工学院（MIT）电子和计算机科学系Viterbi 讲座教授， RC2, RC4,RC5,RC6的发明者。也是 MD2，MD4和 MD5加密哈希(Hash)函数的发明者。 Adi Shamir（阿迪萨莫尔）以色列魏兹曼研究院的阿迪.沙米尔教授是国际著名的密码学专家，为现代密码学提供了很多新的理念，多年来始终活跃在
28、密码学界的前沿，是学界公认的领军人物。Shamir秘密共享方案，Merkle-Hellman密码系统的破解，视觉密码，以及TWIRL和TWINKLE因子分解设备。Shamir博士同Eli Biham一起发现了微分密码分析法一种用来破解分组密码的一般性方法 Leonard M. Adleman（伦纳德阿德曼）是计算机病毒的教父（他的博士生Cohen是计算机病毒的发明人），DNA计算的创始人,RSA加密(Rivest-Shamir-Adelman),1978年提出,直到现在仍然是安全的.依靠质因子分解问题的难解度. 至今为止,还没有人找到捷径或简单的办法在一个有限域中分解大数.表示：密钥d,e 用
29、于解密加密 可以互换 C=Pe mod n P= Cd mod n特点：公钥算法速度慢,一般执行时间是对称加密的10000倍.只用于一些专门的/很少发生的场合.对称加密是常用的工具,RSA算法,1978年提出，基于数论理论，大数提取因子非常困难 (1) 选择两个大质数：p和q（应大于10100） (2) n = p q z = (p-1) (q-1) (3) 选择一个和z互为质数的d (4) 找出e，使得( e d ) (mod z) = 1 加密：C = Pe ( mod n ) 公钥（e,n） 解密： P = Cd ( mod n ) 私钥（d,n）作业：如何产生大质数？编写一个随机产生大
30、质数的算法。,RSA算法举例,P=3,q=11,n=33,z=20 ,d=77e=1(mod 20)= e=3 C=P3(mod 33)P=C3(mod 33),RSA的安全性分析,若破译者能对公开的n作因子分解，找出p和q，就可得出z，由z和e可以得到d 对大数的因式分解极其困难，对200位数分解因子需40亿年。所以RSA算法被广泛使用。,建立共享密钥,n是个大素数，(n-1)/2也是素数，且g要满足一定的条件（g是n的本原根）x,y是A,B秘密选择的大数，xn,yn对于任意小于n的整数K和n的本原根g,能找到唯一的指数i,使得 k=gi mod n 称指数i为k的基为g模为n的离散对数，记
31、作dlogg,n(k)安全性-基于计算离散对数的困难性,Diffie-Hellman密钥交换,水桶队列攻击或中间人攻击,Diffie-Hellman密钥交换,其他公开密钥算法,DSS 使用了SHA-1，并提出了数字签名算法DSA。1991年提出，是专为数字签名功能设计的算法，不能用于加密或密钥交换基于椭圆曲线的公开密钥算法（Menezes and Vanstone 1993），与RSA相比，ECC的主要吸引力在于只需要很少的位数就能提供相同强度的安全性，减少了处理开销。背包算法-背包总重量公开，所有可能的物品公开列出，“根据给定总重量找出可能物品明细列表” NP难问题（Raplh Merkle
32、）不再安全,单向散列函数(one-way function),散列函数的目的为文件、消息或其他数据块产生“指纹”散列函数H必须具备的性质 -给定任意长度P, 容易计算出固定长度的H(P)，并可在软/硬件上实现-实用性 -给定H(P) ，推不出P，在计算上不可行-单向性，或称为抗原像攻击性（preimage resistant） -给定P, 找到P,满足H(P)=H(P)在计算上不可行-抗第二原像攻击性，抗弱碰撞攻击（Weak collision resistant）- 找到满足H(P)=H(P)的任意一对(P,P)在计算上不可行-抗碰撞性或抗强碰撞性。 -输入明文即使只有1位变化，会导致完全不
33、同的输出,Applications of one-way hash,Password files (one way)Digital signatures (collision resistant)Sign hash of message instead of entire messageData integrityCompute and store hash of some dataCheck later by recomputing hash and comparingKeyed hash for message authenticationMAC Message Authenticatio
34、n Code,用于数据完整性验证,用于数字签名(digital signature),只有发送者才能生成的标志,接收者可以用来确认是否属于发送者必须满足两个主要条件:不可伪造;可检验 在完成交易需要另外两个性质: 不可变(完整性) 不可重用(时间戳),接收方可以验证发送方所宣称的身份发送方以后不能否认该消息的内容接收方不可能自己编造这样的消息,用于数字签名（1）,一些直接基于加密机制的签名方案,对签名的批评：签名和保密合在一起认证不需对整条信息加密,用于数字签名（2）,对hash后的信息进行加密用作签名,消息认证码,消息认证是一种允许通行者验证所收消息是否可信的措施 验证消息的内容有无被篡改
35、验证信源是否可信 验证消息的时效性。,基于散列函数消息认证码-HMAC,设计散列函数不是为了用作MAC，因此不能达到MAC的目的将密钥结合到现有的散列算法中，最广为被接收的方案是HMAC。发布为RFC2104标准，被应用于Internet安全协议中，IPsec ,TLS , SET等。,HMAC的设计目标不改动就可以使用散列函数。嵌入式散列函数要有很好的可移植性保持散列函数原有性能，不发生显著退化使用和处理密钥简单,基于散列函数消息认证码-HMAC,uses hash function on the message:HMACK(M)= Hash(K+ XOR opad) | Hash(K+ X
36、OR ipad) | M) where K+ is the key padded out to size opad, ipad are specified padding constants ipad=00110110 (重复b/8次) opad=01011100 (重复b/8次)overhead is just 3 more hash calculations than the message needs aloneany hash function can be usedeg. MD5, SHA-1, RIPEMD-160, Whirlpool,基于分组密码的MACCMAC,CMAC的操作方式适用于AES和3DESwidely used in govt & industrybut has message size limitationthus forming the Cipher-based Message Authentication Code (CMAC)adopted by NIST SP800-38B 美国国家标准及技术研究特刊,基于分组密码的MACCMAC,
