2

Estou a estudar uma matéria de criptografia quântica e não estou a entender o funcionamento do protocolo de Bennett & Brassard, parece-me tudo aleatório e sem sentido... Mesmo lendo outras coisas na Internet ainda não consegui entender como é que uma pessoa adivinha 50% etc... Alguém me pode explicar como funciona este protocolo?

3

1 Resposta 1

4

Em primeiro lugar, esse protocolo assume duas coisas:

  • Um canal quântico, capaz de enviar qubits (por exemplo, fótons polarizados enviados por um cabo de fibra ótica) cujo estado carrega uma informação (por exemplo, um bit clássico, 0 ou 1). Esse canal é público (ou seja, não é seguro), de modo que pode ser interceptado seja passivamente (eavesdropping) ou ativamente (tampering).
  • Um segundo canal, clássico, em que um participante possa enviar mensagens (bits) pro outro. Por exemplo, uma transmissão de rádio ou a própria Internet. Da mesma forma, esse canal é público (não seguro).
    • Nota: posso estar enganado, mas pelo meu entendimento esse protocolo sofre do mesmo problema do protocolo Diffie-Hellman, ou seja, não previne MitM por si só (i.e. ele não autentica Alice com Bob e vice-versa). De modo que na minha opinião ele seria mais seguro usando um canal mais resistente a ataques ativos (ex.: transmissão de rádio) do que um mais vulnerável (ex.: internet, ou qualquer outro canal que possa sofrer tampering).

Pra começar, Alice gera uma sequência aleatória de bits, algumas vezes maior que o tamanho de chave que ela quer negociar. Não sei dizer o número exato, mas vamos assumir que eles queiram uma chave de 256 bits para usar com o AES, e Alice começou com uma sequência 4 vezes maior - 1024 bits. (se a ideia for usar um One-Time Pad, então a chave teria de ser tão grande ou maior que a mensagem a ser enviada).

Alice                     Eve                       Bob
k=0010101101110101

Para codificar esses bits em qubits, Alice escolhe aleatoriamente entre duas bases, por exemplo uma retilínea (ex.: 0° para 0 e 90° para 1) e uma diagonal (ex.: 45° para 0 e 135° para 1). Se a base retilínea foi escolhida e o bit a ser enviado for 0, o qubit resultante será . Se a base diagonal foi escolhida e o bit a ser enviado for 0, o qubit resultante será . Idem pra retilínea e 1 () e diagonal e 1 (). A sequência de qubits é então enviada a Bob.

Alice                     Eve                       Bob
k=0010 1011  0111 0101
a=+xx+ xx+x  xx++ x++x
q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖

Note que, embora tanto Eve quanto Bob tenham recebido os qubits, eles ainda não sabem qual é seu valor - ou mesmo em que base estão - pois eles ainda não os mediram. Note também que Eve não pode fazer uma "cópia" desses qubits (pelo teorema da "não clonagem") para medi-los mais tarde - ou ela faz uma mensuração no momento em que os qubits passaram por ela, ou ela perde a chance de obter qualquer informação sobre eles.

Se Eve não interferiu...

Bob recebeu os qubits, mas ele não sabe em que bases estão codificados. Então ele tenta "adivinhar" a base, acertando em média 50% das vezes:

Alice                     Eve                       Bob
k=0010 1011  0111 0101                              k= ?0?0 1??? 01?1 ??0?
a=+xx+ xx+x  xx++ x++x                              b= xx++ x+x+ xxx+ +x++
q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=???? ???? ???? ????     q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖

Sempre que Bob acerta a base, ele obtém o mesmo bit que Alice conhece. Já quando ele erra, ele pode obter o mesmo bit ou o bit oposto, com 50% de probabilidade de ocorrer um ou outro cenário. Por exemplo, o primeiro lido quando medido numa base x pode virar um (0) ou um (1). No exemplo acima, das 16 bases originais Bob acertou 7 e errou 9. Se fossem 1024 bits, Bob acertaria por volta de 512.

