cenidet · concede la autorización para que proceda con la impresión de su tesis. atentamente...

D.G.I.T. S.E.P. S.E.I.T.

CENTRO NACIONAL DE INVESTIGACIÓN Y DESARROLLO TECNOLÓGICO

cenidet

SISTEMA DE CRIPTOGRAFÍA BASADO EN LA VERIFICACJÓN COMPARTIDA EMPLEANDO VHDL

T E S I S

PARA OBTENER EL GRADO DE:

M A E S T R O E N C I E N C I A S EN iNGENlERíA ELECTRÓNICA

P R E S E N T A :

GABRIEL T I C 0 NAVA ZEA

ANEXO No.11 M i 0

ACEPTACI~N DEL DOCUMENTO DE TESIS

Cuernavaca, Mor.: a I3 de mayo del 2004

C. Dr. Enrique Quintero-Mármol Márquez Jefe del departamento de Electrónica Presente.

At’n C. Dr. Gerardo V. Guerrero Ramirez Presidente de la Academia de Electrónica

Nos es grato comunicarle, que conforme a los lineamientos para la obtención del grado de Maestro en Ciencias de este Centro, y después de haber sometido a revisión académica la tesis titulada: “Sistema de Encripción de Datos Basado en Verificación Compartida Empleando VHDL”, realizada por el C. Gabriel Tico Nava Zea, y dirigida por el M.C. Javier Meneses Ruiz, y habiendo realizado las correcciones que le fueron indicadas, acordamos ACEPTAR el documento final de tesis, así mismo .le solicitamos tenga a bien extender el correspondiente oficio de autorización de impresión.

Nombre y firma Revisor

Atentam La Comisión de Revisi

‘s. E. p.

y DESARROLLO

Nombre y firma Revisor Revisor

C.C.P. Subdirección Académica Departamento de Servicios Escolares Directores de tesis Estudiante

Cenlro Nacional de InvesIIgacion y Desarrollo Tecnologico Sistema Nacional de Institulos Tecnológicos

ANEXO No. 12 MI1

AUTORIZACI~N DE IMPRESI~N DE TESIS

Cuernavaca, Mor., a 2 1 de mayo del 2004

C. Ing. Gabriel Tico Nava Zea Candidato al grado de Maestro en Ciencias en Ingeniería Electrónica Presente.

Después de haber atendido las indicaciones sugeridas por la Comisión Revisora de la Academia de Electrónica en relación a su trabajo de tesis cuyo titulo es: “Sistema de Encripción de Datos Basado en Verificación Compartida Empleando VHDL, me es grato comunicarle que conforme a los lineamientos establecidos para la obtención del grado de Maestro en Ciencias en este centro se le concede la autorización para que proceda con la impresión de su tesis.

Atentamente

//y&,qiz # C. Dr. Enrique Quiníero-Mármol Márquez Jefe del Departamento de Electrónica

C.C.P. Subdirección Académica Presidente de la Academia de Electrónica Departamento de Servicios Escolares Expediente

DEDICATORIA

A DIOS Fuente de apoyo e inspiración en mi vida.

A mis padres: Luz María y Gabriel Por su apoyo incondicional

A mis hermanos: Alondra y Rafael Por los momentos de alegría que me brindaron.

A mis abuelos: Martha ' y Jorge', Alfa y Rafael' Por su sabidm'a y consejos.

A mis tías: Morris y L a r k Por ser ejemplos de lucha y dedicación.

AGRADECIMIENTOS

AI M.C. Javier Meneses Ruiz, por sus consejos y orientación para la realización de este trabajo de investigación.

Al comité de revisión: M.C. Guillermo Cahue Díaz, M.C. José Martin Gómez López, M.C. Carlos Felipe García Hernández, por los comentarios y sugerencias expresadas hacia este trabajo que contribuyeron a enriquecerlo.

A mis profesores del CENIDET, por compartir sus conocimientos en la formación académica que recibí.

Al personal del CENIDET, en especial a Anita, por todo su apoyo recibido durante mi estancia en este centro de investigación.

A mis amigos y compañeros: Amiro Sánchez, Braulio Márquez, Carlos Sanabria, Edson Estrada, =win Sulub, Efiaín Zaleta, Efrén Flores, J acob Mundo, Jaime Fernández, Janeth Alcalá, José Cruz, Luis Arceo, Mariano López, Mario Juárez, Mauricio Ángeles, Miguel Fonseca y Pablo Mendoza, todos los del “Santos” y a los MKs.

A la SEP, por brindarme su apoyo económico durante mis estudios.

Tabla de Contenido

. . Glosario de terminos ..................................................................... v Lista de figuras ............................................................................ vii Lista de tablas ............................................................................. ix

..

Capítulo 1: Introducción . 1.1. Antecedentes ..................... ................................ 1

1.1.1, Criptografía .................. ................................ 3 1.1.2. Metas de la criptografía ......................................................... 3 1.1.3. Tipos de cnptosistemas ......................................................... 5 1.1.4. Verificación compartida ........................................................ 7

1.2. Planteamiento del problema .......................................................... 7

1.4. Alcances .............................................................................. 9 1.5. Sumario ................................. .................................... 9 1.6. Referencias ........................................................................... 9

. . 1.3. Objetivo ............................................................................... 8

Capítulo 2: Análisis del algoritmo de Hsu y Wu . 2.1. Esquema de verificación compartida de Hsu y Wu ............................. 11

2.1.1. Algoritmo ........................................................................ 12 2.1.2. Analisis al algoritmo ............................................................ 13 2.1.3. Comentarios sobre el algoritmo ............................................... 15

2.2. Alternativas de implementación .................................................... 17 2.2.1.FPGA ............................................................................. 17 2.2.2. ASIC .............................................................................. 19 2.2.3. FPGA vs ASIC .................................................................. 20 2.2.4. Lenguajes descriptores de hardware .......................................... 21

. . .

.. 2.3. Solucion adoptada .................................................................... 22 2.4. Sumario ................................................................................ 25 2.5. Referencias ............................................................................ 25

Capítulo 3: Diseño del criptosistema 3.1. Diseño general del criptosistema .................................................. 27

3.1.1. Esquema de comunicación ............................................ 3.1.2. Esquema de codificación ...................................................... 31 3.1.3. Simulación del algoritmo de encnpción ..................................... 33

3.2.1. Módulo aritmético ............................................................... 35 3.2.1.1. Formato numérico .......................................................... 35 3.2.1.2. Suma con signo ............................................................. 37 3.2.1.3. Multiplicación .. ........................................... 38 3.2.1.4. División ......... ..................................... 3.2.1.5. Potencia ......... ................................................. 42

3.2.2. Módulo de comunicaciones ................................................... 47 3.2.3. Unidad central ..................................... ........................... 48

3.2.3.1. Aportación al esquema de Hsu y Wu .................................... 49 3.3. Sumario ............................................................................... 50 3.4. Referencias ........................................................................... 50

. . . 3.2. Descnpcion del diseño .............................................................. 35

Capítulo 4: Desarrollo y resultados 4.1. Módulo aritmético ................................................................... 54

4.1.1, Version preliminar .............................................................. 54 . . .. 4.1.2. Operaciones básicas ............................................................. 55 4.1.3. Funcion xy ........................................................................ 59

4.2. Módulo de comunicaciones ........................................................ 61 4.3. Unidad central ........................................................................ 63

..

4.4. Resultados de la implementación .................................................. 67 4.5. Sumario ................................................................................ 69

11

Capítulo 5: Interfaz gráfica

................... ........_.. 76 5.2.3. Panel de opciones.. . . .... ... . .. . .. . ... .. . .. . . . . .. .... . . . .. . .. . .. . . . . . . . . . ... ..... 77

5.3. Resultados ................................................................ . . _ _ _ _ _ . . _ 78 5.4. Sumario . __ . . . .................... ........ 5.5. Referencias.. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Capítulo 6: Conclusiones ............................... 81

6.2. Aportación del trabajo ... . . . 6.3. Conclusiones . . . . . _'. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87

............................. 89 .,. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 90

Referencias generales.. , , . , . , . , . . . . . . . . . . . . . . . . . . , . . , . . , . , , . . . . . , . . . . . . . . . . . . . . . . . . . . . . . ..93 Anexos ..................................................................................... 97

... 111

Glosario de Términos

C clase

DDS DES ECDSA firmante

firmware

GF(I>)

Mensaje cifrado. Conjunto de caracteristicas que definen a un objeto dentro de la POO. Digital Signature Standard. Digital Encryption Standard. Elliptic Curve Digital Signature Algorithm. Persona que envía un mensaje dentro de la verificación compartida. Es el “sistema operativo” de dispositivos de hardware con capacidad de procesamiento limitada. Campo finito de Galois.

Half-duplex Comunicación en dos sentidos pero no al mismo tiempo. IDEA internacional Data Encryption Algorithm. K Llave KD Llave de decripción. KE Llave de encripción. M Mensaje a enviar. mcd Máximo común divisor. MD5 Message Digest vS. mod Módulo de dos números (residuo). n Número d e p osibles p ersonas a 1 as que se 1 es p uede enviar un

mensaje dentro de la verificación compartida. OOP Object Oriented Programming (Programación orientada a

objetos). RC2 Rivest Cipher v2. RC4 Rivest Cipher v4.

SHA Security Hash Algorithm. t Número de pers0nas.a las que se les envia un mensaje dentro de

la verificación compartida. verificador Persona establecida como receptor dentro de la verificación

compartida. VHDL VHSIC Hardware Description Language . VHSIC Very High Speed Integrated Circuit. XTR Es' un acrónimo para ECSTR (Efficient and Compact Subgroup

Trace Representation) Grupo cíclico de orden n Z"

vi

Fig . 1.1. Fig .. 1.2. Fig . 2.1. Fig . 2.2. Fig . 2.3. Fig . 2.4. Fig . 3.1. Fig . 3.2. Fig . 3.3. Fig . 3.4. Fig . 3.5. Fig . 3.6. Fig . 3.7. Fig . 3.8. Fig . 3.9. Fig . 3.1 O Fig . 3 . I 1 Fig . 3 . I2 Fig . 3 . I 3

