《信息安全概论》课件第二章信息保密技术(1).ppt

1、第二章信息保密技术密码学的发展o 第一个阶段第一个阶段:1949:1949年以前年以前n 古典加密古典加密n 计算机技术出现以前计算机技术出现以前n 密码学作为一种技艺密码学作为一种技艺,而不是一门科学而不是一门科学o 第二个阶段第二个阶段:1949:1949年到年到19761976年年n 标志标志:Shannon:Shannon 发表发表”Communication Theory of ”Communication Theory of Secrecy System”Secrecy System”n 密码学进入了科学的轨道密码学进入了科学的轨道n 主要技术主要技术:单密钥的对称密钥加密算法单密

2、钥的对称密钥加密算法o 第三个阶段第三个阶段 :1976:1976年以后年以后n 标志标志 :Diffie,Hellman:Diffie,Hellman发表发表”New Dircetions in”New Dircetions in Cryptography”Cryptography”n 一种新的密码体制一种新的密码体制 :公开密钥体制公开密钥体制o 本章提示n 2.1 古典密码n 2.2 分组加密技术n 2.3 公钥加密技术n 2.4 流密码技术n 2.5 电子信封设计n 2.6 信息隐藏技术2.1 古典密码o 代换密码n 单表代换密码o 移位密码o 替换密码o 仿射密码n 多表代换密码o

3、Vigenre(维吉尼亚）密码o 置换密码常规密码系统模型消息源加密变换解密变换目的地秘密通道密钥源破译者加/解密原理描述 假设明文字母用P表示，密文字母用C表示,密钥用K表示,加密变换用E表示，解密变换用D表示，则有：o 1.加密原理 文字描述：C=Ek(p)o 2.解密原理 文字描述：p=Dk(C)加密变换EpC解密变换DpC名词解释1.明文（plaintext)未加密的信息。2.密文（ciphertext)已加密的信息。3.密钥（key)控制密码变换操作的符号序列，是保密的核心。4.加密（encryption）将明文变换成密文的过程。5.解密（decryption）将密文变换成明文的过程

