A Matrix-Based Polyalphabetic Algorithm for Information Encoding and Decoding Using Number Sequences

Resumo Técnico: Um Algoritmo Polialfabético Baseado em Matrizes para Codificação e Decodificação de Informações Usando Sequências Numéricas

Problema
O artigo aborda a vulnerabilidade dos cifradores de substituição monoalfabéticos padrão à análise de frequência. Em sistemas monoalfabéticos, o mesmo caractere do texto puro sempre mapeia para o mesmo símbolo do texto cifrado, preservando a distribuição estatística da linguagem de origem e permitindo que atacantes deduzam a chave por meio de contagens de frequência. Embora os cifradores polialfabéticos (como o de Vigenère) mitiguem isso usando múltiplos alfabetos de substituição, os autores propõem uma abordagem inovadora que combina a substituição polialfabética com o comportamento homofônico. O objetivo é distribuir símbolos repetidos do texto puro em diferentes representações numéricas baseadas na posição e na contagem de ocorrência, visamente achatando a distribuição de frequência do texto cifrado e aumentando a resistência à criptoanálise estatística.

Metodologia
O esquema proposto, denominado FLLJ-POLY, é um algoritmo de criptografia polialfabética baseado em matrizes que utiliza quatro sequências inteiras específicas: Fibonacci, Lucas, Leonardo e Jacobsthal. A metodologia prossegue através das seguintes etapas:

1. Fundamentação Teórica e Separação de Sequências:
   Os autores estabelecem que, para índices suficientemente grandes, as sequências de Leonardo, Fibonacci e Jacobsthal geram conjuntos de inteiros disjuntos entre si. Os números de Lucas são reservados especificamente para codificar separadores de palavras. Um módulo primo público livre de colisões $P$ (por exemplo, $P=10159$) é selecionado para garantir que a redução modular desses valores de sequência distintos permaneça injetiva, preservando a capacidade de decodificar os símbolos de forma única.

2. Preparação e Substituição da Mensagem:
   O texto puro é convertido em uma matriz quadrada $M$ de tamanho $3m \times 3m$, com separadores de palavras denotados por um símbolo específico (ex: $\ast$).

   • Substituição de Caracteres: Cada letra é substituída por um valor de um dos três alfabetos baseados em sequências (Fibonacci, Leonardo ou Jacobsthal). A escolha do alfabeto é determinada por uma função de seleção dependente da posição:
     $$\sigma = (v^2 + (i - 1) + (j - 1)) \pmod 3$$
     onde $v$ é a contagem de ocorrência do caractere, e $(i, j)$ são seus índices de linha e coluna. Este mecanismo garante que o mesmo caractere mapeie para diferentes valores numéricos dependendo de sua posição e frequência, introduzindo comportamento homofônico.
   • Codificação de Separadores: Os separadores de palavras são codificados usando números de Lucas com índices deslocados por um parâmetro dependente da chave $a_0$, evitando padrões previsíveis nas fronteiras das palavras.

3. Transformação de Matriz e Criptografia:
   A matriz substituída é dividida em submatrizes $3 \times 3$. Uma sequência de chave secreta $a_0, a_1, \dots, a_{k-1}$ é gerada usando uma semente pré-compartilhada $s$ e um primo $p$ via uma relação de recorrência não linear envolvendo números de Leonardo:
   $$a_{i+1} = (L_s a_i + a_i^2 + i) \pmod p$$
   Cada bloco $3 \times 3$ é criptografado multiplicando-o por uma potência da matriz $Q$-de-Leonardo ($Q^{a_{j-1}}$) módulo $P$.

4. Construção do Texto Cifrado:
   Para reduzir o tamanho da transmissão mantendo a integridade, o algoritmo transmite o determinante de cada bloco criptografado junto com oito das nove entradas da matriz. A entrada "oculta" restante é recuperada pelo receptor usando a condição do determinante, desde que o cofator correspondente seja não nulo módulo $P$.

Principais Contribuições

• Integração de Sequências Inovadora: O artigo introduz um framework unificado utilizando as sequências Fibonacci, Leonardo, Jacobsthal e Lucas simultaneamente, com provas rigorosas (Teoremas 2.1–2.5) demonstrando a disjunção de seus termos para intervalos de índices específicos.
• Híbrido Homofônico-Polialfabético: O esquema combina substituição polialfabética (mudança de alfabetos) com substituição homofônica (múltiplas representações para um símbolo) via uma função de seleção quadrática, reduzindo efetivamente a concentração de frequência.
• Geração de Chave Não Linear: As chaves de bloco são derivadas de uma relação de recorrência quadrática e não-autônoma, adicionando complexidade ao fluxo de chaves em comparação com geradores congruentes lineares.
• Implementação Modular Eficiente: Ao empregar um primo $P$ livre de colisões, os autores garantem que todas as operações permaneçam dentro dos limites da aritmética de inteiros nativos, evitando o overhead computacional da aritmética de inteiros grandes exigida por valores de sequência não reduzidos.

Resultados
Os autores apresentam um exemplo prático e uma análise estatística preliminar usando um texto em inglês de 576 caracteres:

• Segurança Estatística: O esquema reduz significativamente o Índice de Coincidência (I.C.) para aproximadamente 0,0153, comparado a 0,0667 para o inglês padrão e 0,0450 para um cifrador de Vigenère com uma chave curta. A estatística de Qui-quadrado normalizada ($\chi^2/c$) é reduzida em aproximadamente 70,6% em relação à substituição monoalfabética. A eficiência da entropia de Shannon atinge 87,8%, indicando uma distribuição quase uniforme dos símbolos do texto cifrado.
• Efeito Avalanche: Pequenas perturbações nos parâmetros da chave secreta ($s$ ou $p$) resultam em mudanças no texto cifrado que afetam aproximadamente 48,5% dos bits em média, aproximando-se do Critério de Avalanche Estrita ideal de 50%.
• Desempenho Computacional: A implementação modular alcança uma aceleração de 7 a 8 vezes nos tempos de codificação e decodificação em comparação com uma implementação não reduzida usando aritmética de inteiros grandes (GMP), com tempos de codificação para uma mensagem de 500 caracteres caindo de ~1,47 ms para ~0,21 ms.

Significância e Alegações
O artigo posiciona o FLLJ-POLY como uma alternativa matematicamente fundamentada aos cifradores de substituição padrão. Os autores alegam que a construção fornece um comportamento distributivo e eficiência computacional aprimorados. Eles enfatizam que a principal contribuição é o estabelecimento de uma base teórica numérica rigorosa para o procedimento de codificação, utilizando as propriedades de disjunção das sequências de inteiros para justificar alfabetos numéricos distintos.

Os autores declaram explicitamente que o trabalho foca no desenvolvimento e na justificativa da estrutura matemática do esquema, em vez de fornecer um tratamento criptanalítico exaustivo. Consequentemente, eles não alegam que o sistema é inquebrável; em vez disso, observam que a análise rigorosa contra ataques avançados (como ataques de texto conhecido, texto escolhido e algébricos) permanece como um objeto para trabalhos futuros. A significância reside em demonstrar um framework baseado em matrizes, reproduzível, que efetivamente achata as distribuições de frequência e oferece uma estratégia de implementação modular e eficiente.