What should be needed to adapt CRY-ME/break_schnorr.py to ᴇᴄᴅꜱᴀ ?

[ytrezq]

Simple question, how the construct_matrix() function should be modified to support ᴇᴄᴅꜱᴀ ?
Also, what if the nonce is 128‒Bits long and the private key 136 bits long (with the known bits set to 1) ? Does this makes solving from a single signature impossible ?

[amossys-1]

First, I am sorry to give a response this late.
The function construct_matrix() is very specific for the case of CRY-ME where:

• the secret scalar is very short (128 bits only)
• the nonces have short entropy with a special structures (they can be deduced from 8 bytes only)

The adaptation for ECDSA should not be complicated as it is only a matter of rewriting the relation between the two elements of the signature, the nonce, private key, and the representative of the message.

If the private key is longer, then one signature might not be enough.
Without any assumption on the private key, then two signatures are sufficient.
Given a single signature and running through all $2^{64}$ possible nonces, then we should obtain as much potential private keys.
I wouldn't be surprised that knowing 64 bits of the private key would be enough using lattice techniques with a single signature.