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