Aluno: Joelson Sousa de OliveiraOrientador: Clóvis Fortunato da Mata Souza
Teresina, dezembro de 2010
Estudo de Aplicações que Utilizam
Criptografia e Dados Quânticos
Sumário
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos2
1 Introdução
2 Referencial Teórico
2.1 O Modelo Criptográfico Clássico
2.2 Transição para o Modelo Quântico
2.3 Criptografia Quântica
2.4 Medidas Quânticas
2.5 Protocolos Quânticos
3 Metodologia
4 Resultados e Discussões
4.1 A Nova Ordem de Organização dos Dados
5 Conclusão
6 Referências Bibliográficas
1 Introdução
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos3
� Avanços em tecnologia da informação (TI) transientes à família de ondaseletromagnéticas chama-se informação quântica (do latim: quantum).
� Evolução:
� 1950: Passa-se a utilizar transistores, não tão menores que as válvulas de 1940.
� 1965: Circuitos integrados.
� Miniaturização: Próximo passo? Átomos e energia!
� Entrave:
◦ Comportamento atômico;
◦ Sistemas críticos de alto custo.
1 Introdução
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos4
� Surgimento de aplicações criptográficas com alto poder de identificação deintrusão e autodestruição da informação.
� Modelo de segurança voltado para a Distribuição Quântica de Chave(Quantum Key Distribuition - QKD):
� O Protocolo BB84, de Charles Bennett e Gilles Brassard (estudado no itemV).
2 Referencial Teórico
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos5
� O que é criptografia?
� Criptografia (do grego kryptós + gráphein = escrita oculta).
� Qual a sua importância?
� Prover mecanismos e técnicas que assegurem o sigilo de uma comunicação.
2.1 O Modelo Criptográfico
Clássico
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos6
� Pontos fundamentais segundo (FOROUZAN, 2006):
� Privacidade: existe confidencialidade (mecanismo garantidor que amensagem somente é inteligível para quem de fato é o destinatário original).
� Autenticação: a identidade é verificada sem possibilidade de falsificação.
� Integridade: os dados devem chegar exatamente como eles foram enviados,não ocorrendo mudanças durante a transmissão (acidentais ou maliciosas).
� Não Repúdio: capacidade de provar a origem dos dados recebidos, ao passoque não se poderá negar o seu envio.
2.1 O Modelo Criptográfico
Clássico
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos7
� Texto:
� Claro ou limpo;
� Cifrado ou criptograma, operações:
� Cifragem: ato de cifrar um texto limpo transformando-o em cifrado;
� Decifragem: cifrado => limpo.
� Cifra:
� Algoritmo criptográfico.
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos8
� Classificação:
� Chave simétrica, uma para cada par de entidades da comunicação.
� Devantagens segundo (FOROUZAN, 2006):
� A cada par de usuários deve estar associada uma única chave.
� Se N pessoas no mundo quiserem usar este método, serão necessárias N(N-1)/2 chavessimétricas.
2.1 O Modelo Criptográfico
Clássico
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos9
� O One Time Pad o único de inviolabilidade absoluta demonstrada em(SHANNON, 1949), guardando-se o fato de que cada chave seja usadasomente uma única vez.
� Devantagens do OneTime Pad:
� Acepção inicial abrupta (chaves geradas são unívocas);
� O tamanho da chave é proporcional ao comprimento da mensagem;
� A problemática de distribuição de chaves, que reside em se armazenar chavescom segurança.
2.1 O Modelo Criptográfico
Clássico
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos10
� Entidades da comunicação:
Figura 1. Alice se comunica com Bob, enquanto Eve t enta se apoderar da informação.
Fonte: <http://kaioa.com/node/49>
2.1 O Modelo Criptográfico
Clássico
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos11
� Chave pública, uma chave privada guardada pelo receptor e outra, defato, pública.
� Características:
� Abstração do envolvimento das entidades como responsáveis absolutas pelasegurança geral do sistema de comunicação objetivado.
� A criptografia de chave pública é ideal para o estabelecimento de uma sessãode comunicação e jamais para criptografar mensagens longas.
� Como DH (DIFFIE; HELLMAN, 1976); RSA (Ron Rivest, Adi Shamir eLeonard Adleman).
2.1 O Modelo Criptográfico
Clássico
2.2 Transição para o Modelo
Quântico
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos12
� Por que usar o modelo quântico?
� A criptografia de chave pública provê chaves inquebráveis dentro do contextológico de computação clássica.
� Embora seja necessária uma estrutura complexa (supercomputadores ouclusters) atuando para quebrar o sigilo da comunicação, não é possível garantirtotalmente a segurança dos sistemas de informação.
� Motivação:
� Atingir um nível de segurança total em sistemas de informação,independentemente do poder computacional de um agente malicioso.
2.2 Transição para o Modelo
Quântico
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos13
Tabela 1. Analogia do tempo de fatoração entre um a lgoritmo clássico e o algoritmo de Shor
Fonte: <http://www.gta.ufrj.br/grad/10_1/quantica/quantica.html>
2.3 Criptografia Quântica
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos14
� Em 1969, (WIESNER, 1970) propôs:
� Produção de notas de dinheiro imunes à falsificação (dinheiro quântico);
� Resultado:
� Um método para combinação de duas mensagens em uma numa transmissãoquântica e, assim, o receptor poderia escolher entre elas, mas não as duassimultaneamente:
� A partir da leitura de uma mensagem, automaticamente destruiria aoutra.
2.3 Criptografia Quântica
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos15
� Charles Bennet e Gilles Brassard, 1984:
� Uso de fótons para transmitir informações codificadas.
� Criaram o primeiro protocolo quântico conhecido por BB84.
� “Experimental Quantum Criptography” (BENNET, 1991) sintetizou o BB84dando origem ao protocolo B92.
2.4 Medidas Quânticas
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos16
� Computação quântica:
� Unidade básica: qubit (quantum bit).
� Portas e circuitos quânticos.
� Informação quântica:
� Fótons (propriedades quânticas superposição e relatividade), quantos estadostem um qubit?
2.4 Medidas Quânticas
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos17
� Os qubits são representados por vetores dentro de um espaço de estados compropriedades definidas: .
� Representação para um qubit:
Figura 2. Representação de um qubit na esfera de Bloch
Fonte: (NIELSEN; CHUANG, 2000)
2.4 Medidas Quânticas
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos18
Tabela 2. Comparação entre as medidas de rotação de partículas emaranhadas no mesmo eixo e na direção perpendicular
Fonte: (WIKIPEDIA 2010)
mesmo eixo: 1 par par 2 par 3 par 4 ... Par n
Alice, 0 °: + - - + ...
Bob, 0 °: + - - + ...
Correlação:( +1 +1 +1 +1 ... ) / N = 1
Conclusão (100% idênticas)
Eixos
ortogonais:1 par par 2 par 3 par 4 ... Par n
Alice, 0 °: + - + - ...
Bob, 90 °: - - + + ...
Correlação:( -1 +1 +1 -1 ... ) / N = 0
Conclusão (50% idênticos)
2.4 Medidas Quânticas
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos19
Figura 3. Portas clássicas e a porta quântica controlled-NOT para múltiplos qubits
Fonte: (NIELSEN; CHUANG, 2000)
2.5 Protocolos Quânticos
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos20
� A Distribuição Quântica de Chaves (QKD):
� Transmissão de estados de qubit não ortogonais entreAlice e Bob.
� Ao verificar a perturbação em seus estados transmitidos estabelece-se um limitesuperior aceitável em qualquer ruído ou espionagem ocorrida no canal decomunicação.
� Qubits check são intercalados aleatoriamente entre os qubits de dados, de extraçãoda chave.
2.5 Protocolos Quânticos
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos21
� O protocolo BB84, segundo (NIELSEN; CHUANG, 2000):
� Alice escolhe bits de dados aleatórios.
� Alice escolhe um aleatório -bit da sequência b. Ela codifica cada bit de dados como{|0), |1)}, se o bit correspondente de b é 0, ou {|+), |-)}, se b é 1.
� Alice envia o estado resultante de Bob.
� Bob recebe os qubits, anuncia este fato, e mede cadaqubit na base X ou Z ao acaso.
� Alice anuncia b.
2.5 Protocolos Quânticos
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos22
� Alice e Bob descartam quaisquer bits onde Bob obteve uma medidadiferente. Com alta probabilidade, há pelo menos 2n bits à esquerda (docontrário, abortam o protocolo). Mantêm-se 2n bits.
� Alice escolhe um subconjunto de n bits que vai servir como uma verificaçãosobre a interferência de Eve e diz a Bob quais bits ela selecionou.
� Alice e Bob anunciam e comparam os valores dos bits de verificação n. Se maisde um número aceitável discordam, abortam o protocolo.
� Alice e Bob realizam a reconciliação da informação e amplificação daprivacidade dos n bits restantes para obter m bits de chave compartilhada.
2.5 Protocolos Quânticos
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos23
� O protocolo B92:
� Dependendo do bit aleatório a’que ele gera, Bob mede o qubit que recebe de Aliceem cada base Z {|0), |1)} (se a’= 0), ou na base X { } (se a’= 1).
� Obtém o resultado b, que é 0 ou 1, correspondente à -1 e +1, estados de X e Z.
� Bob anuncia publicamente b (com a’ em segredo), e Alice e Bob realizamuma discussão pública mantendo apenas os pares {a, a’} para o qual b = 1.
� Observe que quando a = a’, então b = 0 sempre.
� Só se a’= 1 - a, Bob obterá b = 1, e que ocorre com probabilidade de 50%.
� A chave final é a para Alice, e 1 – a’para Bob.
2.5 Protocolos Quânticos
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos24
� O protocolo EPR:
� As entidades são vistas como parte de um conjunto de n pares emaranhados de qubits:pares EPR.
� Podem ser gerados por Alice ou Bob, ou até por uma terceira entidade.
� Metade dos qubits são remetidos para cada entidade que selecionam um subconjunto etestam de acordo com a desigualdade de Bell.
� Medidos em determinadas bases conjuntamente aleatórias, os dados correlacionadosconstituem os bits de chave secreta, como no B92 e BB84.
3 Metodologia
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos25
Figura 4. Virtual Box executando o Windows XP sobre o sistema operacional Windows 7
4 Resultados e Discussões
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos26
� Apresentação de um aplicativo do tipo jogo que gera estados superpostos.
� Existem três grandezas na natureza: comprimento, largura e altura.
� Einstein, por meio de sua Teoria da Relatividade, propôs considerar o tempo como uma quarta coordenada a fim de identificar eventos de maneira unívoca a qual chamou de espaço-tempo.
4.1 A Nova Ordem de Organização
dos Dados
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos27
� Espaço-tempo:
� Agrega todos os elementos do Universo, em equilíbrio.
� CoordenadasAdjacentes.
Figura 5. Representação da curvatura do espaço-tempo
Fonte: : <http://aventurasdafisica.blogs.sapo.pt/2303.html>
4.1 A Nova Ordem de Organização
dos Dados
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos28
� Organização de dados em matrizes:
� Sistema de computação fictício fundado na natureza da estrutura de dadosempregada, em vez da natureza de partículas elementares do modelo quântico.
� A partir do número de linhas e colunas da matriz, gera-se dois coeficientesrepresentativos do sistema de coordenadas, um para cada eixo:
� É possível interligar toda a informação dentro da estrutura da matriz.
4.1 A Nova Ordem de Organização
dos Dados
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos29
� A ideia utilizada aqui, assemelha-se à daTeoria da Relatividade:
� Para cada par de coordenadas escolhido existirá uma curva (em vez de espaço-tempo, considere linha-coluna da matriz) a partir da qual são gerados estadosrelativos.
� Introduz-se o valor da linha-coluna para “sustentar” uma iminente mudança deestado em outro ponto que se tomou por base.
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos30
� A fundamentação quântica vira a prática realizada no jogo Tetrisminós (dogrego, tetra é quatro e minós é quadrado):
Figura 6. Interface de entrada de valores (x,y)
4.1 A Nova Ordem de Organização
dos Dados
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos31
Case aux_r[i,j].tab[y,7-x] of[…]7: begin
if (arena_pec[((x+contx)-3),y+conty]=0) and ((x+contx)-3>=0)and ((y+conty)>=0) and ((x+contx)-3<=7) and ((y+conty)<=7) then
pec[i,j].tab[((x+contx)-3),y+conty]:=7
elsebegin
log_pec:=true;outtextxy(64, 100, 'Jogada
Improcedente!');readkey;break;
end;end;
end;
case aux_r[i,j].tab[x,7-y] of {Constantes: contx:=x+y-4; conty:=y-x;}
[…]
Figura 7. Procedure Relatividade (em Pascal)
4.1 A Nova Ordem de Organização
dos Dados
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos32
Figura 8. Estados relativos da peça combat
4.1 A Nova Ordem de Organização
dos Dados
5 Conclusão
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos33
� Banco de Dados:
� Capacidade de armazenar informações relativas, transferindo-se capacidade deprocessamento para armazenamento.
� Redes:
� Possibilidade de transferir grande carga de informação a ser processada namáquina cliente.
� Criar uma organização capaz de representar toda a informação: ASCII,Unicode, etc.
� Segurança deTI:
� Dificuldade em inteligir as bases relativísticas de geração dos dados e o nível deentrelaçamento.
6 Referências Bibliográficas
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos34
BENNETT, C.; BRASSARD, G. Quantum cryptography: Public key distributionand coin tossing. IEEE InternationalConference on Computers, Systems and Signal Processing, v. 1, p. 175–179, 1984.
BENNETT, C. H.Quantum cryptograhy using any two nonorthogonal states. Phys.Rev. Lett., v. 68, p. 3121–3124, 1992.
BENNETT, C. H. et al. Experimental quantum cryptography. Lecture Notes in Computer Science, v. 473, p. 253, 1991.
BENNETT, C. H. et al. Generalized privacy amplification. IEEETrans InformationTheory, v. 41, p. 1915–1923, 1995.
BENNETT, C. H.; BRASSARD, G.; ROBERT, J.-M. Privacy amplification by public discussion. SIAM J. Comput., Society forIndustrial andApplied Mathematics, Philadelphia, PA, USA, v. 17, n. 2, p. 210–229, 1988. ISSN 0097-5397.
BRASSARD, G.; SALVAIL, L. Key reconciliation by public discussion. Lecture Notes in Computer Science, v. 765, p. 410–423,1994.
CACHIN, C.; MAURER, U. Linking Information Reconciliation and
Privacy Amplification. Outubro, 1935.
6 Referências Bibliográficas
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos35
COHEN-TANNOUDJI, C.; DUI, B.; LALOE, F. Quantum Mechanics. [S.l.]: JohnWiley & Sons, 1978.
DEUTSCH, D. Quantum theory, the church–turing principle and the universal quantum computer. Proc. R. Soc.,London, v. 400, p. 97–117, 1985.
W. DIFFIE and M. HELLMAN. New directions in cryptography. IEEETrans. Inf.Theory, lT-22i6y.644~54, 1976.
DIRAC, P. The Principles of Quantum Mechanics. 4a. ed. Oxford: Oxford University Press, 1958.
EINSTEIN, A.; PODOLSKY, B.; ROSEN, N. Can Quantum Mechanical Description of Physical Reality Be ConsideredComplete ?. Março, 1935. Publicado Originalmente em: Physical Review,May 15, 1935,V.47, p. 777-780.
EKERT,A. Quantum Criptography Based on Bell’sTheorem. Physical Review Letters, vol. 67, n. 06, 1991, p. 661-663.
FOROUZAN, B.A. Comunicação de Dados e Redes de Computadores. 3a ed., Porto Alegre: Bookman,. 2006, p. 689-748.
GUALTER et al. Tópicos de Física, 3 : eletricidade, física moderna. 15a ed. reform. e ampl. São Paulo: Saraiva, 2001.
6 Referências Bibliográficas
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos36
HERBERT, N. A Realidade Quântica. 1a. ed. Rio de Janeiro: Francisco Alves Editora, 1985.
MARTINS,A. O que é computador?. Coleção primeiros passos n. 247 2a. ed. São Paulo: Brasiliense, 2007, p. 80-88.
MOORE, S. K. Prototype of a commercial quantum computer demonstrated. IEEE Spectrum, 2007.
NIELSEN, M. A.; CHUANG, I. L. Quantum computation and Quantum Information. Cambridge, Massachusetts: CambridgeUniversity Press, 2000.
NOBUO, DANIEL; CÂNDIDO, ANTÔNIO. Pricípios de Criptografia Quântica. Instituto Tecnológico de Aeronáutica, São José dosCampos – SP. Disponível em: <http://www.bibl.ita.br/ixencita/artigos/FundDanielNobuo.pdf>.Acesso em: 1 dez. 2010.
SHANNON, C.Communication theory of secrecy systems.The Bell System Technical Journal, v. 28, n. 4, p. 656–715, 1949.
SHOR, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.SIAM J.Sci.Statist. Comput., v. 26, p. 1484, 1997.
SLUTSKY, B.; RAO, R.; SUN, P.; TANCEVSKI, L.; FAINMAN, S. Defense Frontier Analysis of Quantum CryptographicSystems. Maio, 1998.
6 Referências Bibliográficas
28/12/2010Estudo de Aplicações que Utilizam Criptografia e Dados Quânticos37
STIX, GARY. Os Segredos Mais Bem Guardados. Scientific American
Brasil, n. 33, fev. 2005, p. 39-45.
WIESNER, S.Conjugate Coding. Sigact News, vol. 15, n. 1, 1983, p. 78-88. Manuscrito original datado de 1970.
WWW.
� D-WAVE. <http://www.dwavesys.com>, cosulta em 25 de novembro, 2009.
� ID QUANTIQUE. <http://www.idquantique.com>, consulta em 25 de novembro, 2009.
� WIKIPEDIA. <http://en.wikipedia.org/wiki/Bell's_theorem>, consulta em 07 de dezembro, 2010.