第2讲-密码学的基本概念和理论基础课件.ppt

《第2讲-密码学的基本概念和理论基础课件.ppt》由会员分享，可在线阅读，更多相关《第2讲-密码学的基本概念和理论基础课件.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2讲讲 密码学的基本概密码学的基本概念和理论基础念和理论基础 案例：莫尔斯电码里的爱情案例：莫尔斯电码里的爱情v早已被新科技所取代的莫尔斯密码，却在中国的互联网世界里演绎早已被新科技所取代的莫尔斯密码，却在中国的互联网世界里演绎了一段费尽周折的爱情猜谜传奇。了一段费尽周折的爱情猜谜传奇。v一男子向一女子表白，女子却给了一段莫尔斯密码，以及很少的提一男子向一女子表白，女子却给了一段莫尔斯密码，以及很少的提示，并表示，破译这个密码，才答应和他约会。男子死活不得求解，示，并表示，破译这个密码，才答应和他约会。男子死活不得求解，又在百度贴吧里将密码贴出以求助网友。又在百度贴吧里将密码贴出以求助网友

2、。v电码如下电码如下：“*-/*-/-*/*-/*-/*-/-*/*-/*-/*-/-*/*-/*-/*-/-*/*-/-*/*-/*-/*-/-*/*-/”v“她唯一给我的提示就是这个是她唯一给我的提示就是这个是5层加密的密码，也就是说要破解层加密的密码，也就是说要破解5层密码才是答案。最终语言是英语。层密码才是答案。最终语言是英语。”v网友贴出了莫尔斯密码对照表，然后发现相应密码对应的数字组合网友贴出了莫尔斯密码对照表，然后发现相应密码对应的数字组合和英文字母组合分别是：和英文字母组合分别是：“4194418141634192622374”、“daiddahadafcdaibfbbcgd”

3、网友网友“片羿天使片羿天使”将莫尔斯密码对应的数字将莫尔斯密码对应的数字“41 94 41 81 41 63 41 92 62 23 74”转换成了手机键盘字母转换成了手机键盘字母,以以41为例，它为例，它对应的就是传统手机键盘上的对应的就是传统手机键盘上的“4”的第一个字母，的第一个字母，“94”则是则是“9”的第的第4个字母。个字母。这样片羿天使得到了第二步的答案：这样片羿天使得到了第二步的答案：“G Z G T G O G X N C S”。片羿天使说片羿天使说“因为因为QWE的格式是被世人所认可的，也就有的格式是被世人所认可的，也就有可能成为密码的码表。码表可能成为密码的码表。码表QW

4、E=ABC依次类推。依次类推。”按照按照这样的次序，上面的来自于手机键盘的字母，就转换到了这样的次序，上面的来自于手机键盘的字母，就转换到了第三步答案：第三步答案：“O T O E O I O U Y V L”。案例：莫尔斯电码里的爱情案例：莫尔斯电码里的爱情在第四步中，片羿天使用了包括在第四步中，片羿天使用了包括凯撒凯撒、乘法乘法等等方法，对等等方法，对第三步几乎可以看出来的答案进行了进一步的解码，最后第三步几乎可以看出来的答案进行了进一步的解码，最后发现只有发现只有栅栏密码栅栏密码才能读得通。片羿天使将这组字母分成才能读得通。片羿天使将这组字母分成了了“O T O E O I”和和“O U

5、 Y V L”两排，然后对插重组得两排，然后对插重组得到第四步的字母排列：到第四步的字母排列：“OOTUOYEVOLI”。第五步于第五步于 是变得最为简单起来，那便是将是变得最为简单起来，那便是将“OOTUOYEVOLI”倒序排列，即倒序排列，即“I LOVE YOU TOO”。案例：莫尔斯电码里的爱情案例：莫尔斯电码里的爱情2.1 基本概念基本概念2.1.1 2.1.1 什么是密码学什么是密码学v密码学是研究密码系统或通信安全的一门学科，分为密码学是研究密码系统或通信安全的一门学科，分为密码编密码编码学码学和和密码分析学密码分析学。v密码编码学是使得消息保密的学科密码编码学是使得消息保密的学

6、科v密码分析学实际要研究加密消息破译的学科密码分析学实际要研究加密消息破译的学科密码学的发展历史密码学的发展历史 v第第1阶段阶段：1949年以前。年以前。v第第2阶段阶段：从：从1949年到年到1975年。年。标志：标志：1949年年Shannon发表的发表的保密系统的信息理论保密系统的信息理论一一文。文。v第第3阶段阶段：1976年至今。年至今。标志：标志：1976年年Diffie和和Hellman发表了发表了密码学新方向密码学新方向一文。一文。Shannon模型模型 vX,明文明文（plain-text）：）：作为加密输入的原始信息。作为加密输入的原始信息。vY,密文密文（cipher-

