Atividade 19: Criptografia para jovens – Criptografia de chaves públicas

Apresentação

Criptografia é a chave da segurança informacional. E a chave da criptografia moderna é que usando apenas informações públicas, um remetente possa trancar sua mensagem de forma que ela só possa ser destrancada (em particular, é claro) por seu destinatário pretendido.

É como se todos comprassem um cadeado, escrevessem seu nome nele, e colocassem todos eles em uma mesma mesa, para outras pessoas usarem. Eles ficariam com a chave é claro – os cadeados são do tipo que você só precisar apertá-los para fechar. Se eu quiser te mandar uma mensagem segura, coloco ela em uma caixa, pego seu cadeado, tranco a caixa e a envio a você. Mesmo que ela caia nas mãos erradas, ninguém poderá destrancá-la. Com este esquema não é necessária nenhuma comunicação prévia para providenciar códigos secretos.

Esta atividade mostra como isso pode ser feito digitalmente. No mundo digital, ao invés de pegar seu cadeado e usá-lo, eu o copio e uso a cópia, deixando o cadeado original na mesa. Se eu fosse fazer uma cópia de cadeado físico, eu só poderia fazer isso desmontando ele. Fazendo isso eu inevitavelmente veria como ele funciona. Mas no mundo digital nós podemos organizar para as pessoas copiarem os cadeados sem descobrir o segredo dele.

Parece impossível? Então leia esta atividade até o fim!

Disciplinas e conteúdos relacionados

Habilidades

Nível de Ensino

Material

Projeção da folha Codificando Criptografia para Jovens.

Os alunos são divididos em grupos de quatro integrantes, e dentro desses grupos eles formam duas duplas. Para cada grupo de alunos você vai precisar de:

Criptografia para jovens

Introdução

Esta é a atividade mais tecnicamente desafiadora deste livro. Embora recompensadora, requer trabalho cuidadoso e concentração constante para completá-la com sucesso. Os alunos já deveriam ter estudado o exemplo de funções de uma via na Atividade 14 - Cidade Turística, e ajudaria se eles concluíssem as outras atividades desta seção (Atividade 16 - Compartilhando segredos e Atividade 17 - A moeda peruana). A atividade também usa as ideias abordadas na Atividade 1 - Contando os pontos e Atividade 5 - Vinte palpites.

Amy está planejando enviar uma mensagem secreta a Bill. Normalmente poderíamos pensar em mensagens secretas como uma sentença ou parágrafo, mas no exercício a seguir Amy enviará apenas um carácter - na verdade, ela enviará apenas um número que representa um carácter. Embora isso possa parecer uma mensagem simplista, tenha em mente que ela poderia enviar uma série de “mensagens” para fazer uma frase e, na prática, o trabalho seria realizado por um computador. E às vezes até pequenas mensagens são importantes - uma das mais célebres mensagens da história, transmitidas por Paul Revere, tinha apenas dois valores possíveis. Veremos como incorporar o número de Amy em uma mensagem criptografada usando o cadeado público de Bill, para que, se alguém a interceptar, não seja possível decodificá-la. Somente Bill pode fazer isso, porque somente ele tem a chave do cadeado.

Nós trancaremos mensagens usando mapas. Não mapas da Ilha do Tesouro, onde o X marca o local, mas mapas de ruas como os da Cidade Turística (Atividade 14), onde as linhas são ruas e os pontos são esquinas. Cada mapa tem uma versão pública – a fechadura - e uma versão privada - a chave.

Discussão

Na folha Para projetar: Codificando Criptografia para Jovens está o mapa público do Bill. Não é um segredo: Bill o coloca na mesa (ou em uma página da web) para todo mundo ver, ou fornece para quem possa querer lhe enviar uma mensagem. Amy tem uma cópia dele; assim como todo mundo. A figura a seguir mostra o mapa privado de Bill. É a mesma que o seu mapa público, exceto que algumas das esquinas são marcadas como especiais, ampliando-as. Ele mantém esta versão do mapa em segredo.

