=========================preview======================
(comp170)[2009](s)Midterm2~PPSpider^sol_10163.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
Solutions
Question 1: From the encryption step of the RSA algorithm, we know that
C = Me mod n,
where (e, n) = (173, 481) is the public key of Bob.
We also know that n is the product of two prime numbers p and q, i.e., n = pq. Let T =(p . 1)(q . 1). From the decryption step of the RSA algorithm, we can recover M as
M = Cd mod n,
where d is the multiplicative inverse of e in ZT , i.e., de mod T = 1.
One way to break the RSA encryption is to factorize n. Since n = 481 = 13 37, we let
p = 13 and q = 37. Hence, T = 12 36 = 432.
The multiplicative inverse d satis.es the following equation:

de = kT + 1 or 173d = 432k +1
for some integer k. We note that d = 5 satis.es the equation for k = 2. The original plaintext M can be found as follows:
M = 225 mod 481 = ((222 mod 481)2 22) mod 481 = (32 22) mod 481 = 198.
Question 2: Alice computes A = m a mod n and sends it to Bob. Similarly, Bob computes B = m b mod n and sends it to Alice. Upon receiving A from Alice, Bob computes
K1 = Ab mod n = m ab mod n.
1
Similarly, upon receiving B from Bob, Alice computes
K2 = Ba mod n = m ab mod n.
Since K1 = K2 = mab mod n, it is the key shared by Alice and Bob.
This scheme (and the key) is secure because
f(a)= m a mod n
g(b)= m b mod n

are one-way functions, in the sense that it is easy to compute f(a) and g(b) from a and b but it is di.cult to compute a and b from f(a) and g(b).
Question 3: (a) False. The remainder is equal to 71980 mod 47. Since 47 is prime and gcd(7, 47) = 1, we can apply a variant of Fermats little theorem to compute the remainder as
71980 mod 46 mod 47 = 72 mod 47 = 2 =1.
(b)
False. If p =F,q =T,r = F, then the truth value of the .rst statement is T but that of the second statement is F.

(c)
False. It su.ces to prove that the negation of the statement, i.e.


..x Z+ (.y Z (x + y 4))
or
.x Z+ (.y Z (x + y< 4)) is true. For every x Z+, we can choose y =4 .x.1 Z to satisfy the inequality x + y< 4. So we are done.
(d)
True. We can prove this by induction. For the base case (x = 1), 6 divides x3 . x =1 . 1 = 0 because any positive integer divides 0. So the base case holds. For x> 1, we assume that it holds for x . 1, i.e., 6 | ((x . 1)3 . (x . 1)). To show that 6 | (x3 . x), it su.ces to show that 6 | ((x3 . x) . ((x . 1)3 . (x . 1))). Because (x3 . x) . ((x . 1)3 . (x . 1)) = 3x2 . 3x =3x(x . 1) and x(x . 1) is an even number (i.e., 2 is a divisor) for all x> 1, so both 2 and 3 divide 3x(x . 1) and hence 6 also divides it. By the principle of MI, we can prove the correctness of the statement.

(e)
False. One counterexample is the prime number p = 5, but p!+1 = 121 = 112 is composite.


Question 4: (a) (i) .x (Student(x) . Smart(x))
(ii) .x (Politician(x) .Smart(x))