7、text）：对明文变换的结果。）：对明文变换的结果。vE,加密加密（encrypt）：是一组含有参数的变换。）：是一组含有参数的变换。vD,解密解密（decrypt）：加密的逆变换。）：加密的逆变换。vZ,密钥密钥（key）：是参与加密解密变换的参数。）：是参与加密解密变换的参数。密码系统（密码系统（Cryptosystem）v定义定义:(密码体制）密码体制）它是一个五元组（它是一个五元组（P,C,K,E,D)满足条件：满足条件：（1）P是可能明文的有限集；（明文空间）是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）是可能密文的有限集；（密文空间）（3）K是一切可能密钥

8、构成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间）*（4）任意）任意 ,有一个加密算法有一个加密算法 和相应的解密算法和相应的解密算法 ，使得，使得 和和 分别为加密解密函分别为加密解密函数，满足数，满足 。密码体制的分类密码体制的分类 v几种不同的分类标准几种不同的分类标准 按按操作方式操作方式进行分类进行分类操作方式：是明文变换成密文的方法。操作方式：是明文变换成密文的方法。v替代操作、置换操作、复合操作。替代操作、置换操作、复合操作。按照按照使用密钥的数量使用密钥的数量进行分类进行分类v对称密钥（单密钥）。对称密钥（单密钥）。v公开密钥（双密钥）。公开密钥（双密钥）。按照

9、按照对明文的处理方法对明文的处理方法进行分类进行分类v流密码。流密码。v分组密码。分组密码。柯克霍夫斯柯克霍夫斯(Kerckhoffs)假设假设 v假定：假定：密码分析者知道对方所使用的密码系统密码分析者知道对方所使用的密码系统包括明文的统计特性、加密体制（操作方式、处理方法包括明文的统计特性、加密体制（操作方式、处理方法和加和加/解密算法解密算法）、密钥空间及其统计特性。）、密钥空间及其统计特性。不知道密钥。不知道密钥。v密码体制的安全性仅应依赖于对密钥的保密，而不应依赖于密码体制的安全性仅应依赖于对密钥的保密，而不应依赖于对算法的保密。只有在假设攻击者对密码算法有充分的研究，对算法的保密。

10、只有在假设攻击者对密码算法有充分的研究，并且拥有足够的计算资源的情况下仍然安全的密码才是安全并且拥有足够的计算资源的情况下仍然安全的密码才是安全的密码系统。的密码系统。v一切秘密寓于密钥之中一切秘密寓于密钥之中 密码分析密码分析 v密码分析密码分析：从密文推导出明文或密钥：从密文推导出明文或密钥。v密码分析：常用的方法有以下密码分析：常用的方法有以下4类：类：惟密文攻击惟密文攻击（cybertext only attack）：密码分析者有一）：密码分析者有一个或更多的用同一个密钥加密的密文，通过对这些截获个或更多的用同一个密钥加密的密文，通过对这些截获的密文进行分析得出明文或密钥的密文进行分析

11、得出明文或密钥已知明文攻击已知明文攻击（knownplaintext attack）：除要破译）：除要破译的密文外，密码分析者有一些明文和用同一密钥加密这的密文外，密码分析者有一些明文和用同一密钥加密这些明文所对应的密文。些明文所对应的密文。选择明文攻击选择明文攻击（chosenplaintext attack）：）：密码分析密码分析者可得到所需要的任何明文所对应的密文，这些密文与者可得到所需要的任何明文所对应的密文，这些密文与要破译的密文是用同一个密钥加密得来的要破译的密文是用同一个密钥加密得来的选择密文攻击选择密文攻击（chosenciphertext attack）：）：密码分密码分析者

12、可得到所需要的任何密文所对应的明文，解密这些析者可得到所需要的任何密文所对应的明文，解密这些密文所使用的密钥与要破译的密文的密钥是相同的密文所使用的密钥与要破译的密文的密钥是相同的密码分析密码分析 密码系统密码系统 v一个好的密码系统应满足一个好的密码系统应满足：系统理论上安全，或计算上安全；系统理论上安全，或计算上安全；系统的保密性是依赖于密钥的，而不是依赖于对加密体系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密；制或算法的保密；加密和解密算法适用于密钥空间中的所有元素；加密和解密算法适用于密钥空间中的所有元素；系统既易于实现又便于使用。系统既易于实现又便于使用。加密的功能加