Esta atividade é melhor realizada em sala de aula, pelo menos para começar, porque envolve uma quantidade razoável de trabalho. Embora não seja difícil, isso deve ser feito com precisão, pois erros causarão muitos problemas. É importante que os alunos percebam quão surpreendente é que esse tipo de criptografia possa ser feito – parece impossível (não parece?) - porque eles precisarão dessa motivação para ver através do esforço necessário. Um ponto que achamos altamente motivador para os alunos é que, usando esse método, eles podem passar bilhetes secretos na aula, e mesmo que o professor saiba como o bilhete foi criptografado, não será capaz de decodificá-lo.

  1. Exiba o mapa público do Bill (Para projetar: Codificando Criptografia para Jovens). Decida qual número Amy vai enviar. Agora coloque um número aleatório em cada interseção no mapa, de forma que os números aleatórios somem o número que Amy deseja enviar. Esta figura dá um exemplo desses números como o número superior (sem parênteses) ao lado de cada interseção. Aqui, Amy optou por enviar o número 66, então todos os números sem parênteses somam 66. Se necessário, você pode usar números negativos para obter o total até o valor desejado.

  1. Agora, Amy deve calcular o que enviar para Bill. Se ela enviasse o mapa com os números não seria bom, porque se ele caísse nas mãos erradas, qualquer um poderia somá-los e ver a mensagem.

Em vez disso, escolha qualquer interseção, observe-a e aos seus vizinhos e some os números neles. Escreva este número na interseção escolhida, entre parênteses ou usando uma caneta de cor diferente. Por exemplo, a interseção mais à direita no mapa público do exemplo está conectada a três outras, rotuladas 1, 4, 11 e é rotulada como 6. Portanto, ela tem um total de 22. Agora repita isso para todas as outras intersecções no mapa. Isso deve fornecer os números entre parênteses.

  1. Amy enviará a Bill o seu mapa, com apenas os números entre parênteses nele. Apague os números originais e as somas, deixando apenas os números que Amy envia; ou faça um novo mapa com apenas esses números nele, como mostrado abaixo.

  2. Veja se qualquer um dos alunos consegue encontrar uma maneira de dizer a partir disso o que era a mensagem original. Eles não serão capazes. Somente alguém com a chave particular do Bill pode decodificar a mensagem para encontrar a mensagem que Amy queria enviar originalmente. Na mensagem codificada, marque as intersecções especiais ampliadas no mapa particular de Bill. Para decodificar a mensagem, Bill olha apenas as intersecções secretas marcadas e soma os números nelas. No exemplo, essas interseções são rotuladas 13, 13, 22, 18, somando 66, a mensagem original de Amy.

  1. Como isso funciona? Bem, o mapa é um mapa especial. Suponha que Bill escolha uma das interseções marcadas e desenhe as intersecções uma rua distante dela, repetindo o procedimento para cada interseção marcada. Isso dividiria o mapa em partes não sobrepostas, como ilustrado aqui. Mostre essas partes para os alunos desenhando os limites no mapa. O grupo de interseções em cada parte soma exatamente o número transmitido nas interseções marcadas, de modo que a soma dos quatro números nas interseções aumentadas será a soma de todos os números originais no mapa original; que será a mensagem original! (Encontrando as partes não sobrepostas do mapa, encontra-se a soma e a mensagem original, mas sem o mapa público é muito difícil fazer isso mesmo para mapas não muito grandes.)

Ufa! Parece muito trabalho para enviar uma carta. E é muito trabalho para enviar uma carta - a criptografia não é uma tarefa fácil. Mas veja o que foi realizado: sigilo completo usando uma chave pública, sem necessidade de qualquer acordo prévio entre os participantes. Você pode publicar sua chave num quadro de avisos e qualquer pessoa poderia lhe enviar uma mensagem secreta, mas ninguém poderia descriptografá-la sem a chave particular. E na vida real todo o cálculo é feito por um pacote de software que você adquire (normalmente incorporado no seu navegador de internet), então é apenas o computador que precisa trabalhar duro.

