1
$\begingroup$

I am working on this exercise but can't work out the answer to the question b. I have solved the question (a) by decrypting the ciphertext $C = 2$ using the formula: $$ M = C^d \bmod n = 2^{17} \bmod 21 = 11 $$

Alice and Bob agree to communicate using the RSA cryptosystem. Alice has a private key ($n = 21$, $d = 17$) and a public key ($n = 21$, $e = 5$).

  • (a) Alice receives the ciphertext $C = $2 from Bob. Decrypt this message, show your working.

  • (b) Bob wishes to ensure that he sent the ciphertext to Alice. Bob sends Alice the plaintext message $M = 9$, what message should Alice send back?

  • (c) Perform the calculation Bob would do to verify this returned message.

What do you guys think?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
5
$\begingroup$

Basically $M = 9$ is a challenge. Alice will have to sign it (compute $M^d \pmod {21})$, because only she knows $d$. As $(M^e)^d = (M^d)^e = M \pmod{21}$, it should be clear what Bob should do to verify that the reply indeed equals $M^d$, which only Alice could have produced...

Improve this answer
$\endgroup$
1
$\begingroup$

You are looking for digital signatures using RSA. Have a look at this question. It will help you understand the parts a) and b) of your exercise.

Improve this answer
$\endgroup$
1
$\begingroup$

Henno Brandsma's answer, properly implemented, should get high marks. But in my opinion this exercise is poor (which answers the question as worded), for many reasons:

  • If Bob and Alice do as in (b), that can't be a way for Bob " to ensure that he sent the cyphertext to Alice "; Bob could as well have been sending the message to Eve in (a), and/or be sending the challenge of (b) to Eve who will relay to Alice to pass the test. The best (b) could aim to achieve is that Alice is participating to (b); that's if we had been using much larger numbers.
  • If Alice does as suggested in (b), she compromises the security of what is done in (a); for example Eve that really received the cryptogram with value 2 in (a) could send it to Alice in the context of (b), and obtain from Alice the very plaintext message Bob has wished to privately send to Alice in (a). Add that Eve can send any message to Alice the way Bob does in (a), and we have a total security failure: Eve knows what Bob tried to secretely say to Alice, Bob wrongly believes it reached Alice, but something Eve forged reached Alice.
  • (b) is a challenge-response protocol, and using " plaintext message " for what amounts to a challenge is misleading.
  • The exercise is worded as if that was RSA encryption or authentication save for the small numbers; that's not, for modern definitions of asymmetric encryption or authentication, for it is missing the critical notion of padding.
  • The exercise is about the different roles of the public-key and private-key in encryption (a), and authentication (b and c); but the numerical example is such that the public key and private key perform exactly the same thing!
    Notice that $d=17$ is not the sole private exponent; $d$ is one representative of the class of private exponents, these are defined modulo $\lambda(N)=\operatorname{lcm}(3-1,7-1)=6$, thus $d=5$ or $d=11$ are as good as $d=17$ is (and easier to work with on top of that).
    The choice of $d=17$ might have been intentional (so that using $d$ where $e$ is required, or vice-versa, does not show on the result, but can be caught by looking at what's done); I fail to see how such trickery could be pedagogical.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I agree, but it's just a conceptual exercise, I suppose. It might be part of some algebra course without crypto focus, e.g., so padding, replay attacks etc. are not relevant, but just the application of some algebra theory that was just treated, e.g. I didn;t want to get things in that the OP wouldn't know about. $\endgroup$
    – Henno Brandsma
    Dec 12, 2015 at 15:54
0
$\begingroup$

What about this for the question B:

Alice should send back an encrypted message generated from the plaintext Bob sent to her ($M = 9$) using the decrypted message Bob sent earlier ($11$) as the $e$ key.

$$C = M^e \bmod{n} = 9^{11} \bmod{21} = 31381059609 \bmod{21} = 18$$

Alice should send back 18 in order to let Bob know that she has received the message he sent earlier.

Improve this answer
$\endgroup$
0

Your Answer

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