Cryptography
- rsa public-key terminology trapdoor
- Updated Wed, 08 Jun 2022 13:59:39 GMT
-
What is a trapdoor permutation?
Can anyone explain to me what a trapdoor one-way permutation is? Is RSA a trapdoor one-way permutation?
Context: I was reading about ring signatures. On page 560, it describes steps to implementing a ring signature. I am confused by step 3, where $g()$ is a trap-door permutation. The paper briefly says that $g()$ is an RSA trap-door permutation. I thought that RSA was a public-key encryption protocol. Is RSA a trapdoor permutation?
Solution
Read Wikipedia: Trapdoor function
Then read Luca Trevisan's lecture notes (jump straight to section 2. Trapdoor Permutations and Encryption). Or, read any other textbook or lecture notes that covers trapdoor permutations.
For instance, if $(n,e)$ is a RSA public key, then $f(x) = x^e \bmod n$ is a trapdoor permutation. It is a permutation, since the function $f:S\to S$ is bijective (where $S=(\mathbb{Z}/n\mathbb{Z})^*$). It is a trapdoor one-way permutation, since given $x$ and the public key, we can easily compute $f(x)$, but given $y$ and the public key, it is difficult to compute $f^{-1}(y)$; yet with the private key (the trapdoor), we can easily compute $f^{-1}(y)$, given $y$.
That should answer your question.
Comments (2)
- +0 – Thanks for the explanation. I think I get the general idea, but I don't quite understand the math behind it. They describe the function g(x), which uses the RSA's public exponent e and modulus n. What would g(x)^-1 be in this case when provided with my RSA's private component d? — Nov 14, 2012 at 19:27
- +0 – @user1812844, If $g(x)=x^e \bmod n$, then $g^{-1}(y) = y^d \bmod n$. Again, read lecture notes or other stuff on trapdoor one-way permutations and RSA -- this is standard stuff that should be covered in textbooks. — Nov 14, 2012 at 20:00
External Links
External links referenced by this document: