# Are the first 4 bytes of a Ed25519 public key random?

We are using the Ed25519 signature scheme (which uses Curve25519). A key pair is generated by generating the secret key from random data and then computing the 32-byte (256-bit) public key from said secret key.

The question is about the entropy (randomness) of the public key. We currently use the first 4 bytes of the public key as a "reasonably unique" ID of the public key. We have very limited space and cannot afford more than 4 bytes. Would we improve the uniqueness of the ID if we generate it differently? For example, the ID could be generated by XOR between Bytes 0-3 and Bytes 4-7 of the public key? Or using the first 4 bytes of sha-512 of the public key. Or what?

• If you have 10k public keys, then with probability circa 1% two will share the first 4 bytes; with the probability growing sharply as you add more keys. No, there's no other way of generating 4 byte IDs that improve on this... Apr 4 '17 at 17:39
• @poncho Using the first 4 bytes of a hash over the public key cannot be worse right, or are the most significant bits perfectly distributed? Still, yeah, 4 bytes is not enough for a large number of public keys. A simple counter would be an option? > 4 billion keys... Apr 4 '17 at 22:24
• @MaartenBodewes: actually, Curve25519 is traditionally encoded in little-endian order, and so the first 4 bytes are the lower 32 bits, and so we'd expect them to look random. Apr 5 '17 at 2:52
• Ah yeah, with little endian it makes more sense :) Apr 5 '17 at 8:37
• @poncho can you be bothered to pack your first comment into an answer? :)
– SEJPM
Apr 5 '17 at 9:13

If the 32-bit ids are assigned independently, the best you can hope for with a uniform random assignment of ids is a collision probability no more than about $$n^2/2^{32}$$ where $$n$$ is the number of ids you have, if $$n$$ is small; once $$n$$ grows past $$2^{16}$$ the probability of a collision rapidly approaches 1. This is the standard birthday paradox.