13、密的功能v保密性保密性：基本功能，使非授权者无法知道消息的内容。：基本功能，使非授权者无法知道消息的内容。v鉴别鉴别：消息的接收者应该能够确认消息的来源。：消息的接收者应该能够确认消息的来源。v完整性完整性：消息的接收者应该能够验证消息在传输过程中没有：消息的接收者应该能够验证消息在传输过程中没有被改变。被改变。v不可否认性不可否认性：发送方不能否认已发送的消息。：发送方不能否认已发送的消息。古典加密技术古典加密技术从古到今有无数种加密方法，但归类起来，古代主要是代替密从古到今有无数种加密方法，但归类起来，古代主要是代替密码、置换密码以及两者的结合。码、置换密码以及两者的结合。v代替密码代替密

14、码简单代替密码简单代替密码多码代替密码多码代替密码多字母代替密码多字母代替密码多表代替密码多表代替密码v置换密码：置换密码：换位密码换位密码2.2 传统密码及其破译传统密码及其破译Scytale密码和恺撒密码密码和恺撒密码 v最先有意识的使用一些技术的方法来加密信息的可能是公元最先有意识的使用一些技术的方法来加密信息的可能是公元前前500年的古希腊人。他们使用的是一根叫年的古希腊人。他们使用的是一根叫scytale的棍子。的棍子。送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人。如果不知道棍子的粗细是不可面，接着打

15、开纸送给收信人。如果不知道棍子的粗细是不可能解密里面的内容的，如下图所示。能解密里面的内容的，如下图所示。公元前公元前50年，著名的恺撒大帝发明了一种密码叫做恺撒密年，著名的恺撒大帝发明了一种密码叫做恺撒密码。在恺撒密码中，每个字母都与其后第三位的字母对应，码。在恺撒密码中，每个字母都与其后第三位的字母对应，然后进行替换。如果到了字母表的末尾，就回到开始，如然后进行替换。如果到了字母表的末尾，就回到开始，如此形成一个循环。当时罗马的军队就用恺撒密码进行通信。此形成一个循环。当时罗马的军队就用恺撒密码进行通信。v恺撒密码明文字母表：恺撒密码明文字母表：A B C D E F G X Y Zv恺撒

16、密码密文字母表：恺撒密码密文字母表：D E F G H I J A B Cv26个字符代表字母表的个字符代表字母表的26个字母，从一般意义上说，也可个字母，从一般意义上说，也可以使用其它字符表，一一对应的数字也不一定要是以使用其它字符表，一一对应的数字也不一定要是3，可，可以选其它数字。以选其它数字。Caesar密码密码 乘数密码算法乘数密码算法v加密函数取形式为加密函数取形式为 e(x)=ax(mod 26)，aZ26 要求唯一解的充要条件是要求唯一解的充要条件是gcd(a,26)=1 该算法描述为：该算法描述为：设设P=C=Z26，K=a Z26|gcd(a,26)=1,对对k=a K,定

17、义定义 ek(x)=ax(mod 26)和和dk(y)=a-1(y)(mod 26)，x,y Z26例子例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZ AJSBKTCLUDMVENWFOXGPYHQZIR 明文明文 密文密文 cipher=SUFLKX乘数密码分析乘数密码分析v对于乘数密码，当且仅当对于乘数密码，当且仅当a与与26互素时，加密变换才互素时，加密变换才是一一映射的，因此是一一映射的，因此a的选择有的选择有11种：种：a=3,5,7,9,11,15,17,19,21,23,25 可能尝试的密钥只有可能尝试的密钥只有11个个栅栏密码栅栏密码v所谓栅栏密码，就是把要

18、加密的明文分成所谓栅栏密码，就是把要加密的明文分成N个一组，然后把个一组，然后把每组的第每组的第i个字连起来，形成一段无规律的话。个字连起来，形成一段无规律的话。就是组成栅就是组成栅栏的字母一般不会太多。（一般不超过栏的字母一般不会太多。（一般不超过30个）个）v一般比较常见的是一般比较常见的是2栏的栅栏密码。栏的栅栏密码。比如明文：比如明文：THERE IS A CIPHER 去掉空格后变为：去掉空格后变为：THEREISACIPHER 两个一组，得到：两个一组，得到：TH ER EI SA CI PH ER 先取出第一个字母：先取出第一个字母：TEESCPE 再取出第二个字母：再取出第二个

