New Ideas on a New Old Type of Cipher:The Mixed-Radix One-Time Pad

Resumo Técnico: O One-Time Pad de Radix Mista (MR-OTP)

Enunciado do Problema
O artigo aborda a representação e a criptografia de dados utilizando bases não uniformes (sistemas numéricos de radix mista). Embora um preprint de 2012 tenha introduzido uma cifra baseada na decomposição de inteiros via divisores decrescentes, esta permanecia como um esboço não desenvolvido com restrições analíticas desajeitadas. O problema central é formalizar este conceito em um primitivo criptográfico rigoroso que generalize o One-Time Pad (OTP) clássico para bases mistas, determinando se o uso de bases secretas pode reduzir os requisitos de chave de informação-teórica para a segredo perfeito.

Metodologia
O autor formaliza a representação de radix mista subjacente e define o One-Time Pad de Radix Mista (MR-OTP).

• Representação: Uma mensagem $M$ é tratada como uma tupla de dígitos $(m_1, \dots, m_L)$ dentro de um espaço de dígitos definido por uma sequência de bases $B = (b_1, \dots, b_L)$, onde cada $b_i \ge 2$. A mensagem corresponde a um inteiro via pesos posicionais derivados do produto das bases subsequentes.
• Criptografia: A cifra opera dígito a dígito. Dada uma chave $K = (k_1, \dots, k_L)$ extraída uniformemente ao acaso do espaço de chaves, a criptografia é realizada como $c_i = (m_i + k_i) \mod b_i$.
• Descriptografia: A operação inversa é $m_i = (c_i - k_i) \mod b_i$.
• Análise: O artigo emprega a definição de Shannon para segredo perfeito, utilizando a regra de Bayes para analisar a probabilidade condicional de mensagens dados os textos cifrados. Ele também examina a entropia do espaço de chaves quando as bases são tratadas como secretas versus quando as bases são fixas.

Principais Contribuições

1. Formalização do MR-OTP: O artigo define o MR-OTP como a extensão natural do OTP para sistemas de radix mista, substituindo o XOR bit a bit pela adição por dígito módulo $b_i$.
2. Prova de Segredo Perfeito e Correção:
   • Correção: Provada ao demonstrar que o mapa de criptografia é uma bijeção no grupo cíclico finito $\mathbb{Z}_{b_i}$ para cada posição.
   • Segredo Perfeito: Provado ao demonstrar que, para uma chave uniformemente aleatória, a probabilidade de um texto cifrado $c$ dado uma mensagem $m$ é independente de $m$. Consequentemente, a probabilidade posterior da mensagem dado o texto cifrado é igual à probabilidade a priori.
3. Generalização dos OTPs Clássicos: O artigo estabelece que o OTP binário clássico é o caso específico onde todos os $b_i = 2$, e variantes de base fixa recuperam OTPs sobre alfabetos arbitrários (ex: base 26 para texto latino).
4. Resolução da Conjectura da "Chave Curta": O artigo investiga a hipótese de que tratar as bases $B$ como parte da chave secreta poderia permitir que o pad aditivo $k$ fosse mais curto que a mensagem enquanto mantém o segredo perfeito. O artigo prova que isso é falso.
   • Raciocínio: O segredo perfeito exige que o pad aditivo $k$ seja distribuído uniformemente sobre o conjunto completo $\{0, \dots, b_i-1\}$ para cada posição. Se o pad for encurtado (ou seja, não cobrir a entropia total do espaço de mensagens), a probabilidade condicional $P[C|M]$ torna-se dependente de $M$, quebrando o segredo perfeito. A entropia das bases secretas $H(B)$ adiciona-se à entropia total da chave, mas não pode substituir a entropia necessária no pad aditivo.
5. Protocolo de Sessão de Rolagem de Chave (Key-Rolling): Um protocolo prático é proposto onde uma chave inicial compartilhada é particionada em segmentos disjuntos. Cada sessão utiliza um novo segmento para o pad aditivo e um novo segmento para definir as bases para a próxima sessão. Isso preserva o segredo perfeito enquanto permite que as bases se adaptem à estrutura dos dados (ex: correspondendo à base 26 para texto) para eficiência de codificação, sem reduzir o total de material de chave consumido.

Resultos

• Limites Teóricos: O MR-OTP satisfaz o limite de Shannon $|K| \ge |M|$. O espaço de chaves e o espaço de mensagens coincidem ($K = D_B = M$), garantindo que nenhum material de chave seja desperdiçado.
• Contabilidade de Entropia: A entropia total da chave necessária é $H(K) = H(B) + H(k|B)$. Como $H(k|B) \ge H(M)$ é necessário para o segredo perfeito, a inclusão de bases secretas aumenta estritamente o requisito de entropia da chave total em vez de reduzi-lo.
• Overhead: No protocolo de sessão proposto, o overhead de transmitir as bases é negligenciável quando o tamanho médio da base é grande em relação aos bits necessários para representar a própria base. No caso degenerado de bases binárias ($b_i=2$), o overhead é igual ao comprimento do pad, não oferecendo ganho representacional sobre o OTP binário padrão.

Significância e Alegações
O artigo afirma fornecer uma "generalização limpa" do OTP que conecta a teoria de grupos algébricos (OTP sobre grupos abelianos finitos) com sistemas numéricos. Sua principal significância reside em:

• Clarificação: Formaliza rigorosamente um conceito anteriormente vago, removendo as "restrições laterais" do esboço original de 2012.
• Desmistificação de um Equívoco: Refuta explicitamente a ideia de que bases secretas poderiam baixar o requisito de chave de informação-teórica para o segredo perfeito, esclarecendo que tal redução violaria a hipótese de uniformidade essencial para a prova de Shannon.
• Utilidade Prática: Posiciona a estrutura de radix mista não como um método de compressão de chave, mas como uma ferramenta de eficiência de codificação e adaptabilidade. Ao combinar bases com o alfabeto da fonte (ex: DNA ou texto), o sistema evita a conversão binária artificial e o preenchimento (padding), tornando o OTP mais eficiente em representação enquanto mantém o rigoroso segurança de informação-teórica.

O artigo conclui identificando problemas abertos relativos à dureza do caso médio para recuperar bases secretas e a seleção ótima de bases para fontes estruturadas, observando que a segurança da seleção da base em si permanece uma questão computacional, e não de informação-teórica.