Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Ok, so my crpto lecturer in Uni 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 its 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 taken 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 ex 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 customer puts in his jumbled up public key - Hash function calculates the hash - which should be similar to original public key generated by RSA. 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 ?

EDIT:

Guys I am sorry for the confusion. This question has nothing to do with collisions and expoiting 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 ".

share|improve this question
    
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? –  pg1989 Oct 3 '13 at 0:44
    
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 –  sukhvir Oct 3 '13 at 0:47
    
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. –  pg1989 Oct 3 '13 at 0:50
    
You are right .. thanks a lot –  sukhvir Oct 3 '13 at 0:55
3  
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. –  Thomas Oct 3 '13 at 2:47
add comment

1 Answer 1

up vote 7 down vote accepted

@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.

$$e_1 * d \equiv 1\ (\mathrm{mod}\ \phi(N))$$

$$e_2 * d \equiv 1\ (\mathrm{mod}\ \phi(N))$$

$$(e_1 - e_2) * d \equiv 0\ (\mathrm{mod}\ \phi(N))$$

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\ (\mathrm{mod}\ \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...

[Update]

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

share|improve this answer
4  
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. –  fgrieu Oct 3 '13 at 5:01
    
In the second equation above, read $\phi(N)$ or $(p-1)\cdot(q-1)$ where there is $\phi(p-1,q-1)$, sorry. –  fgrieu Oct 3 '13 at 5:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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