(note que os bits que Bob obteve corretamente podem ser mais que 7, pois sempre que tem um ? ele pode tanto ter acertado quanto errado; mas isso não importa, pois eles nunca poderão ter certeza se os bits estão ou não certos, de modo que eles não são mais úteis pro protocolo)

Alice e Bob então revelam um ao outro quais as bases escolhidas, e comparam as duas sequências para saber quais qubits foram interpretados com sucesso e quais viraram "lixo". O fato dessa informação ser revelada agora não ajuda Eve em nada, pois os qubits já eram e não há mais como medi-los (e relembrando: não há como fazer cópias deles pra uso futuro).

Alice                     Eve                       Bob
k=-0-0 1---  01-1 --0-                              k= -0-0 1--- 01-1 --0-
a=+xx+ xx+x  xx++ x++x    a=+xx+ xx+x xx++ x++x     a= +xx+ xx+x  xx++ x++x
b= xx++ x+x+ xxx+ +x++    b=xx++ x+x+ xxx+ +x++     b= xx++ x+x+ xxx+ +x++

Por fim Alice escolhe aleatoriamente alguns bits pra "jogar fora". Isso é importante pra ajudar a detectar se houve alguma interceptação, mas vou deixar a explicação para adiante. Por ora, saiba apenas que os bits revelados não fazem mais parte da chave comum.

Alice                     Eve                       Bob
k=-0-- 1---  -1-- --0-    k=???0 ???? 0??1 ????     k= -0-- 1--- -1-- --0-

A chave final - 0110 - é conhecida por ambos Alice e Bob mas desconhecida por Eve (que só conhece os bits que foram jogados fora e não servem mais pra nada). Dos 7 bits que Bob acertou, 4 foram usados, 1/4 da quantidade inicial de 16. Se fossem 1024, a chave final teria os 256 bits desejados.

Se Eve tentou interferir...

Digamos no entanto que Eve não simplesmente "deixou passar" os qubits, que ela tentou adivinhar uma base e então medi-los assim como Bob teve que fazer. Da mesma forma que Bob, ela tem 50% de chance de acertar cada base. O problema é que ao mensurar ela faz com que o qubit assuma a base com a qual ela mensurou. Ou seja:

  • Se ela acertar (50%), o qubit vai embora inalterado*, e Bob obterá o mesmo bit quando fizer a medição**;
  • Se ela errar (50%), o qubit assumirá uma das duas formas da base oposta, de modo que quando Bob mensurar ele tem 50% de chance de obter o valor errado ainda que use a mesma base escolhida por Alice!

(* "inalterado" no sentido que uma mensuração na base correta tem pouca chance de introduzir um erro que faça com que Bob obtenha um resultado diferente do que obteria se a mensuração não tivesse sido feita; ** desde é claro que ele também esteja medindo na base certa)

No fim das contas, para cada qubit há 25% de chance das ações de Eve introduzirem um erro no resultado de Bob, sendo que esse erro será significativo em todo caso que Alice e Bob escolheram a mesma base (i.e. no total, 12.5% dos bits comuns serão diferentes para Alice e Bob).

Alice                     Eve                       Bob
k=0010 1011  0111 0101    k= 0010 1??? 0??1 ??01    k= ?0?0 1??? 0??1 ??0?
a=+xx+ xx+x  xx++ x++x    e= +xx+ x+x+ x+x+ +x+x    b= xx++ x+x+ xxx+ +x++
q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=→↗↖→ ↖??? ↗??↑ ??→↖

No exemplo acima Eve errou 5 vezes, de modo que 5 qubits chegaram a Bob num estado indeterminado (igual ou diferente do seu estado original). Agora veja o que acontece quando Alice revela suas bases e ela e Bob tentam determinar quais bits foram transmitidos com sucesso:

Alice                     Eve                       Bob
k=-0-0 1---  01-1 --0-    k= -0-0 1--- 0?-1 --0-    k= -0-0 1--- 0?-1 --0-
a=+xx+ xx+x  xx++ x++x    e= +xx+ x+x+ x+x+ +x+x    b= xx++ x+x+ xxx+ +x++