Talvez sua classe gostaria de saber que eles se juntaram ao seleto grupo de pessoas que realmente trabalharam, à mão, com um exemplo de criptografia de chave pública - os cientistas da computação praticantes considerariam isso como uma tarefa quase impossível e poucas pessoas já a fizeram!

Agora, que tal espionar? O mapa de Bill é como os da Cidade Turística (Atividade 14), onde os cruzamentos marcados são uma forma mínima de colocar vans de sorvete para servir todas as esquinas sem que ninguém precise andar mais de um quarteirão. Vimos em Cidade Turística que é fácil para Bill fazer esse mapa começando com as peças mostradas em seu mapa privado, e é muito difícil para qualquer outra pessoa encontrar a maneira mínima de colocar vans de sorvete, exceto pelo método da força bruta. O método da força bruta é tentar cada configuração possível com uma van, então cada configuração com duas vans e assim por diante até encontrar uma solução. Ninguém sabe se existe um método melhor para um mapa geral - e você pode apostar que muitas pessoas tentaram encontrar um!

Se Bill começar com um mapa suficientemente complicado com, digamos, cinquenta ou cem cruzamentos, parece que ninguém jamais poderá decifrar o código – mesmo os matemáticos mais inteligentes tentaram muito e falharam. (Mas há uma ressalva: veja abaixo em “Do que se trata tudo isso?”)

  1. Tendo passado um exemplo com toda a sala, divida os alunos em grupos de quatro integrantes. Dê a cada par de cada grupo o mapa público que está nos mapas de Criptografia para Jovens. Cada par deve escolher uma “mensagem” (qualquer inteiro), codificá-la com a chave pública e fornecer o mapa resultante para o outro grupo. O outro grupo pode tentar decodificá-la, mas é improvável que eles tenham sucesso até que recebam (ou façam!) o mapa particular. Então, devem fornecer o mapa particular e ver se agora eles podem decodificá-lo corretamente.

  2. Agora, cada par pode criar seu próprio mapa, mantendo a versão particular em segredo e dando a versão pública para o outro par - ou mesmo “publicando” no quadro da sala de aula. O princípio para projetar mapas é exatamente o mesmo que foi discutido na atividade Cidade Turística, e ruas extras podem ser adicionadas para disfarçar a solução. Apenas tome cuidado para não adicionar ruas extras em qualquer um dos pontos “especiais”. Isso criaria uma intersecção a partir da qual duas vans de sorvete poderiam ser alcançadas em um salto, o que é bom para a situação da cidade turística, mas causaria estragos ao criptografar. Isso ocorre porque os pontos especiais não mais decomporiam o mapa em partes não sobrepostas, conforme ilustrado no mapa particular, e isso é essencial para que o truque funcione.

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?

Existem vários motivos para você querer enviar mensagens secretas pela rede de computadores sem que ninguém, além do destinatário pretendido, possa decodificar, não importa quão espertos eles sejam ou quão duro eles tentem. E é claro que existem várias maneiras pelas quais isso pode ser feito se o remetente e o destinatário compartilharem um código secreto. Mas a parte inteligente da criptografia de chave pública é que Amy pode enviar a Bill uma mensagem segura sem nenhum acordo secreto prévio, apenas pegando seu “cadeado” de um local público como uma página da web.

