Descarga la aplicación para disfrutar aún más
Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!
Implementação de Encriptação AES em FPGA
Todo para Aprender
Compartir
Vista previa del material en texto
INSTITUTO TECNOLÓGICO Y DE ESTUDIOS SUPERIORES DE MONTERREY
IMPLEMENTACIÓN DEL ESTÁNDAR DE ENCRIPCIÓN
A V ANZADO "AES" USANDO CIRCUITOS LÓGICOS
PROGRAMABLES DE TIPO FPGA PARA SER UTILIZADO EN
LA ENCRIPCIÓN DE ARCHIVOS DE COMPUTADORA
TESIS QUE PARA OPTAR EL GRADO DE
MAESTRO EN CIENCIAS COMPUTACIONALES
PRESENTA
ALBERTO V ARGUEZ MOO
Asesor: Dr. ROBERTO GÓMEZ CÁRDENAS
Co-asesor: Dr. ANDRÉS DA VID GARCÍA GARCÍA
Comité de tesis: Dr. LUIS FERNANDO GONZÁLEZ PÉREZ
Dr. LUIS ÁNGEL TREJO RODRÍGUEZ
Jurado: Dr. LUIS ÁNGEL TREJO RODRÍGUEZ Presidente
Dr. ANDRÉS DA VID GARCÍA GARCÍA Secretario
Dr. ROBERTO GÓMEZ CÁRDENAS Vocal
Dr. LUIS FERNANDO GONZÁLEZ PÉREZ Vocal
Atizapán de Zaragoza, Edo. Méx., diciembre del 2003.
4
RESUMEN
Mantener la confidencialidad de la información contenida en una computadora es para muchos
una gran necesidad. Para cubrir esta necesidad, existen en el mercado una amplia variedad de
programas de computo que prometen por medio de contraseñas, codificación o encripción
mantener esta confidencialidad, el inconveniente de estos programas radica en que poseen poca
seguridad fisica, especialmente con respecto al almacenamiento de la llave de encripción, además
de la excesiva carga de procesamiento que delegan al microprocesador para realizar la tarea de
protección.
El objetivo de este trabajo fue la implementación de un circuito electrónico para la encripción de
archivos contenidos en una computadora. Específicamente se implemento el Algoritmo de
Encripción Avanzado en un dispositivo lógico programable de alta densidad de tipo FPGA,
adoptando las consideraciones necesarias para que este dispositivo pudiera comunicarse con la
computadora por medio del bus PCI. Se pretende, con esta implementación, proveer una mayor
seguridad a la llave de encripción y de evitar la sobrecarga de trabajo al microprocesador de una
computadora.
Durante el desarrollo de este trabajo se hizo uso de un lenguaje de descripción material para la
descripción funcional del circuito y lenguajes de programación para elaborar la interfaz de
usuario y efectuar pruebas con el algoritmo. Por consiguiente, se emplearon herramientas de
diseño asistido por computadora, como son simuladores y compiladores.
Los resultados obtenidos fueron satisfactorios, ya que la especificación resultante y optimizada
posee características semejantes de productos comerciales.
5
CONTENIDO
AGRADECIMIENTOS ................................................................................................................... 3
RESUMEN ...................................................................................................................................... 4
CONTENIDO .................................................................................................................................. 5
LISTADO DE FIGURAS ................................................................................................................ 8
LISTADO DE TABLAS ............................................................................................................... 11
INTRODUCCIÓN ......................................................................................................................... 13
l. CAPITULO l: EL ALGORITMO DE ENCRIPCION A V ANZADO (AES) ........................ 15
l. l. INTRODUCCIÓN A LA ENCRIPCIÓN ......................................................................... 15
1.1.l. ALGORITMOS SIMÉTRICOS .................................................................................. 16
1.1.2. ALGORITMOS ASIMÉTRICOS ............................................................................... 17
1.2. SELECCIÓN DEL NUEVO ESTÁNDAR DE ENCRIPCIÓN AVANZAD0 ................ 18
1.2.l. PROCESO DE SELECCIÓN ...................................................................................... 19
1.2.2. LOS FINALISTAS ...................................................................................................... 20
1.3. NOTACIÓN Y CONVENCIONES DE AES ................................................................... 21
1.3.l. BITS Y BYTES ........................................................................................................... 21
1.3.2. PALABRA .................................................................................................................. 22
1.3.3. EL ESTADO ............................................................................................................... 22
1.4. ESPECIFICACIÓN ........................................................................................................... 23
1.4.1. LISTA DE LLAVES ................................................................................................... 24
1.4.2. ENCRIPCIÓN ............................................................................................................. 25
1.4.2. l. Transformación SubBytes( ) ................................................................................. 26
1.4.2.2. Transformación ShifRows( ) ................................................................................ 27
1.4.2.3. Transformación MixColumns( ) ........................................................................... 27
1.4.2.4. Transformación AddRoundKey( ) ........................................................................ 28
1.4.3. DECRIPCION ............................................................................................................. 28
1.4.3. l. Transformación InvSubBytes( ) ........................................................................... 29
1.4.3.2. Transformación InvShiftRows( ) .......................................................................... 29
1.4.3.3. Transformación InvMixColumns( ) ..................................................................... 30
1.4.3.4. Inverso de la transformación AddRoundKey( ) ................................................... 30
1.5. IMPLEMENTACIÓN EN HARDWARE .......................................................................... 30
1.5.1. S-BOX ......................................................................................................................... 30
1.5.1. l. Implementación de la S-Box a nivel de registros ................................................. 31
1.5.1.2. Implementación de S-Box en tablas de búsquedas ............................................... 31
1.5.2. ALGORITMO EQUIVALENTE PARA LA DECRIPCIÓN ..................................... 31
6
1.6. CONCLUSIÓN .................................................................................................................. 32
2. CAPITULO 2: DISPOSITIVOS LÓGICOS PROGRAMABLES .......................................... 33
2.1. DISPOSITIVOS LÓGICOS PROGRAMABLES SIMPLES ............................................ 35
2.1.1. ARREGLO LÓGICO PROGRAMABLE ................................................................... 35
2.1.2. ARREGLO GENÉRICO PROGRAMABLE .............................................................. 36
2.2. DISPOSITIVOS LÓGICOS PROGRAMABLES COMPLEJOS ..................................... 36
2.2.1. MATRIZ DE INTERCONEXIONES PROGRAMABLES ........................................ 37
2.2.2. BLOQUE LÓGIC0 ..................................................................................................... 37
2.2.3. MACROCELDAS ....................................................................................................... 37
2.3. ARREGLO DE COMPUERTAS PROGRAMABLE EN CAMPO ................................. 38
2.3.1. BLOQUES LÓGICOS ................................................................................................ 38
2.3.1.1. Tablas de búsqueda basada en elementos lógicos ................................................ 38
2.3.1.2. Multiplexor ........................................................................................................... 39
2.3.1.3. Celdas simétricas ..................................................................................................40
2.3.2. INTERCONEXIÓN .................................................................................................... 40
2.3 .2.1. Enrutamiento en renglones .................................................................................. 41
2.3.2.2. Enrutamiento por segmentación de canal. ........................................................... 41
2.3.2.3. Enrutamiento jerárquico ....................................................................................... 42
2.3.3. ELEMENTOS DE uo ................................................................................................. 43
2.3.4. OTROS RECURSOS .................................................................................................. 43
2.3.4.1. Bloques de memoria ............................................................................................. 44
2.3.4.2. Sujetador de fase (PLL) ........................................................................................ 44
2.4. SELECCIÓN DE DISPOSITIVO ...................................................................................... 44
2.5. HERRAMIENTAS CAD ................................................................................................... 44
2.6. CONCLUSIONES .............................................................................................................. 45
3. CAPITULO 3: DESCRIPCIÓN A NIVEL DE REGISTRO EN VHDL DEL ALGORITMO
DE ENCRIPCIÓN A V ANZADA (AES) .................................................................................. .47
3.1. DISEÑO EN VHDL .......................................................................................................... 47
3.1.1. VENTAJAS DEL DISEÑO EN VHDL. ..................................................................... 47
3.1.2. PROCESO DE DISEÑO EN VHDL. .......................................................................... 48
3 .1.2.1. Proceso de diseño ................................................................................................. 48
3.1.2.2. Herramienta de diseño .......................................................................................... 48
3.1.3. DESARROLLOS COMERCIALES Y OTROS TRABAJOS SEMEJANTES
REALIZADOS ...................................................................................................... 48
3.2. ESTABLECIMIENTO DE LOS REQUERIMIENTOS ................................................... 49
3.2.1. Interfaz de usuario ....................................................................................................... 50
3.2.2. Bloque de control PCI. ................................................................................................ 50
3.2.3. El bloque de AES ........................................................................................................ 50
3.2.4. Bloque de Memoria ..................................................................................................... 50
3.2.5. Bloque de control. ....................................................................................................... 50
3.3. DESCRIPCIÓN FUNCIONAL DEL BLOQUE AES ....................................................... 50
3.3.1. JERARQUIZACIÓN ................................................................................................... 51
3.3.2. DESARROLL0 ........................................................................................................... 52
3.3.2.1. Elaboración de diagrama de flujo ......................................................................... 53
3.3.2.2. Elaboración de los diagramas de estado ............................................................... 53
3.3.2.3. Descripción en VHDL .......................................................................................... 54
3.3.2.4. Simulación funcional y de tiempo ........................................................................ 54
3.3.2.5. Compilación y registro ......................................................................................... 54
3.3.2.6. Elaboración del símbolo ....................................................................................... 56
7
3.3.2.7. Agregar a Package ................................................................................................ 57
3.4. SIMULACIÓN POST-SÍNTESIS DEL MODELO OBTENID0 ...................................... 58
3.5. CONCLUSIÓN .................................................................................................................. 58
4. CAPITULO 4: VERIFICACIÓN FUNCIONAL Y PRUEBAS ............................................. 60
4.1. OPTIMIZACIÓN ............................................................................................................... 60
4.1. l. OPTIMIZACIÓN DEL ALGORITMO DE LA S-Box ............................................... 60
4.1.2. OPTIMIZACIÓN DE CÓDIGO CON EL EMPLEO DE UNA DPRAM .................. 61
4.1.3. OPTIMIZACIÓN DE CÓDIGO CON EL EMPLEO DE UNA ROM ....................... 62
4.1.4. OPTIMIZACIÓN POR COLOCACIÓN Y RUTEO .................................................. 62
4.2. SIMULACIÓN ................................................................................................................... 63
4.2.l. SIMULACIÓN DE S-Box .......................................................................................... 64
4.2.l. SIMULACIÓN DE AES II ........................................................................................ 64
4.2.2. SIMULACIÓN DE AES-III ....................................................................................... 65
4.2.4. COMPARACIÓN DE LAS DESCRIPCIONES ......................................................... 65
4.3. ANÁLISIS COMPARATIV0 ............................................................................................ 66
4.4. PRUEBAS DE FUNCIONALIDAD .................................................................................. 68
4.4.l. INTERFAZ DE USUARI0 ......................................................................................... 68
4.4. l. l. Funcionalidades de la interfaz de usuario ............................................................. 68
4.4.1.2. Ayuda en línea ...................................................................................................... 69
4.4.1.3. Programa de instalación ....................................................................................... 69
4.4. l.4. Comunicación con la tarjeta ................................................................................. 69
4.4.2. TARJETA DE EXPANSIÓN ...................................................................................... 70
4.5. CONCLUSIONES .............................................................................................................. 70
5. CAPITULO 5. TRABAJOS FUTUROS Y CONCLUSIONES FINALES ............................ 71
5.1. TRABAJOS FUTUROS ..................................................................................................... 71
5.2. CONCLUSIONES FINALES ............................................................................................ 71
BIBLIOGRAFIA ........................................................................................................................... 73
ANEXO A: GLOSARIO .............................................................................................................. 75
ANEXO B: FAMILIAS APEX 20KTM Y FLEX® l OK DE ALTERA® ................................... 79
ANEXO C: JERARQUÍAS DE COMPILACIÓN ....................................................................... 84
ANEXO D: INTERCONEXIÓN DE COMPONENTES ............................................................. 88
ANEXO E: CÓDIGO VHDL DE PAQUETES ........................................................................... 91
ANEXO F: SIMULACIÓN ..........................................................................................................98
ANEXO G: MANUAL DEL USUARIO .................................................................................... l 05
ANEXO H: TARJETA DE EXPANSIÓN PCI. .......................................................................... 129
8
LISTADO DE FIGURAS.
Fig. 1.1 Representación grafica de una Palabra ............................................................................ 22
Fig. 1.2 Arreglos de entrada, estado y salida ................................................................................ 23
Fig. 1.3 Operación de las funciones SubWord( )y RotWord( ) .................................................... 24
Fig. 1.4 Seudo código para la expansión de la llave de cifrado ................................................... 25
Fig. 1.5 Seudo código para la rutina de cifrado ............................................................................ 26
Fig. 1.6 La transformación SubBytes() aplica la S-Box a cada byte del Estado ......................... 26
Fig. l. 7 La transformación ShiftRows( ) rota los últimos tres renglones del Estado ................... 27
Fig. 1.8 MixColumns() opera sobre el Estado columna por columna ......................................... 28
Fig. 1.9 AddRoundKey() aplica un XOR de cada columna en el Estado con una Palabra de la
lista de llaves .................................................................................................................. 28
Fig. 1.1 O Seudo código para la rutina de decripción ..................................................................... 29
Fig. l.11 InvShiftRows( ) rota los tres últimos renglones del estado ............................................ 30
Fig. 1.12 Seudo código del Cifrado ............................................................................................... 32
Fig. l.13 Seudo código para las funciones Round() y FinalRound() del cifrado ........................ 32
Fig. 2.1 Clasificación de los PLDs ............................................................................................... 34
Fig. 2.2 Diagrama funcional del GAL 22V l O .............................................................................. 35
Fig. 2.3 Arquitectura básica de un CPLD ..................................................................................... 36
Fig. 2.4 Macrocelda de un bloque lógico en la familia Delta39K™ de Cipress .......................... 37
Fig. 2.5 Clasificación de arquitecturas de un FPGA .................................................................... 38
Fig. 2.6 LUT de 2 entradas ........................................................................................................... 39
Fig. 2. 7 Elemento lógico de un FPGA de la familia FLEX ™ con un LUT de 4 entradas ........... 39
Fig. 2.8 Modulo Lógico Básico desarrollado por ActefrM ........................................................... 40
Fig. 2.9 Arquitectura de Celdas simétricas desarrollado por AtmelTM········································· 40
Fig. 2.1 O Arquitectura de interconexión en FPGAs de ActelTM .................................................... 41
Fig. 2.11 Diagrama a bloques de enrutamiento de CLBs en la familia Spartan XL ..................... 42
Fig. 2.12 Arquitectura de interconexión jerárquica en la familia Flex l O de Altera® ................... 42
Fig. 2.13 Elemento de VO en la familia Flex l O de Altera® ......................................................... 43
Fig. 3.1 Diagrama a bloques del sistema ...................................................................................... 49
Fig. 3.2 Jerarquía ENC_DEC ....................................................................................................... 51
Fig. 3.3 Jerarquía KEY _SCH ....................................................................................................... 52
Fig. 3.4 Proceso para la elaboración de cada componente ........................................................... 52
Fig. 3.5 Diagrama de flujo de la función addroundkey ................................................................ 53
Fig. 3.6 Diagrama de estados de la función addroundkey ............................................................ 53
Fig. 3.7 Símbolo para la entidad addroundkey ............................................................................. 57
9
Fig. 4.1 Colocación de las entidades dentro de un FPGA EP20K600EBC652-1 X ..................... 63
Fig. 4.2 Grafico comparativo de recursos empleados y frecuencia máxima de operación de las
descripciones .................................................................................................................. 65
Fig. 4.3 Grafico de desempeño de cada descripción .................................................................... 66
Fig. 4.4 Ubicación del submenú en la barra de menús para el acceso a la ayuda en línea ........... 69
Fig. 0.1 Interconexión de componentes para la especificación AES ........................................... 88
Fig. 0.2 Interconexión de componentes para la especificación AES_ll. ..................................... 89
Fig. D.3 Interconexión de componentes para la especificación AES_lll.. ................................... 90
Fig. F.1 Simulación de la entidad AddRoundkey ......................................................................... 98
Fig. F.2 Simulación de la entidad SubBytes ................................................................................. 98
Fig. F.3 Simulación de la entidad ShiftRows ............................................................................... 99
Fig. F.4 Simulación de la entidad MixColumns ........................................................................... 99
Fig. F.5 Simulación del proceso de Encripción para la especificación AES ............................. 100
Fig. F.6 Simulación del proceso de Decripción para la especificación AES ............................. 100
Fig. F.7 Simulación del proceso de KeyExpansion para la especificación AES (1 de 2) .......... 101
Fig. F.8 Simulación del proceso de KeyExpansion para la especificación AES (2 de 2) .......... 101
Fig. F.9 Simulación de la entidad inverso .................................................................................. 102
Fig. F. l O Simulación de la entidad inverso _gf. .......................................................................... 1 oi
Fig. F .11 Simulación del proceso de Encripción para la especificación AES_ Il. ...................... 103
Fig. F.12 Simulación del proceso de Decripción para la especificación AES_II ....................... 103
Fig. F.13 Simulación del proceso de KeyExpansion para la especificación AES_ 11 ( 1 de 2) ... 104
Fig. F.14 Simulación del proceso de KeyExpansion para la especificación AES_II (2 de 2) ... 104
Fig. G. l Pantalla de bienvenida del Asistente para la Instalación de AESPCI .......................... 105
Fig. G.2 Cuadro de dialogo para confirmar la Cancelación de la Instalación ............................ 106
Fig. G.3 Pantalla del Contrato de licencia .................................................................................. 106
Fig. G.4 Selección del tipo de Instalación a efectuar ................................................................. l 07
Fig. G.5 Selección del modo de instalación de cada característica ............................................ 107
Fig. G.6 Menú de los estados de instalación disponibles para cada característica que contiene al
menos una subcaracterística ......................................................................................... 108
Fig. G.7 Ayuda para la Instalación personalizada ...................................................................... 108
Fig. G.8 Progreso de la instalación ............................................................................................. 109
Fig. G.9 Pantalla inicial para el mantenimiento de la Interfaz de Usuario ................................. 110
Fig. G. lO Pantalla para la selección del tipo de mantenimiento ................................................. 111
Fig. G.11 Interfaz de usuario ...................................................................................................... 114
Fig. G.12 Barra de títulos ........................................................................................................... 114
Fig. G .13 Menú de la interfaz de usuario ................................................................................... 114
Fig. G.14 Barra de herramientas ................................................................................................. 115
Fig. G.15 Barra de estado ........................................................................................................... 115
Fig. G.16 Barra de estado mostrando el progreso del proceso general y de archivo ................. 116
Fig. G.17 Area de trabajo ........................................................................................................... 116
Fig. G.18 Cuadro de Dialogo Configuración ............................................................................. 118
Fig. G.19 Carpeta Encripción del Dialogo Configurar ............................................................... 119
Fig. G.20 Carpeta Decripción del Dialogo Configurar .............................................................. 120
Fig. G.21 Carpeta Llave del Dialogo Configuración .................................................................. 121
Fig. G.22 Mensaje de llave incompleta ...................................................................................... 122
Fig. G.23 Mensaje de llave no valida ......................................................................................... 122
10
Fig. G.24 Carpeta Directorio del Dialogo Configuración ........................................................... 122
Fig. G.25 Cuadro de dialogo Buscar Carpeta .............................................................................. 123
Fig. H. l Vista superior de la tarjeta de expansión ...................................................................... 130
Fig. H.2 Detalle de la vista superior de la tarjeta de expansión ................................................. 130
Fig. H.3 Vista inferior de la tarjeta de expansión ....................................................................... 131
Fig. H.4 Detalle de la vista inferior de la tarjeta de expansión ................................................... 131
11
LISTADO DE TABLAS.
Tabla 1-1 Indice para bytes y bits .................................................................................................. 22
Tabla 1-2 Numero de rondas por combinaciones de tamaño de llave y bloque en AES ............... 23
Tabla 2-1 Fabricantes y software de programación de dispositivos .............................................. 45
Tabla 3-1 Resultados obtenidos de la compilación individual de entidades en la jerarquía
ENC DEC ................................................................................................................... 55
Tabla 3-2 Resultados obtenidos de la compilación individual de entidades en la jerarquía
KEY SCH ................................................................................................................... 56
Tabla 3-3 Recursos empleados por la entidad AES ...................................................................... 56
Tabla 3-4 Lista de paquetes en la descripción de AES .................................................................. 57
Tabla 3-5 Resultados de tiempo de proceso para la descripción AES(descripción original) ........ 58
Tabla 4-1 Comparación entre entidades que implementan el inverso de GF(256) ....................... 61
Tabla 4-2 Comparación de la descripción original vs 1 ªoptimización ......................................... 61
Tabla 4-3 Comparación de la descripción original vs 2ª optimización ......................................... 62
Tabla 4-4 Ciclos de reloj para hallar un inverso ............................................................................ 64
Tabla 4-5 Resultados de tiempo de proceso para la descripción AES_II (lª optimización) ......... 64
Tabla 4-6 Comparación entre especificaciones similiares ............................................................ 67
Tabla B-1 Características generales de dispositivos de la familia APEX 20K. ............................ 79
Tabla B-2 Características específicas de los dispositivos APEX 20KC (1.8 V) ........................... 80
Tabla B-3 Características específicas de los dispositivos APEX 20K (2.5 V) .............................. 80
Tabla B-4 Características específicas de los dispositivos APEX 20KE (1.8 V) (parte 1 de 2) ..... 81
Tabla B-5 Características específicas de los dispositivos APEX 20KE (1.8 V) (parte 2 de 2) ..... 81
Tabla B-6 Características generales de dispositivos de la familia FLEX 1 OK .............................. 82
Tabla B-7 Características específicas de los dispositivos APEX 1 OKE (2.5 V) ........................... 82
Tabla B-8 Características específicas de los dispositivos APEX 1 OK y 1 OKA (5.0 V Y 3.3 V) .. 83
Tabla B-9 Características específicas de los dispositivos APEX lOK y lOKA (5.0 V Y 3.3 V) .. 83
Tabla C-1 Simbología empleada en las tablas de jerarquías de compilación ............................... 84
Tabla C-2 Recursos empleados para AES en un dispositivo EP20K600EBC652-1X ................. 85
Tabla C-3 Recursos empleados para AES_II en un dispositivo EP20K600EBC652-1X ............ 86
Tabla C-4 Recursos empleados para AES_II en un dispositivo EPF10KlOOEBC356-l ............. 86
Tabla C-5 Recursos empleados para AES_III en un dispositivo EP20K600EBC652-1X ........... 87
Tabla C-6 Recursos empleados para AES_III en un dispositivo EPF10KlOOEBC356-l.. .......... 87
12
Tabla G-1 Comandos en la Barra de Herramientas ..................................................................... 112
Tabla G-2 Descripción de indicadores en la barra de estado ...................................................... 116
Tabla G-3 Comandos del menú Archivo ..................................................................................... 125
Tabla G-4 Comandos del menú Modalidad ................................................................................. 126
Tabla G-5 Comandos del menú Configuración ........................................................................... 127
Tabla G-6 Comandos del menú Ver ............................................................................................ 127
Tabla G-7 Comandos del menú Ayuda ....................................................................................... 128
Tabla H-1 Señalización PCI en las terminales del box header. ................................................... 133
13
INTRODUCCIÓN.
Cada día se incrementa el empleo de los sistemas computacionales, ya sea en el hogar, el trabajo,
las escuelas, los negocios o en los centros de investigación, dando como consecuencia el aumento
en mayor proporción de la cantidad de información procesada por estos sistemas. Junto con el
crecimiento del volumen de la información que se procesa en las computadoras, es obvio que, la
mayor parte de ésta información, es de gran importancia para su propietario, y en algunos casos
está resulta ser de carácter confidencial y en casos más específicos puede ser de carácter secreto,
dependiendo, por supuesto, del ámbito donde se encuentre la información.
Para la protección de la confidencialidad de nuestra información contenida en los sistemas
computacionales, se hace necesario el empleo de mecanismos, que la protejan (p.e. contraseñas,
codificación, encripción). Aunque para la mayoría de los usuarios (hogares, oficinas y escuelas)
no es frecuente el desear proteger algún archivo con información, existen situaciones particulares
donde mantener la información de forma confidencial esparte de un procedimiento sistemático
de operación, como puede ser en los casos de protección de derechos de autor, de la información
desarrollada en un centro de investigación científica y en los centros de inteligencia
gubernamentales.
Existe en el mercado una amplia variedad de paquetes computacionales destinados a
proporcionar confidencialidad a la información almacenada en una PC, el paquete computacional
ofrece poca seguridad fisica, especialmente con respecto al almacenamiento de la llave de
encripción[ 1 ], inversamente los algoritmos criptográficos, así como sus llaves asociadas,
implementados en un dispositivo electrónico son, por naturaleza fisicamente mas seguros y no
pueden ser leídos o modificados fácilmente por un ataque exterior[2].
El objetivo del presente trabajo es implementar el algoritmo de encripción avanzado AEA en un
dispositivo lógico programable (PLD) de alta densidad de tipo FPGA, y que pueda ser controlado
a partir del bus PCI[3], tomando como base que este bus, entre los disponibles en una PC, es el
que ofrece mayor velocidad de transferencia de información. Con el fin de aprovechar al máximo
el potencial de los PLDs de tipo FPGA así como las herramientas computacionales de desarrollo
que los acompañan, se hará uso de un lenguaje de descripción material como HDL para
desarrollar la implementación material del AES.
14
El capitulo l describe al Algoritmo de Encripción Avanzado, objeto de desarrollo en este trabajo:
presenta conceptos básicos de algoritmos, así como el proceso de selección del Estándar, la
notación y convenciones de este mismo, además da una descripción un tanto detallada de la
especificación, y por último se presentan consideraciones para la implementación de hardware de
este Algoritmo.
El capitulo 2 trata lo relacionado con los Dispositivos Lógicos Programables, haciendo énfasis en
los de tipo FPGA; de igual forma se trata la clasificación y los criterios para la selección del
dispositivo a emplear.
La parte medular de este trabajo se presenta en el capitulo 3, se detalla el proceso empleado para
la especificación del Estandar AES elaborada con un lenguaje de descripción material.
El capitulo 4 contiene las pruebas efectuadas a la especificación, las optimizaciones elaboradas
de esta misma, así como un análisis comparativo con otros trabajos semejantes ya realizados.
También se presentan los recursos de apoyo elaborados para una futura puesta en operación del
sistema, como son la interfaz de usuario y tarjeta de expansión.
Las futuras motivaciones de este trabajo y las conclusiones finales se presentan en el último
capitulo.
Se podrá encontrar una lista con Acrónimos y definiciones usadas en este trabajo en el ANEXO
A.
l. CAPITULO 1: EL ALGORITMO DE ENCRIPCION
A V ANZADO (AES).
1.1. INTRODUCCIÓN A LA ENCRIPCIÓN.
15
La criptología es una rama de las matemáticas que estudia los aspectos y contenidos de la
información en condiciones de secrecía. La criptología se divide en criptografia y criptoanalisís.
La c1iptografia es el arte y ciencia de ocultar mensajes de forma segura, ya sea por medio de una
clave secreta o por un método enigmático que altere los símbolos de la infonnación sin alterar su
contenido, convirtiendo a la información modificada en un conjunto de símbolos sin contenido
para las partes que no conocen el método de alteración; por otro lado, el criptoanálisis es el arte y
ciencia de poder saber el contenido de mensajes cifrados, aplicando metodologías y técnicas . que
penniten recuperar la información que ha sido previamente tratada por un procedimiento
criptográfico, sin conocer a priori el método utilizado para la criptografia[4].
Ahora bien, se desea proteger la información contenida en un archivo de computadora, de tal
fonna que la información contenida en él sea inteligible solo para propietario del archivo o para
quien esté último decida. Para tal efecto se le aplica al archivo inteligible (generalmente llamado
en texto plano) una función que lo vuelva ininteligible (texto cifrado), a esta función comúnmente
se le llama encripción o cifrado'. Cuando nuevamente se desee volver inteligible el contenido del
archivo cifrado se le deberá aplicar una función inversa denominada decripción o descifrado.
La función usada para el cifrado y descifrado es llamada algoritmo criptográfico. Trasladándonos
a tiempos remotos, la seguridad de cualquier cifrado radicaba en mantener en secreto la fonna de
cómo operaba el algoritmo criptográfico. En la actualidad este problema se ha esuelto con el uso
de una llave de cifrado o encripción. Esto dio origen a dos tipos de algoritmos basados en llaves:
los algoritmos simétricos y los asimétricos.
I Los términos cifrar y encriptar serán usados en forma indistinta en este documento; al igual que los términos
descifrar y decriptar.
1.1.1. ALGORITMOS SIMÉTRICOS.
Estos algoritmos son comúnmente llamados algoritmos de llave secreta, algoritmos de llave
simple o algoritmos de una llave, ya que por lo general, tanto para el cifrado y descifrado se
emplea una sola llave de encripción. Regresando al caso de nuestro archivo de computadora
encriptado, aquel que desee conocer el contenido de este archivo, deberá contar con la llave usad;1
para cifrar este archivo. La seguridad en este tipo de algoritmos radica en mantener secreta l;1
llave de encripción.
Los algmihnos simétricos, a su vez, son divididos dentro dos categorías. Una categoría abarca ,l
aquellos algoritmos que operan sobre un bit (o a veces sobre un byte) del texto plano a la vez,
estos algoritmos son llamados algoritmos de flujo. Otra categoría abarca a aquellos algoritmos
que operan sobre grupos de bits del texto plano, ya que operan sobre bloques de bits, estos
algmitmos se les conoce como algoritmos de bloque.
Como ejemplos de algoritmos simétricos se pueden citar a:
DES (Data Encryption Standard - Estándar de Encripción de Datos)
DES tuvo su origen en un programa destinado a la protección de datos, presentado por el
Instituto Nacional de Estándares y Tecnología (NIST - National lnstitute of Standard.\· anc/
Technology), de los EE.UU. DES fue adoptado por ·eI gobierno de los EE.UU. como estándar
en 1977 y como estándar ANSI (American National Standards lnstitute - Instituto Nacional
de Estándares Americanos) en 1981. El tamaño de bloque es de 64 bits y la llave de
encripción tiene un tamaño de 56 bits. Su funcionamiento, aunque complicado, está basado en
simples operaciones lógicas, tales como sustituciones seguidas de permutaciones, realizadas
sobre grupos de bits. La combinación de estas operaciones es realizada 16 veces sobre cad,1
bloque resultante.
Triple-DES
Es una variación del algoritmo anterior, pensada para aumentar su seguridad y al mismo
tiempo mantener la compatibilidad con las implementaciones ya hechas de DES. Triple-DES
consiste en aplicar DES tres veces con dos(o tres) claves diferentes, de la siguiente manern:
en primer lugar se cifra el texto en claro empleando la primera clave, después se
descifra(vuelve a encriptar) el criptograma obtenido con la segunda y finalmente se vuelve a
cifrar con la primera(tercera). Para descifrar el mensaje se aplica el proceso inverso. Esto
equivale a un cifrado con una clave de doble(o triple) longitud.
IDEA (lnternational Data Encryption Algorithm, Algoritmo Internacional de Encripción de
Datos)
Sistema criptográfico simétrico, desarrollado en Zurich en el año de 1990 por James L.
Massey y Xuejia Lai. El tamaño del bloque es de 64 bits, la longitud de llave de encripción es
de 128 bits. El sistema realiza 16 iteraciones en tof':11. Inicialmente el bloque inicial se divide
en cuatro sub-bloques, en cada iteración se aplican operaciones de XOR, suma y
multiplicación sobre los cuatro sub-bloques y 16 subllaves. Además, el segundo sub-bloque
es intercambiado con el tercero. Y finalmente los cuatro sub-bloques son combinados con 4
subllaves en una transformación de salida. Estealgoritmo es de libre difüsión y no estú
sometido a ningún tipo de restricciones o permisos nacionales, por lo que se ha difundido
ampliamente, utilizándose en sistemas como UNIX y en programas de cifrado de con-eo
como PGP.
17
Blowfish
Desarrollado por Bruce Schneider. El tamaño del bloque es de 64 bits; la llave de enc1ipción
es de tamaño variable con un limite de hasta 448 bits. El algoritmo consiste en dos partes:
expansión de la llave y encripción de datos. La expansión de la llave consiste en generar
subllaves a partir de la llave de encripción, se generan hasta un total de 4168 bytes. La
encripción de los datos consiste en una función iterada 16 veces. Cada iteración consiste en
una pe1mutación dependiente de la llave y una sustitución dependiente de la llave y de los
datos. Las operaciones básicas realizadas por el algoritmo son adiciones y XORs en palabras
de 32 bits.
RC4 (Rivest'.\· Code 4)
RC4 es un algoritmo de cifrado de flujo de clave de tamaño variable. Fue desairnllado en el
año 1987 por Ron Rivest para la compañía RSA Data Security, Inc. A pai1ir de la llave de
encripción se genera una serie de números aleatorios a los cuales se aplica una operación
XOR junto con los caracteres del mensaje, obteniéndose el criptograma. Para descifrar, se
aplica la misma operación, esta vez con los caracteres del criptograma. RC4 es un alg01itrno
que se utiliza en diversos productos comerciales.
l.l.2. ALGORITMOS ASIMÉTRICOS.
Estos algoritmos son comúnmente conocidos como algoritmos de llave publica, ya que la llave
con que se cifra un archivo puede hacerse publica, de aquí que la llave de enc1ipción y la de
decripción sean diferentes. La llave de decripción es llamada llave privada, solo aquella persona
que contenga la llave privada puede saber el contenido de un archivo cifrado con la llave publica.
Estos algoritmos basan su fortaleza en la dificultad de calcular logaritmos discretos.
Como ejemplos de algoritmos asimétricos podemos citar a:
Diffie-Hellman.
El principal propósito de este algoritmo es permitir el intercambio de llaves entre dos usua1ios
en forma segura. E algoritmo funciona de la siguiente ~rma:
RSA.
Se escogen dos números públicos q y a entre los usuarios con q<a.
El usuario A selecciona un valor privado XA ( XA < q) calcula Y A =ax, y se lo envía a I
usuario B.
El usuario B también selecciona un valor privado X8 (X8< q) calcula Y B=a x,. y se lo
envía al usuario A.
Se generan las llaves secretas en ambos lados con: K= (YslA mod q ó K=(Y A) x,. mod e¡
según corresponda.
Para la encripción de un mensaje M en este algoritmo, se tiene, como llave publica un número
n producto de dos números primos (p y q); y e primo para ¡o-1 )(q-1 ). La llave p1ivada es
d=e· 1 mod ((p-l)(q-1)).
Para encriptar datos se emplea c=Me mod n. Para la decripción M=cd mod n.
IX
EIGamal.
ElGamal puede ser empleado para encnpc1on de un mensaje M: primeramente se escoge un
número primo p, y dos números aleatorios, g y x, tal que ambos sean mucho menores que p.
Se calcula y = gx mod p. La llave publica es y, g y p. La llave privada es x, donde x < p. Pé!ra
encripción se escoge un numero aleatorio k primo a p- 1. Se tiene calcula en cifrado, donde a
= fÍ' mod p, y h= /M mod p son el texto cifrado. La decripción es M=b/ax mod p. Cabe notar
que en este algoritmo, el texto cifrado es dos veces mayor que el texto plano.
1.2. SELECCIÓN DEL NUEVO ESTÁNDAR DE ENCRIPCIÓN
AVANZADO.
En enero de 1997 el Instituto Nacional de Estándares y Tecnología (NIST) de los EE.UU.
anunció la iniciativa para desarrollar un nuevo estándar de encripción llamado Estándar de
Encripción Avanzado (AES). A diferencia del proceso de selección de DES (Data EnCJyption
Standard - Estándar de Encripción de Datos, FIPS PUB 46[5]), de SHA-1 (Secure Hash
Algorithm - Algoritmo de Seguridad Hash2, FIPS PUB 180-1 [6])y de DSA ([)igital Signaturc
Algorithm - Algoritmo Digital de Signatura, FIPS PUB 186-2 [7]), el proceso para la selección
de AES sería abierto, es decir, cualquiera podría presentar un trabajo a fin de ser considerado
como algoritmo candidato a nuevo estándar de encripción avanzado. NIST no diseño ningún tipo
de evaluación para probar la seguridad y eficiencia de los algoritmos candidatos, en lugar de ello
invito a la comunidad criptológica a probar ataques e intentar el criptoanálisis de los diferentes
candidatos, así como evaluar el costo de implementación. Todos los resultados debieron ser
enviados a NIST para ser publicados en el sitio web de esté ó para ser presentados en las
conferencias de AES organizadas por NIST.
En septiembre de 1997 se publicó la solicitud final para recibir candidatos, el requisito mínimo
para ser candidato era de presentar un algoritmo simétrico de bloque, capaz de soportar la
longitud de bloque de 128 bits con llaves de encripción de tamaño de 128, 192 ó 256 bits. NIST
declaró que el algoritmo debe ser igual de seguro como Triple DES, pero mas eficiente que esté;
además de que los desarrolladores deberían de poner disponible su algoritmo, libre de derechos
de autor si resultaran seleccionados como el nuevo AES. Como requisito para ser considerado
como candidato oficial, cada uno de los desarrolladores entregó los siguientes elementos:
l . Especificación completa del bloque de cifrado en forma de algoritmo,
2. Una implementación de referencia en ANSI C, así como optimizaciones matemáticas de
la implementación en ANSI C y Java,
3. Implementación de unas series de respuesta conocida (vectores de prueba) y prnebas de
Monte Cario, a fin de verificar que el algoritmo estuviera bien implementado,
4. Estimados de eficiencia en software y hardware, ventajas y limitaciones del cifrado en
varias aplicaciones.
5. Un análisis de resistencia contra ataques criptográficos conocidos.
1 Un numero hash es aquel generado por medio de transformaciones especificas a partir de una cadena de texto. es
casi imposible que una cadena de texto diferente produzca un mismo numero hash de otra cadena de texto.
19
1.2.l. PROCESO DE SELECCIÓN.
El proceso de aceptación de algoritmos finalizó el 15 de mayo de 1998. Todos los candidatos
aceptados fueron presentados en "La p1imera conferencia de candidatos para estúndar de
enc1ipción avanzado" celebrada en Ventura California del 20 al 22 de agosto de 1998. La
conferencia sirvió como inició oficial de la primera ronda de evaluación.
Los c1iterios de evaluación para la primera fase eliminatoria fueron divididos dentro de tres
categ01ías: seguridad, costo y por ultimo caracteristicas e implementación del algoritmo .. La
NIST invito a la comunidad criptológica a participar para la evaluación de estos aspectos, cuyas
caracteristicas se describen a continuación:
- Seguridad.
La seguridad fue la categoria mas importante, y qmzas la mas dificil de evaluar. Solo
algunos candidatos mostraron algunos errores teóricos en sus diseños, la gran mayotia fue
clasificado dentro la categoria de "debilidades no demostradas".
- Costo.
Se refinieron dos categorias: la primera asociada a los costos con la propiedad intelectual
y las patentes; y la segunda categoria asociada a los costos de implementación y
ejecución, es decir, aspectos relacionados a la implementación en software como
eficiencia computacional, tamaño del programa y memoria requerida, por otra pmte en las
implementaciones en hardware se considero el área que ocuparla implementar el
algoritmo en un circuito integrado.
- Caracteristicas del Algoritmo y de implementación.
Para este aspecto se consideró la versatibilidad, es decir la habilidad del algoritmo para
ser implementado en diferentes plataformas (desde microcontroladores de 8 bits. hasta
Smart Cards); otro aspecto a considerar fue la velocidad con que la llave esta disponible
para ser utilizada, nombrando a esta caracteristicas agilidad de la llave; y diseiio sin¡ple:
que esta relacionado al tamaño de la descripción del algoritmo, así como alnumero de
diferentes operaciones usadas para la especificación.
En marzo de 1999 la segunda conferencia de .candidatos a AES fue en Roma, Italia. En esta
conferencia se presentaron trabajos realizados sobre los candidatos. En la sesión relativa a
ataques criptográficos los algoritmos FROG(TecApro CR), Magenta(Deutsche Telekom DE) y
LOKI97(Brown et al AU) no obtuvieron resultados satisfactorios con respecto a los
requerimientos de seguridad impuestos por NIST; por otro lado DEAL(Outerbridge, Knudsen
USA-DK) no satisfizo los requerimientos de seguridad y HPC (Schroeppel USA) comenzó a
mostrar ciertas debilidades. Lo anterior eliminaba a cinco candidatos. Igualmente se presentaron
trabajos de desempeño en un microprocesador Pentium[8] donde los algoritmos mas rápidos en
este microprocesador fueron: RC6, Rijndael, Twofish, MARS y Crypton, los otros candidatos
como DEAL, Frog, Magenta, SAFER+ y Serpent aparentaron lentitud; otros esciitos (9]( 1 O] lo
confinnaron. Relacionado con el desempeño de los candidatos en implementación en "smmt
cards" con microprocesadores de 8 y 32 bits se presentaron algunos trabajos[l 1][9], destacando
Rijndael como el mejor en esta plataforma de desarrollo.
En agosto de 1999 NIST anunció a los cinco finalistas: MARS, RC6, Rijndael, Serpent y
Twofish, al mismo tiempo que publicó un reporte[l2] donde se describen los pom1enores de la
selección. Las siguientes pruebas a estos cinco fmalistas fueron enfocadas a realizar c1iptoanálisis
a los algoritmos y a la implementación en hardware de los mismos.
20
1.2.2. LOS FINALISTAS
Una breve descripción de los cinco finalistas se presenta a continuación:
MARS
Desarrollado por IBM (Jnternational Business Machines Corporation). A un bloque de
entrada, MARS aplica inicialmente una adición de llave, luego aplica 8 iteraciones de
mezclado de "ida" sin uso de llave, en las siguientes 16 iteraciones si emplea la llave: 8
iteraciones de una transformación de "ida" y 8 iteraciones de una transfo1mación de
"regreso", seguidas de 8 iteraciones de mezclado de "regreso" sin uso de llave. finalmente se
aplica una substracción de llave. Las iteraciones 911 llave usan tablas de substitución (S-Box).
adición, y operaciones XOR. Las iteraciones con llave emplean operaciones como
multiplicación, rotaciones dependientes de los datos y adiciones de llave. Mayor info1111ación
sobre este algoritmo lo podrá encontrar en [ 13].
RC6
Este algoritmo de encnpc1on fue desarrollado por los laboratorios RSA[ 14]. El tamaño del
bloque es de 256 bits, la llave de encripción puede ser de 128, 196 o 256 bits, el numero de
iteraciones para el bloque es de 20. De forma general el algoritmo opera en la siguiente
manera: Inicialmente el texto plano se almacena en cuatro registros de 32 bytes (tamaño del
bloque), la llave inicial es expandida y almacenada en un arreglo de 44 elementos de 256 bits
cada uno. Se aplica una operación XOR con el segundo y cuarto registro con los 2 primeros
elementos de la llave. A continuación se efectúan las 20 iteraciones del bloque, confonnadas
por operaciones sobre los 4 registros de multiplicación modular de 32 bits, adición,
operaciones XOR con la llave y entre registros, para concluir finalmente con una operación
XOR con el primer y tercer registro con los dos últimos elementos del arreglo de la llave. La
decripción opera en forma inversa ala encripción.
Rijndael
Rijndael fue desarrollado por dos particulares loan Daemen y Vincent Rijmen. Rijndael es un
algoritmo con longitudes de bloque y de llave variables. El tamaño del bloque y el tamaño de
la llave puede ser independientemente especificados con múltiplos de 32 bits, teniendo como
mínimo 128 bits y un máximo de 256 bits. Las operaciones especificadas en Rijndael están
orientadas a byte. El tamaño de la llave determina el numero de iteraciones que se realizaran
sobre el bloque. Una descripción mas detallada de este algoritmo se presenta en las secciones
l.3 y l.4. ó en [15].
Serpent
Fue desarrollado por Ross Anderson (Universidad de Cambridge), Eli Biham (Technion), y
Lars Knudsen (Universidad de California San Diego). El algoritmo consiste en una
transformación lineal basada en sustitución. El tamaño del bloque de encripción es de 128
bits, el tamaño de la llave puede ser variable, pero para la propuesta se especificó de 128, 196
o 256 bits. Consta de 32 iteraciones, previo a iniciar las iteraciones, se aplica una pennutación
inicial; a cada iteración se le aplica tres operaciones, a saber: Una operación XOR con una de
las 33 subllaves disponibles, una sustitución en paralelo de 32 bits con una de las ocho S-Box
especificadas y por ultimo se aplica una transformación lineal. En la ultima iteración, una
segunda operación XOR con una subllave es aplicada, reemplazando a la transfonnación
lineal. Finalmente se aplica nuevamente una permutación lineal. Para la dec1ipción se
diferencia de la encripción en que las S-Boxes deben ser empleadas en orden inverso, así
21
como aplicar la función inversa de la transformación lineal, al igual que usar las subllaves en
orden inverso. El algoritmo completo se encuentra disponible en [ 16].
Twofish
Fue desarrollado por un equipo dirigido por Bruce Schneier[ 17]. Twofish es un alg01itmo que
opera sobre bloques de 128 bits. La longitud de la llave de encripción puede ser de 128, 196,
256 o mayor. Consiste en 16 iteraciones de tipo Feistei3 modificado con rotaciones de I bit.
En cada iteración las operaciones modifican una palabra de 32 bits aplicándole una
sustitución dependiente de la llave por medio de S-Boxes, seguida de una transfonnación
seudo- Hadamard y una adición de llave.
Finalmente el 2 de octubre del 2000 NIST anunció oficialmente que el algoritmo elegido para ser
el nuevo AES fue Rijndael. De igual forma NIST publicó un reporte donde se resumen las
contribuciones y motivaciones de esta elección[ 18].
AES comenzó a ser un Estándar del Gobierno Norteamericano a partir del 26 de Mayo del 2002
(FIPS PUB 197[20]) reemplazando al Estándar de Encripción de Datos (DES) [ 19]. A ES será
usado principalmente por Organismos Gubernamentales Norteamericanos para proteger la
información delicada y dificil de clasificar; aunque, NIST anticipa que AES podrá ser usado
voluntariamente por organismos e instituciones no gubernamentales dentro y fuera de los Estados
Unidos.
1.3. NOTACIÓN Y CONVENCIONES DE AES
La notación y convenciones para la especificación de AES se exponen en este apaitado,
solamente se pretende exponer la forma en que los bits, bytes, y arreglos de estos son utilizados y
tratados en la especificación y no hacer un trabajo detallado acerca de la notación y las
matemáticas utilizadas en el algoritmo.
1.3.1. BITS Y BYTES
La entrada y la salida de AES consisten en secuencias de 128 bits. La llave de encripción es una
secuencia de 128,192 o 256 bits. Los bits se numeran comenzando en cero y tenninando en un
numero menor al tamaño de la secuencia, es decir, para una secuencia de 128 bits, los bits irád
numerados del numero O al numero 127. Al número que acompaña al bit se le llama índice.
La unidad básica de procesamiento en el AES es el byte, que es conformada por una secuencia de
ocho bits. Los bytes pueden ser representados por una concatenación de los valores indivi<:fuales
de los bits. Estos bytes pueden ser interpretados como un campo füúto de elementos usando la
siguiente representación polinonúal:
( l. 1)
3 Generalmente Feistel es un método de transformación de cualquier función, empleando para ello una permutación.
22
Los arreglos de bytes pueden ser representados de la siguiente forma:
( 1.2)
De aquí que, el ancho de los bloques conforme al estándar puede ser de n= 1 ó, si se trata del
bloque de entrada o de salida en AES de 128 bits y n=J6 para una llave de longitud igua\mentc
de 128 bits, n=24 para una llave de longitud de 192 bits y n=32 para una llave de longitud de 256
bits.
Resumiendo: elíndice de los bits y bytes de entrada están dados por la tabla 1-1.
Tabla 1-1 Índice para bytes y bits.
Secuencia de
,entrada dél o 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ...
l!it. , '
>:J'lumero de o 1 2
byte
...
'
,Numer.ación
' d~! bit ,t'erit~o . 7 6 5 4 3 2 1 o 7 6 5 4 3 2 1 o 7 6 5 4 3 2 1 ll ...
, ' del byte
"""
1.3.2. PALABRA
Una palabra consiste en un arreglo lineal de 4 bytes (representado en la figura 1.1.), es decir. de
32 bits. Este tipo de dato generalmente es usado en las operaciones de MixColumns y
KeyExpansion que serán tratadas en secciones posteriores.
ªº
Fig. 1.1 Representación grafica de una Palabra.
1.3.3. EL ESTADO
internamente AES opera sobre un arreglo bidimensional de bytes, este arreglo bidimensional es
llamado el estado. El estado consiste en cuatro renglones de bytes, cada renglón contiene N b
bytes, donde Nb es la longitud del bloque dividido entre 32. El arreglo estado se menciona como
s, cada byte individual tiene dos subíndices, r el numero de renglón en el intervalo de O ~ r < 4 y
e el numero de columna en el intervalo de O ~ e < Nb . Por lo tanto para hacer referencia a un
byte individual del Estado se escribirá sr,c o s[r,c]. Para AES Nb=44 .
Al inicio, ya sea de la encripción o de la decripción los bytes de entrada son copiados dentro del
estado como se ilustra en la figura 1.2. Todas las operaciones en el AEA se efectúan sobre el
estado, el resultado final es copiado a otro arreglo de salida.
4 En Rijndael Nb puede tomar un valor diferente a 4.
23
bytes de entrada estado bytes de salida
ino i114 ins Ílt12 So S4 Sg s,2 out o Ollt4 Ollts Oll( f2
in, ins in9 in13 S¡ S5 S9 S13 out, 011(5 OU(9 Olltu
in2 in6 in 10 il114 s2 S6 S¡() S¡4 out2 out6 out 10 011 f /4
i113 i117 ill II in15 SJ S7 su S¡5 out3 011(7 out 11 Oll(¡_,¡
Fig. 1.2 Arreglos de entrada, estado y salida
1.4. ESPECIFICACIÓN
Para AES el tamaño de los bloques de entrada, de salida y el estado es de 128 bits. Esto esta
representado por Nb = 4, lo que significa el numero de palabras de 32 bits (numero de columnas)
en el estado.
Por otra parte el tamaño de la llave de encripción puede ser de 128, 196 o 256 bits. El tama110 de
la llave se representa como Nk = 4,6, o 8, que de igual fom1a representa el numero de palabras de
32 bits (así como el numero de columnas) contenidas en la llave de encripción.
El numero de iteraciones (o rondas) que son ejecutadas durante la encripción o decripción
depende directamente del tamaño de la llave, el numero de rondas es representado por Nr, y esta
dado por la siguiente combinación descrita en la tabla 1-2.
La función iterativa esta compuesta por diferentes transformaciones:
l. Una sustitución de bytes empleando una caja S (S-Box).
2. Corrimiento de bytes en el Estado a diferentes distancias.
3. Mezcla de datos entre columnas del Estado.
4. Inserción de la llave de encripción.
Tabla 1-2 Numero de rondas por combinaciones de tamaño de llave y bloque en AES.
4
11
4 -¡¡ 10
··--··--··-·--··--·--... ~.
J 11 6 4 12
l
-,. -------------·--·-----·- ---
li 8 4 14
1
--- r
1
1
24
Estas transformaciones y sus inversas (para la decripción) son descritas con detalle en ¡20), para
efectos de implementación se describen las tres partes constitutivas del algoritmo en los apa11ados
siguientes.
1.4.1. LISTA DE LLAVES
La programación de la llave consta en sí de dos con'lponentes: La expansión de la llave y la
selección de la Ronda. La expansión de la llave define como la llave expandida se deriva de b
llave de cifrado. El numero total de bits de la llave expandida es igual al tamaño (en bytes) de l,1
llave de cifrado multiplicado por el numero de rondas mas una ronda adicional (ver sección
anterior para el numero de rondas). Para el caso especifico de esta implementación dado que el
tamaño del estado y de la llave de cifrado es 16 bytes, el numero de rondas es I O, el tamaiio de )¡¡
llave expandida es de 176 bytes. La llave expandida siempre es derivada de la llave de cifrado.
nunca deberá ser especificada directamente.
AES toma la llave de encripción, K, y desarrolla una rutina de expansión de llave para generar
una lista de llaves. La rutina de expansión genera un total de Nb (Nr+ 1) palabras. El algoritmo
requiere un co~junto inicial de Nb palabras de la llave. La lista de llaves resultantes consiste en
un mTeglo lineal de palabras, llamado lw¡ 1, con i en el intervalo O :Si :S N" ( N,. + 1)
El algoritmo de expansión de llave se apoya de dos funciones llamadas SubWord( ) y
RotWord( ) así como de una constante de nombre Rcon(i) . La función SubWord( ) toma una
Palabra de entrada y aplica una sustitución de cada byte con los bytes contenidos en una tabla
llamada S-Box. Por otro lado la función RotWord( )toma una palabra de entrada [ao,a1,a2.a,] y
desan-olla una permutación cíclica, devolviendo como resultado una palabra de la lo_m1,1
[a1,a2.a3,ao).
La operación de estas dos funciones se ilustra en la figura 1.3:
5-Box RotWord()
ªo ª1
ª1 ª2
ª2 a' 2 ª2 ª3
ª3 a' 3 33 ªº
Fig. 1.3 Operación de las funciones SubWord( )y RotWord( ).
La constante Rcon[i) es una palabra de la forma [RC[i], {00}, {00}, {00}] donde RC[i] contiene
los valores dados por las siguientes ecuaciones:
RC[l] = xº
RC[2] = x
RC[i] = x • RC[i-1] = xi- l , i>2.
El seudo código para obtener la llave de expansión se presenta en la figura 1.4:
KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+l)], Nk)
begin
word temp
i = o
while (i < Nk)
( 1.3)
( 1.4)
( 1.5)
w[i] = word(key[4*i], key[4*i+l], key[4*i+2], key[4*i+3))
i = i+l
end
end while
i = Nk
while (i < Nb * (Nr+l)]
temp = w[i-1)
if (i mod Nk = O)
temp = SubWord(RotWord(temp)) xor Rcon[i/Nk)
else if (Nk > 6 and i mod Nk = 4)
temp = SubWord(temp)
end if
w[i] = w[i-Nk] xor temp
i = i + 1
end while
Fig. 1.4 Seudo código para la expansión de la llave de cifrado.
Las primeras Nk palabras de la llave expandida (w(O .. Nk-11) son iguales a la llave de encripción.
r _)
La siguiente w(i) palabra (para i 2:: 4) son el resultado de aplicar una operación XOR a la palabra
previa (w(i-11) con la palabra localizada Nk posiciones atrás(w(i-Nkl).
Para obtener las palabras en posiciones múltiplos de Nk se aplica la función RotWord( ) a la
palabra previa (w(i-1]), seguida de una aplicación de la función SubWord( ), termimmdo con una
operación XOR con Rcon[i) antes de la operación XOR con w[i-Nk).
Una operación especial se realiza para hallar la Palabra w(il cuando se cumple que Nk>6 e i mod
N k = 4, esta operación consiste en aplicar solamente la función SubWord( ) a la palabra previa
w(i-1) antes de la operación XOR con w(i-Nk).
l.4.2. ENCRIPCIÓN
Al comienzo de la encripción, la entrada es copiada al Estado usando las convenciones desc1itas
en la sección 1.3.3. Después de una adición de la llave de encripción, el Estado es transfonnado
por una función llamada ronda, 10,12 o 14 veces (dependiendo del tamaño de la llave de
encripción) y finalmente se le aplica una ronda final, misma que es similar a la ronda con un paso
omitido (MixColumns ).
El seudo código del cifrado se presenta en la figura 1.5:
Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+l)])
begin
end
byte state[4,Nb]
state = in
AddRoundKey(state, w[O, Nb-1])
for round = 1 step 1 to Nr-1
SubBytes(state)
ShiftRows(state)
MixColwnns(state)
AddRoundKey(state, w[round*Nb, (round+l)*Nb-1])
end for
SubBytes(state)
ShiftRows(state)
AddRound.Key(state, w[Nr*Nb, (Nr+l)*Nb-1])
out= state
Fig. 1.5 Seudo código para la rutina de cifrado.
Las transfonnaciones al Estado contenidas en la Ronda son descritas a continuación.
1.4.2.1 Transformación SubBytes()
26
La transfom1ación SubBytes( ) es una sustitución lineal que opera sobre cada byte independiente
contenido en el Estado. Se emplea una tabla de sustitución llamada S.Box la cual es inve1tible y
se constmye por medio de dos transformaciones:1. Se toma el inverso multiplicativo en el campo finito GF(i) del byte tal como se describe en [2 1]
2. Se aplica una transformación "affine" al byte sobre GF(2):
( 1.6)
donde b¡ es el Íavo bit del byte, y C¡ es el Íavo bit del byte e con valor { O 1100011 ) .
La figura 1.6 ilustra el efecto de la transformación SubBytes( ) en el Estado.
5-Box
50
0.J
5'1.J
50
2,0
50
2,1 5' 2.2
50
2.J
51
3,0 s'J,1 s' 3.2
51
3,3
Fig. 1.6 La transformación SubBytes() aplica la S-Box a cada byte del Estado.
27
1.4.2.2 Transformación ShifRows( ).
En la transformación ShiftRows( ), los bytes de los tres. últimos renglones del Estado son rotados
sobre diferentes números de bytes. El primer renglón no se rota.
La transfonnación ShiftRows( ) procede como sigue:
s',. e= s, (,+,/11_.,.,. Nh))modNh para o< r < 4 y o~ e< Nb
• • . I\ •
donde el valor de rotación shift(r,Nb) depende del numero de renglón (r)
shift(l,4)=1; shift(2,4)=2; shift:(3,4)=3;
La figura 1. 7 ilustra la transformación de ShiftRows sobre el Estado.
s
5o,o 50,1
5 1,0 5 1,1
52.0 52,1
53,0 sJ.1
5 0,2
5 1,2
5 2,2
sJ.2
50,J
51,J
52,J
5 3,3
r-fCID¡
rKTI:J
rfflllD,
s'
5 o,o 5 0,1 5 0,2
5 1.1 5 1,2 5 1,3
5 2,2 5 2,3 5 2,0
·5 3,3 5 3,0 5 3,1
5 o,3
5 1,0
52.1
53,2
Fig. 1.7 La transformación ShiftRows() rota los últimos tres renglones del Estado.
1.4.2.3. Transformación MixColumns( ).
( 1. 7)
( 1.8)
La transformación MixColumns( ) opera sobre el Estado columna por columna, tratando cada
colunma como m arreglo de 4 bytes, tal como se describe en la sección 1.3.2. Las columnas son
consideradas como polinomios sobre GF(28) y multiplicadas modulo x4+1 con un polinomio fijo
a(x) dado por:
a(x) = {03}x3 + {Ol}x 2 +{Ol}x+{02} ( 1.9)
En notación matricial esta multiplicación se escribe:
[
s'o,c.] [ 02 03 01 01 J-[ So,c] S11,c = 01 02 03 01 - S1,c
s'2,c O I O 1 02 03 S2,c
s\c 03 01 01 02 SJ,c
( l. 1 O)
La figura 1.8 ilustra la transformación MixColumns() sobre el Estado:
28
MixColumns
50
0.2
50
0,J
5 1,c 5 1.2
5 1,J
5 1,c 5 '1 .2
50
1,J
5 2,c
5 2,2 52,J 5 '2.2 s'2,J
5 J,o
~.e
5 J.2
5 3,J 5'3,0
51
32 s'J J
Fig. 1.8 MixColumns() opera sobre el Estado columna por columna.
1.4.2.4. Transformación AddRoundKey( ).
En la transformación Add.RounclKey( ), una ronda de la llave es agregada al Estado por medio de
una simple operación XOR a nivel de bit. Cada Ronda de llave consiste en Nb Palabras lomadas
de la lista de llaves. Estas Nb Palabras son agregadas dentro las columnas del Estado como sigue:
[s'o.c, s' 1,c, s'2.c, s\cl= [so.e, S1,c, S2,c, SJ,c] El) [w ronda*Nb+c] para Ü $ C < Nb ( 1 . 1 1)
donde: lwd es la lista de llaves descritas en la sección 2.3.1, y ronda es un entero en el inte1valo
O S ronda S Nr .
La figura 1.9 ilustra la transfonnación de AddRoundKey en el Estado.
5 o,c
5 0.2 5 o,3
50
0,2
50
0,3
5 1,c 50
1,2 s'1,J
w1 wl+c W1+J 5 2,c
1+2
5 2,2 5 2,3
51
2,2 5'2.J
5 J,o
5 3,c
5 3,2 5 J,J 5'3,0 s'J.2 s'J .J
1 = ronda x Nb
Fig. 1.9 AddRoundKey() aplica un XOR de cada columna en el Estado con una Palabra de la lista de llaves.
l.4.3. DECRIPCION
Las transformaciones descritas en la sección anterior pueden ser invertidas e implementadas en
orden inverso para producir la decripción de AES.
La figura l. l O muestra el seudo código para la decripción.
InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+l)])
begin
end
byte state[4,Nb]
state = in
AddRoundKey(state, w[Nr*Nb, (Nr+l)*Nb-1])
for round = Nr-1 step -1 downto 1
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[round*Nb, (round+l)*Nb-1])
InvMixColUIIUls(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[O, Nb-1])
out= state
Fig. 1.1 O Seudo código para la rutjna de decripción.
l.4.3.l. Transformación InvSubBytes( ).
29
Es el inverso de la transfom1ación SubBytes( ), en el cual el inverso de la S.Box se aplicará sobre
cada uno de los bytes que conforman el Estado. Este se obtiene aplicando el inverso de l;i
transfonnación affme, y posterionnente hallando el inverso multiplicativo en GF(28).
El inverso de la transformación Affine esta dada por
( 1. 12)
donde b; es el Íavo bit del byte, y d; es el Íavo bit del byte d con valor { 00000 l O l } .
1.4.3.2. Transformación InvShiftRows( ).
La transfo1mación InvShiftRows( ) es la transformación inversa a ShiftRows( ). Los bytes en los
últimos tres renglones son rotados a la derecha la misma cantidad de lugares anterionnente
rotados.
La figura l. l l ilustra esta operación:
30
s s'
5 o,o 50,1 5 0,2 5 o,3 5 o,o 5 0,1 5 0.2 5 o,J
51,0 s1.1 s1.2 s1,J s1,J 51,0 s1.1 s1.2
5 2,0 5 2,1 Si,2 5 2,3 5 2,2 5 2,J Si.o 5 2,1
5 3,o sJ,1 sJ,2 5 3,J 5 3,1 sJ.2 sJ,J 53,0
Fig. 1.11 lnvShiftRows() rota los tres últimos renglones del estado.
1.4.3.3. Transformación InvMixColumns( ).
La transfonnación MixColumns( ) opera sobre el Estado columna por columna, tratando cada
columna como un arreglo de 4 bytes, tal como se describe en la sección 2.2.2. Las columnas son
consideradas como polinomios sobre GF(28) y multiplicadas modulo x4+l con un polinomio fijo
1 •
a- (x) dado por:
a-\x) = {Ob}x 3 +{Od}x2 +{09}x+ {Oe} ( 1 .13)
1.4.3.4. Inverso de la transformación AddRoundKey( ).
El inverso de la transformación AddRoundKey( ) descrita en la sección 1.4.2.4. es por si misma
su inversa, ya que solo involucra la aplicación de una operación XOR.
1.5. IMPLEMENTACIÓN EN HARDWARE.
La implementación en hardware del AES presenta algunos problemas relacionados con velocidad
y área de chip utilizada; pero da la ventaja de disponer de un dispositivo dedicado al cifrado y
descifrado. Por ejemplo, una implementación del AES en software ejecutándose en un procesador
de propósito general es muy rápida, pero, mantiene ocupado al procesador para realizar dicha
tarea, por lo que una implementación en hardware desahoga al procesador del trabajo excesivo
para que esté pueda atender otras tareas.
Se tomaron algunas consideraciones para el desarrollo del AES en hardware, tales como la forma
de implementación la S-Box y la reutilización de módulos.
1.5. l. S-BOX.
Se consideraron dos alternativas de diseño para la S-Box (empleada en las funciones SubBytes(),
InvSubBytes( ) y en SubWord() - ver 1.4.2. l., 1.4.3. l. y 1.4. l. respectivamente):
• Especificar todas y cada una de las operaciones que realiza la S-Box a nivel de
transferencia de registros ó
31
• emplear tablas que contengan el contenido de los valores de la S-Box.
1.5.l. l. Implementación e.le la S-Box a nivel de registros.
Para la primera alternativa de diseño se debe de considerar que la transfonnación S-Box S,rn es
construida por dos transfom1aciones:
Son[a] = f(g(a)) ( 1.14)
donde g(a) es la transformación:
( 1.15)
y.l(a) es la transformación "aftine". La transformación g(a) es por sí misma su inversa entonces:
S
0
n[a]= g- 1(j-1(a)) =g(J-'(a)) ( 1.16)
De aquí que solo se tuviera la necesidad de implementar las.transformaciones g,f,j" 1 .
1.5.1.2. Implementación de S-Box en tablas de búsquedas.
La segunda alternativa considera la implementación de la S-Box en tablas de búsqueda, las
cuales, por lo general están albergadas en memoria, ya sea RAM ó ROM, dependiendo de la
versatilidad que se le quiera dar a la implementación.
1.5.2. ALGORITMO EQUIVALENTE PARA LA DECRIPCIÓN.
La estructura del AEA es tal que se puede definir un algoritmo equivalente para la decripción,
en el cual, la secuencia de los pasos es igual al de la encripción, con los pasos, claro esta.
reemplazados por sus operaciones inversas y un pequeño cambio en la lista de las llaves. Para una
implementación en hardware esto es de gran ayuda, ya que permite el empleo de los mismos
bloques para encripción y decripción, empleando solamente una señalización para que el bloque
ejecute la acción requerida ( cifrar o descifrar).
A fin de obtenerel algoritmo equivalente para el descifrado, se debe de tomar en cuenta las
siguientes propiedades del AEA:
• El orden para la ejecución de InvShifRows() y lnvSubBytes() es indiferente y
• El orden de AddRoundKey( ) y InvMixColumns ( ) puede ser invertido si la ronda de la
llave es adaptada correctamente.
Una explicación detallada de estas propiedades puede ser encontrada en [22].
32
Aplicando las propiedades anteriores se puede obtener el seudo código mostrado en la figura
1.12.
InvCipher(State, CipherKey)
begin
EqKeyExpansion(CipherKey,EqExpandedKey);
AddRoundKey(State, EqExpandedKey[Nr]);
for i = 1 step 1 to Nr-1
end
EqRound(State, ExpandedKey[round]);
end for
EqFinalRound (State, ExpandedKey[O]);
Fig. 1.12 Seudo código del Cifrado.
EqKeyExpansion() es la función usada en conjunto con el algoritmo equivalente para
descrifado, está definido como sigue:
• Aplicar KeyExpansion( ).
• Aplicar la función InvMixColumns( ) a todas las rondas de la llave, excepto a la p1imcra
y a la última.
El seudo código de EqRound y EqFinalRound se muestran en la figura l .13:
Round(State, ExpandedKey[i])
begin
end;
InvSubBytes(State);
InvShiftRows(State);
InvMixColumns(State);
AddRoundKey (Sta te, ExpandedKey [i·]);
FinalRound (State, ExpandedKey[Nrll;
begin
End;
InvSubBytes(State);
InvShiftRows(State);
AddRoundKey(State,ExpandedKeyCNrll;
Fig. 1.13 Seudo código para las funciones Round( ) y FinalRound( ) del cifrado.
1.6. CONCLUSIÓN.
Se ha presentado un panorama general de la selección del AES, así como algunos conceptos
básicos de criptología. Del AES se han presentado las tres funciones p1incipales como son h1
encripción, decripción y la forma de obtener la lista de llaves. Un aspecto importante tratado son
las consideraciones para la implementación de hardware.
3]
2. CAPITULO 2: DISPOSITIVOS LÓGICOS
PROGRAMABLES
En los 60's y 70's los diseños eran elaborados con dispositivos estándares, la mejor
representación de estos dispositivos es la familia ITL 7400 desarrollado por Texas Instrnments.
Esta primera familia de dispositivos fue considerada como de pequeña escala de integración (SS!
- Small Sea/e o.f lntegration) por contener solamente compuertas lógicas y algunos flip- flops.
Pronto aparecieron circuitos integrados (IC - lntegrated Cireuit) de mediana escala de
integración (MSI - Médium sea/e of lntegration) como decodificadores, multiplexores y
registros. Tanto los circuitos SSI y los MSI eran montados en tarjetas de circuito impreso ( PC:B -
Printed Cireuit Board) e interconectados por conductores, por lo general de cobre.
Posterionnente surgieron los circuitos integrados de larga escala de integración (LSJ - Large
Sea/e /ntegrated) como ejemplo citamos los microprocesadores, memorias RAM y ROM. pue11os
paralelos, interfaces seriales y controladores de interrupciones.
Posterionnente a mediados de la década de los 80's la industria electrónica experimento el
crecimiento en la demanda de computadoras personales, teléfonos celulares y dispositivos. de
comunicación de datos de alta velocidad. Con el fin de ser competitivos, los fab1icantes
desarrollaron productos para incrementar su productividad, con alto desempeño, poco consumo
de energía, dimensiones pequeñas y bajos costos .de producción. Estos productos fueron
materializados por los fabricantes como sistemas complejos de muy larga escala de integración
(VLSI - Very Large Sea/e lntegrated), con pocos circuitos integrados y ocupando poca área de
una tarjeta de circuito impreso. Para el diseño de estos productos existió la necesidad de adoptar
metodologías modernas de diseño y prueba, así como que esta forma de diseño estuviera bien
estrncturada. Los lenguajes de descripción material (HDL - Hardware Deseription Language)
proporcionaron un buen camino para una metodología estructurada y los esfuerzos comenzaron a
repartirse para el desarrollo de estos lenguajes. Algunos lenguajes como CDL ( Computer Design
Languages - Lenguajes de diseño de computadoras), ISP (Jnstruetion Set Processor - Conjunto
de instrucciones para procesador), y AHPL(A Hardware Programming Language - Un lenguaje
de programación de hardware) fueron usados con anterioridad, pero su fin p1incipal era la
ve1ificación del diseño de una arquitectura y no tenían la capacidad de modelar diseños. además
que eran dependientes de la arquitectura del hardware.
34
En w1 principio, los HDLs no estaban estandarizados, pero en 1983, el Departamento de Defensa
de los EE.UU. dentro del programa de circuitos integrados de muy alta velocidad (VHSJC - Verr
High Speed lntegrated Circuit) comenzó el desarrollo del lenguaje de descripción mate1i¡1I
VHSJC (VHDL - VHSIC Hardware Description Lang~tage), en agosto de 1985 la versión 7.2 del
lenguaje fue liberada y en 1987 comenzó a ser estándar de la IEEE.
Los lenguajes de descripción material facilitan la captura, el entendimiento y el mantenimiento de
un diseii.o, además no dejan espacio para interpretación por estar bien definidos. los lenguajes
están estanda1izados, accesibles a todo publico y son aceptados por la industria. Inclusive
pe1111iten la pmtabilidad entre las herramientas de diseño asistido por computadora (CAD -
Computer-Aided Design) y los módulos resultantes pueden ser reutilizados en diseños füturos.
Además de los HDLs empleados en las nuevas metodologías de diseño, los fabricantes
comenzaron a utilizar los PLDs (Programmab/e Logic Device - Dispositivos Lógicos
Programables), así que, ambos comenzaron a ser piezas importantes para las nuevas
metodologías de diseño. La figura 2.1. muestra la clasificación de los PLDs.
PLDs
Fig. 2.1 Clasificación de los PLDs.
En particular, los dispositivos lógicos programables de alta densidad (HDPLD - Higher Densitv
Programmable Logic frvice), que incluyen a los dispositivos de alta densidad complejos (CPLD
- Complex Programmable Logic Device) y a los arreglos de compuertas programables en campo
(FPGAs - Field Programmable Gate Arrays), pueden ser usados para integrar grandes cantidades
de lógica en un mismo IC. Por otro lado los circuitos integrados de aplicación especifica (ASIC -
Application Specific /ntegrated Circuit) también son usados para la integración de gran cantidad
de lógica, pero los CPLDs y FPGAs presentan la ventaja adicional de una gran flexibilidad de
diseño al permitir ser modificados mediante programación para realizar una tarea especifica y
además son adecuados para desarrollar poco volumen de producto final.
Los fab1icantes de PLDs proveen herramientas CAD que emplean estos lenguajes para el diseño.
la síntesis, simulación y la programación final de sus dispositivos. La gran mayoria de estas
herramientas son especificas para ser usados por dispositivos de determinado fabricante. Entre la
gran cantidad de fabricantes de PLDs Jodemos citar a continuación y por orden alfabético a:
Actel™, Altera™, Atmel™, CypressT , Lattice™ y Xilinx™; en las subsecciones siguientes se
presenta una clasificación de PLDs por la cantidad de lógica y área implementada en ellos, donde
se hará referencia, ha manera de ejemplo, de algunos dispositivos que proveen los fabticantes ya
citados.
35
2.1. DISPOSITIVOS LÓGICOS PROGRAMABLES SIMPLES
La mayoría de los PLOs están constituidos por una matriz de conexiones, una matriz de
compuertas ANO y una matiiz de compuertas OR y algunos otros incluyen registros. Con los
recursos disponibles se implementan las funciones lógicas deseadas mediante un software
especial y un programador de dispositivos. Las matrices pueden ser fijas o programables.
2.1.1. ARREGLO LÓGICO PROGRAMABLE
El dispositivo programable mas simple es el PAL (Programmable Array logic - AITeglo Lógico
Programable). El circuito interno de una PAL consiste en una matriz de conexiones, una matriz
de compuertas ANO y un arreglo de compuertas OR. Una natriz de conexiones es una red de
conductores distribuidos en filas y colwnnas con un fusible en cada punto
Continuar navegando
Materiales relacionados
Compartir