[HN Gopher] A Tour of Curve25519 in Erlang [pdf]
       ___________________________________________________________________
        
       A Tour of Curve25519 in Erlang [pdf]
        
       Author : tosh
       Score  : 74 points
       Date   : 2021-12-17 13:37 UTC (9 hours ago)
        
 (HTM) web link (research.nccgroup.com)
 (TXT) w3m dump (research.nccgroup.com)
        
       | kirse wrote:
       | 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?
        
         | nemo1618 wrote:
         | The process for generating a pubkey is:                   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.
        
           | kirse wrote:
           | _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:
           | 
           | https://www.jcraige.com/an-explainer-on-ed25519-clamping
           | 
           | Thanks for giving me some hope!
        
         | marcosdumay wrote:
         | 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.
        
           | nemo1618 wrote:
           | 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.
        
             | saurik wrote:
             | 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").
        
           | ouid wrote:
           | 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.
        
       | rdtsc wrote:
       | Erlang seems to work well here.
       | 
       | * 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
        
       ___________________________________________________________________
       (page generated 2021-12-17 23:01 UTC)