RSA Signing Key Rotation

Question

I understand the details of RSA encryption/decryption in that a public key can be distributed in the clear since all it can really do anyway is encrypt data. I also understand that this public key can be signed with a different public/private key pair. This is great to validate that the key came from a reliable source and you are not encrypting your sensitive data with with a malicious public key so that an attacker could decrypt with the paired malicious private key. I also understand that it is important to rotate public encryption keys since after a number of uses, the private key becomes mathematically exposed with fewer computational cycles. What I do not understand is if you need to rotate your public signing key. It seems to me that after enough key rotations your private signing key would become exposed and then a malicious public encryption key could be signed by an attacker with the private signing key they have exploited. Issuing a new public signing key, however, becomes susceptible to a man in the middle attack. What piece of this am I missing?

Answer 1

I also understand that it is important to rotate public encryption keys since after a number of uses, the private key becomes mathematically exposed with fewer computational cycles.

Well, you understood wrong. This is a widespread myth, but myth nonetheless. Keys don't wear upon usage -- especially not signature keys. Keys used to require regular rotation, but that was back in the days before computers, when cryptographic algorithms had to be done with a pen and paper, or possibly some assembly of whirring cogs. Times have changed.

A decent signature algorithm is supposed to remain safe even if you produce a billion of billions of signatures. An algorithm which does not achieve at least that level of security is said to be "broken" and cryptographers shun it. RSA (used properly, i.e. as explained in PKCS#1) is not broken.