確認有損耗傳輸的圖象的完整性的方法

2023-05-25 02:42:56

專利名稱：確認有損耗傳輸的圖象的完整性的方法
技術領域：
本發明一般涉及信號加密的領域，並且特別涉及一種用於識別有損耗傳輸的數字圖象是否還沒有被修改過並且是否已經從專用的源發送的方法。這通過建立專門的指紋和「籤名」實現。
現有的諸如美國專利No.5,499,294中公開的用於加密數位訊號以防幹擾的方法可防止有惡意的敵方修改信號。指紋或「散列」用於表示數字圖象。散列算法(即單向函數)已廣為人知並且易於計算，但是卻非常難以數學反演。通常使用加密密鑰加密指紋以證明或鑑別籤名創建人。該加密本身是一種具有使用秘密密鑰的源站的標準公共/秘密密鑰密碼法。由此產生的籤名由具有源公開密鑰的接收站解密。
散列密鑰與原始圖象組合在一起，隨後發送到在解密加密的散列時使用假想發射機的公開密鑰的接收站。接收站對接收的圖象執行相同的散列算法並且把它與解密的散列相比。如果這兩個散列相同，那麼在傳輸中沒有噪聲並且圖象沒有被第三方修改(幹擾)。如果圖象被修改或者使用了錯誤的公開密鑰，那麼兩個散列則不相同。
一般地，同樣的技術在損失信息的傳輸中則行不通。通常，所接收圖象的數位化形式包括損失的比特或噪聲，它們破壞所接收的數位化圖象。因此，根據所接收的源圖象指紋與根據接收的數位化圖象產生的數位化指紋的比較，難以確認接收的圖象是否被竄改過。
解決JPEG傳輸中的此問題的其它努力在Ching-Yun Lin和Shih-Fu Chang發表於ISLT/SPIE Symposium on E1ectronicImaging:Science and Teehnology.Jan 1998,San Jose,Cal.pages77-80的"A Robust Image Authentication AlgorithmDistinguishingJPEGCompressionfromMaiiciousManipulations"中進行了描述。它們的方法是比較JPEG壓縮傳輸的後續幀中的相同塊。進行這個比較是為了確保這兩個塊間的差值範圍即使在執行壓縮和解壓之後也保持相同。通過把兩個塊間的差值與閾值比較可建立籤名。二進位位的「0」或「1，」根據該差值是否高於或低於該閾值而被輸入到籤名中。這個籤名與將要傳送的圖象一起發送，並且此方法如上所述而繼續。
Lin/Chang法的不足之處在於它依賴於JPEG壓縮的固有結構，並且不能用於不遵循JPEG格式的傳輸(包括有損耗傳輸)。而且，Lin/Chang法使幹擾成為可能。由於籤名完全根據連續幀與閾值的比較，所以只要連續幀間的差值大概相同(在所選閾值範圍內)，惡意的敵方就能夠建立完全不同的數據流並且將其發送到接收機。
在本技術領域中已知的另一項技術是水印技術。一組比特(一個標記)添加到傳送的圖象中。這個標記應當完全足以使其能夠被接收機檢測但又不會改變圖象的性質。該技術常常在關注剽竊的版權問題中使用。於是，宣稱沒有複製圖象的被告將被迫解釋為何在圖象中仍有水印。水印技術是一種證明原創的有效方式。但是，它不能指示何時發生了幹擾。
因而希望提供一種改進的方法，用於確認所接收圖象是否已經被修改。該方法應當包括一個指紋，它易於通過圖象進行計算但難以建立具有給定指紋的圖象。指紋法還應當具有難以產生兩個具有相同指紋的圖象的特性。該指紋法應當在數位化信號傳輸存在損耗時能夠使用。
本發明的一個方案是一種用於確認傳送圖象完整性的方法，包括的步驟是把圖象分成具有第一序列的第一多個信元；產生隨機種子(seed)並且根據所述隨機種子產生第一多個偽隨機數。該方法還包括的步驟有根據第一多個偽隨機數和第一多個信元把圖象分成第二多個信元並且產生第二多個偽隨機數，該第二多個偽隨機數形成第二序列。該方法進一步包括的步驟有在形成第一指紋時，把對應於第一序列的信元與對應於第二序列的信元相比較並且把該指紋、圖象和隨機種子傳送到接收機。該方法另外還包括的步驟有由接收機通過使用接收圖象和隨機種子產生第二指紋並且比較第一和第二指紋。
此方法使第三方在不改變圖象指紋的情況下難以操縱該圖象。如果一個人知道種子則可以輕易地建立指紋本身。但是這個種子對於第三方來說是未知的。即使有損耗地發送圖象，指紋也不會改變並且這樣它仍然可用於監控圖象的完整性。
本發明的另一個方案是一種用於建立圖象指紋的方法，包括的步驟有把圖象分成具有第一序列的第一多個信元；產生隨機種子；根據所述隨機種子產生第一多個偽隨機數；並且根據第一多個偽隨機數和第一多個信元把圖象分成第二多個信元。該方法還包括的步驟有產生第二多個偽隨機數，該第二多個偽隨機數形成第二序列；以及在形成指紋時把對應於第一序列的信元與對應於第二序列的信元相比較。這個指紋與上述的指紋具有相同的益處。
在本發明的又一個方案中，一種計算機可讀存儲介質包括表示圖象的指紋，該介質具有一系列的指示，每個指示均由閾值與第一個數和第二個數的差值之間的比較產生。第一個數對應於圖象的第一多個信元的第一信元值。第二個數對應於圖象的第二多個信元的第二信元值。通過把圖象分成第三多個信元並且根據第一多個偽隨機數操縱第三多個信元形成第一多個信元。第二多個信元與所述第一多個信元數目相同，並且具有由所述第二多個偽隨機數指示的序列。
在本發明的再一個方案中，一種計算機可讀存儲介質具有編碼的數據，用於把圖象分成具有第一序列的第一多個信元；產生一個隨機種子；並且根據該隨機種子產生第一多個偽隨機數。該介質還具有數據，用於根據第一多個偽隨機數和第一多個信元把圖象分成第二多個信元；產生第二多個偽隨機數，該第二多個偽隨機數形成第二序列；並且比較對應於第一序列的信元和對應於第二序列的信元。
本發明的一個目的是提供一種用於確認有損耗傳輸的圖象的完整性和源的方法。
本發明的另一個目的是提供一個唯一的數字圖象的籤名，它易於產生並且即使是在有損耗傳輸之後也能夠與另一個籤名相比較。
通過連續參照附圖的下述公開，本發明的這些和其它優點將變得顯而易見，在附圖中，相同的參考數字代表相同的元件。