19、字母：HRIAIHR 连在一起就是：连在一起就是：TEESCPEHRIAIHR v解密的时候，我们先把密文从中间分开，变为两行：解密的时候，我们先把密文从中间分开，变为两行：T E E S C P E H R I A I H R 再按上下上下的顺序组合起来：再按上下上下的顺序组合起来：THEREISACIPHER 分出空格，就可以得到原文了：分出空格，就可以得到原文了：THERE IS A CIPHER 栅栏密码栅栏密码仿射密码仿射密码v仿射密码是一种替换密码。它是一个字母对一个字母的。仿射密码是一种替换密码。它是一个字母对一个字母的。它的加密函数是它的加密函数是 ，其中其中 a和和m互质。互

20、质。m是字母的数目。是字母的数目。解密函数为：解密函数为：v例例 设设k（7，3），），注意到注意到7-1(mod 26)=15,加密函数是加密函数是ek(x)=7x+3，相，相应的解密函数是应的解密函数是dk(y)=15(y-3)=15y-19,易见易见 dk(ek(x)=dk(7x+3)=15(7x+3)-19 =x+45-19 =x(mod 26)若加密明文：若加密明文：hot，首先转换字母首先转换字母h,o,t成为数字成为数字7,14,19,然后加密：然后加密：解密：解密：希尔密码希尔密码v希尔密码（希尔密码（Hill Password）是运用）是运用基本矩阵论原理基本矩阵论原理的的多

21、字多字母代换密码母代换密码，由，由Lester S.Hill在在1929年发明。每个字母当年发明。每个字母当作作26进制数字：进制数字：A=0,B=1,C=2.一串字母当成一串字母当成n维向量，维向量，跟一个跟一个nn的矩阵相乘，再将得出的结果模的矩阵相乘，再将得出的结果模26。注意用作。注意用作加密的矩阵（即密匙）加密的矩阵（即密匙）是可逆的，否则就不可能译码。只是可逆的，否则就不可能译码。只有矩阵的行列式和有矩阵的行列式和26互质，才是可逆的。互质，才是可逆的。其中所有的运算都是在其中所有的运算都是在 中进行。中进行。v例例 假定密钥假定密钥K是是 ，则，则K-1=。现在我们加密。现在我们

22、加密明文明文july分为两个明文组（分为两个明文组（9，20）（相应于）（相应于ju）和（）和（11，24）（相应于）（相应于ly）。计算如下：）。计算如下：因此，因此，july的加密是的加密是DELW。同理，可使用同理，可使用K-1进行解密。进行解密。Vigenre密码密码 v构成构成明文：每个字符惟一对应一个明文：每个字符惟一对应一个025间的数字。间的数字。密钥：一个字符串，其中每个字符同明文一样对应一密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如个数字，代表位移值，如a 表示位移表示位移 0，b 表示位移表示位移 1，c 表示位移表示位移 2，.）。）。v加密过程

23、：加密过程：将明文数字串依据密钥长度分段，并逐一与密钥数字将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模串相加（模26），得到密文数字串；），得到密文数字串；最后，将密文数字串转换为字母串。最后，将密文数字串转换为字母串。v例例 设设m6，且密钥字是，且密钥字是k=CIPHER,这相应于密钥。假定明这相应于密钥。假定明文串是文串是 this cryptosystem is not secure 首先将明文串转化为数字串，按首先将明文串转化为数字串，按6个一组分段，然后模个一组分段，然后模26“加加”上密钥字得：上密钥字得：相应的密文串将是相应的密文串将是:VPXZGIAXIVWPUB

24、TTMJPWIZITWZT解密过程与加密过程类似解密过程与加密过程类似,不同的只是进行模不同的只是进行模26减减,而不是模而不是模26加。加。置换密码置换密码 v在简单的纵行置换密码中，把明文按列写入，按行读出，而在简单的纵行置换密码中，把明文按列写入，按行读出，而密钥事实上由两方面信息组成：行宽、列高，读出顺序默认密钥事实上由两方面信息组成：行宽、列高，读出顺序默认从左到右。一个简单纵行置换密码比如：明文：从左到右。一个简单纵行置换密码比如：明文：computer graphics may be slow，按照列宽，按照列宽10个字符的方式写出为：个字符的方式写出为：c o m p u t

25、e r g ra p h i c s m a y b e s l o wv可以得到密文：可以得到密文：caeopsmhlpioucwtsemragyrb，v下面是一个由密钥确定读出顺序的例子：如果再加上密钥：下面是一个由密钥确定读出顺序的例子：如果再加上密钥：密钥：密钥：43 1 2 567明文：明文：attackp ostpone duntilt woamxyzv按照密钥大小的顺利，按照列的字符得到密文：按照密钥大小的顺利，按照列的字符得到密文：TTNAAPTMTSUOAODWCOIXPETZ。置换密码置换密码 v例例 假定假定m6，密钥是以下置换，密钥是以下置换 ：；则逆置；则逆置换换 为

26、：为：。给出明文给出明文 shesellsseashellsbytheseashore.首先把明文分为首先把明文分为6个字母一组个字母一组：shesel lsseas hellsb ythese ashore.每六个字母按重排，得密文：每六个字母按重排，得密文：EESLSH SALSES LSHBLE HSYEET HRAEOS 用用 类似地解密。类似地解密。置换密码置换密码 置换密码是置换密码是Hill密码的特例。密码的特例。Playfair密码密码vPlayfair在在1854年发明了年发明了Playfair密码。在第一次世界大战中密码。在第一次世界大战中英国人就使用这种密码。英国人就使用

27、这种密码。vPlayfair将明文中的双字母组合作为一个单元对待，并将这将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。些单元转换为密文的双字母组合。I与与J视为同一字符，视为同一字符，55变换矩阵为变换矩阵为CIPHERABDFGKLM NOQSTUVWXYZv加密规则是按成对字母加密，规则为加密规则是按成对字母加密，规则为“相同对中的字母加相同对中的字母加分隔符分隔符(如如x)，同行取右边，同列取下边，其他取交叉，同行取右边，同列取下边，其他取交叉”。明文：明文：balloon 单词中的单词中的ll为相同字符，所以分组为：为相同字符，所以分组为：ba lx lo

28、on明文：明文：he，h和和e在矩阵中同一行，都取右边的字符，密文为：在矩阵中同一行，都取右边的字符，密文为：EC明文：明文：dm，d和和m在矩阵中同一列，都取下面的字符，密文为：在矩阵中同一列，都取下面的字符，密文为：MT明文：明文：kt，k和和t在矩阵中不同行也不同列，取交叉顶点上的字符，在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：密文为：MQ明文：明文：OD，O和和D在矩阵中不同行也不同列，取交叉顶点上的字符，在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：密文为：TR 以这个以这个55变换矩阵为例，可以对单词进行加密，加密结果变换矩阵为例，可以对单词进行加密，加密结果如表如

29、表2-1所示。所示。表表2-1明文明文分组分组密文密文balloonba lx lo ondb sp gs ugbookbo oksr qgfillfi lx lxae sp sp一次一密乱码本一次一密乱码本 v如上所述的所有密码算法均被破解，那么是否存在无法破解的理想加密如上所述的所有密码算法均被破解，那么是否存在无法破解的理想加密方案呢？香农证明了一种密码属于这种情况，它就是一次一密乱码本方案呢？香农证明了一种密码属于这种情况，它就是一次一密乱码本（one-time pad）。）。v一般说来，一次一密乱码本就是一个大的不重复的真随机密钥字母集，一般说来，一次一密乱码本就是一个大的不重复的真

30、随机密钥字母集，发送者用乱码本中的每一个密钥准确地加密一个明文字符，加密是明文发送者用乱码本中的每一个密钥准确地加密一个明文字符，加密是明文字符和密钥字符进行模字符和密钥字符进行模26加法。比如：加法。比如：明文：明文：onetimepad密钥：密钥：TBFRGFARFM密文：密文：IPKLPSFHGQ因为：因为：O+Tmod26=I，N+Bmod26=P，E+Fmod26=K，如果窃听者不能得到用来加密的一次一密乱码本，这个方案就是完全保如果窃听者不能得到用来加密的一次一密乱码本，这个方案就是完全保密的。给出的密文消息相当于同样长度的任何可能的明文消息。密的。给出的密文消息相当于同样长度的任

31、何可能的明文消息。v随机密钥随机密钥v安全强度取决于密钥的随机性安全强度取决于密钥的随机性v理论上不可破理论上不可破v实际上不可行实际上不可行产生大量的随机密钥难产生大量的随机密钥难密钥分配与保护更难密钥分配与保护更难v明文：明文：To be or not to be that is the question,使用使用Vigenre加加密，密钥字取为密，密钥字取为runv密钥：密钥：runrunrunrunrunrunrunrunrunrun 明文：明文：tobeornottobethatisthequestion 密文：密文：KIOVIEEIGKIOVNURNVJNUVKHVMGZIAvKI

32、OV，后一个相当于前一个向后移动了，后一个相当于前一个向后移动了9位；位；NU，后一个相当于前一个向后移动了，后一个相当于前一个向后移动了6位。位。v重复明文字母串的距离正好是密钥长度的倍数。重复明文字母串的距离正好是密钥长度的倍数。Vigenre密码的密码分析密码的密码分析Vigenre密码的密码分析密码的密码分析v第一步：确定密钥的长度，主要方法有：第一步：确定密钥的长度，主要方法有：Kasiski测试法测试法；基本原理基本原理：对于密钥长度为：对于密钥长度为d的的Vigenre密码，如果利用密码，如果利用给定的密钥表周期性地对明文字母进行加密，则当明文给定的密钥表周期性地对明文字母进行加

33、密，则当明文中有两个相同的字母组在明文序列中间隔的字母数为中有两个相同的字母组在明文序列中间隔的字母数为d的的倍数时，这两个明文字母组对应的密文字母组一定相同；倍数时，这两个明文字母组对应的密文字母组一定相同；反之，如果密文中出现两个相同的字母组，则其对应的反之，如果密文中出现两个相同的字母组，则其对应的明文字母组不一定相同。明文字母组不一定相同。重合指数法重合指数法。基本思想基本思想：对于长度分别为：对于长度分别为n的密文串的密文串y=y1y2yn，将其分，将其分为长度为为长度为n/d的的d个子串个子串Yi（i=1,2,d),如果密钥长度为如果密钥长度为d，则则Ic(Yi)0.065(1id

34、)，否则，因为采用不同的密钥依位，否则，因为采用不同的密钥依位加密，子串加密，子串Yi将更为随机。对于一个完全随机的密文串，将更为随机。对于一个完全随机的密文串，Ic(y)26(1/26)2=0.038。由于。由于0.038与与0.065的差值足够大，的差值足够大，所以在一般情况下，依据重合指数法能够判断出正确的密所以在一般情况下，依据重合指数法能够判断出正确的密钥长度。钥长度。Vigenre密码的密码分析密码的密码分析v第二步：确定密钥。第二步：确定密钥。通常采用重合互指数法通常采用重合互指数法。对于长度分别为。对于长度分别为n及及n的字母串的字母串x=x1x2xn和和y=y1y2yn，“重

35、合互指数重合互指数”指的是指的是x的一个的一个随机元素与随机元素与y的一个随机元素相同的概率，记为的一个随机元素相同的概率，记为MIc(x,y)。通过采用重合互指数法，可以获得任何两个子串通过采用重合互指数法，可以获得任何两个子串Yi与与Yj的的相对移位。相对移位。古典密码小结古典密码小结v模运算：模运算：加法、减法、乘法加法、减法、乘法性质：对称、传递、交换、结合、分配性质：对称、传递、交换、结合、分配加法逆元、乘法逆元加法逆元、乘法逆元v对称密码的两个基本运算对称密码的两个基本运算代替和置换代替和置换（Substitution&permutation）v密码分析与密码分析与Kerckhof

36、f原则原则v多轮加密多轮加密v数据安全基于算法的保密数据安全基于算法的保密 古古典典密密码码小小结结2.3 Shannon的保密系统信息理论的保密系统信息理论 v1949年，年，Shannon发表了一篇题为发表了一篇题为保密系统的信息理论保密系统的信息理论的论文。的论文。v用信息论的观点对信息保密问题进行了全面的阐述。用信息论的观点对信息保密问题进行了全面的阐述。v宣告了科学的密码学时代的到来。宣告了科学的密码学时代的到来。什么是信息什么是信息v科学家说：科学家说：信息是不确定性的减少，是负熵信息是不确定性的减少，是负熵v老百姓说：老百姓说：信息是让你知道些什么的东西信息是让你知道些什么的东西

