Upload
manolita-pupo
View
212
Download
0
Embed Size (px)
Citation preview
1
Construcción de multiplicadores sobre
campos finitos GF(2m) para el tratamiento de la información
Presenta: Mario Alberto García-MartínezAsesor: Guillermo Morales-Luna
2
Contenido Antecedentes Motivación y planteamiento del problema Soluciones propuestas
El divisor y el multiplicador El exponenciador para GF(2m)
Resultados mas importantes Publicaciones Trabajo inmediato y conclusiones
3
Antecedentes El antecedente principal para este
trabajo es el diseño de un divisor para campos finitos GF(24) que se realizó como tesis para el grado de maestría. Esquemático PLD´s Altera
4
Motivación y planteamiento ...
Las operaciones aritméticas sobre GF(2m) son intensamente usadas en los algoritmos criptográficos, de códigos de corrección de errores y procesamiento digital de señales.
Esto presenta la necesidad de que tales operaciones puedan ser desarrolladas a altas velocidades.
5
Motivación y planteamiento ...
Frente a los desarrollos en software de estos algoritmos, proponemos en este trabajo la implementación en hardware de tales operaciones básicas.
6
Motivación y planteamiento ...
Ejemplo de algunas implementaciones en SW/HW
7
Objetivo principal:
La implementación en lógica reconfigurable de arquitecturas funcionales para las operaciones básicas sobre GF(2m).
8
Operaciones en campos finitos
Aplicación Criptografía Códigos de corrección de
errores
Algoritmos GF(2m) Suma, multiplicación,inversa, división, elevar alcuadrado
Implementación FPGA´s, VLSI
Aquí se ubica principalmentenuestro trabajo
9
Porqué FPGA’s? Su característica de reprogramación
permite: Menor tiempo de desarrollo y
fabricación que un ASIC Muchas facilidades para verificación y
corrección de fallas. Se adaptan muy bien a las
arquitecturas sistólicas.
10
Soluciones propuestas Se ha realizado el diseño de tres
circuitos: Un divisor serial y sistólico de 4 bits
(Descripción VHDL, síntesis, simulación, implementación)
Un multiplicador serial y sistólico de 64 bits
(Descripción VHDL, síntesis, simulación)
11
Estructura del divisor GF(24)
gin= polinomio irreducible
ain= divisor
cin= dividendo
bout= cociente
•Características:
• Estructura serial y sistólica
• Esta formada por tres bloques:
• Gen-Mat: Generador de una matriz
• Delay: Circuito de retardo
• Solución: Soluciona el sistema de ecuaciones representado por la matriz
• Realiza una división en 5m -1 ciclos de reloj
12
Estructura del multiplicador
Características:
* Usa la estructura Gen_Mat
del circuito divisor
* Reduce la operación a un
producto matriz-vector
* Realiza la multiplicación
en un tiempo 3m-1 ciclos
13
Requerimientos de hardware
14
El exponenciador GF(232)
Sea M un elemento arbitrario de GF(2m) expresado como:
y sea e ( 1 e 2m-1) un entero cuya representación binaria es:
imi
iimM
1
0
}1,0{);,,...,,(2 0121
1
0
inn
in
ii eeeeeee
15
El exponenciador GF(232)
Entonces la potencia R= Me modulo el polinomio irreducible G, está también en GF(2m) y, según el método binario, se calcula mediante el siguiente algoritmo:
16
Algoritmo: ( Exponenciación LSB-first )
Input: M, e, G Output: R =Me ( mod G) =================== 1.- C:= M; R:= 1 ; 2.- for i:= 0 to n-1 do 2.a).- if ei := 1 then R:=R*C ( mod G) 2.b).- C:= C*C (mod G) end for ; 3.- return R;
17
Ejemplo: e = 11111010 = 250
18
Arquitectura del exponenciador
Se requieren n multiplicaciones y sn2 ciclos de reloj
19
Descripción VHDL
20
Implementación y resultadosSe ha realizado una implementación inicial de 32 bits en un FPGA Virtex XCV300 de Xilinx:
Layout de conexiones
Layout del uso de CLB´s
21
Resultados
Consumo de recursos del exponenciador de 32 bits
22
Resultados
Requerimientos de hardware y de tiempos para la exponenciación
23
Resultados ...
24
Publicaciones1. Mario Alberto García Martínez, Guillermo Morales Luna y José Antonio Moreno Cadenas. “Procesador de División sobre Campos de Galois en un PLD”. CIE2000. CINVESTAV, IPN. México D.F. Septiembre de 2000.
2. Mario Alberto García Martínez y Guillermo Morales Luna. “Implantación en un Circuito Lógico del procedimiento de Reducción Gaussiana para matrices en Campos Finitos” GF(2m). Congreso de la Sociedad Matemática Mexicana 2000. Saltillo Coahuila. Octubre de 2000
3. Mario Alberto García Martínez y Guillermo Morales Luna. “Estructura Lógica para el procedimiento matricial de Reducción Gaussiana en Campos
Finitos GF(2m)”. CONAGOLFO2000, Instituto Tecnológico de Orizaba. Orizaba Ver. Noviembre de 2000.
4. Mario Alberto García Martínez y Guillermo Morales Luna. “VHDL specification of a FPGA to divide and multiply in GF(2m)”. Sixth International Conference on Finite Fields and Applications. Oaxaca, Oaxaca, México. Mayo de 2001.
25
5. Mario Alberto García Martínez y Guillermo Morales Luna. “VHDL specification of a FPGA to perform division over Galois Fields” . 3er. Encuentro Internacional de Ciencias de la Computación. ENC´01. Aguascalientes, Ags. México. Septiembre de 2001.
6. Mario Alberto García Martínez y Guillermo Morales Luna. “Descripción en VHDL de un multiplicador serial y sistólico para campos de Galois GF(2m)”. VIII International Workshop IberChip 2002. Guadalajara Jal. México. Abril 2002.
7. Mario Alberto García Martínez, Guillermo Morales Luna y Francisco Rodríguez Enríquez. “ Descripción con VHDL de un exponenciador para campos finitos GF(2m)”. IX International Workshop Iberchip 2003. La Habana, Cuba. Marzo 2003.
8. Mario Alberto García Martínez, Guillermo Morales Luna y Francisco Rodríguez Enríquez. “ Hardware Implementation of Binary Method for Exponentiation in GF(2m)”. 4o. Encuentro Internacional de Ciencias de la Computación. ENC´03. Tlaxcala, Tlax. Septiembre de 2003.
Publicaciones
26
Trabajo inmediato y conclusiones
Se ha de concluír el diseño del multiplicador por dígitos durante los próximos dos meses.
Se han escrito ya los dos primeros capítulos de la tesis, cuyo contenido se presenta enseguida.
27
Trabajo inmediato y conc ...
28
Trabajo inmediato y conc ...
29
Trabajo inmediato y conc ...
Esperamos la conclusión del programa doctoral para finales del presente año.