* Functions look "mathematical". Variables are immutable, so "x = x + 1" doesn't make sense just like in math
* Nice binary matching syntax like <<Result:256/little-unsigned-integer-unit:1>>. Can even manipulate arbitrary bit strings that don't necessarily end on a byte boundary
This is a timely paper. A question for those who are crypto/math experts - I wrote a libsodium-based keygen for ed25519 pairs trying to generate a vanity public key.
Is there a chance that a given byte series will never show up in an ed25519 pub-key due to how this curve intrinsically works? My keygen is looking at the first 5 bytes, which is supposedly a (1 : 256^5) chance per key = (1 : 1,099,511,627,776).
Is my math right and 1:trillion really just could take weeks/months (current rate ~25-30B keys/day) or have I been running this keygen with no hope?
1. Hash the private key
2. "Clamp" the result
3. Multiply by the base point
Clearly step 1 will give you an equal chance of any 5-byte prefix, so the question is whether steps 2 and 3 preserve that entropy.
The clamping in step 2 does two things: it clears the 3 least-significant bits (making the value divisible by 8) and it sets the 2 most-significant bits to 01. So we've lost 5 bits of entropy here.
Finally, step 3 multiplies the value by the base point. The base point is a pair of large (255 bit) numbers. Multiplying by it probably does not appreciably reduce entropy, but I could be wrong here.
So I think your brute-forcing is probably not in vain. However, I would certainly start by trying to generate all possible 2-byte prefixes, 3-byte prefixes, etc. to gain some confidence there no "unreachable" prefixes.
EDIT: I was able to verify that all 2-byte and 3-byte prefixes are reachable. I strongly suspect that that all 5-byte prefixes are reachable as well.
I would certainly start by trying to generate all possible 2-byte prefixes, 3-byte prefixes, etc.
OK great, I did try that to get some insight as to whether various 2/3/4-byte series at different index positions would show up... and they did. The relative lack of results by adding that 5th byte had me concerned, but figured it's due to the exponentially-decreasing odds.
I'll have to read more on what you mean by #2/3. Clamping / bit entropy and the more intricate math is where I start to get lost. This seems like a good resource:
Doesn't the public key have twice the size of the private key that it's derived from? (I remember something about that, but I'm not sure.) If so, yes, most byte series will never appear.
Not really; both the private key (scalar) and public key (point) are encoded as 32 bytes. However, some implementations concatenate the two and refer to that 64-byte array as the "private key" -- this is simply an optimization so that the pubkey doesn't need to be re-derived each time you want to compute a signature.
The point was about public keys, not private keys. The answer then is going to sound similar, but is in fact entirely different: the public key is often specified as the X and Y coordinates of the point ("uncompressed"), but only the X coordinate and axis disambiguation is required ("compressed").
there are many times more public keys than there are 5 byte prefixes. I don't know much 25519, but there is no a priori reason to suspect his brute force won't succeed.
* It has big ints
* Functions look "mathematical". Variables are immutable, so "x = x + 1" doesn't make sense just like in math
* Nice binary matching syntax like <<Result:256/little-unsigned-integer-unit:1>>. Can even manipulate arbitrary bit strings that don't necessarily end on a byte boundary
* Has a decent crypto module https://www.erlang.org/doc/man/crypto.html