e Softwar - repository.udistrital.edu.corepository.udistrital.edu.co/bitstream/11349/2767/1... · o...

Análisis de Desempeño del Algoritmo Criptográ� o

PRESENT usando Plataformas Embebidas Hardware y

Software

Edwar Ja into Gómez

Universidad Distrital Fran is o José de Caldas

Fa ultad de Ingeniería

Bogotá, D.C.

Agosto 2015

Análisis de Desempeño del Algoritmo Criptográ� o

PRESENT usando Plataformas Embebidas Hardware y

Software

Edwar Ja into Gómez

Trabajo de tesis para optar al título de

Magister en Cien ias de la Informa ión y las Comuni a iones

Dire tor

Fredy H. Martínez S., Ph.D.( )

Codire tor

César A. Hernández S., Ph. D. ( )

Universidad Distrital Fran is o José de Caldas

Fa ultad de Ingeniería

Bogotá, D.C.

Agosto 2015

Título en español

Análisis de Desempeño del Algoritmo Criptográ� o PRESENT usando Plataformas Em-

bebidas Hardware y Software

Title in English

Performan e Analysis of Cryptographi Algorithm PRESENT using Embedded Hardware

and Software Platforms

Resumen: La riptografía moderna bus a garantizar la on�den ialidad de la informa ión

y prevenir que personas no autorizadas tengan a eso a ella. Estos prin ipios se pueden

apli ar en dispositivos portátiles que requieren proteger la informa ión alma enada y pro-

esada. Este tipo de apli a iones requieren iertos ompromisos de diseño, que se logran

usando hardware de alto desempeño y la implementa ión de algoritmos ligeros, tipo "light-

weight", el ual sera trabajado en esta tesis, el algoritmo Present ; el algoritmo Present es

un esquema ligero de ifrado por bloques relativamente nuevo, no vulnerado a la fe ha y

on ara terísti as que lo ha en interesante para una implementa ión en hardware y soft-

ware embebido. Este trabajo presenta el estudio, diseño, implementa ión y pruebas de este

algoritmo de ifrado, donde se muestran los on eptos teóri os, se analizan las métri as

para sus diferentes implementa iones, a �n de identi� ar las fortalezas de ada tipo de

implementa ión embebida

Abstra t: Modern ryptography is strongly in�uen ed by prin iples of se urity, and is

widely used in portable devi es that require some level of priva y. These design ompro-

mises are a hieved not only by the use of high-performan e hardware, whi h has been the

urrent natural tenden y, but also for the implementation of lightweight high performan e

algorithms, su h as the Present algorithm. The Present algorithm is a lightweight blo k

en ryption s heme relatively new, not infringed to date, and with features that make it

interesting for implementation in embedded hardware and software. This work presents the

study, design, implementation and testing of this ipher algorithm, where the theoreti al

on epts are shown, and metri s for di�erent implementations to identify the strengths of

ea h type of embedded implementation are dis ussed.

Palabras lave: Cryptología , Hardware embebido, software embebido, ifrador por blo-

que, Criptogra�a Liviana "lightweight".

Contribu iones originales: El prin ipal aporte de la investiga ión es la implementa ión

real de un ifrador por bloque estandar no vulnerado. Esta implementa ión se soporta en

la apropia ión de la aritméti a apli ada de ampos �nitos, así omo el ono imiento de la

arquite tura de los dispositivos sobre los uales se realiza la implementa ión. Se logra una

implementa ión en hardware que redu e en un 26% los requisitos de hardware (respe to a

la implementa ión de referen ia). Además de esto, se logró una implementa ión estándar en

C que fue probada e implementada en un omputador personal y sobre mi ro ontroladores

de distinto tamaño, logrando resultados inéditos de alto throughput en un mi ro ontrola-

dor de 32 bits.

Claims: The main ontribution of the resear h is the a tual implementation of a stan-

dard blo k ipher not infringed. This implementation is supported in the appropriation of

arithmeti applied of �nite �elds, as well as knowledge of the ar hite ture of the devi es on

whi h the deployment is performed. A hardware implementation is obtained to redu e in

signi� ant per entage the hardware requirements (taken with respe t to the referen e) is

a hieved. Besides this, a standard implementation in C was tested and implemented on a

personal omputer and mi ro ontrollers of di�erent sizes, a hieving an unpre edented high

throughput implementation of a 32 bit mi ro ontroller

Nota de a epta ión

Jurado

Prof. Elvis Eduardo Gaona Gar ia

Jurado

Prof. Roberto Ferro Es obar

Dire tor

Prof. Fredy H. Martínez S.

Codire tor

Prof. César A. Hernández S.

Bogotá, D.C., Agosto de 2015

Dedi ado a

En primera medida y omo mayor apoyo durante toda mi vida, tanto a adémi a omo

personal y omo la úni a persona que ha estado a mi lado en todas las etapas de mi

vida, agradez o profundamente a mi madre por darme la vida y por su in ondi ional

e in ansable amor y apoyo, sin di hos sentimientos no hubiera sido apaz de �nalizar mis

estudios, ni mu has otras metas en mi vida.

Además agradez o en primera medida a las personas que sembraron en mí la semilla y

la uriosidad ne esaria para trabajar en sistemas riptográ� os y en general en riptología,

los uales admiro mu ho, por su trabajo en el tema y sus ono imientos en matemáti a

dis reta apli ada, los ingenieros de la Universidad de los Llanos Javier Fernando Castaño

y Fabián Velázquez Clavijo.

Por otro lado quiero manifestar mi profunda admira ión y respeto por el ingeniero Cesar

Hernández Suarez, quien ini ialmente era mi dire tor pero por motivos a adémi os se ha

onvertido en un apoyo externo a este trabajo y on su profundo ono imiento aportado

en gran medida a la realiza ión del mismo.

El sentimiento de agrade imiento se extendería a mu has personas que me han rodeado

en mi vida a adémi a y profesional, pero en este momento quiero resaltar el apoyo y voz de

aliento de mis amigos y ompañeros de trabajo Fernando Martínez Santa, Andrés Javier

Torres y Holman Montiel Ariza.

Un agrade imiento espe ial al profesor Carlos Suarez, por olo ar toda su experien ia

a adémi a e investigativa en este trabajo, además por olo ar su gran alidad humana al

servi io de la omunidad a adémi a de la maestría.

Por último, quiero expresar mi profundo sentimiento de gratitud a mi dire tor el inge-

niero Fredy Hernán Martínez Sarmiento, que on su gran sabiduría, guía y sin su apoyo e

in�nita pa ien ia, no se hubiera llevado a buen término este trabajo.

Índi e general

Índi e general I

Índi e de tablas III

Índi e de �guras IV

Introdu ión V

1. Fundamenta ión matemáti a y estado del arte 1

1.1. Fundamenta ión matemáti a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1. Aritméti a en grupos y ampos de Galois . . . . . . . . . . . . . . . . . . . . 1

1.1.2. Aritméti a en ampos de Galois . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2. Base teóri a de riptología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3. Estru tura del algoritmo PRESENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4. Estru tura de la implementa ión del algoritmo . . . . . . . . . . . . . . . . . . . . . 14

2. Plataformas embebidas de diseño 17

2.1. Diseño ESL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.1. Diseño Top-Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.2. Planea ión de tareas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.1.3. Co-diseño . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2. Plataformas soporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.1. Plataformas embebidas software . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.2. Plataformas embebidas Hardware . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3. Argumento �nal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3. Metodología, diseño y resultados 27

I

ÍNDICE GENERAL II

3.1. Modelo del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.1. Implementa ión plataforma embebida software - mi ro ontrolador . . 27

3.1.2. Implementa ión plataforma embebida hardware - FPGA . . . . . . . . . 30

4. Con lusiones y aporta iones 34

4.1. Con lusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.2. Aportes originales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.3. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Bibliografía 37

Índi e de tablas

1.1. Caja de sustitu ión S-box del algoritmo PRESENT . . . . . . . . . . . . . . . . . 12

1.2. Tabla de sustitu ión de bits pLayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3. Ve tores de prueba para PRESENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1. Cara terísti as del multipro esador PROPELLER . . . . . . . . . . . . . . . . . . 21

2.2. Cara terísti as de los PIC's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3. Cara terísti as de los AVR's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4. Cara terísti as de los Texas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5. Cara terísti as de los Pso 's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.6. Cara terísti as de los Frees ale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.1. Parámetros de rendimiento de las implementa iones . . . . . . . . . . . . . . . . . 29

3.2. Tabla omparativa entre implementa ión de referen ia y la propia . . . . . . . 32

3.3. Tabla omparativa de algunos algoritmos de ifrado . . . . . . . . . . . . . . . . . 33

III

Índi e de �guras

1.1. Pro eso Criptográ� o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2. Clasi� a ión de la riptografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3. Esquema de riptografía Simétri a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4. Opera iones del Cifrado Simétri o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5. Tipos de ifrado simétri o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.6. Cifrado en Flujo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.7. Cifrado en Bloque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.8. Opera iones bási as de una ronda en un ifrador en bloque típi o . . . . . . . . 11

1.9. Ronda del algoritmo PRESENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.10. DataPath de 16 Bits para SBoxLayer y pLayer de Present . . . . . . . . . . . . 14

1.11. DataPath generador de sub lave del algoritmo PRESENT . . . . . . . . . . . . . 15

1.12. Estru tura del algoritmo PRESENT expresada en Pseudo ódigo . . . . . . . . 15

3.1. Pruebas en el PC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.2. Datapath real ifrador en VHDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3. Máquina de estados de la unidad de ontrol del ifrador . . . . . . . . . . . . . . 31

3.4. Simula ión paso a paso de la implementa ión hardware . . . . . . . . . . . . . . . 32

IV

Introdu ión

Esta investiga ión se enmar a en la línea de investiga ión de sistemas de seguridad

