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

现代密码学聂旭云简介p聂旭云聂旭云p2007年毕业于中国科学院研究生院信息安全国年毕业于中国科学院研究生院信息安全国家重点实验室家重点实验室p研究方向：密码学，公钥密码算法，密码学相关研究方向：密码学，公钥密码算法，密码学相关代数理论代数理论参考书目参考书目p现代密码学（第二版），杨波，清华大学出版社，现代密码学（第二版），杨波，清华大学出版社，2007p密码学导引，冯登国，裴定一，科学出版社，密码学导引，冯登国，裴定一，科学出版社，1999p应用密码学手册，作者：应用密码学手册，作者： Alfred Menezes，，译者：译者： 胡磊胡磊 ，电子工业出版社，，电子工业出版社，2005 p应用密码学：协议、算法与应用密码学：协议、算法与C源程序，源程序，Bruce Schneier 著，吴世忠等译，机械工业出版社，著，吴世忠等译，机械工业出版社，2000目的目的p了解什么是密码学？了解什么是密码学？ p熟练掌握各种密码算法原理熟练掌握各种密码算法原理p利用密码算法构造各种安全协议利用密码算法构造各种安全协议p为密码学理论研究、各类安全应用打基础为密码学理论研究、各类安全应用打基础学习方法学习方法p基础：信息安全数学基础、数论和近世代数基础：信息安全数学基础、数论和近世代数p算法和协议：掌握算法和协议的流程，合理性，算法和协议：掌握算法和协议的流程，合理性，安全性基础和设计方法。

安全性基础和设计方法p阅读文献，了解密码学最新进展阅读文献，了解密码学最新进展p密码学顶级会议：密码学顶级会议：CRYPTO、、Eurocrypt、、Asiacrypt，，PKC……p密码学顶级期刊密码学顶级期刊：：Journal of Cryptology p相关网址：相关网址：nInternational Association for Cryptologic Research p数缘社区数缘社区考核方式p考核方式：考核方式： 笔试笔试p成绩构成：平时成绩构成：平时20% +期中期中10%+期末期末70%p平时成绩主要来源于作业和课堂考勤，期中考试平时成绩主要来源于作业和课堂考勤，期中考试采取随堂测试，期末考试为闭卷考试采取随堂测试，期末考试为闭卷考试目录目录第1章 引言第2章 流密码第3章 分组密码体制第4章 公钥密码第5章 数字签名第6章 hash函数第7章 密码协议第8章 密码学的新方向第一章第一章 引言引言p信息安全的主要属性信息安全的主要属性n机密性机密性n完整性完整性n可用性可用性n不可否认性不可否认性n可靠性可靠性密码学起源密码学起源p传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花。

李石传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花李石匠靠手艺赚钱，张小花在家纺纱织布一年，李石匠参加修建石桥，匠靠手艺赚钱，张小花在家纺纱织布一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家一次张小花独自在家只有纺车做因工程紧张，十一个月也没回家一次张小花独自在家只有纺车做伴一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带伴一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封书信去一封书信 形意诗（神智体）密码学起源密码学起源p第六十回第六十回 吴用智赚玉麒麟吴用智赚玉麒麟 梁山泊义军头领宋江久慕卢俊梁山泊义军头领宋江久慕卢俊义的威名，一心想招取卢俊义上山坐第一把交椅，共图大义的威名，一心想招取卢俊义上山坐第一把交椅，共图大业，替天行道智多星吴用扮成一个算命先生，利用卢俊业，替天行道智多星吴用扮成一个算命先生，利用卢俊义正为躲避义正为躲避“血光之灾血光之灾”的惶恐心里，口占四句卦歌，并的惶恐心里，口占四句卦歌，并让他端书在家宅的墙壁上让他端书在家宅的墙壁上p卢花滩上有扁舟，卢花滩上有扁舟，p俊杰黄昏独自游俊杰黄昏独自游p义到尽头原是命，义到尽头原是命，p反躬逃难必无忧。

