保密通信的理论基础课件.ppt

1、东南大学移动通信国家重点实验室第十四章第十四章保密通信的基本理论保密通信的基本理论 第1页，共83页。东南大学移动通信国家重点实验室本章内容提要本章内容提要保密通信的技术体制及数学模型保密通信的技术体制及数学模型信息保密技术的基础知识信息保密技术的基础知识数据加密数据加密DES流加密技术流加密技术公共密钥密码系统公共密钥密码系统PGP标准标准通信网络安全的加密方案通信网络安全的加密方案第2页，共83页。东南大学移动通信国家重点实验室基本概念和术语基本概念和术语 线路加密和信息加密的基本概念线路加密和信息加密的基本概念 密码学的基本概念密码学的基本概念 密码编码密码编码是密码的设计学是密码的设计

2、学 密码分析密码分析则是在则是在未知密钥未知密钥（Key）的情况下从）的情况下从密文密文推测出推测出明文明文。密码编码和密码分析合称为密码编码和密码分析合称为密码学。密码学。术语术语密码密码和和加密加密（Encrypt）指在发端对消息进行变换，）指在发端对消息进行变换，破解密码破解密码和和解密解密（Decrypt）则指在收端对接收消息进行反变换。）则指在收端对接收消息进行反变换。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.1 加密和解密过程的模型加密和解密过程的模型 第3页，共83页。东南大学移动通信国家重点实验室 M 截取 发端 收端 明文M 密文C 明文 公共

3、信道 M=DK=EK1(C)K 安全信道 K 密钥 密码破译 加密算法EK 解密算法DK 图图14.1 加密信道模型加密信道模型 第4页，共83页。东南大学移动通信国家重点实验室 密码信道模型密码信道模型 明码文本明码文本M利用利用密钥密钥,通过某种通过某种可逆变换可逆变换EK加密成加密成密文密文C，即即C=EK（M）。）。密文通过密文通过不安全的或公共信道不安全的或公共信道进行传输。进行传输。在传输过程中可能出现在传输过程中可能出现密文截取密文截取。截取密文又称为截取密文又称为攻击或入侵攻击或入侵。当合法用户得到当合法用户得到C后，用后，用逆变换逆变换DK=EK-1进行解密得到原来进行解密得

4、到原来的明码文本消息，即的明码文本消息，即(14.1)参数参数K是由码元或字符组成的密钥，它是由码元或字符组成的密钥，它规定了密码变换集合中特规定了密码变换集合中特定的一种加密变换定的一种加密变换EK。MMEECDKKK)()(114.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.1 加密和解密过程的模型加密和解密过程的模型 第5页，共83页。东南大学移动通信国家重点实验室安全性能安全性能 密码系统安全性密码系统安全性从根本上依赖于整个加密过程的安全性从根本上依赖于整个加密过程的安全性。但系统最终发展是为了使加密变换或运算法则的普遍特性但系统最终发展是为了使加密变换或运算

5、法则的普遍特性能够能够公开表示公开表示，因为系统的安全性依赖于特定的密钥。，因为系统的安全性依赖于特定的密钥。密钥随待加密的明码文本和需解密的加密文本同时提供（密钥随待加密的明码文本和需解密的加密文本同时提供（加密加密密钥和解密密钥密钥和解密密钥）。）。在大多数密码系统中，拥有密钥者可以同时加解密消息。在大多数密码系统中，拥有密钥者可以同时加解密消息。密钥通过安全信道传送给合法用户群密钥通过安全信道传送给合法用户群。在大量的传送中密钥是不变的，密码分析学的目的就是在不知道密在大量的传送中密钥是不变的，密码分析学的目的就是在不知道密钥的情况下，钥的情况下，对从公共信道中获得的密文进行分析从而得到

6、对从公共信道中获得的密文进行分析从而得到对明文的推测对明文的推测。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.1 加密和解密过程的模型加密和解密过程的模型 第6页，共83页。东南大学移动通信国家重点实验室密码体制密码体制从得到的密文序列的结构来从得到的密文序列的结构来划分，密码体制分成两个基划分，密码体制分成两个基本的类型：本的类型：数据流加密数据流加密和和分分组加密组加密。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.1 加密和解密过程的模型加密和解密过程的模型 第7页，共83页。东南大学移动通信国家重点实验室数据流加密数据流加密流加

7、密流加密类似于卷积编码类似于卷积编码，将明文，将明文M看成是连续的看成是连续的比特流比特流m1m2，每个明文比特，每个明文比特mi被符号序列被符号序列（密钥流）中的第（密钥流）中的第i位元素位元素ki加密，即加密，即 14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.1 加密和解密过程的模型加密和解密过程的模型)()(2211)(mkmkKEECE 其中符号序列是由密钥产生的。其中符号序列是由密钥产生的。如果密钥流每隔如果密钥流每隔p个字符重复自身一次，那么加密过程个字符重复自身一次，那么加密过程是是周期性周期性的，否则就是的，否则就是非周期性非周期性的。的。第8页，共

8、83页。东南大学移动通信国家重点实验室发端 收端 ki ki mi ci ci mi 明文序列 密文序列 明文序列 密钥序列产生器 密钥序列产生器 14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.1 加密和解密过程的模型加密和解密过程的模型 流加密的原理如图流加密的原理如图14.2所示。所示。在发端进行模在发端进行模2运算，得到运算，得到 (14.2)收端对收端对ci的解密算法为的解密算法为 iiikikmmEci)(iiiiiiikmkkmkccDi)(14.3)图图14.2 流加密原理流加密原理 第9页，共83页。东南大学移动通信国家重点实验室分组加密分组加密 明

