=========================preview======================
(comp170)[2009](s)mid2~PPSpider^_10160.pdf
Back to COMP170 Login to download
======================================================
Hong Kong University of Science and Technology
COMP170: Discrete Mathematical Tools for Computer Science
Spring 2009
Midterm Exam 2
21 April 2009, 3:00C4:20pm, LT-E

Instructions
1.
This is a closed-book exam consisting of 7 questions.

2.
Please write your name, student number and email address on the cover page of the answer booklet.

3.
Please sign the honor code statement on the second page of the answer booklet.

4.
All answers must be put on the answer booklet. Only the answer booklet needs to be handed in at the end of the exam.

5.
In the answer booklet each question starts on a new page. This is for clarity and is not meant to imply that your answer needs to .ll up all the space provided.

6.
Unless otherwise speci.ed, you must always explain how you derived your answer. A number without an explanation will be considered an incorrect answer.

7.
Please put your student ID card on the desk so the TA can check it.

8.
All mobile phones must be turned o. completely during the exam or else you will be disquali.ed.


You may use the following identities in the exam without having to provide a proof:
1.
n2n3 +3n2 + n
i2
= .
6
i=1
2. For any real number r .
= 1,
n.1
. n
i 1 . r
r = .
1 . r
i=0
3. For any real number r .
= 1,
. n+1 + r
nnrn+2 . (n + 1)r
iri = .
(1 . r)2
i=1
Question 1: [16 points]
Suppose Alice wants to send a message M to Bob using RSA encryption so that only Bob can read it. The plaintext M, as a single positive integer, is encrypted to the corresponding ciphertext C which is then sent to Bob. An adversary, Eve, intercepts the ciphertext in the communication channel and .nds that C = 22. From a public directory, Eve .nds that the public key (e, n) of Alice is (47, 391) and that of Bob is (173, 481). Eve wants to seek your help to break the RSA encryption to recover the original plaintext M.
What is the value of M? Describe in detail all steps required to compute it. In case you need to .nd the multiplicative inverse of a number, there is no need to show details of the extended GCD algorithm. You just need to provide a number and show that it is the multiplicative inverse.
Question 2: [12 points]
Suppose Alice and Bob want to share a secret key but the communication channel between them is not secure enough for the shared key to be sent directly.
They .rst agree on two integers m and n that do not have to be kept secret. Alice then chooses a secret integer a and Bob chooses a secret integer b. Since the channel is not secure, these two secret numbers will not be sent.
Propose a scheme with which Alice and Bob can share a secret key by performing appropriate operations on the numbers above. Explain why your scheme is secure. What is the value of the shared secret key?
Question 3: [16 points]
For each of the following parts, is the statement true or false?
You need to prove your answer, or else you will receive no mark e