37、v安全专家说：安全专家说：信息是一种资产，它意味着一种风险信息是一种资产，它意味着一种风险v老百姓说：老百姓说：不怕贼偷，就怕贼惦记不怕贼偷，就怕贼惦记通信系统模型通信系统模型 编码器编码器信信 源源信信 道道信信 宿宿译码器译码器干扰器干扰器图图2.2 通信系统模型通信系统模型加密器加密器信信 源源信信 道道接收者接收者解密器解密器分析者分析者图图2.3 保密系统模型保密系统模型密钥密钥Shannon提出的保密模型提出的保密模型无噪信道无噪信道安全信道安全信道密钥源密钥源加加 密密分析者分析者解解 密密接收者接收者发送者发送者信信 源源图图2.3 Shannon的保密系统模型的保密系统模型数

38、学模型数学模型v数学模型数学模型样本空间样本空间密钥空间密钥空间密文空间密文空间概率知识讨论概率知识讨论v在给定密文发生的条件下，某个明文发生的条件概在给定密文发生的条件下，某个明文发生的条件概率率信息量和熵信息量和熵 v定义定义 设随机变量设随机变量 ，出现的概率为出现的概率为 。则。则 X 的不确定性或熵（的不确定性或熵（Entropy）定义为）定义为 v熵反映了集中事件出现的熵反映了集中事件出现的平均不确定性平均不确定性，或为确定集中出现一个，或为确定集中出现一个事件平均所需的信息量（观测之前），或事件平均所需的信息量（观测之前），或集中每出现一个事件平集中每出现一个事件平均给出的信息量

