CRIPTOGRAFIA QUANTICA DOS COMPUTADORES DO FUTURO

3. Aplicações

Usos da criptografia

A criptografia – seja ela tradicional ou quântica – possui usos importantes em áreas variadas, divididos principalmente entre duas vertentes, que recebem o nome de confidencialidade e autenticidade.
O uso mais comum da criptografia é garantir a segurança de informações sigilosas (confidencialidade), codificando os dados de forma que apenas aqueles que tiverem o direito de lê-la o possam fazer. Um documento que se deseja manter secreto é codificado usando alguma das técnicas existentes, e a chave apropriada é fornecida ao receptor (possivelmente usando algum meio diferente), que a utiliza para decodificar os dados criptografados e obter o documento original. Caso algum espião tenha acesso aos dados criptografados durante a transferência ou armazenamento, este não terá como ler o conteúdo verdadeiro do documento.
A segunda categoria de uso é a autenticação, que está relacionada à comprovação de que uma mensagem foi realmente enviada por quem diz ser o remetente, ou que o conteúdo de um documento não foi alterado. Normalmente trabalha-se com funções de hash, que produzem uma cadeia de símbolos substancialmente menor que o texto original e permitem uma comparação rápida. Estas funções são preparadas de forma que pequenas alterações no documento original gerem mudanças significativas na cadeia resultante.
Na autenticação de remetente, este assina a mensagem com sua chave privada – ou seja, gera um hash da mensagem enviada e depois aplica uma criptografia assimétrica sobre o hash utilizando sua chave – e aqueles que quiserem verificar a autenticidade comparam o hash da mensagem recebida com o resultado da aplicação da chave pública do remetente sobre a assinatura enviada.

Veja mais: Assinaturas digitais

Criptoanálise quântica

A segurança da criptografia atual, em especial a criptografia assimétrica, baseia-se na dificuldade de se solucionar alguns problemas matemáticos. As soluções conhecidas para estes problemas têm complexidade não-polinomial: apesar de serem, em teoria, solucionáveis, quando se utiliza chaves com tamanho adequado, o tempo previsto de solução ultrapassa as centenas de anos, tornando ataques brutos impraticáveis.
Entretanto, a computação quântica permite que estes problemas sejam resolvidos em pouco tempo – chegando à ordem dos segundos – pois várias soluções podem testadas ao mesmo tempo, de forma análoga a uma computação paralela, mas com apenas um processador. Esta revolução na criptoanálise inutilizaria as técnicas atualmente conhecidas de criptografia para aqueles com computadores quânticos em seu poder, tornando necessário o desenvolvimento de uma nova classe de técnicas criptográficas. Está em curso, por esta razão, uma corrida científica na pesquisa da criptologia quântica, sendo considerada matéria de segurança nacional em vários países.
O algoritmo mais conhecido que utiliza as vantagens da computação quântica é o algoritmo de Shor, desenvolvido em 1994, que é capaz de fatorar números primos com complexidade O(log³ n), enquanto o melhor algoritmo clássico leva um tempo exponencial. O esquema de chave pública RSA pode ser quebrado usando este algoritmo.
O algoritmo de Shor aplica os seguintes passos para encontrar os fatores de um número N, múltiplo de dois primos. Todos os passos exceto o 3 podem ser executados em um computador clássico.

1. Escolher um número a menor que N.
2. Calcular o maior divisor comum entre a e N. Caso não seja 1, um dos fatores foi obtido.
3. Caso o maior divisor seja 1, calcular o período r da função f(x) = a^x mod N.
   A computação quântica permite testar vários pares (x, r) simultaneamente, com uma probabilidade maior que ½ de encontrar um par válido.
4. Se r for ímpar ou se a^r/2 = -1, retornar ao primeiro passo.
5. Um dos fatores desejados será o maior divisor comum entre a^r/2 ± 1 e N.

Veja mais: Algoritmo de Shor em detalhes

Distribuição de chave

Uma aplicação da criptografia quântica muito estudada é a distribuição de chaves secretas. Ela é caracterizada pelo envio seguro de uma chave de um emissor a um receptor; um intruso interceptando a transmissão pode ser detectado. O envio segue um protocolo que permite a ambas as partes acordar em uma chave sem nenhum conhecimento compartilhado prévio.
Segue abaixo um exemplo de protocolo de distribuição, baseado no protocolo BB84, desenvolvido por Charles Bennett e Gilles Brassard em 1984. Nele, Alice quer estabelecer uma chave secreta com Bob, enviando fótons independentes através de fibra ótica. Estes fótons podem estar polarizados na horizontal, vertical, sentido horário ou anti-horário. É possível medir o fóton na base linear (horizontal/vertical) ou circular (horário/anti-horário), mas não nos dois.

