PDF de programación - Capítulo 6 Teoría de la Información

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 6

Teoría de la Información

Seguridad Informática y Criptografía

Ultima actualización del archivo: 01/03/06
Este archivo tiene: 59 diapositivas

v 4.1

Material Docente de
Libre Distribución

Dr. Jorge Ramió Aguirre
Universidad Politécnica de Madrid

Este archivo forma parte de un curso completo sobre Seguridad Informática y Criptografía. Se autoriza el uso,
reproducción en computador y su impresión en papel, sólo con fines docentes y/o personales, respetando los
créditos del autor. Queda prohibida su comercialización, excepto la edición en venta en el Departamento de
Publicaciones de la Escuela Universitaria de Informática de la Universidad Politécnica de Madrid, España.

Curso de Seguridad Informática y Criptografía © JRA

Capítulo 6: Teoría de la Información

Página 179

Fundamentos de la Seguridad Informática
Los pilares sobre los que descansa toda la teoría asociada a
los criptosistemas son básicamente tres:

• La teoría de la información

– Estudio de la cantidad de información contenida en los

mensajes y claves, así como su entropía.

• La teoría de los números

– Estudio de las matemáticas discretas y cuerpos finitos
que permiten las operaciones de cifrado y descifrado.

• La teoría de la complejidad de los algoritmos

– Estudio de la clasificación de los problemas como

computacionalmente tratables o intratables.

Estos temas los veremos en éste y en los siguientes capítulos del libro.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 6: Teoría de la Información

Página 180

Teoría de la información

• Definición de información:

– Es el conjunto de datos o mensajes inteligibles

creados con un lenguaje de representación y que
debemos proteger ante las amenazas del entorno,
durante su transmisión o almacenamiento, usando
técnicas criptográficas entre otras herramientas.

– La teoría de la información mide la

cantidad de información que
contiene un mensaje a través del
número medio de bits necesario para
codificar todos los posibles mensajes
con un codificador óptimo.

¿Qué significa
cantidad de
información y
codificador
óptimo?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Página 181

Representación de la información

Puede ser numérica, alfabética, simbólica, por lenguaje.

Ejemplo: 15/01/05 15-01-05 15-1-05 15/01/2005

01/15/05 01-15-05 1-15-05 01-15-2005 ...

- Todos son el día 15 de enero del año 2005.
Vitaminas: B12, C, ...
Grupo sanguíneo: A2 Rh+ ...
Elementos: Fe, Si, Hg ...
Compuestos químicos: H2O, CO2 ...
Más común

Veamos la información
que contiene el mensaje

¿Hace calor allí?

Lenguaje con código: “¿Hace calor allí?”

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 6: Teoría de la Información

Página 182

La información que tiene un mensaje

Veremos qué información nos entrega un mensaje
dependiendo del contexto en que nos encontremos.
Esto puede analizarse:
a) En función de la extensión del mensaje recibido.
b) En función de la utilidad del mensaje recibido.
c) En función de la sorpresa del mensaje recibido.
d) Dependiendo del entorno de esa sorpresa.
e) En función de la probabilidad de recibir un mensaje.

Este último enfoque orientado a la ingeniería y usado por
Claude Shannon en su estudio es el que aquí nos interesa.

http://es.wikipedia.org/wiki/Claude_E._Shannon



© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Página 183

Cantidad de información (caso 1)

En función de la extensión del mensaje

– Ante una pregunta cualquiera, una respuesta concreta y
extensa nos entregará mayor información sobre el tema
en particular, y diremos que estamos ante una mayor
“cantidad de información”.
• Pregunta: ¿Hace calor allí?

(una playa en particular)

– Respuesta 1: Sí, hace mucho calor.
– Respuesta 2: Cuando no sopla el viento, el calor allí es
– Respuesta 2: Cuando no sopla el viento, el calor allí es
inaguantable pues supera los 42 grados a la sombra.
inaguantable pues supera los 42 grados a la sombra.
¿Dónde hay una mayor cantidad de información?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 6: Teoría de la Información

Página 184

Cantidad de información (caso 2)

En función de la utilidad del mensaje

– Ante una pregunta cualquiera, una respuesta más útil y
clara nos dejará con la sensación de haber recibido una
mayor “cantidad de información”.

• Pregunta: ¿Hace calor allí? (una playa en particular)

– Respuesta 1: Sí, sobre 30 grados.
– Respuesta 1: Sí, sobre 30 grados.
– Respuesta 2: Si no hay viento del sur y el mar está en

calma, es normal que la temperatura suba bastante.

¿Dónde hay una mayor cantidad de información?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Página 185

Cantidad de información (caso 3)

En función de la sorpresa del mensaje

– Ante una pregunta cualquiera, una respuesta más

inesperada y sorprendente, nos dará la sensación de
contener una mayor “cantidad de información”.

• Pregunta: ¿Hace calor allí? (ahora Finlandia en otoño)

– Respuesta 1: Sí, muchísimo. Es insoportable.
– Respuesta 1: Sí, muchísimo. Es insoportable. ☺
– Respuesta 2: En esta época del año, la temperatura es

más suave y el tiempo muy agradable.

¿Dónde hay una mayor cantidad de información?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 6: Teoría de la Información

Página 186

Cantidad de información (caso 4)

Dependencia del entorno (sorpresa)

– Ante una pregunta cualquiera, una respuesta inesperada
y sorprendente en el entorno, nos dará la sensación de
contener una mayor “cantidad de información”.

• Pregunta: ¿Hace calor allí?

(ahora las mismas respuestas hablan de la temperatura en un horno)
– Respuesta 1: Sí, muchísimo. Es insoportable.
– Respuesta 2: En esta época del año, la temperatura es
– Respuesta 2: En esta época del año, la temperatura es

más suave y el tiempo muy agradable. ?
más suave y el tiempo muy agradable.
¿Dónde hay una mayor cantidad de información?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Página 187

Cantidad de información (caso 5)

En función de la probabilidad de recibir un mensaje
– Este enfoque probabilístico es el que nos interesará en

cuanto a la definición de Cantidad de Información.

¿Dónde le da alegría a su cuerpo Macarena?

– Respuesta 1: En un país de Europa.
– Respuesta 2: En una ciudad de España.
– Respuesta 3: En los números 1 y 3 de la calle Sierpes en
– Respuesta 3: En los números 1 y 3 de la calle Sierpes en
Sevilla, España... La Campana, ¡una excelente bombonería!
Sevilla, España.

¿Por qué?

¿Dónde hay una mayor cantidad de información?

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 6: Teoría de la Información

Página 188

Incertidumbre e información

Ante varios mensajes posibles, en principio todos equiprobables, aquel
que tenga una menor probabilidad de aparición será el que contenga
una mayor cantidad de información.

• En el ejemplo anterior:

– Al ser más extenso el número de calles y sus números en una

ciudad que el número de ciudades en España, y esto último mayor
que los países en Europa, la última respuesta tendrá una mayor
incertidumbre.

– Si suponemos todos los estados equiprobables, entonces la

cantidad de información de la respuesta tercera será mayor que las
demás.

Las siguientes diapositivas resumen el estudio de Claude Shannon sobre la
entropía en su artículo “A Mathematical Theory of Communication” que
puede descargarlo en formato pdf desde esta dirección:

http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html



© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Página 189

Concepto de variable aleatoria

• Sea X una variable aleatoria con n estados posibles con

X = xi una ocurrencia iésima:

X = {x1, x2, x3, ..., xn-1, xn}
p1 = p(x1), p2 = p(x2), ..., pn = p(xn)

Como:

Entonces:

0 ≤ pi ≤ 1 para i = 1, 2, ..., n
n
Σ pi = 1
i = 1

La probabilidad de que ocurra p1 o
p2 o p3, etc. será siempre la unidad
porque seguro será uno de ellos.

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Libro Electrónico de Seguridad Informática y Criptografía v4.1

Capítulo 6: Teoría de la Información

Página 190

Definición de cantidad de información

• Definiremos ci a la cantidad de información del

estado i, como el logaritmo en base dos de la
probabilidad de que ocurra el estado iésimo.

ci = - log2 (pi )

ci

0

pi

0

1

- Logaritmo: p(xi) = 1 ⇒ no hay incertidumbre: ci = 0

p(xi) = 0 ⇒ máxima incertidumbre: ci → ∞

- Signo: p(xi) < 1 ⇒ log p(xi) será negativo
- Base 2: Un fenómeno binario ⇒ dos estados (bit)

© Jorge Ramió Aguirre Madrid (España) 2006

Capítulo 6: Teoría de la Información

Página 191

Grado de indeterminación

ci =

Grado de indeterminación previo
Grado de indeterminación posterior

En una bolsa hay dos papeles con círculos, dos con
cuadrados y dos con triángulos: negros o blancos.
Sacamos a ciegas tres papeles cualesquiera...

Sea ésta será la combinación elegida...

Si hay equiprobabilidad

entonces p(xi) = 1/8

Combinación 1
Combinación 2
Combinación 3
Combinación 4

Combinación 5
Combinación 6
Combinación 7
Combinación 8

¿Q