Page MenuHome GnuPG

interoperability of PGP RSA keys
Testing, LowPublic

Description

It seems that some implementation generates RSA key with p > q.
This is not good for GnuPG.

At least, it is better that libgcrypt's checking secret key implements this check.

Event Timeline

Du we have any information on whether the CRT is used and whether u et al. is also wrong? For example due to an OpenSSL generated key?

CRT is used with GnuPG. In libgcrypt, pk_sign and pk_decrypt don't require P, Q, and U in a key (it's optional), but pk_test_key does.

U is needed to update when we swap the values of P and Q.

I briefly checked existing standards, but I can't find any definition about which should be smaller. It seems that p > q in OpenSSL and OpenSSH.

Here is a patch to modify the values when importing a key:

diff --git a/agent/cvt-openpgp.c b/agent/cvt-openpgp.c
index 2dd5f8b04..c868b25c2 100644
--- a/agent/cvt-openpgp.c
+++ b/agent/cvt-openpgp.c
@@ -141,6 +141,19 @@ convert_secret_key (gcry_sexp_t *r_key, int pubkey_algo, gcry_mpi_t *skey,
     case GCRY_PK_RSA:
     case GCRY_PK_RSA_E:
     case GCRY_PK_RSA_S:
+      /*
+       * We make sure p < q, since libgcrypt requires that.  If not,
+       * swap the values of p and q, and recalculate u.
+       */
+      if (gcry_mpi_cmp (skey[3], skey[4]) > 0)
+        {
+          gcry_mpi_t u = gcry_mpi_new (0);
+
+          gcry_mpi_swap (skey[3], skey[4]);
+          gcry_mpi_invm (u, skey[3], skey[4]);
+          gcry_mpi_release (skey[5]);
+          skey[5] = u;
+        }
       err = gcry_sexp_build (&s_skey, NULL,
                              "(private-key(rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))",
                              skey[0], skey[1], skey[2], skey[3], skey[4],
gniibe mentioned this in Unknown Object (Maniphest Task).Mon, Mar 16, 7:01 AM

existing standards

Sorry, my scope was only for the RSA standards itself (like the one under NIST), not covered many uses of the RSA crypto system.

In OpenPGP specification, November 1998, RFC2440 section 5.5.3. Secret Key Packet Formats requires (p < q).
This could be a reason why we haven't encountered this problem until today.

For OpenSSH, ssh-agent spec. defines p, q, and qInv.
FIPS has: FIPS 186-5 and SP 800-56Br2.

Those don't specify the relationship between p and q, but qInv could be somehow more natural when p > q.

I found that gpg-agent's emulation of ssh-agent has ssh_key_modifier_rsa to handle this issue. https://dev.gnupg.org/source/gnupg/browse/master/agent/command-ssh.c;47bab26daf035ffdce97e4957bdb6ad12dbea506$1378?as=source&blame=off

BTW, LibrePGP also demands p < q in "Algorithm-Specific Part for RSA Keys".

I sent a patch to gcrypt-devel mailing list for the preparation of the change of RSA secret key checking.
If enabled, wrong RSA secret key (wrong means: under the Libre/OpenPGP specification) is rejected at import when gpg-agent calls gcry_pk_test_key.

See: https://lists.gnupg.org/pipermail/gcrypt-devel/2026-March/006055.html

Setting to low because this has never been a problem in the last 30 or 35 years. A check to help pinpointing bad keys is however a good idea.

gniibe mentioned this in Unknown Object (Maniphest Task).Mon, Mar 23, 3:43 AM

I retract my patch in T8171#215603

It somehow "works" (in limited use case), but it's not good silently swap the values without user interaction.
For example, exporting secret keys will have another problem.

It's better to reject the key.

While I pushed the change of libgcrypt, I'd like to apply following change to GnuPG.
This is more kind than GPG_ERR_BAD_PASSPHRASE by gcry_pk_testkey failure.

diff --git a/agent/cvt-openpgp.c b/agent/cvt-openpgp.c
index 2dd5f8b04..202623426 100644
--- a/agent/cvt-openpgp.c
+++ b/agent/cvt-openpgp.c
@@ -141,6 +141,14 @@ convert_secret_key (gcry_sexp_t *r_key, int pubkey_algo, gcry_mpi_t *skey,
     case GCRY_PK_RSA:
     case GCRY_PK_RSA_E:
     case GCRY_PK_RSA_S:
+      /*
+       * Check the condition if p < q, since libgcrypt requires that.
+       * LibrePGP/OpenPGP also requires this condition.
+       */
+      if (gcry_mpi_cmp (skey[3], skey[4]) >= 0)
+        /* Note that it may come here by bad passphrase input.  */
+        return GPG_ERR_BAD_SECKEY;
+
       err = gcry_sexp_build (&s_skey, NULL,
                              "(private-key(rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))",
                              skey[0], skey[1], skey[2], skey[3], skey[4],
gniibe mentioned this in Unknown Object (Maniphest Task).Mon, Mar 30, 2:35 AM