A dificuldade de gerar primos de 1024 bits

• Este é um experimento de gerar diretamente em Rust os dois primos de cerca de 1024 bits necessários para uma chave RSA de 2048 bits, implementando desde a geração de números aleatórios até operações com inteiros grandes sem dependências externas
• A trial division simples bastava em 16 bits, levando cerca de 40ms, mas mesmo em 64 bits ainda levava 6,4 segundos após otimizações, tornando difícil escalar para 1024 bits
• O teste de Fermat é rápido, mas pode não filtrar pseudoprimes, então a decisão final usa o teste de Miller-Rabin com k=10
• Para ultrapassar os limites dos tipos inteiros básicos, foi criado um BigInt próprio, e ao trocar uma estrutura de array de bool por arrays de bytes e depois por chunks u64, o tempo de geração de um primo de 1024 bits caiu de cerca de 32 minutos para algo entre 60 e 90 segundos
• A implementação final combinou BigInt em chunks u64, divisão rápida, trial division com primos pequenos, incremento de candidato em +2 e execução paralela em 16 threads, encontrando em média um primo de 1024 bits em cerca de 40ms, mas não se trata de uma biblioteca criptográfica validada

---

Criando manualmente primos de 1024 bits para RSA

• O objetivo era gerar diretamente primos que pudessem ser usados na geração de chaves RSA
  • Uma chave RSA de 2048 bits é formada pelo produto de dois primos, então são necessários dois primos de cerca de 1024 bits cada
  • O desafio naturalmente se reduziu a gerar primos de 1024 bits
• O experimento impôs três restrições
  • O código seria escrito do zero, sem dependências externas
  • Seria usado um notebook com CPU AMD Ryzen 7 e 16GB de RAM, sem hardware externo nem nuvem
  • Os primos precisariam ser gerados em um “tempo razoável”
• A linguagem escolhida foi Rust, que a pessoa autora estava aprendendo recentemente
  • Ela foi considerada próxima o suficiente do baixo nível para lidar com esses conceitos, mas de alto nível o bastante para tornar os trechos de código compreensíveis

Os limites da trial division revelados em 16 e 64 bits

• O fluxo básico consistia em gerar repetidamente um número aleatório de N bits e encerrar quando ele passasse no teste de primalidade
• Em vez da crate rand do Rust, os números aleatórios foram gerados lendo diretamente /dev/urandom no Linux
  • /dev/urandom é um arquivo de dispositivo virtual que dá acesso ao CSPRNG do kernel Linux
  • O kernel coleta entropia do ambiente do usuário e faz reseed periódico de uma cifra de fluxo determinística baseada em ChaCha20
• Para números aleatórios de 16 bits, o primeiro e o último bit eram definidos como 1
  • O último bit em 1 garante que o número seja ímpar
  • O primeiro bit em 1 garante o uso de toda a faixa de bits necessária
• Em 16 bits, apenas a trial division, testando divisões de 3 até sqrt(num), já encontrava um primo em cerca de 40ms
  • Um exemplo de execução foi Prime found: 44809, com tempo total de cerca de 0,038 segundo
• Ao escalar para 64 bits, a trial division simples passou a levar cerca de 30 segundos
  • Depois disso, ela foi aprimorada para testar apenas candidatos na forma 6k±1 e primeiro dividir por uma lista de primos pequenos
  • Após a melhoria, o tempo para gerar um primo de 64 bits caiu para cerca de 6,414 segundos
• Mesmo em 64 bits, 6 segundos deixavam claro que essa abordagem não chegaria bem a gerar primos de 1024 bits

Mudando para testes probabilísticos de primalidade

• Foram pesquisados algoritmos determinísticos como APR-CL e ECPP, mas eles se mostraram complexos demais matematicamente e sem explicações acessíveis suficientes para servir de alvo de implementação
• Após examinar o código-fonte do OpenSSL e recomendações do NIST, confirmou-se que testes probabilísticos de primalidade são amplamente usados em casos reais, incluindo RSA
• A partir daí, o algoritmo passou a decidir se um número era um provable prime com certa precisão, em vez de “provar” formalmente que era primo

• Teste de Fermat

  • O pequeno teorema de Fermat usa a relação de que, se p é primo e a não é divisível por p, então a^(p-1) = 1 mod p
  • Como exponenciação simples causaria overflow em u128, foi implementada exponenciação modular
  • pow() recebe o expoente como u32, e elevar u128 a expoentes maiores pode causar overflow
  • A própria multiplicação também pode ultrapassar o intervalo de u128, então temporariamente o processo foi conduzido armazenando números de 64 bits dentro de u128
  • O teste de Fermat é rápido, mas por causa dos Fermat pseudoprimes pode classificar erroneamente um composto como primo
  • Mesmo sendo raros, esses compostos são numerosos o bastante para tornar o teste de Fermat sozinho pouco confiável

• Teste de Miller-Rabin

  • O Miller-Rabin se baseia no mesmo princípio do teste de Fermat, mas é usado como um algoritmo probabilístico de primalidade mais forte
  • A implementação separa potências de 2 na forma n-1 = 2^s × d e então verifica várias condições
  • a^d = 1 mod n
  • ou, para algum 0 <= r < s, a^(2^r × d) = n - 1 mod n
  • Em testes com 128 bits, ele encontrou um primo em cerca de 0,042 segundo, de forma semelhante ao teste de Fermat
  • O limite de erro no pior caso do Miller-Rabin é 4^-k, e para n grande a média fica em torno de 8^-k
  • Para k=10, a probabilidade média de erro calculada foi 0.000000000931323%
  • Isso foi comparado à probabilidade 2^-30, equivalente a jogar uma moeda 30 vezes seguidas e obter cara em todas
  • Em uso criptográfico real, a escolha aleatória de bases e condições adversariais exigem mais cuidado

Criando um BigInt próprio

• Os tipos inteiros padrão do Rust não permitem lidar com números suficientemente grandes acima de 64 bits, então foi necessário implementar um inteiro de precisão arbitrária (BigInt)
• Como havia a restrição de não usar uma crate externa de bigint, o BigInt também foi implementado manualmente

• Tentativa 1: array de dígitos numéricos

  • No início, foi tentado um formato que armazenava números grandes como arrays de dígitos decimais
  • Soma e multiplicação podiam ser implementadas como contas feitas à mão, mas a divisão travou a implementação e a ideia foi abandonada

• Tentativa 2: array binário baseado em bool

  • A segunda abordagem armazenava o número como um array de 0 e 1
  • BigInt usava um array [bool; 2048]
  • Como multiplicar dois números de 1024 bits pode exigir até 2048 bits de espaço, foram reservados 2048 bits
  • Soma e subtração foram implementadas com um esquema de full adder
  • A multiplicação usava shift-and-add aproveitando as propriedades do binário
  • A divisão foi implementada como divisão longa binária
  • Com essa implementação, foi possível encontrar o primeiro primo de 1024 bits, mas o tempo de execução foi de cerca de 32 minutos e 44,90 segundos
  • Tecnicamente a meta foi alcançada, mas não atendia à restrição de “tempo razoável”

• Tentativa 3: chunks de byte

  • Foi percebido que cada bool no array de bool ocupa 1 byte, não 1 bit
  • [bool; 2048] usa 2048 bytes, não 2048 bits
  • Depois disso, o armazenamento foi alterado para guardar 2048 bits em um array de 256 bytes
  • Soma, subtração e multiplicação continuaram funcionando sem grandes mudanças, e a divisão foi ajustada para tratar chunks de byte como uma lista de bits
  • Com isso, o tempo para gerar um primo de 1024 bits caiu para 4 minutos e 43 segundos

• Tentativa 4: chunks u64

  • A abordagem com chunks de byte era, na prática, um BigInt baseado em dígitos com base mais alta
  • No passo seguinte, os 2048 bits passaram a ser armazenados em 32 chunks u64
  • Cada chunk funciona como um único “dígito”
  • Para armazenar o resultado da multiplicação entre dois chunks u64, foi usado u128
  • Nessa estrutura, um número de 1024 bits podia ser representado em 16 chunks u64, em vez de 309 dígitos decimais
  • O tempo de geração de um primo de 1024 bits melhorou para 60 a 90 segundos