4、。6.密码算法（cipher algorithm)密码算法是一些公式、法则或程序，是加密算法和解密算法的统称,是密码系统的核心。代换密码o令表示明文字母表，内有q个“字母”或“字符”，可以将抽象地表示为一个整数集o在加密时通常将明文消息划分成长为L的消息单元，称为明文组，以m表示，如 om也称作L报文，它可以看作是定义在 上的随机变量oL1为单字母报（1gram），L2为双字母报（digrams），L3为三字母报（trigrams）。这时明文空间为 。1,1,0qZq10,),(110LlZmmmmmqlLLqZ10,),(110LlZmmmmmLZZZZNlLqqqLq个LqZP 代换密码（

5、续）o 令表示q个“字母”或“字符”的密文字母表，抽象地可用整数集 表示o 密文单元或组为o c是定义在 上的随机变量。密文空间 o 一般地，明文和密文由同一字母表构成，即1,1,0qZq10,)(,(110LlZcLccccqlL个）LqZLqZC 代换密码（续）o代换密码可以看作是从 到 的映射。时 ，称作单字母代换，也称作流密码（Stream cipher）。时，称作多码代换，亦称分组密码（Block cipher）。o一般地，选择相同明文和密文字母表。此时，若 ,则代换映射是一一映射，密码无数据扩展。若 ,则有数据扩展，可将加密函数设计成一对多的映射，即明文组可以找到多于一个密文组来代

6、换，这称之为多名（或同音）代换密码（Homophonic substitution cipher）。若 ,则明文数据被压缩，此时代换映射不可能构成可逆映射，从而密文有时也就无法完全恢复出原明文消息，因此保密通信中必须要求 。但 的映射可以用在认证系统中。LqZLqZ1L1LLL LL LL LL LL 代换密码（续）o 在,q=q，L=1时，若对所有明文字母，都用一种固定的代换进行加密，则称这种密码为单表代换（Monoalphabetic substitute）。若用一个以上的代换表进行加密，这就称作多表代换（Polyalphabetic substitute）。o 这是古典密码中的两种重要体

7、制。还有一个常见的是多字母代换密码。单表代换密码o 单表代换密码是对明文的所有字母都用一个固定的明文字母表到密文字母表的映射，即 。令明文 ，则相应地密文为 o 几类常见的单表代换密码n 移位密码n 替换密码n 仿射密码o 单表代换密码不能非常有效地抵抗密码攻击，因为语言的特征仍能从密文中提取出来 qqZZf:10mmm)()()(1010mfmfccmec移位密码o 由于英文字符有26个字母，可以建立英文字母和模26的剩余之间的对应关系：ABCDEFGHIJ KLMN0 12345678910111213O PQ RS T UV W X Y Z141516171819202122232425

8、移位密码（续）o 对于英文文本，则明文、密文空间都可定义为 （很容易推广到n个字母的情况）。容易看出移位满足我们密码系统的定义，即 。26Z,)(xxxedkk对每个26Z设 定义 ，且。,250,26kZKCP对26mod)(kxxek26,26mod)(Zyxkyydk凯撒密码历史上最著名的移位密码就是凯撒密码。凯撒密码(Caesar cipher)（1）原理（明密对照表）明文：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（

9、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=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

10、)=(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-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

11、)替换密码o 定义设 ，密钥空间K由所有可能的26个符号0，1，.，25的置换组成。对每一个置换 ，定义 则，其中 的逆置换。26ZCP)()(xxe)()(1yyd是1o 置换 的表示为：o 替换密码的密钥是由26个字母的置换组成。这些置换的数目是26！，超过 ，是一个非常大的数。这样即使对现代计算机来说，穷举密钥搜索也是不可行的。显然，替换密码的密钥（26个元素的随机置换）太复杂而不容易记忆，因此实际中密钥句子常被使用。密钥句子中的字母被依次填入密文字母表（重复的字母只用一次），未用的字母按自然顺序排列。25242321025242321026100.4 仿射密码仿射密码o 加密函数为：n

12、 当1时，为移位密码o 仿射函数是双射 n 当且仅当gcd(a,26)=1时同余方程 对每个y有唯一的解 26,26mod)(Zbabaxxe)26(modybax仿射密码系统仿射密码系统o 设 ，且 对 定义 且 o 因为满足 ，gcd(a,26)=1的 只有12种候选，对参数 没有要求。所以仿射密码有 种可能的密钥。26ZCP1)26,gcd(:),(2626aZZbaKKbak),(26mod)(baxxe26mod)()(1byaydk),(26Zyx26Za3122612a多表代换密码 o 以一系列（两个以上）代换表依次对明文消息的字母进行代换的加密方法。o 令明文字母表为 ，为代换

13、序列，明文字母序列 ，则相应的密文字母序列为 。o 若f是非周期的无限序列，则相应的密码称为非周期多表代换密码。这类密码，对每个明文字母都采用不同的代换表（或密钥）进行加密，称作一次一密密码（One-time pad cipher）,这是一种理论上唯一不可破的密码 。qZ),(21fff 21xxx)()()()(2211xfxfxfxeck多表代换密码（续）o 实际应用中都采用周期多表代换密码。o 经典的多表代换密码有n Vigenren Beaufortn Running-Keyn Vernamn 轮转机（Rotor machine）等Vigenre密码o Vigenre密码是由法国密码学

14、家Blaise de Vigenre 于1858年提出的，它是一种以移位代换（当然也可以用一般的字母代换表）为基础的周期代换密码。设m是某固定的正整数，定义 ，对一个密钥 ，定义：且所有的运算都在 中。mZKCP)(26),(21mkkkk),(),(221121mmmkkxkxkxxxxe),(),(221121mmmkkykykyyyyd26Z例利用Vigenre密码，使用密钥word加密信息computer。明文：comp uter密钥：word word密文：ycds qhvu多字母代换密码Hill密码o 特点n 每次对 个字母进行代换，这样做的优点是容易将字母的自然频度隐蔽或均匀化而

15、有利于抗统计分析。o 算法 1L设m是某个固定的正整数，又设 ；对任意 ，定义 ，则其中，所有的运算都是在 中进行。mZCP)(2626ZmmK可逆阵，Kk xkxek)(1)(ykydk26Zo 注1：m1时，系统退化为单字母仿射代换密码，可见Hill密码是仿射密码体制的推广。o 注2：如果m2，可以将明文写为 密文写为 .是 的线性组合.若取 简记为 其中 为密钥.),(21xxx),(21yyy 21,yy21,xx21221178311xxyxxyxky 73811k置换密码o 置换密码的想法是保持明文字符未改变，但通过重排而更改他们位置，所以有时也称为换位密码（Transpositi

16、on Cipher）。o 算法 设m是某个固定的正整数,定义 ,且K由所有 的置换组成.对一个密钥 (即一个置换),定义其中,.mZCP)(26m,2,1),(),()()2()1(21mmxxxxxxe),(),()()2()1(21111mmyyyyyyd的逆置换是1置换密码举例例一栅栏式密码 美国南北战争时期（1861-1865年），军队中曾经使用过的“栅栏”式密码（rail fence cipher)。（1）原理明文：send help加密过程：s n h l e d e p密文：s n h l e d e p（2）算法描述将明文写成双轨的形式，然后按行的顺序书写得到密文。置换密码举例

17、o例二 矩阵置换o以矩阵形式排列明文o将明文逐行写入矩阵,然后逐列读出o密钥指出各列读出的顺序o如:明文abcdefghijklmnopqrstuvwxyzabo密钥为:4312567o dkry cjqx ahov bipw elsz fmta gnubabcdefghijklm nopqrstuvwxyzab解密与密码分析o Kerckhoff假设:攻击者已知加密算法o 解密是加密的逆过程，是指掌握密钥和密码算法的合法人员从密文恢复出明文的过程。密码分析则是指非法人员对密码的破译，而且破译以后不会告诉对方。o 共同点：“解密（脱密）”和“密码分析（密码破译）”都是设法将密文还原成明文。o

18、不同点：二者的前提是不同的，“解密（脱密）”掌握了密钥和密码体制，而密码分析（破译）则没有掌握密钥和密码体制。2.2 分组加密技术o 本节友情提示n 2.2.1基本概念n 2.2.2标准算法的介绍o DES算法o 国际数据加密算法（IDEA）o AES算法n 2.2.3分组密码的分析方法n 2.2.4分组密码的工作模式 2.2.1基本概念o 密码学中常见的有两种体制:n 对称密码体制(单钥密码体制)如果一个加密系统的加密密钥和解密密钥相同，或者虽然不相同，但是由其中的任意一个可以很容易地推导出另一个，即密钥是双方共享的,则该系统所采用的就是对称密码体制。n 非对称密码体制(公钥密码体制)o 分

19、组密码是指将处理的明文按照固定长度进行分组，加解密的处理在固定长度密钥的控制下，以一个分组为单位独立进行，得出一个固定长度的对应于明文分组的结果。属于对称密码体制的范畴。基本概念（续）o 在分组密码的设计中用代替、置换手段实现扩散和混淆功能。o 混淆 指加密算法的密文与明文及密钥关系十分复杂，无法从数学上描述，或从统计上去分析。o 扩散 指明文中的任一位以及密钥中的任一位，对全体密文位有影响。经由此种扩散作用，可以隐藏许多明文在统计上的特性，增加密码的安全 2.2.2标准算法的介绍o DES算法 o 国际数据加密算法（IDEA）o AES算法 DES加密算法的背景l发明人 美国IBM公司W.T

