Se você usa o gnupg via linha de comando já deve ter visto uma mensagem parecida com esta:
Não há bytes aleatórios suficientes. Por favor, faça algum outro trabalho para que o sistema possa coletar mais entropia! (São necessários mais 275 bytes)
Como computadores não geram número verdadeiramente aleatórios o gnupg usa situações que são verdadeiramente aleatórias. Como por exemplo a posição do mouse em um dado tempo. Ou seja, usa elementos que variam de forma caótica no tempo.
Se você está num terminal ou em modo texto há menos elementos caóticos no seu computador e eventualmente o gnupg pode não ter bytes suficientes para gerar uma chave. O gnupg não retorna um erro ou falha por que ele vai esperar que se gere os bytes faltantes. E saiba isso leva muito tempo.
Para contornar o problema eu googlei a melhor solução é usar o rngd. Um serviço que é capaz de gerar entropia suficiente.
Para instala-lo no ubuntu:
apt-get install rng-tools
No fedora:
yum install rng-utils
Para executar:
rngd -r /dev/urandom
assim obtemos a linda saída do gpg:
gpg: Gerando uma chave...
+++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++.++++++++++++++++++++++++++++++..++++++++++++++++++++..+++++++++++++++>++++++++++.+++++
+++++++++++++++.++++++++++++++++++++.++++++++++.+++++.+++++++++++++++++++++++++++++++++++.+++++.++++++++++.++++++++++.++++++++++++++++++++.>+++++......+++++^^^^
gpg: done
Assim, antes de você usar o gnupg (gpg) inicie o rngd, use o gpg e por fim mate o rngd (não há mal algum deixar rodando).