摘要：提出rmsp(random matrix sequence permutation)方法，同时完成帧内宏块(macroblock，mb )之间、块内vlc(variable length coding)码字之间双重互补的乱序加密，并利用随机序列生成随机乱序密钥矩阵序列，供每帧和每块依次用不重复的密钥矩阵对mb和vlc码字乱序。rmsp方法完全保持编码格式和压缩率，具有对应序列密码的抗攻击能力且明文信息完全隐藏的特点，速度快约四倍，适用于mpeg、h.26x及jpeg等主流编码信号加密，可制作单独模块。
关键词：视频加密；变长编码码字乱序；宏块乱序；密钥矩阵序列
图像和视频应用日益广泛，使得实用图像和视频加密技术越来越重要。视频加密的评价较之通用密码体制具有新的要求：应具备足够的抗攻击能力、视觉信息应被充分隐藏。同时，由于视频数据量大、结构性强等特征，实用加密方法的计算速度、对编码格式和压缩率的影响等指标也很重要。
视频密文保持编码格式十分重要。格式信息在存储、传输和在线处理过程中具有重要作用，如实现检索、暂停、快进、快退等交互功能和qos保障作用，提高容错能力和网络适应性。付费视频等商业应用往往需要非授权用户能顺利解码密文却得不到所需视频信息，从而破坏了编码格式，使这些用户因不能识别或解码死机，误认为是线路或软硬件故障，妨碍业务开展；格式被破坏的视频数据可能更容易引起注意，增加遭到攻击和被破译的机会，而对不含视频源信息的长零串等公开的特殊规则序列加密，既为明文攻击提供了便利，也浪费了计算资源。WWw.133229.Com
直接密码方法将视频当做普通流用分组密码、序列密码等加密，安全且易实现[1,2]，但往往不能同时满足视频数据安全、实时和传输处理等实用需要，在很多场合不适用。其最难克服的缺陷是破坏编码格式。vlc码字作为编码视频数据中的重要成分必须重点加密，而有效的vlc码字远未遍历对应比特码空间。直接使用密码加密，必然随机产生大量非法的vlc码字，密文不可能符合编码格式。因此寻求vlc码字的理想加密方法是一个急需研究的课题。
1现有的方法
近年针对视频加密进行了大量研究，提出很多各有不同优缺点的方法[2]，但仍很难解决vlc码字加密的难题。现有针对vlc码字的视频加密方法大致分为：①dct系数乱序(zig－zag permutation)[3]。其速度快，但乱序表固定或有限，对明、密文攻击都脆弱[1]，且大幅降低了压缩率[2]；块置乱(block shuffling)和块旋转(block rotation)[4]同样对明、密文攻击脆弱。由于没有加密宏块的运动矢量，视频的运动信息非常清楚，同时子带乱序[4]方式也降低了压缩率。②改变huffman码表方法[5,6]。它不增加处理负担(lightweight)，可以不降低压缩率，但因密钥空间受限而降低了安全性，且产生密钥困难[5,6]；密钥码表固定，不能抵抗明文攻击；码字出现依长度具有统计规律，便于唯密文分析。③vlc码字映射成定长索引加密[7,8]。其增加了加密比特数即计算量；不同长度码字统一处理(可为多个vlc码字数是2的幂的子集)，降低了压缩率。④随机改变vlc码字符号位[9,10]。它不降低压缩率，但加密信息量过少，安全性不高。这些方法虽能保持编码格式，但均存在明显缺陷，实验还表明它们的视频信息隐藏效果不够。
本文提出利用密钥矩阵序列随机改变乱序表的视频乱序加密方法(random matrix sequence permutation，rmsp)，通过帧内mb乱序来加密视频画面形状和帧间运动信息，通过块内vlc码字乱序来加密纹理细节信息，两者结合使明文视频信息完全隐藏；再由随机序列构造乱序密钥矩阵序列，通过使用每次随机变化的乱序表，使乱序接近一次一密的安全强度。rmsp方法速度快、完全保持编码格式、不降低压缩率，能同时满足安全、实时、传输处理、码流带宽等多项实用要求。
2基于密钥矩阵序列的变模乱序算法
乱序是保持明文的基本元素(如文本的字符、数据的比特位)相同，但顺序被打乱。利用乱序算法的特点，以vlc码字为基本元素而在加密时保证相同，就很容易保证vlc码字合法有效，解决格式兼容问题。由于视频信号数据量大，rmsp以帧为分组对mb乱序、以块为分组对vlc码字乱序，均便于操作。但每帧mb个数和每块vlc码字数都不固定，即每组元素个数不断变化。乱序分组的元素个数称为模数，模数可变的乱序称为变模乱序。
2．1乱序算法描述
2．3由随机序列生成乱序矩阵序列
一次一密被证明是绝对安全的密码体制，给序列密码的研究和应用以强大支持，并取得了不少高性能密钥序列的研究成果[11]。这些序列虽不能直接用于rmsp，但其随机性成果可以利用。rmsp设计了一种由随机序列构造变模乱序矩阵序列用于变模乱序的算法。
3rmsp算法及实现
rmsp方法同时使用mb乱序加密形状与vlc码字乱序加密纹理实现互补，达到完全隐藏画面视觉信息和互相消除相关性的效果，使用随机乱序矩阵序列实现一次一密。其增加计算量不多，可满足实时应用。
3．1mb乱序
当前广泛应用的编码标准的视频数据呈层次结构，每帧划分为16×16像素的宏块mb并按顺序传输，接收方按此逐块解码恢复原视频。若以每帧分组，以mb为基本元素乱序，速度快、不降低压缩率、完全保持编码格式，非法接收方也能正常解码，但原视频的形状信息被隐藏。块间差分的dc和预测帧运动矢量同时得到加密，pb帧密文完全不能理解。 mb乱序加密形状效果很好，但没有加密纹理细节。mb乱序效果如图1(b)所示。由于ac没有加密，mb内纹理可辨，尤其如边界清楚的数字、字母等。将各块差分dc置零(即dc为常数)时如图1(c)所示。为更清楚说明问题，图1(d)所示为破译了dc时的情况。相邻mb的边界像素值相关，dc加密使相邻边界像素值变得不相等，但其差值仍接近相等，这个未被加密的相关性为用拼接方法破译i帧提供了足够的条件。破译i帧就得到了主要视频信息，所以单独的mb乱序不安全，易被破译。
3．2vlc码字乱序
帧内压缩主要基于dct和vlc等。数据一般分成8×8像素块(block)，经dct得到8×8系数块。每个宏块包括四个亮度块和两个色差块。一般将游程编码与熵编码结合进行。每一非零dct系数对应一个event(last,run,level)，各event查表得到vlc码字并顺序传输。
在每块中将vlc码字作为基本元素乱序。若块尾(最后一个)vlc码字改变位置，则将其(last)置零，而让乱序密文的块尾vlc码字改为对应last=1的码字。
该算法加密纹理效果好，画面细节、数字、字母等都无法识别，速度快，保持编码格式，也不降低压缩率。但是密文画面的轮廓可能很清楚，图2为仅采用vlc码字乱序的效果。
3．3两种乱序的同步实现算法
在rmsp中，mb乱序以帧(frame)分组，vlc码字乱序以块分组，对应以mb和vlc码字为元素。mb乱序和vlc码字乱序结合进行，先分析一帧编码流并生成mb乱序密钥矩阵，按矩阵找到各宏块。针对其六个块生成vlc码字乱序密钥矩阵，按矩阵输出各vlc码字。
本文原文
在视频编码数据流中：①每帧编码宏块数和每块vlc码字数不恒定，因此每分组要产生相应不同阶数的密钥矩阵；②每元素的数据长度也是变化的，因此定义指示元素数据的结构，并用结构数组指示每分组的元素数据的起点和长度。
(4)mb直接送回缓冲区排队。
(5)分别对六个块执行vlc码字乱序。生成vlc码字乱序密钥矩阵并按元素指示将vlc码字送回缓冲区重新排队。每块若最后一个码字参与了乱序，则其对应last=1要换为对应last=0的码字；将乱序后的最后码字(对应last=0)换为对应last=1的码字。
(6)对mb乱序矩阵下一元素，重复执行(3)~(5)，送出最后一个mb。
(7)返回第(1)步读下一帧数据。
接收方解密时只要将乱序密钥矩阵改为解乱密钥矩阵即可，其余算法相同。
4rmsp方法的性能分析
4．1加密效果
rmsp加密clairec、mobile序列后再按标准解码。i帧画面分别如图3(a)、(c)所示；预测帧效果分别如图3(b)、(d)所示，完全不能得到原视频信息。
4．2常规攻击方法
由于视频数据量大，rmsp又采用一次一密方式，只要选用足够随机的密钥流，常规攻击方法很难破译。穷举攻击几乎不可能，仅考虑对单帧的攻击情况。由于预测帧(pb帧)解码离不开参考帧(最终依靠i帧)，攻击者必先破译i帧。i帧cif方式有396个编码宏块，qcif方式有99个，分别有396！和99！种排序。qcif预测帧最少约20个编码宏块，在已破译i帧的前提下还有20！>>257种排序方式。
破译少量块数的块内vlc乱序没有意义。若要得到有价值的信息量，如1/3数量的块，qcif应为198块，计算量非常巨大。已知明文或选择明文攻击也无效，由于vlc码字乱序和mb乱序双重互补加密，明文和密文很难对照找出乱序表得到密钥流，即使得到部分密钥流，只要很容易地选用线性复杂度比较高的密钥流，因为每帧每块的乱序表(码本)都是不同的，就难以得到其他视频信息。
4．3特殊攻击方法
vlc码字乱序和mb乱序也在抗攻击能力上互补。纹理清楚的块组成的mb的边界特征信息丰富，便于mb拼接。但是由于vlc码字多而乱序充分难破译，无法获得mb边界相关性。vlc码字少的块容易破译，但大部分这种mb的边界信息接近，所以vlc码字乱序使攻击者难以依靠边界相关性来分析拼接乱序的mb。另一方面，mb乱序消除了邻块间vlc码字的相关性，增加了vlc码字乱序的破译难度。
mb除边界相关性之外，在全帧中的分布依画面随机不同而不同，不容易找到可利用的规律。但由于视频数据的相关性，dct系数具有分布规律。相关性强的块内像素能量集中于左上角dct系数(dc及低频ac)，使dct系数从dc到低频ac再到高频ac在三个方面呈现统计规律：①系数非零的频率由高到低；②系数绝对值由大到小；③非零系数间的间隔由小到大。块内像素变化平缓。相关性越强，这种分布规律越明显，能量越集中；反之纹理越清楚，相关性越弱，能量分散，就没有明显的规律。rmsp注重加密纹理清楚、信息量大的块，使利用这些特性的分析方法失效。
4．3．1频数分析
根据不同位置系数的非零频率不同，若乱序表固定或有限，如zigzag乱序，可通过统计各个位置出现非零系数的频率来破译。尤其容易破译dc和低频ac从而得到主要的视频信息[1]。但是rmsp每块都使用随机不同的乱序表，频数统计得不到明确的系数分布特征，无法反映其非零频率的真实分布。因此依靠频数分析的唯密文攻击难以有效实施。
由于每块乱序表不同，只要选用较高线性复杂度的密钥序列，攻击者不能由已知明文破获，就不能破译其余的视频。明文攻击显然也无效。
4．3．2幅值分析
根据ac幅值的分布规律，将系数按level从大到小排序，可以得到相关性强的块接近明文的效果。但这类块中纹理比较平缓，信息量小。在纹理清楚的块中，高频丰富，高频ac的幅值也较大，按level大小排序没有效果，所以能够破译的块信息量少，而纹理细节清楚的块又不易破译。仅vlc乱序后按level排序破译的画面效果如图4(a)所示，与未经破译的画面接近。其配合mb乱序，更抗分析。rmsp加密后经按level排序破译的视频画面如图5所示。4．3．3间隔分析
根据非零系数间隔(即event中的run参数)的分布规律，将event按run从小到大重新排序，可以破译相关性强的块。同样，这类块中纹理比较平缓，信息量小。在纹理清楚的块中，高频丰富、非零系数分布均匀、非零高频ac也比较集中，难以破译，因此能够破译的块含信息量小，而信息量大的块又难以破译。仅vlc乱序后按run排序破译的画面效果如图4(b)所示，与未经破译的画面接近。rmsp加密后经按run排序破译的视频画面与图5效果基本一致。
对块内vlc码字乱序而言，若块内像素相关性强，系数能量集中，量化后只有dc和少量低频ac。虽然易于破解但纹理平缓、信息量小且不含形状轮廓信息，边界信息接近故无助于mb拼接；块内纹理清楚或处于轮廓处的宏块，则必然高频丰富，ac能量分布均匀，非零系数多而乱序充分，破解就很困难。而仅知道dc和少量低频ac，不仅宏块内纹理不清楚，也不能为拼接破解宏块乱序提供相关性信息，配合难以正确拼接破译的mb乱序，视频画面仍不能理解。对rmsp方法，仅破译dc和少量低频ac是没有用的(若dc另用差分编码，则更难破译)。综合来看，rmsp方法使攻击者难以有效利用视频数据特性进行分析破译。
4．3．4其他性能
实验中硬件配置：p4 2.4 ghz cpu、256 mb ddram；编解码器采用mpeg－4校验模型[12]；密钥流采用a5[12]和rc4[12]组合，rc4的输出作为a5的密钥，每图组i帧更换，便于同步，由a5输出序列生成乱序密钥矩阵序列；视频规格为cif(qcif)和yuv格式文件。
yuv视频数据分别选用clairec(90 f)、mobile(300 f)、foreman(225 f)等序列，经压缩编码得到文件file_mpg，再经加密得到file_mpg_ecr，解密得到file_mpg_dcr，再解码得到file_dcr.yuv。
(1)速度。rmsp方法加/解密过程包括三步：①读入并分析视频流；②产生密钥序列并生成乱序(解乱)矩阵序列；③按密钥矩阵输出密(明)文视频流。①、③主要是比特流读写和数据提取定位，速度快且用时少。i帧宏块多，且要作块内dct系数乱序，故用时较多，但不超过1 ms/f。只对非零dct系数乱序，减少了计算量，速度远快于zigzag乱序(约12倍)。②用时较多且主要在于密钥序列生成上，但仍比直接应用序列密码要快得多。因为用于生成乱序矩阵序列的密钥流约为被加密视频流的1/11，步骤②的软件实现不超过8 ms/f，整个加密过程不超过8 ms/f，可满足实时应用。
编码视频流1 020 544 bytes(foreman)，需密钥流98 225 bytes，相差约10.39倍，这说明比序列密码节省大量的密钥生成时间。每帧耗时如表1所示。表中列出采用相同算法生成密钥序列与编码视频流异或的序列密码耗时及与rmsp方法的比较。两者平均速度差约4.71倍。
(2)密文格式。不加密各层格式信息数据，两种乱序都保持移动后的数据合法，保持vlc码字块尾标志符合语法。file_mpg_ecr可直接按标准解码得到正常完整的视频(本实验为yuv文件)，部分显示如图3所示。解码器不报错，说明加密过程完好保持了数据格式的兼容性。
（3）码流大小。两种乱序都只作视频流中的比特段移位，不改变原数据流大小。明文文件file_mpg、file_mpg_dcr长1 020 544 bytes(foreman)，密文file_mpg_ecr长1 020 546 bytes，说明未降低压缩率。
(4)抗误码能力。只要碰到正确的i帧，密文流与密钥流即可同步，正确解密。在第19帧(p帧)模拟误码，此后解密画面逐渐模糊。由于实验环境是文件存取，到第30帧(第二gop的i帧)即重新恢复清晰。若是视频会议环境具有丢包重编i帧功能，同步更及时。
5总结和讨论
为了解决vlc码字加密的难题，达到视频加密同时满足安全、实时在线、保持压缩率、格式兼容等矛盾性要求，通过分析利用视频编码数据的特性，提出了rmsp方法。rmsp与现有方法比较具有更实用的特点：①兼容，完全保持编码标准格式，密文状态下传输处理方便；②安全，视频画面不能理解，充分消除了攻击者可利用的相关性，可选用随机序列密钥，达到对应序列密码的抗分析强度；③实时，速度比使用相同密钥的序列密码快四倍以上，可满足在线处理需要；④保持压缩率，完全不改变明文编码流长度；⑤丢包后恢复密钥流同步能力可靠，适用于主流编码标准，可制作独立模块。
参考文献：
［1］qiao lintian, nahrstedt k. comparison of mpeg encryption algorithms [j].computer & graphics,1998,22(4): 437－448.
［2］徐正全,杨志云,李伟,等.数字视频加密技术发展现状及展望[j].武汉大学学报,2005，30(7):570－574.
［3］tang lei. methods for encrypting and decrypting mpeg video data efficiently:proceedings of the acm multimedia[c].boston:[s.n.],1996:219－230.
［4］zeng wenjun, lei shanmin. efficient frequency domain selective scrambling of digital video [j].ieee transactions on multimedia,2003,5(1):118－129.
［5］shi changgui, bhargava b.light－weight mpeg video encryption algorithm:proceedings of the international multimedia conference on multimedia[c].new delhi:[s.n.],1998:55－61.
［6］kankanhalli m s, guan t t.compressed－domain scrambler descrambler for digital video [j].ieee transactions on consumer electronics,2002,48(2):356－365.
［7］wen jiangtao, severa m, zeng wenjun,et al. a format－compliant configu－rable encryption framework for access control of multimedia:ieee the 4th workshop on multimedia signal processing[c].[s.l.]:[s.n.],2001：435－440.
［8］wen jiangtao, severa m, zeng wenjun,et al.a format－compliant configurable encryption framework for access control of vi－deo [j].ieee transactions on circuits and systems for video technology,2002,12(6)：545－557.
［9］shi changgui, bhargava b.a fast mpeg video encryption algorithm:proceedings of the 6th acm international multimedia confe－rence[c].bristol:[s.n.],1998: 81－88.
［10］袁春,钟玉琢,贺玉文.基于混沌的视频流选择加密算法 [j].计算机学报,2004,27(2):257－263.
［11］bruce s.应用密码学——协议、算法与c源程序[m].吴世忠,等译.北京：机械工业出版社，2001:261－301.［12］钟玉琢,王琪,贺玉文.基于对象的多媒体数据压缩编码国际标准mpeg－4及其校验模型[m].北京：科学出版社,2000:433－475.
