1
$\begingroup$

I am making a messaging system where users are identified by their public keys. It doesn't matter which friendly username they have, so I'm not going to prompt them to choose one. Each user will have a directory that will get their messages saved to, so it would be nice if the directory that belongs to them has a short name. I.e. I can't create a very large directory name by using the entirety of their public keys (might be too long and hit file system limits).

I was considering to use, say, sha3_244(their_public_key) and consider that hash for their home directory names.

But then I thought, how about I take the 1st 50 bytes of their public key, base32 encode it, and use this instead of the sha3_244 checksum? Should I be worried about collisions?

Improve this question
$\endgroup$
1
  • $\begingroup$ If you know the birthday attack for collisions; with a 50% probability that you will have a collision if you hash $2^{122}$ public key. Note: use all of the public keys, instead. If year fear of this non-zero collision use uuid, or use CS hash collision resolutions. $\endgroup$
    – kelalaka
    Aug 25, 2020 at 21:28

1 Answer 1

Reset to default
4
$\begingroup$

Should I be worried about collisions?

If these are RSA keys, yes, at least, if people find it in their interest to collide with someone else.

It is entire practical to generate an RSA key where to top 400 bits of the modulus are some specified value. Since you use those 400 bits as your identifier, then that means the user can pick any identifier they want, for example, the same identifier as another user.

Whether that is a concern depends on whether users would actually gain an advantage.

As for how you would generate a (say 2048 bit) RSA key with the top 400 bits being the value $X$, here's what you do:

  • Select your 1024 bit prime $p$ as usual

  • Select a prime $q$ from the range $2^{2048-400}X / p < q < 2^{2048-400}(X+1) / p$; there will be plenty of primes in a range that large.

It's easy to see that $pq$ would be a valid RSA modulus with the top 400 bits being the value $X$.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ And collision testing is easy by the GCD them all $\endgroup$
    – kelalaka
    Aug 25, 2020 at 23:18
  • 2
    $\begingroup$ @kelalaka: I have no idea what the GCD attack has to do with the above RSA generation process... $\endgroup$
    – poncho
    Aug 26, 2020 at 3:01
  • $\begingroup$ Thanks. Side question: any recommendation? Should I use entire base62-encoded public key as file name (or partially directory names to avoid file system's length limitations)? Or should I rather use a hash? E.g. sha3_244? $\endgroup$
    – caveman
    Aug 26, 2020 at 4:31
  • $\begingroup$ If the generator is not good enough, it may hit the same prime again? $\endgroup$
    – kelalaka
    Aug 26, 2020 at 4:44
  • 1
    $\begingroup$ @caveman: I'd suggest the hash (you could use the entire public key, but that'd be large...) $\endgroup$
    – poncho
    Aug 26, 2020 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.