Isn't it enough to limit the range of $k$ (the random value selected
during signature generation) to values with the top bit set?
(Or--if there are too few of those--only use values with "01" in the top
bits, still leaving 2^{158} possible values?)
-a