保密安全与密码技术2密码学课件.ppt

1、保密安全与密码技术第二讲 密码学基础n密码学概论n古典密码学n现代密码学对称密码学非对称密码学单向散列数字签名数字信封密码学基础信信 息息 安安 全全 技技 术术对对 称称 密密 码码 学学非非 对对 称称 密密 码码 学学单单 向向 散散 列列 数数 字字 签签 名名 数数 字字 信信 封封身 份 认 证 访 问 控 制入 侵 检 测防 火 墙防 病 毒安 全 管 理 安 全 审 计系 统 安 全安 全 Email 物 理 安 全网 络 安 全密密 码码 学学 基基 础础黑 客 入 侵 与 防 范操 作 系 统 安 全数 据 库 安 全VPNPKI/PMI安 全 Web电 子 商 务电 子

2、政 务电 子 支 付信信 息息 安安 全全 应应 用用n通信模型n基本概念和术语n密码算法分类n密码发展历史n密码分析n密码技术的用途密码学概论发发送送方方接接收收方方原原始始通通信信信信道道敌敌对对方方原原始始通通信信信信道道并并不不安安全全敌敌对对方方的的目目的的是是：1 1：破破坏坏发发送送方方和和接接收收方方之之间间的的通通信信2 2：获获得得发发送送方方和和接接收收方方之之间间的的通通信信信信息息发发送送方方和和接接受受方方的的目目的的是是：在在不不安安全全的的原原始始信信道道上上安安全全的的传传输输信信息息逻逻辑辑信信道道通信模型n密码学一门研究通信安全和保护信息资源的既古老而又年

3、轻的科学和技术n密码编码学对信息编码以隐蔽信息的一门学问n密码分析学研究分析破译密码的学问n这二者既相互对立又相互促进，共同推动密码学的发展基本概念n明文(plain text)：需要秘密传送的消息，M。n密文(cipher text)：明文经过密码变换后的消息，C。n加密(encrypt,encryption)：由明文到密文的变换。n解密(decrypt,decryption)：从密文恢复出明文的过程。n破译：非法接收者试图从密文分析出明文的过程。n密钥(Key)：加密和解密时使用的一组秘密信息，k。n加密算法(Encrypt Algorithm)：对明文进行加密时采用的一组规则，E(M)。

4、n解密算法(Decrypt Algorithm)：对密文进行解密时采用的一组规则，D(C)。nC=E(M)，M=D(C)，D(E(M)=M基本术语n定义定义:密码体制密码体制是一个五元组（M,C,K,E,D)满足条件：M是可能明文的有限集（明文空间）；C是可能密文的有限集（密文空间）；K是一切可能密钥构成的有限集（密钥空间）；任意 ,有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函数，满足 。EekDdkCPek:PCdk:Pxxxedkk,)(这里Kk基本概念和术语注：1*.Alice要将明文在不安全信道上发给Bob，设X=x1 x2 xn ,其中 ,Alice用加密算法ek

5、作yi=ek(xi)1 i n 结果的密文是 Y=y1y2.yn,在信道上发送，Bob收到后解密：xi=dk(yi)得到明文X=x1 x2 xn.。2*.加密函数ek必须是单射函数，就是一对一的函数。3*.若M=C，则ek为一个置换。4*.好的密钥算法是唯密钥而保密的。5*.若Alice和Bob在一次通信中使用相同的密钥，那么这个加密体制为对称的，否则称为非对称的。Mxi基本概念和术语发发 送送 方方接接 收收 方方通通 信信 信信 道道敌敌 对对 方方明明 文文加加 密密密密 文文明明 文文解解 密密密密 码码 编编 码码 学学密密 码码 分分 析析 学学密密 码码 学学密密 钥钥破破 译译

6、基本概念和术语n古典密码算法和现代密码算法按照算法和密钥是否分开n对称密钥密码和非对称密钥密码加密和解密是否使用相同的密钥n分组密码和序列密码每次操作的数据单元是否分块密码算法的分类古典密码和现代密码n古典密码代替密码（Substitution Cipher）换位密码(transposition Cipher)代替密码与换位密码的组合n古典密码（受限密码）的缺陷密码体制的安全性在于保持算法本身的保密性受限算法的缺陷n不适合大规模生产n不适合较大的或者人员变动较大的组织n用户无法了解算法的安全性n现代密码算法把算法和密钥分开 密码算法可以公开，密钥保密密码系统的安全性在于保持密钥的保密性发送方接

7、收方MM加密E解密DC=Ek(M)M=Ek(C)密码分析密钥分配（秘密信道）kk古典密码和现代密码对称密码算法和非对称密码算法n对称密钥密码算法，又称传统密码算法、秘密密钥密码算法加密和解密使用相同的密钥 Ke=Kd常用算法：DES,IDEA,Blowfish,RC2等n优点加密速度快，便于硬件实现和大规模生产n缺点密钥分配：必须通过保密的信道密钥个数：n（n-1）/2 无法用来签名和抗抵赖（没有第三方公证时）对称密码和非对称密码n非对称密码，又称公开密钥密码算法加密和解密使用不同的密钥（Kp,Ks)，把加密密钥公开，解密密钥保密：c=EKp(m),m=DKs(c)常用算法：RSA,DSA,背

