安徽工程大学 信息安全原理及应用 第2讲 密码学理论基础

第2讲密码学基础案例：莫尔斯电码里的爱情早已被新科技所取代的莫尔斯密码，却在中国的互联网世界里演绎了一段费尽周折的爱情猜谜传奇。一男子向一女子表白，女子却给了一段莫尔斯密码，以及很少的提示，并表示，破译这个密码，才答应和他约会。男子死活不得求解，又在百度贴吧里将密码贴出以求助网友。电码如下：“****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***--/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/”“她唯一给我的提示就是这个是5层加密的密码，也就是说要破解5层密码才是答案。最终语言是英语。”网友贴出了莫尔斯密码对照表，然后发现相应密码对应的数字组合和英文字母组合分别是：“4194418141634192622374”、“daiddahadafcdaibfbbcgd”①网友“片羿天使”将莫尔斯密码对应的数字“4194418141634192622374”转换成了手机键盘字母,以41为例，它对应的就是传统手机键盘上的“4”的第一个字母，“94”则是“9”的第4个字母。②这样片羿天使得到了第二步的答案：“GZGTGOGXNCS”。③片羿天使说“因为QWE的格式是被世人所认可的，也就有可能成为密码的码表。码表QWE=ABC依次类推。”按照这样的次序，上面的来自于手机键盘的字母，就转换到了第三步答案：“OTOEOIOUYVL”。案例：莫尔斯电码里的爱情④在第四步中，片羿天使用了包括凯撒、乘法等等方法，对第三步几乎可以看出来的答案进行了进一步的解码，最后发现只有栅栏密码才能读得通。片羿天使将这组字母分成了“OTOEOI”和“OUYVL”两排，然后对插重组得到第四步的字母排列：“OOTUOYEVOLI”。⑤第五步于是变得最为简单起来，那便是将“OOTUOYEVOLI”倒序排列，即“ILOVEYOUTOO”。案例：莫尔斯电码里的爱情密码学的发展历史(1)自人类社会出现战争便产生了密码Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。JuliusCaesar发明了凯撒密码密码学的发展历史(2)1834年，伦敦大学的实验物理学教授惠斯顿发明了电机，这是通信向机械化、电气化跃进的开始，也为密码通信采用在线加密技术提供了前提条件。1920年，美国电报电话公司的弗纳姆发明了弗纳姆密码。其原理是利用电传打字机的五单位码与密钥字母进行模2相加。密码学的发展历史(3)两次世界大战大大促进了密码学的发展。二战中美国陆军和海军使用的条形密码设备M-138-T4。根据1914年ParkerHitt的提议而设计。25个可选取的纸条按照预先编排的顺序编号和使用，主要用于低级的军事通信。Kryha密码机大约在1926年由AlexandervoKryha发明。这是一个多表加密设备，密钥长度为442，周期固定。一个由数量不等的齿的轮子引导密文轮不规则运动。密码学的发展历史(4)两次世界大战大大促进了密码学的发展。转轮密码机ENIGMA，由ArthurScherbius于1919年发明，面板前有灯泡和插接板；4轮ENIGMA在1942年装备德国海军，英国从1942年2月到12月都没能解读德国潜艇的信号。英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。密码学的发展历史(5)1949年香农发表了一篇题为《保密系统的通信理论》的著名论文，该文首先将信息论引入了密码，从而把已有数千年历史的密码学推向了科学的轨道，奠定了密码学的理论基础。1976年，美国密码学家W.Diffie和M.Hellman在一篇题为《密码学的新方向》一文中提出了一个崭新的思想，不仅加密算法本身可以公开，甚至加密用的密钥也可以公开。1977年美国国家标准局颁布了数据加密标准DES2001年11月26日，正式颁布AES为美国国家标准。2.2基本概念什么是密码学密码学是关于加密和解密变换的一门科学，是保护数据和信息的有力武器。密码是什么?密码就是变换。（信息代码变换、数据电平变换）变换是什么？变换是一种算法实现过程。谁来做变换？变换可以由硬件和软件实现。（人、器件部件、计算机）2.2基本概念什么是密码学密码学是研究密码系统或通信安全的一门学科，分为密码编码学和密码分析学。密码编码学是使得消息保密的学科密码分析学实际要研究加密消息破译的学科Shannon模型X,明文（plain-text）：作为加密输入的原始信息。Y,密文（cipher-text）：对明文变换的结果。E,加密（encrypt）：是一组含有参数的变换。D,解密（decrypt）：加密的逆变换。Z,密钥（key）：是参与加密解密变换的参数。密码系统（Cryptosystem）定义:(密码体制）它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足。EekDdkCPek:PCdk:Pxxxedkk,,))((这里Kk密码体制的分类几种不同的分类标准按操作方式进行分类操作方式：是明文变换成密文的方法。替代操作、置换操作、复合操作。按照使用密钥的数量进行分类对称密钥（单密钥）。公开密钥（双密钥）。按照对明文的处理方法进行分类流密码。分组密码。按加解密采用的密钥不同按密码出现的时间不同古典密码现代密码密码学（Cryptology）(Symmetriccipher)(Asymmetriccipher)分组密码流密码公钥密码按加密的方式对称密码非对称密码(Classicalcipher)(Moderncipher)(Blockcipher)(Streamcipher)(Public-Keycipher)密码系统的分类(2)根据明文和密文的处理方式分类分组密码体制（BlockCipher）设M为明文，分组密码将M划分为一系列明文块Mi，通常每块包含若干字符，并且对每一块Mi都用同一个密钥Ke进行加密。M=(M1,M2,…,Mn)，C=(C1,C2,…,Cn,)，其中Ci=E(Mi,Ke)，i=1,2…,n。序列密码体制（StreamCipher）将明文和密钥都划分为位(bit)或字符的序列，并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密。M=(M1,M2,…,Mn)，Ke=(ke1,ke2,…,ken)，C=(C1,C2,…,Cn)，其中Ci=E(mi,kei)，i=1,2,…,n。密码系统的分类(3)根据加密算法是否变化分类设E为加密算法，K0,K1,…,Kn,为密钥，M0,M1,…,Mn为明文，C为密文固定算法密码体制C0=E(M0,K0),C1=E(M1,K1),...,Cn=E(Mn,Kn)变化算法密码体制C0=E1(M0,K0),C1=E2(M1,K1),...,Cn=En(Mn,Kn)密码分析截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。密码分析密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别密码设计是利用数学来构造密码密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力……，有时还靠点运气。密码分析方法—分析法确定性分析法利用一个或几个已知量(比如，已知密文或明文-密文对)用数学关系式表示出所求未知量(如密钥等)。已知量和未知量的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关键步骤。统计分析法利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。密码分析方法--穷举破译法对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；一般来说，要获取成功必须尝试所有可能密钥的一半。或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法(Completetrial-and-errorMethod)。只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。柯克霍夫斯(Kerckhoffs)假设假定：密码分析者知道对方所使用的密码系统包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法）、密钥空间及其统计特性。不知道密钥。密码体制的安全性仅应依赖于对密钥的保密，而不应依赖于对算法的保密。只有在假设攻击者对密码算法有充分的研究，并且拥有足够的计算资源的情况下仍然安全的密码才是安全的密码系统。一切秘密寓于密钥之中密码分析密码分析：从密文推导出明文或密钥。密码分析：常用的方法有以下4类：惟密文攻击（cybertextonlyattack）：密码分析者有一个或更多的用同一个密钥加密的密文，通过对这些截获的密文进行分析得出明文或密钥已知明文攻击（knownplaintextattack）：除要破译的密文外，密码分析者有一些明文和用同一密钥加密这些明文所对应的密文。选择明文攻击（chosenplaintextattack）：密码分析者可得到所需要的任何明文所对应的密文，这些密文与要破译的密文是用同一个密钥加密得来的选择密文攻击（chosenciphertextattack）：密码分析者可得到所需要的任何密文所对应的明文，解密这些密文所使用的密钥与要破译的密文的密钥是相同的密码分析密码系统一个好的密码系统应满足：系统理论上安全，或计算上安全；系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密；加密和解密算法适用于密钥空间中的所有元素；系统既易于实现又便于使用。加密的功能保密性：基本功能，使非授权者无法知道消息的内容。鉴别：消息的接收者应该能够确认消息的来源。完整性：消息的接收者应该能够验证消息在传输过程中没有被改变。不可否认性：发送方不能否认已发送的消息。古典加密技术从古到今有无数种加密方法，但归类起来，古代主要是代替密码、置换密码以及两者的结合。代替密码简单代替密码多码代替密码多字母代替密码多表代替密码置换密码：换位密码传统密码及其破译Scytale密码和恺撒密码最先有意识的使用一些技术的方法来加密信息的可能是公元前500年的古希腊人。他们使用的是一根叫scytale的棍子。送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人。如果不知道棍子的粗细是不可能解密里面的内容的，如下图所示。公元前50年，著名的恺撒大帝发明了一种密码叫做恺撒密码。在恺撒密码中，每个字母都与其后第三位的字母对应，然后进行替换。如果到了字母表的末尾，就回到开始，如此形成一个循环。当时罗马的军队就用恺撒密码进行通信。恺撒密码明文字母表：ABCDEFG…XYZ恺撒密码密文字母表：DEFGHIJ…ABC26个字符代表字母表的26个字母，从一般意义上说，也可以使用其它字符表，一一对应的数字也不一定要是3，可以选其它数字。Caesar密码乘数密码算法加密函数取形式为e(x)=ax(mod26)，a∈Z26要求唯一解的充要条件是gcd(a,26)=1该算法描述为：设P=C=Z26，K={a∈Z26|gcd(a,26)=1},对k=a∈K,定义