密码编码学与网络安全(第五版)02古典密码算法课件.ppt

《密码编码学与网络安全(第五版)02古典密码算法课件.ppt》由会员分享，可在线阅读，更多相关《密码编码学与网络安全(第五版)02古典密码算法课件.ppt（66页珍藏版）》请在三一办公上搜索。

1、Chapter 2 传统加密技术,Chapter 2 传统加密技术,本章要点,密码学基本概念古典/传统密码体制代替/代换技术：凯撒密码、单表代换密码、Playfair密码、Hill密码、多表代替密码；置换技术：栅栏技术转轮密码 隐写术,*,2,本章要点密码学基本概念*2,基本概念,密码学： 研究如何进行秘密通信或保密通信的科学 密码编码学：对信息进行编码，实现信息保密性 密码分析学：研究、分析、破译密码,*,3,基本概念密码学： 研究如何进行秘密通信或保密通信的科学*3,*,4,密码学的发展历史,第1阶段：1949年以前； 第2阶段：从1949年到1975年； 标志：1949年Shannon发

2、表保密系统的信息理论一文；第3阶段：1976年至今。 标志：1976年Diffie和Hellman发表密码学新方向一文。,*4密码学的发展历史 第1阶段：1949年以前；,*,5,基本术语,明文，plaintext - original message 密文，ciphertext - coded message 密码体制，密码，cipher - algorithm for transforming plaintext to ciphertext 密钥，key - info used in cipher known only to sender/receiver 加密，encipher (enc

3、rypt) - converting plaintext to ciphertext 解密，decipher (decrypt) - recovering plaintext from ciphertext,*5基本术语明文，plaintext - original,*,6,密码编码学Cryptography,研究内容主要研究对信息进行编码，实现对信息的隐蔽。特征运算类型：代换与置换所用的密钥数：单钥与双钥处理明文的方法：分组密码与流密码,*6密码编码学Cryptography研究内容,*,7,密码算法分类,按照保密内容受限制的（restricted）算法：算法的保密性基于保持算法的秘密；基于

4、密钥的（key-based）算法：算法的保密性基于对密钥的保密基于密钥的算法，按照密钥特点对称密码算法（传统密码算法或单钥密码算法）非对称算法（公开钥密码算法或双钥密码算法）按照明文处理方式分组密码流密码,*7密码算法分类按照保密内容,*,8,安全要求,加密算法必须足够强最低要求：已知密文时不能破译该密文或由密文推导出密钥；加强形式：已知某些明、密文对，也不能由此破译出新的密文或发现密钥。算法是基于密钥的：通信双方必须在某种安全形式下获得密钥并必须保证密钥的安全,*8安全要求加密算法必须足够强,*,9,密码分析学Cryptanalysis,密码破译攻击的一般方法密码分析学： cryptanal

5、ytic attack穷举攻击： brute-force attack,*9密码分析学Cryptanalysis密码破译,*,10,基于密码分析的攻击Cryptanalytic Attacks,惟密文攻击，ciphertext only only know algorithm & ciphertext, is statistical, know or can identify plaintext 已知明文攻击，known plaintext know/suspect plaintext & ciphertext选择明文攻击，chosen plaintext select plaintext a

6、nd obtain ciphertext选择密文攻击，chosen ciphertext select ciphertext and obtain plaintext选择文本攻击，chosen text select plaintext or ciphertext to en/decrypt,*10基于密码分析的攻击Cryptanalytic Att,*,11,两个概念,绝对安全，Unconditional Security 计算安全，Computational Security,19世纪，Kerckhoff原则： 系统的保密性不依赖于对加密体制或算法的保密，而依赖于对密钥的保密。,*11两个

7、概念绝对安全，Unconditional Secu,*,12,穷举攻击,*12穷举攻击Key Size (bits)Number o,*,13,非技术因素的攻击,偷窃收买逼问,*13非技术因素的攻击偷窃,*,14,2.1 对称密码的模型,传统密码/常规密码/私钥密码/单钥密码conventional / private-key / single-key发送方和接收方共享一个共同的密钥sender and recipient share a common key所有的传统密码算法都是私钥密码20世纪70年代以前私钥密码是唯一类型至今仍广泛应用,*142.1 对称密码的模型传统密码/常规密码/私钥

8、密码,*,15,对称密码模型（Symmetric Cipher Model）,*15对称密码模型（Symmetric Cipher Mo,*,16,对称密码安全的两个必备条件:加密算法必须是足够强的a strong encryption algorithm惟有发送者和接收者知道的秘密密钥a secret key known only to sender / receiver数学表示:C = EK(P) P = DK(C)假设加/解密算法是已知的拥有一个安全通道用于分发密钥,*16对称密码安全的两个必备条件:,*,17,*17,*,18,2.2 古典代替密码,将明文字母替换成其他字母、数字或符号

9、的方法;如果把明文看成是0或1的序列，那么密文就是0或1比特序列的另一种表达。,*182.2 古典代替密码将明文字母替换成其他字母、数字或,*,19,2.2.1 恺撒密码 Caesar Cipher,所知道的最早的代替密码Julius Caesar 首先用在军事通信中用字母后的第三个字母代替,*192.2.1 恺撒密码 Caesar Ciphe,*,20,恺撒密码 - 加密,方式一：公式计算明文编码： 如a=0，b=1，z=25，则 明文P p1p2pn（加密）运算：Ci pi + k （mod 26）, i 1,2,n解码得密文：C c1cc2cn,*20恺撒密码 - 加密方式一：公式计算,

10、*,21,恺撒密码-加密,方式二：查表（例k=3）,*21恺撒密码-加密方式二：查表（例k=3）明 文abcd,*,22,恺撒密码 - 解密,方式一：公式计算密文C c1c2cn（加密）运算：Pi ci - k （mod 26）, i1,2,n解码得明文： P p1p2pn,*22恺撒密码 - 解密方式一：公式计算,*,23,恺撒密码-解密,方式二：查表（例k=3）,*23恺撒密码-解密方式二：查表（例k=3）密文ABCDEF,*,24,恺撒密码,c = E(p) = (p + k) mod (26)p = D(c) = (c k) mod (26),*24恺撒密码c = E(p) = (p

11、+ k) mod,*,25,恺撒密码的密码分析,共有密钥25个 可简单地依次去测试 、强力搜索、穷举攻击 基于字母频率的破译方法所破译的明文需要识别如：破译密文 GCUA VQ DTGCM“ dzrx sn aqdzj （k=3） easy to break （k=2）,*25恺撒密码的密码分析 共有密钥25个,密钥短语密码就是选一个英文短语作为密钥字(Key Word)或密钥短语(Key Phrase)，如HAPPY NEW YEAR，去掉重复字母得HAPYNEWR。将它依次写在明文字母表之下，而后再将字母表中未在短语中出现过的字母依次写于此短语之后，就可构造出一个字母代换表。,*,26,2

12、.2.2 单表代替密码,密钥短语密码就是选一个英文短语作为密钥字(Key Word),若明文为：P = Casear cipher is a shift substitution则密文为：C=PHONHM PBKRNM BOH ORBEQ OSAOQBQSQBJI,*,27,若明文为：*27,*,28,单表代替密码分析,不是简单有序地字母移位 任意地打乱字母的顺序 每个明文字母映射到一个不同的随机密文字母 密钥数目： 26！,*28单表代替密码分析不是简单有序地字母移位,*,29,单表代替密码分析,密钥空间： 26! 4 x 1026 貌似安全，实则不然 语言特性,*29单表代替密码分析密钥空