39、（观测之后）均给出的信息量（观测之后）。如果从编码的角度来考虑，熵也如果从编码的角度来考虑，熵也可以理解成用可以理解成用最优的二进制编码形式表示所需的比特数最优的二进制编码形式表示所需的比特数。v采用以采用以2 2为底的对数时，相应的信息单位称作比特（为底的对数时，相应的信息单位称作比特（BitBit）。）。v如果集如果集X为均匀分布时，即为均匀分布时，即 ，则，则 。v ，当，当X为确定性的事件时，即为确定性的事件时，即X概率分布为概率分布为 ，则，则 。例：某地某季节各种天气情况出现的概率分别为晴：例：某地某季节各种天气情况出现的概率分别为晴：例：某地某季节各种天气情况出现的概率分别为晴：

40、例：某地某季节各种天气情况出现的概率分别为晴：50%50%，阴：，阴：，阴：，阴：25%25%，大雨：，大雨：，大雨：，大雨：12.5%12.5%，小雨：，小雨：，小雨：，小雨：12.5%12.5%。请问某人听到一则天气预。请问某人听到一则天气预。请问某人听到一则天气预。请问某人听到一则天气预报后获得的信息量是多少？报后获得的信息量是多少？报后获得的信息量是多少？报后获得的信息量是多少？（也可以理解为：（也可以理解为：（也可以理解为：（也可以理解为：这则天气预报消除了多少人们对天气情况认这则天气预报消除了多少人们对天气情况认这则天气预报消除了多少人们对天气情况认这则天气预报消除了多少人们对天气

41、情况认识的不确定性识的不确定性识的不确定性识的不确定性？）？）？）？）解：解：解：解：=0.5log =0.5log2 2 1/0.5+0.25 log 1/0.5+0.25 log2 2 1/0.25+1/0.25+0.125log 0.125log2 2 1/0.125+0.125log 1/0.125+0.125log2 2 1/0.125 1/0.125 =1.75 bit =1.75 bit H=Pi log2 1 Pi 4 4i=1i=1信息量和熵信息量和熵 案案 例例韦小宝赌博：韦小宝赌博：韦小宝掷骰子赌钱十赌九赢。计韦小宝掷骰子赌钱十赌九赢。计算包含的算包含的信息量信息量？未做

42、手脚情况：等概率事件，不确定性为：未做手脚情况：等概率事件，不确定性为：H(S)=-log(pi)=-log(1/6)=2.5850(bit)做手脚情况：某面的概率为做手脚情况：某面的概率为0.9，其他，其他5面的概率均面的概率均为为1/50，则不确定性为：，则不确定性为：H(S)=-pi log(pi)=-0.9log(0.9)-50.02log(0.02)=0.7012(bit)韦小宝赌博韦小宝赌博v定义定义 设设 ，出现的概率为出现的概率为 。，出现的概率为出现的概率为 ，则联合事件集则联合事件集 ，令令 的概率为的概率为 ，此时，此时 。集。集X和和Y的联合熵定义为的联合熵定义为 集相

43、对于事件集相对于事件yiY的条件熵定义为的条件熵定义为 集相对于集集相对于集Y的条件熵定义为的条件熵定义为 熵的基本特性熵的基本特性v定理定理 ，当且仅当，当且仅当X和和Y独立时等号成立。独立时等号成立。v定理定理 。v推论推论 ，当且仅当，当且仅当X和和Y独立时等号成立。独立时等号成立。密码体制的安全性（密码体制的安全性（1）v无条件安全或完善保密性无条件安全或完善保密性（unconditionally secure）：）：不论提供的密文有多少，密文中所包含的信息都不足以不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；惟一地确定其对应的明文；具有无限计算资源（诸如时间

44、、空间、资金和设备等）具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。的密码分析者也无法破译某个密码系统。完善保密性完善保密性 v一个保密系统（一个保密系统（P，C，K，E，D）称为完善的无条件的保密）称为完善的无条件的保密系统，如果系统，如果H(P)=H(P|C),其中，其中，P为明文集合，为明文集合，C为密文集合，为密文集合，K为密钥集合，为密钥集合，E为加密算法为加密算法,D为解密算法为解密算法,则完善保密系统存则完善保密系统存在的必要条件是在的必要条件是H(P)H(K)。可见，要构造一个完善保密系。可见，要构造一个完善保密系统，其密钥量的对数（密钥空