para redes [1, 2℄, espe í� amente en la implementa ión y uso de algoritmos de ifrado para

apli a iones de tipo embebido [3, 4, 5℄, que requieran un mínimo grado de seguridad, pero

sin sa ri� io en la velo idad de transmisión [6℄.

La ne esidad de transmitir datos seguros plantea diferentes es enarios y ara terísti as

en ada tipo de apli a ión. En ada aso, dos elementos laves integrados del diseño,

que determinan la on�abilidad y la robustez, son el hardware y el software. En el aso

de apli a iones inalámbri as on baja tasa de transferen ia de datos (throughput) [7℄, el

hardware tiende a ser dedi ado y de bajo osto. Estas apli a iones, objeto de estudio de la

investiga ión, requieren el uso de un hardware embebido on baja apa idad omputa ional

(livianas, tipo lightweight) [8, 9, 10℄, que utili en omo base una plataforma de desarrollo

embebido mi ropro esado [11, 12℄, así omo dispositivos lógi os programables tipo FPGA

[13, 14, 15℄.

Éste tipo de algoritmos lightweight [8, 16, 17℄ se utilizan en apli a iones inalámbri as

de bajo throughput [7, 4, 3℄, dentro de las que se uentan las redes de sensores, los tags

RFID (Radio-Frequen y Identi� ation), redes PAN (Personal Area Network), Xbee y otros

proto olos inalámbri os [17, 18℄.

Los ifradores de bloque [19, 20℄ son unos de los esquemas de ifrado más usados

[21℄, dentro de los uales se en uentran un sin número de algoritmos on diferentes a-

ra terísti as, mu hos de ellos se han implementado en dispositivos lógi os programables

[15, 6, 22, 20℄ igual que implementa iones realizadas en dispositivos embebidos software

tipo mi ro ontrolador [11, 12, 23℄. Como referentes obligados para ifradores de bloque se

en uentra el AES (Advan ed En ryption Standard), ya que es estándar [24, 22, 11℄ y el

algoritmo de urvas elípti as [25, 26℄ por su trasfondo y para dar una base matemáti a al

proye to. Tomando en uenta lo anterior, sabiendo que se puede realizar la implementa ión

de di hos algoritmos on distintas té ni as y diferentes dispositivos, en esta investiga ión

se opta por implementar un ifrador de bloque, que umpla on la �losofía de lightweight

y que además de ello sea fá ilmente realizable en hardware y software. De esta manera,

se de ide trabajar on el algoritmo PRESENT [27, 28, 10, 14, 15℄, el ual se va a imple-

mentar tanto en hardware omo en software y posteriormente se realizarán estudios para

determinar las métri as de mayor interés para ada aso.

La sele ión de este algoritmo se da, por estar estandarizado y a eptado por los entes

que regulan la riptografía a nivel mundial ISO/IEC, NIST y NSA [29, 30℄ y ser un algorit-

V

INTRODUCCIÓN VI

mo relativamente nuevo sin haber sido vulnerado hasta el momento. Además, se tiene un

punto de ompara ión, on otro algoritmo de ifrado por bloques on una implementa ión

previa [11℄, el ual fue publi ado en el Congreso Argentino de Sistemas Embebidos (CASE)

2012.

El algoritmo PRESENT es un algoritmo simétri o de ifrado on una naturaleza total-

mente minimalista, ya que utiliza bloques de sustitu ión y permuta ión de tan solo 4 bits

omo base. Este tipo de estru tura permite que su implementa ión sea realizable en dis-

positivos hardware de redu ido tamaño, lo que permite un sentido de uso ade uado de los

re ursos y ara terísti as, que le permite ser de fá il implementa ión en pro esadores on

un bus pequeño. Además de esto, posee laves de an ho relativamente pequeño, omparado

on otros algoritmos del mismo tipo y requiere una antidad de rondas redu ida; por otro

lado, desde el punto de vista de su diseño e implementa ión presenta un reto interesante,

ya que requiere de una estrategia que tenga en uenta el equilibro entre antidad de re urso

usado y velo idad de omuni a ión general del sistema [31, 32, 7℄.

Justi� a ión

En apli a iones lo ales o en las que por su tamaño y osto no se justi� a el uso de un

PC para el tratamiento y envío de la informa ión, pero que requieren que la omuni a ión

sea segura, se ha e ne esario explorar la implementa ión de pro esadores embebidos [27℄,

sistemas operativos en tiempo real y en general de dispositivos de ifrado en hardware [9℄,

aprove hando los sistemas lógi os re on�gurables y pro esadores de alta velo idad a tuales,

para lograr ondi iones de paralelismo y on urren ia [6℄ que redundan en el rendimiento

del sistema y su velo idad de pro esamiento, fa tor importante a la hora de pensar en una

apli a ión real.

En las redes de omuni a ión a tuales, ya sean ableadas o inalámbri as, se requiere

que los datos viajen seguros manteniendo el equilibrio entre seguridad y antidad de datos

enviados (throughtput); para ello se requieren algoritmos que permitan implementa iones

hardware-software e� ientes en uanto a las métri as de interés. Por tal motivo, se apli a

un algoritmo de ifrado [28℄, que apuesta a la versatilidad, �exibilidad de on�gura ión y

bajo uso de re ursos[10, 14, 15℄ tanto en implementa iones hardware omo software.

Los pro edimientos implementados en hardware brindan solu iones rápidas para apli-

a iones donde el trá� o de datos es mayor y requieren ifrado en tiempo real [6℄. Por

otro lado, los dispositivos lógi os programables son una muy buena alternativa, debido a

que tienen la propiedad de ser re on�gurables y su ara terísti a on urrente ha en que

sean óptimos para pro esos masivos y omplejos on tiempos de respuesta bastante buenos

[10, 14, 15℄.

Las plataformas embebidas de software poseen la versatilidad en uando a la rea ión

de librerías y fun iones estándar que permiten su uso en distintas familias de dispositivos

[12℄, en general, siempre se bus a la rea ión de algoritmos en lenguajes de alto nivel que se

puedan ompilar sobre diferentes plataformas, todo esto de manera sen illa y sin importar

la arquite tura interna de los dispositivos [7℄.

Re ientemente, si se requería un ifrador de bloque usando hardware de pequeñas pres-

ta iones, se tenía asi que obligatoriamente re urrir al algoritmo Rijindael: algoritmo que

INTRODUCCIÓN VII

es un referente obligado, pero por su ara terísti as de tamaño de la aja de sustitu ión

(S-box) y su tamaño de lave, no permitía su implementa ión en dispositivos pequeños;

en este trabajo, se brinda otra posibilidad de ifrador por bloque on tamaño de aja de

sustitu ión ultra redu ida apropiada para dispositivos lógi os programables muy pequeños

o mi ro ontroladores de 8, 16 bits o una nueva familia de 32 bits de muy bajo osto.

Formula ión del problema

Pregunta de investiga ión

¾Cómo desarrollar una implementa ión de un algoritmo de ifrado ligero PRESENT

usando plataformas embebidas hardware y software, para apli a iones de omuni a ión

inalámbri a, mantenido el equilibrio entre uso de re ursos y velo idad de omuni a ión?

Objetivos

General

Evaluar del desempeño del algoritmo riptográ� o PRESENT usando plataformas em-

bebidas hardware y software.

Espe í� os

1. Evaluar las ara terísti as de las plataformas embebidas tanto software omo hard-

ware, en uanto a rendimiento, osto y omplejidad para así elegir los más ade uadas

para la implementa ión del algoritmo riptográ� o.

2. Implementar del algoritmo riptográ� o PRESENT usando plataformas embebidas

hardware y software.

3. Simular y validar los resultados de las implementa iones embebidas hardware y soft-

ware pra ti ando las ompara iones ne esarias y analizando sus respe tivas métri as.

Organiza ión de la tesis de maestría

En primera medida, se debe realizar un estudio on ienzudo de la base matemáti a

de los ifradores de bloque y en general de los ampos de Galois, que son la base teóri a

que permite la implementa ión de este tipo de algoritmos. Seguidamente, se debe dar una

pequeña introdu ión a la riptología, los diferentes esquemas de ifrado y sus diferen ias;

además de esto, se debe dar una expli a ión de las partes bási as o omponentes mínimos

de un ifrador por bloque [33℄ dando una expli a ión de ada uno de ellos.

Después de realizar el levantamiento de las bases teóri as de este tipo de algoritmos, se

debe sele ionar el al an e, las presta iones y ara terísti as de la posible apli a ión reali-

zada [7, 27℄; por eso en su primera parte del desarrollo, antes de realizar la implementa ión,

se debe realizar un estado del arte, tomando en uenta la arquite tura de los dispositivos

INTRODUCCIÓN VIII

y sus ara terísti as [12℄, integrándolo on el diseño y posterior implementa ión del mismo

tanto en hardware omo en software y por último las respe tivas pruebas y ompara iones

de las dos implementa iones realizadas [7, 27℄.

Al tener las implementa iones, pruebas, simula iones y veri� a iones, se deberá plantear

un trabajo futuro, donde el uso de éstas librerías sea signi� ativo, llevando esta investiga-

ión al ampo de apli a ión tanto en la vida a adémi a omo para posibles apli a iones

omer iales.

CAPÍTULO 1

Fundamenta ión matemáti a y estado del arte

1.1. Fundamenta ión matemáti a

En general, los sistemas de ifrado por bloques están diseñados para manejar longitudes

de lave y de bloque variables, ambas omprendidas entre los 80 y los 256 bits. Di hos

paquetes de informa ión se operan a nivel de byte, interpretando éstos omo elementos de

un ampo de Galois GF(k). El resto de opera iones se efe túan en términos de registros

de 32 bits [7, 10℄.

En los ifradores en bloque, todos los bytes se interpretan omo elementos de un ampo

�nito, los uales se representan mediante ampos de Galois GF(k). En este ampo existe

un inverso aditivo y un inverso multipli ativo, lo ual unido a otras propiedades de esta

estru tura algebrai a permite implementar opera iones invertibles, lo que permite ifrar y

des ifrar en el mismo ampo Zk [15, 6℄.

1.1.1. Aritméti a en grupos y ampos de Galois

Una estru tura algebrai a es un onjunto dotado de una o más opera iones binarias

que umple iertas propiedades.

Si el onjunto tiene �nitos elementos, se di e que la estru tura algebrai a tiene orden

�nito, de lo ontrario tiene orden in�nito. Entre las estru turas algebrai as más utilizadas

en los algoritmos riptográ� os, están los grupos y los ampos.

1. Grupos

Un onjunto G dotado de una opera ión binaria *,<G,*>, que umple las siguientes

propiedades tiene estru tura algebrai a de grupo.

(a) Clausurativa: a ∗ b ∈ G,∀a, b ∈ G

(b) Aso iativa: a ∗ (b ∗ c) = (a ∗ b) ∗ c,∀a, b, c ∈ G

( ) Modulativa: ∃e ∈ G/a ∗ e = e ∗ a = a,∀a ∈ G

(d) Invertiva: ∃a−1/a−1 ∗ a = e,∀a ∈ G

1

CAPÍTULO 1. FUNDAMENTACIÓN MATEMÁTICA Y ESTADO DEL ARTE 2

Si además de las propiedades anteriores se umple la propiedad onmutativa en la

ual a ∗ b = b ∗ a,∀a, b ∈ G, enton es el grupo es Abeliano.

En las apli a iones riptográ� as solo interesan los grupos de orden �nito y en los

uales sus opera iones se realizan módulo un numero primo n, o módulo un polinomio

irredu ible f(x). Un sub onjunto H de G que umple las mismas propiedades de grupo

se llama subgrupo y el orden de ualquier subgrupo de G divide al orden de G.

2. Anillos

Un anillo es un onjunto G dotado de dos opera iones binarias ∗,∆ de esta forma se

genera una estru tura algebrai a <*,G,∆> que umple las siguientes ondi iones:

(a) La estru tura algebrai a <G,*> es Grupo Abeliano.

(b) La estru tura <G,∆> , umple las propiedades aso iativas y lausurativas.

( ) El onjunto G dotado de las dos opera iones <*,G,∆> umple la propiedad

distributiva, la ual ha e intera tuar las dos opera iones sobre los elementos de

G.

3. Campos

(a) La estru tura algebrai a <G,*> es grupo Abeliano.

(b) El onjunto G on la opera ión ∆ es grupo Abeliano.

( ) La estru tura <G,∆> umple la propiedad distributiva a dere ha e izquierda.

Los ampos apli ados a la riptografía son aquellos que tienen orden �nito, también

llamados ampos de Galois o ampos �nitos. La aritméti a en estos ampos permite por

ejemplo las opera iones de suma y multipli a ión de puntos ra ionales en la riptografía de

urvas elípti as [5, 26℄, ya que estos tienen estru tura de grupo �nito aditivo Abeliano y las

urvas elípti as se de�nen sobre ampos de Galois. La e� ien ia, la velo idad y el espa io

o upado en un pro esador por la aritméti a de ampos �nitos, es un fa tor impres indible

en el momento de elegir un algoritmo para la implementa ión de ualquier opera ión en

el ampo. La investiga ión en esta área se en amina a lograr mayor e� ien ia tanto en la

representa ión de los ampos �nitos, omo en la implementa ión de aritméti a en estos

ampos, tanto en software omo en hardware.

1.1.2. Aritméti a en ampos de Galois

Campos Primos

En mu has opera iones rela ionadas on algoritmos riptográ� os simétri os se utilizan

los ampos primos puesto que permiten desarrollar opera iones pre al uladas y algunas

ve es basadas en uso de tablas. Este es el aso de algunas ajas S o S-box, usadas en la

gran mayoría de los algoritmos de ifrado por bloques. Las opera iones de ampos primos

son modulares para garantizar la propiedad lausurativa y así onservar el tamaño de

los datos. Entre los ampos más utilizados están los de tamaño un número primo o una

poten ia de 2, en el aso de trabajar on bytes.


1. Aritméti a en ampos GF (qm)

(a) Bases polinomiales

Si se onsidera una extension �nita F = Fqm del ampo �nito K = Fq o-

mo un espa io ve torial sobre K, enton es F tiene dimensión m sobre K y si

(α1, α2, ...., αm) es una base de F sobre K, enton es ada elemento α ∈ F se

puede representar de forma úni a omo: α = C1α1+C2α2+ .....+Cmαm , donde

Cj ∈ K, 1 ≤ j ≤ m

Se puede estable er la siguiente orresponden ia lineal de F en K mediante la

fun ión traza TrF |K(α) : sea K un ampo �nito y sea TrF |K(α) una exten-

sión �nita de K, la base polinomial (1, α, α2, ...., αm−1) es onstruida on las

poten ias de un elemento de�nitorio α de F sobre K, donde el elemento α es

un elemento primitivo de F. Con esta base se representan los elementos de un

ampo �nito mediante polinomios on oe� ientes ai, que pertene en al ampo

K y las poten ias de los elementos de la base. Cada polinomio que representa

un término es una lase residual módulo el polinomio irredu ible, es de ir:

Fqm = a0 + a1x+ a2x2 + ...+ amxm−1|a1 ∈ Fq (1.1)

(b) Produ to

Dos elementos A,B ∈ GF (2m) on polinomio irredu ible p(z), son representados

en la forma de polinomios, en este aso la ara teristi a del ampo q es 2:

A = a0 + a1x+ a2x2 + ...+ am−1x

m−1(1.2)

B = b0 + b1x+ b2x2 + ...+ bm−1x

m−1(1.3)

El produ to C = A ∗B se representa omo:

C = c0 + c1x+ c2x2 + ...+ cm−1x

m−1(1.4)

De la expresión anterior puede notarse que el produ to C tiene el mismo tamaño

que los operandos A y B, lo ual se debe a que son elementos de un ampo �nito.

Para realizar la multipli a ión entre dos elementos de un ampo �nito on repre-

senta ión en base polinomial, se realiza la multipli a ión normal de polinomios,

lo que origina un polinomio de grado máximo 2m − 2 . Como puede observar-

se, éste polinomio no pertene e al ampo �nito, por lo ual se implementa una

redu ión módulo del polinomio irredu ible. Dado que la multipli a ión de poli-

nomios se puede realizar paso a paso, este tipo de multipli adores se denominan

seriales [11, 24, 34, 35℄.

El otro enfoque es tomando omo base el polinomio irredu ible, al ular las

expresiones que generan ada uno de los oe� ientes del resultado de la multi-

pli a ión, la ual por lo tanto se puede implementar en paralelo [22℄.

( ) Suma en GF (2m)


Dados dos elementos:

A = a0 + a1x+ a2x2 + ...+ am−1x

m−1yB = b0 + b1x+ b2x2 + ...+ bm−1x

m−1

(1.5)

en el ampo �nito GF (2m), enton es:

A+B = c0 + c1x+ c2x2 + ...+ cm−1x

m−1(1.6)

donde

Ci = (ai + bi)mod2 (1.7)

lo que equivale a la opera ión XOR bit a bit.

(d) Inverso multipli ativo en el ampo de extensión binario

Para el aso del inverso multipli ativo, se implementa el algoritmo de Itoh-Tsujii

[1℄, el ual en forma re ursiva realiza la exponen ia ión del valor al ual se le va

a al ular el inverso multipli ativo. La expresión general para al ular el inverso

multipli ativo, se deriva de la siguiente forma:

Dado un elemento A ∈ GF (2m) existe un elemento A−1tal que se umple

A ∗A−1 = e, siendo e el elemento neutro de la opera ión produ to, en este aso

e = 1 = z0.

La opera ión inversión es importante en sí misma y también para la implemen-

ta ión de la división, ya que:

A

B−1⇔ B 6= 0 (1.8)

Para esto es ne esario al ular el inverso de B y luego realizar una multipli a ión;

la inversión es la opera ión más difí il de implementar en aritméti a de ampos

�nitos.

Existen dos tipos de algoritmos de inversión: Basados en el Teorema Extendido

de Eu lides, sus variantes y otros basados en multipli a iones en el ampo. Si

se opta por un método basado el algoritmo extendido de Eu lides, la ompleji-

dad omputa ional es bastante alta, lo que impa ta dire tamente en el diseño.

Si se opta por un método basado en multipli a iones, se utiliza la fun ión de

multipli a ión redu iendo la omplejidad omputa ional.

La idea prin ipal del inversor implementado radi a en el "pequeño Teorema de

Fermat"que indi a que para todo elemento no ero en un ampo F2m

a−1 = a2m−2

(1.9)

Esto se demuestra ya que por las propiedades de los ampos F2m

a2m

= a (1.10)

y ha iendo una sustitu ión se llega a la expresión anterior.


La expresión puede rees ribirse omo:

a−1 = a2m−2 = (a2

m−1)2 (1.11)

De esta manera, se puede redu ir la omplejidad de la inversión a un número

menor de eleva iones al uadrado.

Itoh y Tsujii [1, 11℄ en su libro Algebra Moderna(2004), propusieron una inge-

niosa manera de redu ir aún más la omplejidad de la opera ión, ha iendo una

nueva sustitu ión de tal forma que se obtienen las fórmulas:

a2m−1−1 = (a2

m−1

2 −1)2m−1

2−1

∗ a2m−1

2 −1

a ∗ (a2m−2−1)2

(1.12)

El primer aso es para m impar y el otro para m par.

La de�ni ión de grupo y ampos de Galois es fundamental para el desarrollo del

ifrador, ya que se requieren realizar opera iones usando aritméti a en ampos,

puntualmente en el ampo GF (24) ya que el ifrador Present utiliza este tamaño

de bits omo base aritméti a o polinomial. Cada uno de los bloques que se

mostrarán en la siguiente se ión usan opera iones en este ampo, omo suma,

produ to y sustitu ión.

1.2. Base teóri a de riptología

Se podría de�nir el ampo de la riptología, omo el estudio de una serie de pro esos

o té ni as, usando té ni as matemáti as, que le infringen ierto nivel de seguridad a una

informa ión en espe i� o, tal omo la integridad de los datos, autenti a ión de entidades

y del origen de los datos [1, 2℄.

La riptología está formada por dos té ni as, las uales son: riptografía y riptanálisis.

1. Criptanálisis

Es la té ni a de des ifrar un riptograma sin tener la autoriza ión. Consiste en romper

mensajes ifrados ata ándolos y bus ando el mensaje original (mensaje en laro). El

riptanálisis abar a diversas té ni as, mu has ve es no dependen del ono imiento

del algoritmo sino que mediante sistemas de aproxima iones matemáti as se puede

des ubrir el texto en laro o la lave [2, 36℄.

2. Criptografía

Es la té ni a de onvertir un texto inteligible llamado riptograma, en otro uyo

ontenido de informa ión es igual al anterior pero des ifrado úni amente por las

personas autorizadas [36℄.

El objetivo de la riptografía es el de propor ionar omuni a iones seguras sobre

anales inseguros, es de ir, permitir que dos entidades, bien sean personas o apli a-

iones, puedan enviarse mensajes por un anal que puede ser inter eptado por una


Figura 1.1: Pro eso Criptográ� o

ter era entidad, de modo que sólo los destinatarios autorizados puedan leer los men-

sajes. Pero la riptografía no es en sí la seguridad, sólo es la herramienta bási a que

utilizan me anismos más omplejos para propor ionar, además de on�den ialidad,

otros servi ios de seguridad [1, 36℄.

Figura 1.2: Clasi� a ión de la riptografía

Las té ni as de riptografía se pueden lasi� ar en dos grupos según el tipo de lave

utilizado, los uales son: Criptografía simétri a o de lave se reta y Criptografía

asimétri a o de lave públi a. En lo ual nos enfo aremos a presentar informa ión

de Criptografía simétri a ya que el algoritmo PRESENT se en uentra dentro de este

tipo de ifrado.

3. Criptografía simétri a o de lave se reta

Existe una úni a lave (se reta) que omparte emisor y re eptor. Con la misma lave


se ifra y se des ifra, por lo que la seguridad reside en mantener di ha lave en se reto

omo se ve en la �gura 1.3 [1℄.

Figura 1.3: Esquema de riptografía Simétri a

El pro eso de obten ión del mensaje de ifrado es:

c = Ek(m) (1.13)

Donde k es la lave se reta, Ek representa la opera ión de ifrado on esa lave y m

es el mensaje en laro.

Simétri amente el pro eso de re upera ión del mensaje original, mediante la ope-

ra ión de ifrado, Dk, en el que se utiliza la misma lave se reta k, se representa

omo:

m = Dk(c) (1.14)

La simetría del pro eso se basa en que este tipo de ifradores se omporta omo:

Ek(Ek(m)) = m (1.15)

Los algoritmos de lave se reta se apoyan en opera iones algebrai as muy simples, lo

que onlleva que el tiempo ne esario para realizar el pro eso ompleto de ifrado es

muy pequeño. Esta ara terísti a ha e que este tipo de ifrado pueda utilizarse para

propor ionar on�den ialidad en apli a iones telemáti as, en las que se requiere gran

velo idad en �ujo de datos.

La riptografía simétri a impli a que para estable er omuni a ión segura entre dos

usuarios, es ne esario que éstos onoz an y ompartan una lave simétri a on reta.

Dos té ni as bási as de la riptografía simétri a son: onfusión y difusión (Figura

1.4).

(a) Confusión onsiste en estable er una dependen ia fun ional lo más ompleja

posible entre la lave y el mensaje en laro y se onsigue mediante la sustitu ión

de unos símbolos por otros.

(b) Difusión onsiste en dispersar a lo largo del programa las propiedades estadísti-

as del mensaje en laro y se onsigue mediante la transposi ión (permuta ión

de los bits)[1℄.


Figura 1.4: Opera iones del Cifrado Simétri o

4. Cifradores de Flujo y Cifradores de Bloque

Dado un mensaje en laro m, representado mediante un número variable de o tetos,

a la hora de pro eder a su ifrado para onvertirlo en un riptograma existen dos

op iones de ifradores (�gura 1.5), que se diferen ian en omo dividen el mensaje en

laro para abordar la tarea de transforma ión [1, 2℄.

Figura 1.5: Tipos de ifrado simétri o

(a) Cifrado de Flujo

La ara terísti a prin ipal de este ifrado (�gura 1.6), onsiste en tomar el men-

saje en laro omo un �ujo ontinuo de bits (o ara teres) y generar a la salida

el orrespondiente �ujo de bits resultante de la transforma ión produ ida en el

pro eso de ifrado. La ventaja de este sistema es la simpli idad en el pro eso de

ifrado.

Figura 1.6: Cifrado en Flujo

(b) Cifrado en Bloque

En este tipo de ifrado el mensaje en laro se divide en bloques de n bits ada

uno [15, 28℄. La ara terísti a prin ipal de este tipo de ifradores onsiste en que

ada bloque se ifra de igual forma, independientemente del lugar que o upe en


la adena, de manera que todos los bits del bloque se ifran onjuntamente,

parti ipando en opera iones que tratan de os ure er las posibles rela iones que

tuviesen en el mensaje original [1℄. Esto se puede ver en la �gura 1.7

Figura 1.7: Cifrado en Bloque

Los algoritmos simétri os ifran bloques de texto, pero esta longitud varia para

ada algoritmo.

En el ifrado en bloque se realizan uatro opera iones bási as:

• Ele toni CodeBlo k (ECB): en él se en riptan los bloques por separado.

• Cipher Blo kChainning (CBC): los bloques de riptograma se rela ionan

entre ellos mediante fun iones OR EXCLUSIVA.

• Cipher feedba k (CFB): se realiza una OR EXCLUSIVA entre ara teres o

bits aislados del texto y las salidas del algoritmo. El algoritmo utiliza omo

entrada los riptogramas.

• Output feedba k (OFB): igual que el CFB, se realiza una OR EXCLUSIVA

entre ara teres o bits aislados de texto y las salidas del algoritmo, pero éste

utiliza omo entradas sus propias salidas; por tanto no depende del texto,

es un generador de números aleatorios.

A ontinua ión se muestran algunos ejemplos de algoritmos simétri os, que se

han tomado omo referen ia para este trabajo y se onsidera de suma impor-

tan ia nombrarlos de manera dire ta:

• Algoritmo DES : (Data En ryption Standard), Es el algoritmo simétri o más

extendido mundialmente. Se basa en el algoritmo LUCIFER, fue adopta-

do omo estándar por el Gobierno de los EE.UU para omuni a iones no

lasi� adas en 1976. Aunque a tualmente es onsiderado un algoritmo que

ha sido vulnerado en múltiples o asiones. Sin embargo es de utilidad en

mu has apli a iones.

• Algoritmo IDEA: (Interna ional Data En ryption Standard), Es un algorit-

mo muy robusto y popular por haber sido adoptado por PGP, una apli a ión

de orreo ele tróni o seguro, de uso muy extendido. Además, no presenta

debilidad de lave y la longitud de ésta ha e imposible un ataque por fuerza

bruta.

• Algoritmo RC2 : Diseñado por Ron Rivest en 1987 para la ompañía RSA

Data Se urity, utilizado en paquetes de orreo ele tróni o (S-MIME) y en

otros produ tos de seguridad. Este algoritmo está protegido omo se reto

omer ial.



Data Se urity. Sen illo y rápido, orientado a generar se uen ias en unidades

de un byte. Además, permite laves de diferentes longitudes. Es un algoritmo

propietario, lo ual impli a que no puede ser in luido en apli a iones de tipo

omer ial sin pagar los dere hos orrespondientes.


Data Se urity. Consiste en una familia de algoritmos riptográ� os que tie-

nen una serie de parámetros que determinan el tamaño de la lave, el número

de i los y el tamaño de los bloques [37℄.

• Algoritmo SEAL: Su fun ionamiento se basa en un pro eso ini ial en el que

se Cal ulan los valores para unas tablas a partir de la lave, de forma que

el ifrado se lleva a abo de una manera rápida. [36℄

• Algoritmo SKIPJACK : Elegido para soportar el ifrado en el esquema de

lipper hip. Es un algoritmo se reto y su estru tura no ha sido publi ada.

Se ree que su estru tura es similar a la de DES, on bloque de 64 bits,

bloques tipo aja s (S-box), una lave de 80 bits y un omportamiento

iterativo basado en 32 i los.

• Algoritmo GOST : Publi ado omo estándar en la antigua unión soviéti a,

pertene e a un grupo de algoritmos que abar a distintas fun iones de se-

guridad. Su estru tura es muy similar a la de DES y al igual que éste es

iterativo y parte de bloques de 64 bits que se dividen en dos mitades y se

inter ambian entre si en ada i lo [36℄.

• Algoritmo Rijndael-AES : Este algoritmo fue es ogido omo el su esor de

DES, después de una onvo atoria que se realizó en 1997, en una primera

ronda se sele ionaron 15 algoritmos de los uales 5 fueron sele ionados en

la ronda �nal [1, 11, 36, 37℄:

� MARS, de IBM

� RC6 de RSA laboratory

� SERPENT de R. Anderson, E Biham y L. Knudsen

� TWOFISH, de B s hneider y otros

� RIJNDAEL, de Joan Daemen y Vin ent Rijmen

• Simon and Spe k [19℄: El objetivo de estos algoritmos es dar más op iones

de posibles ifradores de bloque tipo lightweight, que posean ara terísti as

de �exibilidad y on�abilidad. Cada uno ofre e un ex elente rendimiento

en plataformas hardware y software respe tivamente. Además de esto, son

lo su� ientemente �exibles omo para admitir una variedad de implemen-

ta iones sobre diferentes plataformas. Ambos se adaptan ex ep ionalmente

bien en todo el espe tro de apli a iones tipo lightweight, pero Simon está

sintonizado para un rendimiento óptimo en hardware y la Spe k para un

rendimiento óptimo en software [7℄.

5. Opera iones bási as de los ifradores en bloque

Las opera iones bási as de un algoritmo de ifrado por bloques se muestran en la

�gura 1.8. Estas pueden variar dependiendo del algoritmo planteado.

En todos los ifradores por bloque se genera una ombina ión de las opera iones

ByteSub, ShiftRow, MixColum y AddRoundKey o sus equivalentes o modi� a iones


Figura 1.8: Opera iones bási as de una ronda en un ifrador en bloque típi o

de las mismas según sea el aso y a la eje u ión de ada una de ellas se le llama 'una

ronda' ; la omplejidad y seguridad del algoritmo depende de la ombina ión de las

opera iones anteriores y de las rondas realizadas a la informa ión a ifrar, además

del tamaño de la lave usada [7, 19℄.

Cada ronda está ompuesta por tres opera iones basadas en transforma iones unifor-

mes e invertibles que son llamadas apas, que han sido diseñadas para resistir ante

el riptanálisis lineal y diferen ial, las uales son:

• Capa no lineal : Consiste en la apli a ión de ajas S en paralelo que tiene pro-

piedades optimas de no linealidad.

• Capa de mez la lineal : garantiza un alto nivel de difusión a lo largo de las

múltiples rondas.

• Capa de adi ión de lave: Se trata de una opera ión OR ex lusiva entre el

estado intermedio y la lave propia de ada ronda.

6. PRESENT : Un algortimo Ultra-lightweight [10, 29℄

PRESENT es uno de los algoritmos de ifrado por bloques tipo lightweight más o-

no ido. Debido a que presenta fa ilidad de apli a ión por su diseño redu ido, tanto

en hardware y software [10, 14℄; su implementa ión en hardware puede ser realizada

en algunas de las FPGA's más pequeñas del mer ado, on un throughtput signi� ati-

vamente alto [15℄. Además de esto, se puede implementar en plataformas embebidas

software de muy bajas presta iones, ya sea en su tamaño de bus o en su memoria

volátil disponible.


1.3. Estru tura del algoritmo PRESENT

En la �gura 1.9 se muestra la estru tura bási a del algoritmo PRESENT, donde se ven

sus bloques y omo se deben realizar ada una de sus 31 rondas [10℄. A ontinua ión se

Figura 1.9: Ronda del algoritmo PRESENT

espe i� a el fun ionamiento de ada una de las partes del diagrama de bloques de la �gura

1.9.

1. Capa de sustitu ión de bytes: SboxLayer Consiste en una sustitu ión no lineal

que se apli a a ada nibble de la matriz de estado de forma independiente, mostra-

da en la tabla 1.1, generando un nuevo nibble. Esta transforma ión onsiste en la

sustitu ión de ada nibble por el resultado de apli arle la tabla de sustitu ión S-Box

[10, 14℄. Este bloque de sustitu ión se le apli a a 16 nibbles que ompletan 64 bits

de informa ión, que es el tamaño estándar de los bloques de ifrador.

Tabla 1.1: Caja de sustitu ión S-box del algoritmo PRESENT

X 0 1 2 3 4 5 6 7 8 9 A B C D E F

S(x) C 5 6 B 9 0 A D 3 E F 8 4 7 1 2

Cuando se diseña el algoritmo de ifrado se bus a la mayor entropía posible en los

datos sustituidos. Para este aso, se trabaja on tamaños de palabra de 4 bits, ya que

al ser un algoritmo totalmente minimalista se logra que sea implementado en una

úni a LUT(Look Up Table), en el aso de las FPGA's; o mediante pequeñas tablas

en pro esadores de bus pequeño ó realizando mas aras de 4 bits en pro esadores on

bus de datos mayor.

2. Permuta ión de Bits: pLayer

Es una apa que mez la mediante una sustitu ión de bit a bit un bloque de informa-

ión de 64 bits, donde el Bit i del la ronda es movido a la posi ión P (i); el orden de

di ha sustitu ión se muestra en la tabla 1.2:


Tabla 1.2: Tabla de sustitu ión de bits pLayer

ì 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

P(i) 0 16 32 48 1 17 33 49 2 18 34 50 3 19 35 51

ì 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

P(i) 4 20 36 52 5 21 37 53 6 22 38 54 7 23 39 55

ì 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

P(i) 8 24 40 56 9 25 41 57 10 26 42 58 11 27 43 59

ì 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

P(i) 12 28 55 60 13 29 45 61 14 30 46 62 15 31 47 63

3. Fun ión de expansión de lave: addRoundKey

PRESENT puede tener laves de 80 o 128 bits de longitud, pero para este diseño e

implementa ión, se tomará en uenta úni amente lave de 80 bits, que serán alma e-

nadas en un registro K de di ho tamaño y serán enumerados K79K78....K0. Pero en

ada ronda solo se mez larán los 64 bits más signi� ativos de la nueva lave al ulada

después de apli ar la fun ión de expansión de lave, de tal manera que para la nueva

lave Ki = k63k62...k0 o viéndolo de otra manera, se debe realizar una rota ión de

bits de la siguiente forma:

Ki = k63k62...k0 = K79K78....K0 (1.16)

Después de realizada esta rota ión del bloque de entrada, se deben realizar las si-

guientes opera iones para ada nueva subClave generada Ki:

• Rota ión de los bits de la lave de entrada:

[k79k78...k0] = [k18k17...k20k19] (1.17)

• Sustitu ión usando S-Box para el nibble de k78 a k76 de la lave:

[k79k78k77k76] = S[k79k78k77k76] (1.18)

• Adi ión o mez la del nibble k19 a k15 de la lave on el ontador de rondas,

mediante la suma en en ampo �nito GF (21) u opera ión XOR:

[k19k18k17k16k15] = [k19k18k17k16k15]⊕RoundCounter (1.19)

Ésta fun ión permite generar bloques de informa ión útiles omo sub laves a partir

de la lave del sistema K. Las primeras Nk palabras de este arreglo (array) ontienen

la lave usada para ifrar, ya que la lave del usuario se mapea al arreglo (array)

W, mientras que el resto de palabras se van generando a partir de estas primeras Nk

palabras [10, 14℄.

Ësta fun ión toma onse utivamente de la se uen ia obtenida por la fun ión de ex-

pansión de lave bytes que va asignado a ada sub lave Ki, para formar bloques del

mismo tamaño que la matriz de estado. Es de ir, toma Nb∗4 bytes para ada vuelta.Para este aso Nb es 16.


La genera ión de la lave (expansión de lave) para el pro eso de des ifrado se ha e

de igual forma al pro eso de ifrado. La diferen ia está en la fun ión de sele ión de

lave. En el pro eso de des ifrado se toman bloques de la lista de laves desde los

valores �nales hasta llegar a los ini iales, que es la propia lave de usuario. Es de ir,

la última sub lave Ki que se utilizó para ifrar, será la primera que se utilizará para

des ifrar [10, 14℄. Por lo ual, en el pro eso de des ifrado, se deben realizar todas

las rondas de genera ión de laves para omenzar desde ésta última Ki, realizando el

pro eso inverso hasta llegar a la lave original, por ello el ontador de rondas debe ser

de remental y realizar su mez la en ada ronda on el nibble indi ado anteriormente.

1.4. Estru tura de la implementa ión del algoritmo

1. Diagrama de bloques: DataPath

Debido a que todos los algoritmos de ifrado, ya sea por bloques o por �ujo, deben

dar toda la informa ión de su posible implementa ión, a ontinua ión se muestra

una posible implementa ión (�gura 1.10) mediante un DataPath que da solu ión al

algoritmo, aunque di ha arquite tura muestra una posible implementa ión en hard-

ware, es una de las mu has posibles implementa iones realizables desde la perspe tiva

Lightweight pero no garantiza una optimiza ión del uso de los re ursos de hardware

del dispositivo programable [19℄. En otras implementa iones se usan bloques de me-

moria dedi ados de algunas FPGA's para lograr la menor antidad de ompuertas

usadas en el dispositivos, provo ando que la antidad de i los de reloj para ada

ronda se in remente [15℄.

Figura 1.10: DataPath de 16 Bits para SBoxLayer y pLayer de Present

Al realizar una ronda se debe volver a realizar el ál ulo de la lave, en este aso


subClave Ki. En la �gura 1.11 se muestran bloques fun ionales que podrían ser im-

plementados tanto en software omo en hardware, ya que PRESENT es un algoritmo

diseñado para ser implementado en ualquiera de estas té ni as sin distin ión.

Figura 1.11: DataPath generador de sub lave del algoritmo PRESENT

2. Algoritmo: Pseudo ódigo

Ya que se propone darle solu ión al algoritmo, tanto desde el punto de vista hardware,

omo desde el punto de vista software, se podría resumir la eje u ión del mismo, a

un simple pseudo ódigo ompilable en ualquier plataforma embebida software [14℄.

Este ódigo se muestra a ontinua ión en la �gura 1.12:

Figura 1.12: Estru tura del algoritmo PRESENT expresada en Pseudo ódigo

Para ada una de las líneas de pseudo ódigo se debe rear una fun ión o método que

reali e las opera iones bási as de los algoritmos de ifrado en bloque. Para este aso se

debe elegir, sí se utilizan fun iones ó sí se van a implementan tablas para realizar las

opera iones de sustitu ión por nibbles para el Sbox y las opera iones de sustitu ión

de bits en la apa pLayer [3, 11℄. En el aso del uso de memoria dinámi a, se aumenta

el tiempo de eje u ión por la realiza ión de los ál ulos ne esarios, pero en el aso de

las tablas, se redu e el tiempo de pro esamiento on un ompromiso en la antidad de

memoria para alma enar las tablas de sustitu ión. Ya que la antidad de memoria de

datos de este tipo de dispositivos es limitada, se requiere ha er una revisión de uál

de las dos metodologías es la mas indi ada, por eso se propone realizar pruebas de


implementa ión para determinar ual es el mejor tipo de metodología para garantizar

que el algoritmo realmente sea tipo Lightweight [7, 8, 28℄.

3. Ve tores de Test

Para realizar la veri� a ión de que el algoritmo esté fun ionando orre tamente,

los diseñadores del algoritmo [10℄, ofre en una tabla en nota ión hexade imal, que

muestra una serie de textos planos, que al ser ombinados on iertas laves arrojan

un ierto texto ifrado ono ido. En la tabla 1.3 se muestran di hos ve tores:

Tabla 1.3: Ve tores de prueba para PRESENT

plaintext key ciphertext

00000000 00000000 00000000 00000000 0000 5579C138 7B228445

00000000 00000000 FFFFFFFF FFFFFFFF FFFF E72C46C0 F5945049

FFFFFFFF FFFFFFFF 00000000 00000000 0000 A112FFC7 2F68417B

FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFF 3333DCD3 213210D2

CAPÍTULO 2

Plataformas embebidas de diseño

En la última dé ada ha o urrido una evolu ión te nológi a en el ampo de los dispositi-

vos digitales programables, lo que a su vez ha permitido un gran salto en las posibilidades

de realizar desarrollos de alto rendimiento en dispositivos de bajo osto [5℄. Un laro ejem-

plo de lo anterior es el estudio de la implementa ión de algoritmos de ifrado ligero tipo

lightweight en dispositivos programables de software embebido (mi ro ontroladores) y en

dispositivos de hardware embebido (FPGA's).

A ontinua ión, se realiza una revisión de las ara terísti as relevantes de estos dispo-

sitivos, que para éste aso son: las herramientas de programa ión y veri� a ión, tenden ias

del mer ado, avan es en su arquite tura, desempeño, además de la genera ión de ódigo

estándar que se pueda usar en posteriores diseños.

Se toma omo base para el diseño, un sistema fun ional que se subdividirá en varios

subsistemas, lo ual umple on la metodología Top-Down [5℄.

El diseño de este sistema requiere una serie de fases, que pueden modi� arse según la

herramienta usada, en general tienen las siguientes ara terísti as [38℄:

• Des rip ión a nivel de sistema.

• Des rip ión a nivel de omportamiento .

• Valida ión (veri� a ión).

• Co-simula ión.

• Estima ión de desempeño.

Cuando se implementan ada uno de los distintos sub-sistemas que omponen el sistema

a nivel global, se eje utan los siguientes pasos para su respe tiva veri� a ión y de esta forma

es que se llega a un úni o sistema fun ional �nal. A lo anterior se le denomina etapa de

mapeo y parti ionamiento:

• Entrada espe i� a ión fun ional.

17

CAPÍTULO 2. PLATAFORMAS EMBEBIDAS DE DISEÑO 18

• Salida Arquite turas HW/SW.

• Me anismos de inter onexión.

• Fun iones optimizando osto, tiempo, área, omuni a ión.

• Síntesis hardware en los diferentes niveles de abstra ión.

• Síntesis software algoritmos simples, on urrentes.

• Síntesis de la interfaz a nivel de buses, me anismos de omuni a ión.

2.1. Diseño ESL

Ele troni System Level

El diseño de sistemas digitales en los últimos años ha tenido un salto enorme en la

omplejidad y apa idad de los sistemas, lo ual onlleva a que se utili en herramientas

y lenguajes de mas alto nivel, para poder ambiar las espe i� a iones de los diseños de

manera dinámi a.

Todas estas té ni as tienen que ver on tratar de plantear metodologías que dan solu-

iones a sistemas omplejos y donde se manejan iertos niveles de abstra ión para des ribir

estos sistemas [5℄; esta evolu ión de las herramientas y de los lenguajes usados, ha e que

el diseño de sistemas digitales tome un ará ter a nivel de sistemas [38℄, donde el uso de

los lenguajes omo C/C++ y el odiseño HW/SW ha e que se pueda rehusar ódigo y

librerías en apli a iones on alta omplejidad.

Todas estas herramientas ha en que la bre ha entre el hardware y el software se dismi-

nuya y que se puedan realizar solu iones donde onvivan las dos osas. En la gran mayoría

de los asos se expresa el algoritmo software en C/C++, lo que ha e que fá il y rápido el

tiempo usado para veri� ar el sistema.

En general la idea es llegar a sistemas que se puedan des ribir mediante lenguajes de

des rip ión de alto nivel, que permitan realizar parti iones HW/SW, aprove hando las

ventajas de los lenguajes tipo C/C++ (Depuradores, ompiladores, lenguajes estándar),

ademas de su fa ilidad para soportar diferentes niveles de abstra ión.

El ESL da soporte a la des rip ión de sistemas, usando lenguajes tipo C/C++ que

permiten el modelamiento tanto del software omo del hardware, aportando herramien-

tas omo el soporte de ve tores, on urren ia, sin roniza ión y manejo de ex ep ión, que

permiten que sean los mas ade uados para la des rip ión de ese tipo de sistemas.

2.1.1. Diseño Top-Down

Cuando se realizan desarrollos en sistemas digitales, una de las metodologías mas usadas

es la de parti ionar el diseño en subsistemas mas pequeños, partiendo desde una espe i�-

a ión fun ional hasta llegar a la realiza ión físi a de la te nología elegida [39℄.


Cuando se de�ne la espe i� a ión fun ional del sistema, se deben diseñar los subsis-

temas de tal manera que se permita la veri� a ión y depura ión de estos en las primeras

etapas de desarrollo.

El uso de una jerarquía de diseño en éste método des endente permite parti ionar el

sistema a diseñar en una serie de subsistemas de omplejidad redu ida omparados on el

original, que pueden ser espe i� ados y diseñados por diferentes grupos de trabajo[39℄.

Con el diseño se bus a el uso de estru turas regulares, ómo lo son los bloques RAM,

ROM y en general el uso de la ele tróni a digital bási a.

La metodología Top-Down permite la reutiliza ión de diseños y permite que el sistema

fun ional original sea usado omo un subsistema en un diseño mas omplejo. Di ha té ni a

requiere la de�ni ión y alma enamiento de librerías de diseño, así omo la reutiliza ión

de diseños genéri os parametrizables [38℄. La reutiliza ión de bloques permite aumentar la

on�abilidad de un nuevo diseño, al presentar omponentes probados y depurados, lo ual

redu e la posibilidad de errores y el tiempo de desarrollo [39℄.

Fases para la implementa ión de una apli a ión:

1. Fase de diseño.

Es la primera fase del desarrollo lógi o. Aquí se tienen en uenta los aspe tos involu-

rados en el diseño teóri o, desde la de�ni ión de las fun iones ne esarias a partir de

las espe i� a iones, hasta lograr una implementa ión de la solu ión a nivel digital.

Esta fase onlleva la realiza ión de las siguientes etapas:

• Planteamiento del problema: Consiste en dar una lara y ompleta des rip-

ión fun ional del problema a ser solu ionado, usando riterios que permitan

visualizar las ne esidades del requerimiento.

• Des rip ión: La des rip ión de los diferentes módulos HW puede ha erse de

diversas maneras, entre las uales están: e ua iones Booleanas, tablas de verdad,

diagramas de tiempo tabulados, tablas de estado, un lenguaje de alto nivel,

diagramas esquemáti os, diagramas de estado, et .

2. Fase de simula ión

Consiste en apli ar niveles a las entradas y probar las respuestas en las salidas,

para asegurar que el diseño lógi o de entrada opere orre tamente. En este paso se

generan los ve tores de diseño, los uales pueden ser derivados dire tamente de las

tablas de verdad, de los diagramas de tiempo o de la forma es ogida para des ribir

el sistema [39℄. En el aso de los algoritmos de ifrado por bloques y en general en

los desarrollos enfo ados a la riptografía, se requieren ve tores de prueba para ada

uno de las rondas y para el ifrador ompleto.

3. Parti ión

En esta etapa se de ide el tipo de implementa ión on la que se realizará el diseño;

se debe espe i� ar las entradas y salidas del sistema, ademas se debe de idir si el

módulo se desarrollará usando té ni as de hardware o software. Se bus a que los

subsistemas de hardware sean de baja omplejidad y los que se reali en en software


sean de mayor omplejidad. Además, se bus a que la interfaz de usuario sea de manejo

natural [39℄. Caben en la ategoría software, implementa iones de módulos on base

a mi ro ontroladores.

4. Fase de implementa ión

El diseñador debe ini ialmente sele ionar el tipo de te nología para la implementa-

ión de ada módulo [39℄. Los módulos des ritos en forma esquemáti a son dire ta-

mente implementables mediante el uso de lenguajes de des rip ión de hardware para

un PLD, o usando fun iones en lenguaje C para los mi ro ontroladores.

5. Do umento

Al �nalizar el pro eso de diseño e implementa ión de un sistema, se debe re opilar

la do umenta ión para ada una de las etapas. Esto es de gran importan ia para la

determina ión de posibles errores y problemas, además de permitir la abstra ión de

las fun iones de ada subsistema fun ional y de esa manera se pueda mantener y

orregir el diseño de manera simple y organizada [38℄.

2.1.2. Planea ión de tareas

Después de tener ada una de las tareas de los subsitemas, se requiere que el diseñador

reali e un esquema de planea ión de eje u ión, dejando laro en que instante de tiempo se

eje utarán las a iones.

En el aso del hardware, se requiere dejar laro la fun ión de ada uno de los bloques

y omo se logrará la sin roniza ión de los mismos, ya que ada uno de ellos se eje utan de

manera on urrente y se debe espe i� ar los tiempos de eje u ión de ada subsistema para

evitar errores de datos o eje u ión errónea del algoritmo [39℄. La manera mas fá il y que

umple on la metodología Top-Down es la de realizar un esquema de diseño tipo Data-

Path, en el ual, ada uno de los subsistemas es ontrolado por una máquina de estados

llamada unidad de ontrol que se en argará de realizar las a iones de sin roniza ión sobre

ada subsistema, hasta lograr la eje u ión del algoritmo de manera satisfa toria.

2.1.3. Co-diseño

Al tenerse sistemas heterogéneos que pueden ontener omponentes de Hardware y

software de manera independiente o ombinada, se requiere que el diseñador posea habi-

lidades en el uso de los lenguajes de programa ión omo C/C++ y HDL's[39℄, además,

se debe poseer la apa idad de dividir el sistema total en bloques fun ionales siguiendo

on la metodología Top-Down que al momento de tener el sistema totalmente espe i� ado

y diseñado, le permitan rear anales y formas de omuni a ión para veri� ar el orre to

fun ionamiento de estos dos omponentes, de manera independiente y ombinada.

En esta etapa de o-diseño se requiere un ono imiento de ada una de las plataformas

(Hardware y Software), para de esta manera generar los anales o rutas de omuni a ión

y veri� a ión entre éstas dos entidades que ha en parte del diseño digital moderno, para

este aso espe i� o, al implementar algoritmos de ierta omplejidad en las plataformas

anteriormente nombradas, se requieren herramientas o metodologías para el diseño, imple-

menta ión y genera ión de pruebas del diseño total.


En este aso, se generó un hardware tipo Data-path, que originalmente fue ontrolado

por una máquina de estados �nitos FSM y al �nal del trabajo se ontroló por un Soft-Core

libre, que fue implementado en el PLD y en ual se orrió un ódigo en C para realizar

pruebas de veri� a ión de fun ionamiento del sistema, además de tareas de omuni a ión

tanto on la plataforma embebida software omo on algunas pruebas realizadas on el uso

de un PC.

Por otro lado, uando se generó la solu ión tipo software embebido, se tuvo espe ial

uidado en realizar ada una de las partes o fun iones del mismo de tal manera que pudiera

ser implementado en una apli a ión de mas alto nivel, mediante el uso de fun iones y

métodos estándar que permitieren el uso de memoria dinámi a y reuso del ódigo. Todo

esto se planeó teniendo en uenta que al �nal del diseño se pudiera utilizar el ifrador

omo una librería que fuese llamada en otra apli a ión y a futuro en sistemas on RTOS

(Sistemas Operativos en Tiempo Real).

2.2. Plataformas soporte

Se estudiaron mi ropro esadores, mi ro ontroladores y PLD's aptos para portar el al-

goritmo PRESENT optimizado para este prototipo, teniendo en uenta la arquite tura,

pre io, ompiladores disponibles, lenguajes de programa ión soportados, memoria, velo i-

dad y fa ilidad de adquisi ión en Colombia [11℄.

2.2.1. Plataformas embebidas software

1. Multipro esador PROPELLER, del ual se ven las ara terísti as en la tabla2.1, es

un multipro esador produ ido por Parallax In . Posee una arquite tura úni a, que

ontiene o ho pro esadores que omparten pines de salida y re ursos. Cada uno de

los o ho pro esadores, ono idos omo COG, es de 32 bits [11℄.

Tabla 2.1: Cara terísti as del multipro esador PROPELLER

Microprocesador Propeller

Lenguaje Spin, Asm-Propeller

Soporta ANSI C/C++ No

Compilador Propeller Tool

Arquitectura Multinucleo

MIPS 20-160

Anchodel busdedatos 32bits

Memoria 2Kb RAM cada COG. 32Kb RAM 32Kb ROM

Velocidad de reloj 20 Mhz

Sistema de desarrollo Si

Empaquetado DIP 40 pines y QFN 44

Perifericos disponibles KeyBoard-Mouse PS/2, VGA, AUDIO,UART

Disponibilidad en el pais Si

Precio chip (COP) 30000

Fuente:Parallax In .


2. Mi ro ontroladores Mi ro hip PIC16F/PIC18F/PIC24FJ/PIC32, es una de las fa-

milias de dispositivos más usados en Colombia, en sus diferentes gamas y on todo

tipo de ara terísti as y empaquetados. En la tabla 2.2 se muestra una visión general

de los dispositivos produ idos por Mi ro hip In ., los uales, son de uso masivo en

el país. Además, varias empresas representan y distribuyen estos produ tos. Di hos

dispositivos tienen un amplio respaldo y las universidades poseen las li en ias de sus

ompiladores en C/C++, lo que ha e que sean muy atra tivos y de fá il uso. En

este aso se onserva una ompatibilidad en uando al uso de sus pines y lo mas

importante su ompilador es estándar para las familias 16F, 18F y 24F.

Tabla 2.2: Cara terísti as de los PIC's

Microprocesador PIC16F PIC18F PIC24FJ PIC32

Lenguaje ASM, C/C++ ASM, C/C++ ASM, C/C++ ASM, C/C++

Soporta ANSI C/C++ Si Si Si Si

Compilador Mplab XC8, Picc CCS Mplab C18, Picc CCS Mplab XC16, Picc CCS Mplab XC32

Arquitectura RISC Microchip RISC Microchip RISC Microchip MIPS

MIPS 5 10 20 124

Ancho del bus de datos 8 bits 8 bits 16 bits 32 bits

Memoria 0.5-2Kb RAM 1-32Kb ROM 0.5-4Kb RAM 1-96Kb ROM 2K-16Kb RAM 8-128Kb ROM 8K-32Kb RAM 32-512Kb ROM

Velocidad max de reloj 20 Mhz 40 Mhz 48 Mhz 80 Mhz

Sistema de desarrollo NO SI SI SI

Empaquetado DIP/SOIC/QFN DIP/SOIC/QFN DIP/SOIC/QFN TQFP/QFN/XBGA

Perifericos disponiblesUART,SPI, I2C,

ADC10Bit,PWMPIC16 + CAN, USB IGUAL PIC18F IGUAL PIC18F

Disponibilidad en el pais Si Si Si NO

Precio chip (COP) 5000-10000 13000-35000 13000-40000 5-10 USD

Fuente:Mi ro hip In ., Su onel, Sigma Ele tróni a

3. Mi ro ontroladores Atmel, son una de las familias más fuertes y signi� ativas en el

mer ado de 8 bits a nivel mundial, siendo la familia AVR una de las más signi� ativas

y on mejor arquite tura en esta gama, ésta ompañía fabri a los dispositivos ha e

ya varios años, pero en el último lustro ha mejorado bastante su ampo de a ión

gra ias a la in lusión del módulo Qtou h; en la tabla 2.3 se muestran algunas de sus

prin ipales ara terísti as.

Tabla 2.3: Cara terísti as de los AVR's

Microprocesador AVR Tiny AVR Mega AVR32

Lenguaje ASM, C/C++ ASM, C/C++ ASM, C/C++

Soporta ANSI C/C++ Si Si Si

Compilador AVR studio AVR studio AVR-GCC,Avr_OS, AVR Studio

Arquitectura RISC RISC RISC

MIPS 20 20 33

Ancho del bus de datos 8 bits 8 bits 32 bits

Memoria 0.5-2Kb RAM 2-8Kb ROM 1-16Kb RAM 16-128Kb ROM hasta 32Kb RAM 256Kb ROM

Velocidad max de reloj 20 Mhz 20 Mhz 66 Mhz

Sistema de desarrollo NO NO SI

Empaquetado DIP/SOIC/QFN DIP/SOIC/QFN LQFP

Perifericos disponibles UART,SPI, I2C, ADC10 bits Igual Tiny + PWM, Qtouch,RTC QTOUCH, UART, SPI, ADC12

Disponibilidad en el pais Si Si Si

Precio chip (COP) 2500-5000 5000-23000 15000-27600

Fuente:Atmel In ., Sigma Ele tróni a


4. Texas Instruments, históri amente una de las ompañías mas grandes y on mayor

experien ia en la produ ión de mi ro ontroladores, tiene una familia que ha sido

bastante fuerte, en uanto al manejo y onsumo de poten ia omo lo es el MSP430,

además de esto, di ha empresa a adquirido la li en ia del nú leo ARM y a puesto una

serie de periféri os y hardware adi ional, on varios sistemas de desarrollo bastante

e onómi os. En la tabla 2.4 se muestra un listado de sus ara terísti as.

Tabla 2.4: Cara terísti as de los Texas

Microprocesador MSP 430 TI Stellaris

Lenguaje ASM, C/C++ ASM, C/C++

Soporta ANSI C/C++ Si Si

Compilador IAR Kic start, Code Composer IAR Kic start, Code Composer

Arquitectura RISC ARM Cortex M

MIPS 16 0

Ancho del bus de datos 16 bits 32 bits

Memoria 0.5Kb RAM 8-16Kb ROM hasta 32Kb RAM 256Kb ROM

Velocidad max de reloj 16 Mhz 80 Mhz

Sistema de desarrollo SI SI

Empaquetado DIP/SOIC LQFP

Perifericos disponiblesUART,SPI, I2C, ADC10 bits,

IrDA, ultra lo po er

igual MSP 30 + 8 UART, I2C,

SPI, US

Disponibilidad en el pais Si Si

Precio chip (COP)-KIT 2500-3 000 3 000-82000

Fuente:Texas In ., Ele tronilab. o

5. Cypress Semi ondu tors, es una de las ompañías que más ha in ursionado en el

mer ado de éstos dispositivos en los últimos años, gra ias a la versatilidad de sus

dispositivos, tiene la gran ventaja de poseer bloques re on�gurables análogos y digi-

tales, lo que ha e que sea perfe to para trabajo on señales mixtas y le permite tener

un sin número de periféri os según las ne esidades del usuario. Di has ara terísti as

se muestran en la tabla 2.5. Estos bloques re on�gurables apare en desde la familia

Pso 1 de 8 bits, junto on las familias Pso 4 y Pso 5 al adquirir la li en ia de los

nú leos ARM ortex M0 y M3 respe tivamente, lo que lo ha e ompatible en uanto

a las herramientas de programa ión, librerías y RTOS.

6. FreeS ale, a tualmente ha sido una de la empresas on mayor in lusión de periféri os

y módulos extra en sus hips y sus sistemas de desarrollo. En la tabla 2.6 se muestran

dos de sus sistemas de desarrollo más desta ados on distribu ión en el país de bajo

osto, tomando en uenta sus módulos y fun ionalidades. Por otro lado, un ítem

importante y que lo ha e muy atra tivo, es su proto olo de programa ión tipo SDA,

el uál le permite ser dete tado omo un dispositivo de alma enamiento masivo y la

programa ión del dispositivo úni amente se resume a mover un ar hivo a su arpeta.

Una de las ara terísti as que ha e que estos sistemas de desarrollo sean espe ialmen-

te atra tivos, es que son parti ipes del proye to Mbed (www.mbed.org), el ual da

fa ilidades de programa ión por su ódigo libre y abierto, el ual no requiere li en ia,

ya que su ompilador es online. Éste proye to tiene la gran ventaja de soportar múlti-

ples plataformas ARM, ha iendo que el ódigo sea totalmente portable, tomando las


Tabla 2.5: Cara terísti as de los Pso 's

Microprocesador PS PS 4 PS

Lenguaje ASM, C ASM, C/C++ ASM, C/C++

Soporta ANSI C/C++ Si Si Si

Compilador Psoc Creator, Psoc Designer Psoc Creator, Psoc Designer Psoc Creator, Psoc Designer

Arquitectura SISC Cypress M8C Core ARM Cortex M0 ARM Cortex M3

MIPS 6 8 80

Ancho del bus de datos 8 bits 32 bits 32 bits

Memoria 0.5-2Kb RAM 1-16Kb ROM 16k b RAM 128Kb ROM 32Kb RAM 512Kb ROM

Velocidad max de reloj 2 Mhz 8 Mhz 80 Mhz

Sistema de desarrollo NO SI SI

Empaquetado DIP/SOIC/TQFP SOIC/TQFP TQFP

Perifericos disponibles6 Analog loc s, Digital

loc s, Cap Sense, Mosfetigual Psoc 1 + CAN, US igual Psoc + LCD Drive, DMA

Disponibilidad en el pais No Si No

Precio chip - it (COP) 5000-20000 28000-62500 65000- 00000

Fuente:Cypress Semi ondu tors, Ele tronilab. o

ventajas de CMSIS y ha iendo que sea totalmente transparente para el programador.

En otra palabras, el ódigo que se reali e mediante éste ompilador es absolutamente

portable a mas de 20 plataformas on pro esadores de arquite tura ARM de por lo

menos 5 diferentes ompañías fabri antes de hips.

Tabla 2.6: Cara terísti as de los Frees ale

Microprocesador M M 0 0

Lenguaje ASM, C/C++ ASM, C/C++

Soporta ANSI C/C++ Si Si

Compilador Mbed, Code Warrior, IAR, uVision Mbed, Code Warrior, IAR, uVision

Arquitectura ARM Cortex M0 ARM Cortex M

MIPS 8 50

Ancho del bus de datos 32 bits 32 bits

Memoria -16Kb RAM 16-128Kb ROM SDA 32 b RAM 128Kb ROM SDA

Velocidad max de reloj 8 Mhz 50 Mhz

Sistema de desarrollo SI SI

Empaquetado LQFP LQFP

Perifericos disponiblesUART,SPI, I2C, ADC16 it,2 PWM,

Qtouch, Acelerometro, US , US -Serie

Igual al KL25 + Sensor de temperatura,

Sensor de luz

Disponibilidad en el pais SI Si

Precio chip - it (COP) 5000- 8000 10000-63000

Fuente:Frees ale In , Ele tronilab. o

2.2.2. Plataformas embebidas Hardware

El análisis de las posibilidades de los posibles dispositivos usados para realizar la imple-

menta ión en hardware embebido tipo FPGA es mu ho mas orta, ya que la ompeten ia


sólo se resume a dos empresas que tienen el 90% del mer ado mundial.

Ésta rivalidad se ha extendido por tres dé adas y tras iende en el tiempo, mostrando

los resultados de las ifras de la apitaliza ión bursátil a nivel mundial, para Xilinx USD

13.77 millardos y para Altera USD 11.4 millardos. Sin embargo, el diseño de FPGA no

depende de la apitaliza ión de mer ado, pero seria bueno revisar la uota de ventas de

Xilinx que esta entre 45% y el 50% y la Altera esta entre el 40% y el 45%. Es de ir,

que las dos ompañías han aplastado onstantemente a todos los ompetidores, pasando

de un 80% de uota a umulada al 90% de hoy. Otro fa tor importante es el grado de

integra ión de los los hips, el ual habla del tamaño en nano metros del los transistores

que forman los dispositivos. En éste ítem las ompañías han tenido un onstante adelanto

durante los últimos nodos de pro eso; Altera fabri o te nología de 40/45nm, después Xilinx

28nm y 20nm, pero para 2015, los dispositivos in luyeron te nología de 16nm y 14 nm.

Por otro lado, o urrió algo que ambia el enfoque de los dispositivos en las dos ompañías,

ya que las dos adquirieron las li en ias de ARM espe í� amente de la familia Cortex AX,

que serán in luidos en mu hos dispositivos, pero para este aso no omo soft ore (lo que

era a ostumbrado) sino omo nú leos en sili io real dentro del dispositivo, aunque esto

in rementará el osto del mismo. Por otro lado es importante veri� ar la versatilidad de la

herramienta y los lenguajes de des rip ión de hardware usados; aunque este punto ya fue

tratado anteriormente, mediante las té ni as de diseño ESL y la metodología Top-Down,

es importante remar ar la importan ia y uso de las herramientas para tomar la de isión

de ual de las dos te nologías usar en este punto. Xilinx tiene una gran desventaja por

los problemas que posee la herramienta ISE, su inestabilidad en uanto a los ambios

realizados en sus distintos ar hivos y las di� ultades en el momento de la simula ión.

De otra manera, la plataforma Quartus II de Altera siendo la segunda genera ión de este

software, tiene depurados los problemas que se generaron en la primera versión, pero al �nal

la gran diferen ia entre éstas herramientas está en el uso de plantillas y el uso de nú leos

de propiedad intele tual (IP). A riterio personal la herramienta ISE supera ampliamente

a Quartus II, por la antidad y alidad de las IP's disponibles y la fa ilidad de uso.

Al �nal, aunque la arquite tura y ara terísti as de los dispositivos y el uso de he-

rramientas son iertamente distintos para ada fabri ante, tienen similitudes que en el

momento de la implementa ión ha en que el fun ionamiento sea similar. Lo importante

es que el diseño del sistema en el lenguaje de des rip ión de hardware sea totalmente es-

tándar, evitando el uso de las IP's o ualquier otra ara terísti a que evite que se pueda

implementar el diseño en ualquiera de los dispositivos de las dos ompañías. En otras

palabras, la idea es des ribir el algoritmo usando lenguajes de des rip ión de hardware, de

tal manera, que el ódigo resultante se pueda exportar al dispositivo de la ompeten ia sin

ningún in onveniente.

Para este aso se de ide realizar una des rip ión del ifrador por bloques usando el

lenguaje de des rip ión de hardware VHDL (VHSIC Hardware Des ription Language), el

ual es estándar para dispositivos de ualquier gama, tanto Altera omo Xilinx y se de ide

usar omo herramienta de diseño e implementa ión el ISE de Xilinx, que aunque tiene

bastantes limitantes es totalmente libre en su versión estudiantil, además por el simple

he ho que la universidad Distrital posee sistemas de desarrollo de baja y media gama que

son de bajo osto omparados on la ompeten ia, di hos dispositivos son las Spartan 3E

y Spartan 3AN de Xilinx. Igual se re al a, que gra ias a que el lenguaje de des rip ión de

hardware es estándar y la des rip ión realizada es genéri a no existe ningún in onveniente


en exportar el ódigo fuente a otro dispositivo de gamas superiores en el mismo fabri ante

o pasar a dispositivos de la ompeten ia.

2.3. Argumento �nal

Después de realizar una revisión que se ve eviden iada en la se ión anterior y veri-

� ando la mayoría de plataformas embebidas software disponibles en el país, se de ide

realizar la implementa ión en varios dispositivos, para tener parámetros de medi ión en

uando al tamaño del bus del pro esador. Se elige usar para familias de 8 y 16 bits de los

mi ro ontroladores de la empresa Mi ro hip TM, espe í� amente la familia 16F, 18F para

8 bits y la familia 24F para un bus de 16 de bits de palabra; se toma esta de isión teniendo

en uenta que el ompilador es estándar para C/C++, además de que se permite rápida

veri� a ión gra ias al poder de sus simuladores y herramientas de desarrollo. Mi ro hip

a tualmente es la empresa de mayor difusión a nivel mundial en 8 bits y su ompilador

ha sido adquirido por la universidad Distrital y es totalmente ompatible en uanto a el

lenguaje en sus diferentes familias y todos los dispositivos son ompatibles pin a pin on

los de gamas anteriores; en uanto a las familias de 32 bits se sele iona el mi ropro esador

ARM Cortex-M0 sobre la tarjeta de desarrollo mbed KL 25Z, debido a que el tiempo de

desarrollo del prototipo se puede ver redu ido por la apa idad de su ompilador en línea

que soporta C/C++ junto on el manejo de apuntadores, asigna ión dinámi a de memoria,

ontrol de versiones on mer urial/git y formateo de ódigo. Su osto, antidad de módulos

y fa ilidad de programa ión, superan a ualquier otro dispositivo de esta gama.

De igual forma la fa ilidad de montaje de las distintas tarjetas de desarrollo y su

tamaño, permiten su uso sobre tarjetas para prototipos o protoboards, brindando una

mayor versatilidad para la eje u ión de pruebas de periféri os y omponentes externos que

amplíen sus fun iones.

Se realza la importan ia del ompilador para ARM Mbed ya que ofre e estadísti as al-

uladas en tiempo de ompila ión, de uso de memoria del ódigo y las variables onstantes

en la FLASH, así omo del tamaño de las variables que puedan terminar en la RAM. Ade-

más, la velo idad de trabajo del pro esador así omo los re ursos de memoria, permiten la

implementa ión del ifrador por bloques on holgura.

La omunidad mundial que soporta el desarrollo de ésta herramienta permite a los

nuevos usuarios utilizar una gran base de datos de informa ión y bibliote as para la tarjeta

ARM de desarrollo, siendo una ayuda muy importante para proye tos de prototipado

rápido.

En uanto a la plataforma embebida hardware tipo FPGA se de ide trabajar on Xilinx

usando la herramienta de desarrollo ISE y usando FPGA's de bajo osto omo las Spartan

3AN y Spartan 3E, las uales están en por lo menos dos sistemas de desarrollo diferentes que

se trabajan en la Universidad Distrital Fran is o José de Caldas. Es de gran importan ia

re al ar que aunque no se planea realizar pruebas en dispositivos de Altera, se realizará

una diseño en el lenguaje de des rip ión de Hardware VHDL, de tal manera que el ódigo

resultante sea totalmente ompatible on ualquier FPGA de ualquier gama y fabri ado

por ualquier ompañía.

CAPÍTULO 3

Metodología, diseño y resultados

Después de elegir la te nología, sistemas de desarrollo y lenguaje a usar, se debe tener

en uenta los parámetros para veri� ar ada una de la plataformas embebidas. En este

aso, para la medi ión de los resultados de la implementa ión del algoritmo de ifrado en

bloque PRESENT, sobre los diferentes mi ro ontroladores y también los dispositivos del

lógi a programable tipo FPGA, se utilizó la fun ión de ifrado y des ifrado on tamaños

de llave de 80 bits, probando su fun ionamiento on los ve tores de prueba estable idos

on tamaños de bloques de datos de 64 bits.

Para ada tipo de plataforma se deben de�nir iertas métri as, para las plataformas

embebidas software tipo mi ro ontrolador se toman en uenta el uso de memoria de pro-

grama (FLASH), uso de memoria de datos (RAM) y throughput ; todo esto tomando en

uenta el tamaño del bus del pro esador y si el pro esador tiene apuntadores a fun iones

o tablas y la velo idad de la CPU medida en millones de instru iones por segundo MIPS.

En uanto a las plataformas embebidas hardware, los parámetros de medi ión son

totalmente diferentes, en este aso el throughput es signi� ativamente superior por la

ara terísti a de paralelismo de los dispositivos, pero se bus a la redu ión del uso de

re ursos en uanto a los Sli es o upados (CLB-GE); estos Sli es o bloques fun ionales son

diferentes para ada ompañía, lo que los ha e difí iles de omparar.

3.1. Modelo del algoritmo

A ontinua ión se muestran los detalles de las distintas implementa iones y la medi ión

de las métri as estable idas para ada tipo de plataforma embebida.

3.1.1. Implementa ión plataforma embebida software - mi ro ontrolador

En todos los ifradores de bloque se genera una ombina ión de opera iones que es

llamada ronda. La omplejidad y seguridad del algoritmo depende de la ombina ión de

éstas opera iones bási as y de la antidad de rondas realizadas a la informa ión a ifrar.

Cada ronda está ompuesta por uatro opera iones basadas en transforma iones uniformes

27

CAPÍTULO 3. METODOLOGÍA, DISEÑO Y RESULTADOS 28

e invertibles que son llamadas apas, las uales se diseñan para resistir ante el riptanálisis

lineal y diferen ial.

Implementa ión del algoritmo

Analizando la estru tura de Present, las diferentes implementa iones do umentadas

del mismo y la proye ión a una implementa ión propia del algoritmo, es posible resumir

la eje u ión del mismo en un simple pseudo ódigo ompilable en ualquier plataforma

embebida software, ya sea de 8, 16 o de 32 bits de la siguiente forma:

generateRoundKeys()

for i=1 to 31 do

addRoundKEy(STATE,Ki)

SBoxLayer(STATE)

pLayer(STATE)

end for

addRoundKey(STATE,K32)

[10℄

Para ada una de las líneas de pseudo ódigo se debe rear una fun ión o método que

reali e las opera iones bási as de los algoritmos de ifrado en bloque, teniendo en uenta

la antidad de bits de la lave; además se requiere ha er una revisión exhaustiva de uál

es la mejor manera de programar ada una de las opera iones del algoritmo.

A ontinua ión, se muestra los nombres de las fun iones generadas en lenguaje C, que

umplen on ada una de esas fun iones; ada parte de este ódigo se realizó de manera

estándar, de tal manera que orra en distintas plataformas embebidas software.

bool read_bit_n_bits(unsigned int *datap, int index);

void write_bit_n_bits(unsigned int*datap, bool val, int index);

void p_layer( void );

void s_box_layer( void );

void data_update( void );

void key_update( void );

void data_xor_key( void );

Ya que éste algoritmo tiene algunas opera iones que requieren mez la y sustitu ión

de bits, se requirió diseñar un par de fun iones que permitan leer (fun ión read) y es ri-

bir(fun ión write) sobre un bit de una posi ión de memoria en espe í� o; estas fun iones se

ajustaron al an ho del bus del pro esador y se es ribieron de manera diferente teniendo en

uenta si el pro esador tiene unidad para opera iones orientadas a bit. El resto de fun iones

umplen la espe i� a ión del algoritmo pero requieren diferente uso de las variables y sus

respe tivos enmas aramientos según el an ho del bus del pro esador.

El ódigo en lenguaje C, fue es rito y probado para varias plataformas; ini ialmente

se es ribió para un PC y se realizaron pruebas on su entorno grá� o veri� ando on su

respe tivo test de prueba (�gura 3.1). A ontinua ión se realizaron pruebas en algunos dis-

positivos de la empresa Mi ro hip de 8 bits (16FXXX y 18FXXX) on y sin apuntadores

internos, después en una familia de dispositivos de 16 bits (24FJXXX) y al �nal en un

mi ro ontrolador on arquite tura ARM Cortex-M0 (KL25Z128) de la empresa FreeS ale.

Di has pruebas se realizaron transmitiendo los datos por la UART del pro esador y veri-


� ando los tiempos, midiendo la fre uen ia por un pin de salida del mi ro ontrolador; en

el aso del pro esador de 32 bits se veri� ó el reloj del sistema para tomar esta métri a.

Figura 3.1: Pruebas en el PC.

Después de ha er las pruebas en ada plataforma embebida, se veri� ó el orre to

fun ionamiento del algoritmo para todos ellos, tanto en el pro eso de ifrado omo de

des ifrado; se sele ionaron algunos parámetros de medi ión on el �n de tener una es ala de

ompara ión para el rendimiento de ada apli a ión en los diferentes dispositivos. En primer

lugar, se sele ionó omo parámetro base la antidad de memoria requerida de programa

(FLASH) y memoria de datos (RAM). Después se veri� ó la antidad de informa ión

ifrada medida en mensajes por segundo y bits por segundo. De este modo se observa que

el dispositivo pueda gestionar el an ho de banda ne esario para algunos WSN. En la tabla

3.1 se muestran los resultados para los diferentes dispositivos que tienen 8, 16 y 32 bits de

an ho de bus del pro esador.

Tabla 3.1: Parámetros de rendimiento de las implementa iones

MicrocontrollerProgram Memory

Flash (bytes)

Memory Data

RAM (Bytes)

Throughtput

Message/secondThroughtput bps Pointer MIPS

Binary

Operator

8 bits 2210 73 12 768 no 5 yes

16 bits 2129 768 12,12 775,68 yes 5 yes

16 bits 3276 245 18,8 1203,2 yes 10 no

32 bits 20,5K 600 234 14976 yes 48 no

Fuente:Autor

Es importante desta ar que la implementa ión del ifrador en el lenguaje C, on peque-

ñas modi� a iones, es totalmente ompatible on las diferentes arquite turas; espe ialmen-

te on las realizadas para mi ro ontroladores ARM de 32 bits; implementa ión de la ual


no se ha en ontrado ante edente alguno en la bibliogra�a a nivel mundial, la ual tiene

un rendimiento signi� ativamente superior a las implementa iones en otras plataformas

embebidas software.

3.1.2. Implementa ión plataforma embebida hardware - FPGA

Para la implementa ión del ifrador implementado en una plataforma embebida hard-

ware tipo FPGA, se requiere apli ar la metodología Top-Down, realizando ada uno de los

bloques y al �nal utilizar una máquina de estados para ontrolar di hos bloques; al �nal

se tendrá un ódigo que se podrá importar omo librería en un diseño de mas alto nivel

omo un bloque fun ional; a ontinua ión se muestra algunos diagramas que son los mas

signi� ativos del diseño, bus ando el in remento en el throughput pero tratando de redu ir

el uso del dispositivo en uanto a uso de sli es, que no son mas que el re urso bási o de

ualquier dispositivo programable en ampo.

Implementa ión del algoritmo

Se diseñaron, probaron e implementaron ada uno de los bloques fun ionales tanto del

ifrador omo del des- ifrador; a ontinua ión en la �gura 3.2 se muestra un diagrama de

bloques, que se toma dire tamente de la herramienta ISE de Xilinx, el ual muestra omo

se unen todos los bloques desarrollados en VHDL para el ifrador PRESENT.

Figura 3.2: Datapath real ifrador en VHDL

Se des ribió ada uno de los bloques en bajo nivel tratando de usar el menor re urso

posible, ada bloque fue simulado y probado antes de realizar la unión de los mismos,


para seguir on la metodología y garantizar el orre to fun ionamiento del sistema, si

todos y ada uno de los bloques fun iona, pero la unidad de ontrol del sistema presenta

fallos, el fun ionamiento del sistema se vería omprometido. A ontinua ión en la �gura

3.3 se mostrará la máquina de estados que hará las ve es de unidad de ontrol del sistema,

realizando el manejo de todas las señales y lo mas importante, de los onteos y veri� a ión

de que la salida del sistema es la indi ada.

Figura 3.3: Máquina de estados de la unidad de ontrol del ifrador

Para la �gura3.3 el sistema está en reposo hasta que se genere una señal de ini io,

después en el siguiente estado se debe generar la arga tanto de la lave omo del text a

ifrar; el ontador de rondas debe arran ar en ero, inmediatamente después se debe pasar

a un estado de ifrado donde se realizan las 30 rondas restantes, las uales mez lan la lave

y la informa ión olo ando los multiplexores en uno para que la salida se retroalimente

on el estado anterior; el ontador de rondas debe estar totalmente sin ronizado, ya que

si al menos se pierde un i lo de reloj o se mez la la lave on un onteo erróneo todo el

pro eso de ifrado de los datos se dañaría, debido a que los bloques S-box layer y P-layer

al ha er permuta iones y ombina iones expanden el error de al menos un bit sobre toda

la informa ión tratada. Al �nal se da un estado de �n el ual genera una señal de salida

que se sin roniza para dar la orden de arga o salida de los datos sobre un posible bloque

de transmisión o alma enamiento de los datos ifrados.

Después de tener el ódigo en su totalidad y teniendo en uenta los ve tores de prueba

dados, se pro ede a realizar una simula ión del sistema ompleto; di ho pro eso se muestra

en la �gura 3.4. Es importante re al ar que al ser un algoritmo de alta omplejidad y al no

tener puntos intermedios en los test de prueba, el pro eso de depura ión y veri� a ión fue

bastante largo y dispendioso; esta tarea requiere el re-diseño de ada uno de los bloques y

de la unidad de ontrol para ada paso.

Esta simula ión después de ser exitosa, sirvió omo ayuda en el diseño de software

embebido, ya que el paso a paso de las rondas permite veri� ar el pro eso de ifrado en

puntos intermedios y realizar depura ión en ada una de las rondas.


Figura 3.4: Simula ión paso a paso de la implementa ión hardware

Al tener la implementa ión ompleta, se realizó una medi ión del hardware usado en

ada bloque fun ional de la des rip ión y se ompara on la del referente realizada por las

personas que plantearon el algoritmo [10℄; se determina que tiene una mejora del 26.89%

en uanto al uso de hardware.

Tabla 3.2: Tabla omparativa entre implementa ión de referen ia y la propia

Fuente:Autor

Uno de los aportes mas importantes es el mejoramiento del throughput del sistema

general, el ual se puede omparar dire tamente on una tabla dada por los autores del

algoritmo [10℄ y que se muestra a ontinua ión en la tabla 3.3.

Espe í� amente el análisis se enfo a en el algoritmo PRESENT-80, en el ual el th-

roughput del sistema que para el autor es de 200 Kbps a 100 Khz y se ompara on el

nuestro, de a uerdo al parámetro del máximo retardo de 6.865 ns lo que equivale a que el

diseño fun iona a un máximo de 291200 Kbps a 145.6 Mhz, tomando en uenta que ada

ronda dura un i lo de reloj; enton es se tiene que son 32 i los de reloj del sistema y

ademas en ada bloque se trabajan on 64 bits de informa ión.


Tabla 3.3: Tabla omparativa de algunos algoritmos de ifrado

Fuente:[10℄

Throughput Aprox =Maxima tasa envio

Cantidad rondas=

145,6Mhz

32 rondas= 4,55MegaMensajes/segundo

(3.1)

Maxima taza de envio en Kbps =4,55M men/s

64bits= 291200Kbps (3.2)

Con base en las e ua iones anteriores se re�eja un in remento en desempeño del 1456%.

Claro que los readores del algoritmo [10℄ se enfo aron en la viabilidad del algoritmo

más que en su desempeño, por esto se ve la mar ada diferen ia.

CAPÍTULO 4

Con lusiones y aporta iones

4.1. Con lusiones

Present es un algoritmo ultra-ligero de ifrado por bloques. Posee uno de los métodos

de en ripta ión más ompa to y ademas, en uanto al tamaño de referen ia, es el más

pequeño de los a tuales esquemas de en ripta ión. Debido a estas ara terísti as en su

estru tura, ha despertado gran interés en apli a iones de investiga ión altamente e� ientes

omputa ionalmente on exigen ias de bajo onsumo de energía. Ésta investiga ión en par-

ti ular, se entró en en un estudio de desempeño sobre diferentes plataformas de hardware

y software, on la inten ión de en ontrar ondi iones fun ionales ideales para apli a iones

de alto desempeño. Se logró un total de uatro implementa iones a medida, sobre uatro

diferentes mi ro ontroladores de hardware �jo, uatro arquite turas del algoritmo espe i-

� as para diferentes grados de exigen ia y una implementa ión sobre FPGA en hardware

re on�gurable que demostró una velo idad de opera ión mas de 1000 ve es superior a la

previamente reportada.

Di has implementa iones requieren el estudio de on eptos previos de aritméti a en

ampos �nitos, opera iones bási as de todo algoritmo riptográ� o, in luido Present. Ésto

requirió el estudio y análisis de ara terísti as espe i� as tales omo la antidad de rondas,

el tamaño de las laves, los tamaños de los bloques de ifrado, el tamaño de las variables,

tablas, los ve tores de sustitu ión y el ál ulo para el menor uso en antidad de memoria

sin sa ri� ar el número de i los de reloj ne esarios para realizar ada una de las rondas

del algoritmo. A partir de lo anterior y ono iendo a fondo la arquite tura interna de los

dispositivos de hardware (hardware �jo, tanto estru tura omo ara terísti as parti ulares)

y software(aquellos de hardware re on�gurable), se realizó un análisis de diseño optimo a

�n de bus ar el mayor aprove hamiento de re ursos disponibles en ada implementa ión.

Gra ias a ello, se obtuvieron sistemas de 8, 16, 32 y 64 bits diseñados a medida y on osto

omputa ional inferior al previamente reportado en las investiga iones do umentadas.

Es importante resaltar que en las investiga iones realizadas previamente a este proye to

sobre este tema, no fue posible en ontrar implementa ión alguna reportada de este algo-

ritmo sobre mi ro ontroladores de 32 bits, lo que ha e de éste trabajo sea úni o. Ademas,

en uanto a la implementa ión sobre FPGA, si bien existen implementa iones previas, ésta

34

CAPÍTULO 4. CONCLUSIONES Y APORTACIONES 35

reporta una redu ión del 26% en uanto al hardware utilizado gra ias al estudio interno

del algoritmo y la arquite tura �nal. Ademas, ésta implementa ión permite odi� a ión

estándar y mantiene la posibilidad futura del uso de herramientas de altísimo nivel para

des rip ión de hardware, o de generadores automáti os de ódigo C para a elerar el tiempo

de desarrollo del algoritmo, sin dejar de lado la �losofía lightweight.

4.2. Aportes originales

Los aportes originales de esta investiga ión se pueden resumir en:

• Redu ión del uso de hardware signi� ativa frente a implementa iones previas sobre

FPGA. La implementa ión en hardware utilizando lenguaje de des rip ión VHDL es-

tándar logró una redu ión del 26,89% en uanto a uso de re ursos sobre una FPGA

Spartan 3AN de Xilinx. Es importante resaltar que la implementa ión de referen-

ia utiliza VHDL estándar, ser repli ada sobre ualquier FPGA de otro fabri ante,

esperando redu iones equivalentes sobre ellos.

• Código tipo CORE (hardware) o librería (software) totalmente estándar para dife-

rentes familias de dispositivos, que se pueden usar de manera simple en apli a iones

reales. Esto también es posible para otros fabri antes de FPGA diferentes a Xilinx.

• Implementa ión y pruebas en varias familias de dispositivos tipo mi ro ontrolador

(de 8, 16 y 32 bits). Se desarrolló un ódigo en C totalmente estándar para di has

familias y que también puede ser utilizado sobre omputadores. Teniendo en uenta

que la implementa ión sobre arquite tura de 32 bits se realizó sobre la familia mas

usada en el mer ado a tualmente, la Cortex M0 de ARM, on un trhoughtput tan

alto que permite su uso en apli a iones reales.

• La implementa ión en mi ros de 16 y 32 es ompletamente inédita. No existe do u-

menta ión de apli a iones similares previas a esta investiga ión. Además, on la de

32 bits se logra un trhoughtput que es usable en las apli a iones de redes de sensores

y apli a iones para las uales está diseñada el algoritmo.

4.3. Trabajo futuro

A partir de esta investiga ión, se plantean los siguientes trabajos futuros, algunos de

los uales ya se en uentran en desarrollo por parte del grupo de investiga ión:

• Implementa ión del sistema de en ripta ión sobre una red de sensores y desarrollo

de las pruebas en apli a iones ompletas.

• Realiza ión de otros algoritmos de ifrado por bloques tipo lightweight (a tualmente

se esta trabajando on HIGHT, del ual ya existen resultados).

• Compara ión on diferentes algoritmos de ifrado en bloque sobre plataformas hard-

ware y software.

CAPÍTULO 4. CONCLUSIONES Y APORTACIONES 36

• Realiza ión de una HSM on una on�gura ión diferente a la implementada anterior-

mente, tanto en software omo en Hardware.

• Publi a ión de tres artí ulos adi ionales respe to al trabajo de esta investiga ión.

Bibliografía

[1℄ N. Pineda and N. Velasquez, �Diseño e implementa ión de un prototipo riptopro e-

sador aes-rijndael en fpga,� Master's thesis, Universidad de Los Llanos, 2007.

[2℄ R. Cardenas, Criptologia, U. Distrital, Ed. Universidad Distrital, 2012, vol. 1, no. 1.

[3℄ E. Kavun, G. Leander, and T. Yal ind, �A re on�gurable ar hite ture for sear hing

optimal software ode to implement blo k ipher permutation matri es,� in Re on�-

gurable Computing and FPGAs (ReConFig), 2013 International Conferen e on, 2013,

pp. 1�8.

[4℄ N. Sklavos, �Cryptographi hardware & embedded systems for ommuni ations,� in

Satellite Tele ommuni ations (ESTEL), 2012 IEEE First AESS European Conferen e

on, 2012, pp. 1�6.

[5℄ A. Delgadillo, N. Pena, and M. Guerrero, �Diseno de un riptosistema para redes

de sensores inalambri os wsn basado en mpso ,� Master's thesis, Universidad de los

Andes, 2008.

[6℄ F. Chih-Peng and H. Jun-Kui, �Implementations of high throughput sequential and

fully pipelined AES pro essors on FPGA,� in International Symposium on Intelligent

Signal Pro essing and Communi ation Systems ISPACS 2007, 2007, pp. 353�356.

[7℄ J. Attridge, �An overview of hardware se urity modules,� SANS Institute, InfoSe

Reading Room, vol. 1, no. 1, pp. 1�10, 2002.

[8℄ H. A. Alkhzaimi and M. M. Lauridsen, �Cryptanalysis of the simon family of blo k

iphers,� Te hni al University of Denmark, vol. 1, no. 1, pp. 1�26, 2013.

[9℄ P. Yalla and J. Kaps, �Lightweight ryptography for FPGAs,� in Re on�gurable Com-

puting and FPGAs, 2009. ReConFig '09. International Conferen e on, 2009, pp. 225�

230.

[10℄ A. Bogdanov, L. Knudsen, G. Leander, and C. Paar1, PRESENT: An Ultra-

Lightweight Blo k Cipher. Springer-Verlag Berlin Heidelberg, 2007, h. 5, pp. 450�466.

[11℄ R. Azuero, E. Ja into, and J. Castano, �A low-memory implementation of 128 aes for

32 bits ar hite tures.� in En Congreso Argentino de Sistemas Embebidos CASE 2012,

2012, pp. 67�73.

37

BIBLIOGRAFÍA 38

[12℄ M. Kumar and A. Singhal, �E� ient implementation of advan ed en ryption stan-

dard (AES) for arm based platforms,� in Re ent Advan es in Information Te hnology

(RAIT), 2012 1st International Conferen e on, 2012, pp. 23�27.

[13℄ K. M. Abdellatif, R. Chotin-Avot, and H. Mehrez, �Lightweight and ompa t solu-

tions for se ure re on�guration of FPGAs,� in Re on�gurable Computing and FPGAs

(ReConFig), 2013 International Conferen e on, 2013, pp. 1�4.

[14℄ J. Pospiil and M. Novotny, �Evaluating ryptanalyti al strength of lightweight ip-

her present on re on�gurable hardware,� in Digital System Design (DSD), 2012 15th

Euromi ro Conferen e on, 2012, pp. 560�567.

[15℄ E. Kavun and T. Yal in, �RAM-based ultra-lightweight FPGA implementation of

present,� in Re on�gurable Computing and FPGAs (ReConFig), 2011 International

Conferen e on, 2011, pp. 280�285.

[16℄ Z. Gong, S. Nikova, and Y. W. Law, �Klein: A new family of lightweight blo k iphers,�

RFID Se urity and Priva y RFID Se 2011, vol. 1, no. 1, pp. 1�18, 2011.

[17℄ T. Eisenbarth and S. Kumar, �A survey of lightweight- ryptography implementations,�

IEEE Des Test Comput, vol. 24, no. 6, pp. 522�533, 2007.

[18℄ D. Huang and H. Kapoor, �Towards lightweight se ure ommuni ation proto ols for

passive RFIDs,� in Sensor, Mesh and Ad Ho Communi ations and Networks, 2009.

SECON '09. 6th Annual IEEE Communi ations So iety Conferen e on, 2009, pp. 1�9.

[19℄ A. Aysu, E. Gul an, and P. S haumont, �SIMOn says: Break area re ords of blo k

iphers on FPGAs,� IEEE Embedded Systems Letters, vol. 6, no. 2, pp. 37�40, 2014.

[20℄ S. Feizi, A. Ahmadi, and A. Nemati, �A hardware implementation of simon rypto-

graphy algorithm,� in Computer and Knowledge Engineering (ICCKE), 2014 4th In-

ternational eConferen e on, 2014, pp. 245�250.

[21℄ L. Shuangqing Wei, J. Wang, R. Yin, and J. Yuan, �Trade-o� between se urity and

performan e in blo k iphered systems with erroneous iphertexts,� vol. 8, no. 4, pp.

636�645, 2013.

[22℄ C.-P. Fan and J.-K. Hwang, �Implementations of high throughput sequential and fully

pipelined AES pro essors on FPGA,� in Intelligent Signal Pro essing and Communi-

ation Systems, 2007. ISPACS 2007. International Symposium on, 2007, pp. 353�356.

[23℄ S. Engels, E. Kavun, C. Paar, T. Yal in, and H. Mihajloska, �A non-linear/linear

instru tion set extension for lightweight iphers,� in Computer Arithmeti (ARITH),

2013 21st IEEE Symposium on, 2013, pp. 67�75.

[24℄ J. J. Tay, M. M. Wong, and I. Hijazin, �Compa t and low power AES blo k ipher

using lightweight key expansion me hanism and optimal number of s-boxes,� in Inte-

lligent Signal Pro essing and Communi ation Systems (ISPACS), 2014 International

Symposium on, 2014, pp. 108�114.

BIBLIOGRAFÍA 39

[25℄ V. Trujillo-Olaya, T. Sherwood, and �. Ko��, �Analysis of performan e versus se urity

in hardware realizations of small ellipti urves for lightweight appli ations,� Journal

of Cryptographi Engineering, vol. 2, no. 3, pp. 179�188, 2012.

[26℄ Urbano-Molano, V. Trujillo-Olaya, and J. Velas o-Medina, �Design of an ellipti urve

ryptopro essor using optimal normal basis over GF(2

233

),� in Cir uits and Systems

(LASCAS), 2013 IEEE Fourth Latin Ameri an Symposium on, 2013, pp. 1�4.

[27℄ R. Beaulieu, D. Shors, and J. Smith, �The simon and spe k blo k iphers on avr 8-bit

mi ro ontrollers,� LightSe 2014 pro eedings, vol. 1, no. 1, pp. 1�18, 2014.

[28℄ R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, and L. Wingers, �The

simon and spe k families of lightweight blo k iphers,� Cryptology ePrint Ar hive,

Report 2013/404, 4 2013, http://eprint.ia r.org/.

[29℄ N. Hanley and M. O'Neill, �Hardware omparison of the ISO/IEC 29192-2 Blo k

iphers,� in VLSI (ISVLSI), 2012 IEEE Computer So iety Annual Symposium on,

2012, pp. 57�62.

[30℄ D. Klin , C. Hazay, A. Jagmohan, H. Kraw zyk, and T. Rabin, �On ompression of

data en rypted with blo k iphers,� vol. 58, no. 11, pp. 6989�7001, 2012.

[31℄ F. Qatan and I. Damaj, �High-speed katan iphers on-a- hip,� in Computer Systems

and Industrial Informati s (ICCSII), 2012 International Conferen e on, 2012, pp. 1�6.

[32℄ S. Mane, M. Taha, and P. S haumont, �E� ient and side- hannel-se ure blo k ipher

implementation with ustom instru tions on FPGA,� in Field Programmable Logi

and Appli ations (FPL), 2012 22nd International Conferen e on, 2012, pp. 20�25.

[33℄ R. D. Nieto and A. Bernal, �A methodologi al approa h for asyn hronous implemen-

tation of the rijndael algorithm,� Revista Ingeniería y Competitividad, vol. 15, no. 2,

2013.

[34℄ A. Ganesh, P. Manikandan, S. Sethu, R. Sundararajan, and K. Pargunarajan, �An im-

proved AES-ECC hybrid en ryption s heme for se ure ommuni ation in ooperative

diversity based wireless sensor networks,� in Re ent Trends in Information Te hnology

(ICRTIT), 2011 International Conferen e on, 2011, pp. 1209�1214.

[35℄ K. Datta, V. Shrivastav, I. Sengupta, and H. Rahaman, �Reversible logi implemen-

tation of AES algorithm,� in Design & Te hnology of Integrated Systems in Nanos ale

Era (DTIS), 2013 8th International Conferen e on, 2013, pp. 140�144.

[36℄ M. Pons, Criptologia, E. universitaria polite ni a de Mataro, Ed. Es uela universitaria

polite ni a de Mataro, 2004, vol. 1, no. 1.

[37℄ O. Casas, Implementa ión de los ifradores de bloque Rijndael, Serpent,

MARS,Two�sh y RC6 para su uso en sistemas embebidos, s. C. Universidad de

San Buenaventura, Ed. Editorial Bonaventuriana, 2010, vol. 1, no. 1.

[38℄ D. Densmore and R. Passerone, �A platform-based taxonomy for esl design,� IEEE

Des Test Comput, vol. 23, no. 5, pp. 359�374, 2006.

BIBLIOGRAFÍA 40

[39℄ C. Camargo, �Te hing/learning methods for embedded systems using opyleft hardwa-

re,� IEEE (Revista IEEE Ameri a Latina) Latin Ameri a Transa tions, vol. 9, no. 4,

pp. 503�509, 2011.

e Softwar - repository.udistrital.edu.corepository.udistrital.edu.co/bitstream/11349/2767/1... · o...

Documents

Transcript of e Softwar - repository.udistrital.edu.corepository.udistrital.edu.co/bitstream/11349/2767/1... · o...