>I mean that 64 bits can probably be inexpensively attacked to produce first or second preimages.

Keep in mind that you would have to generate a valid keypair, or something that could be made into a valid keypair for each iteration. That fact is why PGP got along with 32 bit key IDs for so long. PGP would still be using 32 bit key IDs if it wasn't that someone figured out how to mess with RSA exponents to greatly speed up the process. Ironically, the method with the slowest keypair generation became the limiting factor.

It isn't like this is a new problem. People have been designing and using key fingerprint schemes for over a quarter of a century now.

>$ better_gpg decrypt_and_auth --sender_pubkey [KEY] --recipient_privkey [KEY]

How do you know that the recipient key actually belongs to the recipient? How does the recipient know that the sender key actually belongs to you (so it will validate correctly)?