tesisd encriptacion

7/26/2019 tesisd encriptacion

http://slidepdf.com/reader/full/tesisd-encriptacion 1/100

Construccion y evaluacion de un sistema

digital para encriptacion

Carlos Almaguer Lopez

Instituto de Investigacion en Comunicacion Optica

9 de enero de 2006



Contenido

1 Introduccion 2

2 Requerimientos estadısticos y evaluacion de un generador dellaves 82.1 Aleatoriedad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Impredictivilidad . . . . . . . . . . . . . . . . . . . . . . . . . 92.3 Generadores de Numeros Aleatorios (RNG’s) . . . . . . . . . . 92.4 Generadores de Numeros Pseudo - Aleatorios (PRNG’s) . . . . 10

3 Pruebas estadısticas 123.1 Consideraciones para aleatoriedad, impredictivilidad y evalu-

acion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Pruebas Estadısticas de la NIST . . . . . . . . . . . . . . . . . 13

3.2.1 Prueba de frecuencia (monobit) . . . . . . . . . . . . . 153.2.2 Prueba de frecuencia dentro de un bloque . . . . . . . 163.2.3 Prueba de las corridas . . . . . . . . . . . . . . . . . . 163.2.4 Pruebas de la corrida mas larga de unos en un bloque 173.2.5 Prueba del rango de la matriz binaria . . . . . . . . . . 183.2.6 Prueba de la transformada discreta de Fourier (espectral) 183.2.7 Prueba de coincidencia de la plantilla no traslapada . . 183.2.8 Prueba de coincidencia de la plantilla traslapada . . . . 19

3.2.9 Prueba estadıstica universal de Maurer . . . . . . . . . 203.2.10 Prueba de compresion de Lempel-Ziv . . . . . . . . . . 213.2.11 Prueba de la complejidad lineal . . . . . . . . . . . . . 213.2.12 Prueba serial . . . . . . . . . . . . . . . . . . . . . . . 223.2.13 Prueba de entropıa aproximada . . . . . . . . . . . . . 223.2.14 Prueba de sumas acumulativas . . . . . . . . . . . . . . 22

i



ii CONTENIDO

3.2.15 Prueba de excursiones aleatorias . . . . . . . . . . . . . 24

3.2.16 Prueba de excursiones aleatoria (Variante) . . . . . . . 243.3 Criterios para las evaluacion . . . . . . . . . . . . . . . . . . . 24

3.3.1 Eleccion de la longitud de las secuencias a evaluar . . . 263.3.2 Eleccion de los parametros de las Pruebas Parame-

trizadas . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4 Generador de llaves 314.1 Funciones de un solo tiempo . . . . . . . . . . . . . . . . . . . 314.2 Requerimientos del la NIST para el generador de llaves de 15

bits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5 Resultados de las pruebas estadısticas de las NIST 375.1 Criterios para la evaluacion . . . . . . . . . . . . . . . . . . . 38

6 Sistema de encriptacion 536.1 Ecuaciones de encriptacion y desencriptacion . . . . . . . . . . 536.2 Unidad procesadora del texto plano o cifrado. . . . . . . . . . 56

7 Sistema de encriptacion en un microcontrolador. 607.1 Implementacion en Hardware del PRGN . . . . . . . . . . . . 617.2 Procesamiento de paquetes para encriptacion. . . . . . . . . . 64

7.3 Procesamiento de paquetes para desencriptacion. . . . . . . . 647.4 Implementacion en Hardware del sistema completo . . . . . . 667.5 Comunicacion Serial . . . . . . . . . . . . . . . . . . . . . . . 717.6 Configuracion de modem Nulo (Null Modem) . . . . . . . . . 74

7.6.1 Parametros requeridos para la configuracion del puertoRS-232 . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

8 Programa la NIST para la evaluacion de la aleatoriedad degenerados con fines de encriptacion 82

8.0.2 STS GUI 1.6 . . . . . . . . . . . . . . . . . . . . . . . 838.0.3 STS 1.5 . . . . . . . . . . . . . . . . . . . . . . . . . . 84

8.0.4 Reportes . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Bibliografıa 88



Lista de figuras

1.1 En la figura se muestran las ramas de la criptologıa . . . . . . 3

1.2 a) Procesos de encriptacion. b) Procesos de desencriptacion . 5

1.3 Funcionamiento y estructura interna de un Cifrador . . . . . . 6

4.1 a) Generador de 3 bits, b) Generador de 7 bits, c) Generadorde 15 bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2 Estructura del generador de 15 bits . . . . . . . . . . . . . . . 32

4.3 Diagrama de generacion de llaves . . . . . . . . . . . . . . . . 34

4.4 Estructura que debe tener el archivo con las secuencias queseran evaluadas . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.5 Diagrama de flujo del algoritmo generador de llaves . . . . . . 36

5.1 Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el primer archivo evaluado, en la graficase observa que todas las pruebas y subpruebas pasaron sinproblema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2 Histograma correspondiente a la distribucion uniforme de losvalores P para el primer archivo evaluado. . . . . . . . . . . . 42

5.3 Grafica de los valores correspondientes a la proporcion desecuencias exitosas para el segundo archivo evaluado, en lagrafica se aprecia que un valor de la prueba 8 se encuentra pordebajo del limite. . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.4 Histograma correspondiente a la distribucion uniforme de losvalores P para el segundo archivo evaluado. . . . . . . . . . . 43

iii



iv LISTA DE FIGURAS

5.5 Grafica de los valores correspondientes a la proporcion de se-

cuencias exitosas para el tercer archivo evaluado, en la graficase observa que todas las pruebas y subpruebas aprovaron sinproblema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.6 Histograma correspondiente a la distribucion uniforme de losvalores P para el tercer archivo evaluado. . . . . . . . . . . . . 44

5.7 Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el cuarto archivo evaluado, en la graficase observa que todas las pruebas y subpruebas pasaron sinproblema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.8 Histograma correspondiente a la distribucion uniforme de losvalores P para el cuarto archivo evaluado. . . . . . . . . . . . 45

5.9 Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el quinto archivo evaluado, en la graficase observa que todas las pruebas y subpruebas pasaron sinproblema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.10 Histograma correspondiente a la distribucion uniforme de losvalores P para el quinto archivo evaluado. . . . . . . . . . . . 46

5.11 Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el sexto archivo evaluado, en la grafica

se observa que todas las pruebas y subpruebas pasaron sinproblema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.12 Histograma correspondiente a la distribucion uniforme de losvalores P para el sexto archivo evaluado. . . . . . . . . . . . . 47

5.13 Grafica de los valores correspondientes a la proporcion desecuencias exitosas para el septimo archivo evaluado, en lagrafica se observa que todas las pruebas y subpruebas pasaronsin problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.14 Histograma correspondiente a la distribucion uniforme de losvalores P para el septimo archivo evaluado. . . . . . . . . . . . 48

5.15 Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el octavo archivo evaluado, en la graficase observa que todas las pruebas y subpruebas pasaron sinproblema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.16 Histograma correspondiente a la distribucion uniforme de losvalores P para el octsvo archivo evaluado. . . . . . . . . . . . 49



LISTA DE FIGURAS v

5.17 Grafica de los valores correspondientes a la proporcion de se-

cuencias exitosas para el noveno archivo evaluado, en la graficase observa que todas las pruebas y subpruebas pasaron sinproblema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.18 Histograma correspondiente a la distribucion uniforme de losvalores P para el noveno archivo evaluado. . . . . . . . . . . . 50

5.19 Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el decimo archivo evaluado, en la graficase observa que todas las pruebas y subpruebas pasaron sinproblema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.20 Histograma correspondiente a la distribucion uniforme de los

valores P para el decimo archivo evaluado. . . . . . . . . . . . 51

6.1 Ecuaciones para encriptacion y sus fuentes. . . . . . . . . . . . 566.2 Ecuaciones para desencriptacion y sus fuentes. . . . . . . . . . 566.3 Estructura de datos para encriptacion . . . . . . . . . . . . . . 576.4 Estructura de datos para desencriptacion . . . . . . . . . . . . 586.5 Diagrama de operacion del sistema . . . . . . . . . . . . . . . 58

7.1 Distribucion de los procesos entre la PC y el dispositivo pro-gramable. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.2 Conexiones del sistema . . . . . . . . . . . . . . . . . . . . . . 62

7.3 Al introducir la misma semilla en el sistema desarrollado ensoftware y en el sistema desarrollado en hardware se debegenerar la misma secuencia de bits. . . . . . . . . . . . . . . . 63

7.4 Diagrama de operacion del sistema de generacion de paquetesde datos para su encriptacion . . . . . . . . . . . . . . . . . . 64

7.5 Diagrama de operacion del sistema de generacion de paquetesde datos para su desencriptacion . . . . . . . . . . . . . . . . . 65

7.6 Programa que comprueba el buen funcionamiento de la etapade generacion de paquetes de datos . . . . . . . . . . . . . . . 66

7.7 Diagrama del programa que comprueba el buen funcionamiento

de las ecuaciones de encriptacion y desencriptacion . . . . . . 667.8 Configuracion de las lıneas del protocolo desde el microcon-

trolador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687.9 Protocolo de encriptacion . . . . . . . . . . . . . . . . . . . . 687.10 Protocolo de desencriptacion . . . . . . . . . . . . . . . . . . . 697.11 Diagrama de la distribucion los pines del microcontrolador. . . 70

Universidad Autonoma de San Luis Potosı

Fac. de Ciencias - Iico



vi LISTA DE FIGURAS

7.12 Diagrama del MAX-232. . . . . . . . . . . . . . . . . . . . . . 72

7.13 El Max-232 se encarga de acoplar los niveles logicos entre elpuerto RS-232 de la PC y el microcontrolador. . . . . . . . . . 73

7.14 Distribucion de los pines en los conectores DB-9 y DB-25. . . 737.15 Diagrama de conexiones necesarias para implementar un mo-

dem nulo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757.16 Conexiones del sistema via puerto RS-232 . . . . . . . . . . . 757.17 La instruccion VISA Configure Serial Port, permite configurar

todos los parametros necesarios para el RS-232 . . . . . . . . . 77

8.1 Pantalla principal Nist Statistical Test suite . . . . . . . . . . 83

8.2 Pantalla de seleccion de las pruebas a ejecutar y alimentacionde parametros . . . . . . . . . . . . . . . . . . . . . . . . . . . 848.3 Pantalla principal Nist Statistical Test suite . . . . . . . . . . 86



Lista de tablas

1.1 Tabla de equivalencia de caracteres en el metodo Cesar paraun corrimiento de tres posiciones a la derecha . . . . . . . . . 3

3.1 Division de las pruebas en parametrizadas y no parametrizadas 15

3.2 En la tabla se muestran las longitudes permitidas para losbloques, estas longitudes estan en funcion de la longitud de lasecuencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3 Tabla para elegir los parametros de la prueba. . . . . . . . . . 21

3.4 Longitud de bits requerida para cada prueba. . . . . . . . . . 27

3.5 Tabla de los parametros para las pruebas parametrizadas. . . . 30

5.1 Tabla de asignacion de numeros a cada prueba . . . . . . . . . 39

5.2 En la tabla se muestra la cantidad de subpruebas con quecuenta cada prueba para la evaluacion de 300 secuencias. . . 40

5.3 En esta tabla se concentran los resultados obtenidos por losdiez archivos de secuencias que fueron evaluados utilizando elprograma estadstico de la NIST. . . . . . . . . . . . . . . . . . 52

7.1 Lıneas del protocolo desarrollado para la comunicacion entreel PIC y la PC mediante la tarjeta DIO32HS. . . . . . . . . . 67

7.2 Niveles logicos para el estandar RS-232 . . . . . . . . . . . . . 72

7.3 En la tabla se muestran las lıneas de comunicacion serial conel estandard RS-232 y su ubicacion en los conectores DB9 yDB25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.4 En esta tabla se muestra la funcion de cada una de las lıneasdel estandar RS-232. . . . . . . . . . . . . . . . . . . . . . . . 79

7.5 En la tabla se muestran las configuraciones para el bit de paridad. 80

vii



LISTA DE TABLAS 1

7.6 Relacion entre velocidad y distancia maxima de un cable para

el RS-232. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 807.7 Seleccion de parametros para la paridad en LabView. . . . . . 807.8 Seleccion de parametros para los bits de parada en LabView. . 817.9 Parametros necesarios para la configuracion del puerto RS-232

en el microcontrolador. . . . . . . . . . . . . . . . . . . . . . . 81





Resumen

El objetivo de la tesis es probar un generador de numeros pseudo-aleatoriosbasado en sincronizacion en automatas celulares[28, 36, 37] utilizando laspruebas estadasticas especializadas para este fin, las cuales son proporcionadaspor la National Institution of Standards and Technologies [3] de EstadosUnidos de Norteamerica. Una vez pasadas dichas pruebas estadısticas im-plementar el sistema de encriptacion que utiliza dicho generador de numerospseudo-aleatorios en un microcontrolador.



CAPITULO 1

Introduccion

En la actualidad las telecomunicaciones juegan un papel muy importante, lainformacion que fluye por los canales de comunicacion es de gran trascen-

dencia y muy valiosa tanto para el que este destinado a recibirla, como parael que le interese saber su contenido, es por eso que ha surgido el fen omenode robo de informacion y mas ahora, que se han roto las barreras de los ca-bles con la comunicacion inalambrica, se podrıa decir que la informacion seencuentra virtualmente al alcance de cualquiera.

Desde tiempos muy remotos el hombre ha ingeniado metodos para poderocultar informacion, de manera de que solamente quien conozca el metodocon el cual se oculto la informacion sea capaz de saber su contenido, estoha marcando los inicios de la ciencia de la criptografıa (kryptos ”ocultar”),

(graphos ”escribir”).Un ejemplo muy claro de la criptografıa antigua es elmetodo Cesar, atribuido al emperador romano Julio Cesar, este se basa enla sustitucion de los caracteres del mensaje original, por caracteres de unalfabeto recorrido x posiciones del alfabeto normal. En la tabla 1.1 se muestrael alfabeto normal con la correspondencia de sustitucion del alfabeto Cesar,el cual esta recorrido tres posiciones del alfabeto normal.

2



3

ALFABETO A B C D E F G H I J K L M N

A.CESAR D E F G H I J K L M N N O PALFABETO N O P Q R S T U V W X Y Z

A.CESAR Q R S T U V W X Y Z A B C

Tabla 1.1: Tabla de equivalencia de caracteres en el metodo Cesar para uncorrimiento de tres posiciones a la derecha

Por lo tanto si quisieramos encriptar el siguiente mensaje ”PRUEBADE ENCRIPTACION” utilizando el metodo Cesar con corrimiento de tres

unidades a la derecha, se sustituye cada letra del alfabeto normal, por suequivalente en el alfabeto Cesar, entonces basandonos en la tabla 1.1 el re-sultado es el siguiente.

Mensaje original : ”PRUEBA DE ENCRIPTACION”

Mensaje encriptado : ”SUXHED GH HPFULSWDFLRP”

La criptografıa es la disciplina cuya funcion es crear sistemas de en-

criptacion y desencriptacion, pero tambien existe su contraparte; el crip-toanalisis que se dedica al rompimiento de los sistemas de encriptacion. Es-tas disciplinas en conjunto forman lo que se llama criptologıa, ver figura 1.1.Muy comunmente se confunde el termino de criptografıa con el de criptologıa.

Figura 1.1: En la figura se muestran las ramas de la criptologıa

Al proceso que transforma la informacion de su forma original a una formaen la que no sea posible saber su contenido real se le llama encriptacion para





4 Introduccion

lo cual se requiere de una llave que se utilizara para encriptar la informacion.

Al proceso inverso se le conoce como desencriptacion. Y solamente aquel quetenga conocimiento de la llave que se utilizo para encriptar podra desencriptarsu contenido.

Existen dos tipos de algoritmos de encriptacion basados en llaves, losalgoritmos simetricos (o de llave secreta) y los asimetricos (o de llave publica).La diferencia es que los simetricos usan la misma llave para encriptacion ydesencriptacion o la llave de desencriptacion es facilmente derivada de lallave de encriptacion. Mientras que los algoritmos asimetricos usan una llavediferente para encriptacion y desencriptacion y la llave de desencriptacion

no puede ser derivada de la llave de encriptacion. Los algoritmos simetricospueden ser divididos en cifradores de corriente (stream cipher) y cifradoresde bloques. Los cifradores de corriente pueden encriptar un bit cada vez, encambio los cifradores de bloques toman un numero de bits y los encriptancomo una sola unidad.

Los cifradores asimetricos tambien conocidos como algoritmos de llavepublica, permiten que la llave de encriptacion sea publica, y de esta maneraque cualquiera encripte utilizando esta llave y solo el que conozca la llave dedesencriptacion va a poder desencriptar el mensaje. La llave de encriptaciones tambien llamada llave publica y la llave de desencriptacion, llave secreta

o privada.

La criptografıa, en el contexto de la tecnologıa, es la ciencia que estudialos metodos y procedimientos para modificar los datos mediante algoritmosmatematicos, de tal manera que solamente las personas que tengan la llaveprivada adecuada puedan tener acceso a la version original de los mismos(confidencialidad) y ademas de que podran estar seguros de que los datos nofueron modificados entre el remitente y el destinatario (integridad).

