Cryptography
rsa diffie-hellman one-way-function trapdoor
Updated Wed, 07 Sep 2022 00:27:05 GMT

# Where is the definition of one-way trap-door function used in public key cryptography

This is a rather simple question but I've been unable to find a proper answer for this online.

When defining an asymmetric (public key) algorithm is the one-way trap-door function usage referring to the encryption/decryption function or the key generation process or perhaps both?

I believe that the one-way function is indeed used in the key generation process, but I'm not sure entirely.

For instance when we look upon Diffie-Hellman and RSA, it is known that RSA uses integer factorization as its one-way trap-door, meanwhile Diffie-Hellman uses discrete logarithms.

## Solution

Elliptic curve cryptography (ECC) does not use a one-way trapdoor function. It uses a homomorphically-additive one-way function which transforms a private key into a public key. "Trapdoor" is not a synonym for "one-way" or "invertible". Trapdoor means a function that can be used without knowledge of the "trapdoor" secret, and inverted only with knowledge of the secret.

You can't directly encrypt or decrypt with ECC. You can only agree a key (using Elliptic Curve Diffie-Hellman), and then use that key for symmetric encryption/decryption. Signatures are achieved using a chameleon-hash function, which has a trapdoor (the private key) that can be used to find collisions in order to produce a valid signature that no one else would be able to produce. This is entirely different from the RSA trapdoor function, which allows the trapdoor function to be used in one direction without any secret knowledge, but can be inverted with knowledge of the trapdoor secret.

RSA uses a one-way trapdoor function. The private key (the trapdoor knowledge) and public key are created together from two secret primes when a key pair is generated. The trapdoor function is not used to create the key pair - it's the other way around. Generating the key pair provides the parameters for the trapdoor function. You can directly encrypt with RSA, because there is trapdoor information available that can directly reverse the encryption process. You can also directly sign, by "encrypting" with the private key something that anyone can "decrypt" with the public key.

Summary:

For DH, you choose a private key, and you calculate the public key using $$f(x)=g^x\ mod\ p$$, where the input is the private key and $$g$$ is a well-known generator. This is not a trapdoor function, because although the inverse function is $$f^{-1}(y)=y^{x^{-1}}\ mod\ p$$ (where $$x^{-1}$$ is the modular inverse of $$x$$), the secret needs to be known both for $$f$$ and for $$f^{-1}$$. The definition of a trapdoor function is that the secret trapdoor information is only required when going in one direction.

For ECDH, you choose a private key, and you calculate the public key using $$f(x)=xG$$, where the $$xG$$ operation is scalar multiplication of the scalar $$x$$ with the well-known generator point $$G$$. For the same reason as before, this is not a trapdoor function.

For RSA, the keygen is to pick a public key $$e$$, pick two secret primes $$p$$ and $$q$$, and then calculate the private exponent $$d$$ which can only be calculated with knowledge of $$p$$ and $$q$$ ($$p$$ and $$q$$ are then discarded, and we only retain the modulus $$n=pq$$). The one-way trapdoor function is $$f(x)=x^e\ mod\ n$$, and the secret knowledge to invert the trapdoor function is $$d$$. This allows us to use the inverse function $$f^{-1}(y)=y^d\ mod\ n$$. Unlike DH and EC, we can't re-determine the public key from the private key if we lose the public key exponent $$e$$.