1、福尔摩斯探案集之跳舞的小人 TG“天王盖地虎，宝塔镇河妖”大家一定在电影里看过对暗号的场面。其实，这种暗号是一种最朴素的密码。只不过这种密码过于简单，经不起密码学家的分析，非常容易破译。将密码当成一种科学来研究，就产生了密码学。第二章 密码学技术1、密码学概述2、古典密码学3、分组密码学4、公钥密码学本章重点及难点 本章主要问题集中在现代密码学部分，对称密钥学中的DES加密算法及IDEA加密算法，公钥密码学中的RSA加密算法和ELGamal算法为本章的重点及难点，需要大家好好理解。密码学基本概念 明文：明文：需要秘密传送的消息。需要秘密传送的消息。密文：密文：明文经过密码变换后的消息。明文经过
2、密码变换后的消息。加密：加密：由明文到密文的变换。由明文到密文的变换。解密：解密：从密文恢复出明文的过程。从密文恢复出明文的过程。破译：破译：非法接收者试图从密文分析出明文的过程。非法接收者试图从密文分析出明文的过程。加密算法：加密算法：对明文进行加密时采用的一组规则。对明文进行加密时采用的一组规则。解密算法：解密算法：对密文进行解密时采用的一组规则。对密文进行解密时采用的一组规则。密钥：密钥：加密和解密时使用的一组秘密信息。加密和解密时使用的一组秘密信息。明文Plaintext 密文Cipher text加密Encryption 解密Decryption密钥key加解密过程示意图明文明文密文
3、加密算法解密算法密钥密钥加/解密原理描述 假设明文字母用P或者M表示，密文字母用C表示,密钥用K表示,加密变换用E表示，解密变换用D表示，则有：1.加密原理 文字描述：C=Ek(p)2.解密原理 文字描述：p=Dk(C)加密变换EpC解密变换DpC密码学的发展历史q 发展史发展史q 早在早在40004000多年以前，古埃及人就在墓志铭中使用过类似于象形文字那多年以前，古埃及人就在墓志铭中使用过类似于象形文字那样奇妙的符号；样奇妙的符号；q 公元前约公元前约5050年，凯撒密码一种简单的字符替换被认为是最早的正年，凯撒密码一种简单的字符替换被认为是最早的正式算法；式算法；q 双轨式密码、网格式密
4、码、字典编号密码；双轨式密码、网格式密码、字典编号密码；q 传统密码学、现代密码学、量子密码学。传统密码学、现代密码学、量子密码学。19491949年之前年之前 古典加密学古典加密学 密码学作为一种技艺，是一门艺术，而不是一种科学密码学作为一种技艺，是一门艺术，而不是一种科学 1949 194919751975年年 shannonshannon的的“communication theory of secrecy system”communication theory of secrecy system”密密码学成为科学码学成为科学 主要技术：单密钥的对称密钥加密算法主要技术：单密钥的对称密钥加
5、密算法19761976年以后年以后 Diffie,HellmanDiffie,Hellman发表发表“new directions in cryptography”new directions in cryptography”密码学的新方向密码学的新方向公钥密码学公钥密码学q 应用领域应用领域q 军事、外交、情报军事、外交、情报 商业、个人通信商业、个人通信example-i(象形文字的修改)Modified Hieroglyphics,c.1900 B.C.密码学的第一个例子是对标准书写符号的修改 例如:古埃及法老坟墓上的文字 思想:代替(substitution)example-ii Sp
6、artan Scytale,c.500 B.C.斯巴达人用于加解密的一种军事设备 发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（permutation)example-iii Polybius Checkerboard,205123 B.C.明文:POLYBIUS 密文:3534315412244543 123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZExample-iv Caesar Cipher,c.50 B.C.A B C D E F G X Y Z D E F G H I J A B C 明文:Caesar cipher is a shift subst
7、itution 密文:FDHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQExample-V Nomenclator 代码本 c.1400字母、符号、单词、短语 代码代码 字母、符号、单词、短语应用：World War II2.1 古典密码 代换密码 单表代换密码移位密码替换密码仿射密码 多表代换密码 Vigenre(维吉尼亚）密码 置换密码代换密码 令表示明文字母表，内有q个“字母”或“字符”，可以将抽象地表示为一个整数集 在加密时通常将明文消息划分成长为L的消息单元，称为明文组，以m表示，如 m也称作L报文，它可以看作是定义在 上的随机变量 L1为单字母报（1gram
8、），L2为双字母报（digrams），L3为三字母报（trigrams）。这时明文空间为 。1,1,0qZq10,),(110LlZmmmmmqlLLqZ10,),(110LlZmmmmmLZZZZNlLqqqLq个LqZP 代换密码（续）令表示q个“字母”或“字符”的密文字母表，抽象地可用整数集 表示 密文单元或组为 c是定义在 上的随机变量。密文空间 一般地，明文和密文由同一字母表构成，即1,1,0qZq10,)(,(110LlZcLccccqlL个）LqZLqZC 代换密码（续）代换密码可以看作是从 到 的映射。时 ，称作单字母代换，也称作流密码（Stream cipher）。时，称作多
9、码代换，亦称分组密码（Block cipher）。一般地，选择相同明文和密文字母表。此时，若 ,则代换映射是一一映射，密码无数据扩展。若 ,则有数据扩展，可将加密函数设计成一对多的映射，即明文组可以找到多于一个密文组来代换，这称之为多名（或同音）代换密码（Homophonic substitution cipher）。若 ,则明文数据被压缩，此时代换映射不可能构成可逆映射，从而密文有时也就无法完全恢复出原明文消息，因此保密通信中必须要求 。但 的映射可以用在认证系统中。LqZLqZ1L1LLL LL LL LL LL 代换密码（续）在，时，若对所有明文字母，都用一种固定的代换进行加密，则称这种
10、密码为单表代换（Monoalphabetic substitute）。若用一个以上的代换表进行加密，这就称作多表代换（Polyalphabetic substitute）。这是古典密码中的两种重要体制。还有一个常见的是多字母代换密码。qq 1L单表代换密码 单表代换密码是对明文的所有字母都用一个固定的明文字母表到密文字母表的映射，即 。令明文 ，则相应地密文为 几类常见的单表代换密码 移位密码 替换密码 仿射密码 单表代换密码不能非常有效地抵抗密码攻击，因为语言的特征仍能从密文中提取出来 qqZZf:10mmm)()()(1010mfmfccmec移位密码 由于英文字符有26个字母，可以建立英
11、文字母和模26的剩余之间的对应关系：A B C D E F G H IJ KLMN0 1 2 3 4 5 6 7 8910111213O PQ RS T UV W X Y Z14 15 16 17 18 19 20 21 22 23 24 25移位密码（续）对于英文文本，则明文、密文空间都可定义为 （很容易推广到n个字母的情况）。容易看出移位满足我们密码系统的定义，即 。26Z,)(xxxedkk对每个26Z设 定义 ，且。,250,26kZKCP对26mod)(kxxek26,26mod)(Zyxkyydk凯撒密码历史上最著名的移位密码就是凯撒密码。凯撒密码(Caesar cipher)（1
12、）原理（明密对照表）明文：a b c d e f g h I j k l m n o p q r s t u v w x y z 密文：D E F G H I J K L M N O P Q R S T U V W X Y Z A B C（2）算法描述（数学描述）假设明文字母用P表示，密文字母用C表示，密钥用K表示，加密变换用E表示，解密变换用D表示，并设a=0,b=1,c=2,d=3,x=23,y=24,z=25,则有：C=Ek(p)=(p+3)mod(26)p=Dk(C)=(C-3)mod(26)-C不够减时可向前借位 在计算机中，a=97,b=98,c=99,d=100,x=120,y=
13、121,z=122，则：明密对照表如下：明文：97，98，99，100，120，121，122 密文：100，101，102，103，97，98，99 加/解密算法描述如下：C=Ek(p)=(p-97)+3mod(26)+97 p=Dk(C)=(C-97)-3mod(26)+97 -若(C-97-3)0时，C可借位 （1）求明文字母a的密文字母的过程如下：C=（a-97）+3mod(26)+97=3+97=100(d)（2）求明文字母z的密文字母的过程如下：C=（z-97)+3mod(26)+97=28mod(26)+97=2+97=99（c)（3）求密文字母C的明文字母的过程如下：p=(99
14、-97)-3mod(26)+97=(2-3)+26mod(26)+97=25+97=122（z)(4)求密文字母A的明文字母的过程如下：p=(97-97)-3mod(26)+97=(0-3)+26mod(26)+97=23+97=120(x)替换密码 定义设 ，密钥空间K由所有可能的26个符号0，1，.，25的置换组成。对每一个置换 ，定义 则，其中 的逆置换。26ZCP)()(xxe)()(1yyd是1 置换 的表示为：替换密码的密钥是由26个字母的置换组成。这些置换的数目是26！，超过 ，是一个非常大的数。这样即使对现代计算机来说，穷举密钥搜索也是不可行的。显然，替换密码的密钥（26个元素
15、的随机置换）太复杂而不容易记忆，因此实际中密钥句子常被使用。密钥句子中的字母被依次填入密文字母表（重复的字母只用一次），未用的字母按自然顺序排列。25242321025242321026100.4 仿射密码仿射密码 加密函数为：当a1时，为移位密码;当b=0时，为乘法密码；仿射函数是双射 当且仅当gcd(a,26)=1时同余方程 对每个y有唯一的解 26,26mod)(Zbabaxxe)26(modybax仿射密码系统仿射密码系统 设 ，且 对 定义 且 因为满足 ，gcd(a,26)=1的 只有12种候选，对参数没有要求。所以仿射密码有 种可能的密钥。26ZCP1)26,gcd(:),(26
16、26aZZbaKKbak),(26mod)(baxxe26mod)()(1byaydk),(26Zyx26Za3122612a单表加密的破解 对于单表替代密码，加法密码和乘法密码对于单表替代密码，加法密码和乘法密码的密钥量比较小，可利用穷举密钥的方法的密钥量比较小，可利用穷举密钥的方法进行破译。进行破译。穷举不是攻击密码的惟一方法，密码分析穷举不是攻击密码的惟一方法，密码分析者便可利用语言的统计特性进行分析。者便可利用语言的统计特性进行分析。如如果明文语言的这种统计特性在明文中有所果明文语言的这种统计特性在明文中有所反映，密码分析者便可通过分析明文和密反映，密码分析者便可通过分析明文和密文的统
17、计规律而破译密码。文的统计规律而破译密码。表 26个英文字母出现频率统计表 字母出现频率字母出现频率a0.0856n0.0707b0.0139o0.0797c0.0279p0.0199d0.0378q0.0012e0.1304r0.0677f0.0289s0.0607g0.0199t0.1045h0.0528u0.0249i0.0627v0.0092j0.0013w0.0149k0.0042x0.0017l0.0339y0.0199m0.0249z0.0008通过对26个英文字母出现频率的分析，可以有以下结果：（1）e出现的频率最大，约为0.13；（2）t，a，o，i，n，s，h，r出现的频率
18、约在0.060.1之间；（3）d，l出现的频率在0.04附近；（4）c，u，m，w，f，g，y，p，b出现的频率约在0.015 0.029之间；（5）v，k，j，x，q，z出现的频率小于0.01。在密码分析中，除了考虑单字母统计特性外，掌握双字母、三字母的统计特性以及字母之间的连缀关系等信息也是很有用的。出现频率最高的30个双字母组合依次是：th heineranreedonesstenattonthand oueangas ortiisetitartesehiof 出现频率最高的20个三字母组合依次是：theing and her ere enttha nth was eth for dth hat she ionint his sth ers ver 特别的，the出现的频率几乎是ing的3倍，这在密码分析中很有用。此外，统计资料还表明：英文单词以e，s，d，t字母结尾的超过一半。英文单词以t，a，s，w为起始字母的约占一半。以上这些统计数据是通过非专业性文献中的字母进行统计得到的。对于密码分析者来说，这些都是十分有用的信息。除此之外，密码分析者对明文相关知识的掌握对破译密码也是十分重要的。课后习题 1、使用移位加密算法，设k=7时，对He is a spy.进行加密。2、使用仿射加密算法，设a=5，b=11时，对He is a spy.进行加密。
