4 ms·
This is a good post, kudos on writing it up so quickly! In fact, the first thing I thought of when I read this post on HN was, "Well why not use a pseudorandom
by dsacco 9y ago
This is a good post, kudos on writing it up so quickly! In fact, the first thing I thought of when I read this post on HN was, "Well why not use a pseudorandom permutation instead of a pseudorandom function, this way we efficiently fill all pixels without first checking if they're red?"
Being that a feistel network is a pseudorandom permutation, this fulfills the need (and in my opinion, even more elegantly than a LFSR). For even better performance you could use AES as the PRF, especially if users have AES-NI instructions available for acceleration. Then use a basic Feistel network for the PRP.
- 0x4a42 9y ago>This is a good post, kudos on writing it up so quickly! Wait... what? It took him 25 years! ;)
- antirez 9y agoThanks! Exactly my thought indeed. Probably now that many people are aware of crypto primitives, permutation boxes and other related tools it is an immediate thought to have, but potentially back then when the game was written it was not so obvious.
- dsacco 9y agoAbsolutely. One of my recent research interests in cryptography has been identifying ways to make pseudorandom permutations faster and using them outside of typical cryptographic contexts. I'm happy to see that you use them in Rax. They map very well to a lot of data structure problems in networking, not just encyption (i.e. assigning IDs to users).