Resumen Técnico: Una Nueva Criptografía de Clave Pública Basada en Matrices de Lucas Generalizadas

Declaración del Problema

El artículo aborda la necesidad de esquemas de criptografía de clave pública mejorados que ofrezcan espacios de claves más grandes, una complejidad de transmisión reducida y una seguridad robusta basada en la teoría de números y el álgebra lineal. Si bien la teoría de matrices y las secuencias recursivas (como las secuencias de Fibonacci y Lucas) se han utilizado en criptografía (por ejemplo, el cifrado de Hill, ElGamal), los métodos existentes a menudo implican el intercambio de grandes matrices de claves o dependen de las propiedades estándar de las secuencias. Los autores proponen un sistema que minimiza los datos intercambiados durante el acuerdo de claves mientras maximiza la complejidad del espacio de claves de cifrado mediante el uso de matrices recursivas generalizadas.

Metodología

1. Fundamentos Matemáticos

El núcleo del esquema propuesto reside en la construcción de Matrices de Lucas Generalizadas (GLM) derivadas de Matrices de Fibonacci Generalizadas (GFM).

• Matrices de Fibonacci Generalizadas (GFM): Los autores utilizan la secuencia de Fibonacci generalizada de orden $k$, $\{f_{k,n}\}$, y su correspondiente representación matricial $Q^k_n$. Estas matrices satisfacen propiedades estándar como $Q^n_k Q^l_k = Q^{n+l}_k$ y reglas de determinante específicas basadas en el orden $k$.
• Secuencias de Lucas Generalizadas: Se define una nueva secuencia $\{l_{k,n}\}$ donde los valores iniciales se derivan de la traza de las primeras $k$ matrices GFM ($l_{k,r} = \text{trace}(Q^r_k)$). La relación de recurrencia refleja la secuencia de Fibonacci generalizada: $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• Matrices de Lucas Generalizadas (GLM): Se construye una matriz recursiva $L^{(n)}_k$ utilizando combinaciones lineales de términos de la secuencia de Lucas generalizada. Los autores establecen una relación fundamental entre GLM y GFM:
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  donde $L^{(0)}_k$ es la matriz de Lucas inicial.

2. Esquema Criptográfico

El sistema propuesto integra estas matrices en un Cifrado de Afín-Hill modificado combinado con la infraestructura de clave pública de ElGamal.

• Intercambio de Claves (basado en ElGamal):

  • Receptor (Bob): Selecciona un primo $p$, una raíz primitiva $\alpha$ y un entero secreto $D$. Publica $E_1 = \alpha$ y $E_2 = \alpha^D \pmod p$.
  • Emisor (Alice): Elige un entero aleatorio $e$. Computa una firma $s = E_1^e \pmod p$ y un secreto compartido $\lambda = E_2^e \pmod p$.
  • Transmisión: Alice envía el texto cifrado y la firma $s$ a Bob. Ella no envía la matriz de clave completa ni el secreto $\lambda$.

• Cifrado (Afín-Hill con GLM):

  • Utilizando el secreto compartido $\lambda$ (orden de la matriz) y la firma $s$ (exponente), Alice construye la matriz de clave de cifrado $K = L^{(s)}_\lambda \pmod p$.
  • Se genera un vector de desplazamiento $B$ utilizando términos de la secuencia de Lucas: $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • Los bloques de texto plano $P$ se cifran como $C = (P \cdot K + B) \pmod p$.

• Descifrado:

  • Bob recupera $\lambda$ utilizando su clave privada: $\lambda = s^D \pmod p$.
  • Construye la matriz inversa $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$, donde $H = (L^{(0)}_\lambda)^2$. El artículo demuestra que $L^{(s)}_\lambda L^{(-s)}_\lambda = H$, asegurando la existencia de una inversa.
  • El descifrado se realiza como $P = (C - B) \cdot K^* \pmod p$.

Contribuciones Clave

1. Definición de Matrices de Lucas Generalizadas: El artículo define formalmente la GLM de orden $k$ y establece sus propiedades algebraicas, incluyendo fórmulas de determinante, reglas de producto ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$) y la construcción explícita de sus inversas.
2. Generación de Claves Basada en Parámetros: A diferencia de los cifrados basados en matrices tradicionales donde toda la matriz debe ser compartida o generada a partir de una semilla grande, este esquema permite que la matriz de clave sea reconstruida por ambas partes utilizando solo dos parámetros: $\lambda$ (derivado del problema del logaritmo discreto) y $s$ (la firma).
3. Integración con Afín-Hill y ElGamal: Los autores proponen un esquema híbrido que utiliza la eficiencia del cifrado Afín-Hill (cifrado de bloques con un vector de desplazamiento) asegurado por la dificultad del problema del logaritmo discreto inherente a la configuración de ElGamal.
4. Construcción de la Inversa: El artículo proporciona un método específico para calcular la inversa de la GLM sin depender de la eliminación gaussiana estándar, utilizando la relación $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$.

Resultados y Análisis

• Ejemplo de Implementación: Los autores demuestran el esquema con $p=37$, orden $k=3$ y valores enteros específicos para $D$ y $e$. Logran cifrar el texto plano "NOBLE2022" en bloques de texto cifrado y recuperan el mensaje original, verificando la corrección matemática de las operaciones de matrices y la aritmética modular.
• Reducción de Complejidad: El esquema afirma reducir la complejidad de tiempo y espacio para la transmisión de claves. En lugar de transmitir una matriz $n \times n$, solo se intercambia el par $(\lambda, s)$.
• Análisis de Seguridad:
  • Logaritmo Discreto: Recuperar $\lambda$ a partir de $s$ requiere resolver el problema del logaritmo discreto, lo cual es computacionalmente inviable para primos grandes.
  • Espacio de Claves: La seguridad contra ataques de fuerza bruta depende del tamaño del Grupo Lineal General $|GL(\lambda)|$. Los autores calculan que para $p=37$ y $\lambda=50$, el espacio de claves es aproximadamente $3.105 \times 10^{3920}$, lo cual es exponencialmente grande.
  • Independencia de la Firma: El análisis sugiere que la firma $s$ no compromete la seguridad incluso si se conoce, ya que la seguridad depende primordialmente de la dificultad de determinar $\lambda$ y de la vastedad del espacio de matrices definido por $\lambda$.

Significancia y Reivindicaciones

El artículo concluye que el método propuesto ofrece un marco criptográfico matemáticamente simple pero fuerte para las partes autorizadas, mientras presenta una barrera significativa para los intrusos. La significancia radica en:

• Espacio de Claves Ampliado: El uso de matrices de Lucas generalizadas expande significativamente el espacio de claves disponible en comparación con las implementaciones estándar.
• Eficiencia: Al reducir la transmisión de claves a un par de números, el esquema mejora la eficiencia en términos de ancho de banda y almacenamiento.
• Robustez: La combinación del problema del logaritmo discreto (para el acuerdo de claves) y la complejidad de la estructura de la matriz (para el cifrado) crea una defensa de múltiples capas.

Los autores afirman que el método es "matemáticamente simple para la parte autorizada y tedioso para un intruso", basándose en la dificultad establecida del problema del logaritmo discreto y el gran espacio combinatorio de las matrices de Lucas generalizadas.