Quebrando a Internet. Medo e repulsa com o algoritmo de Shor

Odhran McConnell Segue 8 de jul · 9 min ler

Nota: Graças a minutephysics para o primer que me permitiu fazer este artigo e para tornar muito mais fácil para mim aprender sobre isso.

Tendo iniciado a jornada de aprendizado tanto quanto possível sobre computação quântica , decidi que o próximo passo é tentar entender algo prático. Tem havido muita discussão e debate sobre computadores quânticos tendo o potencial de quebrar a criptografia , tornando assim todo o tráfego criptografado da Internet aberto a olhares indiscretos, então decidi investigar.

Aviso justo, isso vai ficar um pouco complicado e vou tentar explicá-lo em termos leigos, embora haja uma ou duas equações envolvidas – mas nada mais complicado do que a álgebra do ensino médio … eu espero.

Toda a criptografia na Internet baseia-se em encontrar os fatores de um número não primo realmente grande. Ao contrário de multiplicar números juntos para obter um número realmente grande, dividir um número realmente grande em fatores inteiros leva muito tempo. O melhor método que temos para fazer isso é incrivelmente lento. Em meu artigo anterior, mencionei que o maior número RSA fatorado foi de 768 bits e levou 15.000 anos para decifrar (dois anos em tempo real, em muitas centenas de computadores). Isso leva muito tempo e eletricidade para ser útil.

Digite o algoritmo de Shor, os computadores quânticos e a ameaça que eles representam para efetivamente quebrar a criptografia. O algoritmo é baseado em dois aspectos da teoria quântica, 'superposição quântica' e 'interferência'. Peter Shor é um professor americano de matemática aplicada no MIT e é o inventor deste algoritmo quântico de seu trabalho nos anos 90 no campo da computação quântica.

A criptografia RSA é baseada em um mecanismo de obscurecimento de informações com um grande número, de modo que a única maneira de desobstruir é encontrar os fatores desse grande número. Nosso melhor método atual adivinha efetivamente um número e, se não for um fator, ele tenta outro até encontrar um palpite que funcione. Mesmo com otimizações durante o processo, é extremamente lento.

No final das contas, toda a criptografia é baseada na esperança de que o processo de factoring leve tanto tempo que as pessoas não se incomodem e até hoje isso tenha sido o caso.

O algoritmo de Shor é baseado em fazer um palpite ruim de um fator e, em seguida, usar o algoritmo para transformar esse palpite ruim em um palpite muito melhor. Ao contrário dos computadores quânticos que tomam uma quantidade incrivelmente pequena de tempo, os computadores clássicos também podem executar o algoritmo de Shor, mas levam muito tempo para serem concluídos.

Fundamentalmente, pode ser dividido em duas partes:

  1. A parte matemática – tornando a adivinhação mais precisa; e
  2. A parte física – acelerando o processo

O TL; DR aqui é aproximadamente o seguinte:

  1. Faça um palpite, g, em um número que compartilha fatores com o número criptografado RSA, N
  2. O algoritmo de Shor diz que um palpite muito melhor seria g ^ (p / 2) ± 1, onde P é o número de vezes que você teria que multiplicar g com ele mesmo de tal forma que
    g ^ (p) = m * N + 1, onde m é algum múltiplo de N
  3. Podemos encontrar P muito rapidamente usando superposições quânticas e interferências para que todas as superposições erradas de P destrutivamente interfiram umas nas outras e você fique com o valor correto
  4. Trabalhando isso de volta, podemos então usar o algoritmo de Euclides para encontrar os fatores reais
  5. Então nós quebramos a criptografia!

A parte de matemática

(NOTA: A seção seguinte usa * para simbolizar a multiplicação – enquanto isso pode ofender os matemáticos puristas para os propósitos deste artigo, ele está sendo usado devido ao uso comum por não-matemáticos)

Vamos começar com um grande número N , que você precisa encontrar os fatores de. Primeiro passo, faça um palpite, g , que é um número menor que N. Números que compartilham fatores também são bons por causa do algoritmo de Euclides , o qual não vou abordar agora, mas efetivamente significa que podemos encontrar os fatores reais usando isso.

Agora podemos usar um truque baseado no seguinte, para transformar o mau palpite em algo mais preciso:

