第2章密码学基础课件.ppt

第2章 密码学基础,主要内容,密码学的发展历史密码学的基本概念密码系统的分类密码分析经典密码学,密码学的发展历史(1),自人类社会出现战争便产生了密码,Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。,Julius Caesar发明了凯撒密码,密码学的发展历史(2),1834年，伦敦大学的实验物理学教授惠斯顿发明了电机，这是通信向机械化、电气化跃进的开始。1920年，美国电报电话公司的弗纳姆发明了弗纳姆密码。其原理是利用电传打字机的五单位码与密钥字母进行模2相加。,密码学的发展历史(3),两次世界大战大大促进了密码学的发展。,二战中美国陆军和海军使用的条形密码设备M-138-T4。,Kryha密码机大约在1926年由Alexander vo Kryha发明。这是一个多表加密设备，密钥长度为442，周期固定。一个由数量不等的齿的轮子引导密文轮不规则运动。,密码学的发展历史(4),两次世界大战大大促进了密码学的发展。,转轮密码机ENIGMA，由Arthur Scherbius于1919年发明，面板前有灯泡和插接板；4轮ENIGMA在1942年装备德国海军，英国从1942年2月到12月都没能解读德国潜艇的信号。,英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。,密码学的发展历史(5),1949年香农发表了一篇题为保密系统的通信理论的著名论文，奠定了密码学的理论基础。 1976年，美国密码学家W.Diffie和M.Hellman在一篇题为密码学的新方向一文中提出，不仅加密算法本身可以公开，甚至加密用的密钥也可以公开。1977年美国国家标准局颁布了数据加密标准DES 2001年11月26日，正式颁布AES为美国国家标准。,密码学的基本概念(1),密码学是关于加密和解密变换的一门科学，是保护数据和信息的有力武器。,密码学的基本概念(2),密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问密码分析学(Cryptanalytics)，研究分析破译密码的学问。,明文(消息)(Plaintext) ：被隐蔽消息。 密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。 加密(Encryption)：将明文变换为密文的过程。 解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。,密码学的基本概念(3),加密算法(Encryption algorithm)：密码员对明文进行加密时所采用的一组规则。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。,密码学的基本概念(4),密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。 被动攻击(Passive attack)：对一个保密系统采取截获密文进行分析的攻击。 主动攻击(Active attack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。,密码学的基本概念(5),信息加密传输的过程,用户A,用户B,传送给B的信息,B收到信息,C窃听到的信息!#$%,注意,数据安全基于密钥而不是算法的保密。也就是说，对于一个密码体制，其算法是可以公开的，让所有人来使用、研究。但具体对于某次加密过程中所使用的密钥，则是保密的。例如，加密算法为Y=aX+b，其中，X为明文，计算后Y成为密文。在具体加密过程中，a、b的取值为密钥，假设为（2，3），明文为2，则密文计算后为7。在这个过程中，Y=aX+b可以公开，但具体a=2，b=3的取值不公开。所以即使对方知道了采用的加密算法，由于不知道具体参数取值，也无法根据密文计算出明文。,密码系统的分类(1),根据密钥的使用方式分类 对称密码体制（秘密钥密码体制）用于加密数据的密钥和用于解密数据的密钥相同，或者二者之间存在着某种明确的数学关系。 加密：EK(M)=C解密：DK(C)=M 非对称密码体制（公钥密码体制）用于加密的密钥与用于解密的密钥是不同的，而且从加密的密钥无法推导出解密的密钥。 用公钥KP对明文加密可表示为：EKP(M)=C用相应的私钥KS对密文解密可表示为：DKS(C)=M,密码系统的分类(2),根据明文和密文的处理方式分类 分组密码体制（Block Cipher） 设M为明文，分组密码将M划分为一系列明文块Mi，通常每块包含若干字符，并且对每一块Mi都用同一个密钥Ke进行加密。M=(M1, M2, ,Mn) ，C=(C1, C2 , ,Cn,)，其中Ci=E(Mi,Ke)， i=1,2,n。序列密码体制（Stream Cipher）将明文和密钥都划分为位(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),密码分析,截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。,密码分析方法-穷举破译法,对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；一般来说，要获取成功必须尝试所有可能密钥的一半。,注意,Internet的广泛应用，可以把全世界的计算机资源连成一体，形成巨大的计算能力，从而拥有巨大的密码破译能力，使原来认为安全的密码被破译。1994年，40多个国家的600多位科学家通过Internet，历时9个月破译了RSA-129密码，1999年又破译了RSA - 140密码，2005年，RSA-200也被成功破译。1997年6月18日美国科罗拉多州以Rocke Verser为首的工作小组宣布，通过利用Internet上的数万台微机，历时4个多月，通过穷举破译了DES。因此，在21世纪，只有经得起通过Internet进行全球攻击的密码，才是安全的密码。,经典密码学,经典密码（古典密码）对于今天来说，是极不安全的，是极易破解的，但其基本方法仍然是近、现代密码学的基础。经典密码运用的两种基本技术： 代换法：将明文字母替换成其他字母、数字或符号 置换法：明文的字母保持相同，但顺序被打乱,代换技术,代换法，是将明文字母替换成其他字母、数字或符号的方法。 Caesar密码（已知的最早的代换密码）,例如：明晨五点发动反攻明文：MING CHEN WU DIAN FA DONG FAN GONG密文：PLQJ FKHQ ZX GLDQ ID GRQJ IDQ JRQJ,用穷举分析可轻松破解Caesar密码,通常，加密和解密算法是已知的。需测试的密钥只有25个。明文所用的语言是已知的，其意义易于识别。,单表代换密码,使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。例如，明文a用c来代换，b用剩下的25个字母中随机的一个来代换，c用剩下的24个字母中随机的一个来代换，以此类推。这样，密钥空间为26！，约4*1026种可能的密钥。,破解单表代换密码,根据频率统计进行分析确定每个字母被映射到什么字母单个字母出现的可能是A或I一般来说3个字母出现的可能是THE或AND还可以用其他通常出现的双字母或三字母组合还可以应用其它很少应用的字母,最常见的两字母组合，依照出现次数递减的顺序排列：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、DTH,改变明文的语法模式和结构-抵抗频度分析,可采用多表代换密码Playfair密码Hill密码Vigenre密码采用相关的单表代换规则由密钥来决定给定变换的具体规则,最著名的多表代换加密体制-Playfair,由英国科学家Charles Wheatstone于1854年发明，以其好友Baron Playfair的名字命名。在第一次世界大战中，英军使用Playfair密码作为陆军的标准加密体制。在第二次世界大战中，盟军使用它作为通信加密工具。,Lord Peter Wimsey给出的例子,Playfair算法基于使用一个55字母矩阵，该矩阵使用一个关键词构造。从左至右、从上至下填入该关键词的字母（去除重复字母），然后再以字母表顺序将余下的字母填入矩阵剩余空间。字母I和J 被算作一个字母。,属于相同对中的重复的明文字母将用一个填充字母进行分隔，因此，词balloon将被加密为ba lx lo on。 属于该矩阵相同行的明文字母将由其右边的字母替代，而行的最后一个字母由行的第一个字母代替。例如，ar被加密为RM。 属于相同列的明文字母将由它下面的字母代替，而列的最后一个字母由列的第一个字母代替。例如，mu被加密为CM否则，明文的其他字母将由与其同行，且与下一个同列的字母代替。因此，hs成为BP，ea成为IM（或JM，这可根据加密者的意愿而定）。,代换规则,Playfair密码的优点,Playfair密码与简单的单一字母替代法密码相比有了很大的进步 虽然仅有26个字母，但有2626676种字母对，因此，识别字母对要比单个字母要困难得多 一个明文字母有多种可能的代换密文字母，使得频率分析困难的多(hs成为BP, hq成为YP)。由于这些原因，Playfair密码过去长期被认为是不可破的。,最简单的多表代换密码-Vigenre,维吉尼亚密码选择一个词组作为密钥，密钥中每个字母用来确定一个代换表，每个密钥字母用来加密一个明文字母。例如密钥字母为a，明文字母为c，则密文字母为0+2(mod26)=2，也就是c。直到所有的密钥字母用完，后再从头开始，使用第一个密钥字母加密。也就是说，密钥循环使用。,一个例子,明文为attack begins at five，密钥为cipher， attack begins at five 明文 cipher cipher ci pher 密钥 - cbihgb dmvprj cb upzv 密文去除空格后为cbihgbdmvprjcbupzv,一次一密-无法攻破的加密体制,一次一密乱码本（one-time pad）, 由Major Joseph Mauborgne 和AT&T公司的Gilbert Vernam 在1917发明。一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并被粘成一个乱码本。发送者用每一个明文字符和一次一密乱码本密钥字符的模26加法。 每个密钥仅对一个消息使用一次。发送者对所发送的消息加密，然后销毁乱码本中用过的一页或磁带部分。接收者有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。接收者在解密消息后销毁乱码本中用过的一页或磁带部分。新的消息则用乱码本中新的密钥加密。,置换技术,在置换密码中，明文的字母保持相同，但顺序被打乱了。在简单的纵行换位密码中，明文以固定的宽度水平地写在一张图表纸上，密文按垂直方向读出，解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。,Plaintext: COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVEC O M P U T E R G RA P H I C S M A Y BE S L O W B U T A TL E A S T I T S E XP E N S I V ECiphertext: CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX,这种简单的技巧对于密码分析者来说是微不足道的。可在置换前，把列的次序打乱，列的次序就是算法的密钥。,代换技术与置换技术通常结合使用。一般地，可先利用代换技术加密，再用置换技术将密文再次加密。,转轮机-经典密码的机械阶段,20世纪20年代，随着机械和机电技术的成熟，以及电报和无线电需求的出现，引起了密码设备方面的一场革命发明了转轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的重要标志之一。美国人Edward Hebern认识到：通过硬件卷绕实现从转轮机的一边到另一边的单字母代替，然后将多个这样的转轮机连接起来，就可以实现几乎任何复杂度的多个字母代替。转轮机由一个键盘和一系列转轮组成，每个转轮是26个字母的任意组合。转轮被齿轮连接起来，当一个转轮转动时，可以将一个字母转换成另一个字母。照此传递下去，当最后一个转轮处理完毕时，就可以得到加密后的字母。为了使转轮密码更安全，人们还把几种转轮和移动齿轮结合起来，所有转轮以不同的速度转动，并且通过调整转轮上字母的位置和速度为破译设置更大的障碍。,转轮机的工作原理,每一个旋转轮代表一个单表代换系统，旋转一个引脚，再转变为另一个单表代换系统。为使机器更安全，可把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26n，即个单表代换系统。最后一个转轮转完一圈之后，它前面的转轮就旋转一个引脚，有点像时钟的齿轮。,转轮机的经典-ENIGMA,1918年，德国发明家Arthur Scherbius用二十世纪的电气技术来取代已经过时的铅笔加纸的加密方法。 他研究的结果就是永远被尊为经典的ENIGMA。ENIGMA首先是作为商用加密机器得到应用的。它的专利在1918年在美国得到确认。售价大约相当于现在的30000美元 。,ENIGMA在二战中的传奇,二战中德国军队大约装备了三万台ENIGMA。在第二次世界大战开始时，德军通讯的保密性在当时世界上无与伦比。ENIGMA在纳粹德国二战初期的胜利中起到的作用是决定性的。,精密的转轮,破解ENIGMA,波兰人在1934年，研究出了破译ENIGMA的方法。德国人在1938年底又对ENIGMA作了大幅度改进。1939年7月25日，波兰情报部门邀请英国和法国的情报部门共商合作破译ENIGMA。 1939年7月，英国情报部门在伦敦以北约80公里的一个叫布莱奇利的地方征用了一所庄园。一个月后，鲜为人知的英国政府密码学校迁移到此。不久，一批英国数学家也悄悄来到这所庄园，破译恩尼格玛密码的工作进入了冲刺阶段。在这里刚开始时只有五百人，战争结束时已经增加到了七千人。 为了破译ENIGMA，英国人将国内最优秀的数学家悉数照进庄园。其中就有从剑桥来的图灵。正是他打破了ENIGMA不可战胜的神话。 虽然英国人成功的破译了ENIGMA，但是他们极好地隐藏了这一点，使得战争的进程大大加速 。,从海里打捞起来的二战中用到的ENIGMA,隐蔽通道和隐写术,严格来说，隐蔽通道和隐写术这两种技术并不是加密，而是隐藏。它们隐藏明文信息的存在，而密码学通过对文本信息的不同转换而实现信息对外的不可读。同加密相比，隐蔽通道和隐写术有一些缺点，它需要许多额外的付出来隐蔽相对较少的信息。尽管采用一些上述的方案也许有效，但是一旦被破解，整个方案就毫无价值了。它的优点是可以应用于通信双方宁愿他们的秘密通信被发现而不愿其中的重要内容丢失的情况。,