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

1,第2讲密码学的基本概念和理论基础,2,2.1基本概念,2.1.1什么是密码学密码学是研究密码系统或通信安全的一门学科，分为密码编码学和密码分析学。密码编码学是使得消息保密的学科密码分析学是要研究加密消息破译的学科,3,2.1.2密码学的发展历史,第1阶段：古典密码,1949年以前,密码技术的主要特点是数据的安全基于算法的保密。第2阶段：常规现代密码学,从1949年到1975年。标志：1949年Shannon发表的保密系统的信息理论一文。信息论为对称密码系统建立了理论基础，从此密码学成为一门科学。以及破译者的出版和美国数据加密标准DES的实施，标志着密码学的理论与技术的划时代的革命性变革，宣布了近代密码学的开始。,4,密码学的发展历史,第3阶段：公钥密码学，1976年至今。标志：1976年Diffie和Hellman发表了密码学新方向一文，提出了适应网络上保密通信的公钥密码思想。1978年RSA公钥密码体制的出现，成为公钥密码的杰出代表，并成为事实标准，在密码学史上是一个里程碑。,5,2.1.3相关术语,Shannon保密系统模型,术语：明文、密文、密钥（加密密钥与解密密钥）、加密、解密、加密算法、解密算法、加密系统,6,组成部分,X,明文（plain-text）：作为加密输入的原始信息。Y,密文（cipher-text）：对明文变换的结果。E,加密（encrypt）：对需要保密的消息进行编码的过程，是一组含有参数的变换。D,解密（decrypt）：将密文恢复出明文的过程，是加密的逆变换。Z（K）,密钥（key）：是参与加密解密变换的参数。加密算法：对明文进行加密时采取的一组规则或变化解密算法：对密文进行解密时采用的一组规则或变化加密算法和解密算法通常在一对密钥控制下进行，分别称为加密密钥和解密密钥。一个密码系统（或称密码体制或密码）由加解密算法以及所有可能的明文、密文和密钥（分别称为明文空间、密文空间和密钥空间）组成。,7,2.1.4密码体制的分类,几种不同的分类标准1.按操作方式进行分类操作方式：是明文变换成密文的方法。替换密码、换位密码。替换密码又称代替密码是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。换位密码又称置换密码，加密过程中明文的字母保持相同，但顺序被打乱了。2.按照对明文的处理方法进行分类流密码（将明文按字符逐位加密）。分组密码（对明文进行分组后逐组加密）。,8,密码体制的分类,几种不同的分类标准3.按照使用密钥的数量进行分类对称密钥（单密钥）、公开密钥（双密钥）从密钥使用数量上看，密码系统分为单密钥系统和双密钥系统单密钥系统又称为对称密码系统或秘密密钥系统，其加密密钥和解密密钥或者相同或者实质上等同，即从一个密钥得出另一个。,单钥密码的加密、解密过程,9,双密钥系统又称为非对称密码系统或公开密钥系统。双密钥系统有两个密钥，一个是公开的，用K1表示，谁都可以使用；另一个是私人密钥，用K2表示。,双钥密码的加密、解密过程,双密钥系统的主要特点是将加密和解密密钥分开。即用公开的密钥K1加密消息，发送给持有相应私人密钥K2的人，只有持私人密钥K2的人才能解密；而用私人密钥K2加密的消息，任何人都可以用公开的密钥K1解密，此时说明消息来自持有私人密钥的人。前者可以实现公共网络的保密通信，后者则可以实现对消息进行数字签名。,10,2.1.5密码分析,假定：密码分析者知道对方所使用的密码系统包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法）、密钥空间及其统计特性。不知道密钥。在设计一个密码系统时，目标是在Kerckhoffs假设的前提下实现安全。,1.Kerckhoffs柯克霍夫斯假设,对通信双方而言，通信的一方将信息加密后发送给另一方，是为了使攻击者即使得到密文也无法读懂。对于攻击者来说，在不知道密钥的情况下，要想读懂密文，就要根据他的知识以及掌握的情报来进行密码分析。,11,2.密码分析的方法,密码分析：从密文推导出明文或密钥。密码分析：常用的方法有以下4类：惟密文攻击（cybertextonlyattack）；已知明文攻击（knownplaintextattack）；选择明文攻击（chosenplaintextattack）；选择密文攻击（chosenciphertextattack）。,12,（1）惟密文攻击,密码分析者知道一些消息的密文（加密算法相同），并且试图恢复尽可能多的消息明文，并进一步试图推算出加密消息的密钥（以便通过密钥得出更多的消息明文）。对于这种形式的密码分析，攻击者需要掌握的内容只有两样：加密算法、待破译的密文。,13,（2）已知明文攻击,密码分析者不仅知道一些消息的密文，也知道与这些密文对应的明文，并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密）。攻击者需要掌握的内容包括：经密钥加密形成的一个或多个明文密文对，即知道一定数量的密文和对应的明文，另外可能包括加密算法。,14,（3）选择明文攻击,密码分析者不仅知道一些消息的密文以及与之对应的明文，而且可以选择被加密的明文（这种选择可能导致产生更多关于密钥的信息）和对应的密文，并试图推导出加密密钥或算法。攻击者可以事先任意选择一定数量的明文，让被攻击的加密算法加密，并得到相应的密文。目标是通过这一过程获得关于加密算法的一些信息，以利于攻击者在将来更有效的破解由同样加密算法（以及相关密钥）加密的信息。在最坏情况下，攻击者可以直接获得解密用的密钥。在公钥密码学中，这就是一个很现实的模式。因为公钥密码方案中，加密用的密钥是公开的，这样攻击者就可以直接用它来加密任意的信息。,15,（4）选择密文攻击,与选择明文攻击相对应，密码分析者除了知道加密算法外，还包括他自己选定的密文和对应的、已解密的原文，即知道选择的密文和对应的明文。密码分析的目的是推导出密钥。攻击者需要掌握的内容包括：加密算法、截获的部分密文、自己选择的密文消息以及相应的被解密的明文。密码分析者事先任意搜集一定数量的密文，让这些密文通过被攻击的加密算法解密，通过未知的密钥获得解密后的明文。由此能够计算出加密者的私钥，攻击者可以恢复所有的明文。有时选择密文攻击和选择明文攻击一起被称作选择文本攻击。惟密文攻击最困难-分析者可供利用的信息最少。上述攻击的强度递增。一个密码体制是安全的，通常是指在前三种攻击下的安全性，即攻击者一般容易具备进行前三种攻击的条件。,16,3.密码系统,一个好的密码系统应满足：系统理论上安全，或计算上安全（从截获的密文或已知的明文-密文对，要确定密钥或任意明文在计算上不可行）；系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密；加密和解密算法适用于密钥空间中的所有元素；系统既易于实现又便于使用。,17,2.1.6加密的功能,保密性：基本功能，使非授权者无法知道消息的内容。鉴别：消息的接收者应该能够确认消息的来源。完整性：消息的接收者应该能够验证消息在传输过程中没有被改变。不可否认性：发送方不能否认已发送的消息。,18,2.2传统密码,从古代密码出现一直到现代计算机诞生，密码学是由基于字符的密码算法构成的。不同的密码算法是字符之间互相代替或者是互相之间换位，好的密码算法是结合这两种方法，进行多次计算。,19,例子：Scytale密码和恺撒密码,（1）最先有意识的使用一些技术的方法来加密信息的可能是公元前500年的古希腊人。他们使用的是一根叫scytale的棍子。送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人。如果不知道棍子的粗细是不可能解密里面的内容的，如下图所示。,20,（2）曾有这样一件事，有一天，距斯巴达城很远的兵营中来了一个专程从斯巴达城赶来送信的奴隶，兵营中有位名叫莱桑德的将军读了信以后，感到很失望，因为信中毫无重要消息，就随手把它扔到一边去了。可是，刹那间，将军锐利的目光好像发现了什么，他立即命令侍卫人员暂时回避，然后对这个奴隶说：“把腰带给我。”这是一条普通的腰带，只是在腰带周围雕刻着一串字母，看上去毫无意义，大概只是做装饰之用。但当将军把腰带螺旋式地绕在一根棍棒上时，奇迹出现了。显现在棍棒上的字母不再是无意义的了。它告诉将军一个极端重要的消息：斯巴达当时的同盟者波斯人正在搞阴谋，企图谋反夺权；于是将军立即带着他的队伍急速返回斯巴达城，粉碎了这起叛乱。,21,（3）公元前50年，著名的恺撒大帝发明了一种密码叫做恺撒密码。在恺撒密码中，每个字母都与其后第三位的字母对应，然后进行替换。如果到了字母表的末尾，就回到开始，如此形成一个循环。当时罗马的军队就用恺撒密码进行通信。恺撒密码明文字母表：ABCDEFGXYZ恺撒密码密文字母表：DEFGHIJABC26个字符代表字母表的26个字母，从一般意义上说，也可以使用其它字符表，一一对应的数字也不一定要是3，可以选其它数字。,22,代替密码和置换密码,代替密码（SubstitutionCipher)是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。置换密码(PermutationCipher)又称换位密码（TranspositionCipher)，加密过程中明文的字母保持相同，但顺序被打乱了。,23,一、代替密码,在经典密码学中，有4种类型的代替密码：1简单代替密码又称单字母密码（SimpleSubstitutionCipher）明文的一个字符用相应的一个密文字符代替。恺撒密码就是一种简单的代替密码，它的每一个明文字母都由其右边第三个字母代替。ROT13是建立在UNIX系统上的简单的加密程序，它也是简单代替密码。在这种密码中A被N代替，B被O代替，等等，每个字母是环移13所对应的字母。用ROT13加密文件两遍便恢复出原始的文件：P=ROT13（ROT13（P）简单代替密码很容易破解，因为它没有将明文的不同字母的出现频率掩盖起来。（例如E在正常的英语散文中出现频率最高13%，其次是T、R、I、N、O、B等）。,24,2多名码代替密码（HomophonicSubstitutionCipher）在多名码代换中，字符的每次出现也许会有不同的代换，以便降低密文字母出现频率。明文字符和密文字符的关系是一对多的。例如，“a”在文本的开始可以加密为“D”，在文本的中间可以加密为“N”。当对字母的赋值个数与字母出现频率成比例时，安全性将有所提高。这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。1401年DuchyMantua公司就开始使用多名码代替密码，比简单代替密码难破译，但仍不能掩盖明文语言的所有统计特性，用已知明文攻击，较容易破解，但用唯密文攻击要困难一些。举例：,25,举例：,为了创建多码代换密码，要使每个明文字符，既依赖于信息的相关明文字符也依赖于明文字符的位置。这就表明密钥应该是一个子密钥流，其中的每一个子密钥都取决于用子密钥加密的明文字符的位置。也就是说，要用一个密钥流k=(k1,k2,k3,.)，在这一密钥流中，ki用来加密第i个明文字符，以便在密文中创建第i个字符。例如：自动密钥密码(autokeycipher)。在该密码中，密钥是一个子密钥流，其中每一个子密钥都可以用来对明文中相关的字符进行加解密。第一个子密钥是一个在A和B之间秘密协议过的预先规定的值，第二个子密钥是第一个明文字符的值(在025之间)，第三个子密钥是第二个明文字符的值，如此等等。密码的名称“自动密钥”是指，在加密过程中，子密钥是从明文密码字符中自动创建的。设初始密钥值k1=12，“Attackistoday”密文应该是什么？,26,3多字母代替密码（PloygramSubstitutionCipher)字符块被成组加密，例如，ABA可能对应于RTQ，ABB可能对应于SLL，等等。Playfair（普莱费尔）在1854年发明了Playfair密码。在第一次世界大战中英国人就使用这种密码。Playfair将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。I与J视为同一字符，55变换矩阵为CIPHERABDFGKLMNOQSTUVWXYZ,27,多字母代替密码加密规则是按成对字母加密，规则为“相同对中的字母加分隔符(如x)，同行取右边，同列取下边，其他取交叉”。例如下面的分组加密方法:明文he，h和e在矩阵中同一行，都取右边的字符，密文为：EC明文dm，d和m在矩阵中同一列，都取下面的字符，密文为MT明文kt，k和t在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：MQ明文OD，O和D在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：TR明文：balloon单词中的ll为相同字符，所以分组为：balxloon,以这个55变换矩阵为例，可以对单词进行加密，加密结果如表2-1所示。,28,解密规则是按成对字母加密，规则为“同行取左边，同列取上边，其他取交叉”。编程,表2-1,Playfair密码算法有2626=676种字母对组合，字符出现几率一定程度上被均匀化，基于字母频率的攻击比较困难，但依然保留了相当的结构信息。,29,4多表代替密码（PolyalphabeticSubstitutionCipher）由多个简单的代替密码构成。多表代替密码由LoenBattista在1568年发明，曾经被美国南北战争期间的联军所使用。维吉尼亚（Vigenre)密码、博福特（Beaufort）密码、滚动密钥(running-key)密码、弗纳姆(Vernam)密码、转轮机(rotormachine)都属于多表代替密码。,30,二、置换密码,在简单的纵行置换密码中，把明文按列写入，按行读出，而密钥事实上由两方面信息组成：行宽、列高，读出顺序默认从左到右。一个简单纵行置换密码比如：明文：computergraphicsmaybeslow，按照列宽10个字符的方式写出为：computergraphicsmaybeslow可以得到密文：caeopsmhlpioucwtsemragyrb,编程,31,置换密码,下面是一个由密钥确定读出顺序的例子：如果再加上密钥：密钥：4312567明文：attackpostponeduntiltwoamxyz按照密钥大小的顺序，按照列的字符得到密文：TTNAAPTMTSUOAODWCOIXPETZ。,32,（1）转轮机,上个世纪20年代，出现了转轮密码，而由德国发明家亚瑟谢尔比乌斯发明的Enigma密码机最为著名。它主要由经电线相连的键盘、转子和显示器组成，转子本身也集成了26条线路（在下图中显示了6条），把键盘的信号对应到显示器不同的小灯上去。,三.举例,33,图中如果按下a键，那么灯B就会亮，这意味着a被加密成了B。同样地，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。如果在键盘上依次键入cafe（咖啡），显示器上就会依次显示DBCE，这是最简单的加密方法之一简单替换密码。,34,不仅仅如此，因为当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在图中就是转动1/6圈，而在实际中转动1/26圈）。左图表示了连续键入3个b的情况。,35,当第一次键入b时，信号通过转子中的连线，灯A亮起来，放开键后，转子转动一格，各字母所对应的密码就改变了；第二次键入b时，它所对应的字母就变成了C；同样地，第三次键入b时，灯E闪亮。为使机器更安全，可以把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26n。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。,36,德国人为了战时使用，大大加强了其基本设计，军用的Enigma由3个转轮，转轮机中还有一块稍微改变明文序列的插板，有一个反射器导致每个转轮对每一个明文字母操作两次，结构如下图所示。于是转子自身的初始方向，转子之间的相互位置，以及连接板连线的状况就组成了所有可能的密钥：,37,可能的密钥：三个转子不同的方向组成了26*26*26=17576种不同可能性；三个转子间不同的相对位置为6种可能性；连接板上两两交换6对字母的可能性数目非常巨大，有100391791500种；于是一共有17576*6*100391791500，大约为10000000000000000，即一亿亿种可能性。但如此复杂的密码机在第二次世界大战中被破解了，首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的Enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分密码本，获得密钥，以及进行选择明文攻击等等手段，破解出相当多非常重要的德军情报。,38,（2）一次一密乱码本,如上所述的所有密码算法均被破解，那么是否存在无法破解的理想加密方案呢？香农证明了一种密码属于这种情况，它就是一次一密乱码本（one-timepad）。一般说来，一次一密乱码本就是一个大的不重复的真随机密钥字母集，发送者用乱码本中的每一个密钥准确地加密一个明文字符，加密是明文字符和密钥字符进行模26加法。比如：明文：onetimepad密钥：TBFRGFARFM密文：IPKLPSFHGQ因为：O+Tmod26=I，N+Bmod26=P，E+Fmod26=K，如果窃听者不能得到用来加密的一次一密乱码本，这个方案就是完全保密的。给出的密文消息相当于同样长度的任何可能的明文消息。,39,由这样的一个随机密钥序列异或一个非随机的明文消息将产生一个完全随机的密文消息，再大的计算能力也无能为力。这个方案需要注意两点：一是密钥字母必须是真正随机产生的；二是密钥不能重复使用。一次一密乱码本的缺点就是要求密钥序列的长度必须等于消息的长度，这使它非常不适于加密较长的消息，另外要保证发送者和接受者是完全同步的，因为哪怕传输中仅仅有1位的偏移，就会导致消息变成乱七八糟的东西，无法解密。,40,（3）仿射密码,仿射密码是一种替换密码。它是一个字母对一个字母的。加密函数为：其中a和m互质,m是字母的数目，(a,b)作为密钥k。解密函数为：,41,例设k（7，3），注意到7-1(mod26)=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(mod26)若加密明文：hot，首先转换字母h,o,t成为数字7,14,19,然后加密：解密：,42,7-1(mod26)=?,设a-1(modm)=c,则ac=1(modm)(其中a=7,m=26)7c-1=26k，（可以编程测试k=1,2,3,当26*ki+1的值是7的倍数即可）即c=(26k+1)/7=3k+(5k+1)/7此时取k=4(取最小整数使其能够被整除),那么c=12+(20+1)/7=15,43,（4）Vigenre密码,构成明文：每个字符惟一对应一个025间的数字。密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，.）。加密过程：将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模26），得到密文数字串；最后，将密文数字串转换为字母串。解密过程解密过程与加密过程类似，采用的是模26减运算。例子（见P35，解密由同学们完成）。,编程,44,例设m6，且密钥字是k=CIPHER,这相应于密钥。假定明文串是thiscryptosystemisnotsecure首先将明文串转化为数字串，按6个一组分段，然后模26“加”上密钥字得：相应的密文串将是:VPXZGIAXIVWPUBTTMJPWIZITWZT解密过程与加密过程类似,不同的只是进行模26减,而不是模26加。,45,2.3Shannon的保密系统信息理论,1949年，Shannon发表了一篇题为保密系统的信息理论的论文。用信息论的观点对信息保密问题进行了全面的阐述。宣告了科学的密码学时代的到来。,46,通信与保密系统模型,目的：使窃听者即使在完全准确地收到了接收信号的情况下也无法恢复出原始消息。,目的：在信道有干扰的情况下，使接收的信息无错误或差错尽可能小。,47,Shannon提出的保密模型,信源-产生信息的源，密钥源-产生密钥序列的源,48,消息空间：设信源字母表为M=ai,i=0,1,2,N-1,字母ai出现的概率为p(ai)=0,且p(a0)+p(a1)+p(aN-1)=1。信源产生的任一长为L个符号的消息序列为m如下。若研究的是所有长为L的信源输出，则称：为消息空间或明文空间。密钥空间：设字母表为B=bt,t=1,2,s-1。把长为r的密钥序列k=(k1,k2,kr)，kiB的全体称作密钥空间。密文空间：Ck的全体为密文空间。在保密系统中，假定信道是无干扰的，因而对于合法的接收者，由于知道解密变换和密钥，易于从密文得到原来的消息m，m=Dk(Ck)=Dk(Ek(m),1.保密系统数学模型（先复习概率知识2.5节）,49,2.信息熵,简称熵,Shannon把信息（熵）定义为离散随机事件的出现概率。信息的基本作用就是消除人们对事物的不确定性。变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。信息熵是信息论中用于度量信息量的一个概念。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。,50,熵的表示,定义设随机变量出现的概率为:则X的不确定性或熵（Entropy）定义为,51,反映了集X中事件出现的平均不确定性，或为确定集X中出现一个事件平均所需的信息量（观测之前），或集X中每出现一个事件平均给出的信息量（观测之后）。采用以2为底的对数时，相应的信息单位称作比特（Bit）。如果集X为均匀分布时，即，则。例如32(64)队参加球赛，各队夺冠的机率相同，则H(x）=5(6)，当X为确定性的事件时，即X概率分布为，则。(例如考试成绩大于等于零）,52,定义设，出现的概率为。，出现的概率为，则联合事件集，令的概率为，此时。集X和Y的联合熵定义为集X相对于事件yiY的条件熵定义为集X相对于集Y的条件熵定义为条件熵表示观察到集Y后集X还保留的不确定性。,联合熵、条件熵,53,熵的基本特性,定理，当且仅当X和Y独立时等号成立。定理。推论，当且仅当X和Y独立时等号成立。,54,3.密码体制的安全性（1）,衡量一个保密系统的安全性有两种基本方法：一种是无条件安全，又称完善保密性；另一种是计算安全性，又称实际保密性。计算安全性（computationalsecurity）：如果利用最好的算法（已知的或未知的）破译一个密码系统需要至少N（某一确定的、很大的数）次运算，就称该系统为计算上安全的系统。无条件安全（unconditionallysecure）：不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。,55,完善保密性,一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果H(P)=H(P|C),其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法,D为解密算法,则完善保密系统存在的必要条件是H(P)H(K)。可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。从密码系统的设计者角度看，要选择足够大的密钥量，而且希望从密文中提取的有关明文信息尽可能地小。存在完善保密系统如：一次一密（one-timepad）方案；不实用,但可用在少数场合。,56,密码体制的安全性（2）,计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。或者破译该密码系统的难度等价于解数学上的某个已知难题，即从理论上证明破译它的计算量不低于解已知难题的计算量（称可证明安全）。,实际保密性,57,4.伪密钥和惟一解距离,当分析者截获到密文c时，他首先利用所有的密钥对其进行解密，并得到明文mDk(c)，kK。对于所有有意义的消息m，他记录下与之对应的密钥。这些密钥构成的集合通常含有多个元素，并且至少含有一个元素，是正确的密钥。人们把那些可能在这个集合中出现但并不正确的密钥称为伪密钥（spuriouskey）。一个保密系统的惟一解距离定义为使得伪密钥的期望数等于零的n的值，记为n0，即在给定的足够的计算时间下分析者能惟一地计算出密钥所需要的密文的平均量。用于衡量在惟密文攻击下破译一个密码系统时，密码分析者必须处理的密文量的理论下界。一般破译密码系统所需要的密文量都远大于n0。,58,2.4Simmons认证系统的信息理论,内容：将信息论用于研究认证系统的理论安全性和实际安全性问题，指出认证系统的性能极限以及设计认证码所必须遵循的原则。构成一个认证码的基本要素有3个：信源集合、消息集合和编码规则集合，其中每一个编码规则由一个秘密密钥来控制。发送者的任何一个编码规则都是从信源集合到消息集合的一个映射，这个映射的每一个原像可能有一个像，也可能有几个像。如果发送者的每个编码规则的每一个原像只有一个像，则称这种认证码为无分裂的认证码。如果发送者的每个编码规则的每一个原像有不止一个像，则称这种认证码为有分裂的认证码。,西蒙斯,59,信息的认证和保密是信息安全的两个不同方面，一个认证码可以具有保密功能，也可以没有保密功能。没有保密功能的认证码也称为Cartesian码，每个消息都独立于所使用的编码规则并惟一确定一个信源，无论谁看到消息都能断定这一消息所代表的信源。对具有保密功能的认证码而言，任何给定的消息没有给出关于信源的任何消息。,60,认证系统模型分类,一种是无仲裁者的认证系统模型。在这种模型中，只有3种参加者，即消息的发送者、接收者和入侵者。消息的发送者和接收者之间相互信任，他们拥有同样的秘密信息。另一种是有仲裁者的认证系统模型。在这种模型中，有4种参加者，即消息的发送者、接收者、入侵者和仲裁者，信息的发送者和接收者之间相互不信任，但他们都信任仲裁者，仲裁者拥有所有的秘密信息并且不进行欺骗。,61,无仲裁者的认证系统模型,62,无仲裁者的认证系统数学描述,一个无分裂的、没有保密功能的、无仲裁者的认证系统，可由满足下列条件的四重组（S，A，K，）来描述：S是所有可能的信源状态构成的一个有限集，称为信源集；A是所有可能的认证标签构成的一个有限集；K是所有可能的密钥构成的一个有限集，称为密钥空间；对每一个kK,有一个认证规则：ek：S-A。消息集M定义为M=SA。,63,2.5算法复杂性,密码学研究的主要内容之一是对不同的密码技术和算法的计算复杂性进行比较，以便确定它们的安全性。计算复杂性：研究密码分析对于计算量的需求和密码分析的困难程度，从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性，包括：算法复杂性；问题复杂性。,64,1.算法（algorithm）,即求解某个问题的一系列具体步骤（通常被理解为求解所需的通用计算程序）。算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（resolvable），否则称该问题不可解（unresolvable）。,65,2.算法复杂性度量,即度量该算法所需的计算能力，包括：时间复杂性T（timecomplexity）；空间复杂性S（spacecomplexity）；随机位数目、信道带宽、数据总量等算法复杂性的表示符号为“O”（称为“大O”），表示计算复杂性的数量级。一个算法的复杂性通常被记为f(n)=O(g(n)。当f(n)=arnr+ar-1nr-1+.+a1n+a0(r为常数)时，f(n)=O(nr)，所有常数和低阶项均可忽略。具有多项式时间复杂性（O(nr)，r为常数）的算法被称为多项式时间算法。若算法的复杂性为O(tf(n)(t为大于1的常数，f(n)为一个多项式），则称该算法为指数算法。可以按照时间和空间复杂性对算法进行分类（P52表3.1）,66,对一个密码系统进行穷举攻击的时间复杂性与可能的密钥总数成比例，并且是密钥长度的指数函数。若密钥长度为n，则穷举攻击的时间复杂性为O(2n)。,附录：表3.1算法的分类及其运行时间,运算次数,宇宙年龄的,67,2.6问题复杂性,“问题”指的是需要回答的一般性提问。它通常含有若干个参数。当问题的所有参数都有了确定的取值时，称得到了该问题的一个实例（instance）。研究问题的内在复杂性，即在图灵机上解决最难的问题实例所需的最小时间和空间条件。,68,1.图灵机,图灵机是一种具有无限读写存储带的有限状态机，可以被当作一个实际可用的计算模型。确定性图灵机。非确定性图灵机：能够进行猜测。求解一个问题分两个阶段：猜测阶段和验证阶段。,69,2.问题分类,易处理的（tractable）：确定性图灵机上能够在多项式时间内得到处理的问题。称易处理问题的全体为“多项式时间可解类”，记为P。非确定性图灵机上能够在多项式时间内得到处理的问题被称为“非确定性多项式时间可解问题”，简称NP问题。NP问题的全体被称为“非确定性多项式时间可解类”，记为NP。NP完全问题：指NP中的任何一个问题都可以通过多项式时间转化为该问题（SAT？）。NP完全问题的全体被记为NPC。NP完全问题是NP问题中最难的问题。,70,2.7零知识证明,零知识证明的基本思想是向别人证明你知道某种事物或具有某种东西，而且别人并不能通过你的证明知道这个事物或东西，也就是不泄露你掌握的这些信息。即证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明条件包括：最小泄露证明（MininumDisclosureProof）和零知识证明（ZeroKnowledgeProof）。实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。,71,假设用P表示示证者，V表示验证者，要求：（1）P几乎不可能欺骗V，若P知道证明，则可使V几乎确信P知道证明；若P不知道证明，则P使V相信P知道的概率几乎为零