admin 随着多媒体信息在移动、手持设备上应用的日益广泛，人们开始研究低复杂度、对硬件要求较小的多媒体加密技术。如今很多音视频文件格式中（如MPEG4、JPEG、MP3等）都用到了Huffman编码，基于Huffman编码的低复杂度的多媒体加密技术逐渐进入人们的研究视野。
一、MHT加密方法
许多音视频格式如JPEG、MP3、MPEG的熵编码阶段都是根据已预先确定的Huffman码表进行编码，进行数据流的转换，这个过程中可以加入一些加密措施。最早MHT加密方案就是在Huffman码表中选择一些合适的表对数据流进行编码，再对其选择的方式和编码的顺序进行保密，从而达到加密的目的。由于普通的经训练得到的Huffman码表数量有限，进行加密的安全性很低，MHT算法就是为了增加Huffman码表的数量而又不改变其码树的结构，从而增大加密空间来使加密的安全性得到提高。其基本思路是，首先经训练得到多媒体数据对应的基本Huffman码表，再按一定的方式由基本码表变换得到变换码表，在其中选取一部分码表用来对数据流加密，选择方法是通过使用一个已产生的密钥来进行。MHT的加密过程如下：
a)先得到基本Huffman码表，再对其进行变换后共得到2k个码表，依次标记为0一2K-1。
变换方法如图l所示。若基本Huffrnan码树有t个叶子，就有t-l个内部节点和对应的01标记对，先随机产生一个t-l比特的随机序列，每一位与码树的内部节点相对应，序列位上为O则交换对应节点的01标记，为l则不交换。
b)生成一个伪随机向量P=(p1，p2…．，Pn)作为密钥，pi为在0-2&-1范围内的k比特整数。
c)对原始数据的第i段数据使用第Pi个Huff-man码表进行编码，Pi的值为p(i-l(madn))+l。
这种方法只需要经训练得到少量的几个基本Huffman表后，再由基本表变换得到大量的Huffman表，相比于由训练得到大量的Huffman表来说方法更简单。若原Huffinan树有t-l个内节点，我们就有t-l个选择来决定是否变换每个内节点对应的标记对，故可产生2t-1个不同的Huffman树，并且变化得到的Huffman树与原Huffman树结构一样，对数据流的编码效率没有任何影响。MHT方案与直接进行Huffinan编码相比，除了需要再给表加上索引外，基本没增加太多额外的计算量，同时还增加了一定的安全性，但却需要耗费一些额外的内存空间来对表进行存储。
二、MHT的安全性分析
对MHT的安全性分析我们均以JPEG算法中的加密DC（直流分量）系数时其所对应的Huffman编码树为例。
唯密文攻击：在没有任何明文信息的情况下攻击者只能通过寻找不同密文块之间的统计特性来分析密文，而已经证明通过MHT加密后的密文为伪随机序列，接近理想的随机状态，无法使用其统计特性来进行攻击誓。若使用穷举攻击的方法，我们经训练能得到4个基本码表如图2所示。若对应的Huffman树有t个码值，则变换后共得到4 2t-1个Huffman树，选取其中的m个码树，根据矢量P的值得到总的密钥空间为：
总的密钥空间大小：
因其对应的Huffman表有12个码值，则码树有II个内部节点，我们令m=8，P=128，则可得密钥空间大小：
显然是安全的。
已知明文攻击：这种攻击模型中攻击者需要找出我们所使用的Huffman码表以及编码顺序才能破译密文。假如每个明文符号有至少两种可能的编码长度，则N个符号的密文的可能同步方式大于2~，即使每个Huffman码表只有10个码值，至少也需要数百个密文符号被同步出来，从而才能重构出Huffman码表及编码顺序。由此可见，该算法可有效抵抗已知明文攻击。若攻击者得到一串经Huffman变换后的密文B=b lb2.6 r~，，对应明文为S=s IS2.SN，为了将B分为n块Si中对应的各编码块，需要考虑CN:1I种情况，复杂度为O（ON-1），若能知道N块的各编码长度L，则复杂度可降至O(Lml)。这攻击中存在的危险通常是由于编码时对Huffman表的选择不当造成的，由于MHT算法中的Huffman表的选择是随机的，其中一种可能就是所选择的m棵HuFfman树都来自于同一棵原始树，各符号又有着一样的编码长度。由表l可知所有的符号最多有三种不同的编码长度，则复杂度又可降至小于0(313)，而若给定的明文中并未包含所有的这13种符号的话复杂度会更低。
如下这种情况也很容易被攻击者破解：由图2知，大于5的符号均有三种不同的编码长度，且c树、d树对应的编码长度相同，若给定两个大于5的不同密文，当它们由同一棵码树编码所得时，较小符号的编码为Eu，可得较大符号的编码为Eux（其中E、X为01字符串，u为O或l，u则为u的非运算）。那么若知道任一个大于符号5的编码，就能很容易得到小符号的编码，再利用该编码可判断出所属的基本树的四种可能：a树、b树、c或d树。当为第三种情况时，我们可以根据第一个符号编码的第一个比特判断其属于c树还是d树，从而实现对第一个符号的同步。当N=200时，这N个符号中不存在1的可能性很小，可以忽略不计。根据以上条件，我们可以认为当这N个符号中存在两个不同且都大于5的符号时，就能实现对第一个符号的同步口这种情况发生的概率为：
其中，x代表明文符号，P{｝代表x的概率。各符号出现的概率由基本Huffman编码表推导而得a当N-200时，可计算出Psyn>0.9999，同时可以获得这200个符号的编码信息，构造出8个Huffman码表的一部分。后面的信息可使用同样的方式进行分析。若密钥长度为128，我们能成功同步128次的可能性大于0.987．同时获得200*128=25600个符号及其编码信息。只要某个符号出现在已知明文中，就可以恢复其对应的Huffman表的编码。由于任意一个小于10的符号不出现在已知明文中的概率小于0.2%，因此我们能以很大的概率恢复出8个Huffinan表绝大部分的信息，因此只要能获得200个已知明文密文对，就能以大于98.7%的概率破解该密码。
选择明文攻击：MHT在这种情况下的安全性最弱。若攻击者能够在密文中插入一个符号标记并能获得相应的输出密文的话，就完全不存在同步的问题，这对于受保护者是非常危险的。并且，如果不限制输入明文的长度，我们通过每次输入一个符号得出使用的第一个Huffman码表，再每次输入两位获得第二个码表，以此类推，若密钥P的长度为128．每个Huffman码表有12个编码符号，只需要输入128*12次就能破解密钥P和各Huffman码表。
通过以上对MHT安全性的分析，NfHT算法存在存储空间消耗大、不能有效抵抗已知明文和选择明文攻击的缺陷，分别提出了对MHT算法的改进方案，但后经研究发现这两种改进方案也有着无法抵抗同步攻击的缺陷，并且会在一定程度上影n向编码长度，针对MHT算法的缺陷我们也提出一种改进的Huffman表加密方案。
三、改进的MHT算法加密
基本MHT算法是利用变换Huffman树来增大密钥空间从而起到保密性，但这种方法需要大量的存储空间，在某些空问受限的设备上实现可能比较困难，并且如果对表选择不当会有很大的安全漏洞。我们可利用一个伪随机序列对基本Huffman树先进行随机变化然后直接编码，不再进行Huffman树的存储和选择，过程如下：
a)经训练得到基本的Huffman码表。
b)利用一输入密钥生成一个伪随机序列P=(Pl，Pl，…，pn)（使用常用的对称加密算法即可），将该序列分隔为如下的格式；
均为每四位隔开，其中Chi为Num的前两比特，目的屉用来选择使用哪个基本Huffinan表进行扰动；Num本身表示扰动节点个数；indexv则表示Num个需要扰乱加密的节点中每个所对应的序号，如图3所示。
c)扰动的方法就是将对应内部节点上的01互换，其与待加密节点的对应关系及扰动方式如图4所示。
d)原始数据中的第i个节点使用扰动后的Huffman树进行编码。
计算代价分析：这种方法相比MHT方法来讲主要多出了对Huffman树加密扰动的代价，但鉴于对Huffinan树的加密只涉及查找和比特互换操作，开销较小，故计算代价增加不大。而由于其不用存储MHT方法中的大量变换Huffman表，又减小了存储空间的开销。
安全性分析：攻击者在没有密钥的情况下无法得知所对应的各Huffman树，能起到保护作用；MHT方法是先对Huffman变换好，得到固定的树后进行存储，然后从中选掸合适的进行加密，而该方法是直接对Huffman树进行随机扰动，随着序列P的变化每次扰动产生的树不定，且各种扰动的概率没有明显的统计偏向，故能有效抵抗同步攻击；同时，由于编码使用的是扰动后的变换树，即使攻击者得到了原始的四个Huffman树，仍无法通过一些已知明密文对得到二者真正的对应关系来猜测出密钥，从而使选择明文攻击成为不可能。
小知识之Huffman编码
Huffman编码是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