9、文被分为固定大小的块，明文被分为固定大小的块，每块独立加密每块独立加密。对每个相同的密钥，每个明文分组加密后的密码块都是一样对每个相同的密钥，每个明文分组加密后的密码块都是一样的，的，与分组编码相似与分组编码相似。分组加密分组加密不需要同步不需要同步，因此在分组交换网中得到广泛的应，因此在分组交换网中得到广泛的应用。用。分组加密的原理如图分组加密的原理如图14.3所示。所示。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.1 加密和解密过程的模型加密和解密过程的模型 第10页，共83页。东南大学移动通信国家重点实验室 图14.3 分组加密原理发端 收端 明文 密文 密

10、钥 密文 明文 输入 加密算法 n 比特 n 比特 输出 输入 解密算法 n 比特 n 比特 输出 第11页，共83页。东南大学移动通信国家重点实验室 对密码系统的主要要求对密码系统的主要要求 为所有拥有密钥的合法用户提供为所有拥有密钥的合法用户提供简单廉价简单廉价的加解密方法。的加解密方法。确保在没有密钥情况下，密码确保在没有密钥情况下，密码破译者对明文的估计十分困难且代价破译者对明文的估计十分困难且代价高昂高昂。对加密方案的性能要求通常与信道编码方案不同对加密方案的性能要求通常与信道编码方案不同 例如，在加密过程中例如，在加密过程中明文数据决不能在密码中直接出现明文数据决不能在密码中直接出

11、现；但在信道；但在信道编码中，码通常是由未变换的编码中，码通常是由未变换的消息和校验位组成的系统码消息和校验位组成的系统码。又如，又如，错误传播错误传播是密码系统通常要求达到的特性，因为这使得非法是密码系统通常要求达到的特性，因为这使得非法用户很难成功侦听；但在信道编码中，则希望系统能尽可能的纠正用户很难成功侦听；但在信道编码中，则希望系统能尽可能的纠正错误以使输出能少受输入错误的影响。错误以使输出能少受输入错误的影响。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.1 加密和解密过程的模型加密和解密过程的模型 第12页，共83页。东南大学移动通信国家重点实验室 攻击

