Criptografia RSA: Uma abordagem alternativa utilizando Inteiros de Gauss

Resumo

A rápida evolução da comunicação em redes, sobretudo com a introdução de tecnologias tais como a 5G, e a crescente migração de serviços para plataformas digitais implicam desafios cada vez maiores na manutenção da privacidade e confiabilidade dos dados. Neste contexto, os algoritmos criptográficos desempenham um papel de crescente importância na segurança de dados contra ataques maliciosos. Este artigo descreve uma abordagem de criptografia assimétrica mediante uma modificação do algoritmo clássico RSA, introduzindo chaves no domínio de Fatoração Única conhecida como Inteiros de Gauss. Esta modificação parece reduzir os cálculos complexos envolvidos no algoritmo RSA fornecendo o mesmo nível de segurança de chaves inteiras com uso de uma menor quantidade de bits na chave. Definem-se os inteiros de Gauss como um subconjunto [i] = {a + bi | a, b }  C dos números complexos. Em outras palavras, um inteiro de Gauss é um número complexo de partes real e imaginária, ambas inteiras. A caracterização dos primos e unidades em  podem ser encontradas em Ireland e Rosen (1998), Conway e Guy (1996). Os inteiros de Gauss, assim como os próprios inteiros, formam anéis que são, cada um, também de Domínios de Fatoração Única, ou seja, qualquer inteiro ou inteiro de Gauss é produto unicamente definido, a menos da ordem de elementos e do produto por unidades, de elementos do anel que são nele irredutíveis o que, no caso de Dominação de Fatoração Única, são equivalentes ao conceito de primos do anel (Ireland e Rosen, 1998). O RSA é um algoritmo computacional de criptografia baseado em duas chaves, uma mantida privada e outra divulgada como chave pública, sendo então algoritmo criptográfico assimétrico ou criptografia de chave pública (Rivest, Shamir e Adleman, 1978). O algoritmo baseia-se na dificuldade computacional de encontrar os fatores de um número composto com grande quantidade de bits em sua representação binária, sendo comum pares de chaves de 256, 512 e até 1024 bits. Toda codificação do RSA pode ser feita em qualquer domínio de integridade (Das, Mishra e Sahu, 2020). Para os testes de segurança, utilizou-se a abordagem proposta pelo RSA laboratories o chamado The RSA challenge Numbers que consiste em fatorar o produto de primos de grande quantidade de bits cada. Por exemplo, o RSA-100 é um número inteiro composto de 100 dígitos (330 bits) cuja fatoração é conhecida e cujo propósito é testar os algoritmos de fatoração propostos. Atualmente a lista consta com desafios de RSA-100 (cuja solução demanda cerca de uma hora em computador comum) até RSA-2048 cuja solução não parece viável em um futuro próximo. A implementação do teste proposta neste trabalho consistiu em criar números RSA, i.e., produto de dois primos de um dado anel e fatorá-los utilizando o algoritmo Quadratic Sieve (QS) conforme Bressoud e Wagon (2000). O tamanho de um número inteiro é a sua quantidade de bits. Dos inteiros de Gauss o tamanho é a soma da quantidade de bits de suas partes real e imaginária. Foi medido o tempo de CPU em função da quantidade de bits (média da execução de 10 rodadas do algoritmo para cada uma das 10 instancias de números a serem fatorados). A configuração do computador utilizado foi um Processador Intel Celeron, com clock de 1.10GHz e memória RAM de 4,00GB rodando no sistema Operacional Windons 10. Todos os programas foram implementados em linguagem C. Os testes realizados indicam que a complexidade adicional dada no QS para inteiros de Gauss parece indicar a segurança do uso de chaves com menores quantidades de bits advindas desses dois domínios dos inteiros. Não houve diferença significativa do tempo necessário ao produto de inteiros ou inteiros de Gauss indicando que a complexidade adicional refere-se apenas ao tempo necessário a sua fatoração, mas não às operações convencionais de soma ou produto. Proposta de trabalhos futuros incluem melhorias na implementação do QS para inteiros de Gauss e inteiros de Eisenstein permitindo uma melhor comparação da complexidade como função do tamanho dos números envolvidos. Também é proposta futura a implementação do RSA nesses domínios e comparação qualitativa da codificação obtida em diferentes domínios via testes de criptoanálises em textos e imagens.