Pegue qualquer par de números inteiros que não compartilhem um fator com N e multiplique um deles por si só, o suficiente para que você acabe com um número inteiro múltiplo do outro número mais 1

Fator A * Fator B ? A * A * A * A… (vezes suficientes) = alguns múltiplos * B + 1

Escrito de forma mais sucinta, isto é:

A ^ (P) = m * B + 1, para alguma potência P e alguns múltiplos m. A parte importante aqui é que, eventualmente, acabamos com uma situação em que temos um resto de 1.

Vamos dar uma olhada em alguns exemplos.

Se tomarmos 7 e 15 como A e B, então:

7 2 = 3 * 15 + 4

7 3 = 22 * 15 + 13

7 4 = 160 * 15 + 1 ? Temos um bom jogo!

Ou olhando para 42 e 13:

42 2 = 135 * 13 + 9

42 3 = 5699 * 13 + 1 ? E outro jogo

Trabalhando desta para a frente, para o grande número N e alguns palpite ruim g, temos a garantia de que:

g ^ (p) = m * N + 1

Sendo inteligente com a nossa matemática aqui, também podemos escrever isso como:

g ^ (p – 1) = m * N

Ou seja ainda mais esperto, reorganizando a álgebra assim:

(g ^ (p / 2) + 1) * (g ^ (p / 2) -1) = m * N

Agora, temos uma equação que aproximadamente parece algo * algo = m * N, ou seja, os fatores desconhecidos. E melhor ainda, essas duas partes estão no formato que o algoritmo de Shor prescreve, ou seja, faça um chute, multiplique por si só p / 2 vezes e depois adicione ou subtraia 1:

g ? g ^ (p / 2) ± 1

Nesta equação, agora temos uma situação em que cada parte pode ser um múltiplo dos fatores reais que estamos procurando, e Euclides virá ao resgate para que possamos encontrar os fatores reais. Quando os tivermos, teremos quebrado a criptografia!

A parte da física

(Nota: A notação para uma superposição é | algo> onde o algo é um valor, conjunto de valores ou uma função)

Agora, para a parte difícil, como encontrar P (ou seja, o número de vezes que precisamos multiplicar nosso palpite por si só para obter: m * N + 1).

Ao contrário de uma computação normal – que dá uma resposta para uma dada entrada – uma computação quântica pode calcular simultaneamente uma carga inteira de respostas possíveis para uma dada entrada usando uma superposição quântica. Melhor ainda, todas essas possíveis respostas são reduzidas a uma única resposta correta por interferência quântica destrutiva (isto é, assim como as ondas podem interferir destrutivamente umas nas outras para cancelar). Deixe-me tentar explicar um passo de cada vez.

Em geral, pode ser muito difícil tentar colocar qualquer coisa em uma forma quântica, onde todas as respostas erradas interferem destrutivamente, mas é exatamente isso que o algoritmo de Shor faz para o problema de encontrar P.

Apenas para recapitular, fizemos um mau palpite, g, e estamos tentando encontrar P, tal que g ^ (p) = m * N + 1. AP que faz isso também é muito provável que compartilhe fatores com N (isto é, g ^ (p / 2) ± 1).

Em seguida, precisamos construir um programa de computador de mecânica quântica que tome um número x como entrada e, então, elevemos nosso palpite ao poder de x. O programa precisa então pegar esse número e calcular quanto maior que um múltiplo de N é, vamos chamar isso de resto.

| x> ? qf (gx) ? | x, gx> ? qf (?> m * N) ? | x, + r>, onde qf é uma função quântica e o restante, r, estamos procurando eventualmente ser 1.

Como é um computador quântico em que estamos trabalhando, podemos enviar uma superposição de números em vez de um único número para acelerar o processo. Por exemplo:

| 1> + | 2> + | 3> +… ? qf (gx) ? | 1, g ^ 1> + | 2, g ^ 2> + | 3, g ^ 3> +…

E então uma superposição de quanto maiores esses poderes são para o número:

? qf (?> M * N) ? | 1, + 19> + | 2, + 37> + | 3, + 23> +…

Se tentarmos medir a superposição neste ponto, teremos problemas (estamos olhando para o gato na caixa ) porque o estado quântico entrará em colapso e retornará uma resposta aleatória (e não necessariamente a correta). Em vez disso, precisamos obter todas as respostas não-P para interferir destrutivamente e cancelar, deixando-nos com apenas uma resposta possível, o verdadeiro P.