13、间： 26! 4 x 102,*,30,语言的冗余与密码分析,人类的语言是有冗余的 字母的使用频率是不同的在英语中E使用的频率最高 有些字母使用较少单字母、双字母、三字母组合统计,*30语言的冗余与密码分析人类的语言是有冗余的,*,31,英语字母使用频率,*31英语字母使用频率,*,32,2.2.1 Playfair密码,单表代替密码由于密钥空间较小所以无法提供安全性；Playfair密码是一个多表代替密码 ；Charles Wheatstone 于1854年发明, 用其朋友Baron Playfair 命名。,*322.2.1 Playfair密码单表代替密码由于密钥,*,33,Playfa

14、ir密钥矩阵,5 X 5 填写密钥单词用其他字母填写剩下的空缺I = J,*33Playfair密钥矩阵 5 X 5 MONARCH,*,34,加密明文分组（填充）：2个字母组同行字母对加密：循环向右，eiFK同列字母对加密：循环向下，cuEM，xiAS其它字母对加密：矩形对角线字母，且按行排序，yaBN，esIL（或JL）解密加密的逆向操作,Playfair密码的加/解密步骤,*34加密Playfair密码的加/解密步骤,*,35,Playfair密码安全性分析,安全性优于单表代替密码密钥空间：25！1.61025在WW1（一战）中使用多年虽然明文中字母的统计规律在密文中得到了降低，但密文中

15、仍含有明文的部分结构信息给定几百个字母，即可被攻破明、密文字母不是一一对应关系,*35Playfair密码安全性分析安全性优于单表代替密码,*,36,字母出现的相对频率,*36字母出现的相对频率,*,37,2.2.4 希尔(Hill)密码,莱斯特S希尔（Lester S. Hill，18911961），美国数学家、教育家。1911年于哥伦比亚大学读完学士学位，1926年在耶鲁大学读完博士学位，于1929年发明希尔密码。是多表代替密码利用模运算意义下的矩阵乘法、求逆矩阵、线性无关、线性空间与线性变换等概念和运算,*372.2.4 希尔(Hill)密码莱斯特S希尔（L,*,38,Hill密码的加/

16、解密过程,明文分组并编码CKP mod 26，其中，K为密钥矩阵，P、C分别为明、密文分组,加密:,解密:,密文分组并编码PK-1C mod 26,对密钥矩阵K的要求：在mod 26下可逆,*38Hill密码的加/解密过程明文分组并编码加密:解密:密,*,39,密钥矩阵K,明文分组P“mor”,明文编码 P,加密 C,mod 26,解码 C,，即C“HDL”,Hill密码的例子,加密：,K1,*39密钥矩阵K明文分组P“mor”明文编码 P加密,*,40,密钥矩阵K,明文P“mor”,明文 P,解密 P,mod 26,C,C“HDL”,Hill密码的例子,解密：,K1,*40密钥矩阵K明文P“

17、mor”明文 P解密 P,*,41,Hill密码的特点,字母的统计规律进一步降低明、密文字母不是一一对应关系,*41Hill密码的特点字母的统计规律进一步降低,*,42,2.2.5 多表代替密码Polyalphabetic Ciphers,特点：在明文消息中采用不同的单表代换。安全性提高 使得字母的频率分布更加平坦用一个密钥指示明文消息中每个字母加解密时所用的代替表密钥依次重复使用，代替表依次重复使用 例子：Vigenre（维吉利亚）密码（1858）Vernam（唯尔南）密码（1918）,*422.2.5 多表代替密码Polyalphabeti,*,43,一、 Vigenre（维吉利亚）密码,

18、方式一：数学公式计算设明文 P = p1p2pn，密钥 k = k1k2kn，密文C = c1c2cn 明文编码； 计算 ci= pi+ki (mod 26)，=1，2，n； 密文解码。说明：若明文长度大于n，则K重复使用。,加密:,*43一、 Vigenre（维吉利亚）密码方式一：数学公式,*,44,方式二：查表法,一、 Vigenre（维吉利亚）密码,*44方式二：查表法一、 Vigenre（维吉利亚）密码,*,45,一、 Vigenre（维吉利亚）密码,方法一：数学公式计算pi = ciki (mod 26)，=1，2，n；方法二：查表,解密：,*45一、 Vigenre（维吉利亚）密码

