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<sup>-1</sup> 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<sup>-1</sup>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 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
149487.PDF
openaccess
1.35 MB
Adobe PDF
921cd38f8a45e6330df46894e21c0cc6