Ok, so my cryptography lecturer in University posed this question at the end of the RSA key generation lecture as a brain teaser.

I have been thinking about this and I think I have come up with a way ( I am aware it's not practical and very vulnerable - but I would love for you guys to punch holes through it ):

Use RSA to generate public and private key pair.

Make an additive hash function that takes in any input and adds the ASCII value of each character and gives that as an output. ( I am aware additive hash has horrible distribution, for example, ABC, BAC, ACB all have the same hash output -- but theoretically, this can be used as an advantage to solve our problem )

Now take your public key and generate several possible keys by jumbling up the on and off bits.

Give these jumbled up keys to potential customers.

Put our hash function on the server.

When a customer puts in his jumbled up public-key - Hash function calculates the hash - which should be similar to original public key generated by RSA. The customer gets access.

Once again I am aware that this is very vulnerable and terrible. It cant be used in the real world. But does it answer the question my lecturer posed?


I am sorry for the confusion. This question has nothing to do with collisions and exploiting the maths ( Those are definitely valid ways to do that - but they weren't what my lecturer was referring too - they were discussed in the lecture itself. ). The way my lecturer asked this question was - " come up with ways to make several public keys related to a single private key - nevermind how vulnerable your solution is ".

  • $\begingroup$ Can't you just add integer multiples of $\phi(N)$ to a public key to generate an infinite number of valid public keys for any private key? $\endgroup$
    – pg1989
    Commented Oct 3, 2013 at 0:44
  • $\begingroup$ I didn't know that was possible ... so adding ϕ(N) to (n,e) gives another public key which is paired with (n,d) private key. I wasn't even aware this was possible .. But thanks $\endgroup$
    – sukhvir
    Commented Oct 3, 2013 at 0:47
  • $\begingroup$ Well think about how public and private keys are generated. You just need $e$ and $d$ s.t. $e*d = 1 mod \phi(N)$. Adding multiples of $\phi(N)$ changes nothing, because they'll just drop out in the modular reduction. $\endgroup$
    – pg1989
    Commented Oct 3, 2013 at 0:50
  • 7
    $\begingroup$ Plus, if you do that and someone gets hold of two public keys, he can take the difference and get hold of a multiple of $\varphi{(N)}$, and, well, game over. $\endgroup$
    – Thomas
    Commented Oct 3, 2013 at 2:47
  • $\begingroup$ Related answers: stackoverflow.com/questions/3100192/pki-multiple-public-keys stackoverflow.com/questions/9375044/… $\endgroup$
    – skywinder
    Commented Sep 9, 2019 at 2:19

1 Answer 1


@pg1989 has not only the right answer but the only answer if you assume the goal is to have multiple RSA encryption exponents that correspond to the same decryption exponent.

\begin{align} e_1 \cdot d & \equiv 1 \pmod{\phi(N)}\\ e_2 \cdot d & \equiv 1 \pmod{\phi(N)}\\ (e_1 - e_2) \cdot d & \equiv 0 \pmod{\phi(N)} \end{align}

But since $d$ is relatively prime to $\phi(N)$, by Euclid's lemma $\phi(N)$ must divide $e_1 - e_2$ :

$$e_1 \equiv e_2 \pmod{\phi(N)}$$

In other words, any two public RSA exponents that share a private exponent must differ by some multiple of $\phi(N)$.

I highly suspect this is what your professor was thinking. Although, as @Thomas points out if the multiple is small and someone gets hold of both public keys, they can factor $N$. Now, maybe if you use a big multiple...


As @fgrieu notes in a comment, I have conflated $\phi(N) = (p-1)(q-1)$ with $\operatorname{LCM}(p-1, q-1)$. Replace the former with the latter in the above derivation for the right answer.

  • 5
    $\begingroup$ The necessary and sufficient condition for a public expoment $e_j$ to work with private key $d$ is $e_j\cdot d\equiv1\pmod{\mathrm{LCM}(p-1,q-1)}$. This increases the number of $e_j$ we can choose for a given maximum for the $e_j$, compared to the sufficient but not necessary $e_j\cdot d\equiv1\pmod{\phi(p-1,q-1)}$. As stated by Thomas, two holders of $e_j$ could collude and factor the public modulus. $\endgroup$
    – fgrieu
    Commented Oct 3, 2013 at 5:01
  • $\begingroup$ In the second equation above, read $\phi(N)$ or $(p-1)\cdot(q-1)$ where there is $\phi(p-1,q-1)$, sorry. $\endgroup$
    – fgrieu
    Commented Oct 3, 2013 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.