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


Published in:
Advances in Cryptology - ASIACRYPT'96 International Conference on the Theory and Applications of Cryptology and Information Security. Proceedings, 57 - 64
Presented at:
Advances in Cryptology - ASIACRYPT'96 International Conference on the Theory and Applications of Cryptology and Information Security. Proceedings, Berlin, Germany
Year:
1996
Keywords:
Laboratories:




 Record created 2010-06-24, last modified 2018-03-17

Postprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)