第2章密码学概论教材

2024/3/19第2章密码学基础2024/3/19密码学作为信息安全理论与技术的基石，在信息安全领域发挥着中流砥柱的作用。密码学理论的应用，成为现代信息网络得以生存和不断发展的基本前提。Cryptography=crypto+graphy

密码隐藏或秘密写

一般来讲，人们通常认为密码学是一种将信息表述为不可读内容的方式（加密），并且可以采用一种秘密方法将信息恢复出来（解密）。

2024/3/192.1密码学的发展历史自人类社会出现战争便产生了密码JuliusCaesar发明了凯撒密码二战时德国使用Enigma机器加密美国军事部门使用纳瓦霍语(Navaho)通信员密码由军事走向生活电子邮件自动提款机电话卡2024/3/19三个阶段：1949年之前密码学还称不上一门科学1949～1975年

《保密系统的通信理论》

密码学成为科学1976年以后密码学的新方向——公钥密码学2024/3/19密码学的发展历史(1)自人类社会出现战争便产生了密码

Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。JuliusCaesar发明了凯撒密码2024/3/19密码学的发展历史(2)1834年，伦敦大学的实验物理学教授惠斯顿发明了电机，这是通信向机械化、电气化跃进的开始，也为密码通信采用在线加密技术提供了前提条件。1920年，美国电报电话公司的弗纳姆发明了弗纳姆密码。其原理是利用电传打字机的五单位码与密钥字母进行模2相加。2024/3/19美国电报电话公司的弗纳姆发明了弗纳姆密码

11010+111010011100111+11101110102024/3/19密码学的发展历史(3)两次世界大战大大促进了密码学的发展。二战中美国陆军和海军使用的条形密码设备M-138-T4。根据1914年ParkerHitt的提议而设计。25个可选取的纸条按照预先编排的顺序编号和使用，主要用于低级的军事通信。Kryha密码机大约在1926年由AlexandervoKryha发明。这是一个多表加密设备，密钥长度为442，周期固定。一个由数量不等的齿的轮子引导密文轮不规则运动。2024/3/19密码学的发展历史(4)两次世界大战大大促进了密码学的发展。转轮密码机ENIGMA，由ArthurScherbius于1919年发明，面板前有灯泡和插接板；4轮ENIGMA在1942年装备德国海军，英国从1942年2月到12月都没能解读德国潜艇的信号。英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。2024/3/19密码学的发展历史(5)1949年香农发表了一篇题为《保密系统的通信理论》的著名论文，该文首先将信息论引入了密码，从而把已有数千年历史的密码学推向了科学的轨道，奠定了密码学的理论基础。1976年，美国密码学家W.Diffie和M.Hellman在一篇题为《密码学的新方向》一文中提出了一个崭新的思想，不仅加密算法本身可以公开，甚至加密用的密钥也可以公开。1977年美国国家标准局颁布了数据加密标准DES2001年11月26日，正式颁布AES为美国国家标准。

2024/3/19定义密码学是一门研究秘密信息的隐写技术的学科；密码学技术可以使消息的内容对(除发送者和接收者以外的)所有人保密；可以使接收者验证消息的正确性；是解决计算机与通信安全问题重要技术。2024/3/192.2密码学的基本概念(1)密码技术的基本思想是伪装信息。

伪装就是对数据施加一种可逆的数学变换，伪装前的数据称为明文，伪装后的数据称为密文，伪装的过程称为加密，去掉伪装恢复明文的过程称为解密。加密和解密的过程要在密钥的控制下进行。

2024/3/19密码学的基本概念(2)密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支

密码编码学(Cryptography)，研究各种加密方案的学科，是对信息进行编码实现隐蔽信息的一门学问。加密方案则被称为密码体制或者密码。

密码分析学(Cryptanalytics)，研究破译密码的学科，是研究分析破译密码的学问。2024/3/19

明文(消息)(Plaintext)：被隐蔽消息。密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。加密(Encryption)：将明文变换为密文的过程。解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员或密码员(Cryptographer)：对明文进行加密操作的人员。密码学的基本概念(3)2024/3/19

