Generating a large (>8kb) key with GnuPG 2.x

A long while ago, I posted a guide on how to compile GnuPG 1.x, for Windows, to generate a large key.
This time, here is a guide on how to compile GnuPG 2.x (2.2.7 at the time of writing) to generate a large key. However, because GnuPG 2 is so hard to compile for Windows, I’ll compile it “only” for Linux. I’ll compile for Linux, but you’ll find at the end a link to another guide that covers cross-compiling on Linux for Windows. If you’re not on Linux, you can just do this in a virtual machine, it’s practical enough nowadays.

Starting remarks

Before going further, you may have noticed that the title mentions >8KB, not >4KB, even though 4092 bits is the first limit you’ll hit when trying to create a big key. This is because there is a simple solution that doesn’t require compiling if you “only” want a 8192 bits key: simply use the --enable-large-rsa flag, i.e.:

gpg --full-generate-key --enable-large-rsa

This guide might miss dependencies, as I used a Linux install that wasn’t completely new (Kubuntu 18.04, upgraded from 17.04 via 2x do-release-upgrade), although I hadn’t used it much either. Notably, I already had Kleopatra and GnuPG installed (from the distribution-provided packages). If at some points you have dependencies missing, maybe check out the list in the mini-guide there and also simply go for apt-get install gcc. Hopefully, the error messages you may encounter about missing dependencies should be helpful enough in guiding you to the right packages.

Onto the guide per se now.

Compiling

First, grab the source code for the required packages on this page:
https://www.gnupg.org/download/index.html
I needed: GnuPG, Libgpg-error, Libgcrypt, Libksba, Libassuan, nPth (surprisingly, I didn’t need Pinentry)

Compile and install everything but GnuPG. For instance, for Libgcrypt:

tar xf libgcrypt-1.8.2.bz2
cd libgcrypt-1.8.2
./configure
make && make install

(NB: you might want to also run make test)

Now extract GnuPG’s source code but don’t compile just yet. Open gnupg-2.2.7/g10/keygen.c, and there are 2 lines you need to edit in order to remove the hard-coded 4096 bits cap:
Line 1642, change:

  const unsigned maxsize = (opt.flags.large_rsa ? 8192 : 4096);

for instance into:

  const unsigned maxsize = (opt.flags.large_rsa ? 8192 : 409600);

(NB: 409600 is way too large, but it doesn’t hurt either)

Line 2119, change:

      *max = 4096;

for instance into:

      *max = 409600;

Those line numbers are given for version 2.2.7, which is the current version as I’m writing those lines. They might move around a bit in future version, see the end of this post for larger snippets.

Then you can compile and install GnuPG. The commands are similar as for the libraries we dealt with earlier, except from one tweak:

cd gnupg-2.2.7
./configure --enable-large-secmem
make
make test
make install

The --enable-large-secmem flag is what will allow GnuPG to allocate a large enough amount of memory, hence to deal with large keys without crashing.

Generating the key

Run gpg --version to make sure you’re running the compiled version, since your distribution’s version will most likely always be a bit behind (for instance, I just compiled version 2.2.7 and the version from my distribution, which I can still obtain via gpg2 --version, is 2.2.4).

Then you can move on to the key generation, as usual:

gpg --full-generate-key

(if you edited like I did, do not use the –enable-large-rsa flag, as it will still have a size limit of 8912 bits)