Otimização dos gargalos

• Benchmarks simples mostraram uma diferença clara entre a implementação binária e a de chunks u64
  • a + b e a - b: 5537.35ns → 123.57ns
  • a * b: 1292283.14ns → 842.32ns
  • a / b e a % b: 733446.76ns → 44440.12ns
  • a < b e a > b: 2506.02ns → 58.91ns
• Depois disso, as otimizações se concentraram principalmente em divisão, multiplicação, operações internas do Miller-Rabin e lógica de geração de candidatos

• Divisão

  • O maior gargalo era a divisão
  • Mesmo na estrutura com chunks u64, a divisão anterior ainda fazia divisão longa um bit por vez
  • Com base no algoritmo da página 598 do Handbook of Applied Cryptography, foi implementada uma divisão longa baseada em radix
  • O método estima o “dígito” atual do quociente a partir dos 3 “dígitos” iniciais do dividendo e dos 2 “dígitos” iniciais do divisor
  • Essa implementação economizou cerca de 40.000ns por operação de divisão
  • Quando o divisor era um único chunk u64, foi criado um caso especial para realizar uma divisão longa mais direta usando u128
  • Isso ocorre com frequência no Miller-Rabin

• Multiplicação

  • A multiplicação ficou cerca de 2 vezes mais rápida ao reorganizar os loops para eliminar um BigInt usado para armazenar resultados intermediários
  • Também passou a calcular quantos chunks estavam ocupados e iterar apenas sobre os chunks diferentes de zero
  • Como o BigInt geralmente armazena números de até 1024 bits, muitas vezes metade do espaço de 2048 bits fica vazia
  • Também foram considerados métodos como Karatsuba ou multiplicação baseada em FFT, mas eram complexos demais para implementar manualmente, e a multiplicação atual já era considerada suficientemente rápida

• Otimizações internas do Miller-Rabin

  • Na implementação do Miller-Rabin, o foco foi reduzir operações custosas
  • Em vez de x = mod_exp(x, 2, n), passou-se a fazer diretamente x = (x * x) % n
  • O primeiro mod_exp() foi trocado por uma versão inline simplificada para reduzir overhead de chamada de função
  • Foi adicionado num.is_even() para evitar calcular % 2
  • d / 2 foi substituído por d >>= 1
  • += 1 e -= 1 foram tratados de forma especial com increase() e decrease()
  • Em especial, is_even() e d >>= 1 trouxeram ganhos de cerca de 70.000ns cada
  • No benchmark final, a versão otimizada com chunks u64 ficou muito mais rápida
  • a * b: 842.32ns → 295.04ns
  • a / b e a % b: 44440.12ns → 831.77ns
  • a / 2: 75121.58ns → 60.89ns
  • a % 2 == 0: 78400.87ns → 21.65ns
  • a - 1: 103.15ns → 67.54ns

O gerador final de primos de 1024 bits

• A função final primeiro lê um número aleatório de 1024 bits de /dev/urandom
  • O bit mais alto é ativado para garantir 1024 bits
  • O bit mais baixo é ativado para garantir que o número seja ímpar
• Depois disso, em vez de reler um novo número aleatório a cada tentativa, soma-se 2 ao candidato para passar ao próximo ímpar
  • increase_by_2() na maioria das vezes só precisa somar em um único chunk u64
• Antes do Miller-Rabin, é feita uma trial division com uma lista de primos pequenos
  • No código final, são usados os primeiros 1000 primos pequenos
  • Como esses primos pequenos cabem em um único chunk u64, aproveita-se o tratamento especial de divisão rápida para chunk único
• O problema pode ser tratado como embarrassingly parallel, sem necessidade de memória compartilhada nem sincronização entre threads
  • 16 threads de CPU procuram primos em paralelo, e o valor da thread que enviar resultado primeiro é usado
