数字图像加密与实现

2010 届本科毕业论文届本科毕业论文 数字图像加密与实现数字图像加密与实现 系系 院：院： 学生姓名：学生姓名： 学学 号：号： 专专 业：业： 年年 级：级： 完成日期：完成日期： 指导教师：指导教师： 摘 要 I 摘 要 随着 Internet 技术与多媒体技术的飞速发展，数字化信息可以以不同的形 式在网络上方便、快捷地传输。多媒体通信逐渐成为人们之间信息交流的重要手 段。多媒体信息安全技术的研究主要有两种方法：多媒体信息加密和多媒体信息 隐藏技术。信息加密与信息隐藏从不同的角度保证信息的安全，如果我们将信息 加密与信息隐藏有机地相结合，可进一步提高信息的安全性。 本课题的目的是实现一个安全性比较高的图像信息安全算法， 图像信息的 安全主要包括图像加密和图像认证，图像加密的目的是将一幅图像明文通过一定 的算法使其变成不可识别的密文，以防止攻击者截获原图像信息。图像加密有多 种方法，本课题采用的算法是基于 DES 和 RSA 的混合加密。虽然加密可以使原文 信息不被暴露，但一旦原文被接收并被篡改，加密就显得无能为力了。此时，就 需要图像认证的技术。图像认证的作用就是鉴定原图像有没有被篡改，以保护发 送者的利益。为实现图像认证的目的，本课题采用报文摘要结合数字水印的方法。 最后，本课题从安全性角度实现了二者的结合，使得图像信息的安全得到了进一 步的提高。 关键词：信息安全；图像加密 ；图像认证 ；数字水印 Abstract II Abstract With the Internet technology and the rapid development of multimedia technology, digital information can be transfered in different forms on the web quickly and easily. Multimedia communication has gradually become an important means of information exchange between people. Multimedia Information Security Technology there are two main ways: multimedia information and multimedia information hiding encryption technology. Message encryption and information hiding information from different angles to ensure the security, if we hide the information encrypted with the organic combination of information, can further enhance information security. The goal of this topic is realizing a high-security pictorial information security algorithm, the pictorial information security mainly includes the image encryption and the image authentication, the goal of image encryption is turning a pictorial information to be distinguished through a certain algorithm,which preventing the aggressor capture the original map.The image encryption has many kinds of methods,this topic uses the algorithm of the mix encryption which is based on on DES and the RSA. Although encryption may cause the original text information not be exposed, but once the original text is received and is tampered with, the encryption appeared helplessly. This time,needs the image authentication technology. The image authentications function is appraising if the original map picture has been tampered with, which is to protect the transmissions benefit. In order to realize the image authentication goal, this topic uses the method of a telegram abstract union numeral watermark.Finally, this topic has realized the two union from the secure angle,enable the security of pictorial information obtaining further enhancement. KeywordsKeywords :Security；Image encryption；Image Authentication；Digital Watermarking 目 录 目 录 1 绪论 .1 1.1 研究背景.1 1.2 研究方法.1 1.3 研究内容.2 2 关键技术 .3 2.1 报文摘要技术.3 2.1.1 单向散列函数 .4 2.1.2 单向散列函数技术 .4 2.2 数字图像技术.5 2.2.1 数字水印的概念 .5 2.2.2 数字水印的要求 .6 2.2.3 数字水印的原理及其通用模型 .6 2.3 数字图像加密技术.8 2.3.1 数字图像加密的原理与通用模型 .8 2.3.2 数字图像加密的典型算法 .8 3 算法实现 .11 3.1 采用的算法.11 3.2 算法流程图.12 3.3 报文摘要提取.12 3.4 数字图像水印.17 3.4.1 位图的位面 .17 3.4.2 LSB 算法模型 .17 3.4.3 LSB 算法的实现 .18 3.5 混合加密.19 3.5.1 DES 算法 .19 3.5.2 RSA 公开密钥密码体制 .25 3.5.3 混合加密的实现 .26 4 一种基于现代密码体制的图像加密算法 .28 4.1 现代密码体制 .28 目 录 I 4.2 AES 简介 .29 4.2.1 AES 的来源 .29 4.2.2 AES 算法描述 .30 4.3 基于 AES 的数字图像置乱.31 4.4 实验结果与分析.32 4.4.1 图像的置乱效果 .32 5 总结 .33 参考文献 .34 致谢 .35 绪 论 0 1 绪论 1.1 研究背景 随着 Internet 技术与多媒体技术的飞速发展，数字化信息可以以不同的形 式在网络上方便、快捷地传输。多媒体通信逐渐成为人们之间信息交流的重要手 段。人们通过网络交流各种信息，进行网上贸易等。因此，信息的安全与保密显 得越来越重要。信息的安全与保密不仅与国家的政治、军事和外交等有重大的关 系，而且与国家的经济、商务活动以及个人都有极大的关系。随着信息化社会的 到来，数字信息与网络已成为人们生活中的重要组成部分，他们给我们带来方便 的同时，也给我们带来了隐患：敏感信息可能轻易地被窃取、篡改、非法复制和 传播等。因此信息安全已成为人们关心的焦点，也是当今的研究热点和难点。 多媒体数据，尤其是图像，比传统的文字蕴涵更大的信息量，因而成为人类 社会在信息利用方面的重要手段。因此针对多媒体信息安全保护技术的研究也显 得尤为重要，多媒体信息安全是集数学、密码学、信息论、概率论、计算复杂度 理论和计算机网络以及其它计算机应用技术于一体的多学科交叉的研究课题。 1.2 研究方法 多媒体信息安全技术的研究主要有两种方法：多媒体信息加密和多媒体信息 隐藏技术。 多媒体信息加密技术：我们可以把多媒体数据作为文本数据流一样看待，使 用传统的加密算法进行加密。传统的加密方法如 DES、3-DES 或 RSA 等也能满足 多媒体应用中的要求。然而，新型的多媒体应用就需要新的数据加密技术。近年 来，在这方面的研究取得了一些成果，主要针对视频数据和图像数据。 多媒体信息隐藏技术：密码学技术仅仅隐藏了了信息的内容，而信息隐藏技 术不但信息的内容而且隐藏了信息的存在。广义上的信息隐藏技术包括隐写术， 数字水印，数字指纹，隐蔽信道，阈下信道，低截获概率通信和匿名通信等，狭 义上的信息隐藏技术通常指隐写术与数字水印。其中，数字水印技术在图像论证 方面有较广泛的应用。 信息加密与信息隐藏从不同的角度保证信息的安全，如果我们将信息加密与 信息隐藏有机地相结合，可进一步提高信息的安全性。 绪 论 1 1.3 研究内容 数字图像比声音、文字等蕴涵更多的信息，因而在多媒体信息中占有举足 轻重的地位，数字图像信息安全是多媒体信息安全的重要组成部分。因此本文以 数字图像为基础，研究数字图像信息安全技术。图像信息安全技术包括图像加密 和图像认证等。 关键技术 2 2 关键技术 本课题旨在分析数字图像的结构和特点，对数字图像进行加密和解密，即： 利用一定的算法对一副图像进行加密以达到不暴露原始图像的目的,然后进行解 密以达到恢复原始图像的目的。同时，为了鉴别出图像是否被篡改，要求满足图 像认证的要求。认证的目的是检测对图像数据的修改，以确定载体信息的完整性 和真实性。可用易碎水印和报文摘要来实现图像认证。虽然只用报文摘要也能达 到图像认证的目的，这种方法认证的精确度比较高，但是在传输过程中难免会受 到噪声等的干扰，故使用报文摘要可能会达不到预期的目的，同时，因为数字水 印也有图像认证的功能，因此，本系统采用报文摘要结合易碎水印来实现该目的。 2.1 报文摘要技术 在信息的安全领域中，对付被动攻击的重要措施是加密，而对付主动攻击中 的篡改和伪造和则要用报文鉴别的方法。报文鉴别是这样一种过程，它使得通信 的接收方能够验证所收到的报文的真伪。 近年来，广泛使用报文摘要 MD 进行报文鉴别。发送端将可变长度的报文 m 经过报文摘要算法后得出固定长度的报文摘要 H(m)。然后对 H(m)进行加密，得 出 EK（H(m)） ，并将其追加在报文 m 后面发送出去。接收端将 EK（H(m)）解密还 原为 H(m)，再将收到的报文进行摘要运算，得出的是否为此 H(m)。如不一样， 则可断定收到的报文不是发送端发送的。 报文摘要是多对一的单向散列函数的例子。要做到不可伪造，报文摘要算法 必须满足以下两个条件： （1）任给一个报文摘要值 x，若想得到一个报文 y 使得 H(y)=x，则在计算 上是不可行的。 （2）若想找到任意两个报文 x 和 y，使得 H(x)=H(y)，则在计算上是不可行 的。 上述的两个条件表明：若(m, H(m)是发送者产生的报文和报文摘要对，则 攻击者不可能伪造出另一个报文 y，使得 y 与 x 具有同样的报文摘要。发送者可 以对进行数字签名，使报文成为可检验的和不可抵赖的2。 关键技术 3 2.1.1 单向散列函数 要设计一个接收任意长度输入的函数特别是单向散列函数是很困难的事，在 实际中，单向散列函数建立在压缩函数的想法上。给定一长度为 m 的输入，单向 函数输出长为 n 的散列值。压缩函数的输入是消息分组和文本前一分组的输出。 输出是到该点的所有分组的散列，即分组的散列为： i M 公式（2-1） 1 , iii hMfH 该散列值和下一轮消息分组一起，作为压缩函数下一轮的输入。最后一分组 的散列就成为整个消息的散列。散列的信息应该包含整个消息长度的某种二进制 表示。这种方法能消除由不同长度的消息可能会具有相同的散列值所带来的潜在 的安全问题，这种技术有时称之为增强的 MD。 2.1.2 单向散列函数技术 目前的单向散列技术主要有以下几种： （1）Snetru 算法 Snetru 算法是 Rslph Merkle 设计的一种单向散列函数，它将任意长度的消 息散列成 128 或 256 位的值。首先将消息分成为 512-m 的分组（m 是散列值的长 度） 。若输出是 128 位散列值，则每分组 384 位长；若输出是 256 位散列值，则 分组 256 位长。 （2）N-Hash 算法 N-Hash 是由日本电话电报公司的研究人员发明的，他们曾于 1990 年发明了 FEAL。N-Hash 使用 128 位消息分组及一个与 FEAL 类似的复杂随机函数，并产生 128 位散列值。每个 128 位分组的散列是这一分组和上一分组的散列的函数。整 个消息的散列是最后一个消息分组的散列。随机初始值 I 可以是用户设置的任意 值（甚至为全零） 。 （3）MD4 算法 MD4 是 Ron Rivest 设计的单向散列函数，MD 表示消息摘要，对于输入消息， 算法产生 128 位散列值（或消息摘要） 。 （4）MD5 算法 MD5 是 MD4 的改进版，它比 MD4 更复杂，但设计思想相似，并且也产生 128 位散列。在一些初始化处理之后，MD5 以 512 位分组来处理输入文本，每一分组 又划分为 16 个 32 位子分组。算法的输出由四个 32 位分组组成，将它们级联形 关键技术 4 成一个 128 位散列值。 （5）安全散列算法 NIST NSA 一道设计了与 DDS 一起使用的安全散列算法 SHA，SHA 是用于标准 的算法，该标准规定一种保证数字签名算法(DSA)安全所必需的安全散列算法 （SHA） 。当输入是长度小于 264 位的消息时，SHA 产生一称为消息摘要的 160 位 输出，然后将该摘要输入到用于计算消息签名的 DSA 中。SHA 基于的原则与 MIT 的 Ronald L Rivest 教授在设计 MD4 消息摘要算法时所用的原理相似，并且模 仿了该算法。 （6）几种算法的比较 Snefru 的安全性取决于可逆分组密码函数 E，它用几轮运算使数据随机化。 对于轮数少于八的 Snefru，已被证明是不安全的，最近，Merkle 建议使用至少 八轮的 Snefru，但是如此多轮的算法比 MD5 或 SHA 要慢得多。N-Hash 算法已被 证明不安全 。MD5 是 MD4 的改进版，安全性更高，更难于被破译。SHA 算法主 要是与数字签名算法一起使用的安全散列算法，与 MD4 非常相似，主要的改变是 添加了扩展转换，并且为产生更快的雪崩效应而将上一轮的输出送至下一轮。本 课题使用单向散列函数的目的是为了实现图像认证，故选用安全性较高的 MD5 算 法4。 2.2 数字图像技术 2.2.1 数字水印的概念 日程生活中为了鉴别纸币的真伪，人们通常将纸币对着光源，会发现真的纸 币中有清晰的图像信息显示出来，这就是我们熟悉的“水印” 。之所以采用水印 技术是因为水印有其独特的性质：第一，水印是一种几乎不可见的印记，必须放 置于特定环境下才能被看到，不影响物品的使用；第二水印的制作和复制比较复 杂，需要特殊的工艺和材料，而且印刷品上的水印很难被去掉。因此水印常也被 应用于诸如支票、证书、护照、发票等重要印刷品中，长期以来判定印刷品真伪 的一个重要手段就是检验它是否包含水印。 借鉴普通水印的含义和功能，人们采用类似的概念保护诸如数字图像、数字 音乐这样的多媒体数据，因此就产生了“数字水印”的概念。所谓“数字水印” 是往多媒体数据中添加的某些数字信息，比如将在数码相片中添加摄制者的信息， 在数字影碟中添加电影公司的信息等等。与普通水印的特性类似，数字水印在多 关键技术 5 媒体数据中（如数码相片）也几乎是不可见的，也很难被破坏掉。因此数字水印 在今天的计算机和互联网时代大有可为1。 2.2.2 数字水印的要求 数字水印是往多媒体数据（如图像、声音、视频信号等）中添加某些数字信 息以达到图像认证等作用。在绝大多数的情况下，我们希望添加的信息是不可察 觉的，并且希望攻击者在不破坏数据本身质量的情况下无法将水印去掉。同时， 在嵌入水印的过程中，我们又不可以破坏原来的文件，即不能让人们发觉水印的 存在，因此，不可见性是数字水印的首要要求。 鲁棒性问题对数字水印同样非常重要。有效的数字水印应该能够承受大量不 同的物理和几何失真，包括有意的（如恶意攻击）或无意的（如图像压缩，滤波、 扫描与复印，噪音污染、尺寸变化等等） 。显然在经过这些操作后，鲁棒的水印 算法应仍能从水印图像中提取出嵌入的水印或证明水印的存在。若攻击者试图删 除水印则将导致多媒体产品的彻底破坏。因此，我们还需要达到鲁棒性的要求。 2.2.3 数字水印的原理及其通用模型 从图像处理的角度看，嵌入水印信号可以视为在强背景下迭加一个弱信号， 只要迭加的水印信号强度低于 HVS 的对比度门限，HVS 就无法感到信号的存在。 对比度门限受视觉系统的空间、时间和频率特性的影响。因此，通过对原始图像 作一定的调整，有可能在不改变视觉效果的情况下嵌入一些信息。从数字通信的 角度看，水印嵌入可理解为在一个宽带信道（载体图像）上用扩频通信技术传输 一个窄带信号（水印信号） 。尽管水印信号具有一定的能量，但分布到信道中任 一频率上的能量是难以检测到的。水印的译码（检测）则是一个有噪信道中弱信 号的检测问题3。 设载体图像为 I，水印信号为 W，密钥为 K，则水印嵌入可用公式（2-2）描 述。 公式(2-2)KWIFIw, 式中 F 表示水印嵌入策略（算法）.水印的嵌入过程如图 2-1 所示。 有两种常用的水印嵌入公式： ii w i aWVV 公式(2-3) ii w i aWVV1 关键技术 6 图 2-1 水印信号嵌入 其中分别表示载体图像像素和嵌入水印的图像像素；为水印信号分 w ii VV , i W 量，0iK； 为强度因子。为了保证在不可见的前提下，尽可能提高嵌入水 印的强度， 的选择必须考虑图像的性质和视觉系统的特性。 图 2-2，图 2-3 是水印提取与检测流图。图 2-2，图 2-3 中的虚框部分表示 在提取或判断水印信号时原始数据不是必要的。 在某些水印系统中，水印可以被精确地抽取出来，这一过程被称作水印提取。 比如在完整性确认应用中，必须能够精确地提取出插入的水印，并且通过水印的 完整性来确认多媒体数据的完整性。如果提取出的水印发生了部分的变化，最好 还能够通过发生变化的水印的位置来确定原始数据被篡改的位置。 对于强壮水印，通常不可能精确地提取出插入的原始水印，因为一个应用如 果需要强壮水印，说明这个应用很可能遭受到各种恶意的攻击，水印数据历经这 些操作后，提取出的水印通常已经面目全非。这时我们需要一个水印检测过程， 见图 2-3。通常水印检测的第一步是水印提取，然后是水印判决。水印判决的通 常做法是相关性检测。选择一个相关性判决标准，计算提取出的水印与指定的水 印的相关值，如果相关值足够高，则可以基本断定被检测数据含有指定的水印。 从以上论述可以看出，水印提取的任务是从嵌入水印的数据中提取水印信号，而 水印检测的任务是判断某一数据内容中是否存在指定的水印信号。另外，水印检 测的结果依赖于一个阈值，当相关性检测的结果超过这个阈值时，给出含有指定 水印的结论。这实际上是一个概率论中的假设检验问题。当提高相关性检测的阈 值时，虚检概率降低，漏检概率升高；当降低相关性检测的阈值时，虚检概率升 高，漏检概率降低。所谓虚检(false positive)，就是将没有水印信号的数据误 认为含有水印信号。所谓漏检(false negative)，就是未能从含有水印信号的数 据中检测到水印信号。在实际的水印应用中，更注重对虚检概率的控制5。 密 钥水印信息 水印嵌 入算法 含水印 载体信息 载体信息 关键技术 7 水印信息 提取算法 水印信息 密 钥 载体信息 水印信息 水印信息 载体算法 密 钥 原载体信息 含水印否？ 图 2-2 水印信号提取 图 2-3 水印信号检测 2.3 数字图像加密技术 2.3.1 数字图像加密的原理与通用模型 数字图像加密就是在发送端采用一定的算法作用于一幅图像明文，使其变成 不可识别的密文，达到图像保密的目的。在接收端采用相应的算法解密，恢复出 原文。其通用算法模型如图 2-4 所示。 原文图像密 文原文图像 加密解密 密钥 密钥 图 2-4 数字图像加密通用模型 2.3.2 数字图像加密的典型算法 目前国内外对数字图像加密的研究主要采用以下几种方法： （1）基于矩阵变换像素置换的图像加密技术 1）Arnold 变换，俗称猫脸变换.设像素的坐标 x , y S = 0, 1, 2, , N-1, 则 Arnold 变换为： 公式(2-4)1, 1 , 0,mod 21 11 , , NyxN y x y x Arnold 变换可以看做是裁剪和拼接的过程。通过这一过程将离散化的数字 图像矩阵 S 中的点重新排列。由于离散数字图像是有限点集,这种反复变换的结 果, 在开始阶段 S 中像素点的位置变化会出现相当程度的混乱,但由于动力系统 固有的特性, 在迭代进行到一定步数时会恢复到原来的位置。 2）按幻方做图像像素置乱变换。这种变换实质上是矩阵的初等变换, 并且 水印信息 关键技术 8 由于幻方矩阵是一有限维矩阵, 经过 n 次置换, 又会回到原来的位置, 因而也可 以用(1)所述的方法加以破译, 固其加密效果也是不好的。但若能把初等矩阵变 换转化为某种非线性变换则有可能增强置乱效果, 再结合其它的现代密码学的一 些成熟的加密算法如 DES,RSA 等则可以增加算法的保密性6。 （2）基于秘密分割与秘密共享的图像加密技术 秘密分割就是把消息分割成许多碎片, 每一个碎片本身并不代表什么, 但把 这些碎片放到一起消息就会重现出来。这种思想用于图像数据的加密上就是在发 送端先要把图像数据按某种算法进行分割, 并把分割后的图像数据交给不同的人 来保存; 而在接收端需要保存秘密的人的共同参与才能恢复出原始待传输的图像 数据。 （3）基于现代密码体制的图像加密技术 这种加密技术就是把待传输的图像看做明文,通过各种加密算法,如 DES,RSA 等, 在密钥的控制下,达到图像数据的保密通信。这种加密机制的设计思想是加 密算法可以公开,通信的保密性完全依赖于密钥的保密性(即满足 Kerckhoffs 假 设)。其原理框图如图 2-5 所示。 加 密 密码分析 解 密 明文 （原始图像） 密文 （加密图像） 原始明文 原始图像 加密密钥解密密钥 图 2-5 密钥控制下的保密通信框图 其中: 加密密钥和解密密钥可以相同也可以不同, 并依此来划分出两种基本 的密码算法,即对称算法和非对称算法(也叫公开密钥算法。 基于密钥的算法通 常有以下两类: 1) 对称算法 对称算法，又叫传统密码算法,就是加密密钥能够从解密密钥中推算出来,反 过来也成立。在大多数对称算法中,加解密密钥是相同的。这些算法也叫秘密密 钥算法或单钥算法, 它要求发送方和接受方在安全通信之前商定一个密钥。对称 算法的安全性完全依赖于密钥, 泄露密钥就意味着任何人都能对消息进行解密。 只要通信需要保密,密钥就必须保密。对称算法又可分为两类。一次只对明文中 的单个位(或字节)运算的算法称为流密码。另一类算法是对明文的一组位进行运 关键技术 9 算,叫分组密码 ,如 IBM 的 DES 算法。 2) 公开密钥算法 即：用作加密的密钥不同于用作解密的密钥,并且解密密钥不能根据加密密 钥计算出来。之所以叫做公开密钥算法,是因为加密密钥能够公开,即任何人都能 用加密密钥加密信息,但只有用相应的解密密钥才能解密信息。在这种体制中,加 密密钥叫做公开密钥，简称公钥。解密密钥叫做私人密钥，简称私钥。利用公钥 密码体制进行保密通信时,加密密钥可以公开,只保密解密密钥就能达到保密通信。 解密密钥和加密密钥不同,从一个难以推出另一个,其设计规律都是把推算解密密 钥的问题等效为一个难以求解的数学问题。通信双方无须事先交换密钥就可建立 起保密通信,它解决了通信双方进行保密通信的密钥分配问题。它不需要铺设专 门的安全传输线路,也不需要专门信使在通信双方传递密钥,因而可以节约大量费 用。在公钥密码体制中, 最重要的有 RSA 体制、背包体制、ElGamal 体制、 Robin 体制、椭圆曲线体制及多维 RSA 体制等。它们的共同点都是基于陷门单向 函数的概念,把问题归结为某一数学难题的求解。其中背包体制在最初提出 5 年 中被认为是安全的,但此算法在 20 世纪 80 年代初就被 Shamir 完全破译了。 算法实现 10 3 算法实现 3.1 采用的算法 近年来，随着国际互联网络与多媒体技术的迅速发展，数字图像己经逐渐 克服了往日因存储量巨大而带来的种种问题，成为信息表达方式的主流，数字图 像信息的安全问题成为国际上研究的焦点问题。数字图像具有信息量大、信息表 达直观的特点，它的安全保密显然与以往在计算机上所面对的文本数据截然不同。 数字图像信息安全保密是结合数学、密码学、信息论、计算机视觉以及其它计算 机应用技术的多学科交叉的研究课题。数字图像的加密技术是当代信息安全领域 中比较活跃的一个研究方向。它结合了数学、密码学、信息论、计算机视觉以及 其它计算机应用技术的多门学科。随着科技的发展，尤其是多媒体技术的发展， 出现了更多的、新的图像加密算法，而按照不同的分类标准，图像加密算法还可 以作其他不同的分类。 通过阅读一定量的资料了解到该课题目前在国内外的研究状况和相应的发展 趋势。经过反复的思考，本课题打算按以下思路着手设计，以求最终能以程序实 现该课题。 即：DES 和 RSA 的混合加密算法，先随机产生一个 DES 密钥，用此密钥加密 图像，得到扩展名为.bmp.mcs 的文件 1，然后采用 RSA 加密算法对随机产生的 DES 密钥进行加密将得到的密文加到文件 1 的文件头里面去。这样如果想得到原 文件就必须先破解文件头，而文件头是由 RSA 加密的，安全性比较高，想破解并 不是件容易的事，同时又由于 DES 加密速度快，适用于大文件的加密，且安全性 不高，而 RSA 加密速度慢，适用于小文件的加密，但安全性很高，两者的结合即 满足了速度的要求，又满足了安全性的要求。同时，为了满足图像鉴定的要求， 特引进数字水印技术，即：采用一散列函数作用原图像，以提取一报文摘要，然 后将此报文摘要作为水印信息嵌入到原始图像中，经加密解密后，再在解密后的 图像中提取水印信息，然后判断此水印信息和原报文摘要是否相同，若相同，说 明原始图像没有被篡改过，否则说明原始图像已被篡改。 算法实现 11 3.2 算法流程图 原始图像 DES 密钥 数据流 摘要 摘要水印 加密图像 摘要水印 解密后图像 摘要水印 摘要 RSA 加密此密钥 对此，看是否一致？以达到图像认证的目的！ 解密 文件头 加密图像 摘要水印 提取水印 DES 加密 MD5 算法 作为水印信息 图 3-1 算法流程图 3.3 报文摘要提取 MD5 算法是由 Rivest(RSA 中的 R)于 1991 年提出的 Hash 算法。今天已成为 最广泛使用的 Hash 算法。MD5 算法并非是 Rivest 提出的首个 Hash 算法，1990 年 Rivest 就已提出了一个 Hash 算法 MD4，并被接受为标准，MD5 算法是 MD4 算 法的改进。MD5 和 MD4 算法都是将消息划分成 512 位的消息块进行处理，最终形 成 128 位的信息摘要。 实现 MD5 算法主要经过以下五个步骤： (1) 补位 补位的目标是使输入的消息长度，从任意值变成一个新的长度 n，使得 n=448(mod512)，即通过补位使消息长度差 64 位成为 512 的整数倍，即使原消息 的长度正好满足要求，也需要进行补位。补位的补丁包括一个 1，剩下的全是 0，在原消息之后。特别地，如果原消息的长度正好满足要求，则补位包括一个 1 和 512 个 0。 算法实现 12 (2) 追加长度 在追加长度前，通过补位，消息长度已经变成模 512 余 448，接下来的追加 长度将在消息后继续补充 64 位的信息，新消息将是 512 的整数倍。追加长度的 信息由 64 位表示，被追加到已补的信息后，如果原消息长度超过 64 位，只使用 低 64 位。追加的长度是原消息的长度，而不是补位后的信息长度。 (3）缓冲区初始化 为了计算 Hash 函数的结果，需首先设置 128 位的缓冲区。缓冲区除接受 Hash 函数最终结果外，还记录中间结果。 在图 3-2 中，将缓冲区分成 4 等份，即 4 个 32 位寄存器（A，B，C，D） ，每 个 32 位寄存器也被称为字。 第一轮 第二轮 第三轮 第四轮 + A 512 位 位 BCD A B C D A B C D + + + + S CLS S CLS Mk Ti 图 3-2 缓冲区 n-n+1 示意图 图 3-3 四轮算法 赋初值： A: 0 x B: 0 x89abcdef C: 0 xfedcba98 D: 0 x ABCD 构成 buffer0。 （4）消息迭代 从 buffer0 开始，进行算法的主循环，循环的次数是消息中 512 位消息分组 Buffer n Block n 128 位 位 128 位 位Buffer n+1 算法实现 13 的数目，将上面四个变量复制到另外的变量中：A 到 a,B 到 b，C 到 c，D 到 d。 主循环有四轮，每轮很相似，每一轮进行 16 次操作，每次操作对 a,b,c 和 d 中 的其中三个作一次线性函数运算，然后将所得的结果加上第四个变量，文本的一 个子分组和一个常数，再将所得的结果向右环移一个不定的数，并加上或中之一， 最后用该结果取代 a,b,c 或 d 中之一。主循环的运算过程见图 3-4。 第一轮第二轮第三轮第四轮 消息分组 A B C D D C B A 图 3-4 MD5 主循环 在四轮运算中,有四种函数，分别为 F(X,Y,Z),G(X,Y,Z),H(X,Y,Z)和 I(X,Y,Z)： F(X,Y,Z)=(X and Y) or (not (X) and Z) G(X,Y,Z)=(X and Z) or (Y and not (Z) H(X,Y,Z)=X xor Y xor Z I(X,Y,Z)=Y xor (X or not(Z) 这些函数是这样设计的：如果 X，Y 和 Z 的对应位是独立和均匀的，那么 结果的每一位也应是独立和均匀的。函数 F 是按逐位方式操作：如果 X，那么 Y，否则 Z。函数 H 是逐位奇偶操作符。 设 Mj 表示消息的第 j 个子分组（从 0 到 15） ，s 表示循环左移 s 位， 则四种操作为： 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) II(a,b,c,d,Mj,s,ti)表示 a=b+(a+(I(b,c,d)+ Mj + ti)s) 这四轮（64 步）是： 第 1 轮： FF (a, b, c, d, M 0, 11, 0 xd76aa478); 算法实现 14 FF (d, a, b, c, M 1, 12, 0 xe8c7b756); FF (c, d, a, b, M 2, 13, 0 xdb); FF (b, c, d, a, M 3, 14, 0 xc1bdceee); FF (a, b, c, d, M 4, 11, 0 xf57c0faf); FF (d, a, b, c, M 5, 12, 0 x4787c62a); FF (c, d, a, b, M 6, 13, 0 xa); FF (b, c, d, a, M 7, 14, 0 xfd); FF (a, b, c, d, M 8, 11, 0 xd8); FF (d, a, b, c, M 9, 12, 0 x8b44f7af); FF (c, d, a, b, M10, 13, 0 xffff5bb1); FF (b, c, d, a, M11, 14, 0 x895cd7be); FF (a, b, c, d, M12, 11, 0 x6b); FF (d, a, b, c, M13, 12, 0 xfd); FF (c, d, a, b, M14, 13, 0 xae); FF (b, c, d, a, M15, 14, 0 x49b40821); 第 2 轮： GG (a, b, c, d, M 1, 21, 0 xf61e2562); GG (d, a, b, c, M 6, 22, 0 xc040b340); GG (c, d, a, b, M11, 23, 0 x265e5a51); GG (b, c, d, a, M 0, 24, 0 xe9b6c7aa); GG (a, b, c, d, M 5, 21, 0 xd62f105d); GG (d, a, b, c, M10, 22, 0 x); GG (c, d, a, b, M15, 23, 0 xd8a1e681); GG (b, c, d, a, M 4, 24, 0 xe7d3fbc8); GG (a, b, c, d, M 9, 21, 0 x21e1cde6); GG (d, a, b, c, M14, 22, 0 xc33707d6); GG (c, d, a, b, M 3, 23, 0 xf4d50d87); GG (b, c, d, a, M 8, 24, 0 x455a14ed); GG (a, b, c, d, M13, 21, 0 xa9e3e905); GG (d, a, b, c, M 2, 22, 0 xfcefa3f8); GG (c, d, a, b, M 7, 23, 0 x676f02d9); 算法实现 15 GG (b, c, d, a, M12, 24, 0 x8d2a4c8a); 第 3 轮： HH (a, b, c, d, M 5, 31, 0 xfffa3942); HH (d, a, b, c, M 8, 32, 0 x8771f681); HH (c, d, a, b, M11, 33, 0 x6d9d6122); HH (b, c, d, a, M14, 34, 0 xfde5380c); HH (a, b, c, d, M 1, 31, 0 xa4beea44); HH (d, a, b, c, M 4, 32, 0 x4bdecfa9); HH (c, d, a, b, M 7, 33, 0 xf6bb4b60); HH (b, c, d, a, M10, 34, 0 xbebfbc70); HH (a, b, c, d, M13, 31, 0 x289b7ec6); HH (d, a, b, c, M 0, 32, 0 xeaa127fa); HH (c, d, a, b, M 3, 33, 0 xd4ef3085); HH (b, c, d, a, M 6, 34, 0 xe4881d05); HH (a, b, c, d, M 9, 31, 0 xd9d4d039); HH (d, a, b, c, M12, 32, 0 xe6db99e5); HH (c, d, a, b, M15, 33, 0 x1fa27cf8); HH (b, c, d, a, M 2, 34, 0 xc4ac5665); 第 4 轮： II (a, b, c, d, M 0, 41, 0 xf); II (d, a, b, c, M 7, 42, 0 x432aff97); II (c, d, a, b, M14, 43, 0 xab9423a7); II (b, c, d, a, M 5, 44, 0 xfc93a039); II (a, b, c, d, M12, 41, 0 x655b59c3); II (d, a, b, c, M 3, 42, 0 x8f0ccc92); II (c, d, a, b, M10, 43, 0 xffeff47d); II (b, c, d, a, M 1, 44, 0 x85845dd1); II (a, b, c, d, M 8, 41, 0 x6fa87e4f); II (d, a, b, c, M15, 42, 0 xfe2ce6e0); II (c, d, a, b, M 6, 43, 0 xa); II (b, c, d, a, M13, 44, 0 x4e0811a1); 算法实现 16 II (a, b, c, d, M 4, 41, 0 xf7537