Atividade 18: Cara ou coroa – Protocolos de segurança

Apresentação

Esta atividade mostra como executar uma tarefa simples, mas aparentemente impossível: fazer uma escolha aleatória justa, através do Cara ou Coroa, entre duas pessoas que não necessariamente confiam uma na outra e que estão conectadas somente através de um telefone.

Disciplinas e conteúdos relacionados

Habilidades

Nível de Ensino

Material

Cada grupo de alunos vai precisar de:

Cara ou Coroa

Introdução

Você pode personalizar a história para se adequar ao contexto local do lugar no qual se encontra.

Os times de futebol de Porto Alegre, Grêmio e Internacional, têm que decidir quem vai ser o time da casa e terá seu estádio como o principal local para os jogos do campeonato estadual. A maneira mais simples para tomar essa decisão é fazê-la através do jogo de sorte Cara ou Coroa.

O problema é que os estádios ficam em lados opostos da cidade e Renato, representante do Grêmio, e Fernando, representante do Internacional, não podem se reunir pessoalmente para fazer o Cara ou Coroa. Será que eles conseguiriam fazer isso através do telefone?

Renato poderia atirar a moeda para cima e Fernando poderia perguntar se deu Cara ou Coroa. Mas isso não funcionaria, pois Renato pode simplesmente mentir e atribuir o melhor resultado a seu favor. Renato não é trapaceiro, mas o campeonato estadual é um evento muito importante e a tentação de trapacear é muito forte. O problema aqui, então, é: mesmo que Renato seja honesto a respeito do resultado, será que Fernando acreditaria na palavra dele caso o resultado fosse desfavorável a ele?

Essa atividade é mais proveitosa se os alunos já tiverem aprendido alguns conceitos e habilidades que foram abordados em outras atividades desta coleção: números binários, o conceito de paridade e função de mão única.

Isto é o que eles decidem fazer: trabalhando juntos, eles projetam um circuito composto por portas lógicas E e OU, como ilustrado abaixo. A princípio, eles podem fazer isso por telefone, embora reconheçam que, na prática, essa tarefa possa se tornar tediosa. Essa tarefa funcionaria por e-mail também. Durante o processo de construção do circuito, cada um dos participantes tem interesse em garantir que ele seja suficientemente complexo para que o outro seja incapaz de trapacear. O circuito final é de conhecimento público.

Discussão

As regras das portas lógicas E e OU são simples. Cada uma tem duas entradas e uma saída. Cada uma das entradas pode ser um 0 ou um 1, que podem ser interpretados, respectivamente, como falso e verdadeiro. A saída de uma porta E é 1 (verdadeiro) somente se ambas as entradas forem 1 (verdadeiro) e 0 (falso) caso contrário. Por exemplo, a porta E tem um 1 e um 0 em suas entradas (no topo), então a saída (o quadrado na parte inferior) é um 0 (falso). A saída de uma porta OU é 1 (verdadeiro) se uma ou ambas as entradas forem 1 (verdadeiro), e 0 (falso) somente se ambas as entradas forem 0 (falso). Desse modo, a saída da porta OU é 1 para as entradas 0 e 1.

A saída de uma porta pode ser conectada à entrada de outra (ou várias outras) para criar um circuito ainda mais complicado. Por exemplo, no lado esquerdo do circuito, as saídas de duas portas OU são conectadas as duas entradas de uma terceira porta OU. O efeito criado por essas conexões é o de que se qualquer uma dessas quatro entradas for um 1, então a saída também será um 1 (verdadeiro). No lado direito do circuito, as saídas de cada uma das portas E superiores alimenta duas portas inferiores, de modo que todo o circuito tem dois valores nas saídas.

Para o Cara ou Coroa, precisamos de circuitos ainda mais complexos. O circuito da planilha tem seis entradas e seis saídas. Aqui está um exemplo trabalhado para um conjunto particular de valores de entrada.

Esse circuito pode ser utilizado para fazer Cara ou Coroa da seguinte forma:

Renato seleciona uma entrada aleatória do circuito, que consiste em seis dígitos binários (0s ou 1s), e a mantém em segredo. Ele, então, coloca os seis dígitos através do circuito e envia a Fernando os respectivos bits de saída. Uma vez que Fernando tenha esses bits de saída, ele deve tentar adivinhar se a entrada de Renato tem uma quantidade par ou ímpar de números 1 na entrada.

Ou seja, ele deve adivinhar a paridade da contribuição de Renato. Se o circuito for suficientemente complexo, então Fernando não será capaz de encontrar a resposta, e seu palpite terá que ser uma escolha aleatória (na verdade, ele poderia até fazer Cara ou Coroa para obter essa escolha!). Fernando vence - e o time da casa será o Internacional - se seu palpite estiver correto; Renato vence - e o time da casa será o Grêmio - se Fernando adivinhar incorretamente. Assim que Fernando contar a Renato seu palpite, Renato revela sua entrada para que Fernando possa confirmar que esta produz a saída que foi afirmada.

  1. Divida os alunos em pequenos grupos, dê a cada grupo o circuito e alguns botões e explique a história. A história terá mais impacto nos alunos se eles imaginarem os próprios times locais e seus respectivos capitães. Estabeleça uma convenção para as cores dos botões. Se metade for azul e a outra vermelha, então atribua o vermelho ao O (falso) e o azul ao 1 (verdadeiro) ou vice-versa. Peça aos alunos que marquem na legenda, no topo da folha de atividade, para ajudá-los a lembrar da convenção.

  2. Mostre aos alunos como colocar os botões nas entradas para mostrar os dígitos que Renato escolheu. Em seguida, explique as regras das portas E e OU, que estão resumidas no final da folha (peça para os alunos colori-las).

  3. Mostre para os alunos como trabalhar através do circuito, colocando os botões em cada uma das portas para derivar a saída correspondente. A tabela, que não deve ser dada aos alunos, mostra a saída para cada entrada possível (use para referência própria), em caso de dúvida.

Tabela de Entradas e Saídas
Entrada 000000 000001 000010 000011 000100 000101 000110 000111
Saída 000000 010010 000000 010010 010010 010010 010010 010010
Entrada 001000 001001 001010 001011 001100 001101 001110 001111
Saída 001010 011010 001010 011010 011010 011010 011010 011111
Entrada 010000 010001 010010 010011 010100 010101 010110 010111
Saída 001000 011010 001010 011010 011010 011010 011010 011111
Entrada 011000 011001 011010 011011 011100 011101 011110 011111
Saída 001010 011010 001010 011010 011010 011010 011010 011111
Entrada 100000 100001 100010 100011 100100 100101 100110 100111
Saída 000000 010010 011000 011010 010010 010010 011010 011010
Entrada 101000 101001 101010 101011 101100 101101 101110 101111
Saída 001010 011010 011010 011010 011010 011010 011010 011111
Entrada 110000 110001 110010 110011 110100 110101 110110 110111
Saída 001000 011010 011010 011010 011010 111010 011010 111111
Entrada 111000 111001 111010 111011 111100 111101 111110 111111
Saída 001010 011010 011010 011010 011010 111010 011010 111111
  1. Agora, cada grupo deve eleger um Renato e um Fernando. O grupo pode se dividir e cada um escolher um lado (time do Renato ou do Fernando). Renato deve escolher uma entrada aleatória para o circuito, calcular a saída e, então, contar para Fernando. Fernando deve descobrir a paridade da entrada (seja ela par ou ímpar). Deve ficar evidente durante o processo que o palpite de Fernando é essencialmente aleatório. Renato, então, conta a todos qual foi a contribuição e Fernando ganha apenas se adivinhar a paridade correta. Fernando pode verificar se Renato não alterou a entrada escolhida, verificando se ela dá a saída correta do circuito.

Neste momento, o Cara ou Coroa já foi concluído.

Fernando pode trapacear se, diante de uma saída, ele conseguir encontrar a entrada que a produziu. Assim, é do interesse de Renato garantir que a função do circuito seja de mão única, como discutido na Atividade 15, para evitar que Fernando trapaceie. Uma função de mão única é aquela na a qual a saída é fácil de calcular se você souber qual é a entrada, mas a entrada é muito difícil de calcular para uma dada saída.

Renato pode trapacear se encontrar duas entradas de paridades opostas que produzem a mesma saída. Então, seja lá como Fernando faça para adivinhar, Renato pode revelar a entrada que mostra que Fernando está errado. Portanto, é do interesse de Fernando garantir que o circuito não mapeie muitas entradas diferentes para a mesma saída.

  1. Verifique se os alunos conseguem encontrar uma maneira de Renato ou Fernando trapacear. Na primeira linha da tabela você pode ver que várias entradas diferentes geram a saída 010010. Por exemplo, 000001, 000011, 000101, etc. Assim, se Renato diz que escolheu a saída 010010, ele pode escolher a entrada 000001 caso Fernando adivinhe que a paridade é par. Renato pode escolher 000011 se Fernando adivinhar que a paridade é ímpar.

Com este circuito, é difícil para Fernando trapacear. Mas se a saída escolhida for 011000, então a entrada deve ter sido 100010 - não há outra possibilidade! Você pode conferir isso através da tabela. Assim, se este é o número que Renato, por acaso, inventa, Fernando pode adivinhar a paridade e ter certeza de estar correto. Um sistema computacional usa muito mais bits, então haveria muitas possibilidades para tentar (cada bit extra duplica o número de possibilidades).

  1. Agora peça aos grupos que elaborem seus próprios circuitos para este jogo. Veja se eles conseguem encontrar um circuito que seja fácil para Renato trapacear, e outro que seja fácil para Fernando trapacear. Não há razão para o circuito ter seis entradas. Pode até ter números diferentes de entradas e saídas.

Variações e Extensões

  1. Um elemento óbvio, necessário na prática dessa atividade, é a cooperação para construir um circuito aceitável tanto para Renato quanto para Fernando. Isso pode fazer com que a atividade seja ainda mais divertida para os alunos, mas é provável que torne o procedimento inoperacional na prática - especialmente através do telefone! No entanto, existe uma alternativa simples na qual ambos participantes constroem seus circuitos independentemente e os disponibilizam ao público. Nesse caso, então, Renato escolhe a entrada através dos dois circuitos e une as duas saídas comparando os bits correspondentes e tornando a saída final um 1 se as saídas forem iguais e 0 se forem diferentes. Nessa situação, nenhum dos participantes pode trapacear, pois se apenas um dos circuitos for de mão única, então, a combinação dos dois circuitos será, também, uma função de mão única.

As duas variações seguintes não se referem aos protocolos de segurança nem ao problema apresentado pelo Cara ou Coroa, mas sim à ideia de circuitos construídos a partir de portas lógicas E e OU. Eles exploram algumas noções importantes nos fundamentos de lógica. Esse tipo de lógica é chamado de álgebra booleana, cujo nome é dado graças ao matemático George Boole (1815-64).

  1. Os alunos já devem ter notado que uma entrada zero (000000) produz uma saída zero. Da mesma forma, uma entrada um (111111) produz uma saída composta por uns. Pode haver outras entradas que produzem essas saídas também; de fato, há o exemplo 000010, que produz zeros. Além do exemplo 110111, que produz uns. Isso é consequência do fato de que os circuitos são compostos de portas E e OU. Ao adicionar uma porta NÃO, que leva apenas uma entrada e produz o oposto como saída (isto é, 0 → 1 para 1 → 0), os alunos podem construir circuitos que não têm a mesma propriedade apresentada anteriormente.

  2. Dois outros tipos importantes de portas lógicas são as NÃO E e NÃO OU, que são as negações das portas E e OU. Desse modo, a negação pelo operador NÃO de A+B (A ou B) é equivalente a negação individual de cada variável da expressão A.B (A e B), e vice-versa. Elas não permitem a obtenção de quaisquer circuitos funcionalmente diferentes, pois seu efeito pode ser sempre obtido com a porta correspondente E ou OU precedida de NÃO. Entretanto, têm a interessante propriedade de que todos os outros tipos de portas podem ser feitos de portas do tipo NÃO E e, também, do tipo NÃO OU.

Após explicar as portas NÃO E e NÃO OU, desafie os alunos a descobrir se alguma dessas pode ser criada a partir de outras portas. Além disso, desafie-os a descobrir se essas portas podem ser feitas a partir de apenas um tipo de porta. A figura abaixo mostra como três portas básicas (NÃO, E e OU) podem ser construídas a partir de portas do tipo NÃO E (na linha superior) e do tipo NÃO OU (na linha inferior).

Folhas de Atividades e Materiais Adicionais

Você também pode baixar todas as folhas de atividade e materiais adicionais em formato editável aqui.

Do que se trata tudo isso?

Nos últimos anos, há um aumento significativo no comércio realizado através de computadores. E ele é essencial para garantir o intercâmbio eletrônico de fundos, transações confidenciais e assinadas, documentos juridicamente vinculativos. O tema criptografia trata da comunicação de forma segura e particular. Há várias décadas, pesquisadores da computação descobriram o resultado contraintuitivo de que o sigilo pode ser garantido através de técnicas que garantem que certas informações sejam mantidas públicas. Esse resultado é o chamado “criptossistema de chave pública” (veja a Atividade 19), que agora é amplamente utilizado como a forma mais segura de troca de informações. Por exemplo, você pode ter visto configurações em seu navegador, tais como o SSL (Secure Sockets Layer) ou, então, o antecessor, TLS (Transport Layer Security). Esses sistemas são baseados em sistemas de chave pública e permitem que seu navegador configure uma conexão com um site de banco, por exemplo, protegendo a integridade e a veracidade do conteúdo que trafega na Internet.

Criptografia não se trata apenas de manter as coisas em segredo, mas de colocar controles sobre informações, limitando o que outros podem descobrir. Também trata do estabelecimento de confiança entre pessoas que estão geograficamente separadas. Regras formais ou “protocolos” para transações criptográficas foram criados para permitir ações aparentemente impossíveis, tais como assinaturas digitais e a capacidade de contar aos outros que você possui um segredo (por exemplo, uma senha) sem revelar o que é. Jogar Cara ou Coroa pelo telefone é mais simples, mas é um problema análogo e que também parece, à primeira vista, impossível.

Em uma situação real, Renato e Fernando não desenhariam um circuito por conta própria, mas adquiririam um programa que faria esse trabalho internamente. Provavelmente nem estariam interessados nas partes internas do software. Entretanto, ambos gostariam de ter certeza de que o outro é incapaz de influenciar o resultado da decisão, independentemente de suas habilidades de informática.

A princípio, quaisquer disputas teriam que ser resolvidas através de um recurso solicitado a um juiz neutro à tarefa. A esse juiz seria dado o circuito, o número binário original de Renato, a saída que ele originalmente enviou a Fernando, e o palpite de Fernando. Uma vez terminada essa troca, tudo vira informação pública, portanto ambos os participantes terão que concordar que foi com base nisso que o resultado foi obtido. O juiz poderá colocar o número original de Renato através do circuito e verificar se a saída é a alegada e, portanto, decidir se a decisão foi tomada de forma justa. Não é necessário dizer que o próprio fato de haver um procedimento claro para verificar se as regras foram seguidas faz com que seja improvável que surja uma disputa. Compare com a situação em que Renato joga uma moeda e Fernando escolhe Cara ou Coroa; nesse cenário, não seria necessário que um juiz assumisse o caso.

Um circuito tão pequeno quanto o ilustrado não seria muito usual na prática, pois é fácil de usá-lo para trapacear. Usar trinta e dois dígitos binários na entrada proporcionaria melhor proteção. No entanto, mesmo isso não garante que seja difícil trapacear. Tudo depende do circuito particular. Outros métodos poderiam ser utilizados, tais como a função de mão única apresentada na Atividade 15. Os métodos utilizados na prática muitas vezes dependem da fatoração números grandes, o que é conhecido por ser um problema difícil (embora, como vamos aprender no final da próxima atividade, não é NP-completo). É fácil verificar que um número é o fator de outro, mas encontrar os fatores de um grande número é uma tarefa demorada. Isso faz com que o trabalho de Renato e Fernando (e do possível juiz) seja ainda mais complexo de se fazer à mão. Embora, como mencionado, na prática seja feito por um software de prateleira.

As assinaturas digitais são baseadas em uma concepção semelhante. Ao tornar pública a saída do circuito para a entrada secreta particular que ele escolheu, Renato é capaz de provar que foi ele quem gerou a saída. Afinal, com uma função de mão única adequada, ninguém pode inventar uma entrada que funcione. Ninguém pode se passar por Renato! Para fazer uma assinatura digital real, um protocolo mais complexo é necessário para garantir que ele possa assinar uma mensagem específica, além de garantir que outros possam verificar que Renato foi o signatário, mesmo que ele afirme não ser. Mas o princípio é o mesmo.

Outra aplicação possível é o jogo de pôquer, através do telefone, em um ambiente onde não há juiz para supervisionar. Todas as ações devem ser feitas pelos próprios jogadores e, se necessário, ao final, determinar um juiz para desempatar a disputa com base nas regras do jogo. Situações semelhantes ocorrem durante negociações contratuais. Naturalmente, os jogadores devem manter suas cartas em segredo durante o jogo. Mas eles devem ser honestos. Não devem, por exemplo, alegar que têm um ás na mão se isso não for verdade. Ao final do jogo, isso pode ser verificado ao permitir que cada jogador inspecione a mão original do outro e sua sequência de jogadas. Outra questão é como administrar as cartas a fim de manter secreta a mão de cada jogador até o final do jogo. Surpreendentemente, isso é possível através de um protocolo de segurança não muito diferente do Cara ou Coroa.

Os protocolos de segurança são extremamente importantes nas transações eletrônicas, seja para identificar o proprietário de um cartão de débito, para autorizar o uso de um celular para uma chamada, ou para autenticar o remetente de um e-mail. A capacidade de realizar essas ações de forma confiável é crucial para o sucesso do comércio eletrônico.

Para saber mais

O tópico criptografia não faz parte do currículo da educação básica, mas pode ser acessível para estudantes de todas as idades. A coleção Matemática Multimídia possui diversos recursos educacionais que abordam esse tópico com níveis de complexidade muito variados. Se você se interessou, conheça alguns deles aqui.