密码学基础.ppt课件.ppt

现代密码学密码学基础密码学基础电子科技大学计算机学院1感谢你的观看2019年8月28电子科技大学 现代密码学目 的u了解什么是密码学？ u熟练掌握各种密码算法原理u利用密码算法构造各种安全协议u为密码学理论研究、各类安全应用打基础2感谢你的观看2019年8月28电子科技大学 现代密码学学习方法u基础：信息安全数学基础、数论和近世代数基础：信息安全数学基础、数论和近世代数u算法和协议：掌握算法和协议的流程，合理性，算法和协议：掌握算法和协议的流程，合理性，安全性基础和设计方法。安全性基础和设计方法。u阅读文献，了解密码学最新进展阅读文献，了解密码学最新进展u密码学顶级会议：密码学顶级会议：CRYPTO、Eurocrypt、Asiacryptu密码学顶级期刊密码学顶级期刊：Journal of Cryptology u相关网址：相关网址：http:/www.iacr.org/u中国密码学会中国密码学会3感谢你的观看2019年8月28电子科技大学 现代密码学课程考核 平时考勤 10分 作业、小论文 20分 期末考试 70分4感谢你的观看2019年8月28电子科技大学 现代密码学教材及参考书目教材及参考书目 教材：教材：现代密码学许春香等编著，电子科技大学出版社，现代密码学许春香等编著，电子科技大学出版社，2008年。年。 参考书：参考书：现代密码学现代密码学，杨波编著，清华大学出版社，杨波编著，清华大学出版社，2003年。年。计算机密码学计算机密码学计算机网络中的数据保密与安全计算机网络中的数据保密与安全，卢，卢开澄等编著，清华大学出版社，开澄等编著，清华大学出版社，1998年年现代密码学理论与实践现代密码学理论与实践，英英Wenbo Mao 著，著，王继林等译，王育民等审校，电子工业出版社，王继林等译，王育民等审校，电子工业出版社，2004年。年。5感谢你的观看2019年8月28 现代密码学本课程学习内容：本课程学习内容：第第1章章 引言引言-密码学的发展概况及基本概念密码学的发展概况及基本概念第第2章章 流密码流密码第第3章章 分组密码分组密码第第4章章 公钥密码公钥密码第第5章章 数字签名数字签名第第6章章 Hash函数函数第第7章章 密码协议密码协议第第8章章 可证明安全性理论可证明安全性理论第第9章章 基于身份的公钥密码体制基于身份的公钥密码体制第第10章章 密码学的新方向密码学的新方向6感谢你的观看2019年8月28电子科技大学 现代密码学1.1 密码学的发展概况密码学的发展概况1.2 密码学的基本概念密码学的基本概念1.3 古典密码体制古典密码体制第一章 引言7感谢你的观看2019年8月28 现代密码学1.1 密码学的发展概况密码学是一门密码学是一门古老古老、年轻年轻且且深奥深奥的学科。的学科。密码学经历了从密码学经历了从古典密码学古典密码学到到现代密码学现代密码学的演变。的演变。密码学是研究密码学是研究信息系统安全保密信息系统安全保密的科学。它包括的科学。它包括密码编码学密码编码学和和密密码分析学码分析学。1949年前密码技术是一门技术性很强的年前密码技术是一门技术性很强的艺术艺术，而，而不是一门科学不是一门科学。1949年年shannon “保密系统的通信理论保密系统的通信理论”，密码学成为，密码学成为科学科学。1976年年Diffie和和Hellman“密码学的新方向密码学的新方向”，密码学的一场，密码学的一场革命革命。1977年美国国家标准局公布年美国国家标准局公布DES，并公开算法，揭开并公开算法，揭开神秘面纱神秘面纱。8感谢你的观看2019年8月28电子科技大学 现代密码学u现代密码技术的应用已经深入到数据处理现代密码技术的应用已经深入到数据处理过程的各个环节，包括：数据加密、密码过程的各个环节，包括：数据加密、密码分析、数字签名、信息鉴别、零知识认证、分析、数字签名、信息鉴别、零知识认证、秘密共享等。密码学的数学工具也更加广秘密共享等。密码学的数学工具也更加广泛，有概率统计、数论、代数、混沌和椭泛，有概率统计、数论、代数、混沌和椭圆曲线等。圆曲线等。 9感谢你的观看2019年8月28电子科技大学 现代密码学密码学密码学 重要术语重要术语u 消息消息 又被称为明文，用某种方法伪装消息又被称为明文，用某种方法伪装消息以隐藏它的内容的过程称为以隐藏它的内容的过程称为加密加密，加了密，加了密的消息称为的消息称为密文密文，而把密文转变为明文的，而把密文转变为明文的过程称为过程称为解密解密。10感谢你的观看2019年8月28电子科技大学 现代密码学现代密码学引入了密钥，密钥用现代密码学引入了密钥，密钥用K表示。表示。 加密加密 EK（M）=C 解密解密 DK（C）=M 对密文解密记为对密文解密记为 DK（EK（M）=M11感谢你的观看2019年8月28电子科技大学 现代密码学 有些算法使用不同的加密密钥和解密密钥：有些算法使用不同的加密密钥和解密密钥：uEK1（M）=CuDK2（C）=Mu函数必须具有的特性是，函数必须具有的特性是，DK2（EK1（M）=M12感谢你的观看2019年8月28电子科技大学 现代密码学密码学起源密码学起源u大约在大约在40004000年以前，在古埃及的尼罗河畔，一位年以前，在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加擅长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的象形文字来写铭以变形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史。这篇颇具文，从而揭开了有文字记载的密码史。这篇颇具神秘感的碑文，已具备了密码的基本特征：把一神秘感的碑文，已具备了密码的基本特征：把一种符号种符号( (明文明文) )用另一种符号用另一种符号( (密文密文) )代替代替13感谢你的观看2019年8月28电子科技大学 现代密码学u公元前公元前5 5世纪，古斯巴达人使用了一种叫做世纪，古斯巴达人使用了一种叫做“天书天书”的器械，这是人类历史上最早使用的的器械，这是人类历史上最早使用的密码器械。密码器械。“天书天书”是一根用草纸条、皮条或是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍皮纸条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。上，这样字就一圈圈跳出来。 14感谢你的观看2019年8月28电子科技大学 现代密码学u公元前1世纪古罗马凯撒大帝时代曾使用过一种“替代式密码”，在这种密码中，每个字母都由其后的第三个字母（按字母顺序）所代替。这种替代式密码直到第二次大战时还被日本海军使用。u公元前4世纪前后，希腊著名作家艾奈阿斯在著作城市防卫论中就曾提到一种被称为“艾奈阿斯绳结”的密码。它的作法是从绳子的一端开始，每隔一段距离打一个绳结，而绳结之间距离不等，不同的距离表达不同的字母。15感谢你的观看2019年8月28电子科技大学 现代密码学u暗号：通过用物件的状态或人的行为来传达事先约定的信息u隐语：把信息变换成与此信息完全无关的(但有意义的)语言据说，1941年，日本偷袭珍珠港前，美国情报人员曾截获一次重要的电话对话对话里“小孩出生”的真正意思是“发动战争” 在华盛顿的日本人：是不是真的有个小孩要出生了?在东京的日本人：是的而且看来马上就要出生了在华盛顿的日本人：这个小孩真的要生了吗?是在哪个方向呢?16感谢你的观看2019年8月28电子科技大学 现代密码学u1616世纪卡尔达诺发明世纪卡尔达诺发明 “ “卡尔达诺漏格卡尔达诺漏格板板”漏格板是一张用硬质材料漏格板是一张用硬质材料( (如硬纸、如硬纸、羊皮、金属等羊皮、金属等) )做成的板，上面挖了一些长做成的板，上面挖了一些长方形的孔，即漏格方形的孔，即漏格17感谢你的观看2019年8月28电子科技大学 现代密码学“谜谜”（ENIGMA）密码）密码德国人德国人Arthur Scheribius人发明人发明德国人将其改装为军用型，使之更为复杂可靠德国人将其改装为军用型，使之更为复杂可靠1926年开始使用年开始使用“ENIGMA”，陆军则于，陆军则于1928年开始使用。年开始使用。 1933年，纳粹最高统帅部通信部决定将年，纳粹最高统帅部通信部决定将“ENIGMA”作为德国国防军新式闪击部队作为德国国防军新式闪击部队的通信装置。的通信装置。 1940年，盟军破译年，盟军破译ENIGMA18感谢你的观看2019年8月28电子科技大学 现代密码学u传说，古时候有一对夫妻，男的名叫李石匠，女的叫张传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家李石匠参加修建石桥，因工程紧张，十一个月也没回家一次。张小花独自在家只有纺车做伴。一天石匠工地回一次。张小花独自在家只有纺车做伴。一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封书来一个工友路过她家，她托这个工友给丈夫带去一封书信。信。 19感谢你的观看2019年8月28电子科技大学 现代密码学 吴用智赚玉麒麟吴用智赚玉麒麟 卢花滩上有扁舟，俊杰黄昏独自游。卢花滩上有扁舟，俊杰黄昏独自游。义到尽头原是命，反躬逃难必无忧。义到尽头原是命，反躬逃难必无忧。 20感谢你的观看2019年8月28电子科技大学 现代密码学唐伯虎的卖身契我康宣，今年一十八岁，姑苏人氏，身家清白，素无过犯。只为家况清贫，卖身华相府中，充当书僮。身价银五十两，自秋节起，暂存帐房，以三年后支取，从此承值书房，每日焚香扫地，洗砚、磨墨等事，听凭使唤。从头做起。立此契凭。 21感谢你的观看2019年8月28电子科技大学 现代密码学u以一种形式写下消息，以另一种形式读取消息 uI came I saw I conquered几何图形密码22感谢你的观看2019年8月28电子科技大学 现代密码学密码学历史回顾u19491975年年: 计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能1949年年Shannon的的“The Communication Theory of Secret Systems” 1967年年David Kahn的的The Codebreakers1971-73年年IBM Watson实验室的实验室的Horst Feistel等的几篇技术报告：等的几篇技术报告： A Cryptographic Device for Data Communication, 1971 An Experimental Application of Cryptography to a remotely Accessed Data System, 1972 Cryptography and Computer Privacy, 1973 数据的安全基于数据的安全基于密钥密钥而不是而不是算法算法的保密的保密23感谢你的观看2019年8月28电子科技大学 现代密码学u1976年以后年以后: 1976年年Diffie & Hellman的的“New Directions in Cryptography”提出了不对称密钥密码提出了不对称密钥密码1977年年Rivest,Shamir & Adleman提出了提出了RSA公钥算法公钥算法90年代逐步出现椭圆曲线等其它公钥算法年代逐步出现椭圆曲线等其它公钥算法 u公钥密码使得发送端和接收端无密钥传输公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！的保密通信成为可能！密码学历史回顾24感谢你的观看2019年8月28电子科技大学 现代密码学u1976年以后年以后,对称密钥密码算法进一步对称密钥密码算法进一步发展发展 1977年年DES正式成为标准正式成为标准 80年代出现年代出现“过渡性过渡性”的的“post DES”算法算法,如如IDEA,RCx,CAST等等 90年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Twofish, Serpent等出现等出现 2001年年Rijndael成为成为DES的替代者的替代者25感谢你的观看2019年8月28电子科技大学 现代密码学对称算法 u加密和解密由同一个密钥来控制，也叫加密和解密由同一个密钥来控制，也叫“单钥算单钥算法法”，如图所示。，如图所示。26感谢你的观看2019年8月28电子科技大学 现代密码学非对称算法u用作加密的密钥不同于用作解密的密钥，而且解用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来，就是非对称密密钥不能根据加密密钥计算出来，就是非对称算法（算法（Asymmetric Algorithm），如图所示。），如图所示。 27感谢你的观看2019年8月28 现代密码学1.2 密码学的基本概念明文明文（plaintext）: 没有加密的信息没有加密的信息密钥密钥(key): 加密和解密是在密钥控制下进行的。加密和解密是在密钥控制下进行的。密文密文（ciphertext）: 加密后的信息加密后的信息加密变换加密变换（encryption）: 从明文到密文的变换从明文到密文的变换解密变换解密变换（decryption）: 从密文到明文的变换从密文到明文的变换一、密码系统模型一、密码系统模型二、密码体制分类二、密码体制分类三、密码体制的攻击方法三、密码体制的攻击方法 28感谢你的观看2019年8月28 现代密码学1.2.1 密码系统模型加密器 mEck1 cDmk2解密器信源M接收者搭线信道(主动攻击 )搭线信道(被动攻击 )非法接入着密码分析员(窃听者)1K密钥源2K密钥源密钥信道mcmcm1k2k公开信道29感谢你的观看2019年8月28 现代密码学1.2.2 1.2.2 密码体制分类密码体制分类对称密码对称密码 (单钥密码单钥密码, 私钥密码私钥密码): 加密密钥与解密密钥相同加密密钥与解密密钥相同如：分组密码，流密码如：分组密码，流密码非对称密码体制非对称密码体制(双钥密码双钥密码,公钥密码公钥密码): 加密密钥与解密密钥不同加密密钥与解密密钥不同如：公钥密码如：公钥密码30感谢你的观看2019年8月28 现代密码学一个好的密码体制至少应满足的两个条件：一个好的密码体制至少应满足的两个条件：)(1mEck （1）在已知）在已知明文明文m和和加密密钥加密密钥k1时，计算时，计算 容易，容易，)(2cDmk 在已知在已知密文密文c和和解密密钥解密密钥k2时，计算时，计算 容易；容易；（2）在不知解密密钥）在不知解密密钥k2时，不可能由时，不可能由密文密文c恢复出恢复出明文明文m。31感谢你的观看2019年8月28 现代密码学可破译的：可破译的：如果能够根据如果能够根据密文密文确定确定明文或密钥明文或密钥，或根据，或根据明文明文及对应的密文及对应的密文确定确定密钥密钥；否则称为否则称为不可破译的不可破译的。32感谢你的观看2019年8月28 现代密码学密码分析者攻击密码体制的方法：密码分析者攻击密码体制的方法：（1）穷举攻击：）穷举攻击：通过试遍所有的密钥来进行破译。通过试遍所有的密钥来进行破译。 对抗：对抗：可增大密钥的数量。可增大密钥的数量。（2）统计分析攻击：）统计分析攻击：通过分析密文和明文的统计规律来破译。通过分析密文和明文的统计规律来破译。 对抗：对抗：设法使明文和密文的统计规律不一样。设法使明文和密文的统计规律不一样。（3）解密变换攻击：）解密变换攻击：针对加密变换的数学基础，通过数学求针对加密变换的数学基础，通过数学求解设法找到解密变换。解设法找到解密变换。 对抗：对抗：选用具有坚实的数学基础和足够复杂的加密算法。选用具有坚实的数学基础和足够复杂的加密算法。1.2.3 1.2.3 密码体制的攻击方法密码体制的攻击方法33感谢你的观看2019年8月28 现代密码学密码分析者通常可以在下述情况下进行攻击：密码分析者通常可以在下述情况下进行攻击：（1）唯密文攻击：）唯密文攻击：密码分析者仅知道一些密文。密码分析者仅知道一些密文。（2）已知明文攻击：）已知明文攻击：密码分析者知道一些明文和相应的密文。密码分析者知道一些明文和相应的密文。（3）选择明文攻击：）选择明文攻击：密码分析者可以选择一些明文，并得到密码分析者可以选择一些明文，并得到相应的密文。相应的密文。（4）选择密文攻击：）选择密文攻击：密码分析者可以选择一些密文，并得到密码分析者可以选择一些密文，并得到相应的明文。相应的明文。 唯密文攻击的强度最弱，攻击强度依此增加。唯密文攻击的强度最弱，攻击强度依此增加。34感谢你的观看2019年8月28 现代密码学无条件安全的无条件安全的(不可破译的不可破译的)：一次一密方案一次一密方案(一次一密乱码本一次一密乱码本)计算上安全的：计算上安全的：流密码、分组密码、公钥密码流密码、分组密码、公钥密码密码算法只要满足以下两条准则之一就行：密码算法只要满足以下两条准则之一就行：（1） 破译密文的代价超过被加密信息的价值。破译密文的代价超过被加密信息的价值。（2 ) 破译密文所花的时间超过信息的有用期。破译密文所花的时间超过信息的有用期。满足以上两个准则的密码算法在实际中是可用的。满足以上两个准则的密码算法在实际中是可用的。 35感谢你的观看2019年8月28电子科技大学 现代密码学1.3 古典密码体制古典密码的重要的两种构造方法，代替密码和置换密码u置换密码u单表代替密码u多表代换密码36感谢你的观看2019年8月28电子科技大学 现代密码学1.3.1 置换密码 在置换密码体制中，明文中的字或字母被重新排列，字或字母本身不变，但位置发生了改变，形成密文，又称为易位密码易位密码。 最简单的易位密码是采用报文倒置法，即将报文按字的顺序依次倒置，并截成固定长度的字母组，形成密文.37感谢你的观看2019年8月28电子科技大学 现代密码学明文：明文：never accept failure no matter how often it visits you密文：密文：uoys tisi vtin etfo wohr etta mone ulia ftpe ccar even特点： 简单，缺点是不安全，很容易被识破。返回38感谢你的观看2019年8月28电子科技大学 现代密码学1.3.2 单表代替密码 代替密码代替密码是把明文中的每一个字符替换成密文字母表中的另一个字符，并使用密钥K与之进行运算，得到密文；接收者对密文进行逆运算就可以恢复出明文39感谢你的观看2019年8月28电子科技大学 现代密码学 在单表代替密码中，只使用一个密文字母表，并且用密文字母表中的一个字母来代替一个明文字母表中的一个字母。设A和B分别为含个字母的明文字母表和密文字母表：定义A到B的一一映射011,nAaaa011,nBbbbf()f()f()f()1.3.2 单表代替密码f :A B: f (ai)=bi40感谢你的观看2019年8月28电子科技大学 现代密码学单表代换密码又可以分为加法密码乘法密码仿射密码密钥短语代替密码。1.3.2 单表代替密码41感谢你的观看2019年8月28电子科技大学 现代密码学1.3.2 单表代替密码1、加法密码f (ai) = bi = ajj = i+k(mod n) , (aiA ,0kn)Caesar密码就是一种加法密码明文：ATTACK START FROM TEN PM TONIGHT密文：DWWDFN VWDUW IURP WHQ SP WRQLJKW42感谢你的观看2019年8月28电子科技大学 现代密码学1.3.2 单表代替密码2、乘法密码乘法密码f (ai) = bi = ajj = ik(mod n) , (aiA ,0kn，(k,n)=1)43感谢你的观看2019年8月28电子科技大学 现代密码学1.3.2 单表代替密码3、仿射密码仿射密码是乘法密码和加法密码的结合是乘法密码和加法密码的结合f (ai) = bi = ajj = k0 +ik1 (mod n) , (aiA ,0k0 n，(k1 ,n)=1)44感谢你的观看2019年8月28电子科技大学 现代密码学1.3.2 单表代替密码4、密钥短语代替密码密钥短语代替密码 这种密码选用一个英文短语或者单词串作为密这种密码选用一个英文短语或者单词串作为密钥，称为钥，称为密钥字或密钥短语密钥字或密钥短语， 例如例如 HAPPY NEW YEAR，去掉其中的重复，去掉其中的重复字母，得到一个无重复字母的字母串，即字母，得到一个无重复字母的字母串，即HAPYNEWR，把它依次写在明文字母表之下，把它依次写在明文字母表之下，而后再将字母表中未在字母串中出现过的字母依而后再将字母表中未在字母串中出现过的字母依次写于此短语之后，就可以构造一个字母替换表次写于此短语之后，就可以构造一个字母替换表 45感谢你的观看2019年8月28电子科技大学 现代密码学1.3.2 单表代替密码abcdefghijklmHAPYNEWRBCDFGnopqrstuvwxyzIJKLMOQSTUVXZ当选择密钥短语代替密码和上述的密钥进行加密时，当选择密钥短语代替密码和上述的密钥进行加密时，若明文为若明文为 h e l l o，则密文为，则密文为R N F F J。不同的密钥字。不同的密钥字可以得到不同的替换表，对于明文为英文单词时，密可以得到不同的替换表，对于明文为英文单词时，密钥短语密码最多可能钥短语密码最多可能 有个不同的替换表。有个不同的替换表。2626!41046感谢你的观看2019年8月28 现代密码学47感谢你的观看2019年8月28 现代密码学48感谢你的观看2019年8月28 现代密码学49感谢你的观看2019年8月28 现代密码学50感谢你的观看2019年8月28 现代密码学51感谢你的观看2019年8月28电子科技大学 现代密码学国内密码学发展u西安电子科技大学: 肖国镇教授、王育民教授、王新梅教授 肖国镇教授肖国镇教授52感谢你的观看2019年8月28电子科技大学 现代密码学u上海交通大学：来学嘉教授、陈克非教授、曹珍富教授等 来学嘉教授来学嘉教授53感谢你的观看2019年8月28电子科技大学 现代密码学u山东大学: 王小云教授、李大兴教授 王小云教授王小云教授54感谢你的观看2019年8月28电子科技大学 现代密码学u中科院软件所：冯登国教授、吴文玲教授、胡磊教授等u北京邮电大学：杨义先教授u解放军信息工程大学：戚文峰教授、祝跃飞教授u中山大学：黄继武教授、张方国教授等u武汉大学: 张焕国教授u电子科技大学：秦志光教授、许春香教授、范明钰教授、佘坤教授、张凤荔教授等55感谢你的观看2019年8月28 现代密码学第一章重点第一章重点密码体制的分类。密码体制的分类。密码分析者攻击密码体制的方法：密码分析者攻击密码体制的方法：（1）穷举攻击；（）穷举攻击；（2）统计分析；（）统计分析；（3）解密变换攻击。）解密变换攻击。密码分析者通常在下列四种情况下攻击：密码分析者通常在下列四种情况下攻击：（1）唯密文攻击；（）唯密文攻击；（2）已知明文攻击；）已知明文攻击；（3）选择明文攻击；（）选择明文攻击；（4）选择密文攻击。）选择密文攻击。了解古典密码了解古典密码56感谢你的观看2019年8月28电子科技大学 现代密码学57感谢你的观看2019年8月28