反躬逃难必无忧 p这四句诗写出后，被官府拿到了证据，大兴问罪之师，到这四句诗写出后，被官府拿到了证据，大兴问罪之师，到处捉拿卢俊义，终于把他逼上梁山处捉拿卢俊义，终于把他逼上梁山 字谜p天鹅飞去鸟不归，怀念昔日空费心，云开月下双天鹅飞去鸟不归，怀念昔日空费心，云开月下双匕影，水流几处又相逢，日落月出人倚月，单身匕影，水流几处又相逢，日落月出人倚月，单身贵族尔相随贵族尔相随密码学起源密码学起源p〈兵经百言．衍部．传〉军行无通法，则分者不〈兵经百言．衍部．传〉军行无通法，则分者不能合，远者不能应彼此莫相喻，败道也然通能合，远者不能应彼此莫相喻，败道也然通而不密，反为敌算故自金、旌、炮、马、令箭、而不密，反为敌算故自金、旌、炮、马、令箭、起火、烽烟，报警急外；两军相遇，当诘暗号；起火、烽烟，报警急外；两军相遇，当诘暗号；千里而遥，宜用素书，为不成字、无形文、非纸千里而遥，宜用素书，为不成字、无形文、非纸简传者不知，获者无迹，神乎神乎！或其隔敌简传者不知，获者无迹，神乎神乎！或其隔敌绝行，远而莫及，则又相机以为之也绝行，远而莫及，则又相机以为之也密码学起源密码学起源p〈〈六韬．龙韬．阴符六韬．龙韬．阴符〉〉武王问太公曰：武王问太公曰：‘引兵引兵深入诸侯之地，三军猝有缓急，或利或害。

吾深入诸侯之地，三军猝有缓急，或利或害吾将以近通远，从中应外，以给三军之用为之将以近通远，从中应外，以给三军之用为之奈何？奈何？’太公曰：太公曰：‘主与将，有阴符凡八等：主与将，有阴符凡八等：有大胜克敌之符，长一尺；破军杀将之符，长有大胜克敌之符，长一尺；破军杀将之符，长九寸；降城得邑之符，长八寸；却敌报远之符，九寸；降城得邑之符，长八寸；却敌报远之符，长七寸；誓众坚守之符，长六寸；请粮益兵之长七寸；誓众坚守之符，长六寸；请粮益兵之符，长五寸；败军亡将之符，长四寸；失利亡符，长五寸；败军亡将之符，长四寸；失利亡士之符，长三寸诸奉使行符，稽留者，若符士之符，长三寸诸奉使行符，稽留者，若符事泄，闻者告者，皆诛之八符者，主将秘闻，事泄，闻者告者，皆诛之八符者，主将秘闻，所以阴通言语，不泄中外相知之术敌虽圣智，所以阴通言语，不泄中外相知之术敌虽圣智，莫之通识莫之通识’武王曰：武王曰：‘善哉’中国古代军事密码p北宋北宋《《武经总要武经总要》》是中国古代军事史上一部非常重要的著作，是中国古代军事史上一部非常重要的著作，对了解中世纪中国战争史有着极其重要的意义该书作者曾公对了解中世纪中国战争史有着极其重要的意义。

该书作者曾公亮总结前人经验，研究出中国古代已知最早的军事情报通讯密亮总结前人经验，研究出中国古代已知最早的军事情报通讯密码p曾公亮收集了军队中常用的曾公亮收集了军队中常用的40种战斗情况，编成种战斗情况，编成40条短语，条短语，分别编码分别编码p这这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战小胜。

战小胜中国古代军事密码（续）p这套密码的使用方法是：将领带兵接受战斗命令出发前，军事指挥部这套密码的使用方法是：将领带兵接受战斗命令出发前，军事指挥部门与其约定一首门与其约定一首40字的五言律诗作为解码密钥，该诗文字不得重复，字的五言律诗作为解码密钥，该诗文字不得重复，并发给一本有上述并发给一本有上述40个短语的密码本，诗中的每一字都对应一条短个短语的密码本，诗中的每一字都对应一条短语，短语顺序在战前临时随机排列，该密码本只有通信双方极少数高语，短语顺序在战前临时随机排列，该密码本只有通信双方极少数高级将领保管，在战斗中，前后方就按该密码本进行通讯现举例如下：级将领保管，在战斗中，前后方就按该密码本进行通讯现举例如下：p假设双方以唐代王勃的假设双方以唐代王勃的《《送杜少府之任蜀川送杜少府之任蜀川》》“城阙辅三秦城阙辅三秦, 风烟望五风烟望五津 与君离别意与君离别意, 同是宦游人同是宦游人 海内存知己海内存知己, 天涯若比邻天涯若比邻 无为在无为在歧路歧路, 儿女共沾巾儿女共沾巾作为解码密钥如果军队在战斗在粮食将尽，作为解码密钥如果军队在战斗在粮食将尽，需要补充，前方将领就从密码本中查出需要补充，前方将领就从密码本中查出“请粮料请粮料”的编码，假如是第的编码，假如是第九，而九，而《《送杜少府之任蜀川送杜少府之任蜀川》》中的第九字是中的第九字是“五五”。

