Algoritmos heurísticos para la optimización de Substitution Boxes

Santos Jiménez, Emiliano (2020). Algoritmos heurísticos para la optimización de Substitution Boxes. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. de Sistemas Informáticos (UPM), Madrid.

Description

Title: Algoritmos heurísticos para la optimización de Substitution Boxes
Author/s:
  • Santos Jiménez, Emiliano
Contributor/s:
  • Pozo Coronado, Luis
  • García Pardo, Eduardo
Item Type: Final Project
Degree: Grado en Ingeniería del Software
Date: July 2020
Subjects:
Freetext Keywords: Criptología; Ciberseguridad
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (520kB)
[img] Archive (ZIP) - Users in campus UPM only
Download (2kB)

Abstract

En pleno siglo XXI, la ciberseguridad es ya una parte importante de la vida cotidiana de muchos ciudadanos. La protección de la información y la defensa contra ataques cibernéticos es ya algo fundamental y, dentro de este ámbito, el cifrado se ha vuelto una pieza imprescindible en tales tareas. Por ello, el desarrollo de nuevos métodos de cifrado cada vez es más relevante. Por otro lado, la Inteligencia Artificial ha sufrido un auge notorio durante la última década. Sus técnicas ya son cada vez más empleadas en diferentes contextos, entre los que se encuentra la ciberseguridad. Este proyecto aborda la aplicación de técnicas de Inteligencia Artificial para la mejora de diferentes aspectos, relacionados con la criptología, en el ámbito de la ciberseguridad. Una S-Box es un componente importante del cifrado en bloque, cuyo objetivo es transformar una entrada de n bits en una salida diferente de m bits. En la última década varios investigadores han intentado descubrir nuevas formas de crear S-Boxes. La aplicación de técnicas heurísticas (técnicas pertenecientes al campo de la Inteligencia Artificial) para generar S-Boxes con buenas propiedades criptográficas ha cogido mucha relevancia en relación a métodos más convencionales. El enfoque que se aplica en este proyecto consiste en adaptar el método científico para crear un algoritmo heurístico que optimice algunas de las propiedades criptográficas (más concretamente la no-linealidad) de estos componentes el cifrado en bloque. Más concretamente, la propuesta de este proyecto consiste en desarrollar un método constructivo que genera de forma aleatoria una serie de soluciones iniciales sobre las que posteriormente se aplicará una búsqueda local cuyo objetivo es mejorar las soluciones iniciales. Por último se aplica una versión de la metaheurística Variable Neighborhood Search con la finalidad de evitar los óptimos locales que se producen con la búsqueda y tratar de alcanzar un mejor resultado. Los algoritmos propuestos han sido validados mediante la realización de pruebas que comparan los tres métodos desarrollados. El tiempo de ejecución de las pruebas aumenta exponencialmente cuanto mayor es la dimensión de la instancia tratada, siendo el tamaño máximo que se ha considerado en este proyecto de 8x8. Los resultados obtenidos con el constructivo aleatorio muestran valores iniciales prometedores. Sin embargo, esto parece indicar que los valores pueden estar próximos a los óptimos locales, siendo difícil la propuesta de algoritmos de mejora. Abtract: Nowadays, cibersecurity is an important part of the daily life of many citizens. Protecting data and defending against attacks have already become fundamental, and within this area, encrypting has become an essential part in such tasks. This is the reason why developing new encryption methods is increasingly important. On the other hand, Artificial Ingelligence has experienced a boom during the last decade. Its techniques are gradually more used in different contexts, among which is cybersecurity. This project approach the aplication of Artificial Intelligence to improve different aspects related to cryptology, in the context of cibersecurity. An S-Box is an important component of block ciphers, which aim is transform a n bits input into a m bits output. For the last decade, some researchers have tried to find new methods to create S-Boxes. The application of heuristic techniques, which are part of Artificial Intelligence context, to produce S-Boxes with strong cryptological properties has obtained more relevance compared to conventional methods. The approach proposed in this project is to use the scientific method in order to generate an heuristic algorithm to optimize some of those S-Boxes cryptological properties (specifically non linearity). To be more accurate, this project proposes developing a constructive method which create a number of solutions randomly and use a local search in order to improve the initial solutions. Finally, the Variable Neighborhood Search metaheuristic is applied trying to avoid local optima produced by the local search and improve the overall results. The methods proposed have been validated with tests comparing the three methods. The ejecution time of the tests increases exponentially the larger the size of the instance, being 8x8 the maximum size considered in this project. The results obtained with the random consctructive method shows promising initial values. However, this seems to indicate that those values could be near local optima, making the proposal of improvement algorithms harder.

More information

Item ID: 64788
DC Identifier: http://oa.upm.es/64788/
OAI Identifier: oai:oa.upm.es:64788
Deposited by: Biblioteca Universitaria Campus Sur
Deposited on: 19 Oct 2020 10:37
Last Modified: 19 Oct 2020 10:37
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM