Identification by RSA

Suppose we have identification scheme as such:

Bob takes random $r$, and encrypts it with Alices public RSA key $(n,e)$, sends $r^e$ to Alice.

Alice decrypts $r$ and sends it back to Bob, becomes identified.

Why it might be a bad idea to use same RSA key for following communication afterwards?

• How Bob be convinced that he is communicating with Alice ? By this way an authentication of Alice's Identity is missing. Brievly, you need a certificate mechanism from a authority. – Robert NACIRI Apr 5 '15 at 17:43
• @RobertNACIRI: I believe that it is assumed that Bob knows Alice's public key; and it is sufficient for Alice to private that she knows the private key. – poncho Apr 5 '15 at 18:24
• To poncho: This isn't so simple, otherwise PKI (with inherent complexity), wouldn't be introduced. – Robert NACIRI Apr 5 '15 at 18:58

Well, consider if Bob is communicating with Alice; Bob sends Alice a random $r^e$, Alice recovers $r$ and sends it back. Then, they proceed to use the same RSA modulus to negotiate a secret key; for example, Bob picks a secret value $m$, computes $m^e$, sends that to Alice, who recovers $m$, and then they both use $m$ to generate secret keys, and use those keys to exchange messages that they want to keep secret.
Here's what can happen; the NSA can then start communicating with Alice; they can send Alice the value $m^e$, Alice (thinking that this is someone else she is supposed to be talking to) recovers $m$, and sends it back. The NSA now has enough information to recover the secret keys that Alice and Bob used to communicate.
And, if you're thinking "well, can't Alice remember the values that she used to communicate with Bob, and refuse to decrypt that", it turns out that's not sufficient. What the NSA can do is pick a random value $k$, compute $k^e$, and send the value $k^e \cdot m^e = (km)^e$. Alice will recover the value $km$, which will look like a random selection, and send that back; the NSA can then compute $km \cdot k^{-1} = m$, and is then able to decrypt the secret traffic.