=========================preview======================
(COMP170)Midterm2_2008_review.pdf
Back to COMP170 Login to download
======================================================
COMP 170 C Fall 2008
Midterm 2 Solution

Q1. Bob is constructing an RSA key-pair. He .rst chooses p = 11, q = 19 and sets n = 11 19 = 209. He then constructs his public key e and private key d and publishes the (n, e) pair.
(a) Bobs private key is d =7. What is the value of his public key e?.
Q1. Bob is constructing an RSA key-pair. He .rst chooses p = 11, q = 19 and sets n = 11 19 = 209. He then constructs his public key e and private key d and publishes the (n, e) pair.
(a) Bobs private key is d =7. What is the value of his public key e?.
By the de.nition of the RSA algorithm d e mod T =1 where
T =(p . 1)(q . 1) = 10 18 = 180.

Using, e.g., the extended GCD algorithm, we .nd that the multiplicative inverse of 7 mod T is e = 103.
Q1. Bob is constructing an RSA key-pair. He .rst chooses p = 11, q = 19 and sets n = 11 19 = 209. He then constructs his public key e and private key d and publishes the (n, e) pair.
(b) Alice wants to send Bob a message M, 0 <M <n.
She calculates X = Me mod n to send Bob and .nds
that X = 15.
What is the value of the original message M?

Q1. Bob is constructing an RSA key-pair. He .rst chooses p = 11, q = 19 and sets n = 11 19 = 209. He then constructs his public key e and private key d and publishes the (n, e) pair.
(b) Alice wants to send Bob a message M, 0 <M <n.
She calculates X = Me mod n to send Bob and .nds
that X = 15.
What is the value of the original message M?

M = Xd mod n = 157 mod 209 = 203.

(The last equality can be derived any of multiple ways)

Q2(a) Is (1560 mod 61) = (1562 mod 63)? Q2(b) Is (100440 mod 89) = (1001320 mod 89)? Q2(c) Evaluate 31052 mod 60.
Q2.(a) Is 1560 mod61 = 1562 mod63 ?

No.
61 is a prime number so, by Fermats little theorem,
1560 mod 61 = 1..

On the other hand, since 3|15, we also have 3|1562 .
Since 3|63, this means that 3|(1562 mod 63),
so 1562 mod 63 .

=1.
Q2.(b) Is 100440 mod89 = 1001320 mod89 ?

Yes.
89 is prime so, by Fermats little theorem,

10088 mod 89 = 1.
Since both 440 and 1320 are divisible by 88 we have
100440 mod89 =1= 1001320 mod 89 .
Q2.(c) Evaluate 31052 mod 60.

This can be solved by repeated squaring. Set Ii =32i mod 60. Then
I0 =3 I1 = I0 I0 mod 60 = 9 I2 = I1 I1 mod 60 = 21
Now notice that 21 21 mod 60 = 21 so, for all i 2,Ii = 21. Since
31052 =31024 3128

we .nd
(31052 mod 60) = (I7 I10 mod 60) = (212 mod 60) = 21.

(a) (i) (p q) (.p .q)
(ii) (p . q) (q . p)
(b)
(i) .x Up(x) ..x Uq(x)


(ii) .x Up(x) . q(x)

(c)
(i) .x Up(x) ..y Vq(y)

(ii)
.x U .y V (p(x) . q(y))


(b) (i) .x Up(x) ..x Uq(x)


(ii)
.x Up(x) . q(x)




(c)
(i) .x Up(x) ..y Vq(y)



Q3.
(a) (i) (p q) (.p .q)
(ii) (p . q) (q . p)

(ii) .x U .y V (p(x) . q(y))
For each pair, either prove that they are logically equivalent or give a counterexample.
(a) (i) (p