Análise de provável cenário criptográfico pós computação quântica: viabilidade quanto à segurança dos algoritmos assimétricos

Processando o Saber nº 7, 2015 80 ANÁLISE DE PROVÁVEL CENÁRIO CRIPTOGRÁFICO PÓS COMPUTAÇÃO QUÂNTICA: VIABILIDADE QUANTO À SEGURANÇA DOS ALGORITMOS ASSIMÉTRICOS SALGADO, Rodrigo Lopes, Especialista* *Faculdade de Tecnologia de Praia Grande Departamento de Análise e Desenvolvimento de Sistemas Praça 19 de Janeiro, 144, Boqueirão, Praia Grande/SP, CEP: 11700-100 Telefone (13) 3591-1303 [email protected] RESUMO após o advento da construção, para utilização em ambiente produtivo, de computadores baseados na arquitetura quântica. Discute-se a teoria dos números ou em curvas elípticas, perante o alto poder de processamento proporcionado por este novo paradigma computacional. O momento analisado compreende o intervalo de tempo que se dará após a construção, de fato, do computador quântico. Provavelmente, investe no desenvolvimento do computador quântico, com custos de pesquisa e manutenção muito elevados para os padrões de países em desenvolvimento, tornando o uso da capacidade de processamento deste computador um excelente ponto forte alavancador de oportunidades. PALAVRAS-CHAVE: ABSTRACT The paper presents a possible scenario that would be established immediately after the advent of construction of commercial computers based on quantum architecture. It discusses the security of the asymmetric cryptographic algorithms based on number theory and https://doi.org/10.5281/zenodo.15558187 Processando o Saber nº 7, 2015 81 elliptic curves, before the high processing power provided by this new computing paradigm. The analysis includes the time interval that will occur after construction of the quantum computer. It will probably be done by some economic superpower which already invests in the development of quantum computer, which has very high research and maintenance costs by the standards of developing countries, making the use of processing capacity of this computer an excellent opportunity generator. KEY-WORDS: quantum computer, criptography, security. INTRODUÇÃO A arquitetura e organização de computadores está vivenciando um momento de iminente avanço. A computação clássica, como se e criptoanálise em um nível que permita ser vislumbrado um cenário em que exista um computador quântico com capacidade real de processamento que torne completamente obsoleto os métodos de segurança baseados na fatoração de números primos muito grandes. 1 COMPUTAÇÃO QUÂNTICA Desde os anos 1940 a computação vem sendo desenvolvida, inicialmente patrocinada pelas nações que atuavam no esforço de guerra desprendido durante a Segunda Guerra Mundial. Muitos dos presentes na computação atual. A própria arquitetura do computador Processando o Saber nº 7, 2015 82 Segundo Stallings (2010), todo computador ainda é composto Ainda utilizam a mesma macrotecnologia baseada na eletrônica utilizando transistores para a realização dos cálculos binários. O que componentes, proporcionando reduções de escalas que passaram nanométricas em 1993. Os computadores atuais possuem transistores fabricados e manipulados a uma escala de 22 nm. Muitos físicos e estudiosos acreditam que esta distância entre componentes está muito próxima do limite para que um elétron não salte de um transistor para Null e Lobur (2010) concordam com o posicionamento de Stallings (2010) e apresentam algumas opções de arquiteturas computacionais possíveis, porém nem um pouco economicamente viáveis em termos de custo benefícios. Uma das opções seria a computação ótica ou fotônica, onde se utiliza fótons de luz laser ao invés de elétrons para realização da lógica e armazenamento do estado binário. aproxima-se muito da velocidade da luz no vácuo além de poderem que merece mais cuidado com taxas de velocidade e blindagens no caso dos circuitos elétricos. Existem também computadores biológicos construídos com organismos vivos ao invés de silício inorgânico. Um exemplo clássico é o computador criado por cientistas americanos que utiliza neurônios de sanguessugas - projeto , como Por fim, tem-se a computação quântica como uma nova arquitetura. Esta baseia-se na mecânica quântica. Enquanto um elétron armazena apenas um bit, podendo estar ligado ou desligado, computadores quânticos utilizam quantum bits (qubits) que podem assumir diversos estados simultaneamente. Explicar mecânica quântica é uma tarefa árdua. Entender tende a ser muito mais complexo. Os princípios mecânicos da física clássica não se aplicam à mecânica quântica, e propriedades como uma partícula estar ao mesmo tempo em vários lugares, superposicionandose, mantendo ao mesmo tempo ambos os estados binários Processando o Saber nº 7, 2015 83 (ligado e desligado) torna-se difícil de ser aceito. Mas isto ocorre na mecânica quântica. 1.1 QUBITS, BITS E FORÇA BRUTA Um computador quântico com apenas três qubits pode armazenar, ao mesmo tempo, os estados ligado (1) e desligado (0) em cada um dos três qubits, gerando as oito combinações possíveis. Um computador clássico só consegue manter uma das oito combinações por vez. Portanto, só consegue executar cálculos com uma das combinações por vez, também. Já no computador quântico, é possível que os oito cálculos sejam realizados simultaneamente. Um computador quântico com apenas 600 (seiscentos) qubits teria um poder de processamento impossível de ser simulado em uma arquitetura clássica. Null e Lobur (2010) ainda apontam outra questão a favor da componentes fabricados em silício e podem, teoricamente, funcionar sem consumo de energia. Em vista do exposto, percebe-se que a arquitetura quântica é muito mais poderosa em termos de capacidade de processamento pelo fato de realizar simultaneamente cálculos com todas as combinações possíveis de variáveis (booleanas). Sendo assim, um computador quântico mostra sua superioridade quando o paralelismo quântico se possíveis de um usuário de computador, ou testar todas as combinações bancária em uma transação eletrônica. O “testar todas as combinações possíveis” tecnicamente é testar todas as possíveis combinações não é tão simples como parece. No sistema binário (e o computador quântico também é binário) a quantidade de combinações possíveis se dá na ordem de 2n, onde n composta por apenas 3 bits, tem-se 23 Processando o Saber nº 7, 2015 84 Sendo elas: 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 mínimo 128 bits, ou seja, existem 2128 para se testar (2128 38 7.431.768.211.456). Um supercomputador consegue “testar” cerca de assim seria necessário 1x1020 2 CRIPTOGRAFIA E CRIPTOANÁLISE Segundo Stallings (2008), o processo de reverter um texto assimetricamente para a forma clara. Porém, o que se discute no cenário criptológico é que um Discute-se também o ambiente “conspiratório” que sempre permeou Processando o Saber nº 7, 2015 85 tornaram públicos, gerando assim uma enorme vantagem competitiva frente destas descobertas e usufruíram muito desta vantagem, tanto militarmente quanto no âmbito corporativo. Sendo assim, existindo altos investimentos na construção de um computador quântico, não é difícil conectar uma das aplicações deste computador (ou até mesmo protótipo) com a tarefa de criptoanalisar como na alta probabilidade disto ocorrer, ou até mesmo, já estar ocorrendo. 2.1 SEGURANÇA MATEMÁTICA Misoczki (2009) aponta a existência de dois grandes grupos. O primeiro baseado na problemática relacionada à teoria dos números, e tendo a fatoração de números inteiros em primos como principal elemento complicador matemático, como por exemplo o RSA. O segundo grupo utiliza-se dos logaritmos discretos, sendo amplamente representado (Elliptic Curve Digital Signature Algorithm) é um exemplo. Atente-se ao fato de que a Agência Nacional de Segurança dos Estados Unidos da América - NSA (National Security Agency), considerada a maior autoridade de segurança e inteligência do governo baseada nos princípios matemáticos descritos anteriormente. Ambos os cifragem e decifragem. Portanto, torna-se evidente que a problemática problema de um logaritmo discreto para um grupo de uma curva elíptica que garantem a segurança da informação, seja ela armazenada ou trafegando em redes de telecomunicações. Processando o Saber nº 7, 2015 86 2.2 ALGORITMO DE SHOR aplicada do MIT (Massachusetts Institute of Technology), publicou um quântica. Ele criou um algoritmo quântico (que necessariamente depende de um computador quântico para funcionar) capaz de fatorar números inteiros: dado um número inteiro G o algoritmo descobre seus fatores primos. Esta tarefa, que até então era impraticável, tornase viável (desde que se construa um computador quântico com certa quantidade de qubits). A Tabela 1 ilustra esta situação, que segundo Costa (2008) através da fatoração do número inteiro G nos primos p e q p.q). Foram utilizados três métodos para efeito de comparação: Força foi considerado que tanto o computador quântico quanto o clássico realizassem 1012 Tabela 1 - Comparativo entre métodos de fatoração. Método Chave 128 bits Chave 1024bits Força Bruta 210 dias 4 x 10134 anos 0,0006 segundos 11,3 anos 0,002 segundos 0,01 segundos Fonte: Costa (2008). A Tabela 1, de Costa (2008), evidencia o que Misoczki e do computador quântico quanto à segurança dos atuais algoritmos fatoração de inteiros primos e logaritmos discretos estão vulneráveis 2.3 COMPUTADOR QUÂNTICO NA CRIPTOANÁLISE Alguns protótipos funcionais de computadores quânticos já foram construídos e operam com um número ainda muito reduzido de bits quânticos, na ordem de 2 a 4 qubits. Processando o Saber nº 7, 2015 87 Segundo Lucero (2012) e Xu (2013) computadores quânticos tem quebrado recordes na resolução de fatoração de primos. Ainda que pequenos primos, como o número quinze, vinte e um no ano de 2012. E o número primo 143 (cento e quarenta e três) no ano de 2013. Ainda que o número primo 143 aparente ser muito pequeno em cientistas quânticos destaca neste projeto é a técnica de processamento pesquisadas de computação quântica são baseadas em condensados de Bose-Einstein e, mais recentemente, em dispositivos de estado sólido, incluindo semicondutores e diamante. Porém, neste projeto utilizou-se “computação adiabática em fase líquida”, segundo Xu (2013). Percebe-se assim que, independentemente do mérito, tipo ou técnica de construção do computador quântico, cientistas tem com capacidades teóricas de serem escalonados para que possam fatorar na técnica A, B ou C. 2.3.1 Computador quântico D-WAVE TWO™ do Silício, na Califórnia. E de fato, após este anúncio foi publicada a 512 qubits (Figura 1). Processando o Saber nº 7, 2015 88 Figura 1 - Computador Quântico D-WAVE TWO Passado algumas semanas do anúncio feito por Neven muitas controvérsias foram levantadas por toda a comunidade cientistas quântico. A maioria dos pesquisadores não tem acesso ao sistema Ainda segundo Hruska, o que muito se discute quanto ao postura quanto à organização e arquitetura do computador. Em um recente estudo realizado em janeiro de 2014 por quantum simulated annealing”. Ele criou um modelo com