具加密功能之整數型算術編碼的設計與分析

Design and Analysis on Secure Integer Arithmetic Coding

梁尹蓁(Yin-Chen Liang)

指導教授 ： 黃育銘 ； 劉震昌

國立暨南國際大學/科技學院/資訊工程學系/博士(2014年)

https://doi.org/10.6837/NCNU.2014.00284

摘要

隨著數位時代的來臨與資訊技術的進步，網際網路 (Internet) 已成為我們日常生活上的必須工具，利用高科技智慧型的相關產品，透過網路廣泛地傳播、散佈與獲取任何的資訊，享受著數位科技上所帶來的便利，但相對地，也浮現出一些潛在性的問題，如：機密資料文件的竊取、偽造或竄改；在秘密視訊會議上的監聽、偷窺…等相關的問題。因此，數位多媒體的資料也伴隨著資訊安全上的重要性，保護數位資料安全的機制是必然探討的研究。此外，由於網路頻寬有限的問題，對於在即時傳輸的訴求下，如何設計有效的資料加密及壓縮機制，儼然成為一重要研究課題。

近年來，許多研究學者致力於將資料加密與資料壓縮做整合；在設計具安全性的算術編碼相關研究上，除了考量較小壓縮失真 (Compression Loss)，並對其所提出的方法於安全性上做詳細的分析，如：隨機算術編碼 (Randomized Arithmetic Coding, RAC)及具安全性算術編碼 (Secure Arithmetic Coding, SAC) 。上述研究著重在實數型算術編碼，基於計算複雜度的考量，工業界實作大多採用整數型算術編碼，因此本論文主要探討整數型算術編碼。本論文共分三部份，首先我們提出二種具安全性的算術編碼方法，也就是資料在進行算術編碼的過程中，將資訊安全的機制同步整合於系統中；接者深入探討有關整數型算術編碼的最佳壓縮效能，用來佐證所提之二種具安全性的算術編碼方法，其在壓縮效能上損失相當些微。

第一部份，我們提出具安全性整數型算術編碼 (Modified Integer Arithmetic Coding, MIAC)，在編碼之前，先利用安全雜湊演算法 (Secure Hash Algorithm, SHA-256) 產生秘密金鑰，它將用於決定是否對於最大出現頻率的符號所對應的編碼區間長度增加，或對於最小出現頻率的符號所對應的編碼區間長度減少的運作；完成編碼後的碼文，為了提高安全性，我們再將碼文與偽亂數產生器 (Pseudorandom Bit Generator, PRBG)－BBS作XOR運算產生密文；實驗結果顯示，MIAC不僅同時擁有壓縮及加密的功能，且在壓縮效能上往往會比傳統整數型算術編碼 (Traditional Integer Arithmetic Coding, TIAC) 來得佳；對於本論文所用到的測試檔案，當壓縮效能變差時，所增加的壓縮大小都在1個位元以內。

第二部份，我們發現，針對每個符號所對應的編碼區間其長度大小作調整得以減小瞬時熵 (Instantaneous Entropy)。因此，我們進一步提出了第二種方法稱為安全整數算術編碼 (Secure Integer Arithmetic Coding, SIAC)，相較於MIAC，其具有較高的安全性，且幾乎所有壓縮效能都比TIAC來得好。缺點是演算法的計算複雜度變高了。

第三部份，我們提出了一個可調節式整數型算術編碼 (Adjustable Integer Arithmetic Coding, AIAC)，在所有可能整數型算術編碼實作中，其擁有最好的壓縮效能。 根據理論分析，AIAC採用最佳區間分割技巧得以將因整數型算術編碼實作所衍生的冗餘 (Redundancy) 降到最低，所以可以達到最好壓縮效能。

關鍵字

算術編碼 ； 隨機算術編碼 ； 安全性算術編碼 ； 安全雜湊演算法 ； 偽亂數產生器 ； 可調式安全性整數型算術編碼

並列摘要

With the advance of technologies in digital communication and digital storage, a variety of multimedia information can be spread easily to all corners of the world over the internet. But relatively, many potential problems emerge, such as: stealing, forging, or tampering for confidential documents, monitoring in video conference, and so on. Thus, once we deal with the digital multimedia data, the issue of information security will consequently emerge. In addition, due to the constraint of limited network bandwidth for transmitting real-time multimedia data, how to design an effective mechanism for data encryption and compression, has become an important research topic.

Current research in multimedia security has recently focused on improving the cryptanalysis of randomized arithmetic coding (RAC) and secure arithmetic coding (SAC). The above approaches are applied to floating-point arithmetic coding. Integer implementation is more popular than the floating-point arithmetic implementation since it can decrease the computational cost of arithmetic coding without inducing significant compression loss. Taking a different approach, we present two novel multimedia security approaches based on a modification of integer arithmetic coding.

In the first proposed approach, we apply the Secure Hash Algorithm (SHA-256) to construct the key vector. Using the key vector, every time a symbol is encoded, the source intervals associated with different symbols are adjusted accordingly. We then use the Pseudorandom Bit Generator (PRBG) - BBS to generate a key stream to enhance security through the bitwise XOR operation. In terms of coding efficiency, theoretical analysis and experimental results indicate that our proposed code not only provides security, but also often offers better compression efficiency when compared with traditional integer arithmetic coding (TIAC).

Next, we find that it is possible to decrease the instantaneous entropy through the alternate adjustment of source intervals. Hence, we further propose the second approach called integer arithmetic coding (SIAC) with higher security, and the compression efficiency of this code is almost the same or even higher relative to TIAC.

Finally, we propose an adjustable integer arithmetic coding (AIAC) scheme with the best compression performance on integer arithmetic coding. AIAC applies an optimal interval partition scheme to enhance the compression efficiency. Instead of traditional interval partition method, this algorithm can reduce the redundancy induced by integer arithmetic coding to the lowest. AIAC can also be used to verify that both algorithms, MIAC and SIAC, have quite slight loss on the compression performance even in the case of compression loss.

並列關鍵字

Arithmetic Coding ； Randomized Arithmetic Coding ； Secure Arithmetic Coding ； SHA-256 ； Pseudorandom Bit Generator ； Adjustable Integer Arithmetic Coding

參考文獻

[1] D. Kundur and K. Karthik, “Video fingerprinting and encryption principles for digital rights management,” in Proc. IEEE, vol. 92, pp. 918-932, 2004.

[2] Data Encryption Standard (DES), Federal Information Processing Standards Publication 46, Jan. 1977.

[3]Advanced Encryption Standard (AES), Federal Information Processing Standards Publication 197, Nov. 26, 2001.

[4] M. Grangetto, A. Grosso, and E. Magli, “Selective encryption of JPEG2000 images by means of randomized arithmetic coding,” in Proc. IEEE 6th Workshop on Multimedia Signal Process., Siena, Italy, Sep. 2004, pp. 347-350.

[5] M. Grangetto, E. Magli, and G. Olmo, “Multimedia selective encryption by means of randomized arithmetic coding,” IEEE Trans. Multimedia, vol. 8, no. 5, pp. 905-917, Oct. 2006.