How does the "biased-$k$ attack" on (EC)DSA work?
Nguyen and Shparlinski detail the method in The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces. I'll largely follow the notation in that paper.

The idea is to convert the determination of a private key from biased $k$ nonces in several ECDSA signatures into instances of the hidden number problem (HNP), and then solve the HNP as a reduction to the closest vector problem. 

So you collect a lot of signatures and construct a lattice out of them, and reduce that lattice using LLL or BKZ, and then you can extract the private key from the reduced basis vectors.



Estimated computational effort required

I tested this with a hand-crafted LLL Python implementation (it's so slow it surely must constitute an upper bound in performance...) running on a Ubuntu 16.04 VM with 2GB RAM, and I have the following sample runs:


96-bit bias, 5 signatures: (failed) 31 seconds
64-bit bias, 10 signatures: (success) 4 minutes
32-bit bias, 12 signatures: (success) 12 minutes
16-bit bias, 17 signatures: (success) 49 minutes
8-bit bias, 19 signatures: (failed) 79 minutes
8-bit bias, 21 signatures: (success) 244 minutes
8-bit bias, 20 signatures: (success) 177 minutes


I stopped there.  Nguyen and Shparlinski were apparently able to recover the secret key with only 3 bits of bias with 100 signatures and think that recovery is possible with only 2 bits being known. 



More problem details and setup

So let's say you know the low $\ell$ bits of $k$. (This paper describes one way of recovering those bits.) Then you can write $k$ as

$$k = a + 2^\ell b$$

In other words, you know $a \in [0, 2^\ell -1]$. For simplicity, let $a = 0$. Then the equation for $s$ in the ECDSA signature $(r,s)$ becomes

$$s = (h + rx) \cdot (2^\ell b)^{-1}$$

where $h$ is your hashed message and $x$ is your private key, and everything is modulo $q$, the order of your base point. Rewrite this as

$$xr \cdot (2^\ell s)^{-1} = -h \cdot (2^\ell s)^{-1} + b$$

Define $t \equiv r\cdot (2^\ell s)^{-1}$ and $u \equiv -h \cdot (2^\ell s)^{-1}$ and you have

$$xt = u + b$$

Remembering that $0 \lt b \lt q/2^\ell$, you have

$$xt - u \lt q/2^\ell$$

So this is basically the HNP. $b$ is smaller by a factor $1/2^\ell$ than $x$,$t$, and $u$, so approximate this equation:

$$xt - u \approx 0 \longrightarrow xt - u - jq \approx 0$$

since everything is mod $q$. So first collect $n$ signatures, giving you several tuples of $t_i$, $u_i$, and $j_i$, and you can construct a matrix out of basis vectors:

$$ \begin{pmatrix}
q &amp; 0 &amp; 0 &amp; \cdots &amp; 0 \\
0 &amp; q &amp; 0 &amp; \cdots &amp; 0 \\
\vdots &amp; \vdots &amp; \vdots &amp; \ddots  &amp; \vdots \\
0 &amp; 0 &amp; 0 &amp; \cdots &amp; q \\
t_0 &amp; t_1 &amp; t_2 &amp; \cdots &amp; t_n \\
u_0 &amp; u_1 &amp; u_2 &amp; \cdots &amp; u_n \\
\end{pmatrix}
$$ 

(The first $n$ rows contain all zeroes and one $q$, one for each of the unknown $j_i$.) This is an $(n+2) \times n$ matrix. Now let $T \equiv (t_0, t_1, \cdots, t_n)$ and $U \equiv (u_0, u_1, \cdots, u_n)$. Then the short vector of interest, $X$ is going to be something like 

$$U - xT + \text{(other stuff)}$$

You can modify your matrix to include "sentinel values" $s_T$ and $s_U$ so that you can identify $X$; if you see a reduced vector $T'$ with $s_T$ as its last slot, most likely you'll see the next-to-last entry containing $-x\cdot s_U$ from which you can recover $x$. Disclaimer: I saw this trick in a cryptopals problem first and makes things way easier than just guessing. The modified matrix looks like:

$$ \begin{pmatrix}
q &amp; 0 &amp; 0 &amp; \cdots &amp; 0 &amp; 0 &amp; 0\\
0 &amp; q &amp; 0 &amp; \cdots &amp; 0 &amp; 0 &amp; 0\\
\vdots &amp; \vdots &amp; \vdots &amp; \ddots  &amp; \vdots  &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 0 &amp; \cdots &amp; q &amp; 0 &amp; 0\\
t_0 &amp; t_1 &amp; t_2 &amp; \cdots &amp; t_n &amp; s_T &amp; 0 \\
u_0 &amp; u_1 &amp; u_2 &amp; \cdots &amp; u_n &amp; 0 &amp; s_U\\
\end{pmatrix}
$$ 

Now you can use an implementation of LLL from NTL or fplll, find the sentinel value, and extract $x$.