We show how to construct a practical secure signature padding scheme for arbitrarily long messages from a secure signature padding scheme for fixed-length messages.
This new construction is based on a one-way compression function respecting the division intractability assumption. By practical,
we mean that our scheme can be instantia- ted using dedicated compression functions and without chaining. This scheme also
allows precomputations on partially received messages. Finally, we give an instantiation of our scheme using SHA-1 and PKCS
#1ver. 1.5.
Keywords Digital signature - padding scheme - provable security - atomic - primitive - RSA - hash-and-sign - division intractability - smooth numbers
This work was done while visiting Gemplus Montréal R&D Center.