# challenge response for RSA

I've got a homework question asking to explain challenge-response in reference to RSA encryption and signatures. There really doesnt seem to be much or any explanations online. can anyone help me out.

Basic Idea: For simplicity, assume the server $S$ is trusted.

Then all the server has to do is to prove that it has the private key $(n,d)$ corresponding to its public key $(n,e)$ which is trusted, say, via a PKI.

The client uniformly generates a random value $X \in Z_n,$ keeps it private, and then encrypts it into $$Y=X^e ~(mod~n)$$ and sends $Y$ to the server. The server obtains $$Z=Y^d~(mod~n)=X^{ed}~(mod~n)$$ and sends $Y$ back to the client.

By the uniqueness of inverses modulo $\varphi(n)$ we know that $$ed\equiv 1~(mod~\varphi(n))$$ if and only if the private key is correct. Thus all the client needs to do is to check that $Z$ equals the original $X$ it had generated.

I have used plain RSA with no randomisation or encapsulation. There are many wrinkles if we want to protect against replay attacks, etc., but your question sounds like a basic question.

Edit: (Thanks to @fgrieu) copied for completeness of answer, hope he/she doesn't mind.

In challenge/response, the answer's server is more generally known as prover; and the answer's client as verifier. The question also hints at using RSA signature for that: verifier generates and sends random $X;$ prover signs it as $Y=X^d~(mod~n)$ and sends signature $Y$; verifier computes $Z=Y^e~(mod~n)$ and verifies that $Z=X.$ The answer's method given above uses encryption, with the advantage that $X$ is not known to attackers and can be used to derive a shared secret key. But the signature method allows $Z$ to carry information that the prover has signed.

• I believe and sends Y back to the client should be and sends Z back to the client? – Dan Jun 1 '17 at 2:00
• I agree with Dan. – user253751 Oct 28 '19 at 12:07