电子金融与支付第6章密码学基础.ppt

例子 大学生鼓起勇气写信给班上某位女同学请选择以下其中一样在其中打勾 爱情 友情女同学回送给他一首诗 愿君多谅知识浅 选题未答缴白卷爱莫能助实有愧 情愿送诗供君览 元宵夜十字街头看花灯万人空巷尽欢颜火树银花多变换急星流雨天上升 爱情密码游戏 小男孩与小女生正在玩 爱情密码游戏 相思苦 一往情深 无聊死了 我想死你了 我想亲亲你 你亲我就要爱我一辈子 我真的不理你了 有几只海豚 解答 7只海豚 Example2 Solution Example3 跳舞小人历险记 摘自福尔摩斯 SherlockHolmes theAdventureoftheDancingMen 住在英国的HiltonCubitt先生最近娶了美国Chicago的ElsiePatrickCubitt在花园发现一张画有跳舞的小人字条 Elsie一看 脸色大变 跳舞小人历险记 Cubitt寄给Holmes 并前往Holmes家说明所知的一切Holmes直觉认为这是一个信息 而非小孩子的涂鸦因提供的字条太少 Holmes请Cubitt有看到新的 再传给Holmes看 跳舞小人历险记 几日后 Cubitt又在工具室门上发现粉笔画的小人 并临摹下来寄给Holmes 跳舞小人历险记 接下来的几天 陆续在工具室发现小人图 Cubitt全寄给Holmes看 跳舞小人历险记 Holmes将全部小人字条研究数天后 发现大事不妙 立即赶往Cubitt家 欲阻挡悲剧发生抵达Cubitt家后 Cubitt已受枪伤身亡 Elsie也身受重伤 跳舞小人历险记 几番调查后 Holmes终将案情查清楚 便写下一纸条 派马童送至一间叫 Elriges 旅馆的AbeSlaney先生警察询问Holmes为何对案情这么了解 Holmes才开始说明如何破解小人纸条 跳舞小人历险记 Holmes分析所有的图 发现出现次数最多 便将此符号换成 E 因此图4能解读成 E E 可能为 LEVER 杠杆 NEVER 绝不 SEVER 分开 Holmes猜测是NEVER 因此大胆假设便是 ComeElsie 跳舞小人历险记 所以第一张字条可以解开成 M ERE ESL NE AM EREA ESL NE AMHEREABESLANEY 跳舞小人历险记 第二张字条亦可解读A ELRI ESATELRIGES 跳舞小人历险记 最后一张ELSIE RE ARETOMEETTHYGO ELSIEPREPARETOMEETTHYGOD 跳舞小人历险记 警察担心凶手跳跑 Holmes说 他等会儿就自己过来了 Holmes稍早早已写了字条请凶手过来COMEHEREATONCE 跳舞小人历险记 AbeSlaney到场即被逮捕 才道出他是Elsie在Chicago的未婚夫 Elsie发现Slaney和她父亲组帮派为非作歹 才逃出与Cubitt结婚 密码学基础 背景 在当前全球电子互联互通的时代 由于病毒 黑客 电子窃听和电子欺诈 使得安全性比任何时候都重要 计算机系统的大量使用和互联 使得我们越来越依赖于这些系统所存储和传输的信息 因此需要保护数据和资源不被泄露 保证数据和消息的真实性 保护系统不受基于网络的攻击 密码和网络安全学科已经成熟 可以开发方便实用的应用软件来加强网络安全 信息安全的含义 通信保密 COMSEC 60 70年代信息保密信息安全 INFOSEC 80 90年代机密性 完整性 可用性 不可否认性等信息保障 IA 90年代 基本的通讯模型通信的保密模型通信安全 60年代 COMSEC 发方 收方 信源编码信道编码信道传输通信协议 发方 收方 敌人 信源编码信道编码信道传输通信协议密码 信息安全的含义 80 90年代 信息安全的三个基本方面保密性Confidentiality即保证信息为授权者享用而不泄漏给未经授权者 完整性Integrity数据完整性 未被未授权篡改或者损坏系统完整性 系统未被非授权操纵 按既定的功能运行可用性Availability即保证信息和信息系统随时为授权者提供服务 而不要出现非授权者滥用却对授权者拒绝服务的情况 信息安全的其他方面信息的不可否认性Non repudiation 要求无论发送方还是接收方都不能抵赖所进行的传输鉴别Authentication鉴别就是确认实体是它所声明的 适用于用户 进程 系统 信息等审计Accountability确保实体的活动可被跟踪可靠性Reliability特定行为和结果的一致性 安全需求的多样性 保密性一致性可用性可靠性可认证 真实性 责任定位 审计性高性能实用性占有权 信息保障 美国人提出的概念 InformationAssurance保护 Protect 检测 Detect 反应 React 恢复 Restore 保护Protect 检测Detect 反应React 恢复Restore 密码从军事走向生活 电子邮件 自动提款机电话卡 IP卡 201电话卡银行取钱信用卡购物 密码 基本概念 密码学 Cryptology 是研究信息系统安全保密的科学 密码编码学 Cryptography 主要研究对信息进行编码 实现对信息的隐蔽 密码分析学 Cryptanalytics 主要研究加密消息的破译或消息的伪造 基本术语 消息被称为明文 Plaintext 用某种方法伪装消息以隐藏它的内容的过程称为加密 Encrtption 被加密的消息称为密文 Ciphertext 而把密文转变为明文的过程称为解密 Decryption 对明文进行加密操作的人员称作加密员或密码员 Cryptographer 密码算法 CryptographyAlgorithm 是用于加密和解密的数学函数 密码员对明文进行加密操作时所采用的一组规则称作加密算法 EncryptionAlgorithm 所传送消息的预定对象称为接收者 Receiver 接收者对密文解密所采用的一组规则称为解密算法 DecryptionAlgorithm 加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的 分别称为加密密钥 EncryptionKey 和解密密钥 DecryptionKey 密码学的目的 Alice和Bob两个人在不安全的信道上进行通信 而破译者Oscar不能理解他们通信的内容 加密通信的模型 Alice 加密机 解密机 Bob 安全信道 密钥源 Oscar x y x k 密码体制 密码体制 它是一个五元组 P C K E D 满足条件 1 P是可能明文的有限集 明文空间 2 C是可能密文的有限集 密文空间 3 K是一切可能密钥构成的有限集 密钥空间 4 任意k K 有一个加密算法和相应的解密算法 使得和分别为加密解密函数 满足dk ek x x 这里x P 密码算法分类 i 按照保密的内容分 受限制的 restricted 算法 算法的保密性基于保持算法的秘密 基于密钥 key based 的算法 算法的保密性基于对密钥的保密 密码算法分类 ii 基于密钥的算法 按照密钥的特点分类 对称密码算法 symmetriccipher 又称传统密码算法 conventionalcipher 就是加密密钥和解密密钥相同 或实质上等同 即从一个易于推出另一个 又称秘密密钥算法或单密钥算法 非对称密钥算法 asymmetriccipher 加密密钥和解密密钥不相同 从一个很难推出另一个 又称公开密钥算法 public keycipher 公开密钥算法用一个密钥进行加密 而用另一个进行解密 其中的加密密钥可以公开 又称公开密钥 publickey 简称公钥 解密密钥必须保密 又称私人密钥 privatekey 私钥 简称私钥 密码算法分类 iii 按照明文的处理方法 分组密码 blockcipher 将明文分成固定长度的组 用同一密钥和算法对每一块加密 输出也是固定长度的密文 流密码 streamcipher 又称序列密码 序列密码每次加密一位或一字节的明文 也可以称为流密码 序列密码是手工和机械密码时代的主流 密码算法分类 iv 对称密钥密码又可分为 分组密码每次对一块数据加密多数网络加密应用DES IDEA RC6 Rijndael流密码每次对一位或一字节加密手机One timepadding Vigen re Vernam 密码算法分类 v 公开密钥密码 大部分是分组密码 只有概率密码体制属于流密码每次对一块数据加密数字签名 身份认证RSA ECC ElGamal加密解密速度慢 密码学的起源和发展 i 三个阶段 1949年之前密码学是一门艺术1949 1975年密码学成为科学1976年以后密码学的新方向 公钥密码学 密码学的起源 隐写术 steganography 通过隐藏消息的存在来保护消息 隐形墨水字符格式的变化图象图像 example i 象形文字的修改 ModifiedHieroglyphics c 1900B C 密码学的第一个例子是对标准书写符号的修改例如 古埃及法老坟墓上的文字思想 代替 substitution 埃及象形文字 公元前19世纪 埃及人将象形文字写在各处以联络族人 埃及象形文字 因此埃及象形文字乃是我们有知以来最早的加密系统 example ii SpartanScytale c 500B C 斯巴达人用于加解密的一种军事设备发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想 置换 permutation example iii Polybius Checkerboard 205 123B C 明文 POLYBIUS密文 3534315412244543 希腊人 发明一5x5方格加密 将字母转换成数字 先取得列号 再取得行号 课堂练习 TAIWAN Example iv CaesarCipher c 50B C ABCDEFG XYZDEFGHIJ ABC明文 Caesarcipherisashiftsubstitution密文 FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQ JuliusCaesar 100BC 44AD 罗马皇帝 发明 凯撒加密法 亦称 凯撒位移 课堂练习 PHHWPHDIWHUWKHWRJDSDUWB ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC明文 OMNIAGALLIAESTDIVISAINPARTESTRES 高卢全境可分为三个部分 密文 RPQLDJDOOLDHVWGLYLVDLQSDUWHVWUHV PlainTextandCipherText明文和密文 Fig2 4 Example V Nomenclator代码本c 1400字母 符号 单词 短语代码代码字母 符号 单词 短语应用 WorldWarII Monoalphabetic加密法 有别于Caesar加密法的全部位移k个位置改为单一字母个别位移固定的位置如aSbAcHdV 破解Monoalphabetic 密文UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ明文 利用统计方式 分析字母出现频率 破解Monoalphabetic 一般英文文章中 字元相对出现频率 破解Monoalphabetic UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZtaeeteathateeaaVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXettathaeeeaethzaEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQeeetatethet逐一测试解密 itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscowie在Chicago的未婚夫 Elsie发现Slaney和她父亲组帮派为非作歹 才逃出与Cubitt结婚 countrelativeletterfrequencies seetext guessP ZareeandtguessZWisthandhenceZWPistheproceedingwithtrialanderrorfinallyget 密码学的起源和发展 ii 1949年之前 古典密码 classicalcryptography 密码学还不是科学 而是艺术出现一些密码算法和加密设备密码算法的基本手段 substitution permutation 出现 针对的是字符简单的密码分析手段出现 密码学的起源和发展 iii 1949 1975年 计算机使得基于复杂计算的密码成为可能1949年Shannon的 TheCommunicationTheoryofSecretSystems 1967年DavidKahn的 TheCodebreakers 1971 73年IBMWatson实验室的HorstFeistel等的几篇技术报告 Smith J L TheDesignofLucifer ACryptographicDeviceforDataCommunication 1971 Smith J L AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem Aug 1972 Feistel H CryptographyandComputerPrivacy May1973数据的安全基于密钥而不是算法的保密 密码学的起源和发展 iv 1976年以后 1976年Diffie Hellman的 NewDirectionsinCryptography 提出了不对称密钥密码1977年Rivest Shamir Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法公钥密码使得发送端和接收端无密钥传输的保密通信成为可能 密码学的演变历史 1 1918 WilliamFriedman sTheIndexofCoincidenceanditsApplicationsinCryptographyWilliamFrederickFriedman September24 1891 November12 1969 美国陆军密码专家 1930年代 他领导了陆军的一个研究部门SignalsIntelligenceService SIS 其中一部分服务一直延续到五十年代 三十年代晚期 在他的指导下 FrankRowlett破解了日本人的PURPLE加密机 这样就截获了日本的大量外交和军事的秘密 密码学的演变历史 2 EdwardHebern RotorMachinefor50Years 1948 ClaudeShannon s TheCommunicationTheoryofSecrecySystem 成为现代密码学理论基础ClaudeElwoodShannon Apr 30 1916 Feb 24 2001 是美国的一个电气工程师和数学家 被誉为信息论之父 thefatherofinformationtheory 香农之有名在于他以1948年发表的那篇旷世论文而奠定了现代信息论基础 其实早在1937年当21岁的香农还是MIT一个硕士研究生时 他便在他的硕士论文中论述了布尔代数的电子实现和应用 可以构建和解决任何逻辑的和数字的关系 因此他奠定了数字计算机和数字电路设计理论的基础 他的硕士论文一直被认为是迄今最重要的硕士论文 1949 1967 CryptographicLiteraturewasbarren 密码学的演变历史 3 1971 IBM发明LucifferCipher 128位密钥作分组加密 这项发明是由HorstFeistel Jan 30 1915 Nov 14 1990 领导的 他是密码学家 当时在IBM负责设计加密器 他的工作最终激发了70年代DataEncryptionStandard DES 的研发高潮1976 1977 美国国家标准局正式公布实施DES1975 WhitfieldDiffieandMatinHellman ANewDirectioninCryptography 首次提出适应网络保密通信的公开密钥思想 揭开现代密码学研究的序幕 具有划时代的意义 密码学的演变历史 4 1977 1978 RonaldRivest AdiShamir LenAdleman第一次提出公开密钥密码系统的实现方法RSA1981 成立InternationalAssociationforCryptologyResearch1985 AbbasElGamal提出概率密码系统ElGamal方法1990 1992 LaiXuejiaandJames IDEA TheInternationalDataEncryptionAlgorithm2000 AES AdvancedEncryptionStandard Cryptology 保密学 源自希腊语 Greek Krypt s 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 密码学的起源和发展 v 1976年以后 对称密钥密码算法进一步发展1977年DES正式成为标准80年代出现 过渡性 的 postDES 算法 如IDEA RCx CAST等90年代对称密钥密码进一步成熟Rijndael RC6 MARS Twofish Serpent等出现2001年Rijndael成为DES的替代者 密码分析 假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥 这个假设称为Kerckhoff原则 最常见的破解类型如下 1 唯密文攻击 Oscar具有密文串y 2 已知明文攻击 Oscar具有明文串x和相应的密文y 3 选择明文攻击 Oscar可获得对加密机的暂时访问 因此他能选择明文串x并构造出相应的密文串y 4 选择密文攻击 Oscar可暂时接近密码机 可选择密文串y 并构造出相应的明文x 这一切的目的在于破译出密钥或密文 密码破译 密码破译的原则 遵循观察与经验方法 采用归纳与演绎步骤 分析 假设 推测和证实三大要素 语言的频率特征 e连接特征 q u Iex 重复特征 th tion tious 理论安全 或无条件安全TheoreticalSecure orPerfectSecure 攻击者无论截获多少密文 都无法得到足够的信息来唯一地决定明文 Shannon用理论证明 欲达理论安全 加密密钥长度必须大于等于明文长度 密钥只用一次 用完即丢 即一次一密 One timePad 不实用 实际安全 或计算上安全PracticalSecure orComputationallySecure 如果攻击者拥有无限资源 任何密码系统都是可以被破译的 但是 在有限的资源范围内 攻击者都不能通过系统的分析方法来破解系统 则称这个系统是计算上安全的或破译这个系统是计算上不可行 ComputationallyInfeasible 理论安全和实际安全 密码算法的安全性 无条件安全 Unconditionallysecure 无论破译者有多少密文 他也无法解出对应的明文 即使他解出了 他也无法验证结果的正确性 Onetimepad计算上安全 Computationallysecure 破译的代价超出信息本身的价值破译的时间超出了信息的有效期 穷举攻击 总是可以简单地尝试每一个可能的密钥穷举攻击是最基本的攻击 难度与密钥长度成正比平均来说要获得成功必须尝试所有可能密钥的一半 古典密码 基于字符的密码代替密码 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 q 其中s a q 表示小于a q的最大整数 定义r为amodq的剩余 记为r amodq 若整数a和b有 amodq bmodq 则称a与b在modq下同余 对于满足 r a a sq r s Z 的整数集称为同余类 模运算有下述性质 1 若n a b 则a bmodq 2 amodq bmodq 意味a bmodq 3 a bmodq等价于b amodq 4 若a bmodq且b cmodq 则a cmodq 模q算术 ii 模算术 ModularArithmatic 在modq的q个剩余类集 0 1 2 q 1 上可以定义加法和乘法运算如下 加法 amodq bmodq a b modq乘法 amodq bmodq a b modq 移位密码算法 设P C K Z 26 对k K 定义ek x x k mod26 y C同时dk y y k mod26 注1 26个英文字母与模26剩余类集合 0 25 建立一一对应 2 当k 3时 为Caesar密码abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC例子 cipher FLSKHU实际算法为 有同时有 d3 y y 3 mod26 移位密码分析 给定加密的消息 PHHWPHDIWHUWKHWRJDSDUWB由于 加解密算法已知 可能尝试的密钥只有 6个通过强力攻击得到明文 meetmeafterthetogaparty 移位密码很容易受到唯密文攻击 乘数密码算法 加密函数取形式为e x ax mod26 a Z 26 要求唯一解的充要条件是gcd a 26 1该算法描述为 设P C Z 26 K a Z 26 gcd a 26 1 对k a K 定义ek x ax mod26 和dk y a 1 y mod26 x y Z 26 例子 a 9 ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR明文密文cipher SUFLKX 乘数密码分析 对于乘数密码 当且仅当a与 互素时 加密变换才是一一映射的 因此a的选择有 种 a 3 5 7 9 11 15 17 19 21 23 25可能尝试的密钥只有1 个 仿射密码算法 i 加密函数取形式为e x ax b mod26 a b Z 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 y Z 26 q 26时 可能的密钥是26 12 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 4 1026 破译者穷举搜索是不行的 然而 可由统计的方式破译它 3 移位密码 乘数密码 仿射密码算法都是替换密码的特例 0123 2324250 1 2 3 23 24 25 单表替换密码的破译 通过字母的使用频率破译 对抗频率分析的办法 多名或同音代替密码多表代替密码多字母代替密码 多名代替密码 与简单代替密码类似 只是映射是一对多的 每个明文字母可以加密成多个密文字母 例如 A可能对应于5 13 25B可能对应于7 9 31 42当对字母的赋值个数与字母出现频率成比例时 这是因为密文符号的相关分布会近似于平的 可以挫败频率分析 然而 若明文字母的其它统计信息在密文中仍很明显时 那么同音代替密码仍然是可破译的 多表代替密码 多表代替密码 是以一系列 两个以上 代换表依此对明文消息的字母进行代换的方法 非周期多标代替密码 代换表是非周期的无限序列一次一密密码 onetimepadding 对每个明文每次采用不同的代换表 周期多表代替密码 代换表个数有限 重复使用 Vigen recipher 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 GOOGOCPKTPNTLKQZPKMF Vigen recipher 破译 依然保留了字符频率某些统计信息重码分析法 间距是密钥长度整数倍的相同子串有相同密文 反过来 密文中两个相同的子串对应的密文相同的可能性很大 abcdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202122232425密钥 cryptographycryptographycr明文 yourpackagereadyroomathree密文 AFSGIOIPGPG 滚动密钥密码 对于周期代换密码 当密钥的长度d和明文一样长时 就成为滚动密钥密码 Vigen re本人建议密钥与明文一样长 Vernam密码 1918年 GillbertVernam建议密钥与明文一样长并且没有统计关系的密钥内容 他采用的是二进制数据 加密 Ci Pi Ki解密Pi Ci Ki核心 构造和消息一样长的随机密钥 2 2 3Playfair密码 单表代换尽管有大量的密钥 也不能提供足够的安全性 因为密文中残留了大量的明文结构 一种解决办法是引进多表代换密码 Playfair密码是最著名的多表代换密码 它把明文中的双字母音节作为一个单元转换成密文的双字母音节 Playfair密码是由英国科学家CharlesWheatstone在1854年发明的 用了他的朋友BaronPlayfair的名字命名 Playfair算法基于一个由密钥词构成的5x5字母矩阵 Playfair密码的密钥矩阵 假定使用的密钥词是MONARCHY先在5x5矩阵中填上密钥词 去掉重复字母再将剩余的字母按字母表的顺序从左至右 从上至下填在矩阵剩下的格子中 I和J当作一个字母 Playfair密码的加密 对明文按如下规则一次加密两个字母如果该字母对的两个字母是相同的 则在其中插入一个填充字母 如 x balloon 加密成 balxloon 落在同一行的明文字母对中的字母由其右边的字母来代换 每行中最右的字母用该行最左边的第一个字母来代换 如 ar 加密成 RM 落在同一列的明文字母对中的字母由其下面的字母来代换 每列中最下面的一个字母用该列最上面的第一个字母来代换 如 mu 加密成 CM 其他的每组明文字母对中的字母按如下方式代换 该字母所在行为密文所在行 另一字母所在列为密文所在列 如 hs 变换成 BP ea 代换为 IM 或 JM asdesired Playfair密码的安全性 安全性比单表代换大为提高因为有26个字母 因此有26x26 676字母对 对单个字母对进行判断要困难得多 单个字母的相对频率比字母对的相对频率在统计规律上要好 利用频率分析字母对就更困难些 需要676输入的频率表来进行分析 被广泛地使用了许多年 包括在一战和二战时期因为它的密文仍然完好地保留了明文语言的大部分结构特征 它仍然是相对容易攻破的 几百个字母的密文就足够分析出规律了 字母出现的相对频率 明文 曲线画出7万个字母的频率分布 对文中出现的每个字母计数 结果除以字母e的出现次数 加密后的曲线体现了加密后字母频率分布被掩盖的程度 如果完全被掩盖 则应该是一条水平线 多字母代替密码 Playfair Playfair 将明文中的双字母组合作为一个单元对待 并将这些单元转换为密文的双字母组合 5 5变换矩阵 I与J视为同一字符CIPHERABDFGKLMN cipher OQSTUVWXYZ加密规则 按成对字母加密相同对中的字母加分隔符 如x balloon balxloon同行取右边 he EC同列取下边 dm MT其他取交叉 kt MQOD TR Playfair举例 以前面的5 5变换矩阵 cipher 为例CIPHERABDFGKLMN cipher OQSTUVWXYZ 1 balloonbalxloondbspgsug 2 bookbooksrqg 3 fillfilxlxaespsp Playfair密码分析 Playfair有26X26 676种字母对组合字符出现几率一定程度上被均匀化基于字母频率的攻击比较困难依然保留了相当的结构信息 Hill密码 1929 基于矩阵的线性变换 K是一个m m矩阵 在Z 26 上可逆 即存在K 1使得 KK 1 I 在Z 26 对每一个k K 定义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 a Z 26 a 26 1 Z 26 1 3 5 7 9 11 15 17 19 21 23 25 Hill密码的例子 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 99 60 72 140 3 4 且 11 24 121 72 88 168 11 22 于是对july加密的结果为DELW Hill密码的例子 ii 为了解密 Bob计算且因此 得到了正确的明文 july Hill密码分析 完全隐藏了字符 对 的频率信息线性变换的安全性很脆弱 易被已知明文攻击击破 对于一个mxm的hill密码 假定有m个明文 密文对 明文和密文的长度都是m 可以把明文和密文对记为 Pj p1j p2j pmj 和Cj C1j C2j Cmj Cj KPj 1 j m定义mxm的方阵X Pij Y Cij 得到Y KX K YX 1例子 fridayPQCFKUK 517 1516 K 83 25 K 024 1020 因此 置换密码 换位密码把明文按列写入 按行读出密钥包含3方面信息 行宽 列高 读出顺序key 4312567plaintext attackpostponeduntiltwoamxyzciphertext TTNAAPTMTSUOAODWCOIXPETZ完全保留字符的统计信息使用多轮加密可提高安全性 2 2 5PolyalphabeticCiphers多表代换密码 改进简单的单表代换的方法是在明文消息中采用不同的单表代换 这就是多表代换密码poly alphabeticsubstitutionciphers因为需要猜测更多的字母表 并且频率分布特性也变得平坦了 所以使得密码破译更加困难使用一密钥词对每个明文字母选择一个字母表来加密依次使用每个字母表如果到了密钥词最后一个字母 则从头开始继续 Vigen re密码 最简单的多表代换密码是Vigen re密码 它其实是多重Caesar密码26个密码水平放置 最左边是密钥字母 顶部排列的是明文的标准字母表加密一条消息需要与消息一样长的密钥 密钥是密钥词的重复 比如 密钥词为K k1k2 kd加密 给定密钥字母x和明文字母y 密文字母是位于x行和y列的那个字母密钥词的第i字母 表明使用第i个字母表轮 流使用字母表 如果到了消息的第d个字母时则从头再做解密 密钥字母决定行 行里密文字母所在列的顶部字母就是明文字母 Example 写下明文在明文之上重复写下密钥像使用Caesarcipher密钥那样使用每一个密钥字母 加密每一个明文字母比如 使用密钥deceptivekey deceptivedeceptivedeceptiveplaintext wearediscoveredsaveyourselfciphertext ZICVTWQNGRZGVTWAVZHCQYGLMGJ 练习 MEETMEAFTERSCHOOL密钥 ESPIONAGE 答案 QWTBARALXIJHKVBOR Vigen re密码的安全性 每一个明文字母可以有多个密文字母对应 这样字母使用的频率特性减弱了 但是没有完全消失攻击者首先要分析密文是否是用单表代换加密的 即通过简单的测试密文的统计特性如果认为是用Vigen re密码加密的 破译能否取得进展将取决于能否判定密钥词的长度 要通过发现重复序列来判断如果密钥词长度是N 那么密码实际上包含了N个单表代换密钥词的周期性可以用与明文信息一样长的不重复密钥词来消除 如 密钥自动生成系统 但是密文和明文具有相同频率分布特性 仍然是易受攻击的最终措施是选择与明文毫无统计关系且和它一样长的密钥 KasiskiMethodtobreakVigen re卡西斯基方法破解Vigen re 破解Vigen re的方法是由CharlesBabbage 巴贝奇 和FriedrichKasiski 卡西斯基 分别发现的 密文中的重复性可以暗示出密钥词长度如果两个相同明文序列之间的距离是密钥词长度的整数倍 那么产生的密文序列也是相同的前例中 red 的两次出现相隔9个字母 因此得到了两个相同密文序列VTW这时攻击者就可以猜测密钥词的长度是3或者9这样攻击者可以像先前攻击单表密码那样分别进行攻击密钥词的周期性可以用与明文信息一样长的不重复密钥词来消除 AutokeyCipher AutokeyCipher 最理想的是让密钥和要加密的消息一样长Vigen re提出了autokeycipher 密钥词keyword放在消息前面作为密钥key前缀知道了密钥词能够破译密文的前面一些字母 据此可以解密密文消息的其余部分但是这种方法仍然具有字母使用的频率特性可供分析例如 给定密钥词 deceptivekey deceptivewearediscoveredsavplaintext wearediscoveredsaveyourselfciphertext ZICVTWQNGKZEIIGASXSTSLVVWLA 古典密码小结 Substitution permutation密码分析多轮加密数据安全基于算法的保密 Enigma 密码学界划时代的丰碑 独家解密德军U艇密码机 1944年6月4日 美国海军瓜达卡纳尔号航空母舰和5艘驱逐舰组成的编队 在非洲加那利群岛附近海域对德国海军U 505潜艇展开围捕 并缴获了纳粹德国专门用于U艇通讯联系的绝密的密码机恩尼格玛和密码本 从此 德军的U型潜艇完全暴露在盟军的反潜打击之下 德国海军的 狼群 作战遭到彻底失败 并由此改变了整个第二次世界大战的结局 那部对二次大战进程产生过重要影响的德国海军密码机现在存放于美国中央情报局的档案馆 恩尼格玛密码机 德语 Enigma 又译哑谜机 或谜 是一种用于加密与解密文件的密码机 确切地说 恩尼格玛是一系列相似的转子机械的统称 包括了一系列不同的型号 1918年德国发明家亚瑟 谢尔比乌斯 ArthurScherbius 和理查德 里特Ritter 创办了一家新技术应用公司 利用现代化的电气技术 来取代手工编码加密方法 发明了一种能够自动编码的机器 谢尔比乌斯给自己所发明的电气编码机械取名 恩尼格玛 ENIGMA 意为哑谜 可以将其简单分为三个部分 键盘 转子和显示器 亚瑟 谢尔比乌斯和Enigma BletchleyParkMansionandEnigma 亚瑟 谢尔比乌斯和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的破解 让我们来算一算经过这样处理 要想通过 暴力破译法 还原明文 需要试验多少种可能性 三个转子不同的方向组成了26 26 26 17576种可能性 三个转子间不同的相对位置为6种可能性 连接板上两两交换6对字母的可能性则是异常庞大 有100391791500种 于是一共有17576 6 100391791500 其结果大约为10 000 000 000 000 000 即一亿亿种可能性 这样庞大的可能性 即便能动员大量的人力物力 要想靠 暴力破译法 来逐一试验可能性 几乎是不可能的 而收发双方 则只要按照约定的转子方向 位置和连接板连线状况 就可以非常轻松简单地进行通讯了 这就是 恩尼格玛 密码机的保密原理 现代常规加密技术 DES DataEncryptionStandard TripleDESIDEABlowfishRC5CAST 128 DES的产生 i 1973年5月15日 NBS开始公开征集标准加密算法 并公布了它的设计要求 1 算法必须提供高度的安全性 2 算法必须有详细的说明 并易于理解 3 算法的安全性取决于密钥 不依赖于算法 4 算法适用于所有用户 5 算法适用于不同应用场合 6 算法必须高效 经济 7 算法必须能被证实有效 8 算法必须是可出口的 DES的产生 ii 1974年8月27日 NBS开始第二次征集 IBM提交了算法LUCIFER 该算法由IBM的工程师在1971 1972年研制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比特等 应尽量避免按比特置换 在子块上所进行的密码运算尽量采用易于软件实现的运算 最好是用处理器的基本运算 如加法 乘法 移位等 硬件实现的要求 加密和解密的相似性 即加密和解密过程的不同应仅仅在密钥使用方式上 以便采用同样的器件来实现加密和解密 以节省费用和体积 尽量采用标准的组件结构 以便能适应于在超大规模集成电路中实现 简化的DES SimplifiedDES方案 简称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密钥 P10 LS 1 LS 1 LS 2 LS 2 P8 P8 K1 8 K2 5 5 5 8 5 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事实上 它的直观表现形式为 n4n1n2n3n2n3n4n1 8 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经置换P42431它的输出就是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结构分