现代密码学第一章引言.ppt

现代密码学,聂旭云,简介,聂旭云2007年毕业于中国科学院研究生院信息安全国家重点实验室研究方向：密码学，公钥密码算法，密码学相关代数理论,参考书目,现代密码学（第二版），杨波，清华大学出版社，2007密码学导引，冯登国，裴定一，科学出版社，1999。应用密码学手册，作者：Alfred Menezes，译者：胡磊，电子工业出版社，2005 应用密码学：协议、算法与C源程序，Bruce Schneier 著，吴世忠等译，机械工业出版社，2000。,目的,了解什么是密码学？熟练掌握各种密码算法原理利用密码算法构造各种安全协议为密码学理论研究、各类安全应用打基础,学习方法,基础：信息安全数学基础、数论和近世代数算法和协议：掌握算法和协议的流程，合理性，安全性基础和设计方法。阅读文献，了解密码学最新进展密码学顶级会议：CRYPTO、Eurocrypt、Asiacrypt，PKC密码学顶级期刊：Journal of Cryptology 相关网址：http:/www.iacr.org/International Association for Cryptologic Research 数缘社区http:/,考核方式,考核方式：笔试成绩构成：平时20%+期中10%+期末70%平时成绩主要来源于作业和课堂考勤，期中考试采取随堂测试，期末考试为闭卷考试。,目录,第1章 引言第2章 流密码第3章 分组密码体制第4章 公钥密码第5章 数字签名第6章 hash函数第7章 密码协议第8章 密码学的新方向,第一章 引言,信息安全的主要属性机密性完整性可用性不可否认性可靠性,密码学起源,传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家一次。张小花独自在家只有纺车做伴。一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封书信。,形意诗（神智体）,密码学起源,第六十回 吴用智赚玉麒麟 梁山泊义军头领宋江久慕卢俊义的威名，一心想招取卢俊义上山坐第一把交椅，共图大业，替天行道。智多星吴用扮成一个算命先生，利用卢俊义正为躲避“血光之灾”的惶恐心里，口占四句卦歌，并让他端书在家宅的墙壁上。卢花滩上有扁舟，俊杰黄昏独自游。义到尽头原是命，反躬逃难必无忧。这四句诗写出后，被官府拿到了证据，大兴问罪之师，到处捉拿卢俊义，终于把他逼上梁山。,字谜,天鹅飞去鸟不归，怀念昔日空费心，云开月下双匕影，水流几处又相逢，日落月出人倚月，单身贵族尔相随。,密码学起源,兵经百言衍部传军行无通法，则分者不能合，远者不能应。彼此莫相喻，败道也。然通而不密，反为敌算。故自金、旌、炮、马、令箭、起火、烽烟，报警急外；两军相遇，当诘暗号；千里而遥，宜用素书，为不成字、无形文、非纸简。传者不知，获者无迹，神乎神乎！或其隔敌绝行，远而莫及，则又相机以为之也。”,密码学起源,六韬龙韬阴符武王问太公曰：引兵深入诸侯之地，三军猝有缓急，或利或害。吾将以近通远，从中应外，以给三军之用。为之奈何？太公曰：主与将，有阴符。凡八等：有大胜克敌之符，长一尺；破军杀将之符，长九寸；降城得邑之符，长八寸；却敌报远之符，长七寸；誓众坚守之符，长六寸；请粮益兵之符，长五寸；败军亡将之符，长四寸；失利亡士之符，长三寸。诸奉使行符，稽留者，若符事泄，闻者告者，皆诛之。八符者，主将秘闻，所以阴通言语，不泄中外相知之术。敌虽圣智，莫之通识。武王曰：善哉。,中国古代军事密码,北宋武经总要是中国古代军事史上一部非常重要的著作，对了解中世纪中国战争史有着极其重要的意义。该书作者曾公亮总结前人经验，研究出中国古代已知最早的军事情报通讯密码。曾公亮收集了军队中常用的40种战斗情况，编成40条短语，分别编码。这40条短语是：1请弓、2请箭、3请刀、4请甲、5请枪旗、6请锅幕、7请马、8 请衣赐、9请粮料、10请草料、11请车牛、12请船、13请攻城守具、14请添兵、15请移营、16请进军、17请退军、18请固守、19未见贼、20 见贼讫、21贼多、22贼少、23贼相敌、24贼添兵、25贼移营、26贼进兵、27贼退兵、28贼固守、29围得贼城、30解围城、31被贼围、32贼围解、33战不胜、34战大胜、35战大捷、36将士投降、37将士叛、38士卒病、39都将病、40战小胜。,中国古代军事密码（续）,这套密码的使用方法是：将领带兵接受战斗命令出发前，军事指挥部门与其约定一首40字的五言律诗作为解码密钥，该诗文字不得重复，并发给一本有上述40个短语的密码本，诗中的每一字都对应一条短语，短语顺序在战前临时随机排列，该密码本只有通信双方极少数高级将领保管，在战斗中，前后方就按该密码本进行通讯。现举例如下：假设双方以唐代王勃的送杜少府之任蜀川“城阙辅三秦,风烟望五津。与君离别意,同是宦游人。海内存知己,天涯若比邻。无为在歧路,儿女共沾巾。”作为解码密钥。如果军队在战斗在粮食将尽，需要补充，前方将领就从密码本中查出“请粮料”的编码，假如是第九，而送杜少府之任蜀川中的第九字是“五”。于是请粮将领就将“五”字写到一件普通公文书牒之中，并在字上加盖印章。指挥机关接到这件公文后，查出盖印章的“五”字，得知“五”字在临时约好的诗中列第九，再对照密码本上的顺序，就得知了前方的情报。,中国古代密码,密本型：用预先编定的字母或数字密码组，代 替明文中的数字、字母、音节、单字、词汇、短语、符号等，以实现明密变换。中国密本是在明码本基础上发展而来的。清同治十年(1871)，上海大北水线电报公司选出汉字6899个，按部首笔画为序排列，以四码数字与其相匹配，创造了中国最早的明码本。在明码本基础上重新编排横直码和角码成为密本，称普通本或部首本。明文：三 人 之 中 明码：0005 0086 0037 0022 密文：7970 7947 7966 7981 在普通本基础上，密本里编制词汇、短语、句子 等，既增加密本的密度，又缩短电报长度，称作“特别本”。密本作业进一步发展，出现了来去本。去本的文字部分以部首为序，相对应的密码组无序；来本按密码组顺序排列，相对应的文字无序。加密时用去本，脱密时用来本。,密码学起源,大约在4000年以前，在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史。这篇颇具神秘感的碑文，已具备了密码的基本特征：把一种符号(明文)用另一种符号(密文)代替,Scytale密码,最先有意识的使用一些技术的方法来加密信息的可能是公元前500年的古希腊人。他们使用的是一根叫scytale的棍子。送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人。如果不知道棍子的粗细是不可能解密里面的内容的，如图2-4所示。,恺撒密码,公元前50年，著名的恺撒大帝发明了一种密码叫做恺撒密码。在恺撒密码中，每个字母都与其后第三位的字母对应，然后进行替换，比如“a”对应于“d”，“b”对应于“e”，以此类推。如果到了字母表的末尾，就回到开始，例如“z”对应于“c”，“y”对应于“b”，“x”对应于“a”，如此形成一个循环。当时罗马的军队就用恺撒密码进行通信。恺撒密码明文字母表：A B C D E F G X Y Z恺撒密码密文字母表：D E F G H I J A B C例：明文为“veni，vidi，vici”密文“YHAL，YLGL，YLFL”，意思是“我来，我见，我征服”，曾经是恺撒征服本都王法那西斯后向罗马元老院宣告的名言。26个字符代表字母表的26个字母，从一般意义上说，也可以使用其它字符表，一一对应的数字也不一定要是3，可以选其它数字。,以一种形式写下消息，以另一种形式读取消息 I came I saw I conquered,几何图形密码,密码学起源,16世纪意大利数学家卡尔达诺发明的一种保密通信方法，史称“卡尔达诺漏格板”漏格板是一张用硬质材料(如硬纸、羊皮、金属等)做成的板，上面挖了一些长方形的孔，即漏格,密码学起源,大约在1793年，当时的美国总统托马斯杰斐逊发明了一种轮子密码机。转动轮子使明文中的所有字母全排在一条直线上为止这时圆柱体的其他25行字母也因这一行的固定而被固定了任选这25行中的一行发出去即为密文,密码学起源,“谜”（ENIGMA）密码最初是由一个叫胡戈科赫的荷兰人发明的。起初主要提供给想保护自己生意秘密的公司使用，但其商界的销路一直不理想。后来德国人将其改装为军用型，使之更为复杂可靠。德国海军于1926年开始使用“ENIGMA”，陆军则于1928年开始使用。1933年，纳粹最高统帅部通信部决定将“ENIGMA”作为德国国防军新式闪击部队的通信装置。德国人在战争期间共生产了大约10多万部“谜”密码机。1940年，经过盟军密码分析学家的不懈努力，“恩尼格玛”密码机被动攻破，盟军掌握了德军的许多机密，而德国军方却对此一无所知。,密码学起源,20世纪早期密码机,什么是密码学？,密码指得是什么？口令？密码学研究什么？如何使得某个数据自己能看懂，别人看不懂如何确保数据的正确来源如何保证通信实体的真实性如何确保数据在传输过程中没有被删改功能如何实现算法协议,密码学的基本任务,甲和乙两个人在不安全的信道上进行通信，而他们的敌人丙不能理解他们正在通信的内容。,甲,乙,丙,密码算法,基本概念明文要处理的数据密文处理后的数据密钥秘密参数加密函数解密函数,密码算法,密码算法如何构造？需求1：可逆算法的使用者可以求得逆函数需求2：不可逆敌手无法将密文恢复成明文秘密参数密钥密码算法实际上是一个带有秘密参数的函数。知道秘密参数，求逆非常容易不知道秘密参数，求逆在计算上是不可行的,密码学概述,密码学是研究密码系统或通信安全的一门科学，它包括两个分支：密码编码学和密码分析学。密码编码学的主要目的是寻求保证消息机密性或认证的方法，密码分析学主要研究加密消息的破译和消息的伪造。密码学的目标：机密性、数据完整性、认证和不可否认性。加密杂凑（Hash）数字签名,密码学概述,消息和加密消息被称为明文，用某种方法伪装消息以隐藏它的内容的过程称为加密，加了密的消息称为密文，而把密文转变为明文的过程称为解密。下图表明了加密和解密的过程。,现代密码学引入了密钥，密钥用K表示。K可以是很多数值里的任意值，密钥K的可能值的范围叫做密钥空间。加密和解密运算都使用这个密钥，即运算都依赖于密钥，并用K作为下标表示，加解密函数表达为：EK（M）=CDK（C）=MDK（EK（M）=M加密、解密过程如图所示。,有些算法使用不同的加密密钥和解密密钥，也就是说加密密钥K1与相应的解密密钥K2不同，在这种情况下，加密和解密的函数表达式为：EK1（M）=CDK2（C）=M函数必须具有的特性是，DK2（EK1（M）=M，如图2所示。,对称算法,早期的密钥算法是对称算法（Symmetric Algorithm），就是加密密钥能够从解密密钥中推算出来，反之亦然。多数对称算法中，加密和解密由同一个密钥来控制，也叫“单钥算法”，如图所示。,非对称算法,用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来，就是非对称算法（Asymmetric Algorithm），也叫公钥算法（Public-key Algorithm）或双钥算法，如图所示。,密码学历史回顾,三个阶段：1949年之前密码学是一门艺术19491975年密码学成为科学1976年以后密码学的新方向公钥密码学,密码学历史回顾,1949年之前:古典密码（classical cryptography)密码学还不是科学,而是艺术 出现一些密码算法和加密设备 密码算法的基本手段(substitution&permutation)出现，针对的是字符简单的密码分析手段出现，二战中的多个经典故事（1883）Kerchoffs假设：假定密码分析者和敌手知道所使用的密码系统。,密码学历史回顾,19491975年:计算机使得基于复杂计算的密码成为可能1949年Shannon的“The Communication Theory of Secret Systems”1967年David Kahn的The Codebreakers1971-73年IBM Watson实验室的Horst Feistel等的几篇技术报告：Smith,J.L.,The Design of Lucifer,A Cryptographic Device for Data Communication,1971Smith,J.L.,An Experimental Application of Cryptography to a remotely Accessed Data System,Aug.1972Feistel,H.,Cryptography and Computer Privacy,May 1973数据的安全基于密钥而不是算法的保密,密码学历史回顾,1976年以后:1976年Diffie&Hellman的“New Directions in Cryptography”提出了不对称密钥密码1977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！,密码学历史回顾,1976年以后,对称密钥密码算法进一步发展1977年DES正式成为标准80年代出现“过渡性”的“post DES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟 Rijndael,RC6,MARS,Twofish,Serpent等出现2001年Rijndael成为DES的替代者,密码学历史回顾,按照发展进程来分，经历了古典密码、对称密钥密码和公开密钥密码阶段，古典密码算法有替代加密、置换加密；对称加密算法包括流密码和分组密码如A5、DES和AES；非对称加密算法包括RSA、背包密码、McEliece密码、Rabin、椭圆曲线、EIGamal D_H等。目前在数据通信中使用最普遍的算法有DES算法、AES算法、RSA算法和ECC算法等。,现代密码学的应用,密码学在信息时代有着广泛的应用国家安全电子商务隐私保护信息安全几乎所有领域,1.3.3 密码攻击概述,一个加密算法是无条件安全的，如果算法产生的密文不能给出惟一决定相应明文的足够信息。此时无论敌手截获多少密文、花费多少时间，都不能解密密文。Shannon指出，仅当密钥至少和明文一样长时，才能达到无条件安全。也就是说除了一次一密方案外，再无其他的加密方案是无条件安全的。比无条件安全弱的一个概念是计算上安全的，加密算法只要满足以下两条准则之一就称为是计算上安全的：1 破译密文的代价超过被加密信息的价值。2 破译密文所花的时间超过信息的有用期。,仿射密码算法,加密函数：C=E(M)=aM+b mod 26密钥：a，b解密函数：M=D(C)=(C-b)a-1 mod 26关键在于计算a-1：a a-1=1 mod 26方法：扩展的欧几里得算法若(m,n)=1，则存在整数k1，k2使得 k1m+k2n=1这里k1就是m-1 mod n，注意要将k1变为正数-k1 mod n=(n-k1)mod n,扩展的欧几里得算法,设a,bZ+,则存在m,nZ使得gcd(a,b)=ma+nb.,a=bq1+r1b=r1q2+r2 r1=r2q3+r3,rn-2=rn-1qn+rn gcd(a,b)=rn=rn-2-rn-1qn=ma+nb,r1=a-bq1r2=b-r1q2r3=r1-r2q3 rn=rn-2-rn-1qn,扩展的欧几里得算法,利用该方法我们可以求密码学方程ax+by=d的解,这里d=(a,b),例如:求132x+108y=12的解,解：12=gcd(132,108)12=108-424=108-4(132-108 1)=108 4 132+4 108=5*108 4*132,回顾,132=108+24108=24 4+1224=12 2,求17-1mod 26。26=17 1+917=9 1+89=8 1+18=1 8,1=9-8 1=9-（17-9 1）=9 2-17=（26-17 1）2-17=26 2-3 17,-3 mod 26=（26-3）mod 26=23因此17-1mod 26=23,Vigenre密码,习题,P10，T2,