8、包算法，ElGamal,椭圆曲线等n优点：密钥分配：不必保持信道的保密性密钥个数：n 对可以用来签名和抗抵赖n缺点加密速度慢，不便于硬件实现和大规模生产分组密码和序列密码n分组密码（Block Cipher）一次加密或解密操作作用于一个数据块,比如64位n序列密码（Stream Cipher）一次加密或解密操作作用于一位或者一个字节随机序列随机序列密钥序列发生器PiCiCiPiKey密钥序列发生器古古典典密密码码学学对对称称密密码码学学非非对对称称密密码码学学?1 19 94 49 91 19 97 75 5?n早在4000多年以前，古埃及人就在墓志铭中使用过类似于象形文字那样奇妙的符号n公元

9、前约50年，凯撒密码一种简单的字符替换被认为是最早的正式算法n双轨式密码、网格式密码、字典编号密码n传统密码学、现代密码学、量子密码学发展历史密码分析n在未知密钥的前提下，从密文恢复出明文、或者推导出密钥n对密码进行分析的尝试称为攻击n攻击方法分类（根据已知信息量的多少）唯密文攻击已知明文攻击选择明文攻击自适应选择明文攻击选择密文攻击选择密钥攻击n密码算法的安全性如果破译算法的代价大于加密数据本身的价值，或者在信息的生命期内无法破解，那么你的算法可能是安全的。一个算法被称为是计算上安全的，如果一个算法用可得到的资源不能破解。n处理复杂性：计算量，CPU时间n数据复杂性：所需输入数据量n存储复杂

10、性：计算所需的存储空间密码分析密码技术的主要用途n数据保密数据加密/解密数据加密（存储和传输）n认证技术实体身份认证数据源发认证n信息完整性保护数据在传输过程中没有被插入、篡改、重发；n数字签名和抗抵赖（Non-repudiation）源发抗抵赖交付抗抵赖n通信模型n基本概念和术语n密码算法分类n密码发展历史n密码分析n密码技术的用途密码学概论n分组学习现代密码学的各种密码算法n内容：对称密码学：IDEA、SDBI、AES、RC5、CAST-256非对称：DSA、ECC、D-H单向散列：SHA1、RIPE-MDn要求：PPT报告，代表讲解，3-5分钟第一次作业古典密码学n古典密码学的起源n早期

11、的密码：隐写术n代换密码术n置换密码术n古典密码学的优缺点古典密码学的起源战争n古罗马：Caesar 密码 ABCDEFGHIGKLMNOPQRSTUVWXYZDEFGHIGKLMNOPQRSTUVWXYZABCCaesar was a great soldier密码本密文Fdhvdu zdv d juhdw vroglhu明文密文CAESAR 密码：c=(m+3)Mod 26n每一个加密函数ek和每一个解密函数dk都能有效地计算。n破译者取得密文后，将不能在有效的时间内破解出密钥k或明文x。n一个密码体制是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间将是非常大的。古典密码学的起源战争n

12、美国南北战争CANYOUUNDERSTAND输入方向输出方向明文：Can you understand 密文：codtaueanurnynsd 古典密码学的起源战争n转轮密码机ENIGMA，由Arthur Scherbius于1919年发明，4 轮ENIGMA在1944年装备德国海军.古典密码学的起源战争 英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。古典密码学的起源战争一个简单的加密算法异或110101011000110011xxxxxxxx一个简单的加密算法异或 密文：0 1 1 0 解密：密钥：0 1 0 1 明

