保密安全与密码技术2009-2密码学

1、保密安全与密码技术,第二讲 密码学基础,密码学概论 古典密码学 现代密码学 对称密码学 非对称密码学 单向散列 数字签名 数字信封,密码学基础,通信模型 基本概念和术语 密码算法分类 密码发展历史 密码分析 密码技术的用途,密码学概论,通信模型,密码学 一门研究通信安全和保护信息资源的既古老而又年轻的科学和技术 密码编码学 对信息编码以隐蔽信息的一门学问 密码分析学 研究分析破译密码的学问 这二者既相互对立又相互促进，共同推动密码学的发展,基本概念,明文(plain text)：需要秘密传送的消息，m。 密文(cipher text)：明文经过密码变换后的消息，c。 加密(encrypt, e

2、ncryption)：由明文到密文的变换。 解密(decrypt, decryption)：从密文恢复出明文的过程。 破译：非法接收者试图从密文分析出明文的过程。 密钥(key)：加密和解密时使用的一组秘密信息，k。 加密算法(encrypt algorithm)：对明文进行加密时采用的一组规则，e(m)。 解密算法(decrypt algorithm)：对密文进行解密时采用的一组规则，d(c)。 c=e(m)， m=d(c)，d(e(m)= m,基本术语,定义: 密码体制是一个五元组（m,c,k,e,d)满足条件： m是可能明文的有限集（明文空间） ； c是可能密文的有限集（密文空间） ；

3、k是一切可能密钥构成的有限集（密钥空间） ； 任意 ,有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函数，满足 。,基本概念和术语,注：1*.alice要将明文在不安全信道上发给bob， 设x=x1 x2 xn , 其中 , alice用加密算法ek 作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在一次通信中使用相同

4、的密钥，那么这个加密体制为对称的，否则称为非对称的。,基本概念和术语,基本概念和术语,古典密码算法和现代密码算法 按照算法和密钥是否分开 对称密钥密码和非对称密钥密码 加密和解密是否使用相同的密钥 分组密码和序列密码 每次操作的数据单元是否分块,密码算法的分类,古典密码和现代密码,古典密码 代替密码（substitution cipher） 换位密码 (transposition cipher) 代替密码与换位密码的组合 古典密码（受限密码）的缺陷 密码体制的安全性在于保持算法本身的保密性 受限算法的缺陷 不适合大规模生产 不适合较大的或者人员变动较大的组织 用户无法了解算法的安全性,现代密码

5、算法 把算法和密钥分开 密码算法可以公开，密钥保密 密码系统的安全性在于保持密钥的保密性,发送方,接收方,m,m,加密 e,解密 d,c = ek (m),m= ek (c),密码分析,密钥分配（秘密信道）,k,k,古典密码和现代密码,对称密码算法和非对称密码算法,对称密钥密码算法，又称传统密码算法、秘密密钥密码算法 加密和解密使用相同的密钥 ke =kd 常用算法：des, idea, blowfish, rc2等 优点 加密速度快，便于硬件实现和大规模生产 缺点 密钥分配：必须通过保密的信道 密钥个数：n（n-1）/2 无法用来签名和抗抵赖（没有第三方公证时）,对称密码和非对称密码,非对称

6、密码，又称公开密钥密码算法 加密和解密使用不同的密钥（kp, ks)，把加密密钥公开，解密密钥保密： c= ekp(m) , m=dks (c) 常用算法：rsa, dsa, 背包算法，elgamal , 椭圆曲线等 优点： 密钥分配：不必保持信道的保密性 密钥个数：n 对 可以用来签名和抗抵赖 缺点 加密速度慢，不便于硬件实现和大规模生产,分组密码和序列密码,分组密码（block cipher） 一次加密或解密操作作用于一个数据块,比如64位 序列密码（stream cipher） 一次加密或解密操作作用于一位或者一个字节,早在4000多年以前，古埃及人就在墓志铭中使用过类似于象形文字那样奇

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