加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。密码学的基本概念(4)2024/3/19一个密码系统，通常简称为密码体制，由5部分组成：明文空间M全体明文的集合密文空间C全体密文的集合密钥空间K全体密钥的集合加密算法E一组由M到C的加密变换解密算法D一组由C到M的解密变换密码体制基本组成2024/3/19信息加密传输的过程2024/3/19加密:C=E(M,Ke)MCEKeCMKdD解密:M=D(C,Kd)M------明文C------密文Ke-----加密密钥Kd-----解密密钥E-------加密算法D------解密算法2024/3/19明文加密算法加密密钥K1网络信道解密算法明文解密密钥K2密文用户A用户B传送给B的信息B收到信息窃听者CC窃听到的信息!@#$%^2024/3/19注意数据安全基于密钥而不是算法的保密。也就是说，对于一个密码体制，其算法是可以公开的，让所有人来使用、研究。但具体对于某次加密过程中所使用的密钥，则是保密的。例如，加密算法为Y=aX+b，其中，X为明文，计算后Y成为密文。在具体加密过程中，a、b的取值为密钥，假设为（2，3），明文为2，则密文计算后为7。在这个过程中，Y=aX+b可以公开，但具体a=2，b=3的取值不公开。所以即使对方知道了采用的加密算法，由于不知道具体参数取值，也无法根据密文计算出明文。2024/3/19密码的设计应当遵循公开设计原则DES采用公开征集、公开评价的原则，实践证明DES是安全的。AES，又采用在全世界范围的公开征集、公开评价的原则，可以预计AES是安全的。世界各国的军政核心密码都不公开其加密算法（在内部充分公开、讨论）。2024/3/192.3密码系统的分类(1)根据密钥的使用方式分类

