O algoritmo que derrubou os maiores desafios já resolvidos tem nome de animal porque o próprio autor o explicou assim. Em 1978, o matemático britânico John Pollard descreveu um método em que dois cangurus saltam por um campo: um manso, cuja posição se conhece, e um selvagem, que é o que se procura. O manso vai deixando armadilhas onde pisa. Cedo ou tarde, o selvagem pisa numa delas.
A tradução para a curva é direta. O canguru manso parte de um ponto conhecido dentro do intervalo — digamos o meio dele — e a distância que ele já percorreu é anotada a cada salto. O canguru selvagem parte do ponto Q, a chave pública do alvo, cuja distância até a origem é exatamente o número que se quer descobrir.
O detalhe que faz tudo funcionar está no tamanho dos saltos. Ele não é sorteado: é calculado a partir da coordenada do ponto onde o canguru está. Dois cangurus que pisem no mesmo ponto, portanto, dão o mesmo salto seguinte, e o seguinte, e o seguinte — a partir do primeiro encontro os dois caminhos são idênticos para sempre. É isso que transforma um encontro casual numa colisão detectável.
Quando a colisão acontece, a conta é trivial. Sabe-se quanto o manso andou, sabe-se quanto o selvagem andou desde Q, e sabe-se que os dois estão no mesmo lugar. A diferença entre as duas distâncias, somada ao ponto de partida do manso, é a chave privada.
Falta resolver um problema prático: como perceber que a colisão aconteceu, sem guardar todos os pontos por onde cada canguru passou? A resposta são os pontos distinguidos. Escolhe-se uma propriedade rara e fácil de testar — por exemplo, que a coordenada x termine em vinte bits zerados — e só se anota o ponto quando ele tem essa propriedade. Um em cada milhão de saltos, mais ou menos. Como depois da colisão os dois caminhos coincidem, ambos vão acabar pisando no mesmo ponto distinguido, e é ali que o encontro é registrado.
A conta final é a mesma raiz quadrada do método anterior — algo em torno de dois vezes a raiz da largura do intervalo — com uma diferença decisiva: a memória usada é a tabela de pontos distinguidos, que cabe em alguns megabytes. Onde o passo de bebê e passo de gigante pedia setecentos e cinquenta gigabytes para setenta bits, o canguru pede quase nada.
Some-se a isso que ele paraleliza quase perfeitamente. Solte mil cangurus mansos e mil selvagens, cada um numa máquina diferente, todos gravando pontos distinguidos num servidor comum: o trabalho total não muda e o tempo de calendário cai por mil. A técnica de paralelização com pontos distinguidos é de 1999, de Paul van Oorschot e Michael Wiener, e é ela que torna o método prático em escala.
Há duas condições, e as duas importam.
A primeira é que a chave pública precisa ser conhecida. O canguru salta sobre pontos da curva; se você só tem o endereço, não há ponto de partida para o selvagem, e o método não se aplica. Foi a Aula 1 que separou os dois mundos, e é aqui que a separação cobra.
A segunda é que o intervalo precisa ser conhecido. O canguru manso precisa começar perto do selvagem para que o encontro aconteça em poucos saltos; num campo do tamanho da curva inteira, a espera volta a ser 2^128. Sem saber o trecho, não há onde armar a espera.
Repare no que isso significa para uma carteira comum. A sua chave pública fica exposta assim que você gasta pela primeira vez, e ainda assim não há intervalo: ela foi sorteada em 256 bits inteiros, e o canguru precisaria de 2^128 saltos. As duas condições precisam valer juntas, e num desafio elas valem por construção — porque quem o montou escolheu o intervalo de propósito.
Falta olhar o hardware que executa esses saltos, e onde ele para. Na próxima aula, placas de vídeo, ASICs e a distância real entre 2^40 e 2^70.