19、方法一：数学公式,*,46,Vigenre密码例子,加密过程：P“encode and decode”，k“mykey”,*46Vigenre密码例子加密过程：字母序号123456,*,47,Vigenre密码例子,解密过程：C“QLMSBQYXHBQAYHB”，k“mykey”,*47Vigenre密码例子解密过程：字母序号123456,*,48,Vigenre密码的安全性,密钥空间：|K|26n字母的统计规律进一步降低明、密文字母不是一一对应关系Vigenre本人建议：密钥与明文一样长特例：当k1 k2 kn k时，是Caesar密码,*48Vigenre密码的安全性密钥空间：|K|26n

20、,*,49,2.2.6 一次一密,随机密钥理论上不可破实际上不可行产生大量的随机密钥难密钥分配与保护更难,*492.2.6 一次一密随机密钥,*,50,栅栏技术思想：以列（行）优先写出明文，以行（列）优先读出各字母作为密文例1：先行后列例2：先列后行改 进带有密钥再改进：重复加密，多步置换,2.3 置换密码Transposition Ciphers,*50栅栏技术2.3 置换密码Transposition,*,51,例：栅栏密码(Rail Fence cipher),明文：meet me after the toga party写作:m e m a t r h t g p r y e t e

21、f e t e o a a t读出密文为：MEMATRHTGPRYETEFETEOAAT,*51例：栅栏密码(Rail Fence cipher)明文,栅栏技术：按对角线的顺序写出明文，以行的顺序读出作为密文,密文消息 “MEMATEAKETETHPR”,无密钥的置换技术,Example,明文消息 “Meet me at the park”,栅栏技术：按对角线的顺序写出明文，以行的顺序读出作为密文密文,带密钥的置换技术,带密钥的置换技术,置换操作中的加密密钥和解密密钥,同一个密钥在加密和解密（列置换）过程中，以不同的方向来使用在加解密过程中好像使用的是两个不同的密钥,2. 带密钥的置换技术,置

22、换操作中的加密密钥和解密密钥同一个密钥在加密和解密（列置换,*,55,更加复杂的移位以指定的行将明文写作多行按照密钥指定的列读出Key:Plaintext: Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ,例：行移位密码 Row Transposition Ciphers,*55更加复杂的移位例：行移位密码 Row Transpos,*,56,2.4 转轮密码,在现代密码之前，转轮密码是最广泛使用的复杂的密码广泛用在第二次世界大战中German Enigma, Allied Hagelin, Japanese Purple实现了复杂多变的多表代替密码，多层加密

23、采用一系列转轮，每一个都是一个代替表，转轮可以依次旋转加密每个字母用3个转轮就有 263=17576 代替表,*562.4 转轮密码在现代密码之前，转轮密码是最广泛使,*,57,*57,*,58,Enigma 密码机(德国),*58Enigma 密码机(德国),*,59,Two diagrams of the Enigma,*59Two diagrams of the Enigma,*,60,Hagelin 转轮密码机（盟军 ）,*60Hagelin 转轮密码机（盟军 ）,*,61,M-209 密码机（美国）,*61M-209 密码机（美国）,*,62,Purple 密码机（日本）,*62Pu

24、rple 密码机（日本）,*,63,2.5 隐写术Steganography,隐藏信息的存在字符标记用不可见的墨水隐藏在图形图像或声音文件的LSB上缺点需要额外的付出来隐藏相对较少的信息,*632.5 隐写术Steganography隐藏信息的,*,64,*64,*,65,小结,古典密码技术及术语单表代替密码用字母频率进行密码分析Playfair密码多表代替密码置换密码转轮机密码隐写术,*65小结,*,66,作业,思考题：2.2、2.5、2.8、2.9、2.11习题：2.11、2.14阅读一些关于密码历史或战争中密码应用的资料或故事,*66作业思考题：2.2、2.5、2.8、2.9、2.11,