基于ElGamal體制的視頻內(nèi)容保密比較方案

于 鵬，王永濱，柯雅明，劉 文

(中國傳媒大學(xué)計算機(jī)學(xué)院，北京 100024)

1 概述

隨著計算機(jī)和通信技術(shù)的發(fā)展，以及“三網(wǎng)融合”的推進(jìn)，視頻內(nèi)容已經(jīng)成為人們工作、學(xué)習(xí)、娛樂生活中不可或缺的組成部分，人們在享受信息時代方便快捷服務(wù)的同時，同樣也面臨著視頻內(nèi)容帶來的安全問題。由于視頻內(nèi)容很容易遭到非法的使用、復(fù)制和篡改，因此對視頻的保護(hù)尤為重要。主流的對視頻內(nèi)容進(jìn)行保護(hù)的方法有數(shù)字水印技術(shù)[1]，該技術(shù)是通過在視頻中嵌入標(biāo)識信息，通過驗證標(biāo)識信息來確保視頻版權(quán)和完整性。然而，在實際生活中經(jīng)常會遇到如下問題：A擁有視頻MA，B擁有視頻MB，需要對雙方擁有的視頻進(jìn)行比較，判斷視頻是否被篡改過，以及確定篡改發(fā)生的位置。傳統(tǒng)的方法是：A將視頻MA發(fā)給B，B將MA與MB進(jìn)行比對，并將結(jié)果發(fā)回給A。但是，在這個過程中存在以下問題：A會將視頻泄露給B；B在驗證完成后，也可以對A進(jìn)行欺騙，否認(rèn)驗證結(jié)果；視頻數(shù)據(jù)量通常較大，導(dǎo)致此方法的通信開銷較大。顯然，數(shù)字水印技術(shù)無法解決上述問題。

保密比較是隱私保護(hù)、信息安全的重要基礎(chǔ)[2]。保密比較計算研究是于1982年針對姚氏百萬富翁問題提出的解決方案，它是多方保密比較的基礎(chǔ)，如安全多方排序問題、安全比較向量問題等。姚氏百萬富翁問題經(jīng)過許多學(xué)者的發(fā)展[3]，現(xiàn)在的保密計算已經(jīng)成為國際密碼學(xué)研究的熱點問題之一。但是這些方法計算、通信效率低，比較的數(shù)的范圍[4]是[1,100]，而目前針對視頻內(nèi)容的保密比較方法鮮有報道。

本文針對MPEG壓縮視頻，提出一種基于ElGamal體制的保密比較方案。綜合分析視頻編碼和易篡改等特征，在此基礎(chǔ)上提取出視頻特征信息；在驗證雙方間，通過改進(jìn)的可交換ElGamal算法對特征信息分組哈希值進(jìn)行比對，在不泄露雙方視頻內(nèi)容任何信息，包括視頻摘要信息的前提下，使驗證雙方都可獲得驗證結(jié)果，如果發(fā)生篡改還可定位篡改所在的區(qū)域。同時，該方案不需要可信第三方TC來維護(hù)公私鑰的分發(fā)。

2 預(yù)備知識

2.1 視頻相關(guān)介紹

視頻具有明顯的語義結(jié)構(gòu)特征，因此，在設(shè)計壓縮編碼時，MPEG標(biāo)準(zhǔn)使用了分層的語法結(jié)構(gòu)來描述視頻信息。在MPEG壓縮編碼中，視頻被分為6層，分別是視頻序列層、圖像組層、圖像層、條帶層、宏塊層和塊層[5]。頂層是視頻序列層；每個視頻序列又可分為多個圖像組(Group of Picture,GOP)，每個GOP由多個I幀、P幀和B幀組成，一個典型的GOP由12幀組成[6]，包括1個I幀、3個P幀和8個B幀，排列順序為IBBPBBPBBPBBP；每個幀內(nèi)又分為多個條帶，每個條帶由多個16×16大小的宏塊組成；宏塊由多個8×8大小的亮度、色度塊組成。

視頻篡改主要是指借助某些視頻編輯軟件，對視頻格式、內(nèi)容等進(jìn)行修改，導(dǎo)致其原始信息完整性、真實性被破壞[7]。隨著網(wǎng)絡(luò)和各種視頻編輯軟件的迅速發(fā)展，視頻的篡改越來越容易。同時，視頻篡改的方式也有很多，通?？煞譃閇8]時間域篡改和空間域篡改，或者兩者兼而有之。時間域的篡改建立在時間軸上，通常是對幀的操作，包括添加幀、刪除幀、替換幀和重組幀等處理；而空間域的篡改是對視頻幀內(nèi)的篡改，包括添加對象、移除對象等處理。在現(xiàn)實的視頻篡改中，篡改往往是一個視頻中持續(xù)的事件，由于視頻幀的播放速度很快，每秒約30幀，在這種情況下，一個有效的篡改至少要達(dá)到15幀以上[9]。

