4  Criptografia Pós-Quântica

4.1  Novas Velhas Soluções

   (Topo)

Desde que se descobriu o potencial de criptoanálise do computador quântico, especialmente com o algoritmo de Shor, criou-se a idéia de que a criptografia moderna se tornaria inútil assim que esse tipo de computador começasse a ser desenvolvido em larga escala [4]. Logo, todas as mensagens trocadas com o uso de algoritmos criptográficos atuais seriam facilmente interceptáveis.

Em resposta a isso, surgiu a criptografia pós-quântica, ramo da criptografia que estuda classes de algoritmos criptográficos resistentes à criptoanálise quântica. Como exemplos de classes de algoritmos, podemos mencionar os baseados em hash, os baseados em látice, os baseados em códigos, entre outros. Estes algoritmos demorariam um tempo exponencial para serem quebrados, mesmo em computadores quânticos. [4]

No entanto, boa parte da comunidade científica expressa grande ceticismo com relação ao quão rapidamente se desenvolverão computadores quânticos comerciais. Afirmam que, por causa disso, não há grande utilidade em se preocupar com tal possibilidade. Apesar disso, a empresa D-Wave Systems alega ter desenvolvido, em 2011, um computador quântico comercial de 128 Q-bits, dedicado a algoritmos de otimização (portanto incapaz de executar o algoritmo de Shor) [42]; o que já é, no entanto, uma forte motivação para o desenvolvimento desse tipo de algoritmo.

4.2  Criptografia baseada em Hash

   (Topo)

A assinatura digital é de fundamental importância na realização de transações financeiras, entre outras operações. Porém, grande parte delas se baseia em algoritmos criptográficos vulneráveis à fatoração pelo algoritmo de Shor. Para solucionar esta deficiência, os algoritmos criptográficos baseados em função resumo (hash) se valem do fato de apenas poderem ser quebrados, de maneira determinísitca, com o uso de força-bruta, uma operação com custo O(n2), onde n é o número de bits empregados pela função.

A ideia de algoritmos criptográficos baseados em hash não é recente; os fundamentos existem desde final da década de 1970, início da de 1980 [7]. Existem duas grandes vertentes deste tipo de algoritmo: a autenticação de uso único e a autenticação em árvore. Dentre os exemplos mais conhecidos destas duas, estão o algoritmo de Lamport-Diffie e a árvore de Merkle.

4.2.1  Algoritmo Lamport-Diffie

   (Topo)

O algoritmo de Lamport-Diffie foi proposto em 1979 por Lesley Lamport, com a contribuição de Whitfield Diffie, que propôs um problema que serviu de ponto de partida para a criação do algoritmo [25]. Ele usa duas funções básicas: uma função não-inversível f : {0,1}n → {0,1}n e uma função de resumo g : {0,1}* → {0,1}n, onde n é a robustez desejada. O algoritmo utiliza, ainda, uma chave de assinatura A de 2n2 bits, uma chave de verificação B, também de 2n2 bits, que o usuário que deseja realizar a verificação de autenticidade possuía previamente, de mesmo tamanho, e assinaturas de n2 bits, diferentes a cada troca de mensagem.

O primeiro passo é a geração do par de chaves, que serão 2n-uplas de strings de n bits. No caso, A = (a0, a1,..., a2n−2, a2n−1) e B = (b0, b1,..., b2n−2, b2n−1), onde bi = f(ai) para todo i ∈ 0, 1, ... 2n−1. Após a criação das chaves, é feita a aplicação da função de resumo sobre a mensagem M, gerando uma n-upla de bits C = (c0, c1,..., cn−2, cn−1) = g(M). Cada um dos bits de C corresponderá a um tipo de flag, que indicará as posições de A a serem utilizadas para a formação da assinatura µi = aci + 2i, para 0 ≤ i < n.

Para realizar a autenticação, o usuário aplica a função f sobre µi e compara com B: se fi) = b[ci + 2i], para 0 ≤ i < n, então há a garantia de autenticação de mensagem; caso contrário, houve algum erro ou algum tipo de interceptação.

O grande problema do algoritmo acima é que novas chaves precisam ser geradas a cada mensagem trocada, pois se A fosse mantido, alguém poderia gerar várias mensagens para que fossem autenticadas, de forma a descobrir A. Por exemplo, se houver duas mensagens M1 e M2 tal que g(M1) = NOT g(M2), o valor de A será facilmente descoberto.

No início da descrição do algoritmo, supomos que o usuário que queria realizar a autenticação já estava de posse da chave B no começo do processo. Porém a mesma não pode ser passada pelo canal, pois pode ser interceptada por alguém mal-intencionado. A efeito de curiosidade, existem algumas maneiras de realizar esta tarefa, entre elas o envio de mensagem de texto por celular, ou mesmo o envio de carta, contendo a sequência das próximas chaves de verificação a serem utilizadas.

4.2.2  Árvore de Merkle

   (Topo)

Para tentar resolver o problema de uso único de cada par de chaves, Ralph Merkel propôs uma melhoria, onde é usada uma árvore cheia de altura h ≥ 2 [8]. Neste algoritmo, existem 2h−1 pares de chaves (Ak, Bk) do mesmo tipo que as do algoritmo anterior, correspondentes a cada uma das folhas da árvore. A cada folha k é atribuído o valor g(Bk). Aos outros nós é associado o valor g(filho esquerdo | filho direito). A raiz da árvore representa a chave pública, outra modificação em relação a Lamport-Diffie.

Quando um usuário quiser autenticar uma mensagem M, ele calcula d = g(M) e escolhe uma folha s qualquer da árvore. Em seguida, ele gera α, formado pelas posições de As ,determinadas pelo valor d. Por fim, ele computa Σ, a sequência dos “irmãos” dos nós que formam o caminho percorrido a partir da folha s, em ordem, para que se possa obter o valor da chave pública. Feitos estes passos, ele cria µ = α | Bs | s | Σ.


Figura 5: Ilustração da sequência necessária, em uma árvore de Merkle, para se chegar na chave primária no caso de uma árvore de altura 4, que teve s escolhido como sendo a terceira folha, da direita para a esquerda. O primeiro nó da sequência é o de cor azul; em seguida são adicionados os vermelhos em ordem crescente de altura. Se a verificação estiver correta, o resultado será igual ao valor do nó de cor amarela.

Ao receber a assinatura µ, o usuário aplica g(M) sobre a chave de verificação e compara o resultado com f(α). Se os valores forem iguais, ele parte para o segundo passo, que consiste em tentar chegar à chave pública. O algoritmo de verificação é descrito a seguir, com o uso de uma função H de hash qualquer:

função verifica_caminho(caminho Σ, chave_pública raiz, índice s) nó nó_atual = Σ[0]; para todos os nós i de 1 até tamanho(Σ)-1 se s mod2 = 0 então nó_atual := concatenação(nó_atual, Σ[i]); senão nó_atual := concatenação(Σ[i], nó_atual); nó_atual := H(nó_atual); s = s / 2; fim para; se nó_atual = raiz então retorna verdadeiro; senão retorna falso; fim função;

Este algoritmo não apresenta o mesmo problema do anterior, pois existem 2h−1 pares de chaves e, no pior dos casos, em 2h trocas de mensagens, é possível descobrir todos os valores das folhas da árvore e, ao mesmo tempo, os pares de chaves associados a cada uma delas. Se tivermos um valor de h grande, poderemos utilizar esta árvore por bastante tempo. Entretanto, o custo para armazenar uma árvore cheia é, também, exponencial no que diz respeito à altura. Como exemplo, um h = 25 permitiria a realização de assinatura digital 33,3 milhões de vezes aproximadamente com gasto de poucos Megaoctetos.

Para uma explicação mais completa dos algoritmos acima, consultar [4] [8].

4.3  Criptografia baseada em Código

   (Topo)

Criptografia baseada em código é aquela que usa facetas presentes em códigos corretores de erro para a criação de sistemas criptográficos. O mais famoso deles é o Sistema de McEliece, que implementa criptografia assimétrica, podendo ser usado para a realização de assinaturas [4]. Ele usa um código criptográfico corretor de erros conhecido como código de Goppa [28].

Um código criptográfico C(n, k) possui palavras de código de n bits para representar valores de k bits, ou seja, os nk bits restantes são usados para correção de erros. No caso, se d for a distância mínima de Hamming de C, então podem ser detectados até d/2 + 1 erros no código e corrigidos t = d/2. Podemos, ainda, definir uma matriz G: k × n geradora do código criptográfico C, tal que todas as suas linhas são linearmente independentes e que a combinação linear (correspondendo a sucessivas operações de XOR entre as linhas) delas gera as palavras de código de C, isto é, um símbolo γi de k bits é codificado em ci = γiGC(n, k), onde há 2k símbolos possíveis.

O Sistema de McEliece faz uso, ainda, de duas outras matrizes aleatórias: uma binária inversível S: k × k e uma de permutação P: n × n. Ele, então, calcula a matriz G’=SGP. Com isto, ele obtem a chave pública (G’, t) e a privada (P−1, G, S−1). A encriptação de uma mensagem M se dá através da divisão da mesma em blocos µi de k bits. Em seguida, ocorre a geração aleatória de um vetor υ de n bits, com t posições com o valor 1. Ele será usado para a geração de erros na mensagem encriptada que será passada. Finalmente, é calculada a mensagem encriptada χ = µi G’ + υ, que corresponderá ao bloco µi codificado com t erros aleatórios.

A decriptação é feita aplicando-se a chave privada, usando o fato de que AA−1=I para qualquer matriz binária inversível A. O primeiro passo é a geração de χ’ = χ P−1, produzindo um valor pertencente a C(n, k) a menos de um erro υ. Este, então, é corrigido e associado a um dos valores γ i. Por fim, ocorre a multiplicação pelo inverso de S, gerando a mensagem original: µ = γ i S−1.

Abaixo, apresentamos um exemplo da utlização do Sistema McEliece com o uso do código C(5, 2) = {00000, 10111, 11001, 01110}, com distância mínima de Hamming igual a 3, ou seja, capaz de corrigir até 1 erro. Este código possui o conjunto γ = {[0 0], [0 1], [1 0], [1 1]} e a seguinte base geradora:

G = 

10111
11001


As matrizes S, S−1, P, P−1 foram escolhidas aleatoriamente de forma que:

S = 

01
10


     S−1 = 

01
10


P = 





01000
10000
00010
00001
00100






     P−1 = 





01000
10000
00001
00100
00010






Com isto, teremos G′ = SGP:

G′ = 

01111
11100


Se nossa mensagem for igual a µ = 01 e o nosso erro aleatório υ = [0 0 1 0 0], então a mensagem criptografada enviada, χ = µ G′ + υ, será:

χ = 
11000

Ao receber a mensagem, o usuário aplica, primeiramente, o valor P−1 de sua chave primária, de forma a encontrar χ′ = χ P−1:

χ′ = 
11000

O usuário, então, compara χ′ com as palavras de código de C, descobrindo que o valor sem erros é, no caso, 11001. Ele resgata o valor γ3 = [1 0] ao qual a palavra de código está associada. Por fim, ele aplica S−1 sobre γ3, de forma a recuperar a mensagem original (µ = γ3 S−1):

µ = 
10



01
10



01

A vulnerabilidade desta técnica se encontra na descoberta do código Goppa G e das matrizes S e P a partir da chave pública e utilização de G para fazer a correção dos erros gerados, ou fazê-la utilizando apenas G’. No entanto, as duas opções são problemas para os quais não se conhece solução polinomial [14]. Atualmente, utiliza-se chaves bastante grandes para garantir que esta operação não seja realizada em tempo hábil, da ordem de 64 kB, valor bem maior do que o presente nas chaves RSA de hoje em dia, apesar de que o tempo de encripação e decriptação é um pouco mais rápido que o da RSA (para mais informações, ver gráficos comparativos em [18] [33].