En el proceso de encriptacion el mensaje original es conocido como textoplano (plaintext) que al ser procesado junto con una llave por el algoritmo de

encriptacion llamado cifrador (cipher) se convierte en el mensaje encriptadollamado texto cifrado (ciphertext), de esta manera se encripta la informaciontal y como se muestra en la fig 1.2 a); y para desencriptar el algoritmo dedesencriptacion procesa el texto cifrado junto con la misma llave privada quese utilizo para encriptar la informacion y de esta manera se obtiene comoresultado el texto plano como se muestra en la ilustracion 1.2 b).



5

Figura 1.2: a) Procesos de encriptacion. b) Procesos de desencriptacion

Hace algunos anos los unicos usuarios de la criptografıa eran los gobiernosy los militares; en la segunda guerra mundial la encriptacion de informacionfue vital, y esta se basaba en aparatos electricos y electromecanicos. En laactualidad la seguridad de la informacion es tan necesaria y comun que todoaquel que navega en internet esta haciendo uso de la criptografıa aun sindarse cuenta de ello.

La criptografıa hoy en dıa involucra varias formas de encriptacion y des-encriptacion, ası como diferentes metodos de autentificacion. Estos metodosy sus aplicaciones siguen siendo cada vez mas complejos ya que la crip-tografıa como tal sigue girando fundamentalmente alrededor de problemas

matematicos difıciles de solucionar. Y se pueden complicar mas sino secuenta con los requerimientos matematicos o de computo necesarios parasolucionar o decodificar el mensaje encriptado.

Las aplicaciones de la criptografıa no solo se limitan a las computadoras,existen companias que comercializan sistemas que encriptan o desencriptarla informacion en tiempo real en PDA’s, telefonos, fax, etc., y ademas de pro-teger datos, tambien es posible autentificar identidades por medio de firmasdigitales, proteccion contra copiado, certificados digitales, etc.

Una de las partes mas importantes de un cifrador es la que genera se-cuencias de numeros que utilizando ecuaciones o algoritmos disfraza los datosoriginales para este fin se utilizan generadores de numeros aleatorios o bien

generadores de numeros pseudo-aleatorios, por eso es importante que las se-cuencias generadas sean de calidad estadısticamente hablando ya que si estasse pueden predecir facilmente, el algoritmo sera vulnerable. En la figura 1.3se puede observar la estructura interna de un cifrador en donde se utiliza ungenerador de numeros pseudo-aleatorios para esconder el texto que se quiereencriptar.





6 Introduccion

Figura 1.3: Funcionamiento y estructura interna de un Cifrador

Existen muchos algoritmos de encriptacion, pero dependiendo de nuestrasnecesidades debemos escoger un balance entre seguridad y velocidad, uno delos algoritmos mas usados y conocidos es el

, cuyas iniciales son los apellidos de sus creadores Ron Rivest, Adi Shamir yLen Adleman, este algoritmo fue el primero que fue utilizado para encriptar ofirmar digitalmente, y es el algoritmo de llave publica mas popular. A pesarde que es conocido desde 1977, aun es considerado seguro si se trabaja conllaves suficientemente grandes. La generacion de llaves esta basada princi-palmente en la multiplicacion de 2 numeros primos muy grandes y no muy

cercanos entre sı. Apartir de estos numeros se comienzan a generar las llavessubsecuentes. Debido a que con este algoritmo se puede encriptar y firmardigitalmente es importante que las llaves privadas para cada proceso seandiferentes para comprobar la autenticidad de la informacion.

Otro estandar muy conocido es el DES

(Data Encryption Standard), dado a conocer en noviembre de 1976, causomucha polemica desde su aparicion y aceptacion como estandar por la NBS(Nacional Bureau of Standards) hoy llamada NIST

(National Institute of Standards and Technology). Este algoritmo hoy endıa es considerado debil, el DES fue utilizado por la cadena HBO para cod-

ificar su senal en 1986. El algoritmo esta basado en dos permutaciones unainicial y una final, y consta de 16 etapas identicas que estan basadas enuna funcion Feistel y en Xor’s, la funcion Feistel hace que la encriptaciony desencriptacion sean practicamente identicas y se utilize el mismo algo-ritmo para ambas. El gran logro de este algoritmo ironicamente no fue laencriptacion sino que desperto el interes en el estudio de como descifrar el



7

algoritmo (criptoanalisis), la debilidad de este algoritmo fue demostrada a fi-

nales de los 90’s. Apartir del DES se generaron otros algoritmos mas seguroscomo lo es el Triple DES que no es sino el mismo DES

usado 3 veces seguidas en cascada para encriptar los datos, usando 3 llavesdistintas para aumentar su seguridad, pero debido a su lentitud este algoritmono es muy comun para aplicaciones de software, aunque es muy utilizado enaplicaciones de hardware, y es el estandar en algunas companias como Nextel,de esta manera se pueden seguir listando muchos algoritmos, con propiedadesy caracterısticas diferentes.

Con el avance y desarrollo de equipos de computo cada vez mas poderosos,los algoritmos se hacen mas vulnerables a ataques, debido a que la capacidad

de procesamiento en las computadoras aumenta y es mas rapido encontrarla manera de descifrar el algoritmo con la ayuda de equipos de computosofisticados. El criptoanalisis, se puede decir que es un ataque de fuerzabruta, que no es mas que tratar de ”adivinar” la llave privada, este metodo esde prueba y error, busca la posible llave una por una, hasta encontrarla, esteproceso es lento y en muchos casos es impractico cuando la llave es demasiadolarga puede llevar varios cientos de anos descifrar la llave adecuada. Laevaluacion de la aleatoriedad es uno de los puntos cruciales para la seguridadde los generadores de llaves de los sistemas de encriptacion.

En esta tesis se trabajo en un sistema de encriptacion que esta basado

en un algoritmo de encriptacion por sincronizacion en automatas celulares[1] dicho algoritmo debe cumplir ciertos requerimientos para poder ser con-siderado confiable para su uso en criptografıa. Para eso debe cumplir conlos criterios establecidos por la NIST [3](National Institute of Standards andTechnology) . Una parte importante de este trabajo es la evaluacion del gen-erador de llaves de este sistema usando las pruebas estadisticas de la NIST,y una vez comprobada la seguridad del sistema, realizar una aplicaci on enhardware de facil uso para encriptacion de informacion en una PC.





CAPITULO 2

Requerimientos estadısticos y evaluacion deun generador de llaves

Como anteriormente se menciono una de las partes mas importantes de uncifrador es el generador de secuencias de numeros (llaves) con los que se en-cripta la informacion. Si estos numeros se pudieran predecir, la informacionserıa descifrada facilmente. Por lo tanto estas secuencias deben ser impre-

descibles y tienen que ser generados aleatoriamente o pseudo-aleatoriamente.

2.1 Aleatoriedad

Se puede decir que existen niveles de aleatoriedad, por ejemplo no se re-quiere el mismo nivel de aleatoriedad para producir una tirada de dados enun videojuego, que para una aplicacion de criptografıa. La perfecta pro-duccion de numeros aleatorios se puede representar de la siguiente forma;si tenemos un generador de 10 bits, cada bit se debe ver como independi-ente de los otros nueve, como si por cada bit se tuviera una moneda mar-

cada y que en cada tirada diera un ”1” o un ”0” con la probabilidad de1/2 de salir, de esta manera garantizamos que cada volado es independi-ente del anterior y podemos decir que es completamente aleatorio. Por otrolado matematicamente no podemos disenar una moneda electronica que secomporte como una real, lo que se hace es que por medio de algoritmos yecuaciones matematicas emular la moneda, pero solo las pruebas estadısticas

8



2.2 Impredictivilidad 9

podran decir si los valores generados son realmente pseudo-aleatorios, ya que

se esta utilizando un proceso determinıstico para emular otro proceso que nolo es.

2.2 Impredictivilidad

La impredicitibilidad va ligada a la aleatoriedad, pero sin embargo que algosea aleatorio no garantiza que sea impredescible, al existir algun patrono comportamiento perıodico en una secuencia dejara de ser impredecible.Distinguir estadısticamente la aleatoriedad ”aparente” de la ”verdadera” esun proceso difıcil y asegurar la impredictibilidad es aun mas difıcil, mu-chos fenomenos aleatorios pueden presentar caracterısticas organizadas, o pa-trones en su comportamiento. Por ejemplo no debe ser posible saber el valorde una llave generada en un sistema, a pesar de que tengamos conocimientode los valores anteriores de la secuencia de llaves (forward unpredictabil-ity) y tampoco debera ser posible determinar los valores iniciales apartirde algunos de los valores generados (backward unpredictability). En 1955la compania RAND Corp. hizo una publicacion que incluıa un millon denumeros aleatorios, esta publicacion es util para varios tipos de aplicaciones,pero definitivamente es inservible para fines de encriptacion ya que dichosnumeros son aleatorios, pero el inconveniente es que cualquiera que tenga

conocimiento de dicha publicacion sabra cuales fueron los numeros utiliza-dos para encriptar, y por lo tanto dejan de ser impredescibles. Cuando seaplica el criptoanalisis a un sistema criptografıco, lo que se busca es deducirla forma en que trabaja, para ası lograr predecir las secuencias que genera ypoder desencriptar datos que fueron encriptados utilizando dicho sistema.

2.3 Generadores de Numeros Aleatorios (RNG’s)

Los Generadores de Numeros aleatorios o mas conocidos por sus siglas eningles RNG (Random Number Generator), utilizan medios fısicos para la

generacion de datos. Algunos ejemplos son el ruido electrico, el bit menos sig-nificativo en un ADC, los movimientos hechos en un mouse, los movimientoscuanticos en un semiconductor, etc; existe una infinidad de posibles fuentes dedatos para un RNG; las salidas de un RNG deben cumplir estrictos criteriosestadısticos de aleatoriedad, a los datos resultantes de un RNG se les aplicanpruebas que buscan patrones que muestren evidencia de no-aleatoriedad. Por





10Requerimientos estadısticos y evaluacion de un generador de

llaves

ejemplo la salida de un RNG que tiene como fuente de alimentacion ruido

electrico, pudiera presentar patrones repetitivos ya que como es sabido estetipo de ruido puede llegar a tener estructuras organizadas o repetitivas, y deesta manera los datos generados no pasarıan las pruebas de aleatoriedad yel generador serıa considerado no-aleatorio estadısticamente. Este problemapuede ser contrarrestado utilizando varias fuentes aleatorias para alimentar elRNG, pero el problema es que el procesamiento tiende a ser lento cuando estosucede, la principal desventaja de los RNG’s es que para fines de encriptacionse necesita generar la secuencia de numeros aleatorios que se usaron para en-criptar los datos, y para desencriptar es necesario volver a generar la mismasecuencia que se utilizo para encriptar los datos, pero como fueron generados

aleatoriamente es practicamente imposible volver a generarlos, por lo tantouna vez que se genera un secuencia para encriptar, es necesario guardarlapara poder usarla en la desencriptacion, haciendo vulnerable al sistema yaque si alguien obtiene esa secuencia facilmente podra desencriptar los datos.

2.4 Generadores de Numeros Pseudo - Aleatorios(PRNG’s)

Los Generadores de Numeros Pseudo-Aleatorios o mas conocidos por sus

siglas en ingles PRNG (Pseudo-Random Number Generator), se basan enmetodos deterministicos tales como ecuaciones y/o algoritmos matematicos,la gran ventaja y diferencia con los RNG, es que un PRNG debe ser alimen-tado con un valor inicial, llamado ”Semilla” y apartir de esta se producirala secuencia de datos aleatorios y cada valor subsecuente se ir a generandoapartir del dato anterior utilizando algun algoritmo. Para cada semilla segenerara una secuencia de datos diferente y por lo tanto para reproducir unasecuencia solo basta con utilizar la misma semilla inicial. Un PRNG bienformulado es capaz de generar numeros que pasen las pruebas estadısticas dealeatoriedad, y tengan las propiedades de un numero aleatorio, aun sin serlodel todo (de aquı el termino Pseudo-aleatorio), ironicamente en ocasiones los

numeros pseudo-aleatorios presentan estadısticamente mas aleatoriedad quelos mismos numeros aleatorios obtenidos de fuentes fısicas, esto se debe aque cada valor de la secuencia es producido a partir de su valor anterior vıatransformaciones que aparentan introducir aleatoriedad adicional, como unaserie cuyas transformaciones pueden eliminar autocorrelaciones estadısticasentre entrada y salida. Por lo tanto las salidas de un PRNG puede tener



2.4 Generadores de Numeros Pseudo - Aleatorios (PRNG’s) 11

mejores propiedades estadısticas y producir datos confiables mas rapido queun RNG. En el caso de los PRNG’s, si la semilla es desconocida, el siguien-te numero en la salida de la secuencia debera ser impredescible. No debehaber evidente correlacion entre la semilla y alguno de los valores generados;cada elemento de la secuencia debe aparentar venir de un evento aleatorioindependiente cuya probabilidad sera de 1/2.





CAPITULO 3

Pruebas estadısticas

Una secuencia aleatoria puede ser caracterizada y descrita en terminos deprobabilidad, si se prueban estadısticamente secuencias que se sabe que sonaleatorias se espera obtener ciertos resultados que confirmen su aleatoriedad,entonces si se evalua una secuencia de la cual se desconoce su aleatoriedad,se esperara un comportamiento parecido al de las secuencias aleatorias, de

lo contrario se habra detectado evidencia de no-aleatoriedad.Existen infinidad de pruebas estadısticas que demuestran la ausencia de

aleatoriedad, y estas se pueden agrupar en conjuntos de pruebas, pero ningunconjunto esta estadısticamente completo, el tipo de pruebas aplicadas depen-dera de la aplicacion a la que esta destinado el PRNG o RNG y su objetivo esbuscar ciertas debilidades en las secuencias generadas que puedan afectar sudesempeno segun su aplicacion y el hecho que pase las pruebas no garantizaque las secuencias sean aleatorias, significa que las pruebas no encontraronevidencias de no-aletoriedad que afecten el desempeo del generador en laaplicacion a la que esta destinado.

El PRNG utilizado en este trabajo tiene fines de encriptacion, las secuen-cias generadas deben cumplir estrictos requerimientos estadısticos para serconsiderados aptas para dicha aplicacion. Para lo cual existen varios conjun-tos de pruebas especializadas enfocadas hacia PRNGs y RNG’s por ejemploDIEHARD [19], Crypt-x [18], y el conjunto de pruebas estadısticas de la Na-tional Institute of Standards and Technologies[3], de Estados Unidos, entreotras. Estos conjuntos de pruebas mencionados tienen pruebas en comun.

12



3.1 Consideraciones para aleatoriedad, impredictivilidad yevaluacion 13

3.1 Consideraciones para aleatoriedad,impredictivilidad y evaluacion

Una secuencia aleatoria o pseudo-aleatoria tiene cierto comportamiento ypropiedades con respecto a la aleatoriedad e impredictivilidad. Las siguientespropiedades deben ser tomadas en cuenta al evaluar una secuencia aleatoriabinaria.

1. Uniformidad: En cualquier punto de la generacion de una secuenciaaleatoria o pseudoaleatoria de bits, la ocurrencia de un cero o uno es

exactamente la misma, la probabilidad de cada uno es de 1/2. Lacantidad esperada de ceros o de unos es n/2, en donde n = Longituden bits de la secuencia.

2. Escalabilidad: Cualquier prueba aplicable a una secuencia tambienpuede ser aplicada a subsecuencias extraıdas al azar. Si una secuen-cia es aleatoria, entonces cualquier subsecuencia extraıda tambien seraaleatoria. Por consecuencia, cualquier subsecuencia extraıda deberapasar cualquier prueba de aleatoriedad.

3. Consistencia: El comportamiento de un generador debe ser consistente

con respecto a las semillas, es inadecuado probar un PRNG basado enla salida de una semilla unica o un RNG basado en la salida producidapor una sola fuente fısica.

3.2 Pruebas Estadısticas de la NIST

El conjunto de pruebas estadısticas de la National Institute of Standards andTechnology (NIST)[3] contiene procesos utiles para detectar desviaciones dela aleatoriedad de una secuencia binaria. Debido a que todo esto depende dela probabilidad, se espera un cierto numero de fallas en secuencias aleatorias

producidas por algun generador en particular; incluso Pierre L’Ecuyer quienes un investigador reconocido en esta materia, escribio, ”Construir un RNGque pase todas las pruebas estadısticas es un sueno imposible”. Estas prue-bas estadısticas estan formuladas para probar una especifica hipotesis nula,para el proposito de este documento la hipotesis nula bajo prueba es que lasecuencia que se esta probando es aleatoria. Asociada a esta hipotesis nulase encuentra la hipotesis alternativa, que se refiere a que la secuencia es no





14 Pruebas estadısticas

aleatoria. Una vez que se apliquen las pruebas el resultado sera la aceptaciono bien el rechazo de la hipotesis nula.

El conjunto de pruebas de la NIST consta de 16 pruebas estadısticasque fueron desarrolladas para probar la aleatoriedad de secuencias binariasgeneradas por software o por hardware y producidas ya sea por generadoresaleatorios o pseudo-aleatorios para fines de encriptacion. Las pruebas se cen-tran en diferentes tipos de no-aleatoriedad que puede existir en una secuenciagenerada. Las 16 pruebas son:

1. Prueba de frecuencia (monobit)