于是请粮将领就于是请粮将领就将将“五五”字写到一件普通公文书牒之中，并在字上加盖印章指挥机字写到一件普通公文书牒之中，并在字上加盖印章指挥机关接到这件公文后，查出盖印章的关接到这件公文后，查出盖印章的“五五”字，得知字，得知“五五”字在临时约字在临时约好的诗中列第九，再对照密码本上的顺序，就得知了前方的情报好的诗中列第九，再对照密码本上的顺序，就得知了前方的情报中国古代密码p密本型：用预先编定的字母或数字密码组，代密本型：用预先编定的字母或数字密码组，代 替明文中的数字、字母、替明文中的数字、字母、音节、单字、词汇、短语、符号等，以实现明密变换中国密本是在音节、单字、词汇、短语、符号等，以实现明密变换中国密本是在明码本基础上发展而来的清同治十年明码本基础上发展而来的清同治十年(1871)，上海大北水线电报，上海大北水线电报公司选出汉字公司选出汉字6899个，按部首笔画为序排列，以四码数字与其相匹个，按部首笔画为序排列，以四码数字与其相匹配，创造了中国最早的配，创造了中国最早的《《明码本明码本》》在明码本基础上重新编排横直码在明码本基础上重新编排横直码和角码成为密本，称和角码成为密本，称"普通本普通本"或或"部首本部首本"。

p明文：明文： 三三 人人 之之 中中 ……p明码：明码：0005 0086 0037 0022 ……p密文：密文：7970 7947 7966 7981 ……p在普通本基础上，密本里编制词汇、短语、句子在普通本基础上，密本里编制词汇、短语、句子 等，既增加密本的密等，既增加密本的密度，又缩短电报长度，称作度，又缩短电报长度，称作“特别本特别本”p密本作业进一步发展，出现了密本作业进一步发展，出现了"来去本来去本"去本的文字部分以部首为序，去本的文字部分以部首为序，相对应的密码组无序；来本按密码组顺序排列，相对应的文字无序相对应的密码组无序；来本按密码组顺序排列，相对应的文字无序加密时用去本，脱密时用来本加密时用去本，脱密时用来本密码学起源p大约在大约在4000年以前，在古埃及的尼罗河畔，一位擅长书写者在贵年以前，在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史这篇颇具象形文字来写铭文，从而揭开了有文字记载的密码史。

这篇颇具神秘感的碑文，已具备了密码的基本特征：把一种符号神秘感的碑文，已具备了密码的基本特征：把一种符号(明文明文)用用另一种符号另一种符号(密文密文)代替代替Scytale密码密码p最先有意识的使用一些技术的方法来加密信息的可能是公元前最先有意识的使用一些技术的方法来加密信息的可能是公元前500年年的古希腊人他们使用的是一根叫的古希腊人他们使用的是一根叫scytale的棍子送信人先绕棍子的棍子送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人如果不知道棍子的粗细是不可能解密里面的内容的，如图人如果不知道棍子的粗细是不可能解密里面的内容的，如图2-4所所示恺撒密码恺撒密码p公元前公元前50年，著名的恺撒大帝发明了一种密码叫做恺撒密码在恺年，著名的恺撒大帝发明了一种密码叫做恺撒密码在恺撒密码中，每个字母都与其后第三位的字母对应，然后进行替换，比撒密码中，每个字母都与其后第三位的字母对应，然后进行替换，比如如“a”对应于对应于“d”，，“b”对应于对应于“e”，以此类推如果到了字母，以此类推如果到了字母表的末尾，就回到开始，例如表的末尾，就回到开始，例如“z”对应于对应于“c”，，“y”对应于对应于“b”，，“x”对应于对应于“a”，如此形成一个循环。

