Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

The discrete logarithm problem can be attacked with either a specific or a generic algorithm. A specific algorithm is one that tries to exploit structural weaknesses of the specific group in which discrete logarithm is used; e.g. Index Calculus when we are talking about exponentiation modulo a big prime. Generic algorithms only use the group law and thus work on "any" group. For normal elliptic curves (excluding those which allow for an efficient pairing), no specific algorithm is known.

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 280. 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 263, which, while still big, is substantially lower than the expected 280. 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.