2.2 ElGamal算法

ElGamal是公鑰加密算法，其安全性依賴于循環(huán)群G上計算離散對數(shù)的困難性[10]和Diffie-Hellman假設(shè)[11]，它既可用于數(shù)字簽名又可用于加密。ElGamal算法應(yīng)用十分廣泛，在密碼學(xué)研究中占據(jù)重要地位。ElGamal密碼體制原型如下：

首先需要選擇一個素數(shù)p、3個隨機(jī)數(shù)g，x和k，其中，g和x都小于p，k與p–1互素，對明文M的加密算法為：

其中，a和b是密文對，密文的長度是明文M的2倍，x為私鑰，公開y，g和p。解密時，計算：M=b/axmodp ，因為ax≡gkxmod p ，同時有b/ax≡ykM/ax≡gxkM/gxk≡Mmod p，所以解密方法成立。

3 基于ElGamal體制的視頻內(nèi)容保密比較

視頻的保密比較包括2個過程：(1)提取視頻特征信息；(2)對特征信息進(jìn)行保密比較。

3.1 視頻特征提取

對于一段視頻來說，提取哪些信息作為其特征是個非常重要的問題。一般視頻特征提取需要考慮以下原則：(1)代表性，即提取的特征能很好地代表視頻的視覺內(nèi)容，且數(shù)據(jù)量盡可能小。(2)敏感性，即這些特征能對一些非法操作十分敏感。要想設(shè)計一個好的視頻特征提取算法，必須綜合考慮視頻編碼特征和視頻篡改特征[5]。視頻特征提取流程如圖1所示。

圖1 特征提取流程

由MPEG視頻編碼標(biāo)準(zhǔn)可知，MPEG視頻序列由若干GOP組成，每個GOP的基礎(chǔ)幀是I幀，其中I幀編碼方式采用幀內(nèi)編碼，包含了整個GOP的主體信息，而P幀和B幀圖像的重建也離不開I幀數(shù)據(jù)，且MPEG視頻編碼要求約每12幀中有一個I幀，因此，按照畫面頻率24幀/s計算[12]，則1 s有2個I幀出現(xiàn)，故一般不能夠直接在視頻壓縮流中跳過或刪除I幀。因此，在特征提取時，I幀可以很好地代表一段GOP的特征。

文獻(xiàn)[13]的研究表明，MPEG在對I幀進(jìn)行編碼時，使用了基于塊的DCT變換。8×8的圖像塊在進(jìn)行DCT變換后，形成一個8×8系數(shù)矩陣，其中，DC系數(shù)是這8×8圖像塊采樣信息的平均值，包含了圖像塊能量的主要部分[14]。在MPEG視頻編碼中，每一個條帶的Y，U，V分量各自的8×8塊中的DC系數(shù)之間采用差分編碼，修改一個條帶中的一個分量，那么此條帶中后續(xù)分量都會受到影響。因此，在一幀信息中，每個條帶的最后一塊DC系數(shù)，能夠很好地代表一個條塊的特征。此外，人眼對亮度信號比較敏感，同時根據(jù)普通圖像特點，在一個場景內(nèi)，色度總是基本一致且單一的[14]，因此，在特征提取時僅提取亮度分量。

對視頻中每個I幀進(jìn)行解碼，提取每個條帶中最后一個塊的Y分量DC系數(shù)作為此條帶的特征值。設(shè)I幀中有ST個條帶，則提取出的信息為：DCYc={DCYc1,DCYc2,…,DCYST}，DCYc表示當(dāng)前幀Ic中所提取的所有特征信息的集合，將這些信息按順序進(jìn)行級聯(lián)，形成I幀特征值：Fc=DCYc1||DCYc2||…||DCYST，其中，“||”表示信息級聯(lián)；c為I幀的序號。根據(jù)I幀序號c將若干I幀分為一組，假設(shè)分組大小為GT，則當(dāng)前幀所屬的組號Gid=c/GT，將處于同組Gid的特征數(shù)據(jù)進(jìn)行組合：

其中，Π代表某種組合操作。以此類推得到所有分組的特征信息集合{FGid}，其中，Gid=0,1,…,TGid，TGid為分組數(shù)。

