_Criptografía y Matemáticas:
La evolución y aplicación de matrices en la seguridad de la información
- América Olivares Lemunao
- Daniela Olivares Lemunao
- Patricio Vega González
- Carlos Bastias Dávila
- Funciones y matrices
- V-IEI-N2-P3-C1 | Ingeniería en Informática
Descripción
_Problemática
La criptografía ha evolucionado desde métodos rudimentarios como el cifrado por sustitución en la antigua Roma, hasta complejos sistemas matemáticos que protegen la información en la era digital.
Los avances matemáticos, como las transformaciones lineales en el cifrado de Hill y los principios de factorización y claves públicas en RSA, han impulsado la creación de algoritmos robustos y eficientes como los Hash.
Este trabajo explora el papel crucial de las matemáticas, desde matrices y álgebra lineal hasta teorías de números avanzados, en la construcción de métodos criptográficos y criptoanálisis.
Descripción
_Objetivo General: Demostrar cómo las herramientas matemáticas, como las matrices han sido esenciales para desarrollar sistemas criptográficos más seguros y cómo siguen influyendo en la criptografía moderna.
Pregunta 1:
¿Qué elementos hacen más segura una clave?
Pregunta 2:
¿Cuál fue la necesidad de utilizar esta matemática? (Ventaja y Desventajas)
Historia Matemática y Evolución de la Criptografía
Introducción de la aritmética modular
300 a.C
Matemático: Euclides, con su trabajo en divisibilidad y algoritmos.
Impacto en criptografía: La aritmética modular es la base de muchos sistemas modernos de cifrado, como RSA.
Análisis de frecuencias
820 d.C
Matemático: Al-Kindi, su obra "Manuscrito sobre descifrar mensajes cifrados"
Impacto en criptografía: Análisis estadístico como una forma de descifrar códigos basados en sustituciones.
Invención del cifrado polialfabético
1467
Matemático:Leon Battista Alberti.
Impacto en criptografía: Alberti diseñó un disco de cifrado que alternaba entre diferentes alfabetos.
Permutaciones en teoría combinatoria
1514
Matemático: Niccolò Fontana (Tartaglia).
Impacto en criptografía: La teoría combinatoria fue esencial para los sistemas de cifrado.
Desarrollo formal de la probabilidad.
1654
Matemático: Blaise Pascal y Pierre de Fermat.
Impacto en criptografía: La probabilidad sentó las bases para cuantificar la fuerza de los cifrados y predecir la probabilidad de que un atacante pueda adivinar claves o romper.
Publicación de la Teoría de los números.
1801
Matemático: Carl Friedrich Gauss.
Impacto en criptografía: Formalizó la aritmética modular , fundamento clave para algoritmos como RSA y curvas elípticas.
Conceptualización de la teoría de la información
1940
Matemático: Claude Shannon.
Impacto en criptografía: Estableció los principios de la criptografía moderna. Incluyendo entropía y métodos para medir la seguridad de los cifrados.
Creación del algoritmo RSA.
1977
Matemáticos: Ronald Rivest, Adi Shamir, Leonard Adleman.
Impacto en criptografía: RSA utiliza la dificultad de factorizar grandes números primos.
Criptografía basada en curvas elípticas (ECC)
1985
Matemático: Neal Koblitz y Victor Miller.
Impacto en criptografía: Las curvas elípticas usan geometría algebraica para clave pública. Permitió mayor seguridad con claves más pequeñas
Avance en criptografía homomórfica
2000s
Matemático: Craig Gentry (2009).
Impacto en criptografía: Permite cálculos sobre datos cifrados sin necesidad de descifrarlos.
Desarrollo de criptografía post-cuántica.
2010s
Matemáticos: Varios, incluyendo Peter Shor
Impacto en criptografía: Retículas y algoritmos resistentes a computadoras cuánticas para proteger sistemas ante amenazas.
Evaluación de Claves Seguras
_¿Qué elementos hacen más segura una clave?
Criptoanálisis
Cuantificación de seguridad de un sistema
1. Modelos de seguridad
- Seguridad Computacional
- Seguridad Teórica
- Seguridad Asintónica
2. Medidas y Métodos de seguridad
- Bits de seguridad
- Entropía
- Resistencia a ataques específicos
- Ataques de fuerza bruta
- Ataques criptoanalíticos
- Resistencia basado en colisiones
- Costo de ataque
3. Contexto de Ataque
- Ataque de texto claro conocido
- Ataque de texto claro elegido
- Ataque de texto cifrado elegido
- Ataque de canal lateral
Simulación Ataque Fuerza Bruta
¿Cómo funciona?
function evaluate(password) {
const characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()_+[]{}|;:',.<>?/`~";
const N = characters.length;
const L = password.length;
let possibleCombinations = Math.pow(N,L);
const entropy = Math.log2(possibleCombinations);
let securityLevel = '';
if (entropy < 40) {
securityLevel = 'Baja Seguridad: contraseña fácilmente descifrable';
} else if (entropy >= 40 && entropy <= 59) {
securityLevel = 'Moderada: aceptada para usos comunes, pero no recomendada para alta seguridad';
} else if (entropy >= 60 && entropy <= 79) {
securityLevel = 'Alta: adecuada para propósitos críticos con riesgos medios';
} else {
securityLevel = 'Muy Alta: considerada robusta, ideal para aplicaciones críticas';
}
function bruteForce(password) {
const startTime = performance.now();
const containerResult = document.getElementById("result");
let totalAttempts = 0;
let current = "";
let i = 0;
let searchCharacter = true;
while (i < password.length && searchCharacter) {
searchCharacter = false;
for (let j = 0; j < characters.length; j++) {
totalAttempts++;
if (characters[j] = = = password[i]) {
current += characters[j];
searchCharacter = true;
break;
}
}
if (searchCharacter) {
i++;
} else {
break;
}
}
}
1. Configuración inicial y entrada de datos:
- Hemos definido una función llamada Evaluate a la que se le pasa como parámetro password que es la contraseña ingresada por el usuario.
- Luego tenemos nuestra variable characters que guarda el conjunto de posibles caracteres que se podría usar en la contraseña, en este caso es un total de 90 carácteres.
2. Cálculo de la entropía:
- La variable N guarda el número total de caracteres posibles que se pueden usar, en este caso evalúa el largo de la variable characters por lo tanto son 90 carácteres.
- La variable L corresponde a longitud de la contraseñan que ingresó el usuario
- En la variable possibleCombinations utilizamos el método Math.pow(N,L) que calcula el número total de combinaciones posibles, en este caso si N=90 y L=4, entonces 904 = 65.610.000 combinaciones
- Luego tenemos definida la variable entropy guarda el valor en bits. Como vemos al método Math.log2(65610000) le pasamos como parámetro el número total de combinaciones que obtuvimos de la variable possibleCombinations, convirtiendo esto en bits de entropía lo que daría 25.96bits
- La función log2(x) lo que hace es calcular cuántos bits (símbolos binarios 0 y 1) necesitas para representar todas las combinaciones.
3. Evaluación del nivel de seguridad:
- Aquí clasificamos el nivel de seguridad según el resultado de la entropía, tenemos 4 niveles los cuales creamos basándonos en el estándar del NIST SP 800-90B.
- Cuando se cumple una de estas cuatro condiciones entonces la variable securityLevel que estaba declarado como vacío se rellena con un mensaje para el usuario que explica qué nivel tiene su clave y qué significa esto.
4. Simulación de fuerza bruta
- La función bruteForce() intenta "adivinar" una contraseña (password) utilizando un enfoque de fuerza bruta. Esto implica probar todas las combinaciones posibles carácter por carácter hasta encontrar la coincidencia exacta.
- La variable const startTime registra el tiempo inicial para medir cuánto tarda el algoritmo en encontrar la contraseña usando el método performance.now().
- performance.now() es una función disponible en el contexto del navegador web (JavaScript) y en algunos entornos de ejecución como NodeJS. Esto devuelve un valor de tiempo en milisegundos.
- containerResult obtiene el elemento HTML con el id result para mostrar los resultados en la página web al finalizar.
- totalAttempts contabilizará el total de intentos realizados.
- la variable current es quien se encarga de acumular la parte de la contraseña encontrada hasta el momento.
- el índice i se utilizará para recorrer la contraseña password.
- searchCharacter nos indicará si se sigue buscando caracteres en el ciclo principal. Esto nos ayudará a salir del bucle si no se encuentra un carácter.
- Inicialmente asumimos que puede encontrar cada caracter por ello la declaramos con valor true
5. Ciclo principal para adivinar la contraseña:
- El bucle principal intenta encontrar cada carácter de la contraseña
- El ciclo While Se ejecuta mientras queden caracteres en la contraseña (i < password.length) y sea posible encontrar caracteres (searchCharacter).
- searchCharacter = false Al inicio de cada iteración, se asume que no se encontrará el carácter, hasta que el ciclo interno lo demuestre.
- El ciclo interno for itera sobre characters para encontrar el carácter actual de la contraseña.
- la variable totalAttempts++ incrementa los intentos de uno en uno.
- En la condicional comparamos cada carácter de characters con el carácter actual de password.
- Si coincide, agregará el carácter encontrado a current
- Se activa searchCharacter como true para continuar con el siguiente carácter.
- Sale del ciclo interno con break porque ya hemos encontrado el carácter actual.
- Como searchCharacter sen encuentra en true, entonces sumamos 1 al valor de i, significando que pasamos al siguiente caracter. Solo se incrementa si se encontró el carácter actual.
- Si no se encuentra un carácter entonces se rompe el bucle principal, ya que no tiene sentido continuar si algún carácter de la contraseña no está presente en characters.
Introducción a métodos de cifrado
La criptografía es una disciplina que busca garantizar la seguridad de la información mediante el uso de técnicas matemáticas avanzadas.
Exploramos cómo las matemáticas constituyen la base de los métodos criptográficos más destacados, como el Cifrado de Hill, RSA y las funciones de hash.
Estos sistemas no solo permiten la encriptación de datos sensibles, sino que también garantizan su integridad y autenticidad en nuestras comunicaciones en línea.
Método de Cifrado de Hill
Desarrollado por el matemático y criptógrafo estadounidense S. Hill en 1929.
Fue uno de los primeros sistemas en aplicar álgebra lineal y operaciones matriciales al cifrado de mensajes.
Su enfoque marcó un punto de transición hacia métodos más matemáticos en la criptografía
El trabajo de Lester Hill se publicó en artículos académicos de la época, donde se destacaba su método como un sistema resistente para su tiempo, aunque actualmente se considera inseguro frente a ataques modernos.
Método de Cifrado de Hill
1. Preprar el mensaje y clave
Mensaje por cifrar: "HI"
Clave:
Matriz \( K = \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix} \)
Asignación de valor al alfabeto:
| A=0 | B=1 | C=2 | D=3 | E=4 |
| F=5 | G=6 | H=7 | I=8 | J=9 |
| K=10 | L=11 | M=12 | N=13 | O=14 |
| P=15 | Q=16 | R=17 | S=18 | T=19 |
| U=20 | V=21 | W=22 | X=23 | Y=24 |
| Z=25 |
Reemplazo por números:"H"=7 , "I"=8
Representación del mensaje:
\( P = \begin{pmatrix} 7 \\ 8 \end{pmatrix} \)
2. Cifrar el mensaje
Fórmula para cifrar: C=K*P mod 26
Multiplicar:
\[ C = \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix} \cdot \begin{pmatrix} 7 \\ 8 \end{pmatrix} = \begin{pmatrix} 45 \\ 54 \end{pmatrix} \]
Aplicación mod 26:
\[ C = \begin{pmatrix} 45 \mod 26 \\ 54 \mod 26 \end{pmatrix} = \begin{pmatrix} 19 \\ 2 \end{pmatrix} \]
Texto cifrado: 19="T", 2="C"
Resultado cifrado: "TC"
3. Decifrar el mensaje
Cálculo matriz inversa de K en modulo 26
Determinante de K: det(K)=(3*5-3*2) = 9
Inverso del det(K) mod 26: 9-1= 3 en módulo 26
Matriz inversa de K:
\[ K^{-1} = 3 \cdot \begin{pmatrix} 5 & -3 \\ -2 & 3 \end{pmatrix} \mod 26 = \begin{pmatrix} 15 & 17 \\ 20 & 9 \end{pmatrix} \]
Aplicamos el decifrado:
\[ P = K^{-1} \cdot C \mod 26 = \begin{pmatrix} 15 & 17 \\ 20 & 9 \end{pmatrix} \cdot \begin{pmatrix} 19 \\ 2 \end{pmatrix} \mod 26 = \begin{pmatrix} 7 \\ 8 \end{pmatrix} \]
Mensaje descifrado: "HI"
Cifrado de Hill con una matriz 2x2
- Primero dividimos el mensaje en bloques del mismo tamaño que la matriz clave.
- Cada letra del alfabeto se reemplaza por su posición numérica (por ejemplo: A=0, B=1, C= 2,..., Z=25).
- Se elije una matriz cuadrada nxn con números enteros como clave. Esta matriz debe ser invertible en módulo 26 (es decir, tener un determinante que no sea multiplo de 2 o 13 para asegurar que exista una matriz inversa).
- El mensaje se representa como el vector columna.
- Utilizamos la formula para cifrar. Comenzamos multiplicando K * P
- Luego reducimos con módulo 26.
- Obtenemos dos numeros que al reemplazarlos por las letras de nuestra tabla nos retorna 19= "T" y 2 = "C"
- Utilizamos la matriz inversa de la clave para recuperar el mensaje original.
Método de Cifrado de Hill
Ventajas
- Fácil de implementar matemáticamente con matrices pequeñas.
- Resistente a análisis de frecuencia, ya que cifra por bloques en lugar de letras individuales.
- Generalización: permite cifrar bloques más grandes con matrices de mayor tamaño.
Desventajas
- Dependencia de la matriz clave: Si la matriz no es invertible en módulo 26 el módulo no funciona.
- Vulnerabilidad a ataques: Si un atacante conoce varios pares de texto plano y cifrado, puede deducir la matriz clave mediante álgebra lineal.
- Complejidad creciente: Para matrices grandes los cálculos manuales son complicados y propensos a errores.
Método de Cifrado RSA
El método RSA fue desarrollado en 1977 por Ron Rivest, Adi Shamir y Leonard Adleman, tres criptógrafos del Instituto Tecnológico de Massachusetts (MIT).
Su apellido forma el acrónimo RSA
Fue uno de los primeros sistemas prácticos de cifrado asimétrico, donde se utilizan un par de claves.
Este método sigue siendo una de las piedras angulares en sistemas modernos de seguridad digital.
Método de Cifrado RSA
Elección de primos
p=7, q=11
n=7*11 = 77, ϕ(n)=(7-1)*(11-1)=60
Elección de e
Elegimos e=17 (comprimo con ϕ(n)=60)
Cálculo de d
d es el inverso modular de 17mod60, lo que da d=53
Clave pública y privada
Clave pública: (17,77)
Clave privada: (53, 77)
Cifrado
Mensaje M=10
$$C = 10^{17} \mod 77 = 17 \, \text{(resultado simplificado)}.$$
Descifrado
$$M = 17^{53} \mod 77 = 10 \, \text{(mensaje original)}.$$
Pasos del cifrado RSA
1. Generación de claves
- Elegimos números primos grandes, p y q
- Calculamos n= p*q. Este valor será parte de ambas claves.
- Calculamos ϕ(n)= (p-1)*(q-1), la función de Euler.
- Seleccionamos un número e tal que 1 < e < ϕ(n) y que sea coprimo con ϕ(n)
- Calculamos en inverso modular de e, denominado d, tal que: (e*d)modϕ(n)=1
- Claves generadas:
Clave pública: (e, n)
Clave privada: (d, n)
2. Cifrado
- Para un mensaje M (convertido a un número), se cifra como:
$$C = M^e \mod n$$
3. Descifrado
- El receptor usa la clave privada para obtener el mensaje original:
\( M = C^d \mod n \)
Método de Cifrado RSA
Ventajas
- Seguridad sólida basada en la dificultad de factorizar números grandes.
- No se requiere compartir la clave privada, lo que simplifica la comunidad segura.
Desventajas
- Ineficiencia para mensajes grandes debido a cálculos complejos.
- Claves largas necesarias para mantener seguridad (2048 bits o más).
- Amenaza cuántica: algoritmos cuánticos pueden romper RSA en el futuro.
Método de Cifrado de Funciones Hash
Estas funciones transforman datos de entrada de cualquier tamaño en una cadena de texto de longitud fija, conocida como valor hash o digest.
Este proceso es unidireccional.
Las funciones hash son ampliamente utilizadas para verificar la integridad de los datos y en la creación de firmas digitales.
Historia y Desarrollo
- Algunas de las primeras funciones hash, como MD4 y MD5, fueron desarrolladas en la década de 1990.
- Con el avance de la tecnología y el aumento de las amenazas cibernéticas, estas funciones se han vuelto vulnerables a ataques de colisión
- Esto ha llevado al desarrollo de funciones hash más seguras, como SHA-256 y SHA-3.
Pasos del Proceso de Hashing
- Preparar el mensaje:
- Mensaje por hashear: "Hello, World!"
- Función hash: SHA-256
- El mensaje "Hello, World!" se utiliza como entrada.
- Aplicar la función hash:
- Utilizamos SHA-256 para generar el valor hash:
- Verificación de integridad:
- Si el valor hash generado coincide con un valor hash previamente calculado, el mensaje no ha sido alterado.
El mensaje de entrada puede ser de cualquier tamaño y tipo (texto, archivo, etc.).
Utilizar una función hash criptográfica para transformar el mensaje en un valor hash de longitud fija.
SHA-256("Hello, World!") = a591a6d40bf420404a011733cfb7b190d62c65bf0bc...
Comparar el valor hash generado con un valor hash previamente calculado para verificar si el mensaje ha sido alterado.
Método de las Funciones Hash
Ventajas
- Alta seguridad: Las funciones hash criptográficas modernas son altamente seguras y resistentes a ataques.
- Eficiencia: El proceso de hashing es rápido y eficiente, lo que lo hace ideal para verificar la integridad de grandes volúmenes de datos.
- No reversible: No es posible revertir el valor hash para obtener el dato original, lo que añade una capa adicional de seguridad.
Desventajas
- No cifran datos: Las funciones hash no están diseñadas para cifrar datos, solo para verificar su integridad.
- Vulnerabilidad a ataques de colisión: Algunas funciones hash más antiguas son vulnerables a ataques de colisión, donde dos entradas diferentes producen el mismo valor hash.
Tipos de Funciones Hash
- 1. MD4 y MD5:
- 2. SHA-1:
- 3. SHA-2 (SHA-256, SHA-384, SHA-512):
Desarrolladas por Ronald Rivest, estas funciones fueron ampliamente utilizadas en el pasado. Sin embargo, hoy en día se consideran inseguras debido a vulnerabilidades a ataques de colisión.
Desarrollada por la Agencia de Seguridad Nacional de EE.UU. (NSA), SHA-1 es más segura que MD4 y MD5, pero también se considera vulnerable a ataques de colisión.
La familia SHA-2 es una mejora significativa sobre SHA-1 y es ampliamente utilizada en aplicaciones de seguridad modernas. SHA-256 es una de las funciones hash más comunes en esta familia.
- 4. SHA-3:
- 5. BCrypt:
- 6. Scrypt:
Desarrollada por el Instituto Nacional de Estándares y Tecnología de EE.UU. (NIST), SHA-3 es la última generación de funciones hash y está diseñada para ser resistente a ataques de colisión y otros tipos de ataques criptográficos.
Utilizada principalmente para el hashing de contraseñas, BCrypt incluye una "sal" para proteger contra ataques de tablas arcoíris y es diseñada para ser lenta, lo que dificulta los ataques de fuerza bruta.
Similar a BCrypt, Scrypt también es utilizada para el hashing de contraseñas y está diseñada para ser costosa en términos de memoria, lo que la hace resistente a ataques de hardware personalizado.
Reflexiones
_1
Explorar la historia de las matemáticas y la criptografía me permitió entender cómo principios como la teoría de números y el álgebra lineal fueron clave para sistemas como RSA y el cifrado de Hill. También comprendí la importancia de las matemáticas en la seguridad digital, destacando su relevancia en la tecnología actual.
_Daniela
_2
Investigar métodos de cifrado como Hill, RSA y hash me permitió comprender las matemáticas que los respaldan y su relevancia en la criptografía moderna. El cifrado de Hill muestra el uso del álgebra lineal, RSA resalta la factorización de números primos y los métodos de hashing demuestran la importancia del pensamiento matemático. Este proyecto me enseñó sobre algoritmos y la necesidad de diseñar sistemas resistentes a ataques, enfatizando el papel crucial de la entropía.
_Patricio
_3
Trabajar en la cuantificación de la seguridad de claves y diseñar un algoritmo para evaluar la entropía y realizar ataques de fuerza bruta me permitió ver cómo la teoría matemática impacta directamente en la protección de información. Crear el algoritmo me mostró la aplicación práctica de principios matemáticos en la seguridad de claves y entendí la importancia de diseñar sistemas robustos. Este proyecto reforzó mi admiración por la relación entre matemáticas y tecnología.
_América
Conclusiones
- La importancia de las matemáticas en la criptografía
- Conexión entre teoría y aplicación
- La relevancia de la entropía
- La seguridad no es solo cuestión de complejidad
- Los avances del pasado son esenciales para la criptografía moderna
- La fuerza bruta sigue siendo una amenaza
- El diseño de sistemas criptográficos requiere de una visión multidisciplinaria
- La seguridad digital es esencial en la era moderna
- La matemática como herramienta de defensa cibernética
- La evaluación de la seguridad requiere pruebas continuas
_Criptografía y Matemáticas:
La evolución y aplicación de matrices en la seguridad de la información
"La criptografía es el arte de proteger las comunicaciones y la información mediante el uso de códigos, y las matemáticas son el lenguaje que permite que este arte sea posible." — Whitfield Diffie, pionero en la criptografía moderna.