Criptografia Quântica

Gustavo Pfeiffer, Rodrigo Paim, Vinicius Motta

• Início
• Criptografia
  • O que é criptografia
  • Criptografia Simétrica
  • Criptografia Assimétrica
  • Função Resumo
• Computação Quântica
  • Fundamentos da Mecânica Quântica
  • Q-Bits e o Computador Quântico
  • Algoritmo de Shor e Critpoanálise
  • Presente e Futuro
• Criptografia Quântica
  • Quantum Key Distribution
  • "Cara ou Coroa" quântico
  • Transferência Inconsciente
  • Presente e Futuro
• Criptografia Pós-Quântica
  • Novas Velhas Soluções
  • Criptografia baseada em Hash
  • Criptografia baseada em Código
• Conclusão
• Perguntas
• Referências

1  Criptografia

1.1  O que é criptografia

   (Topo)

Criptografia (do grego kryptos "escondido”, “secreto"; e gráphin "escrita") [44] se refere à técnica de “esconder” a mensagem através de uma codificação. O objetivo desta técnica é criar um canal de comunicação confidencial de forma que terceiros não possam decodificar as informações enviadas.

Uma mensagem é encriptada através de um algoritmo que muda a codificação da mensagem, normalmente utilizando uma chave, de forma que o código gerado depende da chave. Um exemplo simples de criptografia em texto comum é alterar a codificação do alfabeto, através de uma tabela que relaciona as duas codificações. A chave deste algoritmo seria a tabela, isto é, arquivo que contenha a permutação de caracteres utilizada.

Já a palavra criptoanálise, refere-se à técnica de decifrar uma mensagem criptografada sem saber a chave. Isto normalmente implica em testar todas as chaves possíveis (conhecido na computação como método da “força bruta”), o que é extremamente custoso: atualmente, quebrar uma chave em tempo rápido requer a utilização de um número enorme de computadores em paralelo, muitas vezes custando mais do que o valor da informação a ser decifrada, ou levando um tempo maior do que a validade da informação [9].

Dentre os diversos tipos de criptografia digital estão a simétrica, a assimétrica e a função resumo, presentes em uma série de aplicações.

1.2  Criptografia Simétrica

   (Topo)

A técnica de criptografia simétrica se baseia em um mecanismo chamado de chave secreta para garantir a segurança da transmissão de mensagens entre dois computadores.

Nesta técnica, tanto o emissor quanto o receptor da mensagem compartilham uma chave secreta, que é usada na encriptação e decriptação do que é transmitido. Contudo, um dos problemas fundamentais está em como enviar a chave, já que há risco de interceptação. A encriptação e decodificação são feitas com o uso de artifícios combinatoriais, como rotações, permutações e outras operações lógicas em cima dos bits que compõem a mensagem, parametrizadas pela chave.

Estas operações são feitas de forma a tornar a criptoanálise extremamente custosa: em geral, tenta-se fazer com que a mensagem encriptada pareça o mais aleatória possível, sem padrões repetitivos e redundâncias, de forma que a única alternativa acaba sendo testar todas as chaves possíveis.

Há vários algoritmos de criptografia simétrica; dentre eles, os mais famosos são o AES, DES, IDEA e blowfish. Para informações adicionais, consultar [31], [12], [30], [38] e [37].

1.3  Criptografia Assimétrica

   (Topo)

A diferença fundamental entre a criptografia simétrica e a assimétrica é que, enquanto na primeira uma chave tem informação suficiente para permitir encriptar e decriptar mensagens, na segunda, estas duas operações requerem chaves distintas.

Neste modelo, cada pessoa possui uma chave privada (que chamaremos de D), que somente ela conhece, e uma chave pública (que chamaremos de E), que qualquer pessoa pode acessar. Esta chave normalmente fica armazenada em um “cartório” de chaves públicas, isto é, uma entidade capaz de garantir que aquela chave está associada a uma certa pessoa. Uma chave funciona como a inversa da outra, ou seja, K_D(K_E(M)) = K_E(K_D(M)) = M, onde K_x é a função criptográfica K associada à chave x. Na verdade, sabendo-se uma chave é possível chegar à outra, já que as duas são inversas; no entanto, a criptografia assimétrica é feita de forma que isto seja tão custoso quanto testar todas as possibilidades.

