1、本章要点本章要点n密码学基本概念密码学基本概念n古典古典/传统密码体制传统密码体制q代替代替/代换技术：凯撒密码、单表代换密码、代换技术：凯撒密码、单表代换密码、Playfair密码、密码、Hill密码、多表代替密码；密码、多表代替密码；q置换技术：栅栏技术置换技术：栅栏技术n转轮密码转轮密码n 隐写术隐写术 2022年1月22日6时26分2基本概念n密码学：密码学： 研究如何进行秘密通信或保密通信的科研究如何进行秘密通信或保密通信的科学学n 密码编码学：对信息进行编码，实现信息保密性密码编码学：对信息进行编码，实现信息保密性n 密码分析学：研究、分析、破译密码密码分析学：研究、分析、破译密码
2、2022年1月22日6时26分32022年1月22日6时26分4密码学的发展历史密码学的发展历史 n第第1阶段：阶段：1949年以前；年以前； n第第2阶段：从阶段：从1949年到年到1975年；年； q标志：标志：1949年年Shannon发表保密系统的信息发表保密系统的信息理论一文；理论一文；n第第3阶段：阶段：1976年至今。年至今。 q标志：标志：1976年年Diffie和和Hellman发表密码学发表密码学新方向一文。新方向一文。2022年1月22日6时26分5n明文明文，plaintext - original message n密文密文，ciphertext - coded me
3、ssage n密码体制，密码密码体制，密码，cipher - algorithm for transforming plaintext to ciphertext n密钥密钥，key - info used in cipher known only to sender/receiver n加密加密，encipher (encrypt) - converting plaintext to ciphertext n解密解密，decipher (decrypt) - recovering plaintext from ciphertext2022年1月22日6时26分6n研究内容研究内容q主要研究对
4、信息进行编码，实现对信息的主要研究对信息进行编码，实现对信息的隐蔽隐蔽。n特征特征q运算类型：代换与置换运算类型：代换与置换q所用的密钥数：单钥与双钥所用的密钥数：单钥与双钥q处理明文的方法：分组密码与流密码处理明文的方法：分组密码与流密码2022年1月22日6时26分7n按照保密内容按照保密内容q受限制的（受限制的（restricted）算法：算法的保密性基于）算法：算法的保密性基于保持算法的秘密；保持算法的秘密；q基于密钥的（基于密钥的（key-based）算法：算法的保密性基）算法：算法的保密性基于对密钥的保密于对密钥的保密n基于密钥的算法，按照密钥特点基于密钥的算法，按照密钥特点q对称
5、密码算法（传统密码算法或单钥密码算法）对称密码算法（传统密码算法或单钥密码算法）q非对称算法（公开钥密码算法或双钥密码算法）非对称算法（公开钥密码算法或双钥密码算法）n按照明文处理方式按照明文处理方式q分组密码分组密码q流密码流密码2022年1月22日6时26分8n加密算法必须足够强加密算法必须足够强q最低要求：已知密文时不能破译该密文或由密文最低要求：已知密文时不能破译该密文或由密文推导出密钥；推导出密钥；q加强形式：已知某些明、密文对，也不能由此破加强形式：已知某些明、密文对，也不能由此破译出新的密文或发现密钥。译出新的密文或发现密钥。n算法是基于密钥的：通信双方必须在某种安算法是基于密钥
6、的：通信双方必须在某种安全形式下获得密钥并必须保证密钥的安全全形式下获得密钥并必须保证密钥的安全2022年1月22日6时26分9n密码破译密码破译n攻击的一般方法攻击的一般方法q密码分析学：密码分析学： cryptanalytic attackq穷举攻击：穷举攻击： brute-force attack2022年1月22日6时26分10n惟密文攻击，惟密文攻击，ciphertext only qonly know algorithm & ciphertext, is statistical, know or can identify plaintext n已知明文攻击，已知明文攻击，known
7、 plaintext qknow/suspect plaintext & ciphertextn选择明文攻击，选择明文攻击，chosen plaintext qselect plaintext and obtain ciphertextn选择密文攻击，选择密文攻击，chosen ciphertext qselect ciphertext and obtain plaintextn选择文本攻击，选择文本攻击，chosen text qselect plaintext or ciphertext to en/decrypt2022年1月22日6时26分11n绝对安全，绝对安全，Unconditio
8、nal Security n计算安全，计算安全，Computational Security 19世纪，世纪，Kerckhoff原则原则： 系统的保密性系统的保密性不依赖于不依赖于对加密体制或对加密体制或算法的保密，算法的保密，而依赖于而依赖于对对密钥密钥的保密。的保密。2022年1月22日6时26分1232232 = 4.3 109231 s = 35.8 minutes2.15 milliseconds56256 = 7.2 1016255 s = 1142 years10.01 hours1282128 = 3.4 10382127 s = 5.4 1024 years5.4 1018
9、years1682168 = 3.7 10502167 s = 5.9 1036 years5.9 1030 years26 characters (permutation)26! = 4 10262 1026 s= 6.4 1012 years6.4 106 years2022年1月22日6时26分13n偷窃偷窃n收买收买n逼问逼问n2022年1月22日6时26分14n传统密码传统密码/常规密码常规密码/私钥密码私钥密码/单钥密码单钥密码conventional / private-key / single-keyn发送方和接收方共享一个共同的密钥发送方和接收方共享一个共同的密钥sender
10、 and recipient share a common keyn所有的传统密码算法都是私钥密码所有的传统密码算法都是私钥密码n20世纪世纪70年代以前私钥密码是唯一类型年代以前私钥密码是唯一类型n至今仍广泛应用至今仍广泛应用2022年1月22日6时26分152022年1月22日6时26分16n对称密码安全的两个必备条件对称密码安全的两个必备条件:q加密算法必须是足够强的加密算法必须是足够强的a strong encryption algorithmq惟有发送者和接收者知道的秘密密钥惟有发送者和接收者知道的秘密密钥a secret key known only to sender / rec
11、eivern数学表示数学表示:C = EK(P) P = DK(C)n假设加假设加/解密算法是已知的解密算法是已知的n拥有一个安全通道用于分发密钥拥有一个安全通道用于分发密钥2022年1月22日6时26分172022年1月22日6时26分18n将明文字母替换成其他字母、数字或符号将明文字母替换成其他字母、数字或符号的方法的方法;n如果把明文看成是如果把明文看成是0或或1的序列，那么密文的序列，那么密文就是就是0或或1比特序列的另一种表达。比特序列的另一种表达。2022年1月22日6时26分19n所知道的最早的代替密码所知道的最早的代替密码nJulius Caesar n首先用在军事通信中首先用
12、在军事通信中n用字母后的第三个字母代替用字母后的第三个字母代替明明 文文a bcdefg hijkl m n o p qrstu v w xyz密密 文文D E F G H IJ K L M N O P Q R S T U V W X Y Z A B C2022年1月22日6时26分20n方式一：公式计算方式一：公式计算q明文编码：明文编码： 如如a=0，b=1，z=25，则，则 明文明文P p1p2pn（加密）运算：（加密）运算：Ci pi + k （mod 26）, i 1,2,nq解码得解码得密文密文：C c1cc2cn2022年1月22日6时26分21n方式二：查表（例方式二：查表（例
13、k=3）明 文abcdefghijklm nopqrstuvwxyz密 文DEFG HIJKLM N O PQ RSTUV W XYZA B C2022年1月22日6时26分22n方式一：公式计算方式一：公式计算q密文密文C c1c2cn（加密）运算：（加密）运算：Pi ci - k （mod 26）, i1,2,nq解码得解码得明文明文： P p1p2pn2022年1月22日6时26分23n方式二：查表（例方式二：查表（例k=3）密文密文ABCDEFGHIJKLMNOPQRSTUV W X Y Z明文明文xyzabcdefghijklmnopqrstuv w2022年1月22日6时26分24
14、c = E(p) = (p + k) mod (26)p = D(c) = (c k) mod (26)2022年1月22日6时26分25n共有密钥25个 n可简单地依次去测试 、强力搜索、穷举攻击 n基于的破译方法n所破译的明文需要识别q如：破译密文 GCUA VQ DTGCM“ dzrx sn aqdzj （k=3） easy to break （k=2）n密钥短语密码就是选一个英文短语作为密钥字密钥短语密码就是选一个英文短语作为密钥字(Key Word)或密钥短语或密钥短语(Key Phrase)，如，如HAPPY NEW YEAR，去掉重复字母得，去掉重复字母得HAPYNEWR。n将它
15、依次写在明文字母表之下，而后再将字母表中未将它依次写在明文字母表之下，而后再将字母表中未在短语中出现过的字母依次写于此短语之后，就可构在短语中出现过的字母依次写于此短语之后，就可构造出一个字母代换表。造出一个字母代换表。2022年1月22日6时26分26n若明文为：若明文为：qP = Casear cipher is a shift substitutionn则密文为：则密文为：qC=PHONHM PBKRNM BO H ORBEQ OSAOQBQSQBJI2022年1月22日6时26分272022年1月22日6时26分28n不是简单有序地字母移位 n任意地打乱字母的顺序 n每个明文字母映射到
16、一个不同的随机密文字母 n密钥数目： 26！ 2022年1月22日6时26分29n密钥空间空间： 26! 4 x 1026 n貌似安全，实则不然 n语言特性2022年1月22日6时26分30n人类的语言是有冗余的人类的语言是有冗余的 n字母的使用频率是不同的字母的使用频率是不同的n在英语中在英语中E使用的频率最高使用的频率最高 n有些字母使用较少有些字母使用较少n单字母、双字母、三字母组合统计单字母、双字母、三字母组合统计2022年1月22日6时26分312022年1月22日6时26分32n单表代替密码由于密钥空间较小所以无法提供安全性；nPlayfair密码是一个多表代替密码密码是一个多表代
17、替密码 ；nCharles Wheatstone 于1854年发明, 用其朋友Baron Playfair 命名。2022年1月22日6时26分33n 5 X 5 n填写密钥单词填写密钥单词n用其他字母填写剩下的空缺用其他字母填写剩下的空缺nI = J2022年1月22日6时26分34n加密加密q明文分组（填充）：明文分组（填充）：2个字母组个字母组q同行字母对加密：循环向右，同行字母对加密：循环向右，eiFKq同列字母对加密：循环向下，同列字母对加密：循环向下，cuEM，xiASq其它字母对加密：矩形对角线字母，且按行其它字母对加密：矩形对角线字母，且按行排序，排序，yaBN，esIL（或（
18、或JL）n解密解密q加密的逆向操作加密的逆向操作2022年1月22日6时26分35n安全性优于单表代替密码安全性优于单表代替密码n密钥空间：密钥空间：25！1.61025n在在WW1（一战）中使用多年（一战）中使用多年n虽然明文中字母的统计规律在密文中得到了虽然明文中字母的统计规律在密文中得到了降低，但密文中仍含有明文的部分结构信息降低，但密文中仍含有明文的部分结构信息n给定几百个字母，即可被攻破给定几百个字母，即可被攻破n明、密文字母不是一一对应关系明、密文字母不是一一对应关系2022年1月22日6时26分36字母出现的相对频率字母出现的相对频率2022年1月22日6时26分37n莱斯特莱斯
19、特S希尔（希尔（Lester S. Hill，18911961），美国数学家、教育），美国数学家、教育家。家。1911年于哥伦比亚大学读完学年于哥伦比亚大学读完学士学位，士学位，1926年在耶鲁大学读完博年在耶鲁大学读完博士学位，于士学位，于1929年发明希尔密码。年发明希尔密码。n是多表代替密码是多表代替密码n利用模运算意义下的矩阵乘法、求利用模运算意义下的矩阵乘法、求逆矩阵、线性无关、线性空间与线逆矩阵、线性无关、线性空间与线性变换等概念和运算性变换等概念和运算 2022年1月22日6时26分38n明文分组并编码明文分组并编码nCKP mod 26，其中，其中，K为密钥矩阵，为密钥矩阵，P
20、、C分别为明、密文分组分别为明、密文分组n密文分组并编码密文分组并编码nPK-1C mod 26 2022年1月22日6时26分39密钥矩阵密钥矩阵K92221182151717明文分组明文分组P“mor” rom171412明文编码明文编码 P 192221182151717 171412 375651527 1137加密加密 C mod 26解码解码 C LDH，即，即C“HDL”Hill密码的例子密码的例子加密加密： 17024617151594K12022年1月22日6时26分40密钥矩阵密钥矩阵K92221182151717明文明文P“mor” rom171412明文明文 P 113
21、7解密解密 P mod 26C LDHC“HDL” 17024617151594 1137解密解密： 17024617151594K1171412 3552222202022年1月22日6时26分41n字母的统计规律进一步降低字母的统计规律进一步降低n明、密文字母不是一一对应关系明、密文字母不是一一对应关系2022年1月22日6时26分42n特点：在明文消息中采用不同的单表代换。特点：在明文消息中采用不同的单表代换。n安全性提高安全性提高 n使得字母的频率分布更加使得字母的频率分布更加平坦平坦n用一个密钥指示明文消息中每个字母加解密用一个密钥指示明文消息中每个字母加解密时所用的代替表时所用的代
22、替表n密钥依次重复使用，代替表依次重复使用密钥依次重复使用，代替表依次重复使用 n例子：例子：qVigenre（维吉利亚）密码（维吉利亚）密码（1858）qVernam（唯尔南）密码（唯尔南）密码（1918）2022年1月22日6时26分43n方式一：数学公式计算方式一：数学公式计算q设明文设明文 P = p1p2pn，密钥，密钥 k = k1k2kn，密，密文文C = c1c2cnn 明文编码；明文编码；n 计算计算 ci= pi+ki (mod 26)，=1，2，n；n 密文解码。密文解码。q说明：若明文长度大于说明：若明文长度大于n，则，则K重复使用。重复使用。2022年1月22日6时2
23、6分44n方式二：查表法方式二：查表法2022年1月22日6时26分45一、 Vigenre（维吉利亚）密码（维吉利亚）密码n方法一：数学公式计算方法一：数学公式计算qpi = ciki (mod 26)，=1，2，n；n方法二：查表方法二：查表2022年1月22日6时26分46n加密过程：加密过程：qP“encode and decode”，k“mykey”字母序号字母序号123456789101112131415明文编码明文编码P =4132143401333421434密钥编码密钥编码k =122410424122410424122410424加密加密C =163712182716242
24、3727162624728模运算模运算111102密文解码密文解码C =QLMSBQYXHBQAYHB2022年1月22日6时26分47n解密过程：解密过程：qC“QLMSBQYXHBQAYHB”，k“mykey”字母序号字母序号123456789101112131415密文编码密文编码C=161112181162423711602472密钥编码密钥编码k=122410424122410424122410424加密加密C=4-13214-2340133-234-24143-22模运算模运算133324密文解码密文解码C=encodeanddecode2022年1月22日6时26分48n密钥空间
25、：密钥空间：|K|26nn字母的统计规律进一步降低字母的统计规律进一步降低n明、密文字母不是一一对应关系明、密文字母不是一一对应关系nVigenre本人建议：密钥与明文一样长本人建议：密钥与明文一样长n特例：特例：q当当k1 k2 kn k时，是时，是Caesar密码密码2022年1月22日6时26分49n随机密钥随机密钥n理论上不可破理论上不可破n实际上不可行实际上不可行q产生大量的随机密钥难产生大量的随机密钥难q密钥分配与保护更难密钥分配与保护更难2022年1月22日6时26分50n思想：以列（行）优先写出明文，以思想：以列（行）优先写出明文，以行（列）优先读出各字母作为密文行（列）优先读
26、出各字母作为密文q例例1：先行后列：先行后列q例例2：先列后行：先列后行n带有密钥带有密钥n再改进：重复加密，多步置换再改进：重复加密，多步置换2022年1月22日6时26分51n明文：meet me after the toga partyn写作:m e m a t r h t g p r y e t e f e t e o a a tn读出密文为：MEMATRHTGPRYETEFETEOAAT：按对角线的顺序写出明文，以行的顺序读出作为密文密文消息 “MEMATEAKETETHPR”Example明文消息 “Meet me at the park”置换操作中的加密密钥和解密密钥l 同一个密
27、钥在加密和解密（列置换）过程中，以不同的方向来使用l 在加解密过程中好像使用的是两个不同的密钥2022年1月22日6时26分55n更加复杂的移位更加复杂的移位n以指定的行将明文写作多行以指定的行将明文写作多行n按照密钥指定的列读出按照密钥指定的列读出qKey:qPlaintext: qCiphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ a tta c k po s tp o n ed u n tiltw o a m x y z2022年1月22日6时26分56n在现代密码之前，转轮密码是最广泛使用的在现代密码之前，转轮密码是最广泛使用的复杂的密码复杂的密码n广泛用
28、在第二次世界大战中广泛用在第二次世界大战中qGerman Enigma, Allied Hagelin, Japanese Purplen实现了复杂多变的多表代替密码，多层加密实现了复杂多变的多表代替密码，多层加密n采用一系列转轮，每一个都是一个代替表，采用一系列转轮，每一个都是一个代替表，转轮可以依次旋转加密每个字母转轮可以依次旋转加密每个字母q用用3个转轮就有个转轮就有 263=17576 代替表代替表2022年1月22日6时26分572022年1月22日6时26分582022年1月22日6时26分592022年1月22日6时26分602022年1月22日6时26分612022年1月22日
29、6时26分622022年1月22日6时26分63n隐藏信息的存在隐藏信息的存在q字符标记字符标记q用不可见的墨水用不可见的墨水q隐藏在图形图像或声音文件的隐藏在图形图像或声音文件的LSB上上n缺点缺点q需要额外的付出来隐藏相对较少的信息需要额外的付出来隐藏相对较少的信息2022年1月22日6时26分642022年1月22日6时26分65小结q古典密码技术及术语古典密码技术及术语q单表代替密码单表代替密码q用字母频率进行密码分析用字母频率进行密码分析qPlayfair密码密码q多表代替密码多表代替密码q置换密码置换密码q转轮机密码转轮机密码q隐写术隐写术2022年1月22日6时26分66作业作业
