线 性 同 余 余伪随机发生器在数字图像置乱中的应用研究 伪 随 机 发 Ａｐｐｌｉｃａｔｉ０ｎ Ｒｅｓｅａｒｃｈ ０ｆ Ｌｉｎｅａｒ Ｃ０ｎｇｒｕｅｎｔｉａｌ Ｐｓｅｕｄｏ Ｒａｎｄｏｍ Ｎｕｍｂｅｒ Ｇｅｎｅｒａｔｏｒ ｉ ｎ Ｄｉｇｉｔａｌ Ｉｍａｇｅ Ｓｃｒａｍｂｌｉｎ９ 生 器 在 徐凯 数 字 Ｘｕ Ｋａｉ 图 （贵州师范大学职业技术学院，贵州贵阳５５００１４） 像 置 （Ｃｏｌｌｅｇｅ ｏｆ Ｖｏｃａｔｉｏｎ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕｉｚｌｉｏｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕｉｚｈｏｕ Ｇｕｉｙａｎｇ ５５００１４） 乱 中 的 摘要：本文提出了一种新的数字图像置乱算法，采用线性同余伪随机数发生器技术，根据ＲＧＢ图像像素值的特性，计算 应 出ＬＣＧ迭代公式中ｍ的值及其原根ａ，并通过实验得出置乱的最小正周期Ｔ。结果表明，该算法置乱效果显著，作为图像隐藏的 用 研 预处理和后期处理是一种良好的方法。 究 关键词：图像置乱；数字图像；线性同余；伪发生器 中图分类号：ＴＰ３０９．２ 文献标识码：Ａ 文章编号：１６７１－４７９２－（２０１０）５—００９１－０３ Ａｂｓｔｒａｃｔ：Ａ ｎｅｗ ｓｃｒａｍｂｌｉｎｇ ａｌｇｏｒｉｔｈｉｎ ｏｆ ｄｉｇｉｔａｌ ｉｍａｇｅ ｂａｓｅｄ ｏｎ ｔｈｅ ｔｅｃｈｎｏｌｏｇｙ ｏｆ ｌｉｎｅａｒ ｃｏｎｇｒｕｅｎｔｉａｌ ｐｓｅｕ－ ｄｏ ｒａｎｄｏｍ ｎｕｍｂｅｒ ｇｅｎｅｉ、ａｔｏｒ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｅ ｐａｐｅｒ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｃｈａｒａｃｔｅｒ ｏｆ ＲＧＢ ｉｍａｇｅ． “ｎ１”ａｎｄ ｏｒｉｇｉ— ｎａｌ ｒｏｏｔ： ａ ｏｆ’ＬＣＧ ａｒｅ ｃａ］ｃｕｌａｔｅｄ．ａｎｄ ｔｈａｔ ｔｈｅ ｌｅａｓｔ ｐｅｒｉｏｄ“Ｔ”ｏｆ ｓｃｒａｍｂ１ｉｎｇ ｉｓ ｆｉｎｄｅｄ ｉｎ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ． Ｔｈｅ ｒｅｓｕｌｔ ｐｒｏｖｅｄ ｔｈａｔ ｔｈｅ ｓｃｒａｍｂｌｉｎｇ ｅｆｆｅｃｔ ｊＳ ｖｅｒｙ ｇｏｏｄ ｉｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ．ａｎｄ ｍｏｒｅ ｔｈｅ ａ】ｇｏｒｉ ｔｈｍ ｉｓ ａ ｇｏｏｄ ｍｅｔｈｏｄ ｉ ｎ ｐｒｅｃｅｄｉ ｎｇ ａｎｄ ｆｉｎａｌｌｙ ｐｒｏｃｅｓｓ ｏｆ ｉｍａｇｅ ｈｉｄｉｎｇ． Ｋｅｙｗｏｒｄｓ：Ｉｍａｇｅ Ｓｃｒａｍｂｌ ｉｎｇ；Ｄｉ ｇｉｔａｌ Ｉｍａｇｅ；Ｌｉｎｅａ，、Ｃｏｎｇｒｕｅｎｔｉａｌ；Ｐｓｅｕｄｏ Ｒａｎｄｏｍ Ｎｕｍｂｅｒ Ｇｅｎｅｒａｔｏｒ ０引言 式（Ｉ）中有三个参数ａ、ｃ、ｍ，其中ｍ是一个素数，ａ是ｍ 随着Ｉｎｔｅｒｎｅｔ技术的迅速发展，图像成为互联网上表 的一个原根，ｃ［０，ｍ］。ａ、ｃ、ｍ分别叫乘数、增量和模。假设存在 达和传输信息的一种重要载体，其安全性问题日益受到人们 一个最小正数Ｔ，使得对于任意一个ｊ，有ｘｉ＋ｒ＝Ｘ 成立，则Ｔ 的关注，数字图像的置乱和隐藏成为信息安全技术中的一个 为伪随机数发生器的最小正周期。 研究热点。图像置乱变换是一种重要的图像加密技术，目前 由Ｅｕｌａｒ定理： 使用较多的图像置乱方法主要有：Ａｒｎｏｌｄ变换、幻方变换、 ａ ｛ －Ｉｌ（ｏｔ ｏ ｍ： ｉ＝ｍ，２－…１ 一２ （２） Ｈｉｌｂｅｒｔ曲线变换、Ｔａｎｇｒａｍ算法、Ｃｏｎｗａｙ游戏、Ｇｒａｙ码变换 如果ｃ＝Ｏ，由初等数论知识可知： 等方法。图像置乱可以作为图像隐藏的预处理和后处理，使 ｘ ＝ａｘ ＝ａ ＝…＝ａ．￣Ｉｘ。＝ｘ。（ｍｏｄ ｍ） （３） 保密图像更加不宜被敌方发觉和破译“ 。 基于这一思想，得到线性同余的最一般应用式： 本文提出一种新的图像置乱算法：基于线性同余伪随机Ｘｉ＋ＩＴ－－ａｘ （ｍｏｄ ｍ） （４） 发生器的图像置乱算法。实验结果表明，该算法与传统的图 ２置乱算法 像置乱算法相比，更加适用于图像文件的加密传输和秘密图 在ｕｉｎｔ８类型的ＲＧＢ数字图像中，ｍ取２５５，其原根为８， 像信息在数字水印技术中的置乱预处理，而且对图像的处理 即ａ＝８。则： 具有良好的鲁棒性。ｘｉ＋ｔ＝８ｘ （ｍｏｄ ２５５） （５） １线性同余伪随机数发生器 设原始图像为Ｍ，置乱后的图像为Ｎ，假设Ｘ 为置乱前的 目前，应用最为广泛的均匀分布伪随机数发生器是线性 图像，Ｘ 为置乱后的图像，ｉ表示迭代的次数，根据式（５）对 同余发生器（Ｌｉｎｅａｒ Ｃｏｎｇｒｕｅｎｔｉａｌ Ｐｓｅｕｄｏ Ｒａｎｄｏｍ Ｎｕｍｂｅｒ 图像进行置乱，有： Ｇｅｎｅｒａｔｏｒ，ＬｃＧ）Ｉｓ］，ＬＣＧ的迭代公式描述为： Ｎ，＝８Ｍ （ｍｏｄ ２５５）： Ｘｌ￣ｌ＝（ａｘ。＋ｃ）（ｍｏｄ ｍ） （１） 算法１：图像置乱算法 ９１ ～ Ｓｔｅｐ １：计算满足式（４）的最小正周期Ｔ； Ｓｔｅｐ ２：读取原始图像Ｍ； Ｓｔｅｐ ３：用ＲＮ＝８ＲＭ（ｍｏｄ ２５５）、ＧＮ＝８ＧＭ（ｍｏｄ ２５５）、ＢＮ－－ＳＢＭ （ｍｏｄ ２５５）对Ｍ的图像数据进行ｉ次置乱；・ Ｓｔｅｐ ４：由置乱后的数据ＲＮ、ＧＮ和ＢＮ生成图像Ｎ。 ７７：—ｒＩＭＮ —（６） 式（６）中，ｎ 表示Ｍ、Ｎ中对应图像数据的像素值相同的 个数，ｎ表示图像数据像素的总数。１＂１∈【０，１】，当ｎ＝１时， 表示两幅图像完全相同，反之，表示两幅图像完全不相同，ｎ 值越小，置乱程度越大。 算法２：图像还原算法 Ｓｔｅｐ １：由Ｔ－ｉ（ｍｏｄ Ｔ）计算出还需置乱次数ｊ； Ｓｔｅｐ ２：读取置乱后的图像Ｎ： 在ｕｉｎｔ８的ＲＧＢ图像中，像素值是０到２５５之间，于是 实验先对０—２５５中的数据按照式（５）进行迭代，当ｉ＝（ｎ－１） 。８，ｎ为正整数时，均能还原原始数据，说明８为最小正周 期。 Ｓｔｅｐ ３：按算法１中的Ｓｔｅｐ３对图像数据进行Ｊ次置 乱，得到数据Ｎ’； Ｓｔｅｐ ４：由Ｎ’生成原始图像Ｍ’。 ３实验结果分析 图一是大小为１００×１００的ｕｉｎｔ８类型的ＲＧＢ图像，（ｂ） 到（ｈ）是按公式（４）对（ａ）进行置乱后的图像。其中（ａ）为置乱 前的图像，（ｂ）到（ｈ）分别为置乱１次、２次、４次、７次、８次、 １Ｏ次、３１次后的图像。从图一可以看出，当ｉ－－８时，置乱后的 ３．１图像的置乱 定义：相似度 如果图像Ｍ和图像Ｎ的大小相同，则Ｍ和Ｎ中对应像素 值相同的个数之和与总像素之比称为两幅图像的相似度，用 公式表示如下： 图像和原始图像完全相同；ｉ：２和ｉ＝１０时，置乱的图像相 同；ｉ＝７和ｉ＝３１时置乱的图像相同。实验证明，算法１对图 像置乱具有周期性。在本例中，最小正周期Ｔ为８。 ■圈圈圈 圈■圈圈 （ｅ）ｉ－－ｑ 图一原始图像和置乱后的图像 分析表一，图像置乱了１次之后，图像的质量受到不同 图二表示置乱次数和相似度之间的关系，其中Ｘ表示置 乱的次数，Ｙ表示相似度，从该图也证明算法１的正确性。 程度的破坏，其近似度的值与图像的大小、图像的类型和像 素值都有一定的关系，说明算法１可以针对不同类型的ＲＧＢ 图像均可进行置乱。 表一田健类型 ＢＭＰ ｌ一 图像类型、大小、置乱次数和相似度之间的关系 豳像大小 １００×Ｉ∞ ｉ鲐×ｌ，０ 置乱Ｉ敖 ｎＯＩ６９ ｎＯ口，， ＯＯＩ１９ 置乱２次 ｎ０２６ｏ 置乱７度 ｎｏ２６０ ｎＭ， ｎＯＩＪ＇ 量乱Ｉ敬 Ｉ．㈣ 置乱ｌ。攻 Ｏ．蝴 置乱，ｌ冼 “ｏ瑚 ｎ∞，】 “ＯｌＩ’ 一、 、—一 Ｌ—／ 一 — ／＼～ —／、一一一 ｎＯｌ３ｌ ＯＯ Ｏ．ＯｌＩ， ＰＣＸ ｌ∞ｘＩ∞ 图二置乱次数与相似度关系图 ｍ０Ｉ＂ ３．２图像的还原 像。该算法可以用来作为数字图像隐藏和伪装的预处理和后 图像被置乱后，只需知道置乱的次数和周期Ｔ即可还原 处理阶段［６－￣１。 图像。根据算法２，式（７）给出了还原原始图像还需将图像置 乱的次数ｔｊ、周期Ｔ和已置乱次数ｉ之间的关系。 参考文献 ｆ ７’一ｉ（ｉ＜７’） ［１】郑文斌．基于ｚｉ ｇ—ｚａｇ扫描的空域图像置乱新算法 ．，＝｛Ｔ（ ＝Ｔ） （７） 【Ｊ］．计算机工程与科学，２００９，３１（７）：２８－４１． Ｉ Ｔ一（，ｏｒｏｄ Ｔ）（ｉ＞Ｔ） ［２］邱炳城，姚仰新等．用小波变换和混沌映射实现图像 图三中的（ａ）是原始图像，（ｂ）是被置乱了３６次的图像， 置乱【Ｊ］．计算机工程与应用，２００９，４５（１１）：１０２—１０３． 周期Ｔ为８。根据式（７），还原原始图像还需置乱的次数Ｊ为 【３］李涛。柳健．基于位平面与｝昆沌系统的图像置乱方法 ８－（３５ ｍｏｄ ８）＝５次。（ｃ）是再次置乱了５次的图像，从（ａ）和 ［Ｊ］．西南民族大学学报：自然科学版，２００９，３５（３）：５９５－５９９． （ｃ）可以看出，两幅图像完全相同，同时验证了算法２的可行 ［４］柏森，曹长修，曹龙汉．基于骑士巡游变换的图像细 性和正确性。 节隐藏技术［Ｊ］．中国图像图形学报，２００１，６（１１）：１０９６－１１００． 【５】王丽娜，郭迟等．信息隐藏技术实验教程［Ｍ］．武汉： 武汉大学出版社，２００４：２６～２７． 圈圈圈 ［６】林雪辉．一种基于二叉树遍历的数字图像置乱方法 【Ｊ］．计算机工程，２００６，３２（１６）：１３９—１４７． ［７］ＨＵＡＮＧＦＡＮＧＪＵＮ，ＧＵＡＮＺＨＩＨＯＮＧ．ｃｒｙｐｔｏｓｙｓｔｅｍｕｓｉｎｇ— ｃ—ｈａｏｔｉｃｋｅｙｓ【ＪＪ，Ｃｈａｏｓ，ｏｌｉｔｏｎｓａｎｄＦｒａｃｔａｌｓ，２００５：８５１— ８５５． （ａ）原始图像 （ｂ）置乱３６次的图像（ｃ）置乱４ｏ次后 的图像 【８］ＧＡＯ，ＨＡＯＪＩＡＮＧ，ＺＩＩＡＮＧＹＩＳＨＥＮＧ，ＬＩＡＮＧ，ＳＨＵＹＵＮ，ｅｔａ１． 图三图像的还原 Ａｎｅｗｃｈａｏｔｉｃａｌｇｏｒｉｔｈｍ ｆｏｒｉｍａｇｅｅｎｃｒｙｐｔｉｏｎ ［Ｊ］．Ｃｈａｏｓ－ Ｓｏｌｉｔｏｎｓａｎ Ｆｒａｃｔａｌｓ，２００６：３９３－３９９． ４结束语 作者简介 本文提出了一种基于线性同余的伪随机数发生器图像 徐凯（１９７９．－），男，汉族，贵州省贵阳市人，贵州师范大 置乱算法，根据ＲＧＢ图像的性质，确定ｍ及其原根ａ的值。实 学职业技术学院讲师，硕士，主要研究方向：多媒体技术，信 验证明，算法对图像的置乱具有周期性，可以针对不同类型、 息隐藏，数字图像处理。 不同大小的ＲＧＢ图像进行置乱，而且很容易还原出原始图 线性同余伪随机发生器在数字图像置乱中的应用研究
