Sean:
A receiving agent SHOULD be able to verify signatures with keys of any size
over 512 bits.
This is asking for denial of service attack. What if someone sends a
certificate that contains a 64Kbit value claiming to be a public key
and a blob of random bits claiming to be a signature? The amount of
time to check the signature (and probably find that it is not valid)
is onerous.
Today, I cannot imagine someone making use of a public key larger
than 8192 bits. Double that it you want to be very future proof.
Russ