12、的类型攻击的类型 按照截取密文的方式，攻击分为密文攻击、已知明文攻击和选择性按照截取密文的方式，攻击分为密文攻击、已知明文攻击和选择性明文攻击。明文攻击。密文攻击：密文攻击：是对系统的密码破解威胁最弱的一类攻击。破解者掌握是对系统的密码破解威胁最弱的一类攻击。破解者掌握一些关于常规系统和消息语言的知识，但惟一有价值的数据就是从一些关于常规系统和消息语言的知识，但惟一有价值的数据就是从公共信道截获的密文。公共信道截获的密文。已知明文攻击：已知明文攻击：是一种严重威胁系统安全的攻击类型，它需要是一种严重威胁系统安全的攻击类型，它需要知道明文和对应的密文信息。通信系统必须设计为能够抵御已知道明文和对

13、应的密文信息。通信系统必须设计为能够抵御已知明文攻击才被认为是安全的。知明文攻击才被认为是安全的。选择性明文攻击：选择性明文攻击：当密码破译者能够选择明文时，这种威胁称当密码破译者能够选择明文时，这种威胁称为选择性明文攻击。为选择性明文攻击。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.2 攻击的类型及密码系统安全性攻击的类型及密码系统安全性 第13页，共83页。东南大学移动通信国家重点实验室密码系统安全性密码系统安全性密码体制分为密码体制分为绝对安全系统和计算性安全系统绝对安全系统和计算性安全系统。绝对安全系统：绝对安全系统：也称为也称为理论上不可破译理论上不可破

14、译的系统，就是对密码破译的系统，就是对密码破译者来说，不管它拥有多么强大的计算能力，只要获得的情报内容不者来说，不管它拥有多么强大的计算能力，只要获得的情报内容不充分就无法确定加密和解密变换充分就无法确定加密和解密变换 计算性安全系统：计算性安全系统：如果一个密码体制中的密码不能被可以使如果一个密码体制中的密码不能被可以使用的计算资源破译，则称它为计算性安全系统。用的计算资源破译，则称它为计算性安全系统。大多数密码系统规范依赖于大多数密码系统规范依赖于“x年计算性安全年计算性安全”，它意味着，它意味着密码破译者在采用密码破译者在采用当前科技水平的当前科技水平的电脑的有利条件下，用电脑的有利条件

15、下，用x年时年时间有可能破坏系统的安全，但绝不可能少于间有可能破坏系统的安全，但绝不可能少于x年。年。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.2 攻击的类型及密码系统安全性攻击的类型及密码系统安全性 第14页，共83页。东南大学移动通信国家重点实验室 恺撒密码恺撒密码 例如将明文循环后移例如将明文循环后移3位构成密文，如下所示：位构成密文，如下所示：明文：明文：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

16、Z A B C 当使用恺撒字母表时，消息当使用恺撒字母表时，消息“arrive at four”的加密如下：的加密如下：明文：明文：ARRIV ERAT FO UR 密文：密文：D UUL YH UDW IRXU 解密密钥就是简单的字母移位数，本例即解密密钥就是简单的字母移位数，本例即3。选择一个新的密钥，码本也随之变化。选择一个新的密钥，码本也随之变化。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.3 常规密码常规密码 第15页，共83页。东南大学移动通信国家重点实验室 Polybius方阵方阵 首先将字母I和J合并在一起看作一个字符，这是因为选择I、J中的哪一个

17、最终可以通过消息的上下文来确定。由此，合并的25个字母排列成55的阵列。任意字符的加密是通过选择相应的行-列（或列-行）数字对完成的。消息的加密如下：明文：A R R I V E R A TF OU R 密文：11 24 24 42 15 51 24 11 44 12 43 54 24 通过重新排列通过重新排列55阵列中阵列中25个字符，密文也随之发生变化。个字符，密文也随之发生变化。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.3 常规密码常规密码 第16页，共83页。东南大学移动通信国家重点实验室 Polybius方阵方阵如图14.4所示。图14.4 Polyb

18、ius 方阵1 2 3 4 5 1 A B C D E 2 F G H IJ K 3 L M N O P 4 Q R S T U 5 V W X Y Z 14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.3 常规密码常规密码 第17页，共83页。东南大学移动通信国家重点实验室 Trithemius累进密钥法累进密钥法 Trithemius累进密钥法是一种多字符密码多字符密码。标有移位0的行，其字母排列与正常情况相同，即不移位。下一行的字母向左循环移动一个字符。依此类推，每一行与前面一行相比，都向左循环移动一个字符，直每一行与前面一行相比，都向左循环移动一个字符，直到字母

19、被全部循环移位到字母被全部循环移位。下图显示的是Trithemius累进密钥法的例子。例如利用该字母表，密文的第一个字母从左移一位的行选取，密文的第二个字母从左移两位的行选取，依此类推：明文：ARR IVERATFOUR 密文：B T U M A K Y I C P Z G E14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.3 常规密码常规密码 第18页，共83页。东南大学移动通信国家重点实验室明 文：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 移 位：0 A B C D E F G H I J K L M

20、N O P Q R S T U V W X Y Z 1 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 A 2 C 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 3 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 4 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 D 5 F G H I J K L M N O P Q R S T U V W X Y Z A B C D E 6 G

21、H I J K L M N O P Q R S T U V W X Y Z A B C D E F 7 H I J K L M N O P Q R S T U V W X Y Z A B C D E F G 8 I J K L M N O P Q R S T U V W X Y Z A B C D E F G H 9 J K L M N O P Q R S T U V W X Y Z A B C D E F G H I 1 0 K L M N O P Q R S T U V W X Y Z A B C D E F G H I J 1 1 L M N O P Q R S T U V W X Y

22、Z A B C D E F G H I J K 1 2 M N O P Q R S T U V W X Y Z A B C D E F G H I J K L 1 3 N O P Q R S T U V W X Y Z A B C D E F G H I J K L M 1 4 O P Q R S T U V W X Y Z A B C D E F G H I J K L M N 1 5 P Q R S T U V W X Y Z A B C D E F G H I J K L M N O 1 6 Q R S T U V W X Y Z A B C D E F G H I J K L M N

23、O P 1 7 R S T U V W X Y Z A B C D E F G H I J K L M N O P Q 1 8 S T U V W X Y Z A B C D E F G H I J K L M N O P Q R 1 9 T U V W X Y Z A B C D E F G H I J K L M N O P Q R S 2 0 U V W X Y Z A B C D E F G H I J K L M N O P Q R S T 2 1 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 2 2 W X Y Z A B

24、C D E F G H I J K L M N O P Q R S T U V 2 3 X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 2 4 Y Z A B C D E F G H I J K L M N O P Q R S T U V W X 2 5 Z 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 第19页，共83页。东南大学移动通信国家重点实验室 Vigenere密钥法密钥法 是利用Trithemius累进密钥得到一种加密法。使用一个关键字来表示消息中每个连续字母加密和解密所使

25、用的行。比如假定关键字为“NEW”，加密如下：关键字：N E W N E W N E W N E W N 明文：AR RI V ERAT FO U R 密文：N V N V Z A E E P S S Q E 关键字中的N表示第一个明文字符使用“N”开头的行，即第13移位行，依此类推。14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.3 常规密码常规密码 第20页，共83页。东南大学移动通信国家重点实验室14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.3 常规密码常规密码 Vigenere自动明文密钥自动明文密钥法法是Vigenere密钥法的一

26、种变形。以一个字母或单词作为初始启动密钥，由初始启动密钥决定明文的第一个或开头几个字符使用的行数，如前所述。接着，明文字符自身被用作关键字。例如使用G作为初始启动密钥的加密如下：关键字：G A R R I V E R A T F O U 明文：A R R I V E R A T F O U R 密文：G R I Z D Z V R T Y T I L自动明文密钥法在加密过程中引入了反馈。通过反馈，密文的选择由消息内容来决定。第21页，共83页。东南大学移动通信国家重点实验室14.1保密通信的技术体制及数学模型保密通信的技术体制及数学模型14.1.3 常规密码常规密码 Vigenere自动密文密

27、钥法自动密文密钥法在使用初始启动密钥加密后，后继字符的加密由前面的密文而不是明文来决定。例如仍用字母G作为初始启动密钥：关键字：G G X O W R M D D W B P J 明文：A R R I V E R A T F O U R 密文：G X O W R M D D W B P J A可改变明文字符统计特性，使破译者很难使用统计分析。缺点是密文中包含关键字，它们将暴露在公共信道上。发现非重复关键字序列可通过消息本身或消息函数来产生。按照现在的标准来衡量，这些早期的常规密码体制都不很安全，按照现在的标准来衡量，这些早期的常规密码体制都不很安全，目前它们通常被用作复杂编码的中间步骤。目前它

28、们通常被用作复杂编码的中间步骤。第22页，共83页。东南大学移动通信国家重点实验室 代码的实际码率或语言的实际熵定义为长度为代码的实际码率或语言的实际熵定义为长度为N的消息中每字符包的消息中每字符包含的平均信息比特数，表示为含的平均信息比特数，表示为(14.4)其中其中H(X)是消息熵，即最佳编码消息的比特数。当是消息熵，即最佳编码消息的比特数。当N很大时，很大时，据估计，中文的据估计，中文的r值不大于值不大于5比特比特/汉字，英文的汉字，英文的r值约在值约在1.0到到1.5比特比特/字符之间。字符之间。绝对码率或语言的最大熵定义为假设所有可能字符序列等概情绝对码率或语言的最大熵定义为假设所有

29、可能字符序列等概情况下，每字符包含的最大信息比特数，用况下，每字符包含的最大信息比特数，用r表示：表示：r=lbL (14.5)其中其中L是语言包含的字符数。中文的绝对码率或最大熵约为是语言包含的字符数。中文的绝对码率或最大熵约为13.9比特比特/汉字，对英文字母，汉字，对英文字母，r=lb 26=4.7比特比特/字符。字符。NHr)(X14.2信息保密技术的基础知识信息保密技术的基础知识14.2.1 基本度量基本度量 第23页，共83页。东南大学移动通信国家重点实验室 代码的冗余度用实际码率和绝对码率来定义：D=r r (14.6)英语的r=4.7比特/字符，r=1.5比特/字符，D=3.2

30、，比率D/r=68%就是英语冗余度的度量。中文的冗余度的度量约为80%。疑义度定义为在给定Y条件下X的条件熵。条件熵定义为：(14.7)疑义度可以认为是在收到Y后消息X的不确定度。密码破译者希望随着截获密文Y的增加，H(X|Y)接近于零。14.2信息保密技术的基础知识信息保密技术的基础知识14.2.1 基本度量基本度量 XYYX,YXYXYYXYXYX)|(1lb)|()()|(lb),()|(PPPPPH第24页，共83页。东南大学移动通信国家重点实验室 在一个密码系统中，如果消息数、密钥数以及密文变换数都是相在一个密码系统中，如果消息数、密钥数以及密文变换数都是相同的，当且仅当满足下面两个

31、条件时，即被称为具有同的，当且仅当满足下面两个条件时，即被称为具有理想保密性理想保密性：(1)每个明文变换成密文时只用一次密钥转换。每个明文变换成密文时只用一次密钥转换。(2)所有的密钥等概。所有的密钥等概。定义定义14.1考虑一个有限消息空间考虑一个有限消息空间M=M0,M1,MN 1 和一个有限密和一个有限密文空间文空间C=C0,C1,CU 1。任何一个。任何一个Mi被发送的先验概率为被发送的先验概率为P(Mi)。假设收到的为。假设收到的为Cj，则发送，则发送Mi的后验概率为的后验概率为P(Mi|Cj)。若对。若对每个消息每个消息Mi和密码和密码Cj，后验概率与先验概率相同就称系统具有理，

32、后验概率与先验概率相同就称系统具有理想保密性：想保密性：P(Mi|Cj)=P(Mi)(14.8)因此截获因此截获Cj并未得到更多信息以确定发送的是哪个消息。并未得到更多信息以确定发送的是哪个消息。14.2信息保密技术的基础知识信息保密技术的基础知识14.2.2 理想保密性理想保密性 第25页，共83页。东南大学移动通信国家重点实验室 例如，在图14.6所示的一个密码系统中，消息空间M=M0,M1,M2,M3，密文空间C=C0,C1,C2,C3，密钥空间K=K0,K1,K2,K3，消息数N和密文数U相等，即N=U=4，P(Mi)=P(Cj)=1/4。加密变换过程如下：NjisMTCiKsj模 )

