Não consigo encontrar muitas informações sobre as especificidades da geração de chaves PGP envolvidas no Thunderbird. O software é bastante antigo e coisas como "Isso pode levar vários minutos" ou algo que leva menos de um segundo, estão me fazendo levantar uma sobrancelha.
Enquanto o software está sendo atualizado com freqüência, o algoritmo de geração de chave ainda é seguro para ele, pois não importa quão seguro seja o PGP se a geração de chave for fraca e previsível.
Crypto.SE ou Security.SE seria capaz de fornecer uma resposta muito melhor do que eu (não trabalho com criptografia), mas:
Em relação a implementações específicas, se você estiver usando um Thunderbird recente com suporte OpenPGP integrado (que na verdade é bastante novo), provavelmente ele foi escrito para usar a função keygen RSA fornecida pelo NSS, a biblioteca SSL/TLS usada pelo Thunderbird e Firefox. Ou seja, a operação não é realmente específica do PGP, e o aplicativo só precisa colocar a chave já gerada no envelope correto - não há motivo para carregar algum código de geração de chave específico do PGP de décadas atrás.
(Embora, mesmo que fosse, isso não significa que o código não tenha sido tocado em décadas, por exemplo, o próprio NSS com suas raízes Netscape é literalmente uma das bibliotecas SSL mais antigas já escritas.)
Por outro lado, está, se bem me lembro, carregando o código da interface do usuário que fazia parte do addon Enigmail; eles apenas o integraram ao aplicativo e substituíram o back-end. Algumas das mensagens do início dos anos 2000 poderiam ter permanecido.
Mas, no geral, existem algumas razões pelas quais é rápido:
Um algoritmo de geração de chave não é como algoritmos de hash de senha; sua força não depende de ser lento. A geração de uma chave RSA costumava ser lenta porque as CPUs eram lentas e encontrar números primos realmente demorava. Mas tanto a geração de números aleatórios quanto os vários testes de primalidade ainda alcançam exatamente a mesma coisa exatamente no mesmo nível de segurança, independentemente de quanto tempo demore.
Isso não varia muito entre os diferentes programas – você pode testar qualquer ferramenta que lide com chaves RSA e elas devem fornecer resultados idênticos. Para usar um tamanho de chave um pouco exagerado como exemplo, algo como
openssl genrsa 8192(com OpenSSL) oucerttool -p --bits=8192(GnuTLS) leva mais de um minuto em uma CPU Celeron ~2005, mas apenas cerca de 8 segundos em um Xeon ~2012.(O OpenSSL também é "bastante antigo", quase tão antigo quanto o NSS, mas é usado diariamente para criar a grande maioria dos certificados TLS e seus pares de chaves na web.)
Os geradores de números aleatórios simples ficaram realmente melhores (com novos algoritmos que são mais rápidos e melhor compreendidos), mas mais importante, eles também estão mais prontamente disponíveis - no passado, o programa tinha que trazer seu próprio RNG e cuidar da coleta entropia de fontes duvidosas (como "Entropy Gathering Daemon" em Unixes, ou as coisas "agite seu mouse por 10 segundos" que o PuTTYgen ainda faz hoje), hoje em dia cada sistema operacional fornece um CSPRNG que o aplicativo pode chamar instantaneamente para dados aleatórios sempre que necessário .
Agora temos algoritmos de chave assimétrica mais difundidos que não são baseados em números primos enormes – gerar uma chave ECDSA, se você escolher essa opção, é feito de uma maneira completamente diferente da geração de uma chave RSA e é, de fato, por design muito mais rápido que o RSA. (As chaves também são muito mais curtas no mesmo nível de segurança.)