当时罗马的军队就用恺撒，如此形成一个循环当时罗马的军队就用恺撒密码进行通信密码进行通信p恺撒密码明文字母表：恺撒密码明文字母表：A B C D E F G …… X Y Zp恺撒密码密文字母表：恺撒密码密文字母表：D E F G H I J …… A B Cp例：明文为例：明文为“veni，，vidi，，vici”p密文密文“YHAL，， YLGL，，YLFL”，，n意思是意思是“我来，我见，我征服我来，我见，我征服”，曾经是恺撒征服本都王法那西斯后向，曾经是恺撒征服本都王法那西斯后向罗马元老院宣告的名言罗马元老院宣告的名言p26个字符代表字母表的个字符代表字母表的26个字母，从一般意义上说，也可以使用其个字母，从一般意义上说，也可以使用其它字符表，一一对应的数字也不一定要是它字符表，一一对应的数字也不一定要是3，可以选其它数字可以选其它数字p以一种形式写下消息，以另一种形式读取消息以一种形式写下消息，以另一种形式读取消息 pI came I saw I conquered几何图形密码几何图形密码密码学起源密码学起源p16世纪意大利数学家卡尔达诺发明的一种保密通信方法，史称世纪意大利数学家卡尔达诺发明的一种保密通信方法，史称“卡卡尔达诺漏格板尔达诺漏格板”．漏格板是一张用硬质材料．漏格板是一张用硬质材料(如硬纸、羊皮、金属等如硬纸、羊皮、金属等)做成的板，上面挖了一些长方形的孔，即漏格．做成的板，上面挖了一些长方形的孔，即漏格．密码学起源密码学起源p大约在大约在1793年，当时的美国总统托马斯杰斐逊发明了一种轮子年，当时的美国总统托马斯杰斐逊发明了一种轮子密码机。

转动轮子使明文中的所有字母全排在一条直线上为止．密码机转动轮子使明文中的所有字母全排在一条直线上为止．这时圆柱体的其他这时圆柱体的其他25行字母也因这一行的固定而被固定了．任选行字母也因这一行的固定而被固定了．任选这这25行中的一行发出去即为密文．行中的一行发出去即为密文．密码学起源密码学起源p“谜谜”（（ENIGMA）密码最初是由一个叫胡戈）密码最初是由一个叫胡戈·科赫的荷兰科赫的荷兰人发明的起初主要提供给想保护自己生意秘密的公司使人发明的起初主要提供给想保护自己生意秘密的公司使用，但其商界的销路一直不理想后来德国人将其改装为用，但其商界的销路一直不理想后来德国人将其改装为军用型，使之更为复杂可靠德国海军于军用型，使之更为复杂可靠德国海军于1926年开始使年开始使用用“ENIGMA”，陆军则于，陆军则于1928年开始使用年开始使用1933年，年，纳粹最高统帅部通信部决定将纳粹最高统帅部通信部决定将“ENIGMA”作为德国国防军作为德国国防军新式闪击部队的通信装置德国人在战争期间共生产了大新式闪击部队的通信装置德国人在战争期间共生产了大约约10多万部多万部“谜谜”密码机1940年，经过盟军密码分析年，经过盟军密码分析学家的不懈努力，学家的不懈努力，“恩尼格玛恩尼格玛”密码机被动攻破，盟军掌密码机被动攻破，盟军掌握了德军的许多机密，而德国军方却对此一无所知。

握了德军的许多机密，而德国军方却对此一无所知 密码学起源20世纪早期密码机世纪早期密码机什么是密码学？什么是密码学？p密码指得是什么？密码指得是什么？n口令？口令？p密码学研究什么？密码学研究什么？n如何使得某个数据自己能看懂，别人看不懂如何使得某个数据自己能看懂，别人看不懂n如何确保数据的正确来源如何确保数据的正确来源n如何保证通信实体的真实性如何保证通信实体的真实性n如何确保数据在传输过程中没有被删改如何确保数据在传输过程中没有被删改p功能如何实现功能如何实现n算法算法n协议协议密码学的基本任务密码学的基本任务 甲和乙两个人在不安全的信道上进行通信，而他们的敌人甲和乙两个人在不安全的信道上进行通信，而他们的敌人丙不能理解他们正在通信的内容丙不能理解他们正在通信的内容甲甲乙乙丙丙密码算法密码算法p基本概念基本概念n明文明文——要处理的数据要处理的数据n密文密文——处理后的数据处理后的数据n密钥密钥——秘密参数秘密参数n加密函数加密函数n解密函数解密函数密码算法密码算法p密码算法如何构造？密码算法如何构造？n需求需求1：可逆：可逆——算法的使用者可以求得逆函数算法的使用者可以求得逆函数n需求需求2：不可逆：不可逆——敌手无法将密文恢复成明文敌手无法将密文恢复成明文n秘密参数秘密参数——密钥密钥p密码算法实际上是一个带有秘密参数的函数。

