Algoritmos Rápidos para Cifragem de Imagens Utilizando Aproximações da DCT de Comprimento 8

Abstract

Introdução Criptografia é o estudo de técnicas matemáticas relacionadas a aspectos de segurança da informação, tais como confidencialidade, integridade e autenticidade de dados [4]. Vários processos de cifragem de imagens envolvem transformadas discretas, como a transformada discreta de Fourier [5], a transformada discreta de Hartley (DHT) [2] e, recentemente, a DHT binária (BDHT) [1]. A BDHT é uma aproximação de baixa complexidade computacional para a DHT e sua utilização em cifragem de imagens torna o método rápido e eficiente. Seguindo o método de codificação de dupla fase aleatória introduzido por [5] e suportada por [1], este trabalho propõem uma investigação de alternativas rápidas e eficientes para cifragem de imagens com três contribuições distintas: (i) utilização da transformada discreta do cosseno (DCT) no algoritmo de cifragem; (ii) utilização de aproximações da DCT de complexidade multiplicativa nula; e (iii) consideração de decomposição da imagem original em sub-blocos, assim como em algoritmos de compressão de imagens, como JPEG. Os pontos (ii) e (iii) são objetivados com o intuito de reduzir o custo computacional envolvido no procedimento de cifragem, propondo algoritmos rápidos e eficientes para aplicações em tempo real. 2. Metodologia Os métodos de cifragem e decifragem de imagens propostos em [1] podem ser descritos, respectivamente, por Q TN · (( TN · (PK1) ·TN ) K2 ) ·TN , (1) R ( TN · (( TN ·Q ·TN ) K′2 ) ·TN ) K′1, (2) em que TN é a matriz N  N da BDHT, P é a imagem original de tamanho N  N , Q é a imagem cifrada, R é a imagem decifrada, K1, K ′ 1, K2 e K ′ 2 são matrizes N  N aleatórias chamadas de chave,  é a operação de multiplicação elemento-a-elemento e  é a operação de divisão elemento-a-elemento. Se K′1 e K′2 forem iguais, respectivamente, a K1 e K2 então a imagem R será igual a imagem original P. Este trabalho foi parcialmente financiado por CNPq, FACEPE e FIT/UFSM. †Bolsista de Iniciação Tecnológica FIT/UFSM. Propomos a substituição da BDHT bidimensional (2D) por outras transformadas 2D como a DCT, a DCT binária (BDCT) [1] e a clássica transformada de Walsh-Hadamard (WHT). Além disso, sugerimos o procedimento de divisão da imagem original em sub-blocos de tamanho k  k, para k  8, 16, 32, 64. Em contraste, em [1], são utilizadas transformadas com mesmas dimensões das imagens. A Figura 1 esquematiza graficamente o método de cifragem considerado. Imagem de entrada P Divisão em blocos P k Transf. 2D Direta Transf. 2D Inversa Bloco Q k crifrado Rearranjo dos blocos Q k Imagem Q cifrada K 1 K 2 (a) Cifragem Imagem Q cifrada Divisão em blocos Q k Transf. 2D Direta Transf. 2D Inversa Bloco R k decifrado Imagem R decifrada K' 1 K' 2 Rearranjo dos blocos R k (b) Decifragem Figura 1: Esquema de cifragem e decifragem de imagens. 3. Resultados e discussões Uma vantagem direta da aplicação do método de sub-divisão da imagem original para o processo de cifragem é a redução do custo computacional. O custo computacional é avaliado pela complexidade aritmética que é dada pelo número de multiplicações e adições exigidas pela aplicação deste método. Algoritmos rápidos para transformadas discretas são comumente comparados em termos de sua complexidade aritmética, como figura de mérito para eficiência. A Tabela 1 apresenta as complexidades aritméticas associadas aos algoritmos de cifragem considerados. As complexidades da DCT exata de comprimento k, DCTk, são determinadas por meio do algoritmo de Chen [3] e as imagens utilizadas em nosso experimentos são imagens 512 512 em escala de cinza de 8 bits. Tabela 1: Comparação da complexidade aritmética dos algoritmos considerados Transformada Número de Complexidade de cada sub-bloco Complexidade total considerada sub-blocos Mult. Adições Total Mult. Adições Total DCT512 1 3936256 6293504 10229760 3936256 6293504 10229760 DCT64 64 37376 61696 99072 2392064 3948544 6340608 DCT32 256 7424 12416 19840 1900544 3178496 5079040 DCT16 1024 1408 2368 3776 1441792 2424832 3866624 DCT8 4096 256 416 672 1048576 1703936 2752512 WHT8 4096 0 384 384 0 1572864 1572864 BDCT8 4096 0 384 384 0 1572864 1572864 Os resultados da Tabela 1 evidenciam que quanto menor o tamanho do bloco, menor é a complexidade aritmética do algoritmo de cifragem associado. Os resultados do experimento computacional para comparação dos desempenhos dos procedimentos de cifragem considerando a DCT com diferentes tamanhos de sub-blocos são apresentados na Figura 2. Essa figura apresenta o ındice de similaridade estrutural (MSSIM) [6] entre as imagens decifradas e a imagem original. A medida MSSIM varia no intervalo [0, 1] e considera características do sistema visual humano diferentemente das medidas usuais, tais como a relação sinal-rúıdo de pico e o erro quadrático médio [6]. Para essa aplicação, os (i, j)-ésimos elementos de K′1 e K′2 foram definidos como [K′1]i,j  [K1]i,jδ e [K′2]i,j  [K2]i,jδ, em que os elementos [K1]i,j e [K2]i,j são independentes e uniformemente distribúıdos em [0.001; 0.001] e 0.001  δ  0.001. Para k  8, o gráfico com os valores de MSSIM decai mais rapidamente à medida que δ se afasta de zero, indicando que são necessárias chaves K′1 e K′2 com valores mais próximos de K1 e K2, respectivamente, para a boa reconstrução da imagem original. Ou seja, a abordagem em sub-blocos, além de fornecer menor custo, também mostra-se como uma opção mais segura para cifragem de imagens. 3e04 0e00 3e04 0. 0 0. 2 0. 4 0. 6 0. 8 1. 0 δ M SS IM k8 k16 k32 k64 k512 Figura 2: MSSIM das imagens decifradas utilizando a DCTk, com k  8, 16, 31, 64 e 512. Com base nos resultados anteriores, destacando o bom desempenho da utilização de k 8, optou-se por utilizar aproximações da DCT de complexidade multiplicativa nula, conforme Tabela 1, nomeadamente a WHT e a BDCT, como substituição da DCT de comprimento 8. A Figura 3 ilustra qualitativamente os resultados da cifragem por meio de alguns dos algoritmos rápidos considerados. (a) WHT8 (b) WHT8 (c) WHT8 (d) BDCT8 (e) BDCT8 (f) BDCT8 Figura 3: Resultados da cifragem na imagem Elaine utilizando WHT8 (a,b,c) e BDCT8 (c,d,e): (a) cifrada, (b) decifrada com δ  0.001, (c) decifrada com chaves corretas (δ  0), (d) cifrada, (e) decifrada com δ  0.001, (f) decifrada com chaves corretas (δ  0). O procedimento de sub-divisão da imagem original para utilização de transformadas de menores comprimentos é bastante promissor. A utilização de transformadas aproximadas para a DCT de comprimento 8 resulta em algoritmos rápidos e úteis para aplicações em tempo real, ao mesmo tempo que mantém a segurança da imagem cifrada. Em trabalho futuro, serão investigadas transformadas discretas específicas para cifragem e a utilização de transformadas de baixa complexidade computacional de outros comprimentos.