8、据复杂性：所需输入数据量 存储复杂性：计算所需的存储空间,密码分析,密码技术的主要用途,数据保密数据加密/解密 数据加密（存储和传输） 认证技术 实体身份认证 数据源发认证 信息完整性保护 数据在传输过程中没有被插入、篡改、重发； 数字签名和抗抵赖（non-repudiation ） 源发抗抵赖 交付抗抵赖,通信模型 基本概念和术语 密码算法分类 密码发展历史 密码分析 密码技术的用途,密码学概论,分组学习现代密码学的各种密码算法 内容： 对称密码学：idea、sdbi、aes、rc5、cast-256 非对称：dsa、ecc、d-h 单向散列：sha1、ripe-md 要求：ppt报告，代表

9、讲解，3-5分钟,第一次作业,古典密码学,古典密码学的起源 早期的密码：隐写术 代换密码术 置换密码术 古典密码学的优缺点,古典密码学的起源战争,古罗马：caesar 密码,abcdefghigklmnopqrstuvwxyz,defghigklmnopqrstuvwxyzabc,caesar was a great soldier,密码本,密文,fdhvdu zdv d juhdw vroglhu,明文,密文,caesar 密码 ： c=( m+ 3) mod 26,每一个加密函数ek和每一个解密函数dk都能有效地计算。 破译者取得密文后，将不能在有效的时间内破解出密钥k或明文x。 一个密码

10、体制是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间将是非常大的。,古典密码学的起源战争,美国南北战争,输入方向,输出方向,明文： can you understand 密文： codtaueanurnynsd,古典密码学的起源战争,转轮密码机enigma，由arthur scherbius于1919年发明，4 轮enigma在1944年装备德国海军.,古典密码学的起源战争,英国的typex打字密码机，是德国3轮enigma的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。,古典密码学的起源战争,一个简单的加密算法异或,一个简单的加密算法异或,已知明文、密文，怎样求得

11、密钥？,只知道密文，如何求得密文和密钥？,定义：将秘密信息隐藏在其余信息中 举例 隐型墨水 字符格式转换 图像隐藏 信息隐藏,古典密码学隐写术,字母对数字 a b c d e f g h i j k l m n o p 0 1 2 3 4 5 6 7 8 910 11 12 13 14 15 q r s t u v w x y z 16 17 18 19 20 21 22 23 24 25 破解：8 11 14 21 4 24 14 20,代换密码,移位密码（shift cipher） abcdefghi j kl mno pqrs t u v wxyz defghi j klmnop qr

12、stuv wx y z abc 破解：fdhvduzdvdjuhdwvroglhu 移位密码：令p=c=z26 , 0k26，对于任意的x,y在z26内，有： ek(x)=(x+k)mod26, 以及 dk(y)=(y-k) mod26。 称k是该加密方法的密钥。,代换密码,例：假设移位密码的密钥为k=11，明文为 we will meet at midnight. 首先将明文中的字母对应于其相应的整数，得到如下数字串： 22 4 22 8 11 11 12 4 4 190 19 12 8 3 13 8 6 7 19 然后将每一数都与11相加，再对其和取模26运算，可得： 15 7 19 22

13、 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 最后，再将其转换为相应的字母串，即得密文： hphtwwxppelextoytrse. 要对密文进行解密，只需执行相应的逆过程即可，bob首先将密文转换为数字，再用每个数字减去11后取模26运算，最后将相应的数字再转换为字母可得明文。,移位密码,例 设有如下密文串jbcrclqrwcrvnbjenbwrwn. 依次试验所有可能的解密密钥，可得如下不同字母串： iabqbkpqvbqumaidmavqvm hzapajopuaptlzhclzupul gyzozinotzoskygbkytotk fxynyhm

14、nsynrjxfajxsnsj ewxmxglmrxmqiweziwrmri dvwlwfklqwlphvdyhvqlqh cuvkvejkpvkogucxgupkpg btujudijoujnftbwftojof astitchintimesavesnine 至此，已得出有意义的明文，相应的密钥k=9。平均来看，使用上述方法计算明文只需试验26/213次即可。 上面的例子表明，一个密码体制安全的必要条件是能抵抗穷尽密钥搜索攻击，普通的做法是密钥空间必须足够大。但是，很大的密钥空间并不是保证密码体制安全的充分条件。,移位密码,a b cd ef g h i j k l mnopq r s t

15、u vwxyz xnyahpogzqwbtsflrcvmuekjdi 请解密：mgzvyzlghcmhjmyxs sfmnhahycdlmha 代换密码的一个密钥刚好对应于26个英文字母的一种代换。所有可能的置换有26！种，这个数值超过4*1026次方，是一个很大的数。 因此，采用穷尽密钥搜索的攻击方法，即使使用计算机，也是计算上不可行的。但是，后面我们将看到，采用别的密码分析方法，代换密码可以很容易地被攻破。,代换密码,代换密码分析,元音字母用得较多，其中e、i较多；辅音中r、t使用较多 字母组合ere，er等 试分析下列密文： bmzalxlbyjbvalxzlrzbjhgkljxsvzb

16、z b5 z4 a2 l5 x3 j3 v2 bmzalxlbyjbvalxzlrzbjhgkljxsvzbz if there is cipher text i can decrypt it 密码表： abcdefg h ijklmn opq rst uvwxyz h ij klmn abcdefg uvwxyz opqrst,代换密码分析,对明文的所有字母都用一个固定的明文字母表到密文字母表的映射 单表代换密码 不能非常有效地抵抗密码攻击，因为语言的特征仍能从密文中提取出来 移位密码、替换密码、仿射密码 多表代换密码 以一系列（两个以上）代换表依次对明文消息的字母进行代换的加密方法 若待换

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

18、码,矩阵置换 换位密码把明文按列写入，按行读出 密钥包含3方面信息：行宽，列高，读出顺序 key: 5353142 ciphertext: saratacethnkite plaintext: sarat trsaa aceth heatc nk i te e intk there is an attack,置换密码,古典密码学,已经成为历史，但被传统密码学所借鉴 加解密都很简单，易被攻破 采用手动或机械的方式加解密，不适合大规模的数据传输。 属于对称密钥学,对称密码学 非对称密码学 单向散列 数字签名 数字信封,现代密码学,原理 加密和解密使用同一个密钥 信息的发送方和接收方必须共享一个密钥

19、 示意图,对称密码学,主要算法 des、3des、idea、sdbi、aes、rc5、cast-256 优缺点 简单、速度快 能力有限、密钥交换困难 实例 des,对称密码学,des加密算法的背景,发明人：美国ibm公司w. tuchman 和 c. meyer 1971-1972年研制成功。 产生：美国国家标准局（nbs)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了ibm的lucifer方案。 标准化：des算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（data encryption stand

20、ard），于1977年7月15日生效。,des算法原理,des是一种对称密钥算法，密钥长度为56bits (加上奇偶校验，通常写成64bits) 是一种分组加密算法，64 bits为一个分组 基本思想： 置乱（confusion） 和扩散（diffusion ） 使用标准的算术和逻辑运算,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）,初始换位（ip）,m=

21、m1m2,m62m63,m64,m=m58m50,m23m15,m7,ip(m),一轮迭代,li-1,ri-1,liri-1,ri=li-1 f (ri-1 ,ki ),ki ( 48bits),32 bits,32 bits,32 bits,e-盒置换,s-盒代替,p-盒置换,32 bits,f,48,32,扩展置换(e-盒置换),将ri从32位扩展到48位 目的：输入的一位影响下一步的两个替换，使得输出对输入的依赖性传播得更快，密文的每一位都依赖于明文的每一位,1 2 3 4,5 6 7 8,1 2 3 4,5 6 7 8,32,48,32 1 2 3 4 5 4 5 6 7 8 9 8

