例子 大学生鼓起勇气写信给班上某位女同学 请选择以下其中一样在其中打勾：爱情； 友情女同学回送给他一首诗： 愿君多谅知识浅，选题未答缴白卷 爱莫能助实有愧，情愿送诗供君览 元宵夜元宵夜十字街头看花灯十字街头看花灯万人空巷尽欢颜万人空巷尽欢颜火树银花多变换火树银花多变换急星流雨天上升急星流雨天上升爱情密码游戏 小男孩与小女生正在玩“爱情密码游戏345157356465340653770075、9125、1845真的8006相思苦相思苦一往情深一往情深无聊死了无聊死了我想死你了我想死你了我想亲亲你我想亲亲你你亲我就要爱我一辈子你亲我就要爱我一辈子我真的不理你了我真的不理你了有几只海豚?解答-7只海豚Example 2SolutionExample 3跳舞小人历险记跳舞小人历险记摘自福尔摩斯摘自福尔摩斯(Sherlock Holmes) (Sherlock Holmes) “the the Adventure of the Dancing MenAdventure of the Dancing Men住在英国的住在英国的Hilton Hilton CubittCubitt先生最近娶了美国先生最近娶了美国ChicagoChicago的的Elsie PatrickElsie PatrickCubittCubitt在花园发现一张画有跳舞的小人字条，在花园发现一张画有跳舞的小人字条，ElsieElsie一看，脸色大变一看，脸色大变跳舞小人历险记跳舞小人历险记CubittCubitt寄给寄给HolmesHolmes，并前往，并前往HolmesHolmes家说明所知家说明所知的一切的一切HolmesHolmes直觉认为这是一个信息，而非小孩子的直觉认为这是一个信息，而非小孩子的涂鸦涂鸦因提供的字条太少，因提供的字条太少，HolmesHolmes请请CubittCubitt有看到新有看到新的，再传给的，再传给HolmesHolmes看看跳舞小人历险记跳舞小人历险记几日后，几日后，CubittCubitt又在工具室门上发现粉笔画的又在工具室门上发现粉笔画的小人，并临摹下来寄给小人，并临摹下来寄给HolmesHolmes跳舞小人历险记跳舞小人历险记接下来的几天，陆续在工具室发现小人图，接下来的几天，陆续在工具室发现小人图，CubittCubitt全寄给全寄给HolmesHolmes看看跳舞小人历险记跳舞小人历险记HolmesHolmes将全部小人字条研究数天后，发现大事将全部小人字条研究数天后，发现大事不妙，立即赶往不妙，立即赶往CubittCubitt家，欲阻挡悲剧发生家，欲阻挡悲剧发生抵达抵达CubittCubitt家后，家后，CubittCubitt已受枪伤身亡，已受枪伤身亡，ElsieElsie也身受重伤也身受重伤跳舞小人历险记跳舞小人历险记几番调查后，几番调查后，HolmesHolmes终将案情查清楚，便写下终将案情查清楚，便写下一纸条，派马童送至一间叫一纸条，派马童送至一间叫 “ElrigesElriges 旅旅馆的馆的 Abe Abe SlaneySlaney 先生先生警察询问警察询问HolmesHolmes为何对案情这么了解，为何对案情这么了解，HolmesHolmes才开始说明如何破解小人纸条才开始说明如何破解小人纸条跳舞小人历险记跳舞小人历险记HolmesHolmes分析所有的图，发现分析所有的图，发现出现次数最多，便将此符号换成出现次数最多，便将此符号换成 “E E因此图因此图4 4能解读成能解读成 “_E_E_E_E_ 可能为可能为 “LEVER(LEVER(杠杆杠杆) ), , “NEVER(NEVER(绝不绝不) ), , “SEVER(SEVER(分开分开) )。HolmesHolmes猜测是猜测是NEVERNEVER。因此大胆假设因此大胆假设便是便是 “Come ElsieCome Elsie跳舞小人历险记跳舞小人历险记所以第一张字条所以第一张字条可以解开成可以解开成_M _ERE _E SL_NE_M _ERE _E SL_NE_AM _ERE A_E SL_NE_AM _ERE A_E SL_NE_AM HERE ABE SLANEYAM HERE ABE SLANEY跳舞小人历险记跳舞小人历险记第二张字条亦可解读第二张字条亦可解读A_ ELRI_ESA_ ELRI_ESAT ELRIGESAT ELRIGES跳舞小人历险记跳舞小人历险记最后一张最后一张ELSIE _RE_ARE TO MEET THY GO_ELSIE _RE_ARE TO MEET THY GO_ELSIE PREPARE TO MEET THY GODELSIE PREPARE TO MEET THY GOD跳舞小人历险记跳舞小人历险记警察担心凶手跳跑，警察担心凶手跳跑，HolmesHolmes说：他等会儿就说：他等会儿就自己过来了自己过来了HolmesHolmes稍早早已写了字条请凶手过来稍早早已写了字条请凶手过来COME HERE AT ONCECOME HERE AT ONCE跳舞小人历险记跳舞小人历险记Abe Abe SlaneySlaney到场即被逮捕，才道出他是到场即被逮捕，才道出他是ElsieElsie在在ChicagoChicago的未婚夫。的未婚夫。ElsieElsie发现发现SlaneySlaney和她父和她父亲组帮派为非作歹，才逃出与亲组帮派为非作歹，才逃出与CubittCubitt结婚结婚密码学基础密码学基础背景背景在当前全球电子互联互通的时代，由于病毒、黑客、电子在当前全球电子互联互通的时代，由于病毒、黑客、电子窃听和电子欺诈，使得安全性比任何时候都重要；窃听和电子欺诈，使得安全性比任何时候都重要；计算机系统的大量使用和互联，使得我们越来越依赖于这计算机系统的大量使用和互联，使得我们越来越依赖于这些系统所存储和传输的信息，因此需要保护数据和资源不些系统所存储和传输的信息，因此需要保护数据和资源不被泄露，保证数据和消息的真实性，保护系统不受基于网被泄露，保证数据和消息的真实性，保护系统不受基于网络的攻击；络的攻击；密码和网络安全学科已经成熟，可以开发方便实用的应用密码和网络安全学科已经成熟，可以开发方便实用的应用软件来加强网络安全。软件来加强网络安全。信息安全的含义通信保密通信保密通信保密通信保密（COMSECCOMSEC）：）：60-7060-70年代年代 信息保密信息保密信息安全信息安全信息安全信息安全（INFOSECINFOSEC）：）：80-9080-90年代年代 机密性、完整性、可用性、不可否认性机密性、完整性、可用性、不可否认性 等等信息保障信息保障信息保障信息保障（IAIA）：）：9090年代年代- -基本的通讯模型基本的通讯模型通信的保密模型通信的保密模型通信安全通信安全-60年代（年代（COMSEC）发方发方收方收方信源编码信源编码信道编码信道编码信道传输信道传输通信协议通信协议发方发方收方收方敌人敌人信源编码信源编码信道编码信道编码信道传输信道传输通信协议通信协议密码密码信息安全的含义信息安全的含义(80-90年代年代)信息安全的三个基本方面信息安全的三个基本方面保密性保密性Confidentiality即保证信息为授权者享用而不泄漏给未经授权者即保证信息为授权者享用而不泄漏给未经授权者。完整性完整性Integrity数据完整性，未被未授权篡改或者损坏数据完整性，未被未授权篡改或者损坏系统完整性，系统未被非授权操纵，按既定的功系统完整性，系统未被非授权操纵，按既定的功能运行能运行可用性可用性Availability即保证信息和信息系统随时为授权者提供服务，而即保证信息和信息系统随时为授权者提供服务，而不要出现非授权者滥用却对授权者拒绝服务的情况。不要出现非授权者滥用却对授权者拒绝服务的情况。信息安全的其他方面信息安全的其他方面信息的不可否认性信息的不可否认性Non-repudiation：要要求求无无论论发发送送方方还还是是接接收收方方都都不不能能抵抵赖赖所所进进行的传输行的传输鉴别鉴别Authentication鉴鉴别别就就是是确确认认实实体体是是它它所所声声明明的的。适适用用于于用用户、进程、系统、信息等户、进程、系统、信息等审计审计Accountability确保实体的活动可被跟踪确保实体的活动可被跟踪可靠性可靠性Reliability特定行为和结果的一致性特定行为和结果的一致性安全需求的多样性安全需求的多样性保密性保密性一致性一致性可用性可用性可靠性可靠性可认证，真实性可认证，真实性责任定位，审计性责任定位，审计性高性能高性能 实用性实用性占有权占有权信息保障美国人提出的概念:InformationAssurance保护保护保护保护（P Protect）检测检测检测检测（D Detect）反应反应反应反应（R React）恢复恢复恢复恢复（R Restore）保护保护Protect检测检测Detect反应反应React恢复恢复Restore密码从军事走向生活密码从军事走向生活电子邮件电子邮件263.net x263.net自动提款机自动提款机电话卡电话卡:IP卡、卡、201电话卡电话卡银行取钱银行取钱信用卡购物信用卡购物基本概念基本概念密码学密码学(Cryptology):是研究信息系统安全保是研究信息系统安全保密的科学密的科学.密码编码学密码编码学(Cryptography):主要研究对信息主要研究对信息进行编码进行编码,实现对信息的隐蔽实现对信息的隐蔽.密码分析学密码分析学(Cryptanalytics):主要研究加密主要研究加密消息的破译或消息的伪造消息的破译或消息的伪造.基本术语基本术语消息被称为消息被称为明文明文(Plaintext)(Plaintext)。用某种方法伪装消息以用某种方法伪装消息以隐藏它的内容的过程称为隐藏它的内容的过程称为加密加密( (EncrtptionEncrtption) )，被加密被加密的消息称为的消息称为密文密文( (CiphertextCiphertext) )，而把密文转变为明文而把密文转变为明文的过程称为的过程称为解密解密(Decryption)(Decryption)。对明文进行加密操作的人员称作对明文进行加密操作的人员称作加密员加密员或或密码员密码员(Cryptographer).(Cryptographer).密码算法密码算法(Cryptography Algorithm):(Cryptography Algorithm):是用于加密和解是用于加密和解密的数学函数。密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作密码员对明文进行加密操作时所采用的一组规则称作加密算法加密算法(Encryption Algorithm).(Encryption Algorithm).所传送消息的预定对象称为所传送消息的预定对象称为接收者接收者(Receiver).(Receiver).接收者对密文解密所采用的一组规则称为接收者对密文解密所采用的一组规则称为解密算法解密算法(Decryption Algorithm).(Decryption Algorithm).加解密加解密过程示意图过程示意图加密和解密算法的操作通常都是在一组密钥的加密和解密算法的操作通常都是在一组密钥的控制下进行的控制下进行的,分别称为分别称为加密密钥加密密钥(EncryptionKey)和和解密密钥解密密钥(DecryptionKey).明文明文密文加密算法解密算法密钥密钥密码学的目的密码学的目的：Alice和和Bob两个人在不安全的信道上进两个人在不安全的信道上进行通信，而破译者行通信，而破译者Oscar不能理解他们通信的内容。不能理解他们通信的内容。加密通信的模型加密通信的模型Alice加密机解密机Bob安全信道密钥源Oscarxyxk密码体制密码体制密码体制：密码体制：它是一个五元组（它是一个五元组（P,C,K,E,D)满足条件：满足条件：（1）P是可能明文的有限集；（明文空间）是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间）*（4）任意）任意kK,有一个加密算法有一个加密算法和相应的解密算法和相应的解密算法，使得，使得和和分别为加密解密函数，满分别为加密解密函数，满足足dk(ek(x)=x,这里这里xP。密码算法分类密码算法分类-i按照保密的内容分按照保密的内容分:受限制的（受限制的（restricted)算法算法:算法的保密性基于算法的保密性基于保持算法的秘密。保持算法的秘密。基于密钥（基于密钥（key-based)的算法的算法:算法的保密性基算法的保密性基于对密钥的保密。于对密钥的保密。密码算法分类密码算法分类-ii基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类：对称密码算法对称密码算法（symmetriccipher)：又称又称传统密码算法传统密码算法（conventionalcipher)，就是加密密钥和解密密钥相同，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称或实质上等同，即从一个易于推出另一个。又称秘密秘密密钥算法密钥算法或或单密钥算法单密钥算法。非对称密钥算法（非对称密钥算法（asymmetriccipher):加密密钥和解密加密密钥和解密密钥不相同，从一个很难推出另一个。又称密钥不相同，从一个很难推出另一个。又称公开密钥公开密钥算法（算法（public-keycipher)。公开密钥算法用一个密钥进行加密公开密钥算法用一个密钥进行加密,而用另一个进行解而用另一个进行解密密.其中的加密密钥可以公开其中的加密密钥可以公开,又称公开密钥（又称公开密钥（publickey)，简称公钥简称公钥.解密密钥必须保密解密密钥必须保密,又称私人密钥又称私人密钥（privatekey)私钥私钥.简称简称私钥私钥。密码算法分类密码算法分类-iii按照明文的处理方法：按照明文的处理方法：分组密码（分组密码（blockcipher):将明文分成固定长度将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。也是固定长度的密文。流密码（流密码（streamcipher):又称又称序列密码序列密码.序列密序列密码每次加密一位或一字节的明文，也可以称为码每次加密一位或一字节的明文，也可以称为流密码。流密码。序列密码是手工和机械密码时代的主流序列密码是手工和机械密码时代的主流密码算法分类密码算法分类-iv对称密钥密码又可分为：对称密钥密码又可分为：分组密码分组密码 每次对一块数据加密每次对一块数据加密 多数网络加密应用多数网络加密应用 DES,IDEA,RC6,RijndaelDES,IDEA,RC6,Rijndael流密码流密码 每次对一位或一字节加密每次对一位或一字节加密 手机手机 One-time One-time padding,Vigenre,Vernampadding,Vigenre,Vernam密码算法分类密码算法分类-v公开密钥密码公开密钥密码: : 大部分是分组密码，只有概率密码体制属于大部分是分组密码，只有概率密码体制属于流密码流密码 每次对一块数据加密每次对一块数据加密 数字签名数字签名, ,身份认证身份认证 RSA,ECC,ElGamalRSA,ECC,ElGamal 加密解密速度慢加密解密速度慢密码学的起源和发展密码学的起源和发展-i三个阶段：三个阶段：19491949年之前年之前 密码学是一门艺术密码学是一门艺术1949194919751975年年 密码学成为科学密码学成为科学19761976年以后年以后 密码学的新方向密码学的新方向公钥密码学公钥密码学密码学的起源密码学的起源隐写隐写术术(steganography):通过隐藏消息的通过隐藏消息的存在存在来保护消息来保护消息.a.隐形墨水隐形墨水b.字符格式的变化字符格式的变化c.图象图像图象图像example-i(象形文字的修改象形文字的修改)ModifiedHieroglyphics,c.1900B.C.密码学的第一个例子是对标准书写符号的修改密码学的第一个例子是对标准书写符号的修改例如例如:古埃及法老坟墓上的文字古埃及法老坟墓上的文字思想思想:代替代替(substitution)埃及象形文字埃及象形文字公元前公元前1919世纪，埃及人将象形文字写在各处以世纪，埃及人将象形文字写在各处以联络族人联络族人埃及象形文字埃及象形文字因此埃及象形文字乃是我们有知以来最早的加因此埃及象形文字乃是我们有知以来最早的加密系统密系统example-iiSpartanScytale,c.500B.C.斯巴达人用于加解密的一种军事设备斯巴达人用于加解密的一种军事设备发送者把一条羊皮螺旋形地缠在一个圆柱形棒发送者把一条羊皮螺旋形地缠在一个圆柱形棒上上思想：置换（思想：置换（permutation)example-iiiPolybiusCheckerboard,205123B.C.明文明文:POLYBIUS密文密文:3534315412244543123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZ希腊人，发明一5x5方格加密，将字母转换成数字。先取得列号，再取得行号课堂练习:TAIWANExample-ivCaesarCipher,c.50B.C.ABCDEFGXYZDEFGHIJABC明文明文:Caesarcipherisashiftsubstitution密密文文:FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQJuliusCaesar(100BC44AD)，罗马皇帝，发明凯撒加密法，亦称凯撒位移课堂练习：PHHWPHDIWHUWKHWRJDSDUWBABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC明文明文:OMNIAGALLIAESTDIVISAINPARTESTRES(高卢全境可分为三个部分高卢全境可分为三个部分)密文密文:RPQLDJDOOLDHVWGLYLVDLQSDUWHVWUHVPlainTextandCipherText明文和密文Fig2.4HiAmit,Hopeyouaredoingfine.HowaboutmeetingatthetrainstationthisFridayat5pm?Pleaseletmeknowifitisokwithyou.Regards.AtulKlDplw,Krshbrxduhgrlqjilqh.KrzderxwphhwlqjdwwkhwudlqvwdwlrqwklvIulgdbdw5sp?Sohdvhohwphnqrzlilwlvrnzlwkbrx.Uhjdugv.DwxoPlaintextmessageCorrespondingciphertextmessageExample-VNomenclator代码本代码本c.1400字母、符号、单词、短语字母、符号、单词、短语代码代码代码代码字母、符号、单词、短语字母、符号、单词、短语应用：应用：WorldWarIIMono alphabetic Mono alphabetic 加密法加密法有别于有别于CaesarCaesar加密法的全部位移加密法的全部位移k k个位置个位置改为单一字母个别位移固定的位置改为单一字母个别位移固定的位置如如 a S b A c H d Va S b A c H d V破解破解Mono alphabeticMono alphabetic密文密文UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ明文明文=?=?利用统计方式，分析字母出现频率利用统计方式，分析字母出现频率P 13.33H 5.83F 3.33B 1.67C 0.00Z 11.67D 5.00W 3.33G 1.67L 0.00S 8.33E 5.00Q 2.50Y 1.67K 0.00U 8.33V 4.17T 2.50I 0.83N 0.00O 7.50X 4.17A 1.67J 0.83R 0.00M 6.67破解破解Mono alphabeticMono alphabetic一般英文文章中，字元相对出现频率一般英文文章中，字元相对出现频率破解破解Mono alphabeticMono alphabeticUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ t a e e te a that e e a aVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX e t ta t ha e ee a e th z aEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ e e e tat e the t逐一测试解密：it was disclosed yesterday that several informal butdirect contacts have been made with politicalrepresentatives of the viet cong in moscowieie在在ChicagoChicago的未婚夫。的未婚夫。ElsieElsie发现发现SlaneySlaney和她和她父亲组帮派为非作歹，才逃出与父亲组帮派为非作歹，才逃出与CubittCubitt结婚结婚countrelativeletterfrequencies(seetext)guessP&ZareeandtguessZWisthandhenceZWPistheproceedingwithtrialanderrorfinallyget:密码学的起源和发展密码学的起源和发展-ii19491949年之前年之前: : 古典密码（古典密码（classical cryptography)classical cryptography) 密码学还不是科学密码学还不是科学, ,而是艺术而是艺术 出现一些密码算法和加密设备出现一些密码算法和加密设备 密码算法的基本手段密码算法的基本手段(substitution & (substitution & permutation)permutation)出现出现，针对的是字符，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现密码学的起源和发展密码学的起源和发展-iii1949194919751975年年: : 计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能19491949年年ShannonShannon的的“The Communication Theory of The Communication Theory of Secret SystemsSecret Systems” 19671967年年David KahnDavid Kahn的的The The CodebreakersCodebreakers1971-731971-73年年IBM WatsonIBM Watson实验室实验室的的Horst Horst FeistelFeistel等的几等的几篇技术报告篇技术报告Smith,J.L.,TheDesignofLucifer,ACryptographicDeviceforDataCommunication,1971Smith,J.L.,AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem,Aug.1972Feistel,H.,CryptographyandComputerPrivacy,May1973数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密密码学的起源和发展密码学的起源和发展-iv19761976年以后年以后: : 19761976年年DiffieDiffie & Hellman & Hellman的的“New Directions New Directions in Cryptographyin Cryptography”提出了不对称密钥密码提出了不对称密钥密码19771977年年Rivest,ShamirRivest,Shamir & & AdlemanAdleman提出了提出了RSARSA公公钥算法钥算法9090年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法 公钥密码使得发送端和接收端无密钥传输的公钥密码使得发送端和接收端无密钥传输的保密通信成为可能保密通信成为可能！密码学的演变历史密码学的演变历史(1)1918,WilliamFriedmansTheIndexofCoincidenceanditsApplicationsinCryptographyWilliamFrederickFriedman(September24,1891November12,1969)美国陆军密码专家。美国陆军密码专家。1930年代，他年代，他领导了陆军的一个研究部门领导了陆军的一个研究部门SignalsIntelligenceService(SIS)，其中一部分服务一直延续到五十年代。三十年，其中一部分服务一直延续到五十年代。三十年代晚期，在他的指导下，代晚期，在他的指导下，FrankRowlett破解了日本人破解了日本人的的PURPLE加密机，这样就截获了日本的大量外交和军加密机，这样就截获了日本的大量外交和军事的秘密。事的秘密。密码学的演变历史密码学的演变历史(2)EdwardHebern,RotorMachinefor50Years.1948,ClaudeShannons“TheCommunicationTheoryofSecrecySystem”成为现代密码学理论成为现代密码学理论基础基础ClaudeElwoodShannon(Apr.30,1916Feb.24,2001),是美国的一个电气工程师和数学家，被誉为信息论之父thefatherofinformationtheory.香农之有名在于他以1948年发表的那篇旷世论文而奠定了现代信息论基础。其实早在1937年当21岁的香农还是MIT一个硕士研究生时，他便在他的硕士论文中论述了布尔代数的电子实现和应用，可以构建和解决任何逻辑的和数字的关系，因此他奠定了数字计算机和数字电路设计理论的基础。他的硕士论文一直被认为是迄今最重要的硕士论文。1949-1967，CryptographicLiteraturewasbarren密码学的演变历史密码学的演变历史(3)1971,IBM发明发明LucifferCipher,128位密钥作分位密钥作分组加密。这项发明是由组加密。这项发明是由HorstFeistel(Jan.30,1915Nov.14,1990)领导的，他是密码学家，当时领导的，他是密码学家，当时在在IBM负责设计加密器，他的工作最终激发了负责设计加密器，他的工作最终激发了70年代年代DataEncryptionStandard(DES)的研发高的研发高潮潮1976-1977，美国国家标准局正式公布实施，美国国家标准局正式公布实施DES1975,WhitfieldDiffieandMatinHellman,ANewDirectioninCryptography,首次提出适应网首次提出适应网络保密通信的公开密钥思想，揭开现代密码学研络保密通信的公开密钥思想，揭开现代密码学研究的序幕，具有划时代的意义究的序幕，具有划时代的意义密码学的演变历史密码学的演变历史(4)19771978，RonaldRivest,AdiShamir,LenAdleman第一次提出公开密钥密码系第一次提出公开密钥密码系统的实现方法统的实现方法RSA1981，成立，成立InternationalAssociationforCryptologyResearch1985，AbbasElGamal提出概率密码系统提出概率密码系统ElGamal方法方法19901992，LaiXuejiaandJames:IDEA,TheInternationalDataEncryptionAlgorithm2000,AES,AdvancedEncryptionStandardCryptology(保密学保密学)，源自希腊语，源自希腊语(Greek)Krypts:hidden;logos:word,是密码学和密码处理过程的研究是密码学和密码处理过程的研究Cryptography:TheScienceandStudyofSecretWriting，密码编码，密码编码学学Cryptanalysis:TheScienceandStudyofSecretBreaking，密码破译，密码破译学学Cipher:Asecretmethodofwriting加密方法加密方法Encipher(encipherment),encryption:将明文转换成密文的过程将明文转换成密文的过程Decipher(decipherment),decryption:将密文还原成明文的过程将密文还原成明文的过程Plaintext(cleartext):原始的可读数据，明文原始的可读数据，明文Ciphertext(Cryptogram):加密后的不可解读之文件，密文加密后的不可解读之文件，密文Key:密钥，对加密与解密过程进行控制的参数密钥，对加密与解密过程进行控制的参数E(m):EncryptionTransformation加密变换加密变换D(c):DecryptionTransformation解密变换解密变换密码学基本术语密码学基本术语Terminologies密码学的起源和发展密码学的起源和发展-v19761976年以后年以后: : 对称密钥密码算法进一步发展对称密钥密码算法进一步发展19771977年年DESDES正式成为标准正式成为标准8080年代出现年代出现“过渡性过渡性”的的“post DESpost DES”算法算法, ,如如IDEA,RCx,CASTIDEA,RCx,CAST等等9090年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Rijndael,RC6, MARS, TwofishTwofish, Serpent, Serpent等出等出现现20012001年年RijndaelRijndael成为成为DESDES的替代者的替代者密码分析密码分析假设破译者假设破译者Oscar是在已知密码体制的前提下来是在已知密码体制的前提下来破译破译Bob使用的密钥。这个假设称为使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：原则。最常见的破解类型如下：1.唯密文攻击：唯密文攻击：Oscar具有密文串具有密文串y.2.已知明文攻击已知明文攻击:Oscar具有明文串具有明文串x和相应的密和相应的密文文y.3.选择明文攻击：选择明文攻击：Oscar可获得对加密机的暂时可获得对加密机的暂时访问，访问，因此他能选择明文串因此他能选择明文串x并构造出相应的密并构造出相应的密文串文串y。4.选择密文攻击选择密文攻击:Oscar可暂时接近密码机可暂时接近密码机,可选可选择密文串择密文串y，并构造出相应的明文并构造出相应的明文x.这一切的目的在于这一切的目的在于破译出密钥或密文破译出密钥或密文密码破译密码破译密码破译的原则密码破译的原则:遵循观察与经验遵循观察与经验方法方法:采用归纳与演绎采用归纳与演绎步骤步骤:分析、假设、推测和证实分析、假设、推测和证实三大要素：三大要素：语言的频率特征：语言的频率特征：e连接特征连接特征:qu,Iex,重复特征重复特征:th,tion,tious理论安全，或无条件安全理论安全，或无条件安全TheoreticalSecure(orPerfectSecure)攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。明文。Shannon用理论证明：欲达理论安全，加密密钥长度必须用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密，大于等于明文长度，密钥只用一次，用完即丢，即一次一密，One-timePad，不实用。，不实用。实际安全，或计算上安全实际安全，或计算上安全PracticalSecure(orComputationallySecure)如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统的分析方法来是，在有限的资源范围内，攻击者都不能通过系统的分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行上不可行(ComputationallyInfeasible)。理论安全和实际安全理论安全和实际安全密码算法的安全性密码算法的安全性无条件安全（无条件安全（Unconditionally Unconditionally securesecure） 无论破译者有多少密文无论破译者有多少密文, ,他也无法解出他也无法解出对应的明文对应的明文, ,即使他解出了即使他解出了, ,他也无法验他也无法验证结果的正确性证结果的正确性. . Onetime pad Onetime pad计算上安全（计算上安全（Computationally Computationally securesecure）破译的代价超出信息本身的价值破译的代价超出信息本身的价值破译的时间超出了信息的有效期破译的时间超出了信息的有效期. .穷举攻击穷举攻击总是可以简单地尝试每一个可能的密钥总是可以简单地尝试每一个可能的密钥穷举攻击是最基本的攻击，难度与密钥长度成穷举攻击是最基本的攻击，难度与密钥长度成正比正比平均来说要获得成功必须尝试所有可能密钥的平均来说要获得成功必须尝试所有可能密钥的一半一半古典密码古典密码基于字符的密码基于字符的密码代替密码（代替密码（substitutioncipher)：就是明文中的就是明文中的每一个字符被替换成密文中的另一个字符。接每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。收者对密文做反向替换就可以恢复出明文。置换密码置换密码(permutationcipher)，又称又称换位密码换位密码（transpositioncipher)：明文的字母保持相同，明文的字母保持相同，但顺序被打乱了。但顺序被打乱了。代替密码代替密码简单代替密码（简单代替密码（simplesubstitutioncipher),又又称称单字母密码（单字母密码（monoalphabeticcipher):明文明文的一个字符用相应的一个密文字符代替。的一个字符用相应的一个密文字符代替。多字母密码（多字母密码（ployalphabeticcipher)：明文中明文中的字符映射到密文空间的字符还依赖于它在上的字符映射到密文空间的字符还依赖于它在上下文中的位置。下文中的位置。单字母密码单字母密码单表代换密码单表代换密码移位（移位（shift）密码、乘数（密码、乘数（multiplicative)密码密码仿射（仿射（affine)密码、多项式（密码、多项式（Polynomial)密码密码密钥短语（密钥短语（KeyWord)密码密码多表代换密码多表代换密码维吉尼亚（维吉尼亚（Vigenere)密码密码博福特（博福特（Beaufort）密码密码滚动密钥滚动密钥(running-key)密码密码弗纳姆弗纳姆(Vernam)密码密码转子机转子机(rotormachine)多多字母代换密码字母代换密码可以用矩阵变换方便地描述多可以用矩阵变换方便地描述多字母代换密码字母代换密码，有时又称起为有时又称起为矩阵变换密码矩阵变换密码。HillcipherPlayfaircipher模模q算术算术-i同余同余：给定任意整数给定任意整数a和和q，以，以q除除a，余数是余数是r，则，则可以表示为可以表示为a=sq+r,0 r FLSKHU 实际算法为：实际算法为： 有有 同时有，同时有，d3(y)=y-3 (mod 26)移位密码分析移位密码分析给定加密的消息给定加密的消息:PHHWPHDIWHUWKHWRJDSDUWB由于（）加解密算法已知由于（）加解密算法已知（）可能尝试的密钥只有（）可能尝试的密钥只有6个个通过强力攻击得到明文：通过强力攻击得到明文：meetmeafterthetogaparty.移位密码很容易受到唯密文攻击。移位密码很容易受到唯密文攻击。乘数密码算法乘数密码算法加密函数取形式为加密函数取形式为e(x)=ax(mod26),aZ/(26)要求唯一解的充要条件是要求唯一解的充要条件是gcd(a,26)=1该算法描述为：该算法描述为：设设P=C=Z/(26)，K=aZ/(26)|gcd(a,26)=1,对对k=aK,定义定义ek(x)=ax(mod26)和和dk(y)=a-1(y)(mod26)x,yZ/(26)例子例子: a=9, ABCDEFGHIJKLMNOPQRSTUVWXYZ AJSBKTCLUDMVENWFOXGPYHQZIR 明文明文 密文密文 cipher = SUFLKX乘数密码分析乘数密码分析对于乘数密码，当且仅当对于乘数密码，当且仅当a与互素时，加与互素时，加密变换才是一一映射的，因此密变换才是一一映射的，因此a的选择有的选择有种：种：a=3,5,7,9,11,15,17,19,21,23,25可能尝试的密钥只有可能尝试的密钥只有1个个仿射密码算法仿射密码算法-i加密函数取形式为加密函数取形式为e(x)=ax+b(mod26),a,bZ/(26)要求唯一解的充要条件是要求唯一解的充要条件是gcd(a,26)=1该算法描述为：该算法描述为：设设P=C=Z/(26)K=(a,b)Z/(26)Z/(26)|gcd(a,26)=1,对对k=(a,b)K,定义定义ek(x)=ax+b(mod26)和和dk(y)=a-1(y-b)(mod26)x,yZ/(26)q=26时，可能的密钥是时，可能的密钥是2612=311个个仿射密码算法仿射密码算法-ii例子，设例子，设k（7，3），），注意到注意到7-1(mod26)=15,加密函加密函数是数是ek(x)=7x+3,相应的解密函数是相应的解密函数是dk(y)=15(y-3)=15y-19,易见易见dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)若加密明文：若加密明文：hot，首先转换字母首先转换字母h,o,t成为数字成为数字7,14,19,然后加密：然后加密：解密：解密：任意的单表代替密码算法任意的单表代替密码算法设设P=C=Z/(26)，K是由是由26个符号个符号0，1,.,25的所有可能的所有可能置换组成。任意置换组成。任意K，定义定义e(x)=(x)=y且且d(y)= -1(y)=x,-1是是的逆置换。的逆置换。注：注：1*.置换置换的表示：的表示：2*密钥空间密钥空间K很大，很大，|k|=26!41026，破译者穷举搜索是破译者穷举搜索是不行的，然而，可由统计的方式破译它。不行的，然而，可由统计的方式破译它。3*移位密码、乘数密码、仿射密码算法都是替换密码的移位密码、乘数密码、仿射密码算法都是替换密码的特例特例0123.2324250123.232425)(单表替换密码的破译单表替换密码的破译通过字母的使用频率破译通过字母的使用频率破译对抗频率分析的办法对抗频率分析的办法多名或同音代替密码多名或同音代替密码多表代替密码多表代替密码多字母代替密码多字母代替密码多名代替密码多名代替密码与与简简单单代代替替密密码码类类似似，只只是是映映射射是是一一对对多多的的，每个明文字母可以加密成多个密文字母。每个明文字母可以加密成多个密文字母。例如，例如，A可能对应于可能对应于5、13、25B可能对应于可能对应于7、9、31、42当当对对字字母母的的赋赋值值个个数数与与字字母母出出现现频频率率成成比比例例时时。这这是是因因为为密密文文符符号号的的相相关关分分布布会会近近似似于于平平的的，可以挫败频率分析。可以挫败频率分析。然然而而，若若明明文文字字母母的的其其它它统统计计信信息息在在密密文文中中仍仍很明显时，那么同音代替密码仍然是可破译的。很明显时，那么同音代替密码仍然是可破译的。多表多表代替密码代替密码多表多表代替密码：代替密码：是以一系列（两个以上）代换是以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。表依此对明文消息的字母进行代换的方法。非周期多标代替密码：非周期多标代替密码：代换表是非周期的无限序列代换表是非周期的无限序列一次一密密码（一次一密密码（onetimepadding):对每个明文对每个明文每次采用不同的代换表。每次采用不同的代换表。周期多表代替密码：代换表个数有限，重复使周期多表代替密码：代换表个数有限，重复使用。用。Vigenre cipher (1858)是一种多表移位代替密码是一种多表移位代替密码设设d为一固定的正整数，为一固定的正整数，d个移位代换表个移位代换表 =（ 1， 2, d)由由密钥序列密钥序列K（k1,k2,kd)给定给定，第，第i+td个明文字母由表个明文字母由表 i决定，即密钥决定，即密钥ki决定决定ek(xi+td)=(xi+td+ki,)modq=ydk(yi+td)=(xi+td-ki)modq=x例子：例子：q=26,x=polyalphabeticcipher,K=RADIO明文明文x=polyalphabeticcipher密钥密钥k=RADIORADIORADIORADIO密密文文y=GOOGOCPKTPNTLKQZPKMFVigenre cipher- -破译破译依然保留了字符频率某些统计信息依然保留了字符频率某些统计信息重码分析法：间距是密钥长度整数倍的相同子串有相重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大。相同的可能性很大。 a b c d e f g h i j k l m 000102 030405 060708 091011 12 n o p q r s t u v w x y z 131415 161718 192021 222324 25密钥密钥: cryptographycryptographycr明文明文: yourpackagereadyroomathree密文密文: AFSGIOI PG PG滚动密钥密码滚动密钥密码对于周期代换密码，当密钥的长度对于周期代换密码，当密钥的长度d和明文一和明文一样长时，就成为滚动密钥密码。样长时，就成为滚动密钥密码。VigenreVigenre本人建议密钥与明文一样长本人建议密钥与明文一样长Vernam密码密码19181918年，年，GillbertGillbert VernamVernam建议密钥与明文一建议密钥与明文一样长并且没有统计关系的密钥内容样长并且没有统计关系的密钥内容，他，他采用的采用的是二进制数据是二进制数据: : 加密加密：C Ci i = P = Pi i K Ki i 解密解密 P Pi i = = C Ci i K Ki i 核心：构造和消息一样长的随机密钥核心：构造和消息一样长的随机密钥 2.2.3 Playfair密码密码单表代换尽管有大量的密钥，也不能提供足够的安全性，单表代换尽管有大量的密钥，也不能提供足够的安全性，因为密文中残留了大量的明文结构，一种解决办法是引进因为密文中残留了大量的明文结构，一种解决办法是引进多表代换密码。多表代换密码。Playfair密码是最著名的多表代换密码，它把明文中的双密码是最著名的多表代换密码，它把明文中的双字母音节作为一个单元转换成密文的双字母音节。字母音节作为一个单元转换成密文的双字母音节。Playfair密码是由英国科学家密码是由英国科学家CharlesWheatstone在在1854年年发明的，用了他的朋友发明的，用了他的朋友BaronPlayfair的名字命名。的名字命名。Playfair算法基于一个由密钥词构成的算法基于一个由密钥词构成的5x5字母矩阵字母矩阵Playfair密码的密钥矩阵密码的密钥矩阵假定使用的密钥词是假定使用的密钥词是MONARCHY先在先在5x5矩阵中填上密钥词，去掉重复字母矩阵中填上密钥词，去掉重复字母再将剩余的字母按字母表的顺序从左至右、从上至下填再将剩余的字母按字母表的顺序从左至右、从上至下填在矩阵剩下的格子中，在矩阵剩下的格子中，I和和J当作一个字母当作一个字母MONARCHYBDEFGI/JKLPQSTUVWXZPlayfair密码的加密密码的加密对明文按如下规则一次加密两个字母对明文按如下规则一次加密两个字母1.如果该字母对的两个字母是相同的，则在其中插入一个填充字母，如x,“balloon”加密成“balxloon”2.落在同一行的明文字母对中的字母由其右边的字母来代换，每行中最右的字母用该行最左边的第一个字母来代换,如“ar”加密成“RM”3.落在同一列的明文字母对中的字母由其下面的字母来代换，每列中最下面的一个字母用该列最上面的第一个字母来代换,如“mu”加密成“CM”4.其他的每组明文字母对中的字母按如下方式代换：该字母所在行为密文所在行，另一字母所在列为密文所在列，如“hs”变换成“BP”，“ea”代换为“IM”或“JM”(asdesired)Playfair密码的安全性密码的安全性安全性比单表代换大为提高安全性比单表代换大为提高因为有因为有26个字母，因此有个字母，因此有26x26=676字母对，对单个字字母对，对单个字母对进行判断要困难得多。母对进行判断要困难得多。单个字母的相对频率比字母对的相对频率在统计规律上单个字母的相对频率比字母对的相对频率在统计规律上要好，利用频率分析字母对就更困难些，需要要好，利用频率分析字母对就更困难些，需要676输入的输入的频率表来进行分析。频率表来进行分析。被广泛地使用了许多年，包括在一战和二战时期被广泛地使用了许多年，包括在一战和二战时期因为它的密文仍然完好地保留了明文语言的大部分结构因为它的密文仍然完好地保留了明文语言的大部分结构特征，它仍然是相对容易攻破的，几百个字母的密文就特征，它仍然是相对容易攻破的，几百个字母的密文就足够分析出规律了。足够分析出规律了。字母出现的相对频率字母出现的相对频率“明文明文”曲线画出曲线画出7万个字母的频率分布，对文中出现的每万个字母的频率分布，对文中出现的每个字母计数，结果除以字母个字母计数，结果除以字母e的出现次数。的出现次数。加密后的曲线体现了加密后字母频率分布被掩盖的程度，如加密后的曲线体现了加密后字母频率分布被掩盖的程度，如果完全被掩盖，则应该是一条水平线。果完全被掩盖，则应该是一条水平线。多多字母代替密码字母代替密码-PlayfairPlayfair:将明文中的双字母组合作为一个单元将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。对待，并将这些单元转换为密文的双字母组合。5555变换矩阵变换矩阵: I: I与与J J视为同一字符视为同一字符C I P H EC I P H ER A B D FR A B D FG K L M N(cipher)G K L M N(cipher)O Q S T UO Q S T UV W X Y ZV W X Y Z加密规则加密规则: :按成对字母加密按成对字母加密1)1) 相同对中的字母加分隔符相同对中的字母加分隔符( (如如x)x)2)2) balloon balloon baba lx lo on lx lo on3)3) 同行取右边同行取右边: he: he EC EC4)4) 同列同列取下边取下边: dm : dm MT MT5)5) 其他其他取交叉取交叉: : ktkt MQ OD MQ OD TR TRPlayfair举例举例以前面的以前面的5555变换矩阵变换矩阵(cipher)(cipher)为例为例 C I P H EC I P H ER A B D FR A B D FG K L M N(cipher)G K L M N(cipher)O Q S T UO Q S T UV W X Y ZV W X Y Z(1)balloon (1)balloon baba lx lo on db sp lx lo on db sp gsgs ugug(2)book (2)book bobo ok ok srsr qgqg(3)fill (3)fill fifi lx lx lx lx aeae sp sp sp spPlayfair密码分析密码分析PlayfairPlayfair有有2626X X2626=676=676种字母对组合种字母对组合字符出现几率一定程度上被均匀化字符出现几率一定程度上被均匀化基于基于字母字母频率的攻击比较困难频率的攻击比较困难依然保留了相当的结构信息依然保留了相当的结构信息Hill密码（密码（1929）基于矩阵的线性变换基于矩阵的线性变换: : K K是一个是一个m*mm*m矩阵矩阵, ,在在Z/(26)上可逆上可逆, ,即存在即存在K K-1-1使得使得: :KKKK-1-1 = I ( = I (在在Z/(26) )对每一个对每一个kK,定义定义ek(x)=xK(mod26)和和dk(y)=yK-1(mod26)注：明文与密文都是注：明文与密文都是m元的向量元的向量（x1,x2,xm);(y1,y2,ym)，Z/(26)为同余类环。在这个环上的可逆矩阵为同余类环。在这个环上的可逆矩阵Amxm,是指行列式是指行列式detAmxm的值的值Z*/(26),它为它为Z/(26)中中全体可逆元的集合。全体可逆元的集合。Z*/(26)=aZ/(26)|(a,26)=1，Z*/(26)=1,3,5,7,9,11,15,17,19,21,23,25Hill密码的例子密码的例子-i例子：当例子：当m=2时，明文元素时，明文元素x=(x1,x2),密文元素密文元素y=(y1,y2)(y1,y2)=(x1,x2)K若若K=,可得可得K-1=若对明文若对明文july加密，它分成加密，它分成2个元素（个元素（j,u),(l,y),分别对应于分别对应于（9,20）,（11,24）,有有（9,20）（9960,72140）（）（3,4）且且（11,24）(12172,88168)（11,22）于是对于是对july加密的结果为加密的结果为DELW。Hill密码的例子密码的例子-ii为了解密，为了解密，Bob计算计算且且因此，得到了正确的明文因此，得到了正确的明文“july”Hill密码分析密码分析完全隐藏了字符完全隐藏了字符( (对对) )的频率信息的频率信息线性变换的安全性很脆弱，易被已知明文攻击击破。线性变换的安全性很脆弱，易被已知明文攻击击破。对于一个对于一个mxmmxm的的hillhill密码，假定有密码，假定有m m个明文个明文- -密文对，明密文对，明文和密文的长度都是文和密文的长度都是m.m.可以把明文和密文对记为：可以把明文和密文对记为：P Pj j= =(p(p1j1j,p,p2j2j,.p,.pmjmj) )和和C Cj j=(C=(C1j1j,C,C2j2j,C Cmjmj), ), C Cj j=KP=KPj j,1,1 j j m m 定义定义mxmmxm的方阵的方阵X=X=（P Pijij) Y=() Y=(C Cijij),),得到得到Y=KXY=KX，K=YXK=YX-1-1例子：例子：fridayfriday PQCFKU PQCFKU K(5 17)=(15 16) K(8 3)=(2 5) K(0 24)=(10 20) K(5 17)=(15 16) K(8 3)=(2 5) K(0 24)=(10 20) 因此，因此，置换密码置换密码换位密码把明文按列写入换位密码把明文按列写入, ,按行读出按行读出密钥包含密钥包含3 3方面信息方面信息: : 行宽行宽, ,列高列高, ,读出顺序读出顺序key:4312567plaintext:attackpostponeduntiltwoamxyzciphertext:TTNAAPTMTSUOAODWCOIXPETZ完全保留字符的统计信息完全保留字符的统计信息使用多轮加密可提高安全性使用多轮加密可提高安全性2.2.5 Polyalphabetic Ciphers多表代换密码多表代换密码改进简单的单表代换的方法是在明文消息中采用不同改进简单的单表代换的方法是在明文消息中采用不同的单表代换，这就是多表代换密码的单表代换，这就是多表代换密码poly-alphabeticsubstitutionciphers因为需要猜测更多的字母表，并且频率分布特性也变因为需要猜测更多的字母表，并且频率分布特性也变得平坦了，所以使得密码破译更加困难得平坦了，所以使得密码破译更加困难使用一密钥词对每个明文字母选择一个字母表来加密使用一密钥词对每个明文字母选择一个字母表来加密依次使用每个字母表依次使用每个字母表如果到了密钥词最后一个字母，则从头开始继续如果到了密钥词最后一个字母，则从头开始继续Vigenre密码密码最简单的多表代换密码是最简单的多表代换密码是Vigenre密码，它其实是多重密码，它其实是多重Caesar密码密码26个密码水平放置，最左边是密钥字母，顶部排列的是明个密码水平放置，最左边是密钥字母，顶部排列的是明文的标准字母表文的标准字母表加密一条消息需要与消息一样长的密钥，密钥是密钥词的加密一条消息需要与消息一样长的密钥，密钥是密钥词的重复，比如，密钥词为重复，比如，密钥词为K=k1k2.kd加密：给定密钥字母加密：给定密钥字母x和明文字母和明文字母y，密文字母是位于，密文字母是位于x行和行和y列的那个字母列的那个字母密钥词的第密钥词的第i字母，表明使用第字母，表明使用第i个字母表轮，流使用字母个字母表轮，流使用字母表，如果到了消息的第表，如果到了消息的第d个字母时则从头再做个字母时则从头再做解密：密钥字母决定行，行里密文字母所在列的顶部字母解密：密钥字母决定行，行里密文字母所在列的顶部字母就是明文字母就是明文字母Example写下明文写下明文在明文之上重复写下密钥在明文之上重复写下密钥像使用像使用Caesarcipher密钥那样使用每一个密钥字母，密钥那样使用每一个密钥字母，加密每一个明文字母加密每一个明文字母比如，使用密钥比如，使用密钥deceptivekey: deceptivedeceptivedeceptiveplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ练习：练习：MEETMEAFTERSCHOOL密钥：密钥：ESPIONAGE答案答案QWTBARALXIJHKVBORVigenre密码的安全性密码的安全性每一个明文字母可以有多个密文字母对应，这样字母使用的频率特每一个明文字母可以有多个密文字母对应，这样字母使用的频率特性减弱了，但是没有完全消失性减弱了，但是没有完全消失攻击者首先要分析密文是否是用单表代换加密的，即通过简单的测攻击者首先要分析密文是否是用单表代换加密的，即通过简单的测试密文的统计特性试密文的统计特性如果认为是用如果认为是用Vigenre密码加密的，破译能否取得进展将取决于能密码加密的，破译能否取得进展将取决于能否判定密钥词的长度，要通过发现重复序列来判断否判定密钥词的长度，要通过发现重复序列来判断如果密钥词长度是如果密钥词长度是N，那么密码实际上包含了，那么密码实际上包含了N个单表代换个单表代换密钥词的周期性可以用与明文信息一样长的不重复密钥词来消除，密钥词的周期性可以用与明文信息一样长的不重复密钥词来消除，如如“密钥自动生成系统密钥自动生成系统”，但是密文和明文具有相同频率分布特性，但是密文和明文具有相同频率分布特性，仍然是易受攻击的仍然是易受攻击的最终措施是选择与明文毫无统计关系且和它一样长的密钥最终措施是选择与明文毫无统计关系且和它一样长的密钥Kasiski Method to break Vigenre卡西斯基方法破解卡西斯基方法破解Vigenre破解破解Vigenre的方法是由的方法是由Charles Babbage(巴贝奇巴贝奇)和和FriedrichKasiski(卡西斯基卡西斯基)分别发现的。分别发现的。密文中的重复性可以暗示出密钥词长度密文中的重复性可以暗示出密钥词长度如果两个相同明文序列之间的距离是密钥词长度的整数如果两个相同明文序列之间的距离是密钥词长度的整数倍，那么产生的密文序列也是相同的倍，那么产生的密文序列也是相同的前例中前例中“red”的两次出现相隔的两次出现相隔9个字母，因此得到了两个字母，因此得到了两个相同密文序列个相同密文序列VTW这时攻击者就可以猜测密钥词的长度是这时攻击者就可以猜测密钥词的长度是3或者或者9这样攻击者可以像先前攻击单表密码那样分别进行攻击这样攻击者可以像先前攻击单表密码那样分别进行攻击密钥词的周期性可以用与明文信息一样长的不重复密钥密钥词的周期性可以用与明文信息一样长的不重复密钥词来消除，词来消除，AutokeyCipherAutokey Cipher最理想的是让密钥和要加密的消息一样长最理想的是让密钥和要加密的消息一样长Vigenre提出了提出了autokeycipher，密钥词，密钥词keyword放在消息放在消息前面作为密钥前面作为密钥key前缀前缀知道了密钥词能够破译密文的前面一些字母，据此可以解知道了密钥词能够破译密文的前面一些字母，据此可以解密密文消息的其余部分密密文消息的其余部分但是这种方法仍然具有但是这种方法仍然具有字母使用的频率特性可供分析字母使用的频率特性可供分析例如，给定密钥词：例如，给定密钥词：deceptivekey: deceptivewearediscoveredsavplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA古典密码小结古典密码小结Substitution & permutationSubstitution & permutation密码分析密码分析多轮加密多轮加密数据安全基于算法的保密数据安全基于算法的保密Enigma：密码学界划时代的密码学界划时代的丰碑丰碑http:/www.techcn.com.cn/index.php?doc-view-131925Enigma(转轮密码机转轮密码机)在密码学界里，绝对是划时代的丰碑。在密码学界里，绝对是划时代的丰碑。它所凝聚成的不是一座丰碑，而是两座：研究并制造出它所凝聚成的不是一座丰碑，而是两座：研究并制造出Enigma是一座，研究并破解是一座，研究并破解Enigma是另一座。只要稍微了是另一座。只要稍微了解一下解一下Enigma的历史，就会被其中闪耀的人类智慧之美所折的历史，就会被其中闪耀的人类智慧之美所折服；而如果要向这样辉煌的智慧敬献花环的话，主要应该献服；而如果要向这样辉煌的智慧敬献花环的话，主要应该献给三个人：首先是德国人亚瑟给三个人：首先是德国人亚瑟谢尔比乌斯谢尔比乌斯(ArthurScherbius)；其次是波兰人；其次是波兰人马里安马里安雷耶夫斯基雷耶夫斯基(MarianRejewski)；然后是英国人；然后是英国人阿兰阿兰图灵图灵(AlanTuring)。德国人发明了德国人发明了Enigma；波兰人初步破解了简单的；波兰人初步破解了简单的Enigma；而英国人彻底终结了最高难的而英国人彻底终结了最高难的Enigma。独家解密德军独家解密德军U艇密码机艇密码机1944年年6月月4日，美国海军瓜达卡纳尔号航空母舰和日，美国海军瓜达卡纳尔号航空母舰和5艘驱逐舰组成的艘驱逐舰组成的编队，在非洲加那利群岛附近海域对德国海军编队，在非洲加那利群岛附近海域对德国海军U-505潜艇展开围捕，潜艇展开围捕，并缴获了纳粹德国专门用于并缴获了纳粹德国专门用于U艇通讯联系的绝密的密码机恩尼格玛和艇通讯联系的绝密的密码机恩尼格玛和密码本。从此，德军的密码本。从此，德军的U型潜艇完全暴露在盟军的反潜打击之下，德型潜艇完全暴露在盟军的反潜打击之下，德国海军的国海军的“狼群狼群”作战遭到彻底失败，并由此改变了整个第二次世界作战遭到彻底失败，并由此改变了整个第二次世界大战的结局。那部对二次大战进程产生过重要影响的德国海军密码机大战的结局。那部对二次大战进程产生过重要影响的德国海军密码机现在存放于美国中央情报局的档案馆。现在存放于美国中央情报局的档案馆。恩尼格玛密码机（德语：恩尼格玛密码机（德语：Enigma，又译哑谜机，或谜）是一种用于加，又译哑谜机，或谜）是一种用于加密与解密文件的密码机。确切地说，恩尼格玛是一系列相似的转子机密与解密文件的密码机。确切地说，恩尼格玛是一系列相似的转子机械的统称，包括了一系列不同的型号。械的统称，包括了一系列不同的型号。1918年德国发明家亚瑟年德国发明家亚瑟谢尔比乌斯（谢尔比乌斯（ArthurScherbius）和理查德）和理查德里特里特Ritter）创办了一家新技术应用公司，利用现代化的电气技术，）创办了一家新技术应用公司，利用现代化的电气技术，来取代手工编码加密方法，发明了一种能够自动编码的机器。谢尔来取代手工编码加密方法，发明了一种能够自动编码的机器。谢尔比乌斯给自己所发明的电气编码机械取名比乌斯给自己所发明的电气编码机械取名“恩尼格玛恩尼格玛”（ENIGMA，意为哑谜），可以将其简单分为三个部分：键盘、转子和显示器。意为哑谜），可以将其简单分为三个部分：键盘、转子和显示器。亚瑟亚瑟谢尔比乌斯和谢尔比乌斯和EnigmaBletchley Park Mansion and Enigma亚瑟亚瑟谢尔比乌斯和谢尔比乌斯和Enigma转轮机有一个键盘和一系列转轮，它是转轮机有一个键盘和一系列转轮，它是Vigenere密码的一种实现。密码的一种实现。每个转轮是字母的任意组合，有每个转轮是字母的任意组合，有26个位置，并且完成一种简单代替。个位置，并且完成一种简单代替。例如：一个转轮可能被用线连起来以完成用例如：一个转轮可能被用线连起来以完成用“F”代替代替“A”，用，用“U”代替代替“B”，用，用“L”代替代替“C”等等，而转轮的输出栓连接到等等，而转轮的输出栓连接到相邻的下一转轮的输入栓。相邻的下一转轮的输入栓。例如，在例如，在4个转轮的密码机中，第一个转轮可能用个转轮的密码机中，第一个转轮可能用“F”代替代替“A”，第二个转轮可能用第二个转轮可能用“Y”代替代替“F”，第三个转轮可能用第三个转轮可能用“E”代替代替“Y”，第四个转轮可能用第四个转轮可能用“C”代替代替“E”，“C”应该是输出密文。应该是输出密文。那么当转轮移动后，下一次代替将不同了。那么当转轮移动后，下一次代替将不同了。为使机器更安全，可把几种转轮和移动的齿轮结合起来。因为所有为使机器更安全，可把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，转轮以不同的速度移动，n个转轮的机器的周期是个转轮的机器的周期是26n。为进一步阻。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。止密码分析，有些转轮机在每个转轮上还有不同的位置号。恩尼格玛有三个转轮，从五个转轮中选择。转轮机中有一块稍微改恩尼格玛有三个转轮，从五个转轮中选择。转轮机中有一块稍微改变明文序列的插板，有一个反射轮导致每个转轮对每一个明文字母变明文序列的插板，有一个反射轮导致每个转轮对每一个明文字母操作两次。操作两次。Enigma的使用的使用使用恩尼格玛通讯时，发信人首先要调节三个转子的方向，使用恩尼格玛通讯时，发信人首先要调节三个转子的方向，而这个转子的初始方向就是密钥，是收发双方必须预先约定而这个转子的初始方向就是密钥，是收发双方必须预先约定好的，然后依次键入明文，并把显示器上灯泡闪亮的字母依好的，然后依次键入明文，并把显示器上灯泡闪亮的字母依次记下来，最后把记录下的闪亮字母按照顺序用正常的电报次记下来，最后把记录下的闪亮字母按照顺序用正常的电报方式发送出去。方式发送出去。收信方收到电文后，只要也使用一台恩尼格玛，按照原来的收信方收到电文后，只要也使用一台恩尼格玛，按照原来的约定，把转子的方向调整到和发信方相同的初始方向上，然约定，把转子的方向调整到和发信方相同的初始方向上，然后依次键入收到的密文，显示器上自动闪亮的字母就是明文后依次键入收到的密文，显示器上自动闪亮的字母就是明文了。加密和解密的过程完全一样，这就是反射器的作用，同了。加密和解密的过程完全一样，这就是反射器的作用，同时反射器的一个副作用就是一个字母永远也不会被加密成它时反射器的一个副作用就是一个字母永远也不会被加密成它自己，因为反射器中一个字母总是被连接到另一个不同的字自己，因为反射器中一个字母总是被连接到另一个不同的字母。母。Enigma的破解的破解恩尼格玛加密的关键就在于转子的初始方向。当然如果敌人收恩尼格玛加密的关键就在于转子的初始方向。当然如果敌人收到了完整的密文，还是可以通过不断试验转动转子方向来找到到了完整的密文，还是可以通过不断试验转动转子方向来找到这个密匙，特别是如果破译者同时使用许多台机器同时进行这这个密匙，特别是如果破译者同时使用许多台机器同时进行这项工作，那么所需要的时间就会大大缩短。对付这样暴力破译项工作，那么所需要的时间就会大大缩短。对付这样暴力破译法法(即一个一个尝试所有可能性的方法即一个一个尝试所有可能性的方法)，可以通过增加转子的，可以通过增加转子的数量来对付，因为只要每增加一个转子，就能使试验的数量乘数量来对付，因为只要每增加一个转子，就能使试验的数量乘上上26倍！倍！由于增加转子就会增加机器的体积和成本，恩尼格玛密码机的由于增加转子就会增加机器的体积和成本，恩尼格玛密码机的三个转子是可以拆卸下来并互相交换位置，这样一来初始方向三个转子是可以拆卸下来并互相交换位置，这样一来初始方向的可能性一下就增加了六倍。假设三个转子的编号为的可能性一下就增加了六倍。假设三个转子的编号为1、2、3，那么它们可以被放成那么它们可以被放成123-132-213-231-312-321这六种不同位置，这六种不同位置，当然这时收发密文的双方除了要约定转子自身的初始方向，还当然这时收发密文的双方除了要约定转子自身的初始方向，还要约好这六种排列中的一种。要约好这六种排列中的一种。Enigma的破解的破解除了转子方向和排列位置，恩尼格玛还有一道保障安全的关卡，除了转子方向和排列位置，恩尼格玛还有一道保障安全的关卡，在键盘和第一个转子之间有块连接板。通过这块连接板可以用一在键盘和第一个转子之间有块连接板。通过这块连接板可以用一根连线把某个字母和另一个字母连接起来，这样这个字母的信号根连线把某个字母和另一个字母连接起来，这样这个字母的信号在进入转子之前就会转变为另一个字母的信号。这种连线最多可在进入转子之前就会转变为另一个字母的信号。这种连线最多可以有六根，后期的恩尼格玛甚至达到十根连线，这样就可以使以有六根，后期的恩尼格玛甚至达到十根连线，这样就可以使6对对字母的信号两两互换，其他没有插上连线的字母则保持不变。当字母的信号两两互换，其他没有插上连线的字母则保持不变。当然连接板上的连线状况也是收发双方预先约定好的。然连接板上的连线状况也是收发双方预先约定好的。转子的初始方向、转子之间的相互位置以及连接板的连线状况组转子的初始方向、转子之间的相互位置以及连接板的连线状况组成了恩尼格玛三道牢不可破的保密防线，其中连接板是一个简单成了恩尼格玛三道牢不可破的保密防线，其中连接板是一个简单替换密码系统，而不停转动的转子，虽然数量不多，但却是点睛替换密码系统，而不停转动的转子，虽然数量不多，但却是点睛之笔，使整个系统变成了复式替换系统。连接板虽然只是简单替之笔，使整个系统变成了复式替换系统。连接板虽然只是简单替换却能使可能性数目大大增加，在转子的复式作用下进一步加强换却能使可能性数目大大增加，在转子的复式作用下进一步加强了保密性。了保密性。Enigma的破解的破解让我们来算一算经过这样处理，要想通过让我们来算一算经过这样处理，要想通过“暴力破译法暴力破译法”还还原明文，需要试验多少种可能性：原明文，需要试验多少种可能性：三个转子不同的方向组成了26262617576种可能性；三个转子间不同的相对位置为6种可能性；连接板上两两交换6对字母的可能性则是异常庞大，有100391791500种；于是一共有175766100391791500，其结果大约为10,000,000,000,000,000！即一亿亿种可能性！这样庞大的可能性，即便能动员大量的人力物力，要想靠这样庞大的可能性，即便能动员大量的人力物力，要想靠“暴力破译法暴力破译法”来逐一试验可能性，几乎是不可能的。而收发来逐一试验可能性，几乎是不可能的。而收发双方，则只要按照约定的转子方向、位置和连接板连线状况，双方，则只要按照约定的转子方向、位置和连接板连线状况，就可以非常轻松简单地进行通讯了。这就是就可以非常轻松简单地进行通讯了。这就是“恩尼格玛恩尼格玛”密密码机的保密原理。码机的保密原理。现代常规加密技术现代常规加密技术DES(DataEncryptionStandard)TripleDESIDEABlowfishRC5CAST-128DES的产生的产生-i1973年年5月月15日日,NBS开始公开征集标准加密算法开始公开征集标准加密算法,并公并公布了它的设计要求布了它的设计要求:(1)算法必须提供高度的安全性算法必须提供高度的安全性(2)算法必须有详细的说明算法必须有详细的说明,并易于理解并易于理解(3)算法的安全性取决于密钥算法的安全性取决于密钥,不依赖于算法不依赖于算法(4)算法适用于所有用户算法适用于所有用户(5)算法适用于不同应用场合算法适用于不同应用场合(6)算法必须高效、经济算法必须高效、经济(7)算法必须能被证实有效算法必须能被证实有效(8)算法必须是可出口的算法必须是可出口的DES的产生的产生-ii1974年年8月月27日日,NBS开始第二次征集开始第二次征集,IBM提交提交了算法了算法LUCIFER，该，该算法由算法由IBM的工程师在的工程师在19711972年研制年研制1975年年3月月17日日,NBS公开了全部细节公开了全部细节1976年年,NBS指派了两个小组进行评价指派了两个小组进行评价1976年年11月月23日，采纳为联邦标准，批准用于日，采纳为联邦标准，批准用于非军事场合的各种政府机构非军事场合的各种政府机构1977年年1月月15日日,“数据加密标准数据加密标准”FIPSPUB46发布发布DES的应用的应用1979年，美国银行协会批准使用年，美国银行协会批准使用1980年，美国国家标准局（年，美国国家标准局（ANSI）赞同赞同DES作为私人作为私人使用的标准使用的标准,称之为称之为DEA（ANSIX.392）1983年，国际化标准组织年，国际化标准组织ISO赞同赞同DES作为国际标准，作为国际标准，称之为称之为DEA-1该标准规定每五年审查一次，计划十年后采用新标准该标准规定每五年审查一次，计划十年后采用新标准最近的一次评估是在最近的一次评估是在1994年年1月，已决定月，已决定1998年年12月以月以后，后，DES将不再作为联邦加密标准。将不再作为联邦加密标准。分组密码的一般设计原理分组密码的一般设计原理分组密码是将明文消息编码表示后的数字（简分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为称明文数字）序列，划分成长度为n的组（可的组（可看成长度为看成长度为n的矢量），每组分别在密钥的控的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）制下变换成等长的输出数字（简称密文数字）序列，序列，两个基本设计方法两个基本设计方法Shannon称之为理想密码系统中，密文的所有称之为理想密码系统中，密文的所有统计特性都与所使用的密钥独立统计特性都与所使用的密钥独立扩散（扩散（Diffusion):明文的统计结构被扩散消失明文的统计结构被扩散消失到密文的长程统计特性到密文的长程统计特性,使得明文和密文之间使得明文和密文之间的统计关系尽量复杂的统计关系尽量复杂混乱混乱(confusion)：使得密文的统计特性与密使得密文的统计特性与密钥的取值之间的关系尽量复杂钥的取值之间的关系尽量复杂实现的设计原则实现的设计原则软件件实现的的要要求求：使使用用子子块和和简单的的运运算算。密密码运运算算在在子子块上上进行行，要要求求子子块的的长度度能能自自然然地地适适应软件件编程程，如如8、16、32比比特特等等。应尽尽量量避避免免按按比比特特置置换，在在子子块上上所所进行行的的密密码运运算算尽尽量量采采用用易易于于软件件实现的的运运算算。最最好好是是用用处理理器器的的基基本本运运算算，如如加加法法、乘乘法法、移移位等。位等。硬硬件件实现的的要要求求：加加密密和和解解密密的的相相似似性性，即即加加密密和和解解密密过程程的的不不同同应仅仅在在密密钥使使用用方方式式上上，以以便便采采用用同同样的的器器件件来来实现加加密密和和解解密密，以以节省省费用用和和体体积。尽尽量量采采用用标准准的的组件件结构构，以以便便能能适适应于于在在超超大大规模模集集成成电路中路中实现。简化的简化的DESSimplifiedDES方案，简称方案，简称S-DES方案。方案。加密算法涉及五个函数：加密算法涉及五个函数：(1)初始置换初始置换IP(initialpermutation)(2)复合函数复合函数fk1，它是由密钥它是由密钥K确定的，具有置确定的，具有置换和替代的运算。换和替代的运算。(3)转换函数转换函数SW(4)复合函数复合函数fk2(5)初始置换初始置换IP的逆置换的逆置换IP-1加密算法的数学表示加密算法的数学表示IP-1*fk2*SW*fk1*IP也可写为也可写为密文密文=IP-1（fk2(SW(fk1(IP(明文明文)其中其中K1=P8(移位移位(P10(密钥密钥K)K2=P8(移位移位(移位移位(P10(密钥密钥K)解密算法的数学表示：解密算法的数学表示：明文明文=IP-1（fk1(SW(fk2(IP(密文密文)对对S-DES的深入描述的深入描述（1）S-DES的密钥生成：的密钥生成：设设10bit的密钥为（的密钥为（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)置换置换P10是这样定义的是这样定义的P10(k1,k2,k10)=(k3,k4,k2,k7,k4,k10,k1,k9,k8,k6)相当于相当于P10=LS-1为循环左移，在这里实现左移为循环左移，在这里实现左移2位位P8=按照上述条件按照上述条件,若若K选为选为(1010000010),产生的两个子产生的两个子密钥分别为密钥分别为K1=(10100100),K2=(01000011) S-DES的密钥生成10-bit密钥密钥P10LS-1LS-1LS-2LS-2P8P8K18K255585(2)S-DES的加密运算的加密运算:初始置换用初始置换用IP函数函数:IP=1234567826314857末端算法的置换为末端算法的置换为IP的逆置换的逆置换:IP-1=1234567841357286易见易见IP-1(IP(X)=X函数函数fk，是加是加密方案中的最重要部分，它可表示为：密方案中的最重要部分，它可表示为：fk(L,R)=(L F(R,SK),R)其其中中L，R为为8位位输输入入,左左右右各各为为4位位,F为为从从4位位集集到到4位位集的一个映射集的一个映射,并不要求是并不要求是1-1的。的。SK为子密钥。为子密钥。对对映射映射F来说：来说：首首先先输输入入是是一一个个4-位位数数（n1,n2,n3,n4），第第一一步步运运算算是是扩张扩张/置换（置换（E/P）运算：运算：E/P41232341事实上，它的直观表现形式为：事实上，它的直观表现形式为：n4n1n2n3n2n3n4n18-bit子子密密钥钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然然后与后与E/P的结果作异或运算得：的结果作异或运算得：n4+k11n1+k12n2+k13n3+k14n2+k15n3+k16n4+k17n1+k18把它们重记为把它们重记为8位位：P0,0P0,1P0,2P0,3P1,0P1,1P1,2P1,3上上述述第第一一行行输输入入进进S-盒盒S0，产产生生2-位位的的输输出出；第第二二行行的的4位位输输入入进进S盒盒S1，产产生生2-位位的的输输出出。两两个个S盒盒按按如下定义：如下定义：S盒按下述规则运算：盒按下述规则运算：将将第第1和和第第4的的输输入入比比特特做做为为2-bit数数，指指示示为为S盒盒的的一一个个行行；将将第第2和和第第3的的输输入入比比特特做做为为S盒盒的的一一个个列列。如此确定为如此确定为S盒矩阵的（盒矩阵的（i,j）数。数。例如：（例如：（P0,0,P0,3）=(00),并且并且(P0,1,P0,2)=(10)确确定定了了S0中中的的第第0行行2列列（0，2）的的系系数数为为3，记记为为（11）输出。）输出。由由S0,S1输出输出4-bit经置换经置换P4243 1它的输出就是它的输出就是F函数的输出。函数的输出。Feistel结构图结构图Feistel结构定义结构定义加密加密:Li=Ri-1;Ri=Li-1 F(Ri-1,Ki)解密解密: :Ri-1=LiLi-1=Ri F(Ri-1,Ki)=Ri F(Li,Ki)Feistel结构分析结构分析Block size(64 128)Key size(56 128256)Number of rounds(16)Subkey generation Round function(F)Fast software encryption/decryptionEasy hardware implementationSimple structureEase of analysisDES示意图示意图DES的描述的描述DES利用利用56比特串长度的密钥比特串长度的密钥K来加密长度为来加密长度为64位的明位的明文，得到长度为文，得到长度为64位的密文位的密文输入输入64比特明文数据比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出64比特密文数据比特密文数据DES算法框图算法框图交换左右交换左右32比特比特 DES加解密过程加解密过程令令i表表示示迭迭代代次次数数， 表表示示逐逐位位模模2求求和和，f为为加加密密函数。函数。DES的加密和解密过程表示如下。的加密和解密过程表示如下。加密过程：加密过程：解密过程：解密过程：初始置换初始置换IP和初始逆置换和初始逆置换IP1Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的一轮迭代的一轮迭代DES: Function FExpansion:3248S-box:64Permutation:选择扩展运算选择扩展运算32 | 01 02 03 04 | 0504 | 05 06 07 08 | 0908 | 09 10 11 12 | 1312 | 13 14 15 16 | 1716 | 17 18 19 20 | 2120 | 21 22 23 24 | 2524 | 25 26 27 28 | 2928 | 29 30 31 32 | 01选择压缩运算选择压缩运算S-Box-iS-Box-iiS-Box对每个盒，对每个盒，6比特输入中的第比特输入中的第1和第和第6比特组成比特组成的二进制数确定的行，中间的二进制数确定的行，中间4位二进制数用来位二进制数用来确定的列。中相应行、列位置的十进制数的确定的列。中相应行、列位置的十进制数的4位二进制数表示作为输出。例如的输入为位二进制数表示作为输出。例如的输入为101001，则行数和列数的二进制表示分别是，则行数和列数的二进制表示分别是11和和0100，即第，即第3行和第行和第4列，的第列，的第3行和第行和第4列的列的十进制数为十进制数为3，用，用4位二进制数表示为位二进制数表示为0011，所，所以的输出为以的输出为0011。Permutation16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 25子密钥的产生子密钥的产生置换选择置换选择1（PC-1）和置换选择和置换选择2（PC-2）对对DES的讨论的讨论F F函数函数( (S-Box)S-Box)设计原理未知设计原理未知密钥长度的争论密钥长度的争论DESDES的的破译破译 弱密钥与半弱密钥弱密钥与半弱密钥S-Box问题问题1976年美国年美国NSA提出了下列几条提出了下列几条S盒的设计准则：盒的设计准则：1.S盒的每一行是整数盒的每一行是整数0，15的一个置换的一个置换2.没有一个没有一个S盒是它输入变量的线性函数盒是它输入变量的线性函数3.改变改变S盒的一个输入位至少要引起两位的输出改变盒的一个输入位至少要引起两位的输出改变4.对任何一个对任何一个S盒和任何一个输入盒和任何一个输入X，S（X）和和S(X 001100）至少有两个比特不同（这里至少有两个比特不同（这里X是长度为是长度为6的比特串）的比特串）5.对任何一个对任何一个S盒，对任何一个输入对盒，对任何一个输入对e,f属于属于0,1,S(X)S(X 11ef00)6.对任何一个对任何一个S盒，如果固定一个输入比特，来看一个盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为固定输出比特的值，这个输出比特为0的输入数目将接的输入数目将接近于这个输出比特为近于这个输出比特为1的输入数目的输入数目。密钥密钥长度长度关于关于DES算法的另一个最有争议的问题就是担算法的另一个最有争议的问题就是担心实际心实际56比特的密钥长度不足以抵御穷举式攻比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有击，因为密钥量只有 个个早在早在1977年，年，Diffie和和Hellman已建议制造一个已建议制造一个每秒能测试每秒能测试100100万个密钥的万个密钥的VLSI芯片。每秒测芯片。每秒测试试100100万个密钥的机器大约需要一天就可以搜万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大索整个密钥空间。他们估计制造这样的机器大约需要约需要2000万万美元。美元。在在CRYPTO93上，上，Session和和Wiener给出了一个非常详给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以算的密钥搜索芯片，所以16次加密能同时完成。此芯次加密能同时完成。此芯片每秒能测试片每秒能测试50005000万个密钥，用万个密钥，用5760个芯片组成的系个芯片组成的系统需要花费统需要花费10万万美元，它平均用美元，它平均用1.5天左右就可找到天左右就可找到DES密钥。密钥。1997年年1月月28日，美国的日，美国的RSA数据安全公司在数据安全公司在RSA安全安全年会上公布了一项年会上公布了一项“秘密密钥挑战秘密密钥挑战”竞赛，其中包括竞赛，其中包括悬赏悬赏1万美元破译密钥长度为万美元破译密钥长度为56比特的比特的DES。美国克罗美国克罗拉多洲的程序员拉多洲的程序员Verser从从1997年年2 2月月18日起，用了日起，用了96天天时间，在时间，在Internet上数万名志愿者的协同工作下，成功上数万名志愿者的协同工作下，成功地找到了地找到了DES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1万美元。万美元。1998年年7月月电子子前前沿沿基基金金会会（EFF）使使用用一一台台25万万美美圆的的电脑在在56小小时内内破破译了了56比比特特密密钥的的DES。1999年年1月月RSA数数据据安安全全会会议期期间，电子子前前沿沿基基金金会会用用22小小时15分分钟就就宣宣告告破破解解了了一一个个DES的密的密钥。DES的破译的破译1990年，以色列密码学家年，以色列密码学家EliBiham和和AdiShamir提出了差分密码分析法，可对提出了差分密码分析法，可对DES进行进行选择明文攻击。选择明文攻击。线性密码分析比差分密码分析更有效线性密码分析比差分密码分析更有效弱密钥与半弱密钥弱密钥与半弱密钥弱密钥弱密钥: E: EK K E EK K = I = I，DESDES存在存在4 4个弱密钥个弱密钥半弱密钥半弱密钥: E: EK1K1 = E = EK2K2，至少有至少有1212个半弱密钥个半弱密钥ReferenceWilliamStallings,Cryptographyandnetworksecurity:principlesandpractice,SecondEdition.BruceShneier,Appliedcryptography:protocols,algorithms,andsourcecodeinC,SecondEdition.ThomasH.Barr,InvitationtoCryptology,PrenticeHall,2002李克洪李克洪主编主编,实用密码学与计算机安全实用密码学与计算机安全,东北大学出东北大学出版社版社,1997,10王育民王育民刘建伟编著刘建伟编著,通信网的安全通信网的安全-理论与技术理论与技术,2000,5http:/williamstallings.com/Security2e.html破译实例破译实例1.珍珠港事件珍珠港事件1941.12.77:30AM查报告，证明查报告，证明“特种情报单位特种情报单位”有功，并拍有有功，并拍有魔术的一天魔术的一天，描写日，描写日攻击珍珠港前攻击珍珠港前24小时的海军情报部门的工作。小时的海军情报部门的工作。1941.12.7早上早上1点点28分，西雅图布里奇岛海军情报站截获日本给驻美大使分，西雅图布里奇岛海军情报站截获日本给驻美大使密报，密报，9分钟后海军部大楼分钟后海军部大楼1649室收到转发报（室收到转发报（OP-20-GY）.上午上午5点已点已脱密成日文：脱密成日文：“请贵大使在当地时间请贵大使在当地时间7日下午日下午1时（即时（即HAWAII早上早上7：30）将我国答复美国政府（）将我国答复美国政府（18小时前由东京分小时前由东京分14部份发出来的最后断交部份发出来的最后断交照会）。照会）。9：30分交海军作战部斯塔克上将和诺克斯海军部长。克雷默将分交海军作战部斯塔克上将和诺克斯海军部长。克雷默将译报向国务院走时（日大使馆的译电员在一小时后才将电报脱密），译报向国务院走时（日大使馆的译电员在一小时后才将电报脱密），9：15到达白宫，罗斯福用到达白宫，罗斯福用10分钟看完分钟看完13部电报说，这意味着战争。部电报说，这意味着战争。10：30左右，克来默回到办公室看到第左右，克来默回到办公室看到第14部电报译稿。部电报译稿。1111110：45将此电报逢将此电报逢到白宫，马歇尔仔细看了此报，想向太平洋地区发出警告，经过加密，到白宫，马歇尔仔细看了此报，想向太平洋地区发出警告，经过加密，46分钟后到达檀香山美国无线电公司（当地上午分钟后到达檀香山美国无线电公司（当地上午7:33分）。分）。7：55分日机分日机开始轰炸。日大侠下午开始轰炸。日大侠下午2:20才走进白宫提交照会。才走进白宫提交照会。11：45分最后一批日分最后一批日机才离开珍珠港。机才离开珍珠港。2.中途岛海战（代号中途岛海战（代号AF）日本）日本出动出动200多艘舰船多艘舰船JOSEPHJOHMROCHFORT中校中校1941年到年到HAWAII14海军区无海军区无线电分队领导工作。线电分队领导工作。1942年春成功破译日海军年春成功破译日海军JN25B密本，得知密本，得知日要进攻中途岛。舰队总司令尼米凉兹上将建议授日要进攻中途岛。舰队总司令尼米凉兹上将建议授“卓越服务奖卓越服务奖章章”。遭海军部反对，直到。遭海军部反对，直到1976年年ROCHEFORT逝世后，逝世后，1985年年海军部长海军部长JOHNLEHMAN才发布命令，由总统授奖章给他女儿。才发布命令，由总统授奖章给他女儿。日本由于准备不及原定日本由于准备不及原定4月月1日更换密码为日更换密码为JN25C,但一直到但一直到5月月1日日才启用，而使美军大量破译了秘密情报）。精确推出将于才启用，而使美军大量破译了秘密情报）。精确推出将于6月月3日日开始攻击中途岛。由于情报准确，开始攻击中途岛。由于情报准确，1942.5.7美机炸沉日本航空母舰美机炸沉日本航空母舰祥风祥风，另一艘的飞行甲板被炸弯，而使多架飞机投入大海中。，另一艘的飞行甲板被炸弯，而使多架飞机投入大海中。中途岛作战日本的中途岛作战日本的“赤城赤城”：“加贺加贺”“苍龙苍龙”“飞龙飞龙”号航空号航空母舰被击沉，从而使日本丧失了进行海战的能力。尼米兹上将认母舰被击沉，从而使日本丧失了进行海战的能力。尼米兹上将认为，中途岛海战本质上是情报的胜利。为，中途岛海战本质上是情报的胜利。3.冲绳战役和冲绳战役和4山本之死山本之死冲绳战役中密码分析者破译了冲绳战役中密码分析者破译了72000吨吨“大和大和“号超级号超级战列舰决死出击令，及其位置，舰载机群于战列舰决死出击令，及其位置，舰载机群于1945.4.7日日12时时32分将其击中，经过二小时反复轰炸沉入海底。分将其击中，经过二小时反复轰炸沉入海底。船上船上2767人全部战死。人全部战死。山本五十六于山本五十六于1943年年4月月13日下午日下午5时时55分到所罗门岛分到所罗门岛视察的日程报给第一基地部队等，被美军截获并通过视察的日程报给第一基地部队等，被美军截获并通过破译破译JN25密码的密码的IMB设备破译出。尼米兹上将决定出设备破译出。尼米兹上将决定出击。击。4月月13日日7时时25分出动分出动18架战斗机将山本座机击落。架战斗机将山本座机击落。5月月21日日本广播才广播这一消息。日日本广播才广播这一消息。5.日本商船的毁灭日本商船的毁灭二次大战中，美国密码分析人员破译二次大战中，美国密码分析人员破译75种日本种日本海军密码。美国击沉日本商船总吨位的海军密码。美国击沉日本商船总吨位的2/3.美美潜艇用鱼雷击沉日本油船潜艇用鱼雷击沉日本油船110艘，日本商船的艘，日本商船的毁灭是东条列举战败的三个原因之一（其他两毁灭是东条列举战败的三个原因之一（其他两个是越岛战略和快速航空母舰作战）个是越岛战略和快速航空母舰作战）6.德国潜艇指挥部密码的破译德国潜艇指挥部密码的破译德国潜艇指挥部德尼茨的德国潜艇指挥部德尼茨的B机关泄露了太多的机关泄露了太多的军事情况。军事情况。1944.6.4德德U-505潜艇受到美海潜艇受到美海军军22.3特遣大队反潜深水炸弹攻击，受伤浮起特遣大队反潜深水炸弹攻击，受伤浮起后美军冲入无线电室，缴获了密码机和大量明、后美军冲入无线电室，缴获了密码机和大量明、密报，并秘密将密报，并秘密将U-505拖回美国，德军误拖回美国，德军误认为沉没海底而未换密码，欧战结束前认为沉没海底而未换密码，欧战结束前11个月，个月，几乎每天击沉一艘潜艇，共计击沉几乎每天击沉一艘潜艇，共计击沉300多艘。多艘。7瑞典人破译德国外交和军事密瑞典人破译德国外交和军事密码码1941年春，瑞典人破译德国外交和军事密码，年春，瑞典人破译德国外交和军事密码，分析出德军将于分析出德军将于6月月20-25日入侵苏联。日入侵苏联。潘汉年也从日将内部得到这一情报，并通过告潘汉年也从日将内部得到这一情报，并通过告知斯大林。知斯大林。信号截收和密码分析在战争中的作用极大，大信号截收和密码分析在战争中的作用极大，大大缩短了战争，二战缩短了大缩短了战争，二战缩短了8年。拯救了千千年。拯救了千千万万的生命。万万的生命。思考和练习思考和练习1.什么特性使得加密绝对不可攻破？什么特性将什么特性使得加密绝对不可攻破？什么特性将使得加密在实际应用中是不可攻破的？使得加密在实际应用中是不可攻破的？2.解释为什么双字母替换密码比单字母替换更安解释为什么双字母替换密码比单字母替换更安全？全？3.解释为什么两个相对简单的密码（如代替和换解释为什么两个相对简单的密码（如代替和换位）的积可将安全提高到较高层次。位）的积可将安全提高到较高层次。习题习题2.1