Resumo Técnico: Uma Nova Criptografia de Chave Pública Baseada em Matrizes de Lucas Generalizadas

Declaração do Problema

O artigo aborda a necessidade de esquemas de criptografia de chave pública aprimorados que ofereçam espaços de chaves maiores, complexidade de transmissão reduzida e segurança robusta baseada em teoria dos números e álgebra linear. Embora a teoria das matrizes e sequências recursivas (como as sequências de Fibonacci e Lucas) tenham sido utilizadas na criptografia (ex: Cifra de Hill, ElGamal), os métodos existentes frequentemente envolvem a troca de grandes matrizes de chave ou dependem de propriedades padrão de sequências. Os autores propõem um sistema que minimiza os dados trocados durante o acordo de chaves, enquanto maximiza a complexidade do espaço da chave de criptografia através do uso de matrizes recursivas generalizadas.

Metodologia

1. Fundamentos Matemáticos

O núcleo do esquema proposto baseia-se na construção de Matrizes de Lucas Generalizadas (MLG) derivadas de Matrizes de Fibonacci Generalizadas (MFG).

• Matrizes de Fibonacci Generalizadas (MFG): Os autores utilizam a sequência de Fibonacci generalizada de ordem $k$, $\{f_{k,n}\}$, e sua correspondente representação matricial $Q^k_n$. Estas matrizes satisfazem propriedades padrão como $Q^n_k Q^l_k = Q^{n+l}_k$ e regras de determinante específicas baseadas na ordem $k$.
• Sequências de Lucas Generalizadas: Uma nova sequência $\{l_{k,n}\}$ é definida onde os valores iniciais são derivados do traço das primeiras $k$ matrizes MFG ($l_{k,r} = \text{trace}(Q^r_k)$). A relação de recorrência espelha a sequência de Fibonacci generalizada: $l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$.
• Matrizes de Lucas Generalizadas (MLG): Uma matriz recursiva $L^{(n)}_k$ é construída utilizando combinações lineares de termos da sequência de Lucas generalizada. Os autores estabelecem uma relação fundamental entre MLG e MFG:
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  onde $L^{(0)}_k$ é a matriz de Lucas inicial.

2. Esquema Criptográfico

O sistema proposto integra estas matrizes em uma Cifra Afim-Hill modificada combinada com a infraestrutura de chave pública ElGamal.

• Troca de Chaves (Baseada em ElGamal):

  • Receptor (Bob): Seleciona um primo $p$, uma raiz primitiva $\alpha$ e um inteiro secreto $D$. Ele publica $E_1 = \alpha$ e $E_2 = \alpha^D \pmod p$.
  • Remetente (Alice): Escolhe um inteiro aleatório $e$. Ela computa uma assinatura $s = E_1^e \pmod p$ e um segredo compartilhado $\lambda = E_2^e \pmod p$.
  • Transmissão: Alice envia o texto cifrado e a assinatura $s$ para Bob. Ela não envia a matriz de chave completa ou o segredo $\lambda$.

• Criptografia (Afim-Hill com MLG):

  • Usando o segredo compartilhado $\lambda$ (ordem da matriz) e a assinatura $s$ (expoente), Alice constrói a matriz de chave de criptografia $K = L^{(s)}_\lambda \pmod p$.
  • Um vetor de deslocamento $B$ é gerado usando termos da sequência de Lucas: $B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$.
  • Blocos de texto simples $P$ são criptografados como $C = (P \cdot K + B) \pmod p$.

• Descriptografia:

  • Bob recupera $\lambda$ usando sua chave privada: $\lambda = s^D \pmod p$.
  • Ele constrói a matriz inversa $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$, onde $H = (L^{(0)}_\lambda)^2$. O artigo prova que $L^{(s)}_\lambda L^{(-s)}_\lambda = H$, garantindo a existência de uma inversa.
  • A descriptografia é realizada como $P = (C - B) \cdot K^* \pmod p$.

Contribuições Principais

1. Definição de Matrizes de Lucas Generalizadas: O artigo define formalmente a MLG de ordem $k$ e estabelece suas propriedades algébricas, incluindo fórmulas de determinante, regras de produto ($L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$) e a construção explícita de suas inversas.
2. Geração de Chave Baseada em Parâmetros: Diferente das cifras baseadas em matrizes tradicionais, onde toda a matriz deve ser compartilhada ou gerada a partir de uma grande semente, este esquema permite que a matriz de chave seja reconstruída por ambas as partes usando apenas dois parâmetros: $\lambda$ (derivado do problema do logaritmo discreto) e $s$ (a assinatura).
3. Integração com Afim-Hill e ElGamal: Os autores propõem um esquema híbrido que utiliza a eficiência da cifra Afim-Hill (criptografia de bloco com um vetor de deslocamento) protegida pela dificuldade do problema do logaritmo discreto inerente à configuração ElGamal.
4. Construção da Inversa: O artigo fornece um método específico para calcular a inversa da MLG sem depender da eliminação de Gauss padrão, utilizando a relação $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$.

Resultados e Análise

• Exemplo de Implementação: Os autores demonstram o esquema com $p=37$, ordem $k=3$ e valores inteiros específicos para $D$ e $e$. Eles criptografam com sucesso o texto simples "NOBLE2022" em blocos de texto cifrado e recuperam a mensagem original, verificando a correção matemática das operações de matriz e aritmética modular.
• Redução de Complexidade: O esquema afirma reduzir a complexidade de tempo e espaço para a transmissão da chave. Em vez de transmitir uma matriz $n \times n$, apenas o par $(\lambda, s)$ é trocado.
• Análise de Segurança:
  • Logaritmo Discreto: Recuperar $\lambda$ a partir de $s$ requer resolver o problema do logaritmo discreto, que é computacionalmente inviável para primos grandes.
  • Espaço de Chave: A segurança contra ataques de força bruta depende do tamanho do Grupo Linear Geral $|GL(\lambda)|$. Os autores calculam que para $p=37$ e $\lambda=50$, o espaço de chaves é aproximadamente $3.105 \times 10^{3920}$, o que é exponencialmente grande.
  • Independência da Assinatura: A análise sugere que a assinatura $s$ não compromete a segurança mesmo se for conhecida, pois a segurança depende primordialmente da dificuldade de determinar $\lambda$ e da vastidão do espaço de matrizes definido por $\lambda$.

Significância e Alegações

O artigo conclui que o método proposto oferece um quadro criptográfico matematicamente simples, porém forte, para as partes autorizadas, enquanto apresenta uma barreira significativa para intrusos. A significância reside em:

• Espaço de Chave Ampliado: O uso de matrizes de Lucas generalizadas expande significativamente o espaço de chaves disponível em comparação com implementações padrão.
• Eficiência: Ao reduzir a transmissão da chave para um par de números, o esquema melhora a eficiência em termos de largura de banda e armazenamento.
• Robustez: A combinação do problema do logaritmo discreto (para o acordo de chaves) e a complexidade da estrutura da matriz (para a criptografia) cria uma defesa de múltiplas camadas.

Os autores afirmam que o método é "matematicamente simples para a parte autorizada e tedioso para um intruso", baseando-se na dificuldade estabelecida do problema do logaritmo discreto e no vasto espaço combinatório das matrizes de Lucas generalizadas.