PDF de programación - Implementación de un Protocolo de Intercambio de Claves Diffie-Hellman empleando Anillos No Conmutativos

Universidad de Buenos Aires

Facultades de Ciencias Económicas, Ciencias Exactas y

Naturales e Ingeniería



Maestría en Seguridad Informática



Tesis



Título

Implementación de un Protocolo de Intercambio de

Claves Diffie-Hellman empleando Anillos No Conmutativos





Autor: Byron Ron H.



Director de Tesis: Dr. Pedro Hecht





Año

2013



RESUMEN


Los protocolos usados en criptografía asimétrica (AC) y criptografía de
clave pública (PKC), en su mayoría, están estrechamente relacionados con
funciones trampa de una vía, principalmente con los problemas de logaritmo
discreto y de factorización de enteros. Estos problemas usan operaciones
aritméticas en estructuras algebraicas conmutativas, además necesitan del
uso de bibliotecas de precisión extendida y requieren de costosas
operaciones de cálculo.


Sin embargo, es interesante ver como en los últimos años ha surgido
un gran interés por el uso de estructuras algebraicas no conmutativas. Es así
que Hecht presenta un interesante modelo, que lo denomina “compacto”, de
criptografía asimétrica usando anillos no conmutativos de matrices.


En el presente trabajo se desarrolló una implementación del protocolo
Diffie-Hellman propuesto por Hecht. La cual no hace uso de bibliotecas de
precisión extendida y que permite establecer una clave compartida entre dos
entes, la misma que es usada para el intercambio seguro de mensajes de
texto. Esta
implementación es utilizada en dispositivos con poder
computacional limitado, como es el caso de la telefonía celular.



Palabras clave: criptografía asimétrica, álgebra no conmutativa, Intercambio
de claves Diffie-Hellman.













iii

TABLA DE CONTENIDOS



RESUMEN .................................................................................................... iii

AGRADECIMIENTOS ................................................................................. vii

ABREVIATURAS ......................................................................................... ix

CAPITULO 1

Introducción ..................................................................... 10

1.1 Estado Actual del Tema .................................................................. 11

1.2 Objetivos ......................................................................................... 11

1.3 Organización de la Tesis ................................................................. 12

CAPITULO 2 Antecedentes ................................................................... 13

2.1 Criptografía de Clave Pública .......................................................... 13

2.2 Protocolo Diffie-Hellman .................................................................. 13

2.2.1 Algoritmo ...................................................................................... 14

2.3 Modelo Compacto de NCAS [6] ........................................................ 15

2.3.1 Fundamentos Algebraicos y Computacionales ............................ 15

2.3.2 Problemas complejos en grupos (y semigrupos)

no conmutativos ........................................................................... 16

2.3.3 Problemas complejos en anillos no conmutativos ........................ 17

2.4 Protocolo Compacto Diffie-Hellman (DH-C) ................................... 19

2.4.1 Algoritmo ...................................................................................... 19

2.4.2 Generalización de Exponentes .................................................... 20

CAPITULO 3

Implementación de DH-C ................................................ 23

3.1 Software y Hardware utilizado ......................................................... 23



iv

3.2 Diffie-Hellman Compacto (DH-C) .................................................... 24

3.2.1 Clase DHC ................................................................................... 25

3.2.2 Clase Matrix ................................................................................. 26

3.2.3 Clase DHCTest ............................................................................ 27

3.2.4 Clase ExecTimer .......................................................................... 27

3.2.5 DHC-Demo .................................................................................. 27

CAPITULO 4 Seguridad de las Técnicas de Intercambio de Claves .. 28

4.1 Principales Métodos de Ataque a DL en Campos Numéricos [5] ..... 28

4.1.1 Búsqueda Exhaustiva o Fuerza Bruta .......................................... 29

4.1.2 Baby-Step Giant-Step .................................................................. 29

4.1.3 Rho de Pollard ............................................................................. 30

4.1.4 Pohlig-Hellman ............................................................................. 32

4.1.5 Index-Calculus ............................................................................. 33

4.2 Seguridad Computacional del Protocolo DH-C [6] ............................ 35

CAPITULO 5 Evaluación y Pruebas de DH-C ....................................... 37

