Cryptography
rsa public-key signature terminology trapdoor
Updated Tue, 14 Jun 2022 16:54:38 GMT

# What is Reverse Trapdoor Function?

In wikipedia on Digital_signature:

but rather, the message to be signed is first hashed to produce a short digest, that is then padded to larger width comparable to N, then signed with the reverse trapdoor function

I could not find the term reverse trapdoor function neither by web search not here on SE, what does it mean?

## Solution

Definition of trapdoor function from Wikipedia;

A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor".

The reverse trapdoor function is just the reverse usage of it.

Normally, for encryption, we want the encryption easy but the decryption is hard without the key. Consider the RSA encryption.

In the signature, we want the reverse, hard to produce without the key - i.e. forgery, but easy to verify. Consider the RSA signature.

Consider RSA, given $$(n,e)$$ public key then $$E(m) = m^e$$ is trapdoor (actually trapdoor permutation) without the private key.

Forward usage: With the public key and $$m$$ it is easy to compute the $$E(m)$$, encrypt. But given $$c = E(m)$$ and public key it is difficult to compute $$E^{-1}(c)$$ without the private key.

Reverse usage: Given $$(n,d)$$ private key then $$S(m) = m^d$$ is the reverse trapdoor. Given $$s = S(m)$$ and public key it is easy to verify but difficult to compute $$S^{-1}(c)$$ without the private key.

Note 1: usually people confuse RSA decryption with the RSA signature. No, it is not. For proper RSA encryption, you need PKCS#1.5 or OAEP padding schemes and for signature you need RSA-PSS padding scheme. And in practice, it is not advised to use the same key for both.

Note 2: As pointed by Tylo, actually Bleichenbacher's attacks and its variations (DROWN, ROBOT) showed that the RSA PKCS#1.5 padding is not secure.

Note 3: PKCS#1 v1.5 padding has no formal security proof but RSA AOEP has.