400430403. La criptografía visual y la segmentación de la complejidad de los planos de bits

La esteganografía se define como «el arte y la ciencia de escribir mensajes ocultos de tal forma que nadie, aparte de los receptores objetivo, conoce la existencia del mensaje» (en.wikipedia.org/wiki/Steganography). Para implementar aplicaciones de esteganografía podemos insertar información tanto en el dominio mismo de la imagen como en uno de los dominios transformados de la imagen – la frecuencia, el coseno, o las ondas pequeñas. En el presente artículo, voy a describir una técnica de esteganografía basada en Bit-Plane Complexity Segmentation (BPCS) y en criptografía visual. Para comprobar su viabilidad, implementé la técnica en Python.

La segmentación de la complejidad de los planos de bits, una técnica de compresión (disipativa) de imágenes propuesta por primera vez en el Instituto de Tecnología Kyushu, nos permite insertar en las imágenes grandes cantidades de datos. Pero para hacerlo, necesitamos de la criptografía visual para descomponer el mensaje en dos porciones con un alto carácter aleatorio.

((Cada píxel de la imagen original se amplia a una matriz de píxeles de 2×2 con una versión diferente en cada una de las dos porciones))

Normalmente, a la criptografía visual se la considera una forma visual de compartir en secreto; véase el artículo de Doug Stinson «Visual Cryptography and Threshold Schemes» (www.ddj.com/184410530) y mi artículo «Extended Visual Cryptography Schemes» (www.ddj.com/dept/architect/184406280). En su forma más simple, un sistema de criptografía visual (2,2) “fracciona” la imagen original en dos “imágenes de sombra” denominadas “porciones”. Cada píxel de la imagen original se amplia a una matriz de píxeles de 2×2 con una versión diferente en cada una de las dos porciones. Cualquier porción contiene píxeles aleatorios en blanco y negro uniformemente distribuidos. Al analizar sólo una única porción, no se puede obtener información sobre la imagen original, por mucho poder de computación o método de análisis que se utilice. La cuestión fundamental de la criptografía visual es que en el proceso de des-encriptación, la imagen original tiene que ser reconstruida visualmente. Cada porción se imprime en una transparencia separada y se le pasa a un participante del sistema. Cuando los dos participantes se reúnen, el secreto puede simplemente (y en teoría de forma instantánea) ser reconstruido al superponer las dos transparencias.

Para compilar las porciones, el sistema de criptografía visual que usa mi aplicación sólo considera matrices diagonales – véase las versiones 1 y 2 de la tabla 1. La figura 1 es un ejemplo del sistema de criptografía visual implementado por la aplicación.

Figura 1: (a) Mensaje secreto; (b) mensaje recompuesto; (c) primera porción; (d) segunda porción.

Tabla 1: Un sistema de criptografía visual (2,2)

Segmentación de la Complejidad de los Planos de Bits

Bit-Plane Complexity Segmentation (BPCS) se apoya en el hecho de que el sistema visual humano es sensible a los patrones, pero incapaz de identificar ruido blanco aleatorio. Por lo tanto, si queremos implementar un algoritmo BCPS, dividimos la imagen en zonas, y calculamos la complejidad de esas zonas. Cualquier zona con complejidad por encima de un cierto umbral puede ser sustituida por datos insertados. Esta técnica funciona con colores reales de 24 bits o con imágenes en escala de grises de 8 bits. No funciona con imágenes paleteadas; cambios pequeños en el valor de un píxel pueden tener drásticas consecuencias en el color del píxel en la imagen paleteada.

Kawaguchy y Eason (citeseer.ist.psu.edu/kawaguchi98principle.html) sugieren que los planos de bits de las imágenes naturales muestran una complejidad monotónica en aumento desde el plano de bits más significativo al menos significativo (MSB y LSB por sus siglas en inglés, respectivamente). La mayoría de los LSB parecen ruido aleatorio (figura 2).

Figura 2: (a) Venecia, imagen original; (b) MSB; (c) 4º plano de bits; (d) LSB.

