PDF de programación - Capítulo 11 Sistemas de Cifra en Flujo

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

Capítulo 11

Sistemas de Cifra en Flujo

Seguridad Informática y Criptografía

Ultima actualización del archivo: 01/03/06
Este archivo tiene: 51 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 11: Sistemas de Cifra en Flujo

Página 420

Cifrador de flujo básico

• Recordando la propuesta de cifrador hecha por Vernam en 1917,

los cifradores de flujo (sistemas con clave secreta) usarán:

– Un algoritmo de cifra basado en la función XOR.
– Una secuencia cifrante binaria y pseudoaleatoria denominada
S y que se obtiene a partir una clave secreta K compartida por
emisor y receptor, y un algoritmo generador determinístico.

– El mismo algoritmo para el descifrado debido el carácter

involutivo de la función XOR.

Clave K

Algoritmo

Determinístico
MENSAJE

⊕

S

M

secuencia cifrante

C

Operaciones ⊕ con bits

Clave K

⊕

S

Algoritmo

Determinístico
MENSAJE

M

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

Capítulo 11: Sistemas de Cifra en Flujo

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 421

Características de la secuencia cifrante S

Condiciones para una clave binaria segura

•

Período:

– La clave deberá ser tanto o más larga que el mensaje. En la

práctica se usará una semilla K de unos 120 a 250 bits en cada
extremo del sistema para generar períodos superiores a 1035.

• Distribución de bits:

– La distribución de bits de unos (1s) y ceros (0s) deberá ser

uniforme para que represente a una secuencia pseudoaleatoria.
Para ello deberá cumplir los postulados de Golomb:
Rachas de dígitos: uno o más bits entre dos bits distintos.
Función de autocorrelación fuera de fase AC(k): desplazamiento de k
bits sobre la misma secuencia Si.

http://ee.usc.edu/faculty_staff/bios/golomb.html



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

Capítulo 11: Sistemas de Cifra en Flujo

Página 422

Rachas de dígitos en una secuencia

El bit anterior
era un 0

Esta distribución
tan particular se
comentará más
adelante...

Rachas de una secuencia S de período T = 15

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0

El próximo
bit será un 1

Rachas de 0s
0 entre dos 1s

Rachas de 1s
1 entre dos 0s

Racha de 00s

Racha de 1111s
1111 entre dos 0s

Racha de 11s
11 entre dos 0s

00 entre dos 1s

Racha de 000s
000 entre dos 1s

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

Capítulo 11: Sistemas de Cifra en Flujo

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 423

Distribución de las rachas de dígitos

Las rachas, es decir la secuencia de dígitos iguales entre
dos dígitos distintos, deberán seguir una distribución
estadística de forma que la secuencia cifrante Si tenga un
comportamiento de clave aleatoria o pseudoaleatoria.
Para que esto se cumpla, es obvio que habrá mayor
número de rachas cortas que de rachas largas como se
observa en el ejemplo anterior.
Como veremos más adelante, esta distribución seguirá
una progresión geométrica. Por ejemplo una secuencia Si
podría tener 8 rachas de longitud uno, 4 de longitud dos,
2 de longitud tres y 1 de longitud cuatro.

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 424

Autocorrelación fuera de fase AC(k)

Función de autocorrelación:

– Autocorrelación AC(k) fuera de fase de una secuencia

Si de período T desplazada k bits a la izquierda:

AC(k) = (A - F) / T

Aciertos ⇒ bits iguales Fallos ⇒ bits diferentes

Ejemplo
Si

A =
F =

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0

Si k = 1

1 1 1 0 1 0 1 1 0 0 1 0 0 0 1

A=7; F=8

AC(1) = -1/15

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

Capítulo 11: Sistemas de Cifra en Flujo

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 425

Autocorrelación fuera de fase constante

Si

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0

Como ejercicio, compruebe que para esta secuencia cifrante Si la
autocorrelación fuera de fase AC(k) para todos los valores de k
(1 ≤ k ≤ 14) es constante e igual a -1/15. Esta característica será
importante para que la clave sea considerada buena.

Es decir, para que una secuencia cifrante S podamos considerarla
segura y apropiada para una cifra, además de cumplir con la
distribución de rachas vista anteriormente, deberá presentar una
autocorrelación fuera de fase AC(k) constante.

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 426

Imprevisibilidad e implementación de Si
•
Imprevisibilidad:
– Aunque se conozca una parte de la secuencia Si, la

