Generating standard DSA signatures without long inversion

We show how the generation of a random integer k modulo q and the subsequent computation of k-1 mod q during the signature phase of the NIST digital signature algorithm (DSA) can be replaced by the simultaneous generation of a pair (k,k-1mod q). The k generated by our method behaves as an unpredictable integer modulo q that cannot, as far as we know, be efficiently distinguished from a truly randomly generated one. Our approach is useful for memory-bound implementations of DSA, because it avoids modular inversion of large integers. It is different from the inversion-free but non-standard method from Naccache et al., (1994), thus avoiding possible patent issues and incompatibility with standard DSA signature verification implementations. Another application of our method is in the `blinding' operation that was proposed by Ron Rivest to foil Paul Kocher's timing attack on RSA, or in any other situation where one needs a random number and its modular inverse