對每個分組計算hGid=H(FGid)有TGid個分組，其中，H(?)表示哈希計算，則通過上述方法可以得到一段視頻的TGid個特征組信息序列{hGid},Gid=0,1,…,TGid。

3.2 保密比較

3.2.1 保密比較概念

保密比較是指參與比較的各方在不出示本方秘密數(shù)據(jù)的前提下驗證各方數(shù)據(jù)是否相同。一般假設(shè)參與協(xié)議的各方都是半誠實參與者，半誠實參與者是指各參與者在計算過程中將嚴(yán)格地執(zhí)行協(xié)議，不會進(jìn)行串通，但也會保留計算的中間結(jié)果并試圖推導(dǎo)出其他參與者的輸入。

若一個加密方案E滿足等式：

其中，k1和k2為不同的加密密鑰；x為待加密的明文。則稱該加密方案為可交換的加密算法，可交換加密算法可以實現(xiàn)兩方之間的保密比較。

3.2.2 可交換ElGamal算法

本文改進(jìn)了ElGamal加密算法，使其滿足可交換性。在保密比較的雙方之間共享一個大素數(shù)p，相互保密g，x和k；由于保密比較不需要對密文進(jìn)行解密，因此丟棄用于解密的密文a及其相關(guān)計算。設(shè)保密比較的雙方為A和B，A擁有消息MA，B擁有消息MB，在不泄露MA和MB的情況下，

驗證MA和MB是否相同。改進(jìn)算法的執(zhí)行過程如下：

(1)A隨機(jī)選擇一個大素數(shù)p，并將p發(fā)送給B。

(2)A產(chǎn)生隨機(jī)數(shù)gA,xA,kA，其中，gA,xA都小于p，gcd(kA,p–1)=1。B產(chǎn)生隨機(jī)數(shù)gB,xB,kB，其中，gB,xB都小于p，kB與p–1互素。A和B相互保密這些數(shù)據(jù)。

(3)A做如下計算：

bA1即是A對MA進(jìn)行一次加密的密文，bB1即是B對MB進(jìn)行一次加密的密文。

(4)A將密文bA1發(fā)送給B，B將密文bB1發(fā)送給A。

(5)A對收到的密文bB1進(jìn)行二次加密：

B對收到的密文bA1進(jìn)行二次加密得：

(6)A和B交換二次加密結(jié)果，即A發(fā)送bA2給B，B發(fā)送bB2給A。

(7)在A，B兩端做驗證：若bA2=bB2，則MA=MB；否則，MA≠MB。

上述改進(jìn)的ElGamal加密算法可交換性證明如下：

將式(4)代入式(5)得：

根據(jù)mod運(yùn)算的性質(zhì)可得：

將式(3)代入式(6)得：

根據(jù)mod運(yùn)算的性質(zhì)，可得：

若MA=MB，則有式(8)同式(10)，從而得證bA2=bB2，即該算法滿足可交換性。證畢。

3.2.3 視頻保密比較方案

為驗證兩方視頻內(nèi)容是否相等，需要一方選擇特征提取分組大小參數(shù)GT，并發(fā)給另一方。雙方首先按照此參數(shù)對視頻進(jìn)行特征提取，然后按照改進(jìn)的可交換ElGamal算法進(jìn)行保密比較，驗證每個分組是否都相同，如果分組全部相同，則視頻相同；如果不同，則可根據(jù)不同所在的組號定位篡改發(fā)生的區(qū)域。如果需要提高檢測精度，可進(jìn)一步縮小分組參數(shù)GT，從而精確定位篡改發(fā)生的區(qū)域。

4 實驗與結(jié)果分析

為了評測本文方案的效果，在VC++平臺下進(jìn)行仿真實驗。在測試模型中，考慮到取材的廣泛性和普遍性，分別從廣告、新聞、體育比賽和電影中選取5段視頻流，視頻的I幀數(shù)目和分組大小各不相同，其檢測結(jié)果如表1所示。其中，最后一行電影視頻是無篡改視頻。從實驗結(jié)果可知，對于不同大小的視頻在不同的區(qū)域進(jìn)行篡改，本文方案都能準(zhǔn)確地檢測出篡改發(fā)生所在的分組。

表1 篡改檢測結(jié)果

對本文所提出的視頻內(nèi)容保密比較方案分析可知，其具有以下特征：

(1)在視頻特征提取時，僅提取I幀中每個條帶最后一塊DC系數(shù)亮度值，提出的數(shù)據(jù)量少，且極具代表性，減少了待驗證信息的數(shù)據(jù)量和網(wǎng)絡(luò)通信量，降低了計算復(fù)雜度。

