随机矩阵

　第 5 卷第 1 期2006 年 2 月 　 　　 江 南 大 学 学 报 (自 然 科 学 版) Journal of Southern Yangtze University( Natural Science Edition) 　　 　 Vol. 5 　No. 1 Feb. 　2006 　文章编号 :1671 - 7147 (2006) 01 - 0006 - 04 　　收稿日期 :2005 - 01 - 07 ; 　修订日期 :2005 - 07 - 13. 　　基金项目 : 国家自然科学基金(天元基金)项目(10226028) ;福建省泉州市科技重点项目(2004g27) . 　　作者简介 : 陈燕梅 (1981 - ) ,女 ,福建漳州人 ,应用 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 专业硕士研究生. 　　3 通讯联系人 : 张胜元 (1966 - ) ,男 ,福建连城人 ,副教授 ,理学博士 ,硕士生导师. 主要从事密码学与信息安全等 研究. Email : syzhang @21cn. com 基于一类随机矩阵的数字图像置乱新方法 陈燕梅 , 　张胜元 3 (福建师范大学 数学与计算机科学学院 , 福建 福州 350007) 摘 　要 : 以图像信息安全问题为背景 ,改进了用形式固定的矩阵对数字图像进行置乱的方法 ,提出密 钥控制下利用一类随机的上 (下)三角可逆矩阵对数字图像进行置乱与恢复的新方法. 采用此方法 ,使 图像的置乱效果与置乱次数无关且密钥空间足够大 ,而且解密是加密的简单逆过程. 结果表明 :在图 像信息隐藏中 ,这种方法能达到较好的加密与解密效果 ,易于实现并具有良好的应用价值. 关键词 : 数字图像 ;模 n 矩阵 ;模 n 矩阵的逆矩阵 ;数字图像置乱 中图分类号 : TP 391 文献标识码 : A A Novel Digital Image Scrambling Method Based on A Class of Stochastic Matrices CH EN YanΟmei , 　ZHAN G ShengΟyuan 3 (School of Mathematics and Computer Science , Fujian Normal University , Fuzhou 350007 , China) Abstract :Faced wit h t he security p roblem of image information. The paper p resent s a digital image scrambling met hod which uses fixed form mat rices restores digital images by means of a class of stochastic upper or lower t riangular invertible mat rices under t he cont rol of secret key. Adopting t his met hod , the effect s of image scrambling have no relations wit h t he scrambling times ; t he space of secret key is large enough ; decryption is t he simple reversed process of encryption. The result s show t hat in image information hiding this met hod can reach preferable effect s of encryption and decryption. The new met hod is easy to realize and has application value. Key words : digital image ; modal n mat rix ; inverse mat rix of modal n mat rix ; digital image scrambling 　　随着网络技术的高速发展 ,大量个人和公众的 信息经过网络传播 ,使得信息安全显得日趋重要. 传统的保密学尚缺少对图像安全性足够的研究. 目 前已有的几种数字图像置乱方法 , 主要是基于 Arnold 变换的系列置乱方法 ;用分形图形学中的方 法对空间曲线填充 ,以及利用其它数学知识和奇特 现象进行数字图像置乱[1 ] . 但现有的基于矩阵的数 字图像置乱方法是采用形式固定的矩阵进行置乱 , 有一定的局限性. 本文的目的在于建立一种新算 法 ,通过对密钥的控制 ,使得用于置乱的矩阵具有 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 较大的随机性 ,从而增加了非法破译的复杂度 ,在 一定程度上提高了数字图像信息隐藏的安全性及 实用性. 1 　矩阵的模 n 逆 设 Zn ∈{ 0 ,1 , ⋯, n} ,按通常数的加、乘运算并 用 n 取模 , Zn 构成环 , 称之为模 n 剩余类环 , 且称 Mm ( Zn) 为 Zn 上的 m 阶矩阵. 定义 1 　设 a ∈Zn ,如果存在 b ∈Zn ,使得 ab = 1 , 称 a 为 Z n的可逆元[2 ] . 容易验证 a 为 Z n 中的可逆元[3 ] ,当且仅当 a与 n 互 素 ,即 ( a , n) = 1 . 定义 2 　设 A , B ∈M m ( Zn) ,若 AB = BA = Im (mod n) (其中 Im 为 m 阶单位矩阵) ,则称 B是A 对于模 n 的逆矩阵[4 ] ,记为 A- 1 ,也记作 B ≡A- 1 或 B = A- 1 . 定理 1 　Zn 中的可逆元个数即为欧拉函数φ( n) [5 ] , 设 n 的既约因子分解式为 n = P1 e1 P2 e2 ⋯, Ps es . 其 中 , P1 , P2 , ⋯, Ps 为互不相同的素数 ,则 φ( n) = n(1 - 1 P1 ) (1 - 1 P2 ) ⋯(1 - 1 Ps ) (1) 若以 N m ( n) 记 Zn 上 m 阶可逆矩阵的个数 ,则 有以下 N m ( n) 的计数公式[3 ] . 定理 2 　设 n ≥2 为整数 , n = Pr11 Pr22 ⋯Prss 为 n 的 既约因子分解 , ri ≥1 ( i = 1 ,2 , ⋯, s) , P1 , P2 , ⋯, Ps 为互异的素数 ,则 N m ( n) = ∏ s i = 1 ∏ m- 1 j = 0 ( Pmi - Pji ) Pi ( ri - 1) m 2 以下给出用行列式判断 Zn 上方阵 A 可逆的方 法[3 ] . 定理 3 　方阵 A 在 Z n 上可逆的充分必要条件是 ( A , n) = 1 . 由于 Zn 上 m 阶可逆矩阵全体关于矩阵乘法运 算构成一个有限群 (群的阶数为 N m ( n) ) ,所以 Zn 上 任意 m 阶可逆矩阵 A 都有周期 (即存在最小正整数 k ,使得 Ak = Im ) ;反之 ,若 Zn 上 m 阶方阵A有周期 , 则在 Zn 上可逆. 定理 4 　 Zn 上方阵 A 有周期的充分必要条件是 ( A , n) = 1 . 对于 Zn 上 m 阶可逆矩阵A ,可采用如下初等变 换的方法[6 ] 求出 A- 1 (mod n) . 定义3 　Zn 上方阵A的初等行 (列) 变换指的是对矩 阵施行以下变换 : 1) 交换矩阵的两行 (列) ; 2) 用一个与模 n 互素的整数乘以矩阵的某一 行 (列) 的每一个元素 ; 3) 用一个整数乘矩阵的某一行 (列) 加到另一 行 (列) ,即用这个整数乘某一行 (列) 的每一元素加 到另一行 (列) 的对应元素上. 以上的初等行变换及初等列变换统称为矩阵 的初等变换. 此初等变换相对应的有初等矩阵 , 即 施行一次初等变换得到的矩阵称为初等矩阵. 定理 5 　若模 n的 m 阶矩阵A 的行列式 ( A , n) = 1 ,则 A可经过一系列的初等变换化为单位矩阵 I[6 ] . 对于 Zn 上 m 阶可逆矩阵 A ,有 m 阶初等矩阵 E1 , E2 , ⋯, Es ,使得 Es ⋯E2 E1 A = I [ A | I ] →[ Es ⋯E2 E1 A | Es ⋯E2 E1 I ] = [ I | A- 1 ] (2) 2 　基于矩阵变换的数字图像置乱方法 一幅数字图像 P 可以看作是一个矩阵 P , 矩阵 元素所在的行与列 ,就是图像显示在计算机屏幕上 的诸像素点的坐标 ,元素的数值就是像素的灰度. 彩色图像可以取成混合矩阵 ,每个像素灰度值与红 色 ( R) 、绿色 ( G) 、蓝色 (B) 有关 ,可以用 3 个数值矩 阵 ( P R , P G , P B ) 表示. 目前数字图像置乱一般有两 种方法 :其一是像素位置的置乱 ,如基于正交拉丁 方、原根、幻方、Hilbert 曲线等数字图像的置 乱[7 ,8 ] ,这些方法的置乱效果和变换次数 k 有关 ,因 而不仅需要测试不同的变换次数以达到最优置乱 效果 ,而且要通过变换的周期使图像得以恢复 ,需 花费大量的时间 ,且较为复杂. 其二是像素值的改 变 ,此方法置乱效果较好. 如基于 Arnold 变换、 FibonacciΟQ 变换的数字图像置乱方法. 基于色彩空 间置乱的矩阵变换方法为 : 对于给定的一幅 n ×m数字图像 P ,设其像素的 灰度值矩阵为 P = ( pij ) n×m ( i , j = 1 ,2 , ⋯, n) , p ij 值 即为此图像对应位置的像素灰度值 ,并设 p ij ∈{ 0 , 1 , ⋯, N - 1} ,其中 N 为图像 P中像素灰度值的最高 级 ,通常取 N = 256 . 取 ZN 上的一个 n 阶方阵 A ,令 P′= A P ( mod N) (3) 以 P′中 P ij ′( i , j = 1 ,2 , ⋯, n) 的值作为用 A变 换一次后的置乱图像 P′对应位置的像素灰度值 (如 果 P 是彩色图像 ,则用 A 分别左乘其 3 个数值矩阵 P R , P G , P B后得到相应矩阵) . 对于置乱后的图像 , 要恢复出原始图像 , 必须 保证变换具有可逆性 ,也就是考虑变换的周期性问 题 ,即任意图像 P 经过一系列变换后可以恢复到原 始图像的最少变换次数[9 ] . 这导致诸多文献探讨矩 阵变换具有周期性的条件以及周期的估计或计算 7　第 1 期 陈燕梅等 :基于一类随机矩阵的数字图像置乱新方法 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 的算法[10～12 ] . 然而 ,在图像置乱过程中 , 目前所采用的方法 主要是以形式固定的矩阵进行置乱 ,图像的安全性 只能依赖于置乱的次数. 只要非法破译者花费一定 的运算时间 , 就很可能恢复出原始图像. 而作者设 计的这种新的数字图像置乱矩阵变换的新方法 ,既 达到很好的置乱效果 , 又保证较高的安全性 , 而且 容易实现. 3 　数字图像置乱的矩阵变换新方法 3. 1 　一类随机矩阵 克服矩阵形式固定的方法是随机生成具有周期 的矩阵.定理 2 说明这样的矩阵足够多且密钥空间 大 ,进行图像置乱加密的安全性高. 但对一个随机生 成的矩阵 ,要判断它是否有周期并计算其周期是不易 的.这将造成图像复原困难 ,不易控制.以下 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 矩阵 变换新方法 ,变换的矩阵既有较大的随机性 ,又容易 控制 ,加密与解密实现容易 ,安全性较高. 设 A 为如下形式的下 (上) 三角矩阵 A = d1 0 0 ⋯ 0 d21 d2 0 ⋯ 0 a31 a32 d3 ⋯ 0 … … … ω … an1 an2 an3 ⋯ dn (4) 或者 A = d1 a12 a13 ⋯ a1 n 0 d2 a23 ⋯ a2 n 0 d2 a23 ⋯ a2 n 0 0 d3 ⋯ a3 n … … … ω … 0 0 0 ⋯ dn n (5) 其中 aij , di ∈{ 0 ,1 , ⋯, N - 1} , i , j = 1 ,2 , ⋯, n设 n ×m 的数字图像矩阵 P = ( Pij ) n×m , Pij ∈{ 0 ,1 , ⋯, N - 1} , i , j = 1 ,2 , ⋯, n ,定义从 P 到 P′的一个变换为 P′= A P ( mod N) (6) 以式 (6) 作为数字图像置乱的矩阵变换. 由定 理 4 可得定理 6 . 定理 6 　变换式 (6) 有周期的充分必要条件是 ( di , N) = 1 , i = 1 , ⋯, n ,此时A为 ZN 上的可逆矩阵. 由于 满足 ( di , N) = 1 的 di 有φ( n) 个 ,从而引出定理 7. 定理 7 　使变换式 (6) 有周期的 A 的个数为 φ( N) n ·N n ( n - 1)2 定理 7 表明 ,可用于该置乱变换的矩阵个数已足够 保证图像置乱加密的安全性. 3. 2 　算法分析与实现 3 . 2 . 1 　算法分析 　在实现应用式 (6) 进行数字图 像置乱时 ,以下分析是重要的. 1) 根据 Kerckhoff s 准则 ,保密系统中的所使 用的加密体制和算法应当是公开的 ,系统的安全性 必须也只能依赖于密钥的选取. 对于上述矩阵 A ,可 采用线性同余算法产生随机数. 由于该算法得到的 随机数由输入的初始值 (种子) 惟一决定 ,该种子即 为用于进行图像置乱加密和解密的密钥. 由于 di ( i = 1 ,2 , ⋯, n) 应当在满足定理 6 的条件下随机 选取 ,而 aij ( i , j = 1 ,2 , ⋯, n) ,则在 Zn 中任意选取. 通常 N = 256 = 28 时 , ( di , N) = 1 , 当且仅当 di ( i = 1 ,2 , ⋯, n) 为奇数 ,这是很容易实现的. 由定 理 7 ,置乱矩阵 A 的个数为 (2 8 2 ) ·(28 ) n ( n- 1) 2 = 2n(4 n+3) 此时 , 密钥空间足够大. 如当 n = 10 时 ,2430 = 2 . 772 7 e + 129 ,已足以抵抗大量攻击. 而一般数字 水印图像的阶数 n 为 40 ～ 80 ,安全性已有保证. 2) 假设 P′是图像 P 经过式 (6) 变换一次后的 置乱图像 ,其对应的图像矩阵为 P. 由于所选取的变 换矩阵 A 是有周期的 ,因此 A在 ZN 上可逆 ,这样复 原图像只需用式 (6) 的逆变换 ,即 P = A- 1 P′(mod N) . 而 A- 1 的计算可采用初等变换的方法. 根据式 (2) 计算出该随机矩阵在模 N 下的逆矩 阵. 如果是一般的可逆矩阵 , 用初等变换的方法求 其逆矩阵较为麻烦 , 经常要用到观察法. 但对于上 (下) 三角矩阵 ,高斯消元求其逆矩阵较为简单 ,这 将大大简化程序设计 ,显然优于基于变换的周期性 的图像复原方法. 3) 对一幅数字图像 P ,进行上述变换 k 次得到 的图像 P k ,其图像矩阵 Pk = Ak P (mod N) ,由于上 (下) 三角矩阵的乘积仍为上 (下) 三角矩阵 ,且 Ak 与 A 具有相同的类型 ,因此变换 k 次和变换 1 次的 置乱效果应当是大致相同的. 试验证明 ,的确如此 , 见图 1 . 因此在设计算法时 ,只作一次变换. 对于以上算法 ,可在 Matlab 6. 5 上编程实现 ,置 乱效果见图 1.结果表明 :在图像信息隐蔽中 ,这种技 术能达到较好的加密与解密效果. 3. 2. 2 　基本流程 　图像加密与复原见图 1 . 1) 图像加密 ①读入图像信息 ,将 R GB 值存至 pic[ ] n = 矩 阵 pic 的行数 , m = 矩阵 pic 的列数. 　　②输入密钥 Key ,以 Key 做为种子 ,采用线性 8 　　　江 南 大 学 学 报 (自 然 科 学 版) 　　　　　　　　　　　第 5 卷 　 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 图 1 　图像的置乱与恢复 Fig. 1 　Image scrambling and restoring 同余法产生随机数 aij , di ∈{ 0 ,1 , ⋯, N - 1} , i , j = 1 ,2 , ⋯, n ,其中 di ( i = 1 ,2 , ⋯, n) 为奇数 ,得到随机 的上 (下) 三角矩阵 A. 　　③置乱 :pic = A ×pic ( mod 256) . ④输出置乱图像. 2) 图像复原 ①读入图像信息 ,将 R GB 值存至 pic[ ] n = 矩 阵 pic 的行数 , m = 矩阵 pic 的列数. ②输入密钥 Key ,以 Key 做为种子 ,产生随机 数 aij , di ∈{ 0 ,1 , ⋯, N - 1} , ( i , , j = 1 ,2 , ⋯, n) 和 随机矩阵 A ,由程序计算 A- 1 . ③复原 :pic = A- 1 ×pic ( mod 256) . ④输出复原图像. 4 　结　语 　　数字图像置乱技术 ,可以看作数字图像加密的 一种途径 ,也可以用做数字图像隐藏、数字水印图 像植入、数值计算恢复方法和数字图像分存的预处 理和后处理过程[ 13 ] . 现有的基于矩阵变换的数字图 像置乱方法 ,主要是采用形式固定的矩阵进行置 乱 ,置乱效果与变换次数有关 ,且通常利用变换的 周期性恢复出原始图像 ,其安全性不够高. 文中采用改变图像像素值的方法 ,提出了用一 类随机上 (下) 三角矩阵对数字图像进行置乱与恢 复的新方法. 这类矩阵变换具有可逆性 ,容易通过 求其逆变换达到对图像的恢复 ,而且随机数由用于 加密与解密的密钥控制 , 加密与解密的算法完全公 开. 这种方法算法简单 ,实现容易 ,既能达到很好的 图像置乱效果 ,又能方便地进行解密 ,恢复出原始 图像 ,将会有很好的应用前景. 然而 ,这种方法在抗 攻击 (如局部破损 ,有损压缩等) 方面还存在一定缺 陷 ,仍需进一步研究改进. 参考文献 : [ 1 ] 闫伟齐 ,邹建成 ,齐乐旭. 一种基于 DES 的数字图像置乱新方法[J ] . 北方工业大学学报 ,2002 ,14 (1) :1 - 7. [ 2 ] 辛林 ,陈清华 ,戴跃进 ,等. 近世代数[ M ] . 北京 :当代中国出版社 , 2000. [ 3 ] 张胜元. Zn 上 m 阶可逆矩阵的计数[J ] . 福建师范大学学报 :自然科学版 ,1999 , 15 (1) : 13 - 15. [ 4 ] 于秀源 ,薛昭雄. 密码学与数论基础[ M ] . 济南 :山东科学技术出版社 ,1993. [ 5 ] 卢开澄. 组合数学 (第 2 版) [ M ] . 北京 :清华大学出版社 , 1991. [ 6 ] 党宝栋. 关于模 矩阵的逆矩阵[J ] . 沈阳师范学院学报 :自然科学版 ,2000 ,18 (4) :1 - 6. [ 7 ] 李国富. 基于正交拉丁方的数字图像置乱方法[J ] . 北方工业大学学报 ,2001 , 13 (1) :14 - 16. [ 8 ] 邹建成. 基于原根的数字图像置乱技术[J ] . 北方工业大学学报 ,2001 , 13 (3) :6 - 8. [ 9 ] 齐东旭 ,邹建成 ,韩效宥. 一类新的置乱变换及其在图像信息隐蔽中的应用[J ].中国科学 : E辑 , 2000 ,30 (5) : 440 - 446. [10 ] 丁玮 , 闫伟齐 ,齐东旭. 基于 Arnold 变换的数字图像置乱技术[J ]. 计算机辅助设计与图形学学报 , 2001 ,13 (4) : 339 - 34. [11 ] 邹建成 ,铁小匀. 数字图像的二维 Arnold 变换及其周期性[J ]. 北方工业大学学报 , 2000 , 12 (1) : 10 - 14. [12 ] 王道顺 ,杨地莲 ,齐东旭. 数字图像的两类非线性变换及其周期性[J ]. 计算机辅助设计与图形学学报 ,2001 , 13(9) : 828 - 833. [13 ] 邹建成 ,李国富 ,齐东旭.广义 Gray 码及其在数字图像置乱中的应用[J ].高校应用数学学报 :A 辑 ,2002 ,17 (3) :363 - 370. (责任编辑 :彭守敏) 9　第 1 期 陈燕梅等 :基于一类随机矩阵的数字图像置乱新方法 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net