密码算法实际上是一个带有秘密参数的函数n知道秘密参数，求逆非常容易知道秘密参数，求逆非常容易n不知道秘密参数，求逆在计算上是不可行的不知道秘密参数，求逆在计算上是不可行的密码学概述密码学概述p密码学是研究密码系统或通信安全的一门科学，密码学是研究密码系统或通信安全的一门科学，它包括两个分支：它包括两个分支：密码编码学和密码分析学密码编码学和密码分析学密码编码学的主要目的是寻求保证消息机密性或认码编码学的主要目的是寻求保证消息机密性或认证的方法，密码分析学主要研究加密消息的破译证的方法，密码分析学主要研究加密消息的破译和消息的伪造和消息的伪造p密码学的目标：机密性、数据完整性、认证和不密码学的目标：机密性、数据完整性、认证和不可否认性可否认性n加密加密n杂凑（杂凑（Hash））n数字签名数字签名密码学概述密码学概述 消息和加密消息和加密p消息被称为明文，用某种方法伪装消息以隐藏它的内容的消息被称为明文，用某种方法伪装消息以隐藏它的内容的过程称为加密，加了密的消息称为密文，而把密文转变为过程称为加密，加了密的消息称为密文，而把密文转变为明文的过程称为解密下图表明了加密和解密的过程明文的过程称为解密。

下图表明了加密和解密的过程p现代密码学引入了密钥，密钥用现代密码学引入了密钥，密钥用K表示K可以是很多数值里的任意值，可以是很多数值里的任意值，密钥密钥K的可能值的范围叫做密钥空间加密和解密运算都使用这个密的可能值的范围叫做密钥空间加密和解密运算都使用这个密钥，即运算都依赖于密钥，并用钥，即运算都依赖于密钥，并用K作为下标表示，加解密函数表达为：作为下标表示，加解密函数表达为：pEK（（M））=CpDK（（C））=MpDK（（EK（（M））））=Mp加密、解密过程如图所示加密、解密过程如图所示p有些算法使用不同的加密密钥和解密密钥，也就是说加密有些算法使用不同的加密密钥和解密密钥，也就是说加密密钥密钥K1与相应的解密密钥与相应的解密密钥K2不同，在这种情况下，加密不同，在这种情况下，加密和解密的函数表达式为：和解密的函数表达式为：pEK1（（M））=CpDK2（（C））=Mp函数必须具有的特性是，函数必须具有的特性是，DK2（（EK1（（M））））=M，如图，如图2所示对称算法 p早期的密钥算法是对称算法（早期的密钥算法是对称算法（Symmetric Algorithm），就是加），就是加密密钥能够从解密密钥中推算出来，反之亦然。

多数对称算法中，加密密钥能够从解密密钥中推算出来，反之亦然多数对称算法中，加密和解密由同一个密钥来控制，也叫密和解密由同一个密钥来控制，也叫“单钥算法单钥算法”，如图所示如图所示非对称算法p用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来，就是非对称算法（算出来，就是非对称算法（Asymmetric Algorithm），也叫公钥算法），也叫公钥算法（（Public-key Algorithm）或双钥算法，如图所示或双钥算法，如图所示 密码学历史回顾密码学历史回顾p三个阶段：三个阶段：n1949年之前年之前p密码学是一门艺术密码学是一门艺术n1949～～1975年年p密码学成为科学密码学成为科学n1976年以后年以后p密码学的新方向密码学的新方向——公钥密码学公钥密码学密码学历史回顾p1949年之前年之前:n古典密码（古典密码（classical cryptography)p 密码学还不是科学密码学还不是科学,而是艺术而是艺术p 出现一些密码算法和加密设备出现一些密码算法和加密设备p 密码算法的基本手段密码算法的基本手段(substitution & permutation)出现，针对的是字符出现，针对的是字符p简单的密码分析手段出现，二战中的多个经典故事简单的密码分析手段出现，二战中的多个经典故事p（（1883））Kerchoffs假设：假定密码分析者和敌手知假设：假定密码分析者和敌手知道所使用的密码系统。

