Generalize ECDSA solver to work for arbitrary MSB/LSB

[ellshea]

I'm a student of Nadia's and changed the ECDSA-HNP code to work for arbitrary (not necessarily 0) leaked MSBs or LSBs. The main changes are the lattice construction, predicate checks, and input formatting. The CLI still works the same.

The zero-MSB sampling code lives on in the ecdsa.sample_msb_zero() function, which is still the default for benchmarking, estimation, etc. It is really only the solve functionality that I changed, although the sampling could be changed elsewhere if it's useful.

Let me know if anything in particular deserves more explanation or documented tests. We thought it'd be useful enough to merge so people don't have to work out the lattice changes themselves.

[malb]

Looks great. Two things:

• Can you change all the occurrences of klen to nonce? I'm in favour of the rename you've done but we should be consistent throughout.
• Can you add an explicit test for the different configurations MSB/LSB?

Then if @factorable is happy, I'm happy.

[ellshea]

Yes, I'll add those tests.

Regarding klen and nonce, my intention was to distinguish between the full nonce (nonce and nlen) and the unknown part of the nonce (k and klen). The distinction did not matter when the known bits were all MSB zeroes.

I agree it is a bit confusing. k usually refers to the nonce in ECDSA but it also refers to the HNP secret in the paper, which are now two separate things. The way I set it up was such that for MSBs, nonce = MSBs + k and for LSBs, nonce = 2^t * k + LSBs. This seemed to be a decent way to change as little as possible and ensure that the past experiments over k still refer to the same thing.

[malb]

Thanks for explaining, should this paragraph be added somewhere perhaps?