2. Prueba de frecuencia dentro de un bloque

3. Prueba de las corridas

4. Pruebas de la corrida mas larga de unos en un bloque

5. Prueba del rango de la matriz binaria

6. Prueba de la transformada discreta de Fourier (espectral)

7. Prueba de coincidencia de la plantilla no traslapada

8. Prueba de coincidencia de la plantilla traslapada

9. Prueba estadıstica universal de Maurer

10. Prueba de compresion de Lempel-Ziv

11. Prueba de la complejidad lineal

12. Prueba serial

13. Prueba de entropıa aproximada

14. Prueba de sumas acumulativas

15. Prueba de excursion aleatoria

16. Prueba de excursion aleatoria (Variante)



3.2 Pruebas Estadısticas de la NIST 15

Estas pruebas pueden ser de dos tipos, parametrizadas o no parame-trizadas, las primeras necesitan que el usuario alimente el programa conparametros extra, que son indispensables para ejecutar dichas pruebas, y lasno parametrizadas solo necesitan las secuencias de bits que seran evaluadas.En la tabla 3.5 se muestran las pruebas agrupadas segun su clasificacion.

Pruebas no Parametrizadas Pruebas ParametrizadasFrecuencia (monobit) Frecuencia dentro de un bloque

Corridas Plantilla traslapadaCorrida mas larga de unos Plantilla no traslapada

Rango de la matriz binaria SerialTransformada discreta de Fourier Universal de MaurerCompresion de Lempel-Ziv Complejidad lineal

Sumas Acumulativas Entropıa aproximadaExcursion aleatoria

Excursion aleatoria (variante)

Tabla 3.1: Division de las pruebas en parametrizadas y no parametrizadas

A continuacion se da una breve descripcion de estas pruebas y sus prin-cipales caracterısticas.

3.2.1 Prueba de frecuencia (monobit)

Esta prueba checa que la proporcion de unos y ceros sea aproximadamente lamisma. Con esto se demostrarıa la propiedad de uniformidad anteriormentemencionada. La forma en que trabaja esta prueba es muy simple, cada 1 dela secuencia es sustituido por un +1, y cada 0 es reemplazado por un −1,de esta manera la secuencia se convierte en una suma cuyo resultado idealdebera ser igual a cero o al menos no debera alejarse mucho de este valor.

Por ejemplo si se tiene la pequena secuencia = 1011010100, donde n = 10

Sustituyendo 1 por +1 y 0 por −1 la suma darıa:

S n = 1 + (−1) + 1 + 1 + (−1) + 1 + (−1) + 1 + (−1) + (−1) = 0






La suma Sn debera ser cercana a cero o de lo contrario la prueba nosestarıa mostrando patrones de no aleatoriedad. Las pruebas subsecuentesdependen del resultado de que esta prueba se pase. Esta prueba es no para-metrizada, y requiere de secuencias de al menos 100 bits y no indica un topemaximo de bits.

3.2.2 Prueba de frecuencia dentro de un bloque

Es una variante de la prueba de frecuencia monobit, la diferencia es que estaprueba parte la secuencia de longitud n, en N bloques de longitud de M

bits, para ası determinar la cantidad de unos y ceros dentro de dichos bloques.El proposito de la prueba es determinar si la frecuencia de unos dentro deun bloque de M bits es M/2 como se espera de una secuencia aleatoria, siel tamano del bloque es M = 1 se estarıa realizando la prueba de frecuencia(monobit). Esta prueba es parametrizada y requiere ser alimentada con elparametro M que es la longitud de los bloques la cual se calcula bajo lassiguientes consideraciones:

n ≥ 100, n ≥ MN,

M debe ser elegido de tal forma que :

M ≥ 20, M ≥ 0.01n y N < 100

3.2.3 Prueba de las corridas

Determina el numero de corridas en una secuencia , en donde una corridaes una secuencia ininterrumpida de bits identicos, entonces una corrida delongitud k son k bits identicos sin ningun bit opuesto entre ellos y con unbit de valor opuesto de cada lado, el proposito es identificar si el numero decorridas de unos y ceros de varias longitudes son las que se esperan de unasecuencia aleatoria, ademas de determinar si la velocidad de oscilacion entreunos y ceros es rapida o lenta. Por ejemplo.




Se tiene la secuencia

= 111010100101101000

Agrupando las corridas de unos y de ceros

= 111010100101101000

Tenemos las siguientes corridas :

1 corrida de unos con 2 bits1 corrida de unos con 3 bits

1 corrida de ceros de 2 bits

1 corrida de ceros de 3 bits

Apartir de estos datos el programa calcula ciertos valores que seran uti-lizados para tomar una determinacion sobre la supuesta aleatoriedad de lasecuencia, cada secuencia debe tener una longitud n ≥ 100. Esta prueba esno parametrizada por lo tanto no es necesario introducir ningun parametro

para ejecutarla.

3.2.4 Pruebas de la corrida mas larga de unos en un bloque

Esta prueba se concentra en la corrida mas larga de unos dentro de un bloquede M bits dentro de una secuencia . El proposito de esta prueba, es deter-minar si la longitud de la corrida mas larga de unos dentro de la secuenciaprobada, es consistente con la longitud de la corrida mas larga de unos es-perada de una secuencia aleatoria, observar una irregularidad en la longitudesperada de la corrida mas larga de unos, implica que tambien existe unairregularidad en la longitud esperada de la corrida mas larga de ceros. Por lo

tanto, solo es necesario probar la corrida mas larga de unos. Cada secuencia a evaluar debe tener una longitud n ≥ 100. Esta es una prueba parame-trizada y el parametro que se debe proporcionar al programa es el tamanode los bloques de M bits los cuales solo pueden ser de alguna de las treslongitudes permitidas y estas longitudes estan en funcion de la longitud n dela secuencia . En la tabla 3.2 se muestran las longitudes permitidas para losbloques de M bits, de acuerdo a la longitud n de la secuencia .






Longitud mınima de la serie M128 8

6,272 12875,000 10,000

Tabla 3.2: En la tabla se muestran las longitudes permitidas para los bloques,estas longitudes estan en funcion de la longitud de la secuencia

3.2.5 Prueba del rango de la matriz binaria

Esta prueba se concentra en el rango de sub-matrices disjuntas de la secuenciaentera. El proposito de esta prueba es checar la dependencia lıneal entre sub-cadenas compuestas de la secuencia original, esta prueba tambien aparece enla baterıa de pruebas diehard [19], y es no parametrizada, pero internamentemaneja los parametros M y Q que son el tamano de las columnas y renglonesde las matrices que creara el programa para evaluar la aleatoriedad de lassecuencias y estan predeterminadas ambas a 32, esto significa que la pruebacrea matrices disjuntas de 32 x 32 apartir de la secuencia, el tamano n de lassecuencias a evaluar debe cumplir con la relacion n ≥ 38MQ.

3.2.6 Prueba de la transformada discreta de Fourier (espectral)

Esta prueba mide la altura de los picos en la transformada discreta de Fourierde la secuencia y detecta el numero de picos que excedan el umbral del 95%de altura, el proposito de esta prueba es detectar patrones repetitivos queesten cerca uno de otro. La longitud de las secuencias a evaluar esta dadapor n ≥ 1000, donde n es el numero de bits de la secuencia. La prueba sebasa en el mismo principio de la prueba de la frecuencia monobit, cambiandoen la secuencia cada 1 por +1 y cada 0 por −1, para despues calcular latransformada discreta de Fourier de dicha secuencia, apartir de la cual segenera una secuencia de variables complejas que representan componentesperiodicos de la secuencias de bits a diferentes frecuencias. Esta prueba esno parametrizada.

3.2.7 Prueba de coincidencia de la plantilla no traslapada

Esta prueba genera una ventana de m bits que se va deslizando a lo largode la secuencia de n bits, en busca de patrones predeterminados tambien




de m bits que son extraıdos desde plantillas cargadas en librerıas del pro-grama, estos patrones son caracterısticos de no periodicidad, la prueba haceun recuento de con que tanta frecuencia fueron detectados dichos patrones,para ası poder tomar una determinacion sobre la supuesta aleatoriedad. Estaprueba es parametrizada y el unico parametro necesario es la longitud de laventana que buscara los patrones de esa misma longitud, el programa admitevalores desde m = 2 hasta m = 10 pero recomienda que m sea elegida pref-erentemente entre m = 8 o m = 9. Si la ventana de m bits no encuentra unpatron se desliza un bit hacia delante en la secuencia para seguir buscando,pero si un patron es encontrado la ventana se posiciona un bit despues del

patron encontrado para reanudar la busqueda. Por ejemplo

Si se tiene una secuencia y m = 8

= 10110101100011110101010101010001010

Si no encuentra coincidencia con alguna plantilla se desplaza 1 bit.

= 10110101100011110101010101010001010

En caso de encontrar coincidencia con alguna plantilla se desplaza hasta unbit despues del patron encontrado bit.

= 10110101100011110101010101010001010

Hay que tener en cuenta que esta prueba solo fue disenada para unasecuencia de longitud n = 106. Y no puede ser de ninguna otra longitud.

3.2.8 Prueba de coincidencia de la plantilla traslapada

Esta prueba es una variante de la prueba de la plantilla no traslapada, launica diferencia con la prueba de coincidencia de la plantilla no traslapadaes cuando un patron es encontrado la ventana solo se desliza un bit y no mbits como en su otra variante. Por ejemplo






Si se tiene una secuencia y m = 8

= 10110101100011110101010101010001010

Si no encuentra coincidencia con alguna plantilla se desplaza 1 bit.

= 10110101100011110101010101010001010

En caso de encontrar coincidencia con alguna plantilla se desplaza hasta unbit despues del patron encontrado bit.

= 10110101100011110101010101010001010

Esta prueba al igual que la prueba de la plantilla no traslapada fuedisenada para una longitud de la secuencia de n = 106. Y no puede serde ninguna otra longitud.

3.2.9 Prueba estadıstica universal de Maurer

Esta prueba checa el numero de bits que tienen parametros coincidentesdentro de la secuencia (medida que esta relacionada con la compresibilidaddel sistema), la finalidad es saber si la secuencia puede ser comprimida sin

perdida significativa de informacion, ya que una secuencia que puede sercomprimida significativamente sin perdida de informacion se considera noaleatoria, esta prueba es parametrizada y parte la secuencia en dos segmentosun segmento de inicializacion Q que a su vez esta dividido en bloques de Lbits, y un segmento de prueba K que tambien esta dividido en bloques de Lbits. Los parametros de esta prueba son elegidos en base a la longitud n delas secuencias, los valores se muestran en la tabla 3.3.




n L Q = 10 22

≥387,840 6 640≥904,960 7 1,280≥2,068,480 8 2,560≥4,654,080 9 5,120≥1,342,400 10 10,240≥22,753,280 11 20,480≥49,643,520 12 40,960≥107,560,960 13 81,920≥231,669,760 14 163,840

≥496,435,200 15 327,680≥1,059,061,760 16 655,360

Tabla 3.3: Tabla para elegir los parametros de la prueba.

3.2.10 Prueba de compresion de Lempel-Ziv

Esta prueba se concentra en el numero de patrones acumulados diferentesen la secuencia y que tanto se repiten, al igual que en la prueba estadıstica

universal de Maurer el proposito de esta prueba es determinar que tanto sepuede comprimir la secuencia probada, y esta es considerada no aleatoria sipuede ser comprimida significativamente. Una secuencia aleatoria tendra unnumero caracterıstico de patrones.

El proceso consiste en ir registrando cada nueva combinacion de bits enun diccionario de patrones, y contar las veces que se repite cada patronpara poder saber que tanto puede ser comprimida la secuencia y ası dar unveredicto sobre su aleatoriedad, esta prueba es no parametrizada y la longitudde la secuencia n debe cumplir n ≥ 106.

3.2.11 Prueba de la complejidad linealEsta prueba se concentra en la longitud de un LFSR [9](registro de corrim-iento retroalimentado linealmente) . El proposito de esta prueba es determi-nar si la secuencia es considerada suficientemente compleja para ser consid-erada aleatoria. Las secuencias aleatorias tienen como caracterıstica LFSR’slargos. Un LFSR muy corto implica no aleatoriedad. Esta prueba parte lasecuencia en bloques de longitud M para despues por medio del algoritmo






Berlekamp-Massey [6] calcular la complejidad lineal de cada bloque. Estaprueba es parametrizada y requiere que el usuario proporcione la longitudM de los bloques a los que sera aplicado el algoritmo mencionado anteri-ormente, la prueba requiere que se cumplan las siguientes condiciones: lalongitud n de las secuencias a evaluar debe cumplir que n ≥ 106, el valor deM debe estar dentro del rango de 500 ≤ M ≤ 5000 y la cantidad de bloquesN dentro de la secuencia debe ser N ≥ 500.

3.2.12 Prueba serial

Esta prueba checa la frecuencia de todos los posibles patrones traslapados dem bits dentro de la secuencia entera, con el proposito de verificar si el numerode ocurrencias de patrones traslapados de todos los posibles vectores de mbits se aproxima al que se espera de una secuencia aleatoria. Una secuenciaaleatoria tiene uniformidad, esto significa que cada patron de m bits tiene lamisma posibilidad de aparecer que cualquier otro patron de m bits. Si m = 1la prueba serıa equivalente a la prueba de frecuencia monobit. Esta es unaprueba parametrizada y sus parametros son el tamano de los bloques m y lalongitud de la secuencia n, los cuales estan dados por la siguiente relacionm < [log2n] − 2.

3.2.13 Prueba de entropıa aproximada

Al igual que la prueba serial esta prueba checa la frecuencia de todos losposibles patrones traslapados de m bits dentro de la secuencia entera. Elproposito de esta prueba es comparar la frecuencia de los bloques traslapadosde dos longitudes de bloques traslapados de longitud m (consecutivos) ym + 1 (adyacentes) contra los resultados que se esperan de una secuenciaaleatoria. Esta es una prueba parametrizada, y los parametros requeridosson: el tamano de los bloques m y la longitud de la secuencia n, que estandados por la siguiente relacion por m < [log2n] − 2.

3.2.14 Prueba de sumas acumulativas

Esta prueba se concentra en la distancia maxima del cero de la caminataaleatoria definida por sumas acumulativas. En esta prueba nuevamente sesustituye cada 1 por +1 y cada 0 por -1 para convertir a la secuencia oparte de ella en una suma. El proposito de esta prueba es determinar silas sumas acumulativas de secciones de la secuencia son muy grandes o muy




pequenas comparadas con el comportamiento que se espera de una secuenciaaleatoria, de la cual se espera una suma cercana a cero, para algunos tiposde no aleatoriedad se espera que esta suma sea grande y por lo tanto alejadadel cero. A continuacion se muestra un ejemplo de esta prueba.

Se tiene la serie

= 1011010111

Se sustituye cambiando cada 1 por +1 y cada 0 por -1.X = 1, (−1), 1, 1, (−1), 1, (−1), 1, 1, 1

Se generan las sumas acumulativas, con el fin de detectar la m aximaexcursion del origen (cero),

S 1 = 1

S 2 = 1 + (−1) = 0

S 3 = 1 + (−1) + 1 = 1

S 4 = 1 + (−1) + 1 + 1 = 2

S 5 = 1 + (−1) + 1 + 1 + (−1) = 1

S 6 = 1 + (−1) + 1 + 1 + (−1) + 1 = 2

S 7 = 1 + (−1) + 1 + 1 + (−1) + 1 + (−1) = 1

S 8 = 1 + (−1) + 1 + 1 + (−1) + 1 + (−1) + 1 = 2

S 9 = 1 + (−1) + 1 + 1 + (−1) + 1 + (−1) + 1 + 1 = 3

S 10 = 1 + (−1) + 1 + 1 + (−1) + 1 + (−1) + 1 + 1 + 1 = 4

El programa analiza los resultados y en caso de que estos incluyan unnumero negativo cuyo valor absoluto sea muy grande, existirıa evidencia deque hay demasiados ceros en la secuencia, y si el resultado se trata de unnumero positivo muy grande existirıa evidencia de muchos unos en la secuen-






cia, en cambio resultados cercanos a cero en las subsecuencias indicarıan quelos unos y los ceros son proporcionales y que ademas estan mezclados correc-tamente dentro de la secuencia, la prueba es no parametrizada y recomiendaque la longitud de las secuencias n deben cumplir la siguiente condicionn ≥ 100.

3.2.15 Prueba de excursiones aleatorias

Esta prueba utiliza el mismo principio que la prueba de sumas acumulativasdetecta el numero de ciclos que tienen k visitas a una suma parcial, esta

suma parcial es conocida como estado. Un ciclo consiste en una secuenciade longitud unica, y el proposito de esta prueba es determinar si el numerode visitas a un estado en particular se desvıa de la cantidad esperada deuna secuencia aleatoria. Esta prueba consta de 8 subpruebas y es una porcada estado a probar −4, −3, −2, −1, 0 ,1 ,2 ,3 y 4. Esta prueba es noparametrizada y requiere secuencias de longitud n ≥ 106.

3.2.16 Prueba de excursiones aleatoria (Variante)

Es una variante de la prueba de excursiones aleatorias y de la misma manera

detecta el numero de ciclos que tienen k visitas a una suma parcial. La unicadiferencia es que esta prueba consta de 16 subpruebas que corresponden acada estado a probar desde −9 hasta 9. al igual que la prueba de excursionesaleatorias es no parametrizada y requiere que la longitud de las secuenciascumplan con n ≥ 106.