• Um exemplo de execução final registrou cerca de 0,086 segundo de elapsed time
  • O uso de CPU apareceu como 690%
• A média em 100 execuções foi 0.04109 ± 0.00307 segundo
  • Em média, um primo de 1024 bits foi encontrado em cerca de 40ms
  • Chamadas individuais de prime_1024bit() podem variar de cerca de 8ms até cerca de 800ms por causa da aleatoriedade
  • A execução paralela reduz essa variação ao escolher o resultado mais rápido

Código e limitações

• Todo o código e o repositório estão disponíveis no github
• Há links de discussão no hackernews e no reddit
• Essa implementação dificilmente pode ser considerada criptograficamente segura para uso real, e o objetivo não era criar uma biblioteca para criptografia, mas sim um experimento de aprendizado e implementação

[GN⁺]

Opiniões no Hacker News

• Houve algumas criptomoedas que usavam a busca por grandes números primos como parte da função de prova de trabalho, e, há uns 8 anos, dava para ganhar um bom dinheiro só com uma implementação muito rápida de teste de primalidade.
  Por um tempo fui autor e mantenedor do software de mineração do riecoin; não sei bem o motivo, acho que era simplesmente porque eu gostava de primos.
  Este texto deixou de fora a otimização número 1 para testes rápidos de primalidade, a multiplicação de Montgomery: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
  Ela é a base de implementações práticas e rápidas de exponenciação modular.
  Niall Emmart, que na época estava na academia e hoje, pelo que sei, está na Nvidia, publicou a CGBN, uma biblioteca de inteiros grandes para GPU absurdamente rápida: https://github.com/NVlabs/CGBN
  Ainda é a implementação mais rápida de exponenciação modular em lote que eu conheço e, para bancar o nerd por um instante, é de tirar o fôlego.
  Algum dia preciso escrever a história de como isso me permitiu dominar por uns 5 anos a produção de uma pequena criptomoeda. E Python inclui uma exponenciação modular bastante decente na forma de três argumentos de pow(x, y, m), que calcula x^y % m.
  Com isso, é muito fácil criar testes de primalidade de Fermat ou Miller-Rabin quando você quer implementar por conta própria, e é bem divertido. Se não quiser fazer você mesmo, mpz_probab_prime() da biblioteca gmp também é bom. O gmp é obviamente mais rápido, mas, quando se está brincando com primos grandes, é difícil superar a diversão de um teste de Fermat de duas linhas.

  • Niall também participou de uma das submissões vencedoras do ZPrize relacionadas a multiplicação multiescalar rápida.
    É algo bem próximo de exponenciação modular em lote, mas a diferença é que opera sobre curvas elípticas, não módulo um primo. Vejo isso como uma continuação do trabalho da CGBN.
    Ele fez uma boa apresentação no seminário de almoço de criptografia de Stanford no ano passado, e os slides e a gravação estão online.
    https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
    https://www.youtube.com/watch?v=KAWlySN7Hm8
  • Fico curioso para saber por que essas criptomoedas usavam funções de prova de trabalho tão personalizadas.
    Queria saber se era só uma ideia vaga de que criptografia usa primos de algum jeito, sem saber quando nem por quê, ou se havia um motivo mais profundo.
  • Troquei Perl por Python por causa de pow(x,e,mod).

• Dado um limite máximo para o intervalo de números, é simples tornar Miller-Rabin praticamente determinístico.
  Basta escolher bases que comprovadamente filtrem todos os pseudoprimos dentro daquele intervalo.
  A lista nem fica longa. Miller-Rabin é realmente poderoso.

  • Fico curioso para saber quais seriam essas bases no intervalo de números de 1024 bits.
    Não encontrei a resposta online.
  • Além disso, se você está apenas procurando primos, pode escolher um candidato que pareça primo e confirmá-lo com um teste determinístico.