(2)對視頻特征進(jìn)行靈活分組，可采用逐級細(xì)化的方式，對篡改所在區(qū)域進(jìn)行精確定位。

(3)使用改進(jìn)的可交換ElGamal算法實現(xiàn)保密比較，保密比較雙方僅共享一個大素數(shù)P，私鑰都由用戶自己保存，避免了竊聽者非法獲取密鑰的安全風(fēng)險。

(4)一方獲得的數(shù)據(jù)是另一方對采用私鑰進(jìn)行ElGamal加密的密文，在整個過程中不暴露用戶視頻相關(guān)信息，甚至是特征信息。若試圖通過知道的中間信息進(jìn)行求解，其計算困難性等價于計算GF(p)中解離散對數(shù)的難度。

(5)參與雙方都可公平獲得保密計算的結(jié)果，而不是由一方告知另一方，具有很好的公平性。

5 結(jié)束語

目前，針對視頻內(nèi)容的保密比較研究較少。本文綜合考慮了視頻編碼和視頻篡改相關(guān)特征，在對傳統(tǒng)ElGamal算法進(jìn)行改進(jìn)的基礎(chǔ)上，提出了一種基于ElGamal體制的視頻保密比較方案。該方案對視頻進(jìn)行特征提取，僅選擇視頻幀每個條帶中最后一個宏塊的亮度值作為特征數(shù)據(jù)，提取的數(shù)據(jù)量少，且具有很好的代表性。文中同時對ElGamal算法進(jìn)行改進(jìn)，并給出了改進(jìn)算法的可交換性證明方法。實驗結(jié)果表明，本文方案具有良好的公平性、安全性和有效性，同時具有較低的計算復(fù)雜度和通信開銷。

[1]劉 虹.數(shù)字視頻版權(quán)保護(hù)與內(nèi)容認(rèn)證的基本理論及關(guān)鍵技術(shù)研究[D].武漢:武漢理工大學(xué),2008.

[2]李順東.適用于數(shù)字對象的保密比較協(xié)議[J].陜西師范大學(xué)學(xué)報:自然科學(xué)版,2010,38(1):1-4.

[3]李順東,竇家維,賈曉林.集合相交問題的雙方保密計算[J].西安交通大學(xué)學(xué)報,2006,40(10):1091-1093.

[4]Yao A C.Protocols for Secure Computations[C]//Proc.of the 23rd Annual Symposium on Foundations of Computer Science.Chicago,USA:IEEE Press,1982:160-164.

[5]崔雪冰,馮巧娟,崔平非.基于內(nèi)容特征的MPEG視頻認(rèn)證方案[J].計算機(jī)應(yīng)用,2010,30(1):213-216.

[6]劉 芳,曹 歐,李畢祥.基于DCT的Arnold變換視頻水印算法研究[J].計算機(jī)與數(shù)字工程,2011,39(6):102-105.

[7]譚茂洲,蔣興浩,孫錟鋒.視頻篡改被動檢測技術(shù)研究[J].信息安全與通信保密,2012,3:68-69.

[8]Yin Peng,Yu H H.Classification of Video Tampering Methods and Countermeasures Using Digital Watermarking[C]//Proc.of Multimedia Systems and Applications IV Conference.Denver,USA:[s.n.],2001:239-246.

[9]秦運(yùn)龍,孫廣玲,張新鵬.利用運(yùn)動矢量進(jìn)行視頻篡改檢測[J].計算機(jī)研究與發(fā)展,2009,46(z1):227-233.

[10]許德武,陳 偉.基于橢圓曲線的數(shù)字簽名和加密算法[J].計算機(jī)工程,2011,37(4):168-169.

[11]陳 良,高成敏.半誠實模型下公平高效的安全兩方比較協(xié)議[J].計算機(jī)工程與應(yīng)用,2010,46(36):126-132.

[12]楊 勝,鐘玉琢.一種從MPEG壓縮視頻流中提取關(guān)鍵幀的方法[J].中國圖象圖形學(xué)報,2001,6(3):254-258.

[13]Huang Jiwu,Shi Y Q,Shi Yi.Embedding Image Watermarks in DC Components[J].Circuits and Systems for Video Technology,2000,10(6):974-979.

[14]陶 丹,陳后金.一種壓縮域中基于鏡頭的關(guān)鍵幀提取改進(jìn)算法[J].計算機(jī)應(yīng)用研究,2009,26(9):3539-3541.