Departamento de Ingeniería Eléctrica

Sección de Computación

Nombre: Karla Paulina Gómez Ávila kpgomez@computacion.cs.cinvestav.mx

Marco Antonio Negrete Cervantes mnegrete@computacion.cs.cinvestav.mx Materia: Aritmética Computacional Profesor: Dr. Francisco Rodríguez Henríquez Propuesta del tema: Comparación del Algoritmo Extendido de Euclides vs. Algoritmo de Fermat-Euler para encontrar Inversos multiplicativos.

Inversión en campos finitos Binarios

Resumen El inverso de un elemento no cero mFa

2∈ es el único elemento mFg

2∈ para el cual se cumple

que mFag2

1∈= , esto es, ).(mod1 fag ≡ Este inverso es denotado como fa mod1− o

simplemente 1−a si la reducción polinomial f es comprendida en el contexto.

En este documento se realizará una comparación entre el algoritmo extendido de Euclides y el algoritmo de Itoh-Tsujii para encontrar los inversos de un elemento en un campo finito binario

mFa2

∈ .

1. Introducción Los grupos y campos son elementos principales del álgebra abstracta (álgebra moderna), una rama de las matemáticas. Los campos finitos tienen gran importancia en criptografía ya que varios algoritmos criptográficos basan su operación sobre aritmética realizada en estos campos. Un campo finito es un sistema algebraico que consiste de un conjunto finito F junto con 2 operaciones binarias, + y *, sobre los elementos de F y que satisface los siguientes axiomas:

1. Los elementos 0 y 1 se encuentran en F. 2. F es un grupo abeliano respecto a la operación +. 3. F \{0} es un grupo abeliano respecto a la operación *. 4. Para todo x, y y z en F, x * (y + z) = (x * y) + (x * z) y x +(y * z) = (x + y) * (x + z).

El orden de un campo finito es el número de elementos en el campo. El campo finito de orden q existe si y solo si q es potencia de un número primo (q = pm, donde p es primo y m es un entero positivo), además, el orden del campo es único. El campo se denota como Fq o GF (q) (la notación GF son las siglas de Galois Field, en honor al matemático que fue el primero en estudiar los campos finitos). Siendo q = pm, p se denomina la característica de GF y m se denomina la extensión de GF. El campo finito mF

2, llamado campo finito binario o de característica 2, puede verse como un

espacio de vectores de dimensión m sobre {0,1}. Para cada mFa2

∈ , existen m elementos

{ }1210 ,,,, −mαααα K en mF2

tal que a puede escribirse de forma única dada por la relación:

∑−

=

•=1

0

m

i

iiaa α donde { }1,0∈ia

El conjunto { }1210 ,,,, −mαααα K se denomina base de mF

2 sobre {0, 1}. Cada elemento α a de

mF2

puede representarse por el vector binario { }1210 ,,,, −mαααα K . Existen diferentes bases de

mF2

sobre 2F . Tres de las bases más comunes para mF2

son: base polinomial, base normal y base

dual. Cada una de estas bases presenta ventajas y desventajas cuando se realiza la implementación de la aritmética sobre los elementos del campo finito (multiplicación, división e inversión principalmente). En base polinomial, sea

∑−

=

+=1

0

)(m

i

ii

mxfxxf

Donde { } )(,1,0 xff i ∈ es un polinomio irreducible de grado m sobre {0, 1} llamado polinomio de

reducción. Para cada polinomio de reducción, existe una representación en base polinomial, en tal representación, cada elemento de mF

2 corresponde a un polinomio binario de grado menor que m

con coeficientes en 2F = {0, 1}. Si mFa2

∈ , existen m números { }1,0∈ia tal que

011

1 axaxaam

m +++= −

− K

El elemento a se denota por la cadena de bits ),,,( 011 aaam K− de longitud m. Las siguientes

operaciones se definen sobre los elementos de mF2

cuando se usa una representación polinomial

con polinomio de reducción f(x).

1. Adición: Sean mFba2

, ∈ con ),,,( 011 aaaa m K−= ),( 011 bbbb m K−=

),( 011 ccccba m K−==+ donde .11, −== miXORbac iii K

2. Multiplicación: Sean mFba

2, ∈ con ),,,( 011 aaaa m K−= ),( 011 bbbb m K−=

),( 011 ccccba m K−==• donde ∑−

=

=1

0

)(m

i

ii xcxc es el residuo de la división del polinomio

∑∑

−

=

−

=

1

0

1

0

m

i

ii

m

i

ii xbxa entre el polinomio f(x).

Los polinomios irreducibles f(x) pueden ser un trinomio de la forma 1++ kmxx o un pentanomio

de la forma 1++++ cbamtttx donde m, k, a, b y c son enteros positivos. Cuando f(x) es un

trinomio, la reducción modulo f(x) se realiza eficientemente tanto en software como en hardware.

Una base normal para mF2

sobre {0, 1} es una base de la forma { },,,, 122 −mβββ K donde

.2mF∈β Para un m dado, la base normal siempre existe. Cada elemento a de mF

2 puede escribirse

como

∑−

=

=1

0

2m

i

i

iaa β Donde { }1,0∈ia

La aritmética en campos binarios es principalmente aplicada en el desarrollo de curvas elípticas. Una curva elíptica es un conjunto de pares ordenados que cumplen una relación. Esta relación se define sobre elementos de un campo finito. En cuestiones de criptografía, los campos finitos sobre los que se definen las curvas elípticas son dos: el campo de los números primos GF (p) y el campo de las cadenas de m bits GF (2

m). En ambos casos, las operaciones de adición y multiplicación

terminan siempre con reducción módulo p (Fp) o m (F2m).

La característica importante de las curvas elípticas es que cuando se definen sobre los campos GF(p) o GF(2

m), el conjunto de puntos que conforman a tal curva elíptica forman un grupo abeliano

sobre la operación de suma. Con esto, cualquier operación que se realice entre los puntos de la curva, siempre resultará en otro punto de la curva elíptica. Otra característica importante de las curvas elípticas es que el problema del logaritmo discreto definido sobre los puntos de la curva elíptica es intratable, es decir, el mejor algoritmo conocido para resolver el problema del logaritmo discreto de curva elíptica es de complejidad exponencial. El problema del logaritmo discreto de curva elíptica consiste en encontrar el valor del número entero k tal que dados dos puntos cualquiera P, Q de la curva elíptica, la relación P = kQ se cumple siempre que k existe (k y el orden de Q son números suficientemente grandes). En este problema se basa la seguridad de los criptosistemas de curva elíptica. El mérito que tienen los criptosistemas de curvas elípticas (Elliptic Curve Cryptosystems � ECC) es que, comparado con el criptosistema de llave pública más usado, el RSA, ECC puede proveer el mismo nivel de seguridad con una longitud de llave más pequeña, con una reducción en el tamaño de la llave de 7:1. Con una llave pequeña, las operaciones criptográficas, como la firma digital, puede realizarse más rápido. El uso de llaves pequeñas implica mayor velocidad, y menores necesidades de memoria y de poder de cómputo para la implementación de los algoritmos correspondientes a este esquema. El tiempo para la transmisión y el espacio para almacenamiento de las llaves también se reducen en un factor de 7. Estas características son atractivas especialmente para aplicaciones en dispositivos móviles, los cuales cuentas con modestos recursos computacionales. Un algoritmo criptográfico que opere sobre puntos de una curva elíptica (ECDSA) puede tener el mismo nivel de seguridad que un algoritmo criptográfico que opere sobre enteros grandes (DSA) usando mucho menos bits. 2. Descripción de los algoritmos propuestos

• Algoritmo Extendido de Euclides para polinomios

Se tiene dos polinomios binarios a y b, ambos diferentes de cero. El maximo común divisor (gcd,

greatest common divisor) de a y b, denotado por gcd (a, b), es el polinomio binario d del grado más alto que divide ambos polinomios a y b. Los algoritmos eficientes para el cálculo del gcd(a, b) se basan en el siguiente teorema. Teorema 1. Se tiene dos polinomios binarios a y b. Entonces ),gcd(),gcd( acabba −= para cualquier polinomio binario c. En el Algoritmo de Euclides clásico para el cálculo del gcd de dos polinomios binarios a y b, cuando el ),()( agradobgrado ≥ b es divido por a para obtener un cociente q y un residuo r, que

satisfacen la ecuación rqab += y ).()( agradorgrado p Por el Teorema 1, el

).,gcd(),gcd( arba = Así, el problema de determinar el ),gcd( ba es reducido a calcular

),gcd( ar donde los argumentos ),( ar tienen un grado menor que el grado de los argumentos

originales ).,( ba Este proceso es repetido hasta que uno de los argumentos es cero, el resultado

obtenido inmediatamente de .),0gcd( dd = El algoritmo debe terminar cuando el grado de los residuos disminuya considerablemente. Por otro lado, este algoritmo es eficiente porque el número de divisiones largas es a lo mas k, donde k=grado(a).

En una variante del Algoritmo clásico de Euclides, solamente un paso en cada división larga es modificado. Esto es, si el )()( agradobgrado ≥ y ),()( agradobgradoj −= entonces se calcula

.azbrj+= Por el Teorema 1, ).,gcd(),gcd( arba = Este proceso es repetido hasta encontrar un

residuo igual a cero. Si el )()( bgradorgrado p , el número de divisiones parciales es a lo más k,

en donde { }.)(),(max bgradoagradok = El algoritmo de euclides puede ser extendido para encontrar polinomios binarios g y h que satisfagan la ecuación dbhag =+ donde ).,gcd( bad = En el algoritmo 1 se mantienen fijas

vbhag

ubhag

=+

=+

22

11

El algoritmo termina cuando u=0, con lo cual ),gcd( bav = y .22 dbhag =+ Algoritmo 1. Euclides extendido para polinomios binarios

Entrada: Dos polinomios binarios no-cero a y b, donde )()( bgradoagrado ≤

Salida: ),gcd( bad = y dos polinomios binarios g y h que satisfacen la ecuación .dbhag =+

Supóngase ahora que f es un polinomio binario irreducible de grado m y un polinomio no-cero a tiene grado m-1 (por lo tanto 1),gcd( =fa ). Si el Algoritmo 1 es ejecutado con las entradas a y f, el último cociente u no-cero es encontrado en el paso 3.3 y es u=1. Después de que esto ocurra, los polinomios 1g y 1h , son actualizados en el paso 3.4, y satisfacen la ecuación .111 =+ fhag Por lo

tanto ( )fag mod11 ≡ y .11 ga =− Nótese que 1h y 2h no se necesitan para determinar 1g .

Esta observación es implementada en el Algoritmo 2 para realizar inversos en un campo mF

2.

Algoritmo 2. Inversos en mF

2 usando el Algoritmo de Euclides extendido

Entrada: Un polinomio binario no-cero a de grado m-1.

Salida: fa mod1−

En el algoritmo 2 los bits de los polinomios binarios u y v son reducidos de izquierda a derecha, esto se modifica para el algoritmo 3, en donde los bits son reducidos de derecha a izquierda. Algoritmo 3. Algoritmo binario para Inversos en mF

2

Entrada: Un polinomio binario no-cero a de grado m-1.

Salida: fa mod1−

Este algoritmo fue implementado para un FPGA debido a que los cálculos involucrados con el grado de los polinomios en el paso 3.3 se reducen a una comparación simple de la representación binaria de los polinomios, esto difiere en el algoritmo 2 en donde si se requiere un calculo explicito de los grados de los polinomios en el paso 3.1.

• Algoritmo Itoh-Tsujii

El algoritmo usado para la inversión esta basado en la identidad del Teorema Petit de Fermat:

( )212221 1 −−− −

==nn

aaa Itoh y Tsujii propusieron un método que minimiza el número de multiplicadores para calcular las inversiones el cual esta basado en las siguientes identidades:

impara

paraa

a

a

n

n

n

n

n

,

.

12

2

2

12

12

12 2

1

2

1

2

1

2

1

1 −

−

−

−

−

−

−

−

−

•

=

El algoritmo Itoh-Tsujii calcula los inversos ( 12 1−−n

a ) de los elementos en el campo usando arreglos recursivos de operaciones en campos finitos. Para el desarrollo del algoritmo se tiene una α que es un elemento no-cero arbitrario en el campo

).2( mGF Entonces, se define ),2( m

k GF∈β donde k es un entero positivo, y se obtiene:

12 −=k

k αβ

Los k-bit de α serán representados en su expansión binaria, y se considera como el número positivo m-1, la expansión es representada de la siguiente manera:

tt llllm 22221 121 ++++=− −K

Donde 1121 −=<<<< − kllll ttK .

Entonces el inverso multiplicativo de ,α representado por ( ),21 mGF∈−α se puede representar por:

( )212221 1 −−− −

==mm

ααα Aplicando las identidades antes propuestas se obtiene:

( ) ( ) ( ) 1222

122

2

1

1−−− ===

−

− αααβmm

m

De estas definiciones se obtiene el algoritmo propuesto por Itoh-Tsujii Algoritmo 4. Algoritmo binario para Inversos en mF

2 propuesto por Itoh-Tsujii

Entrada: Un polinomio binario no-cero )2( mGF∈α y una cadena de adición U de longitud t para m-1.

Salida: fa mod1−

Este algoritmo fue implementado en un FPGA para el cálculo de inversos en polinomios de grado

193, la generación de coeficientes para el polinomio irreducible 115193 ++ xx con el algoritmo Itoh-Tsujii es desarrollado en la siguiente tabla:

Tabla 1. Generación de coeficientes para polinomios de grado 193

2. Implementación en Maple

Las pruebas de estos algoritmos fueron implementadas en Maple, usando la librería GF para polinomios en campos binarios mF

2.

• Algoritmo Extendido de Euclides

> P:=x^193+x^15+1; N:=193;

GField:=GF(2,N,P);

Para poder realizar las operaciones necesarias con el polinomio irreducible, este primero se tuvo que transformar en un número binario para posteriormente convertirlo en un polinomio en el campo mGF

2.

Representación binaria y decimal del polinomio irreducible: > v:=convert('

1000000000000000000000000000000000000000000000000000000000000

0000000000000000000000000000000000000000000000000000000000000

0000000000000000000000000000000000000000000000000000000010000

00000000001', decimal, binary);

v :=12554203470773361527671578846415332832204710888928069058561

Representación del polinomio irreducible en el campo GField ya definido > F_poli:=GField[input](v);

F_poli := (x193C x15

C 1 ) mod 2

Los resultados arrojados por la herramienta fueron los siguientes: > :=193; a:=rand((2)^(m))();

a_Polinomio:=GField[input](a);

a_hex:=convert(a,hex);

a_inv_Polinomio:=GField[inverse](a_Polinomio);

a_inv:=GField[output](a_inv_Polinomio);

a_inv_hex:=convert(a_inv, hex);

Prueba:=GField[`*`](a_Polinomio,a_inv_Polinomio);

m := 193

a :=850402938909406019117742474331295778851989411175813283845

a_Polinomio := (x189C x185

C x183C x181

C x179C x178

C x177

C x175C x172

C x171C x170

C x169C x167

C x166C x165

C x164C x162

C x161C x159

C x158C x157

C x154C x153

C x152C x151

C x150C x149

C x144C x143

C x142C x141

C x140C x139

C x137C x135

C x134C x133

C x131C x130

C x129C x127

C x126C x124

C x122C x120

C x119C x118

C x113C x112

C x108C x107

C x106C x105

C x104C x102

C x101C x100

C x99C x96

C x93C x87

C x81C x77

C x76

C x74C x72

C x69C x67

C x66C x63

C x62C x61

C x60

C x59C x50

C x49C x48

C x47C x45

C x44C x42

C x41

C x40C x39

C x38C x36

C x35C x34

C x33C x32

C x31

C x30C x29

C x27C x24

C x23C x22

C x20C x17

C x16

C x2C 1 ) mod 2

a_hex :=22AE9EF6E7E1FAEED5C31F792082352CF807B7DFE9D

30005

a_inv_Polinomio := (x192C x191

C x190C x188

C x186C x183

C x182C x176

C x175C x174

C x172C x171

C x169C x168

C x167C x164

C x162C x160

C x156C x155

C x153C x150

C x144C x141

C x140C x137

C x132C x128

C x126C x124

C x117C x114

C x113C x112

C x111C x110

C x108C x105

C x103C x101

C x98C x97

C x96C x95

C x94C x92

C x91

C x90C x89

C x88C x87

C x83C x80

C x79C x76

C x73

C x72C x70

C x68C x67

C x63C x62

C x61C x60

C x59

C x58C x54

C x52C x51

C x49C x46

C x45C x39

C x36

C x35C x34

C x32C x31

C x30C x25

C x18C x14

C x10

C x6C x4

C x2 ) mod 2

a_inv :=11493894493006897507771957239701142535164284825909919499348

a_inv_hex :=1D4C1DB951A4132115027D2A7DF899358FC5A609DC20

44454

Prueba := 1 mod 2

Los resultados arrojados por el algoritmo creado fueron: > inverso_polinomio:=aia(a); inverso:=GField[output](inverso_polinomio);

inverso_hex:=convert(inverso,hex);

Prueba2:=GField[`*`](a_Polinomio,inverso_polinomio);

inverso_polinomio := (x192C x191

C x190C x188

C x186C x183

C x182C x176

C x175C x174

C x172C x171

C x169C x168

C x167C x164

C x162C x160

C x156C x155

C x153C x150

C x144C x141

C x140C x137

C x132C x128

C x126C x124

C x117C x114

C x113C x112

C x111C x110

C x108C x105

C x103C x101

C x98C x97

C x96C x95

C x94C x92

C x91

C x90C x89

C x88C x87

C x83C x80

C x79C x76

C x73

C x72C x70

C x68C x67

C x63C x62

C x61C x60

C x59

C x58C x54

C x52C x51

C x49C x46

C x45C x39

C x36

C x35C x34

C x32C x31

C x30C x25

C x18C x14

C x10

C x6C x4

C x2 ) mod 2

inverso :=11493894493006897507771957239701142535164284825909919499348

inverso_hex :=1D4C1DB951A4132115027D2A7DF899358FC5A609DC20

44454

Prueba2 := 1 mod 2

Como se puede observar los resultados son iguales tanto de la herramienta como del algoritmo implementado para calcular inversos en campos mGF

2.

El código del algoritmo se encuentra en el archivo anexo “AEE_final.mws”.

• Algoritmo Itoh-Tsujii El programa desarrollado fue: > iit:=proc(a)

local B,U,i,BF,l, k2,k;

B:=Array(1..9);

U:=[1,2,3,6,12,24,48,96,192];

i:=[1,2,3,4,5,6,7,8,9];

B[1]:=a;

for k from 2 to 9 do

l:=U[k]-U[k-1];

k2:=1;

while U[k2]<>l do

k2:=k2+1;

end do;

B[k]:= (B[k-1]^(2^l))*B[k2];

end do;

BF:=(B[9])^(2);

return BF;

end proc; En el algoritmo se desarrollan los índices de β como ]1[][ −− iUiU , para esto se usaron dos arreglos que van comparando cada uno de los elementos del arreglo U que representa la cadena de adición con un arreglo i que presenta el índice en el que se encuentra el valor de

]1[][ −− iUiU .

Se tuvieron problemas con la implementación en Maple para este algoritmo, ya que provoca errores de sobre flujo en los arreglos utilizados. > iit(a); Error, (in iit) numeric exception: overflow 3. Implementación en Xilinx.

• Algoritmo Extendido de Euclides

Una vez que el algoritmo ha sido implementado y probado en Maple, comienza la implementación en Hardware, esta implementación es económica debido a que el lenguaje VHDL es un lenguaje descriptor de hardware, con esta característica y el trabajo de aritmética binaria el uso de los recursos de la tarjeta se minimiza produciendo un diseño simple y que puede ser transferido a cualquier tarjeta. Selección de la tarjeta para la Implementación. Al ser un diseño simple, debido al trabajo de aritmética binaria y al nulo empleo de componentes adicionales (Componentes Core Generator), es posible implementarlo en casi cualquier tarjeta, aunque es deseable hacer un uso eficiente de los recursos, por lo que la selección para el diseño es utilizar la Tarjeta Spartan2 XC2S200 de Xilinx. Operaciones en Aritmética Binaria.

El lenguaje y los métodos que existen en VHDL están pensados en aritmética entera, en la que los acarreos entre dígitos están presentes y son considerados en las operaciones, mientras que en aritmética binaria esto no existen. Con esto es necesario implementar de funciones o modificar las existentes para realizar las operaciones básicas. Multiplicaciones y Divisiones por 2 en Aritmética Binaria. Un package en VHDL es un tipo de archivo que contiene subprogramas, funciones, procedimientos, definiciones de constantes y tipos de datos, que pueden ser utilizados por cualquier unidad de diseño de VHDL. Mediante un package denominado Corrimientos se implementaron las operaciones de multiplicación y división por 2. La multiplicación y división por 2 en aritmética binaria se reducen simplemente a corrimientos a la izquierda y a la derecha respectivamente, esto debido a que la base de la aritmética, y que al efectuar corrimientos e insertar ceros es posible hacer las operaciones con un factor de dos, ya sea multiplicación (inserción de ceros a la derecha) o división (inserción de ceros a la izquierda). Esto al trabajar mediante los tipos de datos que nos proporciona VHDL nos resulta fácil y muy barata la implementación en Hardware. Este paquete consta de dos funciones, corrimientos a la derecha y corrimientos a la izquierda.

Corrimientos a la Izquierda. Como ya se menciono esta función permite hacer una multiplicación por dos en aritmética binaria, la implementación de esta función se basa únicamente en la reasignación cíclica de los valores del vector que se recibe. La declaración de la función es:

FUNCTION shift_left (dato: IN std_logic_vector; cuenta: IN INTEGER)RETURN std_logic_vector ; La función recibe como parámetros de entrada un vector de bits (asignado a dato), es decir el polinomio al que le tiene que realizar corrimientos y en “cuenta” recibe el número de corrimientos que se le tienen que realizar a “dato”. Como parámetro de regreso es enviado el polinomio con los corrimientos a la izquierda. La función trabaja en base a reasignaciones del polinomio “dato”, esto es toma el vector y lo reasigna al mismo vector con una variación de índice en un lugar, y al elemento 0 que no fue reasignado, es donde se le inserta un cero. Esto es:

dato(an-1 downto 0) dato(an-1 downto 0) 0 an an-1 … a1 a0 an an-1 … a1 a0

Corrimientos a la Derecha. Esta función nos permite hacer la división por dos en aritmética binaria, el funcionamiento de esta al igual que en el caso anterior se basa en reasignaciones de los valores de los vectores. La declaración es:

FUNCTION shift_right (dato: IN std_logic_vector; cuenta: IN INTEGER)RETURN std_logic_vector ; La función recibe como parámetros de entrada un vector de bits (asignado a dato), es decir el polinomio al que le tiene que realizar corrimientos y en “cuenta” recibe el número de corrimientos que se le tienen que realizar a “dato”. Como parámetro de regreso es enviado el polinomio con los corrimientos a la derecha indicados en “cuenta”. La función trabaja en base a reasignaciones del polinomio “dato”, esto es toma el vector y lo reasigna al mismo vector con una variación de índice en un lugar a la derecha, y al elemento “n” que no fue reasignado, es donde se le inserta un cero. Esto es:

dato(an downto a1) 0 dato(an downto a1) an an-1 … a1 a0 an an-1 … a1 a0

Detección de Paridad. Para el algoritmo desarrollado, es necesario probar que un vector es divisible por otro, es decir probar un modulo que de valor de cero. Al igual que las operaciones mencionadas anteriormente, no existe implementado el módulo para aritmética binaria, por lo que el análisis de la estructura de los vectores, será de gran utilidad para la implementación del módulo en aritmética binaria. Cada polinomio (std_logic_vector) tiene la siguiente estructura:

n2 12 −n … 12 02 an an-1 … a1 a0

Todos los valores que puede tomar cada uno de los coeficientes en decimal, desde 12 a n2 tienen valores pares, debido a que son potencias de dos, por lo que cualquier combinación que pudieran tener estos números será un número divisible por dos en decimal. El bit a0 es el que da la paridad al polinomio, debido a que este valor es 02 = 1, por lo que el valor de este bit hará que el vector oscile entre paridad par e impar, por lo que este bit es el que fácilmente nos puede dar el valor del modulo 2 del vector (indica si es divisible por 2).

Valor del Bit a0 Condición del Polinomio

0 Par (Divisible por 2) 1 Impar (No Divisible por 2)

Resultados de Simulación.

• Algoritmo Itoh-Tsujii El algoritmo de Itoh-Tsujii es un algoritmo que al trasladarlo a hardware consume una gran cantidad de recursos. Para la implementación de este algoritmo se eligió la tarjeta Virtex 2 xc2v4000-6bf957 debido a la cantidad de entradas y salidas requeridas. El diseño que fue creado tiene varios módulos que están organizados de manera jerárquica, en los siguientes apartados se describirán los distintos módulos que se incluyen en el diseño. Módulo Principal. En el módulo principal en jerarquía es en donde se implementa el algoritmo de Itoh-Tsujii para el cálculo de Inversos Modulares, es en esta parte en donde se realizan todas las funciones de sintetización y simulación. Los módulos que integran la parte principal se utilizan en forma de componentes, por lo que al hacer más de una instanciación a un mismo componente implicará que este se va a crear el número de veces que se haya hecho la instanciación. Los módulos en los que se divide la aplicación principal son: La maquina de estados, el multiplicador Karatsuba y la Tira de Cuadrados. Máquina de Estados. El lenguaje descriptor de Hardware (VHDL) es de naturaleza concurrente, con esta característica la implementación de instrucciones secuenciales no se encuentra definida como en otros lenguajes. Para la ejecución de este tipo de instrucciones existen el VHDL los procesos (la palabra reservada es “process”), estos soportan las instrucciones secuenciales de forma transparente pero una gran desventaja que tienen es que no soportan componentes y además en el caso de ciclos en cada iteración se genera toda la circuitería necesaria, haciendo con esto los ciclos muy costosos en área. La implementación del presente algoritmo de inversión hace necesaria la utilización de un ciclo, por lo que el problema planteado se acentúa. El uso de máquinas de estado fue la técnica empleada para resolver este problema, en este tipo de programación solamente se declara una vez los componentes y en base a cambios en señales y la máquina de estados, se implementa el ciclo. Como en cada iteración del ciclo los componentes requieren distintos parámetros entonces se decidió definir un estado para cada iteración del ciclo. En cada uno de los estados se hace la asignación necesaria para obtener el valor adecuado de la tira de cuadrados y además también las necesarias para el multiplicador Karatsuba. Con esto en cada ciclo de reloj va a ir ejecutando secuencialmente cada uno de los estados de la máquina y realizando la operación de la tira de cuadrados y el multiplicador Karatsuba, por lo que el ciclo necesario se cubre de esta forma, sin hacer uso de hardware en exceso. La implementación de la máquina de estados se hizo mediante dos procesos. El primero de ellos se encarga de cambiar el parámetro de “estado presente”, este definirá el estado de la máquina que se va a ejecutar. El segundo proceso hará con la comparación del parámetro “estado presente” la asignación de las señales, es decir el primer proceso hará el papel del proceso que aumentará la variable contador del ciclo y el segundo actuará como el ciclo en si. Así entonces la ejecución del algoritmo será la ejecución de un estado de la máquina y un paso del algoritmo secuencialmente hasta cubrir todos los estados de la máquina.

Cabe mencionar que VHDL hace una codificación de cada uno de los estados, el tipo de procedimiento que utiliza Xilinx para este fin es la conocida como OneHot, así a continuación se muestra como codifica la máquina de estados la herramienta de síntesis.

Figura. Codificación OneHot para la Máquina de estado.

Multiplicador Karatsuba. Al tomar como módulo base 193, el proceso para multiplicar en Aritmética binaria necesita modificaciones a la forma tradicional en la que se estructura un multiplicador Karatsuba. De forma ordinaria se llega hasta un multiplicador de 128 bits. Para subir a un nivel de 193 bits, se decidió dividir en un Karatsuba de 128 bits y hacer circuiteria para emplear un multiplicador de 64 bits, un multiplicador clásico de 64 bits x 1 bit y un multiplicador de 1 bit x 1 bit. El multiplicador Karatsuba de 64 bits se encuentra ya implementado para el similar de 128 bits. Otro de los elementos que integran el multiplicador de 193 bits, es el multiplicador de 64 bits x 1 bit, en este no es necesario realizar la multiplicación bit a bit, sino que se puede visualizar en hardware como un multiplexor, debido a que dependiendo el valor del parámetro de un bit, el resultado arrojado por el multiplicador es el vector de 64 bits que entro, o un vector de 64 bits de valor cero. Para la implementación de este multiplexor había dos caminos, el primero hacerlo mediante un componente de “Core Generador” o bien hacerlo mediante una asignación condicionada del vector de salida en función del valor del parámetro de 1 bit. Finalmente el multiplicador de 1 bit x 1 bit, es simplemente una compuerta AND. La jerarquía del multiplicador Karatsuba desbalanceado de 193 bits, se muestra en la siguiente figura:

Figura. Diagrama de Jerarquía del Multiplicador Karatsuba

Tiras de Cuadrados. El diseño requiere de elevar un polinomio a distintas potencias, dependiendo del paso de la cadena de adición que se este realizando. Estas potencias todas tienen base dos, por lo que pueden ser expresadas como cuadrados. En este módulo se obtienen los valores de los cuadrados del parámetro de entrada en una tira. En cada paso de la tira es posible obtener valores intermedios, cuando no sea requerido encontrar todos los valores. Adicionalmente todos los valores calculados son reducidos al mismo tiempo que son calculados. En la siguiente figura se muestra un diagrama a bloques de la estructura funcional del módulo.

Figura . Diagrama del Módulo.

Es posible apreciar en la figura que se recibe una entrada “A” y esta pasa a través de la tira de cuadrados, elevando en cada segmento su valor al cuadrado y a la salida de cada uno de estos es posible leer su valor. Este bloque es útil en la implementación para el cálculo de todas las potencias de β ’s que son necesarias. En el funcionamiento de este módulo en cada paso se efectúa la reducción modular, para que en cada pasada se tengan vectores de la misma longitud, esta reducción se efectúa de acuerdo a los criterios establecidos para el manejo de trinomios. Las operaciones en VHDL para este módulo consisten en operaciones booleanas tales como XOR y AND, esto debido a que en aritmética binaria no se consideran acarreos, lo cual simplifica la programación orientada a hardware.

Resultados de Simulación.

Comparación de Resultados de Algoritmos de Inversión. En la siguiente tabla se muestran los resultados comparativos de los algoritmos implementados en el presente reporte:

Valores Obtenidos en el proceso de Síntesis para el Algoritmo de Euclides.

Valores Obtenidos en el proceso de Síntesis para el Algoritmo de Itoh-Tsujii.

Algoritmo Slices Utilizados Periodo [ns] Razón Tiempo/ Area Binario de Euclides 1020 119.107 0.008235 Fermat (Itoh-Tsujii) 11763 63.787 0.001335

Conclusiones La mayoría de los productos y estándares que usan criptografía de asimétrica para cifrado y firmas digitales usan RSA. Aun existen escepticismo de matemáticos y científicos alrededor de la aplicación de ECC, el consenso es que aun existe incredibilidad del nivel de seguridad que ECC ofrece con longitudes de llave pequeñas, muchas pruebas deberían realizarse antes de emplear ECC en aplicaciones grandes. Sin embargo, varias organizaciones para estándares internacionales como IEEE, ANSI e ISO están realizando trabajo para hacer de ECC una alternativa viable comercialmente a las necesidades de criptografía asimétrica. Actualmente se esta realizando investigación alrededor de ECC, principalmente orientándose a la implementación de distintas aplicaciones en dispositivos de hardware reconfigurable, ya que la ganancia obtenida en recursos sobre velocidad es mayor en comparación con la ganancia obtenida en software. El algoritmo binario extendido de Euclides resulta un algoritmo que su implementación en hardware es muy sencilla. Las operaciones y comparaciones que se tienen que realizar se reducen a operaciones booleanas básicas y corrimientos. Con esta lógica la implementación en un FPGA es de un costo en área muy baja debido a que es gran cantidad de alambrado y muy poca lógica combinatoria y secuencial. Con esto es posible implementar esto casi en cualquier tarjeta a pesar de que tenga recursos limitados, la limitante de este diseño tan simple es que en tiempo no es tan óptima. El algoritmo de Itoh-Tsujii que permite obtener el inverso por el teorema de Fermat es un algoritmo que en área resulta costoso y es que como indica el teorema se tienen que hacer una serie de potencias, hasta que en determinado punto se obtiene el inverso, las operaciones que hay que realizar son costosas en área, pero su costo en tiempo resulta bueno, esto es debido a que son pocos los pasos que se tienen que hacer para encontrar la solución, esto depende de la cadena de adición que se seleccione. La implementación de ambos algoritmos en un lenguaje descriptor de hardware resulto un poco complicada debido a la naturaleza no secuencial del lenguaje, la optimización de los diseños depende de la forma en la que se piensen los diseños, un diseño que se concibe en una forma secuencial no será un diseño optimo en hardware mientras que un diseño que se piense y diseñe para su ejecución concurrente y se aprovechen las ventajas del paralelismo, entonces resultara un buen diseño tanto en área como en tiempo. De acuerdo a los resultados obtenidos vemos que el algoritmo de Euclides representa una mejor opción, debido a que a pesar de que su respuesta en tiempo es del doble del algoritmo de Itoh-Tsujii, en cuestión de área ocupa un 10% de lo que ocupa el ultimo algoritmo mencionado, por lo que al hacer una valoración de estos factores, es posible afirmar que no resulta tan significativo lo que se pierde en tiempo con el algoritmo de Euclides, en comparación de lo que se tendría que pagar en área con el algoritmo de Itoh-Tsujii para obtener un ahorro de la mitad de tiempo.

Referencias Bibliográficas.

http://www.springeronline.com/sgw/cda/pageitems/document/cda_downlohttp://www.springeronline.com/sgw/cda/pageitems/document/cda_downlohttp://www.springeronline.com/sgw/cda/pageitems/document/cda_downlohttp://www.springeronline.com/sgw/cda/pageitems/document/cda_downloaddocument/0,11996,addocument/0,11996,addocument/0,11996,addocument/0,11996,0000----0000----45454545----110359110359110359110359----0,00.pdf0,00.pdf0,00.pdf0,00.pdf

http://delta.cs.cinvestav.mx/~francisco/arith/hankerson00software.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/hankerson00software.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/hankerson00software.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/hankerson00software.pdf

http://delta.cs.cinvestav.mx/~francisco/arith/FPL2004_Inverse.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/FPL2004_Inverse.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/FPL2004_Inverse.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/FPL2004_Inverse.pdf http://delta.cs.cinvestav.mx/~francisco/arith/irv03.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/irv03.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/irv03.pdfhttp://delta.cs.cinvestav.mx/~francisco/arith/irv03.pdf