3.3 Criterios para las evaluacion

Para poder utilizar el programa de evaluacion de la NIST, se deben elegirciertos parametros y ciertos requisitos, tales como: la cantidad de secuen-

cias generadas, su longitud, la forma en que se generan, el formato con queseran guardadas dichas secuencias para su evaluacion, y los parametros delas pruebas parametrizadas.

Para cada prueba, existe la aleatoriedad estadıstica relevante llamada (α)y estadısticamente su intervalo valido es [0.001, 0.01] y sera utilizada paraaceptar o rechazar la hipotesis nula, en este caso para las 16 pruebas y susrespectivas subpruebas, el programa tiene predefinido el valor de (α = 0.01)



3.3 Criterios para las evaluacion 25

y no presenta ninguna opcion para redefinirla.El valor de α representa elmargen de error permitido por las pruebas por ejemplo:

Con α = 0.001 se espera que una secuencia de 1000 sea rechazada por laspruebas

Con α = 0.01 se espera que una secuencia de 100 sea rechazada por laspruebas.

Cada prueba y subprueba ejecutada nos dara como resultado un valornumerico por cada secuencia evaluada, llamado Valor P , este valor sera con-frontado contra α, y se obtendran tantos valores P como secuencias se hallanevaluado, el resultado de la evaluacion de cada secuencia se obtiene en basea la siguiente comparacion:

V alorP ≥ α (3.1)

Una secuencia sera considerada exitosa si cumple la condicion anteriory las secuencias cuyos valores P no la cumplan seran llamadas secuenciasfallidas, se espera que algunas secuencias fallen lo cual es normal y el intervaloaceptable de fallas esta en funcion de α.

Con α= 0.01 si un valor P ≥ α, la secuencia se considera aleatoria conuna certeza de 99%. Pero individualmente el resultado de cada secuencia noes capaz de brindarnos ningun resultado sobre la aleatoriedad del generador.Los dos parametros que son decisivos en cuanto a la aleatoriedad de todaslas secuencias son:

o La proporcion de secuencias exitosas

o La distribucion uniforme de valores P






Pero si tenemos tantos valores P como secuencias aun no podemos apre-ciar un resultado claro para la prueba completa, para esto es necesario sabersi la proporcion de las secuencias exitosas cae dentro del intervalo aceptablepara considerar la prueba como aprobada, dicho intervalo esta dado por:

R ± 3

R(R − 1)

m (3.2)

En donde

R = 1 − α

m = numero de secuencias

Para todas las pruebas, m es la cantidad de secuencias que se generaronpara evaluar, con excepcion de las pruebas y subpruebas de la excursionaleatoria y su variante, donde solo se toma una parte del total de secuenciasgeneradas y el intervalo para estas pruebas debe ser calculado con la m

correspondiente.Si al menos un valor correspondiente a la proporcion de secuencias exi-tosas cae fuera del intervalo en cualquier prueba o subprueba, la prueba seratomada como fallida y la hipotesis nula sera rechazada.

El otro parametro que determina la aceptacion o rechazo de la hipotesisnula, es la uniformidad de la distribucion de los valores P tambien conocidacomo el valor P de los valores P este valor es proporcionado por el programay debe cumplirse que el Valor P ≥ 0.0001, no debemos confundir este valorP con el valor P que corresponde a cada una de las secuencias evaluadas.

3.3.1 Eleccion de la longitud de las secuencias a evaluarEl numero de secuencias a generar esta en funcion de α, para poder ejecutarel programa de la NIST es necesario generar un archivo, en donde cada bitgenerado sea representado por un 0 o un 1 en formato ASCII; Se debengenerar al menos 1/α secuencias de datos con 1/α semillas diferentes, comoen cada prueba se requiere determinado numero de bits por secuencia, y parano tener que generar varias secuencias con diferentes longitudes, lo mejor es




encontrar una longitud de secuencia que se adapte a todas las pruebas o a lamayor cantidad posible.

Prueba Longitud de bits requerida

Frecuencia (monobit) n ≥ 100

Frecuencia (Bloque) n ≥ 100

Prueba de las corridas n ≥ 100

Corrida mas larga de unos en un bloque Tabla 3.2

Rango de la matriz binaria n ≥ 38, 912Transformada discreta de Fourier n ≥ 1000

Plantilla no traslapada n = 106

Plantilla traslapada n ≥ 106

Estadıstica universal de Maurer Tabla 3.3

compresion de Lempel-Ziv n ≥ 106

Complejidad lineal n ≥ 106

Prueba serial No especifica mınimo

Entropıa aproximada No especifica mınimo

Sumas acumulativas n ≥ 100

Excursion aleatoria n ≥ 106

Excursion aleatoria (Variante) n ≥ 106

Tabla 3.4: Longitud de bits requerida para cada prueba.

En la tabla 3.4 se muestran los requerimientos de la longitud de las se-cuencias para cada prueba y se puede observar que algunas pruebas requierencomo mınimo secuencias de 100 bits y no especifican maximo, la prueba dela plantilla no traslapada requiere exactamente 106 bits, algunas pruebas re-

quieren n ≥ 106, y otras que tienen intervalos de acuerdo a ciertos parametrosinternos de las mismas pruebas, la mayor limıtante es la prueba de la plan-tilla no traslapada que solo acepta 106 bits, fijando ese valor no existe ningunproblema con las demas ya que las que requieren 100 bits no fijan un limitemaximo y 106 bits es un valor compatible con todas las pruebas. De estamanera el tamano de las secuencias elegido es el de 106 bits, de esta formase genera un solo archivo de secuencias de 106 bits que es valido para todas






las pruebas.

3.3.2 Eleccion de los parametros de las Pruebas Parametrizadas

Como se menciono anteriormente las pruebas se dividen en pruebas parame-trizadas y no parametrizadas, las parametrizadas requieren ser alimentadascon ciertos valores para poder ejecutar dicha prueba y las pruebas no para-metrizadas no necesitan ningun dato extra.

A continuacion se definen los parametros de las pruebas parametrizadas.

1. Frecuencia dentro de un bloque

En esta prueba es necesario alimentar el tamano de los bloques M , elcual debe ser calculado en base las ecuaciones 3.3, 3.4, 3.5 y 3.6.

n ≥ MN (3.3)

M ≥ 20 (3.4)

M ≥ 0.01n (3.5)

N < 100 (3.6)

En donde

n =Bits por secuencia= 106

M = Bits por bloque

N = Numero total de bloques

Se tiene que calcular la longitud de los bloques, tomando en cuenta lasconsideraciones anteriores, se conoce n por lo tanto de la ecuacion 3.5podemos saber que M ≥ 10, 000 y esta ecuacion cumple lo establecidoen la ecuacion 3.4, debido a la ecuacion 3.6 el numero de bloques dentro

de la secuencia debe ser menor a 100, por lo tanto se eligira M =20, 000, que cumple con todas las ecuaciones proporcionadas para estaprueba.

2. Prueba de coincidencia de la plantilla no traslapada

En esta prueba el parametro a elegir tambien es el tamano de losbloques m, para lo cual el programa acepta diferentes longitudes de




M = 2, 3...10, pero recomienda utilizar M = 9 o M = 10, no propor-ciona ningun otro criterio para la eleccion de M , por lo tanto se eligioM = 9.

3. Prueba de coincidencia de la plantilla traslapada Se debe elegir eltamano de los bloques m, para lo cual el programa recomienda utilizarM = 9 o M = 10, no proporciona ningun otro criterio para la eleccionde M , por lo tanto se eligio M = 9.

4. Prueba estadıstica universal de Maurer

Esta prueba requiere de dos parametros como lo son la longitud de losbloques L, y el numero de bloques en la secuencia de iniciacion Q, paraesto de acuerdo a la longitud de las secuencias a evaluar n que en estecaso es n = 106 debemos elegir los valores correspondientes segun la3.3, que para este caso corresponden a L = 7 y Q = 1, 280.

5. Prueba de la complejidad lineal Para esta prueba es necesario

proporcionar el tamano de los bloques M que debe estar dentro delrango de 500 ≤ M ≤ 5000 y la cantidad de bloques N dentro de lasecuencia debe ser N ≥ 500. Para esta prueba se eligıo M = 500 quecumple todas las condiciones ya que n = 106 y por lo tanto N = 2000.

6. Prueba serial En esta prueba se elegio m = 10 el cual cumple larelacion m < [log2n] − 2 donde n = 106

7. Prueba de entropıa aproximada En esta prueba se eligio tambienm = 10 que al igual que en la prueba serial se debe cumplir la relaci onm < [log2n] − 2 y en la cual n = 106.

En la tabla 3.5 se muestran los parametros de las pruebas parametrizadas.los siguientes parametros:






Prueba ParametrosFrecuencia dentro de un bloque M=20000Prueba de coincidencia de la plantilla no traslapada M = 9Prueba de coincidencia de la plantilla traslapada M = 9Prueba estadıstica universal de Maurer L=7, Q=1280Prueba de la complejidad lineal m=500Prueba serial M=10Prueba de entropıa aproximada M=10

Tabla 3.5: Tabla de los parametros para las pruebas parametrizadas.



CAPITULO 4

Generador de llaves

Antes de poder implementar el sistema de encriptacion completo se debeprobar la aleatoriedad del generador de llaves, para eso se aplican las pruebasestadsticas de la NIST a las secuencias generadas por este. En este capitulose explica la estructura de este generador y los resultados de su evaluacion.

El fenomeno de sincronizacion en automatas celulares acoplados es usado

para construir dos familias de permutaciones de palabras binarias de longitudfinita N , donde N toma valores de 2k − 1, k > 0. Estas permutaciones sonusadas para encriptar y desencriptar un texto dividido en bloques de tamano2k − 1, k > 0. Para encriptar cada bloque se usa una llave diferente, lacual debe ser la misma para desencriptar el mismo bloque. El fenomeno desincronizacion tambien permitira construir una funcion, la cual es llamadafuncion RHO, que se utilizara en generadores de llaves. En la figura semuestran tres diferentes longitudes del generador de llaves.

El generador de llaves implementado en esta tesis genera llaves de 15 bits,la semilla inicial consta de 31 bits y esta dividida en dos partes llamadas

semilla baja de 15 bits (X1..X15) y semilla alta de 16 bits (Y1..Y16) en lafigura 4.2 se muestra la estructura del generador de 15 bits.

4.1 Funciones de un solo tiempo

Se hace uso de las versiones booleanas de un solo tiempo de las permutacionesy la funcion del generador implementadas en [1]. A Continuacion se muestran

31



32 Generador de llaves

Figura 4.1: a) Generador de 3 bits, b) Generador de 7 bits, c) Generador de15 bits

Figura 4.2: Estructura del generador de 15 bits

las ecuaciones booleanas de un solo tiempo que en conjunto conforman lafuncion RHO para 15 bits. Dicha funcion se muestra a continuacion.

t1 = x1 + y2

t2 = y1 + x2 + y3

t3 = x1 + x3 + y4

t4 = y1 + y3 + x4 + y5

t5 = x1 + y2 + x3 + x5 + y6



4.1 Funciones de un solo tiempo 33

t6 = y1 + x2 + y5 + x6 + y7

t7 = x1 + x5 + x7 + y8

t8 = y1 + y5 + y7 + x8 + y9

t9 = x1 + y2 + x5 + y6 + x7 + x9 + y10

t10 = y1 + x2 + y3 + y5 + x6 + y9 + x10 + y11

t11 = x1 + x3 + y4 + x5 + x9 + x11 + y12

t12 = y1 + y3 + x4 + y9 + y11 + x12 + y13

t13 = x1 + y2 + x3 + x9 + y10 + x11 + x13 + y14

t14 = y1 + x2 + y9 + x10 + y13 + x14 + y15

t15 = x1 + y16 + x9 + x13 + x15

La generacion de la primera llave es la mas simple, los bits de la semillabaja (X1..X15) y la semilla alta (Y1..Y16) ocupan sus respectivas posicionesen la funcion RHO para ası generar la primer llave(t1..t15), una vez generada

la primer llave el bit menos significativo de la semilla alta Y1 sustituir a albit mas significativo de la semilla alta Y16 y la semilla baja pasara a ocuparlos 15 bits restantes de la semilla alta (Y1..Y15), y la llave que fue generadasera la semilla baja, estos valores pasan por la funcion RHO para formar lasegunda llave, y todas las llaves subsecuentes se generan de la misma formaque la segunda llave. En el diagrama de flujo de la figura 4.3 se puede apreciarla forma en que se genera la primer llave y las llaves subsecuentes.






Figura 4.3: Diagrama de generacion de llaves

4.2 Requerimientos del la NIST para el generador dellaves de 15 bits.

En base al diagrama de la figura 4.3 se debe implementar un algoritmo que seacapaz de generar secuencias de llaves segun los requerimientos del programaestadıstico de la NIST, para este fin es necesario representar cada bit generadocon unos y ceros ASCII, es decir, el archivo sera un archivo de texto formadopor unos y ceros. Para un α = 0.01 se deben generar al menos 100 secuenciasde 1,000,000 de bits y cada secuencia debera ser generada apartir de diferentessemillas por lo tanto sera necesaria una semilla baja y alta por cada secuenciaque deba ser generada. La estructura de los datos debera ser la mostradaen la figura 4.4, en donde cada secuencia debera tener 1,000,000 de bits, y

el numero mınimo de secuencias a generar es 100 secuencias pero se puedengenerar mas si ası se desea y en el diagrama se representa con una n el numeroextra de secuencias que se generen.

El programa de evaluacion requiere 1,000,000 de bits, y debido a que nues-tro PRNG es capaz de proporcionar llaves de 15 bits, no existe un multiploentero de 15 que genere 1,000,000 de bits, con 66,667 llaves de 15 bits segenerarıan 1,000,005 bits. Para lograr el numero requerido por la NIST se



4.2 Requerimientos del la NIST para el generador de llaves de 15bits. 35

Figura 4.4: Estructura que debe tener el archivo con las secuencias que seranevaluadas

utilizaron unicamente los 10 bits menos significativos de la ultima llave paratener 1,000,000 de bits.

Se necesitan tantas semillas diferentes como secuencias, entonces si segeneraran 200 secuencias serıa impractico ingresar las 200 semillas requeri-das manualmente, una opcion es generarlas pseudo-aleatoriamente, ası cadasemilla se generara automaticamente, solo es necesario introducir una semillainicial para la funcion pseudoaleatoria que generara un numero pseudoaleato-rio por cada semilla necesaria para generar las secuencias.

En la figura 4.5 se aprecia el diagrama de flujo del algoritmo utilizado paragenerar y guardar las llaves en la forma que se requiere para ser evaluadas,se tienen dos contadores, uno de ellos llamado ”i” que lleva el control decuantas llaves han sido generadas; y el otro ”K” que lleva la cuenta de lassecuencias que han sido generadas, el primer dato que requiere el programaes la cantidad de secuencias a generar que se guarda en la variable ”N”, des-pues es necesario introducir una semilla ”S”, la cual no tiene nada que vercon el generador que estamos evaluando sino con otra funci on de generacionde numeros pseudoaleatorios, como generador de semillas pseudo-aleatorias,

para cada una de las secuencias del generador que se esta evaluando (casual-mente aquı vemos una aplicacion practica de un PRNG), una vez generadala primer semilla, Se genera la primer llave con la funcion RHO y esta seguarda en un archivo, ademas se preparan los datos que seran introduci-dos a la funcion RHO para la siguiente llave, se aumenta el contador ”i” enuna unidad, si ”i” no ha llegado a 66,666 (que es el numero de llaves quese tienen que generar para tener 999,990 bits) se repite el proceso desde la






Figura 4.5: Diagrama de flujo del algoritmo generador de llaves

funcion RHO; y en caso de que el contador ”i” ya hubiera llegado a 66,666,se genera una llave de solo 10 bits para la cual se toman las diez ecuacionesmenos significativas de la funcion RHO, y esta llave de 10 bits se anexa alarchivo de llaves para ası completar una secuencia de 1,000,000 de bits, elproceso continua reiniciando ”i” a cero y sumando uno al contador ”K” paraası compararlo con ”N” (numero de llaves deseadas), en caso que se hubierallegado a la meta el programa termina, pero si no, se genera otra semilla deforma pseudo-aleatoria para iniciar la siguiente secuencia y ası sucesivamente

hasta lograr el numero de secuencias requeridas. De esta manera trabaja elprograma que genera el archivo de secuencia que alimenta las pruebas es-tadısticas de la NIST, este programa fue implementado en lenguaje C y seanexa el en APENDICEXXXXX.



CAPITULO 5

Resultados de las pruebas estadısticas de las

NIST

Se decidio aplicar el conjunto de pruebas de la NIST al generador de llavespara evaluar su aleatoriedad, dicha decision fue tomada en base al respaldoque le da al conjunto de pruebas haber sido desarrollado por expertos en lamateria, ademas de que varias pruebas que se encuentran en este conjuntose encuentran en otros conjuntos de pruebas que son tambien de renombre[19], [18], aunado a esto el programa es de distribucion gratuita, y existenvarias publicaciones con informacion referente a este [3], [4].

Para fines de esta investigacion inicialmente se opto por utilizar el genera-dor de llaves de 7 bits, pero al momento de analizar las secuencias que fuerongeneradas con este, fue incluso innecesario aplicar las pruebas estadısticas de

la NIST ya que el ciclo del generador es de aproximadamente 85,000 bits, esdecir los datos generados con una misma semilla se repiten cada 85,000 bits, yel programa de evaluacion requiere secuencias de al menos 1,000,000 de bits,el programa de evaluacion encontrarıa patrones de no aleatoriedad debido aque esos 85,000 bits estarıan repitiendose en cada secuencia hasta completar1,000,000 de bits, entonces la mejor opcion para analizar es el generador de15 bits.

37



38 Resultados de las pruebas estadısticas de las NIST

5.1 Criterios para la evaluacion

Debemos recordar que son dos parametros los que nos daran evidencia paratomar una determinacion en cuanto a la supuesta aleatoriedad de las se-cuencias que se evaluan, estos son la proporcion de secuencias exitosas y ladistribucion uniforme de valores P , dichos datos son extraıdos del archivode reporte que arroja el programa estadıstico de la NIST, como en este casose evaluaron 10 archivos de secuencias, se tienen 10 archivos de reporte yde cada uno de ellos es necesario analizar los resultados, para evaluar losresultados de la proporcion de secuencias exitosas, es necesario construir una

grafica en la cual se muestren los valores obtenidos por cada prueba y sub-prueba ademas dicha grafica debe mostrar el valor mınimo permitido paracada prueba; para analizar los resultados de la distribucion uniforme de losvalores P , es necesario construir un histograma en cual cual se representandiez intervalos diferentes y en cada uno de ellos la frecuencia con que ocur-ren los valores P dentro de cada uno de los intervalos, se espera que en elhistograma esos diez intervalos tengan una frecuencia muy parecida, de locontrario habra evidencia de no aleatoriedad.

Como anteriormente se menciono, es practicamente imposible construirun generador de numeros pseudo-aleatorios que sea capaz de pasar siempretodas las pruebas, los criterios y parametros para la evaluacion de las secuen-cias ya fueron planteadas anteriormente en este documento, en este capitulose plantean los criterios para la interpretacion de los resultados de las pruebasaplicadas, el programa estadıstico da pie a tomar varias decisiones en base anuestro criterio. Al ejecutar las pruebas estadısticas, se esperan ciertas fallasen algunas secuencias y por lo tanto pueden fallar algunas pruebas, pero parapoder distinguir cuando se trata de vulnerabilidad en el generador o erroresnormales debidos a la probabilidad, se deben realizar varias veces las prue-bas con diferentes semillas, y observar en donde ocurren las fallas, si estasaparentan no tener ningun patron y si los valores que fallaron, lo hicieron pordiferencias muy pequenas con respecto al valor mınimo esperado, podremos

decir que son errores aleatorios debidos a la probabilidad; pero si se observaun patron en los errores o bien; alguna prueba fallo por una diferencia muygrande, podemos decir que el generador es vulnerable y no es apto para suuso en criptografıa. Para fines practicos los nombres de las pruebas seranrepresentados por medio de numeros. En la tabla 5.1 se muestran las corres-pondencias entre los nombres de las pruebas y los numeros con que seranidentificadas.



5.1 Criterios para la evaluacion 39

Prueba numeroPrueba de frecuencia (monobit) 1Prueba de frecuencia dentro de un bloque 2Prueba de sumas acumulativas 3Prueba de las corridas 4Pruebas de la corrida mas larga de unos en un bloque 5Prueba del rango de la matriz binaria 6Prueba de la transformada discreta de Fourier (espectral) 7Prueba de coincidencia de la plantilla no traslapada 8Prueba de coincidencia de la plantilla traslapada 9

Prueba estadıstica universal de Maurer 10Prueba de entropıa aproximada 11Prueba de excursion aleatoria 12Prueba de excursion aleatoria (Variante) 13Prueba serial 14Prueba de compresion de Lempel-Ziv 15Prueba de la complejidad lineal 16

Tabla 5.1: Tabla de asignacion de numeros a cada prueba

Para la evaluacion confiable de un generador son necesarios suficientesarchivos de secuencias, ya que se deben ejecutar varias pruebas, observarlos resultados que se desprendan de estas y detectar si los errores reflejanvulnerabilidad en el sistema o si solo son errores debido a la probabilidad.En este caso se generan y evaluan diez archivos que constan de 300 secuenciasde 1,000,000 de bits cada una, se estaran evaluando 3,000,000,000 de bits,cantidad suficientemente grande para poder tomar una determinacion certerasobre la aleatoriedad del generador.

En caso de que algun generador sea encontrado no apto para su apli-

cacion en criptografıa, en algunos casos es posible corregir las debilidadesencontradas en este, haciendo ajustes al algoritmo que utiliza para la gene-racion de datos, pero de hacerlo ası, serıa necesario volver a generar datospara aplicarles las pruebas estadısticas.

Algunas pruebas tienen subpruebas, la prueba que cuente con mas sub-purebas es la que mas probabilidad tiene de fallar, y recordemos que si almenos una subprueba falla se considera como fallida a la prueba entera. En






en la tabla 5.2 se muestra el numero de subpruebas con que cuenta cadaprueba, y en ella se puede observar que la prueba con m as subpruebas esla de la coincidencia de la plantilla no traslapada, debido a que la cantidadde subpruebas de esta prueba es muy superior a las demas se espera que sepresenten errores debido a la probabilidad en esta prueba, para diferenciar sise trata de un error debido unicamente a la probabilidad o uno que ponga enevidencia la vulnerabilidad del sistema, basta con analizar que tan inferiores el valor que fallo con respecto del valor mınimo permitido, si se trata deuna diferencia insignificante se puede decir que el error es solo debido a laprobabilidad pero si se trata de una diferencia muy grande se puede hablar

de un error que afecta la supuesta aleatoriedad del generador.

Prueba Total de Pruebas/Subpruebas

Frecuencia (monobit) 1Frecuencia dentro de un bloque 1Sumas acumulativas 2Corridas 1Corrida mas larga de unos en un bloque 1Rango de la matriz binaria 1

Transformada discreta de Fourier (espectral) 1Coincidencia de la plantilla no traslapada 148Coincidencia de la plantilla traslapada 1Estadıstica universal de Maurer 1Entropıa aproximada 1Excursion aleatoria 8Excursion aleatoria (Variante) 19Serial 2Compresion de Lempel-Ziv 1Complejidad lineal 1

Tabla 5.2: En la tabla se muestra la cantidad de subpruebas con que cuentacada prueba para la evaluacion de 300 secuencias.

Se generaron y evaluaron diez diferentes archivos, cada uno de ellos constade 300 secuencias diferentes de 1,000,000 de bits cada una. Los archivos delreporte final son muy largos para mostrarse en este documento ası que solo




se muestran las graficas correspondientes a cada archivo.Para 300 secuencias de 1,000,000 de bits el valor mınimo para aprobar

la proporcion de secuencias exitosas en todas las pruebas a excepci on delas pruebas de excursion aleatoria y su variante es de 0.9727. Y el valormınimo para las pruebas de la excursion aleatoria y su variante es de 0.9677.En las graficas de la proporcion de secuencias exitosas se observa una partesombreada, la cual representa el rango valido, y cada numero en el eje hor-izontal representa una prueba de acuerdo a la tabla 5.1 cada valor obtenidopor cada prueba o subprueba es representado por un punto, y en algunoscasos varias subpruebas de una misma prueba obtienen el mismo valor y por

eso en algunos casos parecera haber menos puntos de los que deberıa. Lasgraficas correspondientes a la distribucion uniforme de los valores P dividenlos valores P resultantes de cada prueba y subprueba en diez intervalos yen estos intervalos se muestra la frecuencia de los valores P dentro de di-chos intervalos, la cual debe estar uniformemente distribuida entre los diezintervalos.

1. Primer archivo evaluado

En la grafica 5.1 se muestran los resultados correspondientes a la pro-porcion de secuencias exitosas para el primer archivo evaluado, en dichagrafica se puede observar que todas las pruebas y subpruebas pasaron

sin ningun problema.

Figura 5.1: Grafica de los valores correspondientes a la proporcion de secuen-cias exitosas para el primer archivo evaluado, en la grafica se observa quetodas las pruebas y subpruebas pasaron sin problema.






En la grfica 5.2 se muestra el histograma resultante de los datos cor-respondientes a la distribucion uniforme de los valores P del primerarchivo evaluado, en dicho histograma se observa la uniformidad de losdiez intervalos, por lo tanto el primer archivo evaluado aprobo todas laspruebas y se considera exitoso, ya que los resultados de la proporci onde secuencias exitosa y la distribucion uniforme de los valores P fueronsatisfactorios.

Figura 5.2: Histograma correspondiente a la distribucion uniforme de losvalores P para el primer archivo evaluado.

2. Segundo archivo evaluado

En la grfica 5.3 se muestran los resultados del segundo archivo evaluadopara la proporcion de secuencias exitosas, en dicha grfica se puedeobservar que existe un valor que se encuentra por debajo del limite enla prueba que tiene asignado el numero 8, la cual de acuerdo a la tabla5.1, corresponde a la prueba de la plantilla no traslapada, que comoanteriormente se menciono es la prueba que cuenta con mayor numero

de subpruebas y por lo tanto es la prueba que mayor probabilidadtiene de fallar, el valor mınimo aceptable para esta prueba es de 0.9727y el valor obtenido para una de las subpruebas fue de 0.9700, dicha fallapuede ser considerada como ”normal” y debida a la probabilidad ya queel valor que fallo esta apenas por debajo del valor mınimo esperado, ypara poder saber con certeza si dicha falla fue debida a la probabilidado realmente indica vulnerabilidad se debe observar el comportamiento




de la prueba de la plantilla no traslapada en los siguientes archivosevaluados.

Figura 5.3: Grafica de los valores correspondientes a la proporcion de secuen-cias exitosas para el segundo archivo evaluado, en la grafica se aprecia queun valor de la prueba 8 se encuentra por debajo del limite.

En la grafica 5.4 se muestra el histograma de la distribucion uniformede los valores P en el cual se observa que no existe ninguna anomalıa.

Figura 5.4: Histograma correspondiente a la distribucion uniforme de losvalores P para el segundo archivo evaluado.






3. Tercer archivo evaluadoEn la grafica 5.5 se muestran los resultados para la proporcion de se-cuencias exitosas del tercer archivo evaluado, de la misma manera enel histograma de la figura 5.8 se muestran los resultados de la distribucion uniforme de los valores P .

Figura 5.5: Grafica de los valores correspondientes a la proporcion de secuen-cias exitosas para el tercer archivo evaluado, en la grafica se observa que

todas las pruebas y subpruebas aprovaron sin problema.

Figura 5.6: Histograma correspondiente a la distribucion uniforme de losvalores P para el tercer archivo evaluado.




4. Cuarto archivo evaluadoEn la grafica 5.7 se muestran los resultados para la proporcion de se-cuencias exitosas del tercer archivo evaluado, de la misma manera en elhistograma de la figura 5.8 se muestran los resultados de la distribucionuniforme de los valores P .

Figura 5.7: Grafica de los valores correspondientes a la proporcion de secuen-cias exitosas para el cuarto archivo evaluado, en la grafica se observa que

todas las pruebas y subpruebas pasaron sin problema.

Figura 5.8: Histograma correspondiente a la distribucion uniforme de losvalores P para el cuarto archivo evaluado.






5. Quinto archivo evaluadoEn la grafica 5.9 se muestran los resultados para la proporcion de se-cuencias exitosas del tercer archivo evaluado, de la misma manera enel histograma de la figura 5.10 se muestran los resultados de la dis-tribucion uniforme de los valores P .

Figura 5.9: Grafica de los valores correspondientes a la proporcion de secuen-cias exitosas para el quinto archivo evaluado, en la grafica se observa que


Figura 5.10: Histograma correspondiente a la distribucion uniforme de losvalores P para el quinto archivo evaluado.




6. Sexto archivo evaluadoEn la grafica 5.11 se muestran los resultados para la proporci on desecuencias exitosas del tercer archivo evaluado, de la misma maneraen el histograma de la figura 5.12 se muestran los resultados de ladistribucion uniforme de los valores P .

Figura 5.11: Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el sexto archivo evaluado, en la grafica se observa que


Figura 5.12: Histograma correspondiente a la distribucion uniforme de losvalores P para el sexto archivo evaluado.






7. Septimo archivo evaluadoEn la grafica 5.13 se muestran los resultados para la proporci on desecuencias exitosas del tercer archivo evaluado, de la misma maneraen el histograma de la figura 5.14 se muestran los resultados de ladistribucion uniforme de los valores P .

Figura 5.13: Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el septimo archivo evaluado, en la grafica se observa

que todas las pruebas y subpruebas pasaron sin problema.

Figura 5.14: Histograma correspondiente a la distribucion uniforme de losvalores P para el septimo archivo evaluado.




8. Octavo archivo evaluadoEn la grafica 5.15 se muestran los resultados para la proporci on desecuencias exitosas del tercer archivo evaluado, de la misma maneraen el histograma de la figura 5.16 se muestran los resultados de ladistribucion uniforme de los valores P .

Figura 5.15: Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el octavo archivo evaluado, en la grafica se observa


Figura 5.16: Histograma correspondiente a la distribucion uniforme de losvalores P para el octsvo archivo evaluado.






9. Noveno archivo evaluadoEn la grafica 5.17 se muestran los resultados para la proporci on desecuencias exitosas del tercer archivo evaluado, de la misma maneraen el histograma de la figura 5.18 se muestran los resultados de ladistribucion uniforme de los valores P .

Figura 5.17: Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el noveno archivo evaluado, en la grafica se observa


Figura 5.18: Histograma correspondiente a la distribucion uniforme de losvalores P para el noveno archivo evaluado.




10. Decimo archivo evaluadoEn la grafica 5.19 se muestran los resultados para la proporci on desecuencias exitosas del tercer archivo evaluado, de la misma maneraen el histograma de la figura 5.20 se muestran los resultados de ladistribucion uniforme de los valores P .

Figura 5.19: Grafica de los valores correspondientes a la proporcion de se-cuencias exitosas para el decimo archivo evaluado, en la grafica se observa


Figura 5.20: Histograma correspondiente a la distribucion uniforme de losvalores P para el decimo archivo evaluado.






En las graficas anteriores se mostraron los resultados de las pruebas apli-cadas a las secuencias evaluadas, dichos resultados se concentran en la tabla5.3, en la cual se puede observar que en el segundo archivo evaluado se pre-sentan un valor por debajo del mınimo establecido 9700 para la proporcionde secuencias exitosas.

Archivo Proporcion Uniformidad1 Aprobado Aprobado2 8 Aprobado3 Aprobado Aprobado

4 Aprobado Aprobado5 Aprobado Aprobado6 Aprobado Aprobado7 Aprobado Aprobado8 Aprobado Aprobado9 Aprobado Aprobado

10 Aprobado Aprobado

Tabla 5.3: En esta tabla se concentran los resultados obtenidos por los diezarchivos de secuencias que fueron evaluados utilizando el programa estadstico

de la NIST.

En el analisis de los resultados se observa que predomina el exito en lapruebas, sin embargo se presentan una falla en la prueba correspondientea la plantilla no traslapada en el segundo archivo evaluado, pero lo valoreque fallo en dicha prueba se encuentra apenas por debajo del limite mınimoestablecido por el programa estadıstico, lo cual nos permite concluir queeste error no afecta la seguridad del sistema, y por lo tanto el generadorse considera apto para su uso en criptografıa. De esta manera es posiblecontinuar con el desarrollo del sistema de encriptacion digital, basado en el

generador que fue evaluado y aprobado para su uso en criptografıa.



CAPITULO 6

Sistema de encriptacion

Una vez comprobada la aleatoriedad estadıstica del generador de llaves, estepuede ser utilizado en un sistema de encriptacion que pueda ofrecer seguridaden su funcionamiento, pero hasta el momento en este documento solo seha abordado el funcionamiento y evalucion del generador de llaves, pero el

sistema de encriptacion completo comprende ademas de este, la forma enque seran acomodados los datos a encriptar o desencriptar para despues serprocesados junto con los numeros que se obtuvieron del generador de llaves.

6.1 Ecuaciones de encriptacion y desencriptacion

Las ecuaciones que hemos visto hasta el momento solo comprenden la funcionRHO, la cual es responsable de la generacion de numeros pseudo-aleatorios,

pero para poder encriptar un dato es necesario, primero generar un numeropseudo-aleatorio, y despues extraer una cadena de bits de longitud N delarchivo de texto plano, que sera procesada por alguna ecuacion junto con elnumero pseudo-aleatorio generado, de esta manera el dato quedara encrip-tado, y solo con otra ecuacion que revierta la encriptacion y con el mismonumero pseudo-aleatorio con que fue encriptado el dato, podremos regresarloa su estado original.

53



54 Sistema de encriptacion

Las ecuaciones para encriptacion de 15 bits deben ser alimentadas por unnumero pseudo-aleatorio de 15 bits representado como x[1..15], el cual seraproveıdo por la funcion RHO, recordemos que la funcion RHO arroja comoresultado 15 bits t[1..15], ademas las ecuaciones de encriptacion requierenser alimentadas con 15 bits de texto plano que deben ser separados del restode los bits del texto plano por medio de un algoritmo que divida todo elarchivo de texto plano en paquetes de 15 bits, los cuales son representadospor c[1..15]. De esta manera las ecuaciones procesan los valores que les soningresados y dan como resultado 15 bits de texto cifrado m[1..15]. En eldiagrama de la figura 6.1 se puede apreciar el proceso de encriptacion. En

seguida se muestran las ecuaciones de encriptacion :

m1 = x15 + x13 + x9 + x1 + c1

m2 = x14 + x10 + x2 + c2

m3 = x13 + x11 + x9 + x3 + x1 + c1 + c3

m4 = x12 + x4 + c4

m5 = x11 + x9 + x5 + x3 + x1 + c1 + c3 + c5

m6 = x10 + x6 + x2 + c2 + c6

m7 = x9 + x7 + x5 + x1 + c1 + c5 + c7

m8 = x8 + c8

m9 = x7 + x5 + x1 + c1 + c5 + c7 + c9

m10 = x6 + x2 + c2 + c6 + c10

m11 = x5 + x3 + x1 + c1 + c3 + c5 + c9 + c11

m12 = x4 + c4 + c12

m13 = x3 + x1 + c1 + c3 + c9 + c11 + c13

m14 = x2 + c2 + c10 + c14

m15 = x1 + c1 + c9 + c13 + c15



6.1 Ecuaciones de encriptacion y desencriptacion 55

Por otra parte las ecuaciones de desencriptacion tambien requieren seralimentadas con un numero pseudo-aleatorio de 15 bits x[1..15] y con 15 bitsde datos del texto cifrado m[1..15], que seran procesados y entregaran comoresultado 15 bits que formaran parte del texto plano c[1..15] tal como se mues-tra en la figura 6.2. En seguida se muestran las ecuaciones de encriptacion:

c1 = x1 + x9 + x13 + x15 + m1

c2 = x2 + x10 + x14 + m2

c3 = x3 + x11 + x15 + m1 + m3

c4 = x4 + x12 + m4

c5 = x5 + x13 + m3 + m5

c6 = x6 + x14 + m2 + m6

c7 = x7 + x15 + m1 + m3 + m5 + m7

c8 = x8 + m8

c9 = x9 + m7 + m9

c10 = x10 + m6 + m10

c11 = x11 + m5 + m7 + m9 + m11

c12 = x12 + m4 + m12

c13 = x13 + m3 + m5 + m11 + m13

c14 = x14 + m2 + m6 + m10 + m14

c15 = x15 + m1 + m3 + m5 + m7 + m9 + m11 + m13 + c15

Los numeros pseudo-aleatorios requeridos para las ecuaciones de encripta-cion y desencriptacion seran obtenidos del PRNG; los 15 bits de texto planoy texto cifrado, no son extraıdos del texto plano o cifrado de 15 bits en 15bits, sino de 16 bits en 16 bits, para este proposito se desarrollo un algoritmoque se encarga de generar los paquetes de 16 bits, de los cuales solo seran






proporcionados 15 bits a las ecuaciones de encriptacion o desencriptacionsegun corresponda el caso, lo cual le agrega aun mas seguridad al sistema.

Figura 6.1: Ecuaciones para encriptacion y sus fuentes.

Figura 6.2: Ecuaciones para desencriptacion y sus fuentes.

6.2 Unidad procesadora del texto plano o cifrado.

Para que las ecuaciones puedan procesar la informacion que sera encriptadao desencriptada, es necesario acomodar los datos del texto plano en paque-tes que puedan ser manipulados por estas junto con los numeros pseudo-aleatorios.

La forma en que se generan dichos paquetes de datos consta en partir elarchivo de texto plano en paquetes de 2 bytes (16 bits), para ser procesados



6.2 Unidad procesadora del texto plano o cifrado. 57

por las ecuaciones de encriptacion, para cada paquete de datos debera sergenerado un numero pseudo-aleatorio de 15 bits, el cual sera introducido a lafuncion de encriptacion junto con los 15 bits mas significativos del paquete dedatos, y el bit menos significativo sera dejado intacto, debido a que es el bitmenos ponderando no representa peligro alguno al ser dejado sin procesar,ademas, a la salida del dato encriptado de 15 bits, este bit ser a reincorporadopero no en la posicion menos significativa de la que fue tomado, sino en laposicion mas significativa, agregando ası aun mayor seguridad al sistema, yaque un bit que no tiene gran importancia esta siendo agregado en la posici onmas significativa de los datos, de esta manera el dato resultante tambien sera

de 16 bits (2 bytes), de los cuales 15 bits fueron procesados por el sistemade encriptacion y uno, solo fue cambiado de posicion tal como se muestra enla figura 6.3.

Figura 6.3: Estructura de datos para encriptacion

Para el proceso de desencriptacion, debemos generar los numeros pseudo-aleatorios con la misma llave con que fueron generados los numeros que seutilizaron para encriptar los datos, en este proceso tenemos el texto cifrado,con la estructura anteriormente mencionada, en paquetes de 16 bits, de los

cuales el bit mas significativo del texto cifrado es el bit menos significativodel texto plano, de esta manera solo hay que cambiar la poscion de este bit,y procesar con la funcion de desencriptacion los 15 bits menos significativos junto con cada numero pseudo-aleatorio generado. Este proceso se muestraen la figura 6.4

En el diagrama de la figura 6.5 se muestran las partes que conformanel sistema completo de encriptacion / desencriptacion, se alcanza a apreciar






Figura 6.4: Estructura de datos para desencriptacion

que la preparacion de los paquetes de datos y la generaci on de los numerospseudo-aleatorios son procesos separados, el proceso de preparaci on de losdatos comienza con seleccionar entre encriptar o desencriptar datos, estodebido a que dependiendo de cada operaci on cambia la estructura de losdatos, una vez generado el paquete de datos se genera el numero pseudoaleatorio que sera introducido junto con el paquete que se genero para obtenerel texto plano o texto cifrado segun corresponda.

Figura 6.5: Diagrama de operacion del sistema

Notese que ”texto plano” es solo la forma de llamar al archivo originalantes de ser encriptado y no quiere decir que podamos encriptar solo archivosde texto, es posible encriptar cualquier tipo de archivo. De esta manera elproceso para poder encriptar o desencriptar un archivo completo, consiste



6.2 Unidad procesadora del texto plano o cifrado. 59

primero en contar el numero total de bits del archivo y divirlo entre 16 encaso de obtener cifras decimales el resultado se redondeara al entero inme-diato superior, este numero indicara cuantos paquetes de datos de 16 bitsseran generados, y por consiguiente tambien sera la cantidad de numerospseudo-aleatorios de 15 bits que seran requeridos para la operacion, el si-guiente paso es indicar que tipo de operacion que se realizara encriptaciono desencriptacion ya que dependiendo de esto se eligir a la forma en quelos bits de los paquetes de datos sean acomodados, al generar el primerpaquete de datos se generara el primer numero pseudo-aleatorio y ambosseran procesados por las funciones de encriptacion o desencriptacion segun

corresponda el caso, y el resultado de 16 bits sera guardado en un archivo, esteproceso se repetira tantas veces como paquetes de datos se hayan generado ycada resultado se ira agregando a los anteriores en el archivo que se genere,despues de procesar todos los paquetes de datos, el archivo resultante estaracompleto y sera el texto plano o bien el texto cifrado.





CAPITULO 7

Sistema de encriptacion en unmicrocontrolador.

El sistema de encriptacion / desencriptacion consta de tres entidades dife-rentes: la unidad de generacion de numeros pseudo-aleatorios, que requierecomo entrada la semilla alta y baja, 31 bits en total; y a la salida entregaen cada ciclo un numero pseudo-aleatorio de 15 bits; la unidad encargada deacomodar los datos del texto plano o texto cifrado para que sean procesadospor las ecuaciones de encriptacion o desencriptacion segun corresponda elcaso, cuya entrada de datos esta definida por el tamano del archivo que seraprocesado y a la salida entrega paquetes de este archivo con una longitud de16 bits, por ultimo se tiene la entidad de encriptacion/desencriptacion que esla encargada de procesar los datos entregados por las otras dos entidades; elsiguiente paso es acoplar las tres entidades para que estas funcionen en per-fecta sincronıa y ademas sean capaces en conjunto de encriptar o desencriptararchivos completos segun sea el caso.

El sistema completo podrıa ser implementado unicamente en software,

pero de ser ası el programa podrıa ser copiado e implementado en otra com-putadora sin ningun problema, es por eso que por razones de seguridad esindispensable que el algoritmo sea ejecutado desde un medio fısico, debidoa que este agrega mayor seguridad, en hardware existen dispositivos pro-gramables que pueden ser protegidos contra copiado, entonces quien quieraencriptar o desencriptar un archivo con este sistema debera tener el hard-ware dedicado a este fin conectado a su PC, o de lo contrario sera imposible

60



7.1 Implementacion en Hardware del PRGN 61

cualquiera de estas operaciones.

7.1 Implementacion en Hardware del PRGN

Para la implementacion en hardware primero es necesario definir que proce-sos se ejecutaran desde la pc y cuales desde el dispositivo programable quese utilize para el sistema desarrollado en hardware. Las ecuaciones de en-criptacion y desencriptacion deberan ser ejecutadas desde el dispositivo pro-gramable, ya que son una parte critica en cuanto a la seguridad del sistema,si se almacenan en un dispositivo programable protegido contra copiado ser a

imposible su reproduccion e incluso visualizacion, la entidad correspondientea la generacion de numeros pseudo-aleatorios tambien debera ser ejecutadadesde el dispositivo programable para proteger el sistema de la visualizaci ono copiado del algoritmo de generacion de las llaves con que son encriptadoso desencriptados los datos, solamente la semilla sera proporcionada desde laPC; la parte de la generacion de los paquetes de datos a procesar puede serejecutada desde la PC, ya que no representa gran peligro que se conozca laestructura que toman los datos antes de ser procesados. Ademas se debegenerar un programa de control en la PC para que todas las entidades fun-cionen correctamente. En la figura 7.1 se muestra como esta distribuida la

ejecucion de los procesos entre la PC y el dispositivo programable.

Figura 7.1: Distribucion de los procesos entre la PC y el dispositivo progra-mable.

La eleccion del dispositivo programable para implementar el sistema ini-cialmente fue un PLD (Programmable Logic Device) EPM7128[10], el cualse programa en lenguaje VHDL, este dispositivo cuenta con multiples pines





62 Sistema de encriptacion en un microcontrolador.

de entrada/salida y debido a que su funcionamiento se basa en compuertaslogicas ofrece un buen desempeno, para la interfaz de prueba entre este dis-positivo y la PC se eligio una tarjeta de adquisicion de datos de NationalInstruments (DIO-32 HS), la cual cuenta con 4 puertos programables de en-trada/salida, ademas de 16 lıneas de handshaking, las cuales tambien puedenser utilizadas como lıneas de datos, esta tarjeta se conecta a la PC via busPCI, y al otro extremo de este se conecta el banco de conexiones SCB-68,tambien fabricado por National Instruments, el programa de control del sis-tema fue desarrollado en LabView debido a su versatilidad, ya que la tarjetade adquisicion de datos ofrece total compatibilidad con este. En la figura 7.2

se muestra la interfaz entre la PC y el PLD.

Figura 7.2: Conexiones del sistema

La primera etapa de desarrollo consta en programar en el PLD el PRNGy generar numeros pseudo-aleatorios, controlando dicho proceso desde la PC,para probar su buen funcionamiento se debe generar una secuencia de bitsdesde el programa desarrollado en software, y con la misma semilla generarexactamente la misma secuencia desde el PLD, tal como se muestra en lafigura 7.3, para ası comparar que no exista ninguna diferencia entre la secuen-cia generada por software y la generada por hardware. Para este proposito se

desarrollo un programa en el PLD con el PRNG cuyo funcionamiento se con-trola desde la PC mediante un programa desarrollado en Labview que ademasde llevar el control de generacion de llaves graba todos los numeros generadosen un archivo; para despues con la misma semilla, generar la misma secuen-cia por medio de el programa desarrollado en lenguaje C. Pero aun despuesde desarrollar varios prototipos diferentes basados en el PLD, las secuenciasnunca coincidıan; tienen errores recurrentes en las secuencias generadas por



7.1 Implementacion en Hardware del PRGN 63

hardware; despues de investigar las causas se llego a la conclusion de que estafalla fue causada debido a que las celdas logicas del PLD no eran suficientespara implementar el programa, y cuando esto sucede, el PLD efectua unasıntesis logica, cuya funcion es tratar de sintetizar las ecuaciones resultantesdel programa en VHDL, lo cual puede llegar a afectar significativamente losresultados que se esperen de este. Entonces la opcion para corregir dicho er-ror era cambiar a un PLD de mayor capacidad, o bien cambiar de dispositivoprogramable; en este caso se opto por cambiar el PLD por un microcontro-lador PIC16F877A, debido a su flexibilidad y escalabilidad ya que se cuentacon multiples pines de entrada y salida ademas de que cuenta con puerto

paralelo, puerto RS-232 y tiene la posibilidad de manejar USB. El 16F877Asoporta una velocidad de reloj de hasta 20 mhz, cuenta con un completoset de instrucciones, 14.3 kbytes de espacio disponible para el programa, 368bytes de RAM y 256 bytes de EEPROM, de esta manera el dispositivo estasobrado en recursos para la aplicacion.

Figura 7.3: Al introducir la misma semilla en el sistema desarrollado en soft-ware y en el sistema desarrollado en hardware se debe generar la mismasecuencia de bits.

De esta manera se implemento el PRNG en el microcontrolador, uti-

lizando la misma interfaz, obteniendo los resultados deseados en la confrontade los datos generados por el sistema desde el microcontrolador y por el pro-grama implementado en software. El programa de control tambien se hizo enLabview. La implementacion del generador de paquetes de datos se realizoen Labview, la funcion de esta entidad es preparar los paquetes de bits paraencriptarlos o desencriptarlos segun sea el caso, una vez que cada paquetesea procesado, esta entidad es la encargada de acomodar los paquetes de bits






que formaran el archivo final de texto plano o texto cifrado dependiendo dela operacion que se halla realizado

7.2 Procesamiento de paquetes para encriptacion.

La preparacion de los paquetes de datos del texto plano para su encriptacion,se lleva a cabo por medio de un programa que lee el archivo de texto plano,ylo parte en paquetes de 16 bits a cada paquete de 16 bits le sera tomadoel bit menos significativo para formar otro arreglos con este; y los 15 bitsrestantes formaran otro arreglo que sera el que alimentara en cada ciclo junto

un un numero pseudo-aleatorio de 15 bits, a las ecuaciones de encriptacionlas cuales a su vez entregaran 15 bits en cada ciclo, los cuales alimentaranun arreglo con los datos ya procesados, al que se le agregara el arreglo de 1bit, en la posicion del bit mas significativo (bit 16) para ası obtener comoresultado un arreglo de paquetes de 16 bits los cuales seran reagrupados enun archivo, este archivo sera el correspondiente al texto cifrado. En la figura7.4 se muestra el diagrama del proceso de generacion de los paquetes de datospara su encriptacion

Figura 7.4: Diagrama de operacion del sistema de generacion de paquetes de

datos para su encriptacion

7.3 Procesamiento de paquetes para desencriptacion.

Para el procesamiento de los paquetes para la desencriptaci on es necesarioleer el archivo de texto cifrado y descomponerlo en un arreglo de paquetes de



7.3 Procesamiento de paquetes para desencriptacion. 65

16 bits; a cada uno de estos paquetes le sera tomado el bit mas significativopara formar un nuevo arreglo y los 15 bits formaran otro arreglo que serael que junto con un numero pseudo-aleatorio de 15 bits, alimentaran lasecuaciones de desencriptacion; las cuales a su vez entregaran paquetes 15bits, con los cuales se formara un arreglo con los datos ya procesados, al cualse le agregara, el arreglo de un bit anteriormente mencionado, en la posicionmenos significativa, para lo cual es necesario realizar un corrimiento a los 15bits que se tienen; y de esta manera formar un arreglo con paquetes de 16 bits,los cuales seran guardados en un archivo, este archivo debera corresponderal archivo que originalmente se encripto (archivo de texto plano), siempre y

cuando la semilla que se utilize para desencriptar halla sido la misma que seutilizo para encriptar.

Figura 7.5: Diagrama de operacion del sistema de generacion de paquetes dedatos para su desencriptacion

Para comprobar que la generacion de paquetes para la encriptacion y des-encriptacion funcionan de manera correcta, se debe ejecutar la generaci onde paquetes para encriptacion a algun archivo e inmediatamente despuesejecutarle la generacion de paquetes para la encriptacion, en ambos casosunicamente se ejecutara la generacion de los paquetes sin agregar las ecua-

ciones de encriptacion o desencriptacion, ya que no se esta ejecutando en-criptacion ni desencriptacion el resultado final debera ser el archivo de textoplano original. Para esto se desarrollo el programa en Labview mostradoen la figura 7.6 con el cual se demostro el correcto funcionamiento de losprogramas generadores de paquetes de datos.

La siguiente etapa consta en implementar y probar las ecuaciones deencriptacion y desencriptacion, las cuales fueron programadas en el micro-






Figura 7.6: Programa que comprueba el buen funcionamiento de la etapa degeneracion de paquetes de datos

