últimos anos, os criptógrafos conseguiram criar uma grande quantidade deles.
Podemos ilustrar com mais simplicidade o princípio envolvido se, em vez de falarmos de
senhas pessoais, pensarmos em modos de colorir mapas. O aclamado teorema das quatro cores
foi conjecturado em 1852 por Francis Guthrie, um estudante de pós-graduação da University
College London. O teorema afirma que qualquer mapa num plano pode ser colorido com no
máximo quatro cores de modo que países adjacentes nunca recebam a mesma cor; foi
finalmente provado em 1976 por Kenneth Appel e Wolfgang Haken, da Universidade de
Illinois. No entanto, se nos limitarmos somente a três cores, alguns mapas poderão ser
coloridos, e outros não.
Suponha que a gerente do seu banco lhe mande um mapa excessivamente complexo, e você
queira convencê-la de que sabe como colori-lo com três cores sem revelar as cores
correspondentes a cada região. Nesse caso você pode construir um elaborado aparelho
eletrônico controlado por duas telas sensíveis ao toque — uma no banco, a outra na sua casa.
O aparelho é configurado para fazer o seguinte, e apenas o seguinte (ver Figura 8.1):
Primeiro, você programa na máquina o modo de colorir o mapa (digamos, tocando as
regiões na tela — um toque para vermelho, dois para azul, três para amarelo).
A seguir, a gerente do banco escolhe a fronteira entre dois países. A máquina realiza uma
permutação aleatória do seu esquema de cores — por exemplo, substituindo sistematicamente
o seu vermelho pelo azul, o seu azul pelo vermelho, e deixando o amarelo como está. Existem
seis maneiras possíveis de permutarmos as cores, e a gerente não sabe qual permutação a
máquina escolheu. Então, a tela da gerente exibe as novas cores dos dois países adjacentes à
fronteira selecionada, sem que nenhum dos demais países tenha sido colorido. Se a coloração
original for válida, essas duas cores deverão ser diferentes.
Figura 8.1
Modo de convencer a gerente do seu banco que você pode colorir um mapa com apenas três cores. Repita
até que todos os lados sejam selecionados.A gerente repete então as mesmas operações até que todas as margens sejam testadas,
sendo assim capaz de determinar se a sua afirmação, de que coloriu o mapa com três cores, é
verdadeira. De fato, se a sua coloração original estiver errada, de modo que dois países
adjacentes tenham a mesma cor, em algum momento a gerente do seu banco selecionará a
fronteira entre eles e as duas cores permutadas reveladas pela máquina serão idênticas. Se, por
outro lado, as cores permutadas em todas as fronteiras forem diferentes, o seu mapa original