5.1 Pruebas de la aplicación DHC-Demo .............................................. 37

5.2 Evaluación del protocolo DH-C ....................................................... 47

5.2.1 Tiempo de Ejecución .................................................................... 47

5.2.1 Uso de Memoria ........................................................................... 48

CAPITULO 6 Conclusiones y Trabajos Futuros .................................. 51

6.1 Conclusiones ................................................................................... 51

6.2 Trabajos Futuros ............................................................................. 52

ANEXOS ...................................................................................................... 53





v

A.1. Estructura de la Interfaz de Usuario ................................................ 53

A.2. Ejecución de la clase DHCTestClass .............................................. 60

BIBLIOGRAFIA ........................................................................................... 62






vi









AGRADECIMIENTOS


A mis queridos padres, Martha y Homero, por todo el apoyo que me han
brindado incondicionalmente y en todo sentido, sin ustedes nada de esto
hubiera sido posible.

A mi hermana, Nadia, por ser mi amiga, mi consejera y por estar junto a mí
cuando más te necesito, eres mi ejemplo a seguir.

A mi Director de Tesis Dr. Pedro Hecht, por aceptar ser mi tutor y confiar en
mi trabajo aún sin conocerme, gracias por su orientación, paciencia y
motivación.

























vii














viii

ABREVIATURAS



Abreviatura Significado
IFP
DLP
DL
AC
PKC
SDP
NCAS
DH-C
GDLP
CSP
DP
GSDP
PDH
DSA
JDK
IDE
SDK
ADT
API
ADB
PID
USB


Problema de Factorización Entera
Problema del Logaritmo Discreto
Logaritmo Discreto
Criptografía Asimétrica
Criptografía de Clave Pública
Problema de la Descomposición Simétrica
Estructura Algebraica No Conmutativa
Diffie Hellman Compacto
Problema Generalizado del Logaritmo Discreto
Problema de la Búsqueda del Conjugador
Problema de la Descomposición
Problema de la Descomposición Simétrica Generalizada
Problema Diffie-Hellman
Algoritmo de Firma Digital
Java Development Kit
Integrated Development Environment
Software Development Kit
Android Development Tools
Application Programming Interface
Android Debug Bridge
Process Identifier
Universal Serial Bus



ix



CAPITULO 1

Introducción

Antes que Whitfield Diffie y Martin Hellman introdujeran la criptografía
de clave pública al mundo en 1976, los algoritmos de cifrado utilizados eran
algoritmos de cifrado simétricos donde
tanto el remitente como el
destinatario deben compartir la misma clave, la cual es intercambiada a
través de un canal seguro.


Diffie y Hellman propusieron un método por el cual un individuo A
puede cifrar un mensaje utilizando la clave pública de un individuo B, pero
solamente B sería capaz de descifrar este mensaje con su clave privada.
Para lograr esto se utiliza lo que se conoce comúnmente como “funciones
trampa de una vía”. De hecho, la seguridad en la mayoría de los sistemas de
clave pública se basa en el problema de la factorización de enteros positivos
(IFP) y el problema del logaritmo discreto (DLP) [5]. El intercambio de claves
Diffie-Hellman se basa en el problema DLP. Este protocolo permite que dos
usuarios A y B puedan acordar una clave secreta, mediante una secuencia
de transmisiones a través de un canal público.


Una desventaja de los problemas IFP y DLP reside en que se
conocen ataques de complejidad sub-exponencial y ataques eficientes a
través de algoritmos cuánticos, de modo que hay serios motivos para
desconfiar de ellos. Para reemplazar de raíz a la criptografía asimétrica (AC)
convencional (y su aplicación en criptografía de clave pública), ha surgido en
años recientes un interés creciente en la aplicación de estructuras
algebraicas no conmutativas [6].


Es así que en 2007, Cao, Dong y Wang [7] presentan un interesante
esquema general de criptografía de clave pública (PKC), basándose en la
dificultad de resolver el problema de la descomposición simétrica (SDP) en
un anillo no conmutativo de polinomios matriciales (PSDP).






10



1.1 Estado Actual del Tema


En la actualidad existe una fuerte tendencia al reemplazo de AC y
PKC basada en sistemas algebra