controlador junto con una semilla predefinida para el PRNG, desde la PCen Labview se efectua el control de la encriptacion y desencriptacion paralo cual se procesa un arreglo de datos de 15 bits predefinido por el usuario,se procesa para ser encriptado y guardado en otro arreglo de 15 bits paradespues ser procesado y desencriptado, el resultado final debera ser el arreglooriginal dado por el usuario, tal como se muestra en la figura ; una vez hechaesta prueba de obtubieron los resultados esperados y se comprobo la correctaejecucion de las ecuaciones de encriptacion y desencriptacion

Figura 7.7: Diagrama del programa que comprueba el buen funcionamiento

de las ecuaciones de encriptacion y desencriptacion

7.4 Implementacion en Hardware del sistema completo

Una vez comprobado el buen funcionamiento individual de cada una delas etapas del generador, es posible implementar el sistema completo. Se



7.4 Implementacion en Hardware del sistema completo 67

tiene disponible una tarjeta de adquisicion de datos National InstrumentsDIO32HS, la cual cuenta con 4 puertos de 8 bits que pueden ser configura-dos como entrada / salida, ademas de contar con 8 lıneas de handshakingque pueden ser configuradas como entrada o salida, y el microcontroladorPIC16f877A cuenta con 35 lıneas de datos y una lınea de Master Clear Re-set, la tarjeta de adquisicion de datos tiene la capacidad de manejar las 35lıneas de datos y el reset del microcontrolador sin necesidad de multiplexar.Se opto por explotar al maximo todas sus lıneas junto con las del micro-controlador, y se creo un protocolo de comunicacion basado en 4 lıneas decontrol que aseguran la perfecta sincronıa entre la PC y el microcontrolador,

ademas se cuenta con dos puertos de datos, uno de entrada de 15 bits y otrode salida de 15 bits. Las lıneas que utiliza este protocolo se muestran en latabla 7.1.

Lınea FuncionReq Manda una senal en alto para avisar a la PC que el PIC esta listoRdy Manda una senal en alto al PIC, para avisar que la PC esta listaE/D Selecciona la modalidad de Encriptacion o DesencriptacionRst Esta conectada MCLR del PIC, al ponerse en bajo resetea PICDin Introduce datos al PIC

Dout Salida de datos

Tabla 7.1: Lıneas del protocolo desarrollado para la comunicacion entre elPIC y la PC mediante la tarjeta DIO32HS.

De esta manera el dispositivo implementado en hardware dispondra delas lıneas requeridas para el protocolo de comunicacion y su representacionse muestra en la figura 7.11.

El protocolo desarrollado para la sincronizacion entre la PC y el microcon-trolador se muestra en la figura 7.9 para encritpacion y para desencritpacion

en la figura 7.10. Para iniciar el proceso es necesario primero limpiar el mi-crocontrolador por medio de un reset, esto se logra poniendo en bajo la lineaRST, la primera instruccion que realiza el microcontrolador despues del RSTsera poner alto la linea Req para avisar a la PC que esta listo, en este puntola linea E/D ya debe estar en el nivel logico correspondiente al proceso que sedesee ejecutar ya sea encriptacion ”0” o desencriptacion ”1”, la PC respon-dera al microcontrolador poniendo en alto la linea Rdy y el microcontrolador






Figura 7.8: Configuracion de las lıneas del protocolo desde el microcontrolador

pondra en bajo Req en cuanto reciba el valor correspondiente a la linea E/Dy a su vez la PC pondra en bajo Rdy, para los siguientes dos ciclos se estable-cera la semilla baja por medio del puerto Din y la semilla alta con sus 15bits menos significativos por medio del puerto Din y el bit mas significativopor medio de la linea E/D; en el siguiente ciclo la PC enviara un dato de 15bits por medio del puerto Din, para ser procesado por el microcontrolador, yen el ciclo posterior el microntrolador lo regresara ya procesado a la PC por

medio del puerto Dout; de esta manera estos ultimos dos ciclos se repitenhasta terminar de procesar todos los datos que provee la PC.

Figura 7.9: Protocolo de encriptacion

El programa de control, desarrollado en Labiew comienza con la selecci ondel proceso a realizar, encriptacion o desencriptacion y pone el valor logicocorrespondiente a la seleccion en la linea E/D, segun el proceso seleccionado,sera la forma en que se generen los paquetes de datos apartir del archivo que



7.4 Implementacion en Hardware del sistema completo 69

Figura 7.10: Protocolo de desencriptacion

sera leıdo y agrupado en un arreglo con paquetes de 16 bits, una vez que selee el archivo y es acomodado en paquetes de datos, se debe saber de cuantospaquetes consta el arreglo, ya que esta cantidad sera el numero de veces quese repita el ciclo que envıa datos al microcontrolador, antes de comenzar elproceso se deben asignar la semilla alta y baja, una vez que le fue elegido elproceso a realizar y las semillas, el programa pone en bajo la linea Rdy, con elfin de evitar que se halla quedado en alto en algun proceso anterior, despuesse manda un Rst al microcontrolador con el fin de limpiar todos sus registrosy garantizar que comenzara un nuevo proceso, la PC lleva el control de cadaciclo por medio de la linea Rdy, y espera que el microcontrolador termine losprocesos que ejecute poniendo en alto la senal de Req, al ejecutarse el primerciclo se el microcontrolador toma el valor de E/D, cuando el microcontroladorponga en alto la linea Req indicando el inicio del segundo ciclo, el programadebera poner en el puerto Din la semilla baja, y cuando el microcontroladorinicie el tercer ciclo poniendo en alto la linea Req, el programa deber a ponerlos 15 bits menos significativos de la semilla alta en Din y el bit 16 en la lineaE/D, cuando el microcontrolador inicie el cuarto ciclo el programa deberaponer en el puerto Din el primer paquete de datos del arreglo de 15 bitsgenerado apartir del archivo a encriptar, cuando el microcontrolador inicie el

quinto ciclo significa que ya termino de procesar el dato que le fue enviado,y que puso el dato procesado en el puerto Dout, y el programa de controldebea leerlo y almacenarlo en un arreglo, estos dos ultimos ciclos se repitentantas veces como paquetes de datos existan, una vez que se procesaron todoslos paquetes disponibles, al arreglo resultante de los datos procesados le seraagregado el arreglo de 1 bit que se obtuvo apartir del arreglo original de 16bits en que se dividio el archivo original, la posicion en que sera agregado






este bit depende de si se esta encriptando o desencriptando, una vez hechoesto se tiene un arreglo con paquetes de 16 bits, los cuales seran reagrupadosen forma de un archivo, este archivo correspondera al texto plano o bien altexto encriptado segun corresponda el proceso que se ejecute.

La configuracion de las lıneas necesarias para el sistema en el microcon-trolador se pueden apreciar en la figura 7.11

Figura 7.11: Diagrama de la distribucion los pines del microcontrolador.



7.5 Comunicacion Serial 71

7.5 Comunicacion Serial

La interfaz utilizada inicialmente solo es experimental, ya que ofrece un buendesempeno y multiples lıneas de comunicacion; pero es una interfaz que re-quiere equipo adicional a la PC, es especializada y costosa, por lo que esnecesario cambiar a una interfaz de uso mas comun, para que el dispositivode encriptacion pueda ser utilizado en la mayorıa de las computadoras, poresta razon se decidio migrar a la interfaz RS-232, debido a que esta interfazno requiere equipo especial, se encuentra disponible en la gran mayorıa delas PC’s, y el microcontrolador utilizado para este proyecto el PIC16F877A,

cuenta con un puerto RS-232, ademas la programacion de este es muy sen-cilla, ya que PIC-C, que es la utilerıa para programar el microcontrolador,cuenta con instrucciones especificas para el envio y recepcion de datos vıapuerto serial, por otra parte el programa de control que sera desarrollada enLabview, que tambien cuenta con librerıas para el manejo del puerto serialRS-232, facilitando la programacion de todos los elementos que forman partedel sistema. Una ventaja adicional de la interfaz serial es que al convertirtodo el protocolo del sistema del sistema de encriptacion a un modo serial,serıa mas facil migrar del puerto RS-232 a cualquier otro tipo de comuni-cacion serial mas rapida y compleja como lo es el USB.

Para lograr el cambio de interfaz es necesario cambiar el protocolo decomunicacion y algunos cambios de hardware al diseno original, enseguida semuestran algunas particularidades que se tienen que tomar en cuenta para eldesarrollo de una interfaz de tipo serial. Los dispositivos que utilizan cablesseriales con el estandar RS-232 para su comunicacion, estan divididos en doscategorıas, estas son DCE (Data Communications Equipment) y DTE (DataTerminal Equipment), los DCE son dispositivos tales como un MODEM,plotter, etc. y los DTE pueden ser una computadora o una terminal. Debidoa que el el puerto serial RS-232, fue diseado para tener un amplio rangode alcance, el voltage de sus niveles logicos es elevedo con respecto de losniveles logicos manejados por los dispositivos TTL/CMOS, en la tabla 7.2 se

muestran los rangos de voltage para los niveles logicos del estandar RS-232.El microntrolador utilizado en este proyecto cuenta con un puerto RS-232,

pero este no es capaz de proporcionar y soportar los voltajes correspondientesa los niveles logicos que dicta este estandar, ya que solo manda y recivelas senales con los voltajes correspondientes a los niveles logicos de TTL,teniendo en cuenta los niveles logicos requeridos por el estandar RS-232,resulta imposible conectar el microcontrolador directamente a el puerto RS-






Nivel logico Rango0 +3 volts a +25 volts1 -3 volts a -25 volts

Indefinido -3 a +3 volts volts

Tabla 7.2: Niveles logicos para el estandar RS-232

232 de una PC, para lograr acoplar estas dos entidades es necesario que entreellas exista un driver, que ajuste los voltajes a niveles permitidos para cada

una de las partes, el driver que se utiliza para acoplar los niveles l ogicosTTL/CMOS, a los niveles del RS-232 es el MAX-232.

El MAX-232 es capaz de generar +10V y -10V (voltaje que cae dentro deel rango de un 1 y un 0 l ogico del estandar RS-232) apartir de una fuente de5v y recibir voltages correspondientes a un uno o cero logico del estandar RS-232 y convertirlo a un uno o cero logico segun corresponda, compatible conTTL/COMS. Dentro de este circuito se tienen dos receptores y dos trans-misores para RS-232, ası como tambien dos receptores y dos transmisorescompatibles con TTL/CMOS, en la figura 7.12 se muestra el diagrama in-terno del driver MAX-232.

Figura 7.12: Diagrama del MAX-232.

El MAX-232 fungira como convertidor de de niveles logicos entre el micro-controlador y el puerto Serial RS-232. En la figura 7.13 se muestra como elMAX-232 sera un intermediario entre el puerto RS-232 y el microcontrolador.

Existen dos tipos de conectores para los puertos seriales con el estandarRS-232 en las PC’s, el tipo DB 25 con un conector de 25 pines y el tipo DB9



7.5 Comunicacion Serial 73

Figura 7.13: El Max-232 se encarga de acoplar los niveles logicos entre elpuerto RS-232 de la PC y el microcontrolador.

con un conector de 9 pines, en la figura 7.14 se muestra la distribuci on delos pines para cada tipo de conector, el tipo DB25 se considera ya obsoleto yfuera de uso, sin embargo el tipo DB9 sigue vigente; el conector de el puertoque se encuentra en la parte posterior de el CPU de una PC es DB9 macho,por lo tanto se requiere que el conector de nuestro dispositivo hacia la PCsea de tipo hembra.

Figura 7.14: Distribucion de los pines en los conectores DB-9 y DB-25.

El estandar RS-232 cuenta con varias lıneas de handshake, y una lineapara enviar datos ası como una para recibirlos, en la tabla 7.3 se muestranlas lıneas con que cuenta el estandar.

Una vez identificadas las lıneas y su ubicacion en los conectores, es nece-sario saber la funcion de cada una de ellas, en la tabla 7.4, se muestra lafuncion de cada una de las lıneas del estandar RS-232.






Numero de Numero de Abreviacion NombrePin (DB25) Pin (DB9) Completo

Pin 2 Pin 3 TD Transmit DataPin 3 Pin 2 RD Receive DataPin 4 Pin 7 RTS Request To SendPin 5 Pin 8 CTS Clear To SendPin 6 Pin 6 DSR Data Set ReadyPin 7 Pin 5 SG Signal GroundPin 8 Pin 1 CD Carrier Detect

Pin 20 Pin 4 DTR Data Terminal Ready

Pin 22 Pin 9 RI Ring Indicador

Tabla 7.3: En la tabla se muestran las lıneas de comunicacion serial con elestandard RS-232 y su ubicacion en los conectores DB9 y DB25

7.6 Configuracion de modem Nulo (Null Modem)

La configuracion de modem nulo es usada para conectar dos DTE entresı, de esta manera se puede establecer una comunicacion serial de manera

facil y rapida (tiempo de desarrollo). Con esta configuracion las senalesrequeridas para la comunicacion se reducen a solo tres: TD, RD y SG; ylas demas lıneas se conectan entre sı. La idea de esta configuracion es hacerpensar al puerto, que se esta comunicando con un modem en vez de con otroDTE, cualquier dato transmitido desde la PC debe ser recibido por nuestrodispositivo de encriptacion, por eso es que la linea TD que proviene de la PCdebe ser conectada conectada a la linea RD del dispositivo de encriptacion yviceversa, las lineas SG de ambos dispositivos deben estar conectadas entresı, para tener tierras comunes. El diagrama de la configuracion para modemsnulos se muestra en la figura 7.15.

El Data Terminal Ready DTS esta conectado a Data Set Ready y CarrierDetect en ambos extremos de los DTE. Cuando Data Terminal Ready sepone en alto, el Data Set Ready y el Carrier Detect se ponen en alto. En estemomento la computadora cree que el modem virtual al que esta conectadaesta listo y detecto el Carrier del otro modem. Como la comunicacion se haraa la misma velocidad no se requiere control de flujo El Request to Send yClear to Send estan conectadas entre sı. Cuando la PC desea mandar datos,



7.6 Configuracion de modem Nulo (Null Modem) 75

pone Request to Send en alto y como se encuentra conectado a Clear to Send,inmediatamente obtiene la respuesta de que se puede enviar los datos y lohace.

Figura 7.15: Diagrama de conexiones necesarias para implementar un modemnulo.

Debido a que la configuracion de modem nulo, es la forma mas sencilla deimplementar un sistema de comunicacion serial bajo el estandar RS-232, serala configuracion que utilizara el dispositivo de encriptacion para comunicarsecon la PC. De esta manera el microcontrolador cuenta con una entrada yuna salida de datos seriales, que son conectadas con la entrada y la salida de

datos compatible con los niveles logicos de TTL/CMOS del Max-232, y sedebe hacer lo mismo con las senales seriales que provienen de la PC, en lafigura 7.16 se muestra el diagrama de conexiones necesarias para implementarla configuracion de modem nulo entre el microcontrolador y la PC.

Figura 7.16: Conexiones del sistema via puerto RS-232

Debido a que se esta creando un modem virtual y varias lıneas de hand-shaking se estan ignorando, es necesario que el sistema este bien sincronizado,






esto debe lograr por medio del programa de control del puerto desarrolladoen Labview y el programa que controla el puerto desde el microcontrolador,para garantizar la perfecta sincronıa entre estos dos elementos, se deben fijarlos mismos parametros en ambos programas de control del puerto serial.

7.6.1 Parametros requeridos para la configuracion del puertoRS-232

Una vez elegida la configuraciıon de modem nulo, es necesario definir var-ios parametros requeridos por el puerto, para su correcto funcionamiento yperfecta sincronia.

Bits de datos: este parametro se refiere a el numero de bits que serantransmitidos o recibidos por cada envio, el valor utilizado con mas frecuenciaes el de 8 bits.

Bit de paridad: el valor de este bit depende del numero de unos que hayaen el dato transmitido, y es una manera de detectar errores en la transmisionde datos.

Tasa de transmision de datos: Configura la velocidad de transmision enel puerto, esta velocidad no es la velocidad real de transmision de los datos,en esta velocidad tambien van incluidos los bits de control. En la tabla semuestran algunas velocidades comunmente utilizadas en el estandar RS-232,pero a mayor velocidad se incrementa la posibilidad de errores y se disminuyela longitud maxima que puede tener el cable.

Bits de parada: El bit de parada es una medida que indica el final de latransmision de un caracter ya que el equipo que halla transmitido el caracterpondra un uno al final del caracter y este uno durara al menos 1 ciclo de relo jcompleto, aunque el tiempo que permanezca este bit puede ser configuradoa 1.5 ciclos de reloj o bien 2 ciclos de reloj.

Los parametros descritos anteriormente seran configurados desde Lab-

View que cuenta con una instruccion para configurar el puerto RS-232. dichaintroduccion es llamada ”VISA Configure Serial Port”

Enable Termination Char (Booleano): prepara el puerto para recibirun caracter de terminacion. Si esta variable es puesta a ”verdadero” (pre-determinado) el puerto estara configurado para reconocer un caracter determinacion. En caso de que esta variable sea puesta a ”falso” el dispositivoserial no reconocera ningun caracter de terminacion.




Figura 7.17: La instruccion VISA Configure Serial Port, permite configurartodos los parametros necesarios para el RS-232

Termination Char: Fija el caracter de terminacion.Timeout:Fija el tiempo de espera, antes de marcar el puerto como de-