Siguiendo con la separación de la imagen en planos de bits, cada plano se descompone en zonas cuadradas de 8×8 y se calcula la complejidad de las zonas. No hay una definición general para la complejidad de una imagen binaria. No obstante, hay una manera sencilla de calcular la complejidad de una zona en el plano de bits – sólo hay que contar el número de cambios de color en cada fila y columna de la zona. Para definir una escala coherente de complejidades, normalizamos esta figura de tal manera que un color simple tiene una complejidad de 0 y un patrón de tablero de damas (la zona más compleja posible) tiene una complejidad de 1.

Cualquier zona en cualquier plano de bits, con una complejidad por encima de un umbral seleccionado se la considera ruido aleatorio y es sustituida por 8 bytes de datos.

Esteganografía BPCS modificada

Sigue siendo posible que un bloque insertado no tenga una complejidad por encima del valor umbral. En este caso, hay que tomar el conjugado del bloque. El conjugado es una imagen binaria que se obtiene de tratar una imagen con XOR con el patrón de tablero de damas. Obviamente, se pueden rehacer los datos originales al volver a tratar la nueva imagen con XOR con el patrón de tablero de damas. Si es necesario, se calcula el conjugado, y se necesita un “píxel bandera” para marcar la zona como “conjugada”.

(En el proceso de des-encriptado (como en un puzzle), tenemos que detectar cualquier pieza de datos insertados y colocarla en su sitio)]

En el proceso de des-encriptado (como en un puzzle), tenemos que detectar cualquier pieza de datos insertados y colocarla en su sitio. Para identificar adecuadamente cada cuadro, he marcado cada uno con un número de secuencia. El número de secuencia es una representación binaria de un número entero.

Como el sistema de insertado propuesto es “ciego” (es decir, no se necesita tener conocimiento previo de la imagen, ni ninguna otra información para extraer el mensaje insertado), hay que escribir de nuevo la información adicional, que consiste en conjugar la bandera y el número de secuencia, dentro de la imagen, junto con los datos insertados.

Para ganar espacio para la información complementaria que debe acompañar a cada cuadrado 8×8, podemos bordear cualquiera de ellos con una fila y una columna; la información se podría organizar como en la figura 3.

Figura 3: organización de la información en una matriz ampliada de 959 píxeles.

El algoritmo no funciona si insertamos más cuadrados que los que se pueden marcar con un número de secuencia. Es decir, el número total de cuadros insertados que permite el modelo es de 216=65.536 cuadros. Desde esta perspectiva, la cantidad máxima de información que puede ser insertada es de 524.228 bytes, o 512 KB de datos.

Mi sistema de esteganografía escribe los datos desde el MSB al LSB en una espiral desde el centro de la imagen. Ello es así porque es los algoritmos de compresión de datos tienden a descartar el LSB y los detalles más importantes están normalmente en el centro de la imagen.

Una imagen de color real de 24 bits consiste en rojo, verde y azul (RGB, por sus siglas en inglés). El sistema visual humano parece sensible a las variaciones del verde y menos sensible a las del azul. Por lo tanto, voy a adoptar el orden siguiente en los datos insertados: Empiezo con el MSB de cada color constituyente, y después voy al plano siguiente hasta que se ha escrito toda la información relativa al insertado. El orden de los componentes del color es azul, rojo, verde.

Aunque se conoce el sistema de insertado para todas las imágenes, no tiene por qué ser comunicado a la parte receptora. El receptor sólo tiene que dividir la imagen en componentes de color, y después en planos de bits y en zonas. Después, todas las zonas con una complejidad superior al umbral predefinido son examinadas en busca de datos.