圖1所示為根據本發明的傳輸圖象的信元的分割和排序圖；圖2所示為根據本發明新近建立的信元圖；圖3所示為根據本發明的典型指紋圖；圖4所示為用於部分表示圖3的圖象和指紋的傳輸信號的產生方法的流程圖；以及圖5所示為用於接收圖3的傳送圖象和指紋並且用於確認該圖象完整性的方法的流程圖。
參照圖1和4，一個n×n網格100應用於源數字圖象103，由此在步驟200建立n2個信元。n值根據處理功率和希望的精確度的可能性而定。n2個信元根據希望的任何合適的編號系統來編號(C1，C2，C3…Cn2)。在步驟202產生隨機種子「r」。產生這個隨機種子的最佳方式實際上是來自源。例如，電子噪聲、放射衰變或者源於太陽的宇宙射線。任何不能輕易改變的不可預測的事物都可形成最佳的源。在步驟204，通過使用作為種子的r產生n2個偽隨機數(prn)。必須為prn值加上邊界，這是因為這些數值可引起偏移(下面將作更詳細描述)。這些數通過使用應用於隨機數r的數學算法來計算。任何算法都可使用。儘管該算法最終會被確認，但不可能輕易地知道隨機數r。
現在參照圖2，在步驟206，每個信元(C1、C2、C3…Cn2)被處理(即偏移或縮放)以作為各自prn的結果。例如，每個信元可偏移其原始位置prn，並且隨後寬度和高度變化相同的量(或者由多個prn產生的不同的量)作為偏移。如果偏移使一個信元超出了原始圖象的邊界，則如圖2所示，該信元折回到另一個邊。顯然，現在會有很多信元重疊。這些新信元(C1′，C2′，C3′…Cn2′)的大小和位置對於第三方來說是未知的。
已有技術中的指紋為每個信元產生一個估算尺度(metric)，由此產生一個相應值。很多技術可用來尋找這個度量。例如，該量度可以是每個信元中的特定顏色量、像素值之和或者是離散餘弦變換(「DCT」)。在這些已有技術的指紋中，如上所述，第三方可以輕易地建立一個具有相同指紋的不同圖象。例如，如果綠色是變量，則第三方只要產生具有相同量的綠色的信元即可。但是，如果第三方試圖重建具有本發明指紋的圖象，那麼他將幹擾多個重疊的信元。
在步驟208，對於這些新產生的信元中的每一個來說，取用一個估算尺度用於圖象的每個最後所得到的區域。實際使用的量度不重要，並且可執行任何已有的技術。通過實驗發現，如果使用DCT，則只需要DC值；AC值對於計算的貢獻不大。用戶可得到並選擇各類技術或者通過使用上述的偽隨機數進行隨機選擇。這樣的各類技術也可以組合起來形成一個大籤名。其目的是產生一個籤名以使第三方難以創建一個具有相同籤名的不同圖象。
在步驟210產生第二組n2個偽隨機數。這些數表示應用於新產生信元的一個序列。該序列的第一個數是與信元1比較的信元數，第二個數是與第二個信元比較的數，而第n2個數則是與信元n2比較的數。例如，如果第二組prn開始於14，23，5…，則信元14將與信元1相比較，信元23與信元2相比較，如此類推。該比較與上面決定的量度有關。
在步驟212，通過把一對信元之間的關係與閾值相比較產生了指紋。如果一對信元間的差值高於閾值，則把「1」輸入到指紋中。否則輸入「0」。因此每對產生n2比特長的指紋的一個比特。指紋的一個實例如圖3所示。該指紋可存儲到任何存儲介質中或者被立即發送。
對於從發射機A到接收機B的傳送來說，在步驟214，通過使用接收機的公開密鑰-Epub(b)(r)，隨機種子被加密。該指紋隨即附加到Epub(b)(r)。最後，在步驟216和218，-Epub(b)(r)和指紋的組合通過使用發射機的秘密密鑰而加密並且發送-Epri(a)[-Epu(b)和指紋]。顯然，Epub(b)(r)不必使用A的秘密密鑰加密。但是，如果不加密，則至少該指紋將要求秘密密鑰A來確認在A的原物。
指紋和圖象均被發送。圖象以其固有的方式發送。至於指紋，甚至連模擬傳輸也分配可有一些損耗發送的數字數據。例如，如果使用NTSC標準，則數字數據可在垂直消隱間隔(VBI)期間發送。在NTSC中，像素被水平地逐行打亮。當最後一個像素被激發時，則需要一個有限的時間周期以回移到屏幕的開始。在這個稱作VBI的時間周期中可接收數字數據。在同類標準中存在其它相似的周期。
參照圖5，在接收機側B，通過使用A的公開密鑰解密圖象和指紋。如果是其它的源而非A發送信息，那麼該結果將沒有意義。如果使用了錯誤的公開密鑰(例如第三站C)，產生的結果也毫無意義。現在，接收機具有籤名和E(r)並且使用其自己的秘密密鑰獲得r。接收機B對其接收的圖象所執行的步驟與A上面執行的步驟相同。這些步驟包括把圖象分成一個n×n的網格；產生偽數等。這樣也將產生接收圖象的指紋。接收站把這個產生的指紋與接收的指紋相比較。這兩個指紋應當是相同的。該比較應當實時進行，或是存儲這些指紋並且隨後進行比較。即使在傳輸中存在損耗，該損耗也不致於使指紋發生顯著地改變。
為了補償傳輸中的噪聲，籤名中的一些差異是允許的。例如，可比較兩個指紋並且如果它們之間的差值(不匹配的0和1的數)低於閾值(「哈明」距離)，則該差值可以接受。甚至在指紋中一些比特的不同也不會影響系統的安全性，這是因為幹擾會使得指紋中的很多比特翻動；噪聲只引起少量的變化。
顯然，上述的所有變量都可以調整，而不會影響該算法的固有性質。例如，所產生的信元數n可根據用戶希望的安全性而增加或減少。
上面公開了一種用於確認傳輸信號的整體性和鑑別的增強方法。本發明至少產生四個可以認識到的優化系統操作的結果1)使用的每個信元的大小對於第三方來說是未知的。這由通過未知的隨機種子產生的prn保護。實際的定大小和縮放的算法也可以是保密的。2)第三方不知道比較哪一個信元。這也是未知的隨機變量的一個函數。3)信元的位置未知，同時它們也是所產生的隨機變量的一個函數。4)用於估算每個信元的算法或估算尺度未知。如上所述，所使用的度量也可以是prn的一個函數。
對於安全性的其它因素來說，可把時間戳記添加到傳輸的信號中。惡意的第三方可訪問圖象並且向接收機發送一個延遲的圖象，由此傳送了一個可接受的圖象和指紋。時間戳記將避免這個問題，因為這個時間也被包括到了傳輸之中。這個戳記將被加密並且與r、計算的指紋、圖象一起發送到接收機。
顯然，我們不需要遵循上面所示的確切步驟。例如，甚至可在應用n×n網格之前的同一時間產生所有的偽隨機數。
本發明值得稱道的是，即使是在傳輸中存在損耗時，通過產生專用指紋也可估算傳送的圖象是否被改變。
對於本領域的普通技術人員來說，通過對最佳實施例的描述，在不背離附屬的權利要求更清晰定義的本發明的範圍和宗旨的情況下顯然可進行各種變化。
權利要求
1．一種用於產生圖象指紋的方法，包括的步驟是把所述圖象分成具有第一序列的第一多個信元(200)；產生一個隨機種子(202)；根據所述隨機種子產生第一多個偽隨機數(204)；根據所述第一多個偽隨機數和所述第一多個信元把所述圖象分成第二多個信元(206)；產生第二多個偽隨機數(210)，所述第二多個偽隨機數決定所述第二多個信元的第二序列；以及在形成所述指紋時，比較對應於所述第一序列的信元和對應於所述第二序列的信元(212)。
2．根據權利要求1所述的方法，其中所述分割步驟包括移動和縮放所述第一多個信元。
3．根據權利要求1所述的方法，其中所述第一多個信元在數目上等於所述第一多個偽隨機數並且在數目上等於所述第二多個偽隨機數。
4．根據權利要求1所述的方法，其中所述比較步驟包括通過使用多個估算尺度估算每個信元。
5．根據權利要求1所述的方法，其中所述比較信元的步驟包括通過使用從多個估算尺度所選的估算尺度來估算每個信元，所述選擇由所述第一和第二多個偽隨機數中的至少一個來指示。
6．一種用於確認傳輸的數字圖象的完整性的方法，包括的步驟是根據權利要求1所要求的方法產生圖象指紋；把所述指紋，所述圖象，和所述隨機種子發送到接收機(218)；通過使用接收的所述圖象和所述隨機種子由所述接收機產生第二指紋(316)；以及比較所述第一和第二指紋(318)。
7．根據權利要求6所述的方法，其中所述發送步驟包括的步驟是使用所述接收機的公開密鑰加密所述隨機種子(214)，由此產生一個加密的種子；以及使用所述發射機的秘密密鑰加密所述第一指紋和所述加密種子(216)。
8．根據權利要求6所述的方法進一步包括的步驟是產生一個時間戳記；以及把所述時間戳記發送到所述接收機。
9．根據權利要求6所述的方法，其中所述第二指紋的形成方式與所述第一指紋相同。
10．一種使用權利要求1或6所述的方法的安全系統。
11．一種包括表示圖象的指紋的計算機可讀存儲介質，所述指紋包括一系列指示，每個所述指示由在閾值與第一數和第二數問的差值之間的比較產生；所述第一數對應於所述圖象的第一多個信元的第一信元的值；所述第二數對應於所述圖象的第二多個信元的第二信元的值；所述第一多個信元通過把所述圖象分成第三多個信元並且根據第一多個偽隨機數處理(206)所述第三多個信元而形成(204)；以及所述第二多個信元在數目上等於所述第一多個信元並且具有一個由所述第二多個偽隨機數指示的序列(210)。
12．根據權利要求11所述的計算機可讀存儲介質，進一步包括一個時間戳記。
13．一種計算機可讀存儲介質包括一個用於對圖象執行下面步驟的電腦程式把所述圖象分成具有第一序列的第一多個信元(200)；產生一個隨機種子(202)；根據所述隨機種子產生第一多個偽隨機數(204)；根據所述第一多個偽隨機數和所述第一多個信元把所述圖象分成第二多個信元(206)；產生第二多個偽隨機數，所述第二多個偽隨機數形成第二序列(210)；在形成一個指紋時，比較對應於所述第一序列的信元和對應於所述第二序列的信元(212)。
全文摘要
一個數字圖象被分成具有第一序列的多個信元。一個隨機種子產生並且用於產生兩組偽隨機數。第一組偽隨機數用於改變信元的位置和形狀,由此產生劃分該圖象的一組新信元。為這些新信元中的每一個取用一個量度。第二組偽隨機數產生第二序列。對應於第一序列的新信元中的每一個與另一個對應於第二序列的新信元相比較。這個比較與一個閾值相關並且產生一個指紋。所產生的指紋與圖象和隨機種子一起發送。接收機對其接收的圖象執行相同的算法。如果它產生的指紋與其接收的指紋相同,則可以斷定該圖象還沒有被修改。
文檔編號H04N1/387GK1288633SQ99802343
公開日2001年3月21日 申請日期1999年9月21日 優先權日1998年9月23日
發明者W·P·洛德, M·阿布德爾－莫塔萊布, M·A·埃普斯坦 申請人:皇家菲利浦電子有限公司