对称密码-- --古典密码

1、第二讲 对称密码- -古典密码一、内容提要1. 为什么需要密码2. 基本的概念和术语3. 密码学的历史4. 传统加密的古典技术-代替密码-置换密码 l 为什么需要密码1. 信息的存储：在公开的地方2. 信息的交换：使用非隐秘介质3. 信息的传输：通过不安全信道 l 基本概念1. 密码学(Cryptology)： 是研究信息系统安全保密的科学。2. 密码编码学(Cryptography)：主要研究对信息进行编码（压缩、保密和纠错），实现对信息的隐蔽。3. 密码分析学(Cryptanalytics)：主要研究加密消息的破译或消息的伪造。 l 基本术语1. 消息被称为明文(Plaintext)。用某

2、种方法伪装消息以隐藏它的内容的过程称为加密(Encryption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)。2. 对明文进行加密操作的人员称作加密员或密码员(Cryptographer)。3. 密码算法(Cryptography Algorithm)：是用于加密和解密的数学函数。4. 密码员对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm)。5. 所传送消息的预定对象称为接收者(Receiver)。6. 接收者对密文解密所采用的一组规则称为解密算法(Decryption Algorithm

3、). 二、传统密码体制1、凯撒密表 2） 加解密过程示意图 加密和解密算法的操作通常都是在一组密钥的控制下进行的，分别称为加密密钥(EncryptionKey) 和解密密钥(Decryption Key)。Y加密机Alice解密机Bob密钥源Oscar安全信道XXK3） 加密通信的模型密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。4. 密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任

4、意kK,有一个加密算法eKE和相应的解密算法dKD，使得eK：P C 和dK ：C P 分别为加密解密函数，满足dk(ek(x)=x, 这里x P。 5. 密码算法分类-i按照保密的内容分：1）受限制的（restricted)算法：算法的保密性基于保持算法的秘密。2）基于密钥（key-based)的算法：算法的保密性基于对密钥的保密。6. 密码算法分类-ii基于密钥的算法，按照密钥的特点分类：对称密码算法（symmetric cipher)：又称传统密码算法（conventional cipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法

5、。非对称密钥算法（asymmetric cipher)：加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-key cipher) 。公开密钥算法用一个密钥进行加密， 而用另一个进行解密。其中的加密密钥可以公开，又称公开密钥（publickey)，简称公钥。解密密钥必须保密，又称私人密钥（private key)私钥，简称私钥。7、 密码算法分类-iii1）按照明文的处理方法：分组密码（block cipher)：将明文分成固定长度的组，每个分组都用相同的密钥进行加密产生相同、输出也是固定长度的密文。n 流密码（stream cipher)：又称序列密码。序列密码每

6、次加密一位或一字节的明文，然后用相关但不同密钥加密产生相应的密文，相同的明文分组由于在明文序列中的位置不同对应的密文不同，也可以称为流密码。序列密码是手工和机械密码时代的主流。 密码学的历史l 密码学的起源和发展(1)三个阶段：1） 1949年之前，密码学是一门艺术；2） 19491975年，密码学成为科学；3） 1976年以后，密码学的新方向公钥密码学。 l 密码学的起源和发展(2)1949年之前：古典密码（classical cryptography) 密码学还不是科学，而是艺术。 出现一些密码算法和加密设备。 密码算法的基本手段(substitution &permutation)出现，

7、针对的是字符。 简单的密码分析手段出现。 l 密码学的起源隐写术(steganography)：通过隐藏消息的存在来保护消息。1） 隐形墨水；2） 字符格式的变化；3） 图像 l Example-1 (象形文字的修改)Modified Hieroglyphics, c. 1900 B.C.密码学的第一个例子是对标准书写符号的修改例如：古埃及法老坟墓上的文字思想：代替(substitution) Example-2 Caesar Cipher, c. 50 B.C.A B C D E F G X Y ZD E F G H I J A B C明文:Caesar cipher is a shift

8、substitution密文:FDHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQExample-3用布或羊皮纸缠在竿上写字、奴隶的头剃光，将消息刺在头上，等头发长好后上路等等。l 密码学的起源和发展(3) 1976年以后： 1976年Diffie & Hellman 提出了不对称密钥密码 1977年Rivest，Shamir & Adleman提出了RSA公钥算法 90年代逐步出现椭圆曲线等其他公钥算法，公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！ l 密码分析假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。这个假设称为Kerckhoff

9、原则。最常见的破解类型如下：1） 唯密文攻击：Oscar具有密文串y。2） 已知明文攻击： Oscar具有明文串X和相应的密文Y。3） 选择明文攻击：Oscar可获得对加密机的暂时访问， 因此他能选择 明文串x并构造出相应的密文串y。 4） 选择密文攻击：Oscar可暂时接近密码机，可选择密文串y，并构造出相应的明文x。这一切的目的在于破译出密钥或密文。密文加密机Alice解密机Bob加密密钥Oscar明文X解密密钥l 密码破译 密码破译的原则： 遵循观察与经验； 方法：采用归纳与演绎； 步骤：分析、假设、推测和证实； 三大要素： 语言的频率特征： e 连接特征： q u, I e x, 重复

10、特征： th, tion , tiousl 密码算法的安全性1）无条件安全（Unconditionallysecure）无论破译者有多少密文，他也无法解出对应的明文，即使他解出了，他也无法验证结果的正确性。2）计算上安全（Computationallysecure） 破译的代价超出信息本身的价值； 破译的时间超出了信息的有效期； l 对称密码分析的两个基本方法1）穷举法(Exhaustive Attack method)，又称为强力法(Brute-force method).。完全试凑法(complete trial-and error method)； 这是对截获的密文依次用各种可能的密钥破

11、译。 对所有可能的明文加密直到与截获的密文一致为止。2） 分析法 系统分析法（统计分析法）：利用明文的统计规律 确定性分析法 l 对称密码的两个基本运算1） 代替(Substitution )古埃及的原始密码（左方是密文，右方是相应的明文）2） 置换(Permutation) l 古典密码基于字符的密码1） 代替密码（substitution cipher)：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。（代替规则、密文所用字符、明文中被代替的基本单位）2） 置换密码(permutation cipher)，又称换位密码（transposition

12、cipher)：明文的字母保持相同，但顺序被打乱了。 l 代替密码 简单代替密码（simple substitution cipher)，又称单字母密码（monoalphabetic cipher)：明文的一个字符用相应的一个密文字符代替，而且密文所用的字符与一般的明文所用字符属同一语言系统。 多字母密码（ployalphabetic cipher)：明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置。l 多字母代换密码可以用矩阵变换方便地描述多字母代换密码，有时又称起为矩阵变换密码。单字母密码l 单表代换密码 移位（shift ）密码 密钥短语（Key Word)密码 任意的单表代替

13、密码1、移位密码算法l 设P=C=K=Z/(26)，对kK，定义ek(x)=x+k (mod 26)=y C同时dk(y)=y-k (mod 26)实际算法为：xP 有e3（x）= x+3(mod 26)= y同时有，d3(y)=y-3 (mod 26)移位密码分析给定加密的消息：PHHW PH DIWHU WKH WRJD SDUWB1） 加解密算法已知2） 可能尝试的密钥只有25个(不包括0)通过强力攻击得到明文：meet me after the toga party.移位密码很容易受到唯密文攻击。2、任意的单表代替密码算法例：置换的对应关系为： ABCDEFGHIJKLMNOPQRST

14、UVWXYZ IDMEFZOAPHXBSCQRLTUYJVNWGK试用单表代换密码以为密钥对明文消息UNIVERSITY加密，然后对密文解密。加密：（u）（n）（i）（v）（e）（r）（s）（i）（t）（y）=JCPVFTUPYG-1的对应关系：ABCDEFGHIJKLMNOPQRSTUVWXYZHLNBDEYJAUZQCWGIOPMRSVXKTF构造方法：以西文单词为密钥的换字表 例如：取atmosphere为密钥，首先找出其中发生重复的字母，去掉重复字母e，成为atmospher. 其次，字母一共10个，从第11个字母开始，用atmosphere按顺序进行代替配置。 然后把其余17个字母按

