Aplicación de la Teoría de Grafos, En la implementación de una Red de seguridad avanzada que comunique a las ciudades mas importantes de la republica Mexicana.

Resumen

La teoría de grafos puede ser utilizada en distintas aplicaciones de varias areas tales como encontrar la mejor ruta, búsquedas a través de arboles, solución de problemas de puentes como los de Koningsberg, problemas de coloración, aplicaciones en redes, etc. En este proyecto se estudia la seguridad informatica en México y tiene como objetivo proponer una solución al robo de información personal y privada.
La solución al problema de seguridad informatica propuesta en este proyecto esta fundamentada en la teoría de grafos, se utilizara un grafo para construir el diseño de una red de seguridad donde los nodos representan las ciudades mas importantes de la republica Mexicana, así como también se hara uso de algoritmos para encontrar la mejor ruta y utilizarla para aplicar un método de encriptación a la información que viaja por la red de seguridad.

Palabras clave: Teoría de Grafos, Algoritmo, planificación de rutas, seguridad informatica.
Introducción

En la actualidad en México nos encontramos con un problema de inseguridad muy grave puesto que la corrupción y la delincuencia organizada cada vez gana mas fuerza, así como tambiénel uso de la tecnología ha facilitado a la delincuencia organizada a realizar sus operaciones, y de acuerdo a los expertos en seguridad informatica en México no se cuenta con una infraestructura 100% segura ya que esta le pertenece a empresas privadas.
Actualmente la infraestructura tecnológica para la transmisión de datos en México pertenece a particulares puesto que el gobierno renta estos servicios de telecomunicaciones a empresas privadas como Telmex o Televisa (Bestel). Estas empresas a pesar de que cuentan con protocolos de seguridad estos no han sido suficientes como para evitar el robo de información.
El 18 de mayo de 2010 el Diario Universal presento una noticia donde se expone la venta de las bases de datos oficiales tales como INEGI, IFE e IMSS en el barrio de Tepito. Esta información incluye datos personales de todos los Mexicanos como los estados de cuenta, domicilio, cuentas bancarias, números telefónicos, pagos hechos a hacienda y crédito público, etc. Esta información hoy en día es utilizada con fines de extorsión y secuestro.
Las bases de datos que manejan información confidencial y critica deben de ser resguardadas en sitios altamente seguros que cuenten con respaldos, equipos a prueba de fuego e inundaciones, firewalls y sistemas de seguridad, a estos sitios se les conoce comoCentros de Procesamiento de Datos CPDs, sin embargo para que estos centros sean realmente seguros es necesaria la implementación de una infraestructura donde viaje la información con la tranquilidad que esta no sera interceptada o robada y de serlo así que sea imposible de leer si no se conoce el método de encriptación.
Este proyecto propone la implementación de una infraestructura de caracter militar y gubernamental donde la información personal sera transmitida de manera segura por una red que esta conformada por nodos en puntos estratégicos de la republica Mexicana, estos nodos son seleccionados de acuerdo a la importancia de las ciudades.

Costo de la implementación de la red de seguridad.

La implementación de una red se hace a los costados de las carreteras mas importantes de la republica puesto que el costo del traslado de la fibra óptica es menor, esta instalación puede ser subterranea o aérea (viaja a través de los postes de luz). La imagen 1 muestra las ciudades donde se instalaran los dispositivos de ruteo o nodos de la red así como también muestra donde seran instalados los cables de fibra óptica (aristas en verde).

