1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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