22、9. 31 32 1,1 2 3 4 5 6 7 8 9 10 11 12 13 14 46 47 48,s盒置换,将48比特压缩成32比特,e,s1,s2,s3,s4,s5,s6,ri-1 (32 bits),ki ( 48bits),48 bits,s7,s8,s盒置换,输入6比特: b1b2b3b4b5b6 输出4比特：s(b1b6 , b2b3b4b5),s1,b1 b2 b3 b4 b5 b6,举例： s 1( 100110 ) = 1000,p-盒置换,32比特输入，32比特输出,p-盒的输出：,子密钥的生成,pc-1,c0,d0,ls1,ls1,c1,d1,ls2,ls2,c2,

23、d2,ls16,ls16,c16,d16,pc-2,k1(48bits),密钥 k, 64 bits,28,28,pc-2,k2(48bits),pc-2,k16(48bits),子密钥生成,ci,di,移位(ls),移位,压缩置换(pc),ci+1,di+1,ki,子密钥生成,拆分：56 bits 的密钥分成两部分，ci , di ， 各28bits 循环左移：根据迭代的轮数，分别左移一位或两位,压缩置换（置换选择）：从56bits中选择48bits,末置换,末置换,初始置换,ip-1(ip(m)=m,des解密过程,des解密过程与加密过程完全相似，只不过将16次迭代的子密钥顺序倒过来，即

24、 m = des-1(c) = ip-1 t16t15.t2 t1 ip(c) 可以证明， des(des-1(m) )=m,des的算法模式,电子密码本（electronic code book, ecb） 密码分组链（cipher block chaining, cbc） 密文反馈（ cipher feed back, cfb） 输出反馈（output feed back, ofb ）,电子密码本模式（ecb）,基本的des算法就是ecb 模式 相同的输入永远产生相同的输出 相当于加密、解密双方各有一个密码本，对于一个密钥，密码本有264个表项 存在重放（replay）类型的攻击，特别是对

25、于结构化的报文： 攻击者可以在不知道密钥的情况下修改被加密过的消息,密码分组链模式（cbc）,ek,ek,pi-1,pi,ek,pi+1,ek,ci-1,ek,ci-1,ek,ci-1,ci-1,ci,ci+1,pi-1,pi,pi+1,iv,des的安全性和速度,弱密钥 产生的子密钥相同，4个 ， 如 000000, 11111111, 010101010101， 10101010 半弱密钥 用不同的密钥加密产生相同的密文，即用一个密钥加密的信息可以用其他密钥解开，12个 密钥的长度 1976年，耗资2000万美元的计算机，可以在一天中找到密钥。 1993年，设计100万美元的计算机，3.5

26、小时用穷举法找到密钥。,des的变形,三重des加密，密钥长度为112比特, k=k1k2,des,des-1,des,des-1,des,des-1,m,m,c,c,k1,k2,k1,k1,k2,k1,密钥长度2112,软硬件实现的速度,硬件实现：商业des芯片 vlsi 公司 vm009 1993年制造 200m bytes/s 软件实现： 80486， cpu 66hz, 每秒加密43000个des分组，336k bytes/s hp 9000/887 ,cpu 125 hz, 每秒加密196,000个分组，1.53m bytes/s,des算法的公开性与脆弱性,des的两个主要弱点：

27、密钥容量：56位不太可能提供足够的安全性 s盒：可能隐含有陷井（hidden trapdoors） des的半公开性：s盒的设计原理至今未公布 报告表明s盒在次序上、内容上是最优的。,des算法存在的问题与挑战,强力攻击：255次尝试 差分密码分析法：247次尝试 线性密码分析法：243次尝试,对des攻击结果及其启示,1997年1月28日美国rsa数据安全公司悬赏“秘密密钥挑战”竞赛 48位的rc5 313小时/3500台计算机 1997年3月13日rocke verser设计一个攻击程序（deschall），参加的志愿者有78516个，第96天（6月17日晚10：39）michael sa

28、nders破译成功，获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，057，572，442，069年,des chall搜索速度估算,其他密码算法,主要算法 des、3des、idea、sdbi、aes、rc5、cast-256 优缺点 简单、速度快 能力有限、密钥交换困难 实例 des,对称密码学,原理 加密和解密使用不同的密钥

29、一对密钥：公钥与私钥 示意图,非对称密码学,主要算法 rsa、dsa、eigamal、ecc、d-h 优缺点 复杂、速度慢 密钥交换简单、可用于身份鉴别 实例 rsa,非对称密码学,rsa算法简介,ron rivest, adi shamir, leonard adleman 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 +

30、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,数论基础,模运算是可交换的、可结合的、可分配的,(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

31、(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,数论基础,欧拉函数(n) n是正整数， (n) 是比n小且与n 互素的正整数的个数 (3)=|1, 2| =2 (4)=|1, 3| =2 (5)=|1, 2, 3, 4 | =4 (6)=

32、|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),数论基础,例如： 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,欧拉定理： 若整数m 和n 互素，则,等价形式,

33、数论基础,推论：给定两个素数p, q , 两个整数 n, m ，使得n=pq, 0mn ； 则对于任意整数k ，下列关系成立： m k(n)+1 m mod n,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

34、,令 k=4, 得到 求得d=77,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加密过程举例,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

35、= 77 公开(e,n)=(79, 119) 将d 保密，丢弃p, q； 加密：m=19 19 5 66 mod 119 , c= 66 解密： 6677 mod 119 =19,rsa 算法的安全性,攻击方法 蛮力攻击：对所有密钥都进行尝试 数学攻击：等效于对两个素数乘积(n)的因子分解 大数的因子分解是数论中的一个难题,因子分解的进展,rsa 算法的性能,速度 软件实现比des 慢100倍 硬件实现比des慢1000倍,diffie hellman密钥交换算法,第一个发表的公开密钥算法，1976 用于通信双方安全地协商一个会话密钥 只能用于密钥交换 基于离散对数计算的困难性 主要是模幂运算

36、 a p mod n,其他公钥密码算法,dsa 1991年, nist 提出了 数字签名算法（dsa）,并把它用户数字签名标准（dss） 只能用于数字签名 算法的安全性也是基于离散对数的难度 招致大量的反对，理由如下： dsa 不能用于加密或密钥分配 dsa是由 nsa研制的，可能有后门 dsa的选择过程不公开，提供的分析时间不充分 dsa比rsa慢（1040倍） 密钥长度太小（512位） dsa可能侵犯其他专利 rsa是事实上的标准,其他公钥密码算法,椭圆曲线密码系统 有限域gf(2n) 运算器容易构造 加密速度快 更小的密钥长度实现同等的安全性,主要算法 rsa、dsa、eigamal、e

37、cc、d-h 优缺点 复杂、速度慢 密钥交换简单、可用于身份鉴别 实例 rsa,非对称密码学,原理：对要传输的数据作运算生成信息摘要，产生信息的数字“指纹”。 主要算法：md2、md5、sha1、ripe-md 目的 确保数据没有被修改或变化 保证信息的完整性不被破坏 特点 输入信息长度任意，输出信息长度固定 给定输入信息，计算输出容易 不可预见、完全不可逆,单向散列,单向散列,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)是计算上不可行的。,简单的散列函数,纵向的奇偶校验码,ci= bi1 bi2 bim,+,+,md5算法简介,ron rivest 设计, rfc 1321 经历过md2, md4 不同的版本 对任意输入均产生128bit的输出 基于32位的简单操作，易于软件实现 简单而紧凑，没有复杂的程序和大数据结构 适合微处理器实现（特别是intel）,md5 产生报文摘要的过程,报文m,1000.0,长度,y0,