O sigilo é apenas um lado da criptografia. Outro é a autenticação: quando Amy recebe uma mensagem de Bill, como ela sabe que a mensagem realmente vem dele e não de algum impostor? Suponha que ela receba um email que diz: “Querida, estou preso aqui sem dinheiro. Coloque $100 na minha conta bancária, número 0241-45-784329 – Com amor, Bill.” Como ela pode saber se a mensagem realmente vem de Bill? Alguns sistemas criptográficos de chave pública podem ser usados para isso também. Assim como Amy envia a Bill uma mensagem secreta, codificando-a com sua chave pública, ele pode enviar a ela uma mensagem que somente ele poderia ter gerado codificando-a com sua chave privada. Se Amy puder decodificá-la com a chave pública de Bill, então deve ter vindo dele. Claro, qualquer outra pessoa poderia decodificá-la também, pois a chave é pública, mas se a mensagem for exclusiva para ela, Bill pode codificá-la uma segunda vez com a chave pública de Amy. Essa codificação dupla fornece sigilo e autenticação com o mesmo esquema básico de chaves públicas e privadas.

Agora é o momento de admitir que, embora o esquema ilustrado nesta atividade seja muito similar a um sistema de criptografia de chave pública de nível industrial, ele não é realmente seguro – mesmo que um mapa bastante grande seja usado.

A razão é que, embora não haja uma maneira conhecida de encontrar a forma de colocar o mínimo de vans de sorvete em um mapa arbitrário, e assim o esquema é de fato seguro deste ponto de vista, acontece de haver uma maneira completamente diferente de atacá-lo. É improvável que a ideia ocorra aos estudantes, pelo menos até o ensino médio, mas você deve pelo menos saber que ela existe. Você pode dizer que o esquema que estamos estudando é a prova de estudantes em nível escolar, mas não a prova de matemáticos. Ignore o próximo parágrafo se você não se interessa tanto por matemática!

Numere as interseções no mapa 1, 2, 3,… Denote os números originais atribuídos às interseções por b1, b2, b3,…, e os números que são realmente transmitidos por t1, t2, t3,…. Suponha que a interseção 1 esteja conectada às interseções 2, 3 e 4. Então, o número que é transmitido para essa interseção é:

t1 = b1 + b2 + b3 + b4

Obviamente, existem equações semelhantes para todas as outras interseções – na verdade, existe o mesmo número de equações que existem incógnitas b1, b2, b3, … Um bisbilhoteiro conhece o mapa público e os números t1, t2, t3, … que são transmitidos e, portanto, pode anotar as equações e resolvê-las com um programa de computador para resolver equações. Uma vez que os números originais foram obtidos, a mensagem é apenas a soma deles - não há necessidade para descobrir o mapa de “descriptografia”. O esforço computacional necessário para resolver diretamente as equações usando a eliminação gaussiana é proporcional ao cubo do número de equações, mas como essas equações são dispersas - a maioria dos coeficientes é zero – existem técnicas ainda mais eficientes. Compare isso com o esforço computacional exponencial que, até onde sabemos, é o melhor que se pode fazer para criar o mapa de “descriptografia”.

Esperamos que você não se sinta enganado! De fato, os processos envolvidos em sistemas de criptografia de chave pública reais são praticamente idênticos aos que vimos, exceto que as técnicas que eles usam para codificação são diferentes - e realmente são inviáveis para fazer à mão. O método original de chave pública, e ainda um dos mais seguros, baseia-se na dificuldade de fatorar grandes números.

Quais são os fatores do número de 100 dígitos: 9.412.343.607.359.262.946.971.172.136.294.514.357.528.981.378.983.082.541.347.532.211.942.640.121.301.590.698.634.089.611.468.911.681? Não gaste muito tempo!

Eles são 86.759.222.313.428.390.812.218.077.095.850.708.048.977 e 108.488.104.853.637.470.612.961.399.842.972.948.409.834.611.525.790.577.216.753. Não existem outros fatores: esses dois números são primos. Encontrá-los é um trabalho e tanto; na verdade é um projeto de vários meses para um supercomputador.

Agora, em um sistema de criptografia de chave pública real, Bill pode usar o número de 100 dígitos como sua chave pública e os dois fatores como a chave privada. Não seria muito difícil criar essas chaves: tudo que você precisa é uma maneira de calcular números primos grandes. Encontre dois números primos grandes o suficiente (o que não é difícil de fazer), multiplique-os, e pronto, aí está a sua chave pública. Multiplicar números grandes não é grande coisa para um computador. Dada a chave pública, ninguém pode encontrar sua chave privada, a menos que eles tenham acesso a vários meses de tempo de supercomputador. E se você está preocupado que eles tenham, use números primos de 200 dígitos em vez de primos de 100 dígitos - isso os atrasará em anos! O ponto principal é que o custo de quebrar a chave seria maior que o valor das informações que ela desbloquearia. Na prática, chaves de 512 bits ou maiores são comuns para configurar conexões seguras, o que equivale a cerca de 155 dígitos decimais ou mais.

Ainda não foi possível codificar uma mensagem usando uma chave pública baseada em números primos de uma maneira que não possa ser decodificada sem a chave privada. Para fazer isso, a vida não é tão simples como dissemos acima. Não são os dois números primos que são usados como chave privada e seu produto como chave pública; em vez disso, são números derivados deles. Mas o efeito é o mesmo: você pode decifrar o código fatorando o número. De qualquer forma, não é difícil superar essas dificuldades e transformar o esquema em um algoritmo de criptografia e “descriptografia” adequado, mas não vamos falar sobre isso aqui. Esta atividade já foi suficientemente trabalhosa!

Quão seguro é o sistema baseado em números primos? Bem, fatorar números grandes é um problema que tem chamado a atenção dos maiores matemáticos do mundo por vários séculos, e embora tenham sido descobertos métodos que são significativamente melhores do que o método da força bruta, tentar todos os fatores possíveis, ninguém descobriu um algoritmo rápido (ou seja, de tempo polinomial). (Mas também, ninguém provou que esse algoritmo é impossível). Portanto, o esquema parece não apenas ser seguro para alunos em nível escolar, mas também seguro para matemáticos. Mas cuidado. Assim como há uma maneira de decifrar o código de Bill sem resolver o problema da Cidade Turística, pode haver uma maneira de decifrar os códigos dos números primos sem realmente fatorar números grandes. Isso foi cuidadosamente verificado e parece OK.

Outra preocupação é que se houverem apenas algumas mensagens possíveis, um interceptador poderia criptografar cada uma delas em vez de usar a chave pública e comparar a mensagem com todas as possibilidades. O método da Amy evita isso porque existem muitas formas de criptografar a mesma mensagem, dependendo de quais números são escolhidos. Na prática sistemas criptográficos são projetados de forma que existam mensagens possíveis demais para testar todas elas, mesmo com a ajuda de um computador muito rápido.

Não se sabe se existe um método rápido de resolver problemas de fatorar números primos. Ninguém conseguiu criar um, mas também não foi provado que um método rápido é impossível. Se um algoritmo rápido para resolver este problema for encontrado, muitos sistemas criptográficos usados atualmente se tornarão inseguros. No Tema 4 nós discutimos problemas de NP completo que seguem a mesma regra: se um deles é eficientemente solucionável, então todos devem ser. Uma vez que tanto esforço (mal sucedido) foi colocado em encontrar um algoritmo rápido para esses problemas, eles parecem candidatos excelentes para se usar para projetar um sistema criptográfico seguro. Infelizmente, existem dificuldades neste plano, e até agora os projetistas de sistemas criptográficos foram forçados a confiar em problemas (como fatoração de primos) que podem ser mais fáceis de resolver do que os problemas de NP completo - talvez muito mais fáceis. As respostas às perguntas levantadas por tudo isso valem muitos milhões de dólares para a indústria e são consideradas vitais para a segurança nacional. Atualmente criptografia é uma área de pesquisa muito ativa em ciência da computação.

Para saber mais

O vídeo Venda Segura da coleção Matemática Multimídia discute como funcionam métodos de criptografia de chave pública. O guia do professor também traz aprofundamentos e referências adicionais.

O texto Criptografia de chaves públicas e grafos para a Educação Básica, de autoria de Leonardo Barichello e Letícia Miguel Pinto, aborda a atividade apresentada anterior com alguns complementos de conteúdo.