sconectado, para operaciones de lectura y escritura.VISA resource name: Selecciona el puerto serial que se esta configu-

rando.baud rate: Fija la taza de transmision, la taza predefinida es de 9600.Data bits: Fija el numero de bits de los datos. Este valor debe estar

entre 5 y 8 bits. El valor predefinido es 8 bits.Parity: Especifica la paridad utilizada para cada marco a transmitir o

recibir.Error in: Describe las condiciones de error que ocurran antes de que

esta funcion se ejecute.Stop bits: Especifica el numero de bits de parada.Flow control: Fija el tipo de control usado por el mecanismo de trans-

ferencia.Duplicate VISA resource name: genera una copia del puerto selec-

cionado en VISA resource name.Error out: Muestra los errores producidos durante la ejecuci on de la

configuracion del puerto.

Par poder seleccionar los parametros con que sera configurado el puertoRS-232 de la PC, es necesario conocer los parametros validos para el puertodel microcontrolador, y ası lograr seleccionar parametros que sean validospara ambos dispositivos.

La configuracion del puerto RS-232 para el microcontrolador se hace me-diante la instruccion USERS 232(opciones) en donde las opciones, represen-tan cada uno de los parametros que se deben especificar para la configuracion






del puerto y deberan se separados por comas, dichos parametros se muestranen la tabla 7.9.

A este punto, ya se tiene conocimiento de los parametros validos paracada una de las partes el microcontrolador y la PC, de esta manera se debenseleccionar los parametros mas convenientes y compatibles con ambas partes.

La configuracion de los parametros para el puerto serial sera la siguiente:la taza de transmision sera fijada a 9600 bauds, ya que esta taza ofrece unbalance entre seguridad, longitud del cable y rapidez; la paridad sera selec-cionada sin paridad ya que omitir la paridad aumenta la fluidez de los datos,y los bits de datos seran 8 ya que esta es la cantidad maxima que ambos

dispositivos tiene en comun, el bit de parada sera fijado en uno ya que elmicrocontrolador no cuenta con la opcion de cambiarlo. Estos parametrosanteriormente mencionados se configuran en el microcontrolador con la sigu-iente linea:

USERS 232(BAUD = 9600, X M I T = P IN C6,RCV=PINC7,PARITY=N,BITS=8)

Y para labview la configuracion se hace mediante elEstas son las configuraciones que se deben llevar a cabo para el correcto

funcionamiento de el RS-232 por parte de el PIC En el programa de controlhecho en Labview la configuracion de el puerto se hace en el bloque llamadoVISA Configure Serial Port




Abreviacion Nombre FuncionTD Transmit Data Salida serial de datos (TXD)RD Recieve Data Entrada serial de datos (RXD)

CTS Clear To Send Indica que el modem estalisto para intercambiardatos

DCD Data Carrier Detect Se pone en alto cuando sedetecta un ”Carrier” del modemal otro extremo de la lınea

DSR Data Set Ready Le indica a el UART que elmodem esta listo para establecerun lazo

SG Signal Ground Linea de tierraDTR Data Terminal Ready Este el lado opuesto a DSR

Le indica a el modem que el

UART esta listo para establecerun lazo

RTS Request To Send Informa a el modem que elUART esta listo paraintercambiar datos

RI Ring Indicador Se pone en alto cuandoel modem detecta unasenal de Ring

Tabla 7.4: En esta tabla se muestra la funcion de cada una de las lıneas delestandar RS-232.






Configuracion CaracterısticasParidad impar: Cuando el numero de unos dentro de la cadena de datos

sea una cantidad impar, el bit de paridad se pondra a uno.Paridad par: Cuando el numero de unos dentro de la cadena de datos

sea una cantidad par, el bit de paridad se pondr a a uno.Paridad marca: Esta configuracion pone siempre a uno el bit de

paridad.Paridad espacio: Esta configuracion pone siempre a cero el bit de

paridad.

Sin paridad: Esta configuracion indica que el bit de paridadnisiquiera es utilizado.

Tabla 7.5: En la tabla se muestran las configuraciones para el bit de paridad.

Velocidad Distancia maxima(Baudios) (pies)

2,400 30004,800 1000

9,600 50019,200 50

Tabla 7.6: Relacion entre velocidad y distancia maxima de un cable para elRS-232.

Parametro Tipo de paridad0 Sin paridad (predefinido)1 Paridad par2 Paridad impar3 Paridad marca4 Paridad espacio

Tabla 7.7: Seleccion de parametros para la paridad en LabView.




Parametro Tipo de paridad10 1 bit de parada (predefinido)15 1.5 bits de parada20 2 bits de parada

Tabla 7.8: Seleccion de parametros para los bits de parada en LabView.

Comando Funcion Parametros ValidosBaud Configura la velocidad del tipico = 9600

puerto en baudiosXMIT Elige el pin del microcontrolador Cualquier pin de datos

dedicado a la transmision de datosRCV Elige el pin del microcontrolador Cualquier pin de datos

dedicado a la recepcion de datosPARITY Selecciona la paridad N (Sin paridad)

E (paridad impar)O (paridad par)

BITS Selecciona el tamano de las 5,6,7,8,9 bitspalabras

Tabla 7.9: Parametros necesarios para la configuracion del puerto RS-232 enel microcontrolador.





CAPITULO 8

Programa la NIST para la evaluacion de la

aleatoriedad de generados con fines deencriptacion

El programa estadıstico de evaluacion de la NIST cuenta dos variantes,una version para Windows XP llamada STS GUI 1.6 (Statistical Test SuiteGraphic User Interface) la cual contiene una interfaz de usuario grafica demuy facil operacion, pero muestra inestabilidad debido al sistema operativoy tambien a que el tamano de los archivos de secuencias son del orden devarios cientos de megabytes que aunado a la gran demanda de recursos delsistema operativo puede llevar a que la computadora se congele, lo cual hacemuy frecuentes las fallas tanto del sistema operativo como del STS GUI 1.6;la segunda version utiliza Linux como plataforma y es llamada STS 1.5, este

programa no cuenta con una interfaz grafica, se maneja via interprete decomandos y ademas de ser muy estable en su funcionamiento reduce consid-erablemente los tiempos de las pruebas respecto a la version de Windows.La diferencia entre las dos versiones solo es en cuanto a su plataforma e in-terfaz con el usuario, por que ambos se comportan de la misma manera alevaluar las secuencias de datos. Ademas ambos programas incluyen ejemplosde generadores que estan precargados en el programa.

82



83

8.0.2 STS GUI 1.6

Esta version cuenta con una interfaz de usuario de muy intuitiva y de muyfacil manejo, el programa inicia con la ventana que se muestra en la figura 8.1en donde es posible elegir algun generador predefinido con el cual se deseengenerar y evaluar secuencias o bien seleccionar la opcion que nos permitaelegir un archivo generado utilizando algun otro generador, tambien se debeseleccionar el formato en que fueron almacenadas las secuencias, que en estecaso es de bits en formato ASCII, y por ultimo el programa nos permiteseleccionar entre regenerar los resultados de la prueba inmediata anterior obien generar nuevos datos que es la opcion que se debe seleccionar cada vezque se inicia una prueba nueva, una vez seleccionados todas las opciones sele da clic en el boton de siguiente para pasar al siguiente menu.

Figura 8.1: Pantalla principal Nist Statistical Test suite

Despues se muestra cada una de las pruebas separadas en dos categorıas,parametrizadas y no parametrizadas tal y como se puede apreciar en la figura8.2, para elegir las pruebas a ejecutar basta con dar un clic sobre el cuadro cor-respondiente a cada una de ellas, y en el caso de las pruebas parametrizadas





84Programa la NIST para la evaluacion de la aleatoriedad de

generados con fines de encriptacion

escribir los parametros requeridos. Una vez seleccionadas las pruebas a eje-cutar, debemos especificar de que longitud son las secuencias generadas queen este caso son de 1,000,000 y cuantas secuencias fueron generadas una vezseleccionados los parametros necesarios el programa comenzara correr laspruebas, se recomienda no ejecutar ningun otro proceso ni programa ademasdel STS GUI 1.6, ya que esto propicia que las pruebas se ejecuten muy lenta-mente e incluso pueden llegar a trabar la computadora dejando las pruebasinconclusas, el programa terminara la evaluacion despues de varias horas deejecucion.

Figura 8.2: Pantalla de seleccion de las pruebas a ejecutar y alimentacion deparametros

8.0.3 STS 1.5Esta version no cuenta con una interfaz grafica y se maneja en modo detexto, para comenzar a ejecutar las pruebas desde una consola de coman-dos en Linux y situado en el directorio en que fue instalado el programa sedebe ejecutar el comando ./assess ¡Longitud de las secuencias¿, esto quieredecir que si la longitud de las secuencias generadas fue de 106 debemos es-cribir ./assess 1000000, para comenzar el programa Para esta version del STS



85

primero hay que leer el manual de operacion ya que su uso no es del todosencillo pero a cambio ofrece gran estabilidad y rapidez en la ejecucion de laspruebas, ademas de que a diferencia de la version 1.6, en esta si es posibleejecutar otros programas al mismo tiempo en que son ejecutadas las pruebas.

8.0.4 Reportes

Independientemente de la version del STS que se utilize, despues de cualquierevaluacion de secuencias el programa genera varios reportes en los cuales pro-porciona informacion detallada sobre los resultados de las pruebas, por cadaprueba existe una carpeta en la cual se crean dos reportes por cada unade ellas, el primero de los reportes tiene como nombre ”stats” y en este seguarda informacion estadıstica dependiendo la prueba a la que corresponda,el otro reporte es llamado ”Results”, este contendra cada uno de los valores P

obtenidos por cada una de las secuencias evaluadas, y en el directorio princi-pal del programa se crean dos reportes uno de ellos tambien llamado ”stats”,pero este reporte muestra la cantidad de bits leıdos desglosando cuantosfueron unos y cuantos ceros dentro de cada una de las secuencias leıdas; enel directorio principal del programa se genera el reporte mas importante detodos llamado ”finalAnalisysReport” del cual se muestra un ejemplo en lafigura 8.3.





86Programa la NIST para la evaluacion de la aleatoriedad de

generados con fines de encriptacion

Figura 8.3: Pantalla principal Nist Statistical Test suite

En el reporte mostrado en la figura 8.3 se pueden observar diez columnasque van desde la columna C1 hasta la columna C10, estas columnas repre-sentan 10 intervalos en los cuales se dividieron todos los valores P de cadaprueba y muestran la frecuencia de los valores P que caen dentro de esos 10intervalos, despues de estas diez columnas se encuentra la correspondientea la distribucion uniforme de los valores P, y debemos recordar que cadavalor dado en esta columna debera ser superior o igual a 0.0001 para poderconsiderar una distribucion uniforme de los valores P, o de lo contrario setendra evidencia en contra de la supuesta aleatoriedad de las secuencias ydel generador; en la columna marcada en el reporte como ”Proportion” se

muestra el valor correspondiente a la Proporcion de secuencias exitosas, estevalor debe ser confrontado con los valores dados en el pie de p agina en elmismo reporte, y si alguno de los valores no es superior o igual a los mınimosaprobatorios proporcionados por el reporte, se considerara evidencia en con-tra de la supuesta aleatoriedad de las secuencias y el generador. De estamanera en este reporte se muestran los valores definitivos que nos ayudan atomar una determinacion en cuanto a las secuencias y a su generador.



87

*****************************

P j+1f (x) =∞

k=−∞

c j[k]ϕ j,k(x) +∞

k=−∞

d j[k]ψ j,k(x), (8.1)

donde los coeficientes son

c j[k] =

f (x)ϕ j,k(x)dx = f (x), ϕ j,k(x), (8.2)

d j[k] = f (x) ψ j,k(x)dx = f (x), ψ j,k(x). (8.3)

De manera similar, al considerar la expansion dada en (??)

f (x) =

∞k=−∞

c0[k]ϕ0,k(x) +

∞ j=0

∞k=−∞

d j[k]ψ j,k(x), (8.4)

*********************************





Bibliografıa

[1] Marcela Mejıa Carlos, Encriptaci´ on por sincronizaci´ on en aut´ omatas celulares. (2001).

[2] S. Wolfram, Random sequence generation by celular automata. Advancesin Applied Mathematics 7, pp. 123-169, (1986).

[3] Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, ElaineBarker, Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, AlanHeckert, James Dray, San Vo, A statistical test suite for random and pseudorandom number generators for cryptographic applications. (2001).

[4] Song-Ju Kim and Ken Umeno Randomness Evaluation and Hardware Implementation of Nonadditive CA Based Stream Cipher. (2004).

[5] Marcela Mejıa, Sergio Pesina y Jesus UrıasGenerador de secuencias bi-narias pseudoaleatorias basado en un automata celular. (2004).

[6] Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Hand-book of applied cryptography., CRC Press, NY, (1997).

[7] Marc Van Droogenbroeck PARTIAL ENCRYPTION OF IMAGES FOR

REAL-TIME APPLICATIONS .

[8] Nigel Gardner and Mark Siegesmund,PiC C An introduction to program-ming the microchip Pic in CCS C .

[9] John Koeter,Whats an LFSR? .(1996)

[10] The ALTERA advantage,Data book .(1996)

88



BIBLIOGRAFIA 89

[11] Jesus Urıas , Cryptography primitives based on a cellular automaton.(1998).

[12] Bruce Schneier, Applied Cryptography. Second edition. Wiley, NY(1996).

[13] Douglas R. Stinson, Cryptography Theory and Practice. CRC, Boca Ra-ton, Florida (1995).

[14] J.G.G. Dobbe, Faster FFTs.Dr. Dobbs , 125–151 (1995).

[15] W. Meier and O. Staffelbach, Analysis of pseudo random sequences gen-erated by cellular automata , Lectures Notes in Computer Science, vol.547, pp. 186-199, (1992).

[16] S. Nandi, B.K. Kar, and P.Pal Chaudhuri, Theory and applications of cellular automata in cryptography , IEEE Tras. Comput., vol. 43, no. 12,pp. 1346-1357, Dec. (1994).

[17] V. Afraimovich and M. Shereshevsky, “Topological dynamics of cellularautomata”, Selecta Mathematica Sovietica , 11, 355–363 (1992).

[18] “Crypt-x”, http://www.isi.qut.edu.au/resources/cryptx/ ,

[19] George Marsaglia “The Marsaglia Random Number CD-ROM including the diehard battery tests of randomness”,http://www.csis.hku.hk/ diehard/cdrom/ ,

[20] S.R. Blackburn, S. Murohy and K.G. Paterson, Comments on “Theoryand applications of cellular automata in cryptography”, IEEE Trans.Computers , 46, 637–638 (1997).

[21] F. Blanchard, P. Kurka, and A. Maass, Topological and measure–

theoretic properties of one–dimensional cellular automata, Physica D103, 86–99 (1997).

[22] Oded Goldreich, Pseudorandomness, Notices of the AMS , 10, 1209–1216(1999).

[23] Puhua Guan, Cellular automaton public–key cryptosystem, Complex Systems , 1, 51–57 (1987).





90 BIBLIOGRAFIA

[24] D.E. Knuth, Seminumerical algorithms, The Art of computer program-ming , 2, Addison-Wesley, Reading, MA, 1969; second edition, (1981).

[25] C.S. Lent and P.D. Tougwa, A devise architecture for computing withquantum dots, Porceedings of the IEEE , 85, 541 (1997).

[26] D.A. Lind, Applications of ergodic theory and sofic systems to cellularautomata, Physica D, 10, 36–44 (1984).

[27] Willi Meier and O. Staffelbach, Analysis of pseudorandom sequencesgenrated by cellular automata, Lecture Notes in Computer Science , 147

186–189 (1992).

[28] M. Mejıa and J. Urıas, Synchronization in cellular automata and ap-plications to cryptography, From crystals to chaos , to be published byWorld Scientific (1999).

[29] M.J. Mihaljevic, Security examination of a cellular automata basedpseudorandom bit generator using an algebraic replica approach, Lecture Notes in Computer Science , 1225, 250–262 (1997).

[30] M.J. Mihaljevic, Security examination of certain cellular automata basedkey stream generator, Proc. 1996 IEEE Intl. Symp. Information Theory and its Applications , Vol. 1, 246–249 ( 1996).

[31] S. Nandi, B.K. Kar and P. Pal Chaudhuri, Theory and applications of cellular automata in cryptography, IEEE Trans. Computers , 43, 1346–1357 (1994).

[32] T. Siegenthaler, Decrypting a class of stream ciphers using ciphertextonly, IEEE Trans. Computers , c-34, 81–85 (1985).

[33] M.A. Shereshevsky, Ergodic properties of certain surjective cellular au-tomata, Mh. Math. 114, 305–316 (1992).

[34] M.A. Shereshevsky, K–property of permutative cellular automata,Indag. Mathem. N.S. 8, 411–416 (1997).

[35] J.G.G. Dobbe, Faster FFTs.Dr. Dobbs , 125–151 (1995).

[36] J. Urıas, G. Salazar and E. Ugalde, Synchronization of cellular automa-ton pairs, Chaos , 8 814–818 (1998).



BIBLIOGRAFIA 91

[37] J. Urıas, E. Ugalde and G. Salazar, A cryptosystem based on cellularautomata, Chaos , 8 819–822 (1998).

tesisd encriptacion

Documents