[cryptography] Near-collisions and ECC public keys

Florian Weimer fw at deneb.enyo.de
Mon Dec 29 08:18:10 EST 2014

To check an OpenPGP fingerprint for correctness, it is sufficient (for
practical purposes) to compare the leading and trailing eight
hexadecimal digits, and perhaps a few digits in the middle.

This is not true for raw RSA keys because weak keys are in close
Hamming distance to any given reference key (I think, I haven't
verified this).  So you'd need to compare the full (n, e) pair, bit by
bit, or compare a cryptographically strong digest of them (the OpenPGP
approach, more or less).

ECC public keys are small, and a digest will not provide much of a
length reduction.  But I wonder if the digest would still make sense
to perturb the bits, so that it is not possible to create a
near-collision.  Do ECC public keys behave like RSA keys in this
regard?  Does this depend on the chosen encoding format?

More information about the cryptography mailing list