15、自然顺序接在后面。以atmosphere为密钥的换字表密码破译l 密码设计是利用数学来构造密码；l 密码分析除了依靠数学、工程背景、语言学知识外，还要靠经验、统计、测试、眼力、直觉判断力有时还要靠点运气；l 密码破译的原则：遵循观察与经验；l 方法:采用归纳与演绎；l 步骤:分析、假设、推测和证实；1、单表替换密码的破译语言的统计特性： 语言的频率特征 连接特征 重复特征1）频率特征 在各种语言中，各个字母的使用次数是不一样的，有的偏高，有的偏低，这种现象叫偏用现象。 对英文的任何一篇文章，一个字母在该文章中出现的次数称作这个字母（在这篇文章中）的频数。 一个字母的频数除以文章的字母总数，就得

16、到字母的使用频率。l 英文字母的普遍使用频率美国密码学家W.F.Friedman在调查了大量英文资料后，得出英文字母的普遍使用规律。 英文单字母的相对频率表字母频率字母频率字母频率R0.0677I0.0627Z0.0008Q0.0012H0.0528Y0.0199P0.0199G0.0199X0.0017O0.0797F0.0289W0.0149N0.0707E0.1304V0.0092M0.0249D0.0378U0.0249L0.0339C0.0279T0.1045K0.0042B0.0139S0.0607J0.0013A 0.0856 l 特殊的特征 开头结尾特征： 有些文章的开头和结尾

17、受到固定格式的限制；有时文章中间的某些特定部位，某些字母也会出现较高的使用频率。l 频度最高的前30个双字母 TH HE IN ER AN RE ED ON ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET IT AR TE SE HI OF l 频度最高的前20个三字母 THE ING AND HER ERE ENT THA NTH WAS ETH FOR DTH HAT SHE ION INT HIS STH ERS VER l 其它频率特征 the 的使用频率最高，是ING的三倍，若把the去掉，t在第II类中排在最后，h会降为第III类，t

18、h和he也不是常出现的字母组了； 一半的单词以e s d t 结尾； 一半的单词以t a s w开头； Y的使用频率90%都集中在单词的结尾； 2）、连接特征 后连接：q u 前连接： x的前面总是i, e很少是o和a 间断连接：在e和e之间，r的出现频率最高 3）、重复特征 两个字符以上的字符串重复出现的现象，叫做语言的重复特征。 th tion tiousl example UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUP

19、ZHMDJUDTMOHMQ确定字母的相对频率 双字母频率 UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ 最常见的双字母组合ZW，Z 猜测其为T，W对应为H，P猜测其为E 三字母组合 UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUP

20、ZHMDJUDTMOHMQ ZWP THE ZWSZ TH T S A 进一步分析-1 进一步分析-2 进一步分析-3 It was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow.单表密码破译小结假定，推翻，再假定，再推翻，直至破译 对密文字母的频数、使用频率和连接次数进行统计； 根据了解到的密码编制人员的语言修养，以及手中掌握的密文的统计规律，多方比较，对明文的语种和密码

21、种类作出假定； 将假定语种的字母频率与密文字母频率进行比较； 首先找出密文中频率最高的字母； 根据字母的频率特征、连接特征、重复特征，从最明显的单词或字母开始，试探进行。 总结 二、对抗频率分析的办法l 多名或同音代替密码l 多表代替密码l 多字母代替密码 1、多名代替密码与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母。例如， A可能对应于5、13、25；B可能对应于7、9、31、42当对字母的赋值个数与字母出现频率成比例时。这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。然而，若明文字母的其它统计信息在密文中仍很明显时，那么同音代替密码仍然是可破译的。 2、多表代替密码多表代替密码： 是以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。 非周期多表代替密码：代换表是非周期的无限序列一次一密密码（one-time padding)：对每个明文每次采用不同的代换表。 周期多表代替密码：代换表个数有限，重复使用。维吉尼亚（Vigenere)密码Vigenre cipher (1858)滚动密钥密码对于周期代换密码，当密钥的长度d和明文一样长时，就成为滚动密钥密码。Vigenre