We describe two encoding methods: EMSA-PSS, for signing with appendix, and EMSR-PSS, for signing with message recovery. These encodings are appropriate for signatures based on the RSA or Rabin/Williams primitive. The methods are as simple and efficient as the methods in the current P1363 draft (based on X9.31 and ISO 9796), but they have better demonstrated security. In particular, treating the underlying hash function as ideal, EMSA-PSS and EMSR-PSS give rise to provably-secure schemes: the ability to forge implies the ability to invert the underlying trapdoor permutation. In fact, when the underlying primitive is RSA, the schemes are not only provably secure, but are so in a tight way: the ability to forge with a certain amount of computational resources implies the ability to invert RSA (on the same size modulus) with essentially the same computational resources.

Click Here to download this article