45、间为均匀分布的条件下）必须统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。不小于明文集的熵。从熵的基本性质可推知，保密系统的密钥量越小，其密文从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。中含有的关于明文的信息量就越大。v定理：存在完善保密系统定理：存在完善保密系统 如：一次一密（如：一次一密（one-time pad）方案；不实用。）方案；不实用。密码体制的安全性（密码体制的安全性（2 2）v实际上安全实际上安全计算上是安全：算出和估计出破译它的计算量下限，利计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码

46、系统所需要的努力超出用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。了破译者的破译能力（诸如时间、空间、资金等资源）。可证明安全：从理论上证明破译它的计算量不低于解已可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。知难题的计算量。伪密钥和惟一解距离伪密钥和惟一解距离 v当分析者截获到密文当分析者截获到密文c时，他首先利用所有的密钥对其进行解密，时，他首先利用所有的密钥对其进行解密，并得到明文并得到明文mDk(c)，kK。接下来，对于所有有意义的消息。接下来，对于所有有意义的消息m，他记录下与之对应的密钥。这些密钥构成的集合通常含

47、有多个元，他记录下与之对应的密钥。这些密钥构成的集合通常含有多个元素，并且至少含有一个元素，即正确的密钥。人们把那些可能在这素，并且至少含有一个元素，即正确的密钥。人们把那些可能在这个集合中出现但并不正确的密钥称为个集合中出现但并不正确的密钥称为伪密钥伪密钥（spurious key）。）。v一个保密系统的惟一解距离定义为一个保密系统的惟一解距离定义为使得伪密钥的期望数等于零的使得伪密钥的期望数等于零的n的值的值，记为，记为n0，即在给定的足够的计算时间下分析者能惟一地计算，即在给定的足够的计算时间下分析者能惟一地计算出密钥所需要的密文的平均量。出密钥所需要的密文的平均量。v用于衡量在惟密文攻

48、击下破译一个密码系统时，密码分析者必须处用于衡量在惟密文攻击下破译一个密码系统时，密码分析者必须处理的密文量的理论下界。理的密文量的理论下界。Simmons认证系统的信息理论认证系统的信息理论 v内容：将信息论用于研究认证系统的理论安全性和实际安全内容：将信息论用于研究认证系统的理论安全性和实际安全性问题，指出认证系统的性能极限以及设计认证码所必须遵性问题，指出认证系统的性能极限以及设计认证码所必须遵循的原则。循的原则。v目的：一个是目的：一个是推导欺骗者欺骗成功的概率的下界推导欺骗者欺骗成功的概率的下界；另一个是；另一个是构造欺骗者欺骗成功的概率尽可能小的认证码构造欺骗者欺骗成功的概率尽可能

49、小的认证码。认证码认证码 基本要素有基本要素有3 3个：个：信源集合；信源集合；消息集合；消息集合；编码规则集合，其中每一个编码规则由一个秘密密钥来编码规则集合，其中每一个编码规则由一个秘密密钥来控制。控制。认证系统模型认证系统模型 v一种是一种是无仲裁者的认证系统模型无仲裁者的认证系统模型。在这种模型中，只有。在这种模型中，只有3种种参加者，即消息的发送者、接收者和入侵者。消息的发送者参加者，即消息的发送者、接收者和入侵者。消息的发送者和接收者之间相互信任，他们拥有同样的秘密信息。和接收者之间相互信任，他们拥有同样的秘密信息。v另一种是另一种是有仲裁者的认证系统模型有仲裁者的认证系统模型。在

50、这种模型中，有。在这种模型中，有4种种参加者，即消息的发送者、接收者、入侵者和仲裁者，信息参加者，即消息的发送者、接收者、入侵者和仲裁者，信息的发送者和接收者之间相互不信任，但他们都信任仲裁者，的发送者和接收者之间相互不信任，但他们都信任仲裁者，仲裁者拥有所有的秘密信息并且不进行欺骗。仲裁者拥有所有的秘密信息并且不进行欺骗。无仲裁者的认证系统模型无仲裁者的认证系统模型 无仲裁者的认证系统数学描述无仲裁者的认证系统数学描述一个无分裂的、没有保密功能的、无仲裁者的认证系统，可由满一个无分裂的、没有保密功能的、无仲裁者的认证系统，可由满足下列条件的四重组（足下列条件的四重组（S，A，K，）来描述：）