02密码学基础.ppt

第二章 密码学基础西南财经大学西南财经大学经济信息工程学院经济信息工程学院目 录l2.1 密码学的发展概况密码学的发展概况 l2.2 密码技术的目标密码技术的目标 l2.3 密码学基本概念密码学基本概念 l2.4 替代技术替代技术 l2.5 置换技术置换技术 l2.6 转子机（转子机（Rotor Machine）l2.7 明文处理方式明文处理方式 密码学的发展阶段密码学的发展阶段l第第1阶段阶段：1949年以前密码学是一门艺术古典密码学l第第2阶段阶段：19491975年密码学成为科学现代密码学l第第3阶段阶段：1975年以后密码学的新方向公钥密码学第1阶段 古典密码 l古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。l古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。l到了1860年，密码系统在外交通信中已得到普遍使用。l在第一次世界大战期间，敌对双方都使用加密系统 第第1阶段阶段古典密码古典密码l公元前5世纪，古斯巴达人使用了一种叫做“天书”的器械，这是人类历史上最早使用的密码器械。“天书”是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。古典密码举例古典密码举例棋盘密码棋盘密码 最早的一种密码是在公元前2世纪，由一位希腊人提出来的。他将26个字母排列在一个55的方格里，其中i和j填在同一格。abcdefghijklmnopqrstuvwxyz每个字母对应下列表格中的一个数。比如每个字母对应下列表格中的一个数。比如c对应对应13，r对应对应42等等。等等。11121314152122232425313233343541424344455152535455使用这种密码可以将明文：Please send moneys转换为密文：35 31 15 11 43 15 43 15 33 14 32 34 33 15 54 43在古代这种棋盘密码曾得到广泛的应用。第1阶段古典密码l20世纪早期的“机器加密设备”；l基于转轮的“密码机”；l大约在1793年，当时的美国总统托马斯.杰斐逊发明了一种轮子密码机。转动轮子使明文中的所有字母全排在一条直线上为止这时圆柱体的其他25行字母也因这一行的固定而被固定了任选这25行中的一行发出去即为密文2020世纪早期密码机世纪早期密码机（用于无线电台加密）（用于无线电台加密）古典密码特点古典密码特点l密码学还不是科学，而是艺术；l出现一些简单的密码算法和加密设备；l密码算法的基本手段出现，针对的是字符；l简单的密码分析手段出现；主要特点主要特点：数据的安全基于算法的保密数据的安全基于算法的保密第1阶段 古典密码l1883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文加密算法应建立在算法的公开不影响明文和密钥的安全和密钥的安全。l这个原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为古典密码和现代密古典密码和现代密码的分界线码的分界线。第2阶段 19491975年，理论研究计算机使得基于复杂计算的密码成为可能相关技术的发展l1949年，Shannon的The Communication Theory of Secret Systems将信息论引入到密码学，密码密码理论研究理论研究发展迅速。l1967年David Kahn的The Codebreakersl1971-1973年IBM Watson实验室的Horst Feistel等几篇技术报告主要特点主要特点l数据的安全基于密钥基于密钥而不是算法的保密扩散（Diffusion):明文的统计结构被扩散消失到密文的统计 特性中,使得明文和密文之间的统计关系 尽量复杂 混乱(confusion)：使得密文的统计特性与密钥的取值之间的 关系尽量复杂第2阶段 常规现代密码学 l密码形成一门新的学科是在20世纪70年代，这是由于计算机科学蓬勃发展刺激和推动的结果。l“The Communication Theory of Secrecy Systems”、“The Codebreakers”两篇重要的论文和美国数据加密标准DES的实施，标志着密码学的理论与技术的划时代的革命性变革，宣布了近代密码学的开始。第3阶段 公钥密码学 l1976年W.Diffie和M.Hellman发表了“New Directions in Cryptography”论文，提出了适应网络上保密通信的公钥密码思想 l1978年RSA公钥密码体制的出现，成为公钥密码的杰出代表，并成为事实标准，在密码学史上是一个里程碑 l80年代逐步出现椭圆曲线椭圆曲线等其他公钥算法。主要特点：主要特点：公开密钥算法用一个密钥进行加密，用另一个密钥进行解密，其中的加密密钥可以公开，使得发送端和接收端无密钥传输的保密通信成为可能。第三阶段对称密钥密码算法进一步发展l1977年DES正式成为标准l80年代出现“过渡性”的“post DES”算法,如IDEA,RCx,CAST等l90年代对称密钥密码进一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出现l2001年Rijndael成为DES的替代者l2.1 密码学的发展概况密码学的发展概况 l2.2 密码技术的目标密码技术的目标 l2.3 密码学基本概念密码学基本概念 l2.4 替代技术替代技术 l2.5 置换技术置换技术 l2.6 转子机（转子机（Rotor Machine）l2.7 明文处理方式明文处理方式 密码技术的使用是为了实现密码技术的使用是为了实现4个基本目标：个基本目标：l保密性保密性l完整性完整性l身份认证身份认证l不可抵赖不可抵赖 保密性 l保密性是确保信息双方传输中保持私密，即个体间和组织间保密通信。l主要有两种类型的保密系统对称密钥系统是在密钥系统中的所有用户使用一个共享的密钥公开密钥系统中的每个用户使用一个公开密钥和私有密钥的单独组合。完整性 l完整性是确保信息在传输过程中不被修改。l信息完整性通过使用建立在信息传输过程信息完整性通过使用建立在信息传输过程中信息摘要的数字签名来实现中信息摘要的数字签名来实现。l信息接收者可以简单进行对信息摘要的数字签名进行验证以确定信息的完整性。身份认证 l身份认证是对于宣称的系统用户身份进行鉴别。l假设甲希望和乙建立通信，并且他们都共享一个保密的通信系统，甲可以使用一个质询 响应的身份认证技术确保乙的真实性。不可抵赖 l不可抵赖是为接收者提供担保，保证信息确实来自发送者，它防止发送者否认发送过信息。l对称密钥不提供对不可否认的保证。l不可抵赖由公钥密码系统提供支持。l2.1 密码学的发展概况密码学的发展概况 l2.2 密码技术的目标密码技术的目标 l2.3 密码学基本概念密码学基本概念 l2.4 替代技术替代技术 l2.5 置换技术置换技术 l2.6 转子机（转子机（Rotor Machine）l2.7 明文处理方式明文处理方式 加密的简化模型加密的简化模型 基本概念 l密码学密码学(Cryptology)是研究信息系统安全保密的科学。l密码编码学密码编码学(Cryptography)主要研究对信息进行编码，实现对信息的隐蔽。l密码分析学密码分析学(Cryptanalytics)主要研究加密消息的破译或消息的伪造。l明文明文（Plaintext）是消息的初始形式；l密文密文（CypherText）是加密后的形式。基本概念基本概念 加密加密（encryption）：用某种方法伪装消息以隐藏它的内容的过程。解密解密（decrytion）：把密文转变为明文的过程。明文密文明文 加密解密基本概念基本概念密码算法（algorithm）：是用于加密和解密的数学函数。简单地说它是一组含有参数k的变换。密钥（key）：参数k明文用M表示，密文用C表示，那么加密变换可以这样表示：Ek(M)C解密变换可以这样表示：Dk(C)=M显然有Dk(Ek(M)=M基本概念基本概念根据密钥的特点，我们可以密码算法分为两类：对称密码算法和公钥密码算法。对称密码算法对称密码算法（symmetric algorithm）：也称单钥密码，就是说加密、解密密钥是相同的。公钥密码算法公钥密码算法（public key algorithm）：也称非对称密码，在这里用于加密的密钥不同于用于解密的密钥，而且解密密钥不能根据加密密钥推算出来。加密密钥可以公开，因此也叫公开密钥（public key）简称公钥，解密密钥必须保密，因此也叫私人密钥（private key），简称私钥。常规加密系统的安全性特点常规加密系统的安全性特点 l加密算法足够强大，即仅仅知道密文很难破译出明文。l基于密钥的安全性。l由于现代加密算法具有开放性，因此算法容易实现和使用。常规加密系统的模型常规加密系统的模型 l密码体系可以进行形式化描述，表示成一个五元组（P，C，K，E，D)。l任意密钥kK，有一个加密算法和相应的解密算法，分别使用加密和解密函数，满足Dk(Ek(x)=x，这里x P。密码系统其他分类 l基本加密算法的密码编码系统可以分为：l替代l置换。l按照明文处理的方式不同可以分为：分组密码（block cipher)流密码（stream cipher)。密码分析技术密码分析技术密码分析技术是在不知道密钥(密码算法可能已知，Kerckhoff原则)的情况下，恢复出信息明文的科学。密码分析技术可以发现密码体制的弱点。最常见的攻击方式包括：1.1.唯密文攻击：唯密文攻击：密码分析者拥有一些密文，并试图通过分析密文破译密码。通常需要尝试所有可能的密钥，难度最大。2.2.已知明文攻击已知明文攻击:密码分析者不仅可以得到一些消息的密文，也知道这些消息的明文。(有可能利用字母的替换关系找出某些规律)3.3.选择明文攻击：选择明文攻击：密码分析者能够获得加密设备的暂时访问，因而能选择明文并构造出相应的密文。某些特殊设计的明文有助于破解密码算法。4.4.选择密文攻击选择密文攻击:密码分析者可暂时接近密码机,可选择密文y，并构造出相应的明文x（解密过程）。最终目的在于破译出密钥或密文。密码分析l密码分析需要具备以下方面的条件：l已知加密算法，l截取到明文、密文中已知或推测的数据项，l数学或统计工具l计算机技术，l密码分析是否能够成功还要具有一定的技巧与运气。密码算法的安全性密码算法的安全性l如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为无条件安全的无条件安全的，或称为理论上是不可破的理论上是不可破的。l在无任何限制的条件下，目前几乎所有实用的密码体制均是可破的。因此，人们关心的是要研制出在在计计算算上上(而而不不是是在在理理论论上上)是是不不可可破破的的密密码码体体制制。如果一个密码体制中的密码不能被可以使用的计算资源破译，则这一密码体制称为在计算上是安全的在计算上是安全的。l破译的代价超出信息本身的价值l破译的时间超出了信息的有效期.l2.1 密码学的发展概况密码学的发展概况 l2.2 密码技术的目标密码技术的目标 l2.3 密码学基本概念密码学基本概念 l2.4 替代技术替代技术 l2.5 置换技术置换技术 l2.6 转子机（转子机（Rotor Machine）l2.7 明文处理方式明文处理方式l替代是加密算法利用不同的字符代替明文信息中的每个字符或位，即明文的字母由其它字母、数字或符号代替。l破译威胁来自于：频率分布、重合指数、考虑最可能的字母及可能出现的单词、重复结构分析创造性和运气等。恺撒密码 恺撒密码字母表恺撒密码一种置换密码，通过将字母按顺序推后3位起到加密作用。l恺撒密码的加密算法是：c=E(p)=(p+3)mod 26 改进的恺撒加密算法改进的恺撒加密算法l恺撒加密算法的位移量是3，如果将位移量设置为任何整数，则恺撒密码的改进算法可以写为：加密算法：C=E(p)=(p+k)mod(26)解密算法：p=D(C)=(C-k)mod(26)l改进的恺撒加密算法有25个可能的密钥k l恺撒密码是单字母密码，仅仅采用了简单替换技术，其优点是算法简单，便于记忆。缺点是结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构。因此这种密码的密度是很低的，只需简单地统计字频就可以破译。单字母替代 l如果明码字母表是由26个符号组成，则该字母表存在有26！41026种单字母替代密码。l讨论该类型的一种简单密码，这个密码以一个密钥开始，该密钥是明码字母表中的一个串。l举例：Southeast University l密钥短语密码本 1l密钥短语密码本 2l单一字母替代编码在公元1世纪开始到10世纪使用广泛。l随着统计学和概率的发展，破解单一字母替代编码非常容易。l因为在语言中不同字母出现的概率不同，有些字母常见，有些字母则很少出现。单一字母密码破译 l任意替换具有26！41026 可能的key，大于56位DES的密钥空间，但是使用基于语言统计规律仍可破译。英文字母出现相对频率英文字母出现相对频率 密文语言统计规律密文语言统计规律 多字母替代密码 l例2-1：奇数位的加密算法E1(a)=(3*a)mod 26，偶数位加密算法 E2(a)=(5*a)+13)mod 26)。多字母替代密码表多字母替代密码表1 明文tsinghua university，对应的密文为fzyaswiniayomucbfd 如果明文为如果明文为SWUFE,那么密文应那么密文应为为l例2-2：奇数位的加密算法 E1(a)=a 偶数位的加密算法 E2(a)=25-asduuel2.1 密码学的发展概况密码学的发展概况 l2.2 密码技术的目标密码技术的目标 l2.3 密码学基本概念密码学基本概念 l2.4 替代技术替代技术 l2.5 置换技术置换技术 l2.6 转子机（转子机（Rotor Machine）l2.7 明文处理方式明文处理方式l通过执行对明文字母的置换，取得一种类型完全不同的映射，即置换密码。l若该明文被视为一个比特序列，则置换涉及到用密文比特模式代替明文比特模式。abcdecad be 栅栏技术栅栏技术l明文以Z形栅栏排列，其高度是置换密码的密钥。l令明文为“Meet me at my department”，密钥为2，则Z形栅栏为：l逐行扫描这个Z形栅栏可以生成密文”memamdprmnetetyeatet”矩阵技术 l选择密钥k=k1k2kn，将明文逐行写入一个n行的长方形中。在第i行上，从位置ki处开始写入明文。随后，有左至右逐列读取这些字母就可以生成密文。l明文“we will meet in my department”，密钥23614 l其加密密文为”ywdemewepmieaeltnrnlimtt”。l另一种矩阵技术是定义密钥k=k1k2kn，将明文逐行写入这个n列的长方形中。随后，按照k1k2kn从小到大顺序逐列读取密文。l明文”get it in the computer department”，密钥“4312567”l其加密密文为“teet icrm ehtr gtua tode imen nppt”单表置换单表置换明文和密文的变换方式如下：明文和密文的变换方式如下：a b c d e f g h i j k l m n o p q r s t u v w x y z a b c d e f g h i j k l m n o p q r s t u v w x y z t s i n g h u a v e r y b c d f j k l m o p q w x zt s i n g h u a v e r y b c d f j k l m o p q w x z其中tsinghuavery是tsinghua university略去前面已出现的字符依次写下的，后面bcdwxz则按英文字母表顺序续上前面未出现的字符构成，这里tsinghua university就是该密码的密钥。下面以一个例子说明密码分析是如何进行的。已知密文G j x x n g g o t z n u c o t w m o h y j t k t a m t x o b y n f g oG I n u g j f n z v q h y n g n e a j f h y o t w g o t h y n a f z nF t u I n z b n e g n l n e u t x n x u f n e j c I n h y a z g a e uT u c q g o g o t h j o h o a t c j x k h y n u v o c o h o u h c n uG h h a f n u z h y n c u t w j u w n a e h y n a f o w o t u c h n pH o g l n f q z n g o f u v c n v j h t a h n g g n t h o u c g j x yO g h y n a b n t o t w g n t h n t x n a e b u f k n f y o h h g I uT j u c e a f h y n g a c j h o a t a e I o c o h u f q x o b y n f g 从大量非技术性的英文书籍、报刊、文章中摘取适当长度的章节进行统计，发现英文字母在各个文章中出现的频率几乎相同。单单字母字母中e出现次数最多，t,a,o出现较多。双字母双字母中th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,a,ng,as,or,ti,is,et,it,ar出现频率较高。三字母三字母中：the,ing,and,her,ent出现频率较高。英文字母出现的频率统计如下表：abcdefg0.08560.01390.02790.03780.13040.02890.0199hijklMn0.05280.06270.00130.00420.03390.02490.0707Opqrstu0.07970.01990.00120.06770.06070.10450.0249Vwxyz0.00920.01490.00170.01990.0008因此可将英文字母分为以下几组：高频率组：e,t,a,o,n,I,r,s,h.(=0.0528)中频率组：d,l,u,c,m.低频率组：p,f,y,w,g,b,v极低组：j,k,q,x,z 对密文字母进行统计，出现的频率如下：A b c d e f g h I j k l m n o p q r16 5 13 0 7 17 23 26 5 12 3 2 2 36 25 1 5 0 s t u v w x y z 0 22 20 4 6 9 14 7现在对密文分析如下：1 密文N是明文e，Ne:2 高频字母中a,i,o三个字母互连的机会极小，推测密文O,U,A可能是a,i,o;3 io的机会相对较高，密文中OA出现2次，OU出现1次，而UO，UA，AO，AU等均不出现，故推测密文OA是io，则O i,A o，U a;4 NU出现5次，而UN不出现，同时ea较多而ae较少，U a可能性非常大；5 YN出现9次，NY不出现，根据Ne和he出现机会多，而eh出现机会少，推测Y h；6 根据英文中th经常出现，而ht很罕见，推测H t；7 高频字母n前面是元音的几率高达0.8，而T前面和N,O,U,A连接的次数为17。推测T n；8 将上述结果代入上面密文，发现密文MOHY*ith，推测M w；9 再将已知结果代入密文，又可得出J u，K k；10 最后我们可以发现有如下的对应关系：L v，H t,J u,F r,G s,U a,V b,X c,B p,E f,W g.由此得到置换的密钥词组为new york city.全部明文为：Success in dealing with unknown ciphers is measured by these four things in the order named,perseverance,careful methods of analysis,intuition,luck.The ability at least to read the the language of the original text is very desirable but not essential.Such is the opening sentence of Parker Hitts Manual for the solution of Military Ciphers.大意如下：破译一未知密码是否成功，可由以下4个因素来衡量，其顺序为：毅力、审慎的分析方法、直观和运气。阅读原文的文字的起码能力是需要的，然而不是必不可少的。这是Parker Hitt的军事密码破译指南一书的开场白。单表置换密码，它的明文字母和密文字母的对应关系是确定的因此可以用频率分析对这种密码体制进行有效的攻击。l对多字母替换的攻击是借助于计算机程序和足够数量的密文，经验丰富的密码分析员能在一小时内攻破这样的密码。具体方法有克思斯基方法和复合指数方法，克思斯基方法用于确定什么时候加密模式的结构重复出现；复合指数方法用于预测替换所使用的字母数目。l2.1 密码学的发展概况密码学的发展概况 l2.2 密码技术的目标密码技术的目标 l2.3 密码学基本概念密码学基本概念 l2.4 替代技术替代技术 l2.5 置换技术置换技术 l2.6 转子机（转子机（Rotor Machine）l2.7 明文处理方式明文处理方式转子机发展历史 转子机原理 l转子机是由一组独立的加密圆筒构成，每个圆筒有26个输入指针和26个输出指针，每个输入指针和输出指针之间内部采用电线连接，因此每个圆筒实现一个26个输入指针和26个输出指针之间的固定置换。一个圆筒能够旋转26次，可以执行26次置换，因此一个由L个圆筒构成的转子机可以实现26L种置换。转子机的密钥是由L个圆筒之间的相对位置关系决定的，密钥包括当前使用的转子的编号（一般在1到8之间）、每个转子在机器中的位置（左、中、右）、当前使用的反射器的编号、转子的初始位置以及连接板连线。转子机转子机 l2.1 密码学的发展概况密码学的发展概况 l2.2 密码技术的目标密码技术的目标 l2.3 密码学基本概念密码学基本概念 l2.4 替代技术替代技术 l2.5 置换技术置换技术 l2.6 转子机（转子机（Rotor Machine）l2.7 明文处理方式明文处理方式分组密码 l加密一条消息时，分组密码会将消息分为多个分组，这些分组具有相等的大小，然后独立地加密各个分组，从而将每个明文都变为一个具有相等大小的密文分组。所有分组都使用相同的算法进行加密，并且这种算法应当是可逆。流密码 l流密码是一种针对比特流的重要加密方法，这种密码使用非常简单的规则，每次只对二进制串的一个比特进行编码。l流密码的原则是创建密钥流的随机比特串，并且将明文比特和密钥流比特组合在一起，生成的比特串就是密文。l组合器通常是异或(XOR)运算，异或密文和相同的密钥流就可以完成解密操作。流密码基于XOR运算具有下列属性：如果C=PK，那么P=CK。XOR值真值表值真值表 序列密码实例序列密码实例l例如，若令例如，若令m=4，设置初始密钥为，设置初始密钥为1000，由由Zi4(Zi+Zi+1)mod 2生成的密钥流为：生成的密钥流为：1000 1001 1010 1111，。任何一个初始。任何一个初始密钥不全为密钥不全为0的密钥都将产生一个周期为的密钥都将产生一个周期为2m-1个二进制长度的密钥流。个二进制长度的密钥流。l明文为“university”，密钥流为key=(1001011 1011001 1000101 1010101 1110001 1001011 1011001 1000101 1010101 1110001)小结 l本章分别讨论密码技术发展的过程，密码技术使用的目标，密码技术的基本概念，经典加密技术：替代、置换，最后讨论替代和置换技术结合在一起的系统：转子机，以及明文处理方式等。作业作业l分析替代技术和置换技术的核心是什么？自己设计一个加密方案，此方案要求使用替代技术和置换技术，并使用此加密方案加密information school，给出加密过程和结果。