20、uchman 和 C.Meyer 1971-1972年研制成功。l基础 1967年美国Horst Feistel提出的理论l产生 美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。l标准化 DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（Data Encryption Standard），于1977年7月15日生效。DES加密算法的背景o 美国国家安全局（NSA,National Security Agency)参与了美国国家标准局制定数据加密标准

21、的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位。o 1979年，美国银行协会批准使用DES。o 1980年，DES成为美国标准化协会(ANSI)标准。o 1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作。DES算法描述o 为二进制编码数据设计的，可以对计算机数据进行密码保护的数学运算。o DES使用56位密钥对64位的数据块进行加密，并对64位的数据块进行16轮编码。在每轮编码时，一个48位的“每轮”密钥值由56位的“种子”密钥得出来。o DES算法的入口参数有三个：Key、Dat

22、a和Mode。n Key为8个字节共64位，是DES算法的工作密钥；n Data也为8个字节64位，是要被加密或被解密的数据；n Mode为DES的工作方式，有两种：加密或解密o 64位明文变换到64位密文，密钥64位，实际可用密钥长度为56位。DES算法框图 DES算法描述（续）o 初始换位的功能是把输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位，其置换规则见下表：58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 4

23、1 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7o例：设置换前的输入值为D1D2D3.D64，则经过初始置换后的结果为：L0=D58D50.D8；R0=D57D49.D7。DES算法描述（续）o逆置换正好是初始置的逆运算。【例】第1位经过初始置换后，处于第40位，而通过逆置 换，又将第40位换回到第1位，其逆置换规则如下表所示：40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45

24、 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25DES算法的一次迭代过程图DES算法描述（续）o 扩展置换为:32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1o P-盒置换为：16 7 20 21 29 12 28 17 1

25、15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25o在变换中用到的S1,S2.S8为选择函数，俗称为S-盒，是DES算法的核心。其功能是把6bit数据变为4bit数据。S1:14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 o在S1中，共有4行数据，命名为0，1、2、3行；每

26、行有16列，命名为0、1、2、3，.，14、15列。现设输入为：DD1D2D3D4D5D6 令：列D2D3D4D5 行D1D6然后在S1表中查得对应的数，以4位二进制表示，此即为选择函数S1的输出。1 0 1 1 0 0 102 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 71 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 82 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 03 15 12 8 2 4 9 1 7 5 11 3 14 1

27、0 0 6 130 0 1 0输出4位使用选择函数S1的例子输入6位S1密钥Ki(48bit)的生成算法 DES的破解o DES的实际密钥长度为56-bit，就目前计算机的计算机能力而言，DES不能抵抗对密钥的穷举搜索攻击。o 1997年1月28日，RSA数据安全公司在RSA安全年会上悬赏10000美金破解DES，克罗拉多州的程序员Verser在Inrernet上数万名志愿者的协作下用96天的时间找到了密钥长度为40-bit和48-bit的DES密钥。o 1998年7月电子边境基金会（EFF）使用一台价值25万美元的计算机在56小时之内破译了56-bit的DES。o 1999年1月电子边境基金会（EFF）通过互联网上的10万台计算机合作，仅用22小时15分就破解了56-bit的ES。o 不过这些破译的前提是，破译者能识别出破译的结不过这些破译的前提是，破译者能识别出破译的结果确实是明文，也即破译的结果必须容易辩认。如果明果确实是明文，也即破译的结果必须容易辩认。如果明文加密之前经过压缩等处理，辩认工作就比较困难。文加密之前经过压缩等处理，辩认工作就比较困难。DES算法的公开性与脆弱性o DES的两个主要弱点：n 密钥容量：56位不太可能提供足够的安全性n S盒：可能隐含有陷井（Hidden trapdoors）o DES的半公开性：S盒的设计原理至今未公布