对称密码体制（秘密钥密码体制）用于加密数据的密钥和用于解密数据的密钥相同，或者二者之间存在着某种明确的数学关系。加密：EK(M)=C解密：DK(C)=M非对称密码体制（公钥密码体制）用于加密的密钥与用于解密的密钥是不同的，而且从加密的密钥无法推导出解密的密钥。用公钥KP对明文加密可表示为：EKP(M)=C用相应的私钥KS对密文解密可表示为：DKS(C)=M2024/3/19密码系统的分类(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。

2024/3/19密码系统的分类(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)

2024/3/192.4密码分析Cryptanalysis

截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。2024/3/19密码分析

密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别

密码设计是利用数学来构造密码密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力……，有时还靠点运气。2024/3/19密码分析方法—分析法

确定性分析法利用一个或几个已知量(比如，已知密文或明文-密文对)用数学关系式表示出所求未知量(如密钥等)。已知量和未知量的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关键步骤。

统计分析法利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。2024/3/19

密码可能经受的攻击

对密码进行分析的尝试称为攻击攻击类型攻击者拥有的资源惟密文攻击Ciphertextonly加密算法截获的部分密文已知明文攻击Knownplaintext加密算法，截获的部分密文和相应的明文选择明文攻击Chosenplaintext加密算法加密黑盒子，可加密任意明文得到相应的密文选择密文攻击Chosenciphertext加密算法解密黑盒子，可解密任意密文得到相应的明文2024/3/19密码分析方法--穷举破译法

Brute-forceattack

对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；一般来说，要获取成功平均尝试所有可能密钥的一半。

或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法(Completetrial-and-errorMethod)。只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。

2024/3/19注意Internet的广泛应用，可以把全世界的计算机资源连成一体，形成巨大的计算能力，从而拥有巨大的密码破译能力，使原来认为安全的密码被破译。1994年，40多个国家的600多位科学家通过Internet，历时9个月破译了RSA-129密码，1999年又破译了RSA-140密码，2005年，RSA-200也被成功破译。1997年6月18日美国科罗拉多州以RockeVerser为首的工作小组宣布，通过利用Internet上的数万台微机，历时4个多月，通过穷举破译了DES。因此，在21世纪，只有经得起通过Internet进行全球攻击的密码，才是安全的密码。2024/3/19两个概念unconditionallysecure无条件安全无论有多少可使用的密文，都不足以唯一地确定密文所对应的明文。computationallysecure计算上安全Thecostofbreakingthecipherexceedsthevalueoftheencryptedinformation.Thetimerequiredtobreakthecipherexceedstheusefullifetimeoftheinformation.2024/3/19破译56位DES的成本单位:美元2024/3/19一个数量级概念赢得彩票头等奖并在同一天被闪电杀死的可能性1/2552024/3/19统计的观点某种计算资源破译需要一年时间,在一个月内破译的可能性8%,若穷举需要一个月时间,则一小时内破译的可能性是0.14%2024/3/192.5经典密码学

ClassicalEncryption古典密码与现代密码的区别古典密码对于今天来说，是极不安全的，是极易破解的，但其基本方法仍然是近、现代密码学的基础之一。古典密码运用的两种基本技术：代换法SubstitutionTechniques

置换法TranspositionTechniques2024/3/192.5.1代换密码代换法，是将明文字母替换成其他字母、数字或符号的方法。

Caesar密码（已知的最早的代换密码）例如：明晨五点发动反攻明文：MINGCHENWUDIANFADONGFANGONG密文：PLQJFKHQZXGLDQIDGRQJIDQJRQJ2024/3/19CaesarCipher凯撒密码如果让每个字母等价于一个数值：则加密公式为：

C=E(p)=(p+3)mod26更一般地：

C=E(p)=(p+k)mod26解密：p=D(C)=(C-k)mod262024/3/19用穷举分析可轻松破解Caesar密码通常，加密和解密算法是已知的。需测试的密钥只有25个。明文所用的语言是已知的，其意义易于识别。因此，为了提高穷举分析的难度，密钥空间必须很大。例如3-DES算法的密钥长度为168位，密钥空间为2168。2024/3/19单表代换密码使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。例如，明文a用c来代换，b用剩下的25个字母中随机的一个来代换，c用剩下的24个字母中随机的一个来代换，……，以此类推。这样，密钥空间为26！，约4*1026种可能的密钥。2024/3/19破解单表代换密码根据频率统计进行分析确定每个字母被映射到什么字母单个字母出现的可能是A或I一般来说3个字母出现的可能是THE或AND还可以用其他通常出现的双字母或三字母组合还可以应用其它很少应用的字母2024/3/19最常见的两字母组合，依照出现次数递减的顺序排列：TH、HE、IN、ER、AN、RE、DE、ON、ES、ST、EN、AT、TO、NT、HA、ND、OU、EA、NG、AS、OR、TI、IS、ET、IT、AR、TE、SE、HI、OF最常见的三字母组合，依照出现次数递减的顺序排列：THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH2024/3/192024/3/192024/3/19改变明文的语法模式和结构

------抵抗频度分析可采用多表代换密码polyalphabeticsubstitutioncipherPlayfair密码Hill密码Vigenere密码采用相关的单表代换规则由密钥来决定给定变换的具体规则2024/3/19最著名的多表代换加密体制--Playfair由英国科学家CharlesWheatstone于1854年发明，以其好友BaronPlayfair的名字命名。在第一次世界大战中，英军使用Playfair密码作为陆军的标准加密体制。在第二次世界大战中，盟军使用它作为通信加密工具。2024/3/19LordPeterWimsey给出的例子Playfair算法基于使用一个5×5字母矩阵，该矩阵使用一个关键词构造。从左至右、从上至下填入该关键词的字母（去除重复字母），然后再以字母表顺序将余下的字母填入矩阵剩余空间。字母I和J被算作一个字母。MONARCHYBDEFGI/JKLPQSTUVWXZ2024/3/19属于相同对中的重复的明文字母将用一个填充字母进行分隔,比如x：因此，词balloon将被加密为balxloon。属于该矩阵相同行的明文字母将由其右边的字母替代，而行的最后一个字母由行的第一个字母代替。例如，ar被加密为RM。属于相同列的明文字母将由它下面的字母代替，而列的最后一个字母由列的第一个字母代替。例如，mu被加密为CM否则，明文的其他字母将由与其同行，且与下一个同列的字母代替。因此，hs成为BP，ea成为IM（或JM，这可根据加密者的意愿而定）。代换规则2024/3/19Playfair密码的优点Playfair密码与简单的单一字母替代法密码相比有了很大的进步虽然仅有26个字母，但有26×26＝676种字母对，因此，识别字母对要比单个字母要困难得多一个明文字母有多种可能的代换密文字母，使得频率分析困难的多(hs成为BP,hq成为YP)。由于这些原因，Playfair密码过去长期被认为是不可破的。2024/3/19最简单的多表代换密码---Vigenère维吉尼亚密码选择一个词组作为密钥，密钥中每个字母用来确定一个代换表，每个密钥字母用来加密一个明文字母。例如密钥字母为b，明文字母为c，则密文字母为(2+1)mod26=3，也就是d。直到所有的密钥字母用完，后再从头开始，使用第一个密钥字母加密。也就是说，密钥循环使用。2024/3/19一个例子明文为attackbeginsatfive，密钥为cipher，

attackbeginsatfive明文＋cipherciphercipher密钥

----------------------------------------------

＝cbihgbdmvprjcbupzv密文去除空格后为cbihgbdmvprjcbupzv2024/3/19破解维吉尼亚密码的一个途径如果密文足够长，其间会有大量重复的密文序列出现。通过计算重复密文序列间距的公因子，分析者可能猜出密钥词的长度（因为密钥词是重复使用的）。2024/3/19无法攻破的加密体制One-TimePad有一种理想的加密方案，叫做一次一密乱码本,由MajorJosephMauborgne和AT&T公司的GilbertVernam在1917发明。一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并被粘成一个乱码本。发送者用每一个明文字符和一次一密乱码本密钥字符的模26加法。每个密钥仅对一个消息使用一次。发送者对所发送的消息加密，然后销毁乱码本中用过的一页或磁带部分。接收者有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。接收者在解密消息后销毁乱码本中用过的一页或磁带部分。新的消息则用乱码本中新的密钥加密。

2024/3/19一次一密的优点面对一条待破译的密文，攻击者能够找到很多个与密文等长的密钥，使得破译出的明文符合语法结构的要求，因为密钥本身是随机的，是没有规律的。就算在这些可能的密钥中存在真正的密钥，攻击者也无法在这些可能的密钥中确定真正的密钥，因为密钥只是用一次，攻击者无法用其它密文来验证这个密钥，因此是无法攻破的。2024/3/192024/3/19一次一密的缺点一个一次一密加密系统，需要在某个规则基础上建立百万个随机字符，提供这样规模的真正随机字符集市相当艰巨的任务。对每一条消息，需要提供给发送发和接收方等长度的密钥，因此存在庞大的密钥分配问题。基于这些原因，一次一密在实际中极少应用。2024/3/19置换技术

TranspositionTechniques在置换密码中，明文的字母保持相同，但顺序被打乱了。在简单的纵行换位密码中，明文以固定的宽度水平地写在一张图表纸上，密文按垂直方向读出，解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。2024/3/19Plaintext:COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECOMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECiphertext:CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX

这种简单的技巧对于密码分析者来说是微不足道的。可在置换前，把列的次序打乱，列的次序就是算法的密钥。2024/3/19代换技术与置换技术通常结合使用。一般地，可先利用代换技术加密，再用置换技术将密文再次加密。2024/3/192.5.3古典密码（机械阶段）

---转轮机RotorMachines20世纪20年代，随着机械和机电技术的成熟，以及电报和无线电需求的出现，引起了密码设备方面的一场革命——发明了转轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的重要标志之一。美国人EdwardHebern认识到：通过硬件卷绕实现从转轮机的一边到另一边的单字母代替，然后将多个这样的转轮机连接起来，就可以实现几乎任何复杂度的多个字母代替。转轮机由一个键盘和一系列转轮组成，每个转轮是26个字母的任意组合。转轮被齿轮连接起来，当一个转轮转动时，可以将一个字母转换成另一个字母。照此传递下去，当最后一个转轮处理完毕时，就可以得到加密后的字母。为了使转轮密码更安全，人们还把几种转轮和移动齿轮结合起来，所有转轮以