Si una zona tiene errores y no es identificada por su complejidad (o si se alteró el número de secuencia), el receptor no percibe el bloque. Pero es posible adivinar qué zona debería contener datos (véase el listado número 7, disponible online en [http://www.ddj.com/code/).

El modelo

Una posible opción para el modelo propuesto implica que haya un «distribuidor» y unos «participantes» en el sistema. El distribuidor elige un mensaje secreto representado como una imagen binaria en blanco y negro y aplica un sistema de criptografía visual (2,2) en el mensaje secreto, obteniendo así las dos porciones correspondientes. Cada porción está insertada individualmente en una imagen de escala de grises de 8 bits (tradicionalmente denominada en inglés “vessel” – que podríamos llamar “vaso”) con el sistema modificado de BPCS. Por último, el distribuidor envía las imágenes electrónicamente con los datos insertados a los participantes.

((Los participantes procesan la imagen recibida (también basada en el sistema BPCS modificado), obtienen la porción insertada como una imagen binaria e imprimen dicha imagen binaria en una transparencia))

Los participantes procesan la imagen recibida (también basada en el sistema BPCS modificado), obtienen la porción insertada como una imagen binaria e imprimen dicha imagen binaria en la transparencia. En cuanto se reúnen los participantes, pueden reconstruir visualmente el mensaje secreto superponiendo con cuidado las dos transparencias.

Este modelo sigue el diagrama de bloques de la figura 4. Aunque separado en la práctica, por simplicidad, la figura 4 ilustra todo el proceso de insertar/extraer: Sólo se trata el método esteganográfico para una imagen en escala de grises de 8 bits. La figura 5 presenta una visión general que considera que la modalidad de datos está insertada en los “vasos”)

Figura 4: El modelo aplicado.

Figura 5: (a) Venecia, imagen original; (b) rosas, imagen original; (c) Venecia, con información insertada; (d) rosas, con información insertada; (e) diferencia entre (a) y (c); (f) diferencia entre (b) y (d).

La implementación

Para ilustrar este modelo, he escrito una aplicación con Python, Python Imaging Library (PIL) (www.pythonware.com/products/pil/), y el paquete de matrices num para Python (www.stsci.edu/resources/software_hardware/numarray). PIL añade capacidades a Python para el procesado de imágenes y procesa una gama de formatos de imagen. La matriz num le permite a Python manipular eficazmente grandes matrices numéricas, semejantes a Matlab, IDL, o Octave.

Hay una convención común en el procesado de imágenes binarias (blanco y negro): Si a cualquier píxel negro de la imagen se le denota con 1 y cualquier píxel blanco es 0, podemos “transformar” cualquier imagen binaria en blanco y negro a una matriz binaria. Este es el método que uso en mi aplicación.

((El programa también proporciona otras herramientas para tareas como la generación de una matriz binaria aleatoria o un patrón de tablero de damas, la inicialización de ficheros de registro, la definición de algunos directorios estándar y cosas por el estilo))

En el proceso de insertado, se seleccionan 858 cuadrados de una matriz más grande (una porción en el modelo) y volvemos a escribir cuadrados de 9×9 en alguna otra matriz (normalmente un plano de bits); véanse los listados número 1 y 2 respectivamente. El algoritmo para calcular la complejidad de una región en un plano de bits se puede implementar como en el listado número 3.

def square(matrix, n, d):

# returns a square slice of dim d from a matrix

# n - square number

maxX = len(matrix(0))

maxY = len(matrix(:,0))

xsquares = maxX/d

ysquares = maxY/d

dy, dx = divmod(n, xsquares)

xslc = dx * d

yslc = dy * d

return matrix(xslc:xslc+d, yslc:yslc+d)

Listado número 1

def writesquare(matrix, square, n):

# writes a square of dim d into a bigger matrix

# n - square number

# returns the matrix with the overwritten sqaure

maxX = len(matrix(0))

maxY = len(matrix(:,0))

sqX = len(square(0))

sqY = len(square(:,0))

xsquares = maxX/sqX

ysquares = maxY/sqY

dy, dx = divmod(n, xsquares)

xslc = dx * sqX

yslc = dy * sqY

matrix(xslc:xslc+sqX, yslc:yslc+sqY) = square

return matriz

Listado número 2

def complexity(matrix):

maxX = len(matrix(0))

maxY = len(matrix(:,0))

norm = maxX*maxY

cmp = 0.

first = matrix(0)(0)

for x in range(maxX):

for y in range(maxY):

if first != matrix(x)(y):

cmp += 1

first = matrix(x)(y)

if cmp != 0:

cmp /= norm

return cmp

Listado número 3

Para garantizar el carácter “ciego” del sistema de insertado, hemos de proporcionar información adicional (como número de secuencia y bandera para las áreas conjugadas) a cualquier cuadrado de 8×8 leído de una porción. La información adicional se vuelve a escribir en el “vaso”, junto con el cuadrado 8×8 de datos insertados. El espacio requerido se obtiene bordeando el cuadrado con una fila y una columna. Aunque generalmente están definidas, las funciones de los listados número 4 (a) y (b) pueden realizar también el bordeado.

(a)

def insert_line(where, line, matrix):

maxX = len(matrix(0))

maxY = len(matrix(:,0))+1

if len(line) != maxX:

print "(ERR) Unable to append line."

sys.exit(1)

getback = zeros((maxY, maxX))

for y in range(maxY):

if y == where:

getback(y) = line

else:

if y < where: getback(y) = matrix(y)

else:

getback(y) = matrixy-1]

return getback

(b)

def insert_column(where, column, matrix):

tmatrix = transpose(matrix)

tcolumn = transpose(column)

tmpback = insert_line(where, tcolumn(0), tmatrix)

return transpose(tmpback)

Listado número 4

El programa también proporciona otras herramientas para tareas como la generación de una matriz binaria aleatoria o un patrón de tablero de damas, la inicialización de ficheros de registro, la definición de algunos directorios estándar y cosas por el estilo. Todo ello se implementa en un paquete de utilidades.

((La función se inicia con un número de secuencia dado y retorna el último número de secuencia que utilizó))

La aplicación tiene módulos de compresión, insertado y extracción. Todos los componentes funcionan sobre imágenes de un nivel de gris de 8 bits o de color real de 24 bits. Yo me he centrado en las imágenes de 8 bits porque el procesado de las imágenes de color real sólo implica la siguiente extensión: PIL nos permite cambiar entre distintas representaciones en píxeles de una imagen mediante la función convert. En términos de imágenes convertidas, sólo hay dos formatos aceptados: L (escala de grises de 8 bits) y/o RGB (color real de 24 bits). Ello nos permite convertir las imágenes de entrada en formato RGB de la manera siguiente:

try:

image = __original_image.convert("RGB")

except IOError:

print "Cannot convert image: " + image_name

Tras su conversión con éxito, el objeto image es en formato RGB. Para objetos de este tipo, PIL ofrece un método que retorna una tupla que contiene los componentes individuales de la imagen (“bandas” en la documentación PIL). Eso significa que podemos decir:

red, green, blue = image.split()

Los objetos red, green, blue esta vez son imágenes en escala de gris de 8 bits. Los tres módulos de la aplicación se implementan en una clase separada denominada image.

La compresión, que está basada en BPCS, sólo establece las zonas de imagen con una complejidad superior al umbral establecido. Estas zonas están sobre-escritas con el color blanco. El módulo insertado usa el esquema BPCS modificado. El módulo realiza el bordeado del cuadrado de 8x8 inicial, insertando los números de secuencia según corresponde y la “bandera conjugada” si se necesita. ( véase el listado numero 6, disponible en [www.ddj.com/code/)

La función se inicia con un número de secuencia dado y retorna el último número de secuencia que utilizó. Eso es así debido al escenario mismo del insertado: Durante el proceso, tenemos que movernos de un plano de bits a otro, y, en el caso de imágenes de color real, de un componente de color a otro. Así pues, la función tiene que “saber” cuál es el número actual de secuencia y retornar el número de secuencia con el que terminó para la siguiente iteración.

El módulo de extracción comprueba la complejidad de cualquier zona en la imagen y busca los datos insertados. La aplicación también intenta establecer si se extrajo la cadena completa de números de secuencia; de no ser así, informa sobre los cuadrados que faltan.

Como en la tabla 1, las únicas matrices 2x2 que deberían existir en una porción son las diagonales. El módulo de extracción también usa un mecanismo de detección de errores y nos informa si se alteró alguna zona de la imagen – se encontró una matriz 2x2 “errónea”. Como la función de insertado, la función de extracción se inicia con un número de secuencia inicial y retorna el siguiente número de secuencia cuando acaba; (véase el listado numero 7, disponible en www.ddj.com/code/)