道所使用的密码系统密码学历史回顾密码学历史回顾p1949～～1975年年: n计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能n1949年年Shannon的的“The Communication Theory of Secret Systems” n1967年年David Kahn的的《《The Codebreakers》》n1971-73年年IBM Watson实验室的实验室的Horst Feistel等的等的几篇技术报告：几篇技术报告：pSmith,J.L.,The Design of Lucifer, A Cryptographic Device for Data Communication, 1971pSmith,J.L.,…,An Experimental Application of Cryptography to a remotely Accessed Data System, Aug.1972pFeistel,H.,Cryptography and Computer Privacy, May 1973p数据的安全数据的安全基于密钥基于密钥而不是而不是算法的保密算法的保密密码学历史回顾密码学历史回顾p1976年以后年以后: n1976年年Diffie & Hellman的的“New Directions in Cryptography”提出了不对称密钥密码提出了不对称密钥密码n1977年年Rivest,Shamir & Adleman提出了提出了RSA公钥算法公钥算法n90年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法 p公钥密码使得发送端和接收端无密钥传输的保密公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！通信成为可能！密码学历史回顾密码学历史回顾p1976年以后年以后,对称密钥密码算法进一步发展对称密钥密码算法进一步发展n1977年年DES正式成为标准正式成为标准n80年代出现年代出现“过渡性过渡性”的的“post DES”算法算法,如如IDEA,RCx,CAST等等n90年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Twofish, Serpent等出现等出现n2001年年Rijndael成为成为DES的替代者的替代者密码学历史回顾密码学历史回顾p按照发展进程来分，经历了古典密码、对称密钥按照发展进程来分，经历了古典密码、对称密钥密码和公开密钥密码阶段，古典密码算法有替代密码和公开密钥密码阶段，古典密码算法有替代加密、置换加密；对称加密算法包括流密码和分加密、置换加密；对称加密算法包括流密码和分组密码如组密码如A5A5、、DESDES和和AESAES；非对称加密算法包括；非对称加密算法包括RSA RSA 、背包密码、、背包密码、McElieceMcEliece密码、密码、RabinRabin、椭圆曲线、、椭圆曲线、EIGamal D_HEIGamal D_H等。

等p目前在数据通信中使用最普遍的算法有目前在数据通信中使用最普遍的算法有DESDES算法、算法、AESAES算法、算法、RSARSA算法和算法和ECCECC算法等现代密码学的应用现代密码学的应用p密码学在信息时代有着广泛的应用密码学在信息时代有着广泛的应用p国家安全国家安全p电子商务电子商务p隐私保护隐私保护p信息安全几乎所有领域信息安全几乎所有领域1.3.3 密码攻击概述p 一个加密算法是一个加密算法是无条件安全的无条件安全的，如果算法产生的，如果算法产生的密文不能给出惟一决定相应明文的足够信息此时密文不能给出惟一决定相应明文的足够信息此时无论敌手截获多少密文、花费多少时间，都不能解无论敌手截获多少密文、花费多少时间，都不能解密密文nShannon指出，仅当密钥至少和明文一样长时，才能达到指出，仅当密钥至少和明文一样长时，才能达到无条件安全也就是说除了一次一密方案外，再无其他的加密无条件安全也就是说除了一次一密方案外，再无其他的加密方案是无条件安全的方案是无条件安全的p比无条件安全弱的一个概念是计算上安全的，加比无条件安全弱的一个概念是计算上安全的，加密算法只要满足以下两条准则之一就称为是密算法只要满足以下两条准则之一就称为是计算上计算上安全的安全的：：n1 破译密文的代价超过被加密信息的价值。

破译密文的代价超过被加密信息的价值n2 破译密文所花的时间超过信息的有用期破译密文所花的时间超过信息的有用期仿射密码算法仿射密码算法p加密函数：加密函数：C=E(M)=aM+b mod 26p密钥：密钥：a，，bp解密函数：解密函数：M=D(C)=(C-b)a-1 mod 26p关键在于计算关键在于计算a-1：：a a-1=1 mod 26p方法：扩展的欧几里得算法方法：扩展的欧几里得算法p若若(m, n)=1，则存在整数，则存在整数k1，，k2使得使得 k1m+ k2n=1这里这里k1就是就是m-1 mod n，注意要将，注意要将k1变为正数变为正数-k1 mod n=(n- k1) mod n扩展的欧几里得算法扩展的欧几里得算法p设设a, b∈ ∈Z+, 则存在则存在m, n∈ ∈Z使得使得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+nbr1=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-4 24 = 108-4  (132-108   1) = 108 – 4   132 +4  108 =5*108 – 4*132回顾回顾132=108+24108= 24  4+1224=12  2p求求17-1mod 26。

p26=17  1+9p17=9  1+8p9=8  1+1p8=1  81=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Vigenère密码习题pP10，T2。