网络信息安全-第2章_网络信息安全基础.ppt

北京邮电大学 朱洪亮,网络信息安全基础-密码学部分,北京邮电大学信息安全中心,本节主要内容,北京邮电大学信息安全中心,本节主要内容,北京邮电大学信息安全中心,密码学基本概念,密码学(cryptology)：研究信息系统安全保密的科学，是关于加密和解密变换的一门科学，是保护数据和信息的有力武器。它包含两个分支 密码编码学(cryptography)，对信息进行编码实现隐蔽信息的一门学问 密码分析学(cryptanalytics)，研究分析破译密码的学问。,北京邮电大学信息安全中心,密码学基本概念,明文(消息)(plaintext) ：被隐蔽消息。 密文(ciphertext)或密报(cryptogram)：明文经密码变换成的一种隐蔽形式。 加密(encryption)：将明文变换为密文的过程。 解密(decryption)：加密的逆过程，即由密文恢复出原明文的过程。 加密员或密码员(cryptographer)：对明文进行加密操作的人员。,北京邮电大学信息安全中心,密码学基本概念,加密算法(encryption algorithm)：密码员对明文进行加密时所采用的一组规则。 接收者(receiver)：传送消息的预定对象。 解密算法：接收者对密文进行解密时所采用的一组规则。 密钥(key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。 截收者(eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。,北京邮电大学信息安全中心,密码学基本概念,密码分析(cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。 密码分析员(cryptanalyst)：从事密码分析的人 被动攻击(passive attack)：对一个保密系统采取截获密文进行分析的攻击。 主动攻击(active attack)：非法入侵者(tamper)、攻击者(attcker)或黑客(hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。,北京邮电大学信息安全中心,密码体制组成,一个密码系统，通常简称为密码体制，由5部分组成：,北京邮电大学信息安全中心,密码体制组成-加密传输过程,北京邮电大学信息安全中心,密码体制组成-加密传输过程,用户a,用户b,传送给b的信息,b收到信息,c窃听到的信息!#$%,北京邮电大学信息安全中心,密码体制组成-加解密过程,加密: c = e(m,ke),m,c,e,ke,c,m,kd,d,m-明文 c-密文 ke-加密密钥 kd-解密密钥 e-加密算法 d-解密算法,解密: m = d(c, kd),北京邮电大学信息安全中心,密码体制组成,注意,数据安全基于密钥而不是算法的保密。也就是说，对于一个密码体制，其算法是可以公开的，让所有人来使用、研究。但具体对于某次加密过程中所使用的密钥，则是保密的。,北京邮电大学信息安全中心,密码系统分类,根据密钥的使用方式分类 对称密码体制（秘密钥密码体制） 用于加密数据的密钥和用于解密数据的密钥相同，或者二者之间存在着某种明确的数学关系。 加密：ek(m)=c 解密：dk(c)=m 非对称密码体制（公钥密码体制） 用于加密的密钥与用于解密的密钥是不同的，而且从加密的密钥无法推导出解密的密钥。 用公钥kp对明文加密可表示为：ekp(m)=c 用相应的私钥ks对密文解密可表示为：dks(c)=m,北京邮电大学信息安全中心,密码系统分类,根据明文和密文的处理方式分类 （对称密码） 序列密码(流密码)体制（stream cipher） 将明文和密钥都划分为位(bit)或字符的序列，并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密。 m=(m1, m2, ,mn) ， ke=(ke1, ke2,ken)，c=(c1, c2,cn)，其中ci=e(mi,kei) ，i=1,2,n。 分组密码体制（block cipher） 设m为明文，分组密码将m划分为一系列明文块mi，通常每块包含若干字符，并且对每一块mi都用同一个密钥ke进行加密。 m=(m1, m2, ,mn) ，c=(c1, c2 , ,cn,)，其中ci=e(mi,ke)， i=1,2,n。,北京邮电大学信息安全中心,密码系统分类,根据加密算法是否变化分类 设e为加密算法，k0, k1,kn,为密钥，m0,m1,mn为明文，c为密文 固定算法密码体制 c0=e(m0,k0), c1=e(m1,k1),., cn=e(mn,kn) 变化算法密码体制 c0=e1 (m0,k0), c1=e2 (m1,k1),., cn=en (mn,kn),北京邮电大学信息安全中心,密码分析学,截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学 密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。 密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别 密码设计是利用数学来构造密码；密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力，有时还靠点运气。,北京邮电大学信息安全中心,密码分析学-分析方法分类,北京邮电大学信息安全中心,密码分析学-典型分析方法,最可靠的攻击办法:强力攻击 统计分析 最有效的攻击:差分密码分析,通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特. 线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统 插值攻击方法 密钥相关攻击,北京邮电大学信息安全中心,古典密码学,经典密码（古典密码）对于今天来说，是极不安全的，是极易破解的，但其基本方法仍然是近、现代密码学的基础。 经典密码运用的两种基本技术： 代换法：将明文字母替换成其他字母、数字或符号 置换法：明文的字母保持相同，但顺序被打乱,北京邮电大学信息安全中心,古典密码学-代换密码,代换法，是将明文字母替换成其他字母、数字或符号的方法。 例如：明晨五点发动反攻 明文：ming chen wu dian fa dong fan gong 密文：gnogn afgno dafna iduwn ehcgn im caesar密码（已知的最早的代换密码）,例如：明晨五点发动反攻 明文：ming chen wu dian fa dong fan gong 密文：plqj fkhq zx gldq id grqj idq jrqj,北京邮电大学信息安全中心,古典密码学-代换密码,caesar密码,如果让每个字母等价于一个数值： a=0,b=1,z=25 则加密公式为： c=e(p)=(p+3) mod 26 更一般地： c=e(p)=(p+k) mod 26 解密：p=d(c)=(c-k) mod 26,北京邮电大学信息安全中心,古典密码学-代换密码,用强力分析可轻松破解caesar密码,通常，加密和解密算法是已知的。 需测试的密钥只有25个。 明文所用的语言是已知的，其意义易于识别。 因此，为了提高穷举分析的难度，密钥空间必须很大。例如3-des算法的密钥长度为168位，密钥空间为2168。,北京邮电大学信息安全中心,古典密码学-代换密码,单表代换密码,使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。 例如，明文a用c来代换，b用剩下的25个字母中随机的一个来代换，c用剩下的24个字母中随机的一个来代换，以此类推。这样，密钥空间为26！，约4*1026种可能的密钥。,北京邮电大学信息安全中心,古典密码学-代换密码,破解单表代换密码,根据频率统计进行分析 确定每个字母被映射到什么字母 单个字母出现的可能是a或i 一般来说3个字母出现的可能是the或and 还可以用其他通常出现的双字母或三字母组合 还可以应用其它很少应用的字母,北京邮电大学信息安全中心,古典密码学-代换密码,破解单表代换密码,最常见的两字母组合，依照出现次数递减的顺序排列：th、he、in、er、an、re、de、on、es、st、en、at、to、nt、ha、nd、ou、ea、ng、as、or、ti、is、et、it、ar、te、se、hi、of 最常见的三字母组合，依照出现次数递减的顺序排列：the、ing、and、her、ere、ent、tha、nth、was、eth、for、dth,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码,改变明文的语法模式和结构，可抵抗频度分析 常见的多表代换密码：playfair密码、hill密码、vigenre密码,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码-playfair密码,由英国科学家charles wheatstone于1854年发明，以其好友baron playfair的名字命名。 在第一次世界大战中，英军使用playfair密码作为陆军的标准加密体制。 在第二次世界大战中，盟军使用它作为通信加密工具。,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码-playfair密码,playfair算法基于使用一个55字母矩阵，该矩阵使用一个关键词构造。从左至右、从上至下填入该关键词的字母（去除重复字母），然后再以字母表顺序将余下的字母填入矩阵剩余空间。字母i和j 被算作一个字母。,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码-playfair密码规则,属于相同对中的重复的明文字母将用一个填充字母进行分隔，因此，词balloon将被加密为ba lx lo on。 属于该矩阵相同行的明文字母将由其右边的字母替代，而行的最后一个字母由行的第一个字母代替。例如，ar被加密为rm。 属于相同列的明文字母将由它下面的字母代替，而列的最后一个字母由列的第一个字母代替。例如，mu被加密为cm 否则，明文的其他字母将由与其同行，且与下一个同列的字母代替。因此，hs成为bp，ea成为im（或jm，这可根据加密者的意愿而定）。,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码-playfair密码优点,playfair密码与简单的单一字母替代法密码相比有了很大的进步 虽然仅有26个字母，但有2626676种字母对，因此，识别字母对要比单个字母要困难得多 一个明文字母有多种可能的代换密文字母，使得频率分析困难的多(hs成为bp, hq成为yp)。 由于这些原因，playfair密码过去长期被认为是不可破的。,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码- vigenre密码例子,明文为attack begins at five，密钥为cipher， attack begins at five 明文 cipher cipher ci pher 密钥 - cbihgb dmvprj cb upzv 密文 去除空格后为cbihgbdmvprjcbupzv,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码- vigenre密码分析,如果密文足够长，其间会有大量重复的密文序列出现。通过计算重复密文序列间距的公因子，分析者可能猜出密钥词的长度（因为密钥词是重复使用的） 。,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码- 一次一密,一次一密乱码本（one-time pad）, 由major joseph mauborgne 和at&t公司的gilbert vernam 在1917发明。是无法攻破的密码体制。 一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并被粘成一个乱码本。发送者用每一个明文字符和一次一密乱码本密钥字符的模26加法。 每个密钥仅对一个消息使用一次。发送者对所发送的消息加密，然后销毁乱码本中用过的一页或磁带部分。接收者有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。接收者在解密消息后销毁乱码本中用过的一页或磁带部分。新的消息则用乱码本中新的密钥加密。,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码- 一次一密的优点,面对一条待破译的密文，攻击者能够找到很多个与密文等长的密钥，使得破译出的明文符合语法结构的要求，因为密钥本身是随机的，是没有规律的。 就算在这些可能的密钥中存在真正的密钥，攻击者也无法在这些可能的密钥中确定真正的密钥，因为密钥只是用一次，攻击者无法用其它密文来验证这个密钥，因此是无法攻破的。,北京邮电大学信息安全中心,古典密码学-代换密码,多表代换密码- 一次一密的缺点,一个一次一密加密系统，需要在某个规则基础上建立百万个随机字符，提供这样规模的真正随机字符集是相当艰巨的任务。 对每一条消息，需要提供给发送发和接收方等长度的密钥，因此存在庞大的密钥分配问题。 基于这些原因，一次一密在实际中极少应用。,北京邮电大学信息安全中心,古典密码学-置换密码,在置换密码中，明文的字母保持相同，但顺序被打乱了。 在简单的纵行换位密码中，明文以固定的宽度水平地写在一张图表纸上，密文按垂直方向读出，解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。,北京邮电大学信息安全中心,古典密码学-置换密码,plaintext: computergraphicsmaybeslowbutatleastitsexpensive c o m p u t e r g r a p h i c s m a y b e s l o w b u t a t l e a s t i t s e x p e n s i v e ciphertext: caelpopseemhlanpiossucwtitsbivemuteratsgyaerbtx,北京邮电大学信息安全中心,古典密码学,代换技术与置换技术通常结合使用。 一般地，可先利用代换技术加密，再用置换技术将密文再次加密。,北京邮电大学信息安全中心,对称密码体制,流密码和分组密码 密码设计原则： 混淆原则 所设计的密码应使得密钥和明文以及密文之间的信赖关系相当复杂以至于这种信赖性对密码分析者来说是无法利用。 扩散原则 所设计密码应使得密钥的每一位数字影响密文的多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也影响密文的多位数字以便隐藏明文数字的统计性性。,北京邮电大学信息安全中心,对称密码体制-流密码,流密码主要应用于军事和外交场合。 流密码的优点是错误扩展小、速度快、利于同步、安全程度高。 典型流密码算法：rc4，a5等,密钥流产生器,密钥k,明文m,密文c,异或运算,北京邮电大学信息安全中心,对称密码体制-流密码,伪随机序列发生器是指输入真随机的较短的密钥（种子）通过某种复杂的运算产生大量的伪随机位流。 真随机序列从真实世界的自然随机性源产生。如自然界中的抛币。 伪随机序列用确定的算法产生，不是真正的随机序列。伪随机序列发生器指使用短的真随机序列（称为种子）x扩展成较长的伪随机序列y。 随机数是较短的随机位序列。,北京邮电大学信息安全中心,对称密码体制-分组密码,分组密码的操作模式,电子密码本ecb (electronic codebook mode) 密码分组链接cbc (cipher block chaining) 密码反馈cfb (cipher feedback) 输出反馈ofb (output feedback) 计数器模式ctr 美国nsb在fips pub 74和81中规定 ansi 在ansi x3.106中规定 iso和iso/iec在iso 9732 iso/iec 10116中规定,北京邮电大学信息安全中心,对称密码体制-分组密码,分组密码的操作模式,北京邮电大学信息安全中心,对称密码体制-分组密码,典型分组密码算法,1. des，3des 2. idea 3. rc5 4. rc6 5. aes 其他一些较实用的算法，如blowfish，cast，以及rc2。,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,1973年，美国国家标准局(nbs) 开始征集联邦数据加密标准的方案。 feistel等人研究了一种128位的对称密钥系统， 后ibm改进为56位的密钥系统，并提交nbs。 1975年3月17日，nbs公布了ibm公司提供的密码算法，以标准建议的形式在全国范围内征求意见。 1977年7月15日，nbs接受这个建议，数据加密标准des正式颁布，供商业界和非国防性政府部门使用。,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des利用56比特串长度的密钥k来加密长度为64位的明文，得到长度为64位的密文,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,初始置换和逆置换,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,li-1（32比特）,ri-1（32比特）,li（32比特）,48比特寄存器,扩充/置换运算,48比特寄存器,子密钥ki （48比特）,32比特寄存器,代换/选择运算,置换运算p,ri（32比特）,li=ri-1,des的一轮迭代,f函数,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,f函数： expansion: 32 48（扩充） s-box: 6 4（压缩） permutation:置换,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,32 | 01 02 03 04 | 05 04 | 05 06 07 08 | 09 08 | 09 10 11 12 | 13 12 | 13 14 15 16 | 17 16 | 17 18 19 20 | 21 20 | 21 22 23 24 | 25 24 | 25 26 27 28 | 29 28 | 29 30 31 32 | 01,扩充/置换运算,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,代换/选择运算,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,s-box-i,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,s-box-ii,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,s-box,对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定的列。相应行、列位置的十进制数的4位二进制数表示作为输出。 例如的输入为101001，则行数和列数的二进制表示分别是11和0100，即第3行和第4列，的第3行和第4列的十进制数为3，用4位二进制数表示为0011，所以的输出为0011。,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,置换运算,16 07 20 21 29 12 28 17 01 15 23 26 05 18 31 10 02 08 24 14 32 27 03 09 19 13 30 06 22 11 04 25,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,子密钥的产生,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,置换选择1(pc-1)和置换选择2(pc-2),北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,des示意图-总结,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,des安全性分析,des的安全性完全依赖于密钥，与算法本身没有关系。 主要研究内容： 密钥的互补性； 弱密钥与半弱密钥； 密文-明文相关性； 密文-密钥相关性； s-盒的设计； 密钥搜索。,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,弱密钥,弱密钥：由密钥 k 确定的加密函数与解密函数相同 ，即 。 des的弱密钥： 如果各轮产生的子密钥一样，则加密函数与解密函数相同。 des至少有4个弱密钥 ： 0101010101010101 1f1f1f1f0e0e0e0e e0e0e0e0f1f1f1f1 fefefefefefefefe,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,弱密钥,半弱密钥：对于密钥 k ，存在一个不同的密钥 ，满足 。 des的半弱密钥：子密钥生成过程中只能产生两个不同的子密钥或四个不同的子密钥，互为对合。 des至少有12个半弱密钥。,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,s盒的设计原则,s -盒的设计原理没有公开，一些原则如下： 所有s-盒的每一行是0,1,15的一个置换； 所有s-盒的输出都不是输入的线性函数或仿射函数； s-盒的输入改变任意一位都会引起输出中至少两位发生变化； 对于任何输入x（6位），s(x)与s(x001100)至少有两位不同； 对于任何输入x（6位），s(x)与s(x00ef00)不相等，e, f取0或1； 对于任意一个输入位保持不变而其他五位变化时，输出中0和1的数目几乎相等。,北京邮电大学信息安全中心,对称密码体制-分组密码-des算法,des的一轮迭代,针对des的攻击方法,攻击des的方法主要有： 密钥穷搜索攻击，des算法总的密钥量为 ，1998年使用高级计算机的情况下，破译des只需56小时； 差分攻击； 线性攻击，比差分攻击更有效； 相关密钥攻击等。,北京邮电大学信息安全中心,公钥密码体制,公开密钥算法中用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内），所以加密密钥能够公开，每个人都能用加密密钥加密信息，但只有解密密钥的拥有者才能解密信息。 在公开密钥算法系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做秘密密钥（私有密钥，简称私钥）。 公开密钥算法主要用于加密/解密、数字签名、密钥交换。 典型公钥密码算法：diffie-hellman密钥交换算法、背包算法、rsa算法、elgamal算法、ecc等,北京邮电大学信息安全中心,公钥密码体制,加密与解密由不同的密钥完成 加密: mc: c = ek(m) 解密: cm: m = db(c) = db(ek(m) 两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的) m = db(ek(m) = ek(db(m),北京邮电大学信息安全中心,公钥密码体制-应用场景,传统加密过程,加密和解密使用相同密钥,明文,明文,密文,北京邮电大学信息安全中心,公钥密码体制-应用场景,公钥密码算法,加密和解密使用不同密钥,明文,明文,密文,北京邮电大学信息安全中心,公钥密码体制-应用场景,公钥密码算法,加密和解密使用不同密钥,明文,明文,密文,北京邮电大学信息安全中心,公钥密码体制-应用场景,基于公钥密码算法的认证,北京邮电大学信息安全中心,公钥密码体制-应用场景,公钥密码算法的应用范围,北京邮电大学信息安全中心,公钥密码体制,单向陷门函数,单向陷门函数是满足下列条件的函数f： (1)给定x，计算y=fk(x)是容易的； (2)给定y, 计算x使x=fk-1(y)是不可行的。 (3)存在k，已知k 时,对给定的任何y，若相应的x存在，则计算x使fk-1(y)是容易的。,北京邮电大学信息安全中心,公钥密码体制,公钥密码算法基于的数学难题,背包问题（背包算法） 大整数分解问题（rsa算法） 有限域的乘法群上的离散对数问题 (the discrete logarithm problem, elgamal体制，dh算法,elgamal算法） 椭圆曲线上的离散对数问题（the elliptic curve discrete logarithm problem, 类比的elgamal体制，ecc）,北京邮电大学信息安全中心,公钥密码体制-dh算法,第一个发表的公开密钥算法，1976 用于通信双方安全地协商一个会话密钥 只能用于密钥交换 基于离散对数计算的困难性 主要是模幂运算 ap mod n,北京邮电大学信息安全中心,公钥密码体制-dh算法,离散对数,对数是指数的反函数： b= ai = i= logab ; 模运算如何？ b ai mod p = i = logab mod p ？ 素根（primitive root） a是素数p 的一个素根，如果 a mod p, a2 mod p , , ap-1 mod p 是1到p-1的排列,北京邮电大学信息安全中心,公钥密码体制-dh算法,离散对数,对于任何整数b 和素数p 的一个素根a, 可以找到一个唯一的指数i，使得： b = ai mod p , 其中0i(p-1) i 称为 b 的以a 为底模p的离散对数或指数，记为 ind a,p (b) 对比：对数运算： i = log a （b） mod p inda,p (1)=0, 因为 a0 mod p =1 mod p =1; inda,p (a)=1 因为 a1 mod p =a mod p =a;,北京邮电大学信息安全中心,公钥密码体制-dh算法,离散对数,y = gx mod p 已知 g, x , p 计算y 是容易的， 已知g, y, p , 计算x 是非常困难的,北京邮电大学信息安全中心,公钥密码体制-dh算法,密钥交换过程,全局公开的参数： q 是一个素数， a q , a是q 的一个素根,a 选择一个私有的xa, xa q 计算公开的ya, ya= a xa mod q,b 选择一个私有的xb, xb q 计算公开的yb, yb= a xb mod q,ek(m),北京邮电大学信息安全中心,公钥密码体制-dh算法,密钥交换过程,例： 全局公开参数： q=97, a = 5 ( 5是97 的素根） a选择私钥 xa=36 , b 选择私钥 xb=58 a 计算公钥 b 计算公钥 ya= 5 36 mod 97 = 50 yb= 5 58 mod 97=44 a 与 b 交换公开密钥 a 计算会话密钥 k = ybxa mod q = 4436 mod 97= 75 b 计算会话密钥 k = yaxb mod q = 4436 mod 97= 75,北京邮电大学信息安全中心,公钥密码体制-rsa算法,ron rivest, adi shamir , leonard dleman rsa的安全性基于大数分解的难度 rsa在美国申请了专利（已经过期），在其他国家没有 rsa已经成了事实上的工业标准，在美国除外,北京邮电大学信息安全中心,公钥密码体制-rsa算法,a与b的最大公因数：gcd (a, b) gcd(20, 24)=4 , gcd (15, 16)=1 如果gcd(a, b)=1 ，称a与b 互素 模运算 mod a= q n +r 0rn ; q=a/n ; x 表示小于或等于x的最大整数 a=a/nn + (a mod n) , r = m mod n 如果 (a mod n )= (b mod n) ，则称a 与b 模n同余，记为 a b mod n 例如， 23 8 mod 5 , 8 1 mod 7,数论基础,北京邮电大学信息安全中心,公钥密码体制-rsa算法,数论基础,模运算是可交换的、可结合的、可分配的,(a+b) mod n = (a mod n ) + (b mod n) ) mod n (a-b) mod n = ( (a mod n) (b mod n) ) mod n (ab) mod n = ( (a mod n ) （b mod n) ) mod n (a (b+c) ) mod n = ( a b) mod n + (a c) mod n,幂, 模运算 ma mod n,m2 mod n = (mm) mod n = (m mod n ) 2 mod n m4 mod n = (m2 mod n ) 2 mod n m8 mod n = ( (m2 mod n )2 mod n )2 mod n m25 mod n = (m m8 m16) mod n,北京邮电大学信息安全中心,公钥密码体制-rsa算法,数论基础,欧拉函数(n) n是正整数， (n) 是比n小且与n 互素的正整数的个数 (3)=|1, 2| =2 (4)=|1, 3| =2 (5)=|1, 2, 3, 4 | =4 (6)=|1, 5| =4 (7)=|1, 2, 3, 4, 5, 6| =6 (10)=|1, 3, 7, 9| =4 (11)=|1, 2,3,4,5,6, 7,8, 9,10| =10 如果p是素数，则(p)=(p-1), 比如(2), (5)， (11) 如果p,q 是素数，则(pq)=(p) (q) (p-1)(q-1) 。比如，(10),北京邮电大学信息安全中心,公钥密码体制-rsa算法,数论基础,例如： m=3, n=10; (10)=4 m(n)=34=81 ; 81 mod 10 = 1 即 81 1 mod 10 34+1 = 243 3 mod 10,欧拉定理 若整数m 和n 互素，则,等价形式:,北京邮电大学信息安全中心,公钥密码体制-rsa算法,数论基础,推论：给定两个素数p, q , 两个整数 n, m ，使得n=pq, 0mn ； 则对于任意整数k ，下列关系成立： m k(n)+1 m mod n,北京邮电大学信息安全中心,公钥密码体制-rsa算法,rsa算法流程,密钥产生 1. 取两个大素数 p, q , 保密; 2. 计算n=pq，公开n; 3. 计算欧拉函数(n) =（p-1）(q-1)； 4. 任意取一个与(n) 互素的小整数e, 即 gcd (e, (n) )=1; 1e (n) e作为公钥公开; 5. 寻找d, 使得 de 1 mod (n) , ed =k (n) +1 d 作为私钥保密。,p=7,q=17,n=119,(n)=96,选择e=5,5d=k961,令 k=4, 得到 求得d=77,北京邮电大学信息安全中心,公钥密码体制-rsa算法,rsa算法流程,密钥对（ku, kr）: ku=e, n , kr=d, n 加密过程 把待加密的内容分成k比特的分组，k log2n，并写成数字，设为m,则： c= me mod n 解密过程 m = cd mod n,5,119,77,119,c=m5 mod 119,m=c77 mod 119,北京邮电大学信息安全中心,公钥密码体制-rsa算法,rsa算法证明,证明解密过程是正确的 m cd mod n ( me mod n)d mod n = med mod n 即 med m mod n 根据欧拉定理推论，mk(n)+1 m mod n ed =k(n)+1,北京邮电大学信息安全中心,公钥密码体制-rsa算法,rsa算法举例,p=7,q=17, n=7*17=119 (n)=(7-1)(17-1)=96 选 e=5, gcd (e, (n) = gcd (5, 96)=1; 寻找 d，使得 ed 1 mod 96 , 即 ed= k*96+1, 取 d= 77 公开(e,n)=(5, 119) 将d 保密，丢弃p, q； 加密： m=19 19 5 66 mod 119 , c= 66 解密 6677 mod 119 =?,北京邮电大学信息安全中心,公钥密码体制-rsa算法,rsa算法举例,p=7,q=17, n=7*17=119 (n)=(7-1)(17-1)=96 选 e=5, gcd (e, (n) = gcd (5, 96)=1; 寻找 d，使得 ed 1 mod 96 , 即 ed= k*96+1, 取 d= 77 公开(e,n)=(5, 119) 将d 保密，丢弃p, q； 加密： m=19 19 5 66 mod 119 , c= 66 解密 6677 mod 119 =?,北京邮电大学信息安全中心,公钥密码体制-rsa算法,rsa算法的安全性,攻击方法 蛮力攻击：对所有密钥都进行尝试 数学攻击：等效于对两个素数乘积(n)的因子分解 大数的因子分解是数论中的一个难题,因子分解的进展,北京邮电大学信息安全中心,公钥密码体制-rsa算法,rsa算法的安全性,速度 无论软硬件实现，最快也比des慢100倍,北京邮电大学信息安全中心,公钥密码体制-ecc算法,ecc算法简介,椭圆曲线密码系统 有限域gf(2n) 运算器容易构造 加密速度快 更小的密钥长度实现同等的安全性,北京邮电大学信息安全中心,单向散列函数,hash : 哈希函数，杂凑函数，散列函数 h= h(m) h 具有如下特性： 1）可以操作任何大小的报文m； 2）给定任意长度的m，产生的h的长度固定； 3）给定m 计算h=h(m) 是容易的； 4）给定h, 寻找m，使得h(m)=h是困难的； 5）给定m ，要找到m,m m 且 h(m)=h(m)是计算上不可行的； 6）寻找任何(x,y) ，xy ，使得h(x) =h(y)是计算上不可行的。,北京邮电大学信息安全中心,单向散列函数,简单hash函数-纵向的奇偶校验码,ci= bi1 bi2 bim,+,+,北京邮电大学信息安全中心,单向散列函数-md5算法,ron rivest 设计, rfc 1321 经历过md2, md4 不同的版本 对任意输入均产生128bit的输出 基于32位的简单操作，易于软件实现 简单而紧凑，没有复杂的程序和大数据结构 适合微处理器实现（特别是intel）,北京邮电大学信息安全中心,单向散列函数-md5算法,报文m,10000,长度,y0,y1,yq,yl-1,md5,md5,md5,md5,摘要,128,iv,512,512,512,512,512,512,512,512,cv1,cvq,cvq+1,cvl,寄存器,北京邮电大学信息安全中心,单向散列函数-md5算法,step1: 填充，使报文长度为512的倍数减64 step2: 附加长度，将填充前的报文长度写入最后的64比特，总长度n=l512 step3: 初始化md 缓存，4个32bit的寄存器（a,b,c,d）,共128 bits a= 01 23 45 67 b= 89 ab cd ef c=fe dc ba 98 d=76 54 32 10,北京邮电大学信息安全中心,单向散列函数-md5算法,step 4 : 处理每个报文分组（512 bits）。算法的核心是4轮循环的压缩函数。 使用一个随机矩阵 t i= 232 abs (sin (i) ) i=1,2,64 cv0= iv cvq+1= sum32 ( cvq, rfiyq ,rfhyq , rfg yq ,rffyq ,cvq step 5 : 输出 。 所有l 个 512 bit 的分组处理完之后，第l阶段的输出便是128bit 的报文摘要,北京邮电大学信息安全中心,单向散列函数-md5算法,f,t1,16 , xi,g,t17,32 , xp2i,h,t33,48 , xp3i,i,t49,64 , xp4i,128,+,+,+,+,128,32,512,yq,a,b,c,d,cvq,cvq+1,md5 的压缩函数,北京邮电大学信息安全中心,单向散列函数-md5算法,+ : 模 232加法 xk: 512bit 输入中的第k字节 ti ： t 矩阵中第i 个32 bit,a,b,c,d,a,b,c,d,+,+,+,s,g,xk,ti,+,基本的md5操作（单步）,北京邮电大学信息安全中心,单向散列函数-典型散列算法,sha, sha-1 nist 和nsa共同设计, 用在dss中 基于md4 设计，与md5 非常相似 产生160 位 散列值 ripe-md 欧共体ripe 项目 128 位散列值,北京邮电大学信息安全中心,消息认证码(mac),a,b,mac= h(m),m,mac= h(m),a,b,mac= h(m),mac= h(m),c,m=m mac= h(m),mac,m,mac,m,mac,北京邮电大学信息安全中心,消息认证码(mac),a 和 b 共享一个密钥k a 计算散列值 mac= h( m, k) , 附在m之后发送给b . mac= md5( m+k) mac= desk( md5(m) ) b 收到m 和h (m,k) 之后计算 h(m,k) 并与收到的mac比较,a,b,mac= h(m,k),m,mac= h(m,k),mac,北京邮电大学信息安全中心,数字签名,m,a: (kua kra), kub,hash,b: (kub krb), kra,= ?,h(m),电子形式的“签名” 数字签名可用于鉴权、完整性和不可抵赖性保证,北京邮电大学信息安全中心,密钥分配-对称密钥分配,问题 密钥必须通过保密信道分配 密钥的数量o(n2),北京邮电大学信息安全中心,密钥分配-对称密钥分配,集中式密钥分配中心（kdc） 每个用户和kdc之间共享一个主密钥 （ master key）,通过可靠的信道分配 会话密钥（ session key）协商 a kdc : 请求访问 b kdc a: ka kab, kbkab a b: kbkab ab: kabm,kdc,a,b,ka,kb,北京邮电大学信息安全中心,密钥分配-公开密钥分配,公开密钥 公开宣布 公布到目录服务,a,b,目录服务,a:kpa b: kpb,ekpb(m),ekpa(m),北京邮电大学信息安全中心,密钥分配-中间人攻击,发送方 a,接收方b,给你我的公钥(a,ka),给你我的公钥(a,kh),北京邮电大学信息安全中心,密钥分配-pki,pki是用于发放公开密钥的一种渠道 ca ra directory 大量的查询操作 少量的插入、删除和修改,directory,ca,ra,用户,用户,注册,签发证书、证书回收列表,北京邮电大学信息安全中心,密钥分配-pki,数字证书,公钥证书的主要内容,身份证主要内容,持有者（subject）标识,签发者（issuer）标识,有效期,公钥（n,e）,ca的数字签名,姓名,签发单位,有效期,照片,签发单位盖章、防伪标志,序列号,身份证号码,北京邮电大学信息安全中心,场景分析-为什么需要pki？,bob，我想给你传一个合同，用什么加密技术才能既安全又快速哪？,可以用对称密码算法呀，如des，aes，rc5等，加解密用相同的密钥,如果黑客截获此文件，是否能用同一算法解密此合同。,不可以，加密算法需要用一个对称密钥来解密，黑客不知道此密钥。,北京邮电大学信息安全中心,场景分析-为什么需要pki？,既然黑客不知密钥，那么你怎样才能安全地得到其密钥呢？用电话通知，若电话被窃听，通过internet发此密钥给你，可能被黑客截获，怎么办?,方法是用非对称密钥算法加密对称密钥后进行传送。你用我的公钥加密对称密钥传给我，只有我自己的私钥才能解开。黑客没有，所以无法解密。,既然我可以用你的公钥加密对称密钥，为啥不直接用你的公钥加密该合同哪？这样不就省去了对称算法加密文件的步骤吗？,不可以，因为公钥算法有两个缺点：加密速度慢，因此只可加密小数据；另外加密后导致密文变长。因此一般用对称密钥加密合同，用公钥算法传送对称密钥。,北京邮电大学信息安全中心,场景分析-为什么需要pki？,如果黑客截获到密文，同样也截获到用公钥加密的对称密钥，由于黑客无你的私钥，因此他解不开对称密钥，但如果他用