If you use the gpg-agent from your distribution’s installation, you’ll get a warning saying gpg-agent is older than gpg: it’s not a problem (but it could be avoided using something like killall gpg-agent && gpg-agent --daemon --pinentry-program /usr/bin/pinentry.

The key generation will take _a lot_ of time. You can speed it up by using the computer (downloading a large file, moving the mouse, typing stuff…), which will help generate entropy.

Once your key is generated, you may want to edit its preferences to make sure compression is enabled. Maybe the GnuPG I compiled didn’t have compression support, but the result was my key had “uncompressed” as the only accepted compression.

gpg --edit-key [keyID]
setpref AES256 AES192 AES 3DES SHA512 SHA384 SHA256 SHA224 SHA1 BZIP2 ZLIB ZIP Uncompressed MDC

Appendixes

Fixing “agent_genkey failed: No pinentry”

If you get an error message saying:

gpg: agent_genkey failed: No pinentry
Key generation failed: No pinentry

it means that for some reason gpg-agent failed to load pinentry. Make sure pinentry is installed (apt-get install pinentry-qt should do the trick, or downloading and compiling and installing it from GnuPG’s site, like we did for the other dependencies), then:

killall gpg-agent
gpg-agent --daemon --pinentry-program /usr/bin/pinentry

You might want to use locate pinentry first, to make sure /usr/bin/pinentry is the right path. (thanks to this ticket for pointers to this fix)

Larger code snippets

Here are longer snippets for more context:

Line 1642 is in function static int gen_rsa (int algo, unsigned int nbits, KBNODE pub_root, u32 timestamp, u32 expireval, int is_subkey, int keygen_flags, const char *passphrase, char **cache_nonce_addr, char **passwd_nonce_addr), in the following block:

  int err;
  char *keyparms;
  char nbitsstr[35];
  const unsigned maxsize = (opt.flags.large_rsa ? 8192 : 4096);

  log_assert (is_RSA(algo));

Line 2119 is in function static unsigned int get_keysize_range (int algo, unsigned int *min, unsigned int *max), in the following block:

    default:
      *min = opt.compliance == CO_DE_VS ? 2048: 1024;
      *max = 4096;
      def = 2048;
      break;

Why no ECC / Elliptic Curves?

ECC allows for much smaller keys and faster computation than RSA for an equivalent security level. For instance, AES 128 bits has roughly the same security as ECC 256 bits and RSA 3300 bits. But both RSA and ECC are weak to quantum computers and, from what I understood, a quantum computer will need to have an amount of qubits proportional to the size of the key to be able to crack it. Tada! What used to be a weakness of RSA, the key length, turns out to be (kind of) a strength.

This is why I’m still generating an RSA key and not an ECC one. Hopefully, next time I renew my key, I’ll have a post-quantum option.
Sorry for not digging a bit more into details here, I’m redacting this from memory, as struggling with GnuPG’s compilation and writing the rest of this post drained me more than I expected.

Update (2018-08-12): I randomly bumped into a paper titled Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms, and it gives some interesting figures, notably solving a 256 bits Elliptic Curve Discrete Logarithm Problem (ECDLP) it would take 2330 qubits, vs 4719 qubits for a 521 bits ECDLP, 6146 qubits for a 3072 bits RSA and 30722 qubits for a 15360 bits RSA. So yup, definitely worth sticking to 8kb+ RSA in my opinion.

Why don’t we also change SECMEM_BUFFER_SIZE?

A link I mentioned earlier suggests increasing SECMEM_BUFFER_SIZE. I suspect this would allow creating even larger keys without running into memory allocation failures. However, this would also allow you to create keys so big that only your modified GnuPG can handle them. I don’t think that’s an acceptable option, but if you really, really want a huge key and don’t care if it’s hard to use practically, I suppose you can go ahead and increase SECMEM_BUFFER_SIZE.

Update (2019-01-24)

I just found this nice guide explaining how to cross-compile GnuPG on Linux for Windows. I tried it and it worked nicely. I still didn’t need to compile pinentry, nor ntbTLS. Zlib is optional too, but if you don’t compile it, your build will only have support for uncompressed data. I didn’t find how to support bzip2 (didn’t really look hard though, as my only interest was in making a build for exporting my key, not for daily use).
An important note if you want to play around with big keys: in order to successfully export my 16kb private key, I had to use both the customized gpg.exe and gpg-agent.exe