13、文：0 0 1 1n已知明文、密文，怎样求得密钥？C=P KP=C K异或运算（不带进位加法）：明文:0 0 1 1 加密：密钥:0 1 0 1 密文：0 1 1 0K=C Pn只知道密文，如何求得密文和密钥？n定义：将秘密信息隐藏在其余信息中n举例隐型墨水字符格式转换图像隐藏n信息隐藏古典密码学隐写术n字母对数字A B C D E F G H I J K L M N O P0 1 2 3 4 5 6 7 8 910 11 12 13 14 15Q R S T U V W X Y Z16 17 18 19 20 21 22 23 24 25n破解：8 11 14 21 4 24 14 20代换

14、密码n移位密码（Shift Cipher）ABCDEFGHI J KL MNO PQRS T U V WXYZDEFGHI J KLMNOP QR STUV WX Y Z ABCn破解：FDHVDUZDVDJUHDWVROGLHUn移位密码：令P=C=Z26,0K26，对于任意的x,y在Z26内，有：Ek(x)=(x+K)mod26,以及Dk(y)=(y-K)mod26。称K是该加密方法的密钥。代换密码yx,n例：例：假设移位密码的密钥为K=11，明文为We will meet at midnight.n首先将明文中的字母对应于其相应的整数，得到如下数字串：22 4 22 8 11 11 12

15、 4 4 19 0 19 12 8 3 13 8 6 7 19n然后将每一数都与11相加，再对其和取模26运算，可得：15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4n最后，再将其转换为相应的字母串，即得密文：HPHTWWXPPELEXTOYTRSE.n要对密文进行解密，只需执行相应的逆过程即可，Bob首先将密文转换为数字，再用每个数字减去11后取模26运算，最后将相应的数字再转换为字母可得明文。移位密码n例例 设有如下密文串JBCRCLQRWCRVNBJENBWRWN.依次试验所有可能的解密密钥，可得如下不同字母串：iabqbkpqvb

16、qumaidmavqvmhzapajopuaptlzhclzupulgyzozinotzoskygbkytotkfxynyhmnsynrjxfajxsnsjewxmxglmrxmqiweziwrmridvwlwfklqwlphvdyhvqlqhcuvkvejkpvkogucxgupkpgbtujudijoujnftbwftojofastitchintimesavesninen至此，已得出有意义的明文，相应的密钥K=9。平均来看，使用上述方法计算明文只需试验26/213次即可。n上面的例子表明，一个密码体制安全的必要条件是能抵抗穷尽密钥搜索攻击，普通的做法是密钥空间必须足够大。但是，很大的密钥空

17、间并不是保证密码体制安全的充分条件。移位密码a b cd ef g h i j k l mnopq r s t u vwxyzXNYAHPOGZQWBTSFLRCVMUEKJDIn请解密：请解密：MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHAn代换密码的一个密钥刚好对应于26个英文字母的一种代换。所有可能的置换有26！种，这个数值超过4*1026次方，是一个很大的数。n因此，采用穷尽密钥搜索的攻击方法，即使使用计算机，也是计算上不可行的。但是，后面我们将看到，采用别的密码分析方法，代换密码可以很容易地被攻破。代换密码yx,代换密码分析n元音字母用得较多，其中e、i较多；辅音中r

18、、t使用较多n字母组合ere，er等n试分析下列密文：nBMZALXLBYJBVALXZLRZBJHGKLJXSVZBZnB5 Z4 A2 L5 X3 J3 V2nBMZALXLBYJBVALXZLRZBJHGKLJXSVZBZnIf there is cipher text I can decrypt itn密码表：nABCDEFG H IJKLMN OPQ RST UVWXYZnH IJ KLMN ABCDEFG UVWXYZ OPQRST代换密码分析n对明文的所有字母都用一个固定的明文字母表到密文字母表的映射n单表代换密码不能非常有效地抵抗密码攻击，因为语言的特征仍能从密文中提取出来移位

