(EC)DSA partial knowledge of nonces and existential forgery with with structured nonces There are attacks against the private key of (EC)DSA when partial knowledge of the nonces $k$ is known, e.g. least significant bits [1] or shared bits [2]. On the other hand, existential forgery with structured nonces is possible. In DSA the public key is (p,q,g,y=g^x). To forge a signature (r,s) of integer $h$ for all integers a,b != 0 set: r=(g^a y^b mod p) mod q s=r/b mod q h=a s mod q Since y=g^x mod p, the unknown nonce is $k=a + b x$ where $x$ is the private key. If $b=1, a=a'+2^l a''$ and we brute force the $l$ LSBs of $x$, we can generate efficiently many messages with known LSBs (a' + (x mod 2^l)), which appears in the favorable case the unconditional [1]. Similar existential forgery exists for ECDSA. Forgeries were tested in practice. Could this approach give subexponential algorithm for breaking the private key, possibly under other assumptions? [1] appears to be deterministic and the abstract starts: |We present a polynomial-time algorithm that provably recovers the |signer's secret DSA key when a few bits of the random nonces k (used at each |signature generation) are known for a number of DSA signatures at most linear in |log q [1] The Insecurity of the Digital Signature Algorithm with Partially Known Nonces [2] Attacking (EC)DSA Given Only an Implicit Hint