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–1 mod 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 [10], 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.