• Uma linha de assembly inline simplifica a multiplicação escolar de inteiros grandes: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
  Se eu pudesse voltar no tempo e mudar uma coisa em C, colocaria o conceito de multiplicação estendida. É uma pena que Rust também não tenha isso. O suporte em hardware existe em todo lugar. O Cortex M0 nem faz divisão, mas tem multiplicação estendida.
  É código de uma implementação de RSA de brinquedo muito feia que escrevi muito tempo atrás: https://github.com/jcalvinowens/toy-rsa
  O motivo pelo qual eu conseguia me virar só com o teste de Fermat era que, se os primos não fossem de fato primos, o algoritmo não funcionaria. O teste de Fermat é rápido, e uma única criptografia/descriptografia elimina a chance extremamente pequena de que um dos dois seja um mentiroso de Fermat.
  Mas não sei se dá para provar que não existe um par de chaves RSA capaz de criptografar/descriptografar uma mensagem com sucesso usando valores de P/Q não primos. Em uma implementação real, claro que isso não seria o correto, mas nunca encontrei a resposta.

  • Curiosamente, C agora tem inteiros grandes.
    O C23 adicionou o tipo _BitInt(N) e, por exemplo, dá para usar _BitInt(1024) como um tipo de 128 bytes.
    Porém, o suporte dos compiladores é limitado. No Clang, para permitir N maior que 128, é possível passar a flag -fexperimental-max-bitint-width=N. Se N for maior que 128 e você dividir _BitInt(N), o compilador simplesmente trava, mas +, -, * funcionam como esperado.
  • Em Zig, isso é relativamente fácil.
    Há o builtin @mulWithOverflow, que retorna o resultado junto com o bit de overflow, e os inteiros vão até (u|i)65535.
    Dependendo do que você está fazendo, é possível detectar overflow e então promover para um tipo maior, ou promover primeiro e depois truncar seletivamente.
    Também há operadores separados: *| para multiplicação saturada e *% para multiplicação com wraparound. Eles podem ser usados quando você precisa dessas semânticas. Outros overflows são comportamento indefinido sujeito a checagens de segurança, então em modos de build Debug e ReleaseSafe eles causam panic.
  • Se p e q forem números de Carmichael coprimos, o RSA ainda consegue criptografar e descriptografar mensagens com sucesso.
    Porém, p*q terá fatores primos menores, tornando a fatoração mais fácil, então a segurança diminui.
  • Pelo que sei, na maioria dos compiladores C e em Rust, se você converter para um tipo maior e então multiplicar, será gerada exatamente a instrução de máquina desejada.
  • O Pretty Good Privacy(PGP) original de Philip Zimmermann, de 1994, usava apenas uma peneira que dividia por todos os primos de 16 bits conhecidos, e essa tabela era criada com a peneira de Eratóstenes. Depois disso, aplicava um teste de Fermat.

• Fico curioso para saber quanto tempo esse trabalho levou.
  Fiz multiplicação de inteiros grandes em um projeto de pesquisa na graduação e isso levou quase dois semestres. Implementei Karatsuba, Toom-Cook, FFT complexa, algumas NTTs e Schonhage-Strassen.
  Números primos são quase magia matemática. Para quem tiver interesse, A Friendly Introduction to Number Theory, do Silverman, é um excelente livro de matemática.
  A propósito, o link da página está como 4025051, não 40250519.

• Ótimo texto. Eu também escrevi recentemente um pouco de código de inteiros grandes para uma versão inicial de [0], e lembro como é frustrante transformar explicações de alto nível em artigos de matemática em operações reais.
  Só tenho uma pequena objeção.
  Se você usa todo o intervalo de u64, o número está em base 2^64, não em base 2^64-1. Cada word tem um intervalo de 0 a 2^64-1, assim como cada dígito decimal vai de 0 a 9.
  [0] https://github.com/LegionMammal978/bigfoot-sim