Lista de Figuras

. . . Criptosistema simetnco .................................................... 5 Criptosistema asimétrico .................................................... 6 Diagrama a bloques de un FPGA ........... .......................... 18 Diagrama a bloques de un ASIC ........................................... 20

............................... 23 Proceso de diseño y desarrollo en VHDL ................................ 24 Típica aplicación de encripción ........................................... 27 Proceso de transmision ..................................................... 29 Topología de la aplicación ................................................. 31

Celda lógica de un FPGA .

. . .

Esquema de verificación compartida ( t 5 4) ............................. 31 Aplicación dividida en bloques ............................................ 32 Esquema numérico para 2n bits ........................................... 36 Esquema numérico para el cnptosistema ................................. 36 Diagrama de flujo de la suma con signo ................................. 38 Esquema para la multiplicación ........................................... 39 Diagrama de flujo de la multiplicación ................................... 39 Algoritmo de división con re-almacenamiento .......................... 40 Esquema para división y módulo .......................................... 41 Resultado de la división .................................................... 41

. ........................................... Fig 3.14. Diagrama de flujo de la división 42 Fig . 3.15. Aproximación a exp y a log (1 segmento) ............................... 44 Fig . 3.16. Aproximación a exp y a log (7 segmentos) .............................. 44 Fig . 3.2 7 . Diagrama de flujo de la potencia Fig . 4.1. Proceso de desarrollo ....................................................... 53 Fig . 4.2. Esquema numérico para módulo preliminar ............................. 54 Fig. 4.3. Simulación de operaciones (8 bits) ........................................ 55

.......................................... 47

vii

Fig . 4.4. Fig . 4.5. Fig . 4.6. Fig . 4.7. Fig . 4.8. Fig . 4.9. Fig . 4 . I O . Fig . 4 . I I . Fig . 5.1. Fig . 5.2. Fig . 5.3. Fig . 5.4. Fig . 5.5. Fig . 5.6.

Diagrama de tiempo para operaciones básicas .......................... 57

Implementación de diseño .................................................. 59 Simulación de operaciones (64 bits) ...................................... 58

Diagrama de tiempo para la función 2’. .................................. 60 Diagrama de tiempo para el módulo de comunicaciones .............. 62 Simulación del módulo de comunicaciones .............................. 62 Diagrama de tiempo de los escenarios .................................... 64 Diagrama de tiempo para funciones en escenarios ...................... 65 Descripción de la aplicación final ......................................... 71 Diagrama de contexto del sistema de software .......................... 73 Diagrama cero del sistema de software .................................. 73 Ventana de transmision ..................................................... 75 Ventana de recepcion ....................................................... 77 Ventana de opciones ........................................................ 78

. . . ..

... VI11

Lista de Tablas

Tabla 2.I. Resultados de encripción ................................

Tabla 3.2. Sistema de ecuaciones para la parábola en (1.5, 4) .............. Tabla 3.3. Ecuaciones para cálculo de 2* .................

Tabla 3.5. Posibles valores dentro del esquema de encripción ..................... 49 Tabla 4 . I . Puertos de E/S para operaciones básicas ................................. 56

............... 16 Tabla 3 . I . Comparación de topologías .................................................. 30

Tabla 3.4. Ejemplos de la función potencia ........................................... 46

Tabla 4.2. Puertos de E/S para la función x” .......................................... 59 Tabla 4.3. Puertos de E/S para el módulo de comunicaciones ..................... 61 Tabla 4.4. Puertos de E/S para la unidad central., .................................. 64 Tabla 4.5. Tiempos de ejecución ....................................................... 69

Tabla 6.2. Tiempos de ejecución., .................................................... 82 Tabla 6.3. Posibles valores dentro del esquema de encnpción ..................... 85 Tabla 6.4. Comparación de tajetas de encripción ................................... 86

.................................................... Tabla 6 . I . Comda de simulación., 81

Capítulo 1

Introducción La criptografía surge hace algunos aios coma una práctica individual basada en la aplicación de técnicas empíricas con el f in de proporcionar seguridad a la información. Hoy en día es considerada una ciencia, y cuenta con cuatra grupos básicos de sistemas de encripción: los de encripción por bloques. cálculo de hash, los de llave privada y los de llave pública. Es necesario mencionar también que acfualmente los criptosistemas que han cobrado más importancia son los de llavepública.

1.1. ANTECEDENTES

A través de los años, muchos protocolos y mecanismos complejos han sido creados para hacer frente a los problemas de seguridad a la información. Actualmente la seguridad de la información se logra mediante el diseño de herramientas de hardware y software dedicadas que implementen los algoritmos matemáticos y protocolos para generar información cifrada, misma a la que sólo pueden accesar quienes tienen la autoridad para conocer su contenido. La creciente cantidad de aplicaciones que se encuentran hoy en día en las cuales la seguridad de la información es vital, han hecho que estos mecanismos de seguridad evolucionen hasta llegar a establecer lo que se conoce como criptografía. Es por esta gran cantidad de aplicaciones que existen muchas tendencias en enfatizar la necesidad de desarrollar mecanismos de seguridad en redes de trabajo [5] , esto debido a todos los posibles ataques a los que se encuentra expuesta la información dentro de los sistemas de comunicaciones actuales, los cuales se pueden dar debido a cuatro causas principales. Primero, el incremento del uso de redes para proporcionar acceso remoto a computadoras facilita a los intrusos el ataque a las redes; segundo, la creciente cantidad y valor de la información existente en las redes las convierte en un blanco más importante para los ataques externos. La tercera causa es debido a que los sistemas computacionales conectados mediante redes de trabajo comparten una gran cantidad de recursos, por lo que la seguridad de la información en un servidor dado depende de las medidas de seguridad empleadas en la red y por otros servidores. Por Último, el empleo de nuevas tecnologías facilita ciertos ataques debido al poco desarrollo que se ha hecho sobre ellas en cuestión de seguridad.

I

~

Capitulo 1 Introducción

Las violaciones de seguridad se pueden dividir en tres categorías: - Liberación no autorizada de información. - Modificación no autorizada de información. - Uso no autorizado de recursos.

Una de las aplicaciones en donde se hace necesario el uso de sistemas de seguridad se presentó hace algunos años en un sistema de comunicación entre EUA y Rusia [l]. Como parte de una investigación de pruebas nucleares norteamericana (en combinación con Rusia), se colocaron sismógrafos en suelo ruso para monitorear la actividad sísmica y detectar actividad nuclear. Aparentemente, estos dos países contaban con la tecnología para implementar estos dispositivos de manera segura, sin embargo, existía una cierta preocupación acerca de la seguridad en la transmisión de los datos de estos dispositivos. La solución inmediata para el gobierno de los Estados Unidos fue emplear un sistema cnptográfico para proteger la información enviada. Lamentablemente esto creó otro problema, ya que Rusia no podría recuperar la información a menos que conociera el sistema de encripción de los Estados Unidos, lo cual los norteamericanos no estaban dispuestos a permitir. Aún así, la criptografia ha evolucionado tanto que les ofreció otra alternativa de solución a su problema. La solución a este problema fue un esquema de encripción llave pública mediante el cual, los rusos sólo necesitaban conocer la mitad del sistema de encripción para recuperar la información.

Otra problemática representativa de la importancia de mantener los datos de una transmisión seguros son los cajeros automáticos. Los cajeros automáticos son usados ampliamente, las 24 horas del día los usuarios pueden aproximarse a ellos y mediante el uso de un protocolo típicamente basado en códigos y tarjetas magnéticas realizan la extracción de dinero. Usualmente el cajero está conectado vía telefónica a una computadora central la cual lleva un registro de los clientes, y cuando se cumplen las condiciones apropiadas transmite los comandos para liberar el dinero. La seguridad que se encuentra implícita en el NIP (Número de Identificación Personal) y en la tarjeta es concerniente al sistema bancario solamente, pero existe un problema de inseguridad de la información en la línea entre el cajero y 1 a computadora c entral, e 1 cual c onsiste e n e vitm que s e i nserten mensajes q ue ocasionen una liberación de una cantidad de dinero ilegítima. Este problema se solucionó mediante un esquema criptográfico, específicamente uno de llave pública. La computadora central calcula la llave privada y la pública, manteniendo la primera y enviando la llave pública al cajero. El cajero se encarga de generar un número aleatorio R (que se empleará únicamente en esta transacción), lo codifica y lo envía de regreso. A partir de ese momento, la computadora usa el número R para codificar y decodificar todos los mensajes necesarios dentro de la transacción.

2

* < . ’ “‘C Introducción Capítulo 1

Como se puede apreciar con un par de ejemplos, existen demasiadas aplicaciones que se basan en el intercambio de información en las cuales, es primordial realizar la transmisión de manera segura. La solución matemática que asegura que las transmisiones digitales se realicen de manera confidencial es la criptografía.

1.1.1. Criptografía

La cnptografia [6] es la ciencia que estudia las técnicas matemáticas relacionadas con aspectos relacionados a la seguridad de la información, entre los cuales se encuentran: confidencialidad, integridad y autentificación de datos y del origen, no repudiación, etc. Su finalidad es transmitir mensajes cifrados de tal forma que estos no puedan ser interpretados por receptores no autorizados. Esta ciencia ha sido muy utilizada debido a su gran variedad de aplicaciones, las cuales están orientadas básicamente a aspectos de comunicación segura, identificación, verificación compartida, certificación, recuperación, comercio electrónico y acceso remoto, entre otros. A través de los años, la criptografía ha sido un arte practicado por aquellos individuos que han diseñado técnicas específicas para cubrir algunos de los requerimientos de la seguridad de la información. Los últimos 20 años fueron un periodo de transición en el que la disciplina de la criptografia se transformó de ser un arte a una ciencia. Hoy e n día, hay muchas conferencias científicas a nivel internacional que se dedican Única y exclusivamente a la criptografía, además de que una organización internacional, la IARC (Internacional Association For Cryptology Research), se ha dedicado de lleno a investigar en esta área. Existen dos procesos que conforman a la criptografía: encripción y decripción [8, 91, y éstos contribuyen a que los usuarios puedan tener una comunicación segura a través de medios electrónicos. El objetivo de la encnpción es la transformación de datos de tal forma que sea imposible su lectura sin una información secreta apropiada (llave). La decripción, proceso inverso, es la transformación de los datos encriptados a un formato entendible.

1.1.2. Metas de la Criptografía

Si bien, el objetivo de la criptografia parece estar bien definido desde su comienzo, hace falta definir con mayor claridad qué es lo que se pretende lograr en cada caso particular de su implementación. Dentro de los avances que han surgido en la criptografía a través de los años, variados criptosistemas se han desarrollado con diversos propósitos. Actualmente, los sistemas criptográficos son desarrollados en base a las siguientes metas [7]:

3


1. Privacidad y confidencialidad. Hay muchos métodos para proveer la confidencialidad, los cuales van desde los métodos físicos de protección hasta los algoritmos matemáticos que mantienen los datos ilegibles.

2. Integridad de los datos. Servicio que direcciona la alteración sin autorización de los datos.

3. Autentificación. Servicio relacionado con la identificación, esta función se aplica a las entidades y a la información por igual.

4. No repudiación. Servicio que previene a las entidades de negar acciones previas.

Para realizar todas las actividades encomendadas a un sistema de encripción de datos, éste se basa en primitivas. Las primitivas son las acciones que se realizan en este tipo de sistemas para poder alcanzar las metas propuestas. Estas primitivas deben de ser evaluadas con respecto a varios criterios tales como:

1. Nivel de seguridad. Usualmente este criterio está dado en términos del número de operaciones requeridas para lograr su objetivo. Este criterio es también llamado el factor de trabajo.

2. Funcionalidad. Las primitivas que sean más efectivas para un objetivo dado serán determinadas por las propiedades básicas de las primitivas.

3. Métodos de operación. Una primitiva puede proporcionar una funcionalidad variada dependiendo de su modo de operación.

4. Rendimiento. Este criterio se refiere a la eficiencia de una primitiva en un modo particular de operación. Un ejemplo de esto podría ser la velocidad de encripción. Un sistema puede ser catalogado por el número de bits por segundo que es capaz de encriptar.

5. Facilidad de implementación. Este parámetro se refiere a la complejidad de implementar la primitiva ya sea en un ambiente de hardware o software.

4

Introducción Capitulo I

1.1.3. Tipos de Criptosistemas

En forma general, existen cuatro tipos de criptosistemas:.por bloques, de hashing, de llave secreta o simétrica y de llave pública o asimétrica [2]. Aunque claro está, es posible una combinación de estos.

Algoritmo de encripción por bloques. Son aquellos algoritmos que encriptan los mensajes en unidades de tamaño fijo llamadas bloques. El tamaño usual de un bloque es de 64 bits. Un ejemplo de este algoritmo es IDEA (International Data Encryption Algorithm).

Algoritmo de hash. También conocidos como algoritmos de cálculo de hush. Son algoritmos que buscan cumplir con sólo una de las metas de la criptografia, integridad de los datos. Ejemplos de este tipo de algoritmo son MD5 (Message Digest version 5) y SHA (Security Hash Algorithm). Esta clase de algoritmos tuvo un auge muy importante debido a que es relativamente fácil calcularle el hash a un mensaje.

Criptosistema Simétrico. Se trata de un algoritmo de llave secreta (ó simétrico) cuando las claves para cifrar y descifrar son idénticas, o fácilmente calculables una a partir de la otra. Esto quiere decir que si utilizamos un criptosistema de clave secreta, necesariamente las dos partes que intercambian información tienen que compartir el secreto de la clave, puesto que tanto para encriptar como para decriptar se necesita una misma clave, u otra diferente pero deducible fácilmente de la primera. Entre estos sistemas se encuentran: DES (Digital Encryption Standard), RC2 (Rivest Cipher v2), RC4 (Rivest Cipher v4), etc. La peculiaridad de estos sistemas de encnpción es que rápidamente se aplican sobre la información. Véase figura 1.1.

K P=D(K,E(K,P))

ción

Fig. I . 1. Criptosisiema Simélrico.

Criptosistema Asimétrico. Si las claves para cifrar y descifrar son diferentes, y una de ellas es imposible de calcular por derivación de la otra, entonces se trata de un criptosistema asimétrico o de llave pública. Cuando se está utilizando este método se dice que se está empleando una firma electrónica o digital. La firma digital consiste en establecer un par de claves asociadas a un sujeto: una pública, conocida por todos los

5


elementos que intervienen en el sector, y otra privada, sólo conocida por el sujeto en cuestión. De esta forma, cuando queramos establecer una comunicación segura con otra parte, basta con encriptar el mensaje con la clave pública del sujeto para que a su recepción, sólo el sujeto que posee la clave privada pueda leerlo. Véase figura 1.2.

KE KD

P - p, C P=D(KD,E(KE,P)) Encripción - Decripción ---+

Fig, 1.2. Criplosislerna Asirnétrico.

Si el mensaje original a transmitir P es una secuencia de caracteres individuales:

p = (Pi, p2, ... , P")

y en forma similar el texto cifrado se escribe como:

Las transformaciones entre el mensaje original y el texto cifrado pueden escribirse:

C = E(P) y P = D(C)

Donde C representa el texto cifrado, E el algoritmo de encripción, P el mensaje original y D el algoritmo de decripción. Utilizando esta connotación, un criptosistema puede ser representado:

P = D(E(P))

Algunos algoritmos de encripción utilizan una llave K, de tal manera que el texto cifrado depende tanto del mensaje original como del valor de la llave. Esto se representa como:

C = E(K,P)

Donde E es un conjunto de algoritmos de encripción y K es la llave que selecciona un algoritmo específico. Cuando las llaves de encripción y decripción son iguales, se tiene un criptosistema simétrico y se representa como:

P = D(K,E(K,P)).

6

c

Introducción Capítulo 1

Cuando la llave de decripción KD invierte la encripción de la llave KE, el criptosistema es asimétrico y se representa como:

P = D(KD,E(KE,P).

1.1.4. Verificación Compartida

El tipo de algoritmo usado dentro de los sistemas cnptográficos ha ido cambiando conforme el paso de los años debido a las diferentes necesidades de comunicación segura existentes. En la actualidad, una alternativa muy solicitada es la de los algoritmos asimétricos, a pesar de esto, en los años recientes ha surgido un planteamiento que no se había considerado, ¿qué se hace cuando un mensaje se desea enviar a un elemento en específico dentro de un grupo de verificadores, sin que los otros elementos lo puedan recuperar? En otras palabras, lo que se plantea es el hecho de mantener los mensajes confidenciales aún dentro de un entorno de comunicaciones seguro, definido para un cierto número de participantes. La solución a este problema dentro de la criptografía se le conoce como esquema de verificación compartida, y su finalidad es compartir un mensaje seguro a t de n participantes dentro del entorno de comunicación.

Aunque en estos últimos años ha surgido más de un"esquema que implemente la verificación compartida en sus algoritmos, hasta ahora el único de ellos que se puede considerar como completo es el presentado por Hsu y Wu en 1998 [3]. Este esquema de verificación compartida es el único que emplea tanto encripción de mensajes como adición de firma digital en un ambiente de llave pública, por lo que es considerado el más robusto de su tipo y una alternativa muy importante para desarrollar herramientas de encripción.

1.2. PLANTEAMIENTO DEL PROBLEMA

Con el auge de las computadoras y de las telecomunicaciones, hoy en día existe la posibilidad de realizar una gran diversidad de actividades de manera virtual. Como ejemplo de estas actividades se pueden citar: envío de documentos, transacciones bancarias, compras en línea, etc. El problema que conlleva el manipular la información electrónicamente en redes públicas es la poca seguridad de la información en comunicaciones de este tipo. Este problema se acentúa debido a que los medios de comunicación no proporcionan por sí mismos ninguna

7


clase de seguridad a los datos que por ellos transitan, una vez que los datos son liberados a través de ellos y quedan fuera de la supervisión humana son vulnerables a ser accesados por terceros 151. En base a esta creciente problemática, dentro de las comunicaciones digitales surge un amplio rango de aplicaciones a desarrollar que sirvan como solución al problema de inseguridad en la transmisión de mensajes electrónicos. Lo que se propuso en este trabajo de tesis para combatir la inseguridad en las comunicaciones es desarrollar un sistema criptográfico q ue s ea capaz tanto d e encnptar c omo d e d ecriptar archivos electrónicos a nivel de hardware. Para esto se utilizará el algoritmo conocido como verificación compartida, el cual, cumple perfectamente con los dos parámetros que se utilizan como métrica para la comprobación de la eficiencia de un algoritmo dentro de la criptografía: la velocidad de encripción y el nivel de seguridad [4].

1.3. OBJETIVO

Esta tesis tiene como objetivo diseñar una herramienta de hardware que combata el problema de la inseguridad en las transmisiones digitales basada en el esquema de encripción de datos con verificación compartida de Hsu y Wu [3]. Dicha herramienta será diseñada mediante el empleo de lenguajes descriptores de hardware (HDL’s). De tal forma qué, aprovechando las ventajas que hoy en día se tienen con los HDL’s en la especificación y simulación de sistemas digitales, se cuente con el diseño del firmware para implementarse en hardware.

Cuando se emplea únicamente la palabra diseñar en la determinación del objetivo, se excluye la etapa de validación física del sistema. La razón para definir el objetivo de esta forma es que los lenguajes descriptores de hardware hoy en día constituyen herramientas tan poderosas, que los resultados producidos por las simulaciones representan un fiel reflejo del comportamiento esperado del hardware, mientras que un buen desempeño en las etapas de síntesis e implementación de diseño dentro de la programación le asegura al usuario que su sistema tendrá el rendimiento esperado. La etapa de validación (implementación y pruebas físicas al criptosistema diseñado) queda fuera del alcance de este trabajo, el cual se enfoca a la obtención de resultados satisfactorios en las simulaciones, y con el cumplimiento del proceso de diseño y especificación de un sistema digital en el HDL seleccionado posteriormente. La posibilidad de la realización de pruebas físicas queda abierta, y dependerá exclusivamente de la adquisición de los recursos materiales necesarios para cumplir con este propósito.

8

,p*- CI 1 - Introducción Capitulo I

1.4.ALCANCES

- Desarrollo de un esquema teórico para el diseño un sistema de encripción de datos con verificación compartida.

- Desarrollo del firmware.

- Simulación en computadora basada en un lenguaje descriptor de hardware en el cual se validará el esquema teórico antes mencionado.

- Sofíware de prueba para enviar datos desde una PC a través del sistema desarrollado.

- Interfaz entre el criptosistema y una PC.

1.5.SUMARIO

Dentro de este capítulo se analizaron los tipos de criptosistemas que existen, así como la importancia que éstos han tomado en la actualidad. De los opciones disponibles dentro de la c riptografia, 1 os algoritmos d e 1 lave pública son 1 os d e mayor demanda debido a que ofrecen una mayor seguridad que los otros algoritmos. A pesar de que los algoritmos de llave pública parecen ser la solución para la mayoría de los problemas de inseguridad en las comunicaciones electrónicas, se ha generado un nuevo tipo de algoritmo de encripción denominado verificación compartida.

1.6. REFERENCIAS

[I] Adleman, L; Rivest, R: “The use of public key cryptography in communication system design”, Communications Magazine, IEEE, Vol. 16, Issue: 6, Nov 1978, Pages: 20 - 23

121 Hernández, Hector; “Criptografia de Verificación Compartida”, ELECTRO 2001

[3j HSU C.L, WU T.C: ”Authenticated encryption scheme with (t,n) shared verification“, LEE Proceedings, 117-121 January 1998.

9


141 Lopez, J; Ortega, J.J; Troya, J.M; Vivas, J: “High-level specification of security systems”, Global Telecommunications Conference, 2003. GLOBECOM ‘03. IEEE , Volume: 3, 1-5 Dec. 2003, Pages:1506 - 1510.

[SI Voydock, V; Kent, S: “Security in high-level network protocols”, Communications Magazine IEEE, Volume: 23, Issue: 7, July 1985, Pages:12 - 24

[6] Seguridad Electrónica: Criptografía [en línea] [Fecha de consulta: Octubre 20021, disponible en:

[7] INEI: Metodologías Informáticas - Seguridad en Internet [en línea] [Fecha de consulta: Octubre 20021, disponible en: ~http://www.inei.gob.pe/biblioineipub/bacopub/Inf/L~b5010/indice.htm~

[S] Apuntes Electrónica: Criptografía [en línea] [Fecha de consulta: Octubre 20021, disponible en:

i

(91 Apuntes Electrónica: criptografía [en línea] [Fecha de consulta: Octubre 20021, disponible en:

10

http://www.htmlweb.net/seguridad/cnptohttp://www.infoapuntes.com.ar/Apuntes/cnptografiahttp://www.infoapuntes.corn.ar/Apuntes/criptograf�a2.htm

Capítulo 2

Análisis del Algoritmo de Hsu y Wu

El objetivo de esta tesis es el de generar una herramienta de hardware que sea una aliernafiva más para combatir la inseguridad en las irasmisiones digitales. Esta herramienta estará desarrollada en YHDL, con elpropósito de aprovechar las ventajas que proporcionan los lenguajes descriptares de hardware. Todo el diseño se llevará a cabo con el objetivo de ser implementado en un dispositivo FPGA.

2.1. ESQUEMA DE VERIFICACIÓN COMPARTIDA DE HSU Y WU

Este esquema es diseñado a partir de uno de los conceptos más solicitados actualmente dentro de la criptografía: la verificación compartida. La diferencia entre este esquema y los propuestos con anterioridad es que en su ejecución se lleva a cabo la firma digital y la encripción, procesos que no se habían visto en el mismo criptosistema de verificación compartida hasta ahora. Estas características convierten a este algoritmo en un tema interesante desde el punto de vista de un trabajo de investigación, y es por eso que esta tesis se basa en él [3]. Teniendo identificado el algoritmo que se va a implementar, es necesario verificar que éste cumpla con los requerimientos que exige un trabajo de tesis. Uno de estos requerimientos es la innovación. AI momento de presentar la propuesta correspondiente a esta tesis no se encontró registro de implementaciones físicas realizadas del esquema de Hsu y Wu, con lo que se logra abarcar la exigencia correspondiente a la innovación. El otro punto que es necesario satisfacer en el desarrollo de un trabajo de tesis es la calidad del producto final. Éste es un aspecto para el cual no es necesario hacer un análisis más profundo al algoritmo seleccionado, debido a que las características que presenta (velocidad de encripción, seguridad, etc.), que sirven como punto de comparación con otros algoritmos, ya han sido revisadas en trabajos anteriores [2]. El resultado de este análisis comparativo demostró que realmente se trata de un algoritmo que puede competir con los ya existentes en aspectos más trascendentes que el de la innovación. En adición a esto, hay que remarcar que se le esta dando continuidad a un trabajo previo referente a este esquema 121.

Capítulo 2 Análisis del algoritmo de Hsu y Wu

Es por estas razones que se considera que el esquema de verificación compartida de Hsu y Wu es el indicado para ser empleado como la base del sistema criptográfico objeto de esta investigación.

2.1.1. Algoritmo

El (I, n) de Hsu y Wu, es un esquema con autentificación de encripción y empleo de técnicas de verificación compartida (31. En este esquema cualquier texto cifrado de firma para un mensaje es direccionado a un grupo específico de verificadores, de tal forma que la habilidad de descifrar la firma es regulada por el esquema adoptado (f, n). Esto es, cualquier t de n participantes en el grupo comparten la responsabilidad (o autoridad) para la recuperación del mensaje. Este esquema conserva el diseño de firma con recuperación del mensaje y el modelo de verificación compartida (t, n).

El esquema se divide en 4 escenarios: - Inicialización del Sistema - Registro - Encripción de Firma - Recuperación del Mensaje

En el escenano de inicialización la autoridad del sistema (SA) define sus parámetros y los hace públicos. Después de esto, SA puede aceptar el registro solicitado por un firmante o un grupo de verificadores. Para el registro del firmante, SA genera una llave secreta y una llave pública; mientras que para el registro del grupo y sus verificadores, SA primero genera una llave secreta y una llave pública para el gnipo, luego emplea el esquema (f, n) de Shamir para dividir la llave secreta del grupo en n porciones y los reparte a cada Verificador del grupo a través de un canal seguro. La parte que el verificador mantiene para él es usada como la llave secreta para la recuperación del mensaje más tarde. En el escenario de encripción de firma el firmante usa primero su propia llave personal para generar la firma de un mensaje direccionado a un grupo especificado, luego usa la llave pública del grupo para producir el texto cifrado de firma y lo envía a los verificadores en ese grupo. La culminación de este escenario finaliza el proceso de transmisión de datos. En el escenario de recuperación del mensaje, cualquier t de n verificadores en el grupo, teniendo la propiedad de decriptar el texto ciflado recibido, puede cooperativamente recuperar y verificar el mensaje.

12

Análisis del algoritmo de Hsu y Wu Capitulo 2

2.1.2. Análisis al Algoritmo

Para poder comprender de manera más amplia el proceso de cifrado y descifrado del esquema elegido, se presenta una descripción más amplia de él. Este desarrollo del algoritmo está dividido en sus cuatro escenarios, y dentro de cada uno de ellos se generan los números de una corrida normal.

Inicialización El primer paso es encontrar dos primos grandes O, y y) que cumplan con

Yb-1.

En este caso se seleccionan dos primos pequeños: y = 3 p = 7. El primo más grande O,) nos dice el máximo mensaje que puede ser enviado. Así entonces, el mayor mensaje que se puede enviar con este ejemplo es el 7.

Como última parte de la inicialización, el sistema selecciona un generador g de orden y en GFO,). Es decir [4],

g = d modp (2.1) con

1 < w < ( p - l ) Y j = (p - l)/y

p. y y g se hacen públicos. Continuando con el ejemplo

w = 3 :. g=2

Registro Una vez teniendo a p , y y g, el sistema debe de seleccionar aleatóriamente a X A , que es la llave personal del firmante A. El criterio para seleccionar esta llave es el siguiente:

x, €2,' endonde Z , = { a l l < a l ( y - l ) , mcú(a,y)=l}

En el caso particular de este ejemplo: xa = 2. Conociendo el valor de XA, se calcula la llave pública de A:

y~ = gU'modp (2.2) ya = 22 mod 5 = 4

13

Capitulo 2 Análisis del algoritmo de Hsu y Wu

Lo anterior se repite para el gmpo de verificadores G, pnmero se escoge la llave personal x, E z;

obteniendo para el ejemplo XG = 1 y~ = gxG modp y ~ = 2 m o d 5 = 2 I

(2.3)

Después de esto, el sistema genera aleatóriamente un vectorf(v) de grado ( t - I) . Donde t es el n úmero d e elementos dentro del grupo d e v enficadores a 1 os cuales se 1 es enviará e 1 mensaje.

(2.4) f ( v ) = x , +a,v I +...+( a,.,v'-l)modq

ai E Z, en donde Z, = {O,l, ...,q- I}

Siguiendo el ejemplo ai = 2 aZ=l.

La última parte de esta etapa consiste en generar las claves personales x, y la correspondiente clave pública y, para cada verificador:

(2.5) x, = f (10, ) x1=4 y1 = 2 x 2 = 6 y2= 1 x3 = I y3 = 2 (2.6) y , = gx' modp

No se hace nada oculto después de que la etapa de registro acabó.

Encripción de firma En esta etapa es donde se define el mensaje M a ser enviado, y en ella debe de cumplirse lo siguiente:

M e Z ,

Para poder obtener el texto cifrado se debe de seleccionar un entero k E 2,' para generar la firma (Y, s) para M

r = (Mg-')modp (2.7)

s = (k - x,r)mod q (2.8)

Para propósito de este ejemplo tenemos que: k = 2 .

14

Análisis del algoritmo de Hsu y Wu Capítulo 2

Entonces, el sistema selecciona un número aleatorio d E Z, (d = 2) y genera la firma cifrada (ci, ~ 2 , cj) correspondiente al mensaje M, donde

c, = g d modp

c2 = (iyid)modp (2.10)

c, = s (2.1 1)

Recuperación del mensaje Primero, cada uno de los Verificadores a los que les fix enviado el mensaje calcula E; utilizando la siguiente ecuación:

Ei =C(JiL!modq)modp 1 (2.12)

donde: Lj = f i - í D j ( í D j -íDj)-lmodq (2.13) j=i ,i+ j

Cuando todos los verificadores involucrados han cumplido esta etapa, envían el valor de E; a los otros, y ahora cada uno calcula

E = f i E j modp j=l

Con este valor se calcula la firma de M I =c,Emodp

s = cj

Finalmente, con estos valores se puede calcular M M =g’y;rmodp

(2.14)

(2.15)

(2.16)

(2.17)

Considerando los valores calculados hasta la etapa de registro y las fórmulas presentadas en los dos siguientes escenarios, se completa el ejemplo para una transmisión de mensajes a tres verificadores dentro de un grupo de 10 personas. El ID para cada uno de los tres verificadores es 1,2, y 3 respectivamente (Tabla 2.1).

2.1.3. Comentarios sobre el Algoritmo

- El número de caracteres permitidos está limitado por el número primo p .

15


Mensaje.. .............. Firma .................... Texto cifrado (4, 0.0625, 1.5)

Mensaje ............................ 2

Mensaje.. .......................... 3 Firma .............................. (0.75, 0.5) Texto cifrado

Mensaje ........................... .4 Firma .............................. (1, O) Texto cifrado ........................ (4, 0.25, O)

. (4, 0.1875, 0.5)

Mensaje.. ............. 6 Firma .............................. (1.5, 2) Texto cifrado ........................ (4, 0.375, 2)

Mensaje. ......................... ..7 Firma .............................. (1.75, 1.5) Texto cifrado ........................ (4, 0.4375, 1.5)

Tabla 2. I . Resultados de encriDción.

- Se necesita manejo de números racionales.

- Se requiere quep sea como mínimo 256 para poder enviar mensajes de 8 bits.

- El mensaje original incrementa su tamaño 3 veces.

- El algoritmo no incrementa significativamente con el aumento del número de verificadores.

- Existe la posibilidad de que la última persona en compartir su clave cometa un engaño para ser él el único en realizar una correcta recuperación del mensaje.

16


- De la selección de los valores aleatorios iniciales depende que los números subsecuentes no sobrepasen los recursos del sistema.

2.2. ALTERNATIVAS DE IMPLEMENTACI~N

El propósito de esta tesis es implementar el algoritmo descrito anteriormente haciendo uso de la programación en HDLs. Los programas realizados en esta clase de lenguajes están enfocados a diversos dispositivos de hardware acorde a su-aplicación. En este caso en específico, y debido a la capacidad requerida por un criptosistema, existen dos dispositivos que pueden servir como plataforma para los programas que se generen. Estos dispositivos son el ASIC y el FPGA. Antes de poder tomar una decisión acerca de cual de los dos es indicado para este trabajo, se realizó una exploración de sus características y un comparativo entre ellos.

2.2.1. FPGA

Antes de la llegada de la lógica programable, los circuitos de lógica tradicional se construyeron a nivel tarjeta usando componentes estándar, o a nivel de compuertas en costosos circuitos integrados de aplicación específica. El FPGA' (Field Programmable Gate Array) es un circuito integrado que contiene muchas celdas lógicas idénticas que pueden ser vistas como componentes estándar. Cada celda lógica puede adquirir independientemente alguna funcionalidad de un conjunto limitado de personalidades. Las celdas individuales están interconectadas por una matriz de líneas y switches programables. Un diseño de usuario es implementado mediante la especificación de funciones de lógica simple para cada celda. Diseños complejos son creados mediante la combinación de estos bloques básicos para crear el circuito deseado.

La arquitectura de celdas lógicas varía entre las diferentes familias de dispositivos IS]. Hablando en general, cada celda lógica combina pocas entradas binarias (típicamente entre 3 y 10) a una o dos salidas de acuerdo a una función lógica booleana especificada en el programa del usuario. En la mayoría de las familias, el usuario además tiene la opción de registrar la salida combinatorial de la celda, de tal manera que la lógica de reloj puede ser fácilmente implementada. La lógica combinatorial de las celdas puede ser fisicamente implementada como una pequeña tabla de memoria (LUT - Lookup Table) o como un conjunto de multiplexores y compuertas. Los dispositivos LUT intentan ser un poco más

17


flexibles y proveen más entradas por celda que las celdas multiplexadas a costa de retraso de propagación. Las palabras Field Programmable de las que se desprenden las siglas FPGA, indican que la función del dispositivo está definida por el usuario mediante un programa, en lugar de estar especificada por el fabricante. Un circuito integrado típico lleva a cabo una función particular definida al tiempo de manufactura. En contraste, la función del FPGA esta definida mediante un programa escrito por alguien diferente al fabricante del dispositivo. Dependiendo del dispositivo en particular, el programa es quemado permanente o semi- permanentemente en el dispositivo o como parte de un proceso de ensamble de la tarjeta, o es cargado desde una memoria externa cada vez que el dispositivo es encendido. Esta programabilidad de usuario nos permite tener acceso a diseños integrados complejos sin los altos costos de ingeniería asociados a circuitos de aplicación específica.

Bloque de Aneglo Embebido

Aneglo Embebido

Un FPGA es un dispositivo con diseño independiente y cada proveedor fabrica dispositivos con una arquitectura propia. Sin embargo, la arquitectura incluye un número de bloques lógicos programables conectados a una matriz programable a base de switches. Para

18

-. . .. - . - I'?"' , .iM% *,


configurar un dispositivo para una operación funcional en particular, hay que programar estas matrices para rutear las señales entre los bloques lógicos individuales. La figura 2.1 presenta el esquema de un FPGA.

2.2.2. ASIC

Como su nombre lo dice (Application Specific Integrated Circuit), estos dispositivos son circuitos integrados cuya función esta dedicada Únicamente al proyecto o aplicación para los cuales fueron diseñados. La diferencia entre un ASIC y un circuito convencional (como los TTL) es que su función puede ser diseñada para una gran variedad de aplicaciones [SI.' Desde la aparición comercial de los transistores, los ingenieros han querido incluir una funcionalidad cada vez mayor a sus productos. La disponibilidad de elementos cada vez más complejos y técnicas nuevas han colaborado a la densidad funcional que existe en nuestros días. Los ASIC's permiten a los diseñadores ir un paso más allá y combinar las funciones requeridas en un encapsulado, ocupando el mismo espacio que se ocuparía en la tablilla de circuito con un sólo CI. Con los recientes avances de la tecnología es posible incluir no sólo lógica convencional, si no que también complejos microprocesadores en un ASIC. Los ASIC's están diseñados a partir de dos arquitecturas:

- Células estándar. Esta propuesta consiste en colocar bloques funcionales en un chip y hacer las conexiones pertinentes entre ellos de la misma forma que se haría en un proto- board. Laventajaquese t i eneesqueno hay limitaciones encuanto a l espacio para añadir elementos.

- Arreglo de compuertas. Como su nombre lo indica, el arreglo de compuertas consiste en un conjunto de transistores colocados de tal forma que, mediante la posición de una o más capas de interconexiones de metal, los transistores pueden ser configurados como compuertas lógicas individuales, a partir de las cuales funciones más complejas pueden ser construidas.

Las ventajas que se pueden obtener de dispositivos de este tipo son:

- Reducir el tamaño del producto final. Al tener un circuito integrado en vez de varios, obviamente el tamaño final se reduce mucho.

- Menor consumo de potencia. AI tener conectado a la alimentación un solo CI el consumo de potencia se ve reducido considerablemente.

19


- Rapidez de las señales internas. Cuando se tienen diseños con circuitos convencionales, muchas veces la velocidad que pueda ofrecer uno de esos circuitos se ve limitada por la conexión a otro circuito no necesariamente más lento. Este problema no existe dentro de los ASIC’s ya que las señales están conectadas dentro del mismo integrado.

- Incremento de la dificultad para copiar un diseño. Cuando se construye un sistema de hardware, se desea que éste no sea imitado. Antes de los ASIC’s era posible aplicar ingeniería inversa a los diseños, lo cual no se puede hacer al trabajar con un ASIC.

- Verificación formal de hardware. Este es un término que ha cobrado mucha importancia dentro del diseño de circuitos electrónicos, y se refiere a la facilidad que ofrece un diseño para ser probado. Con un ASIC esto se vuelve algo muy fácil ya que las pruebas se pueden hacer mediante la simulación.

Aunque estas ventajas parecen muy atractivas, los ASIC’s también presentan algunas desventajas mostradas a continuación.

- Requerimientos mayores en etapas tempranas del diseño. - Pérdidas del control del desarrollo mientras se manufactura el dispositivo. - Daño mayor cuando ocurre un error.

La figura 2.2 muestra el esquema a bloques de un ASIC.

Fig. 2.2. Diagrama a bloques de un ASIC [I I].

2.2.3. FPGA vs ASIC

La selección entre un ASIC y un FPGA depende de muchos factores. Si la selección se hace de acuerdo a los recursos y capacidades electrónicas que ambos ofrecen no se

20

% < . , ' I ,


encontrará una razón de peso para inclinarse por alguno, por lo que es necesario hacer otro tipo de análisis. El costo de fabricación total de un ASIC se encuentra entre .los US $20,000 y los US $100,000, Sin embargo, después de esta inversión inicial, el costo de producción de un dispositivo es de alrededor de US $10. Este costo es mucho menor que el costo de un dispositivo FPGA, típicamente de US $150 a US $250 por unidad [io]. La ventaja de los FPGA's es que son rápidos y fáciles de programar, además de que generan un layout a nivel de tarjeta el diseño en general es completado. Este procedimiento le permite al usuario llevar a cabo pruebas de integración de hardware y software. Si el sistema de pruebas falla, s e puede modificar el diseño y programar el dispositivo otra vez a un costo relativamente bajo. Por estas razones, los diseñadores comúnmente se inclinan sobre los FPGA's para desarrollar sistemas de pruebas y para aplicaciones que requieran producciones pequeñas. En algunos casos estos diseños son trasladados a ASIC's para producciones a mayor escala. Para esto hay que considerar las diferencias de diseño que pudiera haber entre ambos, por ejemplo, los tiempos de espera pueden variar por la diferencia de velocidad entre uno y otro. Para poder hacer la selección entre alguno de los dispositivos comentados para este trabajo, es necesario trasladar los factores de comparación que existen entre ellos a un trabajo de tesis; aunque es necesario mencionar que esta decisión no afecta los resultados finales de la misma, ya que la programación en HDL se mantiene igual. Para finalizar este punto, hay que tomar en cuenta que el empleo de un ASIC en un sistema digital está enfocado para aplicaciones en serie, cosa que no se cumple en un trabajo de tesis. Esta característica esta característica es la que propicia el seleccionar al FPGA como el dispositivo sobre el cual se realizará el diseño de la herramienta de encripción.

2.2.4. Lenguajes Descriptores de Hardware

En años recientes los diseñadores han adoptado metodologías de diseño descendentes [6], la cuales los han llevado del diseño a nivel transistor o lógico a programas abstractos. La introducción de HDL's estándares en la industria y la existencia de herramientas de síntesis comercialmente disponibles han ayudado a establecer esta revolucionaria metodología de diseño. Las ventajas de esta metodología están causando claramente un cambio en los métodos de diseño de CI. Las ventajas del diseño basado en HDL incluyen:

- Aumento de la productividad, ciclos de desarrollo más cortos, más características de producto y una reducción del tiempo de liberación al mercado.

"""I CENIDET (ENTRO DE INFORMACION 21


- La posibilidad de reutilización del diseño, lo cual resulta en un incremento en la flexibilidad para futuras modificaciones al diseño.

- Una rápida expansión de arquitecturas alternativas. - Una rápida expansión de librerías de tecnología alternativas. - Existe realimentación en el proceso de desarrollo. - Simulaciones más rápidas y en etapas más tempranas. - Diseños transferibles y portables.

Para poder programar un FPGA existen varias alternativas (también conocidas como niveles de abstracción) [7], entre los cuales destacan los diagramas de estado, diagramas esquemáticos y lenguajes HDL, siendo esta última la más usada hoy en día. Un HDL es un lenguaje de programación de software usado para modelar la operación específica de una pieza de hardware. Hay dos aspectos de la descripción del hardware facilitados por un HDL: modelado abstracto y modelado estructurado de hardware. Un HDL es declarativo para facilitar la descripción abstracta del comportamiento de hardware para la especificación. Los aspectos estructurales y de diseño intentan no perjudicar este comportamiento. El diseñador puede modelar la estructura de hardware en HDL independientemente del comportamiento del diseño. Además, el diseñador puede modelar y representar el comportamiento del hardware a varios niveles de abstracción durante el diseño. Modelos de nivel más alto describen la operación de hardware abstractamente y los modelos de un nivel más bajo incluyen más detalle.

En términos generales, se pueden mencionar dos HDLs que acaparan el mercado, VHDL y Verilog, y se pueden modelar estructuras de hardware igualmente efectivas en ambos. Por lo que la decisión de cual de ellos emplear se hace simplemente en base a la disponibilidad del software. Acorde a esto, quedó descartado el empleo de Verilog por no contar con las herramientas computacionales adecuadas para programar sobre esta plataforma, por lo tanto el software que se empleó durante todo el desarrollo de la tesis es el ISE 5 . 2 de Xilinx. Este paquete le permite al usuario diseñar sistemas digitales complejos programados en VHDL mediante el empleo de herramientas tales como archivos de banco de pmebas, diagramas de estado, etc.

2.3. SOLUCIÓN ADOPTADA

En el punto anterior se estableció que el esquema de encripción se implementará en un FPGA programado en VVHDL. La creación de sistemas en VHDL ha cobrado gran

i

22

Análisis del algoriiiiio de Hsu y Wu Capitulo 2

~

relevancia, por lo que se ha comenzado a seguir una metodología de desarrollo estandarizada [ 11. Esta metodología la podemos englobar en tres etapas:

- Síntesis - Implementación de diseño - Generación de archivos de programa y programación del dispositivo

Síntesis Si se busca una descripción concisa de lo que se realiza en esta etapa, ésta sería que es la etapa encargada de realizar la compilación del código HDL a nivel de compuertas. Un FPGA está conformado por celdas lógicas que son configuradas para representar, en cuanto a funcionamiento, un conjunto de compuertas lógicas básicas. Es precisamente en la etapa de la síntesis en donde a partir del código programado por el usuario, se genera la configuración de esas celdas lógicas. Véase figura 2.3.

Fig. 2.3. Celda lógica de un FPGA 1.1

Antes de poder llegar a la etapa de la compilación de programas, es necesario haber realizado un trabajo previo de diseño en el que se analiza el problema a resolver y se escribe el código necesario para resolverlo mediante declaraciones en HDL. En este punto es en donde se puede apreciar una de las ventajas que hoy en día presenta la programación en VHDL, y esa es que es posible realizar simulaciones incluso antes de compilar los programas. Para esto se cuenta con archivos de bancos de pruebas mediante los cuales el usuario indica los valores de entrada que toman cada una de las variables del sistema que se está desarrollando. Como parte final de esta etapa, es posible volver a efectuar simulaciones al diseño una vez obtenido el código a nivel compuerta.

23

Capitulo 2 Analisis del algoritmo de Hsu y Wu

Implementación del diseño Esta fase tiene como finalidad adecuar el sistema a un FPGA específico. Actualmente existen muchos fabricantes de FPGAs, y éstos a su vez cuentan con un gran número de familias disponibles, cada una de ellas con características especiales. Por este motivo, es necesario estructurar el programa diseñado para que se adapte a las condiciones físicas que presenta cada uno de los dispositivos: número de puertos de E/S, memoria disponible, cantidad de celdas lógicas, etc. Esta estructuración es realizada mediante el proceso conocido como implementación del diseño, y varia de acuerdo al software empleado para desarrollar el sistema digital.

Generación de archivos de programa y programación del dispositivo La última fase del proceso consiste en generar un archivo en código binario para que pueda ser bajado al FPGA, obteniendo así el producto terminado. Este archivo es obtenido a partir del diseño a nivel compuertas

En la figura 2.4 se representan cada una de las etapas arriba mencionadas.

24


2.4.SUMARIO

Dentro de este capítulo se establece cual son el objetivo y los alcances que se van a obtener al finalizar el trabajo. Como complemento a esto se define cual es el algoritmo de encripción que se implementara con base en sus características y ventajas, este algoritmo es el propuesto por Hsu y Wu [3]. Finalmente se presenta un análisis comparativo de las posibles herramientas para la implementación de una aplicación como ésta. En este comparativo se consideran factores como disponibilidad de las herramientas, recursos económicos, caractensticas electrónicas, etc. Las herramientas que se compararon fueron FPGA vs. ASIC (como dispositivo), y Verilog vs. VHDL (como lenguajes de programación de los dispositivos). Como resultado de este comparativo se seleccionaron el FPGA y VHDL como herramientas de desarrollo.

2.5. REFERENCIAS

Armstrong, James; Gray, Gail: “VHDL Desing Representation and Syntehesis”, 2”d Edition, Prentice Hall, N.J. 2000.

Hernandez, Hector: “Esquema de Encripción Autentificado Empleando Verificación Compartida”, Tesis de Maestría, CENIDET, Cuemavaca, 2001.

HSU C.L, WU T.C: “Authenticated encryption scheme with (t,n) shared verification”, IEE Proceedings, 117-121 January 1998.

Lidl, Rudolf; Pilz, Günter: “Applied Abstract Algebra”, 2”d Edition, Springer, N.Y. 1998.

Phanthavong, Douang: “Re-timing for Performance improvement in FPGA Designs”, Mentor Graphics, April 2003.

Sjoholm, Stefan; Lindh, Lennart: “VHDL for Designers”, Prentice Hall Europe, 1997.

Yalamanchili, Sudhakar: “introductory VHDL from Simulation to Synthesis”, Prentice Hall. N.J. 2001.

DELTA Microelectronics [en línea] [Fecha de consulta: Noviembre 20021, disponible en:

2s

http://www.asic.dW


191 Field Programmable Gate Arrays [en línea] [Fecha de consulta: Noviembre 20021, disponible en:

[lo] EETIMES [en línea] [Fecha de consulta: Diciembre 20021, disponible en:

Ill] MicroUnity: Software Defined Broadband [en línea] [Fecha de consulta: Enero 20031, disponible en:

26

http://www.ece.msstate.edu/-reese/EE4743/impltech/fpga.htmhttp://www.eetimes.corn/story/OEG200112http:/lwww

Capítulo 3

Mensaje Mensaje + ~ ~ ~ i ~ ~ i ó ~ + Onginal Cikado -b + f

Diseño del Criptosistema

Mensaje OfigiIlal Decripción -w

~

Para poder desarrollar el sistema criptográfico que se ha elegido, es necesario realizar un diseño modular. Con un diseño de este tipo lo que se consigue es tener tres secciones independientes de la herramienta de codificación. Esras secciones o niódulos se encargan de realizar los cuatro escenarios de los que consta el esquema de Hsu y Wu. además de que se encargan de los procesos de comunicación necesarios para el 'iniercamhio de información.

4 -:

3.1. DISENO GENERAL DEL CRIPTOSISTEMA

! i i canal i ! ........................ Inseguro

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Clave b

4 -..-: 'r- canal i Seguro

u Fig. 3. I . Típica aplicación de encripción.

AI día de hoy, existe una gran cantidad de aplicaciones en las que se transmiten datos de manera digital para las cuales se puede diseñar una herramienta de encripción de datos (comunicación celular, comunicación de dispositivos móviles, televisión por cable, redes de computadora, cajeros electrónicos, comercio electrónico, etc.). A pesar de esta diversidad de aplicaciones, la manera más común de transmitir mensajes electrónicos es mediante el uso de las computadoras personales. Dentro del ámbito de las comunicaciones basadas en equipos de cómputo, también se pueden encontrar diversas áreas de aplicación entre las

27

Diseño del criptosistema Capitulo 3

cuales se pueden mencionar Internet o redes de área local, entre otras. Es por esto que como inicio de la etapa del diseño es necesario seleccionar un área de aplicación específica para la herramienta de hardware propuesta.

Algo que debe de tener la aplicación para la cual se realizará el diseño, es que la herramienta resultante genere una solución práctica al problema de inseguridad en las comunicaciones digitales. Por lo tanto, se eligió para este trabajo la aplicación con el mercado más amplio en la actualidad: comunicación entre computadoras personales. Como se mencionó anteriormente, existen varias posibilidades de aplicación en esta área; el inconveniente es que en este trabajo se implementará un algoritmo de encripción nuevo, además de que se llevará a cabo sobre una plataforma muy poco usada en este centro. Por lo tanto, el realizar una fase de acoplamiento de la herramienta criptográfica con alguna de las posibles aplicaciones reduciría el tiempo destinado en la etapa de diseño, a la comprensión del esquema de Hsu y Wu, y a la etapa de desarrollo en VHDL. Esta es la razón por la que el diseño del sistema de encripción de datos se hace enfocado a un sistema de comunicación entre computadoras no estandarizado, es decir, un sistema que no cuente con un protocolo de comunicaciones propio al cual la herramienta se tenga que acoplar. Entonces, el diseño del criptosistema comienza con la propuesta de una aplicación sobre la cual se delineará el sistema.

3.1.1. Esquema de Comunicación

La criptografía en general, tiene como propósito brindarle a los usuarios la posibilidad de enviar y recibir datos de manera segura y confiable dentro de un entorno determinado; todo esto mediante el empleo de los conceptos analizados con anterioridad (firma digital, llaves, etc.). En el caso especifico de la verificación compartida, lo que se pretende es que el firmante (transmisor) tenga la opción de decidir concretamente a que verificadores (receptores), dentro del conjunto de participantes, se les va a compartir la información enviada (21. En otras palabras, el mensaje encriptado se envía a t de n verificadores (esquema (t, n)), y para la recuperación del mensaje original es necesaria la participación de cada uno de los t verificadores involucrados, siendo prácticamente imposible la recuperación del mensaje para cualquier otra verificador no incluido. Véase figura 3.2.

Analizando lo anterior, podemos definir el proceso de transmisión de datos con verificación compartida en 5 pasos:

- Encnpción - Envío

28

Capítulo 3 Diseño del criptosistenia

- Recepción - Intercambio de llaves - Recuperación del mensaje

I

Encripción

Recepción

Intercambio

. %, ,.

del mensaje

., .

Fig. 3.2. Proceso de transmisión.

Estos c inco p asos definen e 1 formato que tendrá e 1 s istema d e c omunicación. La s imple transmisión de un mensaje supone la conexión entre el elemento que envía y los receptores, en un sólo sentido. Pero en realidad, en un sistema de comunicaciones completo el receptor continuamente se convierte en el transmisor y viceversa; es decir, el flujo de los datos se invierte continuamente, por lo que la conexión entre los elementos debe ser bidireccional. Otro aspecto que se puede definir basado en el proceso de transmisión es la topología a utilizar. Los mensajes enviados pueden ir dirigidos a cualquier elemento dentro del conjunto de receptores, así que la topología debe de proporcionar la capacidad de interconexión entre todos los elementos de la manera más sencilla posible. Entre las topologías que se pueden utilizar se encuentran [SI:

Topología de Anillo: Consiste en una sene de repetidores conectados entre sí mediante un Único enlace de transmisión unidireccional que configura un camino cerrado.

Topología en Estrella: Todas las estaciones están conectadas mediante enlaces bidireccionales a una estación o nodo central que controla la red.

29

Capítulo 3 Diseño del criptosistema

Topología en Bus: Esta topología busca que las estaciones se conecten a un Único medio bidireccional lineal o “bus” con puntos de terminación bien definidos.

Caracter ís t icas

Ventajas

Desventaias

Anillo Estrel la Bus - Flujo unidireccional. -Flujo bidireccional. - Flujo bidireccional. - Cada estación se conecta

- Por cada nodo pasan todos

- N o enrutamiento. -Simple para interconectar. -Poco medio fisico. - Poca cantidad de cable. - Fácil de extender. -Longitud extendible. - Fácil de instalar. - Altamente susceptible a - Reside mucha importancia - Half-duplex.

- Todas las estaciones se

- Servicio centralizado.

- Una sola linea de - Transmisión por ráfagas.

a otras 2. conectan a un nodo central. comunicación.

los mensajes.

- Funciona aún con la falla de - Rapidez con tráfico pesado.

un nodo.

fallas. en un nodo. - Necesita de todos los nodos - Mayor medio fisico (cable). - Los mensajes llegan a todos

funcionando. I - Software complejo en cada los ncdos. I - Dificil aislar nodo con falla. -

Tabla. 3.1. Comparacibn enire topologias

La determinación de cual sena la topología más conveniente para esta aplicación se basó en el análisis de las desventajas mostradas en la taba1 3.1. Las desventajas que presenta la topología de bus en realidad no interfieren para nada en el funcionamiento del criptosistema que se desarrolló. La primera desventaja presentada es que sólo se puede realizar una comunicación half-duplex, lo cual es exactamente lo que se realiza en el esquema de Hsu y Wu. La segunda desventaja indica que los mensajes llegan a todos los nodos, aspecto que pierde completa importancia debido a que se trata de un cnptosistema de verificación compartida. Por último, se tiene la desventaja de que no se puede aislar de manera sencilla un nodo cuando falla, pero en realidad un nodo con falla no afecta para nada el funcionamiento del esquema de encripción. Analizando las desventajas de cada topología (además de puntos como la complejidad de software requerido en cada nodo y la facilidad de instalación), se tomó la decisión de elegir la topología de bus para interconectar los nodos participantes en el sistema de comunicaciones de la aplicación que aquí se desarrolló.

Teniendo hecha la selección de la topología, resta ahora definir el número de terminales que la conformarán. Para definir cuantas terminales se tomarán en cuenta, es necesario analizar el ambiente dentro del cual una aplicación como ésta podría estar funcionando. Por io general, cuando se trata de compartir archivos codificados el número de terminales no es demasiado grande, de tal forma que para propósitos de esta tesis, un sistema de comunicación de cinco terminales resultará adecuado. La topología seleccionada se presenta en la figura 3.3.

30


Terminal 6 Terminal 4 Terminal 2

Fig. 3.3. Topología de la aplicación 191

3.1.2. Esquema de Codificación

Para diseñar la herramienta de codificación, se tiene que analizar el funcionamiento general del esquema de verificación compartida aplicado al sistema de comunicación propuesto, el cual se encuentra representado en la figura 3.4.

-.-+ I I I ', .

1 Fig. 3.4. Esquema de verificación compartida 1154).

Una consideración importante es que las cinco terminales sean capaces de cifrar y descifrar mensajes, por lo que cada una de ellas debe de tener instalada la herramienta completa, es decir, los cuatro escenarios que conforman el algoritmo de Hsu Wu:

- Inicio

31


- Registro - Encripción de firma - Recuperación

Dentro de estos cuatro escenarios se realiza una serie de procedimientos matemáticos que proporcionan un cierto grado de dificultad a la implementación del algoritmo, motivo por el cual resulta conveniente dividir la aplicación criptográfica en bloques o módulos independientes. El hecho de poder tener bloques independientes facilita su diseño y su programación. Los módulos resultantes de esta fragmentación (figura 3.5) son:

a) Unidad Central. En este criptosistema al módulo que se encarga de administrar la ejecución de las funciones matemáticas, y en general, de cada una de las fases que conforman el algoritmo de encripción se le denomina Unidad Central. Este módulo ejecuta cada uno de los escenarios de los que consta el algoritmo de encripción de Hsu y Wu

Fig. 3.5. Aplicación dividida en bloques.

b) Módulo Aritmético. Todos los sistemas de encripción de datos sustentan su funcionamiento en operaciones aritméticas, las cuáles varían dependiendo de la complejidad del cifrado de los datos. En el caso concreto del criptosistema de Hsu y Wu, las siguientes operaciones básicas son indispensables:

- Suma - Resta - Multiplicación - División - Módulo de dos números

32


Estas operaciones son consideradas dentro de este diseño como básicas, ya que no requieren de ninguna otra para poder completar su algoritmo. En adición a éstas dentro del algoritmo se requiere de elevar un número a una potencia, esta función es considerada compuesta ya que utiliza las cinco básicas para poder entregar un resultado. El módulo aritmético de realiza ambos tipos de operaciones dentro del algoritmo, las básicas y las compuestas.

c) Módulo de Comunicaciones. Aunque la idea de seccionar el criptosistema en módulos se debe a la cantidad de operaciones matemáticas, también existe la necesidad de crear un módulo que se encargue de las comunicaciones dentro de la herramienta de encnpción. El tipo de comunicación a la cual se hace referencia es entre la terminal y la tarjeta de hardware del sistema de codificación. En u n s istema d e c ifrado e lectrónico, 1 os mensajes a c odificar s on p rovenientes d e una computadora personal (documentos, imágenes, archivos de texto, etc.). Por lo que se requiere que el criptosistema sea capaz de recibir archivos electrónicos provenientes de una PC, codificarlos, transmitirlos y regresarlos a su formato original dentro de la computadora destino. Un proceso fundamental dentro de estas funciones es el intercambio de información entre la tarjeta y la PC. Por tal motivo, se requiere'de un módulo independiente que se encargue de esta labor.

3.1.3. Simulación del Algoritmo de Encripción

En un ambiente real es necesario emplear números primos grandes con la finalidad de alcanzar dos propósitos: a) Aumentar la segundad del cnptosistema; entre mayor sean los números generadores de

claves, más difícil será romper el sistema de encnpción. b) Ampliar el rango de posibles mensajes a enviar, ya que como se comentó en el capítulo

dos, el tamaño en bits del mensaje está delimitado por los números primos de inicialización.

Una de las formas d e , conocer el funcionamiento real del cnptosistema (empleando cantidades grandes) es mediante una simulación de su funcionamiento, por lo que para poder llevar acabo una representación de este tipo del algoritmo se seleccionó MATLAB como el sowftware empleado para programar el algoritmo de encnpción y simularlo. Se empleó MATLAB para esta labor ya que este software esta dedicado al desarrollo de aplicaciones matemáticas, lo cual encaja perfectamente con la definición de un

33


~

criptosistema. De la simulación realizada, se obtuvo información que no está descrita en la literatura concerniente a este esquema y que es determinante para la etapa de diseño ya que, como se verá a continuación, es necesario definir ciertos puntos dentro del algoritmo para asegurar lo obtención del mensaje original en cada decripción.

Selección d e p

Debido a la aplicación de la operación matemática mod durante la recuperación de los mensajes, el tamaño de éstos queda determinado por los números primos iniciales, específicamente p . Esta relación entre la recuperación de mensajes y p indica que

M < P

Entonces, tomando en cuenta que los archivos electrónicos están organizados en bytes, el máximo mensaje que se podría intentar transmitir es 255, por lo cual se debe de cumplir la siguiente relación

p > 255

El primer número primo que cumple con esta condición es el 257, desafortunadamente el empleo de esta cantidad genera un desbordamiento en los registros de almacenamiento de MATLAB al momento de simular el esquema de Hsu y Wu, debido a las operaciones que se realizan en este esquema (funciones exponenciales). Lo que se busca entonces, es poder transmitir mensajes más pequeños sin perder información de los archivos. Un método para lograr esto es dividir los bytes de los archivos en dos, parte alta y parte baja (similar a lo realizado en algunos microprocesadores), con lo que el 17 es el valor mínimo de p . Por su parte, el máximo valor que puede tomar p queda nuevamente definido por las características de la herramienta de simulación en software. Las pruebas hechas dieron como resultado que si se emplean números mayores a 31, la recuperación de los mensajes se efectúa de forma incorrecta. De tal modo, la relación que se sigue para la elección de p es

17 s p 5 31

La solución para poder encriptar mensajes de 8 bits es el empleo de algoritmos matemáticos dedicados al manejo de cifras numéricas grandes. Esta solución resulta en una gran cantidad de procesos y algoritmos que requerirían un tema de tesis aparte para su entendimiento y aplicación. Es por este motivo que se limita el número p en el esquema de codificación.

..

34


Selección de las variables restantes

A pesar de que en el esquema de Hsu y Wu están definidas las relaciones para determinar cada una de las variables, estás no se cumplen en todos los casos. Un ejemplo de ello es la variable Xc, el algoritmo de encripción especifica que esta variable debe de cumplir con

x, E z;

Pero en un caso práctico, hay valores que caen dentro del intervalo especificado para esta variable y que producen un resultado erróneo en el proceso criptográfico. Es por esta razón que los valores que pueden tomar cada una de las variables se vuelven dependientes de la selección d e p y 9.

3.2. DESCRIPCIÓN DEL DISENO

En la etapa de diseño general, la aplicación final quedó dividida en tres módulos: aritmético, de comunicación y unidad central. Esta etapa retoma esa división por lo que la descripción del diseño también se divide en tres secciones:

- Módulo Antmético - Módulo de comunicaciones - Unidad Central

3.2.1. Módulo Aritmético

A pesar de todas las ventajas que proporciona la programación en VHDL, en el caso concreto de este trabajo presenta un reto: no cuenta con funciones matemáticas predefinidas, s 610 proporciona c iertas operaciones muy e lementales a n ¡vel d e b its. E sto ocasiona que el desarrollo del módulo aritmético abarque la implementación de las operaciones básicas y compuestas que requiere el algoritmo de encripción, así como su aplicación dentro de cada uno de los escenarios. El primer paso para poder lograrlo es definir el formato numérico con el que se llevarán a cabo las operaciones matemáticas y se almacenarán los datos.

3.2.1.1. Formato Numérico

Debido a que los resultados obtenidos durante la simulación del esquema de Hsu y Wu en MATLAB se pueden considerar satisfactorios, lo más apropiado es utilizar en la

35

Capitulo 3 Diseño del criptosistema

herramienta de encnpción un formato similar al de MATLAB. Este software matemático utiliza un formato de punto flotante de ocho bytes, 53 bits para la mantisa y 11 para el exponente de dos (entre 15 y 16 cifras decimales equivalentes) [4]. Para la herramienta cnptográfica se buscó un' formato numérico parecido al de MATLAB pero que fuera menos complicado de implementar. Es por esta razón que se hace una pequeña modificación al formato empleado en las simulaciones, quedando entonces un formato de ocho bytes pero de punto fijo. Concretamente, se utiliza el formato de punto fijo con complemento a dos.

La representación en complemento dos 131 es una forma eficiente de representar números con signo en microprocesadores de punto fijo. La propiedad fundamental de este formato es que permite representar números negativos, para lo cual se utiliza el bit más significativo de la palabra binana que se está manejando. Esto lleva a que en un formato de palabra de n bits, la capacidad de representación sea de hasta 2"-' para números positivos y 2 '-I- 1 para negativos, El bit de signo será siempre el más significativo. Este formato se muestra en la figura 3.6.

Fig. 3.6. Esquema numérico para 2n bits

Con esta forma d e representación los números p ositivos tendrán e 1 b it más significativo igual a O, mientras que si se trata de un número negativo este bit será 1. La manera de escribir como se encuentra representado un número binario es mediante el formato Qm.n. En esta representación se utilizan m bits para indicar en complemento 2 la parte entera de un número y n bits para indicar en complemento 2 la parte fraccionaria. Para esto son necesarios m + n + 1 bits para almacenar un número en formato Qm.n, también conocido como formato Q,,,+"+l. Entonces, si se ha definido que los datos numéricos sean de 64 bits de punto fijo, se puede decir que la herramienta criptográfica empleará un formato 4 3 2 . 3 1 ( 4 6 4 ) (figura 3.7).

A partir de este punto comienza la etapa de implementación de las operaciones matemáticas, tanto básicas como compuestas:

36

. ., -

Capitulo 3 Diseño del criptosistema

- Suma - Resta - Multiplicación - División - Módulo de dos números - Potencia

Para contar con una implementación eficiente, se necesitan seleccionar cuidadosamente los algoritmos para cada una de ellas. En este caso, lo que se pretende es utilizar algoritmos que sean útiles para calcular más de una operación, así que las operaciones quedan agrupadas en los siguientes algoritmos:

- Suma con signo - Multiplicación - División (cocientehesiduo) - Potencia

3.2.1.2. Suma con signo

Para la ejecución de una suma bajo el formato establecido no se necesita hacer ningún ajuste del resultado, es decir, el resultado está formado por la misma cantidad de bits que los sumandos. Dicho de oha forma:

Qm + Qm = Q m (3.1)

Con el problema de compatibilidad de datos resuelto, únicamente es necesario establecer un algoritmo q ue d efina q ue operación realizar b asado e n el b it d e signo d e 1 os s umandos, adición o sustracción.

La obtención del resultado de esta operación prácticamente se basa en la toma de dos decisiones durante el algoritmo. Una de esas decisiones consiste en saber si los signos de los sumandos son iguales, esto con el fin de saber si lo que se debe de realizar es una adición o sustracción. La otra es identificar cual de los dos datos de entrada es mayor, para así saber cual de los dos datos se va a sustraer del otro en caso de que la operación se trate de una resta. Los procedimientos para realizar concretamente la suma o la resta a nivel de bits no requieren de un análisis detallado, ya que ésas son operaciones que VHDL ya contiene implementadas. La figura 3.8 presenta el diagrama de flujo de la operación de suma.

37

Diseño del criptosistema Capitulo 3

I SF&W I Fig. 3.8. Diagrama dejlujo de la suma con

signo.

3.2.1.3. Multiplicación

A diferencia de la suma, la multiplicación en formato Qm presenta una inconsistencia (sobreflujo) de formato entre los datos de entrada y el resultado:

Q m ‘ Qn = Q m + n (3.2)

Este sobreflujo de bits implica que antes de establecer un algoritmo general para la multiplicación, se tiene que definir un método que permita ajustar a nivel de bits el formato del resultado [l]. El procedimiento de ajuste consiste en eliminar los bits excedentes del resultado con respecto a la cantidad de bits definida por el formato de los datos que se desean multiplicar, con referencia en el punto decimal. Con un formato .Q32,3,, el punto decimal se encuentra en l

cenidet · concede la autorización para que proceda con la impresión de su tesis. atentamente...

Documents