密码分析的艺术.pdf

1 目目录录 密码分析的艺术 3 一 什么是密码分析 3 二 密码分析的历史 3 一 第一阶段 古代 1949 年 3 二 第二阶段 1949 年 1975 年 6 三 第三阶段 1976 年至今 7 三 密码分析的方法 7 一 穷举法攻击 8 二 统计分析攻击 8 三 数学分析攻击 9 四 密码分析的案例 MD5 算法及其破解 10 一 关于 MD5 算法 10 1 MD5 算法简介 10 2 MD5 应用 11 3 MD5 算法原理 13 4 MD5 算法的优势 16 二 MD5 算法的破解 17 五 总结 18 2 密码分析的艺术密码分析的艺术 一 什么是密码分析一 什么是密码分析 密码学是保密学的一部分 保密学是研究密码系统或通信安全的科学 它包 含两个分支 即密码学 cryptology 和密码分析学 cryptanalytics 密码学是 对信息进行编码实现隐蔽信息的一门学问 而密码分析学是研究分析破译密码的 学问 两者相互对立而又相互促进 密码分析这个词有时也被用来指广义上的绕开某个密码学算法或密码协议 的尝试 而不仅仅是针对加密算法 但是 密码分析通常不包括并非主要针对密 码算法或协议的攻击 如贿赂 拷打 入室抢劫 键盘记录器 等等 尽管这些 攻击方式是计算机安全领域里的重要考虑因素 而且通常比传统的密码分析更加 有效 虽然密码分析的目标在密码学的历史上从古至今都一样 但是实际使用的方 法和技巧则随着密码学变得越来越复杂而日新月异 密码学算法和协议从古代只 利用纸笔等工具 发展到第二次世界大战时的恩尼格玛密码机 又称谜 德语 Enigma 直到目前的基于电子计算机的方案 而密码分析也随之改变了 无限 制地成功破解密码已经不再可能 事实上 只有很少的攻击是实际可行的 在上 个世纪 70 年代中期 公钥密码学作为一个新兴的密码学分支发展起来了 而用 来破解这些公钥系统的方法则和以住完全不同 通常需要解决精心构造出来的纯 数学问题 其中最著名的就是大数的质因子分解 二 密码分析的历史二 密码分析的历史 密码学有一个奇妙的发展历程 当然 密而不宣总是扮演主要角色 一般认 为密码学的发展可以划分为三个阶段 一 第一阶段 古代 一 第一阶段 古代 1949 1949 年年 这一时期可以看作是科学密码学的前夜时期 这阶段的密码技术可以说是一 种艺术 而不是一种科学 密码学专家常常是凭知觉和信念来进行密码设计和分 析 而不是推理和证明 早在古埃及就已经开始使用密码技术 但是用于军事目的 不公开 3 1844 年 萨米尔 莫尔斯发明了莫尔斯电码 用一系列的电子点划来进行电 报通讯 电报的出现第一次使远距离快速传递信息成为可能 事实上 它增强了 西方各国的通讯能力 20 世纪初 意大利物理学家奎里亚摩 马可尼发明了无线电报 让无线电波 成为新的通讯手段 它实现了远距离通讯的即时传输 马可尼的发明永远地改变 了密码世界 由于通过无线电波送出的每条信息不仅传给了己方 也传送给了敌 方 这就意味着必须给每条信息加密 随着第一次世界大战的爆发 对密码和解码人员的需求急剧上升 一场秘密 通讯的全球战役打响了 在第一次世界大战之初 隐文术与密码术同时在发挥着作用 在索姆河前线 德法交界处 尽管法军哨兵林立 对过往行人严加盘查 德军还是对协约国的驻 防情况了如指掌 并不断发动攻势使其陷入被动 法国情报人员都感到莫名其妙 一天 有位提篮子的德国农妇在过边界时受到了盘查 哨兵打开农妇提着的篮子 见里头都是煮熟的鸡蛋 亳无可疑之处 便无意识地拿起一个抛向空中 农妇慌 忙把它接住 哨兵们觉得这很可疑 他们将鸡蛋剥开 发现蛋白上布满了字迹 都是英军的详细布防图 还有各师旅的番号 原来 这种传递情报的方法是德国 一位化学家提供的 其作法并不复杂 用醋酸在蛋壳上写字 等醋酸干了后 再 将鸡蛋煮熟 字迹便透过蛋壳印在蛋白上 外面却没有任何痕迹 1914 年 8 月 5 日 英国 泰尔哥尼亚 号船上的潜水员割断了德国在北大西 洋海下的电缆 他们的目的很简单 就是想让德国的日子更难过 没想到这却使 德方大量的通讯从电缆转向了无线电 结果 英方截取了大量原本无法得到的情 报 情报一旦截获 就被送往 40 号房间 英国海军部的密件分析部门 40 号 房间可以说是现代密件分析组织的原型 这里聚集了数学家 语言学家 棋类大 师等任何善于解谜的人 1914 年 9 月 英国人收到了一份 珍贵 的礼物 同盟者俄国人在波罗的海 截获了一艘德国巡洋舰 玛格德伯格 号 得到一本德国海军的密码本 他们立即 将密码本送至 40 号房间 允许英国破译德国海军的密件 并在战争期间围困德 军战船 能够如此直接 顺利且经常差不多是同时读取德国海军情报的情况 在 以往的战事中几乎从未发生过 4 密码学历史上最伟大的密码破译事件开始于 1917 年 1 月 17 日 当时英军截 获了一份以德国最高外交密码 0075 加密的电报 这个令人无法想象的系统由一 万个词和词组组成 与一千个数字码群对应 密电来自德国外交部长阿瑟 齐麦 曼 传送给他的驻华盛顿大使约翰 冯 贝伦朵尔夫 然后继续传给德国驻墨西哥 大使亨尼希 冯 艾克哈尔特 电文将在那里解密 然后交给墨西哥总统瓦律斯提 阿诺 加汉扎 密件从柏林经美国海底电缆送到了华盛顿 英军在那里将其截获并意识到了 它的重要性 但是 同样接到密件的约翰 冯 贝伦朵尔夫却在他的华盛顿办公室 里犯了个致命的错误 他们将电报用新的 0075 密件本译出 然后又用老的密件 本加密后用电报传送到墨西哥城 大使先生没有意识到 他已经犯下了一个密码 使用者所能犯的最愚蠢的 最可悲的错误 此时 已经破译了老密码的英方正对着这个未曾破译的新外交密码系统一筹 莫展 不过没过多久 他们便从大使先生的糊涂操作中获得了新旧密码的比较版 本 随着齐麦曼的密件逐渐清晰起来 其重要性令人吃惊 尽管 1915 年美国的远洋客轮 露斯塔尼亚 号被德军击沉 但只要德国对其 潜艇的行动加以限制 美国仍将一直保持中立 齐麦曼的电文概括了德国要在 1917 年 2 月 1 日重新开始无限制海战以抑制英国的企图 为了让美国原地不动 齐麦曼建议墨西哥入侵美国 重新宣布得克萨斯州 新墨西哥州和亚里桑纳州归 其所有 德国还要墨西哥说服日本进攻美国 德国将提供军事和资金援助 英国海军部急于将破译的情报通知美国而又不能让德国知道他们的密码已 被破译 于是 英国的一个特工成功地渗入了墨西哥电报局 得到了送往墨西哥 总统的解了密的文件拷贝 这样 秘密就可能是由墨西哥方泄露的 他们以此为 掩护将情报透露给了美国 美国愤怒了 每个人都被激怒了 原先只是东海岸的人在关心 现在 整个 中西部都担心墨西哥的举动 电文破译后六个星期 美国对德国宣战 当总统伍 德罗 威尔逊要求对德宣战时 站在他背后的 是一个团结起来的愤怒的国家 它时刻准备对德作战 这可能是密码破译史上 当然也是情报史上最著名的事件 齐麦曼的电文使 整个美国相信德国是国家的敌人 德国利用密码破译击败了俄军 反过来又因自 5 己的密码被破译而加速走向了灭亡 第一次世界大战前 重要的密码学进展很少出现在公开文献中 直到 1918 年 二十世纪最有影响的密码分析文章之一 William F Friedman 的专题论文 重 合指数及其在密码学中的应用 作为私立的 河岸 Riverbank 实验室 的一份研 究报告问世了 其实 这篇著作涉及的工作是在战时完成的 一战后 完全处于 秘密工作状态的美国陆军和海军的机要部门开始在密码学方面取得根本性的进 展 但是公开的文献几乎没有 然而技术却在飞速的发展 简单的明文字母替换法已经被频率分析法毫无难 度地破解了 曾经认为是完美的维吉耐尔 Vigenere 密码和它的变种也被英国人 Charles Babbage 破解了 顺便说一句 这个 Charles Babbage 可不是凡人 他设 计了差分机 Difference Engine 和分析机 Analytical Engine 而这东西就是现在计 算机的先驱 这个事实给了人们两个启示 第一 没有哪种 绝对安全 的密码是 不会被攻破的 这只是个时间问题 第二 破译密码看来只要够聪明就成 在二 次大战中 密码更是扮演一个举足轻重的角色 许多人认为同盟国之所以能打赢 这场战争完全归功於二次大战时所发明的破译密文数位式计算机破解德日密码 1918 年 加州奥克兰的 Edward H Hebern 申请了第一个转轮机专利 这种装 置在差不多 50 年里被指定为美军的主要密码设备 它依靠转轮不断改变明文和 密文的字母映射关系 由于有了转轮的存在 每转动一格就相当于给明文加密一 次 并且每次的密钥不同 而密钥的数量就是全部字母的个数 26 个 同年 密码学界的一件大事 终于 发生了 在德国人 Arthur Scherbius 天才 的努力下 第一台非手工编码的密码机 ENIGMA 密码机横空出世了 密码器 是德军在二战期间最重要的通讯利器 也是密码学发展史上的一则传奇 当时盟 军借助英国首都伦敦北方布来奇利公园的政府电码与密码学院 全力破译德军的 谜 双方隔着英吉利海峡斗智 写下一页精彩无比的战史 后来成为无数电 影与影集的主要情节 随着高速 大容量和自动化保密通信的要求 机械与电路相结合的转轮加密 设备的出现 使古典密码体制也就退出了历史舞台 二 二 第二阶段第二阶段 19491949 年年 1975 1975 年年 1949 年仙农 Claude Shannon 保密系统的通信理论 为近代密码学建立了 6 理论基础 从 1949 年到 1967 年 密码学文献近乎空白 许多年 密码学是军队 独家专有的领域 美国国家安全局以及前苏联 英国 法国 以色列及其它国家 的安全机构已将大量的财力投入到加密自己的通信 同时又千方百计地去破译别 人的通信的残酷游戏之中 面对这些政府 个人既无专门知识又无足够财力保护 自己的秘密 1967 年 David Kahn 破译者 The CodeBreaker 的出现 对以往的密码学 历史作了相当完整的记述 破译者 的意义不仅在于涉及到相当广泛的领域 它使成千上万的人了解了密码学 此后 密码学文章开始大量涌现 大约在同一 时期 早期为空军研制敌我识别装置的Horst Feistel在位于纽约约克镇高地的IBM Watson 实验室里花费了毕生精力致力于密码学的研究 在那里他开始着手美国 数据加密标准 DES 的研究 到 70 年代初期 IBM 发表了 Feistel 和他的同事在 这个课题方面的几篇技术报告 三 三 第三阶段第三阶段 19761976 年至今年至今 1976年diffie 和 hellman发表的文章 密码学的新动向 一文导致了密码学 上的一场革命 他们首先证明了在发送端和接受端无密钥传输的保密通讯是可能 的 从而开创了公钥密码学的新纪元 1978 年 R L Rivest A Shamir 和 L Adleman 实现了 RSA 公钥密码体制 1969 年 哥伦比亚大学的 Stephen Wiesner 首次提出 共轭编码 Conjugate coding 的概念 1984 年 H Bennett 和 G Brassard 在次思想启发下 提出量子 理论 BB84 协议 从此量子密码理论宣告诞生 其安全性在于 1 可以发现窃听 行为 2 可以抗击无限能力计算行为 1985 年 Miller 和 Koblitz 首次将有限域上的椭圆曲线用到了公钥密码系统 中 其安全性是基于椭圆曲线上的离散对数问题 1989 年 R Mathews D Wheeler L M Pecora 和 Carroll 等人首次把混沌理论使 用到序列密码及保密通信理论 为序列密码研究开辟了新途径 2000 年 欧盟启动了新欧洲数据加密 数字签名 数据完整性计划 NESSIE 究适应于 21 世纪信息安全发展全面需求的序列密码 分组密码 公开密钥密码 hash 函数以及随机噪声发生器等技术 7 三 密码分析的方法三 密码分析的方法 密码分析之所以能够成功破译密码 最根本的原因是明文中有冗余度 攻击 或破译密码的方法主要有三种 穷举法 统计分析攻击 数学分析攻击 一 穷举法攻击 一 穷举法攻击 所谓穷举攻击是指 密码分析者采用依次试遍所有可能的秘钥对所获密文进 行破解 直至得到正确的明文 或者用一个确定的秘钥对所有可能的明文进行加 密 直至得到所得的密文 这也是所谓的暴力破解 只要有足够的时间和存储空 间 穷举攻击原则上是可行的 但是集中面积算时间和存储空间都受到限制 只 要秘钥足够长 这种方法往往不行 用暴力破解的方法可以破解出 DES 算法 此法计算相当复杂 但也不是不能 实现的 1998 年 EFF 为了向世人证明 des 不是一种安全的加密方式而制造了一台 专用于破解 des 的机器 这台机器叫做 Deep Crack 总共耗资 20 万美元 该机器使 用 1536 个专用处理器 平均破解 穷举 出一个正确的 key 需耗时 4 天左右 每秒钟 可以穷举 920 亿个 key 二 统计分析攻击 二 统计分析攻击 统计分析攻击是指密码分析者涌过分析密文和明文的统计规律来破译密码 密码分析者对截获的密文进行统计分析 总结出其间的统计规律 并与明文的统 计规律进行比较 从中提取明文和密文之间的对应或变换信息 这一攻击有一个经典案例就是中途岛海战的密码破译 中途岛战役 是第二 次世界大战的一场重要战役 也是美国海军以少胜多的一个著名战例 密码分析 在这场战役中发挥了重要作用 美国海军情报局在与英国以及荷兰相关单位紧密 的合作下 开始成功的解读日本海军主要通讯系统 JN 25 的部分密码 到了五月 上旬 联军在破解 JN 25 上取得了重大的突破 也因此得到了窥探日本海军计划 的能力 JN 25 让联军得悉 AF 方位 将会是日本海军的下一个攻击目标 然而 联军就偏偏破解不到 AF 方位 的位置 一些美军的高层将领认为 AF 方位 便是中途岛 另外一些则认为是阿留申群岛 然而任凭联军解码科技多么的先进 也仍然无法破解 AF 方位 的正确位置 正当美军高层在伤脑筋的同时 一名 年轻军官却想到了一个能够确认 AF 方位 是不是中途岛的妙计 他要求中途 岛海军基地的司令官以无线电向珍珠港求救 说中途岛上的食水供应站出现了问 8 题 导致整个中途岛面临缺水的危机 不久后 美国海军情报局便截夺到一则 JN 25 信息 内容果然提到了 AF 方位 出现缺水问题 结果 AF 方位 便证实 为中途岛 也就是日本海军的下一个攻击目标 三 数学分析攻击 三 数学分析攻击 数学分析攻击是密码分析者针对加解密算法的数学基础和某些密码学特性 通过数学求解的方法来破译密码 第一次世界大战期间 法国谍报人员也曾破译过许多奇特的密码 但是 到 1918 年 3 月 5 日 他们截收到的德军密电中翻来覆去都只是 A D F G X 五 个字母 原来 当时的德军参谋总长鲁登道夫将军非常重视突然袭击的战术效果 但 这需要有一种新的密码体制来难倒法国的破译专家 使他们无法知道德军下一个 进攻目标 经过反复研究与实验 密码专家尼贝尔设计的方案被证明安全系数最 高 这种密码只需要五个字母 A D F G X 画一个 5 5 的正方形 在左边 和上边写好 A D F G X 然后再在表中亳无规律地填入 25 个字母 i 与 j 合而 为一 这样 拍发的一条信息就可编为如下的密码 FX DD AG GF XA DG GX DD AG XA GX AG XA FA GX 其实 这种编码实质上是一个字母改用两个字母代替 好比平 面上点的坐标表示法一样 实在算不上多么难解的天书 当时德军节节推进 其前锋部队已经到达离巴黎只有 80 公里的地方了 一 个重大问题摆在协约军总部面前 鲁登道夫将军的下一个进攻目标在哪里 协约 国应该在哪里集结战略后备队呢 巴黎和整个法国的命运在此一举 就在这紧急关头 正在冥思苦想 试图解密的法国密码破译专家乔治 潘万 发现 被截获的德军情报中忽然添加了一个新的字母 V 一把破译的钥匙就这 样送到了法国人手中 乔治 潘万猜到 增加一个字母就意味着基本坐标方框已 经从 5 5 扩大为 6 6 的正方形 而这一定是为了把数字 0 9 直接进行编码的需 要 经过镇密的推理和无数次的试验 6 月 3 日凌晨 潘万及其部下成功地破译 了仅仅几小时以前截到的一份电报 它泄露了德军下一步将进攻巴黎北部贡比涅 的计划 协约军总司令 法国参谋总长福煦元帅立即调动他的后备队进驻贡比涅 的阵地 德法两军的战斗持续了五天 最后以德军的失败结束 鲁登道夫遭到了 9 他生平最严重的挫折 占领巴黎的野心被彻底粉碎了 四 密码分析的案例 四 密码分析的案例 MD5MD5 算法及其破解算法及其破解 2004 年 8 月 17 日在美国加州圣巴巴拉召开的国际密码学会议 Crypto 2004 上 来自山东大学的王小云教授做了破译 MD5 HAVAL 128 MD4 和 RIPEMD 算法的报告 在会场上 当她公布了 MD 系列算法的破解结果之后 报告被激动 的掌声打断 王小云教授的报告轰动了全场 得到了与会专家的赞叹 报告结束 时 与会者长时间热烈鼓掌 部分学者起立鼓掌致敬 这在密码学会议上是少见 的盛况 王小云教授的报告缘何引起如此大的反响 因为她的研究成果作为密码 学领域的重大发现宣告了固若金汤的世界通行密码标准 MD5 的堡垒轰然倒塌 引发了密码学界的轩然大波 会议总结报告这样写道 我们该怎么办 MD5 被 重创了 它即将从应用中淘汰 SHA 1 仍然活着 但也见到了它的末日 现在就 得开始更换 SHA 1 了 一 关于 一 关于 MD5MD5 算法算法 1 MD51 MD5 算法简介算法简介 MD5 即 Message Digest Algorithm 5 信息 摘要算法 5 用于确保信息传输 完整一致 是计算机广泛使用的杂凑算法之一 又译摘要算法 哈希算法 主 流编程语言普遍已有 MD5 实现 将数据 如汉字 运算为另一固定长度值 是 杂凑算法的基础原理 MD5 的前身有 MD2 MD3 和 MD4 MD5 的作用是让大容量信息在用数字签名软件签署私人密钥前被 压缩 成 一种保密的格式 就是把一个任意长度的字节串变换成一定长的十六进制数字 串 Rivest 在 1989 年开发出 MD2 算法 在这个算法中 首先对信息进行数据补 位 使信息的字节长度是 16 的倍数 然后 以一个 16 位的检验和追加到信息末 尾 并且根据这个新产生的信息计算出散列值 后来 Rogier 和 Chauvaud 发现 如果忽略了检验将和 MD2 产生冲突 MD2 算法加密后结果是唯一的 即不同信 息加密后的结果不同 为了加强算法的安全性 Rivest 在 1990 年又开发出 MD4 算法 MD4 算法同 样需要填补信息以确保信息的比特位长度减去 448 后能被 512 整除 信息比特位 长度 mod 512 448 然后 一个以 64 位二进制表示的信息的最初长度被添加 10 进来 信息被处理成 512 位 damg rd merkle 迭代结构的区块 而且每个区块要 通过三个不同步骤的处理 Den boer 和 Bosselaers 以及其他人很快的发现了攻击 MD4 版本中第一步和第三步的漏洞 Dobbertin 向大家演示了如何利用一部普通 的个人电脑在几分钟内找到 MD4 完整版本中的冲突 这个冲突实际上是一种漏 洞 它将导致对不同的内容进行加密却可能得到相同的加密后结果 毫无疑问 MD4 就此被淘汰掉了 尽管 MD4 算法在安全上有个这么大的漏洞 但它对在其 后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用 1991 年 Rivest 开发出技术上更为趋近成熟的 md5 算法 它在 MD4 的基础 上增加了 安全 带子 safety belts 的概念 虽然 MD5 比 MD4 复杂度大一些 但却更为安全 这个算法很明显的由四个和 MD4 设计有少许不同的步骤组成 在 MD5 算法中 信息 摘要的大小和填充的必要条件与 MD4 完全相同 Den boer 和 Bosselaers 曾发现 MD5 算法中的假冲突 pseudo collisions 但除此之外就没 有其他被发现的加密后结果了 2 MD52 MD5 应用应用 一致性验证一致性验证 MD5 的典型应用是对一段信息 Message 产生信息摘要 Message Digest 以防止被篡改 比如 在 UNIX 下有很多软件在下载的时候都有一个文件名相同 文件扩展名为 md5 的文件 在这个文件中通常只有一行文本 大致结构如 MD5 tanajiya tar gz 0ca175b9c0f726a831d895e269332461 这就是 tanajiya tar gz 文件的数字签名 MD5 将整个文件当作一个大文本信 息 通过其不可逆的字符串变换算法 产生了这个唯一的 MD5 信息摘要 为了 让读者朋友对 MD5 的应用有个直观的认识 以一个比方和一个实例来简要描述 一下其工作过程 大家都知道 地球上任何人都有自己独一无二的指纹 这常常成为公安机关 鉴别罪犯身份最值得信赖的方法 与之类似 MD5 就可以为任何文件 不管其 大小 格式 数量 产生一个同样独一无二的 数字指纹 如果任何人对文件做 了任何改动 其 MD5 值也就是对应的 数字指纹 都会发生变化 我们常常在某些软件下载站点的某软件信息中看到其 MD5 值 它的作用就 在于我们可以在下载该软件后 对下载回来的文件用专门的软件 如 Windows 11 MD5 Check 等 做一次 MD5 校验 以确保我们获得的文件与该站点提供的文件 为同一文件 利用 MD5 算法来进行文件校验的方案被大量应用到软件下载站 论坛数据库 系统文件安全等方面 数字证书数字证书 MD5 的典型应用是对一段 Message 字节串 产生 fingerprint 指纹 以防止被 篡改 举个例子 你将一段话写在一个叫 readme txt 文件中 并对这个 readme txt 产生一个 MD5 的值并记录在案 然后你可以传播这个文件给别人 别人如果修改了文件中的任何内容 你对这个文件重新计算 MD5 时就会发现 两 个 MD5 值不相同 如果再有一个第三方的认证机构 用 MD5 还可以防止文件 作者的 抵赖 这就是所谓的数字签名应用 安全访问认证安全访问认证 MD5 还广泛用于操作系统的登陆认证上 如 Unix 各类 BSD 系统登录密码 数字签名等诸多方面 如在 UN 系统中用户的密码是以 MD5 或其它类似的算 法 经 Hash 运算后存储在文件系统中 当用户登录的时候 系统把用户输入的 密码进行 MD5 Hash 运算 然后再去和保存在文件系统中的 MD5 值进行比较 进而确定输入的密码是否正确 通过这样的步骤 系统在并不知道用户密码的明 码的情况下就可以确定用户登录系统的合法性 这可以避免用户的密码被具有系 统管理员权限的用户知道 MD5 将任意长度的 字节串 映射为一个 128bit 的大 整数 并且是通过该 128bit 反推原始字符串是困难的 换句话说就是 即使你看 到源程序和算法描述 也无法将一个 MD5 的值变换回原始的字符串 从数学原 理上说 是因为原始的字符串有无穷多个 这有点象不存在反函数的数学函数 所以 要遇到了 md5 密码的问题 比较好的办法是 你可以用这个系统中的 md5 函数重新设一个密码 如 admin 把生成的一串密码的 Hash 值覆盖原来的 Hash 值就行了 正是因为这个原因 现在被黑客使用最多的一种破译密码的方法就是一种被 称为 跑字典 的方法 有两种方法得到字典 一种是日常搜集的用做密码的字符 串表 另一种是用排列组合方法生成的 先用 MD5 程序计算出这些字典项的 MD5 值 然后再用目标的 MD5 值在这个字典中检索 我们假设密码的最大长度为 8 位字节 8 Bytes 同时密码只能是字母和数字 共 26 26 10 62 个字符 排列 12 组合出的字典的项数则是 P 62 1 P 62 2 P 62 8 那也已经是一个很 天文的数字了 存储这个字典就需要 TB 级的磁盘阵列 而且这种方法还有一个 前提 就是能获得目标账户的密码 MD5 值的情况下才可以 这种加密技术被广 泛的应用于 UN 系统中 这也是为什么 UN 系统比一般操作系统更为坚固一个 重要原因 3 MD53 MD5 算法原理算法原理 对 MD5 算法简要的叙述可以为 MD5 以 512 位分组来处理输入的信息 且 每一分组又被划分为 16 个 32 位子分组 经过了一系列的处理后 算法的输出由 四个 32 位分组组成 将这四个 32 位分组级联后将生成一个 128 位散列值 在 MD5 算法中 首先需要对信息进行填充 使其位长对 512 求余的结果等 于 448 因此 信息的位长 Bits Length 将被扩展至 N 512 448 N 为一个非负 整数 N 可以是零 填充的方法如下 在信息的后面填充一个 1 和无数个 0 直 到满足上面的条件时才停止用 0 对信息的填充 然后 在这个结果后面附加一个 以 64 位二进制表示的填充前信息长度 经过这两步的处理 现在的信息的位长 N 512 448 64 N 1 512 即长度恰好是 512 的整数倍 这样做的原因是为 满足后面处理中对信息长度的要求 表示第 i 个分组 每次的运算都由前一轮的 128 位结果值和第 i 块 512bit 值 进行运算 初始的 128 位值为初试链接变量 这些参数用于第一轮的运算 以大 端字节序来表示 他们分别为 A 0 x01234567 B 0 x89ABCDEF C 0 xFEDCBA98 D 0 x76543210 每一分组的算法流程如下 第一分组需要将上面四个链接变量复制到另外四个变量中 A 到 a B 到 b C 到 c D 到 d 从第二分组开始的变量为上一分组的运算结果 主循环有四轮 MD4 只有三轮 每轮循环都很相似 第一轮进行 16 次操 作 每次操作对 a b c 和 d 中的其中三个作一次非线性函数运算 然后将所得 结果加上第四个变量 文本的一个子分组和一个常数 再将所得结果向左环移一 个不定的数 并加上 a b c 或 d 中之一 最后用该结果取代 a b c 或 d 中之 一 以一下是每次操作中用到的四个非线性函数 每轮一个 F X Y Z X Y X Z 13 G X Y Z X Z Y Z H X Y Z X Y Z I X Y Z Y X Z 这四个函数的说明 如果 X Y 和 Z 的对应位是独立和均匀的 那么结果的 每一位也应是独立和均匀的 F 是一个逐位运算的函数 即 如果 X 那么 Y 否则 Z 函数 H 是逐位奇偶 操作符 假 设 Mj 表 示 消 息 的 第 j 个 子 分 组 从 0 到 15 常 数 ti 是 4294967296 abs sin i 的整数部分 i 取值从 1 到 64 单位是弧度 4294967296 等于 2 的 32 次方 FF a b c d Mj s ti 表示 a b a F b c d Mj ti s GG a b c d Mj s ti 表示 a b a G b c d Mj ti s HH a b c d Mj s ti 表示 a b a H b c d Mj ti s a b c d Mj s ti 表示 a b a I b c d Mj ti s 这四轮 64 步 是 第一轮 FF a b c d M0 7 0 xd76aa478 FF d a b c M1 12 0 xe8c7b756 FF c d a b M2 17 0 x242070db FF b c d a M3 22 0 xc1bdceee FF a b c d M4 7 0 xf57c0faf FF d a b c M5 12 0 x4787c62a FF c d a b M6 17 0 xa8304613 FF b c d a M7 22 0 xfd469501 FF a b c d M8 7 0 x698098d8 FF d a b c M9 12 0 x8b44f7af FF c d a b M10 17 0 xffff5bb1 FF b c d a M11 22 0 x895cd7be FF a b c d M12 7 0 x6b901122 14 FF d a b c M13 12 0 xfd987193 FF c d a b M14 17 0 xa679438e FF b c d a M15 22 0 x49b40821 第二轮 GG a b c d M1 5 0 xf61e2562 GG d a b c M6 9 0 xc040b340 GG c d a b M11 14 0 x265e5a51 GG b c d a M0 20 0 xe9b6c7aa GG a b c d M5 5 0 xd62f105d GG d a b c M10 9 0 x02441453 GG c d a b M15 14 0 xd8a1e681 GG b c d a M4 20 0 xe7d3fbc8 GG a b c d M9 5 0 x21e1cde6 GG d a b c M14 9 0 xc33707d6 GG c d a b M3 14 0 xf4d50d87 GG b c d a M8 20 0 x455a14ed GG a b c d M13 5 0 xa9e3e905 GG d a b c M2 9 0 xfcefa3f8 GG c d a b M7 14 0 x676f02d9 GG b c d a M12 20 0 x8d2a4c8a 第三轮 HH a b c d M5 4 0 xfffa3942 HH d a b c M8 11 0 x8771f681 HH c d a b M11 16 0 x6d9d6122 HH b c d a M14 23 0 xfde5380c HH a b c d M1 4 0 xa4beea44 HH d a b c M4 11 0 x4bdecfa9 HH c d a b M7 16 0 xf6bb4b60 HH b c d a M10 23 0 xbebfbc70 15 HH a b c d M13 4 0 x289b7ec6 HH d a b c M0 11 0 xeaa127fa HH c d a b M3 16 0 xd4ef3085 HH b c d a M6 23 0 x04881d05 HH a b c d M9 4 0 xd9d4d039 HH d a b c M12 11 0 xe6db99e5 HH c d a b M15 16 0 x1fa27cf8 HH b c d a M2 23 0 xc4ac5665 第四轮 a b c d M0 6 0 xf4292244 d a b c M7 10 0 x432aff97 c d a b M14 15 0 xab9423a7 b c d a M5 21 0 xfc93a039 a b c d M12 6 0 x655b59c3 d a b c M3 10 0 x8f0ccc92 c d a b M10 15 0 xffeff47d b c d a M1 21 0 x85845dd1 a b c d M8 6 0 x6fa87e4f d a b c M15 10 0 xfe2ce6e0 c d a b M6 15 0 xa3014314 b c d a M13 21 0 x4e0811a1 a b c d M4 6 0 xf7537e82 d a b c M11 10 0 xbd3af235 c d a b M2 15 0 x2ad7d2bb b c d a M9 21 0 xeb86d391 所有这些完成之后 将 A B C D 分别加上 a b c d 然后用下一分组 数据继续运行算法 最后的输出是 A B C 和 D 的级联 4 MD54 MD5 算法的优势算法的优势 Van oorschot 和 Wiener 曾经考虑过一个在散列中暴力搜寻冲突的函数 16 brute force hash function 而且他们猜测一个被设计专门用来搜索 MD5 冲突 的机器 这台机器在 1994 年的制造成本大约是一百万美元 可以平均每 24 天就 找到一个冲突 但单从 1991 年到 2001 年这 10 年间 竟没有出现替代 MD5 算法 的 MD6 或被叫做其他什么名字的新算法这一点 我们就可以看出这个瑕疵并没 有太多的影响 MD5 的安全性 上面所有这些都不足以成为 MD5 的在实际应用中 的问题 并且 由于 MD5 算法的使用不需要支付任何版权费用的 所以在一般 的情况下 非绝密应用领域 但即便是应用在绝密领域内 MD5 也不失为一种 非常优秀的中间技术 MD5 怎么都应该算得上是非常安全的了 二 二 MD5MD5 算法的破解算法的破解 关于 MD5 算法的破解 一些黑客破获密码的方法是一种被称为 跑字典 的方法 有两种方法得到字典 一种是日常搜集的用做密码的字符串表 另一种 是用排列组合方法生成的 先用 MD5 程序计算出这些字典项的 MD5 值 然后再 用目标的 MD5 值在这个字典中检索 即使假设密码的最大长度为 8 同时密码 只能是字母和数字 共 26 26 10 62 个字符 排列组合出的字典的项数则是 P 62 1