• Se, como na última otimização, você incrementa o número em 2 em vez de gerar um novo aleatório quando falha, isso enfraquece um pouco a segurança.
  Como os primos não são distribuídos uniformemente, há um viés para primos logo após grandes intervalos entre primos.

  • Li sobre isso durante a pesquisa.
    É um compromisso entre velocidade de execução e aleatoriedade dos primos; considerei que, se 16 threads começarem cada uma de um número aleatório e competirem para encontrar um primo, isso adiciona aleatoriedade suficiente, então optei pela velocidade.
    Se você quiser mais aleatoriedade do que velocidade, trocar +=2 por uma chamada a rng() é uma mudança simples.

• Ótimo texto e bem escrito.
  Acho que o autor quis dizer base-256, não base-255.

• Alguns números de 1 a 2 KB cabem tranquilamente no cache L1 e, mesmo que não coubessem, há megabytes ou mais de cache L2 com tempo de acesso de cerca de 3 ns.
  O texto diz que provavelmente teria ficado esperando leituras/escritas na RAM por causa de misses no cache L1, mas depois não volta a esse ponto.
  Além disso, como isto trata apenas de geração de primos, evita a maioria das armadilhas do RSA, e urandom deve ser seguro. Se o código funcionar corretamente, não há muita coisa que possa dar muito errado.
  No RSA há alguns problemas relacionados a primos fracos que devem ser evitados, mas não sei se eles são comuns o bastante para serem um problema real aqui.

• Isso me lembra um projeto do primeiro ano da faculdade, algumas décadas atrás.
  Meu parceiro de projeto, amigo e mais tarde orador da turma, teve a ideia e implementou a matemática central: criar criptografia RSA de 4096 bits.
  Lembro como a geração de primos era lenta na implementação final. Em uma workstation PA-RISC, levava cerca de 20 minutos para gerar.
  Meu amigo, que era fanático por matemática, continuou otimizando o código mesmo depois do fim do projeto, e lembro dele lendo artigos sobre testes de primalidade e implementações de matemática de inteiros grandes.
  Por exemplo, houve uma melhora enorme quando, em uma multiplicação composta, passamos a pular a multiplicação e devolver 0 se um dos números fosse 0.

  • Em hardware lento, é muito melhor gerar chaves de curva elíptica.
    Caso contrário, você espera muito tempo ou sacrifica a segurança que resistiria ao futuro.

• Entendo definir o bit mais baixo como 1. Números pares nunca são primos. Claro, 2 é a exceção.
  Mas não entendo por que também definir o bit mais alto como 1. Não sou especialista em primos nem em criptografia, mas parece que isso abre mão desnecessariamente de 1 bit de entropia. O que estou deixando passar?

  • Se o bit mais alto está sempre definido e o primo é codificado incluindo esse bit, então o primo sempre é codificado com o mesmo número de bytes.
    Codificações de bytes de comprimento variável podem causar problemas na troca de dados entre softwares diferentes se a especificação não for muito clara e bem testada.
    Veja os problemas que surgem em DHE baseado em RSA quando a chave pública do servidor tem um zero à esquerda.
  • É como gerar um número de dois dígitos.
    Se o primeiro dígito é 0, então não é um número de dois dígitos.
  • Definir o primeiro bit como 1 faz você perder 1 bit de entropia, mas garante que o primo seja grande o suficiente.
    E mais uma coisa: no RSA, você multiplica dois primos. Se um deles tiver 1024 bits, o outro, se minha memória não falha, poderia ter algo em torno de 200 bits e ainda assim alcançar o número de bits de entropia necessário para a chave.
    Então, ao deixar os dois primos com 1024 bits, você ainda ganha uma pequena folga.
  • É verdade que você abre mão de 1 bit de entropia, mas ainda restam 1022 bits.
    Parece mais seguro assim do que alguém pedir um primo de 1024 bits e ficar em dúvida se um primo de 1020 bits também serve. É como normalmente não considerarmos 00042 um número de 5 dígitos.
    Tecnicamente, a escolha ideal pode variar dependendo de onde exatamente isso será usado, mas o método do texto parece um padrão mais seguro.
  • Perder 1 bit de entropia para garantir que você não acabará criando um primo de apenas 50 bits certamente parece um compromisso bastante aceitável.