Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
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
Serge Vaudenay, Laurane Chloé Angélina Marco, Abdullah Talayhan