probabilidad de predecir el próximo dígito no deberá
ser superior al 50%.

– Esta característica se definirá a partir de la denominada

complejidad lineal.

• Facilidad de implementación:

– Debe ser fácil construir un generador de secuencia
cifrante con circuitos electrónicos y chips, con bajo
coste, alta velocidad, bajo consumo, un alto nivel de
integración, etc.

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

Capítulo 11: Sistemas de Cifra en Flujo

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 427

Primer postulado de Golomb G1

Postulado G1:

– Deberá existir igual número de ceros que de unos. Se
acepta como máximo una diferencia igual a la unidad.

S1

S2

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
En la secuencia S1 de 15 bits, hay 8 unos y 7
ceros. Luego sí cumple con el postulado G1.

0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 1
En la secuencia S2 de 16 bits, hay 7 unos y 9
ceros. Luego no cumple con el postulado G1.

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 428

Significado del postulado G1

Si

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0

¿Qué significa esto?

Si una secuencia Si como la indicada cumple con G1, quiere
decir que la probabilidad de recibir un bit 1 es igual a la de
recibir un bit 0, es decir un 50%.
Por lo tanto, a lo largo de una secuencia Si, independientemente
de los bits recibidos con anterioridad, en media será igualmente
probable recibir un “1” que un “0”, pues en la secuencia hay una
mitad de valores “1” y otra mitad de valores “0”.

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

Capítulo 11: Sistemas de Cifra en Flujo

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 429

Segundo postulado de Golomb G2

Postulado G2:

– En un período T, la mitad de las rachas de Si serán de
longitud 1, la cuarta parte de longitud 2, la octava parte
de longitud 3, etc.
1 1 1 1 0 1 0 1 1 0 0 1 0 0 0

Las rachas de
esta secuencia
están en una
diapositiva
anterior

Si

En la secuencia Si de 15 bits, había 4 rachas de longitud uno, 2
rachas de longitud dos, 1 racha de longitud tres y 1 racha de
longitud cuatro. Este tipo de distribución en las rachas para
períodos impares, es típica de las denominadas m-secuencias
como veremos más adelante en el apartado generadores LFSR.

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 430

Significado del postulado G2

Si

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0

¿Qué significa esto?

Si una secuencia Si como la indicada cumple con G2, quiere
decir que la probabilidad de recibir un bit 1 o un bit 0, después de
haber recibido un 1 o un 0 es la misma, es decir un 50%.
Es decir, recibido por ejemplo un “1”, la cadena “10” deberá ser
igual de probable que la cadena “11”. Lo mismo sucede con un 0
al comienzo, o bien un 00, 01, 10, 11, 000, 001, etc. Existirá así
también una equiprobabilidad en función de los bits ya recibidos.
Como comprobaremos más adelante, esto va a significar que la
secuencia pasa por todos sus estados, es decir todos sus restos.

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

Capítulo 11: Sistemas de Cifra en Flujo

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 431

Tercer postulado de Golomb G3 (1/2)

Postulado G3:

– La autocorrelación AC(k) deberá ser constante

para todo valor de desplazamiento de k bits.

Si

1 0 0 1 1 1 0

Secuencia original

Desplazamiento de un bit a la izquierda
0 0 1 1 1 0 1 AC(1) = (3-7)/7 = -4/7
AC(2) = (3-7)/7 = -4/7
0 1 1 1 0 1 0
1 1 1 0 1 0 0 AC(3) = (3-7)/7 = -4/7

k = 1
k = 2

k = 3

sigue

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 432

Tercer postulado de Golomb G3 (2/2)

1 0 0 1 1 1 0

Secuencia original

k = 4

k = 5

k = 6

k = 7

1 1 0 1 0 0 1 AC(4) = (3-7)/7 = -4/7
1 0 1 0 0 1 1

AC(5) = (3-7)/7 = -4/7

0 1 0 0 1 1 1

AC(6) = (3-7)/7 = -4/7

1 0 0 1 1 1 0

Secuencia original en fase

La secuencia Si = 1001110 de 7 bits cumple con G3

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

Capítulo 11: Sistemas de Cifra en Flujo

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

Capítulo 11: Sistemas de Cifra en Flujo

Página 433

Autocorrelación no constante (1/2)

Si

0 1 1 1 0 1 0 0

Secuencia original

Desplazamiento de un bit a la izquierda

k = 1

k = 2
k = 3
k = 4

1 1 1 0 1