Os dois principais objetivos da criptografia assimétrica são:

1. Envio de mensagens confidenciais: Uma pessoa A pode utilizar a chave pública de B para enviar uma mensagem confidencial que somente B pode decodificar, com sua chave privada. Isto resolve o problema de enviar a chave na criptografia simétrica; agora basta utilizar a chave pública, que não é secreta.
2. Envio de mensagens autenticadas: B pode utilizar sua chave privada para encriptar uma mensagem de forma a garantir que ele a escreveu. Neste caso, o objetivo não é esconder a mensagem, e sim autenticá-la, uma vez que qualquer um pode decriptar a mesma com a chave pública de B.

No entanto, devido ao alto custo computacional de encriptar e decriptar mensagens na criptografia assimétrica, esta não costuma ser utilizada para comunicação direta, sendo geralmente utilizada apenas para criar um canal seguro de comunicação. Ou seja, envia-se uma chave simétrica encriptada por uma chave pública e o resto da comunicação é feito utilizando criptografia simétrica.

1.3.1  Algoritmo RSA

   (Topo)

O algoritmo RSA é o mais usado para a realização de criptografia assimétrica [32]. Ele foi nomeado a partir da primeira letra dos sobrenomes de seus inventores (Rivest, Shamir e Adleman).

O método usa uma função conhecida como Totiente (representada por ϕ), introduzida pelo matemático suíço Euler [1]. Esta função apresenta a propriedade de que, para dois números m e n primos entre si, m^ϕ(n) mod n = 1, onde x mod y deve ser entendido como o resto da divisão de x por y. Em particular, quando n é produto de dois números primos p e q, sabe-se que ϕ(n) = (p−1) . (q−1).

Primeiramente, um usuário gera um par de chaves (e, n), como chave pública, e (d, n), como chave privada, onde n = p . q (p e q são números primos muito grandes). Além disto, d é um número muito grande primo relativo a ϕ(n) e e é o inverso multiplicativo do primeiro, sendo, portanto, um número pequeno (e . d mod ϕ(n) = 1).

Por fim, uma mensagem M é encriptada em uma cifra C conforme a fórmula C = M^e mod n, enquanto a decriptação segue M = C^d mod n. Com isto, M = (M^e)^d mod n = M^ed mod n = M^{ed mod ϕ(n)} = M [39].

O ponto-chave para quebrar este algoritmo é a obtenção de ϕ(n), seja a partir de n, ou a partir de p e q após a fatoração de n; ambas as técnicas são extremamente custosas, tendo em vista que o melhor método conhecido para fatoração de inteiros possui complexidade O(ln(n)^{√ln(n)/ln(ln(n))}) [39], impossibilitando a fatoração de um número de 128 bits, por exemplo, em tempo hábil.

1.4  Função Resumo

   (Topo)

A função resumo (hash) foi criada com o intuito de “resumir” uma mensagem de tamanho qualquer em outra de tamanho fixo, normalmente menor que o da original. O hash gera uma saída de caráter pseudo-aleatório, de forma a ser resistente a pequenas mudanças na mensagem, e ser extremamente inviável gerar outra mensagem com o mesmo hash.

Uma das aplicações do hash, em segurança da informação, é a garantia do recebimento da mensagem sem qualquer alteração em relação ao que foi enviado (integridade). No entanto, como um terceiro pode alterar a mensagem e também o seu hash, normalmente utiliza-se o hash em conjunto com criptografia assimétrica.

Outra vantagem do hash é o fato de ser uma função não-inversível. Portanto, a tradução de um valor encriptado para o seu original gera não um valor, mas um conjunto com diversos possíveis geradores da mensagem encriptada. Isto torna impossível a recuperação de uma mensagem, pelo interceptador, utilizando apenas seu hash.

Atualmente, os algoritmos que implementam hash mais utilizados são o MD5 e o SHA-1 [20]. Para informações adicionais, consultar [36] e [29].