Imagen 1 Diseño de la red de seguridad
Ciudades donde seran instalados los dispositivos de ruteo:
Nomenclatura de Ciudades
Nodo | Ciudad |
A | Caborca |
B |Cancun |
C | Ciudad de Mexico |
D | Culiacan |
E | Guadalajara |
F | La Paz |
G | Juarez |
H | Monterrey |
I | Morelia |
J | Nuevo Laredo |
K | Oaxaca |
L | Puebla |
M | Tijuana |
N | Veracruz |
Tabla 1 Representación de Ciudades utilizando nodos
Costo del cableado e instalación de la fibra óptica por kilometro: 3500 USD.
Tabla de distancia entre nodos (kilómetros) y costo (USD).
Aristas | Origen | Destino | Kilometros | Costo(USD) |
DE | Culiacan | Guadalajara | 707.86 | 2477510 |
DA | Culiacan | Caborca | 964.4 | 3375400 |
AM | Caborca | Tijuana | 584.72 | 2046520 |
MF | Tijuana | La Paz | 1499.55 | 5248425 |
AG | Caborca | Juarez | 702.9 | 2460150 |
GH | Juarez | Monterrey | 1147.4 | 4015900 |
HJ | Monterrey | Nuevo Laredo | 223.1 | 780850 |
EH | Guadalajara | Monterrey | 846.8 | 2963800 |
HN | Monterrey | Veracruz | 1086 | 3801000 |
EI | Guadalajara | Morelia | 296.29 | 1037015 |
IC | Morelia | Cd. de México | 307.97 | 1077895 |
CL | Cd. de México | Puebla | 129.86 | 454510 |
LN | Puebla | Veracruz | 281.64 | 985740 |
NB | Veracruz | Cancún | 1320.41 | 4621435 |
LK | Puebla | Oaxaca | 344.02 | 1204070 |
Total |   |   | 10442.92 | 36550220 |
Tabla 2 Tabla de Aristas de la red de seguridad
El costo únicamente del cableadode la red es de 36’550,220 USD, el cual es un costo exageradamente alto así que buscaremos recortar este costo utilizando el modelo de “Arbol Generador Minimal”
Entonces tenemos el siguiente grafo G en la Imagen 2.

Imagen 2 Representación de la red de seguridad en el grafo G

Utilizando el método de “Arbol Generador Minimal” tenemos las siguientes iteraciones:
k=0 c0= c0’=
k=1 c1= c1’=
k=2 c2= c2’=
k=3 c3= c3’=
k=4 c4= c4’=
k=5 c5= c5’=
k=6 c6= c6’=
k=7 c7= c7’=
k=8 c8= c8’=
k=9 c9= c9’=
k=10 c10= c10’=
k=11 c11= c11’=
k=12 c12= c12’=
k=13 c13= c13’=
k=14 c14= c14’=

El grafo H de la imagen 3 representa la red de seguridad después de aplicar el método de “Arbol Generador Minimal”.

Imagen 3 Grafo H

El costo de la implementación de la red de seguridad aún es alto puesto que únicamente fueron eliminadas dos aristas delgrafo, el nuevo costo total de la infraestructura es de 28’733,320 USD.
Al ser un costo muy alto se propone la construcción de la estructura principal de la red (Backbone) con siguientes ciudades:
* Ciudad de México (CPD)
* Guadalajara (CPD)
* Monterrey (CPD)
* Puebla
* Morelia
* Veracruz
Para conectar las ciudades que se encuentran dentro del grafo G en la imagen 1 y que no se han considerado como parte de la estructura principal de la red, se utilizaran las redes privadas como se hace actualmente. Para poder implementar la seguridad en las redes privadas se deben de codificar los datos que seran transmitidos.
Para realizar la encriptación de los paquetes se hizo uso de otra aplicación de la teoría de grafos para elegir la mejor ruta y así obtener una secuencia de nodos que sera utilizada para la encriptación. Utilizando esta secuencia se genera una llave única que en conjunto con un algoritmo basado en Tablas Hash su función es codificar los paquetes cada vez que son transmitidos por un servidor de ruteo, la única forma de regresar los paquetes a su estado original es teniendo la secuencia de nodos para invertir la codificación en el orden correcto.

Pseudocodigo del algoritmo de encriptación.

1 - Se genera la ruta con el menor costo utilizando el algoritmo de Dijkstra.
2- En cada nodo se remueve el identificador inicial si este tiene (solo la primera iteración no necesitara quitar este identificador inicial puesto que el archivo no lo tendra) y se realiza una encriptación con el método de tablas hash donde la llave esta compuesta de la siguiente fórmula
Key = NodoID x RDMkey
NodoID es un número entero único de cuatro dígitos correspondiente a cada nodo, el identificador no puede tener dígitos repetidos como 2233.
RDMkey es un número entero aleatorio de 4 dígitos.
Se coloca el RDMKey en el archivo encriptado en las posiciones de los dígitos.
Ejemplo:
Si el identificador del nodo es 3724, el numero al azar es 5871 y la cadena encriptada es “mnhteyudf734y3r4h345tyb34n4y7f7vik”, el numero al azar sera colocado de la siguiente forma, “mn751hte8yudf734y3r4h345tyb34n4y7f7vik”.
4.- Se coloca al final del archivo el identificador del nodo inicial
5.- El contador de posiciones de la cadena encriptada se incrementa en 10 para que tome como origen los diez dígitos siguientes.
Se realizan pasos 2, 3, 4 y 5 hasta que el paquete llegue hasta el final del archivo.
En el destino se realizara la decodificación sabiendo la ruta se decodificara tantas veces como haya pasado por los diferentes nodos esto quiere decir que si un paquete paso por los nodos E, I,C, L y N el paquete se decodificara 5 veces hasta llegar al archivo original.

Conclusiones:

Los grafos nos ayudan representar conjuntos o conexiones reales como el diseño de una red, y al aplicar algoritmos podemos encontrar el Backbone o estructura principal de la red que nos ayuda a reducir costos en la implementación eliminando conexiones.
En este proyecto utilizando el algoritmo de Arbol Generador Minimal observamos que únicamente se eliminaron dos aristas con lo cual el costo de la implementación de la infraestructura fue reducido de 36’550,220 USD a 28’733,320 USD el cual es un ahorro significativo.
También utilizando el algoritmo de Dijkstra pudimos construir un sistema de seguridad para implementar la red de forma que tengamos una estructura principal propia y usar infraestructura privada para conectar todas las ciudades, gracias a esta combinación de redes se reducen en gran parte los costos de implementación de la red.


Bibliografía y fuentes
CNN Expansión. (Lunes, 09 de agosto de 2010 a las 06:00) disponible 26 de agosto de 2010 de: https://www.cnnexpansion.com/expansion/2010/08/04/bestel-nuevo-rey-de-telecomunicaciones
2 El Universal. (Lunes 19 de abril de 2010) disponible 26 de agosto de 2010 de:
https://www.eluniversal.com.mx/notas/673768.html
3 Datos proporcionados porel ingeniero de planeación de redes de la empresa Orange Telecomunicaciones.
4 Turista.com.mx s.f.) disponible 26 de agosto de 2010 de: https://www.turista.com.mx/modules.php?name=carreterasmexico
5 Universidad de Granada. (s.f) disponible 26 de agosto de 2010 de
https://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/tablash.html
6 Universidad Carlos III de Madrid.(s.f) disponible 26 de agosto de 2010 de:
https://www.it.uc3m.es/~pablo/asignaturas/rysc1/alumnos/04-EncEjerciciosSolucion.pdf

-------- ----- ------ -----------
[ 1 ]. CNN Expansión “Oficinas cambian a Telmex por Televisa” https://www.cnnexpansion.com/expansion/2010/08/04/bestel-nuevo-rey-de-telecomunicaciones
[ 2 ]. El Universal “Tepito vende Bases de datos oficiales”
https://www.eluniversal.com.mx/notas/673768.html
[ 3 ]. Datos proporcionados por el ingeniero de planeación de redes de la empresa Orange Telecomunicaciones.
]. Datos proporcionados por la secretaría de comunicaciones y transportes en la pagina https://www.turista.com.mx/modules.php?name=carreterasmexico
[ 5 ]. Universidad de Granada “Tablas Hash”
https://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/tablash.html
[ 6 ]. Universidad Carlos III de Madrid “Pasos Algoritmo Dijkstra”
https://www.it.uc3m.es/~pablo/asignaturas/rysc1/alumnos/04-EncEjerciciosSolucion.pdf