19、密码、替换密码、仿射密码n多表代换密码以一系列（两个以上）代换表依次对明文消息的字母进行代换的加密方法若待换序列是非周期的无限序列，则相应的密码称为非周期多表代换密码。这类密码，对每个明文字母都采用不同的代换表（或密钥）进行加密，称作一次一密密码（One-time pad cipher）,这是一种理论上唯一不可破的密码Vigenre、轮转机（Rotor machine）等代换密码n保持明文字符未改变，但通过重排而更改他们位置，所以有时也称为换位密码。n栅栏式密码美国南北战争时期（1861-1865年），军队中曾经使用过的“栅栏”式密码（rail fence cipher)。原理明文：send

20、help加密过程：s n h le d e p密文：s n h l e d e p置换密码n矩阵置换n换位密码把明文按列写入，按行读出n密钥包含3方面信息：行宽，列高，读出顺序nkey:5353142nciphertext:SARATACETHNKITE nplaintext:SARAT TRSAA ACETH HEATC NK I TE E INTKnThere is an attack置换密码古典密码学n已经成为历史，但被传统密码学所借鉴已经成为历史，但被传统密码学所借鉴n加解密都很简单，易被攻破加解密都很简单，易被攻破n采用手动或机械的方式加解密，不适合大采用手动或机械的方式加解密，不适

21、合大规模的数据传输。规模的数据传输。n属于对称密钥学属于对称密钥学n对称密码学n非对称密码学n单向散列n数字签名n数字信封现代密码学n原理加密和解密使用同一个密钥信息的发送方和接收方必须共享一个密钥n示意图对称密码学用户A用户B明文加密密文解密明文n主要算法DES、3DES、IDEA、SDBI、AES、RC5、CAST-256n优缺点简单、速度快能力有限、密钥交换困难n实例DES对称密码学DES加密算法的背景l发明人：美国IBM公司W.Tuchman 和 C.Meyer 1971-1972年研制成功。l产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计

22、算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。l标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（Data Encryption Standard），于1977年7月15日生效。DES算法原理nDES是一种对称密钥算法，密钥长度为是一种对称密钥算法，密钥长度为56bits(加加上奇偶校验，通常写成上奇偶校验，通常写成64bits)n是一种分组加密算法，是一种分组加密算法，64 bits为一个分组为一个分组n基本思想：基本思想：置乱（置乱（Confusion）和扩散（和扩散（Diffusion）n使用标准的算术和逻辑运算使用

23、标准的算术和逻辑运算 DES加密过程 首先把明文分成以64 bit为单位的块m，对于每个m,执行如下操作 DES(m)=IP-1 T16 T15.T2 T1 IP(m)初始置换，IP 16轮迭代，Ti,i=1,2,16末置换，IP-1数据加密标准DES数据加密标准DES初始换位（IP）n初始换位（IP）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157M=m1m2,m62m63,m64M=m58m50,m23

24、m15,m7IP(M)一轮迭代Li-1Ri-1LiRi-1Ri=Li-1 f(Ri-1,Ki)Ki(48bits)32 bits32 bits32 bitsE-盒置换 S-盒代替P-盒置换32 bitsf4832扩展置换(E-盒置换)n将Ri从32位扩展到48位n目的：输入的一位影响下一步的两个替换，使得输出对输入的依赖性传播得更快，密文的每一位都依赖于明文的每一位1 2 3 45 6 7 81 2 3 4 5 6 7 8324832 1 2 3 4 5 4 5 6 7 8 9 8 9.31 32 11 2 3 4 5 6 7 8 9 10 11 12 13 14 46 47 48S盒置换n将

25、48比特压缩成32比特ES1S2S3S4S5S6Ri-1 (32 bits)Ki(48bits)48 bitsS7S8S盒置换n输入6比特:b1b2b3b4b5b6n输出4比特：S(b1b6,b2b3b4b5)S1b1 b2 b3 b4 b5 b60123456789101112131415S101441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S2015181461134972131205101.23举例：S 1(100110)=1000P-盒置换n32比特输入

26、，32比特输出123456789303132167202129122817115.11425P-盒的输出：子密钥的生成PC-1C0D0LS1LS1C1D1LS2LS2C2D2LS16LS16C16D16PC-2K1(48bits)密钥 K,64 bits2828PC-2K2(48bits)PC-2K16(48bits)子密钥生成CiDi移位(LS)移位压缩置换(PC)Ci+1Di+1Ki子密钥生成n拆分：56 bits 的密钥分成两部分，Ci,Di ，各28bitsn循环左移：根据迭代的轮数，分别左移一位或两位12345678910 11 12 13 14 15 161122222212222

