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?
-
3Percebes alguma coisa de Mecânica Quântica?– Alexandre CartaxoCommented 27/12/2015 às 19:20
-
1Vê lá se percebes alguma coisa daqui: en.wikipedia.org/wiki/Quantum_key_distribution– Alexandre CartaxoCommented 27/12/2015 às 19:30
-
Já li isso meu problema é perceber como Bob entende a mensagem de Alice... Se ele não tiver a mesma base + ou x– PRVSCommented 27/12/2015 às 19:32
1 Resposta
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
ou1
). 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:
- Os bits incertos foram escolhidos para serem descartados. Então:
- Alice e Bob obtiveram o mesmo bit (50%); Eve se safou dessa...
- Alice e Bob obtiveram bits diferentes (50%); Agora eles sabem que alguém interferiu na comunicação, e o protocolo é abortado.
- Os bits incertos permaneceram na chave comum. Então:
- Alice, Bob e Eve têm o mesmo bit (25%); Eve possui a chave certa...
- 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.
- 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".