1. Alice envia uma certa quantidade de fótons a Bob, polarizando-os aleatoriamente.
2. Para cada fóton efetivamente recebido (é comum alguns se perderem), Bob escolhe uma base aleatoriamente e mede o fóton nessa base.
3. Bob diz a Alice as bases de medição escolhidas.
4. Alice diz quais bases foram escolhidas corretamente.
5. Ambos descartam os fótons cujas bases de medição foram escolhidas incorretamente.
6. Os fótons resultantes são convertidos para bits seguindo uma convenção (ex.: horizontal e horário representam 0 e vertical e anti-horário representam 1).
7. Bob compara com Alice alguns bits aleatórios entre os recebidos com sucesso. Caso eles sejam iguais, assume-se que a transmissão ocorreu sem interferências (tanto do meio como de espionagem); os bits comparados são descartados e os restantes são incluídos na chave secreta.
   Caso contrário, todos os bits são descartados.
8. O processo é repetido até conseguir bits suficientes para gerar a chave secreta de tamanho desejado.
9. Um espião passivo tentando monitorar o envio dos fótons irá interferir em sua polarização, de forma que a transmissão irá falhar no passo de verificação.

A distribuição de chave quântica é uma alternativa ao uso da criptografia assimétrica no envio de dados, com a vantagem de que é segura mesmo quando o inimigo conta com poder computacional ilimitado. Pode-se obter uma chave tão longa quanto se queira, e a cadeia de bits resultante pode ser utilizada como uma chave secreta para realizar uma troca de dados confidenciais codificados com criptografia simétrica tradicional sobre um canal inseguro (mas com mais banda). Pode-se ainda utilizar uma técnica chamada de amplificação de privacidade, aplicando funções de transformação (ex.: hash) sobre a chave, de forma que quaisquer bits obtidos com sucesso pelo espião tornem-se ainda menos úteis.

Veja mais: Simulador de distribuição de chaves

Esquema de compromisso

Uma das possíveis aplicações da criptografia quântica que despertou grande interesse nos pesquisadores foi o esquema de compromisso (bit commitment), no qual um usuário assume o compromisso de um valor sem, entretanto, divulgá-lo para a outra parte.
Um jogo de cara-ou-coroa à distância é um exemplo de esquema de compromisso. A jogadora Alice escolhe cara ou coroa e transmite a Bob uma informação que caracteriza sua resposta sem, entretanto, revelá-la. Bob joga então uma moeda e revela o resultado a Alice que, em seguida, divulga sua opção original. Bob, se quiser, pode conferir a resposta dada com a informação de compromisso fornecida anteriormente, de forma que Alice não pode mentir e escolher a resposta mais favorável.
Um bom esquema de compromisso possui duas características. Em primeiro lugar, a informação de compromisso deve ser fortemente ligada à resposta original (ligante – binding). Isso significa que Alice não pode ter como modificar sua resposta no futuro (para uma opção mais desejável frente a novos fatos) e a resposta modificada coincida com a informação de compromisso. Utiliza-se normalmente funções de hash ou multiplicação de números primos para geral a informação de compromisso. No caso das funções de hash, é importante que não seja possível encontrar colisões (entradas que gerem hashes iguais).
Por outro lado, não se deve permitir que a resposta original seja obtenível através da informação de compromisso (ocultante – hiding); caso contrário, Bob poderia descobrir a escolha de Alice e mentir sobre o valor da moeda a seu favor. Isto pode ocorrer por várias razões, dentre elas a função escolhida ser reversível ou o receptor ter poder computacional suficiente para fatorar o produto dos números primos. Além disso, se o domínio das respostas possíveis for pequeno, Bob pode testar cada um e tentar obter a informação de compromisso enviada.
Utilizando métodos tradicionais é impossível obter um método de esquema de compromisso que seja ao mesmo tempo perfeitamente ligante e perfeitamente ocultante. Deve-se utilizar um meio termo, ou favorecer um dos lados. Por esta razão a criptografia quântica foi vista com grande esperança quando cogitou-se que ela poderia fornecer um esquema completamente seguro. Entretanto, após uma série de tentativas de esquemas supostamente funcionais e refutações subseqüentes, provou-se definitivamente em 1993 que um esquema quântico perfeito também é impossível.

Veja mais: Vídeo sobre esquema de compromisso quântico

Transferência desinformada

Outra aplicação da criptografia que utiliza princípios da física quântica é a multiplexação quântica ou transferência desinformada (oblivious transfer), na qual o emissor envia várias cadeias de dados, mas apenas uma é lida pelo receptor. Cada cadeia de dados pode ser composta por bits ou ser vazia (ou seja, nesse caso haverá uma chance do receptor não obter informação alguma).
De forma similar ao esquema de compromisso, a transferência desinformada possui duas características que devem ser atendidas para um método de transferência seja considerado completamente seguro:

• O emissor não deve saber qual dos dados foi lido pelo receptor.
• O receptor não deve ser capaz de ler mais do que um dos dados enviados.

Também já foi provado que nenhum algoritmo, inclusive quântico, atende perfeitamente aos dois requisitos, sendo no máximo computacionalmente seguro, ou seja, válido somente enquanto algumas suposições forem mantidas.

     

Universidade Federal do Rio de Janeiro

Engenharia de Computação e Informação

Última atualização: 03/06/2008

XHTML 1.0 Transitional válido. Melhor visto