Alice e Bob acreditam que têm os mesmos bits. Mas alguns deles (no exemplo acima, só um) não são garantidamente comuns, pois Bob pode ou não ter derivado o bit certo. E de todo modo, Eve sabe que aquele bit faz parte da chave comum, mas ela também não tem certeza se está ou não com o resultado certo - pois Alice e Bob escolheram a mesma base, enquanto Eve escolheu a base errada. Nesse ponto, as seguintes coisas podem acontecer:

  1. Os bits incertos foram escolhidos para serem descartados. Então:
    1. Alice e Bob obtiveram o mesmo bit (50%); Eve se safou dessa...
    2. Alice e Bob obtiveram bits diferentes (50%); Agora eles sabem que alguém interferiu na comunicação, e o protocolo é abortado.
  2. Os bits incertos permaneceram na chave comum. Então:
    1. Alice, Bob e Eve têm o mesmo bit (25%); Eve possui a chave certa...
    2. Alice e Bob têm o mesmo bit, mas Eve não (25%); Eve possui a chave errada, e não pode ler a comunicação posteriormente criptografada.
    3. Alice e Bob têm bits diferentes (50%); quando no futuro um tentar mandar uma mensagem cifrada pro outro, este não poderá ler, e saberão que alguém interferiu na comunicação (apesar do protocolo ter concluído com sucesso).

No exemplo acima, o bit entrou pra chave definitiva (cenário 2), de modo que o protocolo concluiu com sucesso apesar da interferência de Eve. Ainda assim, há 25% de chance de Eve ter um bit errado (o que exigiria dela esforço extra pra crackear a chave) e 50% de Bob ter um bit errado (o que lhe permitiria descobrir que a comunicação foi interceptada, ainda que a posteriori).

Alice                     Eve                       Bob
k=-0-- 1---  -1-- --0-    k= -0-- 1--- -?-- --0-    k= -0-- 1--- -?-- --0-

Possibilidades:
Alice Eve  Bob   Resultado
0110  0100 0100  Eve e Bob têm a chave errada
0110  0100 0110  Eve tem a chave errada
0110  0110 0100  Bob tem a chave errada
0110  0110 0110  Eve e Bob têm a chave certa

Esses cenários citados (dentre os quais uns beneficiam Eve e outros beneficiam Alice e Bob) valem pra cada bit incerto. Ou seja, quanto mais bits tiver a chave, maior o número de bits que potencialmente apresentarão problemas (1 no exemplo acima que começou com 16, sendo 2 o valor teórico esperado; numa que começasse com 1024, esperaria-se 128 bits problemáticos).

Da mesma forma, quanto mais bits forem escolhidos para "jogar fora", maior a chance de detectar uma discrepância a priori e encerrar o protocolo com fracasso - um cenário preferível a concluí-lo e deixar Eve com um conhecimento parcial da chave compartilhada.

Bits jogados fora   Chance de algum ser problemático   Chance do problema passar despercebido
  1                 12.5%                              87.5%
  2                 23.4%                              76.6%
  3                 33.0%                              67.0%
  4                 41.4%                              58.6%
  5                 48.7%                              51.3%
 10                 73.7%                              26.3%
 20                 93.1%                               6.9%
 50                 99.9%                               0.1%
256                 99.99999999999986%                  1.4e-13%

Nota: essa resposta assumiu para simplificar que o canal quântico é livre de erros, e que qualquer discrepância se deve a uma tentativa de interceptação. Na prática, podem ocorrer erros de transmissão e detecção que fariam que Alice e Bob terminassem com chaves parecidas porém distintas, mesmo na ausência de Eve. Uma fase final seria então necessária, a "amplificação de privacidade e reconciliação da informação".

1
  • Muito esclarecedor. Entendi. Muito obrigado.
    – PRVS
    Commented 29/12/2015 às 9:00

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .