Siga-nos

Perfil

Expresso

Isto é Matemática

Como partilhar um segredo?

  • 333

Imagine que tem um segredo cabeludo, por exemplo o código do cofre onde guarda o seu testamento. Gostaria de deixar o código a quatro pessoas, mas de forma que nenhuma delas sozinha consiga abrir o cofre. O que gostaria mesmo é que quaisquer três delas juntas o consigam abrir, mas uma delas sozinha ou mesmo duas não consiga. Como resolver o problema?

Esta semana explicamos como resolver este problema. É ver o vídeo!

Um sistema de segurança, frequentemente usado em instalações militares, é simplesmente guardar os códigos de lançamento num cofre com dois cadeados e entregar as chaves a pessoas diferentes, esta é a conhecida two-man rule. Abaixo podemos ver uma imagem de um desses cofres num centro de controle de mísseis real. Claro que este problema tem a desvantagem de que se uma das pessoas ficar inoperacional, o lançamento não pode ser executado.

Será que não há uma forma prática de resolver o problema da distribuição da chave por quatro generais, usando cadeados e sendo suficientes três deles, e não menos que três, para abrir o cofre?

Sim, há uma solução! Colocamos seis cadeados na porta, vamos chamar-lhes cadeados A, B, C, D, E e F. Agora fazemos duas chaves para cada um dos cadeados: duas chaves A que abrem o cadeado A, duas chaves B que abrem o B, e assim por diante. Finalmente distribuímos as chaves pelos quatro generais de acordo com o esquema da figura seguinte, a cada general é entregue um conjunto de três chaves como indicado no esquema.

E já está! Um deles sozinho só consegue abrir três cadeados e, portanto, não consegue abrir o cofre. Como pode observar a distribuição foi feita de forma a que qualquer par de generais que junte as suas seis chaves também não consegue abrir a porta. Também é fácil de ver que qualquer grupo de três generais que junte as suas chaves já consegue abrir a porta.

O problema deste sistema é que o número de cadeados e chaves necessárias para resolver o problema, para um número maior de generais, cresce muito rapidamente. Por exemplo, se forem 11 generais e para que só seis deles juntos, e não menos, consigam abrir a porta, um esquema semelhante exigiria 462 cadeados e 252 chaves! Já o método de Shamir apresentado no episódio desta semana é facilmente generalizável para um número arbitrário de generais.

Enquanto estava a escrever o programa, ocorreu-me uma solução curiosa. Se retirarmos as dobradiças da porta, fizermos uma porta quadrada, colocarmos um cadeado em cada uma das arestas e entregarmos uma chave a cada um dos generais, o problema está resolvido.

Sempre que três, e não menos de três, abrem os cadeados com as suas chaves, desprendem três dos lados do quadrado e a porta pode abrir, ao longo da aresta que ainda fica com o cadeado fechado. Substituindo a porta quadrada por uma porta pentagonal, podemos resolver o problema se quisermos ter cinco generais em que são necessários quatro deles para abrir a porta. Na verdade, este tipo de solução resolve o problema para qualquer número de generais, quando queremos que a porta posso ser aberta faltando só um dos generais.

Tanto quanto sei esta solução é original. Vou deixar-lhe um desafio: consegue inventar uma solução para outras combinações de generais. Por exemplo, como construir um cofre e como colocar cadeados, de forma a entregarmos chaves a cinco pessoas e seja necessário um mínimo de três para conseguir abrir o cofre. O céu é o limite, tanto quanto sei a pergunta nunca foi colocada e eu não sei a resposta! Talvez fazer portas estranhas, várias portas, não sei... Se conseguir resolver o problema, deixe a solução na caixa de comentários abaixo ou escreva-me (roma@fct.unl.pt ). Bom trabalho!

O programa Isto é matemática tem o apoio da Fundação Vodafone Portugal. Se perdeu algum dos episódios das nossas primeiras temporadas, ou simplesmente para recordar, espreite e subscreva os nossos canais Youtube e Facebook.