Felizmente, há outro truque matemático que nos permitirá fazer exatamente isso. Então, novamente, vamos recapitular. Se soubéssemos o que P era, poderíamos aumentar nosso palpite, g, para o poder de P e obter mais 1 que um múltiplo de N:

g ^ p = m * N + 1

Se tomarmos nosso palpite para um poder aleatório, digamos 42, então provavelmente haverá algum outro número a mais do que um múltiplo de N:

g ^ 42 = m * N + 7

Agora, aqui está a parte interessante, se elevarmos nosso palpite ao poder daquele número aleatório (42) mais P, então será o mesmo resto com um múltiplo diferente:

g ^ (42 + p) = m2 * N + 7

Note que o resto é sempre o mesmo, não importa o múltiplo de P que nós adicionamos ao nosso número aleatório x:

g ^ x = m * N + r

g ^ (x + P) = m2 * N + r

g ^ (x + 2P) = m3 * N + r

g ^ (x + 3P) = m4 * N + r

Etc.

Efetivamente, P tem uma propriedade repetitiva para que, se tomarmos nosso palpite e elevá-lo ao poder de um número aleatório e, em seguida, adicionar vários Ps a ele, o restante permanecerá o mesmo.

g ^ x ou g ^ (x + P) ou g ^ (x + 2P) ou g ^ (x + 3P) ou… ? + r (r é sempre o mesmo)

Este padrão repetitivo não é algo que você possa descobrir levando em consideração apenas uma potência. Pelo contrário, é uma relação estrutural entre diferentes poderes e podemos aproveitá-lo porque as computações quânticas podem tirar proveito de superposições de diferentes poderes possíveis.

Se tomarmos a superposição de todos os poderes possíveis e apenas medirmos a quantidade mais do que um múltiplo de N parte (o resto, + r), então ficamos com uma superposição apenas dos poderes que poderiam ter resultado no mesmo resto.

A parte chave aqui é que cada uma dessas superposições é exatamente P uma da outra! Estas superposições repetem com um período de P, ou, para ser mais específico, têm uma frequência de 1 / P. Se conseguirmos encontrar a frequência, podemos encontrar P e quebrar a criptografia. Felizmente, temos uma ferramenta para encontrar freqüências: a Transformada de Fourier .

Transformadas de Fourier são uma maneira de inserir um sinal, por exemplo, um sinal de áudio, e elas produzirão um gráfico de todas as freqüências de que o sinal é composto. É assim que funcionam os fones de ouvido com cancelamento de ruído, eles selecionam as freqüências do ambiente ao redor usando uma transformada de Fourier e as cancelam usando interferência de onda. Coisas muito inteligentes.

Para resolver o nosso problema aqui, há uma versão quântica da transformada de Fourier, que podemos aplicar à nossa superposição e encontrar P. Resumindo, isso faz com que todos os valores possíveis que não estão corretos interfiram destrutivamente, de modo que somos deixados com a frequência correta 1 / P.

Agora que temos 1 / P, podemos inverter isso para obter o valor para P (ou seja, 1/1 / P). Contanto que seja um número par, podemos colocar isso de volta em nossa equação g ^ P ± 1, e enquanto isso não for um múltiplo de N, temos a garantia de que ele compartilha um fator com N. Podemos então usar O algoritmo de Euclides para encontrar os fatores reais de N e finalmente quebrar a criptografia!

Próximos passos

Nós temos computadores quânticos hoje , então o que está nos impedindo de quebrar a criptografia agora? Em poucas palavras, o tamanho da memória quântica nesses computadores. Este ainda é um campo emergente de pesquisa e, embora existam alguns computadores quânticos, eles ainda não têm memória quântica suficiente para poder fazer os cálculos necessários para quebrar a criptografia. Algumas estimativas dizem que cerca de 5096 qubits são necessários para quebrar a criptografia RSA de 768 bits no exemplo dado acima. Atualmente, estamos nos 10s de qubits – um longo caminho.

Dizendo isso, muito tempo e dinheiro estão sendo despejados neste campo e os desenvolvimentos estão ganhando ritmo. O que é certo, no entanto, é que os computadores quânticos eventualmente quebrarão a criptografia para que a implantação de uma melhor criptografia seja essencial para combater isso e manter nossas informações privadas realmente privadas.