“Um dos problemas do milênio de Landon T. Clay, conhecido como P versus NP, levanta uma questão interessante sobre essas questões. Se a complexidade de um problema como fatorar números ou colorir mapas surge do enorme tamanho do palheiro que deve ser investigado, poderia sempre haver um método eficiente de encontrar a agulha? Nosso palpite é que a resposta para a questão do P versus NP seja 'não'. Há alguns problemas inerentemente complexos, que nem mesmo as técnicas de pirataria de um Gauss contemporâneo poderiam esquivar. Porém, se a resposta for 'sim', então nas palavras de Rivest, 'seria uma catástrofe para a comunidade criptográfica'. A maioria dos sistemas criptográficos, incluindo o RSA, lida com problemas relacionados a grandes palheiros. Uma resposta positiva a esse problema do milênio significaria que realmente existe uma maneira rápida de decifrar números – nós apenas ainda não a encontramos!”
Marcus du Sautoy – The Music of the primes
Atualmente, o algoritmo mais rápido para fatorar números inteiros com mais de 100 algarismos é o GNFS (General Number Field Sieve), que resolve o problema em uma complexidade sub-exponencial:
Essa notação significa que para uma entrada de tamanho 'n' a quantidade de etapas que o algoritmo tem que fazer cresce de uma forma aproxima com a expressão exposta.
Por exemplo, para saber se um número é ímpar ou par, a complexidade é O(1). Independente do tamanho da entrada, precisamos apenas do último digito para saber essa informação
Para saber o menor número em uma sequência a complexidade é O(n). O tempo de resolução cresce linearmente com o tamanho da sequencia.
A multiplicação de duas matrizes quadradas é resolvido com uma complexidade polinomial de O(n^3).
Como já foi visto, o que garante a segurança de uma criptografia de chave pública é o grau de complexidade no processo de decodificação.
Se houver um algoritmo que reduza o tempo desse processo a criptografia se torna inútil.
Em 1994, Peter Shor desenvolveu um algoritmo que pode ser aplicado com a computação quântica e resolve em tempo polinomial o problema da fatoração de números inteiros e prolemas relacionados ao logaritmo discreto. Para se ter uma idéia das mudanças que isso acarreta, há uma tabela:
"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) = ax 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 ar/2 = -1, retornar ao primeiro passo.
5. Um dos fatores desejados será o maior divisor comum entre ar/2 ± 1 e N."
Fonte:http://www.gta.ufrj.br/grad/08_1/quantica/cap3.html#sub2
Com o progresso que há na computação quântica, se espera que em poucas décadas os principais sistemas de criptografia de chave pública fiquem obsoletos.
A criptografia quântica nasce dentro da criptografia moderna como uma solução para melhorar a confiabilidade. Essa segurança é provida a partir de uma lei natural, o princípio de incerteza de Heisenberg, pois como pode-se usar duas mensagens em uma única transmissão quântica o receptor poderia ler uma mensagem de cada vez e nunca as duas simultaneamente. Uma analogia comum para isso diz que não se pode descobrir a velocidade e posição de uma partícula para um mesmo tempo, ou seja, sempre haverá uma incerteza no mundo subatômico. É dessa incerteza natural que a criptografia quântica se aproveita
Utilizando-se de pares de fótons, a criptografia quântica permite que duas pessoas sem nenhum contato criem chaves secretas. Os fótons, se forem interferidos, no meio da transmissão resultará em uma interferência do sinal que pode ser sentido pelo receptor que assim pode parar a transmissão.
A principal vantagem da criptografia quântica, como dito, é que ela é mais segura do que as demais, sendo impossível que alguém espione a comunicação sem ser detectado.
Uma desvantagem muito importante está no aspecto da aplicação desse novo sistema. Até hoje não se conseguiu alcançar grandes distâncias, mesmo sendo utilizado fibras óticas de alto grau de pureza. Quanto a transmissão no ar, é mais complicada ainda e não se chega a escala de quilômetros.. Outro peso importante a ser considerado nessa tecnologia é seu alto custo. É possível que com novas descobertas e novos equipamentos esse custo operacional caia e ela se torne mas viável.
Além disso, outro problema que afeta a criptografia é o ruído. Não se conseguiu até o presente momento fazer uma transmissão de longas distâncias uma vez que essa tecnologia ainda é muito suscetível a interferências provocadas pelo meio mesmo quando não há espião. Caso se adote uma política muito frouxa em relação a ruídos, um espião poderá não ser detectado mas caso essa política seja muito estrita a transmissão fica ainda mais difícil. É o clássico caso do cobertor curto.
Temos que para a luz polarizada de intesidade I(0) quando é filtrada por um polarizador com um ângulo 'θ' em relação ao ângulo de polarização da luz incidida, a intensidade observada será de
.
A luz que passa pelo filtro então tem uma polarização no ângulo 'θ' do filtro e intensidade I(θ) dada pela expressão.
O protocolo BB84 foi o primeiro protocolo de distribuição de chaves desenvolvido para a criptografia quântica. Criado em 1984 por Gilles Brassard e Charles Bennett, ele ainda hoje é o mais usado por sua simplicidade e eficiência. O BB84 utiliza o fato de que é impossível medir informação quântica sem distorcer essa informação, impedindo assim que a comunicação seja escutada por terceiros que não sejam detectados.
Originalmente, foi proposto que se utilizasse a polarização de fótons em diferentes direções mas outras propriedades quânticas podem ser usadas sem prejuízo à validade do protocolo. Usando a polarização, escolhe-se dois conjuntos de direções ortogonais, o retilíneo com polarizações a 0º e 90º (+) e o diagonal com polarizações a 45º e 135º (X). O emissor possui um equipamento que manda um fóton por vez, de polarização arbitrária, e o receptor possui filtros e detectores de fótons. Note que para distinguir entre as duas polarizações de cada conjunto basta o uso de um filtro adequado, mas o uso desse mesmo filtro não irá dizer nada sobre a polarização do outro conjunto. Para exemplificar, suponha um filtro que só permita a passagem de fótons polarizados verticalmente (0º). Se mandarmos um fóton do conjunto retilíneo (+), ele será detectado caso a polarização seja 0º e não será caso a polarização seja 90º. Já se utilizarmos esse filtro com fótons do conjunto diagonal (X), o equipamento terá 50% de chances de detectar e ainda irá alterar o estado do fóton original.
O BB84 utiliza dois canais destintos: um privado, com informação quântica, tal como o descrito acima e um público, tradicional. Agora, suponha que Alice (emissor) e Bob (receptor) querem estabelecer uma chave de criptografia. Alice envia fótons aleatoriamente polarizados em alguma das quatro direções possíveis e Bob escolhe aleatoriamente para cada um deles se irá utilizar um filtro retilíneo ou um filtro diagonal. Bob comunica essa escolha para Alice, pelo canal público, que por sua vez irá dizer em quais oportunidades Bob escolheu um filtro compatível com a direção de polarização que ela enviou e em quais ele usou o filtro errado. Eles então descartam os resultados que foram obtidos com os filtros errados e o que sobra é uma sequência secreta, que só é do conhecimento dos dois. Por fim, é usada uma convenção para transformar polarização em bits: polarizações de 0º ou 45º são consideradas bits 1 e polarizações de 90º ou 135º são consideradas bits 0.
Para garantir que não houve espionagem, Alice e Bob comparam uma parte, que será descartada, dessa sequência pelo canal público e verificam a integridade. Pelos fundamentos da mecânica quântica, caso alguém estivesse medindo no canal privado, a informação seria alterada e as sequências de Alice e Bob seriam diferentes. Alternativamente, pode-se utilizar informações de paridade para aumentar a confiabilidade e a eficiência dessa checagem.
O protocolo B92 foi criado por Charles Bennet em 1992 e é uma simplificação do BB84. Bennet demonstrou que para estabelecer uma chave por criptografia quântica apenas são necessárias duas direções de polarização não-ortogonais, ao invés de dois pares de direções ortogonais.
Suponha que em uma dada implementação decida-se utilizar a direção vertical, representando o bit 0, e a direção diagonal com ângulo de 45º representando o bit 1. Alice irá enviar fótons aleatoriamente polarizados em uma destas direções e Bob novamente irá utilizar filtros retilíneos (+) ou diagonais (X) para medir a polarização dos fótons, de forma também aleatória. Perceba que ao utilizar um filtro retilíneo, fótons polarizados verticalmente sempre serão detectados corretamente, mas fótons na direção 45º poderão ser detectados como verticais ou horizontais. Assim, sempre que a detecção após o filtro indicar um fóton de direção horizontal, teremos certeza que o original indicava um bit 1. Da mesma forma, ao utilizar um filtro diagonal sempre que a detecção indicar um fóton de direção 135º estaremos certos de que o original representava um bit 0.
O procedimento do B92 é muito semelhante ao anterior: são usados um canal privado quântico e um público tradicional. Alice envia fótons aleatoriamente polarizados em uma das duas direções possíveis pelo canal privado e Bob aplica um dos dois filtros, também aleatoriamente. Bob então informa a Alice pelo canal público em quais medições ele teve a certeza do bit original e esta passa a ser a sequência de bits secreta. Os dois comparam e descartam, ou utilizam mecanismos de paridade, uma parte dessa sequência para garantir a integridade e garantir que a comunicação não foi espionada.
O protocolo E91 foi criado por Artur Ekert em 1991. Ele possui uma diferença fundamental em relação aos outros dois: utiliza a propriedade do emaranhamento quântico para que dois fótons correlacionados sejam enviados para Alice e Bob.
O emaranhamento quântico é um fenômeno que desafiou alguns dos mais importantes físicos do século XX e ainda não existe uma teoria universalmente aceita que explique seu funcionamento completo. Para o âmbito da criptografia quântica, basta saber que é possível criar dois ou mais objetos que possuam propriedades correlacionadas, direta ou inversamente. No exemplo clássico, Alice e Bob usam um filtro retilíneo e seus resultados são sempre iguais para um par de fótons entrelaçado com correlação direta, ou diferentes para correlação inversa. Outra propriedade importante é que a medição de propriedades diferentes não garante correlação, ou seja, se Alice e Bob usarem filtros diferentes de polarização os resultados não serão necessariamente iguais ou opostos.
Dessa forma, o protocolo E91 é bastante simples: uma fonte externa produz um par de fótons entrelaçados, com correlação direta na polarização por exemplo, e envia um fóton para Alice e um para Bob. Cada um deles utiliza um filtro retilíneo ou um filtro diagonal, escolhido de forma aleatória, e mede a polarização do fóton. Após a transmissão, Alice e Bob comparam por um canal público suas escolhas de filtros e descartam as medições diferentes. O emaranhamento quântico garante que a sequência obtida pelos dois é idêntica, bastando apenas comparar parte dessa sequência ou utilizar esquemas de paridade para verificar a integridade contra ruídos ou contra tentativas de escuta. Novamente, a mecânica quântica faz com que qualquer tentativa de escuta modifique os resultados e crie diferenças que serão percebidas nesse estágio.