Compartilhamento de informações sensíveis da cadeia de suprimentos: Um estudo sobre vulnerabilidades nos sistemas de criptografia RSA a partir do uso do algoritmo de shor
Este trabalho propõe uma análise comparativa de algoritmos, considerando-se como base o Algoritmo de Shor. No trabalho emprega-se a ferramenta de inteligência artificial ChatGPT, solicitando-a que elabore códigos na linguagem e computação quântica Qiskit em dois momentos: agosto de 2023 e fevereiro de 2024. Os resultados mostraram que houve um aprendizado considerável da ferramenta ChatGPT em relação às melhores estratégias de implementação do algoritmo, de tal forma que, considerando a última sugestão, de fevereiro de 2024, tem-se um risco considerável à criptografia RSA, caso este tipo de código seja implementado sem supervisão nos ambientes de acesso remoto a computadores quânticos. Destaca-se que o risco à criptografia RSA tem implicações diretas na logística contemporânea, especialmente no compartilhamento de informações sensíveis na cadeia de suprimentos, aumentando a necessidade de desenvolvimento de soluções em segurança da informação que possibilitem prevenir ou atenuar as consequências de tal avanço.
Este trabalho propõe uma análise comparativa de algoritmos, considerando-se como base o Algoritmo de Shor. No trabalho emprega-se a ferramenta de inteligência artificial ChatGPT, solicitando-a que elabore códigos na linguagem e computação quântica Qiskit em dois momentos: agosto de 2023 e fevereiro de 2024. Os resultados mostraram que houve um aprendizado considerável da ferramenta ChatGPT em relação às melhores estratégias de implementação do algoritmo, de tal forma que, considerando a última sugestão, de fevereiro de 2024, tem-se um risco considerável à criptografia RSA, caso este tipo de código seja implementado sem supervisão nos ambientes de acesso remoto a computadores quânticos. Destaca-se que o risco à criptografia RSA tem implicações diretas na logística contemporânea, especialmente no compartilhamento de informações sensíveis na cadeia de suprimentos, aumentando a necessidade de desenvolvimento de soluções em segurança da informação que possibilitem prevenir ou atenuar as consequências de tal avanço.
A segurança digital moderna apoia-se na criptografia assimétrica, com o algoritmo RSA-2048, baseado na fatoração de grandes números primos, sendo um pilar crucial para a proteção de dados sensíveis e transações financeiras globais (Rivest et al., 1978). No entanto, o avanço da computação quântica, que utiliza os princípios de superposição e emaranhamento, representa uma ameaça crescente, pois possibilita a execução do algoritmo de Shor, o que pode comprometer a segurança do RSA-2048 em um futuro incerto. Esse risco é ampliado pela ascensão da inteligência artificial, que não apenas fortalece as defesas, mas também potencializa ataques, como os baseados em aprendizado profundo para a identificação de vulnerabilidades (Goodfellow et al., 2016). Em resposta, o National Institute of Standards and Technology (NIST) tem conduzido a padronização de algoritmos pós-quânticos, como Kyber, Dilithium e SPHINCS+, para enfrentar esses desafios (NIST, 2023). Contudo, esses algoritmos enfrentam limitações, como o tamanho das chaves e a vulnerabilidade a ataques de canal lateral, exigindo validação contínua e auditorias rigorosas (Lizardi et al., 2022). O presente estudo, de natureza qualitativa e exploratória, examina o impacto da computação quântica e da inteligência artificial sobre o RSA-2048, abordando a urgência da migração para protocolos pós-quânticos. A análise discute os desafios técnicos, políticos e éticos dessa transição, projetando um futuro de vulnerabilidade potencial do RSA-2048 nas próximas décadas, condicionado ao avanço da computação quântica e à capacidade de adaptação das infraestruturas de segurança (Morris et al., 2022).
0 algoritmo de Shor e a evolução da computação quântica trouxeram grandes ameaças à segurança dos criptossistemas atuais. Pela necessidade de se encontrar novas alternativas, surgiu a criptografia pós-quântica. Esta dissertação pode ser dividida em três partes principais. Na primeira apresentamos alguns elementos de teoria dos números e descrevemos um criptossistema clássico, o RSA, cuja segurança pode ser facilmente quebrada recorrendo a ataques quânticos. Na segunda parte descrevemos a implementação do algoritmo de Shor, que é um ataque a esse e a todos os criptossistemas cuja segurança reside no problema da fatorização ou no problema do logaritmo discreto. Na implementação deste algoritmo minimizámos o número de qubits necessários. Para isso, utilizámos transformadas de Fourier quânticas para realizar operações como a adição, a multiplicação e a exponenciação modular. Assim, segundo a nossa abordagem, precisámos de apenas Li + 2L2 + 3 qubits, para implementar o algoritmo de Shor, ou seja, para encontrar o período da função /(x) = ax mod N, onde Li corresponde ao número de qubits necessários para representar x tal que N2 < 2L1 < 2N2 e L2 corresponde ao número de qubits necessários para representar N. Por fim, na última parte desta dissertação, apresentaremos elementos da criptografia pós-quântica, em particular, um protocolo proposto por nós. Este é uma nova variante do criptossistema de McEliece, no qual se propõe o uso de códigos convolucionais em vez do uso de códigos de bloco. Assim, a parte codificadora da nossa chave pública, que denotaremos por G'(D), será ela própria convolucional. Ao estudarmos várias possibilidades de ataques para este criptossistema, verificámos que, em comparação com as restantes variantes, para uma chave pública menor conseguimos ter um fator de trabalho muito maior, o que se traduz numa maior segurança
A seguranca de dados e fundamental para a execucao de diversas tarefas do cotidiano, seja acessar contas bancarias ate o funcionamento de carros autonomos. Algoritmos de criptografia, existente desde o inicio dos tempos em diferentes formas, foram criados para garantir a integridade destes dados. Um dos algoritmos de seguranca mais utilizados, o Rivest-Shamir-Adleman (RSA) tornou importante a fatoracao, para saber qual o estado da arte da criptografia e saber quanto tempo levara para fatorar numeros muito grandes, que e o que torna o RSA seguro atualmente. Ha diversas implementacoes de algoritmos de fatoracao, porem, nenhum apresenta uma eficiencia adequada para quebrar a criptografia RSA. No entanto, com o avanco da computacao quântica, como uma necessidade fisica resultante do encolhimento dos chips de processamento dos computadores, a seguranca da informacao e colocada em cheque com o Algoritmo de Shor, desenvolvido por Peter Shor na decada de 1990, que e mais eficiente que os algoritmos classicos de fatoracao, e pode ser capaz de quebrar a criptografia RSA em tempo habil no futuro. O objetivo do presente artigo e apresentar uma analise de diferentes algoritmos de fatoracao classicos e compara-los com o Algoritmo de Shor para mostrar as falhas de seguranca que existirao na era da computacao quântica.
Resumo A criptografia clássica utiliza suposições de dificuldade computacional, como a fatoração de grandes números, para garantir segurança na comunicação. Tal uso pode ser comprometido por avanços de hardware ou software, como a implementação do algoritmo de Shor pela computação quântica. O trabalho em tela explora a segurança da criptografia quântica atrelada inteiramente às leis da mecânica quântica, em um contexto no qual busca-se gerar, de forma segura, chaves clássicas por meios quânticos com a Distribuição Quântica de Chaves para posterior uso em algoritmos como o one-time-pad. A pesquisa teve foco na QKD dependente de equipamentos, mais especificamente dentro da categoria de preparação e medição, contemplando implementações práticas do protocolo de seis estados feitas no IBM Quantum Experience platform. Explora-se cenários ideais, ruidosos, com e sem adversários, analisando os resultados através do QBER. O trabalho abrange ainda conceitos sobre os procedimentos de pós-processamento de reconciliação da informação e amplificação privada, mencionando eventuais ataques quânticos e suas contramedidas, citando a distribuição quântica de chaves independente de dispositivos como uma das possíveis abordagens de solução.
Sistemas criptográficos clássicos, como o RSA e o ElGamal, mostraram ser vulneráveis na presença de um computador quântico suficientemente poderoso. Dada esta descoberta, a comunidade científica focou a sua atenção no desenvolvimento e estudo de alternativas imunes a arquiteturas quânticas. Sistemas baseados em treliças são um dos criptossistemas que se provou serem resistentes a ataques por parte de computadores quânticos. Estes criptossistemas baseiam a sua segurança em problemas matemáticos duros, como o Problema do Vetor mais Curto (Shortest Vector Problem, SVP), Problema do Vetor mais Próximo (Closest Vector Problem, CVP), e outros. Assim sendo, o estudo de algoritmos desenhados para resolver estes problemas -- também conhecidos como ataques -- é de extrema importância, com o objetivo de os entender melhor, e por forma a melhor selecionar os parâmetros de construção destes criptossistemas. O foco desta dissertação é um tipo específico de ataque: algoritmos baseados em célula de Voronoi, que são frequentemente mencionados na literatura como sendo impráticos, mas que têm sido alvo de muito pouca pesquisa, especialmente quando comparados com outros tipos. Nesta dissertação, várias otimizações para um algoritmo baseado em célula de Voronoi são propostas, com o objetivo de reduzir tanto o tempo de execução, como os requisitos de memória das implementações. De modo a aproveitar todo o poder computacional disponível nos computadores modernos, versões paralelas em CPU, GPU e heterogénea CPU + GPU são propostas, apresentando ganhos lineares no primeiro caso (e algum benefício com Hyper-Threading), e reportando ganhos de 13.37x e 15.03x, para as versões GPU e heterogénea, respetivamente, quando comparadas com a versão sequencial base em CPU. Adicionalmente, diversas variantes heurísticas com implementações paralelas em CPU são propostas, com o intuito de acelerar a computação da solução do SVP, com a melhor estratégia de "poda" desenvolvida a alcançar ganhos até 256.51x, usando 8 threads (quando comparada com a versão sequencial base em CPU), calculando a solução correta para 99.84% das bases testadas. Finalmente, conduzida no âmbito desta dissertação, a integração de todo o trabalho na biblioteca Lattice Unified Set of Algorithms (LUSA) -- um projeto que ambiciona disponibilizar acesso público a uma coleção de implementações rápidas e fáceis de utilizar, de algoritmos relacionados com treliças. Os resultados obtidos nesta dissertação mostram, ainda que longe das dimensões do estado da arte, que é possível acelerar imensamente um algoritmo baseado em célula de Voronoi, mantendo taxas de sucesso extremamente elevadas.
Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas