Substituição Homofônica utilizando Códigos de Huffman Canônicos

  • José Rodrigues Fernandes UCP
  • Ruy Luiz Milidiú PUC-Rio
  • Claudio Gomes de Mello IME

Resumo


Neste trabalho, é proposto um algoritmo para compressão e criptografia simultâneas. O algoritmo utiliza um esquema de substituição homofônica. Os códigos para o conjunto de símbolos homofônicos são gerados via Códigos de Huffman Canônicos. Além disso, o algoritmo utiliza uma chave secreta para a fase final de cifragem baseada em permutações. Para testar a eficiência do algoritmo proposto, comparamos seu desempenho com um compressor convencional. Nos experimentos realizados, observamos uma perda de compressão inferior a 6%. Estes resultados indicam um bom compromisso entre qualidade e eficiência.

Palavras-chave: criptografia, substituição homofônica, compressão, Huffman canônico

Referências

Gunter, C.G. 1988. An Universal Algorithm for Homophonic Coding. in Advances in Cryptology Eurocrypt-88, LNCS, vol. 330.

Huffman, D. 1952. A Method for the Construction of Minimum-Redundancy Codes. Proc. IRE, 1098-1101.

Klein, S. T., Bookstein, A., Deerwester, S. 1989. Storing Text Retrieval Systems on CD-ROM: Compression and Encryption Considerations. ACM Trans. on Information Systems, vol. 7, no. 3

Bookstein, A., Klein, S.T. 1993. Is Huffman coding dead?, Computing 50 279-296

Massey, J.L., Kuhn, Y.J.B., Jendal, H.N. 1989. An Information-Theoretic Treatment of Homophonic Substitution. in Advances in Cryptology Eurocrypt-89, LNCS, vol. 434.

Moffat, A., Witten, I.I., Bell, Timothy C. 1994. Managing Gigabytes: Compressing and Indexing Documents and Images. Van Nostrand Reinhold.

Rivest, Ronald L., Mohtashemi, M., Gillman, David W. 1996. On Breaking a Huffman Code. IEEE Transactions on Information Theory, vol. 42, no. 3.

Shannon, C. 1949. Communication Theory of Secrecy Systems. Bell Syst. Tech., vol. 28, no. 4, pp. 656-715.

Stinson, Douglas S. 1995. Cryptography - Theory and Practice. CRC Press.

Wayner, P. 1988. A Redundancy Reducing Cipher, Cryptologia, 107-112.

Zobel, J., Williams, H.E. 1999. Compact In-Memory Models for Compression of Large Text Databases. SPIRE'99 (String Processing and Information Retrieval), 224-231
Publicado
05/03/2001
FERNANDES, José Rodrigues; MILIDIÚ, Ruy Luiz; MELLO, Claudio Gomes de. Substituição Homofônica utilizando Códigos de Huffman Canônicos. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 1. , 2001, Florianópolis. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2001 . p. 50-55. DOI: https://doi.org/10.5753/sbseg.2001.21285.