33、()(14.2信息保密技术的基础知识信息保密技术的基础知识14.2.2 理想保密性理想保密性(14.9)其中TKj表示使用密钥Kj的变换，x模y定义为x除以y后的取余运算。因此s=1,2,3,4。破译者截获消息Cs=C0,C1,C2,C3中的一个，没有办法确定到底是4个密钥中的那一个，因此不能确定正确的消息是M0,M1,M2还是M3。第26页，共83页。东南大学移动通信国家重点实验室 图14.6 具有理想保密性的系统示例 密 钥 P(M0)=1/4 M0 0 C0 1 2 3 3 P(M1)=1/4 M1 0 C1 1 2 2 3 P(M2)=1/4 M2 0 C2 1 1 2 3 P(M3)

34、=1/4 M3 0 C3 明 文 消 息 密 文 消 息 第27页，共83页。东南大学移动通信国家重点实验室 如果密码系统不满足理想保密性的两个条件，则对于给定的Cj，将会有某个消息Mi，没有密钥可以将Cj解密为Mi，即即对某些对某些i和和j，P(Mi|Cj)=0。密码破译者就可以删除一些确可以删除一些确定的明文消息以简化任务定的明文消息以简化任务。在具有理想保密性的系统中，互异的密钥数量至少应等于可互异的密钥数量至少应等于可能的消息数量能的消息数量，因此，如果消息具有无限的长度，要达到理想保密性，就需要无限多的密钥，这在实际系统中并不可行。当密钥空间小于消息空间时，从理论上说，该密码系统就存

35、在被当密钥空间小于消息空间时，从理论上说，该密码系统就存在被破译的可能性。破译的可能性。14.2信息保密技术的基础知识信息保密技术的基础知识14.2.2 理想保密性理想保密性 第28页，共83页。东南大学移动通信国家重点实验室 例例14.1 有一个用恺撒密码加密的29字符的密文：G R O B O K B O D R O R O B Y O C Y P I O C D O B I O K B其中每个字符被移了K个位置，1 K 25。试破译此密文。解解 由于由29个字符组成消息，其有意义的组合有无数个，大于所有可能大于所有可能的密钥数的密钥数25个，因此理想保密性将无法实现个，因此理想保密性将无

36、法实现。在图14.5的Trithemius累进密钥表中，明文字符随行数K的增加而被更高序的字母代替。在密文分析中，将这个过程倒转，使每个密文字符被降序的字符代替。尝试从1到25的所有密钥，如图14.7所示，结果是只有一个密钥K=10能出现有意义的消息：WHERE ARE THE HEROES OF YESTERYEAR(加入了空格)，因此密码被破译。14.2信息保密技术的基础知识信息保密技术的基础知识14.2.2 理想保密性理想保密性 第29页，共83页。东南大学移动通信国家重点实验室密钥 文本 0 G R O B O K B O D R O R O B Y O C Y P I O C D O

37、 B I O K B 1 F Q N A N J A N C Q N Q N A X N B X O H N B C N A H N J A 2 E P M Z M I Z M B P M P M Z W M A W N G M A B M Z G M I Z 3 D O L Y L H Y L A O L O L Y V L Z V M F L Z A L Y F L H Y 4 C N K X K G X K Z N K N K X U K Y U L E K Y Z K X E K G X 5 B M J W J F W J Y M J M J W T J X T K D J X Y J

38、 W D J F W 6 A L I V I E V I X L I L I V S I W S J C I W X I V C I E V 7 Z K H U H D U H W K H K H U R H V R I B H V W H U B H D U 8 Y J G T G C T G V J G J G T Q G U Q H A G U V G T A G C T 9 X I F S F B S F U I F I F S P F T P G Z F T U F S Z F B S 10 W H E R E A R E T H E H E R O E S O F Y E S T

39、E R Y E A R 11 V G D Q D Z Q D S G D G D Q N D R N E X D R S D Q X D Z Q 12 U F C P C Y P C R F C F C P M C Q M D W C Q R C P W C Y P 13 T E B O B X O B Q E B E B O L B P L C V B P Q B O V B X O 14 S D A N A W N A P D A D A N K A O K B U A O P A N U A W N 15 R C Z W Z V M Z O C Z C Z M J Z N J A T Z

40、 N O Z M T Z V M 16 Q B Y L Y U L Y N B Y B Y L I Y M I Z S Y M N Y L S Y Y L 17 P A X K X T K X M A X A X K H X L H Y R X L M X K R X T K 18 O Z W J W S J W L Z W Z W J G W K G X Q W K L W J Q W S J 19 N Y V I V R I V K Y V Y V I F V J F W P V J K V I P V R I 20 M X U H U Q H U J X U X U H E U I E

41、V O U I J U H O U Q H 21 L W T G T P G T I W T W T G D T H D U N T H I T G N T P G 22 K V S F S O F S H V S V S F C S G C T M S G H S F M S O F 23 J U R E R N E R G U R U R E B R F B S L R F G R E L R N E 24 I T Q D Q M D Q F T Q T Q D A Q E A R K Q E F Q D K Q M D 25 H S P C P L C P E S P S P C Z P

42、 D Z Q J P D E P C J P L C 图14.7 密钥空间小于消息空间时密码系统破译 第30页，共83页。东南大学移动通信国家重点实验室14.2信息保密技术的基础知识信息保密技术的基础知识14.2.2 理想保密性理想保密性 如果修改例14.1的密钥空间，可生成具有理想保密性的密码。在新的密码系统中，每个消息字符用随机选择的密钥加密。密钥K由序列k1，k2，k29组成，ki是落在1,25内的随机整数，表明用于第i个字符的偏移量。共有(25)29个不同的密钥序列。此时29字符密文可以对应任何有意义的明文。比如，当密钥为2,4,8,16,6,18,20,时，密文可对应如下明文（已加入

43、空格）ENGLISH AND FRENCH ARE SPOKEN HERE。由于在这个系统中截获密文并不能获得关于明文消息的附加信息，因此具有理想保密性。第31页，共83页。东南大学移动通信国家重点实验室 当密钥数量有限时，密钥的疑义度H(K|C)通常接近于零，因此可以惟一确定密钥，从而破译密文系统。定义定义14.2 单一性距离N定义为使得密钥疑义度H(K|C)接近于0的密文的最小数量。表示为 (14.10)其中H(K)是密钥熵，D=r r 是代码的冗余度。已知单一性距离已知单一性距离N，密钥就可被惟一确定从而破解密文系统。，密钥就可被惟一确定从而破解密文系统。证明证明 假设每个明文和密文字符

44、均来自长为L的有限符号集。这样，长为N的可能消息数就是2rN个，r是绝对码率。将全部消息空间分为两类：有意义消息M1和无意义消息M2，由此，有意义消息数=2rN，无意义消息数=2rN2rN ，其中r为实际码率。DKHN)(14.2信息保密技术的基础知识信息保密技术的基础知识14.2.3 单一性距离单一性距离 第32页，共83页。东南大学移动通信国家重点实验室14.2信息保密技术的基础知识信息保密技术的基础知识14.2.3 单一性距离单一性距离(续)这两类消息的先验概率分别为P(M1)=2rN，P(M2)=0。假设共有2H(K)个可能的密钥，H(K)是密钥熵（密钥的比特数），且所有的密钥都是等概

45、的，即P(K)=1/2H(K)=2H(K)。对每个密钥K和密文C，解密操作DK(C)产生一个随机分布于所有2rN个可能消息（有意义或无意义）中的随机变量。因此，给定K和C，DK(C)等概地产生任意一个明文消息。对于加密操作 ，根据另外一个密钥Kj也能从消息Mi或其它消息如Mj生成Ci，此时就产生了错误解密：(14.11)密码破译者截获到Ci，但是由于不能挑选出正确的密钥从而无法破译系统。)(iKiMECi)()()(jKjKiKiMEMEMECjji第33页，共83页。东南大学移动通信国家重点实验室14.2信息保密技术的基础知识信息保密技术的基础知识14.2.3 单一性距离单一性距离(续)解密

46、一个特定的密文，每个正确的方法伴随着2H(K)1个错误的密钥。设每个密钥产生错误解密的概率都是P(F)因为每个有意义的明文消息都假定是等概的，所以错误解密的概率和得到有意义消息的概率是相同的，即(14.12)其中D=r r为代码的冗余度。错误解密的期望值是(14.13)DNNrrNrrNFP2222)(DNKHDNKHKHFPF)()()(2212)(12当N增加时，迅速减小。定义 (14.14)为临界点，在该点误解密的次数足够小，能够破解密文。此时的单一性距离N即为N=H(K)/D。证毕。F0)(lbDNKHF第34页，共83页。东南大学移动通信国家重点实验室14.2信息保密技术的基础知识信

47、息保密技术的基础知识14.2.3 单一性距离单一性距离 可见，如果H(K)比DN大很多，就有很多种有意义的破解方法，密码破译者能够判断哪种是正确消息的可能性较小。DN代表了为了破解密钥，可利用的等式数目，而H(K)表示未知的数目。当等式数目小于未知的密钥比特数，就无法找到确定的方法，系统是攻不破的。反之就可能找到确定方法，系统就再不能说是不可攻破的了，虽然系统仍然可能是计算性安全的。正是由于无意义解密占支配地位使得密码可以被破解。单一性距离的定义式显示了在加密前进行数据压缩的重要性。数据压缩去除了冗余，因此增加了单一性距离。对任意大小的密钥，理想的数据压缩将使D=0，N=。第35页，共83页。

48、东南大学移动通信国家重点实验室 例例14.2 给定密钥序列k1,k2,k29，每个ki都是从1,25中提取的随机整数，表示第i个字符的移位数，见图14.5。假设所有可能的密钥等概，计算英语文本加密系统的单一性距离。解解 共有(25)29种可能的密钥序列，且均等概分布。密钥熵：H(K)=lb(25)29=135比特 英语的绝对码率：r=lb26=4.7比特/字符 英语实际码率：r=1.5比特/字符 冗余：D=r r=3.2比特/字符 单一性距离：N=H(K)/D=135/3.2 43字符14.2信息保密技术的基础知识信息保密技术的基础知识14.2.3 单一性距离单一性距离 第36页，共83页。东

49、南大学移动通信国家重点实验室14.2信息保密技术的基础知识信息保密技术的基础知识14.2.3 单一性距离单一性距离 在例14.1中，对于29字符长的消息，使用同样的密钥序列得到理想保密性。而在这个例子中可以看到，如果有效的密文是43字符长（意味着某些密钥序列必须用两次），就可能得到惟一的解密。但是，这并没有给解密过程中的计算困难带来任何帮助。即使找到了破解密码所需的密文字符数，仍然可能因为运算量太大而无法破译。第37页，共83页。东南大学移动通信国家重点实验室 1949年，香农发表著名文章，论证了一般经典加密方法得一般经典加密方法得到的密文几乎都是可以破译的到的密文几乎都是可以破译的。密码学的

50、研究面临了严重的危机。但是从20世纪60年代开始，密码学又进入了一个新的发展时期。70年代后期，美国的数据加密标准（年代后期，美国的数据加密标准（DES,Data Encryption Standard）和公共密钥密码系统的出现，成）和公共密钥密码系统的出现，成为近代密码学发展史上的两个重要里程碑。为近代密码学发展史上的两个重要里程碑。90年代，PGP（Pretty Good Privacy）标准的出现，成当前文件加密的事实标准。14.3数据加密标准数据加密标准DES第38页，共83页。东南大学移动通信国家重点实验室 置换置换 置换是一种简单的加密方法，与在经典密码系统中用其他字母来代替原来的