# Are there security issues with discrete logarithm keys not being uniformly distributed?

Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted $q$ here). For instance IEEE P1363 and FIPS 186-3 both specify this range for DL private keys. Is it a problem if the key is not uniformly chosen from this range?

One possibility would be choosing a random integer of $k=\log_2(q)$ bits and reduce it mod $q$. In this case, the private key would be more likely to be in the range $[1,2^k-q]$ than otherwise. Another situation where this would occur is if the implementation fixes a top bit, for instance repeatedly generating $k$-bit integers until one less than $q$ is generated). So the attacker knows the key is not in the range $[1...2^{k-1}]$.

How much of an advantage do attackers gain when key generation techniques like these are used? Obviously the total key space is reduced, but is there a reduction in security beyond that? For instance is a DSA key with 160 bit $q$ and $x$ fixed to being 159 bits easier to break than a DSA key with 159 bit $q$ and $x$ fully random?

For a group with $N$ elements, where the private key is chosen uniformly, the best generic algorithms work with cost $O(\sqrt{N})$; so with a 160-bit group you have security $2^{80}$. If the private key is not chosen uniformly, then the generic algorithm can be adjusted to take that into account: ultimately, this is equivalent to reducing $N$. In your examples, the "equivalent" $N$ is no smaller than $q/2$, so you reduce your security by no more than a $\sqrt{2}$ factor: not really worth worrying.
However, in (EC)DSA signature generation, a new value (called $k$ in FIPS 186-3) must be generated modulo $q$ for each signature; it is sometimes called a "transient private key". Contrary to the private key $x$, the value $k$ MUST be generated uniformly. For instance, if $k$ is chosen by selecting a sequence of random bits of length one less than the length of $q$, or if $k$ is selected by taking a sequence of random bits of the same length than $q$ and reducing it modulo $q$, then the private key $x$ can be reconstructed by observing many signatures and total cost $2^{63}$, which, while still big, is substantially lower than the expected $2^{80}$. This was found by Bleichenbacher in 2001; I am not sure it was formally published anywhere (Vaudenay talks of it as a "private communication"). The problem here is not in the discrete logarithm per se, but in how $k$ and $x$ are used in the computation of $s$ (the second half of an (EC)DSA signature).
The current FIPS 186 (FIPS 186-3) fixes that issue by generating a bit sequence at least 64 bits longer than $q$, then reducing it modulo $q$ (this makes the bias small enough to be unimportant). In X9.62-2005 (the ECDSA standard), they simply generate bit sequences of the length of $k$ and start again if this yields a value which does not lie between $1$ and $q-1$.
Either way, for a properly secure (EC)DSA signature generation, you must have a way to generate reasonably unbiased $k$ values; hence, you can use the same generator for producing the private key $x$.