A lookup table for the discrete log in secp265k1
Clone or download
Latest commit 5be551b Jan 1, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
secp256k1 @ 1e6f1f5 Initial release Jan 1, 2019
.gitignore Initial release Jan 1, 2019
.gitmodules Initial release Jan 1, 2019
Makefile Initial release Jan 1, 2019
README.md Initial release Jan 1, 2019
create-index.c Initial release Jan 1, 2019
enumerate-and-write.c Initial release Jan 1, 2019
hashes-to-r.py Initial release Jan 1, 2019
keep-low-32.c Initial release Jan 1, 2019
lookup.c Initial release Jan 1, 2019
mk-lookup-table.py Initial release Jan 1, 2019
multiple-of-g.c Initial release Jan 1, 2019
split-first-byte.c Initial release Jan 1, 2019
test.sh Initial release Jan 1, 2019

README.md

secp265k1 lookup table

This directory contains code to create a lookup table for the discrete log in the secp265k1 curve.

It was written for a small part of the calculations in the paper Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies by Joachim Breitner and Nadia Heninger.

We share this code here as is, for archival reasons and in case it is useful for anyone else. But note that this is not polished production-ready code. If you have questions, please do not heistate to contact Joachim Breitner mail@joachim-breitner.de.

Installation

git clone --recursive https://github.com/nomeata/secp265k1-lookup-table
make

Also install bsort from https://github.com/pelotoncycle/bsort.

Also run pip3 install fastecdsa.

Speed advice

The lookup program loads all files using mmap, and does lots of random accesses. This is only performant enough if the files are indeed in memory. It does wonder to load them into memory first, e.g. using vmtouch -t -v /path/to/tables with the vmtouch tool.

Example usage

This is for a local test run, which finds n×G with $n<2^24$:

  • Generate a list of the least significant 64 bits, up to 2^20:

    ./enumerate-and-write test/lsb-20-%02hhx-%d.bin 19 0
    ./enumerate-and-write test/lsb-20-%02hhx-%d.bin 19 1
    

    You can parallize this. The filenames encode the most significant byte.

  • Combine the files from the different runs:

     for i in $(seq 0 255); do
       cat test/lsb-20-$(printf "%02hhx" $i)-*.bin > test/lsb-20-$(printf "%02hhx" $i).bin
       rm test/lsb-20-$(printf "%02hhx" $i)-*.bin
     done
    
  • Sort each file:

     for i in $(seq 0 255); do
     bsort -k 8 -r 8 lsb-20-$(printf "%02hhx" $i).bin
     done
    
  • Create an index for each file, for faster lookup:

     for i in $(seq 0 255); do
     ./create-index test/lsb-20-$(printf "%02hhx" $i).bin 24
     done
    
  • Since the first 8 bits are addressed by the file, and the next 24 bit by the index, we only need to keep the low 32 bits of each nonce:

     for i in $(seq 0 255); do
     ./keep-low-32 test/lsb-20-$(printf "%02hhx" $i).bin
     rm test/lsb-20-$(printf "%02hhx" $i).bin
     done
    
  • Generate a lookup table for for nonces with $n<2^10$. Again, this can easily be parallized.

    ./mk-lookup-table.py 9 $((0 * (1<<9)))
    ./mk-lookup-table.py 9 $((1 * (1<<9)))
    mv small-k-rs-9-*.bin > test/small-k-rs-10.bin
    rm small-k-rs-9-*.bin
    bsort -k 32 -r 36 test/small-k-rs-10.bin
    
  • Put the values you want to lookup into a binary files. You will have to code that up yourself. You can look at hashes-to-r.py for inspiration. For testing, you can generate some random values using

    ./multiple-of-g --binary \
      $(for n in $(seq 0 1023); do echo $(( (RANDOM + RANDOM * (1<<16) + RANDOM * (1<<32)) % (1<<26) )); done) \
      > r-values.bin
    
  • Look up the powers, brute-forcing values up to n<2^24:

    ./lookup 24 lsb-20-%02hhx.bin 20 24 small-k-rs-10.bin 10 r-values.bin r-to-k.bin