27、221n压缩置换（置换选择）：从56bits中选择48bits 1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932末置换n末置换40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725585042342618102605244362820124625446383022146645648403

28、22416857494133251791595143352719113615345372921135635547393123157n初始置换IP-1(IP(M)=MDES解密过程nDES解密过程与加密过程完全相似，只不过将16次迭代的子密钥顺序倒过来，即 m=DES-1(c)=IP-1 T16T15.T2 T1 IP(c)n可以证明，DES(DES-1(m)=mDES的算法模式n电子密码本（Electronic Code Book,ECB）n密码分组链（Cipher Block Chaining,CBC）n密文反馈（Cipher Feed Back,CFB）n输出反馈（Output Feed

29、Back,OFB）电子密码本模式（ECB）n基本的DES算法就是ECB 模式n相同的输入永远产生相同的输出n相当于加密、解密双方各有一个密码本，对于一个密钥，密码本有264个表项n存在重放（Replay）类型的攻击，特别是对于结构化的报文：攻击者可以在不知道密钥的情况下修改被加密过的消息12345678910111213时间标记发送银行接受银行储户姓名帐号存款金额密码分组链模式（CBC）)()(111iiiiiiCECPPCECEkEkPi-1PiEkPi+1EkCi-1EkCi-1EkCi-1Ci-1CiCi+1Pi-1PiPi+1IViiiiiiiiiiPPCCPPCPCEECE11111

30、1)()(DES的安全性和速度n弱密钥产生的子密钥相同，4个，如 000000,11111111,010101010101，10101010n半弱密钥用不同的密钥加密产生相同的密文，即用一个密钥加密的信息可以用其他密钥解开，12个n密钥的长度1976年，耗资2000万美元的计算机，可以在一天中找到密钥。1993年，设计100万美元的计算机，3.5小时用穷举法找到密钥。DES的变形n三重DES加密，密钥长度为112比特,k=k1k2DESDES-1DESDES-1DESDES-1mmcck1k2k1k1k2k1密钥长度2112软硬件实现的速度n硬件实现：商业DES芯片VLSI 公司 VM009

31、1993年制造 200M Bytes/sn软件实现：80486，CPU 66Hz,每秒加密43000个DES分组，336K Bytes/sHP 9000/887 ,CPU 125 Hz,每秒加密196,000个分组，1.53M Bytes/s DES算法的公开性与脆弱性nDES的两个主要弱点：密钥容量：56位不太可能提供足够的安全性S盒：可能隐含有陷井（Hidden trapdoors）nDES的半公开性：S盒的设计原理至今未公布n报告表明S盒在次序上、内容上是最优的。DES算法存在的问题与挑战n强力攻击：255次尝试n差分密码分析法：247次尝试n线性密码分析法：243次尝试对DES攻击结果

32、及其启示n1997年1月28日美国RSA数据安全公司悬赏“秘密密钥挑战”竞赛48位的RC5 313小时/3500台计算机1997年3月13日Rocke Verser设计一个攻击程序（DESCHALL），参加的志愿者有78516个，第96天（6月17日晚10：39）Michael Sanders破译成功，获1万美圆奖金。搜索量为24.6%。密钥长度(bit)穷举时间4078秒485 小时5659天6441年7210，696年802，738，199年88700，978，948年96179，450，610，898年11211，760，475，235，863，837年128770，734，505，05

33、7，572，442，069年DES CHALL搜索速度估算其他密码算法算法密钥长度 迭代次数数学操作应用DES5616XOR,S-BoxSET3DES112 or 168 48XOR,S-BoxPGP,S/MIMEIDEA1288XOR,PGPBlowFish最大44816XOR,S-Box,RC5最大2048255+,-，XORCAST-1284012816+,-，S-BoxPGPn主要算法DES、3DES、IDEA、SDBI、AES、RC5、CAST-256n优缺点简单、速度快能力有限、密钥交换困难n实例DES对称密码学n原理加密和解密使用不同的密钥一对密钥：公钥与私钥n示意图用户A用户B

34、明文加密密文用户B的加密公钥用户B的解密私钥解密明文非对称密码学n主要算法RSA、DSA、EIGamal、ECC、D-Hn优缺点复杂、速度慢密钥交换简单、可用于身份鉴别n实例RSA非对称密码学RSA算法简介nRon Rivest,Adi Shamir,Leonard AdlemannRSA的安全性基于大数分解的难度nRSA在美国申请了专利（已经过期），在其他国家没有nRSA已经成了事实上的工业标准，在美国除外数论基础na与b的最大公因数：gcd(a,b)gcd(20,24)=4,gcd(15,16)=1n如果gcd(a,b)=1，称a与b 互素n模运算 moda=q n+r 0rn;q=a/n

35、;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数论基础n模运算是可交换的、可结合的、可分配的(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 nn幂,模运算 ma mod n m2 mo

36、d 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 数论基础n欧拉函数(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)，(

37、11)如果p,q 是素数，则(pq)=(p)(q)(p-1)(q-1)。比如，(10)数论基础例如：m=3,n=10;(10)=4 m(n)=34=81 81 mod 10=1 即：m(n)=34=81 1 mod 10 m(n)+1=34+1=243 3 mod 10 nmn mod 1)(nmmn mod 1)(欧拉定理：欧拉定理：若整数若整数m 和和n 互素，则互素，则等价形式等价形式数论基础n推论：给定两个素数p,q,两个整数 n,m，使得n=pq,0mn；则对于任意整数k，下列关系成立：m k(n)+1 m mod nRSA算法操作过程n密钥产生1.取两个大素数 p,q,保密;2.计

38、算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=17n=119(n)=96选择e=55d=k961令 k=4,得到求得d=77RSA算法加密/解密过程n密钥对（KU,KR）:KU=e,n,KR=d,nn加密过程把待加密的内容分成k比特的分组，k log2n，并写成数字，设为M,则：C=Me mod nn解密过程 M=Cd mod n 5,11977,119c=m5 mod 119m=c77

39、mod 119RSA加密过程举例1.p=7,q=17,n=7*17=1192.(n)=(7-1)(17-1)=963.选 e=5,gcd(e,(n)=gcd(5,96)=1;4.寻找 d，使得 ed 1 mod 96,即 ed=k*96+1,取 d=77 5.公开(e,n)=(79,119)6.将d 保密，丢弃p,q；7.加密：m=19 19 5 66 mod 119,c=66 解密：6677 mod 119 =19 RSA 算法的安全性n攻击方法蛮力攻击：对所有密钥都进行尝试数学攻击：等效于对两个素数乘积(n)的因子分解n大数的因子分解是数论中的一个难题十进制数字位数近似比特数得到的数据MI

40、PS年10033219917110365199275120398199383012942819945000因子分解的进展RSA 算法的性能n速度软件实现比DES 慢100倍硬件实现比DES慢1000倍512位768位1024位加密0.030.050.08解密0.160.480.93签名0.160.520.97验证0.020.070.08Diffie Hellman密钥交换算法n第一个发表的公开密钥算法，1976n用于通信双方安全地协商一个会话密钥n只能用于密钥交换n基于离散对数计算的困难性n主要是模幂运算 a p mod n 其他公钥密码算法nDSA1991年,NIST 提出了 数字签名算法（

41、DSA）,并把它用户数字签名标准（DSS）只能用于数字签名算法的安全性也是基于离散对数的难度招致大量的反对，理由如下：nDSA 不能用于加密或密钥分配nDSA是由 NSA研制的，可能有后门nDSA的选择过程不公开，提供的分析时间不充分nDSA比RSA慢（1040倍）n密钥长度太小（512位）nDSA可能侵犯其他专利nRSA是事实上的标准其他公钥密码算法n椭圆曲线密码系统有限域GF(2n)运算器容易构造加密速度快更小的密钥长度实现同等的安全性n主要算法RSA、DSA、EIGamal、ECC、D-Hn优缺点复杂、速度慢密钥交换简单、可用于身份鉴别n实例RSA非对称密码学n原理：对要传输的数据作运算

42、生成信息摘要，产生信息的数字“指纹”。n主要算法：MD2、MD5、SHA1、RIPE-MDn目的确保数据没有被修改或变化保证信息的完整性不被破坏n特点输入信息长度任意，输出信息长度固定给定输入信息，计算输出容易不可预见、完全不可逆单向散列单向散列nHash:哈希函数，杂凑函数，散列函数h=H(m)nH 具有如下特性：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)是计

43、算上不可行的。简单的散列函数n纵向的奇偶校验码比特1比特2比特n分组1b11b21bn1分组2b21b22bn2.分组mb1mb2mbnm散列码C1C2CnCi=bi1 bi2 bim+MD5算法简介nRon Rivest 设计,RFC 1321n经历过MD2,MD4 不同的版本n对任意输入均产生128bit的输出n基于32位的简单操作，易于软件实现n简单而紧凑，没有复杂的程序和大数据结构n适合微处理器实现（特别是Intel）MD5 产生报文摘要的过程报文m1000.0长度Y0Y1YqYL-1MD5MD5MD5MD5摘要128IV512512512512512512512512cv1cvqCv

44、q+1CvL寄存器MD5 产生报文摘要的过程nStep1:填充，使报文长度为512的倍数减64nStep2:附加长度，将填充前的报文长度写入最后的64比特，总长度N=L512nStep3:初始化MD 缓存，4个32bit的寄存器（A,B,C,D）,共128 bitsA=01 23 45 67 B=89 AB CD EFC=FE DC BA 98D=76 54 32 10MD5 产生报文摘要的过程nStep 4:处理每个报文分组（512 bits）。算法的核心是4轮循环的压缩函数。使用一个随机矩阵 T i=232 abs(sin(i)，i=1,2,.64CV0=IVCVq+1=SUM32(CVq

45、,RFIYq,RFHYq,RFG Yq,RFFYq,CVq nStep5：所有L 个 512 bit 的分组处理完之后，第L阶段的输出便是128bit 的报文摘要。其他散列算法nSHA,SHA-1NIST 和NSA共同设计,用在DSS中基于MD4 设计，与MD5 非常相似产生160 位 散列值nRIPE-MD欧共体RIPE 项目128 位散列值n原理信息的发件人将他们的身份与信息绑定在一起n特征不可伪造、不可复制、不可更改、不可抵赖n主要算法RSA、DSA、GOST数字签名消消 息息摘要摘要数字签名数字签名消消 息息数字签名数字签名消消 息息摘要摘要数字签名数字签名摘要摘要发送方发送方接收方接

46、收方数字签名n原理对称密钥用于明文的加解密非对称密钥用于加解密对称密钥n特征结合对称加密技术和公开密钥技术的优点，它克服了秘密密钥加密中秘密 密钥分发困难和公开密钥加密中加密时间长的问题 数字信封用户A用户B明文对称密钥加密密文加密用户B的加密公钥密文解密用户B的解密私钥对称密钥解密明文数字信封A用户B用户明文Hash加密用户A的私有签名密钥明文十十加密对称密钥密文用户B公开密钥数字信封数字签名数字签名加密密文数字信封密文数字信封十解密对称密钥对称密钥解密明文十十数字签名数字签名解密Hash信息摘要信息摘要信息摘要比较用户A数字证书用户A数字证书用户 B数字证书用户B私有密钥现在密码学的应用模

47、式对公钥密码算法的误解n公开密钥算法比对称密钥密码算法更安全？任何一种算法都依赖于密钥长度、破译密码的工作量，从抗分析角度，没有一方更优越n公开密钥算法使对称密钥成为过时了的技术？公开密钥很慢，只能用在密钥管理和数字签名，对称密钥密码算法将长期存在n使用公开密钥加密，密钥分配变得非常简单？事实上的密钥分配既不简单，也不有效对称密钥分配n问题密钥必须通过保密信道分配密钥的数量O(n2)对称密钥分配n集中式密钥分配中心（KDC）每个用户和KDC之间共享一个主密钥（master key）,通过可靠的信道分配会话密钥（session key）协商 A KDC:请求访问 B KDC A:Ka Kab,KbKab A B:KbKab AB:KabmKDCABKaKbKab公开密钥的密钥分配n公开密钥公开宣布公布到目录服务AB目录服务目录服务A:KPaB:KPbEKPb(M)EKPa(M)小结n基本操作：代替、换位、异或n密码学基本模型n算法的分类n常用的对称密码nDES算法的基本原理nRSA算法nMD5 算法概要